автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы поиска графической информации в информационных системах

На правах рукописи

003171042

Калачик Роман Александрович

Методы поиска графической информации в информационных системах

специальность 05 13 11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

2 3[: -

Тула2008 1

003171042

Работа выполнена на кафедре «Робототехника и автоматизация производства» в ГОУ ВПО «Тульский государственный университет»

Научный руководитель доктор технических наук, доцент

Котов Владислав Викторович

Официальные оппоненты доктор технических наук, профессор

Макаров Николай Николаевич,

кандидат технических наук Титов Сергей Васильевич

Ведущее предприятие Федеральное государственное унитарное

предприятие «Научно-исследовательский институт репрографии», г Тула

Защита состоится « 2$у> 06 2008 г в 14- часов на заседании диссертационного совета Д 212 271 07 в ГОУ ВПО «Тульский государственный университет» (300600, г Тула, пр Ленина, 92, 9-101)

С диссертацией можно ознакомиться в библиотеке Тульского государственного университета (300600, г Тула, пр Ленина, 92)

Автореферат разослан « ло » мая 2008 г

Ученый секретарь диссертационного совета

Ф А Данилкин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность задачи Актуальность разработки математического и программного обеспечения для систем управления базами данных (СУБД) графической информации обусловлена рядом факторов С одной стороны, наблюдается резкий рост объемов хранимых цифровых изображений, обусловленный значительным прогрессом в области построения технических средств формирования цифровых изображений, обработки и хранения цифровой информации включающим расширение номенклатуры фотоэлектронных преобразователей, увеличение емкости и быстродействия цифровых систем хранения информации, появление на рынке специализированных сигнальных процессоров для обработки цифровых изображений

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

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

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

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

онных способов сегментации (яркостной, цветовой, текстурной и т п) для обработки реальных изображений дает неудовлетворительные результаты, поскольку структура сегментов существенно изменяется даже при незначительных вариациях исходного изображения (появление шума, изменение освещенности, смена ракурса, изменение масштаба и т д ) Это позволяет определить предмет исследования диссертационной работы как математические методы и программные средства поиска изображений по содержанию в СУБД графической информации

Диссертационная работа является дальнейшим развитием работ таких отечественных ученых, как В П Андреев, Д А Белов, Г Г Вайнштейн, Я А Фурман, а так же зарубежных ученых А Розенфельда, Р Гонсалеса, У Прэта

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

Реализация поставленной цели включает решение следующих задач

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

2 Поиск формального компактного описания изображения, характеризующего изображение в соответствии с выявленными факторами

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

4 Разработка способа оценки схожести изображений на основании схожести их структурных признаков

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

Методы исследования В работе используются методы теории графов, теории фильтрации, теории вероятностей, теории распознавания образов Разработка алгоритмов и программ осуществлялась на основе объектно-ориентированного подхода к организации данных и алгоритмов

Научная новизна результатов диссертационного исследования заключается в следующем

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

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

3 Предложена система признаков, описывающих визуальные свойства отдельных сегментов, использующаяся для построения нагруженного дерева агрегирования сегментов

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

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

Положения, выносимые на защиту

1 Метод формирования нагруженного дерева агрегирования сегментов, содержащего информацию о форме и расположении сегментов с разной степенью детализации, и векторы признаков отдельных сегментов

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

4 Методика организации базы данных изображений, обеспечивающей повышение эффективности поиска изображений по образцу

Практическая ценность Результаты работы позволяют проводить проектирование систем рассматриваемого класса (разработку программного продукта) без проведения дополнительных исследований

Реализация и внедрение результатов работы Полученные в диссертации теоретические и практические результаты были внедрены в производство программного обеспечения на предприятии «ООО ДевелоперСофт»

(г Тула), а также нашли применение в учебном процессе в ГОУ ВПО «Тульский государственный университет»

Апробация работы Содержание и основные результаты диссертации докладывались на следующих научно-технических конференциях и семинарах.

1 Международная научная конференция «Математические методы в технике и технологиях- ММТТ-19», Воронежская государственная технологическая академия, Воронеж, 2006 г - «Структура системы поиска в коллекциях изображений»

2 ХЫП Всероссийская конференция по проблемам математики информатики физики и химии, РУДН, Москва, 2007 г - «Автоматическая сегментация с агрегированием сегментов в системах поиска изображений»

3 15 я Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», РГРА, Рязань, 2008 г - «Метод получения миниатюр изображений с заданными параметрами»

4 Научно-практические конференции профессорско-преподавательского состава ТулГУ, Тула, 2005-08 гг

Подана заявка на участие в международной научной конференции «Математические методы в технике и технологиях - ММТТ-21», Саратов, 2008 г - «Дерево агрегирования сегментов для задачи автоматической сегментации изображений»

Публикации По теме диссертации опубликованы 11 работ, в том числе 3 тезиса докладов на международных и всероссийских конференциях и семинарах, 8 статей

Структура и объем работы Диссертация состоит из введения, 4 разделов, заключения, изложенных на 146 страницах машинописного текста, и включающих 50 рисунков и 11 таблиц, приложений на 22 страницах и списка использованной литературы из 82 наименований

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первом разделе на основе анализа отечественной и зарубежной научной литературы рассмотрены существующие системы поиска графической

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

• неавтоматизированные,

• полуавтоматические,

• автоматические

Показано, что при росте числа изображений в коллекции неавтоматизированные и полуавтоматические методы поиска неэффективны из-за значительных временных затрат на поиск (в случае неавтоматизированного поиска), либо на поддержку работы ИПС (в случае полуавтоматического поиска)

Выполнен анализ существующих автоматических методов поиска графической информации, включающих

• корреляционные методы поиска изображений,

• методы, использующие нормализацию изображений,

• методы, выделяющие признаки изображений

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

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

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

ноты поиска называют отношение количества полученных релевантных документов к общему количеству существующих в базе данных релевантных документов Коэффициентом точности поиска называют отношение количества релевантных результатов к общему количеству документов, содержащихся в ответе ИПС на запрос Для современных ИПС коэффициент полноты поиска находится в пределах 0 7-0 9, а коэффициент точности находится в пределах 0 1-10 Коэффициент точности больше 0 2 реализуется в системах с ограничениями на класс изображений

Во втором разделе разработана общая схема работы ИПС Определены режимы работы ИПС 1) режим добавления новой информации в базу поиска и 2) режим поиска информации по образцу.

И в том и в другом случае над предъявляемым ИПС изображением последовательно выполняются операции

- первичной обработки, которая может включать в себя пространственно-частотную фильтрацию, масштабирование, нормализацию яркости и т п ,

- извлечения свойств (релевантной относительно задачи поиска информации),

- формирования компактного формального описания изображения

В режиме добавления новой информации сформированное результирующее описание изображения сохраняется в постоянной памяти ИПС

Разработана древовидная структура, содержащая информацию о сегментации изображения с разными уровнями детализации - дерево агрегирования сегментов Дерево агрегирования сегментов представляет собой бинарное дерево, каждому узлу которого сопоставлен сегмент изображения (рис 1) Формирование нижнего слоя дерева агрегирования производится по следующей схеме

Для анализируемого изображения строится взвешенный неориентированный граф С = {у,Е) с множеством вершин У = {У\,У2, V,.} и множеством ребер Е = {е\,в2, еи} для изображения I таким образом, чтобы каждая вершина V, представляла пиксель изображения, и любой паре вершин, представляющих соседние пиксели соответствует ребро Каждому ребру графа б, присваивается вес И^, обратно пропорциональный схожести цветов

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

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

двух сегментов относительно разницы между внутренними элементами каждого из двух сегментов

Внутренняя разность сегмента s, ç V определяется как максимальный

вес в кратчайшем остове графа сегмента, M (s,, Е), 1 (s, ) = max ( w(e))

eeMST(s,,E)

Разница между двумя сегментами s]ts2 ç.V определяется как минимум весов граней, соединяющих два сегмента

¿(s1;52)= min w((v,,v,))

Если нет ни одного ребра, соединяющего si и s2 то D(.s\ ,s2) = œ Пороговая функция D используется для определения необходимости объединения двух сегментов

[О ,D(s„S2)<M(S,,S2)

где

M'is^s,) = min(/(i,) + г(*,), J(j2) + t(s2)) Пороговая функция г определяет величину, на которую должны отличаться два сегмента, чтобы предотвратить их слияние Пусть г(^г) = Ч//]5г], где эмпирическая константа

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

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

Разработан метод формирования дерева агрегирования, основанный на алгоритме автоматической сегментации слиянием сегментов. Основной особенностью предложенного метода является возможность получения результата сегментации с любым уровнем детализации без перезапуска процедуры сегментации. Пусть С = (У,Е) - ненаправленный граф с множеством вершин у, е V и множеством ребер Множество вершин соответствует сегментируемому множеству. Каждое ребро имеет вес м>((к;-,ку)), который представляет собой неотрицательную величину и выражает степень схожести между соседними элементами сегментируемого множества. Обозначим дерево агрегирования символом С , множество вершин в дереве - 5, множество связей вершин — V. Тогда С = {5, V}. Метод заключается в следующем:

1. Сортировать множество ребер графа изображения Е по возрастанию весов. В результате получим упорядоченный набор ребер л(е\,в2,■■£,„).

2а). Задать начальную сегментацию Этаким образом, что каждой вершине соответствует свой компонент в сегментации.

26) Проинициализировать 5 и К пустыми множествами.

3. Повторять шаг 4 для каждого q = 1 ,...т .

4. Построить дерево агрегирования сегментов следующим образом:

4а) Построить из З^1. Имеем Вершины у,и Гупри-

надлежат компонентам из ' и 5у 'соответственно.

46) Если ФБуХ и м>(ед)<М'(3?~\БуХ), тогда:

а) б)

Рис. 1. а) процесс слияния сегментов изображения; б) формирование дерева агрегирования.

4в) Если (5,9-1 >р)&(Бя

> А), ТО

V = Ки(|Уач,5/"1) и (5аЧ,5*-1), иначе = Б*'1 5 Вернуть С = {5, V}

Рассматриваемый метод работает таким образом, что пока площадь объединяемых сегментов не превышает //, его работа повторяет алгоритм сегментации слиянием сегментов, если площадь объединяемых сегментов

превышает //, те выполняется условие (5(9 1 1

> ¡л), формиру-

ется дерево агрегирования сегментов

В третьем разделе введено понятие нагруженного дерева агрегирования Решена задача поиска соответствующих узлов в деревьях агрегирования Для устранения неоднозначности нахождения соответствующих узлов введено три аксиомы

Пусть имеется два нагруженных дерева агрегирования С] и (32, пусть 5| и - соответствующие вершины из и

Аксиома 3 1 Корневые узлы деревьев Сг]°о и ¿2 0 являются соответст-

вующими, т е

- ¿1°0 и 52- ¿2,0

Аксиома 3 2 Соответствующие вершины могут быть расположены только на слоях с одинаковыми номерами, т е

если выполняется 5] = ^ и ^2= то справедливо / = у

Аксиома 3 3 Центры масс агрегированных сегментов, принадлежащих соответствующим вершинам, расположены одинаково относительно центра масс их агрегирующего сегмента, т е , если С(5) - функция расчета координат центра масс сегмента 5 и С?| ^, ¿'ц - соответствующие сегменты, то

справедливо следующее 5./-1

если Сф\~^)Х>Сф,2к)Х, то С(С'2~1) X > ¿(С^) X

если С(6$) ¥ > С(6'2 к) ¥, то С(€'{}) Г > ¿(¿2,,) У если ¿(¿¡~1)X<С(С\к)Х,го )X<С(6'2()X

если С(6ф¥<С{6[ к)¥, то С(д'2})¥ <С(С1и)¥

Решение задачи изложено в виде методики

1 Произвести поиск соответствующих узлов от корней к листьям На основании аксиомы 3 1 корневые узлы деревьев являются соответствующими Сделать корневые вершины текущими вершинами

На основании аксиомы 3 2 и введенных ограничений на арность дерева агрегирования (рассматриваемые деревья агрегирования являются бинарными) можно утверждать, что в множествах агрегированных сегментов текущих вершин возможны только два варианта соответствия

2 На основании аксиомы 3 3 из двух вариантов соответствия выбрать правильный вариант

3 Сделать найденные на шаге 2 соответствующие вершины текущими

Повторять шаги 2-3 пока не будет произведен обход всех узлов деревьев

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

Мера схожести й двух вершин Р1 и Р2 нагруженного дерева агрегирования сегментов определяется как взвешенная сумма квадратов разностей

т 2

компонентов соответствующих им векторов />(/>1,/>2) = (/?1( - р2,) , где

1=1

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

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

1 Вычислить расстояние между векторами свойств корней сравниваемых нагруженных деревьев агрегированияjD = DCG^q^j о), проинициализи-ровать счетчик слоев / = 1

2 g/ди ¿2,( - вычисленные по методике 3 1, соответствующие сегменты текущего слоя сравниваемых деревьев агрегирования

Если <5/¿и ¿21 ~ агрегирующие сегменты, то вычислить расстояние между сегментами и прибавить результат к текущему расстоянию между деревьями агрегирования D = b + D{à[jl,G2t)> увеличить на единицу счетчик слоев в деревьях / = / +1, перейти на пункт 2

Если Gj ^ транзитивный сегмент и 0[ t агрегирующий сегмент или если

Gjj транзитивный сегмент и ^ агрегирующий сегмент, то прибавить к текущему расстоянию штраф за несовпадение структуры деревьев D = D + T

Если G{¿.и ¿21 ~ транзитивные сегменты, то вычислить расстояние между сегментами и прибавить результат к текущему расстоянию между деревьями агрегирования D = D + D{à[¡), перейти к рассмотрению сегментов предыдущего уровня 1 = 1-1, поскольку достигнуты листовые узлы, перейти на пункт 2

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

• свойства области,

• свойства границы области

• комбинированные свойства

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

S У,

__ Vx,eS __Vy,eS

х= и ,>;= И '

где 11 - операция определения мощности множества

Центр масс агрегирующего сегмента 5 = ^ и можно рассчитать как по формулам выше, так и по ускоренной формуле, зная координаты центров масс сегментов, входящих в него Зависимости для расчета центра масс агрегирующего сегмента по раннее рассчитанным координатам центров масс его агрегированных сегментов имеют вид

15,1 + 1521 М + М '

где (х\,~у\) и (Зс2, у2) - координаты центров масс сегментов и £2 соответственно Заметим, что при расчете центра масс сегмента по ускоренным формулам число операций не зависит от числа точек в нем

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

Для промежуточных узлов

1 Узел нагружен вектором вида {Р\,К\,Р2,К.2, ,Ру-],Кд_\,Рд}

где каждое значение Р1 является указателем на другой узел, а каждое значение К, является ключевым значением Можно считать, что Р,_\ указывает на поддерево, у которого узлы содержат ключи, значения которых меньше или равны К,, а Р1 указывает на поддерево, у которого ключи имеют значения, превышающие К,

2 Если узел не корневой, то он содержит минимум [р!2\ указателей на поддеревья

3 Корневой узел содержит минимум 2 указателя на поддеревья Для листовых узлов

1 Узел нагружен вектором вида

{К\, Рг[, К2, Ргз, , , Рг?_1,Рг„}, где К1 является ключом, Рг, - указателем

на данные, а Рг„ - указателем на следующий листовой узел

2 Указатель Рг, указывает на запись или блок записей, имеющих ключ поиска К,

3 В каждом листовом узле хранятся [р/ 2] значений

4 Все листовые узлы расположены в одном слое дерева поиска

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

Поиск информации с использованием В-дерева поиска производится по следующей методике

1 Сделать корневой узел дерева поиска текущим

2 Выполнить двоичный поиск среди ключей в текущем узле

3 Сделать текущим узел, на который указывает найденный по ключу указатель

4 Если поиск в п 2 не вернул указатель, выдать сообщение об отсутствии изображения в базе

5. Если достигнут листовой узел, вернуть изображение, на которое ссылается листовой узел

6 Если не достигнут листовой узел, перейти на пЗ

В четвертом разделе проведены экспериментальные исследования методов поиска графической информации Для экспериментальной проверки предложенных решений разработан программный модуль СУБД, реализующий предложенные методы (рис 2)

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

Рис 2 Структура СУБД для проведения исследований Кроме того, в ЭВМ содержится вся информация о синтезируемых сценах, что позволяет рассчитать фактическое различие между сценами и сравнить его с полученным в результате сравнения изображений сцен предложенным методом

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

Разработанный модуль СУБД представляет собой средство сегментации и поиска цифровых изображений Обрабатываемые изображения могут иметь геометрические размеры до 1500 пикселей по высоте и ширине и быть представлены в одном из четырех распространенных графических форматов (JPEG, GIF, BMP, TIFF) Ограничения геометрических размеров не носят принципиального характера и вызваны стремлением сократить время на отдельный эксперимент

Для экспериментальной проверки предложенных решений были проведены следующие эксперименты

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

• проверка эффективности работы критерия схожести изображений на наборе синтезированных изображений,

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

Проведенные эксперименты показывают, что ИПС может решать основные практические задачи, встречающиеся при поиске изображений в коллекциях Средний коэффициент точности поиска в коллекции реальных изображений сложных сцен составил Р = 0 32, коэффициент полноты поиска составил Я = 1 Коэффициент точности поиска укладывается в нормы для коэффициентов точности работы современных ИПС и согласуется с результатами экспериментов, проведенных на наборе программно синтезированных изображений Предложенная новая структура данных - дерево агрегирования сегментов а так же метод формирования дерева агрегирования и метод сравнения нагруженных деревьев агрегирования позволяют увеличить коэффициент точности поиска графической информации с 0 2 до 0 32 без введения ограничений на характер графических данных Разработанная методика формирования графических миниатюр с заданными параметрами и классификация свойств сегментов позволяют проектировать эффективные с точки зрения производительность системы поиска графической информации

В заключении сформулированы основные результаты и выводы работы

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

По диссертационной работе можно сформулировать следующие основные выводы и результаты

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

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

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

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

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

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

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

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

9 Программно реализована система алгоритмов, создающих предпосылки применения метода поиска графической информации в СУБД для поиска изображений по их содержимому

10 Исследована эффективность критерия схожести на наборе изображений сложных сцен Средний коэффициент точности поиска составил 0 32 Коэффициент точности поиска укладывается в нормы для коэффициентов точности работы современных ИПС и согласуется с результатами экспериментов, проведенных на наборе программно синтезированных изображений

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 R Kalachik, V Kotov Fractal image compression (статья на англ яз ), GlobalDSP [электронный ресурс], 2004 GlobalDSP, Vol 3, Issue 5, May 2004 Режим доступа http //www globaldsp com, свободный - Заголовок с экрана

2 Калачик РА Сравнительный анализ процессоров фирмы Texas Inwstruments при реализации алгоритмов сжатия изображений в мобильных устройствах ИД «Электроника» // Электронные компоненты - №9, 2004 -С 44-48

3 Калачик РА Цифровые усилители мощности ИД «FmeStreet» // Компоненты и технологии - № 8,2004 - С 54-56

4 R Kalachik La composizione degli effetti video (статья на итал яз ) // Elettronica Oggi (ISSN 0391-6391) - October, 2005 -Pp 30-34

5 R Kalachik Code quality improvement under Code Composer Studio (статья на англ яз ) GlobalDSP, August 2005 [электронный ресурс], режим доступа http //www dspstore com/Newsletter/August2005/CodeComposer htm свободный - Заголовок с экрана

6. Калачик P.A., Котов В.В. О задаче поиска изображений в коллекциях. // Известия ТулГУ. Серия: Вычислительная техника. Информационные технологии. Системы управления. Вып. 3. Системы управления. - Тула: Изд-во ТулГУ, 2005. - 245 с. (С. 83-88).

7. Калачик P.A. Алгоритм быстрой сегментации изображений. //Известия ТулГУ. Серия: Проблемы специального машиностроения. Вып. 9, Том 2. - Тула: Изд-во ТулГУ, 2006. - 247с. (С. 191-193)

8 Калачик Р А , Котов В В Структура системы поиска в коллекциях изображений // Математические методы в технике и технологиях -ММТТ-19 Сб трудов Международной научной конференции В 10-ти томах Т 8 Секция 8 / Воронеж, Воронежская государственная технологическая академия, 2006 -226 с. (С 95-06)

9 Калачик Р А , Котов В В Автоматическая сегментация с агрегированием сегментов в системах поиска изображений XLIII Всероссийская конференция по проблемам математики информатики физики и химии Тезисы докладов. Серия физики - М РУДН, 2007,90 с (С 48-49)

10. Калачик P.A. Алгоритм автоматической сегментации с агрегированием сегментов в системах поиска изображений ISSN 1995-4565. // Вестник РГРТУ. Вып. 23. Рязань 2008,200с. (С 135-139)

11 Калачик Р А Котов В В Метод получения миниатюр изображений с заданными параметрами // 15-я Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» Тезисы докладов -Рязань, 2008 -164с (С 91-93)

Формат 60 х 84 1/16 Печать офсетная Бумага офсетная Объем 1,25 п л Тираж 100 экз Заказ №236

Тульский государственный университет 300600, Тула, просп Ленина, 92 Издательство ТулГУ 300600, Тула, ул Болдина, 151

Введение

1. Анализ методов поиска графической информации в информационно-поисковых системах

1.0. Введение

1.1. Общая структура информационно-поисковой системы

1.2. Существующие подходы к решению задачи поиска изображений в коллекциях

1.2.1. Неавтоматизированные (ручные) виды поиска

1.2.2. Полуавтоматические виды поиска

1.2.3. Автоматические виды поиска

1.3. Способы формирования изображений, используемых в ИПС

1.3.1. Формирование изображений с помощью технических средств

1.3.2. Методы синтеза изображений

1.4. Способы кодирования информации в изображениях, используемых в ИПС

1.5. Формальное описание цифровой модели изображения

1.5.1. Общие определения

1.5.2. Кодирование цвета в цифровых моделях изображений

1.6. Требования к информационно-поисковым системам и критерии оценки эффективности работы

1.7. Релевантность поиска графической информации

1.8. Существующие системы поиска графической информации и области их применения

1.9. Постановка задачи на исследования

1.10. Выводы по главе

2 Формирование компактного описания изображения для решения задачи поиска по содержанию

2.0 Введение

2.1 Схема функционирования ИПС

2.2 Формирование графических миниатюр

2.3 Подход к построению формального описания изображения

2.4 Агрегирование сегментов

2.5 Общая схема метода формирования дерева агрегирования сегментов

2.5.1 Создание графа по изображению

2.5.2 Критерий объединения сегментов

2.5.3 Расчет минимального остова графа

2.6 Метод формирования дерева агрегирования сегментов

2.7 Выводы

3 Поиск графической информации по содержанию изображения

3.0 Введение •

3.1 Нагруженные деревья агрегирования

3.2 Поиск соответствующих узлов в нагруженных деревьях агрегирования

3.3 Мера схожести соответствующих узлов нагруженных деревьев агрегирования

3.4 Методика сравнения нагруженных деревьев агрегирования сегментов

3.5 Классификация свойств сегментов

3.6 Вычисление свойств области сегмента

3.7 Вычисление свойств границы области

3.8 Вычисление комбинированных свойств

3.9 Методика индексирования графических изображений при организации базы данных изображений

3.10 Выводы 86 4 Экспериментальные исследования методов поиска графической информации

4.0 Введение

4.1 Описание программно-аппаратного комплекса

4.2 Обобщенная структура алгоритма

4.3 Общая постановка экспериментальных исследований разработанных методов

4.4 Исследование эффективности работы алгоритма автоматической сегментации

4.5 Исследование эффективности критерия схожести изображений на синтезированных изображениях простых сцен

4.6 Исследования эффективности критерия схожести реальных изображений простых сцен

4.7 Исследование эффективности работы поисковой системы на коллекции реальных изображений сложных сцен

4.8 Выводы

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

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

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

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

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

Диссертационная работа является дальнейшим развитием работ таких отечественных ученых, как В.П. Андреев, Д.А. Белов, Г.Г. Вайнштейн, Я.А. Фурман, а так же зарубежных ученых А. Розенфельда, Р. Гонсалеса, У. Прэта.

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

Реализация поставленной цели включает решение следующих задач.

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

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

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

4. Разработка способа оценки схожести изображений на основании схожести их структурных признаков.

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

Методы исследования. В работе используются методы теории графов, теории фильтрации, теории вероятностей, теории распознавания образов. Разработка алгоритмов и программ осуществлялась на основе объектно-ориентированного подхода к организации данных и алгоритмов.

Методы исследования. В работе используются методы теории графов, теории фильтрации, теории вероятностей, теории распознавания образов. Разработка алгоритмов и программ осуществлялась на основе объектно-ориентированного подхода к организации данных и алгоритмов.

Научная новизна результатов диссертационного исследования заключается в следующем:

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

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

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

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

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

Положения, выносимые на защиту.

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

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

4. Методика организации базы данных изображений, обеспечивающей повышение эффективности поиска изображений по образцу.

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

Реализация и внедрение результатов работы. Полученные в диссертации теоретические и практические результаты были внедрены в производство программного обеспечения на предприятии «ООО ДевелоперСофт» (г. Тула), а также нашли применение в учебном процессе в ГОУ ВПО «Тульский государственный университет».

Апробация работы. Содержание и основные результаты диссертации докладывались на следующих научно-технических конференциях и семинарах:

1. Международная научная конференция «Математические методы в технике и технологиях - ММТТ-19», Воронежская государственная технологическая академия, Воронеж, 2006 г. - «Структура системы поиска в коллекциях изображений»

2. XLIII Всероссийская конференция по проблемам математики информатики физики и химии, РУДН, Москва, 2007 г. - «Автоматическая сегментация с агрегированием сегментов в системах поиска изображений».

3. 15 я Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», РГРА, Рязань, 2008 г. - «Метод получения миниатюр изображений с заданными параметрами».

4. Научно-практические конференции профессорско-преподавательского состава ТулГУ, Тула, 2005-08 гг.

Подана заявка на участие в международной научной конференции «Математические методы в технике и технологиях — ММТТ-21», Саратов, 2008 г. — «Дерево агрегирования сегментов для задачи автоматической сегментации изображений».

Публикации. По теме диссертации опубликованы 11 работ, в том числе: 3 тезиса докладов на международных и всероссийских конференциях и семинарах, 8 статей.

Структура и объём работы. Диссертация состоит из введения, 4 разделов, заключения, изложенных на 146 страницах машинописного текста, и включающих 50 рисунков и 11 таблиц, приложений на 22 страницах и списка использованной литературы из 82 наименований.

ВЫВОДЫ ПО РАБОТЕ

По диссертационной работе можно сформулировать следующие основные выводы и результаты:

По диссертационной работе можно сформулировать следующие основные выводы и результаты:

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

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

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

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

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

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

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

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

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

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

1. Абчук В.А., Суздаль В.Г. Поиск объектов. М.: Сов. радио, 1977. -336 с.

2. Айфичер Э., Джервис Б. Цифровая обработка сигналов. Практический подход. М.: "Вильяме", 2004. - 992 с.

3. Александров В.В., Горский М.Д. Представление и обработка изображений. Рекурсивный подход- Л.: Наука. Ленингр. отд-ние, 1985.-189 с.

4. Аммерал Л. Машинная графика на персональном компьютере. М.: Сол Систем, 1992. - 230 с.

5. Андриянов А.В., Шпак И.И. Цифровая обработка информации в измерительных приборах и системах. Минск: Высш. шк., 1987. -174 с.

6. Ахмед Н., Рао К. Ортогональные преобразования при обработке цифровых сигналов. М.: Мир, 1980. - 248 с.

7. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М: Мир, 1989.-245 с.

8. Боресков А.В., Шикин Е.В., Шикин Г.Е. Компьютерная графика: первое знакомство. М.: Финансы и статистика, 1996. - 176 с.

9. Бутаков Е.А., Островский В.И., Фадеев Л.И. Обработка изображений на ЭВМ. М.: Радио и связь, 1987. - 236 с.

10. Быстрые алгоритмы в цифровой обработке в цифровой обработке изображений. // Ред. Хуанга Т.С. М.: Радио и связь, 1984. - 224 с.

11. П.Ватанаба М. Современные тенденции развития технологии технического зрения. // «Обозрение Тошиба». 50, № 8, 1995. - С. 604-606.

12. Введение в цифровую фильтрацию: пер. с англ., под ред. Филиппова Л.И. М.: Мир, 1976.

13. Гинзбург В.И. Формирование и обработка изображений в реальном времени. М.: Радио и связь, 1986. - 312 с.

14. Годжаев Н.М. Оптика. Учебное пособие для вузов. — М.: Высш. школа, 1977. 432 с.

15. Голд Б., Рейден И. Цифровая обработка сигналов. М.: Мир, 1973. -367 с.

16. Гольберг Л.М. Цифровая обработка сигналов. М.: Радио и связь, 1990.- 325 с.

17. Горелик А.Л., Скрипкин В.А. Методы распознавания. — М.: Высш. шк., 1977.-222 с.

18. Горьян Н.С., Кац Б.М., Цуккерман И.И. Выделение статистически однородных участков изображений. В кн.: Иконика. Цифровая голография. Обработка изображений. М.: Наука, 1975. — с. 62-73.

19. Григоренко A.M. Некоторые вопросы теории технической информации. М.: ЮБЕКС, 1998. - 112 с.

20. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов. М.: Мир, 1988. - 488 с.

21. Дмитриев В.И. Прикладная теория информации. М.: Высшая школа, 1989. - 320 с.22.3авалишин Н.В., Мучник И.Б. Модели зрительного восприятия и алгоритмы анализа изображений. М.: Наука, 1974. — 344 с.

22. Информационно-измерительные системы коллективного пользования / Загорский В.П., Пугачев И.С., Ярусов А.Г. АН БССР. Ин-т технической кибернетики. Минск: Наука и техника, 1987. -104 с.

23. Калачик Р.А Алгоритм быстрой сегментации изображений. // Известия ТулГУ. Серия: Проблемы специального машиностроения. Вып. 9, Том 2. Тула: Изд-во ТулГУ, 2006. - с. 191- 193

24. Калачик Р.А. Алгоритм автоматической сегментации с агрегированием сегментов в системах поиска изображений. // Вестник РГРТУ. Вып. 23. Рязань: Изд-во РГРТУ . 2008, - с 135139.

25. Калачик Р.А. Котов В.В. О задаче поиска изображений в коллекциях // Известия ТулГУ. Серия: Вычислительная техника. Информационные технологии. Системы управления. Вып. 3. Системы управления. Тула : Изд-во ТулГУ, 2005. - с 83-88.

26. Калачик Р.А. Котов В.В. Структура системы поиска в коллекциях изображений // Математические методы в технике и технологиях

27. ММТТ-19: Сб. трудов Международной научной конференции. В 10-ти томах. Т. 8. Секция 8 Воронеж: Изд-во ВГТА , 2006. - с 95-06.

28. Калачик Р.А. Сравнительный анализ процессоров фирмы Texas Instruments при реализации алгоритмов сжатия изображений в мобильных устройствах // Электронные компоненты, №9 — М: Изд-во "Электроника", 2004 г, с. 65-67.

29. Калачик Р.А. Цифровые усилители мощности // Компоненты и технологии, № 8 СПб: Изд-во "FineStreet", 2004 г. - с. 73-75.

30. Каппелини В, Константинидис А. Дж., Эмилиани П. Цифровые фильтры и их применение М.: Энергоатомиздат, 1983 — 360 с.

31. Карташев В.Г. Основы теории дискретных сигналов и цифровых фильтров. — М.: Высш. школа, 1982. — 109 с.

32. Катыс Г.П. Восприятие и анализ оптической информации автоматической системой. М.: Машиностроение, 1986. — 416 с.

33. Катыс Г.П. Методы и вычислительные средства обработки изображений. Кишинев: Штиинца, 1991. - 209 с.

34. Катыс Г.П. Обработка визуальной информации М.: Машиностроение, 1990. — 320 с.

35. Колмогоров А.Н. Три подхода к определению понятия «количество информации» //Проблемы передачи информации, 1965. Т. 1. Вып. 1. с. 25-38.

36. Копейкин С.В. Адаптивные методы обработки измерений. -Саратов: Изд-во Саратовского ун-та, 1982. — 120 с.

37. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). — М.: Наука, 1973. — 831 с.

38. Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования. Киев: Вища школа, 1986. - 360 с.41 .Куликовский Л.Ф., Мотов В.В. Теоретические основы информационных процессов. — М.: Высш. шк., 1987. 248 с.

39. Купер Дж., Макгиллем К. Вероятностные методы анализа сигналов и систем: Пер. с англ. М.: Мир, 1989. - 376 с.

40. Логвиненко А.Д. Чувственные основы восприятия пространства, М., Изд. МГУ, 1985-224с.

41. Маликов В.М., Дубовой В.М., Кветный P.M., Исматулаев П.Р. Анализ измерительных информационных систем — Ташкент: Ташкентский политехи, ин-т им. А.Р. Беруни., 1984. 176 с.

42. Методы компьютерной обработки изображений. / Под ред. В.А. Сойфера. М.: Физмат, 2001. - 784 с.

43. Павлидис Т. Алгоритмы машинной графики и обработки изображений. М.: Радио и связь, 1986. - 400 с.

44. Писаревский А.И. Системы технического зрения. СПб.: Машиностроение, 1988. -240 с.

45. Прэтт У. Цифровая обработка изображений: В 2х кн. М.: Мир, 1982 г.-714 с.

46. Р. Гонсалес, Р. Вудс Цифровая обработка изображений. М -Техносфера, 2006 1072с

47. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC М.: Унитех, 1992. - 156 с.

48. С.Н Ганебных, М.М Ланге, "Древовидное представление образов для распознавания полутоновых объектов" // Труды Вычислительного центра им. А.А Дородницына РАН, Москва: ВЦ РАН, 2007, заказ 48 (отдельный выпуск, 32 е.).

49. Смирнов М.В. Распознавание изображения края полуплоскости в задаче количественного анализа изображений //Сб. статей: Применение методов оптической обработки изображений, Л., РПТ ЛИЯФ, 1986.-е. 233-235.

50. Ту Дж., Гонсалес Р., Принципы распознавания образов. М: Мир, 1978.-е. 99-103.

51. Фу К., Гонсалес Р., Ли К. Робототехника. /Пер. с англ. М.: Мир, 1989.-624 с.

52. ХеммингР.В. Цифровые фильтры. -М.: Недра, 1987. -221 с.

53. Хорн Б.К. Зрение роботов. М.: Мир, 1989. - 448 с.

54. Хромов Л.И., Цыцулин А.К., Куликов А.Н. Видеоинформатика. Передача и компьютерная обработка видеоинформации,— М.: Машиностроение, 1990. — 320 с.

55. Хэмминг Р.В. Теория кодирования и теория информации: пер. с англ. М.: Радио и связь, 1983. - 176 с.бЗ.Чжун Кай-лай. Однородные цепи Маркова. М.: Мир, 1964. - 426 с.

56. Чукин Ю.В. Структуры данных для представления изображений. // «Зарубежнаярадиоэлектроника», №8, 1983.-С. 85.

57. А.К. Jain and A. Vailaya. Shape-Based Retrieval: A Case Study with Trademark Image Databases. Pattern Recognition, vol. 31(9):pp. 13691390, 1998.

58. Ann Bengtsson and Jan-Olof Eklundh, "Shape Representation by Multiscale Contour Approximation", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13 (1), pp. 85-93, Jan. 1991.

59. Berretti S., Del Bimbo A. Multiresolution spatial partitioning for shape representation. // IEEE Proceedings of ICPR, 2004. Vol. 2. Pp. 775-778.

60. Blahut R.M. Fast algorithms for digital signal processing. Addison-Wesley, 1985.

61. C. Chu and J. K. Aggarwal, "The integration of image segmentation maps using region and edge information," IEEE Trans. Pattern Anal. Machine Intell., vol. 15, pp. 1241-1252, 1993.

62. Charles Zahn and Ralph Roskie, "Fourier Descriptors for Plane Closed Curves", IEEE Transaction on Computer, vol. C-21 (3), March 1972.

63. D. Comaniciu, P. Meer, "Robust Analysis of Feature Spaces:Color Image Segmentation," Proc. of CVPR'97, pp. 750-755.

64. D. Marr. A theory for cerebral neocortex, Proceedings of the Royal Society of London, 1970.

65. D. Marr. Early processing of visual information, Proceedings of the Royal Society of London, 1976.

66. D. О. Hebb. The organization of behavior. John Wiley, 1949.

67. D. R. Karger, C. Stein. An algorithm for minimum cuts. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pp. 757-765, 1993.

68. Del Bimbo and P. Pala. "Shape Indexing by Multi-Scale Representation." Image and Vision Computing, vol. 17(3-4): pp. 245-261, 1999.

69. Duda R.O., Hart P.E., Stork D.G. Pattern classification. Wiley, 2001.

70. E. M. Stokely and S. Y. Wu. Surface parametrization and curvature measurement of arbitrary 3-D objects: Five practical methods. IEEE Transactions onPAMI, 14,833, 1992.

71. Effcient Graph-Based Image Segmentation Algorithm Pedro F. Felzenszwalb, Daniel P. Huttenlocher. IEEE Trans, on Communications, 4, pp. 342-359, 1994

72. Equitz W.E., Cover T.M. Successive refinement of information. // IEEE Transactions on Information Theory, 1991. Vol. 37. Pp. 269-275.

73. F. Attneave and M. D. Arnoult. The quantitative study of shape and pattern perception. In L. Uhr editor, Pattern Recognition, 141. John Wiley, 1966.

74. Farzin Mokhtarian and Alan K. Mackworth, "A Theorey of Mlltiscale, Curvature-Based Shape Representation for Planar Curves", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14 (8), pp. 85-93, Jan. 1992.

75. H.H.S. Ip, D. Shen, and K.K.T. Cheung. "Affine Invariant Retrieval of ' Binary Patterns Using Generalized Complex Moments." In Second International Conference on Visual Information Systems (VISUAL'97), pp. 301-308, 1997.

76. Ни M.K. Visual pattern recognition by moment invariants. // IRE Transactions on Information Theory, 1962. Vol. 8. Pp. 179-187.

77. J. Haddon and J. Boyce, "Image segmentation by unifying region and boundary information," IEEE Trans. Pattern Anal. Machine Intell., vol. 12, pp. 929-948, 1990.

78. J. J. Gibson. The perception of the visual world. Houghton, 1950.

79. J. Koenderink and A. Van Doom. Dynamic shape, Biological Cybernetics, 1986.

80. Jagadish H., Bruckstein A. On sequential shape descriptions. // Pattern Recognition, 1992. Vol. 25. Pp. 165-172.

81. Kim H., Park K., Kim M. Shape decomposition by collinearity. // Pattern Recognition Letters, 1987. Vol. Pp. 335-340.

82. L. Davis. Understanding shape: Angles and sides. IEEE Transactions on Computers, 26,236, 1977.

83. L. R. Jr. Ford, D. R. Fulkerson. Maximum flow through a network. Canadian Journal of Mathematics, Vol. 8, pp. 399-404, 1956.

84. L. Zusne. Contemporary Theory of Visual Form Perception: III. The Global Theories, chapter 4, Academic Press, 1970

85. L.J. Latecki and R. Lakamper, " Shape Description and Search for Similar Objects in Image Databases", State-of-the-Art in Content-Based Image and Video Retrieval, Kluwer Academic Publishers, 20001.i i

86. L.J. Latecki and R. Lakamper, "Application Of Planar Shape Comparison To Object Retrieval In Image Databases". Pattern Recognition, 35(1), pp. 15-29, 2002.

87. Lange M.M., Ganebnykh S.N. Tree-like data structures for effective recognition of 2-D solids. // IEEE Proceedings of ICPR, 2004. Vol. 1. Pp. 592-595.

88. Lange M.M., Lange A.M. Data classification in the space of tree-structured representations. // Pattern Recognition and Image Analysis, Nauka/Interperiodica, 2004. Vol. 14. No. 1. Pp. 12-22.

89. Loncaric S. A survey of shape analysis techniques. //Pattern Recognition, 1998. Vol. 34. Pp. 983-1001.

90. Milan Sonka, Vaclav Hlavac, and Roger Boyle, Image Processing, Analysis, and Machine Vision, Second Edition, pp. 240-248, Brooks/Cole Publishing Company, 1999.

91. Ming-Kuei Hu, "Visual Pattern Recognition by Moment Invariants", IRE Transaction on Information Theory, vol. 8, pp. 179-187, 1962.

92. N. Pal and S. Pal, "A reviewon image segmentation techniques," PatternRecognit., vol. 26, pp. 1277-1294, 1993.

93. P. L. Palmer, H. Dabis, and J. Kittler, "A performance measure for boundary detection algorithms," Comput. Vis. Image Understanding, vol. 63, pp. 476-494, 1996.

94. P.J. Burt et A.E. Adelson, "The Laplacian pyramid as a compact image code", IEEE Trans, on Communications, 31, pp. 532-540, 1983.

95. R. C. Veltkamp, "Shape Matching: Similarity Measures and Algorithms," Proc. Shape Modelling International,' Genova, Italy, pp. 188-197, May 2001.

96. R. Kalachik Code quality improvement under Code Composer Studio (статья на англ. яз.) GlobalDSP, August 2005. 'электронный ресурс, режим доступа: http://www.dspstore.com/Newsletter/August2005/CodeComposer.htm

97. R. Kalachik La composizione degli effetti video (статья на итал. яз.) ISSN : 0391-6391, Elettronica Oggi October 2005 Pages 30-34.

98. R. Kalachik, V. Kotov Fractal image compression (статья на англ. яз.), GlobalDSP электронный ресурс., 2004. GlobalDSP, Vol. 3, Issue 5, May 2004. Режим доступа: http://www.globaldsp.com, свободный. -Заголовок с экрана.

99. Rafael Gonzalez and Richard Woods, Digital Image Processing, pp.655-659, Prentice Hall, 2002.

100. Rosenfield A. Multiresolution image analysis. // Proceedings of 3-rd Scandinavian Conference on Image Analysis, 1983. Pp. 23-28.

101. Row H., Medioni G. Hierarchical decomposition of axial shape description. // IEEE Transactions on PAMI, 1993. Vol. 15. Pp. 973-981.

102. T. Pavlidis. A review of algorithms for shape analysis. Computer Graphics and Image Processing 1978, 243-258.

103. V. Goldberg, R. E. Tarjan. A New Approach to the Maximum Flow Problem. Journal of the ACM, Vol. 35, pp. 921-940, 1988.

104. Vapnik V.N. The nature of statistical learning theory. Springer, 2000.

105. Voss K., Suesse H. Invariant fitting of planar objects by primitives. // IEEE Proceedings oflCPR, 1996. Pp. 508-512.

106. Weiss I. Geometric invariants and object recognition. // International Journal of Computer Vision, 1993. Vol. 10. Pp. 207-231.

107. Y. Gong and M. Sakauchi, "Detection of regions matching specified chromatic features," Comput. Vis. Image Understanding, vol. 61, pp. 263-269, 1995.

108. Y. H. Ang, Z. Li, and S. H. Ong. "Image Retrieval based on Multidimensional Feature Properties." In Proceedings of IS\&T/SPIE Conference on Storage and Retrieval for Image and Video Databases III, Vol. SPIE 2420, pp. 47-57, 1995.

109. Y. Rui, T.S. Huang, and S.-F. Chang, "Image retrieval: Current techniques, promising directions and open issues," J. Vis. Comm. Im. Repr., vol. 10, pp. 39-62, Mar. 1999.

110. Yannis Avrithis, Yiannis Xirouhakis, Stefanos Kollias. Affine-invariant curve normalization for object shape representation, classification, and retrieval. Machine Vision and Applications (2001) 13: 80-94.

111. Y-S. Kim and Kim W-Y. "Content-Based Trademark Retrieval System by using Visually Salient Feature." In Proc. of IEEE Conf. on Computer Vision and Pattern Recognition, pp. 307-312, 1997.

112. A. Pentland. Fractal-based description of natural scenes. IEEE Transactions on PAMI, 6,661, 1984.