Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 14145] ファイルの概要

このコミットは、Go言語の標準ライブラリ image/jpeg パッケージにプログレッシブJPEG画像のデコード機能を追加するものです。これにより、プログレッシブJPEG形式でエンコードされた画像をGoプログラム内で正しく読み込み、インメモリイメージとして処理できるようになります。

コミット

commit 8b624f607f726347dc48a1ec4989deb868890105
Author: Nigel Tao <nigeltao@golang.org>
Date:   Mon Oct 15 11:21:20 2012 +1100

    image/jpeg: decode progressive JPEGs.
    
    To be clear, this supports decoding the bytes on the wire into an
    in-memory image. There is no API change: jpeg.Decode will still not
    return until the entire image is decoded.
    
    The code is obviously more complicated, and costs around 10% in
    performance on baseline JPEGs. The processSOS code could be cleaned up a
    bit, and maybe some of that loss can be reclaimed, but I'll leave that
    for follow-up CLs, to keep the diff for this one as small as possible.
    
    Before:
    BenchmarkDecode     1000           2855637 ns/op          21.64 MB/s
    After:
    BenchmarkDecodeBaseline      500           3178960 ns/op          19.44 MB/s
    BenchmarkDecodeProgressive           500           4082640 ns/op          15.14 MB/s
    
    Fixes #3976.
    
    The test data was generated by:
    # Create intermediate files; cjpeg on Ubuntu 10.04 can't read PNG.
    convert video-001.png video-001.bmp
    convert video-005.gray.png video-005.gray.pgm
    # Create new test files.
    cjpeg -quality 100 -sample 1x1,1x1,1x1 -progressive video-001.bmp > video-001.progressive.jpeg
    cjpeg -quality 50 -sample 2x2,1x1,1x1 video-001.bmp > video-001.q50.420.jpeg
    cjpeg -quality 50 -sample 2x1,1x1,1x1 video-001.bmp > video-001.q50.422.jpeg
    cjpeg -quality 50 -sample 1x1,1x1,1x1 video-001.bmp > video-001.q50.444.jpeg
    cjpeg -quality 50 -sample 2x2,1x1,1x1 -progressive video-001.bmp > video-001.q50.420.progressive.jpeg
    cjpeg -quality 50 -sample 2x1,1x1,1x1 -progressive video-001.bmp > video-001.q50.422.progressive.jpeg
    cjpeg -quality 50 -sample 1x1,1x1,1x1 -progressive video-001.bmp > video-001.q50.444.progressive.jpeg
    cjpeg -quality 50 video-005.gray.pgm > video-005.gray.q50.jpeg
    cjpeg -quality 50 -progressive video-005.gray.pgm > video-005.gray.q50.progressive.jpeg
    # Delete intermediate files.
    rm video-001.bmp video-005.gray.pgm
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6684046

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/8b624f607f726347dc48a1ec4989deb868890105

元コミット内容

このコミットは、Go言語の image/jpeg パッケージにプログレッシブJPEG画像のデコード機能を追加するものです。これまではベースラインJPEGのみをサポートしていましたが、この変更により、プログレッシブJPEG形式の画像もGoの jpeg.Decode 関数でデコードできるようになります。APIの変更はなく、jpeg.Decode は画像全体がデコードされるまで戻り値を返しません。

この機能追加により、コードの複雑性が増し、ベースラインJPEGのデコード性能が約10%低下することがベンチマーク結果で示されています。しかし、これはプログレッシブJPEGのサポートという重要な機能を実現するためのトレードオフとされています。

変更の背景

この変更の主な背景は、Go言語の image/jpeg パッケージがプログレッシブJPEG形式をサポートしていなかった点にあります。Issue #3976(Fixes #3976)がこの機能の必要性を示しており、このコミットはその問題を解決するために作成されました。

プログレッシブJPEGは、特にウェブ上での画像表示において重要な役割を果たします。画像全体を一度にダウンロードして表示するベースラインJPEGとは異なり、プログレッシブJPEGは低解像度から徐々に詳細な画像を読み込み、表示することができます。これにより、ユーザーは画像全体がダウンロードされるのを待つことなく、画像のプレビューを素早く見ることができ、ユーザーエクスペリエンスが向上します。Go言語で画像処理を行う際に、この形式の画像を扱う必要性が高まったため、デコード機能の実装が求められました。

前提知識の解説

JPEG (Joint Photographic Experts Group)

JPEGは、静止画像の圧縮方式の一つであり、そのファイル形式を指すこともあります。主に写真などの自然画の圧縮に適しており、非可逆圧縮(情報を一部失うことで高い圧縮率を実現)が特徴です。JPEGの圧縮プロセスは、主に以下のステップで構成されます。

  1. 色空間変換: RGB形式の画像をYCrCb形式に変換します。Yは輝度(明るさ)、CbとCrは色差(青と赤の成分)を表します。人間の目は輝度情報に敏感で、色差情報には比較的鈍感であるため、色差情報を間引くことで(クロマサブサンプリング)高い圧縮率を実現できます。
  2. クロマサブサンプリング: CbとCr成分の情報を間引きます。一般的な方式として、4:4:4(間引かない)、4:2:2(水平方向に半分に間引く)、4:2:0(水平・垂直方向に半分に間引く)などがあります。
  3. DCT (Discrete Cosine Transform): 画像を8x8ピクセルのブロックに分割し、各ブロックに対して離散コサイン変換を適用します。これにより、空間領域のピクセル値が周波数領域の係数に変換されます。低周波成分は画像の全体的な構造を、高周波成分は細かいディテールを表します。
  4. 量子化: DCTによって得られた周波数係数を量子化テーブル(Quantization Table)を用いて丸めます。これにより、高周波成分の情報を積極的に間引くことで、人間の目には感知しにくい細部を削除し、圧縮率を高めます。量子化は非可逆圧縮の主要な部分です。
  5. エントロピー符号化: 量子化された係数をさらに効率的に圧縮するために、ハフマン符号化(Huffman Coding)や算術符号化(Arithmetic Coding)などのエントロピー符号化を適用します。これは可逆圧縮であり、データの統計的性質を利用して冗長性を排除します。

ベースラインJPEGとプログレッシブJPEG

JPEGには、主に2つのエンコード方式があります。

  • ベースラインJPEG (Baseline JPEG):

    • 画像を上から下へ、左から右へと一度にエンコード・デコードする最も一般的な形式です。
    • 画像全体がダウンロードされるまで表示が開始されません。
    • シンプルで実装が容易ですが、大きな画像では表示までに時間がかかることがあります。
  • プログレッシブJPEG (Progressive JPEG):

    • 画像を複数回に分けてエンコード・デコードする形式です。
    • 最初のパスでは低品質(低解像度または粗いディテール)の画像が表示され、その後のパスで徐々に詳細な情報が追加されていきます。これにより、画像全体がダウンロードされる前にユーザーにプレビューを提供できます。
    • ウェブブラウザなどで画像を読み込む際に、ぼやけた画像から徐々に鮮明になる表示を見たことがあるかもしれません。これがプログレッシブJPEGの典型的な動作です。
    • プログレッシブJPEGは、主に以下の2つの手法を組み合わせて実現されます。
      • スペクトル選択 (Spectral Selection): DCT係数を周波数帯域ごとに分割して送信します。例えば、最初のパスでDC成分(最も低周波で画像の平均色を表す)のみを送信し、その後のパスでAC成分(高周波でディテールを表す)を送信します。
      • 逐次近似 (Successive Approximation): DCT係数のビットプレーン(各係数の最上位ビットから最下位ビットまで)を分割して送信します。例えば、最初のパスで各係数の上位ビットのみを送信し、その後のパスで下位ビットを追加して精度を高めます。

Go言語の image パッケージ

Go言語の標準ライブラリには、画像処理のための image パッケージとそのサブパッケージ(image/jpeg, image/png など)が含まれています。

  • image.Image インターフェースは、Goにおける一般的な画像を表します。
  • image/jpeg パッケージは、JPEG形式の画像をエンコード・デコードするための機能を提供します。
  • jpeg.Decode(r io.Reader) 関数は、io.Reader からJPEGデータを読み込み、image.Image インターフェースを実装する画像オブジェクトを返します。

JPEGの内部構造とスキャン (Scan)

JPEGファイルは、様々なマーカー(セグメントの開始を示す2バイトのコード)とそれに続くデータで構成されます。主要なマーカーには以下のようなものがあります。

  • SOF (Start Of Frame): 画像のフレーム情報を定義します。ベースラインJPEGでは SOF0 (0xFFC0)、プログレッシブJPEGでは SOF2 (0xFFC2) が使用されます。
  • DHT (Define Huffman Table): ハフマンテーブルを定義します。
  • DQT (Define Quantization Table): 量子化テーブルを定義します。
  • SOS (Start Of Scan): スキャン(実際の画像データ)の開始を示します。プログレッシブJPEGでは、複数のSOSセグメントが存在し、それぞれが画像の異なる部分(スペクトル選択)や異なる精度(逐次近似)のデータを運びます。
  • RST (Restart Interval): リスタートマーカー。データの同期ポイントを提供し、エラー耐性を高めます。
  • EOI (End Of Image): 画像の終了を示します。

JPEGデコーダは、これらのマーカーを解析し、対応するデータを読み込んで画像を再構築します。特にプログレッシブJPEGでは、複数のスキャンを処理し、各スキャンで得られた情報を既存の画像データに統合していく必要があります。

技術的詳細

このコミットは、Goの image/jpeg パッケージがプログレッシブJPEGをデコードできるように、既存のデコーダロジックを大幅に拡張しています。

プログレッシブJPEGデコードのメカニズム

プログレッシブJPEGのデコードは、ベースラインJPEGとは異なり、画像データを複数回の「スキャン」に分けて処理します。各スキャンは、画像の特定の周波数帯域(スペクトル選択)または特定のビット精度(逐次近似)の情報を伝送します。

  1. decoder 構造体の拡張:

    • progressive (bool): 現在のJPEGがプログレッシブ形式であるかを示すフラグ。
    • eobRun (uint16): End-of-Band (EOB) run。逐次近似デコードにおいて、連続するゼロ係数の数を効率的に表現するために使用されます。セクションG.1.2.2で定義されています。
    • progCoeffs ([nColorComponent][]block): プログレッシブモードのスキャン間で係数ブロックの状態を保存するためのフィールド。各コンポーネント(Y, Cb, Cr)ごとに、8x8ブロックのDCT係数を保持します。
  2. processSOS 関数の変更:

    • processSOS 関数は、SOSマーカー(Start Of Scan)の処理を担当します。プログレッシブJPEGでは、この関数が各スキャンのデータ(DC成分、AC成分、スペクトル選択、逐次近似の情報)を読み込み、デコードロジックを制御します。
    • zigStart, zigEnd, ah, al といった変数が導入されました。これらは、現在のスキャンが処理するDCT係数の範囲(zigStart から zigEnd まで)と、逐次近似の精度(ah は上位ビット、al は下位ビット)を定義します。これらはJPEG仕様のSs, Se, Ah, Alに対応します。
    • ベースラインJPEGではこれらの値は固定(0/63/0/0)ですが、プログレッシブJPEGではSOSセグメントのデータから読み取られます。
    • d.progCoeffs を初期化し、プログレッシブモードでの係数保存を可能にします。
    • MCU (Minimum Coded Unit) の処理ロジックが、プログレッシブモードの特性に合わせて変更されました。特に、ブロックの走査順序が、DC成分とAC成分で異なる場合があります。
  3. scan.go の導入と refine 関数の実装:

    • 新しく scan.go ファイルが追加され、プログレッシブJPEGの逐次近似デコードにおける「リファインメント(洗練)」処理を行う refine 関数が実装されました。
    • refine 関数は、既存の係数ブロック b に対して、新しいスキャンで得られた情報(delta)を適用し、係数の精度を高めます。
    • DC成分のリファインメントはシンプルで、新しいビットがセットされていれば delta を加算します。
    • AC成分のリファインメントはより複雑で、ハフマン符号化されたデータからゼロラン(連続するゼロ係数)と非ゼロ係数の情報を読み取り、既存の係数を更新します。
    • eobRun の処理もこの関数内で管理され、連続するゼロ係数の終端を効率的に検出します。
  4. ハフマンデコーダの変更 (huffman.go):

    • bits 構造体の a フィールドが int から uint32 に変更され、ビット操作の安全性が向上しました。
    • decodeBitdecodeBits という新しい関数が追加され、ハフマンデコーダから単一ビットまたは複数ビットを読み取るための低レベルなインターフェースを提供します。これらはプログレッシブデコードの逐次近似フェーズで必要となります。
    • processDHT 関数内の isBaseline 定数が !d.progressive に変更され、プログレッシブモードでのハフマンテーブルの処理が適切に行われるようになりました。
  5. 性能への影響:

    • コミットメッセージに記載されているように、プログレッシブJPEGのデコード機能の追加により、ベースラインJPEGのデコード性能が約10%低下しました。これは、コードの複雑性が増し、プログレッシブデコードのための追加の処理(係数の保存、リファインメントなど)が必要になったためです。
    • ベンチマーク結果:
      • Before: BenchmarkDecode 2855637 ns/op (21.64 MB/s)
      • After:
        • BenchmarkDecodeBaseline 3178960 ns/op (19.44 MB/s)
        • BenchmarkDecodeProgressive 4082640 ns/op (15.14 MB/s)
    • プログレッシブJPEGのデコードは、ベースラインJPEGよりもさらに時間がかかることが示されています。これは、複数回のスキャン処理と係数の逐次的な更新が必要となるため、当然の結果と言えます。

テストデータの生成

コミットメッセージには、新しいテストデータ(プログレッシブJPEGファイル)を生成するためのコマンドが詳細に記載されています。これは、convert (ImageMagick) と cjpeg (libjpeg-turboの一部) を使用して、様々な品質設定、クロマサブサンプリング方式、およびプログレッシブエンコードオプションでJPEGファイルを生成するものです。これにより、新しいデコーダが多様なプログレッシブJPEGファイルを正しく処理できることを保証します。

コアとなるコードの変更箇所

このコミットで変更された主要なファイルと、その変更の概要は以下の通りです。

  • src/pkg/image/decode_test.go:
    • プログレッシブJPEGのテストケースが追加されました。video-001.progressive.jpeg を使用して、デコードが正しく行われるかを確認します。
  • src/pkg/image/jpeg/huffman.go:
    • ハフマンデコーダの内部状態を保持する bits 構造体のフィールド型が変更されました。
    • プログレッシブデコードに必要な decodeBit および decodeBits 関数が追加されました。
    • processDHT 関数内のベースラインモード判定ロジックが、プログレッシブモードを考慮するように修正されました。
  • src/pkg/image/jpeg/reader.go:
    • JPEGデコーダの主要なロジックが含まれるファイルです。
    • decoder 構造体に progressive, eobRun, progCoeffs フィールドが追加されました。
    • processSOS 関数が大幅に修正され、プログレッシブJPEGのスキャン処理(スペクトル選択、逐次近似)に対応しました。これには、MCUの走査順序の変更や、係数ブロックの保存・ロードロジックが含まれます。
    • decode 関数内で sof2Marker (プログレッシブJPEGのSOFマーカー) が認識され、d.progressive フラグが設定されるようになりました。
  • src/pkg/image/jpeg/reader_test.go:
    • 新しく追加されたテストファイルです。
    • TestDecodeProgressive 関数が実装され、ベースラインJPEGとプログレッシブJPEGのデコード結果がピクセルデータレベルで一致するかを検証します。
    • ベンチマーク関数 (BenchmarkDecodeBaseline, BenchmarkDecodeProgressive) が追加され、デコード性能を測定します。
  • src/pkg/image/jpeg/scan.go:
    • 新しく追加されたファイルです。
    • プログレッシブJPEGの逐次近似デコードにおける「リファインメント」処理を行う refine 関数と、その補助関数 refineNonZeroes が実装されています。
  • src/pkg/image/jpeg/writer_test.go:
    • 既存の BenchmarkDecode 関数が削除されました。これは reader_test.go に移動されたためです。
  • src/pkg/image/testdata/:
    • プログレッシブJPEGのテストデータファイルが多数追加されました。これらは、様々な品質、クロマサブサンプリング、プログレッシブエンコード設定で生成されたものです。

コアとなるコードの解説

src/pkg/image/jpeg/reader.go の変更点

reader.go はJPEGデコーダの心臓部であり、プログレッシブJPEGのサポートのために最も大きな変更が加えられました。

decoder 構造体の拡張

type decoder struct {
	// ... 既存のフィールド ...
	progressive   bool
	eobRun        uint16 // End-of-Band run, specified in section G.1.2.2.
	comp          [nColorComponent]component
	progCoeffs    [nColorComponent][]block // Saved state between progressive-mode scans.
	huff          [maxTc + 1][maxTh + 1]huffman
	quant         [maxTq + 1]block // Quantization tables, in zig-zag order.
	// ... 既存のフィールド ...
}
  • progressive: 現在デコード中のJPEGがプログレッシブ形式であるかを示すフラグ。sof2Marker が検出された場合に true に設定されます。
  • eobRun: プログレッシブJPEGの逐次近似デコードにおいて、連続するゼロ係数の数を追跡するために使用されます。
  • progCoeffs: プログレッシブモードでは、各スキャンで部分的にデコードされたDCT係数を保存し、次のスキャンでそれらを「洗練」していく必要があります。このフィールドは、各カラーコンポーネント(Y, Cb, Cr)ごとに、8x8ブロックの係数を保持するためのスライスです。

processSOS 関数の変更

processSOS 関数は、SOS (Start Of Scan) マーカーを処理し、実際の画像データ(スキャンデータ)のデコードを開始します。プログレッシブJPEGのサポートにより、この関数は大幅に複雑化しました。

func (d *decoder) processSOS(n int) error {
	// ... (既存のヘッダー解析ロジック) ...

	// zigStart and zigEnd are the spectral selection bounds.
	// ah and al are the successive approximation high and low values.
	// The spec calls these values Ss, Se, Ah and Al.
	// ... (コメントで詳細な説明) ...
	zigStart, zigEnd, ah, al := 0, blockSize-1, uint(0), uint(0)
	if d.progressive {
		zigStart = int(d.tmp[1+2*nComp])
		zigEnd = int(d.tmp[2+2*nComp])
		ah = uint(d.tmp[3+2*nComp] >> 4)
		al = uint(d.tmp[3+2*nComp] & 0x0f)
		// ... (エラーチェック) ...
	}

	// ... (画像初期化ロジック) ...
	if d.img1 == nil && d.img3 == nil {
		d.makeImg(h0, v0, mxx, myy)
		if d.progressive {
			for i := 0; i < nComp; i++ {
				compIndex := scan[i].compIndex
				d.progCoeffs[compIndex] = make([]block, mxx*myy*d.comp[compIndex].h*d.comp[compIndex].v)
			}
		}
	}

	// ... (MCUループの開始) ...
	for my := 0; my < myy; my++ {
		for mx := 0; mx < mxx; mx++ {
			for i := 0; i < nComp; i++ {
				compIndex := scan[i].compIndex
				// ... (ブロックの座標計算ロジック) ...

				// Load the previous partially decoded coefficients, if applicable.
				if d.progressive {
					b = d.progCoeffs[compIndex][my0*mxx*d.comp[compIndex].h+mx0]
				} else {
					b = block{}
				}

				if ah != 0 { // Successive approximation refinement
					if err := d.refine(&b, &d.huff[acTable][scan[i].ta], zigStart, zigEnd, 1<<al); err != nil {
						return err
					}
				} else { // Baseline or progressive initial scan
					zig := zigStart
					if zig == 0 { // DC component
						// ... (DC成分のデコードロジック) ...
						b[0] = dc[compIndex] << al // Apply successive approximation low bit
					}

					if zig <= zigEnd && d.eobRun > 0 {
						d.eobRun--
					} else {
						// ... (AC成分のデコードロジック) ...
						// Handles EOB (End of Block) and EOB run for progressive
						// b[unzig[zig]] = ac << al // Apply successive approximation low bit
					}
				}

				if d.progressive {
					if zigEnd != blockSize-1 || al != 0 {
						// We haven't completely decoded this 8x8 block. Save the coefficients.
						d.progCoeffs[compIndex][my0*mxx*d.comp[compIndex].h+mx0] = b
						// ... (早期終了のコメント) ...
						continue
					}
				}

				// Dequantize, perform the inverse DCT and store the block to the image.
				for zig := 0; zig < blockSize; zig++ {
					b[unzig[zig]] *= qt[zig]
				}
				idct(&b)
				// ... (画像への書き込みロジック) ...
			}
			// ... (リスタートマーカー処理) ...
		}
	}
	return nil
}
  • zigStart, zigEnd, ah, al: これらの変数は、プログレッシブJPEGのスキャンがどの周波数帯域(スペクトル選択)とどのビット精度(逐次近似)を処理するかを決定します。SOSヘッダーからこれらの値が読み取られます。
  • d.progCoeffs の利用: プログレッシブモードでは、各8x8ブロックのDCT係数は、スキャン間で d.progCoeffs に保存されます。次のスキャンでは、この保存された係数をロードし、新しい情報で「洗練」します。
  • ah != 0 (逐次近似のリファインメント): ah がゼロでない場合、現在のスキャンは逐次近似のリファインメントパスであることを意味します。この場合、新しく導入された d.refine 関数が呼び出され、既存の係数に新しいビット情報を追加します。
  • eobRun の処理: プログレッシブJPEGのAC成分デコードでは、eobRun を使用して連続するゼロ係数を効率的にスキップします。
  • 部分的なデコードと保存: プログレッシブJPEGでは、画像全体が完全にデコードされる前に、部分的な結果を d.progCoeffs に保存し、次のスキャンでそれらを更新し続ける必要があります。zigEnd != blockSize-1 || al != 0 の条件は、ブロックがまだ完全にデコードされていないことを示し、その場合は係数を保存して次のブロックに進みます。

src/pkg/image/jpeg/scan.go の新規追加

このファイルは、プログレッシブJPEGの逐次近似デコードにおける「リファインメント」ロジックをカプセル化するために導入されました。

package jpeg

// refine decodes a successive approximation refinement block, as specified in
// section G.1.2.
func (d *decoder) refine(b *block, h *huffman, zigStart, zigEnd, delta int) error {
	// Refining a DC component is trivial.
	if zigStart == 0 {
		// ... (DC成分のリファインメント) ...
		return nil
	}

	// Refining AC components is more complicated; see sections G.1.2.2 and G.1.2.3.
	zig := zigStart
	if d.eobRun == 0 {
	loop:
		for ; zig <= zigEnd; zig++ {
			// ... (ハフマンデコードと値の解析) ...
			switch val1 {
			case 0:
				// ... (EOB run の処理) ...
				break loop
			case 1:
				// ... (非ゼロ係数のリファインメント) ...
			default:
				return FormatError("unexpected Huffman code")
			}
			// ... (refineNonZeroes の呼び出し) ...
		}
	}
	if d.eobRun > 0 {
		d.eobRun--
		// ... (refineNonZeroes の呼び出し) ...
	}
	return nil
}

// refineNonZeroes refines non-zero entries of b in zig-zag order. If nz >= 0,
// the first nz zero entries are skipped over.
func (d *decoder) refineNonZeroes(b *block, zig, zigEnd, nz, delta int) (int, error) {
	// ... (非ゼロ係数のリファインメントロジック) ...
}
  • refine 関数:
    • b: 現在処理中の8x8ブロックのDCT係数。
    • h: AC成分のハフマンテーブル。
    • zigStart, zigEnd: 現在のスキャンが処理する係数のジグザグ順序での範囲。
    • delta: 逐次近似のステップサイズ(1 << al)。
    • この関数は、DC成分とAC成分のリファインメントロジックを実装しています。ハフマンデコードを行い、新しいビット情報に基づいて既存の係数を更新します。
    • eobRun を利用して、連続するゼロ係数を効率的にスキップします。
  • refineNonZeroes 関数:
    • refine 関数から呼び出される補助関数で、ブロック内の非ゼロ係数をジグザグ順序で走査し、新しいビット情報に基づいてそれらを洗練します。

これらの変更により、Goの image/jpeg パッケージは、プログレッシブJPEGの複雑なデコードプロセスを正確に処理できるようになりました。

関連リンク

参考にした情報源リンク