凸包多角形最小外接矩形アルゴリズム
7168 ワード
実は私はアルゴリズムに対してあまり上手ではありませんが、プロジェクトの中であるアルゴリズムを使ってある機能を実現し、無理に実現しなければなりません.これはずっと前の項目で、凸包多角形の最小外接矩形を計算します.このような状況に遭遇したのはきっと手の施しようがないに違いない.いくつかの資料をめくった後.やっと完成した.
まずプロジェクトについてお話しします.
このDesktopアプリは、外付けカメラに接続した後、カメラでグラフィックを捉え、計算することで何らかの機能を実現しています
例えば、私たちがappを作るとき、カメラを利用して銀行カードを識別し、OCRを通じてカードの数字を識別し、銀行カード番号を迅速に記入する目的を達成することができます.
例えば、銀行が顧客の身分証明書のコピーを必要とする場合、身分証明書をカメラの下に置いてマウスを押すだけで、電子ファイルのコピーを完成させ、スキャナーを捨てることができます.
例えば駐車場に駐車するとき、そのledディスプレイにナンバープレートがすばやく表示されます.これらはいずれもハイビジョンカメラにより顔像を捉え、一連の計算を行い、OCR認識により以下の図を行い、画像から緑色の円部分を取り出す.まず、画像を手に入れた後、画像の階調を落とす-->二値化-->エッジを探す-->最大のblobを得て、座標計算を通じて、最後に円の部分を切り取ることができます.
では、オブジェクトは複雑な図形ですね.例えば、三角形、五角星、不規則な多角形はどのように処理しますか.
いずれの画像も彼の最終的な形状が矩形である場合、不規則な多角形の最小外接矩形を計算し、角度を90°正すことで、所望の図形を得ることができる.
凸多角形の最小包囲矩形には、少なくとも1つのエッジが多角形の1つのエッジと共線している.
暴力アルゴリズム
各エッジ構造を巡って矩形を囲んで面積の大きさを比較します.長方形を囲み、投影点からエッジ、垂直エッジまでの距離を最も遠い2点の距離に取ればよい
かいてんゲージアルゴリズム
回転スケールアルゴリズムを使用すると、凸多角形を計算する最小包囲矩形の時間消費を大幅に削減できます.
座標上の両極値点を取って平行線を構成し、2線を回転させ、線が多角形の1辺と重なると、構成矩形面積を計算します.
90度を超えるまで回転を続けます.最小面積をとる.
このアルゴリズムは凸体にのみ有効である(暴力法は凸体凹体に対しても有効である)ため,凸体の計算過程に制限された時間複雑度の凸体を先に計算する必要がある.
四つ目のポイントを取ると、他のことは言いやすいので、本体から矩形を切り出し、90°に平行にすればOKです.
[完]
まずプロジェクトについてお話しします.
このDesktopアプリは、外付けカメラに接続した後、カメラでグラフィックを捉え、計算することで何らかの機能を実現しています
例えば、私たちがappを作るとき、カメラを利用して銀行カードを識別し、OCRを通じてカードの数字を識別し、銀行カード番号を迅速に記入する目的を達成することができます.
例えば、銀行が顧客の身分証明書のコピーを必要とする場合、身分証明書をカメラの下に置いてマウスを押すだけで、電子ファイルのコピーを完成させ、スキャナーを捨てることができます.
例えば駐車場に駐車するとき、そのledディスプレイにナンバープレートがすばやく表示されます.これらはいずれもハイビジョンカメラにより顔像を捉え、一連の計算を行い、OCR認識により以下の図を行い、画像から緑色の円部分を取り出す.まず、画像を手に入れた後、画像の階調を落とす-->二値化-->エッジを探す-->最大のblobを得て、座標計算を通じて、最後に円の部分を切り取ることができます.
では、オブジェクトは複雑な図形ですね.例えば、三角形、五角星、不規則な多角形はどのように処理しますか.
いずれの画像も彼の最終的な形状が矩形である場合、不規則な多角形の最小外接矩形を計算し、角度を90°正すことで、所望の図形を得ることができる.
凸多角形の最小包囲矩形には、少なくとも1つのエッジが多角形の1つのエッジと共線している.
暴力アルゴリズム
各エッジ構造を巡って矩形を囲んで面積の大きさを比較します.長方形を囲み、投影点からエッジ、垂直エッジまでの距離を最も遠い2点の距離に取ればよい
/* min value */
#define FLT_MIN 1.175494351e-38F
/* max value */
#define FLT_MAX 3.402823466e+38F
struct OBB {
Point u[2]; //x, y
Point c; //
float e[2]; // ，
};
float MinAreaRec(Point *pts, int ptsNum, OBB &obb) {
float minArea = FLT_MAX;
for(int i = 0, j = ptsNum - 1; i < ptsNum; j = i, i++) {//
Point u0 = pts[i] - pts[j];//
u0 = u0/Length(u0);
Point u1 = Point(0-u0.y, u0.x);// u0
float min0 = 0.0f, max0 = 0.0f, min1 = 0.0f, max1 = 0.0f;
for(int k = 0; k < ptsNum; k++) {//
Point d = pts[k] - pts[j];
// u0
float dot = Dot(d, u0);
if(dot < min0) min0 = dot;
if(dot > max0) max0 = dot;
// u1
dot = Dot(d,u1);
if(dot < min1) min1 = dot;
if(dot > max1) max1 = dot;
}
float area = (max0 - min0) * (max1 - min1);
if( area < minArea ) {
minArea = area;
obb.c = pts[j] + ( u0 * (max0 + min0) + u1 * (max1 + min1) )*0.5f;
obb.u[0] = u0;
obb.u[1] = u1;
obb.e[0] = (max0 - min0)*0.5f;
obb.e[1] = (max1 - min1)*0.5f;
}
}
return minArea;
}
Point * GetOBBPoints(OBB obb) {// OBB
Point *pts = new Point [4];
pts[0] = obb.c + ( obb.u[0] * obb.e[0] + obb.u[1] * obb.e[1] );
pts[1] = obb.c + ( obb.u[0] * obb.e[0] - obb.u[1] * obb.e[1] );
pts[2] = obb.c - ( obb.u[0] * obb.e[0] + obb.u[1] * obb.e[1] );
pts[3] = obb.c + ( obb.u[1] * obb.e[1] - obb.u[0] * obb.e[0] );
return pts;
}かいてんゲージアルゴリズム
回転スケールアルゴリズムを使用すると、凸多角形を計算する最小包囲矩形の時間消費を大幅に削減できます.
座標上の両極値点を取って平行線を構成し、2線を回転させ、線が多角形の1辺と重なると、構成矩形面積を計算します.
90度を超えるまで回転を続けます.最小面積をとる.
このアルゴリズムは凸体にのみ有効である(暴力法は凸体凹体に対しても有効である)ため,凸体の計算過程に制限された時間複雑度の凸体を先に計算する必要がある.
float Cos(Point v, Point p1) {
float dot = Dot(v,p1);
float cos = dot/(Length(v)*Length(p1));
return cos;
}
void Setu0u1(Point e, Point &u0, Point &u1) {
// e x ， xy
u0 = e / Length(e);
u1 = Point( 0 - u0.y, u0.x);
}
int GetMinAngleIndex(int imin1, int imax0, int imax1, int imin0,
Point* e, Point u0, Point u1) {
// （cos ）
int imin_angle_index = 0;
float cos = 0, maxCos = FLT_MIN;
cos = Cos(e[imin1], u0);
if(cos > maxCos){maxCos = cos; imin_angle_index = imin1;}
cos = Cos(e[imax0], u1);
if(cos > maxCos){maxCos = cos; imin_angle_index = imax0;}
cos = Cos(e[imax1], Point(0-u0.x,0-u0.y));
if(cos > maxCos){maxCos = cos; imin_angle_index = imax1;}
cos = Cos(e[imin0], Point(0-u1.x,0-u1.y));
if(cos > maxCos){maxCos = cos; imin_angle_index = imin0;}
return imin_angle_index;
}
void SetMinMax(Point*pts, int i, int iu, Point u0, Point u1,
float &max0, float &min0, float &max1,
int & new_imax0, int &new_imin0, int &new_imax1)
{
// x ，y （y ， 0）
// pts
Point d = pts[i] - pts[iu];
float dist0 = Dot( d, u0);
if(dist0 > max0){ max0 = dist0; new_imax0 = i;}
if(dist0 < min0){ min0 = dist0; new_imin0 = i;}
float dist1 = Dot( d, u1);
if(dist1 > max1){ max1 = dist1; new_imax1 = i;}
}
float MinAreaRec2(Point *pts, int ptsNum, OBB &obb) {//
//
float minArea = FLT_MAX;
// e
Point *e = new Point[ ptsNum ];
for(int i = 0; i < ptsNum; i++) {
e[i] = pts[(i+1)%ptsNum] - pts[i];
}
int iu = 0;// e[0]
// u0 u1
Point u0,u1;
Setu0u1(e[iu], u0, u1);
int imax0 = 0, imax1 = 0, imin0 = 0, imin1 = 0;
float min0 = FLT_MAX, max0 = FLT_MIN,
max1 = FLT_MIN, min1 = 0;//min1 ， 0
//
// min1 0
//
for( int i = 0; i < ptsNum; i++) {
SetMinMax(pts, i, iu, u0, u1,
max0, min0, max1,
imax0, imin0, imax1) ;
}
for(int i = 0; i < ptsNum ; i++) {
int iminangle = 0;
iminangle = GetMinAngleIndex((iu+1)%ptsNum, imax0, imax1, imin0, e, u0, u1);
if(iminangle == 0)break;//
if(iminangle == imax0){imax0 = (iu + 1)%ptsNum;iu = iminangle;}
else if(iminangle == imax1){imax1 = (iu + 1)%ptsNum;iu = iminangle;}
else if(iminangle == imin0){imin0 = (iu + 1)%ptsNum;iu = iminangle;}
else if(iminangle == (iu+1)%ptsNum){iu = (iu+1)%ptsNum;}
Setu0u1(e[iu], u0, u1);// u0u1
//
int new_imax0 = imax0, new_imax1 = imax1, new_imin0 = imin0;
min0 =FLT_MAX, max0 = FLT_MIN, max1 = FLT_MIN;
// imax0
SetMinMax(pts, imax0, iu, u0, u1,
max0, min0, max1,
new_imax0, new_imin0, new_imax1) ;
// imax1
SetMinMax(pts, imax1, iu, u0, u1,
max0, min0, max1,
new_imax0, new_imin0, new_imax1) ;
// imin0
SetMinMax(pts, imin0, iu, u0, u1,
max0, min0, max1,
new_imax0, new_imin0, new_imax1) ;
imax0 = new_imax0;
imax1 = new_imax1;
imin0 = new_imin0;
//
// obb
float area = (max0 - min0)*(max1 - min1);
if(area < minArea) {
minArea = area;
obb.e[0] = (max0 - min0)*0.5f;
obb.e[1] = (max1 - min1)*0.5f;
obb.u[0] = u0;
obb.u[1] = u1;
obb.c = pts[iu] + ( u0 * (max0 + min0) + u1 * (max1 + min1) )*0.5f;
}
}
return minArea;
}四つ目のポイントを取ると、他のことは言いやすいので、本体から矩形を切り出し、90°に平行にすればOKです.
[完]