Cleaning massive sonar point clouds
Lars Arge, Kasper Green Larsen, Thomas Mølhave, Freek van Walderveen · 2010
We consider the problem of automatically cleaning massive sonar data point clouds, that is, the problem of automat-ically removing noisy points that for example appear as a result of scans of (shoals of) fish, multiple reflections, scan-ner self-reflections, refraction in gas bubbles, and so on. We describe a new algorithm that avoids the problems of previous local-neighbourhood based algorithms. Our algo-rithm is theoretically I/O-efficient, that is, it is capable of efficiently processing massive sonar point clouds that do not fit in internal memory but must reside on disk. The algo-rithm is also relatively simple and thus practically efficient, partly due to the development of a new simple algorithm for computing the connected components of a graph embedded in the plane. A version of our cleaning algorithm has already been incorporated in a commercial product. Categories and Subject Descriptors: F.2.2 [Analysis of algorithms and problem complexity]: Nonnumerical algo-rithms and problems—Geometrical problems and computa-tions