scikit-image

1
import numpy as np
2
from scipy.spatial.distance import cdist
3

4

5
def match_descriptors(
6
    descriptors1,
7
    descriptors2,
8
    metric=None,
9
    p=2,
10
    max_distance=np.inf,
11
    cross_check=True,
12
    max_ratio=1.0,
13
):
14
    """Brute-force matching of descriptors.
15

16
    For each descriptor in the first set this matcher finds the closest
17
    descriptor in the second set (and vice-versa in the case of enabled
18
    cross-checking).
19

20
    Parameters
21
    ----------
22
    descriptors1 : (M, P) array
23
        Descriptors of size P about M keypoints in the first image.
24
    descriptors2 : (N, P) array
25
        Descriptors of size P about N keypoints in the second image.
26
    metric : {'euclidean', 'cityblock', 'minkowski', 'hamming', ...} , optional
27
        The metric to compute the distance between two descriptors. See
28
        `scipy.spatial.distance.cdist` for all possible types. The hamming
29
        distance should be used for binary descriptors. By default the L2-norm
30
        is used for all descriptors of dtype float or double and the Hamming
31
        distance is used for binary descriptors automatically.
32
    p : int, optional
33
        The p-norm to apply for ``metric='minkowski'``.
34
    max_distance : float, optional
35
        Maximum allowed distance between descriptors of two keypoints
36
        in separate images to be regarded as a match.
37
    cross_check : bool, optional
38
        If True, the matched keypoints are returned after cross checking i.e. a
39
        matched pair (keypoint1, keypoint2) is returned if keypoint2 is the
40
        best match for keypoint1 in second image and keypoint1 is the best
41
        match for keypoint2 in first image.
42
    max_ratio : float, optional
43
        Maximum ratio of distances between first and second closest descriptor
44
        in the second set of descriptors. This threshold is useful to filter
45
        ambiguous matches between the two descriptor sets. The choice of this
46
        value depends on the statistics of the chosen descriptor, e.g.,
47
        for SIFT descriptors a value of 0.8 is usually chosen, see
48
        D.G. Lowe, "Distinctive Image Features from Scale-Invariant Keypoints",
49
        International Journal of Computer Vision, 2004.
50

51
    Returns
52
    -------
53
    matches : (Q, 2) array
54
        Indices of corresponding matches in first and second set of
55
        descriptors, where ``matches[:, 0]`` denote the indices in the first
56
        and ``matches[:, 1]`` the indices in the second set of descriptors.
57

58
    """
59

60
    if descriptors1.shape[1] != descriptors2.shape[1]:
61
        raise ValueError("Descriptor length must equal.")
62

63
    if metric is None:
64
        if np.issubdtype(descriptors1.dtype, bool):
65
            metric = 'hamming'
66
        else:
67
            metric = 'euclidean'
68

69
    kwargs = {}
70
    # Scipy raises an error if p is passed as an extra argument when it isn't
71
    # necessary for the chosen metric.
72
    if metric == 'minkowski':
73
        kwargs['p'] = p
74
    distances = cdist(descriptors1, descriptors2, metric=metric, **kwargs)
75

76
    indices1 = np.arange(descriptors1.shape[0])
77
    indices2 = np.argmin(distances, axis=1)
78

79
    if cross_check:
80
        matches1 = np.argmin(distances, axis=0)
81
        mask = indices1 == matches1[indices2]
82
        indices1 = indices1[mask]
83
        indices2 = indices2[mask]
84

85
    if max_distance < np.inf:
86
        mask = distances[indices1, indices2] < max_distance
87
        indices1 = indices1[mask]
88
        indices2 = indices2[mask]
89

90
    if max_ratio < 1.0:
91
        best_distances = distances[indices1, indices2]
92
        distances[indices1, indices2] = np.inf
93
        second_best_indices2 = np.argmin(distances[indices1], axis=1)
94
        second_best_distances = distances[indices1, second_best_indices2]
95
        second_best_distances[second_best_distances == 0] = np.finfo(np.float64).eps
96
        ratio = best_distances / second_best_distances
97
        mask = ratio < max_ratio
98
        indices1 = indices1[mask]
99
        indices2 = indices2[mask]
100

101
    matches = np.column_stack((indices1, indices2))
102

103
    return matches
104