Università di Roma "La Sapienza", Italy.

i = ( id - Ox ) * ax * ( 1 + k1 * rd^2 ) + Ox

j = ( jd - Oy ) * ( 1 + k1 * rd^2 ) + Oy

By knowing k1, Ox, Oy, ax, (Px and Py) it is possible to undistort the image so that it can be considered as coming from a pinhole camera.

The Hough Transform is a robust and effective method for finding lines fitting a set of points. It also provides an easy way to compute the curvature of a set of point that are supposed to be on a line.

The transformation from (x,y) plane to (r,t) plane is achieved by associating every point P(x,y) with the following curve in the (r,t) plane

r = x * cos(t) + y * sin(t)

At the same time a point in (r,t) correspond to a line in (x,y).This representation is unique and complete as long as 0 <= t < PI.

A graphical representation of the Hough transform (HT)
can be produced by generating a discrete grid of (r,t) plane,
and by defining HT(r,t) as the number of points in (x,y) plane
whose curve pass through (r,t).

The best fitting lines correspond to local maxima of HT(r,t).

The following picture shows the Hough transform of the above binary image, with the following orientation for the axes.

-------------------> r | | | V t

The ten groups of brighter pixels correspond to the ten
lines in the image. Parallel lines in the (x,y) plane are
horizontally aligned in HT, since they have (almost) the same t.

Note also that, as the lines in the image are not straight,
the local maxima in HT are blurred.

In order to find values for undistorting the image we need a measure of distortion, that is a measure of the curvature of the lines.

A possible measure for the curvature of a set of points is given by

eR = SUM(dist(Pi,R))

where R is the best line fitting the points.Moreover if there are many possible lines the overall curvature can be defined as the sum of the curvature for each line

E = SUM(SUM(dist(Pij,Rj)))

In this case we need to know for every line which are the points belonging to that line.Now given a point P (xP,yP) and a line R in the (x,y) plane (let (rR,tR) be the coordinates of R in the Hough domain), the distance between P and R is

dist(P,R) = | rR - ( xP * cos(tR) + yP * sin(tR) ) |

The curvature of R is given by

eR = SUM_(r in Dr) ((rR-r)^2 * HT(r,tR))

and the overall distortion isE = SUM_R (eR) The method does not require to know the list of points belonging to each line (by not considering points that are farther away from the best fitting line than a given factor Dr). Moreover local maxima in HT can be easily detected with a limited local search.

The objective is to find values of the calibration parameters (k1, Ox, Oy, ax)
that minimize the distortion of an image.

However the search in this four dimensional space is not trivial,
and a good strategy is required to get good results.

The following figures show the undistorted image and the Hough Transform of its binary image.

R. Duda and P. Hart.
Use of the Hough Transformation to Detect Lines and Curves in Pictures
*Communications of the ACM*. Vol. 15, N. 1. 1972.

Go to:

Multiresolution Stereo Vision System

Stereo triangulation

Stereo Camera Calibration