Image processing method and apparatus for extracting lines from an image by using the Hough transform

• US 5,832,138 A
• Filed: 03/01/1995
• Issued: 11/03/1998
• Est. Priority Date: 03/07/1994
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Ogura, Takeshi, Nakanishi, Mamoru
• Primary Examiner(s): BOST, DWAYNE D
• Assistant Examiner(s): Johnson, Brian L.
• Application Number:
  US08/396,700
• Time in Patent Office: 1,343 Days
• Field of Search: 382/199, 382/202, 382/203, 382/281, 382/287, 382/104, 382/240, 382/266, 382/200, 382/289, 382/295, 382/296, 382/141, 382/143, 382/151, 382/153, 364/424.033, 364/424.07, 364/725, 348/135, 348/120, 358/426
• US Class Current: 382/281
• CPC Class Codes: G06F 17/14 Fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms for correlation function computation G06F17/156; spectrum analysers G01R23/16
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

An image processing apparatus for extracting lines from an image using the Hough transform. A processor element is assigned to each quantization point in a Hough space. Each processor element calculates, for each scanning line of the image, intersections of the scanning line and the line corresponding to this processor element once per scanning line. A black pixel (a Hough transform object point) on the scanning line is also obtained sequentially. The coordinate values of the intersection are compared with those of the Hough transform object point, and when they agree, voting to a ballot box memory of the processor element is performed. The voting results become Hough transform data. This makes it possible to implement a high speed Hough transform, and to reduce the size of the apparatus.

Claims

1. An image processing apparatus for extracting a line in an image space by using a Hough transform to map the line from the image space onto one of a plurality of points in a Hough space, said image processing apparatus comprising:

a plurality of processor elements each being respectively assigned to one of a plurality of accumulator cells of the Hough space, each of said plurality of accumulator cells corresponding to a respective one of the plurality of points in the Hough space; and

means for sequentially reading image space pixels on a scanning line in the image space, the sequential reading means determining whether or not a pixel being read from among said image space pixels is a Hough transform object point having a value other than zero, the sequential reading means obtaining coordinate values of the image space pixel when the pixel is the Hough transform object point, the sequential reading means supplying the coordinate values of the image space pixel to respective ones of said plurality of processor elements;

wherein each of said plurality of processor elements includes;

a ballot box memory for storing a number of votes;

means for obtaining, for each of a plurality of scanning lines, coordinate values of an intersection of a respective scanning line and a line in image space corresponding to the plurality of processor elements;

means for comparing coordinate values of said Hough transform object point with the coordinate values of said intersection, and storing data as a comparison result as to whether there is coincidence or non-coincidence between the Hough transform object point coordinate values and the intersection coordinate values; and

means for providing a vote to said ballot box memory when the Hough transform object point coordinate values are coincident with the intersection coordinate values, the vote being provided after the comparison result has been obtained for each pixel on said scanning line;

wherein after each of the plurality of scanning lines of the image space have been processed, a line is extracted which corresponds to the processor element whose ballot box memory has a maximum number of votes.

2. The image processing apparatus as defined by claim 1, wherein said plurality of processor elements are provided in a single associative memory having a plurality of words;

wherein the single associative memory comprises a random access memory and determines whether retrieval data provided thereto is coincident with contents stored in at least one of the plurality of words, the single associative memory selecting a word from memory which is coincident with the retrieval data, the single associative memory writing data into at least one selected word in parallel, and providing a parallel calculation function;

at least one word of the single associative memory corresponding to a respective one of said plurality of processor elements each of which corresponds to at least one point of the Hough space; and

wherein said at least one word includes a plurality of memory cells which constitute the ballot box memories and which store data when there is coincidence between the retrieval data and the stored contents, and for obtaining coordinate values of an intersection.

3. An image processing apparatus for extracting a line in an image space by using a Hough transform to map a line from the image space represented by ρ

=xcosθ

+ysinθ

onto a point (ρ

, θ

) in Hough space (where ρ

is a length of a chord from an origin of the image space perpendicular to the line, and θ

is an angle of the chord from a positive X axis in image space), said apparatus comprising;

a plurality of processor elements respectively corresponding to a plurality of Hough quantization points in a first section of the Hough space, the Hough space being divided into the first section (0≦

θ

<

π

/4), a second section (π

/4≦

θ

<

π

/2), a third section (π

/2≦

θ

<

3π

/4), and a fourth section (3π

/4≦

θ

<

π

) in accordance with a value of θ

,

means for sequentially reading pixels on a first scanning line along an X-axis in the image space, and determining whether one pixel being read from among said pixels along said X-axis is a Hough transform object point having a value other than zero, and, when the pixel along said X-axis is the Hough transform object point, obtaining an X-axis coordinate value of `m` and a value of `-m`, obtained by inverting a sign of the coordinate value of `m`, and supplying the X-axis coordinate values to respective ones of said plurality of processor elements;

means for sequentially reading pixels on a second scanning line along a Y-axis in the image space, and determining whether one pixel being read from among said pixels along said Y-axis is a Hough transform object point having a value other than zero, and, when the pixel along said Y-axis is the Hough transform object point, obtaining a Y-axis coordinate value of `n` and a value of `-n`, by inverting a sign of the coordinate value `n`, and supplying the Y-axis coordinate values to respective ones of said plurality of processor elements;

each of the plurality of processor elements (i, j) including four Hough quantization ballot box memories having a first ballot box (ρ

i, θ

j), a second ballot box (ρ

i, (π

/2)-θ

j), a third ballot box (-ρ

i, (π

/2)+θ

j) and a fourth ballot box (ρ

i, π

-θ

j) wherein 0≦

θ

j<

π

/4;

means for calculating coordinate values of an intersection of a line for each of said plurality of processor elements and a scanning line defined by y=k;

first memory means for comparing and determining coincidence between the coordinate value `m` of the Hough transform object point and the intersection coordinate values, and storing the result of the determination as a first comparison result;

fourth memory means for comparing and determining coincidence between the value `-m` and the intersection coordinate values, and storing the result of the determination as a fourth comparison result;

second memory means for comparing and determining coincidence between the coordinate value `n` of said Hough transform object point and the intersection coordinate values, and storing the result of the determination as a second comparison result;

third memory means for comparing and determining coincidence between the value `-n` and the intersection coordinate values, and storing the result of the determination as a third comparison result; and

means for voting to a first ballot box memory when coincidence is determined by and stored in said first memory means, voting to a second ballot box memory when coincidence is determined by and stored in said second memory means, voting to a third ballot box memory when coincidence is determined by and stored in said third memory means, and voting to a fourth ballot box memory when coincidence is determined by and stored in said fourth memory means, said voting being performed after the comparison results have been obtained for all pixels on the first and second scanning lines; and

wherein a line is extracted which corresponds to a processor element from among said plurality of processor elements whose ballot box memory has a maximum number of votes.

4. The image processing apparatus as defined by claim 3, wherein said plurality of processor elements are provided in a single associative memory having a plurality of words;

wherein the single associative memory comprises a random access memory and determines whether retrieval data provided thereto is coincident with contents stored in at least one of the plurality of words, the single associative memory selecting a word therefrom which is coincident with the retrieval data, the single associative memory writing data into at least one selected word in parallel, and providing a parallel calculation function;

wherein plural sets of words of said associative memory are used as said plurality of processor elements each of which corresponds to four quantization points in the Hough space; and

wherein each of said plural sets of words includes four ballot box memory cells which function as said first ballot box memory, said second ballot box memory, said third ballot box memory and said fourth ballot box memory, each of said plural sets of words including four comparison result memory cells for respectively storing the first, second, third and fourth comparison results, and one memory cell for storing, retrieving and calculating the coordinate values of the intersection.

5. An image processing method for extracting a line in an image space by using a Hough transform to map a line from the image space onto one of a plurality of points in a Hough space, said method utilizing a plurality of processor elements respectively assigned to a respective one of a plurality of accumulator cells of the Hough space, each of said plurality of accumulator cells corresponding to a respective one of the plurality of points in the Hough space, the method comprising the steps of:

sequentially reading image space pixels on a scanning line in the image space;

determining whether or not a pixel being read from among said image space pixels is a Hough transform object point having a value other than zero;

obtaining coordinate values of the image space pixel when the pixel is the Hough transform object point;

supplying the coordinate values of the image space pixel to respective ones of said plurality of processor elements;

obtaining, in each of the plurality of processor elements, for each of a plurality of scanning lines, coordinate values of an intersection of a respective scanning line and a line in image space corresponding to the plurality of processor elements;

comparing, in each of the plurality of processor elements, the Hough transform object point coordinate values with the intersection coordinate values;

storing, in each of the plurality of processor elements, data as a comparison result as to whether there is coincidence or non-coincidence between the Hough transform object point coordinate values and the intersection coordinate values;

voting, in each of the plurality of processor elements, to a ballot box memory when the Hough transform object point coordinate values are coincident with the intersection coordinate values after the comparison result has been obtained for each pixel on the scanning line; and

extracting after all the scanning lines of the image space have been processed, a line which corresponds to the processor element whose ballot box memory has a maximum number of votes.

6. An image processing method for extracting a line in an image space by using a Hough transform to map a line from the image space as represented by ρ

=xcosθ

+ysinθ

onto a point (ρ

, θ

) in Hough space (where ρ

is a length of a chord from an origin of the image space perpendicular to the line, and θ

is an angle of the chord from a positive X axis in the image space), said method utilizing a plurality of processor elements respectively corresponding to a plurality of Hough quantization points in a first section of Hough space, the Hough space being divided into the first section (0≦

θ

<

π

/4), a second section (π

/4≦

θ

<

π

/2), a third section (π

/2≦

θ

<

3π

/4), and a fourth section (3π

/4≦

θ

<

π

) in accordance with a value of θ

, each of the plurality of processor elements (i, j) including four Hough quantization ballot box memories having a first ballot box (ρ

i, θ

j), a second ballot box (ρ

i, (π

/2)-θ

j), a third ballot box (-ρ

i, (π

/2)+θ

j) and a fourth ballot box (ρ

i, π

-θ

j) wherein 0≦

θ

j<

π

/4, the method comprising the steps of;

sequentially reading pixels on a first scanning line along an X-axis in the image space, and determining whether one pixel being read from among said pixels along said X-axis is a Hough transform object point having a value other than zero, and, when the pixel along said X-axis is the Hough transform object point, obtaining an X-axis coordinate value of `m` and a value of `-m`, by inverting a sign of the coordinate value of `m`, and supplying the X-axis coordinate values to respective ones of said plurality of processor elements;

sequentially reading pixels on a second scanning line along a Y-axis in the image space, and determining whether one pixel being read from among said pixels along said Y-axis is a Hough transform object point having a value other than zero, and, when the pixel along said Y-axis is the Hough transform object point, obtaining a Y-axis coordinate value of `n` and a value of `-n` by inverting a sign of the coordinate value `n`, and supplying the Y-axis coordinate values to respective ones of said plurality of processor elements;

calculating coordinate values of an intersection of a line for each of said plurality of processor elements and a scanning line defined by y=k;

comparing and determining in a first memory, coincidence between a coordinate value `m` of the Hough transform object point and the coordinate values of the intersection, and storing the result of the determination as a first comparison result;

comparing and determining in a fourth memory, coincidence between a value `-m` and the intersection coordinate values, and storing the result of the determination as a fourth comparison result;

comparing and determining in a second memory, coincidence between a coordinate value `n` of the Hough transform object point and the intersection coordinate values, and storing the result of the determination as a second comparison result;

comparing and determining in a third memory, coincidence between a value `-n` and the intersection coordinate values, and storing the result of the determination as a third comparison result; and

voting to a first ballot box memory when coincidence is determined by and stored in said first memory, voting to a second ballot box memory when coincidence is determined by and stored in said second memory, voting to a third ballot box memory when coincidence is determined by and stored in said third memory, and voting to a fourth ballot box memory when coincidence is determined by and stored in said fourth memory, said voting being performed after the comparison results have been obtained for all pixels on the first and second scanning lines; and

extracting a line which corresponds to a processor element from among said plurality of processor elements whose ballot box memory has a maximum number of votes.