Selecting gradient orientation for Generalized Hough Transform while scaling and rotation is present

Question

I am using this link to study Generalized Hough Transform. I will explain it briefly. In order to detect a shape, an R-table is created for the shape with $\phi$ indicating gradient orientation for points on the edge of the shape. Then $(r, \beta)$ is used to indicate the vector from each of these points to the centroid in the shape. While detecting the shape, we will first find all the edge points and their gradient orientation $(\phi)$. Based on this $\phi$, $(r, \beta)$ values are used to calculate centroid points. Based on the votes on centroid points (and R table), the shape can be detected.

My question is related to rotation of the shape which is explained towards the end. If the shape is rotated by $\theta$, then the gradient orientation $(\phi)$ for a given edge point changes. So, shouldn't we do either one of the following:

1) Rotate all the $\phi$ values in R table by $\theta$?

OR

2) Rotate gradient vector by $(-\theta)$ and then calculate $\phi$ for the edge point?

Answer 1

I was having the same issue as you had: most resources I found online seem to miss this issue about the rotating gradient orientation, as did A_A in their answer (which to be fair is very clear in the other aspects of the GHT).

I found that the original paper by Ballard addresses this very thing in section 4.5 (the emphasis is mine):

We denote a particular $R$-table for a shape $S$ by $R(\phi)$. $R$ can be viewed as a multiply-vector-valued function. It is easy to see that simple transformations to this table will allow it to detect scaled or rotated instances of the same shape.

For example if the shape is scaled by $s$ and this transformation is denoted by $T_s$, then $T_s[R(\phi)] = sR(\phi)$ i.e.,all the vectors are scaled by $s$. Also, if the object is rotated by $\theta$ and this transformation is denoted by $T_\theta$, then $T_\theta[R(\phi)] = Rot\{R[(\phi-\theta)\ (mod\ 2\pi)],\ \theta\}$ i.e., all the indices are incremented by $-\theta$ modulo $2\pi$, the appropriate vectors $r$ are found, and then they are rotated by $\theta$.

So I am pretty sure that your option (1) is a correct way of going about this: when varying $\theta$ you index an offset-by-$\theta$ entry on the $R$-table.

A disclaimer is in order: I am no expert on the matter. In any case, it seems pretty clear to me from the paper, but perhaps I'm missing some invariance which lets us ignore the offset. Anyway, hope this helps.

Edit: Indeed, I just finished implementing the GHT and it won't work properly without the $\theta$-offset.

This first image shows the result without applying the offset before entering the table (the red crosses on the left indicate detected centroids corresponding with the object on the right). As you can see, the rotated object is not detected (the false positive on the lower-left side disappears if I use a stricter threshold (i.e, minimum amount of votes)).

The following results from offsetting by $-\theta$ before retrieving the $R$-table entries (and is also resistant to a higher threshold, meaning it's not just a translation of the false positive):

Answer 2

If the shape is rotated by $\theta$, then the gradient orientation ($\phi$) for a given edge point changes. So, shouldn't we do either one of the following:

1. Rotate all the ϕ values in R table by θ?

OR

2. Rotate gradient vector by ($-\theta$) and then calculate $\phi$ for the edge point?

The generalised Hough transform does #1 implicitly by the $S, \theta$ parameters when accumulating.

Note here that usually, you don't really know that the extracted contour has been rotated by some angle (let's call it $\alpha$). You usually are trying to find that angle.

During the preparation stage, you construct the "template", $\phi$. This quantises the circumference of a circle that encloses the shape to be recognised into $k$ levels ($k$ distinct angles). Then, for each $k^{th}$ level, you look at the contours that make up your template image at the $\phi_k$ bearing and note down their $(r, \beta)$. The $(r,\beta)$ is nothing more than the polar coordinates of an element of your template image's contour that is oriented at angle $\phi_k$.

If you wanted to recognise a simple circle, then you would only have one column of $(r, \beta)$. If that circle enclosed another, smaller circle (imagine for example a road sign), then at some orientation $\phi_k$ you would have more than one "edges" and therefore more than one columns of $(r, \beta)$ data.

Now, during the recognition phase, you use the $\angle G$ to lookup an entry in $\phi$. Once you have found that entry, your take that entry's $(r, \beta)$ and use them to find the "right Hough counter cell" $H(x_c,y_c)$ and increment it.

The point here is that the $(r, \beta)$ are calculated with respect to the centroid and it is that centroid $x_c,y_c$ that accumulates quickly in $H$. When the shape is matching, it means that your test image contains a lot of $\angle G$ entries that have resulted in the $H(x_c,y_c)$ counter getting a very high value.

The next step is to be able to recognise the template $\phi$ irrespectively of scale $S$ and orientation $\theta$.

Notice here that if you were to take the Hough transform of the template with its centroid translated at $(0,0)$, then different rotations $\theta_1, \theta_2, \theta_3, \ldots$ are basically cyclic lateral shifts in the Hough space (where the $x$ dimension now corresponds to bearing $\theta$) and different (uniform) scalings $S_1, S_2, S_3, \ldots$ correspond to different "arc amplitudes" (in the $y$ direction that corresponds to distance from origin).

So, the template doesn't really change, all that you do is consider different scalings and rotations at the same time. From another point of view it is as if you were running $N$ different Hough transforms where you scale / rotate the original image by $(S,\theta)_n$. You would produce one $H$ for every $(S, \theta)_n$ such as $\left(1,0\right), \left(1, \frac{\pi}{4}\right), \left(1, \frac{\pi}{2}\right), \left(1, \frac{3 \pi}{4}\right), \left(1, \pi\right), \left(0.5,0\right), \left(0.5, \frac{\pi}{4} \right), \ldots, \left(0.25, 0 \right), \ldots$. In this case here we are looking for 4 orientations at scale 1, 0.5, 0.25 and so on.

But, rotating and scaling the original image can be costly because there are definitely more pixels in an image than elements in the $k$ level quantised periphery of the curve you are trying to find.

For this reason, instead of rotating the original image and running parallel Hough transforms, you simply scale and rotate $\phi$ but you do it on the fly. Instead of modifying the $\phi$ you just introduce $S, \theta$. $S$ modulates your $r$ (the radius of the template) and $\theta$ offsets your $\beta$ (the bearing of your template).

In this way, you produce $N$ matrices $H(x,y)$, one for each $(S, \theta)_n$ you would like to consider. Again, the $x_c, y_c$ counter that crosses a certain threshold marks the location of the recognised contour but in addition now you can also infer at which scale and rotation by fixing the $(S, \theta)$ pair.

Hope this helps.