Устройство для распознавания образов

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при вводе напечатанных или написанных знаков или фигур. В устройстве задат ча повышения надежности распознавания достигается за счет выделения из множества касательных к границам объектов признаков, связанных с дифференциальными характеристиками внешней границы объекта, а не с место- ,положением их в пространстве, для чего в устройство, содержагцее блоки стереоскопического формирования изображений , минимизации информации, идентификации, анализа контуров, хранения эталонов, сравнения и управления , введены блок синтеза линий, блок формирования признаков и новая совокупность связей. 1 з.п. ф-лы. 6 ил. I (Л кэ 4iai. Од 00 с

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

„„SU„,4244683 (ц 4 С 06 К 9/00

ВСЕГО11 ..- - Я t3 „ t3

БМЬЛ11 Н ЕКА

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

C:.

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ (21) 3810815/24-24 (22) 05.11.84 (46) 15.07.86. Бюл. У 26 (7l) Институт технической кибернетики АН БССР (72) Н,Н.Латышенок, Г.Г. Маньшин и Н.И.Мурашко (53) 681.391.19 (088.8) (56) Заявка Японии У 49-12173, кл. 97 (7)В, 1974.

Авторское свидетельство СССР

И 615504, кл. G 06 К 9/00, 1973. (54)УСТРОЙСТВО ДЛЯ РАСПОЗНАВАНИЯ

ОБРАЗОВ (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано при вводе напечатанных или написанных знаков или фигур. В устройстве зада-, ча повышения надежности распознавания достигается за счет выделения из множества касательных к границам объектов признаков, связанных с дифференциальными характеристиками внешней границы объекта, а не с местоположением их в пространстве, для чего в устройство, содержащее блоки стереоскопического формирования изоб.— ражений, минимизации информации, идентификации, анализа контуров, хранения эталонов, сравнения и управления, введены блок синтеза линий, блок формирования признаков и новая совокупность связей. 1 s.n. ф-лы. 6 ил.

12

Изобретение относится к автоматике и вычислительной технике, B част.ности к устройствам- для распознаваЪ ния образов, и может быть использовано при вводе изображений в ЭВМ, Целью изобретения является повышение достоверности распознавания.

На фиг.1 показана блок-схема устройства распознавания образов; на фиг.2 — схема блока анализа контуров; на фиг.3 — схема блока формирования признаков; на фиг.4 схема блока выделения: на фиг.5 схема блока стереоскопического формирования изображений; на фиг.6 показана схема блока управления.

Устройство для распознавания образов (фиг ° 1) содержит блок 1 стереоскопического формирования изображений, блок 2 преобразования, блок

3 идентификации стереопар, блок 4 управления„ блок 5 выделения линий, блок 6 формирования признаков, блок

7 анализа контуров, блок 8 хранения эталонов и блок 9 принятия решений.

Блок 1 стереоскопического формирования изображений, вход которого является входам устройства, соединен с блоком 2 преобразования, блоком 7 анализа контуров и блоком 4 управления, который подключен к блоку 2 преобразования, блоку 3 идентификации стереопар, блоку 6 формирования признаков, блоку 5 выделения линий,.блоку 7 анализа контуров и блоку 9 принятия решения, который, в свою очередь, связан с выходом устройства, блоком 8 хранения эталонов, блоком 7 анализа контуров, блоком 6 формирования признаков и блоком 5 выделения линий, подключенным к блоку 2 преобразования и блоку 3 идентификации стереопар, который соединен с блоком 7 анализа контуров и блоком 6 формирования признаков °

Блок 7 анализа контуров (фиг.2) предназначен для формирования призна— кав кривизны контура изображения распознаваемых объектов и содержит триггер 10, первый элемент И 11, первый счетчик 12, схему 13 сравнения, второй элемент И 14, второй счетчик 15, дешифратор 16, причем выход третьего счетчика !7 подключен к второму входу блока 9 принятия решений, второй ч первый входы триггера 10 и вторые входы первого элемента И 11 и схемы 13 сравнения свя44683 2 заны с четвертым входом блока 4 управления, а первый вход третьего счетчика 17 соединен с выходом дешифратора 16„ вход которого подключен к выходу второго счетчика 15, вход которого, .в свою очередь, соединен с выходом:второго элемента И 14, второй вход которого подключен к выходу блока 3 идентификации, стереопар, а

llG первый — к выходу схемы 13 сравнения, первый вход которой связан с первым выходам первого счетчика 12 и третьим входом блока 1 стереоскопического формирования изображений, второй !

5 выход — с входом блока 4 управления, а вход — с выходом первого элемента

И 11, первый вход которого подключен к второму выходу триггера 10, первый выход которого связан с входом бло20 ка 4 управления, а второй вход — с вторым выходом блока 1 стереоскапичес.кога формирования изображений.

Блок 6 формирования признаков (фиг,3) предназначен для выделения

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

3g первыи выход — с входом формирователя 19 и первым входом первого счетчика 20, схему совпадений 21, Второй выход триггера 18 подключен к первому входу второго счетчика 22.

Блок 6 содержит также сумматор 23 и дешифратор 24. Выходы формирователя 19, схемы совпадения 21, сумматора 23 и дешифратора 24 соединены с третьим вхэдом блока 9 принятия решений, а вход схемы 21 совпадения подключен к выходу первого счетчика

20 и первому входу сумматора 23, втсрай вход которого и вторые входы триггера 18, первого 20 и второго 22 счетчиков связаны с третьим выходом блока 4 управления.

Блок 5 выделения линий 1фиг.4) предназначен для определения длины прямолинейных участков границы объекта и содержит регистр 25, первый вход которого подключен к выходу блока 2 преобразования, а выход к первому .входу селектора-мультиплексора 26, выход которого подключен к первому входу триггера 27„ первый выход которого, в свою очередь, подключен к входу формирователя 28 и первому входу элемента И 29, вто1244683 4 рой выход триггера 27 соединен с первым входом элемента И 30, а вторые входы регистра 25, селекторамультиплексора 26, триггера 27, первого 29 и второго 30 элементов И

5 связаны с вторым выходом блока 4 управления, а выходы формирователя

28, первого 31 и второго 32 счетчиков связаны с четвертым входом блока

9 принятия решений, при этом входы 10 первого 31 и второго 32 счетчиков подключены соответственно с выходом первого 29 и второго 30 элементов И.

Блок 1 стереоскопического форми- 15 рования изображений 1фиг.5) предназначен для формирования трехмерного пространСтва, в каждой секущей плоскости которого исходное изображение объекта распознаваемого образца 20 относительно предыдущей повернуто на угол d.и содержит блок 33 памяти, первый вход которого подключен к входу устройства, второй вход — к выходу коммутатора 34, а выход — к 25 третьему входу блока 7 анализа контуров и первым входам запоминающих устройств 35, выходы которых подключены к первому входу блока 2 преобразования, вторые входы запоминающих устройств 35.1...,,35. h соединены с соответствующими выходами коммутаторов 36.1,...,36.ь, первые входы которых подключены к выходам сооотвеуствующих постоянных запоминающих устройств (ПЗУ) 37.1,...

37.р входы которых,.а также первый вход коммутатора 34, вторые входы коммутаторов 36.1,...,36. и третьи входы запоминающих устройств

35.1,...,35.п связаны с первым выходом блока 4 управления, кроме того, второй вход коммутатора 34 подключен к третьему выходу блока 7 анализа контуров. 45

Блок 4 управления (фиг.6) предназначен для согласования работы блоков устройства и содержит генератор 38, выход которого подключен к первым входам первого элемента И 39, элемент И 40, выход первого элемента И 39 подключен к первому входу элемента ИЛИ 41, второй вход которого соединен с выходом второго элемента И 40, а выход элемента ИЛИ 41 к последовательно соединенным счетчикам 42 и 43, элемент 2 И-ИЛИ 44, счетчик 45, дешифратор 46, первый выход счетчика 43 связан с первыми входами триггера 47 и вторым входом элемента 2 И-ИЛИ 44, выход которого подключен к входу счетчика 45, выход которого связан с первыми входами триггера 48, второго элемента И 40, и дешифратора 46, второй вход последнего подключен к второму входу триггера 48 и выходу триггера 47, второй вход которого, а также третий вход триггера 48 и пятый вход блока 9 принятия решений подключены к выходу формирователя 49, вход которого и второй" вход элемента И 40 соединены с вторым выходом блока 7 анализа контуров, первый выход триггера 48 подключен к второму входу элемента

И 39 и третьему входу элемента 2

И-ИЛИ 44, второй выход триггера 48 подключен к третьему входу элемента

И 40 и четвертому входу элемента

2И-ИЛИ 44, кроме того, выход элемента ИЛИ 41 и счетчика 42 подключены к вторым входам блока 2 преобразования и блока 5 выделения линий, выходы элемента ИЛИ 41 и счетчиков 42 и 43 соединены с вторым входом блока.7 анализа контуров, выход счетчика 45 и третий выход элемента ИЛИ 41 связаны с вторым входом блока 6 формирования признаков, выходы счетчиков

42 и 43 и первый выход дешифратора 46 подключены к вторым входам блока 3 идентификации стереопар, выходы счетчиков 42 и 43, выход триггера 47 и второй выход дешифратора 46 подключены к второму входу блока 1 стереоскопического формирования иэображений.

Блок 2 преобразования предназначен для выделения точек логической импликации между соседними строками изображений и содержит первый и второй последовательно соединенные и третий m-ðàýðÿäíûé регистры сдвига и логическую схему, причем информационный вход первого регистра подключен к первому выходу блока

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

1244663

15

35

45

В устройстве осуществляется распознавание образов в блоке 9 принятия решений сравнением эталонных признаков Ч, поступающих с блока 8 .хранения эталонов, и выделенных трех групп признаков V, V поступающих соответственно с выхода блока 5 выделения линий, блока 7 анализа контуров и блока 6 формирования признаков, пфичем признаки связаны с векторными характеристикаБлок 9 принятия решений предназначен для сопоставления признаков распознаваемого объекта с эталонным и содержит: регистр, триггер, элемент И, схему сравнения, причем первые входы схемы И и схемы сравнения соединены с выходом блока 8 хранения эталонов, второй вход - с выходом триггера, первый вход которого соединен с пятым вьгкодом блока 4 управления, третий вход схемы сравнения подключен-к выходу регистра, входы которого подключены соответственно к выходу блока 5 выделе ния линий и к первому выходу блока 7 анализа контуров, а выход схемы сравнения подключен к второму входу регистра и элемента И, выход которого подключен к выходу устройства.

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

Блок 3 идентификации предназначен для восстановления пространственных координат ; изображений и содержит ПЗУ, ь коммутаторов и и запоминающих устройств (ЗУ), причем информационные входы ЗУ подключены к вь1ходy блока 2 преобразования, выход их — к первым входам блока 6 формирования признаков и блока 7 анализа контуров а адресные входы соответствующих ЗУ через коммутаторы подключены к выходам ПЗУ, входы которых и вторые входы коммутаторов блока соединены с вторым входом блока 4 управления.

Устройство работает следующим образом. ми прямолинейных участков границ распознаваемого образа, Ч вЂ” с кривизной его границ, U — с векторными характеристиками нормалей точек перегиба и углов его границ. Признаки V, „...,V, формируются из анализа множества {„) касательных к границам распознаваемого-объекта, для чего первоначально в блоке 1 стереоскопического формирования изображения из матричной памяти, куда заносится изображение распознаваемого объекта, формируется трехмерное пространство, образованное из » плоскостей,в каждой плоскости которого изображение повернуто относительно предыдущего на угол

360 — Далее в блоке 2 преобразои вания в каждой из . плоскостей выI деляются координаты точек границ изображения, соприкасающиеся с горизонтальными секущими в ней, исходя из логической импликации элементов соседних строк изображения. Затем блок 3 преобразования осуществляет совмещение пространственных координат точек соприкосновения, образуя описание исходного объекта в дискретном множестве (j касательных к точкам границ изображения.

Образование трехмерного пространства распознаваемого образа производится в блоке 1 стереоскопического формирования изображения, где пространственные координаты исходного объекта, занесенные в блок 3 памяти, преобразуются в соответствующие координаты, плоскостей в ь; постоянном запоминающем устройстве 37, При последовательном опросе через коммутатор 34 блока 33 памяти счетчиками 42 и 43 координат Х, Y блока

4 управления опрашиваются также ПЗУ

37, с выхода которых преобразованные координаты через коммутаторы 36 поступают на адресные входы запоминаю" щих устройств 35, на информационные входы которых в этот момент поступают данные с выхода блока 33 памяти, а на стробирующие входы — сигнал разрешение записи с выхода дешифратора 46 блока 4 управления, По заполнению запоминающих устройств 35 на выходе счетчика 43 координат q в блоке 4 управления доявляется сигнал переполнения, 1244683 устанавливающий триггер 47 в единичное состояние, с ега выхода управляющий сигнал с дешифратора 46 снимает сигнал общего разрешения записи информации. В этом случае дешифратор 46 блока 4 управления разрешает поочередное считывание данных с ЗУ 35, поступающих на вход последовательно соединенных первого и второго регистров блока 2 преобразования. Разрядность этих регистров равна числу элементов в строке иэображения.

Выход первых К разрядов первого регистра, соответствующих текущему значению строки, поступает на первый вход логической схемы, реализующей функцию логической импликации, на второй вход которой поступает информация с первых K разрядов второго регистра, соответствующих предыдущему значению строки.

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

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

Кроме того, с выхода третьего регистра блока 2 преобразования данные после завершения считывания строки, заносятся в регистр 25 блока 5 выделения линий сигналам переполнения счетчика 42 блока 4 управления.

Данные с регистра 25, содержащие точки пересечения границы изображения с касательной ;, начинают поочередно опрашиваться через селектор-мультиплексор 26 счетчиком 42 блока 4 управления. С выхода селектора-муль10

55 типлексора 26 данные поступают на

7)-вход триггера 27 и стробируются.

В зависимости от наличия информации триггер 27 находится в состоянии "1" или "0" и через элементы

29,30 соответственно разрешает ввод счетчика 31, определяющего количества точек изображения на касательной q., или счетчика 32, определяющего количество точек касательной до появления изображения. В конце изображения на данной касательной триггер 27 переходит иэ состояния "1" в "0", по которому формирователь 28 образует синхраимпульс, поступающий в блок 9 принятия решений, производящий .считывание длины прямолинейного отрезка границы изображения со счетчика 31 и его местоположения со счетчика 32. По завершении заполнения ь запоминающих устройств блока 3 идентификации сигнал переполнения счетчика 45 блока 4 управления взводит триггер 48, который через элемент 2 И-ИЛИ 44, элемент

И 40 и элемент ИЛИ 41 перекоммутирует последовательность взвода счетчиков45 и 42,43 ° В данном случае первоначально взводится счетчик 45 опроса номера запоминающих устройств блока 3 идентификации, и затем по его переполнению счетчики 42 и 43 координат. Таким образом, блок 4 управле-. ния организует последовательный опрос запоминающих устройств блока 3 идентификации стереопар, выделяя количество касательных и их наклон в данной точке границы иэображения распознаваемого образа. Считанные дан ные с выхода блока 3 поступают на вход блока 6 формирования признаков и блока 7 анализа контуров, !

В блоке 6 формирования признаков входные данные поступают на Э -вход триггера 18, где они стробируются синхроимпульсом и при наличии информации триггер 18 устанавливается в состояние "1". В зависимости от состояния триггера 18 разрешается счет синхроимпульсов счетчиком 20 или счетчиком 22. Таким образом, на счетчи= ке 22 устанавливается количество касательных из множества ) в данной, локальной точке границы иэображения, а в счетчике 20 — их отсутствие.

При взводе триггера 18 с формирователя 19 снимается стробирующий им!

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

6 нормалей которых составляет 180 что соответствует наличию точки перегиба (признак Ч . Наличие неЗ,1 скольких касательных из л и их ко- 10 личество в счетчике 22 формирует признак 1/„ наличия в локальной точке границы изображения распознаваемого знака угла р, образованного двумя прямыми и равного 15

P -.:(-к)„ где K — показания счетчика 22.

Значение yrzfa p формируется в 20 признак Y из показания счетчика 22

3,2 на дешифраторе 24",а сумматор 23, определяющий разницу показаний счетчика 45 блока 4 управления и счет чика 20, характеризует угол наклона. вектора нормали к точке перегиба признака,.

В блоке 7 анализа контуров произ= водится определение кривизны локальных участков (признак V,) по количест- 30 ву f касательных из ) на его границах, (k=(I-1) С), где С вЂ” константа) для чего через элемент И 11 блока 7 анализа контуров сигнал переполнения счетчика 43 блока 4 управ- З5 ления взводит счетчик опроса блока памяти 33, При наличии информации с выхода блока 33 памяти вэводится триггер 10, прерывающий работу счетчика 12, и счетчик 15 начинает осу- 40 ществлять подсчет числа касательных на локальном участке изображения, определяемого при сравнении схемой

13 сравнения координат опроса ЗУ блока 3 и счетчика 12. 45

Дешифрованные признаки 7 с дешифратора 16 поступают на счетчик

17, где они накапливаются. По завершению опроса ЗУ блока 3 идентификации сигнал переполнения счетчика 43

50 сбрасывает триггер 10, и процесс продолжается аналогично до переполнения счетчика 12, переполнение которого сбрасывает триггеры 47 и 48 блока 4 управления через формирователь 49 короткого импульса и заносит в блок

9 принятия решений признак Ч . Од- новременно по этому импульсу завершается занесение признаков 111 ° 7, изображения, взводится триггер блока 9 принятия решений, который разрешает схеме сравнения сравнивать полученные признаки с эталонными, поступающими с блока 8 хранения эталонов °

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

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

I,Óñòðîéñòâî для распознавания образов, содержащее блок стереоскопического формирования изображений, первый вход которого является входом устройства, второй вход подключен к первому выходу блока управления, первый выход — к первому входу блоI ка преобразования, выход которого соединен с первым входом блока идентификации стереопар, второй вход которого подключен к второму выходу блока управления, блок принятия решений, первый вход которого соединен с выходом блока хранения эталонов, второй вход — с первым выходом бло— ка анализа контуров, а выход являет— ся выхоцом устройства, о т л и ч- а ющ е е с я тем, что, с целью повышения достоверности распознавания, оно содержит блок выделения линий и блок формирования признаков, выход которого подключен к третьему входу блока принятия решений, первые входы блока формирования признаков и блока анализа контуров соединены с выходом блока идентификации стереопар, второй вход блока формирования признаков подключен к третьему выходу блока управления, четвертый выход и вход которого соединены соответст-. венно с вторым входом и вторым выходом блока анализа контуров, тре тий вход и третий выход которого подключены соответственно к второму выходу и третьему входу блока стереоскопического формирования изображений, первый вход блока выделения линий соединен с выходом блока преобразования, а выход — с четвертым входом блока принятия решений, пятый вход которого подключен к пято1244683

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

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

О с выходом второго счетчика, вход которого подключен к выходу второго элемента И, первый вход которого является первым входом блока, а второй вход соединен с выходом схемы !

5 сравнения, причем прямой выход триггера подключен к другому входу первого элемента И, выход которого соединен с входом первого счетчика.

1244683

1244683

Составитель Т,Ничипорович

Редактор М,Циткина Техред Л.Олейник Корректор В,Бутяга

Заказ 3920/53 Тираж 671

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д,4/5

Подписное

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