docs/correspondences_matching.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0d9ba81e-ba31-411e-82b1-2b641c7fcd8c",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "## 1. **BFMatcher (Brute-Force Matcher)**\n",
    "Compares descriptors between keypoints in a brute-force manner, for distance calculation, such as `cv::NORM_L2` or `cv::NORM_HAMMING`. It is suitable for small datasets.\n",
    "\n",
    "**Distance Types**\n",
    "The \"distance\" is purely a measure of similarity between feature descriptors, (Smaller distance = Higher similarity).\n",
    "It does not directly correspond to spatial distances in pixels.\n",
    "\n",
    "1. **`cv::NORM_L2`, `cv.NORM_L2` (Euclidean Distance):**   Euclidean distance, used mainly for floating-point descriptors like **SIFT/SURF**. By default, it is `cv.NORM_L2`. It is good for SIFT, SURF etc (`cv.NORM_L1 is` also there).  Distance = √(Σ(descriptor1[i] - descriptor2[i])²)\n",
    "\n",
    "```\n",
    "bf = cv2.BFMatcher(cv2.cv.NORM_L2, crossCheck=True)\n",
    "```\n",
    "\n",
    "2. **`cv::NORM_HAMMING,cv.NORM_HAMMING` (Hamming Distance):** Used for binary string-based descriptors like **ORB/BRIEF/BRISK**. It counts the number of differing bits between two binary strings. If ORB is using `WTA_K == 3` or `4`, which takes 3 or 4 points to produce BRIEF descriptor\n",
    "\n",
    "\n",
    "```python\n",
    "bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)\n",
    "```\n",
    "\n",
    "`Cross Check`: An option in the BFMatcher that ensures mutual matching. For two keypoints to be considered a match, the keypoint in the first image must match the keypoint in the second image, and vice-versa.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ec2511b-6924-46e0-ab3a-f2bebc6bedf7",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "#### 1.2 Simple `BFMatcher`\n",
    "```cpp\n",
    "cv::Ptr<cv::Feature2D> detector = cv::ORB::create();\n",
    "\n",
    "cv::BFMatcher bfMatcher(cv::NORM_HAMMING);\n",
    "std::vector<cv::DMatch> bfMatches;\n",
    "bfMatcher.match(descriptors1, descriptors2, bfMatches);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55f1581e-e4ad-4ef5-a5af-dddb00d1e693",
   "metadata": {},
   "source": [
    "\n",
    "<img src=\"images/BFMatcher.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe39e5d2-2214-4637-82bb-87c0d73eb720",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "#### 1.3 `knnMatcher`\n",
    "\n",
    "```cpp\n",
    "// Use BFMatcher with NORM_HAMMING (suitable for ORB descriptors)\n",
    "cv::BFMatcher matcher(cv::NORM_HAMMING, /*crossCheck=*/false);\n",
    "\n",
    "// Perform KNN matching (k=2)\n",
    "std::vector<std::vector<cv::DMatch>> knnMatches;\n",
    "matcher.knnMatch(descriptors1, descriptors2, knnMatches, k);\n",
    "\n",
    "// Apply Lowe's ratio test to filter matches\n",
    "const float ratioThresh = 0.75f; // Lowe's ratio test threshold\n",
    "std::vector<cv::DMatch> goodMatches;\n",
    "for (const auto& knnMatch : knnMatches) {\n",
    "    if (knnMatch.size() >= 2 && knnMatch[0].distance < ratioThresh * knnMatch[1].distance) {\n",
    "        goodMatches.push_back(knnMatch[0]);\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "742a14c4-b51e-42b4-b1b8-f4e50fc8a29f",
   "metadata": {},
   "source": [
    "\n",
    "<img src=\"images/KNN_Matches.png\" />\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8596337e-1975-41e7-9c31-a3edfd246c5a",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "#### 1.3 `radiusMatch`\n",
    "Use `radiusMatch` when you want to consider all matches within a **spatial or distance threshold**, especially for applications where proximity is more critical than ranking.\n",
    "\n",
    "\n",
    "If you’re using ORB and set `maxDistance = 50` in `radiusMatch`:\n",
    "- The matcher will consider all descriptors from the second image that are within 50 bits difference (Hamming distance) of a descriptor from the first image.\n",
    "\n",
    "If you’re using SIFT and set `maxDistance = 1.0`:\n",
    "- The matcher will consider all descriptors within a Euclidean distance of 1.0.\n",
    "\n",
    "\n",
    "```cpp\n",
    "cv::BFMatcher matcher(cv::NORM_HAMMING);\n",
    "\n",
    "// Perform radius matching\n",
    "const float maxDistance = 50.0f; // Radius threshold\n",
    "std::vector<std::vector<cv::DMatch>> radiusMatches;\n",
    "matcher.radiusMatch(descriptors1, descriptors2, radiusMatches, maxDistance);\n",
    "\n",
    "// Filter and collect matches for visualization\n",
    "std::vector<cv::DMatch> goodMatches;\n",
    "for (const auto& matches : radiusMatches) {\n",
    "    for (const auto& match : matches) {\n",
    "        if (match.distance < maxDistance) {\n",
    "            goodMatches.push_back(match);\n",
    "        }\n",
    "    }\n",
    "}\n",
    "cv::Mat imgMatches;\n",
    "cv::drawMatches(img1, keypoints1, img2, keypoints2, goodMatches, imgMatches);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ce73104-ab49-4782-b468-c84cc22f1b2a",
   "metadata": {},
   "source": [
    "Here, a `std::vector<std::vector<cv::DMatch>>` is used because this method can potentially return multiple matches for each query descriptor. Unlike other matching methods that return a single best match,  `radiusMatch` finds all matches within a specified distance (`maxDistance`) for each query descriptor  in `descriptors2` (train set) that are within the given radius.\n",
    "\n",
    "- The outer vector corresponds to each descriptor in the query set (`descriptors1`).\n",
    "- The inner vector contains all matches found within the specified radius for that query descriptor.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4049296-efd0-4e05-a770-2eb587e0e61b",
   "metadata": {},
   "source": [
    "\n",
    "<img src=\"images/Radius_Match.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49a7dc69-a694-4383-8d4a-b3dd107037a8",
   "metadata": {},
   "source": [
    "## 2. **FlannBasedMatcher (Fast Library for Approximate Nearest Neighbors)**\n",
    "Efficient for large datasets by using an approximate nearest neighbor algorithm, suitable for high-dimensional data and faster than BFMatcher for larger datasets.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6e89460-1fcc-4fab-a28e-e122b616b170",
   "metadata": {},
   "source": [
    "\n",
    "```cpp\n",
    "cv::FlannBasedMatcher flannMatcher;\n",
    "std::vector<cv::DMatch> flannMatches;\n",
    "flannMatcher.match(descriptors1, descriptors2, flannMatches);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc988078-be7d-4f2c-8da7-78d0e779c300",
   "metadata": {},
   "source": [
    "### 3. `cv::DMatch` \n",
    "is a data structure in OpenCV that represents a match between two keypoints from different images, typically used in feature matching processes. It contains information about the correspondence between these keypoints, such as their indices and the quality of the match.\n",
    "\n",
    "**Members of `cv::DMatch`**\n",
    "1. **`int queryIdx`**  \n",
    "   - The index of the keypoint in the query image (the image from which you are searching for matches).\n",
    "   - It refers to a keypoint in the keypoint vector provided for the query image.\n",
    "\n",
    "2. **`int trainIdx`**  \n",
    "   - The index of the keypoint in the train image (the image being searched for matches).\n",
    "   - It refers to a keypoint in the keypoint vector provided for the train image.\n",
    "\n",
    "3. **`int imgIdx`**  \n",
    "   - The index of the image in the training dataset if you are using a collection of images. \n",
    "   - In most cases, this is not used directly when matching a single image to another, as `trainIdx` suffices.\n",
    "\n",
    "4. **`float distance`**  \n",
    "   - A measure of how well the descriptors of the two keypoints match.\n",
    "   - Typically, this is the Euclidean distance between the descriptor vectors of the two keypoints. A smaller distance indicates a better match.\n",
    "\n",
    "- `queryIdx` and `trainIdx` link the match to keypoints in the respective images.\n",
    "- `distance` is the main criterion for assessing the quality of a match. Matches with smaller distances are generally better.\n",
    "- Matches can be filtered based on the `distance` or other criteria (e.g., using Lowe's ratio test for better robustness)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c2b26a9-4912-4b87-8722-b757a966c8c4",
   "metadata": {},
   "source": [
    "## 4. Correspondence match refinement and rejection"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4352c83a-ae16-47a6-9a8e-d3f2cefcc47e",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "### 4.1 Lowe's Ratio Test\n",
    "\n",
    "It is a **validation step** that helps distinguish between good matches (true correspondences) and poor or ambiguous matches (false correspondences).The idea is based on the assumption that a good match should have a **significantly better similarity score** (smaller distance) than the next best alternative match.\n",
    "\n",
    "\n",
    "\n",
    "#### How Does it Work?\n",
    "\n",
    "1. **`knnMatch` Results**:\n",
    "   - For each descriptor in the first image, the `knnMatch` function retrieves the top `k` closest matches from the descriptors in the second image.\n",
    "   - Typically, `k=2` is used to retrieve the two best matches: `knnMatch[0]` (best match) and `knnMatch[1]` (second-best match).\n",
    "\n",
    "2. **Ratio Test**:\n",
    "   - Compare the distance of the best match (`knnMatch[0].distance`) to the distance of the second-best match (`knnMatch[1].distance`).\n",
    "   - If the ratio of these distances is below a predefined threshold (e.g., 0.75), it indicates a strong match. Otherwise, the match is considered ambiguous and discarded.\n",
    "\n",
    "   Mathematically:\n",
    "   $\n",
    "   \\text{If } \\frac{\\text{knnMatch[0].distance}}{\\text{knnMatch[1].distance}} < \\text{ratioThresh}, \\text{ accept the match.}\n",
    "   $\n",
    "\n",
    "   - **Typical `ratioThresh` Values**:\n",
    "     - The default threshold is often **0.7** or **0.75** (Lowe's original paper recommends 0.75).\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9a8b5a4-f2f2-45e8-80ef-94383709a49f",
   "metadata": {},
   "source": [
    "```cpp\n",
    "const float ratioThresh = 0.75f; // Lowe's ratio threshold\n",
    "std::vector<cv::DMatch> goodMatches;\n",
    "\n",
    "for (const auto& knnMatch : knnMatches) {\n",
    "    if (knnMatch.size() >= 2) { // Ensure at least two matches exist\n",
    "        // Apply Lowe's ratio test\n",
    "        if (knnMatch[0].distance < ratioThresh * knnMatch[1].distance) {\n",
    "            goodMatches.push_back(knnMatch[0]);\n",
    "        }\n",
    "    }\n",
    "}\n",
    "```\n",
    "\n",
    "---\n",
    "\n",
    "\n",
    "\n",
    "#### Example:\n",
    "Imagine the distances for a descriptor in image 1 are:\n",
    "- `knnMatch[0].distance = 0.3` (best match)\n",
    "- `knnMatch[1].distance = 0.5` (second-best match)\n",
    "\n",
    "$\n",
    "\\text{Ratio: } \\frac{0.3}{0.5} = 0.6\n",
    "$\n",
    "\n",
    "If `ratioThresh = 0.75`, this match passes the test.\n",
    "\n",
    "#### Counterexample:\n",
    "Now imagine the distances are:\n",
    "- `knnMatch[0].distance = 0.4`\n",
    "- `knnMatch[1].distance = 0.42`\n",
    "\n",
    "$\n",
    "\\text{Ratio: } \\frac{0.4}{0.42} \\approx 0.95\n",
    "$\n",
    "\n",
    "This match fails the test because the best match is not significantly better than the second-best match, indicating ambiguity.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d57e510-337b-42ee-abe3-e2153677e40f",
   "metadata": {},
   "source": [
    "```python\n",
    "matches = matcher.knnMatch(des1, des2, k=2)\n",
    "good_matches = []\n",
    "\n",
    "# Ratio Test:  For each keypoint, if the distance ratio between the best and the second-best match is below a\n",
    "# threshold (usually around 0.7 to 0.8), the match is retained.\n",
    "ratio_rest = 0.7\n",
    "for m, n in matches:\n",
    "    if m.distance < ratio_rest * n.distance:\n",
    "        good_matches.append(m)\n",
    "matches = good_matches\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "574fc21f-3c9c-4c9b-a620-23ebb2cfa463",
   "metadata": {},
   "source": [
    "### 4.2 Quantile-based filtering\n",
    "\n",
    "- If you choose \"2\", you are asking for all elements below the median (50th percentile).\n",
    "- If you choose \"4\", you are asking for elements below the 25th percentile (1/4 of the sorted data).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f97cedd3-73f5-43de-b1f1-d12f146f3159",
   "metadata": {},
   "source": [
    "```cpp\n",
    "    std::vector<cv::DMatch> matches;\n",
    "    matcher.match(descriptors[i], descriptors[i + 1], matches);\n",
    "    std::vector<float> distances;\n",
    "    for (const auto &match : matches) {\n",
    "      distances.push_back(match.distance);\n",
    "    }\n",
    "    std::nth_element(distances.begin(),\n",
    "                     distances.begin() + distances.size() / quantiles,\n",
    "                     distances.end());\n",
    "    float median_distance = distances[distances.size() / quantiles];\n",
    "\n",
    "    matches.erase(std::remove_if(matches.begin(), matches.end(),\n",
    "                                 [median_distance](const cv::DMatch &match) {\n",
    "                                   return match.distance > median_distance;\n",
    "                                 }),\n",
    "                  matches.end());\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e458064a-5c9a-45ba-8ce5-976f821d5bb5",
   "metadata": {},
   "source": [
    "```python\n",
    "kp1, des1 = detector.detectAndCompute(img1, None)\n",
    "kp2, des2 = detector.detectAndCompute(img2, None)\n",
    "\n",
    "matches = matcher.match(des1, des2)\n",
    "\n",
    "# Sort them based on the distance\n",
    "matches = sorted(matches, key=lambda x: x.distance)\n",
    "\n",
    "matches = matches[:int(len(matches)/top_k_matches)]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ccb1ee7-0d0f-417f-979e-ac72416a5183",
   "metadata": {},
   "source": [
    "## 5. Drawing Matches\n",
    "\n",
    "```cpp\n",
    "cv::drawMatches(img1, keypoints1, img2, keypoints2, matches, img_matches);\n",
    "```\n",
    "\n",
    "\n",
    "```python\n",
    "img_matches = cv2.drawMatches(img1, kp1, img2, kp2, matches, None, flags=2)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e83493a-ddeb-446f-ad91-0a59b36c78a2",
   "metadata": {},
   "source": [
    "[c++ code](../src/correspondences_matching.cpp)\n",
    "\n",
    "[python code](../scripts/correspondences_matching.py)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}