FPGA加速三維CT圖像重建*

鄧靖飛，李建新，李 磊，閆 鑌

（解放軍信息工程大學，河南 鄭州 450002）

FPGA加速三維CT圖像重建*

鄧靖飛，李建新，李 磊，閆 鑌

（解放軍信息工程大學，河南 鄭州 450002）

針對三維圖像重建的經典算法（FDK算法）在FPGA上的加速，提出了并行無等待流水線的實現方法。實驗結果表明，該方法獲得了較高的加速比。

FPGA；CT重建；FDK；流水線

計算機斷層成像技術CT（Computed Tomography）作為一種新型的成像方式已經被廣泛應用于醫(yī)學、工業(yè)等領域。三維CT相對于傳統(tǒng)二維CT有空間分辨率高，各向同性的優(yōu)勢[1]。但是由于三維圖像重建運算量大，重建時間長的問題已成為制約其走向實用的瓶頸。

目前，重建加速研究主要集中在通過改進算法的軟件加速及利用GPU、FPGA進行的硬件加速。其中，FPGA由于具有極佳的并行計算能力及可重構可定制的特點[2]，利用FPGA實現CT重建加速正逐漸引起研究人員的注意。

2002年 Miriam Leeser[3]首次利用 FPGA對二維 CT重建進行了加速，重建規(guī)模為 512^2時需要3.6 s。2003年 Iain Goddard[4]首次對三維 CT重建 FDK算法中的反投影過程用FPGA實現加速，重建規(guī)模為512^3時，反投影過程需要 38.7 s；2008年 Benno Heigl[5]用 9塊 FPGA協(xié)調配合完成了FDK算法中濾波及反投影部分的加速，重建規(guī)模為512^3時，該過程共需要9 s。2009年Nikhil Subramanian[6]利用FPGA作為協(xié)處理器用Impulse c語言開發(fā)實現了二維CT重建過程的加速，重建規(guī)模為512^2時，反投影過程需要38.4 ms。

在FPGA內實現硬件加速是通過全數據流的形式處理，脫離了指令的操作。為了充分利用FPGA的片內資源以獲得更高的加速效果，本文設計了一種并行無等待流水線的處理結構，同時對核心算法電路進行資源優(yōu)化，在保持高度并行性的同時保證了較高的資源利用率。

1 FDK算法

FDK算法作為一種經典的三維CT重建算法是由Feldkamp等人于 1984年針對錐束成像圓形掃描軌跡提出的。該算法作為近似算法的代表具有良好的重建效果以及極佳的并行性，適用于FPGA并行加速的原理。FDK投影幾何意義如圖1所示。S表示射線源，f（x，y，z）表示重建物體的某一點，P（θ，u，v）表示在物體旋轉 θ角度時探測器采集到的投影數據。

FDK算法可以分為以下步驟[7]：

（1）對投影數據進行加權，修正由于錐束光源角度引起的誤差。

其中D表示光源到探測器的距離。

（2）對加權后的投影數據按行進行濾波。

其中g（a）為Ramp濾波函數。

（3）將濾波后的投影數據反投影到重建物體上。

在FDK算法中，反投影的計算復雜度與時間消耗都是最大的，是制約重建速度的瓶頸所在，因此本文研究在FPGA內實現反投影部分的加速方法。

2 FPGA反投影加速實現

反投影過程需要對重建物體旋轉一周所采集到的數據進行處理。實際情況中采集數據的過程是離散的，且每一個分度下投影數據的處理過程不相關?；谶@種可并行性，用FPGA加速的思路是并行計算反投影過程，并且在保證每一個反投影單元速度最快時并行盡可能多的反投影單元。

2.1 無等待流水線的設計

重建物體體素的反投影流程有3個步驟。首先根據圖1的幾何關系定位出重建體素在探測器上的位置；然后從存儲器中讀取相應數據；最后對所讀取數據進行雙線性插值。

通過流水線設計，雙線性插值部分可以在每一個時鐘更新一個數據，但是每更新一個數據需要從數據存儲空間讀取4個數據來計算，如果花費4個時鐘周期來讀取這4個數據，就會造成前級數據讀取時間大于后級雙線性插值時間，雙線性插值處理單元會產生空泡?？张莸漠a生，不但制約了后級處理單元的計算速度，也造成FPGA內資源利用率的降低。

為了解決上述問題，提高處理速度以及資源利用率，分析雙線性插值過程所讀取4個數據之間的關系，如圖2所示。

X、Y分別代表探測器垂直的兩個方向，F（X0，Y0）為重建目標點在探測器上投影位置，A（Xn，Yn），B（Xn+1，Yn），C（Xn，Yn+1），D（Xn+1，Yn+1）為探測器上與之相鄰最近的 4個有效區(qū)域，有效區(qū)域的大小即為探測器分辨率的大小，雙線性插值過程為：

其中x=X0-Xn，y=Y0-Yn+1，A、B、C、D四個點是探測器上相鄰兩行上相鄰兩列的數據。針對這種相關性，在FPGA內部設計一種雙組奇偶雙口RAM結構，如圖3所示。

圖3中兩組共四個存儲空間均為FPGA片內設計的雙口RAM。通過數據預取技術以及兩組RAM之間的乒乓操作避免了雙線性插值時隨機訪問外部存儲器帶來的延遲。在反投影處理中，第一組RAM處于數據寫入過程時，分別向該組兩塊RAM寫入探測器上奇數行數據與偶數行數據。同時另一組RAM中的數據進行雙線性插值。計算完成后，兩組RAM進行讀寫狀態(tài)的互換，完成一次乒乓循環(huán)。在投影尋址單元中，計算出A（Xn，Yn）的縱坐標Yn，對其奇偶性進行判斷，當其為奇數時，從兩塊RAM中所取數據與地址分別為：

當Yn為偶數時，從兩塊RAM中所取數據與地址分別為：

其中：width代表探測器的寬度，addrA、addrB、addrC、addrD分別代表A（Xn，Yn）、B（Xn+1，Yn）、C（Xn，Yn+1）、D（Xn+1，Yn+1）四個數據在相應 RAM內的存儲地址。

通過這種雙組奇偶雙口RAM緩存結構的設計在不增加片內存儲資源消耗的前提下一個時鐘周期內取出四個數據，消除了空泡，實現了無等待流水線，在一個時鐘周期內可更新一個重建點的結果。

單條反投影流水線設計原理如圖4所示。圖中總體邏輯與時序控制模塊通過狀態(tài)機實現對流水線的控制；緩存寫入控制單元對投影數據的寫入操作進行判斷與控制；重建點生成器產生重建點坐標，并根據此坐標由讀地址生成器計算雙線性插值數據的地址，同時通過查表找出空間系數sinθ與cosθ；循環(huán)累加控制器完成對各分度下反投影結果的歸約過程。

2.2并行流水線處理結構

基于各個分度下反投影過程的不相關性，在FPGA內設計一種基于分度的并行流水線處理結構，如圖5所示。數據控制接口以及時序狀態(tài)控制模塊完成對輸入數據的分配調度，通過多條反投影流水線并行計算后，由循環(huán)歸約單元完成反投影結果的歸約。

為了盡量增加N的值，對單條流水線做優(yōu)化來降低其所占的資源量。在XC5VLX330內實現一個32 bit的除法要占用約4%的邏輯資源，因此需要盡量避免除法運算。在反投影過程中有3次除法，分別為：

其中：υ為重建區(qū)域單元尺寸，τ為探測器單元尺寸。這三個除法運算在時間上是順序執(zhí)行的，前兩個運算用于投影點位置的計算，第三個運算用于雙線性插值。為了降低這三個運算在FPGA內的資源占有量，提取出三個式子的公因式：

在FPGA內設計時，預先算出該公因式的值，然后通過移位寄存的方法進行延遲同步，使之在相應的節(jié)拍打入到指定的計算單元。雖然這樣增加了乘法運算，但是將三次除法運算優(yōu)化為一次，節(jié)省了大量的資源。表1給出了優(yōu)化前后資源占有情況對比。

表1優(yōu)化前后資源比較

Block Ram/kbits乘法計算量除法計算量Number of slices LUTs Number of Flip Flops Number of occupied slices可并行流水線數量優(yōu)化前1 620 15 3 11 468 19 806 5 560 7優(yōu)化后1 656 19 1 7 516 10 347 2 985 14對比增加2.2%增加26.7%減少66.7%減少34.5%減少47.8%減少46.3%增加100%

通過優(yōu)化，在XC5VLX330 FPGA內部可以并行14條反投影流水線，相比優(yōu)化以前，流水線數增加1倍。

3 實驗結果與分析

通過編寫Verilog語言程序，在XC5VLX330 FPGA上進行綜合仿真，采取14條并行反投影流水線對Shepp-Logan標準體模進行重建，得到圖6所示結果。

圖6（a）為CPU重建圖像的一個切片，圖6（b）為FPGA加速重建的圖像切片，圖 6（c），圖 6（d）分別為圖 6（a），圖 6（b）切片圖像中心橫線的統(tǒng)計圖，從圖中可以看出FPGA加速重建結果的精度達到要求。表2給出FPGA與CPU對不同規(guī)模數據進行重建時速度對比，計算機CPU為Inter Xeon E5430 2.66 GB，內存為16 GB。

可以看出，通過FPGA加速FDK算法中的反投影過程加速比達到了115，具有顯著效果。獲得加速比的原因由FPGA的體系結構所決定，其基于數據流的處理方式脫離了指令的操作，保證每一個時鐘周期都是用來計算。當采取多條流水線并行處理時，加速比進一步提高，加速比與在FPGA內并行流水線數目成正比。

表2重建不同規(guī)模物體時FPGA與CPU速度對比

重建規(guī)模128^3×360 256^3×360 512^3×360 CPU 41 s 330 s 2 656 s FPGA 0.36 s 2.87 s 23.1 s加速比114 115 115

本文在FPGA上實現了對三維CT重建過程的加速。針對FDK算法中計算復雜度最高的反投影過程，通過雙組奇偶雙口RAM的緩存結構實現了無等待流水線，達到每一個時鐘周期可更新一個重建點的速度。另外通過優(yōu)化電路設計降低了單條流水線的資源占有率，在XC5VLX330上實現了14條流水線的并行處理，在保證重建圖像質量的同時，取得了115倍的加速比。在利用FPGA實現CT重建加速時，影響加速效果的主要因素是FPGA內部資源利用率以及數據傳輸效率，隨著未來FPGA以及存儲器技術的發(fā)展，FPGA可以實現更快的CT重建速度。

[1]包尚聯.現代醫(yī)學影像物理學[M].北京：北京大學醫(yī)學出版社，2003.

[2]劉佳，焦斌亮.FPGA的發(fā)展趨勢及其新應用[J].電子技術，2008（4）.

[3]LEESER M.Parallel-beam backprojection：an FPGA implementation optimized for medical imaging[J].Proc of the Tenth Int.Symposium on FPGA.2002（2）：217-226.

[4]GODDARD I.High-speed cone-beam reconstruction：an embedded systems approach[J].Proceedings of SPIE，2003：483-491.

[5]Benno Heig.High-speed reconstruction for C-arm computed tomography[C].Proceedings of the 9th International Meeting on Fully Three-Dimensional Image Reconstruction in Radiology and Nuclear Medicine.2008：25-28.

[6]Nikhil Subramanian.A C-to-FPGA solution for accelerating tomographic reconstruction[D].University of Washington，2009.

[7]張劍，陳志強.三維錐形束 CT成像 FDK重建算法發(fā)展綜述[J].中國體視學與圖像分析，2005（2）：116-121.

FPGA accelerate 3D CT reconstruction

DENG Jing Fei，LI Jian Xin，LI Lei，YAN Bin
（The PLA Information Engineering University,Zhengzhou 450002，China）

：In this paper,the acceleration of the classic three-dimensional reconstruction FDK algorithm based on FPGA is researched.The method of parallel no-wait pipelines is proposed.The experimental results show that the method obtains a higher speedup.

FPGA；CT reconstruction；FDK；pipeline

TP391

A

0258-7998（2010）09-0050-04

國家 863計劃重點項目（2009AA012201）

2010-03-15）

鄧靖飛，男，1985年生，碩士生，主要研究方向：CT成像技術與應用。

閆鑌，男，1976年生，副教授，主要研究方向：X射線成像及三維圖像處理。