METHOD OF IMAGE ANALYSIS USING SPARSE HOUGH TRANSFORM

• US 20090238459A1
• Filed: 05/07/2009
• Published: 09/24/2009
• Est. Priority Date: 01/25/2006
• Status: Active Grant

• Current Assignee: Tungsten Automation Corp.
• Original Assignee: Atalasoft Incorporated (Kofax Ltd.)
• Inventors: Minerich, Richard T., Hawley, Stephen
• Granted Patent: US 8,385,647 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/20061 Hough transform
• 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. 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:

dividing said digital image into a plurality of tiles;

creating a list of active tiles from said plurality of tiles;

removing active tiles from said list that do not meet a threshold criteria.

2. The media of claim 1 wherein said step of creating a list of active tiles from said plurality of tiles comprises:

pseudo-randomly generating coordinates for an origin tile;

applying said pseudo-randomly coordinates to select a pixel from said origin tile; and

applying said origin tile coordinates to other of said plurality of tiles to select pixels.

3. The media of claim 1 wherein said step of removing active tiles from said list comprises:

analyzing said pseudo-randomly generated pixels to determine if each pixel meets a threshold criteria; and

removing tiles in which pixels from said tiles do not meet said criteria.

4. The media of claim 1 further comprising the step of processing any remaining active tiles according to a parameterization transform.

5. The media of claim 2 wherein the parameterization transform is a selected one of a Radon transform and a Hough transform.

6. 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:

dividing said digital image into a plurality of tiles;

creating a list of active tiles from said plurality of tiles;

removing active tiles from said list that yield results that do not meet a threshold criteria; and

processing remaining active tiles according to a parameterization transform.

7. The media of claim 6 wherein said step of creating a list of active tiles from said plurality of tiles comprises:

generating coordinates for an origin tile;

applying said coordinates to select a pixel from said origin tile; and

applying said origin tile coordinates to other of said plurality of tiles to select pixels.

8. The media of claim 7 wherein said coordinates are generated either randomly or pseudo-randomly.

9. The media of claim 7 wherein said step of removing active tiles from said list comprises:

analyzing said pixels to determine if they meet a threshold criteria; and

removing tiles in which pixels from said tiles do not meet said criteria.

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

11. 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 dividing a digital image into tiles, selecting a pixel from each of said tiles, and processing at least one of said pixels according to a parameterization transform, wherein the pixels are pseudo-randomly selected, and wherein the number of pixels processed is less than a total number of pixels in said digital image.

12. The digital imaging system of claim 11 wherein said parameterization transform is a selected one of a Radon transform and a Hough transform.

13. The digital imaging system of claim 11 wherein said processor analyzes each of said pixels and performs said parameterization transform only on those tiles whose pixels meet a predetermined criteria.

14. A method of analyzing a digital image, the method comprising the steps of:

dividing said digital image into a plurality of tiles;

creating a list of active tiles from said plurality of tiles;

removing active tiles from said list that do not meet a threshold criteria; and

wherein said steps are performed by a digital imaging system that includes an image capture mechanism and a processor.

16. The method of claim 14 wherein said step of removing active tiles from said list comprises:

analyzing said pseudo-randomly generated pixels to determine if each pixel meets a threshold criteria; and

removing tiles in which pixels from said tiles do not meet said criteria.

17. The method of claim 14 further comprising the step of processing any remaining active tiles according to a parameterization transform.

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

15. The method of claim 15 wherein said step of creating a list of active tiles from said plurality of tiles comprises:

pseudo-randomly generating coordinates for an origin tile;

applying said pseudo-randomly coordinates to select a pixel from said origin tile; and

applying said origin tile coordinates to other of said plurality of tiles to select pixels.