Classes - Beard

You are here: start » ee490-11reports


|

Meta

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
ee490-11reports [2011/04/13 14:59]
ben
ee490-11reports [2011/04/21 12:50]
eabryan
Line 12: Line 12:
  
 The loop closure program works by first extracting features from an image. There are several different types of features that can be extracted, but the method that we used is called SURF, which extracts features that are scale and rotation invariant. These features are often abstract or very small so don't expect to understand what features the computer is seeing. For information on how SURF works we recommend you go to [http://​www.aishack.in/​2010/​05/​sift-scale-invariant-feature-transform/​]. It explains the SIFT algorithm, which is the algorithm which SURF is based on. Our code is written in OpenCV, which already has a SURF implementation. The loop closure program works by first extracting features from an image. There are several different types of features that can be extracted, but the method that we used is called SURF, which extracts features that are scale and rotation invariant. These features are often abstract or very small so don't expect to understand what features the computer is seeing. For information on how SURF works we recommend you go to [http://​www.aishack.in/​2010/​05/​sift-scale-invariant-feature-transform/​]. It explains the SIFT algorithm, which is the algorithm which SURF is based on. Our code is written in OpenCV, which already has a SURF implementation.
 +
 {{:​campus_challenge:​matching.png|}} {{:​campus_challenge:​matching.png|}}
 +
 The SURF function outputs two vectors. The first vector is called '​imagedescriptors'​. It contains a 64 bit description of each feature found in the image(making it 64 by N). The other output is a vector called imagekeypoints. This vector stores the location of each feature found on the image. To make it so the computer does not have to process every single feature (There will be potentially hundreds of thousands) The features in the images are grouped into clusters using k-means. The SURF function outputs two vectors. The first vector is called '​imagedescriptors'​. It contains a 64 bit description of each feature found in the image(making it 64 by N). The other output is a vector called imagekeypoints. This vector stores the location of each feature found on the image. To make it so the computer does not have to process every single feature (There will be potentially hundreds of thousands) The features in the images are grouped into clusters using k-means.
  
Line 113: Line 115:
 ==== Quad Trees-Sam Olson ==== ==== Quad Trees-Sam Olson ====
  
 +Quadtrees are already proven to work in robotic environments,​ so there was much more focus placed on finding out if quadtrees would work efficiently enough for our particular application,​ i.e. if the update time would be fast enough to keep up with the incoming laser data.  As such, all effort was immediately put into developing a C++ implementation.
 +Much of the code we have can be attributed to the vNet Project, which can be obtained free of charge from vnet@vnet-project.org. ​
 +
 +After more careful analysis, we discovered that quadtree structures would likely be too slow for our purposes. ​ Our requirements demand an access time under 0.1 seconds, but this implementation (and many others that were investigated) exceeded that constraint significantly as more points were added. ​ Greater numbers of points obtained from laser scan data increased quadtree traversal time too significantly to be of any use.
 +The alternative we then began investigating is a gridmap solution called Gmapping (found at http://​openslam.org/​) which uses Rao-Blackwellized particle filters to provide an individual map associated with every laser sample. ​ The advantage we see in Gmapping with Rao-Blackwellized filters over quadtrees is that speed is potentially much greater, and that it requires significantly fewer particles to build an accurate map.
 +Our conclusion is that quadtrees are much more suited to saving storage space rather than time.  Alternatives are still being researched.
  
 +{{:​campus_challenge:​quadtree_in_c.zip|}}
  
 +{{:​campus_challenge:​gmapping.zip|}}