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

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

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

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

Устройство содержит блок 1 управления, блок 2 коммутации, шины 3 и 4, регистр 5, шины 6 и 7, блок 8 обработки, шины 9 и 10, связь 11, шины 12 и 13, схему 14 сравнения с нулем, коммутатор 15, связь 16 и 17, шину 18, узел 19 ассоциативной памяти, связь 20, счетчик 21, шину 22, сумматор 23, шину 24, сумматор 25 по модулю восемь, шину 26, сумматор 27 по модулю восемь, связи 28-33, узел 34 формирования адреса, шину 35, коммутатор 36, узел 37 ассоциативной памяти, шину 38, связь 39, элемент 40 ИЛИ, связь 41, генератор 42 синхросигналов связи 43-46.

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

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

1 2 3

О С 4

765,

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

Rt R,.,4- К+А,

(1)

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

Если для каждой точки С иметь вектор G граничных значений размерностью восемь, то определяя количество единиц в нем, получаем К. Расположив граничные точки в векторе С следующим образом: нервая компонента вектора - зи.ачение граничной с данной точкой С в направлении 1, вторая - в направлении 2 и так далее, восьмая - в направлении 0. Для четырех значений G 01110001, G 01011100, 0 00010111, 0 11000101 А 100. Для остальных значений G А 011.

В памяти ЭВМ для каждого j-ro элемента матрицы изображения хранится свое значение вектора Gj /Gy, если С 1 Ъ , если .

По щине 12 от ЭВМ поступают сигналы управления в блок 1 управления, по связи 45 запускают генератор 42, который выдает управляющий импульс по связи 11 в регистр 5 и по связи 33 - в схему 14.

При этом на шине 6 из памяти ЭВМ поступают исходные значения Ro и GO. Если GO ф О, то на щине 18 появляется значение кода GO, которое подается для сравнения с кодами (G/- G), записанными в узле 19 и для подсчета единиц в коде в счетчик 21.

По управляющим сигналам, передаваемым по связи 28 и 29, производится соответствующие операции в узле 19 и счетчике 21. Если G равен одному из кодов, записанных в узле 19, то на выходе 20 появляется логическая «1, иначе «О. По сигналу 30 осуществляется арифметическое сложение кода, соответствующего значению К с шины 22 с признаком, поступающим по связи 20. Результаты суммирования по щине 24 передаются в сумматор 25, где по управляющему сигналу, поступающему по связи 31, складываются с константой Oil. Результаты сложения по модулю восемь сумматора 25 подаются по шине 26 в сумматор 27, где по управляющему сигналу, поступающему по связи 32 производите суммирование по модулю восемь с кодом, поступающим из регистра 5. Результаты суммирования поступают в узел 34. Особенности узла 34 определяются типом памяти ЭВМ. В частности, Q основными элементами узла 4 могут быть дешифратор и два реверсивных счетчика, в которые предварительно записываются базовые адреса, а подача сигналов модификации адреса в соответствии с вычисленным значением кода Фримена происходит 5 как показано в таблице.

0

5

Например, если данная страница памяти имеет емкость 1К, а базовый адрес равен 01000, 10000, то после модификации адреса

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

Если же совпадения в узле 37 не происходит, то единичный сигнал на выходе 30 открывает коммутатор 36 и в узел 37 осуществляется запись очередного адреса, который одновременно выдается в шину адреса ЭВМ для считывания очередного значения О/.

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

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

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

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

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

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

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

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

Фиг. 2

Изобретение относится к вычислительной технике. Целью изобретения является повышение быстродействия. Устройство содержит блок 1 управления, блок 2 коммутации, шины 3, 4, регистр 5, шины 6, 7, блок 8 обработки, шины 9, 10, линию связи 11, шины 12, 13. В состав блока 8 обработки входят схема сравнения, коммутатор, узел ассоциативной памяти, счетчик, сумматор, два сумматора по модулю восемь, линии связи. 1 з.п. ф-лы, 4 ил. 1 табл. (Л оо со ел ОО

VUi. 3

Фиг л