Способ опознавания объектов по их контурным изображениям
ОПИСАНИЕ ИЗОБРЕТЕНИЯ 372564
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союза Советских Социалистических Республик
Зависимое от авт. свидетельства №
Заявлено 13.II.1969 (№ 1311127/18-24) с присоединением заявки
Приоритет
Опубликовано 01.11.1973. Бюллетень № 13 Дата опубликования описания 25.12. 1973
М. Кл. G 064 9,00
Комитет по делам изооретений и открытий при Совете Министров СССР
УДК 621,391.19(088.8) Автор изобретения: В. И. Селяндин
Заявитель: Институт физико-технических проблем энергетики AH Литовской ССР
СПОСОБ ОПОЗНАВАНИЯ ОБЪЕКТОВ ПО ИХ КОНТУРНЫМ ИЗОБРАЖЕНИЯМ
Способ опознавания объектов по их контурным изображениям, относящийся к области технической кибернетики и вычислительной техники, может найти применение при классификации плоских фигур и проектировании объектов по их проекциям, при проектировании систем ввода данных (машинописной и рукописной алфавитно-цифровой информации и т. д.) в вычислительные устройства непосредственно с первичных бланков, при автоматической подготовке перфокарт, перфолент, магнитных карт и других носителей информации для ЭВМ, при проектировании самообучающихся систем, при анализе сложных кривых, при автоматической сортировке писем и другой корреспонденции и т. д.
Известны способы опознавания объектов по их контурным изображениям, основанные на выделении признаков замкнутости-разомкнутости, фиксируемых относительно строк с заранее заданным числом пересечений контурных линий.
Так, например, согласно одному из известных способов при построчном анализе изображения в местах перехода стоек с одним количеством пересечений на строки с другим количеством пересечений контурной линии выделяют разделяющие сечения (строки), по отношению к которым фиксируют признаки замкнутости-разомкнутости и их последовательности.
Необходимость привязки признаков к строкам заранее заданного характера затрудняет использование известных способов при опознавании изображений со значительным разнообразием конфигураций, а также когда помехи изменяют количество пересечений контурной линией изображения строк кадра опозпавания.
Предлагаемый способ отличается от известных тем, что признаки замкнутости-разомкнутости контура изображения выделяют путем анализа на перекрытие проекций последовательностей неконтурных элементов смежных строк изображения, ограниченных черно-белыми (и наоборот) переходами, на прямую, параллельную строкам изображения, причем критерием перекрытия является присутствие единичных разрядов в логическом произведении неконтурных элементов рассматриваемых последовательностей; признаки замкнутости-разомкнутости объединяют в парные сочетания, для которых определяют параметры, характеризующие взаимное положение частей изображения объекта, содержащих соответствующие замкнутости-разомкнутости контура изображения.
Для этого после дискретного считывания 30 изображения объекта выделяют сигналы от на чказанную прямую всех М сегментов. Если неконтурных элементов строк, ограниченных черно-белыми переходами и черно-белыми переходами и краем изображения, попарно сопоставляют полученные последовательности сигналов между собой, из полученных разностных последовательностей формируют сигналы признаков замкнутости-разомкнутости, объединяют полученные последовательности сигналов в пары, которые сопоставляют путем последовательного сравнения друг с другом, по результатам сравнения формируют последовательности, характеризующие взаимное положение различных частей изображения, содержащих соответствующие замкнутостиразомкнутости контура, и сравнивают выделенные последовательности с эталонными для принятия решения о принадлежности опознаваемого объекта.
В результате этого достигается полная инвариантность полученных различительных признаков к размерам и положению изображений в кадре опознавания, к искажениям конфигурации контура изображения (в некоторых пределах), к изменениям его толщины, а также к ограниченному повороту изображения (порядка 4-20 ) относительно кадра опознавания, На фиг. 1 — 10 представлены изображения некоторых рукописных знаков, опознаваемых данным способом; на фиг. 11 приведена блоксхема устройства, реализующего данный спо-: соб.
Предположим, что контурное изображение опознаваемого объекта формируется на плоскости, состоящей из E(XL элементов (элементарных площадок). Изображение считывается устройством восприятия (например, преобразователем с бегущим лучом, матрицей светочувствительных элементов, линейкой фотоэлемента и др.), которое вырабатывает сигналы, отображающие значения оригинала, таким образом, что если элемент плоскости или заданная его часть содержит контур изображения, сигнал равен единице, в противном случае сигнал равен нулю. Назовем элемент плоскости контурным, если выработанный для него сигнал равен единице, и неконтурным, если сигнал равен нулю.
Примем в качестве элементарных компонент изображения последовательность смежных неконтурных элементов его строк, которую назовем сегментом. Сегмент, крайний слева в строке изображения, назовем «внешним» слева; сегмент, крайнии справа, — «внешним» справа; сегмент (сегменты) строки изображения, не являющийся внешним (слева или справа), назовем «внутренним».
Далее, введем понятие «перекрывающиеся» сегменты и произведение сегментов. Скажем, что сегменты перекрываются, если их проекции на прямую, параллельную строкам изображения, имеют общие точки, т. е. перекрываются.
«Произведением» М сегментов назовем сегмент, точки которого принадлежат проекциям обозначить через F, r-ный (r=1,2,...N(k) ) сегмент й-ой (юг=1,2,..., К) строки изображеlг ния, произведение сегментов F и F можно записать так:
Формула
Используя введенное понятие, дадим следующие определения замкнутости и разомкнутости контура изображения. Контур изображения является разомкнутым, если строка изображения содержит внутренний сегмент, перекрывающийся с внешним сегментом той или другой строки изображения, смежной с данной, причем, если этот внешний сегмент является внешним слева, соответствующую разомкнутость контура назовем разомкнутостью слева, если же указанный сегмент является внешним справа, — разомкнутостью справа.
Контур изображения является замкнутым, если строка изображения содержит внутренний сегмент, не перекрываемый ни одним сегментом той или другой строки изображения, смежной с данной строкой (фиг. 1, 3, 4, 6).
Данный способ основан на использовании не отдельных замкнутостей-разомкнутостей контура, а их парных сочетаний, которые определяют следующим образом. ,с
Пусть Fm и Рn — два внутренних (1 Fk связан с сегментом Fi Обозначим это Р"Р, если в каждой р-ой строке между Й-ой и l-ой строками изображения существует сегмент F,",g,,p такой, что Я <,> F <,",i>+О для р=k k+1 l — 1 4 22 Обращаясь к фиг. 1, находим, что F5 — r2 5 22 и F2 — F2 . Поэтому соответствующие замкнутости контура изображения объединяем в пары. Рассмотрим работу устройства (фиг. 11), реализующего предложенный способ опознавания. Устройство содержит воспринимающее устройство 1, блок 2 выделения сегментов с регистрами Ri, R2, схему 8 анализа регистров R, R2 с блоком счетчиков, блок 4 формирования признаков замкнутости-разомкнутости (ПЗ P), блок 5 формирования признаков различения (ПР), регистры ПЗР (регистры хранения признаков замкнутости-разомкнутости б, регистры ПР (регистры хранения признаков различения) 7, классификатор 8, блок хранения эта372564 лонных описаний 9 и блок принятия решения 10. С целью выделения замкнутостей-разомкнутостей контура изображения опознаваемого объекта сигналы, полученные устройством восприятия, обрабатываются следующим образом. В блоке 3 имеются две группы R и R2 регистров запоминания сегментов двух смеж1 1 1 ных строк изображения R)= (R1, R2, ", R1 ) и R =(R1, 2, "., Кг ) верхний индекс означает номер группы регистров, нижний номер регистра в данной группе) и схема выделения сегментов 1+1-ой строки изображения, которая распределяет сигналы, получаемые на выходе воспринимаемого устройства в процессе развертки изображения, так, что после считывания k+ 1-ой строки изображения 1-ая (l= 1,2,... L) ячейка регистра запоминания Р, сегмента F, оказывается в состоянии «1», если l-ый неконтурный элемент k+1-ой строки принадлежит сегменту F и в состоянии «О» — в противном случае (напомним, что сегмент определяется по наличию черно-белого и следующего бело-черного переходов в строке). От момента начала считывания k+1-ой строки изображения и до момента начала считывания А+2-ой строки в регистрах группы R хранится информация о сегментах Й-ой строки. Имеются далее схема анализа содержимого регистров R, R и совокупность счетчиков (г (a» a)2 ..., О(т, а21, 022,... a2T) СИГНаЛОВ hrs формируемых указанной схемой (олок 4). Схема анализа содержимого регистров сравнивает 1 состояние регистра R 1 с состоянием регист2 .2 2 ров R1, г;2, RN(1,), состояние регистра 2 2 2 2 R1 — с состоянием регистров Р1, R2 " Йяр+ц и т. д. таким образом, что на ее rXs выходе формируется сигнал h„если хотя бы две )г 1 2 одноименные ячейки регистров Rr Rs, находятся в состоянии «1» (согласно сказанному выше, наличие сигнала 6„свидетельствует гг )г-; 1 о том, что сегменты F, и Fs перекрываютk ся). Сигнал й„увеличивает содержимое счетчиков а,„и а2. на единицу. Затем в зависимости от состояния того или иного счетчика запускаются блок формирования признаков замкнутости-разомкнутости 5, блок формирования признаков различения б. Сигналы, формируемые на их выходе, поступают в регистры ПЗР— регистры хранения признаков замкнутости-разомкнутости 7 либо в регистры HP — регистры хранения признаков различения 8. Рассмотрим порядок работы указанных блоков (ci(. блок-схему фиг. 11). Блок формирования признаков замкнутостиразомкнутости 5 запускается в зависимости от состояния счетчиков а»,, a1N(l ) a22 23, гг2)(и.() 1 в блоке 8, Рассмотрим все возможные случаи: 1) Если содержимое счетчика а» (обозначи;1 его а») таково, что включается блок формирования ПЗР 5, который вырабатывает сигнал, указывающий на наличие разомкнутости контура слева (обозначим этот сигнал ()(),), запоминаемый в одном из регистров ПЗР, и одновременно записывает в этот регистр содержимое регистра и счетчика строк (число k) (предполагается, что содержимое данного регистра записывается в первые L ячеек регистра ПЗР). Затем содержимое счетчика а» уменьшается на «1», и вновь проверяется заданное условие. При его выполнении происходит описанный рабочий цикл с той лишь разницей, что в регистр ПЗР переписывается содержимое регистра Ra и т. д. до тех пор, пока не будет нарушено указанное выше условие. 2) Если содержимое счетчика а(, -(l,) таково, что aiN(k)) 1, включается блок формирования ПЗР 5, работающий, как описано выше, за исключением того, что в регистр ПЗР 7 записываются сигнал, свидетельствующий о разомкнутости контура справа (обозначим его ()(Т) ), и содержимое регистра R2N(), () ь затем регистра R (),+1) — 2 и т. д. до тех пор, пока не будет нарушено заданное условие. 3) Предположим, наконец, что содержимое счетчика a» z аково, что a2>=0, В этом случае также включается блок формирования ПЗР 5, который формирует сигнал, указывающий на наличие замкнутости контура (ооозначим его о)(Я). Этот сигнал, содержимое регистра Rp и счетчика строк записываются в регистр ПЗР 7. Блок формирования признаков различения б включается в зависимости от состояния счетчиков а2(, а2; (+(), п)2, а(з,..., a)N(l) 1 в блоке 3. Рассмотрим возможные случаи: 1) Если блок формирования HP б вырабатывает сигнал ()(р), который поступает в регистр ПР 8, и сигналы опроса первых L ячеек каждого регистра ПЗР 7 и регистра R1, причем в случае обнаружения хотя бы двух одноименных ячеек в соответствующих регистрах, находящихся в состоянии «1», информация, хранимая в ячейках L+1, L+2,..., данного регистра ПЗР (т. е. информации о ПЗР и номере строки, при а) ализе когорой был получен ПЗР), перезаписывается в регистр ПР 8, после чего регистр ПЗР очищается. Таким образом, в регистр ПР 8 оказывается записанной информация следующего вида: сигналы о наличии пары 372564 +2%(k+4) ) 1 а4(=0, ПЗР, например, о)(Я), о3(р) и два числа, например Уь У2 (U<(U2), указывающих номера строк изображения. Эта информация называется признаком различения. После опроса всех регистров ПЗР рабочий цикл блока формирования ПР б заканчивается. 2) Если включается блок формирования ПР 6, причем в этом случае в отличие от первого формируется сигнал о)(Т), а сигналы опроса поступают на регистры ПЗР и регистр Рл(),+4), В результате работы блока в одном из регистров ПР оказывается записанной информация вида (о)(H), о(T), U<, U2), где Не (p, Т, Q). 3) Пусть где Уе (2,3,... Ж((г) — 1). В этом случае включается блок формирования ПР. Работа его аналогична описанной выше с той лишь разницей, что формируется сигнал о)(Я), а сигналы опроса поступают на регистры ПЗР и регистр RæU Блок слежения включается в зависимости от состояния счетчиков à22, а23,..., 02N(k+)) — 4, причем для этого необходимо, чтобы содержимое проверяемого счетчика (обозначим его а2п) было отлично от «О». В этом случае генерируются сигналы опроса первых L ячеек содержимого регистра ПЗР 7 и регистра R2U. При обнаружении одноименных ячеек указанных регистров, находящихся в состоянии «1», в регистр соответствующего ПЗР записывается содержимое регистра P U. В результате рассмотренного процесса в регистрах ПР 8 после считывания всех строк изображения получают совокупность признаков различения, характеризующих конфигурацию локальных частей распознаваемого изображения и относительное положение последних в кадре распознавания. Аналогично изложенному происходит вторичный анализ изображения объекта (анализируются вертикальные строки изображения слева направо) и выделяются признаки замкнутости-разомкнутости контура изображения и параметры признаков. Для повышения помехоустойчивости способа опознавания предлагается: 1) нормировать параметры Уь U2 признаков замкнутости-разомкнутости согласно выражениям — v,— u, — u,— и,, U.= и. — v, u„— и. где Up и U (Uo(U ) — соответственно номера строк изображения, в пределах которых находится контур изображения распознаваемого объекта (строки, содержащие не менее двух сегментов}. 2) исключить из полученного набора признаков различения признаки, величина U2 — Г( для которых меньше заданного значения о. 3) если набор содержит признаки различения о) (Н,), о> (Н,), U„U,), и (Н,), а (Н,), U„U), Н„Н„Н„Н, (рT,Qj, выделенных в исходном (первоначальном) направлении а)(ализа, и Н(— — Н3, U(— — U3 либо Н2 — Н4 U2=U4 то из рассматриваемого набора исключить ПР (о)(Н1), о)(Н2), U>, U2), e"--.ч (U2 — Ю(В U3, и ПР (о) (Н3), н(H4), 3, U4), если Г2 — 01 Π— Т3. 4) если полученный набор ПР содержит М)2 llP (о)(Н), о)(Н), U), U22), Нв(Р)ТД), выделенных в исходном (первоначальном) направлении анализа, то из рассматриваемого набора исключить (М вЂ” 2) ПР с минимальными значениями U2 — Ui. 5) исключить из полученного набора ПР (о)(Q), (о(Я), (ть U2), выделенные при вторичном анализе изображения. 6) если полученный набор ПР содержит М() 1 ПР (o) (Q), о) (Н), О„U2), Нв (р) Т), выделенных при вторичном анализе изображения, то из рассматриваемого набора исключ((ть (М вЂ” 1) ПР с минимальными значениями (2 1) ° 7) если полученный набор ПР содержит М) ПР (о)(Н), о)(Я), У„U2), Не(р(Т), выделенных при вторичном анализе изображения, от из рассматриваемого набора исключить (М вЂ” 2) ПР с минимальными значениями (U2= Ut) ° В результате выполнения перечисленных пунктов получают совокупность признаков различения, которую сопоставляют с эталонной по любой известной схеме классификации. Предмет изобретения Способ опознавания объектов по их контурным изображениям, основанный на дискретном считывании изображения объекта, выделении топологических признаков замкнутости-разомкнутости контура и их последовательностей, сравнении полученной последовательности признаков с эталонными последовательностями, отличающийся тем, что, с целью повышения достоверности результатов опознавания, в процессе дискретного считывания изображения объекта выделяют сигналы от неконтурных элементов строк, ограниченных черно-белыми переходами и черно-белыми переходами и краем изображения, попарно сравнивают эти последовательности сигналов поразрядно друг с другом, по совпадениям единичных сигналов формируют сигналы, характеризующие признаки замкнутости-разомкнутости, эти сигналы попарно сравнивают друг с другом, по результатам сравнения формируют последовательности сигналов, характеризующие 372564 Риг. 2 Разюмкнутость конпура бпла 0аимкн твсть конту a спРМа локальные свойства изображения, и сравнива1от сформированные последовательности с этаЗамннутасть кснп ура лонными для принятия решения о принадлежности опознаваемого объекта, Редактор Б. Федотов Составитель В. Кудрявцев Техред Л. Грачева Корректор E. Сапунова Заказ 1131712 Изд. ¹ 332 Тираж 647 Подписное ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, 7К-35, Раушская наб., д. 4!5 Типография, п р. Сапунова, 2
