JP5347874B2 - Image processing apparatus, image processing method, and program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To shorten a processing time by reducing the amounts of an arithmetic operation even when a search range is relatively large in the case of using a method for comparing a first peak correlation value with a second peak correlation value as a method for evaluating the reliability of the association of a reference block with a candidate block in a search block in an image processor, an image processing method and a program. <P>SOLUTION: This image processor is provided with: a correlation arithmetic circuit for performing a correlation arithmetic operation to calculate the similarity of the reference region and search region of different video frames; and a peak evaluation circuit for associating the image of the reference region with the image of a candidate region in the search region by calculating the first peak position of a correlation value in the search region, and for evaluating the reliability of the association of the image of the reference region with the image of the candidate region in the search region by using a second correlation value by excluding an exclusion region in the neighborhood of the first peak position. The peak evaluation circuit divides the search range into a plurality of partial regions, and extracts the first peak correlation value in each partial region, and performs the sequencing of the first peak correlation value in each partial region, and determines a partial region for searching the second peak correlation value according to the sequencing. <P>COPYRIGHT: (C)2011,JPO&amp;INPIT

Description

  The present invention relates to an image processing apparatus, an image processing method, and a program for performing correlation calculation.

  In the image processing apparatus, the correlation calculation for calculating the similarity between two images is used in processes such as a motion vector measurement process and a stereo measurement process. As an example, a case where correlation calculation is used in motion vector measurement processing will be described as an example.

  FIG. 1 is a diagram for explaining the correlation calculation in the motion vector measurement process. In the motion vector measurement process, a local region of the video frame f is extracted as a reference block (or template) R, and a candidate block C having the maximum similarity with the reference block R in the search block S of the next video frame f + 1. Is extracted, the motion vector indicating how much the reference block R has moved in the next video frame f + 1 can be obtained. In the example of FIG. 1, the candidate block C can move within the search block S by −m to m−1 pixels in the horizontal direction and −n to n−1 pixels in the vertical direction. These are natural numbers.

  In order to extract the position of the candidate block C having the maximum similarity with the reference block R from within the search block S, an operation for obtaining the similarity within the reference block R is scanned two-dimensionally within the search block S. The candidate block C having the highest similarity is extracted. As the similarity index, for example, an SSD (Sum of Squared Difference) correlation value obtained by summing the squares of the luminance differences for each pixel in the block is used. For example, when the size of the reference block R is 8 × 8 pixels, the SSD correlation value can be expressed by the following equation. In the following equation, R (x, y) represents the reference block, and S (x, y) represents the luminance of the image of the search block S.

ＳＳＤ相関値Ｄ_ｋ（ｕ，ｖ）が最小となる（ｕ，ｖ）が、探索ブロックＳ内で参照ブロックＲとの類似度が最大となる探索ブロックＳの位置、即ち、参照ブロックＲの動きベクトルとなる。ＳＳＤ相関値は、類似度が高い場合に小さい値を有し、類似度が低い場合に大きな値を有する。

Although the SSD correlation value D _k (u, v) is minimum (u, v), the position of the search block S having the maximum similarity to the reference block R in the search block S, that is, the movement of the reference block R It becomes a vector. The SSD correlation value has a small value when the similarity is high, and has a large value when the similarity is low.

  As a method for evaluating the reliability of association between the image of the reference block R and the image of the candidate block C in the search block S, a method of comparing the first peak correlation value and the second peak correlation value is known. The first peak correlation value is the minimum correlation value in the search range (that is, the similarity is the maximum), and the second peak correlation value is the first peak position. Is the correlation value at the second peak point, which is the position having the minimum correlation value within the search range excluding the exclusion region in the vicinity of. When the difference between the first peak correlation value and the second peak correlation value is relatively large, since the correspondence between the image of the reference block R and the image of the candidate block C is only found, the image of the reference block R and the search block S It can be determined that the reliability of the association with the image of the candidate block C is high.

  For example, if the frame size is 640 × 480 pixels, the search block size is 32 × 32 pixels (m = 32, n = 32), and the candidate block size is 8 × 8 pixels, which is the same as the reference block size, The neighboring exclusion area is a rectangular area centered on the first peak position. The size of the rectangular area is, for example, 9 pixels in the horizontal direction and 9 pixels in the vertical direction (that is, 9 × 9 pixels). It corresponds to. However, the size of the region excluding the vicinity of the first peak position is not limited to 9 × 9 pixels in this example.

  In order to use the method for evaluating the reliability in this way, processing for obtaining the first peak position and the second peak position is required. Conventionally, the extraction of the first peak position and the second peak position has been performed by the following procedure. FIG. 2 is a diagram illustrating extraction of the first peak position, and FIG. 3 is a diagram illustrating extraction of the second peak position.

  First, as shown in FIG. 2, the first peak position having the minimum correlation value is extracted from all correlation values by performing a search within the search range corresponding to the search block S as indicated by the solid line arrow. To do.

  Next, as shown in FIG. 3, by performing a search within the search range corresponding to the search block S as indicated by a solid line arrow, an exclusion region Ex near the first peak position is selected from all correlation values. The minimum correlation value is obtained from the search range excluding, and the second peak position is extracted. 2 and 3, the broken line indicates the movement of the search position from the end position of one search (or line) to the start position of the next search (or line).

  In a conventional image processing apparatus using a method of comparing the first peak correlation value and the second peak correlation value as a method of evaluating the reliability of the association between the image of the reference block and the image of the candidate block in the search block, Since the process of obtaining the minimum correlation value from the correlation values is executed twice for the entire search range corresponding to the search block, the amount of calculation increases when the search range is relatively large, and the processing time is long. There was a problem of becoming.

  Therefore, the present invention uses a method of comparing the first peak correlation value and the second peak correlation value as a method of evaluating the reliability of the association between the reference block image and the candidate block image in the search block. An object of the present invention is to provide an image processing apparatus, an image processing method, and a program capable of reducing the amount of calculation and reducing the processing time even when the search range is relatively large.

  According to one aspect of the present invention, a correlation calculation circuit that performs a correlation calculation to obtain a correlation value as an index indicating the degree of similarity between a reference area of a first video frame and the reference area of a search area of a second video frame And associating the reference region image with the candidate region image in the search region by determining the first peak position of the correlation value in the search region, and excluding the vicinity of the first peak position A peak evaluation circuit that evaluates the reliability of association between the image of the reference region and the image of the candidate region in the search region using a second peak correlation value that is a second peak of the correlation value excluding the region A first peak correlation value that is a first peak of the correlation value indicates a maximum similarity, and the second peak correlation value indicates a second highest similarity after the first peak correlation value, and the peak evaluation circuit The search range includes a plurality of parts A partial region in which the first peak correlation value in each partial region is extracted, the first peak correlation value in each partial region is ordered, and the second peak correlation value is searched according to the ordering Is provided.

  According to an aspect of the present invention, there is provided a computer-based image processing method, wherein a correlation value is used as an index indicating a similarity between a reference area of a first video frame and the reference area of a search area of a second video frame. And calculating the first peak position of the correlation value in the search region based on the correlation value stored in the memory unit and the procedure of storing the correlation value in the memory unit The image of the reference region is associated with the image of the candidate region in the search region, and the exclusion region in the vicinity of the first peak position is excluded and the second peak correlation value that is the second peak of the correlation value is used. And causing the computer to execute a procedure for evaluating the reliability of the association between the image of the reference area and the image of the candidate area in the search area, and the first peak correlation value that is the first peak of the correlation value is the maximum The similarity of The second peak correlation value shows the next highest similarity after the first peak correlation value, and the procedure for evaluating the reliability divides the search range into a plurality of partial areas, There is provided an image processing method for extracting the first peak correlation value, ordering the first peak correlation values in each partial region, and determining a partial region to search for the second peak correlation value according to the ordering. .

  According to an aspect of the present invention, there is provided a program for causing a computer to execute image processing, and an index indicating a similarity between a reference area of a first video frame and the reference area of a search area of a second video frame Based on a procedure for performing correlation calculation to obtain a correlation value and storing the correlation value in a memory unit, and obtaining a first peak position of the correlation value in the search region based on the correlation value stored in the memory unit In this way, the image of the reference region is associated with the image of the candidate region in the search region, and the second peak correlation that is the second peak of the correlation value is excluded by excluding the excluded region in the vicinity of the first peak position. A first peak correlation that is a first peak of the correlation value, causing the computer to execute a procedure for evaluating the reliability of the association between the image of the reference region and the image of the candidate region in the search region using a value; value is The second peak correlation value indicates the next highest similarity after the first peak correlation value, and the procedure for evaluating the reliability divides the search range into a plurality of partial regions, A program that extracts the first peak correlation value in each partial region, orders the first peak correlation value in each partial region, and determines a partial region to search for the second peak correlation value according to the ordering. Provided.

  According to the disclosed image processing apparatus, image processing method, and program, the first peak correlation value and the second peak are used as a method for evaluating the reliability of the association between the reference block image and the candidate block image in the search block. When using a method for comparing correlation values, even if the search range is relatively large, it is possible to reduce the amount of calculation and shorten the processing time.

It is a figure explaining the correlation calculation in a motion vector measurement process. It is a figure explaining extraction of the 1st peak position. It is a figure explaining extraction of the 2nd peak position. 1 is a block diagram illustrating an image processing apparatus according to an embodiment of the present invention. It is a figure explaining the peak information stored in a peak register. It is a flowchart explaining an image process. It is a flowchart explaining a 1st peak extraction process. It is a flowchart explaining a 2nd peak extraction process. It is a figure explaining the case where the exclusion area | region of the vicinity of a 1st peak position is completely contained in a partial area. It is a figure explaining the case where the exclusion area | region of the vicinity of a 1st peak position straddles a partial area | region. It is a figure explaining the case where the 2nd-4th peak position is contained in the exclusion field near the 1st peak position. It is a block diagram explaining the image processing apparatus in the other Example of this invention.

  The disclosed image processing apparatus, image processing method, and program include a first peak correlation value indicating the maximum similarity as a method for evaluating the reliability of association between an image in a reference area and an image in a candidate area in a search area. And a method of comparing the second peak correlation value indicating the second highest similarity after the first peak correlation value. By dividing the search region into a plurality of partial regions, extracting the first peak correlation value in the range of each partial region, and narrowing down the partial region necessary for extracting the second peak correlation value, The processing time required to extract the second peak correlation value is shortened.

  Embodiments of the disclosed image processing apparatus, image processing method, and program will be described below with reference to the drawings.

  FIG. 4 is a block diagram illustrating an image processing apparatus according to an embodiment of the present invention. For convenience of explanation, in the present embodiment, as an example, a case where correlation calculation is used in motion vector measurement processing will be described.

In the motion vector measurement process, as shown in FIG. 1, the local region of the video frame f is extracted as a reference block (or reference region) R, and within the search block (or search region) S of the next video frame f + 1. By extracting the position of the candidate block (or candidate region) C having the maximum similarity with the reference block R, a motion vector indicating how much the reference block R has moved in the next video frame f + 1 is obtained. In order to extract the position of the candidate block C having the maximum similarity with the reference block R from within the search block S, an operation for obtaining the similarity within the reference block R is scanned two-dimensionally within the search block S. The candidate block C having the highest similarity is extracted. As the similarity index, for example, an SSD correlation value obtained by taking the sum of the squares of the luminance differences for each pixel in the block is used. In the formula described with reference to FIG. 1, the position of the search block S in which the SSD correlation value D _k (u, v) is minimum (u, v) but the similarity to the reference block R is maximum in the search block S. That is, it becomes the motion vector of the reference block R.

  Further, as a method for evaluating the reliability of association between the image of the reference block R and the image of the candidate block C in the search block S, a method of comparing the first peak correlation value and the second peak correlation value is used. The first peak correlation value is the minimum correlation value in the search range (that is, the similarity is the maximum), and the second peak correlation value is the first peak position. Is the correlation value at the second peak point, which is the position having the minimum correlation value within the search range excluding the exclusion region in the vicinity of. When the difference between the first peak correlation value and the second peak correlation value is relatively large, since the correspondence between the image of the reference block R and the image of the candidate block C is only found, the image of the reference block R and the search block S It can be determined that the reliability of the association with the image of the candidate block C is high.

  In the present embodiment, the search block S forming the search area is divided into a plurality of partial areas. Each partial region has a rectangular shape of the same size. The first peak correlation value is extracted in the range of each partial region, and the processing time required to extract the second peak is shortened by narrowing down the partial region necessary for extracting the second peak. To do. In addition, the exclusion region near the first peak position also has a rectangular shape having a size smaller than that of one partial region.

  The image processing apparatus 1 includes a control unit 11, an image memory 12, a correlation calculation circuit 13, a correlation value memory 14, and a peak evaluation circuit 15 connected as shown in FIG. For example, an imaging unit such as a camera 21 is connected to the image processing apparatus 1. The camera 21 may be connected to the control unit 11 or directly to the image memory 12.

  The control unit 11 is formed by a processor such as a CPU (Central Processing Unit), for example, and controls the entire image processing apparatus 1. In this example, the image memory 12 stores image data to be subjected to correlation calculation received from the camera 21, and transmits the image data to the correlation calculation circuit 13 during the correlation calculation process. The correlation calculation circuit 13 performs correlation calculation processing using the image data received from the image memory 12, and transmits the calculation result of the correlation calculation processing to the correlation value memory 14. The correlation value memory 14 stores the correlation calculation result received from the correlation calculation circuit 13 during the correlation calculation process, and reads the correlation calculation result and transmits it to the peak evaluation circuit 15 during the peak extraction process.

  The peak evaluation circuit 15 includes a peak evaluation control unit 151, a comparator 152, a peak register 153, comparators 154-1 to 154-5, and first to fifth peak registers 155-1 to 155-5, and is correlated. While calculating | requiring the 1st-5th peak of a value, a 1st peak and a 2nd peak are extracted.

  The peak evaluation control unit 151 is formed by a processor such as a CPU, for example, and controls peak evaluation processing. Specifically, the peak evaluation control unit 151 includes a partial area to be evaluated in the search block S of the video frame f + 1, an address for accessing the correlation value memory 14, and coordinates corresponding to the correlation value read from the correlation value memory 14. Control such as determination and determination of whether or not the determined coordinate is an excluded region in the vicinity of the first peak position is performed.

  Note that both the control unit 11 and the peak evaluation control unit 151 may be realized by a hardware circuit.

  The comparator 152 compares the correlation value read from the correlation value memory 14 with the correlation value of the peak register 153, and determines whether or not to update the first to fifth peak registers 155-1 to 155-5 for each partial region. Make a decision.

  The peak register 153 stores peak information of each partial area. FIG. 5 is a diagram for explaining the peak information stored in the peak register 153. As shown in FIG. 5, the peak register 153 stores the partial region number of the peak, the X coordinate value, the Y coordinate value, and the correlation value.

  The comparators 154-1 to 154-5 compare the peak information of the partial areas stored in the peak register 153, and obtain the peaks of the top five correlation values for each partial area, that is, the first to fifth peak correlation values. The corresponding first to fifth peak registers 155-1 to 155-5 are stored. The peak information stored in the first to fifth peak registers 155-1 to 155-5 also includes the partial area number of the peak, the X coordinate value, the Y coordinate value, and the correlation value as shown in FIG.

  FIG. 6 is a flowchart for explaining the image processing of the image processing apparatus 1, that is, the image processing method in this embodiment. In FIG. 6, step S <b> 1 reads image data from the image memory 12, performs correlation calculation processing in the correlation calculation circuit 13, and performs correlation calculation processing for storing the calculation result of the correlation calculation processing in the correlation value memory 14.

  Step S2 performs a first peak extraction process. In the first peak extraction process of step S2, in each partial region of the search block S, the correlation value is read from the correlation value memory 14 and a peak is extracted, and the top five correlation values are extracted from the extracted correlation value peaks for each partial region. The first to fifth peak correlation values are stored in the corresponding first to fifth peak registers 155-1 to 155-5. In this first peak extraction process, the first peak correlation value is obtained, and the first peak position and the first peak correlation value are stored in the first peak register 155-1.

  In step S3, a second peak extraction process is performed. In the second peak extraction process in step S3, the correlation is performed by excluding the excluded area near the first peak position from the partial areas of the partial area numbers stored in the first to fifth peak registers 155-1 to 155-5. Extract the value peak. When the second peak correlation value is determined, the second peak extraction process ends, and the second peak position and the correlation value are stored in the second peak register 155-2.

  For example, if the frame size is 640 × 480 pixels, the search block size is 32 × 32 pixels (m = 32, n = 32), and the candidate block size is 8 × 8 pixels, which is the same as the reference block size, The neighboring exclusion area is a rectangular area centered on the first peak position. The size of the rectangular area is, for example, 9 pixels in the horizontal direction and 9 pixels in the vertical direction (that is, 9 × 9 pixels). It corresponds to. However, the size of the region excluding the vicinity of the first peak position is not limited to 9 × 9 pixels in this example.

  When the difference between the first peak correlation value and the second peak correlation value is relatively large, the correlation between the image of the reference block R and the image of the candidate block C can be obtained uniquely, so that the peak evaluation circuit 15 It can be determined that the reliability of the association between the image and the image of the candidate block C in the search block S is high. In the motion vector measurement process, the correspondence between the image of the reference block R and the image of the candidate block C in the search block S is compared by comparing the first peak correlation value and the second peak correlation value thus obtained. However, since the motion vector measurement process itself is well known, detailed description thereof is omitted.

  FIG. 7 is a flowchart illustrating the first peak extraction process in step S2. The first peak extraction process repeats the process of obtaining the correlation value peak for each partial region of the search block S and the process of updating the first to fifth peak registers 155-1 to 155-5. In the following description, N (N is a natural number of 2 or more) indicates the number of partial areas, and the search area to be processed (that is, search block S) is divided into partial areas having partial area numbers B1 to BN. , B are the partial area numbers currently being processed. Bp is a partial area number stored in the peak register 153, Xp is an X coordinate value stored in the peak register 153, Yp is a Y coordinate value stored in the peak register 153, and Cp is a correlation value stored in the peak register 153 Indicates. PB1 to PB5 are partial area numbers stored in the first to fifth peak registers 155-1 to 155-1, and X1 to X5 are stored in the first to fifth peak registers 155-1 to 155-1. X coordinate values, Y1 to Y5 are Y coordinate values stored in the first to fifth peak registers 155-1 to 155-1, and C1 to C5 are stored in the first to fifth peak registers 155-1 to 155-1. The correlation value to be shown.

  In FIG. 7, step S21 sets the partial area number B to B = 1. In step S22, the peak of the correlation value is extracted in the partial area of the partial area number B, the extracted peak position (Xp, Yp) and the correlation value Cp are obtained and set in the peak register.

  In step S23, the first to fifth peak registers 155-1 to 155-5 are updated for the partial region B (in this case, B1). When the correlation value of the peak register 153 is larger than the contents of the first peak register 155-1, the contents of the first to fourth peak registers 155-1 to 155-4 are changed to the second to fifth peak registers 155-2 to 155. The value is shifted (or copied) to -5, and the correlation value of the peak register 153 is set in the first peak register 155-1. When the correlation value of the peak register 153 is smaller than the contents of the first peak register 155-1 and larger than the contents of the second peak register 155-2, the contents of the second to fourth peak registers 155-2 to 155-5 are changed. Shifting (or copying) to the third to fifth peak registers 155-3 to 155-5, and the correlation value of the peak register 153 is set in the second peak register 155-2. Such determination is repeated until the fifth peak register 155-5 is shifted in contents.

  A step S24 increments the partial area number B to B = B + 1. In step S25, it is determined whether or not B> N. If the determination result is NO, the process returns to step S22, and if the determination result is YES, the process ends.

  By such processing, out of the correlation value peaks of all (N) partial regions constituting the search block S, the first to fifth peak correlation values and the first to fifth peak positions are obtained and corresponding. The contents of the first to fifth peak registers 155-1 to 155-5 are updated by being stored in the first to fifth peak registers 155-1 to 155-5. When this process is completed, the first peak correlation value of the entire search region is determined and stored in the first peak register 155-1.

  FIG. 8 is a flowchart for explaining the second peak extraction process in step S3. In the second peak extraction process, the peak evaluation process of the partial areas excluding the excluded area in the vicinity of the first peak position is sequentially performed, and the process ends when the second peak correlation value is determined.

  In FIG. 8, step S31 sets the partial area number B to the partial area number PB1 stored in the first peak register 155-1. In step S32, the correlation value peak is extracted by excluding the excluded region near the first peak position in the partial region of the partial region number B. In step S31, the peak position (Xp, Yp) of the partial region and the correlation value Cp are obtained and set in the peak register 153.

  In step S33, the correlation value Cp of the peak register 153 and the correlation value C2 of the second peak register 155-2 are compared, and it is determined whether or not Cp <C2. If the correlation value Cp is smaller than the correlation value C2 and the determination result in step S33 is YES, it is determined that the correlation value peak in this partial region is the second peak correlation value. In this case, step S37 stores the content of the peak register 153 in the second peak register 155-2, and the process ends.

  If the decision result in the step S33 is NO, a step S34 reads the coordinates (X2, Y2) stored in the second peak register 155-2, and the coordinates (X2, Y2) are read as the first peak position (X1 , Y1), it is determined whether it is outside the excluded area. If the coordinate (X2, Y2) is outside the excluded region near the first peak position (X1, Y1) and the determination result in step S34 is YES, the second peak correlation value is determined, and the process ends. On the other hand, if the decision result in the step S34 is NO, the peak position (X2, Y2) stored in the second peak register 155-2 is in the excluded area near the first peak position, so the first peak position It is necessary to perform the second peak extraction process on the partial area of the partial area number B2 set in the second peak register 155-2 by excluding the excluded area in the vicinity. Therefore, if the decision result in the step S34 is NO, a step S35 sets the partial area number PB2 to the partial area number B and sets B = PB2.

  In step S36, the contents of the third to fifth peak registers 155-3 to 155-5 are shifted (or copied) to the second to fourth peak registers 155-2 to 155-4, and the second peak register 155- After updating the content of 2, the process returns to step S32 to perform the second peak extraction process for the next partial region. In this way, the second peak correlation value is determined and stored in the second peak register 155-2.

  Next, when the excluded region near the first peak position is completely included in the partial region, when the excluded region near the first peak position straddles the partial region, and when the excluded region near the first peak position is The operation when the second to fourth peak positions are included will be described with reference to FIGS.

  FIG. 9 is a diagram illustrating a case where the excluded region near the first peak position is completely included in the partial region. 9 and FIG. 10 and FIG. 11 described later, for convenience of explanation, it is assumed that the search region S is divided into partial regions B1 to B12, and the position of the extracted first peak P1 is indicated by a black circle, The positions of the fifth peaks P2 to P5 are indicated by white circles, and the excluded area near the first peak position is indicated by Ex.

  As shown in FIG. 9, it is assumed that as a result of performing the first peak extraction process of FIG. 7, the first to fifth peaks P1 to P5 are extracted in the following partial region.

First peak P1: Within partial region B6 Second peak P2: Within partial region B3 Third peak P3: Within partial region B4 Fourth peak P4: Within partial region B8 Fifth peak P5: Within partial region B12 In this example, The exclusion region Ex near the position of one peak P1 is completely included in one partial region B6.

  Therefore, in this example, the second peak extraction process of FIG. 8 extracts the correlation value peak by excluding the exclusion region Ex in the vicinity of the first peak P1 in the partial region B6, and the peak ( Hereinafter, the position (Xp, Yp) of Pp and the correlation value Cp are obtained (referred to as “partial region peak”) (step S32).

  If the correlation value Cp at the partial region peak Pp is smaller than the correlation value C2 at the second peak P2 (YES in step S33), it is determined that the partial region peak Pp is the second peak correlation value. The contents of 153 are stored in the second peak register 155-2 (step S37), and the second peak extraction process ends.

  On the other hand, if the correlation value Cp at the partial region peak Pp is greater than or equal to the correlation value C2 at the second peak P2 (NO in step S33), the coordinates (X2, Y2) stored in the second peak register 155-2. To determine whether or not it is in the exclusion area Ex near the coordinates (X1, Y1) of the first peak P1 (step S34). In this example, the coordinates (X2, Y2) read from the second peak register 155-2 are present in the partial area B3 outside the excluded area Ex near the first peak P1 (YES in step S34). The coordinates (X2, Y2) stored in the second peak register 155-2 are determined to be the position of the second peak correlation value, and the process ends.

  FIG. 10 is a diagram for explaining a case where the excluded region in the vicinity of the first peak position straddles the partial region.

  As shown in FIG. 10, it is assumed that the first to fifth peaks P1 to P5 are extracted in the following partial region as a result of performing the first peak extraction process of FIG.

First peak P1: Within partial region B6 Second peak P2: Within partial region B3 Third peak P3: Within partial region B4 Fourth peak P4: Within partial region B8 Fifth peak P5: Within partial region B12 In this example, An excluded area Ex near the position of one peak P1 extends over a plurality of partial areas B2, B3, B6, and B7.

  Therefore, in this example, the second peak extraction process of FIG. 8 extracts the correlation value peak by excluding the excluded area Ex in the vicinity of the first peak P1 in the partial area B6, and the position of the partial area peak Pp. (Xp, Yp) and a correlation value Cp are obtained (step S32).

  If the correlation value Cp at the partial region peak Pp is smaller than the correlation value C2 at the second peak P2 (YES in step S33), it is determined that the partial region peak Pp is the second peak correlation value. The contents of 153 are stored in the second peak register 155-2 (step S37), and the second peak extraction process ends.

  On the other hand, if the correlation value Cp at the partial region peak Pp is greater than or equal to the correlation value C2 at the second peak P2 (NO in step S33), the coordinates stored in the second peak register 155-2 are read out, and the first It is determined whether or not it is in the exclusion area Ex near the peak P1 (step S34). In this example, the coordinates read from the second peak register 155-2 exist in the exclusion area Ex near the first peak P1 (NO in step S34). Therefore, B3 is set as the partial region number B (step S35), and after the correlation value peak is extracted in the partial region B3, the third to fifth peak registers 155-3 to 155-5 are used. Is shifted (or copied) to the second to fourth peak registers 155-2 to 155-4, and the contents of the second peak register 155-2 are updated (step S36). In this case, information on the third peak P3 of the partial region B4 is stored in the second peak register 155-2.

  Next, a correlation value peak is extracted by excluding the excluded region Ex in the vicinity of the first peak P1 in the partial region B3, and the position (Xp, Yp) of the partial region peak Pp and the correlation value Cp are obtained.

  If the correlation value Cp at the partial region peak Pp is smaller than the correlation value stored in the second peak register 155-2 (correlation value at the third peak P3 of the partial region B4 at this time) (in step S32) YES), since it is determined that the partial region peak Pp is the second peak correlation value, the contents of the peak register 153 are stored in the second peak register 155-2 (step S37), and the second peak extraction process is completed. .

  On the other hand, when the correlation value Cp at the partial region peak Pp is equal to or higher than the correlation value stored at the second peak register 155-2 (correlation value at the third peak P3 of the partial region B4 at this time) (step). NO in S33), the coordinates stored in the second peak register 155-2 are read out, and it is determined whether or not it is in the exclusion area Ex near the first peak P1 (step S34). In this example, since the coordinates read from the second peak register 155-2 exist outside the excluded area Ex near the first peak P1 (YES in step S34), they are stored in the second peak register 155-2. It is determined that the third peak P3 of the partial region B4 is the second peak correlation value, and the second peak extraction process ends.

  FIG. 11 is a diagram illustrating a case where the second to fourth peak positions are included in the excluded region in the vicinity of the first peak position.

  As shown in FIG. 11, it is assumed that the first to fifth peaks P1 to P5 are extracted in the following partial region as a result of performing the first peak extraction process of FIG.

First peak P1: Within partial region B6 Second peak P2: Within partial region B3 Third peak P3: Within partial region B2 Fourth peak P4: Within partial region B7 Fifth peak P5: Within partial region B12 In this example, Exclusion region Ex in the vicinity of the position of one peak P1 extends over a plurality of partial regions B2, B3, B6, B7, and the second to fourth peaks P2 to P4 are excluded in the vicinity of the position of the first peak P1. It exists in the area Ex.

  In this example, in the second peak extraction process of FIG. 8, peak evaluation is necessary for all of the partial area B6, the partial area B3, the partial area B2, and the partial area B7. Maximum. Note that the details of the second peak extraction process in this example are clear from the description of FIGS. 9 and 10, and therefore the description thereof is omitted.

  In the above embodiment, the image processing shown in FIGS. 6 to 8 is executed by the image processing apparatus 1 shown in FIG. 4, that is, hardware. However, at least a part of the image processing may be executed by software. In this case, the image processing program (that is, software) causes the computer to execute at least part of the image processing procedure, or functions as means for configuring the computer to form at least part of the image processing apparatus 1 shown in FIG. Or a computer that realizes at least a part of the functions of the image processing apparatus 1. Needless to say, the computer may execute a program stored in a computer-readable storage medium or an image processing program downloaded from outside the computer.

  FIG. 12 is a diagram for explaining an image processing apparatus according to another embodiment of the present invention. For convenience of explanation, it is assumed that the correlation calculation is also used in the motion vector measurement process in this embodiment.

  An image processing apparatus 201 illustrated in FIG. 12 has a configuration in which a CPU 211, a memory unit 212, a transmission / reception unit 213, an operation unit 214 having a plurality of operation keys, a display unit 215, and a camera 216 are connected by a bus 218. The CPU 211 controls the operation of the entire image processing apparatus 201. The memory unit 212 is formed of a semiconductor storage device, a disk device, or the like that stores various data including a program executed by the CPU 211 and intermediate data of operations performed by the CPU 211. Therefore, the memory unit 212 includes the functions of the image memory 12 and the correlation value memory 14 of FIG. 4 and may include the functions of the peak registers 153 and 155-1 to 155-5. The transmission / reception unit 213 has a known configuration for performing transmission / reception via an antenna (not shown) or a network (not shown) such as the Internet, and includes a modem function. The operation unit 214 includes a plurality of operation keys that are operated when a user inputs instructions and information to the image processing apparatus 201. The display unit 215 displays various operation menus, information input from operation keys, images to be processed, and the like. Note that the operation unit 214 and the display unit 215 may be provided integrally as in the case of a touch panel. The camera 216 has a known configuration capable of capturing an image of a subject, and corresponds to the camera 21 shown in FIG. The functions of the peak registers 153, 155-1 to 155-5 may be realized by a register (not shown) in the CPU 211.

  The image processing program stored in the memory unit 12 causes at least a part of the image processing procedure to be executed by a computer formed by at least the CPU 211 and the memory unit 212, or the image processing apparatus 1 shown in FIG. Or at least a part of the functions of the image processing apparatus 1 is realized by a computer. The computer-readable storage medium for storing the image processing program is the memory unit 12 in this embodiment, but the type of the computer-readable storage medium for storing the image processing program is not particularly limited, and is a semiconductor storage device. Alternatively, it may be a magnetic storage medium such as a disk, an optical storage medium, or a magneto-optical storage medium. The computer may execute an image processing program downloaded from outside the computer via the transmission / reception unit 213.

  By the way, in an image processing apparatus capable of performing correlation value peak evaluation processing once per cycle, the search range is L × M pixels (L and M are two or more natural numbers satisfying L = M or L ≠ M). Assuming there is a conventional technique, the first peak evaluation process requires L × M cycles, and the second peak evaluation process requires 2 × L × M cycles in total. On the other hand, according to each of the above embodiments, if the number of partial areas (ie, the number of divisions of the search area) is N, the first peak evaluation process is L × M cycles, and the second peak evaluation process is at worst (L * M / N) * Only 4 cycles are required. As described above, when the overhead of the first peak evaluation process by dividing the search area into partial areas as in the above embodiments is O1 (N) and the overhead of the second peak evaluation process is O2 (N), The processing time T required for the first peak evaluation process and the second peak evaluation process is (1 + 4 / N) × L × M + O1 (N) + O2 (N) cycles.

  For example, when L = 64, M = 64, N = 16, O1 = 128, and O2 = 32, the conventional method requires a processing time T = 8192 cycles, whereas in each of the above embodiments, the processing time T = It can be shortened to 5280 cycles. As described above, when the values of L and M are relatively large and the amount of overhead due to the division of the search area is relatively small, it is confirmed that the processing time T can be shortened in each of the above embodiments as compared with the conventional method. It was done.

  As the number of partial areas increases, the overhead of processing associated with the division of the search area increases. Therefore, the overheads O1 (N) and O2 (N) are functions of N. Therefore, it is desirable to select the number N of partial areas to be used so as to minimize the processing time T.

  In each of the above embodiments, the SSD correlation value is used as an index indicating the degree of similarity between two images. However, the present invention uses other correlations such as an SAD (Sum of Absolute Difference) correlation value as an index indicating the degree of similarity. The same applies to the case of using a value. For example, the present invention can be similarly applied by changing the order of extracting correlation value peaks from the minimum to the maximum even when a normalized cross correlation (NCC) value is used as an index indicating similarity. It is. The NCC value has a large value when the similarity is high, and a small value when the similarity is low.

  The image data to be subjected to image processing is not limited to the luminance value of the pixel, and may be, for example, the values of the three primary color components of the pixels constituting the color image data. In other words, the image processing may be performed on the values of the single red component, the single blue component, or the single green component of the color image data.

The following additional notes are further disclosed with respect to the embodiment including the above examples.
(Appendix 1)
A correlation calculation circuit that performs a correlation calculation to obtain a correlation value as an index indicating the similarity between the reference area of the first video frame and the reference area of the search area of the second video frame;
By associating the image of the reference area with the image of the candidate area in the search area by obtaining the first peak position of the correlation value in the search area, an excluded area in the vicinity of the first peak position is determined. A peak evaluation circuit that evaluates the reliability of the correspondence between the image of the reference region and the image of the candidate region in the search region using the second peak correlation value that is the second peak of the correlation value by excluding,
The first peak correlation value, which is the first peak of the correlation value, indicates the maximum similarity, the second peak correlation value indicates the second highest similarity after the first peak correlation value,
The peak evaluation circuit divides the search range into a plurality of partial areas, extracts the first peak correlation values in each partial area, and orders the first peak correlation values in each partial area, An image processing apparatus that determines a partial region to search for the second peak correlation value according to ordering.
(Appendix 2)
The peak evaluation circuit performs peak evaluation by excluding an excluded region in the vicinity of the first peak position in the determined partial region, and compares and determines the peak correlation value in each of the ordered partial regions. The image processing apparatus according to appendix 1, wherein the second peak correlation value is searched based on the first peak correlation value.
(Appendix 3)
The peak evaluation circuit includes:
Means for extracting a first peak correlation value within each partial region;
Means for ordering the first peak correlation values extracted in each partial region to obtain first to fifth peak correlation values and storing them in the first to fifth registers;
Means for selecting a partial area for searching for a second peak correlation value in order from an arbitrary partial area, and excluding an excluded area in the vicinity of the first peak position in each selected partial area; ,
The second peak correlation value is determined by comparing the peak correlation value obtained by searching for the peak correlation value with the second to fifth peak correlation values ordered by the order of the first peak correlation values in each partial region. The image processing apparatus according to attachment 2, further comprising means for performing:
(Appendix 4)
The image processing apparatus according to claim 1, wherein each of the reference area, the search area, the candidate area, and the partial area has a rectangular shape.
(Appendix 5)
The image processing apparatus according to any one of appendices 1 to 4, wherein the excluded area in the vicinity of the first peak position has a rectangular shape smaller in size than one partial area.
(Appendix 6)
The correlation value is one correlation value selected from a group of SSD (Sum of Squared Difference) correlation value, SAD (Sum of Absolute Difference) correlation value, and Normalized Cross Correlation (NCC) value. The image processing apparatus according to any one of appendices 1 to 5.
(Appendix 7)
An image processing method by a computer,
A procedure for performing a correlation operation to obtain a correlation value as an index indicating the similarity between the reference area of the first video frame and the reference area of the search area of the second video frame, and storing the correlation value in a memory unit;
Correspondence between the image of the reference region and the image of the candidate region in the search region by obtaining the first peak position of the correlation value in the search region based on the correlation value stored in the memory unit And excluding the excluded region in the vicinity of the first peak position and using the second peak correlation value, which is the second peak of the correlation value, between the image of the reference region and the image of the candidate region in the search region Causing the computer to execute a procedure for evaluating the reliability of the correspondence;
The first peak correlation value, which is the first peak of the correlation value, indicates the maximum similarity, the second peak correlation value indicates the second highest similarity after the first peak correlation value,
The procedure for evaluating the reliability includes dividing the search range into a plurality of partial areas, extracting the first peak correlation values in each partial area, and ordering the first peak correlation values in each partial area. And determining a partial region to search for the second peak correlation value according to the ordering.
(Appendix 8)
In the procedure for evaluating the reliability, a peak evaluation is performed by excluding an excluded region in the vicinity of the first peak position in the determined partial region, and a peak correlation value in each of the ordered partial regions is calculated. The image processing method according to appendix 7, wherein the second peak correlation value is searched based on the comparison determination.
(Appendix 9)
The procedure for evaluating the reliability includes:
Extracting a first peak correlation value within each partial region;
Order the first peak correlation values extracted in each partial area to obtain the first to fifth peak correlation values,
A partial region for searching for the second peak correlation value is selected in order from an arbitrary partial region, and an excluded region in the vicinity of the first peak position is excluded in each selected partial region to search for a peak correlation value.
The second peak correlation value is determined by comparing the peak correlation value obtained by searching for the peak correlation value with the second to fifth peak correlation values ordered by the order of the first peak correlation values in each partial region. The image processing method according to appendix 8.
(Appendix 10)
The image processing method according to any one of appendices 7 to 9, wherein each of the reference area, the search area, the candidate area, and the partial area has a rectangular shape.
(Appendix 11)
The image processing method according to any one of appendices 7 to 10, wherein the exclusion region in the vicinity of the first peak position has a rectangular shape smaller in size than one partial region.
(Appendix 12)
The correlation value is one correlation value selected from a group of SSD (Sum of Squared Difference) correlation value, SAD (Sum of Absolute Difference) correlation value, and Normalized Cross Correlation (NCC) value. The image processing method according to any one of appendices 7 to 11.
(Appendix 13)
A program for causing a computer to execute image processing,
A procedure for performing a correlation operation to obtain a correlation value as an index indicating the similarity between the reference area of the first video frame and the reference area of the search area of the second video frame, and storing the correlation value in a memory unit;
Correspondence between the image of the reference region and the image of the candidate region in the search region by obtaining the first peak position of the correlation value in the search region based on the correlation value stored in the memory unit And excluding the excluded region in the vicinity of the first peak position and using the second peak correlation value, which is the second peak of the correlation value, between the image of the reference region and the image of the candidate region in the search region Causing the computer to execute a procedure for evaluating the reliability of the correspondence;
The first peak correlation value, which is the first peak of the correlation value, indicates the maximum similarity, the second peak correlation value indicates the second highest similarity after the first peak correlation value,
The procedure for evaluating the reliability includes dividing the search range into a plurality of partial areas, extracting the first peak correlation values in each partial area, and ordering the first peak correlation values in each partial area. And determining a partial region to search for the second peak correlation value according to the ordering.
(Appendix 14)
In the procedure for evaluating the reliability, a peak evaluation is performed by excluding an excluded region in the vicinity of the first peak position in the determined partial region, and a peak correlation value in each of the ordered partial regions is calculated. The program according to appendix 13, wherein the second peak correlation value is searched based on the comparison determination.
(Appendix 15)
The procedure for evaluating the reliability includes:
Extracting a first peak correlation value within each partial region;
Order the first peak correlation values extracted in each partial area to obtain the first to fifth peak correlation values,
A partial region for searching for the second peak correlation value is selected in order from an arbitrary partial region, and an excluded region in the vicinity of the first peak position is excluded in each selected partial region to search for a peak correlation value.
The second peak correlation value is determined by comparing the peak correlation value obtained by searching for the peak correlation value with the second to fifth peak correlation values ordered by the order of the first peak correlation values in each partial region. The program according to appendix 14.
(Appendix 16)
The program according to any one of appendices 13 to 15, wherein each of the reference area, the search area, the candidate area, and the partial area has a rectangular shape.
(Appendix 17)
The program according to any one of appendices 13 to 16, wherein the exclusion region in the vicinity of the first peak position has a rectangular shape smaller in size than one partial region.
(Appendix 18)
The correlation value is one correlation value selected from a group of SSD (Sum of Squared Difference) correlation value, SAD (Sum of Absolute Difference) correlation value, and Normalized Cross Correlation (NCC) value. 18. The program according to any one of appendices 13 to 17.

  The disclosed image processing apparatus, image processing method, and program have been described above by way of the embodiments. However, the present invention is not limited to the above embodiments, and various modifications and improvements can be made within the scope of the present invention. Needless to say.

DESCRIPTION OF SYMBOLS 1,201 Image processing apparatus 11 Control part 12 Image memory 13 Correlation calculation circuit 14 Correlation value memory 15 Peak evaluation circuit 21,216 Camera 211 CPU
212 Memory unit

Claims (5)

A correlation calculation circuit that performs a correlation calculation to obtain a correlation value as an index indicating the similarity between the reference area of the first video frame and the reference area of the search area of the second video frame;
By associating the image of the reference area with the image of the candidate area in the search area by obtaining the first peak position of the correlation value in the search area, an excluded area in the vicinity of the first peak position is determined. A peak evaluation circuit that evaluates the reliability of the correspondence between the image of the reference region and the image of the candidate region in the search region using the second peak correlation value that is the second peak of the correlation value by excluding,
The first peak correlation value, which is the first peak of the correlation value, indicates the maximum similarity, the second peak correlation value indicates the second highest similarity after the first peak correlation value,
The peak evaluation circuit divides the search range into a plurality of partial areas, extracts the first peak correlation values in each partial area, and orders the first peak correlation values in each partial area, An image processing apparatus that determines a partial region to search for the second peak correlation value according to ordering.   The peak evaluation circuit performs peak evaluation by excluding an excluded region in the vicinity of the first peak position in the determined partial region, and compares and determines the peak correlation value in each of the ordered partial regions. The image processing apparatus according to claim 1, wherein the second peak correlation value is searched based on the second peak correlation value. The peak evaluation circuit includes:
Means for extracting a first peak correlation value within each partial region;
Means for ordering the first peak correlation values extracted in each partial region to obtain first to fifth peak correlation values and storing them in the first to fifth registers;
Means for excluding an excluded region near the first peak position in each partial region and searching for a peak correlation value;
The second peak correlation value is determined by comparing the peak correlation value obtained by searching for the peak correlation value with the second to fifth peak correlation values ordered by the order of the first peak correlation values in each partial region. The image processing apparatus according to claim 2, further comprising: An image processing method by a computer,
A procedure for performing a correlation operation to obtain a correlation value as an index indicating the similarity between the reference area of the first video frame and the reference area of the search area of the second video frame, and storing the correlation value in a memory unit;
Correspondence between the image of the reference region and the image of the candidate region in the search region by obtaining the first peak position of the correlation value in the search region based on the correlation value stored in the memory unit And excluding the excluded region in the vicinity of the first peak position and using the second peak correlation value, which is the second peak of the correlation value, between the image of the reference region and the image of the candidate region in the search region Causing the computer to execute a procedure for evaluating the reliability of the correspondence;
The first peak correlation value, which is the first peak of the correlation value, indicates the maximum similarity, the second peak correlation value indicates the second highest similarity after the first peak correlation value,
The procedure for evaluating the reliability includes dividing the search range into a plurality of partial areas, extracting the first peak correlation values in each partial area, and ordering the first peak correlation values in each partial area. And determining a partial region to search for the second peak correlation value according to the ordering. A program for causing a computer to execute image processing,
A procedure for performing a correlation operation to obtain a correlation value as an index indicating the similarity between the reference area of the first video frame and the reference area of the search area of the second video frame, and storing the correlation value in a memory unit;
Correspondence between the image of the reference region and the image of the candidate region in the search region by obtaining the first peak position of the correlation value in the search region based on the correlation value stored in the memory unit And excluding the excluded region in the vicinity of the first peak position and using the second peak correlation value, which is the second peak of the correlation value, between the image of the reference region and the image of the candidate region in the search region Causing the computer to execute a procedure for evaluating the reliability of the correspondence;
The first peak correlation value, which is the first peak of the correlation value, indicates the maximum similarity, the second peak correlation value indicates the second highest similarity after the first peak correlation value,
The procedure for evaluating the reliability includes dividing the search range into a plurality of partial areas, extracting the first peak correlation values in each partial area, and ordering the first peak correlation values in each partial area. And determining a partial region to search for the second peak correlation value according to the ordering.

Images