RU2321058C1 - Method for recognizing a complex graphic object - Google Patents

Abstract

FIELD: artificial intelligence systems, possible use for identification of complex graphic objects on an image, may be used in electronic workflow systems.

SUBSTANCE: in accordance to the method, spectral representation is generated in form of coordinate-phase portrait of object image. Then wavelet transformation of portrait is performed and at each level of transformation a characteristic vector of signs is formed, which consists of statistical characteristics of distributions of wavelet coefficients. Further, distances are computed between coordinate of signs vector of graphic object being analyzed and centers of clusters of characteristic vectors of standard objects. Resulting distances are recorded in a table. Then the table is sent to classifier. The data from the classifier are received at the block for making decisions about association of object being analyzed with one of the permitted classes, where the decision is then made.

EFFECT: increased trustworthiness when recognizing graphic objects due to extraction of signs from images being analyzed which make it possible to efficiently describe objects being analyzed under conditions when the manner of handwriting influences their structure.

6 dwg

Description

Translated fromRussian

Изобретение относится к автоматике и вычислительной технике и, в частности, к системам искусственного интеллекта. Предназначено для распознавания на изображении сложных графических объектов в виде изолированных печатных и рукописных символов и может быть использовано в системах электронного документооборота (Фиг.1).The invention relates to automation and computer technology and, in particular, to artificial intelligence systems. Designed for recognition of complex graphic objects in the form of isolated printed and handwritten characters on the image and can be used in electronic document management systems (Figure 1).

Задача, решаемая изобретением, заключается в повышении достоверности распознавания графических объектов за счет извлечения из анализируемых изображений признаков, позволяющих эффективно описывать анализируемые объекты в условиях влияния характера почерка на их структуру.The problem solved by the invention is to increase the reliability of recognition of graphic objects by extracting from the analyzed images features that allow you to effectively describe the analyzed objects under the influence of the nature of handwriting on their structure.

Сущность изобретения заключается в том, что на первом этапе формируют спектральное представление анализируемого графического объекта в виде его координатно-фазового портрета на основе построчного пошагового сканирования бит графического изображения в направлении слева-направо и сверху-вниз с фиксацией на каждом шаге переходов бит (дибит) в состояние, соответствующее конкретной фазе, в зависимости от выбранной схемы. Затем производят вейвлет преобразование координатно-фазового портрета графического объекта, заключающееся в формировании характеристического вектора признаков, состоящего из статистических характеристик распределений вейвлет коэффициентов, представляющих собой результат многоуровневой свертки исходного координатно-фазового портрета графического объекта с базовой функцией вейвлета. Значение расстояния между центрами каждого кластера характеристических векторов объектов-эталонов и координатой характеристического вектора анализируемого графического объекта записывают в таблицу. Далее таблицу подают на классификатор, где по критерию минимума расстояния определяется кластер, ближайший к координате характеристического вектора анализируемого графического объекта. Данные с классификатора поступают на блок принятия решения о принадлежности анализируемого объекта к одному из разрешенных классов, где и принимают решение.The essence of the invention lies in the fact that at the first stage a spectral representation of the analyzed graphic object is formed in the form of its coordinate-phase portrait on the basis of line-by-line step-by-step scanning of the graphic image bits from left to right and from top to down with fixation of bit transitions (dibit) at each step to the state corresponding to a specific phase, depending on the selected circuit. Then, a coordinate-phase portrait of a graphic object is converted into a wavelet, which consists in generating a characteristic feature vector consisting of statistical characteristics of the distribution of wavelet coefficients, which are the result of a multi-level convolution of the initial coordinate-phase portrait of a graphic object with the basic wavelet function. The distance value between the centers of each cluster of characteristic vectors of reference objects and the coordinate of the characteristic vector of the analyzed graphic object is recorded in the table. Next, the table is submitted to the classifier, where the cluster closest to the coordinate of the characteristic vector of the analyzed graphic object is determined by the criterion of minimum distance. Data from the classifier goes to the decision-making unit on the belonging of the analyzed object to one of the allowed classes, where they make the decision.

Пример реализации данного способа поясняется чертежами, на которых на Фиг.1 показана схема реализации способа, на Фиг.2 - блок-схема операций предлагаемого способа, на Фиг.3 - схема правил четырехпозиционного фазового пространства координатно-фазового способа, на Фиг.4 - схема правил восьмипозиционного фазового пространства координатно-фазового способа, на Фиг.5 - результат формирования координатно-фазового портрета графического (фрагмент), на фиг.6 - кластеры характеристических векторов объектов-эталонов.An example of the implementation of this method is illustrated by drawings, in which Fig. 1 shows a diagram of the implementation of the method, Fig. 2 is a block diagram of the operations of the proposed method, Fig. 3 is a diagram of the rules of the four-position phase space of the coordinate-phase method, and Fig. 4 is a the rules diagram of the eight-position phase space of the coordinate-phase method, Fig. 5 is the result of the formation of the coordinate-phase portrait of the graphic (fragment), in Fig. 6 are clusters of characteristic vectors of reference objects.

Выполнение предлагаемого способа осуществляется в несколько этапов, как изображено на Фиг.2. Первоначально, на этапе предобработки, на анализируемой сцене определяются координаты всех графических объектов, подлежащих распознаванию (блок 5, Фиг.2). Затем для каждого графического объекта формируется его координатно-фазовый портрет (блок 6, Фиг.2).The implementation of the proposed method is carried out in several stages, as shown in Fig.2. Initially, at the pre-processing stage, on the analyzed scene, the coordinates of all graphic objects to be recognized are determined (block 5, FIG. 2). Then, for each graphic object, its coordinate-phase portrait is formed (block 6, Figure 2).

Правило формирования координатно-фазового портрета заключается в следующем. В процессе просмотра (сканирования) массива пикселей (матрицы) изображения анализируемого графического объекта в направлении сверху-вниз и слева-направо (построчно) осуществляется пошаговая оценка перехода бит (дибит, трибит и т.д.) в состояние, соответствующее конкретной фазе, в зависимости от выбранной схемы правил, показанных на Фиг.3 и Фиг.4. Результат формирования координатно-фазового портрета (фрагмент) показан на Фиг.5.The rule for the formation of the coordinate phase portrait is as follows. In the process of viewing (scanning) an array of pixels (matrix) of the image of the analyzed graphic object in the direction from top to bottom and from left to right (line by line), a step-by-step assessment of the transition of bits (dibit, tribit, etc.) to the state corresponding to a specific phase is performed, in depending on the selected scheme of the rules shown in Fig.3 and Fig.4. The result of the formation of the coordinate-phase portrait (fragment) is shown in Fig.5.

Далее производится вейвлет преобразование полученного координатно-фазового портрета (1) (блок 7, Фиг.2).Next, a wavelet transform of the obtained coordinate-phase portrait (1) is performed (block 7, Figure 2).

где ψ_j,k(x) - базовая функция вейвлета, f(x) - координатно-фазовый портрет графического объекта, x - абсцисса координатно-фазового портрета, d_j,k - многоуровневая последовательность вейвлет коэффициентов, j, k - параметры уровня вейвлет преобразования [1].where ψ_{j, k} (x) is the basic wavelet function, f (x) is the coordinate-phase portrait of a graphic object, x is the abscissa of the coordinate-phase portrait, d_{j, k} is a multi-level sequence of wavelet coefficients, j, k are wavelet level parameters transformations [1].

На следующем этапе формируется характеристический вектор признаков графического объекта, состоящий из статистических характеристик распределений вейвлет коэффициентов на каждом уровне вейвлет преобразования - формула (2) (блок 8, Фиг.2).At the next stage, a characteristic vector of features of a graphic object is formed, consisting of statistical characteristics of the distributions of wavelet coefficients at each level of the wavelet transform — formula (2) (block 8, FIG. 2).

Статистические характеристики распределений вейвлет коэффициентов [2] представляют собой математическое ожидание (3):The statistical characteristics of the distribution of wavelet coefficients [2] are the mathematical expectation (3):

где P_kj - вероятность появления коэффициента со значением d_kj в k позиции, дисперсию (4):where P_kj is the probability of occurrence of a coefficient with a value of d_kj at the k position, variance (4):

асимметрию (5):asymmetry (5):

где

и

, эксцесс (6):Where

and

, excess (6):

Значения расстояний между центрами кластеров характеристических векторов объектов-эталонов (Фиг.6) и координатой характеристического вектора анализируемого графического объекта записывают в таблицу (блок 9, Фиг.2). В качестве меры выбрано Евклидово расстояние.The values of the distances between the centers of the clusters of characteristic vectors of reference objects (FIG. 6) and the coordinate of the characteristic vector of the analyzed graphic object are recorded in the table (block 9, FIG. 2). The Euclidean distance is chosen as a measure.

Сформированная таблица поступает на классификатор (блок 10, Фиг.2), где по критерию минимума расстояния определяется кластер, ближайший к координате характеристического вектора анализируемого графического объекта [3].The generated table goes to the classifier (block 10, Figure 2), where the cluster closest to the coordinate of the characteristic vector of the analyzed graphic object is determined by the criterion of minimum distance [3].

Полученный номер кластера поступает на блок 11 (Фиг.2) принятия решения о принадлежности анализируемого изображения к одному из разрешенных классов. Анализируемый графический объект соответствует тому классу, к кластеру которого он был отнесен.The resulting cluster number is sent to block 11 (FIG. 2) for deciding whether the analyzed image belongs to one of the allowed classes. The analyzed graphic object corresponds to the class to the cluster of which it was assigned.

Экспериментальная проверка предлагаемого способа показала, что характеристический вектор признаков, состоящий из статистических характеристик вейвлет коэффициентов, способен адекватно учитывать вариации в формировании сложных графических объектов, вызванные характером почерка.An experimental verification of the proposed method showed that the characteristic feature vector, consisting of the statistical characteristics of the wavelet coefficients, is able to adequately take into account variations in the formation of complex graphic objects caused by the nature of the handwriting.

Предлагаемый способ реализован в среде математического моделирования MathLab 7.0.4 и рассчитан на выполнение в среде Windows на ПЭВМ класса Pentium, CPU 200 МГц, 64 RAM и выше.The proposed method is implemented in the mathematical modeling environment MathLab 7.0.4 and is designed to run in a Windows environment on a Pentium-class PC, CPU 200 MHz, 64 RAM and higher.

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

Фигура 1:Figure 1:

1 - анализируемая сцена;1 - analyzed scene;

2 - сканирующее устройство;2 - scanning device;

3 - ЭВМ;3 - computers;

4 - эталонные изображения.4 - reference images.

Фигура 2:Figure 2:

5 - блок определения координат графических объектов на анализируемой сцене;5 - block for determining the coordinates of graphic objects on the analyzed scene;

6 - блок формирования координатно-фазового портрета графического объекта;6 - block forming the coordinate-phase portrait of a graphic object;

7 - блок выполнения вейвлет пребразования;7 - block perform the wavelet transform;

8 - блок формирования характеристического вектора признаков;8 - a block for generating a characteristic feature vector;

9 - блок записи векторов в таблицу;9 - block recording vectors in the table;

10 - блок классификатора;10 - classifier block;

11 - блок принятия решения.11 - decision block.

Фигура 6:Figure 6:

12 - координата характеристического вектора признаков графического объекта;12 - coordinate of the characteristic feature vector of the graphic object;

13 - кластеры характеристических векторов объектов-эталонов первого разрешенного класса;13 - clusters of characteristic vectors of standard objects of the first permitted class;

14 - кластеры характеристических векторов объектов-эталонов второго разрешенного класса;14 - clusters of characteristic vectors of standard objects of the second allowed class;

15 - кластеры характеристических векторов объектов-эталонов третьего разрешенного класса;15 - clusters of characteristic vectors of standard objects of the third allowed class;

16 - кластеры характеристических векторов объектов-эталонов четвертого разрешенного класса.16 - clusters of characteristic vectors of reference objects of the fourth allowed class.

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

1. Дьяконов В.П. Вейвлеты. От теории к практике. - М.: СОЛОН-Р, 2002. - 155 с.1. Dyakonov V.P. Wavelets. From theory to practice. - M .: SOLON-R, 2002 .-- 155 p.

2. Гмурман В.Е. Теория вероятностей и математическая статистика. - М.: Высшая Школа, 1972. - 368 с.2. Gmurman V.E. Theory of Probability and Mathematical Statistics. - M.: Higher School, 1972. - 368 p.

3. Яковлев В.Л., Миняев А.А. Аналитическая модель сложноструктурированного объекта факсимильного сообщения. Сборник научных трудов. Выпуск 19. С. - Орел: Академия ФСО России, 2005.3. Yakovlev V.L., Minyaev A.A. An analytical model of a complex structured facsimile message object. Collection of scientific papers. Issue 19. S. - Orel: Academy of the Federal Security Service of Russia, 2005.

4. Яковлев В.Л., Миняев А.А. Алгоритм автоматической обработки факсимильных сообщений. Сборник научных трудов. Выпуск 19. С. - Орел: Академия ФСО России, 2005.4. Yakovlev V.L., Minyaev A.A. Algorithm for automatic processing of fax messages. Collection of scientific papers. Issue 19. S. - Orel: Academy of the Federal Security Service of Russia, 2005.

Claims (1)

Translated fromRussian

Способ распознавания сложных графических объектов, характеризующийся трехуровневой процедурой обработки графического объекта с формированием на первом уровне спектрального представления графического объекта в виде его координатно-фазового портрета на основе построчного пошагового сканирования бит графического изображения в направлении слева-направо и сверху-вниз с фиксацией на каждом шаге переходов бит (дибит) в состояние, соответствующее конкретной фазе, в зависимости от выбранной схемы, вейвлет-преобразованием спектра графического объекта на втором уровне, заключающимся в формировании характеристического вектора признаков, состоящего из статистических характеристик распределений вейвлет-коэффициентов, представляющих собой результат многоуровневой свертки исходного спектра графического объекта с базовой функцией вейвлета, и принятием решения об отнесении образа графического объекта к одному из разрешенных классов по критерию минимума расстояния между центрами кластеров характеристических векторов объектов-эталонов и координатой характеристического вектора анализируемого графического объекта на третьем уровне.A method for recognizing complex graphic objects, characterized by a three-level procedure for processing a graphic object with the formation at the first level of the spectral representation of the graphic object in the form of its coordinate-phase portrait based on line-by-line step-by-step scanning of bits of the graphic image from left to right and from top to bottom with fixing at each step transitions of a bit (dibit) to a state corresponding to a specific phase, depending on the selected scheme, by a wavelet transform of the graphic object at the second level, which consists in the formation of a characteristic feature vector consisting of statistical characteristics of the distributions of wavelet coefficients, which are the result of a multi-level convolution of the initial spectrum of the graphic object with the basic wavelet function, and the decision to assign the image of the graphic object to one of the allowed classes by the criterion for the minimum distance between the centers of clusters of characteristic vectors of reference objects and the coordinate of the characteristic vectors of the analyzed graphic object at the third level.

Images