Устройство для селекции изображений объектов Советский патент 1992 года по МПК G06K9/36 

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

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

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

Устройство содержит первую группу сдвиговых регистров 1, вторую группу сдвиговых регистров 2, буферный регистр3, блок 4 выделения первой строки (изображения), блок 5 перезаписи (изображения), блок 6 управления, первую группу элементов И 7 и первую группу элементов ИЛИ 8.

Блок выделения первой строки изображения (фиг. 2) содержит вторую группу элементов И 9, третью группу элементов И 10, четвертую группу элементов И 11, пятую группу элементов И 12 и вторую группу элементов ИЛИ 13.

Блок перезаписи изображения (фиг. 3) содержит третью группу элементов ИЛИ 14, шестую группу элементов И 15, седьмую группу элементов И 16, восьмую группу элементов И 17.

Блок 6 управления (фиг. 4) содержит генератор 18 тактовых импульсов, первый счетчик 19, второй счетчик 20, первый триггер 21, второй триггер 22, третий триггер 23, первый элемент 24 задержки, второй элемент 25 задержки, третий элемент 26 задержки, четвертый элемент 27 задержки, пятый элемент 28 задержки, первый элемент И 29, второй элемент И 30, третий элемент И 31, четвертый элемент И 32, пятый элемент И 33, шестой эелемент И 34, сзаьмой элемент И 35, восьмой элемент И 3:, первь и элемент ИЛИ 37, второй элемент k.. 1И 38, третий элемент ИЛИ 39, четвертый

элемент ИЛИ 40, первый инвертор41 и второй инвертор 42.

На фиг. 5 показана сцена, совокупность двух изображений, Под изббраженмем понимается множество единичных компонентов, связанных между собой. На растре фиг. 5 компоненты 1-16 составляют первое изображение, компоненты 17-28 - второе изображение. На фиг. 6 последовательно изображены состояния сдвиговых регистров первой группы (нижний ряд), (сдвиговых регистров второй группы (верхний ряд) и буферного регистра (средний ряд) при выделении первого изображения. При этом показана только первая часть процедуры;

Работа устройства начинается с подачи на вход Пуск запускающего импульса. Этот импульс передается на седьмой выход блока 6 управления, связанный с разрешающим входом сдвиговых регистров первой группы 1. Одновременно с запускающим импульсом на группу входов устройства, связанную, с первой .группой входов этих регистров, подаются компоненты всех изображений, т.е. исходная сцена. При этом триггеры верхней и нижней строк регистров заполняются нулями. Запускающий импульс подается также на вход второго элемента ИЛИ 38. Импульс с выхода элемента ИЛИ 38 передается на нулевые выходы второго и третьего триггеров 22 и23, на установочные входы первого и второго счетчиков 19 и 20. Импульс с выхода элемента ИЛИ 38 передается также на первый выход блока 6 управления, связанный с установочным входом сдвиговых регистров второй группы 2. Импульс с выхода элемента ИЛИ 38 поступает также на первый вход четвертого элемента ИЛИ 40, выход которого связан с нулевым входом первого триггера 21, и на вход первого элемента 24. задержки, выход которого соединен с единичным входом первого триггера 21. В результате первый, второй и третий 21, 22 и 23, первый и второй счетчики 19 и 20 и вторая группа регистров 2 устанавливаются в исходные нулевые состояния. Задержанный первым элементом 24 задержки на время переключения узлов 1, 2, 19, 20, 21, 22 м 23 импульс с выхода второго элемента ИЛИ 38 поступает на единичный вход первого триггера 21, устанавливая его в единичное состояние. При этом первый элемент И 29 открывается по второму входу, пропуская на выход тактовые импульсы с непрерывно работающего генератора 18 тактовых импульсов.

Импульсы с выхода первого элемента И 29 поступают на восьмой выход блока 6 управления, связанный со сдвиговым входом

первой группы регистров 1. кроме того, этот импульс поступает на вход второго элемента 25 задержки и задержанный этим элементом задержки на время сдвига в группе регистров 1 передается через первый элемент ИЛИ 37 на второй выход блока 6 управления, связанный со сдвиговым входом сдвиговых регистров второй группы 2. Таким образом, каждый импульс, выработанный генератором 18 тактовых импульсов и прошедший через первый элемент И 29, вызывает сначала сдвиг в первой группе регистров 1, затем сдвиг во второй группе регистров 2. Направление сдвигов определяется состоянием третьего триггера 23, который, находясь в исходном нулевом состоянии, обеспечивает сдвиг вверх. Количество сдвигов подсчитывается первым счетчиком 19, выполненным по схеме реверсивного счетчика.

При каждом импульсе сдвига изображения в регистрах первой группы 1 смещаются на строку вверх, при этом верхняя строка перезаписывается в нижней строке. При очередном сдвиге в регистре сцен, когда в верхней строке регистра появится первая строка сцены, содержащая хотя бы одну единицу, произойдет запись в буферный регистр 3. При этом запишется крайняя слева единица этой строки и все последующие, связанные с ней. Такая запись обеспечивается блоком 4 выделения первой строки. Рассмотрим работу этого блоком. Группы его входов связаны с прямыми и инверсными выходами триггеров верхней строки первой группы регистров 1. Обозначим прямые и инверсные выходы Tpj/irrepoe верхней

строки этих регистров X1,xi, Х2, Х2, , ... Хп,

Хп. Так как входы элементов второй группы элементов И 9 связаны с инверсными выходами триггеров верхней строки данных регистров, на выходах элементов И 9 образуются конъюнкции )2, XI, ХЗХ2Х1 Хп-1

... xaxax. Так как выходы элементов И 9 соединены с вторыми входами элементов четвертой группы элементов И 11, первые входы которых подключены к прямым выходам триггеров верхней строки регистров первой группы, на выходах элементов И 11 имеются сигналы, описываемые конъюнкциями соответственно слева направо; X2Xi, ХЗХ2Х1, ... XnXn-1 ... хзх2)Г1. Эта структура связей обеспечивает передачу на выходы элементов И 11 и далее на выходы элементов второй группы элементов ИЛИ 13 и, значит,, на первые входы пятой группы элементов И 12 первой слева единицы. Пусть, например, первая слева единица встречается в третьей позиции. Тогда на первом входе левого элемента пятой группы элементов И 12 имеется

О, так как . На первом входе второго элемента И 12 имеется О, так как в конъюнкции Х2Х1. передаваемой с выхода элемента И 11 через элемент ИЛИ 13, член . На первом входе третьего элемента И 12 имеется единица, так как в конъюнкции хзх2Х1 все члены равны единицам. На первом входе четвертого и всех последующих элементов пятой группы элементов И 12 имеются нули, так в соответствующих ксжъю кциях

Х4)ЗХ2Х1 Х5Х4ХЗХ2Х1 ... ХпХп-1 ... ХЗХ2Х1 ЧЛеН

. Элементы И 12 открываются по вторым входам тактовым импульсом, задержанным треты/1м элементом 26 задержки на время окончания сдвига в регистрах первой группы 1 и прошедшим через третий элемент И 31, открытый по второму входу потенциалов с инверсного выхода второго триггера 22. Таким образом, наличие элементов второй и четвертой групп элементов И 9 и 11 обеспечивает прием первой слева единицы.

Появление единицы на выходе элемента второй группы элементов ИЛИ 13 обеспечит появление единицы на выходе следующего элемента ИЛИ 13, если на прямом выходе соответствующего триггера верхней строки группы регистров 1 имеется единица. Таким образом, все единицы, следующие за первой единицей, будут переданы на выходы .элементов пятой группы .элементов И 12. Однако, если последовательность единиц прерывается нулем, то на выходе соответствующего элемента третьей группы элементов И 10 имеется нуль и, значит, имеется нуль на выходе соответствующего элемента второй группы элементов ИЛИ 13, Это вызовет появление нуля на выходах всех последующих элементов ИЛИ 13.

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

Далее под воздействием импульса на входе Сдв.И, задержанного вторым элементом 25 задержки на время сдвига в регистрах первой группы 1, переключения блока 4 и приема в буферный регистр 3 и снимаемого с выхода первого элемента ИЛИ 37, информация из буферного регистра 3 перезаписывается в нижнюю строку второй группы регистров 2.

На фиг. 6а показано содержание регистров первой группы, второй группы и буферного регистра после приема сцен и, перед первым сдвигом; на фиг. 66 - содержание

этих регистров после сдвига в регистрах первой группы, записи в буферный регистр и сдвига в регистрах второй группы. При том сцена в регистре сцен сдвинулась на строку вверх.

0 Как .следует из предыдущего описания, в регистрах второй группы 2 перезаписывались лишь компоненты первого изображения. Единичный компонент 17 второго изобр ажения в этих регистрах не записывался, хотя и находился в одной строке с компонентами 1 и 2.

Далее процедура выделения первого изображения выполняется следующим образом.,

0 После того, как в нижней строке второй группы регистров 2 оказалась строка, содержащая хотя бы одну единицу, третий элемент ИЛИ 39, входы которого связаны с прямыми выходами триггеров этой нижней

5 строки выдает единичный сигнал, устанавливающий второй триггер 22 в единичное состояние. Второй триггер 22, перейдя в единичное состояние, будет в дальнейшем поддерживать второй элемент И 30 открытым по второму входу, а третий элемент И 31 -закрытым по второму входу, обеспечивая передачу тактовых импульсов, снимаемых с выхода первого элемента И 29 и задержанных третьим элементом 26 задер5 жки, на вход блока 5.

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

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

0 регистров второй группы 2, где хранятся единичные компоненты. Компоненты предыдущей строки подаются также на соседние элементы ИЛИ 14. разрешая прием тех компонентов новой строки, которые являются

5 соседними с одноименными единичными компонентами предыдущей строки.

Наличие элементов шестой группы элементов И 15 oбecпe ивaeт разрешение записи компоне «тов новой строки, если разрешена запись с педнего слева компонента новой строки и если этот компонент равен единице. Аналогично наличие элементов седьмой группы элементов И 16 обеспечивает разрешение записи компонента новой строки, если разрешена запись соседнего справа компонента новой строки и если этот Компонент равен единице.

Таким образом, при очередном сдвиге в регистрах первой группы 1 в буферный регистр 3 перезаписываются последовательности единичных компонентов очередной строки, если хотя бы один из этих компонентов является одноименным или соседним с единичным компонентом предыдущей строки (фиг. 6б-7г).

После того, как первая строка, содержащая единичные компоненты, зафиксирована в регистрах 2 (фиг. 66), компоненты 1 и 2 ее, содержащиеся в этих регистрах, разрешают запись при втором сдвиге в регистрах первой группы компонентов 3 и 4 в буферный регистр, так как эти компоненты составляют непрерывную последовательность, элементы которой одноименны с единичными компонентами предыдущей строки. В частности, компонент 3 является одноименным компоненту 1, а компонент 4 компоненту 2.

Компонент 5 и буферный регистр не записывается, так как не входит в непрерывную последовательность единичных компонентов 3 и 4. Результат второго сдвига содержимое регистров 1 и 2 и буферного регистра 3 - показан на фиг. 6в. При третьем сдвиге компоненты 3 и 4, составляющие на этот момент предыдущую строку, разрешают запись компонентов 6, 7, 8 и 9, так как эти компоненты составляют непрерывную последовательность единичных компонентов, один из которых, например компонент 6, является одноименным с,единичным компонентом 3. Результат - содержимое регистров 1, 2 и 3 - показан на фиг. 6г.

Результаты последующих сдвигов показаны на фиг. 6-7 а-г, д, е, ж, з, Интерес представляет шестой сдвиг. К этому моменту предыдущую строку составляет компонент 12, который разрешает.запись компонентов 14 и 15 каксоставляющих непрерывную последовательность единичных компонентов, один из которых, а именно компонент 15, является соседним с одноименным единичным компонентом 12 предыдущей строки.

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

Процедура сдвигов вверх изображений в регистрах 1 и 2 продолжается до тех пор, пока после очередного сдвига в нижней строке регистров 2 не зафиксируются все

нули, как, например, после седьмого сдвига (фиг. 72). Это свидетельствует о достижении локального минимума. Даже полный сдвиг по кольцу в одном направлении (вверх) не обеспечивает передачи всех компонентов

0 изображения в регистры 2. В частности, компоненты 5, 11. 13 и 16 первого изображения оказалмсь не переданными. Для обеспечения передачи всех компонентов одного изображения выполняется многократное изменение направления сдвигов. Рассмотрим эту процедуру.

При фиксации локального минимума, когда в нижней строке регистров 2 имеются только нули, на выходе третьего элемента

0 ИЛИ 39, входы которого связаны с прямыми выходами триггеров нижней строки регистров 2, возникает логический ноль, что приводит к появлению логической единицы на выходе первого инвертора 41. При

5 этом шестой элемент И 34 откроется по третьему входу. Поскольку шестой элемент И 34 в этому моменту был уже открыт по второму входу потенциалом с прямого выхода второго триггера 22 и по четвертому входу потенциалом с второго инвертора 42, то он пропустит тактовый импульс, приведший к достижению локального минимума, на счетный вход третьего триггера 23 и на счетный вход второго счетчика 20. Задержка импульса пятым элементом 28 задержки нужна для того, чтобы переход третьего триггера 23 произошел после подачи импульса на первый вход пятого элемента И 33, что исключает появление лишнего импульса сдвига на выходе первого элемента ИЛИ 37. Переход третьего триггера в единичное состояние вызовет установление режима вычитания в первом счетчике 19 и подачу управляю.щего единичного потенциала на четвертый выход блока 6 управления, что обеспечит направление сдвига вниз в регистрах 1 и 2,

При подаче следующего после изменения направления сдвига тактового импульса

0 выполняется кольцевой сдвиг изображений вниз в регистрах 1. При этом в буферный регистр 3 не будет записана информация, так как в нижней строке регистров 2 зафиксированы нули и блок 5 разрешения на прием

5 не выдает. Результат - содержимое реги-. стров 1 и 2 и буферного регистра 3 - показан на фиг. 8а. Далее к моментам подачи очередных тактовых импульсов в нижней строке регистров 2 имеется по крайней мере одна единица, что обеспечивает разрешение передачи информации из верхней строки регистров 1 в буферной регистр 3, При этом в буферный регистр 3 и затем в регистрах 2 будут перезаписываться дополнительно компоненты первого изображения, ранее, при выполнении сдвигов вверх, не записанные. Для обеспечения такой записи регистры 2 выполнены особым образом. Итак, при сдвиге вниз в буферный регистр 3 и затем в регистры 2 перезапишутся ранее не записанные компоненты изображения. Для рассматриваемого примера это компоненты 11 (фиг. 86) и 5 (фиг. 9а).

Таким образом, при сдвиге вниз в буферный регистр 3 и затем в регистр 2 изображений перезаписываются ранее не записанные компоненты изображения. Для рассматриваемого примера это компоненты 11 (фиг. 86) и 5 (фиг. 9а). Содержимое первого счетчика 19 при сдвиге вниз уменьшается.

После ряда сдвигов вниз изображение в регистрах 2 займет такое положение, когда в нижней строке регистров 2 будут только нули (фиг. 9в). При этом третий элемент ИЛИ 39 выдаст ноль, первый инвертор 41 выдаст единицу. Пятый элемент И 33 будет открыт по второму входу первым инвертором 41, а по третьему входу - единичным потенциалом с прямого выхода третьего триггера 23. Последний тактовый импульс, который привел к появлению нулевой строки в нижней строке регистров 2, задержанный четвертым элементом задержки 27 на время сдвига в регистрах 2, пройдет через открытый пятый элемент И 33, через первый элемент ИЛИ 37 и поступит на сдвиговый вход регистров 2. Этим восстановится соответствие расположения изображения в регистрах 2 и соответствующего ему изображения в регистрах 1 (фиг. 9г). Последний тактовый импульс, приведший к появлению нулевой строки в нижней стро ке регистров 2, дополнительно задержится пятым элементом 28 задержки на время сдвига и затем, поступив на счетный вход третьего триггера 23, переведет его в нулевое состояние , обеспечивающее в дальнейшем направление сдвига вверх в регистрах 1 и 2. Таким образом, в результате первой серии сдвигов вверх и первой серии сдвигов вниз в регистрах 2 окажутся зафиксированными все компоненты изображения, расположенные выше первого локального минимума. Продолжающееся поступление тактовых импульсов вызовет вторую серию сдвигов вверх и достижение второго локального минимума; Для рассматриваемого примера при этом в регистрах 2 перезапишутся компоненты 13 и 16. После достижения второго локального минимума направление сдвигов вновь изменится и начнется выполнение второй серии сдвигов вниз. Процедура выполнения пар серий сдвигов вверх и вниз повторяется по числу локальных минимумов. При этом каждое изменение направления сдвигов подсчитывается вторым счетчиком 20. Таким образом, каждой серии сдвигов соответствует увеличение содержимого счетчика 20 на единицу, а каждой паре серий сдвигов 0 увеличение содержимого счетчика на два, так что содержимое счетчика равно удвоенному числу отработанных локальных минимумов. Точное число локальных минимумов для возможных изображений, составляющих

5 сцену, неизвестно. Поэтому заранее обуславливается максимально возможное число локальных минимумов. С выходами второго счетчика 20, составляющими код удвоенного максимально возможного числа локальных минимумов, связаны входы восьмого элемента И 36. Например, если принять максимальное число локальных минимумов равным 5, то входы восьмого элемента 1/1 36 соответствуют коду 1010, т.е. с входами восьмого элемента И 36 связан прямой выход четвертого разряда, инверсный выход третьего разряда, прямой выход второго разряда и инверсный выход первого разряда второго счетчика 20. Таким образом, после выполнения последней серии сдвигов вниз, когда состояние второго счетчика станет 1010, восьмой элемент И 36 выдаст единицу. Эта единица поступит через четвертый элемент .ИЛИ 40 на нулевой вход

5 второго триггера 22, который, перейдя в нулевое состояние, перестанет поддерживать открытый для тактовых импульсов первый элемент И 29, вследствие чего сдвиги , в регистрах прекратятся. Единичный сигнал

0 с выхода восьмого элемента И 36, будучи инвертированным вторым инвертором 42, станет поддерживать пятый элемент И 33 закрытым по четвертому входу. Единичный сигнал с выхода восьмого элемента И

5 36. поступит на девятый выход блока 6 управления, т.е. на вторые входы первой группы элементов И .7, первые входы которых связаны с прямыми выходами соответствующих триггеров регистров 2, а выходы

0 подключены к входам установки в ноль триггеров регистров 1. Появление единицы на выходе восьмого элемента И 36 приведет к установлению в ноль техтриггеров регистров 1, которые соответствуют

5 триггерам регистров 2, где зафиксированы единичные компоненты первого изображения, т.е. в регистрах 1 будет стерто первое изображение. Единичный сигнал с выхода восьмого элемента И 36 будет подан также на выход Готово блока 6 управления, свидетельствуя об окончании выделениапервого изображения. Компоненты изображения выдаются на первой группе выходов регистров 2.

После некоторого интервала времени, требуемого для обработки первого изображения, приемник изображений выдаст сигнал на вход Продолжение. Сигнал на входе Продолжение вызовет те же процедуры, что и сигнал на входе Пуск, за исключением принятия сцены. (При этих процедурах будет выделено второе изображение. Аналогичные процедуры выполня-. ются до тех пор, пока не будут выделены и выданы из регистров 2 все изображения. При этом все изображения в регистрах 1 будут стерты.

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

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

-с третьим и четвертым управляющими входами регистров сдвига первой группы,

девятый выход блока управления - с первыми входами элементов И группы, первые выходы сдвиговых регистров второй группы

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

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

/

LI in I I I IN LJLJM III

Фиг.6

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

ЕГ

т

m