[發明專利]一種CT切片數據可視化重構的八叉樹并行構造方法

有效

• 申請號: 201611062125.2
• 申請日: 2016-11-25
• 公開（公告）號: CN106846457B
• 公開（公告）日: 2020-05-26
• 發明（設計）人: 夏梓峻;孟祥飛;朱小謙;王文珂;馮景華;李菲菲;溫佺;孫華文;郭佳
• 申請（專利權）人: 國家超級計算天津中心
• 主分類號: G06T17/00
• 分類號: G06T17/00;G06T1/20;G06T1/60
• 代理公司: 北京鍾維聯合知識產權代理有限公司 11579
• 代理人: 黃利萍

1.一種CT切片數據可視化重構的八叉樹并行構造方法，其具備TB級數據規模處理能力，其特征在于，該方法包括以下步驟：

A、按照CT切片數據組合而成的原始體數據尺寸X、Y和Z，樹節點設定尺寸為x、y和z，計算獲得X方向、Y方向和Z方向的剖分網格數目N_X、N_Y和N_Z，得到體數據的剖分網格數目N＝N_X*N_Y*N_Z，按照該數目構造一份線性滿八叉樹的索引列表，剖分網格即代表八叉樹的葉子節點；

B、完成索引列表各個屬性字段填充，包括八叉樹屬性字段和樹節點屬性字段，按照按需構造-BONOs原則，根據實際存在的體數據進行劃分：若節點內包含實際存在的體數據，則該節點被標識為存在，若節點只包含擴充的體數據，則該節點被標識為不存在；

C、根據原始體數據尺寸X、Y和Z，以及設定的節點分辨率尺寸x、y和z，進行體數據預取操作，將Z方向的z個CT切片數據文件預取至所有計算節點內存中；

D、將預取至內存的體數據子塊，即其三維尺寸為X、Y和Z的體數據子塊，在XOY平面進行X和Y方向進行等分，X方向劃分，Y方向劃分，將該體數據塊劃分為(X/x)*(Y/y)個葉子節點；

E、基于MPI+OpenMP編程模型，執行葉子節點數據并行轉換操作，由P_N個MPI進程將N個葉子節點進行并行轉換，每個進程內部啟動OpenMP多線程完成數據重排，使得切片文件數據轉換為八叉樹葉子節點數據格式，并存儲為自定義二進制文件，將該轉換操作迭代執行多次，完成整個體數據由CT切片數據格式向葉子節點二進制數據格式的轉換操作；

F、根據線性滿八叉樹索引列表屬性信息和MPI+OpenMP編程模型，從葉子節點所在層位開始進行自底向上八叉樹并行構造，逐層向上合并構造中間節點，并將構造結果存儲為自定義文件，存儲路徑保存至索引表中；

G、完成整棵八叉樹構造，獲得線性滿八叉樹索引列表和八叉樹節點數據文件，滿足體數據三維可視化重構目的。

2.根據權利要求1所述的CT切片數據可視化重構的八叉樹并行構造方法，其特征在于，索引列表內包括以下信息：

a.體數據三維尺寸，即擬處理體數據的實際三維大小X、Y和Z；

b.節點三維尺寸，是BONOs樹節點表示的體數據三維大小x、y和z；

c.實際節點數，是當前BONOs樹的節點個數，包括根節點、中間節點和葉子節點；

d.八叉樹深度，指當前BONOs樹的深度；

e.是否BONO樹：標識當前八叉樹是否為BONO樹；

f.是否壓縮：標識當前八叉樹存儲前是否經過壓縮；

g.線性八叉樹地址向量，滿線性八叉樹，包括：

①節點標識：根據BONOs算法，若該樹節點實際存在，則為真，否則為假；

②樹節點坐標：樹節點的三維坐標x1，y1和z1；

③節點Morton編碼：節點的Morton編碼；

④節點實際內存地址：節點數據所在的實際內存地址；

⑤節點鄰域索引：標識出子節點相鄰的其余體數據索引下標，包括面鄰域、邊鄰域和角鄰域，共27個；

⑥文件存儲絕對路徑：表示當前節點的文件存儲路徑。

3.根據權利要求1所述的CT切片數據可視化重構的八叉樹并行構造方法，其特征在于，所述步驟C中，體數據子塊數據預取操作步驟為：

a.按照節點尺寸x、y和z，以及切片數據大小，申請動態內存空間，等待數據緩存至內存；

b.按照OZ坐標軸方向將z個切片數據讀取至節點內存；

c.根據體數據Z方向尺寸Z和樹節點Z方向尺寸z，計算迭代次數K，其中K表示該數據預取過程將持續K次，K＝┌Z/z┐。

4.根據權利要求1所述的CT切片數據可視化重構的八叉樹并行構造方法，其特征在于，所述步驟D中，葉子節點網絡并行劃分的操作步驟為：

a.按照MPI并行規模P_N，對本次葉子節點網格數N進行平均劃分；

b.每一個進程P，確定擬處理的葉子節點個數和節點編號，確保所有節點能夠被處理；

c.根據擬處理葉子節點數目，申請動態內存空間，分配待處理數據緩存區域。