一種新的基于灰度的圖像匹配方法

1、技 術(shù) 創(chuàng) 新中 文 核 心 期 刊 微 計(jì) 算 機(jī) 信 息 (管 控 一 體 化 2007年 第 23卷 第 10-3期元 /:現(xiàn)場(chǎng)總線技術(shù)應(yīng)用 200例 圖 像 處 理一種新的基于灰度的圖像匹配方法A New gray-based Method of Im ages Matching(中國(guó)科學(xué)院電子學(xué)研究所 ; 中國(guó)科學(xué)院研究生院 范俐捷王巖飛 高 鑫FAN LIJIE WANG YANFEI GAO XIN摘要 :傳 統(tǒng) 的 基 于 灰 度 的 圖 像 匹 配 方 法 , 不 能 處 理 多 傳 感 器 圖 像 間 的 匹 配 , 基 于 特 征 的 方 法 往 往 又 比 較 繁 瑣

2、。 該 文 為 了 滿 足圖 像 匹 配 計(jì) 算 量 小 , 適 用 性 強(qiáng) 的 要 求 , 提 出 了 基 于 灰 度 的 MVGA(Mutual Variance combined with Genetic Arithmetic 算 法 。 我 們 采 用 了 遺 傳 算 法 的 思 想 和 結(jié) 構(gòu) , 選 擇 交 互 方 差 作 為 算 法 的 適 應(yīng) 度 函 數(shù) , 并 對(duì) 算 法 各 個(gè) 過 程 優(yōu) 化 , 從 搜 索 空 間 上 最 大 地 降 低 復(fù) 雜 度 。 新 算 法 是 一 種 基 于 灰 度 的 方 法 , 不 需 要 提 取 特 征 就 可 以 完 成 多 傳 感 器

3、 圖 像 之 間 的 匹 配 , 結(jié) 合 采 取 了 有 效 的 優(yōu) 化 策 略 , 使 算 法 具 有 較 高 的 匹 配 速 度 。 實(shí) 驗(yàn) 驗(yàn) 證 了 該 算 法 的 有 效 性 。 關(guān)鍵詞 :交互方差 ; 遺傳算法 ; 圖像匹配 ; 多傳感器 中圖分類號(hào) :TP751.1文獻(xiàn)標(biāo)識(shí)碼 :AAbstract:General gray-based method can t deal with the matching of multi-sensor images and Feature-based method appears com-plex . For the request of lo

4、w calculation quantity and powerful applicability, MVGA algorithm is proposed. We use mutual variance as the adaptation function and optimize each step of the algorithm for furthest reducing complexity from search space. The new algo-rithm is gray-based , can be used to multi-sensors images matching

5、 without extracting feature and adopts efficient optimization tac-tic. As a result, the efficiency is improved . The validity of the algorithm is verified through experiments. Key words:Mutual Variance, Genetic algorithms(GA, Image matching, Multi-sensor文章編號(hào) :1008-0570(200710-3-0296-021引言圖像 匹 配是 確 定

6、 同一 場(chǎng) 景 的兩 幅 來 自不 同 時(shí) 間 , 不 同 視 點(diǎn) , 不同成像幾何或由不同傳感器獲取的圖像在空間上相對(duì)位 置的過程 。 圖像匹配在導(dǎo)航 , 目標(biāo)跟蹤 , 目標(biāo)識(shí)別 , 打擊評(píng)估等 領(lǐng)域有廣泛的應(yīng)用 。 圖像匹配算法目前主要有兩大類 :一類是基 于灰度相關(guān)的匹配方法 , 它直接利用圖像的灰度進(jìn)行匹配 , 方 法有最小距離法 , 交叉相關(guān)法 , 相關(guān)系數(shù)法等 ; 另一類是基于特 征的匹配方法 , 這種 方 法需 要 先 對(duì)圖 像 提 取特 征 , 比 如點(diǎn) , 線 , 面特征等 , 然后對(duì)提取特征后的圖像進(jìn)行匹配 。 灰度相關(guān)的方 法由于沒有提 取 特 征的 過 程 , 計(jì)算 較

7、 為 簡(jiǎn)單 , 某 種 程度 上 比 基 于特征的方法復(fù) 雜度 要 低 , 但傳 統(tǒng) 的 基于 灰 度 的方 法 , 往 往不 能處理多傳感器的圖像 。 為了處理多傳感器圖像之間的匹配 , 傳統(tǒng)的方法往往會(huì)選擇基于特征的方法 , 比如曾經(jīng)廣泛采用的Hausdorff 距離方法 , 這 類 方 法往 往 需 要提 取 圖 像的 點(diǎn) , 線 或區(qū)域特征 , 處理往往較為繁瑣 , 存在圖像特征難于提取的問題 。為了 滿 足圖 像 匹 配目 前 應(yīng) 用上 時(shí) 效 性高 , 適 用 性強(qiáng) (可 以 用于多傳感器圖像之間匹配 的特點(diǎn) , 本文提出了 MVGA 算法 。 它是一種將交互方差和遺傳算法相結(jié)合的

8、方法 。 交互方差衡量 的是兩幅圖像之間的交互信息 , 不要求圖像之間灰度值具有線 性關(guān)系 , 只要求圖 像 之 間灰 度 值 具有 對(duì) 應(yīng) 一致 性 ; 遺 傳算 法 具 有內(nèi)在的并行性 , 可以極大的提高搜索的速度 。 這種結(jié)合使得MVGA 算法雖然也是基于圖像灰度進(jìn)行匹配 , 但具有以下優(yōu)點(diǎn) :首先 , 比交叉相關(guān)一類的傳統(tǒng)意義上的基于灰度的方法具有更 大的適用性 ; 其 次 , 它 不 需 要提 取 圖 像的 特 征 即可 完 成 圖像 匹 配 , 具有簡(jiǎn)單 的 復(fù) 雜度 ; 另 外 , 它運(yùn) 用 了 遺傳 算 法 的思 想 , 從 搜 索空間上最大化地降低復(fù)雜度 , 時(shí)效性更高 。

9、本文試驗(yàn)結(jié)果顯 示本算法的優(yōu)越性 。2MVGA 算法基本原理2.1遺傳算法基本結(jié)構(gòu)遺傳算法使用所謂的遺傳算子 (genetic operators 作用于群 體 p(t 中 , 進(jìn)行下述遺傳操作 , 從而得到新一代群體 p(t+1 。1 選擇 (selection 根據(jù)各個(gè)個(gè)體的適應(yīng)度 , 按照一定的規(guī)則和方法 , 從第 t 代群體 p(t 中選擇出一些優(yōu) 良 的個(gè) 體 遺 傳到 下一代群體 p(t+1 中 。2 交 叉 (crossover 將 群 體 p(t 內(nèi) 的 各 個(gè) 個(gè) 體 隨 機(jī) 搭 配 成 對(duì) , 對(duì) 每 一對(duì) 個(gè) 體 , 以 某 個(gè) 概 率 (稱 為 交 叉 概 率 , cr

10、ossover rate 交換它們之間的部分染色體 。3 變異 (mutation 對(duì)群體 p(t 中的每一個(gè)個(gè)體 , 以某一概率 (稱為變異概率 , mutation rate 改變某一個(gè)或某一些基因坐上的基因值為其它的等位基因 。通過對(duì)基本遺傳算法的研究 , 新算法進(jìn)行了繼承和發(fā)展 :1 將傳統(tǒng)的二進(jìn)制編碼改進(jìn)為格雷碼 (gray code 。2 采用了擇優(yōu)初始化的方法確定初始種群 。3 根據(jù)新一代的特性 , 適當(dāng)修正交叉率和變異率 。 2.2交互方差交互方差源于這樣一個(gè)思想 :一幅圖像的每個(gè)灰度級(jí)在像素位置上所對(duì)應(yīng)的另一幅圖像的灰度級(jí)最穩(wěn)定 , 在數(shù)學(xué)上就表 現(xiàn)為方差最小 。假設(shè)兩幅圖像

11、 A 和 B 大小為 M ×N, 其 灰度 直 方 圖分 別 為H A (n 和 H B (n , P A (i 和 P B (i 分 別 為 A 和 B 第 i 級(jí) 灰 度 值 的 概 率 。 定義 B 相對(duì)于 A 灰度值為 n 的對(duì)應(yīng)像素集合的灰度均值和 方范俐捷 :在讀博士生基金項(xiàng)目 :十一五預(yù)研項(xiàng)目 (編號(hào)不公開 - :360元 /年 技術(shù) 創(chuàng) 新圖 像 處 理PLC 技術(shù)應(yīng)用 200例 您 的 論 文 得 到 兩 院 院 士 關(guān) 注 差分別為和, 同理定義 A 相對(duì)于 B 灰度值為 n 的對(duì)應(yīng)像素集合的灰度均值和方差分別為和(1 (2 (3 (4再定義和分別為圖像 A 和

12、B 灰度分布的標(biāo)準(zhǔn)差 。 則可以定義交互方差 (MV:mutual variance 為 :(5其中 ,交互方差反映了兩幅圖像灰度相互對(duì)應(yīng)的穩(wěn)定程度 , 通過 對(duì)其的分析可 以 知道 交 互 方差 越 小 , 兩幅 圖 像 匹配 越 好 , 完全 匹配時(shí)交互方差為 0, 完全不相關(guān)時(shí) , 交互方差接近為 2。3GAMA 算法在圖像匹配中的應(yīng)用3.1編碼方案圖像匹配的目的是找到最優(yōu)的匹配位置 , 將匹配位置從解 空間轉(zhuǎn)換到本算法編碼空間的過程即為編碼 , 編碼是本算法的 一個(gè)關(guān)鍵步驟 。 最常用的編碼方法是采用二進(jìn)制編碼作為基因 串來表示匹配的 X,Y 坐標(biāo) 。 但二進(jìn)制編碼的某一位變異時(shí) ,

13、編 碼所代表空間位置可能產(chǎn)生很大差異 (比如 :0000和 0100相差8 , 會(huì)對(duì)本圖像匹配算法的收斂和精確度造成不利影響 。 格雷碼屬于一種循環(huán)碼 , 具有在相鄰空間位置上只差一個(gè)比特的良 好特性 , 滿足相鄰空間位置碼形相似的要求 。 因此我們考慮采 用 Gray Code (格雷碼 來代替二進(jìn)制編碼 。 我們采用如下的編 碼方案 :將上面的 x ,y 軸坐標(biāo)的組合編譯成格雷碼 , 參與交叉和變 異 。 碼字所用比特?cái)?shù)和圖像的尺寸大小有關(guān) 。3.2適應(yīng)度函數(shù)的選擇假設(shè) 表 示待 匹 配 圖 像 , 其 大 小 為 ;B(x,y 表 示 基 準(zhǔn) 圖像上以 (x,y 為左上角的在其范圍內(nèi)的大

14、小為 的一 幅 截 取圖 。 這樣我們定義我們的適應(yīng)度函數(shù)如下 :(6根據(jù) 分 析可 以 知 道適 應(yīng) 度 函數(shù) 隨 兩 幅圖 像 之 間 的 相 關(guān) 程 度增加而遞增 , 當(dāng)兩幅圖像完全相關(guān)時(shí) , 取值為 0; 兩幅圖像完 全不相關(guān)時(shí) , 取值接近于 2。我們的目的是找到 S(x,y 的最小值 。 3.3種群初始化和選擇機(jī)制一般的種群初始化都是采用隨機(jī)選取 。 考慮到初始種群的 質(zhì)量會(huì)影響到后代的質(zhì)量 , 進(jìn)而影響到我們算法的收斂 。 我們采用了擇優(yōu) 初 始化 方 法 , 先隨 即 產(chǎn) 生 n 個(gè) 位 置 , 求取 它 們 適應(yīng) 度函數(shù)值的均值 m 作為后來選取種群的門限 。 大于門限 m

15、的 被選擇為初始種群中的個(gè)體 , 直到選擇量 達(dá) 到 設(shè)定 的 值 N 為 止 。 在從前一代中選擇優(yōu)勝的個(gè)體 , 淘汰劣質(zhì)個(gè)體的過程中 , 最 常用的方法 是 適 應(yīng)度 比 例 方法 , 為 了 加速 收 斂 , 我們 在 采 用適 應(yīng)度比例方法的前提下 , 又保留了前一代的最優(yōu)個(gè)體 , 并且在當(dāng) 前代最優(yōu)差于前一代最優(yōu)的情況下 , 用前一代最優(yōu)個(gè)體替換當(dāng) 前代的最優(yōu)個(gè)體 , 保證種群質(zhì)量的遞增性 。3.4自適應(yīng)調(diào)節(jié)交叉概率 (pc 和變異概率 (pm 。新算法需要解決的兩個(gè)重要問題是 :收斂過慢 ; 進(jìn)入局部收斂 。為了解決這兩個(gè)問題 , 我們進(jìn)行了以下分析 。 遺傳最開始 時(shí) , 一般后

16、一代的最優(yōu)值要大于前一代 , 到了一定代數(shù)時(shí) , 會(huì)出 現(xiàn)后一代差于前一代的情況 , 或接連幾代最優(yōu)解相同的情況 。 后一代差于前一代的情況會(huì)影響收斂的速度 , 接連幾代最優(yōu)值 相同 的 情 況可 能 是 找到 了 最 優(yōu)解 , 也 有 可能 是 陷 入了 局 部 最 優(yōu) 。 為此 , 我們得到新的一代后 , 將后一代的最優(yōu)值和前一代作 比較 , 如 果增 大 , 說 明遺 傳 朝 良 性 發(fā) 展 , 我 們 提 高 pc, 降 低 pm , 可以加快收斂 ; 當(dāng)出現(xiàn)后一代最優(yōu)解差于前一代時(shí) , 說明遺傳朝 惡性發(fā)展 , 我們一方面用前一代的最優(yōu)值替換掉新一代的最優(yōu) 值來遏制惡性發(fā)展 , 另一

17、方面增加 pm, 降低 pc 來擺脫局部收斂 的狀態(tài) 。 我們對(duì)此做了實(shí)驗(yàn) , 發(fā)現(xiàn)這種自適應(yīng)調(diào)解后 , 對(duì)提高收 斂是有作用的 。4算法實(shí)驗(yàn)結(jié)果為了驗(yàn)證新算法的有效 性 , 本文 進(jìn) 行 了實(shí) 驗(yàn) (Pentium(R 4的機(jī)器 , CPU 主頻為 1.50GHZ , 將新算法和廣泛使用的 Haus-dorff 距離方法進(jìn)行比較 。 實(shí)驗(yàn)用兩幅不同模態(tài)的同一區(qū)域的光 學(xué)圖像 img1(圖 1 和 SAR 圖像 img2, 大小 為 的 img1作為 基 準(zhǔn) 圖 , 在 img2上多次截取大小為的圖像作為待匹配圖像 , 進(jìn)行多 次 匹配 (圖 2為 截取 的 其 中一 幅 圖 像 , 圖 3為

18、 對(duì) 應(yīng)的 匹 配 結(jié)果 。最后得到的平均匹配時(shí)間為 1719ms, 中匹配的圖像時(shí)間大 約為 9000ms, 中 采用 與 本 試驗(yàn) 同 樣 的圖 像 的 平均 匹 配 時(shí) 間 為 2287ms, 可見新算法具有一定優(yōu)越性 。 由試驗(yàn)可以得出 , 本文提出的新算法具有處理多傳感器圖像的能力 , 同時(shí)有不錯(cuò)的時(shí)效 性 , 另外新算法和錯(cuò)誤 ! 未定義書簽 。 相比避免了提取特征的繁 瑣過程 , 從而不存在提取特征所引入的誤差 。圖 1基準(zhǔn)圖圖 2待匹配圖圖 3匹配結(jié)果(下轉(zhuǎn)第 8頁(yè) 297-技 術(shù) 創(chuàng) 新中 文 核 心 期 刊 微 計(jì) 算 機(jī) 信 息 (管 控 一 體 化 2007年 第 23

19、卷 第 10-3期元 /:現(xiàn)場(chǎng)總線技術(shù)應(yīng)用 200例 控 制 管 理events list;Step2:scan the coming events list to find the earliest terminat-ing time of transitions, and mark it t;Step3:execute the firing, last for a period of time, process in-formation; ;Step4:terminate the firing, and simulation clock advances to t, then turn t

20、o step 1.Fig.2Effectiveness assessment system' s object models of OPN5ConclusionsBased on the research of function and characteristics of OPN, referring to its application in simulation of C4ISR system, the framework of OPN-based ICBM s operational effectiveness assess-ment system is established

21、. The method discretizes missile combat process, and system analysis based upon OPN classes clarifies the information flow among combat units. Some expanded functions of OPN are propitious to implement system dynamic simulation. The framework can help to assess missile operational effectiveness, but

22、 it needs to be refined further. Next we will complete the system simulation operation, expand the system from single computer sim-ulation to distributed simulation. References:1Han Songchen. Stochastic Theory and Method for Effectiveness Analysis of Missile Weapon System M. Beijing:China National D

23、efense Industry Press, 2002.2Chen Lei. Research on Missile-Combat Simulation System D. Changsha:Doctor s Thesis, National University of Defense Tech-nology, 2000.3Fang Hua, Wang Hangyu. A Model of CEC System Based on OPN J. Control &Automation,2005,21(9-1:5254Biography:Li Jiutian (1975-, Male, H

24、an nationality. The cur-rent researching interests include system effectiveness analysis; Tang Guojin (1963-,Male, Han nationality, Professor. The cur-rent researching interests include modeling and simulation of flight vehicle system, missile structure integrality.(College of Aerospace and Material

25、 Engineering, National U-niv. of Defense Technology, Changsha 410073, China Li Jiutian Tang Guojin Liang Yangang(收稿日期 :2007.7.03(修稿日期 :2007.9.05(上接第 297頁(yè) 5結(jié)論本文所提出的 MVGA 算法為滿 足 圖像 匹 配 的多 傳 感 器適 用性和匹配 高 效率 性 , 利 用了 基 于 灰度 的 方 法的 優(yōu) 點(diǎn) , 將交 互 信息用于遺傳算法結(jié)構(gòu)中實(shí)現(xiàn)圖像匹配 。 由于它不需要提取圖 像點(diǎn) , 線 特征 就 可 以對(duì) 多 傳 感器 圖 像 進(jìn)行 匹

26、 配 , 使得 它 具 有較 低的復(fù)雜度 。 它將圖像匹配問題轉(zhuǎn)化為收斂到適應(yīng)度函數(shù)值最 小的問題 , 并 對(duì) 算 法結(jié) 構(gòu) 中 各個(gè) 環(huán) 節(jié) 進(jìn)行 優(yōu) 化 和改 進(jìn) , 實(shí) 現(xiàn)快 速找到匹配點(diǎn)的目的 。 實(shí)驗(yàn)結(jié)果顯示這種新的基于灰度的圖像 匹配方法有效且可行 。創(chuàng)新點(diǎn) :本文從降低匹配的時(shí)間復(fù)雜度提出和空間復(fù)雜度 出發(fā)提出了 MVGA 算法 , 這種算法和文獻(xiàn)中提到的基于 Haus-dorff 距離方法相比具有計(jì)算復(fù)雜度低 , 步驟簡(jiǎn)單的特點(diǎn) 。 參考文獻(xiàn) :1曹炬,馬杰, 譚毅華, 田金文 . 基于像素抽樣的快速互相關(guān)圖 像匹配算法 J, 宇航學(xué)報(bào), 2004(3, 25(2 :173-1

27、782Ren-Jean Liou, Mahmood R.Azimi-Sadiadi. Dim target detec-tion using high order correlation method J.IEEE Transaction on aerospace and electronic systems, 1993, 29(3:841-8563Brown LG. A Survey of image registration techniquesJ. ACM Computing Surveys, 1992, 24(4:325-3764冷雪飛,劉建業(yè), 熊智, 邢廣華 . 魯棒 Hausdorff 距離在 SAR/慣 性組合導(dǎo)航圖像匹配中的應(yīng)用研究 J. 東南大學(xué)學(xué)報(bào) (自然科學(xué) 版 ,2004(11,34(Sup:141-1445于秋則,程輝, 柳建等 . 基于改進(jìn)的 Hausdorff 測(cè)度和遺傳算法 的 SAR 圖像與光學(xué)圖像匹配 J. 宇航學(xué)報(bào), 2006(1,27(1:130-1346史錫