Difference between Generalized Hough Transform and Cross-correlation Feature Matching

Question

I've been taking the Udacity Computer Vision Course, and one thing that has confused me so far is how the Generalized Hough Transform is any different from feature matching on an edge image using cross-correlation.

As I understand, the Generalized Hough Transform requires you to know the size, shape, and orientation of the object you are looking for, and using the edges of that object, parameterizes that object based on an R-table. I know it can be generalized to size and orientation, but that it is also costly to do. For now, let's say you choose not to generalize.

Given these constraints, couldn't you just do cross-correlation feature matching, using the same edge image the Hough Transform would be trained by?

What's the difference? Is there any reason Hough would perform better in this case, without generalizing to size and orientation?

Answer 1

There is a big difference: The Hough Transform maps the input space to a parameter space, where the search takes place. This way, the run-time of the algorithm is independent of the degree of the spatial search space. Correlation based methods are rather more brute force in that sense as they search explicitly for all transformations. Of course, there are ways to make that search more efficiently.

The Hough transform can easily be made rotation invariant at almost no cost. This generalizes to other types of linear transformations as long as the accumulator space doesn't over-grow as Hough tends to trade-off computational efficiency to storage.

Cross-correlation type methods are less memory intensive and are easier to extend to arbitrary transformations. Moreover, they allow for explicit control of the distance metric, giving rise to more creativity. Yet, they generally tend to be slow, unless implemented carefully. This is because they require a search over the whole input space for all (or part of) transformation space. Due to this this comparison paper, a well-implemented correlation approach with an efficient distance metric can outperform a Hough based one. Thus, we can say that many approximations to correlation methods can be made but one should make sure that the performance is not degraded.