เทคนิคแก้ไขความบิดเบี้ยวของหน้าเอกสาร

 (mzucker.github.io)
2 คะแนน โดย GN⁺ 2024-05-14 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • โมเดล ท่าทาง 3D และความโค้ง เพื่อแปลงภาพถ่ายเอกสารที่โค้งงอให้เป็นภาพแบน และแก้เป็นปัญหา optimization ที่จัดแนวจุดอ้างอิงของข้อความ
  • ดำเนินตามแนวทางแบบ Leptonica และ CTM คือแบ่งข้อความเป็นรายบรรทัด แล้วหา coordinate transform ที่ทำให้บรรทัดดูขนานกันและใกล้เคียงแนวนอน
  • โมเดลประกอบด้วยเวกเตอร์การหมุน r, เวกเตอร์การเลื่อน t, ความชันความโค้ง α, β, และ offset x, y ของ text span โดยทำให้ reprojection error ต่ำที่สุด
  • Pipeline ประกอบด้วยการครอบขอบหน้าเอกสาร, ตรวจจับ contour ของข้อความ, ประกอบ span, สุ่มจุดอ้างอิง, สร้างค่าเริ่มต้น, Powell optimization, และ remapping ด้วย cv2.remap
  • ในการรันตัวอย่าง มีพารามิเตอร์ 104~600 ตัว เวลารันรวม 5.3~24.8 วินาที โดยเวลาส่วนใหญ่ใช้กับ optimization จึงยังมีโอกาสเพิ่มความเร็วด้วย solver หรือภาษา compiled

แก้หน้าเอกสารที่โค้งงอในรูปแบบปัญหา optimization

  • สคริปต์เดิมสำหรับแปลงภาพถ่ายลายมือเป็น PDF ทำได้เพียงใช้ adaptiveThreshold และรวมหลายภาพเป็น PDF แต่สำหรับภาพถ่ายเอกสารที่เก็บถาวร ข้อความจะบิดงอมากเพราะ การม้วนงอของหน้าเอกสาร
  • เป้าหมายคือสร้างโปรแกรมที่แปลงภาพถ่ายหน้าเอกสารที่โค้งงอให้เป็น ภาพเอกสารแบบแบน โดยอัตโนมัติ
  • โค้ดเผยแพร่ไว้ที่ page_dewarp บน GitHub

แนวทางพื้นฐานจาก Leptonica และ CTM

  • การแก้ความบิดเบี้ยวของภาพเอกสารเป็นปัญหาที่รู้จักกันอยู่แล้ว และมีการ implement ไว้ใน Leptonica ไลบรารีประมวลผลภาพโอเพนซอร์สของ Dan Bloomberg ด้วย
  • เอกสารอ้างอิงมี สรุป ผลการแข่งขัน dewarping และ paper เกี่ยวกับวิธีที่ชนะอย่าง Coordinate Transform Model หรือ CTM
  • Leptonica และ CTM แบ่งปัญหาออกเป็นสองขั้นตอนร่วมกัน
    • แยกข้อความเป็น รายบรรทัด
    • หา การบิดเบี้ยวหรือ coordinate transform ที่ทำให้บรรทัดขนานกันและเป็นแนวนอน
  • implementation นี้แทนรูปร่างภายนอกของหน้าด้วยพารามิเตอร์หลายตัว
    • r, t: เวกเตอร์การหมุนและเวกเตอร์การเลื่อนที่แสดงทิศทางและตำแหน่ง 3D ของหน้า
    • α, β: ความชันสองค่าที่กำหนดความโค้งของพื้นผิวหน้า
    • y₁ ... yₙ: offset แนวตั้งของ span แนวนอน n ช่วงบนหน้า
    • xᵢ: offset แนวนอนสำหรับจุดอ้างอิงหลายจุดในแต่ละ span

พื้นผิวโค้ง 3D และ reprojection error

  • รูปร่าง 3D ของหน้าเอกสารถูกแทนเป็นพื้นผิวที่สร้างจากการกวาดเส้นโค้งไปตามแกน y ภายในระบบพิกัดเฉพาะที่
  • พิกัดแนวนอน x ของหน้าถูกแมปเป็นการกระจัดตามทิศ z ของพื้นผิว และหน้าตัดแนวนอนถูกโมเดลด้วย cubic spline
    • จุดปลายทั้งสองของ spline ถูกตรึงไว้ที่ 0
    • รูปร่างของ spline ถูกกำหนดด้วยความชันปลาย α, β เท่านั้น
  • เมื่อกำหนดพารามิเตอร์ท่าทางและความโค้งแล้ว พิกัด (x, y) แต่ละจุดของหน้าจะถูก project ไปยังตำแหน่งหนึ่งบนระนาบภาพ
  • ค้นหา keypoint ของ text span แนวนอนจากภาพต้นฉบับ และหาพารามิเตอร์ที่ลด reprojection error ของ keypoint ให้ต่ำที่สุด โดยเริ่มจากค่าประมาณเริ่มต้น
  • ก่อน optimization จะสมมติว่าไม่มีความโค้ง ทำให้จุด reprojection อยู่บนเส้นตรง แต่หลัง optimization จุด projection ของโมเดลแทบจะทับกับ keypoint ที่ตรวจพบจริง

Pipeline ประมวลผลภาพ

  • ครอบขอบหน้าเอกสาร

    • ไม่ได้ใช้ภาพทั้งหมด แต่ครอบเฉพาะบริเวณตรงกลางด้วย margin คงที่เพื่อหลีกเลี่ยงพื้นที่ไม่จำเป็นบริเวณขอบ
    • ไม่ได้ใช้การตรวจจับขอบหน้าเอกสารแบบอัจฉริยะ

  • ตรวจจับ contour ของข้อความ

    • ใช้ adaptive threshold ในขั้นแรก
    • ทำ morphological dilation) ด้วยกล่องแนวนอน เพื่อเชื่อมพิกเซล mask ที่อยู่ติดกันในแนวนอน
    • ทำ erosion) ด้วยกล่องแนวตั้ง เพื่อลบ noise สูงหนึ่งพิกเซล
    • หลังทำ connected component analysis จะกรอง blob ที่สูงเกินไปหรือหนาเกินไปออก
    • contour ของข้อความที่เหลือจะถูกประมาณเป็น line segment ที่ fit ดีที่สุดด้วย PCA

  • เสริมการตรวจจับเส้นแนวนอน

    • input บางส่วนเป็นรูปแบบตารางที่มีข้อความแนวตั้งจำนวนมาก ดังนั้นหากตรวจพบข้อความแนวนอนไม่เพียงพอ ก็จะลองตรวจจับเส้นแนวนอนหรือ rule ด้วย

การสร้าง text span และการสุ่มจุดอ้างอิง

  • เพื่อจัดกลุ่ม contour ที่ตรวจพบให้อยู่ใน span แนวนอนเดียวกัน จะสร้าง edge ผู้สมัครสำหรับ contour ทุกคู่และคำนวณต้นทุน
  • หาก contour สองอันซ้อนทับกันมากในทิศตามความยาว อยู่ไกลเกินไป หรือมีมุมต่างกันมาก จะตั้งต้นทุนเป็น อนันต์
  • ต้นทุนของ edge ที่ใช้ได้คำนวณจากผลรวมเชิงเส้นของระยะทางและการเปลี่ยนแปลงของมุม
  • หลังเรียง edge ตามต้นทุน จะเชื่อมต่อเฉพาะเมื่อ contour ทั้งสองฝั่งยังไม่ได้เชื่อมต่อ โดยใช้วิธีแบบ greedy ที่ใช้เวลาเชิงกำลังสอง
    • เนื่องจากเวลารันส่วนใหญ่ใช้กับ optimization ความซับซ้อนเวลาเชิงกำลังสองของขั้นตอนนี้จึงไม่ใช่ปัญหาใหญ่
  • หลังสร้าง span แล้ว จะลบ span ที่เล็กเกินไปจนไม่ช่วยในการกำหนดโมเดลออก
  • เนื่องจากโมเดลพารามิเตอร์ต้องการจุดอ้างอิงแบบไม่ต่อเนื่อง จึงเลือก keypoint หนึ่งจุดต่อ contour ข้อความประมาณทุก 20 พิกเซล

การสร้างค่าเริ่มต้นและ Powell optimization

  • ประมาณทิศทางเฉลี่ยของ span ทั้งหมดด้วย PCA
  • ใช้องค์ประกอบหลักจากผล PCA เพื่อตั้งค่าพิกัด x, y เริ่มต้น และท่าทางของหน้าแบบแบนที่ไม่มีความโค้งในเชิงวิเคราะห์
  • การ reprojection จะสุ่มตัวอย่าง cubic spline เพื่อรับ offset z ของจุดวัตถุ แล้ว project ไปยังระนาบภาพด้วยฟังก์ชันของ OpenCV
    • cv2.solvePnP
    • cv2.projectPoints
  • ใช้ scipy.optimize.minimize และ solver 'Powell' สำหรับลด reprojection error
    • ใช้เป็นเครื่องมือ optimization แบบ black-box ที่ไม่ใช้อนุพันธ์
    • ตัวปัญหาเองจัดเป็น non-linear least squares
    • ไม่ได้ทดลอง solver อื่นหรือ solver non-linear least squares เฉพาะทางมากนัก
  • เวลารันโปรแกรมเกือบ 100% ใช้ในขั้นตอน optimization นี้

Remapping และการสร้างภาพผลลัพธ์

  • เมื่อ optimization เสร็จแล้ว จะแยกเฉพาะ r, t, α, β ออกมาเพื่อสร้าง coordinate transform
  • การ dewarp จริงทำได้โดย project dense mesh ของจุด 3D บนหน้าเอกสารด้วย cv2.projectPoints แล้วส่งพิกัดภาพนั้นให้ cv2.remap
  • ผลลัพธ์สุดท้ายถูกบันทึกเป็น PNG แบบ bi-level โดยใช้ cv2.adaptiveThreshold และ Pillow

ผลลัพธ์ตัวอย่างและเวลารัน

  • repository บน GitHub มี example images หลายภาพ
  • สถิติเมื่อรันบน MacBook Pro ปี 2012 เครื่องเดียวมีดังนี้
อินพุต Spans Keypoints Parameters เวลา optimization เวลารวม
boston_cooking_a.jpg 38 554 600 23.3 วินาที 24.8 วินาที
boston_cooking_b.jpg 38 475 521 18.0 วินาที 18.8 วินาที
linguistics_thesis_a.jpg 20 161 189 5.1 วินาที 6.1 วินาที
linguistics_thesis_b.jpg 7 89 104 4.2 วินาที 5.3 วินาที
  • แม้แต่โมเดลที่เล็กที่สุดก็มีพารามิเตอร์ 104 ตัว และโมเดลที่ใหญ่ที่สุดมี 600 ตัว จึงไม่ใช่ปัญหา optimization ขนาดเล็ก
  • ความเร็วของ optimization อาจปรับปรุงได้ด้วยการลองวิธีอื่นหรือใช้ ภาษา compiled

ข้อจำกัดที่เหลืออยู่

  • แนวทางทั้งหมดคืออ่านความรู้พื้นฐานเล็กน้อย แล้ว formalize ปัญหาทั้งหมดให้เป็น output ของกระบวนการ optimization
  • วิธีนี้ทำให้นึกถึง deformable part models และ active appearance models แต่ไม่ได้ซับซ้อนเท่าทั้งสองอย่าง
  • Leptonica และ CTM พยายามโมเดลและแก้ไข ความบิดเบี้ยวแนวนอน ด้วย ไม่ใช่เพียงความบิดเบี้ยวแนวตั้ง
  • implementation นี้ไม่ได้จัดการถึงการแก้ความบิดเบี้ยวแนวนอน
    • เนื่องจาก cubic spline ไม่ได้เป็นการ parameterize แบบ arc-length ข้อความจึงถูกบีบอัดเล็กน้อยในบริเวณที่ความชันของ spline สูง
    • เนื่องจากโปรเจกต์นี้ส่วนใหญ่เป็น proof-of-concept จึงไม่ได้พัฒนาปัญหานี้ต่อ
  • โค้ดสุดท้ายเผยแพร่ไว้ที่ GitHub repository และยังมีการเสริมคอมเมนต์อย่างละเอียดไม่เพียงพอ

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-05-14
ความคิดเห็นใน Hacker News

  • ควรระวังการใช้ การทำ threshold แบบแรงมาก กับผลลัพธ์เหมือนที่ผู้เขียนทำ
    กับหน้าข้อความทั่วไปมันจับได้ค่อนข้างดี แต่ผมเคยเห็นหลายหน้าใน Google Books ที่ภาพประกอบหรือเชิงอรรถเล็ก ๆ พังจนอ่านไม่ได้เลย
    ถ้าสแกนจาก Google Books เป็นแหล่งข้อมูลเดียว ก็แทบไปต่อไม่ได้เลย

    • การทำ threshold ไม่ได้มีไว้เพื่อหาเกณฑ์อ้างอิงสำหรับเลือก พารามิเตอร์การแก้ความบิดเบี้ยว หรอกหรือ?
      พอหาเกณฑ์อ้างอิงได้แล้ว ก็น่าจะเอาพารามิเตอร์นั้นไปใช้กับภาพต้นฉบับได้

  • นี่ปี 2024 แล้ว แต่ก็น่าหงุดหงิดที่แอปสแกนเอกสารยังไม่ใส่ฟีเจอร์แบบนี้มาเป็นมาตรฐานสักที

    • ที่โรงเรียนผมใช้ GeniusScan และมันมีฟีเจอร์นี้: https://blog.thegrizzlylabs.com/2024/03/genius-scan-7.16.htm...
    • ดีมากเลย
      ดูเหมือนว่าหัวใจที่ทำให้วิธีนี้ใช้ได้ผลคือการมี โมเดลการแปรรูปหน้ากระดาษมิติไม่สูง สำหรับใช้ปรับให้เหมาะที่สุด
      นี่เป็นปัญหาที่เหมาะกับขนาด YC มาก อาจใช้เวลาไม่กี่สัปดาห์ก็ออกสู่ตลาดได้ และต้นทุนเปิดตัวก็น่าจะระดับไม่กี่แสนดอลลาร์
      แอปมือถือของ Apple ต้องปรับด้วยมือมากเกินไป ส่วน Office Lens / Microsoft Lens ของ Microsoft ก็มีคนวิจารณ์ทำนองว่า “ขอบมันสุดท้ายก็เพี้ยนหนักและดูแย่มาก”
      เพราะงั้นจึงน่าจะมีตลาดสำหรับสินค้าที่ใช้งานได้ดีจริง และก็อาจออกทางด้วยการขายให้ผู้เข้าซื้อกิจการที่พบได้ทั่วไป
    • ผมรู้สึกว่า Google Drive เมื่อก่อนเคยทำเรื่องนี้ได้ดี แต่ในช่วงไม่กี่ปีที่ผ่านมากลับแย่ลงมาก
    • เดาว่าฝ่ายบริหารผลิตภัณฑ์คงมองว่าความเสี่ยงทางเทคนิคไม่คุ้มจะรับ
      พวกเขาคงมองว่ามันซับซ้อนและเป็นคณิตศาสตร์เกินไป แล้วตัดสินใจว่าเอาทรัพยากรไปทำโมเดลที่ส่องพฤติกรรมโซเชียลมีเดียของผู้ใช้เพื่อจับจังหวะแจ้งเตือนให้แม่นขึ้นจะช่วยตัวชี้วัดผู้ใช้ได้ดีกว่า
      เป็นการตัดสินใจแบบยึดข้อมูลอย่างเข้มงวดของผู้มีอำนาจตัดสินใจ ระหว่างที่พยายามลด churn
    • vflat ดีสำหรับงานนี้

  • หลังจาก John Warnock ลงจากตำแหน่ง CEO ของ Adobe เขาก็เข้าไปมีส่วนร่วมกับบริษัทอนุรักษ์หนังสือประวัติศาสตร์หายากชื่อ Octavo มากขึ้น
    หนึ่งในโจทย์ที่พวกเขาเจอคือการคลี่ความโค้งของหน้าสแกนที่ไม่สามารถกดให้แผ่ออกได้
    https://en.m.wikipedia.org/wiki/Rare_Book_Room

  • บทความยอดเยี่ยมมาก
    ในบริษัทอาจเอาไปใช้อ้างอิงเป็นตัวอย่างของการบันทึกเอกสารสำหรับโปรเจกต์เทคนิคและการตัดสินใจต่าง ๆ ได้อย่างมีประสิทธิภาพ

  • ตอนเรียนมหาวิทยาลัยผมเคยพยายามทำแอปสแกนโน้ตที่แยกด้วยสี แล้วไปเจอปัญหาอีกแบบ
    สีเพี้ยนจากบนลงล่างของหน้า ทำให้แยก ปากกาสีน้ำเงิน กับ ปากกาสีเขียว ได้ไม่เสถียร
    ไว้สักวันคงต้องกลับไปดูใหม่

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

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

  • ระหว่างติดตั้งเจอข้อผิดพลาด:
    ERROR: Could not find a version that satisfies the requirement cv2>=3.0 (from versions: none)
    ERROR: No matching distribution found for cv2>=3.0
    ผมเปิด GitHub issue ไว้แล้ว

  • เจ๋งมาก
    อยากได้ แอปสแกนเอกสาร ดี ๆ ที่ใช้บนมือถือได้ แอปที่ทำทั้งการแก้ความบิดเบี้ยว การทำ threshold และการสร้าง PDF ได้ดี
    ตอนนี้เหมือนถูกบังคับให้ใช้ Adobe Scan เพราะผลลัพธ์ยังดูดีที่สุดเท่าที่มี แต่ถึงอย่างนั้นการแก้ความบิดเบี้ยวก็ยังค่อนข้างแย่อยู่ดี

    • เคยได้ยินว่่า Microsoft Lens ดี แต่พอเปิดบนมือถือผมมันก็ค้างไปเลย

  • อ่านแล้วน่าสนใจมากจริง ๆ
    เหมือนเป็นบทความจากปี 2016 ที่ผมพลาดไป แต่ชอบที่มันถ่ายทอดภาพรวมแบบ “มีปัญหานี้อยู่ แล้วก็ใช้เทคนิคฉลาด ๆ จนได้วิธีแก้ที่ใช้งานได้ดี” ออกมาได้ชัดเจน
    ส่วนตัวคงไม่มีโอกาสต้องใช้สิ่งนี้ แต่เป็นตัวอย่างที่ดีมากของการรับมือปัญหาอย่างเหมาะสม และยอมประนีประนอมกับผลลัพธ์รวมถึงความคาดหวังในขอบเขตที่รับได้
    เขียนก็ดี อธิบายก็ดี

  • ถ้าไม่จำเป็นต้องแสดงหนังสือในเชิงภาพ และต้องการแค่ทำ OCR ก็น่าจะข้ามขั้นตอนนี้ไปได้
    Google แก้ปัญหานี้ได้ตั้งแต่กว่าสิบปีก่อนแล้ว: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
    ถ้าต้นฉบับมีคุณค่ามากจริง ๆ ก็สามารถแก้ความบิดเบี้ยวแบบไม่สัมผัสด้วยเอกซเรย์คอมพิวเตอร์ได้: https://scrollprize.org/tutorial1

    • ถ้าอย่างนั้นก็ควรหาและแนะนำซอฟต์แวร์ที่ใช้งานได้จริงสักตัว
      ฝั่ง Google ใช้ฮาร์ดแวร์ และเรื่องเอกซเรย์คอมพิวเตอร์ก็มีกลิ่นแบบ ChatGPT มาก
      ถึงอย่างนั้น วิธีในบทความนี้ก็ยังดูดีและเรียบง่ายเมื่อมองตามบริบทของปี 2016