OTO-Ohshima Tamashima Observatory-  Index  Search  Changes  Login

左手法のアルゴリズム

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

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

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

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

XY座標系における右回りとは

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

結論だけを先に書くと、

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

ことである。その解説は、例えばここに書いてある。

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

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

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

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

今、過去の位置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 >0

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

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

Δx_f = Δy_p

Δy_f = −1*Δx_p

である。

Rubyによる実装

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

Rubyによる星像範囲の探査        


技術的な覚書きへ戻る

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

943
Last modified:2009/04/03 14:41:17
Keyword(s):
References:[Rubyによる星像範囲の探査] [技術的な覚書き]