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

УДК 681.39;
007.001.362
ББК 32.97
Ф 34

Ф е д о т о в
Н. Г.
Теория
признаков
распознавания
образов
на
основе
стохастической
геометрии
и
функционального
анализа.
—
М.: ФИЗМАТЛИТ, 2010. — 304 с. — ISBN 978-5-9221-0996-3.

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

Рукопись книги стала призером конкурса по информатике 2007 г.
Международного фонда «Human Capital Foundation»
(фонда «Научный потенциал» — Англия).

Научное издание

ФЕДОТОВ Николай Гаврилович

ТЕОРИЯ ПРИЗНАКОВ РАСПОЗНАВАНИЯ ОБРАЗОВ НА ОСНОВЕ
СТОХАСТИЧЕСКОЙ ГЕОМЕТРИИ И ФУНКЦИОНАЛЬНОГО АНАЛИЗА

Редактор С.А. Тюрина
Оригинал-макет: Е.А. Королева
Оформление переплета: Н.В. Гришина

Подписано в печать 28.11.08. Формат 6090/16. Бумага офсетная. Печать офсетная.
Усл. печ. л. 19,0. Уч.-изд. л. 20,0. Тираж 500 экз. Заказ №

Издательская фирма «Физико-математическая литература»
МАИК «Наука/Интерпериодика»
117997, Москва, ул. Профсоюзная, 90
E-mail: fizmat@maik.ru, fmlsale@maik.ru;
http://www.fml.ru

Отпечатано в ООО «Чебоксарская типография № 1»
428019, г. Чебоксары, пр. И. Яковлева, 15

ISBN 978-5-9221-0996-3

9+HifJ
C-LKTTQN+

ISBN 978-5-9221-0996-3

c⃝ ФИЗМАТЛИТ, 2009, 2010

c⃝ Н. Г. Федотов, 2009, 2010

ПРЕДИСЛОВИЕ

Устойчивой тенденцией научно-технического прогресса является
увеличение числа людей, занятых обработкой информации. Оно превысило число людей в сфере материального производства. Настоятельной
стала потребность во все более совершенных средствах информатики,
поскольку информация является ключевым элементом принятия решений. Одной из важнейших задач, возникающих при создании информационных систем, является автоматизация процесса распознавания
образов. Для ее решения ведутся широкие исследования, которые призваны помочь познать одно из основных свойств человеческого мозга —
способность распознавать — и создать решающие предпосылки для
построения интеллектуальных систем. При этом следует подчеркнуть,
что подражание деятельности человеческого мозга — не единственный
подход к построению подобных систем. У техники есть свои собственные пути реализации этой задачи, отличные от естественных возможностей человека. Раскрытию некоторых из этих путей, связанных
с применением стохастической геометрии и функционального анализа,
и посвящена эта книга.
В предшествующей книге автора (Федотов Н.Г. Методы стохастической геометрии в распознавании образов. — М.: Радио и связь,
1990) аппарат стохастической геометрии применён для формирования
признаков распознавания изображений, а полученные на его основе
алгоритмы использованы для построения распознающих систем. Простота, высокое быстродействие и экономичность обусловлены тем, что
распознавание в таких системах совмещено с процессом сканирования.
Эта книга в 1992 г. стала призёром международного конкурса по решению проблемы распознавания образов, организованного транснациональной компанией HEWLETT PACKARD (НР) (жюри: лаборатория
НР по распознаванию образов и университет г. Бристоль — Англия).
Конкурс проводился под девизом «Новые идеи в решении проблемы
распознавания образов». Автор с удовлетворением отмечает, что идеи,
изложенные в книге, не устарели. По данным INTERNET методы
стохастической геометрии используются в Институте белка РАН при
микроскопических исследованиях протеинов. По данным [15] методы,
основанные на стохастических признаках, применяются при поиске
изображений по их содержанию в больших базах данных. Автор и его
научная школа успешно применяют методы стохастической геометрии
при анализе и распознавании биологических микрообъектов из области
нанотехнологий [51, 52, 55, 80, 82, 86]. Однако главный потенциал
новизны упомянутой книги заключается во введённом в ней автором
новом геометрическом преобразовании, связанном со сканированием

Предисловие

изображений по сложным траекториям. Это преобразование названо
в последующих работах трейс-преобразованием (от английского слова
trace — след). Введённое трейс-преобразование дало импульс развитию
новой теории признаков распознавания в последующих исследованиях
автора, включая и данную книгу.
Первые четыре главы настоящей книги посвящены формированию
признаков распознавания на основе исследования геометрических вероятностей пересечений, покрытий геометрических объектов: прямых,
отрезков прямых, кривых, областей и решёток. Часть этих геометрических объектов интерпретируется как распознаваемое изображение,
другая часть как сложные траектории сканирования.
В главе 5 излагается теория трейс-преобразования. Показано,
что трейс-преобразование является удобным инструментом изучения движения объектов. Исследуется реакция результатов трейспреобразования на группу движений и масштабные изменения объектов, по ним определяются параметры этих преобразований.
Трейс-преобразование служит источником нового класса конструктивных признаков распознавания, которые могут быть получены в
режиме автоматической компьютерной генерации. Характерной особенностью этих признаков, названных триплетными, является их структура в виде композиции трёх функционалов. Благодаря такой структуре
возможна генерация большого числа (тысяч) новых признаков распознавания. Опора на большое число признаков позволяет говорить о
новом понимании изображений. В процессе генерации могут появляться коррелированные признаки, для исключения избыточности анализируются пути сокращения размерности признакового пространства.
Исследованию теории триплетных признаков, процессу их генерации
и его программной реализации посвящены главы 6 и 7.
Трейс-преобразование и введённое автором двойственное трейспреобразование дают возможность осуществить нелинейную фильтрацию изображений с целью их сегментации, уменьшения зашумлённости, сглаживания, полигональной аппроксимации и других видов
предварительной обработки изображений. С теоретической точки зрения это очень важно, так как позволяет с единых позиций рассмотреть два этапа распознавания образов: предварительную обработку и
формирование признаков. Это важно и с практической точки зрения,
так как предобработка изображения и формирование признаков осуществляется за один шаг работы сканирующей системы, что ведёт
к повышению быстродействия распознающих систем. Этот материал
составляет содержание главы 8.
В главе 9 рассмотрено приложение стохастической геометрии и
функционального анализа к решению задач технической дефектоскопии — распознаванию дефектов сварных соединений.
Глава
10
посвящена
распознаванию
сложноструктурированных
изображений на основе стохастической геометрии и функционального
анализа и его программной реализации. Речь идёт о применении
триплетных
признаков
для
распознавания
гистологических
изображений
и
изображений
ультразвуковых
исследований
в
рамках

Предисловие
5

проекта INTAS. Целью проекта было создание моделей на стыке
медицины,
информатики
и
математики
для
совершенствования
диагностики.
В главе 11 исследуется новое применение аппарата стохастической
геометрии и функционального анализа для поиска биометрической
информации в больших базах данных.
В главе 12 показано, что аппарат стохастической геометрии можно
успешно применять для распознавания не только изображений, но и
незрительных образов. Приведены примеры применения стохастической геометрии для решения практических задач по распознаванию
образов в геологии, геофизике и экологии. Все они демонстрируют, что
аппарат стохастической геометрии необычайно эффективен. Эта мысль
вполне понятна и людям других профессий, в том числе и людям искусства, тоже имеющим дело со случайностью. Ее весьма емко выразил
Ю. Тынянов, говоря о поэзии Б. Пастернака в своей замечательной
книге «Архаисты и новаторы»: «У нас нет связи, которую он (поэт)
дает, она случайна; но когда он дал ее, она вам как-то припоминается,
она где-то там уже была — и образ становится обязательным».
В заключение автор выражает признательность членам жюри конкурса по информатике 2007 г. международного фонда «Human Capital
Foundation» (фонд «Научный потенциал» — Англия) за предоставленную возможность написания настоящей книги.
Автор благодарит членов научной школы, которые в разные годы учились под его руководством в аспирантуре и докторантуре:
к.т.н. Л. А. Шульгу, к.т.н. Т. В. Никифорову, к.ф-м.н. А. А. Кадырова,
к.ф-м.н. А. В. Моисеева, аспирантов А. С. Кольчугина, С. В. Романова,
А. В. Роя, О. В. Смолькина за участие в исследованиях и разработке
приложений.
Автор благодарит инженера Е. А. Крючкову за большую помощь
в оформлении рукописи этой книги.

Случайность оказывается более сильной
связью, чем самая тесная логическая связь.
Ю. Тынянов «Архаисты и новаторы»

ВВЕДЕНИЕ

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

Введение
7

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

Введение

В предисловии эти результаты перечислены в соответствии с делением книги на главы для обозначения структуры книги и подчёркивания её внутренней целостности.
Как отмечалось, представленная в книге новая теория предварительной обработки изображений и признаков распознавания базируется на совместном применении математического аппарата стохастической геометрии и функционального анализа. Термин «стохастическая
геометрия» охватывает ту часть геометрии и теории групп, которая
относится к случайным процессам. Усиление этого сложного математического аппарата элементами функционального анализа оказалось
плодотворным для исследования проблемы распознавания образов.
Применить ядро стохастической геометрии — интегральную геометрию — для решения задач распознавания образов впервые предложил
в 1961 г. американский профессор А. Новиков на конференции по
принципам самоорганизации, проведенной в Стэнфордском университете [117]. Однако в технике эти идеи не получили должного развития.
Данная книга посвящена исключительно информатике, её теоретическим проблемам, решаемым программным путём. Однако автор счёл
необходимым включить в приложение описание некоторых разработанных им ранее электронных распознающих систем, исключительно в
качестве натурных моделей, для пояснения деталей процесса обработки
информации.

Г Л А В А 1
ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМЫ
РАСПОЗНАВАНИЯ ОБРАЗОВ

1.1. Теорема Бюффона и идея построения
распознающей системы

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

Гл. 1. Принципы построения системы распознавания образов

типов ограничений, накладываемых на объекты, относящиеся к одному
классу, и порождает разнообразие формулировок задач распознавания.
Несмотря на различия определений проблемы распознавания, конечной целью является построение некоторой системы обработки информации, имеющей вход и выход. Данные, поступающие на вход,
очень сложны: имеют большую избыточность, содержат помехи и тесно
связаны с природой объектов. Выходная информация исключительно
проста — содержит указание класса или образа. Без потери общности
можно считать, что выходная информация содержит лишь номера классов или образов, т. е. является конечным подмножеством натуральных
чисел 1, 2, . . . , N. Распознающая система осуществляет отображение
входной информации на это множество.
Таким образом, при проектировании распознающих систем возникает следующая общая задача. Имеется множество образов {A} =
= {A1, A2, . . . , AN}, число которых известно и равно N. Каждому
образу соответствует совокупность наблюдений, являющаяся множеством {X}. Требуется построить распознающий алгоритм, осуществляющий однозначное отображение совокупности наблюдений или множества {X} на множество образов {A}, т. е. {A} ← {X} [38].
В этой главе речь пойдет о распознавании образов, имеющих зрительную природу, т. е. изображений различных объектов. Очевидно,
что поскольку такие образы различимы по форме, они обладают некоторыми устойчивыми геометрическими характеристиками. Применение
аппарата стохастической геометрии для анализа и распознавания подобных образов мы начнем с рассмотрения наиболее известной теоремы
Бюффона [8, 17, 105], лежащей в основе стохастической геометрии 1.
Пусть для распознавания предъявлены два класса объектов или два
образа, представляющие собой решетки параллельных линий, произвольно ориентированные на плоскости и отличающиеся расстояниями
между линиями: у одного из образов это расстояние равно a, у другого — a′. Для решения этой задачи распознавания применим вышеупомянутую теорему Бюффона, известную в литературе как задача
об иголке. Согласно теореме, если мы случайным образом бросаем
на решетку иголку, т. е. ориентированный отрезок длины l, которая
не превышает расстояния между линиями решетки, то вероятность
того, что иголка пересечет одну из линий, а не просто упадет между ними, равна (2/π)(l/a). Пусть выбрали иголку с длиной, равной
меньшему расстоянию между прямыми l = a < a′, осуществили многократное случайное бросание иголки на изображение решетки на
плоскости (причем случайность бросания означает, что реализуется
произвольный выбор ориентации и положения иголки на плоскости),
произвели подсчет и усреднение числа случаев пересечения, тогда

1 Несмотря на более чем 200-летнюю историю этой теоремы, распространение ее на
трехмерное пространство осуществлено лишь недавно, в середине 70-х годов XX века
(см.: Амбарцумян Р. В. К решению задачи Бюффона–Сильвестра в R3 // Докл. АН
СССР. — 1973. — Т. 210, № 6. — С. 1257–1260). Это свидетельствует о значительных
потенциальных возможностях развития идей теоремы, стимулированных современной
математикой, в силу чего она представляется привлекательной и для техники.