第8章 幾何運(yùn)算

第8章幾何運(yùn)算8.1引言幾何運(yùn)算用于改變圖像中各物體之間的空間關(guān)系。相當(dāng)于物體在圖像內(nèi)移動(dòng)?？臻g變換要有約束，否則變換后的圖像會(huì)“支離破碎”。8.1.1空間變換定義：g(x,y)＝f(x’,y’)＝f[a(x,y)，b(x,y)]

其中：f(x,y)為輸入圖像，g(x,y)為輸出圖像。函數(shù)a(x,y)和b(x,y)唯一描述了空間變換，若它們是連續(xù)的，則連通關(guān)系將在圖像中得到保持。1

f(x,y)的灰度值僅在整數(shù)位置(x,y)被定義（原始圖像各像素是位于各離散的整數(shù)坐標(biāo)點(diǎn)上），但變換后的g(x,y)可能對(duì)應(yīng)于非整數(shù)坐標(biāo)。這就意味著，g(x,y)的灰度值通常會(huì)由處于非整數(shù)坐標(biāo)點(diǎn)上的f(x,y)的值來決定。因此，如果把f映射為g，則f中的一個(gè)像素可能會(huì)映射到g中幾個(gè)像素之間的位置；反之亦然。

規(guī)定：所有像素都正好位于采樣?xùn)鸥竦恼麛?shù)坐標(biāo)處。8.1.2灰度級(jí)插值28.1.3實(shí)現(xiàn)當(dāng)實(shí)現(xiàn)一個(gè)幾何運(yùn)算時(shí)，可以想象將輸入圖像的灰度一個(gè)一個(gè)像素地轉(zhuǎn)移到輸出圖像中，若一個(gè)像素被映射到4個(gè)輸出像素之間的位置，則其灰度值就要按照插值算法，在4個(gè)輸出像素之間進(jìn)行分配。這便是像素移交映射。像素移交映射向前映射x’y’yxf(x’,y’)g(x,y)x,y非整形x’,y’整形3還可以有另一種與上述相反的映射過程，即：將輸出圖像的灰度一個(gè)一個(gè)像素地反向映射到輸入圖像中，因此一個(gè)輸出像素可能會(huì)被映射到4個(gè)輸入像素之間的位置，輸出像素的灰度值就要按照插值算法，由4個(gè)輸入像素的某種組合來決定。這便是像素填充映射。像素填充映射向后映射x’y’yxf(x’,y’)g(x,y)x,y整形x’,y’非整形48.2灰度值插值

輸出像素被映射到輸入圖像中的非整數(shù)位置，即4個(gè)像素之間，因此需要插值運(yùn)算。8.2.1最鄰近插值（零階插值）

輸出像素的灰度值等于離它所映射到的位置最近的輸入像素的灰度值。

簡(jiǎn)單，但精度不高。58.2.2雙線性插值（一階插值）

函數(shù)f(x,y)在單位正方形頂點(diǎn)的值已知，希望通過插值找到正方形內(nèi)任意點(diǎn)的值。顯然，令由雙線性方程f(x,y)＝ax＋by＋cxy＋d來定義的一個(gè)雙曲拋物面與已知灰度值的4個(gè)頂點(diǎn)擬合，即可根據(jù)這4個(gè)頂點(diǎn)的灰度值求出a、b、c、d這4個(gè)系數(shù)。從而得到用于計(jì)算灰度級(jí)插值的雙線性方程。一維線性插值：f(x)＝f(0)＋x[f(1)-f(0)]f(0)f(1)01xf(x)6二維線性插值（仿照一維插值方法分三步進(jìn)行）：對(duì)y=0的兩頂點(diǎn)插值：f(x,0)＝f(0,0)＋x[f(1,0)－f(0,0)]

對(duì)y=1的兩頂點(diǎn)插值：f(x,1)＝f(0,1)＋x[f(1,1)－f(0,1)]對(duì)x處y方向的兩點(diǎn)插值：f(x,y)＝f(x,0)＋y[f(x,1)－f(x,0)]

也可將上三式合并：f(x,y)＝[f(1,0)－f(0,0)]x＋[f(0,1)－f(0,0)]y＋[f(1,1)＋f(0,0)－f(0,1)－f(1,0)]xy＋f(0,0)由上可見：前3個(gè)式子共3次乘、6次加，而第4個(gè)式子則有4次乘、8次加。因此，用前3個(gè)式子分步計(jì)算要比只用第4個(gè)式子一次計(jì)算還要快些。7f(0,0)f(0,1)f(1,0)f(1,1)f(x,1)(x,1)f(x,y)(x,y)(0,y)f(x,0)(x,0)(1,1)(0,1)(0,0)(1,0)xyxy由圖可見，通過雙線性插值得到的f(x,y)與4個(gè)頂點(diǎn)f(0,0)、f(1,0)、f(0,1)、f(1,1)通常是不一樣的。8放大263.9%最臨近插值雙線性插值98.2.3高階插值

雙線性插值具有平滑作用，會(huì)使圖像的細(xì)節(jié)退化，特別是在放大處理時(shí)，這種影響將更為明顯。另外，由雙線性插值得到的雙曲拋物面在鄰域的邊界處相接吻合，但該處的斜率并不吻合，即導(dǎo)數(shù)在邊界處不連續(xù)。

因此，高階插值相當(dāng)于用一張大的蒙皮恰好蓋住各個(gè)灰度樁值，而不是象雙線性插值那樣，僅是對(duì)每相鄰的4個(gè)樁蓋一張蒙皮?；叶葮吨?08.3空間變換8.3.1簡(jiǎn)單變換根據(jù)前面的公式：g(x,y)＝f(x’,y’)＝f[a(x,y)，b(x,y)]①令a(x,y)＝x，b(x,y)＝y(tǒng)則g(x,y)＝f(x,y)[復(fù)制]②令a(x,y)＝x＋x0，b(x,y)＝y(tǒng)＋y0則g(x,y)＝f(x+x0,y+y0)[平移]此時(shí)，圖像相對(duì)于基準(zhǔn)點(diǎn)被平移了用齊次矩陣表示為11③令a(x,y)＝x/c，b(x,y)＝y(tǒng)/d則圖像在x軸向和y軸向分別放大c和d倍。（左上角的圖像原點(diǎn)在圖像縮放時(shí)不動(dòng)）④令上述c＝－1，則a(x,y)＝－x，產(chǎn)生關(guān)于y軸的鏡像。令上述d＝－1，則b(x,y)＝－y，產(chǎn)生關(guān)于x軸的鏡像。12⑤令a(x,y)＝xcos(θ)－ysin(θ)，b(x,y)＝xsin(θ)＋ycos(θ)

則圖像繞原點(diǎn)順時(shí)針轉(zhuǎn)θ角。當(dāng)圖像繞任意點(diǎn)(x0,y0)旋轉(zhuǎn)時(shí)，可以先將圖像平移到原點(diǎn)，經(jīng)旋轉(zhuǎn)變換后，再移回到(x0,y0)位置。即：移到原點(diǎn)旋轉(zhuǎn)移回13可分離實(shí)現(xiàn)如果圖像僅作平移或縮放操作，輸出像素的坐標(biāo)位置就僅分別依賴于x和y?？梢栽谶@兩個(gè)方向分別進(jìn)行變換，效率還可能更高。例如，先在水平方向產(chǎn)生一個(gè)中間圖像，然后把中間圖像作為輸入，再在垂直方向進(jìn)行變換，得到最終結(jié)果。

原始圖像先在x方向放大（y方向不變）中間圖像再在y方向放大（x方向不變）最終圖像等寬14對(duì)于旋轉(zhuǎn)變換，Catmull和Smith提出了兩步法：即根據(jù)a(x,y)＝xcos(θ)－ysin(θ)導(dǎo)出：再代入到b(x,y)＝xsin(θ)＋ycos(θ)，得：

（18）因此，在運(yùn)算的第一步（只在水平方向）先把a(bǔ)(x,y)＝xcos(θ)－ysin(θ)與b(x,y)＝y(tǒng)聯(lián)立（即變換圖像g(x,y)＝f[a(x,y),y]，其中y仍為原來的值）。然后再在運(yùn)算的第二步（只在垂直方向）將（18）式與a(x,y)＝x聯(lián)立（即g(x,y)＝f[x,b(x,y)]，其中x剛剛變化完，不需再變）。15在上述可分離旋轉(zhuǎn)變換中，要求θ值要小，否則當(dāng)θ

＝90o時(shí)因cos(θ)=0而失靈。但通常情況的旋轉(zhuǎn)角度都很小，由于90o及90o的整數(shù)倍旋轉(zhuǎn)可以通過簡(jiǎn)單的行列交換而實(shí)現(xiàn)，因此，旋轉(zhuǎn)角度可以限制在45o之間。由以上可見，平移、放大、旋轉(zhuǎn)均可以分為兩步的一維運(yùn)算。168.3.2一般變換

在許多圖像處理應(yīng)用中，所需的空間變換都相當(dāng)復(fù)雜，無法用前述g(x,y)＝f[a(x,y)，b(x,y)]那樣的簡(jiǎn)便數(shù)學(xué)表達(dá)式表示。另外，所需的空間變換經(jīng)常要從對(duì)實(shí)際圖像的測(cè)量中獲得，因此更希望用這些測(cè)量結(jié)果而不是函數(shù)形式來描述幾何變換。

例如，攝像畫面上部的畸變，需用矩形柵格目標(biāo)對(duì)其數(shù)字化，再對(duì)不同的區(qū)域用相應(yīng)的空間變換來校正。對(duì)同一部有畸變失真的攝像機(jī)來說，上述空間變換可用于對(duì)所有從該攝像機(jī)輸出的圖像的校正。178.3.3通過指定控制點(diǎn)進(jìn)行變換思路：指定圖像的一系列控制點(diǎn)作空間變換，其他非控制點(diǎn)的位移由插值來決定。

實(shí)現(xiàn)：將圖像分成許多多邊形區(qū)域，并對(duì)每個(gè)區(qū)域使用雙線性映射。188.3.4多項(xiàng)式卷繞思路：找到變換式g(x,y)＝f[a(x,y)，b(x,y)]中a(x,y)和b(x,y)的函數(shù)表達(dá)式，該表達(dá)式通常為多項(xiàng)式，其參數(shù)選擇能使多項(xiàng)式與控制點(diǎn)及其位移量相吻合。（參考文獻(xiàn)[1]中使用了高達(dá)5階的多項(xiàng)式卷繞函數(shù)）。如果控制點(diǎn)數(shù)多于多項(xiàng)式項(xiàng)數(shù)，就必須采用多項(xiàng)式擬合來決定多項(xiàng)式系數(shù)。這時(shí)要求空間變換整體上與指定的控制點(diǎn)最佳擬合。但對(duì)于每一個(gè)控制點(diǎn)則不一定嚴(yán)格吻合。19208.3.5控制柵格插值

輸入的控制點(diǎn)形成柵格，此柵格映射為輸出圖像中連通的、水平放置的矩形柵格。輸入控制點(diǎn)對(duì)應(yīng)矩形頂點(diǎn)，輸入多邊形內(nèi)的點(diǎn)則對(duì)應(yīng)矩形內(nèi)各點(diǎn)。21通常采用雙線性插值對(duì)柵格進(jìn)行插值，這是因?yàn)殡p線性插值計(jì)算簡(jiǎn)單，且可以產(chǎn)生一個(gè)能保持連續(xù)性和連通性的光滑映射。雙線性空間變換的一般表達(dá)式為：G(x,y)＝F(x’,y’)＝F[ax+by+cxy+d，ex+fy+gxy+h]可見該變換由a、b、c、d、e、f、g、h這8個(gè)系數(shù)來定義。約束：輸入四邊形的4個(gè)頂點(diǎn)對(duì)應(yīng)輸出四邊形的4個(gè)頂點(diǎn)這樣，從x’到x的映射，得到4個(gè)含a、b、c、d的方程從y’到y(tǒng)的映射，得到4個(gè)含e、f、g、h的方程根據(jù)上述8個(gè)方程，即可解出a、b、c、d、e、f、g、h這8個(gè)系數(shù)，得到描述二次線性空間變換算法，并依此確定所有落入矩形框內(nèi)的輸出點(diǎn)。22還有另一種更方便、高效的定義：G(x,y)＝F(x’,y’)＝F[x+dx(x,y)，y+dy(x,y)]上式中的dx(x,y)和dy(x,y)表示像素的位移量，是x和y的雙線性函數(shù)。xa,yaxb,ybxc,ycxd,ydx1,y1x2,y1x2,y2x1,y2x,y1x,y2x,ydx(x2,y2)dy(x2,y2)輸入四邊形輸出四邊形如何為矩形內(nèi)所有點(diǎn)確定dx和dy?23由于是雙線性，那么沿著每一輸出行（或每一輸出列）都是線性的。對(duì)每行定義增量x（像素間隔為1），因此對(duì)dx：，同樣對(duì)dy:增量x隨著行的不同而變化，但在輸出矩形頂點(diǎn)的位移值可容易地計(jì)算（對(duì)應(yīng)點(diǎn)約束），即通過給定點(diǎn)的位移進(jìn)行插值來求得。

僅需兩個(gè)加法（dx和dy各一）。2411114444562323336665控制柵格外推法上圖是定義了6個(gè)相鄰矩形的輸出圖像。其空間變換如前所述。外面矩形的雙線性系數(shù)來自其最鄰近的內(nèi)部矩形。另外，相鄰矩形的頂點(diǎn)要重合。通常一個(gè)由四邊形到矩形的映射不足以描述所期望的空間變換，這就需要在輸入圖像中指定一組互相鄰接的四邊形，并使之映射成為輸出圖像中一組相鄰的矩形。258.4幾何運(yùn)算的應(yīng)用8.4.1幾何校正（calibation）消除由于攝像機(jī)導(dǎo)致的數(shù)字圖像的幾何畸變。校正從衛(wèi)星上或飛機(jī)側(cè)視雷達(dá)上得到的發(fā)生幾何畸變的數(shù)字圖像。268.4.2圖像校直（rectification）一些圖像系統(tǒng)使用非矩形的像素坐標(biāo)，用普通顯示器觀察圖像時(shí)需轉(zhuǎn)換為矩形像素坐標(biāo)。例：VikingLander宇宙飛船使用角掃描攝像機(jī)來數(shù)字化火星的全景圖像。采用球面坐標(biāo)系統(tǒng)，掃描線之間以相等的俯仰角隔開，其像素間距代表相等的方位角增量。校正時(shí)，需要將球面投影到一個(gè)相切的平面上，即投影從球面中心點(diǎn)發(fā)出，并將球面上的點(diǎn)投影到平面上。用矩形系統(tǒng)顯示角掃描圖像278.4.3圖像配準(zhǔn)對(duì)相似的圖像進(jìn)行配準(zhǔn)，以便進(jìn)行比較。例如，利用圖像相減來檢測(cè)運(yùn)動(dòng)或變化。如果相減的圖像有微小的位移，則相減后的差圖像將會(huì)有明顯的偏導(dǎo)數(shù)成分，這就掩蓋了真正有意義的圖像差別。靜止圖像用固定位置的攝像機(jī)拍攝多幅，則各圖像是配準(zhǔn)的。否則，在圖像相減前要進(jìn)行配準(zhǔn)。簡(jiǎn)單的配準(zhǔn)用平移，而旋轉(zhuǎn)或更復(fù)雜的變形需要復(fù)雜的幾何運(yùn)算。對(duì)各圖像的細(xì)小特征點(diǎn)進(jìn)行定位，可用于定義控制點(diǎn)，而后基于控制點(diǎn)進(jìn)行圖像的減運(yùn)算。288.4.4圖像樣式轉(zhuǎn)換將圖像以另一種形式進(jìn)行表示，以便于解釋。例如，通過幾何運(yùn)算將果蠅染色體的原始圖像拉平（原始圖像由顯微鏡所拍攝的照片拼接而成），其原理是將輸入圖像的每個(gè)染色體疊加上一個(gè)四邊形的控制柵格，并使其中的兩條邊平行于染色體的軸線，因而這些四邊形被映射成輸出圖像中水平排列的矩形串。298.4.5地圖投影例如，從宇宙飛船上傳回的地球、月球圖片是球面圖片，而拼接成地圖時(shí)是平面的，因此需要幾何運(yùn)算。這是一個(gè)“球面”“平面”的幾何變換過程。30地圖的三個(gè)性質(zhì)：1、沿某些直線保持尺度不變，則地圖等距（equidistant）。2、投影中區(qū)域的面積保持不變，則地圖等值（equivalence）。3、投影中角度保持不變（表面上直線相交的夾角與地圖上投影線之間的夾角相同），則地圖保角（conformal）或同形（orthomolphic）。31正交投影法球極平面投影法Mercator投影法Lambert保角圓錐投影法地圖投影法各種方法的生成技術(shù)、地圖性質(zhì)等均不同。328.4.6變形（Morphing）在影視作品中常見，表現(xiàn)為一幅畫面連續(xù)地并漸漸地變換到另一幅畫面。由于在變換過程中，物體中的特征點(diǎn)會(huì)從其起始位置平滑地移向終止位置，因此可產(chǎn)生為生動(dòng)的效果。這不同于影視制作技術(shù)中的“淡入淡出”技術(shù)。因?yàn)榈氲鲞^程中，第一幅畫面漸漸隱去，隨后第二幅畫面才淡淡地顯現(xiàn)出來。兩幅畫面沒有融合的過程，因而不會(huì)產(chǎn)生逼真的視覺轉(zhuǎn)換。33通常所說的變形都是指由一段圖像變形到另一段圖像的過程，但也有人給變形賦予了另一層擴(kuò)展的含義，即一段圖像自身的變形（不需要另一段圖像），其實(shí)現(xiàn)過程僅僅是對(duì)該段