Smart Crop，一种切除 PDF 扫描文档白边的新选择（算法篇）

这是我元旦假期的折腾成果。这里先分享一下思路和实现过程中遇到的有意思的事情~~，代码稍后整理后分享到 Github~~。

前些日子，同事送了我一个 Kindle，于是我开心地往里面灌了好几本书，开始假装文化人。

背景

但是在尝试阅读的时候，我发现体验并不怎么好，因为我平日里看的电子书大多是扫描版的以技术为主的各类书籍，这些扫描书有一个共同点，就是有比较宽的白边(margin)。于是我们在阅读这类电子书的时候通常会用各种手段把白边切掉，以便让内容在本来就不大的屏幕上占据更多像素。

亲自动手

其实在大多数人看来，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 可视化，效果见下图。

ratio 空间分布

拍脑袋给了个阈值 $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)$ 中算一算，然后取结果最大的就好了。想法虽好，这个启发函数还是得由我们来实现呀。目前我简单粗暴地实现了一个，勉强可用。

h (w i d t h, C o u n t_w i d t h) = w i d t h \times C o u n t_w i d t h

$\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})$ 。

算法优化

总结一下之前用大段文字描述的算法过程：

图像二值化
根据给定的窗口大小，将图像窗口化
计算每个窗口中文字像素占比
根据给定阈值，将窗口分为正文窗口和白边窗口
使用洪水填充(Flood fill)为连通的窗口分类
对各个分类的窗口做区域扩张，被扩张区域覆盖的窗口标记为正文窗口
扫描并获取水平、垂直方向上的宽度、宽度出现次数、宽度对应的坐标范围
使用启发函数求水平、垂直方向上的最优宽度
根据最优宽度得到正文区域

首先我们看一下第 4 步，这里面有一个阈值，拍脑袋给定的阈值。这个阈值能不能根据不同的图像自行计算呢？其实是可以的。这里取阈值其实就是要把窗口分为两类，这一操作是不是和图像二值化很像！像就对了，那么前辈们在图像二值化上积累的算法就可以拿来用了哈哈。

图像二值化大体上有三种策略，一种是不管三七二十一用一个固定的阈值，比如 127 来做二值化，这种策略最朴素但效果也是最差的。另外两种都是要计算阈值的，一种是算全局阈值，一种是算局部阈值。算局部阈值做局部二值化的算法我没怎么研究过，目前的实现中我使用了一种叫做大津算法的全局阈值算法。

接下来我们看第 5、6 步。最开始的设计中，这两步是只做一次的。后来在一次调试正文区域被切掉的 bad case 中我发现，区域扩张之后，原本两个不连通的正文区域居然可以连通了！而那个被连通的小区域恰好是被错误切除的正文区域。

知道了这个问题之后，解决起来就简单了，迭代到收敛嘛，多么常用的手段。在这里不是迭代到收敛，而是迭代到没有新的被标记为正文区域的窗口产生。

效果展示

算法基本上就是这样了，基本上可以全自动地识别出扫描文档的正文区域。下面找一些扫描版电子书来展示一下效果。左边处理前，右边处理后。

SQL 反模式

经济学通识

工程实现与产品化

元旦假期里我就已经把这个算法实现并且开发了一个完整的能够直接处理 PDF 文档的程序。只不过设计算法的时候用的是 Python，最后做工程实现的时候用的是 Java，这里面也是有许多妥协和不得已，具体原因以及过程我会在后续博文中分享，这里先上个图，然后给个下载链接。~~目前暂且放在阿里云 OSS ，待我把代码整理整理放到 Github 上开源后再迁移到 Github 的 Release 上。~~

下载下来的是一个可执行的 jar 包，在在终端输入如下命令进入 Smart Crop 的字符界面。

java -jar smart-crop-cli-1.0.0-executable.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 迎娶萌妹纸走上人生巅峰就全指望它了。

最后自我吐槽一下，写个博客小标题都跟写论文似的，好羞耻……