« 心に残るもの | トップページ | 缶コーヒーと構造体 »

2011年3月29日 (火)The First Flight of Vector Eigen

本日、久々に当番が廻って来ました。
いや~、ブログ書くのも久々で、キーボードを叩く指も僅かに震えております。
さっきから“っ”とか“ッ”とかが頻繁に入力されやがって、バックスペースキーがいつもにも増して大活躍!みたいな。

前回の順番をお休みしていた間に、アップ休暇でバカンスしたり、GDCでバカンスしたりしていましたが、現地でのめくるめく熱烈なお色気ムンムンの恋の誘いを超華麗にスルーしつつ、無事に誰かひとりのものにならずに帰ってくることができ、35億人の皆んなの恋心を裏切らずに済んで、ホッと一安心と胸をなで下ろしております、プログラマのM.L.Kです(LはLoveのLです、Love&Game!)。

というワケで、主成分分析を使って色のグループ分けをしていきます。ええ、もちろんメディアン・カットで分けるんですけども。

主成分分析とはどういうものかについて、その考え方をきちんと説明すると、物凄く時間がかかってしまうため、ここでは割愛します。
かいつまんで言えば、どの方向から見たら分布の見晴らしがよくなるかを調べる方法なのですが、詳しいことは、Google先生とかに訊いてみて下さいね。

さて、前回は分散と共分散について説明しました。
一般的な統計解析では、分散をS^2xと書き表すのですが、少し記述の見通しを良くするために、赤チャンネルの分散をrr、緑チャンネルの分散をgg、と書くことにします。また、共分散はrgです(まあ、これは一般的な表し方なのですが)。

赤チャンネルと緑チャンネル、2つのチャンネルについて、これらの数字を以下のように並べます。

2011_0328_01_2

2×2行列ですね。
rggrについては表現は異なりますが、意味的にはいずれも赤チャンネルと緑チャンネルとの共分散ですので、同じ数字になります。

ちなみに、青チャンネルを加えた3つのチャンネルでは次の通りになります。

2011_0328_02_2

3×3行列になります。
同様にrbbrgbbgです。

なお、今回は(今回も)説明を簡単にするために、赤チャンネルと緑チャンネルの2チャンネルのみの場合についてを扱います。

閑話休題。
過去のエライ人のおかげで、ある多次元の分布について(今回の場合は2次元の分布について)上のように与えられた行列の、固有値と固有ベクトルを求めることで、分布がどの方向に対してより多く散らばっているかを調べられることが、分かっています。

固有値と固有ベクトルですか…。また、新しい言葉が出てきてしまいました…。

ある行列Aとベクトルx、そして数値λがあったとして、これらの関係が、

2011_0328_03_2

になる場合に、λをAの固有値、xをその固有ベクトルと呼びます。
かいつまんで言うと、ベクトルxを行列Aで変換しても、ベクトルの長さが変わるだけで、その向きは変わらない場合には、xはAの固有ベクトルで、その長さが何倍になるかが、固有値となる、という訳です。
とほほ、本当に掻い摘んだ説明ですな…。

さて、単位行列をIとすると、|A-λI|=0を固有方程式と呼び、解析的に(数式的に)固有値を求めることは、この方程式解くことに他なりません。
ちなみに、ここでの|~|は絶対値表現ではなく、行列式を表しています。
上の2チャンネルの分散の行列で表すと、

2011_0328_04

ということになります。
Srg=Sgrですので、この行列式を展開すると、

2011_0328_05

になり、λについての2次方程式となります。
この方程式でλが求まれば、以下の式で固有ベクトルが求められます。

2011_0328_06

すなわち、

2011_0328_07

これを展開すると、

2011_0328_08

となり、このxとyについての連立方程式を解くことになります。

結果求められた固有ベクトルが、実は分布の散らばりの斜め具合を表しています。
また、その絶対値が最も大きい固有値に対応する固有ベクトルの向きから見れば、もっとも散らばり具合が大きいという非常にありがたい性質があります。

この性質を利用するために、固有ベクトルの単位ベクトルと、各ピクセルの色の値(各チャンネルの値の組み合わせ)とで内積値をとることになります。

例えば、あるピクセルの色の赤チャンネルと緑チャンネルの値を、

2011_0328_09

とすると、固有ベクトルとの内積値は、

2011_0328_10

となります。

この値で固有ベクトル(の単位ベクトル)を乗算したベクトルが、ピクセルの値を固有ベクトル方向に投影した際の位置を表しています。
つまり、この内積値自体は、固有ベクトルの向き(すなわち、いちばん散らばり具合が大きい向き)で見て、分布の中心からどれくらい離れているかを示す値だということになります。

内積値を並べて中央値を求めて、その中央値以上と未満とで分類すれば、もっとも効果的にグループ分けができる、という寸法です。

以前、各チャンネルのうちでもっとも差が大きいチャンネルで分割する、というやり方をしていましたが、アレに相当するものですね。

というわけで、早速実装してみました…、と言いたいところなのですが、このままつらつらと書き連ねるには、行を割く量としてさすがに無理がありました…。

時間切れ~ (・∀・ )っ/凵⌒☆チンチン

赤チャンネルとか緑チャンネルとか、限定する意味ほとんどなかったじゃん!数式ばっかで絵が全然なかったし!ブログでもお色気超スルー!
orz
ちくしょ~。

そんなこんなで、次回に続きます。

follow us in feedly
result = encodeURIComponent( "http://www.accessgames-blog.com/blog/2011/03/the-first-fligh.html" );document.write( "result = " , result );&media=https%3A%2F%2Ffarm8.staticflickr.com%2F7027%2F6851755809_df5b2051c9_z.jpg&description=Next%20stop%3A%20Pinterest">

| | コメント (0) | トラックバック (0)

« 心に残るもの | トップページ | 缶コーヒーと構造体 »

プログラマー」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック


この記事へのトラックバック一覧です: The First Flight of Vector Eigen:

« 心に残るもの | トップページ | 缶コーヒーと構造体 »