间隔数组下采样算法

Question

我有一个由 N 个不同长度的间隔组成的排序数组。我正在用交替颜色 blue/green.

绘制这些间隔

我正在尝试找到一种方法或算法 "downsample" 间隔数组以生成视觉上相似的图，但元素较少。

理想情况下，我可以编写一些函数，在其中我可以将目标输出间隔数作为参数传递。输出长度只需要接近目标即可。

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

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

下面是我要完成的工作的图片。在这个例子中，输入有大约 250 个间隔，输出大约有 ~25 个间隔。输入长度可能相差很大。

Answer 1

我建议使用 K-means 它是一种用于对数据进行分组的算法（此处有更详细的解释：https://en.wikipedia.org/wiki/K-means_clustering and here https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html）这将是该功能的简要说明，希望对您有所帮助。

from sklearn.cluster import KMeans
import numpy as np

def downsample(input, cluster = 25):

    # you will need to group your labels in a nmpy array as shown bellow
    # for the sake of example I will take just a random array
    X = np.array([[1, 2], [1, 4], [1, 0],[4, 2], [4, 4], [4, 0]])

    # n_clusters will be the same as desired output
    kmeans = KMeans(n_clusters= cluster, random_state=0).fit(X)

    # then you can iterate through labels that was assigned to every entr of your input
    # in our case the interval
    kmeans_list = [None]*cluster
    for i in range(0, X.shape[0]):
        kmeans_list[kmeans.labels_[i]].append(X[i])

    # after that you will basicly have a list of lists and every inner list will contain all points that corespond to a
    # specific label

    ret = [] #return list
    for label_list in kmeans_list:
        left = 10001000 # a big enough number to exced anything that you will get as an input
        right = -left   # same here
        for entry in label_list:
            left = min(left, entry[0])
            right = max(right, entry[1])
        ret.append([left,right])

    return ret

Answer 2

您可以执行以下操作：

写出将整个条带划分为区间的点作为数组[a[0], a[1], a[2], ..., a[n-1]]。在您的示例中，数组为 [0, 5, 6, 10, ... ].
计算双倍区间长度 a[2]-a[0], a[3]-a[1], a[4]-a[2], ..., a[n-1]-a[n-3] 并找到其中最小的。让它成为 a[k+2]-a[k]。如果有两个或多个相等长度的值最小，则随机选择其中一个。在您的示例中，您应该获取数组 [6, 5, ... ] 并通过它搜索最小值。
交换间隔 (a[k], a[k+1]) 和 (a[k+1], a[k+2])。基本上，您需要分配 a[k+1]=a[k]+a[k+2]-a[k+1] 以保持长度，然后从数组中删除点 a[k] 和 a[k+2] 因为两对相同颜色的间隔现在合并为两个较大的间隔。这样，经过这一步，蓝色和绿色区间的个数都减少了一个。
如果您对当前的间隔数满意，则结束该过程，否则转到步骤1。

您执行第 2 步是为了减少 "color shift"，因为在第 3 步中，左侧区间向右移动 a[k+2]-a[k+1]，右侧区间移动 a[k+1]-a[k]靠左。这些距离的总和，a[k+2]-a[k] 可以被认为是你在整个画面中引入的变化的度量。

这种方法的主要优点：

简单。
这两种颜色中的任何一种都没有偏好。您不需要将其中一种颜色指定为背景，另一种颜色指定为绘画颜色。图片可以认为是"green-on-blue"和"blue-on-green"。这反映了相当常见的用例，当两种颜色仅描述某些在时间上或 space.

0/1

它始终保持颜色之间的平衡，即在缩小过程中每种颜色的间隔之和保持不变。因此图片的总亮度不会改变。这很重要，因为在某些情况下可以将此总亮度视为 "indicator of completeness"。

Answer 3

我建议您使用 Haar wavelet。这是一个非常简单的算法，经常被用来提供网站大图渐进式加载的功能。

Here 你可以看到它是如何与 2D 函数一起工作的。这就是你可以使用的。 las，该文档是乌克兰语，但代码是 C++，可读性太强了:)

This document提供了一个3D对象的例子：

有关如何使用 Haar 小波进行压缩的伪代码，您可以在 Wavelets for Computer Graphics: A Primer Part 1y.

中找到

Answer 4

更新 1：

下面是我最初删除的 post，因为显示方程式时存在问题，而且我也不太确定它是否真的有意义。但是后来，我发现我描述的优化问题实际上可以用DP（动态规划）有效地解决。

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

这里有一个 live demo，您可以在浏览器中使用它（确保浏览器支持 WebGL2，例如 Chrome 或 Firefox）。加载页面需要一些时间。

这是 C++ 实现：link

更新 2：

原来提出的解决方案具有以下优点属性 - 我们可以轻松控制两部分的重要性 F₁和成本函数的F₂。只需将成本函数更改为 F(α)=F₁ + αF ₂，其中 α >= 1.0 是一个自由参数。 DP算法保持不变

下面是使用相同间隔数 N:

的不同 α 值的一些结果

Live demo ^{（需要 WebGL2）}

可以看出，更高的α意味着覆盖原始输入区间更重要，即使这意味着覆盖中间的更多背景。

原始post

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

首先，不失一般性，让我们声明 blue 颜色为背景色。我们将在其上绘制 N green 间隔（N 是提供给 downsample() OP 描述中的函数）。 i^th 区间由其起始坐标 0 <= x_i 定义 < x_max 和宽度 w_i >= 0 (x_max是输入的最大坐标）。

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

我们现在可以介绍优化问题的成本函数的第一部分：

F₁越小，我们生成的区间覆盖input 间隔，所以我们将搜索 x_i, w_i 最小化它。理想情况下，我们希望 F₁=0 这意味着间隔不覆盖背景的 any （这当然是不可能的，因为 N 小于输入间隔）。

然而，这个函数不足以描述问题，因为显然我们可以通过取空区间来最小化它：F₁(x, 0) =0。相反，我们希望从输入间隔中尽可能多地覆盖。下面介绍对应这个需求的cost function的第二部分：

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

最后，我们可以陈述我们的优化问题：找到x_i, w_i 最小化 F=F₁ + F₂

如何解决这个问题？不确定。也许使用一些元启发式方法进行全局优化，例如模拟退火或微分进化。这些通常很容易实现，尤其是对于这个简单的成本函数。

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

Answer 5

这是动态规划的另一种尝试，与 Georgi Gerganov 的略有不同，尽管尝试和制定动态规划的想法可能受到他的回答的启发。实现和概念都不能保证是正确的，但我确实包含了一个带有可视化示例的代码草图:)

本例中的搜索 space 不依赖于总单元宽度，而是依赖于间隔数。它是 O(N * n^2) 时间和 O(N * n) space，其中 N 和 n 分别是目标和给定的（绿色）间隔数，因为我们假设任何新选择的绿色区间必须由两个绿色区间约束（而不是任意延伸到背景中）。

这个想法还利用了用于计算具有多数元素的游程的前缀和想法。当我们看到目标元素（在本例中为绿色）时我们加 1，其他元素减 1（该算法也适用于具有并行前缀和跟踪的多个元素）。（我不确定将候选区间限制在目标颜色占多数的部分是否总是有保证的，但它可能是一种有用的启发式方法，具体取决于所需的结果。它也是可调整的——我们可以轻松地调整它以检查不同的比 1/2 的部分。)

Georgi Gerganov 的程序寻求最小化，而这个动态程序寻求最大化两个比率。让 h(i, k) 代表绿色间隔的最佳序列，直到第 i 个给定间隔，利用 k 间隔，其中每个间隔都可以延伸回前一个绿色间隔的左边缘。我们推测

h(i, k) = max(r + C*r1 + h(i-l, k-1))

其中，在当前候选区间中，r是绿色与伸展长度的比例，r1是绿色与给定总绿色的比例。 r1 乘以一个可调整的常数，以赋予覆盖的果岭体积更大的权重。 l 是拉伸的长度。

JavaScript 代码（用于调试，它包括一些额外的变量和日志行）：

function rnd(n, d=2){
  let m = Math.pow(10,d)
  return Math.round(m*n) / m;
}

function f(A, N, C){
  let ps = [[0,0]];
  let psBG = [0];
  let totalG = 0;
  A.unshift([0,0]);

  for (let i=1; i<A.length; i++){
    let [l,r,c] = A[i];
    
    if (c == 'g'){
      totalG += r - l;
      let prevI = ps[ps.length-1][1];
      let d = l - A[prevI][1];
      let prevS = ps[ps.length-1][0];
      ps.push(
        [prevS - d, i, 'l'],
        [prevS - d + r - l, i, 'r']
      );
      psBG[i] = psBG[i-1];

    } else {
      psBG[i] = psBG[i-1] + r - l;
    }
  }
  //console.log(JSON.stringify(A));
  //console.log('');
  //console.log(JSON.stringify(ps));
  //console.log('');
  //console.log(JSON.stringify(psBG));

  let m = new Array(N + 1);
  m[0] = new Array((ps.length >> 1) + 1);
  for (let i=0; i<m[0].length; i++)
    m[0][i] = [0,0];

  // for each in N
  for (let i=1; i<=N; i++){
    m[i] = new Array((ps.length >> 1) + 1);
    for (let ii=0; ii<m[0].length; ii++)
      m[i][ii] = [0,0];

    // for each interval
    for (let j=i; j<m[0].length; j++){
      m[i][j] = m[i][j-1];

      for (let k=j; k>i-1; k--){
        // our anchors are the right
        // side of each interval, k's are the left
        let jj = 2*j;
        let kk = 2*k - 1;

        // positive means green
        // is a majority
        if (ps[jj][0] - ps[kk][0] > 0){
          let bg = psBG[ps[jj][1]] - psBG[ps[kk][1]];
          let s = A[ps[jj][1]][1] - A[ps[kk][1]][0] - bg;
          let r = s / (bg + s);
          let r1 = C * s / totalG;
          let candidate = r + r1 + m[i-1][j-1][0];
          
          if (candidate > m[i][j][0]){
            m[i][j] = [
              candidate,
              ps[kk][1] + ',' + ps[jj][1],
              bg, s, r, r1,k,m[i-1][j-1][0]
            ];
          }
        }
      }
    }
  }
  /*
  for (row of m)
    console.log(JSON.stringify(
      row.map(l => l.map(x => typeof x != 'number' ? x : rnd(x)))));
  */
  let result = new Array(N);
  let j = m[0].length - 1;
  for (let i=N; i>0; i--){
    let [_,idxs,w,x,y,z,k] = m[i][j];
    let [l,r] = idxs.split(',');
    result[i-1] = [A[l][0], A[r][1], 'g'];
    j = k - 1;
  }

  return result;
}

function show(A, last){
  if (last[1] != A[A.length-1])
    A.push(last);

  let s = '';
  let j;

  for (let i=A.length-1; i>=0; i--){
    let [l, r, c] = A[i];
    let cc = c == 'g' ? 'X' : '.';
    for (let j=r-1; j>=l; j--)
      s = cc + s;
    if (i > 0)
      for (let j=l-1; j>=A[i-1][1]; j--)
        s = '.' + s
  }

  for (let j=A[0][0]-1; j>=0; j--)
    s = '.' + s

  console.log(s);
  return s;
}

function g(A, N, C){
  const ts = f(A, N, C);
  //console.log(JSON.stringify(ts));
  show(A, A[A.length-1]);
  show(ts, A[A.length-1]);
}


var a = [
  [0,5,'b'],
  [5,9,'g'],
  [9,10,'b'],
  [10,15,'g'],
  [15,40,'b'],
  [40,41,'g'],
  [41,43,'b'],
  [43,44,'g'],
  [44,45,'b'],
  [45,46,'g'],
  [46,55,'b'],
  [55,65,'g'],
  [65,100,'b']
];

// (input, N, C)
g(a, 2, 2);
console.log('');
g(a, 3, 2);
console.log('');
g(a, 4, 2);
console.log('');
g(a, 4, 5);

间隔数组下采样算法

Algorithm for downsampling array of intervals

algorithm

downsampling

intervals

更新 1：

更新 2：

原始post