プロコン

こんばんは．一月ほど前に行われた高専プロコン，行ってきました．
ご存じの方も多いと思われますが，競技部門がシステム未完成のために行われませんでした．
詳細は以下をご覧下さい．

高専プロコンリポート：高専プロコンを襲った魔物の正体とは
http://www.itmedia.co.jp/enterprise/articles/0810/14/news021.html

2日目に試合中止の発表がなされた時は，はっきり言って拍子抜けしてしまいました．競技部門のみの参加でしたので，何もせずに行って帰ってきたようなものです．今月末から来月の頭にかけて，Web上で再試合をやるようですが，熱は冷めきっています．

来年のプロコンは木更津高専で行われます．来年参加しようか，躊躇している処です．現在，プロコン以外のコンテストに興味を持っているので，そちらにシフトしようかなとも考えています．

話がアルゴリズムよりになりますが，今回の競技は巡回セールスマン問題(TSP)を改変したようなものでした．TSPは組み合わせ最適化問題の代表的なものなので，最近ちょこちょこと調査しています．機会があれば，ちょこちょことTSPに関するアルゴリズムを紹介できればと考えています．

画像処理 第5回 線形フィルタ

こんばんは。とてつもない間がありましたが、気にしない方向で。
…今回は線形フィルタについてです。

画像処理の中で、領域に基づく濃淡変換を空間フィルタリングと呼んでいます。で、そこで用いられるフィルタを空間フィルタと呼んでいます。そして更に、空間フィルタは線形フィルタと、非線形フィルタに分けられます。今回紹介する線形フィルタは次式で表されます。



f(x, y)は入力、g(x, y)は出力、h(m, n)はフィルタの係数。
フィルタの大きさは(2w+1)*(2w+1)です。w=1、つまり3*3のフィルタは次のようになっているわけです。

Tab.1 線形フィルタ

h(-1, -1)	h(0, -1)	h(1, -1)
h(-1, 0)	h(0, 0)	h(1, 0)
h(-1, 1)	h(0, 1)	h(1, 1)

というわけで、いくつかのフィルタを紹介します。

・平均化フィルタ(averaging filter)
非常にシンプルなフィルタです。やることは平滑化、つまり、画像をぼかします。
フィルタは次の表です。

Tab.2 平均化フィルタ(3*3)

1/9	1/9	1/9
1/9	1/9	1/9
1/9	1/9	1/9

Tab.3 平均化フィルタ(5*5)

1/25	1/25	1/25	1/25	1/25
1/25	1/25	1/25	1/25	1/25
1/25	1/25	1/25	1/25	1/25
1/25	1/25	1/25	1/25	1/25
1/25	1/25	1/25	1/25	1/25

・加重平均化フィルタ(weighted averaging filter)
平均化フィルタではありますが、重みが付いています。
中央ほど重みが強いので、先の平均化フィルタに比べエッジが残りやすいという特徴があります。

Tab.4 加重平均化フィルタ(3*3)

1/16	2/16	1/16
2/16	4/16	2/16
1/16	2/16	1/16

Tab.5 加重平均化フィルタ(5*5)

1/256	4/256	6/256	4/256	1/256
4/256	16/256	24/256	16/256	4/256
6/256	24/256	36/256	24/256	6/256
4/256	16/256	24/256	16/256	4/256
1/256	4/256	6/256	4/256	1/256

・ガウシアンフィルタ(Gaussian filter)
ガウス分布に従った加重平均化フィルタ。
ガウス分布は以下の式です。



・微分フィルタ
離散値だけど微分。
⊿f(x)=f(x)-f(x-1)
みたいなノリです。いくつかパターンがあるので示しておきます。また、方向も横、縦とあります。
簡単にいえば、このフィルタではエッジ検出が出来ます。しかし、ノイズに敏感だったりします。

Tab.6 微分フィルタ(横方向1)

0	0	0
0	-1	1
0	0	0

Tab.7 微分フィルタ(横方向2)

0	0	0
-1	1	0
0	0	0

Tab.8 微分フィルタ(横方向3)

0	0	0
-1/2	0	1/2
0	0	0

Tab.9 微分フィルタ(縦方向1)

0	1	0
0	-1	0
0	0	0

Tab.10 微分フィルタ(縦方向2)

0	0	0
0	1	0
0	-1	0

Tab.11 微分フィルタ(縦方向3)

0	1/2	0
0	0	0
0	-1/2	0

・プリューイットフィルタ(Prewitt filter)
プリューイットフィルタは横(縦)方向に微分した後、縦(横)方向に平滑化します。つまり、先の微分フィルタに比べ、ノイズが低減されるということです。

Tab.12 プリューイットフィルタ(横方向)

-1	0	1
-1	0	1
-1	0	1

Tab.13 プリューイットフィルタ(縦方向)

1	1	1
0	0	0
-1	-1	-1

・ソーベルフィルタ(Sobel filter)
このフィルタは、大体プリューイットフィルタと同じですが、平滑化の際、中央に重みを付けています。

Tab.14 ソーベルフィルタ(横方向)

-1	0	1
-2	0	2
-1	0	1

Tab.15 ソーベルフィルタ(縦方向)

1	2	1
0	0	0
-1	-2	-1

・2次微分フィルタ
その名の通り、離散値だけど2次微分します。微分フィルタ1の出力から、微分フィルタ2の出力を引くと、丁度2次微分になります。

Tab.16 2次微分フィルタ(横方向)

0	0	0
1	-2	1
0	0	0

Tab.17 2次微分フィルタ(縦方向)

0	1	0
0	-2	0
0	1	0

・ラプラシアンフィルタ(Laplacian filter)
このフィルタは、縦横方向の2次微分の結果を足し合わせたものです。方向に依存しないエッジが得られます。

Tab.18 ラプラシアンフィルタ

0	1	0
1	-4	1
0	1	0

・鮮鋭化フィルタ(sharpening filter)
このフィルタは入力画像からラプラシアンフィルタの出力を引いたものです。このフィルタを掛けると、エッジが強調されます。(鮮鋭化フィルタ2は、入力画像からラプラシアンフィルタを変形したものを引いています。)

Tab.19 鮮鋭化フィルタ1

0	-1	0
-1	5	-1
0	-1	0

Tab.20 鮮鋭化フィルタ2

-1	-1	-1
-1	9	-1
-1	-1	-1

では、これらのフィルタをサンプル画像に施してみます…と思ったのですが、投稿が長くなってしまったので、実際の例は次回へと回そうと思います。

iAppli近況

今日は。どのような状況なのか、全くお伝えしていなかった、TheCUIについてです。
大体出来ています。が、ディティールの作りこみが甘いです。
ですので、テスト版を某所で公開し、様子を見て、最終的に一般公開できたらと思います。

また、他に考えている案があります。今だと時期尚早ですが、「クリスマスツリー」を作ろうかと。実は昨年にも年末にiAppliで作りました。が、不出来だったので、改めて作り直そうかと思っています。

あとは、結構前から流行っている「脳トレ」に便乗したものでも作ろうかな…と。

JDBC

こんばんは。とある事情で、MySQLをJavaで扱うことになったので、ちょっとしたメモ。
JavaからMySQLを弄るために、JDBCを利用します。
JDBCとは、Javaでデータベースに接続するためのAPIです。細かい説明はすっ飛ばして、使用方法を。

MySQLは公式サイト
MySQL AB（http://www.mysql.com/）
から、ダウンロードできます。無料です。
今回は MySQL Connector/J というJDBCドライバを使いました。公式ドライバのようです。
公式サイトからDownloads -> (下の方)MySQL Connector/J とたどれば落とせます。
バージョンは5.1にしました。

落したzipを解凍。中にあるmysql-connector-java-5.1.6-bin.jarをCLASSPATHの通っているディレクトリにコピーで完了。あるいはeclipseならプロジェクト毎に、「外部JARの追加」でmysql-connector-java-5.1.6-bin.jarを追加しても出来ます。

簡単に出来ました。

画像処理 第4回 トーンカーブ

今晩は。今回は画素ごとの濃淡変換についてです。
画素ごとですので、入出力を関数で与える事が出来ます。この関数は階調変換関数と呼ばれています。そして、この関数をグラフで表したものがトーンカーブです。

入力ピクセルをx、出力ピクセルをy、階調変換関数をfとすると、次のような式になるわけです。

y = f(x)

一番簡単なのが、自分自身の写像です。
f(x)=x
グラフはFig.1に示した通りです。

Fig.1:そのまま

以降いくつか代表的なものを示します。

・折れ線型トーンカーブ
直線のみで構成される単純なトーンカーブです(Fig.2)。コントラスト調整に使われたりします。

Fig.2:折れ線型トーンカーブ

・ガンマ変換(gamma transform)
ガンマ変換は次式で表されます。
y=255*(x/255)^(1/γ)
γを変えていったときのトーンカーブをFig.3に示します。
(上からγ=3.0, 2.0, 1.5, 1.0, 0.66, 0.5, 0.33)
コントラストを調整することもできます。

Fig.3:ガンマ変換

・ネガ・ポジ反転
トーンカーブはFig.4で、入力画像と、出力画像とは濃淡が反転しています。

Fig.4:ネガポジ反転

・ソラリゼーション(solarization)
トーンカーブはFig.5。元々は写真制作時の暗室テクニックだったそうです。

Fig.5:ソラリゼーション

・擬似カラー(pseudo color)
擬似カラーはグレースケールの画像に対して施します。
RGBそれぞれでトーンカーブが異なります(Fig.6)。

Fig.6:擬似カラー

実際に画像に対しトーンカーブを適用してみます。

・ガンマ変換

サンプルは左の画像です。北海道のテレビ塔を携帯電話のカメラで撮ったものです。逆光気味で見難いです。
この画像に対しガンマ変換(γ=2.0)をかけたものが右の画像です。暗い部分のコントラストが上がって見やすくなっています。


・ソラリゼーション

サンプル画像は札幌時計台…では無く、その付近の道をカメラを揺らしながら撮影したものです。
ソラリゼーションをかけると右の画像になります。

どうなってるのか良く分からないかもです。

(ちなみに上2つの写真は、北海道旅行の際に撮ったものです。)

・擬似カラー
サンプル画像は、懲りずに「耳」です。グレースケール化しています(2値画像化はしていません)。


濃淡の若干の変化でも、色の差がよく分かります。サーモグラフィーを思い出します。

次は線形フィルタを扱えれば、と思います。

画像処理 第3回 ちょっとカラーモデル

何と無くHSV変換について調べていたので、カラーモデルに関して少しばかり。

・RGB
RGB(RGBカラーモデル)は、Red、Green、Blueの3つを混ぜて色を表現する加法混色の一つです。
数値が増えるにつれて、白に近づきます。
テレビは、正にRGBカラーモデルを採用しています。モニターに近づいてドットを見ると、白のドットがRGBのドット3つで構成されているのが見えたりします。離れて見えると白に見えます、不思議。

・CMY
CMYはCyan、Magenta、Yellowの3つによる、減法混色です。
例は絵の具。数値が増えるにつれて、黒に近づきます。

この辺はよく知られていると思われます。

・HSV
HSVは色相Hue、彩度Saturation、明度Value
から構成されます。HSB(Hue、Saturation、Brightness)とも呼びます。

V=1の時の例を下に示します。



中心に向かうにつれ、白に近づいていきます。
変換式はこんな感じ。


h=floor(H/(PI/3))

P=I*(1-S)
Q=I*(1-S(H-h))
T=I*(1-S*(1-H+h))

if h=0 R=I, G=T, B=P
if h=1 R=Q, G=I, B=P
if h=2 R=P, G=I, B=T
if h=3 R=P, G=Q, B=I
if h=4 R=T, G=P, B=I
if h=5 R=I, G=P, B=Q

0<=R, G, B, S, I<=1, 0<=H<=2*PI


この式だと、若干不連続な領域があります。
ちなみにJavaのColorクラスにもHSVからRGBに変換してくれるメソッドがあります。
このメソッドでは、上に示したものより不連続な点が改善されているようです。

・HLS
HLSは色相Hue、輝度Lightness/Luminance、彩度Saturation
から構成されます。 HSI(Hue、Saturation、Intensity)、HSLとも呼びます。
HSVに似ています…がちょっと違います。

L=0.5の時の例を下に示します。



中心に向かうにつれて、灰色に近づいていきます。
変換式はこんな感じ。

R=X (h=H+2/3*PI)
G=X (h=H)
B=X (h=H-2/3*PI)

X(h)は下の定義
h'=h
h'=h+2*PI (h<0)
h'=h-2*PI (h>2*PI)
M2=I*(1+S) (I<=0.5)
M2=I+S-I*S (I>0.5)
M1=2*I-M2
X=M1+(M2-M1)*h'/(1/3*PI)
(h' < 1/3*PI)
X=M2
(1/3*PI <= h' < PI)
X=M1+(M2-M1)*(4/3*PI-h')/(1/3*PI)
(PI <= h' < 4/3*PI)
X=M1
(4/3*PI <= h' < 2*PI)

0<=R, G, B, S, I<=1, 0<=H<=2*PI

この変換式は、綺麗にできます。

再現性はかなり低いですが、下のようなものもあります。

I=1/5の例。



変換式は…

R=I/3+2*S*cosH
G=I/3-S*cosH+S*sinH
B=I/3-S*cosH-S*sinH

0<=R, G, B<=1, 0<=I<=3, 0<=H<=2*PI, 0<=S<=2/3

あまりまとまりが無いですが、こんな処で。

画像処理 第1回 補間

こんばんは。
ネタが溜まってきました。

さて最近凝っているネタがデジタル画像処理です。画像なので、処理結果が眼で確認できて、非常に分かりやすいです。今回は、「補間」についてです。

「補間」は画像の再標本化の時に使われます。よくある例が拡大です。デジタル画像では座標が離散値ですが、拡大する際には、小数値のピクセルが欲しくなります。で、小数値のピクセルを計算でなんとか求めようというわけです。

主に3つの方法があります。

・ニアレストネイバー(nearest neighbor)
もっとも単純な補間法です。
座標(x,y)のピクセル値I(x,y)は次の式で与えられます(fは元画像のピクセル)。

I(x,y) = f([x+0.5],[y+0.5])

・バイリニア補間(bilinear interpolation)
こちらは次のような式であらわされます(括弧は行列を表しています)。対象のドットに近い周囲4ドットを用いています。
ニアレストネイバーをしてから、平均化したような感じです。

I(x, y) =	(	[x]+1-x	x-[x]	)	(	f([x], [y])	f([x], [y]+1)	)	(	[y]+1-y	)
						f([x]+1, [y])	f([x]+1, [y]+1)			y-[y]

・バイキュービック補間(bicubic interpolation)
3つの中で最も効果の大きい補間方法です。
式は次の通り。対象のドットに近い周囲16ドットを用いています。

I(x, y) =

(

h(x1)

h(x2)

h(x3)

h(x4)

)

(

f11

f12

f13

f14

)

(

h(y1)

)

f21

f22

f23

f24

h(y2)

f31

f32

f33

f34

h(y3)

f41

f42

f43

f44

h(y4)

関数h(t)は、sinc関数(sinc(t)=sin(πt)/(πt))を3次多項式で近似したもので次式で表されます。

h(t) =	{	|t|^3-2|t|^2+1	(|t|<=1)
		-|t|^3+5|t|^2-8|t|+4	(1<|t|<=2)
		0	(2<|t|)

では、これらの補間を実際に施した画像を見てみましょう。
画像はFig.1にしめしたもので、「あ」の文字です。サイズ24のHGS行書体です。
この画像をそれぞれ20倍に拡大したものを以下に示します。

Fig.1:元画像


Fig.2:ニアレストネイバー


Fig.3:バイリニア補間


Fig.4バイキュービック補間

Fig.2は非常にジャギが目立ちます。
Fig.3は平滑化の効果から、ジャギは目立たなくなりますが、エッジが鈍っています。
Fig.4は全体的にFig.3よりスマートに見えます。先端部分も上手く再現されていて、自然な画像となっています。

では今回はこの辺で。次回は、線形フィルタ全般を扱えればと思います。

ボゴソート

今晩は。

面白いアルゴリズムをちまちま紹介しようかなということで、まずはソートについて。

ソートは非常に重要なアルゴリズムなので、かつてから研究されていて、非常に多くのものがあります。

大抵の実用的なアルゴリズムの計算時間は、

平均計算時間:O(n*log(n))
最悪計算時間:O(n^2)

のような感じですが、こんなアルゴリズムもあります。

ボゴソート
平均計算時間:O(n*n!)
最悪計算時間:∞

そして、安定性なしという素晴らしきソートアルゴリズムです。

トランプを順に並べる場合を例にすると、次のようになる。

1.トランプ52枚の束を放り投げて、ばらばらにする。
2.1枚ずつ無作為にすべてを拾い集める。
3.ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。

カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えても良い。

「ボゴソート」『フリー百科事典　ウィキペディア日本語版』（http://ja.wikipedia.org/）。2008年7月12日21時01分（日本時間）現在での最新版を取得。

という訳で、紹介するだけなのもなんなので、計測してみました。

ボゴソート計測結果

要素数[個]	試行回数[回]	平均時間(指数)[sec]	平均時間(小数)[sec]
2	20,000,000	1.55E-6	0.00000155
3	20,000,000	2.20E-6	0.00000220
4	20,000,000	5.53E-6	0.00000553
5	10,000,000	2.45E-5	0.0000245
6	1,000,000	1.28E-4	0.000128
7	100,000	9.38E-4	0.000938
8	20,000	7.17E-3	0.00717
9	1,000	7.02E-2	0.0702
10	100	6.53E-1	0.653
11	100	7.11E+0	7.11

CPU:Intel(R) Pentium(R)4 CPU 3.20 GHz
平均時間は3桁目で四捨五入しています。

要素数につれて、驚く程ソート時間が増えているのが明白に分かります。
上でO(n*n!)だと書きましたが、あまりそれに沿ってないような気がします。クヌースのシャッフル出ないこと原因かもしれないし、ランダム性が高いので、試行回数が足りない所為かも知れません。

他にも特殊なソートがあるので、ちょこまかと紹介していこうと思います。