Anti-Excessive Filtering Model Based on Sliding Window

Haoang Li, Weiming Hu, Jian Yao* and Wenqiao Zhang

School of Remote Sensing and Information Engineering, Wuhan University, Wuhan, Hubei, P.R.China



1. Abstract

This paper is mainly purposed on the problem that ground points in cloud of LiDAR (Light Detection And Ranging) has been excessively filtered. To solve this problem, this paper proposes an improved model on the base of the traditional sliding window model, combining with optimized rules on determining standard elevation value, tolerance of elevation difference and dynamic thresholds. The optimized rules on determining standard elevation could increase the accuracy of filtering, by the nearest neighbor and interpola- tion algorithm whose theoretical base is spatial correlation. Tolerance of elevation difference prevents excessively filtering by skipping some windows with negligible elevation difference, maintaining the accuracy at a relevant higher level. Dynamic thresholds, changing with various terrains and times of itera- tion, are adopted to further improve the model based on the mentioned factors. To demonstrate our algorithm and prove its effectiveness, the standard data from ISPRS (International Society for Photogrammetry and Remote Sensing) for testing is selected. Results have shown that both robustness and efficiency increase with the optimization.

2. Approach

Our approach is mainly composed of three parts: optimized rules on determining standard elevation value, tolerance of elevation difference and dynamic thresholds. They contribute to a higher accuracy and robustness.

Determination of optimum standard elevation value:

  • According to First Law of Geography, the nearer two points are, the more inter-dependent they would be. Thus, it finds the nearest standard point to the undetermined point, using the height of nearest point to represent the standard elevation of the undetermined point, rather than using the lowest point within the window;
  • Kriging interpolation is used. Interpolation will not be as effective when the distances among most of the testing points are larger than the Range (a parameter of Semi-variogram).

Tolerance of elevation difference:

  • When the elevation difference in some window has dropped below the tolerance, meaning that the points left are almost ground points, this exact window would be skipped of filtering, and the algorithm automatically deems all the points left as ground points;
  • After several times of iteration, when all the windows are skipped of filtering because of the tolerance, the accuracy would become stable and it is time for the algorithm to end.

Dynamic thresholds:

  • The threshold is increasing when the iteration goes on, and the speed of this increase slows down, that is, the increment of thresholds should decrease for each iteration;
  • Using the dynamic threshold, with the increase of the number of iterations, if the threshold increases appropriately, the fault that ground point is regarded as non-ground points can be reduced.

3. Experimental Results

The standard data provided by International Society for Photogrammetry and Remote Sensing (ISPRS) is selected to test and support the algorithm. To demonstrate the ap- plicability of the algorithm in different zones with various terrain conditions, this paper contains experimental results and reports from two sets of data, one featuring the sloping fields with vegetation (abbreviated as S) and another one featuring the flat fields with buildings (abbreviated as F). The sloping field data, containing 42477 points, has an intensity of 0.67 point/m2   and the gap between points in sloping fields is 2 to 3.5 meters. The flat field data, containing 17845 points, has an intensity of 0.18 point/m2.  The following three experiments are aimed to test and evaluate respectively the availability and error of the model, according to the three major parameters: the standard elevation value, the tolerance of elevation difference and the dynamic threshold. In the figures of experiment results, the sloping field is marked with rectangles and the flat field is marked with circles. In the experiments, the original division of window is 20×20 and after every iteration, the division times of length and width would both double.

3.1. Evaluation on Standard Elevation Value

In the experiment, traditional model of standard elevation determination (TSE) and optimized model of standard ele- vation determination (OSE) are used to filter the data of the sloping and the flat fields. There are two other methods used, which are standard elevation determination with interpolation only (ISE) and with the nearest neighbor only (NSE).

As the Fig. 1 shows, lines of different patterns represent models used in different fields when determining the standard elevation value. The solid lines represent the results of TSE. The dotted lines represent the results of OSE. The dash- dotted lines represent the results of ISE and the pointed lines represent the results of NSE.

As the results show, generally speaking, the accuracy of OSE is better than ISE or NSE, and this indicates that if nearest neighbor and interpolation algorithm is combined on their applicable condition respectively, it is superior than using one of them only. In addition, in the flat fields, there is little difference between the accuracy of TSE and OSE, and TSE has already had a high accuracy. However, in the sloping fields, the accuracy is not as high as it in flat fields and after some times of iteration, both model achieve stable balance and the OSE has the higher accuracy. the following paper will talks about the reason why after 2 times of iteration, the gap of accuracy between OSE and TSE becomes conspicuous in sloping fields and remain negligible in flat fields.

Spatial distances and spatial correlation between different standard height points are taken into consideration. First calculate distance between every set of two points in the area and figure out the semi-variance value. Then a scatter plot and a fitted line are used to show its major trend. Exponential model is used to fitting the points and the results is shown as Fig. 2.

The Range of the fitted model is approximately 21 meters as shown above. When the time of iteration reaches 2, the distances among different standard elevation points are getting closer to the Range, which is the requirement of interpolation. Thus as iteration goes on, interpolation is having more obvious advantage and promoting the accuracy.

The analysis of the results of flat fields filtering could mainly be based on the applicability and limitation of in- terpolation. The superiority will not be as obvious when the elevation has little variance.

The results indicate that in those areas with big variance in elevation, it is more effective using the distance-based and correlation-based model to determine the standard elevation value, to prohibit excessive filtering and promote accuracy, comparing with the traditional way only using the lowest point as the unified standard point for the whole grid. Furthermore, while the iteration goes on and the divisional windows are getting smaller, interpolation will have a more obvious effect on the accuracy. But it is not necessary to use optimized model in flat fields because the traditional model can get the high accuracy too, and the effect of interpolation is not evident.


Fig. 1.Performances of TSE and OSE in Sloping and Flat Fields..

Fig. 2. Half variance function fitting measurement results in sloping fields with vegetation.

3.2. Evaluation on Tolerance of Elevation Difference

Fig. 3 reports the differences in sloping and flat fields, caused by varied tolerance of elevation difference (TED) with respectively lines of various patterns. The solid, dotted, dot- dash and dashed lines represent no TED, TED=1, 2 and 3 respectively.

It is shown above in the plots that in sloping fields with vegetation, the accuracy culminates when the tolerance of height difference is fixed at 2 meters, a number derived from the formula above. And it is predictable that when the tolerance is fixed at 3 meters or 1 meter, the respective accuracy is not as high. When the tolerance is not adopted, indicating that there is no restraints and for every time of filtering all the windows are processed, the data shows that accuracy suffers from the sliding down after the increase without stopping. This indicates the excessive filtering. To take the flat field with buildings and artificialities as a example, the algorithm performs the best with the tolerance fixed at 1 meter. And it is almost of the same that when the tolerance is changed away from 1 meter, the results more or less get worse. When tolerance is not adopted, same thing happens with the experiment on vegetation fields. Besides, the best tolerance is higher in the sloping fields than that in the flat fields which is explicable because it is demonstrated by the formula that there is significant positive correlation between optimum tolerance of elevation difference and slope.

Additionally, other parameters under the same conditions, it is better for the algorithm with tolerance of elevation difference to filter a sloping field than to do a flat field. The experiments have proved that the introduction of tolerance of elevation difference has a better performance in the areas with more topographic rises and falls.

To sum up, adding tolerance of elevation difference con- tributes to the stability of the algorithm and the improvement of accuracy.

Fig. 3. Performances of TED Fixed to 1, 2 and 3, and without TED in Sloping and Flat Fields.

3.3. Comparative Evaluation

In the paper above, when the standard elevation value is improved and the tolerance of elevation difference is added, it is manifest in the results from the first and second experiment that the accuracy and robustness of algorithm is improved. To go a step further, this paper then introduces dynamic thresholds to achieve further optimization. In Fig. 4  ,the improved models mentioned above, with the optimized standard elevation datum and the tolerance of elevation difference, is marked as IM, and have been used to filter data and the corresponding results have been recorded by the dotted lines. Then, this paper introduces dynamic thresholds on this base, and the results are recorded by the solid line. In contrary, filtering using dynamic thresholds exclusively is marked as dash-dotted line.

From the results of experiments, if dynamic thresholds are added, the accuracy has a small growth that cannot be neglected. In the opposite, without the mentioned base above, the dynamic thresholds alone could not prevent the accuracy from sliding downwards and the rate always stays at a lower level.

Thus, it can be concluded that dynamic thresholds alone cannot obviously promote the accuracy of algorithm, unless the mentioned model is added. They all together consist of the entire and complete model of window-based LiDAR anti- excessive filtering. With all these detailed methods working together, the robustness and accuracy are guaranteed.

Fig. 4. Performances of DT, IM with DT and IM in the sloping and flat fields.

Based on the optimization mentioned above, combining with the three crucial factors, the algorithm is tested with the sloping fields data mentioned above, and the results are shown as below. In Fig. 5 ,the first figure on the left is a three-dimensional visualization of original cloud point data, while the second figure on the right is another one of the after-processed results.

Fig. 5. Contrast between Sloping Fields before and after Filtering.


Haoang Li, Weiming Hu, Jian Yao* and Wenqiao Zhang. Anti-Excessive Filtering Model Based on Sliding Window, submitted to 4th International Conference on Computer Science and Electronic Technology (ICCSET), 2015.

Haoang Li, Weiming Hu, Jian Yao* and Wenqiao Zhang. Anti-Excessive Filtering Model Based on Sliding Window, Technical Report, School of Remote Sensing and Information Engineering, Wuhan University.