(57)【要約】【課題】複雑な埋め込みグラフにおいても頂点や辺を削減可能で、頂点位置が元の埋め込みグラフの頂点位置に限定されないようにすること。【解決手段】異なる位置に配置される複数の点と、二次元データを単純化する二次元データ単純化装置であって、最適化処理部は、第１の評価関数及び第２の評価関数から導かれる第１の行列に対して予め定められる線形変換を行う第１の線形変換部と、線形変換に基づいて得られる第１のベクトルと、予め定められるパラメータとに基づいて、凸射影演算を行って第２のベクトルを生成する凸射影部と、第２のベクトルに対して、線形変換を転置した線形変換を行う第２の線形変換部と、第１の行列から、第２の線形変換部より線形変換された第２のベクトルを減算して第２の行列を生成する減算部と、を備え、第２の行列を用いて、第１の評価値と第２の評価値との和が最小になる点の位置の最適化を行う。【選択図】図４
2018082249.tif 000002
【特許請求の範囲】
【請求項１】
異なる位置に配置される複数の点と、前記複数の点同士の接続とによって形状を示す二次元データを単純化する二次元データ単純化装置であって、
前記二次元データの形状がより少ない直線の組み合わせによって示されるように前記複数の点を移動させて前記直線上に整列させる場合、移動前後の前記点の位置の乖離度合いを示す第１の評価値を算出する第１の評価関数を生成する第１の評価関数生成部と、
前記複数の点を前記直線上に整列させる場合、前記複数の点により形成される直線形状のなめらかさを示す第２の評価値を算出する第２の評価関数を生成する第２の評価関数生成部と、
前記第１の評価値と、前記第２の評価値との和が最小となる前記点の位置の最適化を行う最適化処理部と、
最適化された位置に前記点を移動させる点移動処理部と、
移動後の前記点同士の接続によって形成される辺の成す角度に基づいて前記点の中から不要な点を選別して除去する不要点除去部と、を備え、
前記最適化処理部は、
前記第１の評価関数及び前記第２の評価関数から導かれる第１の行列に対して予め定められる線形変換を行う第１の線形変換部と、
前記線形変換に基づいて得られる第１のベクトルと、予め定められるパラメータとに基づいて、凸射影演算を行って第２のベクトルを生成する凸射影部と、
前記第２のベクトルに対して、前記線形変換を転置した線形変換を行う第２の線形変換部と、
前記第１の行列から、前記第２の線形変換部より線形変換された前記第２のベクトルを減算して第２の行列を生成する減算部と、を備え、
前記第２の行列を用いて、前記第１の評価値と前記第２の評価値との和が最小になる前記点の位置の最適化を行う二次元データ単純化装置。
【請求項２】
前記凸射影部は、
前記第１のベクトルに基づいて、前記第１のベクトルの要素数より少ない要素数の第３のベクトルを生成するベクトル変換部と、
前記第３のベクトルと、前記パラメータとに基づく凸射影演算を行って第４のベクトルを生成する第１の凸射影部と、
前記第１のベクトルと、前記第４のベクトルとに基づく凸射影演算を行って第５のベクトルを生成する第２の凸射影部と、
前記第３のベクトルの要素の総和と、前記パラメータとの比較結果に基づいて、前記第１のベクトルまたは前記第５のベクトルのいずれかを前記第２のベクトルとして出力するスイッチと、
を備える、請求項１に記載の二次元データ単純化装置。
【請求項３】
前記第１の行列は、２×２の行列であり、
前記予め定められる線形変換は、
入力行列の列ベクトルの一方を直角に回転して他方の列ベクトルとの差分を算出する線形変換であり、
前記第１のベクトルは、
前記第１の線形変換部が前記第１の行列に前記線形変換を行って得られるベクトルに１／２を乗じたベクトルであり、
前記ベクトル変換部は、
前記第１のベクトルの要素を２つの組に分け、各々の組ごとのＬ２ノルムを算出し、算出した組ごとのＬ２ノルムを要素とする前記第３のベクトルを生成し、
前記第１の凸射影部は、
前記第３のベクトルに基づいて、前記パラメータを半径とするＬ１ノルム球への凸射影演算を行い第４のベクトルを生成し、
前記第２の凸射影部は、
前記第１のベクトルに基づいて、前記第４のベクトルを半径とするＬ２ノルム球への凸射影演算を行い第５のベクトルを生成する、請求項２に記載の二次元データ単純化装置。
【請求項４】
前記線形変換は、次式（１）に示される線形変換Ａであり、
【数１】
2018082249.tif 000045
前記第１のベクトルがベクトルｔ＝（ｔ１，ｔ２，ｔ３，ｔ４）である場合、前記第３のベクトルは、次式（２）によって算出されるｗ１，ｗ２を要素とするベクトルｗ＝（ｗ１，ｗ２）であり、
【数２】
2018082249.tif 000046
前記第３のベクトルｗに基づいて、前記パラメータであるλを半径とするＬ１ノルム球への凸射影を行って得られる第４のベクトルζ＝（ζ１，ζ２）は、次式（３）によって示され、
【数３】
2018082249.tif 000047
前記第１のベクトルｔに基づいて、前記第４のベクトルζ＝（ζ１，ζ２）を半径とするＬ２ノルム球への凸射影を行って得られる第５のベクトルｓ＝（ｓ１，ｓ２，ｓ３，ｓ４）は、前記第１のベクトルｔを２倍したベクトルをｖ＝（ｖ１，ｖ２，ｖ３，ｖ４）とした場合、次式（４）によって示され、
【数４】
2018082249.tif 000048
前記線形変換Ａを転置した線形変換ＡＴは、次式（５）によって示され、
【数５】
2018082249.tif 000049
第１の行列を行列Ｙとした場合、前記第２の行列は、次式（６）に示される行列Ｚである
【数６】
2018082249.tif 000050
請求項３に記載の二次元データ単純化装置。
【請求項５】
請求項１に記載の二次元データ単純化装置を二次元データ単純化部として備える画像符号化装置であって、
原画像データを、画像骨格情報と画像微細振動情報とに分ける分解部と、
前記画像骨格情報を符号化する第１の符号化部と、
前記画像微細振動情報からテクスチャの種類を示すテクスチャ情報と、当該テクスチャ情報に対応する領域情報とを検出する解析部と、
前記テクスチャ情報を符号化する第２の符号化部と、
前記領域情報を異なる位置に配置される複数の点と、前記複数の点同士の接続とによって形状を示す二次元データに変換する変換処理部と、
前記変換処理部が変換する前記二次元データが前記二次元データ単純化部によって単純化されることにより生成される単純化された二次元データを符号化する第３の符号化部と、
を備える画像符号化装置。
【請求項６】
請求項１に記載の二次元データ単純化装置によって単純化されて生成される単純化された二次元データを符号化した画像符号化装置から符号化後の単純化された二次元データを取得する取得部と、
取得された前記符号化後の単純化された二次元データを復号することによって単純化された二次元データを復元する二次元データ復号部と、
を備える画像復号装置。
【請求項７】
請求項５に記載の画像符号化装置によって符号化された符号化後の画像骨格情報と、符号化後のテクスチャ情報と、符号化後の単純化された二次元データと、を取得する取得部と、
取得された前記符号化後の画像骨格情報を復号することによって画像骨格情報を復元する第１の復号部と、
取得された前記符号化後のテクスチャ情報を復号することによってテクスチャ情報を復元する第２の復号部と、
取得された前記符号化後の単純化された二次元データを復号することによって単純化された二次元データを復元する第３の復号部と、
復号された単純化された二次元データに基づいて、前記領域情報を生成する領域情報生成部と、
生成される前記領域情報が示す領域と、当該領域の各々に対応する前記テクスチャ情報とを関連付けることにより前記画像微細振動情報を合成する合成部と、
合成される前記画像微細振動情報と、復号される前記画像骨格情報とを加算して復号画像データを生成する加算部と、
を備える画像復号装置。
【請求項８】
異なる位置に配置される複数の点と、前記複数の点同士の接続とによって形状を示す二次元データを単純化する二次元データ単純化装置によって単純化されて生成される単純化された二次元データを符号化する画像符号化方法であって、
前記二次元データの形状がより少ない直線の組み合わせによって示されるように前記複数の点を移動させて前記直線上に整列させる場合、移動前後の前記点の位置の乖離度合いを示す第１の評価値を算出する第１の評価関数を生成する第１の評価関数生成ステップと、
前記複数の点を前記直線上に整列させる場合、前記複数の点により形成される直線形状のなめらかさを示す第２の評価値を算出する第２の評価関数を生成する第２の評価関数生成ステップと、
前記第１の評価値と、前記第２の評価値との和が最小となる前記点の位置の最適化を行う最適化処理ステップと、
最適化された位置に前記点を移動させる点移動処理ステップと、
移動後の前記点同士の接続によって形成される辺の成す角度に基づいて前記点の中から不要な点を選別して除去することによって単純化された二次元データを生成する不要点除去ステップと、
前記不要点除去ステップにおいて生成された単純化された二次元データを符号化する符号化ステップと、
を有し、
前記最適化処理ステップが、前記第１の評価関数及び前記第２の評価関数から導かれる第１の行列に対して予め定められる線形変換を行う第１の線形変換ステップと、前記線形変換に基づいて得られる第１のベクトルと、予め定められるパラメータとに基づいて、凸射影演算を行って第２のベクトルを生成する凸射影ステップと、前記第２のベクトルに対して、前記線形変換を転置した線形変換を行う第２の線形変換ステップと、前記第１の行列から、前記第２の線形変換部より線形変換された前記第２のベクトルを減算して第２の行列を生成する減算ステップと、を有し、前記第２の行列を用いて、前記第１の評価値と前記第２の評価値との和が最小になる前記点の位置の最適化を行い、
前記不要点除去ステップにおいて、最適化された位置に前記点を移動させ、移動後の前記点同士の接続によって形成される辺の成す角度に基づいて前記点の中から不要な点を選別して除去する画像符号化方法。
【請求項９】
請求項５に記載の画像符号化装置によって符号化された符号化後の画像骨格情報と、符号化後のテクスチャ情報と、符号化後の単純化された二次元データと、を取得する取得ステップと、
取得された前記符号化後の画像骨格情報を復号することによって画像骨格情報を復元する第１の復号ステップと、
取得された前記符号化後のテクスチャ情報を復号することによってテクスチャ情報を復元する第２の復号ステップと、
取得された前記符号化後の単純化された二次元データを復号することによって単純化された二次元データを復元する第３の復号ステップと、
復号された単純化された二次元データに基づいて、前記領域情報を生成する領域情報生成ステップと、
生成される前記領域情報が示す領域と、当該領域の各々に対応する前記テクスチャ情報とを関連付けることにより前記画像微細振動情報を合成する合成ステップと、
合成される前記画像微細振動情報と、復号される前記画像骨格情報とを加算して復号画像データを生成する加算ステップと、
を有する画像復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二次元データ単純化装置、画像符号化装置、画像復号装置、画像符号化方法及び画像復号方法に関する。
【背景技術】
【０００２】
ネットワークや地理情報学、画像工学などの諸分野において、埋め込みグラフというデータ構造が存在する。埋め込みグラフとは、複数の頂点とその頂点同士を結ぶ辺の集合であるグラフと、その頂点位置を合わせて定義したものである。例えば、ネットワークでは、ネットワークノードを頂点、ネットワークリンクを辺に対応させてグラフを構成できる。このとき、ネットワークノードの物理的な位置や、ネットワークを可視化する際のノード座標を頂点位置に対応させると、埋め込みグラフを見出すことができる。また、地理情報学であれば、国境や県境、海岸線、湖岸線等の境界線データは一般に、埋め込みグラフとしてデータが保持されている。境界線上に密に頂点をプロットして辺を結ぶことで、境界線を表現している。また、画像工学分野であれば、形状や領域に関するデータの保持に埋め込みグラフが使用される。例えば、ベクター画像におけるオブジェクト形状、深度マップにおける深度境界線、自然画像の被写体形状やテクスチャ領域形状等のデータは、埋め込みグラフとして表現される。形状や領域の境界上に頂点をプロットすることで、境界線を辺により表現している。
【０００３】
以上で例示した埋め込みグラフにおいては、埋め込みグラフの形状をできるだけ保ちつつ、頂点数や辺数を可能な限り削減して単純化すること（以下、埋め込みグラフの単純化、あるいは単に単純化と呼ぶ）に大きなメリットがある。
【０００４】
ネットワークにおいては、頂点数、辺数が多いほど詳細なデータを表現できる一方で、一見してネットワーク構成の概要を掴むことが困難になり、加えてデータ量が膨大になるため描画に大きな負荷がかかる。このネットワークについての埋め込みグラフを単純化できれば、ネットワーク構成を視覚的に分かりやすく提示でき、頂点数、辺数を減らしてデータ圧縮し、描画の負荷を低減することが可能になる。地理情報学においては、境界線上に密に頂点をプロットすることで正確に境界線を表現するが、データ量は膨大になってしまう。境界線データを単純化することで、データ量を削減して伝送や蓄積が可能になる他、境界を簡略した視覚的に分かりやすい地理情報を生成することができる。また、画像工学においては、頂点数、辺数が多いほど形状や領域のデータを詳細に保持して正確に表現可能である一方で、データ量が膨大になり、伝送や蓄積に要する符号量が増えてしまう。この形状や領域を単純化できれば、表現の正確性を可能な限り保ちながら、頂点数、辺数を削減して符号量を削減できる。
【０００５】
折れ線グラフや多角形等、非常に簡単な埋め込みグラフを単純化する有効な手法として、Ｒａｍｅｒ−Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒ法（以下、ＲＤＰ法という。例えば、非特許文献１参照）がある。以下、折れ線分にＲＤＰ法を適用する場合のアルゴリズムを説明する。この手法では、（１）まず折れ線分の両端頂点を結んだ線分を初期の折れ線分とする。（２）現在の折れ線分と最も距離の離れた頂点を現在の折れ線分に順次加える。（３）最も離れた頂点との距離が予め定めた許容誤差ε（＞０）よりも小さくなった時点で処理を終了する。
【０００６】
図１７は、ＲＤＰ法の動作例を示している。図１７において、白丸及び破線は入力した埋め込みグラフの折れ線成分を示し、黒丸及び実線は単純化した埋め込みグラフの折れ線成分を示す。図１７（Ａ）は初期状態（状態ＳＴ０）である。初期状態では、折れ線分の端点を繋いだ線分を初期の折れ線分Ｅ１とする。次のステップで加える頂点は、折れ線分Ｅ１からもっとも離れた頂点Ｖ１である。図１７（Ｂ）に示すように、状態ＳＴ１では、頂点Ｖ１を折れ線成分Ｅ１に加えて、新しい折れ線成分Ｅ２とする。次のステップで加える頂点は、折れ線分Ｅ２からもっとも離れた頂点Ｖ２である。図１７（Ｃ）に示すように、状態ＳＴ２では、頂点Ｖ２を折れ線成分Ｅ２に加えて、新しい折れ線成分Ｅ３とする。次のステップで加える頂点は、折れ線分Ｅ３からもっとも離れた頂点Ｖ３である。図１７（Ｄ）に示すように、状態ＳＴ３では、頂点Ｖ３を折れ線成分Ｅ３に加えて、新しい折れ線成分Ｅ４とする。状態ＳＴ３では、全ての頂点が折れ線分Ｅ４から許容誤差以内の距離となり、ここで、単純化処理は終了となる。
【０００７】
多角形の場合は両端点の代わりに、多角形頂点から適切に２点を選んで初期の折れ線分と設定することで、折れ線分のＲＤＰ法を適用可能である。さらにＲＤＰ法では、使用者が指定した特定の頂点を、入力埋め込みグラフと同じ頂点位置で、必ず含むように単純化を行うことも可能である。初期の折れ線分作成時に指定頂点を加え、処理を開始すれば良い。
【０００８】
ＲＤＰ法は形状近似の精度の高さ、実装の容易さなどから最もよく使用される方法である。例えばコンピュータビジョン向けのコンピュータプログラムライブラリであるＯｐｅｎＣＶでは、被写体形状の単純化や輪郭の近似処理としてＲＤＰ法が採用されている。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】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）及び頂点の位置の情報を含む。データ構造の例としてＤ次元座標空間上に分布するＮ個の頂点を考えると、各頂点に「１」から「Ｎ」の整数の頂点ＩＤを任意に付与して、各頂点の座標値を頂点ＩＤの順に並べたＮ行Ｄ列行列をＶとすれば、上記頂点情報の要件を満たす。本実施形態では、この例に倣って、元の頂点情報ＶをＮ行Ｄ列行列として記述する。なお、Ｎ行Ｄ列行列のデータ構造以外に、等価に変換可能な別のデータ構造を用いても良い。Ｅは元の埋め込みグラフＧの辺情報で、どの頂点を接続して各辺を成しているかという情報を含む。辺情報Ｅのデータ構造の例としては、隣接リスト、隣接行列、接続行列、ラプラシアン行列、Ｔｕｔｔｅ行列等がある。これらは、互いに等価に変換できることから、いずれを用いても良い。
【００２８】
単純化された埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）において、Ｖ＊は単純化された埋め込みグラフＧ＊の頂点情報であり、Ｅ＊は単純化された埋め込みグラフＧ＊の辺情報である。単純化された埋め込みグラフＧ＊の頂点情報Ｖ＊、及び辺情報Ｅ＊のデータ構造は、上記の元の埋め込みグラフＧの頂点情報Ｖ及び辺情報Ｅと同様のデータ構造である。ただし、単純化された埋め込みグラフＧ＊は、元の埋め込みグラフＧに比べて頂点数や辺数は減少している。
【００２９】
トレードオフパラメータλは正の実数値であり、大きいほど単純化の度合いを強くし、埋め込みグラフの頂点数が減少するよう調整することができる。
【００３０】
図１に示すように、埋め込みグラフ単純化装置１は、埋め込みグラフ直線整列部１１と、不要頂点除去部１２とを備える。埋め込みグラフ直線整列部１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）と、トレードオフパラメータλとを入力して、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する。
【００３１】
埋め込みグラフＧ’の辺情報Ｅは、元の埋め込みグラフＧの辺情報Ｅと同一の情報である。頂点情報Ｖ’のデータ構造及び頂点ＩＤは、元の頂点情報Ｖと同一であり、頂点位置のみが頂点情報Ｖと異なる。また、埋め込みグラフ直線整列部１１は、元の埋め込みグラフＧよりも直線整列するように変形した埋め込みグラフＧ’を生成する。例えば、埋め込みグラフ直線整列部１１は、図１に示すように埋め込みグラフＧの各頂点の座標を微小に動かし、１つの直線上に多くの頂点が並ぶように局所的に線形に整列（以下、局所線形整列という）させていき、埋め込みグラフＧ’を生成する。また、埋め込みグラフ直線整列部１１は、当該変形の際、トレードオフパラメータλが大きいほど直線に整列する度合いを強くする。換言すると、トレードオフパラメータλが大きいほど、埋め込みグラフＧ’の形状が、より少ない数の直線で表されることになる。
【００３２】
不要頂点除去部１２は、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を入力して、単純化された埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）を出力する。直線整列された埋め込みグラフＧ’の多くの頂点では、接続する辺の成す角度が小さくなっている。そのため、不要頂点除去部１２は、当該角度が予め定めた閾値以下の頂点を選定して取り除く、すなわちデシメーションすることで単純化した埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）を生成する。例えば、図１では、直線整列された埋め込みグラフＧ’の黒色の点を不要な頂点として取り除き、白色の点で構成させる直線整列された埋め込みグラフＧ’を生成している例を示している。
【００３３】
図２は、図１に示す埋め込みグラフ直線整列部１１の詳細な構成を示すブロック図である。図２に示すように、埋め込みグラフ直線整列部１１は、直線整列のための凸最適化問題立式部１１１と、凸最適化問題求解部１１２と、頂点情報置換部１１３とを備える。
【００３４】
直線整列のための凸最適化問題立式部１１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）と、トレードオフパラメータλとを入力して、直線整列のための凸最適化問題を出力する。出力する凸最適化問題は、目的関数と制約条件を記述した数式であり、式（１）で示される。
【００３５】
【数１】
2018082249.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.
【００４３】
頂点情報置換部１１３は、直線整列された頂点情報Ｖ’と、元の埋め込みグラフＧ＝（Ｖ，Ｅ）とを入力して、元の頂点情報Ｖを直線整列された頂点情報Ｖ’に置き換え、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する。
【００４４】
図３は、図２に示した直線整列のための凸最適化問題立式部１１１の詳細な構成を示すブロック図である。図３に示すように、直線整列のための凸最適化問題立式部１１１は、頂点辺情報分解部１１１１と、頂点位置変化損失関数立式部１１１２と、直線整列正則化関数立式部１１１３と、乗算器１１１４と、加算器１１１５と、制約条件立式部１１１６と、凸最適化問題生成部１１１７とを備える。
【００４５】
頂点辺情報分解部１１１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力し、元の頂点情報Ｖと元の辺情報Ｅに分解して出力する。
【００４６】
頂点位置変化損失関数立式部１１１２は、元の頂点情報Ｖを入力して、頂点位置変化損失関数ｆを出力する。頂点位置変化損失関数ｆは、直線整列された埋め込みグラフの頂点情報を変数Ｕとしたときに、元の頂点情報Ｖと変数Ｕとがどれだけ乖離しているかを評価するコストである。頂点位置変化損失関数ｆは、変数Ｕと元の頂点情報Ｖとの絶対値残差や二乗残差を評価する。頂点位置変化損失関数ｆとしては、式（２）〜（４）に例示するような凸関数を用いることができる。
【００４７】
【数２】
2018082249.tif 000004
【００４８】
式（２）〜（４）において、ｖｎ，ｄ及びｕｎ，ｄは、それぞれ、頂点情報Ｖの行列や変数Ｕの行列のｎ行ｄ列成分であり、頂点ＩＤがｎである頂点情報の第ｄ軸成分の値を表す。なお、式（３）及び式（４）におけるｖｅｃは、行列の要素を列ベクトルに並べ替える関数である。
【００４９】
直線整列正則化関数立式部１１１３は、辺情報Ｅを入力して、各頂点に接続する辺の成す角度を評価する直線整列正則化関数を出力する。直線整列正則化関数は、式（５）に例示するようなものを用いることができる。
【００５０】
【数３】
2018082249.tif 000005
【００５１】
式（５）に示す関数は、直線整列された埋め込みグラフの頂点情報を変数Ｕとしたときに、変数Ｕを用いた埋め込みグラフ（Ｕ，Ｅ）が直線整列されている度合いを評価するコストである。このコストは、辺ベクトル生成線形写像Ｌｍ（ｍ＝１，…，Ｍ）と、辺ベクトル角評価関数ｇと、累積演算Σとで構成される。辺ベクトル生成線形写像Ｌｍ（ｍ＝１，…，Ｍ）は、直線整列された埋め込みグラフの頂点情報を示す変数Ｕから、次数（接続する辺の数）が２の頂点毎に接続する辺の大きさと向きを表すベクトル（辺ベクトル）を生成する操作を行う。辺ベクトル角評価関数ｇは、抽出した辺ベクトルの成す角度を核ノルムで評価する。累積演算Σは、これらの評価値を足し合わせる。以下に、この算出法を説明する。
【００５２】
まず、整数Ｍは、埋め込みグラフＧの頂点のうち、次数が２である頂点の個数であり、辺情報Ｅより算出する。そして、Ｍ個ある次数２の頂点に（ｍ＝１，…，Ｍ）の番号を付与し、その頂点ＩＤをｃｕｒｒ＿ｉｄ（ｍ）、隣接する２つの頂点の頂点ＩＤをそれぞれｐｒｅｖ＿ｉｄ（ｍ）、ｎｅｘｔ＿ｉｄ（ｍ）とする。
【００５３】
辺ベクトル生成線形写像Ｌｍ（ｍ＝１，…，Ｍ）は、（ｃｕｒｒ＿ｉｄ（ｍ），ｐｒｅｖ＿ｉｄ（ｍ））の辺ベクトルと、（ｃｕｒｒ＿ｉｄ（ｍ），ｎｅｘｔ＿ｉｄ（ｍ））の辺ベクトルとを算出し、算出されたこれらの辺ベクトルを２行Ｄ列の行列に並べて格納する操作である。この２行Ｄ列の行列を辺ベクトル行列Ｐｍと呼ぶことにする。
【００５４】
式で記述すると、辺ベクトル生成線形写像Ｌｍは、直線整列された埋め込みグラフの頂点情報を示す変数Ｕを入力して、式（６）により、辺ベクトル行列Ｐｍ＝ＬｍＵを出力する。
【００５５】
【数４】
2018082249.tif 000006
【００５６】
この辺ベクトル生成線形写像Ｌｍは、式（７）で示す２行Ｎ列の疎行列を変数Ｕの左から掛ける操作とも等しいため、辺ベクトル生成線形写像Ｌｍと式（７）の行列は同一のものであるとみなせる。
【００５７】
【数５】
2018082249.tif 000007
【００５８】
辺ベクトル角評価関数ｇは、２行Ｄ列の辺ベクトル行列Ｐｍに対し、各辺ベクトルの成す角の大きさを評価する。辺ベクトル角評価関数ｇには、式（８）や式（９）で例示するような凸関数を用いることができる。
【００５９】
【数６】
2018082249.tif 000008
【００６０】
式（８）及び式（９）において、σ１（Ｐｍ）とσ２（Ｐｍ）は、辺ベクトル行列Ｐｍの２つの特異値を表す。式（８）及び式（９）に示す凸関数は、２つの辺ベクトルの成す角度が小さいほど関数値が小さくなり、角度が大きいほど関数値が大きくなる。
【００６１】
乗算器１１１４は、式（５）の直線整列正則化関数とトレードオフパラメータλを乗算した関数を出力する。
【００６２】
加算器１１１５は、頂点位置変化損失関数ｆと乗算器１１１４が出力した関数を線形結合して、式（１）のｍｉｎｉｍｉｚｅの右側の目的関数を出力する。
【００６３】
制約条件立式部１１１６は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力し、式（１）のｓｕｂｊｅｃｔ  ｔｏの右側の制約条件式を出力する。制約条件式は、使用者が予め定めた凸制約であり、式（１０）のように幾つかの頂点情報を限定する制約や、式（１１）や式（１２）のように頂点情報の可動範囲を限定する制約などを課することができる。
【００６４】
【数７】
2018082249.tif 000009
【００６５】
式（１１）及び式（１２）において、ε（ｎ）は、使用者が予め定めた、頂点ＩＤがｎである頂点に対する可動範囲の最大値である。なお、これらの制約条件式（１０）〜（１２）のいくつかを組み合わせて制約条件式とすることもできる。また、制約条件を全く課さないという制約条件式を定めることもできる。
【００６６】
凸最適化問題生成部１１１７は、目的関数と制約条件式を入力して、直線整列のための凸最適化問題を生成する。すなわち、凸最適化問題生成部１１１７は、加算器１１１５から出力された目的関数の左側に最小化を表す「ｍｉｎｉｍｉｚｅ」を加え、制約条件立式部１１１６から出力された制約条件式の左側に制約を表す「ｓｕｂｊｅｃｔ  ｔｏ」を加えて、（１）式に示した凸最適化問題を出力する。
【００６７】
上記の辺ベクトル角評価関数ｇとして、式（８）の核型ノルム関数を適用することにより効果的に埋め込みグラフを直線整列できることが知られている。以下、辺ベクトル角評価関数ｇとして式（８）の核型ノルム関数が適用される場合の凸最適化問題求解部１１２について説明する。この場合、前述したＰＤＳ法を用いると、凸最適化問題求解部１１２において、式（１）に示す凸最適化問題の解を求めるために、次式（１３）に示されるような局所線形整列問題を解くアルゴリズムが適用される。
【００６８】
【数８】
2018082249.tif 000010
【００６９】
式（１３）において、太文字で示される行列Ｘは、前述した式（１）における変数Ｕに相当する。３つ目の演算式である次式（１４）において、括弧内の式（１５）の部分は、後述する行列Ｙとなる。すなわち、式（１４）は、行列Ｙに対して、２行Ｄ列の行列の特異値分解と、閾値処理と、２行Ｄ列の行列×Ｄ行Ｄ列の行列×Ｄ行Ｄ列の行列とを含む計算である核型ノルム関数の近接写像計算を適用し、当該計算を反復することを示している。
【００７０】
【数９】
2018082249.tif 000011
【００７１】
図４は、凸最適化問題求解部１１２に備えられる核型ノルム関数の近接写像高速計算部１１２２の構成を示す図である。図４に示すように、核型ノルム関数の近接写像高速計算部１１２２は、線形変換部１１２２１、乗算器１１２２２、Ｌ１，２ノルム球凸射影部１１２２３、転置部１１２２４、線形変換部１１２２５、減算器１１２２６を備える。核型ノルム関数の近接写像高速計算部１１２２において、入力行列は、２行２列の大きさに限定された上記の式（１５）に示す行列Ｙである。
【００７２】
線形変換部１１２２１は、入力行列Ｙと予め定められる線形変換Ａを入力し、ベクトルｖ＝Ａ（Ｙ）を出力する。ここで線形変換Ａは、行列の要素を列ベクトルに並べ替える関数をｖｅｃとして、式（１６）によって示される。
【００７３】
【数１０】
2018082249.tif 000012
【００７４】
乗算器１１２２２は， ベクトルｖの各要素に１／２をかけてｔ＝（１／２）ｖ出力する。Ｌ１，２ノルム球凸射影部１１２２３はベクトルｔとパラメータλを入力して、Ｌ１，２ノルム球λＢ１，２への凸射影ｕを、次式（１７）にしたがって算出する。ここで、Ｌ１，２ノルム球λＢ１，２は、次式（１８）によって定義される。また、パラメータλは、Ｌ１ノルム球λＢ１の半径となる。式（１７）及び式（１８）に示すように、Ｌ１，２ノルム球凸射影部１１２２３が出力するベクトルｕは、Ｌ１，２ノルム球λＢ１，２上のベクトルであって、ベクトルｔと最もユークリッド距離の近いベクトルとなる。
【００７５】
【数１１】
2018082249.tif 000013
【００７６】
転置部１１２２４は、線形変換Ａの転置ＡＴを出力する。ＡＴは、次式（１９）に示される線形変換を行う。式（１９）において、ｍａｔ２×２は、ベクトルの要素を２×２行列に並べ替える関数である。
【００７７】
【数１２】
2018082249.tif 000014
【００７８】
線形変換部１１２２５はベクトルｕと線形変換ＡＴを入力して、行列ＡＴｕを出力する。減算器１１２２６は、入力行列Ｙと行列ＡＴｕの差Ｚ＝Ｙ−ＡＴｕ、すなわち次式（２０）に示すように行列Ｚを算出する。行列Ｚが、核型ノルム関数の近接写像高速計算部１１２２が出力する出力行列になる。
【００７９】
【数１３】
2018082249.tif 000015
【００８０】
次に、図５を参照しつつ、上記の式（１７）に示すＬ１，２ノルム球λＢ１，２への凸射影を算出するＬ１，２ノルム球凸射影部１１２２３の構成について説明する。図５に示すように，Ｌ１，２ノルム球凸射影部１１２２３は，Ｌ２ノルム算出部１１２２３１、総和算出部１１２２３２、比較部１１２２３３、Ｌ１ノルム球凸射影部１１２２３４、Ｌ２ノルム球凸射影部１１２２３５、スイッチ１１２２３６を備える。
【００８１】
Ｌ２ノルム算出部１１２２３１は、入力ベクトルｔを入力し、入力ベクトルｔを（ｔ１，ｔ２）と、（ｔ３，ｔ４）の２つに分けて、次式（２１）に示すＬ２ノルム計算により、入力ベクトルｔよりも要素数の少ない、ベクトルｗ＝（ｗ１，ｗ２）を出力する。
【００８２】
【数１４】
2018082249.tif 000016
【００８３】
総和算出部１１２２３２は，ベクトルｗ＝（ｗ１，ｗ２）を入力してｗ１＋ｗ２を出力する。比較部１１２２３３は、総和算出部１１２２３２が出力したｗ１＋ｗ２とパラメータλを比較し、ｗ１＋ｗ２≦λならば出力のフラグをＯＮとし、ｗ１＋ｗ２＞λなら出力のフラグをＯＦＦにする。
【００８４】
Ｌ１ノルム球凸射影部１１２２３４は、ベクトルｗとパラメータλを入力して、次式（２２）により、Ｌ１ノルム球λＢ１への凸射影ζ＝（ζ１，ζ２）を算出する。ここで、Ｌ１ノルム球λＢ１は、次式（２３）によって定義される。つまり出力するベクトルζは、半径をパラメータλとするＬ１ノルム球λＢ１上のベクトルであって、ベクトルｗと最もユークリッド距離の近いベクトルである。
【００８５】
【数１５】
2018082249.tif 000017
【００８６】
凸射影ζ＝（ζ１，ζ２）は、具体的には、次式（２４）に示す場合分けを伴う計算によって算出される。
【００８７】
【数１６】
2018082249.tif 000018
【００８８】
Ｌ２ノルム球凸射影部１１２２３５は、ベクトルｔとベクトルζを入力し、次式（２５）により、Ｌ２ノルム球ζ１Ｂ２及びζ２Ｂ２への凸射影ｓ＝（ｓ１，ｓ２，ｓ３，ｓ４）を算出する。ここで、Ｌ２ノルム球ζ*Ｂ２（ここで、「*」には、１，２が入る）は、次式（２６）によって定義される。つまり、Ｌ２ノルム球凸射影部１１２２３５が出力するベクトルｓにおいて、（ｓ１，ｓ２）は、Ｌ１ノルム球λＢ１への凸射影であるζ１を半径とするＬ２ノルム球ζ１Ｂ２上のベクトルであって、ベクトル（ｔ１，ｔ２）と最もユークリッド距離の近いベクトルである。また、（ｓ３，ｓ４）は、Ｌ１ノルム球λＢ１への凸射影であるζ２を半径とするＬ２ノルム球ζ２Ｂ２上のベクトルであって、ベクトル（ｔ３，ｔ４）と最もユークリッド距離の近いベクトルである。
【００８９】
【数１７】
2018082249.tif 000019
【００９０】
【数１８】
2018082249.tif 000020
【００９１】
Ｌ２ノルム球ζ１Ｂ２及びζ２Ｂ２への凸射影ｓ＝（ｓ１，ｓ２，ｓ３，ｓ４）は、具体的には、次式（２７）によって算出される。
【００９２】
【数１９】
2018082249.tif 000021
【００９３】
スイッチ１１２２３６は、入力したフラグの値に応じて、出力ベクトルｕを切り替える。フラグがＯＮの場合、図示のように入力ベクトル側に連結してｕ＝ｔとし、フラグがＯＦＦの場合、他方に連結してｕ＝ｓとする。
【００９４】
（定理の証明）
上記の式（２０）に示される行列Ｚは、線形変換Ａの転置ＡＴとＬ１，２ノルム球λＢ１，２への凸射影ｕとの行列の積を算出した上で、当該積を行列Ｙから減算した行列である。この行列Ｚは、前述した２×２行列である行列Ｙの核型ノルム関数の近接写像となることが定理として知られている（以下、定理１という）。また、定理１を証明する前提として、２×２行列の核型ノルム｜｜Ｙ｜｜＊は、次式（２８）により算出できることを補題として証明する（以下、補題２という）。
【００９５】
【数２０】
2018082249.tif 000022
【００９６】
ただし、式（２８）において、｜｜・｜｜∞，２は、混合Ｌ∞，２ノルムであり、次式（２９）を満たす。
【００９７】
【数２１】
2018082249.tif 000023
【００９８】
２×２行列である行列Ｙの各列ベクトルをベクトルａ，ベクトルｂ、すなわちＹ＝［ａ，ｂ］とし、この２つのベクトルが成す角をθとする。このとき、ベクトルａとベクトルｂにおいて、次式（３０）に示す関係が成り立つ。
【００９９】
【数２２】
2018082249.tif 000024
【０１００】
核型ノルム｜｜Ｙ｜｜＊は、２つの特異値σ１（Ｙ），σ２（Ｙ）の和として定義され、次式（３１）のように示すことができる。
【０１０１】
【数２３】
2018082249.tif 000025
【０１０２】
式（３１）が成立することは、以下の４つの事実を組み合わせることにより、以下の通り確かめられる。すなわち、第１の事実として「（１）行列ＹＴＹが、次式（３２）により示されること」がある。
【０１０３】
【数２４】
2018082249.tif 000026
【０１０４】
第２の事実として、「（２）行列Ｙの特異値は、行列ＹＴＹの固有値の根号、すなわち式（３３）に示される値であること」がある。
【０１０５】
【数２５】
2018082249.tif 000027
【０１０６】
第３の事実として、「（３）行列ＹＴＹの固有値の総和であるλ１（ＹＴＹ）＋λ２（ＹＴＹ）は、行列ＹＴＹの対角和である次式（３４）であること」がある。
【０１０７】
【数２６】
2018082249.tif 000028
【０１０８】
第４の事実として、「（４）行列ＹＴＹの固有値の総和であるλ１（ＹＴＹ）＋λ２（ＹＴＹ）は、行列ＹＴＹの行列式である次式（３５）であること」がある。
【０１０９】
【数２７】
2018082249.tif 000029
【０１１０】
これらの４つの事実を組み合わせると、次式（３６）となる。
【０１１１】
【数２８】
2018082249.tif 000030
【０１１２】
式（３６）におけるｓｉｎ関数につく絶対値記号を外すために正負の符号を考慮し、更に、ｓｉｎθ＝−ｃｏｓ（θ＋π／２）＝ｃｏｓ（θ−π／２）であることに留意すると、次式（３７）のように変形することができる。
【０１１３】
【数２９】
2018082249.tif 000031
【０１１４】
式（３７）の式は、図６に示すように幾何学的に解釈することができる。まず、ベクトルｂを±π／２回転させて新しいベクトルｂ’とｂ’’を考える。新しいベクトルｂ’，ｂ’’は、長さが等しく｜｜ｂ｜｜２であり、ベクトルａと成す角がθ±π／２である。すなわち以下の式（３８），（３９），（４０）が成立する。
【０１１５】
【数３０】
2018082249.tif 000032
【０１１６】
式（３８），（３９），（４０）を式（３７）に代入して整理すると、次式（４１）が得られる。
【０１１７】
【数３１】
2018082249.tif 000033
【０１１８】
すなわち、図６に示す２つの破線の長さを大きい一方と核型ノルムは等しいということができる。また、ベクトルｂ’，ｂ’’は、それぞれ回転行列を用いて式（４２），（４３）の通り記述することができる。式（４２）は、ベクトルｂをπ／２回転させる回転行列であり、式（４３）は、ベクトルｂを−π／２回転させる回転行列である。
【０１１９】
【数３２】
2018082249.tif 000034
【０１２０】
式（４１）に、式（４２），（４３）を代入して整理すると式（４４）が得られる。すなわち、線形変換Ａは、行列の列ベクトルの一方、すなわちベクトルｂをπ／２と−π／２の直角に回転してもう一方の列ベクトルａとの差分を取る変換であるといえる。式（４４）により、式（２８）が成立することがいえる。
【０１２１】
【数３３】
2018082249.tif 000035
【０１２２】
これにより、上記の補題２が成立することがいえる。式（２８）が成立することにより、核ノルム関数の近接写像において次式（４５）が成立する。
【０１２３】
【数３４】
2018082249.tif 000036
【０１２４】
また、線形変換Ａは、ＡＴＡ＝２Ｉ，ＡＡＴ＝２Ｉ（ただし、Ｉは、恒等写像）という性質があり、また、下記の参考文献２の性質１０より、式（４６）のように変形することができる。
【０１２５】
【数３５】
2018082249.tif 000037
【０１２６】
［参考文献２］：P. L. Combettes and J.-Ch. Pesquet, “Proximal splitting methods in signal processsing”, Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp.185 - 212, Springer New York, 2011.
【０１２７】
さらに、参考文献３の式（６．８）によれば、ノルム関数｜｜・｜｜∞，２の近接写像である式（４７）と、双対なノルム｜｜・｜｜１，２のノルム球λＢ１，２＝｛ｘ｜｜｜ｘ｜｜１，２≦λ｝への凸射影である式（４８）との間には式（４９）に示す成分分解定理が成立する。
【０１２８】
【数３６】
2018082249.tif 000038
【０１２９】
［参考文献３］：N. Parikh and S. Boyd, “Proximal algorithms”, Foundations and Trends in optimization, vol.1, no.3, pp.127 - 239, 2014.
【０１３０】
式（４９）を式（４６）に代入して整理すると式（５０）となる。
【０１３１】
【数３７】
2018082249.tif 000039
【０１３２】
これにより、式（２０）の行列Ｚが、２×２行列である行列Ｙの核型ノルム関数の近接写像であるという（定理１）がいえることが分かる。
【０１３３】
上述したように、核型ノルム関数の近接写像について計算を行う場合、式（１４）に示す反復計算を行う必要がある。これに対して、上記の式（２０）に示す行列Ｚを適用することで、式（１３）に示したアルゴリズムは、次式（５１）とすることができる。
【０１３４】
【数３８】
2018082249.tif 000040
【０１３５】
式（５１）では、式（１４）に相当する計算が、次式（５２）に置き換えられている。
【０１３６】
【数３９】
2018082249.tif 000041
【０１３７】
凸最適化問題求解部１１２は、式（５１）に示すアルゴリズムを実行して、式（１）に示す凸最適化問題の解を求めることになり、アルゴリズムを実行する過程で、行列Ｙを核型ノルム関数の近接写像高速計算部１１２２に入力行列として与える。核型ノルム関数の近接写像高速計算部１１２２は、行列Ｙを、式（２０）により、行列Ｚに変換し、行列Ｚを出力行列として出力する。凸最適化問題求解部１１２は、得られた行列Ｚを用いて凸最適化問題の解を求める。これにより、式（１４）に示す反復計算を伴う核型ノルム関数の近接写像計算に替えて、式（５２）に示す、双対なノルム｜｜・｜｜１，２のノルム球λＢ１，２への凸射影演算、すなわち行列Ｙに対する線形変換と、加減乗除演算と、閾値処理によって、最適解を求めることが可能となる。
【０１３８】
次に、図７から図１１を参照しつつ、埋め込みグラフ単純化装置１による単純化処理を説明する。図７は、埋め込みグラフ単純化装置１による埋め込みグラフ単純化処理のフローチャートである。埋め込みグラフ直線整列部１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）と、トレードオフパラメータλとを入力して、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する（ステップＳ１１）。不要頂点除去部１２は、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を入力して、単純化された埋め込みグラフＧ＊＝（Ｖ＊，Ｅ＊）を出力する（ステップＳ１２）。
【０１３９】
図８は、図７のステップＳ１１において行われる埋め込みグラフ直線整列部１１による埋め込みグラフ直線整列処理を詳細化したフローチャートである。直線整列のための凸最適化問題立式部１１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）と、トレードオフパラメータλとを入力して、直線整列のための凸最適化問題を出力する（ステップＳ１１１）。凸最適化問題求解部１１２は、直線性列のための凸最適化問題を入力として、直線整列された頂点情報Ｖ’を出力する（ステップＳ１１２）。頂点情報置換部１１３は、直線整列された頂点情報Ｖ’と元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力して、直線整列された埋め込みグラフＧ’＝（Ｖ’，Ｅ）を出力する（ステップＳ１１３）。
【０１４０】
図９は、図８のステップＳ１１１において行われる直線整列のための凸最適化問題立式部１１１による直線整列のための凸最適化問題立式処理を詳細化したフローチャートである。頂点辺情報分解部１１１１は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力して、頂点情報Ｖと辺情報Ｅに分解して出力する（ステップＳ１１１１）。頂点位置変化損失関数立式部１１１２は、頂点情報Ｖを入力して、頂点位置変化損失関数ｆを出力する（ステップＳ１１１２）。直線整列正則化関数立式部１１１３は、辺情報Ｅを入力して、直線整列正則化関数を出力する（ステップＳ１１１３）。乗算器１１１４は、直線整列正則化関数とトレードオフパラメータλとを入力し、これら２つを乗算した関数を出力する（ステップＳ１１１４）。加算器１１１５は、頂点位置変化損失関数ｆと乗算器１１１４が出力した関数を線形結合して、目的関数を出力する（ステップＳ１１１５）。制約条件立式部１１１６は、元の埋め込みグラフＧ＝（Ｖ，Ｅ）を入力し、制約条件式を出力する（ステップＳ１１１６）。凸最適化問題生成部１１１７は、目的関数と制約条件式を入力して、直線整列のための凸最適化問題を生成して出力する（ステップＳ１１１７）。
【０１４１】
図１０は、核型ノルム関数の近接写像高速計算部１１２２による近接写像高速計算処理のフローチャートであり、当該処理は、図８のステップＳ１１２の凸最適化問題求解処理の過程において行われる処理である。線形変換部１１２２１は、入力行列Ｙと予め定められる線形変換Ａを入力して、ベクトルｖを出力する（ステップＳ１１２２１）。乗算器１１２２２はベクトルｖを入力して、ｔ＝（１／２）ｖを出力する（ステップＳ１１２２２）。Ｌ１，２ノルム球凸射影部１１２２３はベクトルｔとパラメータλを入力して，Ｌ１，２ノルム球λＢ１，２への凸射影ｕを出力する（ステップＳ１１２２３）。転置部１１２２４は，線形変換Ａを入力して，転置ＡＴを出力する（ステップＳ１１２２４）。線形変換部１１２２５はベクトルｕと線形変換ＡＴを入力して、行列ＡＴｕ出力する（ステップＳ１１２２５）。減算器１１２２６は、入力行列Ｙから行列ＡＴｕを減算して行列Ｚを算出する（ステップＳ１１２２６）。
【０１４２】
図１１は、図１０のステップＳ１１２２３において行われるＬ１，２ノルム球凸射影部１１２２３によるＬ１，２ノルム球凸射影処理を詳細化したフローチャートである。Ｌ２ノルム算出部１１２２３１は、入力ベクトルｔを入力し、ベクトルｗ＝（ｗ１，ｗ２）を出力する（ステップＳ１１２２３１）。総和算出部１１２２３２は、ｗ＝（ｗ１，ｗ２）の和ｗ１＋ｗ２を算出して比較部１１２２３３に出力する（ステップＳ１１２２３２）。Ｌ１ノルム球凸射影部１１２２３４は、ベクトルｗとパラメータλを入力して、Ｌ１ノルム球λＢ１への凸射影ベクトルζ＝（ζ１，ζ２）を算出する（ステップＳ１１２２３３）。Ｌ２ノルム球凸射影部１１２２３５は入力ベクトルｔとベクトルζを入力して、Ｌ２ノルム球ζ１Ｂ２，ζ２Ｂ２への凸射影ベクトルｓ＝（ｓ１，ｓ２，ｓ３，ｓ４）を算出する（ステップＳ１１２２３４）。
【０１４３】
比較部１１２２３３は、パラメータλがｗ１＋ｗ２以上であるか否かを判定する（ステップＳ１１２２３５）。比較部１１２２３３は、λがｗ１＋ｗ２以上と判定した場合（ステップＳ１１２２３５：Ｙｅｓ）、入力ベクトルｔを出力ベクトルｕにコピーして処理を完了する（ステップＳ１１２２３６）。一方、比較部１１２２３３は、λがｗ１＋ｗ２以上でないと判定した場合（ステップＳ１１２２３５：Ｎｏ）、Ｌ２ノルム球ζ１Ｂ２，ζ２Ｂ２への凸射影ベクトルｓをベクトルｕとして出力する（ステップＳ１１２２３７）。
【０１４４】
このように，図１１で示した処理手順に従ってＬ１，２ノルム球凸射影処理を行い、図１０に示した処理手順に従って核型ノルム関数の近接写像を計算することができる。なお、図１１において、ステップＳ１１２２３３及びＳ１１２２３４のＬ１ノルム球凸射影処理とＬ２ノルム球凸射影処理とを判定処理であるステップＳ１１２２３５の後、すなわち、Ｓ１１２３５の判定結果が「Ｎｏ」である場合にステップＳ１１２２３３及びＳ１１２２３４の処理を行ってベクトルｓを算出し、ステップＳ１１２２３７において、ベクトルｓをベクトルｕとして出力するようにしてもよい。
【０１４５】
上記の実施形態の構成により、埋め込みグラフ単純化装置１は、異なる位置に配置される複数の頂点と、複数の頂点同士の接続とによって形状を示すグラフを入力データとし、埋め込みグラフ直線整列部１１において、頂点位置変化損失関数立式部１１１２が、二次元データの形状がより少ない直線の組み合わせによって示されるように複数の頂点を移動させて直線上に整列させる場合、移動前後の頂点の位置の乖離度合いを示すコストを算出する頂点位置変化損失関数を生成する。また、直線整列正則化関数立式部１１１３が、複数の頂点を直線上に整列させる場合、複数の頂点により形成される直線形状のなめらかさを示すコストを算出する直線整列正則化関数を生成する。凸最適化問題生成部１１１７は、頂点位置変化損失関数と、直線整列正則化関数と、制約条件式とに基づいて、式（１）に示す直線整列のための凸最適化問題を生成する。凸最適化問題求解部１１２は、直線整列のための凸最適化問題を解く過程で用いるアルゴリズムに含まれる行列Ｙを、核型ノルム関数の近接写像高速計算部１１２２により行列Ｚに変換させ、行列Ｚにより、制約条件下で、頂点位置変化損失関数が算出するコストと、直線整列正則化関数が算出するコストとの和が最小となる頂点の位置を算出する。頂点情報置換部１１３は、算出された位置に頂点を動かす。不要頂点除去部１２は、移動後の頂点同士の接続によって形成される辺の成す角度に基づいて前記点の中から不要な点を選別して除去する。これにより、複雑な埋め込みグラフにおいても頂点や辺を削減可能で、頂点位置が元の埋め込みグラフの頂点位置に限定されないようにすることができる。また、核型ノルム関数の近接写像高速計算部１１２２が、行列Ｙを行列Ｚに変換することにより、以下に示すように演算時間の削減を図ることが可能となる。
【０１４６】
（核型ノルム関数の近接写像高速計算部による計算処理の効果）
上述した、核型ノルム関数の近接写像高速計算部１１２２による近接写像の計算処理の効果を説明するため、式（５１）への置き換えを行わずに、式（１３）に示した局所線形整列問題を解くアルゴリズムをそのまま実行する構成について説明する。図１２は、式（１３）に示した局所線形整列問題を解くアルゴリズムを行う際に適用される核型ノルム関数の近接写像計算部１１２３の構成を示すブロック図である。核型ノルム関数の近接写像計算部１１２３は、低ランク正則化法、すなわちＬＬＲ（Low-Rank Regularization Method）法に基づく処理を行う。このＬＬＲ法は、目的関数や制約式の選択でいくつかのバリエーションが存在するが、当該近接写像計算部１１２３では、核型ノルム関数の近接写像高速計算部１１２２と同様に、辺ベクトル角評価関数ｇとして式（８）の核型ノルムが適用されることを前提としている。核型ノルム関数の近接写像計算部１１２３は、特異値分解計算部１１２３１、ソフト縮退処理部１１２３２、行列再構成部１１２３３を備える。
【０１４７】
特異値分解計算部１１２３１は、行列Ｙを入力して、その特異値分解Ｓ，Ｔ，σを出力する。Ｓ，Ｔはそれぞれ特異ベクトルを並べた直交行列で、左直交行列、右直交行列という。また、σは、特異値を並べたベクトルである。関数ｄｉａｇを、ベクトル要素を対角に並べて対角行列を生成する関数としたとき、次式（５３）が成立する。
【０１４８】
【数４０】
2018082249.tif 000042
【０１４９】
ソフト縮退処理部１１２３２は、特異値ベクトルσとパラメータλを入力して、ソフト縮退した特異値ベクトルσ’を計算する。ベクトルσ’は、次式（５４）により算出される。
【０１５０】
【数４１】
2018082249.tif 000043
【０１５１】
行列再構成部１１２３３は、ソフト縮退した特異値σ’と、左直交行列Ｓ、右直交行列Ｔを入力し、再構成した行列Ｚを次式（５５）により出力する。
【０１５２】
【数４２】
2018082249.tif 000044
【０１５３】
図１３は核型ノルム関数の近接写像計算部による近接写像計算処理のフローチャートであり、当該処理も、図８のステップＳ１１２の凸最適化問題求解処理の過程において行われる処理である。特異値分解計算部１１２３１は、行列Ｙを入力して、特異値分解の計算を行い、左直交行列Ｓ、右直交行列Ｔ、特異値ベクトルσを出力する（ステップＳ１１２３１）。ソフト縮退処理部１１２３２は、特異値ベクトルσとパラメータλを入力して、ソフト縮退した特異値ベクトルσ’を算出する（ステップＳ１１２３２）。行列再構成部１１２３３は、ソフト縮退した特異値ベクトルσ’と、左直交行列Ｓ、右直交行列Ｔを入力し、再構成した行列Ｚを出力する（ステップＳ１１２３３）。
【０１５４】
前述したように、核型ノルム関数の近接写像計算部１１２３による近接写像の計算処理では、２行Ｄ列の行列の特異値分解と、閾値処理と、２行Ｄ列の行列×Ｄ行Ｄ列の行列×Ｄ行Ｄ列の行列とを含む計算である核型ノルム関数の近接写像計算が反復して行われることになる。この計算では、非常に多くの計算時間を要することになり、その主な原因は、多くの小型行列に対する特異値ソフト閾値処理を行うことにある。これに対して、本実施形態による図４の核型ノルム関数の近接写像高速計算部１１２２では、当該特異値ソフト閾値処理を混合Ｌ１，２ノルム球への凸射影演算に置き換えて等価な計算を行うことを可能としている。これにより、特異値分解の計算を行うことなく特異値ソフト閾値処理を行うことができるため、計算時間を削減することが可能となる。このように演算量を削減できている要因としては、数式上はループ向上を排除しているためである。
【０１５５】
また、式（１３）に示すような特異値分解を反復して行う処理は、埋め込みグラフを対象としたデータ処理においてよく用いられる処理であり、これらのいずれの処理においても、本実施形態による手法を適用して、反復処理による処理負荷を軽減することが可能となる。
【０１５６】
本実施形態による図４の核型ノルム関数の近接写像高速計算部１１２２を適用した場合と、核型ノルム関数の近接写像計算部１１２３を適用した場合の計算時間の違いを以下に示す。計算条件は、実装言語：Ｍａｔｌａｂ（Ｒ２０１２ｂ）、実行環境：ＯＳ（Operating System）：Ｗｉｎｄｏｗｓ７（６４ｂｉｔ）（なお、Ｗｉｎｄｏｗｓは、登録商標）、ＣＰＵ(Central Processing Unit)：Ｉｎｔｅｌ  Ｃｏｒｅｉ７  ３．４ＧＨｚ（なお、Ｉｎｔｅｌは、登録商標）、ＲＡＭ：１６．０ＧＢ、最適化問題の規模：頂点数３８１１、辺数３８２８である。トレードオフパラメータλ＝１．０の場合、核型ノルム関数の近接写像計算部１１２３における式（１４）の演算には、３２．６２５［秒］要していたのに対して、本実施形態の核型ノルム関数の近接写像高速計算部１１２２による式（５２）の演算では、０．３９４［秒］となり、大幅に計算時間が軽減できていることがわかる。
【０１５７】
（埋め込みグラフ単純化装置を適用した画像符号化システム）
図１４は、本実施形態による埋め込みグラフ単純化装置１を適用した画像符号化装置３０を含む画像符号化システム２０の構成を示すブロック図である。画像符号化システム２０は、画像符号化装置３０、通信ネットワーク４０、画像復号装置５０を備える。画像符号化装置３０は、Ｃａｒｔｏｏｎ−Ｔｅｘｔｕｒｅ成分分解部３１、Ｃａｒｔｏｏｎ成分画像符号化部３２、Ｔｅｘｔｕｒｅ成分解析部３３、種Ｔｅｘｔｕｒｅ画像符号化部３４、領域情報−グラフ変換部３５、グラフ形状単純化部３６、グラフ符号化部３７、通信部３９を備える。画像復号装置５０は、Ｃａｒｔｏｏｎ成分画像復号部５１、種Ｔｅｘｔｕｒｅ画像復号部５２、グラフ復号部５３、グラフ−領域情報変換部５４、Ｔｅｘｔｕｒｅ成分合成部５５、加算器５６、通信部５９を備える。
【０１５８】
画像符号化装置３０において、Ｃａｒｔｏｏｎ−Ｔｅｘｔｕｒｅ成分分解部３１は、外部から供給される原画像データを入力データとし、当該原画像データをＣａｒｔｏｏｎ成分画像データと、Ｔｅｘｔｕｒｅ成分画像データに分離する。また、Ｃａｒｔｏｏｎ−Ｔｅｘｔｕｒｅ成分分解部３１は、分離したＣａｒｔｏｏｎ成分画像データと、Ｔｅｘｔｕｒｅ成分画像データとをそれぞれＣａｔｒｏｏｎ成分画像符号化部３２とＴｅｘｔｕｒｅ成分解析部３３とに出力する。ここで、Ｃａｒｔｏｏｎ成分画像データとは、画像の色や形状等の画像骨格情報を有する画像成分のデータであり、Ｔｅｘｔｕｒｅ成分画像データとは、画像の微細振動情報を有する画像成分のデータである。Ｃａｒｔｏｏｎ成分画像データと、Ｔｅｘｔｕｒｅ成分画像データとは、ともに原画像データと同じ形式の画像データである。また、Ｃａｒｔｏｏｎ成分画像データとＴｅｘｔｕｒｅ成分画像データとを加算し、更に、予め定めたオフセット値を加算することで原画像データが得られるという性質を有する。
【０１５９】
Ｃａｒｔｏｏｎ成分画像符号化部３２は、Ｃａｒｔｏｏｎ−Ｔｅｘｔｕｒｅ成分分解部３１が出力するＣａｒｔｏｏｎ成分画像データを入力データとし、当該Ｃａｒｔｏｏｎ成分画像データを画像符号化してビットストリームデータに変換して通信部３９に出力する。画像符号化の手法としては、例えば、ＪＰＥＧ(Joint Photographic Experts Group)やＨＥＶＣ（High Efficiency Video Coding）等の符号化手法が適用される。
【０１６０】
Ｔｅｘｔｕｒｅ成分解析部３３は、Ｃａｒｔｏｏｎ−Ｔｅｘｔｕｒｅ成分分解部３１が出力するＴｅｘｔｕｒｅ成分画像データを入力データとし、当該Ｔｅｘｔｕｒｅ成分画像データを解析して、Ｔｅｘｔｕｒｅの種類ごとに、Ｔｅｘｔｕｒｅを十分に示す小さな矩形画像データ（以下、種Ｔｅｘｔｕｒｅ画像データという）とＴｅｘｔｕｒｅが広がる領域（以下、領域情報という）とを生成する。ここで、Ｔｅｘｔｕｒｅ成分画像データを解析するとは、Ｔｅｘｔｕｒｅ成分画像データの中に分布している複数種類のＴｅｘｔｕｒｅ、例えば、布、皮革、肌、金属等のＴｅｘｔｕｒｅの種類と、当該Ｔｅｘｔｕｒｅが存在する位置を検出することである。Ｔｅｘｔｕｒｅ成分解析部３３は、検出したＴｅｘｔｕｒｅの種類ごとに、検出した当該Ｔｅｘｔｕｒｅに基づいて種Ｔｅｘｔｕｒｅ画像データを生成して種Ｔｅｘｔｕｒｅ画像符号化部３４に出力する。また、Ｔｅｘｔｕｒｅ成分解析部３３は、検出したＴｅｘｔｕｒｅの種類ごとに、検出した当該Ｔｅｘｔｕｒｅの位置の情報から領域情報を生成して領域情報−グラフ変換部３５に出力する。
【０１６１】
種Ｔｅｘｔｕｒｅ画像符号化部３４は、Ｔｅｘｔｕｒｅ成分解析部３３が出力する種Ｔｅｘｔｕｒｅ画像データを入力データとし、画像符号化してビットストリームデータに変換して通信部３９に出力する。画像符号化の手法としては、例えば、ＪＰＥＧ(Joint Photographic Experts Group)やＨＥＶＣ（High Efficiency Video Coding）等の符号化手法が適用される。
【０１６２】
領域情報−グラフ変換部３５は、Ｔｅｘｔｕｒｅ成分解析部３３が出力する領域情報を入力データとし、当該領域情報に基づいて、領域情報の境界を辺にするようなグラフ、すなわち頂点と辺の集合体の情報に変換する処理を行い、グラフの情報をグラフ形状単純化部３６に出力する。
【０１６３】
グラフ形状単純化部３６は、埋め込みグラフ単純化装置１に相当する機能部である。グラフ形状単純化部３６は、領域情報−グラフ変換部３５が出力するグラフの情報を入力データとし、埋め込みグラフ単純化装置１が行う図７から図１１に示した処理を行い、単純化されたグラフ、すなわち頂点と辺の数が大幅に削減された情報を生成する。また、グラフ形状単純化部３６は、生成した単純化したグラフの情報をグラフ符号化部３７に出力する。
【０１６４】
グラフ符号化部３７は、グラフ形状単純化部３６が出力する単純化されたグラフの情報を入力データとし、当該単純化されたグラフの情報に対して符号化を行ってビットストリームデータに変換して通信部３９に出力する。グラフの情報の符号化の手法としては、例えば、ＤｅｆｌａｔｅやＬＺＳＳ(Lempel−Ziv−Storer−Szymanski)等の符号化手法が適用される。
【０１６５】
通信部３９は、Ｃａｒｔｏｏｎ成分画像符号化部３２、種Ｔｅｘｔｕｒｅ画像符号化部３４、グラフ符号化部３７が出力するビットストリームデータを通信ネットワーク４０を通じて画像復号装置５０に送信する。なお、Ｃａｒｔｏｏｎ成分画像符号化部３２が出力するビットストリームデータには、Ｃａｒｔｏｏｎ成分画像符号化部３２によって、Ｃａｒｔｏｏｎ成分画像復号部５１を宛先とする宛先情報が付加されている。また、種Ｔｅｘｔｕｒｅ画像符号化部３４が出力するビットストリームデータには、種Ｔｅｘｔｕｒｅ画像符号化部３４によって、種Ｔｅｘｔｕｒｅ画像復号部５２を宛先とする宛先情報が付加されている。また、グラフ符号化部３７が出力するビットストリームデータには、グラフ符号化部３７によって、グラフ復号部５３を宛先とする宛先情報が付加されている。
【０１６６】
画像復号装置５０において、通信部５９は、画像符号化装置３０の通信部３９が送信したビットストリームデータを通信ネットワーク４０から受信する。また、通信部５９は、受信したビットストリームデータを、当該ビットストリームデータに付加されている宛先情報に基づいて、当該宛先情報に対応するＣａｒｔｏｏｎ成分画像復号部５１、種Ｔｅｘｔｕｒｅ画像復号部５２、グラフ復号部５３に出力する。
【０１６７】
Ｃａｒｔｏｏｎ成分画像復号部５１は、通信部５９が出力するビットストリームデータを入力データとし、Ｃａｒｔｏｏｎ成分画像符号化部３２が行った符号化方式に対応する復号方式でビットストリームデータからＣａｒｔｏｏｎ成分画像データを復号する。また、Ｃａｒｔｏｏｎ成分画像復号部５１は、復号したＣａｒｔｏｏｎ成分画像データを加算器５６に出力する。
【０１６８】
種Ｔｅｘｔｕｒｅ画像復号部５２は、通信部５９が出力するビットストリームデータを入力データとし、種Ｔｅｘｔｕｒｅ画像符号化部３４が行った符号化方式に対応する復号方式でビットストリームデータから種Ｔｅｘｔｕｒｅ画像データを復号する。また、種Ｔｅｘｔｕｒｅ画像復号部５２は、復号した種Ｔｅｘｔｕｒｅ画像データをＴｅｘｔｕｒｅ成分合成部５５に出力する。
【０１６９】
グラフ復号部５３は、通信部５９が出力するビットストリームデータを入力データとし、グラフ符号化部３７が行った符号化方式に対応する復号方式で復号し、復号したグラフの情報をグラフ−領域情報変換部５４に出力する。
【０１７０】
グラフ−領域情報変換部５４は、グラフ復号部５３が出力する復号されたグラフの情報を入力データとし、復号されたグラフの辺を境界とするような領域情報に変換し、当該領域情報をＴｅｘｔｕｒｅ成分合成部５５に出力する。
【０１７１】
Ｔｅｘｔｕｒｅ成分合成部５５は、種Ｔｅｘｔｕｒｅ画像復号部５２が出力する種Ｔｅｘｔｕｒｅ画像データと、グラフ−領域情報変換部５４が出力する領域情報とを入力データとし、Ｔｅｘｔｕｒｅ成分画像データを生成して加算器５６に出力する。Ｔｅｘｔｕｒｅ成分画像データの生成は、Ｔｅｘｔｕｒｅの種類ごとに、領域情報によって示される領域内を埋めるように種Ｔｅｘｔｕｒｅ画像データを複製することにより行われる。
【０１７２】
加算器５６は、Ｃａｒｔｏｏｎ成分画像復号部５１が出力するＣａｒｔｏｏｎ成分画像データと、Ｔｅｘｔｕｒｅ成分合成部５５が出力するＴｅｘｔｕｒｅ成分画像データとを加算し、更に予め定められる予め定めたオフセット値を加算することで復号画像データを算出して出力する。
【０１７３】
（画像符号化の処理）
図１５は、画像符号化装置３０による画像符号化処理の流れを示すフローチャートである。Ｃａｒｔｏｏｎ−Ｔｅｘｔｕｒｅ成分分解部３１は、外部から原画像データが供給されると、当該原画像データを入力データとし、Ｃａｒｔｏｏｎ成分画像データと、Ｔｅｘｔｕｒｅ成分画像データに分離して出力する（ステップＳ３１）。
【０１７４】
Ｃａｒｔｏｏｎ成分画像符号化部３２は、Ｃａｒｔｏｏｎ−Ｔｅｘｔｕｒｅ成分分解部３１が出力するＣａｒｔｏｏｎ成分画像データを入力データとし、当該Ｃａｒｔｏｏｎ成分画像データを画像符号化してビットストリームデータに変換して通信部３９に出力する（ステップＳ３２）。
【０１７５】
Ｔｅｘｔｕｒｅ成分解析部３３は、Ｃａｒｔｏｏｎ−Ｔｅｘｔｕｒｅ成分分解部３１が出力するＴｅｘｔｕｒｅ成分画像データを入力データとし、当該Ｔｅｘｔｕｒｅ成分画像データを解析して、Ｔｅｘｔｕｒｅの種類ごとに、種Ｔｅｘｔｕｒｅ画像データと、領域情報とを生成して出力する（ステップＳ３３）。
【０１７６】
種Ｔｅｘｔｕｒｅ画像符号化部３４は、Ｔｅｘｔｕｒｅ成分解析部３３が出力する種Ｔｅｘｔｕｒｅ画像データを入力データとし、画像符号化してビットストリームデータに変換して通信部３９に出力する（ステップＳ３４）。
【０１７７】
領域情報−グラフ変換部３５は、Ｔｅｘｔｕｒｅ成分解析部３３が出力する領域情報を入力データとし、当該領域情報をグラフの情報に変換してグラフ形状単純化部３６に出力する（ステップＳ３５）。グラフ形状単純化部３６は、領域情報−グラフ変換部３５が出力するグラフの情報を入力データとし、埋め込みグラフ単純化装置１が行う図７から図１１に示した処理を行い、単純化されたグラフの情報を生成してグラフ符号化部３７に出力する（ステップＳ３６）。
【０１７８】
グラフ符号化部３７は、グラフ形状単純化部３６が出力する単純化されたグラフの情報を入力データとし、当該単純化されたグラフの情報に対して符号化を行ってビットストリームデータに変換して通信部３９に出力する（ステップＳ３７）。通信部３９は、Ｃａｒｔｏｏｎ成分画像符号化部３２、種Ｔｅｘｔｕｒｅ画像符号化部３４、及びグラフ符号化部３７が出力したビットストリームデータを通信ネットワーク４０を通じて画像復号装置５０に送信する（ステップＳ３８）。
【０１７９】
（画像復号の処理）
図１６は、画像復号装置５０が行う画像復号処理の流れを示すフローチャートである。通信部５９は、通信ネットワーク４０を通じて画像符号化装置３０からビットストリームデータを受信し、受信したビットストリームデータを、ビットストリームデータに付加されている宛先情報にしたがって、Ｃａｒｔｏｏｎ成分画像復号部５１、種Ｔｅｘｔｕｒｅ画像復号部５２、グラフ復号部５３に出力する（ステップＳ５０）。
【０１８０】
Ｃａｒｔｏｏｎ成分画像復号部５１は、受信したビットストリームデータを入力データとし、Ｃａｒｔｏｏｎ成分画像符号化部３２が行った符号化方式に対応する復号方式でビットストリームデータからＣａｒｔｏｏｎ成分画像データを復号して加算器５６に出力する（ステップＳ５１）。
【０１８１】
種Ｔｅｘｔｕｒｅ画像復号部５２は、受信したビットストリームデータを入力データとし、種Ｔｅｘｔｕｒｅ画像符号化部３４が行った符号化方式に対応する復号方式でビットストリームデータから種Ｔｅｘｔｕｒｅ画像データを復号してＴｅｘｔｕｒｅ成分合成部５５に出力する（ステップＳ５２）。
【０１８２】
グラフ復号部５３は、受信したビットストリームデータを入力データとし、グラフ符号化部３７が行った符号化方式に対応する復号方式で復号し、復号したグラフの情報をグラフ−領域情報変換部５４に出力する（ステップＳ５３）。グラフ−領域情報変換部５４は、グラフ復号部５３が出力する復号されたグラフの情報を入力データとし、復号されたグラフの辺を境界とするような領域情報に変換し、当該領域情報をＴｅｘｔｕｒｅ成分合成部５５に出力する（ステップＳ５４）。
【０１８３】
Ｔｅｘｔｕｒｅ成分合成部５５は、種Ｔｅｘｔｕｒｅ画像復号部５２が出力する種Ｔｅｘｔｕｒｅ画像データと、グラフ−領域情報変換部５４が出力する領域情報とを入力データとし、Ｔｅｘｔｕｒｅ成分画像データを生成して加算器５６に出力する（ステップＳ５５）。加算器５６は、Ｃａｒｔｏｏｎ成分画像復号部５１が出力するＣａｒｔｏｏｎ成分画像データと、Ｔｅｘｔｕｒｅ成分合成部５５が出力するＴｅｘｔｕｒｅ成分画像データとを加算し、更に予め定められる予め定めたオフセット値を加算することで復号画像データを算出して出力する（ステップＳ５６）。
【０１８４】
上記の画像符号化システム２０の構成により、画像符号化装置３０が、埋め込みグラフ単純化装置１の構成に相当するグラフ形状単純化部３６を備えることで、原画像データに含まれるテクスチャの領域形状を単純化することができる。そのため、画像符号化装置３０から画像復号装置５０に送信する情報量を削減することが可能となる。
【０１８５】
なお、埋め込みグラフ単純化装置１の全て又は一部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各部の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【０１８６】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【符号の説明】
【０１８７】
１…埋め込みグラフ単純化装置（二次元データ単純化装置、二次元データ単純化部），１１…埋め込みグラフ直線整列部，１２…不要頂点除去部（不要点除去部），１１１…直線整列のための凸最適化問題立式部，１１２…凸最適化問題求解部（最適化処理部），１１３…頂点情報置換部（点移動処理部），１１１１…頂点辺情報分解部，１１１２…頂点位置変化損失関数立式部（第１の評価関数生成部），１１１３…直線整列正則化関数立式部（第２の評価関数生成部），１１１４…乗算器，１１１５…凸最適化問題生成部，１１１６…制約条件立式部，１１２２…核型ノルム関数の近接写像高速計算部，１１２２１…線形変換部（第１の線形変換部），１１２２２…乗算器，１１２２３…Ｌ１，２ノルム球凸射影部（凸射影部），１１２２４…転置部，１１２２５…線形変換部（第２の線形変換部），１１２２６…減算器，１１２２３１…Ｌ２ノルム算出部（ベクトル変換部），１１２２３２…総和算出部，１１２２３３…比較部，１１２２３４…Ｌ１ノルム球凸射影部（第１の凸射影部），１１２２３５…Ｌ２ノルム球凸射影部（第２の凸射影部），１１２２３６…スイッチ，２０…画像符号化システム，３０…画像符号化装置，３１…Ｃａｒｔｏｏｎ−Ｔｅｘｔｕｒｅ成分分解部（分解部），３２…Ｃａｒｔｏｏｎ成分画像符号化部（第１の符号化部），３３…Ｔｅｘｔｕｒｅ成分解析部（解析部），３４…種Ｔｅｘｔｕｒｅ画像符号化部（第２の符号化部），３５…領域情報−グラフ変換部（変換処理部），３６…グラフ形状単純化部（二次元データ単純化部），３７…グラフ符号化部３７（第３の符号化部），３９…通信部，５０…画像復号装置，５１…Ｃａｒｔｏｏｎ成分画像復号部，５２…種Ｔｅｘｔｕｒｅ画像復号部，５３…グラフ復号部，５４…グラフ−領域情報変換部，５５…Ｔｅｘｔｕｒｅ成分合成部，５６…加算器，５９…通信部
【図１】
2018082249.tif 000051
【図２】
2018082249.tif 000052
【図３】
2018082249.tif 000053
【図４】
2018082249.tif 000054
【図５】
2018082249.tif 000055
【図６】
2018082249.tif 000056
【図７】
2018082249.tif 000057
【図８】
2018082249.tif 000058
【図９】
2018082249.tif 000059
【図１０】
2018082249.tif 000060
【図１１】
2018082249.tif 000061
【図１２】
2018082249.tif 000062
【図１３】
2018082249.tif 000063
【図１４】
2018082249.tif 000064
【図１５】
2018082249.tif 000065
【図１６】
2018082249.tif 000066
【図１７】
2018082249.tif 000067