(57)【要約】本発明は、画素に基づいた画像データの圧縮及び伸張方法に係る。各画素は、最初に画素値が決められる。次に、各画素に対し、所与の近接画素数から画素差値が決定され、画素差値は、問題の画素と、問題の画素に近接する画素のそれぞれとの画素値における差から得られる。次に、画素差値は、降順にソートされる。画素差値の計算に用いた各画素を画素群に割当てる。このようにして得られる画素群は、画素差値の降順に応じて格納される。画像の再現のために、最も高い画素差値を有する画素群が最初にロードされる。３つの最も近い画素群から三角形が形成される。各三角形の面は、三角形の３つの隅部をそれぞれ形成する画素群の色値から計算される色処理で埋められる。ロードされる画素群が増加するほど、三角形は小さくなり、画像の再構成はより緻密となる。
2004534432.tif 000002
【特許請求の範囲】
【請求項１】
個々の画像点（画素）のアレイから構成され、各画素（０−４１９）は、該画素の色又は輝度情報を記述する画素値を有する、画像データの圧縮方法であって、
ａ）前に決められた近接画素群の画素値に対する各画素の各画素値を用いて画素差値を計算することによって、上記アレイの各画素に対する優先順位値を決定する段階と、
ｂ）上記優先順位値の計算に用いた画素を、画素群（Ｐ０−Ｐ４）に組合わせる段階と、
ｃ）上記画素群の上記優先順位値を用いて、上記画像アレイの上記画素群をソートする段階と、
ｄ）上記画素群の優先順位値に応じて上記画素群を格納及／又は伝送する段階と、を含むことを特徴とする方法。
【請求項２】
上記画素差値は、考慮される画素と、上記考慮される画素に近接する考慮される各画素との画素値における差から分かることを特徴とする請求項１記載の方法。
【請求項３】
画素で表される画像幅、画素で表される画像高さ、用いられる画素群の形式、及び、４つの画像隅部の隅部画素群といった上記画像のパラメータは、最初に格納及び／又は伝送されることを特徴とする請求項１又は２記載の方法。
【請求項４】
各画素群に対し、基準画素（Ｐ０）の位置が格納又は伝送され、上記基準画素の画素値は、残りの画素（Ｐ１−Ｐ４）の画素値と共に格納又は伝送されることを特徴とする請求項１乃至３のうちいずれか一項記載の方法。
【請求項５】
画像の特定の領域の画素群に、高い優先順位が割当てられることを特徴とする請求項１乃至４のうちいずれか一項記載の方法。
【請求項６】
上記画素群の上記画素値は更に、ランレングス符号化又は他の圧縮方法により圧縮されることを特徴とする請求項１乃至５のうちいずれか一項記載の方法。
【請求項７】
優先順位に応じてソートされる上記画素群の決定及び出力は、スキャナ又はＣＣＤカメラといった、用いられる画像露光装置によって既に行われることを特徴とする請求項１乃至６のうちいずれか一項記載の方法。
【請求項８】
請求項１乃至７記載の方法によって圧縮された画像データを伸張する方法であって、
ａ）上記圧縮された画像に対し読込みされたパラメータから空の画像アレイを生成する段階と、
ｂ）隅部画素群を読込みし、且つ、上記隅部画素群を上記画像アレイの４つの隅部に挿入する段階と、
ｃ）３つの最も近い画素群のそれぞれを少なくとも１つの線によって結ぶことによって三角形を形成する段階と、
ｄ）上記三角形を形成する上記画素群から計算される色又は輝度傾斜によって、上記三角形の面を形成する画素を埋める段階と、
ｅ）次の画素群を読込みし、且つ、上記画像アレイに挿入する段階と、
ｆ）段階ｃ）乃至ｆ）を繰り返す段階と、を含むことを特徴とする方法。
【請求項９】
上記段階ｃ）乃至ｆ）は、全ての画像データ又は所望の数の画像データが読込みされ且つ処理されるまで繰り返されることを特徴とする請求項７記載の方法。
【請求項１０】
上記三角形は、そのサイズを拡大縮小することが可能であり、且つ、異なる画像解像度に適応可能であることを特徴とする請求項７又は８記載の方法。
【発明の詳細な説明】
【０００１】
本発明は、画像データの圧縮及び伸張方法に係る。
【０００２】
今日では、画像データを格納するために多くの技術及び圧縮方法がある。用いられる技術は、本質的に、画素に基づいた方法及びベクトルに基づいた方法から導き出される。
【０００３】
画素に基づいた方法の場合、ラスタが画像上にかぶせられる。各ラスタポイントは、１つの画素に対応する。画素値は、１ビット（例えば、ＷＢＭＰ―＞白と黒）か、又は、数ビット（例えば、ＢＭＰ―＞本当の色）で符号化される。画像ファイルのサイズを小さくするために、様々な圧縮方法を適用することができる。効果的な方法は、画素あたりのビットを減らすことにある。更に、画素を群にまとめる方法も適用することができる。これらは、原則として、ＤＣＴ（離散コサイン変換）を用いて周波数ドメインに変換される矩形の領域である。変換時に発生する高周波コンテンツは、知覚可能な品質の損失なく、無視することができる。この方法は、例えば、ＪＰＥＧ画像に適用される。非常に高いＪＰＥＧ圧縮の場合、いわゆるアーチファクトと称される画像中に矩形の歪んだ、不規則なパッチをもたらす場合がある。
【０００４】
ベクトルに基づいた方法の場合、画像は、幾何学形状（例えば、矩形又は円形）によって明瞭に記述される。公知の方法は、いわゆるＳＶＧ（スケーラブル・ベクトル・グラフィックス）である。この方法によって用意された画像は非常に良好に率にあわせて拡大縮小できるので、製図に際立った結果をもたらすことができる。対応するファイルは、従来のバイナリビットマップ形式のものより明らかに小さい。しかし、この方法は、写真を格納するのにはそれほど適していない。
【０００５】
フィルムを露光する従来の写真装置と並んで、フィルムの代わりに記憶媒体に写真をデジタルで格納する写真装置が登場してきている。これらの記憶媒体は、有限の容量しか有さないので、高解像度の写真を数枚か、または、低解像度の写真を多く格納することができる。現在では、自由な拡大縮小は不可能である。
【０００６】
本発明は、画像データの圧縮及び伸張方法を提供することを目的とする。本発明の方法は、格納サイズ、異なる画像解像度、及び、表示サイズに対し単純且つ柔軟に適応することができる。
【０００７】
本発明の目的は、請求項１の特徴によって実現される。
【０００８】
本発明の有利な成果及び拡張は、従属請求項に記載する。
【０００９】
本発明は、画素に基づいた技術とベクトルに基づいた技術の組合せに基づく。第１の段階として、画像はラスタで覆われる。ラスタの各画素に対し、画素値、即ち、色値又は輝度値が最初に決定される。続いて、以下、画素差値と称する追加値が、前に決められた近接画素数から各画素に対し計算される。画素差値は、考慮される画素の画素値と考慮される各近接画素の画素値との差から分かる。近接画素の画素値に対する画素値の差が大きいほど、画素差値が大きくなる。続いて、画像の各画素の画素差値が、降順にソートされる。画素差値の計算に用いられた各画素は、画素群に組込まれる。従って、このように得られる画素群は、画素差値の降順、即ち、画素差値によって決められる優先順位に応じて格納される。優先順位リストでは、その画素差値、従って、その優先順位が最大のものがリストの最初に現れる。
【００１０】
画素群の画素値は更に、ランレングス符号化、又は、ジップ方式といった他の周知の圧縮方法によって圧縮されることが可能である。
【００１１】
画像の再現のためには、最大画素差値（優先順位）を有する画素群が最初にロードされる。３つの最も近い画素群から、三角形が形成される。三角形は、そのサイズを拡大縮小することができ、従って、異なる解像度に適応することができる。画像の特定の部分が、特に緻密に再現されるべき場合、この部分の画素群に、高い優先順位を与えることが可能である。各三角形の面は、三角形の隅を形成する３つの画素群のそれぞれの色値から計算される色傾斜によって埋められる。白黒画像では、色値の代わりに、画素又は画素群の各輝度値が考慮されて、対応する輝度傾斜が計算される。
【００１２】
多くの画素が表示されると、三角形は小さくなり、従って、画像をより緻密に再構成することが可能となる。
【００１３】
本発明の方法の利点は、様々な表示サイズへの単純な適応による高い拡張性と、画像の特定の領域に優先順位をつけることによって画像の関心領域の解像度を増加する可能性にある。
【００１４】
本発明の方法は、製造業者、又は、画像処理専門家が、異なる優先順位によって製造業者に応じた最適化ルーチンを使用することを可能にする。しかし、ソース画素値は常に伝送されるので、画像は、製造業者に応じた最適化ルーチンを用いなくても生成することができる。
【００１５】
更に、細部の解像度を増加することは、別の解像度を有する全く新しい画像をリロードするのではなく、画像の関心領域をリロードすることによって可能である。
【００１６】
本発明の方法は、個々の画素群の伝送にエラーがある場合に、画像は再度生成できるので、非常に耐障害性がある。
【００１７】
本発明の実施例を、添付図面を参照しながら詳細に説明する。本発明の適用の追加の特徴、利点、及び、可能性は、図面及びその説明から理解できる。
【００１８】
以下に、２次元画像ファイル（画像アレイ）の圧縮及び伸張を、実施例を参照して説明する。
【００１９】
以下において、次のことを前提とする。
【００２０】
画像ソースは、ビットマップ、つまり、画像アレイとしてある。
【００２１】
画像アレイの各画素は、３２ビット値（画素値）によって表す。３２ビットは、例えば、それぞれ８ビットを有する４つの値（透明、赤、緑、青）に分割される。
【００２２】
例として示す画像アレイは、２０画素の画像幅と２１画素の画像高さを有する画像である。画素の１は、整数値によって決められる。画素アレイは、図１に示す通りに、０から４１９まで列挙される。各ボックス内の番号は、対応する画素の位置に対応する。
【００２３】
画像の圧縮は、以下の通りに行われる：
画像アレイの読込み
画像は、図１に示す２０×２１画素画像アレイに読込みされる。各画素は、その位置（０乃至４１９）とその画素値（色値又は輝度値）によって決められる。
【００２４】
画素群の決定
次に、どの近接画素が、画素群を形成するか決定される。その際に、ｐ０は、画素群の位置を特定する画素を表す。基準画素ｐ０に対する画素群の残りの画素、例えば、ｐ１−ｐ４の位置は、用いられる画素群のタイプ（形式）から分かる。図２には、例示的に、画素群の幾つか可能な形式を表す。基準画素ｐ０に対し左右対称の画素群、及び、基準画素ｐ０に対し左右非対称の画素群を形成することが可能である。どのタイプの画素群が用いられるかは、特に、画像材料のタイプ及び所望の圧縮率に依存する。原則として、１つの画素群に含まれる画素数が多いほど、大きい圧縮係数を達成することができる。同一の画素群形式を、例えば、圧縮及び伸張といった画像の符号化及び復号化に用いなければならない。
【００２５】
本発明の方法の以下の説明において、図２中、太枠で囲んだ画素群の形式（左下）で処理を行うものとする。
【００２６】
優先順位値の決定
画素群の各画素ｐ０に対し、その画素群に関連して優先順位が計算される。そのようにすることによって、画像の各画素０乃至４１９は、一度は基準画素となる。
【００２７】
画像のエッジにある画素は、例えば、エッジの領域に特定の画素群形式を選択する、又は、考慮される面を減少する（エッジ領域を削除する）といった特別な処理が施されることが可能である。
【００２８】
優先順位を計算するために、様々な計算方法がある。例として、本願では、線形方法を用いる。このために、画素群の各画素値Ｐ０、Ｐ１、Ｐ２、Ｐ３、及び、Ｐ４は、それぞれの色コンテンツ赤、緑、及び、青に分割される。これらの各色値は、８ビットで表される。各画素Ｐ１−Ｐ４の各色に対し、色差値がＰ０に対し決定され、例えば、Ｐ０＿ｒｅｄ−Ｐ１＿ｒｅｄ、Ｐ０＿ｒｅｄ−Ｐ２＿ｒｅｄ、…、Ｐ０＿ｂｌｕｅ−Ｐ４＿ｂｌｕｅとなる。絶対色差値が足し算され、色の数及び考慮される画素数によって割り算される。結果として、考慮される画素群の優先順位の値が得られる。画素群の各画素の色値に差があるほど、優先順位は高くなる。
【００２９】
優先順位値の決定のための更なる方法としては、グレートーン、又は、色の色差の最大値を用いる方法がある。優先順位値自体は後から伝送される又は格納されないので、優先順位値を決定する方法は、復号化には直接的には関係がない。
【００３０】
この優先順位によって、例えば、エッジといった大きい色の変化又は大きいコントラストを有する画像の領域は、高い優先順位を有し、例えば、青空といった比較的一定に保たれる画像コンテンツは、低い優先順位を有する結果が得られる。
【００３１】
優先順位値のソート
この段階では、優先順位値は、降順にソートされる。実行に応じて、このソート段階は、各新しい優先順位値が決定される後に行っても、又は、もっと後から行ってもよい。
【００３２】
利用可能なリソースに応じて、優先順位がつけられた画素群の位置への依存は、近接画素の色値による純粋な優先順位とともに、利用することが可能である。このことを適用例によって示す。例えば、海において、水平線を観察すると、その水平線は横線のように見える。この水平線に沿っての各画素群の優先順位値は、略同じであると予想される。この場合、互いに最も遠くにある水平線の点が最大の支配権を有して、情報を提供することができる。水平線の最も左にある画素群と最も右端にある画素群を伝送するだけで、水平線をもう一度再構成することができる。
【００３３】
優先順位の追加の可能性は、画像の特定領域の解像度を高くすることにある。画像のこのような領域は、例えば、写真における顔であり得る。休暇中の写真に写った顔は、一般的に、割合として、画像全体の小さな領域しか占めないが、顔は、通常、最大の関心部である。画像のこの領域（顔の領域）の画素群に対応する優先順位を与えることによって、このような人間の知覚的な処理を考慮に入れることができる。同様に、画像の中心にある画素群に、対応する高い優先順位を与えることも可能である。
【００３４】
優先順位の追加の可能性は、近接画素群が互いに重ね合わされることにある。画素群を賢く選択することによって、近接群の重ね合わされた画素値が冗長的に伝送されることを回避することが可能である。
【００３５】
圧縮されるべき画像が、ＣＣＤカメラ又はスキャナによって直接捕捉される場合、原則として、カメラ／スキャナ内にある画像処理マイクロチップから、優先順位に応じてソートされるアレイを直接入手することが可能である。従って、圧縮における計算労力のかなりの部分が省略される。
【００３６】
画素群の格納
最初に、画像の幾つかのパラメータが格納される。例示的に列挙するに、
−画像幅（画素で）
−画素高さ（画素で）
−画素群の用いた形式（１つの形式が標準化される場合は必要ではない）
−画像の隅の４つの画素群
次に、各画素群の優先順位に応じて各画素群が格納される。つまり、高い優先順位を有する画素群が最初に格納される（後から最初に読出しされる）。
【００３７】
このために、画素群の基準画素ｐ０の位置値が最初に格納される。次に、画素値Ｐ０、Ｐ１、Ｐ２、Ｐ３、Ｐ４が格納される。
例：
位置値Ｐ０、画素値Ｐ０、Ｐ１、Ｐ２、Ｐ３、Ｐ４；次の位置値Ｐ０（同じ又は低い優先順位を有する）、画素値Ｐ１、Ｐ２、Ｐ３、Ｐ４、…；次の位置値Ｐ０（最低の優先順位を有する）、画素値Ｐ０、Ｐ１、Ｐ２、Ｐ３、Ｐ４。
【００３８】
格納は、本願には例示的にのみ扱う様々な方法によって最適化される。画素群のランレングス符号化を行うことが可能である。例えば、画像のある領域において赤のコンテンツが現れない場合、その領域は、例えば、８（赤）ではなく２ビットのみで伝送されるか、又は、先行ゼロの数を利用することができる。
【００３９】
更に、例えば、ジップ形式といった一般的な圧縮方法を用いることが可能である。
【００４０】
優先順位の制限値を決定することにより、特定の品質を保証することが可能である。例えば、画素差値の制限値以下の関連付けられる画素群は、常に最低の優先順位値を与えられるよう決めることが可能である。
【００４１】
最大ファイルサイズを決定する際に、優先順位によって、絶対不可欠な情報が最初に格納されることが保証される。
【００４２】
画像の伸張：
新しい画像アレイの生成
新しい画像の生成のために、画像のパラメータが最初に読出しされ、評価される。画像幅、画像高さ、画素群の形式などが例である。これらの値から、図１に表したものと類似する、最初は空である画像アレイが生成される。オリジナルの画像の画像高さ及び画像幅と、現在所望される表示が合わない場合（例えば、有限のＰＤＡ表示装置、又は、高解像度の画面の場合）、対応する拡大縮小が行われなければならない。このために、再計算係数が最初に決められる（画像幅＿オリジナル／画像幅＿表示装置、及び、画像高さ＿オリジナル／画像高さ＿表示装置）。これらの係数は、計算によって、オリジナル画像の位置値を新しい表示装置の位置値に変換するよう用いることが可能である。
【００４３】
隅の画素群の挿入
図３に示すように、優先順位がつけられた画素群は、その順番に応じて読出しされる。最初に４つの画素群が、新しく生成される画像アレイに入力される。各画素群の位置（ｐ０）は、黒塗りされたフィールド２１、３８、３８１、又は３９８によって決定される。この位置値（ｐ０）は、格納ファイルに整数値として存在する。次に、各画素群に属し、濃いグレーに塗られる画素値（ｐ１−ｐ４）が、新しい画像アレイに入力される。濃いグレーに塗られる画素値間にあり、薄いグレーで塗られる画素値は、濃いグレーと黒に塗られるフィールドから計算することが可能である。この計算のために、既知の画素値は、最初にそれらの成分赤、緑、及び、青に分割される。続いて、各色の平均値が計算される。例えば、画素（２２）＝（画素（２）＋画素（２１）＋画素（４２））／３。
【００４４】
面の埋め込み
次に、存在している画素群は、線によって互いに結ばれる。対応する画素群によってその隅が決められる三角形が得られる。例示的に、このことは、画素位置２と画素位置１７との間の線によって示すべきである。この線の色傾斜は、画素２及び１７の色値によって計算される。まず、これらの２つの位置間の画素数が決定され、この例では、１４である。続いて、各色（赤、緑、青）に対し、色差が決定される。例えば、位置２における色値２と、位置１７における色値３０では、色差２８となる。画素２から画素１７までの画素ごとの色値増加は、色差／画素数（この例では、２８／１４、つまり、２）から計算される。
【００４５】
まだ埋められていない面は、位置６３から位置７４、位置８２から位置９３、以下同様、まで横線を書くことによって埋められる。ここでも、点間の暫定的な色傾斜が、上述したように計算される。
【００４６】
図５に示すように、追加される各追加の画素群は、適宜埋められることの可能な追加の三角形をもたらす。まず、４つの隅の点（２１、３８、３９８、３８１）を用いて面全体が埋められた後、各追加の画素群を用いて解像度を精緻化することが可能である。画素群８７の追加は、基準点（２１、３８、８７）、（２１、８７、３８１）、（３８１、８７、３９８）、（３９８、７８、３８）を有する４つの三角形をもたらす。ここで、追加の画素群（２４７）が、例えば、８７、３８１、３９８であるそのような三角形内に挿入されると、３つの新しい三角形（２４７、３８１、３９８）、（２４７、８７、３８１）、及び、（２４７、８７、３９８）が生成される。各新しい画素群は、従って、埋めることのできる３つの新しい三角形を生成する。挿入される画素群が多いほど、即ち、より多くの三角形が形成されるほど、計算された色傾斜は、画像の実際の色傾斜に近くなる。現在の時点では、新しい三角形のみが生成するので、この計算のために最適化される方法が用いられる。更に、毎回新しく生成される３つの三角形は、処理速度を増加するために、並列計算されることが可能である。並列計算の追加の可能性は、新しい画素群が、画像の異なる領域に追加される場合にも現れる。
【図面の簡単な説明】
【００４７】
【図１】２０×２１画素の画像アレイを示す図である。
【図２】画素群の様々な形式を示す図である。
【図３】画像の隅に画素群が挿入された新しく生成された画像アレイを示す図である。
【図４】既に埋められた画素群間の面の埋め込みを示す図である。
【図５】追加の画素群を挿入し、追加の画素群間の面の埋め込みを示す図である。
【国際公開パンフレット】
2004534432.tif 000003
2004534432.tif 000004
2004534432.tif 000005
2004534432.tif 000006
2004534432.tif 000007
2004534432.tif 000008
2004534432.tif 000009
2004534432.tif 000010
2004534432.tif 000011
2004534432.tif 000012
2004534432.tif 000013
2004534432.tif 000014
2004534432.tif 000015
2004534432.tif 000016
2004534432.tif 000017
2004534432.tif 000018
2004534432.tif 000019
2004534432.tif 000020
2004534432.tif 000021
2004534432.tif 000022
【国際調査報告】
2004534432.tif 000023
2004534432.tif 000024
2004534432.tif 000025
2004534432.tif 000026
2004534432.tif 000027
2004534432.tif 000028
2004534432.tif 000029
2004534432.tif 000030