基于NAM的圖像集合運算算法及其實驗研究.pdf

1、在非對稱逆布局模式表示模型(Non-symmetry Anti-packing Pattern RepresentationModel，NAM)的基礎(chǔ)上，提出了一種實現(xiàn)快速的圖像集合運算的新方法，即在導(dǎo)航數(shù)組(Navigation Array，NA)輔助下的分裂組合法(Split and Combination Method，SCM)，并實現(xiàn)了基于NAM 表示的交運算、差運算、并運算和補(bǔ)運算算法，取得了一些有價值的研究成果。 為了

2、解決基于NAM 操作的塊間位置關(guān)系問題，提出了一種新的輔助性措施，即導(dǎo)航數(shù)組。這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)起來簡單方便，可以使分散的塊間關(guān)系重新恢復(fù)，因此可以在需要確定位置關(guān)系的算法中使用，如近鄰尋找、周長計算、連通分量標(biāo)記等算法中都可以使用這種結(jié)構(gòu)來進(jìn)行導(dǎo)航，快速找到相鄰或有是相交的塊，在本課題實現(xiàn)中取得了較好的效果。 在研究基于NAM的圖像集合運算問題中，提出了一種新的實現(xiàn)快速無重疊的圖像集合運算算法，即分裂組合法。這種算法基于分裂的思

3、想，在不斷地分裂過程中，將所需要的部分保留下來，形成集合運算最終的結(jié)果。當(dāng)然，這種運算還有另外一個好處，就是使得集合運算的實現(xiàn)具有很大的相似性，讓程序結(jié)構(gòu)更加清晰明了。 為了與本課題的實驗結(jié)果進(jìn)行比較，還實現(xiàn)了線性四元樹的編碼解碼算法以及基于緊湊四元樹（Compact Improved Quadtree，Compact-IQ）的編碼、解碼和集合運算算法。在對給定的8 幅二值圖像的實驗中，首先比較了基于NAM 表示的結(jié)點數(shù)比線性四元

4、樹和緊湊四元樹壓縮了2.914和1.775 倍，在與緊湊四元樹的集合運算效率的比較中，基于NAM的集合運算算法普遍比基于緊湊四元樹的集合運算算法運行效率要高，從加速比中表現(xiàn)得相當(dāng)明顯，關(guān)于交、差、并、補(bǔ)運算的平均加速比為1.877、4.034、2.140、2.892，實驗證明，基于NAM 表示的集合運算算法比基于緊湊四元樹的集合算法的效率更高。 理論分析和實驗結(jié)果表明，導(dǎo)航數(shù)組輔助下的分裂組合法是一種有效解決基于NAM 集合運算