在时隔四年零四天之后，我更新了使用有限种颜色逼近图像和使用有限种颜色更好地逼近图像的续集。
我发现，似乎我不仅中学时就很喜欢（我当时认知中的）数学，而且乱搞的这些东西其实都是数学——当时我以为这些写代码的东西就属于CS，现在我才知道这完全是属于应用数学/运筹学/统计。真正的CS研究的东西（什么人机交互，虚拟现实，机器人，深度学习，数据库，网络，系统硬件之类）反而几乎都是我不感兴趣的；可能唯一的例外是NLP。
虽然说我对CS不感兴趣，但对TCS由于算法竞赛的缘故还是相当感兴趣的；正因为如此，我这学期才选了数学系的“算法分析与设计”课。抛开惨烈的期末考试与很可能惨不忍睹的绩点不谈，我觉得这课还是挺有意思的。它在讲近似算法的第一节课就提到了所谓的Center Selection问题。我仔细一看，这不就是我在第一篇博客里提出的问题吗！
$\dots$于是我灵光一闪想到了这么一个东西：把图像里面的所有颜色记成三维空间中的点，然后问题就变成了：使用\(k\)个球，覆盖住所有的点，让最大的半径最小。然而这肯定是个我不会做的题，因为二维版本我就不会。可是我会乱搞！$\dots$
由于课程提到的缘故，我很轻松地就搜索到了该问题的wiki页面。不知道为啥我四年前就搜不到这个早就被充分研究过的问题，反而搜到了K-means，因而写了第二篇博客。更让我惊异的是，这两个问题几乎完全相同，仅仅有$L^{2}$范数和$L^{\infty}$范数这一个区别，且两者都被充分研究，但两者的wiki页面上完全没有提到对方的存在！毕竟他们位于完全不同的学科分支上：Metric k-center是TCS/图论中的问题，而K-means是统计学/数据科学/信号处理中的问题。
无论是课程内容，还是Metric k-center的wiki页面，都提到了该问题具有一个相当简单的贪心算法：记选出的球心集合为$V$，每次选择全集中离$V$中所有点最远的点，加入$V$。直到$\vert V\vert=k$。可以证明该算法的近似比为2，并且这已经是$\textrm{P}\ne \textrm{NP}$前提下的最优近似算法了。
但这只是一个理论结果；如此简单的算法，实际效果和我在第一篇博客里设计的那个相当复杂的算法比起来，究竟如何呢？很遗憾，我使用了几张风景图片进行测试，发现它的效果均不如第一篇博客中的算法。由于当时那两篇博客里使用的图片我找不到了（我本地只有压缩后的图片；Google图片搜索出的结果都有水印，不是原图），我使用了今天（2024年1月16日）的Bing Wallpaper进行测试，尝试用10种颜色进行逼近。
由此可见，该贪心算法的效果和我第一篇博客中的算法差不多，而K-means++的整体效果要好得多；不过，作为整张图片核心的暖色调小屋被K-means++无视了，就如同缺少了灵魂一般。其实第二篇博客里已经展示了这一现象，即太阳没有被K-means++表现出来。这是相当合理的，因为$L^2$更注重于全局的平衡，而$L^{\infty}$注重于极端情况的控制；这里的“暖色调小屋”和前两篇博客里的“太阳”一样，是颜色严重偏离该图片平均值的小型极端区域，因此$L^{2}$范数下无法精确地刻画。就更好地逼近图像而言，这两种优化目标明显是各有优劣的。
而数据也支持这一点。在第二篇博客里，我提到过K-means++的误差最大值是“略大于”这两种$L^{\infty}$下的最优化方法；而在这张图片里，K-means++的误差最大值约为222；而第一篇博客里的算法误差最大值约为76，相差了足足3倍。这是由于这张图片里不同色彩间的对比要远大于前两篇博客里的风景照。而简单的贪心算法的误差最大值约为82，只是略差于第一篇博客里的复杂算法（因此本文的标题是“使用有限种颜色更差地逼近图像”）。但毫无疑问，这个算法要快得多。
在阅读陈年代码的过程中，我意识到K-means++算法中启发性地找初始值的一步居然和这个简单的贪心算法如此相似；仍然记当前选出的球心集合为$V$，K-means++是把所有点按照到$V$的距离平方作为权重来随机选择下一个点加入$V$，因此到$V$距离更远的更容易作为下一个点被加入。如果删除随机化，只加入最远的点，就是前面那个贪心了。
后记
我在四年前误将K-means写成了“正确”的，其实也不过是一种近似比任意差的近似算法而已；特此更正。
不光是这里讨论的$L^{2}$范数和$L^{\infty}$范数，$L^{1}$范数也是有研究的，见k-medians clustering。不知道为啥这些统计学家只研究了$L^{1}$和$L^{2}$，却连一个到$L^{\infty}$的链接都不给，恐怕是在他们眼里噪声和异常值会让这个问题变得没有统计学意义。但正如前文的讨论，对少数极端数据的重视在图像逼近中是有意义的。
关于Metric k-center的讨论也经常在图上进行，被称为Vertex k-center problem；此时中心被限定为只能选已有的点。类似地，$L^{1}$的K-means也是有“只能选已有的点”的变种的，见k-medoids。
“使用有限种颜色逼近图像”其实是一个有实际意义的问题，并不是强行给聚类分析找应用；比如超大规模的图像可能会需要使用png的“调色盘模式”来压缩，见文件体积达到 1 GB 甚至 1 TB 的图片会呈现何种内容？ - 酱紫君的回答 - 知乎。
