Способ распознавания геометрических фигур Советский патент 1983 года по МПК G06K9/00 

Изобретение относится к автоматике и вычислительной технике и может найти применение при распознавании плоских геометрических фигур произвольной конфигурации, при анализе микробиологических препаратов и рент генограммы, в установках неразрушаюсцего контроля и роботехнике. Известны способы распознавания образов, основанные на формировании сигналов корреляции либо автокорреляционных функций между объекте и эталонами. При этом необходимо проводить трудоемкий процесс вращения изображения образа относительно набора эталонов или наоборот Cl f2J. Наиболее близким к предлагаемому является способ распознавания геомет рических фигур основанный на сканировании и преобразовании изображения фигуры в последовательность широтномодулированных импульсов. Распознавание проводится путем построчного сканирования участка изображения объ екта с последующим преобразованием в видеосигналы с одновременным формированием суммарных, сигналов и срав нением с эталонными сигналами 3Jf . Недостатком известных способов является ограниченная область примен ния из-за неинвариантности или части ной инвариантности к аффинным преобразованиям (масштабированию, параллельному переносу и повороту) исследу,емых образов в поле анализа. Это требует, во-первых, проведения технически сложной операции вращения изображения образа относительно набора эталонов или наоборот; во-вторых, нормировани образа по масштабу; в-третьих, устра нения зависимости способов от параллельного переноса образа, т.е, изменения местоположения в поле анализа. Все в целом приводит к усложнению технической реализации способов, а значит к значитвльньо4 временным затратам на распрзяаваниё. Так, согласно прототипу, для принятия решения о распознавании в нем необходимо сформировать q налов-образов, число которых зависит от шага сканирования образа, и сравнить их с эталоннБми сигналами Для этого в изобретений предложена операция q-разового в равдения изобра жения образа (фигуры) с одновременны формированием q суммарных сигналов, что увеличивает время распознавания. Цель изобретения - расширение области применения за счет обеспечения инвариантности при аффинных преобразованиях распознаваемой фигуры. Указанная цель достигается тем, что согласно способу распознавания геометрических фигур, основанном на сканировании и преобразовании изоб ражения фигуры в последовательности широтно-модулированных импульсов, сканируют изображение фигуры при непрерывном изменении угла сканирования, преобразуют для Кс1ждого угла сканирования последовательность широтно-импульсных сигналов в интегральные сигналы, выделяют в интегральных сигналах последовательность экстремальных уровней,фиксируют количество экстремальных уровней и глобальный экстремальный уровень в выделенной последовательности, по которым судят о распознаваемой фигуре. На фиг. 1 приведены изображения геометрических (гур) на фиг, 2 сигналы-образы этих фигур; на фиг, 3эталонные последовательности сигналов, которые соответствуют распознаваемым образам; на фиг, 4 - одно из возможных устройств, реализукадее предлагаемый способ распознавания. Пусть исследуемые образы отражаются рецепторным полем, состоящим из MxN элементов, Причем рецепторный элемент принимает значение единицы, если он лежит внутри или пересекает образ, и нуль, когда лежит извне, тогда, если, например, в каждой из строк рецепторНого поля определить зуммарное количество единиц и построить во времени распределения суммарных отсчетов, то получим сигнал-образ Ut,,(t), характеризующий структуру изображения вдоль строк рецепторного поля, т,е, в направлении Ч. Аналогичный сигнал-образ определен и в другом произвольном направлении сканирования . Полученные в результате операции сум1«мрования импульсыобразы для раз 1шх классов изображений, передающие структуру образа в направлениях сканирования и fn приведены на фиг, 2, Изменение местоположения и размеров изображения образа в поле анализа характеризуются соответственно коэффициентами риг. Исходя из построения сигналов-образов, запишем, что tUvf (х, у, t) - Ut(x ± р , s ± р , t) const Ui,(t) tti fit}, vt «-бти , (1) где X И у - координаты образа,t - время,, Из (1) следует, что принятые за основу признаки фигу&л (сигналы-образы) не изменяют своей формы при гомотетиях, т,е, инварианты относительно двух аф {яинных преобразований параллельного переноса и изменения масштаба,Сущность данног о способа заключается в определении для каждого сигнала-образа количества 1. амплитудных значений уровней U импульсов,. Это приводится с целью сокращения количества информации для описания образов, а значит и дополнительного уменьшения времени на распознавание Рассмотрим сигналы-образы (фиг. 2 а -Ъ). Мементу времени t-, в кото рый меняется скорость изменения импульса, соответствует амплитудное значение уровня U.. Следовательно, любой сигнал-образ Ui(t) однозначно характеризуется параметрами Количество уровней l для сигнала зависит от типа и формы, т.е. структурных свойств распознава емых фигур, а также от направления сканирования. Каждому j-му классу Образов можно поставить в соответствие максимальное количество уровнейIj max {|,}уЧ 0,2л ,Vj iTq где q - количество классов образов. Так, например, дщя классов треугольников 1 1 1, четырехугольНИКОВ 1: Ig 2 и т.д. в связи с таким представлением образа первая эталонная последовательность состоит из максимальных ааачений количества уровней для всех рассматриваемых Классов образо Исследования структурных свойств образов показывают, что достаточно всего дважды просканировать образ сформ1фовать импульсы-образы, определить для каждого из них 1 цци Ii, количество уровней, выбрать максимальное значение max {1(л . сравнить ее с первой эталоннои посяедовательностью. Для этого необхо димо найти разницу max p(f j,Vj 1,q (З) между максимальным количе-ством уров ней и членами первой эталонной последовательности. Если разность (3) равна нулю, т.е. max л 1ц| совпадает с одним из значений max {lif то выносится решение о грубсм рас познавании образа, т.е. происходит определение класса, к которому он принадлежит. Как , на первом этапе распознаван 1Я предлагаемая способ не зависит от аффинных преоб разований образа. Введение грубого распознавания с характеристикой образа параметром f позволяет сократить количество информэдии для описания образа, тем самь№1 уменьшить как объем памяти на первую эталонную последовательность так и количество операций вычитания (3) дпя принятия решения. Все это в целс«1 позволяет намного повысить быстродействие распознавания. Однако при распознавании образов возникают задачи определения не только класса анализируемых гесметри ческих фигур, но и подкласса. Напри мер, если в результате первого этапа было принято решение f образ треугольник, закономерен вопрос, какой: произвольный, равносторонний и т.д. Для решения этого вопроса предназначен второй этап детального распознавания, который заключается в следующем, В основу детального распознавания положен интегральный признак фигуры, который не только инвариантен относительно гомотетий и поворота, но и обладает тем свойством, что не существует двух образов, различных по форме и конфигурации, для которых интегральный признак был бы одинаков - это эталонная .траектория образа, т.е. вторая эталонная последовательность. Вторая эталонная последовательность -. множество всех амплитудных значений уровней, определенное для всех направлений сканирования образа. Dj сч. a,v, jT с) Если соединить между собой вершины амплитудных значений уровней, то получим огибающую, которую назовем эталонной траекторией .образа (фиг. 3). Утверждение, что не существует двух одинаковых траекторий образов, следует из того, что нет двух изображений образов, обладающих одинаковой внутренней структурой во всех направлениях. Ъ том случае, когда известны образы, которые будут предъявлены для распознавания, вторая эталонная последовательность строится расчетным путем по формулам, в этом случае, когдй заранее не известны анализируемые образы, для формирования (k} необходимо образ предварительно просканировать в направлениях Ч О,JT и определить для каждого из них параметры {t , . Сокращение числа операций сканирования от О до У JI , а не до V 2 Л, при формировании Ut|(t) и определении (t. , }tf обусловлено тем, что для выбранного признака, положенного в основу спбсоба, образ обладает симметричностью. Таким образом, по сравнению с прототипом уменьшаем объем памяти для хранения вторых эталонных последовательностей тем самым сокращаем время на форАшрование описания С) и на распознавание. Решение о детальном распознаваНИи принимают в результате принадлежности параметров t| , U|J If второй эталонной последовательности, т.е. им. Vj 1 ,q (5)i f разность должна быть равна нулю.

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

Устройство содержит первый блок 1 памяти, первый и второй блоки 2

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

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

По команде из блока 6 управления Входная информация, т.е. бинарное изображение образа, записывается в .первьлй блок 1 памяти, который представляет собой оперативно-запоминающёе устройство. Окончив запись, по команде из блока б в блоках 2 и 3 формируется суммарное количество единиц в двух произвольных направлениях рецепторного поля (например, вдоль строк столбцов fg) Тогда на выходе каждого из них получаем два сигнала 0 (t) и U qig (t), пере дающие структуру образа в направлениях 41, и 2 Затем в блоках 4 и 5 определяем амплитудные значения уровней ч и 1/2СИгналов-образов, максимальное количество которых формируем при сравнении Ii и f в блоке , 8..

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

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

« }

ОС

S

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