Устройство для селекции изображений объектов

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК яи 606 К 9/3 САНИЕ ИЗОБРЕТЕНИ Ы с ш ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИРИ ГКНТ СССР ОРСКОМУ СВИДЕТЕЛЬСТ(46) 30,01,92.Бюл. 3 Ф 41711 Таганрогский радиотехнический институт им. В.Д.Калмыкова(56) Гимельфарб Г.Л, Комплексная обработка информации о сцене, Киев: ИК АН УССР,1976,Яшида М, Обучаемая система машинного зрения для распознавания сложных промышленных деталей. Труды междун.конференц. по искусств интеллекту. М.:ВИНИТИ, 1975. Изобретение относится к технической кибернетике и вычислительной техике и может применяться в распознавающих и классифицирующих системах роботов. Цель изобретения - повышение быстродействия устройства. На фиг, 1 представлена схема предлагаемого устройства; на фиг. 2 - схема блока выделения первой строки иэображения; на фиг. 3 - схема блока перезаписи изображения; на,фиг. 4 - схема блока управления; на фиг. 5-9 - схемы, поясняющие работу устройства.Устройство содержит первую группу сдвиговых регистров 1, вторую группу сдвиговых регистров 2, буферный регистр 3, блок 4 выделения первой строки (изображения), блок 5 перезаписи (изображения), блок 6 управления, первую группу элементов И 7 и первую группу элементов ИЛИ 8.Блок выделения первой строки изображения (фиг. 2) содержит вторую группу эле 5 Ц, 1709358 А 1(54) УСТРО БРАЖЕНИ (57) Изобре кибернетик может прим мах, Цель и родействи введением блока пер элементов позволяет о на изображ ИСТВО ДЛЯ СЕЛЕКЦИИ ИЗОЙ ОБЬЕКТОВтение относится к технической е и вычислительной технике И еняться в распознающих систезобретения - повышение быстя устройства - достигается блока выделения первой строки, езаписи изображения, группы ИЛИ и группы элементов И, что существлять селекцию обьектов ении. 9 ил. ментов И 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, третий э 1 емент И 31, четвертый элемент И 32, пятый элемент И 33, шестой эелемент И 34, с фвьмой элемент И 35, восьмой элемент И 3:, первый элемент ИЛИ 37, второй элемент ,.1 И 38, третий элемент ИЛИ 39, четвертый1709358ФсСоставитель А. Глотов Редактор,А, Лежнина Техред М.Моргентал Корректор М. Демчик Заказ 428 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 4/5Производственно-издательский комбинат "Патент, г, Ужгород, ул,1 ад цн, 101буФерного регистра средний ряд) при выделении первого изображения. При этом показана только первая часть процедуры; 15 30 50 55 элемент ИЛИ 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 управления, связанный со сдвиговым входом 5 10 20 25 35 40 первой группы регистров 1, кроме того, этот импульс поступает на вход второго элемента 25 задержки и задержанный этим элементом задержки на время сдвига в группе регистров 1 передается через первый элемент ИЛИ 37 на второй выход блока 6 управления, связанный со сдвиговым входом сдвиговых регистров второй группы 2. Таким образом, каждый импульс, выработанный генератором 18 тактовых импульсов и прошедший через первый элемент И 29, вызывает сначала сдвиг в первой группе регистров 1, затем сдвиг во второй группе регистров 2. Направление сдвигов определяется состоянием третьего триггера 23, который, находясь в исходном нулевом состоянии, обеспечивает сдвиг вверх. Количество сдвигов подсчитывается первым счетчиком 19, выполненным па схеме реверсивного счетчика.При каждом импульсе сдвига изображения в регистрах первой группы 1 смещаются на строку вверх, при этом верхняя строка перезаписывается в нижней строке. При очередном сдвиге в регистре сцен, когда в верхней строке регистра появится первая строка сцены, содержащая хотя бы одну единицу, произойдет запись в буферный регистр 3. При этом запишется крайняя слева единица этой строки и все последующие, связанные с ней, Такая запись обеспечивается блоком 4 выделения первой строки. Рассмотрим работу этого блоком. Группы его входов связаны с прямыми и инверсными выходами триггеров верхней строки первой группы регистров 1. Обозначим прямые и инверсные выходы триггеров верхнейстроки этих регистров х 1, х 1, х 2, х 2 хп, хп. Так как входы элементов второй группы элементов И 9 связаны с инверсными выходами триггеров верхней строки данных регистров, на выходах элементов И 9 образуются конъюнкции х 2, х 1, хзх 2 х 1 хп - 1хзх 2 х 1, Так как выходы элементов И 9 соединены с вторыми входами элементов четвертой группы элементов И 11, первые входы которых подключены к прямым выходам триггеров верхней строки регистров первой группы, на выходах элементов И 11 имеются сигналы, описываемые конъюнкциями соответственно слева направо: х 2 х 1, хзх 2 х 1,хвхв хзх 2 х 1. Эта структура связей обеспечивает передачу нд выходы элементов И 11 и далее на выходы элементов второй группы элементов ИЛИ 13 и, значит, на первые входы пятой группы элементов И 12 первой слева единицы, Пусть, например, первая слева единица встречается в третьей позиции. Тогда на первом входе левого элемента пятой группы элементов И 12 имеетсяО, так как х 1=0. На первом входе второго элемента И 12 имеется О, так как в конъюнкции х 2 х 1, передаваемой с выхода элемента И 11 через элемент ИЛИ 13, член хг=О. На первом входе третьего элемента И 12 имеется единица, так как в конъюнкции хзх 2 х 1 все члены равны единицам. На первом входе четвертого и всех последующих элементов пятой группы элементов И 12 имеются нули, так в соответствующих конъюнкциях Х 4 ХЗХ 2 Х 1 Х 5 Х 4 ХЗХ 2 Х 1ХХп ХЗХ 2 Х 1 ЧЛЕН хз=О. Элементы И 12 открываются по вторым входам тактовым импульсом, задержанным третьим элементом 26 задержки на время окончания сдвига в регистрах первойгруппы 1 и прошедшим через третий элемент И 31, открытый по второму входу потенциалов с инверсного выхода второго триггера 22. Таким образом, наличие элементов второй и четвертой групп элементов И 9 и 11 обеспечивает прием первой слева единицы,Появление единицы на выходе элемента второй группы элементов ИЛИ 13 обеспечит появление единицы на выходе следующего элемента ИЛИ 13, если на прямом выходе соответствующего триггера верхней строки группы регистров 1 имеется единица. Таким образом, все единицы, следующие за первой единицей, будут переданы на выходы элементов пятой группы .элементов И 12. Однако, если последовательность единиц прерывается нулем, то на выходе соответствующего элемента третьей группы элементов И 10 имеется нуль и, значит, имеется нуль на выходе соответствующего элемента второй группы элементов ИЛИ 13, Это вызовет появление нуля на выходах всех последующих элементов ИЛИ 13,Таким образом, импульсы разрешенияприема, подаваемые в буферный регистр 3 через элементы первой группы элементов ИЛИ 8, поступят в те разряды буферного регистра 3, которым соответствует непрерывная последовательность единиц, начинающаяся слева. Поскольку на информационные входы буферного регистра поступает вся строка, то в этом регистре зафиксируется непрерывная последовательность единиц, начинающаяся слева.Далее под воздействием импульса навходе "Сдв,И", задержанного вторым элементом 25 задержки на время сдвига в ре гистрах первой группы 1, переключенияблока 4 и приема в буферный регистр 3 и снимаемого с выхода первого элемента ИЛИ 37, информация из буферного регистра 3 перезаписывается в нижнюю строку второй группы регистров 2. На фиг, 6 а показано содержание регистров первой группы, второй группы и буферного регистра после приема сцен и, передпервым сдвигом: на фиг. 6 б - содержание5 этих регистров после сдвига в регистрахпервой группы, записи в буферный регистри сдвига в регистрах второй группы, Приэтом сцена в регистре сцен сдвинулась настроку вверх.10 Как.следует из предыдущего описания,в регистрах второй группы 2 перезаписывались лишь компоненты первого изображения. Единичный компонент 17 второгоизображения в этих регистрах не записы 15 вался, хотя и находился в одной строке скомпонентами 1 и 2.Далее процедура выделения первооизображения выполняется следующим образом,20 После того, как в нижней строке второйгруппы регистров 2 оказалась строка, содержащая хотя бы одну единицу, третий элемент ИЛИ 39, входы которого связаны спрямыми выходами триггеров этой нижней25 строкивыдает единичный сигнал, устанавливающий второй триггер 22.в единичноесостояние, Второй триггер 22, перейдя вединичное состояние, будет в дальнейшемподдерживать второй элемент И 30 откры 30 тым по второму входу, а третий элемент И31 - закрытым по второму входу, обеспечивая передачу тактовых импульсов, снимаемых с выхода первого элемента И 29 изадержанных третьим элементом 26 задер 35 жки, на вход блока 5,К моменту подачи очередного тактовогоимпульса в нижней строке группы регистров2 хранится предыдущая строка выделяемо- .го изображений. Единичные компоненты40 этой строки, снимаемые с прямых выходовтриггеров и подаваемые на вторую группувходов блока 5 через элементы третьейгруппы элементов ИЛИ 14, элементы восьмой группы элементов И 17, элементы пер 45 вой группы элементов ИЛИ 8 поступают насинхровходы триггеров буферного регистра3, разрешая прием компонентов новой строки в триггеры буферного регистра, одноименные с триггерами нижней строки50 регистров второй группы 2, где хранятсяединичные компоненты. Компоненты пред"идущей строки подаются также на соседниеэлементы ИЛИ 14, разрешая прием тех компонентов новой строки, которые являются55 соседними с одноименными единичнымикомпонентами предыдущей строки.Наличие элементов шестой группы элементов И 15 обеспеивает разрешение записи компонентов новой строки, еолиразрешена запись с вреднего слева компо 170935810 15 нента новой строки и если этот компонентравен единице. Аналогично наличие элементов седьмой группы элементов И 16обеспечивает разрешение записи компонента новой строки, если разрешена записьсоседнего справа компонента новой строкии если этот Компонент равен единице.Таким образом, при очередном сдвиге врегистрах первой группы 1 в буферный регистр 3 перезаписываются последовательности единичных компонентов очереднойстроки, если хотя бы один из этих компонентов является одноименным или соседним сединичным компонентом предыдущей строки (фиг. 6 б - 7 г).После того, как первая строка, содержащая единичные компоненты, зафиксирована в регистрах 2 (фиг, 6 б), компоненты 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 предыдущей строки.Количество сдвигов подсчитываетсяпервь 1 м счетчиком 19, на вход управлениясложением которого поступает единичныйпотенциал с инверсного выхода третьеготриггера 23. Содержимое первого счетчика19 после каждого сдвига также приводитсяна фиг, 6. 20 25 30 35 40 45 50 55 Процедура сдвигов вверх изображений в регистрах 1 и 2 продолжается до тех пор, пока после очередного сдвига в нижней строке регистров 2 не зафиксируются все нули, как, например, после седьмого сдвига (фиг, 72). Это свидетельствует о достижении локального минимума. Даже полный сдвиг по кольцу в одном направлении (вверх) не обеспечивает передачи всех компонентов изображения в регистры 2. В частности, компоненты 5, 11. 13 и 16 первого изображения оказались не переданными. Для обеспечения передачи всех компонентов одного изображения выполняется многократное изменение направления сдвигов.Рассмотрим эту процедуру,При фиксации локального минимума,когда в нижней строке регистров 2 имеются только нули, на выходе третьего элемента ИЛИ 39, входы которого связаны с прямыми выходами триггеров нижней строки регистров 2, возникает логический ноль, что приводит к появлению логической единицы на выходе первого инвертора 41, При этом шестой элемент И 34 откроется по третьему входу. Поскольку шестой элемент И 34 в этому моменту был уже открыт по второму входу потенциалом с прямого выхода второго триггера 22 и по четверто- . му входу потенциалом с второго инвертора 42, то он пропустит тактовый импульс, приведший к достижению локального минимума, на счетный вход третьего триггера 23 и на счетный вход второго счетчика 20. Задержка импульса пятым элементом 28 задержки нужна для того, чтобы переход третьего триггера 23 произошел после подачи им-пульса на первый вход пятого элемента И ЗЗ, что исключает появление лишнего им- пульса сдвига на выходе первого элемента ИЛИ 37. Переход третьего триггера в единичное состояние вызовет установление режима вычитания в первом счетчике 19 и подачу управляющего единичного потенциала на четвертый выход блока 6 управления, что обеспечит направление сдвига вниз в регистрах 1 и 2,При подаче следующего после изменения направления сдвига тактового импульса выполняется кольцевой сдвиг изображений вниз в регистрах 1. При этом в буферный регистр 3 не будет записана информация, так как в нижней строке регистров 2 зафиксиоованы нули и блок 5 разрешения на прием не выдает. Результат - содержимое реги-, стров 1 и 2 и буферного регистра 3 - показан на фиг. 8 а. Далее к моментам подачи очередных тактовых импульсов в нижней строке регистров 2 имеется по крайней мере одна единица, что обеспечивает разрешение передачи информации из верхней строки регистров 1 в буферной регистр 3, При этом в буферный регистр 3 и затем в регистрах 2 будут перезаписываться дополнительно компоненты первого изображения, 5 ранее, при выполнении сдвигов вверх, не записанные. Для обеспечения такой записи регистры 2 выполнены особым образом. Итак, при сдвиге вниз в буферный регистр 3 и затем в регистры 2 перезапишутся ранее 10 не записанные компоненты иэображения. Для рассматриваемого примера это компоненты 11 (фиг. 86) и 5 (фиг. 9 а).Таким образом, при сдвиге вниз в буферный регистр 3 и затем в регистр 2 изо бражений перезаписываются ранее не записанные компоненты изображения. Для рассматриваемого примера это компоненты 11 (фиг, 8 б) и 5 (фиг. 9 а). Содержимое первого счетчика 19 при сдвиге вниз уменьшается. 20После ряда сдвигов вниз изображение в регистрах 2 займет такое положение, когда в нижней строке регистров 2 будут только нули (фиг, 9 в). При этом третий элемент ИЛИ 39 выдаст ноль, первый инвертор 41 выдаст еди ницу. Пятый элемент И 33 будет открыт по второму входу первым инвертором 41, а по третьему входу - единичным потенциалом с прямого выхода третьего триггера 23. Последний тактовый импульс, который привел 30 к появлению нулевой строки в нижней стро-ке регистров 2, задержанный четвертым элементом задержки 27 на время сдвига в регистрах 2, пройдет через открытый пятый элемент И 33, через первый элемент ИЛИ 37 35 и поступит на сдвиговый вход регистров 2. Этим восстановится соответствие расположения изображения в регистрах 2 и соответствующего ему иэображения в регистрах 1 (фиг. 9 г). Последний тактовый импульс, при ведший к появлению нулевой строки в нижней строке регистров 2, дополнительно задержится пятым элементом 28 задержки на время сдвига и затем, поступив на счетный вход третьего триггера 23, переведет 45 его в нулевое состояние; обеспечивающее в дальнейшем направление сдвига вверх в регистрах 1 и 2, Таким образом, в результате первой серии сдвигов вверх и первой серии сдвигов вниз в регистрах 2 окажутся 50 зафиксированными все компоненты изображения, расположенные выше первого локального минимума. Продолжающееся поступление тактовых импульсов вызовет вторую серию сдвигов вверх и достижение 55 второго локального минимума; Для рассматриваемого примера при этом в регистрах 2 перезапишутся компоненты 13 и 16, После достижения второго локального минимума направление сдвигов вновь иэменится и начнется выполнение второй серии сдвигов вниз. Процедура выполнения пар серий сдвигов вверх и вниз повторяется по числу локальных минимумов. При этом каждое изменение направления сдвигов подсчитывается вторым счетчиком 20, Таким образом, каждой серии сдвигов соответствует увеличение содержимого счетчика 20 на единицу, а каждой паре серий сдвигов - увеличение содержимого счетчика на два, так что содержимое счетчика равно удвоенному числу отработанных локальных минимумов. Точное число локальных минимумов для возможных иэображений, составляющих сцену, не известно. Поэтому заранее обуславливается максимально возможное число локальных минимумов. С выходами второго счетчика 20, составляющими код удвоенного максимально возможного числа локальных минимумов, связаны входы восьмого элемента И 36. Например, если принять максимальное число локальных минимумов равным 5, то входы восьмого элемента И 36 соответствуют коду 1010, т.е, с входами восьмого элемента И 36 связан прямой выход четвертого разряда, инверсный выход третьего разряда, прямой выход второго разряда и инверсный выход первого разряда второго счетчика 20, Таким образом, после выполнения последней серии сдвигов вниз, когда состояние второго счетчика станет 1010, восьмой элемент И 36 выдаст единицу. Эта единица поступит через четвертый элемент .ИЛИ 40 на нулевой вход второго триггера 22, который, перейдя в нулевое состояние, перестанет поддерживать открытый для тактовых импульсов первый элемент И 29, вследствие чего сдвиги, в регистрах прекратятся. Единичный сигнал с выхода восьмого элемента И 36, будучи инвертированным вторым инвертором 42, станет поддерживать пятый элемент И ЗЗ закрытым по четвертому входу. Единичный сигнал с выхода восьмого элемента И 36.поступит на девятый выход блока 6 управления, т.е, на вторые входы первой группы элементов И,7, первые входы которых связаны с прямыми выходами соответствующих триггеров регистров 2, а выходы подключены к входам установки в ноль триггеров регистров 1, Паявление единицы на выходе восьмого элемента И 36 приведет к установлению в ноль техтриггеров регистров 1, которые соответствуют триггерам регистров 2, где зафиксированы единичные компоненты первого изображения, т.е. в регистрах 1 будет стерто первое иэображение, Единичный сигнал с выхода восьмого элемента И 36 будет подан также на выход "Готово"блока 6 управле 1709358 12ния, свидетельствуя об окончании выделения,первого изображения. Компоненты изображения выдаются на первой группе выходов регистров 2,После некоторого интервала времени, требуемого для обработки первого изображения, приемник изображений выдаст сигнал на вход "Продолжение". Сигнал на входе "Продолжение" вызовет те же процедуры, что и сигнал на входе "Пуск", за исключением принятия сцены. При этих процедурах будет выделено второе изображение. Аналогичные процедуры выполняются до тех пор, пока не будут выделены и выданы из регистров 2 все изображения, При этом.все изображения в регистрах 1 будут стерты. Формула изобретения, Устройство для селекции изображений объектов; содержащее две группы сдвиговых регистров, буферный регистр и блок управления, о т л и ч а ю щ е е с я тем, что, с целью повышения бустродействия, в него введены блок выделения первой строки, блок перезаписи изображения, группа элементов ИЛИ и группа элементов И, информационный вход сдвиговых регистров первой группы является информационным входом устройства, входы "Сброс" сдвиговых регистров первой группы соединены с выходами элементов И группы, первый выход блока управления соединен со входами "Сброс" сдвиговых регистров второй группы, второй выход блока управления - с первым управляющим входом сдвиговых регистров второй группы, третий и четвертый выходы блока управления - с вторым и третьим управляющими входами регистров сдвига второй группы и с первым и вторым управляющими входами регистров сдвига первой группы, пятый и шестой выходы 5 блока управления соединены с управляющими входами блока выделения первой строки изображения и блока перезаписи изображения, седьмой и восьмой выходы - с третьим и четвертым управляющими 10 входами регистров сдвига первой группы,девятый выход. блока управления - с первыми входами элементов И группы, первые выходы сдвиговых регистров второй группы - с вторыми входами элементов группы и 15 являются информационным выходом устройства, информационные входы сдвиговых регистров второй группы - с выходом буферного регистра, вторые входы сдвиговых регистров второй группы - с информа ционным входом блока управления и спервым информационным входом блока перезаписи изображения, первые выходы сдвиговых регистров первой группы соединены с первыми информационными входа ми буферного регистра, блока выделенияпервой строки и с вторым информационным входом блока перезаписи изображения, вторые выходы сдвиговых регистров первой группы соединены с вторыми ин формационными входами буферного регистра и блока выделения первой строки изображения, выходы блока выделения первой строки изображения - с первь 1 ми входами элементов ИЛИ группы, выходы 35 блока перезаписи изображения - с вторымивходами элементов ИЛИ группы, выходы которых соединены с третьими информационными входом буферного регистра,