Способ интерполяции изображений

Способ интерполяции изображений

Иллюстрации

Показать все

Реферат

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

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

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

Обычно двумерная интерполяция производится как серия одномерных интерполяций во взаимно перпендикулярных направлениях. Например, изобретение, описанное в патенте США №6915026 [1], предполагает увеличение изображения в два этапа: сначала в вертикальном направлении, затем в горизонтальном, предварительно рассчитывая и сохраняя коэффициенты для интерполяции. Этот метод имеет такой недостаток, что все одномерные интерполяции производятся параллельно координатным осям изображения, и проявляющиеся артефакты обнаруживают лежащую в основе координатную решетку. Некоторые методы предполагают предварительную низкочастотную фильтрацию в диагональных направлениях, но это, к сожалению, ухудшает качество самого изображения. Патенты США №5719967 [2] и 6606093 [3] описывают специальные приемы для подавления зубчатости краев в изображении.

Решение, описанное в патенте США №5446804 [4], использует предварительно рассчитанную субпиксельную карту краев. Для каждого интерполируемого пикселя находятся четыре ближайших соседа. Если ни один из соседних пикселей не отсекается краем от остальных, искомое значение вычисляется как сумма этих соседей с весами. Если же соседи лежат по разные стороны от края, для искомого пикселя вычисляется промежуточное значение с использованием двух диагональных пикселей, лежащих по одну сторону края, выбор которых осуществляется на основе карты краев. Затем искомое значение в позиции, лежащей по другую сторону границы, заменяется на значение, полученное с помощью соседей, лежащих по одну сторону края, и вычисленной величины. Такое решение позволяет получить изображение с резкими границами, но содержащее зубчатые края.

Обычно увеличение изображения производится в два этапа. Сначала вычисляются неизвестные значения яркости, затем для увеличения резкости изображения и улучшения краев производится постобработка изображения. Например, патент США №6714688 [5] описывает метод постобработки изображения для увеличения резкости. Сначала производится билинейная интерполяция изображения, затем производится постобработка краев с помощью движущегося окна. Размер окна определяется исходя из степени увеличения. Сначала к пикселям внутри окна применяется низкочастотный фильтр для выделения высокочастотной составляющей изображения. Высокочастотная составляющая затем суммируется с низкочастотной с некоторым коэффициентом, определяемым на основе локальных яркостных характеристик. Затем края дополнительно обрабатываются с помощью специальной кривой преобразования яркости.

Метод, описанный в опубликованной заявке на Европейский патент №1533899 [6], направлен также на изменение размеров цифрового изображения посредством следующих этапов: интерполяции вдоль границ и дополнительной постобработки. Сначала изображение увеличивается в 2ⁿ раз, затем уменьшается до нужных размеров. Затем производится постобработка краев. Данный метод обеспечивает хорошие результаты, но является достаточно сложным с вычислительной точки зрения.

Наиболее близким к заявляемому изобретению является решение, предложенное в патенте США №6928196 [7], которое описывает метод интерполяции вдоль краев. Сначала конструируется карта краев, на основе интенсивности и направления края, используя значения элементов изображения. Затем к карте краев применяют морфологические операции, эрозии и дилатации. Затем карта краев квантуется на четыре направления: горизонтальное (0), диагональное (π/4), вертикальное (π/2) и параллельное побочной диагонали (3π/4). Ядро интерполяции выбирается на основе интенсивности и направления края. В способе-прототипе, однако, используются всего четыре направления краев, а морфологические операции производятся над вещественными числами.

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

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

Некоторые из разработанных методов увеличения изображений направлены на увеличение, кратное двум, так как требуют сетки фиксированной структуры.

Видимые дефекты изображения, типичные для JPEG сжатых изображений или MPEG видеопоследовательностей, в результате увеличения изображений и последующей обработки краев становятся еще более явными.

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

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

- осуществляют предварительную обработку изображения с целью удаления артефактов сжатия с потерями, если такие артефакты имеются;

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

- выполняют морфологические операции над картой направлений краев;

- вычисляют множество координат, в которых необходимо рассчитать значения яркости;

- для каждой пары вычисленных координат выполняют одномерную интерполяцию в направлении, определяемом значением соответствующего элемента в карте направлений краев;

- повторяют предыдущий шаг для каждой цветовой компоненты;

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

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

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

Для случая увеличения изображения также предлагается предварительно обрабатывать изображение, чтобы удалить артефакты, связанные со сжатием с потерями, например блок-артефакты, проявляющиеся при JPEG-кодировании.

Далее существо заявляемого изобретения поясняется с привлечением графических материалов.

Фиг.1 - схема базовых компонентов системы.

Фиг.2 - блок-схема этапов процесса построения карты направлений краев.

Фиг.3 - блок-схема этапов процесса обработки карты направлений краев.

Фиг.4 - блок-схема этапов процесса интерполяции изображения.

Фиг.5 - интерполяционная схема в случае, когда значения карты направлений краев принимают значения от одного до четырех, как отмечено на шаге 406.

Фиг.6 - интерполяционная схема в случае, когда значения карты направлений краев принимают значения от пяти до восьми, как отмечено на шаге 406.

Фиг.7 - блок-диаграмма этапов постобработки.

Фиг.8 - примеры кривых преобразования яркости для разных значений контролирующего параметра n.

Фиг.9 - примеры реализации заявляемого способа.

Фиг.1 показывает основные компоненты системы, на которой данный способ может быть реализован. Реализация способа управляется процессором 101, который выполняет программный код, хранящийся в памяти 102. Также в памяти 102 хранится исходная черно-белая или цветная фотография. Изображение анализируется, создается новое изображение, пиксели которого вычисляются с помощью пикселей исходного изображения. Новое изображение передают на устройство 104 отображения или на устройство 103 печати. Передачу информации в системе осуществляют по шине 106 данных.

Далее описывается процесс создания интерполированного изображения.

На Фиг.2 приведена блок-схема этапов реализации способа. Пусть I - исходное изображение, размер которого больше, чем четыре на четыре пикселя. Для каждой точки исходного изображения производится следующая процедура. Выделяются шестнадцать ближайших соседей обрабатываемой точки 202. Затем вычисляются абсолютные значения производных в четырех направлениях, в соответствии с нижеприведенным правилом 203. Пусть четыре ближайших соседа А будут I(i,j), I(i+1,j), I(i,j+1) и I(i+1,j+1). Тогда,

где I_x, I_y, I_d1, I_d2, I_xxy, I_yxx, I_xyy, I_yyx являются абсолютными значениями производных по восьми направлениям. На шаге 204 выбирается минимальное значение среди этих восьми производных по направлению. Индекс минимальной по направлению производной заносится в массив - карту направлений краев, шаг 205. Индекс для величин [I_x, I_y, I_d1, I_d2, I_xxy, I_yxx, I_xyy, I_уух] выбирается как [1, 2, 3, 4, 5, 6, 7, 8] соответственно.

Фиг.3 иллюстрирует процесс обработки карты направлений краев. Сначала к карте направлений краев применяется операция удаления резких вариаций: для этого используется окно «3×3» элемента, выделяют восемь ближайших соседей, шаг 301. Если внутри окна существуют, по крайней мере, три разных значения карты направлений краев со значениями, большими или равными пяти, значение карты направлений краев в центральной части окна заменяют по следующему правилу: пять и шесть заменяют на один; семь и восемь заменяют на два, шаг 302. Когда достигается последний элемент карты направлений краев, шаг 303, процесс обработки карты направлений краев переходит к следующему этапу. На последующих шагах, 304-307, небольшие изолированные края, т.е. края с индексами в карте направлений краев, большими или равными пяти, которые могут быть проявлениями шума в изображении, удаляются с помощью морфологических операций эрозии, с последующей дилатацией. Морфологическая операция эрозии помечает центральный пиксель как ненулевой, если все ненулевые элементы структурного элемента совпадают с ненулевыми элементами обрабатываемого массива, т.е. изображения. Морфологическая операция эрозии помечает центральный пиксель как ненулевой, если, по крайней мере, один ненулевой элемент структурного элемента совпадает с ненулевыми элементами обрабатываемого массива, т.е. изображения. Структурный элемент выбирается в зависимости от обрабатываемого значения карты направлений краев следующим образом:

Значение карты направлений краев	Структурный элемент	Значение карты направлений краев	Структурный элемент
	1	1	0		1	0
5	0	1	1	7	1	1
					0	1
	0	1	1		0	1
6	1	1	0	8	1	1
					1	0

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

Далее производится интерполяция, на основе карты направлений краев.

Фиг.4 иллюстрирует интерполяционную процедуру. Сначала строится множество точек, в которых необходимо вычислить значения яркости, 400. Для каждой точки А построенного множества производится следующая процедура. Определяются координаты А, шаг 401. Затем находятся координаты шестнадцати ближайших соседей, принадлежащих исходному изображению, шаг 402, и соответствующее направление края считывается из карты направлений краев, шаг 403. Интерполяция производится в соответствии со считанным значением из карты направлений краев. Этот процесс, шаг 404, будет далее описан подробней. Как только считано последнее значение из множества точек, в которых необходимо вычислить значения яркости, условие 405 удовлетворяется. Описанная процедура, а именно шаги 402-409, производится для каждой цветовой компоненты, в пространстве RGB или YCrCb. После того, как условие 406 выполнено, изображение поступает на устройство вывода, например принтер, дисплей или аналогичное устройство, или сохраняется в память.

Фиг.5 и Фиг.6 подробно иллюстрируют метод интерполяции, упомянутый на шаге 404. В левой колонке таблицы указано значение карты направления краев, в соседней правой приведена соответствующая иллюстрация для интерполяции значений яркости изображения. Пусть требуется найти яркость в точке А (помеченной крестиком) сконструированного множества координат, окруженной шестнадцатью ближайшими соседями. Точки Р₁ и Р₂ находятся такие образом, что линия Р₁Р₂ проходит через точку А и ее наклон равен 45°, -45°, 26.5°, -26.5°, 116.5° или -63.5°. Значения яркости в точках P₁ и Р₂ находятся с помощью одномерной линейной интерполяции, используя два значения по вертикали для точки Р₁ и два значения по горизонтали для точки P₂ (соответствующее ребро координатной решетки отмечено жирным). Для того чтобы найти значения яркости в точке А, используется линейная интерполяция между точками Р₁ и Р₂. Заметим, что методы одномерной интерполяции здесь не ограничиваются линейной или кубической интерполяцией, могут использовать разные интерполяционные функции и большее количество точек сетки для расчета яркости в точках Р₁, Р₂ и А.

Последующая постобработка производится, если необходимо подчеркнуть края и увеличить резкость.

Фиг.7 иллюстрирует основные шаги для подчеркивания краев. Сначала на шаге 700 определяется толщина краев, в вертикальном и горизонтальном направлениях, Kν и Kh соответственно, как округленные значения степени увеличения изображения по вертикали и горизонтали. Затем рассчитывается таблица преобразований (look-up-table - англ.) кривой преобразования яркости для усиления локального контраста, шаг 701. Кривая преобразования яркости отображает сегмент [0,1] в себя, и ее производная в точке 0,5 должна быть больше единицы. Результирующая резкость краев зависит от формы кривой, особенно от величины производной в точке 0,5: чем больше производная, тем резче получаются в результате края. Функция для кривой преобразования яркости выбирается следующая:

где производная в точке х=0.5 контролируется параметром n (на Фиг.8 приведены варианты кривой преобразования яркости для различных значений n). Далее над каждым пикселем исходного изображения производится следующая процедура. Сначала определяется цветовой канал с₁, в котором значение яркости является максимальным из трех, в цветовом пространстве RGB или YCrCb, шаг 703. Далее, на шагах 704-708, обрабатываются значения яркости в данном канале. В некоторой окрестности находятся минимальное и максимальное значения яркости, входной пиксель масштабируется на сегмент [0, 1], шаг 705:

С помощью кривой преобразования яркостей на шаге 706 находится значение d и затем оно масштабируется обратно на сегмент [local_minimum, local_maximum]:

d=local_minimum+f(I^scaled)(local_maximum-local_minimum).

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

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

Фиг.9 иллюстрирует четырехкратное увеличение фрагмента изображения двумя способами: бикубическим и заявляемым способом, где 9.1 - исходные изображения, 9.2 - фрагмент изображения, увеличенного в четыре раза с помощью предложенного метода, 9.3 - фрагмент изображения, увеличенного в четыре раза с помощью бикубической интерполяции.

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

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

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

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

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

выполняют морфологические операции над картой направлений краев;

вычисляют множество координат, в которых необходимо рассчитать значения яркости;

для каждой пары вычисленных координат выполняют одномерную интерполяцию в направлении, определяемом значением соответствующего элемента в карте направлений краев;

повторяют предыдущий шаг для каждой цветовой компоненты;

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

2. Способ по п.1, отличающийся тем, что процедуру интерполяции производят для аффинного преобразования изображения.

3. Способ по п.1, отличающийся тем, что процедуру интерполяции производят для поворота изображения.

4. Способ по п.1, отличающийся тем, что карту направлений краев подвергают морфологической операции эрозии с последующей дилатацией.

5. Способ по п.1, отличающийся тем, что расчет яркости для каждого элемента формируемого изображения выполняют в зависимости от соответствующего значения в карте направлений краев.

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

7. Способ по п.1, отличающийся тем, что увеличение изображения в R раз осуществляют пошагово, с предварительным построением n промежуточных изображений, где k-е изображение (k=l...n) является предыдущим, увеличенным в T_k раз, так что T_k<R и T₁*...*T_n=R.

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

9. Способ по п.8, отличающийся тем, что кривая преобразования яркостей имеет следующий вид: