Устройство для отслеживания контуров двумерных объектов

 

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

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

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

РЕСПУБЛИК ф)

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) (я)л G 06 F 15/66

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

k (21) 4776506/24 (22) 03,01.90 (46) 07.01,93, Бюл, ¹ 1 (72) Г.И.Васильев, Е.И.Зинченко, В,В.Храмов м А.Е. И гнатен ко (56) Авторское свидетельство СССР

N 1314353, кл. G 06 F 15/66. 1987.

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

¹ 1088029, кл. G 06 К 11/00, 1984, (54) УСТРОЙСТВО ДЛЯ ОТСЛЕЖИВАНИЯ

КОНТУРОВ ДВУМЕРНЫХ ОБЪЕКТОВ (57) Изобретение позволяет повысить надежность выделения контура объекта на

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

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

Недостатком этого устройства является

его конструктивная сложность.

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

Недостаток устройства — невысокая надежность, Наиболее близким к предлагаемому по технической сущности является устройство для отслеживания контуров двуМефйИх объектов на прямоугольном растре, содержащее блок управления, блок коммутации, регистр, блок обработки, линии связи, шины данных, шину управления; шину адреса. В блок обработки входит схема сравнения, коммутатор, узел ассоциативной памяти, счетчик, сумматор, два сумматора йо моду- лю восемь, линии связи и повышения быстродействия устройства, в блок обработки введены первый и второй сумматоры по модулю шесть, причем выход счетчика количества единиц кода соединен с информационным входом первого сумматора по модулй шесть, выход которого соединен с информационным входом второго сумматора по мо178б493 дулю шесть, второй информационный вход которого является вторым входом блока обработки, а выход — информационным выходом блока обработки, причем управляющие входы первого и второго сумматоров по модулю шесть соединены, соответственно, с третьим и четвертым управляющими входамй блока обработки.

Недостаток устройства — конструктивт нэя cJlo>KHocTb и низкое быстродействие, 10

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

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

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

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

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

"Существенные отличия".

1786493

25

50

16о,если С =1 0, если С =0

На фиг,1 представлена блок-схема предлагаемого устройства; на фиг.2 — конструктивное использование блока обработки; на фиг.3 — вариант конструктивного исполнения блока управления; на фиг.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 также по стандартной схеме с использованием известных инженерных решений (Соломатин

В.Ф. Теория ассоциативных запоминающих устройств с распределенной записью информации. — Автометрия, hL 1, 1982, с, 29—

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

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

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

Фримена, который определяется переходами;

5 1

С

4 2

3 необходимо знать количество единичных граничных точек изображения К относительно точки С и значение кода Фримена для предыдущего шага Ri1, В этом случае для получения очередного значения кода надо вычислить выражение в; = в;-1 + к + А, (1) где А = 2 — константа. Все компоненты этого выражения трехзначные двоичные числа, а суммирование осуществляется по модулю шесть.

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

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

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

1786493

При этом по шине данных (ШД) 6 из ОЗЧ

ЭВМ поступают исходные значения Во и 6о (фиг,2), Если Gо = О, то на шине 18 появляется значение кода Оо, которое подается в счетчик 19 для подсчета единиц в коде. По управляющему сигналу, передаваемому по цепи 24, производится операция в блоке 19 по подсчету количества единиц в коде, результат по цепи 20 передается в сумматор

21 по модулю шесть, где при наличии управляющего сигнала 25 осуществляется складывание с константой равной двум (010).

Результатй сложения по модулю шесть из узла 21 подаются по шине 22 нэ вход узла

23, где по приходу управляющего сигнала по цепи 26 производится суммирование по модулю шесть с кодом Во, поступающим из регистра 5. Результаты суммирования по шине 7 поступают в узел формирования адреса 28 (УФА) (фиг.3), Особенности устройства УФА определяются типом ОЗУ ЭВМ. В частности, для ОЗУ типа ЗД основными элементами УФА являются дешифратор и два реверсивных счетчика, в которые предварительно записываются базовые адреса в соответствии с вычисленным значением кода

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

Новое значение адреса сравнивается в блоке 31 с адресами, которые были там записаны, то есть адресами границ информационного массива (и адресами предыдущих точек контура, если это не первый шаг); Если такое совпадение имеет место, то есть мы вышли на границу иэображения (или замкнули петлю по контуру, в случае несовпадения адресов для двух различных шагов), то наличие нулевого выходного сигнала на линии 33 позволяет через логический элемент

34 и цепь 41 сигнализировать в 3ВМ об окончании выделения контура. На этот же элемент поступает сигнал и от узла t4 по линии 17для прерывания программы выделения контура, в случае выхода на фоновую часть иэображения.

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

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

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

С учетом того, что узел сравнения с нулем может быть представлен в простейшем случае дизьюнктором на 6 входов, группа ключей — коньюнкторами, а узлы в блоке соединены последовательно — можно определить время задержки информации в блоке обработки т БО но+ кл+ сч+ 2 см, гдето =10 Hc;t> =-10нс; Ьс =30нс; t, "= но кл, сч

= 50 нс — среднее время задержки соответбыть либо 1, либо 2) при принятии решения о распознавайии, 25 В предлагаемом устройстве эа счет упрощения аппаратурной реализации блока обработки нэ два функциональных узла (узла ассоциативной памяти и сумматора) повышает быстродействие, 30 Среднее время задержки микросхем, выполненных на основе транзисторно-транзисторной логики, например серии К155, для сумматоров составляет t>"" =- 50 нс; для ассоциативной памяти — t " = 12 нс на

35 один разряд обрабатываемой информации — в устройстве обрабатывается шестиразрядная информация, следовательно, t3

720 нс, где Ь" и Ь вЂ” среднее время задерАП жки сумматора и ассоциативной памяти со40 ответственно, Суммарное время задержки и нэ этих двух узлах составляет з = 770 нс.

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

770 нс, При обработке массива информации размерностью и х и суммарный выигрыш составит т = 770 нс х и, 2

1786493

10 ственно узла сравнения с нулем, группы ключей, счетчика, сумматора.

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

132 = 150 нс+ 770 нс = 920 нс.

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

ts> 920

Бо 150 . з1

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

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

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

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

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

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

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

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

1786493

Фиг. 2

1786493

1786493

2б

Составитель Г,Васильев

Техред M,Ìîðãåíòàë Корректор E.Ïàïï

Редактор

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 1Q1

Заказ 248 Тираж Подписное

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

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