Method and system for parallel processing of Hough transform computations

• US 7,406,212 B2
• Filed: 06/02/2005
• Issued: 07/29/2008
• Est. Priority Date: 06/02/2005
• Status: Expired due to Fees

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Nasir, Irfan, Mohamed, Magdi A.
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US11/143,169
• Publication Number:
  US 20060274973A1
• Time in Patent Office: 1,153 Days
• Field of Search: 382/280, 382/281, 382248-250, 708400-410
• 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

In a parallel computation of a Hough transform of an array of input data values, the transform space of the Hough transform is partitioned dynamically or statically into a number of sub-spaces. Each sub-space of the transform is stored in a sub-space of memory locations. Data values from the array of input data values are passed to a plurality of processors, each processor associated dynamically or statically with a sub-space of memory locations. Each processor, acting in parallel with the other processors, updates constituent elements of the Hough transform stored in the associated sub-space memory locations dependent upon the input data value.

Claims

1. A system for parallel computation of a Hough transform that utilizes a curve parameterized by the equation s(x,p)=0, where p is a parameter vector in the transform space, x is a position vector in the data array, and s is a function, the system comprising:

a plurality of processors capable of parallel operation;

a first memory interface for retrieving a data value at position x_i from an image memory and passing the data value to each of the plurality of processors; and

a plurality of Hough transform sub-space memories, each associated with a processor of the plurality of processors;

wherein a processor of the plurality of processors is operable to receive the data value at position x_i from the first memory interface and update Hough transform values of parameters p satisfying the equation s(x_i,p)=0 in the associated memory of the plurality of Hough transform sub-space memories.

2. A system in accordance with claim 1, further comprising an image memory operable to store a plurality of data values.

3. A system in accordance with claim 2, further comprising a pre-processor, operable to pre-process a plurality of pixel values of an image to produce the plurality of data values in the image memory.

4. A system in accordance with claim 1, further comprising:

a second memory interface operable to retrieve Hough transform values from the plurality of Hough transform sub-space memories; and

a post-processor, operable to process the Hough transform values.

5. A system in accordance with claim 1, wherein the plurality of Hough transform sub-space memories comprise non-overlapping regions of a single physical memory.

6. A system in accordance with claim 5, wherein the plurality of Hough transform sub-space memories are dynamically allocated from the single physical memory.

7. A method for parallel computation of a transform of an array of data values to a transform space, the method comprising:

initializing a transform space memory;

retrieving a data value from the array of data values;

partitioning the transform space memory into a plurality of transform sub-space memories;

passing the data value to a plurality of processors, each processor associated with a transform sub-space memory of the plurality of transform sub-space memories;

each processor of the plurality of processors updating a plurality of elements of the transform stored in the associated transform sub-space memory dependent upon the data value; and

providing an output dependent upon elements of the transform space, wherein the transform comprises a Hough transform that utilizes a curve parameterized by the equation s(x,p)=0, where p is a parameter vector in the transform space, x is a position vector in the data array, and s is a function and wherein the data value at position x_i is used to update transform parameters p satisfying the equation s(x_i,p)=0.

8. A method in accordance with claim 7, wherein updating elements of the transform comprises:

determining a set of elements in the transform sub-space that are affected by the data value; and

adding the data value to each element in the set of affected elements.

9. A method in accordance with claim 7, wherein the data array comprises pixel values determined by preprocessing an image to detect foreground elements.

10. A method in accordance with claim 7, wherein the data array comprises pixel values determined by preprocessing an image to detect edges of objects in the image.

11. A method in accordance with claim 7, further comprising searching the elements of the Hough transform to find the largest value in the Hough transform elements and wherein providing an output dependent upon the elements of the Hough transform comprises outputting the largest value and its location in the Hough transform.

12. A method in accordance with claim 7, wherein the parallel computation is of a Hough transform and further comprising:

prior to initializing, quantizing the transform space of the Hough transform into a plurality of discrete parameter values, each parameter value have K elements and the plurality of discrete parameter values defining a K-dimensional discrete transform space.

13. A method in accordance with claim 12, wherein the transform memory is partitioned into a plurality of Hough transform sub-space memories such that computation of the Hough transform is distributed among the processor of the plurality of processors in accordance with a specified distribution.

14. A method in accordance with claim 12, wherein the transform memory is partitioned into a plurality of Hough transform sub-space memories such that computation of the Hough transform is approximately evenly distributed among the processor of the plurality of processors.

15. A method for identifying a high level feature of an image represented as an input array of pixel values, comprising:

normalizing the input array of pixel values;

pre-processing the array of normalized pixel values to provide an array of data values;

segmenting the array of data values into one or more regions of interest;

identifying low level features in the array of data values;

dynamically partitioning the transform space of a Hough transform into a plurality of sub-spaces, each sub-space configured to store a plurality of elements of the Hough transform, such that computation of the Hough transform is distributed among a processor of a plurality of processors in accordance with a specified distribution;

calculating, in parallel using one processor for each sub-space, the Hough transform of the one or more regions of interest in the plurality of sub-spaces;

searching the Hough transform space to identify the high level feature of the image; and

outputting parameters to specify the high level feature of the image.

16. A method in accordance with claim 15, wherein identifying low level features in the array of data values comprises detecting edges of objects in the image.

17. A method in accordance with claim 15, wherein the high level feature is an eye position defined by the location of an iris with respect to an eyelid.

18. A method for identifying a high level feature of an image represented as an input array of pixel values, comprising:

normalizing the input array of pixel values;

pre-processing the array of normalized pixel values to provide an array of data values;

segmenting the array of data values into one or more regions of interest;

identifying low level features in the array of data values;

partitioning the transform space of a Hough transform into a plurality of sub-spaces, each sub-space configured to store a plurality of elements of the Hough transform

calculating, in parallel using one processor for each sub-space, the Hough transform of the one or more regions of interest in the plurality of sub-spaces;

searching the Hough transform space to identify the high level feature of the image; and

outputting parameters to specify the high level feature of the image, wherein the array of pixel values define a video frame, the method further comprising;

post-processing the identified high level feature to check for consistency between adjacent video frames.

19. A system for computing a Hough transform comprising:

a plurality of processing means, capable of parallel operation, each operable to calculate a sub-set of elements of a Hough transform;

a plurality of sub-space storage means, each associated with a processing means of the plurality of processing means and operable to store a subset of elements of the Hough transform;

a means for distributing a pixel location value to each processing means of the plurality of processing means; and

a means for outputting a result dependent upon the elements of the Hough transform,

wherein the Hough transform utilizes a curve parameterized by the equation s(x,p)=0, where p is a parameter vector in the transform space, x is a position vector in the data array, and s is a function and wherein the data value at position x_i is used to update transform parameters p satisfying the equation s(x_i,p)=0.

20. A system in accordance with claim 19, further comprising a post-processing means for searching the elements of the Hough transform to detect the largest transform elements.

21. A system in accordance with claim 19, wherein the plurality of sub-space storage means comprises non-overlapping regions of a memory.

22. A system in accordance with claim 21, wherein the non-overlapping regions of a memory are allocated dynamically.

23. A Hough transform method for tracking eye movements, comprising:

receiving a video frame comprising an array of first data values;

preprocessing the array of first data values to provide a plurality of second data values;

calculating a Hough transform of the plurality of second data values for elliptical primitive curves;

identifying eye positions by detecting ellipses using the Hough transform; and

identifying iris positions by detecting circles using the Hough transform of elliptical primitive curves;

wherein calculating a Hough transform of the plurality of second data values comprises;

initializing a Hough transform memory;

retrieving a data value from the plurality of second data values;

passing the data value to a plurality of processors;

associating each processor of the plurality of processors with a Hough transform sub-space memory of the Hough transform memory; and

each processor of the plurality of processors updating elements of the Hough transform stored in the associated Hough transform sub-space memory dependent upon the data value.

24. A method in accordance with claim 23, wherein associating each processor of the plurality of processors with a Hough transform sub-space memory of the Hough transform memory comprises dynamically allocating a Hough transform sub-space memory to each processor to maintain a substantially equal distribution of computation between the plurality of processors.

25. A method in accordance with claim 23, wherein preprocessing the array of first data values to provide a plurality of second data values comprises:

normalizing the array of first data values to provide an array of normalized data values;

filtering the array of normalized data values to provide an array of filtered data values;

segmenting the array of filtered data values to obtain one or more regions of interest; and

extracting low level features in the one or more regions of interest.

26. A method in accordance with claim 23, wherein identifying eye positions and identifying iris positions further comprises checking for consistency with adjacent video frames.