РАСПОЗНАВАНИЕ ОБРАЗОВ

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

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

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

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

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

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

Области практических применений. Методы Р. о. могут найти применение для решения следующих практических задач: 1) распознавание букв и цифр с целью ввода данных в ЦВМ; 2) распознавание слов устной речи с целью ввода данных в ЦВМ или управления автоматами; 3) диагностика болезней, где непрерывное мн-во решений представляет собой мн-во способов лечения; 4) диагностика неисправностей машин; 5) обработка данных геол. разведки, при которой решения принимаются относительно наличия определенных ископаемых; 6) обработка радиолокационных сигналов с принятием решений относительно наличия определенных обнаруживаемых объектов, а также относительно значений параметров, характеризующих эти объекты; 7) автомат, классификация живых клеток, напр., кровяных телец, наблюдаемых под микроскопом; 8) обработка фотографий следов частиц в физ. экспериментах с целью определения параметров частиц и отбора снимков, содержащих интересующие физика события; 9) распознавание фраз или слов в тексте, написанном на формальном или естественном языке; 10) распознавание алгебр, выражений определенных типов при выполнении формальных преобразований над формулами с помошью ЦВМ.

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

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

Формальные постановки задач. Среди перечисленных выше задач распознавания только задача 10) и иногда 9) имеет с самого начала формальную математическую постановку.

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

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

В этом заключается решение задачи классификации.

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

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

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

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

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

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

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

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

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

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

В простейшем случае, когда число классов равно двум и из условия задачи следует, что решающая ф-ция может быть найдена в классе линейных пороговых ф-ций от сигнала х, задача обучения может формулироваться как отыскание по данной выборке такого вектора , для которого при условии где для сигналов из 1-го класса и для сигналов из 2-го класса. Нелинейные решающие функции удается находить в тех случаях, когда по условию известно, что решающая ф-ция представима с помощью достаточно короткого ряда произвольные заранее заданные ф-ции, а число N может достигать нескольких сотен или, самое большее, тысяч. Такая задача сводится к отысканию линейной решающей ф-ции в «спрямляющем» пространстве вторичных признаков и может быть решена, в частности, потенциальных функций методом или с помощью алгоритмов персептрона. При этом следует иметь в виду, что универсальным, т. е. применимым для любой ф-ции этот метод является лишь в случае маломерных сигналов х. В этих случаях в качестве набора ф-ций можно взять к.-л. полную систему ф-ций и тогда любая удовлетворяющая весьма общим требованиям, может быть с достаточной стеценью точности представлена коротким рядом. Однако число членов ряда, необходимых для получения приемлемой точности аппроксимации, растет настолько быстро с ростом размерности сигнала х, что уже при размерности, больше 5, «универсальную» систему ф-ций построить невозможно. В большинстве же практически важных задач распознавания размерность сигнала составляет несколько десятков или даже сотен. В этих случаях успех зависит от удачного выбора системы ф-ций для данной конкретной задачи.

Практические достижения. В области Р. о. они относятся прежде всего к созданию читающих автоматов, предназначенных для непосредственного ввода буквенно-цифровой информации в ЦВМ. Существенные успехи получены и в случае других изображений (см. Распознавание зрительных образов), а также в области автомат, распознавания речевых сигналов Однако эти работы не вышли пока за пределы лабораторий. Многочисленные успешные попытки применения методов распознавания сделаны в области обработки геолого-разведочных данных и прежде всего для распознавания нефтеносных пластов. Имеются определенные успехи также в области распознавания болезней по наборам симптомов. См. между с. 96—97.

Лит.: Читающие автоматы и распознавание образов. К., 1965; Ковалевский В. А. Распознавание образов: эвристика или наука. К., 1970 [библиогр. с. 87—92]; Автоматический анализ сложных изображений. М., 1969. В. А. Ковалевский.