Image processing method and apparatus for block-based corresponding point extraction

• US 5,734,743 A
• Filed: 07/11/1995
• Issued: 03/31/1998
• Est. Priority Date: 07/12/1994
• Status: Expired due to Term

• Current Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Original Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Inventors: Matsugu, Masakazu, Iijima, Katsumi
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Werner, Brian P.
• Application Number:
  US08/503,405
• Time in Patent Office: 994 Days
• Field of Search: 382/154, 382/106, 382/107, 382/278, 382/294, 382/291, 382/173, 348/139, 348/47, 348/50, 356/3.14, 356/12, 395/119, 395/125
• US Class Current: 382/154
• CPC Class Codes: G06T 1/00 General purpose image data processing

Abstract

An image processing method and apparatus for block-based corresponding-point extraction with high-precision, even if an image includes a discontinuous portion. The method comprises an extraction step of extracting edges or outline of a plurality of images, a dividing step of dividing the images into a plurality of blocks in such a manner that every block contains no edge and the sides of every block do not intersect with an edge, and a corresponding-point determination step of determining corresponding points between the images, based on similarity between one block of one image and a corresponding block of another image. Thus, even if one of the images includes a discontinuous portion, the corresponding-point extraction can be smoothly performed.

Claims

1. An image processing method for processing images for stereoscopic vision, obtained by image-sensing an object from a plurality of viewpoints, comprising:

a division step of dividing the respective images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images;

a size changing step of changing a size of a block of interest by combining the block of interest with its adjacent block or blocks out of the plurality of blocks generated in said division step into one block when the block of interest has predetermined relationship with respect to the adjacent block or blocks; and

a corresponding-point determination step of determining corresponding points between the images, each having blocks generated in said division step and said size changing step, based on similarity between one block of one image and that of another image.

2. The image processing method according to claim 1, wherein the similarity is decided based upon a distance between feature vectors of a block of one image and a block of a corresponding image.

3. The image processing method according to claim 2, wherein the feature vectors include luminance of each pixel as a feature vector'"'"'s component.

4. The image processing method according to claim 2, wherein the feature vectors include densities of respective three primary color components in each pixel.

5. The image processing method according to claim 1, wherein each of the corresponding points is a predetermined point in each respective block.

6. The image processing method according to claim 1, further comprising a depth calculation step of calculating depths of respective points of the object, based on positions of the corresponding points between the images, determined in said determination step, and image-sensing positions where the object is image-sensed.

7. The image processing method according to claim 6, further comprising a block expansion step of, among representative points of adjacent blocks, if the difference between the depths of the representative points is smaller than a predetermined threshold value, the adjacent blocks are combined into a larger-sized block,

wherein in said corresponding-point determination step, the corresponding points between the images are determined, based on the block generated in said block expansion step.

8. An image processing method of processing motion images obtained by image-sensing an object at different time points, comprising:

a division step of dividing frame images of the motion images, each into a plurality of blocks, so as not to intersect each block'"'"'s side with any edges in the images;

a size changing step of changing a size of a block of interest by combining the block of interest with its adjacent block or blocks out of the plurality of blocks generated in said division step into one block when the block of interest has predetermined relationship with respect to the adjacent block or blocks; and

a corresponding-point determination step of determining corresponding points between the frame images, each having blocks generated in said division step and said size changing step, based on similarity between one block of one frame image and that of a corresponding frame image.

9. The image processing method according to claim 8, wherein the similarity is decided based upon a distance between feature vectors of a block of one image and a block of a corresponding image.

10. The image processing method according to claim 9, wherein the feature vectors include luminance of each pixel as a feature vector'"'"'s component.

11. The image processing method according to claim 9, wherein the feature vectors include densities of respective three primary color components in each pixel.

12. The image processing method according to claim 8, wherein each of the corresponding points is a predetermined point in each respective block.

13. The image processing method according to claim 9, further comprising a motion vector calculation step of calculating motion vectors at respective corresponding points, based on the positions of corresponding points between the frame images determined in said determination step.

14. The image processing method according to claim 13, further comprising a block expansion step of, among representative points of adjacent blocks, if the difference between the directions of the motion vectors at the representative points of the adjacent blocks is smaller than a predetermined threshold value, combining the adjacent blocks into a larger-sized block,

wherein in said corresponding-point determination step, the corresponding points between the frame images are determined, based on the block generated in said block expansion step.

15. An image processing method for processing images for stereoscopic vision, obtained by image-sensing an object from a plurality of view points, comprising:

a division step of dividing the respective images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images and so as not to include adjacent pixels whose binocular disparities differ from each other by more than a predetermined threshold value and

a corresponding-point determination step of determining corresponding points between the images, each having blocks generated in said division step, based on similarity, each between one block of one image and that of another image.

16. An image processing method according to claim 15,

said each block'"'"'s side is generated on the basis of the difference between adjacent pixels'"'"' intensities.

17. An image processing method according to claim 15,

said each block'"'"'s side is generated on the basis of the difference between adjacent pixels'"'"' colors.

18. An image processing method according to claim 15,

an edge based division step of dividing said images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images;

an edge based corresponding-point determination step of determining corresponding points between the images, each having blocks generated in said division step, based on similarity, each between one block of one image and that of another image; and

a generation step of generating another block by combining adjacent blocks if the difference between the binocular disparity of the representative points of the adjacent blocks is smaller than a predetermined threshold value.

19. An image processing method for processing motion images, obtained by image-sensing an object at different time points, comprising:

a division step of dividing the respective images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images and so as not to include adjacent pixels whose motion vectors differ from each other by a predetermined threshold value and

a corresponding-point determination step of determining corresponding points between the images, each having blocks generated in said division step, based on similarity, each between one block of one image and that of another image.

20. An image processing method according to claim 19,

said each block'"'"'s side is generated on the basis of the difference between adjacent pixels'"'"' intensities.

21. An image processing method according to claim 19,

said each block'"'"'s side is generated on the basis of the difference between adjacent pixels'"'"' colors.

22. An image processing method according to claim 19,

an edge based division step of dividing said images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images;

an edge based corresponding-point determination step of determining corresponding points between the images, each having blocks generated in said division step, based on similarity, each between one block of one image and that of another image; and

a generation step of generating another block by combining adjacent blocks if the difference between motion vectors of the representative points of the adjacent blocks is smaller than a predetermined threshold value.

23. An image processing method according to claim 21, said motion vector is a vector connecting said corresponding points between said motion images.

24. An image processing apparatus for processing images for stereoscopic vision, obtained by image-sensing an object from a plurality of view points, comprising:

division means for dividing the respective images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images;

size changing means for changing a size of a block of interest by combining its adjacent block or blocks out of the plurality of blocks generated by said division means into one block when the block of interest and the adjacent block or blocks have predetermined relationship; and

corresponding-point determination means for determining corresponding points between the images, each having blocks generated by said division means and said size changing means, based on similarity, each between one block of one image and that of another image.

25. The image processing apparatus according to claim 24, wherein the similarity is decided based upon a distance between feature vectors of a block of one image and a block of a corresponding image.

26. The image processing apparatus according to claim 25, wherein the feature vector include luminance of each pixel as a feature vector'"'"'s component.

27. The image processing apparatus according to claim 25, wherein the feature vectors include densities of respective three primary color components in each pixel.

28. The image processing apparatus according to claim 24, wherein each of the corresponding points is a predetermined point in each respective block.

29. The image processing apparatus according to claim 24, further comprising a depth calculation means for calculating depths of respective points of the object, based on positions of the corresponding points between the images, determined in said determination means, and image-sensing positions where the object is image-sensed.

30. The image processing apparatus according to claim 29, further comprising a block expansion means of, among representative points of adjacent blocks, if the difference between the depths of the representative points is smaller than a predetermined threshold value, the adjacent blocks are combined into a larger-sized block,

wherein in said corresponding-point determination means, the corresponding points between the images are determined, based on the block generated in said block expansion means.

31. An image processing apparatus of processing motion images obtained by image-sensing an object at different time points, comprising:

division means for dividing frame images of the motion images, each into a plurality of blocks, so as not to intersect each block'"'"'s side with any edges in the images;

size changing means for changing a size of a block of interest by combining its adjacent block or blocks out of the plurality of blocks generated by said division means into one block when the block of interest and the adjacent block or blocks have predetermined relationship; and

corresponding-point determination means for determining corresponding points between the frame images, each having blocks generated by said division means and said size changing means, based on similarity between one block of one frame image and that of a corresponding frame image.

32. The image processing apparatus according to claim 31, wherein the similarity is decided based upon a distance between feature vectors of a block of one image and a block of a corresponding image.

33. The image processing apparatus according to claim 32, wherein the feature vectors include luminance of each pixel as a feature vector'"'"'s component.

34. The image processing apparatus according to claim 32, wherein the feature vectors include densities of respective three primary color components in each pixel.

35. The image processing apparatus according to claim 31, wherein each of the corresponding points is a predetermined point in each respective block.

36. The image processing apparatus according to claim 32, further comprising a motion vector calculation means for calculating motion vectors at respective corresponding points, based on the positions of corresponding points between the frame images determined in said determination means.

37. The image processing apparatus according to claim 36, further comprising a block expansion means of, among representative points of adjacent blocks, if the difference between the directions of the motion vectors at the representative points of the adjacent blocks is smaller than a predetermined threshold value, combining the adjacent blocks into a larger-sized block,

wherein in said corresponding-point determination means, the corresponding points between the frame images are determined, based on the block generated in said block expansion means.

38. An image processing apparatus for processing images for stereoscopic vision, obtained by image-sensing an object from a plurality of view points, comprising:

a division means for dividing the respective images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images and so as not to include adjacent pixels whose binocular disparities differ from each other by more than a predetermined threshold value and

a corresponding-point determination means for determining corresponding points between the images, each having blocks generated in said division means, based on similarity, each between one block of one image and that of another image.

39. An image processing apparatus according to claim 38,

said each block'"'"'s side is generated on the basis of the difference between adjacent pixels'"'"' intensities.

40. An image processing apparatus according to claim 38,

said each block'"'"'s side is generated on the basis of the difference between adjacent pixels'"'"' colors.

41. An image processing apparatus according to claim 38,

an edge based division means for dividing said images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images;

an edge based corresponding-point determination means for determining corresponding points between the images, each having blocks generated in said division means, based on similarity, each between one block of one image and that of another image; and

a generation means for generating another block by combining adjacent blocks if the difference between the binocular disparity of the representative points of the adjacent blocks is smaller than a predetermined threshold value.

42. An image processing apparatus for processing motion images, obtained by image-sensing an object at different time points, comprising:

a division means for dividing the respective images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images and so as not to include adjacent pixels whose motion vectors differ from each other by more than a predetermined threshold value and

a corresponding-point determination means for determining corresponding points between the images, each having blocks generated in said division means, based on similarity, each between one block of one image and that of another image.

43. An image processing apparatus according to claim 42,

said each block'"'"'s side is generated on the basis of the difference between adjacent pixels'"'"' intensities.

44. An image processing apparatus according to claim 42,

said each block'"'"'s side is generated on the basis of the difference between adjacent pixels'"'"' colors.

45. An image processing apparatus according to claim 42,

an edge based division means for dividing said images into a plurality of blocks so as not to intersect each block'"'"'s side with any edges in the images;

an edge based corresponding-point determination means for determining corresponding points between the images, each having blocks generated in said division means, based on similarity, each between one block of one image and that of another image; and

a generation means for generating another block by combining adjacent blocks if the difference between motion vectors of the representative points of the adjacent blocks is smaller than a predetermined threshold value.

46. An image processing apparatus according to claim 44, said motion vector is a vector connecting said corresponding points between said motion images.

47. An image processing method for processing stereo images obtained by sensing an object from a plurality of view points, comprising:

a first dividing step of dividing each of the stereo images into a plurality of blocks of a predetermined size;

a first corresponding point determining step of determining corresponding points between the stereo images divided in said dividing step, on the basis of similarity between a block of one stereo image and a block of another stereo image;

a parallax distribution extracting step of extracting a distribution of parallax between the corresponding points;

a discontinuous boundary line extracting step of detecting a discontinuous boundary line in the distribution of parallax;

a second dividing step of re-dividing each image of the stereo images into a plurality of blocks so as not to include the discontinuous boundary line in each block; and

a second corresponding point determining step of determining corresponding points between the stereo images re-divided in said second dividing step, on the basis of similarity between a block of one stereo image and a block of another stereo image.

48. The image processing method according to claim 47, wherein the similarity is decided based upon a distance between feature vectors of a block of one image and a block of a corresponding image.

49. The image processing method according to claim 48, wherein the feature vector include luminescence of each pixel as a feature vector'"'"'s component.

50. The image processing method according to claim 48, wherein the feature vectors include densities of respective three primary color components in each pixel.

51. The image processing method according to claim 47, wherein each of the corresponding points is a predetermined point in each respective block.

52. The image processing method according to claim 47, further comprising a depth calculation step of calculating depths of respective points of the object, based on positions of the corresponding points between the images, determined in said determination steps, and image-sensing positions where the object is image-sensed.

53. The image processing method according to claim 52, further comprising a block expansion of, among representative points of adjacent blocks, if the difference between the depths of the representative points is smaller than a predetermined threshold value, the adjacent blocks are combined into a larger-sized block,

wherein in said corresponding-point determination steps, the corresponding points between the images are determined, based on the block generated in said block expansion step.

54. An image processing apparatus for processing stereo images obtained by sensing an object from a plurality of view points, comprising:

first dividing means for dividing each of the stereo images into a plurality of blocks of a predetermined size;

first corresponding point determining means for determining corresponding points between the stereo images, divided by said first dividing means, on the basis of similarity between a block of one stereo image and a block of the other stereo image;

parallax distribution extracting means for extracting a distribution of parallax between the corresponding points;

discontinuous boundary line extracting means for detecting a discontinuous boundary line in the distribution of parallax;

a second dividing means for dividing each image of the stereo images into a plurality of blocks so as not to include the discontinuous boundary line in each block; and

a second corresponding point determining means for determining corresponding points between the stereo images, divided by said second dividing means, on the basis of similarity between a block of one stereo image and a block of the other stereo image.

55. The image processing apparatus according to claim 54, wherein the similarity is decided based upon a distance between feature vectors of a block of one image and a block of a corresponding image.

56. The image processing apparatus according to claim 55, wherein the feature vectors include luminescence of each pixel as a feature vector'"'"'s component.

57. The image processing apparatus according to claim 55, wherein the feature vectors include densities of respective three primary color components in each pixel.

58. The image processing apparatus according to claim 54, wherein each of the corresponding points is a predetermined point in each respective block.

59. The image processing apparatus according to claim 54, further comprising a depth calculation means for calculating depths of respective points of the object, based on positions of the corresponding points between the images, determined by said determination means, and image-sensing positions where the object is image-sensed.

60. The image processing apparatus according to claim 59, further comprising a block expansion means of, among representative points of adjacent blocks, if the difference between the depths of the representative points is smaller than a predetermined threshold value, the adjacent blocks are combined into a larger-sized block,

wherein in said corresponding-point determination means, the corresponding points between the images are determined, based on the block generated in said block expansion means.

61. An image processing method for processing a motion image obtained by sensing an object at different times, comprising:

a first dividing step of dividing each of the motion image into a plurality of blocks of a predetermined size;

a first corresponding point determining step of determining corresponding points between each image of the motion image, divided in said first dividing step, on the basis of similarity between a block of one image of the motion image and a block of another image of the motion image;

a vector distribution extracting step of extracting a distribution of movement vectors between the corresponding points determined in said first corresponding point determining step;

a discontinuous boundary line extracting step of detecting a discontinuous boundary line in the distribution of movement vectors;

a second dividing step of dividing each image of the motion image into a plurality of blocks so as not to include the discontinuous boundary line in each block; and

a second corresponding point determining step of determining corresponding points between each image of the motion image, divided in said second dividing step, on the basis of similarity between a block of one image of the motion image and a block of another image of the motion image.

62. The image processing method according to claim 61, wherein the similarity is decided based upon a distance between feature vectors of a block of one image and a block of a corresponding image.

63. The image processing method according to claim 62, wherein the feature vectors include luminescence of each pixel as a feature vector'"'"'s component.

64. The image processing method according to claim 62, wherein the feature vectors include densities of respective three primary color components in each pixel.

65. The image processing method according to claim 61, wherein each of the corresponding points is a predetermined point in each respective block.

66. The image processing method according to claim 61, further comprising a depth calculation step of calculating depths of respective points of the object, based on positions of the corresponding points between the images, determined in said determination steps, and image-sensing positions where the object is image-sensed.

67. The image processing method according to claim 66, further comprising a block expansion of, among representative points of adjacent blocks, if the difference between the depths of the representative points is smaller than a predetermined threshold value, the adjacent blocks are combined into a larger-sized block,

wherein in said corresponding-point determination steps, the corresponding points between the images are determined, based on the block generated in said block expansion step.

68. An image processing apparatus for processing a motion image obtained by sensing an object at different times, comprising:

first dividing means for dividing each of the motion image into a plurality of blocks of a predetermined size;

first corresponding point determining means for determining corresponding points between each image of the motion image, divided by said first dividing means, on the basis of similarity between a block of one image of the motion image and a block of another image of the motion image;

vector distribution extracting means for extracting a distribution of movement vectors between the corresponding points determined by said first corresponding point determining means;

discontinuous boundary line extracting means for detecting a discontinuous boundary line in the distribution of movement vectors;

second dividing means for dividing each image of the motion image into a plurality of blocks so as not to include the discontinuous boundary line in each block; and

second corresponding point determining means for determining corresponding points between each image of the motion image, divided by said second dividing means, on the basis of similarity between a block of one image of the motion image and a block of another image of the motion image.

69. The image processing apparatus according to claim 68, wherein the similarity is decided based upon a distance between feature vectors of a block of one image and a block of a corresponding image.

70. The image processing apparatus according to claim 69, wherein the feature vectors include luminescence of each pixel as a feature vector'"'"'s component.

71. The image processing apparatus according to claim 69, wherein the feature vectors include densities of respective three primary color components in each pixel.

72. The image processing apparatus according to claim 68, wherein each of the corresponding points is a predetermined point in each respective block.

73. The image processing apparatus according to claim 68, further comprising a depth calculation means for calculating depths of respective points of the object, based on positions of the corresponding points between the images, determined by said determination means, and image-sensing positions where the object is image-sensed.

74. The image processing apparatus according to claim 73, further comprising a block expansion means of, among representative points of adjacent blocks, if the difference between the depths of the representative points is smaller than a predetermined threshold value, the adjacent blocks are combined into a larger-sized block,

wherein in said corresponding-point determination means, the corresponding points between the images are determined, based on the block generated in said block expansion means.