原文：Compressing and enhancing hand-written notes
我写了一个程序来清理手写笔记扫描件，同时减少文件大小。
下面是样例输入输出：
左边： 输入扫描@ 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。我最喜欢的部分？不仅是图片变得_更小_，它还变得_更清晰_！
这里是生成上面压缩、干净的图片的所需步骤：
-
标识原始扫描图片的背景色。
-
通过与背景颜色的差异的阈值来分隔前景。
-
通过从前景选择少数“代表色”来转换成索引颜色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)使用默认阈值设置，看起来棒棒哒：
这里是颜色集群可视化：
下一个(PDF)要求降低饱和度阈值至0.045，因为蓝灰色线条是如此单调：
颜色集群：
最后，是一个来自于工程师的方格纸的样例扫描件(PDF)。对于这个，我将明度阈值设置为0.05，因为背景和线条的对比度非常低：
颜色集群：
这四个PDF文件总共占用约788KB，每张输出页面平均大约130KB。
我很高兴我可以做出一个能用来为我的课程网站准备抄写笔记PDF的实用工具。除此之外，我真的很喜欢准备这篇文章，特别是因为它促使我尝试改善Wikipedia的色彩量化页面展示的实质上是二维的可视化，也最终学会了three.js (非常有趣，会再次使用的)。
如果我重新审视这个项目，那么我想要玩一玩替代的量化方案。我这周突然想到的一个方案是在一组颜色样本的近邻图上使用谱聚类 —— 当我构思它的时候，我想这是一个令人兴奋的新想法，但原来有一篇2012的论文提出了这个确切的方法。哦，好吧。
你也可以尝试使用期望最大化，形成高斯混合模型来描述颜色分布 —— 不确定这在过去是否有了相关的工作。其他有趣的想法包括尝试一种“视觉均匀”颜色空间，像Lab*来聚类，并且还尝试为一个给定的图片自动确定“最佳”集群个数。
另一方面，我还有一堆博客没写，因此，目前我将标记这个项目，并邀请你检出noteshrink.py github repo。直到下一次！
-
手写笔记样本已经得到了我的学生Ursula Monaghan和John Larkin的许可。
-
这里显示的图片实际上向下取样为150分辨率，以使得页面加载速度更快。
-
我们的复印机_做_得不错的一件事是保持PDF文件大小比较小 —— 对于这些类型的文档，可以得到约50-75 KB每页。
-
这得到红、绿和蓝_加法三原色_。你的小学美术老师可能告诉过你，三原色是红、黄、蓝。这是一个谎言；然而，有种_减法三原色_：青色、黄色和品红色。加法三原色涉及到组合_光_ (这是显示器发射的光)，而减法三元色涉及到在油墨和染料中找到的组合_色素_。
-
图片由Wikimedia Commons用户Maklaan提供。许可证：CC BY-SA 3.0
-
看看维基百科的直方图文章中的“提示”样例，获得为什么提高容器大小有帮助的另一个例子。
-
图片由Wikimedia Commons用户SharkD提供。许可证：CC BY-SA 3.0
-
为什么_k_=7而不是8呢？在最终图像中我们想要8种颜色，而我们已经确定了背景色……
-
是的，我在瞪你，Mac OS 图像捕获…