Upper Bound of the Scanning Parameter

Let us discuss the separation of two parallel and close lines defined by parameters (u₀, v₁) and (u₀, v₂). Their lengths along x-axis are the same. The distributions of votes in the parameter space for these lines follow these distributions :

$$v_1+v_{off}+N_Q+N_{T\cdot sym}$$ v_T¹ = (17)

$$v_2+v_{off}+N_Q+N_{T\cdot sym}$$ v_T² = (18)

The shapes of these distributions are the same, while only the positions of their centers differ. The observed vote counts in the parameter space follow the sum distribution of them.

The derivation process of the upper bound of the sampling interval is rather straightforward, however, the rigorous mathematical proofs are a bit complicated. I omit the proofs here.

When two parallel lines can be separated in the discrete image, the lines are apart from each other by at least $\Delta s$measured along y-axis. Let d_r denote the distance between them. The vote peaks corresponding to these lines stand in the parameter space apart by the distance $d_v\simeq \vert\partial F_v/\partial y\vert \ \cdot d_r$ (Figure 4). In other words, the vote peaks are apart from each other by at least

$$d_v\simeq \vert\frac{\partial F_v}{\partial y}\vert \ \cdot \Delta s$$ (19)

in the parameter space if the lines can be separated in the discrete image.

  

Figure 4: Relation between peak distance and image resolution

If we assume the Hough Transform should have enough precision corresponding to the natural quantization error of the given discrete image, it is desired, if possible, every pair of lines which can be separated in the discrete image should also be distinguished in the parameter space. In this case, the condition is given as follows.

Resolution Preservation Condition:

$$q_v \geq R_v$$ (20)

The above inequality are derived from (10), (16) and (19). Figure 5 shows how the vote peaks are distinguished in the parameter space.

  

Figure 5: Relation between peak distance and the width of transformation error

If $R_v\rightarrow 0$, i.e. $\Delta u\rightarrow 0$ (infinitely large computation cost and memory requirement), each peak distribution is square and they can be distinguished by the narrow valley between them. As the width of transformation error R_v increases, the valley in the sum distribution of votes becomes shallow. If R_v=q_v, the valley is still detectable. If R_v>q_v, the valley is completely filled and we cannot distinguish two peaks anymore. Solving (20), we have

$$\Delta u \leq \frac{4q_v(u_0)}{c_{max}(u_0) - c_{min}(u_0)}\ .$$ (21)

Thus, there exists the upper bound of the sampling interval for the scanning parameter.

As a constant sampling interval $\Delta u$ is preferred in general, the following upper bound is more convenient to use.

Upper Bound of the Sampling Interval :

$$\overline{\Delta u} = \min_{(u_0, v_0)\in {\cal P}^2}\ \ \frac{4q_v(u_0)}{c_{max}(u_0) - c_{min}(u_0)}$$ (22)