Information processing apparatus and method as well as medium

[0002] This invention relates to an information processing apparatus and method as well as a medium, and more particularly to an information processing apparatus and method as well as a medium wherein matching between images is performed using a template in measuring a distance according to the stereo method.

[0003] Similarly to the principle used by a human being to sense a shape of an object or a distance from an object to a body, a stereo method is generally known as a method of measuring a distance to an object. According to the stereo method, a shape of or a distance to an object can be measured in accordance with the principle of triangulation using images observed by a plurality of cameras having different visual points from each other.

[0004] FIG. 1 illustrates the principle of the stereo method. Referring to FIG. 1, two cameras of a base camera 1 and a reference camera 2 are disposed at visual points different from each other so that a position of an object point Q to be measured in a three-dimensional space can be determined from the two cameras. In particular, an observation point n_bat which the object point Q is observed on an image plane 1A of the base camera 1 and another observation point n_rat which the object point Q is observed on an image plane 2A of the reference camera 2 are determined. Then, the position of the object point Q in the three-dimensional space can be determined from the two observation points n_band n_r.

[0005] As a technique for detecting the observation point n_rcorresponding to the observation point n_b, a method of searching for a corresponding point on an epipolar line has been proposed. For example, the observation point n_rof the reference camera 2 which is a corresponding point to the observation point n_bwhich is on the image plane 1A observed by the base camera 1 (in the following description, an image on the image plane 1A observed by the base camera 1 is referred to simply as base image 1aas seen from FIG. 2A) is present on a straight line LP along which a plane (image plane) which is defined by the optical center (optical axis) of the reference camera 2 and the observation point n_bof the base camera 1 and the image plane 2A observed by the reference camera 2 (in the following description, an image on the image plane 2A observed by the reference camera 2 is referred to simply as reference image 2aas seen from FIG. 2B) intersect each other. The straight line LP is called epipolar line. Then, if the positional relationship between the base camera 1 and the reference camera 2 is known, then since the same object which is at different projection points from each other can be found, a desired corresponding point can be detected for each observation point of the base camera 1 by searching for the corresponding point on the epipolar line (straight line LP) on the reference image 2a.

[0006] As a technique for searching for a corresponding point, “pixel-based matching”, “feature-based matching” and “area-based” matching are known. They have the following characteristics.

[0007] The pixel-based matching searches for a corresponding point using concentration values of individual pixels. Therefore, it is high in speed of arithmetic operation, but is low in matching accuracy.

[0008] The feature-based matching extracts a characteristic such as a concentration edge from an image and searches for a corresponding point using only the characteristic between images. Therefore, information of a distance image obtained is rough.

[0009] The area-based matching involves a kind of correlation arithmetic operation. Therefore, a high arithmetic operation cost is required. However, since a corresponding point to an object can be searched out with a high degree of accuracy and distance values of all pixels can be calculated, the area-based matching is generally used frequently.

[0010] FIGS. 2A and 2B illustrate the principle of the area-based matching. Referring to FIGS. 2A and 2B, a local window W (area) is set around a noticed point (noticed pixel) 11 set arbitrarily on an image (base image 1a) observed by the base camera 1, and the window W is set as a template 12. In FIG. 2A, the template 12 is formed from 25 pixels arranged in 5 rows×5 columns.

[0011] Then, as seen in FIG. 2B, the template 12 is disposed as a template 12A on an epipolar line 13 of an image (reference image 2a) observed by the reference camera 2, and matching is performed within the set search range and a coincidence degree R(x, y) is arithmetically operated in accordance with the following expression (1): $\begin{array}{cc}R\left(x,y\right)=\sum _{\left(x,y\right)\in w}^{}{\left(I\mathrm{m1}\left(x,y\right)-I\mathrm{m2}\left(x+\Delta x,y+\Delta y\right)\right)}^2& \left(1\right)\end{array}$

[0012] where Im1(x, y) is a pixel of the base image 1a, Im2(x+Δx, y+Δy) is a pixel of the reference image 2a, and Δx and Δy represent an amount of movement of the template 12 on the epipolar line 13. Thereafter, the template 12 is moved along the epipolar line 13 and is disposed as a template 12B. Then, similarly as for the template 12A, a coincidence degree R(x, y) is arithmetically operated in accordance with the expression (1). The template 12 is further moved along the epipolar line 13 and is disposed as a template 12C. Then, similarly as for the templates 12A and 12B, a coincidence degree R(x, y) is arithmetically operated in accordance with the expression (1).

[0013] One of the three coincidence degrees R(x, y) determined in accordance with the expression (1) above which exhibits the lowest value exhibits the highest coincidence degree (similarity degree) between the base image a 1aand the reference image 2a. Accordingly, the movement amount Δx, Δy of the template 12 when the coincidence degree R(x, y) exhibits the lowest value is determined as a parallax of the noticed point 11, and a shape or a depth of the noticed point 11 in the three-dimensional space can be calculated in accordance with the principle of triangulation using the parallax of the noticed point 11.

[0014] In this manner, in the area-based matching, three-dimensional shape data corresponding to all pixels can be obtained by repeating the matching (matching) processing for each pixel. It is to be noted that, while the coincidence degree R(x, y) of the three template 12A to template 12C in FIG. 2B are arithmetically operated in accordance with the expression (1) above, actually the template 12 is successively moved by a predetermined value within a preset search range on the epipolar line 13, and the coincidence degree R(x, y) at each of such positions is arithmetically operated.

[0015] However, whichever one of the techniques described above is used, it is difficult to accurately determine all corresponding points on an image because some “ambiguity” is involved in matching between images.

[0016] For example, if it is tried to use the area-based matching to perform matching of a texture pattern 22 on a plane 21 disposed obliquely in a three-dimensional space as shown in FIG. 3, then the texture pattern 22 observed by the two cameras of the base camera 1 and the reference camera 2 is such as shown in FIGS. 4B and 4C, respectively. In particular, FIG. 4A shows the plane 21 of FIG. 3 and the texture pattern 22 disposed on the plane 21, and FIG. 4B shows an observed image (base image 1a) when the plane 21 is observed from the base camera 1 while FIG. 4C shows an observed image (reference image 2a) when the plane 21 is observed from the reference camera 2. As can be seen from FIGS. 4A to 4C, although the left and right cameras (base camera 1 and reference camera 2) observe the same object pattern (texture pattern 22), a geometrical distortion appears between the images of the texture pattern 22 and the same object pattern is recognized as different objects. This gives rise to a problem that matching is difficult.

[0017] In order to determine a corresponding point with a higher degree of accuracy, such techniques as “local support”, “matching which uses a higher-order characteristic” and “multi base line stereo” have been proposed. However, they are not sufficiently high in accuracy as yet.

[0018] It is an object of the present invention to provide an image processing apparatus and method as well as a medium by which a corresponding point can be found out with a higher degree of accuracy.

[0019] In order to attain the object described above, according to the present invention, a template is deformed to produce deformed templates, and a corresponding point is searched for using the deformed templates.

[0020] In order to attain the object described above, according to an aspect of the present invention, there is provided an image processing apparatus, comprising first inputting means for inputting at least one of images picked up by a plurality of image pickup apparatus as a base image, second inputting means for inputting the other one or ones of the images picked up by the image pickup apparatus than the base image as a reference image or images, setting means for setting an object pixel and peripheral pixels around the object pixel from among pixels of the base image as a template, production means for producing a plurality of deformed templates from the template set by the setting means, and calculation means for determining a corresponding point or points of the reference image or images using the deformed templates to calculate a corresponding relationship of the reference image or images to the base image.

[0021] According to another aspect of the present invention, there is provided an image processing method, comprising a first inputting step of inputting at least one of images picked up by a plurality of image pickup apparatus as a base image, a second inputting step of inputting the other one or ones of the images picked up by the image pickup apparatus than the base image as a reference image or images, a setting step of setting an object pixel and peripheral pixels around the object pixel from among pixels of the base image as a template, a production step of producing a plurality of deformed templates from the template set by the processing in the setting step, and a calculation step of determining a corresponding point or points of the reference image or images using the deformed templates to calculate a corresponding relationship of the reference image or images to the base image.

[0022] According to a further aspect of the present invention, there is provided a medium for causing a computer to execute a program which includes a first inputting step of inputting at least one of images picked up by a plurality of image pickup apparatus as a base image, a second inputting step of inputting the other one or ones of the images picked up by the image pickup apparatus than the base image as a reference image or images, a setting step of setting an object pixel and peripheral pixels around the object pixel from among pixels of the base image as a template, a production step of producing a plurality of deformed templates from the template set by the processing in the setting step, and a calculation step of determining a corresponding point or points of the reference image or images using the deformed templates to calculate a corresponding relationship of the reference image or images to the base image.

[0023] With the image processing apparatus, the image processing method and the medium, a plurality of deformed templates are produced, and corresponding relationships of reference images to a base image are calculated based on the deformed templates to calculate a distance to an object point. Consequently, mapping between images can be performed with a higher degree of accuracy.

[0024] The above and other objects, features and advantages of the present invention will become apparent from the following description and the appended claims, taken in conjunction with the accompanying drawings in which like parts or elements denoted by like reference symbols.

[0025] FIG. 1 is a diagrammatic view illustrating a principle of a stereo method;

[0026] FIGS. 2A and 2B are diagrammatic views illustrating a principle of an area-based matching;

[0027] FIG. 3 is a diagrammatic view illustrating matching between a base camera and a reference camera in which the stereo method is used;

[0028] FIGS. 4A to 4C are diagrammatic views illustrating images which are observed by the cameras shown in FIG. 3;

[0029] FIG. 5 is a diagrammatic view illustrating a principle of an image processing method of the present invention;

[0030] FIG. 6 is a block diagram showing a construction of an image processing apparatus to which the present invention is applied;

[0031] FIG. 7 is a diagrammatic view illustrating a principle in which the shape of an observed image is deformed depending upon the visual point of a camera;

[0032] FIG. 8 is a table illustrating results of arithmetic operation of a distance value;

[0033] FIG. 9 is a flowchart illustrating operation of the image processing apparatus of FIG. 6;

[0034] FIGS. 10A and 10B are diagrammatic views showing deformed templates;

[0035] FIG. 11 is a flowchart illustrating a maximum matching score calculation process in step S8 of FIG. 9;

[0036] FIG. 12 is a graph illustrating a similarity degree;

[0037] FIGS. 13A to 13C are diagrammatic views illustrating various media; and

[0038] FIG. 14 is a block diagram showing a construction of a personal computer shown in FIG. 13A.

[0039] Referring to FIG. 5, there is illustrated a principle wherein, when an object pattern is observed from two cameras (a base camera 1 and a reference camera 2), a plurality of deformed templates 31-1, 31-2, 31-3, . . . are produced based on a predetermined small area (template 12) of a base image a and template matching of the deformed templates 31-1, 31-2, 31-3, . . . with reference images 2a₁, to 2a_sobtained by dividing an image, which is obtained by projection transforming a reference image 2ausing a parameter determined by camera calibration, into s portions in the depthwise direction. The template 12 is set from the base image 1aobserved by the base camera 1, and the template 12 thus set is deformed.

[0040] For example, in the example of FIG. 5, a template 12 formed from totaling 81 pixels arranged in 9 rows×9 columns (hereinafter referred to simply and suitably as 9×9) is transformed into seven deformed templates 31-1 to 31-7 of 3×9, 5×9, 7×9, 9×9, 11×9, 13×9, and 15×9 (for simplified illustration, the deformed templates 31-4 to 31-7 are omitted in FIG. 5). Then, template matching is performed on an epipolar line 13 (not shown) of the reference images 2a₁to 2a_susing the deformed templates 31-1 to 31-7 (a particular example of such template matching is hereinafter described).

[0041] It is to be noted that details of the principle of producing the s reference images 2a₁to 2a_sin the depthwise direction by projection conversion from the camera calibration and the single reference image 2aare disclosed, for example, in Japanese Patent Laid-Open No. Hei 11-53548 or No. Hei 11-53549.

[0042] Subsequently, a construction of an image processing apparatus to which the present invention is applied is described with reference to FIG. 6. A base camera 1 and n reference cameras 2-1 to 2-n (in the following description, where there is no necessity of individually distinguishing them from each other, they are referred to simply as reference cameras 2. This similarly applies to other apparatus described herein.) disposed at visual points different from that of the base camera 1 simultaneously pick up an image of a texture pattern 22, and covert thus picked up observed images (base image 1aand reference images 2a-1 to 2a-n) into electric signals.

[0043] The image processing apparatus 41 is formed from, for example, a personal computer and executes predetermined processing for image signals inputted thereto from the base camera 1 and the reference cameras 2-1 to 2-n. An image memory 51 stores the image signal inputted thereto from the base camera 1, and image memories 52-1 to 52-n store the image signals inputted thereto from the reference cameras 2-1 to 2-n, respectively.

[0044] A template setting section 53 determines an arbitrary noticed point 11 from within the base image 1astored in the image memory 51, sets a local area (template 12) around the noticed point 11, and inputs the template 12 into a template deformation section 55. The template deformation section 55 produces a plurality of deformed templates 31-1 to 31-4, for example, by linear interpolation based on a shape of the template 12 inputted thereto, and inputs the deformed templates 31-1 to 31-r to matching operation sections 54-1 to 54-n, respectively.

[0045] The matching operation sections 54-1 to 54-n perform template matching on the epipolar line 13 using those of the reference images 2a-1 to 2a-n stored in the image memories 52-1 to 52-n which are on the epipolar line 13 and the deformed templates 31-1 to 31-r inputted from the template deformation section 55. Selection sections 56-1 to 56-n determine that one of the deformed templates 31-1 to 31-r which exhibits the highest similarity degree based on a result of the template matching and store the determined deformed template into a memory not shown. Further, the selection sections 56-1 to 56-n determine the coordinate position which exhibits the highest similarity degree as a parallax and inputs the coordinate values into a distance image operation section 57. The distance image operation section 57 arithmetically operates a distance value (depth) from the coordinate values inputted thereto and further produces an image based on the coordinated values inputted thereto and the deformed templates 31 stored in the memory.

[0046] Subsequently, before operation of the image processing apparatus is described, a general principle in accordance with which images observed by the left and right cameras are deformed is described. FIG. 7 illustrates a principle wherein, when the base camera 1 and a reference camera 2 are disposed in a horizontal direction and a line segment L on an oblique plane is observed from the base camera 1 and the reference camera 2, the shapes of the observed images vary depending upon the visual points. The base camera 1 and the reference camera 2 disposed on the left and the right observe the line segment L on the oblique plane placed in the three-dimensional space. In this instance, when four points a, b, c and d on the line segment L are observed from the reference camera 2, they are projected at points a′, b′, c′ and d′, respectively, of a line segment L′ parallel to a straight line interconnecting the base camera 1 and the reference camera 2. Further, a visual point i of the base camera 1 and a visual point j of the reference camera 2 which observe the line segments L and L′ are disposed on the same plane as the line segments L and L′.

[0047] As can be seen from FIG. 7, the length P₁of the line segment L on the base image 1aobserved by the base camera 1 and the length P₂of the line segment L on the reference image 2aobserved by the reference camera 2 are not necessarily equal to each other. Here, the focal length of the lenses of the base camera 1 and the reference camera 2 is represented by F, the distance between the base camera 1 and the reference camera 2 (the distance is referred to as distance of the base line) by gh(ij)=B, and the distance in a straight line from the visual points i and j of the left and right cameras to the line segment L by Z. Further, if it is assumed that the line segment L imaged by the base camera 1 is projected as a line segment b′c′=L₁on the line segment L′ and the line segment L imaged by the reference camera 2 is projected as a line segment a′d′=L₂on the line segment L′, then the difference P₁−P₂between the two images of the base image a observed by the base camera 1 and the reference image 2aobserved by the reference camera 2 can be arithmetically operated in accordance with the following expression (2):

[0048] P₂−P₁=(F/Z)·(L₂−L₁)  (2)

[0049] Here, by substituting eb′=ΔL₁, a′e=ΔL₂, c′f=ΔL₃and fd′=ΔL₄into the expression (2) it can be represented as follows:

[0050] P₂−P₁=(F/Z)·(ΔL₁+ΔL₂+ΔL₃+ΔL₄)  (3)

[0051] Further, by placing gib′=α₁, gic′=α₂, a′jh=β₁and d′jh=β₂, ΔL₁to ΔL₄are represented by the following expressions (4) to (7), respectively:

[0052] ΔL₁=(D/2)·tan α₁  (4)

[0053] $\begin{array}{cc}\Delta L_2=\frac{D}{2}·\tan {\beta }_1=\frac{D}{2}·\frac{B-\left(Z-\frac{D}{2}\right)·\tan {\alpha }_1}{\left(Z-\frac{D}{2}\right)}& \left(5\right)\end{array}$  ΔL₃=(D/2)·tan α₂  (6)

[0054] $\begin{array}{cc}\Delta L_4=\frac{D}{2}·\tan {\beta }_2=\frac{D}{2}·\frac{B-\left(Z+\frac{D}{2}\right)·\tan {\alpha }_2}{\left(Z+\frac{D}{2}\right)}& \left(7\right)\end{array}$

[0055] where D is the distance between the point a and the point d in the depthwise direction.

[0056] Further, tan α₁and tan α₂can be represented by the following expressions (8) and (9), respectively:

[0057] tan α₁=x₁₁/F  (8)

[0058] tan α₂=x₁₂/F  (9)

[0059] where x₁₁is the distance from an intersecting point p between a normal line from the point i to the base image 1aand the base image 1ato an intersecting point between a straight line interconnecting the point a and the point i and the base image 1a, and x₁₂is the distance from the intersecting point p to an intersecting point between a straight line interconnecting the point d and the point i and the base image 1a.

[0060] Accordingly, by substituting the expressions (4) to (9) into the expression (3), the following expression (10) can be obtained:

[0061] P₂−P₁=(F/Z)·{(4ZDB)/(4Z²−D²)}  (10)

[0062] The difference P₂−P₁between the two images of the base image 1aobserved by the base camera 1 and the reference image 2aobserved by the reference camera 2 can be determined in this manner.

[0063] The unit of the difference P₂−P₁determined in accordance with the expression (10) above is, for example, mm. Here, if it is assumed that the number of pixels of the base image 1ain the horizontal direction is m (pixels) and the length of a CCD chip in each of the base camera 1 and the reference camera 2 in the horizontal direction is k (mm), then the difference (P₂−P₁)_pin pixel number between the two images of the base image 1aobserved by the base camera 1 and the reference image 2aobserved by the reference camera 2 can be determined in accordance with the following expression (11):

[0064] (P₂−P₁)_p={4(FDB)/(4Z²−D²)} (m/k)  (11)

[0065] Further, the depth (distance value) D of the line segment L relates to an angle 100 of the line segment L and can be represented by the following expression (12):

[0066] D=L·sinφ  (12)

[0067] FIG. 8 illustrates a result of arithmetic operation of the difference (P₂−P₁)_pin pixel number in accordance with the expression (11) given above where the line segment L is observed and template matching is performed on the epipolar line 13 of the reference image 2a. Here, the focal length of the lens is F=8 (mm), the distance B between the cameras is B=80 (mm), the distance Z from the visual points i and j of the cameras to the line segment L is Z=500 (mm), the pixel number m of the base image a is m=720 (pixels), and the length k of the CCD chips in the horizontal direction is k=4.8 (mm). Further, the window sizes of the template 12 are 3×3, 5×5, 7×7, 9×9, 11×11, 13×13, 15×15, 17×17 and 19×19.

[0068] For example, where the angle φ of the line segment L is 15 degrees, if the size of the template 12 used is 3×3, then the difference (P₂−P₁)_pin pixel number is 0.132 (pixels), but if the size of the template 12 used is 9×9, then the difference (P₂−P₁)_pin pixel number is 0.395 (pixels). Further, if the size of the template 12 used is 15×15, then the difference (P₂−P₁)_pin pixel number is 0.659 (pixels).

[0069] On the other hand, for example, where the angle φ is 45 degrees, if the size of the template 12 used is 5×5, then the difference (P₂−P₁)_pin pixel number is 0.875 (pixels), but if the size of the template 12 used is 11×11, then the difference (P₂−P₁)_pin pixel number is 1.93 (pixels). Further, if the size of the template 12 used is 17×17, then the difference (P₂−P₁)_pin pixel number is 2.99 (pixels).

[0070] Furthermore, for example, where the angle φ is 75 degrees, if the size of the template 12 used is 7×7, then the difference (P₂−P₁)_pin pixel number is 6.164 (pixels), but if the size of the template 12 used is 13×13, then the difference (P₂−P₁)_pin pixel number is 11.607 (pixels). Further, if the size of the template 12 used is 19×19, then the difference (P₂−P₁)_pin pixel number is 17.204 (pixels).

[0071] As can be seen from the results given above, although the same object (line segment L) is observed, the length of the line segment on the image is different depending upon the size of the template 12 and the angle φ of the line segment L. Accordingly, when template matching is performed for the reference image 2aobserved by the reference camera 2, which is at a different visual point from that of the base camera 1, using a single template 12 which has an equal aspect ratio, or when template matching is performed observing a line segment L which has a large angle φ (that is, when the depth is comparatively great), a correct distance value cannot always be obtained.

[0072] Therefore, in the present invention, in order to obtain a correct distance value, a template 12 is set from the base image 1aobserved by the base camera 1, and a plurality of deformed templates 31 are produced from the template 12, and then the deformed templates 31 are used to perform template matching with an image of the epipolar line 13 of the reference image 2a.

[0073] Now, operation of the image processing apparatus when it performs a distance image calculation process of images observed by different cameras is described with reference to a flowchart of FIG. 9. In step S1, the base camera 1 inputs pixels of the observed base image 1aas Im1(x, y) to the image memory 51 so that they may be stored. In step S2, the template setting section 53 determines an arbitrary noticed point 11 from among the pixels Im1(x, y) of the base image 1astored in the image memory 51 and sets a template T(x, y) around the noticed point 11.

[0074] In step S3, the template deformation section 55 deforms the template T(x, y) set in step S2 by linear interpolation to produce deformed templates T_j(j=1, 2, . . . , J). For example, as seen from FIGS. 10A and 10B, the size and the shape of the template T(x, y) composed of totaling 81 pixels arranged in 9 rows×9 columns (in the following, suitably represented simply as 9×9) are deformed in an arbitrary direction. Particularly, FIG. 10A shows deformed templates T₁to T₇obtained by horizontal deformation of the template T(x, y) of 9×9 to seven different sizes of 9×3, 9×5, 9×7, 9×9, 9×11, 9×13 and 9×15 by linear interpolation. In FIG. 10, J=7.

[0075] The template T(x, y) may alternatively be deformed in a vertical direction (y direction). In this instance, for example, seven different deformed templates Y₁to Y₇of sizes of 3×9, 5×9, 7×9, 9×9, 11×9, 13×9 and 15×9 are produced as shown in FIG. 10B.

[0076] Referring back to FIG. 9, processing in steps S4 to S7 is performed in parallel to the processing in steps S1, S2 and S3. In step S4, the reference camera 2-1 inputs pixels Im2 (x, y) of the reference image 2a-1 observed thereby to the image memory 52-1. In step S5, the matching operation section 54-1 performs projection conversion of the reference image 2a-1 using a parameter determined from a camera calibration to divide the reference image 2a-1 into s portions in the depthwise direction to produce reference images 2a₁to 2a_s.

[0077] In step S6, a variable i is initialized to 0. In step S7, the variable i is incremented by 1. Consequently, in this instance, the variable 1 is updated to i=1.

[0078] In step S8, the matching operation section 54-1 performs template matching on the epipolar line 13 using the pixels Im2_i(x_i, y_i) of the ith (now, i=1) reference image 2a_iand the deformed templates T_jproduced in step S3 to calculate a maximum matching score.

[0079] Here, a maximum matching score calculation process wherein the deformed templates T_jof the matching operation section 54-1 are used is described with reference to FIG. 11. In step S21, a variable j for the deformed templates T_jand a maximum matching score value M_iare initialized to 0. In step S22, the variable j is incremented by 1. Consequently, in this instance, the variable j is updated to j=1.

[0080] In step S23, the matching operation section 54-1 calculates a matching score value M_jbetween the deformed templates T_j(j=1) deformed by the template deformation section 55 and the same area around the pixel Im2_i(x_i, y_i) of the ith (i=1) reference image 2a. The matching score value M_jhas a value which increases as the correlation between the template and the reference image increases, and is determined, for example, as a reciprocal value to the coincidence degree R(x, y) determined in accordance with the expression (1) given hereinabove.

[0081] In step S24, the matching operation section 54-1 discriminates whether or not the matching score value M_jcalculated in step S23 is higher than the maximum matching score value M_istored in the memory. If it is discriminated that the matching score value M_jis higher than the maximum matching score value M_i(now, M_i=), then the processing advances to step S25, in which the matching operation section 54-1 substitutes the matching score value M_jinto the maximum matching score value M_i, whereafter the processing advance to step S26. On the other hand, if it is discriminated in step S24 that the matching score value M_jis equal to or lower than the maximum matching score value M_i, then the process in step S25 is skipped, and the processing advances directly to step S26.

[0082] In step S26, the matching operation section 54-1 discriminates whether or not the matching processing with the pixel Im2_i(x_i, y_i) of the ith reference image 2a_iis completed using all deformed templates T_j. If it is discriminated that the matching processing is not completed, then the processing returns to step S22, in which the value of the variable j is incremented by one. Consequently, in this instance, the visual point j is updated to j=2. Consequently, the second deformed template is selected, and thereafter, similar processing is repeated using the second deformed template.

[0083] The processing described above is repeated until it is discriminated in step S26 that the matching processing with the pixel Im2_i(x_i, y_i) of the ith reference image 2a_iis completed using all deformed templates T_j.

[0084] Referring back to FIG. 9, the matching operation section 54-1 discriminates in step S9 whether or not the calculation processing of a maximum matching score with all of the pixels Im2_i(x_i, y_i) of the ith reference image 2a_iis completed. If it is discriminated that the calculation processing is not completed, then the processing returns to step S2. Then, the processing described above is repeated until it is discriminated in step S9 that the calculation processing of a maximum matching score with all of the pixels Im2_i(x_i, y_i) of the ith reference image 2a_iis completed.

[0085] If it is discriminated in step S9 that the calculation processing of a maximum matching score with all of the pixels Im2_i(x_i, y_i) of the ith reference image 2a_iis completed, then the matching operation section 54-1 further discriminates in step S10 whether or not matching processing with all of the reference images 2a₁to 2a_sis completed. If it is discriminated that the matching processing is not completed, then the processing returns to step S7, in which the value of the variable i is incremented by one. Now, the variable i is updated to i=2. Thereafter, the processing advances to step S8, in which similar processing is repeated until it is discriminated in step S10 that matching processing with all of the reference images 2a₁to 2a_sis completed.

[0086] Then, if it is discriminated in step S10 that matching processing with all of the reference images 2a₁to 2a_sis completed, then the selection section 56-1 determines the deformed template T_jwhich exhibits the highest similarity degree (that is, which exhibits the highest value among the maximum matching score values M_i) from the maximum matching score values M_i, and stores the deformed template T_jinto the memory not shown. Further, the selection section 56-1 inputs the pixel Im2(x, y) of the reference image 2a-1 when the similarity degree is in the highest, and inputs it to the distance image operation section 57.

[0087] FIG. 12 illustrates a result of calculation of the maximum matching score value M_iusing the deformed templates T_jby such a maximum matching score calculation process as described above. Referring to FIG. 12, the axis of abscissa represents the deformed templates T_jand the axis of ordinate represents the similarity degree. For example, in FIG. 12, since the deformed template T₆exhibits the highest similarity degree, the deformed template T₆is stored into the memory, and the pixels Im2(x, y) of the reference image 2a-1 then are inputted to the distance image operation section 57.

[0088] Referring back to FIG. 9, in step S11, the distance image operation section 57 determines the amounts of movement of the deformed template when the maximum matching score value M_iis obtained as a parallax between the noticed pixels, and produces a distance image in accordance with the principle of triangulation, thereby ending the processing.

[0089] In the foregoing description, a method of deforming a template into deformed templates T_jof a rectangular shape. However, the present invention can be applied also where a template is deformed into deformed templates of some other shape such as, for example, a trapezoidal shape. Further, while the expression (11) is used as a reference for determination of an aspect ratio of the template 12, it is otherwise possible to use the following expression (13): $\begin{array}{cc}\begin{array}{c}{P}_2-P_1=\frac{L·\sin \phi \left(x_{11}+x_{12}+x_{21}+x_{22}\right)}{Z}·\frac{m}{k}\\ =\frac{4FLB·\sin \phi }{4Z^2-L^2·{\sin }^2\phi }·\frac{m}{k}\end{array}& \left(13\right)\end{array}$

[0090] Further, in addition to determination of the difference P₁−P₂between the images of the base image 1aobserved by the base camera 1 and the reference image 2aobserved by the reference camera 2, it is possible to determine an aspect ratio by determining a ratio P₁/P₂between the images in accordance with the following expression (14): $\begin{array}{cc}\begin{array}{c}{P}_2/P_1=\frac{2F\cos \phi +\left(x_{21}+x_{22}\right)\sin \phi }{2F\cos \phi -\left(x_{11}+x_{12}\right)\sin \phi }\\ =\frac{2F+\left(x_{21}+x_{22}\right)\tan \phi }{2F-\left(x_{11}+x_{12}\right)\tan \phi }\end{array}& \left(14\right)\end{array}$

[0091] As described above, since a plurality of deformed templates 31 (including the original template 12) are produced from the template 12 and template matching is performed using the deformed templates, the ambiguity in matching between images can be reduced and the frequency in occurrence of mismatching can be suppressed considerably, and consequently, a distance value having a high degree of reliability can be obtained.

[0092] Accordingly, a distance value can be measured with a high degree of accuracy also for an object which is complicated in shape particularly in the depthwise direction of a complicated three-dimensional shape.

[0093] The series of processes described above may be executed by hardware or by software. Where the series of processes is executed by software, a program which constructs the software is installed into a computer incorporated in the image processing apparatus 41 as hardware for exclusive use or, for example, a personal computer for universal use which can execute various functions by installing various programs.

[0094] Now, a medium on which the program for execution of the series of processes described above is recorded and which is used to install the program into a computer so that the program may be executed by the computer is described with reference to FIGS. 13A to 13C taking a case wherein the computer is a personal computer for universal use as an example.

[0095] The program can be provided to a user in such a form that it is installed in advance in a hard disk 62 or a semiconductor memory 63 as a recording medium built in a personal computer 61 as shown in FIG. 13A.

[0096] As an alternative, the program may be provided as package software by temporarily or permanently storing (recording) it on such a recording medium as a floppy disk 71, a CD-ROM (Compact Disc Read Only Memory) 72, an MO (Magneto-optical) disk 73, a DVD (Digital Versatile Disc) 74, a magnetic disk 75 or a semiconductor memory 76.

[0097] As another alternative, the program may be transferred by radio to the personal computer 61 from a down load site 81 through an artificial satellite 82 for digital satellite broadcasting, or may be transferred by radio or by wire to the personal computer 61 over a network 91 such as a local area network or the Internet and then installed into the built-in hard disk 62 by the computer 61.

[0098] It is to be noted that the term “medium” in the present specification is used to signify in a broad sense including all such media as mentioned hereinabove.

[0099] Referring to FIG. 14, for example, the personal computer 61 has a CPU 102 built therein. An input/output interface 105 is connected to the CPU 102 over a bus 101. If a user operates an inputting section 107 which is formed from a keyboard, a mouse or the like to input an instruction to the CPU 102 through the input/output interface 105, then the CPU 102 executes a program stored in a ROM 103, which corresponds to the semiconductor memory 63 of FIG. 13A, in response to the instruction. Or, the CPU 102 loads into a RAM 104 and executes a program stored in advance on the hard disk 62, a program transferred from the satellite 82 or the network 91, received by a communication section 108 and then installed on the hard disk 62 or a program read out from the floppy disk 71, CD-ROM 72, MO disk 73, DVD 74 or magnetic disk 75 loaded on a drive 109 and installed on the hard disk 62. Further, the CPU 102 outputs, when necessary, a result of the processing, for example, to a display unit 106, which is formed from an LCD (Liquid Crystal Display) unit or the like, through the input/output interface 105.

[0100] It is to be noted that, in the present application, the steps which describe the program provided in the form of a medium may be but need not necessarily be processed in a time series in the order as described, and include processes which are executed parallelly or individually.

[0101] While a preferred embodiment of the present invention has been described using specific terms, such description is for illustrative purposes only, and it is to be understood that changes and variations may be made without departing from the spirit or scope of the following claims.