Sayfa çarpıklığını düzeltme teknolojisi

• Eğrilmiş bir belge fotoğrafını düz bir görüntüye dönüştürmek için 3B poz ve eğriliği modeller; metin referans noktalarını hizalayan bir optimizasyon problemi olarak çözer
• Leptonica ve CTM gibi metni satır bazında ayırdıktan sonra, satırların paralel ve yataya yakın görünmesini sağlayacak koordinat dönüşümünü bulma akışını izler
• Model; dönüş vektörü r, öteleme vektörü t, eğrilik eğimleri α, β, metin span’lerinin x, y ofsetlerini içerir ve yeniden izdüşüm hatasını en aza indirir
• Pipeline; sayfa sınırını kırpma, metin konturu algılama, span oluşturma, referans noktası örnekleme, başlangıç değerleri üretme, Powell optimizasyonu ve cv2.remap ile yeniden eşlemeyle ilerler
• Örnek çalıştırmalarda parametre sayısı 104–600, toplam çalışma süresi 5,3–24,8 saniyeydi; sürenin çoğu optimizasyona harcandığı için solver veya derlenen bir dille hız iyileştirmesi için alan kalıyor

---

Eğrilmiş sayfayı bir optimizasyon problemi olarak çözmek

• El yazısı fotoğraflarını PDF’ye dönüştüren mevcut betik yalnızca adaptiveThreshold uygulama ve birden fazla görüntüyü PDF’de birleştirme düzeyindeydi; ancak arşiv belgelerinin fotoğraflarında sayfa kıvrılması nedeniyle metinler ciddi şekilde bükülüyordu
• Amaç, eğrilmiş bir sayfa fotoğrafını otomatik olarak düz bir belge görüntüsüne dönüştüren bir program oluşturmaktı
• Kod GitHub’daki page_dewarp deposunda yayımlanmıştır

Leptonica ve CTM’den alınan temel akış

• Belge görüntülerindeki çarpıklığı düzeltme zaten bilinen bir problemdir ve Dan Bloomberg’in açık kaynak görüntü işleme kütüphanesi Leptonica içinde de uygulanmıştır
• Referanslar arasında dewarping contest sonuçlarının özeti ve kazanan yöntem olan Coordinate Transform Model, yani CTM ile ilgili makale yer alır
• Leptonica ve CTM problemi ortak biçimde iki aşamaya ayırır
  • Metni satır bazında ayırır
  • Satırların paralel ve yatay olmasını sağlayacak çarpıtmayı veya koordinat dönüşümünü bulur
• Bu uygulama sayfanın şeklini birden fazla parametreyle ifade eder
  • r, t: sayfanın 3B yönelimini ve konumunu gösteren dönüş vektörü ve öteleme vektörü
  • α, β: sayfa yüzeyi eğriliğini belirleyen iki eğim
  • y₁ ... yₙ: sayfa üzerindeki n adet yatay span’in dikey ofsetleri
  • xᵢ: her span içindeki çeşitli referans noktaları için yatay ofsetler

3B eğri yüzey ve yeniden izdüşüm hatası

• Sayfanın 3B biçimi, yerel y ekseni yönünde bir eğriyi süpürerek oluşturulan bir yüzey olarak ifade edilir
• Sayfanın yatay koordinatı x, yüzeyin z yönündeki yer değiştirmesine eşlenir; yatay kesit ise kübik spline ile modellenir
  • Spline’ın iki uç noktası 0’a sabitlenir
  • Spline biçimi yalnızca uç nokta eğimleri α, β ile belirlenir
• Poz ve eğrilik parametreleri belirlendiğinde, sayfanın her (x, y) koordinatı görüntü düzlemindeki belirli bir konuma izdüşürülür
• Orijinal fotoğrafta yatay metin span’lerinin keypoint’leri bulunur; başlangıç tahmininden başlayarak keypoint’lerin yeniden izdüşüm hatasını en aza indiren parametreler aranır
• Optimizasyondan önce eğrilik olmadığı varsayıldığı için yeniden izdüşüm noktaları düz bir çizgi üzerinde yer alır; optimizasyondan sonra ise modelin izdüşüm noktaları gerçek algılanan keypoint’lerle neredeyse çakışır

Görüntü işleme pipeline’ı

• Sayfa sınırını kırpma

  • Görüntünün tamamı kullanılmaz; kenarlardaki gereksiz alanlardan kaçınmak için yalnızca ortadaki bölge sabit bir margin ile kırpılır
  • Akıllı sayfa sınırı algılama kullanılmaz

• Metin konturu algılama

  • Başlangıçta adaptive threshold uygulanır
  • Yatay bir kutuyla morphological dilation) yapılarak yatayda bitişik maske pikselleri bağlanır
  • Dikey bir kutuyla erosion) yapılarak bir piksel yüksekliğindeki gürültü kaldırılır
  • Connected component analysis sonrasında, çok yüksek veya çok kalın blob’lar filtrelenir
  • Kalan metin konturları PCA ile en iyi uyan doğru parçası olarak yaklaşıklaştırılır

• Yatay çizgi algılamayı destekleme

  • Bazı girdiler dikey metnin yoğun olduğu tablo biçiminde olduğundan, yeterince yatay metin algılanamazsa yatay çizgi veya rule algılama da denenir

Metin span’leri oluşturma ve referans noktası örnekleme

• Algılanan konturları aynı yatay span’de gruplamak için tüm kontur çiftleri üzerinde aday edge’ler oluşturulur ve maliyet hesaplanır
• İki kontur uzunluk yönünde büyük ölçüde örtüşüyorsa, çok uzaksa veya açıları çok farklıysa maliyet sonsuz yapılır
• Geçerli edge’lerin maliyeti, mesafe ve açı değişiminin doğrusal birleşimi olarak hesaplanır
• Edge’ler maliyet sırasına göre sıralandıktan sonra, yalnızca iki taraftaki konturlar henüz bağlanmamışsa bağlantı kuran açgözlü ikinci dereceden zamanlı bir yöntem kullanılır
  • Çalışma süresinin çoğu optimizasyona harcandığından, bu aşamanın ikinci dereceden zaman karmaşıklığı büyük bir sorun değildi
• Span’ler oluşturulduktan sonra, modeli belirlemeye yardımcı olmayacak kadar küçük span’ler kaldırılır
• Parametre modeli ayrık referans noktalarına ihtiyaç duyduğundan, metin konturu boyunca yaklaşık her 20 pikselde bir keypoint seçilir

Başlangıç değerleri üretme ve Powell optimizasyonu

• Tüm span’lerin ortalama yönü PCA ile tahmin edilir
• PCA sonucundaki ana bileşenler kullanılarak başlangıç x, y koordinatları ve düz, eğriliksiz bir sayfanın pozu analitik olarak ayarlanır
• Yeniden izdüşümde, nesne noktalarının z ofsetini elde etmek için kübik spline örneklenir ve OpenCV fonksiyonlarıyla görüntü düzlemine izdüşürülür
  • cv2.solvePnP
  • cv2.projectPoints
• Yeniden izdüşüm hatasını en aza indirmek için scipy.optimize.minimize ve 'Powell' solver kullanılır
  • Kara kutu tarzı, türevsiz bir optimizasyon aracı olarak kullanılır
  • Problemin kendisi doğrusal olmayan en küçük kareler problemidir
  • Diğer solver’lar veya özelleşmiş doğrusal olmayan en küçük kareler solver’ları kapsamlı biçimde denenmemiştir
• Programın çalışma süresinin neredeyse %100’ü bu optimizasyon aşamasında harcanır

Yeniden eşleme ve çıktı görüntüsü oluşturma

• Optimizasyon bittiğinde yalnızca r, t, α, β ayrılarak koordinat dönüşümü oluşturulur
• Asıl dewarp işlemi, 3B sayfa noktalarından oluşan dense mesh’in cv2.projectPoints ile izdüşürülmesi ve bu görüntü koordinatlarının cv2.remap’e verilmesiyle elde edilir
• Nihai sonuç, cv2.adaptiveThreshold ve Pillow kullanılarak bi-level PNG olarak kaydedilir

Örnek sonuçlar ve çalışma süresi

• GitHub deposunda çeşitli example images bulunur
• Tek bir 2012 MacBook Pro’da çalıştırma bazındaki istatistikler şöyledir

Girdi	Spans	Keypoints	Parameters	Optimizasyon süresi	Toplam süre
boston_cooking_a.jpg	38	554	600	23,3 sn	24,8 sn
boston_cooking_b.jpg	38	475	521	18,0 sn	18,8 sn
linguistics_thesis_a.jpg	20	161	189	5,1 sn	6,1 sn
linguistics_thesis_b.jpg	7	89	104	4,2 sn	5,3 sn

• En küçük modelde bile 104 parametre, en büyük modelde 600 parametre olduğundan bu küçük bir optimizasyon problemi değildir
• Optimizasyon hızı, başka yöntemler denenerek veya derlenen bir dil kullanılarak iyileştirilebilir

Kalan sınırlamalar

• Genel yaklaşım, biraz arka plan bilgisi okuyup tüm problemi optimizasyon sürecinin çıktısı olarak formüle etmektir
• Bu yöntem deformable part models ve active appearance models’ı akla getirse de onlar kadar gelişmiş değildir
• Leptonica ve CTM, dikey çarpıklığın yanı sıra yatay çarpıklığı da modellemeye ve düzeltmeye çalışır
• Bu uygulama yatay çarpıklık düzeltmeyi ele almaz
  • Kübik spline arc-length parametreleştirmesi olmadığı için, spline eğiminin büyük olduğu bölgelerde metin biraz sıkışır
  • Proje ağırlıklı olarak proof-of-concept olduğundan bu konu daha ileri götürülmemiştir
• Nihai kod GitHub deposunda yayımlanmıştır; ayrıntılı yorumlarla güçlendirme ise henüz yeterli değildir

[GN⁺]

Hacker News yorumları

• Yazarın yaptığı gibi çıktıya sert eşikleme uygularken dikkatli olmak gerekir.
  Düz metin sayfalarını epey iyi yakalıyor, ancak Google Books’taki birçok sayfada illüstrasyonların ya da küçük dipnotların okunamayacak kadar bozulduğunu gördüm.
  Google Books taraması tek kaynaksa tamamen çıkmaza sokuyor.

  • Eşikleme, bozulma düzeltme parametrelerini seçmek için referans noktalarını bulma amaçlı değil mi?
    Referans noktalarını bulduktan sonra bu parametreleri özgün görüntüye uygulayabilirmişsiniz gibi geliyor.

• 2024 yılındayız; belge tarayıcı uygulamalarında bu özelliğin hâlâ neden varsayılan olarak yerleşik olmadığını anlamak sinir bozucu.

  • Okulda GeniusScan kullanıyorum ve bu özellik var: https://blog.thegrizzlylabs.com/2024/03/genius-scan-7.16.htm...
  • Çok iyi.
    Optimize edilecek düşük boyutlu bir sayfa deformasyon modeli koymuş olmaları, bu yaklaşımın iyi çalışmasının kilit noktası gibi görünüyor.
    Bu, YC ölçeğine tam uyan bir problem. Pazara çıkış birkaç hafta, lansman maliyeti de birkaç yüz bin dolar civarında olabilir gibi.
    Apple’ın telefon uygulaması çok fazla elle ayar gerektiriyor; Microsoft’un Office Lens / Microsoft Lens’i için de “kenarlar sonunda çığırından çıkıp korkunç görünüyor” türü değerlendirmeler var.
    Dolayısıyla düzgün çalışan bir ürün için pazar var ve yaygın alıcı adaylarına satış şeklinde bir exit de mümkün görünüyor.
  • Google Drive eskiden bunu düzgün yapıyor gibiydi; son birkaç yılda çok daha kötüleştiğini hissediyorum.
  • Ürün yönetimi teknik riskin alınmaya değmeyeceğini düşünmüş olabilir.
    Bunu fazla karmaşık ve matematiksel bulmuş, onun yerine kullanıcıların sosyal medya etkinliklerini tarayıp bildirim zamanlamasını daha incelikli ayarlayan bir model yaparsa kullanıcı metriklerinin daha iyi olacağına karar vermiş olabilir.
    Churn’ü azaltma sürecinde karar vericiler katı biçimde veri odaklı karar vermiş sayılır.
  • vflat bu iş için iyi.

• John Warnock, Adobe CEO’luğundan ayrıldıktan sonra nadir tarihî kitapları koruyan Octavo şirketiyle daha yakından ilgilendi.
  Karşılaştıkları zorluklardan biri, bastırılıp düz açılamayan taranmış sayfaların kıvrımını düzeltmekti.
  https://en.m.wikipedia.org/wiki/Rare_Book_Room

• Yazı harikaydı.
  Teknik projelerin ve bu projelerdeki kararların nasıl etkili biçimde belgelenebileceğine örnek olarak şirkette referans alınabilir.

• Üniversitedeyken renklerle ayrılmış notları tarayan bir uygulama yapmaya çalışırken başka bir sorunla karşılaşmıştım.
  Sayfanın üstünden altına doğru renkler kaydığı için mavi kalem ile yeşil kalemi güvenilir biçimde ayırt etmek zorlaşıyordu.
  Bir gün tekrar bakmam gerekecek.

  • Beyaz arka planın da aynı şekilde kaydığını varsayarsak, iyi bir püf noktası görüntüyü kopyalayıp çok büyük ölçekte bulanıklaştırmak, ardından özgün görüntüyü bu bulanık sürüme bölmektir.
    Böylece düşük frekanslı renk/parlaklık değişimleri fiilen kaldırılır.
    Kâğıdın fotoğrafı çekildiğinde gölgeleri yok etmek için sık kullanılır; renk gradyanlarında da aynı şekilde işe yarayacağını düşünüyorum.

• Yeterince iyi görünüyor.
  Ancak deformasyon modeli biraz fazla global gibi.
  Kâğıttaki daha karmaşık bozulmaların bir kısmı modele yakalanmıyor ve nihai sonuçta da kalan bozulma olarak görünüyor.

• Kurulum sırasında hata alıyorum:
  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’su açtım.

• Çok havalı.
  Mobilde kullanılabilecek düzgün bir belge tarama uygulaması olsa keşke: bozulma düzeltme, eşikleme ve PDF oluşturmayı iyi yapan bir uygulama.
  Şu anda sonuçları nispeten en iyi olan Adobe Scan’e bağlı kalmış durumdayım; yine de bozulma düzeltmesi oldukça kötü.

  • Microsoft Lens’in iyi olduğunu duydum ama telefonumda açınca donup kalıyor.

• Okuması gerçekten ilginçti.
  2016’da kaçırdığım bir yazı gibi; “şöyle bir problem vardı, akıllıca bir teknik uygulandı ve iyi çalışan bir çözüm elde edildi” akışını çok iyi gösteriyor.
  Kişisel olarak böyle bir şeye ihtiyacım olacağını sanmıyorum, ama bir problemi iyi bir yöntemle ele almanın ve çıktı ile beklentilerin izin verdiği sınırlar içinde makul tavizler vermenin harika bir örneği.
  Yazı da iyi kaleme alınmış, açıklamalar da güzel.

• Kitabı görsel olarak göstermeniz gerekmiyor ve yalnızca OCR yapacaksanız bu adımı atlayabilirsiniz gibi geliyor.
  Google bu problemi 10 yıldan da uzun süre önce çözmüştü: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
  El yazması gerçekten değerliyse X-ışını tomografisiyle temassız bozulma düzeltme de mümkün: https://scrollprize.org/tutorial1

  • O zaman işe yarar bir yazılım bulup önermek gerekir.
    Google tarafı donanım kullanmıştı; X-ışını tomografisi lafı ise güçlü biçimde ChatGPT havası veriyor.
    Yine de bu yazıdaki yöntem 2016 ölçütlerine göre hoş ve basit.