Locating curvilinear objects using feathered fiducials

• US 5,500,906 A
• Filed: 01/14/1994
• Issued: 03/19/1996
• Est. Priority Date: 01/14/1994
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Barber, Frederic, Picard, Len L.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US08/181,328
• Time in Patent Office: 795 Days
• Field of Search: 382/48, 382/30, 382/42, 382/8, 382/291, 382/209, 382/278, 382/151, 382/217, 382/218, 382/220, 348/87, 348/94, 348/95, 356/390, 356/400, 356/401, 356/247, 356/248
• US Class Current: 382/220
• CPC Class Codes: G06V 10/443 by matching or filtering

Abstract

A method and apparatus for locating curvilinear objects of variable scale in digitized images using feathered fiducials. The leathered fiducials are constructed by: defining a range of tolerated object size scale variations; generating an enlarged submodel within the range of tolerated scale variations and assigning background pixel values exterior to the enlarged submodel; generating a reduced size submodel within the range of tolerated scale variations and assigning foreground pixel values to the reduced size submodel; disposing the reduced size submodel within and tangent to the enlarged submodel at the application point; uniformly changing grey scale pixel values in a graduated manner from foreground to background between the reduced size submodel and the enlarged one. The curvilinear objects are then located by conducting searches using the constructed fiducials.

Claims

1. A method for locating a curvilinear object in a digitized image, comprising:

a) defining a range of scale variations;

b) generating an enlarged submodel having dimensions larger than those expected for said curvilinear object within said range of scale variations;

c) generating a reduced size submodel of said curvilinear object having dimensions smaller than those expected for said curvilinear object and within said range of scale variations;

d) disposing said reduced size submodel within said enlarged submodel and tangent to said enlarged submodel;

e) generating a feathered submodel by varying pixel grey scale values between said enlarged and said reduced size submodels;

f) conducting a correlation search of said digitized image of said curvilinear object using said feathered submodel, whereby the point in said digitized image reported by said correlation search as having the highest correlation to said feathered submodel is deemed to be at an edge of said curvilinear object and used to compute a center of said curvilinear object to locate it.

2. The method of claim 1 wherein generating a feathered submodel further comprises computing a fill area between said enlarged submodel and said reduced size submodel.

3. The method of claim 2, wherein defining the range of scale variations further comprises:

a) specifying a nominal submodel size;

b) specifying a percentage of acceptable size variations larger and smaller than said nominal submodel size.

4. The method of claim 2, wherein generating a feathered submodel further comprises creating a smoothly varying grey scale fill in said fill area.

5. The method of claim 2, further comprising creating a radial grey scale fill in said fill area by varying pixel intensity gradually along a radius.

6. The method of claim 2 further comprising:

a) calculating the distance(dr) along a line from an edge of said reduced size submodel to a point being processed in said fill area;

b) calculating the distance(de) along a line from an edge of said enlarged submodel to said point being processed;

c) setting the value of the pixel for said point being processed to a foreground pixel value, fg, scaled to a background pixel value, bg, using the following algorithm;

##EQU3##

7. The method of claim 3, wherein generating a feathered submodel further comprises creating a smoothly varying grey scale fill in said fill area.

8. The method of claim 3, further comprising creating a radial grey scale fill in said fill area by varying pixel intensity gradually along a radius.

9. The method of claim 3 further comprising:

a) calculating the distance(dr) along a line from an edge of said reduced size submodel to a point being processed in said fill area;

b) calculating the distance(de) along a line from an edge of said enlarged submodel to said point being processed;

c) setting the value of the pixel for said point being processed to a foreground pixel value, fg, scaled to a background pixel value, bg, using the following algorithm;

##EQU4##

10. A method for locating a curvilinear object in a digitized image, comprising:

a) defining a range of scale variations by specifying a nominal submodel size and a percentage of acceptable size variations larger and smaller than said nominal submodel size;

b) generating an enlarged submodel having dimensions larger than those expected for said curvilinear object within said range of scale variations;

c) generating a reduced size submodel of said curvilinear object having dimensions smaller than those expected for said curvilinear object and within said range of scale variations;

d) disposing said reduced size submodel within said enlarged submodel and tangent to said enlarged submodel;

e) computing a fill area between said enlarged submodel and said reduced size submodel;

f) generating a feathered submodel having varying pixel grey scale values between said enlarged and said reduced size submodels by creating a smoothly varying grey scale fill in said fill area;

g) conducting a correlation search of said digitized image using said feathered submodel, whereby the point in said digitized image reported by said correlation search as having the highest correlation to said feathered submodel is deemed to be at an edge of said curvilinear object and used to compute a center of said curvilinear object to locate it.

11. A method for locating a curvilinear object in a digitized image, comprising:

a) defining a range of scale variations;

b) generating an enlarged submodel having dimensions larger than those expected for said curvilinear object within said range of scale variations;

c) generating a reduced size submodel of said curvilinear object having dimensions smaller than those expected for said curvilinear object and within said range of scale variations;

d) disposing said reduced size submodel within said enlarged submodel and tangent to said enlarged submodel;

e) computing a fill area between said enlarged submodel and said reduced size submodel;

f) generating a feathered submodel having varying pixel grey scale values between said enlarged and said reduced size submodels by creating a smoothly varying grey scale fill in said fill area;

g) conducting a correlation search of a digitized image of said curvilinear object using said feathered submodel, whereby the point in said digitized image reported by said correlation search as having the highest correlation to said feathered submodel is deemed to be at an edge of said curvilinear object and used to compute a center of said curvilinear object to locate it.

12. An apparatus for locating a curvilinear object in a digitized image, comprising:

a) means for defining a range of scale variations;

b) means for generating an enlarged submodel having dimensions larger than those expected for said curvilinear object within said range of scale variations;

c) means for generating a reduced size submodel of said curvilinear object having dimensions smaller than those expected for said curvilinear object and within said range of scale variations;

d) means for disposing said reduced size submodel within said enlarged submodel and tangent to said enlarged submodel;

e) means for generating a feathered submodel by varying pixel grey scale values between said enlarged and said reduced size submodels;

f) means for conducting a correlation search of said digitized image of said object using said feathered submodel, whereby the point in said digitized image reported by said correlation search as having the highest correlation to said feathered submodel is deemed to be at an edge of said curvilinear object and used to compute a center of said curvilinear object to locate it.

13. The apparatus of claim 12 wherein said means for generating a feathered submodel further comprises means for computing a fill area between said enlarged submodel and said reduced size submodel.

14. The apparatus of claim 13, wherein said means for defining the range of scale variations further comprises:

a) means for specifying a nominal submodel size;

b) means for specifying a percentage of acceptable size variations larger and smaller than said nominal submodel size.

15. The apparatus of claim 13, wherein said means for generating a feathered submodel further comprises means for creating a smoothly varying grey scale fill in said fill area.

16. The apparatus of claim 13, further comprising means for creating a radial grey scale fill in said fill area by varying pixel intensity gradually along a radius.

17. The apparatus of claim 13 further comprising:

a) means for calculating the distance(dr) along a line from an edge of said reduced size submodel to a point being processed in said fill area;

b) means for calculating the distance(de) along a line from an edge of said enlarged submodel to said point being processed;

c) means for setting the value of the pixel for said point being processed to a foreground pixel value, fg, scaled to a background pixel value, bg, using the following algorithm;

##EQU5##

18. The apparatus of claim 14, wherein said means for generating a feathered submodel further comprises means for creating a smoothly varying grey scale fill in said fill area.

19. The apparatus of claim 14 further comprising means for creating a radial grey scale fill in said fill area by varying pixel intensity gradually along a radius.

20. The apparatus of claim 14 further comprising:

a) means for calculating the distance(dr) along a line from an edge of said reduced size submodel to a point being processed in said fill area;

b) means for calculating the distance(de) along a line from an edge of said enlarged submodel to said point being processed;

c) means for setting the value of the pixel for said point being processed to a foreground pixel value, fg, scaled to a background pixel value, bg, using the following algorithm;

##EQU6##

21. An apparatus for locating a curvilinear object in a digitized image, comprising:

a) means for defining a range of scale variations by specifying a nominal submodel size and a percentage of acceptable size variations larger and smaller than said nominal submodel size;

b) means for generating an enlarged submodel having dimensions larger than those expected for said curvilinear object within said range of scale variations;

c) means for generating a reduced size submodel of said curvilinear object having dimensions smaller than those expected for said curvilinear object and within said range of scale variations;

d) means for disposing said reduced size submodel within said enlarged submodel and tangent to said enlarged submodel;

e) means for computing a fill area between said enlarged submodel and said reduced size submodel;

f) means for generating a feathered submodel having varying pixel grey scale values between said enlarged and said reduced size submodels by creating a smoothly varying grey scale fill in said fill area;

g) means for conducting a correlation search of said digitized image of said object using said feathered submodel, whereby the point in said digitized image reported by said correlation search as having the highest correlation to said feathered submodel is deemed to be at an edge of said curvilinear object and used to compute a center of said curvilinear object to locate it.

22. An apparatus for locating a curvilinear object, comprising:

a) means for defining a range of scale variations;

b) means for generating an enlarged submodel having dimensions larger than those expected for said curvilinear object within said range of scale variations;

c) means for generating a reduced size submodel of said curvilinear object having dimensions smaller than those expected for said curvilinear object and within said range of scale variations;

d) means for disposing said reduced size submodel within said enlarged submodel and tangent to said enlarged submodel;

e) means for computing a fill area between said enlarged submodel and said reduced size submodel;

f) means for generating a feathered submodel having varying pixel grey scale values between said enlarged and said reduced size submodels by creating a smoothly varying grey scale fill in said fill area;

g) means for conducting a correlation search of a digitized image of said object using said feathered submodel, whereby the point in said digitized image reported by said correlation search as having the highest correlation to said feathered submodel is deemed to be at an edge of said curvilinear object and used to compute a center of said curvilinear object to locate it.