<\/p>\n\n\n
Figure 3.8:<\/strong>
\nHough transform, the left image shows three lines in the image space and the right image shows the corresponding lines in the parameter space<\/caption>\n
\n
\n $\"Image$ <\/div>\n<\/td>\n<\/tr>\n<\/table>\n<\/div>\n
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. <\/p>\n
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. <\/p>\n
A linear list is used to store the lines. A list element (line) consists of the following attributes<\/p>\n
\n
Point start<\/strong><\/dt>\n
Stores the image coordinates of the point, where the line has its origin.<\/p>\n<\/dd>\n
Point end<\/strong><\/dt>\n
Stores the image coordinates of the point, where the line ends.<\/p>\n<\/dd>\n
Point cp <\/strong><\/dt>\n
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 $\"$$ is the line in the left image and $\"$$ its corresponding line in the right image, then the cp for $\"$$ is defined as<\/p>\n\n
<\/p>\n\n\n
$\"begin{equation*}begin{aligned}lrightarrow$ <\/td>\n<\/tr>\n<\/table>\n<\/div>\n

<\/p>\n\nThe cp for $\"$$ is defined as the point of intersection between a horizontal line $\"$$ , that has its origin in $\"$$ , and $\"$$ . <\/p>\n<\/dd>\n
Real direction<\/strong><\/dt>\n
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.<\/p>\n<\/dd>\n
Digit length<\/strong><\/dt>\n
Stores the length of the line. It is increased for every pixel that is added to the line.<\/p>\n<\/dd>\n
Digit counterX<\/strong><\/dt>\n
Counter of steps in x direction. It is increased or decreased in every iteration, dependently on the chosen direction.<\/p>\n<\/dd>\n
Digit counterY<\/strong><\/dt>\n
Counter of steps in y direction. It is increased or decreased in every iteration, dependently on the chosen direction.<\/p>\n<\/dd>\n
Digit disparity<\/strong><\/dt>\n
Disparity, $\"$$ if no disparity is found, or the disparity in pixels if a corresponding line has been found.<\/p>\n<\/dd>\n
Real hitRateDisp<\/strong><\/dt>\n
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 $\"$$ .<\/p>\n<\/dd>\n
Real hitRateObj<\/strong><\/dt>\n
is the quality of the found object line or $\"$$ if no line is found.<\/p>\n<\/dd>\n
Real xw<\/strong><\/dt>\n
Stores the x-coordinate of the line in the world coordinate system.<\/p>\n<\/dd>\n
Real yw<\/strong><\/dt>\n
Stores the y-coordinate of the line in the world coordinate system.<\/p>\n<\/dd>\n
Real zw<\/strong><\/dt>\n
Stores the z-coordinate of the line in the world coordinate system.<\/p>\n<\/dd>\n
LineList* next<\/strong><\/dt>\n
Pointer to the next element of the line list or NULL at the end of the list.<\/p>\n<\/dd>\n
LineList* corrEdge<\/strong><\/dt>\n
Pointer to the corresponding line in the other image or NULL if no line is found.<\/p>\n<\/dd>\n
EdgeList* corrObj<\/strong><\/dt>\n
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.\n<\/dd>\n<\/dl>\n
\nFirst of all everything is set to 0, except the disparity and both hit rates, which are all set to $\"$$ . A LIFO (last in, first out) list $\"$$ of length $\"$$ 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.
\nIf 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 $\"$$ . 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.
\nIf 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<\/a> for possible directions and their encodings.\n<\/p>\n\n
<\/p>\n\n\n
Table 3.2:<\/strong>
\nEncoding of directions<\/caption>\n
\n
\n\n\n\n\n\n\n\n\n\n\n\n<\/tr>\n<\/table>\n
<\/p>\n
<\/font><\/div>\n<\/td>\n<\/tr>\n<\/table>\n<\/div>\n\n
If no connection exists the algorithm stops and the pixels that are already in $\"$$ 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 $\"$$ , the attitude $\"$$ of the first part of the line is computed. $\"$$ 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 $\"$$ is the counter in x direction, $\"$$ is the counter in y direction and $\"$$ is a boolean variable, then $\"$$ can be computed as<\/p>\n\n
<\/p>\n
left, up \t<\/font><\/td>\n \t\tup \t\t<\/font><\/td>\n \tright, up \t\t<\/font><\/td>\n<\/tr>\n

\n 7\t\t\t<\/font><\/td>\n \t\t8 \t\t<\/font><\/td>\n \t\t9\t\t\t<\/font><\/td>\n<\/tr>\n
<\/p>\n
left \t\t<\/font><\/td>\n
\t\tCenter <\/font><\/td>\n \tright \t\t\t<\/font><\/td>\n<\/tr>\n

\n 4 \t \t\t<\/font><\/td>\n \t\t\t\t<\/font><\/td>\n \t\t6 \t\t\t<\/font><\/td>\n<\/tr>\n
<\/p>\n
left, down <\/font><\/td>\n
\t\t \t\t<\/font><\/td>\n right, down\t\t<\/font><\/td>\n<\/tr>\n

\n 1\t\t\t<\/font><\/td>\n \t\t\t\t<\/font><\/td>\n \t3 \t\t\t\t<\/font><\/td>\n<\/tr>\n
\n\n
$\"$displaystyle$ <\/td>\n \n(3.14)<\/td>\n<\/tr>\n<\/table>\n<\/div>\n

<\/p>\n\n $\"$$ is used as a reference to decide whether the following pixels belong to a straight line or not. We now have a line $\"$$ with length $\"$$ and attitude $\"$$ . A second EdgeList<\/i> $\"$$ is generated, whose starting point is equal to the end point of $\"$$ . The algorithm does the same as before, it tries to follow the edge. If this is possible, $\"$$ 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 $\"$$ list, thus the oldest element is lost. Until now, it is not clear if the new added point belongs to the line $\"$$ , 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 process^{3.5<\/sup><\/a>. With the aid of we calculate a new attitude . The computation is the same as shown in Equation}3.14<\/a>. 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 $\"$$ would not be that significant. By computing the new attitude with $\"$$ it is proved that only the last part of the line is incorporated. If the absolute difference of both attitudes
\n $\"$$ is below a lower threshold $\"$$ , the points that are not on the list are added to the list and marked as processed. The information needed is stored in $\"$$ . 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 $\"$$ the search continuous. $\"$$ is used to handle the given noise. When $\"$$ 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 $\"$$ 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 $\"$$ 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<\/i> is generated and the old one points to the new one.<\/p>\n
A linear list of lines is the result of this procedure. Figure 3.9<\/a> shows an image in which straight lines are searched.<\/p>\n
<\/p>\n\n\n
Figure 3.9:<\/strong>
\nResults of the line extraction, horizontal lines are dismissed. Found lines are plotted in red, start points are green and the end points are blue (colors can only be seen in the electronic version of this thesis).<\/caption>\n
\n
\n $\"Image$ <\/div>\n<\/td>\n<\/tr>\n<\/table>\n<\/div>\n
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.<\/p>\n\n
Next:<\/b> Correspondence Analysis<\/a>
\n Up:<\/b> Methods<\/a>
\n<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Line Extraction<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1946,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_genesis_hide_title":false,"_genesis_hide_breadcrumbs":false,"_genesis_hide_singular_image":false,"_genesis_hide_footer_widgets":false,"_genesis_custom_body_class":"","_genesis_custom_post_class":"","_genesis_layout":""},"categories":[],"featured_image_src":null,"featured_image_src_square":null,"_links":{"self":[{"href":"https:\/\/www.anagram.at\/en\/wp-json\/wp\/v2\/pages\/1967"}],"collection":[{"href":"https:\/\/www.anagram.at\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.anagram.at\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.anagram.at\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.anagram.at\/en\/wp-json\/wp\/v2\/comments?post=1967"}],"version-history":[{"count":0,"href":"https:\/\/www.anagram.at\/en\/wp-json\/wp\/v2\/pages\/1967\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/www.anagram.at\/en\/wp-json\/wp\/v2\/pages\/1946"}],"wp:attachment":[{"href":"https:\/\/www.anagram.at\/en\/wp-json\/wp\/v2\/media?parent=1967"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.anagram.at\/en\/wp-json\/wp\/v2\/categories?post=1967"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}