Распознавание самолетов

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

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

Другой метод распознавания основан на использовании инвариантных характеристик контура самолета [9]. В качестве таких инвариант рассматриваются центральные моменты, вычисляемые по формуле:

Распознавание самолетов - student2.ru

где Распознавание самолетов - student2.ru и Распознавание самолетов - student2.ru — координаты Распознавание самолетов - student2.ru -й точки изображения, a Распознавание самолетов - student2.ru и Распознавание самолетов - student2.ru — их средние значения по множеству из Распознавание самолетов - student2.ru точек. Были исследованы несколько моментов:

Распознавание самолетов - student2.ru

Распознавание самолетов - student2.ru

Распознавание самолетов - student2.ru и т. д.

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

Третий метод заключается в представлении самолета вектором, составляющими которого являются коэффициенты разложения контура в ряд Фурье. Поскольку контур, как правило, замкнут, то его разлагают в ряд как периодическую функцию. В противном случае разомкнутый контур рассматривают как один период периодической функции [9]. Ряд Фурье записывают в виде:

Распознавание самолетов - student2.ru ,

где Распознавание самолетов - student2.ru – угол отклонения радиус-вектора z. Комплексные коэффициенты ряда вычисляются: Распознавание самолетов - student2.ru .

Достоинство этого метода состоит в том, что при соответствующей нормировке такое описание не зависит от изменения масштаба, угла поворота и сдвига.

Для распознавания необходимо составить библиотеку контуров всех возможных типов самолетов, подлежащих классификации. Разделение на классы выполняется по принципу минимального расстояния от границы раздела классов.

Литература

  1. Фу К., Гонсалес Р., Ли К. Робототехника: Пер.с англ. / Под ред. В.Г.Градецкого. – М.: Мир, 1989. – 624 с.
  2. J. P. Gambotto et T. S. Huang, "Motion analysis of isolated targets in infrared image sequences", 7th Int. Conf. on Pattern Recognition, Montreal, 1984. P. 534—538.
  3. J. P. Gambotto, "Correspondance analysis for target tracking in infrared images", 7th Int. Conf. on Pattern Recognition, Montreal, 1984. P. 526—530.
  4. L. Gerardin, "La bionique", Hachette Paris, 1968.
  5. Жерарден Л. Бионика. Пер. с франц. М. Н. Ковалевой. Под ред. и с предисл. проф. В. И. Гусельникова. М.: Мир, 1971. 231 с.
  6. S. С. Guinot, A. Faure, J. P. Lallemand, A. Leblond et D. Murguet, "Etude de systemes mecaniques evolues et rapides dotes d'intelligence artificielle", Contrat DRET 80—624, sept. 1981.
  7. J. F.Gilmoreet, W. B. Pemberton "Asuivey of aircraft classification algorithms", 7th Int. Conf. on Pattern Recognition, Montreal 1984. P. 559—562.
  8. R. C. Gonzales et M. G. Thomason, "Syntactic pattern recognition", Edit. Addison Wesley, Londres, 1978. P. 118—120.
  9. Восприятие и распознавание образов / Пер. С фр. А.В. Серединского; под ред. Г.П. Катыса. - М.: Машиностроение, 1989 г. - 272 с.: ил.

Распознавание рукописных знаков

Задача распознавания рукописных знаков окончательно еще не решена, так как существует много как теоретических, так и практических трудностей, связанных с огромным многообразием возможных написаний отдельных рукописных знаков. Многие работы в этой области так или иначе связаны с общим принципом, который получил название анализа посредством синтеза, предусматривающим, что процедура распознавания строится на основе знаний о процессе синтеза рукописных знаков. На множестве рукописных знаков выделяется несколько элементов, называемых штрихами, из которых можно построить любой символ по определенным правилам соединения штрихов. Генерируемые по этим правилам знаки представляют собой некоторый идеализированный стандарт [1].

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

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

Распознавание самолетов - student2.ru ,

где Распознавание самолетов - student2.ru , Распознавание самолетов - student2.ru , -- Распознавание самолетов - student2.ru -й элемент изображения, являющийся одним из элементарных изображений Распознавание самолетов - student2.ru ; Распознавание самолетов - student2.ru - длина изображения.

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

Распознавание самолетов - student2.ru ,

где Распознавание самолетов - student2.ru - Распознавание самолетов - student2.ru -й элемент эталона, определенный на множестве допустимых направлений Распознавание самолетов - student2.ru .

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

Для построения алгоритма распознавания используется метод максимального правдоподобия. Решающее правило определяется выражением

Распознавание самолетов - student2.ru . (1)

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

Для реализации решающего правила (1) вместо величины Распознавание самолетов - student2.ru можно использовать монотонно убывающую функцию от этой величины. В качестве такой функции предлагается использовать функцию вида

Распознавание самолетов - student2.ru , (2)

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

С учетом выражения (2) решающее правило может быть определено следующим образом:

Распознавание самолетов - student2.ru .

Это означает, что среди всех классов Распознавание самолетов - student2.ru ищется такой класс Распознавание самолетов - student2.ru , эталон длиной Распознавание самолетов - student2.ru которого дает минимальное значение функции отличия (или максимальное значение функции сходства).

Процесс синтеза эталона Распознавание самолетов - student2.ru из эталона минимальной длины может быть представлен в виде графа, приведенного на рис. 1 и построенного для изображения, состоящего из четырех штрихов. Каждому элементу входного изображения на графе соответствует одна тонкая наклонная линия. Элементам эталона минимальной длины соответствуют горизонтальные линии. Если на Распознавание самолетов - student2.ru -м месте в эталоне может стоять Распознавание самолетов - student2.ru -й элемент минимального эталона, то на пересечении Распознавание самолетов - student2.ru -й вертикальной и Распознавание самолетов - student2.ru -й горизонтальной линий должна находиться вершина графа с индексом Распознавание самолетов - student2.ru (называемая допустимой). Допустимые вершины графа соединяются стрелками, направленными сверху вниз и слева направо. Вершины Распознавание самолетов - student2.ru соединяются с вершинами Распознавание самолетов - student2.ru или Распознавание самолетов - student2.ru . Любая возможная эталонная последовательность Распознавание самолетов - student2.ru , полученная из минимальной эталонной последовательности Распознавание самолетов - student2.ru , представляется на графе путем, который начинается в точке Распознавание самолетов - student2.ru , Распознавание самолетов - student2.ru и оканчивается в точке Распознавание самолетов - student2.ru . Присвоив каждой допустимой вершине графа с индексами Распознавание самолетов - student2.ru значение Распознавание самолетов - student2.ru , задачу о нахождении ближайшего к входному изображению эталона можно свести к задаче о нахождении длины кратчайшего пути на графе. Эта задача решается в соответствии с рекуррентными соотношениями

Распознавание самолетов - student2.ru

Здесь Распознавание самолетов - student2.ru - кратчайший путь из начальной вершины в вершину с индексами Распознавание самолетов - student2.ru . Значение Распознавание самолетов - student2.ru дает длину кратчайшего пути.

Эталон Распознавание самолетов - student2.ru находится простым перебором.

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

Распознавание самолетов - student2.ru
Рис. 1. Процесс синтеза эталона: / - 4 - штрихи.

Распознавание самолетов - student2.ru
Рис. 2. Граф, состоящий из трех штрихов.

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

Экспериментальная проверка описанного алгоритма показала, что некоторые "трудные" знаки, например Распознавание самолетов - student2.ru и Распознавание самолетов - student2.ru , оказываются трудно различимыми, так как они не различаются ни порядком, ни направлением последовательности штриха. Это вызвало необходимость ввести более жесткие ограничения на допустимые варианты генерируемых эталонов путем установления допустимых изменений штрихов эталона снизу и сверху. Отличие такого алгоритма от описанного выше состоит в том, что изменения длины штрихов минимального эталона ограничены сверху пределом, определяемым для каждого класса. Для этой цели используется схема построения графа, приведенная на рис. 2. Горизонтальные линии графа соответствуют элементам генерируемого эталона. Каждая горизонтальная линия, имеющая двойную индексацию Распознавание самолетов - student2.ru (индекс Распознавание самолетов - student2.ru указывает порядковый номер элемента в штрихе, имеющем порядковый номер Распознавание самолетов - student2.ru ), отмечена либо черной точкой, либо кружком. Черной точкой отмечаются элементы, обязательные для эталона, кружком - не обязательные.

Граф представляет собой наибольший из возможных эталонов данного класса. Граф, приведенный на рис. 2, состоит из трех штрихов. Вертикальные линии графа соответствуют элементам входного изображения. Минимальная длина эталона 7, максимальная 12. Входное изображение состоит из 11 элементов. Каждая вершина графа определяется тремя координатами: Распознавание самолетов - student2.ru , где Распознавание самолетов - student2.ru - номер элемента входного изображения.

Каждой вершине графа соответствует некоторая величина Распознавание самолетов - student2.ru , определяемая как кратчайший путь в эту вершину из начальной точки. Вычисление кратчайшего пути из начальной точки в конечную осуществляется по рекуррентным формулам

Распознавание самолетов - student2.ru

где Распознавание самолетов - student2.ru - результат сравнения элементов эталона Распознавание самолетов - student2.ru с элементом входного изображения Распознавание самолетов - student2.ru ; Распознавание самолетов - student2.ru - номер последнего в штрихе обязательного элемента; Распознавание самолетов - student2.ru - номер последнего в штрихе необязательного элемента.

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

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

Если заглянуть в историю, то среди первых разработок, прошедших испытания, можно выделить читающие автоматы Р711 и РУТА-701 Вильнюсского СКВ вычислительных машин.

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

При испытании автомата Р711 вероятности отказа и ошибки для документов, которые соответствовали установленным требованиям, были порядка Распознавание самолетов - student2.ru . Документы, не соответствующие по качеству, перед началом испытания отбраковывались. При исключении предварительной отбраковки документов вероятности отказов и ошибок заметно повышались. Было изготовлено два образца автомата Р711.

Автомат РУТА-701 предназначен для ввода в вычислительную машину многострочных документов. Автомат читает десять цифр и четыре служебных символа. Рукописные цифры должны, так же как и в автомате Р711, вписываться в небольшие прямоугольники, заранее напечатанные на документе краской, не воспринимаемой автоматом. Максимальная скорость чтения автомата составляет 220 знаков в секунду. Вероятность ошибки имеет порядок Распознавание самолетов - student2.ru . Машинописные цифры распознаются методом сравнения с эталоном, рукописные цифры - с помощью специально выбранной системы признаков. В обоих случаях необходима центровка изображения.

Существовали автоматы, в основу которых положен метод сравнения с эталоном. Критерием сходства в этом автомате служит расстояние по Хеммингу. Сначала производится центрирование изображения, а затем предварительная классификация по наличию и расположению линий знака. После этого уже осуществляется сравнение с эталоном. Автомат предназначен для чтения типографских текстов и рассчитан на несколько таких шрифтов. Эталоны всех знаков каждого шрифта хранятся в памяти и вызываются по мере необходимости в оперативную память. Скорость действия автомата около 100 знаков в секунду, вероятность ошибки - порядка Распознавание самолетов - student2.ru .

Многошрифтовой автомат фирмы "Radio Corporation of America" был сконструирован так, что изображение в нем считывается с помощью электронно-лучевой трубки типа "бегущий луч" и фотоумножителя, а затем воспроизводится на экране двухлучевого кинескопа в виде позитива и негатива. С помощью оптического размножителя полученные на экране изображения проектируются на эталонные маски, которые представляют собой высококонтрастные позитивные и негативные изображения эталона. Позитивное изображение накладывается на эталон-негатив, а негативное изображение - на эталон-позитив. Степень несовпадения распознаваемого знака с данным эталоном характеризуется результирующим световым потоком по каждому каналу. Распознавание производится по наименьшему световому потоку. В каждом канале установлены фотоумножители и интеграторы, которые преобразуют световые потоки в соответствующие электрические сигналы. В автомате предусмотрена специальная система управления, которая выполняет следующие действия: переключение операций (поиск знака, поиск строки, чтение знака) и центровку знака. Кроме того, в автомате используется так называемая принудительная идеализация распознаваемых знаков. Это осуществляется с помощью специальной системы автоматического регулирования яркости и контрастности изображения распознаваемого знака, полученного на экране двухлучевого кинескопа.

Автомат позволяет считывать и вводить в ЦВМ две печатные строки со стандартного бланка размером Распознавание самолетов - student2.ru мм. Скорость подачи документов составляет 6 документов в секунду, скорость чтения - 500 знаков в секунду. Автомат обладает высокой надежностью распознавания: одна ошибка на 200 000 знаков, т. е. число ошибочных ответов не превышает 0,0005%. Следует, однако, отметить, что приведенные цифры характеризуют испытание 16-канального макета, причем при оценке надежности не указывается качество печати распознаваемых знаков.

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

Литература.

Наши рекомендации