用于下采样间隔阵列的算法

Question

我有一个不同长度的N个区间的排序数组.我正在用蓝色/绿色交替颜色绘制这些间隔.

我试图找到一种方法或算法来"下采样"间隔数组,以产生视觉上相似的图,但元素较少.

理想情况下,我可以编写一些函数,我可以将目标输出间隔数作为参数传递.输出长度只需接近目标.

input = [
  [0, 5, "blue"],
  [5, 6, "green"],
  [6, 10, "blue"],
  // ...etc
]

output = downsample(input, 25)
// [[0, 10, "blue"], ... ]

下面是我想要完成的图片.在这个例子中,输入有大约250个间隔,输出大约有25个间隔.输入长度可能会有很大差异.

Answer 1

更新1:

下面是我最初删除的原始帖子,因为显示方程式存在问题,而且如果它真的有意义我也不太自信.但后来,我认为我所描述的优化问题实际上可以通过DP(动态编程)有效地解决.

所以我做了一个示例C++实现.以下是一些结果:

GIF

这是一个可以在浏览器中播放的现场演示(确保浏览器支持WebGL2,如Chrome或Firefox).加载页面需要一些时间.

这是C++实现:链接

事实证明,所提出的解决方案具有以下不错的特性 - 我们可以轻松地控制成本函数的两个部分F ₁和F ₂的重要性.简单地改变成本函数F(α) = ˚F ₁ + αF ₂,其中α > = 1.0是一个自由参数.DP算法保持不变.

以下是使用相同数量的间隔N的不同α值的一些结果:

现场演示 ^{(需要WebGL2)}

可以看出,更高的α意味着覆盖原始输入间隔更为重要,即使这意味着覆盖其间的更多背景.

尽管已经提出了一些好的算法,但我想提出一种稍微不同寻常的方法 - 将任务解释为优化问题.虽然,我不知道如何有效地解决优化问题(或者即使它可以在合理的时间内解决),但它可能对纯粹作为一个概念的人有用.

首先,不要失去一般性,让我们将蓝色声明为背景.我们将在其上面绘制N个绿色区间(N是downsample()在OP的描述中提供给该函数的数字).第i ^个间隔由其起始坐标0 <= x _i <x _max和宽度w _i > = 0定义(x _max是来自输入的最大坐标).

还可以将数组G(x)定义为输入数据中区间[0,x)中的绿色单元格数.该阵列可以很容易地预先计算.我们将用它来快速计算任意区间[x,y]中的绿色单元数 - 即:G(y) - G(x).

我们现在可以为优化问题引入成本函数的第一部分:

F ₁越小,我们生成的间隔越好地覆盖输入间隔,因此我们将搜索最小化它的x _i,w _i.理想情况下,我们希望F ₁ = 0,这意味着间隔不会覆盖任何背景(当然这是不可能的,因为N小于输入间隔).

但是,这个函数不足以描述问题,因为很明显我们可以通过获取空间隔来最小化它:F ₁(x,0) = 0.相反,我们希望尽可能多地覆盖输入间隔.让我们介绍与此要求相对应的成本函数的第二部分:

F ₂越小,覆盖的输入间隔越多.理想情况下,我们希望F ₂ = 0,这意味着我们覆盖了所有输入矩形.然而,最小化F ₂与最小化F ₁竞争.

最后,我们可以说明我们的优化问题:找到最小化F = F ₁ + F _2的 x _i,w _i

如何解决这个问题呢？不确定.也许使用一些元启发式方法进行全局优化,例如模拟退火或差分进化.这些通常易于实现,特别是对于这种简单的成本函数.

最好的情况是存在某种DP算法来有效地解决它,但不太可能.