ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 4, с. 122-128
РАСПОЗНАВАНИЕ ОБРАЗОВ И ОБРАБОТКА ИЗОБРАЖЕНИЙ
УДК 517.9-004.92
ИССЛЕДОВАНИЕ МЕТОДА КАРУНЕНА-ЛОЭВА*
© 2007 г. А. Ю. Солодовщиков
Москва, ИПМ им. Келдыша РАН Поступила в редакцию 19.12.06 г.
Работа посвящена исследованию дискретного и непрерывного вариантов преобразования Каруне-на-Лоэва. На основе этого преобразования представлен алгоритм аналитического построения базиса с некоррелированными коэффициентами разложения для анализа растрового изображения. Дано сравнение полученных результатов с существующими в задаче выделения элементов контура. В качестве примера решается задача формального построения этим методом операторов типа оператора Хюккеля. Выполнено сопоставление характеристик сформированных базисных функций.
Введение. Естественные сцены обычно состоят из множества трехмерных объектов. Телевизионные растровые или фотографические изображения являются двумерной проекцией таких сцен и представляют собой области с различными характеристиками яркости отдельных элементов изображения ("пикселов" - от англ. "picture element"). Для получения векторного описания исходного растрового изображения трехмерных сцен хорошо применим предложенный М. Хюккелем оператор, позволяющий преобразовать растровое изображения во множество линейных отрезков фиксированной длины [1]. В своей работе Хюккель решал более частную задачу отображения растровой картины яркости в круглом окне фиксированного радиуса в уравнение прямой, аппроксимирующей позицию и направление линии максимумов градиентов яркости в точках окна. С этой целью он предложил совокупность гладких базисных функций и их дискретное представление для двумерного разложения изображения внутри окна. Подробное исследование этих функций показало, что они удовлетворяют критерию минимума ошибки между элементами исходного изображения и наиболее вероятным положением линии градиентов яркости. В [1] содержится важная идея постановки задач для работы с изображением: следует найти удобный базис некого интегрального преобразования, адекватного решаемой задаче. Этот подход явился предтечей более позднего метода вейвлет-преобразований, заметно потеснившего в настоящее время двумерные преобразования Фурье.
Действительно, для получения лаконичного описания содержания сцены следует выделить из ее изображения только "нужные" (зависящие от искомого содержания) элементы пространственных взаимосвязей пиксельных яркостей, исключив "ненужную" (избыточную) и восполнив уте-
* Работа выполнена при финансовой поддержке РФФИ (грант < 05-01-00885).
рянную (в результате наличия шумов фотоприемника) информацию. Здесь возникает задача построения такого способа описания изображения, в котором элементы описания слабо зависимы. Одним из наиболее перспективных методов решения этой, очень непростой проблемы является поиск двумерного ортогонального базиса для интегрального преобразования растрового изображения, адекватного задаче распознавания сцены, и такого (что важно), который обеспечивает сосредоточение искомой информации в минимальном числе коэффициентов разложения. Эти "старшие гармоники" спектра разложения несут, как правило, искомую информацию об интегральных перепадах яркости, в то время как высокочастотные составляющие спектра отражают лишь избыточную информацию, например, в задаче поиска контуров областей изображения.
1. Постановка задачи. Выполненная проверка подтвердила адекватность базиса Хюккеля поставленной им задаче. Однако представляется крайне желательным иметь формальный метод для построения базиса, адекватного решаемой задаче обработки изображения. Такой метод удалось получить, применив другое хорошо известное в теории распознавания образов преобразование Карунена-Лоэва (КЛ-преобразование). В отличие от ряда работ, развивающих подобный подход, рассмотрение метода не ограничено дискретным вариантом преобразования [2]. Использование непрерывного КЛ-преобразования позволяет аналитически описать структуру базиса, что также удобно при масштабном анализе.
В литературе КЛ-преобразование описывается в рамках вероятностной модели сигнала. Но, безусловно, метод Карунена-Лоэва носит более общий характер, он применим для совокупности не обязательно случайных элементов изображения, для которых существует знание аналога корреляционной функции их яркости. КЛ-преобразование обладает рядом свойств, выделяющих его среди
ИССЛЕДОВАНИЕ МЕТОДА КАРУНЕНА-ЛОЭВА
123
остальных линейных преобразований. Оно дает лучший результат в некотором смысле, определенном ниже. Главным недостатком КЛ-преобра-зования остается отсутствие быстрых алгоритмов вычисления. Полученный в работе метод описывается на примерах построения операторов преобразования изображений, схожих с оператором Хюккеля. Приводится формальный вывод базиса для оператора Хюккеля и анализ значимости его гармоник.
2. Общее описание метода Карунена-Лоэва. С
формально-математической точки зрения КЛ-преобразование представляет собой разложение сигнала Х(Г> по базису ортогональных функций, каждая из которых является собственной функцией интегрального "характеристического" уравнения с симметричным непрерывным ядром (здесь и далее М( ) - математическое ожидание)
|К(5)ф;(5)Ж = Х}-ф;(t)
и Х( t) = £ АаПФП(0,
0 < t < Т,
М(а„, ат) =
1, п = т, 0, п Ф т.
Основная идея заключается именно в существовании и использовании некого ядра, связанного со свойствами сигнала Х(0. При заданном виде ядра приведенное интегральное уравнение определяет ортогональный базис разложения по его собственным функциям, что упрощает разложение и минимизирует [3] квадрат ошибки. Чаще всего ъ) трактуется в виде функции ковариации ъ) = = М(х(0х(у)) - М(х(ъ))М(х(0). В задачах распознавания случайных образов ядро определяется как
Ь
К( t, 5 ) = £ р(щ) К { X (t) х,( 5 )},
1 = 1
т.е. в виде ковариационной функции между классами сигналов с некоторой вероятностью р(ю7), принадлежащих одному из Ь искомых образов [4-6].
В дискретном случае оно диагонализирует матрицу некоторой заданной квадратичной формы К, т.е. приводит ее к виду К = Ф2ФТ, где 2 - искомая диагональная матрица, а Ф - матрица собственных векторов искомого преобразования У = ФТХ. Исследуем КЛ-преобразование применительно к растровым изображениям. Такое изображение всегда содержит избыточную информацию как следствие содержательного и шумового взаимовлияния его соседних элементов. В связи с этим рассматриваются:
ковариационная матрица К, которая описывает аппроксимацию отсчетов в координатной плоско-
сти изображения (х, у) многомерной гауссовой функцией распределения;
соответствующая ей корреляционная матрица Я.
Важным методом многомерного статистического анализа служит исследование массива данных не только в их естественных координатах, но и в системах координат с более удобными свойствами. В частности, весьма полезными оказались системы координат, основанные на собственных значениях и собственных векторах ковариационной матрицы К. Преобразование координат, определяемое матрицей собственных векторов Ф матрицы квадратичной формы, рассматриваемой в качестве линейного оператора исходного пространства, обладает тем свойством, что оно производит перевод заданного массива чисел в другой с некоррелированными элементами, причем получающиеся компоненты имеют убывающие дисперсии. Полезность КЛ-преоб-разования для сокращения избыточности изображений очевидна. Массив отсчетов изображения заменяется набором переменных, имеющих различные статистические веса. Отбрасывая переменные с малым статистическим весом и сохраняя остальные, можно достигнуть многократного сжатия изображения. В процессе исключения переменных возникает среднеквадратичное отклонение от оригинала. Особенность КЛ-преобразования состоит в том, что из всех линейных преобразований именно оно обеспечивает минимальную величину такого отклонения.
3. Оператор нахождения контуров на растровых изображениях (оператор Хюккеля). В [1] был
предложен метод автоматического выделения отрезков на растровом изображении, который является результатом формализации требований и вывода соответствующих формул. Имеется пиксельное изображение размера Ж х Н. Пусть В -множество клеток сетки, наилучшим образом аппроксимирующее круглое окно, принадлежащее изображению. Через Ер, р е В, обозначим значение яркости изображения в точке р. Идеальный элемент контура, наилучшим образом аппроксимирующий эмпирический элемент контура Ер, будет описан ниже. Входом оператора является любая функция {Ер|р е В}. На первом этапе вычисляются восемь промежуточных чисел по формуле
а, = £ НрЕр 1 = (0, ..., 7).
р е В
При непрерывной трактовке
Ви = {(х,у)|х2+ у2 < 1}
и Е (х, у) е В и: а, = | Н, (х, у )Е( х, у) йхйу
Ви
(1 = 0, ..., 7).
Т
0
п = 1
124
СОЛОДОВЩИКОВ
На втором этапе осуществляется нелинейное преобразование этих чисел в конечные контурные данные, описанные ниже. Совокупность чисел Нр образует матрицу из констант, которые получаются из аналогичных непрерывных функций Нг(х, у). Данные функции выражаются через набор {Нг-1 I = = 0, ..., 7}, представляющий выборку из конкретного базиса, полученного Хюккелем, в гильбертовом пространстве, образуемым множеством всех непрерывных на окне Би функций.
Функции Нг- определены как функции низких или высоких пространственных частот в зависимости от / < 7 или / > 7. Для вычисления оператора существенны функции низких частот. Потому гильбертово представление сокращено до первых восьми компонент (а0, а1, ..., а7). Тем самым первый шаг действия оператора может рассматриваться как низкочастотный фильтр. Учет высоких частот не нужен вследствие наличия размытости и(или) шумов на изображениях.
3.1. Определение оператора. Пусть Е(х, у) и ^(х, у) - функции, описывающие эмпирический и идеальный элемент контура, Е(х, у) непрерывна и постоянна в пределах каждой клетки растра и произвольна во всех остальных точках, ^(х, у) - непрерывна и постоянна всюду, кроме линии контура сх + sy = р. Для нормализации этого уравнения положим с2 + s2 = 1. Пусть А - меньшая, а А + В - большая из двух яркостей, соответствую
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.