(57)【要約】【課題】使用するメモリの記憶容量を削減でき、高速にメモリに記録およびアクセスすること。【解決手段】データ管理装置は、n+1次元の離散的な座標の第１のベクトル値pjを、n次元の離散的な座標の第２のベクトル値pj’で表現するベクトル表現変換手段と、第２のベクトル値pj’に基づいてメモリに記録およびアクセスする記録・アクセス手段と、を備える。【選択図】図２
2019121208.tif 000002
【特許請求の範囲】
【請求項１】
n+1次元の離散的な座標の第１のベクトル値pjを、n次元の離散的な座標の第２のベクトル値pj’で表現するベクトル表現変換手段と、
前記第２のベクトル値pj’に基づいてメモリに記録およびアクセスする記録・アクセス手段と、
を備えたデータ管理装置。
【請求項２】
前記ベクトル表現変換手段は、
設定した基底ベクトルに関連する、n行n+1列の行列である擬似逆行列A’を事前に計算する事前計算手段と、
前記擬似逆行列A’を用いて前記第１のベクトル値pjを第２のベクトル値pj’へ次元削減する次元削減手段と、
を備える請求項１に記載のデータ管理装置。
【請求項３】
前記事前計算手段は、
前記基底ベクトルを設定する基底ベクトル設定手段と、
前記設定した基底ベクトルから作成されたn+1行n列の行列Aから、前記擬似逆行列A’を計算する擬似逆行列計算手段と、
を備える請求項２に記載のデータ管理装置。
【請求項４】
前記記録・アクセス手段は、前記第２のベクトル値pjに固有の番号を割り当てる、請求項１乃至３のいずれか１つに記載のデータ管理装置。
【請求項５】
前記記録・アクセス手段は、前記固有の番号の割当てを並列に実行する、請求項４に記載のデータ管理装置。
【請求項６】
前記基底ベクトル設定手段は、
n+1次元の空間の超平面上の規則的な点の座標の次元を削減するための第１の基底ベクトルを設定し、
下記数１
【数１】
2019121208.tif 000010
で表現される前記第１の基底ベクトルの座標を、下記数２
【数２】
2019121208.tif 000011
で表現される第２の基底ベクトルに設定する、
請求項３に記載のデータ管理装置。
【請求項７】
情報処理装置によって、n+1次元の離散的な座標の第１のベクトル値pjを、n次元の離散的な座標の第２のベクトル値pj’で表現し、
前記第２のベクトル値pj’に基づいてメモリに記録およびアクセスする、
データ管理方法。
【請求項８】
前記表現することは、
設定した基底ベクトルに関連する、n行n+1列の行列である擬似逆行列A’を事前に計算し、
前記擬似逆行列A’を用いて前記第１のベクトル値pjを第２のベクトル値pj’へ次元削減する、
ことを含む、請求項７に記載のデータ管理方法。
【請求項９】
前記事前に計算することは、
前記基底ベクトルを設定し、
前記設定した基底ベクトルから作成されたn+1行n列の行列Aから、前記擬似逆行列A’を計算する、
ことを含む、請求項８に記載のデータ管理方法。
【請求項１０】
n+1次元の離散的な座標の第１のベクトル値pjを、n次元の離散的な座標の第２のベクトル値pj’で表現するベクトル表現変換手順と、
前記第２のベクトル値pj’に基づいてメモリに記録およびアクセスする記録・アクセス手順と、
をコンピュータに実行させるデータ管理用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ管理装置、データ管理方法、およびデータ管理用プログラムに関する。
【背景技術】
【０００２】
ノイズ除去などの処理として、バイラテラルフィルタ（bilateral filter）と呼ばれるフィルタ処理がたびたび利用される。ここで、バイラテラルフィルタとは、エッジ(輪郭)をぼかさずにノイズを除去する非線形フィルタの一種である。このフィルタ処理を高速化したPermutohedral Latticeが非特許文献１で提案されている。
【０００３】
図１は、この非特許文献１に開示されたPermutohedral Latticeを説明するための図である。
【０００４】
図１（例：２次元）に示すように、このPermutohedral Latticeでは処理の途中で、n次元上（図中(a)）の各点が持つ値をn+1次元の空間の超平面(図中(b))に投影している。超平面上には、n+1次元の座標で表現される点が規則的に存在する(図中(c))。そこで、Permutohedral Latticeでは、超平面上に投影された値に、距離に応じた値を加算することで、近傍のn+1個の点の値としている。この処理により、点の数を減らすことができる。したがって、Permutohedral Latticeでは、フィルタ処理を施す必要のある点が減るため、処理が高速になる。
【０００５】
この処理では、n+1次元上の各点が持つ値を記録する必要がある。たとえば、n+1＝３とし、3次元（x,y,z）の場合を想定する。そして、表現する座標の範囲を100とし、整数の座標の値のみを記録すると仮定する。この場合、メモリとして、1003=106個のデータ要素を記録可能な記憶容量を持つメモリが必要となる。
【０００６】
より具体的には、Permutohedral Latticeをカラー画像に適用するとする。この場合、画像の次元数である2次元と色の次元数である3次元とを扱うことが必要となる。このため、投影後には6次元となる。したがって、表現範囲を100とし、整数の座標のみ値を記録するとする場合、メモリとして、1006=1012個のデータ要素を記録可能な記憶容量を持つメモリが必要となる。
【０００７】
このように、一般的に、表現範囲をLとすると、メモリとして、L6個のデータ要素を記録可能な記憶容量を持つメモリが必要となる。このため、表現範囲Lが大きくなるにつれて、メモリとして、膨大な記憶容量を持つメモリが必要となる。
【０００８】
非特許文献１では、表現範囲内の座標を1次元の変数kで表現し、投影後に使用する座標が疎であることを利用し、その変数kを任意の値で割った余りhを用いて、メモリへ値の記録を行う。これにより、処理に必要なメモリの記憶容量を削減している。たとえば、3次元（x,y,z）の場合、表現範囲を100とし、任意の値を500とする。この場合、k=10000*x+100*y+z、h=k%500などとし、h番目のメモリ番地に値を記録する。ここで、%はモジュロ（modulo）を示す演算子である。詳述すると、この例では、hが変数kを500で割った余りに等しいことを示している。
【０００９】
しかしながら、この手法では、同じhを持つ異なる座標が複数存在することになる。したがって、h番目のメモリ番地に値を記録する際に、同じ座標からの値かどうかを区別し、異なる座標からの値の場合には他の場所のメモリ番地に値を記録することが必要となる。本例では、この処理を「記録区別処理」と呼ぶことにする。
【００１０】
しかしながら、この記録区別処理は各座標での処理が独立でないため、並列化が困難な処理となっている。したがって、記録区別処理に時間が必要となる。また、記録区別処理だけでなく、アクセスする場合にも同様の手順（処理）が必要になる。本例では、この処理を「アクセス区別処理」と呼ぶことにする。このように、Permutohedral Latticeでは、記録区別処理とアクセス区別処理とに、処理時間が必要となる。
【００１１】
上述したように、非特許文献１では、変数kを任意の値で割った余りhを用いることで、記録に必要なメモリの記憶容量を削減できるが、処理時間が長くなるという問題がある。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Andrew Adams、Jongmin Baek、Myers Abraham Davis著「Fast High-Dimensional Filtering Using the Permutohedral Lattice」Computer Graphics Forum. Blackwell Publishing Ltd出版、２０１０年、ｐｐ．７５３−７６２
【発明の概要】
【発明が解決しようとする課題】
【００１３】
上述したように、先行技術には次に述べるような課題がある。
【００１４】
第１の課題は、n+1次元の座標のベクトル値をメモリに直接記録する場合には、膨大な記憶容量を持つメモリが必要となることである。
【００１５】
第２の課題は、上述した非特許文献１に記載された手法では、変数kを任意の値で割った余りhを用いることで、メモリの記録に必要なデータ要素の数を削減できるが、並列処理が困難であるため、処理時間が長くなることである。
【００１６】
本発明の目的は、上述した第１および第２の課題を解決できるデータ管理装置、データ管理方法およびデータ管理用プログラムを提供することにある。
【課題を解決するための手段】
【００１７】
本発明の１つの態様として、データ管理装置は、n+1次元の離散的な座標の第１のベクトル値をn次元の離散的な座標の第２のベクトル値で表現するベクトル表現変換手段と；第２のベクトル値に基づいてメモリに記録およびアクセスする記録・アクセス手段と、を備える。
【００１８】
本発明の他の態様として、データ管理方法は、情報処理装置によって、n+1次元の離散的な座標の第１のベクトル値pjを、n次元の離散的な座標の第２のベクトル値pj’で表現し；前記第２のベクトル値pj’に基づいてメモリに記録およびアクセスする。
【００１９】
本発明の他の態様として、データ管理用プログラムは、n+1次元の離散的な座標の第１のベクトル値pjを、n次元の離散的な座標の第２のベクトル値pj’で表現するベクトル表現変換手順と；前記第２のベクトル値pj’に基づいてメモリに記録およびアクセスする記録・アクセス手順と；をコンピュータに実行させる。
【００２０】
さらに、係るプログラムを記録するコンピュータが読み取り可能な記録媒体によっても実現される。
【発明の効果】
【００２１】
本発明によれば、使用するメモリの記憶容量を削減でき、高速にメモリに記録およびアクセスできる。
【図面の簡単な説明】
【００２２】
【図１】非特許文献１に開示されたPermutohedral Latticeを説明するための図である。
【図２】本発明の一実施形態に係るデータ管理装置の構成を示すブロック図である。
【図３】図２に示したデータ管理装置に使用されるデータ処理装置の構成を示すブロック図である。
【図４】n＝５の場合の第１の基底ベクトルの組み合わせを示す図である。
【図５】n＝５の場合の第２の基底ベクトルの組み合わせを示す図である。
【図６】n＝５の場合の、設定した基底ベクトルを用いて作成される行列Aの一例を示す図である。
【図７】n=5次元のときに、次元削減部によって、n+1次元の座標を表す第１のベクトル値pjを、擬似逆行列A’を用いて、n次元の第２のベクトル値pj’で表現しなおした一例を示す図である。
【図８】n=5次元のときに、表現する範囲をL=30とした場合に、n+1次元の座標の行列Pにより表現するために必要なメモリの記憶容量と、n次元の座標の行列P’で表現した場合のメモリの記憶容量を示す図である。
【発明を実施するための形態】
【００２３】
次に、発明を実施するための形態について図面を参照して詳細に説明する。
【００２４】
[実施形態] 
[構成の説明]
図２を参照すると、本発明の一実施形態に係るデータ管理装置１００は、データを処理するデータ処理装置２００と、後述するプログラムやデータを記憶する記憶装置（メモリ）３００と、データを入力する入力装置４００と、データを出力する出力装置５００と、を備えている。
【００２５】
出力装置５００は、ＬＣＤ（Liquid Crystal Display）やＰＤＰ（Plasma Display Panel）などの表示装置やプリンタからなる。出力装置５００は、データ処理装置２００からの指示に応じて、操作メニューなどの各種情報を表示したり、最終結果を印字出力する機能を有する。
【００２６】
記憶装置３００は、ハードディスクやリードオンリメモリ（ＲＯＭ）およびランダムアクセスメモリ（ＲＡＭ）などのメモリからなる。記憶装置３００は、データ処理装置２００における各種処理に必要なデータ３１０やプログラム３２０を記憶する機能を有する。
【００２７】
データ処理装置２００は、ＭＰＵ（micro processing unit）などのマイクロプロセッサや中央処理装置（ＣＰＵ）からなる。データ処理装置２００は、記憶装置３００からプログラム３２０を読み込んで、プログラム３２０に従ってデータを処理する各種処理部を実現する機能を有する。
【００２８】
データ処理装置２００は、ベクトル表現変換部２１０と記録・アクセス部２２０とを備える。
【００２９】
ベクトル表現変換部２１０は、後述するように、n+1次元の離散的な座標の第１のベクトル値をn次元の離散的な座標の第２のベクトル値で表現する。記録・アクセス部２２０は、第２のベクトル値に基づいてメモリに記録およびアクセスする。
【００３０】
図３を参照すると、ベクトル表現変換部２１０は、基底ベクトル設定部２１２と擬似逆行列計算部２１４と次元削減部２１６とから成る。本実施形態では、ベクトル表現変換部２１０の次元削減部２１６は、n+1次元の座標を表す第１のベクトル値pjを、後述する擬似逆行列A’を用いて、n次元の第２のベクトル値pj’で表現しなおしている。これにより、次元を削減している。
【００３１】
なお、基底ベクトル設定部２１２と擬似逆行列計算部２１４は、メインの処理とは別に事前に擬似逆行列A’を一度計算しておくことが可能である。したがって、基底ベクトル設定部２１２と擬似逆行列計算部２１４との組み合わせは、事前計算部２１８として働く。次元削減部２１６は、各点の処理の独立性が高いため、並列処理が容易である。
【００３２】
[動作の説明]
次に、図３を参照して本実施形態の全体の動作について詳細に説明する。
【００３３】
基底ベクトル設定部２１２では、空間上の点群を表現するための基底ベクトルを設定する。取りえる座標が離散的に均等に配置されているとき、基底ベクトル設定部２１２は、その座標の次元数より少ない基底ベクトルを設定する。
【００３４】
詳述すると、n次元のPermutohedral Latticeの場合、n+1次元の空間の超平面上の値を記録する必要のある規則的な点の座標は、下記の数１で示す第１の基底ベクトルの組み合わせにより構成される（上記非特許文献１参照）。
【数１】
2019121208.tif 000003
【００３５】
図４は、n＝５の場合の第１の基底ベクトルの組み合わせを示している。
【００３６】
本手法では、この第１の基底ベクトルを、下記の数２で示す第２の基底ベクトルの組み合わせにより表現しなおす。
【数２】
2019121208.tif 000004
【００３７】
図５は、n＝５の場合の第２の基底ベクトルの組み合わせを示している。
【００３８】
Permutohedral Latticeの場合は、前述したように、n+1次元の空間の超平面上にのみ値が存在するので、n次元の座標で表現することが可能である。そのため、本実施形態では、基底ベクトル設定部２１２は、この中からn個のベクトルを基底ベクトルとして設定する。
【００３９】
擬似逆行列計算部２１４では、上記n次元の第２のベクトル値pj’を計算するために必要な、基底ベクトルにより作成される行列Aの擬似逆行列A’を計算する。擬似逆行列計算部２１４は、先ず、下記数３で示される、設定した基底ベクトルを用いて行列Aを作成する。
【数３】
2019121208.tif 000005
【００４０】
図６は、n＝５の場合の行列Aの一例を示している。図６に示されるように、行列Aは、n+1行n列の行列であり、正方行列ではない。このため、擬似逆行列計算部２１４は、下記数４に示すように、擬似逆行列A’を計算する。
【数４】
2019121208.tif 000006
【００４１】
数４において、AＴは行列Aの転置行列を表し、n行n+1列の行列である。したがって、AＴAはn行n列の行列となる。（AＴA）−１は、行列AＴAの逆行列を表す。これにより、擬似逆行列計算部２１４は、n行n+1列の擬似逆行列A’を得ることができる。
【００４２】
これら基底ベクトルの設定と擬似逆行列A’の計算は、次元数が決定していれば固定である。このため、前述したように、事前計算部２１８によって、事前に計算が可能である。たとえば、カラー画像に処理を行う場合には、次元数が5となり、上記の例に示すような計算を事前に行うことができる。
【００４３】
次元削減部２１６では、n+1次元の座標の第１のベクトル値を、擬似逆行列A’を用いてn次元の座標の第２のベクトル値に変換する。n+1次元の座標の第１のベクトル値をpjとするとき、次元削減部２１６は、下記の数５に示すように、n次元の座標の第２のベクトル値を新たにpj’で表す。
【数５】
2019121208.tif 000007
【００４４】
第１のベクトル値pjはn+1次元の座標の値であるため、n+1個の変数により表現される。一方、擬似逆行列A’がn行n+1列の行列であるため、第２のベクトル値pj’はn個の変数で表現され、各変数は整数となる。
【００４５】
表現する点の数をmとし、n+1次元の座標のすべての点を表現する行列Pを下記数６に示すように表すとする。
【数６】
2019121208.tif 000008
【００４６】
このとき、n+1次元の座標の行列Pは、下記数７に示すように、擬似逆行列A’によってn次元の座標の行列P’で表現される。
【数７】
2019121208.tif 000009
【００４７】
記録・アクセス部２２０では、第２のベクトル値pj’の座標に番号を割り当てることで、メモリ３００に記録・アクセスを行う。座標の各変数をucとし、表現する範囲をLとする。このとき、記録・アクセス部２２０は、第２のベクトル値pj’の座標に固有の番号k’=ΣLcucを割り当てる。たとえば3次元（x,y,z）の場合、表現範囲を100とする。このとき、記録・アクセス部２２０は、k=10000*x+100*y+zとして番号を割り当てる。この番号により、記録・アクセス部２２０は、メモリ３００に記録・アクセスを行う。
【００４８】
[効果の説明] 
次に、本実施形態の効果について説明する。
【００４９】
本実施形態において、基底ベクトル設定部２１２と擬似逆行列計算部２１４は、次元数が決定していれば固定であるため、事前に計算が可能である。たとえば、カラー画像に処理を行う場合には、次元数が5となり、例に示すような計算を事前に行うことができる。したがって、処理時間に影響を与えない。
【００５０】
次元削減部２１６では、擬似逆行列A’とn+1次元の座標の行列Pの演算が必要であるが、並列処理が容易なため、高速に処理することが可能である。また、n+1次元の座標の行列Pをn次元の座標の行列P’で表現しなおすことで、座標を表現するために必要な変数の数をn+1からnに削減することができる。さらに、n+1次元の座標の行列Pおよびn次元の座標の行列P’の取りうる値は整数であるため、第２の基底ベクトルにより表現しなおすことで、図７に示すように同じ座標を表現するために必要な値を小さくできる。
【００５１】
たとえばn=5次元のときに、図７に示されるように、（3,3,3,-3,-3,-3）は（-1,-1,-1,0,0）になり、(5,-1,-1,-1,-1,-1)は(-1,0,0,0,0)になるため、表現するための値は小さくなる。
【００５２】
このように、本実施形態では、表現範囲を小さくすることができるため、処理に必要なメモリの記憶容量を減らすことが可能である。
【００５３】
より具体的に説明すると、図８に示すように、たとえばn=5次元のときに表現する範囲をL=30とする。このとき、n+1次元の座標の行列Pにより表現するために必要なメモリの記憶容量は306個となる。一方、n次元の座標の行列P’で表現した場合には、メモリの記憶容量は65個となる。本手法により、処理に必要なメモリの記憶容量を、1/(nnL)にまで削減することができる。
【００５４】
尚、上記実施形態において、データ処理装置２００の各部は、ハードウェアとソフトウェアとの組み合わせを用いて実現可能である。ハードウェアとソフトウェアとを組み合わせた形態では、記憶装置３００にデータ管理用プログラム３２０が格納され、該データ管理用プログラム３２０に基づいてデータ処理装置２００のハードウェアを動作させることによって、各部を各種手段として実現する。また、該データ管理用プログラムは、記録媒体に記録されて頒布されても良い。当該記録媒体に記録されたデータ管理用プログラムは、有線、無線、又は記録媒体そのものを介して、メモリに読込まれ、処理部等を動作させる。尚、記録媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。
【００５５】
上記実施形態を別の表現で説明すれば、データ処理装置２００として動作させるコンピュータを、記憶装置３００に格納されたデータ管理用プログラム３２０に基づき、ベクトル表現変換部２１０（基底ベクトル設定部２１２、擬似逆行列計算部２１４、次元削減部２１６）、および記録・アクセス部２２０として動作させることで実現することが可能である。
【００５６】
尚、上述したように、本実施形態に係るデータ管理装置１００は、ソフトウェア関連発明であるとしても、使用するメモリの記憶容量を削減でき、かつ、高速にメモリにアクセスできるという効果を奏するのであるから、コンピュータ関連技術を改善（向上）するものであり、抽象概念には該当しないのは明らかである。
【実施例】
【００５７】
次に、本発明の実施例について説明する。
【００５８】
ノイズ除去などの処理に利用されるバイラテラルフィルタと呼ばれるフィルタ処理を高速化したPermutohedral Latticeの高速化に対して、本発明の実施例では、処理に時間を要していたメモリへの記録およびアクセス処理を並列化することで高速化することが可能である。
【００５９】
前述したように、関連技術では、n+1次元の座標の第１のベクトル値pjに対して、メモリを割り当てる必要がある。これに対して、本実施例では、このn+1次元の座標の第１のベクトル値pjを、擬似逆行列A’を使用して、n次元の座標の第２のベクトル値pj’へと変換する。
【００６０】
次に、本実施例では、表現する範囲をL’として、n次元の座標の第２のベクトル値pj’に対して固有の番号kj’=ΣLcuc,jを割り当てる。たとえば、n=5の場合、kj’=u0,j +Lu1,j +L2u2,j + L3u3,j + L4u4,jを割り当てる。
【００６１】
そして、本実施例では、kj’番目のメモリ番地に記録およびアクセスを行う。これらすべての処理は、各座標の第１のベクトル値pjに対して独立であるため、並列に処理が可能である。たとえば、座標の第１のベクトル値pjの数が1000個のとき、各処理を100個のスレッドで並列化処理した場合には、本実施例では、各スレッドが独立に処理するため、高速化が可能となる。
【００６２】
以上、本発明の実施形態および実施例を、図面を参照しつつ説明してきたが、当業者であれば、他の類似する実施形態および実施例を使用することができること、また、本発明から逸脱することなく適宜形態の変更又は追加を行うことができることに留意すべきである。
【産業上の利用可能性】
【００６３】
本発明によれば、画像処理を高速化することでデータセンタのサーバの削減や画像処理を用いた認証や検査の時間を短縮でき、また、高次元データのフィルタリングなどの処理の高速化などが可能となる。
【符号の説明】
【００６４】
１００    データ管理装置
２００    データ処理装置
２１０    ベクトル表現変換部
２１２    基底ベクトル設定部
２１４    擬似逆行列計算部
２１６    次元削減部
２１８    事前計算部
２２０    記録・アクセス部
３００    記憶装置（メモリ）
３１０    データ
３２０    プログラム（データ管理用プログラム）
４００    入力装置
５００    出力装置
【図１】
2019121208.tif 000012
【図２】
2019121208.tif 000013
【図３】
2019121208.tif 000014
【図４】
2019121208.tif 000015
【図５】
2019121208.tif 000016
【図６】
2019121208.tif 000017
【図７】
2019121208.tif 000018
【図８】
2019121208.tif 000019