Исследование метода Карунена-Лоэва Москва 2006



Скачать 333,24 Kb.
страница1/6
Дата31.10.2016
Размер333,24 Kb.
  1   2   3   4   5   6


РОССИЙСКАЯ АКАДЕМИЯ НАУК

Ордена Ленина

ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ

им. М.В.Келдыша


А.Ю. Солодовщиков, А.К. Платонов

Исследование метода Карунена-Лоэва


Москва 2006

Аннотация

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



Annotation

This paper is dedicated to anylsis of discrete and continuous variations of Karhunen-Loeve transform. Here the problem of formal deducibility Hueckel's operator by Karhunen-Loeve method is solved. Developing a Karhunen-Loeve basis for pixel images in the problem of constructing line detectors, and comparing the taken results with existent ones are made. Numerical and analytical analysis of Karhunen-Loeve basis for the model of Huckel step-edge element are showed. As result comparative characteristics of the solutions and Hueckel basis functions are described.




Работа поддержана грантом РФФИ № 050100885




1.1 Дискретное преобразование Карунена-Лоэва 9

1.2 Непрерывное преобразование Карунена-Лоэва 10

2. Оператор нахождения контуров на растровых изображениях (оператор Хюккеля) 12

2.1Описание оператора 12

2.2Минимизация ошибок окружения на периферии окна 12

2.3Помехоустойчивость оператора 13

2.4Определение оператора 14

3. Ступенчатая модель границы 16

разделения зон контрастности 16

3.1Формирование вектора признаков 17

4. Исследование базиса Карунена-Лоэва для ступенчатой границы скачка яркости 19

4.1Описание рассматриваемых случаев 19

4.1.1Фиксированный угол 20

4.1.2Фиксированное смещение 21

4.1.3Общий случай 22

4.2Аналитический анализ базисных функций 23

4.2.1Фиксированный угол 25

4.2.2Фиксированное смещение 25

4.2.3Общий случай (модель границы Хюккеля) 26

Заключение 30

Использованная литература 31



Введение

Естественные сцены обычно состоят из множества трехмерных объектов. Телевизионные растровые или фотографические изображения являются двумерной проекцией таких сцен и представляют собой области с различными характеристиками яркости отдельных элементов изображения ("пикселов" – от англ. "picture element"). Главным источником информации, извлекаемой из изображения, является положение, величина и взаимозависимость яркостей соседних пикселов. Хотя растровые изображения и удобны для зрительного восприятия полученного изображения человеком, однако для автоматического распознавания содержания сцены более удобны векторные описания изображений. Последние позволяют более ёмко описать сцену, более просто выделить геометрические границы её объектов и, в ряде случаев, описать сцену на более высоком понятийном уровне.

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

Заметим, что замена растрового изображения меньшей по объёму совокупностью отрезков, отображающих лишь локальные направления изменения яркостей, по-прежнему остаётся удобной лишь для зрительного восприятия изображения сцены, но не для программного распознавания её содержания. Для этого требуется либо семантически управлять движением окна в процессе анализа изображения, либо построить процедуру анализа семантики полученного множества отрезков на изображении. Однако в работе Хюккеля содержится важная идея постановки задач работы с изображением: для этого следует найти удобный базис некого интегрального преобразования, адекватного решаемой задаче. Этот подход явился предтечей более позднего метода вейвлет-преобразований, заметно потеснившего в настоящее время двумерные преобразования Фурье.

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

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

Заметим, что Хюккель не описал, как именно он получил свой набор ортогональных двумерных функций с ограниченным носителем в виде единичного круга (см. ниже). Выполненная в работе [2] проверка подтвердила адекватность базиса Хюккеля поставленной им задаче. Однако, представляется крайне желательным иметь формальный метод для построения базиса, адекватного решаемой задаче обработки изображения. Такой метод удалось построить, используя другое, хорошо известное в теории распознавания образов, преобразование Карунена-Лоэва ("КЛ-преобразование").

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

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

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



1. Общее описание метода Карунена-Лоэва

Преобразование Карунена-Лоэва было предложено независимо финским математиком Каруненом (Kari Karhunen) в 1946 и французским математиком Лоэвом (Michel Loève) в 1955. Метод известен под различными названиями, такими как "разложение Карунена-Лоэва", "преобразование Хотеллинга" (дискретный вариант преобразования Карунена-Лоэва), "квазигармонические моды", "собственное ортогональное разложение", "эмпирическое разложение на собственные функции". С формально-математической точки зрения преобразование Карунена-Лоэва представляет собой разложение сигнала X(t) по базису ортогональных функций, каждая из которых является собственной функцией интегрального "характеристического" уравнения с симметричным непрерывным ядром:



и , 0tT, E{an an}=

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

Чаще всего K(t,s) трактуется в виде корреляционной функции R(t,s)=E{x(t) x(s)} в общем случае непериодического и нестационарного случайного процесса с нулевым математическим ожиданием E(X(t)) и существующим вторым моментом E(X(t))2 . В задачах распознавания случайных образов ядро определяется как



K(t,s)=

т.е. – в виде корреляционной функции между классами сигналов, с некоторой вероятностью p(I) принадлежащих одному из M искомых образов (см. [3], с.291-303).

В дискретном случае оно диагонализирует матрицу некоторой заданной квадратичной формы K, т.е. приводит её к виду , где -искомая диагональная матрица, а - матрица собственных векторов искомого преобразования y=x. Метод во многом носит геометрический характер, но в большинстве источников он описывается с точки зрения теории вероятности. В таком описании матрица K является дискретным представлением корреляционной функции R(t,s) в общем случае непериодического случайного процесса наблюдения сигнальных векторов x(t).

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



  • ковариационная матрица K, которая описывает аппроксимацию отсчетов в координатной плоскости изображения (х,у) многомерной гауссовой функцией распределения и

  • соответствующая ей корреляционная матрица R.

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

Пусть собственные значения матрицы K расставлены в убывающем порядке и пронумерованы. Пусть собственные векторы, связанные с ними, расставлены в том же порядке. Тогда матрица собственных векторов обладает тем свойством, что умножение ее на вектор-изображение g дает вектор , имеющий некоррелированные компоненты, причем компоненты вектора G оказываются расставленными в порядке убывания их дисперсий, что является свойством дискретного варианта разложения Карунена – Лоэва.

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

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

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

Еще раз выпишем основные достоинства КЛ-преобразования:



  • концентрация мощности (дисперсии) в минимально возможном числе признаков,

  • минимальная среднеквадратичная погрешность восстановления исходного изображения при заданном числе признаков,

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

Для всего вышесказанного приведем теоретические основы КЛ-преобразования для произвольного случайного вектора в объеме, необходимом для данной работы. В дальнейших главах мы определим, что является вероятностным пространством в случае модели Хюккеля и на растровом изображении.



Поделитесь с Вашими друзьями:
  1   2   3   4   5   6


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница