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

113

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

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

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

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

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

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

шение числа R. единичных компонентов изображения, лежащих на этой инии, к общему числу компонентов, лежащих на линии, равному горизонтальному размеру т растра, при этом линии полагаются вытянутыми в-общем горизонтальном направлении. Под зачерненно- стью изображения понимается отношени числа Е. единичных компонентов изображения к общему числу ячеек растра, равному п m , X т, где т - размер растра по вертикали. Линейный информативный признак определяется следующим образом: c(L,X) +1, если выполняется условие

Кл Rj

/

m

m ч m/

(1)

М 1 и Cf(L,X) -1, если условие (1) не

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

Условие (1) или эквивалентное ему условие m J-R R| определяет контраст между линией и остальным изображением. Можно усилить контрастность, взяв в левой части неравенства вместо множителя m j другой множитель

5

п

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

2 -R,, R 2 m,V 2

w

(2)

т.е.

5

0

причем

login,jC, где символ ... означает ближайшее большее целое.

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

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

Устройство работает в одном из

5 двух режимов - обучении или распознавании.

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

0 которому формируется случайное число или параметр L. Далее подаются импульс Обуч., по которому параметр из генаратора 2 случайных чисел проходит через мультиплексор 3 и посту5 пает на входы регистра 4 начальной ординаты, регистра 5 знаков приращений ординаты и регистра 6 приращений ординаты, и импульс Пр.Рг, разрешающий прием информации в регистры 4-6, при этом отдельные части параметра L, перезаписанные из генератора 2 случайных чисед в регистры 4-6, интерпретируются как элементы, определяющие положение некоторой случайной кривой. В частности, часть параметра L, записанная в регистр 4, представляет код начальной ординаты кривой. Число разрядов регистра 4 определяется вертикальным размером m 5

0

5

растра и равно , где символ ... означает ближайшее большее целое. В частности, если размер растра по вертикали т 31, то число разрядов регистра 4 равно пяти. Часть параметра L, записанная в регистре 6, рассматривается как приращения ординаты кривой. Приращение ординаты могут быть нулевыми или единичными. Число разрядов регистра 6 равно горизонтальному размеру ту растра. Знаки приращений ординаты фиксируются в регистре 5. При этом полагается, что

кривая разбита на К участков одинако- 15 ложение.

Однов

вой дли ны

1 т, Г

JTI

на каждом участке

знаки приращений ординаты одинаковые поэтому число разрядов регистра 5 равно К.

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

Далее выполняется ряд одинаковых циклов определения информативных признаков cf(L,X) для одного и того же параметра и различных изображений X. Число циклов равно числу изображений обучающей выборки. Каждый цикл выполняется следующим образом. Сначала подаются импульс Уст. О на входы счетчика 7 и накапливающего сумматора 11, по которому эти узлы устанавливаются в исходное нулевое состояние, импульс Пр.Рг.И, по которому очередное изображение принимается и фиксируется регистром 1 фиксации изображения, и импульс Пр.Сч, по которому начальная ордината перезаписывается из регистра 4 в реверсивный счетчик 8.

Далее подается серия из тп импуль- 45 РОЙ соответствует текущей ординате. сов сдвига Сдв, где т, - размер Таким образом, при подаче импульсов

.Сдв и Сдв, на выходе элемента ИЛИ 16 последовательно появляются г;

компоненты изображения, расположенные

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

регистрах 4-6.

Импульс Сдв подается также на вход элемента 13 задержки и задержангранице растра. После окончания серии mj импульсов изображение занима- 55 ьй этим элементом на время переклюет исходное положение. При каждом импульсе сдвига компоненты очередного левого столбца изображения поступают на входы элементов И блока 15 элеменчения узлов 1, 6, 8, 9, 10, 15 и 16 поступает на вход разрешения приема накапливающего сумматора 11 и через ключ 14 на вход счетчика 7. Таким об

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

Одновременно с -,

(К-1)- -- импульсами Сдв, подаваемыми в регистры 1 и 6, в регистр 5 знаков приращений ординаты подается импульс Сдв , П.О которому информация в этом регистре сдвигается на разряд влево. После т импульсов Сдв, т.е. после К сдвигов в регистре 5, информация в нем занимает исходное положение. При каждом сдвиге в регистре 5 выталкиваемый разряд, т.е. знак приращений ординаты очередного участка, перезаписывается в триггеры режима реверсивного счетчика 8.

Таким образом, на каждом участке

„ im tг кривой линии длиной I -- приращения

ординаты, поступающие в реверсивный счетчик 8 из регистра 6, складываются или вычитаются в зависимости от знака, переданного из регистра 5, так

что в реверсивном счетчике 8 формиру- ется код текущей ординаты.

Дешифратор 9 расшифровывает содержимое реверсивного счетчика 8 и открывает элемент И блока 15 элементов И, связанньй со строкой, номер котокомпоненты изображения, расположенные

линии, положение которой определя- ется информацией, зафиксированной в

линии, положение которой определя- ется информацией, зафиксированной в

регистрах 4-6.

Импульс Сдв подается также на вход элемента 13 задержки и задержан ьй этим элементом на время переключения узлов 1, 6, 8, 9, 10, 15 и 16 поступает на вход разрешения приема накапливающего сумматора 11 и через ключ 14 на вход счетчика 7. Таким обIpasoM, в сумматоре 11 после m импульсов Сдв формируется число R,, равное количеству единичных компонентов всего изображения, а в счетчике 7 - число Кд, равное числу единичных

компонентов изображения, лежащих на отрабатываемой кривой.

Разрядность счетчика 7 определяется размером т, растра по горизонтали и равна Jlog. а разрядность сумматора 11 - всем размером растра т и равна m. В частности, при т, iflj 31 разрядность счетчика 7 равна пяти, а разрядность сумматора 11 равна десяти.

Вес старшего разряда сумматора в

; / . 2 раз больше веса старше-

го разряда счетчика 7.

С входами блока 12 сравнения на неравенство соединены разряды счетчика 7 и старшие разряды сумматора 11. Таким образом, блоком 12. сравнения фактически проверяется соотношение между величиной 2 R К. Блок 12 сравнения выдает 1, если выполнено условие (2)

2 л и и О в противном случае.

После окончания серии из т импульсов Сдв определение информативного признака -((L,X) завершено. Этот признак LP(L,X) +1, если блок 12 сравнения на неравенство вьщает на своем выходе 1, и J( L, K) -1, если на выходе блока 12 сравнения имеется О.

I ;.

Итак, значение признака 4(L,X) хранится на выходе блока 12 сравнения, а параметр L - в регистрах 4-6.

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

. Далее выполняется ряд одинаковых циклов формирования информативных признаков g (L,X) для одного и того же изображения X и различных параметров L. Каждый цикл выполняется следующим образом. Вначале подается импульс Расп, по которому параметр L проходит -через мультиплексор 3 и поступает на входы регистров 4-6, и импульс Пр.Рг, разрешающий прием информации в регистры 4-6. Далее подается импульс Уст.О на входы счетчика 7 и накапливающего сумматора 11, по кото

ю15

1592

рому эти узлы устанавливаются в нулевое состояние, и импульс Пр.Сч, по которому начальная ордината перезаписывается из регистра 4 начальной ординаты в реверсивный счетчик 8. Далее подается серия т импульсов Сдв на входы регистра 1 фиксации изображений, регистра 6 приращений ординаты и элемента 13 задержки. Одновременно

-Ifl- 1 «- -ЦЧ

импульсами Сдв подается импульс Сдв на вход регистра 5 знаков приращений ординаты. После окончания серии импульсов Сдв на выходе блока 12 сравнения на неравенство формируется значение признака tf(L,X) 4-1, если на выходе блока 12 сравнения имеется 1, и -1, если на выходе блока 12 сравнения имеется О.

Преобразователь 10 унитарного кода в двоичньм для частного случая, когда число входов М 31, представляет пирамидальную многослойную сетку одноразрядных комбинационных двоичных сумматоров 17. Число сумматоров в первом слое S, определяется числом входов М и равно S, 0,5(М- 1). Число сумматоров во втором слое S 0,5(S, - 1). Аналогично число сумматоров в каждом Последующем слое S,j определяется числом сумматоров в предыдущем слое S ; и равно Sj 0,5(5 f - 1). В последнем слое имеется один сумматор. Если по расчету S не целое, то рассчитанное число S следует увеличить до ближайшего большего целого.

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

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

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

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

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

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

регистров и я:вляется вторым управляю- 1ЩМ входом устройства, вход установки накапливающего сумматора соединен с входом установки счетчика и является входом установки устройства, вход записи регистра фиксации изображений является входом записи устройства, вход записи реверсивного счетчика является третьим управляющ 1М входом с группой входов реверсивного счетчи- 40 Устройства, вход сдвига регистра фик- ка-, выход первого параллельно-после- сации изображений подключен к входу довательного кольцевого подключен к входу направления счета реверсивного счетчика, выход второго

ходов которого подключена к группе входов регистра начальной ординаты, вторая группа выходов - к группе входов первого параллельно-последовательного кольцевого регистра, третья группа выходов - к группе входов второго параллельно-последовательного кольцевого регистра, группа выходов регистра начальной ординаты соединена

35

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

последовательного кольцевого регистра является пятым управляющим входом устройства.

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

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

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

40

35

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

последовательного кольцевого регистра является пятым управляющим входом устройства.

Изобретение относится к области технической кибернетики и вычислительной техники и может применяться в распознающих и классифицирующих системах роботов. Целью изобретения .является увеличение вероятности правильного распознавания. Устройство содержит регистр фиксации изображений, генератор случайных чисел, мультиплексор, регистр начальной ординаты, параллельно-последовательный кольцевой регистр приращений ординаты, счетчик, реверсивный счетчик, дешифратор, преобразователь унитарного кода в двоичный, накапливающий сумматор, блок сравнения на неравенство, элемент задержки, ключ, блок элементов И, элемент ИЛИ, параллельно-последовательный кольцевой регистр знаков приращений ординаты. Устройство позволяет формировать при обучении и распознавании линейные информативные признаки, т.е. признаки, значения которых зависят от совокупности компонентов изображения, расположенных на случайно выбираемой, кривой линии. Повышение вероятности правильного распознавания связано с тем, что структура линейных признаков соответствует структуре изображений с криволинейными фрагментами. 2 ил. с S (Л оо ел со ГчЭ