Способ кодирования элементов бинарного изображения и устройство для его осуществления

 

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

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

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

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

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

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

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

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

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

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

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

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

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

На последнем шаге производят замену номера ячейки, содержащей первоначально код типа 5 или 6, на номер ячейки, которая примыкает к соответственно к верхней или к правой границе данной ячейки.

На фиг.3 отрезки типа 6, находящиеся в ячейках 35, 41, 51 и 61, меняются на отрезки типа 3 и переносятся в соответственно в ячейки 36, 42, 52 и 62. Результат такого преобразования показан на фиг.4.

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

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

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

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

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

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

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

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

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

Формула изобретения

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4