Ask Your Question
6

performance of findHomography

asked 2012-07-31 10:48:33 -0600

christoph gravatar image

updated 2012-08-01 06:30:52 -0600

sammy gravatar image

I am trying to detect a planar object from a video stream. Keypoint detection and feature extraction work both fairly well, as well as matching. findHomography however takes very long (up to 1,6 sec on my mobile). I tried several combinations of detector/extractor/matcher to change the number and quality of keypoints. My current setup is ORB and BFMatcher<Hamming>. My question is: How can I speed up the homography calculation? I'm using ransac, but changing the threshold seems to have little to no effect (neither in quality nor performance). Should I use some other methods like getPerspectiveTransform, or estimateAffine3D or solvePnp?

On a side note: I also had a hard time to get a useful matrix out of findHomography in the first place, although I sticked pretty close to opencv's samples.

edit retag flag offensive close merge delete

Comments

How many points do you have in each set of keypoints?

sammy gravatar imagesammy ( 2012-07-31 11:10:12 -0600 )edit

The object image has about 260 keypoints with a resolution of 327x245 px and the scene images (camera frames) are usually between 460 to 490 with 352x288 res. They give me usually 260 matches. Another thing I might add is the fact, that the tracked object is expected to appear about 2 to 3 times smaller in the scene image than in its reference image. So in the scene image there are obviously less keypoints on the object itself than on some background clutter. So I guess I have to get rid of some bad matches first, before calculating the homography?

christoph gravatar imagechristoph ( 2012-07-31 12:37:07 -0600 )edit

2 answers

Sort by ยป oldest newest most voted
9

answered 2012-08-01 01:42:57 -0600

sammy gravatar image

updated 2012-08-01 02:41:46 -0600

A few suggestions to improve performance are:

  • select a smaller number of keypoints - let's say 80% of the best ones. Less points to fit, higher the speed. Note also that RANSAC processing time is highly dependent on the quality of the points. If 95% of them are good, it can be 100 times faster than if 60% of them are good. Rejecting from start the ones that seem unfit may help.

  • fork OpenCV and rewrite the findHomography internal stuff to work with floats, instead of doubles (modules/calib32/src/fundam.cpp). double is a killer on mobile platforms. Also, compile OpenCV with -ffast-math to speedup floating point operations. Note that although these changes will likely decrease accuracy, the effects are minimal or close to 0. I expect conversion from double to float to be more effective than the compilation flag, although more complicated.

  • profile the function and see where the most time is spent. If it is the solvePoly function, or a similar polynomial solver, you can speed it up enormously by implementing your own solver, based on Vandermonde matrix properties. Check out this ol' good book by Golub for a reference algorithm

  • Finally, try to use NEON in your implementation. Check this post for a bit more info (paragraph E): http://answers.opencv.org/question/755/object-detection-slow/#760

edit flag offensive delete link more

Comments

2

Thank you for these great suggestions. By now I only implemented the first one, and I can confirm that the quality of matches are indeed a key factor regarding speed. I started with a simple distance filter to get the n best matches and might have found a bug.

If I use the build in cross check method in brute force matcher (initializing it like this: BFMatcher(NORM_HAMMING, true) ) all distances have a value of 2.14748e+09, which looks like some kind of overflow to me. If I use BFMatcher(NORM_HAMMING) I get reasonable values. Features and descriptors are both ORB. I'm using the stable 2.4.2 iOS build on an iPhone 4S.

I am positive that these distance values were responsible for the slow down in findHomography in the first place.

christoph gravatar imagechristoph ( 2012-08-01 05:13:38 -0600 )edit
2

answered 2013-05-05 04:08:22 -0600

SR gravatar image

updated 2013-05-06 16:44:17 -0600

Advertisement: I have created a fast RANSAC variant called "1P-WGC-RANSAC" that is suitable for real-time applications. We used it for geometric verification of image search results but it is also applicable to different scenarios. It is extremely fast (a few ms per image, e.g. we could process more than 400 images/s) and has almost identical performance (in terms of accuracy) as e.g. OpenCV's RANSAC implementation. You find more details in the publication (Section 4). Some more insights are given in the slides.

edit flag offensive delete link more

Comments

1

So it is not open source?

Rui Marques gravatar imageRui Marques ( 2014-03-02 16:09:37 -0600 )edit

Still no Open source implementation ?

ZettaCircl gravatar imageZettaCircl ( 2019-04-23 08:14:26 -0600 )edit

Question Tools

1 follower

Stats

Asked: 2012-07-31 10:48:33 -0600

Seen: 6,354 times

Last updated: May 06 '13