Система распознавания фигур

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

Одна из наиболее распространенных и разработанных областей теории распознавания связана с распознаванием зрительных образов (букв, символов, геометрических фигур). Обычный подход при распознавании  зрительных образов состоит в  использовании измерительной сетчатки, или растра, позволяющей заменить каждый образ соответствующим двоичным вектором x=(x1,x2, …,xn), где xi=1 (xi=0), если i-я  ячейка растра занята (не занята) образом. После этого распознавание сводится к алгебраической классификации  имеющегося множества векторов. Однако растровое представление зрительных образов весьма избыточно. Например, такое представление для круга  требует записи значений всех ячеек, расположенных внутри круга, хотя очевидно, что достаточно указать лишь значение ячеек, расположенных по его окружности (при этом необходимо еще отметить, что значения всех ячеек внутри круга  одинаковы).

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

Постановка задачи

Пусть имеется некоторая  плоская фигура (образ) и система  из R плоских фигур-эталонов, каждая из которых определяет соответствующий  класс плоских фигур. Принадлежность произвольной фигуры конкретному классу i определяется большей близостью  этой фигуры к i-му эталону, чем ко всем другим. Задача распознавания состоит  в том, чтобы установить, к какому из R классов принадлежит заданная фигура. Для решения этой задачи достаточно сравнить заданную фигуру с каждым из R эталонов, получив R соответствующих  значений показателя близости (сходства) фигуры и эталона (чем меньше этот показатель, тем больше близость), и  затем отнести фигуру к тому классу S, для которого показатель близости минимален. Таким образом, задача распознавания  сводится к введению подходящего  показателя близости фигуры и эталона D; к построению той или иной математической модели представления фигур и  эталонов и показателя их близости D; к разработке эффективного алгоритма  вычисления значений показателя D для  различных пар фигура, эталон на основе принятой модели представления  фигур и эталонов.

Описание метода

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

Распознаваемая фигура и эталон рассекаются вдоль одной из координатных осей семейством параллельных равноотстоящих линий {i}, i=1..P (см. рис.). Каждая такая  линия пересекается с фигурой  в 2mi точках (а именно, сначала входит в фигуру в точке ai1, затем выходит  в точке bi1, далее входит в точке ai2 и выходит в точке bi2 и так  далее). Точно так же взятая линия i пересекается с эталоном в 2ni точках. Точкам пересечения линий с распознаваемой фигурой можно поставить в  соответствие множество двоичных процессов

Ui(t)=1(ai1,bi1) 0(–,–) 1 (ai2,bi2) …  1(aimi,bimi),

i = 1 … P,                                                               (1)

а точкам пересечения линий i с эталоном – двоичные процессы

Vi(t)=1(ci1,di1) 0(–,–) 1(ci2,di2) … 1(cтi,dтi),

i = 1 … P.                                                               (2)

Здесь 1(e,f) означает интервал (e,f) единичных значений процесса, а 0(–,–) – промежуточный интервал его нулевых значений (вместо моментов изменения процессов можно поставить  прочерки, потому что момент окончания  любого интервала совпадает с  моментом начала соседнего интервала, так что момент изменения процесса достаточно указать один раз на одном  из соседних интервалов). Совокупность P таких процессов содержит полную информацию о распознаваемой фигуре или эталоне в пределах точности приближения, обусловленной расстоянием  между сканирующими линиями (чем  меньше это расстояние, тем выше точность). Зная эти процессы, можно  вычислить показатели близости для  различных пар фигура-эталон и  на этом основании отнести распознаваемую фигуру к одному из имеющихся классов  фигур, а именно к тому, к эталону  которого фигура находится ближе  всего. Для этого надо принять  подходящий для нас показатель близости за функцию выходов автомата-модели, а процессы (1), (2) – за его входные  процессы, чтобы выходной процесс  давал величину показателя близости фигуры и эталона.

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

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

Di(x)=Ui(x) Å Vi(x).                                              (3)

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

Особенности реализации

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

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

Проблемы реализации

При всех достоинствах приведенного метода его реализация требует решения  ряда проблем. Прежде всего, в качестве отправной точки в нем используется понятие пересечение сканирующей  линии с фигурой. Это понятие  интуитивно ясно, однако оно предполагает, что фигура заранее каким-либо образом  отделена от фона, что не всегда просто сделать, учитывая, что реальные изображения, как правило, содержат помехи. Можно  предположить, что временной процесс  выдает единицу всякий раз, когда  цвет изображения под сканирующей  линией изменяется с черного на белый  и наоборот. Таким образом, сканирующая  линия ведет себя подобно счетному триггеру. Кроме того, перед вычислением  показателя близости необходимо как-то добиться максимального совмещения фигуры и эталона в координатной сетке. В классической теории распознавания  для этого используется прием, называемый нормализацией фигуры [2]. Фигура перемещается в растре таким образом, чтобы  пикселы с минимальной x-координатой  располагались в крайнем левом  столбце растра, а пикселы с  максимальной y-координатой – в  его верхней строке. Затем фигура масштабируется так, чтобы она помещалась в стандартный растр m´n точек, где m и n – целые числа, выбираемые разработчиком  системы. Эталоны, хранящиеся в памяти системы, также должны быть нормализованы.

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

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

Распознавание плоских двухцветных  фигур имеет не очень много  практических приложений, главное из которых – системы распознавания  текстовой информации. Намного больше реальных приложений имеет распознавание  фигур, содержащих более двух цветов. На практике цвет обычно кодируется 16, 24 или 32 битами (это может быть изображение  в одной из систем цветопредставления, например, RGB или CMYK, или изображение, выполненное в градациях серого). Адаптировать метод под многоцветные изображения можно двумя способами.

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

Во-вторых, можно отказаться от двоичных процессов и выдавать не единицы в местах наличия фигуры (точнее, цветной точки, которая должна являться ее частью) и нули во всех остальных  местах, а непосредственно индексы  имеющихся цветов. При этом показатели близости можно вычислять с помощью  того же исключающего или, но уже не над отдельными битами, а сразу  над 16-, 24- или 32-битными словами. Здесь  происходит переход от двоичной автоматной модели процесса распознавания к k-ичной (где k – число цветов) при сохранении самой идеи автоматного моделирования  этого процесса. Если вдуматься, это  просто более компактная реализация того же самого подхода. Единственный нюанс предлагаемой реализации состоит  в следующем: надо сразу отфильтровать  фон и везде, где встречается  цвет фона, выдавать нули во всех разрядах.

Описанный метод распознавания  фигур после определенной доработки  может быть использован в реальных системах искусственного интеллекта. Его главным нюансом и, возможно, преимуществом является автоматная модель, которая ранее для распознавания  образов практически не применялась [3]. Чтобы выяснить, какие перспективы  открывает эта модель, требуется  серьезное дополнительное исследование. Также следует иметь в виду, что, в сущности, предлагаемый метод  является всего лишь способом перевода двухмерных изображений в форму, удобную для распознавания.

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

Список литературы

1. Левин В.И. Автоматная  модель и методы распознавания  образов. // Изв. АН СССР. Техническая  кибернетика. – 1991. – №3. –  с. 5-7.

2. Распознавание оптических  изображений. / Под общ. ред. Ю.С.  Сагдуллаева, В.С. Титова. – Ташкент:  ТЭИСЧ, 2000.

3. Искусственный интеллект.: Модели и методы. / Под ред. Д.А.  Поспелова. – М.: Радио и связь. -Кн. 2. - 1990.