基于Census變換的立體匹配算法優(yōu)化及醫(yī)學影像應用*

方純潔，賴小波，石 磊

浙江中醫(yī)藥大學醫(yī)學技術(shù)學院 杭州 310053

基于Census變換的立體匹配算法優(yōu)化及醫(yī)學影像應用*

方純潔，賴小波#，石 磊

浙江中醫(yī)藥大學醫(yī)學技術(shù)學院 杭州 310053

#通信作者，男，1981年6月生，博士，副教授，研究方向：醫(yī)學圖像處理，E-mail：shopo@zcmu.edu.cn

立體匹配；Census非參數(shù)變換；快速實現(xiàn)；醫(yī)學影像應用

目的：建立并優(yōu)化一種基于Census非參數(shù)變換的立體匹配算法。方法：詳細分析了基于Census非參數(shù)變換的立體匹配，運用移動窗口技術(shù)和高速緩存，采用SSE2指令進行數(shù)據(jù)流的并行處理從而優(yōu)化算法結(jié)構(gòu)，縮短取指時間，提高計算效率。用Middlebury標準圖像對對該算法進行驗證，并用于臨床陰道鏡子宮頸圖像對的立體匹配。結(jié)果：快速實現(xiàn)了對Middlebury標準圖像對以及子宮頸圖像對的立體匹配。結(jié)論：該算法能夠有效提高立體匹配的實時性，可應用于外科手術(shù)導航等計算機輔助外科診療系統(tǒng)。

雙目立體視覺是計算機視覺的一個重要分支，由不同位置的兩臺攝像機或者一臺攝像機經(jīng)過移動和旋轉(zhuǎn)對同一場景進行拍攝，再計算空間點在圖像中對應點的視差，然后經(jīng)過一系列投影逆變換，最后獲得該空間點的三維坐標。與其他諸如透鏡板三維成像、全息照相術(shù)等獲取立體視覺的方法相比，雙目立體視覺直接模擬人類雙眼處理場景圖像的方式，可靠簡便，已經(jīng)廣泛應用于機器人導航和3D遠程會議等領(lǐng)域。立體匹配是雙目立體視覺中最核心、最重要的一個步驟，主要解決場景中同一空間點在參考圖像上的投影點如何在匹配圖像上匹配到其對應點的問題。目前研究人員已經(jīng)提出了一些快速立體匹配算法[1]。其中一種方式是采用盒濾波法[2]，一般采用零均值歸一化(ZNCC)或絕對差總和(SAD)等簡單的互相關(guān)方法進行立體匹配[3-4]，匹配性能不會受匹配窗口尺寸的影響。文獻[5]對基于互相關(guān)的立體匹配算法進行了改進，并在兩種不同的硬件配置系統(tǒng)中進行了實驗，能夠?qū)崟r得到移動機器人周圍環(huán)境的視差圖。Wang等[6]在動態(tài)規(guī)劃(dynamic programming, DP)[7]算法架構(gòu)中引入垂直方向的自適應匹配代價聚合步驟，可以在保證實時性的前提下獲得高質(zhì)量的視差圖；但此算法存在的主要問題是不能有效融合水平與垂直方向上的連續(xù)性約束，導致視差圖帶有明顯的條紋狀瑕疵。Felzenszwalb等[8]采用分層匹配的策略有效降低了基于置信度傳播(belief propagation, BP)[9]的立體匹配算法的復雜度；但是此算法完成一幅320×288像素的立體匹配用時需要1 s左右，難以達到實時性的要求。因此，如何在算法的執(zhí)行時間與立體匹配質(zhì)量之間進行權(quán)衡取舍是一項艱巨的任務。Census變換是一種非參數(shù)局部變換，由Zabih和Woodfill提出并最早應用于立體匹配[10]。作者提出了一種基于Census變換的立體匹配快速實現(xiàn)算法并進行了圖像驗證，報道如下。

1 材料與方法

1.1 材料 研究所使用的實際場景圖像對來自Middlebury網(wǎng)站，該網(wǎng)站是Middlebury大學提供的一個權(quán)威的立體匹配算法測試平臺，可以對算法的性能進行綜合評估；標準圖像對來自Middlebury圖片庫，用來檢驗算法，這些圖片是在各種不同的環(huán)境下拍攝，外極線均已校正，并提供了標準視差圖；子宮頸圖像對來自中國科學院深圳先進技術(shù)研究院生物醫(yī)學與健康工程研究所。全部計算在Intel Pentium Ⅳ 2.4 GHz、2.0 G內(nèi)存的普通計算機上采用Visual Basic C++ 6.0編程實現(xiàn)。

1.2 算法結(jié)構(gòu) 基于Census變換的立體匹配算法流程圖如圖1所示。圖中第1個模塊是為了在同一時間獲取參數(shù)相同的圖像對，通常情況下一個折射系統(tǒng)能夠很容易滿足此要求。第2個模塊是為了校正由于鏡頭畸變而引起的圖像失真，校正之后可以使用水平極線約束，使輸入圖像的每一行都與基線平行。在進行極線校正之前，左、右攝像機需進行離線標定。若使用基于Census變換的相似性測度函數(shù)，則第3個模塊用于計算圖像中每個像素的Census比特串。第4個模塊用于獲得視差空間圖像，即匹配代價的計算。 第5個模塊用于獲得穩(wěn)定的匹配結(jié)果，通常采用基于窗口的互相關(guān)法進行匹配代價的聚合，最佳匹配點通過在視差搜索范圍內(nèi)采用優(yōu)勝全選(winner-take-all,WTA)策略獲得。基于窗口的互相關(guān)匹配代價聚合假設(shè)窗口內(nèi)所有像素點的視差連續(xù)，窗口大小可以根據(jù)實際情況調(diào)整。為了濾除視差圖中由于誤匹配以及遮擋引起的不可靠匹配點，引入第6個模塊，進行左右一致性檢測。第7個模塊是視差圖的后處理模塊，根據(jù)需要可選，目的在于進一步提高視差圖的質(zhì)量，獲得亞像素級別的視差圖。

圖1 Census變換立體匹配算法流程圖

1.3 算法結(jié)構(gòu)的改進 為了提高立體匹配的實時性，作者提出了一種基于Census非參數(shù)變換的立體匹配快速實現(xiàn)算法。假設(shè)在進行立體匹配之前，左、右圖像均已經(jīng)過預處理和極線校正。在匹配代價的聚合步驟中，采用基于局部矩形窗口的WTA策略對左右匹配窗口的Hamming距離分別進行運算。若直接進行Hamming距離的求和運算，由于在每一個步驟中，每個像素的灰度值都必須計算一次，因此具有較大的計算復雜度。移動窗口技術(shù)[11]可以消除重復計算，提高計算效率。如圖2所示，通過移動窗口技術(shù)將匹配窗口內(nèi)Hamming距離的求和分解為按列和按行的Hamming距離求和。具體步驟如下。步驟1：通過計算獲得初次的行像素Hamming距離的和，并儲存在計算機的一級緩存區(qū)中。步驟2：后一行像素Hamming距離的和通過已知的前一行像素Hamming距離的和加上后一個像素的Hamming距離同時減去前一行(列)第一個像素的Hamming距離得到。列像素Hamming距離的和用同樣的方式獲得。一旦行、列像素Hamming距離和的初始值算出，那么后一行、列像素Hamming距離和的計算復雜度是固定的，即兩次加法運算和兩次減法運算。因此，假設(shè)匹配窗口大小為n×n，那么計算復雜度從n降為次數(shù)固定的加法運算和減法運算，計算復雜度與窗口尺寸無關(guān)[12]。

圖2 移動窗口技術(shù)

1.4 存儲器組織的優(yōu)化 針對立體匹配應用，通常有3種存儲器組織方式可供選擇。其中，x、y分別為像素點的橫坐標和縱坐標，d為視差搜索范圍。

在圖3方式1中，像素點縱坐標y變化最快，其次為像素點橫坐標x，最后才是視差搜索范圍d。視差搜索范圍d每改變一次，系統(tǒng)都需要重新讀取左、右圖像的數(shù)據(jù)。對于分辨率較高的圖像，存取圖像會消耗大量的時間。同樣的，在方式2中，像素點縱坐標y變化最快，其次為視差搜索范圍d，最后才是像素點橫坐標x。在遍歷不同視差值d時也存在與方式1同樣的問題。在方式3中，視差搜索范圍d變化最快，其次為像素點縱坐標y，最后才是像素點橫坐標x。此時在遍歷不同視差值d時，只需讀取一次該像素的值，由于該像素值可以存放在緩存區(qū)，可大大減少訪問系統(tǒng)內(nèi)存的時間。

1.5 SSE2并行處理指令加速 Streaming SIMD Extensions 2(SSE2)指令集是Intel公司在SSE指令集的基礎(chǔ)上發(fā)展起來的。相比于SSE，SSE2新增了144個指令，擴展了Multiple Media Extension(MMX)部分和SSE部分，這些指令提高了諸多應用程序的運行性能。隨著整數(shù)指令從64位擴展到128 位，MMX技術(shù)部分引進的單指令多數(shù)據(jù)流(single instruction multiple data, SIMD)整數(shù)類型操作的有效執(zhí)行率成倍提高。特別的，SSE2指令可讓軟件開發(fā)員極其靈活地實施算法，并在運行諸如MPEG-2、MP3、3D圖形等之類的軟件時能夠增強性能。SSE2指令集由8個128位的通用寄存器構(gòu)成，其容量是MMX寄存器的2倍。在指令處理速度保持不變的情況下，通過SSE2優(yōu)化后的應用軟件運行速度也將提高2倍。使用SSE2指令集可有效加速立體匹配的下列運算。①匹配代價的聚合：用來計算兩匹配窗口內(nèi)像素Hamming距離的和。經(jīng)過SSE2指令集加速，一次可以同時處理8個16比特的像素。具體實現(xiàn)過程如下所示：

movdqa xmm3,[src]; //將src的值賦給xmm3

movdqa xmm1,[dst]; //將dst的值賦給xmm1

addps xmm1, xmm3; //xmm1的值加上xmm3

的值，和賦值給xmm1。

②提取匹配代價最小的視差值：比較每個待匹配點的匹配代價，把匹配代價最小的視差值作為當前像素點的實際視差值。其中，匹配代價最小值的計算可以采用下列指令：

pmin disp; //獲取最小視差。

圖3 3種存儲器組織方式

1.6 實際應用 為了驗證該算法的有效性，首先采用該方法對4組Middlebury圖像庫標準圖像對Map、Teddy、Tsukuba和Cones分別進行匹配[1]，其中，圖像大小為320×240像素，匹配窗口大小為11×11像素，變換窗口大小為7×7像素。其次，對來自臨床陰道鏡的子宮頸圖像對采用該算法進行立體匹配。

2 結(jié)果

優(yōu)化前后算法執(zhí)行時間的對比情況見表1。從表1可以看出，該算法能夠有效提高立體匹配的實時性。

表1 優(yōu)化前后執(zhí)行時間對比

子宮頸圖像對視差圖如圖4所示。其中，視差搜索范圍d分別為0～16和0～32，匹配窗口大小為11×11像素，變換窗口大小為7×7像素。圖5為d=32時算法優(yōu)化前后的幀頻對比情況。從圖4和圖5可以看出，該算法即使對醫(yī)學圖像對進行立體匹配亦能獲得較高質(zhì)量的視差圖，并具有實時性。

A:左圖像;B:右圖像;C:d=16;D:d=32。圖4 子宮頸圖像對視差圖

圖5 優(yōu)化前后幀數(shù)對比

3 討論

立體匹配大體上可以分為基于局部的立體匹配和基于全局的立體匹配兩大類[13]?；诰植康牧Ⅲw匹配能夠利用對應點自身以及局部鄰域約束信息，計算效率高，在紋理豐富區(qū)域的匹配正確率較高，但是在遮擋區(qū)域或視差不連續(xù)區(qū)域易產(chǎn)生誤匹配。與其相比，基于全局的立體匹配一般能獲得精度較高的視差圖，但相應的參數(shù)設(shè)置較難，算法復雜且費時。近年來，雖然廣大的科研工作者提出了許多精度較高的立體匹配算法，但是，這些算法絕大多數(shù)是計算密集型的，若要從復雜的場景圖像中獲取可靠的三維信息，需要高端的硬件設(shè)備支持。此外，盡管立體匹配的精度是一個很重要的因素，但在實際應用中算法的實時性尤為重要。

Census變換以圖像的信號強度為基礎(chǔ)，圍繞某一特定區(qū)域內(nèi)中心像素的灰度值計算相似性測度。由于Census變換對圖像的徑向失真具有較強的魯棒性，因此在立體匹配中應用較為廣泛[14]。Census變換將變換窗口內(nèi)各鄰域像素灰度值相對于中心像素灰度值的差異轉(zhuǎn)換為0或1的一維向量形式。若變換窗口大小為n×n，那么Census變換的計算結(jié)果為n-1位的比特串，在實際應用中這種屬性能夠有效消除強噪聲或光照不均勻?qū)αⅢw匹配性能的影響。

對于一個實時的應用程序來說，存儲器的組織方式非常重要。存儲器組織方式可以分為一級緩存、二級緩存和系統(tǒng)內(nèi)存；存儲容量按順序逐漸增大，存儲速度卻按順序逐漸降低。在圖像處理應用中，由于數(shù)據(jù)量十分龐大，僅僅依靠緩存難以實現(xiàn)存儲大容量數(shù)據(jù)的需要，這時部分數(shù)據(jù)必須通過系統(tǒng)內(nèi)存進行存儲。根據(jù)文獻[14]的描述，存儲器的傳輸帶寬限制了計算機的多媒體應用，因此只有有效利用緩存，從算法結(jié)構(gòu)上減少訪問系統(tǒng)內(nèi)存的時間，才能夠?qū)崿F(xiàn)大容量數(shù)據(jù)的存儲。方式1和方式2在當前視差搜索范圍d搜索結(jié)束之前不會使用到額外載入的像素值，因此緩存命中率低；而方式3使用到了這些數(shù)據(jù)，從而提高了高速緩存的命中率。因此，在計算完Hamming距離的和之后，作者選用方式3在視差搜索范圍d內(nèi)進行Census變換立體匹配。

總之，為了克服大多數(shù)立體匹配算法計算復雜度偏高以及實時性不強的局限性，作者提出了一種基于Census變換的立體匹配快速實現(xiàn)算法。該算法運用移動窗口技術(shù)和存儲器組織優(yōu)化技術(shù)簡化計算過程，提高計算效率，最后采用SSE2多媒體增強指令并行處理加速。實驗結(jié)果表明，該優(yōu)化算法能夠有效改善立體匹配的實時性，即使對來自陰道鏡的子宮頸圖像對進行立體匹配也能夠獲得滿意的效果，可應用于外科手術(shù)導航等對實時性有較高要求的計算機輔助外科診療系統(tǒng)。如何進一步將該算法應用于醫(yī)學圖像的三維重建將是課題組今后的研究方向。

[1]CHEN W,ZHANG MJ,XIONG ZH.Fast semi-global stereo matching via extracting disparity candidates from region boundaries[J].IET Computer Vision,2011,5(2):143

[2]PARK H,MITSUMINE H,FUJII M.Fast detection of robust features by reducing the number of box filtering in SURF[J].IEICE Trans Inf Syst,2011,E94D(3):725

[3]TIPPETTS BJ,LEE DJ,ARCHIBALD JK,et al.Dense disparity real-time stereo vision algorithm for resource-limited systems[J].IEEE Transacti Circuits Systems Video Technol,2011,21(10):1547

[4]CHIANG Hsiung,LIN Ting,HOU Lun.Development of a stereo vision measurement system for a 3D three-axial pneumatic parallel mechanism robot arm[J].Sensors(Basel),2011,11(2):2257

[5]OLIVER F, THIERRY V, ERIC T, et al. Real time correlation-based stereo: algorithm, implementations and applications[R].France:INRIA, 1993.

[6]WANG L,LIAO M,GONG M,et al.High-quality real-time stereo using adaptive cost aggregation and dynamic programming:Third International Symposium on 3D Data Processing,Visualization,and Transmission,Proceedings[C].Univ North Carolina,Chapel Hill,NC:IEEE,2006:798

[7]劉赫偉,汪增福.一種沿區(qū)域邊界的動態(tài)規(guī)劃立體匹配算法[J].模式識別與人工智能,2010,23(1):38

[8]FELZENSZWALB PF,HUTTENLOCHER DP.Efficient belief propagation for early vision[J].Int J Comput Vis,2006,70(1):41

[9]SUN J,ZHENG NN,SHUM HY.Stereo matching using belief propagation[J].IEEE Trans Pattern Anal Mach Intell,2003,25(7):787

[10]ZABIH R,WOODFILL J. Non-parametric local transforms for computing visual correspondence[C].Stockholm,Swedwn:Proceedings of the Third European Conference on Computer Vision,1994: 151

[11]MüHLMANN K,MAIER D,HESSER J,et al.Calculating dense disparity maps from color stereo images, an efficient implementation[J].Int J Comput Vis,2002,47(1/3):79

[12]IBARRA-MANZANO MA,ALMANZA-OJEDA DL,DEVY M,et al.Stereo vision algorithm implementation in FPGA using census transform for effective resource optimization：Proceedings of The 2009 12th Euromicro Conference on Digital System Design,Architectures,Methods and Tools[C].Patras,Greece:IEEE,2009:799

[13]SCHARSTEIN D,SZELISKI R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J].Int J Comput Vis,2002,47(1/3):7

[14]SEBOT J,DRACH-TEMAM N. Memory bandwidth: the true bottleneck of SIMD multimedia performance on a superscalar processor[Z].LNCS,2001,2150:439

(2016-08-04收稿 責任編輯徐春燕)

Research on a fast implementation algorithm based on Census transform stereo matching and its applications in medical imaging

FANGChunjie,LAIXiaobo,SHILei

CollegeofMedicalTechnology,ZhejiangChineseMedicalUniversity,Hangzhou310053

stereo matching;Census transform; fast implementation; applications in medical imaging

Aim: To propose a fast implementation algorithm based on Census transform stereo matching.Methods: Firstly, the Census transform stereo matching was investigated, and its implementation process was analyzed in detail. Secondly, in order to simplify the calculation process and improve the computational efficiency, the moving window technique and cache were employed to optimize the algorithm structure and shorten the fetch time of the instructions. Finally, the SSE2 instructions were adopted to realize the parallel processing for the data stream, and the proposed algorithm was tested with different image pairs.Results: Fast implementation for the stereo matching with the Middlebury standard image pairs and cervical image pair was achieved.Conclusion: The proposed algorithm can effectively improve the real time of the stereo matching based on Census transform, and it can be applied to the computer-aided surgical diagnosis and treatment system such as surgical navigation.

10.13705/j.issn.1671-6825.2017.02.010

*國家自然科學基金資助項目 61602419；浙江省自然科學基金資助項目 LY16F010008，LQ16F020003；浙江省教育廳科研項目

Y201431354；浙江中醫(yī)藥大學校級課題 2012ZY18

TP751.1