| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| ece4580:module_pcd:localneighborhood [2017/02/21 12:56] – [Using Greedy Point Selection] pvela | ece4580:module_pcd:localneighborhood [2024/08/20 21:38] (current) – external edit 127.0.0.1 |
|---|
| where ''source'' is the set of points that we wish to compute the nearest distances for, as well as generate the label assignment. The set of points in ''target'' are the ones we want to check to nearest distance against. All points in the ''source'' set with the same index belong to the same neighborhood. The point in that neighborhood with the smallest distance to the target point (from the target set at the location ''index'') should be used as the central point. One could try to use the actual target point, but some sub-sampling algorithms also change the data (for example through local averaging). | where ''source'' is the set of points that we wish to compute the nearest distances for, as well as generate the label assignment. The set of points in ''target'' are the ones we want to check to nearest distance against. All points in the ''source'' set with the same index belong to the same neighborhood. The point in that neighborhood with the smallest distance to the target point (from the target set at the location ''index'') should be used as the central point. One could try to use the actual target point, but some sub-sampling algorithms also change the data (for example through local averaging). |
| |
| //Implementation:// Matlab has an internal point cloud routine for [[https://www.mathworks.com/help/vision/ref/pcdownsample.html|down sampling]] a point cloud, which is one way to do it. Another is to simply sub-sample by grabbing every $n$-th index from the set of all points, much like in the [https://www.mathworks.com/help/vision/ref/pcnormals.html|Matlab example]] for point cloud normals. Of course, the Matlab code is not optimized for use in the pipeline just described and there is a better, shorter way of doing it, but the main idea holds. | //Implementation:// Matlab has an internal point cloud routine for [[https://www.mathworks.com/help/vision/ref/pcdownsample.html|down sampling]] a point cloud, which is one way to do it. Another is to simply sub-sample by grabbing every $n$-th index from the set of all points, much like in the [[https://www.mathworks.com/help/vision/ref/pcnormals.html|Matlab example]] for point cloud normals. Of course, the Matlab code is not optimized for use in the pipeline just described and there is a better, shorter way of doing it, but the main idea holds. |
| |
| //Warning:// Many students get caught up on errors that arise from not reading the documentation well. In particular, Matlab and other implementations are not always consistent about how data should be organized when being used as arguments to functions. For vectorial arrays, you need to check if the data is expected to be **row-wise** or **column-wise**. Sending the wrong way leads to algorithm mistakes though the code is syntactically correct. | //Warning:// Many students get caught up on errors that arise from not reading the documentation well. In particular, Matlab and other implementations are not always consistent about how data should be organized when being used as arguments to functions. For vectorial arrays, you need to check if the data is expected to be **row-wise** or **column-wise**. Sending the wrong way leads to algorithm mistakes though the code is syntactically correct. |
| ===== Using Greedy Point Selection ===== | ===== Using Greedy Point Selection ===== |
| |
| This is sort of the dual to the Matlab nearest neighbor search process and more in line with the connectivity matrix approach. Matlab has a function called ''rangesearch'' that finds all the points in a source set that are within range of points in the target set. The return values are cell arrays that give the necessary connectivity and distance information. Since the maximum radius as specified when invoking the function, only the index cell sets are needed. They provide the connectivity information. As noted in the [[Matlab documentation|https://www.mathworks.com/help/stats/rangesearch.html]] for the function, its goes as follows: | This is sort of the dual to the Matlab nearest neighbor search process and more in line with the connectivity matrix approach. Matlab has a function called ''rangesearch'' that finds all the points in a source set that are within range of points in the target set. The return values are cell arrays that give the necessary connectivity and distance information. Since the maximum radius as specified when invoking the function, only the index cell sets are needed. They provide the connectivity information. As noted in the [[https://www.mathworks.com/help/stats/rangesearch.html| Matlab documentation]] for the function, its goes as follows: |
| <code> | <code> |
| [idx, dists] = rangesearch(source, target, radius) | [idx, dists] = rangesearch(source, target, radius) |
| Radius selection for locality calculations has been studied a fair amount, with many folk coming up with different rules. Surely trying to figure out what this number should be by guess and checking is probably not optimal, and definitely does not lend itself to automation. Here are a couple of ideas: | Radius selection for locality calculations has been studied a fair amount, with many folk coming up with different rules. Surely trying to figure out what this number should be by guess and checking is probably not optimal, and definitely does not lend itself to automation. Here are a couple of ideas: |
| |
| - Compute the median distance. For that, the ''pdist'' function could be useful. | - Compute the median distance of all pair-wise point distances. For that, the ''pdist'' function could be useful. |
| - Compute the average distance of only the $k$-nearest neighbors of a point set to itself. Basically, the $k$-nearest neighbors are sought for each point, then all of the distances are collected for these neighbors. Their mean is then computed (or median if you'd prefer). No for loops should be necessary. Matlab's ''knnsearch'' method does most of the work. A couple lines later, you are good to go. | - Compute the average distance of only the $k$-nearest neighbors of a point set to itself. Basically, the $k$-nearest neighbors are sought for each point, then all of the distances are collected for these neighbors. Their mean is then computed (or median if you'd prefer). No for loops should be necessary. Matlab's ''knnsearch'' method does most of the work. A couple lines later, you are good to go. \\ The value $k$ should be chosen so that you almost always get the number of neighbors you need with the radius chosen. Say you need 10 points, then a good value for $k$ would be something like 15. It should be that more than 70% of the time, you will get 10 points. |
| |
| -------------------------- | -------------------------- |
