Инвариантные методы в теории распознавания изображений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение . Ч

Глава I. Предварительные сведения

§ I.Сведения из теории групп и топологии.

§ 2.Инвариантное интегрирование

§ 3.Представления групп. . 15"

§ 4.Ряды Фурье

§ 5.Тензорные произведения матриц . ¿<

Глава 2.Общий метод построения полных систем непрерывных инвариантов от изображений . Л О

§ I.Постановка задачи. . ю

§ 2.Метод построения полных систем непрерывных инвариантов с использованием относительно инвариантной меры . №

§ 3.Примеры применения метода

§ 4.Замечания

§ 5.Метод построения полных систем непрерывных инвариантов без использования относительно инвариантной меры . '

§ 6.Примеры . ^

§ 7.Нахождение вектор-функции V

§ 8.Примеры построения вектор-функции V . ^

§ 9.Некоторые дополнения . ^

Глава 3.Специальные методы построения полных: систем инвариантов

§ I.Получение общих формул для инвариантов . С&

§ 2.Другой способ построения матрицы 5 . ^

§ 3.Построение полной системы инвариантов от изображений относительно произвольной компактной группы .^

§ 4.Иллюстрация изложенных методов на примерах., конкретных групп .J

§ 5.Построение относительно инвариантной меры .Î

§ S .Примеры .LtO

Глава 4.Распространение метода на другие виды преобразований .115"

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

§ 2.Нетранзитивные группы преобразований.

§ 3.Инвариантные статистики. .ш

§ 4.Случай сложных изображений . .i

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

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

Задачи распознавания, как правило, крайне трудны. Более то> го, подавляющее большинство из них до сих пор не удалось даже сформулировать в точных терминах. Неизвестно каким образом с ними справляются животные и человек. Это привело к появлению большого числа различных эвристических методов распознавания. Они,хотя и позволили решить ряд задач, однако не смогли сколько-нибудь существенно продвинуть решение "по1лзмл в целом, что вызвано наличием у них целого ряда общих крупных недостатков. Это, прежде всего, слабая способность к обобщению и образованию абстрактных понятий, узкая сфера применения и неопределенность ее границ. Отсутствие какой-либо теории не позволяет обобщать эвристические алгоритмы и переносить их на другие задачи, а построение такой теории крайне затруднено в связи с их разнородностью и несвязанностью.

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

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

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

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

Единственной известной автору работой, в которой предпринимается попытка построения системы инвариантов для произвольной компактной группы, является статья Ю.П.Штьева [39] . Здесь нужно отметить, что для создания общего метода построения инвариантов относительно произвольной компактной группы математика уже имела весь необходимый аппарат, а именно, теорию гармонического анализа на компактных группах и классическую теорию инвариантов. Для построения полной системы инвариантов нужно лишь разложить изображение, представленное функцией яркости, в ряд яурье по базису, "приуроченному к группе", а затем найти -инварианты от вектора коэффициентов. Это и было проделано автором диссертации совместно с А.М.Шведовым (см.§3,3 настоящей диссертации). Пытьев первым пошел по этому пути, но по мнению автора, предложенное им решение проблемы излишне усложнено ( что, впрочем, обычно для большинства основополагающих работ и ни коим образом не может служить упреком ). Дело в том, что вместо того, чтобы разложить исходную функцию в ряд Фурье, он рассматривает преобразованную функцию, причем считает ее функцией, зависящей от точки исходного пространства и от элемента группы преобразований. Затем он разлагает ее в ряд как функцию на группе и лолучает, естественно, коэффициенты в виде функций, заданных на исходном пространстве. После этого он строит инварианты от этих коэффициентов. Предлагаемый в пункте 3,3 настоящей диссертации метод построения инвариантов для компактных групп отличается большей простотой ( в частности, коэффициентами разложения являются числа, а не функции ).

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

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

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

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

Перейдем теперь к обзору диссертации по главам.

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

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

- ? использования относительно инвариантной меры.

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

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

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

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

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

В заключение отметим, что в диссертации нашли отражение далеко не все работы автора. В ней нет, например, результатов исследования инвариантных функционалов на симметрических группах, полученных совместно с A.M. Вершиком ) (см. [48 - 50J ).

-Но

ЗАКЛЮЧЕНИЕ.

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

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

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

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

Нужно отметить, что теорию, изложенную в диссертации можно

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

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

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

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

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

ПРШЮЖЕНИЕ.

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

Лемма. Пусть даны два набора моментов {¡Лк\ ик = 0,4;-5

и для каждого К найдется такое, что

Х^к) = И1 ¿ = 0,1,.,К.

Тогда существует 6 С такое, что

= ¿ = 0,1,.

Доказательство. '

Рассмотрим множество VС Сс всех преобразований

таких, что «V.»

•V. Г» 1 Г\ б *

Оно замкнуто, поскольку является левым смежным классом по замкнутой подгруппе, оставляющей на месте вектор 3*. Покажем, что множество матриц Т^) } ае V, ограничено как

Поэтому найдутся такие матрицы К и К что

?* = к к* §* = к к*.

Отсюда имеем

Следовательно, Т Г^) К = К 0 где О(^) - некоторая ортогональная матрица. Поэтому

Т (*)* КО^Ж"1.

Таким обрзом, множество IV является образом линейного преобразования подмножества множества всех ортогональных матриц, которое содержится в сфере радиуса с центром в начале координат и, следовательно, ограничено. Поэтому V/ является компактом. Поскольку для любого Кв£}3},<. можно выбрать сходящуюся подпоследовательность Т^к^)* Тогда сходится к т.к. Т* - гомеоморфизм (Т -- точное представление). Покажем теперь, что

VI 91Т(}.)М'1.

Действительно, для всех ^ таких, что Ке > I выполнено:

Теперь остается лищь заметить, что Т сходится

Д. АЛГОРИТМ РАСПОЗНАВАНИЯ СЛОШХ ИЗОБРАЖЕНИЙ ДЛЯ СЛУЧАЯ ГРУПШ СДВИГОВ, ВРАЩЕНИИ И ПОДОБШХ ПРЙОБРАЗОВАНИЛ. О ПИСАНИЕ ЭКСПЕРИМЕНТОВ.

1.0писание идеи алгоритма.

Алгоритм работает в двух режимах: в режиме обучения и в режиме распознавания.

В режиме обучения на вход поступает эталонное изображение.

На эталонном изображении выделяется большое количество кругов различного радиуса. Часть изображения, ограниченную другом, мы будем называть фрагментом. Местоположение и радиксы кругов могут определяться случайным образом или по некоторому правилу. В описанной ниже реализации алгоритма круги располагались таким образом, что их центры находились на перекладинах некоторого воображаемого "креста" (см.рис.1$*

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

В режиме распознавания на вход подается сложное изображение. Напомним, что сложное изображение состоит из эталонного изображения, преобразованного элементом группы, и некоторого |юна (см. § 4.4). По этому сложному изображению движется "окошечко" в форме круга. Радиус его может меняться. Траектория движения определяется некоторым правилом. В приведенной яиже реализации алгоритма центр окошечка "оставлял слзд" в виде нескольких параллельных прямых.(см.рис. 2).

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

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

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

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

¿. Описание алгоритма.

Алгоритм работаат с изображениями, заданными в виде прямоугольных матриц яркости, элементы которых принимают целые значения из промежутка 0 ± Размеры матриц не менее 50 х 50. Радиусы кругов на эталонном изображении лежат в пределах

•г ^ тих » являющихся параметрами алгоритма. Координаты центров кругов О. и 4 являются целыми числами и удовлетворяют соотношениям :

Ь- - Кн 0.x, С квадратные скобки означают целую часть числа). Кругам на эталонном изображении соответствуют множества вида

где $ $ & •

В режиме обучения для каждого фрагмента изображения, ограниченного множеством Д) 4 & 4 » вычисляются моменты

7" ; * I ^ )

где ^ - элементы эталонного изображения.

При вычислении моментов для ускорения счета используется тот факт, что множества ]) а., [•%;] й $ 4 '

а также множества V Л. г*л л и сильно пересекаются.

Затем вычисляются значения инвариантов от каждого фрагмента:

у (4 а = + ** оч-" * У* о г)

^ > * \ )

(формулы для инвариантов были получены в §2.3.Количество инвариантов - два - было выбрано в процессе экспериментов). 1а этом работу алгоритма в режиме обучения заканчивается.

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

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

та,}) *{ + .

Множество определяет круг на сложном изображении

з центром в точке ( I ^ ) радиуса Я. Радиусы всех таких кругов одинаковы, но их значения могут быть различны для эазных изображений (Я является параметром алгоритма).

Meсто положение каждого круга определяется числами i и ^ которые принимают следующие значения : ^ пробегает все целые числа от К до y-R i пробегает все числа вида к К = 1,2,. [р/Л/]

V, здесь ш и (г - размеры эталонного изображения ). Обоснование выделения именно таких

фрагментов будет приведено низке.

Для каждого фрагмента вычисляются значения инвариантов, которые затем сравниваются со значениями инвариантов всех фрагментов простого изображения. Если для фрагмента сложного изображения находится фрагмент простого с близкими ( в описанном ниже смысле ) значениями инвариантов, то эти фрагменты являются "подозрительными на соответствие". Для такой пары фрагментов запоминаются :

а) расстояние между инвариантами $ ;

б) координаты центра фрагмента на эталонном изображении-;

в) координаты центра фрагмента на сложном изображении- 1}^ ;

г) радиус фрагмента на эталонном изображении -. Количество пар фрагментов, сведения о которых хранятся в

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

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

Гхц-У«)1 + С*«-^»)*' +

где , ик(

Зсли критерий выполняется, то вычисляются параметры преобразования эталонного изображения.

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

по формуле :

3. Описание экспериментов.

Для реализации описанного выше алгоритма была создана

реальных изображениях введенных в ЗВМ при помощи фототелеграфа. Исходные изображения были представлены фотографиями. Для каждой фотографии в ЭВМ вводилась матрица яркостей,которые снимались с шагом 0,4мм по горизонтали и вертикали. ^ •Размеры фотографий изменялись от 36 х 48 мм до 95 х 130 мм Матрицы яркостей хранились на диске и на ленте. Эти изображения, играли роль сложных изображений (см.,например, фото 1,2). Эталонные изображения получали следующим образом. Из сложных изображений вырезались фрагменты и к ним применялись преобразования группы поворотов и подобия ( примеры эталонных изображений приводятся ниже).

Все изображения, как уже говорилось выще, представляли собой прямоугольные матрицы, элементы которых были целыми числами из промежутка 0 -г- 63 С каждое число занимало один байт памяти ). Значения параметров Я (см.выше )

были выбраны в процессе отладки и настройки программы следующие : 10, 5 20. Далее во всех экспериментах они не менялись.

программа на языке

к проведены эксперименты на

• "U?-

m л • * л 4

il « i t « i

íii Ч'ЧЙШЙЙНШ

Программа состоит из шести процедур :

1) головная процедура ШСН,в которой

а) происходит обращение ко всем остальным процедурам;

б) вычисляются инварианты простого изображения;

в) осуществляется сканирование сложного изображения;

г) вычисляются моменты и инварианты фрагментов;

д) происходит сравнение инвариантов сложного изображения

с инвариантами эталонного, и запоминаются координаты близких пар точек на простом и эталонном изображениях ( в смысле близости инвариантов) ;

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

ж) простое изображение на сложном заключается в пунктирную рамку.

2) процедура чтения изображения с диска ;

3) процедура считывания фрагмента изображения;

процедура преобразования изображения (осуществляет растяжение и поворот изображения);

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

5) процедура печати шестнадцатиградационного изображения. Объем головной,программы - 463 оператора. Время работы программы на ЭВМ ЕС - 1030 в зависимости от размеров эталонного и сложного изображений колебалось от пяти до двадцати минут. (В это время входит время формирования простого изображения, печати изображений и т.д.). Замети/»что

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

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

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

1. На фото 3-5 представлены распечатки изображений, участвовавших в одном из экспериментов. На фото 3 изображено колесо автомобиля - это эталонное изображение. Его размеры

• 65 х 40. На фото 4 - изображение автомобиля "Волга". Оно

играет роль сложного изображения. Его размеры - 120 х 150. От ЭВМ требовалось найти первое изображение на втором. В качестве ответа ЭВМ напечатала изображение "Волги", на котором рамкой выделено правое заднее колесо ) см. фото 5 ). Заметим, что эталонное изображение колеса имеет вдвое большие размеры, чем соответствующее изображение колеса на сложном изображении.

2. На фото б представлено изображение автомобиля размером 75 х 165 на котором имеются помехи в виде пяти темных пятен

С отмечены на фотографии стрелками ). Это эталонное изображение.

Сложное изображение С фото 7 ) имеет размеры 240 х 500. На зото 8 представлено то же самое сложное изображение, на кото-)ом рамкой выделено найденное простое изображение,Далее приводятся некоторые другие сложные изображения, участвовавшие в экспериментах. ВЗиду слабйй контрастности распечаток и, как следствие, низкого качества их фотографий эти изображения представлены исходными фотографиями.

3. На фото 2 приведено сложное изображение, на котором ЭВМ 1ащла автомобиль "Москвич" и грузовик. 3 качестве эталонного 13ображения служили увеличенные в два раза соответствующие фрагменты этого изображения ( распечатки не приводятся ).

4. Изображение автомобиля на фото 8 играло роль сложного изображения. В качестве эталонных изображений служили изображения колес, которые и были найдены на сложном изображении.

5. В качестве сложного изображения было взято изображение 1а фото 8, но на нем имелись помехи в виде пяти темных пятен. Эталонные изображения те же, а именно, колеса. ЭВМ нашла оба изображения на сложном изображении.

в, На сложном изображении ( фото I ) были выделены изображения автобуса и грузовика.

В случае отсутствия помех на изображениях эксперименты показали устойчивую работу алгоритма при размерах эталонного изображения не менее 50 х 50 и коэффициента растяжения, лежащем в пределах 0,5 * 2. При наличии большого количества помех на эталонных изображениях С например, десять и более темных пя-ген ) эталонные изображения в ряде случаев не были найдены на сложных изображениях. Анализ таких случаев показал, что к отказу от распознавания приводит сильное искажение центральных

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

ЛиТЕРАгУРя

Х.Айзерман М.А. Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.,НаукаД970. 384 с.

2.Бонгард М.М. Проблема узнавания. М.»Наука, 1967 320 с.

3.Вапник В.Н.»Червоненкис А.Я.Теория распознавания образов. М., Наука,1974, 416 с.

4.3авалишин Н.В.,Мучник И.Б. Модели зрительного восприятия и алгоритмы анализа изобращений.М.,Наука, 1974, 344 с.

5.Ковалевский В.А. (редактор). Сб."Читающие автоматы",Киев, Наукова думка, 1965, 167 с.

6.Фомин В.Н.»Математическая теория обучаемых опознающих систем. Л., Изд. ЛГУ, 1976. 236 с.

7.Ковалевский В.А.Распознавание образов: Эвристика или наука? Киев, изд.ИК АН УССР, 1970.33 с.

8.Розенфельд А. Распознавание и обработка изображений.М., Мир, 1972. 230 с.

9.Дуда Р.Дарт П. Распознавание образов и анализ сцен.М., Мир, 1976, 511 с.

10.Интегральные роботы. Сб.статей под ред.Г.Е.Поздняка. М., Мир, 1973. 424 с.

П.Вапник В.Н. Задача обучения распознаванию образов.М., Наука, 1971.60 с.

12.Васильев В.И.Распознающие системы.Киев,Наукова думка, 1969. 292 с.

13.Грановская P.M.Восприятие и модели памяти.Л.,Наука, 1974. 361 с.

14.Грановская P.M.»Березная И.Я.Запоминание и узнавание фигур. Л., изд.ЛГУ, 1974. 96 с.

15.3агоруйко Н.Г. Методы распознавания и их применение.М.,

Советское радио, 1972. 206 с. 16.Дересада В.П.Автоматическое распознавание образов. Л., 1970. 90с.

17.Фу К.Последовательные методы в распознавании образов и обучении машин. М., 1971.V 256 с.

18.Автоматический анализ сложных изображений. Сб.пер.под ред.Э.М.Бравермана. М., Наука, 1969.310 с.

19.Козинец Б.Я.Об одном алгоритме обучения линейного персеп-трона. - В кн.:Вычислительная техника и вопросы программирования, вып.З. Л.,ЛГУ,1964, С.80-83.

20.Козинец Б.Н.,Ланцман Р.М.,Якубович В.А. Об одном кибернетическом методе исследования в криминалистической экспертизе почерка.- В кн.:Кибернетика и судебная экспертиза,

вып.2. Вильнюс, 1966, с.15-35.

21.Ковалевский В.А.Современное состояние проблемы распознавания образов. - Кибернетика, 1967, № 5, с.78-86.

22.Фомин В.Н. Об одном алгоритме опознающих систем. - В кн.: Вычислительная техника и вопросы программирования, вып.4,

Л., изд.ЛГУ, 1965, с.72-75.

23.Якубович В.А. Машины, обучающиеся распознаванию образов. - В кн.:Метод вычислений, вып.2. Л.,1963, с.95-131.

24.Якубович В.А.Некоторые общие принципы построения обучаемых распознающих систем. В кн.:Выч.техника и вопросы программирования, вып.4. Л., изд.ЛГУ,1965, с.3-72.

25.Якубович В.А.Три теоретические схемы обучающихся опознающих систем. - В кн.:Самообучающиеся автоматические системы. М., 1956, с.21-28.

i6. Глезер В.Д.,Дудник К.Н.,Куперман А.М.Деушина Л.И.,

Невская A.A., Подвигин Н.ё., Праздникова Н.В. Зрительное опознание и его нейрофизиологические механизмы. Л.,

Наука, 1975. 272 с.

7.Линкин В.М. Построение обобщенных признаков двумерных изображений. - В сб."Читающие устройства".ВИНИТИ,1955, с.96-102.

28.Махонин В.А. Об аффинном опознании плоских фигур.Изв. АН СССР, ОТН, Техн.кибернетика, 1963, I,с.12-18.

9.?озенблат Ф.Обобщение восприятий по группам ipeобразований. Кибэрн.сб., № 4, ИЛ, 1952.

ЗО.Тхабисимов Д.К., Усиков Д.А.Определение полной системы инвариантов функций относительно группы движений плоскости в задачах распознавания изображений. - М., изд. ИКИ АН СССР, 1979. 14 с.

I.УСИКОВ Д.А. Применение абстрактного гармонического анализа для быстрого распознавания изображений.Предпринт ИКИ АН СССР, Пр. -335, 1977. 12с.

32.Тхабисимов Д.К. Быстрый корреляционный анализ на группе движений и однородных масштабных преобразований движений и однородных гшоскост.Препринт ИКИ АН СССР, Пр-418,1978.11с.

3.Романов В.П.Извлечение информативных инвариантных признаков при автоматическом чтении.-Научно-техн.информация,1964,№2.

>4.Махонин В.А.Инвариантность при опознании сравнением описания с образцом. - В сб."Опознание образов'.Теория передачи информации". М., Наука, 1955.

о.Ху Мин-куэй. Опознание фигур при помощи инвариантных соотношений между моментами.-Тр.Ин-та радиоинженеров,1961,№9, с.19-57.

36.Тимофеев A.B. Системы инвариантного,опознавания и их реализация методами когерентной и некore рентной оптики.

Изв. АН СССР, сер.Техн.кибернетика, $ 6 1971, с.22-29.

37. Ни М,К. patte.*tu ъе-co^ni t CoUi,

¿hmiUHU.-IRE TRA/l/t^lUljT-B^i.

38.Пытьев Ю.П. Алгоритм предварительной обработки сигналов в распознающих системах, обобщающих по подобию.-Кибернетика, 1971, ]£ 3, с. 23-31.

39.Штьев Ю.П. Группы Ли в задачах узнавания.-Вопросы радиоэлектроники, 1970,сер.общетехническая, выл. 8.,с.141-158.

40.Тимофеев A.B., Удовиченко С.П.Даричев В.В.,Шмидт A.A. Полные и непрерывные системы инвариантов в задаче распознавания изображений. - Вестник Ленингр.ун-та, 1972,№19, с.142-144.

41.Харичев В.В.,Шмидт A.A.,Якубович З.А.Об одной новой задаче распознавания образов.-Автоматика и телемеханика, 1973, № I, с. 109-122.

42.Шмидт A.A. Задача о смысловом фильтре при распознавании зрительных образов. - В кн. : Рефераты докладов У1 Всесоюзного совещания по проблемам управления. 4.Т, М.,1974,

с.156-160.

43.Шведов A.M.,Шмидт A.A. О полной системе инвариантов для некоторого класса задач распознавания образов.-Препринт, изд.ДВНЦ АН СССР, 1976.11с.

44.Шведов A.M.,Шмидт A.A. Задача узнавания.- Препринт, изд. ДВНЦ АН СССР, 1976. 12 с.

45.Шведов A.M.,Шмидт A.A.,Якубович В.А.Инвариантные системы признаков в распознавании образов.-Автоматика и телемеха-

ника ¿¡979, Ii 3, с. 131- 142.

46.Наймарк Ю.Г., Хазанович С.И., Шведов A.M.,Шмидт A.A. Инвариантные алгоритма пеленгования сигнала с неизвестным спектром на выходе широкополостной антенны.-Вопросы судостроения, сер.общетехн., 1978, вып. 37, с. 3-8.

47.Шмидт A.A. Построение полных систем непрерывных инвариантов для некоторого класса групп преобразований изображений. Деп. в ВИНИТИ, 6879-83, 1983.

48.Вершик A.M.

, Шмидт A.A. Симметрические группы высокой

степени. -ДАН СССР, 1972, т.206,№2,с.17-19.

49.Вершик A.M.,Шмидт A.A. Предельные меры, возникающие в асимптотической теории симметрических групп, 4,1.-Теория вероятностей и ее применения, 1977, № I,с.72-88.

ЗО.Вершик А.М.Шмидт A.A.Дэздзльныз мзэн, возникающие в асимптотической теории симметрических групп, 4.2.--Теория вероятностей и ее применения, 1978,Щ, с.42-54.

51.Вейль Г. Классические группы, их инварианты и представления. М., ИЛ, 1947. 408 с.

б2.Виленкин Н.Я.С.ециальные функции и теория представлений гру п. М., Наука, 1965. 538с.

53.Наймарк М.А. Теория представлений групп. М.,Наука, ' 1976. 560 с.

54.Хьюитт Э., Росс К. Абстрактный гармонический анализ., т.1, М., Наука, 197 5 656 с.

55.Хьюитт 3., Росс К.Абстрактный гармонический анализ, т.2. М., Мир, 1975.902с.

56. Понтрягин Л.С.Непрерывные группы.М.,Наука, 1973.520с.

57.Серо Ж.-П. Линейные представления конечных групп.М.,Мир, 1970, 132 с.

58.Кириллов A.A. Элементы теории представлений. М.,Наука, 1972. 336 с.

55.Дьедонне Зл.,Керрол Дк.,Мамфорд Д.Геометрическая теория инвариантов. М., Мир, 1974. 280 с.

бО.Рудин У.Функциональный анализ. М., Мир 1975.446 с.

61.Эдварде Р.Функциональный анализ. М., Мир, 1969, 1072 с.

62.Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М., Наука, 1972. 496 с.

63. Ефимов Н.В. Розендорн З.Р. Линейная алгебра и многомерная геометрия. М., Наука, 1974. 544 с.

64.Рид М., Саймон Б. Методы современной математической физики, т.1, M., 1977. 360 с.

65.Рид М., Саймон Б. Методы современной математической физики, Т.2.М.; Мир, 1978, 400 с.

66.Барут А., Рончка Р. Теория представлений групп и ее приложения, т.1,М., Мир, 1980. 455с.

67.Барут А., Рончка Р.Теория представлений групп и ее приложения, т.2, М., Мир, 1980. 400 с.

68.Бурбаки Н.Интегрирование. М., Наука,1970. 320 с.

69.Б.урбаки Н.Группы и алгебры Ли, гл. 1-3.М.,Мир, 1976, 496с.

70.Чеботарев Н.Г. Теория'групп Ли.Гостехтеориздат, 1940.

71.Овсянников Л.В.Групповой анализ дифференциальных уравнений. М., Наука, 1978. 400 с.

72.$айн B.C.»Опознание изображений. М., Наука, 1970.299 с.

73. Закс Ш.Теория статистических выводов. М., Мир,1975.776 с.

74.Лзман Э. Проверка статистических гипотез.М.»Наука,1966.694с.