JP3835937B2 - Feature extraction method, feature extraction apparatus for implementing the method, and recording medium - Google Patents

Description

【００２８】
なお、上記はあくまで実施例であって、パターンの小領域への分割方法や辞書とのマッチング方法などは上記に限定されるものではない。
【００２９】
（実施例３）
本発明は、上述の実施例に限定されず、ソフトウエアによっても実現することができる。本発明をソフトウェアによって実現する場合には、図８に示すように、ＣＰＵ２０，制御装置２１，ＲＯＭ２２，ＲＡＭ２３，表示装置２４，ハードディスク２５，キーボード２６，ＣＤ−ＲＯＭドライブ２７，通信装置２８，スキャナ２９などからなる汎用の処理装置を用意する。なお、本発明を実施するには、ＣＰＵを複数持つマルチプロセッサの処理装置を用意するか、シングルプロセッサの処理装置を並列に接続する。
【００３０】
ＣＤ−ＲＯＭなどのコンピュータ読み取り可能な記録媒体３０には、本発明のデータ提供機能を実現するプログラムが記録されている。該プログラムが起動されると、スキャナから文字パターンを画像データとして入力するか、もしくはあらかじめハードディスクに保存されている画像データを読み出してＲＡＭ上に配置し、該データに対して特徴抽出処理を実行する。
【００３１】
図９に示す例においては、輪郭画素１つにＣＰＵ１つを別個に割り当て、それぞれのＣＰＵ上で、実施例１で述べたような該輪郭画素への滑らかな方向コード抽出→輪郭方向の分解→２組の（方向コード，分解係数）の付与を並列に実行させる。こうすることによって、輪郭画素ごとに逐次的に処理する場合よりも高速に特徴抽出を行うことができる。
【００３２】
請求項４の発明においては、図１０に示すように、小領域１つにＣＰＵ１つを別個に割り当て、それぞれのＣＰＵ上で該領域内に存在する輪郭画素への滑らかな方向コード抽出→輪郭方向の分解→２組の（方向コード，分解係数）の付与、および、該領域に関する方向コードヒストグラム成分の作成を並列に実行させ、それらを統合して最終的な方向コードヒストグラムを得る。こうすることによって、方向コードの付与とヒストグラムの作成をヒストグラム成分ごとに逐次的に処理する場合よりも高速に特徴抽出を行うことができる。また、一般に、小領域の数は輪郭画素数に比べてかなり小さいので、上記した輪郭画素ごとにプロセッサを割り当てる方法よりもずっと少ないプロセッサで実現可能であり、システムの肥大化を抑えることができる。
【００３３】
【発明の効果】
本発明によれば、あらかじめ定められた方向コードのみを用いて実際のパターンに近い滑らかな輪郭方向を実現でき、パターン形状に関する情報をより正確に含む特徴量を得ることができる。
【図面の簡単な説明】
【図１】 本発明による特徴量抽出方法及び装置を説明するための要部構成図である。
【図２】 本発明の動作説明をするためのフロー図である。
【図３】 輪郭方向の説明をするための図である。
【図４】 平滑化された輪郭方向を説明するための図である。
【図５】 輪郭方向と分解に用いる方向コードを示す図である。
【図６】 付与される方向コードと分解係数を示す図である。
【図７】 パターンの分割例を示す図である。
【図８】 本発明による記録媒体が使用されるコンピュータの構成例を示す図である。
【図９】 方向コード付与の並列処理を説明するための図である。
【図１０】 ヒストグラム作成の並列処理を説明するための図である。
【図１１】 方向コードを説明するための図である。
【図１２】 輪郭方向の説明をするための図である。
【図１３】 平滑化された輪郭方向を説明するための図である。
【符号の説明】
１…輪郭方向抽出部、２…輪郭方向分解部、３…方向コード記憶部、４…分解係数記憶部、５…方向コード記憶部、６…分解係数記憶部、７…方向コード付与部、１１…パターン入力部、１２…前処理部、１３…パターン分割部、１４…方向コード付与モジュール、１５…特徴量作成部、１６…辞書作成部、１７…辞書、１８…マッチング部、１９…認識結果出力部。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a feature extraction method and a feature extraction device for character recognition, a computer-readable recording medium storing a program for causing a computer to execute feature extraction processing, and a feature extraction method using the recording medium.
[0002]
[Prior art]
The procedure for executing character recognition generally extracts a feature quantity from a given character pattern, compares it with a standard feature quantity in a dictionary prepared in advance, and outputs the most consistent category as a recognition result.
Here, the feature quantity must efficiently include information on the shape of the pattern, but as one of widely used feature extraction methods, it is exemplified in Japanese Patent Application Laid-Open No. 8-194780. There is an approach to create a simple direction code histogram. That is, for a pixel considered as a character outline in a pattern, a direction code reflecting the outline direction is assigned to the pixel, and a vector (direction code histogram) having a coefficient value of the assigned direction code as a component is characterized. Amount.
[0003]
Specifically, the example described in Japanese Patent Application Laid-Open No. 8-194780 will be described. Among the white pixels of the pattern, the pixels adjacent to the top, bottom, left, and right are any of the states shown in FIGS. 11 (A) to 11 (D). In this case, the pixel is defined as a contour pixel, and any one of method codes 1 to 4 representing horizontal, vertical, right-up, and right-down contour directions is assigned according to FIG.
[0004]
[Problems to be solved by the invention]
However, in the above method, a contour direction smoother than the quantization step of the direction code cannot be given to each contour pixel. For example, in FIG. 12, FIG. 12 (B) shows an enlarged view of part B of FIG. 12 (A) and shows a part of a straight line having an intermediate inclination between 0 ° and 45 ° as measured from the horizontal axis. However, in the method described above, each contour pixel can only express its contour direction by either 0 ° (direction code 1) or 45 ° (direction code 3). That is, although the pixels shown in A to D in FIG. 12B are all contour pixels on a straight line having the same inclination, A and C have directions of 45 ° and B and D have 0 °. Therefore, it has become a “rough” contour expression.
[0005]
By the way, by smoothing the contour direction, each contour pixel can be given a smooth direction temporarily. For example, weight 1 is used for the contour pixel of interest, and weight 0.5 is used for adjacent contour pixels, and a weighted average of the contour direction between these three pixels is obtained. Assuming that the direction vector corresponding to the horizontal direction (direction code 1) is x = (1, 0) and the direction vector corresponding to the right upward direction (direction code 3) is u = (1, 1),
Pixels A and C: 0.5x + u + 0.5x = x + u
Pixel B, D: 0.5u + x + 0.5u = x + u
As shown in FIG. 13, a smooth contour direction can be obtained. In addition, since the difference in the contour direction is small between the pixels A to D (the difference is eliminated in this example), the contour expression is a good reflection of the actual straight line.
[0006]
However, in the conventional method, even if a smooth contour direction is temporarily obtained in this way, in the end, only one of the predetermined direction codes can be represented at the stage of giving.
[0007]
An object of the present invention is to provide a feature extraction method for applying a direction code so that each contour pixel can express a smooth contour direction while using a predetermined direction code.
[0010]
[Means for Solving the Problems]
The invention according to claim 1 is a feature extraction method for assigning any one of predetermined direction codes to contour pixels of a character pattern, and extracts a contour direction smoother than the quantization step of the direction code. And a step of decomposing the extracted contour direction into a superposition of two direction codes, and a step of assigning these two direction codes to a contour pixel. In the decomposition step, In the feature extraction method in which the decomposition coefficient corresponding to each is stored and the respective division coefficients are given to the contour pixel together with the two direction codes in the adding step , the character pattern is divided into a plurality of small regions. Then, for each small area, the sum of the absolute values of the decomposition coefficients assigned in the area is obtained for each direction code, and the vector having these sums as components is recognized. Is obtained is characterized in that the characteristic quantity for.
[0013]
According to a second aspect of the present invention, there is provided means for extracting a contour direction smoother than a predetermined quantization step of a direction code with respect to a contour pixel of a character pattern, and overlapping the extracted contour direction with two direction codes. Means for decomposing them together, and means for giving these two direction codes to the contour pixel, the decomposing means comprising a coefficient storage unit for storing a decomposition coefficient corresponding to each of the two decomposed direction codes, In the feature extraction device that assigns each decomposition coefficient read from the coefficient storage unit together with two direction codes to the contour pixel, the assigning means divides the character pattern into a plurality of small regions, Means for obtaining for each direction code the sum of absolute values of decomposition coefficients assigned in each area for each small area, and means for creating a vector having these sums as components It is obtained by said.
[0015]
According to a third aspect of the present invention, there is provided a step of extracting a contour direction smoother than a predetermined quantization step of a direction code with respect to a contour pixel of a character pattern, and superimposing the extracted contour direction on two direction codes. A character pattern in a computer-readable recording medium storing a program for causing a computer to execute a feature extraction process including a step of decomposing them together and a step of assigning a corresponding decomposition coefficient to the contour pixels together with these two direction codes Dividing a plurality of small regions, obtaining a sum of absolute values of decomposition coefficients given in each region for each small region for each direction code, and creating a vector having these sums as components Characterized by recording a program that causes a computer to execute feature extraction processing A.
[0017]
The invention of claim 4 assigns a separate processor to each of the small regions divided from the character pattern, and the feature extraction processing according to claim 3 for each of the contour pixels in each region, and the processor The step of obtaining the sum of the absolute values of the decomposition coefficients given in the region for each direction code is executed in parallel.
[0018]
DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 is a block diagram of a main part of a feature extraction method and apparatus according to the present invention. FIG. 1A shows a direction code assigning module using the present invention, and 1 is a contour for each contour pixel of an input character pattern. A contour direction extracting unit 2 for extracting a direction, 2 is a contour direction decomposing unit that decomposes the contour direction into a superposition of two direction codes, and 3 and 4 store one of the two direction codes obtained by the decomposition. A direction code storage unit and a decomposition coefficient storage unit for storing the decomposition coefficient, 5 and 6 similarly, a direction code storage unit for storing the other direction code, a decomposition coefficient storage unit for storing the decomposition coefficient, and 7 for these storage units. 4 is a direction code applying unit that applies the direction code and the decomposition coefficient read from 4 and 6 to the contour pixel.
[0019]
FIG. 1B is a character recognition module using the direction code assigning module, 11 is a pattern input unit composed of a scanner or the like, 12 is a preprocessing unit for performing image processing such as pattern normalization and noise removal, A pattern dividing unit that divides 13 patterns into small regions, 14 is a direction code assigning module shown in FIG. 1A, and 15 is a feature value creating unit that creates feature values based on the given direction code. The feature amount is sent to the dictionary creation unit 16 when the dictionary is created, where a standard feature amount for each category is created and stored in the dictionary 17. Further, at the time of character recognition, the feature amount is sent to the matching unit 18, where it is collated with the dictionary 17 created prior to recognition, and the recognition result is output from the recognition result output unit 19.
[0020]
Example 1
FIG. 2 is a diagram showing a processing flow according to the present invention, and FIGS. 3 to 6 are diagrams for explaining the operation. Hereinafter, FIG. 12 (same as FIG. 3) and FIG. The same will be described in detail with reference to the contour expression of the straight line shown in FIG. Here, it is assumed that four types of direction codes are defined in increments of 45 ° representing horizontal, vertical, right-up, and right-down, and the corresponding direction vectors are represented by x, y, u, and v, respectively.
[0021]
First, for each contour pixel, a contour direction smoother than the direction code quantization step (ie, 45 ° step) is extracted. Here, after obtaining the contour direction in increments of 45 ° according to FIG. 11 (state of FIG. 3), smoothing of the contour direction described above is performed (state of FIG. 4). Of course, the method for extracting the smooth contour direction is not limited to this one, and another method may be used.
[0022]
Next, each of the extracted smooth contour directions is decomposed into a superposition of two direction codes. The superposition of the direction codes here is considered to be a linear combination of the direction vectors corresponding to them. As shown in FIG. 5, the two direction codes to be used for the decomposition are determined in advance as follows according to the value of the contour direction θ (degrees).
・ 0 ≦ θ <45: x and u
45 ≦ θ <90: y and u
90 ≦ θ <135: y and v
135 ≦ θ <180: x and v
That is, the two direction codes closest to the contour direction are used.
[0023]
Now, it is clear that the smooth contour directions extracted in the example of FIG. 4 are all decomposed into x + u. The two direction codes obtained as a result of the decomposition are horizontal (code 1) and upward (code 3), and the respective decomposition coefficients are both 1. Therefore, as shown in FIG. 6, (direction code, decomposition coefficient) = (1, 1) (3, 1) is assigned to the contour pixel.
In this way, in any contour pixel, the original contour direction is reproduced by multiplying the two given direction codes by the respective decomposition coefficients and taking the vector sum. That is, each contour pixel can have a smooth contour direction that cannot be expressed in 45 ° increments.
[0024]
(Example 2)
Next, a method for creating a direction code histogram from the two direction codes given as described above and the decomposition coefficient will be described. First, a given pattern is divided into a plurality of small areas. Here, as shown in FIG. 7, it is assumed that the image is divided into 4 × 4 small areas. Next, two sets of values (direction code, decomposition coefficient) are assigned to each contour pixel by the method described in the first embodiment.
[0025]
In the conventional direction code histogram, after that, the number of direction codes assigned to each contour pixel for each small region is counted for each code. In the present invention, the direction code assigned to each contour pixel is The sum of the absolute values of the corresponding decomposition coefficients is obtained for each code. For example, in the case of FIG. 6, the pixel A corresponds to the right upward direction (code 3) of the same small area at the same time as adding 1 to the histogram component corresponding to the horizontal direction (code 1) of the small area to which A belongs. 1 is also added to the histogram component. It should be noted here that “the direction codes 1 and 3 are assigned to the pixel A one by one, so that the corresponding histogram components are increased by one”. Whereas the conventional histogram component is a count value of “number of direction codes”, in the present invention, it can be said that the histogram component is based on “strength of direction code” having continuous values.
[0026]
As described above, a direction code histogram having 4 × 4 (small region) × 4 (direction code) = 64 components is obtained, and this is used as a feature amount for character recognition. At the time of recognition, for example, the city block distance between the standard feature amount for each category prepared in the dictionary in advance and the feature amount created from the given pattern is obtained, and the category having the minimum distance is recognized. As output. As an example of obtaining the standard feature value, several learning character patterns belonging to the category are prepared, and an average value of the feature values is obtained.
[0027]
[Expression 1]

[0028]
Note that the above is only an example, and the method of dividing the pattern into small regions, the method of matching with the dictionary, and the like are not limited to the above.
[0029]
Example 3
The present invention is not limited to the above-described embodiments, and can be realized by software. When the present invention is implemented by software, as shown in FIG. 8, as shown in FIG. 8, CPU 20, control device 21, ROM 22, RAM 23, display device 24, hard disk 25, keyboard 26, CD-ROM drive 27, communication device 28, scanner 29 A general-purpose processing device consisting of the above is prepared. In order to implement the present invention, a multiprocessor processing apparatus having a plurality of CPUs is prepared, or single processor processing apparatuses are connected in parallel.
[0030]
A computer-readable recording medium 30 such as a CD-ROM stores a program for realizing the data providing function of the present invention. When the program is started, a character pattern is input from the scanner as image data, or image data stored in advance on the hard disk is read out and placed on the RAM, and feature extraction processing is executed on the data .
[0031]
In the example shown in FIG. 9, one CPU is separately assigned to one contour pixel, and smooth direction code extraction to the contour pixel as described in the first embodiment is performed on each CPU. Two sets of (direction code, decomposition coefficient) are applied in parallel. In this way, feature extraction can be performed at a higher speed than when sequential processing is performed for each contour pixel.
[0032]
In the invention of claim 4 , as shown in FIG. 10, one CPU is separately assigned to one small region, and smooth direction code extraction to contour pixels existing in the region on each CPU is performed. → 2 sets of (direction code, decomposition coefficient) and creation of direction code histogram components for the region are executed in parallel, and they are integrated to obtain a final direction code histogram. In this way, feature extraction can be performed at a higher speed than the case where direction code assignment and histogram creation are sequentially performed for each histogram component. In general, since the number of small regions is considerably smaller than the number of contour pixels, it can be realized with a much smaller number of processors than the above-described method of allocating a processor for each contour pixel, and the enlargement of the system can be suppressed.
[0033]
【The invention's effect】
According to the present invention, it is possible to realize a smooth contour direction close to an actual pattern using only a predetermined direction code, and to obtain a feature amount that includes information on the pattern shape more accurately.
[Brief description of the drawings]
FIG. 1 is a configuration diagram of a main part for explaining a feature amount extraction method and apparatus according to the present invention.
FIG. 2 is a flowchart for explaining the operation of the present invention.
FIG. 3 is a diagram for explaining a contour direction;
FIG. 4 is a diagram for explaining a smoothed contour direction.
FIG. 5 is a diagram showing contour directions and direction codes used for disassembly.
FIG. 6 is a diagram showing a direction code and a decomposition coefficient to be given.
FIG. 7 is a diagram illustrating an example of pattern division.
FIG. 8 is a diagram illustrating a configuration example of a computer in which a recording medium according to the present invention is used.
FIG. 9 is a diagram for explaining parallel processing for giving a direction code;
FIG. 10 is a diagram for explaining parallel processing for creating a histogram.
FIG. 11 is a diagram for explaining a direction code.
FIG. 12 is a diagram for explaining a contour direction.
FIG. 13 is a diagram for explaining a smoothed contour direction.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 ... Contour direction extraction part, 2 ... Contour direction decomposition | disassembly part, 3 ... Direction code memory | storage part, 4 ... Decomposition coefficient memory | storage part, 5 ... Direction code memory | storage part, 6 ... Decomposition coefficient memory | storage part, 7 ... Direction code provision part, 11 DESCRIPTION OF SYMBOLS ... Pattern input part, 12 ... Pre-processing part, 13 ... Pattern division part, 14 ... Direction code provision module, 15 ... Feature-value creation part, 16 ... Dictionary creation part, 17 ... Dictionary, 18 ... Matching part, 19 ... Recognition result Output part.

Claims (4)

A feature extraction method for assigning a predetermined direction code to a contour pixel of a character pattern, the step of extracting a contour direction smoother than the quantization step of the direction code, and the extracted contour Decomposing a direction into a superposition of two direction codes, and applying these two direction codes to a contour pixel;
In the decomposition step, a decomposition coefficient corresponding to each of the two decomposed direction codes is stored, and in the adding step, each decomposition coefficient is also given to the contour pixel together with the two direction codes. In the extraction method,
Character pattern for character recognition by dividing the character pattern into a plurality of small areas, obtaining the sum of absolute values of the decomposition coefficients assigned in each small area for each direction code, and vectors having these sums as components A feature extraction method characterized by a quantity. Means for extracting a contour direction smoother than a predetermined quantization step of the direction code for the contour pixels of the character pattern; means for decomposing the extracted contour direction into a superposition of two direction codes; Means for assigning these two direction codes to the contour pixel, wherein the disassembling means includes a coefficient storage unit for storing a dissociation coefficient corresponding to each of the two disjoined direction codes, and the providing means includes the contour pixel. In the feature extraction apparatus for assigning the respective decomposition coefficients read from the coefficient storage unit together with the two direction codes,
A means for dividing the character pattern into a plurality of small areas, a means for obtaining the sum of absolute values of the decomposition coefficients given in the respective areas for each direction code, and a vector having these sums as components feature extraction device you comprising the means. Extracting a contour direction smoother than a predetermined quantization step of the direction code for the contour pixels of the character pattern; decomposing the extracted contour direction into a superposition of two direction codes; A computer-readable recording medium recording a program for causing a computer to execute a feature extraction process including a step of assigning a corresponding decomposition coefficient to the contour pixel together with these two direction codes.
A step of dividing the character pattern into a plurality of small areas, a step of obtaining a sum of absolute values of the decomposition coefficients given in the small areas for each small area for each direction code, and creating a vector having these sums as components recorded computer readable medium storing a program for executing a feature extraction process consisting of steps in a computer. 4. A feature extraction process according to claim 3 for each of the small regions divided from the character pattern and each processor for contour pixels existing in the region, and a decomposition coefficient assigned to the region. The computer-readable recording medium which recorded the program which performs the step which calculates | requires the sum of the absolute value of every according to direction code in parallel.

Images