Learning OpenCV: Hierarchical Matching

การ matching ด้วย moments ไม่เพียงพอ (แต่เร็ว) ก่อนอื่นมาทำความรู้จักกับ contour tree ก่อน

Contour tree
contour tree ไม่ใช่การ represent contour ด้วย tree (อย่างที่ได้จากค่า cvFindContours) ลองมาดูวิธีการสร้าง contour tree กัน ก่อนอื่นเริ่มต้อนด้วยรูป

ขั้นตอนเริ่มจากการหาบริเวณที่มีส่วนยื่นออกมาหรือส่วนที่เว้าเข้าไปเป็นสามเหลี่ยม (จริงๆ ก็หาจุดสองจุดที่ไม่ติดกันอย่างในรูป) ส่วนที่ยื่นออกไป(A,B,D) จะถูกตัดทิ้ง ส่วนที่หดลงไปจะโดนถม (จะกลายเป็นรูปในเส้นประ) ทุกครั้งที่ิถมหรือตัดสามเหลี่ยมจะเป็นการลดจำนวนจุดใน contour และนำพื้นที่เหล่านี้ใสเข้าไปใน contour tree

ถ้าสามเหลี่ยมที่ถูกตัดหรือถูกถมนั้น มีด้านสองด้านอยู่ใน contour เดิมสามเหลี่ยมนั้นจะเป็น leaf node และถ้าด้านใดด้านหนึ่งของสามเหลี่ยมนั้น เป็นด้านในด้านหนึ่งของสามเหลี่ยมใน tree แล้ว สามเหลี่ยมนั้นจะเข้ามาเป็น parent ของ node นั้น ตัดไปเรื่อยๆ จนเหลือสี่เหลี่ยม (มี vertices เหลือ สี่อัน) แล้วก็หั่นเป็นสองท่อน เป็น child node ของ root

note อย่าลืมว่าทรีสร้างจากใบไปราก, สามเหลี่ยมหนึ่งๆ จะมีสามด้าน ด้านที่ถูกตัดทิ้งแรกๆ (คือมีสองด้านอยู่ในcontour ต้นฉบับ มีแนวโน้มเป็นใบ) parent ของมันจะโดนตัดเป็นอันดับถัดมา(y เป็น parent ของ c,d) ซึ่งแน่นอนว่า parent มีลูกได้แค่สอง(เพราะต่อกับสามเหลี่ยมได้อีกสองอัน อีกอันหนึ่งไว้ต่อกับ parent ของตัวเอง

หลังจาก contour tree สร้างแล้ว ก็จะมาเปรียบเทียบ contour tree ทั้งสองอัน โดยดูจากโหนดในทรีที่ตรงกันแล้วเปรียบเทียบระหว่างโหนดที่ตรงกันนั้นด้วย คุณลักษณะต่างๆ (เช่น ความยาว, moments, etc)

มีข้อควรระวังคือการสร้าง contour tree ของ OpenCV ไม่ค่อย robust การเปลี่ยนแปลงจุดเล็กน้อยใน contour อาจจะทำให้มีผลเปลี่ยนแปลงอย่างมากใน contour tree และ root ของทรี ก็เลือกแบบไม่มีหลักการเท่าใด ดังนั้นจึงแนะนำให้ เรียก cvApproxPoly และทำ cyclic shift

ฟังก์ชันในการเปรียบเทียบ contour มีดังนี้

• cvCreateContourTree
• cvContourFromContourTree
• cvMatchContourTrees