Method and apparatus for image matching

• US 20040240725A1
• Filed: 04/06/2004
• Published: 12/02/2004
• Est. Priority Date: 10/26/2001
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Xu, Li-Qun, Lei, Bangjun
• Granted Patent: US 8,009,897 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10021 Stereoscopic video; Stereoscopic image sequence
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: H04N 13/189 Recording image signals; Reproducing recorded image signals
• CPC Class Codes: H04N 2013/0081 Depth or disparity estimation from stereoscopic image signals
• CPC Class Codes: H04N 2013/0085 Motion estimation from stereoscopic image signals
• CPC Class Codes: H04N 2013/0088 Synthesising a monoscopic image signal from stereoscopic images, e.g. synthesising a panoramic or high resolution monoscopic image
• CPC Class Codes: H04N 2013/0092 Image segmentation from stereoscopic image signals

Abstract

The invention provides a method and apparatus for performing correspondence estimation between pixels of a stereo image pair to obtain matching information for corresponding pixels in each image. To perform a match for a particular pixel in a first image firstly an adaptive curve is constructed about the pixel, being a sequence of connected pixels with similar intensity values to the pixel being matched. The adaptive curve thus constructed is then used as a matching element within the second image to find a matching pixel representative of the same 3D scene point in the second image to the particular pixel. By performing matching in this manner for every pixel in an image, accurate disparity maps can be obtained which are then used in a known image synthesis algorithm to produce novel images of a scene of improved quality.

Claims

1. A method of matching picture elements between at least a first image and a second image each comprising a plurality of picture elements, the method comprising the steps of:

selecting a first picture element within the first image to be matched within the second image;

constructing a first sequence of connected picture elements within the first image and including the first picture element, wherein each picture element within the sequence possesses one or more characteristics most similar to the first picture element than other surrounding picture elements; and

searching the picture elements of the second image using the constructed sequence as a matching element to find a substantially corresponding picture element within the second image to the first picture element.

2. A method according to claim 1, wherein the constructing step further comprises the steps of:

searching the picture elements of the first image in a first direction from the first picture element to determine a first line of up to h connected picture elements to form part of the first sequence; and

searching the picture elements of the first image in a second direction opposite to the first direction to determine a second line of up to h connected picture elements to form part of the first sequence.

3. A method according to claim 1 wherein each picture element within the sequence possesses the least differences in intensity to the first picture element than other surrounding picture elements.

4. A method according to claim 1 wherein for any particular picture element to be searched in the second image, the searching step comprises:

determining within the second image a corresponding sequence of picture elements including the picture element to be searched to the first sequence of picture elements; and

comparing the characteristics of the picture elements in the first sequence with the characteristics of the picture elements in the corresponding sequence to derive a cost value indicative of the degree of matching,

wherein a picture element in the second image is matched with the first picture element if its cost value indicates the highest degree of matching from those picture elements in the second image which have been searched.

5. A method according to claim 4, wherein the characteristics of the picture elements compared include one or more of picture element intensity, a mean value of intensity, and/or variance of intensity.

6. A method according to claim 5, wherein for a particular picture element, the mean value of intensity is the average of the intensity of a segment of w adjacent picture elements including the particular picture element.

7. A method according to claim 5 wherein the variance of intensity is the variance of the intensity a segment of w adjacent picture elements including the particular picture element.

8. A method according to claim 7, wherein the calculated variance value is rendered negative if the segment w of adjacent picture elements has a greater sum of picture element intensities at one of either the left or right sides of the segment.

9. A method according to claim 4, wherein the cost value for a particular picture element being searched in the second image is calculated as follows:

10. A method according to claim 1, wherein the searching step further includes the step of predicting a picture element in the second image at which to start searching based upon previous matches obtained for other picture elements.

11. A. method according to claim 10, wherein the predicting step further includes the step of selecting a starting picture element in the second image based upon a previous match obtained for another connected picture element to the first picture element.

12. A method according to claim 10, wherein the predicting step further includes the step of selecting a starting picture element in the second image based upon a previous match obtained for another picture element which is a member of the first sequence.

13. A method according to claim 10, wherein the predicting step further includes the step of selecting a starting picture element in the second image based upon a previous match obtained for another picture element for which the first picture element is a member of the sequence constructed according to the constructing step for the other picture element.

14. A method according to claim 10, wherein the predicting step further includes the step of selecting a picture element in the second image based upon a previous match obtained for a corresponding picture element in a temporally displaced version of the first image to the first picture element.

15. A method according to claim 1, and further comprising the steps of:

generating a plurality of versions of each of the first and second images, each version of each image having a different resolution to the other versions of the same image, but the same resolution as the corresponding version of the other image, and

performing picture element matching in accordance with any of the preceding claims between each corresponding version of the first and second images.

wherein picture element matching is performed between versions with a lower resolution prior to versions with a higher resolution.

16. A method according to claim 15, wherein, for versions of the first and second images other than the lowest resolution the searching step further comprises the step of determining a search range of picture elements in the second image to be searched based upon previous matches obtained for corresponding picture elements in one or more of the lower resolution versions of the images.

17. A method according to claim 1, and further comprising the step of checking that the picture element in the second image found by the searching step meets one or more predetermined parameters with respect to the matching picture elements to other picture elements in the first image adjacent to or surrounding the first picture element;

and discarding the match if the parameters are not met.

18. A method according to claim 17, wherein one of the parameters is the continuity of the matched picture element with respect to previously matched adjacent or surrounding picture elements.

19. A method according to claim 17, wherein one of the parameters is the ordering of the matched picture element with respect to previously matched adjacent or surrounding picture elements.

20. A method according to claim 1, wherein when the searching step is unable to find a match for the first picture element, the method further comprises the steps of:

locating a matching previously made for another picture element in the first image for which the first picture element is a member of the sequence constructed for the other picture element according to the constructing step; and

matching the first picture element with a picture element in the second image which exhibits the same spatial displacement within the second image with respect to the position of the first picture element in the first image as the picture element within the second image matched to the other picture element in the first image exhibits with respect to the position of the other picture element within the first image.

21. A method according to claim 1, wherein when the searching step is unable to find a match for the first picture element, the method further comprises the steps of:

locating the matching previously made for other picture elements in the first image which are members of the sequence constructed for the first picture element by the constructing steps,

for each located matching pair, determining a displacement vector (d) representative of the spatial displacement of the position of the matched picture element within the second image with respect to the position of the corresponding other picture element in the first image;

interpolating between the determined displacement vectors to find an average resultant displacement vector; and

applying the resultant vector to the corresponding position within the second image of the first picture element within the first image to locate the matching picture element within the second image.

22. A method of generating novel views of a scene, comprising the steps of:

receiving a first view of the scene as a first image comprising a plurality of picture elements;

receiving a second view of the scene as a second image different to the first image and comprising a plurality of picture elements;

performing picture element matching between the first and second images in accordance with any of the preceding claims; and

using the matching information thus obtained to synthesise a third image showing a third view of the scene.

37. An apparatus according to claim 23, and further comprising:

image version generating means for generating a plurality of versions of each of the first and second images, each version of each image having a different resolution to the other versions of the same image, but the same resolution as the corresponding version of the other image, and

wherein the apparatus of the invention is further arranged to perform picture element matching in accordance with any of the preceding claims between each corresponding version of the first and second images.

wherein picture element matching is performed between versions with a lower resolution prior to versions with a higher resolution.

38. An apparatus according to claim 37, wherein the image searching means further comprises search range determination means for determining a search range of picture elements in the second image to be searched based upon previous matches obtained for corresponding picture elements in one or more of the lower resolution versions of the images.

45. A computer-readable storage medium storing a program for a computer, which, when run on a computer controls the computer to perform a method according to claim 1.

23. An apparatus for matching picture elements between at least a first image and a second image each comprising a plurality of picture elements, comprising:

element selecting means for selecting a first picture element within the first image to be matched within the second image;

sequence construction means for constructing a first sequence of connected picture elements within the first image and including the first picture element, wherein each picture element within the sequence possesses one or more characteristics most similar to the first picture element than other surrounding picture elements; and

image searching means for searching the picture elements of the second image using the constructed sequence as a matching element to find a substantially corresponding picture element within the second image to the first picture element.

24. An apparatus according to claim 23, wherein the sequence construction means further comprises:

first direction searching means for searching the picture elements of the first image in a first direction from the first picture element to determine a first line of up to h connected picture elements to form part of the first sequence; and

second direction searching means for searching the picture element of the first image in a second direction opposite to the first direction to determine a second line of up to h connected picture elements to form part of the first sequence.

25. An apparatus according to claim 23, wherein each picture element within the sequence possesses the least differences in intensity to the first picture element than other surrounding picture elements.

26. An apparatus according to claim 23, wherein the image searching means comprises:

sequence determination means for determining for any particular picture element to be searched in the second image, a corresponding sequence of picture elements including the picture element to be searched the first sequence of picture elements; and

element comparison means for comparing the characteristics of the picture elements in the first sequence with the characteristics of the picture elements in the corresponding sequence to derive a cost value indicative of the degree of matching,

wherein the image searching means is operable to match a picture element in the second image with the first picture element if its cost value indicates the highest degree of matching from the picture elements in the second image which have been searched.

27. An apparatus according to claim 26, wherein the characteristics of the picture elements compared include one or more of picture element intensity, a mean value of intensity, and/or variance of intensity.

28. An apparatus according to claim 27, wherein for a particular picture element, the mean value of intensity is the average of the intensity of a segment of w adjacent picture elements including the particular picture element.

29. An apparatus according to claim 27 wherein the variance of intensity is the variance of the intensity a segment of w adjacent picture elements including the particular picture elements.

30. An apparatus according to claim 29, wherein the calculated variance-value is rendered negative if the segment w of adjacent picture elements has a greater sum of picture element intensities at one of either the left or right sides of the segment.

31. An apparatus according to claim 26, wherein the cost value for a particular picture element being searched in the second image is calculated as follows:

32. An apparatus according to claim 23, wherein the image searching means further include prediction means for predicting a picture element in the second image at which to start searching based upon previous matches obtained for other picture elements.

33. An apparatus according to claim 32, wherein the prediction means further includes first selection means for selecting a starting picture element in the second image based upon a previous match obtained for another connected picture element to the first picture element.

34. An apparatus according to claim 32, wherein the prediction means further includes second selection means for selecting a starting picture element in the second image based upon a previous match obtained for another picture element which is a member of the first sequence.

35. An apparatus according to claim 32, wherein the prediction means further includes third selection means for selecting a starting picture element in the second image based upon a previous match obtained for another picture element for which, the first picture element is a member of the sequence constructed by the sequence construction means for the other picture element.

36. An apparatus according to claim 32, wherein the prediction means further includes temporal selection means for selecting a picture element in the second image based upon a previous match obtained for a corresponding picture element in a temporally displaced version of the first image to the first picture element.

39. An apparatus according to claim 23, and further comprising checking means for checking that the picture element in the second image found by the image searching means meets one or more predefined parameters with respect to the matching picture elements to other picture elements in the first image adjacent to or surrounding the first picture element;

and discarding the match if the parameters are not met.

40. An apparatus according to claim 39, wherein one of the parameters is the continuity of the matched picture element with respect to previously matched adjacent or surrounding picture elements.

41. An apparatus according to claim 39, wherein one of the parameters is the ordering of the matched picture element with respect to previously matched adjacent or surrounding picture elements.

42. An apparatus according to claim 23, further comprising the image searching means:

matching location means for locating a matching previously made for another picture element in the first image for which the first picture element is a member of the sequence constructed for the other picture element by the sequence construction means; and

auxiliary matching means for matching the first picture element with a picture element in the second image which exhibits the same spatial displacement within the second image with respect to the position of the first picture element in

the first image as the picture element within the second image matched to the other picture element in the first image exhibits with respect to the position of the other picture element within the first image;

wherein the matching location means and auxiliary matching means are operable when the image searching means is unable to find a match for the first picture element.

43. An apparatus according to claim 23, further comprising:

matching location means for locating the matching previously made for other picture elements in the first image which are members of the sequence constructed for the first picture element by the sequence construction means;

vector determination means for, for each located matching pair, determining a displacement vector (d) representative of the spatial displacement of the position of the matched picture element within the second image with respect to the position of the corresponding other picture element in the first image;

interpolation means for interpolating between the determined displacement vectors to find an average resultant displacement vector; and

vector matching means for applying the resultant vector to the corresponding position within the second image of the first picture element within the first image to locate the matching picture element within the second image.

44. An apparatus for generating novel views of a scene, comprising:

view receiving means for receiving a first view of the scene as a first image comprising a plurality of picture elements, and for receiving a second view of the scene as a second image different to the first image and comprising a plurality of picture elements;

an apparatus according to claim 23, and arranged to perform picture element matching between the first and second images; and

image synthesis means arranged to use the matching information thus obtained to synthesise a third image showing a third view of the scene.