OTO - Ohshima Tamashima Observatory- - left_hand_method Diff

!左手法を使い連続領域を一周するアルゴリズム

天体観測の画像において、星像を検出し、その重心を自動的に決定するという場合を考える。
コンピュータにコンピュータで重心を計算させるには計算するには、まず星像の範囲を教える知る必要がある。

星像とは、ある閾値（例えば、スカイのスカイレベルの平均値＋３σ）を越えた値を持つピクセルの有限な連続領域のことであるが連続領域のことであると言ってよいと思うが、星像をゴミや宇宙線イベントと弁別する必要もある。ここでは、系外惑星や変光星の測光を扱うことに限定する。つまり主にデフォーカスした画像であるので画像を対象に考えると、ある星像とはある一定以上の面積を持っているかどうかで判断できるとする弁別できる。

その判断のためには、あるまずある閾値以上の値を持つピクセルがどの程度連続した領域であるかをコンピュータが知る必要がある。以下はそのためのアルゴリズムであるそのためのアルゴリズムを以下のように考えてみた。

!!XY座標系における右回りとは
閉じた有限の領域内で領域内から出発して（＝出発点として星像内部の最輝点を考えている）で、例えば左手法を採用して探索する場合、進行方向は直進して壁にぶつかると進行方向を「右回り」になるに変え、あとは左手法で星像の外周をたどっていくことになる。が、XY座標系で座標系において、進行方向に無関係に、「右回り」はどのように表現すればよいのであろうかを採るとはどのようにアルゴリズムを考えればよいのであろうか。

結論だけを先に書くと、

右回りとは、ベクトルの外積が負になるようにとる

ことである。その解説は、例えば[[ここ|http://www5d.biglobe.ne.jp/~noocyte/Programming/Geometry/RotationDirection.html]]に書いてある。

!!XY座標系において左手法で探索するアルゴリズム

天体画像上の星像を認識するためにピクセル探索する場合、ここでは左手法を使うことにする。

左手法は、迷路から脱出する場合の最も簡単な解法の一つで、出口を見付けるために、左手を壁につけたまま離さずに前進し続ける方法である。採るべきアルゴリズムは星像内部の1点から出発して、そのまま進むか壁に到達した後、それができない時は右へ曲がれ左手法を使って星像の外周をたどると、というだけの簡単な方法である全体として右回りになる。しかし、ここでXY座標系において「右へ曲がる」アルゴリズムをどう表現するかが問題になる。人間にとっては「右へ曲がる」とはどうすることかを判断するのは簡単なことであるが、コンピュータにXY座標系を使って定義を教えるのはひと仕事である。

もちろん、来た方向で４つの場合分けをして、それぞれについて、将来はどの方向へ進めば「右」になるかを一つずつ記述してもよいのであるが、それでは「右回り」の定義をコンピュータに教えたことにはならない。ここはスマートに「右へ曲がる」を数学的に一つの式で表したいところである。


今、過去の位置A点（x_a, y_a）から、現在の位置B点（x_b, y_b）に移動して来ており、次に進む位置をC点(x_c, y_c）とする。

点Aから点Bへ来た経路を、X方向の増分Δx_p、Y方向の増分Δy_pで表すとしよう。

つまり、Δx_p =（x_b - x_a)、　Δy_p = (y_b - y_a)である。

また、次に進むべき経路（点Bから点C）を、X方向の増分をΔx_f、Y方向の増分をΔy_fで表すとする。

同様に、Δx_f =（x_c - x_b)、　Δy_f = (y_c - y_b)である。

この記述法で、外積をとると、右回り（時計回り）の場合は、

Δx_f・Δy_p - Δx_p・Δy_f　＞０

という条件式で表される。


画像上でピクセルを探索する場合、プログラムのステップとしては、X方向かY方向のどちらかへ１ピクセルずつ移動していくことになる。その場合、Δx_pまたはΔy_pのどちらかは０になるので、上式の２つの項のどちらかが消え、１項だけの式になる。
また、増分は＋１、または−１なので、結局、

Δx_f　＝　Δy_p

Δy_f ＝　−１＊Δx_p

である。

!Rubyによる実装
以上のアルゴリズムを使い、星像を検出し、重心を求めるプログラムに実装してみた。

→[[Rubyによる星像範囲の探査]]
　
　
　
　
----
[[技術的な覚書き]]へ戻る

[[OTO-Ohshima Tamashima Observatory-]]トップへ戻る

{{counter}}