(57)【要約】【課題】２つの要素列が類似するようにそれぞれの要素を対応付ける弾性マッピングにおいて、２つの要素列の性質のみに基づく対応付けを行うことで、任意の個数の要素を対応付けからスキップし、任意の対応を始端終端とする対応付け結果を得る。【解決手段】長さI、Jの２つの要素列間の対応付けを行う際、それぞれの要素の集合の直積集合である格子空間上で有向無閉路グラフを構成し、動的計画法を用いた該グラフでの最短経路の探索により対応付けを求める手順において、第１の特徴としてI2J2に比例した数の有向辺から成る有向無閉路グラフを構成し、第２の特徴として、要素間のコストである格子点のコストを、要素間を対応付けるべき際に設定する負の値のコストを持つ格子点と、そうで無い場合に設定する非負のコストを持つ格子点と、を混在させるように設定する。【選択図】図６
2016177327.tif 000002
【特許請求の範囲】
【請求項１】
第１の要素列と第２の要素列とを比較して、第１の要素列の要素と第２の要素列の要素との組を1つ以上含む対応付けを得る際に、
第１の要素列の要素による集合と第２の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第１のステップと、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第１の要素列の要素と第２の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第２のステップと、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで２つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第３のステップと、
求めた最小コスト経路に含まれる格子点の第１の要素列の要素と第２の要素列の要素との組の集合を第１の要素列と第２の要素列との対応付けの結果とする第４のステップと、
を有する、要素列間対応付け方法において、
前記第１のステップでは、
前記有向無閉路グラフにより定義される半順序での、有向辺の始点側を上位、終点側を下位とした順序関係にて、
すべての該順序関係にある上位の格子点と下位の格子点について、該上位の格子点から該下位の格子点への有向辺を設けるように、前記有向無閉路グラフを構成することと、
前記第２のステップでは、
前記要素列の対応付けの目的において、前記格子点を構成する第１の要素列の要素と第２の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値０のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする、要素列間対応付け方法。
【請求項２】
第１の要素列と第２の要素列とを比較して、第１の要素列の要素と第２の要素列の要素との組を1つ以上含む対応付けを得る際に、
第１の要素列の要素による集合と第２の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第１のステップと、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第１の要素列の要素と第２の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第２のステップと、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで２つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第３のステップと、
求めた最小コスト経路に含まれる格子点の第１の要素列の要素と第２の要素列の要素との組の集合を第１の要素列と第２の要素列との対応付けの結果とする第４のステップと、
を有する、要素列間対応付け方法において、
前記第１のステップでは、
前記第１の要素列の要素数をIとし、前記第２の要素列の要素数をＪとし、前記Iと前記Jとの２つの値に応じて、I2J2に比例する数の有向辺を設けて、前記有向無閉路グラフを構成することと、
前記第２のステップでは、
前記要素列の対応付けの目的において、前記格子点を構成する第１の要素列の要素と第２の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値０のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする、要素列間対応付け方法。
【請求項３】
前記最小コスト経路を求める第３のステップでは、
前記有向無閉路グラフにより定義される半順序によりトポロジカルソートした順序で前記格子点ごとに該格子点に至る経路の最小経路コストを順次計算する際に、
最小経路コストを求める対象である第１の格子点を終点とする有向辺の始点となる第２の格子点のすべてについて、
該第２の格子点の計算済みの最小経路コストに負または０の値を持つものがある場合には、その負または０の値の中での最小値に第１の格子点のコストを足した値を、第１の格子点へ至る経路の最小経路コストとし、さらに、該最小値の最小経路コストを有する第２の格子点を第１の格子点の親の格子点として記憶し、
該第２の格子点の計算済みの最小経路コストが例外なく正の値である場合には、第１の格子点のコストを第１の格子点の最小経路コストとするとともに、第１の格子点を始端候補として記憶し、
すべての前記格子点にて最小経路コストを計算したのちに、その中で最小の値を持つ格子点を終端と定め、
該終端である格子点を始まりとして、格子点から上記親の格子点を繰り返し求めるバックトラック手順を行い、
該バックトラック手順にて前記始端候補と記憶された格子点が前記親の格子点となった際には該格子点を始端と定めて繰り返しを終了し、
得られた終端と始端とを両端としてバックトラック手順で現れた格子点を前記有向辺でつないだ経路を最小コスト経路とすることを特徴とする、
請求項１、または請求項２記載の要素列間対応付け方法。
【請求項４】
前記始端候補および前記終端の少なくとも１つについて、前記第３のステップにて決定する際に、あらかじめ定めた条件を満たす格子点のみを、前記始端候補および前記終端と決定する対象とすることを特徴とした、請求項３記載の要素列間対応付け方法。
【請求項５】
第１の要素列と第２の要素列とを比較して、第１の要素列の要素と第２の要素列の要素との組を1つ以上含む対応付けを得る際に、
第１の要素列の要素による集合と第２の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第１の手段と、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第１の要素列の要素と第２の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第２の手段と、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで２つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第３の手段と、
求めた最小コスト経路に含まれる格子点の第１の要素列の要素と第２の要素列の要素との組の集合を第１の要素列と第２の要素列との対応付けの結果とする第４の手段と、
を有する、要素列間対応付け装置において、
前記第１の手段では、
前記有向無閉路グラフにより定義される半順序での、有向辺の始点側を上位、終点側を下位とした順序関係にて、
すべての該順序関係にある上位の格子点と下位の格子点について、該上位の格子点から該下位の格子点への有向辺を設けるように、前記有向無閉路グラフを構成することと、
前記第２の手段では、
前記要素列の対応付けの目的において、前記格子点を構成する第１の要素列の要素と第２の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値０のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする、要素列間対応付け装置。
【請求項６】
第１の要素列と第２の要素列とを比較して、第１の要素列の要素と第２の要素列の要素との組を1つ以上含む対応付けを得る際に、
第１の要素列の要素による集合と第２の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第１の手段と、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第１の要素列の要素と第２の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第２の手段と、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで２つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第３の手段と、
求めた最小コスト経路に含まれる格子点の第１の要素列の要素と第２の要素列の要素との組の集合を第１の要素列と第２の要素列との対応付けの結果とする第４の手段と、
を有する、要素列間対応付け装置において、
前記第１の手段では、
前記第１の要素列の要素数をIとし、前記第２の要素列の要素数をＪとし、前記Iと前記Jとの２つの値に応じて、I2J2に比例する数の有向辺を設けて、前記有向無閉路グラフを構成することと、
前記第２の手段では、
前記要素列の対応付けの目的において、前記格子点を構成する第１の要素列の要素と第２の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値０のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする、要素列間対応付け装置。
【請求項７】
前記最小コスト経路を求める第３の手段では、
前記有向無閉路グラフにより定義される半順序によりトポロジカルソートした順序で前記格子点ごとに該格子点に至る経路の最小経路コストを順次計算する際に、
最小経路コストを求める対象である第１の格子点を終点とする有向辺の始点となる第２の格子点のすべてについて、
該第２の格子点の計算済みの最小経路コストに負または０の値を持つものがある場合には、その負または０の値の中での最小値に第１の格子点のコストを足した値を、第１の格子点へ至る経路の最小経路コストとし、さらに、該最小値の最小経路コストを有する第２の格子点を第１の格子点の親の格子点として記憶し、
該第２の格子点の計算済みの最小経路コストが例外なく正の値である場合には、第１の格子点のコストを第１の格子点の最小経路コストとするとともに、第１の格子点を始端候補として記憶し、
すべての前記格子点にて最小経路コストを計算したのちに、その中で最小の値を持つ格子点を終端と定め、
該終端である格子点を始まりとして、格子点から上記親の格子点を繰り返し求めるバックトラック手順を行い、
該バックトラック手順にて前記始端候補と記憶された格子点が前記親の格子点となった際には該格子点を始端と定めて繰り返しを終了し、
得られた終端と始端とを両端としてバックトラック手順で現れた格子点を前記有向辺でつないだ経路を最小コスト経路とすることを特徴とする、
請求項５、または請求項６記載の要素列間対応付け装置。
【請求項８】
前記始端候補および前記終端の少なくとも１つについて、前記第３の手段にて決定する際に、あらかじめ定めた条件を満たす格子点のみを、前記始端候補および前記終端と決定する対象とすることを特徴とした、請求項７記載の要素列間対応付け装置。
【請求項９】
請求項１乃至請求項４に記載の要素列間対応付け方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、順序を持つ要素の集合である要素列について、２つの要素列を比較して、一方の要素列の要素と他方の要素列の要素との対応を決定する、対応付け方法、対応付け装置ならびに対応付けプログラムに関する。
【背景技術】
【０００２】
第１の要素列と第２の要素列のそれぞれの要素を対応付ける技術は、音声などの時系列パターンの認識や、文字や指紋などの画像パターンの認識など、様々な分野での応用がある。ここでいう要素とは、２つの要素列のそれぞれの要素間で対応付けの指標となる数値を定義できるものであれば良い。例えばＮ次元空間上の点の列であれば、２つの点の間の距離を対応付けの指標と定義することが出来る。
【０００３】
要素列に歪みがあると対応付けは難しくなり、要素列を伸縮させてもっとも整合した対応付けを得る技術は、弾性マッチングと呼ばれる。弾性マッチングには動的計画法（Dynamic Programming）を利用したＤＰマッチングが広く用いられている。
【０００４】
例えば類似画像の検索においてもＤＰマッチングが用いられている。特許文献１に記載された類似画像検索においては、ブロックに分割した画像データごとに特徴量行列を生成し、特徴量行列を構成する各特徴列間の距離をＤＰマッチングにより求める過程を含んでいる。
【０００５】
あるいは、画像情報であるジェスチャの認識においてもＤＰマッチングが用いられている。特許文献２に記載されたジェスチャ認識装置においては、要素列として特徴パラメータ系列を取り、連続ＤＰマッチングと呼ぶ手法の中で特徴パラメータ間の距離計算の順序の逆行を許すことで、標準パターンとして用いられる要素列の情報量を減らす工夫を行っている。
【０００６】
非特許文献１中第２節に記された単調連続性制約を持つＤＰマッチングを例に、従来技術としてＤＰマッチングの原理を説明する。このＤＰマッチングでは、次の式（１）に示す２つの要素列、ＸとＹとを対応付けの対象とする。
【０００７】
【数１】
2016177327.tif 000003
【０００８】
非特許文献１に記されたＤＰマッチングでは、次の式（２）に示す、Xの第i番目の要素xiとYの第j番目の要素yjとの対応付けを最適化する。式（２）は、iの値がひとつずつ増えることを意味しており、これを連続性制約と呼ぶこととする。なお、この連続性制約はＤＰマッチング一般に課される制約ではない。
【０００９】
【数２】
2016177327.tif 000004
【００１０】
つぎに、要素間の対応付けのコストを、式（３）のように表す。なお、ＤＰマッチングにおいては、２つの要素列中のそれぞれの要素間の対応付けでの指標とする値を、コスト、距離、類似度などと呼ぶ。コストや距離と呼ぶ場合は、指標値の合計を最小化することを要素列の対応付けの目的とする定式化を行うのに対し、類似度と呼ぶ場合は指標値の合計を最大化するように定式化する場合もある（例えば非特許文献２）。適当な変換を行えば両者は同じ意味となり、本出願においてはコストの用語を用いることにする。
【００１１】
【数３】
2016177327.tif 000005
【００１２】
非特許文献１では、式（３）のようにコストをノルムの形式で記しており、局所距離とも呼んでいる。距離の一般化として捉えられるノルムは正定値性を備えており、すなわち非負である。
【００１３】
式（１）（２）（３）のように定めた際、最適化問題は次の式（４）のように定式化される。式（４）中に示すように、この例では単調性制約を課し、その他、傾斜制限、始端、終端に関する条件を課している。これらのうち、単調性制約については条件として課す場合が一般的であるが、そうでない場合も報告されている。傾斜制限については、図１を用いて後述するようにさまざまな種類がある。始端と終端とについても式（４）に示す条件を課す場合が一般的であるが、始端終端フリー化を図る方法も報告されている。
【００１４】
【数４】
2016177327.tif 000006
【００１５】
式（４）の最適解を求める際、ＤＰマッチングの手法では、コストの総和であり累積距離とも呼ばれる値（式（５）中ではgi(ui)）を、次の式（５）に示す漸化式により始端から順次求める。式（５）はＤＰ漸化式と呼ばれる。式（５）のＤＰ漸化式の始端以外の場合での最小値選択範囲は、式（４）中の単調性制約と傾斜制限とにより決められている。
【００１６】
【数４】
2016177327.tif 000007
【００１７】
ＤＰ漸化式中の最小値選択範囲は、さまざまな種類がある傾斜制限によって異なってくる。図１に、非特許文献１（２．２項）に示された傾斜制限、すなわち、最小値選択範囲の種類を示す。式（４）の場合、図１中１０１の破線で示した格子でのiとjとによる座標にて、黒丸で記した点のgi(ui)の値を決める際に比較を行うgi-1(ui-1)の値の点を白丸で示している。図１中１０４は、単調性制約の無い傾斜制限を表す。
【００１８】
ＤＰ漸化式を用いて求めたgi(ui)の終端での値gI(J)が、式（４）の目的関数Fの最小値となる。この最適解の際の対応付けu1,...,ui,...,uIは、式（５）のＤＰ漸化式で最小値をいずれのgi-1(ui-1)より選んだかを終端より逆に辿ることにより、すなわち、バックトラックにより得られる。
【００１９】
ＤＰマッチングの定式化においては、{1,...,i,...,I}と{1,...,j,...,J}との直積集合であるＤＰ平面上の格子点ではなく、格子点を結ぶ有向辺にコストを割り当てているものもある。これを含む異なる定式化は、格子点にコストが割り当てる定式化に置き換え可能である。本出願においては、格子点へのコストを割り当てる定式化を基本的に用いるが、より簡明な説明が行える場合には有向辺にコストを割り当てる例（図５）も用いる。
【００２０】
以上、非特許文献１での記述による例を基にして、ＤＰマッチングの原理を説明した。ＤＰマッチングは弾性マッチングにてＤＰ（Dynamic Programming、動的計画法）を利用した手法であり、上述の式（１）〜（５）によるＤＰマッチングの例は、図２に示すＤＰ平面上に構成された有向無閉路グラフ（DAG、Directed Acyclic Graph）での最小コスト経路を動的計画法にて求めたことに相当する。すなわち、図２は、要素列X中の要素の集合と要素列Y中の要素の集合との直積集合である格子空間上で、格子点間を式（２）および、式（４）中の単調性制約と傾斜制限とにより制限された有向辺で結んだ有向無閉路グラフを矢印で示したものである。上述の例でのＤＰマッチングは、２０１の始端から、２０２の終端へのコスト最小経路を動的計画法によって求め、その経路に含まれる格子点の集合を対応付け結果とするものである。
【００２１】
なお、以上の説明においては、対応付け手法であるＤＰマッチングと、ＤＰマッチングで用いられている動的計画法（ＤＰ）とを区別している。以下での説明においても、両者を区別して記す。
【００２２】
ＤＰマッチングで利用する動的計画法は、図２のように直積集合である格子空間上で有向無閉路グラフが構成されていれば適用できる。すなわち、有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を処理することにより最小コスト経路を求めることが、ＤＰマッチングの基本的な考え方である。式（１）〜（５）に示す定式化は例であり、ＤＰマッチングを適用するために必要な条件ではない。
【００２３】
逆に、対応付けの対象となる２つの要素列の順序に従って、最適化問題の制約条件として単調性制約を課せば、明らかに格子空間上で有向無閉路グラフが構成されるため、ＤＰマッチングが適用できる。
【００２４】
以上、非特許文献１での記述を基にして、ＤＰマッチングの原理を式（１）〜（５）による例で説明したが、コストの観点からは、式（３）とは異なる捉え方を行っているＤＰマッチングもある。例えば非特許文献２に見えるＤＮＡ塩基配列の比較方法、すなわち、塩基配列同士の対応付けへのＤＰマッチングの適用においては、類似度と呼ぶコスト相当の値に、ノルムのような非負の値ばかりでなく、正負の両方の値が用いられている。また、特許文献３は、ＤＮＡ塩基配列ではなく、これを組み合わせたアミノ酸配列へ翻訳を行った後に比較を行っているが、やはりコストにあたるスコアにおいて正負の両方の値を用いている。
【００２５】
なお、非特許文献２、および、特許文献３では、最適化問題において目的関数最大化の定式化を行っており、式（４）での最小化の定式化と比べると、コストに当たる指標の正負の意味付けは逆になっている。以下では、目的関数最小化の定式に基づく指標としてのコストにおける正負の意味付けを前提に説明を行う。
【００２６】
有向無閉路グラフに対して動的計画法を適用してコスト最小の経路を求める際、そのコストは非負である必要は無い。よって、負のコストにあたる指標が用いられている非特許文献２および特許文献３における対応付けにおいても、問題無くＤＰマッチングは動作する。なお、非特許文献２、および、特許文献３でのいずれのＤＰマッチングの例でも、単調性制約を課していることより、コスト最小の経路を求めるグラフは有向無閉路グラフとなっている。
【００２７】
また、非特許文献２では、図１中１０２に当たる傾斜制限を課している。特許文献３の傾斜制限は、塩基列の３つごとにアミノ酸列を考えることなどにより複雑化しているが、固定的な範囲を最小値選択範囲（請求項２では７つの格子点）としていることは変わりがない。ＤＰの計算量はO(IJ)であるが、これは最小値選択範囲が固定的であることに拠る。
【先行技術文献】
【特許文献】
【００２８】
【特許文献１】特開２００６−１４６７１５号公報
【００２９】
【特許文献２】特開平９−３３０４００号公報
【００３０】
【特許文献３】特開平１０−３３４１０４号公報
【非特許文献】
【００３１】
【非特許文献１】内田  誠一「ＤＰマッチング概説  〜基本と様々な拡張〜」、電子情報通信学会、技術報告、PRM2006-166、 2006年12月
【００３２】
【非特許文献２】中川  匠、吉原  郁夫、山森  一人、安永  守利「ゲノム解析に用いるＤＰマッチングの分割統治法による高速化」、宮崎大學工學部紀要、35、257-262、2006年8月
【発明の概要】
【発明が解決しようとする課題】
【００３３】
特許文献１〜３、非特許文献１〜２に記されたＤＰマッチングの手法を含む従来技術においては、いずれもＤＰ漸化式において固定的な最小値選択範囲を採っている。これは前述のとおりO(IJ)という小さい計算量であるＤＰマッチングの利点の裏付けとなっているが、傾斜制限により実現されている固定的な最小値選択範囲は、「類似するように２つの集合の要素を対応付ける」という弾性マッチングの原義とは直接関係がない。すなわち、固定的な最小値選択範囲は、対応付けを素早く計算するための手段であり、“類似させる”ことへは制限となっている。
【００３４】
また、特許文献３、および、非特許文献２に記された正負の値を持つコストは、コスト０を境にして“類似する”ことの定義と尺度を与えるものであると考えられる。すなわち、負の値であれば対応付けることが好ましく、正の値であれば対応付けないことが好ましいという基準を、弾性マッピングに与えるコストの設定の仕方と捉えることが出来る。しかしながら、上述のように固定的な最小値選択範囲と併用されているため、正負の値を持つコストの効果は対応付け結果に対して限定的である。
【００３５】
本発明は、「類似するように２つの集合の要素を対応付ける」という弾性マッチングの原義に沿った対応付けを得ることを目的とする。すなわち、類似するように対応させることへの障害となっていた制限を無くした柔軟な対応付け、類似することの基準を明確に設定できる対応付けを実現することが目的である。制限を無くすには、制限を無くしたことにより意図しない対応付けが最適解となることを防ぐことが必要となる。
【課題を解決するための手段】
【００３６】
本発明に係る２つの要素列の対応付け方法の第１の構成は、
第１の要素列と第２の要素列とを比較して、第１の要素列の要素と第２の要素列の要素との組を1つ以上含む対応付けを得る際に、
第１の要素列の要素による集合と第２の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第１のステップと、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第１の要素列の要素と第２の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第２のステップと、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで２つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第３のステップと、
求めた最小コスト経路に含まれる格子点の第１の要素列の要素と第２の要素列の要素との組の集合を第１の要素列と第２の要素列との対応付けの結果とする第４のステップと、
を有する、要素列間対応付け方法において、
前記第１のステップでは、
前記有向無閉路グラフにより定義される半順序での、有向辺の始点側を上位、終点側を下位とした順序関係にて、
すべての該順序関係にある上位の格子点と下位の格子点について、該上位の格子点から該下位の格子点への有向辺を設けるように、前記有向無閉路グラフを構成することと、
前記第２のステップでは、
前記要素列の対応付けの目的において、前記格子点を構成する第１の要素列の要素と第２の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値０のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする。
【００３７】
この構成によれば、有向無閉路グラフ上の各格子点を終端とする経路コストの最小値は、有向無閉路グラフの半順序において上位に位置するすべての格子点を最小値選択範囲として持つことになり、ＤＰ平面である有向無閉路グラフ上で多くの第１の集合の要素、および、第２の集合の要素を対応付けせずに柔軟にスキップすることに相当する、多様な経路が最小コスト経路となり得る。このようにＤＰ平面上で多様な経路を許容すると、コストの増加を避けて好ましい対応付けもスキップされて想定外に小さい対応づけの集合となることが従来技術では懸念されるが、負のコストを格子点に設定することにより、好ましい対応付けは目的関数の最小化に有利な負のコストの格子点としてスキップされにくくなり、従来技術で懸念される事態が起こることが無い。
【００３８】
本発明に係る２つの要素列の対応付け方法の第２の構成は、
第１の要素列と第２の要素列とを比較して、第１の要素列の要素と第２の要素列の要素との組を1つ以上含む対応付けを得る際に、
第１の要素列の要素による集合と第２の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第１のステップと、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第１の要素列の要素と第２の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第２のステップと、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで２つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第３のステップと、
求めた最小コスト経路に含まれる格子点の第１の要素列の要素と第２の要素列の要素との組の集合を第１の要素列と第２の要素列との対応付けの結果とする第４のステップと、
を有する、要素列間対応付け方法において、
前記第１のステップでは、
前記第１の要素列の要素数をIとし、前記第２の要素列の要素数をＪとし、前記Iと前記Jとの２つの値に応じて、I2J2に比例する数の有向辺を設けて、前記有向無閉路グラフを構成することと、
前記第２のステップでは、
前記要素列の対応付けの目的において、前記格子点を構成する第１の要素列の要素と第２の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値０のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする。
【００３９】
この構成によれば、多様な経路が最小コスト経路となり得ることと、好ましい対応付けが負のコストの格子点としてスキップされにくいことと、の２つの特徴を維持しながら、２つの要素列を対応付ける処理の対象となる事象の固有の性質に基づき、対応付けとなるコスト最短経路に制約を加えることが出来る。
【００４０】
本発明に係る２つの要素列の対応付け方法の第３の構成は、
前記第１の構成、または前記第２の構成において、
前記最小コスト経路を求める第３のステップでは、
前記有向無閉路グラフにより定義される半順序によりトポロジカルソートした順序で前記格子点ごとに該格子点に至る経路の最小経路コストを順次計算する際に、
最小経路コストを求める対象である第１の格子点を終点とする有向辺の始点となる第２の格子点のすべてについて、
該第２の格子点の計算済みの最小経路コストに負または０の値を持つものがある場合には、その負または０の値の中での最小値に第１の格子点のコストを足した値を、第１の格子点へ至る経路の最小経路コストとし、さらに、該最小値の最小経路コストを有する第２の格子点を第１の格子点の親の格子点として記憶し、
該第２の格子点の計算済みの最小経路コストが例外なく正の値である場合には、第１の格子点のコストを第１の格子点の最小経路コストとするとともに、第１の格子点を始端候補として記憶し、
すべての前記格子点にて最小経路コストを計算したのちに、その中で最小の値を持つ格子点を終端と定め、
該終端である格子点を始まりとして、格子点から上記親の格子点を繰り返し求めるバックトラック手順を行い、
該バックトラック手順にて前記始端候補と記憶された格子点が前記親の格子点となった際には該格子点を始端と定めて繰り返しを終了し、
得られた終端と始端とを両端としてバックトラック手順で現れた格子点を前記有向辺でつないだ経路を最小コスト経路とすることを特徴とする。
【００４１】
この構成によれば、コストが最小となる経路の始端と終端とが固定されず、第１および第２の要素列の中で対応付けに最初に含まれる始点、および、最後に含まれる終点が固定されないようになる。この性質は、始端終端フリー化として、非特許文献１（２．５項）にも記されており、始点終点付近の不安定部分をスキップすることなどを行うことが出来る。本発明による本発明による始端終端フリー化は、始端終端に全く制限を設けないという意味で、完全な一般化となる。
【００４２】
本発明に係る２つの要素列の対応付け方法の第４の構成は、
前記第３の構成において、
前記始端候補および前記終端の少なくとも１つについて、前記第３のステップにて決定する際に、あらかじめ定めた条件を満たす格子点のみを、前記始端候補および前記終端と決定する対象とすることを特徴とする。
【００４３】
この構成によれば、始端終端フリー化により決まる始端終端の位置を、２つの要素列を対応付ける処理の対象となる事象の固有の性質に基づき、適当な範囲内とすることが出来る。
【００４４】
本発明に係る２つの要素列の対応付け装置の第１の構成は、
第１の要素列と第２の要素列とを比較して、第１の要素列の要素と第２の要素列の要素との組を1つ以上含む対応付けを得る際に、
第１の要素列の要素による集合と第２の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第１の手段と、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第１の要素列の要素と第２の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第２の手段と、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで２つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第３の手段と、
求めた最小コスト経路に含まれる格子点の第１の要素列の要素と第２の要素列の要素との組の集合を第１の要素列と第２の要素列との対応付けの結果とする第４の手段と、
を有する、要素列間対応付け装置において、
前記第１の手段では、
前記有向無閉路グラフにより定義される半順序での、有向辺の始点側を上位、終点側を下位とした順序関係にて、
すべての該順序関係にある上位の格子点と下位の格子点について、該上位の格子点から該下位の格子点への有向辺を設けるように、前記有向無閉路グラフを構成することと、
前記第２の手段では、
前記要素列の対応付けの目的において、前記格子点を構成する第１の要素列の要素と第２の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値０のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする。
【００４５】
本発明に係る２つの要素列の対応付け装置の第２の構成は、
第１の要素列と第２の要素列とを比較して、第１の要素列の要素と第２の要素列の要素との組を1つ以上含む対応付けを得る際に、
第１の要素列の要素による集合と第２の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第１の手段と、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第１の要素列の要素と第２の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第２の手段と、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで２つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第３の手段と、
求めた最小コスト経路に含まれる格子点の第１の要素列の要素と第２の要素列の要素との組の集合を第１の要素列と第２の要素列との対応付けの結果とする第４の手段と、
を有する、要素列間対応付け装置において、
前記第１の手段では、
前記第１の要素列の要素数をIとし、前記第２の要素列の要素数をＪとし、前記Iと前記Jとの２つの値に応じて、I2J2に比例する数の有向辺を設けて、前記有向無閉路グラフを構成することと、
前記第２の手段では、
前記要素列の対応付けの目的において、前記格子点を構成する第１の要素列の要素と第２の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値０のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする。
【００４６】
本発明に係る２つの要素列の対応付け装置の第３の構成は、
装置の前記第１の構成、または装置の前記第２の構成において、
前記最小コスト経路を求める第３の手段では、
前記有向無閉路グラフにより定義される半順序によりトポロジカルソートした順序で前記格子点ごとに該格子点に至る経路の最小経路コストを順次計算する際に、
最小経路コストを求める対象である第１の格子点を終点とする有向辺の始点となる第２の格子点のすべてについて、
該第２の格子点の計算済みの最小経路コストに負または０の値を持つものがある場合には、その負または０の値の中での最小値に第１の格子点のコストを足した値を、第１の格子点へ至る経路の最小経路コストとし、さらに、該最小値の最小経路コストを有する第２の格子点を第１の格子点の親の格子点として記憶し、
該第２の格子点の計算済みの最小経路コストが例外なく正の値である場合には、第１の格子点のコストを第１の格子点の最小経路コストとするとともに、第１の格子点を始端候補として記憶し、
すべての前記格子点にて最小経路コストを計算したのちに、その中で最小の値を持つ格子点を終端と定め、
該終端である格子点を始まりとして、格子点から上記親の格子点を繰り返し求めるバックトラック手順を行い、
該バックトラック手順にて前記始端候補と記憶された格子点が前記親の格子点となった際には該格子点を始端と定めて繰り返しを終了し、
得られた終端と始端とを両端としてバックトラック手順で現れた格子点を前記有向辺でつないだ経路を最小コスト経路とすることを特徴とする。
【００４７】
本発明に係る２つの要素列の対応付け装置の第４の構成は、
装置の前記第３の構成において、
前記始端候補および前記終端の少なくとも１つについて、前記第３の手段にて決定する際に、あらかじめ定めた条件を満たす格子点のみを、前記始端候補および前記終端と決定する対象とすることを特徴とする。
【００４８】
本発明に係るプログラムの構成は、前記第１乃至第４の構成に係る要素列間対応付け方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００４９】
以上説明したように、本発明によれば、２つの要素列間の対応付けにおいて、第１の特徴である対応付けを決定するために用いるＤＰ平面上に構成する有向非閉路グラフを有向辺が十分な数だけあるものすることにより、スキップや始端終端の位置に制約が少ない柔軟な対応付けが可能となる。また、第２の特徴である、対応付ける要素間のコストであるＤＰ平面上の格子点のコストを、格子点に対応する要素間を対応付けるべきであれば負のコストとし、そうでなければ非負のコストにして、負のコストの格子点と非負のコストの格子点とを混在させることにより、経路コストの最小を得るように経路を決定する動的計画法が適用されると、負のコストを持つ格子点を経由することを積極的に求め、正のコストを持つ格子点を経由することを避けるように、経路が決定される。これにより、制限が無いことにより意図しない対応付けとなる事態を起こさないようになるとともに、負と非負とにコストを定めた基準に沿った対応付けを得ることが出来る。
【図面の簡単な説明】
【００５０】
【図１】従来技術でのＤＰ漸化式での最小値選択範囲を図示したものである。
【図２】従来技術でのＤＰ平面上の有向無閉路グラフを図示したものである。
【図３】本発明の実施例での最小値選択範囲を図示したものである。
【図４】ＤＰ平面上の始端終端および経路を、本発明の実施例と従来技術の実施例とで比較した図である。
【図５】負のコストによる最小コスト経路選択を、正のコストによる最小コスト経路選択と比較した図である。
【図６】本発明の実施例での、境界値により最適な対応付けが変化する事例を説明した図である。
【図７】本発明の実施例での、制約条件を課した場合のＤＰ平面上の有向無閉路グラフの存在範囲を示す図である。
【図８】本発明の実施例での、対応付け方式を実装したJavaScript（登録商標）プログラムである。
【発明を実施するための形態】
【００５１】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００５２】
最初に上述の式（２）〜（５）で示した従来技術との比較が可能なように、本発明での対応付け方法の定式化を行う。従来技術の説明においてもその定式化は多様な方法のうちの一例を示したが、本発明での定式化も多様な方法のうちの一例となる。定式化は、可能な限り一般性のあるものとしている。
【００５３】
実施例１における対応付けの対象は、従来技術での定式化と同じく、式（１）に示す２つの要素列、XとYとする。
【００５４】
式（２）に示した従来技術の例での対応付けの定式化では、iの値がひとつずつ増える連続性制約を前提としていた。従来技術のＤＰマッチングにおいてもiの値がひとつずつ増える連続性制約は必須のものではなく、式（２）は非特許文献１第２節に記述された一例に従ったものである。本発明においては、iの値がひとつずつ増える連続性制約は課さない方が一般的であるため、次の式（６）のように対応付けを定式化する。すなわち、単純にiとjとの組の集合（直積の部分集合）Uで対応付けを表す。
【００５５】
【数６】
2016177327.tif 000008
【００５６】
式（７）に示すように、本発明によるコストは、値域が非負となるノルムではなく、負の値も値域に含む一般的な関数とする。
【００５７】
【数７】
2016177327.tif 000009
【００５８】
式（７）のような正負の値を取るコストは、xiとyjとの間の性質を表す非負の物理量（たとえば２点間の距離、ノルム）に対して境界値（Border Value）を設定し、その境界値を非負の物理量から引いた値をコストとすることで実現できる。すなわち、式（７）の関数fは、式（８）のように定義することで実現できる。
【００５９】
【数８】
2016177327.tif 000010
【００６０】
本発明による実施例となる対応付けの最適化問題を、式（１）（６）（７）を用いて、次の式（９）のように定式化する。従来技術の例である式（４）と異なり、式（９）では単調性制約のみを制約条件としている。単調性制約は、ＤＰ平面上に有向無閉路グラフが構成される十分条件であり、これにより動的計画法の適用可能が保証される。しかしながら、必要条件ではなく、単調性制約を課さない定式化も考えられる。多くの場合は、単調性制約を課しても適用範囲が狭められることは無い。
【００６１】
【数９】
2016177327.tif 000011
【００６２】
式（１０）に、本発明による実施例のＤＰ漸化式を示す。この漸化式の１つめの特徴は、最小値選択範囲が固定でなく、iとjとの増加に伴って大きくなることである。２つめの特徴は、始端を一意に定めていないことである。すなわち、最小値選択範囲内に負か０の値の経路の最小コストが無い場合にはそれらを引き継がず、格子点のコストを経路の最小コストとして、始端候補となることである。
【００６３】
【数１０】
2016177327.tif 000012
【００６４】
図３に、本発明による実施例でのＤＰ漸化式の最小値選択範囲を示す。従来技術の図１での最小値選択範囲の大きさは固定であったのに対し、図３では３０１の注目する特定の格子点(i,j)について、最小値選択範囲はi×j-1の大きさになっている。このため、従来ＤＰマッチングでの計算量はO(IJ)であったのに対して、本発明による対応付けでは、O(I2J2)となる。計算量は増えるが、多項式時間の範囲である。
【００６５】
図３の最小値選択範囲は特定の格子点３０１について記しているが、他の格子点についても同様な最小値選択範囲が設定される。これは、動的計画法による最短経路探索が行われる有向無閉路グラフが、有向辺の始点側を上位、終点側を下位とした半順序において、上位下位の順序関係が存在する２つの格子点においては、必ず上位の格子点から下位の格子点へ有向辺を有するものであることを示している。このように本発明の特徴の一つは、動的計画法を適用する有向無閉路グラフの形状として表すことが出来る。
【００６６】
式（１０）によりすべての格子点での経路の最小コストを求めた後、本発明の実施例での終端(ie,je)を、次の式（１１）に従って、経路の最小コストが一番小さい格子点として求める。すなわち、終端も固定されていない。すべてのコストが非負の場合は必ずgI,Jが最小となるが、負のコストを導入されているため、gI,Jが最小とは限らない。
【００６７】
【数１１】
2016177327.tif 000013
【００６８】
本発明による実施例でも、対応付けは、終端から始端へＤＰ漸化式での最小値の選択に基づくバックトラック手順により得られる。終端は、式（１１）に示した条件により確定される。この終端よりバックトラック手順を行い、辿りついた式（１０）での始端候補が始端となる。
【００６９】
このように始端終端を固定しない本発明による実施例は、非特許文献１に記された“始端終端のフリー化”の完全な一般化となっている。図４を用いて、本発明による“始端終端のフリー化”の説明を行う。図４中、４１０のＤＰ平面上には式（６）〜（１１）で定式化した本発明による実施例で有り得る最小コストの経路の例が示してあり、４２０のＤＰ平面上には式（１）〜（５）で定式化した従来ＤＰマッチングで有り得る最小コストの経路の例が示してある。図４中４２０のＤＰ平面上に示すように、式（１）〜（５）で定式化した従来ＤＰマッチングにおいては、式（４）中に示したu1=1、および、uI=Jの条件により、始端（４４１）と終端（４６１）とは固定されており、動的計画法により得られる経路はいずれもこれらを両端としている。これに対して本発明による実施例での要素列間の対応付けではすべての格子点が始端終端となる可能性があるため、図４中４１０のＤＰ平面上に示すように、始端（４３１，４３２，４３３）、および、終端（４５１，４５２，４５３）を異にした経路が動的計画法により得られる。すなわち、式（１１）により得られる終端は固定的でなく、この終端からバックトラックにより辿りつく始端候補も固定的ではない。
【００７０】
図５を用いて、本発明による実施例での負のコストの役割について説明する。すなわち、式（７）（８）に記したコストにより、図３のような最小値選択範囲としても、意図しない極端な対応付けとならない理由を説明する。図５中では負のコストの役割に絞って説明するため、簡略化した表記を用いている。すなわち、格子状の各辺にはその辺の始点から終点へのコストが記しており、これ以外の始点と終点の組み合わせの場合は、図には記されていないがコストを０とする。
【００７１】
図５中５１０のＤＰ平面上では、記されたコストはすべて正であり、記されていないコストを含めてすべて非負である。この際に左下の丸印の始端（５３１）から右上の四角印の終端（５５１）への最小コスト経路は、図に示すように始端と終端とを直接結んだ経路となり、経路の最小コストは０となる。この５１０のＤＰ平面上の経路は、意図しない極端な対応付けの例となっている。
【００７２】
一方、図５中５２０のＤＰ平面上に記されたコストは、５０１での対応する辺のコストから１０を引いた数値であり、全て負となっている。記されていないコストを合わせて、５２０のコストはすべて０以下である。この際に左下の丸印の始端（５４１）から右上の四角印の終端（５６１）への最小コスト経路は、図に示すように負のコスト値の小さいもの（絶対値が大きいもの）を選んで構成されており、合計コストは、（−８）＋（−７）＋（−７）＋（−９）＋（−８）で計算される、−３９となる。
【００７３】
図５で説明したように、負のコストを導入すれば対応付けの個数(｜U｜)が大きい（経路のエッジの数が多い）ほどコスト最小化に向かう性質を帯びる。逆にすべての対応付けコストが非負であれば、｜U｜ が大きいほどコストが増えて最適解から遠ざかる性質を帯びる．すなわち、負のコストを導入すれば積極的(アグレッシブ) に多くの対応付けの個数(｜U｜) を得ようとするのに対し，コストが非負であれば対応付けの個数を増やすことには消極的になる。式（１）〜（５）による従来ＤＰマッチングでの傾斜制限や始端終端の固定は、コストの増加を嫌って対応付けを避ける性質に対して、対応付けを強制する働きがある。すなわち、傾斜制限の条件下でコストを生じる対応付けをなるべく避けた解を求めるよう、従来ＤＰマッチングは働く。
【００７４】
これに対して、本発明による実施例では、コストを避けるのではなく、負のコストを求めて積極的に対応付けを増やそうとする方向に最適化が働く。これにより，コストを避けた短絡的な最小解を防ぐことを目的とする、固定的な最小値選択範囲を設ける必要が無くなる。
【００７５】
なお、ＤＰマッチングではなく一般的な動的計画法を有向無閉路グラフに適用する場合、負の重み付けを持つネットワークの最短経路探索問題では、“エッジの数が多い経路”を探索するように性質が変わることは，教科書にも記されている（例えば、R. Sedgewick, Algorithms in Java（登録商標） Third Edition Part 5:Graph Algorithms, Addison Wesley, 2003.など）。
【００７６】
以上、式（６）〜（１１）により、本発明による実施例での２つの要素列の対応付け問題の定式化を行った。式（６）〜（１１）の実施例ではなるべく一般的な定式化を行っているが、これよりも制約条件を多くしても良い。
【００７７】
例えば式（１０）および図３に示す最小値選択範囲は、適用する対象の性質に合わせて、条件を課して狭くする場合もあり得る。例えば前記第１の要素列の特定の要素については、前記第２の要素列のうち特定の複数要素のいずれかと対応させなければならない条件がある場合、この条件に合わせて部分的に最小値選択範囲を狭くしても良い。
【００７８】
また、従来のＤＰマッチングで計算量を削減するために行われている“枝刈り”の処理を、本発明の実施例に適用することも可能である。“枝刈り”は、経路コストが最小となる可能性が小さい経路を見出してその計算を行わないようにする処理である。そのような枝刈りは動的計画法を適用する有向無閉路グラフの形状を変更している訳ではなく、本発明の要件には関わらない。
【００７９】
また、始端終端についても、制限を加えても良い。従来ＤＰマッチングのように始端終端を固定としても良いし、終端や始端候補を決める際に条件を課しても良い。例えば終端は、ＤＰ平面上で(I,J)から一定距離範囲の格子点の中で、経路の最小コストが最小であるものを選んでも良い。
【実施例２】
【００８０】
次に具体的な数値を伴った対象に対する、本発明の実施例を、図を用いて説明する。対応付けの対象となる２つの要素列を、式（１２）に示す通り、２次元平面上の点列とする。
【００８１】
【数１２】
2016177327.tif 000014
【００８２】
対応する点の間のマンハッタン距離（各座標の差の絶対値の総和）を、コストの基になる物理量とする。すなわち、式（８）での||xi-yj||は、表１のとおりとなる。
【００８３】
【表１】
2016177327.tif 000015
【００８４】
図６に、要素間のコストを定める際に表１のマンハッタン距離による物理量から減じる境界値を変えた場合に、得られる対応付けが変わる様子を示す。図６には、縦方向に並んだ“(a)境界値＝０”（６１０）、“(b) 境界値＝４”（６２０）、“(c)境界値＝８”（６３０）のそれぞれの場合について，横方向に並んだ[対応付け１]（６０１）、[対応付け２]（６０２）、[対応付け３]（６０３）の３つの対応付けの合計コストとその計算の内訳が示されている。図６中の６６１、６６２、６６３は、それぞれの対応付けの集合による表現を示す。
【００８５】
図６中６４０に式（１２）のXの点列を、６５０にYの点列を、それぞれ図示する。なお、図６中に図示する２次元平面では、x軸は右方向、y軸は下方向、左上端が原点としている。
【００８６】
図６中６４１、および、６５１は、[対応付け１]により対応付けられた点列X中の点、および、点列Y中の点を、矢印で結んで示したものである。同様に、６４２と６５２は[対応付け２]の、６４３と６５３は[対応付け３]の、対応付けられた点列X中の点、および、点列Y中の点を、矢印で結んで示したものである。
【００８７】
なお、図６の例では、分かりやすさのために、対応付けは１対１で，２つ以上の対応があるという制約条件を設けて、対応付けを行っている。
【００８８】
図６（ａ）の“境界値＝０”（６１０）の場合は，傾斜制限の無い従来ＤＰマッチングと同じことになるため、意図しない極端な対応付けである[対応付け１]（６６１、U={(x1,y1), (x4,y3)}）での合計コストが１となり、最適解となっている。このコストの内訳を、６１１に示す。x1とy1とを対応付けることによるコストは、表１中に示した２点間のマンハッタン距離である“０”から、境界値である“０”を引いて、“(0 - 0)”として求められる。x4とy3とを対応付けることによるコストは、表１中に示した２点間のマンハッタン距離である“１”から、境界値である“０”を引いて、“(1 - 0)”として求められる。これら２つのコストを合計した“１”が[対応付け１]の合計コストであり、同様な方法で求めた[対応付け２]の合計コスト（６１２）、および、[対応付け３]の合計コスト（６１３）よりも小さく、最小値となっている。
【００８９】
図６（ｂ）の“境界値＝４”（６２０）の場合は、「距離が“４”以内であれば類似しているとして対応付けたほうが良く、それ以上であれば対応付けない方が良い」ということを意味する。この基準に従うと、[対応付け２]（６６２、U={(x1,y1), (x2,y2), (x4,y3)}）での合計コストが−９となり、最適解となっている。このコストの内訳を、６２２に示す。x1とy1とを対応付けることによるコストは、表１中に示した２点間のマンハッタン距離である“０”から、境界値である“４”を引いて、“(0 - 4)”として求められる。x2とy2とを対応付けることによるコストは、表１中に示した２点間のマンハッタン距離である“２”から、境界値である“４”を引いて、“(2 - 4)”として求められる。x4とy3とを対応付けることによるコストは、表１中に示した２点間のマンハッタン距離である“１”から、境界値である“４”を引いて、“(1 - 4)”として求められる。これら３つのコストを合計した“−９”が[対応付け２]の合計コストであり、同様な方法で求めた[対応付け１]の合計コスト（６２１）、および、[対応付け３]の合計コスト（６２３）よりも小さく、最小値となっている。
【００９０】
図６（ｃ）の“境界値＝８”（６３０）の場合は，「距離が“８”以内であれば対応付けた方が良い」ということを意味し、マス目の縦横が５であるので、ほとんどの場合は遠くても対応付けたほうが良いことになる。この結果、[対応付け３]（６６３、U={(x1,y1), (x2,y2), (x3,y3), (x4,y4)}）での合計コストが−２２となり、最適解となる。このコストの内訳を、６３３に示す。x1とy1とを対応付けることによるコストは、表１中に示した２点間のマンハッタン距離である“０”から、境界値である“８”を引いて、“(0 - 8)”として求められる。x2とy2とを対応付けることによるコストは、表１中に示した２点間のマンハッタン距離である“２”から、境界値である“８”を引いて、“(2 - 8)”として求められる。x3とy3とを対応付けることによるコストは、表１中に示した２点間のマンハッタン距離である“５”から、境界値である“８”を引いて、“(5 - 8)”として求められる。x4とy4とを対応付けることによるコストは、表１中に示した２点間のマンハッタン距離である“３”から、境界値である“８”を引いて、“(3 - 8)”として求められる。これら４つのコストを合計した“−２２”が[対応付け３]の合計コストであり、同様な方法で求めた[対応付け１]の合計コスト（６３１）、および、[対応付け２]の合計コスト（６３２）よりも小さく、最小値となっている。
【００９１】
仮に「２つの点列により構成されるポリラインのうち、人が見て類似したものを探し出す」という目的であれば，図６中の６４２と６５２との点列の図示が似ているという意味で、“境界値＝４”（６２０）がこれに比較的適う。例えば漢字書き取り自動採点装置において、正答となる漢字中の画と、これに対応する入力された漢字中の画とについて、画を構成する辺を対応付ける応用へは、この類似したポリラインを探し出す方法が適用可能である。さまざまな応用分野の目的に応じて、この境界値は決めれば良い。単純な方法としては、要素列間のすべての要素の組み合わせにおけるコストの平均値や中央値を境界値とすることが考えられる。
【００９２】
また、図６の（ｂ）の“境界値＝４”（６２０）の場合、最適解である[対応付け２]において、y4は対応付けから外れている。これは、上述の“始端終端のフリー化”の例となっている。
【実施例３】
【００９３】
実施例２では、実施例１の図３に示した最小値選択範囲を採らず、１対１対応とする制約条件を設けた。実施例３では、このように制約条件を変更した場合の、有向無閉路グラフ上での有向辺の数に関わる条件を明らかにするための実施例を示す。
【００９４】
実施例３を示すに先立って、実施例１と実施例２とについて、その有向辺の数を示す。
【００９５】
実施例１では、図３に示す最小値選択範囲をすべての前記有向無閉路グラフ上の格子点で取っており、式（１）中のI、Jを用いて、有向無閉路グラフ上での有向辺の数|E|は、次の式（１３）のように表される。
【００９６】
【数１３】
2016177327.tif 000016
【００９７】
実施例２では、「1対１の対応」という制約条件を伴っている。式（１）中のI、Jについて、I=4、J=4となっているが、IとJとに値を代入しないで、有向無閉路グラフ上での有向辺の数|E|は、次の式（１４）のように表される。なお、表記を簡易にするために、式（１４）ではi’=i-1とj’=j-1という変数の置き換えを行っている。
【００９８】
【数１４】
2016177327.tif 000017
【００９９】
式（１４）は式（１３）の値よりも小さくなるが、I2J2に比例する数であることには変わりない。すなわち、図３に示す最小値選択範囲を小さくする制約条件を課した場合でも、制約条件が図３の最小値選択範囲を割合として小さくする場合には、有向辺の数はI2J2に比例する数となる。図１に示した固定的な最小値選択範囲となるような制約条件を課した場合は、有向辺の数はIJに比例する数となる。この有向辺の数の違いが、本発明による効果の有無に直結している。すなわち、本発明の適用に際して、最小値選択範囲を小さくする制約条件を課すことは出来るが、I2J2に比例する数の有向辺を持つ有向無閉路グラフとすることは必要となる。
【０１００】
実施例３での有向辺の数を表すために、制約条件を課さない場合の有向辺の数を表す関数を、次のようにe(m,n)と定義しておく。すなわち、実施例１の場合であれば、|E|=e(I,J)となる。
【０１０１】
【数１５】
2016177327.tif 000018
【０１０２】
以上、実施例１、および、実施例２での有向無閉路グラフ上での有向辺の数について整理した。
【０１０３】
実施例３では、式（１）、（６）〜（１１）による実施例１に対して「(xi1, yj2)、もしくは、(xi2, yj1)のいずれかの対応付けを必ず含む（但し、i1＜ i2, j1＜ j2）」という制約条件を課す。すなわち、次の式（１６）を制約条件として課す。この制約条件は、すべての格子点の最小値選択範囲を一律に制約した実施例２での制約条件と異なり、ＤＰ平面上で巨視的に制約条件を課するものである。このため、部分的な格子点での最小値選択範囲に影響する。
【０１０４】
【数１６】
2016177327.tif 000019
【０１０５】
式（１）、（６）〜（１１）、（１６）による実施例３の対応付けにおける前記有向無閉路グラフは、図７のハッチングした部分（７４１、７４２）の内部に構成されることになる。始端（７１１）からの経路は、座標が(i1, j2)の格子点７３１と、座標が(i2, j1)の格子点７３２とのいずれかを通る。すなわち、始端７１１から格子点７３１もしくは格子点７３２とまでの経路は、始点終点とも７４１のハッチングした部分にある有向辺を連ねたものである。格子点７３１もしくは格子点７３２とから終端７２１までの経路は、始点終点とも７４２のハッチングした部分にある有向辺を連ねたものである。なお、図７のハッチング範囲内に有向無閉路グラフがあれば、式（１６）が満たされるという訳ではない。
【０１０６】
図７中のハッチング部分での有向辺の数を数えれば良いので、式（１６）による制約条件を課した実施例３での有向無閉路グラフの有向辺の数|E|は、式（１５）のe(m,n)を用いて、次の式（１７）のとおりとなる。式（１７）中、始めの３つの項は７４１のハッチング部分での有向辺の数であり、格子点７１１と７３１とを結ぶ線分を対角線とする長方形内の有向辺の数e(i1,j2)と、格子点７１１と７３２とを結ぶ線分を対角線とする長方形内の有向辺の数e(i2,j1)とを足したものから、格子点７１１と７５１とを結ぶ線分を対角線とする長方形内の有向辺の数e(i1,j1)を引くことによって求めている。終わりの３つの項は７４２のハッチング部分での有向辺の数である。
【０１０７】
式（１７）の値は、式（１３）や式（１４）と同様に、I2J2に比例する数となる。
【０１０８】
【数１７】
2016177327.tif 000020
【０１０９】
逆に、I2J2に比例する数の有向辺がある有向無閉路グラフであれば、すべての格子点ではなくとも、(i,j)の座標を持つ格子点にi×j個に比例する最小値選択範囲があるような、一群の格子点が必ず存在する。その部分では、境界値により設定された基準に従って、その部分内での任意の個数の要素をスキップして、類似しているとする部分を柔軟に対応付けることが出来るという本発明効果が、制約条件の範囲内で発揮される。
【実施例４】
【０１１０】
本発明による対応付け方式の実装方法の実施例について、図８を用いて説明する。図８は、式（１）、（６）〜（１０）に従う本発明による対応付け方式を、プログラミング言語ＪavaＳcript（登録商標）により実装したものである。図８のプログラムでは変数として、第１の要素列の要素数であるI、第２の要素列の要素数であるJ、境界値であるBV、xiとyjとの物理量であるmd（マンハッタン距離Manhattan distanceを意識した変数名）が設定済みであることを前提としている。
【０１１１】
図８のプログラム中、nodesが格子点の情報を格納するオブジェクトの２次元配列である。この格子点のオブジェクトには、式（１０）中のgi,jに相当し、経路の最小コストを保持するgフィールドと、バックトラックを行うために最小コストを設定した前の格子点のオブジェクトを保持するprevious_nodeフィールドとが設けられている。その他、格子点(i,j)の座標値である第１の要素列の要素番号iと、第２の要素列の要素番号jを保持するフィールドも設けられている。なお、JavaScript（登録商標）においては配列のインデックスは０からであるが、式（６）〜（１０）の表記と合わせるため、図８のプログラムではインデックスを１から使用している。
【０１１２】
図８のプログラム中２行めと４行めとの繰り返しは、すべての格子点を順に処理するためのものである。変数iとjとを共に昇順でループさせれば、単調性制約の元で構成されたＤＰ平面上の有向無閉路グラフの半順序のトポロジカルソート順となり、動的計画法を適用する要件を満たす。
【０１１３】
図８のプログラム中５行めから７行めでは、格子点の初期化を行っている。このうち７行めでは、式（１０）の漸化式の始端候補である場合の経路のコストを設定している。この始端候補としての経路コストの値は、後の処理で該格子点が始端候補以外となる場合に、更新される。
【０１１４】
図８のプログラム中８行めと９行めとの繰り返しは、格子点に対する最小値選択範囲を順に処理するためのものである。すなわち、式（１０）の最小値に対する範囲設定の“1≦it≦i, 1≦ｊt≦ｊ”に対応するものである。
【０１１５】
図８のプログラム中１１行めから１３行めは、最小値を更新する処理である。１１行めで最小値の更新となるか否かを判定し、１２行目で最小値を更新し、１３行めではバックトラック処理のために前の格子点をpvevious_nodeフィールドに記憶する。８行めと９行めとの繰り返しの終了時に、この１１行めから１３行めの処理によってpvevious_nodeフィールドが設定されていれば始端候補であり、設定されていれば始端候補ではない。
【０１１６】
図８のプログラム中１５行めから２２行めは、式（１１）に従って終端を求める処理である。
【０１１７】
図８のプログラム中２３行めから２９行めは、終端からバックトラック処理を行って、対応付けを表す経路を文字列として求める処理である。２６行めでは、始端候補に達したことをpvevious_nodeフィールドが設定されていないことにより判定している。得られた対応付け結果は、30行めで出力される。
【０１１８】
図８のプログラムにて、Iに４を、Jに４を、mdに表１の値を設定し、BVをそれぞれ０、４、８の値に設定して、図６に示した結果を得るように動作させるには、前述した「対応付けは１対１、２つ以上の対応」という条件を盛り込む必要がある。例えば「対応付けは１対１」の条件は、８行めと９行めとの繰り返し文中の判定部にて、“＜＝”を“＜”に変更すれば良い。
【０１１９】
図８のプログラム、もしくは、他のプログラミング言語での同等のプログラムは、ＣＰＵ、メモリ等を備えた一般的な計算機で実行可能である。また、組み込みシステムとして、図８のプログラム、もしくは、他の言語での同等のプログラムを実行する装置を構成することも、可能である。さらに図８のプログラム中の２行めと４行めとの繰り返しの内部の処理は、前記有向無閉路グラフでの半順序の順序関係を守る範囲で並列化が可能であり、スレッドに分割してマルチコアＣＰＵ上の別コアで実行させることも出来る。いずれの実装も、一般的な周知の方法により実現可能である。
【産業上の利用可能性】
【０１２０】
画像や音声信号、文章など、様々な対象について、２つの要素列間の対応付けに利用可能であり、認証、認識、検索などの用途に適用できる。
【符号の説明】
【０１２１】
１０１〜１０４    最小値選択範囲の例
２０１    始端
２０２    終端
３００    ＤＰ平面
３０１    注目する特定の格子点
４１０，４２０    ＤＰ平面
４３１〜４３３、４４１    始端
４５１〜４５３、４６１    終端
５１０、５２０    ＤＰ平面
５３１、５４１    始端
５５１、５６１    終端
６０１〜６０３    対応付けごとの列
６１０、６２０、６３０    境界値
６１１〜６１３、６２１〜６２３、６３１〜６３３    合計コストとその計算
６４０、６５０    点列の図示
６４１〜６４３、６５１〜６５３    対応付けの対象となった点列の矢印による図示
６６１〜６６３    対応付けの集合による表現
７００    ＤＰ平面
７１１    始端
７２１    終端
７３１、７３２    制約条件で言及する格子点
７４１、７４２    ハッチング部分
７５１、７５２    格子点
【図１】
2016177327.tif 000021
【図２】
2016177327.tif 000022
【図３】
2016177327.tif 000023
【図４】
2016177327.tif 000024
【図５】
2016177327.tif 000025
【図６】
2016177327.tif 000026
【図７】
2016177327.tif 000027
【図８】
2016177327.tif 000028