Learning OpenCV: Freeman Chain Codes, Polygon Approximations and Dominant point

Freeman Chain Codes
ปกติวิธีในการเก็บ contour จาก cvFindContours (ค่า default คือ CV_CHAIN_APPROX_SIMPLE) อีกวิธีหนึ่งคือ Freeman chains โดยกำหนดใน mode  CV_CHAIN_CODE ลองดูภาพตัวอย่าง

จากรูป (a) เราจะแบ่งทิศทางออกเป็นแปดทิศตามรูป ส่วนใน (b) แสดงการใช้ freeman codes ในการลากแทนที่ contour ของรถถัง โดยเริ่มจากท้ายตัวถัง

ในการอ่านค่า freeman chains ใช้ฟังก์ชันดังนี้

• cvStrarReadChainPoints
• cvReadChainPoint

 คำสั่งแรกเป็นการเริ่มอ่านค่า chain (เหมือน fopen) แล้วทำการอ่านค่า chain ต่อไปเรื่อยๆ ด้วย cvReadChainPoint จนกว่าจะเจอค่า NULL ในทำนองเดียวกับ CvSeqReader

Polygon Approximations

ปกติ Polygon Approximations จะใช้ในการลดจำนวน vertics OpenCV ใช้วิธี Douglas-Peucker (DP) approximation ในฟังก์ชันที่เรียกว่า cvApproxPoly()

CvSeq* cvApproxPoly(

    const void* src_seq,

    int header_size,

    CvMemStorage* storage,

    int method,

    double parameter,

    int recursive = 0

);

ผลลัพธ์ที่ได้จะเป็น CvSeq* ที่ชี้ไปยัง contour แรก (เราสามารถหา contour ต่อไปได้เอง) 

src_seq คือ sequence ของ contour ที่จะใช้ในการหา approximation

header_size = sizeof(CvContour)

storage เป็น memory storage ที่ต้องใช้ในการคำนวณ

method  เป็น CV_POLY_APPROX_DP (อย่างที่กล่าวไว้ในข้างต้น และตอนนี้มีวิธีเดียว)

recursive จะบอกว่าให้ค่า  approximation เฉพาะ contour แรกที่ชี้(head) หรือจะให้หาทุก contour

parameter เป็นค่าที่กำหนดเป็น threshold สำหรับวิธีการหา approximation

ก่อนอื่นลองดูวิธีการหา approximation เพื่อที่จะเข้าใจถึง parameter

(a) เป็น image, (b) คือ contour ของ (a) ต่อไปเราจะหา extreme point แล้วเชื่อมด้วยเช่น (c)  หลังจากนั้นจะหาจุดใน contour ที่ไกลจากเส้นที่สุด (ดูใน (c)) หลังจากนั้นลากเส้นเชื่อม (d) แล้วหาจุดที่ไกลจากสามเหลี่ยมใน (d)  ทำไปเรื่อยๆ จนในที่สุด เส้นที่หาได้น้อยกว่าค่าทีระบุใน parameter ก็หยุด

Dominant point

คือจุดที่มีข้อมูลเกี่ยวกับ curve มากกว่า จุดอื่น(นัยว่าสำคัญกว่าจุดอื่นเพราะมีข้อมูลเยอะกว่า ถ้าจะลดจำนวน vertices จุดทีเป็น dominant point ไม่น่าโดน) ฟังก์ชันที่ใช้หา dominant point ใน OpenCV คือ 

CvSeq* cvFindDominantPoints(

    CvSeq* contour,

    CvMemStorage* storage,

    int method = CV_DOMINANT_IPAN,

    double parameter1 = 0,

    double parameter2 = 0,

    double parameter3 = 0,

    double parameter4 = 0

);

contour คือ contour ที่จะหา dominant point

storage คือ memory storage ที่ใช้ในการคำนวณ

method ตอนนี้มีค่า CV_DOMINANT_IPAN หมายถึง algorithm IPAN

แนวคิดคือ IPAN จะพยายาม scan ไปทั่ว contour เพื่อจะสร้างสามเหลี่ยมโดยใช้จุดใน contour ลักษณะของสามเหลี่ยมจะกำหนดโดย ขนาดสองด้าน และ มุม (ด้านมุมด้าน เพียงพอที่จะกำหนดสามเหลี่ยมได้ ยังจำได้ไหม) 

parameter1, parameter2 หมายถึง ระยะทางที่สั้นสุด และระยะทางที่ยาวที่สุด

parameter3 หมายถึง neighbor distance

parameter4 หมายถึง maximum angle θ

หลังจากที่ IPAN สร้างสามเหลี่ยมที่แบบที่ ด้านสองด้าน มีค่าระหว่าง paramter1และ parameter2 โดยที่มุมระหว่างสองด้านน้อยกว่า parameter4 หลังจากนั้น จุดที่มีมุมที่น้อยที่สุดในระหว่างจุดที่ใกล้เคียงกัน (กำหนดความใกล้เคียงกันโดย parameter3) จะคงอยู่ที่เหลือจะถูกกำจัดออกไป

โดยปกติค่า parameter1-4 จะกำหนดเป็น 7,9,9,150 ตามลำดับ