Method of image analysis using sparse hough transform

• US 7,738,730 B2
• Filed: 01/25/2006
• Issued: 06/15/2010
• Est. Priority Date: 01/25/2006
• Status: Active Grant

• Current Assignee: Kofax Incorporated
• Original Assignee: Atalasoft Incorporated (Kofax Ltd.)
• Inventors: Hawley, Stephen
• Primary Examiner(s): Kassa; Yosef
• Application Number:
  US11/339,724
• Publication Number:
  US 20070172148A1
• Time in Patent Office: 1,602 Days
• Field of Search: 382/274, 382/275, 382/281
• 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 individual pixels from an entirety of said image, said selected pixels forming 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 one of a Radon transform and a Hough 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 5 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.

7. 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 of said plurality of image pixels being distributed about an entirety of said image, and said selected number being less than a total number of said plurality of image pixels.

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

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

10. The method of claim 7 wherein:

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

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

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

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

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

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

wherein said negative pseudo-randomly selecting a first subgroup comprises pseudo-randomly selecting a second subgroup of said plurality of pixels in said image and deleting said second subgroup of said plurality of pixels; and

wherein a sum of the first and second subgroups of said plurality of pixels comprises the total number of pixels in the image.

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

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

15. 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 of said plurality of image pixels being distributed about an entirety of said image, and said selected number being less than a total number of said plurality of image pixels.

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

17. 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; and

wherein the processor is further configured for 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.

18. 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 one of a Radon transform and a Hough transform;

transforming Cartesian coordinate data for each pixel in said first plurality of image pixels 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;

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

wherein 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.

19. The method of claim 18 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.

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

pseudo-randomly selecting individual pixels from an entirety of said image, said selected pixels forming 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 one of a Radon transform and a Hough transform;

wherein said image is captured by an image capture device electrically connected to an electronic processor; and

wherein said step of pseudo-randomly selecting and said step of processing are performed by said electronic processor.