2次元配列の空白を埋めてください

Question

私は次のような配列がまばらにあります。直線的に意味をなさない値ですべての空白を埋めるアルゴリズムはありますか？すなわち、周囲の元の値から推測される。

私は双線形補間と双三次補間を見てきましたが、他にもありますか？例えば

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 
--------------------------------------------------------------------------------- 
1 | 
2 | 
3 |    55 
4 |    50          12   6 
5 |    45            19 
6 |    xxx 
7 |    35  45  50  yyy 
8 | 
9 | 
10 | 
11 | 
12 |      zzz 
13 | 
14 | 
15 | 

、私は、xxxは40の近傍にあることを期待し、50 ZZZの近傍にあるとYYYは、しかし、よりランダムな値を有するかもしれません。ただし、xxx、yyy、zzzだけでなく、すべての空白スペースを設定したいと思います。そして、まばらに配置された配列のためにそうすることができます。

このようなアルゴリズムはありますか？

Answer 1

このようなアルゴリズムが100万個存在します。だから、最初にすべてのあなたは、このように知られている値のいくつかの辞書を持っている：

known_values = { 
    (2, 3): 55.0, 
    (2, 4): 50.0, 
    (2, 5): 45.0, 
    (2, 7): 35.0, 
    (3, 7): 45.0, 
    (4, 7): 50.0, 
    (6, 4): 12.0, 
    (7, 4): 6.0, 
    (7, 5): 19.0, 
} 

最も簡単な方法は、任意の時点での値は人口の点の全ての加重平均であると言うことです。 1 /距離2乗で重み付けします。

def interpolate(known_values, p): 
    total_weight = 0.0 
    total_sum = 0.0 
    for q, value in known_values: 
     if p == q: 
      return value 
     d_square = (p[0] - q[0])**2 + (p[1] - q[1])**2 
     total_weight = total_weight + 1.0/d_square 
     total_sum = total_sum + value/d_square 
    return total_sum/total_weight 

このソリューションは限り行列は任意のデータで埋めているように動作します。だからあなたのような場合には、次のようなコードを持っていると思います。

しかし、どのように質問したかで判断すると、小さな領域でほぼ直線的な滑らかな補間が必要な場合があります。その1つの方法は、a*x + b*y + c関数が誤差の2乗の和を最小にするように(a, b, c)を探します。重みは、あなたの希望する点から既知の点までの距離の4乗です。 （最初の2つの力は、面積の四角形を元に戻し、他の2つの重点は近くの点をもっと元に戻します。）

エラーの最小二乗を使用する理由は、数学が簡単に機能することです。 a、b、またはcの小さな変化が値を大きく変更しない場合、つまり偏微分が0であることを正確に最小限に抑えることができます。したがって、3つの偏微分によって3組の線形方程式が得られます。 3つの変数で3つの方程式を解くことはかなり簡単です。

しかし、派生は長く、乱雑です。試してみたいのであれば、通常の最小二乗導出を見て、詳細を調べてみるべきです。次にそれを実装しようとします。しかし、あなたがの場合は、実際にはのデータがある場所から離れたところに線形投影を試みようとしたいと考えてみてください。

Answer 2

この問題は「二変数補間」問題とみなされ、この領域には数多くの研究があります。 Wikiで "多変量補間"を検索し、 "2次元"セクションでアルゴリズムを探すことができます。

バイリニア/バイキュービック補間では、データがグリッドを形成する必要がありますが、これはデータには当てはまりません。 Delaunayの三角測量法は、必要に応じて外挿には適していません。逆重み付き距離法は実装が容易で外挿に適していますが、結果はしばしば満足のいくものではありません。あなたがあまりにも多くのデータポイント（千など）を持っていない限り、ラジアル基底関数を使用することを個人的にお勧めします。