Differences

This shows you the differences between two versions of the page.

--- ece4580:module_pcd:localnormals [2017/02/04 13:23] – [Visualizing in Matlab] pvela
+++ ece4580:module_pcd:localnormals [2024/08/20 21:38] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
-====== Local surface Normal Estimation ======
+====== Local Surface Normal Estimation ======
-For some applications, not only is the local connectivity of a point region important, but so is the local surface normal for that particular neighborhood.  Naturally, then, many point cloud libraries invole the calculation of the local normal vectors, either over the entire point set or for a subset of the point set.  There are two related approaches for computing the normal vector.
+For some applications, not only is the local connectivity of a point region important, but so is the local surface normal for that particular neighborhood.  Naturally, then, many point cloud libraries involve the calculation of the local normal vectors, either over the entire point set or for a subset of the point set.  There are two related approaches for computing the normal vector.
+First, though, it is important to note that we are talking about local neighborhoods to the points in question.  Since the normals will be computed for local neighborhoods, it does not make much sense to actually compute the normal at every point.  Yes, it is possible and may be of utility for many algorithms. Here, we want to get a slightly coarse estimate of the normals over the entire point cloud.  What that means, is that a subset of points should be selected for computing these local normals, much like in the [[ECE4580:Module_PCD:LocalNormals#Matlab_Version|Matlab Version]] noted below.
+===== Getting a Local Neighborhood =====
+There are actually many ways to get a local neighborhood.  What we are really looking for in a neighborhood is a center point from the point cloud, plus the local surrounding points to that chosen center point.  As long as you identify a reasonable policy for establishing the center point and its local nearby points, you should be good to go.
+Some ideas are:
+  * Using the connectivity matrix.
+  * Using Matlab's internal $k$-nearest neighbors code to grab the local points.
+  * Using evenly chosen points from the point cloud list, then creating their neighborhoods.
+More details on the underlying algorithms go [[ECE4580:Module_PCD:LocalNeighborhood | here]].
 ===== PCA =====
-The principal component analysis, or PCA, approach does not really perform principal component analysis, however it does share that same processing up to a certain point.  PCA is effectively a method for finding a linear subspace that represents the data well. It involves eigenvalue/eigenvector analysis of the covariance matrix for a set of data.
+The principal component analysis, or PCA, approach does not really perform principal component analysis, however it does share that same processing up to a certain point.  PCA is effectively a method for finding a linear subspace that represents the data well. It involves eigenvalue/eigenvector analysis of the covariance matrix for a set of data.  Let $\Sigma$ be the covariance matrix of the data given by $P$ (a 3 x $n$ matrix of points).
+the eigenvalue decomposition of the covariance matrix is
+$$ \Sigma = V \Lambda V^T, \ \ \text{where}\ \ \Lambda = \text{diag}(\lambda_1, \lambda_2, \lambda_3).$$
+The eigenvalue $\lambda_i$ reflects the variance associated to the data along the direction given by its associated eigenvector $\vec e_i$.  Recall that the matrix $V$ consists of the eigenvectors
+$$ V = \left[ \begin{matrix} | & | & | \\ \vec e_i & \vec e_2 & \vec e_3 \\ | & | & | \end{matrix} \right].$$
+If the set $P$ is truly planar, then the normal vector to the points in $P$ should be aligned with the eigenvector with no variance (the eigenvalue such that $\lambda_i = 0$). In practice there will be noise or some curvature, so what is sought is the minimal eigenvalue and eigenvector.  Normally, eigenvectors can be complex valued, but for covariance matrices that is not the case.  They should be non-negative real values.
-NOTES HERE.
+Finding the smallest of the non-negative, real eigenvalues and taking its eigenvector gives the local surface normal.
+//Matlab Notes:// Implementation will involve proper use of the ''min'',''cov'', and ''eigs'' functions.
 ===== SVD =====
@@ Line 21: / Line 38: @@
 Naturally, if we are given a small set $P$ and would like to compute its normal, then the first step would be to center the data.  After that computation of the SVD followed by extraction of the smallest singular vector gives the necessary estimate. By definition of the SVD, this vector is already unit length, so we've got the answer.
+//Matlab Notes:// In slightly older Matlab versions, implementation will involve proper use of ''bsxfun'' to perform the mean offset computation (in one line of code). For R2016b and later, Matlab allows for implicit expansion of array operations, which means that it will automatically invoke ''bsxfun'' given the coded operation ([[https://www.mathworks.com/help/matlab/ref/bsxfun.html|discussed here]]). Be careful about whether Matlab wants/returns things row-wise or column-wise.
 ===== Visualizing in Matlab =====
@@ Line 31: / Line 50: @@
 ===== Matlab Version =====
-Matlab has its own internal routine for performing the same operation. It is called ''pcnormals'' and its operation is sort of described in this [[https://www.mathworks.com/help/vision/ref/pcnormals.html|tutorial]].
+Matlab has its own internal routine for performing the same operation. It is called ''pcnormals'' and its operation is sort of described in this [[https://www.mathworks.com/help/vision/ref/pcnormals.html|tutorial]]. The tutorial can be followed as a check of your code, but should not be used as the solution to the weekly activity (unless explicitly noted).
 ---------------------