压缩和增强手写笔记

Question

我写了一个程序来清理手写笔记扫描件，同时减少文件大小。下面是样例输入输出：

左边： 输入扫描 @ 300 DPI, 7.2MB PNG / 790KB JPG。 右边： 输出 @ 相同的分辨率，121KB PNG.1

免责声明： 这里描述的过程过多或少 Office Lens 应用已经实现了，并且或许有一些其他工具也做了相似的事。我并不是声称自己想出了一个激进的新发明 —— 只是我自己对一个有用的工具的实现。

如果你赶时间，那么看看 github repo，或者跳到后面的结果部分，在那里，你可以玩下颜色集群的交互式三维图。

动机

我的一些课程并没有指定教材。对于这些课，我喜欢任命每周“学生抄写员”与其他同学分享他们的课堂笔记，因此，对于学生来说，有些手写资源可以用来帮助他们仔细检查对材料的理解。笔记作为 PDF 放在课程网站上。

在学校，我们有一个“智能”复印机，可以将文件扫描成 PDF，但是它生成的文档……有点糟糕。这里是来自手写作业的一些输出例子：

似乎是随意的，复印机选择是否 二值化 每个符号 (像 x )，或者将它们变成糟糕的块状 JPG (像平方根符号)。不用说，我们可以做得更好。

概述

我们从一张像这样的一张可爱的学生笔记页扫描开始：

原始的 300 分辨率的 PNG 扫描图片大概 7.2MB；转换成 JPG，质量水平为 85 的相同的图片，大概是 790KB (2)。由于扫描的 PDF 文件通常只是一种关于 PNG 或者 JPG 的 容器格式 ，我们当然不希望在转换成 PDF 的时候 减少 所需存储大小。每页 800KB 很大，由于加载次数，我想要让它接近 100KB 每页。(3)

虽然这个学生写笔记非常整洁，但是上面显示的扫描看起来有点乱（并不是她的错)。页面隐隐约约显示出另一面的内容，与恒定颜色背景的页面相比，这都会让浏览器分心，并且使得 JPG/PNG 编码器难以压缩。

这里是我的 noteshrink.py 程序的输出：

这是一个比较小的 PNG 文件，只有 121KB。我最喜欢的部分？不仅是图片变得 更小 ，它还变得 更清晰 ！

过程和彩图原理

这里是生成上面压缩、干净的图片的所需步骤：

1. 标识原始扫描图片的背景色。
2. 通过与背景颜色的差异的阈值来分隔前景。
3. 通过从前景选择少数“代表色”来转换成索引颜色 PNG。

在我们深入研究每个步骤之前，回顾一下彩色图像是 如何 数字化存储是有用的。因为人眼有三种不同类型的颜色敏感细胞，我们可以通过组合红、绿、蓝色光的各种强度来重构任何颜色。(4) 得到的系统等价于 RGB 颜色空间 中三维点的颜色，这里示出：(5)

虽然真正的向量空间允许无限数量的连续变化像素强度，但是为了数字化存储它们，我们需要离散颜色 —— 通常把每个 8 位赋给红、绿、蓝色通道。不过，考虑到图像中的颜色类似于连续三维空间中的点，这为分析提供了强大的工具，在我们讲到上面的提到的处理步骤时，我们将会看到。

识别背景颜色

由于页面的大部分是没有墨水或者线条的，因此我们可能会期望纸张颜色是在扫描图像中最常出现的颜色，而如果扫描器始终将无标记的白色页面表示成相同的 RGB 三元组，那么将其挑出来并没问题。令人遗憾的是，并非如此；由于玻璃上的灰尘斑点和污渍而导致的颜色随机变化，页面本身的颜色变化，传感器噪声等等。因此在现实中，“页面颜色”能跨越数千个不同的 RGB 值。

原始的扫描图像是 2,081 x 2,531，总面积有 5,267,011 个像素。虽然我们 可以 考虑每个单独的像素，但是处理输入图片的代表性样本会更快。 noteshrink.py 程序默认取样输入图像的 5%（对于分辨率 300 的扫描绰绰有余），但现在，让我们看看从原始扫描随机选取的 10,000 个像素的一个更小的子集：

虽然它并不怎么像实际的扫描页面 —— 上面找不到文本 —— 但是两张图像上的颜色分布是非常一致的。两个都是具有多数的灰白像素，有一点红、蓝和暗灰色像素。这里是相同的 10,000 个像素，根据亮度分类 (例如，它们的 R,G 和 B 强度之和)：

远远望去，图片底部的 80-90%似乎都是相同的颜色；然而，若仔细观察就会看到由相当多的变化。事实上，在上面的图片中，最频繁的颜色是 RGB 值为(240, 240, 242) 的颜色，只占 10,000 个样本中的 226，不到像素总数的 3%。

由于这里的 众数 ) 占样本如此之小的比例，因此我们应该质疑它如何可靠地描述出图片中色彩的分布。如果我们在查找众数之前首先减少图片的 位深度 ，那么我们就更有机会确定页面的普遍颜色。下面是当我们通过让 4 个 最低有效位 清零，从而从每通道 8 比特移到 4 时的样子：

现在，最常出现的颜色是 RGB 值为(224, 224, 224) 的颜色，3,623 个采样像素 (占 36%)。本质上，通过降低位深度，我们将相似的像素分组放进较大的“容器”中，这使得更容易在数据中查找一个强峰值。(6)

在可靠性和精度之间存在权衡：小容器能让色彩区分更精细，但是更大的容器会健壮得多。最后，我使用每通道 6 比特来确定背景色，这似乎是两个极端之间的一个不错的最有效点。

分隔前景

一旦我们确定了背景色，我们就可以根据图片中每个像素的相似度来对图片做 阈值化 ) 处理。计算两种颜色相似性的一个自然而然的方法是，计算它们在 RGB 空间中的坐标的 欧几里得距离 ；然而，这种简单的方法无法正常的对下面显示的颜色进行分段：

这里是一个表格，它指定了颜色及其到背景颜色的欧几里得距离：

颜色	所在之处	R	G	B	从 BG 的距离
白色	背景	238	238	242	—
灰色	从背后渗出	160	168	166	129.4
黑色	页面前面的油墨	71	73	71	290.4
红色	页面前面的油墨	219	83	86	220.7
粉色	左边距的垂直线	243	179	182	84.3

正如你说看到的，我们想要作为背景进行分类的深灰色透背实际上比我们希望作为前景色分类的粉红色线条离白页颜色 更远 。任何将粉色标记为前景色的欧几里得距离的阈值必然也会包含透背。

我们可以通过从 RGB 空间转到 色调-饱和度-明度(Hue-Saturation- Value，HSV) 空间来解决这个问题，HSV 空间将 RGB 立方体变形为在这个剖视图中描绘出的圆柱形状(7):

HSV 圆柱表示了关于它的外部顶部边缘的圆形分布的各种颜色的特性； 色相 指的是该圆的角度。圆柱的中心轴线范围从底部的黑色到顶部的白色，灰色色调在它们中间 —— 这整个轴具有零 饱和度 ，或者说颜色的强度，而在外圆周的鲜艳的色调都具有 1.0 饱和度。最后， 明度 指的是颜色的整体亮度，范围从底部的暗色调到顶部的亮色调。

所以，现在重新考虑我们上面的颜色，这一次按照明度和饱和度：

颜色	明度	饱和度	从 BG 的明度差	从 BG 的饱和度差
白色	0.949	0.017	—	—
灰色	0.659	0.048	0.290	0.031
黑色	0.286	0.027	0.663	0.011
红色	0.859	0.621	0.090	0.604
粉色	0.953	0.263	0.004	0.247

正如你所料，白色、黑色和灰色明度显然不同，但是具有相似的低饱和度 —— 远低于红色和粉红色。有了由 HSV 提供的额外的信息，如果任一下面这些标准成立，那么我们可以成功地标记一个像素属于前景：

• 与背景色的明度差超过 0.3， 或者
• 与背景色的饱和度差超过 0.2

前一个标准拉入黑色笔标记，而后者拉入红色墨水以及粉色线。两个标准都成功地将灰色透背从前景中排除。不同的图像可能需要不同的饱和度/明度阈值；见结果部分以了解详情。

选择一组代表色

一旦我们分隔了前景，我们就留下了对应于页面标记的新的一组颜色。让我们可视化该组 —— 但这一次，我们并不将颜色想成像素的集合，而是将它们看成 RGB 空间中的三维点。由此产生的散点图最终看起来相当的“块状”，具有几个相关色彩的带：

我们现在的目标是通过选择小数量（在这个例子中是 8）的颜色来表达整个图片，从而将原始的每像素 24 比特的图片转换成 索引色 图片。这有两种影响：首先，它减少了文件大小，因为现在指定一个颜色只需要 3 比特（由于 8 = 2^3）。此外，它使得结果图像更具视觉凝聚力，因为在最终的输出图像中，相似的颜色墨水标记有可能赋值成相同的颜色。

要完成此目标，我们将使用一个数据驱动的方法，它利用上图中的“块状”特性。选择对应于集群中心的颜色将导致一组准确表示基础数据的颜色。在技术方面，我们将解决一个 颜色量化 问题 (这本身只是 矢量量化 ) 的一个特例，通过使用 聚类分析 。

我所选择处理该任务的具体方法工具是 k -means 聚类 。其总目标是找到一组均值或中心，使得从每个点到最近中心的距离最小。当你用它来调出上面数据集中的 7 个不同聚类时，你会获得以下内容：(8)

注：原文是一个交互式三维图，有兴趣的可以到原文去玩下。

在该图中，具有黑色轮廓的点表示前景色样本，着色线将它们连接到 RGB 颜色空间中最近的中心。当图片被转化成索引色时，每个前景样本将被替换成最近中心的颜色。最后，圆形轮廓表示从每个中心到它最远相关样本的距离。

附加功能

除了能够设置明度和饱和度阈值外， noteshrink.py 程序还有一些其他显著的特点。默认情况下，它通过分别调整最小强度值和最大强度值为 0 和 255，从而提高最终调色板的鲜艳度和对比度。如果没有这样的调整，那么上面扫描件的 8 颜色调色板会是这样的：

调整后的调色板更有生气：

还有一种选项可以在分隔前景色后迫使背景色变成白色。为了进一步在转换成索引色后减少 PNG 图片的大小， noteshrink.py 可以自动的运行 PNG 优化 工具，例如 optipng ， pngcrush 或者 pngquant 。

程序的最后输出使用 ImageMagick 的 convert 工具，像 这个 一样将多个输出图像组合成 PDF。作为进一步的奖励， noteshrink.py 按数值 (与按字母相反，与 shell 的 globbing ) 操作符行为相似) 自动排序输入文件名。当你蠢蠢的扫描程序(9) 生成诸如 scan 9.png 和 scan 10.png 这样的文件名，而你不想让它们在 PDF 的顺序互换时，这就派上用场了。

结果

这里是该程序输出的一些例子。第一个( PDF ) 使用默认阈值设置，看起来棒棒哒：

这里是颜色集群可视化：

(Ele 注：原文中的图更精彩~)

下一个( PDF ) 要求降低饱和度阈值至 0.045，因为蓝灰色线条是如此单调：

颜色集群：

(Ele 注：原文中的图更精彩~)

最后，是一个来自于工程师的方格纸的样例扫描件( PDF )。对于这个，我将明度阈值设置为 0.05，因为背景和线条的对比度非常低：

颜色集群：

注：原文中的图更精彩~

这四个 PDF 文件总共占用约 788KB，每张输出页面平均大约 130KB。

结论和未来的工作

我很高兴我可以做出一个能用来为我的课程网站准备抄写笔记 PDF 的实用工具。除此之外，我真的很喜欢准备这篇文章，特别是因为它促使我尝试改善 Wikipedia 的 色彩量化 页面展示的实质上是二维的可视化，也最终学会了 three.js (非常有趣，会再次使用的)。

如果我重新审视这个项目，那么我想要玩一玩替代的量化方案。我这周突然想到的一个方案是在一组颜色样本的 近邻图 上使用 谱聚类 —— 当我构思它的时候，我想这是一个令人兴奋的新想法，但原来有一篇 2012 的论文 提出了这个确切的方法。哦，好吧。

你也可以尝试使用 期望最大化 ，形成 高斯混合模型 来描述颜色分布 —— 不确定这在过去是否有了相关的工作。其他有趣的想法包括尝试一种“视觉均匀”颜色空间，像 L a b* 来聚类，并且还尝试为一个给定的图片自动确定 “最佳”集群个数 。

另一方面，我还有一堆博客没写，因此，目前我将标记这个项目，并邀请你检出 noteshrink.py github repo。直到下一次！

---

1. 手写笔记样本已经得到了我的学生 Ursula Monaghan 和 John Larkin 的许可。
2. 这里显示的图片实际上向下取样为 150 分辨率，以使得页面加载速度更快。
3. 我们的复印机 做 得不错的一件事是保持 PDF 文件大小比较小 —— 对于这些类型的文档，可以得到约 50-75 KB 每页。
4. 这得到红、绿和蓝 加法三原色 。你的小学美术老师可能告诉过你，三原色是红、黄、蓝。这是一个 谎言 ；然而，有种 减法三原色 ：青色、黄色和品红色。加法三原色涉及到组合 光 (这是显示器发射的光)，而减法三元色涉及到在油墨和染料中找到的组合 色素 。
5. 图片由 Wikimedia Commons 用户 Maklaan 提供。许可证：CC BY-SA 3.0
6. 看看维基百科的 直方图文章 中的“提示”样例，获得为什么提高容器大小有帮助的另一个例子。
7. 图片由 Wikimedia Commons 用户 SharkD 提供。许可证：CC BY-SA 3.0
8. 为什么 k =7 而不是 8 呢？在最终图像中我们想要 8 种颜色，而我们已经确定了背景色…
9. 是的，我在瞪你，Mac OS 图像捕获 …

原文： Compressing and enhancing hand-written notes