原文地址

This CGAL component implements two algorithms for shape detection:

  • the Efficient RANSAC (RANdom SAmple Consensus) method, contributed by Schnabel et al. [2];
  • the Region Growing method, contributed by Lafarge and Mallet [1].

这个CGAL组件实现了两种形状检测算法：

  1. 高效的RANSAC方法
  2. 区域增长算法

高效的RANSAC

From an unstructured point set with unoriented normals, this algorithm detects a set of shapes (see Figure Figure 79.1). Five types of primitive shapes are provided by this package: plane, sphere, cylinder, cone, and torus. Other primitive shapes can be easily added by the user (see Section Custom Shapes).

从具有无向法线的非结构化点集，该算法检测一组形状（见图 79.1）。这个包提供了五种类型的原始形状：平面、球体、圆柱体、圆锥体和圆环体。用户可以轻松添加其他原始形状（请参阅自定义形状部分）。

形状检测 - 图1

Figure 79.1 Input and output of the Efficient RANSAC method. (a) Input point set. (b) Point set depicted with one color per detected shape.

图79.1 高效RANSAC方法的输入输出 (a)输入的点集；(b)每个检测到的形状用一种颜色表示，以此进行区分

This method takes as input a point set with unoriented normals and provides as output a set of detected shapes with associated input points. The output of the algorithm is a set of detected shapes with assigned points and all remaining points not covered by these shapes. Each input point can be assigned to at most one detected shape.

输入：

  1. 法线未定向的点集
  2. 添加需要检测的形状（用户可自定义形状）

输出：

  1. 一组检测到的形状，一个形状一个颜色
  2. 未覆盖的剩余点

说明：

  1. 每个输入点最多可分配给一个检测形状

自定义形状

Other shape types can be detected by implementing a shape class derived from the class Shape_detection::Shape_base and registering it to the shape detection factory of the Efficient RANSAC object. This class must provide the following functions: construct a shape from a small set of given points, compute the squared distance from a query point to the shape, and compute the normal deviation between a query point with the normal and the normal to the shape at the closest point from the query. The used shape parameters are added as members to the derived class.

用户可自定义形状，步骤：

  1. 继承Shape_detection::Shape_base
  2. 并将其注册到Efficient RANSAC对象的形状检测工厂

用户自定义形状类需要满足以下条件：

  1. 用一组给定点构造出这个形状
  2. 计算从查询点到形状的平方距离
  3. 计算查询点与法线之间的法线偏差
  4. 查询最近点到该形状的法线

Note that the RANSAC approach is efficient for shapes that are uniquely defined by a small number of points, denoted by the number of required samples. The algorithm aims at detecting the largest shape via many random samples, and the combinatorial complexity of possible samples increases rapidly with the number of required samples.

请注意，要保证一小组点只能对应出一种形状，如此，RANSAC才是有效的。该算法旨在通过许多随机样本来检测最大的形状，并且可能样本的组合复杂度随着所需样本数量的增加而迅速增加。

More specifically, the functions to be implemented are defined in the base class Shape_detection::Shape_base:

The last two functions are used to determine the number of inlier points to the shape. They compute respectively the squared distance from a set of points to the shape, and the dot product between the point normals and the normals at the shape for the closest points on the shape.

具体来说，要重载Shape_detection::Shape_base中的以下方法：

  • [Shape_detection::Shape_base::minimum_sample_size()](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#afba75428e79da4371347314858440a41) const 返回所需样本的最小数量
  • [Shape_detection::Shape_base::create_shape](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#a4f4e29f440b04dccebd9597f98bb3b2e)(const std::vector<size_t>& indices) 通过一组下标来指定随机生成的样本。
    • 使用[Shape_detection::Shape_base::point](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#a541fb82f5936525b01dc690ae3317fa4)(std::size_t index)和[Shape_detection::Shape_base::normal](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#afa97971c02d019424edf02f87911c542)(std::size_t index)来检索点和法线。根据其他形状类型，所提供的样本数量可能大于上述所需最小样本数量。如果所提供的样本不足以定义一个独特的形状，例如在退化的情况下，该形状被认为是无效的
  • [Shape_detection::Shape_base::squared_distance](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#ab04f03619adb9bee6112f074ba2508ff)(const Point& point) const 此方法计算，查询点到形状的平方距离，它用于遍历分层的空间数据结构。
  • 最后两个函数用于确定形状的内点数
    • [Shape_detection::Shape_base::squared_distance](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#ab04f03619adb9bee6112f074ba2508ff)(std::vector<FT>& distances, const std::vector<size_t>& indices) 计算一组点到形状的平方距离
    • [Shape_detection::Shape_base::cos_to_normal](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#a07f487f782693af3fa42a29f9ad14a97)(const std::vector<size_t>& indices, std::vector<FT>& angles) const 点法线和形状上最近点的法线之间的点积

The access to the actual point and normal data is carried out via Shape_detection::Shape_base::point(std::size_t index) and Shape_detection::Shape_base::normal(std::size_t index) (see the example below). The resulting squared distance/dot product is stored in the vector provided as the first argument.

对实际点和法线数量的访问是通过[Shape_detection::Shape_base::point](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#a541fb82f5936525b01dc690ae3317fa4)(std::size_t index)和[Shape_detection::Shape_base::normal](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#afa97971c02d019424edf02f87911c542)(std::size_t index)进行的。平方距离/点积的结果存储在一个向量中，这个向量当做第一个参数返回。

By default, the connected component is detected via the neighbor graph as mentioned above. However, for shapes that admit a faster approach to detect a connected component, the user can provide his/her own implementation to extract the connected component via:

  • Shape_detection::Shape_base::connected_component(std::vector& indices, FT cluster_epsilon): The indices of all supporting points are stored in the vector indices. All points that do not belong to the largest cluster of points are removed from the vector indices.

默认情况下，连接组件是通过上面提到的邻接图来检测的。当然用户也可提供自定义的方式，来提取连接组件

  • [Shape_detection::Shape_base::connected_component](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#a48186a53453c9a0c11cfebc8dcd399eb)(std::vector<std::size_t>& indices, FT cluster_epsilon)：所有支持点的索引都存储在indices中。所有不属于最大点簇的点都从indices中移除

Another optional method can be implemented to provide a helper function providing the shape parameters written to a string:

  • Shape_detection::Shape_base::info(): This function returns a string suitable for printing the shape parameters into a log/console. The default solution provides an empty string.

另一个可选方法，用来提供一个写入字符串的形状参数：

  • [Shape_detection::Shape_base::info](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Shape__base.html#ac1bbd0a749fbc118fe266039fcb88b09)(): 此函数返回一个字符串，用于将形状参数打印到日志/控制台。默认是一个空的字符串

The property maps are used to map the indices to the corresponding points and normals.

属性映射用于将索引对应到相应的点和法线上。

The following header shows an implementation of a planar shape primitive, which is used by the example Shape_detection/efficient_RANSAC_with_custom_shape.cpp.

下面的示例，即显示了一个自定义的平面形状图元

  1. #ifndef MY_PLANE_SHAPE_H
  2. #define MY_PLANE_SHAPE_H
  3. #include <CGAL/number_utils.h>
  4. #include <CGAL/Shape_detection/Efficient_RANSAC.h>
  6. // My_Plane is derived from Shape_base.
  7. //The plane is represented by its normal vector and distance to the origin.
  8. //此平面由它的法向量和到原点的距离表示
  9. template <class Traits>
  10. class My_Plane : public CGAL::Shape_detection::Shape_base<Traits> {
  11. public:
  12.   typedef typename Traits::FT FT;           // number type
  13.   typedef typename Traits::Point_3 Point;   // point type
  14.   typedef typename Traits::Vector_3 Vector; // vector type
  15.   My_Plane() :
  16.   CGAL::Shape_detection::Shape_base<Traits>()
  17.   { }
  19.   // Compute squared Euclidean distance from query point to the shape.
  20.   //计算任意点到该shape的平方距离
  21.   virtual FT squared_distance(const Point& p) const {
  22.     const FT sd = (this->constr_vec(m_point_on_primitive, p)) * m_normal;
  23.     return sd * sd;
  24.   }
  26.   Vector plane_normal() const {
  27.     return m_normal;
  28.   }
  29.   FT d() const {
  30.     return m_d;
  31.   }
  32.   // Return a string with shape parameters.
  33.   virtual std::string info() const {
  34.     std::stringstream sstr;
  35.     sstr << "Type: plane (" << this->get_x(m_normal) << ", "
  36.     << this->get_y(m_normal) << ", " << this->get_z(m_normal) << ")x - " <<
  37.     m_d << " = 0" << " #Pts: " << this->m_indices.size();
  38.     return sstr.str();
  39.   }
  40. protected:
  41.   // Construct shape base on a minimal set of samples from the input data.
  42.   //基于输入数据的最小样本集构造出形状
  43.   virtual void create_shape(const std::vector<std::size_t>& indices) {
  44.     const Point p1 = this->point(indices[0]);
  45.     const Point p2 = this->point(indices[1]);
  46.     const Point p3 = this->point(indices[2]);
  47.     m_normal = this->cross_pdct(p1 - p2, p1 - p3);
  48.     m_normal = m_normal * (1.0 / sqrt(this->sqlen(m_normal)));
  49.     m_d = -(p1[0] * m_normal[0] + p1[1] * m_normal[1] + p1[2] * m_normal[2]);
  50.     m_point_on_primitive = p1;
  51.     this->m_is_valid = true;
  52.   }
  53.   // Compute squared Euclidean distance from a set of points.
  54.   //计算一组点到欧几里得距离的平方
  55.   virtual void squared_distance(const std::vector<std::size_t>& indices,
  56.     std::vector<FT>& dists) const {
  57.     for (std::size_t i = 0; i < indices.size(); ++i) {
  58.       const FT sd = (this->point(indices[i]) - m_point_on_primitive) * m_normal;
  59.       dists[i] = sd * sd;
  60.     }
  61.   }
  62.   // Compute the normal deviation between a shape and a set of points with normals.
  63.   //计算形状与一组具有法线点之间的法线偏差
  64.   virtual void cos_to_normal(
  65.     const std::vector<std::size_t>& indices,
  66.     std::vector<FT>& angles) const {
  67.     for (std::size_t i = 0; i < indices.size(); ++i)
  68.       angles[i] = CGAL::abs(this->normal(indices[i]) * m_normal);
  69.   }
  70.   // Return the number of required samples for construction.
  71.   //返回所需的样品数量
  72.   virtual std::size_t minimum_sample_size() const {
  73.     return 3;
  74.   }
  75. private:
  76.   Point  m_point_on_primitive;
  77.   Vector m_normal;
  78.   FT     m_d;
  79. };
  80. #endif // MY_PLANE_SHAPE_H

区域增长算法

This shape detection component is based on the region growing algorithm applied to a set of user-specified items. Shapes are detected by growing regions from seed items, where each region is created as follows:

  1. Pick the next available seed item;
  2. Find its neighbors in the data set;
  3. Include those neighbors, which satisfy the region requirements;
  4. Repeat the procedure for all included neighbors;
  5. If no further neighbor satisfies the requirements, start a new region.

此形状检测组件基于区域增长算法，此算法应用于一组由用户指定的项目(items)。形状由种子项目(items)的生长区域检测，每个区域的创建如下：

  1. 选择下一个可用的种子项目；
  2. 在数据集中找到它的邻居
  3. 包括满足区域要求的邻域
  4. 对所有包含的邻居重复这个过程
  5. 如果没有其他邻居满足要求，则启动一个新的区域

Together with the generic algorithm’s implementation CGAL::Shape_detection::Region_growing, three particular instances of this algorithm are provided:

与通用版本的区域增长算法一起（[CGAL::Shape_detection::Region_growing](https://doc.cgal.org/latest/Shape_detection/classCGAL_1_1Shape__detection_1_1Region__growing.html)），本代码库还提供了三个具体实现：

  • 二维点集的线检测
  • 三维点集的车道检测
  • 多边形网格的平面检测

Other instances can be easily added by the user, as explained below.

用户可以很容易的添加其他实例，如下所示：

框架Framework

The main class CGAL::Shape_detection::Region_growing is parameterized by

  • InputRange that stores a range of user-defined input items;
  • NeighborQuery that provides the means for accessing neighbors of an item;
  • RegionType that provides the means for validating regions;
  • SeedMap that defines the seeding order of items.

Using this generic framework, users can grow any type of regions on a set of arbitrary items with their own propagation and seeding conditions (see an example).

主类CGAL::Shape_detection::Region_growing的参数为：

  • InputRange 用户自定义输入项的范围
  • NeighborQuery 提供访问邻居的方法
  • RegionType 提供验证区域的方法
  • SeedMap 定义播种顺序

使用这个通用框架，用户可以根据自己的传播和播种条件，在一组任意项目上生成任何类型的区域（参见示例）

示例

This toy example shows how to define one’s own NeighborQuery and RegionType classes, which are used to parameterize the CGAL::Shape_detection::Region_growing. It also shows how to skip unnecessary items and change their default seeding order.

此示例展示了如何定义自己的NeighborQuery和RegionType类，它们用于参数化CGAL::Shape_detection::Region_growing。它还展示了如何跳过不必要的项目，并更改其默认播种顺序。

File Shape_detection/region_growing_with_custom_classes.cpp

// STL includes.
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <iterator>
// CGAL includes.
#include <CGAL/Shape_detection/Region_growing/Region_growing.h>
// Custom Neighbor_query, Region_type, and Seed_map classes for region growing.
namespace Custom {
  // An object that stores indices of all its neighbors.
  //Object：存储它邻居的索引
  struct Object {
    std::vector<std::size_t> neighbors;
  };
  // A range of objects.
  using Objects = std::vector<Object>;
  // The Neighbor_query functor that accesses neighbors stored in
  // the object struct above.
  class Neighbor_query {
    const Objects& m_objects;
  public:
    Neighbor_query(const Objects& objects) :
    m_objects(objects)
    { }
    void operator()(
      const std::size_t query_index,
      std::vector<std::size_t>& neighbors) const {
      std::size_t i = 0;
      for (const auto& object : m_objects) {
        if (i == query_index) {
          neighbors = object.neighbors;
          return;
        } ++i;
      }
    }
  };
  // The Region_type class, where the function is_part_of_region() verifies
  // a very specific condition that the first and second objects in the
  // range are in fact neighbors; is_valid_region() function always
  // returns true after the first call to the update() function.
  // These are the only functions that have to be defined.
  class Region_type {
    bool m_is_valid = false;
  public:
    Region_type() { }
    bool is_part_of_region(
      const std::size_t,
      const std::size_t query_index,
      const std::vector<std::size_t>& region) const {
      if (region.size() == 0)
        return false;
      const std::size_t index = region[0];
      if (index == 0 && query_index == 1) return true;
      if (query_index == 0 && index == 1) return true;
      return false;
    }
    inline bool is_valid_region(const std::vector<std::size_t>&) const {
      return m_is_valid;
    }
    void update(const std::vector<std::size_t>&) {
      m_is_valid = true;
    }
  };
  // The SeedMap class that uses the m_objects_map to define
  // the seeding order of objects.
  class Seed_map {
  public:
    using key_type   = std::size_t;
    using value_type = std::size_t;
    using reference  = std::size_t;
    using category   = boost::readable_property_map_tag;
    Seed_map(const std::map<std::size_t, std::size_t>& objects_map)
      : m_objects_map(objects_map)
    { }
    value_type operator[](const key_type& key) const
    {
      return m_objects_map.find(key)->second;
    }
    friend value_type get(const Seed_map& seed_map,
                          const key_type& key)
    {
      return seed_map[key];
    }
  private:
    const std::map<std::size_t, std::size_t>& m_objects_map;
  };
} // namespace Custom
// Type declarations.
using Object         = Custom::Object;
using Objects        = Custom::Objects;
using Neighbor_query = Custom::Neighbor_query;
using Region_type    = Custom::Region_type;
using Seed_map       = Custom::Seed_map;
using Region  = std::vector<std::size_t>;
using Regions = std::vector<Region>;
using Region_growing =
CGAL::Shape_detection::Region_growing<Objects, Neighbor_query, Region_type, Seed_map>;
int main() {
  std::cout << std::endl <<
    "region_growing_with_custom_classes example started"
  << std::endl << std::endl;
  // Define a range of objects, where the first two objects form
  // the first region, while the third object forms the second region.
  // Note that Objects is a random access container here, however the
  // same algorithm/example can work with other containers, e.g. std::list.
  Objects objects;
  // Region 1.
  Object object1;
  object1.neighbors.resize(1, 1);
  objects.push_back(object1);
  Object object2;
  object2.neighbors.resize(1, 0);
  objects.push_back(object2);
  // Region 2.
  Object object3;
  objects.push_back(object3);
  // Extra object to skip.
  Object object4;
  objects.push_back(object4);
  // Create instances of the classes Neighbor_query and Region_type.
  Neighbor_query neighbor_query = Neighbor_query(objects);
  Region_type    region_type    = Region_type();
  // Create a seed map.
  std::map<std::size_t, std::size_t> objects_map;
  objects_map[0] = 1; // the order is swapped with the next object
  objects_map[1] = 0;
  objects_map[2] = 2; // the default order
  objects_map[3] = std::size_t(-1); // skip this object
  const Seed_map seed_map(objects_map);
  // Create an instance of the region growing class.
  Region_growing region_growing(
    objects, neighbor_query, region_type, seed_map);
  // Run the algorithm.
  Regions regions;
  region_growing.detect(std::back_inserter(regions));
  // Print the number of found regions. It must be two regions.
  std::cout << "* " << regions.size() <<
    " regions have been found among " << objects.size() <<  " objects"
  << std::endl;
  std::cout << std::endl <<
    "region_growing_with_custom_classes example finished"
  << std::endl << std::endl;
  return EXIT_SUCCESS;
}

点集Point Set

If one wants to detect lines (see 2D Example)

如果想要检测线条（参见二维示例）
形状检测 - 图2

Figure 79.6 A 2D point set depicted with one color per detected line.

图 79.6用每条检测线一种颜色描绘的 2D 点集。

or planes (see 3D Example)

或者平面（参见三维示例）
形状检测 - 图3

Figure 79.7 A 3D point set depicted with one color per detected plane.

图79.7 一个三维点集，每个探测平面用一种颜色表示

PolygonMesh

If one wants to detect planes on a polygon mesh, this CGAL component provides the corresponding models of the concepts NeighborQuery and RegionType. In particular, it has

如果要检测多边形网格上的平面，此组件提供了NeighborQuery和RegionType概念的相应模型。特别是，它具有

This component accepts any model of the concept FaceListGraph as a polygon mesh. A picture below gives an example of the region growing algorithm for detecting 3D planes on CGAL::Surface_mesh.

此组件接受任何模型的FaceListGraph作为多边形网格。下面给出了，在CGAL::Surface_mesh中，用于检测3D平面的区域增长算法示例
image.png

Figure 79.10 A surface mesh depicted with one color per detected plane.

图79.10 每个检测平面用一种颜色描绘的表面网格。