단순 다각형(simple polygon)의 삼각화 알고리즘의 다른 구현이다. 이전 구현과 같은 Ear-Clipping 알고리즘을 써서 구현한 것이다. 폴리곤의 각 꼭짓점을 돌면서 현재 꼭짓점의 직전과 직후의 꼭짓점들로 구성한 삼각형이 Ear인가를 체크해서 맞으면 이 삼각형을 추가하고, 현 꼭짓점은 주어진 폴리곤에서 제거를 한 후 나머지에 대해 테스트를 계속한다. $N$ 개의 꼭짓점을 가지는 단순 폴리곤의 경우에 $N-2$ 개의 삼각형으로 분해가 된다.

주어진 폴리곤이 시계방향으로 정렬된 경우는 반시계 방향으로 바꾸어서 정렬시킨 후 작업을 한다. 구현된 알고리즘의 복잡도는 ${\cal O}(N^2)$이다. 

last update: 2012.10.03;

static 
bool leftSide(const CPoint &P, const CPoint &A, const CPoint &B) {
    // P가 선분(A,B)의 왼쪽 또는 위에 있는가?
    return ((B.x-A.x)*(P.y-A.y) - (B.y-A.y)*(P.x-A.x)) >= 0;
}
static 
bool insideTriangle(const CPoint &P, const CPoint &A, const CPoint &B, const CPoint &C) {
    // 반시계방향으로 정렬된 삼각형(A,B,C)의 안에 점 P가 있는가?(경계포함);
    if (!leftSide(P, A, B)) return false;
    if (!leftSide(P, B, C)) return false;
    if (!leftSide(P, C, A)) return false;
    return true;
};
static 
int polygonArea2(const std::vector<CPoint> &pts) {
    double area2 = 0;
    for (int p = pts.size() - 1, q = 0; q < pts.size(); p = q++)
        area2 += pts[p].x * pts[q].y - pts[p].y * pts[q].x;
    return area2;
}
static 
bool earTest(int a, int b, int c, 
             int nv, const std::vector<int> &V, 
             const std::vector<CPoint> &pts) 
{
    // Check the triangle {V[a], V[b], V[c]} is an Ear; 
    const CPoint &A  = pts[V[a]]; 
    const CPoint &B  = pts[V[b]]; 
    const CPoint &C  = pts[V[c]]; 
    // colinear(A->B->C) or concave인가를 체크; 반시계 방향으로 정렬된 입력점이므로 왼편에
    // 있으면 concave이므로 ear가 안된다;
    if (leftSide(B, A, C)) return false; 
    // 이미 만들어진 삼각형의 꼭지점이 포함되는지 체크한다;
    for (int k = 0; k < nv; ++k) {
        if ((k == a) || (k == b) || (k == c)) continue;
        if (insideTriangle(pts[V[k]], A, B, C)) return false;
    }
    return true;
};
/* Polygon should be simple(ccw or cw);*/
std::vector<Triple> polygonTriangulation(const std::vector<CPoint>& pts) {
    if (pts.size() < 3) return std::vector<Triple> (); //null_vec;
    std::vector<int> V(pts.size());  // contains vertex indices;
    // 주어진 단순폴리곤을 ccw-ordering;
    if (polygonArea2(pts) > 0)
        for (int v = pts.size(); v-- > 0;) V[v] = v;
    else 
        for (int v = pts.size(), k = 0; v-- > 0;) V[v] = k++;
        
    std::vector<Triple> triples;
    triples.reserve(pts.size() - 2);
    // (pts.size()-2)개 꼭지점을 차례로 제거한다. 
    // 꼭지점이 제거될때마다 삼각형이 하나씩 생긴다;    
    int nv = pts.size();
    int err_detect = 2 * nv;   /* error detection */
    for (int v = nv - 1; nv > 2;  ) {
        // 단순폴리곤이 아닌 경우에 무한루프를 도는 것을 방지;
        if (0 >= err_detect--) {
            TRACE("ERROR::non-simple polygon\n");
            return std::vector<Triple> ();
        }
        // <u,v,w>는 연속하는 세 꼭지점의 인덱스임;
        int u = v % nv; 
        v = (u + 1) % nv;
        int w = (v + 1) % nv;
        if (earTest(u, v, w, nv, V, pts)) { 
            triples.push_back(Triple(V[u], V[v], V[w]));  
            // 꼭지점 V[v]를 제거함;
            for (int k = v, j = k + 1; j < nv;) V[k++] = V[j++];
            /* resest error detection counter */
            err_detect = 2 * (--nv);
        }
    }
    return triples;
}

최적화 후:

728x90

'Computational Geometry' 카테고리의 다른 글

Wu's Line Algorithm  (1) 2008.06.02
Brute Force Triangulation  (1) 2008.05.28
Polygon Triangulation  (4) 2008.05.25
Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
,

구현 code:  http://kipl.tistory.com/13

Polygon의 내부를 겹치지 않게 삼각형으로 분할하는 것을 polygon의 삼각화라고 한다. $N$개의 꼭짓점이 있는  simple polygon의 경우 처음 세 꼭짓점이 만드는 삼각형이 생성된 후 꼭짓점을 하나씩 추가할 때마다 삼각형도 하나씩 늘어난다. 따라서 simple polygon 내부에는 $N-2$개의 서로 겹치지 않은 삼각형으로 분할이 되고 polygon의 경계와 겹치지 않는 $N-3$개의 내부 경계 라인을(diagonal)을 가지게 된다. 

사용자 삽입 이미지


분할 삼각형의 외접원 반지름에 차이가 많이 나는 경우 삼각형들의 면적에 편차가 심하게 된다. 좀 더 균일한 면적을 가지는 삼각형으로 분할하기 위해서는 인접하는 두 삼각형으로 만들어지는 사변형에서 현재 대각 변에 교차하는 대각 변으로 재분할을 시도해 본다. 새로이 만들어지는 두 삼각형을 검사하여 이전보다 면적이 균일하면 이 분할을 사용하면 된다. 물론 삼각형의 외접원의 반경이 작을 때는 거의 균일한 분할을 얻을 수 있다. Polygon Optimizing을 참고하기 바란다.

*simple polygon이 아닌 경우는 아래의 링크를 참조하기 바란다.

1). O(n log(n)) 복잡도를 갖는 polygon triangulation algorithm;
==> 'Fast Polygon Triangulation based on Seidel's Algorithm'.
==> http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

2). Poly2Tri 홈페이지:
==> Fast and Robust Simple Polygon Triangulation With/Without Holes by Sweep Line Algorithm
==> http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html

 

 

triangulation notes: (몇 개의 사이트는 없어졌다).
Nice lecture notes:
http://arachne.ics.uci.edu/~eppstein/junkyard/godfried.toussaint.html
▶ Narkhede & Manocha's description/code of Seidel's alg:
http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
▶ Some school project notes w/ triangulation overview & diagrams:
http://www.mema.ucl.ac.be/~wu/FSA2716-2002/project.html
▶ Toussaint paper about sleeve-following, including interesting
description & opinion on various other algorithms:
http://citeseer.ist.psu.edu/toussaint91efficient.html
▶ Toussaint outline & links:
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
http://geometryalgorithms.com/algorithms.htm
▶ History Of Triangulation Algorithms
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Thierry/thierry507webprj/complexity.html
▶ Ear Cutting For Simple Polygons
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian//cutting_ears.html
▶ Intersections for a set of 2D segments
http://geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm
▶ Simple Polygon Triangulation
http://cgafaq.info/wiki/Simple_Polygon_Triangulation
▶ KKT O(n log log n) algo
http://portal.acm.org/citation.cfm?id=150693&dl=ACM&coll=portal&CFID=11111111&CFTOKEN=2222222
▶ Poly2Tri implemenation, good notes and looks like good code, sadly the
license is non-commercial only:(최근에 사이트가 존재하지 않음)
http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html
▶ FIST
http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html
▶ Nice slides on monotone subdivision & triangulation:
http://www.cs.ucsb.edu/~suri/cs235/Triangulation.pdf

▶ Interesting forum post re monotone subdivision in Amanith:
http://www.amanith.org/forum/viewtopic.php?pid=43
 

728x90

'Computational Geometry' 카테고리의 다른 글

Brute Force Triangulation  (1) 2008.05.28
Polygon Triangulation (II)  (0) 2008.05.26
Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
,

RANSAC Algorithm

Image Recognition 2008. 5. 24. 09:02

어떤 현상을 설명하는 이론 모델을 만들려면 현상에서 관측 데이터를 모아야 한다. 그런데 관측 데이터에는 모델에 대한 잘못된 가정이나 측정의 오차 등에서 생기는 여러 가지 형태의 노이즈가 들어 있게 마련이다. 이러한 노이즈는 모델을 정확히 예측하는 것을 방해한다. 모델 파라미터의 예측을 방해하는 데이터(outliners)가 들어 있는 관측 데이터로부터 어떻게 하면 모델을 구축할 수 있는가라는 질문에 대한 한 해결책을 RANSAC("RANdom SAmple Consensus") 알고리즘이 제공한다. 이 알고리즘은 1981년 Fischler과 Bolles에 의해서 제안되었다.

RANSAC 알고리즘에 들어가는 입력은 관측된 데이터, 관측 결과를 피팅하거나 설명할 수 있는 모델 파라미터, 그리고 신뢰성을 나타내는 파라미터를 필요로 한다.

RANSAC 알고리즘은 주어진 원본 데이터에서 일부를 임의로 선택하는 과정을 반복하여서 최적의 파라미터를 예측하는 프러시저의 형태를 가진다. 전체의 관측 데이터가 M개 있고, 모델 파라미터를 예측하는데 N개의 데이터가 필요한 경우, 알고리즘의 동작은

     1. 임의로 관측 데이터에서 N개의 부분 데이터를 선택한다.
     2. 선택 데이터를 (가상의) inlier로 생각하고 모델을 예측한다.
     3. 원본 데이터(M) 중에서 예측된 모델에 잘 맞는가를 체크한다. 잘 맞는 데이터 수를 K라고 한다.
     4. 만약에 K가 충분하면, 이 모델을 확정하고 알고리즘을 종료한다.
     5. 모델이 좋지 않으면 14 과정을  L번 반복한다.
     6. 충분한 반복 후에도 좋은 모델을 찾지 못하면 예측에 실패한 것으로 간주한다.

1. 임계값 K는 주어진 전체 데이터 중에서 어느 정도의 비율로 찾는 모델에 잘 맞는가로 판단하는 기준인데, 사용자가 결정해야 한다. 대략적으로 주어진 샘플에서 inlier의 비율을 Pg정도라고 생각되면 다음 정도로 잡으면 된다:

 
   K = M * (1- P
g)

2. 얼마나 많은 반복을 해야하는가? 주어진 관측 데이터에서 inlier일 확률이 Pg인 경우에 L번의 모델 예측 시도가 실패할 확률을 계산하여서 이것이 주어진 설정값, pfail 보다도 작은 경우에 모델 예측의 실패로 처리하므로,

  pfail   = L번의 모델예측 실패 확률
          = (한 번 시도가 실패할 확률)L
          = (1 - 한 번 시도가 성공할 확률))L
          = (1 - (랜덤 데이터가 모델을 예측할 확률)N))L
          = (1- (Pg) N)L

이 사실로부터 최대 반복 횟수는 
    
   L = log(pfail)/log(1-(Pg)N)

로 주어진다.
inlier가 반이 섞인 경우 Pg (=주어진 데이터중에서 inlier일 확률) = 0.5,
pfail = 0.01 인 경우, N = 3 (세 점만 있으면 모델 구성이 가능한 원의 피팅이 한 예)이면 최대 반복 횟수는 윗 식에 적용하면,
     
                   L = 35 회

RANSAC 알고리즘은 주어진 관측 데이터에 많은 outlier가 존재하더라도 매우 정확히 모델 파라미터를 예측할 수 있는 능력이 있는 robust 한 알고리즘이지만, 얼마나 많은 반복을 해야 하는가에 대한 상한 값이 제공되지 않는다(사용자가 pfail 를 설정한다). 따라서 사용자 설정에 의한 상한 값은 최적의 모델이 아닐 수 있다.

"The RANSAC procedure is opposite to that of conventional smoothing techniques: Rather than using as much of the data as possible to obtain an initial solution and then attempting to eliminate the invalid data points, RANSAC uses as small an initial data set as feasible and enlarges this set with consistent data when possible".

Martin A. Fischler and Robert C. Bolles (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography". Comm. of the ACM 24: 381–395.

예제 코드:
ransac을 이용한 라인 피팅: http://blog.naver.com/helloktk/80029006029
ransac을 이용한 원 피팅: http://kipl.tistory.com/32

 

RANSAC: Circle Fit

RANSAC 알고리즘을 써서 주어진 2차원 점집합에서 원을 추정한다. 원을 만들기 위해서는 최소한 3점이 필요하고, 또 일직선에 있지 않아야 한다. 이렇게 만들어진 원은 세 점을 꼭짓점으로 하는

kipl.tistory.com

ransac을 이용한 타원 피팅: kipl.tistory.com/110

 

RANSAC Ellipse Fitting

타원은 원뿔을 평면으로 잘랐을 때 생기는 곡선 중의 하나로 다음 이차 형식(quadratic form)으로 표현된다. . 이 이차 형식의 계수를 구하기 위해서는 타원 위의 5개의 서로 다른 점이 필요하다 $(a

kipl.tistory.com

 

728x90

'Image Recognition' 카테고리의 다른 글

Gaussian Mixture Model  (2) 2008.06.07
Rasterizing Voronoi Diagram  (0) 2008.05.26
Contour Tracing  (0) 2008.05.22
Gausssian Scale Space  (0) 2008.05.22
Watershed Algorithm 적용의 예  (2) 2008.05.21
,