Anagram Engineering

Webdesign und Softwarelösungen aus Vorarlberg. Ihr Partner für innovative Lösungen rund ums Internet. Full Service Agentur.

Line Extraction



Next: Correspondence Analysis
Up: Methods
Previous: Edge detection

Line Extraction

A line is defined as a set of points which are connected and form a straight line. It can be completely described through the start point and end point. There are different techniques for finding straight lines. The most popular one is the Hough transform. The basic idea of this technique is to find curves that can be parameterized, like lines, polynomials, circles, etc. in a suitable parameter space. The detection of straight lines in images will be shortly discussed because it is the main feature used in the proposed approach. Let us assume that the line is described in parameterized form
$ r = xcostheta+ ysintheta$, where $ r$ is the perpendicular distance from the origin and $ theta$ the angle of the $ x$-coordinate with the normal. For any point
$ p = (x_i,y_i)$ on a straight line, $ r$ and $ theta$ are constant. Points in the cartesian image space maps to curves in the polar Hough parameter space. This point-to-curve transformation is called Hough transform. Points which are collinear in the image space intersects at a common point
$ (r,theta)$. Figure 3.8 shows how three lines are mapped into the parameter space. The transformation is implemented by quantizing the Hough parameter space into finite intervals, called accumulator cells. For every $ (x_i,y_i$, the parameters
$ (r,theta)$ are computed and the accumulator at position
$ (r,theta)$ is incremented. Peaks in the parameter space represent a straight line in the image space.

The main disadvantage is that it needs a lot of computational effort to transform the image into the hough-space and the output is a parametric description of a line, thus the starting and end point are not known and it needs some comparisons to find the starting and end point. Another way is to define a convolution mask which detects lines. The main disadvantage with this method is that every mask only finds lines that have a certain direction.

Another approach is to follow edge points iteratively and use the attitude of the found edge points as a reference to decide whether the following set of edge points seems to be in a line with the same attitude or not. The proposed work uses such a method.

A linear list is used to store the lines. A list element (line) consists of the following attributes

Point start
Stores the image coordinates of the point, where the line has its origin.

Point end
Stores the image coordinates of the point, where the line ends.

Point cp
The compare-point stores the image coordinates of the point, that is used to calculate the disparity between this line and the corresponding line in the other image. In other words, if $ l$ is the line in the left image and $ l'$ its corresponding line in the right image, then the cp for $ l$ is defined as

begin{equation*}begin{aligned}lrightarrow cp_x = frac{lrightarrow start_x +... ... + (lrightarrow end_y - lrightarrow start_y)}{2}. end{aligned}end{equation*}


The cp for $ l'$ is defined as the point of intersection between a horizontal line $ h$, that has its origin in $ l->cp$, and $ l'$.

Real direction
Stores the direction of the line, which is computed by adding up the directions of the edge pixels that are considered to lie on the line. The resulting direction is mainly used to find corresponding lines in other images, as well as finding corresponding object lines.

Digit length
Stores the length of the line. It is increased for every pixel that is added to the line.

Digit counterX
Counter of steps in x direction. It is increased or decreased in every iteration, dependently on the chosen direction.

Digit counterY
Counter of steps in y direction. It is increased or decreased in every iteration, dependently on the chosen direction.

Digit disparity
Disparity, $ infty$ if no disparity is found, or the disparity in pixels if a corresponding line has been found.

Real hitRateDisp
Stores the rating of the correspondence between this line and a line in the other image. The line with the best rating is chosen, otherwise the rating is set to a value which is equivalent to $ infty$.

Real hitRateObj
is the quality of the found object line or $ infty$ if no line is found.

Real xw
Stores the x-coordinate of the line in the world coordinate system.

Real yw
Stores the y-coordinate of the line in the world coordinate system.

Real zw
Stores the z-coordinate of the line in the world coordinate system.

LineList* next
Pointer to the next element of the line list or NULL at the end of the list.

LineList* corrEdge
Pointer to the corresponding line in the other image or NULL if no line is found.

EdgeList* corrObj
Pointer to a line that seems to belong to the other side of this line i.e. the two lines of a goal or a robot.

First of all everything is set to 0, except the disparity and both hit rates, which are all set to $ infty$. A LIFO (last in, first out) list $ vartheta$ of length $ varsigma$ is created, which stores the chosen directions. The algorithm controls every pixel in the image whether it is an edge pixel. The search starts at the top-left of the image and searches from left to right and top to bottom. For vertical lines it is proven that when an edge pixel is found and it belongs to a line, the pixel is the first point of the line. This is not true for lines that are almost horizontal, but it can be ignored because horizontal lines cannot be used to calculate disparity and thus they are not searched for.
If an edge pixel is found and it is not already processed, the start and end points of the line list are set to its coordinate. Then the algorithm tries to follow the edge pixels, starting from the actual point, until the length of the line has reached a given threshold $ varsigma$. During the process of following a line, pixels that seem to be more likely to lie on a straight line are preferred. This is necessary, otherwise the algorithm would always prefer a given direction.
If a connection between a line point and one of its neighbour points, that can be used to continue the search, exists, the direction in which the new point can be found is stored. See Table 3.2 for possible directions and their encodings.

If no connection exists the algorithm stops and the pixels that are already in $ vartheta$ will be marked as processed. Then it continues searching edge pixels that are not processed yet. But if the length of the line reaches the threshold $ varsigma$, the attitude $ alpha$ of the first part of the line is computed. $ vartheta$ is now totally filled, that means if we add another direction, the oldest element will be shifted out of the list. Let us assume that $ c_x$ is the counter in x direction, $ c_y$ is the counter in y direction and $ beta$ is a boolean variable, then $ alpha$ can be computed as


$ alpha$ is used as a reference to decide whether the following pixels belong to a straight line or not. We now have a line $ l_{ref}$ with length $ varsigma$ and attitude $ alpha$. A second EdgeList $ l_h$ is generated, whose starting point is equal to the end point of $ l_{ref}$. The algorithm does the same as before, it tries to follow the edge. If this is possible, $ l_h$ stores the new end coordinate, its counters are increased and the new point is marked as processed. The chosen direction, in which the new edge pixel is situated is shifted into the $ vartheta$ list, thus the oldest element is lost. Until now, it is not clear if the new added point belongs to the line $ l_{ref}$, thus the points added are stored in a separate list. This is needed, because otherwise a lot of points would be lost during the search process3.5. With the aid of $ vartheta$ we calculate a new attitude $ alpha'$. The computation is the same as shown in Equation 3.14. One could ask why not compare the attitude of the whole line with the reference line. If the whole line would be compared, the computation of $ alpha'$ would not be that significant. By computing the new attitude with $ vartheta$ it is proved that only the last part of the line is incorporated. If the absolute difference of both attitudes
$ arrowvert alpha - alpha' arrowvert$ is below a lower threshold $ tau_l$, the points that are not on the list are added to the list and marked as processed. The information needed is stored in $ l_h$. The list which stores the points is emptied, because now it is clear that these points belong to the line. Otherwise, if the difference is below a high threshold $ tau_h$ the search continuous. $ tau_h$ is used to handle the given noise. When $ tau_l$ is very low, the distance between a point and the line is only allowed to be very small thus noise can lead to the end of the search. With the use of $ tau_h$ a higher variance is allowed, but only to follow the edge. To gain access to the line, in sum the change in direction has to be low. Only pixels that belong to the line are marked as processed. If the difference is higher as $ tau_h$ the search is finished. The line is kept, if its length is higher than the minimum length accepted. If the line is accepted, a new LineList is generated and the old one points to the new one.

A linear list of lines is the result of this procedure. Figure 3.9 shows an image in which straight lines are searched.

Unfortunately, edge pixels are not always connected. Thus, after the line list has been generated it tries to connect lines if they have approximately the same attitude, e.g. the absolute difference of two lines is below a threshold, and the end point of one line is near the start point of the other or vice versa.

Next: Correspondence Analysis
Up: Methods