We dream a magic button for 3-D point cloud processing

aurivus|REVIT, 3D Studio MAX, 3D Coat, Lightwave, ZBrush, VRMesh, TopoGun, Blender, Rhino, Trimble Sketchup Etc.
Post Reply
User avatar
Joon
V.I.P Member
V.I.P Member
Posts: 335
Joined: Wed Aug 21, 2013 8:01 pm
10
Full Name: Sung Joon Ahn
Company Details: CurvSurf
Company Position Title: Founder + CEO
Country: Republic of Korea
Linkedin Profile: Yes
Location: Seongnam-si, Korea
Has thanked: 7 times
Been thanked: 35 times
Contact:

We dream a magic button for 3-D point cloud processing

Post by Joon »

Free technology preview of Point Cloud Feature Extraction for Autodesk Revit Now Available (January 24, 2012)
New free way to do auto feature extraction in Revit (February 1, 2012)


The history of 3-D point cloud processing is dating back to 1960’s.

The most fatal misconception of 3-D point cloud processing may be the edge detection in point cloud. Edge detection in 2-D image is worth, but not in 3-D point cloud. Some people have been applying edge detection, a 2-D image processing technique, to 3-D point cloud data. Radially and laterally from the viewpoint of measuring device, the edges of 3-D point cloud are generally unstable and unreliable.

Taking an image is generating a 2-D map of 3-D space. Edge detection in 2-D image is finding the boundary points of 2-D regions. The 2-D boundaries may be represented by 2-D curves fitted to the 2-D edgels (edge elements) extracted. Worth!

3-D measurement is generating a 3-D point cloud, the boundary points of 3-D volumetric regions. The 3-D boundaries may be represented by 3-D surfaces fitted to the 3-D points measured. Worth!

3-D space is more complex than 2-D space. 2-D space is a constrained subset of 3-D space. Data processing techniques applied to 2-D images have practically nothing to do with 3-D point cloud and should not be applied to.

For 3-D point cloud processing, first, we must identify/understand the physics and the statistics & probability theory of 3-D measurement. Second, we have to more understand than known the analytic geometry of surfaces.

We must process the point cloud directly without meshing. First, meshing requires much time. Second, the meshes generated from point cloud are arbitrary artifacts that do not really exist. Finally, if the measurement noise of point cloud is large in comparison with the distances between neighboring points, meshing will be resulting in spiky meshes.

By signal processing theory, the variance of the normal vectors of mesh triangles will be amplified by the measurement noise, because the normal vectors of mesh triangles are inherently differentials of points, i.e. slopes between points.

We must suppress the noises of 3-D point cloud to get the geometry of object surface. The accurate & reliable shapes, sizes, positions & orientations of 3-D object surfaces are what we want to know in real time. All the necessary mathematics and knowledge for the 3-D point cloud processing mentioned above are applied to the videos below:

Real Time 3-D Object Recognition

youtu.be/6tn4rMeIBaw

FindSurface SDK - Revit Plugin Demo

youtu.be/ThpXAFJEBJ4

What must be done is the combination of 2-D image processing and 3-D point cloud processing. The information of 2-D image and 3-D point cloud are inherently mutually orthogonal, delivering complementary information. 3-D surfaces can be determined by 3-D point cloud processing, of which boundaries can be determined by 2-D image processing.

Joon
Last edited by Joon on Tue Oct 09, 2018 3:39 am, edited 3 times in total.
User avatar
Joon
V.I.P Member
V.I.P Member
Posts: 335
Joined: Wed Aug 21, 2013 8:01 pm
10
Full Name: Sung Joon Ahn
Company Details: CurvSurf
Company Position Title: Founder + CEO
Country: Republic of Korea
Linkedin Profile: Yes
Location: Seongnam-si, Korea
Has thanked: 7 times
Been thanked: 35 times
Contact:

Re: We dream a magic button for 3-D point cloud processing

Post by Joon »

Appended to the original post:

We must process the point cloud directly without meshing. First, meshing requires much time. Second, the meshes generated from point cloud are arbitrary artifacts that do not really exist. Finally, if the measurement noise of point cloud is large in comparison with the distances between neighboring points, meshing will be resulting in spiky meshes.

By signal processing theory, the variance of the normal vectors of mesh triangles will be amplified by the measurement noise, because the normal vectors of mesh triangles are inherently differentials of points, i.e. slopes between points.

Experiment on ARKit with iPad Pro

youtu.be/2TlJ_8Tq6js
User avatar
Joon
V.I.P Member
V.I.P Member
Posts: 335
Joined: Wed Aug 21, 2013 8:01 pm
10
Full Name: Sung Joon Ahn
Company Details: CurvSurf
Company Position Title: Founder + CEO
Country: Republic of Korea
Linkedin Profile: Yes
Location: Seongnam-si, Korea
Has thanked: 7 times
Been thanked: 35 times
Contact:

Re: We dream a magic button for 3-D point cloud processing

Post by Joon »

Optical 3-D measurement techniques, e.g., photogrammetry, structured-light, time-of-flight, are subject to lateral and radial measurement uncertainties. The lateral uncertainties are mainly concerning about the resolution of encoder or sensor cells. On the other hand, the radial uncertainties are concerns about the S/N ratio.

If 3-D measurement data are accurate and free from the problems of concentricity/collinearity/coplanarity, 3 points are enough for clearly determining the parameter values of an object plane measured (1 point for point, 2 points for line, 3 points for plane, 4 points for sphere, 5 points for cylinder, 6 points for cone, and 7 points for torus, etc.). In general, 3-D measurement data are containing millions of points.

By the 3-D point cloud processing with PCA (principal component analysis) for line/plane, or with ODF (orthogonal distance fitting) for curve/surface, there will be no more practical advantages in parameter accuracy by processing more than about 1,000 inliers. Thus, to accelerate the speed of data processing, we can randomly sample the input point cloud data to limit the number of inliers to about 1,000. As a result, the time for recognizing a 3-D object geometry is quasi-constant independently on the size of input point cloud, because the data random sampling is much cheaper than the data processing with PCA or ODF.

The number 1,000 of data sampling is optimal from the viewpoint of statistics and economy (cost).
The number 1,000 of data sampling is the magic number compromising between accuracy and cost.
The number 1,000 is the large number to which we can count in real life from 1.

When we recognize a 3-D object geometry, we first gaze a 3-D object point and analyze the neighboring points around the gazing point. Gazing only a single 3-D point is crucial for accelerating the 3-D object recognition. We need not care the all environment around us in order to recognize a geometric object. The size of the neighboring region around the gazing point is determined by the scale of the 3-D object geometry, i.e., the curvature radii of the object surface to be recognized.

Through the curvature analysis of the neighboring points (i.e., initial inlier points) around the gazing point, the shape type of object surface and the initial values of the shape parameters can be determined. ODF to the current inlier points updates the shape parameter values. And, region growing based on the current object shape updates the inlier points. By alternating ODF (model fitting) and region growing (segmentation), the shape parameter values and the inlier points can be determined simultaneously.

Fully automatic feature extraction from point cloud

youtu.be/42ZKbkjpBbY

CT: Fully automatic feature extraction from point cloud

youtu.be/pEFpHJ9HcC8

On the other hand, RANSAC (random sample consensus) selects randomly three points from the input point cloud to determine the parameter values of object plane. But, the probability of encountering 3 points of an object plane out of a large point cloud is extremely low. In order to find an object plane, we must try many times selecting 3 points. RANSAC is a single-modal method, finding a line (2 points), a plane (3 points), a sphere (4 points), a cylinder (5 points), a cone (6 points), or a torus (7 points), one by one. Furthermore, the computing time increases exponentially as the number of the points to be selected is increasing. The Hough transform suffers from the similar shortcomings of RANSAC.

In summary, the gazing (selecting) a single point per object and the direct processing of point cloud without meshing are crucial for automatic real-time object recognition.

One shot one get.

Joon
Last edited by Joon on Sat Nov 03, 2018 10:46 pm, edited 7 times in total.
User avatar
Joon
V.I.P Member
V.I.P Member
Posts: 335
Joined: Wed Aug 21, 2013 8:01 pm
10
Full Name: Sung Joon Ahn
Company Details: CurvSurf
Company Position Title: Founder + CEO
Country: Republic of Korea
Linkedin Profile: Yes
Location: Seongnam-si, Korea
Has thanked: 7 times
Been thanked: 35 times
Contact:

Re: We dream a magic button for 3-D point cloud processing

Post by Joon »

Another crucial requirement of an efficient and accurate 3-D point cloud processing is the separation between the internal and the external parameters of object surfaces in space.

Object surfaces in space have shapes, sizes, positions, and rotations. The shape and size of an object surface will not be changed by the movement of the object surface. The shape and size are internal parameters of object surface in space, and, the position and rotation are external parameters.

(also, with the bundle adjustment of photogrammetry, we separate the camera parameters into the two groups. The internal parameters will not be changed substantially when the camera is being moved, except some correlations between parameters. The external parameters represent the movement of camera).

The separation of the object surface parameters into the two groups is of great advantage to 3-D point cloud processing. First, there is not the problem of large coordinate values. Second, the parameter correlations are minimized. Third, object surface can be recognized (identified) based on the shape and size, independently on the position and rotation. Fourth, the parameter separation is beneficial to applications. Finally, the 3-D point cloud processing is speedy and accurate.

Joon
Last edited by Joon on Mon Oct 22, 2018 12:15 am, edited 1 time in total.
sudo_ki
I have made 40-50 posts
I have made 40-50 posts
Posts: 44
Joined: Fri Mar 23, 2018 4:23 pm
6
Full Name: AJS
Company Details: Nomad
Company Position Title: Surveyor
Country: UK
Linkedin Profile: No

Re: We dream a magic button for 3-D point cloud processing

Post by sudo_ki »

I am always interested reading your posts.

Thanks
User avatar
Joon
V.I.P Member
V.I.P Member
Posts: 335
Joined: Wed Aug 21, 2013 8:01 pm
10
Full Name: Sung Joon Ahn
Company Details: CurvSurf
Company Position Title: Founder + CEO
Country: Republic of Korea
Linkedin Profile: Yes
Location: Seongnam-si, Korea
Has thanked: 7 times
Been thanked: 35 times
Contact:

Re: We dream a magic button for 3-D point cloud processing

Post by Joon »

sudo_ki wrote: Sun Oct 21, 2018 10:29 pm I am always interested reading your posts.

Thanks
Dear AJ Swanepoel,

Thank you for your interest.

I will be appending more logic of FindSurface SDK to this post, except sensitive original know-how's of CurvSurf.

Joon
User avatar
Joon
V.I.P Member
V.I.P Member
Posts: 335
Joined: Wed Aug 21, 2013 8:01 pm
10
Full Name: Sung Joon Ahn
Company Details: CurvSurf
Company Position Title: Founder + CEO
Country: Republic of Korea
Linkedin Profile: Yes
Location: Seongnam-si, Korea
Has thanked: 7 times
Been thanked: 35 times
Contact:

Re: We dream a magic button for 3-D point cloud processing

Post by Joon »

Edgels (edge elements) are ‘boundary points’ of 2-D regions in 2-D image.
Surfels (surface elements) are ‘boundary points’ of 3-D volumetric regions in 3-D space.

2-D cameras generate 2-D images. Edge detection in 2-D images extracts the ‘boundary points’ of 2-D regions.

3-D cameras generate 3-D point clouds, the ‘boundary points’ of 3-D volumetric regions.

What about the ‘boundary points’ of ‘boundary points’?
They are unstable and unreliable, dependent on the lateral resolution (point density) of sensor, environmental conditions, software algorithm used, etc. Useless!
The boundary points of boundary points.PNG

Some Thoughts on 2-D/3-D Information Processing

youtu.be/9kDixwHUWSY
You do not have the required permissions to view the files attached to this post.
Last edited by Joon on Wed Oct 31, 2018 10:28 am, edited 2 times in total.
User avatar
Joon
V.I.P Member
V.I.P Member
Posts: 335
Joined: Wed Aug 21, 2013 8:01 pm
10
Full Name: Sung Joon Ahn
Company Details: CurvSurf
Company Position Title: Founder + CEO
Country: Republic of Korea
Linkedin Profile: Yes
Location: Seongnam-si, Korea
Has thanked: 7 times
Been thanked: 35 times
Contact:

Re: We dream a magic button for 3-D point cloud processing

Post by Joon »

Dear Anybody,

Please find your ID & PW for FindSurface for Web below,
ID: YourCompanyName
PW: **********
(Please email to [email protected] for your ID/PW using your company/university email address).

Please do not let your ID & PW be known to others.

FindSurface for Web is a prototype web service for demonstrating the functionalities of FindSurface, without installing the FindSurface SDK on your computer.
FindSurface for Web is a prototype web service without optimization for web traffic.

Overview outlines the FindSurface for Web.
Interface explains the UI applied.
Step-by-Step shows the how-to-use to be followed.

The input parameters for FindSurface:
parameter_dialog.png

1. Accuracy:
The measurement accuracy of the input point cloud data. We recommend 1/2 ~ 2/1 of what you believe. FindSurface works based on your number input. FindSurface could analyze the input point cloud and estimate the number but would not.

2. Mean Distance:
The mean distance between neighboring points. We recommend 3~10 times larger value than the apparent value because of a possible large hole among object surfaces. In other words, a large hole inside object surface area decreases the mean density of inlier points (i.e., increases the mean distance of inlier points).
MeanDistance.png

3. Touch Radius:
Concerns for object scales/curvatures. Large value for large object, small value for small object. We recommend 1/4 ~ 2/1 of the object radius, dependently on the measurement accuracy. Large value for inaccurate data, small value for accurate data.

4. Radial Expansion:
The level of radial region expansion, controlling the thickness of the ROI volume. Large value for accurate data, small value for inaccurate data. A small value suppresses noises.
Region Growing.PNG

5. Lateral Extension:
The level of lateral elongation, controlling the length/width of the ROI volume. Large value for long/wide objects, small value for short/narrow objects. A small value shortens object length/width.

6. Gazing point:
You have to select a seed point among point cloud. If you could automate the selection of seed points, the whole process could be automated. The seed points corresponding to the object surfaces in a scene might be prepared by 2-D image segmentation. 3-D CAD data could also provide seed points. It’s up to yours, the application developers!

We will be distributing an App together with its source codes for probing the principles of FindSurface.
FindSurfaceParameterTest.png

You can probe the functional behavior of FindSurface by changing the program parameters.

Joon
You do not have the required permissions to view the files attached to this post.
Last edited by Joon on Thu Nov 01, 2018 6:04 am, edited 8 times in total.
User avatar
Joon
V.I.P Member
V.I.P Member
Posts: 335
Joined: Wed Aug 21, 2013 8:01 pm
10
Full Name: Sung Joon Ahn
Company Details: CurvSurf
Company Position Title: Founder + CEO
Country: Republic of Korea
Linkedin Profile: Yes
Location: Seongnam-si, Korea
Has thanked: 7 times
Been thanked: 35 times
Contact:

Re: We dream a magic button for 3-D point cloud processing

Post by Joon »

Now, we know that object curve/surface parameters can be divided into the two groups of internal and external parameters. The internal parameters represent the shape and size, and the external parameters represent the position and rotation of curve/surface in space.

We examine the position and rotation of curve/surface in space.

First, we look the formulas of 2-D line.
Definition of Line.GIF

1. Y = a X + b.
The most familiar formula of 2-D line. The parameter a is the slope, and b is the y-intersection of 2-D line. But, this formula cannot represent a vertical 2-D line. Furthermore, when the measurement data are remote from the origin, the value b is unstable and unreliable. The parameter b cannot represent the position of an object 2-D line remote from the origin (the problem of large coordinate values).

2. - X sin(k) + Y cos(k) - d = 0.
( -sin(k), cos(k) ) is the normal, and d the distance from the origin, and k the slope angle of a line. This formula is used by Hough transform of 2-D lines. It works well! But, only for 2-D lines in camera images with the bounded coordinate values up to few thousands. When the measurement data are remote from the origin, the value d is unstable and unreliable. The parameter d cannot represent the position of an object 2-D line remote from the origin (the problem of large coordinate values).

3. (X, Y) = (Xo, Yo) + u ( cos(k), sin(k) ).
( cos(k), sin(k) ) is the direction, and (Xo, Yo) is the position of line. (Xo, Yo) is the mass center of the measurement data. ( cos(k), sin(k) ) is the axis direction (eigenvector) of the minimum rotational inertia (eigenvalue) centered at (Xo, Yo). Once measurement data are given, k and (Xo, Yo) are the most stable and reliable representation of an object 2-D line.

Next, we will look the position/rotation of cylinder/cone in 3-D space.

Joon
You do not have the required permissions to view the files attached to this post.
Last edited by Joon on Mon Nov 19, 2018 10:47 pm, edited 2 times in total.
User avatar
Joon
V.I.P Member
V.I.P Member
Posts: 335
Joined: Wed Aug 21, 2013 8:01 pm
10
Full Name: Sung Joon Ahn
Company Details: CurvSurf
Company Position Title: Founder + CEO
Country: Republic of Korea
Linkedin Profile: Yes
Location: Seongnam-si, Korea
Has thanked: 7 times
Been thanked: 35 times
Contact:

Re: We dream a magic button for 3-D point cloud processing

Post by Joon »

We examine the positions of cylinder/cone in space.
Position of Cylinder and Cone.GIF

The rotation/direction of cylinder/cone is represented by the axis. The position of cylinder/cone is a point on axis. But, there are infinite number of axis points. We must define an axis point as the cylinder/cone position.

Many people have been defining the position of cylinder/cone on the XY-plane, or, at the nearest point from the origin, or, at the vertex of cone.

They are unstable and unreliable, if the measurement points are remote from them. In other words, they have nothing to do with the position of object cylinder/cone. A work on coordinate metrology and applications, based on such definitions of object cylinder/cone, is destined to be unsuccessful.

The position of object cylinder/cone should be defined inside the object cylinder/cone, then it will be stable and reliable: the nearest point on axis from the mass center of measurement points.

PS: Cylinder is a special instance of cone with zero vertex angle. It can be verified by making a paper cylinder/cone. The analogue of cylinder/cone, sphere/cylinder/torus will be posted at the end of this posting.

Joon
You do not have the required permissions to view the files attached to this post.
Last edited by Joon on Sat Dec 08, 2018 1:30 am, edited 3 times in total.
Post Reply

Return to “Modeling Software”