Highly constrained tomography for automated inspection of area arrays

• US 20050105682A1
• Filed: 11/15/2003
• Published: 05/19/2005
• Est. Priority Date: 11/15/2003
• Status: Active Grant

• Current Assignee: Agilent Technologies, Inc.
• Original Assignee: Agilent Technologies, Inc.
• Inventors: Tufillaro, Nicholas, Gines, David, Heumann, John M., Fox, Colin
• Granted Patent: US 7,099,435 B2
• Time in Patent Office: Days
• US Class Current: 378/58
• CPC Class Codes: G01N 2223/419 computed tomograph
• CPC Class Codes: G01N 23/046 using tomography, e.g. computed tomography [CT]

Abstract

A tomographic reconstruction method and system incorporating Bayesian estimation techniques to inspect and classify regions of imaged objects, especially objects of the type typically found in linear, areal, or 3-dimensional arrays. The method and system requires a highly constrained model M that incorporates prior information about the object or objects to be imaged, a set of prior probabilities P(M) of possible instances of the object; a forward map that calculates the probability density P(D|M), and a set of projections D of the object. Using Bayesian estimation, the posterior probability p(M|D) is calculated and an estimated model M_EST of the imaged object is generated. Classification of the imaged object into one of a plurality of classifications may be performed based on the estimated model M_EST, the posterior probability p(M|D) or MAP function, or calculated expectation values of features of interest of the object.

Claims

1. A method for automated industrial inspection of manufactured devices characterized by a repetitive array of similar objects, comprising:

obtaining a set of observed projections of one or more objects under inspection that are members of said repetitive array;

obtaining a highly constrained model of said objects under inspection based partially on or expressing some prior information about said objects under inspection;

obtaining a distribution or density expressing prior probabilities, P(M), for all possible instances of said objects under inspection representable by said highly constrained model;

obtaining a forward map capable of predicting the likelihood of observing specified projections that would result from any collection of objects representable by said highly constrained model;

estimating a model of said objects under inspection based on said set of observed projections, said highly constrained model, said distribution or density expressing prior probabilities, and said forward map.

2. The method of claim 1, further comprising:

classifying said objects under inspection based on said estimated model of said objects under inspection.

3. The method of claim 1, wherein said step for estimating said model further comprises:

finding a maximum a priori (MAP) estimate of said objects under inspection.

4. The method of claim 3, further comprising:

classifying said objects under inspection based on said MAP estimate.

5. The method of claim 1, wherein said step for estimating said model further comprises:

determining a posterior probability density or distribution of said objects under inspection.

6. The method of claim 5, wherein said step for determining said posterior probability density or distribution comprises:

utilizing Bayesian techniques to determine said posterior probability density or distribution given said set of observed projections.

7. The method of claim 5, further comprising:

classifying said objects under inspection based on said posterior probability density or distribution.

8. The method of claim 1, wherein said step for estimating said model further comprises:

calculating expectations of one or more features comprising said highly constrained model or functions thereof.

9. The method of claim 8, further comprising:

classifying said objects under inspection based on said expectations of said one or more features.

10. The method of claim 8, wherein said calculating step comprises:

implementing a Markov Chain Monte Carlo (MCMC) algorithm to visit model states with frequency proportional to their posterior probability and to approximate said expectations of said one or more features.

11. The method of claim 1, wherein said method for estimating said model comprises:

initializing a current model to an initial estimate;

computing a posterior of said current model to generate a current model posterior;

proposing changes to said current model to generate a next model;

computing a posterior of said next model to generate a next model posterior;

determining whether to accept or reject said next model based on values of said current model posterior and said next model posterior;

if said next model is to be accepted, updating said estimated model with said next model, and if said next model is to be rejected, discarding said proposed changes to said current model; and

repeating said proposing step through said updating or said discarding steps until sufficient accuracy is achieved or allotted time and/or iterations have expired.

12. A method in accordance with claim 11, wherein said step for determining whether to accept or reject said next model comprises:

utilizing a Metropolis-Hastings algorithm.

13. The method of claim 1, wherein:

said repetitive array of similar objects comprises an array of electrical connections in an electronic assembly.

14. The method of claim 13, wherein said array of electrical connections comprises an array of integrated circuit joints.

15. The method of claim 1, further comprising:

generating said observed projections using penetrating radiation.

16. The method of claim 15, wherein:

said penetrating radiation comprises X-rays.

17. The method of claim 1, wherein:

said step for estimating said model of said objects under inspection is performed in realtime.

18. A computer readable storage medium tangibly embodying program instructions implementing a method for automated industrial inspection of manufactured devices characterized by a repetitive array of similar objects, the method comprising the steps of:

obtaining a set of observed projections of one or more objects under inspection that are members of said repetitive array;

obtaining a highly constrained model of said objects under inspection based partially on or expressing some prior information about said objects under inspection;

obtaining a distribution or density expressing prior probabilities, P(M), for all possible instances of said objects under inspection representable by said highly constrained model;

obtaining a forward map capable of predicting the likelihood of observing specified projections that would result from any collection of objects representable by said highly constrained model;

estimating a model of said objects under inspection based on said set of observed projections, said highly constrained model, said distribution or density expressing prior probabilities, and said forward map.

19. The computer readable storage medium of claim 18, further comprising:

classifying said objects under inspection based on said estimated model of said objects under inspection.

20. The computer readable storage medium of claim 18, wherein said step for estimating said model further comprises:

finding a maximum a priori (MAP) estimate of said objects under inspection.

21. The computer readable storage medium of claim 20, further comprising:

classifying said objects under inspection based on said MAP estimate.

22. The computer readable storage medium of claim 18, wherein said step for estimating said model further comprises:

determining a posterior probability density or distribution of said objects under inspection.

23. The computer readable storage medium of claim 22, wherein said step for determining said posterior probability density or distribution comprises:

utilizing Bayesian techniques to determine said posterior probability density or distribution given said set of observed projections.

24. The computer readable storage medium of claim 22, further comprising:

classifying said objects under inspection based on said posterior probability density or distribution.

25. The computer readable storage medium of claim 18, wherein said step for estimating said model further comprises:

calculating expectations of one or more features comprising said highly constrained model or functions thereof.

26. The computer readable storage medium of claim 25, further comprising:

classifying said objects under inspection based on said expectations of said one or more features.

27. The computer readable storage medium of claim 25, wherein said calculating step comprises:

implementing a Markov Chain Monte Carlo (MCMC) algorithm to visit model states with frequency proportional to their posterior probability and to approximate said expectations of said one or more features.

28. The computer readable storage medium of claim 18, wherein said method for estimating said model comprises:

initializing a current model to an initial estimate;

computing a posterior of said current model to generate a current model posterior;

proposing changes to said current model to generate a next model;

computing a posterior of said next model to generate a next model posterior;

determining whether to accept or reject said next model based on values of said current model posterior and said next model posterior;

if said next model is to be accepted, updating said estimated model with said next model, and

if said next model is to be rejected, discarding said proposed changes to said current model; and

repeating said proposing step through said updating or said discarding steps until sufficient accuracy is achieved or allotted time and/or iterations have expired.

29. A computer readable storage medium in accordance with claim 28, wherein said step for determining whether to accept or reject said next model comprises:

utilizing a Metropolis-Hastings algorithm.

30. The computer readable storage medium of claim 18, wherein:

said repetitive array of similar objects comprises an array of electrical connections in an electronic assembly.

31. The computer readable storage medium of claim 30, wherein said array of electrical connections comprises an array of integrated circuit joints.

32. The computer readable storage medium of claim 18, wherein:

said step for estimating said model of said objects under inspection is performed in realtime.

33. An automated imaging inspection system for automated industrial inspection of manufactured devices characterized by a repetitive array of similar objects, said system comprising:

a reconstruction engine responsive to receiving a set of observed projections of one or more objects under inspection that are members of said repetitive array by estimating a model of said objects under inspection based on said set of observed projections, a highly constrained model of said objects under inspection based partially on or expressing some prior information about said objects under inspection, a prior probability distribution or density expressing prior probabilities for all possible instances of said object representable by said highly constrained model, and a forward map capable of predicting the likelihood of observing specified projections that would result from any collection of objects representable by said highly constrained model.

34. The system of claim 33, further comprising:

a classification function which classifies said objects under inspection based on said estimated model of said objects under inspection.

35. The system of claim 33, wherein said reconstruction engine comprises:

a maximum a posteriori (MAP) algorithm which operates to find a maximum a priori (MAP) estimate of said objects under inspection.

36. The system for claims 35, further comprising:

a classification function which classifies said objects under inspection based on said MAP estimate.

37. The system of claim 33, wherein said reconstruction engine comprises:

an algorithm which determines a posterior probability density or distribution of said objects under inspection.

38. The system for claims 37, wherein:

said algorithm which determines said posterior probability density or distribution of said objects under inspection comprises;

a Bayesian estimation algorithm which determines said posterior probability density or distribution given said set of observed projections.

39. The system of claim 37, further comprising:

a classification function which classifies said objects under inspection based on said posterior probability density or distribution.

40. The system of claim 33, wherein said reconstruction engine comprises:

an algorithm which calculates expectations of one or more features comprising said highly constrained model or functions thereof.

41. The system of claim 40, further comprising:

a classification function which classifies said objects under inspection based on said expectations of said one or more features.

42. The system of claim 40, wherein said algorithm which calculates expectations comprises:

a Markov Chain Monte Carlo (MCMC) algorithm which visits model states with frequency proportional to their posterior probability and to approximate said expectations of said one or more features.

43. The system of claim 33, wherein:

said repetitive array of similar objects comprises an array of electrical connections in an electronic assembly and said object comprises a single electrical connection that is a member of said array of electrical connections.

44. The system of claim 43, wherein said array of electrical connections comprises an array of integrated circuit joints.

45. The system of claim 33, further comprising wherein:

said repetitive array of similar objects comprises an array of electrical connections in an electronic assembly and said object comprises two or more electrical connections that are members of said array of electrical connections.

46. The system of claim 45, wherein said array of electrical connections comprises an array of integrated circuit joints.

47. The system of claim 33, further comprising:

a projection collector which collects said set of observed projections of said objects under inspection.

48. The system of claim 47, wherein:

said projection collector generates said observed projections using penetrating radiation.

49. The system of claim 48, wherein:

said penetrating radiation comprises X-rays.

50. The system of claim 33, wherein:

said reconstruction engine estimates said model of said objects under inspection in realtime.

51. An automated imaging inspection system for automated industrial inspection of electrical connections arranged in a repetitive array in an electronic assembly, said system comprising:

a reconstruction engine which receives a set of observed projections of one or more electrical connections under inspection in a repetitive array of an electronic assembly under inspection, said reconstruction engine comprising;

a reconstruction algorithm which receives said set of observed projections and estimates one or more of;

a maximum a priori (MAP) estimate of said one or more electrical connections under inspection;

a posterior probability density or distribution of said one or more electrical connections under inspection;

one or more expectations of one or more features comprising said highly constrained model or functions thereof;

wherein said reconstruction algorithm utilizes;

a highly constrained model of said one or more electrical connections under inspection based partially on or expressing some prior information about said one or more electrical connections;

a prior probability distribution or density expressing prior probabilities for all possible instances of said one or more electrical connections under inspection representable by said highly constrained model; and

a forward map capable of predicting the likelihood of observing said set of observed projections that would result from any collection of said one or more electrical connections representable by said highly constrained model.

52. The system of claim 51, further comprising:

a classification function which classifies said one or more electrical connections under inspection based on said MAP estimate.

53. The system of claim 51, further comprising:

a classification function which classifies said one or more electrical connections under inspection based on said posterior probability density or distribution.

54. The system of claim 51, further comprising:

a classification function which classifies said one or more electrical connections under inspection based on said expectations of said one or more features.

55. The system of claim 51, further comprising:

a projection collector which collects said set of observed projections of said one or more electrical connections under inspection.

56. The system of claim 55, wherein:

said projection collector generates said observed projections using penetrating radiation.

57. The system of claim 56, wherein:

said penetrating radiation comprises X-rays.

58. The system of claim 51, wherein:

said reconstruction engine estimates said model of said one or more electrical connections under inspection in realtime.