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

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

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

Известно также устройство для распознавания образов по А.С. СССР № 486712. Данное устройство является наиболее близким по технической сущности и достигаемому эффекту к заявляемой группе изобретений и признано за прототип.

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

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

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

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

На фиг.1 представлено поле распознавания и модель распознанного изображения, состоящая из геометрических примитивов - первичных элементов.

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

На фиг.3 представлен преобразователь адреса, где 1, 2 и 3 - сумматоры.

На фиг.4 представлена схема сдвигового регистра адреса, где 1 - генератор тактовых импульсов ГТИ, 2 - инвертор, 3 - третий ключевой коммутатор, 4 - сдвиговый регистр конечного адреса, 5 - четвертый ключевой коммутатор, 6 - схема сравнения, 7 - сдвиговый регистр начального адреса, 8 и 9 - вторые ключевые коммутаторы, 10 - сдвиговые регистры адресов, 11 - генератор сдвиговых импульсов ГСИ.

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

На фиг.1 множество первичных элементов содержит четыре элемента: горизонтальный отрезок вдоль нижнего края ячейки распознавания, вертикальный отрезок вдоль левого края ячейки распознавания и два диагональных отрезка. Этого множества достаточно, чтобы для заданного масштаба и точности модели построить образ исследуемого объекта и записать в памяти вычислительного устройства. Закодируем рассмотренные отрезки соответственно буквами А, Б, В и Г:

Таким образом, весь объект декомпозируется на четыре типа первичных элементов: А, Б, В и Г.

Каждому элементу в поле распознавания ставится в соответствие пара ячеек, с которыми тем или иным образом соприкасается данный элемент. На фиг.1 ячейки пронумерованы слева направо и сверху вниз, первая ячейка имеет номер 0. Номера ячеек являются адресами первичных элементов изображения в поле распознавания. В зависимости от типа первичного элемента ему в соответствие ставится пара адресов по правилу, предназначенному для данного типа элемента. Правила перекодировки приведены в таблице.

Здесь а_н - адрес (номер) первой ячейки, образующей пару, а_к - адрес (номер) второй ячейки, образующей пару. В дальнейшем эти адреса будем называть адресом начала и адресом конца соответственно. Эти две ячейки тем или иным образом соединяются данным элементом: Х - номер текущей ячейки, в которой находится рассматриваемый элемент; L - длина горизонтальной стороны поля распознавания (на фиг.1 равно 10). Пример кодирования элементов парами адресов для изображения на фиг.1 показан ниже:

1 - A-2,3 2-Б-12,22 3-В-15,26 4-Г-46,54

Эти пары записываются каждая в свой регистр, соответствующий типу элемента. Для примера на фиг.1 таких регистров четыре. Общее число пар равно общему числу задействованных ячеек. Число пар в каждом регистре равно числу элементов данного типа в поле распознавания.

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

На следующем шаге производят следующее. Если а_ki оказывается равен а_i+1, то i-ю и i+1-ю пары объединяют так, что образуется новая пара, у которой а_н равен a_нi, а а_k равен a_ki+1. Аналогичные действия производят до тех пор, пока есть пары, которые можно объединять по указанному правилу. В результате исходное множество пар, соответствующих отдельным первичным элементам, преобразуется в множество пар, соответствующих протяженным отрезкам - фрагментам распознаваемого изображения. Для примера на фиг.1 отрезки типа Г в конечном итоге образуют фрагмент - протяженный отрезок, который кодируется парой 46, 72.

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

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

Устройство для осуществления способа, представленное на фиг.2, работает следующим образом.

С помощью устройства управления считыванием 1 происходит последовательная локализация сенсорного элемента 2 на ячейках поля распознавания. Это может быть механическое перемещение СЭ 2 по полю распознавания. В этом случае СЭ выполняется в виде считывающей головки. СЭ может быть выполнен в виде матрицы, ячейки которой расположены напротив поля распознавания. Каждую ячейку матрицы в этом случае можно рассматривать как элементарный сенсорный элемент, считывающий информацию всегда из одной ячейки поля распознавания. Устройство управления считыванием 1 в этом случае может последовательно опрашивать ячейки распознающей матрицы. В любом случае в каждый момент времени производится обработка элемента изображения в данной конкретной ячейке поля распознавания. Адрес этой ячейки подается на входы первых ключевых коммутаторов 4.

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

В общем случае преобразователь адреса может представлять собой пару сумматоров, на одни входы которых подается считанный адрес ячейки, а на другие - заданные константы. В результате на выходах сумматоров образуются пары значений адресов ячеек. На фиг.3 показаны преобразователи адреса для рассмотренного выше примера на фиг.1. Фрагмент А) соответствует типам элементов А, Б и В, а фрагмент Б) - типу Г. На фрагменте А) К может принимать значения 1, L и L+1 в зависимости от типа элементов (см. таблицу).

С выходов преобразователей адреса 5 (сумматоров 1, 2 и 3 на фиг.3) пары значений адресов ячеек а_н и а_к подаются на входы соответствующих сдвиговых регистров адреса 6.

Функциональная схема сдвиговых регистров адреса 6 показана на фиг.4.

Через ключевые коммутаторы 8 и 9 на входы 1 сдвиговых регистров конечного адреса 4 и начального адреса 7 соответственно поступают значения конечного и начального адресов ячеек пары, образованной в преобразователе адреса. Разрешающим сигналом является 1 такт от генератора тактовых импульсов 1 (см. диаграмму работы устройства на фиг.5). В результате в регистрах 4 и 7 записываются значения адресов пары ячеек. Данные регистры могут быть собраны из дискретных электронных элементов, в частности триггеров. При этом входы 1 являются установочными и служат для переключения регистров в соответствующие состояния. Входы 2 являются сдвиговыми. При подачи на них последовательности импульсов через сдвиговые выходы 3 информация передвигается в следующий справа регистр. С выходов 4 снимаются сигналы, соответствующие текущему состоянию данного регистра. Значения адресов могут быть закодированы двоичным кодом. Поданный на вход регистров код переключает их в соответствующее состояние, которое они сохраняют до следующего переключения.

Сдвиговые регистры адресов 10 аналогичны по своему устройству регистрам 4 и 7. В совокупности сдвиговые регистры адресов 10 представляют собой сдвиговый регистр, в котором хранятся пары адресов ячеек.

После записи очередной пары адресов производится сравнение с помощью схемы сравнения 6 значения адреса в первом сдвиговом регистре адреса 10 и в регистре начального адреса 7. Схема сравнения может быть выполнена с использованием логических конъюнкторов. При положительном результате сравнения на входе ключевого коммутатора 5 с выхода схемы сравнения 6 появляется разрешение для прохождения сигнала. Другое разрешение поступает с 2 тактом от ГТИ 1 (см. фиг.5). После чего происходит перезапись значения с выхода 4 регистра конечного адреса 4 в первый сдвиговый регистр адреса 10. При этом на сдвиговые входы сигналы не подаются, и в других регистрах адреса 10 значения не меняются. Изменяется только значение первого регистра. Тем самым новая последовательность не образуется, а изменяется значение последней записанной пары, т.е. длина хранимого фрагмента изображения.

При отрицательном результате сравнения в схеме сравнения 6 ключевой коммутатор 5 закрыт, напротив открывается через инвертор 2 ключевой коммутатор 3. Второй такт от ГТИ 1 запускает генератор сдвиговых импульсов 11, пакет импульсов с которого через открытый ключевой коммутатор 3 подается на вход 2 регистра конечного адреса 4. Количество импульсов в пакете равно удвоенному значению разрядности числа адреса ячейки. В результате по всему регистру сдвига от 4 до n-го 10 происходит сдвиг значений. Тем самым дописывается новая пара ячеек.

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

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

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