Shape detection and ellipse fitting of a polygon

1. A method of shape detection, comprising the steps of:

detecting a figure with a contouring loop method that extracts at least one iso-contour polygon from a set of pixels in an image using a triangular lattice superimposed over the set of pixels of the image, the triangles of the triangular lattice having vertices on at least one of pixel centers and pixel corners; and

starting from an original triangle,

extracting the iso-contour polygon by selecting an intensity chroma value within the set of pixels between three corners of a triangle to find a directed line segment that represent the crossing of the intensity value within the triangle, and

determining an exit point of the directed line segment and a nearest triangle which contains the next directed line segment of the at least one iso-contour polygon to create a first matrix of points [B] on the at least one iso-contour polygon,

until arriving at the original triangle.

2. The method of claim 1 further comprising the steps of:

determining a center of mass of the at least one iso-contour polygon;

determining a circle centered at the center of mass within the iso-contour polygon and a second matrix of points [A] on the circle used with the first matrix of points [B] to create a linear transform matrix that represents a fit between the points in the first and second matrices; and

determining minor and major axes of a detected ellipse by extracting eigenvectors and eigenvalues from the linear transform matrix.

3. The method of claim 2 further comprising the step of adjusting the minor and major axes for boundary shift distortion.

4. The method of claim 2 , wherein the step of determining a center of mass further comprises the steps of:

collecting a sequence of points describing the polygon from the first matrix [B];

creating a triangle fan between a first point and the remaining sequence of points;

determining the signed area and respective center of mass for each triangle of the triangle fan; and

calculating the center of mass of the polygon using a weighted average of the respective center of masses for all triangles in the triangle fan.

5. The method of claim 2 further comprising:

creating a linear transform matrix [M] by,

creating a second matrix of points [A] on a circle with its center at the center of mass of the polygon, and

using a linear transform matrix [M] and a least squares fit method where M=AB(B T B) −1 ; and

determining the best fit ellipse from the transform matrix [M] by extracting eigenvectors and eigenvalues to determine a semi-major axis and a semi-minor axis of the best fit ellipse.

6. The method of claim 5 wherein the step of determining the best fit ellipse is refined iteratively by creating a new matrix [A] with a center adjusted by the origin of the previous matrix [M] and recalculating a new matrix [M].

7. The method of claim 5 further comprising the step of adjusting the semi-minor and semi-major axes for boundary shift distortion.

8. The method of claim 1 further comprising the step of using linear interpolation between the three corners of the triangle to find the directed line segment.

9. The method of claim 1 further comprising the step of fitting the extracted iso-contour polygon with ellipses to evaluate for quality of the fit by best fit ellipse.

10. A non-transitory computer readable medium having computer readable instructions stored thereon that if executed by a processor, cause the processor to process sets of pixels in image data for shape detection using the method of claim 1 .

11. A method of fitting an ellipse to a polygon, comprising the steps of:

collecting a sequence of points describing the polygon in a first matrix [B];

creating a triangle fan between a first point and the remaining sequence of points;

determining the signed area and respective center of mass for each triangle of the triangle fan;

calculating the center of mass of the polygon using a weighted average of the respective center of masses for all triangles in the triangle fan;

creating a second matrix of points [A] on a circle with its center at the center of mass of the polygon; and

translating the points on the circle to their closest point on the polygon.

12. The method of claim 11 wherein translating the points includes using a linear transform matrix [M] and a least squares fit method where M=AB(B T B) −1 .

13. The method of claim 11 wherein fitting an ellipse is refined iteratively by:

creating a new matrix [A] with a center adjusted by the origin of the previous matrix [M]; and

recalculating a new matrix [M].

14. The method of claim 11 further including the step of detecting the polygon in a raster image with an iso-contour algorithm.

15. The method of claim 11 further including the step of determining the best fit ellipse from the transform matrix [M] by extracting eigenvectors and eigenvalues to determine the semi-major and semi-minor axes of the best fit ellipse.

16. The method of claim 15 further comprising the step of adjusting the semi-minor and semi-major axes for boundary shift distortion.

17. The method of claim 11 further comprising the step of detecting a figure with a contouring loop method that extracts at least one iso-contour polygon from a set of pixels in an image using a triangular lattice superimposed over the set of pixels of the image, the triangles of the triangular lattice having vertices on at least one of pixel centers and pixel corners; and

starting from an original triangle,

extracting the iso-contour polygon by selecting an intensity chroma value within the set of pixels between three corners of a triangle to find a directed line segment that represent the crossing of the intensity value within the triangle, and

determining an exit point of the directed line segment and a nearest triangle which contains the next directed line segment of the at least one iso-contour polygon to create a first matrix of points on the at least one iso-contour polygon,

until arriving at the original triangle.

18. The method of claim 17 further comprising the steps of:

determining a circle centered at the center of mass within the iso-contour polygon and a second matrix of points on the circle used with the first matrix of points to create a linear transform matrix that represents a fit between the points in the first and second matrices; and

determining minor and major axes of a detected ellipse by extracting eigenvectors and eigenvalues from the linear transform matrix.

19. The method of claim 18 further comprising the step of adjusting the minor and major axes for boundary shift distortion.

20. A non-transitory computer readable medium having computer readable instructions stored thereon that if executed by a processor, cause the processor to fit an ellipse to a polygon using the method of claim 11 .