JP2008042424A - Image matching apparatus and image matching method - Google Patents

Abstract

【Task】
More accurate image matching is performed with a smaller amount of computation.
[Solution]
An integer pixel accuracy matching unit that performs image matching with integer pixel accuracy, and a plurality of image matching similarities in a predetermined axial direction are obtained, and a plurality of image matching positions are obtained by using a fitting function obtained from the similarity. A fractional pixel accuracy matching unit that calculates the degree of similarity at the position and compares the plurality of image matching positions with the degree of similarity at the position to perform image matching with a fractional pixel precision to obtain one image matching position; Is provided.
[Selection] Figure 1

Description

  The present invention relates to a digital moving image encoding technique.

  Patent Document 1 discloses a method for approximating a cost distribution with a fitting function, such as parabolic fitting or equiangular straight line fitting, and calculating a minimum cost pixel by using a fitting function as a high-precision positioning technique for images in the field of image processing. ing.

  In addition, as an image block matching method in moving image encoding, a pixel value with decimal precision is complemented by a multi-tap filter, and then block matching is performed on these pixels. A method of creating a complementary image using a plurality of taps is disclosed, for example, in Non-Patent Document 1 (H.264 / AVC).

Japanese Patent Application No. 2004-525640, "Multi-parameter high-accuracy simultaneous estimation method and multi-parameter high-accuracy simultaneous estimation program for image sub-pixel matching", Science and Technology Promotion Association (Shimizu, Okutomi) H.264 / AVC (ITU-T Recommendation H.264 and ISO / IEC 14496-10 (MPEG-4 part 10) Advanced Video Coding), JVT (Joint Video Team)

  In Patent Document 1, in order to obtain the minimum cost pixel more accurately, pixels at a plurality of decimal pixel precision positions with respect to the horizontal and vertical axes are obtained using a fitting function, and the decimal precision pixels for each axis are obtained. Create an approximate straight line and use the intersection as the decimal precision pixel that will eventually be adopted, but it includes the process of obtaining multiple decimal precision pixels for each axis and further obtaining those approximate straight lines, resulting in an enormous amount of computation. There was a problem.

  On the other hand, the method in Non-Patent Document 1 has a problem that the amount of processing becomes very large due to interpolation processing because pixel values are interpolated by a multi-tap filter and block matching is performed.

  The present invention has been made in view of the above problems, and an object thereof is to realize high-precision image matching with a smaller amount of calculation.

  In order to achieve the above object, the present invention includes an integer pixel accuracy matching unit that performs image matching with integer pixel accuracy, and a decimal pixel accuracy matching unit that performs image matching with decimal pixel accuracy.

  According to the present invention, highly accurate image matching can be realized with a smaller amount of calculation.

  Embodiments for carrying out the invention will be described below with reference to the drawings. In addition, in each drawing, the component to which the same code | symbol is attached | subjected shall have the same function.

  First, an example of an image storage / playback apparatus to which the present invention is applied will be described with reference to FIG. This image storage / playback apparatus records a video camera (including a mobile phone having such a photographing function) that captures an image and stores it in a storage medium such as a tape or an optical disc, or a received television broadcast, for example. For example, a hard disk recorder or a DVD recorder, or a television apparatus incorporating such a recorder. That is, the present invention can be applied to a video camera, a hard disk recorder, a DVD recorder, a television device, and the like. Of course, any other apparatus having a function of encoding and recording a moving image can be applied in the same manner.

  In FIG. 5, from an input terminal IN, for example, an image captured by an imaging device such as a CCD or a received digital television broadcast image is input. This input image is assumed to be a moving image. The input image is encoded in real time by the encoding unit 501 and supplied to the storage medium 502. Details of the encoding process in this encoding unit will be described later. The storage medium 502 stores encoded moving images, and includes, for example, a semiconductor memory such as an optical disk, a hard disk, and a flash memory, a tape recorder, and the like. The decoding unit 503 decodes the encoded image stored in the storage medium 502 and generates, for example, a video signal in RGB or component (Y / Cb / Cr) format. This video signal is supplied to a display unit 504 having a display element such as an LCD or a PDP as necessary. The display unit 504 displays a moving image reproduced from the storage medium 2 based on the supplied video signal.

  Next, details of the encoding unit 501 will be described with reference to FIG. FIG. 1 shows an example of the configuration of a moving picture encoding apparatus according to the present invention, which performs vector estimation with decimal pixel accuracy using a fitting function. The input image 101 input to the input unit 100 is supplied to the subtractor 102, the motion estimation unit 111 using the fitting function, and the motion to the compensation unit 113, respectively. First, in the subtracter 102, a difference between one block image of the input image 101 input from the input unit 100 and the prediction block 114 output from the motion compensation unit 113 is obtained and output as an error signal. This error signal is input to the converter 103 and converted into DCT (discrete cosine transform) coefficients. The DCT coefficient output from the converter 103 is quantized by the quantizer 104 to generate a quantized transform coefficient 105. At this time, the code amount of the error signal is also output together with the quantized transform coefficient 105. The quantized transform coefficient 105 is supplied to the multiplexer 116 as transmission information. The quantized transform coefficient 105 is also used as information for combining predicted images between frames. That is, the quantized transform coefficient 105 is inversely quantized by the inverse quantizer 106, inversely transformed by the inverse transformer 107, then added by the adder 108 with the output image 114 from the motion compensation unit 113, and the current frame The decoded image is stored in the frame memory 109. As a result, the current frame image is delayed by one frame time and supplied to the motion estimation unit 111 as a previous frame image 110.

  The motion estimation unit 111 performs a process of estimating a motion vector using the input image 101 and the previous frame image 110 that are images of the current frame. In motion vector estimation, a portion similar to the content of the target macroblock is searched from the decoded image (reference image) of the previous frame (generally, the prediction error in the luminance signal block is compared with the search range of the previous frame. This is processing for obtaining motion information (motion vector) and motion prediction mode information, which is referred to as block matching (positioning) processing in the present application. For example, a technique disclosed in Japanese Patent Application Laid-Open No. 2004-357086 may be used for determining the degree of similarity between the target macroblock and the reference image in the block matching process.

  The motion estimation unit 111 outputs motion information 112 such as motion vectors and residuals to the motion compensation unit 113. The motion compensation unit 113 generates motion information and motion prediction mode information 115 by predictive macroblock information and block matching processing. The predicted macroblock image 114 is output to the subtractor 102 as described above, and the motion information and motion prediction mode information 115 are supplied to the multiplexer 116. The multiplexer 116 multiplexes and encodes the quantization coefficient 105 and the motion information and motion prediction mode information 115.

  The present embodiment is characterized in that information on the fitting function for the cost is used in the motion estimation processing in the motion estimation unit 111. The motion estimation unit 111 in the present embodiment creates a fitting function from the cost value of integer pixel accuracy obtained in advance by the conventional method, and reduces the amount of calculation related to the minimum cost pixel search with decimal pixel accuracy. .

  Here, in the present application, the cost refers to a numerical value indicating the degree of similarity (similarity) between the above-described target macroblock and the reference image. The fitting function refers to a function that passes through values at coordinate positions of discrete points given to coordinates, or a function approximate to this. For example, a linear function for a discrete two-point value given to coordinates, an approximate linear function for a discrete three-point value given to coordinates, and a quadratic to a discrete three-point value given to coordinates Curve function, approximate quadratic curve function for discrete four point values given to coordinates, function by two pairs of straight lines passing through two points among discrete four point values given to coordinates, etc. .

  Here, creating or obtaining a fitting function from a cost value means giving the above function so that the cost value is taken as a sampling value and passes through or approximates the sampling value. .

  The detailed operation will be described below.

  FIG. 2 shows a configuration of the motion estimation unit 111 using the fitting function according to the present embodiment.

  Assume that the input image 101 is processed by being divided into a plurality of blocks (macroblocks). First, the integer pixel accuracy motion estimation unit 201 performs matching according to the conventional method for the block of the input image 101 to obtain the minimum cost point in the search for integer pixel accuracy. Next, the integer pixel accuracy motion estimator 201 outputs the integer pixel accuracy cost minimum point information 202, and the fractional pixel accuracy motion estimator 203 outputs the fractional pixel accuracy around the integer pixel accuracy cost minimum point information 202. The minimum cost pixel is calculated. In this embodiment, the minimum cost of integer pixel accuracy is calculated by matching in the conventional method, and the minimum cost pixel of decimal pixel accuracy is calculated using a fitting function, but the fitting function is used for decimal pixels. It is not limited to. That is, it is also possible to estimate the position of the minimum cost pixel with integer pixel accuracy from these costs after first creating a cost every several pixels.

  2 has been described as the motion estimation unit of the video encoding device, but when used as an image matching device, the integer pixel accuracy motion estimation unit 201 is an integer pixel accuracy image matching unit, the decimal pixel accuracy motion estimation unit 203 is A decimal pixel image matching unit may be used.

  Next, referring to FIG. 3, a method for calculating the minimum cost pixel using a fitting function in the horizontal axis direction will be described. 301 represents an input image, and 302 represents a reference image. Here, it is assumed that the pixel having the minimum cost is obtained for a certain block 303 in the input image. If the block that best matches the block 303 within a given range is 304, fitting is performed from the cost value of that block and the cost of the block (305 and 306, respectively) that moved the block by ± 1 pixel in the horizontal direction. Create function 307. For example, a fitting function that is a quadratic curve function is used. The coordinate 308 of the minimum value of this fitting function is adopted as the coordinate of the horizontal axis of the pixel that gives the minimum cost. Also, with respect to the vertical axis, the coordinates of the minimum pixel are obtained by the same processing as in FIG. Here, the minimum point of the fitting function is the minimum cost point. However, the minimum cost point using the fitting function can be determined by a method other than the minimum point of the function, such as an intersection of two straight lines. In this example, fitting is performed for the cost of blocks shifted by ± 1 pixel. However, the block to which the fitting is applied is not limited thereto.

  FIG. 4 shows a flowchart of sub-pixel accuracy motion estimation using a fitting function in the sub-pixel accuracy motion estimation unit 203 of FIG. The fractional pixel accuracy motion estimation unit 203 starts the fractional pixel accuracy motion estimation in step 400 based on the input information on the minimum cost of integer pixel accuracy obtained by the conventional method. Next, in step 401, cost values of neighboring pixels are calculated with respect to the horizontal axis, and in step 403, coordinates estimated to minimize the cost are determined using a fitting function. Regarding the vertical axis, the same processing is performed in step 405 and step 407, and in step 409, from the output information of step 403 and step 407, the coordinate position in the horizontal axis direction of the final estimated point of the minimum cost is determined to be vertical. Determine the axial coordinate position. For example, at this time, out of the coordinates estimated to minimize the cost using the fitting function on each axis, one of the coordinates having the smallest cost may be set as the coordinate of the estimated point having the smallest cost. In addition, the coordinate value in the horizontal axis direction of the coordinates of the estimated point of the lowest cost is the minimum position coordinate on the vertical axis acquired from step 403, and the vertical axis of the coordinate of the estimated point of the lowest cost The cost on the vertical axis acquired from step 407 may be the minimum position coordinate for the direction coordinate value.

  In the flowchart of FIG. 4, the steps of processing the horizontal axis and the vertical axis in parallel are shown, but these steps may be processed in series.

  Up to this point, the method of obtaining the minimum cost point with decimal pixel accuracy using the fitting function has been described. However, it is only that when the cost distribution has anisotropy and is not along the horizontal axis and the vertical axis. There is a problem that the pixel with the lowest cost is not necessarily selected.

  That is, FIG. 6a shows a schematic diagram when the cost distribution is anisotropic and not along the horizontal axis and the vertical axis. FIG. 6a shows the case where the cost minimum point is estimated using the horizontal axis and the vertical axis for the anisotropic cost distribution. Reference numeral 703 denotes a contour line of the cost distribution. Here, it is assumed that the cost is reduced toward the center of the ellipse. Reference numeral 705 denotes a pixel having a minimum cost value obtained by estimation, and reference numeral 706 denotes a point at which the cost is actually minimized.

  On the other hand, in the fractional pixel precision motion estimation in the present embodiment, a cost minimum point estimation method using other than the horizontal axis and the vertical axis is also used. For example, an axis inclined 45 degrees as shown in FIG. 6b is used. In FIG. 6b, reference numeral 707 denotes a pixel having the minimum cost value obtained by estimation.

  In FIG. 6a, the estimated value 705 and the actual value 706 are significantly different from each other, whereas in FIG. 6b, the cost distribution is close to the axis, and the estimated value 707 and the actual value 706 are close to each other. It is possible to obtain the minimum cost point with higher accuracy than when using the axis and the vertical axis.

  Further, when the axis is further tilted to an angle other than 45 degrees as shown in FIG. 6c, the pixel position 708 having a different minimum cost value and a minimum cost value is also acquired.

  In FIGS. 6a, b, and c, the fitting function is obtained on the two axes, and the smaller pixel with the smallest cost on each axis is estimated as the pixel position with the smallest cost. However, the position of the pixel having the position of the minimum cost value on each axis as the coordinate value in the direction of each axis may be estimated as the pixel position having the minimum cost.

  In FIG. 6, the description is made using two axes orthogonal to each other, but two axes that are not orthogonal may be used.

  Thus, it can be seen that in an anisotropic cost distribution, pixel positions can be obtained with different minimum cost values and minimum cost values depending on which axis is used as the axis to which the fitting function is applied.

  As described above, in this embodiment, the minimum cost pixel is estimated using not only the conventional horizontal axis and vertical axis directions but also adjacent pixels at different angles. Further, a pixel having a low cost is adopted among the results of estimating the minimum cost pixel in each direction. Thereby, estimation with higher accuracy than estimation of decimal pixel accuracy using a fitting function in two specific axes can be performed.

  Next, a method for calculating the minimum cost pixel using a fitting function for an axial direction inclined by 45 degrees with respect to the horizontal and vertical axes will be described with reference to FIG. Here, a cost fitting function is obtained for pixels adjacent in the direction of 45 degrees with respect to the horizontal and vertical axes, and coordinates are determined based on the minimum cost pixel obtained in each direction. Reference numeral 801 denotes an input image, and 802 denotes a reference image. Here, it is assumed that a pixel having a minimum cost is obtained for a certain block 803 in the input image. In the predetermined range, if the block that best matches the block 803 is 304, the cost value in that block and the block in which the block is moved in the horizontal +45 degree direction by ± 1 pixel (805 and 806 respectively) A fitting function 307 is created from the cost. The coordinate 308 of the minimum value of this fitting function is adopted as the coordinate of the horizontal +45 degree direction axis of the pixel giving the minimum cost. Also, with respect to the vertical +45 degree direction axis, the coordinates of the minimum pixel are obtained by the same processing as in FIG.

  Here, the minimum point of the fitting function is the minimum cost point, but the method of determining the minimum cost point using the fitting function can also be determined by a method other than the minimum point of the function, such as the intersection of two straight lines. In this example, the fitting is performed on the cost of the block shifted by the adjacent pixels on the axis, but the block to which the fitting is applied is not limited thereto.

  In the above description, the axis direction is inclined by 45 degrees with respect to the horizontal and vertical axes. However, as long as the axis includes integer pixels to which the fitting function can be applied, the same applies to the axis as shown in FIG. 6c, for example. You can go to That is, in this case, the fitting function may be obtained from the cost of the block that best matches the block 803 and the cost of the block moved in the inclination direction of the axis.

  In this way, it is possible to obtain the fitting function also in the axis other than the horizontal, vertical, and axes tilted by 45 degrees from these, and there is a high possibility that more accurate estimation can be performed.

  Next, a flowchart of sub-pel accuracy motion estimation using a fitting function in axes other than horizontal and vertical as shown in FIGS. 6b and 6c in the sub-pixel accuracy motion estimation unit 203 of FIG.

  First, in step 900, decimal pixel precision motion estimation is started. Next, in step 901, the cost calculation of neighboring pixels is performed with respect to one axis (for example, the axis in the horizontal +45 degree direction), and in step 903, the coordinates on the axis are obtained. In step 905, the cost of neighboring pixels is similarly calculated for the other axis (for example, the axis in the direction of vertical +45 degrees), and in step 907, the coordinates on the axis are obtained. Based on the coordinates on these two axes, the minimum cost pixel is determined in step 909. The process in step 909 is basically the same process, except that the horizontal axis and the vertical axis in the process of step 409 in FIG. 4 are changed to one axis and the other axis.

  In the flowchart of FIG. 8, the steps of processing the one axis and the other axis in parallel are shown, but these steps may be processed in series.

  Further, in the fractional pixel accuracy motion estimation unit 203 in FIG. 2, the minimum cost value and the minimum cost pixel position obtained in a plurality of axis pairs from among the axis pairs as shown in FIGS. 6 a, 6 b, and 6 c. May be selected so that the lower cost is selected. An example of a flowchart of this process is shown in FIG.

  In the example of FIG. 9, the fractional pixel accuracy motion estimation using the fitting function is performed on each of the two axis pairs out of the axis pairs shown in FIGS. 6a, 6b, and 6c. Here, the first axis pair will be described as a horizontal axis and a vertical axis, and the second axis pair will be described as an axis in the horizontal +45 degree direction and an axis in the vertical +45 degree direction. In this process, the results of sub-pixel precision motion estimation using the fitting function in the two axis pairs are compared.

  First, in step 1000, decimal pixel precision motion estimation is started. Next, in step 1001, sub-pixel accuracy motion estimation using a fitting function is performed on the horizontal axis and the vertical axis that are the first axis pair. That is, in the process in step 1001, for example, the processes in steps 400 to 409 in the flowchart of FIG. 4 are performed. Also, in step 1002, sub-pixel precision motion estimation using a fitting function is performed for the second axis pair, the horizontal +45 degree direction axis and the vertical +45 degree direction axis. That is, in the processing at step 1002, for example, the processing from steps 900 to 909 in the flowchart of FIG. 8 is performed. The processing in step 1003 may compare the minimum value of the fitting function or its approximate value, and select the pixel position with the smallest cost value. In addition, a new minimum cost value and minimum cost pixel position are calculated by performing further calculations using a plurality of minimum cost values and minimum cost pixel positions obtained by motion estimation of decimal pixels using fitting functions in a plurality of axis pairs. You may do it.

  In FIG. 9, two predetermined axis pairs are compared, but a method of selecting an arbitrary two-axis axis pair from a plurality of axis pairs and adopting the point that the cost is estimated to be the smallest It is good.

  In the present embodiment, matching in moving image coding is shown, but the present invention is not limited to moving image coding, and can be applied to matching processing in general.

  Although the block size used for matching has been described as a 4 × 4 block as an example in the present embodiment, it is not limited to this.

  Although this embodiment has been described as a moving image encoding device, when used as an image matching device, the integer pixel accuracy motion estimation unit 201 in FIG. 2 is replaced with an integer pixel accuracy image matching unit and a decimal pixel accuracy motion estimation unit 203. The decimal pixel image matching unit may be used to calculate the matching position of the image instead of calculating the motion vector.

  According to the embodiment described above, motion vector estimation can be performed with higher accuracy by performing sub-pixel precision motion estimation using a fitting function in axes other than the horizontal and vertical axes in image matching of video coding. Can be done.

  Also, by performing fractional pixel precision motion estimation using a fitting function in a plurality of axis pairs and comparing the results to estimate the motion vector, it is possible to estimate the motion vector with high accuracy with a small amount of computation. It becomes possible.

  In other words, the processing widely used in video coding including H.264 is to create an interpolated image and perform matching, while the interpolation processing and matching processing become very large, The motion vector search processing in the present embodiment applies a fitting function to the cost value obtained with integer pixel accuracy to estimate the motion vector with decimal pixel accuracy, and realizes a high-precision and high-speed motion vector search with decimal pixel accuracy. To do.

  Further, any of the embodiments described above can be used in combination to form an embodiment of the present invention.

  According to the matching method of the present invention described above, more accurate image matching can be performed with a smaller amount of calculation.

The figure which shows an example of the moving image encoder which concerns on one Example of this invention. The figure which shows the structural example of the motion estimation part which concerns on one Example of this invention. Explanatory drawing of an example of the cost minimum pixel estimation method which concerns on one Example of this invention. An example of a flowchart of a minimum cost pixel estimation method according to an embodiment of the present invention The figure which shows an example of the image recording / reproducing apparatus to which this invention is applied The figure which shows an example of the axis pair and cost distribution which concern on one Example of this invention The figure which shows an example of the axis pair and cost distribution which concern on one Example of this invention The figure which shows an example of the axis pair and cost distribution which concern on one Example of this invention Explanatory drawing of an example of the cost minimum pixel estimation method which concerns on one Example of this invention. An example of a flowchart of a minimum cost pixel estimation method according to an embodiment of the present invention An example of a flowchart of a minimum cost pixel estimation method according to an embodiment of the present invention

Explanation of symbols

DESCRIPTION OF SYMBOLS 100 ... Input part, 101 ... Input image, 102 ... Subtractor, 103 ... Conversion part, 104 ... Quantization part, 105 ... Prediction error and prediction error code amount, 106 ... Dequantization part, 107 ... Inverse conversion part, 108 ... adder 109 ... frame memory, 110 ... decoded image, 111 ... motion estimation unit using fitting function, 112 ... motion estimation result information, 113 ... motion compensation unit, 114 ... predicted image, 116 ... multiplexing unit, 201 ... Integer pixel accuracy motion estimator, 203 ... Decimal pixel accuracy motion estimator

Claims (9)

An integer pixel accuracy matching unit that performs image matching with integer pixel accuracy;
An image matching apparatus comprising: a decimal pixel accuracy matching unit that performs image matching with decimal pixel accuracy.   The decimal pixel accuracy matching unit calculates similarity of a plurality of image matching in a predetermined axial direction, and performs image matching with decimal pixel accuracy by using a fitting function calculated from the similarity. Image matching device.   The decimal pixel accuracy matching unit calculates a plurality of image matching similarities in a predetermined axial direction, and uses a fitting function calculated from the similarities to obtain a plurality of image matching positions and similarities at the positions. An image matching apparatus characterized in that a single image matching position is obtained by calculating and comparing the similarity at the plurality of image matching positions. Performing image matching with integer pixel accuracy;
And a step of performing image matching with decimal pixel accuracy. The step of performing image matching with the decimal pixel accuracy is as follows.
Obtaining a plurality of image matching similarities in a predetermined axial direction;
And a step of performing image matching with decimal pixel accuracy by using a fitting function obtained from the similarity. The step of performing image matching with the decimal pixel accuracy is as follows.
Obtaining a plurality of image matching similarities in a predetermined axial direction;
Calculating a plurality of image matching positions and similarities at the positions by using a fitting function obtained from the similarities;
An image matching method comprising: obtaining a single image matching position by comparing the plurality of image matching positions and the similarity at the positions.   An image matching apparatus used for encoding a moving image includes a block matching processing unit that performs a block matching process for each block obtained by dividing the moving image into a plurality of blocks, and uses a fitting function from a cost value of integer pixel accuracy. An image matching apparatus that performs motion estimation with decimal pixel accuracy.   8. The image matching apparatus according to claim 7, wherein a further detailed integer pixel precision or decimal precision search point can be obtained from a search result with integer pixel precision obtained by thinning points. . The image matching apparatus according to claim 7, wherein the feature detection unit performs fitting using samples in an oblique direction as well as in the horizontal axis and vertical axis directions, and uses both results or has a lower cost. A moving picture coding apparatus characterized by obtaining a decimal precision pixel.

Images