ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2011, № 1, с. 54-69
РАСПОЗНАВАНИЕ ОБРАЗОВ ^^^^^^^^^^^^ И ОБРАБОТКА ИЗОБРАЖЕНИЙ
УДК 519.722
АКСИОМАТИЧЕСКИЙ ПОДХОД К ИЗМЕРЕНИЮ ИНФОРМАТИВНОСТИ ЗНАКОВЫХ ПРЕДСТАВЛЕНИЙ ИЗОБРАЖЕНИЙ* © 2011 г. А. Г. Броневич, А. В. Гончаров
Таганрог, Технологический ин-т Южного федерального ун-та Поступила в редакцию 10.11.09 г., после доработки 04.05.10 г.
Вводится знаковое представление изображений и исследуются его основные свойства. В частности, обсуждается задача измерения информативности знаковых представлений. Для этого строятся аксиоматические меры информативности изображений и их знаковых представлений. Показано, что данные меры очень близки по свойствам к энтропии Шеннона. Статья также содержит результаты расчета значений введенных мер информативности для модельных и реальных изображений.
Введение. Многие задачи распознавания образов эффективно решаются с помощью алгоритмов, основанных на знаковом представлении изображений. В [1] знаковые представления изображений рассматривались для задачи детекции лиц, которая заключается в поиске участков изображения, содержащих лица и не включающих в себя элементы фона. Детекция лиц является важным предварительным этапом для распознавания лиц, их идентификации, определения пола и возраста, распознавание эмоций и др. В работах [1, 2] данный подход использовался для идентификации лиц, когда по лицу-запросу осуществляется поиск наиболее похожих лиц, содержащихся в базе изображений. Применение знакового представления изображений в моделях активных контуров [2] позволяет эффективно с вычислительной точки зрения решать задачу локализации антропометрических признаков лица, таких, как контуры бровей, координаты уголков глаз и центров зрачков, контуры носа и губ, овал лица. Знаковое представление изображений хорошо зарекомендовало себя и при поиске нечетких дубликатов в больших коллекциях изображений [3]. Данная задача актуальна, например, для поисковых систем [4, 5], поскольку одним из критериев "качества" информационного поиска является разнообразие результатов запроса. Кроме того, обнаружение нечетких дубликатов представляет большой интерес при борьбе со спамом [6], распространяемым в виде графических файлов. Идея перехода от исходного представления сигнала или изображения к знакам некоторого функционала достаточно широко используется как в распознавании образов, так и в анализе случайных процессов.
Один из аналогов знакового представления — описание формы объекта с помощью цепного кода, предложенного впервые Фрименом (H. Freeman) [7]. Цепной код — это способ задания контура с помощью
последовательности смежных пикселей, т.е. (x,)^, где двумерные векторы x, имеют целочисленные координаты, причем если ДХ- = x,+1 - Xi = (l, m), где i е {1,..., N -1}, то l, m е {-1,0,1}. Поэтому в цепном коде положение следующего пикселя относительно предыдущего кодируется парой чисел (l, m) или, что эквивалентно, их знаками. Таким образом, цепной код можно рассматривать в качестве одного из примеров знакового представления информации.
Наиболее близким аналогом знакового представления является хорошо известный морфологический подход, предложенный Ю.П. Пытьевым [8]. В основе морфологии Пытьева лежит идея разбиения изображения на участки, соответствующие постоянной яркости изображения, при этом само изображение представляется в виде взвешенной суммы ортогональных характеристических функций, которые отличны от нуля лишь на подмножествах, соответствующих областям постоянных значений яркости. Множество изображений, которые могут быть получены из исходного изображения действием некоторой функции на значения яркости, называется "формой" изображения [9, 10]. В предлагаемом подходе рассматривается полное и оконное знаковые представления. Множество изображений, отвечающих полному знаковому представлению, совпадает с понятием формы по Пытьеву в классе строго возрастающих преобразований яркости. Однако множество изображений, получаемых на основе оконного знакового представления, шире, чем форма изображений по Пытьеву.
Несмотря на широкий спектр задач, решаемых при помощи знакового представления изображений, системного изучения его свойств до настоящего времени не проводилось, при этом наибольший
1 Работа выполнена при финансовой поддержке РФФИ (проекты № 08-07-00135; 10-07-00478).
3 -
2 -
1 -
0 -
Рис. 1. Пример оконного знакового представления (1.2), когда окрестность каждого пикселя состоит из непосредственно примыкающих пикселей
интерес вызывает вопрос о мере информативности такого представления изображений. Меры информативности специального вида использовались в методах обработки изображений в [11—13]. В рамках данной работы предлагается аксиоматический подход к введению мер информативности на изображениях и соответствующих им знаковых представлениях, а также мера неопределенности знакового представления, описывающая количественно потери информации при переходе от изображения к его знаковому представлению.
1. Знаковое представление изображений. Под изображением будем понимать неотрицательную целочисленную функцию f = f (x1,x2), заданную в точках целочисленной сетки Q = INх IM = {1, ..., N х х {1, ..., M}, т.е. f Q ^ Z+. Пару чисел x = (х1, x2), x1 е IN ,x2 е IM, будем именовать пикселем, а f (x) — значением яркости изображения f в пикселе x. Множество всех изображений f : Q ^ Z+ обозначим через 9.
Определение 1. Отношение xcfixQназовем знаковым представлением изображенияfе 9, если выполняются следующие условия.
1) если (x t, x j) ex, то f(x t) < f(x j);
2) если (x t, x j) ет, а (x j, x t) £ т, то f (x ) < f (x j).
В качестве примеров рассмотрим некоторые способы введения знакового представления на изображениях. Под полным знаковым представлением будем понимать такое, которое обладает свойством связности, т.е. содержит все пары точек изображения f
тс = {(x, y)eQ2f (x)< f (y)}. (1.1)
Отметим, что полное знаковое представление изображения f однозначно определяется условием связности отношения. Введем также оконное знаковое представление — компактный вариант знакового представления, когда учитываются лишь отношения на смежных пикселях
хЕ = {(x, y) eQ2f (x) < f (y),y 6 OE (x)}, (1.2)
где OE (x) — окрестность точки x, например
OE (x) = {y eO||| x - y ||<s), (1.3)
где | | x - y|| = |xi - j'li+ix2 - J2I.
На рис. 1 преведен пример оконного знакового представления. Отметим, что для прикладных задач именно оконное знаковое представление (1.2) с окрестностью (1.3) представляет наибольший интерес, поэтому далее будем рассматривать знаковые представления, заданные отношениями на смежных пикселях.
Класс изображений, соответствующих знаковому представлению т, пометим как 9 т. Пусть т — это некоторое знаковое представление изображения f е 9 и тТг — транзитивное замыкание отношения т.
: 'т. ■-- 1
jl t J
ч ■
J_I_I_I_L_
0 12 3 4
Тогда, очевидно, тТг является также знаковым представлением/ причем 9 т> = 9т. С учетом этого при анализе знаковых представлений изображений можно ограничиться рефлексивными и транзитивными отношениями (т.е. отношениями квазипорядка), множество которых обозначим через
Множество изображений 9 т является аналогом понятия формы в морфологии Пытьева. Предположим, что Ф — это семейство отображений ф: Ж+ ^ Ж+, моделирующих условия регистрации изображения. Тогда под формой в форфологии Пытьева понимается множество изображений У= {ф о /\ феФ}. Легко видеть, что, если в качестве Ф взять класс всех строго возрастающих отображений, то Ус 9 т. Обратное же включение 9 т с У £ выполняется только для случая полного знакового представления изображения / и в этой ситуации понятия формы по Пытьеву и знакового представления совпадают. Во всех остальных случаях, в частности, для оконных знаковых представлений множество 9 т шире, чем множество У/.
Знаковому представлению т изображения / можно поставить в соответствие ориентированный граф = (О,Ет), множество вершин которого образовано множеством О, а множество дуг Ет совпадает с множеством т, при этом если (х, у) е т, то соответствующая дуга графа направлена от вершины x к вершине у. Интерпретацию знакового представления как графа От удобно применять для изучения свойств знакового представления, а также для его визуализации.
Сформулируем необходимые и достаточные условия того, что произвольное отношение т, заданное на является оконным знаковым представлением некоторого изображения. Для этого будем использовать графовую интерпретацию знакового представления.
Обозначим через Е множество всех дуг (включая петли), которые соединяют смежные пиксели, введем также граф От = Е\ЕТ) (здесь, строго говоря, граф От не является дополнительным к От). Рассмотрим отношение эквивалентности 0 = (т п т-1)Тг, где т-1 — это обратное отношение к т, т.е. т-1 = {(х, у) е ^2\(у, х) е т}, а также связанное с отношением 0 разбиение множества вершин О на фактор-множества . Отметим, что данное разбиение определяется однозначно. Если т — оконное знаковое представление некоторого изображения, то классы эквивалентности будут соответствовать связанным множествам пикселей, имеющих одинаковую яркость. Далее введем следующие графы на множестве
V = {VI,..., vn} всех классов эквивалентности отношения 0: ОТ = (V,ЕТ0) и Ох = (V, Е%), где (уь V,) е Ет0,
_х
если существует такая пара (х,у) е Ет, что х е V- и у е V.; аналогично, (V,-, V) е Ет, если имеется пара
9 9
(х, у) е Е\ЕТ такая, что х е V и у е V.. Таким образом, граф От = (V, Ет) представляет собой продолжение графа ОТ = (О, ЕТ) на множество классов эквивалентности V. Отношение смежности пикселей можно также перенести на классы эквивалентности. Считаем, что классы эквивалентности ч1 и V. смежные, если найдутся смежные пиксели х е и у е V.. Если обозначить через Е — множество всех дуг (включая петли) между смежными классами эквивалентности, то О^ = (V, Е\Е). В дальнейшем будем полагать, что функция / также определена на классах эквивалентности, т.е./(V) = /X), если V е V и x е V.
Следующее утверждение дает необходимые и достаточные условия того, что произвольно заданный граф От
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.