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

.Вф ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ОПИСАНИ К АВТОРСКОМУ (21) 3810815/24-24(46) 15.07.86. Бюл. У 26 (71) Институт технической кибернетики АН БССР(57) Изобретение относится к областавтоматики и вычислительной техники и может быть использовано при,801244683 А 1 вводе напечатанныхили написанныхзнаков или фигур, В устройстве зада-, ча повышения надежности распознавания достигается за счет выделения иэ множества касательных к границам объектов признаков, связанных с дифференциальными характеристиками внешней границы объекта, а не с местоположением их в пространстве, для чего в устройство, содержащее блокистереоскопического формирования иэоб. - ражений, минимизации информации, идентификации, анализа контуров, хранения эталонов, сравнения и управления, введены блок синтеза линий,блок формирования признаков и новая совокупность связей, 1 э.п. ф-лы. 6 ил.112Изобретение относится к автоматике и вычислительной технике, в част.ности к устройствам для распознаваЪния образов, и может быть использовано при вводе изображений в ЭВМ.Целью изобретения является повышение достоверности распознавания.На фиг.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 идентификации, стереопар, а О первый - к выходу схемы 13 сравнения,первый вход которой связан с первымвыходам первого счетчика 12 и третьим входом блока 1 стереоскопического Формирования изображений, второй 5 выход - с входом блока 4 управления,а вход - с выходом первого элементаИ 11, первый вход которого подключенк второму выходу триггера 10, первыйвыход которого связан с входом бло ка 4 управления, а второй вход - свторым выходом блока 1 стереоскапичес.кога Формирования изображений,Блок 6 формирования признаков(Фиг,3) предназначен для выделения 25 особых точек дифференциальных характеристикконтура точек перегиба .иизлома и содержит триггер 18, первый вход которого соединен с выходомблока 3 идентификации стереопар, аЗ 0 первый выход - с входом формирователя 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 стереоскопического форми рования изображений 1 фиг.5) предназначен для формирования трехмерного пространСтва, в каждой секущей плоскости которого исходное изображение объекта распознаваемого образца 20 относительно предыдущей повернуто на угол Ы и содержит блок 33 памяти, первый вход которого подключен к входу устройства, второй вход - к выходу коммутатора 34, а выход - к 25 третьему входу блока 7 анализа контуров и первым входам запоминающих устройств 35, выходы которых подключены к первому входу блока 2 преобразования, вторые входы запоминающих устройств 35.135.соединены с соответствующими выходами коммутаторов 36.1. 36,ь, первые входы которых подключены к выходам сооотвеуствующих постоянных запоминающих устройств (ПЗУ) 37.1,37 входы которых,.а также первый вход коммутатора 34, вторые входы коммутаторов 36.136. и третьи входы запоминающих устройств 35,135,ь связаны с первым выходом блока 4 управления, кроме того, второй вход коммутатора 34 подключен к третьему выходу блока 7 анализа контуров. 45Блок 4 управления 1 фиг.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 преобразования предназначен для выделения точек логической импликации между соседними строками изображений и содержит первый и второй последовательно соединенные и третий -разрядный регистры сдвига и логическую схему, причем информационный вход первого регистра подключен к первому выходу блока 1 стереоскопического формирования изображенияПервый и второй входылогической схемы подключены соответственно к выходам первого и второ. го регистров, а выход - к информационному входу третьего регистра, входы синхроимпульсов сдвига которого, а также первого и второго регистров соединены с вторым выходом блока 4 управления.1 О 15 20 45 Блок 9 пРинЯтиЯ Решений предназ начен для сопоставления признаков распознаваемого объекта с эталонным и содержит: регистр, триггер, элемент И, схему сравнения, причем первые входы схемы И и схемы сравнения соединены с выходом блока 8 хранения эталонов, второй вход - с выходом триггера, первый вход которого соединен с пятым вьгкодом блока 4 управления, третий вход схемы сравнения подключен.к выходу регистра, входы которого подключены соответственно к выходу блока 5 выделения линий и к первому выходу блока 7 анализа контуров, а выход схемы сравнения подключен к второму входу регистра и элемента И, выход которого подключен к выходу устройства.Блок 8 хранения эталонов предназначен для последовательной выдачи кодов множества распознаваемых образцов и их признаков и содержит последовательно соединенные генера тор, счетчик, постоянное запоминающее устройство, причем выходы счетчика и постоянного запоминающего устройства подключены к первому входу блока 9 принятия решений. 3Блок 3 идентификации предназначен для восстановления пространственных координат ; изображений и содержитПЗУ, ь коммутаторов изапоминающих устройств (ЗУ), причем информационные входы ЗУ подключены к вь 1 ходу блока 2 преобразования, выход их - к первым входам блока 6 формирования признаков и блока 7 анализа контуров, а адресные входы соответствующих ЗУ через коммутаторы подключены к выходам ПЗУ, входы которых и вторые входы коммутаторов блока соединены с вторым входом блока 4 управления.Устройство работает следующимобразом,В устройстве осуществляется распознавание образов в блоке 9 принятия решений сравнением эталонных признаков Ч , поступающих с блока 8 .хранения эталонов, и выделенных трех групп признаков УЧ, поступающих соответственно с выхода блока 5 выделения линий, блока 7 анализа контуров и блока 6 формирования признаков, пФичем признаки 1 ч связаны с векторными характеристиками прямолинейных участков границ распознаваемого образа, Ч - с кривизной его границ, У, - с векторными характеристиками нормалей точек перегиба и углов его границ. Признаки Ч, . ,Ч, формируются иэ анализа множества п касательных к границам распознаваемого объекта, для чего первоначально в блоке 1 стереоскопического формирования изображения из матричной памяти, куда заносится изображение распознаваемого объекта, формируется трехмерное пространство, образованное изплоскостей,в каждой плоскости которого изображение повернуто относительно предыдущего на угол360с = -- . Далее в блоке 2 преобразо- и вания в каждой из . плоскостей вы 1деляются координаты точек границизображения, соприкасающиеся с горизонтальными секущими в ней, исходяиз логической импликации элементовсоседних строк изображения, Затемблок 3 преобразования осуществляетсовмещение пространственных координат точек соприкосновения, образуяописание исходного объекта в дискретном множестве 1 ) касательных к точкам границ изображения.Образование трехмерного пространства распознаваемого образа производится в блоке 1 стереоскопическогоформирования изображения, где пространственные координаты исходногообъекта, занесенные в блок 3 памяти,преобразуются в соответствующие координаты , плоскостей в ь; постоянном запоминающем устройстве 37,При последовательном опросе черезкоммутатор 34 блока 33 памяти счетчиками 42 и 43 координат Х, У блока4 управления опрашиваются также ПЗУ37, с выхода которых преобразованныекоординаты через коммутаторы 36 поступают на адресные входы запоминаю"щих устройств 35, на информационныевходы которых в этот момент поступают данные с выхода блока 33 памяти,а на стробирующие входы - сигналразрешение записи с выхода дешифратора 46 блока 4 управления,По заполнению запоминающих устройств 35 на выходе счетчика 43координатв блоке 4 управлениядоявляется сигнал переполнения, 244683Таким образом, на вход третьего регистра с выхода логической схемы поступает информация, содержащая логическую импликацию текущей и предыдущей строки изображения, "единицав которой соответствует наличию касательной линии к границе изображения, наклон которой определяется номером ; опрашиваемого запоминающего устройства 35 блока 1 стереоскопического формирования изображений. С выхода третьего регистра блока 2 преобразования информация, содержащая точки соприкосновения касательных к границе изображения, записывается в соответствующие ; запоминающие устройства блока 3 идентификации стереопар, причем адрес записи поступает с выхода постоянного запоминающего устройства этого же блока, осуществляющего восстановление пространственных координат границы иэображения объекта. Кроме того, с выхода третьего регистра блока 2 преобразования данные после завершения считывания строки, заносятся в регистр 25 блока 5 выделения линий сигналам переполнениясчетчика 42 блока 4 управления. Данные с регистра 25, содержащие точки пересечения границы изображения с касательной, начинают поочередно опрашиваться через селектор-мультиплексор 26 счетчиком 42 блока 4 управления. С выхода селектора-мульустанавливающий триггер 47 в единичное состояние, с его выхода управляющий сигнал с дешифратора 46 снимает сигнал общего разрешения записи информации. В этом случае дешифратор 46 блока 4 управления разрешает поочередное считывание данных с ЗУ 35, поступающих на вход последовательно соединенных первого и второго регистров блока 2 преобразования. Разрядность этих регистров равна числу элементов в строке иэображения.Выход первых К разрядов первого регистра, соответствующих текущему значению строки, поступает на первый вход логической схемы, реализующей функцию логической импликации, на второй вход которой поступает информация с первых К разрядов второго регистра, соответствующих предыдущему значению строки. 1 О 15 20 25 30 35 40 45 50 55 типлексора 26 данные поступают на Я-вход триггера 27 и стробируются.В зависимости от наличия информации триггер 27 находится в состоянии 1 или 0" и через элементы29,30 соответственно разрешаетввод счетчика 31, определяющегоколичества точек изображения на касательной 1 , или счетчика 32, определяющего количество точек касательной до появления изображения, Вконце изображения на данной касательной триггер 27 переходит иэ состояния 1 и в 0, по которому формирователь 28 образует синхроимпульс,поступающий в блок 9 принятия решений, производящий .считывание длины прямолинейного отрезка границыизображения со счетчика 31 и его местоположения со счетчика 32. По завершении заполнения и запоминающих устройств блока 3 идентификации сигналпереполнения счетчика 45 блока 4 управления взводит триггер 48, которыйчерез элемент 2 И-ИЛИ 44, элементИ 40 и элемент ИЛИ 41 перекоммутируетпоследовательность взвода счетчиков45 и 42,43В данном случае первоначально взводится счетчик 45 опросаномера запоминающих устройств блока 3 идентификации, и затем по егопереполнению счетчики 42 и 43 координат. Таким образом, блок 4 управле-,ия организует последовательныйопрос 1 запоминающих устройств блока 3 идентификации стереопар, выделяяколичество касательных и их наклон вданной точке границы иэображения распознаваемого образа. Считанные дан -.ные с выхода блока 3 поступают навход блока 6 формирования признакови блока 7 анализа контуров,В блоке 6 формирования признаковвходные данные поступают на Э -входтриггера 18, где они стробируютсясинхроимпульсом и при наличии информации триггер 18 устанавливается всостояние "1". В зависимости от состояния триггера 18 разрешается счетсинхроимпульсов счетчиком 20 или счетчиком 22, Таким образом, на счетчи=ке 22 устанавливается количество касательных из множества в данной,локальной точке границы иэображения,а в счетчике 20 - их отсутствие,При взводе триггера 18 с формирователя 19 снимается стробирующий им 244 б 83пульс, и на выходе схемы 21 совпадения появляется сигнал, соответствующий наличию н локальной точке границы иэображения распознаваемого знака двух касательных, угол векторовб нормалей которых составляет 180 что соответствует наличию точки перегиба (признак Ч ) . Наличие нескольких касательных изл и их ко- О личество в счетчике 22 формируетпризнак Ч наличия в локальной точке границы изображения распознаваемого знака угла 11, образованного двумя прямыми и равного 55 -.: (и - к)где К - показания счетчика 22,Значение угЛа р формируется в 20 признак Ч из показания счетчика 22 на дешифраторе 24" ,а сумматор 23, определяющий разницу показаний счетчика 45 блока 4 управления и счет чика 20, характеризует угол наклона. 25 вектора нормали к точке перегиба признака,.В блоке 7 анализа контуров производится определение кривизны локальных участков (признак Ч,) по количест- ЗО ву Г касательных из ) на его границах, (1 с=(1-1) С), где С - константа) для чего через элемент И 11 блока 7 анализа контуров сигнал переполнения счетчика 43 блока 4 управ- З 5 ления взводит счетчик опроса блока памяти 33, При наличии информации с выхода блока 33 памяти вэводится триггер 1 О, прерывающий работу счетчика 12, и счетчик 15 начинает осу О ществлять подсчет числа касательных на локальном участке изображения, определяемого при сравнении схемой 13 сравнения координат опроса ЗУ блока 3 и счетчика 12. 45Дешифрованные признаки 1 с дешифратора 16 поступают на счетчик 17, где они накапливаются. По завершению опроса ЗУ блока 3 идентификации сигнал переполнения счетчика 4350 сбрасывает триггер 10, и процесс продолжается аналогично до переполнения счетчика 12, переполнение которого сбрасывает триггеры 47 и 48 блока 4 управления через формирователь 49 короткого импульса и заносит в блок 9 принятия решений признакЧ . Од-новременно по этому импульсу завершается занесение признаков изображения, взводится триггер блока 9 принятия решений, который разрешает схеме сравнения сравнивать полученные признаки с эталонными, поступающими с блока 8 хранения эталонов.1 спольэонание заявляемого устройства позволяет снизить требования к исходному шрифту, а значит и требования при подготовке входной документации, расширить входной алфавит и нацежность распознавания.Формула и з о б р е т е н и я1,Устройство для распознавания образон, содержащее блок стереоскопического Формирования изображений, первый вход которого является входом устройства, второй вход подключен к первому выходу блока управления, первый выход - к первому входу блока преобразования, выход которого соединен с первым входом блока идентификации стереопар, второй вход которого подключен к второму выходу блока управления, блок принятия решений, первый вход которого соединен с выходом блока хранения эталонов, второй вход - с первым выходом блока анализа контуров, а выход являет - ся выхоцом устройства, о т л и ч а ющ е е с я тем, что, с целью повышения достоверности распознавания, оно содержит блок выделения линий и блок формирования признаков, выход которого подключен к третьему входу блока принятия решений, первые входы блока формирования признаков и блока анализа контуров соединены с выходом блока идентификации стереопар, второй нход блока формирования признаков подключен к третьему выходу блока управления, четвертый выход и вход которого соединены соответст-. венно с вторым входом и вторым выходом блока анализа контуров, тре- тий вход и третий выход которого подключены соответственно к второму выходу и третьему входу блока стереоскопического формирования изображений, первый вход блока выделения линий соединен с выходом блока преобразования, а выход - с четвертым входом блока принятия решений, пятый вход которого подключен к пято 1244683 12му выходу блока управления, шестой выход которого соединен с вторыми входами блока преобразования и блока выделения линий.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок анализа контуров содержит триггер, один из входов которого является третьим входом блока, первый и второй элементы И, схему сравнения, дешифратор, первый, второй и третий счетчики, выход последнего является первым выходом блока, вторым выходом которого является инверсный выход триггера и один из выходов первого счетчика, другой выход которого подключен к первому входу схемы сравнения и является третьим выходом блока, четвертым входом которого является второй вход схемы сравнения, один иэвходов первого элемента И и другойвход триггера, соединенный с однимих входов третьего счетчика, другойвход которого подключен к выходудешифратора,вход которого соединен О с выходом второго счетчика, вход .которого подключен к выходу второгоэлемента И, первый вход которого являетсяпервым входом блока, а второй вход соединен с выходом схемы 5 сравнения, причем прямой выходтриггера подключен к другому входупервого элемента И, выход которогосоединен с входом первого счетчика.1244 б 83 Составитель Т,НичипоровичРедактор М,Циткина Техред Л.Олейник Корректор В,Бутяга Заказ 3920/53 Тираж 671 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 13035, Москва, Ж, Раушская наб., д,4/5