ASP.NET 画像の色量子化の最適化

[アーティクル]
06/24/2011

モーガン・スキナー
Microsoft Developer Services

2003 年 5 月

概要：.NET Framework バージョン 1.0 および 1.1 での GDI+ の制限を克服するために、ASP.NET ページで動的に生成されたイメージを量子化 (色変更) する方法について説明します。この記事では、画像の色深度を減らす 2 つの方法について説明します。 (13ページ印刷)

適用先:
   Microsoft Framework バージョン 1.0 および 1.1
   Microsoft Visual C#
   Microsoft ASP.NET

DotNET_Color_Quantization_Code.exe サンプルファイルをダウンロードします。

内容

はじめに
問題の概要
量子化の概要
パレットベースの量子化
Octree ベースの量子化
Web サイトの例
まとめ
詳細情報
著者について

はじめに

ほとんどの Web サイトには、MSDN Web サイトのバナー見出しや、最近の見出しの一覧で使用できるサムネイル画像など、何らかの形式のグラフィックスが含まれています。これらのイメージはすべて静的です。これらは Web チームのメンバーによって生成され、Web サイトの要件に合わせて色が変更され、必要に応じて使用されるディスクに格納されます。

ASP.NET では、動的イメージ (現在の Web 要求の処理中に作成されるイメージ) を作成することもできます。これには、Web デザイナーのサービスを必要とせずに、サイトをカスタマイズしたり、特定のビジュアルスタイルに準拠するイメージを生成したりする用途があります。

イメージの生成は比較的簡単です。描画するサーフェスを作成し、適切なイメージをレンダリングし、これをユーザーに返される ASP.NET 応答ストリームに保存します。

このシナリオの唯一の問題は、結果のイメージの品質です。既定では、GDI+ は、GIF や JPEG などの Web ページに適したイメージにビットマップを変換するときに、Web セーフパレットを利用します。 (詳細については、この記事の最後を参照してください)。結果として得られる画像は品質が悪く、使用される減色アルゴリズムのさまざまな迷走色が含まれている可能性があります。この Web セーフパレットへの変換は、画像が出力の種類 (GIF や JPEG など) に変換される前に発生するため、出力の種類で多くの色がサポートされている場合でも、Web セーフパレットの色を使用するようにイメージが生成されます。

結果の画像の品質に加えて、画像の色を変更するもう 1 つの理由は速度です。一般に、1 ピクセルあたり 4 バイトより 1 バイトを使用する Web サイトから画像をダウンロードする方が高速であり、誰もが ADSL を持っているわけではありません。さらに、特定のブラウザー (WebTV など) には色空間が限られているため、顧客に良いイメージを提供するために色を変更する必要があります。

色を減らしたパレットを割り当てるために画像の色を変更するプロセスは、 量子化と呼ばれるものです。

問題の概要

既定の GDI+ イメージレンダリングの結果を確認するには、イメージ生成の簡単な例を示し、このイメージを要求する Web ページからの結果の出力を示します。

たとえば、オンライン銀行に勤務していて、クレジットカードサインアッププロセスの一環として、顧客は定義済みの一連の画像から画像を選択してカードをカスタマイズできるとします。サインアッププロセス中に "顧客の名前" をキャプチャした可能性があるため、画像に名前が浮き出したクレジットカードの表現をレンダリングできると便利です。

Aa479306.colorquant01(en-us,MSDN.10).gif

図 1. (架空の) MSDN クレジットカードの背景ビットマップ

ユーザーに表示されるイメージは、バックグラウンドビットマップ (MSDN カード) を読み込み、その上にテキストをレンダリングしてイメージをカスタマイズすることによって作成されます。次のコードは、アセンブリマニフェストからイメージを読み込み、顧客の名前をその上に浮き出し、ASPX ページからこれを返す方法を示しています。

// Obtain a stream over the background image resource
Assembly assem = Assembly.GetExecutingAssembly ( ) ;

using ( Stream   s = assem.GetManifestResourceStream 
                           ( "TestApp.MSDNCard.gif" ) )
{
   // And load the resource into a bitmap
   Bitmap   background = Bitmap.FromStream ( s ) as Bitmap ;

   Bitmap copy = new Bitmap ( background ) ;

   // Now construct a graphics object from the bitmap 
   // so that I can render onto it
   using ( Graphics g = Graphics.FromImage ( copy ) )
   {
      // Get a credit-card-like font
      Font textFont = new Font ( "Lucida Console" , 10 , FontStyle.Bold ) ;

      // Render the name of the card owner
      g.DrawString ( cardholder , textFont , Brushes.Silver , 12 , 130 ) ;
      g.DrawString ( cardholder , textFont , Brushes.White , 13 , 131 ) ;

      // And then the expiry date
      StringFormat   fmt = new StringFormat ( ) ;
      fmt.Alignment = StringAlignment.Far ;

      g.DrawString ( "June 04" , textFont , Brushes.Silver , 
        new RectangleF ( 186 , 130 , 100 , 20 ) , fmt ) ;
      g.DrawString ( "June 04" , textFont , Brushes.White , 
        new RectangleF ( 187 , 131 , 100 , 20 ) , fmt ) ;
   }

   // Return the image
   Response.ContentType = "image/gif" ;

copy.Save ( Response.OutputStream , ImageFormat.Gif ) ;
}

この例の画像は、現在のアセンブリ内に含まれています。これを自分で行うには、イメージ (または他のリソース) をプロジェクトに追加し、[ ビルドアクション ] を [埋め込みリソース] に設定します。 ビルドアクション プロパティには、Visual Studio .NET の任意のファイルの種類の [プロパティ] ウィンドウからアクセスできます。

その後、画像にテキストを描画します。ここでは、最初にテキストをシルバーで描画し、X 軸と Y 軸のピクセルでオフセットし、テキストを白で再描画することで、粗い浮き出しの外観を作成しました。これにより、擬似浮き出しの外観が生成され、この例では確かに十分です。

このイメージが ASP ページに返される (またはディスクに保存された) 場合、出力は Web セーフパレットを使用して色が減ります。これにより、出力の種類 (GIF、JPEG など) に関係なく、次の画像が作成されます。

Aa479306.colorquant02(en-us,MSDN.10).gif

図 2. 既定のパレットを使用して返されるディザリングされたイメージ

この図の吹き出しからわかるように、結果の画像は非常に "粗い" です。これは、イメージを 256 色に減らすために必要なディザリングと、結果のイメージが 256 色のカスタムパレットではなく Web セーフパレットを利用していることが原因です。

必要なのは、画像の色深度を 256 色 (またはそれ以下) に減らし、画像に固有のパレット情報を含む GIF を生成する方法です。このプロセスは一般に 量子化と呼ばれる。

量子化の概要

画像を量子化するプロセスは簡単に記述できます。ソースイメージ内の各ピクセルについて、ターゲットイメージ内のそのピクセルの色を定義する値を検索または計算します。色の深さを 256 色に減らすと、通常、結果の "色" がパレットのインデックスであることを意味します。

たとえば、5000 色の不連続色を含むイメージがあり、これを 256 色の GIF に減らしたいとします。結果の画像には明らかに色の損失があり、適切な量子化アルゴリズムはこれらの損失を最小限に抑えて許容可能な画像を生成することを目指しています。

最初の手順として、ソースイメージ内の最初の 256 個の個別の色を取得し、これらをイメージ全体のパレットとして使用できます。後続の色は、これらの初期 256 にマップされます。この方法では、画像内の色の頻度は考慮されないため、多くの場合、結果が低くなります。イメージの 257 番目の色がイメージの 50% に使用されている場合は、この色がコピー先のイメージで変更されていないことを確認することをお勧めします。

スケールのもう一方の端では、32 KB スロットを含む配列を作成し、各スロットのピクセルの累積カウントを生成できます。次に、出力パレットに昇格させるピクセルと、パレットの色に変換するピクセルを決定する必要があります。最も頻繁に使用される色を最初に選択し、次に頻繁に選択し、パレットがいっぱいになるまでなどです。

どちらの場合も、アルゴリズムには 2 つのメイン部分があります。 1 つ目はソースを反復処理し、2 つ目はピクセルを量子化し、結果の画像とカラーパレットを生成することです。この知識を備えたアルゴリズムの最初の部分を作成し、画像を一度にピクセルで走査し、必要に応じて別の量子化器を接続します。

ビットマップに関するビット

アルゴリズムを生成するには、ビットマップの内部 (メモリ) 表現について少し知る必要があります。この例では、8 BPP (ピクセルあたりのビット数) または 32 BPP の画像のみを考慮します。 8 BPP イメージはピクセルごとに 1 バイトなので、16 倍 16&のイメージです。ピクセルは 256 バイトで構成されます。同じサイズの 32 BPP イメージは 1024 バイトで構成されます。各ピクセルは 4 バイトで構成されます。どちらの場合も、ビットマップのサイズなど、ビットマップに関連するオーバーヘッドは無視されます。

コンピューティングの暗い時代 (まあ、カラフルではない) では、ディスプレイアダプターの色は 256 色 (1983 年に 2 番目のコンピューターで行いました) のみになる可能性があるため、ピクセルの色は個々のバイトで識別されます。しかし、今日では、すべての男性と彼の犬は32 KB以上の色が可能なアダプターを持っているので、1バイトが色のパレットにインデックスを表すために使用されるようになりました。したがって、8 つの BPP イメージの書き込みは、ソースビットマップ内の各ピクセルのパレットインデックスを計算し、パレットエントリを設定する 2 段階のプロセスでもあります。

Aa479306.colorquant03(en-us,MSDN.10).gif

図 3: 32-BPP イメージと 8-BPP イメージ

32 BPP イメージは、色の赤、緑、青のコンポーネントに対して 8 ビットに加えて、追加の 8 ビットの "アルファ" チャネル情報で構成されます。このアルファ成分は、ピクセルの透明度を決定します。255 の値は完全に不透明で、0 の値は完全に透明です。この例の残りの部分ではこのコンポーネントを扱いませんが、(たとえば) アルファコンポーネントが定義済みの値より小さい任意の色を選択して、結果の GIF で透明にすることができます。

ソースイメージ内のバイトをループするには、ポインターを使用してプロセスを高速化するため、安全でないコードがいくつか必要になります。 Bitmap クラスには、使用できる GetPixel 関数があります。ただし、この関数は、画像内のすべてのピクセルを反復処理するのに十分な速度ではありません。

次のコードは、ソースイメージ内のすべてのピクセルをループ処理し、サンプルコードではデータを最初に通過する際に使用されます。

BitmapData   sourceData = null ;

try
{
   // Lock the source data into memory
   sourceData = bmp.LockBits ( new Rectangle ( 0 , 0 , width , height ) , 
                               ImageLockMode.ReadOnly , 
                               PixelFormat.Format32bppArgb ) ;

   // Define the source data pointers. The source row is a byte to
   // keep addition of the stride value easier (as this is in bytes).
   byte*   pSourceRow = (byte*)sourceData.Scan0.ToPointer ( ) ;
   Int32*   pSourcePixel ;

   // Loop through each row
   for ( int row = 0 ; row < height ; row++ )
   {
      // Set the source pixel to the first pixel in this row
      pSourcePixel = (Int32*) pSourceRow ;

      // And loop through each column
      for ( int col = 0 ; col < width ; col++ , pSourcePixel++ )
      {
         // Do something with *pSourcePixel
      }

      // Add the stride to the source row
      pSourceRow += sourceData.Stride ;
   }
}
finally
{
   // Ensure that the data is unlocked
   bmp.UnlockBits ( sourceData ) ;
}

イメージビットのループ処理はかなり簡単です。ポインターはメモリ内のイメージの先頭に設定され、次のピクセルにインクリメントされます。すべての行の後に、行ポインターに "stride" の値を追加し、列をもう一度反復処理します。

ビットマップの '"stride"' は、各行が占めているバイト数です。これは、画像内のピクセル数と同じである場合とそうでない場合があります。たとえば、幅が 13 ビットの 8 BPP イメージでは、ストライドが 16 になる可能性があります。これは、32 ビットコンピューターの優れた丸い数値であるためです。

出力ビットマップの生成

出力ビットマップを生成するコードは、カラーパレットを生成するために入力ビットをループするために上に示したものとよく似ています。

このインスタンスでは、ソースビットマップとコピー先ビットマップの両方の各ピクセルをループ処理し、ソースピクセルの計算されたパレットインデックスをターゲットピクセルに割り当てます。これが完了すると、完全に量子化された画像がユーザーに表示される準備が整う必要があります。次のコードスニペットは、この記事に付属するサンプルで使用されるアルゴリズムの簡略化されたバージョンです。

for ( int y = 0 ; y < height ; y++ )
   for ( int x = 0 ; x < width ; x++ )
      destinationPixel[x,y] = Quantize ( sourcePixel[x,y] ) ;

実際に使用されるアルゴリズムは、ビットマップを 2 次元配列として扱うよりも高速に実行できるため、上記ほど単純ではありません。

すべてのピクセルが変換されたので、最後に行う必要があります。発生した量子化に基づいて出力イメージが正しく表示されるように、パレットを新しく生成されたイメージに関連付ける必要があります。

パレットベースの量子化

最初に説明する例は、既知のパレットに基づいています。多くの Web サイトには、ブランド化の目的で使用される一連のカスタム色 ( www.gotdotnet.com で使用される青など) があります。ここで必要なのは、イメージを生成し、何らかの方法で生成されたパレットを使用してイメージの色を変更することです。この例では、イメージエディターを使用して架空の MSDN クレジットカードのパレットを作成しました。

パレットベースのアルゴリズムは、ソースイメージ内の各ピクセルの出力パレットで最も近い色を選択することで機能します。

この方法には、理解しやすいという利点があります。ただし、入力パレットによって制限されるという点では適応的ではありません。画像の色がパレットと大きく異なる場合は、画質が低下します。

指定されたピクセルをソースカラーからターゲットパレットインデックスに変換するために、RGB値がソースカラーに最も近い色をパレット内でスキャンするメソッドを記述しました。アルゴリズムの根性を次に示します。

int   leastDistance = int.MaxValue ;
int red = pixel->Red ;
int green = pixel->Green;
int blue = pixel->Blue;

// Loop through the entire palette, looking for the closest color match
for ( int index = 0 ; index < _colors.Length ; index++ )
{
   // Lookup the color from the palette
   Color   paletteColor = _colors[index];
   
   // Compute the distance from our source color to the palette color
   int   redDistance = paletteColor.R - red ;
   int   greenDistance = paletteColor.G - green ;
   int   blueDistance = paletteColor.B - blue ;

   int      distance = ( redDistance * redDistance ) + 
                       ( greenDistance * greenDistance ) + 
                       ( blueDistance * blueDistance ) ;

   // If the color is closer than any other found so far, use it
   if ( distance < leastDistance )
   {
      colorIndex = (byte)index ;
      leastDistance = distance ;

      // And if it's an exact match, exit the loop
      if ( 0 == distance )
         break ;
   }
}

これにより、単純な最小二乗アルゴリズムを使用して最も近い色の一致を検索し、ハッシュテーブルを使用して見つかった色を格納し、まだ量子化されていない色に対してのみパレットを走査する必要があります。これは、色の数が多い画像の場合、(メモリの観点から)高価になる可能性がありますが、何らかの形式のキャッシュがないと、アルゴリズムが非常に遅くなる可能性があります。

Octree ベースの量子化

パレットベースのアルゴリズムはかなり高速ですが、1 つの欠点に悩まされます。これはアダプティブアルゴリズムではありません。一方、Octree は、イメージ内の異なる色の数に関係なく、任意のイメージを処理できます。多くの色からより合理的なものに変換すると、劣化が少なく合理的な結果が得られます。欠点は、計算コストの高いアルゴリズムです。つまり、通常、同じ画像を量子化するにはパレットアルゴリズムよりも時間がかかります。

Octree という名前は、イメージの色を表すために使用されるデータ構造に由来します。これは多数のノードで構成され、それぞれが最大 8 人の子を持ちます。

量子化する色の値 (#6475D6) があるとします。色は個々の赤、緑、青の各コンポーネントに分割され、連続するビットは、0 から 7 の間の数値を生成するために、赤、緑、青の値からシフトされます。この値は、ツリーの作成時、および最も近い色の値を検索するときに、現在のノードから走査されるリーフを決定します。

赤 (0x64)	01100100
緑 (0x75)	01110101
青 (0xD6)	11010110
結果	47360742

上記の結果は、各構成色値のビットの組み合わせであり、RGB 色の各ビットについて次のように計算されます。

result = red | green<<1 | blue<<2 ;

ビットは最上位から最下位に走査されるため、私の例では、最上位ビット (ビット 7)、次の有効ビット (ビット 6) からシフトします。上記の例では、ツリー内で走査されるノードは次のとおりです。

Aa479306.colorquant04(en-us,MSDN.10).gif

図 4: 色#6475D6の Octree トラバーサル

前に説明したように、色が Octree に挿入されると、ノードが走査されます。リーフノードが見つかると、この特定の色のピクセル数がノード内でインクリメントされ、赤、緑、青のコンポーネントがノード内の R、G、B の値に追加されます。これらの数値は、各色の値をその色のピクセル数で割った値に基づいて、平均色を生成するために使用されます。

排除を行わないと、入力イメージに個別の色があるのと同じ数のリーフノードを持つツリーが作成されます。ツリーで広告の無限大を拡大する代わりに、Octree はイメージ全体が量子化されるとカラーパレットを形成する所定の数の葉を持つことができます。

Octrees のディスカッションは以前に MSDN で公開されました。そのため、Microsoft Systems Journal (MSJ) の 1997 年 10 月発行の Jeff Prosise のウィキッドコードに関する記事のコードを再利用しました。この例では、Jeff のコードを Visual C++ から C# に変換し、いくつかの変更を加えました。

JeffのOctreeアルゴリズムに加えたメイン変更は、量子化ループのパフォーマンスを向上することでした。私のバージョンでは、私は各量子化呼び出しの結果をキャッシュし、これは互いに隣接する同じ色のピクセルの数がある場合にプロセスを高速化することができます。ループの周りの各反復は現在のピクセルの色をチェックし、それが量子化された最後のピクセルと一致する場合は、前の結果を返すためにコードをショートサーキットすることができます。

Web サイトの例

この記事の付随するコードには、パレットベースと Octree ベースの量子化アルゴリズムの両方が含まれています。量子化の結果は、元の画像と GDI+ で量子化された画像と共に表示されます (非常に粗く表示されます)。 (下の図 5 の比較から元の画像を省略していますが、コード例で確認できます)。

画像を生成するために、画像の種類ごとに簡単な ASPX ページを作成しました。これには、次のようなコードが含まれています。

  public void RenderImage ( )
{
   using ( Bitmap image = Generator.GenerateImage ( "Octree Quantized" ) )
   {
      OctreeQuantizer   quantizer = new OctreeQuantizer ( 255 , 8 ) ;

      using ( Bitmap quantized = quantizer.Quantize ( image ) )
      {
         Response.ContentType = "image/gif" ;

         quantized.Save ( Response.OutputStream , ImageFormat.Gif ) ;
      }
   }
}

これにより、Octree 量子化器を使用してクレジットカードの量子化されたイメージが生成され、応答の種類が image/gif に設定されます。これは、img タグとして Web サイトページの例に含まれています。 <img src="OctreeQuantization.aspx"> 各 ASPX ページには、単に上記の RenderImage 関数の呼び出しが含まれています。

量子化処理の結果を以下に示します。

量子化の種類	Image	イメージサイズ (KB 単位)
なし (既定の GDI+)		21342
パレットベース		16748
Octree ベース		16744

図 5: 量子化結果の比較

パレットと Octree の結果は、Web セーフパレットを使用した既定の GDI+ レンダリングよりも 20% 小さく、画質ははるかに優れています。パレットベースの画像と Octree ベースの画像は異なります。画像にはテキストが少し異なるためです。結果は画像のサイズによって異なる場合がありますが、小さい方が優れた画像を生成する価値がある必要があります。

まとめ

ASP.NET を使用すると、その後 Web サイトに表示されるイメージを生成することで、個々のユーザー (ユーザーのセット) のサイトをカスタマイズできます。これが有利になる理由は多数あります。たとえば、現在のユーザーの言語設定に基づいてボタンキャプションを生成する必要がある場合があります。テキストを除き、基本的に同じ多数のイメージを生成するのではなく、汎用ボタンイメージを作成し、実行時にテキストをレンダリングすることができます。

この記事では、.NET の量子化の 2 つの方法を紹介しましたが、他にも多数のアルゴリズムが用意されているため、自由に実験できます。コードは拡張するように記述されているため、 クオンタイザー クラスから派生し、 QuantizePixel メソッドと GetPalette メソッドをオーバーライドし、必要に応じて InitialQuantizePixel メソッドをオーバーライドすることで、独自の量子化器をプラグインできます。このコードでは、独自のアルゴリズムをプラグインする方法の例を文書化しています。

詳細情報

Jeff Prosise、ウィキッドコード (Microsoft Systems Journal)
カラー量子化に関する FAQ とは
ロバート・ヘス安全パレット
ラジオシティ: プログラマーの視点、Wiley Professional 1994 (ISBN 0-471-30444-1)。この本は何年も印刷されていませんが、コピーはオンラインで見つけることができ、CD版も入手できます。

著者について

Morgan は、Visual C#、コントロール、WinForms、ASP.NET を専門とする、英国の Microsoft で働くアプリケーション開発コンサルタントです。 2000 年の PDC リリース以来、.NET と協力し、入社をとても気に入った。彼のホームページはで http://www.morganskinner.com、彼が書いた他のいくつかの記事へのリンクがあります。彼の空き時間(それほど多くはない)では、彼は彼の割り当てで雑草と戦い、奇妙なコーニッシュのペーストリーを楽しんだ。

次の方法で共有