Структурное распознавание изображений на основе моделей голосования признаков характерных точек - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Лабораторная работа Распознавание изображений по углу между векторами... 1 48.46kb.
Автоматический анализ изображений и распознавание образов на основе... 3 458.84kb.
Семинаре «Обработка изображений и распознавание образов» 1 17.89kb.
Лабораторная работа Представление изображений в n-мерном векторном... 1 59.63kb.
1 XI международная конференция «Распознавание образов и анализ изображений... 4 510.41kb.
Архитектурная репрезентация государственной идеи на дальнем востоке 1 52.15kb.
Оксиды, их классификация и химические свойства 1 27.68kb.
Распознавание образов и анализ изображений: новые информационные... 1 154.55kb.
Распознавание образов и анализ изображений: новые информационные... 1 153.82kb.
Психология и соционика межличностных отношений Рубрика 9 1038.8kb.
Ансамбль Казанского кремля 10 929.25kb.
Автоматизация подготовки управляющих программ для станков с чпу на... 1 125.71kb.
Направления изучения представлений о справедливости 1 202.17kb.

Структурное распознавание изображений на основе моделей голосования признаков характерных - страница №1/1



УДК 681.51:007.5
В. А. Гороховатский, Е. П. Путятин

Харьковский национальный университет радиоэлектроники

проспект Ленина, 14, 61166 Харьков, Украина

Структурное распознавание изображений на основе

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

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

Извлечение из изображения осмысленной и структурированной информации представляет собой довольно сложную проблему из-за большого объема излишних данных, которые включает видеосигнал наряду с данными о визуальных объектах. Успех могут принести технологии, основанные на анализе особенностей изображения в отдельных точках [1–5]. На основе анализа свойств конечного числа характерных признаков (ХП) можно решить практические задачи любой сложности [6–9].

Распознавание изображений на основе системы ХП имеет несомненные преимущества в следующих аспектах: упрощение процедур формирования признаков, сокращение признакового пространства, универсальная возможность структурного анализа объектов, устойчивость к влиянию фоновых искажений и ложных объектов. Характерные точки (по-другому ключевые точки, точки интереса, характерные признаки, структурные элементы, примитивы) формируются на основе информации, которая содержится в отдельных «значимых» фрагментах изображения [2–6]. Это небольшие по размеру блоки пикселей с характерным внешним видом. В известных применениях ХП отражают степень изменчивости (кривизну) функции яркости, а также уровень отличия от соседних фрагментов. Это выражается в таких локальных особенностях изображения как углы, перепады, границы, контрастные точки, концы кривых, линий и др. [5–8].
© В. А. Гороховатский, Е. П. Путятин

В пространстве ХП распознавание сводится к построению меры для сравнения конечных множеств. Эффективный способ реализации такой меры — голосование элементов множеств ХП [6]. Идейной основой голосования ХП в компьютерном зрении считается преобразование Хафа [9], а теоретической базой выступают теория множеств, методы вычисления оценок, статистический анализ. Наряду с устойчивостью принятия решения при неполном представлении, методы голосования обладают таким важным достоинством, как простота реализации, что при достаточно высокой надежности делает их конкурентоспособными среди известных подходов.

Цель работы — формализация и анализ моделей распознавания на базе принципов голосования ХП.

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


Представление множества характерных признаков

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

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

Пусть — конечный набор ХП, — множество их координат, а кортеж , — это множество пар вида . Здесь — конечномерный вектор значений ХП, ,, , — размерность вектора признаков. В общем случае совокупности считаем мультимножествами [1], а есть множество с неповторяющимися элементами. Между множествами имеется однозначное соответствие вида . Построение сводится к оптимизационной задаче получения локальных экстремумов, когда фрагменты изображения проходят «испытание», относятся ли они к ХП. Конкретный способ формирования ХП выбирается путем компромисса факторов: подчеркивание свойств объектов, качество и надежность выделения, инвариантность к преобразованиям, объем вычислений, помехоустойчивость, независимость значений и др. Формирование множества включает три основных этапа:

— применение системы локальных фильтров и получение списка точек, где имеется «существенное» для дальнейшего анализа значение фильтра;

— «отсев» элементов списка в целях сокращения времени и других ресурсов;

— вычисление значений для точек списка.

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


Свойства характерных признаков

Номер ХП

Координаты

Значения ХП













Наряду с множеством значений ХП будем рассматривать также множество отношений на , где . Часто отношения записывают в виде предиката , где 1 означает выполнение для набора аргументов. Использование отношений дополняет ресурсы системы распознавания высокоуровневыми признаками. Комбинации признаков в виде отношений заложены в самой природе структурного представления как способ грануляции данных в целях получения новых знаний. Для конкретности используем бинарные отношения .

Имеем три типа отношений: — на множестве , — на множестве , а также комбинированные отношения , заданные на множестве пар элементов признак–координаты. Отношения типа реализуют групповые свойства значений ХП, а отношения типа и учитывают пространственные связи между ХП.

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

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

Введем понятие функции соответствия локального признака классу . Она является ключевым моментом структурного анализа. На основе реализуется отображение признак–класс, устанавливающее степень соответствия ХП классу объекта. Функция , как правило, основывается на сходстве или расстоянии от точки до множества и является основой локального решения , . Для определенности можно считать, что , а с ростом увеличивается схожесть признака с множеством . Область значений функции представим в виде отрезка , где — минимальное, а — максимальное значения. Эту область можно легко преобразовать к отрезку .

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

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


Рис. 1
Рассмотрим вычисление в виде расстояния , в


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

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

Однозначное локальное решение можно представить как
(1)
а многозначное решение выглядит соответственно:
(2)
Решения (1), (2) предполагают, что классы признаков и классы объектов совпадают. Более общая постановка состоит в построении представления двух множеств, когда для ХП строится одно множество классов, которое затем отображается во множество классов объектов. Модель с однотипными классами концентрирует вычисление сходства на интегрировании локальных решений и не требует построения дополнительного отображения из одного множества классов в другое, что усложняет обработку.

Варианты систем признаков и функций соответствия:

1) признаки яркости и корреляционные меры сходства [2, 3];

2) инвариантные признаки и расстояние в пространстве векторов (моментные инварианты, спектры, локальные потоки [8], масштабно-инвариантное преобразование SIFT [7] и другие);

3) статистические признаки и меры сравнения параметров распределений [6, 9] (матожидание, дисперсия, ковариации, автокорреляционная функция фрагмента, гистограмма яркости).
Формальное представление голосования

Представим распознавание как отображение множества на компоненты множества эталонов и реализуем путем решения задачи оптимизации вида


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

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

Имеется несколько возможностей реализации (3). Первая связана с оптимизацией расстояния от ХП до каждого из множеств . Ее можно назвать «независимым голосованием». В результате получаем элемент гистограммы голосов . Другая концепция основана на оптимизации расстояния между множествами и . Здесь имеем иерархию решений. Такая схема может быть названа «совместным голосованием».

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


, (4)
т.к. вероятность любого события есть сумма вероятностей элементарных событий, из которых оно состоит. Знак здесь символизирует приближение к независимости элементарных событий. Правило (3) на основе максимизации вероятности (4) соответствует минимуму среднего риска при равных априорных вероятностях классов и одинаковой стоимости ошибок первого и второго рода [9]. Представим как вероятностную модель
(5)
где — порог, равный или в зависимости от варианта локального решения, отражает вклад ХП в суммарный голос. Соотношение означает, что признак с номером относится к классу и имеет значимую величину соответствия этому классу. Частный случай (5) для однозначного голосования приводит к бинарной вероятностной модели вида:
(6)
Результат голосования определяется решающей коалицией , при условии, что удельная сумма ее голосов (сумма голосов, деленная на мощность ) превышает заданный порог, т.е. , где — порог. При выборе предполагается возможность решения на основе относительно небольшого числа ХП, что не вписывается в рамки традиционных статистических решений и требует обоснования.

На основе определим вероятность отнесения признака классу :


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

Как видим, определяющим фактором при построении голосующих процедур есть функция . Ряд исследований посвящено усовершенствованию или новым принципам построения [4–7]. В работе [8] рассматривается представление вида


, (9)
где вычисляется как сумма значений, соответствующих поддержке «соседей» k-го признака из некоторой области , — вес поддержки i-го соседа, — расстояние между ХП. Выражение вида (9) определяет новый тип расстояния от точки ХП до множества.

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


Построение надежных локальных решений

Наряду с очевидными достоинствами, реализация голосования требует обеспечения надежных локальных решений. Дело в том, что отдельные фрагменты изображений часто бывают схожими между собой. Это вызывает близость ХП разных классов и затрудняет определение максимума [6–8]. Уменьшение влияния указанного фактора путем подбора типов ХП, значения которых различаются для разных эталонов, приводит к необходимости получения отдельных оптимальных фильтров для разных классов. При имеющемся разнообразии изображений это становится неразрешимой проблемой. Более приемлемым есть путь подтверждения голосов ХП. Второй подход — совместное голосование признаков [10]. Оба способа связаны с анализом отношений ХП.

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

Разновидностями поддержки являются: пространственная, амплитудная и комбинированная, что соответствует видам отношений ,,. Например, пространственную окрестность i-го фрагмента составляют соседних фрагментов в виде совокупности (при восьмисвязности ). Множество фрагментов из окрестности фрагмента j-го эталона обозначим . Эквивалентность окрестностей установим на основе предиката


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

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


Практические аспекты и результаты

В плане особенностей реализации моделей голосования отметим следующее.

Исходные данные имеют вид совокупности матриц ХП для эталонов и объекта :
, , .
Матрицы в общем случае имеют разное количество строк, каждая строка состоит из элементов, соответствующих признаку . Отношения устанавливаются между подмножествами строк. Например, бинарные отношения характеризуют пары строк. Распознавание сводится к сопоставлению между собой строк или их отношений и установлению матрицы, наиболее близкой к . Степень соответствия выражается функцией . Параметрами распознавания являются пороги для количества голосующих строк или их комбинаций. Учитывая, что сравнение осуществляется путем перебора, нужно использовать эффективные способы поиска, например, хеш-структуры [6].

Наши эксперименты характеризуют в сравнительном аспекте методы голосования ХП и метод частных корреляций [5, 8], основанный на функции яркости фрагментов. Для формирования ХП использованы детектор Харриса и локальные потоки. В данной серии распознавались полутоновые изображения автомобилей размером на сложном фоне в условиях геометрических преобразований смещения и поворота. В плане устойчивости к аддитивному шуму метод голосования по множеству ХП несколько уступает методу частных корреляций. Амплитудные отношения сигнал–шум, при которых обеспечивается распознавание с вероятностью выше 0,95, составили величины 3 и 6. В то же время устойчивость к локальным помехам типа заслонения оказалась выше у метода голосования. Соответствующие соотношения сигнал–шум для локальной помехи составляют 0,25 и 0,45 в пользу голосования. Заметим, что величина 0,25 здесь соответствует надежному принятию решения по 1/5 части распознаваемого объекта. Быстродействие методов голосования, обусловленное эффективными процедурами фильтрации наиболее информативных точек, для компьютерной модели оказывается в пять раз (!) выше по сравнению с методом частных корреляций.

Другая серия экспериментов проведена в целях сравнительного анализа корреляционных методов голосования при ограниченном числе фрагментов, выбранных интерактивно (рис. 2). Использовалось 20 фрагментов для базы из 30 полутоновых изображений аквариумных рыбок, вид которых представлен на рис. 3. Для сравнения смоделирован также способ полного представления в виде разбиения на 400 фрагментов. Исходя из экспериментальных данных, по уровню помехозащищенности к аддитивному шуму методы располагаются так: полный набор фрагментов, совместное голосование, независимое голосование. По быстродействию рассмотренные варианты корреляционного подхода можно упорядочить следующим образом: совместное голосование, независимое голосование, полный набор фрагментов. При этом совместное голосование реализуется примерно в 15 раз быстрее, чем полный набор фрагментов. Голосование с поддержкой занимает промежуточное положение по сравнению с анализом без поддержки и уменьшает требуемое соотношение сигнал–шум в пределах 20–40 %, аналогичным образом снижая и быстродействие.

а) б)
Рис. 2. Примеры систем фрагментов: а) фиксированная; б) произвольная


Рис. 3. Изображения базы эталонов


Третья серия экспериментов предназначалась для оценки эффективности применения голосования на основе отношений типа . Для этого в виде признаков использовались векторы чисел размерности 10 с равномерным распределением. Использовано полное множество отношений ХП, в которое включены все возможные комбинации. При действии аддитивного шума обеспечивается распознавание с вероятностью выше 0,95 при следующих значениях сигнал–шум: для одиночных ХП — 5,5; для пар — 1,4; для триплексов — 0,03. Таким образом, надежность распознавания на основе голосования отношений значительно выше, чем при голо-совании одиночных ХП. Заметим, однако, что и вычислительные затраты при этом

несколько выше.


Выводы

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

Новизна работы состоит в обосновании моделей голосования как способа построения иерархических мер для сопоставления изображений в пространствах ХП.

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

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

1. Шлезингер М. Десять лекций по статистическому и структурному распознаванию / М. Шлезингер, В. Главач. — К.: Наук. думка, 2004. — 535 с.

2. Путятин Е.П. Обработка изображений в робототехнике / Е.П. Путятин, С.И. Аверин. — М.: Машиностроение, 1990. — 320 с.

3. Путятін Є.П. Методи та алгоритми комп’ютерного зору: навч. посіб. / Є.П. Путятін, В.О. Гороховатський, О.О. Матат. — Харків: ТОВ «Компанія СМІТ», 2006. — 236 с.

4. Гороховатский В.А. Распознавание изображений в условиях неполной информации / В.А. Гороховатский. — Харьков: ХНУРЭ, 2003. — 112 с.

5. Путятин Е.П. Распознавание изображений в пространстве инвариантных локальных признаков / Е.П. Путятин, В.А. Гороховатский, С.В. Кузьмин // Радиоэлектроника и информатика. — 2006, № 1(32). — С. 69–73.

6. Шапиро Л. Компьютерное зрение / Л. Шапиро, Дж. Стокман; пер. с англ. — М.: Бином. 2006. — 752 с.

7. Lowe D.G. Distinctive Image Features from Scale-Invariant Keypoints // International Journal of Computer Vision. — 2004. — 60, N 2. — Р. 91110.

8. Schmid C. Local greyvalue invariants for image retrieve / C. Schmid, R. Mohr // IEEE Trans. Pattern Analysis and Machine Intelligence. —1997. — Vol. 5, N 19. — P. 530–535.

9. Duda R.O. Pattern Classification. — 2 ed. / R.O. Duda, P.E. Hart, D.G. Stork. — Wiley, 2000. — 738 p.



10. Kim S. Biologically Motivated Perceptual Feature: Generalized Robust Invariant Feature / S. Kim, I.-S. Kweon. — In Asian Conference of Computer Vision (ACCV–06). — 2006. — P. 305–314.
Поступила в редакцию 23.09.2008

ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2008, Т. 10, № 4 75





Как счастлив был бы мужчина, если бы он зарабатывал сумму, в которую, как полагает его жена, оценивают его заработки соседи! Жорж Куртелин
ещё >>