ページ歪み補正技術
(mzucker.github.io)- 曲がった文書写真を平坦な画像に変換するため、3D姿勢と曲率をモデル化し、テキスト基準点を合わせる最適化問題として解く
- LeptonicaやCTMのようにテキストを行単位に分割した後、行が平行かつ水平に近く見えるようにする座標変換を求める流れを取る
- モデルは回転ベクトル
r、移動ベクトルt、曲率勾配α、β、テキストspanのx、yオフセットを含み、再投影誤差を最小化する - パイプラインはページ境界の切り出し、テキスト輪郭検出、spanの組み立て、基準点サンプリング、初期値生成、Powell最適化、
cv2.remapによる再マッピングへと続く - 実行例ではパラメータ数は104〜600個、総実行時間は5.3〜24.8秒で、その大半が最適化に使われており、solverやコンパイル言語による高速化の余地が残っている
曲がったページを最適化問題として解く
- 手書き写真をPDFにする既存スクリプトは
adaptiveThresholdと複数画像をPDFにまとめる程度だったが、アーカイブ文書の写真では ページの反り によってテキストが大きく湾曲していた - 目標は、曲がったページ写真を自動で 平坦な文書画像 に変換するプログラムを作ること
- コードはGitHubの page_dewarp で公開されている
LeptonicaとCTMから取り入れた基本フロー
- 文書画像の歪み補正はすでによく知られた問題であり、Dan Bloombergのオープンソース画像処理ライブラリ Leptonica にも実装されている
- 参考資料には、dewarping contest結果の 要約 と、優勝方式であるCoordinate Transform Model、すなわちCTMに関する 論文 が含まれる
- LeptonicaとCTMは共通して問題を2段階に分けている
- テキストを 行単位 に分離する
- 行が平行かつ水平になるような 歪みまたは座標変換 を求める
- この実装ではページ外形を複数のパラメータで表現する
r,t: ページの3D方向と位置を表す回転ベクトルと移動ベクトルα,β: ページ表面の曲率を定める2つの勾配y₁ ... yₙ: ページ上のn個の水平spanの縦方向オフセットxᵢ: 各span内の複数基準点に対する横方向オフセット
3D曲面と再投影誤差
- ページの3D形状は、ローカル
y軸方向に曲線を掃引して作る曲面として表現する - ページの横座標
xは曲面のz方向変位にマッピングされ、水平断面は 3次スプライン でモデル化する- スプライン両端点は0に固定される
- 端点勾配
α,βのみでスプライン形状が決まる
- 姿勢と曲率パラメータが決まると、ページ上の各
(x, y)座標が画像平面上の特定位置へ投影される - 元写真から水平テキストspanの keypoint を見つけ、初期推定値から始めてkeypointの 再投影誤差 を最小化するパラメータを求める
- 最適化前は曲率がないと仮定するため再投影点は一直線上に並ぶが、最適化後はモデル投影点が実際に検出されたkeypointとほぼ重なる
画像処理パイプライン
-
ページ境界の切り出し
- 画像全体は使わず、周辺の不要領域を避けるため固定マージンで中央領域だけを切り出す
- 賢いページ境界検出は使っていない
-
テキスト輪郭検出
- 初期adaptive thresholdを適用する
- 水平ボックスで morphological dilation) を行い、水平方向に隣接するマスク画素を接続する
- 垂直ボックスで erosion) を行い、1ピクセル高さのノイズを除去する
- connected component analysis の後、背が高すぎる、または太すぎるblobを除外する
- 残ったテキスト輪郭は PCA により最もよく当てはまる線分で近似する
-
水平線検出の補完
- 一部の入力は縦書きテキストが多い表形式だったため、水平テキストが十分に検出されない場合は水平線やruleの検出も試みる
テキストspan構成と基準点サンプリング
- 検出された輪郭を同じ水平spanにまとめるため、すべての輪郭ペアについて候補edgeを作成し、コストを計算する
- 2つの輪郭が長さ方向に大きく重なりすぎる、遠すぎる、または角度差が大きい場合、コストは 無限大 とする
- 有効なedgeのコストは距離と角度変化の線形結合で計算される
- edgeをコスト順に並べ、両側の輪郭がまだ接続されていない場合にのみ接続する 貪欲な二次時間 の方式を使う
- 実行時間の大半は最適化に使われるため、この段階の二次時間計算量は大きな問題ではなかった
- span生成後は、小さすぎてモデル決定に役立たないspanを除去する
- パラメータモデルには離散的な基準点が必要なため、テキスト輪郭およそ20ピクセルごとにkeypointを1つ選ぶ
初期値生成とPowell最適化
- すべてのspanの平均方向はPCAで推定する
- PCA結果の主成分を使って、初期
x,y座標と平坦で無曲率なページの姿勢を解析的に設定する - 再投影では3次スプラインをサンプリングして物体点の
zオフセットを取得し、OpenCV関数で画像平面へ投影するcv2.solvePnPcv2.projectPoints
- 再投影誤差の最小化には
scipy.optimize.minimizeと'Powell'solver を使用する- ブラックボックス型の微分不要最適化ツールとして使われる
- 問題自体は 非線形最小二乗 に該当する
- 他のsolverや特化型の非線形最小二乗solverはあまり試していない
- プログラム実行時間のほぼ100%がこの最適化段階に費やされる
再マッピングと出力画像生成
- 最適化終了後、
r,t,α,βだけを取り出して 座標変換 を作る - 実際のdewarpは3Dページ点のdense meshを
cv2.projectPointsで投影し、その画像座標をcv2.remapに渡して行う - 最終結果は
cv2.adaptiveThresholdと Pillow を使ってbi-level PNGとして保存する
実例結果と実行時間
- GitHubリポジトリには複数の example images が含まれている
- 単一の2012 MacBook Proでの実行統計は次の通り
| 入力 | Spans | Keypoints | Parameters | 最適化時間 | 総時間 |
|---|---|---|---|---|---|
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個あり、小さな最適化問題ではない
- 最適化速度は、別の手法を試したり コンパイル言語 を使ったりすることで改善できる可能性がある
残された限界
- 全体のアプローチは、背景知識を少し調べたうえで、問題全体を最適化過程の出力として定式化するというもの
- この方法は deformable part models や active appearance models を思わせるが、それらほど洗練されてはいない
- LeptonicaとCTMは垂直歪みだけでなく 水平歪み もモデル化し、補正しようとしている
- この実装では水平歪み補正までは扱っていない
- 3次スプラインが arc-length パラメータ化ではないため、スプライン勾配が大きい領域ではテキストがやや圧縮される
- プロジェクトは主にproof-of-conceptだったため、この問題はそれ以上進めていない
- 最終コードは GitHubリポジトリ で公開されているが、詳細なコメントの補強はまだ十分ではない
1件のコメント
Hacker Newsのコメント
著者がやったように出力へ強いしきい値処理を適用するのは注意が必要
通常のテキストページにはかなりうまく効くが、Google Booksのいくつかのページでは挿絵や小さな脚注が読めないほど壊れるのを見た
Google Booksのスキャン版が唯一の資料なら完全に詰んでしまう
いったん基準点を見つければ、そのパラメータを元画像に適用できそう
2024年なのに、なぜ文書スキャナーアプリにこういう機能がまだ標準搭載されていないのかもどかしい
最適化する低次元のページ変形モデルを置いているのが、この方式がうまく動く鍵に見える
これはYC規模にぴったりの問題だ。市場投入まで数週間、投入コストは数十万ドル程度で済みそう
Appleのスマホアプリは手動調整が多すぎるし、MicrosoftのOffice Lens / Microsoft Lensには「端が最終的に暴走してひどい見た目になる」といった評価がある
だから単にちゃんと動く製品の市場があり、よくある買収候補に売却する形のエグジットも可能に見える
複雑すぎて数学的すぎると見なし、その代わりユーザーのソーシャルメディア活動をあさって通知タイミングをより精密に決めるモデルを作ったほうがユーザー指標が良くなると考えたのだろう
離脱率を下げようとする中で、意思決定者たちが厳格にデータ駆動で決めたわけだ
John WarnockはAdobeのCEOを退いた後、希少な歴史書を保存する会社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.0GitHub Issueを上げた
とてもクール
モバイルで使えるまともな文書スキャンアプリがあるといい。歪み補正、しきい値処理、PDF生成まできちんとできるアプリのこと
今は結果がまだ一番ましなAdobe Scanに縛られているが、それでも歪み補正はかなりいまいち
読んでいて本当に興味深かった
2016年に見逃していた記事のようだが、「こういう問題があって、賢い手法を適用して、うまく動く解法を得た」という全体の流れがよく伝わってきて良い
個人的にこれが必要になることはなさそうだが、問題への取り組み方や、出力結果と期待値の許容範囲の中で適切に折り合いをつける優れた例だ
文章もよく書けているし、説明も良い
本を視覚的に見せる必要がなく、OCRだけでよいなら、この段階は飛ばせそう
Googleは10年以上前にこの問題を解決していた: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
原稿が本当に価値あるものなら、X線断層撮影で非接触の歪み補正も可能: https://scrollprize.org/tutorial1
Googleのほうはハードウェアを使っていたし、X線断層撮影の話はChatGPTっぽさが強い
それでもこの記事の手法は2016年時点としては見栄えがよく、シンプルだ