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

Stephen Mather stephen at smathermather.com
Wed Mar 18 20:24:05 PDT 2015 

Yes, ROS would change platform expectations / requirements quite a bit, if
I understand things correctly. I'll have to check out their point clouds,
although I'll openly admit that good surfaces from point clouds is a bit
magical to me... .

On Tue, Mar 17, 2015 at 12:42 AM, Cole <colek42 at gmail.com> wrote:

> 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/20150318/9e29055a/attachment-0001.html>

More information about the OpenDroneMap-dev mailing list