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

 

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

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

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

Недостаток этого устройства - его конструктивная сложность и неспособность кодировать контура на смешанном прямоугольном растре.

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

Недостаток устройства - неспособность обрабатывать изображения на смещенных прямоугольных растрах.

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

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

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

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

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

Все элементы и узлы, входящие в состав предлагаемого устройства, в том числе и дешифратор адреса, стандартны (например, серии К 155).

При этом устройство включает (фиг. 1): блок управления 1, блок коммутации 2, регистр 5 и блок 8 обработки вектора элемента изображения, первый и второй входы которого соединены соответственно с информационным входом устройства 6 и выходом 9 регистра 5, первый информационный вход которого соединен с информационным входом устройства 6, второй информационный вход регистра соединен с первым выходом 7 блока 8 обработки вектора элемента изображения, с информационным входом блока коммутации и информационным входом блока управления 1, с первого по девятый выходы которого соединены соответственно с управляющим входом 3 блока коммутации 2, входом записи 11 регистра 5, первым 24, вторым 25, третьим 26 и четвертым 27 синхровходами блока 8 обработки вектора элемента изображения, с адресным выходом устройства 13, выходом окончания выделения контура 35 и тактовым выходом устройства 40. Выход 4 блока коммутации 2 соединен с информационным выходом устройства, вход запуска устройства 39 является входом запуска блока управления. При этом блок 8 обработки вектора элемента изображения (фиг. 2) содержит коммутатор 15, информационный вход 6 которого является первым входом блока 8 обработки вектора элемента изображения и соединен с информационным входом схемы сравнения с нулем 14 и первым входом элемента И 41, второй вход и выход 43 которого соединены соответственно с четвертым синхровходом 27 блока и первым входом первого элемента ИЛИ 42, второй вход 44 и управляющий выход 17 которого соединены соответственно со вторым выходом схемы сравнения с нулем и вторым выходом блока 8, выход 20 счетчика 19 соединен с информационным входом первого сумматора 21 по модулю шесть, выход 22 которого соединен с первым информационным входом второго сумматора 23 по модулю шесть, второй информационный вход 9 и выход 7 которого являются вторым входом блока и седьмым выходом блока 8 обработки элемента изображения соответственно, второй 25 и третий 26 синхровходы которого являются соответственно синхровходами первого 21 и второго 23 сумматоров по модулю шесть, управляющий вход 16 и первый выход 18 коммутатора 15 соединен соответственно с выходом схемы сравнения с нулем 14 и информационным входом счетчика 19, синхровход которого соединен с первым синхровходом 24 блока 8 обработки вектора элемента изображения.

Блок управления 1 (фиг. 3) содержит узел формирования адреса 28 с информационным входом 7, являющимся информационным входом блока управления 1, информационным выходом 29, соединенным с информационным входом группы ключей 30 и входом признаков блока ассоциативной памяти 31, вход записи которого 32 подключен к адресному выходу 13 устройства и выходу группы ключей 30, управляющий вход 33 которой подключен к выходу блока ассоциативной памяти 31 и первому входу второго элемента ИЛИ 34, второй вход которого подключен к управляющему выходу 17 блока 8 обработки вектора элемента изображения, а выход 35 является выходом окончания выделения контура. Узел синхронизации 36 осуществляет синхронизацию блока ассоциативной памяти 31 по цепи 37, узла формирования адреса 28 по цепи 38 и управляется по цепи 39 от центральной ЭВМ и сигнализирует по цепи 40 в нее по шине управления 12 об окончании очередного шага вычислений.

Узел формирования адреса 28 (фиг. 4) включает дешифратор 45, третий 46, четвертый 47 и пятый 48 элементы ИЛИ, первый 49 и второй 56 реверсивные счетчики, выходы которых образуют соответственно старшее и младшее слово адреса очередного вектора элемента изображения для информационного выхода 29. При этом вход полного дешифратора 45 на три входа соединен с информационным входом 7 узла формирования адреса 28, а используемые с нулевого по пятый выходы дешифратора подключены следующим образом. Нулевой 50, первый 51 и пятый 55 выходы соединены с первым, вторым и третьим входами третьего элемента 46 ИЛИ, первый 51 и второй 55 соединены соответственно с первым и вторым входами четвертого элемента ИЛИ 47, третий 53 выход соединен со вторым входом первого 49 реверсивного счетчика, четвертый 54 и пятый 55 выходы дешифратора подключены соответственно к первому и второму входам пятого элемента ИЛИ 48, выход которого 59 подключен ко второму входу второго реверсивного счетчика 56, первый вход которого подключен к выходу 58 четвертого элемента ИЛИ 47, а первый вход первого реверсивного счетчика 49 подключен к выходу 57 третьего элемента ИЛИ 46. Управляющие входы реверсивных счетчиков 49 и 56 подключены к синхровходу 38 узла формирования адреса 28.

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

Для того чтобы задать координаты любого элемента изображения (пиксела) необходимо указать пару целых чисел. Например, координаты точки C₀ (см. фиг. 5,б) соответственно равны X_c = 11, а Y_c = 2.

Аналогичным образом можно задать координаты и остальных пикселов изображения объекта. Следовательно, будем говорить, что плоское изображение на смешанном прямоугольном растре может быть описано, как и для обычного прямоугольного растра, двумерной матрицей размерностью n·m.

Если известны два соседних элемента контура изображения объекта C₀ и C₁, то этот факт можно закодировать по Фримену, как это показано на фиг 5,а, то есть как переход по одному из шести как переход по одному из шести направлений и представить одной из цифр 0...5, в частности переход от точки C₀ к точке C₁ кодируется цифрой 0, а обратно - цифрой 3.

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

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

В ОЗУ ЭВМ для каждого j-го элемента матрицы изображения хранится свое значение вектора: G_j = G_j, если (C) = 1 и G_j = 0, если (C) = 0, где (C) - содержимое пиксела изображения, помеченного C.

По шине управления 12 от ЭВМ (фиг. 1, 2) по линии 39 поступает сигнал на запуск узла синхронизации 36, который выдает управляющий импульс по цепи 27 шины 10 на схему сравнения с нулем 14 и элемент И 41, а также по линии 11 на вход разрешения записи регистра 5. При этом по шине данных 6 из ОЗУ ЭВМ последовательно поступают исходные значения R₀ (в регистр 5) и G₀ (в блок обработки вектора элемента изображения 8).

Если G₀ ≠ 0, то на выходе 16 схемы сравнения с нулем 14 появляется сигнал, разрешающий работу коммутатора 15, и это значение вектора через коммутатор 15 по связи 18 поступает в счетчик 19, где после подачи на него разрешающего сигнала по линии 24 формируется значение K₀, которое подается по связи 20 на первый сумматор по модулю шесть 21, где прибавляется константа 2 под управлением сигнала по линии 25, затем результат по связи 22 подается на второй сумматор по модулю шесть 23, на который также поступает значение R₀ по связи 9 и, по управляющему сигналу по линии 26 формируется значение R₁, которое по связи 7 поступает в регистр 5, блок коммутации 2 (и далее под управлением сигнала по линии 3 посредством связи 4 и шины данных 6 в ЭВМ) и блок управления 1, узел формирования адреса 28 при наличии управления по линии 38.

В узле формирования адреса значение кода Фримена R_i подается на вход полного дешифратора 45 на три входа, на одном из шести (шестой и седьмой выходы не используются) выходов (50 - 55) которого появляется сигнал, который непосредственно (линия 53) или через элементы ИЛИ 46, 47, 48 (структура связей узла пояснена таблицей и фиг. 5,а) подается на входы реверсивных счетчиков 49 и 56, в которых формируется индексная часть адреса очередного вектора элемента изображения G_i, хранимого в ОЗУ ЭВМ.

В устройстве предусматривается контроль за окончанием процедуры выделения контура, то есть если контур замыкается, дает петлю или выходит на границу растра. С этой целью имеется блок ассоциативной памяти 31, в который по связи 29, через группу ключей 30 и связь 32 и под управлением сигнала по линии 37 осуществляют запись координат (точнее их индексных частей) всех выявленных для текущего контура его точек. Группа ключей 30 управляется сигналом по линии 33. Такой сигнал подается из блока ассоциативной памяти 31 в случае отсутствия в ней последних вычисленных координат точки контура.

Кроме того, осуществляется контроль за сбоем процедуры выделения контура. При этом вычисленный в узле формирования адрес может сооветствовать либо точке вне объекта, либо внутри его. В первом случае вектор элемента изображения нулевой, что и фиксируется схемой сравнения с нулем 14 и по линии 44 подается на первый вход первого элемента ИЛИ 42. Во втором случае вектор элемента изображения полностью состоит из единиц, что и фиксируется элементом И 41 и по линии 43 подается на второй вход первого элемента ИЛИ 42, выход 17 которого совместно с сигналом от блока ассоциативной памяти при окончании выделения контура 33 подается на второй элемент ИЛИ 34, выход которого 35 через шину управления 12 обеспечивает сигнал в ЭВМ о факте завершения процедуры выделения контура.

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

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

Если расстояния между соседними пикселами в обычном прямоугольном растре отличается на (ортогональные и диагональные соседние пикселы), то для смещенного прямоугольного растра такое отличие составляет .

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

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

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6