A Shortest Path Approach for Vibrating Line Detection and Tracking (Pattern Recognition and Image Analysis)

Abstract

This paper describes an approach based on the shortest path method for the detection and tracking of vibrating lines. The detection and tracking of vibrating structures, such as lines and cables, is of great importance in areas such as civil engineering, but the specificities of these scenarios make it a hard problem to tackle. We propose a two-step approach consisting of line detection and subsequent tracking. The automatic detection of the lines avoids manual initialization – a typical problem of these scenarios – and favors tracking. The additional information provided by the line detection enables the improvement of existing algorithms and extends their application to a larger set of scenarios.

Keywords: Computer vision, vibrating lines, detection, tracking.

Introduction

The monitoring of vibrating structures is important in several areas including mechanics and civil engineering. The observation of structures like cable-stayed bridges, antennas or electricity distribution systems is vital for the extension of their life-span and for the reduction of system failures and consequent costs. Past approaches made use of devices, such as accelerometers or load cells (devices which translate force into an electrical signal), placed at the structures to be monitored [5,2,7]. Although the use of such techniques has produced accurate results, the installation of this type of equipment may easily become very expensive. Moreover, in many cases such as antennas or even some cable-stayed bridges it may not be possible to install such devices. Hence, there is a desire to use Computer Vision (CV) techniques to provide a non-invasive alternative. Despite the existence of past work, the natural difficulties of these scenarios pose serious problems. These include: cameras placed at large distances; oscillations in the camera; illumination changes; adverse weather conditions; reduced thickness of the structures and minimal displacements in the image. Line detection specifically targeted for video sequences is by itself a complex problem, also being tackled in other contexts [8,4,3].

The characteristics of the lines or cables, namely their reduced thickness and lack of texture information, forced common CV approaches to this problem to introduce restrictions and assumptions. Difficulties in identifying the structures to be tracked typically require a user to mark a point or region of interest (ROI), for example on the line or cable themselves or on their image representation [6,10,9]. Displacement of the camera or occlusion situations may require a new marking of the points. Also, scenarios where the projection of the cables into the image plane causes the cables to be close together may originate problems as the vibrations may lead to occlusion between them.

We propose to use automatic line detection to augment the flexibility and robustness of vibrating lines tracking algorithms. We argue that the ability to automatically detect the objects (i.e., the lines) to be tracked may increase the reliability of tracking using state-of-the-art algorithms by providing more information. By enabling the automatic selection of an arbitrary number of points over the line to be tracked, it is possible to make a more complete characterization for any point and not only for those manually marked during the initialization. Following this reasoning we divided the description of the proposed method into line detection and tracking.

Line Detection and Tracking

The proposal described in this paper consists of two steps: detection of the lines; tracking of one or multiple points over the line. A vibrating line can be considered as a connected path between the two lateral margins of the image (for simplicity, the presentation will be oriented for horizontal lines only; the necessary adaptations for the detection of vertical lines should be clear at the end). As vibrating lines are almost the only extensive objects on the image, lines can then be found among the shortest paths between the two margins of the image if paths through high gradient positions are favored. Vibrating lines are then best modeled as paths between two regions Q1 and Q2, the left and right margins of the image. These same ideas have been successfully applied to other applications [4,3].

Line Detection Using a Shortest Path Approach

The method considers the image as a graph, where pixels are the nodes and a cost is associated with each edge connecting 8-neighbourhood pixels.

One may assume that vibrating lines do not zigzag back and forth, left and right. Therefore, one may restrict the search among connected paths containing one, and only one, pixel in each column of the image1. Formally, let I be an N\ x N2 image and define an admissible line to be

where y is a mappingThat is, a vibrating line is an 8-connected path of pixels in the image from left to right, containing one, and only one, pixel in each column of the image.

Given the weight function w(p, q) defined over neigbouring pixels p and q, the cost of a line can be defined asThe optimal vibrating line that minimizes this cost can be found using dynamic programming. The first step is to traverse the image from the second column to the last column and compute the cumulative minimum cost C for all possible connected vibrating lines for each entry (i,j):

whererepresents the weight of the edge incident with pixels at positionsAt the end of this process, indicates the end of the minimal connected line. Hence, in the second step, one backtrack from this minimum entry on C to find the path of the optimal line.

Assume one wants to find all vibrating lines present in an image. This can be approached by successively finding and erasing the shortest path from the left to the right margin of the image. The erase operation is required to ensure that a line is not detected multiple times.

To stop the iterative vibrating lines search, the method receives from the user the number of lines to be detected and tracked. Since this can be done once for the entire sequence, it is a very reasonable solution.

Design of the Weight Function. The weight function on the edges was defined so that the shortest path corresponds to a path that maximises the amount of edge strength in the image along the contour. An immediate approach is to support the design of the weight function solely on the values of the incident nodes, fixing the weight of an edge as a monotonically increasing function of the average gradient value of the incident pixels.

Although a more general setting could have been adopted, the weight of the edge connecting 4-neighbour pixels was expressed as an exponential law

withand g is the average of the gradient computed on the two incident pixels. For 8-neighbour pixels the weight was set totimes that value.

Detecting Vibrating Lines in Different Positions. It should be obvious now how to adapt the detection technique for lines between the superior and inferior margins. It is also possible to apply the detection technique to adjacent margins. Suppose that the endpoints of the vibrating lines are in the left and top margins. A difficulty with searching for the shortest paths (shortest in the sense on minimizing the cost of the path) between the top row and left column is that small paths, near the top-left corner are naturally favored. To overcome this challenge, we propose to pre-process the image, adopting the polar coordinates. The left column is mapped to the bottom row (corresponding to an angle of n/2 rads) and the top row stays in the same position. In this new coordinate-system, the path to search for is now between the top and bottom rows.

A different setting is when one of the endpoints of the vibrating lines is on the left OR the top margin and the other endpoint is in the bottom OR right margins. It is still possible to pre-process the image with an appropriate transform before the application of the proposed detection technique. The goal of the transformation is to place the endpoints in opposing margins. Although different solutions exist, we started by rotating the image followed by a linear scaling to transform the oblique lines into vertical ones.

Finally, it is worth mentioning that the vibrating line detection can be applied in a user defined region in the image (and in the video sequence). That can be important when other extensive objects are visible in the image.

Line Tracking

Many line tracking methods use optical flow to compute the displacement vector of one or more points over the line to be tracked. The typical lack of texture information over the line makes tracking methods that require this information unsuitable for these scenarios. Optical flow has limitations concerning occlusion situations and the deformation of objects, but given the characteristics of the scenarios one can assume that such restrictions are respected. Nevertheless, the aperture problem is present making it harder to reliably compute the tangential component of the displacement. We argue that using more points over the line and their corresponding displacements can minimize tracking errors, while contributing to a more complete characterization of the line behavior.

State-of-the-art optical flow methods were considered and experiments performed to assess the most adequate. Each method was applied to sequences containing vibrating lines and compared to the corresponding reference information. It was observed that the Pyramidal Lucas-Kanade [1] outperformed the others. Hence, this was the method used in the subsequent experiments.

The proposed tracking approach consists of the following. On each frame, the lines are detected using the described shortest path method. For any point over the line a window of length L, also over the line, is considered and the median of the displacement vectors for every point in the window computed.

Validation of the Proposed Approach

The capture of sequences for the target scenarios is not a simple task due to aspects such as location or legal implications. Hence, there is a lack of appropriate sequences and of the corresponding reference information.

Dataset

To aid the validation of the proposal described in this paper a set of synthetic sequences with appropriate characteristics and the corresponding reference information was generated. The images consist of six lines, each vibrating with a given frequency and maximum amplitude. Different characteristics for the lines were also simulated, namely: thickness; frequency; amplitude; curvature radius. A background was added to approximate a real situation. The dataset also includes a real sequence of a typical scenario captured and provided by a civil engineering research institute. A set of frames containing reference information were manually generated for the real sequence for the purpose of assessing line detection. Sequence 1 and 2 feature curved lines and sequences 3 and 4 straight ones. The lines in sequence 1 and 3 are thinner. The background in sequence 5 is noisier to augment the difficulty in detection and tracking. Sequence 6 consists of images captured in a real scenario. Fig. 1 depicts an example of synthetic and natural images of the sequences.

Fig. 1. Examples of images from the dataset 3.2 Line Detection Assessment

As previously described, the shortest path method was applied over the gradient of the image. Experiments in the gradient computation over different color spaces were conducted and it was verified that the use of the grayscale space was not adequate causing large gaps in the edges corresponding to the lines. The best results were obtained using the HSV color space and in particular the Saturation channel provided robust information.

The evaluation of the line detection approach was accomplished by measuring the distance between reference and detected lines. For each possible pair, the distance is computed and correspondences determined using the Hungarian algorithm. In the distance calculation, for each point in the reference line, the distance to each point in the detected line is computed and two overall measures are taken: the average and the Hausdorff distance. For an image with multiple lines, the average of the line errors and the Hausdorff distance are taken. Similarly, for a sequence, the same process applies over the image values.

Tracking Assessment

For the evaluation of the tracking, the results of two tracking approaches, one based on measuring the displacement vectors in a point over the line and the one proposed, are compared to the reference information by measuring the euclidean distance. For each mark (reference point in one line), the root mean square error over the sequence is computed and the average over the number of lines to be tracked in the sequence is calculated. For the proposed approach, different window sizes were considered. Sequences 3 to 5 were use in the evaluation due to the possibility of using an arbitrary number of reference points.

Results

Table 1 presents the results for line detection, using shortest paths, for the dataset. As stated, the average and Hausdorff distance were calculated and normalized by the diagonal size of the image.

Table 1. Results for line detection normalized by the image diagonal

	Average Distance	Hausdorff Distance
Seq. 1	0.13%	0.13%
Seq. 2	0.13%	0.15%
Seq. 3	0.13%	0.15%
Seq. 4	0.14%	0.15%
Seq. 5	0.20%	1.21%
Seq. 6	0.04%	0.07%

One can observe that the errors obtained are small and for sequences 1 to 4 they are nearly the same. These sequences comprise the same background with changes only in the characteristics of the lines. The error is greater for sequence 5 since it presents a higher level of difficulty in both the noisy background and lack of distinctiveness of the lines. The best performance is achieved for the real sequence, as the distinctiveness of the lines is greater.

Table 2 presents the results for the evaluation of the tracking. For each line in a sequence, the root mean square error relatively to the reference at time instant t was calculated and the average over the lines in the sequence determined. Tracking using 1 point corresponds to using a state-of-the-art algorithm with the user marking the interest point in the image. The error gain in percentage relatively to the 1 pixel approach was calculated for the displacement vectors and its individual components (vertical and horizontal). Tracking results taking into account all the visible line are considered, but care must be taken in these situations since a high degree of curvature may induce errors.

The use of more points over the line enables a decrease in the RMSE. A considerable part of the improvement in the line tracking is due to a better approximation of the horizontal component since, in the considered scenarios, it is the most affected by the aperture problem. For different line positions the changes are straightforward.

The frequencies of vibrations for each line were also computed and compared to the reference values. The results are presented in Table 3.

Table 2. Results for line tracking

		Window Size
		1 points	3 points|ll points|101 points|301 points| all line
	Direction	RMSE	Error gain relatively to the 1 point approach (%)
Seq. 3	horizontal	1,22	-2,45	-13,72	-54,52	-87,16	-90,72
	vertical	0,79	0,03	4,32	-7,10	-39,01	-60,26
	total	1,73	-1,39	-7,46	-35,74	-68,98	-80,48
Seq. 4	horizontal	1,85	-6,34	1,05	-44,75	-69,94	-91,23
	vertical	0,46	-2,65	-12,98	-28,38	-42,18	-29,43
	total	1,94	-5,97	-0,42	-42,59	-66,79	-80,22
Seq. 5	horizontal	0,89	-0,60	-4,45	-39,32	-61,24	-81,86
	vertical	1,16	-0,13	0,93	-15,76	-10,78	-7,43
	total	1,80	0,22	-0,79	-25,97	-31,18	-38,90

Table 3. Frequency outputs (in rad/s) from sequences 3, 4 and 5

Seq. 3		Seq. 4		Seq. 5
Reference	Obtained	Reference	Obtained	Reference	Obtained
0,800	0,800	0,800	0,801	0,800	0,800
0,850	0,848	0,850	0,848	0,300	0,300
0,900	0,901	0,900	0,902	0,200	0,200
0,950	0,951	0,950	0,950	0,950	0,950
1,000	1,000	0,050	0,050	0,100	0,100
1,050	1,051	1,500	1,502	1,500	1,501

Conclusions

The use of the shortest path method enables the automatic detection of the vibrating lines, straight or curved, to be tracked with very small errors. Such automatic detection avoids the need for manual initialization of the points to be tracked. Moreover, obtained results show that using more points over the line enables a reduction of the tracking errors due to the optical flow computation.

The application of the proposed method to the monitoring of civil engineering structures can take advantage of the knowledge of the structure dimensions to perform camera calibration and obtain 3D measures of the displacement.

Future work will include the validation of the method with data captured from other devices such as accelerometers. Other forms of using the additional information provided by the lines detected are also a research topic of interest.