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

 

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

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

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

PECnYEiflVlH

Л0 „, 1314353 A 1 (51)4 G06F 1566

i . 1

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4036784/24-24 (22) 17.03.86 (46) 30.05.87. Бюл. № 20 (72) В. В. Храмов, Г. И. Васильев, А. В. Лярский и В. А. Вдовиченко (53) 681.325(088.8) (56) Опубликованная заявка Франции № 2555003, кл. G 06 F 15/66, 1985.

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

1088029, кл. G 06 К 11/00, 1982. (54) УСТРОЙСТВО ДЛЯ ОТСЛЕЖИВАНИЯ КОНТУРОВ ДВУМЕРНЫХ ОБЪЕКТОВ (57) Изобретение относится к вычислительной технике. Целью изобретения является повышение быстродействия. Устройство содержит блок 1 управления, блок 2 коммутации, шины 3, 4, регистр 5, шины 6, 7, блок 8 обработки, шины 9, 10, линию связи 11, шины 12, 13. В состав блока 8 обработки входят схема сравнения, коммутатор, узел ассоциативной памяти, счетчик, сумматор, два сумматора по модулю восемь, линии связи.

1 з п. ф лы, 4 ил. 1 табл.

1314353

1-й реверсивный

Кои <рриие— нв (во связи 7) -й реверсивный счетчик счетчик

R„=R; + К+А, 40

3 4 3

0 0

0 0

4

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

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

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

Устройство содержит блок 1 управления, блок 2 коммутации, шины 3 и 4, регистр 5, шины 6 и 7, блок 8 обработки, шины 9 и

10, связь 11, шины 12 и 13, схему 14 сравнения с нулем, коммутатор 15, связь 16 и 17, шину 18, узел !9 ассоциативной памяти, связь 20, счетчик 21, шину 22, сумматор 23, шину 24, сумматор 25 по модулю восемь, шину 26, сумматор 27 по модулю восемь, связи 28 — 33, узел 34 формирования адреса, шину 35, коммутатор 36, узел 37 ассоциативной памяти, шину 38, связь 39, элемент

40 ИЛИ, связь 41, генератор 42 синхросигналов связи 43 — 46.

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

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

1 2 3

О С 4

7 6 5, необходимо знать количество единичных граничных точек изображения К относительно точки С и значение кода Фримена для предыдущего шага R; 1. В этом случае для получения очередного значения кода надо вычислить выражение где А — константа, все компоненты этого выражение трехзначные двоичные числа, а суммирование осуществляется по модулю восемь.

Если для каждой точки С иметь вектор

G граничных значений размерностью восемь, то определяя количество единиц в нем, получаем К. Расположив граничные точки в векторе С следующим образом: первая компонента вектора — значение граничной с данной точкой С в направлении 1, вторая— в направлении 2 и так далее, восьмая в направлении О. Для четырех значений G =

= 01110001, G = 01011100, G == 00010111, G4= 11000101 А= 100. Для остальных значени" G A= 011.

В памяти ЭВМ для каждого j-ãî элемента матрицы изображения хранится свое значение вектора GJ- JGJ, если С==!

10, если C= — О.

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

При этом на шине 6 из памяти ЭВМ поступают исходные значения Кв u Gp. Если

Go -ф О, то на шине 18 появляется значение кода Go, которое подается для сравнения с кодами (G; — G ), записанными в узле 19 и для подсчета единиц в коде в счетчик 21.

По управляющим сигналам, передаваемым по связи 28 и 29, производится соответствующие операции в узле 19 и счетчике 21.

Если G равен одному из кодов, записанных в узле 19, то на выходе 20 появляется логическая «1», иначе «О». По сигналу 30 осуществляется арифметическое сложение кода, соответствук>щего значению К с шины

22 с признаком, поступающим по связи 20.

Результаты суммирования по шине 24 пере20 даются в сумматор 25, где по управляющему сигналу, поступающему по связи 31, складываются с константой О!1. Результаты сложения по модулю восемь сумматора 25 подаются по шине 26 в сумматор 27, где по управляющему сигналу, поступающему по связи 32 производится суммирование по модулю восемь с кодом, поступающим из регистра 5. Результаты суммирования поступают в узел 34. Особенности узла 34 определяются типом памяти ЭВМ. В частности, основными элементами узла 4 могут быть дешифратор и два реверсивных счетчика, в которые предварительно записываются базовые адреса, а подача сигналов модификации адреса в соответствии с вычисленным значением кода Фримена происходит как показано в таблице.

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

01000, 10000, то после модификации адреса

1314353

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

На этот же элемент поступает сигнал и от схемы 14 по связи 17 для прерывания программы выделения контура, в случае выхода на фоновую часть изображения.

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

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

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

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

1314353

j; П

2 зй

2t й5 моиг, 3

Дгйг и

Составитель А. Жеренов

Реда кто р A. Доли нич Техред И. Верес Корректор А. Обручар

Заказ 2007 50 Тираж 673 Г!одписное

ВНИ1г!Г1И Государственного комитета СССР но делам изобретений и открытий

I 1 3035, .Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Г1роизводствснно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4