การออกแบบอัลกอริทึมสำหรับคัดแยกและค้นหาใบหน้าสุนัข

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

อัลกอริทึมสำหรับสร้างตัวคัดเลือกคุณสมบัติจากรูปใบหน้ำสุนัข 
OverFeat สามารถดึงคุณสมบัติจากรูปภาพได้ โดยจะให้คุณสมบัติทั้งหมด 4,096 คุณสมบัติต่อ 1 รูปภาพ ซึ่งจำนวนที่มากดังกล่าวอาจก่อให้เกิดปัญหามิติของข้อมูลหรือ Curse of Dimensionality เกิดจากการที่มิติข้อมูลไม่ได้ไปในทิศทางเดียวกัน ข้อมูลเกิดการกระจาย บางจุดอาจจะไม่มีข้อมูลอยู่เลย ส่งผลโดยรวมต่อการนำข้อมูลไปใช้ โดยเฉพาะการแบ่งกลุ่มด้วย K-Means ซึ่งให้นำ้หนักทุก ๆ คุณสมบัติเท่ากัน อาจก่อให้เกิดปัญหาการแบ่งกลุ่มโดยข้อมูลไม่มีความสัมพันธ์กันหรือมีความสัมพันธ์ต่ำ จึงต้องทำการลดคุณสมบัติที่ไม่สาคัญออกไปโดยการคัดเลือกคุณสมบัติ ซึ่งสามารถใช้การวิเคราะห์การถดถอยเชิงเส้นหาค่าน้าหนักของแต่ละคุณสมบัติได้ และนำค่าดังกล่าวมาคัดคุณสมบัติที่ไม่มีน้ำหนักหรือมีนำาหนักต่ำออก 
กระบวนการคัดเลือกคุณสมบัติสามารถแบ่งออกได้เป็น 8 ขั้นตอน 
1) การเตรียมรูปภาพใบหน้าสุนัข ซึ่งเป็นรูปใบหน้าสุนัขหน้าตรง โดยยอมให้มีการเอียงของใบหน้าได้แต่ต้องมีองค์ประกอบบนใบหน้าครบ ได้แก่ ตาทั้งสองข้าง หมูก ปาก ซึ่งในที่นี้จะเก็บรูปภาพใบหน้าสุนัข 30 ตัว ที่มีลักษณะแตกต่างกัน จำนวน 30 สายพันธุ์ 



2) ดึงคุณสมบัติจากรูปภาพใบหน้าสุนัขโดยใช้ OverFeat ในการดึงคุณสมบัติ 4096 คุณสมบัติต่อ 1 รูปภาพ จากนั้นนำข้อมูลทั้งหมดเก็บลงฐานข้อมูล โดยเก็บแยกของสุนัขแต่ละตัว 
3) จับคู่และรวมคุณสมบัติ โดยการจับคู่คุณสมบัติของรูปใบหน้าสุนัข 2 รูป รูปละ 4096 คุณสมบัติ รวมเป็น 8192 คุณสมบัติ การจับคู่ในขั้นตอนนี้จะแบ่งออกเป็น 2 แบบคือ การจับคู่ที่ถูกต้อง เป็นการจับคู่คุณสมบัติของสุนัขตัวเดียวกัน และการจับคู่ที่ไม่ถูกต้อง เป็นการจับคู่คุณสมบัติของสุนัขคนละสายพันธุ์ โดยการจับคู่ที่ถูกต้องจะกำหนด class เป็น 1 ส่วนการจับคู่ที่ไม่ถูกต้องจะกาหนด class เป็น 0 
4) สุ่มการจับคู่ โดยรักษาอัตราส่วนระหว่างการจับคู่ที่ถูกต้องและการจับคู่ที่ไม่ถูกต้องให้เท่ากัน เพื่อลดความผิดพลาดของการสร้างโมเดล เนื่องจากเน้นที่การนำค่าน้ำหนักที่ได้จากโมเดลมาใช้เป็นสำคัญ 
5) นำคุณสมบัติที่ถูกจับคู่ทั้งหมดมาสร้างโมเดลโดยใช้การวิเคราะห์การถดถอยเชิงเส้น ซึ่งเราจะได้ค่าน้ำหนักหรือสัมประสิทธิ์ (coefficient) ของคุณสมบัติแต่ละตัว 
6) นำคุณสมบัติทั้งหมดมาผ่านการกรอง ค่าน้ำหนักของคุณสมบัติใดไม่ถึงเกณฑ์ที่กำหนดจะถูกคัดออก คงเหลือเฉพาะคุณสมบัติที่สำคัญเท่านั้น 
7) นำคุณสมบัติของสุนัขทั้งหมดมาสร้างโมเดลโดยใช้อัลกอริทึมการวิเคราะห์องค์ประกอบหลัก (Principal Component Analysis: PCA) โดยกำหนดให้อัตราการรักษาองค์ประกอบอยู่ที่ร้อยละ 90 
8) นำคุณสมบัติของสุนัขทั้งหมดมาผ่านการแปลงปริภูมิ (Dimensional Transformation) เพื่อลดปริภูมิ ส่งผลโดยตรงต่อการลดจำนวนคุณสมบัติ 



อัลกอริทึมสำหรับคัดแยกใบหน้ำสุนัขตำมกลุ่มที่มีลักษณะใบหน้ำคล้ำยกัน 


ในขั้นตอนนี้ จะนำข้อมูลของรูปใบหน้าสุนัขทั้งหมดที่ผ่านขั้นตอนการดึงคุณสมบัติและขั้นตอนการคัดเลือกคุณสมบัติแล้วมาสร้างตัวคัดแยกขึ้นมาเพื่อใช้คัดแยกรูปใบหน้าสุนัขให้อยู่ในกลุ่มที่มีลักษณะใบหน้าที่คล้ายกัน แบ่งออกเป็น 4 ขั้นตอน 
1) การแบ่งกลุ่มด้วยอัลกอริทึม Affinity Propagation 

2) ขั้นตอนการแบ่งข้อมูล ในขั้นตอนนี้จะแบ่งข้อมูลออกเป็น 2 ชุด ได้แก่ชุดข้อมูลฝึกและชุดข้อมูลทดสอบ โดยจะนำชุดข้อมูลฝึกไปใช้ในกระบวนการสร้างโมเดล และนำชุดข้อมูลทดสอบไปใช้ในกระบวนการทดสอบและประเมินโมเดล เพื่อป้องกันการเกิดปัญหา overfitting โดยข้อมูลของสุนัข 1 ตัว จะถูกแบ่งออกเป็น 2 ส่วน ด้วยอัตราส่วนชุดฝึกและชุดทดสอบ 7:3 ส่วน 
3) ขั้นตอนการสร้างโมเดลหรือตัวคัดแยก นำชุดข้อมูลฝึกมาสร้างโมเดล 
4) ขั้นตอนทดสอบและประเมินโมเดล เป็นขั้นตอนในการนำชุดข้อมูลทดสอบซึ่งยังไม่เคยผ่านตัวคัดแยก นำมาป้อนและตรวจสอบผลลัพธ์ที่ได้ หากค่าความถูกต้องไม่ถึงเกณฑ์ จะต้องมีการปรับพารามิเตอร์ของโมเดลหรือปรับปรุงคุณภาพของข้อมูลเพื่อให้ได้ค่าความถูกต้องเพียงพอสำหรับการทำงานกับข้อมูลจริง 


อัลกอริทึมสำหรับค้นหาใบหน้ำสุนัขที่มีลักษณะคล้ำยที่สุด 


เราสามารถค้นหาใบหน้าสุนัขที่มีลักษณะคล้ายกันได้โดยอาศัยคุณสมบัติที่มีค่าต่างกันของแต่ละรูปใบหน้าสุนัข ด้วยหลักการคือยิ่งลักษณะใบหน้าสุนัขบนรูปภาพมีความคล้ายกันมากเท่าใด ความแตกต่างของคุณสมบัติก็ยิ่งน้อยลง ซึ่งสามารถดำเนินการได้ด้วยการวิธีการค้นหาเพื่อนบ้านใกล้เคียงหรือ Nearest Neighbor Search โดยใช้อัลกอริทึมการหาระยะทางยูคลิเดียนในการหาระยะบนปริภูมิระหว่างจุดที่ต้องการ (Query point) ซึ่งก็คือรูปใบหน้าสุนัขสูญหาย เทียบกับทุก ๆ จุดบนปริภูมิซึ่งก็คือใบหน้าสุนัขที่มีในระบบ โดยจะได้เป็นระยะออกมา ยิ่งระยะของจุดใด ๆ เทียบกับจุดที่ต้องการเข้าใกล้ศูนย์ ค่าความคล้ายก็จะเพิ่มขึ้นมากเท่านั้น แต่เนื่องจากข้อมูลของสุนัขในระบบมีจำนวนมากและเพิ่มขึ้นเรื่อย ๆ ตามจานวนผู้ใช้ที่เพิ่มขึ้น จึงจาเป็นต้องแบ่งออกเป็นกลุ่มแยก ๆ ตามลักษณะความคล้ายแล้วจึงใช้ NSS ในการหารูปภาพใบหน้าสุนัขที่คล้ายกัน เพื่อลดระยะเวลาการทางานของอัลกอริทึมลง เนื่องจากการเทียบทุก ๆ จุดข้อมูลจะทำให้ใช้เวลานาน 



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



การทำงานของอัลกอริทึมแบ่งออกเป็น 6 ส่วน 
1) ตัวดึงคุณสมบัติจากรูปภาพ (Feature Extractor) ทำหน้าที่ดึงคุณสมบัติออกมาจากรูปภาพที่ใส่เข้าไปซึ่งก็คือรูปภาพใบหน้าสุนัข โดยจะให้คุณสมบัติทั้งหมด 4,096 คุณสมบัติ 
2) ตัวคัดเลือกคุณสมบัติ (Feature Selector) ทำหน้าที่กรองคุณสมบัติที่ไม่สำคัญหรือไม่มีน้ำหนักเพียงพอตามค่าที่กำหนด โดยข้อมูลชุดหนึ่งจะส่งให้ตัวคัดแยก (Classifier) อีกชุดหนึ่งจะส่งให้เครื่องมือค้นหารูปภาพสุนัขเหมือน (Nearest Neighbor Search Engine) ซึ่งข้อมูลทั้งสองชุดเป็นข้อมูลเดียวกัน 
3) ตัวคัดแยก (Classifier) ทำหน้าที่คัดแยกคุณสมบัติที่ได้รับจากตัวคัดเลือกคุณสมบัติว่าอยู่ในกลุ่มใด โดยจะให้ชื่อกลุ่ม (class หรือ label) เป็นผลลัพธ์ออกมา 
4) ตัวดึงคุณสมบัติของรูปภาพใบหน้าสุนัข (Dog Face Features Inquirer) ทำหน้าที่ค้นหากลุ่มของคุณสมบัติที่ถูกระบุจากตัวคัดแยกในฐานข้อมูลใบหน้าสุนัข (Dog Faces Database) ซึ่งก็คือกลุ่มของใบหน้าสุนัขที่มีลักษณะคล้ายกัน โดยจะส่งให้เครื่องมือค้นหารูปภาพใบหน้าสุนัขเหมือน (Nearest Neighbor Search Engine) 
5) เครื่องมือค้นหารูปภาพใบหน้าสุนัขเหมือน (Nearest Neighbor Search Engine) เป็นเครื่องมือเปรียบเทียบคุณสมบัติ โดยจะหาคุณสมบัติที่ได้จากตัวดึงคุณสมบัติของรูปภาพใบหน้าสุนัขที่มีความใกล้เคียงกันกับคุณสมบัติที่ได้จากตัวคัดเลือกคุณสมบัติมากที่สุดตามจำนวนที่ถูกกำหนด จากนั้นจะส่งรายชื่อของรูปภาพที่มีคุณสมบัติใกล้เคียงไปให้ตัวดึงรูปภาพใบหน้าสุนัข (Dog Face Photo Inquirer) 
6) ตัวดึงรูปภาพใบหน้าสุนัข (Dog Face Photo Inquirer) จะทำหน้าที่ค้นหารูปภาพใบหน้าสุนัขจากฐานข้อมูลใบหน้าสุนัขตามที่กำหนดในรายชื่อที่ได้รับจากเครื่องมือค้นหารูปภาพใบหน้าสุนัขเหมือน และส่งกลุ่มของรูปใบหน้าสุนัขเหมือนออกเป็นผลลัพธ์ 




Comments

Popular posts from this blog

ER diagram

ทฤษฏีที่เกี่ยวข้อง

บทสรุปและข้อเสนอแนะ