[[225234]]

大數(shù)據(jù)文摘作品

編譯：HAPPEN、于樂(lè)源、小魚(yú)

一位樂(lè)于分享學(xué)生精彩筆記的大學(xué)教授對(duì)于掃描版的文件非常不滿(mǎn)意——顏色不清晰并且文件巨大。他因此用python自己寫(xiě)了一個(gè)小程序來(lái)解決這個(gè)問(wèn)題。

這個(gè)程序可以用來(lái)整理手寫(xiě)筆記的掃描件哦，輸出的圖片不僅很清晰，而且文件大小只有100多KB!

先來(lái)看一個(gè)例子：

左：輸入掃描件(300 DPI，7.2MB PNG/790KB JPG.)

右：輸出圖片(300 DPI，121KB PNG)。

如果你急于上手操作，可以直接查看Github repo中的代碼，或跳到本文結(jié)果部分，看看炫酷的顏色簇交互式三維圖。

免責(zé)聲明：上述過(guò)程或許可以用Office Lens應(yīng)用程序?qū)崿F(xiàn)，或者其他工具也可以實(shí)現(xiàn)。本文只是一個(gè)實(shí)用方法分享，不是什么發(fā)明創(chuàng)造。

起因

一些我任課的班級(jí)沒(méi)有指定的教材，這是因?yàn)槲腋矚g每周指定一個(gè)“學(xué)生記錄員”，與班里其他同學(xué)分享他們的講義。這樣可以為學(xué)生提供一些書(shū)面資源，以便他們需要時(shí)可以進(jìn)行對(duì)照。筆記以PDF的格式發(fā)布在課程網(wǎng)站。

在學(xué)校，我們有一臺(tái)能夠?qū)⒐P記掃描成PDF文件的“智能”復(fù)印機(jī)，但是它生成的文件不夠招人喜歡。下圖是手寫(xiě)筆記的輸出示例：

復(fù)印機(jī)好像隨意地決定是否將每個(gè)數(shù)學(xué)符號(hào)進(jìn)行二值化，或者轉(zhuǎn)換后的JPG很不理想(如上圖中的平方根符號(hào))。因此我決定對(duì)上述問(wèn)題進(jìn)行優(yōu)化。

概述

我們從某位同學(xué)一頁(yè)漂亮的筆記開(kāi)始處理，筆記掃描件如下：

以300 DPI精度掃描的原始PNG圖像大小約為7.2MB;轉(zhuǎn)換為圖像品質(zhì)較高的JPG格式后，文件大小約為790KB。由于PDF掃描件通常采用PNG或JPG作為容器格式，我們當(dāng)然不希望在轉(zhuǎn)換為PDF時(shí)損失文件信息。

但是考慮到網(wǎng)頁(yè)加載時(shí)間，每頁(yè)筆記800KB已經(jīng)相當(dāng)大了，我希望獲得文件大小更接近100KB/頁(yè)的圖像。

雖然這位學(xué)生的筆記很整潔，但筆記的掃描件看起來(lái)有點(diǎn)亂。原因是復(fù)印機(jī)將這頁(yè)筆記的反面內(nèi)容也進(jìn)行了掃描，這會(huì)分散讀者的注意力，而對(duì)于JPG或PNG編碼器來(lái)說(shuō)，這種情況比純色背景的圖片更難壓縮。

下圖是我寫(xiě)的noteshrink.py程序的輸出結(jié)果：

輸出結(jié)果是一個(gè)相對(duì)較小的PNG文件，大小只有121KB。不僅圖像內(nèi)存變小，而且看起來(lái)更清晰!這才是我想要的!

處理過(guò)程和彩色圖像基礎(chǔ)

以下是生成小內(nèi)存且清晰的圖像所需的步驟：

1. 識(shí)別原始掃描圖像的背景色。
2. 根據(jù)背景色的不同閾值分離出前景色。
3. 從前景色中選擇幾種“代表性顏色”，作為生成PNG過(guò)程中需要的索引色。

在深入研究這些步驟之前，先來(lái)了解下彩色圖像是如何以數(shù)字形式進(jìn)行存儲(chǔ)的。由于人類(lèi)眼睛中有三種不同類(lèi)型的感色細(xì)胞，因此我們可以通過(guò)組合不同強(qiáng)度的紅色、綠色和藍(lán)色來(lái)重建任何顏色。重構(gòu)過(guò)程就是將每種顏色與RGB顏色空間中的三維點(diǎn)一一對(duì)應(yīng)，如下所示：

盡管真正的向量空間允許無(wú)限數(shù)量的像素亮度連續(xù)變化，但為了將顏色以數(shù)字形式存儲(chǔ)在計(jì)算機(jī)上，我們需要對(duì)上述像素范圍進(jìn)行離散處理——通常紅色、綠色和藍(lán)色分別用8位通道色表示。這種將像素類(lèi)比成三維色彩空間坐標(biāo)的分析方法將為我們接下來(lái)的理解與重建提供巨大的幫助。

識(shí)別背景色

由于頁(yè)面的大部分地方?jīng)]有墨跡或線條，也許有人會(huì)認(rèn)為紙張本身的顏色將會(huì)是掃描圖像中出現(xiàn)頻率最高的一種顏色——即復(fù)印機(jī)會(huì)將白紙的每個(gè)像素表示為相同的RGB值。

如果結(jié)果真是這樣，那么分離背景色將不會(huì)有任何問(wèn)題。遺憾的是，情況并非總是如此，由于復(fù)印機(jī)玻璃板上的灰塵和污跡、頁(yè)面本身的顏色變化、傳感器噪聲等不同的因素，像素的RGB值會(huì)發(fā)生隨機(jī)的變化，頁(yè)面的“實(shí)際顏色”其實(shí)可能涵蓋數(shù)千個(gè)不同的RGB值。

掃描圖像的原件大小為2081×2531，共5267011個(gè)像素點(diǎn)。雖然我們可以逐一處理每個(gè)像素點(diǎn)，但是處理輸入圖像的代表性像素點(diǎn)會(huì)更快。

noteshrink.py程序默認(rèn)采集輸入圖像5%的像素點(diǎn)(在掃描精度為300 DPI的情況下)。接下來(lái)，我們先選擇一個(gè)10000點(diǎn)的小像素集，結(jié)果如下圖所示：

雖然結(jié)果與筆記掃描件的頁(yè)面差異很大(沒(méi)有手寫(xiě)墨跡)——但兩幅圖像的顏色分布幾乎完全相同。兩張圖片中大多像素點(diǎn)呈灰白色，也有少量紅色、藍(lán)色和深灰色的像素點(diǎn)。然后我們對(duì)10000個(gè)像素點(diǎn)按亮度進(jìn)行了排序(例如將每個(gè)像素點(diǎn)的R、G和B進(jìn)行求和)，結(jié)果如下：

從遠(yuǎn)處看，圖像底部80-90%的區(qū)域看上去是同一種顏色;然而仔細(xì)觀察后，你會(huì)發(fā)現(xiàn)很多不一致的細(xì)節(jié)。事實(shí)上，上圖中主要顏色(RGB值為(240,240,242))的像素個(gè)數(shù)僅為226——占比還不到總像素?cái)?shù)10000的3%。

由于上述方法中主要顏色占總像素的比例很小，能否將它作為代表性顏色來(lái)描述圖像的顏色分布就值得懷疑。如果在尋找方法之前先減小圖像的位深度，我們將更好地識(shí)別頁(yè)面的主要顏色。

因此我們把每個(gè)色彩通道四個(gè)最低有效位置零，將原來(lái)每個(gè)8位通道色簡(jiǎn)化成4位通道色，結(jié)果如下所示：

現(xiàn)在主要顏色的RGB值為(224,224,224)，并且其像素點(diǎn)數(shù)為3623，占總像素的36%。通過(guò)減少位深度，實(shí)際上我們將相似的像素分到更大的“組”，這將更容易在數(shù)據(jù)中找到一個(gè)強(qiáng)峰。

可靠性和精確度之間存在一個(gè)折衷方案：小像素集可以更好地區(qū)分顏色，但大像素集處理起來(lái)更可靠。最后，我決定用6位通道色表示來(lái)識(shí)別背景色，這似乎是兩個(gè)極端之間的一個(gè)最佳選擇。

分離前景色

一旦識(shí)別出背景色，就可以根據(jù)圖像中每個(gè)像素與背景色的相似程度來(lái)進(jìn)行閾值計(jì)算。通常來(lái)說(shuō)，通過(guò)計(jì)算兩個(gè)像素坐標(biāo)的歐幾里得距離，再與預(yù)設(shè)的閥值進(jìn)行比較就能得到他們之間的相似性。可這個(gè)最常用的方法卻無(wú)法正確區(qū)分下面的幾個(gè)顏色：

下表展示了每種顏色與背景色的歐幾里德距離：

從表中可以看出，筆記反面滲過(guò)來(lái)的深灰色應(yīng)該被分為背景色，但它與白色背景的差值要比粉紅色的差值更大，而粉紅色應(yīng)該是前景色。如果使用這種方法，就無(wú)法有效分離出粉紅色的前景色，因?yàn)榭倳?huì)包含滲過(guò)來(lái)的深灰色。

為了解決這個(gè)問(wèn)題，我們可以將圖片從RGB空間移動(dòng)到色相-飽和度-亮度(Hue-Saturation-Value，HSV)空間，HSV將RGB的立方體轉(zhuǎn)變?yōu)閳A柱體，其剖面圖如下：

HSV圓柱體上表面邊緣呈現(xiàn)圓形分布的彩虹色，色度(hue)是指圍繞圓柱體的中心軸旋轉(zhuǎn)的角度(紅色為0°)。圓柱體的中心軸從底部的黑色、中間的灰色漸變到頂部的白色——整個(gè)軸的飽和度(saturation)為0，外圓周上鮮艷的顏色飽和度都為1。最后，亮度(value)是指顏色的整體亮度，其變化范圍從底部的暗色調(diào)到頂部的亮色調(diào)。

現(xiàn)在讓我們用HSV重新區(qū)分一下之前的顏色：

從表中可以看出，白色、黑色和灰色的亮度差別很大，但它們的飽和度都很接近且數(shù)值較低——遠(yuǎn)低于紅色或粉紅色。通過(guò)分析圖像的HSV值，我們可以利用下面的標(biāo)準(zhǔn)來(lái)標(biāo)記屬于前景色的像素，只需要滿(mǎn)足其中一條就可以：

• 該像素的亮度與背景色的差值大于0.3;
• 該像素的飽和度與背景色的差值大于0.2;

第一條標(biāo)準(zhǔn)可以分離出筆記中的黑色墨跡，第二條標(biāo)準(zhǔn)則可以分離出紅色墨跡和粉色線條，且這兩個(gè)標(biāo)準(zhǔn)在選取前景色時(shí)排除了筆記反面滲透過(guò)來(lái)的灰色。但不同的圖像可能需要不同的飽和度或亮度閾值，詳情請(qǐng)參閱結(jié)果部分。

選擇一組有代表性的顏色

當(dāng)我們將前景色分離后，會(huì)得到與頁(yè)面上筆記的顏色相對(duì)應(yīng)的一組顏色。將得到的像素點(diǎn)重新放進(jìn)RGB空間并計(jì)算每個(gè)像素對(duì)應(yīng)的坐標(biāo)，可以看到新的散點(diǎn)圖呈現(xiàn)簇狀，每一個(gè)顏色會(huì)形成自己的色塊：

由three.js提供支持的交互式三維圖

現(xiàn)在我們的目標(biāo)是將原始的圖像(24位/像素)中的所有顏色用8種“索引色”進(jìn)行替換(8并非固定的數(shù)字)。這樣做有兩種好處：首先，它縮小了文件的大小，因?yàn)楝F(xiàn)在只需要3位就可以指定一種顏色(因?yàn)? = 2^3);此外，它使得生成的圖像在視覺(jué)上更美觀，因?yàn)樵谧罱K輸出的圖像中，相似顏色的筆記都會(huì)只用一種顏色替代。

為了實(shí)現(xiàn)這個(gè)目標(biāo)，我們通過(guò)數(shù)據(jù)驅(qū)動(dòng)的方式，也就是利用上圖中的“簇狀”特性，選擇每個(gè)色簇的中心坐標(biāo)來(lái)表示這一組顏色。用術(shù)語(yǔ)說(shuō)，我們將通過(guò)聚類(lèi)分析來(lái)解決一個(gè)色彩量化問(wèn)題(其實(shí)是向量量化)。

具體的做法是，通過(guò)k-means算法在一個(gè)顏色簇中找到一個(gè)點(diǎn)，這個(gè)點(diǎn)到其他每個(gè)點(diǎn)的平均距離之和最小。對(duì)上述數(shù)據(jù)集使用這個(gè)方法，得到7個(gè)不同的顏色簇：

由three.js提供支持的交互式三維圖

在這張圖中，黑色輪廓彩色實(shí)心的點(diǎn)表示前景色像素的顏色坐標(biāo)，通過(guò)彩色的線將它們連接到RGB色彩空間中最近的中心點(diǎn)。當(dāng)圖像轉(zhuǎn)換為索引顏色時(shí)，每個(gè)前景色像素的顏色將被替換為距其最近的中心點(diǎn)的顏色。最后，包圍每個(gè)顏色簇的圓表示每個(gè)中心點(diǎn)距相關(guān)像素的最遠(yuǎn)距離。

細(xì)節(jié)調(diào)整

除了能夠設(shè)置亮度和飽和度的閾值之外，noteshrink.py還具有幾個(gè)其他值得一提的功能。默認(rèn)情況下，它通過(guò)將亮度的最小和最大值重新調(diào)整為0和255來(lái)增加最終調(diào)色板的鮮艷度和對(duì)比度。如果不進(jìn)行調(diào)整，上述掃描件的8色調(diào)色板將如下所示：

調(diào)整后的調(diào)色板色彩更鮮明：

在完成前景色分離后，還有一個(gè)選項(xiàng)可以強(qiáng)制將背景色變?yōu)榘咨Ｍㄟ^(guò)轉(zhuǎn)換為索引顏色的圖像可以進(jìn)一步壓縮PNG文件，noteshrink.py還可以運(yùn)行如optipng、pngcrush或pngquant等圖像優(yōu)化工具。

該程序最終會(huì)將多個(gè)壓縮后的圖像合并為一個(gè)PDF文件，就像使用ImageMagick的轉(zhuǎn)換工具一樣。此外，noteshrink.py會(huì)自動(dòng)對(duì)輸入文件名進(jìn)行數(shù)字排序(而不是像shell globbing 那樣按字母順序排列)。當(dāng)復(fù)印機(jī)輸出的文件名是scan 9.png和scan 10.png時(shí)是非常有幫助的，上述排序功能保證了壓縮后的頁(yè)面在PDF中也保持同樣的順序。

結(jié)果

以下是一些程序輸出的例子。第一個(gè)輸出的PDF使用默認(rèn)的閾值設(shè)置，看起來(lái)很棒：

不同顏色簇的可視化：

由three.js提供支持的交互式三維圖

第二個(gè)PDF需要將飽和度閾值降低到0.045，因?yàn)樗{(lán)灰色的線條顏色太深不便于閱讀：

對(duì)應(yīng)的顏色簇：

由three.js提供支持的交互式三維圖

最后這個(gè)PDF來(lái)自于工程師的方格紙，在這個(gè)過(guò)程中我將亮度閾值設(shè)置為0.05，因?yàn)楸尘昂途€條之間的對(duì)比度非常低：

對(duì)應(yīng)的顏色簇：

由three.js提供支持的交互式三維圖

綜上，這四份PDF文件大小約788KB，平均每頁(yè)130KB大小。

結(jié)論與展望

我很高興能開(kāi)發(fā)一個(gè)實(shí)用的工具，這個(gè)工具可以將課程網(wǎng)站中的手寫(xiě)筆記的PDF進(jìn)行加工和美化。與此同時(shí)，記錄下這整個(gè)過(guò)程也讓我受益匪淺，我先后在維基百科上補(bǔ)充了關(guān)于顏色量化的更多內(nèi)容，也促使我嘗試并學(xué)習(xí)了three.js。

如果再次啟動(dòng)這個(gè)項(xiàng)目，我想嘗試一下其他的量化方案，就在前幾天還在想用光譜簇結(jié)合最近鄰圖的方式去嘗試一下，當(dāng)時(shí)十分興奮認(rèn)為這是一個(gè)絕佳的方案，然后就發(fā)現(xiàn)已經(jīng)有一篇2012年的論文提出了完全一樣的構(gòu)思，哎…

你也可以嘗試使用最大期望算法來(lái)生成描述顏色分布的高斯混合模型——不確定之前是否有人做過(guò)類(lèi)似的實(shí)現(xiàn)。當(dāng)然感興趣的同學(xué)也可以試試其他有趣的想法，如使用Lab這類(lèi)視覺(jué)上均勻的色彩空間進(jìn)行顏色聚類(lèi)，并嘗試自動(dòng)給出指定圖像的“最佳”聚類(lèi)數(shù)量。

原文鏈接：https://mzucker.github.io/2016/09/20/noteshrink.html

【本文是51CTO專(zhuān)欄機(jī)構(gòu)大數(shù)據(jù)文摘的原創(chuàng)譯文，微信公眾號(hào)“大數(shù)據(jù)文摘（ id: BigDataDigest）”】

戳這里，看該作者更多好文