Dynamically Quantized Spaces for Focusing the Hough Transform

1. THE HOUGH TRANSFORM

The Hough Tramform [7) has developed into a useful image processing technique. It is applicable whenever some set of image patterns P can be described by a finite number of parameters Ut,u1, · · · · u._. Its purpose is to determine the parameters for the patterns in the imqe. Eal:h point (u1, .. . , Ut) in parameter space determines a particular pattern p E P via a function f : f(u 1 · ·· · , u4)-p. The Hough Tramform c:omists of making measurements in the i.rnaF that give evidence for a subset of the patterm P. C:P, am mapping these patterm into the parameter space with the inverse of J : r 1 (P.>.

If thia process of mapping an imqc measurement into a set of points in parameter space is repeated, then those points that actu­ ally c:aresponl to a pattern present in the image will be mapped to (or "hit" or "voted for" [ 13]) most frequently. This property forms the basis of implementations of the technique. The parameter space is represented as a k~nsional aa:umulator array, each cell of which counts the number of times it has been hit by a mapping from the image. The parameter coordinates of the cell that attains the highest count then c:orresponls to the pattern that has the most evidential support from the lmqe measurements. Thus the Hough Transform conwrta a alobal pattern detection problem into a loc:al detection problem: finding a loc:al maximum in the parameter space [13].

This technique has been successfully applied towards finding straight lines [7)[S], circles [9), parabolas [17], ani arbitrary 2D shapes [13)[1] in images, as -ll as for imqe registration [17]; many other applications are possible.

2. DYNAMIC QUANTIZATION

The quantization of the parameter space represented by the acc:umulator array is usually chosen to be uniform: each cell has the same size. Static: non-uniform quantization schemes have been used to emure that each cell is equally likely to be hit [4)[8). But all quantization schemes run into a serious problem: the large amount of storage required for the cells of the accumulator array. This problem bea:Jmes especially acute for high~nsional param­ eter spaces, · where e-ven a coarse quantimtion leads to immense storage requirements. It is to help alleviate this problem that Dynamically ~trlzd ( DQ) Spaces have been proposed [IO)[Il)[l2].

The hJahest dimensionll 1111a1 I lla~~e seen In lite lilelature is the 4dimenslonll llliCe used in 113111 ).

In a DQ Space, cells may split or merge in respoll!l: to the local characteristics of the data. Each cell represents a k­ dimensional rectangular box in the parameter space, am contains a counter that accumulates the number of hits within the bounls of the cell. A cell may be modified in three ways:

• M 1 : Its counter may be lncremenud by being hit by an inverse mapping from the image.
• M2: It may !Jiilt in half across one dimension. creating two new cells.

M l : It may merge with one or more of its immediate neighbors.

The splitting ani merging are guided by two goals:

• G 1 : The count in each cell should represent an equo/ ponlon of the total count o'llll:r all cells in the Space.
• G1 : The hits within each cell should be: unifonn/y distributed throughout the volume of the cell.

This last goal requires that each cell have some knowledge of the distribution of hits within its bounlaries. This is accomplished by associating a k~miomllmba/ance vector (essentially an approxi­ mation to the gradient) with each cell, ani updating it as points fall in the cell.

The above goals lead to the following split ani merge rules: SPLIT RULE: A cell should be split if its count is too large (rela­ tive to the total count), or if its internal imbalance becomes too large. Each of the two new cells resulting from the split receive exactly half of the count of the original cell.

MERGE RULE: A cell should be merged with its neighbor if together their counts are not too large, and the merge will not pro­ duce a highly unbalanced cell. The new cell resulting from the merge is assigned as a count the sum of the counts in the merging participants.

Note that the merge rule is essentially the complement of the split rule. The actual rules in use are considerably more compli­ cated than the above statements indicate; see [10) for details.

3. HIERARCHICAL ORGANIZATION

It is clear from the abo-ve description that the cells must be stOI'ed in a data structure that (a) allows any cell to be aa:essed quickly for incrementing its count, and (b) permits the neighbors of any cell (used in the merge rule) to be: found easily.

A hierarchical organimtion immediately suggests itself, ani in particular, the k-dimemional generalization of the quad am oct tree [16) seems an obvious candidate for the structure. However, their rigid organimtion ani large number of sons per node (r) have led me to use instead the k-11 trees of Bentley [3)[6)[2]. Sloan is currently investigating the quad/oct tree alternati-ve, which he calls a Dynamically Quantizrxl (DQ) Pyramid [lSI.

&ch node of a lc-4 tree resx-1111 a lc-dimelllioDII JeClaDBUiar box. Ewlry node hu ~ twO 10111, which partition it into two smaUer piec:llll. The index ~ the dimenllon Knlll which the box is sJiit !I stored at the noda, alq with an indication of how far Ilona the apliUU. dimemioo. the cut oa:un (it does not have to be at the midpoint).

4. PaOPEtTIES OF DQ SPACES

In the c:uneal implllmemation, polnra are ·p~otted" in pumne­ * llpiCII bJ ( 1) lll:llliUina the appropriate Cllll via a path from the root. (2) lraemenW. the cell's counter, llld (3) firina the aplit or JDKJe rule for the CIIU If applicable, m1 ~ the rules for am'

neighboring cells modified by a rule firing, am so on recursively. The elfect is that a DQ Spare will dynamically reorpnize it!lelf to match the local characteristics of the data. This schetne possesses the following properties:

Foc:M Capa~Ulty: Figure 1 shows a 20 DQ Space containing 500 points that do not display any marked cenual tendency; the result­ ing cells are roughly the same sim. The 500 pOints in Figure 2 , however, cluster arowxl the two points (3,7) am (8,4), am the cell sims adjusted to focus in on thee dusters. The lc-4 tree sup­ porti~ the cells of Figure 2 is depicted in Flaure 3. The splittilll ditnension is i.nlicated at each node, am a siJIIIe diait proportional to the density of counts in each cell is shown at the ISIOCiated ter­ minal node.

Resohltlon Control: The resolution of the Space aan easily be ron­ trolled bJ paratneters that limit the number of cells. The DQ Spaa: tries to achieve its goals within the limits set, am "gracefully degrldes" if the resources allocated are i!Widequate to the task .

DbanalollaUty Redlldlon: If the daJ.a is unifamly distributed 110111 some ditnension, then the DQ Space will tend not to discrim­ inate (i.e., split) along that ditnension <- Figure 4). In effect, the ditnensionality of the spaa: is redumd. This could be espec:ially Important in a high-dimensional space that hu some in~~~~ential ditnensions.

Chanae of Attention: Jn the current impletnelllltion, the count in each cell "fades· with time, so that a moving peak in paratneter apace aan be "trackrd" by the focusing capability of the DQ Space.

5. CURRENT AND FUTURE WORK

DQ Spaces are currently being used for motion detection am analysis [101111121. Some success has been achieved with a vari­ ation of Ullman's "Two Cylinder Experiment" [ 19) usina a 30 parameter space [12).

The complexity of DQ Spaces has rendered thecretic:al analysis difficult. · Currently the interrelationships benw~een the split and merge to1eranDcs am the resolution parameters, which tosethclr c:ontrd the behavior of the ~p~a~, are unclear. One advantqe bf Sl0111's DQ Pyramids is their simplicity relati-w: to DQ Spaces.

' See I I OJ for tho me~~er resa!IS thai ha.,. been oloellnal.

The price for this simplicity is inflexibility: DQ Pyran\ids al-ys allocate equal system resources for each dimension of the parameter space. whereas DQ Spaces can ignore irrele'4nt dimen­ sions. In fact, it is possible for a DQ Space to have different dimensions in different !ICCtions of the SJliiCC, constituting a son of patchwork quilt of different parameter spwes. This corresponds "M:IJ with our intuition that a c~ of oontext may engender a change of rele'4nt features.