前言
之前想對圖片素材進行分類管理，除了打標簽，還有一樣是通過主題色進行分類，于是開始尋找能提取主主題色的工具，最后找到了大名鼎鼎的 Leptonica 庫，其中就有中位切割演算法的實作，下面附上中位切割演算法的其它語言版本的實作，
- JavaScript版：quantize （此庫有提取顏色數量不對的問題，見 issues/9）
- Java版：theme-color （我自己基于 quantize 實作的Java版）
中位切割演算法（Median cut）
theme-color 專案的效果如下：
講中位切分法之前，我們先聊聊顏色該如何描述，
顏色模型
常見的顏色模型有RGB，HSV等，中位切分法基于 RGB 模型，RBG 模型是一種加色模型，將紅（Red）、綠（Green）、藍（Blue）三原色的色光以不同的比例相加，以合成產生各種色彩光，每個像素由24位編碼的RGB值表示，使用三個8位無符號整數（0到255）表示紅色、綠色和藍色的強度，所以RGB能表示1677萬（256?256?256）萬種顏色，如果將所有的顏色采用三維空間來進行描述，則如下圖所示：
演算法實作
中位切割演算法（Median cut） 是Paul Heckbert于1979年提出來的演算法，原理是將影像顏色映射成三維色彩空間中的長方體，沿著RGB中最長的一邊從顏色數量統計的中位數一切為二，使得到的兩個長方體所包含的像素數量相同，重復上述步驟，直到得到想要數量的長方體，
原理很簡單，但是 Leptonica 的實作包含了很多細節，
壓縮顏色總數
演算法需要統計影像的每種顏色的數量（色彩分布圖），也就是需要將三維的長方體映射到一維的陣列中，RGB 總顏色數量達到1677萬 (2^8 * 2^8 * 2^8)，這在檢索的時候會造成不小的性能開銷，如果將8位無符號整數（0到255）壓縮到5位無符號整數（0到31），那么總數量減少到 2^5 * 2^5 * 2^5 = 32768，而且可以使用 int 來表示陣列下標了，
中位切分的優化
在原始的中位切分法中，是沿著顏色數量統計的中位數將長方體（vbox）一切為二的，Leptonica 中對此進行了優化，改成通過中位數將 vbox 分為左右兩個vbox（只是分出左右，還未切割），然后從左右選出體積較大的vbox的中點進行切割，下面放上作者原話
Determine the cut planes, making sure that two vboxes are always produced. Generate the two vboxes and compute the sum in each of them. Choose the cut plane within the greater of the (left, right) sides of the bin in which the median pixel resides. Here's the surprise: go halfway into that side. By doing that, you technically move away from "median cut," but in the process a significant number of low-count vboxes are produced, allowing much better reproduction of low-count spot colors.
長方體體積大包含像素少問題
存在某些條件下 VBox 體積很大但只包含少量像素，解決的方法是，每次切分前先對所有 vbox 排序，再取出優先級最高的 vbox 進行中位切分，如果需要切割的 vbox 總數為 total，那前 total * FractByPopulation 個 vbox 以 vbox包含的像素數 排序，后 total * (1-FractByPopulation) 個 vbox 以 包含像素數 * vbox體積 排序，
FractByPopulation的值在 Leptonica 庫中為 0.85，在 quantize 庫中為 0.75
總結
本文介紹了中位切割演算法以及在 Leptonica 庫中的實作，
參考資料
三原色光模式 - 維基百科，自由的百科全書 (wikipedia.org)
中位切割演算法 - 維基百科，自由的百科全書 (wikipedia.org)
影像主題色提取演算法_mmcq演算法_mingo_敏的博客-CSDN博客
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/546291.html
標籤：Java
上一篇：springboot~ConditionalOnProperty注解的使用
下一篇：03-RabbitMQ的作業模式