ББК 32.81
Р24
УДК 007
С. J. D. М. VERHAGEN, R. Р. W. DUIN, F. С. A. GROEN, J. С. JOOSTEN and Р. W. VERBEEK
Pattern Recognition Group, Department of Applied Physics, Delft University of Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands
PROGRESS REPORT ON PATTERN RECOGNITION
Reports on Progress in Physics, 1980, vol. 43, N 6, pp. 785—831.
Printed in Great Britain
Редакция переводной литературы
1502000000-069
P 046(01 )-85
© 1980 The Institute of Physics.
(О Перевод на русский язык, примечания переводчика и послесловие редактора перевода, дополнительный список литературы. Издательство «Радио: и связь», 1985.
Предисловие
Этот обзор посвящен распознаванию образов, причем он не ограничивается достижениями за несколько последних лет. Основное внимание уделяется важнейшим задачам, методам и прикладным областям, и поэтому отсутствие ряда подробностей оказалось неизбежным.
В гл. 1 распознавание образов рассматривается двояко: на содержательном уровне и более формально— как некоторое однозначное отображение. Выделен ряд источников изменчивости, приводящей к тому, что один и тот же образ может иметь несколько допустимых представлений. Все они должны идентифицироваться как один образ и после классификации заноситься в некоторый определенный класс. Существенным аспектом распознавания образов, связанным с указанной классификацией, является выбор признаков в процессе предварительной обработки исходных данных. Другим существенным аспектом является процесс решения, основанный на использовании этих признаков и обеспечивающий получение результатов классификации.
В гл. 2 рассматривается несколько видов предварительной обработки. Выделены преобразования глобального и локального характера, с помощью которых целесообразно реализовывать отдельные разновидности фильтрации, разбиения и сегментации.
В гл. 3 обсуждаются три подхода, используемые в распознавании образов, а именно статистический, нечеткий и лингвистический. При обсуждении статистического подхода рассмотрены дискриминантный анализ, выбор признаков и кластерный анализ; рассмотрение нечеткого подхода включает нечеткие множества, нечеткую принадлежность классам, нечеткие признаки и нечеткую классификацию; обсуждение лингвистического подхода включает грамматики и языки для описания и синтаксического анализа изображений, построенных из «епроизводных элементов.
3
В гл. 4 кратко изложены основные прикладные задачи распознавания образов: приложения распознавания в физике и все остальные приложения (ядерная физика, геохимия, формирование изображений с помощью ультразвуковых волн, метеорология, материаловедение и спектральный анализ выбраны в качестве примеров физических приложений или приложений, в которых физические проблемы преобладают; биологическая и медицинская кибернетика, социология и экономика, психология восприятия, техника, распознавание символов, отпечатков пальцев и речи, дистанционное зондирование представляют примеры из других областей для которых приложение распознавания образов имеет существенный характер).
В гл. 5 выделены некоторые тенденции в области распознавания образов и намечены их возможные проявления в будущем.
Авторы с чувством глубокого удовлетворения выражают благодарность г-же С. Массотти за ее подробные замечания, касающиеся английского языка этого обзора. Несколько исправлений сделал также проф. А. Чоудри, приглашенный исследователь Дельфтского университета, прибывший из Университета шт. Род-Айленд, США.
Данный обзор в настоящем виде был представлен в декабре 1979 года.
1. ВВЕДЕНИЕ
1.1. Распознавание образов человеком и с помощью автоматических систем
Термином «распознавание образов» обозначается обширное поле деятельности, связанной как с реальными жизненными потребностями (распознаванием людьми и животными «образов» в окружающей их среде), так и с решением научных и технических задач (распознаванием людьми или автоматическими системами треков в пузырьковых камерах, считыванием символов, классификацией хромосом и т. д.). В этом обзоре мы практически не будем затрагивать механизмы восприятия, свойственные людям (и животным), — исключение составляет п. 4.2.3 — и сосредоточимся на «автоматическом» распознавании образов. В то же время сведения, собранные человеком посредством механизмов восприятия (часто называемые априорным знанием), будут использоваться многократно. Некоторое внимание будет уделено также и интерактивным системам, предусматривающим вмешательство человека в процесс решения. Автоматическое распознавание образов — обширное поле деятельности с несколько неопределенными границами. В литературе можно найти множество различных описаний, определяющих понятия «образ» и «распознавание образов» в целом как научное направление [157]. Все согласны с тем, что распознавание образов всегда предполагает наличие некоторой системы обработки данных (информации), имеющей вход и выход. На вход системы данные могут поступать от множества различных источников: физического объекта, находящегося в некоторой среде, некоторого процесса или как результат эксперимента, или как метеорологические, экономические, или просто некоторые отвлеченные данные. Данные, поступающие на вход системы распознавания, как правило, весьма сложны и включают сигналы, которые часто являются пространственными и/или временными функциями. Выходная информация сравнительно проста: она сводится к указанию одного из нескольких классов. Например, если входной информацией служат результаты измерения коэффициента отражения неко
5
торой поверхности, полученные посредством сканирования, то выходная информация указывает названия символов, нанесенных на эту поверхность.
Введение затрагивает, главным образом описательно, некоторые задачи и понятия, связанные с автоматическим распознаванием образов. Остальные главы также в основном имеют описательный характер, что присуще данному журналу. Поскольку в данном журнале статья, посвященная распознаванию, помещается впервые, было признано целесообразным дать общий обзор этого направления, опустив частности, выводы формул, и не ограничиваться исключительно достижениями в области распознавания за самые последние годы.
1.2. Два направления в автоматическом распознавании образов
В распознавании можно выделить два направления.
 1. Распознавание образов в узком смысле состоит в автоматическом распознавании таких образов, которые могут распознаваться людьми (и животными) при помощи их органов чувств (зрительные, звуковые образы и т. д.). Это направление мы будем называть распознаванием на основе данных, воспринимаемых органами чувств (sense-data pattern recognition).
2. Распознавание образов в широком смысле состоит в автоматическом (рас) познавании всевозможных регулярностей, встречающихся, скажем, в экономических данных или в данных научных исследований; (рас) познавание этих регулярностей достигается в результате использования методов распознавания образов. При такой интерпретации образу соответствуют все типы регулярностей (порядок, структура), встречающиеся в сложных данных. Это направление распознавания мы будем называть распознаванием на основе данных произвольного характера (general-data pattern recognition). Понятие «сложные» употреблено здесь как противопоставление понятию «простые»: анализ простых данных не относится к распознаванию образов. Решение о том, достаточно ли сложны данные для того, чтобы их анализ можно было бы называть распознаванием, определяется традициями и зависит от того, о какой именно прикладной области идет речь.
6
Анализ сложных научных данных, проводимый с применением различных методов кластерного анализа, используемых в распознавании, можно считать разновидностью распознавания образов. Данные, воспринимаемые органами чувств (сенсорные) и содержащие определенные закономерности, также обладают регулярностями; они сложны, и потому их анализ можно включить в категорию распознавания на основе данных произвольного характера.
В нашем обзоре рассматриваются оба направления распознавания образов, однако основное внимание уделяется распознаванию на основе данных, воспринимаемых органами чувств.
1.3.	Идентификация и классификация
Результатом распознавания человеком лиц, голосов и т. д. часто является идентификация некоторого определенного объекта. Под идентификацией в данном случае понимается присвоение рассматриваемому объекту надлежащего и однозначного названия. Человеку в процессе идентификации совсем не обязательно явным образом определять характерные признаки объекта. Имеет значение, в сущности, только окончательный результат процесса наблюдения, восприятия и распознавания. Автоматические системы, заменяющие распознавание посредством органов чувств человека, должны осуществлять такую же идентификацию, как и человек, сталкивающийся с определенным объектом. Однако распознающие системы должны явным образом использовать характерные признаки объекта.
Классификация включает все процессы, заканчивающиеся указанием некоторого класса (или принадлежности классу) для рассматриваемых объектов или данных. Результат распознавания тоже можно представить как подобное указание класса — в таком смысле распознавание образов является одной из разновидностей классификации. Классификация включает также простые процессы, в основе которых лежит, например, использование некоторого измеренного и некоторого порогового значений (для определения того, находится ли значение температуры в безопасных пределах). И снова традиция (а также область приложения) определяет, является ли данная классификация достаточно сложной
7
для того, чтобы считать ее распознаванием. В тех случаях, когда каждый класс содержит только один объект, классификация эквивалентна идентификации.
1.4.	Дискретные, нечеткие и непрерывные классы
Классы, возникающие в результате реализации процесса распознавания, могут быть дискретными (объект либо является, либо не является элементом некоторого класса) или нечеткими (объектам ставятся в соответствие функции принадлежности классу). В случае нечетких классов некоторый объект может характеризоваться принадлежностью к одному или нескольким классам, значение которой может задаваться в пределах 0—1. Подходы, основанные на нечетких понятиях, могут оказаться полезными для решения задач распознавания, если классы имеют нечеткий характер. Они могут также играть роль промежуточных средств при решении задач распознавания, причем решение заканчивается переходом к дискретным классам (в число которых входит класс «отказа от распознавания» или сомнительная область») (см. § 3.2).
Иногда результатом процесса распознавания является присвоение аналоговой (непрерывной) переменной некоторого значения с помощью интерполяции между дискретными классами. Например, положение протеза руки, соответствующее напряжению, которое определяется мышечной деятельностью (миограмма), будет некоторой непрерывной переменной. При применении методов распознавания на этапе обучения будет использоваться ряд дискретных положений (дискретных классов). Целесообразно, однако, приводить результат распознавания положения по данным мышечной деятельности к некоторому интерполированному значению положения, лежащему между значениями, соответствующими дискретным классам, вместо того, чтобы задавать это положение, указывая один из этих классов [30]. В результате распознавания могут возникать аналоговые данные совершенно нового типа. Так, после распознавания трека на фотографии, полученной с помощью пузырьковой камеры, его местонахождение можно указать посредством некоторого (дискретизированного) аналогового значения.
8
1.5.	Основные особенности распознавания в случае дискретных классов;
формальная постановка задачи
В большинстве задач распознавания, решавшихся до сих пор, классы были дискретными. Изложим кратко некоторые особенности распознавания образов применительно к такому случаю. Как уже указывалось, входная информация отличается определенной степенью сложности и «вырабатывается» некоторым «реальным» источником (физическим объектом, погруженным в некоторую среду, процессом, экспериментом, экономической системой и т. д.). Выходная информация, сравнительно проста — она сводится к указанию класса. Существенным в распознавании является то обстоятельство, что множество различных входных данных, поступающих, например, от датчика, подключенного к различным источникам s,i, s,-2,  • •, но несущих информацию об одном и том же образе I, должны быть отображены в один и тот же класс Ci. Например, все разновидности символа А должны отображаться в один и тот же класс А; все электрокардиограммы, снятые у здоровых людей, должны отображаться в один и тот же класс «норма» независимо от пола, национальности и возраста обследуемых, свойственных им биологических отклонений, расположения электродов при снятии электрокардиограммы и т. д. Следовательно, распознавание образов представляет собой однозначное отображение. Это означает, что все входные данные, поступающие от Si2,... и подлежащие отображению в один и тот же класс, эквивалентны (хотя и различны) относительно соответствующего образа. На языке теории множеств это означает, что на множестве S(={Sii, Si2,...} должно существовать некоторое отношение эквивалентности « S;». Отношением эквивалентности и является всякое отношение, обладающее свойствами рефлексивности, симметричности и транзитивности. Под рефлексивностью 1 понимается принадлежность Sa к тому же классу, что и sH; симметричность указывает, что если su принадлежит к тому же классу, что и stj, то и stJ- также принадлежит к тому же классу, что и s,/; транзитивность означает,
1 Рефлексивность отношения эквивалентности означает, что каждый элемент находится в отношении эквивалентности с самим собой. — Прим, перев.
9
что если sn принадлежит к тому же классу, что Зц, и Stj принадлежит к тому же классу, что и slft, то и s,-ft также принадлежат к одному и тому же классу. Отношение эквивалентности для классов С, представляет собой отношение тождества «==», поскольку все элементы одного и того же класса тождественны относительно своего образа.
Формально распознавание образов можно определить, указав, что однозначное отображение т: St-+Ct должно быть таким, чтобы отображение S, в Ci представляло собой некоторый гомоморфизм <Si, ~S,> в <СЙ => (это означает, что если Зц, Stk^s, и зц^з^ь, то и m(Sij) —m(Sik)) [36, 158].
1.6.	Распознавание образов с учителем и без учителя
Можно говорить о двух различных подходах.
1. Для каждого из отличающихся друг от друга образов I задаются примеры sn, s,-2>, причем каждому ставится в соответствие метка, указывающая класс С,, к которому он принадлежит. Множество таких примеров называют обучающим множеством. Это множество следует использовать в процессе разработки системы распознавания. Говорят, что такая система имеет учителя, знающего, к каким классам на самом деле относятся соответствующие примеры. В процессе обучения система должна научиться отображать (так хорошо, как это возможно) входную информацию в «правильные» классы. Система, однако, должна отображать и другие входные данные — не входящие в обучающее множество— в соответствующие «правильные» классы. Следовательно, должна быть предусмотрена возможность обобщения с тем, чтобы не только элементы обучающего множества, но и все возможные допустимые входные данные отображались системой в соответствующие правильные классы. Обучающее множество должно быть репрезентативно относительно всех возможных входных данных. Результат распознавания зависит также от размера обучающего множества (см. п. 3.1.5). Вариант с обучающим множеством часто используется в задаче распознавания при замене человека какой-либо технической системой, скажем, при распознавании на основе данных, воспринимаемых органами чувств (следует 10
обеспечить достижение таких же результатов, которых добивается человек при решении соответствующей задачи распознавания).
2. Случай распознавания без учителя возникает, если примеры, подлежащие анализу, не снабжены метками, указывающими их принадлежность к классу (обучение без учителя). Такая ситуация иногда также .связана с тем, что неизвестно, отличаются ли некоторые классы друг от друга. Примерами служат астрономические или экономические данные, когда следует обнаружить наличие излучающих центров или определенных ситуаций соответственно. Для решения таких задач можно воспользоваться методами кластерного анализа (см. п. 3.1.4). Случай обучения без учителя возникает и при решении задач распознавания на основе данных произвольного характера.
1.7.	Признаки
Двумя существенными проблемами в распознавании являются следующие: какие входные данные можно считать уместными и какая (предварительная) обработка исходных данных (обычно отличающихся чрезвычайной избыточностью) приводит к получению «свойств» или «признаков», действительно позволяющих проводить классификацию. Этим проблемам уделяется много внимания, но, к сожалению, сегодня неизвестны формализованные методы, которые позволили бы получить ответ на эти вопросы. Априорные знания, интуиция, метод проб и ошибок, опыт так или иначе используются при определении признаков. При наличии значительного объема априорных сведений о регулярностях, составляющих образы, и при условии, что эти регулярности просты и имеют детерминистскую природу, отыскание признаков не составляет труда (хотя при построении надежной и недорогой системы могут возникнуть затруднения). При распознавании приходится сталкиваться, главным образом, со сложными ситуациями, когда явных знаний о соответствующих регулярностях имеется немного, а сами регулярности отличаются существенными флуктуациями и изменчивостью.
В зависимости от специфики задачи используется множество типов признаков. Некоторые признаки хорошо поддаются определению и легко интерпретируются
|1
на объектах; так, при классификации автомобилей на легковые и грузовые их длина и высота могут оказаться полезными признаками; при классификации простых штриховых изображений их разбиение на более простые или даже чрезвычайно простые подобразы (называемые часто непроизводными элементами) с учетом их взаимных отношений могут позволить получить подходящие признаки. Однако более сложные признаки, основанные на форме, текстуре, статистических связях, разложении в ряд исходных данных и т. д., необходимы для классификации электрокардиограмм, клеток крови, символов и т. д. Если получаемые в результате признаки можно рассматривать как статистические величины, то для выделения из исходного набора признаков наиболее важных можно воспользоваться статистическими методами выбора признаков (см. п. 3.1.3). Если признаки можно рассматривать как непроизводные элементы и их отношения, то для описания и анализа образов можно воспользоваться лингвистическим подходом (см. § 3.3). При выборе непроизводных элементов должны получаться такие непроизводные элементы и их комбинации, которые позволяют строить простые описания анализируемых образов.
Когда признаки тем или иным способом выбраны, к ним можно применить формальную схему, изложенную в § 1.5. Вместо одного отображения m используются отображение игр. Sr+Fi, обеспечивающее получение значений признаков	fi2,...}, и отображение т2:
Fi-^Ct — процесс классификации, посредством которого входным данным ставятся в соответствие классы. Этот процесс должен основываться на существовании некоторого отношения эквивалентности ~Ft на F,-, такого, что отображение т2: F^C; представляет собой некоторый гомоморфизм (Fi,~Fi) в <С,, =>.
1.8.	Структурная схема реальной системы распознавания образов
Материал, изложенный в предыдущих разделах, можно обобщить с помощью структурной схемы, приведенной на рис. 1 и представляющей действующую систему распознавания образов, которая уже прошла стадию обучения. Датчик, соответствующий анализируемому объекту (источнику), обеспечивает поступление исходных данных. Блок предварительной обработки преобра-12
зовывает эти данные в признаки. Датчик и блок пред-зарительной обработки совместно реализуют отображение Ш\. Классификатор выносит решение, касающееся класса, к которому относится источник, и тем самым реализует отображение т2.
Для достижения практических целей необходимы гораздо более изощренные системы: блок предварительной обработки и классификатор могут разделять соответствующие преобразования на несколько этапов, как это имеет место, например, в иерархическом классифи-
Исходные данные (результаты
Источник	измерении)	Признаки.	Классы
Рис. 1. Структурная схема системы распознавания образов
кагоре, выполняющем в первую очередь классификацию по группам классов и лишь потом (возможно, после дополнительных измерений и предварительной обработки) выдающем более точные решения; может быть предусмотрено введение обратной связи между классификатором и предшествующими блоками для передачи в процессе классификации дополнительной или специальной информации; параметры блоков могут быть изменяемыми для того, чтобы их можно было регулировать на стадии обучения или корректировать с учетом временных эффектов, и т. д. Приведенная структурная схема иллюстрирует основные составные элементы простейшего варианта системы распознавания образов.
Еще одно отклонение от этой простой структурной схемы возникает в тех случаях, когда требуется использовать интерактивную систему. В сложных ситуациях невозможно или чрезвычайно трудно обеспечить полностью автоматическую классификацию. Выходом из положения может явиться участие человека на отдельных этапах процесса распознавания, так как человек может воспользоваться своей зрительной памятью и опытом, являющимся достоянием его мозга, для распознавания даже очень сложных ситуаций, неясных контуров и причудливых кластеров. Таким образом, в процессе распознавания промежуточные результаты мо
13
гут быть продемонстрированы оператору, вводящему в систему необходимую дополнительную информацию при помощи светового пера, координатной ручки (джойстика), цифрового планшета и т. п., после чего система в состоянии решать задачу самостоятельно [82].
Приведенная выше структурная схема и наши комментарии к ней относятся главным образом к рабочему режиму системы распознавания. В процессе разработки системы приходится выполнять и многое другое, чтобы отыскать и выбрать полезные признаки, определить адекватные алгоритмы решения. Эксперименты, статистический или лингвистический анализ, машинная имитация различных моделей распознавания образов и оценка результатов классификации на репрезентативных выборках — все это необходимо на этапе разработки системы.
1.9.	Датчики
В системах распознавания можно применять самые обычные датчики, например микрофоны в системах распознавания речи, электрокардиографы при исследовании электрической активности сердца. Поскольку в большинстве таких систем используются цифровые методы, аналоговые исходные данные необходимо преобразовать в цифровую форму. Создано и продолжает разрабатываться множество специальных датчиков для зрительных данных: телевизионные камеры и оптические сканирующие устройства с бегущим лучом, воспроизводящие дискретизированные значения; одно- и двухмерные матрицы на полупроводниковых светочувствительных элементах очень малого размера; сканирующие устройства, в которых лазерный луч, световой луч или световая плоскость освещают объекты, а фотоэлементы измеряют интенсивность отраженного или прошедшего излучения. В большинстве случаев трехмерные объекты представляются плоскими проекциями. Для того чтобы получить информацию о третьей координате, можно воспользоваться изображениями, соответствующими различным направлениям, и с помощью ЭВМ восстановить трехмерный объект; другая возможность связана с использованием световых решеток. Измерения расстояния (с помощью лазеров или ультразвука) также позволяют 14
получить данные о третьей координате. Для получения информации можно использовать все виды излучений, например ультразвук (см. п. 4.1.3), микроволны, рентгеновские лучи, ядерные пучки (см. п. 4.1.2). Модифицированная измерительная система, реализующая принцип ядерного магнитного резонанса, также пригодна для получения двухмерной информации о материалах, помещенных в магнитное поле. Обзор, посвященный датчикам, можно найти в справочнике [160].
1.10.	Изменчивость реализаций образов
Основная проблема распознавания была определена в § 1.5 и 1.6 — это изменчивость образов. Входные данные, которые должны быть классифицированы как представители одного и того же класса, могут отличаться довольно сильно. Имеется множество причин этой изменчивости.
Во-первых, существует изменчивость, связанная с процессом измерения. Каждый датчик порождает (аддитивный и/или мультипликативный) шум; может возникнуть необходимость в устройствах с низким уровнем шума. Шум квантования возникает в процессе дискретизации (ст2= 1/12 самого младшего разряда, если измеряемая величина распределена равномерно в наименьших интервалах). Систематические ошибки измерения не приводят к возникновению изменчивости при условии, что искажения всегда одинаковы. На практике, однако, иногда применяются датчики с различными искажениями в различных рабочих диапазонах, что приводит к возникновению изменчивости. Оптические сканирующие устройства с экранированием (их чувствительность зависит от положения выборочной точки) вносят изменчивость в тех случаях, когда источники не всегда расположены одинаково относительно сканирующего устройства. Может возникать необходимость компенсировать искажения (например, затенение) при помощи аппаратных или программных средств.
Вторым источником изменчивости могут быть шум или искажения, вносимые каналами связи или промежуточными элементами обработки, разделяющими источник информации и измерительную систему. Примерами могут служить протяженные каналы связи, по которым со спутников передаются изображения, и промежуточ-
15
ный этап — получение фотографии — в случае электронной микроскопии.
Труднее всего поддается описанию изменчивость, свойственная собственно образам; объекты, принадлежащие одному классу, скажем все различные варианты буквы А, могут очень сильно отличаться друг от друга. Этот вид изменчивости существенно зависит от характера образа. Для изучения специфической изменчивости образов, принадлежащих отдельным классам некоторого репрезентативного обучающего множества, может потребоваться анализ этого множества, причем с учетом упоминавшихся выше видов изменчивости.
Рассмотрим ряд общих проблем, связанных с изменчивостью образов. Во-первых, можно различать «сущностную» изменчивость образа (разновидности написания буквы А) и изменчивость, порождаемую способом, с помощью которого объекты, например, подготавливаются и обрабатываются. Размеры, форма, распределение ДНК или поперечных дисков хромосомы сильно зависят от способа приготовления соответствующего препарата. Различия в освещении объекта, а также «осмотр» объекта под различными углами также могут приводить к получению совершенно различных исходных данных. Акустические отражения могут изменить сигналы микрофона, источником которых служит речь. Люди и животные при распознавании обращают очень мало внимания на такие отклонения, если они остаются в определенных пределах. При автоматическом распознавании образов необходимо стандартизировать, насколько это возможно, подготовку и обработку объектов с тем, чтобы свести дополнительную изменчивость к минимуму.
Исходя из «сущности» изменчивости можно ввести разделение на образы, порожденные человеческой культурой, и естественные образы. В первом случае, когда речь идет о таких образах, как печатные или рукописные символы, можно выделить несколько стадий возникновения изменчивости. Все печатные символы, соответствующие одному знаку, имеют стандартные размеры и очертания; изменчивость же возникает из-за ограниченности срока службы символов, используемых при печати, что связано с их износом, неравномерным нанесением типографской краски, неоднородностью бумаги, загрязнением и т. д. Расширение набора символов-приводит к росту изменчивости — «декоративные» симво-16
лы могут сильно отличаться от обычных. Написанные от руки печатные символы (в еще большей степени это-справедливо для рукописных символов) проявляют ужасающую изменчивость и по форме, и по размеру. В этой ситуации вряд ли возможно сформировать «репрезентативные» обучающие множества. Любой пишущий может создавать собственные символы с тем условием, что он сам, а также те, кто будет читать написанный им текст, легко распознают эти символы. Если символы выписаны хорошо, то удобно воспользоваться структурным анализом, фиксируя число концевых точек, пересечений, а также число и расположение выпуклых и вогнутых отрезков линий; обычно рукописные символы существенно отличаются от хорошо выписанных образцов. Чтобы упростить задачу системы распознавания,, проводится нормализация (на чеках, например, печатаются сетки или направляющие для написания символов). При анализе сцен, включающих объекты, порожденные деятельностью человека (сцены в помещениях, на улице, здания, автомобили, самолеты и т. д.), приходится сталкиваться с точно такими же сложностями. Хорошо определенные стандартизированные или обладающие простой структурой объекты также проявляют меньшую изменчивость и проще поддаются распознаванию, чем сложные объекты. Изменчивость естественных образов, например биологических объектов или естественных сцен, определяется их природой. Объекты типа вирусов (при условии должной нормализации способов-подготовки препаратов) проявляют лишь малую изменчивость; объекты, относящиеся к более высоким биологическим уровням, характеризуются растущей изменчивостью размеров и формы, а иногда и облика. Объекты,, относящиеся к таким уровням, как хромосомы, клетки (клетки крови) и ткани, обладают изменчивостью, при которой автоматическая классификация является целесообразной. Объекты, принадлежащие к еще более высоким уровням: такие, как цветы, животные, человеческие лица,— не часто становятся объектами распознавания из-за свойственной им чрезвычайно высокой изменчивости. Отпечатки пальцев и следы, оставленные ногами, содержат, однако, хорошо определенные признаки, что дает возможность применять к ним методы, распознавания (см. п. 4.2.6). Тщательно отобранные и сравнительно небольшие словари позволяют осущест-2—115	17
влять распознавание речи, однако до сих пор речь характеризуется слишком сильной изменчивостью, препятствующей ее обработке с помощью методов распознавания образов (см. п. 4.2.7).
Можно считать очевидным, что «абсолютное» значение изменчивости каждого из образов («собственная» изменчивость) имеет значение лишь в сравнении с «различиями», существующими между образами, относящимися к разным классам («межклассовая» изменчивость) (см. § 1.12).
1.11.	Статистические и лингвистические методы принятия решений
Существует целый ряд методов принятия решений, пригодных для отнесения объекта к одному из нескольких классов по заданным признакам и с учетом изменчивости образов. Эти методы существенно зависят от типов признаков и соотношения собственной и межклассовой изменчивости соответствующих образов. В дополнение к специализированным и эвристическим можно выделить два обширных семейства методов принятия решений.
1. Методы статистической теории решений применимы при работе с объектами, признаками которых служат числовые значения, причем эти значения у объектов, принадлежащих одному классу, неодинаковы. Априорные сведения являются существенными для выбора признаков; сведения об отклонениях значений признаков у объектов одного и того же класса должны собираться с использованием статистического анализа. Эти обе разновидности сведений могут способствовать формированию решающих функций, обеспечивающих классификацию (см. § 1.12, 3.1).
2. Лингвистические методы (называемые также структурными или синтаксическими) применимы при работе с объектами, признаками которых служат непроизводные элементы (или конгломераты непроизводных элементов) и их отношения. Некоторая грамматика определяет правила построения образа из непроизводных элементов. Используется множество типов грамматик (в том числе стохастические грамматики), обладающих различными широтой грамматического описания и сложностью. Такие грамматики часто удается определять 18
на основе априорных сведений об образах; в противном случае для их получения приходится прибегать к грамматическому выводу по репрезентативной выборке образов. Выполнение классификации при заданных непроизводных элементах и их отношениях требует грамматического разбора (см. § 3.3).
Уместным может оказаться применение комбинации двух этих методов.
1.12.	Понятия сходства и расстояния
При выполнении некоторых условий изменчивость образа и различия между образами, обсуждавшиеся в § 1.10, можно определить строго.
Если рассматриваемые образы можно охарактеризовать некоторым набором k признаков, каждый из которых принимает непрерывные или дискретные значения, то можно задать fe-мерное векторное пространство, каждая координата которого представляет один признак (признаковое пространство). В таком случае образ задается некоторой точкой й-мерного пространства. Если ввести понятие расстояния (евклидова, махаланобисова, кварталы и т. д.), то образы, находящиеся на небольшом расстоянии друг от друга, можно считать сходными, а образы, разделенные значительным расстоянием,— различными. Образ, обладающий малой изменчивостью, т. е. малыми вариациями значений признаков различных представлений данного образа, определяется небольшим характеристическим объемом в fe-мерном пространстве (центром этого объема могут служить, скажем, средние значения признаков). Иногда предполагается, что все представления некоторого образа должны располагаться в пределах подобного малого объема (гипотеза «компактности») при условии правильного выбора признаков. Шумы, связанные с измерением и передачей данных (см. § 1.10 и 2.2), приводят к увеличению характеристического объема.
Если различные образы далеко отстоят друг от друга и занимают непересекающиеся характеристические объемы, то очень простое решение задачи распознавания состоит в классификации предъявленного образа в соответствии с положением области ^-мерного пространства, в которой находится представляющая этот образ точка. Практически, однако, эти объемы часто не яв-2*	19
ляются малыми, а области, соответствующие различным образам, пересекаются. Кроме того, эти объемы должны определяться с помощью обучающих множеств или кластерного анализа, что по большей части приводит к получению плохо определенных областей. Значения признаков иногда можно рассматривать как случайные переменные (с учетом случайной природы шумов, возникающих в системах измерения и каналах связи). В таком случае соответствующие области можно считать плотностью распределения образов. Следует найти оптимальные разделяющие поверхности, обеспечивающие классификацию образов с неизвестной классовой принадлежностью (см. § 3.1). Помимо интерпретации как плотности распределений признаки можно задавать также с помощью нечетких понятий (см. § 3.2); в этом случае также можно ввести меры сходства.
Если рассматриваемые образы можно представить некоторой последовательностью двоичных символов (например, нулей и единиц), то в качестве расстояния между образами можно использовать расстояние Хэмминга (число несовпадений соответствующих символов обеих последовательностей). Как и прежде, чем меньше расстояние Хэмминга, разделяющее образы, тем большим сходством они обладают.
1.13.	Распознавание образов и приобретение новых знаний
Распознавание на основе данных, воспринимаемых органами чувств, часто приводит к получению результатов, которые в состоянии получать человек посредством прямого наблюдения. Мы еще далеки от возможности добывать с помощью систем распознавания образов все те знания, которые доступны органам чувств человека. Существуют, однако, и исключения; при контроле быстро перемещающихся поверхностей может возникнуть необходимость замены людей-контролеров на распознающие системы.
Значительно более фундаментальный характер имеет проблема распознавания на основе данных произвольного характера. Применение методов распознавания для установления происхождения кремниевых орудий первобытного человека позволяет получить сведения, которые невозможно или очень трудно получить другими спосо-20
вами (см. п. 4.1.2). Кластерный анализ и другие методы поиска регулярностей в данных, применяемые при распознавании образов, могут также обеспечить получение новых знаний. Анализ точности статистической системы распознавания, в процессе которого определяется ошибка классификации, свойственная этой системе (вероятность ошибки при классификации новых объектов), позволяет обнаружить существование определенных границ для этой ошибки и, следовательно, для приобретаемого в процессе распознавания знания. Ошибка классификации зависит от размера обучающего множества, числа признаков и применяемого статистического метода. Можно показать [29] (см. п. 3.1.5), что при некотором фиксированном объеме обучающего множества увеличение числа признаков приводит к росту ошибки классификации; интересным следствием является необходимость иногда ограничивать число переменных (признаков), значения которых измеряются и используются при статистическом анализе.
1.14.	Физика и распознавание образов
Распознавание образов можно использовать для автоматизации некоторых рутинных наблюдений, например при анализе простых треков в пузырьковой камере или в материаловедении для подсчета и определения размеров частиц и различных включений, число которых очень велико. Ряд методов распознавания может применяться и для изучения сложных данных в астрономии, метеорологии, спектральном анализе и т. д. Как указывалось в предыдущем разделе, некоторые результаты распознавания могут быть использованы для планирования эксперимента при наличии ограничений на возможности сбора данных. Высказывались также предположения о возможности применения методов распознавания образов при использовании квантовомеханического подхода к изучению молекул [127]. В § 4.1 приведен ряд примеров применения распознавания образов в физике.
Для решения многих задач распознавания требуются знания в области физики классифицируемых объектов, фона (в случае изображений), датчиков и ошибок измерений (см. § 1.9, 1.10). Успеху процесса распознавания могут существенно способствовать эксперименты, прово-
21
димые с целью отыскания признаков, адекватность которых определяется их связями с физическими характеристиками рассматриваемых образов.
1.15.	Связи между распознаванием образов и другими дисциплинами
Можно выделить два аспекта таких связей: в распознавании образов используются знания и технические приемы других дисциплин, а другие дисциплины используют распознавание образов для решения некоторых своих задач.
Из предыдущих разделов следует, что, в частности, статистика и физика вносят свой вклад в решение задач распознавания образов; то же самое относится и к теории автоматов, теории множеств, теории управления, теории информации, кибернетике, искусственному интеллекту, информатике, обработке изображений, лингвистике, формальным языкам, теории нервных сетей, биологии, теории восприятия и психологии. При разработке реальных систем распознавания образов необходимо использовать многочисленные технические достижения оптики, механики и электроники.
Специалисты в области распознавания стремятся объединить знания и средства, заимствованные из всех этих областей науки и техники, а также собственные результаты для того, чтобы получать должные решения задач распознавания. Можно утверждать, что распознавание образов представляет собой междисциплинарное направление, объединяющее информатику, математику, физику и технику, не считая других наук; эти направления, сливаясь, образуют междисциплинарное ядро распознавания, обеспечивающее систематическую основу для решения всех типов задач распознавания.
Распознавание можно использовать во многих дисциплинах как для замены органов чувств человека (или в качестве вспомогательного средства), так и для анализа сложных структур данных. Решение стандартных задач диагностики и контроля в технике и медицине может постепенно быть передано устройствам распознавания образов; кроме того, решение некоторых задач такого рода может стать возможным лишь в результате использования соответствующих устройств распознавания. Иногда после перестройки системы можно отка-22
заться от использования устройств распознавания: так, при сборке можно организовать хранение элементов собираемой конструкции таким строго фиксированным и упорядоченным образом, что применение методов распознавания для сортировки и ориентации деталей становится излишним. В § 4.2 мы приведем примеры приложений распознавания образов, не относящиеся к физике.
Мы уже упоминали об обработке изображений. Существуют сильные зависимости между распознаванием образов, обработкой изображений и родственной им машинной графикой. Многие задачи распознавания связаны с образами, присутствующими в изображениях, и поэтому блоки предварительной обработки должны осуществлять обработку изображений и выделение признаков (например, непроизводных элементов). Экспериментальные, экономические и другие данные иногда преобразуются в зрительную форму —кривые, наборы изолированных точек — и могут служить отправной точкой для распознавания образов. Кроме того, промежуточные данные, возникающие в процессе распознавания, могут представляться в виде некоторого изображения с тем, чтобы облегчить работу оператора в интерактивном режиме и дать возможность использовать в процессе распознавания опыт человека и свойственные ему способы принятия решений.
Обработка изображений как таковая может являться целью; при этом решение собственно задачи распознавания возлагается на человека. Поскольку датчики вносят искажения в сканируемое изображение, в процессе обработки изображения может быть улучшено его качество («восстановление») при помощи обратной фильтрации и снижения уровня шумов. Вследствие улучшения качества изображения может быть повышена его контрастность, выделены края и контуры и т. д., тем самым человек сможет лучше увидеть то, что он хочет увидеть. Восстановление и улучшение качества изображений могут также оказаться полезными в качестве предварительной обработки для распознавания.
2. МЕТОДЫ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ
2.1.	Введение
Процесс предварительной обработки должен обеспечить, как это указывалось в § 1.7, преобразование и сжатие исходных данных (часто в несколько этапов) с тем, чтобы определить свойства или признаки, (наиболее) характерные для рассматриваемых образов. Мы будем выделять (быть может, несколько произвольно) три типа преобразований.
Первый тип связан с уменьшением шума, порождаемого в процессе формирования, измерения и передачи образа (см. также § 1.10). Для этого можно использовать как стандартные методы, так и некоторые специализированные нелинейные процедуры. Подобная фильтрация может иметь как локальный, так и глобальный характер. Некоторые подробности соответствующих процедур будут рассмотрены в § 2.2.
Глобальные преобразования, в процессе которых все входные значения используются для определения каждого выходного значения, составляют второй тип преобразований, который будет рассмотрен в § 2.3. Для осуществления этого рода преобразований часто применяются различные разложения, результатом которых является некоторый набор коэффициентов, который может затем использоваться в процессе принятия решения.
Третий тип — локальные преобразования, в процессе которых лишь небольшое число входных значений, характеризующихся временной или пространственной близостью, объединяются для «одновременной» обработки. Подобные локальные преобразования часто используются при обработке изображений. Локальная область может быть сведена к единственной выборочной точке или представлять собой окрестность большего или меньшего порядка. При многократном применении локальных преобразований затрагиваемая ими область растет, что приводит к получению результатов более глобального характера (релаксационные методы [132]) . В § 2.4 рассматриваются некоторые виды локальных преобразований, используемые при обработке изображений.
24
2.2.	Преобразования (фильтрации), связанные с уменьшением шума
Понижение шумов, вносимых каналами связи и/или измерительными системами (см. § 1.10), достигается достаточно просто в тех (частных) случаях, когда измерения и передача данных от некоторых источников могут осуществляться многократно. Усреднение по п независимым значениям всех исходных данных Xi источников обеспечивает снижение шума в У п раз. Если шум указанного вида полностью определяет изменчивость (чрезвычайно редкий случай), не зависит от исходных значений Xi и его распределение, скажем, нормально, то для некоторых процедур разделения можно вычислить ошибку классификации (и пределы ее уменьшения) (см. § 3.1). Если шум известным нам образом зависит от исходных значений, то применение (нелинейного) преобразования масштаба к значениям х, позволяет свести этот случай к предыдущей модели нормально распределенного шума с вырожденными распределениями, не зависящими от исходного сигнала.
На практике часто не удается получать многократно исходные значения признаков рассматриваемых объектов, и фильтрацию необходимо реализовывать на единственном значении исходного сигнала, скажем на одном кадре видеосигнала. Если какие-то предшествующие эксперименты позволили определить энергетический спектр шума, причем последний существенно отличается от энергетического спектра сигнала, то целесообразно воспользоваться полосовой фильтрацией (аналоговой или цифровой). Если эти спектры пересекаются и известны некоторые статистические свойства сигнала и шума, то можно применить методы оптимальной статистической фильтрации. Эти методы часто используются в сочетании с линейными преобразованиями исходных данных хг, что позволяет получать признаки, обеспечивающие более естественную, чем в случае исходных признаков, реализацию процесса решения. Эти преобразования могут включать устранение систематических ошибок типа размывания посредством подбора передаточной функции точки или импульсной характеристики (обратная фильтрация), вычисление величин, производных от исходных (косвенные измерения), кодирование коэффициентами глобальных преобразований (см. § 2.3) и т. д. Винер
25
указал правила построения оптимальных функций, обеспечивающих минимизацию квадратичной ошибки, появившейся в преобразованных данных [133]. Для использования этого метода необходимо располагать ковариационными матрицами объектов и шумов и идеального преобразования при отсутствии шума, что в реальных задачах оказывается довольно жестким ограничением. Кроме того, реализация этого метода требует значительных затрат машинного времени, поскольку связана с обработкой матриц больших размеров. Можно синтезировать одномерные и двухмерные, аналоговые и цифровые фильтры Винера [1, 123, 140]. Калман предложил метод рекурсивной фильтрации, допускающий более простую реализацию [59, 114, 133]. Исходные данные часто не удается адекватно представить одной ковариационной матрицей, так как элементы изображения и фон имеют разные ковариационные матрицы и разделяются границами изображения. Последние существенны для распознавания и должны быть сохранены. Используя нелинейные методы, можно предотвратить уничтожение резких границ в результате глобального сглаживания изображения в целом [115, 124]. Целесообразным может также оказаться использование специализированных методов преобразования, основанных на нелинейной фильтрации и не требующих учета статистических характеристик изображения в целом [111]. В этом случае границы могут сохраняться, если для каждого элемента изображения определена дисперсия значения зачернен-ности по различным направлениям и в качестве значения зачерненности соответствующего элемента подставлено значение зачерненности, соответствующее тому направлению, в котором дисперсия наименьшая. Направлению, на котором встречается граница, обычно соответствует большая дисперсия, чем направлению, параллельному границе, и поэтому реализация такой процедуры не приводит к сглаживанию границы.
Одни и те же преобразования должны применяться в равной мере на стадиях обучения, экзамена и практического использования.
2.3.	Глобальные преобразования
Глобальные преобразования применяются для получения ряда характеристик на основании исходных данных в целом с тем, чтобы сформировать признаки, 26
устранить избыточность, исправить систематические ошибки (например, с помощью восстановления изображения) и т. д. Итак, некоторый набор функций yt(xi, ... ..., хп), ..., ут(х\.хп), т^п, обеспечивает получе-
ние значений г/,, 1=1, 2, ..., т, на основе всех исходных значений Xj, /=1, 2, ..., п. В реальных задачах используются главным образом линейные функции и потому
п
CijXj или у=Сх, где х и у — векторы, компонен-/=1
тами которых служат Xj и у,, а С — некоторая матрица (с,;). Применению линейных преобразований может предшествовать линейное или нелинейное изменение масштаба х (скажем, логарифмирование х); подобная операция может впоследствии быть применена к у [118].
Если в преобразовании у=Сх матрица С — неособенная, т=п и С-1 — обратная матрица матрицы С, то х= = С->(1)^+С-1(2)1/2 ... Н-С->(п)у„, где С-'(1)-первый столбец обратной матрицы С-1 и т. д. Эту процедуру можно рассматривать как разложение или разбиение исходных данных х по нормальным функциям или базисным векторам (базисным изображениям) у-. Используются базисные векторы многих типов в зависимости от математической и физической природы задачи, а также удобства реализации вычислительных процедур. В случае усеченного разложения (как это делается при сжатии данных) тип и число /n(zn<n) базисных векторов определяют точность разбиения. Поскольку исходные данные часто имеют очень большой объем (особенно при работе с изображениями), удобство реализации вычислительных процедур иногда становится основным требованием. Это обстоятельство стимулировало разработку специализированных быстродействующих процедур, например быстрого (дискретного) преобразования Фурье (БПФ) [3, 21, 50]. Благодаря удобству вычислений можно также осуществлять разбиение матрицы С за большее число, но более простых шагов и использовать унитарные, эрмитовы, циркулянтные матрицы, а также иные разновидности нормальных матриц [1, 124].
Если матрица С —нормальная, то она поддается разбиению: C—UAU-1, где Л — диагональная матрица характеристических чисел матрицы С, а столбцами матрицы U служат собственные векторы матрицы С.
27
Некоторая матрица U пригодна для представления различных матриц С, если все они перестановочны с некоторой нормальной матрицей Со, характеристические числа которой различны. Важный пример — случай циклической перестановки
1 . . О ~
0 1.0
0 . .	1
0 . . 0
которая является хорошей аппроксимацией сдвига “01. . О"
0 0 1.0
0 0 . . 1
_ о о . о _
Многие операции обработки сигналов инвариантны относительно сдвига (не зависят от времени), т. е. ССо= =С0С, и, следовательно, их собственные векторы — комплексные показательные функции. Матрицы всех подобных операций «фильтрации» — циркулярные; соответствующая матрица U представляет собой преобразование Фурье.
В случае двухмерных сигналов (изображений) часто оказывается возможным представить матрицу С как кронекеровское произведение матриц, что существенно упрощает решение соответствующих задач.
В основе многих процедур обработки лежит ковариационная матрица 2 векторов исходных данных [71], являющаяся эрмитовой. В случае векторов сигналов х с нулевым математическим ожиданием разбиение х по собственным векторам ковариационной матрицы 2 с использованием некоторой матрицы \U приводит к некоторой действительной диагональной матрице A=U~lW, которую можно рассматривать также в качестве ковариационной матрицы преобразованные данные некоррелированны. Это преобразование Карунена — Лоэва (КЛП) всецело зависит от свойств исходного сигнала и потому не может выбираться произвольно; часто оно вызывает осложнения при реализации вычислений [76]. Если в каждой циклической перестановке появляются все исходные сигналы, то ковариационная матрица 2 28
является циркулянтной и КЛП совпадает с преобразованием Фурье (винеровская фильтрация). Примерами, процедур, основанных на использовании ковариационной, матрицы 2, являются обобщенная винеровская фильтрация (см. § 2.2) [123] и сжатие данных, обеспечивающее-минимум среднеквадратичной ошибки [усеченное разложение по собственным векторам ковариационной матрицы 2 с наибольшими характеристическими числами' обеспечивает минимизацию среднеквадратичной ошибки преобразованных данных (по отношению к исходным)].
В нескольких практически используемых унитарных матрицах элементами столбцов служат нули, единицы, минус единицы или небольшое число коэффициентов, что обеспечивает возможность применения простых алгоритмов (преобразования Адамара, Уолша, Хаара, наклонное преобразование [123]). Часто они используются для получения приближенно диагональных матриц, позволяющих упростить вычисления.
Совершенно другой задачей является разложение данных по минимальному числу стандартных векторов, выбираемых из некоторого зависимого множества. Она возникает, например, при описании кривых, характеризующих спектральную плотность и плотность распределения хромосом, посредством некоторой суммы кривых нормального распределения, с помощью которых, как следует из физики, эти данные нужно представлять [53, 68].
2.4.	Локальные преобразования в обработке изображений
Допустим, что некоторое изображение можно описать через единственную функцию f(x, у). Хотя такой функцией можно представлять и различные величины (например, яркость, интенсивность, плотность, светимость), преобразования, которым она подвергается, часто оказываются подобными. Мы будем называть эту функцию зачерненностью. Пространственное квантование и квантование по зачерненности — необходимые условия для обработки изображения с помощью ЭВМ; в результате квантования строится целочисленная матрица, элементами которой являются значения зачерненности. Точки выборки могут образовывать прямоугольную решетку (обычно используемую) или шестиугольную.
29
Кроме решетки, образованной точками выборки, можно построить решетку из линий, представляющих собой границы, разделяющие выборочные точки и проведенные посередине между ними. Эта сетка дополняет каждую выборочную точку элементом изображения, называемым пикселом (pixel). Таким образом, вся площадь изображения оказывается разделенной на элементы, центром каждого из которых служит одна из выборочных точек.
Изменение масштаба значений зачерненности можно использовать, скажем, для повышения контрастности изображения. Помимо растяжения и сжатия уровней зачерненности ее значения могут быть подвергнуты новому квантованию с тем, чтобы обеспечить равномерность гистограммы зачерненности. Если после нового квантования должна быть обеспечена равная вероятность К значений зачерненности, то кумулятивную гистограмму (прежней) зачерненности следует разделить ровно на К равных частей. Поскольку кумулятивная гистограмма состоит из ступенек, новый вариант квантования не обеспечивает точного равенства ступенек квантования в преобразованной кумулятивной гистограмме. Известно несколько методов, позволяющих уменьшить эффект повторного квантования [155].
2.4.1.	Сегментация. Часто изображение состоит из частей, называемых компонентами и подлежащих анализу, и фона. Под сегментацией понимается отнесение каждого элемента изображения либо к компонентам, либо к фону. Можно выделить три метода сегментации.
1.	Разделение по порогу. Сегментация осуществляется исключительно на основе значения зачерненности каждого элемента изображения. Если это значение больше некоторого (локального) порогового, то соответствующий элемент изображения классифицируется как компонента, если значение зачерненности оказывается меньше порогового, то элемент относится к фону (либо наоборот). Известно несколько методов определения порогового значения по гистограмме зачерненности изображения [133].
2.	Обнаружение края. Если граница между компонентой и фоном характеризуется изменением значения зачерненности, то эти изменения можно использовать для выделения компонент. Обнаружение краев можно осуществлять посредством вычисления производной 30
функции зачерненности, высокочастотной фильтрации [133], оценивания границы статистическими методами [116] или с помощью специальных процедур [72, 73, 121]. Ложные края или утраченные части краев можно обнаружить, используя априорную информацию.
3.	Разделение изображения на области [12, 168]. Изображение разбивается на простейшие области, образованные соединенными между собой элементами изображения с одинаковыми значениями зачерненности. Затем соседние элементарные области объединяются с учетом различия зачерненности вдоль общей границы объединяемых областей и относительной длины общей границы. При объединении областей также можно использовать априорную информацию.
2.4.2. Преобразования сегментированных изображе-
ний. Пусть S — некоторое интересующее нас подмноже-
ство элементов изображения, относящихся к компонентам, а через S обозначим дополнение подмножества S (фон).
а.	Контур. Контур элементов пзображения-компонент состоит из тех элементов изображения, принадлежащих подмножеству S, которые имеют в качестве соседнего элемент изображения, относящийся к подмножеству фона S. Для анализа (замкнутого) контура некоторой компоненты часто требуется последовательность соседних элементов изображения, образующих контур. Эту последовательность можно
Рис. 2. Цепной код. Для любого рассматриваемого (центрального) элемента изображения можно с помощью цепного кода задать соседний пиксел контура
получить в процессе построения
контура. Начиная с исходного пиксела контура, прово
дится проверка соседних элементов до тех пор, пока не обнаруживается следующий пиксел контура. Этот процесс повторяется до тех пор, пока поиск не доходит снова до исходного пиксела контура. Соответствующие алгоритмы приведены в работах [133, 137].
Эффективность кодирования контура обеспечивается применением цепного кода [37]. Поскольку очередной пиксел контура является одним из восьми элементов изображения, соседних по отношению к рассматриваемому
31
(при использовании' прямоугольного растра), для кодирования очередного пиксела контура достаточно использовать одно число из набора целых чисел от 0 до 7. Идея цепного кода проиллюстрирована на рис. 2. По записи контура в цепном коде можно вычислить ряд признаков, в частности площадь, ограниченную контуром, кривизну в определенном пикселе контура, длину контура, а также определить, замкнут ли контур [37].
Поддаются вычислению параметры, характеризующие конфигурацию компоненты, скажем Фурье-дескрипторы контура [166]; можно также установить, обладает ли контур локальной вогнутостью или выпуклостью [38, 48, 79].
б.	Поверхностное разрушение [сжатие, прореживание] и наращивание [расширение, распространение] £65]. Для реализации этих операций необходимо пере-
! труктурирую-:: /ий элемент В
Опорный
пиксел
Резулыпат поверх-
постного разруше-
Рис. 3. Операция «поверхностное разрушение»; поверхностное разрушение некоторой компоненты изображения 3 достигается посредством перемещения некоторого структурирующего элемента В по изображению. Структурирующий элемент состоит из центрального пиксела, окруженного четырьмя соседними элементами изображения, причем центральный пиксел играет роль опорного. Положения центрального пиксела, которым соответствует полное покрытие структурирующего элемента компонентой S, определяют элементы изображения, входящие в фигуру, получаемую в результате применения операции поверхностного разрушения к компоненте 3. Штриховыми линиями указаны удаляемые пикселы, т. е. те позиции центрального пиксела структурирующего элемента, которым соответствует неполное покрытие структурирующего элемента компонентой S.
32
мещать некоторый «структурирующий элемент» В п» сегментированному изображению, содержащему компоненты. Этот структурирующий элемент представляет собой совокупность элементов изображения некоторой конфигурации, один из которых выполняет роль опорного элемента В. В тех случаях, когда структурирующий элемент полностью входит в подмножество компонент S, местоположение опорного пиксела структурирующего элемента фиксируется и элемент изображения, занимающий эту позицию, рассматривается как результат поверхностного разрушения подмножества S структурирующим элементом В- если структурирующий элемент не входит в S полностью, то элемент изображения, соответствующий положению опорного пиксела, удаляется. На рис. 3 приведен пример использования этой операции; структурирующий элемент состоит из центрального пиксела и четырех соседних с ним пикселов. Опорным является центральный пиксел. После применения операции поверхностного разрушения те пикселы подмножества 5, которые не охватывают структурирующий элемент полностью, удалены (на рисунке они изображены штриховыми линиями). Дополнительная к рассмотрен-нои операция называется наращиванием и определяется как поверхностное разрушение дополнения подмножест-ва S. В случае применения операции наращивания к подмножеству S с тем же структурирующим элементом компоненты расширяются — в них включаются все элементы фона, соседние пикселы которых принадлежат подмножеству S.
Последовательное применение поверхностного разрушения и наращивания при использовании одного и того же структурирующего элемента представляет собой операцию, называемую разъединением. Все компоненты подмножества 5, не покрывающие структурирующий элемент, устраняются. Операция, дополнительная к разъединению— последовательное применение наращивания и поверхностного разрушения, — называется соединением. В результате ее применения все промежутки, имеющиеся в компонентах подмножества 5 и меньшие структурирующего элемента, устраняются. Примеры применения этих операций приведены на рис. 4.
Поверхностное разрушение и наращивание можно применять многократно; они играют важную роль при очищении изображений (удалении малых частиц, запол-3—115	33
Рис. 4 Примеры применения операций «разъединение» и «соединение». Изображение CERMET (а) и результаты применения к нему операции разъединения (б). Все части компоненты S (пикселы изображения А с одинаковой яркостью), не покрывающие структурирующий элемент иа рис. 3, удаляются (белые пикселы на рис. б), в результате чего с изображения убираются мелкие частицы, элементы, связывающие такие частицы, и малые «возмущения». Изображение хромосомы (в) и результаты применения к нему дополнительной операции соединения (г); промежутки между компонентами (черные пикселы изображения на рис. 4,в), размеры которых меньше размеров структурирующего элемента, заполняются (белые пикселы изображения на рис. 4,а) и восстанавливается вся область, в которой размещаются хромосомы
нении промежутков) и, например, позволяют получить информацию о распределении размеров частиц.
в.	Остовы (сжатие, сохраняющее топологию). Многократное поверхностное разрушение контура в конечном счете приводит к полному устранению подмножества S. Выделение остова представляет собой операцию поверхностного разрушения, результатом которой является получение фигуры, образованной линией толщиной в один элемент изображения, которая проходит по середине компоненты S; связность построенной фигуры такая же, как у исходной компоненты (рис. 5). Условия удаления элемента изображения при выделении остова указаны 34
Рис. 5. Символы (а) и их остовы (б)
для двухмерного случая в работе [66] и для трехмерного — в работе [97].
Роль остовов состоит в том, что они обнажают струк-iypy компонент. Концевые точки и вершины разделяют остов на составляющие.
г.	Серединные оси (medial axis) (иногда пх называют остовами!) [9, 134]. Элемент изображения, входяший в подмножество S, принадлежит его серединной оси, если его расстояние до S больше или равно расстоянию до 5 любого из соседних с ним элементов изображения. Расстояние элемента изображения р до фона S определяется как длина кратчайшего пути, состоящего из связных элементов изображения, от р до пиксела фона. Исходное подмножество S можно полностью восстановить по пикселам серединных осей (/г, I) и их расстоянию d(k, I) до S [133]. Преобразование, приводящее к построению серединных осей, может обеспечить эффективное кодирование бинарных изображений.
При реализации преобразования, выделяющего серединные оси, можно учитывать и значения зачерненности [94], но в общем случае нельзя восстановить исходное изображение по серединным осям, помеченным значениями зачерненности.
2.4.3. Обзоры. Профессор А. Розенфельд публикует библиографические обзоры по обработке изображений с помощью ЭВМ, причем каждый обзор охватывает сотни источников. Его первый обзор был опубликован в 1969 г. в журнале Computing Surveys, vol. 1, р. 147— 176, и составлен на основе литературных источников вплоть до 1969 г. Второй обзор, охватывающий литературные источники за 1969—1971 гг., появился в 1973 г. 3*	35
в журнале Computing Surveys, vol. 5, p. 81 — 108. Начиная с обзора, составленного по материалам, опубликованным в 1972 г., его ежегодные обзоры печатаются в журнале Computer Graphics and Image Processing»: 1972, vol. 1, p. 394—416; 1974, vol. 3, p. 178—194; 1975, vol. 4, p. 133—155; 1976, vol. 5, p. 215—237; 1977, vol. 6, p. 157—183; 1978, vol. 7, p. 211—242; 1979, vol. 9, p. 354— 393 L
3. МЕТОДЫ, ИСПОЛЬЗУЕМЫЕ В РАСПОЗНАВАНИИ ОБРАЗОВ
3.1. Статистические методы
3.1.1. Введение. Статистический подход к распознаванию образов можно использовать в тех случаях, когда имеющихся сведений недостаточно для описания образов или классов, которые, возможно, содержатся в рассматриваемом наборе данных. В таких обстоятельствах выходом из положения может оказаться применение статистических методов для анализа, что позволяет использовать всю имеющуюся априорную информацию. Иногда необходимо провести и проанализировать новые наблюдения. Представление этих данных на статистическом языке (в виде, например, плотностей распределения, вероятностей) иногда оказывается чрезвычайно затруднительным. Если эти трудности не удается преодолеть удовлетворительным образом, то можно воспользоваться многошаговой процедурой, при реализации которой попеременно используются статистический, «физический» и эвристический подходы. В данном обзоре мы можем лишь кратко остановиться на различных аспектах статистических методов распознавания. Более подробные сведения можно найти в монографиях [10, 26, 46] и обзорах [82, 113].
* К настоящему времени А. Розенфельдом опубликовано еще несколько обзоров из этой серии: 1980, vol. 13, р. 46—79; 1981 vol. 16, р. 52—89; 1982, vol. 19, р. 35—75; 1983, vol. 22, р. 339—387. С 1983 г. журнал, в котором публикуются обзоры А. Розенфельда, выходит под названием Computer Vision, Graphics and Image Processing. — Прим, nepee.
36
Исходным материалом для применения статистической процедуры служит некоторый набор объектов, каждый из которых задается некоторым набором значений признаков (см. § 1.12). Необходимы априорные сведения, касающиеся возможных плотностей распределения значений признаков, адекватности признаков и т. д. При статистическом подходе совершенно безразлично, являются ли объекты распознавания реальными физическими объектами либо такими «нефизическими» категориями, как «социальное поведение» или «экономический прогресс», если все они допускают единообразное представление через признаки.
Мы рассмотрим следующие методы анализа данных:
1.	Дискриминантный анализ: строятся функции, зависящие от признаков и обеспечивающие оптимальное в некотором смысле разделение объектов, относящихся к разным классам.
2.	Выделение и выбор признаков: из некоторого (избыточного) набора признаков выбирается подмножество «наилучших» признаков или их комбинаций.
3.	Кластерный анализ: данные разделяются на группы объектов, подобных в том или ином отношении.
Кроме того, некоторое внимание уделено проблемам, связанным с объемом выборки и числом признаков.
3.1.2. Дискриминантный анализ [90]. Формирование дискриминантной функции, разделяющей два или несколько классов объектов, основывается обычно на одном из следующих методов.
а.	Статистические методы основываются главным образом на минимизации оценки ошибки классификации. Эта ошибка (е) представляет собой вероятность неправильной классификации поступившего на распознавание произвольного ^-мерного объекта х:
L
е— 2 Pi РГ°Ь Ф(х)т^/| X G классу /),	(3.1)
z=i
где L — число классов; £>(х)—функция, выносящая классификационное решение (может принимать одно из значений 1, 2, ..., /, ..., L), и p/=prob (хеклассу I) — априорная вероятность принадлежности произвольного объекта х классу /. (Prob (a|b) обозначает вероятность совершения события а при выполнении условия Ь.)
37
Иногда минимизируются ожидаемые потери
L L
S с//^гРгоЬ(Р(х) = /|хСклассу Z'),	(3.
Z=1 Z' = l
где Си—потери, связанные с отнесением объекта х к классу I в то время, как на самом деле хеклассу Г, Если сг/=1 при 1^Г и с;г-=0 при 1=1', то выражение (3.2) совпадает с (3.1). Воспользуемся критерием (3.1). Можно доказать, что значение (3.1) достигает минимума, если
П(х)=/ и pifi(x) >pi'fi'(x) для любых 1=£1',	(3.3)
Рис. 6. Пример применения правила классификации вида (3.3) для случая одного признака (й=1) и трех классов (£ = 3). Каждая точка х относится к тому классу, для которого произведение априорной вероятности на плотность распределения pift (х) максимально
где fi(x) —плотность распределения класса / в ^-мерном признаковом пространстве. Правило классификации (3.3) называется бейесовским. На рис. 6 представлен одномерный пример для случая трех классов (А=1, L= =3). Точки х относятся к тому классу, которому соответствует максимальное значение pifi(x); классификационные решения выносятся в соответствии с правилом (3.3). При решении реальных задач сведения об априор-. ных вероятностях и плотностях распределения приходится извлекать из имеющихся исходных данных. Ниже будет описан ряд методов, основанных на различных способах оценивания плотности распределения. Мы не будем касаться оценивания априорных вероятностей, поскольку это чисто вычислительная задача.
б.	Эвристические методы. Во многих практически, применяемых методах не используется описанный выше принцип минимизации ошибки, основанный на оценках плотностей распределения. В этих методах заложены иные критерии, часто непосредственно связанные с име-
38
ющимися исходными данными; требуется меньше априорной информации о плотности распределения (скажем, о его нормальности) или имеется возможность использовать другие априорные сведения (см. ниже пи. IV— VI).
Теперь рассмотрим несколько процедур классификации. Они отличаются друг от друга, в частности, требуемыми априорными сведениями о классах, числом оцениваемых параметров и вычислительной сложностью.
(I) Разделение с помощью квадратичных функций на основе использования плотностей нормального распределения. Если все плотности распределений f;(x), Z=l, L, можно считать нормальными, то можно построить простую разделяющую функцию, обеспечивающую минимальную ошибку классификации. Плотность распределения определяется (при Z=l, L) следующим выражением:
f ( W - (2г) -k12 I 2ZI -1 /2ехр [ -4- (х - м/ s;1 (х - g,)],
(3-4)
где k — число признаков; gz— среднее значение для класса Z; 2; — ковариационная матрица класса I и хг обозначает результат транспозиции вектора х. Нетрудно убедиться в том, что р^(х) >р1фг(х), если
(х) - —~ (X - g/s;1 (х - И;)+4- (X- И/,)г X
Х2?Дх - g,,)_ log(/7Z,//?;) — 4“lc‘g( ! 1 / ! LZ' I ) >Q-
(3.5)
Таким образом, £)(х)=/, если Szr(x) >0	Отме-
тим, что S«'(x) —квадратичная функция. На рис. 7 приведен пример разделения с помощью квадратичной функции для двух классов. Эта функция оптимальна, если истинные распределения нормальны. При решении реальных задач параметры gz, цг, Sj, pi и pi- оцениваются по обучающему множеству.
(II)	Разделение с помощью линейных функций на основе использования плотностей нормального распреде-
39
ления. Выражение (3.5) сводится к линейному виду, если Si—S/-=S:
(х)= 2 (р; nz,) S x —S P;-}-
+4"	— 1Qg (PpIPi) > °-	(3-6)
Это выражение называют линейной разделяющей функцией Фишера. При Si#=S(' линеаризация достигается заменой S; и S;- на S=(Si4-Sz')/2 (см. рис. 7). Известны н другие линейные разделяющие функции, основанные на использовании плотности нормального распределения
Рис. 7. Пример применения квадратичной разделяющей функции SI22(x) и ее линейного приближения -Si2! (к) для случая двух классов. Линии равной плотности распределения приведены для двух классов; предполагается, что р1=Рг=0,5
(III)	Если вид кривой плотности распределения неизвестен и нельзя сделать сколь бы то ни было обоснованных допущений о ее характере, можно воспользоваться каким-либо непараметрическим методом [22, 161]. Используются парзеновские ядра оценок. Каждый объект в пространстве признаков заменяется некоторым ядром, например плотностью нормального распределения с ковариационной матрицей hl (I — единичная ма-40
трица). Могут быть использованы и ядра других типов. Оценка плотности распределения класса определяется теперь как среднее по обучающей выборке класса
^(Х) =^St?(x~xZ,,A)’	(3-7)
/=1
где mt— число обучающих объектов хг,- класса I, а <р(х, /г)—ядро. Оценка плотности распределения зависит от значения коэффициента сглаживания h. Небольшие значения h приводят к получению исключительно островершинных оценок, большие значения h дают очень сглаженные оценки. Разделяющая функция
s/z, (х) = аМх)~/>гМх)	(3-8)
может в принципе быть нелинейной. Все обучающие объекты используются в процессе классификации предъявленного объекта х, причем процесс классификации может оказаться вычислительно неэффективным. Линейная аппроксимация разделяющей функции может быть эффективной [143].
(IV)	Правила ближайшего соседа. Объект зачисляется в тот класс, которому принадлежит его ближайший сосед из обучающего множества (правило ближайшего соседа) или большинство из его К. ближайших соседей (правило К ближайших соседей). Этому методу, однако, свойствен тот недостаток, что все обучающие объекты должны использоваться при получении каждого классификационного решения.
(V)	Оптимизация по какому-либо критерию ошибки. Эвристический метод сводится к оптимизации параметров выбранной разделяющей функции '(линейной, квадратичной или иного вида) по какому-либо критерию ошибки. В качестве последнего можно, например, использовать число неправильно классифицированных объектов из обучающего множества, среднее или «взвешенное» расстояние между обучающим множеством и разделяющей функцией. Полезным может оказаться применение этого метода в сочетании с описанным ниже методом одного контрольного объекта.
(VI)	Иерархическое разделение. Применение дерева решений особенно целесообразно, если число признаков велико. В каждой вершине дерева исследуется один из
41
признаков и в зависимости от его значения выбирается очередная ветвь. В конце концов, в нижней вершине принимается классификационное решение. Подобные деревья являются очень гибким инструментом для использования априорных знаний [83, 85, 88]. К сожалению, оптимальных схем обучения не существует.

Рис. 8. Пример областей, соответствующих отказу от классификации, для случая двух классов. Объект не классифицируется из-за сомнительности ситуации (область пересечения классов, близкая к границе, определяемой разделяющей функцией) или из-за плохогв согласия (области со сравнительно низкой плотностью распределения)
(VII)	Адаптивные разделяющие функции. При решении некоторых прикладных задач приходится в процессе решения изменять разделяющую функцию, т. е. вносить небольшие изменения в значения ее параметров при неправильной классификации одного или нескольких объектов. Этой проблеме специально посвящено несколько работ [101, 105, 117].
Важным понятием дискриминантного анализа является «отказ от распознавания» (рис. 8). В сомнительных случаях (объекты расположены слишком близко к разделяющей функции) или при плохом согласии (объекты расположены далеко от средних значений классов) объекту может быть отказано в классификации. Это означает, что он не классифицируется с помощью разделяющей: функции. Следовательно, при необходимости классификация должна осуществляться другими средствами (например, вручную). Используя отказ от классификации* 42
можно резко повысить качество классификации, хотя число правильных классификационных решений и уменьшается.
Известно несколько методов оценки разделяющей функции на основе оценивания ее классификационной ошибки. Простейшая возможность заключается в применении ее к объектам обучения и подсчете числа неправильных решений. Применение этого метода вносит «оптимистическое» смещение. Другая возможность связана с разделением множества объектов на обучающее и контрольное (метод утаивания имеющейся информации). Обучающее множество используется при этом для формирования разделяющей функции, а контрольное — для оценки ее качества. Применение этого метода приводит к получению «пессимистически» смещенного результата по отношению к разделяющей функции, формируемой на основе полного множества объектов (качество последней в среднем выше качества разделяющей функции, построенной на основе одного обучающего множества). Компромиссом между этим методом и методом использования для контроля обучающего множества является метод исключения из обучающего множества и применения в качестве контрольного единственного элемента обучающего множества. Этот метод предусматривает изъятие из обучающего множества лишь одного объекта, который затем используется для оценки качества разделяющей функции. Процедура повторяется для всех объектов обучения *. Общее число неправильных классификаций дает почти несмещенную оценку классификационной ошибки. Тем не менее оказывается, что дисперсия этой оценки может быть очень велика; к тому же очень значительны и необходимые для получения оценки вычислительные затраты. Возможно также применение компромиссных вариантов, предусматривающих изъятие из обучения и использование для контроля нескольких объектов. Предложено и несколько других методов, почти свободных от смещения и обеспечивающих намного меньшую дисперсию оценки, чем метод исключения из обучения и контроля по одному объекту (обзор таких методов можно найти в работе [153]). Сравнение вычислительной эффективности этих методов проведено в работе [49].
1 В отечественной литературе этот метод иногда называют методом скользящего контроля. — Прим, перев.
43
3.1.3.	Выделение и выбор признаков. Может возникнуть необходимость выбрать наиболее важные из исходного набора признаков или найти новые линейные комбинации из заданных признаков в связи с одним из следующих обстоятельств:
а)	цель исследования состоит в отыскании тех переменных, которые порождают различия между классами;
б)	после применения процедуры выбора признаков должен проводиться дискриминантный анализ; в некоторых случаях (малая ЭВМ, большой объем данных)' необходимо по причинам чисто вычислительного характера на этапе обучения уменьшить число признаков;
в)	для реализации сформированной разделяющей функции может оказаться необходимым уменьшить в максимально возможной степени число признаков; такое уменьшение приводит к сокращению числа измерительных процедур, аппаратуры, размера ЭВМ и времени вычислений;
г)	малое число признаков может существенно влиять на точность дискриминантного анализа, особенно в случае малого объема выборки (см. п. 3.1.5).
Выбор метода выбора/еыделения признаков может определяться целью последнего.
Известно несколько критериев оценки адекватности набора признаков. Естественным, но трудоемким критерием является оценка ошибки классификации одной из разделяющих функций, рассмотренных в предыдущем подразделе, поставленная в соответствие всем допусти-, мым множествам признаков. Рассмотрим более общие критерии, например
<р=колебание средних значений для класса/среднее
колебание для класса.	(3.9)
Применение этого критерия эффективно в тех случаях, когда различия между классами вызываются главным образом различиями средних значений. Если все средние значения одинаковы и, следовательно, <р=0, то осуществлять различение можно лишь на основе моментов высшего порядка. Это принципиальное осложнение; оно свойственно всем критериям выбора и выделения признаков, не использующих ошибку классификации: они могут достигать максимума на неоптимальных ситуациях и принимать минимальное значение при удовлетвори-44
тельных решениях. Критерий Фишера
=	(3.10)
может служить одномерным критерием адекватности /-го признака для разделения классов I и Г; здесь рЛ и ци— средние значения, a oi2i и о3'2г—дисперсии двух этих классов по признаку j. Выражение (3.10) основано на выражении (3.9). С помощью прекрасного метода выделения признаков, основанного на использовании критерия (3.10) [88], определяется линейная комбинация признаков, соответствующая оптимальному значению критерия (3.10), для общего случая L классов.
Критерий Фишера может также оказаться полезным для упорядочения признаков. В подобном методе выбора признаков не учитываются, однако, связи между признаками. Можно доказать, что в общем случае К наилучших признаков не составляют лучшие К признаков (см., например, работу [24]). Следовательно, нужны многомерные критерии. Соответствующим примером служит расстояние Махаланобиса
=	(И/ - Н/Д	(3.11)
где 2 — общая ковариационная матрица классов I и Г. Этот критерий можно интерпретировать как евклидово расстояние между классами, взятое с весами, определяемыми дисперсией разности ц/—цу. Этот критерий особенно важен для классов с многомерным нормальным распределением, которые отличаются лишь средними значениями.
В работе [25] доказано, что в общем случае для отыскания наилучшего подмножества из К.' признаков в множестве из К признаков необходимо исследовать все возможные С к подмножеств из К' признаков. Все остальные методы дают лишь субоптимальный результат. Вычислительная сложность, однако, часто не позволяет использовать этот метод полного перебора. Субоптимальным является метод выбора лучшего признака: выбирается лучший признак и на каждом последующем шаге присоединяется признак, образующий наилучшее подмножество с признаками, выбранными на предыдущих шагах; эта процедура повторяется до тех пор, пока не получается искомый набор из К' признаков. Этот простой метод может обеспечивать очень существенную экономию времени.
46
3.1.4.	Кластерный анализ. Кластерным называют анализ неклассифицированных объектов, проводимый с целью выделения структур, классов, образов, множеств подобных объектов и т. п. До сих пор нет точного определения кластерного анализа. Одной из причин этого является то обстоятельство, что кластерный анализ ис-пользуется и совершенствуется в столь различных обла-стях, как социология, психология, биология, медицина, геология и астрономия. В кластерном анализе не существует однозначного количественного критерия, подобного ошибке классификации в дискриминантном анализе. Такой критерий нельзя сформировать, поскольку в различных прикладных задачах различными могут быть и цели анализа. Иногда необходимо выделить группы с высокой плотностью распределения и низкой дисперсией, а иногда — обнаружить связные точечные структуры.
В литературе описаны сотни методов кластеризации. И все же трудно указать удачное приложение кластерного анализа, основанное на использовании только известных методов. Это отражает то обстоятельство, что для решения задачи кластеризации важную роль может играть ее специфика. В сущности, кластерный анализ тесно связан с исследованиями процесса порождения данных. Многие из тех, кто хочет использовать приемы этого анализа, сами создают новый метод (методы) кластеризации. Хорошим введением в кластерный анализ может служить монография Дуды и Харта [27]. Имеется ряд книг, специально посвященных этому методу [10, 35, 36, 64, 78]. ,
В качестве примеров рассмотрим три разновидности кластерного анализа.
К первой относятся методы, основанные на отыскании моды распределения. Идея этих методов состоит в том, что кластеры соответствуют максимумам плотности распределения источника, порождающего данные. Поэтому необходимо оценивать плотность распределения (например, с помощью парзеновских оценок) и отыскивать все максимумы (моды). Каждый максимум плотности распределения соответствует некоторому кластеру. Каждый объект должен быть отнесен к одному из кластеров. В итоге некоторые кластеры могут быть объединены. Результаты кластеризации тесно связаны со способом оценивания плотности распределения. При ис* 46
пользовании парзеновских оценок число мод может изменяться от одной (при большом коэффициенте сглаживания) до значения, равного числу объектов (при малом коэффициенте сглаживания). Для выбора коэффициента сглаживания можно воспользоваться априорными данными о числе кластеров (если такие данные имеются).
Если число кластеров известно, можно воспользоваться второй разновидностью анализа — методом, в котором в качестве критерия используется отношение внутрикластерной дисперсии к межкластерной дисперсии (ср. с обсуждением-методов выделения признаков, приведенным в п. 3.1.3). Могут использоваться и другие критерии. Почти во всех руководствах по кластерному анализу описывается итеративный самоорганизующийся метод анализа данных — ИСОМАД. В его основу положена идея о том, что объекты принадлежат кластеру с наиболее близким средним значением. Рассмотрим соответствующую процедуру, являющуюся сходящейся. Средние значения для исходного разбиения выбираются случайным образом, но так, чтобы центры были окружены объектами. На втором шаге процедуры проводится отнесение объектов к тем кластерам, центры которых находятся от них ближе всего. После этого подсчитываются новые средние значения для кластеров и повторяется второй шаг процедуры. Последняя быстро сходится. Результат кластеризации может зависеть от выбора начальных средних значений для кластеров. Если кластеры, полученные в результате применения этой процедуры, не являются «истинными», то различное назначение исходных средних может привести к различным результатам кластеризации. Если число кластеров априори неизвестно, процедуру следует повторить для различного числа кластеров.
И наконец, отметим иерархические схемы кластеризации. При их использовании обычно вначале каждый объект рассматривается как отдельный кластер. Затем два ближайших (наиболее похожих) кластера объединяются; этот шаг повторяется вплоть до получения единственного кластера. Использование этого метода предполагает, что некоторым образом определен способ измерения расстояния между кластерами, например расстоянием между двумя кластерами можно считать расстояние между средними значениями кластеров, между
47
двумя ближайшими объектами или между двумя наиболее удаленными объектами. Существует много других способов задания расстояния, и каждый из них порождает свою разновидность кластерного анализа. В результате применения этого метода строится некоторая разновидность дерева, называемая часто «дендрограммой»; последняя отражает процесс последовательного объединения кластеров с учетом соответствующей меры кластеризации. Окончательный вариант кластеризации выбирается по этой дендрограмме вручную.
Важной проблемой кластерного анализа является выбор расстояния (см. § 1.12) между объектами или кластерами, которое называют также сходством или мерой различия. В литературе описано много соответствующих предложений. Они часто связаны со спецификой конкретной задачи, хотя иногда имеют и более общий характер, как, например, нечеткая мера сходства, введенная в работе [5]. Часто имеет смысл решать задачу с использованием нескольких методов кластерного анализа и при выборе окончательного варианта кластеризации учитывать различия и сходство полученных результатов. Этот прием позволяет до определенной степени оценить надежность методов кластерного анализа. Один из методов сопоставления результатов кластеризации, полученных разными способами, предложен в работе [129]. Часто очень полезно при выборе процедуры кластеризации и оптимизации параметров использовать одну из разновидностей интерактивной системы в сочетании с двухмерным отображением условных математических ожиданий данных или оценок плотностей распределения. Имеются обширные библиотеки машинных программ для кластерного анализа; в каждой программе предусмотрено значительное число управляющих параметров [164].
3.1.5.	Число признаков и объем выборки. В статистическом распознавании образов объем исходных данных имеет большое значение. Если объем выборки мал, то свойства классов оцениваются грубо и следует применять лишь глобальные методы, требующие учета незначительного числа параметров. Обычно это сводится к использованию линейного разделения и простых методов выбора признаков, причем методы кластерного анализа позволяют выделить только очень явно выраженные кластеры. С увеличением объема выборки по-48
вышается точность и появляется возможность обнаруживать больше деталей; кроме того, могут использоваться и более тонкие методы. Однако выборки большого объема трудно не только получать, но и обрабатывать. Для работы с ними требуются большие ЭВМ. и много машинного времени.
Маленький набор признаков полезен со статистической точки зрения. Предполагается, что небольшое число переменных выбирается с помощью средств нестатистического характера и что этого набора достаточно для решения задачи распознавания. Поэтому отпадает необходимость в выборе или выделении признаков. Если добавить к имеющемуся набору новые признаки, разделяющая сила множества признаков может увеличиться и соответственно улучшится качество распознавания. Возможен и противоположный эффект: увеличение числа признаков означает увеличение размерности и, следовательно, числа параметров, требующих оценивания. Вследствие этого ошибки оценивания будут возрастать, что может привести к понижению качества распознавания. Итак, существует оптимальный набор признаков. Как при сжатии, так и при расширении этого набора понижается качество распознавания. Это явление называют образованием острых максимумов [17, 30]. Одна из главных проблем, связанных с образованием острых максимумов, состоит в том, что вряд ли возможно на основании заданного обучающего множества выбрать оптимальное подмножество признаков. Методы выбора признаков, упоминавшиеся в п. 3.1.3, не учитывают ошибок оценивания параметров. Следовательно, необходимо создать новые методы выбора признаков, учитывающие существование острых максимумов.
3.2.	Нечеткие методы
3.2.1.	Нечеткие множества. Л. Заде ввел понятие нечеткого множества, в котором принадлежность некоторого элемента такому множеству может принимать любое значение в диапазоне 0—1 [165]. Это предложение являлось попыткой квантифицировать и формализовать всякого рода неопределенные и интуитивные утверждения типа «теплый день» или «продолжительное путешествие». День может быть элементом множества жарких дней со значением принадлежности 0,7 и 4—115	4&
элементом множества холодных дней со значением 0,1. (Сумма этих двух значений не обязательно должна быть равна единице).
В теории нечетких множеств приходится вводить новые определения для объединения и пересечения множеств. Если, например, А и В — нечеткие множества и /л(х) и указывают значения принадлежности некоторого элемента х множествам 4 и В, то принадлежность к XU5 можно определить как
(х)=тах{/л(х), /в(х)},	(3.12)
а принадлежность к — как
/дпа.(х) =пйп{/а (*):	(3.13)
Возможны и другие определения.
Предпринимались многочисленные попытки использовать теорию нечетких множеств в различных приложениях [47]. Здесь мы ограничимся обсуждением некоторых возможностей, связанных с распознаванием образов.
3.2.2	Нечеткие метки. Метки, указывающие принадлежность объектов обучающего множества к соответствующим классам, могут быть нечеткими. Это означает, что специалист должен классифицировать объект с учетом всех возможных классов. Так, кардиограмма определенного характера может соответствовать нескольким разновидностям сердечных заболеваний, но также и здоровому сердцу. Это обстоятельство отражают значения принадлежности ко всем классам заболеваний и к классу нормы. Отметим, что значения принадлежности соответствуют «возможностям», но не вероятностям.
Если при распознавании вместо «классических» меток, указывающих принадлежность точно к одному классу, пользоваться нечеткими метками, то результаты классификации могут оказаться более точными, поскольку на этапе обучения используется больший объем информации. Кроме того, отпадает необходимость «чистки» обучающего множества, поскольку все объекты, в том числе сомнительные случаи и «выбросы», могут быть помечены. Все это обеспечивает возможность работать с более репрезентативным обучающим множеством.
50
3.2.3.	Нечеткие признаки. Еще одна возможность проявления нечеткости связана с «размыванием» признаков. Обычно признаки представляют собой результаты каких-то объективных измерений и не содержат нечеткостей. Значения признаков, однако, могут быть сделаны нечеткими посредством отображения на интервал [0,1], например, в следующем виде:
fi (х) = ехр (—а | х—хг0 | ₽).
Здесь аир — положительные постоянные, подлежащие определению; х1о — некоторое «идеальное» значение признака для класса I. В процессе классификации признаки могут объединяться с помощью формул типа' (3.12) и (3.13).
3.2.4.	Нечеткие классификации. С помощью описанных выше процедур можно вычислить значения принадлежности для всех классов. Нечеткость результата классификации можно устранить, относя объект к тому классу, которому соответствует наибольшее значение принадлежности. Существует, однако, и другая возможность— рассматривать значения принадлежности как окончательный результат процесса распознавания. В этом случае для принятия решения следует применить иные методы или доверить его вынесение человеку, который должен использовать при этом вычисленные значения принадлежности.
Нечеткие классификации такого рода можно использовать в кластерном анализе при формировании критерия выделения кластеров [5]. В этом, как и во многих других случаях, теория нечетких множеств применяется для получения гибкого и исчерпывающего описания реально используемой стратегии.
3.3.	Лингвистические методы
3.3.1.	Введение. В лингвистическом подходе к распознаванию признаками служат подобразы, называемые непроизводными элементами, а также отношения между ними, характеризующие структуру образа (см. § 1.7 и 1.11). Для описания образов через непроизводные элементы и их отношения можно использовать некоторый «язык» образов. Правила такого языка, позволяющие составлять образы из непроизводных элементов, называются грамматикой. При этом образ пред-4*	51
ставляется некоторым предложением в соответствии с действующей грамматикой.
Для распознавания некоторого образа необходимо в первую очередь определить его непроизводные элементы и отношения между ними, после чего следует провести (синтаксический) анализ с тем, чтобы установить, согласуется ли описание образа с грамматикой, которая могла бы его породить; такой анализ часто называют « (грамматическим) разбором».
Синтезировать грамматику можно, опираясь на априорные сведения об образах или на результаты анали-
Блек преВваритель-
1 ’//ой обработки
БЛок выделения непроизводных элементов и отношений между ними.
блок распознавав и -пая (грамма -тического раз-
борд} класс*
Грамматика
£ьНорм-_ рЛОК
ВЫгЫраза. .грамматики
Рис. 9. Структурная схема лингвистической системы распознавания образов
за некоторого конечного множества репрезентативных образов (вывод грамматики).
Структурная схема лингвистической системы распознавания приведена на рис. 9.
Читатель, интересующийся подробностями, выходящими за пределы этого короткого обзора, может обратиться к работам [39, 41, 44, 52, 104].
3.3.2.	Грамматики и языки. Грамматика образов может быть использована для порождения предложений, представляющих некоторый образ, и для грамматического разбора предложений, цель которого состоит в определении соответствия их структуры применяемой грамматике. Рассмотрим порождение предложений с помощью нескольких грамматик, интересных с точки зрения обработки изображений.
Порождение предложения начинается с некоторого начального символа S, принадлежащего некоторому множеству так называемых вспомогательных символов Va- Правило, входящее в набор правил R некоторой грамматики, можно применить для преобразования начального символа S в некоторую цепочку символов, например S->-aA; это означает, что символ S заменен сим-.52
волами аА. Некоторые символы, входящие в такую цепочку, могут принадлежать множеству вспомогательных символов Ул, однако некоторые другие символы могут принадлежать множеству непроизводных элементов Vp. Эти элементы будем обозначать строчными буквами, а вспомогательные символы — заглавными. Вспомогательные символы, входящие в цепочку, полученную в результате преобразования, могут быть подвергнуты новому преобразованию в соответствии с правилами используемой грамматики и т. д. Предложение считается построенным, когда в нем содержатся только непроизводные элементы. Грамматики и типы правил определяются теорией, обладающей высокой степенью формализации.
Пример 1. Воспользуемся очень простой грамматикой. Заданы: яепроизводные элементы а, Ь, с и d, так что VP = {a, b, с. d}; вспомогательные'символы Va={S, А, В, С, D}', правила /?={5->-аД,
S-xC, S-+dD, A->~b, B->-c, C-*-d, D-*-a}. Можно вывести четыре предложения (знак => обозначает вывод): S=>aA=>ab; S=> =>&В=ф-Ьс; S=xC=>crf; S=>dD^da. Если непроизводные элементы имеют вид, показанный на рис. 10,а, а цепочка представляет некоторую конкатенацию непроизводных элементов (головная часть при-зоединяется к хвостовой), то данная грамматика описывает четыре образа прямого угла, приведенные на рис. 10,6.
Пример 2. Рассмотрим грамматику с более сложными правилами: Va = {S, А, В, С, D}; Vp = {a, b, с}; множество R включает семь правил: R={S-*aSBC, S-+abC, CB^CD, CD-+BD, BD-+BC, bB-+bb, C-x}. Вывод предложения abc имеет вид S=>abC=>abc-, вывод предложения а2Ь2с2 имеет вид S^aSBC^aabCBC=>aabCDC=>aabBDC=s-=>aabBCC=>aabbCC=>-aabbcC=>aabbcc. Можно показать, что данная грамматика определяет язык вида {апЬпсп |п^1}. Если непроизвод-
ь
с
а)
cd
Рис. 10. Четыре непроизводных элемента (а); четыре образа прямого угла (6)
53
ные элементы а, b и с имеют вид, представленный на рис. 11,а соответственно, и цепочка снова представляет некоторую конкатенацию непроизводных элементов, то данная грамматика описывает прямоугольные треугольники различного размера, как это показано на рис. 11,6.
В стохастических (вероятностных) грамматиках используются вероятностные правила вида
рц
а1^ ?/. 0<Р;/< 1,
где рц—'Вероятность замены некоторой строки at некоторой строкой Pj. Если шаги в выводе взаимно независимы, то вероятность.
Рис. 11. Три непроизводных элемента (а); три прямоугольных треугольника (б)
построения предложения определяется произведением вероятностей Ра используемых при его выводе правил.
Пример 3. В грамматике применяется набор правил
2/3	1/6	1/6	1/2	1/3	1/6
R={S^>ab0C, S-^abtC, S^> ab2C, с0,	С->с2}.
Искаженные треугольники, приведенные на рис. 12,6, построены из непроизводных элементов, изображенных на рис. 12,а; вероятности порождения этих искажений треугольников указаны на рис. 12,5 (ср. с [39, гл. 6]).
Грамматики массивов (array grammars) [103] представляют собой двухмерные грамматики, предназначенные для работы с изображениями; эти грамматики оперируют не цепочками, а массивами, элементами которых являются вспомогательные символы, элементы изображения, служащие его непроизводными элементами, и пустые элементы (элементы фона) #.
Пример 4. Рассматривается следующая грамматика: VА — = {S, Т}, Vp={a, #}; правила грамматики приведены на рис. 13,а. Вывод треугольника со стороной, длина которой равна трем, представлен на рис. 13,6. Использование «параллельных» правил вместо «последовательных» ускоряет процесс вывода.
Применяя матричные грамматики (matrix grammars) [138, 139] и веб-грамматики [122], можно порождать более сложные или специальные изображения.
Правила преобразования вспомогательных символов (в том числе начального символа S) могут отличаться 54
Рис. 12. Семь непроизводных элементов (а); девять искаженных треугольников (б)
аЬгс,	ab2c2
18	36
#	#	#
	#	#
S	#	#
#	#	#
S	#	#
а	а	#
а	а	г
#	#	#
5	#
а	т
т	
а	
а	#
а	г
#	*	#
5	#	#
а	г	#
#	#	#
S	#	#
а	т	
а	т	
#	#	#
S	#	#
а	т	#
а	а	#
#	#	#
S	#	#
а	а	#
а	а	а
#	#	#
а	#	
а	а	#
а	а	а
#	#	#
а
6
Рис. 13. Четыре правила подстановки (а); вывод треугольника (б)
55
значительным разнообразием. Правило вида ЬВ->-ЬЬ из примера 2 означает, что символ В может быть заменен символом b только в тех случаях, когда перед В стоит Ь; таким образом, в данном случае имеет значение контекст вспомогательного символа. Грамматика, включающая подобное правило, называется грамматикой составляющих. Согласно Хомскому [20] можно выделить четыре типа грамматик:
тип 0: рекурсивно перечислимая или неограниченная грамматика;
тип 1: грамматика (непосредственно) составляющих (НС-грамматика);
тип 2: бесконтекстная грамматика (КС-грамматика); тип 3: регулярная грамматика.
Все правила любой регулярной грамматики предусматривают замену некоторого вспомогательного символа некоторым непроизводным элементом, за которым следует некоторый вспомогательный символ, либо только некоторым непроизводным элементом. Можно сформулировать это правило по-другому: некоторый вспомогательный символ заменяется некоторым вспомогательным символом, за которым следует некоторый непроизводный элемент, либо только некоторым непроизводным элементом.
Язык относится к типу I, если он порождается грамматикой типа i, i=0(l)3. Можно доказать, что ЬзсЬ2с:Ь1сЬ0 (иерархия Хомского), где L,—семейство» объединяющее все языки типа i [20].
В примере 1 использована регулярная грамматика, в примерах 2 и 4 — грамматики составляющих и в примере 3 — бесконтекстная грамматика.
3.3.3.	Деревья вывода. Вывод предложений, порождаемых бесконтекстными грамматиками, можно представить с помощью дерева вывода. На рис. 14 приведены деревья вывода для примера 1. Корнем дерева служит начальный символ S; выводимое предложение образуют (слева направо) листья на концах ветвей. Каждое дерево вывода порождает одно предложение. Большинство грамматик позволяет порождать большое, иногда бесконечное число предложений, поскольку допускается возможность выбора (определяемого, возможно, вероятностями).
3.3.4.	Деревья решений. Внешне эти деревья подобны деревьям, изображенным на рис. 14. В простейшем 56
случае из каждой вершины «растут» две ветви: одна соответствует решению о наличии некоторого признака, другая — о его отсутствии. Дерево решения не содержит информации о процессе вывода в том виде, как он определен выше; это дерево показывает (иерархически), какие признаки (в данном случае — какие непроизводные элементы и отношения между ними) присутствуют. Хотя можно построить грамматику, описывающую про-
Рис. 14. Деревья вывода для примера 1
цесс вывода в соответствии со структурой дерева решения, довольно часто строятся и используются только деревья. Обычно процедуры, связанные с использованием деревьев решений, относят к лингвистическому распознаванию.
Деревья решений имеют некоторое сходство с иерархическим разделением, рассмотренным в п. 3.1.2, однако в последнем случае решение в каждой вершине принимается исходя из статистических свойств соответствующего признака; если же речь идет о дереве решений, то решение, принимаемое в некоторой вершине, должно определять наличие или отсутствие некоторого признака. На рис. 15 представлен типичный пример дерева решений.
Очевидно, что фигуры, построенные из отрезков линий, в частности символы, поддаются описанию с помощью дерева решений подобного типа. В случае более сложных структур из одной вершины может расти несколько ветвей (например, присоединение горизонтального непроизводного элемента справа к нижнему концу вертикального непроизводного элемента, присоединение горизонтального непроизводного элемента к нижнему концу вертикального непроизводного элемента как справа, так и слева или отсутствие горизонтального непроизводного элемента).
3.3.5.	Распознавание. Распознать изображение, описываемое с помощью некоторой грамматики, означает
57
определить, является ли представление этого изображения через его непроизводные элементы и их отношения синтаксически правильным и, следовательно, принадлежит ли оно к образам, задаваемым соответствующей грамматикой. Если оказывается, что образ не определяется с помощью этой грамматики, то либо он отклоняется, либо для его анализа должна использоваться другая грамматика.
Рис. 15. Пример дерева решений. Вершина Г. определяется наличие или отсутствие вертикального непроизводного элемента. Вершина 2а: определяется наличие или отсутствие горизонтального непроизводного элемента справа от нижней части вертикального непроизводного элемента. Вершина 2Ь: определяется наличие или отсутствие криволинейного непроизводного элемента указанного на рисунке вида. Вершины 3: определяется наличие или отсутствие горизонтального непроизводного элемента справа от верхней части вертикального непроизводного элемента. Вершины 4: определяется наличие или отсутствие горизонтального непроизводного элемента в середине вертикального непроизводного элемента
При проведении грамматического разбора снизу вверх дерево вывода должно быть восстановлено, начиная с терминальных элементов, посредством применения грамматических правил в обратном порядке. Терминальный элемент а предложения ab (из примера 1) можно получить с помощью как правила D—^a, так и правила 5->аЛ; вспомогательный элемент D порождается правилом S-^dD и, следовательно, не приводит к получению ab\ поскольку S-^aA в сочетании с дейст-58
вительно позволяет получить предложение ab, последнее считается допустимым. Предложения вида’ ас и ad отклоняются. Общий метод разбора снизу вверх разработан в теории автоматов [69]. Можно показать, что языки, допускаемые автоматами определенного типа, представляют собой языки, порождаемые грамматиками определенного типа. Предложения, порожденные с помощью регулярных, бесконтекстных, рекурсивно перечислимых грамматик и грамматик составляющих, допускаются конечными автоматами, автоматами с магазинной памятью, машинами Тьюринга и линейными ограниченными автоматами соответственно. Применение регулярных грамматик и особенно грамматик составляющих не вызывает особых затруднений.
При грамматическом разборе сверху вниз грамматические правила применяются в обычной последовательности, начиная с начального символа и до тех пор, пока анализируемое предложение будет или не будет обнаружено.
Если некоторое дерево решений представляет задачу (см. п. 3.3.4), то распознавание предполагает проверку наличия или отсутствия некоторого признака в каждой вершине. Признаки используются, а часто и определяются последовательно в соответствии со структурой дерева. В медицинской диагностике, биологических классификациях и других задачах методы, основанные на последовательном опросе, используются уже давно; ответы, получаемые в процессе этого опроса, определяют маршрут продвижения по дереву решений. Описание алгоритмов грамматического разбора можно найти в монографии Ахо и Ульмана [2].
3.3.6.	Вывод грамматики. Задача заключается в отыскании (выводе) некоторой грамматики по некоторой конечной выборке предложений некоторого языка (положительные примеры), а иногда и с учетом некоторого конечного числа предложений, не принадлежащих этому языку (отрицательные примеры). Положительные примеры должны обладать структурной полнотой в том смысле, что все грамматические правила должны применяться при порождении по крайней мере одного из этих выборочных предложений. Известно несколько соответствующих методов [6, 42, 43]; по большей части они весьма сложны даже для случая регулярных грамматик.
59
3.3.7.	Заключительные замечания. Теория формальных грамматик, входящих в иерархию Хомского, и теория автоматов хорошо развиты, однако проблемы, возникающие при их практическом применении, не столь просты.
Выбор непроизводных элементов осуществляется на основе априорных сведений и интуиции; если оказывается, что не удается построить простое описание изображений, то может потребоваться смена непроизводных элементов. Могут возникнуть трудности при отыскании непроизводных элементов на реальных изображениях. Если непроизводными элементами служат линии, то для обнаружения и прослеживания линий и разделения их на прямолинейные и криволинейные отрезки можно разработать специализированную аппаратуру и программное обеспечение [92, 164].
Правила грамматики задаются обычно на основе априорных сведений (свойств хорошо выписанных символов, хромосом с четкими очертаниями). Вывод правил на основе выборки предложений (образов) возможен, но труден и используется в распознавании не часто.
Автоматы осуществляют разбор. При решении прикладных задач используются главным образом простые грамматики процедуры разбора. Популярны бинарные деревья решений.
При использовании вероятностных грамматик можно работать с искаженными изображениями, если искажения точно определены, что в реальных задачах составляет большие трудности. Целесообразно до начала грамматического разбора очистить изображение от шума и искажений, воспользовавшись методами восстановления и улучшения качества изображения. Поскольку подобное очищение не будет идеальным, совпадение с (идеальными) предложениями некоторой грамматики установить не удастся. Допустив возможность некоторого (опять четко определенного) рассогласования (определенное число элементов не согласуется с грамматикой), можно уменьшить влияние этих трудностей. Другая возможность ее разрешения связана с использованием грамматического разбора, обеспечивающего исправление ошибок [150; 151]. Могут применяться и нечеткие методы [149].
Лингвистические методы распознавания применяются (иногда для решения отдельных подзадач) в различ-60
ных прикладных областях, в частности для анализа фотографий, полученных с помощью пузырьковых камер (см. п. 4.1.1), в материаловедении (см. п. 4.1.5), в биологии и медицине (см. п. 4.2.1), для обнаружения дефектов промышленных объектов, деталей машин и механизмов (см. п. 4.2.4), распознавания символов (см. п. 4.2.5), классификации отпечатков пальцев (см. п. 4.2.6), распознавания речи (см. п. 4.2.7), дистанционного обследования окружающей среды (см. п. 4.2.8),. анализа формы, для распознавания (двухмерных) математических выкладок и т. д. Ряд примеров решения подобных прикладных задач описан в сборнике [41], там же имеется и обширная библиография по этому вопросу.
4.	ПРИКЛАДНЫЕ ЗАДАЧИ РАСПОЗНАВАНИЯ ОБРАЗОВ
4.1.	Применение в физике
4.1.1.	Ядерная физика. Применения методов распознавания в ядерной физике довольно разнообразны— от управления энергетическими ядерными установками [51, 91] до анализа траекторий элементарных частиц. В биологической и медицинской кибернетике (см. п. 4.2.1) методы ядерной физики и распознавания образов применяются совместно в задачах, связанных с получением изображений тела человека с помощью гамма-квантов или позитронов. Кроме того, обработка изображений может использоваться для контроля качества в ядерной технике. Методы масс-спектрометрии (см. п. 4.1.6) и радиоактивационного анализа (см. п. 4.1.2) также используются совместно с распознаванием образов в ядерной физике.
Ниже мы остановимся на применении распознавания в физике высоких энергий (физике элементарных частиц), поскольку, вероятно, именно в этом направлении впервые распознавание было использовано в явном виде. Более подробно эта тема уже обсуждалась в данном журнале [78]; после этого был опубликован обзор [99].
61
Физика высоких энергий изучает реакции между’ элементарными частицами посредством анализа их, траекторий, в частности в некотором магнитном поле. Придя на смену камерам Вильсона, пузырьковые камеры стали как массовую продукцию выдавать записи экспериментальных данных на пленке (всегда, по крайней мере, три проекции для одного момента времени); свой вклад стали вносить также стримерные камеры. .Полученные таким образом данные (пленки) с помощью высокоточных развертывающих устройств с бегущим лучом или оптико-механических развертывающих устройств подвергаются измерению и дискретизации. Более того, дрейфовые и проволочные камеры воспроизводят непосредственно цифровую измерительную информацию, записанную на ленте. При обработке данных следует учитывать специфику каждого источника, определяющую различия в уровне априорных сведений и возможностях использования интерактивного режима. В важных априорных сведениях содержатся законы сохранения (однако незаряженные частицы могут ускользнуть незамеченными), особенно это относится к компоненте скорости, направленной вдоль магнитного поля, и кривизне трека в параллельной полю проекции. В течение длительного времени в экспериментах с пузырьковыми камерами использовались малые энергии, что приводило к получению траекторий сравнительно простых форм, которые, в конце концов, почти полностью расшифровывались автоматически. В стримерных камерах это уже было не так, и вмешательство человека, стало существенным элементом анализа сложных пучков почти параллельных треков. При использовании проволочных камер возникает проблема восстановления стереологического типа: возможно получение некоторого ограниченного числа одномерных проекций, почти перпендикулярных траекториям. Проблему, связанную с пространственным квантованием, в некоторой степени можно решить, заменив стримерные камеры дрейфовыми, в которых аналоговая интерпретация обеспечивает более высокую точность.
И снова априорные знания позволяют воспользоваться сравнительно простыми и робастными алгоритмами для восстановления траекторий по нескольким наборам трех одномерных проекций. Чтобы должным образом оценить эту задачу, ее следует сравнить с за-
• 62
дачей воспроизведения кровеносных сосудов тела человека при построении трехмерной рентгеновской томограммы по множеству наборов, в каждый из которых входит свыше ста одномерных проекций.
4.1.2.	Геохимия. При геохимических исследованиях измеряется концентрация химических элементов или соединений в образцах вещества для того, чтобы идентифицировать эти образцы или установить их происхождение (см., например, монографию [70]). При этом можно применять несколько методов измерения, таких, как радиоактивационный анализ, масс-спектрография или инфракрасная спектрография.
Концентрации представляют закономерности, которые могут быть полезны для выяснения происхождения геологических и археологических образцов. Среди соответствующих прикладных задач могут встречаться классификации гальки в соответствии с их геологической природой, кремниевых камней по их месторождениям (чтобы восстановить расположение древних торговых путей) и классификация эстуарийного ила на речной и морской.
При решении таких задач применение статистических методов распознавания может оказаться, в частности, полезным в тех случаях, когда неизвестны физические причины возникновения обнаруженных концентраций определенных элементов или соединений (например, при использовании в качестве признаков концентраций микроэлементов) [14]. Однако при этом возникают трудности, упоминавшиеся в п. 3.1.5. Объемы выборок обычно малы, поскольку применение некоторых методов (таких, как радиоактивационный анализ) стоит очень дорого. Число признаков тем не менее часто оказывается большим, поскольку обычно одновременно измеряются концентрации многих элементов. Априорные знания, которые можно было бы использовать при выборе этих признаков, отсутствуют. Следовательно, в данном примере мы сталкиваемся с образованием острых максимумов (см. п. 3.1.5).
4.1.3.	Ультразвуковая визуализация. Первыми системами, предназначенными для получения акустических изображений, были гидролокаторы для обнаружения подводных лодок и регистрации сейсмических сигналов при поиске месторождений нефти. Обе системы излучали акустические импульсы и принимали отраженные 63
сигналы, позволяя вычислять расстояние по времени прихода отраженного сигнала. При сейсмических измерениях используются источник, обеспечивающий излучение сигнала по многим направлениям, и большое число акустических датчиков, принимающих отраженные звуковые волны, предназначенные для синтеза двухмерных изображений структуры области на поверхности Земли; гидролокатор снабжен источником, излучающим в основном в одном направлении, и одним датчиком, принимающим информацию, поступающую в этом направлении, что приводит в целом к получению одномерных результатов. Принцип гидролокации был применен в неразрушающем контроле материалов и в медицине; рабочая частота составляла несколько мегагерц, причем как излучение, так и прием сигнала осуществлялись одним и тем же пьезоэлектрическим преобразователем. Этот подход позволил впервые получить изображение бьющегося сердца [31].
Одномерные результаты, полученные методами типа акустической локации в различные моменты времени или по различным направлениям, можно объединить и синтезировать на их основе двухмерное изображение, воспользовавшись регистрирующими устройствами, фотопленкой или экранами с запоминанием. На ЭВМ можно возложить функции запоминания и объединения данных, а также выполнения процедуры восстановления и улучшения качества изображения, обеспечивающей некоторое повышение предельной разрешающей способности (около 1 мм) и качества изображения (контрастность, шум и мертвые * зоны, возникающие вследствие недиффузности отражения).
Скорость сбора и обработки информации в значительной степени определяется скоростями источника. Помимо отдельных локальных измерений скорости доплеровскими методами быстрые структурные изменения могут регистрироваться лишь посредством быстрой выборки пространственных позиций. При исследовании биения сердца разумной является скорость, равная 50 изображений/с, однако, чтобы обеспечить полную разрешающую способность при регистрации быстрых перемещений сердечных клапанов, требуется около 1000 изображений/с. Следовательно, при получении двухмерных изображений необходимо использовать электронную систему для изменения рабочего положения преобразова-64
теля (сканирования), которое можно осуществлять двумя способами. Предусматривается либо последовательное включение одинаковых одномерных систем, разнесенных каким-то способом (расположенных, например, на одной прямой) и быстро переключаемых £11], либо ряд датчиков подключается с запаздыванием, что позволяет имитировать один «неустойчиво» расположенный датчик с соответственно изменяющейся диаграммой направленности (фазированная антенная решетка) £142, 152]. Первый способ требует принятия компромиссных решений при определении положения датчика, второй— оказывается более сложным в целом из-за наличия схемы задержки. В данном случае ЭВМ снова используется для восстановления и улучшения качества изображения, а также для получения количественных данных, касающихся, например, изменений объема сердца, скоростей движения сердечных клапанов и т. п. Часть соответствующих машинных программ предназначена для реализации методов распознавания и обработки изображений, обеспечивающих выявление структуры и обнаружение краев. Специального внимания требуют методы отображения информации, поскольку врач должен получать легко интерпретируемые изображения. Для восстановления очень полезна также информация о временных изменениях, содержащаяся в последовательности изображений. До сих пор, однако, в процессе обработки эхокардиограмм часто требуется прибегать к помощи кардиологов.
Высокая скорость обработки двухмерных изображений (в том числе их синтез) часто ограничивается скоростью современных вычислительных машин, в связи с чем неизбежным становится отказ от обработки в естественном масштабе времени. Попытки выйти из положения за счет использования параллельной оптической обработки до сих пор не увенчались успехом [15].
4.1.4.	Метеорология. Эта область отличается колоссальным количеством накопленных данных и отсутствием в настоящее время возможности определить физическую сущность связей между всеми этими данными. Поэтому здесь могут найти применение статистические методы. Можно выделить две задачи.
При прогнозе погоды дискриминантный анализ (см. п. 3.1.2) может служить полезным инструментом (см. например, работу [120]). На основании множества из-5—115	65
мерений давления воздуха, температуры и т. п., выполненных в разное время в разных пунктах, можно определить классы «день без осадков» и «дождливый день». Применение статистических методов выбора признаков позволяет определить наиболее существенные для классификации параметры.
Если задача заключается в описании погоды, то можно воспользоваться кластерным анализом (см. п. 3.1.4). Благодаря его применению удается выделить несколько часто встречающихся типов погоды, причем в качестве признаков здесь выступают такие характеристики, как распределение значений атмосферного давления. На втором этапе может быть изучено соотношение выделенных классов с реально наблюдаемой погодой. Еще одна возможность связана с обнаружением или описанием климатических изменений, скажем некоторые кластеры встречаются реже, чем несколько лет назад.
4.1.5.	Материаловедение. Объектами, для изучения которых в материаловедении используются методы распознавания образов, служат полученные с помощью оптического или электронного микроскопа изображения тонких срезов, сечений и поверхностей излома таких материалов, как металлы, композиты и т. д. Эти изображения часто содержат значительное число небольших частиц или включений, очень сильно различающихся по размерам и форме. Некоторые из их параметров имеют чрезвычайно аномальные распределения. Чтобы получить объективное количественное описание таких изображений, необходимо провести множество измерений в различных частях образца; при этих условиях можно установить природу соответствующих распределений и уловить их изменения при запланированном изменении параметров в процессе Лроизводства исследуемого материала. Такие данные необходимы, например, при изучении кинетики роста и связей структуры со свойствами материалов. Чрезвычайно желательна автоматизация обнаружения частиц, рассеянных в некоторой области образца, классификации этих частиц в соответствии с размерами или формой, определения их пространственного распределения и расстояний между отдельными частицами, топологических свойств (таких, как связность частиц, наличие агломераций или тяжей) или распознавания частиц заданных типов. Много вни-66
мания должно быть уделено определению этих свойств; в прошлом по поводу этих определений недоразумения возникали неоднократно. Размеры, например, можно устанавливать, опираясь на площадь, периметр, максимальную или среднюю длину связи и т. д.; мерой функции формы может быть распределение длин случайных отрезков, проходящих через частицу, Фурье-описание и множество других.
Методы обработки, упоминавшиеся в § 2.4 (такие, как поверхностное разрушение, наращивание, разъединение и соединение), хорошо приспособлены для достижения упомянутых выше целей. Для решения подобных задач разработаны специализированные системы обработки изображений, например Quantimet system фирмы Metals Research (Великобритания) и TAS system фирмы Leitz (ФРГ), но для этих же целей можно применять и системы обработки изображений общего назначения.
Многие из описанных выше процедур появились в результате исследований металлических поверхностей. Они, однако, могут применяться во всех тех научных, технических и медицинских задачах, где необходимы данные о характеристиках множества частиц и требуется проводить их статистический анализ. Соответствующими примерами служат изучение структуры дерева, кости и бетона, описание порошков (например, порошкообразный металл или порошок окислов металла), взвесей, аэрозолей, асбестовых волокон, клеток крови, биологических тканей и т. д. Эффективность измельчения можно оценивать, сопоставляя распределения частиц до и после помола. Аналогичным образом можно исследовать материалы, используемые при шлифовке, так же как проблемы загрязнения микрочастицами.
Часто нас интересуют пространственные структуры, причем обычно в этих случаях недостаточно иметь сведения о плоских сечениях, поскольку они лишь частично приоткрывают пространственную геометрию исследуемого материала. Стереология как раз и занимается проблемами количественного описания трехмерных микроструктур на основе задаваемых плоских сечений объекта. Много работ, посвященных проблемам, обсуждавшимся в данном разделе, действительно можно найти в трудах конгрессов по стереологии (в частности, тех, 5*	67
что проводятся Международным обществом по стереологии (International Society for Stereology).
4.1.6.	Спектры. Сплошные спектры, например такие, как спектральные распределения плотности энергии теплового излучения, распознаются с помощью любых методов распознавания, позволяющих классифицировать непрерывные функции. Дискретные спектры можно смоделировать с помощью некоторой суммы дельтафункций (называемых спектральными линиями), соответствующих различным позициям; наличие определенной группы спектральных линий служит характеристикой источника излучения, например его химического состава (масс-спектры, атомные эмиссионные спектры). В реальных условиях спектральные линии уширяются и их форма отражает характеристики источника и процесса порождения спектра. Уширение означает, что линии одной или различных групп спектра могут накладываться друг на друга, в результате чего может возникнуть сплошной спектр. Если расстояние между спектральными линиями достаточно велико, то их положения, интенсивность (площадь) и форма могут быть определены и использованы в процессе распознавания [98]. Иногда лишь небольшая часть этой информации принимается во внимание, как, например, при классификации масс-спектров органических химических соединений, когда имеется очень много спектральных линий, а в качестве экспериментального набора признаков используется лишь факт наличия достаточно интенсивных: спектральных линий в определенных интервалах [144].; Другой типичной задачей спектральной классификации; является разделение перекрывающихся спектральных: линий, т. е. представление некоторой заданной неотри-: цательной функции в виде суммы некоторого заданного; или наименьшего числа неотрицательных функций, форма которых фиксирована, а локализация, интенсивность, и ширина неизвестны. Известно несколько алгоритмов, позволяющих разлагать подобные функции на функции нормального распределения (см. § 2.3), причем в качестве признаков для статистического распознавания используются среднее значение, амплитуда и среднеквадратичное отклонение. Общий способ разложения до сих пор неизвестен. После того, как локализация и т. п. определены, часто остается нерешенной задача распознавания характеристических групп спектральных ли-68
ний, причем группы эти могут перекрываться, а утраченные или слившиеся спектральные линии могут служить источником очень серьезных ошибок. Подобные задачи возникают при классификации окрашенных хромосом на основе закономерностей их оптической экстинкции в метафазе (характера исчерченности хромосом).
4.2.	Приложения распознавания образов, не относящиеся к физике
4.2.1.	Биологическая и медицинская кибернетика. В биологии и медицине возникает множество задач распознавания различных типов. Иногда распознавание используется как альтернатива способностям человека извлекать информацию из изображений (например, разделение клеток крови на несколько классов и подсчет их числа, обнаружение патологий по рентгенограмме), позволяющая обойтись без (дорогостоящего) труда человека, особенно при выполнении большого объема утомительной работы; в этом направлении еще нельзя говорить о полном успехе. Часто распознавание используется для получения более объективных и более «количественного» характера данных, чем те, которые в состоянии собирать человек. Исходные данные часто представляются в виде изображений, но в принципе могут применяться все виды клинических данных и наблюдений. Мы приведем несколько примеров.
Медицинская диагностика часто сводится к дифференциальному диагнозу, т. е. к выбору одного из нескольких заболеваний, причем при таком выборе учитывается и возможность наличия нормы (отсутствие какого-либо заболевания). Диагностические тесты (результаты опроса пациента, клинические данные, история болезни) образуют исходные данные для диагностики, из которых (при автоматическом распознавании) формируется для каждого обследуемого некоторый вектор симптомов (одно из затруднений может заключаться в том, что некоторые входные данные непрерывны, в то время как другие дискретны или имеют логический характер). Затем следует сформировать обучающее множество, включающее описания больных, действительно страдающих соответствующими заболеваниями, и описания людей, у которых этих заболеваний нет;
69
кроме того, для обеих групп должны быть заданы априорные вероятности. Теперь все методы из арсенала статистического распознавания можно применить для классификации нового пациента, т. е. для отнесения его к одному из классов заболеваний или классу нормы. При практическом использовании этого подхода возникают трудности, связанные со значительной изменчивостью векторов симптомов, соответствующих разным классам; эта изменчивость вызывается как существованием биологических различий непатологического характера между отдельными людьми, так и разнообразием способов влияния патологических процессов на норму (локализация, интенсивность и проявления). Очень трудно сформировать репрезентативное обучающее множество, включающее все возможные возрасты, расы, образы жизни и истории болезни для всех пациентов; данные, входящие в обучающее множество, с течением времени изменяются. Данные, используемые при построении вектора симптомов, часто не очень надежны из-за наличия ошибок измерения, неоднозначно определяемых величин, неточностей и т. д. Все эти трудности, однако, возникают и при постановке диагноза человеком! Опыт врача и использование некоторых не сформулированных в явном виде данных (а возможно, и интуиция) позволяют (иногда) избежать вынесения неверных диагностических решений. Более того, ошибки, сделанные системой распознавания, будут оцениваться иначе, чем ошибки врача. Успехи в автоматизации диагностики обычно наблюдаются в тех случаях, когда следует различать небольшое число сходных заболеваний при наличии обширных статистических данных [58]. Сочетание автоматической диагностики и постановки диагноза человеком может помочь избежать врачебных ошибок. Полезной может оказаться и частичная автоматизация диагностики, когда решение, полученное автоматизированной системой, интерпретируется врачом, например пики, выделяемые на электроэнцефалограмме автоматически, должны интерпретироваться невропатологом.
Существенное внимание уделяется автоматическому анализу изображений мазков крови, цервикальных мазков, хромосомных препаратов [17, 57, 102, 126] и т. д., целью которого являются обнаружение и классификация клеток и хромосом различных типов, позволяющие 70
затем выделить объекты с отклонениями от нормальной структуры, определить их число и оценить характер отклонений количественно. В этой сфере мы снова сталкиваемся со значительной биологической изменчивостью и затруднениями при объективном определении адекватных признаков, однако о некотором прогрессе говорить уже можно. В трудных случаях преимущество все еще принадлежит хорошо обученным и действующим осмысленно специалистам. Существуют серийные системы для классификации и подсчета кровяных клеток. Для обработки мазков крови в настоящее время используется развертывающее устройство с бегущим лучом,, разработанное для обработки фотографий, получаемых в пузырьковых камерах (BioPEPR) [167].
Значительное внимание уделяется также рентгеновским, радиационным и ультразвуковым изображениям. Обработка используется для восстановления или улучшения качества изображений, предлагаемых для анализа человеку, и для получения числовых характеристик изображений, иногда в интерактивном режиме с участием человека. Эхокардиограммы могут применяться для измерения скорости движения (частей) сердечных клапанов и для определения объема крови, перекачиваемой за одно биение сердца. Использование распознавания для обнаружения (частей) клапанов и стенок левого желудочка (распознавание может осуществляться в интерактивном режиме) позволяет определять указанные величины (полу) автоматически. То же самое относится и к ангиокардиограммам (проекциям сердца, получаемым в рентгеновских лучах). Проблемы автоматизации анализа тканей и изменений формы по рентгеновским и радиационным изображениям также являются предметом исследований [62].
Восстановление трехмерных изображений, например? мозга, по двухмерным проекциям находится уже на достаточно хорошем уровне и осуществляется с помощью) систем, построенных на основе ЭВМ [19, 148]. Интерпретация остается главным образом объектом приложения способностей человека к распознаванию. В трудах большинства конференций, посвященных распознаванию образов [например, Международные объединенные конференции по распознаванию образов (International Joint Conferences on Pattern Recognition)], содержится много-статей, посвященных биомедицинским приложениям'
71
распознавания; см. по этому поводу также Труды состоявшегося в 1976 г. Симпозиума по машинной диагностике медицинских изображений [1976, Proceedings of the Symposium on Computer-aided Diagnosis of Medical Images (IEEE Computer Society)} и специальный выпуск, посвященный обработке и анализу биологических сигналов (ТИИЭР, 1977, т. 65, № 5).
4.2.2.	Социология и экономика. Кроме зрительных, слуховых и тактильных образов человек также имеет дело с образами более абстрактного характера (регулярности, см. § 1.2), возникающими, например, в социально-экономической сфере. Заманчиво и для их распознавания воспользоваться понятиями и методами принятия решений, разработанными в распознавании образов. Результаты, получаемые в этом направлении, до сих пор остаются весьма скромными, однако некоторые из используемых подходов заслуживают внимания [7, 8, 40]. В качестве примера рассмотрим определение групповых предпочтений посредством объединения индивидуальных предпочтений. Хорошо известно, что голосование, основанное на принципе большинства и учитывающее индивидуальные предпочтения по отношению к альтернативам, может приводить к несовместным ситуациям. Рассмотрим, в частности, трех участников голосования, обозначенных номерами 1, 2 и 3, и три альтернативы а, b и с. Если 1 -.а>Ь, то это означает, что первый участник отдает предпочтение а перед Ь\ из а>Ь>с следует, что а>с, и если 1:а>Ь>с, 2-.Ь> >Оа и Ъ'.с>а'>Ь, то с большинством в 2/3 голосов предпочтение отдано а перед b, b перед с и с перед а. Теория неосуществимостей Эрроу [86] точно указывает, при каких условиях подобная несовместность может возникать. Индивидуальное предпочтение можно интерпретировать как некоторый образ, описываемый признаками, принадлежащими некоторому пространству признаков: признак Xi может характеризовать отношение между а и Ь, например &>b-^Xi=l и —нс,=:0; аналогично признак х2 представляет отношение между b и с, а х3 — отношение между с и а; выражение а>Ь>с представляется в данном признаковом пространстве как ПО. Несовместными являются случаи 111 и ООО. Возможно введение количественной оценки предпочтения (а=Х\Ь), что приводит к получению непрерывных пространств. Если задано много образов (точек 72
в пространстве признаков), характеризующих индивидуальные предпочтения участников голосования то воспользовавшись одним из методов кластерного анализа, можно найти «сходства» отдельных участников голосования или сформировать некоторую компромис-
сную альтернативу, находящуюся на наименьшем (евклидовом) расстоянии ото всех образов индивидуальных предпочтений. Парето-решение требует определе-
ния некоторой альтернативы существующей ситуации, которую все участники голосования считали бы наилучшей. Можно доказать, что это решение лежит на выпуклом замыкании всех предпочтений, представленных в признаковом пространстве |40]. В таком случае отдель-
ный участник голосования имеет возможность предотвратить принятие определенных решений.
4.2.3.	Психология (зрительного) восприятия. Знания, касающиеся механизмов (зрительного) восприятия, могут использоваться при разработке алгоритмов для
автоматических систем распознавания, хотя еще не ясно, окажутся ли эффективными в автоматических распознающих системах, рассчитанных на сугубо специ-
альные приложения, решения, заимствованные из живой природы и ориентированные на распознавание множества самых разнообразных ситуаций. Автоматические системы распознавания, оказавшиеся удачными, не копируют природу слепо, подобно тому, как это не имеет места ни в автомобилях, ни в самолетах, ни в кораблях, ни в большинстве известных роботов. Тем не менее сведения о механизмах восприятия могут оказаться полезными. Справедливым может оказаться и обратное: специалисты в области психологии восприятия могут использовать сведения, почерпнутые из распознавания образов, при постановке своих экспериментов и интерпретации их результатов. Они сталкиваются с проблемами, аналогичными тем, которые возникают при построении автоматических распознающих систем; например, какие признаки некоторого образа имеют шанс быть наиболее существенными для человека в процессе распознавания этого образа. Существует обоюдный интерес у этих двух отрядов исследователей,
однако сенсационных результатов пока не видно.
Существует значительное количество данных как экспериментальных, так и теоретических, касающихся зрения, особенно для случая простых (зависящих и не за-6—115	73
висящих от времени) конфигураций, построенных из пиний и точек; эти данные относятся как к начальной фазе (глобального) обнаружения объектов (и к сканированию посредством саккадических движений глаз), так и к заключительной стадии интерпретации (распознавания). Зрительные иллюзии также часто служат объектом изучения. Существует обзор, в котором на техническом языке обсуждаются такие понятия, как контрастность, форма, расположение и текстура; все эти категории объединены термином «психопикторика» [96]. В последнем десятилетии много внимания уделялось построению формальных описаний структур более или менее сложных образов с помощью различных кодов и с привлечением аппарата лингвистики, искусственного интеллекта, теории информации и физиологии [80, 81, 93, 109, 141]. Иногда старые утверждения типа «значительная часть информации об объектах содержится в контуре и, в частности, там, где его направление резко изменяется» [4] переформулируются, принимая более строгий и более подробный характер, но кодирование порождает также и много новых описаний, например, связанных с сегментацией изображения на объекты и фон, текстурой, постоянством размеров, движением и видимым движением, иллюзиями. Все еще остается некоторая надежда использовать часть этих сведений для построения автоматических распознающих систем.
4.2.4.	Техника. Мы кратко остановимся на нескольких обширных областях применения распознавания образов (и обработки изображений) в промышленности. Наиболее важной из них, судя по всему, является или становится таковой контроль качества (быстро) движущейся поверхности стали, бумаги, текстильных изделий и нетканых материалов, контроль качества печати, рисунков или водяных знаков, нанесенных на такие поверхности. При решении этих задач достаточным может оказаться обнаружение нарушений регулярности, но может потребоваться и различение дефектов отдельных типов или разновидностей нарушений поверхности. Люди не очень хорошо справляются с работой такого характера. Для решения таких задач достаточно применить одномерное строчное сканирование (с помощью лазерных сканирующих устройств или линейных решеток фотоэлементов) в сочетании с запоминающим устрой-74
ством для хранения предыдущих строк. Трудности, возникающие при этом, обычно заключаются в точном определении типов дефектов, представляющих практический интерес, и в необходимости быстрой обработки при контроле быстро перемещающихся поверхностей.
Много внимания уделяется контролю и классификации, ориентации и перемещению механически обработанных деталей, полупроводниковых кристаллов и электронных компонент, однако, как указывалось в § 1.14, вследствие изменения организации технологического процесса иногда может отпасть необходимость в решении задач такого типа.
Другой областью приложения распознавания являются: контроль материалов в процессе их производства, цель которого — установить, соответствует ли данная партия продукции определенным стандартам, регламентирующим состав включений, агломератов и т. д.; контроль внутренней структуры на основе анализа рентгеновских и ультразвуковых изображений; дистанционное измерение, например, размеров капель кипящей стали; распознавание символов или кодов в АСУ производством до начала, в процессе и после окончания технологического цикла; поиск чертежей и извлечение необходимой информации из чертежей, хранящихся в памяти ЭВМ; проектирование механических, электрических и архитектурных конструкций в автоматическом и интерактивном режимах на основе использования машинной графики, обработки изображений и методов классификации.
В трудах Международных объединенных конференций по распознаванию образов помещено много статен, посвященных применению распознавания в промышленности. Смотрите также Труды Международного семинара по автоматизации и использованию для контроля качества методов обработки изображений, 1977 [1977, Proceedings of the International Seminar on Automation and Inspection Applications of Image Processing Techniques, SPIE, vol. 130 (London: SIRA)]; целесообразно познакомиться и с обзором, посвященным этим проблемам и помещенным в трудах этого же семинара [159].
4.2.5.	Распознавание символов. Автоматическое считывание стилизованных символов (дорожных чеков) и печатных символов нескольких гарнитур шрифта (сортировка почты) используется повседневно [13]. Одна-6*	75
ко в настоящее время отсутствует какое-либо приемлемое решение задачи распознавания обычного почерка. Наибольшее внимание уделяется задачам, занимающим промежуточное положение между упомянутыми выше, например распознаванию написанных от руки печатных изолированных буквенно-цифровых символов. Имеется обзор, посвященный серийным системам распознавания символов [159]. Для достижения высокого качества распознавания необходимо вводить некоторые ограничения на способы написания символов. Следует при этом иметь в виду, что человек, распознающий рукописные печатные символы при отсутствии контекста, также допускает ошибки, число которых доходит до 4% [145].
Отметим несколько достижений в этой области. Прежде всего, расширилась номенклатура объектов автоматического считывания: теперь имеется возможность считывать не только типографские символы, но и машинописные, символы, напечатанные конторскими счетными машинами и построчно-печатающими устройствами; эти символы подвержены значительно большей изменчивости, чем обычные полиграфические символы. Методы распознавания, основанные на использовании программно-задаваемых масок, применяются аналогично тому, как это делается в случае типографских символов, однако при этом требуются несколько большая степень нормализации, в частности толщины линий, и очень тщательная установка масок относительно считываемого символа. Особую задачу представляет считывание (китайских идеографических) символов «азбуки» Кэндзи, напечатанных на японских пишущих машинках. В этой области часто используются иерархические методы. На первом шаге выделяются группы сходных символов, для чего применяются глобальные признаки. На последующих шагах для разделения символов в группах сходных символов используются все более тонкие признаки. Сообщается об. экспериментальной системе, которая, осуществляя двухэтапную процедуру, обеспечивает распознавание свыше 2000 знаков Кэндзи с точностью, превышающей 99% [45].
В банках, при безналичных расчетах, на почтах для сортировки корреспонденции в соответствии с почтовыми индексами и во многих других учреждениях применяется несколько систем для распознавания цифр, написанных разными людьми и без всяких ограничений либо 76
с очень слабыми ограничениями. При распознавании используются лингвистические признаки типа формы штрихов и множество более сложных, в том числе иногда статистических. Утверждают, что новые системы, часто еще находящиеся в стадии эксперимента, обеспечивают распознавание с точностью 99,5% [64, 145].
Распознавание рукописных буквенно-цифровых символов (в том числе символов Фортрана и азбуки Катакана), основанное на методах, аналогичных используемым при распознавании цифр, проводится с точностью около 95% и выше, если вводятся большие ограничения на способ написания символов. Считывание рукописных знаков Кандзи также вызывает затруднения из-за наличия значительного числа сложных символов. Распознавание набора, содержащего около 2000 символов (набор включает почти все используемые в Японии символы), проводится в естественном масштабе времени с точностью 90—98% (вариации точности зависят от уровня обработки и исключения символов, которым система отказывает в распознавании) [74].
Использование распознавания слов вслед за распознаванием символов позволяет за счет сопоставления со словарями, хранящимися в памяти ЭВМ, и определения максимальной корреляции обеспечить достижение большей точности, чем можно ожидать, исходя из точности распознавания собственно символов [154].
Большинство эксплуатируемых и разрабатываемых систем сложно, дорого, а иногда слишком медлительно. Существует надежда преодолеть эти недостатки с помощью специализированной аппаратуры, поточной обработки и специализированных блоков на больших интегральных схемах.
4.2.6.	Отпечатки пальцев. Данные дерматоглифики (изучение отпечатков пальцев, ладоней и стоп) имеют существенное значение для столь различных областей, как антропология, наследственные заболевания, банковское дело и юриспруденция. В последние 15 лет проводились исследования в области автоматической и полуавтоматической классификации отпечатков пальцев на основе применения методов распознавания образов.
Во всех известных системах используются картина расположения бороздок на отпечатке пальца и так называемые «мелкие детали» (концы бороздок, разветвления и т. п.).
77
Система классификации по Генри [18] не рассчитана на применение автоматических процедур. Ее недостатками являются малое число классов и их неустойчивость. Так, три основных типа расположения бороздок — с контурами, завитками и дугами — встречаются в 60, 30 и 5% случаев соответственно. Поэтому используется модификация этой системы или другая система. Из-за наличия шума и большой избыточности отпечатков пальцев требуется значительная предварительная обработка. После дискретизации и разделения по порогу осуществляются выделение остова, выделение и кодирование бороздок и изолированных частей отпечатка. Некоторые подходы предусматривают построение по. оцифрованному изображению некоторой матрицы выборочных элементов [54]. Каждому выборочному квадрату (окну), образованному примерно ста элементами изображения, присваивается код, соответствующий тангенсу угла наклона большей части проходящих через него бороздок. Топологическая структура отпечатка пальца дает возможность проводить автоматическую классификацию лингвистическими методами.
В одном из проектов [Ю9] для проведения первого этапа классификации по семи основным классам используется бесконтекстная грамматика (см. § 3.3), причем признаками служат топологические свойства четырех расположенных рядом окон. При дальнейшей классификации используются вероятностные бесконтекстные грамматики [107]. Несколько иной лингвистический подход, предусматривающий применение так называемых «треугольников» (фокальных точек отпечатка пальца), описан в работе [129]. В упоминавшихся выше системах использовались грамматики цепочек; в более позднем подходе [108] — грамматики деревьев (двухмерное обобщение грамматики цепочек) на этапе классификации. В работе [32] применены оптические корреляционные методы и цифровая обработка.
4.2.7.	Распознавание речи. Основной задачей этого направления распознавания является разработка методов и систем, в которых речь является входной информацией для различной аппаратуры, ЭВМ, информационно-поисковых систем, систем идентификации личности и т. д. Имеется ряд обзоров, посвященных этой тематике [130, 131 (верификация диктора), НО].
. Простейшая задача сводится к пониманию речи
78
одного человека, произносящего некоторый ограниченный набор изолированных слов, например десять цифр; самая сложная задача — распознавание обычной связной речи множества различных людей. Имеются примеры практического решения очень простых задач.
Распознавание происходит на нескольких уровнях. На нижнем уровне осуществляются разделение и маркировка фонем с помощью признаков, в качестве которых использовались спектральные характеристики коротких отрезков речи, коэффициенты кодирования речевого сигнала с помощью линейного прогнозирования [100], параметры частной корреляции [75], звонкие и глухие фонемы, число пересечений нулевого уровня и т. д., а также параметры голосового тракта, определенные по речевому сигналу. Точность распознавания существенно зависит от числа говорящих и достигает 60% и выше.
При распознавании изолированных слов некоторая цепочка фонем распознаваемого слова сравнивается (после нормализации по времени) с эталонной цепочкой слов соответствующего словаря, хранящегося в памяти, с тем, чтобы обнаружить наиболее сходный объект; при этом принимаются во внимание и лингвистические соображения. Точность распознавания зависит от размера словаря и числа говорящих, но при любых обстоятельствах находится в пределах 80—98%.
Распознавание связной речи — задача еще более трудная, так как неизвестно, где кончается одно слово и начинается следующее. Для распознавания предложений с точностью 50% и выше необходимо использовать синтаксические и семантические характерибтики.
В системах понимания речи важно обеспечить понимание некоторого сообщения, а не просто каждой фонемы и каждого слова. Для этого необходимо использовать прагматику и контекст, а также многократное обращение к режиму ответов на вопросы. При решении отдельных задач (резервирования мест [136]) достигнута высокая точность распознавания (99%).
4.2.8.	Дистанционное зондирование. При дистанционном обследовании изображения отдельных участков земной поверхности поступают от бортовых самолетных и спутниковых датчиков. Расстояние до земли изменяется от 300 м до 300 км. Данные, поступающие от датчиков, имеют главным образом спектрозональный ха-
79
рактер (видимый и инфракрасный диапазоны), исполь-; зуются и радиолокаторы бокового обзора.	’
Дистанционное зондирование может применяться для< решения множества задач: мониторинг качества окру- < жающей среды, выявление геологических формаций или; археологических объектов [135], составление географи-j ческих карт и карт землепользования, классификация обработанных полей, определение стадии развития и, выявления заболеваний сельскохозяйственных культур, и т. д.
Причиной размывания или искажения изображения^ могут быть перемещения датчика, рассеяние света ат-, мосферными частицами [89], шум, специфика переда--точной функции точки датчика, его положение и ориен< тация относительно поверхности земли и т. д. Сущест- ] вует множество способов коррекции изображения. 1
Для обработки получаемых видеоданных (для спут-] ника Landsat их объем составляет около 1013 бит в год)] требуются ЭВМ, что, в свою очередь, предполагает осу-] ществление автоматической классификации. Спектрозо-] нальные данные часто коррелировали; применение ана-1 лиза методом главных компонент (преобразование Да- | рунена — Лоэва) позволяет уменьшить объем данных и ) выделить некоррелированные признаки [25]. В основе анализа изображений могут лежать статистические ме-i тоды, текстурная информация [60, 162], построение на изображении областей [33], непараметрическое сравнение локальных Гистограмм изображения [112] или специализированные методы, предназначенные для решения конкретных задач, например обнаружения и подсчета зданий [Ш]. Получаемые результаты существенно зависят от используемых данных и поставленных целей, тем не менее возможности их практического ис-I пользования выглядят обнадеживающе [95, 146, 147].|
5.	ТЕНДЕНЦИИ И ПЕРСПЕКТИВЫ * 80
Как следует из материала предыдущих разделов, задачи, объединяемые под названием «распознавание образов», очень разнообразны. Не существует универсального подхода к их решению; предложено несколько довольно общих теорий [55, 56, 60, 119], позволяющих решать многие задачи, однако приложение их резуль-
80
татов до сих пор затруднительно; много теоретических результатов получено для специальных случаев и подзадач. Сердцевиной всех затруднений распознавания является, однако, проблема выбора признаков. Приходится определять даже тип признака и устанавливать, позволяет ли он проводить статистическую, нечеткую или структурную обработку. Разумный выбор признаков требует использования априорных знаний об образах, интуиции и метода проб и ошибок. Применяя статистические методы, можно определить плохие признаки, выбрать и упорядочить признаки в соответствии с некоторым критерием полезности или объединить признаки и сформировать меньший набор лучших признаков, но нельзя найти новые, хорошие признаки. Действительно, хорошие признаки могут даже «обмануть» статистические процедуры! Поиск единого универсального подхода, возможно, также бессмыслен. Для большинства технических и физических задач, особенно если они относятся к достаточно обширным направлениям, общих решений не существует.
С этими проблемами связано и существование определенной несбалансированности между развитием теории и созданием реальных систем распознавания. В основе многих теорем теории статистических решений лежат понятия расстояния и мер близости, в свою очередь основанные на определенных допущениях относительно характера соответствующих распределений, но при решении реальных задач число обучающих объектов часто оказывается недостаточным для определения этих распределений с приемлемой точностью или реальные распределения очень сильно отклоняются от их идеализированных теоретических моделей. Как отмечалось [84], некоторые средства, заимствованные из лингвистики и статистики, не были должным образом приспособлены для решения задач распознавания; упоминались, в частности, «бремя отношения конкатенации» и «обработка слева направо», а также «жесткие процедуры грамматического разбора строго сверху вниз или снизу вверх», применяемые в лингвистическом подходе к распознаванию.
Узким местом удачных реальных систем распознавания являются необходимость выполнения огромного объема вычислений, особенно при обработке изображений, и быстродействие, необходимое для систем, рабо-
81
тающих в естественном масштабе времени. Изображение размером (всего лишь) 256X256 при затрате (всего лишь) 5 бит на один элемент изображения порождает информацию объемом около 3X105 бит. Осуществление двухмерных глобальных преобразований на таком изображении или его линейная фильтрация с помощью некоторого двухмерного фильтра занимают при использовании ЭВМ широкого назначения много времени, вследствие чего стоит дорого, а часто оказывается и слишком медленной с точки зрения требований, предъявляемых к стандартным операциям.
Материал предыдущих разделов показывает, почему прогресс в распознавании оказался более медленным, чем предполагалось в начале 60-х годов. Несмотря на несомненный рост возможностей вычислительных машин, они все еще не могут конкурировать с механизмами восприятия, свойственными человеку. Система глаз (или ухо) — мозг исключительно сложна и гибка, но в то же время она надежна и дешева. Даже хорошо спроектированные и хорошо проявляющие себя в эксплуатации системы, например системы, предназначенные для определения кариотипа (хромосомного комплекса), мало используются практически, так как труд человека дешевле, человек работает быстрее и более гибко реа-. гирует, встречаясь с непредвиденными ситуациями.' Большая часть достижений относится к весьма специфическим задачам с более или менее строго фиксированными ситуациями; в таких успешно работающих си-стемах используются специализированные устройства-(это относится, в частности, к считыванию нормализо--ванных символов, классификации клеток крови и автоматизации научных исследований). В работах, включенных в список литературы, можно найти описание множества частных задач анализа данных научных исследований, в которых успешно применены методы распознавания.
Каковы же перспективы на будущее? На такой вопрос всегда трудно отвечать. Поэтому мы отметим лишь некоторые тенденции и их возможные следствия.
В области теории: желательно установление более тесных связей между статистическим, нечетким и лингвистическим подходами в сочетании с приспособлением средств, заимствованных из этих областей (статистики, теории нечетких множеств и лингвистики), к специфи-82
ческим задачам распознавания; требуется больше априорных знаний о конкретных разновидностях распознаваемых образов, в частности, о способах их порождения; прогресс в распознавании речи, например, может быть достигнут за счет физических исследований голосового тракта и акустических свойств речи, а также за счет лингвистических и психологических (психология восприятия) исследований роли контекста, интонации и т. д.; прогрессу автоматизации процессов распознавания могут способствовать исследования в области зрительного восприятия человека и теории кодирования зрительных образов. Во всех этих, как и во многих других, направлениях наблюдается интенсивная работа специалистов в области распознавания, так что можно рассчитывать на получение искомых результатов.
В области аппаратуры: разработка новых поколений аппаратуры все еще интенсивно продолжается. Общеизвестен прогресс в области микропроцессоров. Можно рассчитывать, что линейные и плоскостные сканирующие устройства на полупроводниковых приборах найдут применение при решении множества различных задач; другой областью, обещающей принести новые достижения, являются системы графического отображения, снабженные средствами работы в интерактивном режиме. Многообещающе выглядят интерактивные системы распознавания, в которых рутинные и трудоемкие операции выполняются автоматически, а вмешательство человека предусматривается при появлении трудных задач распознавания. Важными представляются исследования, посвященные архитектуре аппаратной части систем распознавания. Много внимания уделяется таким концепциям, как параллельная, матричная и потоковая обработки, особенно применительно к работе в естественном масштабе времени и обработке больших объемов данных за ограниченное время. Разрабатывается специализированная аппаратура для восприятия информации и реализации операций, которые часто встречаются при обработке; можно в этой связи отметить систему СЫР [27, 28]; разрабатывается несколько специализированных быстродействующих процессоров изображений.
Оптические вычислительные системы, которым свойственна очень высокая степень параллельности обработки, отличаются очень высоким быстродействием, но не
83
очень большой гибкостью; в отдельных задачах, однако, их применение может дать блестящие результаты.
В области программного обеспечения: новая аппаратура требует соответствующего программного обеспечения, непосредственно приспособленного для осуществления параллельной и потоковой обработки; во многих случаях будет необходимо использовать микропрограммирование в сочетании (для нужд широкого круга пользователей) с языками высоких уровней; полезным может оказаться использование специализированного языка обработки изображений.
Поскольку разработке аппаратуры и программного обеспечения уделяется много внимания, то, учитывая также внимание, уделяемое разработке теории, есть все основания ожидать в очередном десятилетии значительного прогресса в области распознавания образов.
Послесловие редактора перевода.
Синтез оптимального алгоритма в классе алгоритмов вычисления оценок
Распознавание образов в последние годы стало одним из наиболее популярных и «прикладных» направлений прикладной математики. Это превращение явилось следствием действия целого ряда факторов, в частности естественности сведения множества разнообразных задач обработки и анализа данных к задаче распознавания, интереса к изучению сложных или плохо формализованных систем, для которых не удается синтезировать модели традиционными математическими средствами из-за недостатка априорной информации, возникновения в распознавании интересной внутренней математической проблематики.
Обращение к методам и приемам распознавания — характерная особенность исследований, связанных с математической обработкой информации в тех случаях, когда точные математические модели изучаемых объектов, явлений или процессов невозможно строить либо невозможно реализовать с помощью существующих вычислительных средств, а решение отыскивается на базе Правдоподобных эвристических соображений. К середине 70-х годов распознавание достигло такой стадии развития, что возникла необходимость (и возможность) переходить от описания отдельных эвристических процедур к изучению моделей таких процедур, постановке 84
соответствующих оптимизационных задач и т. д. Наступила пора обобщений, и различные математические школы, действуя в соответствии с собственными традициями и вкусами, решали, как это теперь стало очевидным, классическую задачу кибернетики — задачу «черного ящика». Ее суть, как известно, состоит в том, что, опираясь на некоторую (ограниченную, неполную, намеренно или ненамеренно искаженную, вероятностную, нечеткую) информацию об отдельных проявлениях (внешних характеристиках, наблюдаемых параметрах, поведении) системы, можно сформировать представление о механизмах, лежащих в ее основе, определить набор ее наиболее существенных свойств и получить прогноз ее динамики, т. е. построить практически полезную математическую модель. В рамках распознавания эта задача принимает множество обликов: обнаружение закономерностей, восстановление зависимостей по эмпирическим данным, выявление регулярностей, эмпирическое предсказание, анализ данных, анализ неэкспериментальных данных, принятие решений на основе прецедентов и т. д.
Важно отдавать себе отчет в том, что, несмотря на почти тридцатилетний путь, пройденный распознаванием в качестве самостоятельного научного направления, реальное признание оно получило лишь во второй половине 70-х годов. Это произошло после того, как специалисты-прикладники начали осознавать, что «измерения» — сбор и накопление информации — сами по себе неэквивалентны изучению и не дают понимания работы сложной системы в целом, сколь бы прецизионными измерения ни были и сколь бы обширной и подробной ни была исходная информация. Между результатами измерений и возможностью разумно их использовать существует разрыв — для того чтобы перейти от первых ко вторым, необходимо осуществить целый ряд преобразований — эти преобразования и методы их осуществления и составляют предмет распознавания образов.
Авторы обзора, с которым познакомился читатель, совершили маленькое чудо: им удалось ясно, доступно и чрезвычайно лаконично изложить основные подходы к решению задач распознавания и способы их реализации. В роли «первого чтения» по распознаванию этот обзор, вероятно, не имеет конкурентов. Тем не менее 85
один существенный пробел здесь имеется. Ниже мы по- S пытаемся восполнить его в столь же лаконичной манере. Я
Речь идет о классе алгоритмов распознавания, осно- д ванных на вычислении оценок (сокращенно АВО), пред- Я ложенном известным советским математиком Ю. И. Жу- I равлевым (Вычислительный центр АН СССР) и разви- а том на протяжении 70-х годов в его работах и в рабо- I тах его учеников [1—3] подробную библиографию по Я АВО можно найти в работах [3, 4]. В основе алгорит- Я мов этого класса лежит очень естественный эвристиче- fl ский принцип, которым человек пользуется часто и охот- fl но: принцип прецедентности или частичной прецедент- fl ности, лежащий в основе принятия решений по fl аналогии: в сходных ситуациях можно действовать ана- fl логично.	fl
«Принцип действия» АВО состоит в вычислении * приоритетов (оценок сходства), характеризующих бли- Ж зость распознаваемого и эталонного объектов по систе- Я ме ансамблей признаков, представляющей собой систе- Л му подмножеств заданного множества признаков. Опыт Я решения задач распознавания свидетельствует о том, что'Л часто основная «различающая» информация заключена Я не в отдельных признаках, а в различных их сочета- If ниях. Уже в середине 60-х годов предпринимаются по- А пытки строить алгоритмы распознавания, позволяющие ; учитывать информацию, заключенную в комбинациях признаков. Наибольшую известность среди алгоритмов этого типа приобрели так называемые тестовые алгоритмы (впервые описаны в работе [5]), программа «Геометрия» (блок «Кора») [6] и алгоритм «Кора» [7]. Из-за вычислительной сложности (объема перебора) в двух последних алгоритмах пришлось ограничиться конъюнкциями сложности три. При использовании тестовых алгоритмов возникали трудности, связанные с синтезом совокупности всех тупиковых тестов для данной задачи.
Класс АВО доводит идею использования совокупностей признаков до логического конца: поскольку не  всегда известно, какие именно сочетания признаков информативны в наибольшей степени, то в АВО степень похожести объектов вычисляется в процессе сопоставления всех возможных (или определенных — для слу-
1 Работы, на которые даны ссылки в послесловии, приведены в списке литературы к послесловию редактора перевода.
86
чая, когда известны сочетания признаков, обладающие наибольшей разделяющей силой) сочетаний признаков, входящих в описание объектов. Для вычисления соответствующих оценок близости в АВО имеются несложные аналитические формулы, снимающие перебор при реализации процедуры распознавания.
Для описания класса АВО необходимо определить понятие исходной информации, модель АВО и задать правила вычисления оценок близости сопоставляемых объектов.
Пусть дано множество М объектов со; на этом множестве существует разбиение на конечное число под-т
множеств (классов) t=l, ..., т, М = (J £2г. Разбие-/ —1
ние М определено неполностью. Задана лишь некоторая информация /о о классах Q,. Объекты со задаются значениями некоторых признаков х,, /=1......N (этот на-
бор всегда один и тот же для всех объектов, рассматриваемых при решении определенной задачи). Совокупность значений признаков Xj определяет описание /(со) объекта и. Каждый признак может принимать значения из различных множеств допустимых значений признаков. Задача распознавания состоит в том, чтобы для данного объекта w и набора классов Qi, ..., Qm по обучающей информации 70(йь • • Йт) о классах и описанию 7(<о) вычислить значения предикатов Р((<о) — —i=l, ..., т. Априорная информация в задаче распознавания с непересекающимися классами часто задается в виде так называемой таблицы обучения TN,m.
Алгоритм распознавания, основанный на принципе прецедентности или частичной прецедентности, сравни-дается в виде так называемой таблицы обучения Ты,т. и принимает решение о том, к какому классу следует отнести этот объект. Решение выносится на основе вычисления степени похожести распознаваемого объекта (строки) на строки, принадлежность которых заданным классам известна.
2.
Пусть заданы стандартные описания объектов {<о
аЛ и {а>й‘}, шй* Необходимо определить принадлежность классу Qz, i = l, ..., т, предъявленного для распознавания объекта ш'. Если введен способ определения близости для некоторых частей описания /(«>') и co-
s''
Стандартная форма задания таблицы обучения TN т
Объекты	Признаки и их значения				Классы
	*1	xt	*i	XN	
"1	а1,1	al,3	al,j	al,N	
«о,	а1Л	ai,2	a2,j	a2,N	Qj
“г.	аГ,1	ar,2	ari.l	ar,,N	
... . . • ...					
		ari_1+i,3  	ari~l+l-i •	 ari-l+l.N	
“fi-i+s		ari_1+2,2  		• ari-i + W	
<%	ariti	аГ,,2	..	ari.i •	art ,N	
. . .	• • • ... • •. 						. . .
	%rm—i+l-l		i '	 arm-^-N	
'm—V *		•••	arm^i+id 	 arm-^N	
(Ог гт		ar 9 гт,я	a'm-i	 V	
					
to'	*1	ь2	bj	bN	2,
ответствующих частей описаний {/(аЛ)} и {/(ш 1)}, то можно сформировать «обобщенную близость» между объектом а/ и множествами объектов {«Л } и {«Л} соответственно. В простейшем случае обобщенная близость приравнивается сумме близостей между частями описаний. В ре-зультате характеристику вида Г, (ш') = Г/ — 1. , где Г.1 и Гв‘ —значения соответствующих обобщенных близостей, естественно считать значением функции принадлежностк 88
объекта at' классу G2i. Величина Г/(to') называется оценкой объекта со' по классу й(.
Описания объектов {со'}, предъявленные для распознавания, переводятся алгоритмом распознавания в числовую матрицу {Г,.}—матрицу оценок. Эта процедура включает два этапа: сначала подсчитывается оценка to' по каждой строке из Ты,т, а затем определяются суммарные оценки по каждому из классов Q,.
Рассмотрим процедуру построения оценок Г, (со'), используемую в тестовых алгоритмах и АВО. В основе тестовых алгоритмов лежит понятие теста [8]. Тестом таблицы Ты,т называется совокупность столбцов. xt,...,x. таких, что после удаления из TN,m всех * ч
столбцов, за исключением имеющих номера Л, ..., tq> в полученной таблице Т t t т все пары строк, при-надлежащих разным классам, различны. Тест {xt...xt У
называется тупиковым, если никакая его часть не является тестом.
Пусть {7} — множество всех тупиковых тестов ТN т.
и Т = {х. , ..., xt }G{7}. Выдели в описании распоз-г' я
наваемого объекта I(со') часть (Ь......bt ), соответству-
1 ч
ющую признакам
частичными описаниями (aft ,
ЛВДЫ TN,m> '• = '•<-.+ 1....
число совпадений — Гг (со',
и сопоставим ее со всеми
...,ar ) объектов I(<ог) таб-%
rh i — 1...т. Подсчитаем
&,) — частичных описаний
(bie ..., bt ) со всеми частичными описаниями (art ,..., aTt объектов i-го класса. Величина Гт (со', Q,) представляет собой число строк этого класса, близких распознаваемой строке а' по тесту Т, т. е. оценку строки со' для класса Q, по тесту Г. Аналогичным образом вычисляется оценка для со' по остальным тестам (для всех классов). Величина
=	Гг«й(.)	(ПЛ).
г&Г) представляет собой оценку объекта to' по классу Q,. 7— 115	89*
Известны разновидности тестовых алгоритмов, в которых при формировании оценок Гт(со', R,) учитываются различия в представительности («важности») отдельных строк таблицы TN,m и признаков, включенных в стандартные описания объектов. Для этого используются числовые коэффициенты — веса признаков и веса объектов. Существует довольно много способов введения таких весов, чаще всего они задаются из эвристических соображении, исходя из специфики решаемой задачи с помощью экспертной оценки и тому подобное.
Переход от тестовых алгоритмов к АВО связан с расширением видов подмножеств признаков, по которым проводится сопоставление распознаваемого объекта с объектами из Тя,т, и построением эффективных формул вычисления оценок Г (со', й;) для различных случаев задания подмножеств множества признаков (в АВО -они называются опорными множествами алгоритма распознавания). В тестовых алгоритмах в качестве системы опорных множеств используются множества тупиковых тестов (при отсутствии пересечений классов в TN,m и бинарных признаках). В АВО рассматриваются два случая: наличие [1, 2] и отсутствие ограничений на систему опорных множеств алгоритма [9]. В первом случае наиболее распространенными являются системы опорных множеств, составленные из всех подмножеств множества признаков фиксированной длины, q, q = —2, ..., jV—1, либо из всех непустых подмножеств множества признаков.
Рассмотрим полный набор признаков ..., Хлг> и выделим систему подмножеств множества признаков (систему опорных множеств алгоритма) Sb ..., Sz. Удалим произвольный поднабор признаков из строк coi, <02, .  ...,т , ш' и обозначим полученные строки через S<o2, ...
rm
.... Sos , Sa>'. Правило близости, позволяющее оценить 'т
похожесть строк Sos' и Su>r, состоит в следующем. Пусть «усеченные» строки содержат q первых признаков, т. е. So)r = (av .... а9) и Sw'—(bi.Ьч), и заданы пороги
«,•..е^, S. Строки Sa>r и So>' считаются похожими, если
выполняется не менее б неравенств вида |а,-—bj\^ej, 90
/=1, . . q. Величины ei, ..e,q, d входят в качестве параметров в модель класса АВО.
Рассмотрим процедуру вычисления оценок по подмножеству Si. Для остальных подмножеств она полностью аналогична. В таблице Тк>т выделяются столбцы, соответствующие признакам, входящим в Si; остальные столбцы вычеркиваются. Проверяется близость строки Sim' со строками Sitoi, . . ., Si©ri, принадлежащими классу йь Число строк этого класса, близких по выбранному критерию классифицируемой строке Si®', обозначается через ГзДо/, Й1) (оценка строки со' для класса Hi по опорному множеству Si). Аналогичным образом вычисляются оценки для других классов:
Г51(а>',йг).Г5 (а/, йт). Применение подобной процедуры
ко всем остальным опорным множествам алгоритма позволяет получить систему оценок Г5 (<»>', й,), ...,Г5 (<о',йт), ... ...,	(«/, й,)...(<»',	йт). Величины
Г («>',	= Г51 (со', й.) + Г5а (»', й.) + ...
... + Г (<о',Й1)=2Г(щ',й1);
5/1	(П.2)
Г (со', QJ = rSi(«o', Йт) + Г5а(со',йт)+ ...
•• + Г5 (<QJ-2r(<o',Qm) «Л
представляют собой оценки строки со' для соответствующих классов по системе опорных множеств алгоритма Sa- На основании анализа этих величин принимается решение об отнесении объекта ю' к одному из классов й,-, z=I, ..., т, или об отказе от его распознавания. Решающее правило может принимать различные формы, в частности распознаваемая строка может быть отнесена к классу, которому соответствует максимальная оценка, либо эта оценка будет превышать оценки всех остальных классов не меньше чем на определенную пороговую величину т)ь либо величина отношения соответствующей оценки к сумме оценок для всех остальных классов должна быть не менее величины некоторого порога т,г и т. д. Параметры типа тц и т]2 также включаются в модель АВО.
Определение класса АВО сводится к формализации следующих этапов, соответствующих последовательно-7*	91
сти реализации процедуры распознавания: 1) выделяется система опорных множеств алгоритма, по которым , производится анализ распознаваемых объектов; 2) вво- _ дится понятие близости на множестве частичных описа- Я ний объектов; 3) задаются правила: а) вычисления оцен- fl ки для пар объектов по значению оценки степени подо- fl бия эталонного и распознаваемого объектов; б) форми- fl рования значений оценок для каждого из эталонных клас- fl сов по фиксированному опорному множеству на основе -fl оценок для пар объектов; в) формирования суммарной Я оценки для каждого из эталонных классов по всем опор- fl| ным множествам; г) принятия решения, обеспечивающе- fl| го на основе оценок для классов отнесение распознавае- fl мого объекта к одному из классов или отказывающего fll этому объекту в классификации.	fl
Фиксация способа выбора системы опорных множеств, >< типа функции близости, правил вычисления оценок и jL решающего правила определяют выбор подкласса алго- wj ритмов типа АВО, а задание значений соответствующих як параметров — конкретный алгоритм АВО. Модель клас- Ж са АВО — параметрическая, т. е. имеет место взаимно- ® однозначное соответствие между конкретными алгорит-мами и наборами числовых параметров. В таком случае ~ задание конкретного алгоритма, принадлежащего рас- Jtl •сматриваемому классу, позволяет сопоставить ему зна- fl| чение некоторого функционала качества распознавания fl| :и, следовательно, определить последний на точках пара- fl| метрического пространства алгоритма.	-^fl
Задав параметрическую модель алгоритма, можно jfl •подбирать и изменять его параметры таким образом, fl| чтобы значение функционала качества изменялось в нуж- |fl ном направлении. Если существует эффективный способ ^вычисления функционала качества фА, то принципиаль- jfl но возможно построение алгоритма А*, на котором до- jfl •стигается экстремум фА. Хотя известно, что последняя Jfl задача не всегда может быть решена до конца (в ряде ситуаций приходится удовлетворяться локальными экс- |fl тремумами), в тех случаях, когда абсолютно экстремаль-jfl ный алгоритм может быть найден, имеется гарантия, jfl что при данном исходном материале в данном классе алгоритмов для заданного контрольного материала не fl| существует лучшего алгоритма распознавания, чем A* fl| [2, 3].	fl
Если строить вычислительную процедуру по приве? «
•92
денному описанию алгоритма, то при большой мощности системы опорных множеств требуется значительное число машинных операций. Так, при выборе в качестве системы опорных множеств алгоритма всех подмножеств множества признаков мощности q число опорных множеств равно Сдг, а число слагаемых в формуле (П.2) равно
Существенное достоинство АВО состоит в том, что для вычисления оценок, определяющих принадлежность распознаваемого объекта одному из заданных классов, имеются простые аналитические формулы, заменяющие сложные переборные процедуры. Поскольку эффективность процедуры вычисления значений функционала качества полностью определяется эффективностью процедуры вычисления оценок, то принципиально возможно построение оптимального алгоритма в классе АВО.
Так, при выборе в качестве SA системы всех подмножеств мощности q множества признаков {1, ..., N} формула, обеспечивающая эффективное вычисление оценок Г(ю', Qi), имеет вид [1]
У] Tw(SC!'..r-c^.v)-
/ = 0
(П.З)
где 2(ю', <ьг) —число выполненных неравенств вида | —6j|для пары (со', <ог), /= 1, ..., N; у(а>г) —вес объекта <ог.
В некоторых случаях поднаборы признаков, которые следует учитывать при сопоставлении распознаваемого объекта с объектами таблицы обучения, известны априори. Эти подмножества могут иметь различную длину, могут задаваться запрещенные или «избыточные» комбинации и т. п. Для случая произвольных опорных множеств также получены эффективные формулы вычисления оценок [9]. Вывод этих формул основан на введении характеристической булевой функции системы опорных множеств алгоритма и установлении взаимнооднозначного соответствия между подмножествами множества признаков и вершинами единичного М-мерного куба. Показано, что сложность формулы вычисления оценок в АВО при произвольной SA пропорциональна сложности дизъюнктивной нормальной формы (ДНФ),
93
представляющей характеристическую функцию системы I опорных множеств алгоритма. Это означает, что по- | строение простой формулы вычисления оценок связано , с задачей минимизации булевых функций в классе ДНФ.
В последнее время были изучены модели АВО с опор- | ными множествами, задаваемыми на Тн,т локальными 1 окрестностями невысоких порядков — 2-индексными | опорными множествами (подмножество признаков зада- 1 ется пересечением нескольких строк и столбцов табли- J цы обучения).	я
Класс АВО успешно используется для решения за- 1 дач медицинской диагностики, геологического прогноза, 1 обработки социологической информации, идентифика- | ции технологических процессов и управления ими, про- 1 гноза свойств синтезируемых химических соединений, ' оптимального выбора алгоритма и оптимизации процес- , сов принятия решений, профессионального отбора, авто- ’ матизации обработки экспериментальных данных и т. д. i
Говоря о тенденциях современного распознавания, ’I необходимо обратить внимание на одно обстоятельство, , не нашедшее отражения в обзоре. При решении практических задач распознавания очень большое значение • имеет правильный выбор алгоритма из множества известных. По мере развития теории и практики распо- J знавания стало выясняться, что систематизация выбора 1 наилучшего алгоритма распознавания непосредственно 1 связана с формализацией теории распознавания и ее | основных понятий — образа и алгоритма распознавания. 1 Для решения первой задачи существенное значение | имеет теория образов У. Гренандера.	1
На определенном этапе (70-е годы) развитие теории а распознавания определялось попытками строить едино- | образные описания для достаточно богатых множеств 1 эвристических («некорректных»), но успешно решающих 1 реальные задачи процедур. Подобное множество зада- | ется указанием переменных, объектов, функций, пара- 1 метров и точным определением областей их изменений, 1 что приводит к описанию модели класса некорректных 1 алгоритмов. Оказалось, что получение описания класса 1 алгоритмов распознавания представляет задачу, сход- | ную с построением общего определения алгоритма. |
Введение понятия модели распознающего алгоритма 1 позволило изучать множества некорректных процедур j распознавания с помощью строгих математических мето- ] 94	?

дов. Появление моделей, как мы убедились на примере АВО, позволило ставить и решать в пределах определенной модели задачу выбора алгоритма, экстремального по функционалу качества классификации или прогноза. Следующий этап развития теории распознавания связан с изучением строения в целом совокупности некорректных алгоритмов для решения задач, связанных с вычислением конечного числа свойств, фиксированных априори. Анализ совокупности некорректных алгоритмов распознавания позволил по мере их накопления выделять и описывать не только отдельные частные алгоритмы, но и принципы их формирования. Эти принципы, действующие уже над множествами алгоритмов и формулируемые сначала также в плохо формализованном виде, могут затем реализовываться в виде точных математических описаний. На этом этапе выбор принципа имеет собственно эвристический характер, а алгоритмы, порождаемые на основе соответствующего принципа, могут строиться стандартным образом.
На этой основе Ю. И. Журавлевым была поставлена задача построения общей теории алгоритмов распознавания и предложен так называемый «алгебраический подход к решению задач распознавания и классификации», обеспечивающий эффективное исследование и описание класса алгоритмов распознавания и предусматривающий такое определение алгоритмов, в которые полностью укладываются существующие модели алгоритмов [3, 4, 10, 11].
Параметризация ряда моделей алгоритмов (реализующих принцип разделения, вероятностных, АВО, основанных на методе потенциальных функций и структурных) и возможность на основе имеющейся информации о классах определять значения параметров позволяют выбирать корректные алгоритмы для некоторых подклассов задач. В большинстве практических случаев, однако, оказывается, что такие подклассы довольно узки, так как в противном случае семейство алгоритмов распознавания должно было бы являться достаточно точной моделью изучаемого явления. Кроме того, построение оптимального алгоритма в многопараметрической модели связано с решением трудных экстремальных задач. В качестве выхода из этой ситуации и был предложен алгебраический подход: «обогащение» (расширение) семейства алгоритмов с помощью алгебраи
95
ческих операций и построение семейства, гарантирующего получение корректного алгоритма, обеспечивающего решение изучаемого класса задач. В результате на основе изучения различных моделей алгоритмов оказалось возможным сформулировать общее определение алгоритма распознавания и изучить свойства множества таких алгоритмов. Оказалось, что множество алгоритмов распознавания является алгеброй, причем операции этой алгебры обладают свойствами, позволяющими детально изучить множество этих алгоритмов.
Основной результат алгебраической теории алгоритмов распознавания состоит в том., что для описания класса алгоритмов, правильно классифицирующих конечную выборку по всем классам, достаточно взять любую полную модель, рассмотреть линейное замыкание совокупности ее распознающих операторов и присоединить к ней любое корректное решающее правило. Следовательно, вместо построения формальных моделей в различных областях, плохо поддающихся формализации, достаточно построить семейство «интуитивно разумных» алгоритмов решения соответствующих задач, затем ввести алгебру на множестве таких задач и построить алгебраическое замыкание «интуитивного» семейства алгоритмов. В этом замыкании оказывается принципиально разрешимой любая задача из множества задач, связанных с исследованием плохо формализованных ситуаций.
В заключение отметим, что для более глубокого знакомства с методами и средствами распознавания можно обратиться к соответствующим работам [6, 12—23] (см. список литературы к послесловию).
Список литературы к послесловию редактора перевода
1.	Журавлев Ю. И., Никифоров В. В. Алгоритмы распознавания, основанные на вычислении оценок. — Кибернетика, 1971, № 3, с. 1—11.
2.	Журавлев Ю. И. Экстремальные задачи, возникающие при обосновании эвристических процедур. — В кн.: Проблемы прикладной математики и механики. — М.: Наука, 1971, с. 67—75.
3.	Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания и классификации. — В кн.: Проблемы кибернетики. — М.: Наука, 1978, вып. 33, с. 5—68.
96
4.	Журавлев Ю. И. Непараметрические задачи распознавания образов.— Кибернетика, 1976, № 6, с. 93—103.
5.	Дмитриев А. Н., Журавлев К). И., Кренделев Ф. П. О математических принципах классификации предметов и явлений. — В кн.: Дискретный анализ. — Новосибирск: Ин-т математики СО АН СССР, 1966, вып. 7, с. 3—15.
6.	Бонгард М. М. Проблема узнавания. — М.: Наука, 1967. — 320 с.
7.	Вайнцвайг М. Н. Алгоритм обучения распознаванию образов «Кора». — В кн.: Алгоритмы обучения распознаванию образов/ Под ред. В. Н. Вапника. — М.: Сов. радио, 1973, с. ПО—116.
8.	Чегис И. А., Яблонский С. В. Логические способы контроля работы электрических схем. — В кн.: Сборник статей по математической логике и ее приложениям к некоторым вопросам кибернетики/ Под ред. С. В. Яблонского. — Тр. Математ. ин-та АН СССР им. В. А. Стеклова. — М.: Изд-во АН СССР, 1958, т. 51, с. 270—360.
9.	Гуревич И. Б., Журавлев Ю. И. Минимизация булевых функций и эффективные алгоритмы распознавания. — Кибернетика, 1974, № 3, с. 16—20.
10.	Журавлев Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. — Кибернетика. Ч. I, 1977, № 4, с. 14—21; ч. II, 1977, № 6, с. 21—27; ч. Ill, 1978, № 2, с. 35—43.
11.	Задачи распознавания и классификации со стандартной обучающей информацией/Ю. И. Журавлев, А. А. Зенкин, А. И. Зенкин и др. — Журнал вычислительной математики и математической физики, 1980, т. 20. № 5, с. 1294—1309.
12.	Айвазян С. А., Бежаева 3. И., Староверов О. В. Классификация многомерных наблюдений. — М.: Статистика, 1974. — 240 с.
13.	Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. — М.: Наука, 1970. — 384 с.
14.	Браверман Э. М., Мучник И. Б. Структурные методы обработки эмпирических данных. — М.; Наука, 1983. — 464 с.
15.	Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. — 448 с.
16.	Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. Статистические проблемы обучения. — М.: Наука, 1974. — 416 с.
17.	Васильев В. И. Распознающие системы: Справочник. — 2-е изд., перераб. и доп. — Киев: Наукова думка, 1983. — 424 с.
18.	Горелик А. Л., Скрипкин В. А. Методы распознавания: Учеб, пособие для вузов. — 2-е изд., перераб. и доп. — М.: Высшая школа, 1984, —208 с.
19.	Загоруйко Н. Г. Методы распознавания и их применение. — М.: Сов. радио, 1972. —208 с.
20.	Перцептрон — система распознавания образов/ Под общ. ред. чл.-кор. АН УССР А. Г. Ивахненко. — Киев: Наукова думка, 1975, —430 с.
21.	Патрик Э. Основы теории распознавания образов: Пер. с англ.— М.; Сов. радио, 1980.— 408 с.
22.	Ту Дж., Гонсалес Р. Принципы распознавания образов: Пер. с англ. — М.: Мир, 1978.— 416 с.
23.	Фомин В. Н. Математическая теория обучаемых опознающих систем, —Л.: Изд-во ЛГУ, 1976.— 236 с.
97
СПИСОК ЛИТЕРАТУРЫ
1	Ahmed N and Rao KR 1975 Orthogonal Transforms for Digital Signal Processing (Berlin: Springer-Verlag)
2	Aho AV and Ullman J D 1972 The Theory of Parsing, Translation, and Compiling vol 1 (Englewood Cliffs, NJ: Prentice Hall)
3	Andrews HC 1970 Computer Techniques in Image Processing (New York: Academic)
4	Attneave F 1954 Psychol. Rev. 61 183-93
5	Backer E 1978 Cluster Analysis by optimal decomposition of induced fuzzy sets. Thesis, Deljt (Delft: Delft University Press)
6	Bierman AW and Feldman JA 1972 Frontiers of Pattern Recognition ed S Watanabe (New York: Academic) pp31-54
7	Blin JM and Cohen C 1976 Proc. 3rd Int. Joint Conf, on Pattern Recognition, Coronado (New York: IEEE) pp376-80
8	Blin JM and Whinston AB 1974 Proc. 2nd Int. Joint Conf, on Pattern Recognition, Copenhagen (New York: IEEE) PP291-3
9	Blum H 1967 Models for the Perception of Speech and Visual Form ed W Wathen-Dunn (Cambridge, Mass.: MIT Press) pp362-80
10	Bock HH 1974 Automatische Klassifikation (Gottingen: Vandcnhocck and Rvprecht)
11	Bom N, Lancee CT, Zwieten G van, Kloster FE and Roelandt J 1973 Circulation 43 1066-74
12	Brice CR and Fennema CL 1970 Artificial Intelligence 1 205-26
13	British Computer Society 1971 Character Recognition (London: The British Computer Society)
14	de Bruin M, Korthoven PJM, Duin RPW, Groen FCA and Bakels CC 1973 J. Radioanalyt. Chem. 15 181-91
15	Brunecl C, Bridoux E, Delannov B. Nongaillard B, Rouvaen JM and Torguet R 1978.7. Appl. Phys. 49 569-73
16	van Campenhout JM 1978 IEEE Trans. Syst., Man, Cybern. SMC-8 390-5
17	Caspersson T and Zech L (ed) 1973 Chromosome Identification (New York: Academic)
18	Chapel CE 1941 Fingerprinting. A Manual of Identification (New York: Coward McCann)
19	Cho Z H 1979 Advances in Picture Reconstruction (Oxford: Pergamon)
20	Chomsky N 1959 Information and Control 2 137-67
21 Cochran WT, Cooley W, Favin DL, Helms HD, Kacnel RA, Lang WW, Maling GC, Nelson DE, Rader CM and Welch PD 1967 IEEE Trans. Audio Electroacoust. AU-15 45-55
22 Cover T 1972 Frontiers of Pattern Recognition ed S Watanabe (New York: Academic) pp83-98
23 Cover TM 1974 IEEE Trans. Syst., Man, Cybern. SMC-4 116-7
24 Cover TM and van Campenhout JM 1977 IEEE Trans. Syst., Man, Cybern. SMC-7 657-61
25 Dittel RH 1977 Informatik-Fachbericht 8: Digitale Bildverarbeitung ed HH Nagel (Berlin: Springer-Verlag) pp60-70
26 Duda RO and Hart PE 1973 Pattern Classification and Scene Analysis (New York: Wiley)
27 Duff MJB 1974 Proc. IFIP Congr. on Information Processing, Stockholm (Amsterdam: North-Holland) pp94— 7
28 ---- 1976 Proc. 3rd Int. Joint Conf, on Pattern Recognition, Coronado (New York: IEEE)
, pp728-33
29 Duin RPW 1978 On the accuracy of statistical pattern recognizers. Thesis, Delft (Pijnacker: Dutch Efficiency Bureau)
30 Duin RPW, Vos JA, Bakker JGM, de Boer RR and Furnee EH 1977 Proc. SITEL-VLG Seminar on Pattern Recognition, Liege, Belgium (Ophain, Belgium: SITEL) ppS.l.1.-8.1.9
31 Edler I and Hertz CH 1954 Kungl. Fysiografiska Sallskapets I Lund for Fcrhandlingar 24 40-58
32 Eleccion M 1973 IEEE Spectrum 10 36-45
33 Ernst D, Bangel В and Holdermann F 1976 Proc. 3rd Int. Joint Conf, on Pattern Recognition* Coronado (New York: IEEE) pp679-83
34 Everitt В S 1974 Cluster Analysis (London: Heinemann)
35 ---- 1979 Biometrics 35 169-81
36 Finkelstein L 1975 Measurement and Control 8 105-11
37 Freeman H 1961 IRE Trans. Electron. Comput. 10 260-8
38 Freeman H and Davis LS 1977 IEEE Trans. Comput. C-26 297-303
39 Fu KS 1974 Syntactic Methods in Pattern Recognition (New York: Academic)
40----- 1976 Systems Theory in the Social Sciences ed H Bossel, S Klaczko and S Muller (Basel:
Birkhauser-Verlag! ppi81-200
4! Fu KS (ed) 1977 Syntactic Pattern Recognition, Applications (New York: Springer-Verlag)
42 Fu KS and Booth TL 1975a IEEE Trans. Syst., Man, Cybern. SMC-5 95-111
98
43 ----- 1975b IEEE Trans. Syst., Man, Cybern. SMC-5 409-23
44 Fu KS and Swain PH 1971 Software Engineering vol 2, ed JT Tou (New York: Academic)’ ppi 55-82
45 Fujisawa II, Nakano Y, Kitazume Y and Yasuda M 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyoto (New York: IEEE) pp816-20
46 Fukunaga К 1972 Introduction to Statistical Pattern Recognition (New York: Academic)
4? Gaines BR and Kohout LS 1977 Int. J. Man-Machine Studies 9 1-68
48 Gallus G and Neurath PW 1970 Phys. Med. Biol. 15 435—45
49, Glick N 1978 Pattern Recognition 10 211-22
50 Gold В and Rader CM 1969 Digital Processing of Signals (New York: McGraw-Hill)
51 Gonzalez RC and Howington LC 1977 IEEE Trans. Syst., Man, Cybern. SMC-7 717-28
52 Gonzalez RC and Thomason MG 1978 Syntactic Pattern Recognition, An Introduction (London: Addison-Weslev)
53 Granlund GH 1971 J. Theor. Biol. 40 573-89
54 Grasselli A 1969 Methodologies of Pattern Recognition ed S Watanabe (New’ York: Academic) pp253-73
55 Grenander U 1976 Pattern Synthesis (New York: Springer-Verlag)
56 ----- 1978 Pattern Analysis (New York: Springer-Verlag)
57 Grocn FCA 1977 Analysis of DNA based measurement methods applied to human chromosome classification. Thesis, Delft (Pijnacker: Dutch Efficiency Bureau)
58 Habbema JDF and Hermans J 1978 Statistical methods for clinical decision making. Thesis, Leyden
59 Habibi A 1972 Proc. IEEE 60 878-83
60 Haralick RM, Shanmugan К and Dinstein I 1973 IEEE Trans. Syst., Man, Cybern. SMC-3 610-21
61 -----1978 Pattern Recognition 10 223-36	'
62 Harlow C A 1976 Digital Picture Analysis ed A Rosenfeld (Berlin: Springer-Verlag) pp65-l 50
63 Hartigan J A 1975 Clustering Algorithms (New York: Wiley)
64 Hattisch W, Tropf H and Winkler G 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyoto (New York: IEEE) pp786-8
65 Hersant T, Jeulin D and Parriere P 1976 Newsletter 1976 in Stereology ed G Ondracek (Gesellschaft fur Kernforschung Karlsruhe) ppl7-78
66 Hilditch CJ 1969 Machine Intelligence vol 4, ed В Meltzer and D Mirchie (Edinburgh: Edinburgh University Press) pp403-20
67 Ho YC and Agrawala AK 1968 Proc. IEEE 56 2101-14
68 Hohne H D 1974 Proc. 2nd Int. Joint Conf. Pattern Recognition, Copenhagen (New York: IEEE) pp307-9
69 Hopcroft JE and Ullman JD 1969 Formal Languages and Their Relation to Automata (Reading, Mass.: Addison-Wesley)
70 Howarth RJ 1973 Geochemical Exploration 1972 (London: Institution of Mining and Metallurgy) pp297-304
71	Huang TS, Schriebcr WF and Tretiak OJ 1971 Proc. IEEE 59 1586-609
72	Hueckel M H 1971 J. ACM 18 113-25
73	--- 1973 J. ACM 20 634-47
74	Ikeda K, Yamamura T, Mitamura Y, Fujiwara S, Tominaga Y and Kiyono T 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyoto (New York: IEEE) pp813-5
75	Itakura F, Saito S, Koike T, Sawabe H and Nishikawa M 1972 IEEE Trans. Commun. COM-20 792-7
76	Jain AK 1976 IEEE Trans. Commun. COM-24 1023-9
77	Jardine N and Sibson R 1971 Mathematical Taxonomy (New York: Wiley)
78	Jobes M and Shaylor HR 1972 Rep. Prog. Phys. 35 1077-172
79	Johnston E and Rosenfeld A 1973 IEEE Trans. Comput. C-22 875-8
80	Julesz В 1971 Foundation of Cyclopean Perception (Chicago: University of Chicago Press)
81	1975 Set. Am. 232 No 4, 34-43
82	Kanal L N 1972 Proc. IEEE 60 1200-15
83	— 1974 IEEE Trans. Information Theory ГГ-20 697-722
Ш ----- 1977 Syst., Man, Cybern. Rev., Newsletter of IEEE SMC-Soc. 9-14 August
--- 1979 IEEE Trans. Pattern Analysis and Machine Intelligence PAMI-1 193-201
86	Kelly J S 1978 Arrow Impossibility Theories (New York: Academic)*
87	Kittier J and Young PC 1973 Pattern Recognition 5 335-52
88	Kulkarni AV and Kanal LN 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyoto (New York: IEEE) pp238-45
89	Lusaka T, Haba Y, Kawat Y, Terashita Y and Ueno S 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyoto (New York: IEEE) pp931-5
99
90	Lachenbruch P A and Goldstein M 1979 Biometrics 35 69-85
91	Lavison P, Dubuisson В and Gourdon J 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition,’ Kyoto (New York: IEEE) pp975-7
92	Ledley RS, Rotolo LS, Golab TJ, Jacobson J D, Ginsberg M D and Wilson J В 1965 Optical and Electro-optical Information Processing ed JT Tippett, DA Berkowitz, LC Clapp, дД CJ Koester and A Vanderburgh Jr (Cambridge, Mass.: MIT Press) pp591-613
93	Leeuwenberg ELJ and BufTart HFJM (ed) 1’978 Formal Theories of Visual Patterns (New York: Wiley)
94	Levi GU and Montanari A 1970 Information and Control 17 62-91
95	Lillesand TM and Kiefer RW 1979 Remote Sensing and Image Interpretation (New York: ЖН| Wiley)	.	.
96	Lipkin BS and Rosenfeld A (ed) 1970 Picture Processing and Psychopictorics (New York: Academic)
97	Lobregt S, Verbeek PW and Groen FCA 1980 IEEE Trans. Pattern Analysis and Machine Intelligence PAM 1-2 75-7
98	Lowry SR, IsenhourTL, Justice Jr JB, McLafferty FW, Dayzinger HE and Venkataraghavan ЯЕ R 1977 Analyt. Chem. 49 1720-2	S
99	McIlwain RL 1976 Digital Picture Analysis ed A Rosenfeld (Berlin: Springer-Verlag) ppl51-;^K 207	W
100	Makhout J 1975 Proc. IEEE 63 561-80	’.'^g
101	Mendel ] M and Fu KS 1970 Adaptive Learning and Pattern Recognition Systems: Theory and Applications (New York: Academic)
102	Mendelsohn ML (ed) 1975 Proc. Asilomar Workshop on Automation of Cytogenetics, Pacific * Grove (Livermore, Calif.: Lawrence Livermore Laboratory)
103	Mercer A and Rosenfeld A 1973 Commun. ACM 16 299-305
104	Miller WF and Shaw AC 1968 Proc. AFIPS Fall Joint Comput. Conf., San Francisco (Mou tvale, NJ : AFIPS Press) pp279-90	>
105	Minsky M and Papert S 1969 Perceptrons: An Introduction to Computational Geometry (Cam- .fs bridge, Mass.: MIT Press)
106	Moayer В and Fu KS 1975 Pattern Recognition 7 1-23
107		1976a Pattern Recognition 8 173-9
108	--- 1976b IEEE Trans. Comput. C-25 262-74
109	Moore DJ H, Seidl RA and Parker D J 1975 Int. J. Man-Machine Studies 7 449-509
110	de Mori R 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyoto (New York: IEEE) -ppl06-24
Hl Nagao M and Matsuyama T 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyoto -fly (New York: IEEE) PP518-20	•
112	Nagao M, Tanabe H and Ito К 1976 Proc. 3rd Int. Joint Conf, on Pattern Recognition, Coronado "|я| (New York: IEEE) pp669-72	Ж
113	Nagy G 1968 Proc. IEEE 56 836-62	-Я
114	Nahi NE and Assefi T 1972 IEEE Trans. Comput. C-21 734—8	iK.
И5 Nahi NE and Habibi A 1975 IEEE Trans. Circuits Syst. CAS-22 286-93
116 Nahi NE and Lopez-Mora S 1976 Proc. IEEE Decision and Control Conf., Clearwater, Florida ж (New York: IEEE) pp607-12	W
117 Nilsson NJ 1965 Learning Machines (New York: McGraw-Hill)	ж
118 Appenheim AV, Schafer RW and Stockham TG 1972 Digital Signal Processing ed LR Rabiner
and CM Rader (New York: IEEE Pres^ ррбб-93
119 Pavel M 1978 Pattern Recognition 10 249-54
120 Peagle J N 1975 J. Appl. Meteor ol. 14 180-8	Ж
121 Pcrsoon E 1976 Computer Graphics and Image Processing 5 425-46	-w
122 Pfaltz J L and Rosenfeld A 1969 Proc. Int. Joint Conf, on Artificial Intelligence, Washington, DC Ijy pp609-19	Ж
123 Pratt WK 1972 IEEE Trans. Comput. C-21 636—41	Ж
124------ 1978 Digital Image Processing (New York: Wiley)	як
125 Pratt WK and Bavarian F 1977 IEEE Trans. Comput. C-26 571-80	\	S
126 Preston К 1976 Digital Picture Analysis ed A Rosenfeld (Berlin: Springer-Verlag) ppVo9-94 Ж
127	Primes G 1975 Theor. Chim. Acta 39 127-48	J	Ж
128	Rand WM 1969 The development of objective criteria for evaluating clustering metfibds. Thesis, jK
University of California	S'
129	Rao KCV and Balck К 1976 Proc. 3rd Int. Joint Conf. on Pattern Recognition, Coronado ' yr (New York: IEEE) pp778-82	1
130	Reddy DR 1976 Proc. IEEE 64 501-31	•->
131	Rosenberg AE 1976 Proc. IEF.E 64 475-87	i-
132 Rosenfeld A 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyoto (New York: IEEE) ppl81-5	"
133 Rosenfeld A and Как AC 1976 Digital Picture Processing (New York: Academic)
134 Rosenfeld A and Pfaltz J L 1966 J. ACM 13 471-94	’
1 35 Scollar I, Huang TS, Weidner В and Tang S 1977 Informatik-Fachberhht 8: Digitale	'
, arbeilung ed HH Nagel (Berlin: Springer-Verlag) ppl98-211
136 Shikano К and Kohda M 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyoto (New York: IEEE) ppi039-41
137 Sidhu GS and Boute RJ 1972 IEEE Trans. Comput. C-21 1206-16
138 Siromoney G, Siromoney R and Krithivasan К 1972 Computer Graphics and Image Processing
1 284-307
139 ----- 1973 Information and Control 22 447-70
140 Slepian D 1967 J.-Opt. Soc. Am. 57 918-22
141 Snijder AW, Laughlin SB and Stavenga DG 1977 Vision Res. 17 1163-75
142 Somer JC 1968 Ultrasonics 6 153-9
143 Specht D 1967 IEEE Trans. Electron. Comput. EC-16 308-19
144 Stroham TJ and Shaw MA 1975 Pattern Recognition 7 235-42
145 Suen C Y, Berthod M and Mori S 1978 Proc. 4th Int. Joint Conf, on Pattern Recognition, Kyotcr (New York: IEEE) pp30-44
146 Swain PH and Davis SM (ed) 1978 Remote Sensing: The Quantitative Approach (New York:
McGraw-Hill)
147 Tamura H, Mori S and Yamawaki T 1977 Proc. IEEE Comput. Soc. Conf, on Pattern Recognition-and Image Processing (Troy, NY: IEEE) pp'289-98
148 Ter-Pogossian MM, Philips ME, Browell G L, Cox JR Jr, Davis DO and Evans RG (ed) 1977 Reconstruction Tomography in Diagnostic Radiology and Nuclear Medicine (Baltimore: University Park Press)
149 Thomason MG 1973 Pattern Recognition 5 383-90
150------ 1975 IEEE Trans. Comput. C-24 1211-6
151 Thomason MG and Gonzalez RC 1975 IEEE Trans. Comput. C-24 93-5
•152 Thurstone FL and Ramm ОТ 1974 Acoustical Holography vol 5 (New Y’ork: Plenum) pp249-59
153 Toussaint GT 1974 IEEE Trans. Information Theory ГГ-20 472-9
154 ---- 1978 Pattern Recognition 10 189-204
155 Troy EB, Deutch ES and Rosenfeld A 1973 IEEE Trans. Syst., Man, Cybern. SMC-3 91-8
156 Ullmann J R 1976 Digital Picture Analysis ed A Rosenfeld (Berlin: Springer-Verlag) pp295-343
157 Verhagen CJDM 1975a Pattern Recognition 7 109-16
158 ----- 1975b Proc. Jurema Part I, ed Vladimir Muljevic (Zagreb: Elektrotechniiki fakultet
Zagreb) ppi 13-9
159 ---- 1977 Proc. Int. Seminar on Automation and Inspection Applications of Image Processing
Techniques SIRA Sept. 1977, London (Bellingham, Washington: SPIE) pp8-17
160 Verhagen CJDM, Duin RPW, Gerritsen FA, Groen FCA, Joosten JC and Verbeek PW 1980 Handbook of Measurement Science Fundamentals ed P Sydenham (London: Wiley) to be published
161 Wagner TJ 1975 IEEE Trans. Information Theory IT-21 438-40
162 Weszka J S, Dyer CR and Rosenfeld A 1976 IEEE Trans Syst., Man, Cybern. SMC-6 269-85
163 Wishart D1978 Clustan User Manual, Program Library Unit (Edinburgh: Edinburgh University) 3rd edn
164 Wolff HJG 1977 Proc. SITEL-ULG Seminar or Pattern Recognition, Liege, Belgium (Ophain, Belgium: SITEL) pp7.2.1-7.2.7.
165 Zadeh LA 1965 Information and Control 8 338-53
166 Zahn CT and Roskies RZ 1972 IEEE Trans. Comput. C-2 269-81
167 Zahniser DJ, Oud PS, Raaymakers MCT, Vooys G P and van de Walk RT 1979 J. Hhlocfiem* Cytochem. 27 635-41
168 Zucker S\V 1976 Computer Graphics and Image Processing 5 382-99
101
100
1.
2.
3.
20.
26.
39.
46.
50.
55.
56.
59.
61.
67.
71.
72.
82.
100.
105.
Список работ, переведенных на русский язык
Ахмед Н., Рао К. Р. Ортогональные преобразования при обра-”'-ботке цифровых сигналов: Пер. с англ. — М.: Связь, 1980. 248 с.
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода" и компиляции. Т. I. Синтаксический анализ: Пер. с англ. — М. Мир, 1978.— 616 с.
Эндрюс Г. Применение вычислительных машин для обработки изображений: Пер. с англ. — М.: Энергия, 1977.— 161 с. Хомский Н. О некоторых формальных свойствах грамматик. —« Кибернетический сборник: Пер. с англ. — М.: Изд-во ИЛ, 1962,| вып. 5, с. 279—311.	I
Дуда Р., Харт П. Распознавание образов и анализ сцен: Пер.?! с англ. — М.: Мир, 1976. — 512 с.	1
Фу К. Структурные методы в распознавании образов: Пер. с англ. — М.: Мир, 1977. — 320 с.
Фукунага К. Введение в статистическую теорию распознавания образов: Пер. с англ. — М.: Наука, 1979. — 368 с. Голд Б., Рэйдер Ч. Цифровая обработка сигналов. С приложе-нием работы Д. Кайзера «Цифровые фильтры»: Пер. с англ. — Я М.: Сов. радио, 1973. — 368 с.
Гренандер У. Лекции по теории образов. Т. 1. Синтез образов: "Л Пер. с англ. — М.: Мир, 1979. — 384 с.	Я
Гренандер У. Лекции по теории образов. Т. 2. Анализ образов: Пер. с англ. — М.: Мир, 1981. — 448 с.	
Хабиби. Двумерная байесовская оценка изображений.— ТИИЭР. Обработка изображений при помощи цифровых вы- -в числительных машин. — Тем. вып., 1977, т. 60, № 7, с. 153—160. ~ Харалик Р. Структурное распознавание образов, гомоморфизмы Л и размещения. — Кибернетический сборник. Новая серия: Пер. fl с англ. — М.: Мир, 1983, вып. 19, с. 170—199.	Л
Хо, Агравала. Об алгоритмах классификации образов: Введение Я и обзор. — ТИИЭР, 1968, т. 56, № 12, с. 5—19.	Я
Хуанг, Шрейбер, Третьяк. Обработка изображений. — ТИИЭР, Я 1971, т. 59, № 11, с. 59—89.	
Хюккель М. Оператор нахождения контуров на кодированных Я изображениях. — В кн.: Интегральные роботы: Пер. с англ.— Я М.: Мир, 1973, с. 225—240.	-Я
Канал. Обзор систем для анализа структуры образов и алго- а ритмов классификации в режиме диалога. — ТИИЭР, 1972, т. 60, Я № 10, с. 122—141.	Я
Макхол. Линейное предсказание: Обзор. — ТИИЭР, 1975, т. 63,	
№ 4, с. 20—44.	Я
Минский М., Пейперт С. Персептроны: Пер. с англ. — М.: Мир, 1 1971, —264 с.	I
113.	Надь. Распознавание образов: @бзор. — ТИИЭР, 1968, т. 56, № 5, с. 57—86.
117.	Нильсон Н. Обучающиеся машины: Пер. с англ. — М.: Мир, 1967, — 180 с.
125.	Прэтт У. Цифровая обработка изображений. Пер. с англ. — М.: Мир, 1982. — Кн. 1—312 с.; кн. 2 — 480 с.
130.	Редди. Машинное распознавание речи: Обзор. — ТИИЭР, 1976, т. 64, № 6, с. 95—130.
131.	Розенберг. Автоматическая верификация диктора: Обзор.— ТИИЭР, 1976, т. 64, № 6, с. 66—79.
102
ОГЛАВЛЕНИЕ
Предисловие........................................... 8
1.	Введение.................................................. 5'
1.1.	Распознавание образов человеком и с помощью автоматических	систем ......................... 3
1.2.	Два направления в автоматическом распознавании образов ........................................ 6
1.3.	Идентификация и классификация	....	'
1.4.	Дискретные, нечеткие	и непрерывные классы	8
1.5.	Основные особенности распознавания в случае дискретных классов;	формальная	постановка
задачи ........................................... &
1.6.	Распознавание образов	с учителем и	без учителя	Ю
1.7.	Признаки......................................11
1.8.	Структурная схема реальной системы распознавания образов.........................................12
1.9.	Датчики..........................................14
1.10.	Изменчивость релизаций	образов ....	15
1.11.	Статистические и лингвистические методы принятия решений.......................................*8
1.12.	Понятия сходства	и	расстояния..................19
1.13.	Распознавание образов и приобретение новых знаний .............................................20
1.14.	Физика и распознавание образов ....	21
1.15.	Связи между распознаванием образов и другими дисциплинами ................................... 22
2.	Методы предварительной обработки...........................24
2.1.	Введение.........................................24
2.2.	Преобразования (фильтрации), связанные с уменьшением шума................................'	.	25
2.3.	Глобальные преобразования........................26
2.4.	Локальные преобразования в обработке изображений ..............................................29
3.	Методы, используемые . в распознавании образов ...	36
3.1.	Статистические методы............................36
3.2.	Нечеткие методы .................................49
3.3.	Лингвистические методы ..........................51
4.	Прикладные задачи распознавания образов ....	61
\
4.1.	Применение в физике	.	.	.	.	.	61
4.2.	Приложения, распознавания образов, не относящиеся к физике .	......................... 69
5.	Тенденции и перспективы....................................80
Послесловие редактора перевода. Синтез оптимального алгоритма в классе алгоритмов вычисления оценок................................................84
Список литературы к послесловию редактора перевода	.............................................96
Список	литературы...................................98
Список	работ,	переведенных на русский язык .	.	102
108
Распознавание образов: состояние и пер-Р 24 спективы: Пер. с англ./ К. Верхаген, Р. Дёйн, Ф. Грун и др. — М.: Радио и связь, 1985.— 104 с., ил.
40 к. 16 000 экз.
Обзор, написанный известными голландскими специалистами, посвящен достижениям в области распознавания образов. Дано общее представление о методологии распознавания, способах описания объектов и выборе признаков. Рассмотрены статистические, размытые и структурные методы распознавания. Большое внимание уделено прикладным задачам и перспективам развития теории распознавания.
Для инженерно-технических работников, связанных с практическим использованием методов распознавания и анализом данных на ЭВМ.
1502000000-069
Р 046(01)-85	5’85
ББК 32.81
6Ф0.1
К. Верхаген, Р. Дёйн, Ф. Грун, Й. Йостен^П. Вербек
РАСПОЗНАВАНИЕ ОБРАЗОВ: СОСТОЯНИЕ И ПЕРСПЕКТИВЫ
Редактор Е. А. Засядько
Обложка художника В. П. Груздева Художественный редактор Т. В. Бусарова Технический редактор 3. Н. Ратникова Корректор Т. С. Власкина
МБ № 1114
Сдано в набор 23.10.84.	Подписано в печать 10.01.85
Формат 84 X Ю81/э«	Бумага кн.-журнальная	Гарнитура литератур!
Печать высокая Усл. печ. л. 5,46 Усл. кр.-отт. 5,809	Уч.-изд. л. 5
Тираж 16 000 экз.	Изд. № 21077	Зак. № 115	Цена 40
Издательство «Радио и связь». 101000 Москва^ Почтамт, а/я 693
Московское производственное объединение «Первая Образцовая типограф Союзполиграфпрома при Государственном комитете СССР по делам и< тельств, полиграфии и книжной торговли. 113054, Москва, Валовая, 28.