Smart Crop，一種切除 PDF 掃描文檔白邊的新選擇（算法篇）

這是我元旦假期的折騰成果。這里先分享一下思路和實現過程中遇到的有意思的事情，代碼稍后整理后分享到 Github。

前些日子，同事送了我一個 Kindle，于是我開心地往里面灌了好幾本書，開始假裝文化人。

背景

但是在嘗試閱讀的時候，我發現體驗并不怎么好，因為我平日里看的電子書大多是掃描版的以技術為主的各類書籍，這些掃描書有一個共同點，就是有比較寬的白邊(margin)。于是我們在閱讀這類電子書的時候通常會用各種手段把白邊切掉，以便讓內容在本來就不大的屏幕上占據更多像素。

相關工作

之前用 iPad 看電子書的時候，用的是大名鼎鼎的多看閱讀，這個 App 我從大學用 Andriod 設備的時候就一直在用，挺喜歡的。多看對 PDF 也是提供切邊功能的，只不過這功能做的比較糙。多看里所謂的切邊其實是這樣，上下左右來四根線，用戶可以隨意拖動框出正文區域，如果有需要的話勾選一個「奇偶頁對稱」就能實現奇偶頁切邊的時候是鏡像的。

除去多看內建的切邊功能不看，互聯網上我們能找到的絕大部分用來給 PDF 切白邊的工具都是這個套路，讓用戶選定一個正文區域，然后用這個區域套在每一頁上，只保留區域內的內容。這種策略的好處就是實現簡單，用戶理解起來也容易。

但是，每次用這種「一刀切」的白邊裁剪，我總是感覺很焦慮，會不會把內容給我切了呢，會不會呢會不會呢……于是我就會陷入一種蛋疼的狀態，切少了留下一大截白邊好難受，切多了把內容切沒了好難受……所以說一刀切其實是把困難留給了用戶，切好了是運氣，切壞了是用戶自己手殘。

后來我找到一個在 PDF 裁剪領域鶴立雞群的軟件，briss，在讓用戶放心的程度上足以秒殺其他的競品。為了保證不把內容切掉，這個軟件用了一個顯然的策略，把內容頁處理之后疊加成一張圖，用戶在疊加圖上去框選正文區域。

這種方式其實就是把每頁的正文區域取了并集，好處是不會把內容切掉，壞處也是顯而易見的，就是有些頁的白邊沒切干凈！可能左邊空了一大塊，可能右邊空了一大塊。

親自動手

其實在大多數人看來，briss 能做到這步已經很好了，但是我還是覺得不夠好，沒切干凈留了一大塊白邊好難受。就因為這個被一個妹紙說是處女座強迫癥了，慘慘慘。

假如我能寫出一個軟件，能夠比較精準而且高效地識別出 PDF 文檔每一頁的正文區域，不就可以實現精確的白邊裁剪了么？我抓住了這個稍縱即逝的想法，想方設法實現它。

我找了幾本電子書作為測試集，包括「經濟學通識」、「SQL 反模式」等等。為了快速試驗，我把這些電子書一頁頁輸出成 PNG 格式位圖，用 Python 做圖像處理。之前學習數字圖像處理的時候用的是 Matlab，我也嘗試安裝了當初用的版本，發現在最新的 OS X 上那個版本已經因為空指針沒法啟動了，只好作罷。

Python 做圖像處理曾經有大名鼎鼎的 PIL，如今已經被它的 fork 取代了，叫做 Pillow。另一個必備類庫是 numpy，矩陣操作神器，比手寫 for 循環不知道高到哪里去。

工具選定了，接下來就是要實現算法，一個能識別正文區域的算法，輸入是一頁掃描書的圖像，輸出是兩個二維坐標，分別代表左上和右下。一開始我想到幾個常用的策略，比如掃描線，局部窗口之類的。思考之后掃描線策略被我放棄了，因為在像素級別并沒有什么顯然的線能夠作為區域邊界，而且掃描線本身容易被正文之外的內容（頁眉頁腳頁碼）干擾。

于是局部窗口就成了我的首選策略。對于一張 $w \times h$ 的二值化圖像，如果我們使用 $w' \times h'$ 的窗口，那么整個圖像將被劃分為 $\lceil w/w' \rceil \times \lceil h/h' \rceil$ 個窗口。對于每個窗口，我們計算正文像素占總像素的比例 $ratio ＝ \text{pixels}(body) / \text{pixels}(total)$，如果 $ratio$ 大于閾值 $T$，則認為該窗口位于正文區域內。

為了在試驗階段獲取一個合適的閾值 $T$，我用 $25 \times 25$ 的窗口跑了一頁圖像，然后把 $ratio$ 的分布用 Mathematica 可視化，效果見下圖。

拍腦袋給了個閾值 $T = 0.04$，于是我就能夠根據這個閾值選出位于正文區域的窗口了。

為了省事，我直接用 numpy 把標記為正文區域的窗口涂黑了，不過這并不影響展示效果。說是正文區域其實不太準確，應該說是「文本區域」比較確切，因為位于左上角的頁碼和頁眉，因為像素顏色和正文一致，像素密度大于閾值，也被誤認為是正文區域了。

雖然到此為止，我們已經大體上把可能為正文區域的窗口標記出來了，但是這些窗口并不連續，中間參雜了非正文區域的窗口。如何從這些散亂的小窗口上抽象出一個大的完整的正文區域，并盡可能的把頁碼頁眉之類的干擾排除呢？

我開始了嘗試，一開始開始用掃描線，在窗口這一層級上應用掃描線，橫著掃一遍豎著再掃一遍，一遍不行就掃兩遍，掃描的過程中用各種復雜的古怪的邏輯去找出 $x$ 方向和 $y$ 方向上的正文范圍。寫出來之后發現這種方式并不優雅，效果也不理想，更不具備普適性。掃描過程中的復雜邏輯就仿佛一套針對某本書定制的規則，換了一本書就不一定好使了。

后來我嘗試了連通圖，也是目前使用的策略。對于每個處于正文區域內的窗口，我發現這些窗口大體上是連通的，特別是當我們放寬連通性的判定條件，不僅僅局限于有直接相鄰關系的四鄰域或者八鄰域，而是放大到二十四鄰域的時候。二十四鄰域就是說，即使兩個黑格子之間隔著一個白格子，我們也認為這兩個黑格子是連通的。

依次遍歷每個窗口，每當我們發現一個沒被訪問過的黑格子，就把所有跟這個黑格子連通的黑格子標記為同一個分類。遍歷完成后，我們就把所有的黑格子分成了一個或多個分類。這里面標記連通的黑格子的操作就需要用到圖搜索算法了，我的首選當然是 DFS 啦，寫起來簡單嘛。一開始寫 DFS 照例用的遞歸，后來有一次測試的時候發現遞歸棧居然被打爆了，只好老老實實換成迭代寫法。

寫完后我才發現我居然重新發明了 Flood fill 算法 ……沒文化真可怕。

對于前一步標記出來的每個分類，我們分別找到那個恰好能把分類中所有窗口覆蓋的最小區域，并把這個最小區域內的所有窗口都標記為正文區域。這一步我把它稱為正文區域擴張。

從上圖左邊可用看到，正文區域內的窗口被分成了兩類，第一類是左上角的頁碼和頁眉，第二類是真正的正文區域。右邊則是區域擴張的結果。

基本上到了這一步，離我們想要的結果就不遠了！接下來就是要用一個比較巧妙的方式，把頁碼等干擾區域排除在外，提取出真正的正文區域。一開始的時候我們把像素抽象組合成窗口，然后在窗口這個層級上做各種操作，到了最后一步出結果的時候，就需要把抽象層級從窗口下放到像素了。

最終還是用上了掃描線，橫著豎著都要掃描。在窗口層級上，用水平的掃描線獲取每行窗口在 $x$ 方向上的像素寬度，并記錄每個寬度出現的次數，以及這個寬度下的最大最小 $x$ 坐標。垂直掃描線也是類似的，獲取 $y$ 方向上的像素寬度及其出現次數，還有各個寬度下的最大最小 $y$ 坐標。

接下來我們就是分別在兩個方向上選取最優寬度，得到最優寬度之后就能用這兩個寬度下的最大最小坐標標定出一個矩形區域作為算法的輸出了。那么如何定義最優寬度呢？反正不能是最大寬度，最大寬度就把頁眉頁碼等干擾區域都算進去了。

假設我們有一個啟發函數 $\text{h}(\theta_1, \theta_2, \cdots)$，我們把寬度、寬度出現的次數等等各種信息作為入參，就能夠得到一個數字，參數組合越接近最優解數字越大。我們只需要把每個寬度扔到 $\text{h}(\theta_1, \theta_2, \cdots)$ 中算一算，然后取結果最大的就好了。想法雖好，這個啟發函數還是得由我們來實現呀。目前我簡單粗暴地實現了一個，勉強可用。

$$ \text{h}(width, Count_{width}) = width \times Count_{width} $$

用 $y$ 方向來舉個例子。

我們在 $y$ 方向上主要有兩種高度，一種用紅色標記，高度為 $h_r$，出現 $C_r$ 次；另一種用白色標記，高度為 $h_w$，出現 $C_w$。如果 $h_w \times C_w > h_r \times C_r$，那么我們就認為白色標記的高度優于紅色標記的高度。這一策略之所以勉強可用，是因為它包含了這樣的假設：干擾信息占據的寬度并不大。如果干擾信息和正文差不多寬，那這個啟發函數就搞不定了。

掃描執行完成之后，我們就得到了 $x$ 方向上的最大最小坐標 $x_{max}$ 和 $x_{min}$，以及 $y$ 方向上的最大最小坐標 $y_{max}$ 和 $y_{min}$。做個簡單的組合，我們就能夠返回一對可以用于表達區域的坐標了，位于左上角的 $(x_{min}, y_{min})$ 和位于右下角的 $(x_{max}, y_{max})$。

算法優化

總結一下之前用大段文字描述的算法過程：

1. 圖像二值化
2. 根據給定的窗口大小，將圖像窗口化
3. 計算每個窗口中文字像素占比
4. 根據給定閾值，將窗口分為正文窗口和白邊窗口
5. 使用洪水填充(Flood fill)為連通的窗口分類
6. 對各個分類的窗口做區域擴張，被擴張區域覆蓋的窗口標記為正文窗口
7. 掃描并獲取水平、垂直方向上的寬度、寬度出現次數、寬度對應的坐標范圍
8. 使用啟發函數求水平、垂直方向上的最優寬度
9. 根據最優寬度得到正文區域

首先我們看一下第 4 步，這里面有一個閾值，拍腦袋給定的閾值。這個閾值能不能根據不同的圖像自行計算呢？其實是可以的。這里取閾值其實就是要把窗口分為兩類，這一操作是不是和圖像二值化很像！像就對了，那么前輩們在圖像二值化上積累的算法就可以拿來用了哈哈。

圖像二值化大體上有三種策略，一種是不管三七二十一用一個固定的閾值，比如 127 來做二值化，這種策略最樸素但效果也是最差的。另外兩種都是要計算閾值的，一種是算全局閾值，一種是算局部閾值。算局部閾值做局部二值化的算法我沒怎么研究過，目前的實現中我使用了一種叫做 大津算法 的全局閾值算法。

接下來我們看第 5、6 步。最開始的設計中，這兩步是只做一次的。后來在一次調試正文區域被切掉的 bad case 中我發現，區域擴張之后，原本兩個不連通的正文區域居然可以連通了！而那個被連通的小區域恰好是被錯誤切除的正文區域。

知道了這個問題之后，解決起來就簡單了，迭代到收斂嘛，多么常用的手段。在這里不是迭代到收斂，而是迭代到沒有新的被標記為正文區域的窗口產生。

效果展示

算法基本上就是這樣了，基本上可以全自動地識別出掃描文檔的正文區域。下面找一些掃描版電子書來展示一下效果。左邊處理前，右邊處理后。

工程實現與產品化

元旦假期里我就已經把這個算法實現并且開發了一個完整的能夠直接處理 PDF 文檔的程序。只不過設計算法的時候用的是 Python，最后做工程實現的時候用的是 Java，這里面也是有許多妥協和不得已，具體原因以及過程我會在后續博文中分享，這里先上個圖，然后給個 下載鏈接 。目前暫且放在 阿里云 OSS ，待我把代碼整理整理放到 Github 上開源后再遷移到 Github 的 Release 上。

下載下來的是一個可執行的 jar 包，在在終端輸入如下命令進入 Smart Crop 的字符界面。

java -jar smart-crop-latest.jar

然后用 crop 命令來處理 PDF 文檔，自動識別正文區域并切除白邊。

crop --input in.pdf --output out.pdf

在我的偽頂配 RMBP 上，處理一個 400 多頁的 PDF 文檔耗時約 2 分鐘，絕大部分的時間都花在把 PDF 一頁頁轉換成圖像上，我的算法消耗的時間反而可以忽略不計了。

如果機器性能不錯，可以開啟多核模式，充分利用多核計算能力和內存。多核模式下，原本需要 2 分鐘的處理過程就只需要不到半分鐘了，代價是風扇呼呼的轉，內存也消耗得很厲害，大約占了 2G 的內存空間，如果人為用 -Xmx 之類的參數限制最大內存空間，GC 就會經常跑出來搗亂了，性能下降不少。

crop --use-multi-core --input in.pdf --output out.pdf

由于時間的關系，我目前僅實現了一個字符界面程序。如果要做大批量自動化的處理，字符界面的程序是最好的選擇。但是從人機交互的角度來說，字符界面肯定是不夠直觀的，特別是一些極端場景下，需要用戶提供更多的信息，算法才能給出更好的結果。

比如在使用大津算法自動獲取閾值的時候，我們能夠獲得更激進的去白邊的效果，但是有的時候也會因此而把一些位處偏僻的正文當成干擾信息一并去除，看下面這個例子，左上是原圖，右上是區域擴展，下方是處理結果。

處理結果真的就只保留了那一大段文字，把標題、署名之類的都丟棄了。如果我們引入人機交互，允許用戶在正文區域內簡單涂抹，算法識別涂抹區域，或者視為正文區域，或者僅作為連接分散的正文區域的參考區域，都能在很大程度上減少有用信息的丟失。

作為演示，我在 Preview 中隨便用鋼筆工具劃拉兩下，就把原本丟失的標題和署名撈回來了。

除了劃拉一下找回丟失的標題，我們還可以劃拉一下把那些誤認為是正文的無用區域排除。而且不用擔心誤傷正文區域，因為有區域擴張這一步的存在，只要不是真把正文區域傷筋動骨了，抹掉一些那也是沒關系的，最后還是會擴張回來。

結論和展望

如果在移動設備上使用這個算法，可以充分發揮觸摸交互的優勢，在程序開始處理之前詢問用戶是否需要簡單涂抹一下標出可能的正文區域，或者涂抹一下覆蓋那些肯定不是正文的區域。

后面如果時間和精力允許的話，我會考慮分別寫一個 iOS App 和 Android App，把我的這個 Smart Crop 算法帶給更多的用戶。雖然我現在還不太會寫這兩個平臺的 App，但是我只要想寫，這些就都不是問題。

如果多看閱讀能夠把這個算法內嵌到多看閱讀 App 里面，或許我就不用親自操刀開發應用了哈哈~如果真拿去用了別忘了給我個名譽專家或者終身 offer 什么的，我出任 CTO 迎娶萌妹紙走上人生巔峰就全指望它了。

最后自我吐槽一下，寫個博客小標題都跟寫論文似的，好羞恥……