728x90

 

Posted by helloktk

댓글을 달아 주세요

  1. hgmhc 2020.12.30 15:14 신고  댓글주소  수정/삭제  댓글쓰기

    원리도 알려주시면 감사하겠습니다!

728x90

실행화일.zip
다운로드

마우스 클릭으로 생긴 이미지 상의 입력 점을 가지고 triangulation을 한 후에 각각의 삼각형 내의 영역을 그 영역의 평균 컬러 값으로 채우는 효과이다. voronoi 다이어그램을 이용해서 tiling 하는 효과와 유사하다.

그림: Lena사진(일부)을 이용한 예:

사용 algorithm
  - incremental delaunay triangulation;
  - polygon fill;



Voronoi Tiling:

 

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

한 점에서 선분까지 거리  (1) 2010.01.16
삼각형 채우기  (0) 2009.12.19
Triangulation을 이용한 Imge Effect  (0) 2009.12.18
Ellipse Drawing Algorithm  (0) 2008.06.04
Circle Drawing Algorithm  (1) 2008.06.03
Wu's Line Algorithm  (1) 2008.06.02
Posted by helloktk

댓글을 달아 주세요

728x90

주어진 점집합에서 세 점을 뽑아서 만든 삼각형의 외접원에 다른 점이 하나도 포함하지 않으면 triangulation의 기본 삼각형 cell이 된다. 주어진 점으로 만들 수 있는 삼각형의 총개수가 ${}_nC_3$ 이므로, 기본 삼각형을 찾기 위해서는 이들 각각의 삼각형에 대서 나머지 점을 가지고 incircle 테스트를 수행해야 한다. 따라서 이 알고리즘은 ${\cal O}(n^4)$의 스텝이 필요하게 된다.

/*brute force attack*/
foreach point p1
      foreach point p2 
             foreach point p3
                   foreach point p4 
                          if(incircle(p1,p2,p3,p4))
                                 iscell=false;
                                 break ;
                   endfor;
                   if(iscell) 
                           add(triangle(p1,p2,p3));
              endfor;
       endfor;
endfor;

세 점에 의해서 형성이 되는 외접원은 대수적으로 쉽게 구할 수 있다. 여기서는 좀 더 기하학적인 접근을 쓰면, 평면의 점은 

$$(x, y)\rightarrow (x, y, z=x^2 + y^2)$$

의 mapping에 의해서 3차원 paraboloid 곡면의 점으로 옮길 수 있다. paraboloid 위의 세 점이 형성하는 3차원에서 평면이 paraboloid를 절단하는 곡선을 $x-y$ 평면으로 정사영하면 원이 된다는 것을 쉽게 알 수 있다.(incircle 포스팅 참조). 따라서 주어진 점이 세 점의 외접원에 포함되는가를 테스트하는 작업은 이 점을 paraboloid로 올렸을 때의 점과 (paraboloid로 올려진) 외접원의 3점이 형성하는 3차에서의 평면과 관계를 조사하는 것으로 바꿀 수 있다.

주어진 점이 외접원에 포함되면 paraboloid로 변환된 점은 평면의 아래에 놓이고, 외접원 밖의 점이면 평면 위에 놓이게 된다. 물론 외접원 위의 점은 평면에 놓인다. 따라서 평면의 법선 벡터 구하고, 삼각형의 한 꼭짓점을 기준한 주어진 점의 변위 벡터와 내적을 구하면 내적의 값은 평면 위인지, 아래인지 또는 평면에 놓인 점인가에 따라서 부호가 달라진다. 평면의 수직 벡터를 고정하면(예제는 아래 방향: $n_z < 0$), 평면 위에 놓인 점과의 내적은 음수, 평면 아래에 놓인 점과의 내적은 양수가 되고, 평면의 점과의 내적은 0이다. 

주어진 세 점이 만드는 외접원 내부(and 경계)에 들어가는 점이 없으면 이 삼각형을 선택한다.

** 참고 : Computational Geometry in C(2nd Edition) by Joseph O'Rourke

// input  x[0], x[1],....,x[n-1],
// input  y[0], y[1],....,y[n-1];
// calculate z[0]=x[0]^2+y[0]^2, z[1]=x[1]^2+y[1]^2,...;
int dt4(int n, double x[], double y[]) {
    double *z = new double [n] ;
    for(int i = 0; i < n; i++) 
        z[i] = x[i] * x[i] + y[i] * y[i] ;

    int ntri = 0;
    /* For each triple (i,j,k) */
    for (int i = 0; i < n - 2; i++ )
        for (int j = i + 1; j < n; j++ )
            for (int k = i + 1; k < n; k++ )
                if ( j != k ) {
                    /* Compute normal to triangle (i,j,k)::  outter_product(j-i, k-i)*/
                    double nx = (y[j] - y[i]) * (z[k] - z[i]) - (y[k] - y[i]) * (z[j] - z[i]); 
                    double ny = (x[k] - x[i]) * (z[j] - z[i]) - (x[j] - x[i]) * (z[k] - z[i]);
                    double nz = (x[j] - x[i]) * (y[k] - y[i]) - (x[k] - x[i]) * (y[j] - y[i]);
                    
                    /* Only examine faces on bottom of paraboloid: nz < 0. */
                    int flag = (nz < 0);
                    if (flag) {
                        /* For each other point m */
                        for (int m = 0; m < n; m++) {
                            /* Check if m above (i,j,k)::i점을 기준으로 m 과 
                            ** normal 간의 내적으로 체크(내적이 양수이면 
                            ** m이 원의 내부에 완전히 들어 있는 경우가 된다. 
                            ** 0인 경우는 원주상에 놓인 경우이므로 배제한다
                            */
                            flag &= ((x[m]-x[i])*nx + (y[m]-y[i])*ny + (z[m]-z[i])*nz <= 0);
                        }
                    }
                    if (flag) {
                        ntri++;
                        // (i, j, k)의 외접원이 다른 점을 포함하지 않으므로 이 삼각형은 
                        // 삼각분할의 한 면을 형성하게 된다.
                        // addTriangle(tri(i, j, k));
                    }
                }
    delete[] z ;
    return ntri;
}

사용자 삽입 이미지

 

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

Circle Drawing Algorithm  (1) 2008.06.03
Wu's Line Algorithm  (1) 2008.06.02
Brute Force Triangulation  (1) 2008.05.28
Polygon Triangulation (II)  (0) 2008.05.26
Polygon Triangulation  (4) 2008.05.25
Polygon Fill  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요

  1. hgmhc 2020.12.30 15:18 신고  댓글주소  수정/삭제  댓글쓰기

    계속 보게 되네요 ㅋㅋ

728x90

이미지에서 Voronoi diagram으로 영역을 분할할 때 각 픽셀이 어느 Voronoi cell에 포함되는가를 알아야 하는 경우가 있다. 보통은 Voronoi 다이어그램으로 구한 cell을 폴리곤으로 표현하고, 해당 픽셀이 어느 폴리곤에 들어가는 가는 체크 해야 한다. 그러나, 이 과정은 복잡하고 계산이 많이 발생한다. 이미지에 만들어진 Voronoi diagram의 경우 cell mask를 이용하면 해당 픽셀이 어느 cell에 들어있는지를 바로 판단할 수 있다. 특히, cell의 개수가 적은 경우 mask를 gray 이미지로 처리할 수 있어서 메모리 사용도 줄일 수 있다.

Voronoi diagram의 이미지화 과정은 Voronoi 알고리즘을 이용할 필요는 없고 단지 각 cell을 형성하는 픽셀들은 그 cell의 중심까지 거리가 다른 cell보다 가깝다는 사실만 이용한다.

void rasterize_voronoi(POINT vorocenter [], int N, BYTE *image, int width, int height) {
    // RGB 컬러이미지이므로 image는 적어도 (3 * width * height) 크기의 버퍼를 가져야 한다.
    // make color lookup table;
    DWORD *color = new DWORD [N]; //RGBQUAD;
    // 랜덤 컬러 LUT;
    for (int i = 0; i < N; i++) 
        color[i] = (rand() % 256) << 16 | (rand() % 256) << 8 | (rand() % 256);
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            int min_id = 0; 
            int dist2_min = INT_MAX; //caution overflow;
            for (int k = 0; k < N; k++) {
                int dx = x - vorocenter[k].x;
                int dy = y - vorocenter[k].y;
                int ds2 = dx * dx + dy * dy;
                if (ds2 < dist2_min) {
                    dist2_min = ds2;
                    min_id = k;
                }
            }
            // set pixel value(here,we use RGB-color) wih verocenter[i]'s id
            *image++ = (color[min_id] >> 16) & 0xFF;   //B;
            *image++ = (color[min_id] >> 8)  & 0xFF;   //G;
            *image++ = (color[min_id])       & 0xFF;   //R;
        }
    };
    // draw cell center;
    delete[] color ;
};

사용자 삽입 이미지

 

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

EM Algorithm: Line Fitting 예  (0) 2008.06.29
Gaussian Mixture Model  (2) 2008.06.07
Rasterizing Voronoi Diagram  (0) 2008.05.26
RANSAC Algorithm  (0) 2008.05.24
Contour Tracing  (0) 2008.05.22
Gausssian Scale Space  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요

728x90

 

 

Fortune2.zip
다운로드
사용자 삽입 이미지

 

 

사용자 삽입 이미지

 

평면에서 보로노이 다이어그램을 계산하는 알고리즘 중에 1980년대에 Fortune에 의해서 발견이 된 Sweep line 알고리즘에 대해서 살펴보겠다. 이 알고리즘은 보로노이 다이어그램 계산문제의 optimal 한 답 중에 하나이다(~O(n * log(n)). Fortune이 자신의 알고리즘을 직접 C로 구현한 것이 있는데 이것은 웹상에서 쉽게 구할 수 있다. 그러나 알고리즘의 얼개는 간단하나 구현에 들어간 자료구조 등을 간단히 않아서 코드를 이해하는 것이 쉽지 않았다(이에 비하면 incremental delaunay triangulation은 매우 단순하다). 몇 번을 간단한 자료구조를 이용해서 재 작성을 해보려고 했는데 잘 되지 않았다. 인터넷에서 구할 수 있는 다양한 구현 소스를 분석해 보았으나 쉬운 것을 찾기가 힘들었다(triangle.c에서도 구현되어 있고, 자바로도 구현이 된 것을 찾을 수 있다.) 원래의 목적은 Fortune의 코드가 메모리 처리를 잘못하여 메모리 leak이 발생하여서 이 문제를 해결하려고 시도한 것인데, 메모리 문제는 자바의 경우에 처럼 가비지 콜렉터를 만들어서 처리할 수는 있다. 이 알고리즘의 구현에 들어가는 기본적인 자료구조는 priority queue와 balanced binary tree이다. 이들의 기본적인 구현은 이미 잘 알려져 있으므로 이것들을 직접적으로 알고리즘에 적용하는 문제만 남는다. balanced binary tree로 만들어진 자료구조를 쓰면 자료를 찾는 시간이 O(log(n))의 시간 복잡도를 주지만, 이것이 알고리즘을 직관적으로 보는 것을 방해하므로 여기서는 이중 연결 리스트를 이용하도록 한다. 전체적으로 알고리즘은 O(n^2)의 복잡도를 가진다.

1. priority queue 구성: 주어진 입력점들을 가지고 구성한다. 알고리즘 중간에 세 점으로 원이 구성이 되는 circle event가 생성이 되는데 이것은 따로 event 큐를 구성한다. event의 우선순위는  x 좌표의 순서에 의해서 구성하고 동일한 x 좌표값에 대해서는 y값이 작은 순서대로 구성한다(compare 구조체에서 point와 event에 대한 비교 연산자를 정의한다).

std::priority_queue <point, std::vector <point>, compare> points ; // 입력점(point-구조체)들로
                                                                   // 만들어지는 priority_queue;
std::priority_queue <event*, std::vector <event*>, compare> events;//circle events(event-구조체);

2. site event 처리: sweep line(x=const)은 전체 평면을 반으로 나누는 역할을 한다. 알고리즘은 sweep 라인이 쓸고 지나간 영역에서만 관심 영역이다. sweep라인과 주어진 점은 하나의 포물선을 정의할 수 있다(주어짐 점이 포물선의 초점을 구성함). 따라서 sweep 라인이 진행하면 sweep line의 왼편의 입력점들은 각각 하나의 포물선을 형성하고, 이 포물선들의 구간 중에서 sweep라인에 가장 가까운 부분은 포물선 arc로 연결인 되는 하나의 beach line을 형성한다.  sweep라인이 새로운 입력점을 지나면 여기서 새로운 포물선 arc가 생기는데, 이것은 이미 만들어진 beach라인을 구성하는 포물선 arc 중 하나를 둘로 가르고, 그 자신이 새로운 beach 라인의 일부를 구성하게 된다; sweep라인이 전진하면서 비치라인을 구성하는 arc가 다른 arc에 파 묻혀서 없어지는 경우가 생긴다. 이 경우가 circle event가 만들어지는 시점이다.

.......................

*           BEFORE                                  AFTER
*
*           new point                               new arc
*               |                                       |
*     __        |       _____                   __      |       _____
*       \      \|/        |                       \    \|/       arc a
*        \      `         |                        \    `       __|__
*         \     X         |                         p------X    __|__<-- arc c
*      a   |             arc a                  a    |            |
*         /               |                         /            arc a
*        /                |                        /              |
*      /__              __|__                     /__           __|__
*   __/    \              |                    __/   \            |
*           \             |                           \           |
*            \            |                            \          |
*       b     |          arc b                  b       |        arc b
*            /            |                            /          |
*           /             |                           /           |
*        __/            __|__                      __/          __|__

 

3. circle event 처리; sweep라인이 각각의 site에 도달하면 새로운 포물선의 arc가 비치라인에 추가가 되는데 sweep 라인으로부터 멀어진 arc들은 어느 시점에서 없어져야 한다. 이것은 인접하는 세 개의 arc들의 교점이 현재의 sweepline 위치에서 하나로 만들어져서 중앙의 arc가 없어지는 경우로 이것을 circle event라고 한다. 이때 만들어지는 교점은 보로노이 에지의 꼭짓점을 구성하게 된다. circle event에서는 나머지 두 개의 남은 arc의 교점이 trace 하는 새로운 에지가 생기게 된다.

*    __
*       \
*   a    \
*         \
*   __     |
*     `   /
*      \ /
*   b   X           <-- Arc b is overtaken at point X (this is a circle center)
*     / \
*   __,   \
*          \
*           \
*   c        |
*           /
*          /
*         /

*
*       BEFORE                                              AFTER
*
*      \        arc a                                   \
*        \                                               \              a.s0
*         \   <-- a.s0                                    \               |
*          \                                               \             \|/
*           \                                               \             `
*            \                                               \
*    arc b   X     <-- termination point                      .--------------------<-- new segment
*           /                                                /          
*          /                                                /            .
*         /   <-- c.s1                                     /            /|\ 
*        /                                                /              |
*       /    arc c                                       /              c.s1
*      /      

                                 

//포물선 arc를 정의하기 위한 클래스;

struct arc {
    point p;                //focus of parabola;
    arc *prev, *next;       //double linked-list;
    event *e;
    ////////////////////////////////////////////////////
    seg *s0 ;               //edge of voronoi starting from break point;
    seg *s1;                //edge of voronoi starting from break point;
    arc(point _p, arc *_a=0, arc *_b=0)
        : p(_p), prev(_a), next(_b), e(0), s0(0), s1(0) {}
};

// voronoi edge를 정의하는 segment class;
struct seg {
    point start, end;                           //defines segment;
    bool done;
    int ref ;                                   //referece count in order to distingush the double edges;
    seg(point _p, int _ref=0)
        : start(_p), end(0,0), done(false), ref(_ref)
    { output.push_back(this); }                 //garbage collector;
    void finish(point p) { if (done) return; end = p; done = true; }
};

//메인 wrapper;

int fortune_main(std::vector<POINT>& pts,          //voronoi points;
                       std::vector<EDGE>& edges)     //voronoi edges;

{
      //point priority_queue구성;
      std::vector<POINT>::iterator iter=pts.begin();
      for(; iter !=pts.end(); iter++) {
          point P(iter->x, iter->y) ;
          points.push_back(P);
      }
      //body of algorithm ;
      while(!points.empty()) {
           if(!events.empty() && events.top()->x <= points.top().x) 
                 process_event() ; //circle event ;
           else 
                 process_site() ;   //site event;
      }
      //for remaining circle events if any;
      while(!events.empty()) 
           process_event() ;
                                                                      
      //2. prepare output edges and clean memory;
}

arc * root=NULL;                              //global variable;
void process_site() {
    point P= points.top(); points.pop(); //because popping return void in STL;
    if(!root) { // root of double linked list for arcs(global);
        root = new arc(P) ; return  ;
    }
    //
    for(arc* a = root; a; a=a->next) {
         point Q;
         if(intersect(P, a, &Q)) { //arc a와 점P에서의 포물선(degenerate 된)이 만나는 점 Q;
              duplicate_arc(P, a) ; //교차하는 arc를 둘로 만든다 
                                    //(다음 arc가 있고, 만약에 이것과도 교차하면 circle event 임으로 제외)
              insert_new_arc(P, a, a->next) ;//새 arc를 중간에 삽입한다;
              //새 arc의 에지 세팅 ::교차점을 출발점으로 하는 두개의 반직선을 만든다: 
              //도착점은 circle event에 대부분 결정되고, 나머지는 후처리 과정에서 결정됨)
              a = a->next ;
              a->prev->s1 =a->s0 = new seg(Q, ref_count) ;
              a->next->s0 =a->s1 = new seg(Q, ref_count++) ; //쌍으로 생성되는 반직선을 identify하기 
                                                             //위해서 동일번호를 부여함.
              //새 site 추가로 비치라인을 구성하는 arc의 초점들과 circle event를 만들 수 있는가 체크함;
              check_circle_event(a, P.x) ;
              check_circle_event(a->prev, P.x) ;
              check_circle_event(a->next, P.x) ;
         }
    }//for-;
};
//
void process_event(){
    event *e = events.top(); events.pop();
    if (e->valid) {
        // start a new edge.(single edges)
        seg *s = new seg(e->p, ref_count++);
        // remove the associated arc from the front. and attach a new segment;
        arc *a = e->a;
        remove_arc(a, s);
        // finish the edges before and after a==>new voronoi vertex;
        if (a->s0) a->s0->finish(e->p);
        if (a->s1) a->s1->finish(e->p);        
        // recheck circle events on either side of p:
        if (a->prev) check_circle_event(a->prev, e->x);
        if (a->next) check_circle_event(a->next, e->x);
        delete a;
    }
    delete e; 
};
// Look for a new circle event for arc a.
void check_circle_event(arc *a, double x0/*=current sweep-line*/) { 
    // Invalidate any old event.
    if (a->e && a->e->x != x0)  a->e->valid = false;
    a->e = NULL;
    if (!a->prev || !a->next) return;
    double maxx;
    point O;
    point& A = a->prev->p ;
    point& B = a->p ;
    point& C = a->next->p ;
    //collinear가 아니고, 최대값이 현재의 site event위치보다도 큰 경우에;
    if (circle(A, B, C, &maxx, &O) && maxx > x0) { //점 A,B,C에 의해서 형성이 되는 
                                                   //원 중심(O)과 최우측x(maxx) 좌표를 얻음;
        // create new event.
        a->e = new event(maxx, O, a);
        events.push(a->e);
    }
};

나머지 함수들은 모두 단순한 구현이므로 생략한다;

보로노이 에지는 seg collector에서 각각의 segment를 끄집어내어서 그리면 된다. 그러나 각각의 segment는 보로노이 에지를 전체를 커버하는 것이 아니다. site event인 경우에는 항상 듀얼로 반직선을 생성하는데. 이 두 개의 반직선이 하나의 보로노이 에지를 정의한다(따라서 ref를 참조하면 온전한 하나의 에지를 찾을 수 있다). circle event의 경우에는 에지가 듀얼로 생성하지 않았으므로 이 경우에는 하나의 segment가 그 에지를 표현한다. 에지 액세스를 쉽게 하기 위해서는 모든 에지를 듀얼 구조로 만들어서 사용할 수 있다.

n 개의 점들의 보로노이 다이어그램은 얼마나 많은 꼭짓점과 에지를 가질까?

이것은 오일러 공식 V-E+F=2를 사용하면 된다. 보로노이 다이어그램은 경우 바깥쪽의 에지들은 무한대로 연결이 되어 있다. 이것을 무한대에서 가상의 꼭짓점을 가정하고 그것에 연결이 되어 있다고 생각하면 된다. 따라서 V --> V+1로 계산을 해야 한다. 오일러 공식 : V+1-E + F= 2; 여기서 F=n임을 알 수 있다. (n개의 점들이 하나의 face상에 놓여 있음)그리고 하나의 에지가 두 개의 꼭짓점을 연결하므로 각각의 꼭짓점에서 나간 에지의 합(=deg(v))을 계산하면 2*E 개 임을 알 수 있다. sum deg(v) = 2 * E;그런데 각각의 꼭짓점에서는 적어도 3개 이상의 에지와 연결이 되어 있으므로 위식의 좌변은 (V+1) * 3 <= 2 * E;를 준다. 따라서 오일러 공식과 이 부등식을 연관시키면 V <=  2*n - 5; E <=  3*n - 6;임을 알 수 있다. 즉 필요한 메모리의 양은 입력점의 수의 선형적으로 비례한다.

따라서 전체 이벤트의 개수는 site 이벤트와 꼭짓점에 해당하는 circle event 만큼이 있으므로 O(3*n) 정도이다. 각각의 event에 대해서 arc노드를 검색해야 하므로 O(n) 번 탐색을 해야 한다(balanced binary tree의 경우에는 log(n)). 따라서 알고리즘의 복잡도는 O(n^2 ( n*log(n))이다./**** http://blog.naver.com/helloktk/80041603288*/

** 첨부된 실행파일로 알고리즘을 테스트해 볼 수 있다(중복된 입력점은 제거하였고, 세 점이 일직선상에 놓인 것을 방지하기 위해서 작은 랜덤 값을 첨가하였다)

 

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

Polygon Triangulation  (4) 2008.05.25
Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Trapezoidalization  (0) 2008.05.22
Optimizing Polygon Triangulation  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요