System and method for sampling and/or placing objects using low discrepancy sequences

• US 6,370,270 B1
• Filed: 08/27/1999
• Issued: 04/09/2002
• Est. Priority Date: 01/06/1999
• Status: Expired due to Term

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Nair, Dinesh, Vazquez, Nicolas, Wenzel, Lothar, DeKey, Samson
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/385,121
• Time in Patent Office: 956 Days
• Field of Search: 382/209, 382/215, 382/217, 382/218, 382/219, 382/220, 382/161, 382/228, 382/141, 382/112, 707/526, 707/527, 707/523, 707/541
• US Class Current: 382/209
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30108 Industrial image inspection
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 2201/06 Recognition of objects for industrial automation

Abstract

A system and method for improved image characterization, object placement, and mesh design utilizing Low Discrepancy sequences. The Low Discrepancy sequence is designed to produce sample points which maximally avoid one another, i.e., the distance between any two sample points is maximized. The invention may be applied specifically to methods of image characterization, pattern matching, acquiring image statistics, object location, image reconstruction, motion estimation, object placement, sensor placement, and mesh design, among others. Image characterization is performed by receiving an image and then sampling the image using a Low Discrepancy sequence, also referred to as a quasi-random sequence, to determine a plurality of sample pixels in the image which characterize the image. Sensor placement is performed by generating a Low Discrepancy sequence for the desired placement application, and then selecting locations for the optimal placement of sensors using the generated Low Discrepancy sequence.

Claims

1. A computer-implemented method for characterizing an image, the method comprising:

receiving the image, wherein the image comprises a first plurality of pixels;

sampling the image using a Low Discrepancy sequence to determine a plurality of sample pixels in the image which characterize the image; and

storing the plurality of sample pixels in a memory of the computer system, wherein the plurality of sample pixels characterize the image.

2. The method of claim 1, wherein the Low Discrepancy sequence is a quasi-random sequence.

3. The method of claim 1, wherein the Low Discrepancy sequence is designed to produce sample points which maximally avoid each other.

4. The method of claim 1, wherein said Low Discrepancy sequence sampling results in fewer points to characterize the image than a uniform or random sequence.

5. The method of claim 1, wherein the Low Discrepancy sequence is a Halton sequence.

6. The method of claim 1, wherein the Low Discrepancy sequence is a sequence selected from the group comprising:

Halton, Sobol, Faure, and Niederreiter.

7. The method of claim 1, wherein said sampling the image using a Low Discrepancy sequence comprises:

generating the Low Discrepancy sequence;

selecting pixels in the image using the Low Discrepancy sequence to determine a plurality of sample pixels in the image which characterize the image.

8. The method of claim 1, further comprising:

receiving user input indicating a desired granularity of an image characterization;

wherein the method generates a number of sample pixels based on the desired granularity of the image characterization.

9. The method of claim 1,

wherein the image is a template image used in pattern matching;

the method further comprising;

receiving a target image;

comparing the sample pixels in the template image with pixels in the target image to determine one or more instances of the template image in the target image.

10. The method of claim 1, further comprising:

determining image statistics based on the sample pixels.

11. The method of claim 1, wherein said sampling the image and said storing the plurality of sample pixels are performed by a first computer system;

the method further comprising;

the first computer system transmitting the sample pixels to a second computer system over a network;

the second computer system displaying the sample pixels.

12. The method of claim 11, further comprising:

the second computer system reconstructing pixels from the image which were not received, wherein said reconstructed pixels are displayed with the sample pixels to display a more complete image.

13. The method of claim 1,

wherein the image is a search image used in motion estimation;

the method further comprising;

receiving a target image;

comparing the sample pixels in the search image with pixels in the target image to determine a motion vector.

14. A system for characterizing an image, wherein the image comprises a first plurality of pixels, the system comprising:

a memory which stores the image, wherein the image comprises a first plurality of pixels;

a processor coupled to the memory which is operable to sample the image using a Low Discrepancy sequence to determine a plurality of sample pixels in the image which characterize the image;

wherein the memory is operable to store the plurality of sample pixels, wherein the plurality of sample pixels characterize the image.

15. The system of claim 14, wherein the Low Discrepancy sequence is a quasi-random sequence.

16. The system of claim 14, wherein the Low Discrepancy sequence is designed to produce sample points which maximally avoid each other.

17. The system of claim 14, wherein said Low Discrepancy sequence sampling results in fewer points to characterize the image than a uniform or random sequence.

18. The system of claim 14, wherein the Low Discrepancy sequence is a sequence selected from the group comprising:

Halton, Sobol, Faure, and Niederreiter.

19. The system of claim 14, wherein the system is a machine vision system.

20. The system of claim 14,

wherein the processor is operable to generate the Low Discrepancy sequence;

wherein the processor selects pixels in the image using the generated Low Discrepancy sequence to determine a plurality of sample pixels in the image which characterize the image.

21. The system of claim 14, wherein the image is a template image used in pattern matching;

wherein the system further includes an input for receiving a target image;

wherein the processor is operable to compare the sample pixels in the template image with pixels in the target image to determine one or more instances of the template image in the target image.

22. The system of claim 14, wherein the processor is operable to determine image statistics based on the sample pixels.

23. The system of claim 14, wherein the image is a search image used in motion estimation;

wherein the system further includes an input for receiving a target image;

wherein the processor is operable to compare the sample pixels in the template image with pixels in the target image to determine a motion vector.

24. The system of claim 14, further comprising:

a transmitter coupled to the memory which is operable to transmit the sample pixels to a second computer system over a network;

wherein the second computer system is operable to display the sample pixels.

25. A system for transmitting an image, the system comprising:

a first computer system, comprising;

a memory which stores the image, wherein the image comprises a first plurality of pixels;

a processor coupled to the memory which is operable to sample the image using a Low Discrepancy sequence to determine a plurality of sample pixels in the image which characterize the image;

a transmitter coupled to the memory which is operable to transmit the sample pixels over a network;

a second computer system coupled to the first computer system over the network, comprising;

an input for receiving the sample pixels; and

a display for displaying the sample pixels.

26. The system of claim 25,

wherein the second computer system is operable to reconstruct pixels from the image which were not received, wherein said reconstructed pixels are displayed with the sample pixels to display a more complete image.

27. A memory medium which comprises program instructions for characterizing an image, wherein the image comprises a first plurality of pixels, wherein the program instructions are executable to implement:

sampling the image using a Low Discrepancy sequence to determine a plurality of sample pixels in the image which characterize the image; and

storing the plurality of sample pixels in a memory of the computer system, wherein the plurality of sample pixels characterize the image.

28. The memory medium of claim 27, wherein the Low Discrepancy sequence is a quasi-random sequence.

29. The memory medium of claim 27, wherein the Low Discrepancy sequence is designed to produce sample points which maximally avoid each other.

30. The memory medium of claim 27, wherein said Low Discrepancy sequence sampling results in fewer points to characterize the template image than a uniform or random sequence.

31. The memory medium of claim 27, wherein the Low Discrepancy sequence is a sequence selected from the group comprising:

Halton, Sobol, Faure, and Niederreiter.

32. The memory medium of claim 27,

wherein the image is a template image used in pattern matching;

wherein, in response to a received target image, the program instructions are further executable to implement;

comparing the sample pixels in the template image with pixels in the target image to determine one or more instances of the template image in the target image.

33. The memory medium of claim 27, wherein the program instructions are further executable to implement:

determining image statistics based on the sample pixels.

34. The memory medium of claim 27, wherein said sampling the image and said storing the plurality of sample pixels are performed by a first computer system;

wherein the program instructions are further executable to implement;

transmitting the sample pixels to a second computer system over a network;

wherein the second computer system is operable to display the sample pixels.

35. The memory medium of claim 27,

wherein the image is a search image used in motion estimation;

wherein, in response to a received target image, the program instructions are further executable to implement;

comparing the sample pixels in the search image with pixels in the target image to determine a motion vector.

36. A computer-implemented method for placing sensors in an area for coverage of the area, the method comprising:

generating a Low Discrepancy sequence;

placing the sensors at locations in the area according to the Low Discrepancy sequence.

37. The method of claim 36, wherein the area is a 2-dimensional area.

38. The method of claim 36, wherein the area is a 3-dimensional volume.

39. The method of claim 36, further comprising:

receiving information on the area in response to user input, wherein said information includes dimensions of the area;

wherein said generating the Low Discrepancy sequence is performed based on said information.

40. The method of claim 36, wherein the area is determined by the computer based on the type and number of sensors to be placed.

41. The method of claim 36, wherein the Low Discrepancy sequence is a quasi-random sequence.

42. The method of claim 36, wherein the Low Discrepancy sequence is designed to produce sample points which maximally avoid each other.

43. The method of claim 36, wherein the Low Discrepancy sequence is a sequence selected from the group comprising:

Halton, Sobol, Faure, and Niederreiter.

44. A computer-implemented method for placing sensors in an area for coverage of the area, the method comprising:

receiving information on the area in response to user input, wherein said information includes dimensions of the area;

generating a Low Discrepancy sequence, wherein the Low Discrepancy sequence is generated based on said information;

placing the sensors at locations in the area according to the Low Discrepancy sequence.

45. A computer-implemented method for constructing a CCD sensor comprising a plurality of CCD sensor elements, the method comprising:

generating a Low Discrepancy sequence, wherein elements of the Low Discrepancy sequence indicate locations of the CCD sensor elements;

constructing the CCD sensor, wherein said constructing includes placing the CCD sensor elements at locations in the CCD sensor according to the Low Discrepancy sequence.

46. A computer-implemented method for constructing a CCD sensor, the method comprising:

generating a Low Discrepancy sequence;

placing CCD sensor elements at locations in the CCD sensor according to the Low Discrepancy sequence.