Advanced Hough Transform Implementations

ADVANCED HOUGH TRANSFORM IMPLEMENTATIONS

C.M. Brown, M.B. Curtiss, and D.B. Sher Computer Science Department, University of Rochester Rochester, NY 14627 U.SA.

(negative) votes against parame~ers with which the feature is inconsistent, as well as (positive) votes for parameters with which it is consistent. The negative votes can cancel off-peak positive votes. Compl~mentary Hough sharpens peaks and reduces sidelobe bias and variance.

C. Space Efficiency? Cache Hough

Problem: Multi-dimensional quantized parameter spaces are most straightforwardly impl~mented as arrays which grow impractically large as th~u dimension (the number of parameters) increases. Solullons: One solullon is the use of dynamically quantized parameter space (O'Rourke, 1981; Sloan, 1981]. The solution explored here is Cache Hough: Accumulate vote tallies m a content· addressable cache (in hardware) or hash table (m software) [Brown and Sher, 1982a; 1982b]. The ~bstract problem is that of estimating the mode(s) of a distribullon using fixed memory. Cache H?ugh IS a promising technique suitable for hardware Implementallon.

II. Results: Synthetic Data

A. Complementary Hough Performance

What fpsf for complementary Hough maximizes peak delectability and minimizes bias? All the results of this section arise from synthesized versions of Clfcle detecllon for a constant radius, but the results are suggestive of general principles. In every case, the. circumferential feature points in the input "image" contam no duecllonal information; it is as if they were generated by a rotationally symmetric feature detector. This means that the fpsf in the regular Hough parameter space of cucle centers is a complete circle of unit weight votes (each edge feature votes for a set of centers at all locations a radius distance away). The fpsfs for complementary Hough are circles of unit-weight votes with neighbori~g concentric circles of negative votes. The first graph (Fig. 1) documents the search for the best complementary Hough fpsf. The data points correspond to fpsfs with the indicated negative surrounds. The fpsf with a circle of ones surrounded on both sides by -112's was used for all the remaining work reported in this section.

Complementary Hough keeps the mean background near zero with small biases magnified by the contributio~s of many noise features. Ideally, peak height is proportional to amount of evidence; complementary Hough achieve this. The graph of Fig. 2 shows one measure of regular Hough and complementary Hough performance in seven different imaging situations, getting

Abstract

In the Hough transform, a feature in an input sp_ace I votes for parameters in a transform space P with which It is compatible. If it also uses negative votes to vote agai~st parameters with which it is incompatible, background bias and inherent noise in P can be reduced and peaks sharpened.

In the usual Hough transform implementation. an array is used to accumulate votes, raising the problem that the space requirement increases exponentially with the number of parameters. Accumulation in a fixed-size content-addressable cache (or hash table) may provide a solution.

I. Definitions, Problems, Solutions

A. Hough Transform as Voting and Imaging

Considered as a voting process, the Hough transform maps features of a phenomenon in an input space I to sets of votes in the parameter space P. The parameter vectors receivi11g the most votes describe instances of the phenomenon explaining the most evidence. Ideapy, the Hough transform maps a phenomenon mto a set of votes that is a delta function in parameter space: the votes are unanimous. Usually the votes are more or less spread out, since several phenomena might generate a feature. Call the pattern of votes arising from a feature its feature point spread function (fpsf), and the superposition of all fpsfs from a phenomenon its parameter point_ spread function (ppsf) [Brown, 1983]. A ppsf usually consists of a peak of votes at the correct parameter vector surrounded by sidelobes of incorrect votes.

B. Inherent. Noise and Bias? Complementary Hough

Problem: When the input space contains multiple instances close together, sidelobes from one instance can overlap the peak from another, adding both variation and bias to the peak height. Even in single-instance noiseless inputs, the near-peak votes can spread the peak. Solution: In the Complementary Hough transform, the fpsf contains

The preparation of this paper was supported in part by the Office of Naval Research under Grants N00014-80-C0197 and N00014-82-K-0193, and the Defense Advanced Research Projects Agency under Grant N00014-78-C0164.

progressively more complex and _noisy: SNR3 indicates delectability by global thresholdmg (It IS a multiple­ instance version of the measure used below to quantify performance of cache Hough (Section llB}).

NOISELESS PARAI'£TER POINT SPREAD FUNCTion

.Figure 2. SNR3. SNR3 measures peak detectability when simple thresholding is the detection criterion. SNR3 is the average peak height divided by the maximum off­ peak height. This is a multiple-instance version of the measure used for the cache-based Hough study of Section liB.

B. Cache Hough Performance

We created synthetic phenomenon instances ("shapes") of controllable size, number, and location, embedded them in controllable amounts of noise features, and scanned the resulting images in several ways. Each time a feature was encountered, a vote burst (fpsf) of controllable size was emitted sequentially into a cache whose length and cache-flushing strategy were were also controllable. The hope is . that the parameter vector corresponding to the instance survives in the cache and accumulates the most votes. For technical details see [Brown and Sher, 1982b]. Comprehensive results appear in [Brown and Sher, 1982a].

The form of synthetic images and fpsfs is dictated by theory in [Brown, 1983]. The size of the instances and psfs and number of noise features in the image determine how many votes are sent to the cache. The scanning methods determine the order of sending. The cach'e length and flushing algorithm determine what vote tallies survive. We used four cache lengths (32, 64, 128, infinite). The infinite cache is equivalent to an accumulator array. Our instances had horizontal extent of 1, 2, or 3 and vertical extent of 11. The fpsfs were of 3, 9, and 15 votes. There was only one instance per image. Regular and Complementary Hough were used. Images were scanned five ways (Left to Right within Top to Bottom, Top to Bottom within Left to Right, Random with ~eplacement, Random without Replacement, and Left to Right within Random Scanline). One flushing method eliminated tallies below a threshold, the other eliminated a fixed fraction of tallies, ch.osen at random, below a larger threshold.

The results of these experiments yielded statistics such as the histograms of Figs. 3 and 4, which display a ratio

(votes for vector describing instance)

max (votes for other vectors in cache)

SNR3 = ----------------------------------------------------

If SNR3 > l, the correct parameter vector tallied a plurality of votes and woul~ be detected as the largest entry in the cache. Otherwise, an Incorrect parameter tallied at least as many (see also Fig. 2).

III. Results: Real Data

Our Hough Transform software laboratory allows flexible expenmentation and comparison between methods. The cache accumulator module can be parameterized to provide finite or "infinite" length and various flushing methods. Fig. 5 shows sample output.

IV. Discussion

Complementary Hough reduces inherent noise and bias and sharpens peaks at the cost of increased voting effort, depending on the implementation. In a naive implementation the cost might be strictly proportional to the number of votes, but in an implementation with hard­ wired voting patterns there is no extra cost. Antialiasing is of some benefit, but also may affect voting cost.

Complementary Hough is most effective with dense voting that maximizes the superimposition of cancelling votes. If evidence is sparse, fpsfs and votes are sparse in the accumulator and little cancellation takes place; similarly if fpsfs are sparse. In the example of Section Ill, positive votes occur in line$ through 3-space, and each positive vote is surrounded by only six (of a possible 1.6 in 3-D) nearest-neighbor negative votes, resulting in less than optimal cancellation. If each feature votes for exactly one parameter vector (the fpsf is a single point), then complementary Hough degenerates to a linear enhance­ ment operation: a central positive vote surrounded by a cloud of complementary ones is like a Laplacian operator.

In complementary Hough, sidelobes should cancel while the central peak accumulates positive votes. Feature perturbation error arises from quantization effects [Shapiro and Iannino, 1979]; e.g., the angle computed for an edge element is only approximate. Such error spreads the locus of the peak and superimposes complementary votes on it, degrading complementary Hough perform­ ance. Thus the results of Section III represent a severe test for the complementary Hough, and it is gratifying that it performs slightly better than regular Hough.

The remainder of the discussion concerns cache Hough. Finite caches of adequate size seem to be practical r)

Hough accumulators, not significantly worse than accumulator arrays. The results show a graceful and qualitatively predictable degradation of performance as noise and fpsf length increase and cache length decreases. Cache lengths of a few percent of the total number of votes seem adequate, but we do not yet know how this figure grows with parameter dimensionality.

The random (with replacement) scan was uniformly significantly worse in all cases than other methods. The random (without replacement) does not seem significantly better than nonrandom scans. Even in 30% noise, the Top to Bottom within Left to Right scanning method was not better than the Left to Right within Top to Bottom. This indicates (with our vertical instances) that successive bursts of votes (fpsfs) containing votes for the "true parameters" are not enough . to help the peak establish itself. Probably the noise that arrives before the instance and the flush algorithm dominate the peak-establishment process. Thus the results are fairly insensitive to scanning method, as long as each input space point is considered once.

In good conditions (short fpsf, low noise, large instances), average cache complementary Hough performance is reliably markedly better than cache regular Hough. However, as conditions get worse, their average performance is approximately the same. Several of the histograms show a significant bimodality with one peak at 0. This indicates that the "true peak" never gets established in a significant number of cases, and that some pre-processing might help dramatically in establishing peaks. One idea is "pair Houghing," in which only parameter vectors that appear in two fpsfs are allowed into the cache. Clearly without such preprocessing the issue is whether peaks are able to survive in the cache, and this depends to a large extent on the Flush algorithm. The Random Below Threshold Flush makes for a significant improvement in (mean peak)/(maximum background)' ratio, and reduces the frequency of occasions on which the correct parameters end up with zero vote weight.

Systematic distortion, occlusion, and feature perturbation pose thorny problems for cache Hough. An important topic of current work is to assess the performance of cache Hough schemes in more stringent noise conditions and to develop means of improving such performance.

Hierarchical caches can incorporate a form of "geometric locality" that is lost in simple content­ addressable caches. Natural nush algorithms for a single­ level cache are based strictly on tallies. Multiple caches in a resolution pyramid, maintained in parallel, can be used to restrict flushing to coherent localities in the input space. This idea is another topic of current research.