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

сл

С

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

Целью изобретения является повыше- ие надежности отслеживания контура объ- ста на гексагональном растре.

На фиг. 1 представлена блок-схема устройства; на фиг. 2 - конструктивное использование блока обработки; на фиг. 3 - вариант конструктивного исполнения блока у|фавления.

Устройство включает блок управления 1J первую группу ключей 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 и вто00

Сл VI CJ

ГО

ю

рой сумматор 23 по модулю шесть, а также управляющие связи 24...27 с 1 ...4 выходами блока управления для синхронизации работы соответственно узлов 19, 21, 23, Т4, логический элемент И 41, первые шесть входов которого подключены к соответствующим линиям входной шины устройства 6, седьмой вход объединен с входом управления 27 узла сравнения с нулем 14. логический элемент ИЛИ 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), необходимо знать количество единичных граничных точек изображения К относительно точки С и значение кода Фремена для предыдущего шага RM. В этом случае для получения очередного значения кода надо вычислить выражение

RM-RI+ К + А,(1)

где - константа.

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

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

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

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

5 матрицы изображения хранится свое значение вектора

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

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

При этом по шине данных (ШД) б по СЗУ ЭВМ поступают исходные значения R0 и G0 (фиг. 2). Если Go 0, то на шине 10 появляется значение кода Go, которое подается в

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

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

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

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

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

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

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

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

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

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

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

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

6

шд

10 Фиг. I

е.З.

f

И .

3

Фиг.4

f