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

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

и '

ГОРБАНЬ Александр Сергеевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ ОБНАРУЖЕНИЯ СИММЕТРИИ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ

Специальность 05.13.18 — Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ диссертация на соискание учёной степени кандидата физико-математических наук

Таганрог 2008

Работа выполнена

в Технологическом институте Южного федерального университета в г.Таганро!

Научный руководитель: доктор физико-математических наук,

профессор Каркищенко Александр Николаева

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

профессор Нахушев Адам Маремович (НИИ прикладной математики и автоматизации КБНЦ РАН, г. Нальчик)

доктор физико-математических наук, профессор Сербина Людмила Ивановна (СевКавГТУ, г. Ставрополь)

Ведущая организация: Вычислительный центр РАН

им. АА. Дородницына, г. Москва.

Защита состоится « 26 » августа 2008 года в 14 ч. 20 мин. на заседании Диссертационного совета Д212.208.22 Южного федерального университета по адресу: Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФ по адресу: Ростов-на-Дону. ул. Пушкинская, 148.

Автореферат разослан « 7 » июля 2008 года.

Просим Вас прислать отзыв на автореферат, заверенный гербовой печать учреждения, по адресу: 347928, Таганрог, пер. Некрасовский, 44, диссертационнь совет Д212.208.22.

Ученый секретарь

диссертационного совета Д212.208.22 доктор технических наук, профессор

А.Н. Цел

общая характеристика работы

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

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

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

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

В связи с поставленной целью необходимо решить следующие задачи

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

2) разработать математический аппарат для исследования свойств симметрии непрерывных изображений,

3) разработать и исследовать эффективные в вычислительном плане методы

определения параметров вращательной и отражательной симметрии конту ров и изображений,

4) практически реализовать и экспериментально исследовать полученные мс тоды

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

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

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

• введено и исследовано понятие непрерывного преобразования симметрии,

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

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

• разработаны эффективные алгоритмы обнаружения вращательной и отр жательной симметрии контуров и изображений.

Практическая ценность. Разработанная математическая модель симметри цифровых изображений может применяться для сегментации изображений, от слеживания и распознания движения, индексирования баз данных графическо информации, выделения глобальных характерных особенностей изображений, о наружения, распознавания и выделения характерных черт лиц, сжатия изобра жений На основании теоретических результатов диссертационной работы был создано программное обеспечение на языке С под управлением GNU/linux дл анализа симметрии изображений фотографического качества

Апробация работы. Практические и теоретические результаты диссертаци использованы в научно-исследовательских проектах РФФИ №07-07-00067 «Раз работка обобщенной математической модели анализа симметрии изображений н основе непрерывного преобразования симметрии» и №08-07-00129 «Исследовани многомасштабного знакового представления образов в задачах анализа биомет рической информации при разработке систем информационной безопасности»

Основные положения и результаты работы представлялись и обсуждались н VII Всероссийской научной конференции студентов и аспирантов «Техническа кибернетика, радиоэлектроника и системы управления» (Таганрог, 2004), III Всс российской научной конференции молодых ученых и аспирантов «Новые инфор мациониые технологии Разработка и аспекты применения» (Таганрог, 2004), Фс деральпой итоговой научно-технической конференции «Всероссийского конкурс на лучшие научные работы студентов по естественным, техническим наукам ( области высоких технологий) и инновационным научно-образовательным прое

там» (Москва, 2004), Международной научной конференции «Интеллектуальные и многопроцессорные системы-2005» (Таганрог, 2005), II Международной научной конференции «Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий» (г Евпатория, 2006), Восьмом научно-практическом семинаре «Практика и перспективы развития партнерства в сфере высшей школы» (Донецк, 2007), Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2007), III Международной научной конференции «Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий» (г Евпатория, 2007), Второй Международной конференции «Системный анализ и информационные технологии» (Обнинск, 2007), Международной конференции по системам искусственного интеллекта (AIS/CAD '08) (Дивноморское, 2008)

Публикации. По теме диссертации опубликовано 17 работ, из них две работы в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утвержденный ВАК

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех тематических глав, заключения, списка литературы и приложений Общий объем основного текста - 166 страниц, включая 40 рисунков Список литературы изложен на 13 страницах и содержит 100 наименований

содержание работы

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

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

Пусть D = R2 и Ьаф —xsm а + у cosa — р — 0, —к < а < п, р > 0, -некоторая прямая в R2, заданная нормальным уравнением Здесь а - угол, кото-

(cos а\

рый образует направляющий вектор па— I I прямой La p с положительным

направлением оси ОХ, ар - расстояние от прямой до начала координат Также используются следующие обозначения Faj} - преобразование плоскости, состоящее в ортогональном отражении точек плоскости относительно прямой Lap, называемой осью симметрии, Тах - оператор поворота точек плоскости относительно

точки х 6 R2, называемой центром вращения, на угол а против часовой стрелк В данной главе исследуются свойства изображений при действии следуюпц групп преобразований плоскости Gp = (Fa,p) ~ группа отражений и Gt = {Та, - группа вращений Легко убедиться, что имеют место следующие соотношени Fl = е, Г"1 = Г_„, F0TaFp = Т_0, ТаТд = Ta+[i, Fa+0 = Т* = Тк

к € Z, где е - тождественное преобразование Показывается, что композиц ей двух отражений является вращение, причем FaiFai = Т2(а2-а1), а композ ция отражения и вращения является отражением, причем FaT7 = Fa_a Данн свойства аффинных преобразований используются для доказательства следу щих вспомогательных лемм

Лемма 1 Для любого г £ R справедливо Fa p (гх) = rFat2 (х)

Лемма 2. Пусть х, у € R2 Тогда FQiP (х + у) = Fa>px + Fn py - 2рпа

Основная часть первой главы посвящена исследованию свойств введенного п нятия автоморфных областей Пусть G - некоторая группа преобразований, опр деленных на плоскости R2, действие которой рассматривается в некоторой обл сти DC К2 Область Д С D будем называть G-автоморфной, если для любо g € G справедливо равенство <?Д = Д Область Д называется (а,р)-автоморфпо если она G-автоморфна, где G = {Fn p) Термин «автоморфная область» являет синонимом инвариантного подмножества относительно действия группы отраж ний, иными словами, это область переходящая при отражении сама в себя Вм сте с тем, введенное понятие автоморфности в большей степени ориентировано i «прикладной» смысл исследований, связанных с анализом внутренних симметр изображений Область А,шх называется максимальной автоморфной область если не существует автоморфной области Д такой, что Атах С Д Обозначи через g (D) = {<?х | х £ D} образ области D при действии элемента группы Тогда нетрудно видеть, что Aniax = DCi Faj) (D)

Ключевым для преобразования симметрии является понятие меры автомор ной области т (Атах) = тп(а,р) В качестве меры области в работе берется площадь Если D является кругом, то определение Атах не представляет особо труда и в работе показывается, что т(а,р) = R2 arccos (2^ — 1 j - p^JR2 —р Однако в общем случае, когда D - произвольная ограниченная область, и даж если она полигональная и выпуклая, нахождение выражения для меры макс мальпой автоморфной области является нетривиальной задачей

Пусть Н (2) - функция Хевисайда, то есть Я (г) = < г — Введем в ра

10, г < О

смотрение вспомогательные функции в(а,р) = Н [VN2 + М2 tg a cos (а + ip) — 01 (а,р) = Н [— у/N2 + М2 ctg а cos (а + — р]

Основным результатом первой главы является следующая теорема

Теорема 1. Пусть задана область D = {(х,у) | х 6 [-N,N],x& [-М,М] причем М < N, и прямая La<p, a S [0, |], р > 0, пересекающая эту облает

Тогда мера т(Л) = т(а, р) автоморфной области для группы отражений С определяется выражением

т(а,р) =

(О, U) - (N, М) - в (а,р) А, (а,р) е <ть

Llv (-N, М) - в (,а,р) Д (а,р) е аа,

2

srn 2а а,р s in 2а

^ + 0! (а,р) В + [1 - в (а,р)] А, (а,р) € а3,

acfe CTi = {0 < а < <р, 0 < р < \/N2 + М2 [sin (а - </?)|}, о"2 = {0 < а < ViV2 + М2 |sin {а-ф)\ <p<p(a)j, cr3 = {<Р < а < §, 0 < р < y/W+Ш|sm(а - </?)[}, р(а) = \/N2 + М2 sin (а + Л = ££ (¿а,р (—ЛГ, М) -В = (Ьа, (-iV, М) - у, = arctg £

Поскольку прямоугольник D обладает двойной осевой симметрией (относительно осей ОХ и ОУ), то и функция тп(а,р) будет обладать симметрией Таким образом, справедливо следующее утверждение

Утверждение 1. Для меры автоморфных областей выполняются следующие равенства т(а,р) ~ т{—а р) и т(а,р) — тп(т: — а,р)

Это утверждение позволят восстановить значения меры на всем промежутке а € [—7г,7г) Полученные выше формулы относятся к случаю, когда М < N, то есть «горизонтальный» размер изображения больше (точнее, не меньше), чем «вертикальный» Следующая теорема устанавливает связь между выражениями для каждого из этих случаев и тем самым окончательно решает задачу определения меры автоморфной области для случая прямоугольника

Теорема 2 Значения меры тп (а, р) для случая М > N определяются выражением m.M>N {се,р, N, М) = mM<N (f — а>Р> М, N)

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

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

Теорема 3 (о структуре автоморфной области). Пусть G = {gi, §2, ,дк} ~ некоторая конечная группа порядка N, действующая на множестве R2, и D С

N

К2 Тогда множество А = f~) gtD будет максимальной автоморфной областью

i=i

относительно действия данной группы

Утверждение 2. Пусть = (Раир), С?2 = {^аг,р) и С = Ст и Сг- Тогда махси мальная автоморфная область Атах относительно группы б, действующей нс^ области О, описывается выражением Атах = Ппег [Ра2-п(а1-а2)1) П Т2п(

Вторая глава посвящена исследованию симметрии плоских контуров. В начале главы дается общая постановка задачи анализа симметрии контура в непрерывном случае. Вводятся определения вращательно и отражательно симметричных контуров. Контур г(£), Т £ [0,Ь] называется отражательно симметричным относительно прямой Ьаф, если для любого £ 6 [0, Ь] найдется такое значение £*, £* ф что выполняется равенство г(£) = г(£*). Контур г(£), £ 6 [0,1/], называется вращательно симметричным относительно точки х, если для любого £ е [0, Ь] найдется такое значение £*,£* ф t, что Та,хг(£) = г(£*). 1

Доказываются теоремы о параметре отражательной и вращательной симмет] рии контура.

Теорема 4. Пусть г(£) - гладкий замкнутый натурально параметризованный контур без самопересечений, заданный на промежутке [О, Ь], где Ь - длина контура. Для того чтобы данный контур был отражательно симметричным от] носительно прямой Ьаф, необходимо и достаточно, чтобы существовала такая константа С, что для всех £ € [О, Ц выполняется равенство Рарг (£) = г (С — £).

Теорема 5. Пусть г(£) - гладкий замкнутый натурально параметризованный контур без самопересечений, заданный на интервале [0, Ц, где Ь - длина кон-ь тура. Для того, чтобы данный контур был вращательно симметричным om.no] сителъно точки х необходимо и достаточно, чтобы существовала такая кощ станта С, что для любого £ выполнялось Тах г(£) = г (С + £).

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

Следствие 1. При выполнении условий теоремы 4 контур г(£) отражательно симметричен тогда и только тогда, когда для любого £: ^(1,рг(£) = г(2£о — £), где £0 - значение параметра, соответствующее точке пересечения контура с осью отражательной симметрии Ьаф.

Следствие 2. Пусть группа вращений имеет конечный порядок п. При выполнен нии условий теоремы 5 контур г(£) вращательно симметричен тогда и только тогда, когда для любого £ выполняется Тахг(£) = г{кЬ/п+ Ь),к 6 Ъ.

|

Рис. X. График значений меры автоморф-нои области прямоугольника для различных значений аир

Для того, чтобы распространить теорию на случай неидеальных, в частности, защумленных контуров, понятие симметрии контуров обобщается путем введения С-инвариантных признаков изображений и контуров (З-инвариантным признаком контура будем называть функцию [О, Ь] —* М, инвариантную относительно группы преобразований С? точек плоскости, то есть такую функцию а/(х), что для любого д из группы й справедливо и> (Г) = ш (£), где параметр V определяется из условия г(£*) = рг(£) Выбор инвариантных признаков определяется группой С или типом анализируемой симметрии В реальных задачах, связанных с обработкой цифровых изображений, сложно достичь абсолютно точного выполнения этого условия, поэтому обычно используют функции признаков, удовлетворяющие условию инвариантности только для некоторых компонент аффинного преобразования В контексте обнаружения симметрии наибольший интерес представляют преобразования отражения и вращения

При обобщении понятия симметрии контуров ключевую роль играет определение понятия ошибки согласования точек контура, которое дает количественную меру несоответствия «симметричных» точек на предположительно симметричном контуре Ошибкой согласования точек контура I 6 [О, Ь] будем называть функцию в) = [ш(г(£)) — ш(г(в))]2 Для конструктивного определения параметров С вводится следующий функционал £(С) = ^ Е{Ь, С ± £) сИ Из определения ошибки согласования следует, что в идеальном случай его нули будут находиться в точках С, являющихся параметрами симметрии контура г(£) При анализе оцифрованных изображений из-за влияния шумов, ошибок дискретизации и погрешностей задания контуров равенство нулю данного функционала для значений параметра С, соответствующих осям симметрии, как правило, не достигается Однако соответствующие значения будут достаточно малыми Поэтому для определения параметров симметрии контура требуется определить значения С, в которых достигаются локальные минимумы данного функционала В работе показывается, что задача анализа отражательной и вращательной симметрии контура сводится к определению локальных максимумов автокорреляционной функции контура /г(С) = /с± Ь)сИ

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

Третья глава является центральной главой диссертационной работы - в ней исследуются вопросы симметрии полутоновых изображений Изображение /(х), заданное в области £>, будем называть симметричным относительно группы С в автоморфиой области Б а С I). если оно не меняется при действии данной группы преобразований, то есть для любых д € С? и х € Ид выполняется I (<?х) = I (х) Обозначим через Ыв множество всех С-симмстричпых в фиксиро-

ванной автоморфной области Dq изображений Нетрудно видеть, что Us является подпространством линейного пространства изображений U Обозначим через Ыа ортогональное дополнение К, к подпространству U, то есть Ua3 = U.^ Оно такж является подпространством пространства U, причем Us®Uas = U Следовательно любое изображение I £U может быть единственным образом представлено в вид I = 1„ + 1ая, где I, £ Ua, Ias 6 Uas При этом изображения Is и Ias являются oj тогональными (в смысле введенного в U скалярного произведения) и называютс симметричной и антисимметричной составляющими изображения I

На основе известной в теории представления групп теоремы об проекции векто ра на инвариантное подпространство вводится определение алгебраической мерь симметрии Алгебраической мерой симметрии Mg{I) изображения I относительно заданной группы преобразований G или мерой G-симметричности называете норма проекции I на инвариантное подпространство Ы3

Анализ изображения осуществляется путем перехода в пространство призна ков и сравнения векторов признаков ключевых точек Произвольная скалярная функция ш(х), заданная в D и зависящая от изображения /(х), называется при знаком этого изображения Функцией признаков изображения называется вектор ная функция <1>(х), ставящая в соответствие точкам плоскости К2 вектор призна ков й(х) = (wi(x), ,шп(х))Т, где wt(x) - какие-то инвариантные относительн некоторой группы преобразований скалярные признаки изображения I Выбо тех или иных инвариантных характеристик ш,(х) в значительной степени опреде ляет качество работы методов анализа симметрии

В работе исследуются инвариантные характеристики, определенные следующим образом Пусть х - некоторая точка изображения, а -Вд(х) - ее окрестность радиуса R Рассмотрим множество векторов градиента изображения в окрестности Вц(х) Пусть A(z) — grad/(z) = (Ai(z), Дз(г))т - вектор градиента интенсивности изображения в точке z € Дй(х), то есть Ai(z) = J^-j , A2(z) =

1 !z I z

Обозначим через <p(z) угол, образуемый вектором градиента A(z) с осью абсцисс Очевидно, что <p(z) = arctg Определим угол 7(х) = arctg ^Z^l ■ гДе (¿i,¿2) - координаты центра «масс» окрестности Вд(х) Этот угол будем называть углом наклона окрестности Вд(х) Разобьем промежуток [0,2тг) на N промежутков к = 0,1,2, , N — 1, где а^ — Цг Обозначим через

А)t(x) = {z | <p(z) — 7(х) 6 [q^, a^+i)} множество точек окрестности -Вд(х), в которых угол между градиентом изображения и углом наклона окрестности принадлежит к-му промежутку Тогда компоненты вектора признаков можно записать в следующем виде и>к{х) = ff ]|A(z)|| dz Определенные таким образом инвариантные характеристики являются инвариантными относительно сдвига, вращения и частично инвариантны относительно изменения освещенности сцены и изменения угла обзора

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

признаков \¥ Мерой сходства точек изображения 1(х) относительно векторной функции признаков ш называется интегрируемая в области Б х Б функция рч Б х Б —> [0,1], удовлетворяющая следующим условиям 1) для любых Х1,Х2,Хз,Х4 £ Б из того, что выполняется неравенство Цс^Х;) — ш(х2)|| > \\и{хз) ~ ^(х4)(|, следует, что р(хьх2) < /-¿(х3,х4), причем ¿¿(хьх2) = р(х3,х4) в том и только том случае, если Ца^х^ — ш(хг)|| = |[ш(хз) — ш(х4}|| (монотонное убывание по расстоянию), 2) если ||и(х!) — ш(х2)|| = 0, то /¿(х 1,х2) = 1 (нормиро-ванность), 3) если (хх, х2) £ Б х Б, то ц(х\, х2) не определена Этому определению удовлетворяет достаточно широкий класс функций Конкретными примерами поточечных мер сходства являются следующие

МХ1,х2) = „ ' ■„, и /фсьх2) = 1 - И.О-Ч.у

' Нх1)-и(х2)|| +1 ШН ||И(Х[) —и(х2)

Х!,Х2еО

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

у! + ао/^-У14"1 = 0, т = 0,1, ,¿=1,2, , а0 > 0, /г(0) = 1, где р = \\и) (хх) — ш (х2)|| - расстояние между точками в признаковом пространстве, ар, — р,(р) - поточечная мера сходства Решения данного уравнения позволяют разделить меры поточечного сходства на два семейства

экспоненциальное ц(хих2) = е~а|1ш(х1)_ы(х2)||к, а > 0, к - 1,2, ,

гиперболическое /х(х1,х2) — ^а ||о;(х1) - а;(х2)||': +1^ ™ ,а > 0, к,т 6 N В данной главе приводится также психофизическое обоснование полученного дифференциального уравнения

Поточечная мера сходства продолжается на орбиты группы (7 Мерой сходства точек орбиты Сх, |(7х| ф 1, называется функция /*(<?*) = |Ох|(|Ох|-1) 2 м(хьх2)

Х1,х2бСх

Х1^Х2

Теорема 6. Мера сходства точек орбиты Сх, |Сх| ф 1, выражается формулой Д (Сх) = Щ5П51Щ ^ ~ |С|-|Я(х)|

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

Е £•»»№) к=1 хк к=1

Исследуются базовые свойства введенной меры сходства

Утверждение 3 Мера сходства множества удовлетворяют условию нормировки 0 < ц(СХ) < 1, причем равенство р,(СХ) = 1 достигается в том и только в том случае, если /л (Сх) = 1 для всех точек х € X

Утверждение 4 Пусть Х\ и Хг - два подмножества из автоморфной отно тельно группы <3 области, причем Х\ п Х^ — 0 Кроме того, предположим, ч множество X = Хх и Х2 не содержит различных элементов, принадлежат, одной и той же орбите Тогда ц (йХ) = ^^Ц {вХх) + (ОХ2)

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

Непрерывным преобразованием отражательной симметрии изображени по ограниченной области Б будем называть преобразование вида

= щщ По Ч (*> ^а,Рх) йх, где т [Б) - мера автоморфной области!)

Непрерывным преобразованием вращательной симметрии изображения I ограниченной области Б будем называть преобразование вида

с) = £ Ц0 V (х, 71сх) ¿х;

где п - порядок группы вращений

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

Утверждение 5. Пусть изображение /(х) - имеет некоторую ось симметр с параметрами (<*о, Ро) Тогда в точке («о, ро) достигается локальный максим^ непрерывного преобразования симметрии

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

Исследуются свойства непрерывного преобразования симметрии изображен при некоторых обратимых аффинных преобразованиях Пусть А . К2 —» К2 -ратимое аффинное преобразование плоскости К2 вместе с заданными на нем з чениями изображения I (х) Это значит, что если и = Ах, то получаемое нов изображение 1а (и) удовлетворяет условию 1а (и) = 1а (^х) = I (х) Если о значить через р.а меру сходства точек преобразованного изображения 1а (х) , из последнего равенства следует, что ¡1а (Ах, ЛРарх) = ц (х, Рау~х) Данное венство позволяет получить ряд полезных свойств непрерывного преобразован симметрии при некоторых аффинных преобразованиях изображения

Теорема 7 (о гомотетии) Пусть 1Т - гомотетичное преобразование изобраэ/ ния I (х) с коэффициентом г,г>0,ше 1гх = гх Тогда 5(а,р)[7/г1 = 5(а,£) [/]

Теорема 8 (о вращении). Пусть Т7 - преобразование вращения изобраэюен I (х) на угол 7 против часовой стрелки Тогда 5 (а,р) = й (а - 7,р) [/]

Следствие 3. Если Ir - гомотетия и г < 0, то S (а,р) [Iir\ = S [а — -к, ^j [/], где (а — 7г) - главное значение угла.

Теорема 9 (о смещении). Пусть Ад - преобразование, состоящее в смещении изображения на вектор А, то есть Адх = х 4- Д. Тогда S(a,p)[IAb} = S(a,p~(A,na))[I}.

Теорема 10 (об отражении). Пусть FpA - преобразование ортогонального отражения изображения I (х) относительно оси Lgi?. Тогда

S(a,p) [i>J = 5(20 - а,2?cos (р - а) +р) [7].

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

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

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

Снижая порог выбора информативных точек, в пределе все точки изображения формально становятся информативными и дискретное преобразование стремится к непрерывному преобразованию симметрии. В ЭТОМ случае пред- Рис 2. Пример обнаружения осей отпражателъ-ложепный алгоритм будет стано- ной симметрии вится все более вычислительно затратным и в пределе превратится в алгоритм, непосредственно реализующий вычисление меры симметрии.

а) дискретное преобразование симметрии

б) исходное изображение и обнаруженные оси отражательной симметрии

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

На рисунке 2 представлен пример определения параметров отражательн симметрии фотореалистичного изображения

В данной главе предлагается метод количественной оценки результатов рабо алгоритмов обнаружения симметрии изображений на основе введенного понят расстояния между параметрическими группами Для тестирования алгоритм обнаружения симметрии была создана база изображений Описаны особенное использования разработанных приложений Программы и база изображений ступны по адресу www lampai tsure ru/research/practics/symmetry/

основные результаты

При решении поставленных в диссертационной работе задач получены еле ющие новые теоретические и прикладные результаты

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

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

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

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

список публикаций по теме работы

1 Горбань, А С Описание и обнаружение аффинных симметрий изобра ния /АС Горбань // Материалы VII Всероссийской научной конференц

студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», -Таганрог: Из-во ТРТУ, 2004, с. 230-231.

2. Горбань, A.C. Обнаружение отражательной и вращательной симметрии контура / A.C. Горбань // Сборник докладов III Всероссийской научной конференции молодых ученых и аспирантов "Новые информационные технологии. Разработка и аспекты применения", -Таганрог:Из-во ТРТУ, 20G4, с. 118-123.

3. Горбань, A.C. Аналитическое решение задачи обнаружения аффинных симметрии контура / A.C. Горбань // Всероссийский конкурс среди учащейся молодежи высших учебных заведений Российской Федерации на лучшие научные работы по естественным наукам: Тезисы научных работ. Саратов: Сарат. гос. техн. ун-т, 2004, с. 30-31.

4. Горбань, A.C. Аналитическое решение задачи обнаружения аффинных симметрии контура / A.C. Горбань // Федеральная итоговая научно-техническая конференция «Всероссийского конкурса на лучшие научные работы студентов по естественным, техническим наукам (в области высоких технологий) и инновационным научно-образовательным проектам». Материалы итоговой конференции - М.: МИЭМ, 2004, с. 315-319.

5. Горбань, A.C. Использование инвариантных характеристик при обнаружении вращательных и отражательных симметрий контура / A.C. Горбань // Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий. Т.1. - Херсон: Изд. Херсонского морского института, 2005, с. 69-71.

6. Горбань, A.C. Использование интегральных инвариантов для обнаружения аффинных симметрий контура / A.C. Горбань, А.Н. Каркищенко /'/ Интеллектуальные и многопроцессорные системы-2005 // Материалы Международной научной конференции. Т.З, -Таганрог: Изд-во ТРТУ, 2005, с. 132-136.

7. Горбань, A.C. Дифференциальные и интегральные и инварианты в задачах обнаружения аффинных симметрий контура / A.C. Горбань, А.Н. Каркищенко // Искусственный интеллект. Донецк, Украина, Изд-во ДонГИИИ «Наука i ocBiTa», 2005, № 4, с. 682-688.

8. Горбань, A.C. Методы обнаружения отражательной симметрии полутоновых изображений / A.C. Горбань // Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий. Т.1. - Херсон: Изд. Херсонского морского института, 2006, с. 57-61.

9. Горбань, A.C. Эффективная численная реализация метода обнаружения симметрии полутоновых изображений / А С Горбань. А.Н. Каркищенко // «Практика и перспективы развития партнерства в сфере высшей школы»: Материалы восьмого научно-практического семинара, г. Донецк, 17-20 апреля 2007 г. В 3-х томах. Т.З. - Донецк, ДонНТУ, 2007, с. 65-70.

10. Горбань, A.C. Выделение высокоуровневых признаков изображений в задачах цифровой обработки сигналов / A.C. Горбань, А.Н. Каркищенко // Материалы Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Изд-во ТТИ ЮФУ, 2007. с. 96-99.

11. Горбань, A.C. Определение областей отражательной симметричности по тоновых изображений / A.C. Горбань, А.Н. Каркищенко // Сборник т дов III Международной научной конференции «Интеллектуальные систег принятия решений и прикладные аспекты информационных технолог: (ISDMIT'2007) 14 - 18 мая 2007 г., г. Евпатория, с. 323-327.

12. Горбань, A.C. Инвариантные характеристики в задачах обнаружения с метрии изображений / A.C. Горбань, А.Н. Каркищенко // Вторая Меж народная конференция «Системный анализ и информационные технологи САИТ-2007 (10 - 14 сентября 2007г., Обнинск, Россия): Труды конфер< ции. В 2 т. Т. 2. - М.: Изд-во ЛКИ, 2007, с. 210-212.

13. Горбань, A.C. Поиск портретных изображений по содержанию / A.B. Гон1 ров, А.Н. Каркищенко, А.Е. Лепский, A.C. Горбань // Интернет-математи 2007: Сборник работ участников конкурса. -Екатеринбург: Издательс Урал, ун-та, 2007. с. 56-64.

14. Горбань, A.C. Распознавание лиц на изображениях с низким разреше / A.B. Гончаров, A.C. Горбань // Труды российской конференции mojil,, ученых по информационному поиску в рамках RuSSIR 2007. Екатеринбу 5-12 сентября 2007г., с 5-15.

15. Горбань, A.C. Моделирование и классификация поточечных мер сходс / A.C. Горбань, А.Н. Каркищенко // Труды международной конферен AIS/CAD '08, Таганрог, 2008.

Личный вклад автора в работах, опубликованных в соавторстве: [6,7,12] - иссле; вание инвариантных характеристик контура и программная реализация, [9-11 программная реализация метода и проведение численных экспериментов, [13,14 применение методов анализа симметрии для оптимизации алгоритмов обнару ния лиц, [15] - исследование свойств модели симметрии цифровых изображен

Работы в изданиях, входящих в «Перечень ведущих научных жу налов и изданий, выпускаемых в Российской Федерации», утвержде ный ВАК.

1. Горбань, A.C. Аффинные свойства непрерывного преобразования симм рии / A.C. Горбань, А.Н. Каркищенко // Вестник Ростовского государств ного университета путей сообщения. -Ростов н/Д, РГУПС, № 4(28), 2007, 117-124.

2. Горбань, A.C. К определению мер сходства полутоновых изображений / А. Горбань, А.Н. Каркищенко // Известия ЮФУ. Технические науки, Таганр №4, 2008.

Личный вклад автора в работах, опубликованных в соавторстве: [1,2] - иссле вание свойств модели симметрии цифровых изображений.

К , - л .

Типография ТТИ ЮФУ, ГСП 17А, Таганрог, ул. Энгельса, 1. Заказ №_, Тираж 100 экз.

Список обозначений

Введение

1 Исследование аффинных преобразований плоскости применительно к анализу симметрии

1.1 Основные определения.

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

1.3 Автоморфные области.

1.3.1 Определения.

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

1.3.3 Групповые свойства автоморфных областей.

1.4 Выводы.

2 Симметрия плоских контуров изображения

2.1 Анализ симметрии непрерывного контура.

2.2 Анализ симметрии дискретного контура.

2.2.1 Дифференциальный метод обнаружения симметрии

2.2.2 Полулокальный метод обнаружения симметрии

2.2.3 Интегральный метод обнаружения симметрии

2.3 Выводы.

3 Анализ симметрии полутоновых изображений

3.1 Меры симметрии изображений.

3.2 Функции признаков изображений

3.2.1 Определение векторной функции признаков

3.2.2 Примеры функций признаков.

3.3 Меры сходства точек изображения.

3.3.1 Определение и примеры мер сходства точек изображения

3.3.2 Дифференциальное описание и классификация поточечных мер сходства.

3.4 Продолжение поточечных мер сходства на изображения

3.5 Непрерывное преобразование симметрии

3.5.1 Отражательная симметрия.

3.5.2 Вращательная симметрия.

3.5.3 Связь непрерывного преобразования симметрии с алгебраической мерой симметрии и мерой симметрий для контуров.

3.5.4 Аффинные свойства непрерывного преобразования симметрии

3.5.5 Разбиение области определения изображения па автоморфные подобласти

3.6 Выводы.

Разработка эффективных численных алгоритмов па основе преобразования симметрии и вычислительные эксперименты

4.1 Численный алгоритм обнаружения отражательной симметрии

4.2 Численный алгоритм обнаружения вращательной симметрии

4.3 Оценка качества методов анализа симметрии.

4.4 Выводы.

Симметрия - одно из наиболее фундаментальных свойств природы, которое является в некотором смысле синонимом понятий гармонии, порядка, закона. Будучи таким важным понятием, симметрия нашла свое отражение практически во всех областях научного знания. Несмотря на кажущуюся простоту, симметрия является очень сложным предметом для изучения, поэтому долгое время она теоретически исследовалась только как философская категория. Однако под влиянием работ Феликса Клейна и Софуса Ли утвердилось понимание того, что симметрия - это, в первую очередь, объединяющее понятие для совокупности операций, сохраняющих определенные алгебраические или геометрические соотношения. Симметрия неразрывно связана с математическим понятием группы. В современной науке понятие симметрии наиболее широко используется в физике. С одной стороны, она играет вспомогательную роль при решении сложных задач в пределах уже известных законов природы, а с другой, - выступает как принципиально важный инструмент при построении моделей новых явлений [1, 2].

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

Исследование вопросов восприятия симметрии человеком началось еще в 1886 году [4], и в настоящее время в данной области уже достигнуты значительные результаты [5, 6, 7]. В частности, было установлено, что для человека, также как и для живых организмов, наиболее значимыми являются вертикальные и горизонтальные отражательные симметрии. Показано, что человеческий мозг часто исходит из предположения о симметричности видимых объектов, когда необходимо интерпретировать размытые или неполные визуальные данные. Основной целью, которую ставят перед собой исследователи в данной области компьютерного зрения, является создание метода, который бы оценивал симметрию изображения схожим с человеком образом.

В основе определения цифрового изображения лежит определение эле-'/ мента изображения - пикселя. Каждый пиксель задается своими координатами в пределах изображения и интенсивностью света. Опустим детали -представления изображения и цветовых пространств - для нас важным является только тот факт, что изображение представимо в виде множества4 пикселей. Задачу анализа симметрии изображения, таким образом, можно сформулировать как задачу определения конкретной конечной группы, действующей на множестве элементов исследуемого изображения. Однако такая формулировка является малопригодной для решения практических задач анализа цифровых изображений. Поскольку наиболее «значимыми» для человека являются группы симметрий отражения, вращения и трансляции, то задача анализа симметрии изображения обычно формулируется как задача отыскания параметров какой-либо фиксированной группы симметрий. Для группы отражений такими параметрами являются параметры оси отражения. Для группы вращений - центр вращения и порядок группы.

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

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

Задача анализа симметрии изображений тесно связана с задачей сегментации изображенных объектов. В работе [8] предлагается метод, использующий информацию о симметрии изображения для сегментации объектов с последующим улучшением результатов анализа симметрии. В [9] симмет-5 рия используется для восстановления невидимых на изображении частей симметричных объектов. Основываясь на фундаментальных принципах,' устанавливающих связь между симметрией и проективными преобразованиями, в [10] разработан прототип системы для автоматической сегментации объектов в трехмерном пространстве по их двумерным изображениям. В работах [11, 12] теми же авторами предлагается метод для восстановления трехмерных сцен на основе анализа симметрии изображения. В своей диссертационной работе Филип Шмид [13] исследовал возможность использования симметрии для сегментации изображения применительно к дерматоскопическим изображениям.

В работе [14] информация о симметрии используется для отслеживания движения технических объектов, в [15, 16] - для распознавания движений человека и животных. Симметрия движений в этих работах определяется при помощи обобщенного оператора симметрии и используется для распознавания походки. Приводятся факты, свидетельствующие о том, что человеческая походка является симметричным шаблоном движения. Показывается, что свойства симметрии походки являются уникальными для каждого человека и животного.

Значительное число работ в компьютерном зрении посвящено контекстному поиску изображений. Ключевым моментом при реализации любого вида поиска является составление индекса базы данных. Индексирование баз данных графической информации представляет собой особенно трудную задачу. В работе [17] предлагается метод для автоматического выделения глобальных характерных особенностей изображений, таких как контуры и параметры движения. Одним из основных признаков, используемых в данной работе, является информация о локальной симметрии. Симметрия также используется для определения характерных точек панорамных изображений применительно к задаче движения роботов-[18]. ^

Одной из наиболее широко исследованных прикладных задач обработки изображений является проблема распознавания лиц [19, 20]. В этой области также существуют методы, основанные на использовании информации о симметрии изображений [21,22, 23]. Так, например, в работе [24], посвященной автоматической аутентификации лиц при помощи ЗБ-поверхностей, в основу построения модели лица по фотоснимкам положено определение соответствующих характерных точек лица при помощи информации о его симметрии. В этой работе авторы используют вертикальную отражательную симметрию для определения угла наклона лица, что в значительной степени увеличивает скорость определения соответствия лиц. В работе [25]

Reisfeld,Wolfson и Yeshurun разработали обобщенный детектор симметрии и применили его для локализации особых точек изображений и, в частности, для локализации признаков лица, таких как глаза и рот.

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

В задачах анализа изображений лиц человека симметрия используется для определения воспринимаемой привлекательности человека. В работе [27] проведено исследование связи симметричности мужского лица с воспринимаемым состоянием здоровья кожи лица. Показано, что более симметричное лицо воспринимается как более здоровое, чем несимметричное. *■ Показывается, что состояние здоровья кожи лица человека коррелирует с его внешней привлекательностью. •' - "

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

Традиционно выделяют два основных класса задач анализа симметрии изображений: определение меры симметрии [28, 29] и определение осей симметрии или параметров симметрии [30, 31].

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

Существуют различные подходы к определению непрерывной меры симметрии [29, 32, 33]. Метод в [34] измеряет непрерывную степень симметрии по отношению к конкретной группе. Для измерения непрерывной меры симметрии в работе [28] вводится дескриптор отражательной симметрии, представляющий собой меру отражательной симметрии для произвольных вексельных моделей относительно всех плоскостей, проходящих через'< центр масс модели (даже если они не являются плоскостями симметрии). Преимущества такого дескриптора формы состоят в том, что он опреде-1 лен на каноническом множестве (сфере) и описывает глобальные свойства-ЗБ-формы.

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

По способу представления данных существующие алгоритмы обнаружения симметрии делятся на векторные, использующие контурное задание изображения [35, 36, 37, 38], и растровые, в которых применяется полутоновое представление [32, 31]. Использование информации об углах и линиях при анализе изображения (в случае векторных алгоритмов) является более предпочтительным, так как для человеческого восприятия-симметрия углов является более значимой, чем симметрия областей. Однако общим недостатком векторных алгоритмов является то, что задача выделения качественного контура является сложной, а иногда практически неразрешимой задачей.

При анализе изображения-как растра наиболее распространенный подход- это разложение изображения целиком или его частей по некоторому базису и:последующий анализ коэффициентов этого разложения. Чаще всего для этих целей используется, дискретное преобразование Фурье, однако одним из основных недостатков его использования является плохая локализация в пространстве. Для решения этой проблемы применяется оконное преобразование Фурье; Однако в современных методах исследователи все* больше стремятся использовать вейвлет-преобразование. Помимо хорошей-частотной локализации оно также локализовано и в пространственной области. При анализе симметрии изображений это требование является определяющим, так как основные задачи анализа1симметрии состоят не только в том; чтобы определить, симметрично изображение или нет; но и в том, чтобы по возможности попытаться определить области и параметры симметричности. Примером применения теории вейвлетов для решения задачи анализа симметрии является работа [39].

Выбор метода анализа симметрии существенно зависит от типа представления данных. Насколько известно автору, методов, которые можно использовать как для векторных, так и для растровых данных, на момент написания; данного диссертационного исследования не существует.

Основываясь на природе признаков, извлекаемых из формы объекта, существующие методы можно условно разделить на два основных подхода: глобальный и локальный. В рамках глобального подхода рассматривают внутреннюю часть контура и затем ищут оси искаженной симметрии [40, 41]. В рамках локального - используют локально определенные характерные признаки, например, инварианты, вычисляемые в отдельных точках кривой [3, 28], и методы, которые статистически сравнивают пару точек контура [42]. Для преодоления некоторых недостатков как глобальных методов, так и локальных, в работе [43] предложены интегральные инварианты, основанные на групповой инвариантной параметризации. Показано, что, как и можно было ожидать, интегральные инварианты остаются работоспособными при перекрытии частей объекта и являются менее чувствительны к шуму по сравнению с дифференциальными инвариантами. Поэтому при создании универсального метода для анализа симметрии^ важна возможность тонкой параметрической настройки для решения конкретного класса практических задач анализа симметрии изображений. /

В том случае, когда отражательно симметричный объект наблюдается в удаленной перспективе, в плоскости изображения объект претерпевает*1 аффинные преобразования, которые приводят к искаженной симметрии (skewed symmetry). Обнаружение искаженной симметрии и ее анализ также являлись темами многих работ [35, 41, 40]. В [42] предлагается метод обнаружения осей симметрии, базирующийся на свойствах введенных так называемых обобщенных комплексных моментов. В этой работе вводится понятие симметричной и асимметричной энергии изображения, а задача обнаружения симметрии формулируется как задача минимизации функционала асимметричной энергии.

Большая доля существующих методов анализа симметрии базируется на так называемых преобразованиях симметрии [25, 44, 45, 14, 46, 47, 48,

49]. В основе практически всех преобразований симметрии лежит идея перехода от исходного преобразования к некоторому фазовому пространству параметров. Параметрами отражательной симметрии, например, являются параметры прямой - оси симметрии. В работах [44, 45] преобразование симметрии построено на основе преобразования Хау - одного из классических в области компьютерного зрения метода для определения параметров прямых на изображении. В [50, 51] используется локальная фазовая информация для определения локальной симметричности изображения. Множество преобразований симметрии не так разнообразно, как может покажется на первый взгляд. Наиболее интересными примерами преобразований симметрии являются преобразование отражательной симметрии (ПОС) [48] и обобщенное преобразование симметрии (ОПС) [25]. Для фиксирован— ных изображения и оператора отражения значение ПО С равно расстоянию от изображения до его проекции на пространство симметричных изображений. Значения ОПС определяются алгоритмически: для каждой точки изображения вычисляется так называемая величина симметричности. Величина симметричности точки равна сумме «симметричностей» всех пар точек изображения, для которых данная точка является геометрическим центром. Чем больше эта величина, тем симметричней изображение в данной точке. Практически все существующие преобразования симметрии являются «улучшенными версиями» этих двух преобразований. Почему для решения одной задачи определения параметров симметрии изображения существуют два класса преобразований, использование которых дает сходный результат? Общим недостатком описанных выше методов также является то, что они не позволяют ответить на вопрос: что будет с симметрией изображения, если оно подвергается некоторым изменениям? Как изменится мера симметрии для заданных параметров при действии некоторых аффинных преобразований?

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

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

Предлагаемый в диссертационной работе новый подход основан на введенном ранее автором [31, 52] непрерывном преобразовании симметрии отображающем изображение в фазовое пространство параметров симметрии (осей симметрии и центров симметрии). Этот подход обладает большой'*-общностью, так как позволяет показать, что многие методы, предложенные в опубликованных научных работах, являются частным случаем данного преобразования. В частности, в настоящей диссертационной работе показывается, что ПОС и ОПС, два на первый взгляд «непохожих» преобразования, эквивалентны.

Существующие работы по анализу свойств симметрии изображений можно условно разделить на два больших практически не пересекающихся класса: сугубо теоретические исследования симметрии как группового свойства изображений [53] и методы, позволяющие количественно определить степень симметричности того или иного объекта [8, 54, 55, 14]. Данная работа может послужить своеобразным «мостом» между этими двумя классами работ. В ней аксиоматически определяется понятие схожести и показывается, как при помощи аппарата теории представлений групп получить количественные оценки симметричности изображений.

Суть предлагаемого подхода состоит в следующем.

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

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

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

17 симумов по параметрам несобственного интеграла.

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

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

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

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

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

В связи с поставленной целью необходимо решить следующие задачи:

1) исследовать аффинные преобразования плоскости применительно к задачам анализа симметрии изображений;

2) разработать математический аппарат для исследования свойств симметрии непрерывных функций двух переменных;

3) разработать и исследовать эффективный в вычислительном плане метод определения параметров вращательной и отражательной симметрии контуров и изображений;

4) практически реализовать и экспериментально исследовать полученные методы.

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

Материалы диссертационной работы распределены по главам в соответствии с перечисленными задачами.

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

Глава 2 посвящена исследованию симметрии плоских контуров. Одним из наиболее распространенных подходов к анализу изображений является исследование формы изображаемого объекта. Контуры объекта во многом описывают его форму. В начале главы дается общая постановка задачи анализа симметрии контура в непрерывном случае. Вводятся определения вращательно и отражательно симметричных контуров. Доказывается теорема о параметре симметрии контура. Данная теорема является основой для построения методов определения параметров как отражательной, так и вращательной симметрии контуров. Дается определение С-инвариантных признаков изображений и контуров. Предлагается метод определения параметров симметрии контура на основе введенного понятия ошибки согласования точек контура. Показывается, что задача определения параметров симметрии контуров сводится к определению точек локальных максимумов'"' автокорреляционной функции. Основной раздел второй главы посвящен г анализу симметрии дискретных контуров. В нем приводится обзор суще-"1 ствующих методов представления и предварительной обработки дискрет ных контуров. Ключевым этапом при разработке метода анализа контура5*-' является выбор аффинно-инвариантной характеристики. В данной главе рассматриваются методы, основанные как на дифференциальных инвариантах, так и на интегральных. Анализируются их недостатки и преимущества, а также предлагается полулокальный метод, сочетающий в себе преимущества обоих методов.

Глава 3 является центральной главой диссертационной работы - в ней исследуются вопросы симметрии полутоновых изображений. Вводится понятие С-симметричного изображения. Симметрия понимается в самом общем смысле - изображение считается симметричным, если оно не меняется при действии некоторой группы преобразований. Если действующая группа является группой отражений, то изображение считается отражательно симметричным, если конечной группой вращений, то вращатель-но симметричным. Поскольку в реальной жизни идеально симметричные изображения встречаются крайне редко, то вводится понятие меры симметрии. Показывается, что пространство изображений представимо в виде прямой суммы двух подпространств: пространства симметричных и пространства антисимметричных изображений. Мера симметрии изображения вводится как норма проекции изображения на симметричное подпространство изображений. Анализ изображения осуществляется путем перехода в пространство признаков и сравнения векторов признаков ключевых точек.

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

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

На защиту выносятся следующие основные результаты и положения:

- новое понятие автоморфных областей и оценки их мер;

- понятие непрерывного преобразования симметрии;

- новые методы обнаружения произвольных симметрий контурных объектов и полутоновых изображений;

- связь предлагаемых методов анализа симметрии изображений с известными методами;

- алгоритмы обнаружения вращательной и отражательной симметрии контуров и изображений.

Практические и теоретические результаты диссертации использованы научно-исследовательских проектах РФФИ:

1) №07-07-00067 «Разработка обобщенной математической модели анализа симметрии изображений на основе непрерывного преобразования симметрии»;

2) №08-07-00129 «Исследование многомасштабного знакового представления образов в задачах анализа биометрической информации при разработке систем информационной безопасности».

Основные результаты диссертационной работы докладывались на:

- VII Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2004) [29];

- III Всероссийской научной конференции молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2004) [36];

- Федеральной итоговой научно-технической конференции «Всероссийского конкурса на лучшие научные работы студентов по естественным, техническим наукам (в области высоких технологий) и инновационным научно-образовательным проектам» (Москва, 2004) [37];

- Международной научной конференции «Интеллектуальные и многопроцессорные системы-2005» (Таганрог, 2005) [57];

- II Международной научной конференции «Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий» (г. Евпатория, 2006) [31];

- Восьмом научно-практическом семинаре «Практика и перспективы развития партнерства в сфере высшей школы» (Донецк, 2007) [58];

- Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2007) [59];

- III Международной научной конференции «Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий» (г. Евпатория, 2007) [60];

- Второй Международной конференции «Системный анализ и информационные технологии» (Обнинск, 2007) [52]; ?

- Международной конференции по системам искусственного интеллекта (AIS/CAD '08) (Дивноморское, 2008) [61]. :

По теме диссертации опубликовано 17 работ, из них две работы в изданиях, входящих в «Перечень ведущих научных журналов и изданий, вы- i пускаемых в Российской Федерации», утвержденный ВАК.

Объем и структура диссертационной работы. Диссертационная работа состоит из введения, четырех тематических глав, заключения, списка литературы и приложений. Общий объем основного текста - 166 страниц, включая 40 рисунков. Список литературы изложен на 13 страницах и содержит 100 наименований.

4.4 Выводы

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

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

2) Разработаны алгоритмы, реализующие предложенные в диссертационной работе методы анализа симметрии.

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

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

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

Заключение

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

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

1) Введено и исследовано важное для вычисления меры симметрии понятие автоморфных областей изображения:

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

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

2) Исследована задача анализа симметрии контура:

- доказан ряд теорем, позволяющих конструктивно решать задачу отыскания параметров симметрии контура;

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

3) Предложена и исследована общая модель симметрии цифровых изображений:

- на основе введенной векторной функции признаков дано аксиоматическое определение поточечной меры сходства и получено дифференциальное уравнение, порождающее достаточно широкий класс таких мер;

- на основе построенной меры сходства произвольных областей получены непрерывные преобразования отражательной и вращательной симметрии;

- установлена связь непрерывного преобразования симметрии с существующими методами анализа симметрии. ^.Показано, что-последние являются его частными случаями;

- детально исследованы аффинные свойства непрерывного преобразования симметрии.

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

1. Голод, П. Математические основы теории симметрии / П. Голод, А. Климык. - Изд-во РХД, 2001.

2. Cheh, J. Algorithms for differential invariants of symmetry groups of differential equations journal / J. Cheh, P. J. Olver, J. Pohjanpelto. — 2008.

3. Symmetry from shape and shape from symmetry / L. van Gool, T. Moons, D. Ungureanu, E. Pauwels // Int. J. Rob. Res. — 1995. — Vol. 14, no. 5. — Pp. 407-424.

4. Mach, E. The analysis of sensations.— http: / /•www. marxists. org / reference/sub j ect/philosophy /works/ge/mach. htm.

5. Tyler, C. W. Theoretical issues in symmetry perception / C. W. Tyler // Spatial Vision. 1994. - Vol. 8. - Pp. 383-391(9).

6. Tyler, C. W. Empirical issues in symmetry perception / C. W. Tyler // Spatial Vision. 1994. - Vol. 8. - Pp. 383-391(9).

7. Bosco, T. Symmetry impedes symmetry discrimination / T. Bosco, L. Zili 11 Jour, of Vis. 2005. -12. - Vol. 5, no. 10. - Pp. 888-900.

8. Geiger, D. Segmenting by seeking the symmetry axis. — 1998.

9. Zabrodsky, H. Completion of occluded shapes using symmetry / H. Zabrodsky, S. Peleg, D. Avnir // CVPR93. 1993. - Pp. 678-679.

10. Geometric segmentation of perspective images based on symmetry groups / A. Yang, S. Rao, K. Huang et al. // ICCV '03: Proc. of the Ninth IEEE Int. Conf. on Comp. Vis. — 2003. — P. 1251.

11. On symmetry and multiple-view geometry: Structure, pose, and calibration from a single image / W. Hong, A. Y. Yang, K. Huang, Y. Ma // Int. J. of Comp. Vis. — 2004.- Vol. 60, no. 3.- Pp. 241265.

12. Symmetry-based 3-d reconstruction from perspective images / A. Y. Yang, K. Huang, S. Rao et al. // Comput. Vis. Image Underst. — 2005. Vol. 99, no. 2. - Pp. 210-240.

13. Schmid, P. Segmentation and symmetry measure for image analysis: Application to digital dermatoscopy / P. Schmid. — 1999.

14. Gesu, V. D. The discrete symmetry transform in computer vision. — 1995.

15. Hayfron-Acquah, J. B. Automatic gait recognition by symmetry analysis / J. B. Hayfron-Acquah, M. S. Nixon, J. N. Carter // Pattern Rec. Lett. 2003. - Vol. 24, no. 13. - Pp. 2175-2183.

16. Hayfron-Acquah, J. Recognising human and animal movement by symmetry / J. Hayfron-Acquah, M. Nixon, J. Carter // Image Proc., 2001. Proc. 2001 Int. Conf. Vol. 3. - 2001. - Pp. 290-293 vol.3.

17. Content-based indexing of image and video databases by global and shape features / E. Ardizzone, M. Casia, V. D. Ges'u, C. Valenti //In Proc. of the Int. Conf. on Pattern Rec. — 1996.

18. Zhang, J. Using symmetry as a feature in panoramic images for mobile robot applications / J. Zhang, K. Huebner // In Proc. Robotik. — 2002. — Vol. 1679.-Pp. 263-268.

19. Гончаров, А. Распознавание лиц на изображениях с низким разрешением / А. Гончаров, А. Горбань // Труды российской конференции молодых ученых по информационному поиску в рамках RuSSIR 2007. — Изд-во Урал, ун-та, 2007. — Сентябрь. — С. 5-15.

20. Поиск портретных изображений по содержанию. / А. В. Гончаров, А. Н. Каркищенко, А. Е. Лепский, А. С. Горбань // Интернет-математика 2007: Сбор, работ уч-в конкурса. — 2007. — С. 56-64.

21. Szlavik, Z. Face analysis using cnn-um / Z. Szlavik / / Cellular Neural Networks and their Applications. Proc. of the 8th IEEE international workshop Budapest. 2004. - Pp. 190-195.

22. Balasuriya, L. S. Frontal view human face detection and recognition / L. S. Balasuriya, N. D. Kodikara // Proc. of the Int. Inf. Tech. Conf IITC200. 2001.

23. Szlavik, Z. Attention based facial symmetry detection / Z. Szlavik // Pattern Recognition and Image Analysis, Third Int. Conf. on Advances in Pattern Recognition, 1С APR 2005, Bath, UK. 2005.

24. Beumier, C. Automatic face authentication from 3d surface / C. Beumier, M. Acheroy //In British Machine Vis. Conf. BMVC 98 / University of Southampton UK. 1998. - Sept. - Pp. 449-458.

25. Reisfeld, D. Context-free attentional operators: the generalized symmetry transform / D. Reisfeld, H. Wolfson, Y. Yeshurun // Int. J. Comput. Vision. 1995. - Vol. 14, no. 2. - Pp. 119-130.

26. Tabesh, A. Method and system for image compression using image symmetry. US Patent 7,254,275. — 2007. — Aug.

27. The relationship between shape symmetry and perceived skin condition in male facial attractiveness / В. C. Jonesa, A. C. Littlea, D. R. Feinberga et al. // Evolution and Human Behavior. — 2004. — January. — Vol. 25, no. 1. Pp. 24-30.

28. A reflective symmetry descriptor / M. Kazhdan, B. Chazelle, D. Dobkin et al. // 7th Europ. Conf. on Сотр. Vis. (ECCV 2002). 2002.: -may. -Pp. 642-656.r ,

29. Горбань, А. Описание и обнаружение аффинных симметрий изображения / А. Горбань // Мат-кы VII Всерос. научн. конф. студентов и аспирантов «Техн. киб-ка, радиоэлектроника и сист. управ-я». — 2004.- С. 230-231.

30. Marola, G. On the detection of the axes of symmetry of symmetric and almost symmetric planar images / G. Marola // IEEE Trans. Pattern Anal. Mach. Intell. — 1989. Vol. 11, no. 1.- Pp. 104-108.

31. Горбань, А. Методы обнаружения отражательной симметрии полутоновых изображений / А. Горбань // Интел-е сист. принятия решений и приклад, аспекты инф. техн-й. — 2006. — Т. 1. — С. 57-61.

32. Kiryati, N. Detecting symmetry in grey level images: The global optimization approach / N. Kiryati, Y. Gofman // Int. J. Comput. Vision. 1998. - Vol. 29, no. 1. - Pp. 29-45.

33. Hel-Or, H. Computational aspects in image analysis of symmetry and of its perception / H. Hel-Or, D. Avnir // Int. conf. of the Int. Society for the Interdisciplinary Study of Symmetry ISIS-98. — Haifa, Israel: 1998. — Sept.

34. Zabrodsky, H. Continuous symmetry measures / H. Zabrodsky, S. Peleg, D. Avnir // Journal of the American Chemical Society J ACS. — 1992. — Vol. 114.-Pp. 7843-7851.

35. Shen, D. Robust detection of skewed symmetries by combining local and semi-local affine invariants / D. Shen, H. H. S. Ip, E. K. Teoh // Pattern Recognition. 2001. - Vol. 34. - Pp. 1417-1428.

36. Горбанъ, А. Обнаружение отражательной и вращательной симметрии контура / А. Горбань // Сб. док-в конф. III Всерос. науч. конф. молодых ученых и аспирантов "Новые инф. техн. Разработка и аспекты применения". — 2004. С. 118-123.

37. Antoine, J. Directional wavelets revisited: Cauchy wavelets and symmetry detection in patterns / J. Antoine, R. Murenzi, P. Vandergheynst // Appl. and Сотр. Harmonic Anal. — 1999. — Vol. 6, no. 3. — Pp. 314-345.

38. Gross, A. D. Analyzing skewed symmetries / A. D. Gross, Т. E. Boult // Int. J. Сотр. Vision. — 1994. — Vol. 13, no. 1. —Pp. 91-111.

39. Friedberg, S. A. Finding axes of skewed symmetry / S. A. Friedberg // Сотр. Vis. Graph. Image Proc. — 1986. — Vol. 34, no. 2. — Pp. 138-155.

40. Symmetry detection by generalized complex (gc) moments: A close-form solution / D. Shen, H. H.-S. Ip, К. К. T. Cheung, E. K. Teoh<// IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1999. — Vol. 21, no. 5. Pp. 466-476.

41. Sato, J. Affine integral invariants for extracting symmetry axes / J. Sato, R. Cipolla // Image Vis. Сотр. 1997. - Vol. 15, no. 8. - Pp. 627-635.

42. Li W. Zhang A., K. L. Fast global reflectional symmetry detection for robotic grasping and visual tracking / K. L. Li W., Zhang A. // Australasian Conf. on Robotics and Automation. — 2004.

43. Sciascio, E. D. Similarity evaluation in image retrieval using the hough transform / E. D. Sciascio, A. Celentano // Journal of Computing and Information Technology. — 1996. — Vol. 4, no. 3. — Pp. 199-204.

44. Geso, V. D. A note on the iterative object symmetry transform / V. D. Geso, B. Zavidovique // Pattern Rec. Let. — 2004.— Vol. 25.— Pp. 1533-1545.

45. A shape-preserving non-parametric symmetry transform / O. Lahdenoja, E. Alhoniemi, M. Laiho, A. Paasio // ICPR '06: Proc. of the 18th Int. Conf. on Pattern Rec. — Washington, DC, USA: IEEE Computer Society, 2006.-Pp. 373-377.

46. M. Desbrun, H. P. A reflective symmetry transform / H. P. M. Desbrun // Eurographics Symposium on Geometry Processing. — 2005. — Pp. 1-11.

47. A planar-reflective symmetry transform for 3d shapes / J. Podolak, P. Shilane, A. Golovinskiy et al. // SIGGRAPH '06: ACM SIGGRAPH 2006 Papers. New York, NY, USA: ACM, 2006. - Pp. 549-559.

48. Zhitao Xiaoa Zhengxin Houb, С. M. Using phase information for symmetry detection / С. M. Zhitao Xiaoa, Zhengxin Houb, J. Wanga // Pattern Recognition Letters. — 2005. — Vol. 26, no. 13. — Pp. 314-345.

49. Kovesi, P. Image features from phase congruency: Tech. Rep. 95/4 / P. Kovesi: 1995.

50. Горбанъ, А. Инвариантные характеристики в задачах обнаружения симметрии изображений / А. Горбань, А. Каркищенко // Вт. Меж-дун. конф. «Системный анализ и инф. техн.» САИТ-2007: Труды конф. 2007. - Т. 2. - С. 210-212.

51. Heijmans, Н. J. А. М. Similarity and symmetry measures for convex shapes using minkowski addition / H. J. A. M. Heijmans, A. Tuzikov //

52. EE Tran. on Pat. Anal, and Machine Intel. — 1998. — Vol. 20, no. 9. — Pp. 980-993.

53. Demode, S. Shape distance for rotation estimation and rotational symmetry detection in gray-level images.

54. Cham, Т.-J. Skewed symmetry detection through local, skewed symmetries / T.-J. Gham, R. Cipolla // BMVC 94: Proc. of the conf. on British machine vis. — Vol. 2. Surrey, UK, UK: BMVA Press, 1994. — Pp. 549-558.

55. A quantitative evaluation of symmetry detection algorithms: Tech. Rep. CMU-RI-TR-07-36 / P.-C. Chen, J. H. Hays, S. Lee et al. — Pittsburgh, PA: 2007.-September.

56. Каркищенко, А. Моделирование и Классификация поточечных мер сходства / А. Каркищенко, А. Горбань // Международной конференции по системам искусственного интеллекта (AIS/CAD'08). — Дивно-морское: ТТИ ЮФУ, 2008.

57. Быков, В. Теория кривых / В. Быков. — Изд-во челябинского государственного университета, 2002. — С. 20.

58. Горбань, А. Использование инвариантных характеристик при обнаружении вращательной и отражательной симметрии контура / А. Горбань. — Т. 1. — Херсон: Изд. Херсонского морского института, 2005. — С. 69-71.

59. Горбань, А. Дифференциальные и интегральные инварианты в задачах обнаружения аффинных симметрий контура / А. Горбань, А. Каркищенко // Искусственный интеллект.— 2005.— Т. 4.— С. 682-688.

60. Attneave, F. Informational aspects of visual perception / F. Attneave // Psychological Review. — 1954. — Vol. 61. — Pp. 183-193.

61. Hoffman, D. D. Parts of recognition: Tech. Rep. AIM-732 / D. D. Hoffman, W. Richards: 1983.

62. Lowe, D. G. Organization of smooth image curves at multiple scales / D. G. Lowe // ICCV88. 1988. - Pp. 558-567.

63. Mackworth, A. K. Scale based description and recognition of planar curves and two-dimensional shapes / A. K. Mackworth, F. Mokhtarian // PAMI. 1986. - September. - Vol. 8, no. 5. - P. 675.

64. Horn, B. K. P. Filtering closed curves / B. K. P. Horn, J. E J Weldon // IEEE Trans. Pattern Anal. Mach. Intell.— 1986.— Vol. 8, no. 5.— Pp. 665-668.

65. Horn, B. K. P. Extended gaussian images / B. K. P. Horn // Proc. of the IEEE. 1984. - Vol. 72. - Pp. 1671-1686.

66. Horn, B. K. P. The binford-horn line finder / B. K. P. Horn // MIT AI Memo. — 1973.

67. Horowitz, S. L. Picture segmentation by a tree traversal algorithm / S. L. Horowitz, T. Pavlidis // J. ACM.- 1976.- Vol. 23, no. 2.-Pp. 368-388.

68. Pavlidis, T. Segmentation of plane curves / T. Pavlidis, S. L. Horowitz // IEEE Trans. Comput. 1974. - Vol. 23, no. 8. — Pp. 860-870.

69. Дубровин, Б. Современная геометрия / Б. Дубровин, С. Новиков, А. Фоменко. — М.: Наука, 1986.

70. Integral invariant signatures / S. Manay, A. J. Yezzi, B. W. Hong, S. Soatto // Proc. of the Eur. Conf. on Сотр. Vision. — 2004.

71. Integral invariants for shape matching / S. Manay, D. Cremers, BW. Hong et al. // Pattern Analysis and Machine Intelligence, IEEE Transactions on. — 2006. Oct. - Vol. 28, no. 10. — Pp. 1602-1618.

72. Барут, A. X. Теория представления групп и приложения / А. X. Ба-рут, P. X. Рончка. М.: Наука, 1986. - С. 455.

73. Daliri, М. R. Robust symbolic representation for shape recognition and retrieval / M. R. Daliri, V. Torre // Pattern Rec. — 2008.— Vol. 41.— Pp. 1782-1798. .

74. Attalla, E. Robust shape similarity retrieval based on contour segmentation polygonal multiresolution and elastic matching / E. Attalla, P. Siy // Pattern Rec. 2005. - Vol. 38. - Pp. 2229-2241.

75. Chetverikov, D. Matching for shape defect detection / D. Chetverikov, Y. Khenokh // Сотр. Anal, of Images and Patterns. — 1999. — Pp. 367374.

76. Chetverikov, D. A general methodology for shape defect detection. http://citeseer.ist.psu.edu/37789.html.

77. Reiss, Т. H. Recognizing Planar Objects Using Invariant Image Features / Т. H. Reiss. — Secaucus, NJ, USA: Springer-Verlag New York, Inc., 1993.

78. Alferez, R.-B. 0. Geometric and illumination invariants for object recognition / R.-B. 0. Alferez, Y.-F. Wang // IEEE Trans, on Pattern. Anal, and Machine Intel — 1999. — Vol. 21, no. 6. — Pp. 505-536.

79. Sadler, B. Shift and rotation invariant object recognition using the bispectrum / B. Sadler //In Proceedings of the Workshop on Higher Order Spectral Analysis. — 1989. — Pp. 106-111.

80. Scholkopf B. Learning with Kernels / B. Scholkopf, A. J. Smola.— Cambridge, MA, USA: MIT Press, 2002.

81. Ни, M.-К. Visual pattern recognition by moment invariants / M.K. Hu // Inf. Theory, IEEE Trans. — 1962.- Vol. 8, no. 2.- Pp. 179187.

82. Lowe, D. Distinctive image features from scale-invariant keypoints / D. Lowe // Int. J. of Сотр. Vis. Vol. 20. - 2003. - Pp. 91-110.

83. Столниц, Э. Вейвлеты в компьютерной графике / Э. Столниц, Т. Де-роуз, Д. Салезин. -М.: РХД, 2002. - С. 272.

84. Апд, С.-Н. A fast quadtree normalization algorithm / C.-H. Ang, H. Samet // Pattern Recogn. Lett. — 1994. Vol. 15, no. 1. - Pp. 57-63.

85. Каркищенко, А. К определению мер сходства полутоновых изображений / А. Каркищенко, А. Горбань // спец. выпуск «Интеллектуальные САПР» эюурнала «Известия ЮФУ. Технические науки». — 2008. Т. 4.

86. Stevens, S. S. On the psychophysical law / S. S. Stevens // Psychological Review. 1957. - Vol. 64, no. 3. - Pp. 153-181.

87. Tyler, С. Human symmetry perception and its computational analysis / C. Tyler // VSP Press. 1997.

88. Shen, J. On the foundations of vision modeling i. weber's law and weberized tv restoration / J. Shen // Physica Dpages. — 2003. — Vol. 175.

89. Tyler, C. The symmetry magnification function varies with detection task / C. Tyler Ц J. Vis. 2001. -12. - Vol. 1, no. 2. - Pp. 137-144.

90. Chengzhi, F. Horizontal and vertical asymmetry in visual spatial crowding effects / F. Chengzhi, J. Yi, H. Sheng // J. Vis. 2007.-7.- Vol. 7, no. 2. - Pp. 1-10.

91. Каркищенко, А. Аффинные свойства непрерывного преобразования симметрии / А. Каркищенко, А. Горбань // Вестник Ростовского государственного университета путей сообщения. — 2007. — Т. 4, №28.-С. 117-124.

92. Performance evaluation of state-of-the-art discrete symmetry detection algorithms / M. Park, S. Lee, P.-C. Chen et al. // Proceedings of CVPR 2008. — 2008. — June. — (to appear).

93. Canny, J. A computational approach to edge detection / J. Canny // IEEE Trans. Pattern Anal. Mach. Intell. — 1986. — November. Vol. 8, no. 6. - Pp. 679-698.

94. Bradski, G. The opencv library / G. Bradski // Dr. Dobb's Journal of Software Tools. 2000.

95. Доказательство теоремы 3.6m

96. А (яг, у) нормальное продолжение функции /¿(¿) на Ве, а ш - площадь области 0£.Т

97. Доказательство. Обозначим через п(£) — (гадЛ),пу{Ь)) вектор нормали к контуру г(£).А

98. Рис. А.1. Иллюстрация к теореме

99. Очевидно, что пх{Ь) — —гу(Ь), Пу(Ь) = гх(Ь). Поскольку по условиюконтур натурально параметризован, то это означает, что ||г'(£)|| = 1, и,следовательно, ||п(г)|| = 1.

100. Вычислим значение интеграла ££ ¡л (х, у) с1хс1у. Для этого перейдем к1. О.криволинейным координатам, связанным с контуром г(£).ь £

101. J J р{х,у) dxdy = J J Д (x(t, s), y(t, s)) (1 + sK(t)) dsdt.de0 -£

102. С учетом определения продолжения у) и задания криволинейной системы координат 5)}, получим, что функция Д б), ?/(£, я)) не зависит от 5, и Д (х(Ь, 5), ?/(£, 5)) = Д (гх(£), гу(£)) = Поэтому1.е

103. J J fi(x(t,s),y(t,s))(l + sK(t)) dsdt1. О -e1. Ь e L,

104. J (i{t) J (1 + sK(t)) dsdt = 2£ J ¡i(t)dt.e

105. Используя аналогичный переход к криволинейной системе координат, вычислим значение меры т (Д.) области Д.1.е