Colmap PartitionCluster 分塊聚類的核心部分

這部分代碼讀完感覺作者寫的很冷靜，很缜密

整個代碼是用來 一個Image的集合進行分塊的。 這些分出來的塊可以用于并行的重建，聽起來是挺不錯的呃，下面我們來看看具體的實作：

void SceneClustering::PartitionCluster(
    const std::vector<std::pair<int, int>>& edges,
    const std::vector<int>& weights, Cluster* cluster) {
  CHECK_EQ(edges.size(), weights.size());

  // If the cluster is small enough, we return from the recursive clustering.
  //這裡應該是用在下面遞歸特判的，避免炸
  if (edges.size() == 0 ||
      cluster->image_ids.size() <=
          static_cast<size_t>(options_.leaf_max_num_images)) {
    return;
  }

  // Partition the cluster using a normalized cut on the scene graph.
  // 此處是核心
  // 圖的最小割，頂點是一個個圖檔，邊權重是圖檔對之間inliers的數量
  // 應該是調用metis的圖割，把圖切成兩部分（為什麼是兩部分因為我們要遞歸使用
  // 這個方法， 是以類似于構造一個二叉樹，左右孩子不斷向下延伸）
  // 傳回的label就是每個節點的組好，要麼是1，要麼是2
  const auto labels =
      ComputeNormalizedMinGraphCut(edges, weights, options_.branching);

  // Assign the images to the clustered child clusters.
  // 對每個圖檔，都加入到對應的cluster中，要麼是第一個cluster，要麼是第二個
  cluster->child_clusters.resize(options_.branching);
  for (const auto image_id : cluster->image_ids) {
    if (labels.count(image_id)) {
      auto& child_cluster = cluster->child_clusters.at(labels.at(image_id));
      child_cluster.image_ids.push_back(image_id);
    }
  }

  // Collect the edges based on whether they are inter or intra child clusters.
  std::vector<std::vector<std::pair<int, int>>> child_edges(options_.branching);
  std::vector<std::vector<int>> child_weights(options_.branching);
  std::vector<std::vector<std::pair<std::pair<int, int>, int>>>
      overlapping_edges(options_.branching);
  for (size_t i = 0; i < edges.size(); ++i) {
    const int label1 = labels.at(edges[i].first);
    const int label2 = labels.at(edges[i].second);
    // 如果說這個邊的兩個圖檔是同一個 label，那麼這對圖檔（這個邊）就可以加入到
    // 這個cluster中了
    if (label1 == label2) {
      child_edges.at(label1).push_back(edges[i]);
      child_weights.at(label1).push_back(weights[i]);
    } else {
    // 如果邊上的兩個圖檔是屬于不同的label，那麼就拆開加入到不同的cluster中
    // 
      overlapping_edges.at(label1).emplace_back(edges[i], weights[i]);
      overlapping_edges.at(label2).emplace_back(edges[i], weights[i]);
    }
  }

  // Recursively partition all the child clusters.
  for (int i = 0; i < options_.branching; ++i) {
  // 其實這裡的遞歸是關鍵，
  // 這裡直接把那些 image 的兩個圖是同一個label的image_pair 保留，作為這個cluster的内部邊，然後可以很順利的進行遞歸操作。
  // 
    PartitionCluster(child_edges[i], child_weights[i],
                     &cluster->child_clusters[i]);
  }

  if (options_.image_overlap > 0) {
    for (int i = 0; i < options_.branching; ++i) {
      // Sort the overlapping edges by the number of inlier matches, such
      // that we add overlapping images with many common observations.
      // 将跨兩個cluster的邊按照内點數量從大到小進行排序
      std::sort(overlapping_edges[i].begin(), overlapping_edges[i].end(),
                [](const std::pair<std::pair<int, int>, int>& edge1,
                   const std::pair<std::pair<int, int>, int>& edge2) {
                  return edge1.second > edge2.second;
                });

      // Select overlapping edges at random and add image to cluster.
      // 把跨cluster的邊上的image id配置設定到對應的 子cluster 中
      std::set<int> overlapping_image_ids;
      for (const auto& edge : overlapping_edges[i]) {
        if (labels.at(edge.first.first) == i) {
          overlapping_image_ids.insert(edge.first.second);
        } else {
          overlapping_image_ids.insert(edge.first.first);
        }
        if (overlapping_image_ids.size() >=
            static_cast<size_t>(options_.image_overlap)) {
          break;
        }
      }

      // Recursively append the overlapping images to cluster and its children.
      // 這裡是定義一個： 遞歸向 cluster 及其 孩子節點 中插入overlapping
      // id 的函數
      std::function<void(Cluster*)> InsertOverlappingImageIds =
          [&](Cluster* cluster) {
            cluster->image_ids.insert(cluster->image_ids.end(),
                                      overlapping_image_ids.begin(),
                                      overlapping_image_ids.end());
            for (auto& child_cluster : cluster->child_clusters) {
              InsertOverlappingImageIds(&child_cluster);
            }
          };
      //調用上面定義的方法，遞歸插入
      InsertOverlappingImageIds(&cluster->child_clusters[i]);
    }
  }
}