УСТРОЙСТВО АССОЦИАТИВНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ Российский патент 2020 года по МПК G06K9/62 G06K9/68 

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

Известно устройство для распознавания образов, содержащее группу умножителей на весовые коэффициенты, входы которых являются входами устройства, параллельный сумматор, входы которого соединены к выходами умножителей на весовые коэффициенты, и блок вычисления активационной функции, вход которого соединен с выходом параллельного сумматора, а выход - является выходом устройства [Редько В.Г. Эволюция, нейронные сети, интеллект: Модели и концепции эволюционной кибернетики. М.: КомКнига, 2006, стр. ис. 5.1].

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

Известно также устройство ассоциативного распознавания, содержащее первый параллельный сумматор и первый блок вычисления активационной функции, вход которого соединен с выходом первого параллельного сумматора, а выход - является первым выходом устройства ассоциативного распознавания, Р-1 параллельных сумматоров со второго по Р-ый, Р-1 блоков вычисления активационной функции со второго по Р-ый, входы каждого из которых соединены с выходами одноименных параллельных сумматоров, а выходы являются одноименными выходами устройства ассоциативного распознавания, а также Р групп с первой по Р-ую блоков формирования значений функций принадлежности, выходы каждой из которых соединены с входами одноименных параллельных сумматоров, при этом, каждая из Р групп блоков формирования значений функций принадлежности содержит K блоков формирования значений функций принадлежности с первого по K-ый, входы каждого из которых соединены с входами одноименных блоков значений функций принадлежности каждой из других групп из Р групп блоков формирования значений функций принадлежности и являются входами устройства ассоциативного распознавания (RU 2342702 C2, МПК G06K 9/62, 27/06/2008).

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

Известно также устройство ассоциативного распознавания, содержащее Р блоков вычисления активационной функции и Р групп блоков формирования значений функций принадлежности, при этом каждая из Р групп блоков формирования значений функций принадлежности содержит K блоков формирования значений функций принадлежности, входы каждого из которых соединены с входами одноименных блоков значений функций принадлежности каждой из других групп из Р групп блоков формирования значений функций принадлежности и являются входами устройства ассоциативного распознавания, отличающееся тем, что введены Р групп блоков умножителей на весовые коэффициенты, каждая из которых содержит K блоков умножителей на весовые коэффициенты, входы каждого из которых соединены с выходами соответствующих блоков формирования значений функции принадлежности из Р групп блоков формирования функции принадлежности, а выходы соединены с соответствующими входами Р блоков выделения максимального сигнала, а выходы каждого из Р блоков выделения максимального сигнала соединены с входом соответствующего блока вычисления активационной функции из Р блоков вычисления активационной функции (RU 2504837 C1, МПК G06K 9/62, 20/01/2014).

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

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

Общим недостатком таких устройств является необходимость создания большого количества связей и длительного обучения для настройки их весовых коэффициентов [Николаенко С., Кадурин А., Архангельская Е. Глубокое обучение. - СПб.: Питер, 2018. - 480 с., ил.].

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

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

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

- на фиг. 1 представлен общий вид устройства;

- на фиг. 2 показано расположение элементов в матрицах запоминающих элементов и передающих элементов;

- на фиг. 3 показаны направления продвижения сигналов передающими элементами при гексагональном расположении элементов в матрицах;

- на фиг. 4 изображена схема концевого элемента Связи

- на фиг. 5 приведена схема коннектора концевых элементов связи запоминающего элемента;

- на фиг. 6 изображена схема промежуточного элемента связи;

- на фиг. 7 приведена схема коннектора промежуточных элементов связи;

- на фиг. 8 показана схема запоминающего элемента;

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

- на фиг. 10 показаны возможные точки соединения структурных элементов рукописных букв;

- на фиг. 11 изображено состояние матриц запоминающих и передающих элементов после записи эталонного образа буквы «m»;

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

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

Устройство ассоциативного распознавания содержит устройство ввода данных 1, блок управления 2, устройство вывода 3, матрицу запоминающих элементов 4 и матрицу передающих элементов 5. Выход 6 (эталонные образы) и выход 7 (анализируемый, он же распознаваемый образ) устройства ввода данных 1 связаны со входами блока управления 2. Блок управления 2 связан шиной данных и команд 10 с матрицей запоминающих элементов 4, который связан шиной команд 11 с матрицей передающих элементов 5. Выход 8 (список соответствий между структурными элементами) и выход 9 (оценка сходства) блока управления 2 связаны с устройством вывода 3.

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

Работа устройства описывается на примере гексагонального размещения активных элементов (Фиг. 2). Гексагональный растр более экономичен по количеству связей с соседними элементами по сравнению с ортогональным растром.

Запоминающий элемент (ЗЭ) содержит собственно запоминающий элемент и коннектор его концевых элементов связи 12 (КЭС).

Передающий элемент (ПЭ) - это промежуточные элементы связи (ПЭС) и коннектор промежуточных элементов связи 13.

При гексагональном размещении активных элементов каждый ЗЭ связан с помощью коннектора с шестью КЭС, а каждый передающий элемент имеет 9 ПЭС и коннектор, организующий передачу сигналов через них (фиг. 2).

Принцип установления связи между двумя запоминающими элементами (вершинами графа) заключается в поиске кратчайшего пути через незанятые элементы связи. С этой целью из обоих соединяемых ЗЭ исходят сигналы к их концевым элементам связи (фиг. 3а). От первого ЗЭ идет первичная волна, которая продвигается промежуточными элементами связи в 3 направления, ближайших по ходу волны (фиг. 3б, 3в), пока не дойдет до КЭС, примыкающего ко второму соединяемому ЗЭ. После этого, уже как вторичная волна, она возвращается обратно к первому ЗЭ, проходя и устанавливая в качестве элемента ребра графа на каждом шаге только один из возможных элементов связи, через которые прошла первичная волна.

Концевой элемент связи (КЭС) соединяет вершину графа с ребром графа, т.е. является началом или концом цепочки элементов связи, составляющих ребро графа.

Схема концевого элемента связи изображена на фиг. 4.

В режиме установления ребра графа КЭС работает следующим образом:

1. Из запоминающих элементов (ЗЭ), отображающих две связываемые вершины графа, исходят сигналы w₀₁ и w₀₂: w₀₁ - на шесть КЭС, примыкающих к первому ЗЭ, w₀₂ - на шесть КЭС, примыкающих ко второму ЗЭ (Фиг. 3а).

2. Сигнал w₀₁ из ЗЭ₁ запускает первичную волну установления ребра. Он проходит через элемент И1 в том случае, если данный КЭС еще не включился в состав какого-либо другого ребра графа, о чем сигнализирует триггер Т2. Включается триггер Т01, указывающий, что первичная волна прошла через данный КЭС, а формирователь Ф1 продвигает ее на соседний передающий элемент связи (ПЭС), находящийся в соответствующем направлении по отношению к данному КЭС.

3. Сигнал w₀₂ из второго связываемого ЗЭ, проходя через элемент И2 при условии, что данный КЭС не занят другим ребром (триггер Т2), включает триггер Т02, указывающий, что здесь должна закончиться первичная волна.

4. Когда первичная волна приходит на вход bвх такого концевого элемента связи, который подготовлен сигналом w02, она проходит через элемент И3 и переключает триггер Т2 в состояние, указывающее, что этот КЭС вошел в состав ребра графа. При этом формирователь Ф2 через cвых начинает вторичную волну, которая пойдет обратно в направлении ЗЭ1. Таким образом, КЭС, примыкающий к ЗЭ2, окончательно включился в состав формируемого ребра графа, а запущенная им вторичная волна включит в ребро промежуточные элементы связи, через которые прошла первичная волна, и КЭС, примыкающий к ЗЭ1.

5. Когда вторичная волна приходит на вход dвх исходного КЭС, примыкающего к первой из соединяемых вершин (см. п. 2), т.е. в котором включен триггер Т01, она включает данный КЭС в состав ребра графа с помощью формирователя Ф3 и передает на блок управления (БУ) сигнал «Связь есть», чтобы завершить процесс установления связи.

В режиме сравнения графов при включенном триггере Т2 (признак принадлежности ребру графа) работают каналы:

Через них осуществляется подготовка (активизация) тех ЗЭ (вершин графа), которые связаны цепочками элементов связи с ЗЭ, совпавшими на текущем шаге сравнения.

Коннектор концевых элементов связи запоминающего элемента. Коннектор КЭС запоминающего элемента организует работу концевых элементов связи, через которые данный ЗЭ может быть соединен с другими ЗЭ (фиг. 5).

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

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

Когда первичная волна приходит со стороны соседних промежуточных элементов связи (сигнал ) на коннектор второй соединяемой вершины, где сигналом W02 в КЭС включены триггеры Т02, она через элемент ИЛИ1 включает дешифратор, который поочередно открывает свои элементы связи.

Как только первичная волна попадает на КЭС, где включен триггер окончания ребра, сигнал t2 из нее через элемент ИЛИ2 выключит дешифратор, тем самым не давая возможности другим КЭС этого коннектора включиться в состав ребра графа. Тогда вторичная волна пойдет обратно только из одного КЭС.

Заканчивается процесс установления ребра графа когда вторичная волна вернется на и с помощью дешифратора попадет в один из тех КЭС, где стартовала первичная волна.

Схема промежуточного элемента связи (ПЭС) изображена на фиг. 6.

В режиме установления ребра графа ПЭС работает следующим образом. Первичная волна из КЭС, примыкающего к ЗЭ₁ в зависимости от направления ее движения, которое определяется коннектором передающих элементов связи (фиг. 7), приходит на а^вх или b^вх и продвигается данным ПЭС на а^вых или b^вых соответственно. Включившийся при этом триггер Т1 показывает, что прошла первичная волна. Вторичная волна из КЭС, примыкающего к ЗЭ₂, приходит на c^вх или d^вх и, если включен Т1, включает данный ПЭС в состав цепочки элементов связи, отображающей ребро ЗЭ₁ - ЗЭ₂ графа, путем включения Т2. При этом вторичная волна продвигается на c^вых или d^вых пока через такие же ПЭС не дойдет до КЭС, примыкающего к ЗЭ₁:

1. Первичная волна W1 приходит на вход a^вх. Начав свой путь от какого-то концевого элемента связи (см. выше), она проходит через элемент И1, если данный элемент связи еще не включен в состав какого-либо ребра графа (триггер Т2). При этом включается триггер Т1 - признак «Была первичная волна» и формирователь Ф1 продвигает ее далее через выход а^вых и связанные с ним входы соседних ПЭС, передающих сигналы по трем ближайшим направлениям (фиг. 3б). В зависимости от направления движения волны, она может прийти на а^вх или b^вх и выйти через а^вых или b^вых соответственно. Если обозначить входы и выходы ПЭС запоминающего элемента как B_ij, i=1…6, j=1…6, то волна идет от входа i к выходу j=i+3, или к выходу j=i+2, или к выходу j=i+4.

2. Когда из другого КЭС, который примыкает ко второму связываемому ЗЭ, начнет возвращаться вторичная волна W2, она идет по линии c^вх - И5 - ИЛИ3 - Ф2 - И6 - c^вых или d^вх - И7 - ИЛИ3 - Ф2 - И8 - d^вых. При этом, если данный ПЭС еще не включен в состав ребра графа (триггер Т2), но проходила волна W1 (триггер Т1), то формирователь Ф2 включает триггер установления связи Т2, сбрасывает триггер Т1 первичной волны и продвигает W2 далее.

3. Волна W2 должна уйти только на один из трех ПЭС, ближайших по направлению передачи сигнала, и на которых побывала волна W1. С этой целью на вход g поступает сигнал из коннектора передающих элементов связи (фиг. 7), который поочередно опрашивает свои ПЭС. Как только найдется такой ПЭС, в которой включен триггер T1, т.е. была первичная волна, формирователь Ф2 включит триггер установления связи Т2, а сигнал с выхода t₂ сообщит об этом своему коннектору.

В режиме сравнения графов при включенном триггере Т2 (признак принадлежности ребру графа) работают каналы:

Через них осуществляется подготовка (активизация) тех ЗЭ (вершин графа), которые связаны цепочками элементов связи с ЗЭ, совпавшими на текущем шаге сравнения.

Коннектор промежуточных элементов связи. Коннектор ПЭС (фиг. 7) организует работу девяти промежуточных элементов связи (в случае гексагонального размещения активных элементов), расположенных в некотором узле гексагональной решетки и через которые ЗЭ могут быть соединены с другими ЗЭ.

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

Каждый ПЭС одного коннектора передает выходные сигналы в прямом и обратном направлении как показано на фиг. 3б, а коннектор распространяет один входной сигнал на три ПЭС в соответствии с фиг. 3в.

Сигналы первичной волны через шину приходят на входы а^вх или b^вх промежуточных элементов связи в зависимости от направления ее движения (фиг. 3б) и выходят из них (а^вых или b^вых) через шину данного коннектора на соответствующие входы шины соседних коннекторов.

Сигналы вторичной волны через шину приходят на входы c^вх или d^вх промежуточных элементов связи и выходят из них (c^вых или d^вых) через шину данного коннектора на соответствующие входы соседних коннекторов - на их шины . При этом, чтобы вторичная волна уходила не на все три ближайших направления (фиг. 3в), а только на те ПЭС, на которых побывала первичная волна, дешифратор коннектора посылает сигнал на вход g своих ПЭС для опроса, была ли на них первичная волна. Дешифратор прекращает опрос, как только на ИЛИ2 поступит сигнал t₂ из ПЭС, которая включилась в состав цепочки элементов, связывающих два запоминающих элемента.

Запоминающий элемент (фиг. 8) служит для хранения в виде атрибутов (признаков) информации одной вершины эталонного графа G_E и для сравнения этой информации с вершинами анализируемого графа G_A, а также для установления связей между запоминающими элементами (ЗЭ), которые в эталонном графе соединены ребрами.

Запоминающий элемент содержит 4 блока памяти:

- собственные параметры;

- блок функциональных программ;

- атрибуты информации;

- ключи связи с другими ЗЭ, а также

- один пороговый элемент, срабатывающий при совпадении входной информации с информацией, хранящейся в ЗЭ.

В блоке собственных параметров хранятся:

1. Идентификатор (ID) запоминающего элемента - уникальный шифр элемента, отличающий его от других ЗЭ системы.

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

3. Состояние (Status) принимает значение {0, 1, 2, 3, 4, 5}, в зависимости от режима работы ЗЭ (0 - ЗЭ свободен, 1 - ЗЭ занят, 2, 3 - идет установление связи между элементами, 4 - связь установлена, 5 - идет сопоставление графов образов).

4. Признак готовности ЗЭ (Ready) к сравнению с очередной вершиной анализируемого графа. Принимает значения «Вкл/Выкл» (On/Off).

5. Признак совпадения (Match) данной вершины эталона с очередной вершиной анализируемого графа. Принимает значения «Вкл/Выкл» (On/Off).

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

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

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

- прием и запоминание информации;

- установление связей с другими ЗЭ;

- сравнение информации ЗЭ с информацией очередной вершины анализируемого образа.

Функции ЗЭ реализуются тремя программами P1, Р2, Р3.

Р1. Прием и запоминание атрибутов. Запускается в состоянии Status=0:

1. Установление (запоминание) класса вершины Class=<наименование типа вершины>, вершины разных типов могут иметь различные наборы атрибутов.

2. Прием и запоминание имен a₁, …, a_N и значений v₁, …, v_N атрибутов.

3. Переключение статуса ЗЭ в состояние Status=1 - ЗЭ занят.

Р2. Установление связи. В большинстве прикладных задач сопоставления графов различаются входящие и исходящие дуги. Здесь для большей универсальности каждый ЗЭ, отображающий вершину графа имеет список начальных и список конечных адресов элемента. Эти адреса указывают на вершины, с которыми связана данная вершина. Можно их трактовать как списки исходящих и входящих дуг.

Сигналы Status=2 или Status=3 приходят из блока управления (БУ) одновременно на два связываемых ЗЭ эталонного графа образа. Сигнал Status=2 означает, что элемент, отображаемый данным ЗЭ, должен соединиться своим началом с другим ЗЭ, т.е. с началом или концом другого элемента в зависимости от того, какой из сигналов Status=2 или Status=3 придет на второй ЗЭ. Соответственно, если на данный ЗЭ приходит сигнал Status=3, он должен соединиться своим концом с началом или концом другого элемента.

1. Команда Status=2 или Status=3 установления связи проходит через свободный (Gate=Off) выход g₁, …, g₃ или g₄, …, g₆, соответственно и распространяется элементами связи. Первичная волна через концевой элемент связи (КЭС) первого ЗЭ и промежуточные элементы связи (ПЭС) распространяется до КЭС второго ЗЭ. Оттуда возвращается вторичная волна через те ПЭС, через которые прошла первичная волна. Из КЭС первого ЗЭ она попадает на один из свободных входов g'₁, …, g'₃ или g'₄, …, g'₆ этого элемента соответственно. При этом задействованные элементы связи включаются как занятые.

2. Запоминание (включение) соответствующей связи Gate_k=On.

3. Переключение ЗЭ в Status=4 - связь установлена.

Р3. Сравнение. Запускается, если запоминающий элемент готов к сравнению (Ready=On) путем установления его в состояние Status=5:

1. Из блока управления на входы всех ЗЭ одновременно поступает наименование C типа, имена x₁, …, x_N и значения y₁, …, y_N атрибутов искомой (сравниваемой) вершины анализируемого графа G_A. Если на пороговом элементе какого-то ЗЭ эталонного графа G_E произошло совпадение с типом и атрибутами этого ЗЭ, то включается признак совпадения Match=On.

2. Совпавший ЗЭ активизирует связанные с ним ЗЭ, посылая сигнал через свои включенные связующие выходы g₁, …, g_M. Этот сигнал проходит через включенные элементы связи на соответствующий вход g'₁, …, g'_M связанного ЗЭ и активизирует его путем включения признака готовности Ready=On.

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

Блок управления обеспечивает работу устройства, осуществляя запись информации эталонного графа в матрицы запоминающих элементов (вершин графа) и передающих элементов (ребер графа), управляет их работой в процессе установления связей и сопоставления графов, вычисляет оценку сходства с помощью соответствующих программ PN1, PN2, PN3.

PN1. Запись информации эталонного графа.

1. Запись в запоминающие элементы (ЗЭ) имен классов и атрибутов вершин графа. Информация очередной вершины графа заносится в первый попавший свободный (Status=0) ЗЭ. Переключение состояния ЗЭ в Status=1.

2. Установление связей между ЗЭ, отображающими вершины графа, которые связаны ребром. Команды Status=2 или Status=3 одновременно поступают на два связываемых ЗЭ.

3. При получении ответа Status=4 (связь установлена) от обоих связываемых ЗЭ выполняется связывание следующей пары ЗЭ. Так пока все ребра эталонного графа не будут зафиксированы в матрице передающих элементов.

PN2. Ассоциативный поиск - грубое (предварительное) распознавание: поочередно информационный вектор атрибутов каждой вершины G_A сравнивается одновременно со всеми вершинами G_E. Количество совпадений накапливается в блоке управления.

1. Активизация класса (множества) субъектов по атрибуту «Наименование класса».

2. Выборка из числа активных субъектов по вектору значений атрибутов.

3. Вычисление степени сходства С=N1/N2, где N1, N2 - количество совпавших и общее количество вершин эталонного графа соответственно.

На основании этой грубой оценки, в зависимости от задачи, блок управления (БУ) принимает решение: закончить процесс сопоставления этих графов или продолжить, но теперь уже учитывая связи между вершинами и ребрами внутри этих графов.

PN3. Сопоставление эталонного графа G_E с анализируемым графом G_A.

1. Все ЗЭ переводятся в режим сравнения Status=5.

2. Имя класса и атрибуты первой вершины графа G_A сравниваются одновременно со всеми ЗЭ, хранящими информацию вершин эталонного графа.

Если в каком-то ЗЭ произошло совпадение, то он через передающие элементы, связывающие его с другими ЗЭ (вершинами графа G_E), активизирует (подготавливает) эти ЗЭ к следующему шагу - сравнению со следующими вершинами анализируемого графа.

3. В анализируемом графе берется такая вершина, которая связана ребром с предыдущей совпавшей вершиной и сравнивается с активизированной для сравнения (Ready=On) вершиной эталонного графа, т.е. теперь при сравнении вершин графов учитываются и связи между ними. Если найдено несколько удовлетворительных вершин в G_E, то БУ организует стек для поочередной проверки возможных мест установки (отображения) вершин анализируемого графа на граф эталона.

4. Переход к сравнению следующей вершины анализируемого графа.

Если на некотором шаге сопоставления графов очередная вершина G_A не совпала ни с одной вершиной G_E, то берется другая вершина из G_A, связанная с предыдущей совпавшей. Если таковых нет, то очередная вершина G_A сравнивается как первая - со всеми вершинами G_E.

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

5. Вычисление уточненной оценки сходства графов G_A и G_E по суммарному количеству вершин в совпавших цепочках. При этом перекрывающиеся части цепочек учитываются один раз

Отметим, что устройство может хранить одновременно множество эталонных образов. Это зависит от числа элементов в его матрицах 2, 3 (фиг. 1).

Рассмотрим работу устройства на примере распознавания рукописных букв. Буквы состоят из структурных элементов, приведенных в таблице 1. Пусть имеется эталонный образ буквы «m» (фиг. 9а), который требуется сравнить с образами букв «h», «n» (фиг. 9б, 9в).

Структурные элементы букв имеют следующие атрибуты:

1. Chord Length - длина хорды, соединяющей концы элемента.

2. Segment Number - число сегментов, образованных цепочкой слева и справа от хорды элемента.

3. Left Segment Area - площадь сегмента слева от хорды, считая хорду направленной от начала цепочки к концу.

4. Right Segment Area - площадь сегмента справа от хорды.

5. Max Area Height - максимальная высота сегментов хорды.

6. Tilt Angle - угол наклона хорды.

7. Closed - данный элемент является замкнутым.

Буква «m» (фиг. 9а) - конструкция, состоящая из короткой палочки, обозначенной буквой а, двух вертикальных палочек d, е, одной левой дуги b и одной извилины c, образующих два узла. В первом узле палочка а нижним концом соединена с верхним концом палочки d и с левым концом дуги b. Во втором узле правый конец дуги b соединен с верхним концом палочки е и левым концом извилины c (см. таблица 2). Расположение точек соединения элементов показано на фиг. 10.

В результате записи эталонного образа буквы «m» в матрицах запоминающих и передающих элементов установятся связи как показано на фиг. 11.

Рассмотрим работу устройства в процессе сопоставления образов.

На этапе ассоциативного поиска (грубого распознавания) при сопоставлении буквы «h» с эталоном буквы «m» совпадут все элементы кроме «b», т.е. степень сходства C=4/5. При сопоставлении буквы «n» совпадут все элементы кроме «c», степень сходства C=4/5.

На этапе сопоставления графов «m» и «h»:

Шаг 1. Элемент 1 буквы «h» совпадет с элементом «а» буквы «m», который через элементы связи подготовит для сопоставления на следующем шаге элементы «b» и «d».

Шаг 2. Элемент 2 буквы «h» не совпадет с активизированными на предыдущем шаге (разрешенными для сравнения) элементами «b» и «d» буквы «m». Тогда он будет сравниваться снова, как на шаге 1, со всеми элементами буквы «m». Произойдет совпадение с элементом «c», который через элементы связи подготовит для сопоставления на следующем шаге элементы «b» и «e».

Шаг 3. Элемент 3 буквы «h» совпадет с элементом «е» буквы «m».

Таким образом, не будут отмечены как совпавшие элементы «b» и «d» буквы «m». Уточненная степень сходства C=3/5.

При сопоставления графов «m» и «n»:

Шаг 1. Элемент 1 буквы «n» совпадет с элементом «а» буквы «m», который через элементы связи подготовит для сопоставления на следующем шаге элементы «b» и «d».

Шаг 2. Элемент 2 буквы «n» совпадет с элементом «b» буквы «m», который через элементы связи подготовит для сопоставления на следующем шаге элементы «c», «d» и «е».

Шаг 3. Элемент 4 буквы «n» совпадет с элементом «е» буквы «m», который через элементы связи подготовит для сопоставления на следующем шаге элемент «c».

Шаг 4. Элемент 3 буквы «n» не совпадет с разрешенным для сравнения в результате предыдущего шага элементом «c» и он будет сравниваться снова, как на шаге 1, со всеми элементами буквы «m». Произойдет совпадение с элементом «d».

В результате, не будет отмечен как совпавший элемент «c» буквы «m». Уточненная степень сходства C=4/5.

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

Принцип действия устройства был промоделирован с помощью специализированного аппаратно-программного комплекса.. Образец рукописного текста заимствован из [Кучуганов М.В., Кучуганов А.В. Дескрипционная логика на графах изображений. // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, Вып. 4, 2018, Т. 28, С. 582-594. DOI: 10.20537/vm180410].

На фиг. 12 показана панель описания структурных элементов букв и результаты поиска этих элементов на изображении.

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

Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах автоматического распознавания образов со сложной структурой: изображений объектов, моделей ситуаций и других данных, представленных в виде атрибутивных графов или семантических сетей - совокупностей связанных между собой структурных элементов, заданных наборами (векторами) признаков. Техническим результатом настоящего изобретения является повышение надежности распознавания образов со сложной структурой таких, что для каждого структурного элемента образа требуется свой набор значений признаков - свой запоминающий элемент. Устройство ассоциативного распознавания содержит устройство ввода данных, блок управления, устройство вывода и матрицу запоминающих элементов, связанную шиной данных и команд с блоком управления. Устройство дополнительно содержит матрицу передающих элементов, связанную шиной команд с матрицей запоминающих элементов, а каждый передающий элемент связан шинами команд с ближайшими соседними передающими элементами. 2 з.п. ф-лы, 13 ил., 2 табл.

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

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

3. Устройство по п. 1, отличающееся тем, что запоминающие элементы выполнены на основе микропроцессоров, а передающие элементы связи выполнены на основе сверхбольших интегральных схем.