Method of image analysis using sparse hough transform

• US 20070172148A1
• Filed: 01/25/2006
• Published: 07/26/2007
• Est. Priority Date: 01/25/2006
• Status: Active Grant

• Current Assignee: Tungsten Automation Corp.
• Original Assignee: Atalasoft Incorporated (Kofax Ltd.)
• Inventors: Hawley, Stephen
• Granted Patent: US 7,738,730 B2
• Time in Patent Office: Days
• US Class Current: 382/281
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

A digital image includes a plurality of pixels arranged in an array. In a method of analyzing the image, some of the pixels are purposefully not processed. In particular, only those pixels in a particular subgroup are processed according to a Hough or similar transform. The number of pixels in the subgroup is less than the total number of pixels in the image (e.g., as little as about 5% of the total pixels), and each pixel in the subgroup is pseudo-randomly selected. The Hough transform is inherently configured to function within the context of noisy images, for identifying features of interest in the image, as simulated by the pseudo-random selection and processing of less than the total number of pixels in the image. This significantly reduces the processor resources required to analyze the image.

Claims

1. A method of analyzing an image having a plurality of image pixels, the method comprising the steps of:

pseudo-randomly selecting a subgroup of said plurality of pixels, wherein the number of pixels in said subgroup is less than the total number of pixels in said image; and

processing each of the pixels in the subgroup according to a parameterization transform.

2. The method of claim 1 wherein:

the plurality of image pixels are arranged in a rectangular array; and

the subgroup of pixels are pseudo-randomly distributed about the rectangular array.

3. The method of claim 1 wherein the number of pixels in said subgroup comprises less than about 30 percent of the number of pixels in the plurality of pixels in the image.

4. The method of claim 3 wherein the number of pixels in said subgroup comprises about 5 percent of the number of pixels in the plurality of pixels in the image.

5. The method of claim 1 further comprising the step of:

choosing the number of pixels in said subgroup based on at least one quality characteristic of the image.

6. The method of claim 1 wherein the parameterization transform is a selected one of a Radon transform and a Hough transform.

7. The method of claim 6 further comprising the steps of:

transforming Cartesian coordinate data for each pixel in the subgroup to normal parameters;

incrementing cells in an accumulator matrix according to the normal parameters;

identifying at least one accumulator matrix cell having a maximum value; and

converting normal parameter values of the at least one identified accumulator matrix cell to Cartesian coordinate values.

8. A method of analyzing an image having a plurality of image pixels, the method comprising the steps of:

pseudo-randomly selecting one of said plurality of image pixels;

processing the selected pixel according to a parameterization transform; and

repeating the selection and processing steps for a selected number of said plurality of image pixels, said selected number being less than a total number of said plurality of image pixels.

9. The method of claim 8 wherein the number of selected pixels comprises no more than about 30 percent of the plurality of image pixels.

10. The method of claim 9 wherein the number of selected pixels comprises about 5 percent of the plurality of image pixels.

11. The method of claim 8 wherein:

the plurality of image pixels are arranged in a rectangular array; and

the selected pixels are pseudo-randomly distributed about the rectangular array.

12. The method of claim 8 wherein the parameterization transform is a selected one of a Radon transform and a Hough transform.

13. A method of analyzing an image having a plurality of pixels arranged in an array, the method comprising the steps of:

selecting a subgroup of said plurality of pixels, wherein the number of pixels in said subgroup is less than the total number of pixels in said image, and wherein the pixels in the subgroup are distributed about the entirety of the array; and

processing each of the pixels in the subgroup according to a parameterization transform.

14. The method of claim 13 wherein the pixels in the subgroup are pseudo-randomly distributed about the entirety of the array.

15. The method of claim 14 wherein the number of pixels in the subgroup comprises from about 5 percent to about 30 percent of the plurality of pixels of the image.

16. Electronically-readable media tangibly embodying a program of instructions executable by a processor to perform a method of image analysis, the method comprising the steps of:

selecting one of a plurality of image pixels of a digital image;

processing the selected pixel according to a parameterization transform; and

repeating the selection and processing steps for a selected number of said plurality of image pixels only, said selected number being less than a total number of said plurality of image pixels.

17. The media of claim 16 wherein the selected pixels are pseudo-randomly selected.

18. A digital imaging system comprising:

an image capturing mechanism configured for obtaining a digital image comprising a plurality of pixels stored in a memory of the digital imaging system; and

a processor electrically connected to at least one of the image capturing mechanism and memory and configured for processing each pixel in a subgroup of said plurality of pixels according to a parameterization transform, wherein the pixels in the subgroup are pseudo-randomly selected, and wherein the number of pixels in the subgroup is less than a total number of pixels in said plurality of pixels.

19. A method of analyzing an array of image pixels, the method comprising the steps of:

processing a first plurality of the image pixels in the array according to a parameterization transform, wherein;

the first plurality comprises less than a total number of pixels in said array; and

the pixels in the first plurality are chosen based on a selected one of a negative pseudo-random selection process and a positive pseudo-random selection process.

20. The method of claim 19 wherein the parameterization transform is a Hough transform.

21. The method of claim 19 wherein the pixels in the first plurality are chosen based on a negative pseudo-random selection process comprising:

pseudo-randomly selecting a second plurality of pixels in said array, wherein a sum of the first and second pluralities of pixels comprises the total number of pixels in said array; and

deleting the second plurality of pixels from the array.

22. A method of analyzing an image having a plurality of pixels, the method comprising the steps of:

processing no more than a portion of the plurality of pixels according to a Hough transform, wherein the pixels for processing are selected according to one of a random and pseudo-random process.