Detect lines and their width.

The operator lines_gauss can be used to extract lines (curvilinear structures) from the image Image. The extracted lines are returned in Lines as sub-pixel precise XLD-contours. The parameter LightDark determines, whether bright or dark lines are extracted. If ExtractWidth is set to 'true' the line width is extracted for each line point. If CorrectPositions is set to 'true', lines_gauss compensates the effect of asymmetrical lines (lines having different contrast on each side of the line), and corrects the position and width of the line. This parameter is only meaningful if ExtractWidth='true'. Because the line extractor is unable to extract certain junctions because of differential geometric reasons, it tries to extract these by different means if CompleteJunctions is set to 'true'.

The extraction is done by using partial derivatives of a Gaussian smoothing kernel to determine the parameters of a quadratic polynomial in x and y for each point of the image. The parameter Sigma determines the amount of smoothing to be performed. Larger values of Sigma lead to a larger smoothing of the image, but can lead to worse localization of the line. Generally, the localization will be much better than that of lines returned by lines_facet with comparable parameters. The parameters of the polynomial are used to calculate the line direction for each pixel. Pixels which exhibit a local maximum in the second directional derivative perpendicular to the line direction are marked as line points. The line points found in this manner are then linked to contours. This is done by immediately accepting line points that have a second derivative larger than High. Points that have a second derivative smaller than Low are rejected. All other line points are accepted if they are connected to accepted points by a connected path. This is similar to a hysteresis threshold operation with infinite path length (see hysteresis_threshold). However, this function is not used internally since it does not allow the extraction of sub-pixel precise contours.

For the choice of the thresholds High and Low one has to keep in mind that the second directional derivative depends on the amplitude and width of the line as well as the choice of Sigma. The value of the second derivative depends linearly on the amplitude, i.e., the larger the amplitude, the larger the response. For the width of the line there is an approximately inverse exponential dependence: The wider the line is, the smaller the response gets. This holds analogously for the dependence on Sigma: The larger Sigma is chosen, the smaller the second derivative will be. This means that for larger smoothing correspondingly smaller values for High and Low have to be chosen. Two examples help to illustrate this: If 5 pixel wide lines with an amplitude larger than 100 are to be extracted from an image with a smoothing of Sigma = 1.5, High should be chosen larger than 14. If, on the other hand, 10 pixel wide lines with an amplitude larger than 100 and a Sigma = 3 are to be detected, High should be chosen larger than 3.5. For the choice of Low values between 0.25 High and 0.5 High are appropriate.

The extracted lines are returned in a topologically sound data structure in Lines. This means that lines are correctly split at junction points.

lines_gauss defines the following attributes for each line point if ExtractWidth was set to 'false':

'angle':        The angle of the direction perpendicular
                         to the line
'response':     The magnitude of the second derivative

'width_left':   The line width to the left of the line
'width_right':  The line width to the right of the line

'asymmetry':    The asymmetry of the line point
'contrast':     The contrast of the line point

In general, but in particular if the line width is to be extracted, Sigma >= w/sqrt(3) should be selected, where w is the width (half the diameter) of the lines in the image. As the lowest allowable value Sigma >= w/2.5 must be selected. If, for example, lines with a width of 4 pixels (diameter 8 pixels) are to be extracted, Sigma >= 2.3 should be selected.

/* Detection of lines in an aerial image */
read_image(Image,'mreut4_3') 
lines_gauss(Image,Lines,1.5,3,8,'light','true','true','true') 
disp_xld(Lines,WindowHandle).

Let A be the number of pixels in the domain of Image. Then the runtime complexity is O(A*Sigma).

Let S = Width*Height be the number of pixels of Image. Then lines_gauss requires at least 55*S bytes of temporary memory during execution.

lines_gauss returns 2 (H_MSG_TRUE) if all parameters are correct and no error occurs during execution. If the input is empty the behaviour can be set via set_system(::'no_object_result',<Result>:). If necessary, an exception handling is raised.

lines_gauss is reentrant and processed without parallelization.

gen_polygons_xld

lines_facet

bandpass_image, dyn_threshold, topographic_sketch

C. Steger: ``Extracting Curvilinear Structures: A Differential Geometric Approach''. In B. Buxton, R. Cipolla, eds., ``Fourth European Conference on Computer Vision'', Lecture Notes in Computer Science, Volume 1064, Springer Verlag, pp. 630-641, 1996.

C. Steger: ``Extraction of Curved Lines from Images''. In ``13th International Conference on Pattern Recognition'', Volume II, pp. 251-255, 1996.

C. Steger: ``An Unbiased Detector of Curvilinear Structures''. Technical Report FGBV-96-03, Forschungsgruppe Bildverstehen (FG BV), Informatik IX, Technische Universität München, July 1996.

Sub-pixel operators