Feature extraction by shape matching - Feature Extraction and Image Processing - page 213

code is based in the implementation presented in Code 5.11 . We use the value of β defined
in Equation 5.89 to index the table passed as a parameter to the function GHTInv . The data
k recovered from the table is used to compute the slope of the angle defined in Equation
5.97. This is the slope of the line of votes traced in the accumulators.
Figure 5.24 shows the accumulator obtained by the implementation of Code 5.13 . Figure
5.24 (a) shows the template used in this example. This template was used to construct the
R-Table in Code 5.12. The R-table was used to accumulate evidence when searching for
the piece of the puzzle in the image in Figure 5.24 (b). Figure 5.24 (c) shows the result of
the evidence gathering process. We can observe a peak at the location of the object.
However, this accumulator contains significant noise. The noise is produced since rotation
and scale change the value of the computed gradient. Thus, the line of votes is only an
approximation. Another problem is that pairs of points ω i and ω j might not be found in an
image, thus the technique is more sensitive to occlusion and noise than the GHT.

(a) Edge template (b) Image (c) Accumulator

Figure 5.24 Applying the invariant GHT

5.6 Other extensions to the HT

The motivation for extending the HT is clear: keep the performance , but improve the speed .
There are other approaches to reduce the computational load of the HT. These approaches
aim to improve speed and reduce memory by focusing on smaller regions of the accumulator
space. These approaches have included: the Fast HT (Li, 1986) which successively splits
the accumulator space into quadrants and continues to study the quadrant with most evidence;
the Adaptive HT (Illingworth, 1987) which uses a fixed accumulator size to iteratively
focus onto potential maxima in the accumulator space; and the Randomised HT (Xu, 1990)
which uses a random search of the accumulator space; and pyramidal techniques. One
main problem with techniques which do not search the full accumulator space, but a
reduced version to save speed, is that the wrong shape can be extracted (Princen, 1989), a
problem known as phantom shape location . These approaches can also be used (with some
variation) to improve speed of performance in template matching. There have been many
approaches aimed to improve performance of the HT and of the GHT.
Alternative approaches to the GHT include two Fuzzy HTs: (Philip, 1991) which (Sonka,
1994) includes uncertainty of the perimeter points within a GHT structure and (Han, 1994)
which approximately fits a shape but which requires application-specific specification of