D(0,j),D(i,0)など領域外の累積誤差をある最大値に初期設定し選択しないようにする。D(1,1)= d(1,1)から開始し、隣接のDが できてからD(i,j)を作成するよう全矩形領域を走査する。その間、i,jは、単調非減少である。
D(i,j)= d(i,j) + Min(D(i-1,j),D(i,j-1),D(i-1,j-1)) .....(1)
(i,j)の範囲は全ての1＜＝i＜＝I, 1＜＝j＜＝Jでなくてもよく、任意に制限できる。その範囲のD(i,j)を作った後に、D(I,J)から 方向指示v(i,j)を逆たどりすると対応線を知ることができる。DPには、開始点と終了点を(1,1)と(I,J) 以外の複数点にする手法、 対角線に幅をもつ帯、対角線の中央を広げた菱形にするなど調べる領域を制限する手法がある。 また、傾斜制限という手法もある。例えば、傾きを 1/2〜2に制限する対称型(2)、常にx方向に1増加し、y方向に0〜2増加する非対称(3)がある。
D(i,j)= d(i,j) + Min(D(i-2,j-1),D(i-1,j-2),D(i-1,j-1)) ....(2)
D(i,j)= d(i,j) + Min(D(i-1,j),D(i-1,j-1),D(i-1,j-2)) ....(3)
なぜなら、(1)は同じiにjは(逆に同じjにiも)、どこまでも大きく増加でき(増加中のd(i,j)は累積されるが)、それはある程度、 連続性を捨てることになるからである。
D(i,j,k)= d(i,j,k) + Min( D(i-1,j,k), D(i,j-1,k), D(i,j,k-1), D(i-1,j-1,k), D(i-1,j,k-1), D(i,j-1,k-1), D(i-1,j-1,k-1)) ...(4)
逆たどりのための最小方向指示ベクトルも 000以外の 100,010,001,110,101,011,111の7種になり、3bitで貯蔵できる。 これが正しいかというと、誤りであり、誤りは、逆たどりが示すものは、線であり、面でないことである。 求めたいのは、面と面との成す立体のなかの、対応する面であり、対応する線でない。 7隣接から選択するべきは、１つのノードでなく、x,y方向のそれぞれに一つの対応する2つのノードの作成する微小面である。それゆえ、 逆たどりのためのベクトルは、2つの2bitになる。
D(i,j,k)= d(i,j,k)
+ Min(D(i-1,j,k), D(i,j-1,k), D(i-1,j-1,k))
+ Min(D(i-1,j,k-1), D(i,j-1,k-1), D(i-1,j-1,k-1)) ....(5)
+ Min(D(i,j,k-1),
最後の(i,j,k-1)からの連結は、x,y方向には移動せずz方向にだけ移動するもので、上の行に含め4最小にしても、下の行に含め4最小にしてもよい。 又は、省略してもよいかもしれない。
もうひとつの誤りは、x,y方向の連結を最小値でそれぞれ調べるのはよいが、両者の最小値を和するのは間違いである。 逆たどりのための連結は2本あるが、累積誤差は、どれかひとつに和するべき。そうしないと累積よりも大きくなる。 (4)のように最小値判定で方向を示し、そこにx,yの2方向の連結指示がある。7種の方向は、x,yそれぞれの連結指示をもつ。 連結情報は、逆たどりに使用するには、1つだけあればよく、2つの連結情報は、残す意味がない。
2次元の画像2枚(i,j),(k,l)の間の対応は、4次元の対応点が必要である。最小判別は i,j,k,lの各に0/1前の隣接15種から選ぶ。逆たどりは4bitが残されればよい。
D(i,j,k,l)= d(i,j,k,l) + Min( D(i-1,j,k,l), D(i,j-1,k,l), D(i,j,k-1,l), D(i-1,j-1,k,l), D(i-1,j,k-1,l), D(i,j-1,k-1,l), D(i-1,j-1,k-1,l), D(i,j,k,l-1), D(i-1,j,k,l-1), D(i,j-1,k,l-1), D(i,j,k-1,l-1), D(i-1,j-1,k,l-1), D(i-1,j,k-1,l-1), D(i,j-1,k-1,l-1), D(i-1,j-1,k-1,l-1) ) ...(6)
2次元DPマッチングは、フレーム間動き補償予測を使う動画像符号化において、動きベクトル抽出という符号化側の技術である。 画素毎の2次元マッチングは、ブロック毎の動きベクトル抽出とは違う処理であり、それにそのまま使用できない。 画素毎のマッチング誤差を変換符号化する場合にもマッチング情報は動き情報として別に伝送する必要があり、その表現法も変わるが、 この手法がブロックの角のグリッド交差点の動き情報として伝送し、ブロック内はそれを線形内挿して、画素毎に使用する動き補償という方法(MPEG-4の 途中に出たP6)もある。フレーム間の動きは、元々ブロック毎ではなく平行移動だけではない画像間のアフィン変換された動きがある。そのため、 一般に、動き補償予測精度はブロック単位よりも画素への細分によって向上するが、伝送動き情報量との兼ね合いで、動き情報をブロック毎に伝送し、 ブロック内部で画素毎に使用することが望ましい。そのような動き補償技術の基礎に画素単位の2次元DPマッチングがある。
また、奥行き検出の立体視、左右のカメラ画像の水平ズレ検出は、左右の水平走査線同士のDPマッチングではカメラの厳密な水平設置を要し、実現が難しい だけでなく、画像特性である上下の連続性を捨て、結果にも上下の繋がりがなくなり平滑化が必要になる。そのため立体視にも2次元DPマッチングが望ましい。