Effects of data filtering techniques in line detection.

Boiangiu, Costin Anton ; Raducanu, Bogdan

1. INTRODUCTION

The Line Detection module is typically implemented at the software application level of an Automatic Content Conversion System. This module is being fed a black and white image which holds enough information to solve the considered task. The desired output is a collection of lines represented either by their analytical parameters or by a list of pixel collections (each made of a series of connected black pixels).

This task proves to be less straightforward than it might seem as lines are often imperfect, containing noises or deformations. The line detection module should be developed such that to be able accept a set of calibrating parameters (in order to help it cover the broad range of possible line types).

There are a number of approaches to the line detection problem. Among the most popular and researched are the ones based on voting, firstly introduced along with the Hough Transform method. Their efficiency lies in their ability to deal with noises (Duda & Hart, 1972).

2. THE HOUGH TRANSFORM

When using the Hough Transform, lines are viewed as a pair of polar parameters, (p, [theta]). A line equation in terms of these parameters would be (Princen et al., 1992):

[rho] = [y.sup.*] sin[theta] + [x.sup.*]cos[theta] (1)

Every point in the input image counts as a vote for each line it may lay on. In the generated parameter space (or accumulator) lines are identified either as a maximum or by applying a threshold (Sklanksy, 1978).

3. DISCRETE LINE PARAMETERIZATION

Following the approach of the Hough Transform, we have developed a system which employs a different parameterization in order to achieve better results for our particular targets. The parameterization of a line is set in terms of the pair ([x.sub.0], dx) and called Discrete Parameterization--it was designed to resemble a digital line, as drawn onto a discrete memory space. In an image with height h, a line described by ([x.sub.0], dx) passes through the points ([x.sub.0], 0) and (x[.sub.0] + dx,h) .

[FIGURE 1 OMITTED]

Retrieving the lines from the voting space is a fundamental problem and requires a well thought approach (Niblack & Petkovic, 1990).

When working with scanned newspaper or book pages, the accumulator is flooded with votes from the large contents of characters. It is important to find a stable threshold mechanism so characters do not yield many false lines.

4. PARAMETER SPACES

Looking at the voting space as a greyscale image (brighter pixels correspond to higher voting counts) we obtain a visual of the voting process.

One way to extract information from the two spaces is to find points with values above a threshold. Lines imply a high number of votes, thus they will pass the threshold. The problem is that characters are responsible for the majority of votes. The difference between a false line point and a correct line point, in terms of votes, could be very small (5%) and it is impossible to establish a threshold in this case.

A second approach is to analyze local maxima points. Characters participate with high probability with the same number of votes to a set of lines so they will not influence local maxima. The problem with this approach is that the parameter space is constructed point by point and this heavily affects the continuous nature of local maxima.

[FIGURE 2 OMITTED]

5. FILTERING THE PARAMETER SPACES

Both problems presented above can be solved by using resampling filters. Such a filter modifies the points in the parameter space and assigns them new values based on a weighted sum their neighbours' values. The filters have a macro scale effect of blurring or smoothing the space, which is the exact solution for the local maxima sweep problem. Particularly useful for this is the Triangle filter (Umbaugh, 2005).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Equation (2) shows a one dimensional Triangle filter. To apply this to the two dimensional parameter space, we first apply it for every row and obtain a preliminary array. Finally we apply the filter again for each column, thus obtaining a 2D effect. This approach is only possible for symmetrical filters such as this one.

The Triangle Filter gives higher weights to points closer to the origin point and lower values as points are further apart, thus real local maxima are enhanced while false maxima are decimated.

[FIGURE 3 OMITTED]

The parameter spaces in Fig. 3. have been filtered with a Triangle Filter. Correct local maxima (represented by bright pixels) are more obvious now, while noise generated maxima disappeared.

To solve the thresholding problem, a different, more complex, filter is adopted. This is the Lanczos scaling filter.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

Equation (3) represents a one dimensional Lanczos filter. It is applied to the two dimensional parameter space first row-wise then column-wise.

The Lanczos filter is typically used for scaling images because it has the property that it retains protruding aspects of the original image, producing results of higher quality.

To diminish the effects of the large number of characters on the voting space, we first apply the Lanczos filter on the space and then we subtract the original space from it. This is called a Negative filter effect and the results are shown in Fig. 4.

Before applying this filter, the parameter space was heavily composed of the votes generated by characters. Lines were difficult to detect because their vote count was negligible higher than the average.

[FIGURE 4 OMITTED]

The filter has overcome this problem and in the resulting space, the lines have become more obvious. A thresholding scheme can now be applied with greater stability as the range of possible values has been greatly decreased.

Points with high vote counts are now more visible, in the sense that they strongly disperse from the vote average. This effect is caused by the special quality of the Lanczos filter to normalize high frequency values while enhancing peak values.

These examples show how filtering the parameter spaces can enhance particular characteristics and turn out helpful in determining the intended points.

Depending on the desired characteristics, other filters can be used. A median filter can be used first to diminish noises propagated in the parameter space.

To further enhance local maxima, a Gauss convolution filter may be applied. For larger kernel dimensions, a Gauss filter can prove more accurate than the Triangle filter.

6. CONCLUSIONS

When working with digital signals, such as images or sounds, there is no stable way of extracting certain characteristics like maximums, frequencies or gradients. Hence, an important preprocessing is the naturalization of the signal which leads to resampling of the discrete data in order to conform to a continuous domain.

In this paper we have shown how resampling an input image, considered as a two dimension array of data, can enhance its characteristics and improve the computation of useful information about it.

Statistical methods, like the ones proposed in this paper, are a powerful method of solving difficult tasks without a deterministic solution. Hence, these filtering techniques may prove useful in determining a good approximating solution for a problem in any domain.

7. REFERENCES

Duda, R. & Hart, P. (1972). Use of the Hough Transformation to Detect Lines and Curves in Pictures, Comm. ACM, Vol. 15, Issue 1, (January 1972) pp. 11-15, ISSN: 0001-0782

Niblack, W. & Petkovic, D. (1990). On improving the accuracy of the Hough Transform, Mach. Vision Appl,. Vol. 3, Issue 2, (March 1990) pp. 87-106, ISSN: 0932-8092

Princen, J.; Illingworth, J. & Kittler, J. (1992). A Formal Definition of the Hough Transform: Properties and Relationships, JMIV, Vol. 1, No. 2, (July 1992) pp. 153168, ISSN: 0924-9907

Sklanksy, J. (1978). On the Hough Technique for Curve Detection, IEEE Transactions on Computers, Vol. 27, Issue 10, (October 1978) pp. 923-926, ISSN: 0018-9340

Umbaugh, S. E. (2005). Digital Image Analysis and Processing, CRC, ISBN: 0849329191