УСТРОЙСТВО ДЛЯ ОТСЛЕЖИВАНИЯ КОНТУРОВ ДВУМЕРНЫХ ОБЪЕКТОВ Российский патент 1995 года по МПК G06K9/00 

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

Известно устройство для кодирования контуров двумерных объектов на прямоугольном растре, содержащее блок управления, блок коммутации, блок обработки, линии связи, шину данных, шину адреса [1]
Недостаток этого устройства его конструктивная сложность и неспособность кодировать контура на триангональных растрах.

Наиболее близким к предлагаемому по технической сущности является устройство для отслеживания контуров двумерных объектов, содержащее блок управления, блок коммутации, регистр, блок обработки, линии связи, шину данных, шину управления, шину адреса [2]
Недостаток устройства конструктивная сложность и низкое быстродействие, неспособность обрабатывать триангональные растры.

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

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

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

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

На фиг.1 изображена общая структура устройства; на фиг.2 структура блока управления; на фиг. 3 блок обработки; на фиг.4 показан вариант реализации дешифратора, на иг. 5 фрагмент изображения на триангональном растре.

Все элементы и узлы, входящие в состав предлагаемого устройства, стандартны (например, серии N К155). Дешифратор также реализован на стандартных элементах. При этом первые информационные входы блока обработки 1 и регистра кода предыдущего шага 3 объединены и образуют входную шину 6 устройства, информационный выход блока обработки 1 образует шину 7, связанную с информационными входами блока управления 2, группы ключей 4 и вторым информационным входом регистра кода предыдущего шага 3, выход 8 которого подключен к второму информационному входу блока обработки 1, первый 9, второй 10 и третий 11 управляющие входы которого подключены к соответствующим выходам блока управления 2, первый управляющий вход 12 которого подключен к соответствующему выходу блока обработки 1, четвертый 13 и пятый 14 управляющие выходы блока управления 2 подключены к первым управляющим входам соответственно регистра кода предыдущего шага 3 и группы ключей 4, второй управляющий вход 15, шестой 16 и седьмой 17 управляющие выходы блока управления 2 подключены к входной шине управления 18, а адресный выход 19 блока управления образует соответствующий выход устройства.

Блок управления 2 включает узел формирования адреса 20, входом которого является информационный вход 7 блока, узел ассоциативной памяти 21, первый информационный вход которого подключен к выходу 25 узла формирования адреса 20, второй информационный вход 19 подключен к выходу узла коммутации 22 и соединен с адресным выходом блока. Информационный вход узла коммутации соединен с выходом 25 узла формирования адреса 20, а управляющий вход 26 соединен с выходом узла ассоциативной памяти 21 и инверсным входом элемента ИЛИ 24, прямой вход 12 которого является первым управляющим входом блока, а выход 16 шестым управляющим выходом блока. Первый 9, второй 10, третий 11, четвертый 13 и пятый 14 управляющие выходы генератора синхроимпульсов 23 образуют соответствующие выходы блока, шестой 17 управляющий выход является седьмым управляющим выходом блока, седьмой 27 и восьмой 28 выходы генератора синхроимпульсов образуют управляющие входы узла формирования адреса 20 и узла ассоциативной памяти 21, а управляющий вход генератора синхроимпульсов 23 образован вторым управляющим входом блока управления.

Блок обработки 1 состоит из дешифратора 29, реверсивного счетчика по модулю шесть 30, сумматора по модулю шесть 31, выход 7 которого является информационным выходом блока, а первый вход соединен с выходом 3 реверсивного счетчика по модулю шесть 30, а второй с первым информационным выходом 33 дешифратора 29, второй 34 и третий 35 информационные выходы которого являются соответственно первым и вторым информационными входами реверсивного счетчика 30 по модулю шесть, третий информационный вход которого образован линиями шины 8 второго информационного входа блока. Информационный вход 6 дешифратора 29 является информационным входом блока обработки, управляющий выход 12 дешифратора 29 является управляющим выходом блока обработки, а первый 9, второй 10, третий 11 управляющие входы блока обработки являются соответственно управляющими входами дешифратора 29, реверсивного счетчика 30 и сумматора 31 по модулю шесть.

При этом дешифратор 29 включает полный дешифратор 36 на три входа, информационный вход которого 6 является информационным входом блока обработки, а управляющий вход 9 первым управляющим входом блока, первый (соответствующий нулевому начальному коду) выход является управляющим выходом блока обработки, второй, третий и пятый выходы подключены к входам первого элемента И 37, четвертый, шестой и седьмой выходы к входам второго элемента И 38, выходы которых образуют первые два информационных выхода 33, 34, а восьмой выход полного дешифратора 36 образует третий информационный выход 35 узла 29.

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

Реализуется выполнение эвристического алгоритма выделения контура двумерного объекта на триангональном растре.

Особенности представления и обработки изображений показаны на фиг.5.

Для того, чтобы задать координаты любого элемента изображения (треугольного пиксела) необходимо указать три координаты Х,Y,Z. Например, координаты точки С_о (см.фиг.5) соответственно равны X_co 5, Y_co 2, Z_co 2. Соответственно можно получить и координаты остальных пикселов изображения объекта. Следовательно, будем говорить, что плоское изображение может быть описано трехмерной бинарной матрицей размерностью n х n х n. Если известны два соседних элемента контура изображения, например, С_о и С₁, то этот факт можно закодировать по Фримену следующим образом: O C 3 т.е. переход по одному из шести направлений кодируется одной из цифр 0,5, в частности переход от точки С_о к точке С₁ кодируется цифрой 3, а от точки С₁ к точке С_о цифрой 0.

У каждого из пикселов имеется при соседних, имеющих общую сторону (границу). Следовательно, если пиксел изображения принадлежит контуру, то перейти можно к одному из трех соседей. Если задано первоначальное значение кода R_i-1 ∈0,1,5} и известно количество соседних данному пикселу элементов изображения, принадлежащих объекту К ≅ 3, то очередное значение кода Фримена вычисляется по формуле:
R_i= (1)
Все компоненты этих выражений шестиричные числа, а суммирование и вычитание осуществляются по модулю шесть.

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

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

= где (С) содержимое пиксела изображения, помеченного С.

По шине управления 18 от ЭВМ поступают сигналы управления (см.фиг.1 и 2), по цепи 15 запускают узел синхронизации 23, который выдает управляющий импульс по цепи 13 в регистр 3 и по цепи 9 в узел 36 (см.фиг.4).

При этом по шине данных (ШД) 6 из ОЗУ ЭВМ последовательно поступают исходные значения R_o и G_o (см.фиг.1). Если G ≠ 0, то по одной из связей 33, 34 или 35 поступает сигнал в реверсивный счетчик 30 по модулю шесть (при двух или трех граничных единичных пикселах) или на сумматор 31 по модулю шесть, где при наличии управляющего сигнала 10 осуществляется суммирование (линия 34) или вычитание (линия 35) единицы в реверсивном счетчике, или при наличии управляющего сигнала 11 в сумматоре происходит сложение R_i-1 с константой равной трем. Результаты вычислений по шине 7 поступают в узел формирования адреса 20 (УФА) (см.фиг.2). Особенности устройства УФА определяются типом ОЗУ ЭВМ. В частности, для ОЗУ типа 3D основными элементами УФА являются дешифратор и три реверсивных счетчика, в которые предварительно записываются базовые адреса. В соответствии с вычисленным значением кода Фримена, как показано в таблице, происходит модификация адреса.

Новое значение адреса и кода Фримена сравниваются в блоке 21 с адресами и кодами, которые были там записаны, т.е. адресами границ информационного массива (и адресами предыдущих точек контура, если это не первый шаг). Если такое совпадение имеет место, т.е. мы вышли на границу изображения (или замкнули петлю по контуру в случае несовпадения адресов или двух различных шагов), то наличие нулевого выходного сигнала на линии 26 позволяет через логический элемент 24 и цепь 16 сигнализировать в ЭВМ об окончании выделения контура. На этот же элемент поступает сигнал и от узла 36 по линии 12 для прерывания программы выделения контура в случае выхода либо на фоновую часть изображения, либо захода внутрь объекта.

Если совпадения в блоке 21 не происходит, то единичный сигнал на выходе по цепи 26 открывает группу ключей 22 и в блоке 21 происходит запись очередного адреса, который одновременно выдается в шину адреса ЭВМ для считывания очередного значения G_j.

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

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

Среднее время задержки обработки информации по прототипу:
t_{зад.прототип} t_или + t_u + t_сч + 2t_см + t_ап, где t_или время задержки элемента ИЛИ;
t_и среднее время задержки элемента И;
t_cч и t_см cреднее время задержки счетчика и сумматора соответственно;
t_ап время задержки в узле ассоциативной памяти,
Представим t_сч t_или + n ˙ t_и, где n 6 (так как счетчик по модулю шесть).

Подставим в исходное выражение
t_{зад.прототип} t_или + t_и + t_или + 6t_и +
+ 2t_см + t_ап
Время задержки для предложенного устройства:
t_{зад.предл} t_или + t_и + t_сч + t_см
Отсюда эффективность предлагаемого блока обработки:
Э ;
Э ;
Например, применительно для серии К 155 среднее время задержки для элементов И и ИЛИ t_и t_или 10 нс; для сумматоров t_cм 50 нс; для узла ассоциативной памяти t_ап 70 нс.

Отсюда эффективность предлагаемого блока обработки:
Э 1,7
Кроме того, эффективность предлагаемого устройства выражается в возможности реализации функции вычисления очередного кода контура двумерного объекта на триангональном растре за счет изменения структуры блока обработки и связей в блоке управления.

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

УСТРОЙСТВО ДЛЯ ОТСЛЕЖИВАНИЯ КОНТУРОВ ДВУМЕРНЫХ ОБЪЕКТОВ, содержащее блок обработки, блок управления, регистр кода предыдущего шага, группу ключей, выходы которых образуют информационный выход устройства, первый информационный вход блока обработки соединен с первым входом регистра кода предыдущего шага и образует информационный вход устройства, а информационный выход блока обработки соединен с информационными входами ключей группы, блока управления и вторым входом регистра кода предыдущего шага, выход которого соединен с вторым информационным входом блока обработки, а первый, второй и третий выходы блока управления соединены соответственно с первым, вторым и третьим управляющими входами блока обработки, управляющий выход которого соединен с первым входом блока управления, четвертый и пятый выходы которого соединены соответственно с управляющими входами регистра кода предыдущего шага и ключей группы, второй вход и шестой, седьмой выходы блока управления соединены с соответствующими входами-выходами устройства, а адресный выход блока управления соединен с выходом адреса устройства, причем блок управления содержит узел формирования адреса, узел ассоциативной памяти, коммутатор, генератор синхросигналов, элемент ИЛИ, выход которого является шестым выходом блока управления, информационный вход узла формирования адреса является информационным входом блока управления, а выход подключен к информационному входу коммутатора и первому входу узла ассоциативной памяти, выход которого соединен с инверсным входом элемента ИЛИ и управляющим входом коммутатора, выход которого подключен к адресному выходу блока управления и второму входу узла ассоциативной памяти, прямой вход элемента ИЛИ является первым входом блока управления, вход пуска генератора синхросигналов является вторым входом блока управления, выходы с первого по пятый генератора синхросигналов являются соответствующими выходами блока управления, шестой и седьмой выходы генератора синхросигналов соответственно соединены с синхронизирующими входами узла формирования адреса и узла ассоциативной памяти, восьмой выход генератора синхросигналов является седьмым выходом блока управления, отличающееся тем, что блок обработки содержит дешифратор, реверсивный счетчик по модулю шесть, сумматор по модулю шесть, выход которого является информационным выходом блока обработки, первый вход сумматора по модулю шесть соединен с выходом реверсивного счетчика по модулю шесть, а второй вход сумматора по модулю шесть соединен с первым информационным выходом дешифратора, второй и третий информационные выходы которого являются соответственно первым и вторым информационными входами реверсивного счетчика по модулю шесть, третий информационный вход которого соединен с вторым информационным входом блока обработки, информационный вход дешифратора является первым информационным входом блока обработки, управляющий выход дешифратора является управляющим выходом блока обработки, а первый, второй и третий управляющие входы блока обработки являются соответственно управляющими входами дешифратора, реверсивного счетчика по модулю шесть, сумматора по модулю шесть.