7
$\begingroup$

I'm a new guy in image processing and computer vision, so this question might be stupid to you.

I just learned some feature detection and description algorithms, such as Harris, Hessian, SIFT, SURF, they process images to find out those keypoints and then compute a descriptor for each, the descriptor will be used for feature matching.

I've tried SIFT and SURF, found that they are not so robust as I thought, since for 2 images (one is rotated and affined a little), they don't match the features well, among almost 100 feature points, only 10 matches are good.

So I wonder

  1. What can we use these feature detection algorithms for in practice? Is there any more robust algorithms for feature detection and matching? Or SIFT and SURF is already good, I just need to refine it for further use?

  2. Another problem is that I thought these algorithms are not quite for real-time application (without considering multi-core implementation), but there are some commercial products (such as Kinect) which work and response in real-time! I assume these products also detect and match feature from what they see, do they use the algorithms such as SIFT? How could they detect features so well?

  3. With my limited knowledge, I know feature matching can be used to find out same objects in two images, or estimate homographies, but any other purpose for feature matching?

$\endgroup$
  • $\begingroup$ Hey! I think you probably have a problem with your SIFT/SURF implementation. They should both work much better than 10/100. Would you mind uploading your images, and/or matching results? $\endgroup$ – penelope Oct 8 '13 at 7:49
  • $\begingroup$ @penelope, actually I'm using SIFT/SURF by OpenCV. Also I think they should work better than 10/100, maybe I should handle the feature matching part more carefully,;-). $\endgroup$ – avocado Oct 8 '13 at 8:10
  • $\begingroup$ @penelope, btw, do they work well with affined images? $\endgroup$ – avocado Oct 8 '13 at 8:12
  • $\begingroup$ Oh yes. Take a look at this paper. It's a comparison of several detectors, and shows their robustness against affine changes, blur, lighting, and many other things. Actually no SIFT there, but SIFT should not be bad in comparison to any of these. I'm gonna type you up a more detailed response later today, don't have time right this second $\endgroup$ – penelope Oct 8 '13 at 8:19
8
$\begingroup$

Image keypoints are a key feature in many Image and Video processing softwares, both industrial and academic. The principle behind is always the same:

  • detect some meaningful points in some images;
  • [optional] compute a stable description of the image part surrounding each keypoint;
  • match keypoints from an image (the template) to another (the query).

Now, some more detail.

Why detecting points? Basically, because a point is an intersection of two lines. As such, it is detected much more accurately (and in a more stable way) as lines or other features (area, etc.). This has been common knowledge in Computer Vision later proved in a paper by Mikolajczyk. This is rooted deeply in any point detector: for example, Harris point detector relies on the Hessian matrix to check that there are two crossing lines.

Why is the description part optional? Basic point detectors (Harris, SUSAN, Moravec, FAST) do not come with a descriptor. The process of matching them is purely location-based. Thus, they are mostly used for video processing. The intuition behind is that you can have many many points, then a robust estimation process (e.g., RANSAC). Recent keypoints however (SIFT and the ones that came after) embed an image patch descriptor, because they are meant to be used in more complex situations (object detection, large baseline matching...).

What's he difference between Harris/Hessian and SIFT/SURF? Besides the descriptor part, SIFT/SURF also include a localization in scale. Thus, when you detectd a SIFT/SURF point, you expect to find it again even if your image has been zoomed in/out, etc.

What's the difference between SIF and SURF? Well, SURF is actually mostly an approximated version of SIFT that is better suited for fast computations (by using integral images). Consequently, SURF is not as stable (as "good") as SIFT under affine transforms, but it comes at something like 1/10th of the computational cost.

Are they suited for realtime software? Yes, fore sure for Harris. SURF was designed to be fast, so a good implementation should be fast too. SIFT was not designed for speed, but you can find GPU implementations. But if you really want to be fast even on lower-end devices, then you need to check recent points such as FAST (detector), BRIEF, ORB, BRISK, FREAK (binary descriptors).

What can you do with them? Well, many things. By tracking points in videos then you can stablize them, augment them with objects, track objects. By matching points between cameras, you can automate the calibration process of 3D reconstruction pipelines. By matching points on parts of object, you can detect objects. And probably much more...

$\endgroup$
  • $\begingroup$ thank you so much for this detailed answer. As you mentioned, intuition behind is that you can have many many points, then a robust estimation process (e.g., RANSAC), I think to conduct a robust estimation (such as homography), feature descriptor is indispensable, because, from my limited knowledge, estimation involves feature correspondences which needs feature descriptor for feature matching, right? Or is there any other estimation without feature matching? $\endgroup$ – avocado Oct 8 '13 at 9:30
  • $\begingroup$ In video processing, you have e.g. 25fps which means 40 milliseconds between two frames. Keypoints will not move much, and the matching process will be some spatial nearest neighbour process. If points did appear/disappear, then you hope RANSAC will deal with that (which is true as long as you still have 50% good matchings). Remark also that adding a descriptor still ends up in nearest neighbour matching but in feature space, not in spatial space anymore. $\endgroup$ – sansuiso Oct 8 '13 at 9:35
  • $\begingroup$ Nice answer. If an object is rigid and essentially limited to 3 degrees of freedom in 2D (x, y, rotation) + scaling, then there are some fine "robust pattern matching" algorithms in commercial software packages that work very well for certain applications. Examples include software from Cognex, Hexavision, DALSA, and Halcon from MvTec. These algorithms may not be as generalized as the original poster wanted, but for rigid objects they can be quite robust. $\endgroup$ – Rethunk Oct 28 '13 at 4:24
  • $\begingroup$ Maybe OCR also? $\endgroup$ – FindOutIslamNow Apr 17 '18 at 12:00
2
$\begingroup$

Well, that's a great answer by @sansuiso, so I'll just concentrate on various possible uses of detected keypoints, and describe some examples for you. There are certainly more uses, the ones listed are just based on what I came in touch with until now.

Content based image retrieval (CBIR) You treat the features (the feature vectors you get after applying feature descriptors to the detected points) as visual words. On those visual words, you apply bag-of-words techniques, that were first introduced for text retrieval (think Google). I gave a quite detailed answer on that here (also look at references therein). This will allow you to:

  • find similar images in the database
  • detect the presence of a certain object throughout database pictures
  • "cluster" and organize the database automatically

("Coarse") Homography estimation on image pairs Detect features, do matching, chose the most robust matches, and then estimate the homography based on those matches. There are some techniques to improve performance: in addition to just matching descriptors, spatial information can be used as well (e.g. a match can be rejected if its neighbors from image A are not matched in the same neighborhood in the image B - example technique near the end of this article Can be used for example in:

  • image stitching - e.g. to connect multiple "panorama pictures" in to one picture
  • coarse pose estimation - we used this in a project where we had to navigate a robotic car automatically through a recorded course (based on human navigation). The only information we had was "key" images taken at certain distances along the path. First we used CBIR to find the closest key image, and then initial localization and positioning was done based on image matching between the current view and the database image.
  • video stabilization - I've seen a very nice example of footage of a road-crossing taken with a camera hanging from a helicopter. The idea was to "neutralize" the swinging of the camera -- and the final result was a very nice, steady-looking video.

Feature tracking I can't tell you as much about how this is done since I didn't do much tracking myself, but I can give you some examples of when this might be useful. The idea is to select some points of interest and then follow their position in the video from frame to frame. Examples (I've seen):

  • traffic sign following: Could be an aid in driving, e.g. if there's a view of the road ahead, and the driver can get a processed image, it could be useful to detect, mark, and track the position of a traffic sign showing up in front of the driver (maybe alerting the driver to the location/distance of the sign, and meaning)
  • fine localization and positioning: in the same automated navigation of the robotic car I mentioned above, it was much more precise to do fine localization based on tracked features. In order to update the current position and give the command on further movement, certain features were tracked in the frame (so, no matching needed), and homography was estimated based on those features.
$\endgroup$
  • $\begingroup$ Thank you for these applications, and also the paper and post you linked in. $\endgroup$ – avocado Oct 8 '13 at 12:02
1
$\begingroup$

There is a website which will give you a lot of information about your queries: http://www.robots.ox.ac.uk/~vgg/research/affine/

It contains information about feature detectors and descriptor, their current performance and which one is best in which scenario.

This field has still a lot to go on.

For example when you want to go for stereo reconstruction these algorithms usually fail in case of multi-view point images. You can try something of that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.