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

ЧУВАШСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ И.Н.УЛЬЯНОВА

О А

5

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

БАШ БАЛЕ

ЗАМКНУТОСТЬ ОРЗИГ В ЗАДАЧАХ РАСПОЗНАВАНИЯ ДИСКРЕТНЫХ КЗОбРЛЕНКИ

Специальность 05.13.16.- применение вычислительной техники, математического моделирования и математических методов в научных исследованиях.

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата физико - математических наук

ЧЕБОКСАРЫ - 1996.

Диссертация выполнена в Чувашском государственном университете им. И.Н. Ульянова.

Научный руководитель:

Доктор, технических наук БЕРЕЗКИН О.И.

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

наук ОРЕЛ Е.Н. Кандидат физико-математических наук ГОЛОВ В.И.

Ведущая организация

Механико-математический фа культет МГУ

Зашита состоится "1$"- ЖИ 1996 г. в часов на заседании

Диссертационного Совета при Государственном институте физико-технических проблем по адресу: 119034, г. Москва, ул. Пречистенка. Д.13/7.

С диссертацией моашо ознакомиться в научной библиотеке Чувашского госуниверситета им. И.Н. Ульянова.

Автореферат разослан "К! 1996 г.

ОбШЯ ХАРАКТЕРИСТИКА РАООТН. Актуальность темы, в диссертации центральным объектом исследования является вопрос о замкнутости орбит в задачах распознавания дискретных изобрагений. Одной из важнейших проблем распознавания объектов по изобрахениям» представляющим собой комбинации бинарных пикселов, является выяснение условий, при которых идентификация будет заведомо успешной независимо от того, в каком ракурсе предстанет тот или иной предмет. Говоря о различных ракурсах мы имеем в виду повороты, сдвиги, отражения» схатия и другие преобразования. которым могут подвергаться объекты и их образы. Серьезные трудности возникают уже на этапе формализации этой проблемы. Они имеют топологический характер и связаны с необходимостью исследования пространства» экспоненциального по отношению к исходному двумерному или трехмерному пространству» в котором представлены объекты и изображения.

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

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

г

параметров алгоритмов.

Итак, задача ставилась следующим образом:

1) Как перейти к более общим, интересным для практики, классам групп ?

2) Как дать практические рекомендации по выбору алгоритмов?

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

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

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

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

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

Классами изображений, которые следует при этом "различать", служат классы евклидово эквивалентных (конгруэнтных) изображений. Особенность и сложность этой задачи состоит в том, что на практике при использовании ЭВМ приходится иметь дело не с. самими подмножествами плоскости, а с их дискретными аналогами. Такие аналоги могут быть получены с помощью задания на плоскости фиксированной квадратной сетки с некоторым шагом и сопоставления каждому подмножеству плоскости его "клеточного" расширения. При этом шаг квадратной сетки должен быть таким, чтобы можно было различать изображения разных классов.

Можно показать, что прикладной вопрос "различимости" изображений из классов конгруэнтности» представляющих собой орбиты действия (на экспоненте), определяемого действием группы евклидовых движений плоскости при переходе к клеточным расширениям сводится к чисто теоретическому вопросу замкнутости орбит действия на экспоненте.

Цель работы заключается в следующем:

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

Общая иетодика исследований.

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

Научная новизна работы:

1) Установлена совершенность индуцированного действия на экспоненте Еполне регулярного пространства X, при условии, что исходное действие на X совершенно.

2) Установлена совершенность индуцированного действия на экспоненте мнокества левых смежных классов G/H левыми сдвигами, при условии, что G - топологическая группа, а H - ее компактная подгруппа .

3) Установлена совершенность действия локально-компактной группы G, счетной в бесконечности на экспоненте пространства X. при условии, что она действует транзитивно на X. а стационарная подгруппа Gs для некоторой точки компактна.

4) Приводится обобщение теоремы Г- К. Непомнящего на классы конгруэнтности относительно групп преобразований плоскости, действующих совераенно.

Теоретическая и практическая значимость.

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

Апробация работы.

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

- научной конференции факультета физико-математических и

б

естественных наук Университета Дружбы Народов. ( Москва» 1992).

- научной конференции факультета физико-математических и естественных наук Российского Университета Дружбы Народов.

( Москва, 1994 ). Публикации.

По материалам диссертации опубликованы 5 печатных работ, перечисленных в конце автореферата. Структура и объем работы.

Диссертация состоит из введения, обзора литературы, трех глав, заключения, списка литературы, включающего 86 наименований и приложений. Работа содержит 113 страниц машинописного текста, 18 рисунков, и 2Т страниц приложений.

Содержание диссертации.

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

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

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

Цель этой главы: подготовка к изучению действий групп на экспоненте. что приводит к основной теореме второй главы. ■

Определение 1. Непрерывное замкнутое отображение 1: X -> У

называется совершенным, если X хаусдорфово и слои I (У)- компак-

г

тные подмножества.

Пусть Х- топологическое пространство. Экспоненциальное пространство определяется формулой

ехр(Х) = С Р с х: Р/ 0, Р замкнуто ).

Обозначим

ехрс(X) = { Р е ехр(Х): Р - компактное подмножество). Для непрерывного отображения 1: X -> 1 хаусдорфовых пространств зададим отображение

ехрс1: ехрс(Х)->ехрс(У),

полагая для каждого Р е ехрс(Х)

<ехрсЯ(Р) = 1(Р).

сопоставление

X 1-> ехрсх и Г I-> ехр С1

для любого хаусдорфова пространства X и непрерывного отображения I : X ->1 хаусдорфовых пространств определяет функтор на категории хаусдорфовых пространств и непрерывных отображений в себя, причем коммутативна диаграмма

> ехр (X)

ехр„1

-> ехр (У)

Здесь ix обозначает непрерывное отображение X-> ехрс (X), сопоставляющее каждой точке х е х одноточечное подмножество

Теореыа 1. Если X и Y вполне регулярные пространства, то отобра жение

ezp0(i): ехрс(X)->ехрс(У)

совершенно тогда и только тогда, когда совершенно отображение

и X->У.

Определение 2. Пусть (Х,р)~ метрическое пространство. Для А, В s X определим число

С (А,В) = вир { р(а,В): а <= А >,

называемое отклонением множества А от множества В. Здесь через р(а,В) обозначено расстояние от точки а до множества В;

р(а,В) = Inf { р(а,Ъ): 1з е в }.

Метрика Хаусдорфа hp на ехр(Х) задается следующим образом: если А, В £ ехр(Х), то

hp(A,B) = maz { Ö(A,B), Ö(B,A) >

В главах II и III изложены результаты, полученные и выносимые на защиту автором диссертации.

Глава II. в этом разделе рассматриваются действия группы на экспоненте. Большое внимание уделяется индуцированным действиям.

Определение 3. Пусть G - группа, а X - множество. Отображение I : Сх X->Х называется действием группы G на.

.У

множестве X, если

(1) Т(в,Т(Ь,х)) = = (£Ь)Х = КёЬ.х) для любых в, 11 из б и

для любого х из X,

(2) Т(е,х) = ех = х для любого х из X, где е - единица группы С.

Определение 4. Пусть Б - топологическая группа; X - хаусдорфово

пространство и Т: С х X ->Х - непрерывное действие группы

Ъ на X.

Зададим действие I : Сг ехрс(Х) -> ехрс(Х), полагая

Т (£,Р)= Т(ё х Р), где й х Р = х € Р }, а Р € ехр0(Х).

Пусть X и У - топологические пространства. Зададим отображения

3 : ехрс (X) х ехрс (У) -> ехрс(Х х У)

и

г : ехрс(Х х У) -> ехрс(Х) х ехрс(У)

формулами

З(А.В) = А х В V А ( ехрс(X), V В е ехрс(У) , г(Р) = (тс1(Р),тс2(Р)) V Р с ехрс(Х х У), где

: X х У->Х, X х У->У - проекции.

Основные результаты сформулированы в следующих леммах и теоремах. Леша 1. Отображения г и 3 непрерывны.

Леша 2. Если X и У - Хаусдорфовы пространства, то отображение

ехрс(X) х ехрс(У) -> ехрс(ХхУ), З(А.В) = АхВ,

есть замкнутое вложение, которое вкладывает ехрс(Х) х ехрс(У) в

expc(XxY) в качестве ретракта.

Teopeua 2. Пусть Т: G х X->Х совершенное действие группы

G на вполне регулярном пространстве X. Тогда индуцированное дейс-

«V

твие Ï: G х expQ(X)->ехрс(Х) группы G на экспоненте также

совершенно.

Teopeua 3. Пусть G - топологическая группа» а H - ее компактная подгруппа. Тогда действие группы G на ехрс(G/H), индуцированное действием группы G на множестве левых смежных классов G/H левыми сдвигами» совершенно.

Teopeua 4. Пусть локально-компактная группа G, счетная в бесконечности. транзитивно действует на X. Если стационарная подгруппа Gx для некоторой (а, значит, и для любой) точки x s х компактна, то это действие совершенно, а вместе с ним совершенно и индуцированное действие группы G на ехрс(Х).

Teopeua 5. Действия на экспоненте ехрс(кп), индуцированные действиями групп

a) Is - изометрий;

b) le4"- движений;

c) Тг - трансляций

на к11, совершенны. В частности, орбиты этих действий замкнуты.

Глава III. в этой главе приводится обобщение теоремы Г.М. Непомнящего на классы конгруэнтности относительно групп преобразований плоскости, действующих совершенно.

Через Bg(X) будем обозначать замкнутые е-окрестности подмножеств

о

пространства ехрс(к ) в метрике Хаусдорфа Ь^, порожденной метри-ш. которая определена следующим образом:

?

Ш(

и.у);(х',у')) = гаах||х-х'|.|у-у'

Имеем

Ве(Х) = | Р « ехрс(к2): ^(Р.А) < б, 1 я X

2

В работе е-сетью множества У £ егрс (к ) назовем подмножество X £ £ * такое, что X £ В£(X).

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

<3 = |(Х,У) е к2: 1*1 $ I, |у|<

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

Задаем отображение

С^: ехрс(ге2)-> ехрс(в?2)

р

сопоставляющее каждому изображению Р е ехрс(к'-) изображение

су?) = и ^ е ъ П Р * 0 |.

Изображение ^(Р) называется клеточным образом изображения Р.

Заметим, что для любого множества Р « егрс(к2) имеет место неравенство

и. как следствие, принадлежность

Теорема о распознавании. Пусть Х1 .Х^.. .,3^ £ ехр(£2). Каждое множество ^ представляет собой семейство изображений в О. т.е. некоторую совокупность подмножеств из О. Произвольное множество Р е е Х^ как бы составлено из клеточек (пикселов). Это множество можно интерпретировать как образец. По каждому предмету с номером 1 хранится (или "генерируется") набор образцов для различных ракурсов.

Для заданных ро. 5>0 определим многозначное отображение I): ехр«2) -> £1,2.....п), полагая

Отметим, что соотношение С^(Р) « В5(Х1) означает следующее: для некоторого А « имеет место неравенство 11т^(Р),А| 4. 5, Другими словами, множество С^(Р) как точка пространства ехр(С) лежит в замкнутой б-окрестности множества Х^^ в ехр(<2).

Отображение 0 называется распознающим (для данного семейства {Х1 «х^....Хд) пары чисел (ц,$)).

Определение 5. Будем говорить, что отображение

Б(Р) » 4 1: 1 < 1 < п, С (Р) * В

ь = о

. м|

правильно распознает изображения семейств , У2.....Уп £ ехр(О), если из Р е ^ вытекает = (1).

В работе класс конгруэнтности изображения Р относительно группы преобразований С обозначается символом С(Р).

Наряду с классами конгруэнтности также рассматриваются их клеточные образы

СС(Р) = С^ОР) п ехрШ)|.

Пусть .....рп е езФ«2) - попарно-неконгруэнтные изобрахе-

ния. Будем говорить, что распознающее отображение В правильно распознает образы этих изображений, если оно правильно распознав изображения семейств С(Р1) Г) ехр(<2)....,С(Рп) П ехр«2) в смысле, указанном выше.

о

Теорема 6. Пусть топологическая группа О действует на совершенно, а Р1,Р2,...,РП е ехр(О) - попарно неконгруэнтные изображе ния относительно этого действия.

Тогда существует такое > 0, что для любого положительного (л < у.0> существует распознающее отображение В = ко-

торое правильно распознает образы изображений Р1,Р2,...,РП.

В качестве семейства Х^, 1 = 1,... ,п, может быть взята любая ц-сеть множества СС(Р1).

Итак, можно сделать следующие выводы:

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

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

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

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

1) доказана совершенность индуцированного действия на экспоненте вполне регулярного пространства X, при условии, что исходное действие на X совершенно.

2) установлена совершенность индуцированного действия на экспоненте множества левых смежных классов G/H левыми сдвигами, при условии, что G - топологическая группа, а H - ее компактная подгруппа.

3) установлена совершенность действия локально-компактной группы G, счетной в бесконечности на экспоненте пространства X, при условии, что она действует тракзитивно на X, а стационарная подгруппа Gs для некоторой точки компактна. г

4) приводится обобщение теоремы Г. И. Непомнящего на классы конгруэнтности относительно групп преобразований плоскости» действу ¡стих совершенно«

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

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

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

Список работ, опубликовавшие по теме диссертации.

1) Саий Пале, Зеркалов Л.Г.. Буда Сандорого. Применение топологи-чееккх методов к обработке изображений". Тезисы докладов XXVIII научной конференции факультета физико-математических и естественных наук Ш. 18-25 мая 1992г. Москва 1992. с.7.

2) Баий Бале, Зеркалов Л.Г. Использование метрики Хаусдорфа в

и

распознавании бинарных изображений .Тезисы XXX научной конференция факультета Физико-математических и естественных наук РУДН.

16-24 мая 1994г. Москва 1994. с.37.

3) Баий Бале. Применение топологических методов к изучению связ-

м

ности двухуровневых изображений . УДИ. Быпускная работа. Москва 1992г.

4) Баий Бале. Использование метрики Хаусдорфа в распознавании бинарных изображений". РУЛИ• Выпускная работа. Москва. 1994г.

5) Баий Бале. 1Замкнутость орбит в задачах распознавания дискретных изображений", //сб. нау. тр. Информационная бионика и моделирование. М. ГОС. ИФТП. 1995. с.13-24.