การตรวจจับภาพคนทั้งตัว ด้วย Histogram of Oriented Gradeint และ Support Vector Machines

สมมุติว่าเราต้องการจะเขียนโปรแกรมเพื่อจับภาพคนทั้งตัวให้ได้ผลดังรูปที่1 เราจะมีวิธีการเขียนอย่างไร บทความนี้จะอธิบายลงลึกในรายละเอียดว่ามันทำให้เป็นความจริงได้อย่างไร

รูปที่1แสดง ผลของการทำงานของโปรแกรมที่ต้องการ

OpenCV code: https://sourceforge.net/projects/hogtrainingtuto/
Matlab code: https://github.com/peerajak/HOGSVM

หลักการของมันคือจะต้องมีการทำ Edge Feature Extraction หรือแปลเป็นไทยคือการดึงคุณลักษณะที่เป็นขอบของวัตถุออกมา  จากนั้นเราจะเรียนรู้ตัวแยกแยะเชิงสถิติโดยการป้อนคุณลักษณะของภาพที่ไม่ใช่คนหลายๆภาพ และคุณลักษณะของภาพที่เป็นคนหลายๆภาพ  เราหวังว่าตัวแยกคุณลักษณะทางสถิตินี้หลังจากเรียนรู้แล้ว จะสามารถนำไปแยกแยะว่าในกรอบสี่เหลี่ยมมีคนหรือไม่มีคน

 

รูปที่2 แสดง pipeline ของการใช้ HOG-SVM HOG ทำหน้าที่เป็นตัวแยกคุณลักษณะ และ SVM ทำหน้าที่เป็นตัวแบ่งแยก

ตัวแยกคุณลักษณะในกรณีนี้เราเรียกมันว่า Histogram of Orientation Gradient (HOG)  เราสามารถ Visualize การแยกคุณลักษณะของ HOG ได้ดังรูปที่สาม

รูปที่3 แสดงการทำงานของ HOG  ภาพ RGBของจักรยาน ที่มนุษย์เข้าใจง่ายถูกแปลงให้เป็นBlocks of Edges ซึ่งคำว่า Gradient ของ HOG ก็คือการดึงEdge(ขอบของวัตถุออกมา)ส่วนคำว่า Histogram ก็คือการนับสถิติแบบ histogram ว่าในบริเวณที่สนใจนั้นมีขอบในทิศทางไหนมากกว่ากัน

เรามีภาพคนที่ผ่าน HOG แล้ว npos (n of positives)ภาพ  และเรามีภาพที่ไม่ใช่คนที่ผ่าน HOG แล้วจำนวน nneg ภาพ (n of negatives) เราเรียกHOGของ ภาพที่มีคนว่า positive features และ HOGของภาพที่ไม่มีนว่า negative features เราจะเรียนรู้ตัวแยกแยะทางสถิติอย่างไร?

การเรียนรู้ทางสถิติด้วย SVM เกิดจากความคิดแบบนี้   สมมุติว่าเรามีตัวอย่าง positive เป็นสีเขียวและ ตัวอย่าง negative เป็นสีแดง  เราต้องการหาเส้นแยกแยะสีน้ำเงินที่แบ่งตัวอย่างออกเป็นสองกลุ่ม เพื่อว่าถ้าตัวอย่างทดสอบสีแดงอยู่ในกลุ่มเดียวกับสีแดงสีเขียวในกลุ่มเดียวกับสีเขียว  ตัวแยกแยะตัวนี้จะทำงานแยกแยะได้อย่างถูกต้อง  ตัวอย่างจึงเป็นตัวอย่างในอดีตและตัวอย่างทดสอบจึงเป็นตัวอย่างในอนาคตที่ต้องการเดา เพราะฉะนั้นมันจึงเป็นตัวแยกแยะเชิงสถิติ

รูปที่4 การหาเส้นแบ่งแยกทางสถิติ

 เราทำการแปลง HOG data ให้เป็น vector ขนาด d  สำหรับตัวอย่างตัวที่ $i$ เราแทน $x_i$ คือ HOG data ที่ถูกทำให้เป็นเวคเตอร์ และ $y_i$ คือป้ายแปะว่ามันคือตัวอย่างบวก(positive) หรือ ลบ(negative) โดยถ้าเป็นตัวอย่างบวกให้แทนค่า $y_i=1$ ถ้าเป็นตัวอย่างลบให้แทนค่า $y_i=-1$ หรือเราเขียนเป็นภาษาคณิตศาสตร์ว่า 
\begin{equation*}
(x_i,y_i), \quad x \in \mathbb{R}^d, y \in \{-1,1\}.
\end{equation*}

SVM คือ Support Vector Machine เพื่อที่จะเข้าใจว่า SVM คืออะไร เรามาเข้าใจคำว่า Support Vector กันก่อน มันคืออะไร ขอให้ย้อนกลับไปเรื่อง Linear Algebra เราจะคิดถึง จุด จุดหนึ่งใน $\mathbb{R}^d$ space ว่าเป็น Vector ใน  $d$  dimensional space. Space ของเราเป็น Vector Space ที่ถูก spanned ได้ด้วย Coordinate system of $d$ linearly independent orthogonal basis vectors. ตอนนี้ขอให้เรามาดูปัญหาการหาระยะห่างระหว่างจุดกับเส้นตรงในแบบ Linear Algebra กัน

ถ้าสมการเส้นตรง ใน $d$ dimensional space เป็น

$g(x) = w^T x + w_0  = 0$

แล้ว ระยะห่างระว่างจุด $\mathbf{x}$ (โปรดสังเกตุตัวหนา) ใดๆ ไปยัง เส้นตรง $g(x)=0$ จะต้องวัดตั้งฉาก  นั่นคือจะไปเจอกับเส้น $g(x)=0$ ที่จุด b  ระยะความยาวzจะมีค่าเป็น 
$$z = \frac{|g(\mathbf{x})|}{||w||}$$
 ดูรูป5

 รูป5 แสดงระยะ z ซึ่งวัดความห่าง จาก g(x)=0 ไป $\mathbf{x}$

 โปรดดูพิสูจน์จาก http://www.intmath.com/plane-analytic-geometry/perpendicular-distance-point-line.php 

รูปที่6 การเลือกตัวแบ่งแยกทางสถิติที่ทำให้ระยะห่างจาก positive training sample กับ negative training sample มีระยะห่างเท่ากันคือ $z$

จากรูปที่6 ถ้าตัวอย่างของเราแบ่งแยกด้วยเส้นได้อย่างสมบูรณ์ทุกตัวอย่าง  มันจะต้องมี $z$ ซึ่งทำให้ระยะห่างของpositive training data ตัวที่ใกล้ที่สุดเท่ากับระยะห่างของ negative training data  เส้นที่ถูกเลือกโดยการหาค่า $z$ บนเงื่อนไขนี้ย่อมเป็นเส้นที่แบ่งแยกสองชนิดออกจากกันได้ระยะห่างสูงสุดระยะห่างนี้ต่อไปจะเรียกว่า margin    

เราเรียกตัวที่ใกล้ที่สุดที่ถูกนำมาคำนวน margin ว่า support vectors ซึ่งมีทั้ง positive support vectors และ negative support vectors.  จากภาพระยะของ margin คือ $2z$ ให้ $x_v$ แทน $x$ ที่เป็น support vectors เราจะได้ว่าระยะของ margin $2z = \frac{2|g(x_v)|}{||w||}$  เมื่อเราต้องการหาค่า max margin เราทำได้โดยการ \begin{align}
maximize \quad \frac{2|g(x_v)|}{||w||}\\
\text{such that} \quad y_i (w \cdot x_i + w_0) \ge 1
\end{align}
แต่ $2|g(x_v)|$ เป็นค่าคงที่สำหรับทุก$x_{vi}$, ซึ่งไม่เปลี่ยนคำตอบ $w$ ตอนที่กำลังทำ maximization. ดัังนั้นเราแก้ objective function เป็น \begin{align}
maximize \quad \frac{2}{||w||}\\
\text{such that} \quad y_i (w \cdot x_i + w_0) \ge 1
\end{align}
แต่ว่า มันยังยากอยู่ ถ้าเราแก้เพิ่มอีกหน่อย ให้ใช้ Quadratic Programming (QP) ได้ เราแก้Objective function เพิ่มเติมเป็น \begin{align}
minimize \quad \frac{1}{2}||w||^2\\
\text{such that} \quad y_i (w \cdot x_i + w_0) \ge 1
\end{align}


จากนั้นคุณก็แก้ QP ด้วยวิธีที่อธิบายใน blog ก่อนหน้านี้  http://peerajakwitoonchart.blogspot.com/2017/04/latex-blogger.html

คุณก็จะได้ตัวแยกแยะทางสถิติซี่งสามารถบอกได้ว่ารูปนี้เป็นคนหรือไม่ สมมุติว่าภาพที่ผ่านHOGมาแล้วที่ต้องการตรวจสอบเป็น $x_t$ โดยการตรวจสอบทำได้โดยการ

$g(x_t) = w^T x_t + w_0 $ ถ้า $g(x_t) >0$ เราสรุปว่าเป็นภาพคน หากมิใช่ เราสรุปว่าไม่ใช่คน

 

ผล

Opencv implementation details
Start implement:
1. Using the INRIA person dataset ,
- INRIAPerson/96X160H96/Train/pos
- INRIAPerson/Train/neg
- INRIAPerson/Test/neg
for positive train test set.
2. Prepare the 64x128 images for those picture. For negative image, it is required that the 64x128 randomly cropped from the original image.

3. HogCompute parameter. We will compute the HOG using Opencv HOGDescriptor::compute with the following default parameters.
blockSize =(16,16) blockStride =(8,8) CellSize =(8,8) derivAperture bool =0 gammaCorrection bool=0 histogramNormType =0if = 0 means L2Hys L2HysTheshold =0.2 nbins =9
winSigma =-1 winSize =(64,128) 

4. SVM learn, and classifier. SVMLight is used. Using libsvm/tools/checkdata.py to make sure that the input file to SVM is correctly formated.

5. Compute HOG, train the SVM, test the negative test set with the trained model, put the fault positive to retrain again. (its called hard train)

6. Compute the weight vector of the hard train and use it as  vector<float> getDefaultPeopleDetector()  the trig is we need to put the theshold value from the model added into the last vector position.

7. At detectMultiScale function, change the threshold values,group threshold and hit threshold until u get good result.