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

 

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

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

РЕСПУБЛИК (51)5 G 06 F 15/66

НОЕ ПАТЕНТНОЕ

ССР

CPj

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

KKI

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

) 4940959/24

) 03.06.91

) 30,08.93. Бюл. М 32

) В.В. Храмов, Г.И. Васильев, Е.И. Зиннко и А.Е. Игнатенко

) Заявка Франции N. 2555003, 6 06 Р 15/66, 1985.

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

1314353, кл, G 06 Е 15/66, 1987.

4) УСТРОЙСТВО ДЛЯ .ОТСЛЕЖИВАНИЯ

НТУРОВ ДВУМ Е РН ЫХ ОБЬЕКТОВ

7) Изобретение позволяет повысить нажность выделения контура объекта на умерном гексагональном растре за счет нтроля за выходом обнаруживаемой с поИзобретение относится к вычислительнрй технике и может быть использовано в с ставе специализированных вычислительн ix системах обработки изображения.

Целью изобретения является повышен е надежности отслеживания контура объе та на гексагональном растре, На фиг. 1 представлена блок-схема устр йства; на фиг. 2 — конструктивное использ вание блока обработки; на фиг, 3— в риант конструктивного исполнения блока у равления.

Устройство включает блок управления

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

„„ „Ы„„1837329 А1 мощью устройства точки контура объекта внутрь его изображения, В устройстве производится контроль за очередной порцией входной информации с помощью вновь введенного логического элемента И 41, первые шесть входов которого подключены к соответствующим линиям входной шины устройства, седьмой вход 27 является входом синхронизации и подключен к блоку управления 1. а выход логического элемента ИЛИ

41 подключен к первому входу логического элемента 42, второй вход которого подключен к выходу узла сравнения с нулем, выход элемента ИЛИ 42 подключен по линии 17 к первому управляющему входу блока управления. 4 ил., 1 табл, предыдущего шага, а по управляющей шине

10 (включающей линии 17, 24, 25, 26, 27) осуществляется связь по управлению с блоком управления. Пятая управляющая связь 11 обеспечивает управление процессом записи информации в регистр 5 со стороны блока управления 1. Шина 12 обеспечивает сопряжение устройства по управлению, а шина 13 по адресации с ЭВМ.

При этом блок обработки 8 содержит узел сравнения с нулем 14, вторую группу ключей

15, управляющие входы которой подключены связью 16 к первому выходу узла 14, второй выход 17 этого узла связан с первым управляющим входом блока управления, информационную выходную шину 18 второй группы ключей, счетчик количества единиц кода 19, имеющего информационную выходную шину 20, первый сумматор 21 по модулю шесть с выходной шиной 22 и вто1837329 рой сумматор 23 по модулю шесть, а также управляющие связи 24...27 с 1„.4 выходами блока управления для синхронизации работы соответственно узлов 19, 21, 23, 14; логический. элемент И 41, первые шесть входов которого подключены к соответствующим линиям входной шины устройства 6, седьмой вход обьединен с входом управления 27 узла сравнения с нулем 14, логический элемент YiJlM 42, первый вход которого соединен с выходом логического элемента И 41, а второй вход соединен со вторым выходом

43 узла сравнения с нулем 14, а выход подключен к первому управляющему входу блока управления 17, Блок управления содержит узел формирования адреса 28, с информационным выходом 29 третью группу ключей 30, блок ассоциативной памяти 31, шину 32 записи информации в блок ассоциативной памяти, выход признака совпадения 33 блока ассоциативной памяти, логический элемент 34

ИЛИ, имеющий два прямых и один инверсный входы и прямой выход 35, узел синхронизации 36, осуществляющий синхронизацию блока 31 по цепи 37, узла 28 по цепи 38, управляемый от шины управления ЭВМ по цепи 39 и сигнализирующий о выполнении шага вычислений в шину управления ЭВМ по цепи 40.

Узлы 2, 5, 14, 15, 21, 23, 30, 34 выполнены по стандартной схеме, блок 31 также по стандартной схеме с использованием известных инженерных решений, счетчик 19 реализован на основе известного решения, узел 28 реализован программно, а узел 36 реализован с использованием известных инженерных решений для реализации временной диаграммы.

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

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

Фремена, который определяется переходами (см. фиг. 4), необходимо знать количество единичных граничных точек изображения К относительно точки С и значение кода Фремена для предыдущего шага Ri-1, В этом случае для получения очередного значения кода надо вычислить выражение

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

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

С следующим образом: первая компонента

"О вектора — значение граничной с данной точкой С в направлении 1, вторая — в направлении 2 и так далее, шестая — в направлении

О.

В ОЗУ ЭВМ для каждого J-ro элемента

15 матрицы изображения хранится свое значение вектора (6, если С=1 = 0, если С=О

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

25 на элемент 41.

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

ЭВМ поступают исходные значения Ro и 60 (фиг. 2), Если Go Ф О, то на шине 10 появляется значение кода Go, которое подается в

30 счетчик 19 для подсчета единиц в коде. По управляющему сигналу, передаваемому по цепи 24 производится операция в блоке 19 по подсчету количества единиц в коде, результат по цепи 20 передается в сумматор

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

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

40 23, где по приходу управляющего сигнала по цепи 26 производится суммирование по модулю шесть с кодом, поступающим из регистра 5, Результаты суммирования по шине 7 поступают в узел формирования адреса 28

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

Фримена происходит как показано в таблице.

Например, если данная страница ОЗУ

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

Новое значение адреса сравнивается в блоке 31 с адресами, которые были там за1837329

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

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

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

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

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

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

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

1837329

10 О

Фиг.1

737

Фиг, Z

1837329

» 1 7 фиг. 9

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

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