Hough Transform by $\rho$-$\theta$ parameterization

The transformation function is given by $F_{\rho}(x, y ; \theta) = x \cos\theta + y \sin\theta$as (4). Let $\theta$ and $\rho$ correspond to u and v respectively. The angle between x-axis and the line is in the range $[-\pi/4, \pi/4)$. $\theta$ denotes the angle between x-axis and the normal of the line. Therefore, $\theta$ is defined in the range $\pi/4 \leq \theta < 3\pi/4$.

The maximum quantization error is given by

$$q_{\rho}(\theta) = \frac{\Delta s}{2} \cdot \vert\sin \theta\vert\ .$$ (27)

From (11) and (12), if $\pi/4\leq \theta<\pi/2$, we have $c_{max}(\theta) = - x_{min} \sin\theta + y_{max} \cos\theta$ and $c_{min}(\theta) = - x_{max} \sin\theta + y_{min} \cos\theta$, where x_max, y_max, x_min, y_min denote the maximum and the minimum values of the coordinates x,y of discrete sampling points on the same line. In the same way, we can calculate $c_{max}(\theta)$ and $c_{min}(\theta)$ for $\pi/2\leq\theta <3\pi/4$. As a result, we have

$$c_{max}(\theta) - c_{min}(\theta) = l_x \sin\theta + l_y \vert\cos\theta\vert \ ,$$ (28)

where l_x = x_max - x_min and l_y = y_max - y_min. Moreover, if the length of a line segment is given by l, we have $l_x = l\sin\theta$ and $l_y=l\cos\theta$, and then,

$$c_{max}(\theta) - c_{min}(\theta) = l$$ (29)

can be obtained.

$2q_{\rho}(\theta)$ has the minimum value $\Delta s/\sqrt{2}$ at $\theta=\pi/4$. Since the image is square, the length of the line, l, has the maximum value $2\sqrt{2}N$at the same value of $\theta$. Hence, the upper bound of the sampling interval is given as follows.

Upper Bound of the Sampling Interval for $\rho$-$\theta$ parameterization:

$$\overline{\Delta \theta} = \min_{\theta } \frac{4q_{\rho}(\t... ...{max}(\theta) -c_{min}(\theta)} \ = \ \frac{\Delta s}{2N} \ .$$ (30)

We have another interesting coincidence between our discussion and a previous work. Van Veen et al. derived the boundary between the oversampling and the subsampling of the quantization of parameter space [3]. The boundary is given by

$$\Delta\rho \simeq l\cdot \sin(\frac{\Delta\theta}{2}) \ ,$$ (31)

where l denotes the length of the longest line segments and $\Delta\rho$ denotes the sampling interval of the parameter $\rho$. The sampling interval of the image is assumed to be $\Delta s=1$. Assuming $\Delta\theta$ is very small, we have

$$\Delta\rho \simeq l\cdot \sin(\frac{\Delta\theta}{2}) \ .$$ (32)

When $\Delta\rho$ is given, the above equation gives the condition which $\Delta\theta$ must satisfy.

The distance between two parallel lines adjacent each other in the discrete image is $\Delta s \cdot\max\{\vert\cos(\theta)\vert, \vert\sin(\theta)\vert\}$measured perpendicular to the lines. It is quite natural that the upper bound of the sampling interval of $\rho$ is given by $\overline{\Delta\rho}=\Delta s/\sqrt{2}$. Here let us suppose the parameter space is quantized by $\Delta\rho=\overline{\Delta\rho}$. Note that this sampling interval will provide us with the Hough Transform which requires less memory. The length of the longest line segment in the square image is given by $l=2\sqrt{2}N$. Substituting the sampling interval and the line length into (32), we obtain

$$\Delta\theta\simeq \frac{\Delta s}{2N}=\frac{1}{2N} \ .$$ (33)

Now we have the same sampling interval as (30).