Fast two dimensional object localization based on oriented edges

1. A method for object localization comprising the steps of:

defining an edge model for object localization;

searching an image for an object matching the edge model comprising the steps of:

defining a region of interest, including a portion of the object;

sub-sampling the region of interest;

extracting an edge image comprising edges from the region of interest;

thinning at least one edge of the edge image;

determining a distance map between the image and the edge image according to a distance transformation; and

matching the edge model to the edge image within a search area defined according to the distance map.

2. The method of claim 1 , wherein the edge image comprising edges is sub-sampled to extract model edge points.

3. The method of claim 1 , wherein the distance map defines a distance for each pixel of the image to a nearest edge pixel of the edge image.

4. The method of claim 1 , wherein the step of matching further comprises the step of determining an error measure according to a distance to a next image edge pixel and a difference in edge orientation.

5. The method of claim 1 , wherein the step of matching further comprises the step of matching the edge model in a plurality of rotations to the edge image.

6. The method of claim 5 , further comprising the step of determining an error for each rotation of the edge model relative to the edge image.

7. The method of claim 6 , wherein determining an error further comprises the steps of:

determining a distance to a next image edge pixels for each model edge point;

determining a difference in edge orientation of corresponding pixels for each model edge;

truncating the distance to the next image edge pixels and the difference in edge orientation;

scaling the distance to the next image edge pixels and the difference in edge orientation to a given interval;

determining a relative weight of the distance to the next image edge pixels and the difference in edge orientation; and

determining an error as a summation of a matching error over all model edge points.

8. The method of claim 1 , wherein defining the edge model comprises the steps of:

defining a region of interest, including a portion an object to be trained;

sub-sampling the region of interest;

extracting a edge model image comprising edges from the region of interest;

thinning at least one edge of the edge model image; and

selecting a number of edge pixels, wherein a selected set of edge pixels comprises the edge model.

9. The method of claim 8 , further comprising the step of determining a plurality of rotated edge models corresponding to the edge model rotated in discrete steps.

10. The method of claim 1 , further comprising the step of matching the edge model to the edge image by iterative closest point, comprising the steps of:

determining, for each pixel in the edge model, a closest edge pixel of the edge image in a corresponding search area;

determining transformation parameters, wherein the transformation parameters minimize a distance between the edge model and the edge image, according to a sum distance of a plurality of pixels of the edge model to a plurality of pixels of the edge image; and

correcting a position of the model according to the transformation parameters.

11. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for object localization, the method steps comprising:

defining an edge model for object localization;

searching an image for an object matching the edge model comprising the steps of:

defining a region of interest, including a portion of the object;

sub-sampling the region of interest;

extracting an edge image comprising edges from the region of interest;

thinning at least one edge of the edge image;

determining a distance map between the image and the edge image according to a distance transformation; and

matching the edge model to the edge image within a search area defined according to the distance map.

12. The method of claim 11 , wherein the edge image comprising edges is sub-sampled to extract model edge points.

13. The method of claim 11 , wherein the distance map defines a distance for each pixel of the image to a nearest edge pixel of the edge image.

14. The method of claim 11 , wherein the step of matching further comprises the step of determining an error measure according to a distance to a next image edge pixel and a difference in edge orientation.

15. The method of claim 11 , wherein the step of matching further comprises the step of matching the edge model in a plurality of rotations to the edge image.

16. The method of claim 15 , further comprising the step of determining an error for each rotation of the edge model relative to the edge image.

17. The method of claim 16 , wherein determining an error further comprises the steps of:

determining a distance to a next image edge pixels for each model edge point;

determining a difference in edge orientation of corresponding pixels for each model edge;

truncating the distance to the next image edge pixels and the difference in edge orientation;

scaling the distance to the next image edge pixels and the difference in edge orientation to a given interval;

determining a relative weight of the distance to the next image edge pixels and the difference in edge orientation; and

determining an error as a summation of a matching error over all model edge points.

18. The method of claim 11 , wherein defining the edge model comprises the steps of:

defining a region of interest, including a portion an object to be trained;

sub-sampling the region of interest;

extracting a edge model image comprising edges from the region of interest;

thinning at least one edge of the edge model image; and

selecting a number of edge pixels, wherein a selected set of edge pixels comprises the edge model.

19. The method of claim 18 , further comprising the step of determining a plurality of rotated edge models corresponding to the edge model rotated in discrete steps.

20. The method of claim 11 , further comprising the step of matching the edge model to the edge image by iterative closest point, comprising the steps of:

determining, for each pixel in the edge model, a closest edge pixel of the edge image in a corresponding search area;

determining transformation parameters, wherein the transformation parameters minimize a distance between the edge model and the edge image, according to a sum distance of a plurality of pixels of the edge model to a plurality of pixels of the edge image; and

correcting a position of the model according to the transformation parameters.