PNG (Portable Network Graphics) Specification, Version 1.2


Previous page
Next page
Table of contents

6. フィルターアルゴリズム

この章では圧縮前に適応することのできるフィルターアルゴリズムを説明します。これらのフィルタの目的はイメージデータを最適な圧縮にするために調整することです。

6.1. フィルター形式

PNG のフィルター手法が 0 は 5 つの基本的なフィルター形式を定義しています:

   Type    Name
   
   0       None
   1       Sub
   2       Up
   3       Average
   4       Paeth

IHDRのフィルター手法 0 は実際にはこの5つのフィルタ形式を指定していることに注意してください。フィルター形式のセットが拡張されるときはいつでも、拡張されたセットに対してことなるフィルター手法ナンバーが割り振られ、サポートされないフィルタータイプが含まれていることにきづいたならばデコーダはデータを伸張する必要はありません)

エンコーダはスキャンラインごとに適用するフィルターアルゴリズムを選択することができます。圧縮工程に送られるイメージデータ中で、それぞれのスキャンラインはそのスキャンラインに使われるフィルターアルゴリズムを指定するフィルター形式バイトに続きます。

フィルターアルゴリズムはイメージのビット深度やカラータイプに関わらず、ピクセルではなく、バイトに適用されます。フィルタリングアルゴリズムは Image layout で説明されるように表現されたスキャンラインによって形成されたバイトの連続に働きます。イメージがαチャンネルを含むときは、αデータはイメージデータと同様の方法でフィルターされます。

イメージがインターレースのときは、フィルターのためにインターレースパターンのそれぞれのパスが独立したイメージとして扱われます。フィルターはパスの間に実際に転送されるピクセルから形成されるバイトの連続に働き、「一つ前のスキャンライン」 は同じパスの前に転送されたものであり、完成したイメージの直前のものではありません。一回のパスで転送されるサブイメージは常に長方形であり、完全なイメージよりも幅や高さで小さいということに注意してください。フィルターはこのサブイメージが空のとき適用されません。

すべてのフィルターでは、スキャンラインの最初のピクセルの左側のバイトは 0 として扱う必要があります。直前のスキャンラインを参照するフィルターでは、全体の直前のスキャンラインはすべて 0 でイメージの最初のスキャンラインとして扱う必要があります(もしくはインターレースイメージのパスの)。

フィルターの効果を反転させるために、デコーダは同じラインの直前のピクセル、直前のラインの現在のピクセルの真上のピクセル、真上のピクセルの左のピクセルのデコードされた値、を使う必要があります。このことは、デコーダが少なくとも1スキャンライン分のイメージデータを保存する必要がつねにあるということを意味しています。たとえ、いくつかのフィルター形式は直前のスキャンラインを参照しないとしても、次のスキャンラインはそれを参照するフィルターを使うかもしれないので、デコーダは常にそれぞれのスキャンラインをデコードされた状態で保存する必要があります。

PNG はイメージにどのフィルター形式が適用できるかどうかの制限は課しません。しかし、すべてのデータの形式でフィルターは同様の効果があるわけではありません。エンコーダへの勧告は:Filter selection を参照してください。

論拠は:Filtering を参照してください。

6.2. フィルター形式 0: None

None() フィルターでは、スキャンラインは変更されることなく転送されます。データの直前にフィルター形式バイトを挿入する必要があるだけです。

6.3. フィルター形式 1: Sub

Sub() フィルターはそれぞれのバイトと対応するピクセルのバイトの値との差を転送します。

Sub() フィルターを計算するにはスキャンラインのそれぞれのバイトに以下の式を適用します:

   Sub(x) = Raw(x) - Raw(x-bpp)

ここで x の範囲は 0 からスキャンラインを表現するバイト数マイナス1までで、Raw() はスキャンライン中のそのバイト位置の生のデータバイトを参照し、bpp は完全なピクセルあたりのバイト数として定義され、1 に丸められます。たとえば、カラータイプが 2 、ビット深度が 16 のとき、bpp は 6 (3サンプル、サンプルあたり 2-byte)に等しく、カラータイプが 0、ビット深度が 2 のとき、bpp は 1 (丸め)に等しく、カラータイプが 4、ビット深度が 16 のとき、bpp は 4 (2-byte のグレイスケールサンプル、2-byte のαサンプル)に等しい。

この計算はビット深度に関係なく、それぞれのバイトになされます。16-bit のイメージでは、それぞれの MSB は先行する MSB から予測され、それぞれの LSB は先行する LSB から予測されるので、bpp はこのように定義されます。

無符号の 256 を法とした算術が使われ、したがって、入力も出力もバイトに適します。Sub 値の連続がフィルターされたスキャンラインとして転送されます。

x < 0、はすべて、Raw(x) = 0 と仮定されます。

伸張のあとに Sub() フィルターの効果を反転するためには、以下の値を出力します:

   Sub(x) + Raw(x-bpp)

(256 のあまりを計算して)、ここでは、Raw() はすでにデコードされたバイトを参照します。

6.4. フィルター形式 2: Up

Up() フィルターは予報値として左側の値ではなく現在のピクセルの真上のピクセルが使われること以外は Sub() フィルターと同様のものです。

Up() フィルターを計算するために、スキャンラインのそれぞれのバイトに以下の式を適用します:

   Up(x) = Raw(x) - Prior(x)

ここで、x の範囲は 0 から、スキャンラインが表現するバイト数マイナス1までで、Raw() はスキャンライン中のそのバイト一の生のデータバイトを参照し、Prior(x) は直前のスキャンラインのフィルターされていないバイトを参照します。

この計算はビット深度に関係なく、それぞれのバイトになされることに注意してください。無符号の 256 を法とした算術が使われ、したがって、入力も出力もともにバイトに適合します。Up 値の連続がフィルターされたスキャンラインとして転送されます。

イメージの(もしくはインターレースイメージのパスの)最初のスキャンラインでは、すべての xPrior(x) = 0 と仮定されます。

Up() フィルターを伸張のあとに反転するためには以下の値を出力します:

   Up(x) + Prior(x)

(256 のあまりを計算し)、ここでは Prior() はデコードされた直前のスキャンラインを参照します。

6.5. フィルター形式 3: Average

Average() フィルターはピクセルの値を予測するために2つの近隣ピクセル(左と上)の平均を使います。

Average() フィルターを計算するために、スキャンラインのそれぞれのバイトに以下の式を適用します:

   Average(x) = Raw(x) - floor((Raw(x-bpp)+Prior(x))/2)

ここで、x の範囲は 0 から、スキャンラインが表現するバイト数マイナス1までで、Raw() はスキャンライン中のそのバイト位置の生のデータバイトを参照し、Prior(x) は直前のスキャンラインのフィルターされていないバイトを参照し、bppSub() フィルターのように定義します。

この計算はビット深度に関係なく、それぞれのバイトになされることに注意してください。Average 値の連続がフィルターされたスキャンラインとして転送されます。

生のバイトから予測値を引くときは 256 を法とする必要があり、したがって、入力と出力はともにバイトに適合します。しかし、Raw(x-bpp)+Prior(x) の合計はオーバーフローしないように生成する必要があります(少なくとも 9-bit の算術を用いることで)。floor() は割り算の結果を切り下げることを示しています。言い換えるなら、整数の割り算、もしくは左シフト演算です。

x < 0 ときはすべて、Raw(x) = 0 と仮定されます。イメージの(もしくはインターレースイメージのパスの)最初のスキャンラインでは、すべての xPrior(x) = 0 と仮定されます。

Average() フィルターを伸張のあとに反転するためには、以下の値を出力します:

   Average(x) + floor((Raw(x-bpp)+Prior(x))/2)

ここでは、結果は 256 のあまりとして計算されますが、予測値はエンコードと同様の法で計算されます。Raw() は常にデコードされたバイトを参照し、Prior() は直前のスキャンラインのデコードされたバイトを参照します。

6.6. フィルター形式 4: Paeth

Paeth() フィルターは3つの近隣ピクセル(左、上、左上)の単純な線形関数を計算します。計算値と最も近い近隣ピクセルを予測値として選択します。この技法は Alan W. Paeth [PAETH] によります。

Paeth() フィルターを計算するために、スキャンラインのそれぞれのバイトに以下の式を適用します:

   Paeth(x) = Raw(x) -
              PaethPredictor(Raw(x-bpp), Prior(x), Prior(x-bpp))

ここで、x の範囲は 0 から、スキャンラインが表現するバイト数マイナス1までで、Raw() はスキャンライン中のそのバイト位置の生のデータバイトを参照し、Prior(x) は直前のスキャンラインのフィルターされていないバイトを参照し、bppSub() フィルターのように定義します。

この計算はビット深度に関係なく、それぞれのバイトになされることに注意してください。無符号の 256 の法の算術が使われますので、入力と出力ともにバイトに適合します。Paeth 値の連続がフィルターされたスキャンラインとして転送されます。

PaethPredictor() 関数は以下の疑似コードで定義されます:

   function PaethPredictor (a, b, c)
   begin
        ; a = left, b = above, c = upper left
        p := a + b - c        ; initial estimate
        pa := abs(p - a)      ; distances to a, b, c
        pb := abs(p - b)
        pc := abs(p - c)
        ; return nearest of a,b,c,
        ; breaking ties in order a,b,c.
        if pa <= pb AND pa <= pc then return a
        else if pb <= pc then return b
        else return c
   end

PaethPredictor() 関数内の計算はオーバーフローすることなく計算される必要があります。256 を法とした算術は目標とするバイト値から関数の結果を引き算する最後の工程のみで使われます。

結合順序は重大であり、改造はしてはいけないことに注意してください。結合順序は:左側のピクセル、上のピクセル、左上のピクセルです。(これは Peath の条項で与えられるものとは異なる順序です。)

x < 0 ときはすべて、Raw(x) = 0Prior(x) = 0と仮定されます。イメージの(もしくはインターレースイメージのパスの)最初のスキャンラインは、すべての x にたいして、Prior(x) = 0 と仮定されます。

Paeth() フィルターを伸張のあとに反転するためには、以下の値を出力します:

   Paeth(x) + PaethPredictor(Raw(x-bpp), Prior(x), Prior(x-bpp))

(256 のあまりを計算し)、ここでは Raw()Prior() はデコードされた直前のスキャンラインを参照します。エンコーダとデコーダでは正確に同じ PaethPredictor() 関数が使われます。


Previous page
Next page
Table of contents