任俊杰,彭青玉,3

(1.暨南大學(xué)計(jì)算機(jī)科學(xué)系，廣州 510632；2.廣東省高等學(xué)校光學(xué)信息與傳感技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣州 510632;3.中國科學(xué)院光學(xué)天文聯(lián)合開放實(shí)驗(yàn)室昆明基地，昆明 650011)

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

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

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

文章的內(nèi)容是這樣安排的：第1節(jié)介紹了基于向量的方法；第2節(jié)描述了基于徑向和環(huán)向特征的方法；第3節(jié)給出了兩種方法實(shí)驗(yàn)結(jié)果的對(duì)比分析；最后一部分是結(jié)論。

1 基于向量的方法

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

1.1 構(gòu)造點(diǎn)對(duì)

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

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

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

(1)

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

圖1 使用用戶定義的m顆星來構(gòu)造預(yù)先定義的形狀

從列表R中取出前n顆亮星構(gòu)造點(diǎn)對(duì)列表，則n顆星總共可構(gòu)造的點(diǎn)對(duì)數(shù)為：

P=n(n-1)/2

(2)

構(gòu)造點(diǎn)對(duì)列表的目的是提供星表中點(diǎn)對(duì)的相關(guān)信息，以供圖像中的點(diǎn)對(duì)進(jìn)行搜索匹配。為了加快搜索速度，先按照角距離對(duì)所構(gòu)造的點(diǎn)對(duì)列表進(jìn)行排序，位置角也同樣會(huì)被排序，因?yàn)樗徒蔷嚯x是一一對(duì)應(yīng)的。這種方法只需要構(gòu)造一個(gè)點(diǎn)對(duì)列表，而且所構(gòu)造的點(diǎn)對(duì)數(shù)目遠(yuǎn)遠(yuǎn)小于傳統(tǒng)的三角形方法所構(gòu)造的三角形數(shù)目[8]。

1.2 匹配點(diǎn)對(duì)

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

一旦m個(gè)候選點(diǎn)被識(shí)別，這m個(gè)點(diǎn)就會(huì)被用來求解底片常數(shù)(這里采用6常數(shù)模型)。如果底片常數(shù)正確，則匹配成功。否則說明這m個(gè)點(diǎn)中存在某些誤配點(diǎn)，這時(shí)將用一個(gè)函數(shù)來循環(huán)找出正確匹配的點(diǎn)，剔除錯(cuò)誤匹配的點(diǎn)。如果m個(gè)候選點(diǎn)中正確匹配的點(diǎn)數(shù)小于3，則調(diào)用此函數(shù)會(huì)失敗。因?yàn)橹辽傩枰?個(gè)點(diǎn)才能確定圖像和星表之間的對(duì)應(yīng)關(guān)系，用下一個(gè)m顆星所構(gòu)造的形狀特征集來繼續(xù)這個(gè)過程。這個(gè)過程將重復(fù)進(jìn)行直到有足夠多的星被識(shí)別為止，否則就是匹配失敗。

2 基于徑向和環(huán)向特征的方法

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

2.1 構(gòu)造徑向特征

徑向特征的構(gòu)造方式如下：

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

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

Rr為特征模式半徑，Nq為量化等級(jí)Rc為特征模式半徑

NS為Rr半徑鄰域內(nèi)星的個(gè)數(shù)

圖2 徑向特征和環(huán)向特征示意圖

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

2.2 構(gòu)造環(huán)向特征

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

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

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

2.3 構(gòu)建導(dǎo)航數(shù)據(jù)庫

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

2.4 匹配特征向量

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

2.4.1 初始匹配

2.4.2 后續(xù)匹配

理論上，如果存在兩顆以上的觀測(cè)星對(duì)應(yīng)的候選匹配星唯一，則可進(jìn)入驗(yàn)證識(shí)別階段。如果C中存在大量的冗余匹配，將用環(huán)向特征對(duì)其作進(jìn)一步的篩選。如果觀測(cè)星圖的環(huán)向特征和導(dǎo)航星模式庫中的相同，則保留該候選匹配星，否則剔除。

2.4.3 FOV約束

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

3 實(shí)驗(yàn)結(jié)果對(duì)比分析

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

表1 所使用的資料集說明

圖3 匹配好的NGC2168圖像

n 構(gòu)造點(diǎn)對(duì)(ms)匹配點(diǎn)對(duì)(ms)總耗時(shí)(ms)匹配率%1000330305219588592001880398261899163003490485339899804006480661482810050104508665589100601505112161511008027891626899610010045992026147561001501076429912121210020018986441426889100

表3 方法2處理NGC2168圖像用時(shí)統(tǒng)計(jì)

圖4描繪了對(duì)于NGC2168星團(tuán)，方法1中點(diǎn)對(duì)的匹配時(shí)間相對(duì)于點(diǎn)對(duì)構(gòu)造時(shí)間的對(duì)比。從圖中可以直觀看出，當(dāng)n較小時(shí)，構(gòu)造點(diǎn)對(duì)所花費(fèi)的時(shí)間幾乎是可以忽略的，匹配點(diǎn)對(duì)占大部分時(shí)間。但隨著n的增加，構(gòu)造點(diǎn)對(duì)所花費(fèi)的時(shí)間急劇增加，而匹配點(diǎn)對(duì)的時(shí)間卻接近于一個(gè)常數(shù)。顯然構(gòu)造點(diǎn)對(duì)占據(jù)了絕大部分時(shí)間。

圖5給出了對(duì)于NGC2168星團(tuán)，基于徑向和環(huán)向特征的方法在構(gòu)造特征向量和匹配特征向量階段的時(shí)間對(duì)比。發(fā)現(xiàn)當(dāng)n較小時(shí)，匹配特征向量所花費(fèi)的時(shí)間是很小的，但隨著n的增加，匹配特征向量所花費(fèi)的時(shí)間卻陡然增加，說明此方法的時(shí)間主要花費(fèi)在此階段。

圖4 NGC2168中構(gòu)造和匹配點(diǎn)對(duì)所用的時(shí)間對(duì)比

圖5 NGC2168中構(gòu)造和匹配特征向量所用的時(shí)間對(duì)比

圖6給出了兩種方法在匹配階段及整個(gè)匹配過程所花費(fèi)時(shí)間的對(duì)比。由于不同的人所使用的機(jī)器不同或者是所使用的列表大小不一樣等原因，所以絕對(duì)的運(yùn)行時(shí)間是沒有可比性的。

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

圖7給出了星團(tuán)NGC1664觀測(cè)時(shí)一幀典型的CCD的圖像，畫圈的表示已匹配的(在UCAC2中)星。表4給出了第1種方法對(duì)于NGC1664中不同大小列表所花費(fèi)時(shí)間的統(tǒng)計(jì)。表5給出了第2種方法對(duì)于NGC1664中不同大小列表所花費(fèi)時(shí)間的統(tǒng)計(jì)。

圖7 匹配好的NGC1664圖像

n 構(gòu)造點(diǎn)對(duì)(ms)匹配點(diǎn)對(duì)(ms)總耗時(shí)(ms)匹配率%1000630345238586692001600458291895963003701535399898984006851961487810050108024565719100601607292169911008030153647901610010046754016150561001501098849112315210020019997558428421100

表5 方法2處理NGC1664圖像用時(shí)統(tǒng)計(jì)

圖8描繪了對(duì)于NGC1664星團(tuán)，方法1中點(diǎn)對(duì)的匹配時(shí)間相對(duì)于點(diǎn)對(duì)構(gòu)造時(shí)間的對(duì)比。圖9給出了對(duì)于NGC1664星團(tuán)，基于徑向和環(huán)向特征的方法在構(gòu)造特征向量和匹配特征向量階段的時(shí)間對(duì)比。圖10給出了NGC1664中兩種方法的對(duì)比?？梢钥闯觯蚇GC2168的測(cè)試結(jié)果基本相同。

圖8 NGC1664中構(gòu)造和匹配點(diǎn)對(duì)所用的時(shí)間對(duì)比

圖9 NGC1664中構(gòu)造和匹配特征向量所用的時(shí)間對(duì)比

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

4 結(jié) 論

本文采用基于向量的方法和基于徑向和環(huán)向特征的方法對(duì)實(shí)際的天文圖像進(jìn)行了匹配。通過對(duì)NGC2168和NGC1664的大量圖像進(jìn)行匹配，結(jié)果都表明基于向量的方法更優(yōu)，它在匹配階段所需時(shí)間幾乎是一個(gè)常數(shù)，獨(dú)立于列表的大小，而基于徑向和環(huán)向特征的方法在匹配階段耗時(shí)較多。

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

[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] 李展，彭青玉，韓國強(qiáng)，CCD圖像數(shù)字定心算法的比較[J].天文學(xué)報(bào)，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.