Устройство для отслеживания контуров двумерных объектов Советский патент 1993 года по МПК G06F15/66 

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

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

Недостатком этого устройства является его конструктивная сложность.

Известно также устройство, содержащее фотоэлектронный преобразователь,

первую и вторую группу ключей, группу дешифраторов, реверсивные счетчики, блок управления.

Недостаток устройства - невысокая надежность;

Наиболее близким к предлагаемому по технической сущности является устройство для отслеживания контуров Двум еЩУх б бъ- ектов- на прямоугольном растре, содержащее блок управления, блок коммутации, регистр, блок обработки, линии связи, шины данных, шину управления, шину адреса. В блок обработки входит схема сравнения, коммутатор, узел ассоциативной памяти, счетчик, сумматор, два сумматора по моду- лю восемь, линии связи и повышения быстродействия устройства, в блок обработки введены первый и второй сумматоры по модулю шесть, причем выход счетчика количества единиц кода соединен с информационным входом первого сумматора по модули шесть, выход которого соединен с информационным входом второго сумматора по моСО

С

ч со о

N ю

СО

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

i i.Недостаток устройства - конструктивная сложность и низкое быстродействие

Цель изобретения - повышение быстродействия..

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

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

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

блока обработки.

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

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

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

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

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

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

Сравнение заявленного решения с другими техническими решениями показывает,

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

аппаратурной реалйза цШТТём саМЫм к повышению надежности работы, увеличение быстродействия.,

Это позволяет сделать вывод о соответствии технического решению критерию Существенные отличия.

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

Устройство включает блок управления 1, первую группу ключей 2, соединенных шестой управляющей связью 3, выходную шину 4, регистр 5 кода предыдущего шага, получающего исходное значение по входной шине 6 данных, промежуточные значения по входной шине 7, блок обработки 8, на которой по шине 9 поступают значения кода предыдущего, шага, а по управляющей шине 10, включающей линии 17, 24, 25, 26, 27, осуществляется связь по управлению с блоком управления. Пятая управляющая связь 11 обеспечивает управление процессом записи информации в регистр 5 со стороны блока управления 1. Шина 12 обеспечивает сопряжение устройства по управлению, а шина 13-поадресации с ЭВМ. При этом блок обработки 8 содержит узел 14 сравнения с нулем, вторую группу ключей 15, управляющие входы которой подключены связью 16 к первому выходу узла 14, второй выход 17 этого узла связан с первым управляющим входом блока управления, информационную выходную шину 18 второй группы ключей, счетчик 19 количества единиц кода, имеющего информационную выходную шину 20, первый сумматор 21 по модулю шесть с выходной шиной 22 и второй сумматор.23 по модулю шесть, а также управляющие связи 24-27 с 1-4 выходами блока управления для синхронизации работы соответственно узлов 19, 21, 23 и 14.

Блок управления содержит узел формирования адреса 28 ;с информационным выходом 29, третью группу ключей 30, блок ассоциативной памяти 31, шину 32 записи информации в блок ассоциативной памяти, выход признака совпадения 33 блока ассоциативной памяти, логический элемент ИЛИ 34, имеющий один прямой и один инверсный входы и прямой выход 35, узел синхронизации 36, осуществляющий синх- ронизацию блока 31 по цепи 37, узла 28 по цепи 38, управляемый от шины управления ЭВМ по цепи 39 и сигнализирующий о выполнении шага вычислений в шину управления ЭВМ по цепи 40..

Узлы 2, 5, 14, 15,21. 23, 30 и 34 выполнены по стандартной схеме, блок 31 также по стандартной схеме с использованием известных инженерных решений (Соломатин В.Ф, Теория ассоциативных запоминающих

ycTpoucfe с распределенной записью ин- формации. - Автометрия, Ms 1, 1982. с. 29- 34), счетчик 19 реализован на основе авт.св. СССР N 892715, кл. Н 03 К 13/24, узел 28 реализован программно, а узел 36 реализован с использованием известных инженерных решений для реализации временной диаграммы, представленной на фиг.4.

Устройство работает следующим образом. .

Устройство реализует выполнение следующего эвристического алгоритма выделения контура двумерного объекта на гексагональном растре. Если изображение представлено двухуровневой матрицей (О или 1) размером n x n и известны две любые соседние точки контура объекта на контрастном изображении, то для выделения контура и представления его в виде кода Фримена, который определяется переходами; . О

5 1

С

42

3 .

необходимо знать количество единичных граничных точек изображения К относительно точки С и значение кода Фримена для предыдущего шага RI-I. В этом случае для получения очередного значения кода надо вычислить выражение

Ri Ri-i + K + A, (1) . где А 2 - константа. Все компоненты этого выражения трехзначные двоичные числа, а суммирование осуществляется по модулю шесть.

Если для каждой точки С иметь вектор G граничных значений размерностью шесть, то, определяя количество единиц в нем, получаем.К. Выбрав афинную систему координат и расположив граничные точки в векторе С следующим образом: первая компонента вектора - значение граничной с данной точкой С в направлении 1, вторая - в направлении 2 и так далее, шестая - в направлении 0 (фиг.4).

В ОЗУ ЭВМ для каждого j-ro элемента матрицы изображения хранится свое значение вектора

г / Go- если С 1 4 10, если С О

По шине управления 12 от ЭВМ поступают сигналы управления на второй управляющий вход блока управления 1 (фиг.1), по цепи 39 запускают узел синхронизации 36, который выдает управляющий импульс по цепи 11 в регистр 5 и по цепи 27 в узел 14.

При этом по шине данных (ШД) 6 из ОЗУ ЭВМ поступают исходные значения R0 и Go (фиг,2). Если Go - 0, то на шине 18 появляется значение кода Go, которое подается в счетчик 19 для подсчета единиц в коде. По управляющему сигналу, передаваемому по цепи 24, производится операция в блоке 19 по подсчету количества единиц в коде, результат по цепи 20 передается в сумматор 21 по модулю шесть, где при наличии управляющего сигнала 25 осуществляется складывание с константой равной двум (010), Результаты сложения по модулю шесть из узла 21 подаются по шине 22 на вход узла 23, где по приходу управляющего сигнала по цепи 26 производится суммирование по модулю шесть с кодом R0, поступающим из регистра 5. Результаты суммирования по шине 7 поступают в узел формирования адреса 28 (УФА) (фиг.З). Особенности устрой-, ства УФА определяются типом ОЗУ ЭВМ. В частности, для ОЗУ типа ЗД основными элементами УФА являются дешифратор и два. реверсивных счетчика, в которые предварительно-записываются базовые адреса в соответствии с вычисленным значением кода Фрммена происходит как показано в таблице, . , . ...:

Например, если данная страница ОЗУ типа ЗД имеет емкость 1 К, а базовый адрес равен 0100, 0010, то после информации .адреса в УФА при значении кода Фримена равном 1 новый адрес равен 0101, 0011.

Новое значение адреса сравнивается в блоке 31 с адресами, которые были там записаны/то есть адресами границ информационного массива (и адресами предыдущих точек контура, если это не первый шаг). Если такое, совпадение имеет место, то есть мы вышли на границу изображения (или замкнули петлю по контуру, в случае несовпадения адресов для двух различных шагов), то наличие нулевого выходного сигнала на ли- . нии 33 позволяет через логический элемент 34 и цепь 41 сигнализировать в ЭВМ об окончании выделения контура. На этот же элемент поступает сигнал и от узла 14 по линии 17 для прерывания программы выделения контура, в случае выхода на фоновую часть изображения.

Если же совпадение в блоке 31 не происходит, то единичный сигнал на выходе по цепи 33 открывает третью труппу ключей 36 и в блоке 3.1 осуществляется запись очередного адреса, который одновременно выдается на шину адреса ЭВМ для считывания очередного значения G.

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

устройством управления ЭВМ управляющей информацией.:

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

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

быстродействие и точность (по сравнению с прямоугольным растром, где расстояния между соседними точками контура могут быть либо 1, либо 2) при принятии решения о распознаваний..

В предлагаемом устройстве за счет уп- рсщения аппаратурной реализации блока обработки на два функциональных узла (узла ассоциативной памяти и сумматора) повышает быстродействие.

Среднее время задержки микросхем, выполненных на основе транзисторно-транзисторной логики; например серии К155, для сумматоров составляет t3CM 50 не; для ассоциативной памяти - t3Am 12 не на

один разряд обрабатываемой информации - в устройстве обрабатывается шестираз- рядиая информация, следовательно, Тз 720 не, где t$M и ХзДП- среднее время задержки сумматора и ассоциативной памяти соответственно. Суммарное время задержки

на этих двух узлах составляет t э 770 не.

Следовательно, время цикла в предлагае. мом устройстве в среднем будет меньше на

770 не. При обработке массива информации

размерностью n x n суммарный выигрыш

составит t 770 не x n2.

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

обработки

1,6°.МзНО + 1зКП + 1эь

+ 2ta

но .

где т.3г ° - 10 не; 13КЛ 10 не; гэсч 30 не; t3CM 50 не - среднее, время задержки соответственно узла сравнения с нулем, группы ключей, счетчика, сумматора.

Тогда время задержки в блоке обработки предлагаемого устройства t3i5° 150 не, а в устройстве принятом за прототип;

1з2 150 не + 770 не 920 не.

Отсюда эффективность предлагаемого блока обработки составляет

tJ2° 920 ft1 .ГГ

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

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

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

0 первым выходом блока сравнения с нулем, а выходы соединены с информационным входом счетчика количества единиц кода, первые управляющие входы блока сравнения с нулем и счётчика количества единиц

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

5 сумматоры по модулю шесть, причем выход счетчика количества единиц кода соединен с информационным входом первого сумматора по модулю шесть, выход которого соединен с информационным входом второго

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

5 сумматоров по модулю шесть соединены, соответственно с третьим и четвертым управляющими входами блока обработки.

Л1

1

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

C6W8Z.1.