Устройство для формирования информативных признаков при распознавании изображений Советский патент 1987 года по МПК G06K9/36 

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

Устройство для формирования информативных признаков во многом определяет важнейшие параметры и характеристики распознающих устройств.

Целью изобретения является увеличение вероятности правильного распоз навания.

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

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

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

1 единичных компонентов всего изображения к общему числу ячеек рас- т,, где га, - размер

.1

2

тра, равному m

растра по горизонтали,

растра по вертикали.

m 2

размер

Полосовой информативный признак lf|.(L,X) определяется следующим образом: l/n(L,X) - +1, если выполняется условие

-- т -SJ}-г 1

RO tn,m/

где gi.(L,X) -1, если условие (1)

п не выполняется.

Условие (1) или условие ,

эквивалентное ему

Ш . га

Rn RoR

И

определяет контраст между полосой

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

i определяется неравенствами 2 m, х X т., 2

, откуда i ., где символ 1 ... t означает ближайшее большее целое.. Тогда получается следующее вьфажение

2 -К,

п

(2)

5

0

5

0

Параметр L применительно к полосовым информативным признакам определяет положения граничных кривых полосы.

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

Устройство содержит регистр 1 фиксации изображения, генератор 2 случайных чисел, мультиплексор 3, регистр 4 первой начальной ординаты, параллельно-последовательный кольцевой регистр 5 знаков приращений rtep- вой ординаты, параллельно-последовательный кольцевой регистр 6 прираще- НИИ .первой ординаты, первьш реверсивный счетчик 7, первый дешифратор 8, первый блок 9 элементов ИЛИ, регистр 10 второй начальной ординаты, парал5 лельно-последовательный кольцевой регистр 11 знаков приращений второй ординаты, параллельно-последовательный кольцевой регистр 12 приращений . второй ординаты, второй реверсивньм

0 счетчик 13, второй дешифратор 14,

второй блок 15 элементов ИЛИ, блок 16 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, блок 17 элементов И, первый-преобразователь 18 унитарного кода в двоичный, первый

5 накапливающий сумматор 19, второй преобразователь 20 унитарного кода в двоичный, второй накапливающий сумматор 21, (Третий преобразователь 22 унитарного кода в двоичный, третий

0 накапливающий сумматор 23, элемент 24 задержки, блок 25 умножения и блок 26 сравнения на неравенство.

. . Устройство работает в одном из 55 двух режимов - обучение или распозна-; вание.

В режиме обучения вначале на вход генератора 2 случайных чисел подается импульс Ф , по которому в генераторе

1

2 формируется случайное число или параметр L.

Далее подаются импульс ()буч., по которому параметр проходит через мультиплексор 3 и поступает иа входы регистров 4 и 10 начальных ординат, регистров 5 и 11 знаков приращений ординат и регистров 6 и 12 приращений ординат, и импульс Пр.Рг., разре- шающий прием информации в регистры 4-6 и 10-12. При этом отдельные части параметра L, перезаписанные из генератора 2 случайных чисел в регистры 4-6 и 10-12, интерпретируются как элементы, определяющие положения двух случайн ых кривых - границ полосы . В частности, части параметра L, записанные в регистры 4 и 10, представляют коды начальных ординат граничных кривых. Число разрядов в регистрах 4 и 10 определяется вертикальным размером mj растра и равно , где символ J...t означает ближайшее большее целое. Например, если размер растра по вертикали т 31, то число разрядов в регистрах 4 и 10 равно пяти. Части параметра L, записанные в регистры 6 и 12, рассматриваются как модули приращений ординат граничных кривых. Модули приращений ординат могут быть нулевыми или единичными . Число разрядов в регистрах 6 и 12 равно горизонтальному размеру т растра. Знаки приращений ординат граничных кривых записываются в регистры 5 и 11. При этом полагается, что каждая граничная кривая разбита на К

участков одинаковой длины

.

m 1

леднии участок, если -- не целое, MO- IS.

жет быть меньше остальные. На каждом участке знаки приращений ординат гра- яичных кривых одинаковые. Очевидно, .число разрядов регистров 5 и 11 равно К.

Таким образом, параметр L, вырабатываемый генератором 2 случайных чи- сел, состоит из ,m, m + K разрядов. В частности, при т., т 31 и К 4 число разрядов параметра L равно 80.

. После подачи импульсов Обуч. и Пр.Рг. вьшолняется ряд одинаковых циклов определения информативных признаков if(L,X) для одного и того же параметра L и различных изображений

361

„ IQ is 202530

40

45 Qg

591

X обучающей выборки. Число циклов равно числу изображений обучающей выборки.

Каждый цикл выполняется следующим образом. Вначале на входы накапливающих сумматоров 19, 21 и 23 подается импульс Уст.О, по которому эти узлы устанавливаются в исходное нулевое состояние. Одновременно с импульсом Уст.О на вход регистра 1 фиксатдии изображения подается импульс Пр.Рг. И, по которому очередное изображение принимается и фиксируется в регистре 1 фиксации изображений. Также одновременно с импульсом Уст.О на входы реверсивных счетчиков 7 и 13 подается импульс Пр.Сч., по которому начальные ординаты граничных кривых перезаписываются из регистра 4 в счетчик 7 и из регистра 10 в счетчик 13.

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

Каждый импульс Сдв. поступает также на сдвиговые входы регистра 6 приращений первой ординаты и регистра 12 приращений второй ординаты. Информация в регистрах 6 и 12 сдвигается влево и выталкиваемые разряды из регистра 6 поступают на счетный вход первого реверсивного счетчика 7, а разряды, выталкиваемые из регистра 12, поступают на счетный вход второго реверсивного счетчика 13. Так как регистры 6 и 12 кольцевые, то после т, импульсов сдвига информация в них занимает исходное положение.

Одновременно с первым импульсом

| II1 1 Г

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

сдвигается на разряд влево. После сы

эл 1 ИСК

импульсов Сдв., т.е. после К

, так как на одном из входов этих элементов имеется О, а на другом 1. На входах остальных элементов ИСКЛЮЧАЮЩЕЕ ИЛИ блока 16 имеются либо

подсерии из гг импульсов Сдв. в

реверсивных счетчиках 7 и 13 реализуется либо режим Сложение, либо режим Вычитание, определяемый состоянием крайнего левого разряда регистров 5 и 11 соответственно, поскольку выходы регистров 5 и 11 подключены к входам управления режимами счетчиков 7 и 13. ,

Таким образом, на каждом участке граничных кривых линий длиной

тЛ

к

приращения ординат, поступающие

на выходах блока 17 совпадения и, значит, на входах третьего преобразователя 22 унитарного кода в двоичный

т.

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

на выходах их формирутся нули.

Таким образом, в каждьш момент времени на выходах блока 16 формируется унитарный код, у которого внут- 0 ренние разряды, соответствующие отрабатываемой полосе, равны единицы, а остальные - нулю. Таким образом, число единиц этого кода равно ширине полосы. Этот-унитарный код поступает J5 на входы первого преобразователя 18 унитарного кода в двоичный. Одновременно в каждый текущий момент времени на входах второго преобразователя 20 унитарного кода в двоичный имеется 20 унитарный код, соответствующий текув счетчики 7 и 13, прибавляются к со- щему столбцу изображения. Наконец, держимым этих счетчиков или вычитаются из содержимых. Следовательно, на каждом шаге в счетчике 7 формируется

код текущей ординаты первой граничной 25 образуется унитарный код, соответ- кривой, а в счетчике 13 - код текущей ствующий части текущего столбца йзоб- ординаты второй граничной кривой. В ражения, расположенной внутри полосы, то же время на каз1сдом шаге в левом . Импульс Сдв., задержанный эле- столбце регистра 1 оказывается разме- ментом 24 задержки на время переклю- щенным текущий столбец изображения. 30 чения узлов 1, 4-17, 18, 20 и 22, последовательно, по мере подачи импуль- ступает на входы приема информации

накапливающих сумматоров 19, 21, 23 и двоичные коды, образующиеся на выходах преобразователей 18, 20 и 22, вуют. номеру столбца изображения, пе- 35 поступают в соответствующие суммато- реместившемуся в крайний левьй стол- ры. Таким образом, по окончании пос- бец регистра 1 код ординаты первой тупления импульсов Сдв. в первом кривой содержится в первом реверсив- накапливающем сумматоре 19 формиру- ном счетчике 7, код ординаты второй ется число R, равное числу ячеек кривой содержится во втором реверсив- 40 растра, лежащих внутри полосы, во ном счетчике 13. Эти кривые являются втором накапливающем сумматоре 21 граничными-кривыми некоторой полосы. формируется число R, равное числу

Дешифраторы 8 и 14 расшифровывают единичных компонентов всего изобра- содержимое счетчиков 7 и 13, при этом жения, в третьем накапливающем сум- воэбуждаются те шины дешифраторов, 45 маторе 23 формируется число К, равное ЧИСЛУ единичных компонентов изображения внутри полосы.

В блоке 25 умножения, имеющем комбинационную структуру, фор1 шруется

подаваемое на

входы блока 26 сравнения на неравенство. На вторые входы блока 26 сравсов Сдв. и Сдв . в устройстве отрабатываются две кривые линии: текущие абсциссы этих кривых .соответстномера которых соответствуют текущим ординатам. При возбуждении определенной выходной шины дешифратора 8 возбуждёнными оказываются выход соответствующего элемента ИЛИ блока 9 и вы- 50 произведение R. R „,

ходы всех последующих элементов ИЛИ блока 9. Дешифратор 14 с блоком 15 элементов ИЛИ функционирует аналогично..

Единичные сигналы формируются на выходах тех элементов ИСКЛЮЧАНЩЕЕ 11ПИ блока 16, которые соответствуют ординатам, расположенным внутри полонения поступает число R, сдвинутое i разрядов, т.е. число 2 55 X R. Блок 26 проверяет условия (2):

влево на

пи вьщает

2 К 4 IT I I

R п R о п если условие (2) вьтолсы

, так как на одном из входов этих элементов имеется О, а на другом 1. На входах остальных элементов ИСКЛЮЧАЮЩЕЕ ИЛИ блока 16 имеются либо

два нуля, либо две единицы и, значит,

на выходах блока 17 совпадения и, значит, на входах третьего преобразователя 22 унитарного кода в двоичный

щему столбцу изображения. Наконец,

поступает число R, сдвинутое i разрядов, т.е. число 2 Блок 26 проверяет условия (2):

на

вьщает

2 К 4 IT I I

R п R о п если условие (2) вьтолнено, и О в противном случае. Единица на выходе блока 26 сравнения .рассматривается как факт Ц СЬД) +1 , а ноль - как cfCLiX) -1,

После окончания серии из т им- пульсов Сдв. значение признака tfCLjX) хранится на выходе блока 26 сравнения, а параметр L - на выходе регистров 4-6 и 10-12.

В режиме распознавания вначале по дается импульс Пр.Рг.И, по котором распознаваемое изображение X поступает в регистр 1 фиксации изображений и фиксируется в нем.

Далее выполняется ряд одинаковых циклов формирования информативных признаков t/(L,X), для одного и того же изображения X различных параметров L. Число циклов равно числу за фиксированных параметров L. Каждый цикл выполняется следующим образом. Вначале подаются импульсы Расп. и

Пр.Рг., по которым параметр L проходит через мультиплексор 3 и фикси- „

,,.,,,.„„ ос изображении, содержащее регистр фик- руется в регистрах 4-6 и 10-12. Далее - ,,-,r,tУстройство для формирования инфор мативных признаков при распознавании

сации изображений, блок элементов И, первый дешифратор, группа выходов регистра фиксации изображений соединена с первой группой входов блока элементов И, отличающееся тем, что, с целью увеличения вероятности правильного распознавания, в устройство введены генератор случайных чисел, мультиплексор, регистры первой и второй начальных ординат, четьгре параллельно-последовательных кольцевых, регистра, два реверсивных счетчика, второй дешифратор, два блока элементов ИЛИ, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, три преобразователя унитарного кода в двоичный, три накапливающих сумматора, элемент задержки, блок умножения, блок сравнения, при этом группа выходов генератора случайных чисел соединена с пер вой группой входов мультиплексора, первая группа выходов которого под- ключена к группе входов регистра первой начальной ординаты, вторая группа выходов к группе входов первого параллельно-последовательного кольцевого регистра, третья группа выходов - к группе входов второго параллельно-последовательного кольцевого регистра, четвертая группа выходов - к группе входов регистра второй начальной ординаты, пятая группа выходов - к группе входов третьего параллельно-последовательного кольцево

30

подается импульс Уст.О, по которому в накапливающих сумматорах 19, 21 и 23 устанавливаются исходные нулевые состояния, и импульс Пр.Сч., по которому начальные ординаты перезаписываются из регистра 4 в реверсивньш счетчик 7 и из регистра 10 в реверсивный счетчик 13.,Далее подается серия т импульсов Сдв. и соответственно импульсы Сдв., как и в ре- 35 жиме обучения. По окончании серии этих импульсов на выходе блока 26 сравнения на неравенство формируется 1, кодирующая факт Cf(L,X) +1, или О, кодирующий факт (L.X) -1,

40

Преобразователь унитарного кода в двоич|5ый, для частного случая, когда число входов М 31, представляет пирамидальную многослойную сетку одноразрядных комбинационных двоичных сумматоров 27. Число сумматоров в первом слое S определяется числом входов М и равно S 0.,5.(М - 1). ЧислсГ сумматоров во втором слое S 0,5(5 - 1). Аналогично число сумматоров в каясдом последующем слое S определяется числом сумматоров в пре- дьщущем слое S - и равно 0,5(8 .;, - 1).

имеется один сумматор. Если по расчету Sj не целое, то рассчитанное число S, следует увеличить до ближайшего большего целого.

1-1 - i

В последнем слое

В каждом слое одноразрядные комбинационные двоичные сумматоры 27 соединены так, что выход Сумма преды- дущего сумматора соединен с одним из входом последующего сумматора. Выходы Перенос сумматоров предыдущего слоя соединены с входами сумматоров последующего слоя. I

Унитарный код подается на входы сумматоров первого слоя. Разряды двоичного кода образуются на выходах Сумма последних (на фиг.2 верхних) сумматоров каждого слоя: разряд с весом 2° в первом слое, разряд с весом 2 во втором слое и т.д. Старший разряд формируется на выходе Перенос единственного сумматора последнего слоя.

Формула изобретения

„

Устройство для формирования информативных признаков при распознавании

изображении, содержащее регистр фик- ,,-,r,t

сации изображений, блок элементов И, первый дешифратор, группа выходов регистра фиксации изображений соединена с первой группой входов блока элементов И, отличающееся тем, что, с целью увеличения вероятности правильного распознавания, в устройство введены генератор случайных чисел, мультиплексор, регистры первой и второй начальных ординат, четьгре параллельно-последовательных кольцевых, регистра, два реверсивных счетчика, второй дешифратор, два блока элементов ИЛИ, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, три преобразователя унитарного кода в двоичный, три накапливающих сумматора, элемент задержки, блок умножения, блок сравнения, при этом группа выходов генератора случайных чисел соединена с первой группой входов мультиплексора, первая группа выходов которого под- ключена к группе входов регистра первой начальной ординаты, вторая группа выходов к группе входов первого параллельно-последовательного кольцевого регистра, третья группа выходов - к группе входов второго параллельно-последовательного кольцевого регистра, четвертая группа выходов - к группе входов регистра второй начальной ординаты, пятая группа выходов - к группе входов третьего параллельно-последовательного кольцево91

го регистра, шестая группа выходов - к группе входов четвертого параллельно-последовательного кольцевого регистра, группа вькодов регистра первой начальной ординаты соединена с группой входов первого реверсивного счетчика, группа выходов регистра второй начальной ординаты подключена к группе входов второго реверсивного счетчика, выход первого параллельно- последовательного кольцевого регистра соединен с входом направления счета первого реверсивного счетчика, выход третьего параллельно-последовательного кольцевого регистра подклю- чен к входу направления счета второго реверсивного счетчика, выход второго параллельно-последовательного кольцевого, счетчика соединен со счетным входом первого реверсивного счетчика, выход четвертого параллельно-последовательного кольцевого счетчика подключен к счетному входу второго реверсивного счетчика, группа выходов первого реверсивного счетчика соеди- нена с группой входов первого дешиф- ратора,группа выходов второго реверсивного счетчика подключена к группе входов второго дешифратора, группа входов первого блока элементов ИЛИ соединена с группой выходов первого дешифратора, группа входов второго блока элементов ИЛИ подключена к группе выходов второго дешифратора, вьгхо- ды блоков элементов ИЛИ соединены соответственно с первой и второй группами входов блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы которого соединены с группой входов первого преобразователя унитарного кода в двоичный и со второй группой входов блока элементов И, группа выходов регистра фиксации изображений подключена к группе входов второго преобразователя унитарного кода в двоичный, группа выходов блока элементов И соединена с группой входов третьего преобразователя унитарного кода в двоичньй, группы выходов первого, второго и третьего преобразователей унитарного кода в двоичный подключены соответ

5 0 5 О Q 5 Q

5

591. 10

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

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

Фи&Л

Фиг. 2

Изобретение относится к технической кибернетике и вычислительной технике. Устройство является частью распознающего устройства и мджет при- меняться в распознающих системах роботов. Целью изобретения является увеличение вероятности правильного распознавания изображений, основными фрагментами которых являются кривые полосы переменной ширины. Устройство содержит генератор случайных чисел, регистры, счетчики, депшфраторы, накапливающие сумматоры, преобразователи унитарного кода в двоичный, блок умножения, блок сравнения на неравенство, логические элементы. При этом выходы генератора случайных чисел через мультиплексор соединены с входами регистров начальных ординат, знаков приращений и приращений ординат, выходы этих регистров соединены с реверсивными счет.чиками, где формируются ординаты граничных кривых, выходы счетчиков связаны с входами дешифраторов, выходы дешифраторов, регистра фиксации изображений подключены через логические элементы и схемы ИСКЛЮЧАЮЩЕЕ ИЛИ к преобразователям унитарно- а го кода в двоичный, выходы которых связаны с входами накапливающих сумматоров, где формируются значения за- черненности полосы и изображения в целом, выходы накапливающих суммато- ров связаны с входами блока сравнения 5 на неравенство, состояние которого определяет значение полосового информативного признака. 2 ил. (О со 05 01 со

Редактор И.Николайчук

Заказ 6293/50Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Составитель В.Макаренков

Техред А.Кравчук Корректор О.Кравцова