• Введение
• Цели и задачи, которые должны решаться
• Актуальность темы
• Предполагаемая научная новизна
• Планируемые практические результаты
• Обзор наиболее популярных алгоритмов масштабирования
• Алгоритм контентно-зависимого масштабирования
• Выводы

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

Компьютерная графика используется практически во всех научных и инженерных дисциплинах для наглядности восприятия и передачи информации.

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

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

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

В ходе исследования должны быть решены следующие задачи:

1. Выявление основных недостатков существующих алгоритмов, поиск возможностей их устранения.
2. Разработка алгоритма, анализирующего изображение по его содержимому и выявляющего наиболее и наименее значимые участки изображения.
3. Разработка алгоритма, масштабирующего изображение на основе полученных при анализе данных.
4. Программная реализация алгоритма, обеспечивающая контентно-зависимое масштабирование.
5. Анализ и сравнение результатов, полученных при использовании разработанных алгоритмов и существующих уже алгоритмов.

Задача масштабирования — изменение размеров изображения — широко применяется в различных сферах. Эта задача особенно актуальна для переноса изображений на мобильные устройства, где оно не может отображаться в полном масштабе, для размещения изображений на сайтах. Увеличение изображений часто применяется для более детального обзора фрагмента изображения, при обработках изображений и т.д.

Основная задача при масштабировании — сохранение достаточного качества изображения. Поиск эффективных способов реализации данного алгоритма является предметом исследований многих ученых различных стран мира. К ним относятся:

1. Джефф Этворд (бывший сотрудник Vertigo Software, Поинт Ричмонд, Калифорния). http://www.codinghorror.com/blog/2007/07/better-image-resizing.html
2. Шаи Авидан (сотрудник Mitsubishi Electric Research Labs, Северная Америка). http://portal.acm.org/citation.cfm?id=1276377.1276390
3. Ариэль Шамир (Техасский университет в Остине). http://portal.acm.org/citation.cfm?id=1457515.1409064

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

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

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

Также планируется проведение комплексного анализа и сравнения практических аспектов реализации различных алгоритмов масштабирования.

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

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

Также существуют улучшенные увеличвающие алгоритмы, разработанные для компьютерной графики, которые называются supersampling (сглаживание). Лучшие результаты на таких алогритмах достигаются при увеличении изображений с несколькими цветами в малом разрешении.^[1]

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

В вычислительной математике билинейной интерполяцией называют расширение линейной интерполяции для функций в двух переменных. Ключевая идея заключается в том, чтобы провести обычную линейную интерполяцию сначала в одном направлении, затем в другом.

Рисунок 1 — Результат билинейой интерполяции на сетке [0, 3] x [0, 3]. Черными точками обозначены известные значения

Результат билинейной интерполяции не зависит от порядка шагов. Возможно сначала интерполировать между известными точками вдоль оси ординат и затем, получив два вспомогательных значения, интерполировать между ними вдоль оси абсцисс. Результат будет тот же.^[2]

В компьютерной графике билинейная интерполяция получила широкое распространение в процессе ресемплинга (или, проще говоря, масштабирования) изображений.

При увеличении цифровых изображений наблюдается сильная пикселизация картинки. Билинейная интерполяция используется для расчета цветов дополнительных пикселей (P) относительно основных, исходных (Q), что позволяет сглаживать переходы. Значением функции f в данном случае выступает цвет пикселя (его составляющие). При этом квадрат, образованный четырьмя рассматриваемыми основными точками принимается единичным.^[2]

Рисунок 2 — Пример увеличения части изображения - простым масштабированием(слева) и с применением билинейной интерполяции(справа)

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

Связано это с тем, что в исходном изображении, например, по горизонтали имеется W точек, т.е. (W−1) смежных пар. При увеличении изображения в N раз между каждой парой основных точек вставляется по (N−1) дополнительных точек (т.е. при увеличении вдвое между основными точками вставляется еще по одной, при увеличении втрое — по две и т.д.). Итого в результате ширина результирующего изображения будет равна сумме количества основных и дополнительных точек:

Проще говоря, для последнего пикселя (в каждой строке и столбце) исходного изображения не находится пары, с которой можно было бы провести интерполирование.^[2]

В вычислительной математике бикубической интерполяцией называется расширение кубической интерполяции на случай функции двух переменных, значения которой заданы на двумерной регулярной сетке. Поверхность, полученная в результате бикубической интерполяции является гладкой функцией, в отличие от поверхностей, полученных в результате билинейной интерполяции или интерполяции методом ближайшего соседа. Так же бикубическая интерполяция часто используется в обработке изображений, давая более качественное изображение по сравнению с билинейной интерполяцией.^[3]

Допустим, что необходимо интерполировать значение функции f(x,y) в точке P(x,y), лежащей внутри квадрата [0, 1] x [0, 1], и известно значение функции f в шестнадцати соседних точках (i, j), i=-1…2, j=-1…2. Тогда общий вид функции, задающей интерполированную поверхность, может быть записан следующим образом:

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

Рисунок 4 — Результат интерполяции методом ближайшего соседа на сетке [0, 3] x [0, 3]. Черными точками обозначены известные значения

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

Алгоритмы предискретизации. Передискретиза́ция (англ. resampling) в обработке сигналов — изменение частоты дискретизации дискретного (чаще всего цифрового) сигнала. Алгоритмы передискретизации широко применяются при обработке звуковых сигналов, радиосигналов и изображений (передискретизация растрового изображения — это изменение его разрешения в пикселах).

Отсчёты сигнала, соответствующие новой частоте дискретизации, вычисляются по уже имеющимся отсчётам и не содержат новой информации.

Повышение частоты дискретизации называется интерполяцией, понижение — децимацией.

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

При передискретизации отсчёты сигнала, соответствующие одной частоте дискретизации, вычисляются по имеющимся отсчётам этого же сигнала, соответствующим другой частоте дискретизации (при этом предполагается, что обе частоты дискретизации соответствуют условиям теоремы Котельникова). Идеальная передискретизация эквивалентна восстановлению непрерывного сигнала по его отсчётам с последующей дискретизацией его на новой частоте.^[5]

Точное вычисление значения исходного непрерывного сигнала в определённой точке производится следующим образом:

где x(ti) — i-й отсчёт сигнала, ti — момент времени, соответствующий этому отсчёту, ωd = 2πfd — циклическая частота дискретизации, x(t) — интерполированное значение сигнала в момент времени t.

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

где h(t) — импульсная характеристика соответствующего восстанавливающего фильтра. Вид этого фильтра выбирается в зависимости от задачи.

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

1. децимация с целым коэффициентом (уменьшение частоты дискретизации в целое число раз);
2. интерполяция с целым коэффициентом (увеличение частоты дискретизации в целое число раз);
3. изменение частоты дискретизации в рациональное (M/N) число раз (этот случай можно рассматривать как комбинацию двух предыдущих).

При таких ограничениях становится удобным применение стандартных реализаций цифровых фильтров для передискретизации

Выбор функции h(t) обуславливается компромиссом между качеством передискретизации (то есть близости её к идеальной) и вычислительной сложностью этого процесса. В принципе, для передискретизации может быть использован любой фильтр нижних частот с необходимой частотой среза. КИХ-фильтры применяются для этих задач чаще, чем БИХ-фильтры, из-за возможности построения КИХ-фильтров с линейной фазо-частотной характеристикой.^[5]

Для передискретизации изображений применяется большое число фильтров, которые можно классифицировать следующим образом:

1. Фильтры интерполяционного типа, обладающие сравнительно узкой импульсной характеристикой. К ним относятся, в частности, треугольный фильтр, производящий билинейную интерполяцию и полином Лагранжа, с помощью которого можно реализовать бикубическую интерполяцию. Применение таких фильтров позволяет осуществить передискретизацию изображения достаточно быстро.
2. Фильтры с колоколообразной характеристикой, такие как фильтр Гаусса. Эти фильтры хорошо справляются с пикселизацией, звоном и алиасингом, а также отфильтровывают высокочастотные шумы. Их недостаток — заметное размытие изображения.
3. Оконные sinc-фильтры. Sinc-фильтр — это идеальный фильтр нижних частот. Как говорилось выше, он не может быть реализован. Однако если частотную характеристику sinc-фильтра умножить на оконную функцию, получится реализуемый фильтр с хорошими спектральными свойствами. При применении данных фильтров к изображениям удаётся сохранить относительно высокую чёткость (даже при увеличении разрешения), но может быть сильно заметен эффект звона. Одним из наиболее часто применяемых фильтров данного типа является фильтр Ланцоша.^[1]

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

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

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

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

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

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

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

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

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

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

а)                          б)

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

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

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

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

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

Шаг 3. Наша задача — изменение размера изображения. Увеличение и уменьшение изображение немного отличаются, поэтому сначала будет рассмотрено уменьшение, а потом уже увеличение.

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

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

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

Рисунок 6 — Оригинальное изображение




Рисунок 7 — Уменьшенное по горизонтали изображение




Рисунок 8 — Уменьшенное по вертикали изображение

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

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

1. Thyssen A. Resize and Scaling. // Examples of ImageMagick Usage (Version 6), 2009. — http://www.imagemagick.org/Usage/resize/
2. Билинейная интерполяция. // Статья википедии — свободной Интернет-энциклопедии — http://ru.wikipedia.org/wiki/Билинейная_интерполяция
3. Бикубическая интерполяция. // Статья википедии — свободной Интернет-энциклопедии — http://ru.wikipedia.org/wiki/Бикубическая_интерполяция
4. Алгоритмы масштабирования пиксельной графики // Статья википедии — свободной Интернет-энциклопедии — http://ru.wikipedia.org/wiki/Алгоритмы_масштабирования_...
5. Ronald E. Crochiere, Lawrence R. Rabiner. Multirate digital signal processing. — Prentice-Hall, 1983. — http://www.flipkart.com/multirate-digital-signal-processing-lawrence-book-0136051626
6. Liquid Rescale. // Content-aware resizing for the GIMP, 2009. — http://liquidrescale.wikidot.com/en:examples
7. Михаил М. Liquid Resize своими руками. — Habradigest, №7, январь 2009. — http://habradigest.ru/hd/habradigest_07.pdf
8. Конник М. Новый метод масштабирования растровых изображений с учётом их содержимого Liquid Rescale. — Записки дебианщика, 2007. — http://mydebianblog.blogspot.com/2007/09/blog-post.html
9. Шеховцов С.О. Контентно-зависимое масштабирование изображений с использованием алгоритма Seam Carving // Искусственный интеллект.— Донецк: ІПШІ МОН і НАН України “Наука і освіта”, 2010.
10. Шеховцов С.О. Анализ недостатков алгоритмов масштабирования. Контентно-зависимое масштабирование // ІУС та КМ-2010 — Матеріали І всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених — Донецьк: ДонНТУ, 19-21 травня 2010. — 634с.

При написании данного реферата, магистерская работа еще не завершена. Окончательное завершение: декабрь 2010 года. Полный текст работы и все материалы по теме могут быть получены у автора или его руководителя после указанной даты.