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 );
}

Learning OpenCV: Inpainting and Mean-shift segmentation

Inpainting

เป็นวิธีในการกู้ image ที่เกิด noise เช่น ฝุ่นในภาพถ่าย


void cvInpaint(
    const CvArr* src,
    const CvArr* mask,
    CvArr* dst,
    double inpaintRadius,
    int flags
);

src คือ image ต้นฉบับ
mask ระบุถึงตำแหน่งที่ damaged ใน image (ตำแหน่งที่ต้องการซ่อม)
dst คือ image ผลลัพธ์
inpaintRadiuse กำหนดความขนาดพื้นที่รอบๆ จุดที่ต้องการ inpaint (ถ้ากว้างมากจุดจะโดนเฉลี่ยมากทำให้เกิดการ blur ได้)
flags คือวิธีการใน inpanting เลือกได้ระหว่า

• CV_INPAINT_NS(Navier-Stokes method)
• CV_INPAINT_TELEA (A. Telea’s method)

Mean-Shift Segmentation

ในตอนก่อนๆ ได้อธิบายเรื่องการ segmentation โดยใช้ image pyramids (cvPyrSegmentation) วิธีนี้จะใช้ color merge เพื่อ segment image. วิธีนี้จะใช้การ minimizing energy ของ image (energy กำหนดโดย link strength ซึงกำหนดด้วย ความเหมือนของสี อีกที)  cvPyrMeanShiftFiltering ก็ใช้แนวคิดนี้ในการทำ color segmentation ภาพ

void cvPyrMeanShiftFiltering(

    const CvArr* src,

    CvArr* dst,

    double spatialRadius,

    double colorRadius,

    int max_level = 1,

    CvTermCriteria termcrit = cvTermCriteria(CV_TERMCRIT_ITER | CV_TERMCRIT_EPS,5,1)

);

src คือ image ต้นฉบับ

dst คือ image ผลลัพธ์

saptialRadius, colorRadius คือรัศมีสำหรับ spatial และ color ตามลำดับ

max_level คือ level ในการทำ pyramid scale

termcrit  เป็น iterative algorithm ที่กำหนดว่าการ iteration จะหยุดอย่างไรลองดูการประกาศ

cvTermCriteria(

    int type; // CV_TERMCRIT_ITER, CV_TERMCRIT_EPS,

    int max_iter,

    double epsilon

);

int คือเป็นตัวบอกว่า iteration จะหยุดใด

• CV_TERMCRIT_ITER จะหยุดเมื่อ iteration จนครบจำนวนครั้ง ค่านี้กำหนดใน max_iter
• CV_TERMCRIT_EPS จะหยุดเมื่อ convergence metrix มีค่าเล็กลงถึงขนาดหนึ่ง กำหนดค่านี้ใน epsilon 

ค่า CV_TERMCRIT_ITER กับ CV_TERMCRIT_EPS สามารถใช้ด้วยกันได้

กลับมาที่ cvPyrMeanShiftFiltering กันต่อ ในกรณีที่ข้อมูลเราอยู่ในระนาบ x,y และ r,g,b  mean-shift จะ  หา ก้อนของข้อมูล(segment) ที่รวมกันอยู่อย่างหนาแน่นโดยกา้ร scan ตัว window ไปทั่ว space แต่ range ของ spatial กับ range ของ color จะแตกต่างกัน  ดังนั้น mean-shift ต้องการรัศมีที่ต่างกันในการ scan ระหว่าง spatial space (กำหนดใน spatialRadius) และ color space (colorRadius) ตลอดทางที่ mean-shift window เคลื่อนที่ (scan) จุดที่ converge (โดยสี) ไปยัง peak จะถูกจัดอยู่ในกลุ่มเดียว (owned by) กับ peak นั้นๆ

จุด peak และส่วนที่ owned by peak นั้นๆ จะถูกนับเป็น segment เดียวกัน จริงๆ แล้วการทำ color clustering จะทำใน scale pyramids (จากคำสั่ง cvPyrUp, cvPyrDown) ดังนั้น max_level จะเป็นตัวกำหนดจำนวน level ในการทำ image pyramids 

Learning OpenCV: Watershed Algorithm

ก่อนที่จะเข้าเรื่อง segmentation ที่เกี่ยวกับภาพเคลื่อนไหวมาเข้าเรื่องการ segmentation ที่ไม่ต้องใช้ภาพจากหลายๆ เวลากันก่อน


Watershed Algorithm
เป็นวิธี segmentation ที่ไม่ได้ใช้ concept ของการ remove background (เพราะในบางครั้งมันไม่มีหรือว่าสำคัญเท่ากันหมด)  คำอธิบายในหนังสืออ่านแล้วก็ไม่สื่อเท่าไร ลองไปค้นมาจาก wiki ก็ได้ความถึง กระบวนการของ watershed คือ เราสามารถมอง ภาพ intensity image(ก็ gray scale นั่นแหละ) ให้เปรียบเสมือนแผนที่ในโหมด topography (ไอ้โหมดที่สีเข้มแทนที่สูง สีน้ำเิงินแทนน้ำทะเล) เราก็จะเห็นภาพเปรียบเสมือนภูเขาและแอ่งน้ำได้ ทีนี้เราก็กำหนดจุด fill ซึ่งก็มีหลายวิธี ในหน้งสือจะอธิบายวิธี fill โดยใช้ flooding ง่ายๆ คือกำหนดจุดปล่อยน้ำให้น้ำไหลจากที่สูงไปที่ต่ำแล้วก็ขังเกิดเป็นลุ่มน้ำ (watershed) ซึ่งลุ่มน้ำนี้อาจจะถือได้ว่าเป็นการ segment ประเภทหนึ่ง (background)

 watershed ยังอนุญาติให้ ผู้ใช้คือ algorithm อื่นกำหนด background และ บอกว่า พื้นที่เหล่านี้เป็นพื้นที่ๆ เดียวกัน(ในกรณีที่มี noise แยกพื้นที่สองที่ๆ ควรจะเป็นที่เดียวกันออก)

ในภาพซ้ายเราเส้นสีขาวเป็นตัวบอกว่าพื้นที่ๆ ต่อกันด้วยเส้นเป็นพื้นที่เดียวกัน ผลลัพธ์ที่ได้ออกมาดังภาพขวา


void cvWatershed(
    const CvArr* image,

    CvArr* markers
);

image เป็นภาพที่ต้องการทำ watershed
markers มีขนาดเท่า image และมีค่าเป็น 0s ยกเว้นจะต้องการจะบอก cvWatershed ว่าพื้นที่ในส่วนต่างๆ เป็นพื้นที่เดียวกัน โดยกำหนดค่า ตัวเลขใดๆ ใน maskers ตัวเลขที่เท่ากันจะบอกถึงความเป็นพื้นที่เดียวกัน

Learning OpenCV: Contour Convexity and Pairwise Geometrical Histograms

ในตอนนี้จะรวมสองเรื่องที่เหลือในการ matching contour


Contour Convexity and Convexity Defects
เป็นวิธีในการหา convex hull (เปลือกที่นูน น่าจะหมายถึงเส้นรอบของ วัตถุที่ไม่มีส่วนเว้าเข้า) ของวัตถุ หลังจากนั้นคำนวณหา convexity defects เราจะนำ convexity defects เหล่านี้มาเป็นส่วนหนึั่งของ characteristic ของ complex object ได้

จากรูปมือที่่เห็น เส้นกรอปนอก(สีดำ)คือ convex hull พื้นที่ ตั้งแต่ a-h คือ convexity defects

ฟังก์ชันที่ใช้ในการคำนวณ convexity defects มีสามตัวคือ

#define CV_CLOCKWISE 1

#define CV_COUNTER_CLOCKWISE 2

CvSeq* cvConvexHull2(

    const CvArr* input,

    void* hull_storage = NULL,

    int orientation = CV_CLOCKWISE,

    int return_points = 0

);

int cvCheckContourConvexity(

    const CvArr* contour

);

CvSeq* cvConvexityDefects(

    const CvArr* contour,

    const CvArr* convexhull,

    CvMemStorage* storage = NULL

);

่
คำสั่ง cvConvexHull2 จะเป็นการสร้าง hull ของ contour คำสั่งที่สองจะเป็นการตรวจสอบว่า hull นั้น convex หรือไม่ คำสั่งสุดท้ายจะเป็นการหา convexity defects จาก contour และ convex hull

cvConvexHull2 จะเอา input array เป็น พารามิเตอร์แรก พารามิเตอร์ต่อมาคือ memory storage พารามิเตอร์ที่สามจะกำหนดว่า hull ที่ได้จะวนหรือตามเข็ม พารามิเตอร์สุดท้ายถ้าเป็น 1 จุดต่างๆ จะคืนค่ากลับมาใน array ไม่เช่นนั้น จะคืนค่ามาแต่ indices ที่อ้างไปยัง input

cvCheckContourConvexity รับค่า contour เข้าไปและสามารถตรวจสอบได้ว่า convex หรือไม่ วิธีนี้รวดเร็วและง่าย แต่ถ้า contour ตัดกัน วิธีนี้จะใช้ไม่ได้

cvConvexityDefects จะรับค่า contour, convex hull (จาก cvConvexHull2) มาคำนวณหา convexity defects



Pairwise Geometrical Histograms

เราได้อธิบายถึงการกำหนด contour โดยวิธี freeman chain codes ไปแล้ว ต่อไปนี้จะกล่าวถึงประโยชน์ที่กล่างถึงมากอันหนึ่งคือการนำไปใช้ใน Pairwise Geometrical Histograms (PGH) ซึ่งตัว PGH เป็น extension ชอง chain code histogram (CCH)

CCH เป็น histogram ที่คำนวณโดยนับความถี่ที่เกิดขึ้นในแต่ละ step (ทั้ง 8 steps) ที่ represent contour คุณสมบัิติอย่างหนึ่งของ histogram แบบนี้คือการหมุนวัตถุทุกๆ 45 องศา จะทำให้ histogram เกิดการ cyclic transformation เท่านั้น

รูปซ้าย เป็นรูป contour, freeman chain code และ CCH ของรูปรถถัง

รูปขวา เป็นรูป contour, freeman chain code และ CCH ของรูปรถถังที่หมุน 45 องศา

PGH จะใช้แนวคิดคล้ายๆ วิธีการสร้าง PGH คือให้ เลือก edge อันหนึ่งเป็น base edge แล้วหลังจากนั้นจับคู่กับ edge ที่เหลือทุกอัน เพื่อคำนวณหาค่า dmin, dmax, θ   โดยที่ dmin คือระยะที่สั้นที่สุดระหว่าง edge ทั้งสอง dmax คือระยะที่ยาวที่สุด θ คือมุมระหว่าง edge ทั้งสอง แล้วเปลี่ยน edge อันใหม่ให้เป็น base edge จนครบทุกคู่  PGH จะเป็น histogram สองมิติ ที่มิติแรกเป็น θ มิติที่สองเป็น d ในทุกๆ การจับคู่ของ edge จะมีค่า (dmax, θ) และ (dmin, θ) เกิดขึ้น bins ทั้งสองและระหว่างนั้น จะถูกเพิ่มค่า

ในภาพซ้ายแสดง edge ทั้งสองเส้น(เส้นทึบ)พร้อมค่า dmin, dmax, θ 

ในภาพขวาแสดงถึง histogram ที่จะถูกเพิ่มค่าจาก คู่ edge ทางด้านซ้าย

ฟังก์ชันในการคำนวณค่า PGH คือ

void cvCalcPGH(

    const CvSeq* contour,

    CvHistogram* hist

);

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

Learning OpenCV: Moments

Moments เป็นวิธีหนึ่งที่ง่ายที่สุดในการเปรียบเทียบ contour โดยการเปรียบเทียบ contour moments
ลองมาดูนิยามของคำว่า moment กันก่อน

m(p,q) = ผลรวมของ (I(x,y)*x^p*y^q) ในทุกจุด

ในกรณีที่ p=q=0 m(0,0) และเป็นรูป binary จะหมายถึงความยาวของ contour ถ้าเป็นรูปปิดจะหมายถึงพื้นที่ (จำนวนจุดทุกจุดในเส้นรอบปิด เท่ากับพื้นที่)


ฟังก์ชันที่ใช้ในการหา moment คือ


void cvContoursMoments(
    CvSeq* contour,
    CvMoments* moments
)



โดย CvMoments นิยามดังนี้


typedef struct CvMoments {
    // spatial moments
    double m00, m10, m01, m20, m11, m02, m30, m21, m12, m03;
    // central moments
    double mu20, mu11, mu02, mu30, mu21, mu12, mu03;
    // m00 != 0 ? 1/sqrt(m00) : 0
    double inv_sqrt_m00;
} CvMoments;

cvContoursMoments จะคำนวนเฉพาะ spatial moments ให้เท่านั้น เราสามารถหา moment ได้โดยใช้คำสั่ง
cvGetSpatialMoment


moments ที่กล่าวมายังใช้ัในการเปรียบเทียบ contour ได้ไม่ดีนัก ปกติแล้วเรามักจะต้องการ normalized moments (contour ที่รูปร่างเหมือนกันแต่ขนาดต่างกันจะได้เปรียบเทียบกันได้) และ moment ที่คำนวณได้จะขึ้นกับ ระนาบที่เลือกใช้ เพราะฉะนั้นถ้า contour เกิดการหมุน moments ก็จะไม่ match กัน

OpenCV มีทางเลือกในการหา moments คือ

• cvMoments เหมือน cvContoursMoments แต่รับ input เป็นภาพ สามารถตั้งให้เป็น binary image ได้
• cvGetCentralMoment การคำนวณคล้ายกับ cvMoments เพียงแต่ ลบค่า เฉลี่ยในแกน x,y ลงไป มีผลทำให้เกิดคุณสมบัติ transition invariant (ไม่เปลี่ยนแปลงไปตามการเลื่อน)
• cvGetNormalizedCentralMoment เหมือน cvGetCentralMoment ยกเว้นมีการ normalized การ normalized นี้ทำให้เกิด invariant to scale (moment ของ contour ที่คล้ายๆ กัน แต่ขนาดไม่เท่ากันจะถูก normalized ให้ใกล้ๆ กัน)
• cvGetHuMoments เกิดจากผลรวมของ normalized central moment ผลที่ได้ จะได้ค่าที่ invariant to scale, rotation, and reflection (ผลจาก Hu Moment เลเวลหนึ่งจะ invariant to rotate  เลเวลเจ็ด จะ invariant to skew จึงสามารถนำมาใช้ในการเปรียบเทียบได้ดีกว่า moment ธรรมดา)

Matching with Hu Moments

การ matching contours ใน OpenCV ใช้คำสั่ง


double cvMatchShapes(
    const void* object1,
    const void* object2,
    int method,
    double parameter = 0
);

object1, object2 สามารถเป็น image หรือ contour ได้ ถ้าเป็น image ฟังก์ชันนี้จะคำนวณ moments ให้ก่อน แล้วนำมาเปรียบเทียบ
parameter ตอนนี้ไม่ได้ใช้
method เลือกได้ระหว่าง

• CV_CONTOURS_MATCH_I1
• CV_CONTOURS_MATCH_I2
• CV_CONTOURS_MATCH_I3

รายละเอียดดูได้จากในหนังสือ (เพราะไม่ได้บอกถึงผลที่ได้จากการ คำนวณแต่ละแบบ)

Learning OpenCV: Contour Summary Characteristics and Geometry

คุณลักษณะของ contour ที่สำคัญๆ ที่ OpenCV สามารถหาได้

• cvArcLength ใช้หาความยาวของ contour
• cvContourArea หาพื้นที่ของ contour
• cvBoundingRect หา bounding box ของ contour เป็นสี่เหลี่ยมแนวขนานกับแกน x
• cvMinAreaRect2 หา bounding box โดยสี่เหลี่ยมที่ bound จะมีมุมใดๆ ก็ได้
• cvMinEnclosingCircle หา bounding circle
• cvFitEllipse2 หา fitting ellipse

Geometry
เป็นฟังกขันในการคำนวณเกี่ยวกับ bounding box ทั้งหลาย

• cvMaxRect หา bounding box ระหว่าง CvRect สองตัว
• cvBoxPoints หาจุดทั้งสี่มุมจาก CvRect 
• cvPointSeqFromMat สร้าง sequence ของจุดจาก metric
• cvPointPolygonTest ใช้ในการทดสอบว่าจุด อยู่ใน polygon หรือไม่ 

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 ตามลำดับ

Learning OpenCV: Contour

จากตอนก่อนๆ เรื่องเกี่ยวกับการ detect edge โดยใช้ canny ขั้นตอนต่อไปคือการรวมจุดที่ประกอบเป็น edge นั้นรวมกัน เรียกว่า contour แน่นอน OpenCV มีฟังก์ชันสำหรับหา contour ไว้ให้

ก่อนอื่นมาดูนิยามของ contour ก่อน contour คือ list ของจุดที่แทน curve ในรูปภาพ ในกรณีของ Contour ใน OpenCV จะเก็บไว้ใน sequence ลองดูภาพประกอบ

ในภาพบนเป็นภาพที่เราต้องการหา contour ซึ่งประกอบด้วยส่วน A-E ส่วนด้านล่างคือ contour ที่ OpenCV หามาได้ (โดยฟังกชัน cvFindContours) ซึ่งกำกับไว้ด้วยคำว่า cX หรือ hX โดย c หมายถึง contour, h หมายถึง hole ตัวที่เป็นเส้นประ เป็น exterior boundaries ของพื้นที่สีขาว (ที่ไม่ใช่ 0 ก็คือกรอบของพื้นที่ขาว)   ตัวเส้นจุดนั้นเป็น interior boundaries ของพื้นที่สีขาว หรือ exterior boundary ของพื้นที่ดำ (คืออยู่ในพื้นที่ขาว, หรือว่าเป็นกรอบของพื้นที่สีดำ) ซึ่ง OpenCV จะแยกความแตกต่างระหว่างสองตัวนี้

*notes ในความเป็นจริงระหว่างภาพ binary (ภาพขาวดำ) และ edge ที่ detect ได้จาก canny จะมีความแตกต่างกันเล็กน้อยในผลลัพธ์ เพราะจริงๆ แล้ว cvFindContours ไม่รู้จักว่า edge คืออะไร แต่จะมองเห็นเป็นพื้นที่สีขาวบางๆ (ไม่ได้เข้าใจว่ามันเป็น edge แต่อย่างไร) ผลลัพธ์ที่ได้ก็คือ ใน edge วงรอบปิดหนึ่งๆ จะได้ exterior contour และ interior contour มาสองอันที่ขนาดใกล้กันมาก

ลองมาดูฟังก์ชันกันซะที

int cvFindContours(
    IplImage* img,
    CvMemStorage* storage,
    CvSeq** firstContour,
    int headerSize = sizeof(CvContour),
    CvContourRetrievalMode mode = CV_RETR_LIST,
    CvChainApproxMethod method = CV_CHAIN_APPROX_SIMPLE
);

img คือรูปภาพซึ่ง OpenCV จะใช้พื้นที่นี้ในการคำนวณด้วย ถ้าต้องการเก็บข้อมูลส่วนนี้ให้ copy ไว้ก่อน
storage เป็น memory storage ที่เราจองไว้
firstContour เป็นผลลัพธ์ที่ได้จากฟังก์ชัน
headerSize ใช้ในการบอกถึงขนาด object ที่จะ allocate ปกติเป็น sizeof(CvContour) หรือ sizeof(CvChain)
mode มีตัวเลือกอยู่ 4 ตัว

• CV_RETR_EXTERNAL จะหาเฉพาะ extrme outer contours
• CV_RETR_LIST หาทุก contour และแทนด้วย list
• CV_RETR_CCOMP หาทุก contour และแทนด้วยต้น list สอบระนาบ ระนาบบนมีแต่ cX ระนาบล่างเป็น hX
• CV_RETR_TREE  หาทุก contour และจัดเรียงเป็น tree

ลองดูตัวอย่างผลที่ได้จากการหา contour ในรูปแรกกัน

ตัวเลือกเหล่านี้จะบอกว่าเราต้องการหา contour แบบไหนและผลลัพธ์แบบไหน ซึ่งจริงๆ วิธีการลิงก์ linked list ของ sequence ด้วย h_prev, h_next, v_prev, v_next นั้นกำหนดได้จาก mode ในการหา contour

method คือวิธีการประมาณค่า contour

• CV_CHAIN_CODE ผลลัพธ์ contour จะอยู่ในรูปแบบ Freeman chain code วิธีอื่นจะเป็น polygons (sequence of vertics)
• CV_CHAIN_APPROX_NONE แปลง chian code ให้เป็น จุด
• CV_CHAIN_APPROX_SIMPLE 
• CV_CHAIN_APPROX_TC89_L1  CV_CHAIN_APPROX_TC89_KCOS ใช้วิธี Teh-Chin approximation algorithm
• CV_LINK_RUN  method นี้จะใช้ได้กับ mode CV_RETR_LIST เท่านั้น

ซึ่งวิธีการหา contour นอกจาก cvFindContours แล้ว ยังสามารถใช้กลุ่มฟังก์ชันเหล่านี้ในการหา contour ได้

• cvStartFindContours
• cvFindNextContour
• cvSubstituteContour
• cvEndFindContour
• cvApproxChains

แนวคิดของวิธีนี้คือเราจะไม่หา contour ออกมาทีเดียว เราจะออกมาทีละตัว โดยตัวแรกเราจะใช้คำสั่ง cvStartFindContours ซึ่งจะให้ผลลัพธ์มาเป็น CvSequenceScanner (คล้ายๆ กับการ เปิด file ก่อนด้วย fopen)

ซึ่งใน CvSequenceScanner เก็บ state เกี่ยวกับ contour ที่เราหาไปแล้ว (อย่าสับสนระหว่าง CvSequenceScanner กับ CvSeqReader, CvSeqReader ไว้ใช้อ่าน elements ที่เรียงเป็น sequence แต่ CvSequenceScanner  เป็น list ของ contour (ซึ่งเป็น list ของ sequece อีกที)

เราสามารถหา contour ต่อไปได้เรื่อยๆ ด้วยคำสั่ง cvFindNextContour จนกว่าจะเจอค่า NULL หรือสั่งจบการหาเองด้วย cvEndFindContour (เหมือน fclose)

ฟังก์ชัน cvSubstituteContour ใช้ในการแทน contour ในตำแหน่งที่ปัจจุบันด้วย contour ใหม่ หรือจะใช้ลบ contour ปัจจุบันอยู่ก็ได้ (โดยใช้ค่า NULL ไปใน contour ที่จะแทนที่)

ฟังก์ชัน  cvApproxChains ใช้ในการแปลง Freeman chians ไปเป็น polygon (จริงๆ มีการประมาณค่าด้วย)

Drawing Contours

ฟังก์ชันในการวาด contour คือ

void cvDrawContours(

    CvArr* img,

    CvSeq* contour,

    CvScalar external_color,

    CvScalar hole_color,

    int max_level,

    int thickness = 1,

    int line_type = 8,

    CvPoint offset = cvPoint(0,0)

);

img คือ image ที่จะวาด contour

contour คือ root node ของ contour tree

external_color, hole_color เป็นสี่ที่จะใช้ fill ระหว่าง external กับ hole

max_level จะเป็นการสั่งให้วาด contour ใน contour tree เท่ากับจำนวนชั้นที่กำหนด(ในกรณีของ CV_RETR_LIST มีชั้นเดียว ค่า 0 ก็พอ ในกรณี CV_RETR_CCOMP มีสองชั้นถ้าใส่หมดก็จะต้องให้ค่าเป็น 1 ยังมีค่าที่ติดลบสำหรับใช้ในกรณี CV_RETR_CCOMP และ CV_RETR_TREE)

thickness คือความกว้างของเส้นที่จะวาด ถ้าให้ค่าเป็น

line_type ประเภทของเส้นที่จะวาด

offset ใช้ในการกำหนดตำแหน่งการวาดแทนที่จะวาดเป็น absolute coordinate สามารถใช้ได้ในกรณีที่เรา หา contour โดยใช้ ROI

Learning OpenCV: Template Matching

วิธีนี้ไม่ใช้ histogram แต่ใช้วิธีการ match patch ที่มีรูปภาพ (ในกรณีของ back project patch นั้นจะเป็นแค่กรอบ ภาพนั้นใช้ภาพจากภาพ test) การ match patch ของรูปภาพ กับ ภาพที่จะหานั้นจะใช้วิธีที่จะกล่าวถึงต่อไปในตอนนี้

ก่อนอื่นมาดูฟังก์ชันในการ match template กันก่อน

void cvMatchTemplate(
    const CvArr* image,
    const CvArr* templ,
    CvArr* result,
    int method
);

image คือภาพที่จะหา template
templ คือ template ที่จะหาในภาพ
result คือผลลัพธ์
method คือวิธีในการคำนวณการ matching มีดังนี้

• Square difference matching method (method = CV_TM_SQDIFF)(หาค่าผลต่างกำลังสอง)
• Correlation matching methods (method = CV_TM_CCORR)(หา correlation)
• Correlation coefficient matching methods (method = CV_TM_CCOEFF)

ยังมี normalized version ของสามวิธีนี้ ซึ่งจะช่วยลดผลการผิดพลาดเนื่องจากสภาพแสงไม่เท่ากัน (ในตัวอย่าง histogram matching EMD) คือ

• CV_TM_SQDIFF_NORMED
• CV_TM_CCORR_NORMED
• CV_TM_CCOEFF_NORMED

วิธี CV_TM_SQDIFF จะใช้เวลาน้อยสุดแต่ผลที่ได้จะค่อนข้างแย่ตรงช้ามกับ CV_TM_CCORR_NORMED แต่ก็ต้อง trade-off

เช่นเดียวกับ cvCalcBackProjectPatch เราจะหาตำแหน่งของ วัตถุได้โดยใช้คำสั่ง cvMinMaxLoc (แต่ต้องระวังหน่อยเพราะว่า mothod ที่ต่างกันค่าที่ต้องการก็จะต่างกันเช่น CV_TM_SQDIFF_NORMED ต้องหาค่า min ส่วน CV_TM_CCORR_NORMED หรือ CV_TM_CCOEFF_NORMED ต้องหาค่า max)

เพื่อต้องการหาค่า match ที่ถูกต้อง(ไม่บังเอิญเจอ error) จึงมีแนวคิดที่ว่า บริเวิณรอบๆ จุดที่ match เจอน่าจะมีค่าค่อนข้างสูง(เพราะภาพความมีความต่อเนื่อง) ดังนั้นวิธีการ smooth ภาพผลลัพธ์ก่อนที่จะใช้ cvMinMaxLoc ในการหาจุดสุดสุดต่ำสุดน่าจะช่วยได้

Learning OpenCV: Back Projection

back projection
เป็นวิธีในการบันทึกว่า pixel หรือว patch ของ pixel เข้ากันได้กับ histogram ของ
model (ตัวอย่าง)  อย่างเช่นถ้าเรามี histogram ของสีผิวคน เราสามารถใช้ back project
หาตแหน่งของสีผิวคนในภาพได้

void cvCalcBackProject(
    IplImage** image,
    CvArr* back_project,
    const CvHistogram* hist
);
image คือภาพ ที่จะหาว่ามีข้อมูลใน histogram อยู่หรือไม่
hist คือ histogram ที่จะหา
back_project เป็น CvArr ขนาดเท่า image

ค่าใน back_project จะเป็นค่าที่อยู่ใน bin (ใน hist ที่ associated กับจุดนั้นๆ) ในกรณีที่ hist นั้น normalized ค่านี้อาจถือได้ว่า เป็นค่า ความน่าจะเป็นแบบมีเงื่อนไข (conditional probability value) อธิบายได้ว่าคือความน่าจะเป็นที่ pixel นั้นๆ จะอยู่ในเงื่อนไขเดียวกับ hist

ซ้ายบนคือ histogram ของมือ(ไม่ใช่ของขวาบน)
ขวาบนคือภาพที่เราจะทดสอบ

ซ้ายล่างคือ histogram ของภาพที่จะทดสอบ(ภาพขวาบน)
ขวาล่างคือค่าความน่าจะเป็น p(C|F)

ลองดูตัวอย่าง ถ้า C เป็นสีของ pixel และ F คือความน่าจะเป็นที่สีนั้นจะเป็นสีผิวหนัง ดังนั้น probability map(back_project) อันนี้ ให้ค่า p(C|F)

เพราะว่าค่าตรงนี้คือค่าใน bin หรือความถี่ ของ histogram ของผิว ที่ associate กับจุดนั้น ความหมายของความถี่คือจำนวน ครั้งที่เกิดขึ้นของ สีนั้นๆ ใน histogram p(C)เมื่อ histogram นี่เป็น histogram ที่คำนวณจากภาพผิวหนัง(ในตัวอย่างคือภาพมือ) เพราะฉะนั้น ค่าที่ได้คือ p(C|F)

ความน่าจะเป็นที่จะเป็นเป็น C เมื่อวัตถุนั้นเป็นผิวหนัง(F)  ในทางกลับกันเราต้องการหา ความน่าจะเป็นที่ pixel ตรงนั้นจะเป็นผิวหนัง(F) ในเงื่อนไขที่ว่า pixel ตรงนั้นมีสี C หรือ p(F|C) แต่ความน่าจะเป็นทั้งสองนี้สัมพันธ์กันโดย bayes's theorem  ดังนั้น ถ้าเรารู้ความน่าจะเป็นที่จะเจอสีผิวในภาพ p(C)  และความน่าจะป็นในการจะเจอบริเวณส่วนที่เป็นเนื้อในภาพ p(F) เราสามารถคำนวณหา p(F|C) ได้

จริงๆ ตรงนี้เห็นว่ามันแปรผันตรงกัน ค่า p(C|F) มากก็น่าจะหมายถึง ค่า p(F|C) มาก และน่าจะเป็นจริงในทางกลับกัน


ข้อควรระวังในการใช้ฟังก์ชันนี้คือถ้า back_project เป็น bytes image(ไม่ใช่ float) hist จะต้องไม่ถูก normalized หรือไม่ก็ scale ขึ้นมา เพราะการ normailized ทำให้ค่าสูงสุดใน hist คือหนึ่งค่าที่ต่ำกว่านั้นจะถูกปัดเป็น 0 ในภาพแบบ bytes



patch based back projection

เราใช้ back projection ในการดูว่า pixel น่าจะเป็นวัตถุที่เราสนใจขนาดไหน (วัตถุที่เราสนใจถูกแทนด้วย histogram) ซึ่งไม่ตรง(กันทีเดียว)กับการคำนวณความน่าจะเป็นที่วัตถุนั้นจะปรากฏในภาพ ทางเลือกอีกทางคือ กำหนด sub region ของภาพ แล้วคำนวณหา feature histogram ของ sub region  แล้วดูว่า match กับ histogram ของ model (ตัวอย่าง, วัตถุที่ต้องการหา) หลังจากนั้น เราจะ associate แต่ละ sub region ด้วยความน่าจะเป็นที่ sub region นั้นจะเป็น วัตถุที่เราสนใจ

ในขณะที่ cvCalcBackProject คำนวนความน่าจะเป็นของ pixel จะเป็นส่วนหนึ่งของ object ที่สนใจ  cvCalcBackProjectPatch จะคำนวณความน่าจะเป็น ที่ patch จะมี object ที่สนใจอยู่ โดย cvCalcBackProjectPatch จะคำนวณพื้นที่ patch นั้นไปทั่ว image แล้วคำนวณค่าใน patch นั้นเพื่อมาใส่ในผลลัพธ์(คล้ายๆ กับการทำ filter) โดยเหตุผลคือ ณ จุดนั้นๆ เพียงจุดเดียวไม่สามารถ ระบุถึง feature บางอย่างบริเวณจุดนั้นได้(เช่น texture ไม่สามารถระบุได้โดยใช้จุดเพียงจุดเดียว)

ลองดูพารามิเตอร์ของฟังก์ชัน

void cvCalcBackProjectPatch(
    IplImage** images,
    CvArr* dst,
    CvSize patch_size,
    CvHistogram* hist,
    int method,
    float factor
);

hist คือ histogram ของ object
dst เป็นผลลัพธ์ ที่มี 1 channel ขนาดลดลงตามขอบเนื่องจากการรันของ patch
patch_size คือ ขนาดของ patch
method เป็น method ที่เดียวกับที่ใช้เปรียบเทียบ histogram ในฟังกชัน cvCompareHist
factor คือระดับการ normalized ถ้าต้องการให้ภาพผลลัพธ์เห็นชัดขึ้น(ขยายความสว่าง) ก็สามารถปรับค่านี้ได้

ผลที่ได้คือความน่าจะเป็นของวัตถุ ในตำแหน่งต่างๆ หลังจากนั้น เราอาจจะใช้ คำสั่ง cvMinMaxLoc ในการหาตำแหน่งของภาพที่มีค่า สุงสุดหรือต่ำสุด

Learning OpenCV: Comparing Two Histograms

เรื่องสำคัญใน CV เรื่องหนึ่งคือการเปรียบเทียบ histogram ซึ่ง OpenCV มีฟังก์ชัน


double cvCompareHist(
    const CvHistogram* hist1,
    const CvHistogram* hist2,
    int method
);

method หมายถึง algorithm ที่ใช้ในการคำนวณเปรียบเทียบความแตกต่างของ histogram มีสี่วิธีคือ

1. Correlation (method = CV_COMP_CORREL)
2. Chi-square (method = CV_COMP_CHISQR)
3. Intersection (method = CV_COMP_INTERSECT)
4. Bhattacharyya distance (method = CV_COMP_BHATTACHARYYA)

histogram ต้อง normalized ก่อนจะมาเปรีบบเทียบ

ผลที่ได้ขึ่นอยู่กับ method ที่ใช้ในฟังก์ชัน เช่น exact match CV_COMP_CORREL, CV_COMP_INTERSECT จะได้ค่า 1, CV_COMP_CHISQR, CV_COMP_BATTACHARYYA ได้ค่า 0

ลองดูผลการคำนวณ เปรีบยเทียบ สี่วิธีกับ EMD (Earth Mover's Distance)

ปัญหาที่เกิดขึ้นคือจาก model ต้นแบบ(แถวแรก) กับ model ทดสอบที่สาม (total mis-match) ในแง่ของ CV จริงๆ แล้วอาจจะสื่อถึงสิ่งเดียวกันก็ได้ เช่น ภาพถ่ายมือ ในที่ๆ แสดงไม่เท่ากัน จึงการเลื่อนของ histogram   ถ้าเลื่อน histogram ทดสอบอันที่สามมาทางซ้าย จะได้ผล exact match  ซึ่ง EMD จะให้ค่าของจำนวน bins ที่ต้อง shift ให้ histogram เพื่อให้เกิด exact match ในกรณีตารางตัวอย่างนี้ จะเห็นได้ว่า EMD สามารถ ทายค่าของ Total mis-match ได้ถูกต้อง ในแง่ของความคล้ายระหว่างสอง histogram ในขณะที่ อีกสี่วิธีบอกไม่ได้ การคำนวณหา EMD มีฟังก์ขันแบบง่ายดังนี้ (ในหนังสือไม่ได้อธิบายพารามิเตอร์ของแบบยากไว้ และคิดว่าไม่น่าจำเป็น)

float cvCalcEMD2(

    const CvArr* signature1,

    const CvArr* signature2,

    int distance_type

);

distance_type ในที่นี้มีสองประเภทคือ Manhattan distance (CV_DIST_L1) หรือ Euclidean distance (CV_DIST_L2)

signature1, signature2 คือ CvArr ที่จะเปรียบเทียบหา EMD โดย เป็น Array ที่ประกอบด้วยค่าตามด้วยพิกัด

เช่นในกรณีที่มีมิติเดียว(ตังตัวอย่าง)  ตัว model จะได้ signature เป็น [1,0:0,1] ([ค่าหนึ่ง, ในตำแหน่งที่ศูนย์ และ : ค่าศูนย์, ในตำแหน่งที่หนึ่ง]) half match จะได้ signature เป็น  [0.5,0:0.5,1] ([ค่า 0.5, ในตำแหน่งที่ศูนย์ และ : ค่า 0.5, ในตำแหน่งที่หนึ่ง])  ในกรณีของ 3 มิติ จะได้ signature เป็น [value, x : y,z]

ลองดูตัวอย่าง 7-3 ในหนังสือ Learning OpenCV ซึ่งจะแสดงขันตอน การเปรียบเทียบ histogram โดยใช้ EMD เริ่มตั้งแต่การสร้าง signature และคำนวณค่า EMD

Learning OpenCV: Histogram Equalization

จริงๆ เรื่องนี้อยุ่ใน Image Transformation แต่เป็นการ transform histogram เลยมาอธิบายหลังจากที่ได้รู้จัก histogram กันก่อน (จริงๆ ก็ไม่จำเป็นเท่าไร)

การทำ histogram equalization คือการ mapping distribution อันหนึ่ง ให้เป็น distribution อีกอันหนึ่ง โดยให้ ค่า intensity เสมอกันเท่าที่เป็นไปได้  ซึ่งในการ remap นั้น เขาแนะนำ cumulative distribution function เป็น mapping function  ลองยกตัวอย่าง distribution ที่เป็น gaussian และ cumulative gaussian distribution

เมื่อนำ cumulative distribution มา map แล้วจะได้ distribution ที่ค่อนข้าง uniform

แต่ในกรณีภาพทั่ว equalized distribution อาจจะไม่ uniform แบบนี้ก็ได้

Learning OpenCV: Histogram

คงรู้จักกันดีว่า histogram คืออะไร มาดูการใช้งานใน OpenCV เลยดีกว่า

ใน OpenCV เราสร้าง histogram ด้วยคำสั่ง

CvHistogram* cvCreateHist(
    int dims,
    int* sizes,
    int type,
    float** ranges = NULL,
    int uniform = 1
);

dims คือจำนวนมิติของ histogram
sizes คือขนาดในแต่ละมิติ
type อาจะเป็น CV_HIST_ARRAY เพื่อเก็บข้อมูล histogram ใน dense multidimensional matrix structure (CvMatND) หรือ CV_HIST_SPARSE เพื่อเก็บข้อมูล histogram ใน sparse matrix representation (CvSparseMat)
uniform บอกว่า ข้อมูลใน bins (แต่และช่องของ histogram) เป็น uniform หรือไม่ และยังมีผลต่อความหมายของพารามิเตอร์ ranges  ถ้าตั้งค่าไม่เท่ากับศูนย์ bins จะ uniform
ranges ในกรณีที่ uniform=1 ranges เป็น array ของค่าคู่ลำดับ จำนวนคู่ลำดับจะเท่ากับจำนวนมิติ ในกรณี uniform =0 จะเป็นอะเรย์ของช่วงของแต่ละมิติ (งงล่ะสิ ดูตัวอย่างโลด)


uniform = 1 dims=1 (histogram 1 มิติ) sizes[0]=2  ranges[0] = [0,10]
จะหมายถึง histogram 1 มิติ มี 2 bins bin แรกเก็บค่า [0,5) bin สองเก็บค่า [5,10]

uniform = 0 dims=1 (histogram 1 มิติ) sizes[0]=5 ranges[0]=[0,2,4,5,7,12]

จะหมายถึง histogram 1 มิติ 5 bins  เก็บค่า [0,2), [2,4), [4,5), [5,7) ,[7,12]

เราสามารถให้ OpenCV ตั้ง range ได้โดยใช้คำสั่ง cvSetHistRanges  และเราสามารถ clear histogram เพื่อนับค่าใหม่ได้โดยใช้คำสั่ง cvCreateHist และ release histogram โดยใช้คำสั่ง cvReleaseHist 

Accessing Histogram
OpenCV มีฟังก์ชันในการเข้าถึงข้อมูลใน historgram อยู่สองชุด

1. cvQueryHistValue_1D, cvQueryHistValue_2D, cvQueryHistValue_nD
2. cvGetHistValue_1D, cvGetHistValue_2D, cvGetHistValue_nD

ถ้าต้องการเข้าถึงข้อมูลตรงเพื่อประสิทธิภาพ เราก็สามารถเข้าถึงข้อมูลโดยตรงได้ โดยอ้างถึง CvHistogram ก่อนอื่นมาดู struct ของ histogram กันก่อน

typedef struct CvHistogram

{

    int type;

    CvArr* bins;

    float thresh[CV_MAX_DIM][2]; // for uniform histograms

    float** thresh2; // for nonuniform histograms

    CvMatND mat; // embedded matrix header

     // for array histograms

}

CvHistogram;

ในกรณีที่เป็น sparse histogram mat น่าจะเป็น CvSparseMat 

ยกตัวอย่างในกรณีที่่ histogram เป็นแบบ dense ข้อมูลของ histogram จะเก็บในข้อมูล CvMatND เราก็สามารถอ้างถึงข้อมูลตรงนี้ได้ เช่น

• หาจำนวนมิติได้ โดยใช้ histogram->mat.dims
• หาจำนวน bins ในมิติ i โดยใช้ histogram->dim[i].size;
• ในกรณี uniform หา lower, upper bound ของ bin ในมิติ ที่ i โดย histogram->thresh[ i ][ 0 ], histogram->thresh[ i ][ 1 ]
• ในกรณี non uniform หา lower, upper bound ของ bin j ในมิติที่ i โดย histogram->thresh2[ i ][ j ], histogram->thresh2[ i ][ j +1]

Basic Manipulations with Histograms


ขั้นตอนที่สำคัญเกี่ยวกับ histogram จริงน่าจะเป็นการเก็บข้อมูลใน histogram และนำไปวิเคราะห์มากว่า

ในส่วนนี้จะสรุปเนื้อหาคร่าวในการสร้าง histogram เพื่อนำไปใช้ในการประมวลผล

เริ่มต้นที่การสร้าง histogram จาก image กันก่อน ด้วยคำสั่ง


void cvCalcHist(
    IplImage** image,

    CvHistogram* hist,
    int accumulate = 0,
    const CvArr* mask = NULL
);

image เป็นภาพที่ต้องการหา histogram (channel เดียวเท่านั้น) (จริงๆ ใช้ CvMat ก็ได้)
hist ผลลัพธ์
accumulate จะตั้งว่าให้เคลียร์ histogram ใหม่หรือไม่(ในกรณีต้องการคำนวณ histogram รวมหลายๆ ภาพ)
mask จะกำหนด pixel ที่จะคำนวณ histogram ถ้าไม่ระบุก็จะหมายถึงทุก pixel

หลังจากคำนวณ histogram แล้วเราสามารถใช้คำสั่งเหล่านี้เพื่อ manipulate histogram ได้

• cvCopyHist  สำเนาค่าไปยัง histogram ใหม่
• cvGetMinMaxHistValue หาค่าสูงสุดต่ำสุดของ histogram
• cvThreshHist ตัดค่าใน bin ที่น้อยกว่า threshold ให้เป็น 0
• cvNormalizeHist normalize histogram

Learning OpenCV: The rest of Transformation

ยังเหลือ Transform อีกสองแบบที่กล่าวไ้ว้คือ Integral Images กับ Distance Transform ซึ่งมองภาพไม่ออก เอาไว้ช่วยในการคำนวณล้วนๆ (ประมาณเดียวกับ transform ช่วงหลังๆ ) เข้าเรื่องเลยดีกว่า

Integral Images 

เป็นการ transform โดยการคำนวณค่าผลรวม, ผลรวมของกำลังสอง, ผลรวมของภาพที่่หมุนแล้ว (ไม่รู้เรื่องใช่มะ ดูภาพดีกว่า)

ทางซ้ายจะเป็น matrix ทางขวาจะเป็น matrix ที่เป็นค่ารวม (สังเกตว่า จะมีขนาดใหญ่กว่า) ค่าในแถวบน และหลักซ้ายจะเท่าเดิม  ส่วนค่าใน pixel ใดๆ จะได้มาจากผลรวมทั้งหมดจากแถวแรก ถึงแถวมัน จากหลักแรกถึงหลักมัน เช่น 25 นี่ได้มาจาก 1+2+2+20  80 ได้มากจาก 1+2+5+2+20+50 แต่จริงแล้วในการคำนวณค่า 80 ในแถวสองไม่จำเป็นต้องบวกหมดทั้งหกตัว จะใช้แค่ 50(ตัวมันเอง)+25(ซ้ายของมัน)+8(บนของมัน)-3(ซ้ายบน) ดังนั้นเวลาคำนวณ ตารางนี้ใช้เวลาเป็น O(N)

ประโยชน์หนึ่งในการคำนวณ integral image คือถ้าเราต้องการหาผลรวมในพื้นที่ (เพื่อทำค่าเฉลี่ย ความแปรปรวน) ในส่วนหนึ่งของ image ยกตัวอย่างคือ พื้นที่ที่ล้อมรอบด้วยวงเส้นทึบ ปกติการคำนวณจะใช้ระยะเวลาขึ้นกับขนาดพื้นที่ที่ต้องการคำนวณ O(N^2) ผลการคำนวณจากด้านซ้ายจะได้
20+50+20+50+100+50+20+50+20 = 380 แต่ในการคำนวณด้านขวาจะใช้ตัวเลขสี่ตัวเท่านั้นตลอดไม่ขึ้นกับขนาด ทำให้ O(1) 398-10-9+1 =380 (คงไม่งง) ฟังก์ชันของ OpenCV คือ


void cvIntegral(
    const CvArr* image,
    CvArr* sum,
    CvArr* sqsum = NULL,
    CvArr* tilted_sum = NULL
);

image คือภาพต้นฉบับ
sum คือผลลัพธ์แบบตารางในรูปด้านขวา
sqsum คือคล้ายๆ อันที่แล้วที่ยกกำลังสองก่อนบวก
tilted_sum คือหมุน 45 องศา(คือการ transpose หรือเปล่า) แล้ว sum



Distance Transform

มาถึงการ transform แบบสุดท้าย (ในหนังสือ) นิยามของการ transform แบบนี้คือในภาพผลลัพธ์ค่าที่ได้ในจุด x,y จะเป็นระยะห่างระหว่างจุด x,y ในภาพต้นฉบับกับจุด pixel ที่เป็น 0 ที่ใกล้ที่สุด (ลองคิดดูว่าถ้าหา edge detection เช่น canny แล้วกลับค่าให้ edge เป็น 0 ส่วนที่ไม่ใช่ edge มีค่า แล้วทำ distance transform ค่ายิ่งมากก็น่าจะเป็น centroid ของวัตถุ)

ในการคำนวณของ OpenCV จะใช้วิธีคำนวณระยะจริงๆ หรือว่าจะใช้ kernel ในการช่วยก็ได้


Void cvDistTransform(
    const CvArr* src,
    CvArr* dst,
    int distance_type = CV_DIST_L2,
    int mask_size = 3,
    const float* kernel = NULL,
    CvArr* labels = NULL
);

src, dst คือต้นฉบับและผลลัพธ์
distance_type คือวิธีการคำนวณหาระยะ (CV_DIST_L2 หมายถึงคำนวณระยะแบบ Cartesian)
mask_size คือขนาดของ mask ถ้าไม่ต้องการใช้ mask ใส่ CV_DIST_MASK_PRECISE
kernel ในกรณีที่เราจะทำ mask เอง (distance_type = CV_DIST_USER)
labels เป็นตัวเก็บไว้ว่าระยะห่างที่ใกล้ที่สุดที่คำนวณมาแต่ละ pixel ในผลลัพธ์คำนวณเทียบกับจุด zero ใดในภาพต้นฉบับ

Learning OpevCV: Discrete Fourier Transform and Discrete Cosine Transform

มาถึงการ transform ที่มองไม่เห็นภาพเท่า ไม่เข้าใจตั้งแต่เรียน EE math แล้วว่าทำไปเพื่ออะไร มาดูตัวอย่างก็เข้าใจขึ้นมานิดนึง ว่าบางทีการคำนวณในระนาบ x,y มันลำบาก เลยต้อง transform แล้วค่อยคำนวณ ดูอย่างในตอน Log Polar

Discrete Fourier Transform
เอาไว้ transform จากโดเมนที่เป็น discrete ซึ่ง  ปกติตามสูตร(หาได้ทั่วไป) ค่า O(big oh) จะเป็น N^2 มันเลยมีวิธีคิดได้หลายวิธี เช่น fast Fourier Transform (FFT) ซึ่งได้ประมาณ O(N*logN) ฟังก์ชัน cvDFT สามารถคำนวณ FFT สำหรับ CvArr มิติเดียวหรือสองมิติ (ในกรณีที่ CvArr เป็นสองมิติ สามารถเลือกได้ว่า จะคำนวณ FFT สองมิติ หรือมอง CvArr เป็น array มิติเดียวหลายตัว ซึ่งจะคำนวณเร็วทำทีละตัว)

ตามปกติ algorithm ในการคำนวณ DFT จะมีเคสพิเศษที่คำนวณได้รวดเร็วกว่าการคำนวณแบบปกติ ในกรณีของ OpenCV ก็เช่นกัน ถ้า CvArr มีขนาด 2^m*3^n*5^n  จะสามารถคำนวณได้ดีเป็นพิเศษ(เข้าใจว่าในกรณีนี้จะใข้ FFT คำนวณ)
ลองมาดูฟังก์ชันการคำนวณ DFT กัน

void cvDFT(
    const CvArr* src,
    CvArr* dst,
    int flags,
    int nonzero_rows = 0
);

src, dst คือตันฉบับและผลลัพธ์ ถ้าต้นฉบับมี channel (แสดงถึง มีแต่ ส่วน real) ผลลัพธ์จะมีการ packing เป็นพิเศษ(นัยว่าเพื่อประหยัดเนื้อที่)
flags

• CV_DXT_FORWARD  
• CV_DXT_INVERSE  คำนวณย้อนกลับ(ค่าไม่เท่าเดิมนะ ถ้าจะได้เท่าเดิมต้อง scale กันก่อน)
• CV_DXT_SCALE ใช้ในการ scale ค่า
• CV_DXT_INV_SCALE, CV_DXT_INVERSE_SCALE รวมสองอันข้างบนไว้
• CV_DXT_ROWS บอก cvDFT ว่า CvArr สองมิตินั่นคือ CvArr มิติเดียวหลายตัว

nonzero_rows บอกจำนวนแถวที่ padding ค่า 0 ไว้

จากที่บอกไป cvDFT สามารถคำนวณ CvArr บางขนาดได้ดีกว่าบางขนาด ซึ่งเราสามารถหาได้จากฟังก์ชัน cvGetOptimalDFTSize() ซึ่งจะให้ค่าที่ optimal ออกมา เราก็จึงต้องทำการแปลง CvArr ของเราให้ใหญ่ขึ้นตามขนาดนั้น แล้วก็ padding แถวที่เหลือด้วยค่า 0 แล้วก็ใช้ nonzero_rows บอกให้ cvDFT รู้ว่า padding กี่แถวเพื่อจะได้ละเลยไปซะทำให้การทำงานเร็วขึ้น (padding column ไม่เกี่ยว) ซึ่งค่านี้จำเป็นทั้งสำหรับการทำ forward และ inverse 

Spectrum Multiplication

Convolution and DFT

ในหัวข้อนี้จะแสดงเรื่องประโยชน์ของ DFT (เออ เพิ่งเจอตัวแรก) คือการ convolute ภาพต่างๆ นั้นมันจะยากวิธีง่ายๆ คือก็ transform ภาพโดย DFT ทำแบบเดียวกับ kernel แล้วเอาสองตัวนี้มา Multiplication กันหลังจากนั้นก็ inverse transform ผลลัพธ์ (มันจะ่ง่ายกว่าเหรอ) ลองดูในตัวอย่าง 6-5 ในหนังสือ Learning OpenCV ของ Oreilly 

Discrete Cosine Transform

ใช้เหมือนกับ DFT เพียงแต่ว่า DCT ไม่มีส่วน imagination (i) 

void cvDCT(

    const CvArr* src,

    CvArr* dst,

    int flags

);

พารามิเตอร์ใช้แบบเดียวกับ DFT (ตอนนี้ง่ายแฮะ)

Learning OpenCV: Cartesian, Polar, and Log Polar

ตอนนี้จะเป็นการ convert ระนาบจาก Cartesian กับ Polar

void cvCartToPolar(
    const CvArr* x,
    const CvArr* y,
    CvArr* magnitude,
    CvArr* angle = NULL,
    int angle_in_degrees = 0
);
void cvPolarToCart(
    const CvArr* magnitude,
    const CvArr* angle,
    CvArr* x,
    CvArr* y,

    int angle_in_degrees = 0
);

x,y คือพิกัดในระนาบ xy
magnitude, angle คือพิกัดในระนาบ polar
angle_in_degree เซ็ตว่ามุกในระนาบ polar จะเป็น degree หรือ radius

ส่วนการแปลง Cartesian ไปเป็น log polar ใช้ฟังก์ชันดังนี้

void cvLogPolar(
    const CvArr* src,
    CvArr* dst,
    CvPoint2D32f center,
    double m,
    int flags = CV_INTER_LINEAR | CV_WARP_FILL_OUTLIERS
);
src คือจุดในระนาบ x,y
dst ตือผลลัพธ์ในระนาบ log polar
center กำหนดจุดกึ่งกลางของภาพ src
m เป็นการขยาย scale
flags คือวิธีการ interpolation (CV_INTER_NN, CV_INTER_LINEAR, CV_INTER_AREA, CV_INTER_CUBIC) รวมกับ(โดยใช้ bitwise or) flags CV_WARP_FILL_OUTLIERS หรือ CV_WARP_INVERSE_MAP

ลองมาดูข้อดีของระนาบแบบ log polar ที่เกี่ยวข้อกับ การ หมุน และการ scale

ในรูปจะเห็นภาพสี่เหลี่ยมเส้นทึบโดนหมุน(เส้นเทา)และขยาย(เส้นประ) ผลลัพธ์ที่ได้ในระนาบ log polar จะเป็นการเลื่อนกราฟไปในแนวตั้งและแนวนอน (จากคุณสมบัติของ logarithm  กับการ transform แบบ linear transform) ซึ่งจริงๆ จะดูจากภาพก็ได้ว่า สี่เหลี่ยมทีเทาเกิดจากการหมุน ระยะห่างเท่าเดิมแต่มุมเพิ่มขึ้น ดังนั้นการเลื่อนกราฟไปในแนวตั้งในระนาบ log polar ก็เป็นเรื่องปกติ เพราะจุดเปลี่ยนแค่มุม ส่วนการขยายภาพ ก็จะเห็นได้ว่ามุมแต่มุมยังอยู่เท่าเดิมแต่ระยะห่างจาก center เพิ่มขึ้น การ shift กราฟไปทางขวาก็สมเหตุผล


การประยุกต์ใช้จะเห็นได้ว่าการ scale ภาพและการหมุนภาพ ไม่ใช่ปัญหาในการวิเคราห์ภาพอีกต่อไปถ้าอยู่ในระนาบ log polar การ matching ระหว่าง กราฟสามเส้นทางด้านขวาว่าเป็นสี่เหลี่ยมเหมือนกันง่ายกว่าการ matching สี่เหลี่ยมสามรูปทางด้านซ้ายมาก

Learning OpenCV: Stretch, Shrink, Warp, and Rotate

การ ทำ geometric transform รูปภาพใน planar นั้นอาจจะใช้ matrix 2x3 ที่เรียกว่า affine transformation หรือ 3x3 ที่เรียกว่า perspective transformation(หรือเรียกว่า homography)  มองง่ายๆ ดังรูป

การทำ affine จะสามารถ transform รูปสี่เหลี่ยมผืนผ้าไปเป็นรูปสี่เหลี่ยมด้านขนาน  ในขณะที่ homography สามารถ transform ไปเป็นรูปสี่เหลี่่ยมคางหมูได้ (เหมือนมุมมองเปลี่ยน)

ประโยชน์หนึ่งของการใช้ transformation คือการที่วัตถุอันเดียวกันถูกมองด้วยมุมมองที่ต่างกัน เช่นภาพถ่ายของวัตถุเดียวกันแต่คนละมุม ซึ่ง affine transformation สามารถใช้ได้ในหลายกรณี ยกเว้นบางกรณีทีต้องใช้ perspective transformation(homography) แต่ homography มีพารามิเตอร์มากกว่า


affine transformation คือการ transform แบบ linear transformation ตามด้วยการ translation ดังนั้นปกติในภาพ 2 มิติการทำ linear transformation สามารถใช้ matrix 2x2 แทนได้ และ ใช้ matrix 2x1 แทนการ translation ได้ (เลยเป็นที่มีของ matrix 2x3 ในที่กล่าวมาในตอนแรก) ส่วน perspective คือการหมุนในระนาบสามมิติแล้ว map กลับมาที่ระนาบสองมิติ (เลยทำไมต้อง 3x3)

การ transform ทั้ง affine และ perspective สามารถนำมาใช้ได้ทั้งการ transform แบบ dense (ภาพหรือว่าจุดที่ต่อกันเป็นภาพ) หรือแบบ sparse (list ของจุด) เราลองมาดูเป็นกรณีไป

Dense Affine Transform
เริ่มดูจากคำสั่ง

void cvWarpAffine(
    const CvArr* src,
    CvArr* dst,
    const CvMat* map_matrix,
    int flags = CV_INTER_LINEAR | CV_WARP_FILL_OUTLIERS,
    CvScalar fillval = cvScalarAll(0)
);

src, dst คือภาพต้นฉบับและผลลัพธ์เหมือนเช่นเคย
map_matrix คือ matrix 2x3 ที่จะใช้ transform แบบ affine
flag จะบอกถึงวิธีการคำนวณในกรณีที่ pixel ไม่สามารพ map ได้โดยตรง และสามารถเพิ่ม(ด้วย boolean or) ตัวเลือกต่อไปนี้

• CV_WARP_FILL_OUTLIERS fill ส่วนที่ไม่สามารถ map ได้ด้วย fillval
• CV_WARP_INVERSE_MAP ให้ map จาก dst ไป src แทน

ในหนังสือแนะนำให้ใช้วิธีการทำ Dense Affine Transformation อย่างอื่นคือ

void cvGetQuadrangleSubPix(

    const CvArr* src,

    CvArr* dst,

    const CvMat* map_matrix

);

ซึ่่งจะเห็นว่ามีพารามิเตอร์น้อยกว่า (header ในการประมวลผลก็จะน้อยกว่า) และสามารถ transform ได้ทีละหลายๆภาพ(หนังสือไม่ได้บอกว่าทำยังไง)

ปัญหาคือ ถ้าไม่ต้องการคำนวณ map_matrix เอง OpenCV ก็มีฟังก์ชันในการคำนวณให้

CvMat* cvGetAffineTransform(

    const CvPoint2D32f* pts_src,

    const CvPoint2D32f* pts_dst,

    CvMat* map_matrix

);

โดย pts_src จะเป็นจุดในต้นฉบับสามจุด (ซึ่งเพียงพอกับการกำหนดมุมของสี่เหลี่ยมผืนผ้า) และ pts_dst จะเป็นจุดในผลลัพธ์ที่ต้องการสามจุดเช่นกัน (ก็เพียงพอกับการกำหนดมุมของสี่เหลี่ยมด้านขนาน) ผลลัพธ์ที่ได้จะอยู่ใน map_matrix อีกฟังก์ชันหนึ่งที่กล่าวถึงในหนังสือคือ cv2DRotationMatrix ซึ่งคำนวณ map_matrix จากการหมุนรูปภาพ (ซึ่งเข้าใจว่าไม่สามารถแทนการ stretch กับ shrink ได้)

Sparse Affine Transformations

เป็นการ affine transform กลุ่มของจุด

void cvTransform(

    const CvArr* src,

    CvArr* dst,

    const CvMat* transmat,

    const CvMat* shiftvec = NULL

);

ในหนังสือแนะนำวิธีการใช้ฟังก์ชันนี้สองวิธี แต่ความเห็นส่วนตัวแนะนำวิธีที่ ใช้ transmat เป็น matrix 2x3 เช่นเดียวกับการทำ Dense Affine Transformation 

Dense Perspective Transformation

void cvWarpPerspective(

    const CvArr* src,

    CvArr* dst,

    const CvMat* map_matrix,

    int flags = CV_INTER_LINEAR + CV_WARP_FILL_OUTLIERS,

    CvScalar fillval = cvScalarAll(0)

);

การใช้งานแบบเดียวกับ Dense Affine Translation ทุกอย่างยกเว้น map_matrix ต้องเป็น 3x3

และหา map_matrix ได้ด้วย


CvMat* cvGetPerspectiveTransform(
    const CvPoint2D32f* pts_src,
    const CvPoint2D32f* pts_dst,
    CvMat* map_matrix
)

คล้ายๆ การหา map_matrix ของ Dense Affine Transformation เพียงแต่ ต้องกำหนดสี่จุด (เพราะว่า สามจุดไม่เพียงพอต่อการกำหนดสี่เหลี่ยมคางหมูได้อีกต่อไป)


Sparse Perspective Transformation

เปิดมาด้วยฟังก์ชันเลย

void cvPerspectiveTransform(
    const CvArr* src,
    CvArr* dst,
    const CvMat* mat
);

โดยที่ถ้า mat เป็น matrix 3x3 จะเป็นการ project ภาพสองมิติไปยังสองมิติ(เนื้อหาในตอนนี้) ถ้าเป็น 4x4 จะเป็นการ project จาก 4 มิติไปยัง 3 มิติ (ยังหาอ่านไม่เจอ)

Learning OpenCV: Convolution (cont)

Canny Edge Detection
แนวคิดของ canny edge detection คือการหาอนุพันธ์เพื่่อหาจุดสุดสุดและต่ำสุดของข้อมูล โดยเชื่่อว่าจุดนั้นคือ edge (ดังที่ได้อธิบายไปในตอนที่แล้ว) ที่นี้ข้อแตกต่างก็คือ ในขณะที่ Laplace ใช้ผลรวมของสองแกน x,y ของ canny หาอนุพันธ์ของแกนสี่แกน (มุมเฉียงอีกสองแกน) วิธีการเรียกก็เหมือนกับ Laplace


void cvCanny(
    const CvArr* img,
    CvArr* edges,
    double lowThresh,
    double highThresh,
    int apertureSize = 3
);

ค่าที่ได้จะเป็น array ของ edge ที่ detect ได้ (ซึ่งสามารถสร้างเป็น contour)
โดยถ้าค่า gradient ที่ได้มากว่า highThresh จะถือว่าเป็น edge ถ้านอ้ยว่า lowThresh จะถือว่าไม่ใช่ edge ค่าที่อยู่ระหว่างนั้น ให้ดู pixel ข้างเคียง โดยถือว่าเป็น edge ถ้าข้อมูลข้างเคียงสูงกว่า highThresh

Hough Transform
เป็นการค้นหาเส้นตรงที่อยู่ในรูปภาพโดยมีแนวคิดที่ว่า จุดใดๆ ในภาพอาจจะเป็นส่วนหนึ่งของเส้นตรงได้
ดังนั้นถ้ากำหนดพารามิเตอร์ของเส้นตรงเช่น เส้นตรงกำหนดได้ด้วย a,b (ความชัน กับ จุดตัดแกน x) ดังนั้น จุดในระนาบ x,y ใดๆ ในภาพก็สามารถ map ไปยังระนาบ a,b ได้ (แน่นอนไม่ได้เป็น one-to-one แต่เป็น one-to-many) เมื่อ map หลายจุดเข้าไป ในระนาบ จุดที่ซ้ำกัน ก็ให้รวมค่าซะ (เราเรียก plane นี้ว่า accumulator plane) ค่าที่เป็น local maximum (เนื่องจากจุดใกล้ๆ เป็นเส้นตรงที่คล้ายๆ กันไม่จำเป็นต้องนับทั้งหมด) ก็ถือว่าเป็นเส้นที่อยู่ในภาพ แต่จริงๆ แล้วการใช้ระนาบ a,b ไม่ค่อยเวิร์คเพราะว่าค่า a มีได้อนันต์ จึงใช้วิธีกำหนดเส้นโดยใช้ polar (ρ,θ) (จริงๆ polar กำหนดเส้นตรงไม่ได้ แต่ในที่นี้กำหนดให้เส้นตรงนั้นตั้งฉากกับมุม θ) ใน OpenCV จะคำนวณค่า local max ในระนาบ   (ρ,θ) ออกมาให้

OpenCV สนับสนุน Hough Line Transform สองชนิด ชนิดแรกคือ standard Hough Transform (SHT) ดังที่กล่าวไปแล้ว อีกชนิด คือ progressive probabilistic Hough Transform (PPHT) โดยใช้ความน่าจะเป็นในการคำนวณ local max โดยไม่จำเป็นต้องคำนวณทุกจุดใน accumulator plane เพราะถือว่าถ้า local max สูงพอ การคำนวณขาดไปบางจุดค่า local max ก็ยังต้องสูงอยู่ดี

CvSeq* cvHoughLines2(

    CvArr* image,
    void* line_storage,
    int method,
    double rho,
    double theta,
    int threshold,
    double param1 = 0,
    double param2 = 0
);

image คือรูปภาพที่จะ transform
line_storage คือที่เก็บผลลัพธ์ อาจจะเป็น memory storage หรือ CvArr ขนาด Nx1 (N คือขนาดมากสุดของผลลัพธ์)
method คือ CV_HOUGH_STANDARD, CV_HOUGH_PROBABILISTIC, หรือ CV_HOUGH_
MULTI_SCALE สำหรับ SHT, PPHT และ multi scale variant ของ SHT
rho, theta คือขนาดของของระนาบ  (ρ,θ)
threshold  คือขนาดที่กำหนดไว้ เพื่อที่จะนับว่าเป็น line ข้อควรระวังคือค่านี้ไม่ normalize เพราะฉะนั้นในกรณีที่รูปภาพใหญ่ขึ้นสำหรับ SHT ค่านี้อาจจะต้องตั้งสูงขึ้น

SHT ไม่ใช้ค่า param1, param2
PPHT ใช้ค่า param1 สำหรับความยาวสั้นสุดของเส้นผลลัพธ์ (สั้นมากก็ไม่น่าจะนับเป็นเส้นตรง) param2 จะเป็นระยะห่างต่ำสุดที่จะไม่เชื่อมเส้นตรงสองเส้นที่อยู่ในแนวเดียวกันด้วยกัน(คือถ้าระยะห่างสั้นกว่า param2 ก็เขื่อมเส้นตรงสองเส้นนี้เป็นเส้นเดียวกันซะ)
multi scale HT ค่า param1, param2 จะใช้ในการ กำหนดรายละเอียดการค้นหาเส้น โดยหลังจากคำนวณหาเส้นแล้วจะทำการ ตรวจสอบผลของเส้นโดยการ เพิ่ม resolution ใน rho ด้วย param1 และ theta ด้วย param2 (อันนี้หนังสืออธิบายว่าผลลัพธ์สุดท้าย rho จะเท่ากับ rho/param1 และ theta จะเท่ากับ theta/param2 ถ้าละเอียดขึ้นมันน่าจะคูณกันนี่นา)

ค่าที่ return จากฟังก์ชัน ขึ้นอยู่กับ พารามิเตอร์ line_storage ถ้าเป็น matrix array ฟังก์ชันจะคืนค่า NULL แล้วค่าของ  (ρ,θ) จะอยู่ใน 2 channel ใน array ถ้าเป็น PPHT จะเป็น array 4 channel เก็บค่า x,y ของจุดต้นและจุดปลายของเส้น ทั้งสองกรณีขนาด rows จะถูกอัพเดตโดยฟังกช์นเองเพื่อให้สอดคล้องกับจำนวนเส้นที่หาได้

ในกรณีที่ line_storage เป็น memory storage ฟังก์ชันจะคืนค่า pointer ไปยัง sequence ตัวอย่างการอ้างถึง line ที่สนใจใน sequence

float* line = (float*) cvGetSeqElem( return_line , i );

return_line คือ pointer ของ sequence ที่ได้มาจากฟังก์ชัน line[0] จะเป็นค่า ρ line[1] จะเป็นค่า θ (สำหรับ SHT, MSHT ในกรณีของ PPHT ต้อง casting ให้เป็น CvPoint)


Hough Circle Transform

เป็นแนวคิดในการหาวงกลมคล้ายๆ กับ การหา Hough Line Transform แต่เปลี่ยนจาก accumulate plane เป็น accumulate volume เพราะต้องการค่า x,y และ r แต่จริงๆ แล้ว OpenCV ไม่ได้ใช้วิธีนี้แต่ใช้วิธีที่เรียกว่า Hough Gradient Method

วิธีการของ Hough Gradient Method คือ นำภาพมาผ่านกระบวนการ edge detection ก่อน(คือ cvCanny) ต่อมาทุกๆ จุดที่ไม่ใช้ 0 ใน edge image จะมาดูค่า gradient (ที่ได้มาจากอนุพันธ์ลำดับแรกใน cvSobel) โดย

1. ทุกจุดบนเส้นนี้(เส้นที่ผ่านจุดใน edge มีความชันทีได้มากจาก gradient โดยมีระยะห่างต่ำสุดและสูงสุดกำหนดไว้ จะถูกเพิ่มใน  accumulator)
2. จุดที่เป็น local max ใน accumulator น่าจะมีสิทธิ์ เป็นจุดศูนย์กลาง นำมาเรียงจากมากไปน้อย
3. ไล่ขนาดวงกลมไปเพื่อให้ตัดจุดที่ไม่ใช้ 0 ใน canny image วงกลมที่ตัดจุดมากพอและห่างจากวงกลมที่เคยหาได้แล้ว จะถูกเก็บ
4. ไล่ไปจนครบทุก candidate ที่จะเป็น center

CvSeq* cvHoughCircles(

    CvArr* image,

    void* circle_storage,
    int method,
    double dp,
    double min_dist,
    double param1 = 100,
    double param2 = 300,
    int min_radius = 0,
    int max_radius = 0
)

image หมายถึง ภาพต้นฉบับ
circle_storage ถ้าเป็น CvArr จะได้ค่ามาเป็น array 3 channel แทน x,y,r ตามลำดับและฟังก์ชันจะคืนค่า NULL ถ้าเป็น memory storage ฟังก์ชันจะคืนค่า pointer ไปยัง sequence (คล้ายๆ อันที่แล้ว)
dp จะกำหนดตัวหารเพื่อลดขนาดของ accumulator image
min_dist เป็นค่าระยะห่างต่ำสุดที่จะแยกว่าวงกลมสองวงเป็นคนละวง
param1 คือ cvCanny threshold (จริงๆ canny ต้องการ threshold สองค่า แต่ cvHoughtCircles จะกำหนดค่าที่สองให้เป็ฯ param1/2)
param2 คือ accumulator threshold
min_radius, max_radius คือรัศมีของวงกลมที่เล็กสุดและใหญ่สุด

Learning OpenCV: Convolution

การ convolution image คือการทำอะไรสักอย่างกับทุกส่วนของ image ในปกติที่ผ่านมา เราะจะใช้ convolution kernel ซึ่งก็คือ อะเรย์ขนาดคงที่ที่มีค่าสัมประสิทธิ์อยู่ และมีจุด anchor point (ปกติจะอยู่ตรงกลาง) ขนาดของ array เราจะเรียกว่า support ของ kernel แน่นอนว่า เราไม่จำเป็นต้องวนลูปจัดการทุก pixel ในภาพ OpenCV ได้เตรียมฟังก์ชันไว้ให้แล้ว

void cvFilter2D(
    const CvArr* src,
    CvArr* dst,
    const CvMat* kernel,
    CvPoint anchor = cvPoint(-1,-1)

);

ค่าทุกอย่างดูตรงไปตรงมาดี ในกรณีของ anchor point ค่า default จะหมายถึงตรงกลาง ของ kernel
ในกรณีที่เราต้องการ convolute เอง เราอาจจำเป็นที่ต้องจัดการเรื่องขอบของภาพเอง โดยใช้คำสั่ง

cvCopyMakeBorder ซึ่งจะขอข้ามไปในรายละเอียด


Sobel
การ convolute ที่กล่าวถึงอันแรกคือ sobel derivative


cvSobel(
    const CvArr* src,
    CvArr* dst,
    int xorder, //0,1,2
    int yorder, //0,1,2
    int aperture_size = 3 //1,3,5,7
);
คื่อการคำนวณอนุพันธ์อันดับ xorder ในแกน x และ yorder ในแกน y

แต่ในความเป็นจริงแล้ว OpenCV ไม่ได้ทำการหาอนุพันธ์แต่ใช้วิธีการประมาณค่าอนุพันธ์เอา ดังนั้นบล็อก kernel ที่ใหญ่กว่าจะให้ค่าที่ถูกต้องมากกว่า (ไม่ความเสี่ยงต่อ noise น้อยกว่า) ใน OpenCV สามารถใช้ filter พิเศษที่เรียกว่า scharr filter โดยกำหนด ค่า CV_SCHARR ให้กับ aperture_size ใน cvSobel

Laplace
OpenCV implement Laplace operator  ไว้เป็นอนุพันธ์ลำดับสองของทั้งแกน x และ y ดูเผินๆ คล้ายๆ กับ sobel ที่ xorder=yorder=2 ซึ่งจริงๆ แล้ว ที่พารามิเตอร์นั้น OpenCV ใช้ Laplace Operator ในการคำนวณ
ลองดูฟังก์ชันจะเห็นว่าคล้ายกับ sobel มาก


void cvLaplace(
    const CvArr* src,
    CvArr* dst,
    int apertureSize = 3
);



ความสำคัญของการใช้ Laplace มา detect edge คือ จากการใช้อนุพันธ์อันดับสอง(ตามนิยาม) จุดที่ได้ค่าเท่ากับศูนย์ เป็นไปได้สามแบบคือ local maximum, local minimum, และเส้นโค้งที่มีความเว้าน้อยมากๆ (เรียกว่าอะไรนะ)  ของอนุพันธ์อันดับหนึ่ง (ตัดกรณีหลังทิ้งไป)

แนวคิดคือภาพน่าจะมีการเปลี่ยนแปลงไม่มากนักแต่จะเริ่มเปลี่ยนแปลงมากขึ้นเมื่อเข้าใกล้ขอบ (ดังนั้นข่วยนี้อนุพันธ์อันดับหนึ่งจะลดลงหรือเพิ่มขึ้น) จนถึงขอบและหลังจากนั้นการเปลี่ยนแปลงจะลดลงเมื่อออกจากขอบ (อนุพันธ์จะเพิ่มขึ้นหรือลดลงเข้าใกล้ศูนย์) ดังนั้นช่วงสูดสุดหรือต่ำสุดน่าจะหมายถึงขอบของภาพ ซึ่งสามารถตรวจสอบได้โดยใช้อนุพันธ์ลำดับสองมาช่วย (ก็ Laplace ไง) ลองดูตัวอย่างในหนังสือ Learning OpenCV ของ OReilly ดู

จากรูปข่วยเส้นสีเทาจะเป็นช่วงที่ อนุพันธ์อันดับสองเป็นศูนย์ที่น่าจะหมายถึงขอบ ซึ่งสัมพันธ์กับ อนุพันธ์ลำดับหนึ่งที่มีค่าสุดสุดหรือต่ำสุด  และในช่วงที่อนุพันธ์อันดับหนึ่งมากกว่า threshold ที่กำหนดไว้ จะหมายถึงค่า strong edge คือมีการเปลี่ยนแปลงถึงขนาดที่เรากำหนด เนื่องจากการเปลี่ยนแปลงเล็กๆ น้อยๆ  ก็อาจจะทำให้เกิด local max, local min ได้ จะต้องกำจัดส่วนนี้ไปด้วย

Learning OpenCV: Threshold

เรื่องสำคัญในการทำ CV อีกเรื่องคือ threshold คงไม่ต้องอธิบายมากับความหมาย เรามาดูวิธีการใช้ดีกว่า
เริ่มต้นที่ definition เช่นเคย

double cvThreshold(
    CvArr* src,
    CvArr* dst,
    double threshold,
    double max_value,
    int threshold_type
);

src คือต้นฉบับ
dst คือผลลัพธ์
double คือ threshold ที่ตั้งไว้
max_value คือค่าคงที่ใช้ในการตั้งค่าผลลัพธ์
threshold_type คือวิธีการคำนวณ threshold ใชัหลักดังนี้ (ให้ M=max_value)

• CV_THRESHOLD_BINARY              dst = (src>T)?M:0
• CV_THRESHOLD_BINARY_INV     dst = (src>T)?0:M
• CV_THRESHOLD_TRUNC               dst = (src>T)?M:src
• CV_THRESHOLD_TOZERO_INV    dst = (src>T)?0:src
• CV_THRESHOLD_TOZERO             dst = (src>T)?src:0

และยังมี adaptive threshold ที่ค่า threshold จะเปลี่ยนค่าเองไปได้เรื่อย ซึ่งจะมีประโยชน์ในกรณีที่ภาพต้นแบบนั้นเจอแสดงแบบ gradient ทำให้ค่าต่างกันมากตาม gradient ของภาพ การเรียกใช้ก็จะคล้ายๆ กัน

void cvAdaptiveThreshold(

    CvArr* src,

    CvArr* dst,

    double max_val,

    int adaptive_method = CV_ADAPTIVE_THRESH_MEAN_C

    int threshold_type = CV_THRESH_BINARY,

    int block_size = 3,

    double param1 = 5

);

ในฟังก์ชันนี้ค่า threshold ที่จุด x,y ใดๆ จะคำนวณมาจาก ค่าเฉลี่ยของ pixel ในสี่เหลี่ยมจัตตุรัสที่มีขนาดกำหนดไว้ใน block_size แล้วลบด้วยค่า param1 โดยการเฉลี่ย pixel นั้นมีสองวิธีกำหนดไว้ใน adaptive_method คือ CV_ADAPTIVE_THRESH_MEAN_C จะถ่วงน้ำหนักเท่ากันทุก pixel ในขณะที่ถ้ากำหนดเป็น CV_ADAPTIVE_THRESH_GAUSSIAN_C จะถ่วงน้ำหนัก pixel โดย ใช้ gaussian function จากระยะห่าง 

Open CV: Resize Image and Image Pyramids

Resize Image

การ resize image ใน OpenCV จริงๆ แล้วไม่น่าจะมีอะไรยุ่งยากในการใช้ ลองดูคำสั่งกันก่อน


void cvResize(
    const CvArr*  src,
    CvArr*           dst,
    int                    interpolation = CV_INTER_LINEAR
);

src, dst คือภาพต้นฉบับและผลลัพธ์โดยดูจากขนาดของภาพใน header (IplImage) ควรระวังการตั้ง ROI ในภาพต้นฉบับ พารามิเตอร์สุดท้ายคือฟังก์ชันในการประมาณค่า interpolate ค่า pixel โดยมีค่าเป็น

1. CV_INTER_NN nearest neighbor
2. CV_INTER_LINEAR Bilinear
3. CV_INTER_AREA Pixel area re-sampling
4. CV_INTER_CUBIC Bicubic interpolation

Image Pyramids

Image pyramids คือ collection ของ image  โดยเริ่มจาก image เริ่มต้นแล้วลดขนาดไปเรื่อยๆ จนถึงจุดที่ต้องการ ในหนังสือกล่าวถึง image pyramid สองแบบคือ gaussian pyramid กับ laplacian pyramid

Gaussian Pyramids จะเริ่มต้นที่ภาพต้นแบบเรียกว่าเลเยอร์ที่ 0 (แทนด้วย G0) เราจะสร้าง เลเยอร์ีที่ G(i+1) จากเลเยอร์ Gi โดยการ convolute Gi ด้วย gaussian kernel แล้วลบแถวคู่และหลักคู่ของภาพออกไป จะได้ภาพที่ขนาดเหลือหนึ่งในสี่ของเดิม ทำได้โดยใช้คำสั่ง

void cvPyrDown(

    IplImage* src,

    IplImage* dst,

    IplFilter filter = IPL_GAUSSIAN_5x5

);

ถ้าต้องการ ขยายภาพขึ้นมาใช้คำสั่ง

void cvPyrUp(

    IplImage* src,

    IplImage* dst,

    IplFilter filter = IPL_GAUSSIAN_5x5

);

แต่ภาพที่ได้จะคำสั่ง cvPyrUp จะไม่เท่ากับภาพก่อนหน้า เพราะว่ามีข้อมูลที่หายไปจากการ down sampling collection ของข้อมูลเหล่านี้จะเรียกว่า Laplicain Pyramids ลองดูรูปภาพตัวอย่างจากหนังสือ Learning OpenCV ของ OReilly

ไอ้ส่วนที่วงสีแดงไว้ผมว่าลูกศรน่าจะกลับทิศนะ

แล้วปัญหาคือไอ้ Image Pyramids นี่เกี่ยวกับ image segmentation ยังไงล่ะ

เขาบอกว่า การทำ image pyramids ทำให้การ segment สามารถ segment ที่ภาพเล็กๆ ก่อนแล้วค่อย map กลับเป็นภาพใหญ่ทีหลัง แน่นอน OpenCV ได้ใส่ฟังก์ชันนี้มาใ้ห้ท่านแล้ว

void cvPyrSegmentation(

    IplImage* src,

    IplImage* dst,

    CvMemStorage* storage,

    CvSeq** comp,

    int level,

    double threshold1,

    double threshold2

);

src, dst คือต้นฉบับและผลลัพธ์(เนื่องจาก OpenCV ใช้ dst ในการคำนวณด้วย ดังนั้นยังไงก็ต้องใส่) int คือจำนวน level ของ pyramids (จะต้องระวังด้วย ว่าขนาดของความกว้างและความยาวของภาพใน src จะต้องหารด้วย 2^(levlel-1) ลงตัว)

stroage เป็น memory storage ที่ OpenCV ต้องการใช้ (รายละเอียดใน Memory Storage)

comp จะเป็น sequence ที่สร้างมาจาก cvPyrSegmentation เป็นข้อมูลเกี่ยวกับ connected component (cvConnectedComp) ซึ่งอธิบายโดย

typedef struct CvConnectedComponent {

    double area;            // พื้นที่ของ component

    CvScalar value;       // สีเฉลี่ยของพื้นที่นั้น

    CvRect rect;           // กรอบสี่เหลี่ยมรอบ component นั้น

    CvSeq* contour;    // ในฟังก์ชัน cvPyrSegmentation ไม่ได้เซต แต่หมายถึง sequence ของ contour(ไว้อธิบายในเรื่อง contour)

};

ลองมาดูตัวอย่างเพื่อความเข้าใจในการ segmentation ด้วย cyPyrSegmentation 

CvMemStorage* storage = cvCreateMemStorage(0);

CvSeq* comp = NULL;

cvPyrSegmentation( src, dst, storage, &comp, 4, 200, 50 );

int n_comp = comp->total;

for( int i=0; i

     CvConnectedComp* cc = (CvConnectedComp*) cvGetSeqElem( comp, i );

do_something_with( cc );

cvReleaseMemStorage( &storage );

จากโคด เราจะได้ sequence ของ connected component ซึ่งส่งต่อให้ฟังก์ชัน do_something_with

Learning OpenCV: more about image segmentation in OpenCV

ต่อจากเรื่อง image morphology ยังมีเรื่องค้างอีกนิดหน่อยเีกี่ยวกับการ segment ข้อมูล
เรื่องการคือการทำ Flood Fill แนวคิดของ flood fill นี้อาจจะเคยเห็นกันมาแล้วบ้างจากโปรแกรมแต่งรูปต่างๆ
คือจะมีเลือกจุดในรูปภาพ (seed point) แล้วทั้ง seed point และจุดรอบข้างที่มีสีเหมือนกัน(หรือใกล้เคียงกันตามกำหนด) จะถูกแทนที่ด้วยสีที่กำหนด และประเด็นคืออะไร จริงๆ แล้วประเด็นสำคัญคือ ผลที่ได้จาก flood ่่fill operation นั้นจะเป็นพื้นที่ๆ ต่อเนื่องกันพื้นที่หนึ่ง เรียกได้ว่าเป็นการ segment ด้วยสี ลองดูการประกาศฟังก์ชัน


void cvFloodFill(
    IplImage* img,
    CvPoint seedPoint,
    CvScalar newVal,
    CvScalar loDiff = cvScalarAll(0),
    CvScalar upDiff = cvScalarAll(0),
    CvConnectedComp* comp = NULL,
    int flags = 4,
    CvArr* mask = NULL
);

พารามิเตอร์จะเป็น img รูปภาพที่จะ fill, seedPoint คือตำแหน่ง seed point  newVal คือสีที่จะ fill loDiff กับ upDiff คือผลต่างค่าที่จะยอมรับได้ที่จะต้องแทนที่สี(หรือว่าเป็นพื้้นที่เดียวกันนั่นเอง) ปกติผลต่างนัั้นจะคำนวณระหว่าง pixel ที่ติดกันยกเว้นถ้ามี flag CV_FLOODFILL_FIXED_RANGE จะคำนวณผลต่างจาก seed point เท่านั้น

CvConnectedComp จะเก็บข้อมูลสถิติเกี่ยวกับพื้นที่ๆ ถูก fill จะยกยอดไปอธิบายในเรื่อง Image Pyramids

mask ถ้ากำหนดจะต้องมีขนาด 1 channel และขนาดกว้างและยาวกว่า img (เพื่อการคำนวณ filter ภายใน) โดย pixel (x+1,y+1) ใน mask จะ map กับ x,y ใน img โดยการทำงาน Flood Fill จะ fill img เฉพาะในส่วนที่ mask ตรงตำแหน่งเป็น 0 

ผลการ Flood Fill สามารถ กำหนดให้ fill ทั้ง  img และ mask หรือ fill เฉพาะ mask อย่างเดียวก็ได้

flag จะประกอบด้วยข้อมูลสามส่วน
        แปดบิทล่าง จะมีค่าเป็น 4,8 ใช้กำหนดทิศทางในการ fill โดย 4 จะเป็นการ fill เฉพาะแนวตั้งและแนวนอนและ 8 จะ fill รอบด้านทั้งแปดทิศ
        แปดบิทกลาง จะกำหนดว่า mask จะถูกกำหนดว่า mask จะถูก fill ด้วยค่าอะไรถ้า set เป็น 0 จะถูก fill ด้วยค่า 1s(127)
        แปดบิดบน จะเป็นการเซตค่า CV_FLOODFILL_FIXED_RANGE (ที่อธิบายไปแล้ว) และ CV_FLOODFILL_MASK_ONLY fill เฉพาะ mask เท่านั้น

ลองยกตัวอย่าง flag ถ้าเราต้องการให้  fill ทั้งแปดทิศ, fill เฉพาะ mask, fill mask ด้วยค่า 47

flag = 8 | CV_FLOODFILL_MASK_ONLY | CV_FLOODFILL_FIXED_RANGE | (47<<8)

(น่าจะไม่มีปัญหา bitwise or และ shift bit ธรรมดา)

Learning OpenCV: Sequences

ประเภทข้อมูล sequence เป็นข้อมูลที่เก็บไว้ใน memory storage (จากตอนที่แล้ว) ตัวมันเองเป็น linked list ชนิดหนึ่งที่ชี้ไปยังโครงสร้างข้อมูลแบบอื่น ลองดูการประกาศ sequence


typedef struct CvSeq {
    int flags; // miscellaneous flags
    int header_size; // size of sequence header
    CvSeq* h_prev; // previous sequence
    CvSeq* h_next; // next sequence
    CvSeq* v_prev; // 2nd previous sequence
    CvSeq* v_next // 2nd next sequence
    int total; // total number of elements
    int elem_size; // size of sequence element in byte
    char* block_max; // maximal bound of the last block
    char* ptr; // current write pointer
    int delta_elems; // how many elements allocated
    // when the sequence grows
    CvMemStorage* storage; // where the sequence is stored
    CvSeqBlock* free_blocks; // free blocks list
    CvSeqBlock* first; // pointer to the first sequence block
}

จะเห็นมีข้อมูลที่สำคัญอยู่คือ total ที่บอกจำนวนในลิสต์ กับ pointer สำหรับ linked list สี่ตัวคือ h_prev, h_next, v_prev, v_next เป็น linked list ที่ชี้ได้สี่ทิศเลยทีเดียว

โดยตามปกติเช่นเดียว linked list ทั่วไป sequence จะสามารถจัดการข้อมูลที่อยู่บนหัวท้ายได้ดีกว่าข้อมูลที่อยู่ตรงกลาง 

โดยปกติ ฟังก์ชันใน OpenCV จะสร้าง sequence ให้เราโดยอัตโนมัติ เราแค่เรียกใช้ sequence ให้ถูกก็พอ ในกรณีที่ต้องการสร้างและลบ sequence เอง ใช้คำสั่งต่อไปนี้


CvSeq* cvCreateSeq(
    int seq_flags,
    int header_size,
    int elem_size,
    CvMemStorage* storage
);

แล้วลบด้วย


void cvClearSeq(
    CvSeq* seq
);



sequence ใช้หน่วยความจำใน memory storage (ที่ผ่าน parameter ใน cvCreateSeq) ในตอนที่ใช้คำสั่ง cvClearSeq หน่วยความจำจะไม่ถูก recycle (อ้างอิงจากตอนที่แล้ว เรื่อง memory storage)


คำสั่งจริงๆ ที่น่าจะใช้ของ sequence น่าจะเป็นการเข้าถึง object ใน sequence มากกว่า ลองดูคำสั่งตัวอย่างในหนังสือ


for( int i=0; itotal; ++i ) {
    CvPoint* p = (CvPoint*)cvGetSeqElem ( seq, i );
    printf(“(%d,%d)\n”, p->x, p->y );
}

จะเป้นการใช้คำสั่ง cvGetSeqElem โดยใส่ sequence เป็นพารามิเตอร์และ index i ที่ต้องการอย่าลืม casting ให้เป็นข้อมูลทีเราต้องการด้วย


คำสั่งอื่นๆ ในการจัดการ sequence จะขอลิสต์ไว้ ต่อไปนี้

คำสั่งในการ ค้นหา element ใน sequence

• cvSeqElemIdx

คำสั่งในการเข้าถึง manipulate sequence

• cvCloneSeq
• cvSeqSlice
• cvRemoveSlice
• cvInsertSlice

การเรียง sequence การแบ่ง sequence และการค้นหาข้อมูลใน sequence

• cvSeqSort
• cvSeqSearch
• cvSeqInvert
• cvSeqPartition

ในฟังก์ชันส่วนนี้จะต้องกำหนดฟังก์ชันสำหรับเปรียบเทียบด้วย เพื่อที่ OpenCV จะได้เข้าใจว่า object สองตัวเรียงกันอย่างไร (เรียงตาม x หรือ y ใครที่เคยเขียน quick sort ใน C น่าจะนึกภาพออก) โดยกำหนดฟังก์ชันในรูปแบบนี้

typedef int (*CvCmpFunc)(const void* a, const void* b, void* userdata );

การใช้ sequence เป็น stack (สองหัวด้วยนะ)

• cvSeqPush
• cvSeqPop
• cvSeqPushFront
• cvSeqPopFront
• cvSeqPushMulti
• cvSeqPopMulti

การแทรก element กลาง sequence

• cvSeqInsert
• cvSeqRemove

การเปลี่ยนขนาด memory block size (จะได้ใช้เหรอ)

• cvSetBlockSize

การแปลงระหว่าง array กับ sequence

• cvCvtSeqToArray
• cvMakeSeqHeaderForArray

ส่วนสุดท้ายคือการอ่านเขียน sequence ซึ่งมีประสิทธิภาพมากกว่าการ insert การ ใช้ฟังก์ชัน cvGetSeqElem โดยใช้วิธีสร้างตัว sequence reader กับ sequence writer ขึ้นมา การจัดการดูแล้วเหมือนการอ่านเขียนไฟล์ใน C

คำสั่งที่เกี่ยวข้องกับ sequence writer

• cvStartWriteSeq
• cvStartAppendToSeq
• cvEndWriteSeq
• cvFluseSeqWriter
• CV_WRITE_SEQ_ELEM
• CV_WRITE_SEQ_ELEM_VAR

คำสั่งที่เกี่ยวข้องกับ sequence reader

• cvStartReadSeq
• cvGetSeqReaderPos
• cvSetSeqReaderPos
• CV_NEXT_SEQ_ELEM
• CV_PREV_SEQ_ELEM
• CV_READ_SEQ_ELEM
• CV_REV_READ_SEQ_ELEM

เนื่องจากการเขียนใน sequence writer น่าจะสำคัญจะอาจจะได้ใช้ เลยยกตัวอย่างในหนังสือมาเสียหน่อย

We will create a writer and append a

hundred random points drawn from a 320-by-240 rectangle to the new sequence.

CvSeqWriter writer;

cvStartWriteSeq( CV_32SC2, sizeof(CvSeq), sizeof(CvPoint), storage, &writer );

for( i = 0; i < 100; i++ )

{

    CvPoint pt; pt.x = rand()%320; pt.y = rand()%240;

    CV_WRITE_SEQ_ELEM( pt, writer );

}

CvSeq* seq = cvEndWriteSeq( &writer );