Methods and apparatuses for identifying regions of similar texture in an image

• US 6,647,132 B1
• Filed: 12/09/1999
• Issued: 11/11/2003
• Est. Priority Date: 08/06/1999
• Status: Expired due to Term

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Inventors: Montillo, Albert A., Bachelder, Ivan A.
• Primary Examiner(s): Werner, Brian
• Assistant Examiner(s): Miller, Ryan J.
• Application Number:
  US09/457,825
• Time in Patent Office: 1,433 Days
• Field of Search: 382/108, 382/146, 382/111, 382/204, 382/205, 382/176, 382/191, 382/280, 345/582, 348/128
• US Class Current: 382/108
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/20056 Discrete and fast Fourier transform, [DFT, FFT]
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/168 involving transform domain methods
• CPC Class Codes: G06T 7/42 using transform domain methods

Abstract

Methods and apparatuses are disclosed for identifying regions of similar texture in an image. The areas of similar texture include areas conventionally thought of as similar texture regions as well as areas of more varied texture that are treated as regions of similar texture in order to identify them within an image. The method associates frequency characteristics of an image with a spatial position within the image by: applying a frequency analysis on sub-regions of the image, thereby, generating frequency characteristics representative of the sub-regions: and associating the frequency characteristics with the origin of the sub-regions. An embodiment disclosed applies a fast Fourier transform on sub-regions in a given direction to determine a dominant frequency of the sub-region and the power of the dominant frequency, both of which are associated with the respective sub-region by storing the dominant frequency and power in a frequency image and power image, respectively, at the position of the origin. Thereafter, the frequency image and the power image are segmented to generate binary images containing regions having similar frequencies and powers, respectively. The binary images are then logically anded together to further refine the regions possessing similar frequency, and thereby finding regions having similar texture in an image.

Claims

1. A method for identifying regions of similar texture in at least one input image, the method comprising:

acquiring image data representing the at least one input image;

dividing at least a portion of the image data into sub-regions, each of the sub-regions having an origin, and a length;

applying a one dimensional spatial frequency analysis along the length of each of the sub-regions so as to produce a frequency characteristic for each of the sub-regions and associating the frequency characteristic of each sub-region with its origin; and

examining the frequency characteristic of each of the sub-regions to identify similar sub-regions, thereby identifying regions of similar texture in the input image, wherein the frequency characteristic is the frequency spectrum of each sub-region along the length.

2. The method of claim 1, wherein the regions of similar texture are regions of homogeneous texture.

3. The method of claim 1, wherein the image data is an input image.

4. The method of claim 1, wherein the sub-regions overlap.

5. The method of claim 1, wherein the origins of the sub-regions are at regular intervals along at least a single dimension within the at least one input image.

6. The method of claim 1, where the origins of the sub-regions correspond with every pixel location in the at least one input image.

7. The method of claim 1, wherein each of the sub-regions is the same size.

8. The method of claim 1, wherein the determining a frequency characteristic further includes:

performing a one-dimensional Fourier analysis along the length of each of the sub-regions so as to determine the frequency characteristic of each of the sub-regions.

9. The method of claim 1, wherein the examining the frequency characteristic of each of the sub-regions further includes:

comparing the frequency characteristic of neighboring sub-regions so as to identify the similar sub-regions.

10. The method of claim 9, wherein the comparing further includes:

comparing the frequency characteristic of the neighboring sub-regions using a similarity metric so as to determine the similar sub-regions.

11. The method of claim 9, wherein the neighboring sub-regions are adjacent sub-regions.

12. The method of claim 1, wherein the examining the frequency characteristic further includes:

representing the frequency characteristic of each of the sub-regions as a value on a frequency-characteristic image at the respective origin of each of the sub-regions;

segmenting the similar sub-regions within the frequency-characteristic image using the values of the sub-regions.

13. The method of claim 12, wherein the segmenting further includes:

thresholding the values within the frequency-characteristic image to form binary images, each of the binary images containing only a background and at least one region of similar texture.

14. The method of claim 12, wherein representing the frequency characteristic further includes:

representing the frequency characteristic of each of the sub-regions as a grey-scale value on the frequency-characteristic image at the respective origin of each of the sub-regions; and

wherein the segmenting further includes;

segmenting the similar sub-regions within the frequency-characteristic image using the grey-scale values of the sub-regions.

15. The method of claim 1, wherein the examining the frequency characteristic of each of the sub-regions further includes:

representing a plurality of the frequency characteristics of each of the sub-regions as respective values on a plurality of frequency-characteristic images at the respective origin of each of the sub-regions;

segmenting the similar sub-regions within the plurality of frequency-characteristic images using the values, thereby identifying the similar sub-regions in each of the respective frequency characteristic images.

16. The method of claim 1, wherein determining the frequency characteristic includes,

performing a one-dimensional spatial frequency analysis in substantially one orientation to determine at least a portion of a frequency spectrum of each of the sub-regions, the at least a portion of the frequency spectrum of each of the sub-regions providing the frequency characteristic of each of the sub-regions, and

wherein examining the frequency characteristic includes,

examining the at least a portion of the frequency spectrum of each of the sub-regions to identify the similar sub-regions.

17. The method of claim 16, wherein examining the at least a portion of the frequency spectrum includes,

examining a mid-range of the frequency spectrum of each of the sub-regions.

18. The method of claim 16, wherein examining the at least a portion of the frequency spectrum includes,

examining a standard deviation of the at least a portion of the frequency spectrum of each of the sub-regions to identify the similar sub-regions.

19. The method of claim 16, wherein the at least a portion of the frequency spectrum include terms derived from a transform analysis.

20. An apparatus for identifying regions of similar texture in at least one input image, the at least one input image having sub-regions, each of the sub-regions having an origin, and a length, the apparatus comprising:

frequency-characteristic means, adapted to apply a one dimensional spatial frequency analysis to determine a frequency characteristic, along the length of each of the sub-regions and associating the frequency characteristic of each sub-region with its origin; and

examination means, in communication with the frequency-characteristic means, adapted to identify similar sub-regions using the frequency characteristic of each of the sub-regions, wherein the frequency characteristic is the frequency spectrum of each sub-region along the length.

21. The apparatus of claim 20, wherein the similar sub-regions are sub-regions of portions of leads of a leaded device.

22. The apparatus of claim 20, wherein the similar sub-regions are sub-regions of portions of balls of a ball grid array device.

23. The apparatus of claim 20, wherein the frequency characteristic means further includes:

analysis means adapted to performing a one-dimensional spatial frequency analysis in substantially one orientation on each of the sub-regions so as to determine the frequency characteristic of each of the sub-regions.

24. The apparatus of claim 23, wherein the frequency characteristic is at least a portion of a frequency spectrum of each of the sub-regions, and wherein the examining means is further adapted to examine the at least a portion of the frequency spectrum of each of the sub-regions to identify the similar sub-regions.

25. The apparatus of claim 24, wherein the at least a portion of the frequency spectrum is a mid-range of the frequency spectrum of each of the sub-regions.

26. The apparatus of claim 24, wherein the examining means is further adapted to examine a standard deviation of the at least a portion of the frequency spectrum of each of the sub-regions to identify the similar sub-regions.

27. The apparatus of claim 24, wherein the at least a portion of the frequency spectrum include terms derived from a transform analysis.

28. The apparatus of claim 20, wherein the examination means further includes:

comparison means, in communication with the frequency means, adapted to compare the frequency characteristic of each of the sub-regions so as to identify the similar sub-regions.

29. The apparatus of claim 20, further comprising:

frequency-characteristic images, in communication with the frequency-characteristic means, adapted to receive a value of the frequency characteristic of each of the sub-regions at the respective origin position of each of the sub-regions; and

wherein the examination means further includes;

segmenting means, adapted to segment the similar sub-regions within the frequency-characteristic images using the values of the sub-regions.

30. A method for identifying regions of similar texture in at least one input image of a surface-mount device, the method comprising:

acquiring image data representing the at least one input image of the surface-mount device;

dividing at least a portion of the image data into sub-regions, each of the sub-regions having an origin, and a length;

determining a frequency characteristic by applying a one-dimensional spatial frequency analysis along the length of each of the sub-regions and associating the frequency characteristic of each sub-region with its origin; and

identifying a sub-set of the sub-regions having similar frequency characteristics, thereby identifying regions of similar texture in the at least one input image, the regions containing at least portions of features of the surface-mount device, wherein the frequency characteristic is the frequency spectrum of each sub-region along the length.

31. The method of claim 30, wherein the determining the frequency characteristics further includes:

performing a one-dimensional spatial frequency analysis in substantially one orientation on each of the sub-regions to determine the frequency characteristic of each of the sub-regions.

32. The method of claim 30, wherein the identifying the sub-set of the sub-regions having similar frequency characteristics further includes:

identifying neighboring sub-regions having similar frequency characteristics.

33. The method of claim 30, wherein the identifying the sub-set of the sub-regions further includes:

representing a plurality of the frequency characteristics of each of the sub-regions as respective values on a plurality of frequency-characteristic images at the respective origin of each of the sub-regions; and

segmenting the sub-set of the sub-regions having similar frequency characteristics within each of the plurality of frequency-characteristic images using the values.

34. The method of claim 30, wherein determining the frequency characteristic includes,

performing a one-dimensional spatial frequency analysis in substantially one orientation to determine at least a portion of a frequency spectrum of each of the sub-regions, the at least a portion of the frequency spectrum of each of the sub-regions providing the frequency characteristic of each of the sub-regions, and

wherein identifying the subset of the sub-regions includes,

identifying the subset of the sub-regions having similar portions of the respective frequency spectrums.

35. The method of claim 34, wherein identifying the sub-set of the sub-regions includes,

examining a mid-range of the frequency spectrum of each of the sub-regions.

36. The method of claim 34, wherein identifying the subset of the sub-regions includes,

examining a standard deviation of the at least a portion of the frequency spectrum of each of the sub-regions to identify the subset of the sub-regions having similar frequency spectrums.

37. The method of claim 34, wherein the at least a portion of the frequency spectrum include terms derived from a transform analysis.

38. A method for identifying regions of similar texture in at least one input image, the method comprising:

acquiring image data representing the at least one input image;

dividing at least a portion of the image data into sub-regions, each of the sub-regions having an origin;

applying a Fourier analysis, in substantially one orientation, of each of the sub-regions so as to produce a frequency characteristic for each of the sub-regions;

examining the frequency characteristic of each of the sub-regions to identify similar sub-regions thereby identifying regions of similar texture in the input image;

individually optimizing the size of each sub-region to ensure that a substantially homogenous texture is contained therein, based on the frequency characteristic of the given sub-region; and

repeating the steps of applying and examining.