全体像をソートすることにより、この問題を「正面から」解決しようとするかもしれません。 ただし、このような操作には時間がかかりすぎる場合があります。 他のいくつかのアルゴリズムが頼みます。
そのため、同じ写真を少し実験して、車が直線で動いていたと思います。 私は25×25ピクセルのサイズの領域を取り、車の想定された経路に沿ってそれをシフトし、ピクセルの明るさの合計偏差を計算します。ここにプログラムコードがあります：
private void tsmiFindShift_Click(object sender, EventArgs e) { ImageMatrix matrix1 = create_matrix("D:\\3\\1.png"); ImageMatrix matrix2 = create_matrix("D:\\3\\2.png"); Bitmap picture = new Bitmap(matrix1.picture); using (var wrapper = new ImageWrapper(picture, true)) { int x1 = 110; int x2 = x1+25; int y1 = 140; int y2 = y1+25; int dx = 0; int dy = 0; StringBuilder sb = new StringBuilder(); for (dx = -100; dx < 200; dx++) { Int64 res = 0; for (int i = x1; i < x2; i++) { for (int j = y1; j < y2; j++) { int light1 = matrix1.matrix[i, j]; int light2 = matrix2.matrix[i + dx, j + dy]; int light = Math.Abs(light2 - light1); res = res + light; } } sb.AppendFormat("{0}; {1};\n", res, dx); } System.IO.File.WriteAllText("D:\\3\\1.txt", sb.ToString()); pbImage.Image = picture; }
受信したチャートを確認します。
何が得られますか？ ある時点で、この偏差の合計は最小ですが、ゼロではありません。 なぜゼロではないのですか？ おそらく、車の方向は完全に直線ではなく、さまざまなノイズ（雨滴、手ふれなど）である可能性もあります。 それでも、この仮説をテストするために、写真の広い領域の座標を整理することにより、「額」検索の実験を行いました。 目的関数の最小値がy軸に沿って正確にゼロ変位、つまり水平方向にのみ移動することが判明したため、私の仮定が真実であり、車が実際に直線で移動したことが判明しました。 すべてのノイズを除去するために残っています。 ただし、見つかったポイントでフレームを減算するためのマスクを表示しても害はありません。
減算領域では、ヘッドライトのエッジが見えますが、明らかに何らかのグレアがあります。
問題が発生します：勾配に沿った降下のようなものを使用したり、目的関数の最小値を検索してオブジェクトの新しい位置を検索することは可能ですか？ グラフをよく見ると、関数には多くの局所的な極値があることがわかります。アルゴリズムが局所的な極値とメインの極値を混同しないようにする方法はまだ明確ではありません。
ここにアイデアがあります：バイナリ検索を使用する場合 最初にx軸に沿って関数を取り、次にyに沿って関数を取り、関数が最小になる象限を見つけ、それを同じ象限の4つに分割して、目的の点を見つけます。 これは、検索エリア内のすべてのポイントを移動するよりもはるかに高速です。
実験のために、異なる画像が選択されました。水平と斜めの両方に同時に移動する楕円：
x軸に沿って目的関数をプロットします。
dx = 24での極値関数
そして、y軸に沿って：
-34で極端。
見ての通り。 dy軸では極値が正しく見つかりましたが、xでは、オブジェクトが完全に異なる象限にシフトしていることがわかりました。極値はdx> 0の領域にありますが、実際にはバイアスはxの減少方向にあります。 したがって、他のアルゴリズムが必要です。
極値点を通る垂直な直線を描いて、それに沿って極値を探すことができます。 そして、同じ線上の極値へのポイントを介して垂直線を描画します。 したがって、極値を探している直線があり、軸Oxに平行で、次にOyになります。 それで、Oxの極値を見つけ、dx = 24でOyに平行な軸を見ます。
dy = -1で極端です。 すでにOx軸に平行な点dx = 24、dy = -1を通る線を引きます。 この結果が得られます。
これで、点dx = 18にすでに極値があります。 もう少し真実に近い。 唯一の質問は、この方法で極値が見つかるかどうか、および「ダム検索」よりもどれだけ効果的かということです。
だから、最初の愚かなバスト。 アルゴリズムは、15556回の反復に対して、点dx = -12、dy = -23で極値を見つけました。
この例では40401の反復が考えられますが、ラップトップの実行時間は約0.7秒です。 ストリーミングビデオ処理の場合、この速度はもちろん許容できません。
それでは、緩やかな近似で上記のアイデアを実装してみましょう。
private ResStruct search(ImageMatrix matrix1, ImageMatrix matrix2, int x1, int y1, int x2, int y2, StringBuilder sb, int x_beg, int y_beg, int x_end, int y_end) { Int64 min_res = 999999999999999999; ResStruct result = new ResStruct(); int min_dx = 999999999; int min_dy = 999999999; for (int dy = y_beg; dy <= y_end; dy++) { for (int dx = x_beg; dx <= x_end; dx++) { Int64 res = 0; for (int i = x1; i < x2; i++) { for (int j = y1; j < y2; j++) { int light1 = matrix1.matrix[i, j]; int light2 = matrix2.matrix[i + dx, j + dy]; int light = Math.Abs(light2 - light1); res = res + light; } } if (res < min_res) { min_res = res; min_dx=dx; min_dy=dy; } //sb.AppendFormat("{0}; {1}; {2}; {3};\n", dx, dy, res, min_res); } } result.dx = min_dx; result.dy = min_dy; result.res = min_res; return result; } private void tsmiFastFindShift_Click(object sender, EventArgs e) { ImageMatrix matrix1 = create_matrix("D:\\3\\11.png"); ImageMatrix matrix2 = create_matrix("D:\\3\\12.png"); Bitmap picture = new Bitmap(matrix1.picture); using (var wrapper = new ImageWrapper(picture, true)) { int x1 = 140; int x2 = x1 + 25; int y1 = 110; int y2 = y1 + 25; Random rnd=new Random(); StringBuilder sb = new StringBuilder(); DateTime dt1 = DateTime.Now; Int64 min_res = 999999999999999999; int min_dx = 0; int min_dy = 0; int k=0; bool flag = false; do { ResStruct res; if (flag) { res = search(matrix1, matrix2, x1, y1, x2, y2, sb, min_dx, -100, min_dx, 100); } else { res = search(matrix1, matrix2, x1, y1, x2, y2, sb, -100, min_dy, 100, min_dy); } flag = !flag; if (res.res < min_res) { min_res = res.res; min_dx = res.dx; min_dy = res.dy; } else { // ( ) // if (flag) min_dy = min_dy + rnd.Next(10) - 5; else min_dx=min_dx + rnd.Next(10) - 5; } sb.AppendFormat("{0}; {1}; {2}; {3}; {4}\n", res.dx, res.dy, res.res, min_res, k); k++; } while (k < 1000 && min_res>=1); DateTime dt2 = DateTime.Now; MessageBox.Show(dt1.ToString() + " " + dt2.ToString()); System.IO.File.WriteAllText("D:\\3\\1.txt", sb.ToString()); for (int i = x1; i < x2; i++) { for (int j = y1; j < y2; j++) { int light1 = matrix1.matrix[i, j]; int light2 = matrix2.matrix[i + min_dx, j + min_dy]; int light = Math.Abs(light2 - light1); wrapper[i, j] = Color.FromArgb(light, light, light); } } pbImage.Image = picture; } }
このアルゴリズムは、12,600回の反復（63〜200）のオフセットを見つけました。
これはやや高速です。 確かに、アルゴリズム自体は最適ではなく、さらに最適化できます。 その他の欠点：間違った開始点を選択すると、フリーズし、何も見つかりません。 たとえば、-100を最初に-100を選択しましたが、検索は機能しませんでした。
このトピックに興味がある場合は、このアルゴリズムをさらに改善して欠点をなくす方法、および描画された画像ではなく実際に操作する方法について説明します。