Methods, apparatus and computer program products for automated visual inspection

• US 6,023,680 A
• Filed: 05/15/1997
• Issued: 02/08/2000
• Est. Priority Date: 05/15/1997
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Corporation Of America (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Technologies, Inc. (Panasonic Holdings Corporation)
• Inventors: Deo, Shantanu, Wooster, Andrew
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): KALINOWSKI, ALEXANDER G
• Application Number:
  US08/857,199
• Time in Patent Office: 999 Days
• Field of Search: 705/7, 705/8, 382/141, 382/145, 382/147, 382/148, 382/149, 382/150, 348/126
• US Class Current: 705/7.26
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/06398 Performance of employee with respect to a job function
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/0004 Industrial image inspection

Abstract

Methods, apparatus and computer program products for automated visual inspection of regions of interest of a product utilizing an automated visual inspection device having a constrained viewing area are provided according to the present invention. Particularly, inspection of regions of interest on a product utilizing a constrained viewing area characterized as a view minimization problem is minimized by translating the view minimization problem into a set-covering problem and a traveling salesman problem. Known heuristics are applied to the set-covering problem and the traveling salesman problem to minimize the number of views required to view the regions of interest and to minimize the distance of travel between the views. Apparatus and computer programs products are also provided which minimize inspection time in a like manner.

Claims

1. A method of automated visual inspection of regions of interest of a product utilizing an automated visual inspection device including a viewing device having a viewing area for acquiring images of regions of interest of a product being inspected, wherein said viewing area is constrained in size and has a predetermined geometric shape, and wherein said method comprises the steps of:

selecting a plurality of views for viewing the regions of interest in the constrained viewing area, wherein said selecting step comprises;

generating an initial set of views wherein every region of interest is included in at least one view based on the constraints of the viewing area and the predetermined geometric shape of the viewing area and wherein the regions of interest are capable of being included in more than one view of the initial set of views; and

performing a set-covering on the initial set of views from said generating step to select a plurality of views; and

performing relaxed traveling salesman problem on the selected plurality of views to select the path of movement between the selected plurality of views.

2. A method of automated visual inspection as defined in claim 1, further comprising the step of:

moving the constrained viewing area of the viewing device relative to the regions of interest based upon the selected path of movement.

3. A method of automated visual inspection as defined in claim 1, wherein said performing a set-covering step involves applying a heuristic to the set-covering and said performing relaxed traveling salesman problem step involves applying a heuristic to the relaxed traveling salesman problem such that said performing a set-covering step and said performing relaxed traveling salesman problem step minimize the time required to inspect the regions of interest by selecting a minimized number of views |V| for viewing the regions of interest in the constrained viewing area and a minimized distance of movement between the selected number of views according to Formula (I):

space="preserve" listing-type="equation">a*|V|+Ε

.sup.i<

|V| c(V.sub.i+1, V.sub.i) (I)

where a is the time required to process a single view, and where c(V_i+1, V_i) is the cost of moving from the i^th view v_i to the next (i+1)^th view v_i+1 in the sequence that is obtained from the solution of the traveling salesman problem.

4. A method of automated visual inspection as defined in claim 3, wherein said performing relaxed traveling salesman problem step further comprises requiring the constrained viewing area to visit every city v in a tour but not requiring the viewing area to return to the city v of origination to form a tour and utilizing a city v_o having a cost equal to zero to alternating views of the viewing area such that c(v_o, v_i)=0 for all v_iε

V and requiring the city v_o to be the city of origination in applying at least one said heuristic to solving said traveling salesman problem.

5. A method of automated visual inspection as defined in claim 3, wherein the following step is performed prior to the selecting step:

accepting input of a solution criteria including at least one of a level of time and aggressiveness for controlling both said performing a set-covering step and said performing relaxed traveling salesman problem step based on said solution criteria such that both of the performing steps perform according to the accepted input of solution criteria.

6. A method of automated visual inspection as defined in claim 1, wherein said performing a set-covering step further comprises applying a heuristic to the set-covering to select a minimized number of views for viewing the regions of interest in the constrained viewing area;

and

wherein said performing relaxed traveling salesman problem step further comprises applying a heuristic to the relaxed traveling salesman problem to select a minimized distance of movement between the views selected by said performing a set-covering step.

7. A method of automated visual inspection of a product as defined in claim 1 wherein said performing a set-covering step further comprises applying a heuristic to the set-covering to produce a set of views |V| which cover all of the regions of interest and wherein said second performing relaxed traveling salesman problem step further comprises applying a heuristic to minimize the distance of movement between the views |V|.

8. A method of automated visual inspection as defined in claim 7, wherein said performing a set-covering step further comprises performing an instance (X,F) of the set covering problem according to Formula II:

space="preserve" listing-type="equation">Let X=O II.

wherein O=the regions of interest;

Let F={i;

iε

O and i≠

j

i_x -j_x +j_w and

i_y -j_y +j_h and

i_x ≦

j_x and

i_y ≦

j_y }.

9. A method of automated visual inspection as defined in claim 7, wherein said generating an initial set of views step comprises generating an initial set of Views |V| from the set O of regions of interest according to Formula III:

space="preserve" listing-type="tabular">______________________________________ III. V = .O slashed. Sort O by x For each i ε

O NEAREST = .O slashed. For each j ε

O If (j.sub.x -i.sub.x <

=w) AND (i.sub.y -j.sub.y <

=h) NEAREST = NEAREST ∪

{j};

For each j ε

NEAREST If(i.sub.y <

= j.sub.y) SUBSET = .O slashed. For each K ε

NEAREST If (k.sub.x >

=i.sub.x) AND (k.sub.y >

=j.sub.y) AND (k.sub.x +k.sub.w -i.sub.x <

w) AND (k.sub.y +k.sub.h -j.sub.y <

=h) SUBSET = SUBSET ∪

{k} V = V .O slashed. {SUBSET} Return V. ______________________________________

10. An apparatus for automated visual inspection of regions of interest of a product comprising:

a viewing device having an image acquiring mechanism including an image acquiring viewing area configured to view regions of interest of a product, wherein said image acquiring viewing area of said image acquiring mechanism has a constrained size and a predetermined geometric shape;

means for moving said constrained viewing area of the viewing device relative to the regions of interest;

means for generating an initial set of views wherein every region of interest is included in at least one view based on the constraints of the viewing area and the predetermined geometric shape of the viewing area, and wherein the regions of interest are capable of being included in more than one view of the initial set of views;

means for performing a set-covering on the initial set of views to select a number of views for viewing the regions of interest in the constrained viewing area; and

means for performing a relaxed traveling salesman problem on the selected number of views to select a path of movement between the selected number of views; and

wherein the moving means is responsive to the relaxed traveling salesman problem to move along the selected path of movement.

11. An apparatus for automated visual inspection as defined in claim 10, wherein said set-covering performing means further comprises means for applying a heuristic to the set-covering and said relaxed traveling salesman problem performing means further comprises means for applying a heuristic to the relaxed traveling salesman problem, such that said set-covering performing means and said relaxed traveling salesman problem performing means minimize the time required to inspect the regions of interest by selecting a minimized number of views and a minimized distance of movement between the selected number of views according to Formula (I):

space="preserve" listing-type="equation">a*|V|+Ε

.sup.i<

|V| c(V.sub.i+1, V.sub.i) (I)

where a is the time required to process a single view, and where c(V_i+1, V_i) is the cost of moving from the i^th view v_i to the next (i+1)^th view v_i+1 in the sequence that is obtained from the solution of the traveling salesman problem.

12. An apparatus for automated visual inspection as defined in claim 11, wherein said relaxed traveling salesman problem performing means further comprises means for utilizing a city v_o having a cost equal to zero with alternating views such that c(v_o, v_i)=0 for all v_iε

V and requiring the city v_o to be the city of origination in said applying a heuristic means to said traveling salesman problem.

13. An apparatus for automated visual inspection of regions of interest as defined in claim 11, further comprising solution criteria selection means for selecting solution criteria of at least one of a level of time and aggressiveness for controlling both said set-covering performing means and said relaxed traveling salesman problem performing means based on said solution criteria such that said set-covering performing means and said relaxed traveling salesman problem performing means perform according to the selected solution criteria.

14. An apparatus for automated visual inspection as defined in claim 10, wherein said set-covering performing means further comprises means for applying a heuristic to the set-covering to select a minimum number of views for viewing the regions of interest in the constrained viewing area;

and

wherein said relaxed traveling salesman problem performing means further comprises means for applying a heuristic to the relaxed traveling salesman problem to select a minimum distance of movement between the views selected by said set-covering performing means.

15. An apparatus for automated visual inspection as defined in claim 10, wherein said set-covering performing means further comprises means to produce a set of views |V| which cover all of the regions of interest and wherein said traveling salesman problem performing means further comprises means to minimize the distance to move between the views V.

16. An apparatus for automated visual inspection as defined in claim 15, wherein said set-covering performing means further comprises means for reducing to an instance (X,F) of the set covering according to Formula II:

space="preserve" listing-type="equation">Let X=O II.

wherein O=the regions of interest;

Let F={i;

i, jε

O and i≠

j

i_x -j_x +j_w <

w and

i_y -j_y +j_h <

h and

i_x ≦

j_x and

i_y ≦

j_y }.

17. An apparatus for automated visual inspection as defined in claim 10 wherein said means for generating an initial set of views which cover all regions of interest further comprises means for generating an initial set of views |V| for set O of the regions of interest according to Formula III:

space="preserve" listing-type="tabular">______________________________________ III. V = .O slashed. Sort O by x For each i ε

O NEAREST = .O slashed. For each j ε

O If (j.sub.x -i.sub.x <

=w) AND (i.sub.y -j.sub.y <

=h) NEAREST = NEAREST ∪

{j};

For each j ε

NEAREST If(i.sub.y <

= j.sub.y) SUBSET = .O slashed. For each K ε

NEAREST If (k.sub.x >

=i.sub.x) AND (k.sub.y >

=j.sub.y) AND (k.sub.x +k.sub.w -i.sub.x <

w) AND (k.sub.y +k.sub.h -j.sub.y <

=h) SUBSET = SUBSET ∪

{k} V = V .O slashed. {SUBSET} Return V. ______________________________________

18. A computer program product for controlling automated visual inspection of regions of interest of a product utilizing an automated visual inspection device including a viewing device for acquiring images of regions of interest being inspected, wherein said viewing device has a viewing area that is constrained in size and has a predetermined geometric shape, and wherein the computer program product comprises:

a computer readable storage medium having computer readable program code means embodied in said medium, said computer-readable program code means comprising;

computer-readable program code means for generating an initial set of views wherein every region of interest is included in at least one view based on the constraints of the viewing area and the predetermined geometric shape of the viewing area, and wherein the regions of interest are capable of being included in more than one view of the initial set of views;

computer-readable program code means for performing a set-covering on the initial set of views to select a number of views for viewing the regions of interest in the constrained viewing area; and

computer-readable program code means for performing a relaxed traveling salesman problem on the selected number of views to select a path of movement between the selected number of views.

19. A computer program product as defined in claim 18, wherein said computer-readable program code means further comprises:

computer-readable program code means for generating a path of movement corresponding to an ordered list of coordinates generated from said set-covering computer-readable program code means and said traveling salesman performing computer-readable program code means; and

computer-readable program code means for controlling movement of the constrained viewing area of the viewing device relative to the regions of interest according to the selected path of movement.

20. A computer program product as defined in claim 18, wherein said set-covering performing computer-readable program code means further comprises computer-readable program code means for applying a heuristic to the set-covering;

and

wherein said traveling salesman problem performing computer-readable program code means further comprises computer-readable program code means for applying a heuristic to the relaxed traveling salesman problem;

such that said set-covering and said traveling salesman problem performing computer-readable program code means minimize the time required to inspect the regions of interest by selecting a minimized distance of movement between the selected number of views according to Formula (I);

space="preserve" listing-type="equation">a*|V|+Ε

.sup.i<

|V| c(V.sub.i+1, V.sub.i) (I)

where a is the time required to process a single view, and where c(V_i+1, V_j) is the cost of moving from the i^th view v_i to the next (i+1)^th view v_i+1 in the sequence that is obtained from the solution of the traveling salesman problem.

21. A computer program product as defined in claim 20, wherein said relaxed traveling salesman problem performing computer-readable program code means further comprises computer-readable program code means for utilizing a city v_o having a cost equal to zero with alternating views such that c(v_o, v_i)=0 for all v_i ε

V and requiring the city v_o to be the city of origination in applying said a least one heuristic to said traveling salesman problem.

22. A computer program product as defined in claim 20, wherein said computer readable program code means further comprises:

computer readable program code means for accepting input of solution criteria including at least one of a level of time and aggressiveness for controlling the heuristic applying means.

23. A computer program product as defined in claim 18, wherein said set-covering performing computer-readable program code means further comprises computer-readable program code means for applying a heuristic to the set-covering to select a minimum number of views for viewing the regions of interest in the constrained viewing area;

and

wherein said relaxed traveling salesman problem performing computer-readable program code means further comprising computer-readable program code means for applying at least a one heuristic to the relaxed traveling salesman problem on the selected views to select the minimum distance of the path of movement between the views selected by the set-covering performing computer-readable program code means.

24. A computer program product as defined in claim 23, wherein said computer readable program code means for performing a set-covering further comprises computer readable program code means for performing an instance (X,F) of the set covering according to Formula II:

space="preserve" listing-type="equation">Let X=O II.

wherein O=the regions of interest;

Let F={i;

i, jε

O and i≠

j

i_x -j_x +j_w <

w and

i_y -j_y +j_h <

h and

i_x ≦

j_x and

i_y ≦

j_y }.

25. A computer program product as defined in claim 18, wherein said computer-readable program code means for generating an initial set of views comprises means for generating an initial set of views |V| for the set O of the regions of interest according to Formula III:

space="preserve" listing-type="tabular">______________________________________ III. V = .O slashed. Sort O by x For each i ε

O NEAREST = .O slashed. For each j ε

O If (j.sub.x -i.sub.x <

=w) AND (i.sub.y -j.sub.y <

=h) NEAREST = NEAREST ∪

{j};

For each j ε

NEAREST If(i.sub.y <

= j.sub.y) SUBSET = .O slashed. For each K ε

NEAREST If (k.sub.x >

=i.sub.x) AND (k.sub.y >

=j.sub.y) AND (k.sub.x +k.sub.w -i.sub.x <

w) AND (k.sub.y +k.sub.h -j.sub.y <

=h) SUBSET = SUBSET ∪

{k} V = V .O slashed. {SUBSET} Return V. ______________________________________