Non-maximum suppression using python

Improve the image sliding window for object classification model

หลังจากที่ได้ Implement sliding window สำหรับรูปภาพในตอนก่อนหน้านี้ Function ที่เขียนออกไว้ดูเหมือนยังใช้งานไม่ได้ดีกับข้อมูลจริง เพราะยังมีโจทย์ที่ต้องแก้ไขก่อนนำไปใช้งาน ซึ่งเป็นเนื้อหาทั้งหมดใน Blog ตอนนี้

Issue

ปัญหาที่เกิดขึ้นจากการทำ Sliding window ใน Object detection model คือในหลายครั้งที่ Window สามารถ Detect object เดิมได้มากกว่า 1 ครั้ง ตัวอย่างที่เห็นได้ชัดจากรูปทางซ้ายคือ Sliding window บอกว่าสามารถ Detect object ได้ทั้งหมด 3 Objects จากกล่องสีแดงที่วาดขึ้น โดยที่เป้าหมายของ Object detection model คือต้องการผลลัพธ์เป็นเหมือนรูปด้านขวา

การที่โมเดลสามารถ Detect objects ได้ทั้ง 3 อย่างแตกต่างกันคือ Decision confidence หมายความว่าความมั่นใจที่มีต่อทั้ง 3 Objects มีความแตกต่างกัน สมมติให้ทั้ง 3 ผลลัพธ์มี Confidence อยู่ที่ 75%, 85% และ 90% ตามลำดับ

ถ้าเป็นโจทย์จากรูปนี้ สามารถแก้ไขได้อย่างง่ายคือการเพิ่ม Decision confidence threshold ให้ไม่ต่ำกว่า 90% ก็สามารถลดผลลัพธ์ให้เหลืออยู่เพียง 1 คำตอบได้แล้ว

แต่ปัญหาที่อาจเกิดขึ้นตามมาคือ หากมีรถมากกว่า 1 คันในรูปภาพนี้ แล้ว Decision confidence มีค่าไม่ถึง Threshold ที่ตั้งไว้ที่ 90% (70% < 90%) ดังนั้นรถคันดังกล่าวจึงไม่ได้ถูก Model ตรวจจับได้ สิ่งที่เกิดขึ้นนี้เรียกว่า False Negative (FN)

ต่อมาเพื่อแก้ไขให้โมเดลสามารถ Classify รถได้ทั้ง 2 คัน อาจลด Threshold ลดมาให้เหลือที่ 65% แน่นอนว่าสิ่งที่เกิดขึ้นคือ Model สามารถ Detect รถคันที่ 2 ได้ แต่ก็จะ Sensitive กับวัตถุอื่นด้วยเช่นกัน สิ่งที่เกิดขึ้นนี้เรียกว่า False Positive (FP)

ปรากฎการณ์หรือ Process ทั้งหมดที่เกิดขึ้นนี้เรียกว่า Trade-off Sensitivity and Specificity คือเมื่อเพิ่ม Sensitivity ให้มากขึ้นความ Specificity ก็จะลดลง หรือเมื่อเพิ่ม Specificity ให้มากขึ้นความ Sensitivity ก็จะลดลงเช่นกัน การเลือก Decision confidence threshold ให้มีความ Balance จึงเป็นเรื่องสำคัญ สิ่งที่มีค่ามากกว่า Threshold ที่ได้ตั้งไว้ เรียกว่า True Positive (TP) ซึ่งถือว่าเป็นผลลัพธ์จาก Model ทั้งหมด

การใช้งาน Sliding window กับ Classification model ตรง ๆ อาจเกิด True Positive มากเกินไป และทำให้เกิดความผิดพลาดขึ้นได้ง่ายตามตัวอย่างให้ไว้ ดังนั้น Non-maximum suppression จึงเป็น Algorithm ที่เข้ามาช่วยจัดการในเรื่องนี้

Non-maximum suppression

Non-maximum suppression เป็นการนำเอาผลลัพธ์ที่เป็น True Positive ทั้งหมด แล้วลบ Duplicate ออกจากผลลัพธ์ให้เหลือเป็นผลลัพธ์เดียว

ตัวอย่างเช่นเลือก Decision confidence threshold ที่ 70% ดังนั้น True Positive จึงมีทั้งหมด 4 ค่าตาม Confidence% 70%, 75%, 85% และ 90%

การหาพื้นของ True Positive สามารถบอกได้ด้วย IoU (Intersection over Union) จากสูตรด้านบน IoU คือการอัตราส่วนของพื้นที่ระหว่างพื้นที่ True Positive ที่ต้องวาดขึ้นมาใหม่จาก Array ของ True Positive ทั้งหมด ส่วนด้วยพื้นที่ของ Area ทั้งหมด

Image example

ใช้รูปไพ่อย่างง่าย เพื่อเป็นตัวอย่างสำหรับการเขียน Code ด้วย Python สิ่งต่อไปที่ต้องมีคือ Object ที่ต้องการ Detect

ใน Blog ตอนนี้ยังไม่ได้มี Classification model เข้ามาเกี่ยวข้อง ดังนั้นจึงขอใช้เป็นรูป Heart ที่อยู่ตรงกลางไพ่เป็น Target หรือวัตถุที่ต้องการ Detect

ใช้โปรแกรม crop รูปออกมาตรง ๆ ไม่ได้สร้างจาก model

ใช้ cv2.matchTemplate() เพื่อทำการ Matching รูปภาพไพ่ทั้งภาพกับรูปภาพของ Target (Object) เป็นเหมือนการจำลองว่าให้มีการหา Object จากภาพใหญ่ที่มีค่าใกล้เคียงกันด้วย Correlation

สังเกตที่จุดกลางภาพที่มีสีแตกต่างจากบริเวณอื่น คือจุดที่เกิด Correlation ขึ้นมากที่สุด เพราะเป็นรูปเดียวกัน เพียงแค่ Crop ออกมาเป็น 2 รูป เลยเกิด Correlation ขึ้นได้ง่าย แต่กรณีแบบนี้อยากไม่ได้เกิดขึ้นเมื่อใช้ Model

Implement with python

เมื่อได้ Logic ที่ต้องการแล้ว สามารถนำไป Implement ด้วย Python ต่อได้ โดยสิ่งที่ต้องทำต่อคือการ Extract array (x, y, x + w, y + h) ที่ผ่าน Correlation threshold ออกมาทั้งหมด

นำ Correlation ที่หาได้จาก cv2.matchTemplate() ที่อยู่ในรูป Array 2 มิติ มาเทียบกับ Threshold ที่ตั้งไว้ ใช้ np.where() หา Index 2 มิติ (y, x) ที่ Correlation มากกว่า Threshold จากนั้นสร้างกรอบจาก Index ด้วยการบวก Height และ Width ด้วยค่าของขนาด Target และเก็บค่าเป็น Array ในลักษณะ [x1, y2, x1 + w (x2), y1 + h (y2)]

ใช้งาน Function ด้วย Threshold เท่ากับ 75%

Total boxes found: 102

จากผลลัพธ์ที่บอกว่าเจอ Target (Boxes) ทั้งหมด 102 กล่อง ลองวาดผลลัพธ์ออกมาเพื่อให้เห็นภาพการทำงานของ Function

เห็นได้ว่ามีการตีกรอบที่ Heart ทั้งหมด 102 ครั้ง (เป็นเส้นหนา) ตาม Array ที่มีค่ามากกว่า Correlation threshold ทั้งหมด

เมื่อได้เป็น Array ของสิ่งที่คาดว่าคือผลลัพธ์ทั้งหมดแล้ว ให้นำ Array ทั้งหมดนั้นทำ Non-maximum suppression เพื่อทำให้ได้ผลลัพธ์เป็น Array เดียว ผ่านจุด [x1, y2, x1 + w (x2), y1 + h (y2)] ทั้งหมดเข้าไปใน Function แล้วหาพื้นที่สี่เหลี่ยมทั้งหมดออกมา +1 เพราะต้องการให้อย่างน้อยมี 1 Pixel ในกรณีที่ด้านกว้างลบด้านยาว แล้วได้แค่เป็น 0

หาจุด x และ y ใหม่โดยที่ xx1, yy1 หาเป็นค่า Maximum ส่วน xx2, yy2 ใช้เป็นค่า Minimum เพื่อให้ได้พื้นที่ที่ตรง Object ที่สุด (ตามรูปกราฟด้านบน) ต่อมาให้หา Height และ Width ใหม่ จาก x และ y ใหม่ จากนั้นคำนวณพื้นที่สี่เหลี่ยมจาก Height และ Width ใหม่

ใช้พื้นที่สี่เหลี่ยมหา IOU โดยค่าที่เกินกว่า Threshold ให้ลบ Array นั้นออกไปถือว่าไม่ใช่คำตอบ

Final box found with Non-Maximum Suppression: [171 267 250 360]

วาดกรอบสี่เหลี่ยมจาก Array ที่เป็นผลลัพธ์ Array เดียว

ผลลัพธ์ที่ได้จากการทำ Non-maximum suppression

Conclusion

จากที่เขียนมาทั้งหมด 3 ตอน ดูเหมือนว่า Materials สำหรับ Object detection model จะพร้อมแล้ว ตอนต่อไปการเป็น Integrate เนื้อหาที่เขียนมาทั้งหมด 3 ตอน (ในช่วงนี้) รวมกันให้เป็น Object detection model ขึ้นมาจริง ๆ เสียที

statisticalModel/nonMaximumSuppression.ipynb at main · naenumtou/statisticalModel

สำหรับ Colab notebook ประกอบเนื้อหา Blog ตอนนี้ สามารถดูได้จาก Link ด้านบน