способ считывания и адресного кодирования графических изображений и устройство для его осуществления
Классы МПК: | G06K9/00 Способы и устройства для считывания и распознавания напечатанных или написанных знаков или распознавания образов, например отпечатков пальцев |
Автор(ы): | Стреж С.В. (RU) |
Патентообладатель(и): | Стреж Сергей Васильевич (RU) |
Приоритеты: |
подача заявки:
2001-03-01 публикация патента:
10.06.2004 |
Изобретение относится к области автоматики и вычислительной техники, а именно к устройствам формирования графических изображений. Его применение позволяет получить технический результат в виде экономии памяти вычислительного устройства. Этот результат достигается благодаря тому, что в память записывают адреса ячеек поля распознавания, содержащих первичные элементы изображения, и коды типов первичных элементов изображения, находящихся в соответствующих ячейках, полученные адреса ячеек и коды типов первичных элементов изображения группируют по типам первичных элементов, осуществляют перекодирование результата распознавания в пары адресов ячеек, соединяемых данным первичным элементом, путем упорядочивания пар адресов ячеек в последовательности таким образом, что второй адрес предыдущей пары адресов ячеек совпадает с первым адресом последующей пары адресов ячеек, преобразовывают последовательности пар адресов ячеек в такие пары адресов ячеек, первым адресом которых являются первые адреса первых пар адресов ячеек из данной последовательности, а вторым - второй адрес последней пары адресов ячеек из данной последовательности. 2 с.п. ф-лы, 1 табл., 5 ил.
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5
Формула изобретения
1. Способ адресного кодирования графических изображений, в котором распознают первичные элементы изображения или геометрические примитивы в поле распознавания, отличающийся тем, что в память вычислительного устройства записывают адреса ячеек поля распознавания, содержащих первичные элементы изображения, и коды типов первичных элементов изображения, находящихся в соответствующих ячейках, полученные адреса ячеек и коды типов первичных элементов изображения группируют по типам первичных элементов, по функциям преобразования, заданным для каждого типа первичных элементов изображения, осуществляют перекодирование результата распознавания в пары адресов ячеек, соединяемых данным первичным элементом, путем упорядочивания пар адресов ячеек в последовательности таким образом, что в каждой последовательности второй адрес предыдущей пары адресов ячеек совпадает с первым адресом последующей пары адресов ячеек, преобразовывают последовательности пар адресов ячеек в такие пары адресов ячеек, первым адресом которых являются первые адреса первых пар адресов ячеек из данной последовательности, а вторым - второй адрес последней пары адресов ячеек из данной последовательности.2. Устройство считывания и адресного кодирования графических изображений, содержащее сенсорный элемент, соединенный с классификатором, отличающееся тем, что дополнительно содержит первые ключевые коммутаторы, первые входы которых соединены с выходами классификатора, устройство управления считыванием, один выход которого соединен с сенсорным элементом, а другой - со вторыми входами первых ключевых коммутаторов, также содержит сумматоры, первые входы которых соединены с выходами соответствующих первых ключевых коммутаторов, на вторые входы сумматоров поданы соответствующие константы, также содержит n сдвиговых регистров адреса, сдвиговый выход каждого i-го регистра, кроме n-го, соединен со сдвиговым входом i+1-го сдвигового регистра адреса, также содержит сдвиговый регистр начального адреса, сдвиговый выход которого подключен к сдвиговому входу первого сдвигового регистра адреса, а сдвиговый вход соединен со сдвиговым выходом сдвигового регистра конечного адреса, выход первого сдвигового регистра адреса соединен с первым входом схемы сравнения, второй вход которой соединен с выходом сдвигового регистра начального адреса, а выход соединен с входом инвертора, выход которого соединен с первым входом третьего ключевого коммутатора, второй вход которого соединен с выходом генератора сдвиговых импульсов, а выход - со сдвиговым входом сдвигового регистра конечного адреса, вход генератора сдвиговых импульсов соединен с генератором тактовых импульсов, выход схемы сравнения соединен также с первым входом четвертого ключевого коммутатора, второй вход которого соединен с выходом сдвигового регистра конечного адреса, а третий вход соединен с генератором тактовых импульсов, выход четвертого ключевого коммутатора соединен с входом первого сдвигового регистра адреса, входы сдвиговых регистров начального и конечного адресов соединены с выходами вторых ключевых коммутаторов, первые входы которых соединены с выходами соответствующих сумматоров, а вторые входы соединены с выходом генератора тактовых импульсов.Описание изобретения к патенту
Изобретения относятся к области автоматики и вычислительной техники, а именно к устройствам формирования графических изображений.Известно устройство для выделения контура бинарного изображения по А. С. СССР № 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 равен aki+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 происходит сдвиг значений. Тем самым дописывается новая пара ячеек.Таким образом, совокупность существенных признаков изобретений позволяет распознавать и классифицировать фрагменты изображения, соответствующие заданному множеству геометрических примитивов, формировать из них протяженные фрагменты и записывать их в виде пары адресов ячеек поля распознавания. При этом существенно экономится память вычислительного устройства, кроме того, запись законченных фрагментов изображения в памяти вычислительного устройства позволяет производить над полученной моделью изображения дальнейшую обработку.Класс G06K9/00 Способы и устройства для считывания и распознавания напечатанных или написанных знаков или распознавания образов, например отпечатков пальцев