We dream a magic button for 3-D point cloud processing
- Joon
- 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
Measurement Error Model
Measuring the coordinates of a spatial point goes through several steps of hardware and software process. Each of the processing steps has own statistical and probabilistic properties. Gaussian model is the statistical and probabilistic model of the overall processing steps because multiple processing steps can be modeled as a single Gaussian process as the number of processing steps increases.
According to the Gaussian process assumed above, a measurement point is a probable observation of an unknown object point lying next to the measurement point. The distance between the measurement point and an unknown object point is an unknown measurement error. The maximum likelihood estimation substitutes an unknown object point by the measurement point to minimize the measurement error down to zero.
Once we have measured an object curve/surface, we are assuming a model curve/surface and estimating the model parameter values. The minimum distances between the measurement points and the model curve/surface are the measurement errors. The maximum likelihood estimation minimizes the sum of the squared error distances. The estimated model curve/surface substitutes an unknown object curve/surface.
How to minimize the sum of the squared error distances will be outlined in the next post.
Measuring the coordinates of a spatial point goes through several steps of hardware and software process. Each of the processing steps has own statistical and probabilistic properties. Gaussian model is the statistical and probabilistic model of the overall processing steps because multiple processing steps can be modeled as a single Gaussian process as the number of processing steps increases.
According to the Gaussian process assumed above, a measurement point is a probable observation of an unknown object point lying next to the measurement point. The distance between the measurement point and an unknown object point is an unknown measurement error. The maximum likelihood estimation substitutes an unknown object point by the measurement point to minimize the measurement error down to zero.
Once we have measured an object curve/surface, we are assuming a model curve/surface and estimating the model parameter values. The minimum distances between the measurement points and the model curve/surface are the measurement errors. The maximum likelihood estimation minimizes the sum of the squared error distances. The estimated model curve/surface substitutes an unknown object curve/surface.
How to minimize the sum of the squared error distances will be outlined in the next post.
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:26 am, edited 1 time in total.
- Joon
- 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
Principal Component Analysis (PCA)
PCA is a linear least-squares method for fitting linear models (i.e., 2-D line, 3-D line, or plane) to data points. PCA determines the parameter values of linear models by minimizing the sum of the squared error distances between the model and the data points.
The rotational inertia of a set of data points about an axis is the sum of the squared distances of data points from the axis. Given an axis direction, the rotational inertia is minimized by placing the axis onto the mass center of data points (parallel-axis theorem). The mass center is the position of the linear model to be fitted.
There are max three orthogonal axis directions (eigenvectors) corresponding to the maximum, medium, and minimum rotational inertia (eigenvalues). The axis direction corresponding to the minimum rotational inertia is the direction of the 3-D line (or 2-D line) we look for. And, the axis direction corresponding to the maximum rotational inertia is the normal of the plane (or 2-D line) we look for. Given a set of data points, the best direction of 3-D line (or 2-D line) is the worst normal of plane (or 2-D line), and vice versa.
The orthogonal distance fitting (ODF) for curve/surface will be outlined in the next post.
PCA is a linear least-squares method for fitting linear models (i.e., 2-D line, 3-D line, or plane) to data points. PCA determines the parameter values of linear models by minimizing the sum of the squared error distances between the model and the data points.
The rotational inertia of a set of data points about an axis is the sum of the squared distances of data points from the axis. Given an axis direction, the rotational inertia is minimized by placing the axis onto the mass center of data points (parallel-axis theorem). The mass center is the position of the linear model to be fitted.
There are max three orthogonal axis directions (eigenvectors) corresponding to the maximum, medium, and minimum rotational inertia (eigenvalues). The axis direction corresponding to the minimum rotational inertia is the direction of the 3-D line (or 2-D line) we look for. And, the axis direction corresponding to the maximum rotational inertia is the normal of the plane (or 2-D line) we look for. Given a set of data points, the best direction of 3-D line (or 2-D line) is the worst normal of plane (or 2-D line), and vice versa.
The orthogonal distance fitting (ODF) for curve/surface will be outlined in the next post.
You do not have the required permissions to view the files attached to this post.
- Joon
- 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
Orthogonal Distance Fitting (ODF)
ODF is a nonlinear least-squares method for curve/surface fitting. ODF determines the parameter values of model curve/surface (e.g., circle, ellipse, parabola, sphere, cylinder, cone, etc.) by minimizing the sum of the squared error distances between the model and the data points.
Except some curves and surfaces (e.g., circle, sphere, cylinder, cone, torus) composed of linear or circular elements, the distance between the model curve/surface and a data point cannot be described in closed-form. Thus, ODF is a twofold nonlinear minimization problem. Not only the sum of the squared error distances but also every individual error distance between the model curve/surface and data points must be minimized.
Fitting a Sine Curve
youtu.be/XgCytTYPoIY
Fitting a Heart Curve
youtu.be/g1l00Yl_vu8
Superquadric Fitting
youtu.be/dZ-sckgb688
If you are interested in more details of ODF, please refer to my monograph “Least Squares Orthogonal Distance Fitting of Curves and Surfaces in Space”, Springer, 2004. This book describes in detail two ODF algorithms for implicit curve/surface and three ODF algorithms for parametric curve/surface.
The next post is about the canonical form of curve/surface, describing the shape and size of curve/surface independently on the position and rotation.
Joon
PS: The basic principles of ODF algorithms were developed early 2000’s, almost 20 years ago. But, the ODF algorithms could not have been used for industrial applications of 3-D measurement technique. First, the computing power of PC was not adequate to utilize the ODF algorithms for industrial applications. Second, the memory handling was not optimized. Third, the initial value problems were not cleverly solved for cone and torus. And, the automatic recognition of object shapes was incomplete.
ODF is a nonlinear least-squares method for curve/surface fitting. ODF determines the parameter values of model curve/surface (e.g., circle, ellipse, parabola, sphere, cylinder, cone, etc.) by minimizing the sum of the squared error distances between the model and the data points.
Except some curves and surfaces (e.g., circle, sphere, cylinder, cone, torus) composed of linear or circular elements, the distance between the model curve/surface and a data point cannot be described in closed-form. Thus, ODF is a twofold nonlinear minimization problem. Not only the sum of the squared error distances but also every individual error distance between the model curve/surface and data points must be minimized.
Fitting a Sine Curve
youtu.be/XgCytTYPoIY
Fitting a Heart Curve
youtu.be/g1l00Yl_vu8
Superquadric Fitting
youtu.be/dZ-sckgb688
If you are interested in more details of ODF, please refer to my monograph “Least Squares Orthogonal Distance Fitting of Curves and Surfaces in Space”, Springer, 2004. This book describes in detail two ODF algorithms for implicit curve/surface and three ODF algorithms for parametric curve/surface.
The next post is about the canonical form of curve/surface, describing the shape and size of curve/surface independently on the position and rotation.
Joon
PS: The basic principles of ODF algorithms were developed early 2000’s, almost 20 years ago. But, the ODF algorithms could not have been used for industrial applications of 3-D measurement technique. First, the computing power of PC was not adequate to utilize the ODF algorithms for industrial applications. Second, the memory handling was not optimized. Third, the initial value problems were not cleverly solved for cone and torus. And, the automatic recognition of object shapes was incomplete.
You do not have the required permissions to view the files attached to this post.
Last edited by Joon on Sat Dec 22, 2018 10:16 am, edited 2 times in total.
- Joon
- 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
Insert to Oct. 09, 2018 Post.
"
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.
"
Do you have ever counted numbers to 1,000 in series starting from 1?
One, two, three, four, …
Joon
"
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.
"
Do you have ever counted numbers to 1,000 in series starting from 1?
One, two, three, four, …
Joon
- Joon
- 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
Early 90’s, I had been learning the neural networks and but lost interest in them, because they had been promising too misty without concrete theoretical bases from my viewpoint (The current machine learning (ML) techniques of 2018 may also be going the similar way as has been till, at least with the 3-D point cloud processing).
Then, I had been working on 3-D measurement techniques, specifically on the stripe projection method by using the ABW-Projector. And, I had my hands on photogrammetry: Systematic geometric image measurement errors of circular object targets: Mathematical formulation and correction. Dr. R. Kotowski and Dr. J. Dold were my consultant.
After I had been getting point clouds by using my own 3-D measuring machine, I asked me what I can do with these point clouds. Nothing! Above all, what is a measurement point? I expanded the applied numerical mathematics I put use to "Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola". The results are the algorithms of Orthogonal Distance Fitting (ODF).
Then, I had been working on 3-D measurement techniques, specifically on the stripe projection method by using the ABW-Projector. And, I had my hands on photogrammetry: Systematic geometric image measurement errors of circular object targets: Mathematical formulation and correction. Dr. R. Kotowski and Dr. J. Dold were my consultant.
After I had been getting point clouds by using my own 3-D measuring machine, I asked me what I can do with these point clouds. Nothing! Above all, what is a measurement point? I expanded the applied numerical mathematics I put use to "Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola". The results are the algorithms of Orthogonal Distance Fitting (ODF).
You do not have the required permissions to view the files attached to this post.
Last edited by Joon on Tue Nov 20, 2018 6:19 am, edited 7 times in total.
- Joon
- 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
I had developed a circular coded target with patent. The patent together with C source codes was bought by INPHO GmbH to improve the 3-D measurement accuracy and automate the measurement process of the random pattern method.
In order to improve the image measurement accuracy of object circular targets, new algorithms were developed:
In order to improve the image measurement accuracy of object circular targets, new algorithms were developed:
- Orthogonal distance fitting (ODF) of image ellipses
- Sub-pixel accurate edge detection of the contours of image ellipses
- Compensating the eccentricity errors of image ellipses
- Optimally discretizing the coding elements around the center of object target.
You do not have the required permissions to view the files attached to this post.
Last edited by Joon on Sat Dec 08, 2018 4:49 am, edited 3 times in total.
- Joon
- 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
Canonical form of curve/surface
We explore the separation of curve/surface parameters into the two groups of internal and external parameters.
We introduce a model coordinate frame xyz referenced to the machine coordinate frame XYZ. The coordinate transformation between the two coordinate frames is
X = inv(R) x + Xo
or
x = R ( X – Xo ).
Xo is the position of the frame xyz and the rows of the rotational matrix R are the direction cosines of xyz-axes referenced to the frame XYZ. When a model curve/surface is defined in the frame xyz, Xo and R represent the position and rotation of the model curve/surface referenced to the frame XYZ. The coordinate transformation is common to all model curves/surfaces.
Now, we can define a model curve/surface in the frame xyz by using only a few parameters representing the shape and size of the model curve/surface (canonical form). We name the shape and size parameters as internal parameters and the position and rotation parameters as external parameters.
We explore the separation of curve/surface parameters into the two groups of internal and external parameters.
We introduce a model coordinate frame xyz referenced to the machine coordinate frame XYZ. The coordinate transformation between the two coordinate frames is
X = inv(R) x + Xo
or
x = R ( X – Xo ).
Xo is the position of the frame xyz and the rows of the rotational matrix R are the direction cosines of xyz-axes referenced to the frame XYZ. When a model curve/surface is defined in the frame xyz, Xo and R represent the position and rotation of the model curve/surface referenced to the frame XYZ. The coordinate transformation is common to all model curves/surfaces.
Now, we can define a model curve/surface in the frame xyz by using only a few parameters representing the shape and size of the model curve/surface (canonical form). We name the shape and size parameters as internal parameters and the position and rotation parameters as external parameters.
You do not have the required permissions to view the files attached to this post.
- Joon
- 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
CurvSurf's Capital/fund raising:
Oct. 2013: 11.3 Mio. KRW for 2,260 shares (Company founding with ca. 4 USD/share)
Oct. 2015: 1,450 Mio. KRW for 290 shares (1st private investment with ca. 4,000 USD/share)
Jan. 2018: 570 Mio. KRW for 38 shares (2nd private investment with ca. 12,000 USD/share)
3rd investment with ca. 30,000 USD/share is on the way.
Oct. 2013: 11.3 Mio. KRW for 2,260 shares (Company founding with ca. 4 USD/share)
Oct. 2015: 1,450 Mio. KRW for 290 shares (1st private investment with ca. 4,000 USD/share)
Jan. 2018: 570 Mio. KRW for 38 shares (2nd private investment with ca. 12,000 USD/share)
3rd investment with ca. 30,000 USD/share is on the way.
- Joon
- 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
Measure the Geometry
Monetizing the geometric reality
youtu.be/O9m8KIp3cMQ
Early 2019, CurvSurf will be releasing 'FindSurface for Android' together with the source codes of a simple AR application. A potential use case of 'FindSurface for Android' is overlaying 3-D CAD information onto the live-video on site.
'FindSurface for Android' will extend the AR playground from planes to curved surfaces.
Do you have ever noticed that the current AR applications are built on a reference plane?
Floor, wall, street, ground, table-top, etc. Joon
Monetizing the geometric reality
youtu.be/O9m8KIp3cMQ
Early 2019, CurvSurf will be releasing 'FindSurface for Android' together with the source codes of a simple AR application. A potential use case of 'FindSurface for Android' is overlaying 3-D CAD information onto the live-video on site.
'FindSurface for Android' will extend the AR playground from planes to curved surfaces.
Do you have ever noticed that the current AR applications are built on a reference plane?
Floor, wall, street, ground, table-top, etc. Joon
You do not have the required permissions to view the files attached to this post.
- Joon
- 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
Local Curvature Analysis of Point Cloud
Locally nonsingular (i.e. differentiable) surfaces can be classified as one of the 4 surface types: planar, parabolic, elliptic, or hyperbolic.
Most man-made object surfaces are composed of planes, spheres, cylinders, cones, and tori:
- Plane is planar
- Sphere is elliptic
- Cylinder is parabolic
- Cone is parabolic
- Torus is locally elliptic, hyperbolic, or parabolic (seldom).
Then, through the local curvature analysis, we can assume the local shape of the point cloud measured:
- Planar --> plane
- Parabolic --> cylinder or cone
- Elliptic --> sphere or torus
- Hyperbolic --> torus.
From the local principal curvatures and axes of point cloud, we can determine the parameter values of the local object surface: size/radius, vertex angle, position, and rotation. The parameter values are then used as the initial values for the nonlinear ODF (orthogonal distance fitting).
By utilizing the analogue between cylinder/cone, sphere/cylinder/torus, we can automate the object surface recognition:
- A cone with zero vertex angle is a cylinder
- A torus with zero mean radius is a double-layer sphere (spindle torus)
- A small portion of torus with infinite mean radius is a cylinder.
Joon
Locally nonsingular (i.e. differentiable) surfaces can be classified as one of the 4 surface types: planar, parabolic, elliptic, or hyperbolic.
Most man-made object surfaces are composed of planes, spheres, cylinders, cones, and tori:
- Plane is planar
- Sphere is elliptic
- Cylinder is parabolic
- Cone is parabolic
- Torus is locally elliptic, hyperbolic, or parabolic (seldom).
Then, through the local curvature analysis, we can assume the local shape of the point cloud measured:
- Planar --> plane
- Parabolic --> cylinder or cone
- Elliptic --> sphere or torus
- Hyperbolic --> torus.
From the local principal curvatures and axes of point cloud, we can determine the parameter values of the local object surface: size/radius, vertex angle, position, and rotation. The parameter values are then used as the initial values for the nonlinear ODF (orthogonal distance fitting).
By utilizing the analogue between cylinder/cone, sphere/cylinder/torus, we can automate the object surface recognition:
- A cone with zero vertex angle is a cylinder
- A torus with zero mean radius is a double-layer sphere (spindle torus)
- A small portion of torus with infinite mean radius is a cylinder.
Joon
You do not have the required permissions to view the files attached to this post.