Method and system for parallel processing of Hough transform computations
AssigneeMotorola, Inc.
InventorsMagdi A. Mohamed, Irfan Nasir
Life of this patent
Estimating the term…
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.
Claims26
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 xi 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 xi from the first memory interface and update Hough transform values of parameters p satisfying the equation s(xi,p)=0 in the associated memory of the plurality of Hough transform sub-space memories.
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 xi is used to update transform parameters p satisfying the equation s(xi,p)=0.
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.
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.
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 xi is used to update transform parameters p satisfying the equation s(xi,p)=0.
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.
Dependencies are inferred from the claim text.