JP2008090583A - Information processing system, program, and information processing method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide an information processing technique for accurately and rapidly searching for a corresponding point between two images picked up from different viewing points. <P>SOLUTION: An information processing system, which obtains a standard image and a reference image using a stereo camera, computes using SAD method a correlation value between an image within a window set on the standard image and each image in each of a plurality of windows set on the reference image, thereby searching for the corresponding point on the reference image that corresponds to a designated point on the standard image. The form of a graph showing the relationship between each parallax obtained through this correlation computation (the position of each window on the reference image) and the correlation value is analyzed; (b) if two or more extremal points J1, J2 are detected and (c)-(e) if no extremal point is detected, the window size is changed and the corresponding point is again searched. In this way, the corresponding point can be searched accurately and rapidly. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

  The present invention relates to an information processing technique for performing processing related to a first image and a second image captured and acquired from different viewpoints.

  Each pixel of two images captured and acquired from different viewpoints by a stereo camera is associated with each other, and the three-dimensional position of each point on the image is calculated from the obtained correspondence based on the principle of triangulation How to do is known.

  FIG. 12 is a diagram schematically illustrating a method of calculating a three-dimensional position from the corresponding points between images based on the principle of triangulation.

  When the difference between the corresponding point positions of the reference camera and the reference camera is Δd, the distance D to the object is calculated by the following equation.

D = fB / Δd:
However, the reference length of the camera is B, and the focal length of the camera lens is f.

  At this time, the three-dimensional position (X, Y, Z) of the object is calculated by the following equation.

X = xD / f, Y = yD / f, Z = D:
However, the above x and y are the coordinates of the target pixel on the reference image.

  For example, the similarity (correlation) between an image in a window set on one image (reference image) and an image in each window set on the other image (reference image) that is the same size as this window There is a method of searching for a corresponding point between two images by obtaining a value) using SAD or the like and specifying a window position on a reference image having the highest similarity. If such a corresponding point search method is used, it is possible to acquire a three-dimensional position regarding each point on the captured image obtained by the stereo camera.

  However, in the above-described corresponding point search method, since the similarity of images is determined using a window of a certain size, the window size is not necessarily an appropriate size (for example, a size determined according to a change in image density). It is not always set, and there is a problem that high-precision corresponding point search cannot be performed satisfactorily.

  As a technique for improving this problem, there is one disclosed in Patent Document 1, for example. In this technique, windows of different sizes are set as a standard image and a reference image, and the accuracy of corresponding point search is improved by determining the similarity of images in these windows.

Japanese Patent Laid-Open No. 10-320561

  However, in the technique of the above-mentioned patent document 1, since the calculation of similarity must be performed in each window of different sizes, the calculation time increases, and it is difficult to quickly search for corresponding points between images. It is.

  The present invention has been made in view of the above problems, and an object of the present invention is to provide an information processing technique capable of quickly and accurately searching for corresponding points between two images captured and acquired from different viewpoints.

  In order to solve the above problems, the invention of claim 1 is an information processing system that performs processing related to a first image and a second image captured and acquired from different viewpoints, and (a) on the first image. A first search means for searching for a corresponding point on the second image corresponding to the specified specified point; and (b) a second corresponding point different from the first corresponding point searching process performed by the first searching means. A second search means for searching for a corresponding point on the second image corresponding to the specified point on the first image by a search process; and (c) searching for a corresponding point by the first corresponding point search process. And determining means for determining whether or not to perform re-searching of corresponding points by the second corresponding point search process, based on the acquired information obtained through the first corresponding point search process, The first search means (a-1) has a predetermined size and includes the designated point. (A-2) second setting means for setting the second area having the predetermined size at a plurality of positions in the second image; a-3) correlation calculating means for calculating a correlation value related to the image in the first area and the image in the second area at each position of the second area set by the second setting means; -4) means for searching for corresponding points on the second image based on the correlation value calculated by the correlation calculation means, and the acquired information is the second area obtained by the correlation calculation means Extreme value information acquired from the relationship between each position and the correlation value.

  Further, the invention according to claim 2 is the information processing system according to claim 1, wherein the second corresponding point search processing is performed in the first corresponding point search processing in the first corresponding point search processing. It is a corresponding point search process performed by setting the size to another size different from the predetermined size.

  According to a third aspect of the present invention, in the information processing system according to the second aspect of the present invention, the different size is a size set based on contrast information relating to an image in the first region.

  According to a fourth aspect of the present invention, in the information processing system according to any one of the first to third aspects, the acquired information is information on the number of extreme points related to the maximum value of the correlation value. .

  According to a fifth aspect of the present invention, in the information processing system according to the fourth aspect of the present invention, the extreme value point includes a first condition in which the maximum value related to the correlation value is greater than a first threshold, and a maximum value. The point of the maximum value satisfying the second condition in which the ratio of the correlation value calculated at the position of the second region set adjacent to the position of the second region to be taken is smaller than the second threshold value. is there.

  The invention according to claim 6 is the information processing system according to claim 4 or claim 5, wherein the determining means is (c-1) when the number of extreme points is 1, There is means for determining not to perform the corresponding point re-search by the second corresponding point search process.

  The invention according to claim 7 is the information processing system according to claim 2 or claim 3, wherein the acquired information is information on the number of extreme points related to the maximum value of the correlation value, and the determination is performed. (C-2) a second unit for calculating the correlation value only at each position of the second region related to each of the two or more extreme points when the number of the extreme points is two or more; Means for determining the corresponding point re-search by the corresponding point searching process.

  According to an eighth aspect of the present invention, in the information processing system according to the first aspect of the invention, the second corresponding point search process is a corresponding point search process using a phase-only correlation method.

  The invention of claim 9 is a program for causing an information processing system to function as the information processing system according to any one of claims 1 to 8 by being executed by a computer mounted on the information processing system. It is.

  The invention of claim 10 is an information processing method for performing processing related to a first image and a second image captured and acquired from different viewpoints, and (a) a designated point designated on the first image A first search step for searching for a corresponding point on the corresponding second image; and (b) a second corresponding point search process different from the first corresponding point search process performed in the first search step. A second search step of searching for a corresponding point on the second image corresponding to a specified point on one image; and (c) a search for a corresponding point by the first corresponding point searching process, A determination step for determining whether or not to perform a corresponding point re-search by the second corresponding point search process, based on the acquired information obtained through the corresponding point search process, wherein the first search step includes: (a-1) A first area having a predetermined size and including the designated point is defined as the first image. A first setting step for setting; (a-2) a second setting step for setting the second region having the predetermined size at a plurality of positions in the second image; and (a-3) the second setting. A correlation calculation step of calculating a correlation value between the image in the first region and the image in the second region at each position of the second region set in the step; (a-4) in the correlation calculation step And searching for corresponding points on the second image based on the calculated correlation value, and the acquired information includes each position of the second region and the correlation value obtained in the correlation calculation step. It is extreme value information acquired from the relationship.

  According to the first to tenth aspects of the present invention, acquired information (designated on the reference image) obtained through the first corresponding point search process after the corresponding point search by the first corresponding point search process is executed. Each position of the second area on the reference image set for searching for the corresponding point on the reference image corresponding to the point, and the image in the first area and the image in the second area including the designated point Based on the extreme value information obtained from the relationship with the correlation value), it is determined whether or not to perform a corresponding point re-search by a second corresponding point search process different from the first corresponding point search process. As a result, the corresponding point search can be performed quickly with high accuracy.

  In particular, in the second aspect of the invention, the second corresponding point search process is performed by setting the sizes of the first area and the second area to different sizes from the predetermined size in the first corresponding point search process. Therefore, the corresponding points can be re-searched with high accuracy.

  In another aspect of the invention, the different size is a size set based on the contrast information regarding the image in the first region, so that the corresponding points can be searched again with higher accuracy.

  Further, in the invention of claim 4, since the acquired information is information on the number of extreme points related to the maximum value of the correlation value, it can be easily determined whether or not to re-search for corresponding points.

  In the invention of claim 5, the extreme point is set adjacent to the first condition where the maximum value related to the correlation value is larger than the first threshold and the position of the second region where the maximum value is taken. Since the correlation value calculated at the position of the second region is a maximum value point that satisfies the second condition in which the ratio of the correlation value to the maximum value is smaller than the second threshold value, whether or not the corresponding point should be re-searched Can be determined appropriately.

  In the invention of claim 6, when the number of extreme points is 1, since the corresponding point re-search by the second corresponding point search process is not executed, unnecessary processing is omitted and Point search can be performed at high speed.

  In the invention of claim 7, when the number of extreme points is two or more, the correlation value is calculated only at each position of the second region relating to each of the two or more extreme points. Since the corresponding points are searched again by the corresponding point search process, the corresponding points can be searched again quickly.

  In the invention of claim 8, since the second corresponding point search process is a corresponding point search process using the phase only correlation method, the corresponding points can be re-searched with high accuracy.

<First Embodiment>
<Configuration of information processing system>
FIG. 1 is a block diagram showing a main configuration of an information processing system 1A according to the first embodiment of the present invention.

  The information processing system 1A includes a two-lens stereo camera 2 and an information processing apparatus 3A connected to the stereo camera 2 so as to be able to transmit data.

  The stereo camera 2 is provided with two imaging systems 21 and 22 each having an imaging device. These imaging systems 21 and 22 are configured so that the subject in front of the camera can be imaged from different viewpoints in synchronism with each other, and each image data acquired by imaging is processed via the data line CB. It is transmitted to the device 3A.

  The information processing apparatus 3A is configured, for example, as a personal computer, and includes an operation unit 31 that includes a mouse and a keyboard, a display unit 32 that includes, for example, a liquid crystal display, and an interface for receiving data from the stereo camera 2 ( I / F) unit 33. The information processing apparatus 3 </ b> A includes a storage unit 34, an input / output unit 35, and a control unit 36.

  The storage unit 34 is configured as a hard disk, for example, and stores a program PGa for performing corresponding point search processing described later.

  The input / output unit 35 is configured as a disk drive, for example, and is a part for exchanging data with the optical disk 9.

  The control unit 36 includes a CPU 36a that functions as a computer and a memory 36b, and is a part for comprehensively controlling each unit of the information processing apparatus 3A. When the control unit 36 executes the program PGa in the storage unit 34, a corresponding point search process (described later) can be performed.

  Program data recorded on the optical disk 9 as a recording medium can be stored in the memory 36 b of the control unit 36 via the input / output unit 35. Thereby, the stored program can be reflected in the operation of the information processing apparatus 1A.

  Further, the control unit 36 can perform a process of searching for corresponding points between stereo images acquired by the stereo camera 2, and the corresponding point search process will be described below.

  In this embodiment, in order to simplify the description, it is assumed that the aberration of the stereo camera is corrected well and set in parallel. Even if the actual hardware is not in such a condition, it is possible to convert it to an equivalent image by image processing.

<Corresponding point search processing>
In the information processing apparatus 3A, a corresponding point search process between stereo images using the SAD (Sum of Absolute Difference) method can be performed. The corresponding point search by the SAD method will be described with reference to FIG.

  FIG. 2 is a diagram for explaining the corresponding point search processing using the SAD method.

  Two images acquired in synchronization by the imaging systems 21 and 22 of the stereo camera 2 are set as a standard image (first image) Ga and a reference image (second image) Gb. Then, a window (first region) Wa including the pixel (designated point) Wao designated on the standard image Ga to search for the corresponding pixel (corresponding point) on the reference image Gb is used as the standard image Ga. The window (second area) Wb having the same size as the window Wa is set at a plurality of positions in the reference image Gb.

  Here, since the stereo cameras are installed in parallel, the plurality of windows Wb in the reference image Gb are set in the horizontal direction (lateral direction) over the range of the maximum parallax pmax. For example, a plurality of windows Wb that are shifted one pixel at a time from the position Qo on the reference image Gb shown in FIG. 2 (position where parallax p = 0) to the position Qmax corresponding to the maximum parallax pmax are set.

  Next, at each position of the parallax p, that is, the position of the window Wb set on the reference image Gb, a correlation value indicating the similarity between the image in the window Wa in the standard image Ga and the image in the window Wb in the reference image Gb. Is calculated. In this correlation calculation, for example, the density of each pixel in the window Wa is Img1 (i, j), and the density of each pixel in the window Wb at the parallax p is Img2 (i, j + p). Correlation value CORp using is calculated.

  When the correlation value for each parallax p is calculated by the above equation (1), the relationship between the parallax p and the correlation value becomes clear as shown in the graph Kf of FIG. In this graph Kf, the center point of the window Wb corresponding to the parallax ps having the maximum correlation value (extreme point) is the point corresponding to the designated point Wao of the reference image Ga. That is, the corresponding point on the reference image Gb corresponding to the designated point Wao of the standard image Ga is searched by specifying the peak position of the correlation value based on the correlation value calculated using the above equation (1). It becomes.

  Hereinafter, a method for appropriately determining (detecting) the extreme value point of the correlation value from the correlation value for each parallax p will be described.

  For the extreme points of the correlation value, the position of the parallax p that satisfies the following equations (2) and (3) is detected as an extreme point.

  That is, the ratio of the correlation value in the adjacent parallax (p-1) and the parallax (p + 1) to the correlation value (maximum value) in the parallax p as shown in the above equation (2) is the threshold α (for example, 0.9). ) Is smaller (that is, when there is a certain convex portion in the graph shape), and if the correlation value at the parallax p is greater than the threshold value β, it is determined that the parallax p has an extreme point. That is, the correlation value calculated based on the first condition where the maximum value related to the correlation value is greater than the threshold (first threshold) β and the position of the window Wb set adjacent to the position of the window Wb having the maximum value. The point of the maximum value that satisfies the second condition in which the ratio to the maximum value is smaller than the threshold value (second threshold value) α is detected as the extreme value point.

  Next, the extreme points detected by applying the method for determining the extreme points as described above will be described with specific examples.

  FIG. 3 is a diagram for explaining detection of extreme points. In FIGS. 3A to 3E, five types of graph shapes are shown as examples of graphs assumed in relation to the parallax and the correlation value.

  The extreme points detected by applying the above equations (2) and (3) to the graphs shown in FIGS. 3A to 3E will be described below.

  FIG. 3A shows a case where one extreme point Jk is detected, and FIG. 3B shows a case where two extreme points J1 and J2 are detected. That is, the extreme value point Jp in FIG. 3A and the extreme value points J1 and J2 in FIG. 3B each have a correlation value larger than the threshold value β, and the correlation values at the parallax adjacent to the correlation value are The ratio satisfies a condition that the ratio is smaller than a threshold value α (for example, 0.9).

  FIGS. 3C to 3E show cases where no extreme points are detected (that is, zero extreme points are detected). That is, in the graphs of FIGS. 3D to 3E, since the correlation value (the maximum value thereof) is equal to or less than the threshold value β (that is, the above expression (3) is not satisfied), no extreme point is detected. On the other hand, in the graph of FIG. 3C, although the maximum correlation value (maximum value) Ek is larger than the threshold value β, the ratio of the correlation values E1 and E2 in the parallax on both sides is equal to or larger than the threshold value α (that is, Since the above formula (2) is not satisfied), the maximum correlation value Ek is not detected as an extreme point.

  When one extreme point Jk is detected as shown in FIG. 3A by detecting the extreme points as described above, the corresponding points of the reference image Gb related to the designated point Wao of the standard image Ga can be easily obtained. However, when two extreme points J1 and J2 are detected as shown in FIG. 3B, or when extreme points are not detected as shown in FIGS. Therefore, it is difficult to specify corresponding points in the reference image.

  Therefore, extreme value information (for example, extreme point information in the graphs shown in FIGS. 3A to 3E) acquired from the relationship between the parallax (each position of the window Wb) obtained by the correlation calculation and the correlation value. ), When two or more extreme points are detected or when no extreme points are detected, the window size of the window Wa on the reference image Ga and the window Wb on the reference image Gb is changed to the size It is assumed that the corresponding point is re-searched by the above-described corresponding point search process in the changed window.

  It is said that the optimum window size is preferably determined according to the density change of the image. That is, in a uniform image portion where the change in density is small, the window on the similar reference image increases when the window size is small, and in the edge portion where the change in density is large, the peripheral portion becomes large when the window size is large. Since it becomes noise, it is difficult to search for the corresponding points satisfactorily. Therefore, in the information processing apparatus 3A of the present embodiment, the contrast in the image within the window Wa of the reference image Ga is calculated, and the corresponding point is searched using the window set to the window size based on this contrast.

  Specifically, the contrast CTR of the image in the window Wa in the reference image Ga is calculated using the following equation (4).

  When the contrast CTR calculated by the above equation (4) is larger than the predetermined threshold γ, the window size is changed to a smaller window size, and when the contrast CTR is equal to or smaller than the threshold γ, the large window size is changed. Change to As for the change of the window size, for example, the window is enlarged / reduced around the center of gravity (center point) of the window.

  Thus, by setting the windows Wa and Wb resized to different sizes based on the contrast information regarding the image in the window Wa to the base image Ga and the reference image Gb, and executing the corresponding point search process again, Since one extreme point can be obtained appropriately, the corresponding points can be re-searched satisfactorily.

  In the information processing system 1A, when a corresponding point on the reference image Gb corresponding to one designated point in the base image Ga is specified, a corresponding point search process for the next designated point is performed. Specifically, a window in which the center point of the window Wa is shifted to the right by a predetermined number of pixels (for example, one pixel) is set on the reference image Ga, and a corresponding point on the reference image Gb is searched. . If such designated points are set for all the pixels on the standard image Ga, the corresponding points on the reference image Gb for all the pixels on the standard image Ga can be specified.

<Operation of Information Processing System 1A>
FIG. 4 is a flowchart showing the basic operation of the information processing system 1A. The operation of the information processing system 1A is performed by executing the program PGa in the storage unit 34 by the CPU 36a of the control unit 36.

  In step S1, the stereo image (standard image Ga and reference image Gb) taken by the stereo camera 2 is acquired by the information processing device 3A via the data line CB.

  In step S <b> 2, it is determined whether or not the scan target by the window Wa exists in the reference image Ga. That is, it is determined whether a corresponding point of the reference image Gb has been searched for each pixel of the base image Ga. If the scan target exists, the process proceeds to step S3. If the scan target does not remain, the operation of the flowchart ends.

  In step S3, a corresponding point on the reference image Gb corresponding to the designated point on the standard image Ga is searched (detailed later).

  In step S4, the graph shape of the correlation value is analyzed from the correlation value data for each parallax obtained in step S3 (detailed later).

  In step S5, based on the analysis result of the graph shape of the correlation value in step S4, it is determined whether the number of extreme points related to the maximum value of the correlation value in the correlation value graph is one. Here, when the number of extreme points is one, it is decided not to perform the corresponding point re-search in step S6, and the process proceeds to step S7. When the number of extreme points is other than one, Advances to step S6 on the assumption that an appropriate corresponding point search process has not been performed in step S3.

  That is, in step S5, after the corresponding point search by the corresponding point search process in step S3 is executed, the next step is performed based on the information on the number of extreme points (acquired information) obtained through the corresponding point search process. Whether or not to perform the corresponding point re-search in S6 is determined.

  In step S6, the size of the window set in the base image Ga and the reference image Gb is changed, and the corresponding points are searched again (detailed later). That is, the correspondence on the reference image Gb corresponding to the designated point Wao (FIG. 2) on the standard image Ga is obtained by the corresponding point search processing (second correspondence point search processing) different from the corresponding point search processing performed in step S3. A point is searched.

  In step S7, the corresponding point on the reference image Gb corresponding to the designated point (the center point of the window Wa) on the standard image Ga is specified. In this case, even if the extreme point is not fixed to one by the corresponding point search operation in step S3, one extreme point can be detected by re-searching the corresponding point in step S6. In this case, the corresponding points can be appropriately identified.

  In step S8, the scan position is updated. That is, the window Wa of the reference image Ga is moved to a position shifted by one pixel in the right direction, for example. If the window Wa protrudes from the reference image Ga when shifted by one pixel in the horizontal direction, the window Wa is moved to the left end one pixel below.

  FIG. 5 is a flowchart corresponding to the operation in step S3 and showing the corresponding point search operation.

  In step S31, a window Wa and a window Wb having the same window size are set in each of the base image Ga and the reference image Gb acquired in step S1. Here, it is assumed that the window Wb on the reference image Gb is set at a position where the parallax p = 0 (window position Qo in FIG. 2).

  In step S32, it is determined whether the parallax p corresponding to the position of the window Wb in the reference image Gb is less than the maximum parallax pmax. If the parallax p is less than the maximum parallax pmax, the process proceeds to step S33. If the parallax p is greater than or equal to the maximum parallax pmax, the process proceeds to step S4.

  In step S33, a correlation value between the image in the window Wa in the standard image Ga and the image in the window Wb in the reference image Gb is calculated. Here, the correlation value CORp at the parallax p is calculated using the above equation (1).

  In step S34, the currently set parallax p and the correlation value calculated in step S33 are stored in, for example, the memory 36b.

  By repeating the operation of step S34 for each parallax 0 to pmax, data representing the relationship between each parallax 0 to pmax and the correlation value is accumulated in the memory 36b.

  In step S35, the parallax p is updated. Specifically, the parallax p is increased by 1, for example. As a result, the window Wb set in the reference image Gb is shifted by one pixel in the right direction.

  FIG. 6 is a flowchart corresponding to the operation of step S4 and showing the graph value analysis operation of the correlation value.

  In step S41, data indicating the relationship between each parallax 0 to pmax and the correlation value accumulated in the memory 36b by the operation in step S34 is read. Thereby, the graph shape of the correlation value as shown in the graph Kf of FIG. 2 can be grasped.

  In step S42, the maximum value of the correlation value and its parallax are extracted from the data read in step S41.

  In step S43, it is determined whether the maximum value is larger than the threshold value β. Specifically, it is determined whether or not the maximum value satisfies the above formula (3). Here, when the maximum value is larger than the threshold value β as shown in FIGS. 3A to 3C, for example, the process proceeds to step S44, and the maximum value is set as the threshold value β as shown in FIGS. 3D to 3E, for example. In the following cases, the process proceeds to step S5.

  In step S44, a local maximum value that satisfies the above equations (2) and (3) is detected as an extreme point. For example, one extreme point Jk is detected in FIG. 3A, two extreme points J1 and J2 are detected in FIG. 3B, and 0 in FIG. 3C. Extreme points are detected.

  In step S45, the number of extreme points detected in step S44 is stored in, for example, the memory 36b. Specifically, the number “1” of extreme points is stored for the graph shape of FIG. 3A, and the number “2” of extreme points is stored for the graph shape of FIG. In the graph shape of FIG. 3C, the number of extreme points “0” is stored.

  In step S46, the number of extreme points is set to “0”, for example, stored in the memory 36b.

  FIG. 7 is a flowchart corresponding to the operation in step S6 and showing the corresponding point re-search operation.

  In step S61, the window size is reset for the base image Ga and the reference image Gb (details will be described later).

  In step S62, the window having the size reset in step S61 is set as the standard image Ga and the reference image Gb, and the same operation as in step S3 described above, that is, the corresponding point search operation shown in the flowchart of FIG. 5 is performed. That is, in the corresponding point search process performed in step S3 described above, the size of the window Wa on the standard image Ga and the window Wb on the reference image Gb is set to a different size from the window size in step S3. Corresponding point search processing is performed.

  FIG. 8 is a flowchart corresponding to the operation in step S61 and showing the window size resetting operation.

  In step S71, the contrast relating to the image in the window Wa on the reference image Ga is calculated. Specifically, the contrast CTR is calculated using the above equation (4).

  In step S72, it is determined whether the contrast calculated in step S71 is larger than the threshold value γ. If the contrast is greater than the threshold γ, the process proceeds to step S73. If the contrast is less than the threshold γ, the process proceeds to step S76.

  In step S73, the window size set for the reference image Ga is reduced.

  In step S74, the contrast relating to the image in the window whose size has been changed in step S73 is calculated again.

  In step S75, it is determined whether the contrast calculated in step S74 is smaller than the threshold value γ. If the contrast is smaller than the threshold γ, the window size is appropriate and the process proceeds to step S79. On the other hand, if the contrast is greater than or equal to the threshold γ, the process returns to step S73 to further reduce the window size.

  In step S76, the window size set for the reference image Ga is enlarged.

  In step S77, the contrast relating to the image in the window whose size has been changed in step S76 is calculated again.

  In step S78, it is determined whether the contrast calculated in step S77 is larger than the threshold value γ. Here, if the contrast is larger than the threshold γ, it is determined that the window size is appropriate and the process proceeds to step S79. On the other hand, if the contrast is less than or equal to the threshold γ, the process returns to step S76 to further enlarge the window size.

  In step S79, the window whose size has been changed by the operation in step S73 or step S76 is reset to the base image Ga (and reference image Gb).

  Based on the number of extreme points obtained from the graph shape showing the relationship between the parallax and the correlation value obtained by searching for the corresponding points using the SAD method by the operation of the information processing system 1A described above, the window size is set. Since it is determined whether or not to re-search the changed corresponding point, the corresponding point search can be performed quickly with high accuracy.

  For the corresponding point search processing in the information processing system 1A, it is not essential to calculate the correlation value using the SAD method, but the SSD method for obtaining the sum of squares of the concentration or the NCC (normalized cross correlation) method is used. Thus, the correlation value may be calculated.

<Second Embodiment>
An information processing system 1B according to the second embodiment of the present invention has a configuration similar to that of the information processing system 1A according to the first embodiment shown in FIG. 1, but is stored in a storage unit of the information processing apparatus. (Configuration) is different.

  That is, the storage unit 34 of the information processing apparatus 3B according to the second embodiment stores a program PGb for executing the operation of the information processing system 1B described below.

<Operation of Information Processing System 1B>
In the information processing system 1B, an operation similar to the operation shown in the flowchart of FIG. 4 is performed, but the corresponding point re-search operation is different. Hereinafter, the corresponding point re-search operation in the information processing system 1B (operation in step S60 in FIG. 4) will be described.

  FIG. 9 is a flowchart showing the corresponding point re-search operation in the information processing system 1B.

  In step S81, the same operation as step S61 (FIG. 7) of the first embodiment, that is, the window size resetting operation shown in the flowchart of FIG. 8 described above is performed.

  In step S82, the window Wa and the window Wb are set for each of the standard image Ga and the reference image Gb acquired by the stereo camera 2 as in step S31 of FIG.

  In step S83, 0 is substituted for the flag Flag.

  In step S84, it is determined whether the number of extreme points in the correlation value graph is two or more based on the analysis result of the correlation value graph shape in step S4 of FIG. If the number of extreme points is 2 or more, the process proceeds to step S85. If the number of extreme points is less than 2, the process proceeds to step S86.

  In step S85, 1 is assigned to the flag Flag.

  In step S86, as in step S32 of FIG. 5, it is determined whether the parallax p corresponding to the position of the window Wb in the reference image Gb is less than the maximum parallax pmax. If the parallax p is less than the maximum parallax pmax, the process proceeds to step S87. If the parallax p is greater than or equal to the maximum parallax pmax, the process proceeds to step S92.

  In step S87, it is determined whether the flag Flag is 0. That is, it is determined whether or not an extreme point less than 2 is detected by the graph shape analysis operation of the correlation value in step S4 of FIG.

  If the flag Flag is 0 in step S87, the process proceeds to step S89. However, when one extreme point is detected in step S4 of FIG. 4, the corresponding point in this flowchart is not re-searched, so the extreme point is substantially detected in step S4. If not, the process proceeds to step S89.

  On the other hand, if the flag Flag is not 0 in step S87, that is, if two or more extreme points are detected in step S4 of FIG. 4, the process proceeds to step S88.

  In step S88, it is determined whether or not the extreme value point is taken with the parallax p. Specifically, it is determined whether or not the parallax at the extreme point detected in step S4 of FIG. Here, when an extreme point is obtained with the parallax p, the process proceeds to step S89, and when an extreme point is not taken, the process proceeds to step S91.

  The operation of step S88 is detected because it is considered that one or more appropriate extreme points are included in the two or more extreme points detected in step S4 of FIG. This operation is necessary for calculating the correlation value in step S89 only for the parallax related to two or more extreme points. In this way, when the number of extreme points is 2 or more, the corresponding points are re-searched by the corresponding point search process that calculates the correlation value only at each position of the window Wb related to each of the two or more extreme points. Thus, the correlation value can be calculated efficiently, and the corresponding points can be searched again quickly.

  In steps S89 to S91, operations similar to those in steps S33 to S35 in FIG. 5 are performed.

  In step S92, the maximum correlation value (that is, one extreme point) and the parallax at the correlation value are determined by referring to the data on the relationship between the parallax p and the correlation value stored in step S90.

  The operation of the information processing system 1B described above provides the same effects as those of the first embodiment. Furthermore, in the information processing system 1B according to the present embodiment, when two or more extreme points are detected in the corresponding point search (step S3 in FIG. 4), the window size is set only by the detected extreme points. Since the changed corresponding points are searched again (step S60 in FIG. 4), the corresponding points can be searched again efficiently and quickly.

<Third Embodiment>
An information processing system 1C according to the third embodiment of the present invention has a configuration similar to that of the information processing system according to the first embodiment shown in FIG. 1, but is stored in a storage unit of the information processing apparatus. (Configuration) is different.

  That is, the storage unit 34 of the information processing apparatus 3C according to the third embodiment stores a program PGc for executing the operation of the information processing system 1C described below.

<Operation of Information Processing System 1C>
In the information processing system 1C, an operation similar to the operation shown in the flowchart of FIG. 4 is performed, but the corresponding point re-search operation is different. Specifically, in the corresponding point re-search operation in the information processing system 1C, the corresponding point search process using the SAD method is not performed as in the first embodiment, but the phase-only correlation method (POC) described below is used. : Corresponding point search processing using Phase Only Correlation).

  FIG. 10 is a diagram for explaining the corresponding point search process using the phase only correlation method.

  In the corresponding point search process using the phase only correlation method, first, an image in the window on the reference image and an image in the window on the reference image are extracted. These images are expressed as the following Expression 4.

Here, f (n ₁ , n ₂ ) and g (n ₁ , n ₂ ) in the above equation 4 indicate an image in the window on the standard image and an image in the window on the reference image. N ₁ and N ₂ are set as N ₁ = 2M ₁ +1 and N ₂ = 2M ₂ +1, for example.

  Next, two-dimensional Fourier transform processing T1a and T1b using the arithmetic expression shown in the following equation 5 is performed on each image in the window of the standard image and the reference image.

Note that N ₁ and N ₂ are substituted for the subscript P of W in the proviso of the above formula 5, and ₁ and ₂ are substituted for the subscript s of k.

  For each image subjected to such Fourier transform processing T1a, T1b, normalization processing T2a, T2b for removing the amplitude component of the image is performed using the arithmetic expression shown in the following equation (6). .

  When the normalization processes T2a and T2b are completed, a synthesis process T3 using the following equation 7 is performed, and a two-dimensional inverse Fourier transform process T4 using the equation 8 is performed. Thereby, the correlation calculation between the images is performed, and the result (POC value) is output.

By the processing using the above phase-only correlation method, for example, a result as shown in FIG. 11 is obtained. In FIG. 11, the POC value at a location with high correlation in the window (N ₁ × N ₂ ) is large, and the position in the window on the reference image corresponding to the peak Jc of the POC value is This corresponds to the corresponding point on the reference image corresponding to the center point (designated point) of the window.

  According to the corresponding point search process using the phase-only correlation method as described above, the amplitude component of the image is removed, and the correlation calculation is performed only with the phase component of the image. The corresponding points on the image can be searched with high accuracy.

  In the information processing system 1C, when the corresponding point search using the SAD method (step S3 in FIG. 4) does not provide a good result (that is, when the number of extreme points is other than 1), the above-described phase Since the corresponding points are re-searched using the limited correlation method, the corresponding points on the reference image can be accurately and reliably identified.

<Modification>
In the corresponding point search processing (step S3 in FIG. 4) in each of the above embodiments, it is not essential to search for corresponding points on the reference image for all the pixels of the standard image, and an image range predetermined in the standard image A search for corresponding points may be performed for only the pixels within the pixel.

  In the second embodiment, it is not essential that the threshold value γ compared in steps S72, S75, and S78 of FIG. 8 is set to the same numerical value, and may be set to different numerical values.

It is a block diagram which shows the principal part structure of 1 A of information processing systems which concern on 1st Embodiment of this invention. It is a figure for demonstrating the corresponding point search process using SAD method. It is a figure for demonstrating the detection of an extreme point. It is a flowchart which shows the basic operation | movement of 1 A of information processing systems. It is a flowchart which shows the search operation | movement of a corresponding point. It is a flowchart which shows the analysis operation | movement of the graph shape of a correlation value. It is a flowchart which shows the re-search operation of a corresponding point. It is a flowchart which shows the reset operation | movement of a window size. It is a flowchart which shows the search operation of the corresponding point in the information processing system 1B which concerns on 2nd Embodiment of this invention. It is a figure for demonstrating the corresponding point search process using the phase only correlation method in 1C of information processing systems which concern on 3rd Embodiment of this invention. It is a figure for demonstrating the search of the corresponding point by a phase only correlation method. It is a figure which shows typically the method of calculating a three-dimensional position from the corresponding point between images based on the principle of triangulation.

Explanation of symbols

1A, 1B, 1C Information processing system 2 Stereo camera 3A, 3B, 3C Information processing device 34 Storage unit 36 Control unit 36b Memory J1, J2, Jk Extreme point Ga Reference image Gb Reference image PGa, PGb, PGc Program Wa, Wb window

Claims (10)

An information processing system that performs processing related to a first image and a second image captured and acquired from different viewpoints,
(a) first search means for searching for a corresponding point on the second image corresponding to a specified point specified on the first image;
(b) A corresponding point on the second image corresponding to the designated point on the first image is searched by a second corresponding point searching process different from the first corresponding point searching process performed by the first searching means. Second search means for performing,
(c) After performing the corresponding point search by the first corresponding point search process, based on the acquired information obtained through the first corresponding point search process, the corresponding point search by the second corresponding point search process Determining means for determining whether to perform a re-search;
With
The first search means includes
(a-1) first setting means for setting, in the first image, a first area having a predetermined size and containing the designated point;
(a-2) second setting means for setting the second region having the predetermined size at a plurality of positions in the second image;
(a-3) correlation calculation means for calculating a correlation value related to the image in the first area and the image in the second area at each position of the second area set by the second setting means;
(a-4) means for searching for corresponding points on the second image based on the correlation value calculated by the correlation calculating means;
And having
The information processing system, wherein the acquired information is extreme value information acquired from a relationship between each position of the second region and the correlation value obtained by the correlation calculation means. The information processing system according to claim 1,
The second corresponding point search process is performed by setting the first area and the second area to a different size from the predetermined size in the first corresponding point search process. An information processing system characterized by The information processing system according to claim 2,
The information processing system according to claim 1, wherein the different size is a size set based on contrast information relating to an image in the first region. In the information processing system according to any one of claims 1 to 3,
The acquired information is information on the number of extreme points related to the maximum value of the correlation value. The information processing system according to claim 4,
The extreme point is calculated based on a first condition where the maximum value related to the correlation value is greater than a first threshold, and a position of a second region set adjacent to a position of the second region where the maximum value is taken. An information processing system, wherein a point of a maximum value satisfying a second condition in which a ratio of the correlation value to the maximum value is smaller than a second threshold value. In the information processing system according to claim 4 or 5,
The determining means includes
(c-1) means for determining not to re-execute the corresponding point search by the second corresponding point search process when the number of extreme points is one;
An information processing system comprising: In the information processing system according to claim 2 or claim 3,
The acquired information is information on the number of extreme points related to the maximum value of the correlation value,
The determining means includes
(c-2) When the number of extreme points is two or more, a second corresponding point for calculating the correlation value only at each position of the second region related to each of the two or more extreme points Means for deciding to re-search for corresponding points by a search process;
An information processing system comprising: The information processing system according to claim 1,
The information processing system, wherein the second corresponding point search process is a corresponding point search process using a phase only correlation method.   A program for causing an information processing system to function as the information processing system according to any one of claims 1 to 8, when executed on a computer mounted on the information processing system. An information processing method for performing processing related to a first image and a second image captured and acquired from different viewpoints,
(a) a first search step of searching for a corresponding point on the second image corresponding to a specified point specified on the first image;
(b) A corresponding point on the second image corresponding to the designated point on the first image is searched by a second corresponding point searching process different from the first corresponding point searching process performed in the first searching step. A second search step,
(c) After performing the corresponding point search by the first corresponding point search process, based on the acquired information obtained through the first corresponding point search process, the corresponding point search by the second corresponding point search process A decision step for deciding whether to perform a re-search;
With
The first search step includes
(a-1) a first setting step of setting, in the first image, a first area having a predetermined size and including the designated point;
(a-2) a second setting step of setting the second region having the predetermined size at a plurality of positions in the second image;
(a-3) a correlation calculation step of calculating a correlation value regarding the image in the first region and the image in the second region at each position of the second region set in the second setting step;
(a-4) searching for corresponding points on the second image based on the correlation value calculated in the correlation calculation step;
And having
The information processing method, wherein the acquired information is extreme value information acquired from a relationship between each position of the second region and the correlation value obtained in the correlation calculation step.

Images