Image segmentation using branch and bound analysis

• US 7,447,358 B2
• Filed: 03/31/2004
• Issued: 11/04/2008
• Est. Priority Date: 03/31/2004
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Gat, Yoram, Haussecker, Horst W.
• Primary Examiner(s): Hung; Yubin
• Application Number:
  US10/815,896
• Publication Number:
  US 20050226493A1
• Time in Patent Office: 1,679 Days
• Field of Search: 382145-147, 382/164, 382/171, 382173-180, 382/209, 382/321, 382/324, 358/462, 358/453, 358/538, 348/207.1, 348/207.11
• US Class Current: 382/173
• 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 computer-implemented method comprising:

inserting a state into a queue, wherein a state comprises a set of image segmentations and has a priority representing a bound for a quality of each of its image segmentations, and wherein states in the queue are ordered by their respective priority;

iteratively repeating the following;

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 states;

determining the priority of each of the plurality of states; and

inserting the plurality of states into the queue.

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

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 imaging system comprising:

an imaging device, the imaging device to receive an image of a device under test; and

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

inserting a state into a queue, wherein a state comprises a set of image segmentations and has a priority representing a bound for a quality of each of its image segmentations, and wherein states in the queue are ordered by their respective priority;

iteratively repeating the following;

extracting the state in the queue having the highest priority;

if the extracted state meets a standard of precision;

halting and outputting the extracted state as a solution;

if the extracted state does not meet the standard of precision;

refining the extracted state into a plurality of states;

determining the priority of each of the plurality of states; and

inserting the plurality of states into the queue.

11. The imaging system of claim 10, wherein the operation of the imaging device is directed automatically based on identification of the structure.

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

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

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

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

16. The imaging system of claim 13, wherein the imaging system is utilized to analyze the microelectronic device.

17. The imaging system of claim 10, wherein the quality for a segmentation comprises light intensity homogeneity for the segmentation.

18. The imaging system of claim 10, further comprising a focused ion beam tool.

19. An article of manufacture comprising:

a machine-readable storage medium storing computer-executable instructions that, when executed by a computer, cause the computer to perform operations comprising;

inserting a state into a queue, wherein a state comprises a set of image segmentations and has a priority representing a bound for a quality of each of its image segmentations, and wherein states in the queue are ordered by their respective priority;

iteratively repeating the following;

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 states;

determining the priority of each of the plurality of states; and

inserting the plurality of states into the queue.

20. The article of manufacture of claim 19, further comprising computer-executable instructions that, when executed by the computer, cause the computer to perform operations comprising identifying a structure in the image based on the solution.

21. The article of manufacture of claim 19, wherein refining an extracted state comprises producing a set of states that form a partition of the extracted state.

22. The article of manufacture of claim 19, wherein the image segmentations in a state are based on one or more geometric models.

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

24. The article of manufacture of claim 19, further comprising computer-executable instructions that, when executed by the computer, cause the computer to perform operations comprising evaluating the quality of a segmentation of the image based on intensity of light falling on pixels of the image.