Teknologi Koreksi Distorsi Halaman

• Memodelkan pose 3D dan kelengkungan untuk mengubah foto dokumen yang melengkung menjadi gambar datar, lalu menyelesaikannya sebagai masalah optimisasi yang menyelaraskan titik acuan teks
• Mengikuti alur seperti Leptonica dan CTM: membagi teks per baris, lalu mencari transformasi koordinat agar baris-baris tampak sejajar dan mendekati horizontal
• Model mencakup vektor rotasi r, vektor translasi t, gradien kelengkungan α, β, serta offset x, y dari span teks, dan meminimalkan galat reproyeksi
• Pipeline berlanjut dari pemotongan batas halaman, deteksi kontur teks, perakitan span, pengambilan sampel titik acuan, pembuatan nilai awal, optimisasi Powell, hingga remapping dengan cv2.remap
• Dalam eksekusi contoh, parameternya 104–600, total waktu eksekusi 5,3–24,8 detik, dan sebagian besar dihabiskan untuk optimisasi, sehingga masih ada ruang peningkatan kecepatan lewat solver atau bahasa terkompilasi

---

Menyelesaikan halaman melengkung sebagai masalah optimisasi

• Skrip lama untuk membuat PDF dari foto tulisan tangan hanya sebatas memakai adaptiveThreshold dan menggabungkan beberapa gambar menjadi PDF, tetapi pada foto dokumen arsip, teks sangat melengkung karena halaman menggulung
• Tujuannya adalah membuat program yang secara otomatis mengubah foto halaman melengkung menjadi gambar dokumen datar
• Kodenya tersedia di GitHub pada page_dewarp

Alur dasar yang diambil dari Leptonica dan CTM

• Koreksi distorsi gambar dokumen adalah masalah yang sudah dikenal, dan juga sudah diimplementasikan di pustaka pemrosesan gambar open source Dan Bloomberg, Leptonica
• Referensi mencakup ringkasan hasil dewarping contest dan makalah terkait Coordinate Transform Model, atau CTM, yang menjadi metode pemenang
• Leptonica dan CTM sama-sama membagi masalah menjadi dua tahap
  • Memisahkan teks per baris
  • Mencari distorsi atau transformasi koordinat agar baris-baris menjadi sejajar dan horizontal
• Implementasi ini merepresentasikan bentuk halaman dengan beberapa parameter
  • r, t: vektor rotasi dan vektor translasi yang menunjukkan orientasi dan posisi 3D halaman
  • α, β: dua gradien yang menentukan kelengkungan permukaan halaman
  • y₁ ... yₙ: offset vertikal dari n span horizontal di atas halaman
  • xᵢ: offset horizontal untuk beberapa titik acuan di dalam tiap span

Permukaan 3D dan galat reproyeksi

• Bentuk 3D halaman direpresentasikan sebagai permukaan yang dibuat dengan menyapu kurva sepanjang sumbu y lokal
• Koordinat horizontal x pada halaman dipetakan menjadi perpindahan arah z pada permukaan, dan penampang horizontal dimodelkan sebagai spline kubik
  • Kedua titik ujung spline dikunci pada 0
  • Bentuk spline ditentukan hanya oleh gradien titik ujung α, β
• Setelah parameter pose dan kelengkungan ditentukan, setiap koordinat (x, y) pada halaman diproyeksikan ke posisi tertentu pada bidang gambar
• Menemukan keypoint dari span teks horizontal pada foto asli, lalu mencari parameter yang meminimalkan galat reproyeksi keypoint, dimulai dari estimasi awal
• Sebelum optimisasi, dengan asumsi tidak ada kelengkungan, titik reproyeksi berada pada garis lurus; setelah optimisasi, titik proyeksi model hampir bertumpuk dengan keypoint yang terdeteksi

Pipeline pemrosesan gambar

• Memotong batas halaman

  • Tidak memakai seluruh gambar; hanya memotong area tengah dengan margin tetap untuk menghindari area tepi yang tidak diperlukan
  • Tidak menggunakan deteksi batas halaman yang cerdas

• Deteksi kontur teks

  • Menerapkan adaptive threshold awal
  • Melakukan morphological dilation) dengan kotak horizontal untuk menghubungkan piksel mask yang berdekatan secara horizontal
  • Melakukan erosion) dengan kotak vertikal untuk menghapus noise setinggi satu piksel
  • Setelah connected component analysis, blob yang terlalu tinggi atau tebal disaring
  • Kontur teks yang tersisa didekati sebagai segmen garis paling sesuai menggunakan PCA

• Pelengkap deteksi garis horizontal

  • Karena sebagian input berbentuk tabel dengan banyak teks vertikal, jika teks horizontal yang terdeteksi tidak cukup, deteksi garis horizontal atau rule juga dicoba

Penyusunan span teks dan sampling titik acuan

• Untuk mengelompokkan kontur yang terdeteksi ke span horizontal yang sama, dibuat kandidat edge untuk semua pasangan kontur dan biayanya dihitung
• Jika dua kontur sangat bertumpang tindih sepanjang arah panjangnya, terlalu jauh, atau sudutnya terlalu berbeda, biayanya ditetapkan menjadi tak hingga
• Biaya edge yang valid dihitung sebagai kombinasi linear antara jarak dan perubahan sudut
• Setelah edge diurutkan berdasarkan biaya, digunakan metode greedy waktu kuadratik yang hanya menghubungkan ketika kedua kontur belum terhubung
  • Karena sebagian besar waktu eksekusi dipakai untuk optimisasi, kompleksitas waktu kuadratik pada tahap ini bukan masalah besar
• Setelah span dibuat, span yang terlalu kecil sehingga tidak membantu menentukan model dihapus
• Karena model parameter memerlukan titik acuan diskret, satu keypoint dipilih kira-kira setiap 20 piksel pada kontur teks

Pembuatan nilai awal dan optimisasi Powell

• Arah rata-rata semua span diestimasi dengan PCA
• Menggunakan komponen utama dari hasil PCA, koordinat awal x, y dan pose halaman datar tanpa kelengkungan ditetapkan secara analitis
• Reproyeksi mengambil offset z dari titik objek dengan menyampling spline kubik, lalu memproyeksikannya ke bidang gambar memakai fungsi OpenCV
  • cv2.solvePnP
  • cv2.projectPoints
• Untuk minimisasi galat reproyeksi digunakan scipy.optimize.minimize dan solver 'Powell'
  • Digunakan sebagai alat optimisasi black-box tanpa turunan
  • Masalahnya sendiri termasuk non-linear least squares
  • Solver lain atau solver non-linear least squares khusus tidak banyak diuji
• Hampir 100% waktu eksekusi program digunakan pada tahap optimisasi ini

Remapping dan pembuatan gambar keluaran

• Setelah optimisasi selesai, hanya r, t, α, β yang dipisahkan untuk membuat transformasi koordinat
• Dewarp yang sebenarnya diperoleh dengan memproyeksikan dense mesh titik halaman 3D menggunakan cv2.projectPoints, lalu meneruskan koordinat gambar tersebut ke cv2.remap
• Hasil akhir disimpan sebagai PNG bi-level menggunakan cv2.adaptiveThreshold dan Pillow

Hasil contoh dan waktu eksekusi

• Repositori GitHub memuat beberapa example images
• Statistik berdasarkan eksekusi pada satu MacBook Pro 2012 adalah sebagai berikut

Input	Spans	Keypoints	Parameters	Waktu optimisasi	Total waktu
boston_cooking_a.jpg	38	554	600	23,3 dtk	24,8 dtk
boston_cooking_b.jpg	38	475	521	18,0 dtk	18,8 dtk
linguistics_thesis_a.jpg	20	161	189	5,1 dtk	6,1 dtk
linguistics_thesis_b.jpg	7	89	104	4,2 dtk	5,3 dtk

• Model terkecil pun memiliki 104 parameter, dan model terbesar 600 parameter, jadi ini bukan masalah optimisasi kecil
• Kecepatan optimisasi bisa ditingkatkan dengan mencoba metode lain atau menggunakan bahasa terkompilasi

Keterbatasan yang tersisa

• Pendekatan keseluruhannya adalah membaca sedikit pengetahuan latar, lalu memformulasikan seluruh masalah sebagai keluaran dari proses optimisasi
• Metode ini mengingatkan pada deformable part models dan active appearance models, tetapi tidak secanggih keduanya
• Leptonica dan CTM mencoba memodelkan serta mengoreksi distorsi horizontal selain distorsi vertikal
• Implementasi ini tidak menangani koreksi distorsi horizontal
  • Karena spline kubik bukan parameterisasi arc-length, teks sedikit terkompresi di area dengan gradien spline besar
  • Karena proyek ini terutama merupakan proof-of-concept, masalah ini tidak dilanjutkan lebih jauh
• Kode final tersedia di repositori GitHub, dan penambahan komentar yang lebih rinci masih belum memadai

[GN⁺]

Komentar Hacker News

• Perlu berhati-hati menerapkan thresholding yang kuat pada output seperti yang dilakukan penulis
  Untuk halaman teks biasa hasilnya cukup bagus, tetapi saya pernah melihat ilustrasi atau catatan kaki kecil di beberapa halaman Google Books menjadi rusak sampai tidak terbaca
  Jika hasil pindai Google Books adalah satu-satunya bahan, ini bisa benar-benar membuat buntu

  • Bukankah thresholding dipakai untuk menemukan titik acuan guna memilih parameter koreksi distorsi?
    Setelah titik acuan ditemukan, sepertinya parameter itu bisa diterapkan ke gambar asli

• Ini sudah 2024, dan saya frustrasi kenapa fitur seperti ini masih belum menjadi bawaan standar di aplikasi pemindai dokumen

  • Di sekolah saya memakai GeniusScan, dan fitur ini ada: https://blog.thegrizzlylabs.com/2024/03/genius-scan-7.16.htm...
  • Sangat bagus
    Adanya model deformasi halaman berdimensi rendah untuk dioptimalkan tampaknya menjadi kunci kenapa metode ini bekerja dengan baik
    Ini masalah yang pas sekali untuk skala YC. Beberapa minggu sampai masuk pasar, dengan biaya peluncuran mungkin sekitar ratusan ribu dolar
    Aplikasi ponsel Apple butuh terlalu banyak penyesuaian manual, dan Microsoft Office Lens / Microsoft Lens mendapat penilaian seperti “tepinya pada akhirnya jadi kacau dan terlihat mengerikan”
    Jadi tampaknya ada pasar untuk produk yang memang bekerja dengan baik, dan exit dengan menjualnya ke kandidat akuisisi yang umum juga terlihat memungkinkan
  • Rasanya Google Drive dulu pernah melakukan ini dengan benar, tetapi dalam beberapa tahun terakhir terasa jauh lebih buruk
  • Manajemen produk mungkin menganggap risiko teknologinya tidak sepadan untuk ditanggung
    Mereka mungkin menilainya terlalu kompleks dan terlalu matematis, lalu memutuskan bahwa jika mereka membuat model yang menelusuri aktivitas media sosial pengguna untuk mengatur waktu notifikasi dengan lebih presisi, metrik pengguna akan lebih baik
    Dalam upaya mengurangi churn, para pengambil keputusan secara ketat membuat keputusan berbasis data
  • vflat bagus untuk keperluan ini

• Setelah John Warnock mundur dari posisi CEO Adobe, ia lebih banyak terlibat di Octavo, perusahaan yang melestarikan buku sejarah langka
  Salah satu tantangan yang mereka hadapi adalah meratakan kelengkungan halaman pindai yang tidak bisa ditekan terbuka
  https://en.m.wikipedia.org/wiki/Rare_Book_Room

• Tulisannya luar biasa
  Ini bisa dijadikan referensi di perusahaan sebagai contoh bagaimana mendokumentasikan proyek teknis dan keputusan-keputusannya secara efektif

• Saat kuliah, saya pernah mencoba membuat aplikasi untuk memindai catatan yang diberi kode warna, tetapi menemui masalah lain
  Warna berubah dari bagian atas ke bawah halaman, sehingga sulit membedakan pena biru dan pena hijau secara andal
  Suatu saat saya harus melihatnya lagi

  • Jika diasumsikan latar putih juga berubah dengan cara yang sama, trik yang bagus adalah menyalin gambar, memberi blur sangat besar, lalu membagi gambar asli dengan versi blur itu
    Dengan begitu perubahan warna/kecerahan frekuensi rendah pada dasarnya hilang
    Ini sering dipakai untuk menghilangkan bayangan saat memotret kertas, dan sepertinya akan bekerja sama baiknya untuk gradasi warna

• Kelihatannya cukup bagus
  Namun model deformasi-nya terasa agak terlalu global
  Sebagian distorsi kertas yang lebih rumit tidak tertangkap oleh model, dan tampak sebagai distorsi sisa pada hasil akhir

• Terjadi error saat instalasi:
  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
  Saya sudah membuat issue di GitHub

• Sangat keren
  Andai ada aplikasi pemindai dokumen yang layak dipakai di mobile. Maksudnya aplikasi yang bagus untuk koreksi distorsi, thresholding, sampai pembuatan PDF
  Saat ini saya terikat pada Adobe Scan yang hasilnya sejauh ini paling lumayan, tetapi koreksi distorsinya tetap cukup buruk

  • Saya dengar Microsoft Lens bagus, tetapi saat dibuka di ponsel saya, aplikasinya langsung macet

• Sangat menarik dibaca
  Sepertinya tulisan dari 2016 yang terlewat oleh saya, dan saya suka karena alurnya jelas: “ada masalah ini, lalu teknik cerdas diterapkan dan menghasilkan solusi yang bekerja dengan baik”
  Secara pribadi saya mungkin tidak akan pernah membutuhkannya, tetapi ini contoh bagus tentang cara menangani masalah dengan baik dan berkompromi seperlunya sesuai keluaran serta batas ekspektasi yang dapat diterima
  Tulisannya juga bagus dan penjelasannya jelas

• Jika tidak perlu menampilkan buku secara visual dan hanya perlu OCR, sepertinya tahap ini bisa dilewati
  Google sudah menyelesaikan masalah ini lebih dari 10 tahun lalu: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
  Jika manuskripnya benar-benar bernilai, koreksi distorsi tanpa kontak juga bisa dilakukan dengan tomografi sinar-X: https://scrollprize.org/tutorial1

  • Kalau begitu, tinggal cari perangkat lunak yang layak dan rekomendasikan
    Yang dari Google memakai perangkat keras, dan pembahasan tomografi sinar-X terasa sangat seperti ChatGPT
    Meski begitu, metode dalam tulisan ini terlihat bagus dan sederhana untuk standar 2016