華夏等

摘要摘要：論述了圖像校正算法的并行集群實(shí)現(xiàn)方法。針對(duì)圖像復(fù)原問(wèn)題，對(duì)復(fù)原算法結(jié)構(gòu)與流程的并行處理進(jìn)行研究，提出了整體數(shù)據(jù)傳輸、按行分片計(jì)算復(fù)原的并行處理方法。該方法在基于MPI的計(jì)算機(jī)并行集群系統(tǒng)中的8個(gè)計(jì)算節(jié)點(diǎn)上通過(guò)了測(cè)試，給出了集群校正實(shí)驗(yàn)結(jié)果和MPI并行計(jì)算時(shí)空?qǐng)D。實(shí)驗(yàn)結(jié)果表明，基于集群計(jì)算的并行復(fù)原方法十分有效，可縮短計(jì)算時(shí)間，提高計(jì)算效率。

關(guān)鍵詞關(guān)鍵詞：圖像復(fù)原；并行處理；MPI；集群計(jì)算

DOIDOI：10.11907/rjdk.151061

中圖分類(lèi)號(hào)：TP317.4

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)

文章編號(hào)：16727800（2015）004014203

0引言

退化圖像的快速?gòu)?fù)原是成像探測(cè)研究的重要課題。傳統(tǒng)的復(fù)原方法是在目標(biāo)圖像點(diǎn)擴(kuò)展函數(shù)確定的情況下，用去卷積的方法來(lái)實(shí)現(xiàn)圖像復(fù)原。然而，在復(fù)雜條件下，點(diǎn)擴(kuò)展函數(shù)很難測(cè)定與預(yù)先獲得[1]?；跇O大似然估計(jì)準(zhǔn)則的正則化圖像復(fù)原算法利用序列多幀退化圖像數(shù)據(jù)，采用極大似然估計(jì)方法來(lái)尋找最相似于退化圖像的點(diǎn)擴(kuò)展函數(shù)和目標(biāo)圖像，從概率意義上達(dá)到極大程度恢復(fù)圖像的目的[2，3]。由于該復(fù)原算法采用迭代的方式，因此計(jì)算量大，計(jì)算速度較慢。為了縮短計(jì)算時(shí)間，加快計(jì)算速度，人們對(duì)算法的結(jié)構(gòu)優(yōu)化和計(jì)算方法進(jìn)行了研究[4]，但要將計(jì)算負(fù)擔(dān)降低一半以上仍存在困難。因此，對(duì)該算法采用高性能并行化處理值得深入研究。

高性能計(jì)算技術(shù)在國(guó)內(nèi)外受到高度重視，其在科學(xué)研究、工程技術(shù)以及軍事技術(shù)方面的應(yīng)用已取得了巨大成果。目前，利用相對(duì)廉價(jià)的微機(jī)和高速網(wǎng)絡(luò)構(gòu)建高性能的并行與分布式集群計(jì)算系統(tǒng)來(lái)完成高性能計(jì)算任務(wù)已越來(lái)越普遍[5]。集群計(jì)算在圖像校正方面有著廣闊的應(yīng)用前景。建立算法并行模型的問(wèn)題即是解決算法如何并行的問(wèn)題，如何把單機(jī)運(yùn)行的圖像處理算法改造成在并行集群上運(yùn)行的算法。并行計(jì)算的目的是充分利用計(jì)算集群系統(tǒng)資源，縮短計(jì)算時(shí)間，提高計(jì)算效率。并行計(jì)算的實(shí)現(xiàn)方法是將一個(gè)大計(jì)算量的計(jì)算任務(wù)分解成多個(gè)子任務(wù)，分配給各個(gè)節(jié)點(diǎn)進(jìn)行并行計(jì)算。由于計(jì)算上的內(nèi)在關(guān)聯(lián)性，計(jì)算節(jié)點(diǎn)之間必須進(jìn)行數(shù)據(jù)交換，然而圖像復(fù)原校正處理中圖像的數(shù)據(jù)量通常較大，所以并行計(jì)算不可避免地會(huì)引入額外的節(jié)點(diǎn)間的通信時(shí)間。額外的通信時(shí)間過(guò)大，將降低并行計(jì)算的運(yùn)行效率。如果通信時(shí)間大于算法并行計(jì)算節(jié)省的計(jì)算時(shí)間，并行集群計(jì)算系統(tǒng)運(yùn)行速度將低于一臺(tái)計(jì)算機(jī)的運(yùn)行速度，并行計(jì)算則失去了意義。因此，建立算法的并行模型，需要確定算法哪一部分運(yùn)算需要進(jìn)行并行計(jì)算，哪一部分不并行，如何并行處理直接決定著并行計(jì)算的運(yùn)行效率。

建立算法并行模型過(guò)程分為3步：①對(duì)算法模型與流程進(jìn)行分析，找出算法中運(yùn)算量最大的幾個(gè)計(jì)算量或步驟，也即需要并行計(jì)算的部分；②對(duì)需要并行計(jì)算的計(jì)算量進(jìn)行分析，找出并行實(shí)現(xiàn)的方法；③分析并行計(jì)算的可行性，如果計(jì)算耗時(shí)遠(yuǎn)大于并行計(jì)算需要的額外通信耗時(shí)，并行計(jì)算則是高效和可行的；如果計(jì)算耗時(shí)小于額外通信耗時(shí)，或者與通信耗時(shí)相當(dāng)，并行計(jì)算則是低效的。

MPI（Message Passing Interface）是目前比較流行的并行計(jì)算開(kāi)發(fā)環(huán)境之一。MPI是一個(gè)并行計(jì)算消息傳遞接口標(biāo)準(zhǔn)，其現(xiàn)已成為被產(chǎn)業(yè)界廣泛支持的并行計(jì)算標(biāo)準(zhǔn)，具有可移植性，因此選擇MPI來(lái)構(gòu)建并行校正計(jì)算系統(tǒng)。

1基于空間域按行分片的并行計(jì)算處理方法

流場(chǎng)點(diǎn)擴(kuò)展函數(shù)具有衰減性質(zhì)，有意義的支撐區(qū)域（其值大于零）集中在峰值附近[6]。點(diǎn)擴(kuò)展函數(shù)的支撐區(qū)域一般比圖像的支撐區(qū)域小得多。因此，對(duì)點(diǎn)擴(kuò)展函數(shù)而言，只需要估計(jì)點(diǎn)擴(kuò)展函數(shù)空間支撐域范圍內(nèi)的有效值。

由復(fù)原校正算法可知，若圖像大小為N×N，點(diǎn)擴(kuò)展函數(shù)支撐域?yàn)镸×M，則在每次迭代中，計(jì)算點(diǎn)擴(kuò)展函數(shù)和目標(biāo)圖像的加法和乘法運(yùn)算量正比于N2M2，在圖像空間域進(jìn)行計(jì)算時(shí)，計(jì)算工作量較大，圖像恢復(fù)較慢。為了縮短計(jì)算時(shí)間，加快計(jì)算速度，有必要對(duì)基于EM計(jì)算的最大似然估計(jì)復(fù)原校正算法（簡(jiǎn)稱(chēng)EM算法）進(jìn)行并行化處理。

從算法流程可知，EM算法是一個(gè)多次迭代過(guò)程，每一次迭代過(guò)程都包含多個(gè)計(jì)算步驟。因此沒(méi)有必要把每一個(gè)計(jì)算步驟都并行化，因?yàn)椴⒉皇敲總€(gè)計(jì)算步驟都需要并行化，對(duì)計(jì)算量過(guò)小的計(jì)算步驟并行化，引入的通信時(shí)間會(huì)大于并行計(jì)算節(jié)省的計(jì)算時(shí)間，反而會(huì)降低算法運(yùn)行速度。所以，只需選取計(jì)算量較大的計(jì)算步驟進(jìn)行并行化，計(jì)算量小的部分在根節(jié)點(diǎn)上單機(jī)計(jì)算，在實(shí)現(xiàn)并行計(jì)算的同時(shí)達(dá)到減少節(jié)點(diǎn)間通信量的目的。

對(duì)單機(jī)上運(yùn)行的串行EM算法每一次迭代過(guò)程中的各個(gè)步驟計(jì)算時(shí)間進(jìn)行了記錄。從單機(jī)運(yùn)行的時(shí)間結(jié)果來(lái)看，一次迭代過(guò)程中a、b、c三個(gè)計(jì)算步驟（見(jiàn)表1）用時(shí)占一次迭代計(jì)算總時(shí)間的99%以上，只要把這三個(gè)計(jì)算步驟進(jìn)行并行化，則可以大大降低計(jì)算耗時(shí)。其它幾個(gè)步驟計(jì)算量較低，沒(méi)必要分配到各節(jié)點(diǎn)進(jìn)行并行計(jì)算，否則節(jié)點(diǎn)間的數(shù)據(jù)通信和計(jì)算同步需要的時(shí)間可能會(huì)大于3ms，反而降低計(jì)算速度。所以，現(xiàn)將a、b、c三個(gè)計(jì)算步驟分配到各個(gè)節(jié)點(diǎn)上進(jìn)行并行計(jì)算，其它步驟在根節(jié)點(diǎn)（進(jìn)程號(hào)為0的節(jié)點(diǎn)）上用單機(jī)計(jì)算。

并行計(jì)算即把計(jì)算任務(wù)分配到各個(gè)計(jì)算節(jié)點(diǎn)上，a、b、c三個(gè)計(jì)算步驟需并行處理的計(jì)算值ik、hk及Ux，均可看成具有M行和N列的二維圖像（見(jiàn)圖1）。由于每一塊的計(jì)算涉及到整體圖像數(shù)據(jù)，所以提出整體數(shù)據(jù)傳輸、分塊計(jì)算復(fù)原的并行處理方法：即將整個(gè)圖像數(shù)據(jù)傳輸?shù)矫恳粋€(gè)計(jì)算節(jié)點(diǎn)上，在每一個(gè)節(jié)點(diǎn)上計(jì)算每一塊的數(shù)據(jù)值，然后傳回到根節(jié)點(diǎn)上，再整體傳輸?shù)礁鞴?jié)點(diǎn)上進(jìn)行分塊計(jì)算，直至計(jì)算結(jié)束為止。采用的分配方法是細(xì)粒度任務(wù)劃分方法，把圖像分成若干個(gè)子塊圖像并按行存放，為便于分片并行計(jì)算處理，按行對(duì)圖像進(jìn)行分配計(jì)算。把整個(gè)圖像根據(jù)并行計(jì)算節(jié)點(diǎn)數(shù)量按行平均分為n個(gè)子塊圖像，計(jì)算任務(wù)分配如圖1所示。按行分片，每個(gè)子塊圖像的計(jì)算在同一個(gè)計(jì)算節(jié)點(diǎn)上進(jìn)行，不同子塊圖像計(jì)算在不同計(jì)算節(jié)點(diǎn)上進(jìn)行。具體方法如圖2所示。

2基于MPI環(huán)境的并行計(jì)算與實(shí)現(xiàn)

利用內(nèi)部局域網(wǎng)把各臺(tái)獨(dú)立的計(jì)算機(jī)連接起來(lái)組成一個(gè)并行計(jì)算集群。集群系統(tǒng)采用并行計(jì)算方法，把圖像處理中計(jì)算量大的計(jì)算任務(wù)分解成各個(gè)子任務(wù)，然后分配給各個(gè)節(jié)點(diǎn)進(jìn)行并行計(jì)算。由于計(jì)算上的內(nèi)在關(guān)聯(lián)性，節(jié)點(diǎn)之間必然存在數(shù)據(jù)交換，而由于圖像的數(shù)據(jù)量相當(dāng)大，內(nèi)部網(wǎng)絡(luò)傳輸數(shù)據(jù)的速率是整個(gè)系統(tǒng)計(jì)算速度的瓶頸。盡量高的傳輸帶寬和盡量低的傳輸延時(shí) （Latency）是圖像處理集群系統(tǒng)高并行效率的基本要求[7]。因此，采用千兆光纖網(wǎng)絡(luò)來(lái)傳輸內(nèi)部網(wǎng)絡(luò)數(shù)據(jù)。

MPI并行計(jì)算進(jìn)程必須由mpirun命令啟動(dòng)[7]，mpirun命令只支持以命令提示符的方式啟動(dòng)并行計(jì)算進(jìn)程。因此，無(wú)法在軟件的主界面中調(diào)用MPI函數(shù)，只能通過(guò)命令行調(diào)用mpirun命令啟動(dòng)并行計(jì)算進(jìn)程。主程序和MPI并行計(jì)算程序是兩個(gè)獨(dú)立的進(jìn)程，各個(gè)進(jìn)程的存儲(chǔ)區(qū)獨(dú)立，進(jìn)程與進(jìn)程之間不能直接傳遞數(shù)據(jù)。并行計(jì)算輸入?yún)?shù)和輸入圖像的傳遞利用共享內(nèi)存映射方法實(shí)現(xiàn)。建立共享內(nèi)存映射即建立一段共享內(nèi)存，該內(nèi)存不屬于某個(gè)進(jìn)程獨(dú)有，每個(gè)進(jìn)程都可以通過(guò)這段內(nèi)存的名字來(lái)訪(fǎng)問(wèn)它。在MFC中CreateFileMapping函數(shù)可用來(lái)建立一段內(nèi)存映射。主進(jìn)程創(chuàng)建了共享內(nèi)存以后，MPI進(jìn)程和主進(jìn)程都可以使用這段內(nèi)存空間，主進(jìn)程首先把并行計(jì)算需要的參數(shù)和輸入圖像都拷貝到共享內(nèi)存空間，然后啟動(dòng)MPI進(jìn)程進(jìn)行并行計(jì)算，MPI進(jìn)程計(jì)算完畢后仍然把計(jì)算結(jié)果圖像拷貝到這段共享內(nèi)存，主程序讀取共享內(nèi)存后將其釋放。通過(guò)這個(gè)過(guò)程完成了算法的MPI并行計(jì)算。

Windows提供了程序調(diào)用命令，可以在一個(gè)進(jìn)程中創(chuàng)建另一個(gè)進(jìn)程。程序調(diào)用命令為：int system（ const char *command ），其中command即為要調(diào)用的程序及參數(shù)。在軟件系統(tǒng)中編制程序代碼啟動(dòng)MPI命令，調(diào)用并行計(jì)算命令，啟動(dòng)并行程序。EM算法的MPI并行程序名稱(chēng)設(shè)為EMRec_MPI.exe，該文件和應(yīng)用程序存放在一個(gè)目錄下，用GetModuleFileName命令獲得當(dāng)前應(yīng)用程序所在路徑，即可得到并行程序所在路徑。在mpirun命令中，使用了-np與-localroot參數(shù)。變量nodeNum指定參與并行計(jì)算節(jié)點(diǎn)的數(shù)目，該變量由用戶(hù)通過(guò)校正軟件人機(jī)交互界面設(shè)置?，F(xiàn)使用默認(rèn)節(jié)點(diǎn)設(shè)置，參與計(jì)算的節(jié)點(diǎn)在圖像校正軟件系統(tǒng)啟動(dòng)之前配置完成。

圖像復(fù)原軟件系統(tǒng)主程序進(jìn)程和圖像恢復(fù)并行計(jì)算程序進(jìn)程是兩個(gè)獨(dú)立的進(jìn)程，各個(gè)進(jìn)程的存儲(chǔ)區(qū)獨(dú)立，進(jìn)程和進(jìn)程之間不能直接通過(guò)變量或內(nèi)存地址的方式傳遞數(shù)據(jù)。用共享內(nèi)存文件映射的方法實(shí)現(xiàn)主進(jìn)程和并行計(jì)算進(jìn)程間的數(shù)據(jù)傳遞。共享內(nèi)存文件由某一個(gè)進(jìn)程創(chuàng)建，該文件映射對(duì)象的內(nèi)容能夠?yàn)槎鄠€(gè)其它進(jìn)程所映射，這些進(jìn)程共享的是物理存儲(chǔ)器的同一個(gè)頁(yè)面。因此，當(dāng)一個(gè)進(jìn)程將數(shù)據(jù)寫(xiě)入此共享文件映射對(duì)象的內(nèi)容時(shí)，其它進(jìn)程可以立即獲取數(shù)據(jù)變更情況。

首先，主進(jìn)程通過(guò)CreateFileMapping（）函數(shù)創(chuàng)建一個(gè)內(nèi)存映射文件對(duì)象，并把該文件對(duì)象命名為EM_rec_mem，在并行計(jì)算進(jìn)程中，即可通過(guò)這個(gè)名字找到該內(nèi)存文件。如果創(chuàng)建成功，則通過(guò)MapViewOfFile（）函數(shù)將此文件映射對(duì)象的視圖映射到地址空間，同時(shí)得到此映射視圖的首地址。首先，計(jì)算需要?jiǎng)?chuàng)建的內(nèi)存文件大小。其中40個(gè)為頭信息，并保存算法的輸入?yún)?shù)等信息。內(nèi)存文件創(chuàng)建成功以后，把輸入數(shù)據(jù)，包括圖像恢復(fù)參數(shù)、輸入圖像幀數(shù)，擴(kuò)展函數(shù)行、列數(shù)，迭代次數(shù)、多幀輸入圖像數(shù)據(jù)等，寫(xiě)入共享文件內(nèi)存。完成了初始化工作，即可調(diào)用并行計(jì)算程序。并行計(jì)算進(jìn)程由mpirun命令啟動(dòng)以后，首先用CreateFileMapping（）函數(shù)創(chuàng)建一個(gè)名稱(chēng)為EM_rec_mem的內(nèi)存文件，然后獲得輸入數(shù)據(jù)，并把輸入數(shù)據(jù)用MPI_Bcast的方法廣播到各個(gè)計(jì)算節(jié)點(diǎn)上的進(jìn)程，開(kāi)始并行計(jì)算。并行計(jì)算完成后把處理結(jié)果寫(xiě)入共享內(nèi)存文件，完成算法的MPI并行計(jì)算。

3實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)以空間域按行分片復(fù)原算法為基礎(chǔ)，引入并行計(jì)算，用VC6.0編程進(jìn)行實(shí)現(xiàn)。將并行系統(tǒng)校正方法在計(jì)算機(jī)并行集群系統(tǒng)（微機(jī)主要配置均為CPU Intel Pentium IV，2.66 GHz，1024 MB內(nèi)存）上運(yùn)行。以紅外直升機(jī)目標(biāo)圖像的并行集群校正為例，下面給出在該并行集群系統(tǒng)運(yùn)行通過(guò)的兩個(gè)并行校正實(shí)驗(yàn)結(jié)果。3幀退化圖像如圖3所示，為便于對(duì)比，分別采用1～8個(gè)節(jié)點(diǎn)進(jìn)行并行復(fù)原校正，其中迭代次數(shù)均為80次。不同節(jié)點(diǎn)復(fù)原圖像如圖4所示，當(dāng)節(jié)點(diǎn)數(shù)設(shè)置不同時(shí)，由從輸入相同的模糊圖像中復(fù)原出來(lái)的結(jié)果圖像相同，說(shuō)明各個(gè)節(jié)點(diǎn)并不改變算法參數(shù)和圖像數(shù)據(jù)，只參與并行計(jì)算，以提高計(jì)算效率。不同節(jié)點(diǎn)數(shù)耗費(fèi)時(shí)間對(duì)比見(jiàn)表2。由表2可知，隨著節(jié)點(diǎn)數(shù)增加，計(jì)算耗時(shí)幾乎成比例地減少，這是由于各個(gè)節(jié)點(diǎn)平均分擔(dān)了計(jì)算任務(wù)。不同節(jié)點(diǎn)數(shù)并行運(yùn)算的時(shí)空?qǐng)D如圖5所示，其中橫向細(xì)實(shí)線(xiàn)寬度表示計(jì)算所用時(shí)間，橫向塊寬度表示數(shù)據(jù)傳輸及廣播所用時(shí)間。分析時(shí)空?qǐng)D可知，節(jié)點(diǎn)之間數(shù)據(jù)通信所耗費(fèi)的時(shí)間相對(duì)于整個(gè)計(jì)算時(shí)間較短。但隨著節(jié)點(diǎn)數(shù)目增加，通信量增多，數(shù)據(jù)通信耗費(fèi)時(shí)間增加。因此，節(jié)點(diǎn)數(shù)并不是越多越好，當(dāng)節(jié)點(diǎn)數(shù)目達(dá)到一定數(shù)量（8節(jié)點(diǎn)）時(shí)，復(fù)原算法耗費(fèi)時(shí)間將達(dá)到穩(wěn)定。

4結(jié)語(yǔ)

針對(duì)圖像校正算法迭代次數(shù)多、耗時(shí)長(zhǎng)等問(wèn)題，為提高計(jì)算效率，本文引入了并行集群計(jì)算。對(duì)復(fù)原校正算法的結(jié)構(gòu)與流程進(jìn)行了研究，提出了整體數(shù)據(jù)傳輸、按行分片計(jì)算復(fù)原的并行處理方法，有效解決了校正算法的并行集群處理問(wèn)題。并行集群實(shí)驗(yàn)計(jì)算結(jié)果表明，本文提出的并行方法十分有效，可縮短計(jì)算時(shí)間，提高計(jì)算效率。通過(guò)研究了解圖像處理算法MPI并行化方法，實(shí)現(xiàn)了基于MPI的并行計(jì)算集群，解決了MPI并行程序與Windows窗口的集成連接問(wèn)題，建立了一個(gè)并行計(jì)算圖像校正軟件平臺(tái)。由此證實(shí)MPI并行計(jì)算在氣動(dòng)光學(xué)效應(yīng)圖像校正處理中具有實(shí)用價(jià)值。

參考文獻(xiàn)參考文獻(xiàn)：

[1]張?zhí)煨?，洪漢玉，張新宇.氣動(dòng)光學(xué)效應(yīng)校正[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2013.

[2]洪漢玉，張?zhí)煨?，余?guó)亮.航天湍流退化圖像的極大似然估計(jì)規(guī)整化復(fù)原算法[J].紅外與毫米波學(xué)報(bào)，2005，24（2）：130134.

[3]洪漢玉，張?zhí)煨?，余?guó)亮.基于Poisson模型的湍流退化圖像多幀迭代復(fù)原算法[J].宇航學(xué)報(bào)，2004，25（6）：649654.

[4]洪漢玉，王進(jìn)，張?zhí)煨?，?紅外目標(biāo)圖像循環(huán)迭代復(fù)原算法的加速技術(shù)研究[J].紅外與毫米波學(xué)報(bào)，2008，27（1）：433436.

[5]都志輝.高性能計(jì)算之并行編程技術(shù)—MPI并行程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，2001.

[6]J G NAGY，R J PLEMMONS，T C TORGERSEN.Iterative image RESToration using approximate inverse preconditioning[J].IEEE Trans.on Image Processing，1996，5（7）：11511162

[7]呂捷.并行與分布式圖像處理系統(tǒng)的實(shí)現(xiàn)與應(yīng)用[D].武漢：華中科技大學(xué)，2004.

責(zé)任編輯（責(zé)任編輯：黃?。?