Image processing system and method using subsampling with constraints such as time and uncertainty constraints

• US 6,157,732 A
• Filed: 04/07/1999
• Issued: 12/05/2000
• Est. Priority Date: 03/18/1997
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Drisko, Robert, Bachelder, Ivan A.
• Primary Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US09/287,637
• Time in Patent Office: 608 Days
• Field of Search: 382/141, 382/145, 382/148, 382/149, 382/147, 382/151, 382/152, 382/154, 382/298-300, 348/86, 348/87, 348/94, 348/125, 348/126
• US Class Current: 382/148
• CPC Class Codes: G06T 2207/30141 Printed circuit board [PCB]
• CPC Class Codes: G06T 7/0004 Industrial image inspection
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80

Abstract

A method and apparatus subsamples, in a constraint satisfying manner, an image for subsequent processing of the subsampled image. The subsampling is based on constraints provided for the subsequent image processing. A subsampling factor or pair of factors are determined for the image and the image is subsampled by the subsampling factor(s). The constraints comprise at least time constraints, uncertainty constraints, accuracy constraints or implementation constraints. When time constraints are given, the constraints specify a function of the time needed for the subsequent image processing along with at least a maximum and a minimum time that the subsequent image processing should take. When uncertainty constraints are specified, the constraints give a function of the uncertainty in the subsequent image processing and at least a maximum and a minimum uncertainty required from the subsequent image processing. When the constraints specify accuracy constraints, the constraints specify a function of the accuracy of the subsequent image processing at least a maximum and a minimum accuracy required from the subsequent image processing.

Claims

1. In an automated object inspection system involving locating an object in an input image, an image processing method comprising:

obtaining a pixel representation of an input image including said object;

obtaining expected geometric parameters representing certain expected geometric features of said object;

selecting from said pixel representation a set of pixels required for input to an object locating process;

defining, after said selecting said set of pixels and after said obtaining said expected geometric parameters, a subsampling factor based upon at least said expected geometric parameters, said subsampling factor defining a reduction in resolution of said set of pixels;

subsampling said set of pixels in accordance with the defined subsampling factor; and

running said object locating process on the subsampled set of pixels, wherein said defining further comprises;

determining a set of image sizes, satisfying a function t, which yields results between a maximum and a minimum allowed times;

determining a set of image resolutions, satisfying a function u, which yields an appropriate accuracy; and

selecting the subsampling factor based on an intersection of the set of image sizes and the set of image resolutions.

2. The method according to claim 1, wherein said defining a subsampling factor comprises estimating an uncertainty value indicative of an uncertainty in a location to be determined by running said object locating process, and defining said subsampling factor so said uncertainty value falls within a desired uncertainty range.

3. The method according to claim 2, wherein said defining said subsampling factor comprises defining said subsampling factor so said time value is maximized while said uncertainty value falls within said desired uncertainty range.

4. The method according to claim 3, wherein said object comprises a surface mounted device (SMD).

5. The method according to claim 1, wherein said object comprises a surface mounted device (SMD).

16. The method of claim 1, wherein said defining further comprises selecting the subsampling factor that is allowable by hardware constraints and software constraints.

6. Computer-readable media tangibly embodying a program of instructions executable by the machine to perform functions including:

obtaining a pixel representation of a input image including said object;

obtaining expected geometric parameters representing certain expected geometric features of said object;

selecting from said pixel representation a set of pixels required for input to an object locating process;

defining, after said selecting said set of said pixels and after said obtaining said expected geometric parameters, a subsampling factor based upon at least said expected geometric parameters, said subsampling factor defining a reduction in resolution of said set of pixels;

subsampling said set of pixels in accordance with the defined subsampling factor; and

running said object locating process on the subsampled set of pixels, wherein said defining further comprises;

determining a set of image sizes, satisfying a function t, which yields results between a maximum and a minimum allowed times;

determining a set of image resolutions, satisfying a function u, which yields an appropriate accuracy; and

selecting the subsampling factor based on an intersection of the set of image sizes and the set of image resolutions.

7. The method according to claim 6, wherein said defining a subsampling factor comprises estimating an uncertainty value indicative of an uncertainty in a location to be determined by running said object locating process, and defining said subsampled factor so said uncertainty value falls within a desired uncertainty range.

8. The method according to claim 7, wherein said defining said subsampled factor comprises defining said subsampled factor so said time value is maximized while said uncertainty value falls within said desired uncertainty range.

9. The method according to claim 8, wherein said object comprises a surface mounted device (SMD).

10. The method according to claim 6, wherein said object comprises a surface mounted device (SMD).

11. An automated object inspection system involving locating an object in an input image, said system comprising:

means for obtaining a pixel representation of an input image including said object;

means for obtaining expected geometric parameters representing certain expected geometric features of said object;

means for selecting from said pixel representation a set of pixels required for input to an object locating process;

means for defining, after said set of pixels is selected and after said expected geometric parameters are obtained, a subsampling factor based upon at least said expected geometric parameters, said subsampling factor defining a reduction in resolution of said set of pixels;

means for subsampling said set of pixels in accordance with the defined subsampling factor; and

means for running said object locating process on the subsampled set of pixels wherein said means for defining further comprises;

means for determining a set of image sizes, satisfying a function t, which yields results between a maximum and a minimum allowed times;

means for determining a set of image resolutions, satisfying a function u, which yields an appropriate accuracy; and

means for selecting the subsampling factor based on an intersection of the set of image sizes and the set of image resolutions.

12. The system according to claim 11, wherein said defining a subsampling factor comprise estimating an uncertainty value indicative of an uncertainty in location determined by running said object locating process, and means for defining said subsampling factor so said uncertainty value falls within a desired uncertainty range.

13. The system according to claim 12, wherein said means for defining said subsampling factor comprise means for defining said subsampling factor so said time value is maximized while said uncertainty value falls within said desired uncertainty range.

14. The system according to claim 13, wherein said object comprises a surface mounted device (SMD).

15. The system according to claim 11, wherein said object comprises a surface mounted device (SMD).

17. In an automated object inspection system involving locating an object in an input image, an image processing method comprising:

obtaining a pixel representation of an input image including said object;

obtaining expected geometric parameters representing certain expected geometric features of said object;

selecting from said pixel representation a set of pixels required for input to an object locating process;

defining, after said selecting said set of pixels and after said obtaining said expected geometric parameters, a subsampling factor based upon at least said expected geometric parameters, said subsampling factor defining a reduction in resolution of said set of pixels;

subsampling said set of pixels in accordance with the defined subsampling factor; and

running said object locating process on the subsampled set of pixels, wherein said defining further comprises;

creating space for a two-dimensional matrix T of size (w_max -w_min, h_max -h_min), where w is a width and h is a height, and space for a two-dimensional matrix U of size (w_max -w_min, h_max -h_min);

setting a value of the matrix T(w,h) to a value indicating satisfaction of a time function t(w,h) if a value of the time function t(w,h) is greater than a minimum value of allowable time t_min and the value of the time function t(w, h) is less than a maximum value of allowable time t_max, otherwise setting the value of the matrix T(w,h) to a value indicating no satisfaction of the time function t(w,h).