2009年6月29日月曜日

画像処理 #18 ハーフトーニング

2値画像ネタです.

先日の2値化では,ある閾値を設け,それより画素値が高いか否かで白黒判断していました.
しかし,それだと満足しない方もおられるはず.

というわけで,ハーフトーニング.渇いた喉を潤してくれます.
簡単に言うと,白黒の2値だけで,濃淡の微妙な変化を表現しようというものです.
スクリーントーンとかは正にそれです.

・濃度パターン法(density pattern method)
1つのグレースケール画素を複数の2値画像で表現します.
例えば,1画素を4x4画素の2値画像で表現するとすると,256階調を17分割することができます.


Fig.1

こんな感じ.
1画素を4x4画素で表現するので,入力画像がWxH画素の場合,出力画像4Wx4H画素となります.

・ディザ法(dither method)
ディザパターンというものを使う方法です.


Fig.2 Dither pattern

1. 入力画像を4x4のブロックに分割する.
2. ブロック内の各画素がディザパターンの対応画素*16+8以上なら,出力画素を255,そうでないなら,0とする.
3. 全てのブロックについて,2を行う.

ディザ法では周期的パターンが目立つので(実例を後述します),ディザパターンをFig.2に固定せず,可変にする方法も考案されているようです.

・誤差拡散法(error diffusion method)
これは,2値化を行うことによる誤差をキャンセルさせて行くというものです.
処理の流れは,以下の通り.

f:入力画素
g:出力画素

1. fからgを以下の様に決定し,誤差をe=g-fとする.
f>127 → g=255
f≦128 → g=0
2. 誤差eを入力画素周辺の数画素に分散させる.
分散式の例:
f=f(x, y)だったとき
f'(x+1, y)=f(x+1, y)+(5/16)e
f'(x+1, y)=f(x-1, y+1)+(3/16)e
f'(x+1, y)=f(x, y+1)+(5/16)e
f'(x+1, y)=f(x+1, y+1)+(3/16)e
3. 1,2の処理を,全画素について行う(左上から右下に向かって).

下が今回の例.


Fig.3 sample


Fig.4 density pattern method
出力画像がでかいので一部のみ.


Fig.5 dither method


Fig.6 error diffusion method

誤差拡散法が一番周期的パターンが目立ちにくいです.

これでまた一つ,人生の楽しみが増えました.

2009年6月26日金曜日

数学 #2 数値解析 #1 オイラー法

微分方程式が趣味の方は居るでしょうか.
日々閉じた解を追い求める,これ以上のロマンはありません.

しかし,行き詰ってしまうことも少なくないはず.そこはそれ,人生は旅です.気楽に行きましょう.

そんなわけでオイラー法です.

例えば,
y'=x2+y2
この微分方程式は,解を初等関数で表すことはできないようです.

ではどうするか.数値解を求めれば良いのです.

まず,初期値x0,y0,刻み幅hを決めます.

さて,
x1=x0+h
y1=y(x1)
としましょう.y(x1)はy()が分からないので求められませんが,テイラー展開することが出来ます.

y1=y(x0+h)
=y0+hy'0+(h2/2!)y''n

始めの2項にのみ注目しましょう.(hが十分に小さいとすれば,それ以降を無視しても誤差は小さいです)
つまり,
x1=x0+h
y1=y0+hy'0
と書くことが出来ます.

ちなみに,ここで,y'0
y'0=y'(x0, y0)
ですのでご注意を.

最終的に,これを再帰的に記述すれば,
xn+1=xn+h
yn+1=yn+hf(xn, yn)
(但し,f(x, y)=y'(x, y))

となります.
これらから,初期値を決めてしまえば,数値的振る舞いが分かるのです.

下に例を示しましょう.


Fig.1
先の微分方程式について,それぞれの座標での傾きを表したものです(-2≦x≦2, -2≦y≦2).これで,解の外形をイメージすることが出来ます.


Fig.2 x0=-1.6, y0=-1.8, h=1/4, 1/16
初期値を設定して"解いて"みました(-2≦x≦2, -2≦y≦2).
hが小さいほど,誤差は小さくなります(hが1/2になると,誤差も1/2になる).

ちなみにこれ,精度はそれ程良くないです.
もっと精度を良くしたいというのであらば,テーラー級数の項を増やすか,あの方法を使いましょう…と,次回へ引き延ばしてみたり.

2009年6月24日水曜日

数学 #1 ゼータ関数

先日,電車に乗っていたら,学生2人が乗り込んできました.
会話を盗み聞きしていたのですが,大体こんな内容だったと思います.

A「おまえ,ζ関数知ってるか」
B「何それ」
A「おっまえ,ζ関数知しらねぇのか.ζ(s)=∑1/nsでよぉ,ζ(2)=π2/6になんだぜ」
B「πでてくんのかよ,まじパネェな」
A「そんでよ,ζ(-1)発散すると思うだろぉ.解析接続とかするとζ(-1)=-1/12になるんだぜ」
B「ζ関数まじパネェな」
A「ζ(-2)なんか0になっちまうんだぜ,まじパネェよ」


さて,そんなわけでζ(:ゼータ)関数ですが,下の様な定義です.
ζ(s)=∑1≦n1/ns
この級数の和は,s>1に対してのみ収束しますが,A君の言う通り,解析接続によって複素数平面全体(一部除く)にまで定義域を拡張できます.例えば,
ζ(-1)=1+2+3+4+5+…
となり,明らかにこの級数は発散しますが,解析接続をすると,
ζ(-1)=-1/12
となるようです.

しかし,級数を強引に弄ると,
ζ(-1)=1+2+3+4+5+…=-1/12
を示すことも出来ます.

ζ(-1):
s=ζ(-1)=1+2+3+4+5+…
-3s=s-4s=1-2+3-4+5-…
-6s=-3s-3s=1-1+1-1+1-…
-12s=-6s-6s=1+0+0+0+0+…=1
∴ζ(-1)=-1/12

ζ(-2):
s=ζ(-2)=1+22+32+42+52+…
-7s=s-2*22*s=1-22+32-42+52-…
-14s=-7s-7s=1-3+5-7+9-…
-28s=-14s-14s=1-2+2-2+2-…
-56s=-28s-28s=1-1+0+0+0+…=0
∴ζ(-2)=0

ζ(-3):
s=ζ(-3)=1+23+33+43+53+…
-15s=s-2*23*s=1-23+33-43+53-…
-30s=-15s-15s=1-7+19-37+61-…
-60s=-30s-30s=1-6+12-18+24-…
-120s=-60s-60s=1-5+6-6+6-…
-240s=-120s-120s=1-4+1-0+0+…=-2
∴ζ(-3)=1/120

非常にオドロキです.かなり強引とはいえ,一応の形で示すことが出来ています.

ちなみにζ関数に関連したリーマン予想は,ミレニアム懸賞問題であり,解決することが出来れば賞金1億円がもらえます.暇な人はどうぞ.

2009年6月22日月曜日

カオス理論 #22 1/fゆらぎ

「1/fゆらぎ」
簡単に言うと,振幅スペクトルがf(周波数)に反比例するゆらぎのことです.

これは,様々な現象(物理,生物)に現れます.
例えば,木目の模様は1/fゆらぎです.脈の間隔も1/fゆらぎだったりするので,人間が快適と感じるらしい…です.

無秩序と秩序の間(カオス)といった所とも言えるようです.
ちなみに,同じ周波数成分を持つ光はピンク色なので,ピンクノイズ(pink noise)とも言います.

文章だと意味不明なので,実際に作ってみた例.

F(t)
=∑k∈(-∞, ∞) ckejωkt
=∑k∈(-∞, ∞) |ck|ej(ωkt+φk)
=∑k∈[0, ∞) 2|ck|cos(ωkt+φk)
ck=|ck|ek
|ck|=0(k=0)
=1/k(o.w.)
φk∈[0, 2π)

位相φkは,[0, 2π)の範囲で乱数により与えています.
振幅スペクトルは,|ck|.
位相スペクトルは,φkとなります.

では,F(t)はどんな波形になるかというと…


Fig.1 pink noise(graph)


Fig.2 pink noise(line)
Fig.2は閾値を設けてそれ未満なら黒,それ以上なら白としています.

ちなみに,振幅スペクトルが1だったとすると,F(t)はホワイトノイズとなります.

Fig.3 white noise(graph)


Fig.4 white noise(line)

ホワイトノイズの方は乱雑としています.ちなみに,1/f2の場合は,1/fに比べ,より無秩序さが失われます.

2009年6月17日水曜日

専門書を読む #8

集合・位相入門
p39

p40~の問題が非常に多いです.

2009年6月15日月曜日

画像処理 #17 LOGフィルタ

またまた画像処理ネタ.

LOGフィルタ(Laplacian Of Gaussian Filter)

LOGフィルタというものがあります.
エッジの検出には,ラプラシアンフィルタを使ったりします.ラプラシアンフィルタは,2次微分と同様の働きをするため,値が+から-に変化する所(ゼロ交差=zero crossing)がエッジに相当します.しかし,2次微分であるためノイズが強調されます.だので,ガウシアンフィルタをかけ平滑化した後,ラプラシアンフィルタをしましょうというのがLOGフィルタです.

下がフィルタの式です.



ちなみにグラフはこんな感じ.


Fig.1 LOGフィルタのグラフ(σ=2)

下に例を…


Fig.2 元画像


Fig.3 LOGフィルタ(σ=1)


Fig.4 LOGフィルタ(σ=2)


Fig.5 LOGフィルタ(σ=4)


Fig.6 LOGフィルタ(σ=8)

左の画像は,フィルタ適用後の値が0の時,中間の色(=(128,128,128)T)となるようにしています.
右の画像は,ゼロ交差を白色にしたものです.

面白い感じにエッジが検出出来ています.
σを大きくすることで,エッジ検出が鈍くなっていきます.

いやぁ,フィルタって本当にいいもんですね~.

2009年6月14日日曜日

専門書を読む #7

集合・位相入門
p37

中々残念な状態です.

2009年6月8日月曜日

専門書を読む #6

今月中にどこまで進むでしょうか.

集合・位相入門
p34

只今写像合成中….

2009年6月3日水曜日

【自己紹介バトン】

バトン.

ブログ、mixiなどにおいて、特定のテーマに沿った質問群に回答し、友人・知人や別のユーザーに同様の質問群を回すことを繰り返す行為。インターネットにおけるバトン参照。(by Wikipedia)

ということで,みずち。氏からのこのバトン.全力で受け止めたいと思います.

【自己紹介バトン】
3日以内に書く 嘘偽りなく /*アンカー禁止*/
/*回した人はちゃんとその人がやったか見に行く
※書いてない人にデスゲーム!(CV:ハナゴエ)*/

■回す人5人
μ(φ(5))=0なので,回す人は0人.

■あなたの名前
 きっと皆さんご存じの通り,とど,あるいはトド,若しくはtodo.本名は非公開.

■呼ばれ方
 とどさん|とどくん|苗字くん

■あなたの年齢
 青二才.

■好きなもの(5つ)
 ・漫画
 ・音楽
 ・絵画
 ・書籍
 ・妄想

■今現在の恋人は?
 全人類.

■好きなタイプ
 マイ・ワールドを展開できる方.

■嫌いなタイプ
 極端にウェットで無ければ良いと思います.

■好きな映画
 絶妙な雰囲気を醸し出し,見終わった後の余韻が大きい映画.映画はディティール.

■好きな音楽
 民族音楽(生理的快感が大きい)や,緻密な計算が為された音楽,70~80年代の邦楽.

■好きな食べ物
 カレー,ラーメン,唐揚げ等.

■送り主を色にしたら?
 本当の所は,御本人の写真を撮り,平均の色を計算するという,クールな方法を取りたかったのですが,現時点では写真を持ち合わせていないので,発見的に割り出してみます.
 これには,RGB値を調整する,あるいはHSVで調整するか等,色々方法がありますが,RGB値の方が一般的な気がする,そんなご時世ですので,RGBにしてみましょう.
(R G B)T = (64 128 144)T
…こんなもんですかな.

■回す人を色にしたら?
■3日以内に実行しなかった人の罰ゲーム
μ(φ(5))=0なの(以下,青二才の都合で省略させて頂きます.

さて,このような所でしょうか.

2009年6月1日月曜日

画像処理 #16 2値化

画像処理ネタカムバック.

皆さんは日常で,グレースケール画像を2値画像にしたい,そんな事がよくあると思います.ちなみに,2値画像とは,グレースケール画像の様に灰色のような中間色を含まず,白黒はっきりつけた画像のことです.2値画像に変換することを2値化といいます.

さて,どのように変換すればよいでしょう.
1. ペイント->名前を付けて保存->モノクロビットマップ
2. 1ピクセルずつ愛をこめて判定していく.
3. とある分析方法を使う.

今回は,3.の方法を使ってみましょう.

判別分析法(discriminant analysis method)
"分離度"を用いて,白黒の境であるしきい値tを決める方法です.
分離度とはクラス間分散とクラス内分散の比で定義されるものです.これが一番大きい時のtをしきい値とするわけです.
式の計算がゴニョゴニョしててわずらわしいので,結論まで飛躍してしまいましょう.

結論:
クラス間分散σb2が最大になるようにtを定めれば良い.
σb2は以下の式で定義されます.



ここで,
ω1 : 黒画素クラスの画素数
ω2 : 白画素クラスの画素数
m1 : 黒画素クラスの画素値の平均
m2 : 白画素クラスの画素値の平均

黒画素クラス : しきい値tより,画素値が低い画素の集合
白画素クラス : しきい値tより,画素値が高い画素の集合

では,さっくりと実例を…


Fig.1 元画像1


Fig.2 変換画像1(しきい値t=132)


Fig.3 元画像2


Fig.4 変換画像2(しきい値t=174)

こんな感じ.ちゃんと2値化できているんではないでしょうか.