Method for reconstructing a three-dimensional surface of an object

• US 20090022393A1
• Filed: 12/10/2007
• Published: 01/22/2009
• Est. Priority Date: 04/07/2005
• Status: Active Grant

• Current Assignee: Visionsense Ltd. (Medtronic Plc)
• Original Assignee: Visionsense Ltd. (Medtronic Plc)
• Inventors: Yaron, Avi, Bar-Zohar, Meir
• Granted Patent: US 7,990,371 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06T 7/593 from stereo images

Abstract

Method for determining a disparity value of a disparity of each of a plurality of points on an object, the method including the procedures of detecting by a single image detector, a first image of the object through a first aperture, and a second image of the object through a second aperture, correcting the distortion of the first image, and the distortion of the second image, by applying an image distortion correction model to the first image and to the second image, respectively, thereby producing a first distortion-corrected image and a second distortion-corrected image, respectively, for each of a plurality of pixels in at least a portion of the first distortion-corrected image representing a selected one of the points, identifying a matching pixel in the second distortion-corrected image, and determining the disparity value according to the coordinates of each of the pixels and of the respective matching pixel.

Claims

1. Method for determining a disparity value of a disparity of each of a plurality of points on an object, the method comprising the procedures of:

detecting by a single image detector, a first image of said object through a first aperture, and a second image of said object through a second aperture;

correcting the distortion of said first image, and the distortion of said second image, by applying an image distortion correction model to said first image and to said second image, respectively, thereby producing a first distortion-corrected image and a second distortion-corrected image, respectively;

for each of a plurality of pixels in at least a portion of said first distortion-corrected image representing a selected one of said points, identifying a matching pixel in said second distortion-corrected image; and

determining said disparity value according to coordinates of each of said pixels and the respective said matching pixel.

2. The method according to claim 1, further comprising a procedure of determining a confidence percent level respective of said procedure of identifying said matching pixel.

3. The method according to claim 1, further comprising the procedures of:

reconstructing an image according to said first image and said second image;

marking a point among said points, on said reconstructed image by a user, via a user interface;

determining a distance value of a distance from said point to said single image detector, according to said disparity value; and

displaying said distance value on a display.

4. The method according to claim 3, further comprising the procedures of:

determining a confidence percent level respective of said distance value; and

displaying said confidence percent level on said display.

5. The method according to claim 1, further comprising a procedure of determining a geometric parameter respective of said object, according to said disparity value.

6. The method according to claim 5, wherein said geometric parameter is selected from the list consisting of:

volume;

mass;

surface area; and

the amount by which said object protrudes from a background.

7. The method according to claim 1, wherein said procedure of identifying said matching pixel is performed by a method selected from the list consisting of:

cross correlation;

vectorial gradient;

cross entropy;

squares of differences;

absolute value of differences;

histogram; and

Kalmagorov distance method.

8. The method according to claim 1, wherein said procedure of identifying said matching pixel is performed according to a parameter of said pixels, said parameter being selected from the list consisting of:

intensity;

directional differential of an intensity of each of said pixels along a horizontal axis of said single image detector; and

directional differential of said intensity along a vertical axis of said single image detector.

9. The method according to claim 1, further comprising the procedures of:

constructing a disparity map respective of said points, according to said disparity values, and

eliminating said disparity value from said disparity map, according to a predetermined criterion.

10. The method according to claim 9, wherein said criterion is selected from the list consisting of:

said disparity value being larger than a certain multiple of a standard deviation of the average disparity of a predetermined number of pixels, in the neighborhood of a pixel in an image detected by said single image detector;

a similarity level parameter respective of said procedure of identifying said matching pixel, is larger than a certain multiple of a standard deviation of the average similarity level parameter respective of said predetermined number of said pixels; and

a cross validation of a surface normal associated with said pixel being unacceptable.

11. The method according to claim 9, further comprising a procedure of determining an interpolated disparity value in place of said eliminated disparity value, by employing an interpolation procedure to interpolate between disparity values adjacent to said eliminated disparity value.

12. The method according to claim 11, wherein said interpolation procedure is a radial basis function.

13. The method according to claim 11, further comprising a procedure of determining the validity of said interpolation procedure by,

producing an empirical disparity map according to said disparity values,

producing a controlled disparity map by applying a known disparity function to said first image, and

comparing said empirical disparity map with said controlled disparity map.

14. The method according to claim 13, wherein said known disparity function is a parabolic function.

15. The method according to claim 1, wherein another disparity value is determined, by performing said procedure of identifying said matching pixel, while said first distortion-corrected image is replaced with said second distortion-corrected image,

wherein a calculated disparity value is calculated for said point, when a sum of said disparity value and said other disparity value is within a predetermined range, said calculated disparity value being equal to an average of absolute values of said disparity value and said other disparity value, times the sign of said disparity value,

wherein said disparity value is selected for said point, when said sum is equal to zero,

wherein a disparity map is constructed respective of said points, according to said disparity value and said calculated disparity value, and

wherein said disparity value is eliminated from said disparity map, when said sum is outside said predetermined range.

41. Method according to any of claims 1-40 substantially as described hereinabove.

42. Method according to any of claims 1-40 substantially as illustrated in any of the drawings.

16. Method for determining disparity value of a disparity of a point on an object being detected by at least one image detector, according to a stereoscopic color image pair of the object, the point being represented by a plurality of pixels in each image of the stereoscopic color image pair, the method comprising the procedures of:

producing a first set of distortion-corrected color images respective of each of a plurality of colors of said at least one image detector, by applying an image distortion correction model to a first distorted image among said stereoscopic color image pair;

producing a second set of distortion-corrected color images respective of said colors, by applying said image distortion correction model to a second distorted image among said stereoscopic color image pair;

producing a set of modified images by determining at least one interpolated pixel between every two adjacent actual pixels in each row of each of said distortion-corrected color images of said second set of distortion-corrected color images;

determining a distance range between said object and said at least one image detector;

determining a disparity range respective of said stereoscopic color image pair, according to said distance range;

defining a window of a predetermined size around an actual pixel in each of said distortion-corrected color images of said first set of distortion-corrected color images;

defining a plurality of windows around a plurality of central pixels in each of said modified images, the size of each of said windows being the same as said predetermined size, said central pixels having the same row indices respective of the row of said actual pixel, and a plurality of column indices within said disparity range from the column index of said actual pixel;

determining a plurality of color intensity distribution differences between the color intensity distribution of said window and each of said windows;

selecting a minimum color intensity distribution difference among said color intensity distribution differences;

selecting a central pixel among said central pixels, as a pixel which matches said actual pixel, said central pixel corresponding to a selected window among said windows, said selected window corresponding to said minimum color intensity distribution difference; and

determining said disparity value according to a difference between the coordinates of said actual pixel and of said selected central pixel.

17. The method according to claim 16, wherein said procedure of producing said set of modified images is performed by interpolating between every two of said adjacent pixels.

18. The method according to claim 16, wherein said procedure of defining said windows is performed around respective ones of said central pixels, selected as said at least one interpolated pixel.

19. The method according to claim 16, wherein said procedure of selecting said central pixel is performed by:

determining a similarity level parameter between said window associated with each of said first set of distortion-corrected color images, and each of said windows in said modified images; and

selecting said similarity level parameter as the one having the lowest value among said similarity level parameters.

20. The method according to claim 16, wherein each of said windows in said modified images includes selected ones of said at least one interpolated pixels, when a central pixel of said central pixels is an interpolated pixel, and

wherein said windows in said modified images includes said actual pixels, when said central pixel is not an interpolated pixel.

21. The method according to claim 16, further comprising the procedures of:

determining a confidence percent level respective of said procedure of selecting said central pixel; and

reducing said disparity range when said confidence percent level is greater than a predetermined threshold.

22. The method according to claim 16, further comprising a procedure of determining the validity of said method by,

producing an empirical disparity map according to a plurality of disparity values,

producing a controlled disparity map by applying a known disparity function to said first distorted image, and

comparing said empirical disparity map with said controlled disparity map.

23. The method according to claim 22, wherein said known disparity function is a parabolic function.

24. Method for determining a disparity value of a disparity of a point on an object being detected by at least one image detector, according to a stereoscopic color image pair of the object, the point being represented by a plurality of pixels in each image of the stereoscopic color image pair, the method comprising the procedures of:

producing a first set of distortion-corrected color images respective of each of a plurality of colors of said at least one image detector, by applying an image distortion correction model to a first distorted image among said stereoscopic color image pair;

producing a second set of distortion-corrected color images respective of said colors, by applying said image distortion correction model to a second distorted image among said stereoscopic color image pair;

applying a first filter to each of said distortion-corrected color images in said first set and in said second set;

producing a set of modified images by determining at least one interpolated pixel between every two adjacent actual pixels in each row of each of said filtered distortion-corrected color images of said second set of distortion-corrected color images;

determining a distance range between said object and said at least one image detector;

determining a disparity range respective of said stereoscopic color image pair, according to said distance range;

defining a window of a predetermined size around an actual pixel in each of said distortion-corrected color images of said first set of distortion-corrected color images;

defining a plurality of windows around a plurality of central pixels in each of said modified images, the size of each of said windows being the same as said predetermined size, said central pixels having the same row indices respective of the row of said actual pixel, and a plurality of column indices within said disparity range from the column index of said actual pixel;

determining a linear function of an absolute value of vectorial gradients, of another absolute value of vectorial gradient differences, and of the absolute value of the difference between color image intensities, respective of said window and of respective ones of each of said windows;

selecting a minimum value among said linear functions;

selecting a central pixel among said central pixels, as a pixel which matches said actual pixel, said central pixel corresponding to a selected window among said windows, said selected window corresponding to said selected minimum value; and

determining said disparity value according to a difference between the coordinates of said actual pixel and of said selected central pixel.

25. The method according to claim 24, wherein each of said first filter and said second filter is a low-pass filter.

26. The method according to claim 24, further comprising the procedures of:

constructing a disparity map respective of a plurality of points of said object, according to a plurality of disparity values respective of said points, and

eliminating said disparity value from said disparity map, according to a predetermined criterion.

27. The method according to claim 26, wherein said criterion is selected from the list consisting of:

said disparity value being larger than a certain multiple of a standard deviation of the average disparity of a predetermined number of pixels, in the neighborhood of a pixel in an image detected by an image detector;

a similarity level parameter respective of said procedure of identifying said matching pixel, is larger than a certain multiple of a standard deviation of the average similarity level parameter respective of said predetermined number of said pixels; and

a cross validation of a surface normal associated with said pixel being unacceptable.

28. The method according to claim 24, wherein another disparity value is determined, by performing said procedure of selecting said central pixel, while said procedure of defining said window is performed with respect to each of said modified images, and said procedure of defining said windows is performed with respect to said first set of distortion-corrected color images,

wherein a calculated disparity value is calculated for said point, when a sum of said disparity value and said other disparity value is within a predetermined range, said calculated disparity value being equal to an average of absolute values of said disparity value and said other disparity value, times the sign of said disparity value,

wherein said disparity value is selected for said point, when said sum is equal to zero,

wherein a disparity map is constructed respective of said points, according to said disparity value and said calculated disparity value, and

wherein said disparity value is eliminated from said disparity map, when said sum is outside said predetermined range.

29. The method according to claim 24, further comprising a procedure of determining the validity of said method by,

producing an empirical disparity map according to a plurality of disparity values,

producing a controlled disparity map by applying a known disparity function to said first distorted image, and

comparing said empirical disparity map with said controlled disparity map.

30. The method according to claim 29, wherein said known disparity function is a parabolic function.

31. Method for determining a center of distortion of a first distorted image and a second distorted image of a target, the method comprising the procedures of:

determining two-dimensional coordinates of a plurality of known points of said target, in said first distorted image and in said second distorted image;

correcting two-dimensional locations of said two-dimensional coordinates, in said first distorted image and in said second distorted image, according to an image distortion correction model, whose origin is selected as an image detector center;

determining a first transformation model and a second transformation model, according to respective ones of said corrected two-dimensional locations, and according to three-dimensional coordinates of said known points;

determining a first set of calculated points and a second set of calculated points, by applying said first transformation model and said second transformation model, respectively, to said three-dimensional coordinates;

determining a first set of distorted calculated points and a second set of distorted calculated points, by applying an image distortion model to said first set of calculated points and to said second set of calculated points, respectively, about a set of auxiliary centers different than said image detector center;

determining a first set of distances between respective points in said first distorted image and said first set of distorted calculated points;

determining a second set of distances between respective points in said second distorted image and said second set of distorted calculated points; and

selecting one of said auxiliary centers as said center of distortion, said auxiliary center corresponding to a minimum characteristic value respective of said first set of distances and said second set of distances.

32. The method according to claim 31, wherein each of said first transformation model and said second transformation model is represented by a matrix which is equal to a product of an intrinsic parameter matrix and an extrinsic parameter matrix, said intrinsic parameter matrix being respective of a plurality of intrinsic parameters respective of at least one image detector detecting first distorted image and said second distorted image, and said extrinsic parameter matrix being respective of a plurality of extrinsic parameters respective of said at least one image detector.

33. The method according to claim 31, further comprising the procedures of:

determining a first representative distance according to said first set of distances; and

determining a second representative distance according to said second set of distances.

34. The method according to claim 33, wherein said procedure of determining said first representative distance is performed by performing a procedure selected from the list consisting of:

determining a sum of absolute values of said first set of distances;

determining a sum of squares of said first set of distances; and

determining a median value of said first set of distances, and

wherein said procedure of determining said second representative distance is performed by performing a procedure selected from the list consisting of;

determining a sum of absolute values of said second set;

determining a sum of squares of said second set of distances; and

determining a median value of said second set of distances.

35. The method according to claim 33, wherein said procedure of determining said minimum characteristic value is determined by performing a procedure selected from the list consisting of:

determining a sum of said first representative distance and said second representative distance;

determining a sum of squares of said first representative distance and said second representative distance;

determining a median value of said first representative distance and said second representative distance; and

determining a median value of first set of distances and said second set of distances.

36. Image distortion correction model for correcting an image distortion in a first distorted image and in a second distorted image of a stereoscopic image pair of an object being detected by an optical device, the image distortion correction model being defined by,

$f_c^X$

( X , Y ) = a 00 + a 01 

x ′

+ a 20 

x ′

2 + a 30 

x ′

3 + a 50 

x ′

5 + a 02 

y ′

2 + a 12 

x ′



y ′

2 + a 22 

x ′

2 

y ′

2 + a 32 

x ′

3 

y ′

2 + a 52 

x ′

5 

y ′

2

in a horizontal direction, and by,

$f_c^Y<br><br>\left(X,Y\right)=c_{01}<br><br>y^{\mathrm{\prime <br><br>}}+c_{11}<br><br>x^{\mathrm{\prime <br><br>}}<br><br>y^{\mathrm{\prime <br><br>}}+c_{21}<br><br>x^{\mathrm{\prime <br><br>2}}<br><br>y^{\mathrm{\prime <br><br>}}+c_{30}<br><br>y^{\mathrm{\prime <br><br>3}}+c_{13}<br><br>x^{\mathrm{\prime <br><br>}}<br><br>y^{\mathrm{\prime <br><br>3}}+c_{23}<br><br>x^{\mathrm{\prime <br><br>2}}<br><br>y^{\mathrm{\prime <br><br>3}}+c_{05}<br><br>y^{\mathrm{\prime <br><br>5}}+c_{15}<br><br>x^{\mathrm{\prime <br><br>}}<br><br>y^{\mathrm{\prime <br><br>5}}+c_{25}<br><br>x^{\mathrm{\prime <br><br>2}}<br><br>y^{\mathrm{\prime <br><br>5}}$

in a vertical direction, wherein x′

is defined by,

$x^{\mathrm{\prime <br><br>}}=\frac{\left(x-x_0\right)}{x_{\max }}$

and y′

is defined by,

$y^{\mathrm{\prime <br><br>}}=\frac{\left(y-y_0\right)}{y_{\max }}$

wherein x and y are the indices of a current pixel in each of said first distorted image and said second distorted image,

wherein x₀ and y₀ define a center of distortion of said first distorted image and of said second distorted image,

wherein x_max is a distance along said horizontal direction, between a center of a substantially rectangular undistorted calculated image and a side of said substantially rectangular undistorted calculated image, said substantially rectangular undistorted calculated image being respective of said optical device,

wherein y_max is another distance along said vertical direction, between said center and another side of said substantially rectangular undistorted calculated image,

wherein parameters a₀₀, a₀₁, a₂₀, a₃₀, a₅₀, a₀₂, a₁₂, a₂₂, a₃₂, a₅₂, c₀₁, c₁₁, c₂₁, c₃₀, c₁₃, c₂₃, c₀₅, c₁₅ and c₂₅ are a set of coefficients which are determined by solving a set of simultaneous Equations for a set of points, each point having the indices x and y, said points being respective of a target being detected by said optical device, the coordinates of said points being known in a global coordinate system,

wherein f_c^X(X,Y) designates a horizontal distortion of a point among said points, said horizontal distortion being along said horizontal direction,

wherein f_c^Y(X,Y) designates a vertical distortion of said point along said vertical direction, and

wherein x₀ and y₀ are set to an image center of said substantially rectangular undistorted calculated image.

37. Method for providing a stereoscopic perception of a scene for a user, such that the vision associated complexions experienced by the user are minimized, the method comprising the procedures of:

determining a shift between a pair of stereoscopic images to be displayed to said user, said shift being associated with stereoscopic viewing characteristics of said user;

receiving another pair of stereoscopic images shifted relative to one another by a current shift, said other pair of stereoscopic images being respective of said scene;

shifting said other pair of stereoscopic images by the difference between said determined shift and said current shift; and

displaying said other pair of shifted stereoscopic images.

38. Method for varying a local disparity between each depth plane pair of each of a plurality of depth plane pairs, each depth plane of the depth plane pairs defining the depth of a given set of pixels in a first image and a second image of a stereoscopic image pair of an object, relative to an image detector detecting the stereoscopic image pair, the method comprising the procedures of:

determining a pixel depth for each of said pixels, in said first image and in said second image, from a three-dimensional reconstruction of a volume represented by said stereoscopic image pair;

determining a plurality of depth planes at a plurality of different plane depths, for said first image and said second image, each of said depth planes being substantially perpendicular to a line of sight respective of a respective one of the eyes of an observer;

associating each of said depth planes from said first image, with a corresponding depth plane from said second image, at the same plane depth, thereby determining a plurality of depth plane pairs;

associating each of said pixels with a respective one of said depth plane pairs, according to a respective one of said pixel depths, and according to a respective one of said plane depths; and

varying said local disparity by moving every pair of said depth plane pairs, relative to one another, in a direction substantially perpendicular to said line of sight.

39. The method according to claim 38, further comprising a preliminary procedure of acquiring said stereoscopic image pair.

40. The method according to claim 38, wherein said procedure of varying is performed by moving a first set of said depth planes associated with said first image, and a second set of said depth planes associated with said second image, in a uniform manner.