Segment based image matching method and system

• US 20050286756A1
• Filed: 06/25/2004
• Published: 12/29/2005
• Est. Priority Date: 06/25/2004
• Status: Active Grant

• Current Assignee: STMicroelectronics International N.V. (STMicroelectronics NV)
• Original Assignee: STMicroelectronics Incorporated (STMicroelectronics NV)
• Inventors: Hong, Li, Chen, George-Qian
• Granted Patent: US 7,330,593 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06V 10/10 Image acquisition document image scanning and transmission H04N1/00; control of digital cameras H04N23/60
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects

Abstract

An image matching method and system for use with multiple images of a scene captured from different angles. Image matching is performed by identifying a plurality of segments within at least two images, determining an initial disparity values for pixels in the images and then determining initial disparity planes for the segments by fitting a plane to initial disparity values for the segments. A refined disparity plane set is created by iteratively refitting the disparity planes by using various fitting cost functions and weighted linear systems. A labeling of each segment to a disparity plane is made by minimizing a global energy function that includes energy terms for segment to disparity plane matching as well as penalizing disparity plane discontinuities between adjacent image segments.

Claims

1. A method for image matching, the method comprising the steps of:

determining a first disparity surface by fitting initial disparity values for at least three pixels that are contained within a first segment of a plurality of segments within an image;

determining a second disparity surface by fitting initial disparity values for at least three pixels that are contained within a second segment within the plurality of segments of the image;

creating a disparity surface set comprising at least the first disparity surface and the second disparity surface; and

labeling each segment of the plurality within segments to a respective best fit disparity surface within the disparity surface set by minimizing a labeling efficiency function that globally determines labeling efficiency for each segment with respect to each disparity surface within the disparity surface set.

2. The method according to claim 1, wherein the labeling step is performed using segments within the plurality of segments that have a number of pixels greater than a respective predetermined threshold.

3. The method according to claim 1, wherein the step of determining the first disparity surface comprises the sub-steps of:

determining at least one outlying pixel within the at least three pixels that are contained within the first segment by determining a first disparity for a first pixel in the image relative to a corresponding pixel in a second image, and a second disparity calculated for the corresponding pixel relative to the first pixel, the at least one outlying pixel determined by an inequality between the first disparity and the second disparity; and

excluding the at least one outlying pixel from the at least three pixels.

4. The method according to claim 1, wherein the labeling step comprises the sub-step of labeling a selected segment within the plurality of segments to a respective best fit disparity surface by using a selected minimum cost function chosen from a plurality of minimum cost functions dependent upon a number of pixels in selected segment.

5. The method according to claim 1, further comprising, after the labeling step, the steps of:

determining if the first disparity surface and the second disparity surface have the same label;

determining if the first segment and the second segment are adjacent; and

combining, in response to determining that the first disparity surface and the second disparity surface have the same label and that the first disparity surface is adjacent to the second disparity surface, the first segment and the second segment.

6. The method according to claim 1, further comprising the step of refining the disparity surface set by iteratively refitting the first disparity surface to pixels within the first segment and iteratively refitting the second disparity surface to pixels within the second segment.

7. The method according to claim 6, wherein iteratively refitting the first disparity surface comprises determining an improved disparity surface estimate by fitting the improved disparity surface estimate to the at least three pixels with a weighted linear system function that includes a weighting in the weighted linear system function for each pixel within the at least three pixels, the weighting being dependent upon an a difference between an initial disparity value for the each pixel of the at least three pixels and a prior disparity surface estimate for the first segment.

8. The method according to claim 6, wherein at least one of the determining a first disparity surface, determining a second disparity surface and refining the disparity surface set is performed with segments within the plurality of segments that have a number of pixels greater than a respective predetermined threshold.

9. The method according to claim 6, wherein refining the disparity surface set comprises creating a refined disparity surface set by evaluating a matching cost function between a respective segment and a selected disparity surface within the refined disparity surface set, and the matching cost function comprises a term dependent upon a proportion of supporting pixels in a respective segment for the selected disparity surface.

10. The method according to claim 6, further comprising the steps of:

determining if the first disparity surface and the second disparity surface are equivalent;

determining if the first segment and the second segment are adjacent; and

fitting, in response to determining that the first disparity surface and the second disparity surface are equivalent and that the first disparity surface is adjacent to the second disparity surface, a respective best fit plane to a joint segment comprising the first segment and the second segment.

11. The method according to claim 1, wherein the labeling function operates to reduce disparity surface discontinuities among adjacent segments.

12. The method according to claim 11, wherein the labeling function comprises:

E(ƒ

)=E_data(ƒ

)+E_smooth(ƒ

)

where E_data(ƒ

) comprises a data-dependent energy term containing the cost of assigning disparity plane labels to the segments and E_smooth(ƒ

) comprises a function to enforce smoothness and that operates to reduce disparity plane discontinuities by penalizing such discontinuities.

13. The method according to claim 12,

$\mathrm{wherein}$

 

⁢

E data ⁡

( f ) ⁢

 

⁢

comprises ⁢

;

⁢

 

⁢

∑

S ∈

R ⁢

C ⁡

( S , f ⁡

( S ) ) , and $E_{\mathrm{smooth}}<br><br>\left(f\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{comprises}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{S,S^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>u_{S,S^{\mathrm{\prime <br><br>}}}<br><br>\mathrm{\delta <br><br>}<br><br>\left(f<br><br>\left(S\right)\ne <br><br>f<br><br>\left(S^{\mathrm{\prime <br><br>}}\right)\right),$

where S and S′

are neighboring segments, R is the plurality of segments, u_S,S′

is proportional to the common border length between segment S and S′

, and δ

(ƒ

(S)≠

ƒ

(S′

)) has value 1 if ƒ

(S)≠

ƒ

(S′

), otherwise 0, and C(S,ƒ

(S)) is a matching cost function.

14. The method according to claim 13, wherein C(S,ƒ

(S)) is one of;

$\underset{\left(x,y\right)\in <br><br>S-O}{\sum <br><br>}<br><br>c<br><br>\left(x,y,d\right)<br><br>{\mathrm{e<br><br>}}^{1-\frac{s}{n}}$

where O is a set of occluded pixels, s is a number of non-occluded pixels in S, x and y are pixel coordinates and d is a respective initial disparity for pixel (x, y), and n is a number of pixels in S, and

$\underset{\left(x,y\right)\in <br><br>S}{\sum <br><br>}<br><br>c<br><br>\left(x,y,d\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{where}$ $c<br><br>\left(x,y,d\right)=\frac{1}{9}<br><br>\underset{i=-1}{\overset{1}{\sum <br><br>}}<br><br>\underset{j=-1}{\overset{1}{\sum <br><br>}}<br><br><br><br>I<br><br>\left(x+i,y+j\right)-J<br><br>\left(x+i+d,y+j\right)<br><br>.$

15. An image matching system, comprising:

a disparity calculator that creates a disparity surface set that comprises at least the first disparity surface and the second disparity surface by determining the first disparity surface by fitting initial disparity values for at least three pixels that are contained within a first segment of a plurality of segments within an image and by determining the second disparity surface of the disparity surface set by fitting initial disparity values for at least three pixels that are contained within a second segment within the plurality of segments of the image; and

a best fit processor that labels each of the plurality of segments within the image to a respective best fit disparity surface within the disparity surface set by minimizing a labeling efficiency function that globally determines labeling efficiency for each segment with respect to each disparity surface within the disparity surface set.

16. The image matching system according to claim 15, wherein the best fit processor labels only segments within the plurality of segments that have a number of pixels greater than a respective predetermined threshold.

17. The image matching system according to claim 15, wherein the best fit processor labels each segment of the plurality of segments by at least labeling a selected segment within the plurality of segments to a respective best fit disparity surface by using a selected minimum cost function chosen from a plurality of minimum cost functions dependent upon a number of pixels in selected segment.

18. The image matching system according to claim 15, further comprising a plane refinement processor that refines the disparity surface set by iteratively refitting the first disparity surface to pixels within the first segment and iteratively refitting the second disparity surface to pixels within the second segment.

19. The image matching system according to claim 18, wherein the plane refinement processor iteratively refits the first disparity surface by at least determining an improved disparity surface estimate by at least fitting the improved disparity surface estimate to the at least three pixels with a weighted linear system function that includes a weighting in the weighted linear system function for each pixel within the at least three pixels, the weighting being dependent upon a difference between an initial disparity value for the each pixel of the at least three pixels and a prior disparity surface estimate for the first segment.

20. The image matching system according to claim 18, wherein segments within the plurality of segments that have a number of pixels greater than a respective predetermined threshold are used by at least one of the disparity calculator to determine a first disparity surface and a second disparity surface, and the plane refinement processor to refine the disparity surface set.

21. The image matching system according to claim 18, wherein the plane refinement processor creates a refined disparity surface set by evaluating a matching cost function between a respective segment and a selected disparity surface within the refined disparity surface set, and the matching cost function comprises a term dependent upon a proportion of supporting pixels in a respective segment for the selected disparity surface.

22. The image matching system according to claim 18, wherein the plane refinement processor further:

determines if the first disparity surface and the second disparity surface are equivalent;

determines if the first segment and the second segment are adjacent; and

fits, in response to determining that the first disparity surface and the second disparity surface are equivalent and that the first disparity surface is adjacent to the second disparity surface, the a respective best fit plane to a joint plane comprising the first disparity surface and the second disparity surface.

23. The image matching system according to claim 15, wherein the labeling efficiency function operates to reduce disparity surface discontinuities among adjacent segments.

24. The image matching system according to claim 23, wherein the labeling efficiency function comprises:

E(ƒ

)=E_data(ƒ

)+E_smooth(ƒ

)

where E_data(ƒ

) comprises a data-dependent energy term containing the cost of assigning disparity plane labels to the segments and E_smooth(ƒ

) comprises a function to enforce smoothness and that operates to reduce disparity plane discontinuities by penalizing such discontinuities.

25. The method according to claim 24,

$\mathrm{wherein}$

 

⁢

E data ⁡

( f ) ⁢

 

⁢

comprises ⁢

;

⁢

 

⁢

∑

S ∈

R ⁢

C ⁡

( S , f ⁡

( S ) ) , and $E_{\mathrm{smooth}}<br><br>\left(f\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{comprises}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{S,S^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>u_{S,S^{\mathrm{\prime <br><br>}}}<br><br>\mathrm{\delta <br><br>}<br><br>\left(f<br><br>\left(S\right)\ne <br><br>f<br><br>\left(S^{\mathrm{\prime <br><br>}}\right)\right),$

where S and S′

are neighboring segments, R is the plurality of segments, u_S,S′

is proportional to the common border length between segment S and S′

, and δ

(ƒ

(S)≠

ƒ

(S′

)) has value 1 if ƒ

(S)≠

ƒ

(S′

), otherwise 0, and C(S,ƒ

(S)) is a matching cost function.

26. The image matching system according to claim 25, wherein C(S,ƒ

(S)) is one of;

$\underset{\left(x,y\right)\in <br><br>S-O}{\sum <br><br>}<br><br>c<br><br>\left(x,y,d\right)<br><br>{\mathrm{e<br><br>}}^{1-\frac{s}{n}}$

where O is a set of occluded pixels, s is a number of non-occluded pixels in S, x and y are pixel coordinates and d is a respective initial disparity for pixel (x, y), and n is a number of pixels in S, and

$\underset{\left(x,y\right)\in <br><br>S}{\sum <br><br>}<br><br>c<br><br>\left(x,y,d\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}$ $c<br><br>\left(x,y,d\right)=\frac{1}{9}<br><br>\underset{i=-1}{\overset{1}{\sum <br><br>}}<br><br>\underset{j=-1}{\overset{1}{\sum <br><br>}}<br><br><br><br>I<br><br>\left(x+i,y+j\right)-J<br><br>\left(x+i+d,y+j\right)<br><br>.$

27. A computer program product comprising machine readable instructions for image matching, the machine readable instructions comprising instructions for:

determining a first disparity surface by fitting initial disparity values for at least three pixels that are contained within a first segment of a plurality of segments within an image;

determining a second disparity surface by fitting initial disparity values for at least three pixels that are contained within a second segment within the plurality of segments of the image;

creating a disparity surface set comprising at least the first disparity surface and the second disparity surface; and

labeling each segment of the plurality within segments to a respective best fit disparity surface within the disparity surface set by minimizing a labeling efficiency function that globally determines labeling efficiency for each segment with respect to each disparity surface within the disparity surface set.

28. The computer program product according to claim 27, wherein the instructions for labeling comprise instructions for labeling each segment of the plurality of segments to a respective best fit disparity surface is performed with segments within the plurality of segments that have a number of pixels greater than a respective predetermined threshold.

29. The computer program product according to claim 27, further comprising instructions for refining the disparity surface set by iteratively refitting the first disparity surface to pixels within the first segment and iteratively refitting the second disparity surface to pixels within the second segment.

30. The computer program product according to claim 29, wherein the instructions for iteratively refitting the first disparity surface comprises instructions for determining an improved disparity surface estimate by fitting the improved disparity surface estimate to the at least three pixels with a weighted linear system function that includes a weighting in the weighted linear system function for each pixel within the at least three pixels, the weighting being dependent upon an a difference between an initial disparity value for the each pixel of the at least three pixels and a prior disparity surface estimate for the first segment.