Discrete Lines and Transformation Functions

Suppose we have a continuous line. Let ${\cal P}^2$ be a subset of the 2-dimensional Euclidean space, and call it ``parameter space.'' Let (u,v) denote an element of ${\cal P}^2$. The continuous line defined by (u,v) is represented by the set of points (x,y) which satisfy

$$v=F_v(x, y ; u)\ ,$$ (2)

where F_v(x, y ; u) is the continuous, linear function. We call F_v ``transformation function.'' For simplicity of the discussion, the angle of the line measured from x-axis is limited to $[-\pi/4, \pi/4)$ in this document.

The following transformation functions are often used in the Hough Transform.

  

$$\mbox{$a$ --$b$\space parameterization:}$$

$$\ \ \ \ \ b=F_b(x, y ; a) = y-ax$$ (3)

$$\mbox{$\rho$ --$\theta$\space parameterization:}$$

$$\ \ \ \ \ \rho=F_{\rho}(x, y ; \theta) = x\cos\theta+y\sin\theta$$ (4)

Note that these are the special cases of (2). In the framework of the Extended Hough Transform (EHT)  [1] we can use arbitrary functions as F_v under some conditions.

The continuous line which has the parameters (u₀, v₀)appears in the discrete image as the discrete line which is represented by the set of pixels

$$\{(\hat{x},\hat{y})\vert v_0=F( x,y ; u_0 ), (x,y) \in {\cal X}^2\}\ ,$$ (5)

where ${\cal X}^2$ denotes the range of definition of the coordinate (x,y)on the line.

To detect the discrete line in a given discrete image is same as to find the parameters (u₀, v₀) for the line. Let us consider the continuous sampling points on a continuous line. Let the continuous sampling points be defined as the intersection of the line and the straight line $x=t\cdot\Delta s$ (t: integer) which is parallel to y-axis. Let (x_i, y_i) represent the i-th continuous sampling point, and let $(\hat{x}_i, \hat{y}_i)$ denote the quantized value of it. Obviously, we have $\delta x_i=\hat{x}_i-x_i=0$. Thus, we can consider only the quantization error along y-axis, i.e., $\delta y_i=\hat{y}_i-y_i$.