淺談圖片取樣

早期沒有圖形介面時，在電腦上想使用文字模式顯示圖像，一種方式是透過ASCII可見字元來呈現圖像內容。在圖形介面早就普及的現在，這種顯示圖像的方式被視為一種文字藝術，你可以在維基百科〈ASCII藝術〉條目中，看到維基百科圖示的ASCII藝術，實際上，字元並沒有灰階值的差別，然而視覺上卻以為是張灰階圖。

基於半色調、藍雜訊來實現圖片取樣

這類ASCII藝術的實現不難，我們可將圖片轉為灰階，再將灰階值四對應某個字元，而常見的字元組合會是：「$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/\|()1{}[]?-_+~<>i!lI;:,"^`\'.」（.後方有個空白字元）顯示ASCII時，建議使用等寬字型。

之所以覺得有灰階效果，是因為字元串由左而右的字元越來越簡單，以印刷技術而言，可看成墨點大小的變化，而藉由大小組合，能在視覺產生灰階效果。

這其實是半色調（Halftone）的應用變化。通常半色調是相對於連續調（continue tone），連續調是指圖像基本元素（例如像素）本身含有顏色的深淺，可建立連續的顏色變化，例如灰階值的連續性。半色調的基本元素只有兩種狀態：有色或無色，藉由改變元素的大小或頻率，來模擬明暗變化，你應該常看過這種半色調印刷的應用場合，也就是漫畫。

如果想看看Python的實現，可以參考〈ASCII Art文字藝術〉，其中的每個像素，就是一個取樣點，取樣點間的距離固定，灰階值會對應至某個字元，由於字元簡單或複雜，相當於改變基本元素的大小來實現半色調，這稱為調幅加網（AM Screening）。

相對地，若元素大小固定，但鄰近取樣點之間的距離是依照灰階值來決定，也就是在一定範圍內，依照灰階值來決定取樣點的頻率，就稱為調頻加網（FM Screening），例如目前取樣點若較黑，候選的鄰近取樣點就較近，反之較遠，問題在於決定遠近範圍後，接下來該如何在範圍內決定取樣點位置。

隨機取樣點？

第一個想法是在範圍內隨機取樣。若範圍為r，在以r為半徑的圓範圍內隨機取樣，這牽涉兩個問題：

第一是圓內取樣方式，單純讓半徑隨機於0到 r，角度隨機於0到360來取樣是錯的，這會造成接近圓心的取樣點過密，關於這部分，你應該看看〈Disk Point Picking〉有關圓內隨機點分布說明。

若圓內每個點的取樣機率一致，單純隨機取樣面臨的第二問題出現，也就是疊頻（Aliasing）。簡單來說，兩個取樣點各自隨機決定的鄰近取樣點，距離可能過近甚至重疊，因而造成取樣後的結果，會有過疏或過密的區域。

可以想像如何在圖片上散布雜訊？雜訊值與像素值相加後，高於某值不取樣，低於某值就取樣，而隨機散布雜訊，概念相當於散布白雜訊（white noise），可簡單理解為：各雜訊值各自的總數是差不多的（相當於光線中各頻率的光強度差不多）。

若想避免取樣點間距離過近或重疊，我們可能直覺想到的是：檢查新取樣點與既有取樣點間是否保持適當距離，若能做到這點，取樣點的散佈方式，概念上相當於藍雜訊（blue noise）。你可以在維基百科〈雜訊的顏色〉條目中看到藍雜訊的頻譜，再想像成雜訊值各自的總數也呈現相同的趨勢。

一個有趣的事實是，視網膜細胞的排列方式也呈現出藍雜訊的特徵，或許是半色調能在視覺造成灰階效果的原因。視網膜細胞數量龐大，但畢竟是細胞，仍須有一定的大小，若在每個細胞位置畫點，點與點會有一定距離，不會太近，也不會太遠（畢竟要在有限範圍容納龐大數量細胞），由於取樣點的分布符合Poisson分布，又稱為Poisson Disk取樣。

Poisson Disk取樣

想讓取樣點之間有一定的距離範圍，直覺想法是生成新取樣點時，與既有的全部取樣點進行距離檢查，不過這需要龐大的運算。

為了改善這樣的效能問題，有許多方式，例如，Cem Yuksel的Weighted Sample Elimination，先產生一堆隨機點，然後基於KD-tree，以空間分割的方式，來取得鄰近點，並消去相鄰過近的點；Robert Bridson的〈Fast Poisson Disk Sampling in Arbitrary Dimensions〉，由於速度快且實作簡單，成為常見的解決方案。

以二維圖像來說，Bridson的做法是，將圖像分割為棋盤式的格子，每格只允許一個採樣點，因此，若採樣點之間最近距離只能是r，那麼格子的寬度就是r/sqrt(2)，Bridson可以擴展至n維，這時空間大小的單位就是r/sqrt(n)。

開始進行取樣時，取樣清單中加入第一個點，置入對應的格子裡，並將該點加入一個活動點清單，接著開始迭代，每次從活動點清單中隨機取得一個活動點，然後試著在r到2r的環狀範圍裡取k個點，由於每格只允許一個採樣點，這k個點只要看看活動點的九宮格內，是否出現了小於r的點，不用去檢查全部既有的取樣點，從而避免了方才的效能問題。

在Bridson的論文裡談到，k通常取為30就可以了。如果k個取樣點都不合格，作廢當時的活動點，下次迭代就不會拿來作為取樣基礎，而如果k個點有若干點符合資格，Bridson並未明確說明該怎麼做，只說加入取樣清單與活動點清單，也就是，後續的取樣點可以基於此次的取樣點作為基礎。

關於k個點有若干點符合資格的處理，網路上有人說採距離最長的，有人說取最短的，實際試過兩種後，我發現採用距離最短的取樣點，密度比較高，另外，由於每個新取樣點都是從活動點衍生出來，若將活動點與衍生點連接成線，可得到樹狀圖，取最短距離作為取樣點時，樹狀圖不易出現交樹枝交叉，可以參考〈poisson-disc-sampling.js〉，這是使用p5.js的實作。

我也嘗試過將只取第一個合格點，或全部適用的新取樣點都納入的實現，若不在乎密度也不考量樹枝交叉的問題，這能加快整個圖像的取樣速度，最後結果看來，距離分布也還算均勻。正如方才談到的，k通常取30就可以了，太大沒意義，太小的話，容易k個取樣點都不合格，導致無法涵蓋整個範圍。

對此，《The Nature of Code》的作者在〈Poisson-disc Sampling〉有段教學影片，循序漸近實現Poisson Disk取樣，有興趣可以看看。

多樣的應用

若想實際應用至半色調，在考量新取樣點時，可以將取樣點灰階值納入考量，當灰階值差異過大時，建立一棵新的取樣樹，取樣距離r根據新的取樣點灰階值設置，也就是整張圖像的取樣，可以是多棵取樣樹組成，多棵取樣樹的基本建立方式，我在〈poisson-trees.js〉有個簡單的p5.js實作可以參考。

除了半色調應用，Poisson Disk取樣也可用於彩色圖片的取樣，結果會構成點彩畫派（Pointillism）的風格，也就是用很粗的彩點堆砌，創造整體形象的油畫繪畫方法。

或者，我們可以將取樣點作為Voronoi分割的依據，取樣的顏色填滿分割後的凸邊形，構成圖像的晶格化效果。想看到更多這類作法，可以試著搜尋「blue noise」、「Poisson Disk」的圖片，將會看到許多相關的圖像處理應用。