Errors in the Hough Transform

In the Hough Transform, the votes are distributed around the point of the true parameters (u₀,v₀)like a butterfly shape as shown by the meshes in Figure 2. The estimated values of the parameters are expected to be the quantized values of the true parameter (u₀, v₀). Let $\delta u=\hat{u}_k-u_0$ and $\delta v=\hat{v}_m-v_0$ denote the errors of the parameters.

Since u is the scanning parameter, we will be able to find the value of u whose error is within the quantization error,

$$\vert\delta u\vert\leq \frac{\Delta u}{2}\ .$$ (6)

In the following discussion, we assume that the estimated value of u is given by $\hat{u}_k$ which satisfies (6).

$\vert\delta v\vert$, the absolute value of the error of the parameter v, cannot be made smaller only by decreasing the sampling interval $\Delta v$. The coordinates $(\hat{x}_i, \hat{y}_i)$, which are substituted for the transformation function, include the error of at most $\pm\Delta s/2$ which comes from the quantization of image. The parameter $\hat{u}_k$ also includes the error of at most $\pm\Delta u/2$. In general, v_ik is affected by these errors through the transformation function. Let $\delta v_i=v_{ik}-v_0$ be the difference (of the error) between v_ik and the true parameter v₀. In order to make $\vert\delta v\vert=\vert\hat{v}_m-v_0\vert$smaller in the Hough Transform, $\vert\delta v_i\vert$ must be made smaller. We mainly discuss this non-quantized error in this document.

The error of v_i is given by

$$\delta v_i F_v(\hat{x}_i, \hat{y}_i \ ; \ \hat{u}_k) - F_v(x_i, y_i \ ; \ u_0)$$ =

$$F_v(x_i, y_i+\delta y_i \ ; \ u_0+\delta u)$$ =

$$\hspace{6em}-F_v(x_i, y_i \ ; \ u_0)\ .$$ (7)

If we apply the Taylor's expansion around $\vec{x}=(x_i, y_i),\ u=u_0$ to the first term on the right side of the above equation, we obtain

 

$$\delta v_i E_Q(\vec{x}_i ; u_0 ; \delta y_i)+E_T(\vec{x}_i ; u_0 ; \delta u)... ...elta y_i\cdot \delta u\vert, \vert\delta y_i\vert^2, \vert\delta u\vert^2) )\ ,$$ =

$$\delta v_i^L E_Q(\vec{x}_i ; u_0 ; \delta y_i)+E_T(\vec{x}_i ; u_0 ; \delta u) \ \ \ \simeq \ \ \ \delta v_i \ ,$$ = (8)

$$\mbox{where} E_Q(\vec{x}_i ; u_0 ; \delta y_i) = \delta y_i \cdot \left.\frac{\partial F_v}{\partial y} \right\vert _{\vec{x}=\vec{x}_i, u=u_0}\ ,$$

$$E_T(\vec{x}_i ; u_0 ; \delta u)= \delta u \cdot \left.\frac{\partial F_v}{\partial u} \right\vert _{\vec{x}=\vec{x}_i, u=u_0}\ .$$

We call $E_Q(\vec{x}_i ; u_0 ; \delta y_i)$ ``quantization error,'' since the error is produced by the quantization of the image. We call $E_T(\vec{x}_i ; u_0 ; \delta u)$ ``transformation error,'' since the error is produced by the quantization of the scanning parameter.

Note that the error measured along v-axis is affected not only by the quantization of the image but also by the quantization of the scanning parameter in the Hough Transform. This property is essential in the Hough Transform, however, it has often been overlooked.

(8) denotes the errors for only a single sampling point (x_i, y_i). If we consider all the sampling points on the line, or if we consider the moving of a point along the line, the errors $\delta v^L_i$ are distributed around v=v₀ in the parameter space. Each of the quantization errors and the transformation errors also has a sort of distribution according to the change of i. Regarding the distributions as probability distributions, we can took at the errors as the noises which come from the probability distributions. Let N_Q and N_T denote these noises, and we call them ``quantization noise'' and ``transformation noise'' respectively. A real distribution of votes at $u=\hat{u}_k$ (the quantized value of u₀) is expected to be the same distribution as a random variable v_T, where

$$v_T=v_0+N_Q+N_T\ .$$ (9)

When we design a system which requires the Hough Transform, we may often try to make the maximum value of errors smaller, or to make the average value of errors smaller. Here, we give the definition of the maximum absolute values of the quantization errors and those of the transformation errors when (x_i,y_i) takes various values. A ``maximum quantization error,'' which is denoted by q_v or q_v(u₀), is defined as the maximum absolute value of the quantization errors $E_Q(\vec{x}_i ; u_0 ; \delta y_i)$. From (8) and $\vert\delta y_i\vert\leq \Delta s/2$, we get

$$q_v=q_v(u_0)=\frac{\Delta s}{2}\cdot\max_{\vec{x}_i\in {\cal ... ...l F_v}{\partial y}\right\vert _{\vec{x}=\vec{x}_i, u=u_0}. \ \$$ (10)

The distribution of the quantization noise N_Q follows that of the quantization error $\delta y$, because the transformation function F_v is a linear function of y. It is known that $\delta y$ follows a discrete distribution for the sampling of images with square grid if the tangent of the angle between x-axis and a straight line is a rational number. It is also known that $\delta y$ follows a continuous, uniform distribution for a infinitely long line if the tangent is an irrational number. We can regard the distribution of the quantization noise N_Qas a continuous and uniform distribution Qin the range [-q_v, q_v] as shown in Figure 3.

  

Figure 3: Distribution of quantization noise and transformation noise

In general, $\partial F_v/\partial u$ in the transformation error $E_T(\vec{x}_i ; u_0 ; \delta u)$ is the linear function of the coordinates x and y. Therefore, $\partial F_v/\partial u$ on a certain line is distributed uniformly from its minimum to its maximum value. We can easily verify by the computer simulation that the real transformation errors $E_T(\vec{x}_i ; u_0 ; \delta u) = (\partial F_v/\partial u)\cdot\delta u$have a uniform distribution.

We introduce some notations here.

  

$$\equiv \max_{\vec{x}_i\in {\cal X}^2} \ \left.\frac{\partial F_v}{\partial u}\right\vert _{\vec{x}=\vec{x}_i, u=u_0}$$ c_max(u₀) (11)

$$\equiv \min_{\vec{x}_i\in {\cal X}^2} \ \left.\frac{\partial F_v}{\partial u}\right\vert _{\vec{x}=\vec{x}_i, u=u_0}$$ c_min(u₀) (12)

Let $\varepsilon_v^+$ and $\varepsilon_v^-$ denote the maximum and the minimum value of the transformation error respectively. We obtain $\varepsilon_v^+ = \max \{ \delta u\cdot c_{max}(u_0), \delta u\cdot c_{min}(u_0) \}$and $\varepsilon_v^- = \min \{ \delta u\cdot c_{max}(u_0), \delta u\cdot c_{min}(u_0) \}$. The transformation noise N_T is distributed in the range $[\varepsilon_v^-, \varepsilon_v^+]$such as D shown in Figure 3. We define R_v⁰ and v_off as the following.

$$\equiv R_v^0(u_0,\delta u) \equiv \frac{1}{2} (\varepsilon_v^+ - \varepsilon_v^-)$$ R_v⁰ (13)

$$\frac{1}{2} \cdot \vert\delta u\vert\cdot \left\{c_{max}(u_0)-c_{min}(u_0)\right\}$$ = (14)

$$\equiv v_{off}(u_0,\delta u) \equiv \frac{1}{2} (\varepsilon_v^+ + \varepsilon_v^-)$$ v_off (15)

We introduce a random variable $N_{T\cdot sym}$ which follows a uniform distribution in the range [-R_v⁰, R_v⁰]. We have $N_T=N_{T\cdot sym} + v_{off}$, and hence, the observational value v_T is given by $v_T=v_0+v_{off}+N_Q+N_{T\cdot sym}$. We call R_v⁰ ``width of transformation error.'' v_off denotes the offset of the error distribution.

Since $\delta u$ is an unknown value, and since the maximum value of R_v⁰ is important in the following discussion, we use $\vert\delta u\vert=\Delta u/2$ which maximize R_v⁰. The maximum value is given by

$$R_v \equiv R_v(u_0) = \frac{\Delta u}{4}\cdot \left\{c_{max}(u_0)-c_{min}(u_0)\right\}\ .$$ (16)

R_v can be regarded as the level of transformation error.

The distribution of v_T is known to have a trapezoid shape. The upper base length of the trapezoid is 2|q_v-R_v|, and the center of the upper base is v₀+v_off(Figure 3).

As the origin of the coordinate system gets apart from the center of the image, the absolute value of the offset v_off gets greater. This means that the error of the estimated parameter for vincreases. To design precise Hough Transform, we should put the origin on the center of the image.