Интерполяция изображений на основе арифметических операций

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

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

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

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

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

Постановка задачи

Пусть даны два изображения. Известен алгоритм, который позволяет построить семейство переходных изображений (множеств) {},, по схеме

.

Задачи В работе рассматриваются: вопрос о применении вместо множителей (1- t) и t двух непрерывных функций и с соответствующими граничными условиями. Нахождение явного вида этих функций в том случае, когда производится оптимизация по размерам интерполяционных векторов из;

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

введение

новых числовых характеристик изображений для априорной оценки качества интерполяции.

1. Построение интерполяционных объектов

Нам даны два вектора, построим вектор M, конечные точки которого будут находиться на отрезке

Рис. 3

Найдем вектор .

+ = + = +

= (-).

То есть получили следующую формулу для интерполяции векторов:

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

2. Линейные операции над множествами по Минковскому

Пусть нам даны два множества G0 и G1. Тогда линейные операции над ними можно определить следующим образом

1.

2.

Свойства данных операций

1.

2.

3.

4.

Пример 1 — Сложение множеств Рис. 1

Пример 2 — Умножение на число Рис. 2

В итоге для интерполяции множеств применима формула:

(1)

где — исходные множества, — интерполяционное (переходное множество).

Пример 3

Рассмотрим множества — круг радиуса 1 с центром в (0;0), — круг радиуса 3 с центром в (11,5; 8). Тогда интерполяционное множество будет принимать следующий вид:

Рис. 4

Пример 4

Рассмотрим в качестве исходных множеств треугольники. — треугольник с вершинами в (0;0), (2,3), (2,-3), — треугольник с вершинами в (0;0), (-2,3), (-2,-3). Тогда интерполяционное множество при t = будет иметь следующий вид:

Рис. 5

3. Исследование формулы интерполяции

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

Рис. 6

Рассмотрим более общую формулу:

(2)

Где функции — непрерывные на функции и имеют следующие граничные условия:

Исследуем ее сначала для случая векторов из .

интерполяционный операция минковский вектор Рис. 7

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

Для нахождения определим некоторую целевую функцию.

Будем считать дополнительно, что на пространстве объектов определена метрика (например, для векторов — евклидова метрика, для множеств — метрика Хаусдорфа).

При линейной интерполяции имеем:

(3)

где с — расстояние на множестве данных объектов; что можно понимать, как перемещение от одного множества к другому по кратчайшему пути.

Рассмотрим другую постановку задачи. Пусть нужно осуществить переход

. ()

Семейство объектов (назовём оптимальным путем из, если

1. ;

2. для любого выполняется:

где (.) — размер объекта.

Это соответствует перемещению вектора на рисунке 8.

4. Вывод формулы поворота вектора

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

Пусть исходные векторы имеют следующие координаты =(x0,y0) и =(x1,y1)

Координаты переходного вектора обозначим как (x, y). Сначала подставим векторы в схему (1) и распишем операцию умножения на число с помощью матрицы:

Дальше воспользуемся тем, что вектор (x1,y1) можно получить из (x0,y0) умножением последнего на матрицу:

Где, , i = 0, 1, а — угол между соответствующим вектором и осью Ox. Подставим вторую формулу в первую:

=

(*)

Дальше воспользуемся вторым условием из определения оптимального пути. В нашем случае оно примет следующий вид:

Или Теперь вспомним, что вектор (x, y) так же можно получить поворотом и растяжением из вектора (x0,y0):

Где — угол поворота вектора (x, y) от оси Ox.

Прировняв правые части этого уравнения и (*) получим следующую систему:

Найдем :

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

Где, .

Можно отметить, что в случае сонаправленнных векторов (=0) функции сводятся к функциям в первоначальной формуле ().

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

Рис. 9

5. Числовые характеристики изображений

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

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

Рассмотрим общее определение момента инерции. Пусть у нас имеется система материальных точек.

(4)

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

Определение.

Моментом инерции системы (4) относительно некоторой точки S называется следующая величина (по Эйлеру):

Пример 5

Пусть ABCD — квадрат со стороной 2a, в каждой вершине которого помещена масса 1. Через S обозначим середину стороны AB, а через Z — центр квадрата. Вычислим моменты инерции

Рис. 10

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

Теорема.

Пусть Z — центр масс системы (1), тогда для произвольной точки S справедлива формула

(5)

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

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

Таким образом, итоговая формула для момента инерции дискретного множества из N точек имеет следующий вид:

где

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

(, если

гдеплощадь изображения).

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

Наиболее важными для нас будут являться моменты первого и второго порядка. Моменты первого порядка для величин входящих в рассматриваемую систему будут их математические ожидания.

Пусть одномерная случайная величина принимает некоторые значения тогда математическое ожидание этой величины:

где вероятность того, что принимает значение .

(Понятие математического ожидания соответствует понятию центра масс в механике) Свойства математического ожидания

1.

2.

3. Если 0, то 0. При этом = 0 0

4. Если, то

5.

6.

7.

Для двумерной случайной величины = () математическое ожидание:

где =, = .

Центральные моменты второго порядка представляют собой дисперсии случайных величин входящих в систему.

Определение.

Дисперсия — это математическое ожидание квадрата отклонения случайной величины от своего математического ожидания. Дисперсия показывает средний разброс значений случайной величины относительно математического ожидания:

т. е. .

Свойства дисперсии:

1.

2. c

3.

4. = 2

5. = |c|

8.

где о и з независимые случайные величины.

Так же полезным является рассмотрение второго смешанного момента (ковариации).

Определение.

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

= =

где .

Свойства ковариации

1. =

2.

3. 1.

2.

4., где с и d константы.

5.

6. независимы

Для оценки степени этого влияния используют коэффициент корреляции случайных величин:

Свойства коэффициента корреляции:

1. =

2.

3.

4., при этом (величины линейно зависимы)

5. Если независимые случайные величины, то Если случайные величины 1 и 2 независимы, ковариация и коэффициент корреляции равны нулю. В общем случае равенство нулю этих характеристик является необходимым, но не достаточным условием независимости случайных величин.

Если имеется система, состоящая из 2 случайных величин, можно ввести ковариационную матрицу:

.

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

Для начала отметим, что если мы интерполируем по формуле (1) подобные изображения, то выполняется условие оптимальности для размеров множеств.

Пример 6

В качестве исходных множеств рассмотрим квадраты.

Рис. 11

.

Теперь рассмотрим пример, на котором формула (2) перестает работать.

Пример 7

Рассмотрим два перпендикулярных прямоугольника Рис. 12

видно, что

В данном случае, как и в случае векторов, оптимальным переходным множеством являлось бы следующее:

Рис. 13

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

Рис. 14

Рис. 15

Тут следует пояснить, что мы понимаем под схожестью в данном контексте. На множестве всех непустых компактных подмножеств метрического пространства можно рассмотреть метрику Хаусдорфа.

Определение.

Пусть X и Y суть два непустых компактных подмножества метрического пространства M. Тогда расстояние по Хаусдорфу определяется следующей формулой Пример 8

Рис. 16

Воспользуемся данной формулой в нашем случае и будем искать угол, при котором расстояние по Хаусдорфу между совмещенными множествами будет минимально. (Рисунки 14 и 15 — тут).

Далее идея следующая — переходное множество будет строиться по следующему правилу — поворачиваем одно из множеств на полученный угол, интерполируем их по формуле (1) и поворачиваем полученное множество на угол, полученный по формуле:

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

Рис. 17

Опишем алгоритм по шагам.

Имеем на входе — два дискретных изображения, в виде набора точек (N и M точек соответственно).

1) Находим при помощи формул Где — координата Xi-ой точки множества (аналогично для)

2) Совмещаем множество с множеством (получаем в итоге множество)

3) Применяя матрицу поворота к точкам множества, находим угол, при котором расстояние между и минимально. Шаг поворота является входным параметром алгоритма.

где — множество с примененной матрицей поворота на угол относительно точки ().

4) Теперь сам процесс интерполяции — применяем матрицу поворота на угол ко всем точкам множества. Строим интерполяционное множество по формуле (1) между полученным множеством и. И потом при помощи матрицы поворота поворачиваем переходное множество на угол .

(

(

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

Пример 9

Рис. 18

Пример 10

Рис. 19

7. Исследование исходных множеств

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

Построим следующие вектора для исходных множеств.

= для

= для

В случае если первый вектор пропорционален второму, делаем вывод, что применения формулы (1) уже достаточно для проведения успешной интерполяции.

(7)

Однако на практике точного равенства добиться невозможно, поэтому рассматривается следующее условие Пример 11

Рассмотрим два дискретных множества Рис. 20

В итоге получаем Однако даже в случае выполнения условия (7) возможна следующая ситуация:

Рис. 21

В данном случае необходимо рассмотреть так же и ковариацию. А точнее — ее знак. Отличие в знаке покажет нам, что исходные изображения повернуты на и в данном случае необходимо применить поворот.

Применение указанных характеристик и условия (7) недостаточно для разделения оставшихся (и довольно многочисленных) случаев. Поэтому, для дальнейшего анализа, предлагается ввести производные характеристики.

Рассмотрим некоторые их свойства аналогично и для

Фактически, коэффициент показывает отличие множества от отрезка перпендикулярного. Соответственно отличие от отрезка перпендикулярного .

Эти две характеристики представляют большой интерес для исследования, так как являются довольно универсальными, то есть описывают больше природу множества, его общие свойства, не связанные с растяжением и переносом. (Инвариантность к растяжению и переносу можно пронаблюдать на рисунке 20)

При поверхностном взгляде на эти характеристики можно сделать вывод про исходные множества:

Если = и =, то исходные изображения повернуты на 90 градусов.

Особый интерес для рассмотрения представляет сумма этих коэффициентов. Рассмотрим следующую функцию:

где — угол поворота исходного множества G относительно его центра масс.

В ходе ее численного исследования были сделаны следующие выводы:

1)

2), причем это значение достигается, когда Например, при для круга.

3) свой для каждого изображения.

Заключение

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

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

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

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

1. Цифровая обработка телевизионных и компьютерных изображений / Под ред. Ю. Б. Зубарева, В. П. Дворковича. — M., 1997. — 216 с.

2. Балк М. Б., Болтянский В. Г. Геометрия масс М.: Наука 1987

3. Браверман Э. М. Опыты по обучению машины распознаванию образов. // АиТ. 1962. — № 3. — Стр. 221−228

4. Глушков В. М.

Введение

в кибернетику. — Киев: Изд-во АН УССР, 1964.

5. Грюнбаум Б. Этюды по комбинаторной геометрии и теории выпуклых тел. М.: Наука 1971