ares 
pipe 
wo- 
and 
d is 
it is 
red 
The 
leet 
nly 
on 
vel 
ea 
ion 
ely 
[he 
[he 
tial 
f a 
  
135 
straight line corresponding to the line equation (X cos(0) - Y sin(0) — p). In practice, the HT maps a bounded discrete 
binary image to a bounded discrete Hough space called accumulator array. Every cell Acc[i,j] of the accumulator 
corresponds to the set of straight lines with parameters (p , 60) € (p+Ap , 6+A6), where the cell size (2Ap , 240) 
bounds the precision of further results. 
It is obvious, that this classic parametrization is not the only possible one. Moreover, it has some essential 
disadvantages. The most important one is the presence of a prior empty area in the classic accumulator. Since our 
lines have a low slope angle, the useful area will be very small. The accuracy and computational speed are also not 
high. So, we have to search for some other parametrization. We think that in this case the best choice is a type of 
natural parametrization, generated by the discrete raster of the analyzed image (Svalbe, 1989). 
There is a simple connection between the 2D rectangular discrete lattice and the set of possible discrete straight lines 
on this lattice. When the straight line is characterized by the couple of lattice cells containing its ends, such 
parametrization is called "natural". The simplest natural parametrization uses all possible combinations of two pixels 
as possible line descriptions. However, this parametrization is too superfluous - it requires an accumulator of size N* 
for an image of size N2. Due to this disadvantage, it is never used. 
In (Svalbe, 1989) the following case of natural parametrization is proposed. Let's describe the straight line by the pair 
of points lying on the intersection of the line with the perimeter. For an [NxM] lattice with 2(N+M) perimeter points, 
this representation of the HT requires (because of symmetry) (4Nx4M)/2 = 8NM elements, i.e. possible lines. As one 
quarter of these points lies on same border of an image, the final size of the parameter space will be 6NM. It is only a 
small subset of the natural set with O[(NM)?] parameters. The advantage of this parametrization is that if it is applied 
in image subareas, it permits to connect lines, that are broken into segments, more easily than other HT 
representations, because the broken segments can be joined using the common perimeter points. The disadvantage of 
the perimeter point representation is that the information on the line direction (slope angle) is not given in an explicit 
form. Nevertheless, such parametrization can be applied in the initial stage of the modular algorithm, because te 
direct measurement of the angle will be made only at the last (measurement) stage. 
In addition, the here adopted object model permits an even more compact natural parametrization of lines. We can 
describe lines by a pair of points, lying on the vertical borders of the image. Such parametrization will also use the 2D 
accumulator space (y1,y2), where y1 is the ordinate of the line intersection with the left border and y2 is the ordinate 
of the line intersection with the right border. For any image of size NxM pixels, there are M? possible lines 
(accumulator cells) because there are M points at the left border of the image and M points at the right one. The gain 
in comparison to the parametrization presented above becomes even more obvious, if we take into account, that the 
type of the problem presented here requires use of "wide" images with size N>2M. 
This parametrization permits to consider only lines with relatively small negative and positive inclination angles. It 
also permits to split the initial image into a set of vertical stripes in order to analyze the possible curvature of the 
object lines. When there is a line curvature, the slope of the line varies from one stripe to another. Thus, we can take 
into account only the stripes with small line slope variation between them and ignore the remaining ones. 
The analysis of the accumulator consists in the search of a pair of lines. Our algorithm is based on the following 
assumption. Let the object consist of two lines with parameters (y11,y12) and (y21,y22). Our object model prescribes 
that these two lines intersect outside of the image, at the left. Thus, we can find some threshold value Tyl that 
satisfies the condition y11<Tyl<y21 or y21<Tyl<yll. It means, that there is always a tessellation of the accumulator 
(y1,y2) by a line y1=Ty1, such that the cells of the accumulator, corresponding to the two lines, will be in different 
areas of this tessellation. 
In turn, it permits to reduce the analysis of the accumulator to the analysis of its Lateral Histogram, with LH 
LHist[yl] = Z(Acc[y1,y2]) , v2 = 1,..,M. 
Tests on a set of images have shown, that the LH expresses very well the image bimodality, and that the detected 
modes correspond to the two lines of the angular object. To search for the histogram modes, the Otsu algorithm 
(Otsu,1979) can be applied. 
Thus, the object detection algorithm has the following steps: 
]) Extract image contours. 
2) Execute the Hough Transform with parametrization (y1,y2). 
3) Collect the Lateral Histogramm LHist[y ] |. 
4) Determine the coordinate Tyl of the tessellation, separating the cells of the parameter space (y1.y2), by using 
the Otsu algorithm for optimum threshold detection. 
IAPRS, Vol. 30, Part 5W1, ISPRS Intercommission Workshop "From Pixels to Sequences”, Zurich, March 22-24 1995