(57)【要約】【課題】  圧縮されていないデータを符号化するためにユニバーサル位置符号化方法及びシステム（１８）を提供する。【解決手段】  データ記号がビン部分及びｒａｗ部分に割り当てられ、データのツリー構造が利用される。トップ・ダウン手法は、データのビット深度に基づいてデータのツリーを初期化し、所定の分割条件に基づいてビンを分割して２つの別々のビンを形成し、終了条件に到達するまで分割段階を繰り返す、ことを含む。ボトム・アップ手法は、データのツリーを形成し、併合条件に基づいて２つの既存のビンを併合して新しいビンを形成し、終了条件に到達するまで併合段階を繰り返す、ことを含む。【選択図】      図１
2004177965.tif 000002
【特許請求の範囲】
【請求項１】
データを符号化する方法であって、
各々が複数のトップツリー記号を含む複数のトップツリービンからなるトップツリービン構造を前記データのビット深度に基づいて初期化し、
前記トップツリービンのいずれか１つを分割条件に基づいて２つの分割トップツリービンに分割し、
終了条件に到達するまで前記分割段階を繰り返し、
前記複数のトップツリービン及び前記複数の分割トップツリービンを用いて所望の前記ビン構造を生成する、
ことを含む方法。
【請求項２】
ゼロに等しいｒａｗを有するトップツリービンは分割されないことを特徴とする請求項１に記載の方法。
【請求項３】
前記複数のトップツリー記号の各々が前記圧縮されていないデータを表すことを特徴とする請求項１に記載の方法。
【請求項４】
前記分割条件が、前記複数のトップツリービンの各々を複数のチャイルド・トップツリービンに擬似的に分割することに基づいて定められ、前記分割段階が、
前記複数のチャイルド・トップツリービンの各々についてのビン情報を加え、
前記トップツリービンのうち、ビン情報における最小の増加に対応する前記複数のチャイルド・トップツリービンからなるものを分割する、
ことを含む請求項１に記載の方法。
【請求項５】
前記分割条件が最大損失に基づいて定められることを特徴とする請求項１に記載の方法。
【請求項６】
所定のビット深度を有する圧縮されていないデータを符号化する方法であって、
各々が複数のボトムツリー記号を含む複数のボトムツリービンからなるボトムツリービン構造を初期化し、
前記複数のボトムツリービンの少なくとも２つを併合条件に基づいて併合して、複数の併合ボトムツリービンが生成されるようにし、
終了条件に到達するまで前記併合段階を繰り返し、
前記複数のボトムツリービン及び前記複数の併合ボトムツリービンを用いて所望の前記ビン構造を生成する、
段階を含む方法。
【請求項７】
数学的演算を前記圧縮されていないデータに実行し、数学的逆演算を前記圧縮解除されたデータに実行することをさらに含む請求項６に記載の方法。
【請求項８】
数学的演算がウェーブレット変換演算であり、前記数学的逆演算が逆ウェーブレット変換演算である請求項６に記載の方法。
【請求項９】
所望のビン構造を生成するためのユニバーサル位置符号化システム（１８）を備えるデータ符号化システム（１０）であって、前記ユニバーサル位置符号化システムが、
ツリーのビン構造を初期化するように構成された初期化ブロック（１４）と、
前記初期化ブロックに連結され、前記ツリー・ビン構造及び前記圧縮されていないデータを処理して前記所望のビン構造を生成するように構成された処理ブロック（１６）と、
を含むデータ符号化システム（１０）。
【請求項１０】
前記初期化ブロックが、各々が複数のトップツリー記号を含む複数のトップツリービンからなるトップツリービン構造（５０）を初期化し、
前記処理ブロックが、複数のトップツリービンのいずれか１つを分割条件に基づいて分割して、複数の分割トップツリービンを生成し、
前記処理ブロックが、終了条件に到達するまで前記複数のトップツリービンをさらに分割し、
前記処理ブロックが、前記複数のトップツリービン及び前記複数の前記分割トップツリービンを用いて、前記所望のビン構造を生成する、
請求項９に記載のデータ符号化システム。
【請求項１１】
圧縮されていないデータを符号化するようにコンピュータシステムに命令するためのコンピュータ用の命令を格納するコンピュータ可読媒体であって、前記コンピュータ用の命令が、
ツリーのビン構造を初期化し、
前記ツリーのビン構造及び前記圧縮されていないデータを処理して前記所望のビン構造を生成する、
ことを含むコンピュータ可読媒体。
【請求項１２】
各々が複数のトップツリー記号を含むトップツリービンからなるトップツリー構造を初期化し、
前記複数のトップツリービンの前記いずれか１つを分割条件に基づいて分割して複数の分割トップツリービンを生成し、
終了条件に到達するまで前記複数のトップツリービンをさらに分割し、
前記複数のトップツリービン及び前記複数の分割トップツリービンを用いて所望のビン構造を生成する、
請求項１１に記載のコンピュータ可読媒体。
【請求項１３】
圧縮されていないデータが符号化されるように所望のビン構造を生成する方法であって、
ツリーのビン構造を初期化し、
前記ツリーのビン構造及び前記圧縮されていないデータを処理して前記所望のビン構造を生成する、
ことを含む方法。
【請求項１４】
各々が複数のトップツリー記号を含む複数のトップツリービンからなるトップツリービン構造を、前記データのビット深度に基づいて初期化し、
前記トップツリービンのいずれか１つを分割条件に基づいて２つの分割トップツリービンに分割し、
終了条件に到達するまで、前記分割段階を繰り返し、
前記複数のトップツリービン及び前記複数の分割トップツリービンを用いて前記所望のビン構造を生成する、
ことをさらに含む請求項１３に記載の方法。
【請求項１５】
圧縮されていないデータを符号化するシステムであって、
ツリーのビン構造を初期化する手段と、
前記ツリー・ビン構造及び前記圧縮されていないデータを処理して所望のビン構造を生成する手段と、
を備えることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にデータの符号化に関し、より具体的には、データを符号化及び圧縮するシステム及び方法に関する。
【背景技術】
【０００２】
圧縮とは、最小のビット数を用いてデータを表すことを指す。概して、データの圧縮には２種類あり、すなわち、有損失圧縮と無損失圧縮である。データの無損失圧縮とは、圧縮解除されたときにどのようなデータも損失すること無く完全に復元できるものをいう。通常は、多くの用途、特に医療用画像においては、無損失圧縮が望ましい。
【０００３】
典型的には、医療用画像は、高いダイナミックレンジと大きな空間的寸法からなる。符号化システムの設計は、医療用画像の場合と同様に、符号化されるべきデータのダイナミックレンジが比較的大きい場合により複雑である。このような場合においては、計算コストが低く、良好な圧縮率を有する符号化及び圧縮技術を設計することが望ましい。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
したがって、大量のデータの符号化に用いることができ、複雑さが少なく良好な圧縮率を維持する符号化技術を提供することが望ましい。
【課題を解決するための手段】
【０００５】
要約すると、本技術の好ましい実施形態において、圧縮されていないデータを符号化するためのユニバーサル位置符号化方法が説明される。この方法は、データを符号化するために所望のビン構造を生成することを含む。所望のビン構造は、２つの手法を用いて生成される。一実施形態においては、トップ・ダウン手法は、データのビット深度に基づいてデータのツリーを初期化し、所定の分割条件に基づいてビンを分割して２つの別々のビンを形成し、終了条件に到達するまで分割段階を繰り返すことを含む。別の実施形態においては、ボトム・アップ手法は、データのツリーを形成し、併合条件に基づいて２つの既存のビンを併合して、新しいビンを形成し、終了条件に到達するまで併合段階を繰り返すことを含む。
【０００６】
本発明の別の態様においては、データを符号化するためのデータ符号化システムが提供される。データ符号化システムは、データのツリー構造をトップ・ダウン又はボトム・アップ手法で利用するユニバーサル位置符号化システムを備える。ユニバーサル位置符号化システムは、エントロピー・エンコーダのためのプリプロセッサである。エントロピー・エンコーダは圧縮されていないデータ及び所望のビン構造を受け取り、該所望のビン構造を用いて該圧縮されていないデータをコード化して圧縮データを生成する。
【発明を実施するための最良の形態】
【０００７】
本発明のこれら及び他の特徴、態様、及び利点は、同じ符号が図面全体にわたって同じ部分を表す添付図面を参照して、以下の詳細な説明を読むことにより、一層よく理解されるであろう。
【０００８】
図１は、本発明の好ましい実施形態により実施されたデータ符号化システム１０のブロック図である。データ符号化システム１０は、数学的演算ブロック１２、ユニバーサル位置符号化システム１８、エントロピー・エンコーダ２４、エントロピー・デコーダ２２、及び数学的演算ブロック２０を備えるものとして示される。各々のブロックについては、以下に詳細に説明される。
【０００９】
ユニバーサル位置符号化システム１８は、圧縮されていないデータを変換ブロック１２から受け取り、所望のビン構造が生成されるように、最初のビン構造を用いてこの圧縮されていないデータを処理する。図示された実施形態においては、ユニバーサル位置符号化システムは初期化ブロック１４及び処理ブロック１６を備える。
【００１０】
エントロピー・エンコーダ２４は、ユニバーサル位置符号化システム１８に連結され、圧縮されていないデータ及び所望のビン構造を受け取る。エントロピー・エンコーダは、対応する圧縮データが生成されるように、所望のビン構造を用いて圧縮されていないデータをコード化する。エントロピー・エンコーダはさらに、圧縮データ及び所望のビン構造を表すデータを含むデータファイルを生成する。
【００１１】
エントロピー・デコーダ２２は、エントロピー・エンコーダに連結され、該エントロピー・エンコーダにより生成されたデータファイルを受け取る。エントロピー・エンコーダからのデータ、より一般的には、ここで説明される種々の機能構成要素間で交換されたデータは、通常の「ファイル」又はここに説明されるようにアクセスされかつ処理可能な他の形態のいずれかのような、適切な方法でフォーマットすることができることに留意されたい。エントロピー・デコーダは、対応する圧縮解除されたデータが生成されるように、所望のビン構造を表すデータを用いて圧縮データを復号する。
【００１２】
図示されるように、データ符号化システム１０は、数学的演算ブロック１２及び数学的逆演算ブロック２０を備える。数学的演算ブロック１２は、エントロピー・エンコーダブロック２４に連結され、圧縮されていないデータ上で数学的演算を実行する。圧縮されていないデータ上で数学的演算を実行することにより、ユニバーサル位置符号化システムは、特定のルールに基づいて繰り返し最初のビン構造を更新し、該圧縮されていないデータの符号化に用いることができる所望のビン構造を生成する。一実施形態において、数学的演算ブロックは、任意的なウェーブレット変換演算を圧縮されていないデータ上で実施する。
【００１３】
数学的逆演算ブロック２０は、エントロピー・デコーダ２２に連結され、該エントロピー・デコーダにより生成された圧縮解除データを受け取る。数学的逆演算ブロックは、数学的逆演算を圧縮解除データ上で実行する。実施形態において、逆ウェーブレット変換演算が圧縮解除されたデータ上で実施される。
【００１４】
実施形態において、圧縮されていないデータは、圧縮解除されたデータと等価である。したがって、データ符号化システムは、損失すること無く圧縮されていないデータを復元し、すなわち、無損失復元が行われる。例示的な実施形態においては、圧縮されていないデータは、３Ｄ画像、ビデオ画像などを含む画像に相当する。
【００１５】
引き続きユニバーサル位置符号化システムを参照すると、圧縮されていないデータは所望のビン構造が生成されるように処理される。所望のビン構造を生成する方法は、以下に図２及び図３を参照して説明される。
【００１６】
図２は、本発明の一実施形態により所望のビン構造を生成する方法を示すフローチャートである。詳細には図２は、本発明の好ましい実施形態によるユニバーサル位置符号化に対するトップ・ダウン手法を示す。このプロセスは、段階３０で始まり、制御は直ちに段階３２に進む。各段階については以下に詳細に説明される。
【００１７】
段階３２において、トップツリービン構造が初期化される。トップツリービン構造は、幾つかのトップツリービンを備える。各々のトップツリービンは、幾つかのトップツリー記号を含む。実施形態において、トップツリー記号は、圧縮されていないデータを表す。図示された実施形態においては、初期化ブロック１４がトップツリービン構造を初期化する。実施形態において、トップツリービンは、以下のフィールドを備える。
【００１８】
「ｒａｎｇｅ＿ｓｔａｒｔ」は、ビンにおける最初の記号を表し、「ｒａｎｇｅ＿ｅｎｄ」は該ビンにおける最後の記号を表し、「ｒａｎｇｅ」は記号の総数を表す（大きさのみ）。「ｒａｗ」はビンにおける各々の記号を一意的に表すのに必要とされるビットを表す。「ｃｏｕｎｔ」はビンにおけるすべての記号の発生総数を表し、「ｌｏｓｓ」はビンにおけるすべての記号を表すのに必要とされるビットの合計を表す。数学的には、
Ｒａｎｇｅ＝（ｒａｎｇｅ＿ｅｎｄ−ｒａｎｇｅ＿ｓｔａｒｔ＋１）
Ｒａｗ＝ｌｏｇ2（ｒａｎｇｅ）
符号付きの記号（例えば、＋２又は−２を表す記号）については
Ｒａｗ＝ｌｏｇ２（２＊ｒａｎｇｅ）、及び
Ｌｏｓｓ＝ｃｏｕｎｔ＊ｒａｗ
である。
【００１９】
一般に、ビンにおける記号は整数値であり、したがって、ビンは連続する記号を表す。
【００２０】
所望のビン構造を設計する際に用いられる他のパラメータが以下に説明される。
【００２１】
Ｐiがｉ番目のビンであり、ＰimがＰiのｍ番目のチャイルドである場合には、ビンＰiについてのビン情報Ｐi．ｂｉは、
【００２２】
【数１】
2004177965.tif 000003
【００２３】
により与えられる。
【００２４】
同様に、ｉ番目ビンのビットバジェットＰi．ｂｂは、
Ｐi．ｂｂ＝Ｐi．ｂｉ＋Ｐl．ｌｏｓｓ
として表され、合計ビットバジェットは、
【００２５】
【数２】
2004177965.tif 000004
【００２６】
として与えられる。
【００２７】
段階３４において、トップツリービンのいずれか１つが、分割条件に基づいて、少なくとも２つの分割トップツリービンに分割される。図示される実施形態においては、処理ブロック１６が段階３４を実行する。この分割条件は、様々な要因に基づくものとすることができる。
【００２８】
一実施形態においては、分割条件は最小ビン情報に対応するトップツリービン構造のトップツリービンを分割することに対応する。最小のビン情報に対応するトップツリービンは、
ａｒｇiｍｉｎＰi．ｂｉ
として表される。
【００２９】
ここで、
ａｒｇiｍｉｎＰi．ｂｉ
は、「ｉ」がこの引数（指数）において量が最小値をとる考慮中の量の引数（指数）であることを意味する。この場合においては、「ｉ」はトップツリービン構造Ｓにおける他のすべてのビンと比較すると、最小のビン情報を有するビンに対応するビンの数である。
【００３０】
或いは、分割条件は、最初に前述の複数のトップツリービンの各々を幾つかのチャイルド・トップツリービンに擬似的に分割し、該チャイルド・トップツリービンの各々のビン情報を付加し、続いてビン情報における最小の増加に対応する幾つかのチャイルド・トップツリービンからなるトップツリービンを分割することにより求められる。図示される実施形態においては、トップツリービンは２つのチャイルド・トップツリービンに分割される。ビン情報における最小の増加に対応するビンは、擬似的な分割の後、以下の式を用いて計算される。
【００３１】
【数３】
2004177965.tif 000005
【００３２】
別の実施形態においては、分割条件は、トップツリービンのうち、損失における最大の減少に対応するビンを分割することに対応する。損失が最大の減少となるものに対応するトップツリービンは、
ａｒｇiｍａｘＰi．ｌｏｓｓ
として与えられる。
【００３３】
或いは、分割条件は、トップツリービンの各々を幾つかのチャイルド・トップツリービンに擬似的に分割し、該チャイルド・トップツリービンの各々の損失を付加し、続いて損失における最大の減少に対応するチャイルド・トップツリービンからなるトップツリービンを分割することにより求めることができる。損失における最大の減少に対応するトップツリービンは、
【００３４】
【数４】
2004177965.tif 000006
【００３５】
として与えられる。
【００３６】
別の実施形態においては、分割条件は最大ビットバジェットに対応するトップツリービンの１つを分割することに対応する。最大ビットバジェットに対応するトップツリービンは、
ａｒｇiｍａｘ[Ｐi．ｌｏｓｓ＋Ｐi．ｂｉ]
として表される。
【００３７】
或いは、分割条件は、トップツリービンの各々を複数のチャイルド・トップツリービンに擬似的に分割し、続いてビットバジェットにおける最大の減少に対応するチャイルド・トップツリービンからなるトップツリービンの１つを分割することにより求めることができる。ビットバジェットにおける最大の減少に対応するトップツリービンは、
【００３８】
【数５】
2004177965.tif 000007
【００３９】
として与えられる。
【００４０】
分割のための各々の基準を選択する場合に種々のトレードオフが存在する。この基準は、ビンに直接作用する演算、及び／又は、擬似的にビンを分割した後にビンに作用する演算にカテゴリ化することができる。例えば、ビンに直接作用する前者の基準は、計算をそれほど必要とせず、各々のビンについての情報を有するテーブルをソートすることにより行うことができる。後者の基準においては、追加の計算が必要となるが、より良い結果が得られる。さらに、この基準は、ビン情報、損失、及びビットバジェットに基づいて分類することができる。ビン情報に基づいた基準において、ビンのエントロピーが考慮される。エントロピー・エンコーダがこの基準を駆動する。この基準は損失がわずかなものである場合に有利であり、有損失圧縮設定において用いられることが多い。しかしながら、ビン情報の計算は、対数計算のような比較的複雑な演算を必要とする。損失に基づいた基準は、単純な乗法及びビン構造の適切なフィールドを更新することにより行うことができるため複雑さが少ない。一方、ビットバジェットに基づく基準は、計算上複雑である。
【００４１】
最後に、対数の計算上の複雑さ、所望の圧縮率、及びエントロピー・コーダに基づいて、適切な基準が選択される。
【００４２】
図示される実施例において、符号付き及び符号なしデータの両方について、第１のトップツリービンは常にトップツリー記号「０」を含む。ゼロに等しいｒａｗを有するトップツリービンは分割することができず、トップツリービンの分割はその中に等しい記号の数を有する２つの新しい分割トップツリービンを生じし（これは、選択された最初のトップツリービン構造に起因する）、該トップツリービンにおける記号の数は２の累乗である。
【００４３】
トップツリービンを分割するプロセスは、段階３６において示されるように終了条件に到達するまで継続される。終了条件は、以下の方法により決定することができる。
【００４４】
実施形態において、終了条件は前述の複数のトップツリービンに基づいて決定される。終了条件はさらに、複数のトップツリー記号の係数である歪み量に基づいて定めることができる。終了条件はさらに、圧縮率に基づいて定めることができる。或いは、終了条件はトップツリービンと圧縮率とに基づいて定めることができる。
【００４５】
段階３８において、最初のトップツリービン構造を用い、上述のように該トップツリービンを分割することにより所望のビン構造が生成される。好ましい実施形態においては、所望のビン構造は、分割されなかったトップツリービン及びそれ以上分割されなかった分割トップツリービンを含む。
【００４６】
図２の各段階が実施される方法を示す実施例を以下に説明する。４ビットのデータ（すなわち、ビット深度が４に等しい）が次のシーケンス「２２３４７００１０２２３７」により表される。この４ビットのデータは、図３に示される４つのビン５４、５６、５８、及び６０で表される。ビン５４はトップツリー記号０を、ビン５６はトップツリー記号１を、ビン５８はトップツリー記号２ないし３を、ビン６０はトップツリー記号４ないし７を含む。各々のビンにおけるフィールドについては以下に記される。
【００４７】
ビン５４において、ｒａｎｇｅ＿ｓｔａｒｔは０、ｒａｎｇｅ＿ｅｎｄは０、ｒａｎｇｅは１、ｒａｗは０、ｃｏｕｎｔは３、ｌｏｓｓは０である。同様に、ビン５６においては、ｒａｎｇｅ＿ｓｔａｒｔは１、ｒａｎｇｅ＿ｅｎｄは１、ｒａｎｇｅは１、ｒａｗは０、ｃｏｕｎｔは１、ｌｏｓｓは０である。ビン５８においては、ｒａｎｇｅ＿ｓｔａｒｔは２、ｒａｎｇｅ＿ｅｎｄは３、ｒａｎｇｅは２、ｒａｗは２、ｃｏｕｎｔは６、ｌｏｓｓは６である。ビン６０においては、ｒａｎｇｅ＿ｓｔａｒｔは４、ｒａｎｇｅ＿ｅｎｄは７、ｒａｎｇｅは４、ｒａｗは２、ｃｏｕｎｔは３、ｌｏｓｓは６である。この実施例においては、ビンの総数はビット深度に１を足したものと等しいことが分かる。
【００４８】
図３は、最初のトップツリー構造５０を表す。トップツリー構造は、４つのトップツリービン５４、５６、５８、及び６０からなり、すべてがノード５２から始まる。したがって、トップツリービン５８は、図４に示されるように、ノード６６において集合する分割トップツリービン６２及び６４に分割される。分割条件に基づいて、分割トップツリービンは、図５に示されるように、さらに分割トップツリービン６８及び７０に分割される。したがって、生成される所望のビン構造は、トップツリービン５４、５６、及び６０と、分割トップツリービン６４、６８、及び７０とをそれぞれ含む。
【００４９】
別の実施形態においては、ユニバーサルな位置符号化に対するボトム・アップ手法が用いられる。この代替的な手法は、図６ないし図１０を参照して以下に説明される。
【００５０】
図６は、ボトム・アップ手法を用いて所望のビン構造を生成する方法を示すフローチャートである。このプロセスは、段階８０で始まり、制御は直ちに段階８２に進む。各々の段階については以下に詳細に説明される。
【００５１】
段階８２において、最初のボトムツリー構造が初期化される。ボトムツリービン構造は、複数のボトムツリービンからなる。ボトムツリービンの各々は、幾つかのボトムツリー記号を備える。実施形態において、ボトムツリー記号は圧縮されていないデータを表す。図示される実施形態においては、初期化ブロック１４がボトムツリービン構造を初期化する。実施形態において、ボトムツリービンはトップツリービンに関して説明されたものと同じフィールドを備える。
【００５２】
段階８４において、任意の２つのボトムツリービンが、併合条件に基づいて、少なくとも１つの併合ボトムツリービンに併合される。図示される実施形態においては、処理ブロック１６が段階８４を実行する。併合条件は、様々な要因に基づくものとすることができる。種々の併合条件が以下に説明される。Ｐi:i+nは「ｉ」から始まる「ｎ」個の連続したビンを併合することにより形成されたビンであることに留意されたい。一般に、「ｎ」には２を選択する。
【００５３】
実施形態において、併合条件は、ビン情報における最大の減少に対応するボトムツリービンの２つを併合させることに対応する。ビン情報における最大の減少に対応するボトムツリービンは、
【００５４】
【数６】
2004177965.tif 000008
【００５５】
として与えられる。
【００５６】
別の実施形態においては、併合条件は、損失が最小の増加となるものに対応するボトムツリービンの２つを併合させることに対応する。損失が最小の増加となるものに対応するボトムツリービンは、
【００５７】
【数７】
2004177965.tif 000009
【００５８】
として与えられる。
【００５９】
さらに別の実施形態においては、併合条件は、ビットバジェットが最小の増加となるものに対応するボトムツリービンの２つを併合させることに対応する。ビットバジェットが最小の増加となるものに対応するボトムツリービンは、
【００６０】
【数８】
2004177965.tif 000010
【００６１】
として与えられる。
【００６２】
別の実施形態においては、併合条件は、最小のビン情報に対応するボトムツリービンの２つを併合させることに対応する。最小のビン情報に対応するボトムツリービンは、
【００６３】
【数９】
2004177965.tif 000011
【００６４】
として与えられる。
【００６５】
別の実施形態においては、併合条件は最小の損失に対応するボトムツリービンの２つを併合させることに対応する。最小の損失に対応するボトムツリービンは、
【００６６】
【数１０】
2004177965.tif 000012
【００６７】
として表される。
【００６８】
さらに別の実施形態においては、併合条件は最小のビットバジェットに対応する２つのボトムツリービンを併合させることに対応する。最小のビットバジェットに対応するボトムツリービンは、
【００６９】
【数１１】
2004177965.tif 000013
【００７０】
として表される。
【００７１】
ボトムツリービンを併合させるプロセスは、段階８６において示されるように終了条件に到達するまで継続される。終了条件は、以下の方法により決定することができる。
【００７２】
実施形態において、終了条件は、ボトムツリービンの数に基づいて決定される。別の実施形態において、終了条件は、前述のボトムツリーの記号の数の係数である歪み量に基づいて定められる。さらに別の実施形態においては、終了条件はボトムツリービンの数と圧縮率とに基づいて定められる。
【００７３】
段階８８において、ボトムツリービン及び併合ボトムツリービンを用いて所望のビン構造が生成される。実施形態において、所望のビン構造は、併合されなかったボトムツリービン及びそれ以上併合されなかった併合ボトムツリービンを含む。
【００７４】
図６の段階が実施される方法を示す実施例を以下に説明する。この例においては、圧縮されていないデータは４ビットのデータである。４ビットのデータは、図７に示されるように、１５のボトムツリービン１１０ないし１２４で表される。ビン１１０はボトムツリー記号３を、ビン１１１はトップツリー記号０を、ビン１１２はトップツリー記号−１を、ビン１１３はトップツリー記号１を、以下同様に含む。各々のビンにおけるフィールドについては、以下に記される。
【００７５】
この場合、図７は、最初のボトムツリー構造９４を表す。ボトムツリー構造は、１５のボトムツリービン１１０ないし１２４からなる。したがって、ボトムツリービン１２３及び１２４は、図８に示されるように、併合ボトムツリービン１２５に併合される。併合条件に基づいて、ボトムツリービン１２１及び１２２は、図９に示されるように、併合ボトムツリービン１２６に併合される。併合ボトムツリービン１２５及び１２６は、図１０に示されるように、さらに併合されて併合ボトムツリービン１２７が形成される。このように所望のビン構造が生成され、ボトム１１０ないし１２０及び１２７を含む。上記の実施形態においては、所望のビン構造の生成は、トップツリービン構造又はボトムツリービン構造のいずれかを用いて説明された。或いは、当業者であれば、所望のビン構造をトップツリービン構造法及びボトムツリービン構造法の組み合わせを用いて生成することができることを理解されるであろう。
【００７６】
所望のビン構造を生成する上記の方法は、コンピュータシステムを用いて実施することができる。コンピュータシステムを用いて所望のビン構造を生成する方法を以下にさらに詳細に説明する。
【００７７】
図１１は、上記の方法において説明されたような、データを符号化するための所望のビン構造を生成するのに用いることができる汎用コンピュータシステム１０の概略図を示す。コンピュータシステム１３０は一般に、少なくとも１つのプロセッサ１３２、メモリ、入力／出力装置１３６、及び該プロセッサ、メモリ、及び入力／出力装置に接続するデータ経路（例えば、バス）１４６を備える。プロセッサ１３２は、メモリ１３４からの命令及びデータを受け取り、ユニバーサルな位置の符号化のような種々の動作を実行する。プロセッサ１３２は、算術及び論理演算を実行する算術論理演算ユニット（ＡＬＵ）、及びメモリ１３４からの命令を抽出し、これらを復号して実行し、必要に応じてＡＬＵを呼び出す制御ユニットを含む。メモリ１３４は、一般に、ランダム・アクセス・メモリ（ＲＡＭ）及び読み出し専用メモリ（ＲＯＭ）を含むが、プログラム可能な読み出し専用メモリ（ＰＲＯＭ）、電気的消去書込み可能な読出し専用メモリ（ＥＥＰＲＯＭ）のような他の種類のメモリであってもよい。さらに、メモリ１３４は、プロセッサ１３２上で実行する演算システムを格納することが好ましい。演算システムは、入力を認識すること、出力を出力装置に送ること、ファイル及びディレクトリの記録をとること、及び種々の周辺機器を制御することを含む基本的なタスクを実行する。
【００７８】
入力／出力装置は、ユーザがデータ及び命令をコンピュータシステム１３０に入力できるようにするキーボード１３８及びマウス１３７を備えることができる。さらに、ディスプレイ１４０を用いて、ユーザがコンピュータの実行した結果を見ることを可能にする。他の出力装置としては、プリンタ、プロッタ、シンセサイザ、及びスピーカを含むことができる。電話又はケーブルモデム、或いはイーサネットアダプタ（「イーサネット」は商標）、ローカルエリアネットワーク（ＬＡＮ）アダプタ、総合デジタル通信網（ＩＳＤＮ）アダプタ、又はデジタル加入者線（ＤＳＬ）アダプタ等のネットワークカードのような通信装置１４２により、コンピュータシステム１３０が他のコンピュータや、ＬＡＮ又は広域エリアネットワーク（ＷＡＮ）のようなネットワーク上のリソースにアクセスすることが可能になる。
【００７９】
大容量記憶装置１４４は、コンピュータシステム１３０が恒久的に大量のデータを保持できるようにするために用いることができる。大容量記憶装置は、フレキシブルディスク、ハードディスク、及び光学ディスクのようなすべての種類のディスクドライブ、並びにデジタルオーディオテープ（ＤＡＴ）、デジタルリニアテープ（ＤＬＴ）、又は他の磁気的に符号化された媒体を含むことができる、テープにデータを読み書き可能なテープドライブを含むことができる。上述のコンピュータシステム１３０は、ハンドヘルド・デジタルコンピュータ、携帯情報端末、ノート型コンピュータ、パーソナルコンピュータ、ワークステーション、ミニコンピュータ、メインフレームコンピュータ、又はスーパーコンピュータの形態を取ることができる。
【００８０】
ここで上述されたように、データを符号化する方法は、医療用画像に適用することができる。図１２は、本発明の好ましい実施形態によるユニバーサルな位置の符号化を適用することができる例示的なイメージングシステムについての一般的な概観を与える。イメージングシステム１５０は、一般に、画像データ又は信号を検出し、該信号を有益なデータに変換するある種のイメージャ１５２を含む。より完全に以下に説明されるように、イメージャ１５２は画像データを生成するために、種々の物理的な原理にしたがって動作する。しかしながら、一般には、患者の関心領域を表す画像データは、写真フィルムのような通常の支持体又はデジタル媒体のいずれかにおいてイメージャにより生成される。
【００８１】
イメージャはシステム制御回路構成１５４の制御のもとで動作する。システム制御回路構成は放射線源制御回路、タイミング回路、患者又は移動テーブルと共にデータ収集を調整するための回路、放射線又は他の線源及び検出器の位置を制御するための回路などのような幅広い範囲の回路を含むことができる。
【００８２】
イメージャ１５２は、画像データ又は信号の収集に続いて、デジタル値への変換などのために該信号を処理し、該画像データをデータ収集回路構成１５６に転送することができる。写真フィルムのようなアナログ媒体の場合には、データ収集回路構成は一般に、フィルムのための支持体並びにフィルムを現像しハードコピーを生成するための装置を含むことができる。デジタルシステムにおいては、データ収集回路構成１５６は、デジタル・ダイナミックレンジの調整、データの平滑化又は鮮鋭化、並びに所望の場合には、データストリーム及びファイルのコンパイルのような幅広い初期処理機能を実行することができる。
【００８３】
次いでデータは、付加的な処理及び分析が実行されるデータ処理回路構成１５８に転送される。写真フィルムのような従来の媒体においては、データ処理回路構成はフィルムに文字情報を付加し、並びに、特定の注釈又は患者識別情報を付けることができる。利用可能な種々のデジタル・イメージングシステムにおいては、データ処理回路構成は大量のデータ分析、データの順序付け、鮮鋭化、平滑化、特徴認識などを実行する。
【００８４】
最終的に、画像データは観察及び分析のために、ある種のオペレータ・インタフェース１０６に転送される。観察の前に、画像データ上で操作を実行することができると共に、オペレータ・インタフェース１６０は集められた画像データに基づく再構成画像を観察するために幾つかの点で有益である。写真フィルムの場合においては、通常画像は、放射線医及び主治医がより容易に画像シーケンスを読影及び注釈できるように照明ボード又は同様のディスプレイ上に配置されることに留意されたい。さらに画像は、本目的において一般に医用画像管理システムのようなインタフェース１６０内に含まれるものとしてみなされる短期又は長期記憶装置に格納することができる。画像データはまた、ネットワークなどを介して遠隔の場所に転送することができる。
【００８５】
一般的な観点から、オペレータ・インタフェース１６０はまた、典型的にはシステム制御回路構成１５４とのインタフェースを通じてイメージングシステムの制御をもたらすことに留意されたい。さらに、１つ以上のオペレータ・インタフェース１６０を設けることができることに注意されたい。したがって、イメージングスキャナ又はステーションは、画像データ収集手順に含まれるパラメータの調節を可能にするインタフェースを含むことができ、ここでは異なるオペレータ・インタフェースを、結果として得られる再構成された画像の操作、強調、及び観察のために備えることができる。
【００８６】
本発明の既に説明された実施形態は、圧縮率と設計アルゴリズムの複雑さとの間のトレードオフを達成することを含む多くの利点を有する。換言すると、大量のデータを符号化するためのより複雑さの少ないアルゴリズムが有利に形成されると同時に、良好な圧縮率が維持される。
【００８７】
本発明の特定の特徴についてのみここで図示し説明してきたが、当業者であれば多くの修正及び変更を行うことができるであろう。したがって、特許請求の範囲は、本発明の真の技術的思想に含まれるものとしてこのような修正及び変更を含むことを理解されたい。
【図面の簡単な説明】
【００８８】
【図１】本発明の好ましい実施形態により実施されるデータ符号化システムのブロック図。
【図２】本発明の一実施形態による所望のビン構造を生成する方法を示すフローチャート。
【図３】図２のフローチャートを実施する実施例。
【図４】図２のフローチャートを実施する実施例。
【図５】図２のフローチャートを実施する実施例。
【図６】本発明の一実施形態による所望のビン構造を生成する方法を示すフローチャート。
【図７】図６のフローチャートを実施する実施例。
【図８】図６のフローチャートを実施する実施例。
【図９】図６のフローチャートを実施する実施例。
【図１０】図６のフローチャートを実施する実施例。
【図１１】本発明の好ましい実施形態にしたがって用いられる汎用コンピュータシステムの概略図。
【図１２】本発明の好ましい実施形態を利用する例示的なイメージングシステムの概略図。
【符号の説明】
【００８９】
１０  データ符号化システム
１２  数学的演算ブロック
１４  初期化ブロック
１６  処理ブロック
１８  ユニバーサル位置符号化ブロック
２０  数学的逆演算ブロック
２２  エントロピー・デコーダ
２４  エントロピー・エンコーダ
５０  最初のトップツリービン構造
５４、５６、５８、６０、６２、６４、６８、７０  トップツリービン
９２  最初のボトムツリービン構造
１１０−１２４  ボトムツリービン
１３０  コンピュータシステム
１３２  プロセッサ
１３４  メモリ
１３６  入力装置
１３７  マウス
１３８  キーボード
１４０  ディスプレイ
１４２  通信装置
１４４  大容量記憶装置
１４６  データ経路
１５０  イメージングシステム
１５２  イメージャ１５２
１５４  制御回路構成
１５６  データ収集回路構成
１５８  データ処理回路構成
１６０  オペレータ・インタフェース
【図１】
2004177965.tif 000014
【図２】
2004177965.tif 000015
【図３】
2004177965.tif 000016
【図４】
2004177965.tif 000017
【図５】
2004177965.tif 000018
【図６】
2004177965.tif 000019
【図７】
2004177965.tif 000020
【図８】
2004177965.tif 000021
【図９】
2004177965.tif 000022
【図１０】
2004177965.tif 000023
【図１１】
2004177965.tif 000024
【図１２】
2004177965.tif 000025