Recognizing broken characters in historical documents and solving other set-partitioning problems

Abstract

ในงานวิจัยนี้ เราเน้นการแก้ปัญหาของการรู้จำตัวอักษรขาด (Broken Characters Recognition) ที่ปรากฏเป็นจำนวนมากในเอกสารทางประวัติศาสตร์ ปัจจุบันระบบการรู้จำตัวอักษร (OCR) ส่วนใหญ่จะถูกออกแบบให้จัดการกับเอกสารสิ่งพิมพ์ที่มีตัวอักษรทั้งไทยและอังกฤษได้ผลเป็นอย่างดี อย่างไรก็ตามเมื่อนำมาทดสอบกับเอกสารที่มีปัญหาเช่น เก่า เหลือง ตัวอักษรขาด ประสิทธ์ผลในความแม่นยำของระบบจะลดลงอย่างมากโดย เฉพาะกรณีของตัวอักษรขาดและไม่สมบูรณ์ แม้มนุษย์เราจะสามารถอ่านตัวหนังสือที่มีตัวอักษรขาดได้ไม่ยากนัก แต่สำหรับคอมพิวเตอร์แล้วก็เป็น เรื่องที่ค่อนข้างจะยุ่งยากด้วยความไม่สมบูรณ์ของตัวอักษร ในงานวิจัยนี้ เราจะได้นำเสนอวิธีการแบ่งเซทเหมาะที่สุด (Optimal Set-Partition) ในการจัดการกับตัวอักษรขาดที่เกิดขึ้นในเอกสารโดยทั่วไป เพื่อไห้ได้ผลลัพธ์ที่ดีด้วยแบบของฟังก์ชันความน่าจะเป็น (Probability Functions) นอกจากนี้เพื่อไห้ได้ผลลัพธ์ที่ดีขึ้นในเรื่องความถูกต้องแม่นยำ เราจะตรวจคำศัพท์ของผลลัพธ์กับคำที่มีในพจนานุกรมด้วยการสร้างเอ็นแกรมกราฟ (N-grams Graph) เมื่อได้ทำการทดสอบประสิทธ์ผลของระบบงานด้วยเอกสารทางประวัติศาสตร์ฉบับภาษาไทย ฉบับภาษาอังกฤษ และฉบับโทรสารภาษาไทย พบว่าความแม่นยำอยู่ในเกณฑ์ที่น่าพอใจจึงมีความเชื่อว่าผลงานนี้จะเป็นประโยชน์ต่องานการเก็บรักษาเอกสารทางประวัติศาสตร์ ของไทยและของต่างประเทศที่มีตัวอักษรขาดปรากฏโดยทั่วไป การศึกษาหาผลลัพธ์ที่เหมาะที่สุดสำหรับปัญหาของการแบ่งเซทนั้น วิธีการที่ง่ายและตรงที่สุดเห็นจะเป็นการแยกประเมินทีละส่วนจากหัวจดท้ายจนหมดรายการ แต่วิธีนี้ต้องใช้เวลามากและไม่เหมาะสมในกรณีที่ขนาดเซทเพิ่มมากขึ้นซึ่งจะทำให้ได้คำตอบที่ช้ามากจนไม่สามารถนำไปใช้ได้ในทางปฏิบัติ ในงานวิจัยนี้เราจึงได้นำเสนออัลกอริทัมใหม่ด้วยการขยายการแบ่งส่วน (Partition-Growing) ที่สามารถแบ่งเซทได้อย่างดีที่สุดของตัวอักษรขาดภายในช่วงเวลาอันสั้น โดยอาศัยคุณลักษณะเฉพาะของฟังก์ชันความน่าจะเป็นเป็นตัวหลักในการแก้ปัญหา นอกจากนี้เรายังนำอัลกอริทัมนี้ไปแก้ปัญหาอื่นๆที่เกี่ยวกับการแบ่งเซท (SPP) ทั้งที่เป็นลักษณะเชิงเส้นและไม่เชิงเส้น ด้วยแบบจำลองตัวระบบของฟังก์ชันความน่าจะเป็น ผลการทดลองพบว่าอัลกอริทัมนี้ทำงานอย่างได้ผลสำหรับปัญหาของการแบ่งเซทที่ดีที่สุดจริง