k-meansのC++の実現
物は類を以て集まり,人は群を以て分ける
k-meansとは、k平均クラスタリングである.クラスタリングの過程は中国の歴史上の「春秋五覇、戦国七雄」のようなもので、それらは同じ中国の大地に属し、同時に周王室に分封されている.分封の過程はKクラスの指定過程に相当し,各諸侯国は1つのクラスタリングに対応する.五覇は五類、七雄は七類、五覇から七雄まで、つまり一つのクラスターの成長過程に相当する.
数学的に言えば,N個のサンプルが集合Aを構成し,欧米式距離に応じてAをKサブセットに分割する必要があると仮定すると,サブセットを分割する過程がk平均クラスタリング実現の過程である.
簡単に言えば、物はクラスタで、人はクラスタで、数学でもそうです.
K平均はどのように実現されたのか
周王室が諸侯を分封するように、k平均クラスタリングも「いったいどれだけ諸侯を分封するのか」と告げられる必要がある.诸侯王たちが马鹿ではないことを考えると、土地が肥沃で+物产が豊富で+风调雨顺+がほしい...だから周王室はいっそ「ランダムに指定しましょう!」と切った.そこで、諸侯たちは封地に着いた後、もっと彼らの居住に適した場所を得るために、絶えず彼らの国都を変えて、絶えず周囲の群落を蚕食して、ある日まで、彼らはそれぞれ自分の理想の国に達したことを発見しました--彼らは無限の子民を持っていて、無数の子民が彼らの周辺を囲んで、彼らは広大な土地を持っていて、彼らは土地の中央に位置しています!結局、すべての諸侯王は首都を移さず、定住過程も終わった.
k平均値を類比して、以下の点をまとめます.何人の諸侯が分封します--k値 最初はどうやって分けますか--ランダム 諸侯国移動--距離 まだ移動しますか--クラスタリング最適 定住--クラスタリング終了 こうぞうせっけい
もちろん、アルゴリズムを実現するには、データ構造の設計が欠かせません.主に3 DデータのK平均に対して計算されるため、各サンプルは1つの構造体タイプとして宣言する必要があります.
後続の計算を容易にするには、ポイントとそのポイントのインデックス番号を格納するための構造も設計する必要があります.
k平均アルゴリズムを実現する以上、
classを定義する以上、その含むべき具体的な実装関数を考慮すべきである.まず、クラスタ数Kはもちろんのこと、定義
次に、次のクラスタリングプロセスがどのように実現されるかを考えます.ああ、諸侯はランダムに分類されています.では、ランダム関数InitKcenter()を初期化します.次に、諸侯の移行は、クラスタリングセンターが絶えず変化する過程であり、クラスタリングセンターが更新された関数も含まれるべきようです.それは
KMeansクラスのメンバー関数はすべて揃っているようですが、メンバー変数はまだ説明されていません.
今まで、k平均クラスタリングの全体的な構造はすでにあって、次は彼らを組み合わせて(ここではpclライブラリを借りて、今までpclの中でまだK-meansアルゴリズムの機能がなかったため、ps:誰かがpclの中でk-meansアルゴリズムを見つけることができたら、必ず伝言を残して知らせてください.感謝に堪えません.pclを借りて、3次元の点群の読み取りと貯蔵の面倒を省くためだけです)
具体的な実装
まず、クラスタリング中心が移動するか否かを判断するバルブ値cosnt float DIST_を設定するNRAR=0.001、つまり2回のクラスタリング中心の差がこの値より小さい場合、クラスタリングは停止します.
上のコード:
インスタンス検出
k-meansとは、k平均クラスタリングである.クラスタリングの過程は中国の歴史上の「春秋五覇、戦国七雄」のようなもので、それらは同じ中国の大地に属し、同時に周王室に分封されている.分封の過程はKクラスの指定過程に相当し,各諸侯国は1つのクラスタリングに対応する.五覇は五類、七雄は七類、五覇から七雄まで、つまり一つのクラスターの成長過程に相当する.
数学的に言えば,N個のサンプルが集合Aを構成し,欧米式距離に応じてAをKサブセットに分割する必要があると仮定すると,サブセットを分割する過程がk平均クラスタリング実現の過程である.
簡単に言えば、物はクラスタで、人はクラスタで、数学でもそうです.
K平均はどのように実現されたのか
周王室が諸侯を分封するように、k平均クラスタリングも「いったいどれだけ諸侯を分封するのか」と告げられる必要がある.诸侯王たちが马鹿ではないことを考えると、土地が肥沃で+物产が豊富で+风调雨顺+がほしい...だから周王室はいっそ「ランダムに指定しましょう!」と切った.そこで、諸侯たちは封地に着いた後、もっと彼らの居住に適した場所を得るために、絶えず彼らの国都を変えて、絶えず周囲の群落を蚕食して、ある日まで、彼らはそれぞれ自分の理想の国に達したことを発見しました--彼らは無限の子民を持っていて、無数の子民が彼らの周辺を囲んで、彼らは広大な土地を持っていて、彼らは土地の中央に位置しています!結局、すべての諸侯王は首都を移さず、定住過程も終わった.
k平均値を類比して、以下の点をまとめます.
もちろん、アルゴリズムを実現するには、データ構造の設計が欠かせません.主に3 DデータのK平均に対して計算されるため、各サンプルは1つの構造体タイプとして宣言する必要があります.
typedef struct st_pointxyz
{
float x;
float y;
float z;
}st_pointxyz;
後続の計算を容易にするには、ポイントとそのポイントのインデックス番号を格納するための構造も設計する必要があります.
typedef struct st_point
{
st_pointxyz pnt;
int groupID;
st_point()
{
}
st_point(st_pointxyz &p,int id)
{
pnt =p;
groupID= id;
}
}st_point;
k平均アルゴリズムを実現する以上、
class KMeansを定義しましょう.classを定義する以上、その含むべき具体的な実装関数を考慮すべきである.まず、クラスタ数Kはもちろんのこと、定義
SetK().次に、入力出力を含めるべきだと思います.では、メンバー入力関数:SetInputCloud（）、出力関数:SaveFile（）を構築します.入出力を含め、クラスタリングプロセスの実装関数を含まなければならないのは当然で、Cluster（）と定義しておきましょう.次に、次のクラスタリングプロセスがどのように実現されるかを考えます.ああ、諸侯はランダムに分類されています.では、ランダム関数InitKcenter()を初期化します.次に、諸侯の移行は、クラスタリングセンターが絶えず変化する過程であり、クラスタリングセンターが更新された関数も含まれるべきようです.それは
UpdateGroupCenter（）と定義されています.思い出してみてください.彼らのクラスタリングの過程は2点のヨーロッパ式距離で実現されています.DisBetweenPoints()も少なくないようですが、ここまでクラスタリングプロセスがまだ終わっていないようです.クラスタリング計算を終了する「終了関数」をもう一つ与えなければなりません.諸侯王が定住したように、国は変わりません.k平均クラスタリングの中心は変わりません.クラスタリングプロセスの結束と考えることができます.それでは、中心点が移動しているかどうかを判断する関数ExistCenterShift（）を定義します.KMeansクラスのメンバー関数はすべて揃っているようですが、メンバー変数はまだ説明されていません.
int m_kはもちろん、typedef vector VecPoint_t (vectorでデータを格納する予定)の後に使用するコマンド別名を定義し、計算が必要な入力ポイントクラウドVecPoint_t mv_pntcloudを定義し、クラスタリング結果を保存する構造をvectorm_grp_pclcloud と定義する必要があります.最後に、各クラスタリングセンターvector m_center も知ります.今まで、k平均クラスタリングの全体的な構造はすでにあって、次は彼らを組み合わせて(ここではpclライブラリを借りて、今までpclの中でまだK-meansアルゴリズムの機能がなかったため、ps:誰かがpclの中でk-meansアルゴリズムを見つけることができたら、必ず伝言を残して知らせてください.感謝に堪えません.pclを借りて、3次元の点群の読み取りと貯蔵の面倒を省くためだけです)
class KMeans
{
public:
int m_k;
typedef vector VecPoint_t; //
VecPoint_t mv_pntcloud; //
vectorm_grp_pntcloud; //k ，
vectormv_center; //
KMeans()
{
m_k =0;
}
inline void SetK(int k_) //
{
m_k = k_;
m_grp_pntcloud.resize(m_k);
}
//
bool SetInputCloud(pcl::PointCloud<:pointxyz>::Ptr pPntCloud);
// k
bool InitKCenter();
//
bool Cluster();
// k ( )
vector UpdateGroupCenter(vector &grp_pntcloud,vector cer);
//
double DistBetweenPoints(st_pointxyz &p1,st_pointxyz &p2);
//
bool ExistCenterShift(vector &prev_center,vector &cur_center);
// pcd
bool SaveFile(const char *fname);
};
具体的な実装
まず、クラスタリング中心が移動するか否かを判断するバルブ値cosnt float DIST_を設定するNRAR=0.001、つまり2回のクラスタリング中心の差がこの値より小さい場合、クラスタリングは停止します.
上のコード:
bool KMeans::InitKCenter( )
{
mv_center.resize(m_k);
int size = mv_pntcloud.size();
srand(unsigned(time(NULL)));
for (int i =0; i< m_k;i++)
{
int seed = random()%(size+1);
mv_center[i].x = mv_pntcloud[seed].pnt.x;
mv_center[i].y = mv_pntcloud[seed].pnt.y;
mv_center[i].z = mv_pntcloud[seed].pnt.z;
}
return true;
}
bool KMeans::SetInputCloud(pcl::PointCloud<:pointxyz>::Ptr pPntCloud)
{
size_t pntCount = (size_t) pPntCloud->points.size();
for (size_t i = 0; i< pntCount;++i)
{
st_point point;
point.pnt.x = pPntCloud->points[i].x;
point.pnt.y = pPntCloud->points[i].y;
point.pnt.z = pPntCloud->points[i].z;
point.groupID = 0;
mv_pntcloud.push_back(point);
}
return true;
}
bool KMeans::Cluster()
{
InitKCenter();
vectorv_center(mv_center.size());
size_t pntCount = mv_pntcloud.size();
do
{
for (size_t i = 0;i < pntCount;++i)
{
double min_dist = DBL_MAX;
int pnt_grp = 0; //
for (size_t j =0;j 0.000001)
{
min_dist = dist;
pnt_grp = j;
}
}
m_grp_pntcloud[pnt_grp].push_back(st_point(mv_pntcloud[i].pnt,pnt_grp)); //
}
//
for (size_t i = 0; i KMeans::UpdateGroupCenter(std::vector &grp_pntcloud, std::vector center)
{
for (size_t i = 0; i < m_k; ++i)
{
float x = 0, y = 0, z = 0;
size_t pnt_num_in_grp = grp_pntcloud[i].size();
for (size_t j = 0; j < pnt_num_in_grp; ++j)
{
x += grp_pntcloud[i][j].pnt.x;
y += grp_pntcloud[i][j].pnt.y;
z += grp_pntcloud[i][j].pnt.z;
}
x /= pnt_num_in_grp;
y /= pnt_num_in_grp;
z /= pnt_num_in_grp;
center[i].x = x;
center[i].y = y;
center[i].z = z;
}
return center;
}
//
bool KMeans::ExistCenterShift(std::vector &prev_center, std::vector &cur_center)
{
for (size_t i = 0; i < m_k; ++i)
{
double dist = DistBetweenPoints(prev_center[i], cur_center[i]);
if (dist > DIST_NEAR_ZERO)
{
return true;
}
}
return false;
}
// pcd
bool KMeans::SaveFile(const char *prex_name)
{
for (int i = 0; i < m_k; ++i)
{
pcl::PointCloud<:pointxyz>::Ptr p_pnt_cloud(new pcl::PointCloud<:pointxyz> ());
for (size_t j = 0, grp_pnt_count = m_grp_pntcloud[i].size(); j < grp_pnt_count; ++j)
{
pcl::PointXYZ pt;
pt.x = m_grp_pntcloud[i][j].pnt.x;
pt.y = m_grp_pntcloud[i][j].pnt.y;
pt.z = m_grp_pntcloud[i][j].pnt.z;
p_pnt_cloud->points.push_back(pt);
}
p_pnt_cloud->width = (int)m_grp_pntcloud[i].size();
p_pnt_cloud->height = 1;
char newFileName[256] = {0};
char indexStr[16] = {0};
strcat(newFileName, szFileName);
strcat(newFileName, "-");
strcat(newFileName, prex_name);
strcat(newFileName, "-");
sprintf(indexStr, "%d", i + 1);
strcat(newFileName, indexStr);
strcat(newFileName, ".pcd");
pcl::io::savePCDFileASCII(newFileName, *p_pnt_cloud);
}
return true;
}
インスタンス検出