Learning OpenCV: Delaunay Triangulation, Voronoi Tesselation

Delaunay triangulation

เป็นวิธีการเชื่อมจุดใน space ให้เป็นสามเหลี่ยม (เรียกวา่ Delaunay) โดยคุณสมบัติคือ มุมที่น้อยที่สุดในสามเหลี่ยมทั้งหมดจะมีค่ามากสุด(ก็คงพยายามทำให้เป็ฯสามเหลี่ยมด้านเท่า เท่าที่เป็นไปได้) และ circum-circle( หมายถึงวงกลมที่ล้อมรอบสามเหลี่ยม) ทุกอันจะต้องไม่มี จุด อยู่ภาพในวงกลม(ไม่งั้นก็หมายความว่า รูปนี้สามารถสร้างสามเหลี่ยมเล็กลงไปได้อีก)

จริงๆ สองส่วนนี้สัมพันธ์กันในลักษณะที่ว่า ถ้ามีสามเหลี่ยมมี่ผอมๆ (มีมุมหนึ่งน้อยๆ imply ว่าต้องมีอย่างน้อยอีกมุมมากๆ) จะทำให้ จุดศูนย์กลางของ circum-circle อยู่นอกสามเหลี่ยมนั้น ความเป็นจริงต้องไม่มีมุมใดมีขนาดถึง 90 องศา ลองดูภาพ circumcenter (จุดศูนย์กลางภาพ) ในกรณีต่างๆ

ซ้ายเป็นภาพที่ไม่มีมุมไหนถึง 90 องศา กลางภาพสามเหลี่ยมมุมฉาก ขวาสามเหลี่ยมมุมป้าน


วิธีคำนวณหาสามเหลี่ยม Delaunay วิธีหนึ่งคือ

1. เริ่มจากการกำหนดจุดนอก space นี้แล้วสร้างสามเหลี่ยมโดยร่วมกับอีกสองจุดใน space
2. เพิ่มจุดใน space ไปในกลุ่มสามเหลี่ยมที่เราสร้างแล้ว (ในตอนแรกจะมีสามเหลี่ยมเดียวที่มีจุดจากนอก space มาด้วย) คำนวณหา circum-circle ทุกอันว่ามีอันไหนที่ล้อมรอบจุดใหม่นี้ ถ้ามี สามเหลี่ยมนั้นไม่ใช่ (ตามที่ได้อธิบาย) ลบสามเหลี่ยมนั้นทิ้ง
3. จากขั้นที่สองสร้างสามเหลี่ยมใหม่ จากจุดที่เพิ่มเข้าไปในขั้นสอง และจุดที่โดนลบสามเหลี่ยมทิ้งไป
4. ไปยังข้อสองจนกว่าทุกจุดใน space จะถูกเพิ่มเข้าไปใน สามเหลี่ยม Delaunay 

ในพื้นที่ระหว่างจุดใน space เราสามารถหาได้ว่ามันอยู่ในอิทธิพลของจุดใด (ในหนังสือเรียก owned by) เราจึงสามารถแบ่ง partition ของ space ที่ owned โดยจุดได้ partition นั้นเรียกว่า Voronoi tessellation

ภาพซ้ายคือ Delaunay triangle ที่มี circum-circle และ circumcenter
ภาพขวาคือ Voronoi tessellation

จากรูปจะเห็นได้ว่า Voronoi tessellation เกิดจากการเชื่อมต่อ circumcenter เข้าด้วยกัน ซึ่งก็สมเหตุผล เพราะ เราอาจจะมอง ว่า circumcenter เป็นส่วนในวงกลม ที่มีจุดศูนย์กลางที่จุดต่างๆ ก็ได้ ดังนั้นเส้นที่ลากระหว่าง circumcenter ก็อาจจะมองได้ว่าเป็นเส้นที่ลากเชื่อมระหว่างจุดตัดของวงกลมของวง ซึ่งเส้นนี้จะอยู่ห่างจากจุดศูนย์กลางของวงกลมเ่ท่ากันทั้งสองวง  จึงสามารถนำเส้นเชื่อมระหว่าง circumcenter มาใช้ในการแบ่งเขตของ จุดใน space ได้


Creating a Delaunay or Voronoi Subdivision

มาดูวิธีการสร้าง Delaunay Subdivision กัน


CvRect rect = { 0, 0, 600, 600 };                //Our outer bounding box
CvMemStorage* storage;                        //Storage for the Delaunay subdivsion
storage = cvCreateMemStorage(0);        //Initialize the storage
CvSubdiv2D* subdiv;                              //The subdivision itself
subdiv = init_delaunay( storage, rect); //See this function below


ขั้นแรกคือการกำหนดพื้นที่สี่เหลี่ยมกัน (อย่าลืมว่า OpenCV จะสร้างสามเหลี่ยมโดยเริ่มจาก external vertex)
สร้าง memory storage และใช้คำสั่ง init_delaunay ในการสร้าง CvSubdiv2D ขึ้นมา


หลังจากนั้นก็เพิ่มจุดเข้าไป


CvPoint2D32f fp;             //This is our point holder
for( i = 0; i < as_many_points_as_you_want; i++ ) {
     // However you want to set points
    //
    fp = your_32f_point_list[i];
    cvSubdivDelaunay2DInsert( subdiv, fp );
}

เราสามารถสร้างข้อมูล Voronoi Tesselation ใน cvSubdiv2D ได้โดยคำสั่ง cvCalcSubdivVoronoi2D และลบข้อมูลเหล่านั้นโดยคำสั่ง cvClearSubdivVoronoi2D


Navigating Delaunay Subdivisions

หลังจากได้ Delaunay Subdivisions แล้วเราคงต้องการจะทำอะไรสักอย่างกับทุก edge (โดยการ navigate)

structure cvQuadEdge2D จะเก็บ edge ของ Delaunay และ Voronoi (ต้องสร้างก่อนด้วยคำสั่ง cvCalcSubdivVoronoi2D ) ลองดูรูป

e คือ edge ของ Delaunay ที่จะเก็บ เส้นประคือ voronoi edge



ส่วน structure CvSubdiv2DPoint จะเก็บ  Delaunay edge กับ associate point

e คือ Delaunay edge ที่เริ่มที่จุดที่มีสี่เหลี่ยม

Walking on edges

จากรูปที่สามเมื่อเรามีข้อมูล input edge เราสามารถหา edge ที่เหลือทั้งสี่ได้โดยใช้คำสั่ง


CvSubdiv2DEdge cvSubdiv2DRotateEdge(
    CvSubdiv2DEdge edge,
    int type
);

edge คือ input edge
type

• 0 หมายถึง input edge (e)
• 1 หมายถึง rotated edge (eRot)
• 2 หมายถึง reversed edge (reversed e)
• 3 หมายถึง reversed rotated edge (reversed eRot)

หรือจะใช้้คำสั่ง cvSubdiv2DGetEdge  เพื่อหา edge ที่ associate กับ input edge (ดูรูปที่ 4 ประกอบ)

CvSubdiv2DEdge cvSubdiv2DGetEdge(

    CvSubdiv2DEdge edge,

    CvNextEdgeType type

); 

edge คือ input edge

type 

• CV_NEXT_AROUND_ORG edge ถัดจากจุดกำเนิด (eOnext)
• CV_NEXT_AROUND_DST edge ถัดจากจุดปลาย (eDnext)
• CV_PREV_AROUND_ORG edge ก่อนจุดกำเนิด (reversed eRnext)
• CV_PREV_AROUND_DST edge ก่อนจุดปลาย (reversed eLnext)
• CV_NEXT_AROUND_LEFT edge ถัดไปใน left facet (eLnext)
• CV_NEXT_AROUND_RIGHT edge ถัดไปใน right facet (eRnext)
• CV_PREV_AROUND_LEFT edge ก่อนหน้าใน left facet (reversed eOnext)
• CV_PREV_AROUND_RIGHT  edge ก่อนหน้าใน left facet (reversed eDnext)

เราสามารถหาจุดใดๆ จาก edge โดยคำสั่ง

CvSubdiv2DPoint* cvSubdiv2DEdgeOrg( CvSubdiv2DEdge edge );

CvSubdiv2DPoint* cvSubdiv2DEdgeDst( CvSubdiv2DEdge edge );

(เราอาจจะต้องแปลง จุดเหล่านี้ให้อยู่ในรูปที่เข้าใจง่าย  cvPointForm32f(output_Org->pt)

ก่อนอื่นที่จะ travel ไปใน edge หรือจุดต่างๆ บน subdivision ได้ ก่อนอื่น ต้องหาจุด หรือ edge แรกก่อน
วิธีแรกใช้ฟังก์ชัน

CvSubdiv2DPointLocation cvSubdiv2DLocate(
    CvSubdiv2D* subdiv,
    CvPoint2D32f pt,
    CvSubdiv2DEdge* edge,
    CvSubdiv2DPoint** vertex = NULL
);

subdiv คือ subdivision ที่จะหา edge
pt คือจุดใดๆ

ผลลัพธ์ที่ได้มีดังนี้

• CV_PTLOC_INSIDE pt อยู่ใน จะคืนค่า edge หนึ่งใน facet กลับมาใน พารามิเตอร์ edge.
• CV_PTLOC_ON_EDGE pt อยู่ใน edge จะคืนค่า edge กลับมาใน พารามิเตอร์ edge
• CV_PTLOC_VERTEX pt เป็น vertex  จะคือนค่า vertex กลับมาในพารามิเตอร์ vertex
• CV_PTLOC_OUTSIDE_RECT pt อยู่นอกกอรบ
• CV_PTLOC_ERROR เกิดข้อผิดพลาดใน subdiv หรือ pt

วิธีที่สอง
เนื่องจากเราสร้าง Delaunay ด้วยการกำหนดจุด external มาก่อน (เพื่อสร้าง external triangle) เราสามารถเข้าถึงข้อมุลเหล่านี้ได้
วิธีหาค่า vertices ของ external triangle

CvSubdiv2DPoint* outer_vtx[3];
    for( i = 0; i < 3; i++ ) {
        outer_vtx[i] = (CvSubdiv2DPoint*)cvGetSeqElem( (CvSeq*)subdiv, I );
}


วิธีหาค่า edge  ของ external triangle

CvQuadEdge2D* outer_qedges[3];
    for( i = 0; i < 3; i++ ) {
        outer_qedges[i] = (CvQuadEdge2D*)cvGetSeqElem( (CvSeq*)(my_subdiv->edges), I );
}