23

基于这个最初的想法，你们中的许多人可能以前见过： 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 个三角形）：

替代文字 替代文字 替代文字

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

300 个圆和 300 个三角形：

替代文字 替代文字

4

4 回答 4

2

使用多次运行的想法：

  • 使用您的原始算法作为第一次运行，并在预定数量的步骤后停止它。
    • 分析第一次运行的结果。如果图像的大部分部分效果很好，但图像的一小部分效果不佳，则增加这部分的重点。
  • 运行第二次运行时，将强调部分的误差贡献加倍（见注释）。这将导致第二次运行在该区域进行更好的匹配。另一方面，相对于第一次运行，它在图像的其余部分会做得更糟。
  • 重复执行多次运行。

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

注意：实际上有一些算法可以计算误差贡献应该增加多少。它被称为http://en.wikipedia.org/wiki/Boosting。但是，我认为如果不使用数学上精确的方法，这个想法仍然有效。

于 2010-10-03T01:16:18.350 回答
2

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

您的问题似乎建议远离遗传方法（即试图找到一个合适的三角形而不是进化它）。然而，它可以被解释为两种方式，所以我将从遗传方法来回答。

集中突变的一种方法是在图像上应用网格，计算哪个网格正方形是目标图像中相应网格正方形的最差匹配，并确定哪些三角形与该网格正方形相交，然后标记它们以获得更大的突变机会。

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

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

  • 确定 64 个网格正方形中的哪一个是最差匹配，并标记相交（或附近/周围）三角形以获得更高的突变机会。
  • 确定 64 个网格正方形中的哪一个是最佳匹配，并仅在该正方形内使用另一个较小的 8x8 网格重复（即最佳网格正方形内的 8x8 网格）。这些可以被标记为添加新三角形的可能点，或者只是为了微调细节。
于 2010-10-03T01:36:41.303 回答
1

确实很有趣的问题！我分析此类问题的方法是使用进化策略优化算法。它不快，如果三角形数量很少，则适用。我没有很好地近似原始图像-但这部分是因为我的原始图像太复杂了-所以我没有尝试很多算法重新启动来查看EVO可能产生的其他次优结果......在任何案例 - 这作为抽象艺术生成方法还不错:-)

于 2010-10-03T16:02:36.410 回答
1

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

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}
于 2010-10-04T11:25:26.313 回答