使用原始形状重新生成图像（图形优化问题）

Question

基于这个原始想法，你们中的许多人可能已经看到过：

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

我想尝试采用不同的方法：

你有一个目标图像。假设你每次只能添加一个三角形。存在某些三角形（或在并列情况下的若干三角形），可以最大化图像相似度（适应性函数）。如果你可以强制搜索所有可能的形状和颜色，你会发现它。但是这是非常昂贵的。搜索所有三角形是一个10维的空间：x1, y1, x2, y2, x3, y3, r, g, b, a。

我使用了模拟退火并取得了不错的结果。但我想知道是否可以进一步改进。一个想法是实际分析目标图像和当前图像之间的差异，并寻找可能是放置新三角形的好位置的“热点”。

你会使用什么算法来找到最大化图像相似度的最佳三角形（或其他形状）？

算法是否应该因处理粗略细节和精细细节而有所不同？我还没有让它运行足够长的时间来开始优化更精细的图像细节。似乎随着运行时间的增加，它对添加新形状变得“羞怯”……使用低 alpha 值（非常透明的形状）。

目标图像和重现图像（28个三角形）：

编辑！我想到了一个新的想法。如果给定形状坐标和透明度值，则可以通过分析当前图像和目标图像中的像素来计算形状的最佳RGB颜色。这样就从搜索空间中消除了3维，你知道使用的颜色始终是最优的！我已经实现了这个功能，并尝试使用圆形代替三角形进行另一次运行。

300个圆和300个三角形：

- FogleBird

Answer 1

一个使用多次运行的想法：

• 将原始算法作为第一次运行，设定一个预定数目步骤后停止。
  • 分析第一次运行的结果。如果大部分图像的结果都不错，但是在某个小区域表现很差，增加该区域的重视程度。
• 当运行第二次时，将强调部分的误差贡献翻倍（见注释）。这将导致第二次在该区域进行更好的匹配。另一方面，相对于第一次运行，在图像的其他部分它会做得更差。
• 重复执行许多运行。

最后，使用遗传算法来合并结果-可以从所有先前运行生成的三角形中进行选择，但不能生成任何新的三角形。

注：事实上有一些计算误差贡献应该增加多少的算法。被称为http://en.wikipedia.org/wiki/Boosting。然而，我认为即使没有使用数学上精确的方法，这个想法仍然有效。

- rwong

Answer 2

我建议你开始尝试使用顶点颜色（每个顶点具有不同的RGBA值），这会略微增加复杂性，但极大地提高了快速匹配目标图像的能力（假设是具有自然渐变的摄影图像）。

你的问题似乎暗示着要远离基因方法（即尝试找到适合的三角形而不是演化它）。但是，它可以被解释两种方式，所以我将从基因方法回答。

一种聚焦突变的方法是在图像上应用网格，计算哪个网格方块与目标图像中相应的网格方块最不匹配，并确定哪些三角形与该网格方块相交，然后标记它们以获得更高的突变几率。

同时，您还可以通过对最佳匹配网格方块进行较小的基于网格的检查来改进细节。

例如，如果您正在图像上使用8x8网格：

- 确定64个网格方块中哪个是最差的匹配，并标记相交（或附近/周围）的三角形以获得更高的突变几率。 - 确定哪个64个网格方块是最佳匹配，并在其中一个小的8x8网格内重复操作（即在最佳网格方块内的8x8网格）。这些可以被标记为添加新三角形的可能位置，或者只是微调细节。

- jhabbott

---

你有尝试过这个想法吗？我真的很想看看当你使用具有不同顶点颜色的Gouraud着色三角形时会发生什么。 - jhabbott

Answer 3

我认为那个算法实际上非常简单。

P = 200 # size of population 
max_steps = 100

def iteration
  create P totally random triangles (random points and colors)
  select one triangle that has best fittness
  #fitness computing is described here: http://rogeralsing.com/2008/12/09/genetic-programming-mona-lisa-faq/
  put selected triangle on the picture (or add it to array of triangles to manipulate them in future)
end

for i in 1..max_steps {iteration}

- dfens

---

我在任何其他尝试之前就尝试了这个，只是为了测试我的渲染代码。它的效果比我想象的要好，但远不如我的模拟退火解决方案。 - FogleBird

Answer 4

非常有趣的问题！我的分析方法是使用进化策略优化算法。它并不快，适用于三角形数量较小的情况。我没有得到原始图像的好近似值——但这部分是因为我的原始图像太复杂了——所以我没有尝试过很多次算法重启来看看EVO能产生什么其他的次优结果......无论如何，这并不是一种坏的抽象艺术生成方法 :-)

- Agnius Vasiliauskas