JP2001101411A - System and method for pattern matching - Google Patents

Abstract

PROBLEM TO BE SOLVED: To perform pattern matching of information at high speed. SOLUTION: First of all, the information of a retrieval object is stored in a dictionary memory 40 together with a pattern index made into binary code. Then, the binary coded pattern index of inputted information is found in an input pattern index part 100 by the similar patterning method. Next, the pattern index in this dictionary memory and the pattern index of the input information are selected by a high-speed pattern matching part 120 and by preferentially performing pattern matching to information belonging to this pattern index, the optimal pattern can be retrieved from the information of the retrieval object at high speed.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to information retrieval by pattern matching, and more particularly to high-speed retrieval of target information.

[0002]

2. Description of the Related Art Fractal image coding is a technique for compressing information using self-similarity, which is a structural feature of an image. Many studies have been made on fractal image coding as a coding method capable of high resolution and high compression. In the coding process of fractal image coding, first, an image is divided into unit blocks of R × R pixels called range blocks. Then, for each range block, a D × D pixel (D> R) having a pattern similar to the range block
Search for the domain block in its own image.
This similar domain block is called the optimal domain block. This fractal image coding will be described with reference to FIG. In fractal image coding, an image is first divided into non-overlapping blocks of R × R pixels. This unit block is called a range block R ₀ ... R _m . Prior to the encoding process, a domain pool is created from a block group of D × D (D> R) pixels called domain blocks extracted from the image.

In the encoding process, first, the standard deviation of the pixel values of the range block is calculated. A range block having a small standard deviation value is classified as a flat block.
With respect to the range block classified as the flat block, the search for the optimal domain block is not performed, and the decoding is approximated by only the average value at the time of decoding.

[0004] A range block having a large standard deviation value is classified as a non-flat block, and an optimum domain block is searched from the created domain pool. In the search for the optimal domain block, first, the range block and the blocks in the domain pool are normalized, and δ of [Equation 1] shown below is calculated. Here, the normalization is a process of subtracting the average value from each pixel value of the block and dividing the average value by the standard deviation. Then, the domain block having the smallest calculated value of δ is selected as the fastest domain block.

(Equation 1) dev (r): standard deviation of the range block n: block size τ: eight kinds of affine transformation d _{(i, j)} : pixel value r _(i ) at the position (i, j) of the normalized domain block _{, j)} : Normalized pixel value at the position (i, j) of the range block By this encoding process, the image data is converted into an average value, a standard deviation of each range block, and an image of the optimal domain block in the image. The information is converted into affine conversion information added to the position and domain block, and transmitted to the decoding side.

[0005] In the decoding process of fractal image encoding,
First, using only the average value of the received range block,
Generate a low resolution initial image. The resolution of the image is increased by repeatedly performing the following decoding processing based on the initial image. Extract a domain block from the image from the position information of the optimal domain block.・ Range block of domain block
The size is reduced, and affine conversion is performed according to the received affine conversion information. Average values m (r), m (d) and standard deviations dev (r), d of the range block and the domain block, respectively
ev (d), the pixel value d of the transformed domain block
Using (i, j), the pixel value of the range block is

(Equation 2) Update to This decoding process is performed until an image having a sufficient resolution is obtained or until the change in the image converges.

When searching for the optimal domain block, a very large amount of calculation is required to perform pattern matching between the range block and the domain block.
The encoding process takes time. This is one of the problems in fractal image coding. To reduce processing time, search for similar domain blocks
The most effective method is to reduce the number of calculations by reducing the number of comparisons by matching the range block and the domain block. For example, in order to reduce the number of comparisons between the range block and the domain block, three types of blocks of shade, midrange, and edge are defined according to the magnitude of the change in pixel value, and the blocks are classified into these three types of blocks. And first, the range block has little change
If it is a shade block, this range is calculated using only the average value without searching for similar domain blocks.
Approximate blocks. In addition, the range block is midr
In the case of an ange block or an edge block, a method of reducing the number of comparisons between blocks by searching for similar domain blocks only from domain blocks of the same type, thereby reducing the amount of calculation. Can also. However, the amount of comparison and calculation is still too large, and a high-speed image information pattern matching method is still desired.

[0007]

SUMMARY OF THE INVENTION An object of the present invention is to propose a new high-speed pattern matching method which requires a small amount of calculation.

[0008]

In order to achieve the above object, the present invention relates to a pattern matching system for retrieving an optimum pattern for input information from search target information, comprising n elements. From each element of the search target information,
Subtract the average of the values of the n elements, express the sign of the result as 1 or 0, and construct a binary code with the information indicating the sign.
Search target information having the same binary code is collected into one group, and the binary code is used as an index of the group, including a dictionary divided into a plurality of groups, and input information including n elements. The average value of the n elements is subtracted from the value of each element, the sign of the result is represented by 1 or 0, and a pattern index that forms a binary code with the information representing the sign is calculated, and the input information is calculated. Pattern matching is preferentially performed from search target information belonging to a group of dictionaries having the same index as the pattern index.

If there is no or a small number of dictionary groups having the same index as the pattern index of the input information, pattern information is searched for the search target information belonging to the dictionary group in order from the index close to the pattern index of the input information.・ Matching can be performed. This makes it possible to perform pattern matching on input information at high speed.

[0010] This pattern matching system comprises:
It can be applied to pattern matching in fractal image coding for image information. This is performed by setting the input information as a range block, the search target information as a domain block, and a plurality of groups in the dictionary as a domain pool including domain blocks having the same pattern index. . Before calculating the pattern index of the input information, make sure that the input information has a flat range
When it is detected that the block is a block, it is output that the block is a flat range block, and pattern matching can not be performed.

The present invention also includes a method executed by the above-described pattern matching system, and a recording medium on which a program capable of constructing the above-described pattern matching system in a computer system is recorded.

[0012]

Embodiments of the present invention will be described in detail with reference to the drawings. FIG. 2 is a diagram for explaining the outline of the present invention. 2, in the present invention, first, information to be searched is stored in the dictionary memory 140 together with a binary-coded pattern index. Then, the input pattern index unit 100 obtains the binary coded pattern index of the input information by the same patterning technique. Next, the high-speed pattern matching unit 120 selects a pattern index in the dictionary memory and a pattern index of the input information, and preferentially performs pattern matching on information belonging to the pattern index. The optimum pattern can be searched at high speed from the search target information.

Referring to FIG. 3, the method of obtaining a binary code pattern index from search information will be described in detail, taking two-dimensional image information as an example. As shown in FIG.
First, in image information including n elements (blocks) to be searched, an average value m (b) of n blocks is calculated from pixel values b (i, j) of the blocks. And FIG.
As shown in (b), the average value m is calculated from the pixel value b (i, j).
(B) is subtracted, and each block is binarized by its sign. As shown in FIG. 3C, the binarized two-dimensional pixel value is converted into one-dimensional data by, for example, Hilbert scanning. As shown in FIG. 3D, the pattern index is obtained by regarding the one-dimensionally converted pixel value data as an n-bit binary bit string.

In this way, an n-digit binary coded pattern index including the features of the image information can be obtained from the image information. In the above description, the Hilbert scan is performed to convert the binarized two-dimensional pixel values into one-dimensional data. Anything can be used as long as it is possible.

In the above description, image information has been described as an example. However, a pattern index can be created for other audio information than image information, for example, by the same method. In the present invention, the matching is performed using the binary coded pattern index of the input information and the binary coded pattern index in the dictionary.
By performing the processing in step 20, high-speed pattern matching for searching for an optimal pattern is performed. Next, an example of the processing of the high-speed pattern matching unit 120 will be described with reference to the flowchart of FIG.

First, the structure of data stored in the dictionary memory 140 used for the matching process will be described. The dictionary memory 140 collects search target information having the same pattern index to form one dictionary pattern group, and a plurality of groups each having the pattern index as an index of the group are configured to store search target information. I have. By the way, before starting the matching process, the binary coded pattern index for the input information is obtained as described above. The matching process is performed using the input information and the obtained pattern index.

In the flowchart of FIG. 4, a dictionary pattern group having the same pattern index as the input information is selected from the dictionary memory (S202). If there is a dictionary pattern group having the same pattern index (S20
(Yes in 4), matching is performed between the search target information belonging to the dictionary pattern group having the same pattern index and the input information (S206), and the optimum pattern is selected. If there is no dictionary pattern group having the same pattern index as the input information (No in S204), the hamming distance (m) is set to 1 (S222), and the hamming distance between the input information and the pattern index is 1 from the dictionary memory. The dictionary pattern group having the pattern index is selected (S224). If the dictionary pattern group of the pattern index whose Hamming distance is 1 is equal to or more than the threshold x (Yes in S226), pattern matching is performed with the search target information belonging to the dictionary pattern group (S2).
28), detecting an optimal pattern.

When the number of dictionary pattern groups of pattern indexes whose Hamming distance is 1 is smaller than x thresholds (S
(No at 226), the hamming distance is incremented by 1, and a dictionary pattern group having a pattern index of the hamming distance that has been incremented again is selected (S224). In this way, the search range of the Hamming distance up to n is increased by one, a dictionary pattern group is selected, pattern matching is performed with search target information belonging to the selected dictionary pattern (S228), and an optimum pattern is selected. I do. in this way,
By obtaining a binary code pattern index for the information to be searched, and searching using this pattern index, it is possible to perform high-speed pattern matching processing by reducing the information to be subjected to pattern matching.

[0019]

Embodiment <Pattern in Fractal Image Coding
Search Method Using Index> An embodiment in which the above-described algorithm of the high-speed search method using the pattern index is used for fractal image coding will be described with reference to the flowchart of FIG. Prior to searching for an optimal domain block, a domain pool (dictionary pattern group) is created in a dictionary memory used for searching. The domain pool is
Create for each pattern index. First, domain blocks are extracted from an image at regular intervals, reduced to a range block size, subjected to affine transformation, and a pattern index is calculated. Then, a domain pool is created by a group of domain blocks having the same pattern index.

In the search, first, the target range
Calculate the standard deviation of the block. If the standard deviation is smaller than the threshold T1 (Yes in S312), the block is classified into a flat range block, and no search is performed. A flat range block is approximated only by an average value during decoding. When the standard deviation is large (No in S312)
Performs the following processing in order to classify into non-flat range blocks and perform an optimal domain search.

Calculate the pattern index of the range block. And the range block pattern
An optimal domain block is searched from the domain pool of the same pattern index as the index (S3
22). The domain block is evaluated by δ in the above [Equation 1] (S324). In the search processing up to this point, if the number of evaluated domain blocks is equal to or larger than the threshold value T2 (No in S326), the domain block having the smallest δ among the evaluated domain blocks is determined as the optimal domain block.
A block is selected (S328). This process is called a coincidence index search unit 320. If the number of evaluated domain blocks is smaller than the threshold value T2 (Yes in S326), the process proceeds to the next process.

A pattern index of the range block is calculated, and a pattern index different from the pattern index by a threshold value T3 bits is calculated (S33).
1). Then, an optimal domain block is searched from the domain pool of the pattern index different from the pattern index of the range block by T3 bits (S332). The evaluation of the domain block is performed by δ in [Equation 1] as in the case of the coincidence index search unit (S334). In the search processing up to this point, when the number of evaluated domain blocks is equal to or larger than the threshold T4 (S3
(No at 35), the domain block having the smallest δ among the evaluated domains is selected as the optimal domain block (S336). If the evaluated number of domain blocks is smaller than the threshold T4 (Yes in S335), the threshold T3
The evaluation range is widened by increasing the value of. Threshold T3 until the number of evaluated blocks exceeds threshold T4
Repeat the adjustment of the value of. This process is called a difference index search unit 330.

<Regarding Threshold T1> As described above, the processing of the proposed search method includes the flat range determination unit 310, the match index search unit 320, and the difference index search unit 3
30 types. First, when the flat range determination unit 310 determines that the range block is a flat block, the search for the optimal domain block is not performed at all. Therefore, when the range block is a flat block, the amount of calculation is the least regardless of the domain block. The determination of the flat block is made by comparing the standard deviation of the range block with the threshold value T1. Increasing the threshold T1 increases the ratio of flat range blocks, thereby reducing the amount of calculation and the amount of information. However, on the other hand, the image quality deteriorates because the range block is simply approximated by only the average value. For example, in order to determine the threshold T1, only flat blocks of five types of test images were encoded, and a subjective evaluation experiment was performed on the reproduced images. The threshold T1 was set to T1 = 4 so that all images had a rating value of 3.5 (permissible limit) or more based on the evaluation using the double stimulation method and the five-point rating scale.

<Regarding the Threshold T2> If the range block has a non-flat range, the processing of the next matching index search unit 320 is performed. In this search group, only the domain block in the domain pool having the same pattern index as the range block is evaluated by δ in [Equation 2], and the optimal domain block is determined.
The amount of calculation required to evaluate domain blocks is as simple as determining which pool to search for each range block because the domain pools of the proposed method are classified in advance by the pattern index. So it is very slight. The number of domain blocks evaluated here is determined by the threshold value T2. Threshold T
If 2 is set small, the number of blocks that do not proceed to the next process increases, so that the calculation amount can be reduced. However, when only a small number of blocks are evaluated, the error between the range block and the optimal domain block becomes large, and the surface quality of the reproduced image is reduced. When the pattern index matches, the pattern matching is considered to be better than when the pattern indexes do not match.
The threshold value T2 = 1 at which the amount of calculation can be reduced most is set to T1.

<Regarding Thresholds T3 and T4> When the number of evaluated domain blocks is smaller than the threshold T2, the processing of the difference index search unit 330 is further performed. First, a pattern index whose hamming distance is a threshold T3 is calculated from the pattern index of the range block.
Then, a domain pool having the same pattern index as the calculated pattern index is selected, and only the domain blocks in the pool are evaluated. At the stage where all blocks in the selected domain pool are checked, the number of evaluated domain blocks is reduced to a threshold T4.
If it is smaller, the value of the threshold T3 is increased, and the range of the domain block to be evaluated is increased. The process is repeated while increasing the value of the threshold T3 until the number of domain blocks finally evaluated exceeds the threshold T4,
The domain block having the smallest δ is set as the optimal domain block. In this embodiment, a pattern of a range block is used to evaluate and determine a domain block.
The pattern whose hamming distance from the index is the threshold T3
Calculate the index. For example, the calculation of a pattern index having a Hamming distance of n bits is 2 in which the pattern index and n bits are 1 and other bits are 0.
It can be easily calculated by taking the exclusive OR with the hex code. Therefore, the computation required to determine which domain pool to select and evaluate is small.

First, consider the threshold value T3. Already in the match index search, a domain with a Hamming distance of 0
Since the block is being evaluated, the initial value of the threshold value T3 is 1. If the number of evaluated domain blocks is smaller than the threshold value T4, the value of the threshold value T3 is increased to widen the range of the domain block to be searched. Since the closer the hamming distance of the pattern index is, the more similar the pattern is considered, if the number of evaluated domain blocks is smaller than the threshold T4, the value of the threshold T3 is increased by one, and the hamming distance of the pattern index is increased. Preferentially evaluates the closer domain block.

Next, consider the threshold value T4. When the threshold value T4 is increased, the number of domain blocks evaluated by the difference index search unit increases and the amount of calculation increases, but the image quality of the reproduced image improves. The table shown in FIG. 6 shows the average (MEDN) of the number of evaluated domain blocks per range block and the SNR (signal-to-noise ratio) of the reproduced image when the threshold value T4 is changed. The relationship is Other threshold values are T1 = 4, T2 =
1, T3 = 1, and the range in which T3 is expanded is 1. FIG.
Even if the value of the threshold value T4 is reduced from the table, the image quality of the reproduced image is not significantly degraded. In the present embodiment, the threshold value T4 is set to 1 so as to minimize the amount of calculation for a high-speed search for the optimal domain block.

The present invention can be applied not only to the pattern matching of image information described in detail above, but also to information for which a pattern index corresponding to information can be obtained, such as audio information. it can.

The present invention may be applied not only to a stand-alone computer system but also to, for example, a client server system composed of a plurality of systems. The system according to the present invention can be realized by reading and executing the program from a storage medium storing the program according to the present invention by the system.
The recording medium includes a floppy (registered trademark) disk, a CD-ROM, a magnetic tape, a ROM cassette, and the like.

[0030]

As described above, according to the present invention, the information to be subjected to pattern matching consisting of n elements is 1 or 0 depending on whether or not the average value of the values of the n elements is equal to or less than the average value.
By using such a binary code, a binary-coded pattern
Calculate the index. By performing pattern matching based on this pattern index, high-speed pattern matching processing can be realized.

[Brief description of the drawings]

FIG. 1 is a diagram for describing fractal image encoding.

FIG. 2 is a diagram illustrating a pattern matching process according to the present invention.

FIG. 3 is a diagram illustrating a method of obtaining a pattern index for image information.

FIG. 4 is a flowchart showing a pattern matching process using a pattern index.

FIG. 5 is a flowchart showing a case where the processing of the present invention is applied to pattern matching of fractal image coding.

FIG. 6 is a table showing the influence of a threshold value T4 in the flowchart of FIG.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 100 Input pattern index part 120 High-speed pattern matching part 140 Dictionary memory 310 Flat range determination part 320 Matching index search part 330 Difference index search part

Claims (6)

[Claims] 1. A pattern matching system for searching an optimum pattern for input information from search target information, comprising: averaging the values of n elements from each element of the search target information including n elements A value is subtracted, the sign of the result is represented by 1 or 0, and a binary code is formed by the sign information.
Search target information having binary codes is collected into one group, and the binary code is used as an index of the group, including a dictionary divided into a plurality of groups, and each element of the input information consisting of n elements Subtracts the average of the values of the n elements from the result, represents the sign of the result as 1 or 0, and calculates a pattern index in which a binary code is formed by the information indicating the sign, and calculates the pattern index of the input information. A pattern matching system wherein pattern matching is performed preferentially from search target information belonging to a group of dictionaries having the same index as an index. 2. The pattern matching method according to claim 1,
In the system, if there is no dictionary group having the same index as the pattern index of the input information, the pattern
A pattern matching system wherein pattern matching is performed on search target information belonging to a group of dictionaries in order from an index close to the index. 3. The pattern matching system according to claim 1, wherein the input information is a range block, the search target information is a domain block, and the plurality of groups in the dictionary are the same pattern. A pattern matching system, which is a domain pool composed of domain blocks having an index, and performs pattern matching in fractal image coding for image information. 4. The pattern matching method according to claim 3,
When calculating the pattern index of the input information, if the input information detects that the input information is a flat range block with little change in elements, the system outputs that it is a flat range block and outputs the pattern range. A pattern matching system characterized by not performing matching. 5. A pattern matching method for searching an optimum pattern for input information from search target information, comprising: an average value of values of n elements from each element of the search target information including n elements And the sign of the result is represented by 1 or 0, and the information representing the sign is used to form a binary code.
Search target information having binary codes is collected into one group, and the binary code is used as an index of the group, including a dictionary divided into a plurality of groups, and each element of the input information consisting of n elements Subtracts the average of the values of the n elements from the result, represents the sign of the result as 1 or 0, and calculates a pattern index in which a binary code is formed by the information indicating the sign, and calculates the pattern index of the input information. A pattern matching method characterized by performing pattern matching preferentially from search target information belonging to a group of dictionaries having the same index as an index. 6. A recording medium on which a program capable of constructing the pattern matching system according to claim 1 in a computer system is recorded.