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

 

СПОСОБ РАСПОЗНАВАНИЯ ГБОМЕТ РИЧЕСКИХ ФИГУР, основанный на скаНИ-. ровании и преобразовании изображения фигуры в последовательности широтномодулированяых импульсов, о т л ичающийся тем, что, с, целью расширения области применения за счет, обеспечения инвариантности при аффинных преобразованиях распознаваемой фигуры, сканируют и.зображениё фигуры при непрерывном изменении угла сканирования, преобразуют дая каждого угла сканирования последовательность широтно-импульсных сигналов в интегральные сигналы, выделяют в интегральных сигналах последовательность экстремальных уровней, фиксируют количество экстремальных уров . н ей и гл обальный эк стретлаль ный уровень в коделенной последовательности, по KOTOpbw судят о распознаваемой (Л фигуре. tsD О СХ) 4i

СОЮЗ СОВЕТСНИХ

Otltl6

РЕСПУБЛИН,З«5П G 06 К 9 ОО

l

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ИЙ (21) 3396673/18-24 (22) 12.02 ° 82 (46) 30 05 83. Бюл. В 20 (72) В. И Гордиенко, В. В. Грицык и Б. П..Русин (71) Фиэйко-механический институт

АН украинской CCP (53) 681. 391. 19 (088. 8) (56) 1. Шибанов Г. П. Распознавание в системах автоконтроля. И., "Машиностроение", 1972, .с. 424;

2. Патент «2IA 9 2787188, кл. 235-181, 1964.

3. Авторское свидетельство СССР

Ф 446087, кл. 6 06 К 9/ОО, 1974 (прототип). (54)(57) СПОСОБ РАСПОЗНАВАНИЯ ГЕОМЕТР"

РИЧЕСКИХ ФИГУР, основанный на скани-, ровании и преобразовании изображения ,SU„„A фигуры в последовательности широтномодулированных импульсов, о т л и.ч а ю шийся тем, что, с. целью расширения области применения за счет обеспечения инвариантности при аффинных преобразованиях распознаваемой фигуры, сканируют изображение фигуры при непрерывном изменении угла сканирования, преобразуют для каждого угла сканирования последователь. ность широтно-импульсных сигналов в интегральные сигналы, выделяют в ин. тегральных сигналах последовательность экстремальных уровней, фиксируют количество экстремальных уров,ней и глобальный экстремальный уровень в выделенной последовательности, Я по которым судят о распоэнаваемойфигуре.

1020840

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

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

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

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

Все в целом приводит к усложнению технической реализации способов, а значит к значительным временным затратам на распознавание. 45

Так, согласно прототипу, для принятия решения о распознавании в нем

2Ti необходимо сформировать q сигаЧ налов-образов, число которых зависит от а Р- шага сканирования образа, и сравнить их с эталоинымн сигналами, Для этого в изобретении предложена операция q-разового вращения изображения образа (фигуры) с одновременным

Формированием ц суммарных сигналов, что увеличивает время распознавания.

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

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

Пусть исследуемые образы отражаются рецепторным полем, состоящим из

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

Тогда, если, например, в каждой из строк рецепторного поля определить суммарное количество единиц и построить во времени распределения суммарных отсчетов, то получим сигнал-образ U<(t), характеризующий структуру изобрйжения вдоль строк рецепторного поля, т.е. в Направлении 1 . Аналогичный сигнал-образ определен и в другом произвольном направлении сканирования 9 . Полученные в результате операцйи суммирования импульсыобразы для разных классов изображе.ний, передающие структуру образа в направлениях сканирования Y и V> приведены на фиг. 2.

Изменение местоположения и размеров изображения образа в поле анализа характеризуются соответственно коэффициентами р и r . Исходя из построения сигналов-образов, запишем, что

U< (x, у, t) 0 (м g р,>1y,t)

cons t ц, () - 1-u (t); V 0,2Л, (1) где х и у - координаты образа,t " ""ape.

Мяе

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

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

1020840 количества информации для описания образов, а значит и дополнительного уменьшения времени на распознавание.

Рассмотрим сигналы-образы (фиг. 2

a — Ь ). Моменту времени t, в кото1 рый меняется скорость измерения импульса, соответствует амплитудное значение уровня U . Следовательно, 1 любой сигнал-образ U+(t) однозначно характеризуется. параметрами

ft>,U;«<. Количество уровней 1< для 10 сигнала зависит oz типа и формы, т.е. структурных свойств распознаваемых Фигур, а также от направления сканирования. Каждому j-му классу образов можно поставить в соответ- 15 ствие максимальное количество уровней

I> max (1 «У У= 0,2 У, У! = 1,ц (2) где q — количество классов образов.

Так, например, для классов тре- 20 угольников 1. 1 1, четырехуголь.1 ников 1 = 12 2 и т.д.

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

Исследования структурных свойств образов показывают, что достаточно всего дважды просканировать образ, З0 сформировать импульсы-образы, определить для каждого из них 1 и 1 количество уровней, выбрать максймальное значение max 1 л 1<р2 и сравнить ее с первой эталонной последовательностью. Для этого необходимо найти разницу

max 1, alp «- 1 °, 4j = 1,q (3) ! t между мак аимальным количеством уров- 40 ней и членами первой эталонной последовательности. Если разность (3) равна нулю, т.в. max fly л lq «совпадает с одним иэ эиаченйй аах (1 «, то выносимая решение о "грубом" рас- 45 познавании образа, т.е. происходит . определение класса, к которому он принадлежит. Как вйдим, на первом этапе распознавания предлагаеьий способ не зависит от еффинных преоб 50 разоваиий образа.

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

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

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

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

Вторая эталонная последовательность —. множество всех амплитудных значений уровней„определенное для всех направлений сканирования образа.

Ф у 2в

= ф;, u,.);., q=g+j = 1,q (q.)

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

В том случае, когда известны образы, которые будут предъявлены для распознавания, вторая эталонная.последовательность строится расчетным путем по формулам. В этом случае, когда заранее не известны анализируемые образы, для формирования (4) необходимо образ предварительно просканировать в направлениях 9 0,Х и определить для каждого из них параметры (й„, 01j< . Сокращение числа операций сканирования от Ч = О до

Ч = л, а не до V= 2, при формировании 0 (й) и определении )t-, U„-, обусловлено тем, что для выбранного признака, положенного в основу способа, образ обладает симметричностью.

Таким образом, по сравнению с прототипом уменьшаем объем. памяти для хранения вторых эталонных последовательностей, тем самым сокращаем время на формирование описания (4) и на распознавание.

Решение о детальном распознава,нии принимают в результате принадлежности параметров E t;, U>) второй эталонной последовательности, т.е. разность должна быть равна нулю.

1020840

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

Устройство содержит первый блок

1 памяти, первый и второй блоки 2 5 и 3 формирования сигналов-образов, первый и второй блоки 4 и 5 определения амплитудных .значений уровней, блок б управления, блок 7 нормирова- . ния, блок 8 определения максималь- 10 ного количества уровней, первый и второй блоки 9 и 10 сравнения, второй блок 11 памяти, блок 12 обучения.

Устройство работает следующим образом. 15

По команде из блока б управления. входная информация, т.е ° бинарное иэображение образа, записывается в первый блок 1 памяти, который представляет собой оперативно-запоминающее устройство. Окончив запись, по . 20 команде из блока б в блоках 2 и 3 формируется. суммарное количество единиц в двух произвольных направлениях рецепторного поля (например, вдоль строк Ч.,и столбцов 9<). Тогда на выходе каждого из них получаем два сигнала U< (t) и Uq (с), передающие структуру образа в направлениях

1 и "Z . Затем в блоках 4 и 5 определяем амплитудные значения уровней

О„,р и (t 0„) (g сигналов-образов, маЪсимальное количество которых формируем при сравнении lq и 1 в блоке; 8.

Для "грубого" распознавания обра- 35 зов предназначен первый блок 9 срав нения, на первый вход которого поступает max 1 л 1,р 1>,а на второй—

1 2 первая эталонная посЛедовательность

l., Чтобы разбить класс распознанноА образа на подклассы, т.е. для детального распознавания, предназначен второй блок 10 дравнения, на первый вход которого подаются амплитудные значения уровней, а на второй— вторая эталонная последовательность.

Блоки 9 и 10 реализуют операции (3) и (5). В том случае, когда не совпадают масштабы исследуемого и эталонного образа, применяется блок 7 нормирования, в котором происходит нормирование по масштабу амплитудных значений уровней ° Блок 12 обучения. предназначен для формирования первой и второй эталонных последовательностей и записи их во второй блок 11 памяти, когда заранее неизвестны классы распознаваемых образов. Результаты распознавания получаем на выходах блоков 9 и 10.

Таким образом предлагаемый способ распознавания и устройство, реализующее его, по сравнению с прототипом позволяет расширить область применения, а также позволяет при дискретности сканирования 4Y= 5 повысить быстродействие распознавания в 36 раэ,. на порядок уменьшить объем памяти на хранение эталонных последовательностей. Уменьшение числа операций поворота образа и объема памяти на хранение эталонных характеристик позволяет не только улучшить технические характеристики предлагаемого способа (повысить быстродействие) но и уменьшить аппаратурные затраты на реализацию способа распознавания образов.

1UZU840

Составитель Т Ничипорович

Редактор С. Квятковская Техред «Т.фанта

Заказ 3899/42 Тираж 706

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Рауыская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Корре кт ор A. ференц

Подписное