{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"name":"python","version":"3.10.12","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"kaggle":{"accelerator":"nvidiaTeslaT4","dataSources":[{"sourceId":91498,"databundleVersionId":11655853,"sourceType":"competition"}],"dockerImageVersionId":30918,"isInternetEnabled":false,"language":"python","sourceType":"notebook","isGpuEnabled":true}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Image Matching Challenge 2025: DTU Submission\n\n**Team:** Danmarks Tekniske Universitet <br>\n**Captain:** Dr. Gustav Olaf Yunus Laitinen-Fredriksson Lundström Imanov <br>\n**Members:** Kayrahan Ozcan, Umit Anik, Saliha Rana Uzun <br>\n\n---\n\n## Table of Contents\n1.  [Introduction](#Introduction)\n    *   1.1. [The Challenge: Beyond Pairwise Matching](#The-Challenge)\n    *   1.2. [Core Problem: Messy Data and Ambiguity](#Core-Problem)\n    *   1.3. [Our Approach: A Hybrid Strategy](#Our-Approach)\n    *   1.4. [Evaluation Metrics Recap](#Evaluation-Metrics)\n2.  [Setup and Environment](#Setup)\n    *   2.1. [Importing Libraries](#Importing-Libraries)\n    *   2.2. [Defining Constants and Paths](#Defining-Constants)\n    *   2.3. [Loading Competition Metadata](#Loading-Metadata)\n3.  [Exploratory Data Analysis (EDA)](#EDA)\n    *   3.1. [Understanding the Data Structure](#Data-Structure)\n    *   3.2. [Analyzing Training Labels](#Analyzing-Labels)\n    *   3.3. [Visualizing Image Samples](#Visualizing-Samples)\n    *   3.4. [Distribution Analysis](#Distribution-Analysis)\n4.  [Methodology](#Methodology)\n    *   4.1. [Overall Pipeline](#Pipeline-Diagram)\n    *   4.2. [Step 1: Feature Extraction](#Feature-Extraction)\n    *   4.3. [Step 2: Feature Matching and Geometric Verification](#Feature-Matching)\n    *   4.4. [Step 3: Image Clustering / Scene Segmentation](#Image-Clustering)\n    *   4.5. [Step 4: Structure from Motion (SfM) per Cluster](#SfM)\n    *   4.6. [Step 5: Pose Formatting and Handling Unregistered Images](#Pose-Formatting)\n5.  [Implementation Details](#Implementation)\n    *   5.1. [Feature Extraction Function](#Feature-Extraction-Function)\n    *   5.2. [Matching and Verification Function](#Matching-Function)\n    *   5.3. [View Graph and Clustering Function](#Clustering-Function)\n    *   5.4. [SfM Function (per cluster)](#SfM-Function)\n    *   5.5. [Pose Formatting Utility](#Pose-Format-Utility)\n6.  [Main Processing Logic](#Main-Logic)\n    *   6.1. [Processing Loop Structure](#Loop-Structure)\n    *   6.2. [Applying Functions to Test Data](#Applying-Functions)\n7.  [Evaluation (Conceptual)](#Evaluation)\n    *   7.1. [Defining the Evaluation Metrics in Code](#Metrics-Code)\n    *   7.2. [Applying Evaluation (Example on Train Data)](#Applying-Evaluation)\n8.  [Submission Generation](#Submission)\n    *   8.1. [Generating the Final `submission.csv`](#Generating-Submission)\n9.  [Conclusion and Future Work](#Conclusion)\n    *   9.1. [Summary of Approach and Findings](#Summary)\n    *   9.2. [Limitations](#Limitations)\n    *   9.3. [Potential Improvements](#Improvements)\n10. [References](#References)\n\n---","metadata":{"_uuid":"e6a7d13b-0f14-4e15-8a43-5f1eabbb447c","_cell_guid":"c90b5f12-ad02-4ff8-b593-0e55092f33f5","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"markdown","source":"## 1. Introduction <a name=\"Introduction\"></a>\n\n### 1.1. The Challenge: Beyond Pairwise Matching <a name=\"The-Challenge\"></a>\nThe Image Matching Challenge 2025 extends previous iterations by requiring participants not only to perform 3D reconstruction (estimating camera poses) but also to determine *which* images belong together in a scene and which are outliers. This addresses a critical real-world problem where image collections are often unstructured and contain unrelated data.\n\n### 1.2. Core Problem: Messy Data and Ambiguity <a name=\"Core-Problem\"></a>\nReconstructing 3D scenes from arbitrary internet or crowdsourced image collections is notoriously difficult. Challenges include:\n*   **Unrelated Images:** Photos taken nearby but irrelevant to the main scene (e.g., a selfie near a landmark).\n*   **Visual Ambiguity:** Different parts of a structure appearing very similar (e.g., two identical facades of a building).\n*   **Varying Conditions:** Changes in lighting, weather, viewpoint, and camera types.\n*   **Lack of Reliable Metadata:** GPS data might be inaccurate or unavailable.\n\nThis competition simulates these issues, forcing methods to be robust in grouping and discarding images appropriately.\n\n### 1.3. Our Approach: A Hybrid Strategy <a name=\"Our-Approach\"></a>\nWe propose a pipeline combining classical computer vision techniques with graph-based clustering:\n1.  **Feature Extraction:** Detect and describe keypoints in each image using SIFT, known for its robustness.\n2.  **Matching & Verification:** Find potential correspondences between image pairs and rigorously verify them using the epipolar constraint (Fundamental Matrix estimation via RANSAC).\n3.  **Clustering:** Construct a 'view graph' where images are nodes and edges represent strong geometric consistency. Apply graph clustering (e.g., connected components or spectral clustering) to partition the graph into scene candidates. Identify isolated nodes or small components as outliers.\n4.  **Structure from Motion (SfM):** For each cluster, perform incremental SfM to recover camera poses (Rotation **R** and Translation **T**). This involves initialization, iterative image registration (PnP), and potentially triangulation. Bundle adjustment, while crucial for high accuracy, is complex and computationally intensive for a kernel environment; we focus on robust PnP registration.\n5.  **Output:** Format the results, assigning cluster labels and poses (or `nan` for outliers/unregistered images).\n\n### 1.4. Evaluation Metrics Recap <a name=\"Evaluation-Metrics\"></a>\nThe final score is the harmonic mean (F1-score) of the mean Average Accuracy (mAA) and a Clustering Score, averaged over datasets.\n\n*   **mAA (per cluster C w.r.t. scene S):** Measures the recall of correctly registered images from scene S within cluster C.\n    $$ \\text{mAA}(C, S) = \\frac{|\\{\\text{Registered images of } S \\text{ found in } C\\}|}{|S|} $$\n*   **Clustering Score (per cluster C w.r.t. scene S):** Measures the precision of cluster C with respect to scene S.\n    $$ \\text{ClusteringScore}(C, S) = \\frac{|S \\cap C|}{|C|} $$\n*   **Greedy Assignment:** Each ground truth scene $S_{ki}$ is matched to the predicted cluster $C_{kj_i}$ that maximizes $mAA(C_{kj}, S_{ki})$, breaking ties with the Clustering Score.\n*   **Dataset Clustering Score:** Aggregated precision over matched clusters.\n    $$ \\text{DatasetClusteringScore}_k = \\frac{\\sum_i |S_{ki} \\cap C_{kj_i}|}{\\sum_i |C_{kj_i}|} $$\n*   **Dataset mAA Score:** Aggregated recall over matched clusters (calculated using the mAA definition).\n*   **Combined Score $S_k$:** Harmonic mean for dataset $k$.\n    $$ S_k = 2 \\times \\frac{(\\text{Dataset\\_mAA}_k \\times \\text{Dataset\\_ClusteringScore}_k)}{(\\text{Dataset\\_mAA}_k + \\text{Dataset\\_ClusteringScore}_k)} $$\n*   **Final Score:** Average of $S_k$ over all datasets.","metadata":{"_uuid":"1dafa339-269c-4b8c-a978-9253a4ddb742","_cell_guid":"fc18e3df-a250-4a73-b428-c29d90df4332","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"markdown","source":"## 2. Setup and Environment <a name=\"Setup\"></a>","metadata":{"_uuid":"47bec39e-db56-4aa1-a8d3-e90edcbac7a9","_cell_guid":"f6cca29b-f492-439f-a5e3-ee7153e80559","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"code","source":"# ### 2.1. Importing Libraries <a name=\"Importing-Libraries\"></a>\nimport numpy as np\nimport pandas as pd\nimport cv2\nimport matplotlib.pyplot as plt\nimport seaborn as sns\nfrom pathlib import Path\nimport networkx as nx\nfrom sklearn.cluster import SpectralClustering # For graph clustering alternative\nfrom tqdm.notebook import tqdm # Progress bars\nimport os\nimport gc # Garbage collection for memory management\nfrom collections import defaultdict\nimport time\n\nprint(\"Libraries imported.\")\nprint(f\"OpenCV version: {cv2.__version__}\")\nprint(f\"NetworkX version: {nx.__version__}\")\nprint(f\"Pandas version: {pd.__version__}\")\nprint(f\"Numpy version: {np.__version__}\")","metadata":{"_uuid":"09c02dbb-8657-43ac-bb25-f4ebe0988f24","_cell_guid":"093bb3fb-b491-4679-8816-205e0f2acc3d","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"# ### 2.2. Defining Constants and Paths <a name=\"Defining-Constants\"></a>\n\n# Determine if running in Kaggle environment and set paths accordingly\nIS_KAGGLE = os.path.exists('/kaggle/input')\nif IS_KAGGLE:\n    DATA_DIR = Path('/kaggle/input/image-matching-challenge-2025/')\n    OUTPUT_DIR = Path('/kaggle/working/')\n    # For submission, the test directory might be different, handled later\n    TEST_DIR_PUBLIC = DATA_DIR / 'test' # Public test for code dev\nelse:\n    # Set local paths if running outside Kaggle\n    DATA_DIR = Path('./data/') # Adjust this to your local data path\n    TEST_DIR_PUBLIC = DATA_DIR / 'test'\n    OUTPUT_DIR = Path('./output/')\n    OUTPUT_DIR.mkdir(exist_ok=True)\n\nTRAIN_DIR = DATA_DIR / 'train'\n\n# --- Feature Extraction Parameters ---\n# Options: 'SIFT', 'AKAZE', 'ORB' (DISK/ALIKED need external setup)\nFEATURE_EXTRACTOR_TYPE = 'SIFT'\nSIFT_NFEATURES = 8000 # Max features per image for SIFT\n\n# --- Matching Parameters ---\nMATCHER_TYPE = 'FLANN' # 'BF' (Brute Force) or 'FLANN' (Fast Library for Approximate Nearest Neighbors)\nLOWE_RATIO_TEST_THRESHOLD = 0.8 # For filtering good matches (knnMatch ratio)\nMIN_INLIER_MATCHES_INITIAL = 15 # Min inliers for initial pairwise geometry check\nMIN_INLIER_MATCHES_GRAPH = 10 # Min inliers to add edge to view graph (can be lower)\n\n# --- Geometric Verification (RANSAC for Fundamental Matrix) ---\nRANSAC_THRESHOLD = 1.5 # RANSAC reprojection threshold in pixels for findFundamentalMat\n\n# --- Clustering Parameters ---\n# Options: 'ConnectedComponents', 'Spectral'\nCLUSTERING_ALGORITHM = 'ConnectedComponents'\nMIN_CLUSTER_SIZE = 3 # Minimum images to form a valid scene cluster\n\n# --- SfM Parameters ---\nMIN_VIEWS_FOR_TRIANGULATION = 2 # Need at least two views for triangulation\nPNP_RANSAC_THRESHOLD = 5.0 # RANSAC reprojection threshold for solvePnPRansac\nPNP_CONFIDENCE = 0.999 # Confidence for PnPRansac\nMIN_3D_POINTS_FOR_PNP = 6 # Minimum 3D points required for PnP\n\n# --- Camera Intrinsics (Approximation - Not submitted, but needed for E/PnP) ---\n# We estimate a default K matrix. Real K varies per image, but this is a common\n# simplification if intrinsics aren't provided or estimated.\n# Focal length is often approximated based on image width.\nDEFAULT_FOCAL_LENGTH_FACTOR = 1.2\n# Assuming cx, cy are image center. Will be calculated per image later.\n\n# --- Submission Runtime Control ---\nMAX_RUNTIME_SECONDS = 8.5 * 3600 # Slightly less than 9 hours Kaggle limit\nSTART_TIME = time.time()\n\nprint(f\"Constants defined. Using {FEATURE_EXTRACTOR_TYPE} features and {MATCHER_TYPE} matcher.\")\nprint(f\"Running in {'Kaggle' if IS_KAGGLE else 'Local'} environment.\")\nprint(f\"Data Directory: {DATA_DIR}\")","metadata":{"_uuid":"492a1a4a-c71f-4103-98a0-b91de9a5843b","_cell_guid":"c47198ee-dc57-44b3-84d4-89d0764b3ea0","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"# ### 2.3. Loading Competition Metadata <a name=\"Loading-Metadata\"></a>\ntry:\n    train_labels_df = pd.read_csv(DATA_DIR / 'train_labels.csv')\n    train_thresholds_df = pd.read_csv(DATA_DIR / 'train_thresholds.csv')\n    sample_submission_df = pd.read_csv(DATA_DIR / 'sample_submission.csv')\n\n    print(\"--- Train Labels Info ---\")\n    train_labels_df.info()\n    print(f\"\\nLoaded {len(train_labels_df)} training labels.\")\n    print(train_labels_df.head())\n\n    print(\"\\n--- Train Thresholds Info ---\")\n    train_thresholds_df.info()\n    print(f\"Loaded {len(train_thresholds_df)} training thresholds.\")\n    print(train_thresholds_df.head())\n\n    print(\"\\n--- Sample Submission Info ---\")\n    sample_submission_df.info()\n    print(f\"Loaded {len(sample_submission_df)} sample submission rows.\")\n    print(sample_submission_df.head())\n\nexcept FileNotFoundError as e:\n    print(f\"Error loading metadata: {e}\")\n    print(\"Please ensure the data is correctly placed in the DATA_DIR.\")\n    # Handle error appropriately, maybe exit or use dummy data if developing\n    if IS_KAGGLE: # If in Kaggle and files are missing, it's a problem\n        raise e\n    else: # If local, maybe we proceed with dummy data for structure testing\n        print(\"Proceeding without metadata (for structure testing only).\")\n        train_labels_df = pd.DataFrame() # Dummy dataframes\n        train_thresholds_df = pd.DataFrame()\n        sample_submission_df = pd.DataFrame()","metadata":{"_uuid":"2e8fd89d-99e7-4392-8b6c-928f212a9da4","_cell_guid":"91619ffa-5e10-4ad7-ae27-57cbb1f44aa7","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## 3. Exploratory Data Analysis (EDA) <a name=\"EDA\"></a>\n*(Note: EDA primarily uses the training data to understand patterns. The actual test data is hidden during submission scoring.)*","metadata":{"_uuid":"e7f129fa-8125-4714-983f-829a9cbf1e67","_cell_guid":"18b63e30-d613-41a6-b958-95b71c3753a1","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"code","source":"# ### 3.1. Understanding the Data Structure <a name=\"Data-Structure\"></a>\nif not train_labels_df.empty:\n    datasets_train = train_labels_df['dataset'].unique()\n    print(f\"Training datasets ({len(datasets_train)}): {datasets_train}\")\n\n    # List subdirectories in train and test (public)\n    train_folders = [f.name for f in TRAIN_DIR.iterdir() if f.is_dir()]\n    print(f\"\\nFolders in {TRAIN_DIR} ({len(train_folders)}): {train_folders}\")\n\n    if TEST_DIR_PUBLIC.exists():\n        test_folders = [f.name for f in TEST_DIR_PUBLIC.iterdir() if f.is_dir()]\n        print(f\"\\nFolders in {TEST_DIR_PUBLIC} ({len(test_folders)}): {test_folders}\")\n    else:\n        print(f\"\\nPublic test directory {TEST_DIR_PUBLIC} not found.\")\n\nelse:\n    print(\"Skipping EDA as training labels are not loaded.\")","metadata":{"_uuid":"0c0835e2-bca3-45e5-aaf6-61af61ec8f6c","_cell_guid":"9c58371a-4064-428b-af19-db256efa37cb","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"# ### 3.2. Analyzing Training Labels <a name=\"Analyzing-Labels\"></a>\nif not train_labels_df.empty:\n    # Calculate scenes per dataset\n    scenes_per_dataset = train_labels_df.groupby('dataset')['scene'].nunique()\n    # Calculate images per scene (excluding outliers for distribution stats)\n    images_per_scene = train_labels_df[train_labels_df['scene'] != 'outliers'].groupby(['dataset', 'scene']).size().reset_index(name='image_count')\n    # Outlier counts per dataset\n    outliers_per_dataset = train_labels_df[train_labels_df['scene'] == 'outliers'].groupby('dataset').size()\n\n    print(\"\\n--- Scenes per Dataset (including 'outliers' as a scene) ---\")\n    print(scenes_per_dataset)\n\n    print(\"\\n--- Statistics on Images per Scene (excluding outliers) ---\")\n    print(images_per_scene['image_count'].describe())\n\n    print(\"\\n--- Outlier Images per Dataset ---\")\n    print(outliers_per_dataset)\n\n    # Plotting\n    plt.figure(figsize=(15, 12))\n\n    plt.subplot(2, 2, 1)\n    sns.barplot(x=scenes_per_dataset.index, y=scenes_per_dataset.values)\n    plt.title('Number of Scenes per Dataset')\n    plt.xlabel('Dataset')\n    plt.ylabel('Number of Scenes')\n    plt.xticks(rotation=45, ha='right')\n\n    plt.subplot(2, 2, 2)\n    sns.histplot(images_per_scene['image_count'], bins=30, kde=True)\n    plt.title('Distribution of Images per Scene (Excluding Outliers)')\n    plt.xlabel('Number of Images')\n    plt.ylabel('Frequency')\n    plt.tight_layout()\n\n    plt.subplot(2, 2, 3)\n    if not outliers_per_dataset.empty:\n        sns.barplot(x=outliers_per_dataset.index, y=outliers_per_dataset.values)\n        plt.title('Number of Outlier Images per Dataset')\n        plt.xlabel('Dataset')\n        plt.ylabel('Number of Outliers')\n        plt.xticks(rotation=45, ha='right')\n    else:\n        plt.text(0.5, 0.5, 'No Outliers Found', ha='center', va='center')\n        plt.title('Outlier Images per Dataset')\n\n\n    plt.tight_layout()\n    plt.show()\n\nelse:\n    print(\"Skipping label analysis as training labels are not loaded.\")","metadata":{"_uuid":"c3a2c3d1-a12f-4de6-94ca-c6ff0f4eb1cb","_cell_guid":"6d621c94-40f2-4d07-a6b2-acb0d6b4d176","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"# ### 3.3. Visualizing Image Samples <a name=\"Visualizing-Samples\"></a>\n# Function to display sample images from a dataset\ndef display_dataset_samples(dataset_name, n_scenes_to_show=2, n_samples_per_scene=3):\n    if train_labels_df.empty:\n        print(\"Cannot display samples without train_labels_df.\")\n        return\n\n    dataset_labels = train_labels_df[train_labels_df['dataset'] == dataset_name]\n    if dataset_labels.empty:\n        print(f\"No labels found for dataset: {dataset_name}\")\n        return\n\n    scenes = dataset_labels['scene'].unique()\n    print(f\"Scenes in {dataset_name}: {scenes}\")\n\n    plt.figure(figsize=(15, 5 * n_scenes_to_show))\n    plot_idx = 1\n\n    # Show samples from regular scenes\n    regular_scenes = [s for s in scenes if s != 'outliers'][:n_scenes_to_show]\n    for scene in regular_scenes:\n        scene_images = dataset_labels[dataset_labels['scene'] == scene]['image'].sample(min(n_samples_per_scene, len(dataset_labels[dataset_labels['scene'] == scene]))).tolist()\n        for img_name in scene_images:\n            img_path = TRAIN_DIR / dataset_name / img_name\n            if img_path.exists():\n                img = cv2.imread(str(img_path))\n                img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)\n                ax = plt.subplot(n_scenes_to_show + 1, n_samples_per_scene, plot_idx) # +1 for outliers row\n                ax.imshow(img)\n                ax.set_title(f\"Scene: {scene}\\n{img_name}\", fontsize=8)\n                ax.axis('off')\n            plot_idx += 1\n        # Fill remaining plots in the row if fewer samples found\n        plot_idx = ( (plot_idx -1) // n_samples_per_scene + 1) * n_samples_per_scene + 1\n\n\n    # Show samples from outliers if they exist\n    if 'outliers' in scenes:\n         outlier_images = dataset_labels[dataset_labels['scene'] == 'outliers']['image'].sample(min(n_samples_per_scene, len(dataset_labels[dataset_labels['scene'] == 'outliers']))).tolist()\n         # Adjust starting plot index for outlier row\n         plot_idx = n_scenes_to_show * n_samples_per_scene + 1\n         for img_name in outlier_images:\n             img_path = TRAIN_DIR / dataset_name / 'outliers' / img_name # Check specific outlier folder if structure dictates\n             # Fallback to main folder if outlier folder doesn't exist or image isn't there\n             if not img_path.exists():\n                 img_path = TRAIN_DIR / dataset_name / img_name\n\n             if img_path.exists():\n                 img = cv2.imread(str(img_path))\n                 img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)\n                 ax = plt.subplot(n_scenes_to_show + 1, n_samples_per_scene, plot_idx)\n                 ax.imshow(img)\n                 ax.set_title(f\"Scene: outliers\\n{img_name}\", fontsize=8)\n                 ax.axis('off')\n             plot_idx += 1\n\n\n    plt.suptitle(f\"Sample Images from Dataset: {dataset_name}\", fontsize=16)\n    plt.tight_layout(rect=[0, 0.03, 1, 0.95]) # Adjust layout to prevent title overlap\n    plt.show()\n\n# Display samples from a dataset known to have multiple scenes/outliers\nif not train_labels_df.empty:\n    example_dataset = 'imc2024_lizard_pond' # Choose a dataset from EDA\n    if example_dataset in train_labels_df['dataset'].unique():\n         display_dataset_samples(example_dataset)\n    else:\n        print(f\"Example dataset '{example_dataset}' not found in labels. Choose another.\")\n        if len(datasets_train)>0:\n             display_dataset_samples(datasets_train[0]) # Show first dataset if example not found\nelse:\n    print(\"Skipping visualization as training labels are not loaded.\")","metadata":{"_uuid":"2a4d7638-5530-4bac-989f-fe730eadd18c","_cell_guid":"e9536cac-c3bf-4a48-b4e7-52542bd62d7c","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"### 3.4. Distribution Analysis <a name=\"Distribution-Analysis\"></a>\n*(Distribution plots were generated in section 3.2)*\n\nKey observations from EDA (example):\n*   Datasets vary significantly in the number of scenes and images per scene.\n*   Some datasets contain a substantial number of designated outlier images.\n*   The visual similarity within scenes and potential dissimilarity between scenes needs careful handling by the matching and clustering stages.","metadata":{"_uuid":"8637f8df-a8ab-4738-ad81-44a2d7243946","_cell_guid":"b4f3d219-efb9-4215-ba83-040f74eef840","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"markdown","source":"## 4. Methodology <a name=\"Methodology\"></a>\n\n### 4.1. Overall Pipeline <a name=\"Pipeline-Diagram\"></a>\nThe processing pipeline for each dataset involves the following steps:\n\n```mermaid\ngraph TD\n    A[Input: Image Collection for Dataset D] --> B{Feature Extraction};\n    B --> C{Pairwise Matching & Geometric Verification};\n    C --> D{Build View Graph};\n    D --> E{Graph Clustering};\n    E --> F{Identify Outliers};\n    E --> G{For Each Cluster C_i};\n    G --> H{Initialize SfM (2 views)};\n    H --> I{Iteratively Register New Views (PnP)};\n    I --> J{Triangulate 3D Points (Optional Refinement)};\n    J --> K{Store Poses (R, T)};\n    F --> L[Label as Outliers];\n    K --> M{Format Results};\n    L --> M;\n    M --> N[Output: submission.csv fragment for D];\n```\n*Note: Mermaid diagrams might not render directly in all Kaggle notebook viewers.*\n\n**Pipeline Description:**\n1.  **Feature Extraction:** Detect and compute descriptors (e.g., SIFT) for all images in the dataset.\n2.  **Matching & Verification:** For each pair of images, find potential feature matches and verify them geometrically using the Fundamental Matrix estimated with RANSAC. Store the number of inlier matches.\n3.  **View Graph:** Construct a graph where nodes are images. An edge exists between two images if they have a sufficient number of geometrically verified matches (inliers). Edge weight can be the number of inliers.\n4.  **Clustering:** Apply a graph clustering algorithm (like finding connected components or spectral clustering) to partition the graph. Each partition (cluster) represents a potential scene.\n5.  **Outlier Identification:** Nodes with very low degree in the graph or belonging to very small clusters (below `MIN_CLUSTER_SIZE`) are marked as outliers.\n6.  **Structure from Motion (SfM):** Process each valid cluster independently:\n    *   Select a robust initial pair of images within the cluster.\n    *   Compute their relative pose (**R**, **t**) and triangulate initial 3D points.\n    *   Iteratively select unregistered images that have sufficient matches to already registered images' features (which correspond to known 3D points).\n    *   Estimate the pose of the new image using `cv2.solvePnPRansac` (Perspective-n-Point algorithm).\n    *   Store the estimated absolute pose (**R**, **T**) for each registered image relative to the cluster's coordinate system.\n    *   Images within a cluster that cannot be registered via PnP are marked as unregistered (pose = `nan`).\n7.  **Formatting:** Combine the results, assigning cluster labels (e.g., `cluster1`, `cluster2`, ...) and poses. Assign the `outliers` label and `nan` poses to outlier images and unregistered images.\n\n### 4.2. Step 1: Feature Extraction <a name=\"Feature-Extraction\"></a>\n*   **Theory:** Local invariant features like SIFT (Scale-Invariant Feature Transform) detect keypoints and compute descriptors that are robust to changes in scale, rotation, illumination, and viewpoint. This allows matching images taken under different conditions.\n*   **Method:** We use `cv2.SIFT_create(nfeatures=SIFT_NFEATURES)`. Other options like AKAZE (`cv2.AKAZE_create()`) offer potential speed benefits and are license-friendly, while ORB is faster but less robust to scale/rotation.\n\n### 4.3. Step 2: Feature Matching and Geometric Verification <a name=\"Feature-Matching\"></a>\n*   **Theory:**\n    *   **Matching:** Find candidate correspondences by comparing feature descriptors (e.g., using Euclidean distance for SIFT). Brute-Force (BF) or FLANN matchers are common. FLANN is generally faster for large descriptor sets.\n    *   **Ratio Test:** Lowe's ratio test helps discard ambiguous matches by comparing the distance of the best match ($d_1$) to the second-best match ($d_2$). A match is kept if $d_1 / d_2 < \\text{ratio\\_threshold}$.\n    *   **Geometric Verification:** False matches often violate geometric constraints between two views. The **epipolar constraint** relates corresponding points $\\mathbf{p}$ in image 1 and $\\mathbf{p'}$ in image 2 via the **Fundamental Matrix F**:\n        $$ \\mathbf{p'}^T \\mathbf{F} \\mathbf{p} = 0 $$\n        The Fundamental Matrix ($3 \\times 3$, rank 2) encapsulates the relative camera geometry (rotation and translation direction) and intrinsic parameters (though often estimated without explicit K first).\n    *   **RANSAC (RANdom SAmple Consensus):** An iterative method to estimate parameters (here, the matrix **F**) from data containing outliers. It randomly samples minimal subsets of matches (7 for F), computes **F**, and counts how many other matches (inliers) are consistent with this **F** (i.e., satisfy the epipolar constraint within a threshold). The **F** supported by the largest set of inliers is chosen.\n*   **Method:** We use `cv2.BFMatcher` or `cv2.FlannBasedMatcher` with `knnMatch(k=2)`, apply the ratio test, and then use `cv2.findFundamentalMat` with `cv2.FM_RANSAC`. The number of inliers found is a strong indicator of geometric consistency.\n\n### 4.4. Step 3: Image Clustering / Scene Segmentation <a name=\"Image-Clustering\"></a>\n*   **Motivation:** Group images belonging to the same physical scene based on pairwise geometric consistency.\n*   **Approach: View Graph:** Construct $G = (V, E)$, where $V$ is the set of images and an edge $(i, j) \\in E$ exists if `num_inliers(i, j) >= MIN_INLIER_MATCHES_GRAPH`. The edge weight $w(i, j)$ can be `num_inliers(i, j)`.\n*   **Clustering Algorithm:**\n    *   **Connected Components:** Simple and fast. Finds groups of images where you can reach any image from any other within the group by following edges. Treats each component as a scene. (`nx.connected_components`)\n    *   **Spectral Clustering:** Uses the eigenvectors of the graph Laplacian. Can sometimes find better clusters, especially if connected components merge unrelated scenes weakly linked. Requires specifying the number of clusters or estimating it. (`sklearn.cluster.SpectralClustering`)\n    *   *(Other options like Louvain exist but may require extra libraries.)*\n*   **Outlier Detection:** Images not part of any cluster (isolated nodes) or belonging to clusters smaller than `MIN_CLUSTER_SIZE` are designated as outliers.\n\n### 4.5. Step 4: Structure from Motion (SfM) per Cluster <a name=\"SfM\"></a>\n*   **Theory:** Recover the 3D structure of the scene and the camera poses (absolute **R**, **T** relative to a common coordinate system for the cluster) for images within a cluster.\n*   **Simplified Incremental SfM:**\n    1.  **Initialization:** Select a robust initial pair $(i, j)$ within the cluster (high number of inliers, sufficient baseline). Estimate their relative pose $(\\mathbf{R}_{rel}, \\mathbf{t}_{rel})$ using the **Essential Matrix E**. The Essential matrix ($3 \\times 3$, rank 2, special properties) relates *normalized* image coordinates: $\\mathbf{p'}_{norm}^T \\mathbf{E} \\mathbf{p}_{norm} = 0$. It can be computed from **F** if intrinsics **K** are known ($\\mathbf{E} = \\mathbf{K'}^T \\mathbf{F} \\mathbf{K}$) or estimated directly. `cv2.findEssentialMat` and `cv2.recoverPose` handle this. Set the first camera pose as $[\\mathbf{I} | \\mathbf{0}]$ and the second as $[\\mathbf{R}_{rel} | \\mathbf{t}_{rel}]$.\n    2.  **Triangulation:** Reconstruct the 3D positions $\\mathbf{X}$ of points corresponding to matched features between the initial pair using `cv2.triangulatePoints`.\n    3.  **Image Registration (PnP):** For a new image $k$ with matches to already registered images:\n        *   Identify 2D features $\\mathbf{p}_k$ in image $k$ that correspond to known 3D points $\\mathbf{X}$.\n        *   Use the Perspective-n-Point (PnP) algorithm (`cv2.solvePnPRansac`) to estimate the absolute pose $(\\mathbf{R}_k, \\mathbf{T}_k)$ of image $k$ that minimizes the reprojection error:\n            $$ \\underset{\\mathbf{R}_k, \\mathbf{T}_k}{\\operatorname{argmin}} \\sum_i \\| \\mathbf{p}_{ki} - \\pi(\\mathbf{R}_k \\mathbf{X}_i + \\mathbf{T}_k) \\|^2 $$\n            where $\\pi$ is the camera projection function (using estimated/default intrinsics **K**). RANSAC handles outliers among the 2D-3D matches.\n    4.  **Bundle Adjustment (BA) - Conceptual:** Ideally, after adding several views, BA would globally refine all poses $(\\mathbf{R}_j, \\mathbf{T}_j)$ and 3D points $\\mathbf{X}_i$ simultaneously by minimizing the total reprojection error over all views and points. This is computationally expensive and complex. *Our implementation relies on robust PnP and skips full BA.*\n*   **Method:** Use OpenCV functions: `findEssentialMat`, `recoverPose`, `triangulatePoints`, `solvePnPRansac`. Handle failures in any step (e.g., insufficient points, PnP failure) by marking the image as unregistered for that cluster.\n\n### 4.6. Step 5: Pose Formatting and Handling Unregistered Images <a name=\"Pose-Formatting\"></a>\n*   **Output Format:** For each image, provide its assigned `dataset`, `scene` (cluster label or `outliers`), `image` filename.\n*   **Poses:**\n    *   If successfully registered in a cluster, provide the $3 \\times 3$ rotation matrix $\\mathbf{R}$ and $3 \\times 1$ translation vector $\\mathbf{T}$.\n    *   Flatten $\\mathbf{R}$ row-major: `r11;r12;r13;r21;r22;r23;r31;r32;r33`.\n    *   Format $\\mathbf{T}$ as `t1;t2;t3`.\n*   **NaN Values:** For images assigned to `outliers` or those that could *not* be registered within their assigned cluster (due to SfM/PnP failures), use `nan;nan;...;nan` for both `rotation_matrix` and `translation_vector`.","metadata":{"_uuid":"29dd540a-ed7d-4afc-92c3-cc822e9fe66d","_cell_guid":"baaaada8-faf3-4c36-a813-68160bc71001","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"markdown","source":"## 5. Implementation Details <a name=\"Implementation\"></a>","metadata":{"_uuid":"01c5f416-3330-402c-989f-756868db0589","_cell_guid":"a0ab5dde-ae37-414a-bece-504584245159","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"code","source":"# ### 5.1. Feature Extraction Function <a name=\"Feature-Extraction-Function\"></a>\n\ndef get_feature_extractor(extractor_type='SIFT'):\n    \"\"\"Creates the specified OpenCV feature extractor.\"\"\"\n    if extractor_type == 'SIFT':\n        return cv2.SIFT_create(nfeatures=SIFT_NFEATURES)\n    elif extractor_type == 'AKAZE':\n        # AKAZE needs descriptors of size 61*8 = 488 bits\n        return cv2.AKAZE_create()\n    elif extractor_type == 'ORB':\n        return cv2.ORB_create(nfeatures=SIFT_NFEATURES) # Use same nfeatures param for consistency\n    # Add other types like BRISK if needed\n    else:\n        raise ValueError(f\"Unsupported feature extractor type: {extractor_type}\")\n\ndef extract_features(image_path, extractor):\n    \"\"\"Extracts keypoints and descriptors from an image file.\"\"\"\n    img = cv2.imread(str(image_path), cv2.IMREAD_GRAYSCALE)\n    if img is None:\n        print(f\"Warning: Could not read image {image_path}\")\n        return None, None, (None, None)\n\n    # Check if image dimensions are too small (might cause issues)\n    h, w = img.shape\n    if h < 20 or w < 20: # Example threshold\n        # print(f\"Warning: Image {image_path} is very small ({w}x{h}), skipping feature extraction.\")\n        return None, None, (w,h)\n\n\n    kps, descs = extractor.detectAndCompute(img, None)\n\n    if kps is None or descs is None or len(kps) == 0:\n         # print(f\"Warning: No features found for image {image_path}\")\n         return None, None, (w,h)\n\n    # Convert keypoints to a standard format if needed (e.g., for serialization)\n    # kps_tuples = [(kp.pt, kp.size, kp.angle, kp.response, kp.octave, kp.class_id) for kp in kps]\n    # For direct use with OpenCV, keep the original KeyPoint objects\n    return kps, descs, (w, h) # Return image dimensions as well\n\ndef load_and_extract_features_dataset(dataset_id, dataset_base_path, extractor):\n    \"\"\"Loads all images for a dataset and extracts features.\"\"\"\n    features = {}\n    image_dims = {}\n    dataset_path = dataset_base_path / dataset_id\n    image_files = list(dataset_path.glob('*.png')) + list(dataset_path.glob('*.jpg')) + list(dataset_path.glob('*.jpeg'))\n\n    # Handle potential 'outliers' subdirectory - check if needed based on actual data structure\n    outlier_path = dataset_path / 'outliers'\n    if outlier_path.is_dir():\n        print(f\"Including images from outliers subdirectory for {dataset_id}\")\n        image_files.extend(list(outlier_path.glob('*.png')) + list(outlier_path.glob('*.jpg')) + list(outlier_path.glob('*.jpeg')))\n\n\n    print(f\"Extracting features for {len(image_files)} images in dataset {dataset_id}...\")\n    for img_path in tqdm(image_files, desc=f\"Features {dataset_id}\"):\n        image_id = img_path.name # Use filename as unique ID within dataset\n        kps, descs, dims = extract_features(img_path, extractor)\n        if kps is not None and descs is not None:\n            features[image_id] = (kps, descs)\n            image_dims[image_id] = dims\n        else:\n             # Store dims even if features failed, might be needed for K matrix\n             if dims[0] is not None:\n                 image_dims[image_id] = dims\n\n    return features, image_dims\n\n\n# Example Usage (can be commented out during full run)\n# sift = get_feature_extractor(FEATURE_EXTRACTOR_TYPE)\n# example_img_path = next((TRAIN_DIR / 'imc2024_lizard_pond').glob('*.png'), None) # Get one image\n# if example_img_path:\n#     kps, descs, dims = extract_features(example_img_path, sift)\n#     if kps:\n#         print(f\"Extracted {len(kps)} features from {example_img_path.name}\")\n#         img_bgr = cv2.imread(str(example_img_path))\n#         img_rgb = cv2.cvtColor(img_bgr, cv2.COLOR_BGR2RGB)\n#         img_kps = cv2.drawKeypoints(img_rgb, kps, None, flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)\n#         plt.figure(figsize=(10, 7))\n#         plt.imshow(img_kps)\n#         plt.title(f\"Features ({FEATURE_EXTRACTOR_TYPE}) on {example_img_path.name}\")\n#         plt.axis('off')\n#         plt.show()\n# else:\n#     print(\"Could not find an example image for feature extraction demo.\")","metadata":{"_uuid":"e109d684-a34f-4f33-b537-a2a2cb532b70","_cell_guid":"5706d3c9-5fad-4964-96c4-e299c08aa08c","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"# ### 5.2. Matching and Verification Function <a name=\"Matching-Function\"></a>\n\ndef get_matcher(matcher_type='FLANN', extractor_type='SIFT'):\n    \"\"\"Creates the specified OpenCV feature matcher.\"\"\"\n    if matcher_type == 'BF':\n        # Use appropriate norm type based on descriptor\n        if extractor_type in ['SIFT', 'SURF']: # SURF is patented, usually avoid\n             norm_type = cv2.NORM_L2\n        elif extractor_type in ['ORB', 'BRISK', 'AKAZE']: # Binary descriptors\n             norm_type = cv2.NORM_HAMMING\n        else: # Default assumption\n             norm_type = cv2.NORM_L2\n        return cv2.BFMatcher(norm_type, crossCheck=False) # Use crossCheck=False for knnMatch\n\n    elif matcher_type == 'FLANN':\n        # FLANN parameters depend on descriptor type\n        if extractor_type in ['SIFT', 'SURF']:\n            # FLANN_INDEX_KDTREE = 1\n            index_params = dict(algorithm=1, trees=5)\n            search_params = dict(checks=50) # or pass empty dictionary\n        elif extractor_type in ['ORB', 'BRISK', 'AKAZE']:\n            # FLANN_INDEX_LSH = 6\n            # Parameters are tuned for ORB, may need adjustment for others\n            index_params= dict(algorithm = 6,\n                               table_number = 6, # 12\n                               key_size = 12,     # 20\n                               multi_probe_level = 1) # 2\n            search_params = dict(checks=50) # or pass empty dict\n        else:\n             raise ValueError(f\"FLANN parameters not defined for extractor type: {extractor_type}\")\n        return cv2.FlannBasedMatcher(index_params, search_params)\n    else:\n        raise ValueError(f\"Unsupported matcher type: {matcher_type}\")\n\n\ndef match_and_verify(kps1, descs1, kps2, descs2, matcher):\n    \"\"\"Matches features and verifies geometry using Fundamental Matrix RANSAC.\"\"\"\n    if descs1 is None or descs2 is None or len(kps1) < MIN_INLIER_MATCHES_INITIAL or len(kps2) < MIN_INLIER_MATCHES_INITIAL :\n        return None, 0 # Not enough keypoints\n\n    # Perform k-Nearest Neighbor matching\n    matches = matcher.knnMatch(descs1, descs2, k=2)\n\n    # Filter matches using Lowe's ratio test\n    good_matches = []\n    try:\n        for m, n in matches:\n            if m.distance < LOWE_RATIO_TEST_THRESHOLD * n.distance:\n                good_matches.append(m)\n    except ValueError:\n         # Handle cases where k=1 match is returned (e.g., if descs2 has only 1 feature)\n         # print(\"Warning: knnMatch did not return pairs, possibly too few features in one image.\")\n         return None, 0\n\n\n    if len(good_matches) < MIN_INLIER_MATCHES_INITIAL:\n        # print(f\"Insufficient good matches after ratio test: {len(good_matches)}\")\n        return None, 0 # Not enough good matches\n\n    # Extract locations of good matches\n    pts1 = np.float32([kps1[m.queryIdx].pt for m in good_matches]).reshape(-1, 1, 2)\n    pts2 = np.float32([kps2[m.trainIdx].pt for m in good_matches]).reshape(-1, 1, 2)\n\n    # Find Fundamental Matrix using RANSAC\n    try:\n        F, mask = cv2.findFundamentalMat(pts1, pts2, cv2.FM_RANSAC, RANSAC_THRESHOLD, confidence=0.99)\n    except cv2.error as e:\n        # Can happen if points are degenerate (e.g., collinear)\n        # print(f\"cv2.findFundamentalMat error: {e}\")\n        return None, 0\n\n\n    if F is None or mask is None:\n        # print(\"Fundamental matrix estimation failed.\")\n        return None, 0\n\n    # Count inliers\n    num_inliers = int(mask.sum())\n\n    if num_inliers < MIN_INLIER_MATCHES_INITIAL:\n        # print(f\"Insufficient inliers after RANSAC: {num_inliers}\")\n        return None, 0\n\n    # Keep only inlier matches\n    inlier_matches = [m for i, m in enumerate(good_matches) if mask[i][0] == 1]\n\n    return inlier_matches, num_inliers\n\n\n# Example Usage (can be commented out)\n# matcher = get_matcher(MATCHER_TYPE, FEATURE_EXTRACTOR_TYPE)\n# example_img_path2 = next((TRAIN_DIR / 'imc2024_lizard_pond').glob('*.png'), None) # Get another image\n# if example_img_path and example_img_path2 and example_img_path != example_img_path2:\n#     kps1, descs1, _ = extract_features(example_img_path, sift)\n#     kps2, descs2, _ = extract_features(example_img_path2, sift)\n#     if kps1 and kps2:\n#         inlier_matches, num_inliers = match_and_verify(kps1, descs1, kps2, descs2, matcher)\n#         if inlier_matches:\n#             print(f\"Found {num_inliers} inlier matches between {example_img_path.name} and {example_img_path2.name}\")\n#             # Visualize matches\n#             img1_bgr = cv2.imread(str(example_img_path))\n#             img2_bgr = cv2.imread(str(example_img_path2))\n#             img_matches = cv2.drawMatches(img1_bgr, kps1, img2_bgr, kps2, inlier_matches, None,\n#                                           flags=cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)\n#             plt.figure(figsize=(15, 5))\n#             plt.imshow(cv2.cvtColor(img_matches, cv2.COLOR_BGR2RGB))\n#             plt.title(f\"Inlier Matches ({num_inliers})\")\n#             plt.axis('off')\n#             plt.show()\n#         else:\n#             print(f\"No robust match found between {example_img_path.name} and {example_img_path2.name}\")","metadata":{"_uuid":"3ba3559e-bea0-4f93-8d83-f089c0437b44","_cell_guid":"e2f18f5a-686e-4059-b4a1-8b9197265429","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"# ### 5.3. View Graph and Clustering Function <a name=\"Clustering-Function\"></a>\n\ndef build_view_graph(image_ids, features, matcher):\n    \"\"\"Builds a view graph based on pairwise matching.\"\"\"\n    G = nx.Graph()\n    G.add_nodes_from(image_ids)\n    pairwise_matches = {} # Store matches for reuse in SfM\n\n    print(f\"Building view graph for {len(image_ids)} images...\")\n    # Optimized iteration: create pairs first\n    pairs_to_match = []\n    for i in range(len(image_ids)):\n        for j in range(i + 1, len(image_ids)):\n            pairs_to_match.append((image_ids[i], image_ids[j]))\n\n    # Process pairs with progress bar\n    match_results = {}\n    for id1, id2 in tqdm(pairs_to_match, desc=\"Matching pairs\"):\n        # Check runtime\n        if (time.time() - START_TIME) > MAX_RUNTIME_SECONDS:\n            print(\"Warning: Time limit approaching, stopping graph construction early.\")\n            break\n\n        kps1, descs1 = features.get(id1, (None, None))\n        kps2, descs2 = features.get(id2, (None, None))\n\n        if kps1 is None or kps2 is None:\n            continue\n\n        inlier_matches, num_inliers = match_and_verify(kps1, descs1, kps2, descs2, matcher)\n\n        if inlier_matches is not None and num_inliers >= MIN_INLIER_MATCHES_GRAPH:\n             match_results[(id1, id2)] = (inlier_matches, num_inliers)\n             G.add_edge(id1, id2, weight=num_inliers)\n             # Store matches symmetrically for easier lookup during SfM\n             pairwise_matches[(id1, id2)] = inlier_matches\n             pairwise_matches[(id2, id1)] = [(m.trainIdx, m.queryIdx) for m in inlier_matches] # Swap query/train indices\n\n    print(f\"View graph built with {G.number_of_nodes()} nodes and {G.number_of_edges()} edges.\")\n    return G, pairwise_matches\n\n\ndef cluster_images(G, algorithm='ConnectedComponents', min_cluster_size=3):\n    \"\"\"Clusters the view graph and identifies outliers.\"\"\"\n    clusters = []\n    outliers = []\n\n    if G.number_of_nodes() == 0:\n        return [], []\n\n    print(f\"Clustering graph using {algorithm}...\")\n    if algorithm == 'ConnectedComponents':\n        # Use connected components as clusters\n        components = list(nx.connected_components(G))\n        for comp in components:\n            if len(comp) >= min_cluster_size:\n                clusters.append(list(comp))\n            else:\n                outliers.extend(list(comp)) # Add small components to outliers\n    elif algorithm == 'Spectral':\n         # Requires estimating number of clusters (k) - this is tricky\n         # Heuristic: sqrt(nodes) or based on eigenvalues, but can be unstable\n         num_nodes = G.number_of_nodes()\n         if num_nodes < 2 : return [], list(G.nodes())\n\n         # Estimate k (simple heuristic, might need improvement)\n         k_estimated = max(2, min(10, int(np.sqrt(num_nodes / 5)))) # Cap at 10\n         print(f\"Estimating k={k_estimated} for Spectral Clustering\")\n\n         adj_matrix = nx.to_scipy_sparse_array(G, weight='weight', format='csr')\n         sc = SpectralClustering(n_clusters=k_estimated,\n                                 affinity='precomputed',\n                                 assign_labels='kmeans', # or 'discretize'\n                                 random_state=42)\n         try:\n             labels = sc.fit_predict(adj_matrix)\n             # Group nodes by label\n             temp_clusters = defaultdict(list)\n             image_ids = list(G.nodes())\n             for i, label in enumerate(labels):\n                 temp_clusters[label].append(image_ids[i])\n\n             for label, members in temp_clusters.items():\n                 if len(members) >= min_cluster_size:\n                     clusters.append(members)\n                 else:\n                     outliers.extend(members)\n\n         except Exception as e:\n              print(f\"Spectral clustering failed: {e}. Falling back to Connected Components.\")\n              # Fallback\n              components = list(nx.connected_components(G))\n              for comp in components:\n                  if len(comp) >= min_cluster_size:\n                      clusters.append(list(comp))\n                  else:\n                      outliers.extend(list(comp))\n\n    else:\n        raise ValueError(f\"Unsupported clustering algorithm: {algorithm}\")\n\n    # Identify nodes that were in the original list but not in the graph (no edges)\n    isolated_nodes = set(G.nodes()) - set(node for cluster in clusters for node in cluster) - set(outliers)\n    outliers.extend(list(isolated_nodes))\n\n    print(f\"Found {len(clusters)} clusters and {len(outliers)} potential outliers.\")\n    return clusters, list(set(outliers)) # Ensure outliers are unique\n\n\n# Example Usage (can be commented out)\n# if 'kps1' in locals() and kps1 is not None: # Check if features were extracted\n#     example_image_ids = [example_img_path.name, example_img_path2.name]\n#     example_features = {\n#         example_img_path.name: (kps1, descs1),\n#         example_img_path2.name: (kps2, descs2)\n#     }\n#     # Add more dummy features for a slightly larger graph example if needed\n#\n#     G_example, _ = build_view_graph(example_image_ids, example_features, matcher)\n#     clusters_example, outliers_example = cluster_images(G_example, algorithm=CLUSTERING_ALGORITHM, min_cluster_size=MIN_CLUSTER_SIZE)\n#     print(\"Example Clustering Results:\")\n#     print(\"Clusters:\", clusters_example)\n#     print(\"Outliers:\", outliers_example)\n#\n#     # Visualize graph (optional, can be slow/messy for large graphs)\n#     # if G_example.number_of_nodes() > 0 and G_example.number_of_nodes() < 50: # Only plot small graphs\n#     #     plt.figure(figsize=(10, 10))\n#     #     pos = nx.spring_layout(G_example) # Layout algorithm\n#     #     nx.draw(G_example, pos, with_labels=True, node_size=50, font_size=8)\n#     #     plt.title(\"Example View Graph\")\n#     #     plt.show()","metadata":{"_uuid":"f704ddb9-287e-4304-b974-fbb80274806a","_cell_guid":"f3d1e980-f524-4cbb-bf35-c6d6188f4857","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"# ### 5.4. SfM Function (per cluster) <a name=\"SfM-Function\"></a>\n\ndef get_default_camera_matrix(img_width, img_height):\n    \"\"\"Creates a default camera intrinsic matrix K.\"\"\"\n    f = DEFAULT_FOCAL_LENGTH_FACTOR * max(img_width, img_height)\n    cx = img_width / 2.0\n    cy = img_height / 2.0\n    K = np.array([[f, 0, cx],\n                  [0, f, cy],\n                  [0, 0, 1]], dtype=np.float32)\n    return K\n\ndef estimate_poses_for_cluster(cluster_image_ids, features, image_dims, matcher, pairwise_matches):\n    \"\"\"\n    Performs simplified incremental SfM for a single cluster.\n    Returns a dictionary of {image_id: (R, T, K)} for registered images.\n    R is 3x3 rotation, T is 3x1 translation.\n    K is the intrinsic matrix used (can be default).\n    Returns nan poses for unregistered images in the cluster.\n    \"\"\"\n    num_images_in_cluster = len(cluster_image_ids)\n    if num_images_in_cluster < 2:\n        print(f\"Cluster too small ({num_images_in_cluster} images), cannot perform SfM.\")\n        return {img_id: (np.full((3, 3), np.nan), np.full((3, 1), np.nan)) for img_id in cluster_image_ids}\n\n    registered_poses = {} # Stores {image_id: (R, T)}\n    registered_points_3d = {} # Stores {point_idx: (X, Y, Z, observations)} where observations is {image_id: keypoint_idx}\n    point_counter = 0\n    processed_images = set()\n\n    # --- 1. Find Best Initial Pair ---\n    best_pair = None\n    max_inliers = -1\n\n    for i in range(num_images_in_cluster):\n        for j in range(i + 1, num_images_in_cluster):\n             # Check runtime\n             if (time.time() - START_TIME) > MAX_RUNTIME_SECONDS:\n                 print(\"Warning: Time limit approaching during SfM initialization.\")\n                 # Return current state or empty poses\n                 return {img_id: (registered_poses.get(img_id, (np.full((3, 3), np.nan), np.full((3, 1), np.nan)))[0],\n                                  registered_poses.get(img_id, (np.full((3, 3), np.nan), np.full((3, 1), np.nan)))[1])\n                         for img_id in cluster_image_ids}\n\n\n             id1, id2 = cluster_image_ids[i], cluster_image_ids[j]\n             kps1, descs1 = features.get(id1, (None, None))\n             kps2, descs2 = features.get(id2, (None, None))\n\n             if kps1 is None or kps2 is None: continue\n\n             # Reuse matches if available, otherwise compute\n             if (id1, id2) in pairwise_matches:\n                 matches = pairwise_matches[(id1, id2)]\n                 num_inliers = len(matches) # Assuming stored matches are already inliers\n             elif (id2, id1) in pairwise_matches:\n                  matches = pairwise_matches[(id2, id1)] # Use symmetric entry\n                  # Need to swap query/train indices back if stored swapped\n                  matches = [(m[1],m[0]) for m in matches]\n                  num_inliers = len(matches)\n             else:\n                 # This shouldn't happen if graph building stored all matches, but as fallback:\n                 matches, num_inliers = match_and_verify(kps1, descs1, kps2, descs2, matcher)\n                 if matches is None: continue\n\n             if num_inliers > max_inliers and num_inliers >= MIN_INLIER_MATCHES_INITIAL:\n                 max_inliers = num_inliers\n                 best_pair = (id1, id2, matches) # Store the actual matches\n\n    if best_pair is None:\n        print(f\"Could not find a suitable initial pair in cluster with {num_images_in_cluster} images.\")\n        return {img_id: (np.full((3, 3), np.nan), np.full((3, 1), np.nan)) for img_id in cluster_image_ids}\n\n    id1, id2, initial_matches = best_pair\n    print(f\"Initializing SfM with pair ({id1}, {id2}) with {max_inliers} matches.\")\n\n    kps1, _ = features[id1]\n    kps2, _ = features[id2]\n    dims1 = image_dims[id1]\n    dims2 = image_dims[id2]\n\n    # Get default K matrices\n    K1 = get_default_camera_matrix(dims1[0], dims1[1])\n    K2 = get_default_camera_matrix(dims2[0], dims2[1])\n\n    # Extract point coordinates for the initial pair matches\n    pts1 = np.float32([kps1[m.queryIdx].pt for m in initial_matches]).reshape(-1, 1, 2)\n    pts2 = np.float32([kps2[m.trainIdx].pt for m in initial_matches]).reshape(-1, 1, 2)\n\n    # --- 2. Estimate Relative Pose (E -> R, t) ---\n    E, mask_e = cv2.findEssentialMat(pts1, pts2, K1, method=cv2.RANSAC, prob=0.999, threshold=RANSAC_THRESHOLD)\n\n    if E is None or mask_e is None:\n        print(f\"Essential matrix estimation failed for initial pair ({id1}, {id2}).\")\n        return {img_id: (np.full((3, 3), np.nan), np.full((3, 1), np.nan)) for img_id in cluster_image_ids}\n\n    num_inliers_e = int(mask_e.sum())\n    print(f\"Essential matrix inliers: {num_inliers_e}\")\n    if num_inliers_e < MIN_INLIER_MATCHES_INITIAL: # Need enough support for E\n        print(f\"Insufficient inliers ({num_inliers_e}) after Essential matrix estimation.\")\n        return {img_id: (np.full((3, 3), np.nan), np.full((3, 1), np.nan)) for img_id in cluster_image_ids}\n\n\n    # Recover relative pose (R, t) from E\n    # recoverPose returns the Rotation and Translation vectors for the *second* camera\n    # relative to the *first* camera's coordinate system.\n    _, R_rel, t_rel, mask_rp = cv2.recoverPose(E, pts1[mask_e.ravel()==1], pts2[mask_e.ravel()==1], K1) # Use K1 (or K2, assumes same intrinsics for simplicity here)\n\n    if R_rel is None or t_rel is None or mask_rp is None:\n        print(f\"recoverPose failed for initial pair ({id1}, {id2}).\")\n        return {img_id: (np.full((3, 3), np.nan), np.full((3, 1), np.nan)) for img_id in cluster_image_ids}\n\n    # --- 3. Set Initial Poses ---\n    # First camera is at the origin\n    R1 = np.eye(3)\n    T1 = np.zeros((3, 1))\n    registered_poses[id1] = (R1, T1)\n    processed_images.add(id1)\n\n    # Second camera pose is relative to the first\n    R2 = R_rel\n    T2 = t_rel\n    registered_poses[id2] = (R2, T2)\n    processed_images.add(id2)\n\n    # --- 4. Triangulate Initial Points ---\n    # Projection matrices P = K[R|T]\n    P1 = K1 @ np.hstack((R1, T1))\n    P2 = K2 @ np.hstack((R2, T2)) # Use K2 here\n\n    # Get the subset of points that were inliers for recoverPose\n    inlier_indices_rp = np.where(mask_e.ravel() == 1)[0][mask_rp.ravel() > 0] # Indices into original `initial_matches`\n    pts1_rp = np.float32([kps1[initial_matches[i].queryIdx].pt for i in inlier_indices_rp])\n    pts2_rp = np.float32([kps2[initial_matches[i].trainIdx].pt for i in inlier_indices_rp])\n\n    if len(pts1_rp) < MIN_VIEWS_FOR_TRIANGULATION:\n         print(\"Not enough points survived recoverPose for triangulation.\")\n         # Can still proceed maybe, but less robustly. Return failure for now.\n         return {img_id: (np.full((3, 3), np.nan), np.full((3, 1), np.nan)) for img_id in cluster_image_ids}\n\n\n    # Triangulate points\n    points_4d_hom = cv2.triangulatePoints(P1, P2, pts1_rp.T, pts2_rp.T) # Input shapes (2, N)\n    points_3d = points_4d_hom[:3] / points_4d_hom[3] # Convert to non-homogeneous\n    points_3d = points_3d.T # Shape (N, 3)\n\n    # Store 3D points and their observations\n    for i, pt_3d in enumerate(points_3d):\n        original_match_idx = inlier_indices_rp[i]\n        kp_idx1 = initial_matches[original_match_idx].queryIdx\n        kp_idx2 = initial_matches[original_match_idx].trainIdx\n\n        # Basic check for points behind camera (optional, depends on coordinate system)\n        # Cheirality check: point must be in front of both cameras\n        pt_world = pt_3d.reshape(3, 1)\n        pt_cam1 = R1.T @ (pt_world - T1)\n        pt_cam2 = R2.T @ (pt_world - T2)\n        if pt_cam1[2] > 0 and pt_cam2[2] > 0: # Check if z-coordinate is positive\n             registered_points_3d[point_counter] = {\n                 'pos': pt_3d,\n                 'observations': {id1: kp_idx1, id2: kp_idx2}\n             }\n             point_counter += 1\n\n    print(f\"Triangulated {len(registered_points_3d)} initial 3D points.\")\n    if not registered_points_3d:\n         print(\"No valid 3D points triangulated, stopping SfM.\")\n         # Mark initial pair as failed? Or just return no poses? Let's return nan for all.\n         return {img_id: (np.full((3, 3), np.nan), np.full((3, 1), np.nan)) for img_id in cluster_image_ids}\n\n\n    # --- 5. Incremental Registration ---\n    remaining_images = [img_id for img_id in cluster_image_ids if img_id not in processed_images]\n    # Sort remaining images by number of matches to already registered images (heuristic)\n    # This requires efficiently querying matches, pairwise_matches helps here\n    images_to_process_queue = sorted(remaining_images, key=lambda img_id: \\\n                                     sum(len(pairwise_matches.get((img_id, reg_id), []))\n                                         for reg_id in processed_images if (img_id, reg_id) in pairwise_matches),\n                                     reverse=True)\n\n\n    print(f\"Attempting to register {len(images_to_process_queue)} remaining images...\")\n    for img_id_new in tqdm(images_to_process_queue, desc=\"Registering images\"):\n\n        # Check runtime\n        if (time.time() - START_TIME) > MAX_RUNTIME_SECONDS:\n            print(\"Warning: Time limit approaching during SfM registration.\")\n            break # Stop adding new images\n\n\n        kps_new, descs_new = features.get(img_id_new, (None, None))\n        if kps_new is None: continue\n\n        dims_new = image_dims[img_id_new]\n        K_new = get_default_camera_matrix(dims_new[0], dims_new[1])\n\n        # Find 2D-3D correspondences between the new image and existing 3D points\n        points_3d_for_pnp = []\n        points_2d_for_pnp = []\n        kp_indices_new_for_pnp = [] # Store kp index in new image for potential triangulation later\n\n        # Iterate through registered 3D points\n        observed_in_new = [] # Track which 3d points have a match in the new image\n        for pt_idx, pt_data in registered_points_3d.items():\n            # Check if this 3D point was observed by any *already registered* image\n            registered_observers = pt_data['observations'].keys() & processed_images\n            if not registered_observers: continue\n\n            # Find matches between the new image and *one* of the registered observers of this 3D point\n            # Pick one observer (e.g., the first one)\n            observer_id = next(iter(registered_observers))\n            kp_idx_observer = pt_data['observations'][observer_id]\n            kps_observer, descs_observer = features[observer_id]\n\n            # Check if matches exist between new image and this observer\n            current_matches = []\n            if (img_id_new, observer_id) in pairwise_matches:\n                current_matches = pairwise_matches[(img_id_new, observer_id)]\n            elif (observer_id, img_id_new) in pairwise_matches:\n                # Need to swap query/train indices\n                 swapped_matches = pairwise_matches[(observer_id, img_id_new)]\n                 # Format needs care: pairwise_matches stores (kp_idx1, kp_idx2) tuples or Match objects?\n                 # Assuming tuple format: (idx_observer, idx_new)\n                 current_matches = [(m[1], m[0]) for m in swapped_matches] # Now (idx_new, idx_observer)\n\n            # Find if the specific keypoint kp_idx_observer has a match in current_matches\n            found_match = False\n            for kp_idx_new, kp_idx_obs in current_matches:\n                 if kp_idx_obs == kp_idx_observer:\n                     # Found a 2D correspondence for this 3D point\n                     points_3d_for_pnp.append(pt_data['pos'])\n                     points_2d_for_pnp.append(kps_new[kp_idx_new].pt)\n                     kp_indices_new_for_pnp.append(kp_idx_new)\n                     observed_in_new.append(pt_idx)\n                     found_match = True\n                     break # Only need one match per 3D point for PnP list\n\n\n        num_correspondences = len(points_3d_for_pnp)\n        # print(f\"Found {num_correspondences} 2D-3D correspondences for image {img_id_new}\")\n\n        if num_correspondences < MIN_3D_POINTS_FOR_PNP:\n            # print(f\"Skipping {img_id_new}: Not enough ({num_correspondences}) 2D-3D correspondences for PnP.\")\n            continue\n\n        # Estimate pose using PnP + RANSAC\n        try:\n            points_3d_np = np.array(points_3d_for_pnp, dtype=np.float32)\n            points_2d_np = np.array(points_2d_for_pnp, dtype=np.float32)\n\n            # distCoeffs can be assumed None or np.zeros((4,1)) if not estimated/known\n            dist_coeffs = np.zeros((4,1))\n\n            success, rvec, tvec, inliers_pnp = cv2.solvePnPRansac(\n                points_3d_np, points_2d_np, K_new, dist_coeffs, # Use K_new\n                iterationsCount=100,\n                reprojectionError=PNP_RANSAC_THRESHOLD,\n                confidence=PNP_CONFIDENCE,\n                flags=cv2.SOLVEPNP_ITERATIVE # Or other flags like SOLVEPNP_EPNP\n            )\n\n            if success and inliers_pnp is not None and len(inliers_pnp) >= MIN_3D_POINTS_FOR_PNP:\n                R_new, _ = cv2.Rodrigues(rvec) # Convert rotation vector to matrix\n                T_new = tvec\n\n                # Add pose to registered list\n                registered_poses[img_id_new] = (R_new, T_new)\n                processed_images.add(img_id_new)\n                print(f\"Successfully registered image {img_id_new} ({len(inliers_pnp)} PnP inliers).\")\n\n                # --- 6. Optional: Triangulate New Points ---\n                # Find matches between this newly registered image and other registered images\n                # that observe common features, and triangulate those features if not already 3D points.\n                # This makes the reconstruction denser but adds complexity. Skipping for now.\n                # Simplified: Update observations for existing points found via PnP\n                # for i, pnp_idx in enumerate(inliers_pnp.flatten()):\n                #     pt_idx_3d = observed_in_new[pnp_idx] # Find the corresponding 3d point index\n                #     kp_idx_new = kp_indices_new_for_pnp[pnp_idx] # Find the corresponding kp index in the new image\n                #     if pt_idx_3d in registered_points_3d:\n                #          registered_points_3d[pt_idx_3d]['observations'][img_id_new] = kp_idx_new\n\n\n            else:\n                # print(f\"PnP failed or insufficient inliers for {img_id_new}.\")\n                pass # Keep it unregistered\n\n        except cv2.error as e:\n            print(f\"cv2.solvePnPRansac error for {img_id_new}: {e}\")\n            continue\n\n\n    # --- 7. Finalize Poses ---\n    final_poses = {}\n    for img_id in cluster_image_ids:\n        if img_id in registered_poses:\n            final_poses[img_id] = registered_poses[img_id] # (R, T)\n        else:\n            final_poses[img_id] = (np.full((3, 3), np.nan), np.full((3, 1), np.nan))\n\n    print(f\"Finished SfM for cluster. Registered {len(registered_poses)} out of {num_images_in_cluster} images.\")\n    return final_poses","metadata":{"_uuid":"0e0d92e5-7090-4b9a-94e4-66879d3f7937","_cell_guid":"4c9a180c-4dbf-4968-861c-5cd88b049eb6","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"# ### 5.5. Pose Formatting Utility <a name=\"Pose-Format-Utility\"></a>\n\ndef format_pose(R, T):\n    \"\"\"Formats rotation matrix R and translation vector T into the required submission string format.\"\"\"\n    if R is None or T is None or np.isnan(R).any() or np.isnan(T).any():\n        R_str = \";\".join([\"nan\"] * 9)\n        T_str = \";\".join([\"nan\"] * 3)\n        return R_str, T_str\n\n    # Ensure R is 3x3 and T is 3x1 or 1x3\n    R = np.array(R).reshape(3, 3)\n    T = np.array(T).reshape(3,) # Flatten T to 1D array\n\n    R_str = \";\".join(map(str, R.flatten()))\n    T_str = \";\".join(map(str, T))\n    return R_str, T_str\n\n# Example\nR_example = np.eye(3)\nT_example = np.array([1.0, 2.0, 3.0])\nr_str, t_str = format_pose(R_example, T_example)\nprint(f\"Example Formatted R: {r_str}\")\nprint(f\"Example Formatted T: {t_str}\")\n\nr_str_nan, t_str_nan = format_pose(np.full((3,3), np.nan), np.full((3,1), np.nan))\nprint(f\"Example Formatted NaN R: {r_str_nan}\")\nprint(f\"Example Formatted NaN T: {t_str_nan}\")","metadata":{"_uuid":"13f21c8b-c486-40c5-ad7c-5df8b7f0a303","_cell_guid":"85de5c7f-ab25-4731-a74c-853aa00cb468","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## 6. Main Processing Logic <a name=\"Main-Logic\"></a>","metadata":{"_uuid":"361cf9f0-abf9-4191-af96-8d1edcbbe380","_cell_guid":"7dc53dd4-581e-4f07-84f4-08da23ed9775","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"code","source":"# ### 6.1. Processing Loop Structure <a name=\"Loop-Structure\"></a>\n# This section outlines the main loop that iterates through datasets found in the test set,\n# applies the pipeline (feature extraction, matching, clustering, SfM), and collects results.\n\ndef process_dataset(dataset_id, test_image_dir, extractor, matcher):\n    \"\"\"Runs the full pipeline for a single dataset.\"\"\"\n    print(f\"\\n--- Processing Dataset: {dataset_id} ---\")\n    dataset_results = [] # List to store results for this dataset's images\n\n    dataset_path = test_image_dir / dataset_id\n    if not dataset_path.is_dir():\n        print(f\"Error: Dataset directory not found: {dataset_path}\")\n        # Need to handle this - maybe return empty results or based on sample_submission\n        # For now, assume sample_submission dictates images if dir is missing\n        image_ids_in_dataset = sample_submission_df[sample_submission_df['dataset'] == dataset_id]['image'].tolist()\n        print(f\"Warning: Using image list from sample_submission for missing dataset {dataset_id}\")\n        features = {}\n        image_dims = {}\n\n    else:\n         # 1. Extract Features\n         features, image_dims = load_and_extract_features_dataset(dataset_id, test_image_dir, extractor)\n         image_ids_in_dataset = list(features.keys())\n\n         if not features:\n              print(f\"No features extracted for dataset {dataset_id}. Marking all as outliers.\")\n              # Use image list from directory listing if features is empty but dir exists\n              all_images = list(f.name for f in dataset_path.glob('*.png')) + \\\n                           list(f.name for f in dataset_path.glob('*.jpg')) + \\\n                           list(f.name for f in dataset_path.glob('*.jpeg'))\n              for img_id in all_images:\n                   r_str, t_str = format_pose(None, None)\n                   dataset_results.append({\n                       'dataset': dataset_id, 'scene': 'outliers', 'image': img_id,\n                       'rotation_matrix': r_str, 'translation_vector': t_str\n                   })\n              return dataset_results\n\n\n    # Add images found in directory but failed extraction to image_ids_in_dataset\n    all_images_found = list(image_dims.keys())\n    image_ids_set = set(image_ids_in_dataset)\n    for img_id in all_images_found:\n        if img_id not in image_ids_set:\n            image_ids_in_dataset.append(img_id)\n\n\n    # 2. Build View Graph\n    G, pairwise_matches = build_view_graph(image_ids_in_dataset, features, matcher)\n\n    # Check runtime after graph building\n    if (time.time() - START_TIME) > MAX_RUNTIME_SECONDS:\n         print(f\"Warning: Time limit reached after graph building for {dataset_id}. Marking remaining as outliers.\")\n         # Mark all images in this dataset as outliers\n         for img_id in image_ids_in_dataset:\n                r_str, t_str = format_pose(None, None)\n                dataset_results.append({'dataset': dataset_id, 'scene': 'outliers', 'image': img_id,\n                                        'rotation_matrix': r_str, 'translation_vector': t_str})\n         gc.collect()\n         return dataset_results\n\n\n    # 3. Cluster Images\n    clusters, outliers = cluster_images(G, algorithm=CLUSTERING_ALGORITHM, min_cluster_size=MIN_CLUSTER_SIZE)\n\n    # 4. Process Outliers\n    print(f\"Marking {len(outliers)} images as outliers.\")\n    for img_id in outliers:\n        r_str, t_str = format_pose(None, None)\n        dataset_results.append({\n            'dataset': dataset_id, 'scene': 'outliers', 'image': img_id,\n            'rotation_matrix': r_str, 'translation_vector': t_str\n        })\n\n    # 5. Run SfM per Cluster\n    print(f\"Running SfM for {len(clusters)} clusters...\")\n    all_cluster_poses = {} # Combine results from all clusters\n    for i, cluster_nodes in enumerate(clusters):\n        cluster_label = f\"cluster{i+1}\"\n        print(f\"\\nProcessing {cluster_label} ({len(cluster_nodes)} images)...\")\n\n        # Check runtime before starting SfM for a cluster\n        if (time.time() - START_TIME) > MAX_RUNTIME_SECONDS:\n             print(f\"Warning: Time limit reached before processing {cluster_label} for {dataset_id}. Marking as outliers.\")\n             for img_id in cluster_nodes:\n                 r_str, t_str = format_pose(None, None)\n                 dataset_results.append({'dataset': dataset_id, 'scene': 'outliers', 'image': img_id,\n                                         'rotation_matrix': r_str, 'translation_vector': t_str})\n             continue # Skip to next cluster if time allows, or break if needed\n\n\n        # Filter features/dims/matches for the current cluster\n        cluster_features = {img_id: features[img_id] for img_id in cluster_nodes if img_id in features}\n        cluster_dims = {img_id: image_dims[img_id] for img_id in cluster_nodes if img_id in image_dims}\n        # Filter pairwise matches (tricky, need both nodes in cluster)\n        cluster_pairwise_matches = {}\n        for (id1, id2), matches in pairwise_matches.items():\n             if id1 in cluster_nodes and id2 in cluster_nodes:\n                 cluster_pairwise_matches[(id1, id2)] = matches\n\n\n        cluster_poses = estimate_poses_for_cluster(\n            cluster_nodes,\n            cluster_features,\n            cluster_dims,\n            matcher,\n            cluster_pairwise_matches # Pass filtered matches\n        )\n\n        # Add results for this cluster\n        for img_id in cluster_nodes:\n            R, T = cluster_poses.get(img_id, (None, None)) # Get pose, default to None if not found\n            r_str, t_str = format_pose(R, T)\n            dataset_results.append({\n                'dataset': dataset_id, 'scene': cluster_label, 'image': img_id,\n                'rotation_matrix': r_str, 'translation_vector': t_str\n            })\n\n        # Clean up memory\n        del cluster_features, cluster_dims, cluster_poses, cluster_pairwise_matches\n        gc.collect()\n\n\n    print(f\"--- Finished Processing Dataset: {dataset_id} ---\")\n    return dataset_results","metadata":{"_uuid":"50f7d5ca-d676-4408-b9e8-290c425df885","_cell_guid":"cd2ab889-20ce-4b57-8fbe-415495d40ce8","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import cv2\nimport numpy as np\nimport os\nfrom glob import glob\n\ndef load_images_from_dir(directory, extensions=[\".png\", \".jpg\", \".jpeg\"]):\n    \"\"\"\n    Loads images from a directory given a list of possible extensions.\n    Returns a sorted list of images and their paths.\n    \"\"\"\n    image_paths = []\n    for ext in extensions:\n        image_paths.extend(glob(os.path.join(directory, \"*\" + ext)))\n    image_paths = sorted(image_paths)\n    images = []\n    for p in image_paths:\n        img = cv2.imread(p)\n        if img is not None:\n            images.append(img)\n        else:\n            print(f\"Warning: Unable to read image {p}\")\n    return images, image_paths\n\ndef extract_features(images):\n    \"\"\"\n    Extracts ORB keypoints and descriptors from a list of images.\n    \"\"\"\n    # You can tweak nfeatures if needed\n    orb = cv2.ORB_create(nfeatures=1000)\n    keypoints_all = []\n    descriptors_all = []\n    for img in images:\n        kp, des = orb.detectAndCompute(img, None)\n        keypoints_all.append(kp)\n        descriptors_all.append(des)\n    return keypoints_all, descriptors_all\n\ndef match_features(des1, des2):\n    \"\"\"\n    Matches descriptors between two images using BFMatcher with Hamming distance.\n    Returns a sorted list of matches (sorted by distance).\n    \"\"\"\n    bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)\n    if des1 is None or des2 is None:\n        return []\n    matches = bf.match(des1, des2)\n    matches = sorted(matches, key=lambda x: x.distance)\n    return matches\n\ndef process_dataset(dataset_path):\n    \"\"\"\n    Processes a single dataset folder:\n      - Loads images.\n      - Extracts features.\n      - Matches features between consecutive images.\n      - Estimates relative pose (if enough matches are found).\n    \"\"\"\n    print(\"Processing dataset:\", dataset_path)\n    images, image_paths = load_images_from_dir(dataset_path)\n    if len(images) == 0:\n        print(\"No images found in\", dataset_path)\n        return\n\n    print(f\"Found {len(images)} images in {os.path.basename(dataset_path)}.\")\n    \n    # Extract keypoints and descriptors for each image.\n    keypoints_all, descriptors_all = extract_features(images)\n    \n    # Process consecutive image pairs\n    for i in range(len(images) - 1):\n        kp1 = keypoints_all[i]\n        kp2 = keypoints_all[i+1]\n        des1 = descriptors_all[i]\n        des2 = descriptors_all[i+1]\n        matches = match_features(des1, des2)\n        print(f\"Image pair '{os.path.basename(image_paths[i])}' and '{os.path.basename(image_paths[i+1])}': {len(matches)} matches\")\n        \n        # If there are enough matches, attempt pose estimation.\n        if len(matches) >= 8:\n            pts1 = np.float32([kp1[m.queryIdx].pt for m in matches]).reshape(-1, 1, 2)\n            pts2 = np.float32([kp2[m.trainIdx].pt for m in matches]).reshape(-1, 1, 2)\n            \n            # Use approximate focal length and principal point (center of the image)\n            h, w = images[i].shape[:2]\n            focal = 1.0  # Adjust this value if you have calibrated camera data\n            pp = (w / 2, h / 2)\n            \n            E, mask = cv2.findEssentialMat(pts1, pts2, focal=focal, pp=pp, method=cv2.RANSAC, prob=0.999, threshold=1.0)\n            if E is not None and E.shape[0] >= 3:\n                _, R, t, mask_pose = cv2.recoverPose(E, pts1, pts2)\n                print(\"Estimated Pose for pair:\")\n                print(\"Rotation matrix R:\\n\", R)\n                print(\"Translation vector t:\\n\", t)\n            else:\n                print(\"Essential matrix estimation failed.\")\n        else:\n            print(\"Not enough matches for pose estimation.\")\n\ndef main():\n    # Define base directories from Kaggle input\n    base_train = \"/kaggle/input/image-matching-challenge-2025/train\"\n    base_test = \"/kaggle/input/image-matching-challenge-2025/test\"\n    \n    # Process train datasets\n    if os.path.isdir(base_train):\n        train_datasets = [os.path.join(base_train, d) for d in os.listdir(base_train) if os.path.isdir(os.path.join(base_train, d))]\n        print(\"=== Processing Train Datasets ===\")\n        for dataset in train_datasets:\n            process_dataset(dataset)\n    else:\n        print(\"Train directory not found!\")\n    \n    # Process test datasets\n    if os.path.isdir(base_test):\n        test_datasets = [os.path.join(base_test, d) for d in os.listdir(base_test) if os.path.isdir(os.path.join(base_test, d))]\n        print(\"\\n=== Processing Test Datasets ===\")\n        for dataset in test_datasets:\n            process_dataset(dataset)\n    else:\n        print(\"Test directory not found!\")\n\nif __name__ == \"__main__\":\n    main()","metadata":{"_uuid":"f4b5b24d-9c42-40a0-9b25-de244ea4197a","_cell_guid":"95e110fa-77e7-4cde-8b69-69fe79686237","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## 7. Evaluation (Conceptual) <a name=\"Evaluation\"></a>\nThis section provides the *code* for the evaluation metrics as defined by the competition. **It cannot be run directly on the hidden test set** as we don't have the ground truth. However, it can be used locally for validation by comparing results generated on the *training* data against the `train_labels.csv`.\n\n### 7.1. Defining the Evaluation Metrics in Code <a name=\"Metrics-Code\"></a>\n*(Requires ground truth data `gt_df` and predicted data `pred_df`)*\n\n```python\n# Placeholder - Requires gt_df (from train_labels.csv) and pred_df (output of pipeline on train data)\n#\ndef calculate_mAA_score(pred_cluster_poses, gt_scene_poses, thresholds):\n    \"\"\"\n    Calculates the mean Average Accuracy (mAA) for a predicted cluster against a ground truth scene.\n    This requires comparing estimated poses against ground truth poses within given thresholds.\n    NOTE: Pose comparison logic (using thresholds) is complex and needs careful implementation\n          based on the exact metric from the 2024 challenge (likely camera center distance).\n          This is a simplified placeholder for the concept.\n    \"\"\"\n    # Simplified: Assume we just check if an image from the scene was registered (pose is not nan)\n    # A real implementation needs the pose comparison logic from IMC 2024.\n    registered_in_cluster = {img for img, (R, T) in pred_cluster_poses.items() if not np.isnan(R).any()}\n    gt_scene_images = set(gt_scene_poses.keys())\n\n    correctly_registered = registered_in_cluster.intersection(gt_scene_images)\n\n    if not gt_scene_images:\n        return 1.0 # Or 0.0? Define behavior for empty scenes. Assume 1.0 if no images expected.\n\n    # *** Placeholder for actual pose accuracy check ***\n    # accurate_poses = 0\n    # for img_id in correctly_registered:\n    #    pred_R, pred_T = pred_cluster_poses[img_id]\n    #    gt_R, gt_T = gt_scene_poses[img_id]\n    #    # Calculate camera center distance: || gt_C - pred_C || where C = -R.T @ T\n    #    gt_C = -gt_R.T @ gt_T\n    #    pred_C = -pred_R.T @ pred_T\n    #    dist = np.linalg.norm(gt_C - pred_C)\n    #    # Check against multiple thresholds\n    #    # mAA logic involves area under the accuracy-threshold curve\n    #    # THIS IS COMPLEX and needs the exact 2024 code/logic.\n\n    # Using simplified registration recall for now:\n    recall = len(correctly_registered) / len(gt_scene_images)\n    return recall # This is NOT the real mAA, just a placeholder concept.\n\ndef calculate_clustering_score(pred_cluster_images, gt_scene_images):\n    \"\"\"Calculates the Clustering Score = |S intersect C| / |C|\"\"\"\n    intersection = len(set(pred_cluster_images).intersection(set(gt_scene_images)))\n    cluster_size = len(pred_cluster_images)\n    if cluster_size == 0:\n        return 0.0 # Avoid division by zero\n    return intersection / cluster_size\n\ndef evaluate_dataset(pred_df_dataset, gt_df_dataset, thresholds_df_dataset):\n    \"\"\"Evaluates a single dataset based on competition metrics.\"\"\"\n\n    # --- Prepare Data ---\n    # 1. Group predictions by cluster\n    pred_clusters = pred_df_dataset[pred_df_dataset['scene'] != 'outliers'].groupby('scene')['image'].apply(list).to_dict()\n    # Store predicted poses (needs parsing from string) - Simplified: store image names only for clustering score\n    # pred_poses = {} # {cluster_label: {image_id: (R, T)}} - Needs parsing R, T strings\n\n    # 2. Group ground truth by scene\n    gt_scenes = gt_df_dataset[gt_df_dataset['scene'] != 'outliers'].groupby('scene')['image'].apply(list).to_dict()\n    # gt_poses = {} # {scene_label: {image_id: (R, T)}} - Needs parsing R, T strings\n\n    # --- Greedy Cluster-Scene Assignment ---\n    scene_to_cluster_map = {} # {gt_scene: assigned_pred_cluster}\n    assigned_clusters = set()\n\n    # Iterate through ground truth scenes\n    for gt_scene_label, gt_scene_images in gt_scenes.items():\n        best_mAA = -1.0\n        best_clustering = -1.0\n        best_cluster_label = None\n\n        # Get GT poses and thresholds for this scene (needed for real mAA)\n        # gt_scene_poses_map = ... parse R,T for gt_scene_images ...\n        # thresholds = ... parse thresholds_df_dataset for gt_scene_label ...\n\n        # Compare with each predicted cluster\n        for pred_cluster_label, pred_cluster_images in pred_clusters.items():\n            # Get predicted poses for this cluster (needed for real mAA)\n            # pred_cluster_poses_map = ... parse R,T for pred_cluster_images ...\n\n            # *** Replace with actual mAA calculation ***\n            # current_mAA = calculate_mAA_score(pred_cluster_poses_map, gt_scene_poses_map, thresholds)\n            # Simplified using registration recall:\n            registered_in_cluster = set(pred_df_dataset[(pred_df_dataset['scene'] == pred_cluster_label) & (pred_df_dataset['rotation_matrix'] != 'nan;nan;nan;nan;nan;nan;nan;nan;nan')]['image'])\n            correctly_registered = registered_in_cluster.intersection(set(gt_scene_images))\n            current_mAA = len(correctly_registered) / len(gt_scene_images) if gt_scene_images else 1.0 # Placeholder mAA\n\n            current_clustering = calculate_clustering_score(pred_cluster_images, gt_scene_images)\n\n            if current_mAA > best_mAA:\n                best_mAA = current_mAA\n                best_clustering = current_clustering\n                best_cluster_label = pred_cluster_label\n            elif current_mAA == best_mAA and current_clustering > best_clustering:\n                # Tie-breaking using clustering score\n                best_clustering = current_clustering\n                best_cluster_label = pred_cluster_label\n\n        if best_cluster_label is not None:\n             # Assign scene to best cluster (can assign multiple scenes to one cluster)\n             scene_to_cluster_map[gt_scene_label] = best_cluster_label\n             assigned_clusters.add(best_cluster_label)\n             # print(f\"Assigned GT Scene '{gt_scene_label}' to Pred Cluster '{best_cluster_label}' (mAA={best_mAA:.3f}, Clust={best_clustering:.3f})\")\n\n\n    # --- Calculate Aggregated Scores ---\n    total_intersection = 0\n    total_cluster_size = 0\n    total_mAA_numerator = 0 # Weighted sum for mAA average\n    total_gt_scene_size = 0 # Sum of sizes of scenes that got assigned\n\n    processed_clusters_for_scoring = set() # Ensure each *assigned* cluster contributes only once to denominator\n\n    for gt_scene_label, assigned_cluster_label in scene_to_cluster_map.items():\n        gt_scene_images = set(gt_scenes[gt_scene_label])\n        pred_cluster_images = set(pred_clusters[assigned_cluster_label])\n\n        intersection = len(gt_scene_images.intersection(pred_cluster_images))\n        total_intersection += intersection\n\n        # Accumulate cluster size only once per assigned cluster\n        if assigned_cluster_label not in processed_clusters_for_scoring:\n            total_cluster_size += len(pred_cluster_images)\n            processed_clusters_for_scoring.add(assigned_cluster_label)\n\n        # Accumulate for mAA (using placeholder recall)\n        registered_in_assigned_cluster = set(pred_df_dataset[(pred_df_dataset['scene'] == assigned_cluster_label) & (pred_df_dataset['rotation_matrix'] != 'nan;nan;nan;nan;nan;nan;nan;nan;nan')]['image'])\n        correctly_registered = len(registered_in_assigned_cluster.intersection(gt_scene_images))\n        total_mAA_numerator += correctly_registered # Simplified: sum of correctly registered images\n        total_gt_scene_size += len(gt_scene_images)\n\n\n    final_clustering_score = total_intersection / total_cluster_size if total_cluster_size > 0 else 0.0\n    # final_mAA = total_mAA_numerator / total_gt_scene_size if total_gt_scene_size > 0 else 0.0 # This is average recall, NOT mAA\n    # *** Actual mAA calculation is more complex, likely averaging per-scene mAA values ***\n    final_mAA = final_clustering_score # TEMP: Using clustering score as proxy for mAA until real metric is implemented\n\n    # --- Combined Score (Harmonic Mean) ---\n    if final_mAA + final_clustering_score == 0:\n        combined_score = 0.0\n    else:\n        combined_score = 2 * (final_mAA * final_clustering_score) / (final_mAA + final_clustering_score)\n\n    return combined_score, final_mAA, final_clustering_score\n```\n\n### 7.2. Applying Evaluation (Example on Train Data) <a name=\"Applying-Evaluation\"></a>\n```python\n# --- Example: Evaluate pipeline output on training data ---\n# Assumes you have run the pipeline on the 'train' directory\n# and produced a results DataFrame 'train_pred_df' similar to submission_df\n\nif not train_labels_df.empty and 'train_pred_df' in locals(): # Check if data exists\n    overall_scores = []\n    train_datasets_eval = train_pred_df['dataset'].unique()\n\n    for dataset_id in train_datasets_eval:\n        print(f\"\\n--- Evaluating Dataset: {dataset_id} ---\")\n        pred_data = train_pred_df[train_pred_df['dataset'] == dataset_id]\n        gt_data = train_labels_df[train_labels_df['dataset'] == dataset_id]\n        threshold_data = train_thresholds_df[train_thresholds_df['dataset'] == dataset_id] # Needed for real mAA\n\n        if gt_data.empty:\n            print(f\"Warning: No ground truth found for dataset {dataset_id}. Skipping evaluation.\")\n            continue\n\n        # NOTE: Using placeholder evaluation logic (relies heavily on clustering score)\n        score, mAA, clust_score = evaluate_dataset(pred_data, gt_data, threshold_data)\n        overall_scores.append(score)\n        print(f\"Dataset {dataset_id}: Combined Score = {score:.4f} (mAA={mAA:.4f}, Clustering={clust_score:.4f})\")\n\n    if overall_scores:\n        final_avg_score = np.mean(overall_scores)\n        print(f\"\\n--- Overall Average Combined Score (Validation): {final_avg_score:.4f} ---\")\n    else:\n        print(\"\\nNo datasets evaluated.\")\nelse:\n     print(\"\\nSkipping evaluation example: Train labels or predictions not available.\")\n     print(\"To run evaluation, first run the main pipeline on the training data directory.\")\n\n```","metadata":{"_uuid":"07fa8702-05c9-466b-8301-d366e32dff41","_cell_guid":"b0076cd3-edae-408d-bc28-f6f8300df7a9","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"markdown","source":"## 8. Submission Generation <a name=\"Submission\"></a>","metadata":{"_uuid":"5a0b81d5-00b8-4787-8c68-104f06a68dd1","_cell_guid":"b3cc6783-4ed2-44b1-8c18-ea7ac6e9e642","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"code","source":"# ### 8.1. Generating the Final `submission.csv` <a name=\"Generating-Submission\"></a>\n\nif 'submission_df' in locals() and not submission_df.empty:\n    # Ensure columns are in the correct order\n    submission_df = submission_df[['dataset', 'scene', 'image', 'rotation_matrix', 'translation_vector']]\n\n    # Ensure dtypes are suitable (object/string generally fine for CSV)\n    submission_df = submission_df.astype(str) # Force string type to avoid issues with NaN representation etc.\n    # Replace python 'nan' strings potentially created with the required format 'nan'\n    submission_df.replace('nan;nan;nan;nan;nan;nan;nan;nan;nan', 'nan', inplace=True, regex=False) # Simplification, format_pose should handle this\n    submission_df.replace('nan;nan;nan', 'nan', inplace=True, regex=False)\n\n\n    submission_path = OUTPUT_DIR / 'submission.csv'\n    submission_df.to_csv(submission_path, index=False)\n\n    print(f\"\\nSubmission file saved to: {submission_path}\")\n    print(f\"Number of rows in submission file: {len(submission_df)}\")\n\n    # Display final submission snippet again\n    print(\"\\n--- Final Submission Snippet ---\")\n    print(submission_df.head())\n\n    # Check if it matches sample submission length exactly (if sample exists)\n    if not sample_submission_df.empty:\n         if len(submission_df) == len(sample_submission_df):\n              print(\"\\nSubmission row count matches sample submission.\")\n         else:\n              print(f\"\\nWarning: Final submission row count ({len(submission_df)}) differs from sample ({len(sample_submission_df)}).\")\n\nelse:\n    print(\"\\nNo submission data generated. Cannot save file.\")\n    # Create a dummy submission based on sample if needed for kernel to pass\n    if not sample_submission_df.empty and IS_KAGGLE:\n         print(\"Creating dummy submission from sample file to allow kernel completion.\")\n         sample_submission_df['scene'] = 'outliers' # Assign all to outliers\n         nan_pose_r, nan_pose_t = format_pose(None, None)\n         sample_submission_df['rotation_matrix'] = nan_pose_r\n         sample_submission_df['translation_vector'] = nan_pose_t\n         submission_path = OUTPUT_DIR / 'submission.csv'\n         sample_submission_df.to_csv(submission_path, index=False)\n         print(f\"Dummy submission file saved to: {submission_path}\")","metadata":{"_uuid":"9b8ee454-06c0-47ae-9f81-ec82f8f4a1d6","_cell_guid":"65862fcb-afd7-465d-92d2-adc0f9a69d1f","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## 9. Conclusion and Future Work <a name=\"Conclusion\"></a>\n\n### 9.1. Summary <a name=\"Summary\"></a>\nThis notebook presented a pipeline for the Image Matching Challenge 2025. It addresses both the image clustering and 3D reconstruction tasks using a combination of classical computer vision techniques:\n*   SIFT feature extraction provides robustness.\n*   FLANN matching with Lowe's ratio test and RANSAC-based Fundamental Matrix estimation ensures geometrically consistent pairwise matches.\n*   View graph construction followed by connected components clustering groups images into potential scenes while identifying outliers.\n*   A simplified incremental Structure from Motion pipeline using Essential Matrix decomposition and Perspective-n-Point (PnP) registration estimates camera poses for images within each cluster.\n\n### 9.2. Limitations <a name=\"Limitations\"></a>\n*   **SfM Robustness:** The implemented SfM is simplified. It lacks bundle adjustment, robust handling of drift, and advanced outlier rejection during PnP, potentially leading to inaccurate poses or registration failures.\n*   **Clustering Accuracy:** Connected components clustering might incorrectly merge distinct scenes if they are weakly linked by spurious matches, or split scenes if matches are sparse. More advanced clustering might be needed.\n*   **Camera Intrinsics:** Using a default camera matrix **K** for Essential Matrix and PnP calculations is an approximation. Estimating intrinsics or using methods less sensitive to them could improve accuracy.\n*   **Parameter Tuning:** Performance heavily depends on parameters like matching thresholds, RANSAC thresholds, and minimum cluster size, which were set heuristically.\n*   **Runtime:** The pairwise matching and SfM steps can be computationally intensive, potentially hitting Kaggle's runtime limits on larger datasets. The code includes basic time checks but could be further optimized.\n*   **Evaluation Metric:** The provided evaluation code uses placeholder logic for the mAA score, as the exact 2024 pose accuracy metric implementation is complex.\n\n### 9.3. Potential Improvements <a name=\"Improvements\"></a>\n*   **Advanced Features/Matchers:** Experiment with learned features (e.g., DISK, ALIKED, SuperPoint) and matchers (e.g., SuperGlue, LightGlue), which often show superior performance, especially if provided as offline Kaggle datasets.\n*   **Robust SfM:** Integrate a more robust SfM library (e.g., parts of PyCOLMAP if feasible within constraints) or implement techniques like pose graph optimization to refine poses globally after initial estimation.\n*   **Clustering Enhancements:** Explore more sophisticated graph clustering algorithms (Louvain, spectral clustering with better k-estimation) or density-based methods. Implement specific outlier rejection strategies beyond small cluster size.\n*   **Camera Self-Calibration:** Attempt to estimate camera intrinsics during the SfM process.\n*   **Hierarchical Clustering:** Use a hierarchical approach, first finding strong pairs, then growing clusters more carefully.\n*   **Code Optimization:** Optimize feature matching (e.g., using approximate nearest neighbor libraries like FAISS if allowed), parallelize independent tasks where possible.\n*   **Ensembling:** Combine results from different feature types, matching parameters, or clustering algorithms.\n*   **Validation Strategy:** Implement a robust local cross-validation strategy using the training data to tune parameters effectively before submission.","metadata":{"_uuid":"25503d6b-bb01-41be-b124-f3d3aa9b0f24","_cell_guid":"ddbcbeb0-d2a4-4e1b-924c-21b90c85ee45","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"markdown","source":"## 10. References <a name=\"References\"></a>\n\n*   **OpenCV Documentation:** [https://docs.opencv.org/](https://docs.opencv.org/)\n*   **Lowe, D. G. (2004).** Distinctive Image Features from Scale-Invariant Keypoints. *International Journal of Computer Vision*, 60(2), 91-110. (SIFT)\n*   **Fischler, M. A., & Bolles, R. C. (1981).** Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. *Communications of the ACM*, 24(6), 381-395. (RANSAC)\n*   **Hartley, R., & Zisserman, A. (2003).** *Multiple View Geometry in Computer Vision*. Cambridge University Press. (Fundamental/Essential Matrix, PnP, SfM)\n*   **NetworkX Library:** [https://networkx.org/](https://networkx.org/)\n*   **Image Matching Challenge 2025:** [https://kaggle.com/competitions/image-matching-challenge-2025](https://kaggle.com/competitions/image-matching-challenge-2025) (Competition Page & Citation)\n*   **Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008).** Fast unfolding of communities in large networks. *Journal of Statistical Mechanics: Theory and Experiment*, 2008(10), P10008. (Louvain Clustering Algorithm)\n*   **Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002).** On spectral clustering: Analysis and an algorithm. *Advances in neural information processing systems*, 14. (Spectral Clustering)","metadata":{"_uuid":"025cbf59-090d-43b5-8cf5-5fdbc2df459f","_cell_guid":"ac69d9c3-4e72-46c3-be30-dec83fdf315d","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"code","source":"print(\"Notebook execution finished.\")\nfinal_time = time.time()\nprint(f\"Total runtime: {(final_time - START_TIME) / 60:.2f} minutes.\")","metadata":{"_uuid":"8f7e45b6-1648-494e-8872-c0ff88c67195","_cell_guid":"1c2c47fe-8e24-418e-9961-80e1b3fe9b42","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}},"outputs":[],"execution_count":null}]}