System and method for scanning a region using a low discrepancy sequence

• US 6,959,104 B2
• Filed: 06/08/2001
• Issued: 10/25/2005
• Est. Priority Date: 02/05/2001
• Status: Expired due to Term

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Nair, Dinesh, Wenzel, Lothar, Rajagopal, Ram
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/876,983
• Publication Number:
  US 20020146152A1
• Time in Patent Office: 1,600 Days
• Field of Search: 382/106, 382/107, 382/141, 382/151, 382/153, 382/154, 382/169, 382/184, 382/193, 382/199, 382/201, 382/203, 382/209, 382/274, 382/285, 382/287, 382/291, 382/294, 382/305, 382/316, 382/103, 382/144, 382/145, 382/152, 382/147, 382/212, 734/88, 734/89, 348/154, 348/169, 356/27, 356/29, 356/237.1, 356/237.4, 708/250, 345/426, 705/36, 705/38
• US Class Current: 382/107
• CPC Class Codes: G05B 19/41815 characterised by the cooperation between machine tools, manipulators and conveyor or other workpiece supply system, workcell
• CPC Class Codes: G05B 2219/32212 If parameter out of tolerance reject product
• CPC Class Codes: G05B 2219/40554 Object recognition to track object on conveyor
• CPC Class Codes: G06T 7/0004 Industrial image inspection
• CPC Class Codes: G06V 10/10 Image acquisition document image scanning and transmission H04N1/00; control of digital cameras H04N23/60
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 10/421 by analysing segments intersecting the pattern
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

A system and method for scanning for an object within a region using a Low Discrepancy Sequence scanning scheme. The system may comprise a computer which includes a CPU and a memory medium which is operable to store one or more programs executable by the CPU to perform the method. The method may: 1) calculate a Low Discrepancy Sequence of points in the region; 2) generate a motion control trajectory from the Low Discrepancy Sequence of points (e.g., by generating a Traveling Salesman Path (TSP) from the Low Discrepancy Sequence of points and then re-sampling the TSP to produce a sequence of motion control points comprising the motion control trajectory); 3) scan the region along the motion control trajectory to determine one or more characteristics of the object in response to the scan. The method may also generate output indicating the one or more characteristics of the object.

Claims

1. A method for scanning for an object within a region, comprising:

generating a motion control trajectory, by;

calculating a Low Discrepancy Sequence of points in the region; and

generating the motion control trajectory from the Low Discrepancy Sequence of points, by;

generating a Traveling Salesman Path (TSP) from the Low Discrepancy Sequence of points, wherein the TSP includes each point of the Low Discrepancy Sequence of points; and

re-sampling the TSP to produce a sequence of motion control points comprising the motion control trajectory;

scanning the region along the motion control trajectory, and measuring the region at a plurality of points along the motion control trajectory;

determining one or more characteristics of the object in response to said scanning; and

generating output indicating the one or more characteristics of the object.

2. The method of claim 1, wherein said generating a Traveling Salesman Path comprises applying Lin'"'"'s Nearest Neighbor algorithm to the Low Discrepancy Sequence of points to generate the Traveling Salesman Path.

3. The method of claim 1,

wherein the TSP comprises a first sequence of points, wherein the first sequence of points defines a first trajectory having a first maximum curvature;

wherein said re-sampling the TSP comprises manipulating the first sequence of points to produce the sequence of motion control points;

wherein the sequence of motion control points defines a second trajectory having a second maximum curvature which is less than the first maximum curvature.

4. The method of claim 3,

wherein the sequence of motion control points is a superset of the first sequence of points.

5. The method of claim 3,

wherein the sequence of motion control points comprises a subset of the first sequence of points and one or more additional points.

6. The method of claim 1, wherein said calculating the Low Discrepancy Sequence of points in the region comprises determining a plurality of points, wherein any location in the region is within a specified distance of at least one of the Low Discrepancy Sequence of points.

7. The method of claim 1, wherein the region has a dimensionality of one of one or two.

8. The method of claim 1, wherein the region has a dimensionality greater than two.

9. A system for scanning for an object within a region, comprising:

a sensor; and

a computer which is operable to couple to said sensor, said computer comprising;

a CPU; and

a memory medium which is operable to store a scanning program;

wherein said CPU is operable to execute said scanning program to perform;

generating a motion control trajectory, by;

calculating a Low Discrepancy Sequence of points in the region; and

generating the motion control trajectory from the Low Discrepancy Sequence of points, by;

generating a Traveling Salesman Path (TSP) from the Low Discrepancy Sequence of points, wherein the TSP includes each point of the Low Discrepancy Sequence of points; and

re-sampling the TSP to produce a sequence of motion control points comprising the motion control trajectory;

scanning the region along the motion control trajectory, and measuring the region at a plurality of points along the motion control trajectory;

determining one or more characteristics of the object in response to said scanning; and

generating output indicating the one or more characteristics of the object.

10. The system of claim 9, wherein said generating a Traveling Salesman Path comprises applying Lin'"'"'s Nearest Neighbor algorithm to the Low Discrepancy Sequence of points to generate the Traveling Salesman Path.

11. The system of claim 9, wherein the TSP comprises a first sequence of points, wherein the first sequence o points defines a first trajectory having a first maximum curvature;

wherein said re-sampling the TSP comprises manipulating the first sequence of points to produce the sequence of motion control points;

wherein the sequence of motion control points defines a second trajectory having a second maximum curvature which is less than the first maximum curvature.

12. The system of claim 11, wherein the sequence of motion control points is a superset of the first sequence of points.

13. The system of claim 11, wherein the sequence of motion control points comprises a subset of the first sequence of points and one or more additional points.

14. The system of claim 9, wherein said calculating the Low Discrepancy Sequence of points in the region comprises determining a plurality of points, wherein any location in the region is within a specified distance of at least one of the Low Discrepancy Sequence of points.

15. The system of claim 9, wherein the region has a dimensionality of one of one or two.

16. The system of claim 9, wherein the region has a dimensionality greater than two.

17. A memory medium containing program instructions which are executable to scan for an object within a region, wherein said program instructions are executable to perform:

generating a motion control trajectory, by;

calculating a Low Discrepancy Sequence of points in the region; and

generating the motion control trajectory from the Low Discrepancy Sequence of points, by;

generating a Traveling Salesman Path TSP from the Low Discrepancy Sequence of points wherein the TSP includes each point of the Low Discrepancy Sequence of points; and

re-sampling the TSP to produce a sequence of motion control points comprising the motion control trajectory;

scanning the region along the motion control trajectory, and measuring the region at a plurality of points along the motion control trajectory;

determining one or more characteristics of the object in response to said scanning; and

generating output indicating the one or more characteristics of the object.

18. The memory medium of claim 17, wherein said generating a Traveling Salesman Path comprises applying Lin'"'"'s Nearest Neighbor algorithm to the Low Discrepancy Sequence of points to generate the Traveling Salesman Path.

19. The memory medium of claim 17,

therein the TSP comprises a first sequence of points, wherein the first sequence of points defines a first trajectory having a first maximum curvature;

wherein said re-sampling the TSP comprises manipulating the first sequence of points to produce the sequence of motion control points;

wherein the sequence of motion control points defines a second trajectory having a second maximum curvature which is less than the first maximum curvature.

20. The memory medium of claim 19,

wherein the sequence of motion control points is a superset of the first sequence of points.

21. The memory medium of claim 19,

wherein the sequence of motion control points comprises a subset of the first sequence of points and one or more additional points.

22. The memory medium of claim 17, wherein said calculating the Low Discrepancy Sequence of points in the region comprises determining a plurality of points, wherein any location in the region is within a specified distance of at least one of the Low Discrepancy Sequence of points.

23. The memory medium of claim 17, wherein the region has a dimensionality of one of one or two.

24. The memory medium of claim 17, wherein the region has a dimensionality greater than two.