-
Notifications
You must be signed in to change notification settings - Fork 0
Algorithm improvements to KD-Tree module: applications to ICP (Pranjal Kumar Rai) #1
Comments
Student: @pranjal-rai Main mentor: @jlblancoc |
Hi @jlblancoc and @feroze, Thank you for giving me the opportunity to work on this project. I am planning to start reading the existing code of nanoflann from the next week. |
👍 !! Since this project will be all about efficiency, I would start preparing, in your repo/fork, one subdirectory with a suite of benchmarks: executable programs that repeat certain operations and measure the time ellapsed, in microseconds or milliseconds; typically, one operation is repeated N times, then the time divided by N to have a better estimate. In our case, tasks to be benchmarked are, at least, building a KD-tree, and querying it for some random points. A couple pointcloud datasets could be added from some public repos as test cases. You can take a look at the sources of |
While playing with the code I found a possible bug, I have created a pull request. |
Great! I've just answered you there. |
|
I think that the current KD-Tree index class should remain more or less as is, and tailored to static datasets. A new class should be created for the dynamic algorithm, since, if I recall it right, it requires having an array/vector of kd-tree indices, so this later class would use "composition" with the former one. On the two approaches: I would prefer having this new class being unique. Then having some
Yes, sure! |
Hi @pranjal-rai ! How are you doing with the preliminary work on the datasets and/or performance tests? Do you need any help? PS: Please, keep your fork up-to-date to the latest accepted pull-requests in the main nanoflann repo. |
Hi @jlblancoc I forked flann and experimented with the code a bit. I noticed that there are two codes of our interest at this time.
I quickly looked through the tree building procedure of both the codes. I think they are using different approaches for building and searching the tree. I coded the rebuild threshold approach for nanoflann but I found some cases where the proposed algorithm fails for nanoflann but passes for the general flann code. I am not sure if rebuild threshold approach can be applied to nanoflann. Right now I am stuck with this part. I also wrote a rough code for logarithmic approach, the performance of this method is much better than the one in the general flann code for large number of dynamic insertions. I have updated my forked repository. |
Hi @jlblancoc I have implemented logarithmic approach for dynamic support. I have created a new branch with proposed changes. I have tested it using random point clouds. For now I have added just one example file, I will add more once you review it. |
Hi @jlblancoc I compared the index building time requirement for nanoflann and flann for inserting points dynamically. Flann is based on the rebuild threshold approach whereas nanoflann uses logarithmic approach. |
Hi @jlblancoc Is there any comment on the logarithmic approach implementation? Out of these only FLANN supports dynamic insertions/deletions. So I plan to illustrate the dynamic support comparison only between FLANN and nanoflann. I will illustrate other comparison results for all the four libraries along with nanoflann. |
Hi! You made good progress, congrats! If you go on at this pace, I'm sure we'll achieve the project goals. Some quick answers:
Good results! Another issue is: inserting points one by one is a good test case in general, but in mobile robotics it's far more common to insert them in batches of 100s to 1000s (for 2D or 3D LiDAR scanners, respectively). Probably the general trend of the graphs won't change but we will be reporting more realistic total time costs (many seconds seem too much, probably that's only because of the 1-by-1 approach). Give it a try to see how much results are affected...
I haven't compiled and tested it, just visually inspected the code for now. Firstly, the approach of defining the new classes seems reasonable. 👍 In any case, common code could be refactored anyway via the CRTP. Let me know if you want to learn more on this method. One more thing: The vector here is expected to grow as new points are added, right? When we move to the range of millions of points, resizing a std::vector has an important cost due to reallocations. Consider using Also: in connection with the robotics applications, please consider adding an alternative
👍 |
@jlblancoc thanks for the pointers. I will start working on all the pointers and get them done ASAP. |
Hi @jlblancoc
The results change significantly when points are added in chunks of size 100, our time is nearly the same because as per theory the points in logarithmic approach are still added one by one but in flann time improves because now it requires much lesser number of rebuilds.
I compared the time taken for std::deque and std::vector. The latter performs slightly better. I am not sure about the reason for this.
I have removed addPoint and added a new function addPoints to insert multiple elements at a time. I have committed the changes in my branch.
Most of the functions are common between the two classes. I duplicated the functions as I had to modify some of the existing functions to include deletion support because this feature was missing in static index adaptor. I am still working on this part and I will try to create one common shared base class for the functions which are exactly same. Rebuild Threshold Approach Regarding this method, is there any paper/resource which validates its correctness. I coded this part but it fails for some cases. The failure itself seems genuine. The thing is when a new point is added dynamically without rebuilding the index it is not assured that it will be at the same location in the tree where it would have been if the index was rebuilt from scratch. So when we perform the nearest neighbour query on the tree this particular branch which contains the dynamically inserted point might get ignored even though it was closest to the query point. I came across many such examples. |
Good! Lots of results in a short time.
What method of flann are you comparing to? The "A"NN stands for approximate, so that may be also the answer to: Rebuild Threshold Approach
I don't have right now any reference at hand, but thresholding may be valid only to generate approximate trees. In that case, we can't compare an "exact vs approximate" algorithms, at least, not without making clear that they are different.
👍 Remember trying to use CRTP to avoid virtual functions, which may (depends on compiler and many details) come with a runtime cost. |
Hi @jlblancoc
Even I think that rebuild threshold method can only be applied to approximate nearest neighbour searches. |
Hi @jlblancoc
|
Hi @pranjal-rai ! Apart of a comment I made regarding the documentation of classes, I'm happy with your approach! No virtual methods means efficient code... 👍
Sorry, I missed something... what two methods? Logarithm method and threshold?
Since we aim at exact NN, just remove the method that is an approximation. Also: how are you doing with the bencharking application from real pointcloud datasets? I couldn't find it in your branch... I saw your new example, and it's good. Note that since we don't want large files in Git, if we want to use a dataset it might be better to either: (a) edit the dataset so only a small file is added to the repo, or (b) use CMake to download the dataset files from Internet. If you hasn't found datasets, let me know and I'll give you some. Cheers. |
This is a kind reminder to all GSoC students and mentors According to GSoC FAQ, students are supposed to devote 30+ hours per week to their assigned project. This amounts to 6h/day (Mon-Fri) or 4.3h/day (Mon-Sun), or any equivalent distribution given the flexibility to work on your own schedule. Clearly failing to such a commitment may be a reason to fail in the monthly evaluations, since that information was clear at the time of applying to GSoC. It's difficult to convert hours into GitHub commits, but as a rule of dumb, there should at least a substantial daily commit during each week working day, that is, roughly 5 substantial commits per week. This is a general rule, and mentors may be flexible depending on the difficulty and nature of each project. The first evaluation will start June 26-30. |
Hi @jlblancoc I have added the documentation for all the classes.
I proposed two different implementations for rebuild threshold method. I have implemented both but it seems that the rebuild threshold approach is valid only for approximate nearest neighbour searches. So this will not work for our purpose.
I think it will be better to use CMake to download the dataset files from Internet because we need to run tests on large files and editing the dataset won't be a feasible solution. I will update you with the real pointcloud datasets ASAP. If you have any suggestion for datasets, please share it with me. |
Sure! Some datasets:
|
Hi @jlblancoc We now have the support for dynamic point clouds. I have tested the implementation and it looks good to me. We can verify it again once you are done with executables for testing. Also: As the rebuilding threshold approach does not work for us, so should I push these changes to my repo in a new branch or just leave it?
I am now planning to create a GUI based application to perform all the benchmarking tests. This can either be done in MATLAB or Python with Tkinter (preferably latter, as I don't have much experience with Tkinter and I want to learn more about it). I will first design the tool with all the basic functionalities and then start with the coding part after the first evaluation. We can also add an option for running the codes directly for users who wish to perform intensive testing with their own parameters. Also, do I need to make a report for the first evaluation? |
You could push it to a separate branch so we can take a look at it just for evaluation purposes for this first evaluation period; then remove it after some more weeks if will be definitively useless. Ok, go on with the GUI for benchmarking. Please, let me know the list of exact benchmarks you plan to support in it. I think we've discussed this in the past, but it's good to revisit it again ;-)
Nope, we'll just review based on public discussion (this thread!) and your commit. Might come back to ask you for some doubts if we need it. |
Hi @jlblancoc I have added both approaches for rebuild threshold method as separate branches [1], [2]. Right now I have added the support for dynamic insertions by modifying the existing class itself without duplicating the class. I will structure the code properly if we plan to use it in the future. List of benchmarks:
|
All good.
I'm not sure about your plans to go on working with branches, but if
the Logarithm method seems stable, you can merge it now to your fork's
master... do you agree? Or do you have other plans? I mention it
because in that way the next step (starting with benchmarking) could
be carried out in master...
|
Hi @jlblancoc Sure. I will go ahead and merge the Logarithm Method branch into master. I will then create another branch from master for benchmarking which can be merged later. |
Hi @jlblancoc I have merged Logarithmic Method into master and created another branch Benchmarking from master in which I will start working on the benchmarking tool. I had some doubts regarding the work now. |
Hi,
That's a good idea. Only, make sure of using cmake to download and build
the 3rd party libraries. Read on this command:
https://cmake.org/cmake/help/v3.0/module/ExternalProject.html
|
Hi @pranjal-rai ! Also, I noticed that the code refactoring to move all shared code down to the base class
In general, all functions ( |
One fundamental thing that seems to be missing in your contributions so far is this: we have a great benchmark to test the computational efficiency of different metrics / algorithms; that's all good. But there are no unit tests that verify that the output of those methods is correct (!!). Please, consider adding new unit tests to Comparing the nearest point according to KD-tree queries for:
against the output of the brute force algorithm (so, please use a relatively small number of points). As you can see, the current code checks this a number of times for random datasets to assess that the kd-tree always outputs the correct answer, for the L2 metric. Duplicated code like definitions of auxiliary dataset classes, functions to generate a random point cloud (of the different kinds: XYZ, Quaternion,...) could be better refactored from their current Again, avoid code duplication at all cost!! It's evil! 😈 |
Again on code duplication: |
Now, regarding the topic of The point is that metrics must be able to be obtained element-wise for the kd-tree to work. inline DistanceType accum_dist(const U a, const V b, int idx) const In short: summing So, this unfortunately means that the "acos()" metric must be ruled out, since I can hardly think of a way to compute it element-wise... For L1, L2, SO(2) the implementation of For SO(3)-InnerProdQuat: I thought of this solution:
inline DistanceType evalMetric(const T* a, const size_t b_idx, size_t size) const {
DistanceType result = DistanceType();
for (int i=0; i<size; ++i) {
const DistanceType diff = a[i] * data_source.kdtree_get_pt(b_idx, i);
result += diff;
}
result = 1 - std::abs(result); The accum_dist() for idx=0 could include the As a replacement for the acos-innerProduct metric, we could implement the Frobenius norm: Please, unroll the expression (with paper and pencil... or with a symbolic package of Matlab, Mathematica or any other software) for the trace(R^t * Ri) you will see it's the sum of 3 terms, each of them a function of the 4 quaternion components. I think that this metric is suitable for being added up element by element, although some refactoring might be needed in the function parameters to pass not only the (a[i],b[i]) elements, but the entire vectors (a,b). PS: If time permits, please take note of this task that would be another great add-on: add more unit tests, one per metric class (L1,L2,SO2,...) and that, instead of building a complex dataset, etc. it just verifies that the sum of PS2: Ask in case you have doubts... which would be more than understandable at this point! ;-) |
Hi everyone! Then I wonder, must the distance be an actual distance (positive)? I ask this because if you use alone this value can go from -3 to +3. A simple solution if this is an issue would be then to take each term in instead to have a distance that goes from 0 to +6. Best, |
HI @jlblancoc
Now moving on to SO(3)-InnerProdQuat
I think there is a problem in this solution. Example: Please correct me if I am wrong. |
I have added |
|
@jbriales thanks a lot! 👍
I noticed your quaternions are not unitary (|q1| = 0.659 ??) and think I found a bug in your code generation for random quaternions, please check my comment on your commit. Giving it a second thought... I spoke a senseless thing yesterday: we CAN'T force (qx,qy,qz) to always be positive! It's the axis of rotation, we must cover quadrants with negative values no matter qw (the first quaternion element) is allowed to be negative or not. This means that, apparently, there is no straighforward valid SO3 metric that can be built up element-by-element, and still complying with the kd-tree algorithm of assuming that adding the distance increment for one dimension always make distances to increase. There is a final, valid alternative for SO(3): using the L2 (square norm) of the unit quaternion itself. That is, working with the quaternion as if it was a common 4-length vector in Euclidean space. This implies enforcing qw to be always positive, so there is no chances of having the same rotation described by different quaternions. Please, rename and rewrite the SO3 metric so it works like this (yes: it would be identical to L2 for now!!). We could think of something better in the future... If you are done with this, then the next most important thing to do before the end of GSoC would be IMO the unit tests I mentioned above (including the new tests, and the refactoring of common code among examples and tests). Keep pushing! ;-) |
Hi @jlblancoc
Actually I made a typo in comments, w in q1 is actually -0.75 not -0.075. Sorry. I have now updated the quaternion generation code to use the approach you suggested. Right now I am using any random angle between [0, PI] so that w remains positive and x, y, z can be of any sign. I ensured that I am generating unit quaternions. I will now start working on following tasks.
|
Great! Come back if you have any further doubt.
|
Hi @jlblancoc I have added unit tests to validate the following: I will now start working on removing the duplicate codes. |
|
I have added unit tests and also removed duplicate codes from examples and unit tests. I will clean and document all the codes by tomorrow. |
Hi @jlblancoc I have cleaned the codes and moved some common functions to base class. What do we do now? |
Great work! I'll review the code changes later today.
In the meanwhile, you can merge all the changes in your master branch, and
open a pull request against the original repo.
|
Hi @jlblancoc I have created a PR but building flann requires administrative permissions and the tests fail because of this reason. What should I do for this? |
I fixed the previous issue. All other tests except this complete successfully now. |
Good! I think it's a problem of the external project, so let's ignore it. cmake $SRC_DIR -DBUILD_BENCHMARKING=OFF Obviously, you should add some "if()"s as well inside the CMake scripts to detect that new CMake variable and skip the external projects and the benchmarking app if it's set. |
Hi @jlblancoc Thanks for the suggestion. Right now all the tests pass without any fail. |
Hi @jlblancoc Can you please add my contribution to the initial description of the project? I need to fill it in the final evaluations. |
Done! 👍 Thanks for all the hard work during GSoC! |
GSOC 2017 [Algorithm improvements to KD-Tree module] Discussion on implemented features can be reached [here](MRPT/GSoC2017-discussions#1).
BTW: You can also create a gist (see for example this one) as a summary of your work, so you can be sure the content "belongs" to you and you can edit it at any time in the future... It will be OK for me to use either this page, or a custom gist (in that case, please post a link to it here so we can quickly review it). |
Hi @jlblancoc I have created a report as you suggested. Please review it. I am adding this link in the evaluation for now. |
Good! If you are still in time (I think it's late?) you could use that
report instead, since you can directly edit it at any time.
Anyway, feel free to come back and claim any change in the first comment's
"summary of work"!
…On Tue, Aug 29, 2017 at 2:27 PM, Pranjal Rai ***@***.***> wrote:
Hi @jlblancoc <https://github.com/jlblancoc>
I have created a report
<https://gist.github.com/pranjal-rai/307e178d023b9a4b5455ca9ca8383344> as
you suggested. Please review it. I am adding this link in the evaluation
for now.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#1 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AFPj2ksBMRChnL4X6YatGxuKldhMZm5mks5sdAPIgaJpZM4NRWSn>
.
--
___________________________________________________________
Jose Luis Blanco-Claraco
Universidad de Almería - Departamento de Ingeniería
https://w3.ual.es/~jlblanco/
https://github.com/jlblancoc
___________________________________________________________
|
Hi @pranjal-rai , It was a pleasure to have you in GSOC-2017! 👍 I'm now closing this issue ticket, since the changes were already merged upstream. New issues or ideas discussion could go on either here, or in the nanoflann repo, ok? I still have to do a more careful test of your recent changes, so expect feedback in the next week or so. Cheers! |
Hi @jlblancoc
👍
Thank you very much. Thank you being an awesome mentor throughout and giving me the opportunity to work on this project. I learned a lot from you while working on this project. I would love to contribute to MRPT in future too. |
Initial description
Nanoflann is a C++ library provided by MRPT for building KD-Trees. The library is a fork of the widely-used FLANN C++ library and is mostly optimized for lower dimensional point clouds. Most ICP algorithms for robot SLAM and localization require finding nearest neighbor in 2D/3D point clouds. Support for dynamic point clouds and nearest neighbour query in non flat spaces are two paramount features which are missing in the current nanoflann library.
See attached PDF.
5589797390254080_1491229396_MRPT_GSOC_Proposal.pdf
Final results:
The text was updated successfully, but these errors were encountered: