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

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

Постановка задач исследования. Необходимо провести улучшение алгоритма масштабирования, для чего необходимо проанализировать существующие алгоритмы и их недостатки. В качестве улучшения предложен метод контентно-зависимого масштабирования, в основе которого лежит предварительный анализ изображения

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

Недостатком билинейной интерполяции при масштабировании изображений является тот факт, что при увеличении в N раз изображения размером W на H пикселей в результате будет получено изображение размером не NW на NH пикселей, а (N(W − 1) + 1) на (N(H − 1) + 1) пикселей. Пример масштабирования с применением билинейной интерполяции показан на рисунке 1.

Бикубическая интерполяция идёт на один шаг дальше билинейной, рассматривая массив из 4x4 окружающих пикселей — всего 16. Поскольку они находятся на разных расстояниях от неизвестного пикселя, ближайшие пиксели получают при расчёте больший вес. Бикубическая интерполяция производит значительно более резкие изображения, чем предыдущие два метода, и возможно, является оптимальной по соотношению времени обработки и качества на выходе. По этой причине она стала стандартной для многих программ редактирования изображений (включая Adobe Photoshop), драйверов принтеров и встроенной интерполяции камер.

Рисунок 1 – Увеличение изображения простым масштабированием (а) и с применением билинейной интерполяции (б)

Многие алгоритмы работают только при увеличении в целое число раз: 2x, 3x и 4x.

Существует так же группа адаптивных алгоритмов, включающая в себя многие коммерческие алгоритмы в лицензированных программах, таких как Qimage, PhotoZoom Pro, Genuine Fractals и другие. Многие из них применяют различные версии своих алгоритмов (на основе попиксельного анализа), когда обнаруживают наличие границы — с целью минимизировать неприглядные дефекты интерполяции в местах, где они наиболее видны. Эти алгоритмы в первую очередь разработаны для максимизации бездефектной детальности увеличенных изображения, так что некоторые из них для вращения или изменения перспективы изображения непригодны.

Рассмотрим алгоритм контентно-зависимого масштабирования Seam Carving — это алгоритм изменения размеров изображения, который учитывает содержимое изо­бражения (как называют авторы — Content-Aware Image Resizing Algorithm). Впервые был предложен в 2007 году.

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

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

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

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

Шаг 1. Для определения важности пикселя изображения необходимо посчитать его энергию: чем больше энергия — тем важнее точка. Существует множество способов вычисления энергии. Одна из самых простых функций дает наиболее оптимальные результаты (формула 1).

                (1)

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

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

            

а)                                                          б)
Рисунок 2 – Пример «правильных» (а) и «неправильных» (б) цепочек

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

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

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

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

Шаг 3. Наша задача — изменение размера изображения. Увеличение и уменьшение изображение немного отличаются, поэтому сначала будет рассмотрено уменьшение, а потом уже увеличение. Если необходимо уменьшить ширину изображения на 1 пиксель, то все просто: находится вертикальную цепочка, как описано выше, и просто удаля­ется.

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

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

Рисунок 3 – Оригинальное(а) и уменьшенное по горизонтали(б) изображения

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

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

Выводы.В результате анализа существующих алгоритмов масштабирования были выявлены их основные недостатки. Для оптимизации масштабирования был предложен метод контентно-зависимого масштабирования. В дальнейшем планируется совершенствование алгоритма и его программная реализация.

Список литературы

1. «Liquid Rescale» - http://liquidrescale.wikidot.com/en:examples
2. «Liquid Resize своими руками» - Habradigest, №7, январь 2009
3. «Билинейная интерполяция» - http://ru.wikipedia.org/wiki/Билинейная_интерполяция
4. «Алгоритмы масштабирования пиксельной графики» - http://ru.wikipedia.org/wiki/Алгоритмы_масштабирования_пиксельной_графики