« Maxima メモ | トップページ | Google マップのストリート・ビュー日本版 »

HSB の色調整を LUT だけで処理する方法

 Maxima のおかげで、また一つ昔考えたアルゴリズムを思い出した。今度は、画像処理をやっていたころのものである。

 画像処理というのは、いろんなコンピュータのアプリケーションの中でも、計算量の多いことで悪名高い処理だ。その理由は、単純に処理しなくてはならないデータが多いから。たとえば、ビットマップだったら、100×100 ピクセルぐらいの小さな画像でも、単純に計算して 1 万ピクセルの処理が必要だし、現代のコンピュータで標準的なディスプレイサイズの画像だったら、1000×1000 ピクセルぐらいなので 100 万ピクセル、印刷用の画像に至ってはさらにこの何百倍何万倍のピクセルを処理しなくてはならない。したがって、画像処理において、アルゴリズムの最適化はきわめて重要だ。

 画像処理のアルゴリズムは、いくつかの種類に分けられる。そのうちで最も簡単なのは、いわゆるポイント・プロセス(Point Process)と呼ばれるものだ。このアルゴリズムでは、変換前の画像の各ピクセルと変換後の画像の各ピクセルが 1 対 1 に対応しており、変換後のピクセルの属性は変換前のピクセルの属性だけで決まる。このようなアルゴリズムは、変換前のピクセルの属性を p、変換後のピクセルの属性を p' とすると、

p' = f(p)

で表せる。たとえば、画像が RGB のフルカラー画像だったとすると、

r' = Fr( r, g, b )

g' = Fg( r ,g, b )

b' = Fb( r, g, b )

という形になる。実際には、かなりの種類の画像処理アルゴリズムが、このポイント・プロセスに分類される。

 一方、ぼかし、ノイズ除去、エンボス、エッジ検出、モーフィングなどの処理はポイント・プロセスでは処理できない。このような処理を行うには、特定のピクセルの情報だけでなく、その近傍のピクセルの情報や、もっと大域的な画像全体の情報が必要になる。が、ここではその話は余談だ。

 さて、このポイント・プロセスの中でもっとも単純な形は、変換後の各色成分が、他の色成分に依存しない、言い換えれば、r' が r、g' が g、b' が b だけで決まるというものだ。式で書くと、次のような形になる。

r' = Fr( r )

g' = Fg( g )

b' = Fb( b )

 非常にシンプルな計算だが、実は、輝度調整、コントラスト、ポスタライズなどの処理はこの形で表すことができる。

 これだけシンプルな計算だと、計算量も知れてるように思う人もいるかもしれないが、Fr、Fg、Fb 自体が計算量の多い関数だと、この形であっても必ずしも無視できない計算量になる可能性がある。たとえば、

newImage[R] = (unsigned char)sqrt( ( float )oldImage[R] );

newImage[G] = (unsigned char)sqrt( ( float )oldImage[G] );

newImage[B] = (unsigned char)sqrt( ( float )oldImage[B] );

なんていうコードだったら、なかなか馬鹿にならない計算量が必要になることがわかるだろう。

 ところが、このような形の場合、Fr、Fg、Fb がどのような形の関数であっても、ほとんど計算量をかけずに済ます方法があることが知られている。それは、LUT(Look Up Table)を使う方法だ。つまり、変数と関数値の対応表を先に計算してメモリに保存しておくのである。

 たとえば、RGB 24 ビットカラーの画像の場合、各ピクセルの R、G、B 値はそれぞれ 8 ビット= 0~255 の整数で表される。つまり、対応表のエントリは 256 個あれば十分である。そしてこの場合、変換後の画像も同じ RGB 24 ビットであるから、各エントリのサイズも 8 ビット= 1 バイト確保すればよい。つまり、1 × 256 = 256 バイトのテーブルがあれば、各関数の変数と関数値の対応表を保存することができる。たとえば、上記の sqrt の例だったら、次のようなコードを書けばよい。

unsigned char sqrtLUT[256];

for( int i = 0; i < sizeof( sqrtLUT ); i++ )

sqrtLUT[i] = ( unsigned char )sqrt( (float)i );

こうしておけば、上記のコードは次のように書き換えられる。 

newImage[R] = sqrtLUT[oldImage[R]];

newImage[G] = sqrtLUT[oldImage[G]];

newImage[B] = sqrtLUT[oldImage[B]];

 定義域全体に対する関数値がすべて必要とは限らないのに、このコードのようにすべて計算してしまうのはムダではないかと思う人もいるかもしれない。しかし実際には、先のコードは画像の全ピクセルに対して行う必要があるわけであるから、冒頭に述べたように、何万回~何百万回以上計算することになるわけだ。そう考えれば、このコードでは 256 回(Fr、Fg、Fb がすべて異なる場合でも 256 × 3 = 768 回)計算すれば後はまったく計算しなくてもいいわけだから、差し引きすれば計算量を大幅に節約できているわけである。

 実は、ここまでは画像処理をやったことのある人にとっては常識の部類であろう(もっとも、ぼくがやっていたころは、この程度のアルゴリズムですら日本語の文献にはほとんど載っていなかった!)。

 ところが、この LUT を利用する方法は、あくまで Fr、Fg、Fb がそれぞれ r、g、b だけの関数として表せる場合専用であり、これを一般のポイント・プロセスに応用しようとすると、とたんに壁にぶつかる。先程と同じように、F( r, g, b ) の変数と関数値すべての対応表を作ることを考えてみよう。仮に、さっきと同じく r、g、b が各 8 ビットだったとしても、r、g、b すべての可能な組み合わせは 256 × 256 × 256 = 2 ^ ( 8 × 3 ) = 16777216 もある。ということは、この LUT を保存するには約 16MB ものメモリが必要だ。仮にスタックのような一時メモリに保存することにして、画像処理関数の呼び出し時に計算し直したとしても、今度は、16MB もの関数値を先に計算するには、4000 × 4000 ピクセル程度の画像全体を処理するのと同じ程度の計算量が必要になる。これでは LUT を使う意味がない。

 さて、いよいよここから先がぼくが考えたアイデアである。確かに一般の F( r, g, b ) の LUT を計算するのは非現実的だ。それなら、一般の F( r, g, b ) よりも、ちょっとだけ厳しい制約条件をつけたらどうだろう。たとえば、F を r、g、b の関数の和に分解できる場合に限定するのである。つまり、

r' = Rr(r) + Rg(g) + Rb(b)

g' = Gr(r) + Gg(g) + Gb(b)

b' = Br(r) + Bg(g) + Bb(b)

という形を考えるのだ。これなら、LUT を作るために必要なメモリは、256 × 9 = 2304、つまり約 2K バイトですむ。もっともこの場合、関数の値域が 8 ビットだからと言って、途中の計算も 8 ビットですむとは限らないという点には注意をしなければならない。たとえば、Rr(r) = 5000、Rg(g) = 5000、Rb(b) = -9999 だったら、Rr(r) + Rg(g) + Rb(b) = 1 となって、各関数値は 8 ビットの範囲に収まっていないにもかかわらず、その和は 8 ビットの範囲に収まってしまう。だから、各 LUT のビット長がどれだけ必要かは、それぞれの関数形を見て決めなくてはならない。もっとも、それにしたって、2K が 4K か 8K になるぐらいの話で済むはずで、先程の 16MB に比べれば遥かに現実的なサイズになる。

 しかし、このような制限された関数でできる、何か役に立つ処理があるのだろうか。実はちゃんとある。それが HSB による色調整だ。なぜ HSB がこのような形で表せるかというと、RGB から HSB への変換というのは、要するに色空間の座標変換だからだ。

 色というのは、RGB で表そうが HSB で表そうが、常に 3 つのパラメータによって表される。これは空間の次元数と同じなので、このようなパラメータの空間は色空間と呼ばれる。RGB も HSB も、そのような色空間の座標系のとりかたの 1 つにすぎない。ためしに、RGB から HSB の座標変換がどうなるかを考えてみよう。

 B(Brightness: 明るさ)というのは、色と関係なく、暗ければ小さく、明るければ大きくなる。RGB 座標系でこのような性質を持つのは、(1, 1, 1) のように r = g = b となるようなベクトルである。したがって、この方向の単位ベクトルと内積をとれば、B 軸の成分を抽出できる。そのような単位ベクトルは、

8.png

である。さて、B 軸が決まれば、RGB 空間の任意のベクトルを B 軸方向のベクトルと B 軸に直交する方向のベクトルとに分けることができる。この直交する方のベクトルは、明るさ成分がなく色成分だけを持つベクトルである。このベクトルを、B 軸に直交する平面上の極座標で表したときに、そのベクトルの絶対値が S(Saturation: 彩度)、回転角が(Hue: 色相)になる。

 ただ、ここでいきなり極座標に変換してしまうと、線形代数的に扱いにくくなるので、まず、B 軸に直交する平面上に、互いに直交する単位ベクトルを 2 つ任意にとって直交座標系をつくり、座標変換してしまおう。この場合、その平面上での軸の方向はわりとどうでもよいので(その理由は後でわかる)、仮に、

10.png

12.png

の 2 つにしておく。すると、この座標変換を表す行列は、次のようになる。

14.png

 さて、この行列で RGB 色座標を座標変換した結果を ( HS1, HS2, B ) としよう。ここまでくれば、HSB の色調整は簡単にできる。まず、B はそのまま明るさを表しているから、これにそのまま調整倍率(b)を掛ければよい。HS1、HS2 は、色相と彩度を直交座標で表したものであるから、HS1 と HS2 のそれぞれに彩度の調節倍率(s)をかけてから、色相の調整量(h)だけ座標軸を回転させればよい。つまり、座標全体に次のような行列をかければよい。

18.png

(cos hs というのは、cos( h * s ) ではなく、s * cos( h ) という意味。このような表記になってしまうのは Maxima の仕様らしい。)

 これで HSB 座標系での色調整は済んだので、最後に色座標を元の RGB 座標系に戻してやれば処理は完成だ。そのためには、先程の座標変換行列の逆行列を掛けてやればよい。その逆行列は次のようになる。

16.png

(このように、最終的には元の RGB 座標系に戻すので、途中での軸のとりかたは恣意的でよいわけである。これはいわば、行列の対角化の逆をやっているとも言える。)

 したがって、この HSB 座標系による色調整の全体は、この座標変換行列と HSB 調整行列と座標逆変換行列の 3 つの行列をすべてかけたものになる。これは手作業でやると非常に面倒な計算で、ぼくが十数年前に実装したときには何時間もかけて計算したものだが、今は Maxima 様に頼めば一瞬でやってくれる(^^)。

20.png

 このように、HSB 座標系での色調整は、最終的には RGB 色座標に 1 個の 3 × 3 行列を掛けるのと同じことになる。 このような行列の掛け算による線形変換が、先に述べた各成分の関数の和として表せることはもはや説明するまでもないだろう。この式自体は確かにかなりゴチャゴチャしているが、実際に処理する際には LUT を作るときに一回計算するだけなので、いくらゴチャゴチャしてても問題ない。こうすれば、HSB による色調整を LUT だけで処理することができるのである。

|

« Maxima メモ | トップページ | Google マップのストリート・ビュー日本版 »

パソコン・インターネット」カテゴリの記事

数学」カテゴリの記事

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/67762/42078622

この記事へのトラックバック一覧です: HSB の色調整を LUT だけで処理する方法:

« Maxima メモ | トップページ | Google マップのストリート・ビュー日本版 »