2
$\begingroup$

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?

  • 0
    @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.2011-01-27

2 Answers 2

1

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.

  • 0
    I finally found the paper I used most frequently in my vision work: Reconstructing complex surfaces from multiple stereo views, Fua, $1$995. 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.2011-01-27
1

I've been tackling complex maths on point clouds for a few weeks now, i will give you some ideas.

First of all, your points are either 16 bit 3D points or rounded to managable integers, for example every point is an integer ranging from size 0-5000, that givs high precision while giving access to fast X-Y-Z value sorting.

Normally they use KD trees for point cloud algebra, but if you have discreet points you can place them as true false values in a 3d boolean array, which can be very interesting to program with.

You have to specifically tailor your algorithm for the type of pattern that you wish to detect and fix, every time.

The result depends if you have reliable normals, precision level, error type, you have to get someone with good spacial visualization to figure out all the best logic to deal with your pattern recognition, it is very fun for me.

You have to sort your arrays by X/Y/Z and do iterative comparisons on them. Use square of distance to compare two points, not distance, square maths is slow.

sorting X Y Z individually, you will be able to fast compare close vertices on three axes in different iteration runs.

If you sort by x then y then z, you may have a nicely sorted data set that is fast to get data from.

It sounds like you just need a poximity test for Z compared to it's neighbors. description of data is vague. no images provided!

If so, sort array by z into strata of the precision of 1 unit or round them, make an array which holds data which tells you how many times a dot appears in any Z strata, for example the building roof at 20m contains 800 poins, 10m strata contains 200 points, and so forth for every strata, so you have an array of point number per strata.

You can use that strata number array to order all your data into an array you can read and write from very fast, comparing only 1% of the points to every z value instead of 100%, 100 times faster! that kind of data sorting takes 1 hour to write and can sort a 100 million poinds in a few seconds. you need to memorize number points on each axis level, write a staircase so you know that all points between 20 and 21 meters are in indexes 5mn and 5.23mn of your sorted point cloud for example.

Also check KD trees.

dont use distance maths use square of distance, it's faster.

hope that's helpful.