如何找到最合適的X顏色來表示圖像？

Question

假設我們有格式爲（r，g，b）的[1..n]個像素的圖像。

我們現在可以選擇格式爲（r，g，b）的X顏色來生成第二個相同大小的圖像。 這些X顏色中的每一個都將代表n/x自由選擇我們新圖像的像素。

現在我們計算兩幅圖像上[1..n]中的每個像素對並將它們的色差求和sqrt（sqr（R1-R2），計算從原始圖像到新生成圖像的平方偏差）+ SQR（G1-G2）+ SQR（B1-B2））。

現在讓我們假設我們分配了所有的X顏色，這樣這個平方偏差的總和最小。

這裏我的問題是：如何找到完美的X顏色，所以在完美的分佈後，我們的平方偏差與其他顏色集相比是最小的？

如果某些信息丟失或不清楚（由於我的英語不好），請告訴我。

謝謝！

PS： 爲了更好的理解，我添加了一個X = 4的例子。顏色的分佈幾乎是最優的，但我確定我沒有選擇完美的4種顏色來表示原始圖像。

不幸的是我沒有張貼圖像的聲譽，所以我增加了鏈接到它，而不是 Before-After example for X=4

Answer 1

的問題稱爲color quantization，即給定的輸入n顏色和給定大多數m < n輸出顏色，找到顏色值的最佳分配，使總顏色誤差總和最小。

最佳量化是NP hard，大致意味着沒有已知的算法在一般情況下起作用並且不必嘗試所有可能的組合。

有--however--各種近似算法，其中大部分是基於聚類算法，由於問題基本上等於在n點字段來定位m點以使得的總和（很少）m點之間的距離和所有（很多）n點之間的距離是最小的。

還要注意，在RGB空間中使用歐幾里得距離決不是一個很好的度量來確定colorimetric color difference。