(57)【要約】【課題】最適輸送問題において、精度が高く、かつ、解釈性の高い解を得ること。【解決手段】最適輸送理論を適用又は応用した問題を分析する分析装置であって、入力された第１のデータ系列と、第２のデータ系列と、前記第１のデータ系列の各データと前記第２のデータ系列の各データとの間の予め定められた変換コストを表すコスト行列とに基づいて、前記第１のデータ系列と前記第２のデータ系列との対応付けを表すカップリング行列のスパース性を決定するパラメータが含まれる所定の正則化項を有する所定の目的関数を設定する設定手段と、前記設定手段が設定した目的関数の解又は該解が得られた場合における前記カップリング行列を算出する分析手段と、を有し、前記目的関数は、前記カップリング行列にしたがって前記第１のデータ系列を前記第２のデータ系列に変換する際の前記コスト行列により特定されるコストを最小化するように設定される、ことを特徴とする。【選択図】図１
2019133323.tif 000002
【特許請求の範囲】
【請求項１】
最適輸送理論を適用又は応用した問題を分析する分析装置であって、
入力された第１のデータ系列と、第２のデータ系列と、前記第１のデータ系列の各データと前記第２のデータ系列の各データとの間の予め定められた変換コストを表すコスト行列とに基づいて、前記第１のデータ系列と前記第２のデータ系列との対応付けを表すカップリング行列のスパース性を決定するパラメータが含まれる所定の正則化項を有する所定の目的関数を設定する設定手段と、
前記設定手段が設定した目的関数の解又は該解が得られた場合における前記カップリング行列を算出する分析手段と、
を有し、
前記目的関数は、前記カップリング行列にしたがって前記第１のデータ系列を前記第２のデータ系列に変換する際の前記コスト行列により特定されるコストを最小化するように設定される、ことを特徴とする分析装置。
【請求項２】
前記正則化項は、負のエントロピー正則化項に対して前記パラメータを導入した第１の正則化項、Ｌ２ノルムの二乗に対して前記パラメータを導入した第２の正則化項、又はグループlassoに対して前記パラメータを導入した項が含まれる第３の正則化項のいずれかである、ことを特徴とする請求項１に記載の分析装置。
【請求項３】
前記第１のデータ系列は、色変換元の原画像に含まれる第１の色を表すデータの系列であり、
前記第２のデータ系列は、前記原画像を色変換するための参照画像に含まれる第２の色を表すデータの系列であり、
前記コストは、前記第１の色と前記第２の色との色の違いを表す距離であり、
前記分析手段は、
前記第１の色と、該第１の色の変換先となる前記第２の色との対応付けを表す前記カップリング行列を算出する、ことを特徴とする請求項１又は２に記載の分析装置。
【請求項４】
最適輸送理論を適用又は応用した問題を分析する分析装置が、
入力された第１のデータ系列と、第２のデータ系列と、前記第１のデータ系列の各データと前記第２のデータ系列の各データとの間の予め定められた変換コストを表すコスト行列とに基づいて、前記第１のデータ系列と前記第２のデータ系列との対応付けを表すカップリング行列のスパース性を決定するパラメータが含まれる所定の正則化項を有する所定の目的関数を設定する設定手順と、
前記設定手順が設定した目的関数の解又は該解が得られた場合における前記カップリング行列を算出する分析手順と、
を実行し、
前記目的関数は、前記カップリング行列にしたがって前記第１のデータ系列を前記第２のデータ系列に変換する際の前記コスト行列により特定されるコストを最小化するように設定される、ことを特徴とする分析方法。
【請求項５】
コンピュータを、請求項１乃至３の何れか一項に記載の分析装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分析装置、分析方法及びプログラムに関する。
【背景技術】
【０００２】
最適輸送理論（ＯＴ：Optimal Transport）とは、ｎ個の出発地点からｍ個の目的地点へ商品等を輸送する場合に、その輸送コストを最小化するような輸送経路を求める問題を数学的に定式化したものである。最適輸送理論は、商品等の輸送コストを最小化するような輸送経路を求める問題に限られず、機械学習の分野における様々な問題又はタスクにも応用することができる。例えば、或る画像（入力画像）の色調を、別の画像（参照画像）の色合いに応じて変換するといった画像の色変換の問題や、或るドメイン（学習用データセット）で学習したモデルを、別のドメイン（学習用データセットとは異なる分布に従うデータセット）での学習及び予測に利用可能なように変換を行うドメイン適応の問題等にも最適輸送理論を応用することができる。以降では、最適輸送理論を適用又は応用した問題を「最適輸送問題」とも表す。
【０００３】
最適輸送問題では、与えられたｍ次元ベクトルａとｎ次元ベクトルｂとに対して、Ｔａ＝ｂを満たすｍ×ｎのカップリング行列Ｔのうち、与えられたコスト行列Ｃの下で所定の目的関数を最小にするカップリング行列Ｔ又はこのときのａとｂとの間の距離を求める。なお、最適輸送問題によって、目的関数を最小にするカップリング行列Ｔを求める必要がある場合と、目的関数を最小にするａとｂとの間の距離を求める必要がある場合とがある。
【０００４】
ここで、非特許文献１及び２では、最適輸送問題の解を得るための計算を効率化すると共に、解の精度を向上させるために、エントロピー正則化が用いられている。これは、最小化したいコストを表す関数に対して所定の正則化項（エントロピー正則化項）を加えた関数を目的関数とするものである。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Marco Cuturi, Sinkhorn Distances: Lightspeed Computation of Optimal Transport. In Proc. of NIPS, pages 2292-2300. 2013.
【非特許文献２】Lenaic Chizat, Gabriel Peyre, Bernhard Schmitzer, and Francois-Xavier Vialard, SCALING ALGORITHMS FOR UNBALANCED OPTIMAL TRANSPORT PROBLEMS. arXiv preprint arXiv:1607.05816, 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
エントロピー正則化を用いる場合は、カップリング行列Ｔが密であるという条件（言い換えれば、スパース性が低いという条件）を課す必要がある。しかしながら、画像の色変換やドメイン適応等、最適輸送理論を応用する問題によっては、カップリング行列Ｔが密であるという条件が問題設定に適さず、適切な解（すなわち、精度が高い解）が得られない場合がある。また、スパース性が低いために、解の解釈が困難な場合がある。
【０００７】
本発明は、上記の点に鑑みてなされたもので、最適輸送問題において、精度が高く、かつ、解釈性の高い解を得ることを目的とする。
【課題を解決するための手段】
【０００８】
そこで、本発明の実施の形態は、最適輸送理論を適用又は応用した問題を分析する分析装置であって、入力された第１のデータ系列と、第２のデータ系列と、前記第１のデータ系列の各データと前記第２のデータ系列の各データとの間の予め定められた変換コストを表すコスト行列とに基づいて、前記第１のデータ系列と前記第２のデータ系列との対応付けを表すカップリング行列のスパース性を決定するパラメータが含まれる所定の正則化項を有する所定の目的関数を設定する設定手段と、前記設定手段が設定した目的関数の解又は該解が得られた場合における前記カップリング行列を算出する分析手段と、を有し、前記目的関数は、前記カップリング行列にしたがって前記第１のデータ系列を前記第２のデータ系列に変換する際の前記コスト行列により特定されるコストを最小化するように設定される、ことを特徴とする。
【発明の効果】
【０００９】
最適輸送問題において、精度が高く、かつ、解釈性の高い解を得ることができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態における分析装置の機能構成の一例を示す図（実施例１）である。
【図２】本発明の実施の形態における分析装置が実行する処理の一例を示すフローチャート（実施例１）である。
【図３】本発明の実施の形態における分析装置が実行する処理の一例を示すフローチャート（実施例２）である。
【図４】従来技術と本発明とを画像の色変換に応用した場合における色変換結果の比較例を示す図である。
【図５】従来技術と本発明とを画像の色変換に応用した場合におけるカップリング行列を視覚化したときの比較例を示す図である。
【図６】本発明の実施の形態における分析装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について図面を参照しながら説明する。本発明の実施の形態では、与えられたｍ次元ベクトルａとｎ次元ベクトルｂとに対して、Ｔａ＝ｂを満たすｍ×ｎのカップリング行列Ｔのうち、与えられたコスト行列Ｃの下で所定の目的関数を最小にするカップリング行列Ｔ又はこのときのａとｂとの間の距離を求める最適輸送問題を考える。
【００１２】
例えば、ｍは出発地点の数、ｎは目的地点の数、Ｔの（ｉ，ｊ）成分ｔｉｊは出発地点ｉから目的地点ｊへの輸送数、Ｃはｍ×ｎ行列であり、Ｃの（ｉ，ｊ）成分ｃｉｊは出発地点ｉから目的地点ｊへ商品等を輸送する場合の輸送コストである。ただし、最適輸送問題は、ｎ個の出発地点からｍ個の目的地点へ商品等を輸送する場合に限られず、上述したように、例えば、画像の色変換やドメイン適応等にも適用することができる。最適輸送問題は、一般に、何等かの基準（コスト）が最適となるような入力データ系列（例えば、ｍ個の出発地点のデータ系列）と出力データ系列（例えば、ｎ個の目的地点のデータ系列）との関係を分析する問題に適用することができる。なお、入力データ系列及び出力データ系列とは、１以上のデータ（要素）で構成されるベクトルで表される。
【００１３】
最適輸送問題の解は、線形計画法を用いて解くことができるが、以下の式１及び式２に示す制約を満たす必要がある。
【００１４】
【数１】
2019133323.tif 000003
【００１５】
【数２】
2019133323.tif 000004
ここで、１ｎは全ての成分が１であるｎ次元ベクトル、１ｍは全ての成分が１であるｍ次元ベクトルを表す。また、τは行列の転置を表す。
【００１６】
このとき、一般的に、最適輸送問題の目的関数は、以下の式３で表すことができる。
【００１７】
【数３】
2019133323.tif 000005
ここで、
【００１８】
【数４】
2019133323.tif 000006
である。また、〈・，・〉は内積を表す。
【００１９】
本発明の実施の形態における最適輸送問題では、上記の式３に示す目的関数に対して、スパース性を決定するパラメータγを含む正則化項Ωを加えた関数を目的関数する。すなわち、本発明の実施の形態における最適輸送問題では、以下の式４に示す関数ＯＴΩを目的関数として、この目的関数ＯＴΩの解を求める。
【００２０】
【数５】
2019133323.tif 000007
ここで、ｔｊはカップリング行列Ｔの第ｊ列をベクトル（ｍ次元ベクトル）で表したものである。
【００２１】
また、正則化項Ωとしては、以下の式５、式６又は式７に示す関数Ωの何れかを用いる。式５に示す正則化項Ωは、負のエントロピー正則化項に対して、スパース性を決定するパラメータγを導入した正則化項と言うこともできる。式６に示す正則化項Ωは、Ｌ２ノルムの二乗に対して、スパース性を決定するパラメータγを導入した正則化項と言うこともできる。式７に示す正則化項Ωは、式６に示す正則化項に対して、更に、Group-lassoにスパース性を決定するパラメータγを導入した正則化項と言うこともできる。そこで、式５に示す正則化項ΩをNegative entropy、式６に示す正則化項ΩをSquared 2-norm、式７に示す正則化項ΩをGroup-lassoとも称する。以降では、「Negative entropy」、「Squared 2-norm」及び「Group-lasso」と表した場合、それぞれ式５、式６及び式７に示す正則化項Ωを指すものとする。
【００２２】
【数６】
2019133323.tif 000008
【００２３】
【数７】
2019133323.tif 000009
【００２４】
【数８】
2019133323.tif 000010
ここで、μは予め決められたパラメータである。Ｇはｍ次元ベクトルｙの各要素を示す添え字ｉのうち、同一グループに属する要素（すなわち、同時に正則化される要素）を示す添え字ｉの集合である。ｙＧはＧに関するｙのサブベクトル（すなわち、ｙの各要素のうち、Ｇに属する添え字ｉが示す要素のみで構成されるベクトル）である。
【００２５】
上述したように、上記の式５乃至式７に示す正則化項Ωに含まれるγは、スパース性を決定するパラメータである。パラメータγは、その値が予め決められており、例えば、０より大きい任意の値を用いることができる。
【００２６】
本発明の実施の形態における最適輸送問題は、スパース性を決定するパラメータγが含まれる正則化項Ωを加えた関数を目的関数とし、この目的関数の解を求めることが特徴である。これにより、本発明の実施の形態における最適輸送問題では、カップリング行列Ｔのスパース性を保ったまま正則化の手法を導入することが可能となり、様々な問題に対して高い精度の解を効率的に得ることができる。また、カップリング行列Ｔのスパース性を高く保つことができるため、解釈性の高い解を得ることができる。
【００２７】
本発明の実施の形態における最適輸送問題をコンピュータ等で解く場合には、上記の式４に示す目的関数そのものを解くのではなく、これを双対問題に変換した式に基づいて算出する。
【００２８】
上記の式４に示す目的関数の双対問題は、以下の式８で表される。
【００２９】
【数９】
2019133323.tif 000011
ここで、
【００３０】
【数１０】
2019133323.tif 000012
である。
【００３１】
また、上記の式４に示す目的関数を、半双対問題と呼ばれる問題に変換した式に基づいて算出しても良い。半双対問題とは、上記の式８に示す双対問題の変数α又はβを削除した問題のことである。例えば、変数βを削除した場合における半双対問題は、以下の式９で表される。
【００３２】
【数１１】
2019133323.tif 000013
ここで、
【００３３】
【数１２】
2019133323.tif 000014
である。また、
【００３４】
【数１３】
2019133323.tif 000015
である。また、Δｍはｍ−１次元の単体（simplex）であり、
【００３５】
【数１４】
2019133323.tif 000016
である。更に、
【００３６】
【数１５】
2019133323.tif 000017
である。
【００３７】
ここで、δΩ（・）の閉形式（closed-form）は、正則化項ΩとしてNegative entropyを用いた場合、以下の式１０で表される。なお、閉形式とは、有限個の定数や変数、演算子、初等的又は良く知られた関数等によって表される式のことである。
【００３８】
【数１６】
2019133323.tif 000018
また、δΩ（・）の閉形式は、正則化項ΩとしてSquared 2-normを用いた場合、以下の式１１で表される。
【００３９】
【数１７】
2019133323.tif 000019
ここで、［ｘ］＋はｍａｘ（ｘ，０）である。
【００４０】
δΩ（・）の閉形式は、正則化項ΩとしてGroup-lassoを用いた場合、以下の式１２で表される。
【００４１】
【数１８】
2019133323.tif 000020
ここで、ｙ★はＧ上におけるベクトル分解であり、これをｙ★Ｇと表せば、
【００４２】
【数１９】
2019133323.tif 000021
である。
【００４３】
ｍａｘΩｊ（・）の閉形式は、正則化項ΩとしてNegative entropyを用いた場合、以下の式１３で表される。
【００４４】
【数２０】
2019133323.tif 000022
また、ｍａｘΩｊ（・）の閉形式は、正則化項ΩとしてSquared 2-normを用いた場合、以下の式１４で表される。
【００４５】
【数２１】
2019133323.tif 000023
なお、正則化項ΩとしてGroup-lassoを用いた場合、ｍａｘΩｊ（・）の閉形式は存在しない。
【００４６】
上記の式８及び式９の解ＯＴΩ（ａ，ｂ）は、上記の式４の解ＯＴΩ（ａ，ｂ）と等しい。また、ＯＴΩ（ａ，ｂ）は、ベクトルａとベクトルｂとの間の距離である。したがって、ベクトルａとベクトルｂとの間の最短距離を求めたい場合は、ＯＴΩ（ａ，ｂ）が最短距離となる。一方で、例えば最適輸送経路を求めたい場合はカップリング行列Ｔの値が必要となる。このカップリング行列Ｔの値は、後述するように、解ＯＴΩ（ａ，ｂ）を与えるα及びβから計算することができる。
【００４７】
（実施例１）
以降では、実施例１として、上記の式８又は式９により、解ＯＴΩ（ａ，ｂ）又は当該解が得られたときのカップリング行列Ｔを求める分析装置１０について説明する。
【００４８】
＜機能構成＞
まず、本発明の実施の形態の実施例１における分析装置１０の機能構成について、図１を参照しながら説明する。図１は、本発明の実施の形態における分析装置１０の機能構成の一例を示す図（実施例１）である。
【００４９】
図１に示すように、本発明の実施の形態の実施例１における分析装置１０は、入力部１０１と、初期化部１０２と、目的関数設定部１０３と、分析部１０４と、出力部１０５とを有する。これら各部は、分析装置１０にインストールされた１以上のプログラムがＣＰＵ（Central Processing Unit）等に実行させる処理により実現される。
【００５０】
入力部１０１は、分析対象とする入力データ系列ａと、出力データ系列ｂと、コスト行列Ｃとを入力する。ここで、ａは単体Δｍの要素であり、ｂは単体Δｎの要素である。したがって、入力データ系列ａ及び出力データ系列ｂはそれぞれ要素数ｍのベクトル及び要素数ｎのベクトルで表すことができるため、以降では、入力データ系列ａ及び出力データ系列ｂを、それぞれベクトルａ及びベクトルｂとも表す。なお、入力部１０１により入力されるデータ（ベクトルａ、ベクトルｂ及びコスト行列Ｃ）の入力元は限定されない。入力元としては、例えば、補助記憶装置や外部記録媒体、他のプログラム、ネットワークを介して接続される他の装置等が挙げられる。また、キーボードやマウス等の入力装置を用いてユーザにより作成されたデータが入力されても良い。
【００５１】
初期化部１０２は、入力部１０１が入力した入力データ系列ａの要素数ｍと出力データ系列ｂの要素数ｎとに応じて、ｍ×ｎのカップリング行列Ｔの各要素を初期化する。初期化部１０２は、カップリング行列Ｔの各要素をランダムな値に初期化しても良いし、最適輸送問題が適用される問題に応じた値に初期化しても良い。
【００５２】
目的関数設定部１０３は、入力部１０１により入力されたベクトルａと、ベクトルｂと、コスト行列Ｃとに基づいて、スパース性を決定するパラメータγを含む正則化項を有する目的関数を設定する。
【００５３】
分析部１０４は、目的関数設定部１０３により設定された目的関数を解いて、解ＯＴΩ（ａ，ｂ）又は当該解ＯＴΩ（ａ，ｂ）が得られたときのカップリング行列Ｔを算出する。
【００５４】
出力部１０５は、分析部１０４により得られた解ＯＴΩ（ａ，ｂ）又は当該解ＯＴΩ（ａ，ｂ）が得られたときのカップリング行列Ｔを出力する。なお、出力部１０５による出力先は限定されない。出力先としては、例えば、ディスプレイや補助記憶装置、外部記録媒体、他のプログラム、ネットワークを介して接続される他の装置等が挙げられる。
【００５５】
＜分析装置１０が実行する処理＞
以降では、本発明の実施の形態の実施例１における分析装置１０が実行する処理について、図２を参照しながら説明する。図２は、本発明の実施の形態における分析装置１０が実行する処理の一例を示すフローチャート（実施例１）である。
【００５６】
ステップＳ１０１：入力部１０１は、入力データ系列ａと、出力データ系列ｂと、コスト行列Ｃとを入力する。
【００５７】
ステップＳ１０２：初期化部１０２は、入力部１０１が入力した入力データ系列ａの要素数ｍと出力データ系列ｂの要素数ｎとに応じて、ｍ×ｎのカップリング行列Ｔの各要素を初期化する。
【００５８】
ステップＳ１０３：目的関数設定部１０３は、入力部１０１により入力されたベクトルａと、ベクトルｂと、コスト行列Ｃとに基づいて、スパース性を決定するパラメータγを含む正則化項を有する目的関数として、上記の式８又は式９に示す関数を設定する。なお、このとき、目的関数設定部１０３は、上記の式１及び式２を当該目的関数の制約に設定する。
【００５９】
ステップＳ１０４：分析部１０４は、目的関数設定部１０３により設定された目的関数を解いて、解ＯＴΩ（ａ，ｂ）又は当該解ＯＴΩ（ａ，ｂ）が得られたときのカップリング行列Ｔを算出する。なお、分析部１０４は、上記のステップＳ１０３で設定された目的関数（式８又は式９に示す関数）を、例えば、勾配法及びL-BFGS等を用いて解くことができる。
【００６０】
ベクトルａとベクトルｂとの間の距離を求めたい場合は、分析部１０４は、目的関数の解ＯＴΩ（ａ，ｂ）を算出する。
【００６１】
また、解ＯＴΩ（ａ，ｂ）が得られたときのカップリング行列Ｔを求めたい場合（すなわち、例えば、最適な輸送経路を求めたい場合等）は、分析部１０４は、目的関数の解ＯＴΩ（ａ，ｂ）を与えるα及びβ（以降、それぞれα★及びβ★とする。）を勾配法及びL-BFGS等により求めた上で、このα★及びβ★を用いて、カップリング行列Ｔの第ｊ列を表すベクトルｔ★ｊを算出する。
【００６２】
すなわち、上記の式８に示す関数が目的関数として設定された場合は、分析部１０４は、以下の式１５によりｔ★ｊを算出する。
【００６３】
【数２２】
2019133323.tif 000024
ここで、［ｎ］は集合｛１，・・・，ｎ｝である。また、ｃｊはコスト行列Ｃの第ｊ列を表すベクトル、β★ｊはβ★の第ｊ列を表すベクトルである。なお、∇は勾配を表す。
【００６４】
一方で、上記の式９に示す関数が目的関数として設定された場合は、分析部１０４は、以下の式１６によりｔ★ｊを算出する。
【００６５】
【数２３】
2019133323.tif 000025
ステップＳ１０５：出力部１０５は、分析部１０４により得られた解ＯＴΩ（ａ，ｂ）又は当該解ＯＴΩ（ａ，ｂ）が得られたときのカップリング行列Ｔを出力する。
【００６６】
（実施例２）
次に、実施例２として、上記の式８及び式９とは異なる目的関数を用いる場合について説明する。なお、分析装置１０の機能構成については実施例１と同様であるため、その説明を省略する。
【００６７】
＜分析装置１０が実行する処理＞
以降では、本発明の実施の形態の実施例２における分析装置１０が実行する処理について、図３を参照しながら説明する。図３は、本発明の実施の形態における分析装置１０が実行する処理の一例を示すフローチャート（実施例２）である。なお、図３のステップＳ１０１〜ステップＳ１０２及びステップＳ１０５は、図２と同様であるため、その説明を省略する。
【００６８】
ステップＳ２０１：目的関数設定部１０３は、入力部１０１により入力されたベクトルａと、ベクトルｂと、コスト行列Ｃとに基づいて、スパース性を決定するパラメータγを含む正則化項を有する目的関数として、以下の式１７又は式１８に示す関数を設定する。
【００６９】
【数２４】
2019133323.tif 000026
【００７０】
【数２５】
2019133323.tif 000027
ここで、Φ（・）が正則化項であり、この正則化項Φは、
【００７１】
【数２６】
2019133323.tif 000028
である。γは、実施例１と同様に、スパース性を決定するパラメータであり、例えば、０より大きい任意の値を用いることができる。このように、実施例２では、Ｔ１ｎとａとのＬ２ノルムの二乗に対してパラメータγを設定した項やＴτ１ｍとｂとのＬ２ノルムの二乗に対してパラメータγを設定した項を正則化項Φとして用いる。
【００７２】
ステップＳ２０２：分析部１０４は、目的関数設定部１０３により設定された目的関数（式１７又は式１８に示す関数）を解いて、解ＲＯＴΦ（ａ，ｂ）又は当該解ＲＯＴΦ（ａ，ｂ）が得られたときのカップリング行列Ｔを算出する。このとき、分析部１０４は、例えば、射影勾配法等を用いて、解ＲＯＴΦ（ａ，ｂ）又は当該解ＲＯＴΦ（ａ，ｂ）が得られたときのカップリング行列Ｔを算出することができる。
【００７３】
＜従来技術と本発明との比較例＞
ここで、本発明の実施の形態における分析装置１０を画像の色変換に適用した場合に、従来技術との比較について説明する。
【００７４】
画像の色変換とは、入力画像（この画像は「原画像」とも称される。以降では、原画像と表す。）の色調を、参照画像の色調に変換するものである。原画像に用いられている各色を並べたデータ系列を入力データ系列ａとし、参照画像に用いられている各色を並べたデータ系列を出力データ系列ｂとする。原画像で用いられている色数をｍ、参照画像に用いられている色数をｎとすれば、画像の色変換の問題は、ｍ色で彩色された画像をｎ色で彩色された画像に変換する問題と捉えることができる。
【００７５】
原画像で用いられている色を「入力色」とし、参照画像で用いられている色を「目的色」とすると、ｍ個の入力色の各々を、ｎ個の目的色の何れかにマッピングする（対応付ける）ことになる。このとき、各入力色と、当該入力色に対応する目的色（当該入力色とマッピングされる目的色）との色が近くなるようにする。この入力色と目的色との色の違い（この色の違いは「距離」と見做せる）をコストとしてコスト行列Ｃを与える。すると、ａをｂにマッピング（カップリング）するカップリング行列Ｔのうち、コストが最小となるカップリング行列Ｔを求めるという最適輸送問題に定式化できる。
【００７６】
このとき、図４（ａ）に示すＳｏｕｒｃｅを原画像、図４（ｂ）に示すＲｅｆｅｒｅｎｃｅを参照画像として、本発明の実施の形態における分析装置１０又は従来技術によってカップリング行列Ｔを求め、このカップリング行列Ｔにより原画像を色変換した結果を図４（ｃ）〜図４（ｈ）に示す。
【００７７】
図４（ｃ）に示すＵｎｒｅｇｕｌａｒｉｚｅｄは、正則化項を用いない従来技術により色変換した結果である。図４（ｄ）に示すＳｍｏｏｔｈｅｄ  ｓｅｍｉ−ｄｕａｌ（ｅｎｔ．）は、上記の式９に示す目的関数の正則化項として、従来技術のエントロピー正則化項を用いて求めたカップリング行列Ｔにより色変換した結果である。
【００７８】
一方で、図４（ｅ）に示すＳｍｏｏｔｈｅｄ  ｓｅｍｉ−ｄｕａｌ（Ｌ２２）は、入力色と目的色との色の違いをＬ２ノルムの二乗により計算したものをコストとして、上記の式９に示す目的関数を用いて、本発明の実施の形態における分析装置１０によって求めたカップリング行列Ｔにより色変換した結果である。図４（ｆ）に示すＲｅｌａｘｅｄ  ｐｒｉｍａｌ（Ｅｕｃｌ．）は、入力色と目的色との色の違いをユークリッド距離により計算したものをコストとして、上記の式１７に示す目的関数を用いて、本発明の実施の形態における分析装置１０によって求めたカップリング行列Ｔにより色変換した結果である。図４（ｇ）に示すＳｅｍｉ−ｒｅｌａｘｅｄ  ｐｒｉｍａｌ（Ｅｕｃｌ．）は、入力色と目的色との色の違いをユークリッド距離により計算したものをコストとして、上記の式１８に示す目的関数を用いて、本発明の実施の形態における分析装置１０によって求めたカップリング行列Ｔにより色変換した結果である。図４（ｈ）に示すＳｅｍｉ−ｒｅｌａｘｅｄ  ｐｒｉｍａｌ（ＫＬ）は、入力色と目的色との色の違いをＫＬ（Kullback-Leibler）距離により計算したものをコストとして、上記の式１８に示す目的関数を用いて、本発明の実施の形態における分析装置１０によって求めたカップリング行列Ｔにより色変換した結果である。
【００７９】
また、図４（ｅ）〜図４（ｈ）では、γの値を１０−４，１０−２，１０−１，１０，１０２，１０４としてそれぞれ求めたカップリング行列Ｔにより原画像をそれぞれ色変換した画像のうち、視覚的に最も良好な変換結果を採用した。
【００８０】
図４（ｃ）〜図４（ｈ）に示す結果から、本発明の実施の形態における分析装置１０は、正則化しない場合と比較して、画素間の境界が滑らかで自然な色変換が実現できていることがわかる。
【００８１】
次に、原画像の色変換に用いるカップリング行列Ｔを視覚化したものを図５に示す。図５（ａ）〜図５（ｄ）において、色が付与されている各四角形が、カップリング行列Ｔの各要素のうち０より大きな値を持つ要素である。また、横軸は入力色のヒストグラムで、あり、縦軸は目的色のヒストグラムである。なお、入力色のヒストグラムはベクトルａ、目的色のヒストグラムはベクトルｂに相当する。
【００８２】
色が付与されている四角形に対応する列の入力色が、当該四角形に対応する行の目的色に変換されることを意味する。なお、視認性を高めるため、入力色の色数と目的色の色数とをそれぞれｋ−ｍｅａｎｓ法によりクラスタリングし、３２種類にグループ化して図示した。
【００８３】
図５（ａ）に示すＵｎｒｅｇｕｌａｒｉｚｅｄは、正則化項を用いない従来技術により求めたカップリング行列Ｔを視覚化したものである。図５（ｂ）に示すＳｍｏｏｔｈｅｄ  ｄｕａｌ（ｅｎｔｒｏｐｙ）は、上記の式５に示す目的関数の正則化項として、従来技術のエントロピー正則化項を用いて求めたカップリング行列Ｔを視覚化したものである。図５（ｃ）に示すＳｍｏｏｔｈｅｄ  ｄｕａｌ（ｓｑ．  ２−ｎｏｒｍ）は、上記の式８に示す目的関数の正則化項として、上記の式６に示すSquared 2-normを用いて求めたカップリング行列Ｔを視覚化したものである。図５（ｄ）に示すＲｅｌａｘｅｄ  ｐｒｉｍａｌ（ｓｑ．Ｅｕｃｌｉｄｅａｎ  ｄｉｓｔ．）は、上記の式１７に示す目的関数を用いて求めたカップリングＴを視覚化したものである。なお、上記の式１７に示す目的関数の正則化項は、Ｌ２ノルム（ユークリッド距離）の二乗を用いた正則化項である。
【００８４】
また、図５（ａ）〜図５（ｄ）の各％は、カップリング行列Ｔの各要素のうち、零である要素の割合を表す。
【００８５】
図５（ａ）に示すように、正則化しない場合はカップリング行列Ｔのスパース性は９４％であり、スパース性が高すぎるために画素間の境界が目立ってしまったものと考えられる。
【００８６】
また、図５（ｂ）に示すように、エントロピー正則化項を用いた場合はカップリング行列Ｔのスパース性は０％であり、カップリング行列Ｔが密になっている。このため、入力色と目的色との間で色数を減らすことができず、非常に複雑な色変換が必要となってします。
【００８７】
一方で、図５（ｃ）〜図５（ｄ）に示すように、本発明の実施の形態における分析装置１０によって求めたカップリング行列Ｔのスパース性は９０％及び８７％であり、或る程度のスパース性が維持できている。このため、本発明の実施の形態における分析装置１０によれば、高い精度の解を得つつ、解釈性が高い解（画像の色変換の場合は、解釈性が高いとは、画素間の境界が滑らかで自然な視覚的に自然であることを意味する）を得ることができる。
【００８８】
＜ハードウェア構成＞
最後に、本発明の実施の形態における分析装置１０のハードウェア構成について、図６を参照しながら説明する。図６は、本発明の実施の形態における分析装置１０のハードウェア構成の一例を示す図である。
【００８９】
図６に示すように、本発明の実施の形態における分析装置１０は、入力装置２０１と、表示装置２０２と、外部Ｉ／Ｆ２０３と、ＲＡＭ（Random Access Memory）２０４と、ＲＯＭ（Read Only Memory）２０５と、ＣＰＵ２０６と、通信Ｉ／Ｆ２０７と、補助記憶装置２０８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【００９０】
入力装置２０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置２０２は、例えばディスプレイ等であり、分析装置１０の処理結果を表示する。なお、分析装置１０は、入力装置２０１及び表示装置２０２の少なくとも一方を有していなくても良い。
【００９１】
外部Ｉ／Ｆ２０３は、外部装置とのインタフェースである。外部装置には、記録媒体２０３ａ等がある。分析装置１０は、外部Ｉ／Ｆ２０３を介して、記録媒体２０３ａ等の読み取りや書き込みを行うことができる。記録媒体２０３ａには、分析装置１０が有する各機能を実現するプログラム等が記録されていても良い。
【００９２】
記録媒体２０３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【００９３】
ＲＡＭ２０４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ２０５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ２０５には、例えば、ＯＳ（Operating System）設定やネットワーク設定等が格納されている。
【００９４】
ＣＰＵ２０６は、ＲＯＭ２０５や補助記憶装置２０８等からプログラムやデータをＲＡＭ２０４上に読み出して処理を実行する演算装置である。
【００９５】
通信Ｉ／Ｆ２０７は、分析装置１０を通信ネットワークに接続するためのインタフェースである。分析装置１０が有する各機能を実現するプログラムは、通信Ｉ／Ｆ２０７を介して、所定のサーバ装置等から取得（ダウンロード）されても良い。
【００９６】
補助記憶装置２０８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置２０８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上において各種機能を実現するアプリケーションプログラム、分析装置１０が有する各機能を実現するプログラム等がある。
【００９７】
本発明の実施の形態における分析装置１０は、図６に示すハードウェア構成を有することにより、上述した各種処理を実現することができる。
【００９８】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【００９９】
１０        分析装置
１０１      入力部
１０２      初期化部
１０３      目的関数設定部
１０４      分析部
１０５      出力部
【図１】
2019133323.tif 000029
【図２】
2019133323.tif 000030
【図３】
2019133323.tif 000031
【図４】
2019133323.tif 000032
【図５】
2019133323.tif 000033
【図６】
2019133323.tif 000034