(57)【要約】【課題】直交ではない高次元の変換行列Ａに対し、リフティングアルゴリズムを適用可能とするための行列因数分解を実施できるデータ変換装置、データ変換方法及びプログラムを提供する。【解決手段】データ変換装置１００は、ｄｅｔＡ≠１、Ａ＝ＧＨｎＨｎ−１・・・Ｈ１＝ＧＦであるｎ次の正方行列Ａ及びＦの内に、成分（ｎ，ｎ）を含むｍ次（ｍ≧２）の第１の正方部分行列を定義し、このうち最も次数の低い行に含まれる成分に基づいて、Ｈｉに含まれる第１の成分を算出する。同様に、ｍ＋１次の第２の正方部分行列を定義し、このうち最も次数の低い行に含まれる成分と第１の成分とに基づいて、Ｈｉに含まれる第２の成分を算出する。第２の成分の算出処理を、第２の正方部分行列がｎ次となるまで繰り返す。データ変換装置１００は、Ａ及びＨ１の成分を用いて、Ｇの成分を算出するが、この際所定の変数変換を行って、ｎ変数ｎ拘束条件の連立一次方程式を解く。【選択図】図１
2014115917.tif 000002
【特許請求の範囲】
【請求項１】
ｄｅｔＡ≠１であるｎ次の正方行列Ａを、リフティングアルゴリズムを適用可能な形式に分解するデータ変換装置であって、
前記変換行列Ａは、ｎ次の正方行列であるＧ、Ｆ及びＨｉ（Ｈｎ、Ｈｎ−１、・・・Ｈ１）を含む式（１）の形に分解可能であり、
Ａ＝ＧＨｎＨｎ−１・・・Ｈ１＝ＧＦ  ・・・（１）
前記行列Ｇは、対角成分として１、最も高い次数の行の成分としてｇ１、ｇ２、・・・ｇｎ−１及び１、その他の成分として０を有する行列であり、
前記行列Ｈｉは、対角成分として１、ｎ−ｉ＋１次の行の成分としてｈｉ１、ｈｉ２、・・・ｈｉｎ−１及び１、その他の成分として０を有する行列であり、
前記行列Ａを格納する記憶部と、
前記記憶部から前記行列Ａを取得し、
前記行列Ａ及び前記行列Ｆの内に、成分（ｎ，ｎ）を含むｍ次（ｍ≧２）の第１の正方部分行列を定義し、
前記第１の正方部分行列のうち最も次数の低い行に含まれる成分に基づいて、前記行列Ｈｉに含まれる第１の成分を算出し、
前記変換行列Ａ及び前記行列Ｆの内に、成分（ｎ，ｎ）を含むｍ＋１次の第２の正方部分行列を定義し、
前記第２の正方部分行列のうち最も次数の低い行に含まれる成分と、前記第１の成分とに基づいて、前記行列Ｈｉに含まれる第２の成分を算出し、
前記第２の成分の算出処理を、前記第２の正方部分行列がｎ次となるまで繰り返すことにより、前記行列Ｈｉに含まれる全ての成分を算出し、
前記行列Ａ及び前記行列Ｈ１の成分を用いて、前記行列Ｇの成分を算出する演算処理部と、を有し、
前記演算処理部は、前記行列Ｇの成分を算出する際、所定の変数変換を行って、ｎ変数ｎ拘束条件の連立一次方程式を解くものである
データ変換装置。
【請求項２】
前記演算処理部は、前記変数変換を式（２）及び（３）により行うものである
請求項１記載のデータ変換装置。
【数１】
2014115917.tif 000017
【数２】
2014115917.tif 000018
【請求項３】
前記演算処理部は、前記行列Ｇ又は前記行列Ｆの少なくともいずれか一方を、前記記憶部に対し出力する
請求項１又は２記載のデータ変換装置。
【請求項４】
ｄｅｔＡ≠１であるｎ次の正方行列Ａを、リフティングアルゴリズムを適用可能な形式に分解するデータ変換方法であって、
前記変換行列Ａは、ｎ次の正方行列であるＧ、Ｆ及びＨｉ（Ｈｎ、Ｈｎ−１、・・・Ｈ１）を含む式（１）の形に分解可能であり、
Ａ＝ＧＨｎＨｎ−１・・・Ｈ１＝ＧＦ  ・・・（１）
前記行列Ｇは、対角成分として１、最も高い次数の行の成分としてｇ１、ｇ２、・・・ｇｎ−１及び１、その他の成分として０を有する行列であり、
前記行列Ｈｉは、対角成分として１、ｎ−ｉ＋１次の行の成分としてｈｉ１、ｈｉ２、・・・ｈｉｎ−１及び１、その他の成分として０を有する行列であり、
前記行列Ａを取得するステップと、
前記行列Ａ及び前記行列Ｆの内に、成分（ｎ，ｎ）を含むｍ次（ｍ≧２）の第１の正方部分行列を定義し、
前記第１の正方部分行列のうち最も次数の低い行に含まれる成分に基づいて、前記行列Ｈｉに含まれる第１の成分を算出するステップと、
前記変換行列Ａ及び前記行列Ｆの内に、成分（ｎ，ｎ）を含むｍ＋１次の第２の正方部分行列を定義し、
前記第２の正方部分行列のうち最も次数の低い行に含まれる成分と、前記第１の成分とに基づいて、前記行列Ｈｉに含まれる第２の成分を算出するステップと、
前記第２の成分の算出処理を、前記第２の正方部分行列がｎ次となるまで繰り返すことにより、前記行列Ｈｉに含まれる全ての成分を算出するステップと、
前記行列Ａ及び前記行列Ｈ１の成分を用いて、前記行列Ｇの成分を算出するステップと、を有し、
前記行列Ｇの成分を算出するステップは、前記行列Ｇの成分を算出する際、所定の変数変換を行って、ｎ変数ｎ拘束条件の連立一次方程式を解くものである
データ変換方法。
【請求項５】
請求項４記載のデータ変換方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ変換装置、データ変換方法及びプログラムに関し、特にリフティングアルゴリズムのための行列因数分解技術に関する。
【背景技術】
【０００２】
従来より、データ（典型的には画像、動画、音声など）の可逆圧縮、非直交変換（大きさの変化を伴う回転変換など）における整数可逆変換などを実施するための種々の手法が提案されている。
【０００３】
式（１）は直交変換を含め、多くのデータ変換処理でよく用いられる変換式である。
Ｙ＝ＡＸ      ・・・（１）
ここで、殆どの場合、変換行列Ａの係数は実数である。変換係数は、可逆変換が要求されるアプリケーションでは、高い計算精度が必要なため、無限語長であることが望ましい。しかし、実際の情報処理装置に上記変換式を実装する際には、無限語長の変換係数を用いることは事実上不可能である。そこで、変換係数の有限語長化や、丸め処理が用いられる。このとき、有限語長化や丸め処理による誤差を、順変換と逆変換との間で打ち消す作用を有するリフティングアルゴリズムが、実装において重要な役割を果たしている。
【０００４】
式（２）及び式（３）は、リフティングアルゴリズムの基本形式である。
【数１】
2014115917.tif 000003
【数２】
2014115917.tif 000004
ここで、ＢＢ−１＝Ｅより、係数ｂを丸めても誤差が順変換と逆変換との間で打ち消されることが分かる。そのため、上述の問題は変換行列Ａを式（２）の形式に行列因数分解する問題に帰着する。非特許文献１及び非特許文献２は、それぞれ違うアプローチで変換行列Ａの因数分解を行うものである。
【０００５】
非特許文献１は、整数可逆変換のために三角行列分解を利用する手法を開示している。また、非特許文献２は、逐次的な変数代入により、変換行列Ａの行列因数分解を実現する手法を開示している。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｐｅｎｇｗｅｉ  Ｈａｏ  他１名，Ｍａｔｒｉｘ  Ｆａｃｔｏｒｉｚａｔｉｏｎｓ  ｆｏｒ  Ｒｅｖｅｒｓｉｂｌｅ  Ｉｎｔｅｇｅｒ  Ｍａｐｐｉｎｇ，ＩＥＥＥ  ＴＲＡＮＳＡＣＴＩＯＮＳ  ＯＮ  ＳＩＧＮＡＬ  ＰＲＯＣＥＳＳＩＮＧ，２００１年１０月，ＶＯＬ．４９，ＮＯ．１０，第２３１４−２３２４頁
【非特許文献２】Ｍａｓａｈｉｒｏ  Ｉｗａｈａｓｈｉ  他１名，Ｔｈｒｅｅ  ｄｉｍｅｎｓｉｏｎａｌ  ｉｎｔｅｇｅｒ  ｒｏｔａｔｉｏｎ  ｔｒａｎｓｆｏｒｍ  ａｎｄ  ｉｍｐｒｏｖｅｍｅｎｔ  ｏｆ  ｉｔｓ  ｃｏｍｐａｔｉｂｉｌｉｔｙ，ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ，２００９年５月２４日，第２２０５−２２０８頁
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１記載の手法を適用できる変換行列Ａには、条件ｄｅｔＡ＝１を満たさなければならないという制約がある。また、非特許文献２記載の手法を適用できる変換行列Ａは直交行列（｜ｄｅｔＡ｜＝１）のみであり、４次元以上の高次元直交行列になると変数の数が多くなり変数代入作業が困難になる。
【０００８】
本発明は、このような問題点を解決するためになされたものであり、直交ではない（｜ｄｅｔＡ｜≠１）高次元の変換行列Ａに対し、整数可逆変換を可能ならしめる、すなわちリフティングアルゴリズムを適用可能とするための行列因数分解を実施できるデータ変換装置、データ変換方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明にかかるデータ変換装置は、ｄｅｔＡ≠１であるｎ次の正方行列Ａを、リフティングアルゴリズムを適用可能な形式に分解するデータ変換装置であって、前記変換行列Ａは、ｎ次の正方行列であるＧ、Ｆ及びＨｉ（Ｈｎ、Ｈｎ−１、・・・Ｈ１）を含む次式の形に分解可能であり、
Ａ＝ＧＨｎＨｎ−１・・・Ｈ１＝ＧＦ
前記行列Ｇは、対角成分として１、最も高い次数の行の成分としてｇ１、ｇ２、・・・ｇｎ−１及び１、その他の成分として０を有する行列であり、前記行列Ｈｉは、対角成分として１、ｎ−ｉ＋１次の行の成分としてｈｉ１、ｈｉ２、・・・ｈｉｎ−１及び１、その他の成分として０を有する行列であり、前記行列Ａを格納する記憶部と、前記記憶部から前記行列Ａを取得し、前記行列Ａ及び前記行列Ｆの内に、成分（ｎ，ｎ）を含むｍ次（ｍ≧２）の第１の正方部分行列を定義し、前記第１の正方部分行列のうち最も次数の低い行に含まれる成分に基づいて、前記行列Ｈｉに含まれる第１の成分を算出し、前記変換行列Ａ及び前記行列Ｆの内に、成分（ｎ，ｎ）を含むｍ＋１次の第２の正方部分行列を定義し、前記第２の正方部分行列のうち最も次数の低い行に含まれる成分と、前記第１の成分とに基づいて、前記行列Ｈｉに含まれる第２の成分を算出し、前記第２の成分の算出処理を、前記第２の正方部分行列がｎ次となるまで繰り返すことにより、前記行列Ｈｉに含まれる全ての成分を算出し、前記行列Ａ及び前記行列Ｈ１の成分を用いて、前記行列Ｇの成分を算出する演算処理部と、を有し、前記演算処理部は、前記行列Ｇの成分を算出する際、所定の変数変換を行って、ｎ変数ｎ拘束条件の連立一次方程式を解くものである。
【００１０】
本発明にかかるデータ変換方法は、  ｄｅｔＡ≠１であるｎ次の正方行列Ａを、リフティングアルゴリズムを適用可能な形式に分解するデータ変換方法であって、前記変換行列Ａは、ｎ次の正方行列であるＧ、Ｆ及びＨｉ（Ｈｎ、Ｈｎ−１、・・・Ｈ１）を含む次式の形に分解可能であり、
Ａ＝ＧＨｎＨｎ−１・・・Ｈ１＝ＧＦ
前記行列Ｇは、対角成分として１、最も高い次数の行の成分としてｇ１、ｇ２、・・・ｇｎ−１及び１、その他の成分として０を有する行列であり、前記行列Ｈｉは、対角成分として１、ｎ−ｉ＋１次の行の成分としてｈｉ１、ｈｉ２、・・・ｈｉｎ−１及び１、その他の成分として０を有する行列であり、前記行列Ａを取得するステップと、前記行列Ａ及び前記行列Ｆの内に、成分（ｎ，ｎ）を含むｍ次（ｍ≧２）の第１の正方部分行列を定義し、前記第１の正方部分行列のうち最も次数の低い行に含まれる成分に基づいて、前記行列Ｈｉに含まれる第１の成分を算出するステップと、前記変換行列Ａ及び前記行列Ｆの内に、成分（ｎ，ｎ）を含むｍ＋１次の第２の正方部分行列を定義し、前記第２の正方部分行列のうち最も次数の低い行に含まれる成分と、前記第１の成分とに基づいて、前記行列Ｈｉに含まれる第２の成分を算出するステップと、前記第２の成分の算出処理を、前記第２の正方部分行列がｎ次となるまで繰り返すことにより、前記行列Ｈｉに含まれる全ての成分を算出するステップと、前記行列Ａ及び前記行列Ｈ１の成分を用いて、前記行列Ｇの成分を算出するステップと、を有し、前記行列Ｇの成分を算出するステップは、前記行列Ｇの成分を算出する際、所定の変数変換を行って、ｎ変数ｎ拘束条件の連立一次方程式を解くものである。
【００１１】
本発明にかかるプログラムは、前記データ変換方法をコンピュータに実行させるためのプログラムである。
【発明の効果】
【００１２】
本発明により、直交ではない高次元の変換行列Ａに対し、リフティングアルゴリズムを適用可能とするための行列因数分解を実施できるデータ変換装置、データ変換方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態１にかかるデータ変換装置１００の構成を示す図である。
【図２】実施の形態１にかかるデータ変換装置１００の処理を示す図である。
【図３】実施の形態２にかかるデータ変換装置１００の処理を示す図である。
【発明を実施するための形態】
【００１４】
＜実施の形態１＞
実施の形態１では、４次の変換行列Ａを例として、変換行列Ａの行列因数分解を行う手法を開示する。
【００１５】
はじめに、図１のブロック図を用いて、実施の形態１に係るデータ変換装置１００の構成について説明する。
【００１６】
データ変換装置１００は、記憶部１０１、演算処理部１０２を有する。記憶部１００は、演算処理部１０２が演算処理を行うために必要なデータ、演算処理部１０２による演算結果としての出力データ、及び演算アルゴリズムを含むプログラム等を格納する。演算処理を行うために必要なデータとは、例えば変換対象の入力データ、変換行列Ａを含む。演算処理部１０２は、記憶部１０１から演算処理を行うために必要なデータと、プログラムとを読み出し、当該プログラムに従って、変換行列Ａを用いた入力データの変換処理を行う。また、演算処理部１０２は、当該処理の結果を記憶部１０１に記憶させる。
【００１７】
データ変換装置１００は、典型的にはパーソナルコンピュータ（ＰＣ）等のコンピュータであり、記憶部１０１としての揮発性メモリ又は不揮発性メモリ、演算処理部１０２としての中央処理装置（ＣＰＵ）を含む。
【００１８】
つづいて、図２のフローチャートを用いて、データ変換装置１００の動作について説明する。
【００１９】
Ｓ１０１：演算処理部１０２は、記憶部１０１から変換行列Ａを取得する。ここで、変換行列Ａは４次の行列であって、式（４）の形式であるものとする。
【数３】
2014115917.tif 000005
【００２０】
ここで、変換行列Ａは式（５）のように分解可能である。また、式（５）における行列Ｈ４、Ｈ３、Ｈ２、Ｈ１、Ｇ及びＦは、式（６）乃至（１１）のように表し得る。
Ａ＝ＧＨ４Ｈ３Ｈ２Ｈ１＝ＧＦ      ・・・（５）
【数４】
2014115917.tif 000006
【数５】
2014115917.tif 000007
【数６】
2014115917.tif 000008
【数７】
2014115917.tif 000009
【数８】
2014115917.tif 000010
なお、以下の説明において、行列成分（ｈ１１，ｈ１２，ｈ１３）を底辺成分、（ｈ２４，ｈ３４，ｈ４４）を右辺成分と称する。
【００２１】
式（５）乃至（１０）より、以下の式（１１）において、行列Ａ及び行列Ｆにおける斜線領域内の成分は同じ値を持つことが理解できよう。
【数９】
2014115917.tif 000011
【００２２】
また、式（５）乃至（１０）より、以下の連立方程式（式（１２）乃至（１７））が成り立つ。
ｈ２４＝ａ３４      ・・・（１２）
１＋ｈ２４ｈ１３＝ａ３３      ・・・（１３）
ｈ２２＋ｈ２４ｈ１２＝ａ３２      ・・・（１４）
ｈ３３ｈ２４＋ｈ３４＝ａ２４      ・・・（１５）
ｈ３３（１＋ｈ２４ｈ１３）＋ｈ３４ｈ１３＝ａ２３      ・・・（１６）
１＋ｈ３３（ｈ２２＋ｈ２４ｈ１２）＋ｈ３４ｈ１２＝ａ２２      ・・・（１７）
【００２３】
Ｓ１０２：演算処理部１０２は、行列成分（ｈ１３，ｈ２４）、（ｈ１２，ｈ３３，ｈ３４）、（ｈ１１，ｈ４２，ｈ４３，ｈ４４）を算出する（Ｈ行列の計算１）。
【００２４】
まず、演算処理部１０２は、式（１８）の斜線領域成分より、行列成分（ｈ１３，ｈ２４）を算出する。
【数１０】
2014115917.tif 000012
換言すれば、演算処理部１０２は、式（１２）及び（１３）からなる連立方程式を解くことにより、（ｈ１３，ｈ２４）を算出する。連立方程式を解く際、演算処理部１０２は、任意の公知の解法アルゴリズムを使用することができる。
【００２５】
つぎに、演算処理部１０２は、式（１９）の下線上にある成分を基に立てられる連立一次方程式の解と、先に求めた行列成分（ｈ１３，ｈ２４）とを用いて、行列成分（ｈ１２，ｈ２２，ｈ３３，ｈ３４）を算出する。
【数１１】
2014115917.tif 000013
具体的な（ｈ１２，ｈ２２，ｈ３３，ｈ３４）の算出手順は以下のとおりである。
【００２６】
演算処理部１０２は、先に求めた底辺成分ｈ１３と、式（１３）、（１５）及び（１６）より、（ｈ３３，ｈ３４）を算出する。
【００２７】
Ｓ１０２〜Ｓ１０５：つづいて、演算処理部１０２は、先に求めた（ｈ１３，ｈ３３，ｈ３４）と、式（１４）及び（１７）より、底辺成分ｈ１２を算出する。この際、右辺成分ｈ３４による除算が発生するが、このｈ３４の絶対値が小さい場合、より具体的には演算処理部１０２が除算において扱うことのできる最小値を下回る場合、除算エラーが発生し、底辺成分ｈ１２が発散してしまう。よって、かかる場合に限り、演算処理部１０２はＳ１０４の処理を行う（Ｓ１０３）。
【００２８】
この除算エラーは、（ａ３３，ａ３４）及び（ａ２３，ａ２４）に起因する。かかる除算エラーを回避するためには、ガウス消去法における部分的ピボット選択を行うことが考えられる。ここで、（ａ３３，ａ３４）は、上述のように底辺成分ｈ１３を求める際に使用するため、動かすことができない。そこで、（ａ２３，ａ２４）について、ガウス消去法における部分的ピボット選択を行うこととする。本実施例では、（ａ２１，ａ２２，ａ２３，ａ２４）と、（ａ１１，ａ１２，ａ１３，ａ１４）を入れ替える処理を行うことにより、部分的ピボット選択を実施する（Ｓ１０４）。かかる措置により、演算処理部１０２は、除算エラーを発生させることなく、底辺成分ｈ１２を算出することができる（Ｓ１０５）。
【００２９】
つづいて、演算処理部１０２は、先に求めた底辺成分ｈ１２と、式（１２）及び（１４）より、ｈ２２を算出する。
【００３０】
つぎに、演算処理部は、式（２０）の下線上にある成分を基に立てられる連立一次方程式の解と、先に求めた行列成分（ｈ１３，ｈ２４）及び（ｈ１２，ｈ２２，ｈ３３，ｈ３４）とを用いて、行列成分（ｈ１１，ｈ２１，ｈ３１，ｈ４２，ｈ４３，ｈ４４）を算出する。
【数１２】
2014115917.tif 000014
具体的な（ｈ１１，ｈ２１，ｈ３１，ｈ４２，ｈ４３，ｈ４４）の算出手順は以下のとおりである。
【００３１】
上記成分に関連して、式（１２）乃至（１７）と同様に設定された関係式、及び式（２０）下線上にある成分を用いた連立方程式が設定できる。演算処理部１０２は、この連立方程式を、Ｓ１０２〜Ｓ１０５として示した上述の手順と同様の手順により、連立方程式を解くことができる。これにより、演算処理部１０２は、（ｈ４２，ｈ４３，ｈ４４）及び底辺成分ｈ１１を算出する。
【００３２】
つづいて、演算処理部１０２は、先に求めた底辺成分ｈ１１と、上記関係式より、（ｈ２１，ｈ３１）を算出する。
【００３３】
Ｓ１０６：演算処理部１０２は、行列成分ｈ２２、（ｈ２１，ｈ３１）の算出を行う（Ｈ行列の計算２）。なお、ｈ２２、（ｈ２１，ｈ３１）の算出方法については既に述べたとおりである。
【００３４】
Ｓ１０７：演算処理部１０２は、行列Ｇを確定する、すなわち行列成分（ｇ１，ｇ２，ｇ３）を算出するための処理を行う。具体的には、式（２１）乃至（２４）より（ｇ１，ｇ２，ｇ３）を求める必要がある。なお、式（２１）乃至（２４）は、式（５）乃至（１０）より導出できる。
ａ１１ｇ１＋ａ２１ｇ２＋ａ３１ｇ３＋ｈ１１＝ａ４１      ・・・（２１）
ａ１２ｇ１＋ａ２２ｇ２＋ａ３２ｇ３＋ｈ１２＝ａ４２      ・・・（２２）
ａ１３ｇ１＋ａ２３ｇ２＋ａ３３ｇ３＋ｈ１３＝ａ４３      ・・・（２３）
ａ１４ｇ１＋ａ２４ｇ２＋ａ３４ｇ３＋１＝ａ４４      ・・・（２４）
【００３５】
式（２１）乃至（２４）は、３変数４拘束条件の過剰な連立一次方程式である。一般にｄｅｔＡ＝１の場合は４条件のうち３条件を使って（ｇ１，ｇ２，ｇ３）を算出し、最終的にすべての条件を満たすことができる。一方、ｄｅｔＡ≠１の場合はかかる手法は使用できず、最小二乗法による最適解の計算を行うことが一般的である。しかし、ここで得られる最適解は真の解と異なるため、誤差の影響により式（５）が成り立たないという問題が生じる。しかし、本発明では以下に示す変数変換によって、４変数４制約条件の線型方程式を立てることが可能になり、（ｇ１，ｇ２，ｇ３）の真の解を求めることができる。
【００３６】
すなわち、演算処理部１０２は、まず式（２５）により変数変換を行い、ついで式（２６）に示す４変数４拘束条件の連立一次方程式を解くことで、（ｇ１，ｇ２，ｇ３）を算出する。
【数１３】
2014115917.tif 000015
【数１４】
2014115917.tif 000016
【００３７】
最後に、演算処理部１０２は、行列Ｇ、行列Ｆを、記憶部１０１に対して出力し、処理を終了する。
【００３８】
本実施の形態では、４次元の変換行列Ａについて行列因数分解を行う例を示したが、上記処理手順を変換行列の次元数に応じてループ化すれば、５次元以上の高次元変換行列の因数分解も可能である。すなわち、高次元の変換行列でもリフティングアルゴリズムによる整数可逆変換が可能になる。
【００３９】
本実施の形態によれば、ｄｅｔＡ≠１の高次元変換行列Ａを、リフティングアルゴリズムを適用可能な形式に因数分解出来る。そのため、例えば大きさの変化を伴う回転変換、アフィン変換などの整数可逆変換が可能になる。特に大きさの変化を伴う回転変換は、可逆データ圧縮において重要な技術である。
【００４０】
＜実施の形態２＞
実施の形態２では、上述のデータ変換装置１００を、ベクトル回転に適用した例を示す。従来の可逆データ圧縮では、圧縮率のデータ依存性がある。ここで、圧縮率のデータ依存性とは、データの分布特性による圧縮率のバラツキのことをいう。そのため、従来の可逆データ圧縮では、運用に制約があった。その理由は、圧縮率が一定ではないため、保存装置や通信路の容量をワーストケースで考える必要があるからである。このデータ依存性に対する１つの対策は、ベクトル回転である。その理由は、任意のベクトルを圧縮しやすい理想ベクトルと重なるように回転すれば、そのベクトルの分布特性も理想ベクトルに近いため、圧縮率の変動が小さくなるからである。
【００４１】
図３のフローチャートを用いて、実施の形態２におけるデータ変換装置１００の動作について説明する。なお、本実施の形態におけるデータ変換装置１００の構成は、実施の形態１と同様であるものとする。
【００４２】
Ｓ２０１：演算処理部１０２は、記憶部１０１に格納された入力データのうち、所定のサンプル数（例えば１６）を読み出す。ここで、各入力データはベクトルであって（入力ベクトル）、読み出された複数の入力ベクトルによりベクトルの集合が構築される。
【００４３】
Ｓ２０２：演算処理部１０２は、入力ベクトルの回転行列を算出する。入力ベクトルをリファレンスベクトル（例えば軸ベクトルＰ＝［Ｐ０，０，０，・・・０，０，０］）と重なるように回転できれば、理論上どんな入力ベクトルでも符号量が同じである。しかし、回転行列の数が膨大になるという問題が生じる。その理由は、入力ベクトルの数と回転行列の数が同じだからである。そのため、回転行列の量子化、すなわち差分の小さいベクトル同士が共通の回転行列を使用することが必要となる。その理由は、回転行列の量子化により回転行列の数を減らすことができるからである。そして、回転行列の量子化に際しては、量子化誤差、つまり回転した入力ベクトルとリファレンスベクトルがうまく重ならなくなるという問題が生じる。その理由は、複数の入力ベクトルが一つの回転行列を共有しているからである。
【００４４】
ここで、量子化誤差は入力ベクトルの大きさに比例する。よって、入力ベクトルに一定のスケール係数を掛けることで量子化誤差の低減が期待できる。
【００４５】
リファレンスベクトルを単位軸ベクトルＵ＝［Ｕ０，０，０，・・・０，０，０］とすれば、入力ベクトルに大きさが“１”となるようなスケール係数を掛けることが望ましいが、このようなスケール係数も大量にあるため量子化が必要である。
【００４６】
スケール係数の量子化ステップが小さければ、回転行列の量子化誤差の抑制効果も大きい。しかし、それに伴う圧縮率のロスが生じる。ここで、圧縮率のロスが生じるのは、スケール係数の数が増えるからである。そのため、切り出しサンプル数でスケール係数の数を調整する。
【００４７】
演算処理部１０２は、回転行列の量子化ステップ、スケール係数の量子化ステップに応じて回転行列を計算できる。具体的には、演算処理部１０２は、行列因数分解することにより回転行列を算出する。
【００４８】
Ｓ２０３：つづいて、演算処理部１０２は、得られた回転行列を、実施の携帯１と同様の方法でリフティングが適用可能な形式に因数分解する。
【００４９】
Ｓ２０４：演算処理部１０２は、リフティングが適用可能な形式となった回転行列を使用して、入力ベクトルを単位軸ベクトルに近い形まで回転する。
【００５０】
Ｓ２０５：演算処理部１０２は、回転した入力ベクトルを差分符号化や、算術符号化などの符号化技術で符号化する。なお、回転処理は可逆であるため、復号化して逆回転すれば元の入力ベクトルを得ることができる。
【００５１】
本実施の形態は、従来の可逆データ圧縮に比べ、圧縮率のデータ依存性が低いという点で有利である。
【００５２】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば、上述の実施の形態では、本発明を主にハードウェアの構成として説明したが、これに限定されるものではなく、任意の処理を、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）にコンピュータプログラムを実行させることにより実現することも可能である。この場合、コンピュータプログラムは、様々なタイプの非一時的なコンピュータ可読媒体（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ  ｃｏｍｐｕｔｅｒ  ｒｅａｄａｂｌｅ  ｍｅｄｉｕｍ）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（ｔａｎｇｉｂｌｅ  ｓｔｏｒａｇｅ  ｍｅｄｉｕｍ）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ  ＰＲＯＭ）、フラッシュＲＯＭ、ＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（ｔｒａｎｓｉｔｏｒｙ  ｃｏｍｐｕｔｅｒ  ｒｅａｄａｂｌｅ  ｍｅｄｉｕｍ）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【符号の説明】
【００５３】
１００  データ変換装置
１０１  記憶部
１０２  演算処理部
【図１】
2014115917.tif 000019
【図２】
2014115917.tif 000020
【図３】
2014115917.tif 000021