(57)【要約】【課題】頂点位置が元の埋め込みグラフの頂点位置に限定されない、埋め込みグラフ単純化装置を提供する。【解決手段】埋め込みグラフ単純化装置は、頂点位置を整列する埋め込みグラフ整列部を備える。埋め込みグラフ整列部は、整列のための最適化問題を立式して出力する最適化問題立式部と、最適化問題を求解して整列された頂点位置を求める最適化問題求解部とを備える。最適化問題立式部は、頂点位置を変数として用いて、整列された埋め込みグラフが直線に近い度合いを評価する整列正則化関数を生成する整列正則化関数立式部を含む。整列正則化関数立式部は、頂点に接続される２つの辺の大きさによる影響が相対的に小さく、２つの辺が成す角度による影響が相対的に大きくなるように重み付け合成して、整列正則化関数を生成する。【選択図】図１１
2018136797.tif 000002
【特許請求の範囲】
【請求項１】
頂点の位置情報を有する埋め込みグラフを単純化する埋め込みグラフ単純化装置であって、
各頂点に接続する辺の成す角度が小さくなるように頂点位置を整列する埋め込みグラフ整列部、
を備え、
前記埋め込みグラフ整列部は、
整列のための最適化問題を立式して出力する最適化問題立式部と、
前記最適化問題立式部で出力された整列のための最適化問題を求解して、整列された頂点位置を求める最適化問題求解部と、
前記最適化問題求解部で求められた頂点位置で、前記埋め込みグラフの頂点の位置情報を置き換える頂点情報置換部と、
を備え、
前記最適化問題立式部は、
整列された埋め込みグラフの頂点位置を変数として用いて、整列された埋め込みグラフが直線に近い度合いを評価する整列正則化関数を生成する整列正則化関数立式部と、
整列された後の前記頂点位置の範囲に関する制約条件を生成する制約条件立式部と、
前記整列正則化関数立式部が生成した前記整列正則化関数に基づく目的関数と前記制約条件とを合わせて最適化問題を生成する最適化問題生成部と、
を備え、
前記整列正則化関数立式部は、前記埋め込みグラフに含まれる各頂点に接続する辺の向きおよび大きさを表す辺ベクトルを求め、前記頂点に接続される２つの辺の大きさと前記２つの辺が成す角度とを、前記２つの辺の大きさによる影響が相対的に小さく前記２つの辺が成す角度による影響が相対的に大きくなるように重み付け合成して、前記整列正則化関数を生成する、
埋め込みグラフ単純化装置。
【請求項２】
前記最適化問題立式部は、
整列された埋め込みグラフの頂点位置を変数としたときに、前記変数が元の頂点位置とどれだけ乖離しているかを評価する頂点位置変化損失関数を生成する頂点位置変化損失関数立式部と、
整列正則化関数立式部が出力した前記整列正則化関数にトレードオフパラメータを乗算する乗算器と、
前記頂点位置変化損失関数と、前記トレードオフパラメータが乗算された整列正則化関数とを線形結合して目的関数を生成する加算器と、
を備え、
前記最適化問題生成部は、前記加算器が出力した前記目的関数と前記制約条件とを合わせて最適化問題を生成する、
請求項１に記載の埋め込みグラフ単純化装置。
【請求項３】
前記埋め込みグラフ整列部によって整列された埋め込みグラフから、接続する辺の成す角度が小さい頂点を選定し、前記接続する辺の成す角度が小さい頂点を取り除く不要頂点除去部、
をさらに備える請求項１または２に記載の埋め込みグラフ単純化装置。
【請求項４】
前記整列正則化関数立式部は、
前記埋め込みグラフに含まれる頂点のうち接続される辺の数が２である頂点に、当該頂点に接続される各々の辺の大きさと向きを表す辺ベクトル生成線形写像Ｌｍ（ｍは頂点のインデックス，ｍ＝１，・・・，Ｍ）を生成する辺ベクトル生成線形写像生成部と、
前記辺ベクトル生成線形写像生成部が出力した前記辺ベクトル生成線形写像Ｌｍと前記埋め込みグラフの頂点情報を示す変数Ｕとを入力して、辺ベクトル行列Ｐｍ（Ｐｍ＝ＬｍＵ）を生成する辺ベクトル行列生成部と、
前記辺ベクトル行列生成部が出力した前記辺ベクトル行列Ｐｍの、辺の大きさに対応する第１特異値と、２辺が成す角度に対応する第２特異値と、を求める特異値分解部と、
前記第１特異値および前記第２特異値にそれぞれ対応する第１重み値ｗ１および第２重み値ｗ２を用いて、前記第１特異値および前記第２特異値の加重和を生成する加重和生成部と、
前記加重和生成部が出力した前記加重和または前記加重和の２乗の、全ての頂点の総和を整列正則化関数として生成する総和生成部と、
を備え、
前記加重和生成部は、（ｗ２≧ｗ１≧０）の関係を満たす前記第１重み値ｗ１および前記第２重み値ｗ２を用いる、
請求項１から３までのいずれか一項に記載の埋め込みグラフ単純化装置。
【請求項５】
頂点の位置情報を有する埋め込みグラフを単純化する埋め込みグラフ単純化方法であって、
各頂点に接続する辺の成す角度が小さくなるように頂点位置を整列する埋め込みグラフ整列処理ステップ、
を有し、
前記埋め込みグラフ整列処理ステップは、
整列のための最適化問題を立式して出力する最適化問題立式処理ステップと、
前記最適化問題立式処理ステップで出力された整列のための最適化問題を求解して、整列された頂点位置を求める最適化問題求解処理ステップと、
前記最適化問題求解処理ステップで求められた頂点位置で、前記埋め込みグラフの頂点の位置情報を置き換える頂点情報置換処理ステップと、
を有し、
前記最適化問題立式処理ステップは、
整列された埋め込みグラフの頂点位置を変数として用いて、整列された埋め込みグラフが直線に近い度合いを評価する整列正則化関数を生成する整列正則化関数立式処理ステップと、
整列された後の前記頂点位置の範囲に関する制約条件を生成する制約条件立式処理ステップと、
前記整列正則化関数立式処理ステップで生成した前記整列正則化関数に基づく目的関数と前記制約条件とを合わせて最適化問題を生成する最適化問題生成処理ステップと、
を有し、
前記整列正則化関数立式処理ステップは、前記埋め込みグラフに含まれる各頂点に接続する辺の向きおよび大きさを表す辺ベクトルを求め、前記頂点に接続される２つの辺の大きさと前記２つの辺が成す角度とを、前記２つの辺の大きさによる影響が相対的に小さく前記２つの辺が成す角度による影響が相対的に大きくなるように重み付け合成して、前記整列正則化関数を生成する、
埋め込みグラフ単純化方法。
【請求項６】
コンピュータを、請求項１から４までのいずれか一項に記載の埋め込みグラフ単純化装置として機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、埋め込みグラフ単純化装置、埋め込みグラフ単純化方法、及びコンピュータプログラムに関する。
【背景技術】
【０００２】
ネットワークや地理情報学、画像工学などの諸分野において、埋め込みグラフというデータ構造が存在する。埋め込みグラフとは、複数の頂点とその頂点同士を結ぶ辺の集合であるグラフと、その頂点位置を合わせて定義したものである。例えばネットワークでは、ネットワークノードを頂点、ネットワークリンクを辺に対応させてグラフを構成できる。
このとき、ネットワークノードの物理的な位置や、ネットワークを可視化する際のノード座標を頂点位置に対応させると、埋め込みグラフを見出すことができる。また、地理情報学であれば、国境や県境、海岸線、湖岸線等の境界線データは一般に、埋め込みグラフとしてデータが保持されている。境界線上に密に頂点をプロットして辺を結ぶことで、境界線を表現している。また、画像工学分野であれば、形状や領域に関するデータの保持に埋め込みグラフが使用される。例えばベクター画像におけるオブジェクト形状、深度マップにおける深度境界線、自然画像の被写体形状やテクスチャ領域形状等のデータは、埋め込みグラフとして表現される。形状や領域の境界上に頂点をプロットすることで、境界線を辺により表現している。
【０００３】
以上で例示した埋め込みグラフにおいては、埋め込みグラフの形状をできるだけ保ちつつ、頂点数や辺数を可能な限り削減して単純化すること（以下、埋め込みグラフの単純化、あるいは単に単純化と呼ぶ）に大きなメリットがある。
【０００４】
ネットワークにおいては、頂点数、辺数が多いほど詳細なデータを表現できる一方で、一見してネットワーク構成の概要を掴むことが困難になり、加えてデータ量が膨大になるため描画に大きな負荷がかかる。このネットワークについての埋め込みグラフを単純化できれば、ネットワーク構成を視覚的に分かりやすく提示でき、頂点数、辺数を減らしてデータ圧縮し、描画の負荷を低減することが可能になる。地理情報学においては、境界線上に密に頂点をプロットすることで正確に境界線を表現するが、データ量は膨大になってしまう。境界線データを単純化することで、データ量を削減して伝送や蓄積が可能な他、境界を簡略した視覚的に分かりやすい地理情報を生成することができる。また画像工学においては、頂点数、辺数が多いほど形状や領域のデータを詳細に保持して正確に表現可能である一方で、データ量が膨大になり、伝送や蓄積に要する符号量が増えてしまう。この形状や領域を単純化できれば、表現の正確性を可能な限り保ちながら、頂点数、辺数を削減して符号量を削減できる。
【０００５】
折れ線グラフや多角形等、非常に簡単な埋め込みグラフを単純化する有効な手法として、Ｒａｍｅｒ−Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒ法（非特許文献１以下ＲＤＰ法）がある。以下、折れ線分にＲＤＰ法を適用する場合のアルゴリズムを説明する。この手法では、（１）まず折れ線分の両端頂点を結んだ線分を初期の折れ線分とする。（２）現在の折れ線分と最も距離の離れた頂点を現在の折れ線分に順次加える。（３）最も離れた頂点との距離が予め定めた許容誤差ε（＞０）よりも小さくなった時点で処理を終了する。
【０００６】
図１３は、ＲＤＰ法の動作例を示している。図１３において、白丸及び破線は入力した埋め込みグラフの折れ線成分を示し、黒丸及び実線は単純化した埋め込みグラフの折れ線成分を示す。図１３（Ａ）は初期状態（状態ＳＴ０）である。初期状態では、折れ線分の端点を繋いだ線分を初期の折れ線分Ｅ１とする。次のステップで加える頂点は、折れ線分Ｅ１からもっとも離れた頂点Ｖ１である。図１３（Ｂ）に示すように、状態ＳＴ１では、頂点Ｖ１を折れ線成分Ｅ１に加えて、新しい折れ線成分Ｅ２とする。次のステップで加える頂点は、折れ線分Ｅ２からもっとも離れた頂点Ｖ２である。図１３（Ｃ）に示すように、状態ＳＴ２では、頂点Ｖ２を折れ線成分Ｅ２に加えて、新しい折れ線成分Ｅ３とする。次のステップで加える頂点は、折れ線分Ｅ３からもっとも離れた頂点Ｖ３である。図１３（Ｄ）に示すように、状態ＳＴ３では、頂点Ｖ３を折れ線成分Ｅ３に加えて、新しい折れ線成分Ｅ４とする。状態ＳＴ３では、全ての頂点が折れ線分Ｅ４から許容誤差以内の距離となり、ここで、単純化処理は終了となる。
【０００７】
多角形の場合は両端点の代わりに、多角形頂点から適切に２点を選んで初期の折れ線分と設定することで、折れ線分のＲＤＰ法を適用可能である。さらにＲＤＰ法では、使用者が指定した特定の頂点を、入力埋め込みグラフと同じ頂点位置で、必ず含むように単純化を行うことも可能である。初期の折れ線分作成時に指定頂点を加え、処理を開始すれば良い。
【０００８】
ＲＤＰ法は形状近似の精度の高さ、実装の容易さなどから最もよく使用される方法である。例えばコンピュータビジョン向けのコンピュータプログラムライブラリであるＯｐｅｎＣＶでは、被写体形状の単純化や輪郭の近似処理としてＲＤＰ法が採用されている。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Hershberger and Snoeyink,"An O (n log n) implementation of the Douglas-Peucker algorithm for line simplification," pp. 383-384, 1994.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述したＲＤＰ法では以下の２つの問題が生じる。（１）折れ線分や多角形を除く、複雑な埋め込みグラフへの適用が困難である。（２）単純化した埋め込みグラフの頂点位置は、元の埋め込みグラフの頂点位置を厳密に守るため、頂点位置を微小に変位させてより良い単純化を算出することができない。
【００１１】
上述の（１）の問題について説明する。上述したネットワークや地図・交通解析、画像・映像符号化の例でも見られるように、一般に埋め込みグラフは分岐、複数のループ、非結合グラフ等を持ち、折れ線分や多角形よりも複雑な構造を持つ。ＲＤＰ法はこのような複雑なグラフを単純化することができない。あるいは折れ線や多角形に分解する前処理と分解したグラフを結合する後処理を行えば、複雑なグラフについてもＲＤＰ法を適用できる。しかし分岐数が多い複雑なグラフでは分解数が増えて端点が増えるため、複雑なグラフほど頂点や辺の削減が困難になる。
【００１２】
上述の（２）の問題について説明する。ＲＤＰ法では元の埋め込みグラフの頂点を選択して新しい埋め込みグラフを構成するため、新しい埋め込みグラフの頂点位置は元の埋め込みグラフと同じ頂点位置に必ず限定される。一般に、頂点位置が微小に変位することを許容すればより良い単純化をすることができるが、ＲＤＰ法ではこれを算出できない。また同じ理由で、使用者が特定頂点に課す制約についても、入力と同じ頂点位置であることしか指定できない。
【００１３】
上記事情に鑑み、本発明は、頂点位置が元の埋め込みグラフの頂点位置に限定されない埋め込みグラフ単純化装置、埋め込みグラフ単純化方法、及びコンピュータプログラムを提供することを目的としている。
また、本発明の副次的な課題は、複雑な埋め込みグラフにおいても頂点や辺を削減可能とすることである。
【課題を解決するための手段】
【００１４】
本発明の一態様は、頂点の位置情報を有する埋め込みグラフを単純化する埋め込みグラフ単純化装置であって、各頂点に接続する辺の成す角度が小さくなるように頂点位置を整列する埋め込みグラフ整列部、を備え、前記埋め込みグラフ整列部は、整列のための最適化問題を立式して出力する最適化問題立式部と、前記最適化問題立式部で出力された整列のための最適化問題を求解して、整列された頂点位置を求める最適化問題求解部と、前記最適化問題求解部で求められた頂点位置で、前記埋め込みグラフの頂点の位置情報を置き換える頂点情報置換部と、を備え、前記最適化問題立式部は、整列された埋め込みグラフの頂点位置を変数として用いて、整列された埋め込みグラフが直線に近い度合いを評価する整列正則化関数を生成する整列正則化関数立式部と、整列された後の前記頂点位置の範囲に関する制約条件を生成する制約条件立式部と、前記整列正則化関数立式部が生成した前記整列正則化関数に基づく目的関数と前記制約条件とを合わせて最適化問題を生成する最適化問題生成部と、を備え、前記整列正則化関数立式部は、前記埋め込みグラフに含まれる各頂点に接続する辺の向きおよび大きさを表す辺ベクトルを求め、前記頂点に接続される２つの辺の大きさと前記２つの辺が成す角度とを、前記２つの辺の大きさによる影響が相対的に小さく前記２つの辺が成す角度による影響が相対的に大きくなるように重み付け合成して、前記整列正則化関数を生成する、埋め込みグラフ単純化装置である。
【００１５】
本発明の一態様は、上記の埋め込みグラフ単純化装置であって、前記最適化問題立式部は、整列された埋め込みグラフの頂点位置を変数としたときに、前記変数が元の頂点位置とどれだけ乖離しているかを評価する頂点位置変化損失関数を生成する頂点位置変化損失関数立式部と、整列正則化関数立式部が出力した前記整列正則化関数にトレードオフパラメータを乗算する乗算器と、前記頂点位置変化損失関数と、前記トレードオフパラメータが乗算された整列正則化関数とを線形結合して目的関数を生成する加算器と、を備え、前記最適化問題生成部は、前記加算器が出力した前記目的関数と前記制約条件とを合わせて最適化問題を生成する、埋め込みグラフ単純化装置である。
【００１６】
本発明の一態様は、上記の埋め込みグラフ単純化装置であって、前記埋め込みグラフ整列部によって整列された埋め込みグラフから、接続する辺の成す角度が小さい頂点を選定し、前記接続する辺の成す角度が小さい頂点を取り除く不要頂点除去部、をさらに備える、埋め込みグラフ単純化装置である。
【００１７】
本発明の一態様は、上記の埋め込みグラフ単純化装置であって、前記整列正則化関数立式部は、前記埋め込みグラフに含まれる頂点のうち接続される辺の数が２である頂点に、当該頂点に接続される各々の辺の大きさと向きを表す辺ベクトル生成線形写像Ｌｍ（ｍは頂点のインデックス，ｍ＝１，・・・，Ｍ）を生成する辺ベクトル生成線形写像生成部と、前記辺ベクトル生成線形写像生成部が出力した前記辺ベクトル生成線形写像Ｌｍと前記埋め込みグラフの頂点情報を示す変数Ｕとを入力して、辺ベクトル行列Ｐｍ（Ｐｍ＝ＬｍＵ）を生成する辺ベクトル行列生成部と、前記辺ベクトル行列生成部が出力した前記辺ベクトル行列Ｐｍの、辺の大きさに対応する第１特異値と、２辺が成す角度に対応する第２特異値と、を求める特異値分解部と、前記第１特異値および前記第２特異値にそれぞれ対応する第１重み値ｗ１および第２重み値ｗ２を用いて、前記第１特異値および前記第２特異値の加重和を生成する加重和生成部と、前記加重和生成部が出力した前記加重和または前記加重和の２乗の、全ての頂点の総和を整列正則化関数として生成する総和生成部と、を備え、前記加重和生成部は、（ｗ２≧ｗ１≧０）の関係を満たす前記第１重み値ｗ１および前記第２重み値ｗ２を用いる、埋め込みグラフ単純化装置である。
【００１８】
本発明の一態様は、頂点の位置情報を有する埋め込みグラフを単純化する埋め込みグラフ単純化方法であって、各頂点に接続する辺の成す角度が小さくなるように頂点位置を整列する埋め込みグラフ整列処理ステップ、を有し、前記埋め込みグラフ整列処理ステップは、整列のための最適化問題を立式して出力する最適化問題立式処理ステップと、前記最適化問題立式処理ステップで出力された整列のための最適化問題を求解して、整列された頂点位置を求める最適化問題求解処理ステップと、前記最適化問題求解処理ステップで求められた頂点位置で、前記埋め込みグラフの頂点の位置情報を置き換える頂点情報置換処理ステップと、を有し、前記最適化問題立式処理ステップは、整列された埋め込みグラフの頂点位置を変数として用いて、整列された埋め込みグラフが直線に近い度合いを評価する整列正則化関数を生成する整列正則化関数立式処理ステップと、整列された後の前記頂点位置の範囲に関する制約条件を生成する制約条件立式処理ステップと、前記整列正則化関数立式処理ステップで生成した前記整列正則化関数に基づく目的関数と前記制約条件とを合わせて最適化問題を生成する最適化問題生成処理ステップと、を有し、前記整列正則化関数立式処理ステップは、前記埋め込みグラフに含まれる各頂点に接続する辺の向きおよび大きさを表す辺ベクトルを求め、前記頂点に接続される２つの辺の大きさと前記２つの辺が成す角度とを、前記２つの辺の大きさによる影響が相対的に小さく前記２つの辺が成す角度による影響が相対的に大きくなるように重み付け合成して、前記整列正則化関数を生成する、埋め込みグラフ単純化方法である。
【００１９】
本発明の一態様は、コンピュータを、上記の埋め込みグラフ単純化装置として機能させるためのコンピュータプログラムである。
【発明の効果】
【００２０】
本発明によれば、複雑な埋め込みグラフにおいても頂点や辺を削減可能で、頂点位置が元の埋め込みグラフの頂点位置に限定されず、埋め込みグラフ単純化が可能となる。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１実施形態による埋め込みグラフ単純化装置の構成を示すブロック図である。
【図２】本発明の第１実施形態による埋め込みグラフ直線整列部のブロック図である。
【図３】本発明の第１実施形態による直線整列のための最適化問題立式部のブロック図である。
【図４】本発明の第１実施形態による直線整列正則化関数立式部の詳細な機能構成を示すブロック図である。
【図５】本発明の第１実施形態による埋め込みグラフ単純化処理のフローチャートである。
【図６】本発明の第１実施形態による埋め込みグラフ直線整列処理のフローチャートである。
【図７】本発明の第１実施形態による直線整列のための最適化問題立式処理のフローチャートである。
【図８】本発明の第１実施形態による埋め込みグラフ単純化装置における入力とする埋め込みグラフの例を示す図である。
【図９】本発明の第１実施形態による埋め込みグラフ単純化装置における直線整列された埋め込みグラフの例を示す図である。
【図１０】本発明の第２実施形態による直線整列のための最適化問題立式部の機能構成を示すブロック図である。
【図１１】本発明の第２実施形態による直線整列正則化関数立式部の詳細な機能構成を示すブロック図である。
【図１２】本発明の第２実施形態による埋め込みグラフ単純化装置が回避する問題を説明するための概略図である。
【図１３】埋め込みグラフ単純化方法であるＲＤＰ法の概略（従来技術）を示す図である。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態について図面を参照して説明する。
［第１実施形態］
図１は、本発明の一実施形態における埋め込みグラフ単純化装置１の構成を示すブロック図である。埋め込みグラフ単純化装置１は、バスで接続されたＣＰＵ（Central Processing Unit）やメモリや補助記憶装置などを備え、プログラムを実行する。埋め込みグラフ単純化装置１は、プログラムの実行によって埋め込みグラフ直線整列部１１及び不要頂点除去部１２を備える装置として機能する。なお、埋め込みグラフ単純化装置１の各機能の全て又は一部は、ＡＳＩＣ（Application Specific Integrated Circuit）やＰＬＤ（Programmable Logic Device）やＦＰＧＡ（Field Programmable Gate Array）等のハードウェアを用いて実現されてもよい。プログラムは、コンピュータ読み取り可能な記録媒体に記録されてもよい。コンピュータ読み取り可能な記録媒体とは、例えばフレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置である。プログラムは、電気通信回線を介して送信されてもよい。
【００２３】
図１において、埋め込みグラフ単純化装置１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）とトレードオフパラメータλとを入力して、単純化された埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）を出力する。ここで、埋め込みグラフとは、図１に示すように、異なる位置に配置された複数の点と、当該複数の点同士の接続によって形状を示す二次元データであり、埋め込みグラフ単純化装置１は、より広い概念では、このような二次元データを対象として単純化を行う二次元データ単純化装置であると言える。
【００２４】
元の埋め込みグラフＧ＝（Ｖ，Ｅ）において、Ｖは元の埋め込みグラフＧの頂点情報であり、各頂点の頂点ＩＤ（IDentification）及び頂点の位置の情報を含む。データ構造の例としてＤ次元座標空間上に分布するＮ個の頂点を考えると、各頂点に「１」から「Ｎ」の整数の頂点ＩＤを任意に付与して、各頂点の座標値を頂点ＩＤの順に並べたＮ行Ｄ列行列をＶとすれば、上記頂点情報の要件を満たす。本実施形態では、この例に倣って、元の頂点情報ＶをＮ行Ｄ列行列として記述する。なお、Ｎ行Ｄ列行列のデータ構造以外に、等価に変換可能な別のデータ構造を用いても良い。Ｅは元の埋め込みグラフＧの辺情報で、どの頂点を接続して各辺を成しているかという情報を含む。辺情報Ｅのデータ構造の例としては、隣接リスト、隣接行列、接続行列、ラプラシアン行列、Ｔｕｔｔｅ行列等がある。これらは、互いに等価に変換できることから、いずれを用いても良い。
【００２５】
単純化された埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）において、Ｖ＊は単純化された埋め込みグラフＧ＊の頂点情報であり、Ｅ＊は単純化された埋め込みグラフＧ＊の辺情報である。単純化された埋め込みグラフＧ＊の頂点情報Ｖ＊、及び辺情報Ｅ＊のデータ構造は、上記の元の埋め込みグラフＧの頂点情報Ｖ及び辺情報Ｅと同様のデータ構造である。ただし、単純化された埋め込みグラフＧ＊は、元の埋め込みグラフＧに比べて頂点数や辺数は減少している。
【００２６】
トレードオフパラメータλは正の実数値であり、大きいほど単純化の度合いを強くし、埋め込みグラフの頂点数が減少するよう調整することができる。
【００２７】
図１に示すように、埋め込みグラフ単純化装置１は、埋め込みグラフ直線整列部１１と、不要頂点除去部１２とを備える。埋め込みグラフ直線整列部１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）と、トレードオフパラメータλとを入力して、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する。
【００２８】
なお、本実施形態において「直線整列」とは、埋め込みグラフを構成する一連の頂点の少なくとも一部の並びが、例えばジグザグの形状から、なるべく直線に近い形状になるように頂点位置を変更することである。この直線整列の処理の結果、一連の頂点の並びが真に１本の直線状に並ぶ場合もあり、また、真の直線にはならないものの直線に近い度合いが高まる場合もある。また、「直線整列」のことを単に「整列」とも呼ぶ。
【００２９】
埋め込みグラフＧ’の辺情報Ｅは、元の埋め込みグラフＧの辺情報Ｅと同一の情報である。頂点情報Ｖ’のデータ構造及び頂点ＩＤは、元の頂点情報Ｖと同一であり、頂点位置のみが頂点情報Ｖと異なる。また、埋め込みグラフ直線整列部１１は、元の埋め込みグラフＧよりも直線整列するように変形した埋め込みグラフＧ’を生成する。例えば、埋め込みグラフ直線整列部１１は、図１に示すように埋め込みグラフＧの各頂点の座標を微小に動かし、１つの直線上に多くの頂点が並ぶように局所的に線形に整列（以下、局所線形整列という）させていき、埋め込みグラフＧ’を生成する。換言すると、埋め込みグラフ直線整列部１１は、各頂点に接続する辺の成す角度が小さくなるように頂点位置を直線整列する。ここで「各頂点に接続する辺の成す角度が小さくなる」とは、ある特定の頂点に接続する２つの辺の成す角度が１８０度（直線）に近付くことを意味する。
【００３０】
また、埋め込みグラフ直線整列部１１は、当該変形の際、トレードオフパラメータλが大きいほど直線に整列する度合いを強くする。換言すると、トレードオフパラメータλが大きいほど、埋め込みグラフＧ’の形状が、より少ない数の直線で表されることになる。
【００３１】
不要頂点除去部１２は、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を入力して、単純化された埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）を出力する。直線整列された埋め込みグラフＧ’の多くの頂点では、接続する辺の成す角度が小さくなっている。そのため、不要頂点除去部１２は、当該角度が予め定めた閾値以下の頂点を選定して取り除く、すなわちデシメーションすることで単純化した埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）を生成する。例えば、図１では、直線整列された埋め込みグラフＧ’の黒色の点を不要な頂点として取り除き、白色の点で構成させる直線整列された埋め込みグラフＧ’を生成している例を示している。
【００３２】
図２は、図１に示す埋め込みグラフ直線整列部１１の詳細な構成を示すブロック図である。図２に示すように、埋め込みグラフ直線整列部１１は、直線整列のための最適化問題立式部１１１と、最適化問題求解部１１２と、頂点情報置換部１１３とを備える。
【００３３】
直線整列のための最適化問題立式部１１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）と、トレードオフパラメータλとを入力して、直線整列のための最適化問題を出力する。出力する最適化問題は、目的関数と制約条件を記述した数式であり、式（１）で示される。なお、この最適化問題は、凸最適化問題であってもよく、また非凸最適化問題であってもよい。
【００３４】
【数１】
2018136797.tif 000003
【００３５】
この式（１）は、これから求めたい直線整列された埋め込みグラフの頂点情報を示す変数をＵとして、「ｓｕｂｊｅｃｔ  ｔｏの右側の制約を満たす変数Ｕの中で、ｍｉｎｉｍｉｚｅの右側の目的関数値を最小にするＮ行Ｄ列の行列Ｕを求めよ」という最適化問題を表現している。
【００３６】
目的関数は二つの項の線形結合で構成されている。第一項は、直線整列された埋め込みグラフの頂点情報を変数Ｕとしたときに、元の埋め込みグラフの頂点情報Ｖと変数Ｕとがどれだけ乖離しているかを評価するコスト、すなわち評価値である。すなわち、第一項は、整列による頂点座標の極端な変化を抑制できているかを示す忠実化項といえる。
【００３７】
第二項は、直線整列された埋め込みグラフの頂点情報を変数Ｕとしたときに、埋め込みグラフ（Ｕ，Ｅ）が直線整列されている度合いを評価するコスト、すなわち評価値である。すなわち、第二項は、辺の折れ曲がりに対するペナルティ、換言すると直線整列のなめらかさを示す正則化項といえる。
【００３８】
制約条件は、直線整列された埋め込みグラフの頂点情報を示す変数Ｕの可動範囲を表している。この最適化問題は、後続の最適化問題求解部１１２により解を求めることで、直線整列された頂点情報Ｖ’が生成されるよう設計されている。
【００３９】
式（１）において、ｆは頂点位置変化損失関数であり、ｇは辺ベクトル角評価関数である。頂点位置変化損失関数ｆ及び辺ベクトル角評価関数ｇは、微分可能であるか、または近接写像計算可能な関数である。Ｌｍは辺ベクトル生成線形写像である。Ｃは制約集合である。制約集合Ｃは、射影が計算可能な集合である。
【００４０】
最適化問題求解部１１２は、最適化問題を入力として、その解を求め、直線整列された頂点情報Ｖ’を出力する。解を求めるためのアルゴリズムは任意に選択することができる。例えば、ＰＤＳ法（Primal Dual Splitting Method）では、頂点位置変化損失関数ｆの勾配計算、あるいは近接写像、辺ベクトル角評価関数ｇの勾配計算、あるいは近接写像、辺ベクトル生成線形写像Ｌｍとその共役写像ＬｍＴ（ｍ＝１，…，Ｍ）、制約集合Ｃへの射影、四則演算を組み合わせた反復で、最適化問題を求解することができる。なお、ＰＤＳ法については、以下の参考文献１に記載されている。
【００４１】
［参考文献１］：Condat, “A Generic Proximal Algorithm for Convex Optimization -Application to Total Variation Minimization”, Signal Process IEEE, vol. 21, no. 8, pp. 985-989, 2014.
【００４２】
頂点情報置換部１１３は、直線整列された頂点情報Ｖ’と、元の埋め込みグラフＧ＝（Ｖ，Ｅ）とを入力して、元の頂点情報Ｖを直線整列された頂点情報Ｖ’に置き換え、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する。つまり、頂点情報置換部１１３は、最適化問題求解部１１２で求められた頂点位置で、埋め込みグラフの頂点の位置情報を置き換える。
【００４３】
図３は、図２に示した直線整列のための最適化問題立式部１１１の詳細な構成を示すブロック図である。図３に示すように、直線整列のための最適化問題立式部１１１は、頂点辺情報分解部１１１１と、頂点位置変化損失関数立式部１１１２と、直線整列正則化関数立式部１１１３と、乗算器１１１４と、加算器１１１５と、制約条件立式部１１１６と、最適化問題生成部１１１７とを備える。
【００４４】
頂点辺情報分解部１１１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力し、元の頂点情報Ｖと元の辺情報Ｅに分解して出力する。
【００４５】
頂点位置変化損失関数立式部１１１２は、元の頂点情報Ｖを入力して、頂点位置変化損失関数ｆを出力する。頂点位置変化損失関数ｆは、直線整列された埋め込みグラフの頂点情報を変数Ｕとしたときに、元の頂点情報Ｖと変数Ｕとがどれだけ乖離しているかを評価するコストである。頂点位置変化損失関数ｆは、変数Ｕと元の頂点情報Ｖとの絶対値残差や二乗残差を評価する。頂点位置変化損失関数ｆとしては、式（２）〜（４）に例示するような関数を用いることができる。
【００４６】
【数２】
2018136797.tif 000004
【００４７】
式（２）〜（４）において、ｖｎ，ｄ及びｕｎ，ｄは、それぞれ、頂点情報Ｖの行列や変数Ｕの行列のｎ行ｄ列成分であり、頂点ＩＤがｎである頂点情報の第ｄ軸成分の値を表す。なお、式（３）及び式（４）におけるｖｅｃは、行列の要素を列ベクトルに並べ替える関数である。なお、頂点位置変化損失関数ｆとして用いる関数は、凸関数であってもよく、非凸関数であってもよい。
【００４８】
直線整列正則化関数立式部１１１３は、辺情報Ｅを入力して、各頂点に接続する辺の成す角度を評価する直線整列正則化関数（整列正則化関数）を出力する。直線整列正則関数は、一連の頂点の並びが直線に近い度合いを評価するための関数である。直線整列正則化関数は、式（５）に例示するようなものを用いることができる。
【００４９】
【数３】
2018136797.tif 000005
【００５０】
式（５）に示す関数は、直線整列された埋め込みグラフの頂点情報を変数Ｕとしたときに、変数Ｕを用いた埋め込みグラフ（Ｕ，Ｅ）が直線整列されている度合いを評価するコストである。このコストは、辺ベクトル生成線形写像Ｌｍ（ｍ＝１，…，Ｍ）と、辺ベクトル角評価関数ｇと、累積演算Σとで構成される。辺ベクトル生成線形写像Ｌｍ（ｍ＝１，…，Ｍ）は、直線整列された埋め込みグラフの頂点情報を示す変数Ｕから、次数（接続する辺の数）が２の頂点毎に接続する辺の大きさと向きを表すベクトル（辺ベクトル）を生成する操作を行う。辺ベクトル角評価関数ｇは、抽出した辺ベクトルの成す角度を核ノルムで評価する。累積演算Σは、これらの評価値を足し合わせる。以下に、この算出法を説明する。
【００５１】
まず、整数Ｍは、埋め込みグラフＧの頂点のうち、次数が２である頂点の個数であり、辺情報Ｅより算出する。そして、Ｍ個ある次数２の頂点に（ｍ＝１，…，Ｍ）の番号を付与し、その頂点ＩＤをｃｕｒｒ＿ｉｄ（ｍ）、隣接する２つの頂点の頂点ＩＤをそれぞれｐｒｅｖ＿ｉｄ（ｍ）、ｎｅｘｔ＿ｉｄ（ｍ）とする。
【００５２】
辺ベクトル生成線形写像Ｌｍ（ｍ＝１，…，Ｍ）は、（ｃｕｒｒ＿ｉｄ（ｍ），ｐｒｅｖ＿ｉｄ（ｍ））の辺ベクトルと、（ｃｕｒｒ＿ｉｄ（ｍ），ｎｅｘｔ＿ｉｄ（ｍ））の辺ベクトルとを算出し、算出されたこれらの辺ベクトルを２行Ｄ列の行列に並べて格納する操作である。この２行Ｄ列の行列を辺ベクトル行列Ｐｍと呼ぶことにする。
【００５３】
辺ベクトル生成線形写像Ｌｍは、直線整列された埋め込みグラフの頂点情報を示す変数Ｕを入力して、辺ベクトル行列Ｐｍ＝ＬｍＵを出力する。辺ベクトル生成線形写像Ｌｍを式で記述すると、式（６）の通りである。
【００５４】
【数４】
2018136797.tif 000006
【００５５】
この辺ベクトル生成線形写像Ｌｍは、式（７）で示す２行Ｎ列の疎行列を変数Ｕの左から掛ける操作とも等しいため、辺ベクトル生成線形写像Ｌｍと式（７）の行列は同一のものであるとみなせる。
【００５６】
【数５】
2018136797.tif 000007
【００５７】
辺ベクトル角評価関数ｇは、２行Ｄ列の辺ベクトル行列Ｐｍに対し、各辺ベクトルの成す角の大きさを評価する。辺ベクトル角評価関数ｇには、式（８）や式（９）で例示するような関数を用いることができる。
【００５８】
【数６】
2018136797.tif 000008
【００５９】
式（８）及び式（９）において、σ１（Ｐｍ）とσ２（Ｐｍ）は、辺ベクトル行列Ｐｍの２つの特異値を表す。式（８）及び式（９）に示す関数は、２つの辺ベクトルの成す角度が小さいほど関数値が小さくなり、角度が大きいほど関数値が大きくなる。
【００６０】
乗算器１１１４は、式（５）の直線整列正則化関数とトレードオフパラメータλを乗算した関数を出力する。
【００６１】
加算器１１１５は、頂点位置変化損失関数ｆと乗算器１１１４が出力した関数を線形結合して、式（１）のｍｉｎｉｍｉｚｅの右側の目的関数を出力する。
【００６２】
制約条件立式部１１１６は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力し、式（１）のｓｕｂｊｅｃｔ  ｔｏの右側の制約条件式を出力する。制約条件式は、使用者が予め定めた制約であり、式（１０）のように幾つかの頂点情報を限定する制約や、式（１１）や式（１２）のように頂点情報の可動範囲を限定する制約などを課することができる。
【００６３】
【数７】
2018136797.tif 000009
【００６４】
式（１１）及び式（１２）において、ε（ｎ）は、使用者が予め定めた、頂点ＩＤがｎである頂点に対する可動範囲の最大値である。なお、これらの制約条件式（１０）〜（１２）のいくつかを組み合わせて制約条件式とすることもできる。また、制約条件を全く課さないという制約条件式を定めることもできる。
【００６５】
最適化問題生成部１１１７は、目的関数と制約条件式を入力して、直線整列のための最適化問題を生成する。すなわち、最適化問題生成部１１１７は、加算器１１１５から出力された目的関数の左側に最小化を表す「ｍｉｎｉｍｉｚｅ」を加え、制約条件立式部１１１６から出力された制約条件式の左側に制約を表す「ｓｕｂｊｅｃｔ  ｔｏ」を加えて、（１）式に示した最適化問題を出力する。
【００６６】
上記の辺ベクトル角評価関数ｇとして、式（８）の核型ノルム関数を適用することにより効果的に埋め込みグラフを直線整列できる。以下、辺ベクトル角評価関数ｇとして式（８）の核型ノルム関数が適用される場合の最適化問題求解部１１２について説明する。この場合、前述したＰＤＳ法を用いると、最適化問題求解部１１２において、式（１）に示す最適化問題の解を求めるために、次式（１３）に示されるような局所線形整列問題を解くアルゴリズムが適用される。
【００６７】
【数８】
2018136797.tif 000010
【００６８】
式（１３）において、太文字で示される行列Ｘは、前述した式（１）における変数Ｕに相当する。３つ目の演算式である次式（１４）において、括弧内の式（１５）の部分は、後述する行列Ｙとなる。すなわち、式（１４）は、行列Ｙに対して、２行Ｄ列の行列の特異値分解と、閾値処理と、２行Ｄ列の行列×Ｄ行Ｄ列の行列×Ｄ行Ｄ列の行列とを含む計算である核型ノルム関数の近接写像計算を適用し、当該計算を反復することを示している。
【００６９】
【数９】
2018136797.tif 000011
【００７０】
ここで、直線整列正則化関数立式部１１１３のさらに詳細な構成について説明する。
図４は、図３に示した直線整列正則化関数立式部１１１３の詳細な機能構成を示すブロック図である。図４に示すように、直線整列正則化関数立式部１１１３は、辺ベクトル生成線形写像生成装置１１１３１と、辺ベクトル行列生成装置１１１３２と、特異値分解装置１１１３３と、特異値インデクスについての和の生成装置１１１３４と、頂点インデクスについての総和の生成装置１１１３５とを備える。
【００７１】
辺ベクトル生成線形写像生成装置１１１３１は、辺情報Ｅに基づいて、辺ベクトル生成線形写像Ｌｍ（ｍ＝１，…，Ｍ）を生成し出力する。
【００７２】
辺ベクトル行列生成装置１１１３２は、辺ベクトル生成線形写像生成装置１１１３１から出力される辺ベクトル生成線形写像Ｌｍに基づいて、辺ベクトル行列Ｐｍ＝ＬｍＵを生成し出力する。この辺ベクトル行列Ｐｍは、上の説明における式（６）で示したものである。
【００７３】
特異値分解装置１１１３３は、辺ベクトル行列Ｐｍ＝ＬｍＵを入力し、この辺ベクトル行列Ｐｍの２つの特異値σ１（Ｐｍ）およびσ２（Ｐｍ）を求め、出力する。
【００７４】
特異値インデクスについての和の生成装置１１１３４は、特異値分解装置１１１３３から出力された２つの特異値の和である｛σ１（Ｐｍ）＋σ２（Ｐｍ）｝を算出し、出力する。
【００７５】
頂点インデクスについての総和の生成装置１１１３５は、特異値インデクスについての和の生成装置１１１３４から出力される特異値の和｛σ１（Ｐｍ）＋σ２（Ｐｍ）｝を入力し、頂点インデクスについての総和を算出する。
【００７６】
頂点インデクスについての総和の生成装置１１１３５からの出力は、式（１６）あるいは式（１７）で表される。
【００７７】
【数１０】
2018136797.tif 000012
【００７８】
つまり、頂点インデクスについての総和の生成装置１１１３５は、特異値インデクスについての和の生成装置１１１３４が出力した前記和または前記和の２乗の、全ての頂点の総和を直線整列正則化関数として生成する。これら式（１６）および式（１７）が、式（５）に示した直線整列正則化関数にあたるものである。なお、式（１６）および式（１７）は、辺ベクトル角評価関数ｇとして、それぞれ、式（８）および式（９）に示したものを用いる場合に対応する。
【００７９】
次に、図５、図６及び図７を用いて、本実施形態の埋め込みグラフ単純化装置１による単純化処理を説明する。
【００８０】
図５は、埋め込みグラフ単純化装置１による埋め込みグラフ単純化処理のフローチャートである。埋め込みグラフ直線整列部１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）と、トレードオフパラメータλとを入力して、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する（ステップＳ１１）。不要頂点除去部１２は、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を入力して、単純化された埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）を出力する（ステップＳ１２）。
【００８１】
図６は、図５のステップＳ１１において行われる埋め込みグラフ直線整列部１１による埋め込みグラフ直線整列処理を詳細化したフローチャートである。直線整列のための最適化問題立式部１１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）と、トレードオフパラメータλとを入力して、直線整列のための最適化問題を出力する（ステップＳ１１１）。最適化問題求解部１１２は、直線性列のための最適化問題を入力として、直線整列された頂点情報Ｖ’を出力する（ステップＳ１１２）。頂点情報置換部１１３は、直線整列された頂点情報Ｖ’と元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力して、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する（ステップＳ１１３）。
【００８２】
図７は、図６のステップＳ１１１において行われる直線整列のための最適化問題立式部１１１による直線整列のための最適化問題立式処理を詳細化したフローチャートである。頂点辺情報分解部１１１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力して、頂点情報Ｖと辺情報Ｅに分解して出力する（ステップＳ１１１１）。頂点位置変化損失関数立式部１１１２は、頂点情報Ｖを入力して、頂点位置変化損失関数ｆを出力する（ステップＳ１１１２）。直線整列正則化関数立式部１１１３は、辺情報Ｅを入力して、直線整列正則化関数を出力する（ステップＳ１１１３）。乗算器１１１４は、直線整列正則化関数とトレードオフパラメータλとを入力し、これら２つを乗算した関数を出力する（ステップＳ１１１４）。加算器１１１５は、頂点位置変化損失関数ｆと乗算器１１１４が出力した関数を線形結合して、目的関数を出力する（ステップＳ１１１５）。制約条件立式部１１１６は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力し、制約条件式を出力する（ステップＳ１１１６）。最適化問題生成部１１１７は、目的関数と制約条件式を入力して、直線整列のための最適化問題を生成して出力する（ステップＳ１１１７）。
【００８３】
次に具体例を挙げて、図１に示す埋め込みグラフ単純化装置１、図２に示す埋め込みグラフ直線整列部１１、及び図３に示す直線整列のための最適化問題立式部１１１が、図５、図６及び図７に示す処理を行うときの動作を説明する。
【００８４】
ここでは、画像領域の符号化のための埋め込みグラフ単純化を考え、埋め込みグラフは２次元平面上に埋め込まれたグラフ、頂点位置変化損失関数ｆは式（４）のコスト、辺ベクトル角評価関数ｇは式（８）のコスト、制約条件は画像縁に位置する頂点を式（１０）の形で制約するものとする。最適化問題求解部のアルゴリズムにはＰＤＳ法を用いるものとする。
【００８５】
埋め込みグラフ単純化装置１の入力である、元の埋め込みグラフＧ＝（Ｖ，Ｅ）は、図８に示す２次元平面上に埋め込まれたグラフとする。図８における丸の記号は埋め込みグラフの各頂点の位置を表し、丸の記号の右下の数字が頂点ＩＤを表している。また頂点位置は、図８における下方向を第１座標軸方向、右方向を第２座標軸方向とする直交座標系で記述する。例えば図８で最も左上にある頂点は頂点ＩＤが「２」で、その座標は（１，０）である。頂点情報ＶはＮ行２列行列とし、行番号が頂点ＩＤ、列番号が座標軸番号を示す。例えば頂点ＩＤが「２」の頂点についての情報は、頂点情報Ｖを示す行列の２行目に格納されており、（ｖ２，１＝１）であり、（ｖ２，２＝０）である。
【００８６】
頂点と頂点を結ぶ実線は、埋め込みグラフの各辺を表している。例えばＩＤが「ＩＤ＝２」の頂点と「ＩＤ＝３」の頂点の間には、この２頂点を結ぶ辺が存在する。辺情報Ｅは隣接リストとして格納されている。埋め込みグラフ単純化装置１の入力である、トレードオフパラメータλは、１．５などの任意の実数値を選ぶことができる。
【００８７】
埋め込みグラフ直線整列部１１が行う処理ステップＳ１１では、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する。この例では、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）として、図９のような埋め込みグラフを出力する。図９における丸の記号は、図８と同様に、埋め込みグラフの各頂点の位置を表し、丸の記号の右下の数字が頂点ＩＤを表している。図８と図９とを比較すれば分かるように、埋め込みグラフ直線整列部１１が行う処理ステップＳ１１により、各頂点の間の辺情報は維持され、埋め込みグラフが直線整列するように、頂点の位置が変動している。また、頂点ＩＤが（ＩＤ＝１，２，４２、…，１４１）の頂点については、制約条件により、変動位置が制約されている。
【００８８】
不要頂点除去部１２が行う処理ステップＳ１２では、埋め込みグラフＧ’の頂点のうち、接続する辺の成す角度が小さくなっている頂点を予め定めた閾値（例えばπ／１００ラジアン）で選定し、この頂点を取り除いて単純化された埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）を生成する。
【００８９】
埋め込みグラフ直線整列部１１が行う処理ステップＳ１１の詳細な動作について述べる。直線整列のための最適化問題立式部１１１が行う処理ステップＳ１１１では、例えば式（１３）の最適化問題を生成する。
【００９０】
【数１１】
2018136797.tif 000013
【００９１】
ここでは、頂点位置変化損失関数ｆは、式（４）のコストを用い、辺ベクトル角評価関数ｇは式（８）のコストを用いている。また、制約条件は、画像外縁に位置する頂点はその外縁上の移動しかできない事とし、式（１０）の形式で頂点ＩＤが（ＩＤ＝１，２，４２、…，１４１）の頂点について制約している。
【００９２】
最適化問題求解部１１２が行う処理ステップＳ１１２では、式（１８）の最適化問題をＰＤＳ法で解き、頂点情報Ｖ＊を生成する。
【００９３】
式（１８）に対するＰＤＳ法では、式（４）の頂点位置変化損失関数ｆの近接写像、式（８）の辺ベクトル角評価関数ｇの近接写像、辺ベクトル生成線形写像Ｌｍとその共役写像ＬｍＴ（ｍ＝１，…，１３２）、制約集合Ｃの制約条件を表す集合への射影を計算する必要がある。これらが計算可能であれば反復演算により解を求めることができる。
【００９４】
式（４）の頂点位置変化損失関数ｆの近接写像は、ある任意のステップサイズμ（＞０）に対して、式（１９）により計算できる。
【００９５】
【数１２】
2018136797.tif 000014
【００９６】
ここで関数ｓｉｇｎは、入力した行列の各要素の符号を抽出して−１，０，＋１に対応させ、入力と同じサイズの行列に格納して出力する関数である。また、丸で示す演算子はアダマール積で、左右の行列の要素同士を掛けあわせて同じサイズの行列に格納して出力する演算である。また、関数ｍａｘは、入力した２つの実数の値を比較して、大きい方を出力する関数である。
【００９７】
式（８）の辺ベクトル角評価関数ｇの近接写像は、ある任意のステップサイズμに対して、式（２０）により計算できる。
【００９８】
【数１３】
2018136797.tif 000015
【００９９】
ここで関数ｄｉａｇは、入力したベクトルを対角要素に並べた対角行列を出力する関数である。またＳ（Ｐ），Ｔ（Ｐ），σ（Ｐ）は行列Ｐの特異値分解であり、式（２１）が成立する。
【０１００】
【数１４】
2018136797.tif 000016
【０１０１】
辺ベクトル生成線形写像Ｌｍとその共役写像ＬｍＴ（ｍ＝１，…，１３２）は、式（７）の行列やその転置行列を左から掛ける操作により計算可能である。
【０１０２】
制約集合Ｃの制約条件を表す集合は式（２２）である。
【０１０３】
【数１５】
2018136797.tif 000017
【０１０４】
よって、Ｃへの射影は、式（２３）により計算できる。
【０１０５】
【数１６】
2018136797.tif 000018
【０１０６】
頂点情報置換部１１３が行う処理ステップＳ１１３では直線整列された頂点情報Ｖ’と元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力して、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する。すなわち、頂点情報置換部１１３が行う処理ステップＳ１１３は、元の埋め込みグラフＧの頂点情報Ｖを直線整列された頂点情報Ｖ’に置き換え、直線整列された埋め込みグラフＧ’を生成する。
【０１０７】
直線整列のための最適化問題立式部１１１が行う処理ステップＳ１１１の詳細な動作について述べる。頂点辺情報分解部１１１１が行う処理ステップＳ１１１１では、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力して、頂点情報Ｖと辺情報Ｅに分解して出力する。
【０１０８】
頂点位置変化損失関数立式部１１１２が行う処理ステップＳ１１１２では、元の頂点情報Ｖを入力して、頂点位置変化損失関数ｆを出力する。頂点位置変化損失関数ｆとしては、例えば式（４）のコストを使用する。
【０１０９】
直線整列正則化関数立式部１１１３が行う処理ステップＳ１１１３では、元の辺情報Ｅを入力して、式（５）の直線整列正則化関数を出力する。辺ベクトル生成線形写像Ｌｍ（ｍは頂点のインデックス，ｍ＝１，…，Ｍ）は、辺情報Ｅから各次数２の頂点の隣接頂点ＩＤを得ることで、式（７）の行列として生成することができる。また、辺ベクトル角評価関数ｇとしては、例えば式（８）のコストを使用する。
【０１１０】
乗算器１１１４が行う処理ステップＳ１１１４では、式（５）の直線性列正則化関数とトレードオフパラメータλを乗算した関数を出力する。
【０１１１】
加算器１１１５が行う処理ステップＳ１１１５では、頂点位置変化損失関数ｆと乗算器１１１４が出力した関数を線形結合して、式（１８）のｍｉｎｉｍｉｚｅの右側の目的関数を出力する。
【０１１２】
制約条件立式部１１１６が行う処理ステップＳ１１１６では、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力し、式（１８）のｓｕｂｊｅｃｔ  ｔｏの右側の制約条件式を出力する。
【０１１３】
最適化問題生成部１１１７が行う処理ステップＳ１１１７は、目的関数と制約条件式を入力して、直線整列のための最適化問題を生成する。すなわち、最適化問題生成部１１１７が行う処理ステップＳ１１１７は、目的関数と制約条件式それぞれの左側に、最小化を表す「ｍｉｎｉｍｉｚｅ」と、制約を表す「ｓｕｂｊｅｃｔ  ｔｏ」を加えて出力する。
【０１１４】
このように図７で示した処理手順に従って直線整列のための最適化問題を生成し、図６で示した処理手順に従って埋め込みグラフの直線整列を行い、図５で示した処理手順に従って埋め込みグラフを単純化することができる。
【０１１５】
［第２実施形態］
次に、第２実施形態について説明する。なお、前述の実施形態と同様の事項については記載を省略し、以下では本実施形態に特有の事項について説明する。
【０１１６】
第１実施形態による局所線形正則化法を用いた場合、多数の頂点から構成される急峻なカーブを短絡してグラフ形状を大きく劣化させるという問題が生じる場合がある。この原因は直線整列正則化関数立式部における特異値和にある。入力行列の２つの特異値のうち、第１特異値は入力行列の列ベクトルの大きさに寄与し、第２特異値は列ベクトルの成す角度に寄与している。ここで入力行列の列ベクトルは隣接する２つの辺ベクトルであるため、核ノルムを正則化することで、これらの辺ベクトル同士が成す角度を０度あるいは１８０度に近付けると同時に、ベクトルの大きさを小さくする効果が働いてしまう。このように各辺ベクトルの大きさを小さくする効果が働くことで、急峻なカーブを短絡し、グラフ形状を大きく劣化させてしまう場合がある。
【０１１７】
本実施形態は、グラフが多数の頂点から構成され、その形状が急峻なカーブを有する場合においても、単純化処理の結果として短絡化によりグラフ形状を大きく劣化させるという問題を回避するものである。
【０１１８】
図１０は、本実施形態における直線整列のための最適化問題立式部１１１の機能構成を示すブロック図である。図１０に示すように、本実施形態における直線整列のための最適化問題立式部１１１は、第１実施形態における直線整列のための最適化問題立式部１１１と類似の構成を有する。ただし、本実施形態における直線整列のための最適化問題立式部１１１は、直線整列正則化関数立式部１１１３に代えて、直線整列加重正則化関数立式部１１１８を備える。つまり、図１０の直線整列のための最適化問題立式部１１１は、直線整列加重正則化関数立式部１１１８を除いて、図３の直線整列のための最適化問題立式部１１１と同一構成、同一処理である。このため直線整列加重正則化関数立式部１１１８以外の各部についての説明を省略する。直線整列加重正則化関数立式部１１１８は、グラフの頂点について直線整列の処理を行う際に、２種類の特異値それぞれに重みを付けた加算を行う。
【０１１９】
ここで直線整列加重正則化関数立式部１１１８を詳細に説明する。図１１は、直線整列加重正則化関数立式部１１１８の詳細な機能構成を示すブロック図である。図１１に示すように、直線整列加重正則化関数立式部１１１８は、辺ベクトル生成線形写像生成装置１１１３１と、辺ベクトル行列生成装置１１１３２と、特異値分解装置１１１３３と、特異値インデクスについての加重和の生成装置１１１８４と、頂点インデクスについての総和の生成装置１１１３５とを備える。つまり、直線整列加重正則化関数立式部１１１８は、直線整列正則化関数立式部１１１３における特異値インデクスについての和の生成装置１１１３４に代えて、特異値インデクスについての加重和の生成装置１１１８４を備える。図１１に示す特異値インデクスについての加重和の生成装置１１１８４以外の各部の機能は、図４において同一符号を有する各部の機能と同一であり、ここでは説明を省略する。
【０１２０】
直線整列加重正則化関数立式部１１１８は、埋め込みグラフに含まれる各頂点に接続する辺の向きおよび大きさを表す辺ベクトルを求め、頂点に接続される２つの辺の大きさと２つの辺が成す角度とを、２つの辺の大きさによる影響が相対的に小さく、２つの辺が成す角度による影響が相対的に大きくなるように重み付け合成して、直線整列正則化関数を生成する。
【０１２１】
特異値インデクスについての加重和の生成装置１１１８４は、特異値分解装置１１１３３の出力である特異値と、重みｗ１（第１重み値）およびｗ２（第２重み値）とを入力して、特異値の加重和を生成し出力する。特異値インデクスについての加重和の生成装置１１１８４が求める特異値の加重和は、式（２４）で示す通りである。
【０１２２】
【数１７】
2018136797.tif 000019
【０１２３】
つまり、重みｗ１は、頂点に接続される２つの辺の大きさに対応する第１特異値（σ１）にかかる重みである。また、重みｗ２は、これらの２つの辺が成す角度に対応する第２特異値（σ２）にかかる重みである。
【０１２４】
式（２４）における重みｗ１およびｗ２としては、（ｗ２≧ｗ１≧０）という関係を満たす値を与えるようにする。なお、ｗ２とｗ１との関係として、（ｗ２＞ｗ１）としてもよい。また、ｗ１と０との関係として、（ｗ１＞０）としてもよい。第１実施形態の方法においては直線整列正則化したグラフが、指数関数をグラフ化した形状に収束する場合があり得る。一方、本実施形態の方法は、ベクトルの角度の重みｗ２をベクトルの大きさの重みｗ１以上（重みｗ１，ｗ２はいずれも非負値）とするため、そのような場合を回避することができる。つまり、本実施形態では、（ｗ２≧ｗ１≧０）としたため、グラフデータを単純化したときに、元のデータに関係なく指数関数をグラフ化した形状に単純化されることを避ける。つまり、ベクトルの角度の重みがベクトルの大きさの重みよりも大きくなるようにしている。
【０１２５】
特異値インデクスについての加重和の生成装置１１１８４が上記のように加重加算を行うようにしたため、本実施形態において、頂点インデクスについての総和の生成装置１１１３５が出力する総和値の例は、式（２５）および式（２６）に示す通りである。
【０１２６】
【数１８】
2018136797.tif 000020
【０１２７】
以上説明した本実施形態によれば、グラフが多数の頂点から構成され、そのグラフの形状が急峻なカーブを有する場合にも、グラフ単純化処理の結果として頂点の並びを短絡してグラフ形状を大きく劣化させるという問題を回避することができる。
【０１２８】
その理由は次の通りである。即ち、辺ベクトル行列Ｐｍ＝の２つの特異値のうち、第１特異値σ１（Ｐｍ）は入力行列の列ベクトルの大きさに寄与し、第２特異値σ２（Ｐｍ）は入力行列の列ベクトルの成す角度に寄与している。入力行列の列ベクトルは隣接する２つの辺ベクトルであるため、核ノルムを正則化すると、辺ベクトルの成す角度を０度あるいは１８０度に近付けると同時に、ベクトルの大きさを小さくする効果が働いてしまう。すると、各辺ベクトルの大きさを小さくする効果が働くことで、急峻なカーブを短絡し、グラフ形状を大きく劣化させてしまう場合があった。一方で、本実施形態の方法では、上記特異値の和計算に重み付けを付けることにより、第１特異値による影響を小さくし、第２特異値による影響を大きくする。これにより、各辺ベクトルの大きさを小さくする効果を抑制し、急峻なカーブの短絡を抑制する。つまり、本実施形態による方法では、単純化する対象のグラフが急峻なカーブを含む場合においても、短絡が少なく、劣化が生じにくい。
【０１２９】
図１２は、本実施形態による埋め込みグラフ単純化装置１が回避する問題を説明するための概略図である。同図において、一点鎖線で示す折れ線は、埋め込みグラフ単純化装置１への入力となるグラフの例の形状を示す。また、小さな丸印（頂点）と、これらの丸印を順次接続する実線による直線（辺）は、第１実施形態によるグラフの単純化の処理を行った場合、一つの処理結果の可能性を示す。図示するように、この結果の特に矢印で指し示す部分は、元のグラフを大幅に短絡させており、形状が劣化していると見なせる。本実施形態では、前述の通り第１特異値による影響を小さくして第２特異値による影響を大きくすることにより、グラフの形状劣化を回避することができる。なお、ここでは２次元平面上のグラフに単純化処理を適用した場合の例を示しているが、多次元（３次元以上）の空間におけるグラフに単純化処理を適用してもよいことは言うまでもない。
【０１３０】
上記のいずれかの実施形態の構成による埋め込みグラフ単純化装置１は、異なる位置に配置される複数の頂点と、複数の頂点同士の接続とによって形状を示すグラフを入力データとし、埋め込みグラフ直線整列部１１において、頂点位置変化損失関数立式部１１１２が、二次元データの形状がより少ない直線の組み合わせによって示されるように複数の頂点を移動させて直線上に整列させる場合、移動前後の頂点の位置の乖離度合いを示すコストを算出する頂点位置変化損失関数を生成する。また、直線整列正則化関数立式部１１１３または直線整列加重正則化関数立式部１１１８が、複数の頂点を直線上に整列させる場合、複数の頂点により形成される直線形状のなめらかさを示すコストを算出する直線整列正則化関数を生成する。最適化問題生成部１１１７は、頂点位置変化損失関数と、直線整列正則化関数と、制約条件式とに基づいて、式（１）に示す直線整列のための最適化問題を生成する。最適化問題求解部１１２は、直線整列のための最適化問題を解く過程で用いるアルゴリズムに含まれる行列Ｙを、核型ノルム関数の近接写像高速計算部１１２２により行列Ｚに変換させ、行列Ｚにより、制約条件下で、頂点位置変化損失関数が算出するコストと、直線整列正則化関数が算出するコストとの和が最小となる頂点の位置を算出する。頂点情報置換部１１３は、算出された位置に頂点を動かす。不要頂点除去部１２は、移動後の頂点同士の接続によって形成される辺の成す角度に基づいて前記点の中から不要な点を選別して除去する。これにより、複雑な埋め込みグラフにおいても頂点や辺を削減可能で、頂点位置が元の埋め込みグラフの頂点位置に限定されないようにすることができる。また、核型ノルム関数の近接写像高速計算部１１２２が、行列Ｙを行列Ｚに変換することにより、以下に示すように演算時間の削減を図ることが可能となる。
【０１３１】
［変形例］
ここで、上述した各実施形態に適用可能な変形例について説明する。
上述した各実施形態では、埋め込みグラフ単純化装置１は、埋め込みグラフ直線整列部１１と不要頂点除去部１２とを備えていた。この変形例として、埋め込みグラフ単純化装置１が不要頂点除去部１２を持たず、埋め込みグラフ直線整列部１１による直線整列の処理のみを行うようにしてもよい。この場合も、埋め込みグラフを単純化できるという効果を得ることができる。
【０１３２】
また、上述した各実施形態では、直線整列のための最適化問題立式部１１１が、頂点位置変化損失関数立式部１１１２と直線整列正則化関数立式部１１１３（または直線整列加重正則化関数立式部１１１８）の両方を備えていた。そして、これら両方において立式される関数を重み付け加算（重みは、トレードオフパラメータλによる）して、目的関数を生成していた。この変形例として、直線整列のための最適化問題立式部１１１が、頂点位置変化損失関数立式部１１１２を持たず、直線整列正則化関数立式部１１１３のみにおいて立式される関数を用いて、目的関数を生成するようにしてもよい。このような変形例では、単純化処理による頂点位置の変化がより大きくなる場合もあり得るが、頂点の直線整列という所定の効果を得ることはできる。
【０１３３】
なお、各実施形態および変形例で説明した埋め込みグラフ単純化装置１の全部または一部の機能を実現するためのプログラム（コンピュータプログラム）をコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各部の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【０１３４】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【符号の説明】
【０１３５】
１…埋め込みグラフ単純化装置、１１…埋め込みグラフ直線整列部（埋め込みグラフ整列部）、１２…不要頂点除去部、１１１…直線整列のための最適化問題立式部（最適化問題立式部）、１１２…最適化問題求解部、１１３…頂点情報置換部、１１１１…頂点辺情報分解部、１１１２…頂点位置変化損失関数立式部、１１１３…直線整列正則化関数立式部（整列正則化関数立式部）、１１１４…乗算器、１１１５…加算器、１１１６…制約条件立式部、１１１７…最適化問題生成部、１１１８…直線整列加重正則化関数立式部（整列正則化関数立式部）、１１１３１…辺ベクトル生成線形写像生成装置（辺ベクトル生成線形写像生成部）、１１１３２…辺ベクトル行列生成装置（辺ベクトル行列生成部）、１１１３３…特異値分解装置（特異値分解部）、１１１３４…特異値インデクスについての和の生成装置、１１１３５…頂点インデクスについての総和の生成装置（総和生成部）、１１１８４…特異値インデクスについての加重和の生成装置（加重和生成部）
【図１】
2018136797.tif 000021
【図２】
2018136797.tif 000022
【図３】
2018136797.tif 000023
【図４】
2018136797.tif 000024
【図５】
2018136797.tif 000025
【図６】
2018136797.tif 000026
【図７】
2018136797.tif 000027
【図８】
2018136797.tif 000028
【図９】
2018136797.tif 000029
【図１０】
2018136797.tif 000030
【図１１】
2018136797.tif 000031
【図１２】
2018136797.tif 000032
【図１３】
2018136797.tif 000033