OpenCV feature matching for multiple images

Question

How can I optimise the SIFT feature matching for many pictures using FLANN?

I have a working example taken from the Python OpenCV docs. However this is comparing one image with another and it's slow. I need it to search for features matching in a series of images (a few thousands) and I need it to be faster.

My current idea:

1. Run through all the images and save the features. How?
2. Compare an image from a camera with this above base, and find the correct one. How?
3. Give me the result, matching image or something.

http://docs.opencv.org/trunk/doc/py_tutorials/py_feature2d/py_feature_homography/py_feature_homography.html

import sys # For debugging only
import numpy as np
import cv2
from matplotlib import pyplot as plt

MIN_MATCH_COUNT = 10

img1 = cv2.imread('image.jpg',0) # queryImage
img2 = cv2.imread('target.jpg',0) # trainImage

# Initiate SIFT detector
sift = cv2.SIFT()

# find the keypoints and descriptors with SIFT
kp1, des1 = sift.detectAndCompute(img1,None)
kp2, des2 = sift.detectAndCompute(img2,None)

FLANN_INDEX_KDTREE = 0
index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
search_params = dict(checks = 50)

flann = cv2.FlannBasedMatcher(index_params, search_params)

matches = flann.knnMatch(des1,des2,k=2)

# store all the good matches as per Lowe's ratio test.
good = []
for m,n in matches:
    if m.distance MIN_MATCH_COUNT:
    src_pts = np.float32([ kp1[m.queryIdx].pt for m in good ]).reshape(-1,1,2)
    dst_pts = np.float32([ kp2[m.trainIdx].pt for m in good ]).reshape(-1,1,2)

    M, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC,5.0)
    matchesMask = mask.ravel().tolist()

    h,w = img1.shape
    pts = np.float32([ [0,0],[0,h-1],[w-1,h-1],[w-1,0] ]).reshape(-1,1,2)
    dst = cv2.perspectiveTransform(pts,M)

    img2 = cv2.polylines(img2,[np.int32(dst)],True,255,3, cv2.LINE_AA)

else:
    print "Not enough matches are found - %d/%d" % (len(good),MIN_MATCH_COUNT)
    matchesMask = None

draw_params = dict(matchColor = (0,255,0), # draw matches in green color
                   singlePointColor = None,
                   matchesMask = matchesMask, # draw only inliers
                   flags = 2)

img3 = cv2.drawMatches(img1,kp1,img2,kp2,good,None,**draw_params)

plt.imshow(img3, 'gray'),plt.show()

---

UPDATE

After trying out many things I might have come closer to the solution now. I hope it's possible to build the index and then search in it like this:

flann_params = dict(algorithm=1, trees=4)
flann = cv2.flann_Index(npArray, flann_params)
idx, dist = flann.knnSearch(queryDes, 1, params={})

However I still haven't managed to build an accepted npArray to the flann_Index parameter.

loop through all images as image:
  npArray.append(sift.detectAndCompute(image, None))
npArray = np.array(npArray)

Answer 1

Along with the reply of @stanleyxu2005 I'd like to add some tips as to how to do the whole matching itself since I'm currently working of such a thing.

1. I strongly recommend to create some custom class that wraps around the cv::Mat but also stores various other essential pieces of data. In my case I have an ImageContainer store the original image (that I will use for the final stitching), the processed one (grayscaled, undistorted etc.), its keypoints and the descriptors for those. By doing so you can access all the matching-relevant information in a pretty well organized well. You can either implement the keypoint extraction and descriptor generation in it or do that outside the class and just store the results in that container.
2. Store all image containers in some kind of a structure (vector is usually a good choice) for easy access.
3. I also created a class called ImageMultiMatchContainer, which stores a pointer to a given query image (all images are query images), a vector with pointers to all train images (for a single query image of the image set all others are train images) that were matched to it and also a vector of the match vectors for each of those matches. Here I stumbled across a storage issue namely - first you have to skip matching of an image with itself because it is pointless and second you have the problem of comparing two images two times and thus generating a considerable overhead if you have a lot of images. The second problem is due to the fact that we iterate through all images (query images) and compare them to the rest in the set (train images). At some point we have image X (query) matched with image Y (train), but later we also have image Y (now query) matched with image X (now train). As you can see this is also pointless since it's basically matching the same pair of images twice. This can be solved (currently working on this) by creating a class (MatchContainer) that stores a pointer to each of the two images in a matched pair and also the match vector. You store this in a central location (in my case this is my matcher class) and for each image as query image you check the list of matched images of the train image. If it's empty then you create a new MatchContainer and add it to the rest of the MatchContainers. If it's not then you look in it and see if the current query image is not present there (comparing pointers is a fast operation). If it is then you just pass the pointer to that MatchContainer's vector item that stores the matches for those two images. If that is not the case, you do as if it's empty and create a new MatchContainer etc. MatchingContainers should be stored in a data structure with a small access times since you will be looking at them a lot and iterating from start to end costs too much time. I'm considering using a map but maybe a tree of some sort can offer some advantages as well.
4. The homography estimation is a very tricky part. Here I recommend you look at bundle block adjustment. I saw that the stitcher class in OpenCV has a BundleBase-class but haven't tested it yet to see what's in it.

A general recommendation is to look at the stitching process in OpenCV and read the source code. The stitching pipeline is a straight forward set of processes and you just have to see how exactly you can implement the single steps.

Answer 2

I never solved this in Python, however I switched environment to C++ where you get more OpenCV examples and don't have to use a wrapper with less documentation.

An example on the issue I had with matching in multiple files can be found here: https://github.com/Itseez/opencv/blob/2.4/samples/cpp/matching_to_many_images.cpp

Answer 3

Here are several pieces of my advice:

1. You should reduce the amount of point data by using proper techniques.
2. Calculate the reference image repeatedly is a waste. You should persistent all calculated reference.
3. Do not put the calculate on a mobile device. You'd better upload the calculated reference of a captured image to a powerful server and do the searching there.

This is a very interesting topic. My ears are opening too.