Шеховцов С.О.


Название статьи: Контентно-зависимое масштабирование изображений с использованием алгоритма Seam Carving
Источник: Матеріали IV міжнародної науково-практичної конференції молодих учених, аспірантів і студентів «Сучасна інформаційна Україна: інформатика, економіка, філософія» — Державний університет інформатики і штучного інтелекту, Донецьк, 13-14 травня 2010.

Текст статьи

Одной из задач компьютерной графики является масштабирование – изменение размера изображения. При этом в зависимости от типа графики (растровая, векторная), масштабирование производится по разным алгоритмам. Если графика векторная, то масштабирование происходит без потерь качества изображения, если растровая, то при масштабировании происходит потеря качества изображения, особенно при изменении размера без сохранения пропорций.

Была поставлена задача улучшение алгоритма масштабирования, путем применения метода контентно-зависимого масштабирования, в основе которого лежит предварительный анализ изображения

Алгоритм Seam Carving — это алгоритм изменения размеров изображения, который учитывает содержимое изо­бражения, впервые был предложен в 2007 году.

Способ учи­тывает содержимое изображения: сначала вычисляется важность раз­ных участков изображения, после чего изменяются в размере только те части, которые, по мнению ал­горитма, являются не такими важными. Основные проблемы алгоритма: как определить насколько важными являются части изображения, как найти и сжать ме­нее важные участки изображения и т. д.

Основные шаги алгоритма для горизонтального масштабирования (для вертикального – аналогично):

  1. Нахождение энергии каждой точки.
  2. Нахождение такой вертикальной цепочки пик­селей, чтобы суммарная энергия пикселей, которые входят в эту цепочку была минимальной.
  3. После нахождения цепочки с минимальной энерги­ей, необходимо ее удалить, если выполняется уменьшение изображения, или растянуть, если выполняется увеличение

Рассмотрим алгоритм более детально.

Шаг 1. Для определения важности пикселя изображения необходимо посчитать его энергию: чем больше энергия — тем важнее точка. Энергия пикселя равна изменению цвета со­седних пикселей по сравнению с данным пикселем. То есть чем больше разница в цвете между данным пиксе­лем и соседними — тем больше его энергия.

Шаг 2. После определения значения энергий необходимо выбрать те пиксели у ко­торых это значение минимальное. Для начала необходимо определить  «правильную» цепочку пикселей — это набор точек, такой, что в каждой строчке изображения выбран ровно один пиксель, а пиксели в соседних строчках «соединены» или сторонами, или углами.

Выбирать следует цепочку, в которой сумма энергий пикселей, которые входят в нее, минимальна. Для ее нахождения следует применить динамическое программирование. Сначала создается новый массив, который по размеру равен массиву с энергиями пикселей. В этот массив для каждого пикселя записывается сумма эле­ментов минимальной цепочки пикселей, которая на­чинается у верхнего края изображения и заканчива­ется на данном пикселе.

Сначала определяется, какой пиксель из нижней строчки изображения принадлежит этой цепочке: искомый элемент будет иметь наименьшее значение в массиве сумм среди элементов нижней строчки. Интересующие нас заканчиваются на пикселе из последнего ряда. Соответственно для всего рисунка минимальная цепочка будет выбрана как минимальная из всех минимальных цепочек, которые заканчиваются на пикселях из нижней строчки.

После этого возможно нахождение пикселя из предпоследней строчки. Из нижнего пикселя мы можем пойти только в 3 соседние пиксели на строчку выше: слева-сверху, сверху или справа-сверху. Среди этих пикселей выбираем пиксель с минимальным значением в масси­ве сумм, и переходим к нему. Продолжаем, пока не дойдем до верхней строчки.

После выполнения всех этих операций будет получен набор пикселей, которые возможно изменить с минимальными потерями для изо­бражения.

Шаг 3. Рассмотрим отдельно уменьшение и увеличение изображения. Если необходимо уменьшить ширину изображения на один пиксель, то все просто: находится вертикальную цепочка, как описано выше, и просто удаляется. Если необходимо уменьшение на большее значение, то выполняется операция удаления цепочки столько раз, сколько необходимо (каждый раз при этом надо будет искать новую цепочку).

Следует обратить внимание, что операция уменьшения изображения на n пикселей и операция уменьшения изображения на один пиксель n раз не являются экви­валентными. При уменьшении на один пиксель n раз, для каждого из проме­жуточных изображений ищется энергия пикселей, а если сразу происходит уменьшение на n, то энергия пикселей берется из исходного изображения.

При увеличении изображения нельзя просто выбирать цепочки и их «растягивать». Необходимо брать не одну минимальную цепочку, а столь­ко, сколько надо, чтобы дополнить рисунок до нужной ширины (как при обычном растягивании), но увеличивать изображение следует поэтапно: так, чтобы на каждом этапе охватывалось как можно больше «не важных» частей изображения, и как можно мень­ше «важных». Один из вариантов разбиения на этапы такой, что на каждом этапе изображение не увеличивается больше, чем на 50%. Пример увеличения показан на рисунке 1.




Рисунок 1 – Оригинальное(а) и увеличенное по горизонтали(б) изображения

В дальнейшем планируется совершенствование алгоритма и его программная реализация.

1. «Liquid Rescale» -http://liquidrescale.wikidot.com/ en:examples
2. «Liquid Resize своими руками» - Habradigest, №7, январь 2009