[OpenDroneMap-dev] Ideas for speeding up the Point Matching

Cole colek42 at gmail.com
Mon Mar 16 21:42:14 PDT 2015 

the LSD slam page has some ply files you can open in mesh lab -- I was
doing my best to get a mesh from the point cloud, but I hjave nevr used
meshlab before and all I was getting was globs.  Also their source is
GNUv3, so we can use it.  They are using ROS, so we would need change some
stuff around to get it to work independently -- ROS has a high learning
curve and is definitely not suitable for what you guys want to do.



On Mon, Mar 16, 2015 at 10:40 PM, Stephen Mather <stephen at smathermather.com>
wrote:

> Hi Cole,
>
> Awesome video. That's really illustrative. I look forward to digging into
> the code.
>
> In my mind, lsdslam and similar dense optical flow techniques are
> brilliant, and would solve a few ODM problems, not the least of which is
> performing matching on continuously variable surfaces with otherwise few
> matchable features (i.e.
> https://twitter.com/reprojected/status/576142074522648576/photo/1 ). The
> one thing about them is their tendency (as I understand it) to drift, so I
> think that there is still a place for feature matching to avoid having to
> calculate large loop closures, as this may not always be practical for
> input datasets.
>
> Unless I misunderstand the process, the matching is not all pixels to all
> images but first feature identification, then match. Only once this is done
> does PMVS perform full pixel matching, which is the shortest portion of the
> toolchain aside from mesh and texture.
>
> Regardless of approach, match / dense optical flow, or hybrid, it will
> still be useful to use image ephemeris to aid with pre-matching, especially
> in cases where yaw/pitch/roll in addition to location are known.
>
> Best,
> Steve
>
>
>
> On Mon, Mar 16, 2015 at 7:33 PM, Cole <colek42 at gmail.com> wrote:
>
>> How is the point matching being done with bundler?  It seems like it is
>> just iterating over every pixel of every image.  There are much better
>> methods, especially if we have access to IMU, Gyro, and GPS data (you can
>> buy a 9 axis sensor for about $50 these days).  Even without this sensor
>> data, state estimation in video can be calculated from one frame to the
>> next using dense optical flow.  I wrote something using a similar concept
>> for image stabilization.  Demo here:
>> https://www.youtube.com/watch?v=LIcYE9eBNjE This was done in real time,
>> using python and OpenCV.  Code is here (free for use)
>> https://github.com/colek42/TrackIt/tree/master/catkin/src/stabilize/src
>> <https://github.com/colek42/TrackIt>   ( this is just test code,
>> prototyping for some C++, I apologize in advance for it's ugliness)
>>
>> see http://vision.in.tum.de/research/lsdslam .  Their code is not
>> license compatible, but is a good example of what can be done as far as
>> efficiency, and how far the current tool chain is away from state of the
>> art, as far as point matching.
>>
>> I am working on the lens correction code tonight.  I have a pull request
>> for a script that will have you input a checkerboard image, and a dir with
>> all the images or video you would like processed.  It will depend on python
>> 2.74 and OpenCV.
>>
>> I wish I could give the project some more time, but I am currently
>> working full time, taking way too many credits, and a family I like to
>> spend some time with.  My schedule should clear up in a couple months and I
>> should be able to make some progress on some of this stuff
>>
>> v/r
>> NJK
>>
>>
>>
>> On Mon, Mar 16, 2015 at 3:01 PM, <
>> opendronemap-dev-request at lists.osgeo.org> wrote:
>>
>>> Send OpenDroneMap-dev mailing list submissions to
>>>         opendronemap-dev at lists.osgeo.org
>>>
>>> To subscribe or unsubscribe via the World Wide Web, visit
>>>         http://lists.osgeo.org/cgi-bin/mailman/listinfo/opendronemap-dev
>>> or, via email, send a message with subject or body 'help' to
>>>         opendronemap-dev-request at lists.osgeo.org
>>>
>>> You can reach the person managing the list at
>>>         opendronemap-dev-owner at lists.osgeo.org
>>>
>>> When replying, please edit your Subject line so it is more specific
>>> than "Re: Contents of OpenDroneMap-dev digest..."
>>>
>>>
>>> Today's Topics:
>>>
>>>    1. Ideas for speeding up the Point Matching (Alex Mandel)
>>>    2. Re: Ideas for speeding up the Point Matching (Stephen Mather)
>>>    3. Re: Ideas for speeding up the Point Matching (Stephen Mather)
>>>
>>>
>>> ----------------------------------------------------------------------
>>>
>>> Message: 1
>>> Date: Sun, 15 Mar 2015 20:00:56 -0700
>>> From: Alex Mandel <tech_dev at wildintellect.com>
>>> To: opendronemap-dev at lists.osgeo.org
>>> Subject: [OpenDroneMap-dev] Ideas for speeding up the Point Matching
>>> Message-ID: <55064768.4010109 at wildintellect.com>
>>> Content-Type: text/plain; charset=utf-8
>>>
>>> So 2 days in to running ~1000 images I started pondering how to speed up
>>> the point matching step.
>>>
>>> Here's the basic idea, split the list of images into related chunks,
>>> process those chunks and then process a slice of overlap from 2 adjacent
>>> chunks.
>>>
>>> This nice part is that this idea will work for either time/numeric
>>> ordered or GeoExif grouping.
>>>
>>> Here's the basic idea, take a number of photos that is reasonable to
>>> process like 100. Now take your set of photos, 1000 and divide it by
>>> 100. So you first do 10 sets of a 100. Then you take 1/2 or 1/3 or 1/4
>>> of two adjacent sets. So the last 50 of set 1 and first 50 of set 2 (for
>>> 1/2), that gives you 9 additional sets of 100 but you only have to do
>>> 1/2 of the matches, only the ones that have a photo from a different
>>> original set.
>>>
>>> Here's the math:
>>> n!/(r!(n-r)!)
>>>
>>> http://www.calculatorsoup.com/calculators/discretemathematics/combinations.php
>>>
>>> n is number of photos in a set
>>> r is 2, number of photos in a pair
>>>
>>> 100 Photos is 4950 pairs. If you do just 1000 you get 499,500 pairs to
>>> check. If you do what I said above, groups of 100, with 50% overlap you
>>> get 71,775 pairs to check ((10*4950)+9(4950/2))
>>>
>>> Now for the fancy part, the dumb application of this to GeoExif is to
>>> take the bbox of all the photos, take the longer side of the box and
>>> divide it by 10, so you make 10 new rectangles and run each of those as
>>> a set, then run the 9 overlap regions. Long term we can get smarter with
>>> how we pick the regions to ensure ~100 images per region.
>>>
>>> So steps to accomplish this,
>>> 1. write a short script to make lists of photos in each set to run.
>>> 2. figure out how to send the lists to the point matching tool
>>> 2a. figure out how to make the point matching tool skip matches done in
>>> a previous set.
>>> 3. Continue from there as usual.
>>>
>>> Feedback anyone?
>>>
>>> Thanks,
>>> Alex
>>>
>>>
>>> ------------------------------
>>>
>>> Message: 2
>>> Date: Sun, 15 Mar 2015 23:15:25 -0400
>>> From: Stephen Mather <stephen at smathermather.com>
>>> To: Alex Mandel <tech at wildintellect.com>
>>> Cc: opendronemap-dev at lists.osgeo.org
>>> Subject: Re: [OpenDroneMap-dev] Ideas for speeding up the Point
>>>         Matching
>>> Message-ID:
>>>         <CAPkJWLVZdGn=
>>> pn4oXQw2D9YdZqGHidUa1RouKBkORfx4npiUiw at mail.gmail.com>
>>> Content-Type: text/plain; charset="utf-8"
>>>
>>> Hi Alex,
>>>
>>> One thought I had was to use geolocations in the exif, pipe those values
>>> through something really dumb like geohash, then sort by geohash, thus
>>> clustering similar values, and (I think) you can limit the number of
>>> images
>>> that match tries to match to some reasonable number like you propose, so
>>> that it would still chunk through the dataset as a single model, but
>>> limit
>>> the matching to some moving window based on image order as determined by
>>> the hash.
>>>
>>> Going to reread your write up in the morning when I am smarter... :) .
>>> It's
>>> undoubtedly better than a geohash hack... .
>>>
>>> Best,
>>> Steve
>>> -------------- next part --------------
>>> An HTML attachment was scrubbed...
>>> URL: <
>>> http://lists.osgeo.org/pipermail/opendronemap-dev/attachments/20150315/36293eae/attachment-0001.html
>>> >
>>>
>>> ------------------------------
>>>
>>> Message: 3
>>> Date: Mon, 16 Mar 2015 13:13:51 -0400
>>> From: Stephen Mather <stephen at smathermather.com>
>>> To: Alex Mandel <tech at wildintellect.com>
>>> Cc: opendronemap-dev at lists.osgeo.org
>>> Subject: Re: [OpenDroneMap-dev] Ideas for speeding up the Point
>>>         Matching
>>> Message-ID:
>>>         <CAPkJWLURZeG+s-W1VrQzb3QsnA9_=jm_t1=
>>> oHWok6HpsNuewpQ at mail.gmail.com>
>>> Content-Type: text/plain; charset="utf-8"
>>>
>>> Ok -- this is deep. So this approach reduces the factorial load
>>> independently of geography, with the exception that the subset locations
>>> are chosen by geography?
>>>
>>> Thanks,
>>> Best,
>>> Steve
>>>
>>>
>>>
>>> On Sun, Mar 15, 2015 at 11:00 PM, Alex Mandel <
>>> tech_dev at wildintellect.com>
>>> wrote:
>>>
>>> > So 2 days in to running ~1000 images I started pondering how to speed
>>> up
>>> > the point matching step.
>>> >
>>> > Here's the basic idea, split the list of images into related chunks,
>>> > process those chunks and then process a slice of overlap from 2
>>> adjacent
>>> > chunks.
>>> >
>>> > This nice part is that this idea will work for either time/numeric
>>> > ordered or GeoExif grouping.
>>> >
>>> > Here's the basic idea, take a number of photos that is reasonable to
>>> > process like 100. Now take your set of photos, 1000 and divide it by
>>> > 100. So you first do 10 sets of a 100. Then you take 1/2 or 1/3 or 1/4
>>> > of two adjacent sets. So the last 50 of set 1 and first 50 of set 2
>>> (for
>>> > 1/2), that gives you 9 additional sets of 100 but you only have to do
>>> > 1/2 of the matches, only the ones that have a photo from a different
>>> > original set.
>>> >
>>> > Here's the math:
>>> > n!/(r!(n-r)!)
>>> >
>>> >
>>> http://www.calculatorsoup.com/calculators/discretemathematics/combinations.php
>>> >
>>> > n is number of photos in a set
>>> > r is 2, number of photos in a pair
>>> >
>>> > 100 Photos is 4950 pairs. If you do just 1000 you get 499,500 pairs to
>>> > check. If you do what I said above, groups of 100, with 50% overlap you
>>> > get 71,775 pairs to check ((10*4950)+9(4950/2))
>>> >
>>> > Now for the fancy part, the dumb application of this to GeoExif is to
>>> > take the bbox of all the photos, take the longer side of the box and
>>> > divide it by 10, so you make 10 new rectangles and run each of those as
>>> > a set, then run the 9 overlap regions. Long term we can get smarter
>>> with
>>> > how we pick the regions to ensure ~100 images per region.
>>> >
>>> > So steps to accomplish this,
>>> > 1. write a short script to make lists of photos in each set to run.
>>> > 2. figure out how to send the lists to the point matching tool
>>> > 2a. figure out how to make the point matching tool skip matches done in
>>> > a previous set.
>>> > 3. Continue from there as usual.
>>> >
>>> > Feedback anyone?
>>> >
>>> > Thanks,
>>> > Alex
>>> > _______________________________________________
>>> > OpenDroneMap-dev mailing list
>>> > OpenDroneMap-dev at lists.osgeo.org
>>> > http://lists.osgeo.org/cgi-bin/mailman/listinfo/opendronemap-dev
>>> >
>>> -------------- next part --------------
>>> An HTML attachment was scrubbed...
>>> URL: <
>>> http://lists.osgeo.org/pipermail/opendronemap-dev/attachments/20150316/82090550/attachment-0001.html
>>> >
>>>
>>> ------------------------------
>>>
>>> _______________________________________________
>>> OpenDroneMap-dev mailing list
>>> OpenDroneMap-dev at lists.osgeo.org
>>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/opendronemap-dev
>>>
>>>
>>> End of OpenDroneMap-dev Digest, Vol 2, Issue 3
>>> **********************************************
>>>
>>
>>
>> _______________________________________________
>> OpenDroneMap-dev mailing list
>> OpenDroneMap-dev at lists.osgeo.org
>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/opendronemap-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/opendronemap-dev/attachments/20150317/010e0e39/attachment-0001.html>

More information about the OpenDroneMap-dev mailing list