JP3025481B2 - Block matching method applying genetic algorithm - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image compression method, and more particularly, to a block matching method using a genetic algorithm, which considers the association with a predetermined object extracted in a reference frame of an image. The present invention relates to an initialization method for performing a different initialization on each of the divided feature blocks after the feature blocks are partitioned.

[0002]

2. Description of the Related Art An image data compression technique is an intra frame coding for compressing information using spatial redundancy existing in an image.
When there is a temporally continuous image, an interframe coding that compresses information by using temporal redundancy between the images (interframe codin).
g). In particular, in moving picture transmission, motion compensated coding using inter-frame coding is a method for reducing the amount of transmission data.
g) is typically used. The motion compensation coding is a method of transmitting a motion vector indicating a movement value of an object moving in a temporally adjacent video frame and a prediction error due to the motion compensation.

[0003] As a method of measuring the amount of movement of an object,
A block matching algorithm (BMA; Block Matching A)
lgorithm) is used. The block matching algorithm includes a global search method, a three-step search method using a high-speed algorithm, and a step-by-step direction change search (one at a time searc).
h) method and a hierarchical block matching algorithm (hierarchical BMA) method using a hierarchical method. Among them, the global search method has a characteristic that it has a regular flow of data, so that it is easy to implement hardware compared to other methods and exhibits good prediction performance, but it requires a large amount of calculation. There are disadvantages.

[0004] The genetic algorithm is a search algorithm based on natural selection and genetic structure, and is to embody an adaptive phenomenon of a natural system into an artificial system. In order to implement a genetic algorithm, an object to be optimized should be represented as a set of parameters, that is, a meaningful bit string having genetic information. This set of parameters is an important part of the genetic algorithm. The bit sequence should be determined analogously to a natural object so as to adequately represent the desired information.

[0005] When the determined genetic information is transmitted to the next generation, a change in the hereditary trait is made, and which operator is selected as a transfer function is determined by the fitness. Genetic algorithms, unlike other search techniques, use internal genetic information rather than direct phenomena, and treat populations with individual genetic information to change the population to a desired optimized state. It is a way to convert.

[0006] Genetic algorithms can be said to be a kind of random search technique, but unlike other random search techniques, there are natural genetic features in addition to simple random features. This genetic characteristic is represented by a set representing genetic information, that is, a genetic trait (DNA or chromosome) and its genetic change, evolution, and the like. Therefore, a genetic algorithm as a search algorithm is not determined by a random function, but is represented by a natural ecosystem phenomenon with respect to a set representing genetic information. For this purpose, functions such as gene regeneration, crossing, and mutation are defined, and changes in genetic traits from one generation to another are evolved, that is, the biological characteristics shown in the method of reducing entropy are used. In this way, the genetic algorithm minimizes the influence of local characteristics with a random function, and moreover, the global characteristics are often found as natural phenomena determined by natural actions.

In the genetic algorithm, the characteristics of a population change from one generation to the next generation depending on the degree of fitness.
The degree of fitness plays a role in selecting only appropriate genetic traits. Such a process requires genetic operators to change the genetic traits, and simple genetic algorithms that give good results in actual application problems can be reproduced, crossed,
It is composed of three mutation operators.

Regeneration is an operator that copies each genetic trait to the next generation according to their objective function, the fitness function. In this regard, the objective function is considered to be a measure for expressing the optimization state due to the application problem. Duplicating a genetic trait by fitness means that the genetic trait with high fitness has a high probability of surviving in the next generation.

After the regeneration operation, the mating operation is performed in two stages. Initially, newly generated genetic traits are arbitrarily combined, an arbitrary position of the genetic trait is selected, and up to the last bit of the genetic trait at that position is exchanged with a relative genetic trait.

Next, there is a mutation that occurs with a given probability. This means that any bit of the genetic trait can be changed from 0 to 1, 1
Is an operator that exchanges for 0. This mutation is an operator that plays an ancillary role in the genetic algorithm, and in some cases, regeneration and crossing alone without mutation operators can produce satisfactory optimization results.

[0011]

SUMMARY OF THE INVENTION It is an object of the present invention to classify macroblocks according to characteristics in association with an object extracted in a reference frame of an image and to perform initialization more suitable for the classified blocks. Accordingly, an object of the present invention is to provide an initialization method using an object extraction feature block by a block matching method using a genetic algorithm that can reduce the amount of motion vector calculation.

[0012]

According to an aspect of the present invention, there is provided a block matching method using a genetic algorithm according to the present invention, comprising the steps of: extracting a predetermined object from a reference frame of an image; An image dividing step of dividing the image into predetermined blocks, a feature dividing step of dividing the divided blocks of the image into respective features in association with the object, and a motion value suitable for the divided feature blocks. An initializing step of initializing a motion value by applying the extracted object, wherein the feature-based dividing step includes a block having no relation to the extracted object, a block overlapping the contour of the extracted object, and In the initialization process, DPC is applied to blocks irrelevant to the extracted object, and the extracted object may be divided into blocks within the object. Block overlapping the contour by applying motion values of neighboring blocks that weights, block at the extracted the object is characterized by applying motion values of neighboring blocks.

[0013]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, the present invention will be described in more detail with reference to the attached drawings. FIG. 1 is a diagram for explaining a block matching method using a genetic algorithm.
7 is an embodiment in which a genetic algorithm is applied using correlation between motion values of adjacent blocks. The motion value of the reference block is determined (S10). If the characteristics of video are not considered, the initialization determines the motion value randomly generated as the initialization value.However, since the moving image has a correlation with the adjacent block, the motion of the adjacent block is determined using this correlation. The average value obtained by averaging the motion values is used as the initialization value. If the average value is used as the initialization value in this way, the number of iterations for applying the genetic algorithm can be reduced, the number of blocks to be searched can be reduced, and the amount of calculation can be reduced.

The fitness is calculated based on the initialized motion values (S12). Mean square error is used as a method of calculating the fitness. In other words, the smaller the error value is, the higher the fitness is. A pair of populations having the smallest mean square error used for calculating the fitness, that is, one population exhibiting the optimal state is selected (S1).
4).

A mating process for generating the next generation is performed by combining or exchanging the genes of the population selected in step S14 (S16). Here, the mating process is UX (Un
iform Crossover) through masking. That is, a mask with a length such as the length of the chromosome of the parent population is generated, but the value of each bit is determined randomly, and if the value of one bit is 1, the value of the descendants is two populations. The value matches one chromosome, and if 0, it matches the value of another chromosome. The value of the other descendant is determined using the inverted mask.

Since there may be traits that have escaped from the population for statistical reasons, a mutation process for inverting the value of the chromosome is performed to supplement the traits (S18). That is, it is a process of finding the overall optimal value while preventing the deviation from the regional optimal value. Finally, from S10 to S
If the 18 steps are repeated until the predetermined optimal value is reached, the strongest chromosome appears, and the value at this time becomes the overall optimal value (S20).

FIG. 2 is a view for explaining an initialization method according to the present invention, and shows a human form, that is, an object, extracted in a reference frame of an image. Here, when the macroblock divided by the reference frame is examined, a block to which the extracted object does not belong such as an A1-B1 block (hereinafter, referred to as an A type block) and an A4-B2 block are extracted. The block can be divided into a block including a contour of the object (hereinafter, referred to as a B type block) and a block completely included in the extracted object (hereinafter, referred to as a C type block), such as an A5-B3 block.

Examining the characteristics of each type block, the A type block is a block whose motion value is difficult to predict.
Since the initialization value should refer to the motion value of an adjacent block, and a B-type block often has one or more motion values in a block, motion prediction using an adjacent block is not particularly effective. Is the case. In addition, the C type block has a high probability of having the same motion value, and there is a case where there is a slightly different motion. Especially for humans,
Eyes and mouths can be good examples. The case of such a C type block is an example suitable for applying the genetic algorithm.

FIG. 3 is a diagram for explaining a method of initializing by applying a genetic algorithm according to each type of FIG. 2, and includes four parent chromosomes and two offspring chromosomes. A case where a group is included will be described. First, the characteristics of the macroblock are determined in association with the extracted object (S30).

As a result of the determination in S30, in the case of a block having no association with the extracted object, for example, an A-type block, a DPC (Dynamic Population Control scheme) is applied. In other words, this method uses one of the motion values of the block at the same position in the previous frame and the position just above the block,
One of the lower, left and right motion values is defined as a parent chromosome. Then, two motion values are arbitrarily selected from the blocks in the search area shown in FIG. 4 and are replaced with the two chromosomes having the smallest fitness during the six types of selection. DPC is performed once after the third generation, and the arbitrarily selected values are the search areas (1, 2, 3, 4) in FIG. 4 and one for each of the first and third search areas in the third generation. Then, in the sixth generation, one for each of the second and fourth search areas is arbitrarily selected. Nine generations, twelve generations. . . Select repeatedly in order. This order is determined by reflecting the characteristic that the human eye is more sensitive in the vertical direction.

If the block is associated with the object extracted in step S30, it is determined whether the block overlaps the outline (S34). If the block overlaps with the contour portion, the next motion value having a weight is applied to the initialization (S36). That is, even if only a portion of an object is located in a block, the motion of the object affects the entire block. However, the background movement may not be neglected. Given this, other weights are given in each of the two cases, and one motion value is selected as a parent chromosome one by one in the A type block and the C type block in the adjacent blocks. Then, they are crossed so as to further obey the characteristics of the parental chromosome belonging to the C type. That is, instead of arbitrarily masking to generate a descendant, a descendant is generated by giving a weight value so that the C-type block is better followed.

If the result of determination in S34 is that the block is not a block that overlaps the outline, the next motion value is applied to initialization (S38). In this case, it is most desirable to be able to find small motion in blocks within the divided object. This is because, considering the overall movement, there is a high probability that the movement of the object will be the movement of the block itself. At this time, one motion value in the C-type block and one motion value in a block at the same position in the previous frame are selected as parent chromosomes, and then a small motion value is found by an algorithm such as mating and mutation. Can be

In the present invention, the characteristics of an image are applied to a genetic algorithm in order to predict an optimal motion value. The most accurate method used to predict motion values is the global search method, which requires too much computation and applied a simplified method to solve this. There is an inferior problem. That is, the overall optimum value cannot be found concentrated on the regional optimum value. Although the characteristics of the genetic algorithm can find the overall optimum without inaccurate assumptions, the computational complexity is relatively large. In order to solve this problem, a block matching method is presented to the genetic algorithm considering the characteristics of the video block, and this calculates the optimal motion value compared to the technology that applies the genetic algorithm based only on the motion value of the neighboring block. A small amount of calculation is required, and an accurate motion value can be calculated.

[0024]

As described above, according to the block matching method to which the genetic algorithm according to the present invention is applied, according to the initialization method according to the feature block of object extraction, the technique of applying the genetic algorithm based only on the motion value of the neighboring block. Therefore, the amount of calculation for calculating the optimum motion value is smaller than that of, and an accurate motion value can be calculated.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating a block matching method using a genetic algorithm.

FIG. 2 is a diagram illustrating an initialization method according to the present invention.

FIG. 3 is a view illustrating a method of initializing by applying a genetic algorithm according to each type of FIG. 2 of the present invention.

FIG. 4 is a drawing showing a search block.

[Explanation of symbols]

S30 A process of determining a feature of a macroblock (feature classification process) S32 A DPC application process S34 A process of determining whether a block overlaps an outline portion (feature classification process) S36 Next motion value having a weight value To apply to the initialization (initialization process) S38 A process to apply the next motion value to the initialization (initialization process) Reference number F05491A1

──────────────────────────────────────────────────続 き Continuation of front page (56) References JP-A-7-121499 (JP, A) H. -K. Chow and M.S. L. Liou, "Genetic Motion Search Algorithm for Video Compression", IEEE Transactions on Circuits and Systems for Technology, Video Technology. 1993, Vol. 3, No. 6, pp. 440-445 K. Kim and R.S. H. Park, "Block Matching Algorithm Using a Genetic Algorithm", SPIE Symp. Visual Communications and Image Processing '95, May 1995, Part 3, pp. 1545-1552 (58) Field surveyed (Int. Cl. ⁷ , DB name) H04N ^7/ 24-7/68 G06F 15/18 550 JICST file (JOIS)

Claims (1)

(57) [Claims] 1. After dividing an image into predetermined blocks,
Motion value that initializes the motion value in each divided block
Decision process and goodness of fit to calculate the mean square error of initialized motion values
Calculation process and population selection to select the population with the smallest mean square error
The selection process and the selected population based on a genetic algorithm,
Based on the genetic algorithm, the mating process and the mating population
And a mutation process for generating a mutation ,
Also, in the block matching method that repeats the above steps,
The motion value determining step includes extracting a predetermined object from a reference frame of the video,
The video segmentation process that divides each block into blocks, and each divided block is not related to the extracted object
Block or overlaps the contour of the extracted object
Block or block in the extracted object
The feature-based segmentation process for segmenting into any one of the blocks and D for the blocks not related to the extracted object
Apply PC and overlap the contour of the extracted object.
Block, the object in that block
Motion and background motion magnitudes and neighboring block motion values
And initialize the motion value of the block based on
Neighbor blocks for blocks within the extracted object
That it comprises a initialization process of applying the locking movement values
A block matching method comprising: