幾何操作中重采樣問題數(shù)據(jù)并行實現(xiàn)

摘 要:幾何操作是計算機圖形和計算機視覺的基本操作之一。如何快速、實時地實現(xiàn)幾何操作，是現(xiàn)代媒體應(yīng)用中的主要問題。重采樣操作是圖像處理中非常關(guān)鍵的全局操作，一般是通過串行處理方法予以解決。在SIMD處理元陣列上進行數(shù)據(jù)并行處理幾乎是空白，為了滿足對圖像進行實時處理的需要，提出幾何操作中重采樣操作的數(shù)據(jù)并行實現(xiàn)方法，并對結(jié)論進行了論證。通過SIMD PE陣列之間的數(shù)據(jù)并行傳送，實現(xiàn)了重采樣，從而使實現(xiàn)重采樣的復(fù)雜度由存儲器數(shù)據(jù)流訪問實現(xiàn)方法的Ο(MN)降低到Ο(M+N)，大大提高了處理速度，能更好地滿足圖像快速實時處理的需要。

關(guān)鍵詞: 幾何操作; 重采樣; 數(shù)據(jù)映射; 數(shù)據(jù)并行

中圖分類號:TP302 文獻標識碼:A

文章編號:1004-373X(2010)10-0030-03

Data Parallel Implementation of Resampling in Geometric Operation

WANG Guang

(Xi′an University of Arts and Science， Xi’an 710065， China)

Abstract:Geometric operation is one of the basic operations in computer graphics and computer vision. How to implement the high-speed and real-time operations effectively， is a major problem existing in modern media applications. The resampling operation， a key global operation in image processing， is generally implemented by sequential implementation means. There are few reports about the data parallel implementation of geometric operations on SIMD processor array. In order to meet the requirements of real-time processing of images， a method of the data parallel implementation of resampling in geometric operations is put forward， and the results are proved. Through the data parallel transmission between SIMD PE arrays， the resampling problem of geometric operations was solved in data parallel. The implementation of the data parallel reduces the complexity of resampling from Ο(MN) implemented by accessing memory to Ο(M+N)， and greatly enhances the processing speed of processor. Thereby， it can meet the requirements of real-time processing of images.

Keywords: geometric operation; resampling; data mapping; data parallelism

0 引 言

幾何操作是計算機圖形和計算機視覺的基本操作之一[1-2]。數(shù)字圖像的幾何操作通過通過改變圖像像素的位置而改變了圖像中各物體之間的空間位置關(guān)系，從而可以實現(xiàn)圖像幾何校正、圖像較直、圖像配準以及圖像藝術(shù)處理等應(yīng)用。

目前，幾何操作的串行實現(xiàn)方法已很成熟[3]，但對幾何操作在SIMD處理元陣列上進行數(shù)據(jù)并行處理的報導(dǎo)并不多。由于圖像處理中很多操作都具有數(shù)據(jù)并行性[4-5]，為了滿足對圖像進行實時處理的需要，必須研究幾何操作的數(shù)據(jù)并行實現(xiàn)方法。幾何操作包括坐標變換、灰度校正和重采樣操作3個方面算法。前2個是點操作和局部操作，并行化較容易;而重采樣操作是圖像處理中的全局操作，非常關(guān)鍵，也非常復(fù)雜。在SIMD并行處理器上，重采樣操作一般是采用處理元陣列與陣列存儲器之間的數(shù)據(jù)流傳送方法來實現(xiàn)[6-9]的。也就是說，只能通過串行處理方法來解決，數(shù)據(jù)并行化非常困難。這樣，幾何操作數(shù)據(jù)的巨大重采樣通信量，給媒體處理的實時性要求提出了嚴峻的挑戰(zhàn)。

在此，希望通過處理元陣列內(nèi)的數(shù)據(jù)并行傳送方法，對數(shù)字圖像幾何操作的數(shù)據(jù)并行實現(xiàn)方法進行研究，以實現(xiàn)幾何操作中重采樣的數(shù)據(jù)并行實現(xiàn)，從而降低數(shù)據(jù)并行實現(xiàn)的復(fù)雜性，更好地滿足數(shù)字圖像快速實時處理的需要。

1 幾何操作的數(shù)據(jù)并行實現(xiàn)

為了便于討論，這里首先給出原圖像空間和變換圖像空間的概念。原圖像空間f(x，y)指未經(jīng)變換的原始數(shù)字圖像空間，以行數(shù)x、列數(shù)y來索引，每個點對應(yīng)變換前圖像的像素灰度值。變換圖像空間g(x′，y′)是指幾何操作后的數(shù)字圖像空間，以行數(shù)x′、列數(shù)y′來索引，每個點對應(yīng)變換后圖像的像素灰度值。

從數(shù)字圖像結(jié)構(gòu)的角度來說，原圖像空間和變換圖像空間都是用同樣的笛卡爾直角坐標系來描述的，坐標原點在圖像左上角，x和x′軸沿水平方向向右為正，y和y′軸沿垂直方向向下為正。

設(shè)原圖像空間中的像素為點P(x，y)，變換后變換圖像空間的像素點為P′(x′，y′)，則稱P′是P的變換點。灰度值表示為f(P)或者f(x，y)，相應(yīng)有g(shù)(P′)或者g(x′，y′)。從概念上來說，一對變換點的灰度值是相等的，即f(P)=f(P′)，也就是說，把像素的幾何位置換了個地方。同理，每個像素對應(yīng)的處理元用PE(x，y)和PE(x′，y′)表示。當x=x′，y=y′時，PE(x，y)=PE(x′，y′)。

文獻[10]中對幾何操作的計算內(nèi)容進行了清楚的闡述。它認為幾何操作就是將坐標為(x，y)的像素值映射到新位置(x′，y′)上，數(shù)學上是用一對變換方程即描述的，即:

x′=Tx(x，y)， y′=Ty(x，y)(1)

假設(shè)要對一幅圖像相對于原點旋轉(zhuǎn)一個角度θ，則式(1)可以表示為:

x′=xcos θ-ysin θ，y′=xsin θ+ycos θ(2)

根據(jù)式(2)，如果將坐標位置(50，0)處的像素旋轉(zhuǎn)35°，由于cos 35°與sin 35°都不是整數(shù)值，于是有x′=40.96，y′=28.68，也就是將像素值移動到坐標位置(40.96，28.68)處，出現(xiàn)了非整數(shù)坐標問題。這表示輸入圖像中該像素值不能正好映射到輸出圖像的某個像素位置上，而是在某些像素位置的附近。所以，幾何操作的計算內(nèi)容除了變換方程的計算外，還有非整數(shù)坐標問題引起的插值計算。一般情況下，輸入圖像的位置坐標(x，y)為整數(shù)，而輸出圖像的位置坐標(x′，y′)是非整數(shù)，這時必須采用重采樣的方法來決定該坐標位置的灰度值，所以插值計算又叫重采樣操作。

不難看出，當幾何操作采用數(shù)據(jù)并行方法實現(xiàn)時，其難點就是解決重采樣的數(shù)據(jù)并行實現(xiàn)問題。

2 重采樣問題的數(shù)據(jù)并行實現(xiàn)

假如已經(jīng)確定幾何操作的映射方程為變換方程(1)，其中x和y為原始圖像中像素的坐標，而x′和y′為目的圖像中像素的坐標，很明顯，需要通過映射方程，根據(jù)原圖像中坐標位置(x，y)計算出變換圖像中新的坐標位置(x′，y′)，所以需要將坐標位置(x，y)處的像素值移動到坐標為(x′，y′)的新位置處，這就是所謂的數(shù)據(jù)重采樣。圖1給出了進行幾何操作前后的兩幅圖像。

在SIMD 處理陣列上如何快速高效地實現(xiàn)圖像處理中的重采樣操作，是現(xiàn)代圖像處理，特別是密集型數(shù)據(jù)圖像處理的一個難題。下面針對重采樣實現(xiàn)問題進行討論。

圖1 圖像的幾何操作

重采樣問題的實現(xiàn)，在已知的SIMD并行處理器上，是采用處理元陣列與陣列存儲器之間的數(shù)據(jù)流傳送方法實現(xiàn)的，也就是說，重采樣問題是通過load/store方法實現(xiàn)的。為了獲取所需要的重采樣數(shù)據(jù)，ALU陣列必須頻繁地訪問片上中間存儲層次，甚至是片外存儲器。假設(shè)數(shù)據(jù)的位寬為k，對一個N×M的像素幀來說，其傳送數(shù)據(jù)的次數(shù)為NM/k，即重采樣用該方法實現(xiàn)的復(fù)雜度為Ο(NM)。很明顯，這樣的實現(xiàn)方法不但增加了中間存儲層次的數(shù)據(jù)帶寬要求，而且增加了處理復(fù)雜度，降低了處理速度。

為了使SIMD體系結(jié)構(gòu)的計算機能更好地滿足數(shù)字圖像快速實時處理的需要，必須對全局操作算法中重采樣問題進行數(shù)據(jù)并行實現(xiàn)。下面，基于SIMD PE陣列，討論一種新的實現(xiàn)全局操作中重采樣問題的方法。

從上面的討論知道，圖像處理中的重采樣操作，就是通過一定的映射關(guān)系，計算出原始圖像中像素所處坐標位置(x，y)所對應(yīng)的新位置(x′，y′)，從而將(x，y)位置的像素值移動到(x′，y′)處。假設(shè)SIMD PE陣列的大小與圖像陣列的大小相等，即每個PE中只包含原始圖像中一個像素值，則數(shù)據(jù)重采樣如圖2所示。

圖2 重采樣操作示意圖

圖2中，坐標x的增大方向表示向東，坐標y的增大方向表示向南。從圖2可以看出，(x1，y1)位置的像素值需要被傳送到(x1′，y1′);(x2，y2)位置的像素值需要被傳送到(x2′，y2′)，依此類推，每個PE位置都有與之對應(yīng)的像素值，即(xi，yi)位置的像素值需要被傳送到(xi′，yi′)。

假設(shè)圖像陣列的大小與SIMD PE陣列的大小都為M×N，并且圖像已經(jīng)存放在SIMD PE陣列中，即每個PE的一個局部存儲存放一個圖像像素。由于原始圖像空間和目的圖像空間都位于同一個SIMD PE陣列之中，所以數(shù)字圖像處理中的重采樣操作，實質(zhì)上就是像素值的空間位置變換，也就是說，將像素值從一個初始位置(xi，yi)處的PE中移動到另一個新的位置(xi′，yi′)處的PE中。這種操作可以通過SIMD PE陣列的通信機制來實現(xiàn)。

按照什么規(guī)律來移動SIMD PE陣列，才能減少陣列的通信時間，提高重采樣效率，是需要研究的主要問題。這里，首先提出像素移動的偏移量概念。所謂像素移動的偏移量，指在SIMD PE陣列中將像素值從其初始PE位置(x，y)傳送到目的PE位置(x′，y′)所需的移動次數(shù)，包括x方向偏移量ΔX和y方向偏移量ΔY。數(shù)學公式為:

ΔX=x′-xΔY=y′-y(3)

需要說明的是，此時計算出來的兩個偏移量ΔX和ΔY范圍分別為[-M，M]和[-N，N]。其中，ΔX為負值，表示像素需要向西移動;ΔX為正值，表示像素需要向東移動;同樣，ΔY為負值，表示像素需要向北移動;ΔY為正值，表示像素需要向南移動。

計算出各個像素相對于PE的幾何位置偏移量后，就可以知道SIMD PE陣列中所有像素值所需要進行的移動情況。像素值在SIMD PE陣列中的這種移動，可以通過陣列的鄰近通信機制來實現(xiàn)。也就是說，全局操作的數(shù)據(jù)移動最終可以通過局部操作的鄰近PE數(shù)據(jù)傳送來實現(xiàn)。

下面具體討論像素值在SIMD PE陣列中實現(xiàn)移動的情況。

假設(shè)用(x，y)表示(x，y)位置處的PE，即用f(x，y)表示原始圖像中(x，y)位置處的像素值;用g(x′，y′)表示目的圖像中(x′，y′)位置處的像素值;用Reg(x，y)表示存儲像素值的寄存器;用Buffer-E，Buffer-W，Buffer-S，Buffer-N分別表示PE(x，y)中東西南北E，W，N，S四個方向的輸入、輸出緩沖器。PE中4緩沖器如圖3所示。

圖3 PE中4個緩沖器示意圖

根據(jù)計算出偏移量的整數(shù)部分進行陣列移動。首先，進行x方向的移動;其次進行y方向的移動。移動時，除了需要移動像素點的灰度值，還要同時移動2個偏移量ΔX和ΔY，因為偏移量決定了數(shù)據(jù)移動的目的地址。需要注意的是，偏移量每移動1次，其值也同時變化1次，或加1或減1。

根據(jù)ΔX的值，PE在東西方向上移動數(shù)據(jù)的操作過程可以分3種情況，陣列移動具體算法如下:

如果ΔX>0:數(shù)據(jù)向東傳送，ΔX值減1，f(x，y)和新的偏移量被送到緩沖器中，并從緩沖器中取出從西面PE(x-1，y)傳送過來的像素值和像素移動偏移量;

如果ΔX<0:數(shù)據(jù)向西傳送，X值加1，f(x，y) 和新的偏移量被送到緩沖器中，并從緩沖器中取出從東面PE(x+1，y)傳送過來的像素值和像素移動偏移量;

如果ΔX=0:陣列移動結(jié)束;

同理，根據(jù)ΔY的值，PE在南北方向上移動，數(shù)據(jù)的具體操作過程也可以分為類似于東西方向移動的3種情況。

因為兩個偏移量ΔX和ΔY的取值范圍分別為[-M，M]和[-N，N]，所以數(shù)據(jù)向東西方向移動的最大次數(shù)為M，向南北方向移動的最大次數(shù)為N。這樣，如果大小為M×N的SIMD PE陣列(或圖像像素陣列)中，所有PE都進行并行操作，則最多經(jīng)過2(M+N)次數(shù)據(jù)移動就可以完成重采樣操作。也就是說，在SIMD PE陣列上，對數(shù)據(jù)并行實現(xiàn)重采樣問題的并行度，被提高到與處理元陣列大小一致的程度，即Ο(M+N )。

3 結(jié) 語

幾何操作的數(shù)據(jù)并行實現(xiàn)，必須先根據(jù)變換方程計算出圖像中每個像素點所對應(yīng)的新坐標位置，而這個坐標位置一般不是整數(shù)值，所以幾何操作的數(shù)據(jù)并行，避免不了重采樣問題。本文通過SIMD PE陣列上的特殊傳送指令，在PE陣列內(nèi)部數(shù)據(jù)并行上實現(xiàn)全局操作算法中的重采樣問題，使實現(xiàn)重采樣的復(fù)雜度由傳統(tǒng)方法的Ο(M×N)變?yōu)棣?M+N)，大大提高了處理速度。

當然，針對幾何操作中重采樣問題的討論，只是假設(shè)了圖像幀大小與處理元陣列大小一致的情況。實際上，圖像幀大小要遠大于處理元陣列大小，這就使問題更加復(fù)雜化。對于圖像幀大小要遠大于處理元陣列大小的情況，采用該文提出的方法與傳統(tǒng)重采樣方法相結(jié)合，即將圖像數(shù)據(jù)分為2部分:已經(jīng)傳送到處理元陣列內(nèi)的數(shù)據(jù)和處理元陣列外的數(shù)據(jù)。對PE陣列內(nèi)的數(shù)據(jù)重采樣，可以通過討論的陣列內(nèi)數(shù)據(jù)移動予以實現(xiàn);而對PE陣列外數(shù)據(jù)的重采樣操作，目前仍舊采用傳統(tǒng)方法完成，即通過數(shù)據(jù)的存取過程，實現(xiàn)重采樣操作。

參考文獻

[1]KOREN I. Computer arithmetic algorithms[M]. Englewood Cliffs: Prentice Hall， 1993.

[2]CHAUDHARY V， AGGARWAL J K. Parallelism in computer vision: a review [C]//Parallel Algorithms for Machine Intelligence and Vision， New York: Springer-Verlag， 1990: 271-309.

[3]KANADE T， MORITA T. A sequential factorization me-thod for recovering shape and motion from image streamsr [C]//Proc. of the ARPA Image Understanding Workshopr. San Fransisco: Morgan Kaufmann Publishers， 1994: 1177-1188.

[4]WEN Y H， CARPENTER B， ZHANG G S， et al. Java data parallel extensions with runtime system support [C]//Fifth International Conference on High Performance Computing 12. Washington DC: IEEE Computer Society， 1998: 12-17.

[5]MARESCA M， FOUNTAIN T J. Scanning the issue: massively parallel computers[J]. Proceeding of the IEEE， 1991， 79(4): 395-402.

[6]OWENS J D， RIXNER S， KAPASI U J， et al. Media processing applications on the imagine stream processor [C]//20th IEEE International Conference on Computer Design， IEEE Computer Society. Germany: Freiburg， 2002: 295-302.

[7]GONZALEZ R C， WOODS R E， EDDINS L. Digital image processing using matlab[M]. Beijing: Publishing House of Electronic Industry， 2004.

[8]KOZYRAKIS C. Scalable vector media processors for embedded systems [D]. Berkeley: University of California， 2002.

[9]RICHARDS J A， JIA Xiu-ping. Remote sensing digitalimage analysis: an introduction [M]. [S.l.]: [s.n.]， 1999.

[10]EFFORD N. Digital image processing: a practical introduction using Java [M]. UK: Pearson Education Limited， 2000.