Selecting gradient orientation for Generalized Hough Transform while scaling and rotation is present
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:
  
  
  Rotate all the ϕ values in R table by θ?
  
  
  OR
  
  
  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.