---------原理介紹：

（1）首先計算出來各點的曲率值，將曲率值按照從小到大的順序進行排序。

（2）設置一空的種子點序列和一個空的聚類數組。

（3）選取曲率最小的點放入上述種子點序列中。

（4）從序列中拿出來一個種子點搜索其鄰域。

（5）搜索到鄰域后，這些點先過法線夾角閾值，通過的保留到聚類數據，然后再從這些通過法線夾角閾值的點中，檢查是否通過曲率閾值，通過的加入種子點序列。即比較鄰域點的法線與當前種子點法線之間的夾角，如果小于閾值將該鄰域點加入聚類數組。再從這些小于法線閾值的點中判斷是否小于曲率閾值，如果小于則將該鄰域點加入種子序列。

（6）結束后刪除用過的種子點，用下一個種子點重復第（4）（5）步，直至種子點序列清空為止。

（7）從曲率排序的點中，即從小到大的排序，取聚類數組中沒有的點作為種子點，重復第（2）（3）（4）（5）（6）步驟。

可以理解為，聚類出的同一個平面上的點，曲率小于某一閾值(設置的曲率閾值)，才可以當作種子點，繼續生長。

曲率閾值和法相量夾角閾值都是需要提前設置的。首先將曲率從小到大排序，選取最小的加入種子序列，這時候種子序列里只有一個點，然后拿出種子序列中的一個點(這時候也就是這個剛放進去的唯一的點)，和設置了指定范圍的臨域中的點比較法相量夾角，如果小于法相量夾角閾值，則這個臨域的點和種子點是同一個平面，另外，如果這個點的曲率小于曲率閾值，則把這個點當作種子點，放入種子序列。反復上面的過程，直到種子序列為空，此時長出了一個平面。

其實在實際源代碼中你會看到有一個做標記的過程還有一個記錄聚類個數的過程。（分割其實就是賦標簽的過程，種子點開始生長，滿足條件就一直長，直到不滿足條件了就不長了，把這些點標記一個標簽，再從剩下的點里面重新選種子點，再次生長，標簽累加，一直迭代到沒有點為止。）（-1代表還沒有標記的點云?如果！=-1說明該點已經標記過標簽了?已經分割過的點云不參與后續的分割。）

以下是分步代碼解讀：

1.就是讀取數據（略）

2.基于kd-tree搜索求法線，求的的法線保存在normal_里邊（略）

3.鄰域

//3.鄰域************************************************************************************int point_num = cloud->points.size();//cloud點云個數,賦值給point_numvector<int>nebor_index;//vectot存放近鄰搜索的索引vector<float>nebor_dis;//vectot存放近鄰搜索的距離int nebor_size(10);//類似于 int nebor_size=10 近鄰搜索的個數vector<vector<int>>point_nebor;//point_nebor是個vector，該vector的元素還是vectorpoint_nebor.resize(point_num, nebor_index);for (int i_point = 0; i_point < point_num; i_point++){tree->nearestKSearch(cloud->points[i_point], nebor_size, nebor_index, nebor_dis);//把計算出來鄰域矩陣和存儲鄰域的矩陣置換了一下point_nebor[i_point].swap(nebor_index);//容器的swap()交換函數不是一般的swap(a,b)交換函數}

下面是關于在C++中vector<vector<int>>的用法

vector<vector<int> > A;//正確的定義方式
vector<vector<int>> A;//c++11之前這樣定義是錯誤的，c++11之后支持這種定義方式

codeblocks設置支持c++11：Settings->Compiler->Compiler Flags

插入元素

若想定義A = [[0,1,2],[3,4]]，有兩種方法。

（1）定義vector B分別為[0,1,2]和[3,4]，然后放入vector A。

//第一種方式
vector<vector<int> > A;vector<int> B;
B.push_back(0);
B.push_back(1);
B.push_back(2);A.push_back(B);//把B中的元素放入A中B.clear();
B.push_back(3);
B.push_back(4);A.push_back(B);

//第二種方式
vector<vector<int> > A;
for(int i = 0; i < 2; ++i)  A.push_back(vector<int>());   
A[0].push_back(0);
A[0].push_back(1);
A[0].push_back(2);//注意下邊A的索引值由0變為1
A[1].push_back(3);
A[1].push_back(4);

長度

//vector<vector<int> >A中的vector元素的個數
len = A.size();
//vector<vector<int> >A中第i個vector元素的長度
len = A[i].size();

訪問某元素（訪問某元素時，方法和二維數組相同，例如：）

//根據前面的插入，可知輸出1。
printf("%d\n", A[0][1]);

vector之resize()函數

c++中序列式容器的一個共性函數，
vv.resize(int n,element)表示調整容器vv的大小為n，擴容后的每個元素的值為element，默認為0
resize()會改變容器的容量和當前元素個數
定義 vector<type> vv；
頭文件#include<vector>//標準模版庫的內容

std::vector::resize

void resize (size_type n, value_type val = value_type());

resize()的作用是改變vector中元素的數目。
如果n比當前的vector元素數目要小，vector的容量要縮減到resize的第一個參數大小，既n。并移除那些超出n的元素同時銷毀他們。
如果n比當前vector元素數目要大，在vector的末尾擴展需要的元素數目，如果第二個參數val指定了，擴展的新元素初始化為val的副本，否則按類型默認初始化。
注意：如果n大于當前的vector的容量(是容量，并非vector的size)，將會引起自動內存分配。所以現有的pointer,references,iterators將會失效。

resize()，設置大小（size）;size指指當前容器所存儲的元素個數。

reserve()，設置容量（capacity）;capacity指容器在分配新的存儲空間之前能存儲的元素總數。

size()是分配容器的內存大小，而capacity()只是設置容器容量大小，但并沒有真正分配內存。

打個比方：正在建造的一輛公交車，車里面可以設置40個座椅（reserve(40);），這是它的容量，但并不是說它里面就有了40個座椅，只能說明這部車內部空間大小可以放得下40張座椅而已。而車里面安裝了40個座椅(resize(40);)，這個時候車里面才真正有了40個座椅，這些座椅就可以使用了。

1).reserve表示容器預留空間，但并不是真正的創建對象，需要通過insert（）或push_back（）等創建對象。

resize既分配了空間，也創建了對象。

2).reserve只修改capacity大小，不修改size大小，resize既修改capacity大小，也修改size大小。

3).兩者的形參個數不一樣。

?? resize帶兩個參數，一個表示容器大小，一個表示初始值（默認為0）

?? reserve只帶一個參數，表示容器預留的大小。

#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{      vector <int> wgw;cout << "initilize size is: " << wgw.size() << endl;    //輸出0cout << "initilize capacity is :" << wgw.capacity() <<endl;       //輸出0wgw.reserve(100);cout << "wgw size is: " << wgw.size() << endl;    //輸出0cout << "wgw capacity is :" << wgw.capacity() <<endl;    //輸出100vector <int>wgw1;wgw1.resize(200);cout << "wgw1 size is :" << wgw1.size()<<endl;     //輸出200cout << "wgw1 capacity is:" << wgw1.capacity() <<endl;     //輸出200return 0; 
}

vector利用swap()函數進行內存的釋放

swap可以有效降低當前 vector占用的內存總量。還有一個將 vector內存全部釋放的技巧：

vector<int> vecEmpty;

v.swap(vecEmpty); //將要操作的 vector v與空 vector置換，可以將當前的 vector清空

首先，vector與deque不同，其內存占用空間只會增長，不會減小。比如你首先分配了10,000個字節，
然后erase掉后面9,999個，則雖然有效元素只有一個，但是內存占用仍為10,000個。所有空間在vector析構時回收。

empty()是用來檢測容器是否為空的，clear()可以清空所有元素。
但是即使clear()，所占用的內存空間依然如故。如果你需要空間動態縮小，可以考慮使用deque。
如果非要用vector，這里有一個辦法：
使用這種方法的前提是vector從前存儲了大量數據，比如10000000，經過各種處理后，
現在只有100條，那么向清空原來數據所占有的空間，
就可以通過這種交換技術swap技法
就是通過交換函數swap（），使得vector離開其自身的作用域，
從而強制釋放vector所占的內存空間。

vector<int>a,b;
for(int i=1;i<=10;++i) a.push_back(i);
a.swap(b);//這樣a的空間大小就被釋放了，現在是b存到了a里邊，應該是這樣的？？

4.曲率

vector<pair<float, int>>point_curvature_index;//在vector中插入pair對的用法for (int i_point = 0; i_point < point_num; i_point++){//使用make_pair(float,int)先給pair賦值，之后存入vectorpoint_curvature_index.push_back(make_pair(normal_->points[i_point].curvature, i_point));}sort(point_curvature_index.begin(), point_curvature_index.end());//將計算出來的曲率按照從小到大排序

C++中pair用法：

//定義一種新類型，它是一種vector類型，且每個元素都是pair類型。

typedef vector<pair<int, int> > vCoordinate;? //>和>之間要有一個空格? C++11新標準可以不用

pair是C++中一種模板類型。每個pair對象可以存儲兩個值，這兩個值可以是不同的數據類型。存儲的值可以是基本數據類型也可以是自定義數據類型。

using namespace std; ? 或? using std::pair; pair<int, int> pdata; ?? 或使用全名std::pair<int, int> pdata;

（1）定義和初始化

pair<int, int> p1(1, 2);//同種類型int,int
pair<int, int> p2(p1); //使用已有的p1對象初始化
pair<int, float> p3(1, 1.2);//不同類型int,float
pair<int, int> p4; //沒有顯示初始化，自動執行默認初始化操作。p4為(0,0)

（2）賦值操作

pair<int, int> p1(1, 2);
pair<int, int> p2;
p2 = pair<int, int> (1, 4);//賦值操作，需要用強制轉換p2 = p1; //賦值操作

使用make_pair()函數

pair<int, int> p3;
p3 = make_pair(1, 4); //無需指明類型，可自動生成pair對象

（3）訪問和修改操作

pair有兩個屬性：first和second。

pair<int, int> p1(1, 2);
p1.first = 11; //修改第一個數值
p1.second = 22; //修改第二個數值
cout << p1.first << "," << p1.second << endl;

STL中map通過鍵－值的形式保證一一對應關系，而multimap則可以出現一對多的關系，這兩種數據類型在存儲數據時，會根據pair<>的first成員進行排序，不同的是前者將不會插入對first成員重復的結構，而后者可以。

而當我們我們只想存儲pair對，不需要對其排序時，就可以用到vector，將pair對插入其中即可。下面就使用做一些簡單說明：
（1）聲明vector：
? ? ?? vector<pair<int,int>>vec
（2）往vector中插入數據，需要用到make_pair:
? ? ? vec.push_back(make_pair<int,int>(10,50));
? ? ? vec.push_back(make_pair(20,30));
（3）定義迭代器：
? ? ? vector<pair<int,int> > ::iterator iter;
? ? ? for(iter=vec.begin();iter!=vec.end();iter++);
（4）數據讀取：
? ? ? 第一個數據:(*iter).first
? ? ? 第二個數據:(*iter).second
?

//使用vector+pair來實現直角坐標數據的存放
#include<iostream>
#include<vector>
using namespace std;		
//定義一種新類型，它是一種vector類型，且每個元素都是pair類型。		
typedef vector<pair<int, int> > vCoordinate;// >和>之間要有一個空格	 	
int main()	
{		vCoordinate vCoor;		for (int i = 0; i < 10; ++i)		{	vCoor.push_back(vCoordinate::value_type(i, i));//往vector中插入元素//相當于存儲坐標數據（x,y）	}	for (int i = 0; i < vCoor.size(); ++i)		{	//輸出坐標數據		cout << vCoor[i].first << ", " << vCoor[i].second << endl;//循環輸出坐標（x,y）	}		 	getchar();	return 0;	
}

value_type可用于獲取vector中元素的類型，則vCoordinate::value_type會獲取到vCoordinate元素的類型pair<int, int>。所以vCoordinate::value_type(i, i)就等價于pair<int, int>(i, ?i)。
sort()函數用法

（1）Sort函數包含在頭文件為#include<algorithm>的c++標準庫中，調用標準庫里的排序方法可以不必知道其內部是如何實現的，只要出現我們想要的結果即可！

（2）Sort函數有三個參數：

? ? ? ? （2.1）第一個是要排序的數組的起始地址。

? ? ?? （2.2）第二個是結束的地址（最后一位要排序的地址）

? ? ?? （ 2.3）第三個參數是排序的方法，可以是從大到小也可是從小到大，還可以不寫第三個參數，此時默認的排序方法是從小到大排序。

Sort函數使用模板: ?? Sort(start,end,排序方法)

//指定一個從大到小的排序方法
#include<iostream>
#include<algorithm>
using namespace std;
bool complare(int a,int b)
{return a>b;
}
int main()
{int a[10]={9,6,3,8,5,2,7,4,1,0};for(int i=0;i<10;i++)cout<<a[i]<<endl;sort(a,a+10,complare);//在這里就不需要對complare函數傳入參數了，
//這是規則for(int i=0;i<10;i++)cout<<a[i]<<endl;return 0;
}

5.區域生長

float normal_threshold = cosf(10.0 / 180.0 * M_PI);//余弦 表示法線閾值float curvature_threshold = 0.4;//法向量閾值,曲率閾值int counter_(0), segment_label(0);//賦值為0int seed_index_orginal = point_curvature_index[0].second;//選取第一個最小的曲率點作為初始種子點的索引，對應前邊兩個值中的第二個vector<int>point_label;vector<int>seg_ave_num;point_label.resize(point_num, -1);//（大小，初始值）就是point_label里邊都是-1while (counter_<point_num)//point_num整個點云的點數{queue<int>seed;//隊列創建：queue <int> queue1;這里的int可以是各種類型，包括結構體類型seed.push(seed_index_orginal);//加入隊列：queue1.push(x);將x添加到隊列的末尾int counter_1(1);point_label[seed_index_orginal] = segment_label;//此處的為0while (!seed.empty())//判斷是否為空，不為空執行操作{int curr_seed = seed.front();//訪問隊首元素，如例：q.front()，即最早被壓入隊列的元素。seed.pop();//出隊，如例：q.pop(); 彈出隊列的第一個元素，注意，并不會返回被彈出元素的值。int K_nebor(0);while (K_nebor<nebor_size)//相當于小于10{//point_nebor[隊列中的第一個元素就是第一個曲率值最小的那個點][從0到9]int index_nebor = point_nebor[curr_seed][K_nebor];if (point_label[index_nebor] != -1)//這里怎么判斷是否等于-1？？?如果不等于-1就K_nebor疊加{K_nebor++;continue;}bool is_a_seed = false;Map<Vector3f>curr_seed(static_cast<float*>(normal_->points[curr_seed].normal));Map<Vector3f>seed_nebor(static_cast<float*>(normal_->points[index_nebor].normal));float dot_normal = fabsf(curr_seed.dot(seed_nebor));if (dot_normal<normal_threshold){is_a_seed = false;}else if (normal_->points[index_nebor].curvature>curvature_threshold){is_a_seed = false;}else{is_a_seed = true;}if (!is_a_seed){K_nebor++;continue;}point_label[index_nebor] = segment_label;counter_1++;if (is_a_seed){seed.push(index_nebor);}K_nebor++;}}segment_label++;counter_ += counter_1;seg_ave_num.push_back(counter_1);for (int i_seg = 0; i_seg < point_num; i_seg++){int index_ = point_curvature_index[i_seg].second;if (point_label[index_] == -1){seed_index_orginal = index_;break;}}}

queue

C++隊列是一種容器適配器，提供了一種先進先出的數據結構。
queue 模板類的定義在<queue>頭文件中。
與stack 模板類很相似，queue 模板類也需要兩個模板參數，一個是元素類型，一個容器類
型，元素類型是必要的，容器類型是可選的，默認為deque 類型。
定義queue 對象的示例代碼如下：
queue<int> q1;
queue<double> q2;

queue 的基本操作有：
（1）入隊，如例：q.push(x); 將x 接到隊列的末端。
（2）出隊，如例：q.pop(); 彈出隊列的第一個元素，注意，并不會返回被彈出元素的值。
（3）訪問隊首元素，如例：q.front()，即最早被壓入隊列的元素。
（4）訪問隊尾元素，如例：q.back()，即最后被壓入隊列的元素。
（5）判斷隊列空，如例：q.empty()，當隊列空時，返回true。即若為空隊列則返回1，否則返回0
（6）訪問隊列中的元素個數，如例：q.size()

注意queue中無法使用迭代器，無法對隊列進行遍歷，所以如果有遍歷要求的話就不能使用隊列。

//一部分源碼
//PCL基于法向量和曲率的區域生長算法
#include <pcl/io/pcd_io.h>
#include <pcl/search/kdtree.h>
#include <vector>
#include <pcl/features/normal_3d.h>
#include <Eigen/dense>
#include <cmath>
#include <ctime>
#include<pcl/visualization/pcl_visualizer.h>
using namespace pcl;
using namespace Eigen;
using namespace std;
int main() 
{//1.讀取數據PointCloud<PointXYZ>::Ptr cloud(new PointCloud<PointXYZ>);io::loadPCDFile("F://coutsaved//test//boxes//pcd//6.pcd", *cloud);//2.基于kd-tree搜索求法線，求的的法線保存在normal_里邊search::KdTree<PointXYZ>::Ptr tree(new search::KdTree<PointXYZ>);PointCloud<Normal>::Ptr normal_(new PointCloud<Normal>);NormalEstimation<PointXYZ, Normal>ne;tree->setInputCloud(cloud);ne.setInputCloud(cloud);ne.setSearchMethod(tree);ne.setKSearch(10);ne.compute(*normal_);//3.鄰域************************************************************************************int point_num = cloud->points.size();//點云個數vector<int>nebor_index;//vectot存放近鄰索引vector<float>nebor_dis;//vectot存放近鄰距離int nebor_size(10);//類似于 int nebor_size=10vector<vector<int>>point_nebor;//point_nebor是個vector，該vector的元素還是vectorpoint_nebor.resize(point_num, nebor_index);//重新修改point_nebor大小，將point_num即cloud大小給point_neborfor (int i_point = 0; i_point < point_num; i_point++){tree->nearestKSearch(cloud->points[i_point], nebor_size, nebor_index, nebor_dis);//原來point_nebor被resize成了cloud點云個數的大小，現在point_nebor[i_point]就是一個點即i_point表示一個點，存儲10個索引point_nebor[i_point].swap(nebor_index);//swap()交換函數//替換完之后事實上這個point_nebor仍然是cloud點云個數的大小，只是里邊每個點都存儲了10個索引，并未改變point_nebor的大小}//4.曲率*************************************************************************************vector<pair<float, int>>point_curvature_index;for (int i_point = 0; i_point < point_num; i_point++){//point_curvature_index里邊存放的是（曲率，該曲率對應的點號）是兩個值point_curvature_index.push_back(make_pair(normal_->points[i_point].curvature, i_point));}sort(point_curvature_index.begin(), point_curvature_index.end());//每點的曲率排序//5.區域生長*******************************************************************************float normal_threshold = cosf(10.0 / 180.0 * M_PI);//余弦 表示法線閾值float curvature_threshold = 0.4;//法向量閾值,曲率閾值int counter_(0), segment_label(0);//賦值為0int seed_index_orginal = point_curvature_index[0].second;//選取第一個最小的曲率點作為初始種子點的索引，對應前邊兩個值中的第二個vector<int>point_label;vector<int>seg_ave_num;point_label.resize(point_num, -1);//（大小，初始值）就是point_label里邊都是-1while (counter_<point_num)//point_num整個點云的點數{queue<int>seed;//隊列創建：queue <int> queue1;這里的int可以是各種類型，包括結構體類型seed.push(seed_index_orginal);//加入隊列：queue1.push(x);將x添加到隊列的末尾int counter_1(1);point_label[seed_index_orginal] = segment_label;//此處的為0while (!seed.empty())//判斷是否為空，不為空執行操作{int curr_seed = seed.front();//訪問隊首元素，如例：q.front()，即最早被壓入隊列的元素。seed.pop();//出隊，如例：q.pop(); 彈出隊列的第一個元素，注意，并不會返回被彈出元素的值。int K_nebor(0);while (K_nebor<nebor_size)//相當于小于10{//point_nebor[隊列中的第一個元素就是第一個曲率值最小的那個點][從0到9]int index_nebor = point_nebor[curr_seed][K_nebor];if (point_label[index_nebor] != -1)//這里怎么判斷是否等于-1？？?如果不等于-1就K_nebor疊加{K_nebor++;continue;}bool is_a_seed = false;Map<Vector3f>curr_seed(static_cast<float*>(normal_->points[curr_seed].normal));Map<Vector3f>seed_nebor(static_cast<float*>(normal_->points[index_nebor].normal));float dot_normal = fabsf(curr_seed.dot(seed_nebor));if (dot_normal<normal_threshold){is_a_seed = false;}else if (normal_->points[index_nebor].curvature>curvature_threshold){is_a_seed = false;}else{is_a_seed = true;}if (!is_a_seed){K_nebor++;continue;}point_label[index_nebor] = segment_label;counter_1++;if (is_a_seed){seed.push(index_nebor);}K_nebor++;}}segment_label++;counter_ += counter_1;seg_ave_num.push_back(counter_1);for (int i_seg = 0; i_seg < point_num; i_seg++){int index_ = point_curvature_index[i_seg].second;if (point_label[index_] == -1){seed_index_orginal = index_;break;}}}//分割結果匯總***************************************************vector<PointIndices>cluster_;PointIndices segments;int seg_num = seg_ave_num.size();cluster_.resize(seg_num, segments);for (int i_seg = 0; i_seg < seg_num; i_seg++) {cluster_[i_seg].indices.resize(seg_ave_num[i_seg], 0);}vector<int> counter;counter.resize(seg_num, 0);for (int i_point = 0; i_point < point_num; i_point++){int segment_index = point_label[i_point];int nebor_idx = counter[segment_index];cluster_[segment_index].indices[nebor_idx] = i_point;counter[segment_index] += 1;}//剔除一定數量的分割單元*****************************************vector<PointIndices>clusters;int min_number = 6000, max_number = 1000000;for (int i_seg = 0; i_seg < seg_num; i_seg++){if (cluster_[i_seg].indices.size()>min_number&&cluster_[i_seg].indices.size() < max_number){clusters.push_back(cluster_[i_seg]);}}//可視化*********************************************************visualization::PCLVisualizer::Ptr viewer(new visualization::PCLVisualizer("view"));PointCloud<PointXYZRGB>::Ptr color_point(new PointCloud<PointXYZRGB>);srand(time(nullptr));vector<unsigned char>color;for (int i_segment = 0; i_segment < clusters.size(); i_segment++){color.push_back(static_cast<unsigned char>(rand() % 256));color.push_back(static_cast<unsigned char>(rand() % 256));color.push_back(static_cast<unsigned char>(rand() % 256));}int color_index = 0;for (int i_seg = 0; i_seg < clusters.size(); i_seg++){int clusters_size = clusters[i_seg].indices.size();for (int i_idx = 0; i_idx < clusters_size; i_idx++){PointXYZRGB point;point.x = cloud->points[clusters[i_seg].indices[i_idx]].x;point.y = cloud->points[clusters[i_seg].indices[i_idx]].y;point.z = cloud->points[clusters[i_seg].indices[i_idx]].z;point.r = color[3 * color_index];point.g = color[3 * color_index + 1];point.b = color[3 * color_index + 2];color_point->push_back(point);}color_index++;}viewer->addPointCloud(color_point);viewer->spin();return 0;
}

下面是調用pcl::RegionGrowing類中調用區域增長算法。首先注意一點，這里是region growing segmentation，不是color-based region growing segmentation.

算法核心：該算法是基于點法線之間角度的比較，企圖將滿足平滑約束的相鄰點合并在一起，以一簇點集的形式輸出。每簇點集被認為是屬于相同平面。

算法核心：該算法是基于點法線之間角度的比較，企圖將滿足平滑約束的相鄰點合并在一起，以一簇點集的形式輸出。每簇點集被認為是屬于相同平面。

工作原理：首先需要明白，區域增長是從有最小曲率值(curvature value)的點開始的。因此，我們必須計算出所有曲率值，并對它們進行排序。這是因為曲率最小的點位于平坦區域，而從最平坦的區域增長可以減少區域的總數。現在我們來具體描述這個過程：

1.點云中有未標記點，按照點的曲率值對點進行排序，找到最小曲率值點，并把它添加到種子點集；

2.對于每個種子點，算法都會發現周邊的所有近鄰點。1）計算每個近鄰點與當前種子點的法線角度差(reg.setSmoothnessThreshold)，如果差值小于設置的閾值，則該近鄰點被重點考慮，進行第二步測試；2）該近鄰點通過了法線角度差檢驗，如果它的曲率小于我們設定的閾值(reg.setCurvatureThreshold)，這個點就被添加到種子點集，即屬于當前平面。

3.通過兩次檢驗的點，被從原始點云去除。

4.設置最小點簇的點數min（reg.setMinClusterSize），最大點簇為max（reg.setMaxClusterSize）。

4.重復1-3步，算法會生成點數在min和max的所有平面，并對不同平面標記不同顏色加以區分。

5.直到算法在剩余點中生成的點簇不能滿足min，算法停止工作。

//PCL里邊的Region growing調用格式非源碼
#include <pcl/point_types.h>
#include <pcl/io/pcd_io.h>
#include <pcl/search/search.h>
#include <pcl/search/kdtree.h>
#include <pcl/features/normal_3d.h>
#include <pcl/visualization/cloud_viewer.h>
#include <pcl/features/integral_image_normal.h>
#include <pcl/segmentation/region_growing.h>
#include <pcl/filters/voxel_grid.h>int main(int argc, char** argv)
{pcl::PointCloud<pcl::PointXYZRGBA>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZRGBA>); // PointXYZRGBA型點云pcl::PCDReader reader;reader.read("pig2.pcd", *cloud); pcl::visualization::CloudViewer viewer("Cloud Viewer"); // 創建一個可視化窗口viewer.showCloud(cloud); // 在窗口中顯示點云while (!viewer.wasStopped ()){}// 體素網格濾波pcl::VoxelGrid<pcl::PointXYZRGBA> sor;sor.setInputCloud(cloud);sor.setLeafSize(0.005f, 0.005f, 0.005f);sor.filter(*cloud);pcl::visualization::CloudViewer viewer2("Cloud Viewer"); // 創建一個可視化窗口viewer2.showCloud(cloud); // 在窗口中顯示點云while (!viewer2.wasStopped ()){}// 創建一個空的kd-treepcl::search::KdTree<pcl::PointXYZRGBA>::Ptr tree (new pcl::search::KdTree<pcl::PointXYZRGBA> ());// 創建一個normal點云pcl::PointCloud <pcl::Normal>::Ptr cloud_normals (new pcl::PointCloud <pcl::Normal>);pcl::NormalEstimation<pcl::PointXYZRGBA, pcl::Normal> normal_estimator; // 創建法線估計對象normal_estimator.setSearchMethod (tree); // 設置搜索方法normal_estimator.setInputCloud (cloud); // 設置法線估計對象輸入點集normal_estimator.setRadiusSearch (0.02); // 使用半徑在查詢點周圍2厘米范圍內的所有鄰元素normal_estimator.compute (*cloud_normals); // 計算并輸出法向量pcl::RegionGrowing<pcl::PointXYZRGBA, pcl::Normal> reg; // 創造區域生長分割對象reg.setMinClusterSize (50); // 設置一個聚類需要的最小點數，聚類小于閾值的結果將被舍棄reg.setMaxClusterSize (1000000); //設置一個聚類需要的最大點數，聚類大于閾值的結果將被舍棄reg.setSearchMethod (tree); // 設置搜索方法reg.setResidualThreshold (0.03); // 設置搜索的近鄰點數目reg.setInputCloud (cloud); // 設置輸入點云 reg.setInputNormals (cloud_normals); // 設置輸入點云reg.setSmoothnessThreshold (5 / 180.0 * M_PI); //設置平滑閥值reg.setCurvatureThreshold (1); //設置曲率閥值// 以下兩行用于啟動分割算法，并返回聚類向量std::vector <pcl::PointIndices> clusters;reg.extract (clusters); // 獲取聚類的結果，分割結果保存在點云索引的向量中//區域生長結果可視化pcl::PointCloud <pcl::PointXYZRGB>::Ptr colored_cloud = reg.getColoredCloud ();pcl::visualization::CloudViewer viewer3("Cloud Viewer"); // 創建一個可視化窗口viewer3.showCloud(colored_cloud);while (!viewer3.wasStopped ()){}
}

下圖從左到右分別為 ?? 原始點云 ?? 降采樣后的點云 ? ? 區域分割后的點云

? ?? ??

#include <iostream>
#include <vector>
#include <pcl/point_types.h>
#include <pcl/io/pcd_io.h>
#include <pcl/search/search.h>
#include <pcl/search/kdtree.h>
#include <pcl/features/normal_3d.h>
#include <pcl/visualization/cloud_viewer.h>
#include <pcl/filters/passthrough.h>
#include <pcl/segmentation/region_growing.h>int main(int argc, char** argv)
{DWORD t1, t2;t1 = GetTickCount();//以上兩句和最后return 0 之上的為計時函數。//點云的類型pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);//打開點云if (pcl::io::loadPCDFile <pcl::PointXYZ>("resultFloor局部.pcd", *cloud) == -1)//改成想要輸入的點云名稱...*cloud就是把輸入的點云記錄到變量指針cloud中。{std::cout << "Cloud reading failed." << std::endl;return (-1);}//設置搜索的方式或者說是結構pcl::search::Search<pcl::PointXYZ>::Ptr tree = boost::shared_ptr<pcl::search::Search<pcl::PointXYZ> >(new pcl::search::KdTree<pcl::PointXYZ>);//求法線pcl::PointCloud <pcl::Normal>::Ptr normals(new pcl::PointCloud <pcl::Normal>);pcl::NormalEstimation<pcl::PointXYZ, pcl::Normal> normal_estimator;normal_estimator.setSearchMethod(tree);normal_estimator.setInputCloud(cloud);normal_estimator.setKSearch(50);normal_estimator.compute(*normals);//直通濾波在Z軸的0到1米之間pcl::IndicesPtr indices(new std::vector <int>);pcl::PassThrough<pcl::PointXYZ> pass;pass.setInputCloud(cloud);pass.setFilterFieldName("z");pass.setFilterLimits(0.0, 1.0);pass.filter(*indices);//聚類對象<點，法線>pcl::RegionGrowing<pcl::PointXYZ, pcl::Normal> reg;//1首先還是先建立了一個區域增長的對象regreg.setMinClusterSize(50);  //最小的聚類的點數  //2然后設置平面包含的最少點數（這個參數非常重要，小于這個參數的平面會被忽略不計）reg.setMaxClusterSize(1000000);  //最大的   //3然后設置最大的點數，原理同上，但是一般我們希望的是無窮大，所以可以設大一點，當然如果你有特殊要求可以按自己需求來reg.setSearchMethod(tree);    //搜索方式reg.setNumberOfNeighbours(30);    //設置搜索的鄰域點的個數  //4然后設置參考的鄰域點數，也就是看看周邊的多少個點來決定這是一個平面（這個參數至關重要，決定了你的容錯率，如果設置的很大，那么從全局角度看某一個點稍微有點歪也可以接受，如果設置的很小則通常檢測到的平面都會很小）reg.setInputCloud(cloud);         //輸入點  //5然后輸入要檢測的點云cloud//reg.setIndices (indices);reg.setInputNormals(normals);     //輸入的法線  //6然后輸入點云的法線reg.setSmoothnessThreshold(3.0 / 180.0 * M_PI);  //設置平滑度  //7然后設置判斷的閾值，大概也就是兩個法線在多大的夾角內還可以當做是共面的reg.setCurvatureThreshold(1.0);     //設置曲率的閾值   //8最后也是一個彎曲的閾值，這個決定了比當前考察的點和平均的法線角度，決定是否還有繼續探索下去的必要。（也就是假設每個點都是平穩彎曲的，那么normal的夾角都很小，但是時間長了偏移的就大了，這個參數就是限制這個用的）std::vector <pcl::PointIndices> clusters;//9reg.extract(clusters);
//9然后就可以把結果輸出到一個簇里面，這個簇會自動把每個平面分成一個vector，可以打印下來看看std::cout << "Number of clusters is equal to " << clusters.size() << std::endl;std::cout << "First cluster has " << clusters[0].indices.size() << " points." << endl;std::cout << "These are the indices of the points of the initial" <<std::endl << "cloud that belong to the first cluster:" << std::endl;//int counter = 0;//while (counter < clusters[0].indices.size())//{//	std::cout << clusters[0].indices[counter] << ", ";//	counter++;//	if (counter % 10 == 0)//		std::cout << std::endl;//}//std::cout << std::endl;//可視化聚類的結果   //10也可以把檢測到的每個平面涂上不同的顏色pcl::PointCloud <pcl::PointXYZRGB>::Ptr colored_cloud = reg.getColoredCloud();//pcl::visualization::CloudViewer viewer("Cluster viewer");//viewer.showCloud(colored_cloud);//while (!viewer.wasStopped())//{//}pcl::PCDWriter writer;//將點云寫入磁盤writer.write("resultFloor局部_Cluster_viewer.pcd", *colored_cloud, false);//改成想要輸出的點云名稱t2 = GetTickCount();  //從這句到return 0之間的兩句為計時函數printf("Use Time:%f\n", (t2 - t1)*1.0 / 1000);return (0);
}

?

------擴展到二維圖片中Region Growing算法

（1）原理：

? ? ? ? ?

區域生長是根據預先定義的生長準則將像素或子區域組合為更大區域的過程。基本方法是從一組“種子”點開始（原點），將與種子相似的臨近像素（在特定范圍內的灰度或顏色）添加到種子棧中，不斷迭代，生成一大片區域。嚴謹的數學定義可以查看岡薩雷斯的數字圖像處理。

（2）算法實現

算法的步驟如下：

• 創建一個與原圖像大小相同的空白圖像
• 將種子點存入vector中，vector中存儲待生長的種子點
• 依次彈出種子點并判斷種子點如周圍8領域的關系(生長規則)并與最大與最小閾值進行比較，符合條件則作為下次生長的種子點
• vector中不存在種子點后就停止生長

（3）與三維區域生長算法不同的地方：

• 不需要kd-tree搜索鄰域，2D圖片的區域生長算法生長方向為八個且方向固定，如上圖所示。
• 三維區域生長，是否為同一類看法線閾值，是否可以作為種子點看曲率閾值。而2D圖片的區域生長這兩個閾值為同一個灰度閾值。

?

opencv實現：

#include <iostream>
#include <opencv2/opencv.hpp>using namespace std;
using namespace cv;Mat RegionGrow(Mat src, Point2i pt, int th)
{/*src：Mat類，輸入圖像pt：Point2i類，初始生長點th：int型，與初始生長點的灰度差在這個范圍內則進行生長*/int ptValue = 0;      /*當前生長點的灰度值*/Point2i pToGrowing;   /*待生長點位置*/int pToGrowLabel = 0; /*判斷待生長點是否生長過*/int pToGrowValue = 0; /*當前生長點灰度值*/Mat growLabelImage = Mat::zeros(src.size(), CV_8UC1); /*創建和輸入src等尺寸的空白區域，填充為黑色*/int DIR[8][2] = {{-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1}, {-1,0}}; /*生長方向順序數據*/vector<Point2i> ptVector; /*生長點棧*/ptVector.push_back(pt);   /*將初始生長點壓入棧中*/growLabelImage.at<uchar>(pt.y, pt.x) = 255; /*初始生長點位置填充為白色*/ptValue = src.at<uchar>(pt.y, pt.x); /*記錄初始生長點的灰度值*/while (!ptVector.empty()) /*生長棧為空則停止循環*/{pt = ptVector.back(); /*取出一個生長點*/ptVector.pop_back();  /*刪除生長點棧中的當前生長點*//*分別對八個方向上的點進行生長*/for (int i=0; i<8; ++i){   pToGrowing.x = pt.x + DIR[i][0]; /*得到待生長點的位置*/pToGrowing.y = pt.y + DIR[i][1];/*檢查是否是邊界點，如果是，則跳出循環*/if (pToGrowing.x < 0 || pToGrowing.y < 0 || pToGrowing.x > (src.cols-1) || (pToGrowing.y > src.rows -1)){continue;}/*判斷當前待生長點是否生長過*/pToGrowLabel = growLabelImage.at<uchar>(pToGrowing.y, pToGrowing.x);ptValue = src.at<uchar>(pt.y, pt.x) /*得到當前生長點的灰度值*/; /*如果當前待生長點還沒生長，進行區域生長，否則跳過*/if (pToGrowLabel == 0)                    {pToGrowValue = src.at<uchar>(pToGrowing.y, pToGrowing.x); /*得到當前待生長點的灰度值*/if (abs(ptValue - pToGrowValue) < th) /*在閾值范圍內則生長*/{growLabelImage.at<uchar>(pToGrowing.y, pToGrowing.x) = 255; /*生長過的點標記為白色*/ptVector.push_back(pToGrowing); /*將下一個生長點壓入棧中*/}}}}return growLabelImage.clone(); /*同一類的255，不是用一類是0*/
}int main(int argc, char** argv)
{Mat srcImg = imread("test.jpg"); /*用opencv讀取圖片*/Mat graySrcImg;Mat srcImgClone = srcImg.clone();cvtColor(srcImgClone, graySrcImg, CV_BGR2GRAY); /*轉化為灰度圖像*/Mat LabelMask;/*得到區域生長算法返回的mask*/    LabelMask = RegionGrow(graySrcImg, Point2i(134, 70), 24); /*設置初始種子位置和閾值*/  Mat outputImage = srcImg.clone();for(int j=0; j<LabelMask.rows; ++j){for(int k=0; k<LabelMask.cols; ++k){if(LabelMask.at<uchar>(j,k) == 0){outputImage.at<Vec3b>(j, k) = 0;}}}imshow("src", srcImg);imshow("gray", graySrcImg);imshow("mask", LabelMask);imshow("result", outputImage);waitKey(0);return 0;
}

下圖從左到右分別為? 原圖 ? 灰度圖 ? ? 區域生長算法返回的mask ? ? 掩膜后的結果

? ?? ?? ??

參考：https://blog.csdn.net/Zhang_Chen_/article/details/101228569

對原本的區域生長算法多加了最大與最小值的限制，作為默認參數可以不填。

/*** @brief 區域生長算法，輸入圖像應為灰度圖像* @param srcImage 區域生長的源圖像* @param pt 區域生長點* @param ch1Thres 通道的生長限制閾值，臨近像素符合±chxThres范圍內才能進行生長* @param ch1LowerBind 通道的最小值閾值* @param ch1UpperBind 通道的最大值閾值，在這個范圍外即使臨近像素符合±chxThres也不能生長* @return 生成的區域圖像（二值類型）*/
Mat RegionGrow(Mat srcImage, Point pt, int ch1Thres,int ch1LowerBind=0,int ch1UpperBind=255)
{Point pToGrowing;                       //待生長點位置int pGrowValue = 0;                             //待生長點灰度值Scalar pSrcValue = 0;                               //生長起點灰度值Scalar pCurValue = 0;                               //當前生長點灰度值Mat growImage = Mat::zeros(srcImage.size(), CV_8UC1);   //創建一個空白區域，填充為黑色//生長方向順序數據int DIR[8][2] = {{-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1}, {-1,0}};vector<Point> growPtVector;                     //生長點棧growPtVector.push_back(pt);                         //將生長點壓入棧中growImage.at<uchar>(pt.y, pt.x) = 255;              //標記生長點pSrcValue = srcImage.at<uchar>(pt.y, pt.x);         //記錄生長點的灰度值while (!growPtVector.empty())                       //生長棧不為空則生長{pt = growPtVector.back();                       //取出一個生長點growPtVector.pop_back();//分別對八個方向上的點進行生長for (int i = 0; i<8; ++i){pToGrowing.x = pt.x + DIR[i][0];pToGrowing.y = pt.y + DIR[i][1];//檢查是否是邊緣點if (pToGrowing.x < 0 || pToGrowing.y < 0 ||pToGrowing.x > (srcImage.cols-1) || (pToGrowing.y > srcImage.rows -1))continue;pGrowValue = growImage.at<uchar>(pToGrowing.y, pToGrowing.x);       //當前待生長點的灰度值pSrcValue = srcImage.at<uchar>(pt.y, pt.x);if (pGrowValue == 0)                    //如果標記點還沒有被生長{pCurValue = srcImage.at<uchar>(pToGrowing.y, pToGrowing.x);if(pCurValue[0] <= ch1UpperBind && pCurValue[0] >= ch1LowerBind ){if (abs(pSrcValue[0] - pCurValue[0]) < ch1Thres )                   //在閾值范圍內則生長{growImage.at<uchar>(pToGrowing.y, pToGrowing.x) = 255;      //標記為白色growPtVector.push_back(pToGrowing);                 //將下一個生長點壓入棧中}}}}}return growImage.clone();
}

上面是灰度圖像的處理，我這里重載了三通道圖像的區域生長

/*** @brief 區域生長算法，輸入圖像應為三通道圖像（RGB、HSV、YUV等）* @param srcImage 區域生長的源圖像* @param pt 區域生長點* @param ch1Thres ch2Thres ch3Thres 三個通道的生長限制閾值，臨近像素符合±chxThres范圍內才能進行生長* @param ch1LowerBind ch1LowerBind ch1LowerBind 三個通道的最小值閾值* @param ch1UpperBind ch2UpperBind ch3UpperBind 三個通道的最大值閾值，在這個范圍外即使臨近像素符合±chxThres也不能生長* @return 生成的區域圖像（二值類型）*/
Mat RegionGrow(Mat srcImage, Point pt, int ch1Thres,int ch2Thres, int ch3Thres,int ch1LowerBind=0,int ch1UpperBind=255,int ch2LowerBind=0,int ch2UpperBind=255,int ch3LowerBind=0,int ch3UpperBind=255)
{Point pToGrowing;                       //待生長點位置int pGrowValue = 0;                             //待生長點灰度值Scalar pSrcValue = 0;                               //生長起點灰度值Scalar pCurValue = 0;                               //當前生長點灰度值Mat growImage = Mat::zeros(srcImage.size(), CV_8UC1);   //創建一個空白區域，填充為黑色//生長方向順序數據int DIR[8][2] = {{-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1}, {-1,0}};vector<Point> growPtVector;                     //生長點棧growPtVector.push_back(pt);                         //將生長點壓入棧中growImage.at<uchar>(pt.y, pt.x) = 255;              //標記生長點pSrcValue = srcImage.at<Vec3b>(pt.y, pt.x);         //記錄生長點的灰度值while (!growPtVector.empty())                       //生長棧不為空則生長{pt = growPtVector.back();                       //取出一個生長點growPtVector.pop_back();//分別對八個方向上的點進行生長for (int i = 0; i<8; ++i){pToGrowing.x = pt.x + DIR[i][0];pToGrowing.y = pt.y + DIR[i][1];//檢查是否是邊緣點if (pToGrowing.x < 0 || pToGrowing.y < 0 ||pToGrowing.x > (srcImage.cols-1) || (pToGrowing.y > srcImage.rows -1))continue;pGrowValue = growImage.at<uchar>(pToGrowing.y, pToGrowing.x);       //當前待生長點的灰度值pSrcValue = srcImage.at<Vec3b>(pt.y, pt.x);if (pGrowValue == 0)                    //如果標記點還沒有被生長{pCurValue = srcImage.at<Vec3b>(pToGrowing.y, pToGrowing.x);if(pCurValue[0] <= ch1UpperBind && pCurValue[0] >= ch1LowerBind&&   //限制生長點的三通道上下界pCurValue[1] <= ch2UpperBind && pCurValue[1] >= ch2LowerBind &&pCurValue[2] <= ch3UpperBind && pCurValue[2] >= ch3LowerBind ){if (abs(pSrcValue[0] - pCurValue[0]) < ch1Thres &&abs(pSrcValue[1] - pCurValue[1]) < ch2Thres &&abs(pSrcValue[2] - pCurValue[2]) < ch3Thres)                    //在閾值范圍內則生長{growImage.at<uchar>(pToGrowing.y, pToGrowing.x) = 255;      //標記為白色growPtVector.push_back(pToGrowing);                 //將下一個生長點壓入棧中}}}}}return growImage.clone();
}

References：

https://www.jianshu.com/p/8e1bc28ef6fc

https://blog.csdn.net/liukunrs/article/details/80482788
https://blog.csdn.net/robin__chou/article/details/50071313
數字圖像處理（第三版） ——岡薩雷斯 P493

總結

以上是生活随笔為你收集整理的PCL：超详细的基于法向量和曲率的区域生长算法原理以及源码解读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。