Устройство для выделения связных фигур

о 11 474825

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ьоюз Советских

Социалистических

Республик

4(Ь (61) Дополнительное к авт. свид-ву (22) Заявлено 01.08.72 (21) 18122-" 7 18-24 (51) М. Кл. 6 061< 9/00 с присоединением заявки №

Государственный комитет

Совета Министров СССР по делам изобретений и открытий

Опубликовано 25.06.75. Бюллетень № 23

Дата опубликования описания 29.10.75 (53) УДК 681.327(088.8) (72) Авторы изобретения

О. А. Башкиров, А. M. Бланк и Б. М. Чудинович

Научно-исследовательский институт прикладной математики и кибернетики (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ СВЯЗНЫХ

ФИГУР

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

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

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

Обработка разветвленных и замкнутых кривых требует дополнительно нахождения узловых элементов или их размыкания.

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

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

ið элемента данной фигуры мож со перейтп по соседним одноцветным элементам. Выделение одноцветной связной фигуры состоит в том, что каждому элементу данной связной фигуры ставится в соответствие индекс (номер), одинаковый для всех элементов данной фигуры и отличный от индексов всех других фигур.

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

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

Предмет изобретения

25

1. ,".= — Осады

35 fJair.od к саседнил

ramanandi

59

Составитель И. Сидорова

Техред Т. Курилко Корректор А. Дзесова

Редактор А. Батыгин

Заказ 2591/9 Изд. № 836 Тираж 679 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, Я-35, Рвушская наб., д. 4/5

Типография, пр. Сапунова, д. 2 декса — ко второму входу схемы управления.

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

На чертеже представлена структурная схема одного канала предлагаемого устройства.

Канал обработки состоит из схемы 1 управления, выход которой соединен с первым регистром 2 индекса (все цепи передачи индексов показаны на чертеже двойными стрелками).

Выход первого регистра 2 индекса соединен со входом схемы 3 переиндексации своего канала и входами схем переиндексации соседних каналов. Схема 3 переиндексации имеет один вход от первого регистра индекса своего канала |и восемь входов от пер|вых регистров индекса соседних каналов. Выход схемы 3 переиндексации присоединен ко входу второго регистра 4 индекса своего канала, выход которого присоединен к одному из входов схемы управления; второй вход последний является входом устройства для данного канала. На этот вход поступает сигнал от фоторецептора: 1 — если клетка черная, Π— если клетка белая, Устройство работает в несколько тактов.

Вначале на первые регистры 2 индекса через схему 1 управления заносятся начальные индексы (номера) черных клеток, например, возрастающие слева направо и сверху вниз. В следующий такт Т, схемы 3 переиндексации сравнивают индекс клетки своего канала, если она черная, с индексами соседних черных клеток и передают минимальный индекс на второй регистр индекса.

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

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