(57)【要約】【課題】同一の圧縮率で常にＪＰＥＧよりも美しい圧縮を実現することが可能な画像特徴抽出方法を提供すること。【解決手段】本発明の画像特徴抽出方法は、与えられた画像に対してｋ２分割化処理を少なくとも１回実行することにより、該与えられた画像を多分割画像に変換するステップを包含し、該ｋ２分割化処理は、ａ）画像行列Ｘに基づいて、行列Ｔを作成するステップと、ｂ）行列Ｔの特異値を計算するステップと、ｃ）ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かを判定するステップと、ステップｃ）の判定結果が「Ｎｏ」である場合には、拡大行列Ｔαの特異値を計算する処理を行った後、ステップｃ）に戻るステップと、ｅ）ステップｃ）の判定結果が「Ｙｅｓ」である場合には、Ｔ＝ＵＳＶＴとなるＵを求めるステップと、ｆ）行列Ｔ１＝ＵＴＴを求めるステップと、ｇ）行列Ｔ１に基づいて、画像行列Ｘ１を作成するステップとを包含する。【選択図】図５
2008042335.tif 000002
【特許請求の範囲】
【請求項１】
画像の特徴を抽出する画像特徴抽出方法であって、
与えられた画像に対してｋ２（ｋは２以上の任意の整数）分割化処理を少なくとも１回実行することにより、該与えられた画像を多分割画像に変換するステップを包含し、
該ｋ２分割化処理は、
ａ）画像行列Ｘに基づいて、行列Ｔを作成するステップと、
ｂ）行列Ｔの特異値σ１，σ２，・・・，σｋ＾２を計算するステップであって、σ１≧σ２≧・・・≧σｋ＾２である、ステップと、
ｃ）ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かを判定するステップであって、εはマシンイプシロン以上の定数である、ステップと、
ｄ）ステップｃ）の判定結果が「Ｎｏ」である場合には、拡大行列Ｔαの特異値を計算する処理を行った後、ステップｃ）に戻るステップと、
ｅ）ステップｃ）の判定結果が「Ｙｅｓ」である場合には、Ｔ＝ＵＳＶＴとなるＵを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），Ｕは直交行列、Ｖは直交行列である、ステップと、
ｆ）行列Ｔ１＝ＵＴＴを求めるステップと、
ｇ）行列Ｔ１に基づいて、画像行列Ｘ１を作成するステップと
を包含し、
ステップｄ）における拡大行列Ｔαの特異値を計算する処理は、
画像行列Ｘの少なくとも一辺の少なくとも一部に付けられる少なくともｋ×ｋのサイズを有するふちと行列Ｔとに基づいて、拡大行列Ｔαを作成するステップと、
拡大行列Ｔαの特異値σ１，σ２，・・・，σｋ＾２を計算するステップであって、σ１≧σ２≧・・・≧σｋ＾２である、ステップと
を包含する、画像特徴抽出方法。
【請求項２】
画像の特徴を抽出する画像特徴抽出方法であって、
与えられた画像に対してｋ２（ｋは２以上の任意の整数）分割化処理を少なくとも１回実行することにより、該与えられた画像を多分割画像に変換するステップを包含し、
該ｋ２分割化処理は、
ａ）画像行列Ｘに基づいて、行列Ｔを作成するステップと、
ｂ）行列Ｔの特異値分解Ｔ＝ＵＳＶＴを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ＾２は、σ１≧σ２≧・・・≧σｋ＾２を満たすＴの特異値、Ｕは直交行列、Ｖは直交行列である、ステップと、
ｃ）ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かを判定するステップであって、εはマシンイプシロン以上の定数である、ステップと、
ｄ）ステップｃ）の判定結果が「Ｎｏ」である場合には、拡大行列Ｔαの特異値分解を実行する処理を行った後、ステップｃ）に戻るステップと、
ｅ）ステップｃ）の判定結果が「Ｙｅｓ」である場合には、行列Ｔ１＝ＵＴＴを求めるステップと、
ｆ）行列Ｔ１に基づいて、画像行列Ｘ１を作成するステップと
を包含し、
ステップｄ）における拡大行列Ｔαの特異値分解を実行する処理は、
画像行列Ｘの少なくとも一辺の少なくとも一部に付けられる少なくともｋ×ｋのサイズを有するふちと行列Ｔとに基づいて、拡大行列Ｔαを作成するステップと、
拡大行列Ｔαの特異値分解Ｔα＝ＵＳＶＴを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ＾２は、σ１≧σ２≧・・・≧σｋ＾２を満たすＴαの特異値、Ｕは直交行列、Ｖは直交行列である、ステップと
を包含する、画像特徴抽出方法。
【請求項３】
前記画像は、グレースケール画像またはカラー画像である、請求項１または２に記載の画像特徴抽出方法。
【請求項４】
前記Ｔおよび前記Ｔαの特異値分解が浮動小数点演算で行われる、請求項１または２に記載の画像特徴抽出方法。
【請求項５】
前記Ｔおよび前記Ｔαの特異値分解が整数演算で行われる、請求項１または２に記載の画像特徴抽出方法。
【請求項６】
前記ｋ２分割化処理とウェーブレット変換などの既知のｋ２分割化処理とを併用することにより、前記与えられた画像行列Ｘが多分割画像に変換される、請求項１または２に記載の画像特徴抽出方法。
【請求項７】
画像を圧縮する画像圧縮方法であって、
与えられた画像に対してｋ２（ｋは２以上の任意の整数）分割化処理を少なくとも１回実行することにより、該与えられた画像を多分割画像に変換するステップと、
該多分割画像に対してデータ圧縮処理を行うことにより、圧縮画像を作成するステップと
を包含し、
該ｋ２分割化処理は、
ａ）画像行列Ｘに基づいて、行列Ｔを作成するステップと、
ｂ）行列Ｔの特異値σ１，σ２，・・・，σｋ＾２を計算するステップであって、σ１≧σ２≧・・・≧σｋ＾２である、ステップと、
ｃ）ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かを判定するステップであって、εはマシンイプシロン以上の定数である、ステップと、
ｄ）ステップｃ）の判定結果が「Ｎｏ」である場合には、拡大行列Ｔαの特異値を計算する処理を行った後、ステップｃ）に戻るステップと、
ｅ）ステップｃ）の判定結果が「Ｙｅｓ」である場合には、Ｔ＝ＵＳＶＴとなるＵを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），Ｕは直交行列、Ｖは直交行列である、ステップと、
ｆ）行列Ｔ１＝ＵＴＴを求めるステップと、
ｇ）行列Ｔ１に基づいて、画像行列Ｘ１を作成するステップと
を包含し、
ステップｄ）における拡大行列Ｔαの特異値を計算する処理は、
画像行列Ｘの少なくとも一辺の少なくとも一部に付けられる少なくともｋ×ｋのサイズを有するふちと行列Ｔとに基づいて、拡大行列Ｔαを作成するステップと、
拡大行列Ｔαの特異値σ１，σ２，・・・，σｋ＾２を計算するステップであって、σ１≧σ２≧・・・≧σｋ＾２である、ステップと
を包含する、画像圧縮方法。
【請求項８】
画像を圧縮する画像圧縮方法であって、
与えられた画像に対してｋ２（ｋは２以上の任意の整数）分割化処理を少なくとも１回実行することにより、該与えられた画像を多分割画像に変換するステップと、
該多分割画像に対してデータ圧縮処理を行うことにより、圧縮画像を作成するステップと
を包含し、
該ｋ２分割化処理は、
ａ）画像行列Ｘに基づいて、行列Ｔを作成するステップと、
ｂ）行列Ｔの特異値分解Ｔ＝ＵＳＶＴを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ＾２は、σ１≧σ２≧・・・≧σｋ＾２を満たすＴの特異値、Ｕは直交行列、Ｖは直交行列である、ステップと、
ｃ）ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かを判定するステップであって、εはマシンイプシロン以上の定数である、ステップと、
ｄ）ステップｃ）の判定結果が「Ｎｏ」である場合には、拡大行列Ｔαの特異値分解を実行する処理を行った後、ステップｃ）に戻るステップと、
ｅ）ステップｃ）の判定結果が「Ｙｅｓ」である場合には、行列Ｔ１＝ＵＴＴを求めるステップと、
ｆ）行列Ｔ１に基づいて、画像行列Ｘ１を作成するステップと
を包含し、
ステップｄ）における拡大行列Ｔαの特異値分解を実行する処理は、
画像行列Ｘの少なくとも一辺の少なくとも一部に付けられる少なくともｋ×ｋのサイズを有するふちと行列Ｔとに基づいて、拡大行列Ｔαを作成するステップと、
拡大行列Ｔαの特異値分解Ｔα＝ＵＳＶＴを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ＾２は、σ１≧σ２≧・・・≧σｋ＾２を満たすＴαの特異値、Ｕは直交行列、Ｖは直交行列である、ステップと
を包含する、画像圧縮方法。
【請求項９】
前記画像は、グレースケール画像またはカラー画像である、請求項７または８に記載の画像圧縮方法。
【請求項１０】
前記Ｔおよび前記Ｔαの特異値分解が浮動小数点演算で行われる、請求項７または８に記載の画像圧縮方法。
【請求項１１】
前記Ｔおよび前記Ｔαの特異値分解が整数演算で行われる、請求項７または８に記載の画像圧縮方法。
【請求項１２】
前記ｋ２分割化処理とウェーブレット変換などの既知のｋ２分割化処理とを併用することにより、前記与えられた画像行列Ｘが多分割画像に変換される、請求項７または８に記載の画像圧縮方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同一の圧縮率で常にＪＰＥＧよりも美しい圧縮を実現することが可能な画像圧縮方法およびそれに適した画像特徴抽出方法に関する。
【背景技術】
【０００２】
ハードウェアの進歩に伴い、コンピュータやデジタルカメラ・プリンタなどの周辺機器で扱うことができる画像は、今や超精密アナログカメラの画質レベルに匹敵する。当然、画像がもつデータ量も増大するため、細部にわたる忠実さよりも表示速度が重視される場面では画像圧縮は必要不可欠な技術である。もちろん、画像圧縮によりデータ量を削減するだけでなく、原画像との違いは人間の視覚では、できる限り確認できないのが理想である。同時に、記憶領域を小さくできれば、メモリやハードディスクなどの計算機資源が有効に活用できる。
【０００３】
Ｗｅｂサイトでは、一般的にＧＩＦやＪＰＥＧ、ＰＮＧといった形式で圧縮された画像が利用されている。これらは、ＢＭＰ画像のような非圧縮画像に比べてファイルサイズが格段に抑えられるため、高いアクセス性が求められるＷｅｂサイトには適している。また、ネットワークを介して画像データを送受信する際も画像圧縮技術は重宝されることが多い。
【０００４】
画像は、コンピュータ内部でピクセルごとに色の濃淡が数値化される。例えば、縦ｍピクセル、横ｎピクセルの２５６階調グレースケール画像Ｘは、成分に［０，２５５］の整数値をもつｍ×ｎ行列として表現される。
【０００５】
【数１】
2008042335.tif 000003
ただし、ｘｉ，ｊは［０，２５５］の整数値である。
【０００６】
以下では画像と行列を同一視して表す。ＲＧＢカラー画像は、赤（Ｒｅｄ）・緑（Ｇｒｅｅｎ）・青（Ｂｌｕｅ）の３色について濃淡情報をそれぞれグレースケール画像と同様の行列形式で保持している。よって、簡単化のため、以下、グレースケール画像を対象とする。
【０００７】
画像Ｘに対して２次元離散ウェーブレット変換、または、ブロック化＋特異値分解を１度実行すれば、左上（ｍ／２）×（ｎ／２）ピクセルには画像Ｘを１／２倍したような画像Ｘ１が生成される。右上には縦方向、左下には横方向、右下には斜め方向のエッジを抽出したような画像が現れる。同様に、Ｘ１の４分割、すなわち、Ｘ１→（縮小近似画像Ｘ２）＋（縦方向のエッジ抽出画像）＋（横方向のエッジ抽出画像）＋（斜め方向のエッジ抽出画像）、Ｘ２を４分割、・・・、Ｘｋを４分割というように分割を繰り返せば多分割画像が作成できるが、これが画像圧縮における基本的な工程となる［１］。画像の多分割化後は、ＳＰＩＨＴ［５］などでコーディングすればよい。なお、離散コサイン変換による画像圧縮でもＸのブロック化は伴うが、ブロック特異値分解のような画像の４分割は行われない。量子化やハフマン符号によるコーディングが施され、データ量も小さく拡大縮小にも強い圧縮画像が得られるが、原画像を復元できない不可逆変換ということには注意が必要である［２］。
【０００８】
ブロック特異値分解による多分割アルゴリズムが、Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａ［３］によって提案されている。このアルゴリズムと離散ウェーブレット変換を併用したハイブリット型アルゴリズムも報告されている［１］。指紋のような特別な性質をもつ画像では、ＪＰＥＧやＪＰＥＧ２０００として実用化されている離散コサイン変換や離散ウェーブレット変換よりも、ハイブリット型アルゴリズムによって、より自然な画質で画像圧縮できることも知られている。ブロック特異値分解による画像圧縮には様々な可能性が秘められており、さらなる数値的な検証がなされるべきである。
【非特許文献１】［１］Ａｓｈｉｎｏ，Ｒ．，Ｍｏｒｉｍｏｔｏ，Ａ．，Ｎａｇａｓｅ，Ｍ．，ａｎｄ  Ｖａｉｌｌａｎｃｏｕｒｔ，Ｒ．：Ｉｍａｇｅ  ｃｏｍｐｒｅｓｓｉｏｎ  ｗｉｔｈ  ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ  ｓｉｎｇｕｌａｒ  ｖａｌｕｅ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ａｎｄ  ｏｔｈｅｒ  ｍｅｔｈｏｄｓ，Ｍａｔｈ．  Ｃｏｍｐｕｔ．  Ｍｏｄｅｌ．，Ｖｏｌ．４１，ｐｐ．７７３．７９０（２００５）
【非特許文献２】［２］越智宏，黒田秀夫：  ＪＰＥＧ  ＆  ＭＰＥＧ  図解でわかる画像圧縮技術，日本実業出版社（２００６）
【非特許文献３】［３］Ｋａｋａｒａｌａ，Ｒ．，ａｎｄ  Ｏｇｕｎｂｏｎａ，Ｏ．Ｐ．：Ｓｉｇｎａｌ  ａｎａｌｙｓｉｓ  ｕｓｉｎｇ  ａ  ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ  ｆｏｒｍ  ｏｆ  ｔｈｅ  ｓｉｎｇｕｌａｒ  ｖａｌｕｅ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ，ＩＥＥＥ  Ｔｒａｎｓ．Ｉｍａｇｅ  Ｐｒｏｃｅｓｓ．，Ｖｏｌ．１０，ｐｐ．７２４．７３５（２００１）
【非特許文献４】［４］Ｉｗａｓａｋｉ，Ｍ．，ａｎｄ  Ｎａｋａｍｕｒａ，Ｙ．：Ａｃｃｕｒａｔｅ  ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  ｓｉｎｇｕｌａｒ  ｖａｌｕｅｓ  ｉｎ  ｔｅｒｍｓ  ｏｆ  ｓｈｉｆｔｅｄ  ｉｎｔｅｇｒａｂｌｅ  ｓｃｈｅｍｅｓ，（ｓｕｂｍｉｔｔｅｄ）
【非特許文献５】［５］Ｓａｉｄ，Ａ．，ａｎｄ  Ｐｅａｒｌｍａｎ，Ａ．Ｗ．：Ａ  ｎｅｗ  ｆａｓｔ  ａｎｄ  ｅｆｆｉｃｉｅｎｔ  ｉｍａｇｅ  ｃｏｄｅｃ  ｂａｓｅｄ  ｏｎ  ｓｅｔ  ｐａｒｔｉｔｉｏｎｉｎｇ  ｉｎ  ｈｉｅｒａｒｃｈｉｃａｌ  ｔｒｅｅｓ，ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙ，Ｖｏｌ．６，ｐｐ．２４３．２５０（１９９６）
【非特許文献６】［６］高田雅美，木村欣司，岩崎雅史，中村佳正：高速特異値分解のためのライブラリ開発，投稿中
【非特許文献７】［７］Ｐａｒｌｅｔｔ，Ｂ．Ｎ．，ａｎｄ  Ｍａｒｑｕｅｓ，Ｏ．Ａ．：Ａｎ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  ｔｈｅ  ｄｑｄｓ  ａｌｇｏｒｉｔｈｍ（ｐｏｓｉｔｉｖｅ  ｃａｓｅ），Ｌｉｎ．Ａｌｇ．Ａｐｐｌ．，Ｖｏｌ．３０９，ｐｐ．２１７．２５９（２０００）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本明細書では、まず、Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムで多分割する際、特異値分解の対象となる行列の特異値の分布を調べる。画像によっては特異値が互いに重複および近接するが、そのような場合、既存の特異値分解法では、精度よく特異ベクトルが計算できるとは限らない［６］。［６］は倍精度演算による実験結果であるが、単精度や整数型演算では特異ベクトルを高い精度で求めることはより一層困難となる。
【００１０】
本発明では、ブロック特異値分解において特異値の近接度を下げるアルゴリズムを新たに定式化する。本発明の目的の１つは、同一の圧縮率で常にＪＰＥＧよりも美しい圧縮を実現することが可能な画像圧縮方法およびそれに適した画像特徴抽出方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明の方法は、画像の特徴を抽出する画像特徴抽出方法であって、与えられた画像に対してｋ２（ｋは２以上の任意の整数）分割化処理を少なくとも１回実行することにより、該与えられた画像を多分割画像に変換するステップを包含し、該ｋ２分割化処理は、ａ）画像行列Ｘに基づいて、行列Ｔを作成するステップと、ｂ）行列Ｔの特異値σ１，σ２，・・・，σｋ＾２を計算するステップであって、σ１≧σ２≧・・・≧σｋ＾２である、ステップと、ｃ）ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かを判定するステップであって、εはマシンイプシロン以上の定数である、ステップと、ｄ）ステップｃ）の判定結果が「Ｎｏ」である場合には、拡大行列Ｔαの特異値を計算する処理を行った後、ステップｃ）に戻るステップと、ｅ）ステップｃ）の判定結果が「Ｙｅｓ」である場合には、Ｔ＝ＵＳＶＴとなるＵを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），Ｕは直交行列、Ｖは直交行列である、ステップと、ｆ）行列Ｔ１＝ＵＴＴを求めるステップと、ｇ）行列Ｔ１に基づいて、画像行列Ｘ１を作成するステップとを包含し、ステップｄ）における拡大行列Ｔαの特異値を計算する処理は、画像行列Ｘの少なくとも一辺の少なくとも一部に付けられる少なくともｋ×ｋのサイズを有するふちと行列Ｔとに基づいて、拡大行列Ｔαを作成するステップと、拡大行列Ｔαの特異値σ１，σ２，・・・，σｋ＾２を計算するステップであって、σ１≧σ２≧・・・≧σｋ＾２である、ステップとを包含し、これにより、上記目的が達成される。
【００１２】
本発明の方法は、画像の特徴を抽出する画像特徴抽出方法であって、与えられた画像に対してｋ２（ｋは２以上の任意の整数）分割化処理を少なくとも１回実行することにより、該与えられた画像を多分割画像に変換するステップを包含し、該ｋ２分割化処理は、ａ）画像行列Ｘに基づいて、行列Ｔを作成するステップと、ｂ）行列Ｔの特異値分解Ｔ＝ＵＳＶＴを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ＾２は、σ１≧σ２≧・・・≧σｋ＾２を満たすＴの特異値、Ｕは直交行列、Ｖは直交行列である、ステップと、ｃ）ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かを判定するステップであって、εはマシンイプシロン以上の定数である、ステップと、ｄ）ステップｃ）の判定結果が「Ｎｏ」である場合には、拡大行列Ｔαの特異値分解を実行する処理を行った後、ステップｃ）に戻るステップと、ｅ）ステップｃ）の判定結果が「Ｙｅｓ」である場合には、行列Ｔ１＝ＵＴＴを求めるステップと、ｆ）行列Ｔ１に基づいて、画像行列Ｘ１を作成するステップとを包含し、ステップｄ）における拡大行列Ｔαの特異値分解を実行する処理は、画像行列Ｘの少なくとも一辺の少なくとも一部に付けられる少なくともｋ×ｋのサイズを有するふちと行列Ｔとに基づいて、拡大行列Ｔαを作成するステップと、拡大行列Ｔαの特異値分解Ｔα＝ＵＳＶＴを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ＾２は、σ１≧σ２≧・・・≧σｋ＾２を満たすＴαの特異値、Ｕは直交行列、Ｖは直交行列である、ステップとを包含し、これにより、上記目的が達成される。
【００１３】
前記画像は、グレースケール画像またはカラー画像であってもよい。
【００１４】
前記Ｔおよび前記Ｔαの特異値分解が浮動小数点演算で行われてもよい。
【００１５】
前記Ｔおよび前記Ｔαの特異値分解が整数演算で行われてもよい。
【００１６】
前記ｋ２分割化処理とウェーブレット変換などの既知のｋ２分割化処理とを併用することにより、前記与えられた画像行列Ｘが多分割画像に変換されてもよい。
【００１７】
本発明の方法は、画像を圧縮する画像圧縮方法であって、与えられた画像に対してｋ２（ｋは２以上の任意の整数）分割化処理を少なくとも１回実行することにより、該与えられた画像を多分割画像に変換するステップと、該多分割画像に対してデータ圧縮処理を行うことにより、圧縮画像を作成するステップとを包含し、該ｋ２分割化処理は、ａ）画像行列Ｘに基づいて、行列Ｔを作成するステップと、ｂ）行列Ｔの特異値σ１，σ２，・・・，σｋ＾２を計算するステップであって、σ１≧σ２≧・・・≧σｋ＾２である、ステップと、ｃ）ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かを判定するステップであって、εはマシンイプシロン以上の定数である、ステップと、ｄ）ステップｃ）の判定結果が「Ｎｏ」である場合には、拡大行列Ｔαの特異値を計算する処理を行った後、ステップｃ）に戻るステップと、ｅ）ステップｃ）の判定結果が「Ｙｅｓ」である場合には、Ｔ＝ＵＳＶＴとなるＵを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），Ｕは直交行列、Ｖは直交行列である、ステップと、ｆ）行列Ｔ１＝ＵＴＴを求めるステップと、ｇ）行列Ｔ１に基づいて、画像行列Ｘ１を作成するステップとを包含し、ステップｄ）における拡大行列Ｔαの特異値を計算する処理は、画像行列Ｘの少なくとも一辺の少なくとも一部に付けられる少なくともｋ×ｋのサイズを有するふちと行列Ｔとに基づいて、拡大行列Ｔαを作成するステップと、拡大行列Ｔαの特異値σ１，σ２，・・・，σｋ＾２を計算するステップであって、σ１≧σ２≧・・・≧σｋ＾２である、ステップとを包含し、これにより、上記目的が達成される。
【００１８】
本発明の方法は、画像を圧縮する画像圧縮方法であって、与えられた画像に対してｋ２（ｋは２以上の任意の整数）分割化処理を少なくとも１回実行することにより、該与えられた画像を多分割画像に変換するステップと、該多分割画像に対してデータ圧縮処理を行うことにより、圧縮画像を作成するステップとを包含し、該ｋ２分割化処理は、ａ）画像行列Ｘに基づいて、行列Ｔを作成するステップと、ｂ）行列Ｔの特異値分解Ｔ＝ＵＳＶＴを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ＾２は、σ１≧σ２≧・・・≧σｋ＾２を満たすＴの特異値、Ｕは直交行列、Ｖは直交行列である、ステップと、ｃ）ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かを判定するステップであって、εはマシンイプシロン以上の定数である、ステップと、ｄ）ステップｃ）の判定結果が「Ｎｏ」である場合には、拡大行列Ｔαの特異値分解を実行する処理を行った後、ステップｃ）に戻るステップと、ｅ）ステップｃ）の判定結果が「Ｙｅｓ」である場合には、行列Ｔ１＝ＵＴＴを求めるステップと、ｆ）行列Ｔ１に基づいて、画像行列Ｘ１を作成するステップとを包含し、ステップｄ）における拡大行列Ｔαの特異値分解を実行する処理は、画像行列Ｘの少なくとも一辺の少なくとも一部に付けられる少なくともｋ×ｋのサイズを有するふちと行列Ｔとに基づいて、拡大行列Ｔαを作成するステップと、拡大行列Ｔαの特異値分解Ｔα＝ＵＳＶＴを求めるステップであって、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ＾２は、σ１≧σ２≧・・・≧σｋ＾２を満たすＴαの特異値、Ｕは直交行列、Ｖは直交行列である、ステップとを包含し、これにより、上記目的が達成される。
【００１９】
前記画像は、グレースケール画像またはカラー画像であってもよい。
【００２０】
前記Ｔおよび前記Ｔαの特異値分解が浮動小数点演算で行われてもよい。
【００２１】
前記Ｔおよび前記Ｔαの特異値分解が整数演算で行われてもよい。
【００２２】
前記ｋ２分割化処理とウェーブレット変換などの既知のｋ２分割化処理とを併用することにより、前記与えられた画像行列Ｘが多分割画像に変換されてもよい。
【発明の効果】
【００２３】
本発明によれば、同一の圧縮率で常にＪＰＥＧよりも美しい圧縮を実現することが可能な画像圧縮方法およびそれに適した画像特徴抽出方法を提供することができる。
【発明を実施するための最良の形態】
【００２４】
以下、図面を参照しながら、本発明の実施の形態を説明する。
【００２５】
１．はじめに
これまでに画像のデータ量を圧縮する様々な方法が提案されている。ここでは、Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａの画像圧縮アルゴリズムを取り上げる。この方法と離散ウェーブレット変換とを併用することで、すぐれた画像圧縮が可能となる。この方法には行列の多分割（ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ）特異値分解の計算過程が含まれるが、その数値的検証はこれまで十分には行われてはいない。本明細書では、まず、画像のタイプによって特異値分布が大きく変動すること、ある場合には特異値がクラスタをなすことを数値的に示す。特異値の近接度が高いと既存の特異値分解ルーチンでは必ずしも特異ベクトルが高精度に求められるとは限らず、圧縮画像が原画像と大きく異なってしまう危険性がある。そこで、本発明において、特異値のクラスタを分散させ、特異値相互のギャップを拡大するアルゴリズムを提案し、数値実験によってその効果を明らかにする。
【００２６】
２章では、画像を多分割化するためのＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａのブロック特異値分解アルゴリズムについて概観する。３章において、縦、横、斜め縞模様、および、ランダム模様の画像に対してＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムを適用したとき、どのような特異値分布をもつ行列が現れるかを論じる。４章では、ブロック特異値分解アルゴリズムにおいて、特異値相互のギャップを拡大し近接度を下げる効果的な方法について提案し、その効果を数値実験で確認する。
【００２７】
２．Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａのブロック特異値分解アルゴリズム
画像行列Ｘに対して、２次元ウェーブレット変換すれば図１のような４分割画像が得られる。縮小近似画像の４分割化を繰り返すと多分割画像が生成され、ＳＰＨＩＴなどでコーディングすれば画像圧縮は完了する。なお、多分割画像は４分割画像に限定されない。縮小近似画像のｋ２分割化を繰り返すことにより多分割画像を生成するようにしてもよい。ここで、ｋは２以上の任意の整数である。画像の多分割化は、Ｘのブロック化＋特異値分解でも実現できる。なお、離散コサイン変換もＸのブロック化と併用されるが、この場合は多分割画像が生成されない。本章では、画像を多分割するためのＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａによって提案されたブロック特異値分解アルゴリズムについて概説する。Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムは任意のブロックサイズで任意サイズの長方形画像に適用できるが、その場合については［１、３］を参照されたい。また、大きな画像は適当なサイズの複数個の画像に分けて、それぞれについて個別に多分割化してもよい。便宜上、以下ではブロックサイズを２として３２ピクセル×３２ピクセルの原画像Ｘから４分割画像Ｘ１を作成する場合におけるＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムを説明する。
【００２８】
Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズム
（１）３２×３２行列Ｘを２×２小行列Ｘ（ｋ，ｌ）（１≦ｋ≦１６，１≦ｌ≦１６）に分割する。
【００２９】
【数２】
2008042335.tif 000004
（２）Ｘ（ｋ，ｌ）ごとに４×１の列ベクトルに変換する。
【００３０】
【数３】
2008042335.tif 000005
（３）列ベクトルを並べて４×２５６行列Ｔを作成する。
【００３１】
【数４】
2008042335.tif 000006
（４）Ｔの特異値分解Ｔ＝ＵＳＶＴを求める。ただし、Ｓ＝ｄｉａｇ（σ１，σ２，σ３，σ４），σｋ，ｋ＝１，２，３，４はＴの特異値、Ｕは４×４直交行列、Ｖは２５６×２５６直交行列とする。
【００３２】
（５）４×２５６行列Ｔ１＝ＵＴＴを求める。
【００３３】
（６）Ｔ１のｋ行目ベクトルを１６×１６行列Ｘ１（ｋ）に変換する。
【００３４】
【数５】
2008042335.tif 000007
（７）Ｘ１（ｋ）を並べて３２×３２行列Ｘ１を作成する。
【００３５】
【数６】
2008042335.tif 000008
（４）で得られる直交行列Ｕの第１列目ベクトルは、（１）でブロック化された２×２行列Ｘ（ｋ，ｌ）の４成分を平均化するフィルタとなる。（２）、（３）によってＸ（ｋ，ｌ）の成分はＴの列に配置されるので、（５）のようにＴの左からＵＴを作用させれば、Ｔ１の第１行目にはブロックに含まれる４成分の平均値が並ぶ。よって、（６）のようにＴ１の第１行目をＸ１（１）に変換すれば、それがＸの縮小近似画像となる。同様に、Ｘ１（２）、Ｘ１（３）、Ｘ１（４）はそれぞれＸの縦、横、斜め方向のエッジが強調された画像と対応する。したがって、（７）のようにＸ１（ｋ）を並べると、Ｘの４分割化が完了する。
【００３６】
３．画像の種類と特異値分布
Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムで多分割画像を作成する際、特異値分解の対象となる行列Ｔは画像ごとに異なり、ブロック特異値分解で求められる特異値σｊ（σ１≧σ２≧・・・）も画像によって変動する。
【００３７】
特異値分解では、特異値のギャップｇａｐ≡｜σｊ−σｊ＋１｜は特異ベクトルの精度に関する重要な指標である。すなわち、一般に特異値の分布が密になるほど、特異ベクトルの直交性が悪化する［６］。
【００３８】
以下では、図２の縦、横、斜め縞およびランダム模様の３２ピクセル×３２ピクセルグレースケール画像を作成して、Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムのもとで行列Ｘ＊がもつ特異値の最小ギャップｇａｐｍｉｎ≡ｍｉｎｊ｜σｊ−σｊ＋１｜がどの程度になるかを調べた。数値実験にはＣＰＵ：Ｐｅｎｔｉｕｍ（登録商標）  Ｍ  １．２ＧＨｚ、Ｍｅｍｏｒｙ：５０４ＭＢをもつＩＢＭ  Ｔｈｉｎｋ  Ｐａｄ上でＭａｔｌａｂ  ６．５を使用した。なお、行列の特異値分解はＭａｔｌａｂの組み込み関数ｓｖｄ（）によって倍精度で求めた。
【００３９】
図２のテスト画像（ａ）〜画像（ｅ）は、それぞれ、縞の濃淡と太さまたは点の濃淡をランダムに変化させて生成した画像である。具体的には、行列の成分ｘｋ、ｋ＝１，２，・・・，１０２４を［０，２５５］のランダムな整数とし、このようなＸａ、Ｘｂ、Ｘｃ、Ｘｄ、Ｘｅをそれぞれ１００００個ずつ準備した。
【００４０】
【数７】
2008042335.tif 000009
画像（ａ）および画像（ｂ）について、それぞれ、１００００個の４分割化をしたところ、ｇａｐｍｉｎの値は同じような傾向を示していて、ほとんどの場合１０−１０以下となった。表１のように、最も特異値が近接する場合でｇａｐｍｉｎがマシンイプシロン程度の極めて小さい値になることも分かった。一方、画像（ｃ）および画像（ｄ）では、図３のように、ほとんどがｇａｐｍｉｎ＞１であったが、表１に示すように、ｇａｐｍｉｎがゼロとなり行列Ｘ＊の特異値が重複することもあった。画像（ｅ）では、概ねｇａｐｍｉｎ＞１、かつ、最も特異値が近接する場合でもｇａｐｍｉｎ＝０．５２と他の画像の場合と比較して特異値が分散していることが分かった。
【００４１】
【表１】
2008042335.tif 000010
倍精度計算において、ｇａｐｍｉｎ＞１０−３程度ならば直交性のよい特異ベクトルが計算できるとされている［６］。この中で、常にこの条件が満たされるのは画像（ｅ）のみである。つまり、画像（ａ）〜画像（ｄ）のような何らかの規則性をもつ画像の場合は、Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムでは行列Ｘ＊を精度よく特異値分解できず、その結果、美しい圧縮画像が得られない可能性がある。
【００４２】
４．拡大画像
原画像Ｘに何らかの規則性があると、Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムにおける特異値分解が高精度に実現できるかは定かでない。つまり、原画像Ｘより生成される行列Ｔの特異値相互の最小ギャップｇａｐｍｉｎが小さければ、必ずしも美しい４分割画像が得られるとは限らない。本章では、原画像Ｘのまわりにランダム模様のふちを追加することで規則性を崩したＸバーについて検討する。ここで、「Ｘバー」とはＸの上に水平線を付した表記と同義である。なお、原画像サイズは３２ピクセル×３２ピクセル、Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムにおけるブロックサイズをｂ＝２とする。
【００４３】
まず、左側のみに２ピクセルのふちが付いた拡大画像を表す３２×３４行列
【００４４】
【数８】
2008042335.tif 000011
について数学的に考察する。ただし、ｄｋ，ｋ＝１，２，・・・，６４は［０，２５５］のランダムな整数とする。Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムの（１）〜（４）において、Ｘが４×２５６行列Ｔに、Ｘバーが４×２７２行列Ｔバーに変換されるならば、ＴバーはＴとふちの画像に対応する４×１６行列Ｄによって
【００４５】
【数９】
2008042335.tif 000012
と表現できる。ただし、Ｄの成分はｄｋ，ｋ＝１，２，・・・，６４からなる。このとき、
【００４６】
【数１０】
2008042335.tif 000013
なので、Ｄを変化させるとＴバー（Ｔバー）ＴはＴＴＴと異なる固有値分布をもつことが分かる。つまり、Ｄをうまく制御すれば、Ｔバーは近接した特異値をもたない行列にできる。ここで、「Ｔバー」とはＴの上に水平線を付した表記と同義である。
【００４７】
左側に加えて右側、上側、下側に任意サイズのふちを付けた拡大画像Ｘバーは、Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムの（１）〜（４）によって
【００４８】
【数１１】
2008042335.tif 000014
に変換される。ただし、Ｄｋ，ｋ＝１，２，・・・，３２は上下左右いずれかのふちの画像に対応する行数４の行列またはベクトルであり、Ｔ＝（Ｔ１  Ｔ２・・・  Ｔ３２）となる。ふちが左側のみの場合と同じように
【００４９】
【数１２】
2008042335.tif 000015
が成り立つ。したがって、ふちあり画像を４分割の対象とすれば、ｇａｐｍｉｎの値が小さくなるような行列の特異値分解は避けられる。また、Ｔバーの行を入れかえても特異値は変化せず、列を入れかえても直交行列Ｕは変化しないことにも注意したい。
【００５０】
通常用いられる特異値分解アルゴリズムでは、原点シフトによって特異値の相対ギャップが拡大されるため、得られる特異値の精度はｇａｐｍｉｎの値にほとんど依存しない。ｄｑｄｓアルゴリズム［７］やｍｄＬＶｓアルゴリズム［４］のように、高い相対精度をもつ特異値計算法もある。
【００５１】
画像圧縮で必要なのは特異値ではなく特異ベクトルのいくつかの成分である。このことから、特異値の相対ギャップを拡大して特異ベクトルを高精度に計算する新しいアルゴリズムが定式化できる。
【００５２】
なお、拡大画像は、原画像の左側のみにふちを付けることによって得られるものには限定されない。拡大画像は、原画像のうちの少なくとも１つにふちを付けることによって得られるものであってもよい。また、ふちの幅または長さは、２ピクセルには限定されない。ふちの幅および長さは、所定の数のピクセルであり得る。ここで、所定の数は任意の整数であり得る。ふちの幅および長さのピクセル数は、例えば、原画像の性質に応じて設計され得る。また、ふちに対応する各要素ｄｋの値は、ランダム値には限定されない。ふちに対応する各要素ｄｋの値は、実質的にランダムな値（例えば、擬似ランダム値）であれば同等の効果が得られる。
【００５３】
以下では、画像Ｘの高精度な４分割アルゴリズムを提案する。
【００５４】
高精度な４分割アルゴリズム
Ｓｔｅｐ  １：Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムの（１）〜（４）によってＸからＴに変換する。また、Ｔバー←Ｔとする。
【００５５】
Ｓｔｅｐ  ２：Ｔバーの特異値を求める。
【００５６】
ｇａｐｍｉｎ≧εならば
Ｔバーの特異値分解Ｔバー＝ＵＳＶＴを求める。
【００５７】
ｇａｐｍｉｎ＜εならば
Ｔバー←（Ｄ（Ｔバー））としてＳｔｅｐ２に戻る。ただし、Ｄは、成分が［０，２５５］のランダムな整数で与えられた４×ｎ’行列、ｎ’はふちの大きさに対応する。
【００５８】
どの特異値分解アルゴリズムを利用するかによってεの値を設定すべきであるが、マシンイプシロン付近の小さな値は望ましくない。
【００５９】
Ｓｔｅｐ  ３：ふちの情報を含まないＴに左からＵＴを作用させる、つまり、Ｔ１←ＵＴＴとする。
【００６０】
Ｓｔｅｐ  ４：Ｋａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムの（６）、（７）によって４分割画像Ｘ１を得る。
【００６１】
このアルゴリズムは、特異値に近接しているものがあれば一時的にふちを付けて、特異値分解終了後には直ちにふちを取り除いて４分割画像を作成するという仕組みである。
【００６２】
この４分割アルゴリズムの効果（特に、Ｓｔｅｐ  ２の効果）を実証するための数値実験を行った。原画像は３章と同じく図２の画像（ａ）〜画像（ｅ）、拡大画像はそれぞれに２ピクセルのランダムなふちを上側と左側につけた画像とした。
【００６３】
【表２】
2008042335.tif 000016
画像（ａ）および画像（ｂ）の拡大画像それぞれ１００００個から生成されるＴバーでは、特異値相互のギャップがｇａｐｍｉｎ＞１０となった。行列Ｔバーの特異値が最も近接する場合でも、ｇａｐｍｉｎの値は、表２のように、画像（ａ）で７．８×１０−４、画像（ｂ）で１．５×１０−３となり、３章に示したふちなしよりも特異値のクラスタが分散されているのが分かる。画像（ｃ）および画像（ｄ）の拡大画像については、多くの場合でＴバーのｇａｐｍｉｎが０．１以上となり、ふちなし画像と比較すれば行列Ｔバーの特異値が若干近接するが、高精度に特異値分解するには全く支障のないレベルである。最低でもｇａｐｍｉｎはＯ（１０−３）に抑えられ、Ｔバーが重複特異値をもつ状況は回避できた。画像（ｅ）では、原画像に規則性がないため、ふちを付けてもｇａｐｍｉｎの値が大きく変化することはなかった。
【００６４】
原画像をもとに縮小近似画像と縦、横、斜め方向のエッジ抽出画像の４分割画像を作成する画像圧縮方式において、有用な手段の１つであるＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａのブロック特異値分解について説明した。５種類のテスト画像をＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムによって４分割化したところ、規則性のある画像についてはアルゴリズムの途中で近接または重複特異値をもつ行列が現れることがあった。特異値相互のギャップが小さくなれば、特異ベクトルの精度が低下するとの報告もあるため、本発明では特異値の相対ギャップを拡大し、クラスタを分散させる４分割アルゴリズムを定式化した。原画像にランダム模様のふちを追加して４分割化するというシンプルなアイデアではあるが、理論的にも実験的にも高精度な特異値分解が困難な状況を回避できることを示した。
【００６５】
５．画像圧縮
提案した４分割化アルゴリズムとＳＰＨＩＴコーディングを組み合わせて圧縮画像を生成したところ、図５のような結果が得られた。図５の横軸は、原画像に対するファイルサイズ比（左ほど高圧縮）を示し、図５の縦軸は、ＰＳＮＲ値（上ほど美しい圧縮）を示す。図５において、実線は、本発明による画像圧縮の特性を示し、点線は、比較例として公知のＪＰＥＧによる画像圧縮の特性を示す。図５から、本発明の画像圧縮によれば、同じ圧縮率で常にＪＰＥＧよりも美しい圧縮となることが分かる。
【００６６】
また、行列Ｔの特異値がばらつくならば、特異値分解を倍精度、単精度、整数演算のいずれで求めてもＰＳＮＲ値はほとんど変わらない（表３参照）。
【００６７】
【表３】
2008042335.tif 000017
もちろん整数演算するのが最も高速で、かつ情報量を削減（より圧縮できる）できるが、近接あるいは重複特異値が存在する場合は倍精度演算のときよりもＰＳＮＲ値の悪化する可能性が高い。そのため、特に整数演算で画像圧縮を行う際には、提案アルゴリズムを多分割化に利用すべきであると考える。
【００６８】
ＳＰＨＩＴのほかにＥＺＷによる符号化もあり、それらをランレングス符号化やシャノン符号（ハフマン符号、算術符号など）により符号化することでデータはさらに圧縮される。また、ＬＺ７７を基本アルゴリズムとするＬＨＡ、ｇｚｉｐ、ｂｚｉｐ２、ＺＩＰ、ＣＡＢ、７ｚ、ＲＡＲ、ＣＡＢ、ＤＧＣＡ、ＧＣＡなどを併用しても圧縮される。
【００６９】
６．画像圧縮方法の詳細
以下、図６〜図１６を参照して、ｌ×ｍ画像行列Ｘで表される画像を圧縮する方法を詳細に説明する。なお、ｌ×ｍ画像行列Ｘで表される画像は、グレースケール画像でもよいし、カラー画像でもよい。
【００７０】
図６は、本発明の画像圧縮方法の処理の手順を示すフローチャートである。この処理は、任意のプロセッサによって実行され得る。
【００７１】
ステップＳ６１：原画像Ｘは、多分割画像ＸＭに変換される（多分割化：Ｘ→ＸＭ）。ここで、原画像Ｘは、ｌ×ｍ行列の形式で表される（以下、ｌ×ｍ画像行列Ｘという）。多分割画像ＸＭは、ｋ２分割を少なくとも１回実行することによって得られる画像であり、行列の形式で表される（以下、多分割画像行列ＸＭという）。ここで、ｋは２以上の任意の整数であり、ｌ、ｍはｋの任意の倍数である。多分割画像ＸＭを得ることは、原画像Ｘの特徴抽出を行うことにほかならない。ステップＳ６１を包含する画像特徴抽出方法もまた本発明の範囲内である。
【００７２】
ステップＳ６２：多分割画像行列ＸＭに対してデータ圧縮処理を行うことにより、圧縮画像行列ＸＣｏｍが得られる（データ圧縮：ＸＭ→ＸＣｏｍ）。
【００７３】
ここで、ステップＳ６１への入力である画像行列Ｘ、ステップＳ６１からの出力であり、かつ、ステップＳ６２への入力である多分割画像行列ＸＭ、ステップＳ６２からの出力である圧縮画像行列ＸＣｏｍは、いずれも、任意の記憶装置（媒体）に格納され得る。
【００７４】
図７は、多分割化処理（図６のステップＳ６１）の手順を示すフローチャートである。
【００７５】
ステップＳ７２において、画像行列Ｘｎをｋ２分割することにより画像行列Ｘｎ＋１を生成する処理が少なくとも１回実行される。ここで、ｎ＝０，１，・・・，ｎｍａｘ−１であり、Ｘ０＝Ｘである。
【００７６】
ここで、分割回数ｎ、画像行列Ｘｎは、いずれも、任意の記憶装置（媒体）に格納され得る。
【００７７】
図８は、画像行列Ｘｎをｋ２分割することにより画像行列Ｘｎ＋１を生成する処理（図７のステップＳ７２）の手順を示すフローチャートである。ここでは、ｎ＝０の場合の処理を説明するが、ｎ＝１，・・・，ｎｍａｘ−１の場合も同様である。
【００７８】
ステップＳ８１：ｌ×ｍ画像行列Ｘに基づいて、ｋ２×（ｌｍ／ｋ２）行列Ｔが作成される。このステップは、上述したＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムの（１）〜（４）に対応する。
【００７９】
ステップＳ８２：Ｔの特異値σ１，σ２，・・・，σｋ＾２が計算される。ただし、σ１≧σ２≧・・・≧σｋ＾２である。
【００８０】
ステップＳ８３：ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かが判定される。ここで、εはマシンイプシロン以上の定数を示す。ステップＳ８３における判定結果が「Ｙｅｓ」である場合には、処理はステップＳ８４に進む。ステップＳ８３における判定結果が「Ｎｏ」である場合には、処理はステップＳ８５に進む（ステップＳ８５、Ｓ８６において、拡大行列Ｔαの特異値σ１，σ２，・・・，σｋ＾２が計算される）。
【００８１】
ステップＳ８４：Ｔ＝ＵＳＶＴとなるＵのみが求められる。ただし、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），Ｕは直交行列、Ｖは直交行列とする。
【００８２】
ステップＳ８５：行列Ｔが拡大行列Ｔαに変換される。拡大行列Ｔαは、画像行列Ｘの少なくとも一辺の少なくとも一部に付けられるふちと行列Ｔとに基づいて生成される。ふちは、少なくともｋピクセル×ｋピクセルのサイズを有する。ふちに属するピクセルの値はランダム値（もしくは、実質的にランダムな値）である。
【００８３】
ステップＳ８６：Ｔαの特異値σ１，σ２，・・・，σｋ＾２が計算される。ただし、σ１≧σ２≧・・・≧σｋ＾２である。このＴαの特異値がステップＳ８３に入力される（ステップＳ８３において、ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かが再び判定される）。
【００８４】
その結果、ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するまで、ステップＳ８５、Ｓ８６が繰り返される。
【００８５】
ステップＳ８７：行列Ｔ１＝ＵＴＴが求められる。行列Ｔ１は、特徴抽出行列と呼ばれる。
【００８６】
ステップＳ８８：行列Ｔ１に基づいて、画像行列Ｘ１が作成される。画像行列Ｘ１は、行列Ｘをｋ２分割することによって得られる行列である。このステップは、上述したＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムの（６）〜（７）に対応する。
【００８７】
ここで、画像行列Ｘ、行列Ｔ１、行列Ｓ、特異値σ１，σ２，・・・，σｋ＾２、拡大行列Ｔα、直交行列Ｕ、ｋ２分割画像行列Ｘ１、特徴抽出行列Ｔ１は、いずれも、任意の記憶装置（媒体）に格納され得る。
【００８８】
図９は、画像行列Ｘｎをｋ２分割することにより画像行列Ｘｎ＋１を生成する処理（図７のステップＳ７２）の別の手順を示すフローチャートである。ここでは、ｎ＝０の場合の処理を説明するが、ｎ＝１，・・・，ｎｍａｘ−１の場合も同様である。
【００８９】
ステップＳ９１：ｌ×ｍ画像行列Ｘに基づいて、ｋ２×（ｌｍ／ｋ２）行列Ｔが作成される。このステップは、上述したＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムの（１）〜（４）に対応する。
【００９０】
ステップＳ９２：Ｔの特異値分解Ｔ＝ＵＳＶＴが求められる。ただし、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ^２は、σ１≧σ２≧・・・≧σｋ^２を満たすＴの特異値、Ｕは直交行列、Ｖは直交行列とする。
【００９１】
ステップＳ９３：ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かが判定される。ここで、εはマシンイプシロン以上の定数を示す。ステップＳ９３における判定結果が「Ｙｅｓ」である場合には、処理はステップＳ９４に進む。ステップＳ９３における判定結果が「Ｎｏ」である場合には、処理はステップＳ９５に進む（ステップＳ９５、Ｓ９６において、拡大行列Ｔαの特異値分解が実行される）。
【００９２】
ステップＳ９４：行列Ｔ１＝ＵＴＴが求められる。行列Ｔ１は、特徴抽出行列と呼ばれる。
【００９３】
ステップＳ９５：行列Ｔが拡大行列Ｔαに変換される。拡大行列Ｔαは、画像行列Ｘの少なくとも一辺の少なくとも一部に付けられるふちと行列Ｔとに基づいて生成される。ふちは、ふちは、少なくともｋピクセル×ｋピクセルのサイズを有する。ふちに属するピクセルの値はランダム値である。
【００９４】
ステップＳ９６：Ｔαの特異値分解Ｔα＝ＵＳＶＴが求められる。ただし、Ｓ＝ｄｉａｇ（σ１，σ２，・・・，σｋ＾２），σ１，σ２，・・・，σｋ＾２は、σ１≧σ２≧・・・≧σｋ＾２を満たすＴαの特異値、Ｕは直交行列、Ｖは直交行列とする。このＴαの特異値がステップＳ９３に入力される（ステップＳ９３において、ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するか否かが再び判定される）。
【００９５】
その結果、ｍｉｎｊ｜σｊ−σｊ−１｜＞εが成立するまで、ステップＳ９５、Ｓ９６が繰り返される。
【００９６】
ステップＳ９７：行列Ｔ１に基づいて、画像行列Ｘ１が作成される。画像行列Ｘ１は、行列Ｘをｋ２分割することによって得られる行列である。このステップは、上述したＫａｋａｒａｌａ−Ｏｇｕｎｂｏｎａアルゴリズムの（６）〜（７）に対応する。
【００９７】
ここで、画像行列Ｘ、行列Ｔ１、行列Ｓ、特異値σ１，σ２，・・・，σｋ＾２、拡大行列Ｔα、直交行列Ｕ、ｋ２分割画像行列Ｘ１、特徴抽出行列Ｔ１は、いずれも、任意の記憶装置（媒体）に格納され得る。
【００９８】
なお、ＴおよびＴαの特異値分解は、浮動小数点演算で行われてもよい。あるいは、Ｔおよび前記Ｔαの特異値分解は、整数演算で行われてもよい。
【００９９】
図１０は、ｌ×ｍ画像行列Ｘに基づいてｋ２×（ｌｍ／ｋ２）行列Ｔを作成する処理（図８のステップＳ８１および図９のステップＳ９１）を模式的に示す。
【０１００】
図１１は、行列Ｔを拡大行列Ｔαに変換する処理（図８のステップＳ８５および図９のステップ９５）を模式的に示す。
【０１０１】
図１２は、行列Ｔ１に基づいて画像行列Ｘ１を作成する処理（図８のステップＳ８８および図９のステップＳ９７）を模式的に示す。
【０１０２】
なお、図８のステップＳ８５および図９のステップＳ９５において、画像行列Ｘのふちは、画像行列Ｘのすべての辺に付けられる必要はなく、画像行列Ｘの少なくとも一辺に付けられてもよい。さらに、画像行列Ｘのふちは、画像行列Ｘの少なくとも一辺の全部に付けられる必要はなく、画像行列Ｘの少なくとも一辺の少なくとも一部に付けられてもよい。
【０１０３】
図１３は、画像行列Ｘがｌ×ｍ行列である場合において、画像行列Ｘに付けられるふちのパターンのバリエーションを示す。図１３において黒塗り部分がふちに相当する。ｋ２分割化が行われる場合には、少なくともｋピクセル×ｋピクセルのサイズを有するふちが画像行列Ｘに付けられればよい。
【０１０４】
なお、画像行列Ｘに付けるふちに属するピクセルの値をどのような値にするかは重要であるが、画像行列Ｘのどの位置にふちを付けるかは重要ではない。図１４の矢印に示されるようにふちの位置を移動させたとしても同じ結果になるからである。ふちに属するピクセルの値は、例えば、ランダム値である。あるいは、ふちに属するピクセルの値は、実質的にランダムな値（例えば、擬似ランダム値）であってもよい。
【０１０５】
なお、図６に示されるステップＳ６１において行われる多分割化処理は、図８に示されるｋ２分割化処理とウェーブレット変換などの既知のｋ２分割化処理とを併用することによって行われてもよいし、図９に示されるｋ２分割化処理とウェーブレット変換などの既知のｋ２分割化処理とを併用することによって行われてもよい。
【０１０６】
なお、図６に示されるステップＳ６２において行われるデータ圧縮処理は、分割された領域の画像の類似性を利用して行われることが好ましい。上述したように、ｋ２分割化をｎ回繰り返すと、大きさは異なるが類似した特徴が抽出されるｎ箇所の領域が（ｋ２−１）組現れる。例えば、図１５は、４分割化を３回繰り返した場合において、類似した特徴が抽出される領域を同一の丸付き数字で表したものである。図１５の例では、３つの領域（１）の画像が類似した画像となり、３つの領域（２）の画像が類似した画像となり、３つの領域（３）の画像が類似した画像となる。このような領域間の画像の類似性を利用することにより、多分割画像行列ＸＭを単純に保存する場合に比べて必要とされるデータ量を削減することができる。このような領域間の画像の類似性を利用する方法としては、例えば、画素値の差分値を保存するようにしてもよいし、本来１６桁の倍精度数で保存しなければならないが、類似性が高ければ単純に０を保存するようにしてもよい。このようなデータ圧縮処理は、例えば、ＳＰＨＩＴやＥＺＷによって実現することができる。
【０１０７】
さらに、ランレングス符号化やシャノン符号（ハフマン符号，算術符号など）により符号化することでデータを圧縮するようにしてもよい。また、ＬＺ７７を基本アルゴリズムとするＬＨＡ、ｇｚｉｐ、ｂｚｉｐ２、ＺＩＰ、ＣＡＢ、７ｚ、ＲＡＲ、ＣＡＢ、ＤＧＣＡ、ＧＣＡなどを併用してデータを圧縮するようにしてもよい。
【０１０８】
さらに、上述した実施形態では、ｌ×ｍ画像行列Ｘ（ｋは２以上の任意の整数、ｌ、ｍはｋの任意の倍数）を用いて、ｋの倍数である縦横サイズを有する画像の特徴を抽出する例を説明したが、本発明はこれに限定されない。ｋの倍数でない縦横サイズを有する画像の特徴を抽出する場合には、例えば、画像行列の下側または左側に適切な数の行または列を追加することにより、ｋの倍数である縦横サイズを有する画像を作成し、その画像の特徴を抽出するようにすればよい。追加する行または列に属するピクセルの値は、例えば、０である。このようにして特徴抽出された画像から追加した行または列に対応する部分を取り除くことにより、所望の結果を得ることができる。あるいは、適切な数の行または列を追加する代わりに、適切な数の行または列を削除することによって、ｋの倍数である縦横サイズを有する画像を作成し、その画像の特徴を抽出するようにすればよい。
【０１０９】
さらに、上述した実施形態では、画像行列Ｘをｋ２分割化する例を説明したが、画像行列Ｘをいくつかの領域に分割して、各領域について独立にｋ２分割化を行うようにしてもよい。この場合、各領域における分割数は同一である必要はなく異なっていてもよい。例えば、図１６に示されるように、画像行列Ｘを８つの領域（領域（１）〜領域（８））に分割して、領域（１）について２２分割化、領域（２）について３２分割化・・・を行っていもよい。また、各領域におけるｋ２分割化を並列に実行するようにしてもよい。
【０１１０】
以上のように、本発明の好ましい実施形態を用いて本発明を例示してきたが、本発明は、この実施形態に限定して解釈されるべきものではない。本発明は、特許請求の範囲によってのみその範囲が解釈されるべきであることが理解される。当業者は、本発明の具体的な好ましい実施形態の記載から、本発明の記載および技術常識に基づいて等価な範囲を実施することができることが理解される。
【産業上の利用可能性】
【０１１１】
本発明は、同一の圧縮率で常にＪＰＥＧよりも美しい圧縮を実現することが可能な画像圧縮方法およびそれに適した画像特徴抽出方法等を提供するものとして有用である。
【図面の簡単な説明】
【０１１２】
【図１】（ａ）は原画像の一例を示す図、（ｂ）は４分割画像の一例を示す図
【図２】５種類のテスト画像（３２ピクセル×３２ピクセル）を示す図であって、（ａ）は縦縞、（ｂ）は横縞、（ｃ）は斜め縞Ｉ、（ｄ）は斜め縞ＩＩ、（ｅ）はランダムを示す。
【図３】５種類の画像１００００個をそれぞれ４分割する際、特異値分解の対象となる行列Ｔがもつ特異値相互の最小ギャップｇａｐｍｉｎを示す図
【図４】４種類のふちあり画像１００００個をそれぞれ分割する際、特異値分解の対象となる行列Ｔがもつ特異値相互の最小ギャップｇａｐｍｉｎを示す図
【図５】原画像に対するファイルサイズ比と圧縮画像のＰＳＮＲ値との関係を示す図
【図６】本発明の画像圧縮方法の処理の手順を示すフローチャート
【図７】多分割化処理（図６のステップＳ６１）の手順を示すフローチャートである。
【図８】画像行列Ｘｎをｋ２分割することにより画像行列Ｘｎ＋１を生成する処理（図７のステップＳ７２）の手順を示すフローチャート
【図９】画像行列Ｘｎをｋ２分割することにより画像行列Ｘｎ＋１を生成する処理（図７のステップＳ７２）の別の手順を示すフローチャート
【図１０】ｌ×ｍ画像行列Ｘに基づいてｋ２×（ｌｍ／ｋ２）行列Ｔを作成する処理（図８のステップＳ８１および図９のステップＳ９１）を模式的に示す図
【図１１】行列Ｔを拡大行列Ｔαに変換する処理（図８のステップＳ８５および図９のステップ９５）を模式的に示す。
【図１２】行列Ｔ１に基づいて画像行列Ｘ１を作成する処理（図８のステップＳ８８および図９のステップ９７）を模式的に示す図
【図１３】ｌ×ｍ画像行列に付けられるふちのパターンのバリエーションを示す図
【図１４】画像行列に付けられるふちの位置を移動した場合を説明するための図
【図１５】類似した特徴が抽出される分割領域の一例を示す図
【図１６】画像行列を複数の領域に分割して、各領域について独立にｋ２分割化を行う場合を説明するための図
【図６】
2008042335.tif 000018
【図７】
2008042335.tif 000019
【図８】
2008042335.tif 000020
【図９】
2008042335.tif 000021
【図１】
2008042335.tif 000022
【図２】
2008042335.tif 000023
【図３】
2008042335.tif 000024
【図４】
2008042335.tif 000025
【図５】
2008042335.tif 000026
【図１０】
2008042335.tif 000027
【図１１】
2008042335.tif 000028
【図１２】
2008042335.tif 000029
【図１３】
2008042335.tif 000030
【図１４】
2008042335.tif 000031
【図１５】
2008042335.tif 000032
【図１６】
2008042335.tif 000033