Image segmentation using branch and bound analysis

• US 20050226493A1
• Filed: 03/31/2004
• Published: 10/13/2005
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Gat, Yoram, Haussecker, Horst W.
• Granted Patent: US 7,447,358 B2
• Time in Patent Office: Days
• US Class Current: 382/145
• CPC Class Codes: G06T 2207/10056 Microscopic image
• CPC Class Codes: G06T 2207/30141 Printed circuit board [PCB]
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/0006 using a design-rule based approach
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/162 involving graph-based methods

Abstract

According to an embodiment of the invention, a method and apparatus for image segmentation are described. An embodiment of a method comprises inserting a state comprising a set of image segmentations into a queue, the queue being ordered by priority, the set of image segmentations having a priority representing a bound for a quality of the segmentations; extracting the state in the queue having the highest priority; if the extracted state is a terminal state, halting and outputting the extracted state as a solution; if the extracted state is not a terminal state refining the extracted state into a plurality of sets of segmentations, each of the plurality of sets having a priority, inserting the plurality of sets of segmentations into the queue, and iteratively repeating the extraction of the state in the queue having the highest priority.

Claims

1. A method comprising:

inserting a state comprising a set of image segmentations into a queue, the queue being ordered by priority, the set of image segmentations having a priority representing a bound for a quality of the segmentations;

extracting the state in the queue having the highest priority;

if the extracted state is a terminal state, halting and outputting the extracted state as a solution;

if the extracted state is not a terminal state;

refining the extracted state into a plurality of sets of segmentations, each of the plurality of sets having a priority,

inserting the plurality of sets of segmentations into the queue, and

iteratively repeating the extraction of the state in the queue having the highest priority.

2. The method of claim 1, further comprising identifying a structure in the image based on the output.

3. The method of claim 2, wherein the image is an image of a portion of a microelectronic device.

4. The method of claim 3, wherein the structure comprises a wire structure in the microelectronic device.

5. The method of claim 1, wherein an extracted state is a terminal state if the set of segmentations for the state meets a precision standard.

6. The method of claim 1, wherein refining an extracted state comprises producing a set of segmentation sets that form a partition of the extracted state.

7. The method of claim 1, wherein the segmentations of the image are based on one or more geometric models.

8. The method of claim 7, wherein the one or more geometric models represent one or more expected structures in the image.

9. The method of claim 1, wherein the quality represents relative intensity of light on pixels of the image.

10. An imager comprising:

an image receptor to receive an image of a device under test, the image to include a structure in the device under test; and

an interface with a processor, the imager to provide data to the processor;

wherein the structure in the device under test is to be identified based on comparison of sets of image segmentations with one or more models of expected structures, the sets of image segmentations to be evaluated using a bound and branch analysis, each of the sets of image segmentations having a priority representing a bound on a quality of the image.

11. The image of claim 10, wherein the operation of the imager is directed automatically based on identification of the structure.

12. The imager of claim 10, wherein the structure comprises a nano-structure.

13. The imager of claim 10, wherein the device under test comprises a microelectronic device.

14. The imager of claim 13, wherein the structure comprises a wiring structure in the microelectronic device.

15. The imager of claim 14, wherein the one or more models comprise one or more geometric models of expected wiring structures.

16. The imager of claim 10, wherein the branch and bound technique comprises ordering sets of image segmentations according to priority and analyzing the set of image segmentations with the highest priority.

17. The imager of claim 16, wherein the quality comprises light intensity homogeneity for a set of segmentations.

18. An imaging system comprising:

an imaging device, the imaging device to receive an image; and

a processing system, the processing system to identify a structure in the image by evaluating sets of segmentations of the image in relation to models of expected structures, wherein evaluating comprises;

determining a priority for each of the plurality of sets of segmentations, wherein the priority for a set represents a bound for a quality of the segmentations in the set, and

analyzing the sets of segmentations according to priority order.

19. The imaging system of claim 18, wherein analyzing the sets of segmentations according to priority order comprises determining whether the set of segmentations with the highest priority is a terminal result.

20. The imaging system of claim 19, wherein a set of segmentations is a terminal result if the set meets a standard of precision.

21. The imaging system of claim 19, wherein analyzing the sets of segmentations further comprises refining the set of segmentations with the highest priority into a plurality of sets of segmentations if the set of segmentations is not a terminal result.

22. The imaging system of claim 18, wherein the imaging system comprises a focused ion beam tool.

23. The imaging system of claim 18, wherein the device under test is a microelectronic device.

24. The imaging system of claim 18, wherein the imaging system is utilized to analyze the microelectronic device

25. An article of manufacture comprising:

a machine accessible storage medium storing instructions that, when executed by a processing system, cause the processing system to perform operations comprising;

inserting a set of image segmentations into a queue, ordering the sets by priority, priority of a set of image segmentations representing a bound for a quality of the segmentations in the set;

evaluating the set of image segmentations having the highest priority;

if the set of image segmentations having the highest priority meets a termination standard, halting and outputting the extracted set as a solution;

if the set of image segmentations having the highest priority does not meet the termination standard;

refining the set of segmentations into a plurality of sets of segmentations, each of the plurality of sets having a priority;

inserting the plurality of sets of segmentations into the queue according to priority; and

repeating the process until a set of image segmentations having the highest priority meets the termination standard.

26. The article of manufacture of claim 25, further comprising instructions that, when executed by a processing system, cause the processing system to perform operations comprising identifying a structure in the image based on the solution.

27. The article of manufacture of claim 25, wherein refining a set of segmentations comprises producing a set of segmentation sets that form a partition of the refined set.

28. The article of manufacture of claim 25, wherein the segmentations of the image are based on one or more geometric models.

29. The article of manufacture of claim 28, wherein the one or more geometric models represent one or more expected structures in the image.

30. The article of manufacture of claim 25, further comprising instructions that, when executed by a processing system, cause the processing system to perform operations comprising evaluating the image based on intensity of light falling on pixels.