# Detecting abnormal points in point cloud

I've asked the same question at Math SE, but the suggestion is that probably this question belongs here.

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?

-

An outlier detector for your irregular ("vector") point data is available in GRASS as v.outlier.

An overview of spatial outlier detection methods appears in a 2004 paper by Cheng and Li.

An older method, specialized for topographic data, relies on "drainage enforcement" (making the water flow downhill continuously without accumulating in sinks). That can find some of the outliers, but probably not all of them.

A more generic method is to adapt a local indicator of spatial variability, such as a local Moran's I statistic, to identify points that are "too far" away from the surface. GeoDa can compute such statistics.

-

Are the points relatively dense on your surface? Then I would suggest counting the number of points in a sphere around every point. Choose the radius of your sphere to be a bit less than the distance the "abnormal" points have to the regular surface - maybe half of what they typically have. Then throw out the points where the number of other points inside that sphere is very low. (I don't know if your outliers occur in small groups or if they are isolated points; this technique should work for either case.)

If a naive implementation picks out the correct points but is too slow, and you're struggling to come up with a faster algorithm to do the same, then let us know. I'm sure we could come up with something :)

-
don't think your solution will work because most of the abnormal points have wrong $z$ values, not wrong $x,y$ values –  Graviton Jan 28 '11 at 6:06
I think it's a moot point because others have suggested better techniques, but I'm not sure I understand your objection -- I would think the fact that the $z$ coordinates are off is essential to why my method would work. –  Erik P. Jan 28 '11 at 14:47
The main problem is that the size of an extreme variation in the $z$ values may be--and usually is--quite a bit smaller than typical spacing between points in $(x,y)$. Your method would tend to thin the data without necessarily finding any outlying elevations at all. –  whuber Jan 28 '11 at 18:22
I see. In my mind the variation in $z$ was pretty big. Thanks for both of your comments. –  Erik P. Jan 28 '11 at 22:31

I think this problem relies only in the outliers of variable $z$.

The surveyor scans a grid of $x$,$y$ points that are "well-behaved". On the other hand $z$ points may contain abnormal values (in statistics we call them outliers).

I would suggest to explore the values of $z$, and the plot of $(x,y,z)$.

From those plots it will be clear that abnormal values of $z$ occur isolated.

Lets suppose that we have a rectangular grid of points $x_k, y_k$, at each point of the grid we have a value of $z$ that we will denote as $z_{k,k}$.

So, if we think $z_k$ is an abnormal point, we expect a low correlation among $(x_k,y_k,z_{k,k})$ and $(x_{k+1},y_{k},z_{k+1,k})$.

In general, we expect a low correlation between $(x_k,y_k,z_{k,k})$ and its neighbors $\mathcal{N}(k,k)$. A way to measure the spatial correlation between the point $(k,k)$ and its neighborhood is the empirical variogram defined by:

$\hat{\gamma}(k,k) = \frac{1}{\#\mathcal{N}(k,k)} \sum_{(i,j), (p,q) \in \mathcal{N}(k,k)} | z_{i,j} - z_{p,q} |^2$.

If you calculate $\hat{\gamma}(k,k)$ for the whole grid you can be sure that outliers in the empirical variogram are indeed abnormal points.

A boxplot can be useful to identify the outliers.

Using the variogram is a way to ensure that you are actually reading an abnormal point. Suppose that your surveyors are scanning a slope, then you will notice that the $z_{k,k}$ has high values, but also their neighbors. In case the point is abnormal only $z_{k,k}$ will have high values.

NOTE: If you're sure that your surveyors are analyzing a rather flat surface, get rid of the variogram and make a boxplot of $z$, any outlier identified by the boxplot is an abnormal point.

-
I think that's the problem; I don't know what value of $\hat{\gamma}(k,k) = \frac{1}{\#\mathcal{N}(k,k)} \sum_{(i,j), (p,q) \in \mathcal{N}(k,k)} | z_{i,j} - z_{p,q} |^2$ would qualify as "outlier" –  Graviton Jan 28 '11 at 6:08
I am downvoting primarily because the suggestion doesn't work. Outliers in a set of "variograms" (I use quotes because the formula is not the usual empirical variogram), as indexed by $(k,k)$ (why the double subscript?) will identify neighborhoods, not points. One truly outlying point will contribute to many large (not small) outlying values in this set of variograms. A sharp fault in the slope, such as a cliff (or building, for LIDAR datasets) will also create large numbers of large outliers. –  whuber Jan 28 '11 at 18:19
You could fit some sort of smooth function for $z(x,y)$, perhaps using locally weighted scatterplot smoothing (LOWESS or LOESS), then look for points where the residual for $z$ (i.e. the difference between the observed and fitted values) is greater than some fixed multiple of the standard error of prediction. That should be straightforward e.g. in R using the loess function in the standard stats package.
some fixed multiple of the standard error. This is pretty ambiguous. How do I know what is the correct coefficient? –  Graviton Jan 28 '11 at 6:07