СПОСОБ ОПОЗНАВАНИЯ ОБЪЕКТОВI ЙСЕПОЮЭНАй • •': •!-.-;, ,-i,:,?i т-''"'^-•::.••'.^.^i:^:.^-{':.:•,';, •1:•:.''.--";'.-Г vTiC^ Советский патент 1973 года по МПК G06K9/50 

1

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

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

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

замкнутости-разомкнутости и их последовательности.

Необходимость привязки признаков к строкам заранее заданного характера затрудняет

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

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

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

Для этого после дискретного считывания

изображения объекта выделяют сигналы от

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

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

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

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

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

Далее, введем понятие «перекрывающиеся сегменты и произведение сегментов. Скажем, что сегменты перекрываются, если их проекции на прямую, параллельную строкам изображения, имеют общие точки, т. е. перекрываются. «Произведением М сегментов назовем сегмент, точки которого принадлежат проекциям на указанную прямую всех М сегментов. Если

обозначить через Fr г-ный (г,2,.. .N(k сегмент й-ой (й 1,2,...,/() строки изображения, произведение сегментов pl и Fs можно записать так:

ptt р1

г S

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

Данный способ основан на использовании не отдельных замкнутостей-разомкнутостей контура, а их парных сочетаний, которые определяют следующим образом.

Пусть Рт и Fn - два внутренних (:m.N(k, (l)

сегмента строк изображения (), каждый из которых не перекрывается ни одним из сегментов смежной строки, либо перекрывается одним из внешних ее сегментов. Согласно данным выше определениям это свидетельствует о наличии двух замкнутостей-разомкнутостей контура изображения. Эти замкнутости-разомкнутости объединяют в пару, если сегмент F т связан с сегментом Fn в соответствии со следующим определением. Допустим, что сегмент F связан с сегментом F. Обозначим это , если в каждой /9-ой строке между й-ой и /-ОЙ строками изображения существует сегмент Fm(,,) такой, что

,i) лля p k, k+l,..., . Обращаясь к фиг. 1, находим, что fs - Р

,-,51-22 „

и Га - Г2 . Поэтому соответствующие замкнутости контура изображения объединяем в пары.

Рассмотрим работу устройства (фиг. 11), реализующего предложенный способ опознавания.

Устройство содерл ит воспринимающее устройство I, блок 2 выделения сегментов с регистрами R, Rz, схему 3 анализа регистров R, Rz с блоком счетчиков, блок 4 формирования признаков замкнутости-разомкнутости (ПЗР), блок 5 формирования признаков различения (ПР), регистры ПЗР (регистры хранения признаков замкнутости-разомкнутости 6, регистры ПР (регистры хранения признаков различения) 7, классификатор 8, блок хранения эталонных описаний 9 и блок принятия решения 10.

С целью выделения замкнутостей-разомкнутостей контура изображения опознаваемого объекта сигналы, полученные устройством восприятия, обрабатываются следующим образом. В блоке 3 имеются две группы / и R регистров запоминания сегментов двух смежных строк изображения R(Ri, Rz, , RT и R(R, , ... , 7- ) верхний индекс означает номер группы регистров, нижний номер регистра в данной группе) и схема выделения сегментов +1-ой строки изобрал ения, которая распределяет сигналы, получаемые на выходе воспринимаемого устройства в процессе развертки изображения, так, что после считывания fe-l-1-ой строки изображения /-ая (,2,... L) ячейка регистра запоминания Rr сегмента F г оказывается в состоянии «1, если /-ЫЙ неконтурный элемент й+1-ой

строки принадлежит сегменту Fr , и в состоянии «О - в противном случае (напомним, что сегмент определяется по наличию черно-белого и следующего бело-черного переходов в строке). От момента начала считывания fe- -1-ой строки изображения и до момента начала считывания й4-2-ой строки в регистрах группы R хранится информация о сегментах й-ой строки.

Имеются далее схема анализа содержимого регистров , R и совокупность счетчиков

(аи, aj2,...., OIT; Oai, 022,... aigr) сигналов hrs формируемых указанной схемой (блок 4). Схема анализа содержимого регистров сравнивает состояние регистра R i с состоянием регистров 1, , ... Rmk) , состояние регистра

п2п2 п2п2

Ki - с состоянием регистров Кь Afs, .. i (k+i) и т. д. таким образом, что на ее rXs выходе формируется сигнал Лг , если хотя бы две одноименные ячейки регистров Rr-, Rs . находятся в состоянии «1 (согласно сказанному выше, наличие сигнала hrs свидетельствует о том, что сегменты f г и FS перекрываются). Сигнал увеличивает содержимое счетчиков Cjr и ais на единицу.

Затем в зависимости от состояния того или иного счетчика запускаются блок формирования признаков замкнутости-разомкнутости 5, блок формирования признаков различения 6. Сигналы, формируемые на их выходе, поступают в регистры ПЗР - регистры хранения признаков замкнутости-разомкнутости 7 либо в регистры ПР - регистры хранения признаков различения 8.. ..

Рассмотрим порядок работы указанных блоков (см. блок-схему фиг. И).

Блок формирования признаков замкнутостиразомкнутости 5 запускается в зависимости от состояния счетчиков ац,... йш(), , ,. , й2л-(й+1)-1 в блоке 3. Рассмотрим все возможные случаи;

1)Если содержимое счетчика ац (обозначим его аи) таково, что

,

включается блок формирования ПЗР 5, который вырабатывает сигнал, указывающий на наличие разомкнутости контура слева (обозначим этот сигнал щр), запоминаемый в одном из регистров ПЗР, и одновременно записывает в этот регистр содержимое регистра и счетчика строк (число k) (предполагается, что содержимое данного регистра записывается в первые L ячеек регистра ПЗР).

Затем содержимое счетчика аи уменьшается на «1, и вновь проверяется заданное условие. При его выполнении происходит описанный рабочий цикл с той лишь разницей, что в регистр ПЗР переписывается содержимое реО

гистра Кз и т. д. до тех пор, пока не будет нарушено указанное выше условие.

2)Если содержимое счетчика abv(fe) таково, что

Й1Л(/{)1

25

включается блок формирования ПЗР 5, работающий, как описано выше, за исключением того, что в регистр ПЗР 7 записываются сигнал, свидетельствующий о разомкнутости контура справа (обозначим его ((Т) ), и содержимое регистра (h+i)i, затем регистра (h+i)2, и т. д. до тех пор, пока не будет нарушено заданное условие. 3) Предположим, наконец, что содержимое

счетчика а2р 1аково, что

.

В этом случае также включается блок формирования ПЗР 5, который формирует сигнал, указывающий на наличие замкнутости контура (обозначим его (Q). Этот сигнал, содер 2

жимое регистра Кр и счетчика строк записываются в регистр ПЗР 7.

Блок формирования признаков различения 6 включается в зависимости от состояния счетчиксв а2ь а2л-№+1). Л)2, ais,..., aiN(k)-i в блоке 3. Рассмотрим возможные случаи: 1) Если

50

.

блок формирования ПР 6 вырабатывает сигнал ю(р), который поступает в регистр ПР 8, и сигналы опроса первых L ячеек каждого регистра ПЗР 7 и регистра Ri , причем в случае обнаружения хотя бы двух одноименных ячеек в соответствующих регистрах, находящихся в состоянии «1, информация, хранимая в ячейках , L+2,..., данного регистра ПЗР

(т. е. информации о ПЗР и номере строки, при анализе которой был получен ПЗР), перезаписывается в регистр ПР 8, после чего регистр ПЗР очищается. Таким образом, в регистр ПР 8 оказывается записанной информация

следующего вида: сигналь: о наличии пары

ПЗР, например, «(Q), о{р) и два числа, например V, f/2 (i.), указывающих номера строк изображения. Эта информация называется признаком различения.

После опроса всех регистров ПЗР рабочий цикл блока формирования ПР 6 заканчивается.

2)Если

(/1+1) 1.

включается блок формирования ПР 6, причем в этом случае в отличие от первого формируется сигнал со (Г), а сигналы опроса иостуиают на регистры ПЗР и регистр (h+i). В результате работы блока в одном из регистров ПР оказывается записанной информация вида (со (Я), со (Г), 1, t/2). где Нг {р, Г, Q}.

3)Пусть

0117 0,

где Не, {2,3, ...N(k} - 1}. В этом случае включается блок формирования ПР. Работа его аналогична описанной выше с той лишь разницей, что формируется сигнал co(Q), а сигналы опроса поступают на регистры ПЗР и регистр R uБлок слежения включается в зависимости от состояния счетчиков ааз, «23,. - , a2N(k+i)-i, причем для этого необходимо, чтобы содержимое проверяемого счетчика (обозначим его йзи) было отлично от «О. В этом случае генерируются сигналы оцроса первых L ячеек содержимого регистра ПЗР 7 и регистра . При обнаружении одноименных ячеек указанных регистров, находящихся в состоянии «1, в регистр соответствующего ПЗР занисывается содержимое регистра результате рассмотренного процесса в регистрах ПР 8 после считывания всех строк изображения получают совокупность признаков различения, характеризующих конфигурацию локальных частей распознаваемого изображения и относительное положение последних в кадре распознавания.

Аналогично изложенному происходит вторичиый анализ изображения объекта (анализируются вертикальные строки изображения слева направо) и выделяются признаки замкнутости-разомкнутости контура изображения и параметры признаков.

Для повышения помехоустойчивости способа опознавания предлагается:

1) нормировать параметры Ui, Uz признаков замкнутости-разомкнутости согласно выражениям

(i-Uo JJ ,

« СУ а - 1

,

где t/o и f/ () соответственно номера строк изображения, в пределах которых находится контур изображения распознаваемого объекта (строки, содержащие не менее двух сегментов).

2)исключить из полученного набора признаков различения признаки, величина f/2-Ui для которых меньше заданного значения б.

3)если набор содержит признаки различения

0)(ЯО, «(//.). П f/), «(з), «(4),

и,, и,), /у,, Н,, Я„ fi,p,T,Q}, выделенных в ис.ходном (первоначальном) направлеции аь ализа, и , f/i -f/3- либо Hz Ht, , то из рассматриваемого jiaбора исключить ПР ((a(Hi), со(Я2), f/i, U), ,-77з, и ПР м(Яз), со (Я/.), Us, и,, если U2-Ui U,-U3.

4)если полученный набор ПР содержит ПР со(Я), со(Я), 1/1, Щ, Яе{Л71д}, выделенных в исходном (первоначальном) направлении анализа, то из рассматриваемого набора исключить (М-2) ПР с минимальными значениями L/z-Ui.

5)исключить из полученного набора ПР oj(Q), cd(Q), f/i, Uz, выделенные при вторичном анализе изображения.

6)если полученный набор ПР содержит ПР o)(Q), (,)(Н), и,, iJz, HB{PJ}, выделенных при вторичном анализе изображения, то из рассматриваемого набора исключить {М-1) ПР с минимальными значениями

(U2-U,).

7)если полученный набор ПР содержит М ПР о)(Я), w(Q), С/ь Щ, , выделенных при вторичном анализе изображения, от из рассматриваемого набора исключить (JVI-2) ПР с минимальными значениями (Uz-Ui). В результате выполнения перечисленных

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

Предмет изобретения

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

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

Замкнутости контура

fue.fФиг. 2

Разомкнутостц контура Слеёа Р113омкн1/тость контура спра8а

Радомr нутость контура cnpaSa

11