# Detect Abnormal Points in Point Cloud

Given a list of point cloud in terms of $(x,y,z)$ how to determine abnormal points?

The motivation is this. We need to reconstruct a terrain surface out from those point cloud, which the surveyors obtain when doing field survey. The surveyors would take an equipment and record a sufficient sample of the $x,y,z$ of a terrain. Those points will be recorded into a CAD program.

The problem is that the CAD file can be corrupted from time to time with the introduction of "abnormal" points. Those points do not fit into the terrain surface generally, and tend to have erroneous $z$ value ( i.e., the $z$ value is outside of the normal range).

I am aware that the definition of abnormal points is a bit loose; and I can't come up with a rigorous definition of it. However, I know what is an abnormal point when I see the drawing.

Given all these constraint, is there any algorithm to detect these kinds of abnormal points?

-
I feel like the answers to this question are more refined in the field of statistics (stats.stackexchange.com), programming (stackoverflow.com), or game development (gamedev.stackexchange.com) – Justin L. Jan 27 '11 at 7:52
@Justin, I afraid that those sites are not really suitable for this kind of question. I think it is more math-y than any other aspect. – Graviton Jan 27 '11 at 8:30

The answer is largely determined by your surface reconstruction technique (simple triangulation, marching cubes, and the characteristics of the noise. If the noise points are infrequent and uncorrelated, then the problem is easier.

1. You can presume the surface is locally planar and fit a plane to some small region. A simple "averaging" fit is straightforward and computationally efficient. Once the fit plane is known, you can reject points outside of some tolerance. You can choose to keep the "good" points as they are - or you might consider obtaining new "average" points by projecting the good points onto the fit plane to obtain new samples.
2. An iterative technique (like a re-weighted least squares) is better if you have the time to perform a few iterations on each region.
3. There are other, more robust, surface reconstruction techniques like marching cubes, etc., that can perform limited artifact rejection.

Regardless, a good characterization of the spurious points is needed.

-
you have any papers, or working code on this? – Graviton Jan 27 '11 at 6:40
@Graviton: Here is a doc that describes a least-squares planar fit. geometrictools.com/Documentation/LeastSquaresFitting.pdf – Throwback1986 Jan 27 '11 at 20:27
This stackoverflow discussion is relevant, as well: stackoverflow.com/questions/1400213/3d-least-squares-plane – Throwback1986 Jan 27 '11 at 20:28
I finally found the paper I used most frequently in my vision work: Reconstructing complex surfaces from multiple stereo views, Fua, 1995. This one covers the planar fits in pretty good detail, as well as point-projection to obtain new samples. I made a quick google search but didn't find the pdf online, maybe you will have better luck. If not, let me know, and I'll find a place to post it. – Throwback1986 Jan 27 '11 at 20:57