OpenCV Flann matching of feature point for multiple views

Question

I am trying to prepare overlapping aerial images for a bundle adjustment to create a 3D reconstruction of the terrain. So far I have a script that computes which images are overlapping and constructs a list of these image pairs. My next stage is to detect and compute SIFT features for each image and then match the feature points to any image that overlaps in the dataset. For this I am using the FLANN Matcher available in OpenCV.

My issue is, the bundle adjustment input needs to have a unique point id for each feature point. The FLANN matcher as far as I'm aware can only match feature points of two images at a time. So, if I have a the same point visible in 5 cameras how can I give this point an ID that is consistent across the 5 cameras? If I simply gave the point an ID when saving it during the matching now, the same point would have different ID's depending which sets of cameras were used to compute it.

The format of the bundle adjustment input is:

camera_id (int), point_id(int), point_x(float), point_y(float)

I am using this because the tutorial for the bundle adjustment code I am following uses the BAL dataset (i.e. ceres solver and scipy).

My initial idea is to compute and describe all the SIFT points across all the images and add into 1 list. From here I could remove any duplicate key point descriptors. Once I have a list of unique SIFT points in my dataset I could sequentially add an ID to each point. Then each time I match a point I could look up the points descriptor in this list and assign the point ID based on that list. Although I feel this would work, it seems very slow and doesn't make use of the K-TREE matching approach which I am using for the matching.

So finally, my question is... Is there a way to achieve feature matching for multiple views (>2) using the FLANN matcher in OpenCV python? Or... is there is general way the photogrammetry/SLAM community approach this problem?

My code so far:

matches_list = []
sift = cv2.xfeatures2d.SIFT_create()

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)

for i in overlap_list:

    img1 = cv2.imread(i[0], 0)
    img2 = cv2.imread(i[1], 0)

    img1 = cv2.resize(img1, (img1.shape[1]/4, img1.shape[0]/4), interpolation=cv2.INTER_CUBIC)
    img2 = cv2.resize(img2, (img2.shape[1]/4, img2.shape[0]/4), interpolation=cv2.INTER_CUBIC)

    kp1, des1 = sift.detectAndCompute(img1,None)
    kp2, des2 = sift.detectAndCompute(img2,None)

    matches = flann.knnMatch(des1,des2,k=2)
    for j,(m,n) in enumerate(matches):
        if m.distance < 0.7*n.distance:
            pt1 = kp1[m.queryIdx].pt
            pt2 = kp2[m.trainIdx].pt
            matches_list.append([i[0], i[1], pt1, pt2])

This returns a list with the following structure with length = number of feature matches:

matches_list[i] = [camera_1.jpg, camera_2.jpg, (cam1_x, cam1_y), (cam2_x, cam2_y)]

Answer 1

The precise problem this question asks is "How can I label a set of multiple matches uniquely when all I have is pairwise matches?"

This is a standard graph theory problem: getting from sets of edges to connected components.

Just for some intuition:

The idea is you have edges (pairs of feature matches). So for e.g. in the above graph, (2, 1) is an edge. And (1, 3), and (5, 6), and so on. So since 2 is matched with 1, and 1 with 3, really, 1, 2, and 3 are all probably the same feature. And so you can group the same features together by finding all the components which are connected together in this graph. Note that the graph need only be described by these pairs and nothing more.

You already have code to compute your matches. I'll provide some code to compute the connected components. No guarantees that this code is particularly fast, but it should be robust to whatever types of data you're using. Note however that each distinct node that you send in has to have distinct data as this uses sets.

def conncomp(edges):
    """Finds the connected components in a graph.

    Parameters
    ---------- 
    edges : sequence
        A sequence of pairs where the pair represents an undirected edge.

    Returns
    -------
    components : list
        A list with each component as a list of nodes. Only includes single
        nodes if the node is paired with itself in edges.
    """

    # group edge pairs together into a dict
    pair_dict = defaultdict(set)
    nodes = set([num for pair in edges for num in pair])
    for node in nodes:
        for pair in edges:
            if node in pair:
                pair_dict[node] = pair_dict[node].union(set(pair))

    # run BFS on the dict
    components = []
    nodes_to_explore = set(pair_dict.keys())
    while nodes_to_explore:  # while nodes_to_explore is not empty
        node = nodes_to_explore.pop()
        component = {node}
        neighbors = pair_dict[node]
        while neighbors:  # while neighbors is non-emtpy
            next_node = neighbors.pop()
            if next_node in nodes_to_explore:
                nodes_to_explore.remove(next_node)
            next_nodes = set([val for val in pair_dict[next_node] if val not in component])
            neighbors = neighbors.union(next_nodes)
            component.add(next_node)
        components.append(list(component))

    return components

As mentioned above, the input to this function is a list of pairs (tuples). I'd just send in a list of paired IDs, so for e.g.:

edges = [(img1_feat_i, img2_feat_j), ...]

where img1_feat_i and img2_feat_j the ids of features matched from knnMatch or BFMatch or whatever you like to use.

The function will return a list of components like

[[img1_feat_i, img2_feat_j, img3_feat_k, ...], ...]

Each component (i.e. each sublist) are all the same feature across images, so you can then map all those distinct ids to one unique id for the component.