System and method for generating a low discrepancy curve in a region

• US 20020140700A1
• Filed: 06/08/2001
• Published: 10/03/2002
• Est. Priority Date: 02/05/2001
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Nair, Dinesh, Wenzel, Lothar, Rajagopal, Ram
• Granted Patent: US 7,034,831 B2
• Time in Patent Office: Days
• US Class Current: 345/442
• CPC Class Codes: G05B 19/00 Programme-control systems
• 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: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• 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 generating a curve in a region, e.g., a Low Discrepancy Curve. The method may generate an unbounded Low Discrepancy Point (LDP); apply one or more boundary conditions to the unbounded LDP to generate a bounded LDP located within the region; repeat said generating and said applying one or more boundary conditions one or more times, generating a Low Discrepancy Sequence (LDS) in the region; store the LDS; and generate output comprising the LDS, wherein the LDS defines the curve in the region. The method may scan the region according to the defined curve. In generating the unbounded LDP, the method may select two or more irrational numbers, a step size epsilon (ε), and a starting position; initialize a current position to the starting position; and increment components of the current position based on ε and the irrational numbers to generate the unbounded LDP.

Claims

1. A method for generating a curve in a region, the method comprising:

generating an unbounded Low Discrepancy Point;

applying one or more boundary conditions to the unbounded Low Discrepancy Point to generate a bounded Low Discrepancy Point, wherein the bounded Low Discrepancy Point is located within the region;

repeating said generating and said applying one or more boundary conditions one or more times, thereby generating a Low Discrepancy Sequence in the region;

storing the Low Discrepancy Sequence; and

generating output comprising the Low Discrepancy Sequence, wherein the Low Discrepancy Sequence defines the curve in the region.

2. The method of claim 1, wherein the curve is a Low Discrepancy Curve.

3. The method of claim 1, further comprising:

scanning the region according to the curve defined by the Low Discrepancy Sequence.

4. The method of claim 1, wherein said generating the unbounded Low Discrepancy Point comprises:

selecting two or more irrational numbers;

selecting a step size epsilon (ε

);

selecting a starting position;

initializing a current position to the starting position; and

incrementing one or more terms of the current position based on a factor of ε and

one of the irrational numbers to generate the unbounded Low Discrepancy Point, wherein each term corresponds to a dimension of the region.

5. The method of claim 4, further comprising:

setting the current position to the bounded Low Discrepancy Point after said applying the one or more boundary conditions.

6. The method of claim 5, wherein said repeating said generating and said applying boundary conditions one or more times comprises:

repeating said incrementing, said applying one or more boundary conditions, and said setting the current position, one or more times.

7. The method of claim 4, further comprising:

selecting a maximum length L of the curve in the region;

initializing a current length to zero prior to said repeating; and

updating the current length to include a distance from the current position to the bounded Low Discrepancy Point after said generating the bounded Low Discrepancy Point;

wherein said repeating one or more times comprises repeating until the current length meets or exceeds the maximum length L.

8. The method of claim 4, wherein the starting position is a randomly selected point in the region.

9. The method of claim 4, wherein the region includes an origin, and wherein the starting position is the origin.

10. The method of claim 4, wherein the two or more irrational numbers are not integral multiples of each other.

11. The method of claim 1, wherein said applying one or more boundary conditions comprises:

if the unbounded Low Discrepancy Point is outside of the region, applying one of a reflecting boundary condition or a toroidal boundary condition at each border of the region.

12. The method of claim 1, wherein said storing the Low Discrepancy Sequence comprises:

storing each bounded Low Discrepancy Point of the Low Discrepancy Sequence as it is generated.

13. The method of claim 1, wherein the region comprises a 2-dimensional rectangular region, wherein the two or more irrational numbers comprise two irrational numbers, and wherein the curve in the region comprises one or more line segments.

14. The method of claim 13, wherein the rectangular region comprises a unit square.

15. The method of claim 1, wherein said generating the unbounded Low Discrepancy Point comprises:

selecting two or more irrational numbers (α

₁, . . . , α

_n) such that a sequence ({(n*α

₁)mod1}, . . . , {(n*α

_n)mod1}) comprises a first Low Discrepancy Sequence (LDS) in the region, where n is a natural number;

selecting a step size epsilon (ε

);

selecting a starting position (x0₁, . . . x0_n);

initializing a current position (x₁, . . . x_n) to the starting position (x0₁, . . . x0_n); and

incrementing each term (x_i) of the current position by (ε

* α

_i) to generate an unbounded Low Discrepancy Point (y₁, . . . y_n), wherein each term (x_i) corresponds to a dimension of the region.

16. The method of claim 15, wherein said applying one or more boundary conditions to the unbounded Low Discrepancy Point comprises:

applying a boundary condition to each term (y_i) of the unbounded Low Discrepancy Point (y₁, . . . y_n) in response to said incrementing to generate the bounded Low Discrepancy Point (z₁, . . . z_n);

17. The method of claim 16, further comprising:

setting the current position (x₁, . . . x_n) to the bounded Low Discrepancy Point (z₁, . . . z_n) after said applying the one or more boundary conditions.

18. The method of claim 15, further comprising:

selecting a maximum length L of the curve in the region;

initializing a current length to zero prior to said repeating; and

updating the current length to include a distance from the current position (x₁, . . . x_n) to the bounded Low Discrepancy Point (z₁, . . . z_n) after said generating the bounded Low Discrepancy Point (z₁, . . . z_n);

wherein said repeating one or more times comprises repeating until the current length meets or exceeds the maximum length L.

19. The method of claim 15, wherein the two or more irrational numbers (α

₁, . . ., α

_n) are not integral multiples of one another.

20. A method for generating a curve in a region, the method comprising:

selecting two or more irrational numbers;

selecting a step size epsilon (ε

);

selecting a starting position;

initializing a current position to the starting position;

incrementing each term of the current position based on a factor of ε and

one of the irrational numbers to generate an unbounded Low Discrepancy Point, wherein each term corresponds to a dimension of the region;

applying boundary conditions to one or more terms of the unbounded Low Discrepancy Point in response to said incrementing to generate a bounded Low Discrepancy Point, wherein the bounded Low Discrepancy Point is located within the region;

setting the current position to the bounded Low Discrepancy Point;

storing the bounded Low Discrepancy Point;

repeating said incrementing, said applying boundary conditions, said setting the current position, and said storing one or more times, thereby generating a Low Discrepancy Sequence in the region; and

generating output comprising the Low Discrepancy Sequence, wherein the Low Discrepancy Sequence defines the curve in the region.

21. The method of claim 20, wherein the two or more irrational numbers are useable in creating at least one Low Discrepancy Sequence (LDS) in the region.

22. A method for generating a Low Discrepancy Curve in a region, the method comprising:

selecting a starting position (x0₁, . . . x0_n);

initializing a current position (x₁, . . . x_n) to the starting position;

incrementing each term (x_i) of the current position by (ε

*α

₁) to generate an unbounded Low Discrepancy Point (y₁, . . . y_n), wherein each term (x_i) corresponds to a dimension of the region;

applying boundary conditions to each term (y_i) of the unbounded Low Discrepancy Point (y₁, . . . y_n) in response to said incrementing to generate a bounded Low Discrepancy Point (z₁, . . . z_n);

setting the current position (x₁, . . . x_n) to the bounded Low Discrepancy Point (z₁, . . . z_nZn);

storing the bounded Low Discrepancy Point (z₁, . . . z_n);

repeating said incrementing, said applying boundary conditions, said setting the current position, and said storing until a stopping condition is reached, thereby generating a second Low Discrepancy Sequence in the region; and

generating output, wherein said output comprises the second Low Discrepancy Sequence, wherein the second Low Discrepancy Sequence defines the Low Discrepancy Curve in the region.

24. The memory medium of claim 23, wherein the programs instructions are further executable to perform:

scanning the region according to the curve defined by the Low Discrepancy Sequence.

25. The memory medium of claim 23, wherein said applying one or more boundary conditions comprises:

if the unbounded Low Discrepancy Point is outside of the region, applying one of a reflecting boundary condition or a toroidal boundary condition at each border of the region.

26. The memory medium of claim 23, wherein said generating the unbounded Low Discrepancy Point comprises:

storing two or more irrational numbers;

storing a step size epsilon (ε

);

storing a starting position;

initializing a current position to the starting position; and

incrementing one or more terms of the current position based on a factor of ε and

one of the irrational numbers to generate the unbounded Low Discrepancy Point, wherein each term corresponds to a dimension of the region.

27. The memory medium of claim 26, wherein the programs instructions are further executable to perform:

setting the current position to the bounded Low Discrepancy Point after said applying the one or more boundary conditions.

28. The memory medium of claim 27, wherein said repeating said generating and said applying boundary conditions one or more times comprises:

repeating said incrementing, said applying one or more boundary conditions, and said setting the current position, one or more times.

29. The memory medium of claim 28, wherein the programs instructions are further executable to perform:

storing a maximum length L of the curve in the region;

initializing a current length to zero prior to said repeating; and

updating the current length to include a distance from the current position to the bounded Low Discrepancy Point after said generating the bounded Low Discrepancy Point;

wherein said repeating one or more times comprises repeating until the current length meets or exceeds the maximum length L.

30. The memory medium of claim 26, wherein the starting position is a randomly selected point in the region.

31. The memory medium of claim 23, wherein said storing the Low Discrepancy Sequence comprises:

storing each bounded Low Discrepancy Point of the Low Discrepancy Sequence as it is generated.

32. The memory medium of claim 23, wherein the region comprises a 2-dimensional rectangular region, wherein the two or more irrational numbers comprise two irrational numbers, and wherein the curve in the region comprises one or more line segments.

33. The memory medium of claim 32, wherein the rectangular region comprises a unit square.

35. The system of claim 34, wherein the CPU is further operable to execute said one or more software programs to perform:

scanning the region according to the curve defined by the Low Discrepancy Sequence.

36. The system of claim 34, wherein said applying one or more boundary conditions comprises:

if the unbounded Low Discrepancy Point is outside of the region, applying one of a reflecting boundary condition or a toroidal boundary condition at each border of the region.

37. The system of claim 34, wherein said generating the unbounded Low Discrepancy Point comprises:

storing two or more irrational numbers;

storing a step size epsilon (ε

);

storing a starting position;

initializing a current position to the starting position;

incrementing one or more terms of the current position based on a factor of ε and

one of the irrational numbers to generate the unbounded Low Discrepancy Point, wherein each term corresponds to a dimension of the region; and

setting the current position to the bounded Low Discrepancy Point after said applying the one or more boundary conditions.

38. The system of claim 37, wherein the programs instructions are further executable to perform:

storing a maximum length L of the curve in the region;

initializing a current length to zero prior to said repeating; and

updating the current length to include a distance from the current position to the bounded Low Discrepancy Point after said generating the bounded Low Discrepancy Point;

wherein said repeating one or more times comprises repeating said incrementing, said applying one or more boundary conditions, said setting the current position, and said updating the current length, until the current length meets or exceeds the maximum length L.

23. A memory medium which is operable to store program instructions for generating a curve in a region, wherein said program instructions are executable to perform:

generating an unbounded Low Discrepancy Point;

applying one or more boundary conditions to the unbounded Low Discrepancy Point to generate a bounded Low Discrepancy Point, wherein the bounded Low Discrepancy Point is located within the region;

repeating said generating and said applying one or more boundary conditions one or more times, thereby generating a Low Discrepancy Sequence in the region;

storing the Low Discrepancy Sequence; and

generating output comprising the Low Discrepancy Sequence, wherein the Low Discrepancy Sequence defines the curve in the region.

34. A system for generating a curve in a region, comprising:

a CPU; and

a memory medium which is operable to store one or more software programs;

wherein said CPU is operable to execute said one or more software programs to perform;

generating an unbounded Low Discrepancy Point;

applying one or more boundary conditions to the unbounded Low Discrepancy Point to generate a bounded Low Discrepancy Point, wherein the bounded Low Discrepancy Point is located within the region;

repeating said generating and said applying one or more boundary conditions one or more times, thereby generating a Low Discrepancy Sequence in the region;

storing the Low Discrepancy Sequence; and

generating output comprising the Low Discrepancy Sequence, wherein the Low Discrepancy Sequence defines the curve in the region.