兩種快速星像匹配算法的比較

任俊杰,彭青玉,3

(1.暨南大學計算機科學系，廣州 510632；2.廣東省高等學校光學信息與傳感技術重點實驗室，廣州 510632;3.中國科學院光學天文聯合開放實驗室昆明基地，昆明 650011)

在現代天文觀測中，大多使用CCD探測器來成像觀測。為了快速提取每一幅CCD圖像中觀測對象的物理信息(如位置、光度等)，人們開發了多種自動處理軟件。例如DAOPHOT[1]，DoPHOT[2]，SExtractor[3]等。為了方便資料的歸算和處理，常常需要將圖像中星像的位置和光度等信息和已知星表中的相應位置和光度的對象作匹配。當圖像中星的數量較少時，這種匹配是容易實現的。然而，對于大視場或密集星場的多目標的快速匹配卻并非易事。

另外，由于拍攝星圖像時所用的濾光片不同或曝光時間和分辨率不同導致同一天區所拍攝的星圖也不一樣，即所拍攝的圖像中的星和星表中的星不完全一樣。如果所拍攝的圖像中有而星表中沒有的星，我們把它記為額外的星，相反，如果所拍攝的圖像中沒有而星表中卻有的星，我們把它記為丟失的星。匹配過程中除了必須處理那些額外的星和丟失的星，還必須處理平移、旋轉和由溫度引起的微小焦距尺度的變化。

目前，已經提出了多種星像配準算法。Groth首次提出了基于三角形的匹配算法[4]。他通過限制三角形中最長邊與最短邊的比率在一個用戶定義的范圍內來減少所構造的三角形的個數，從而減少匹配的時間。此算法在匹配階段的時間復雜度是O(n4.5)，這里的n是列表中星的個數。Murtagh提出了一種基于坐標對集合特征的方法[5]。這種算法的匹配是基于兩個列表中與坐標對相關的特征向量。Murtagh的算法在匹配階段的時間復雜度是O(n2)。Valdes等人提出了一種自動的星表匹配算法[6]。通過提取含有量度坐標和星等的兩個或多個星表，然后再匹配它們。其算法是取出星表中較亮的對象，然后找出一個星表到參考星表之間的坐標變換，這樣星表中所有的對象都可基于變換后的參考坐標進行匹配。Pal和Bakos描述了另一種基于三角形的方法[7]。此方法通過裁剪使得其在大視場中也非常高效，盡管大視場中有大量的點源或者較大的非線性扭曲。其程序是基于新定義的三角形空間中的對稱點進行匹配的。2007年Tabur提出了兩種快速的星圖匹配算法[8]：基于三角形空間的方法和基于向量的方法。作者的研究還表明后者要快于前者。最近，Zhang等人又提出了基于徑向和環向特征的星圖匹配算法[9]。Tabur的方法主要是針對星圖中的星比較密集的情況，而Zhang等人的方法主要是用于天文導航。針對這兩種不同的星圖匹配算法，我們進行比較分析。

文章的內容是這樣安排的：第1節介紹了基于向量的方法；第2節描述了基于徑向和環向特征的方法；第3節給出了兩種方法實驗結果的對比分析；最后一部分是結論。

1 基于向量的方法

按照Tabur的思想，基于向量的方法主要是通過嚴格的形狀定義來構造形狀特征集。期望通過匹配每個特征集來減少可能發生的誤配，盡快找到正確的匹配點。一旦有一個特征集匹配成功就可以停止匹配，避免了匹配整個列表和不必要的計算。

1.1 構造點對

對于所拍攝的圖像，首先用定心算法測量每顆星的位置及星等。因為亮星能夠提供更加準確的信息，所以把測得的所有星按星的亮度降序排列，選擇前n顆亮星構成一列表，記為I。它表示這些星來自圖像。而已有的星表能夠提供關于星的準確信息，所以從某一星表中提取亮度高于一定星等的星的基本信息(赤經、赤緯和星等)構成另一列表，記為R。它表示源于參考星表。我們期望從列表R中所選的n顆亮星都能在列表R中找到與自己所對應的星。然而，實際情況并非如此。因為額外的星和丟失的星造成兩個列表只有一部分重疊。增大列表R可以增大匹配概率，代價就是更長的點對列表構造時間。和以前的方法不同的是，增加列表的大小并不顯著增加點對匹配的時間。

常用的定心算法有Gauss擬合法、中值法、矩方法(包括修正矩方法)和尋導法等[10]。在實驗中采用Gauss擬合法來獲取星像的中心，用星表UCAC2[11]來獲取星像的信息。據李展等人的研究，在上述經典定心算法中，與修正距方法和中值法相比，Gauss擬合法是精度最高的一種定心算法[12]。而UCAC2是一部星像密度和位置、自行精度相對較高的星表。

具體地說，為了減少可能發生的誤配，仍然需要嚴格的形狀定義來保證在幾乎常數的時間里產生一個成功的匹配。首先從星像列表I中取出用戶定義的m顆亮星來構造我們所定義的形狀，構造過程通過把m顆亮星中的第一顆亮星A作為坐標的中心，而其它的星B、C、D，…按照相對于A點的坐標構造而成，并計算它們的角距離和位置角。在匹配過程中可能需要構造多個由m顆星定義的形狀特征集來進行匹配，一旦匹配成功就停止構造。定義計算位置角的參考方向朝北，順時針旋轉為角度增加的方向，如圖1。角距離：dad=dAD/F.

(1)

其中dAD是所拍攝圖像中的兩顆星A與D之間的距離，以像素為單位；F為焦距；dad是星表中與A和D對應的兩顆星之間的距離，以弧度為單位。這里假定在列表R中的位置信息已經從天球投影到了成像的圖像平面。

圖1 使用用戶定義的m顆星來構造預先定義的形狀

從列表R中取出前n顆亮星構造點對列表，則n顆星總共可構造的點對數為：

P=n(n-1)/2

(2)

構造點對列表的目的是提供星表中點對的相關信息，以供圖像中的點對進行搜索匹配。為了加快搜索速度，先按照角距離對所構造的點對列表進行排序，位置角也同樣會被排序，因為它和角距離是一一對應的。這種方法只需要構造一個點對列表，而且所構造的點對數目遠遠小于傳統的三角形方法所構造的三角形數目[8]。

1.2 匹配點對

這個匹配的過程就是從所構造的點對列表中找出與AB、AC、AD… 所對應的點對，而它們每一對是否匹配要靠角距離和位置角來確定。對于第一個m顆星所構造的形狀特征集，首先從點對列表中找出與AB匹配的點對，用二分查找來快速定位匹配點對，如果查找到的點對與AB的角距離之差在所給的誤差范圍內，將首先定義圖像與星表之間的旋轉角為AB與其匹配點對的位置角之差，每個形狀特征集只定義一次。因為圖像和星表中位置角的不同是由于探測器的旋轉造成的，所以后面的AC、AD…與其匹配點對之間的旋轉角也應該和AB的一樣，如果偏差大于1°就會被認為是不匹配的。如果找不到一個點對的角距離與AB的角距離之差在預先給定的誤差范圍內，AB將會被拒絕，轉而進入下一個點對AC的查找。

一旦m個候選點被識別，這m個點就會被用來求解底片常數(這里采用6常數模型)。如果底片常數正確，則匹配成功。否則說明這m個點中存在某些誤配點，這時將用一個函數來循環找出正確匹配的點，剔除錯誤匹配的點。如果m個候選點中正確匹配的點數小于3，則調用此函數會失敗。因為至少需要3個點才能確定圖像和星表之間的對應關系，用下一個m顆星所構造的形狀特征集來繼續這個過程。這個過程將重復進行直到有足夠多的星被識別為止，否則就是匹配失敗。

2 基于徑向和環向特征的方法

按照Zhang等人的研究[9]，基于徑向和環向特征的匹配算法是將鄰域伴星的幾何分布特征分解成徑向特征和環向特征來構成特征模式，并建立相應的特征模式庫。徑向特征具有構造簡單和旋轉不變性，是一種比較可靠的特征，所以用徑向特征作初始匹配，用環向特征作后續匹配。

2.1 構造徑向特征

徑向特征的構造方式如下：

(1)如圖2(a)所示，以星S為主星，在半徑為Rr鄰域內的星均稱為S的伴星(共有NS顆)。沿徑向方向量化(設量化等級為Nq)，即將以S為中心以Rr為半徑的鄰域劃分成間隔相等的環帶G1,G2,…,GNq。

(a) 徑向特征，其中 (b) 環向特征

Rr為特征模式半徑，Nq為量化等級Rc為特征模式半徑

NS為Rr半徑鄰域內星的個數

圖2 徑向特征和環向特征示意圖

Fig.2 Illustration of the definitions of quantitative characteristics varying along radii and circumferential directions(in (a)and(b)),respectively

2.2 構造環向特征

(1)如圖2(b)所示，以S為主星確定環向模式半徑Rc，依次計算伴星之間的夾角，如圖2(b)中的∠T1ST2,∠T2ST3,∠T3ST1(其T1,T2,T3為S的伴星)。

(2)找出最小夾角(如圖中的∠T1ST2)，并用它的一邊(ST1)作為起始邊對圓形鄰域作環向劃分，將圓周等分成8個扇區。由所有伴星在各象限上逆時針方向的分布組成一個8bit的向量v。如圖2(b)所示v=(11000100)。

(3)將v作循環移位，找出v所組成的數(十進制)的最大值，將這個最大值作為S的環向特征。如圖2(b)所示v循環移位后環向特征向量patc(S)=(11000100)=196。

2.3 構建導航數據庫

導航數據庫包含兩部分：參考星表和導航星模式庫。參考星表包含從基本星表中提取的亮度高于一定星等的星的基本信息(赤經、赤緯和星等)。導航星模式庫由特征構造過程所生成的特征模式向量構成。這里先用徑向模式特征作初始匹配，因此必須先構建徑向模式向量的導航星模式庫。直接存放徑向特征模式向量會造成匹配搜索速度慢，所以這里采用查找表的形式構建徑向特征模式庫。經過初始匹配后，可得到一個候選匹配星的集合，再構造環向特征作后續匹配。

2.4 匹配特征向量

基本思想是先利用初始匹配(粗匹配)將搜索范圍限定到一個較小的量級，然后用其他的特征逐層篩選，直到獲得最終的正確匹配。

2.4.1 初始匹配

2.4.2 后續匹配

理論上，如果存在兩顆以上的觀測星對應的候選匹配星唯一，則可進入驗證識別階段。如果C中存在大量的冗余匹配，將用環向特征對其作進一步的篩選。如果觀測星圖的環向特征和導航星模式庫中的相同，則保留該候選匹配星，否則剔除。

2.4.3 FOV約束

如果經過前面的篩選后候選匹配星仍不唯一，將采用FOV約束對其作進一步篩選。FOV約束基于這樣一個假設：當前觀測星圖中所有星的正確匹配包含在C中，而且它們還應該集中在某個FOV的限制區域內，而那些不正確的匹配(錯誤匹配和冗余匹配)則隨機分散在全天球范圍內。基于這一假設，對C進行掃描，如果某候選匹配星一定鄰域半徑r內星的個數少于某一個閾值T，則將其從C中剔除。

3 實驗結果對比分析

為了對兩種方法進行比較，利用云南天文臺1m望遠鏡所拍攝的多幅圖像進行了匹配，并對匹配過程進行了粗略的時間測定。具體地，使用了星團NGC2168和NGC1664的觀測圖像，詳細信息見表1。圖3給出了星團NGC2168觀測時一幀典型的CCD圖像，畫圈的表示已匹配的(在UCAC2中)星。表2給出了第1種方法對于NGC2168中不同大小列表所花費時間的統計。它包括列表中星的顆數(n)、構造點對的平均時間、匹配點對的平均時間、匹配過程平均總耗時及匹配率。表3給出了第2種方法對NGC2168中不同大小列表所花費時間的統計。它也包括列表中星的顆數(n)、構造特征向量的平均時間、匹配特征向量的平均時間、匹配過程平均總耗時及匹配率。

表1 所使用的資料集說明

圖3 匹配好的NGC2168圖像

n 構造點對(ms)匹配點對(ms)總耗時(ms)匹配率%1000330305219588592001880398261899163003490485339899804006480661482810050104508665589100601505112161511008027891626899610010045992026147561001501076429912121210020018986441426889100

表3 方法2處理NGC2168圖像用時統計

圖4描繪了對于NGC2168星團，方法1中點對的匹配時間相對于點對構造時間的對比。從圖中可以直觀看出，當n較小時，構造點對所花費的時間幾乎是可以忽略的，匹配點對占大部分時間。但隨著n的增加，構造點對所花費的時間急劇增加，而匹配點對的時間卻接近于一個常數。顯然構造點對占據了絕大部分時間。

圖5給出了對于NGC2168星團，基于徑向和環向特征的方法在構造特征向量和匹配特征向量階段的時間對比。發現當n較小時，匹配特征向量所花費的時間是很小的，但隨著n的增加，匹配特征向量所花費的時間卻陡然增加，說明此方法的時間主要花費在此階段。

圖4 NGC2168中構造和匹配點對所用的時間對比

圖5 NGC2168中構造和匹配特征向量所用的時間對比

圖6給出了兩種方法在匹配階段及整個匹配過程所花費時間的對比。由于不同的人所使用的機器不同或者是所使用的列表大小不一樣等原因，所以絕對的運行時間是沒有可比性的。

圖6 NGC2168中兩種方法的對比(方法1：基于向量的方法，方法2：基于徑向和環向特征的方法)

圖7給出了星團NGC1664觀測時一幀典型的CCD的圖像，畫圈的表示已匹配的(在UCAC2中)星。表4給出了第1種方法對于NGC1664中不同大小列表所花費時間的統計。表5給出了第2種方法對于NGC1664中不同大小列表所花費時間的統計。

圖7 匹配好的NGC1664圖像

n 構造點對(ms)匹配點對(ms)總耗時(ms)匹配率%1000630345238586692001600458291895963003701535399898984006851961487810050108024565719100601607292169911008030153647901610010046754016150561001501098849112315210020019997558428421100

表5 方法2處理NGC1664圖像用時統計

圖8描繪了對于NGC1664星團，方法1中點對的匹配時間相對于點對構造時間的對比。圖9給出了對于NGC1664星團，基于徑向和環向特征的方法在構造特征向量和匹配特征向量階段的時間對比。圖10給出了NGC1664中兩種方法的對比。可以看出，和NGC2168的測試結果基本相同。

圖8 NGC1664中構造和匹配點對所用的時間對比

圖9 NGC1664中構造和匹配特征向量所用的時間對比

圖10 NGC1664中兩種方法的對比(方法1：基于向量的方法，方法2：基于徑向和環向特征的方法)

4 結 論

本文采用基于向量的方法和基于徑向和環向特征的方法對實際的天文圖像進行了匹配。通過對NGC2168和NGC1664的大量圖像進行匹配，結果都表明基于向量的方法更優，它在匹配階段所需時間幾乎是一個常數，獨立于列表的大小，而基于徑向和環向特征的方法在匹配階段耗時較多。

致謝：感謝孟小華副教授，張慶豐副教授在本文研究過程中提出的建設性意見。

[1] Stetson P B. DAOPHOT: A computer program for crowded-field stellar photometry[J]. PASP,1987, 99: 191-222.

[2] Schechter P L, Mateo M, Saha A. DOPHOT, A CCD photometry program: description and tests[J]. PASP, 1993, 105:1342-1353.

[3] Bertin E, Arnouts S. SExtractor: Software for source extraction[J]. A&AS, 1996, 117:393-404.

[4] Groth E J. A pattern-matching algorithm for two-dimensional coordinate lists[J].AJ, 1986, 91: 1244-1248.

[5] Murtagh F. A new approach to point-pattern matching[J]. PASP, 1992, 104:301-307.

[6] Valdes F G, Campusano L E, Velasquez J D, et al. FOCAS automatic catalog matching algorithm[J].PASP, 1995, 107: 1119-1128.

[7] Pal A, Bakos G A. Astrometry in Wide-Filed Surveys[J]. PASP, 2006, 118:1474-1483.

[8] Tabur V. Fast algorithm for matching CCD images to a stellar catalogue[J]. PASA, 2007, 24:189-198.

[9] Zhang G J, Wei X. G, Jiang J. Full-sky autonomous star identification based on radial and cyclic features of star pattern[J].Image and Vision Computing, 2008,26：891-897.

[10] Stone R C.A Comparison of Digital Centering Algorithms[J].AJ,1989, 97：1227-1237.

[11] Zacharias N，Urban S E, Zacharias M I , et al. The Second US Naval Observatory CCD Astrograph (UCAC2)[J].AJ, 2004, 127：3043-3059.

[12] 李展，彭青玉，韓國強，CCD圖像數字定心算法的比較[J].天文學報，2009, 50(3): 340-348.

LI Zhan,PENG Qing-yu,HAN Guo-qiang.Comparison of Digital Centering Algorthms Based on CCD Images[J].Acta Astronomica Sinica,2009,50(3):340-348.