{"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":"none","dataSources":[{"sourceId":91498,"databundleVersionId":11655853,"sourceType":"competition"}],"dockerImageVersionId":30918,"isInternetEnabled":false,"language":"python","sourceType":"notebook","isGpuEnabled":false}},"nbformat_minor":4,"nbformat":4,"cells":[{"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:47.759962Z","iopub.execute_input":"2025-04-16T19:42:47.760279Z","iopub.status.idle":"2025-04-16T19:42:53.248136Z","shell.execute_reply.started":"2025-04-16T19:42:47.760252Z","shell.execute_reply":"2025-04-16T19:42:53.246807Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:53.249816Z","iopub.execute_input":"2025-04-16T19:42:53.250786Z","iopub.status.idle":"2025-04-16T19:42:53.261259Z","shell.execute_reply.started":"2025-04-16T19:42:53.250748Z","shell.execute_reply":"2025-04-16T19:42:53.260094Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:53.263675Z","iopub.execute_input":"2025-04-16T19:42:53.264034Z","iopub.status.idle":"2025-04-16T19:42:53.433367Z","shell.execute_reply.started":"2025-04-16T19:42:53.264006Z","shell.execute_reply":"2025-04-16T19:42:53.432069Z"}},"outputs":[],"execution_count":null},{"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:53.435057Z","iopub.execute_input":"2025-04-16T19:42:53.435389Z","iopub.status.idle":"2025-04-16T19:42:53.450785Z","shell.execute_reply.started":"2025-04-16T19:42:53.435360Z","shell.execute_reply":"2025-04-16T19:42:53.449696Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:53.451693Z","iopub.execute_input":"2025-04-16T19:42:53.452070Z","iopub.status.idle":"2025-04-16T19:42:54.678493Z","shell.execute_reply.started":"2025-04-16T19:42:53.452036Z","shell.execute_reply":"2025-04-16T19:42:54.677175Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:54.680399Z","iopub.execute_input":"2025-04-16T19:42:54.681056Z","iopub.status.idle":"2025-04-16T19:42:56.730995Z","shell.execute_reply.started":"2025-04-16T19:42:54.680997Z","shell.execute_reply":"2025-04-16T19:42:56.729334Z"}},"outputs":[],"execution_count":null},{"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:56.732266Z","iopub.execute_input":"2025-04-16T19:42:56.732649Z","iopub.status.idle":"2025-04-16T19:42:56.745992Z","shell.execute_reply.started":"2025-04-16T19:42:56.732611Z","shell.execute_reply":"2025-04-16T19:42:56.744590Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:56.748683Z","iopub.execute_input":"2025-04-16T19:42:56.749009Z","iopub.status.idle":"2025-04-16T19:42:56.791350Z","shell.execute_reply.started":"2025-04-16T19:42:56.748982Z","shell.execute_reply":"2025-04-16T19:42:56.790119Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:56.792964Z","iopub.execute_input":"2025-04-16T19:42:56.793366Z","iopub.status.idle":"2025-04-16T19:42:56.819529Z","shell.execute_reply.started":"2025-04-16T19:42:56.793336Z","shell.execute_reply":"2025-04-16T19:42:56.818373Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:56.820646Z","iopub.execute_input":"2025-04-16T19:42:56.820977Z","iopub.status.idle":"2025-04-16T19:42:56.862075Z","shell.execute_reply.started":"2025-04-16T19:42:56.820946Z","shell.execute_reply":"2025-04-16T19:42:56.860616Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:56.863263Z","iopub.execute_input":"2025-04-16T19:42:56.864307Z","iopub.status.idle":"2025-04-16T19:42:56.893088Z","shell.execute_reply.started":"2025-04-16T19:42:56.864088Z","shell.execute_reply":"2025-04-16T19:42:56.891481Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:56.894378Z","iopub.execute_input":"2025-04-16T19:42:56.894760Z","iopub.status.idle":"2025-04-16T19:42:56.917444Z","shell.execute_reply.started":"2025-04-16T19:42:56.894729Z","shell.execute_reply":"2025-04-16T19:42:56.915975Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:42:56.918789Z","iopub.execute_input":"2025-04-16T19:42:56.919189Z","iopub.status.idle":"2025-04-16T19:58:41.048589Z","shell.execute_reply.started":"2025-04-16T19:42:56.919161Z","shell.execute_reply":"2025-04-16T19:58:41.047137Z"}},"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},"execution":{"iopub.status.busy":"2025-04-16T19:58:41.050625Z","iopub.execute_input":"2025-04-16T19:58:41.051039Z","iopub.status.idle":"2025-04-16T19:58:41.089776Z","shell.execute_reply.started":"2025-04-16T19:58:41.050999Z","shell.execute_reply":"2025-04-16T19:58:41.087619Z"}},"outputs":[],"execution_count":null},{"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},"execution":{"iopub.status.busy":"2025-04-16T19:58:41.092615Z","iopub.execute_input":"2025-04-16T19:58:41.093178Z","iopub.status.idle":"2025-04-16T19:58:41.106105Z","shell.execute_reply.started":"2025-04-16T19:58:41.093123Z","shell.execute_reply":"2025-04-16T19:58:41.104645Z"}},"outputs":[],"execution_count":null}]}