Патент на изобретение №2297039

(54) СПОСОБ РАСПОЗНАВАНИЯ СЛОЖНОГО ГРАФИЧЕСКОГО ОБЪЕКТА

(57) Реферат:

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

Изобретение относится к автоматике и вычислительной технике и, в частности, к системам искусственного интеллекта, предназначено для идентификации сложных объектов на изображении и может быть использовано в системах электронного документооборота (Фиг.1).

Известен способ компьютерного распознавания объектов (см. патент RU 2191431 С2, кл. МПК G 06 K 9/68, от 03.12.1999), при котором на экран монитора выводится изображение распознаваемого объекта, преобразованное в изображение, выполненное в градациях – различных степенях яркости одного цвета, и на него последовательно, поочередно накладываются изображения хранящихся в памяти компьютера шаблонов, выполненных, например, в градациях зеленого, что позволяет увидеть в зоне перекрытия изображений изображение другого, отличного от первых двух цвета, которое и фиксируется как распознанное в случае тождественных, идентичных, а значит, имеющих одинаковый контур изображений распознаваемого объекта и шаблона.

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

Известен способ компьютерного распознавания объектов (см. патент RU 2234127 С2, кл. МПК G 06 K 9/68, от 05.06.2002), при котором программа распознавания объектов пошагово совмещает нормализованные изображения, центрированные и вписанные в одинаковых размеров ячейки таблицы распознаваемых объектов, и изображения шаблонов, центрированные и вписанные в аналогичные ячейки таблицы шаблонов, с шагом, равным высоте строки с ячейками или ширине столбца ячеек таблиц.

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

Наиболее близким по своей технической сущности к заявляемому способу (прототипом) является способ распознавания заданного эталонного изображения на предъявляемой сцене (см. патент США №6775411, кл. МПК G 06 K 9/62, от 13.01.2005), который заключается во фрактальном кодировании анализируемой сцены, при котором сцена разбивается на ранговые блоки, эталонное изображение разбивается на доменные блоки, производится итеративный поиск наилучшего доменно-рангового сопоставления и подсчитывается число успешных сопоставлений. Затем общее число успешных сопоставлений делится на общее число ранговых блоков в сцене для вычисления относительного числа успешных сопоставлений. Решение о присутствии заданного эталона в сцене принимается посредством анализа значения относительного числа успешных сопоставлений.

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

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

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

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

Выполнение предлагаемого способа осуществляется в несколько этапов, как изображено на Фиг.2. Первоначально, на этапе предобработки, на изображениях всех эталонных объектов формируются доменные блоки (блок 5, Фиг.2), представляющие собой области изображения размером 8×8 пикселей. Затем в изображении анализируемого объекта формируются ранговые блоки (блок 6, Фиг.2), представляющие собой области изображения размером 4×4 пикселей. Таким образом, ранговые блоки в два раза меньше доменных блоков. Указанная разница в размере необходима для того, чтобы аффинное преобразование было сжимающим. Результат формирования доменных и ранговых блоков показан на Фиг.3.

Далее, с использованием аффинных преобразований, реализуют итерационный алгоритм поиска для каждого рангового блока подобного ему доменного блока (блок 7, Фиг.2). Блоки считаются подобными, если значение средней пиксельной ошибки PSNR, определяемое по формуле (1), меньше некоторого порогового значения [4]:

где k, w – сравниваемые изображения, M_gravlavel – число уровней изображения, N_rows, N_cols – число строк и столбцов изображения, k_ij, w_ij – значения пикселя в i ряду j столбце соответствующего изображения. Пороговое значение выбирается исходя из требуемой точности распознавания и априорно известного уровня искажений.

Сжимающее аффинное преобразование определяется формулой (2):

где х_n, у_n и x_n+1, y_n+1 входные и выходные координаты пикселя в декартовой системе, a, b, c, d – коэффициенты, отвечающие за масштабирование и поворот, e, f – коэффициенты, отвечающие за перенос [4]. Результаты сжимающих аффинных преобразований представлены на Фиг.4.

Для тех ранговых и доменных блоков, значение PSNR между которыми меньше порогового, в блоке 8 (Фиг.2) отдельно для каждого эталона формируется таблица векторов расстояний между центами блоков (Фиг.5), ячейки которой получают приращения при записи (блок 9, Фиг.2) в таблицу вектора расстояния, значение которого удовлетворяет диапазону ячейки. В качестве меры расстояния выбрано Евклидово расстояние. Пример формирования таблицы показан на Фиг.6.

После завершения итерационного поиска подобных доменных и ранговых блоков сформированные таблицы каждого эталона поступают на классификатор (блок 10, Фиг.2) по методу наименьших квадратов (3) [5]:

где d – расстояние между объектами k и w, s_i – i^ый признак объекта k, g_i – i^ый признак объекта w.

Полученное расстояние между объектами поступает на блок 11 (Фиг.2) принятия решения о принадлежности анализируемого изображения к одному из эталонных. Анализируемое изображение соответствует тому объекту, расстояние до которого является наименьшим. Схема алгоритма предлагаемого способа изображена на Фиг.7-9.

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

Предлагаемый способ реализован в среде программирования C++Builder 6.0 с использованием графического интерфейса GUI и рассчитан на выполнение в среде Windows на ПЭВМ класса Pentium, CPU 200 Мгц, 64 RAM и выше.

Описание элементов фигур

Фигура 1:

1 – Анализируемая сцена;

2 – Сканирующее устройство;

3 – ЭВМ;

4 – Эталонные изображения.

Фигура 2:

5 – Блок формирования доменных блоков в изображениях всех эталонных объектов;

6 – Блок формирования ранговых блоков в изображении анализируемого объекта;

7 – Блок поиска наилучшего доменно-рангового сопоставления;

8 – Блок формирование векторов расстояний;

9 – Блок записи векторов в таблицу;

10 – Блок классификатора;

11 – Блок принятия решения.

Фигура 3:

12 – Эталонное изображение;

13 – Доменный блок;

14 – Ранговый блок;

15 – Анализируемое изображение.

Фигура 5:

16 – Доменный блок;

17 – Эталонное изображение;

18 – Проекция доменного блока;

19 – Анализируемое изображение;

20 – Ранговый блок;

21 – Вектор расстояния между доменным и ранговым блоком.

Источники информации

1. Патент RU 2191431 С2, кл. МПК G 06 K 9/68, от 03.12.1999.

2. Патент RU 2234127 С2, кл. МПК G 06 K 9/68, от 05.06.2002.

3. Патент США №6775411, кл. МПК G 06 K 9/62, от 13.01.2005.

4. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии / Перевод с англ. – М.: Триумф, 2001.

5. Фукунага К. Введение в статистическую теорию распознавания образов / Перевод с англ. – М.: Наука, 1979.

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

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

РИСУНКИ

MM4A – Досрочное прекращение действия патента СССР или патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе

Дата прекращения действия патента: 19.04.2007

Извещение опубликовано: 20.07.2008 БИ: 20/2008