結合主成分分析和圖像分塊的重定向研究

彭晏飛， 王靜， 劉曉軒， 鞏勝杰

（遼寧工程技術大學 電子與信息工程學院， 遼寧 葫蘆島 125105）

1 引言

隨著媒體技術的發展，不同尺寸的顯示設備出現在市場上。同一張圖像，在不同設備間轉換并顯示時，需要對圖像進行非均勻縮放。圖像重定向技術將圖像適配到目標屏幕上并很好地展示，受到多個領域的重視和應用［1-3］。

傳統的重定向方法有裁剪［4-5］和縮放［6-7］。裁剪指在圖像中選擇并保留感興趣區域；縮放（Scaling，SCL）指主體信息和背景信息按照同一縮放因子縮放。傳統的重定向方法雖然能改變圖像的長寬比，但是可能會造成圖像的重要信息丟失或結果變形。當裁剪面積較大或縮放比例較大時，不能達到保護顯著目標的目的。因此，為了克服傳統重定向方法的缺點，基于內容感知的圖像重定向技術成為圖像處理領域研究的熱點［8-10］。

基于內容感知的圖像重定向是一種數字媒體處理技術，將圖像重定向到不同的縱橫比，應盡可能保護重要內容區域。Avidan等人［11］首次提出內容感知的圖像重定向技術，即線裁剪算法（Seaming Carving， SC），以圖像梯度圖作為能量圖，動態規劃尋找并迭代移除最小能量裁縫線至目標尺寸。Rubinstein等人［12］在線裁剪算法的基礎上引入一種正能量判斷依據，將移除裁縫線產生的能量考慮在變形之內。然而當重定向尺寸較大時，上述方法存在圖像變形且運行時間長等問題，影響縮放圖像的質量和處理效率。

綜合以上分析，為解決上述問題，本文提出一種基于主成分分析法（PCA）和圖像分塊的重定向技術。方法的創新性在于：（1）使用PCA算法融合顯著圖和梯度圖，解決主體信息識別度低的問題；（2）裁縫線使用平均值代替，避免了像素不連貫；（3）采用圖像分塊算法并行實現圖像的縮放，克服了傳統重定向技術速度慢的問題。

2 相關工作

SC算法由邊緣檢測生成圖像能量圖，每個像素都賦予能量值，從上到下或從左到右計算八連通路徑的能量值。能量值越大，代表該路徑越重要；反之，能量值越小，路徑相對不重要。重復移除最小能量值的路徑，直到目標尺寸。SC算法可以有效地保護圖像主要目標，因此，許多研究基于SC算法進行改進，改進方式大致分為3類：

（1）重新構造能量圖突出主體［13-17］。能量圖提取信息越多，保護的范圍相對越廣。文獻［13-14，17］引入顯著圖作為能量圖的一部分。Shafieyan等人［15］提出構造顯著圖、深度圖和梯度圖作為能量圖。文獻［16］指出陰影圖像幫助理解圖像內容，故以顯著圖、梯度圖、陰影圖作為重要度圖。以上方法使用線性融合提取圖像特征，但線性融合可能會導致圖像邊緣信息模糊。

（2）改變裁縫線的方式［13-14，17-20］，提高重定向效率。Domingue等人［18］提出一種“流”裁剪算法，雙向移除多條裁縫線。文獻［13］提出一次性自定義移除多個接縫以加快重定向速度。文獻［14，17］提出將八連通路徑改為直線移除。李等人［19-20］提出基于遺傳算法的視頻重定向，在圖像中選擇非最優裁縫線。郭等人［21］提出一種優化累計能量圖的方法IBOC（an improved seam carving algorithm based on image blocking and optimized cumulative energy map）。改變裁縫線的方式，可能會扭曲圖像，視覺效果較差。

（3）多種方法結合操作［22-23］。Wang等人［22］提出拉伸與縮放相結合的變形方法。Dong等人［23］提出先使用線裁剪算法，再使用縮放算法使圖像達到目標比例。多算子操作優于單獨操作，但沒有考慮圖像中主體信息和背景信息的特點。

本文在現有改進方向的基礎上提出新的方法，即通過PCA融合圖像代替線性融合圖像來突出圖像感興趣區域。根據分塊特點，對非顯著分塊進行線裁剪操作，對顯著分塊進行線裁剪和縮放多算子操作，從而減少時間復雜度。

3 本文方法

本文方法從保留圖像顯著內容和減少時間復雜度兩個角度研究圖像重定向問題。算法主要包括以下4個步驟：

（1）PCA融合梯度能量圖和LDF顯著圖；

（2）根據能量閾值，將圖像分為顯著分塊和非顯著分塊；

（3）改進接縫線，取平均能量值代替原始能量；

（4）顯著分塊采用線裁剪和縮放多算子操作重定向圖像，非顯著分塊采用線裁剪算法重定向圖像。

圖1是本文方法的整體框架圖，基于圖像內容將圖像重定向到目標尺寸。首先，通過主成分分析法（PCA）融合梯度圖和顯著圖，得到圖像的能量圖。像素點的能量值越大，代表該像素點越重要；反之，像素點能量值越小，代表該像素點越不重要。其次，由列能量值和閾值為基準，將圖像分為顯著分塊和非顯著分塊。然后，改變裁縫線的方式，取縫線的平均值代替邊界像素能量值。最后，對顯著分塊和非顯著分塊進行重定向操作，顯著分塊按照能量小于閾值的條數進行線裁剪操作，如果沒有達到目標尺寸，直接縮放到目標尺寸；非顯著區域使用線裁剪算法重定向到目標尺寸。

圖1 基于PCA和圖像分塊的重定向流程圖Fig.1 Retargeting flow chart based on PCA and image block

3.1 基于PCA的圖像融合

特征提取是圖像重定向技術保證圖像不失真的前提。梯度圖反映圖像的邊緣信息，顯著圖反映圖像的主體信息，將多源信息相融合，使圖像信息更加豐富，有利于圖像信息的分析和處理。因此，本文利用PCA融合梯度圖和顯著圖，從而產生能量圖。

（1）梯度圖

梯度圖是檢測圖像邊緣信息的重要方法之一。對于圖像I，梯度圖是對x軸方向求導的絕對值與對y軸方向求導的絕對值之和，如式（1）所示：

（2）顯著圖

顯著性目標檢測提取圖像中引入注意的區域，即顯著圖。為了達到保護顯著目標使圖像不失真的目的，引入顯著圖作為能量圖的一部分。利用Wei等人［24］提出的LDF（label decoupling framework for salient object detection）算法對圖像提取顯著圖ES。

（3）PCA融合圖像

現有能量圖以梯度圖代替，但梯度圖只反映梯度信息，不能突出圖像主體信息。以加權平均或點乘來融合梯度圖和顯著圖，雖然操作簡單、速度快，但是所有像素按照相同權重計算，不能突出圖像的主要信息。因此，本文采用PCA方法融合圖像，生成所需的能量圖。

PCA［25］是一種有效分析數據的方法，利用低維非相關變量近似高維向量，常用于提取數據的主要特征。根據特征值的大小確定相應的加權系數，有利于突出圖像重點信息。假設圖像矩陣X=[x1，x2，…xn]，μ為X的均值，cov為協方差矩陣：

計算協方差矩陣cov的特征值λ=[λ1，λ2，…λn]和特征向量c=[c1，c2，…，cn]，選擇q個最大特征值并歸一化W，利用此矩陣可得到高維到低維的轉換，降維矩陣為Y：

PCA提取圖像矩陣中主要成分，兩幅圖像進行直方圖匹配并逆變換，即可得到融合圖像E：

其中，α為系數。

如圖2所示，本文基于PCA圖像融合與圖像線性融合進行對比，驗證PCA圖像融合更能突出圖像顯著區域的細節信息，在重定向過程中保護顯著區域的完整性。

圖2 PCA融合圖和線性融合對比Fig.2 Comparison of PCA fusion graph and linear fusion

3.2 圖像分塊

SC算法遍歷所有像素計算圖像能量值，每移除一條裁縫線，需重新計算能量值。對于尺寸較大的像素，需消耗較長的運行時間。因此，引入圖像分塊。一方面，能夠將顯著區域和非顯著區域分塊，為圖像重定向奠定基礎；另一方面，可以有效降低圖像維度，減少運行時間。

分塊策略有均勻分塊、等距離環形分塊等。但需要移除整條裁縫線來保證圖像的平滑，故將圖像分成1×ω或ω×1塊。當移除垂直裁縫線時，如公式（5）所示：

直接將圖像分成若干個大小相同但不重疊的分塊，不能顯示圖像的特點，因此，提出以能量值決定其顯著性。

以PCA算法融合梯度圖和顯著圖生成的能量圖為標準，假設圖像I尺寸為m×n，計算列能量值E(j)和平均能量值如公式（6）所示：

平均能量值為分界閾值，列能量值大于閾值則認為是顯著列，小于閾值則認為是非顯著列。

圖像分塊時以顯著列為依據。設共有p個顯著分塊，Nk代表第k個顯著分塊。若分塊間隙太小，可忽略不計，記分塊間隙為Th=0.03×m。顯著分塊步驟如下：

Step1：列表list儲存顯著列序號，顯著分塊起始列記為starts（Nk），終止列記為ends（Nk），k＜p。

Step2：k初始化為1，第一個顯著列序號作為第一個顯著分塊的起始值：

Step3：計算列表中相鄰顯著列序號差值：

Step4：所有相鄰顯著列均滿足Δ(i+1)≤Th，表示顯著區域恰好連續，則p=1，即

最后一個顯著列序號作為顯著分塊的終止值。

Step5：如果Δ(i+1)＞Th，表示顯著區域不連續，需分為多個顯著分塊，即p＞1。

迭代求各顯著分塊的起始值和終止值。

Step6：重復執行step3和step5，直到遍歷完列表中所有數據，記

最后一個顯著列序號作為第p個顯著分塊的終止值。

細化與合并顯著分塊。若顯著分塊間隙太小，同樣忽略不計，即

如果顯著分塊滿足公式（12），則忽略此顯著分塊。

顯著分塊不一定從圖像第一列開始，以圖像最后一列結束。因此，如果原始圖像第一列至第一個顯著分塊起始值的間距小于或等于分塊間隙，則歸為第一個顯著塊；同理，如果最后一個顯著分塊的終止值至原始圖像最后一列的間距小于或等于分塊間隙，則歸為最后一個顯著塊，如公式（13）所示：

由公式（7）～（13）可將圖像分為p個顯著分塊，并由顯著分塊間隔分為p-1或p或p+1個非顯著分塊。

3.3 裁縫線的處理

線裁剪算法是一種從左到右或從上到下尋找并移除貫穿整個圖像低能量縫線的重定向技術。根據線裁剪算法的思想，縫線需滿足條件：

其中，X：[1，2，…，n]→[1，2，…，m]是一個映射，裁縫線的像素在圖像中每一列/行只包含1個像素點，且像素點位置滿足八連通要求。

由能量圖計算每條裁縫線的能量值S，并選擇能量值最小的裁縫線。能量值越小，代表該路徑的像素越不重要。故取能量值最小的裁縫線S*，定義為：

動態規劃尋找最優裁縫線，從第二行遍歷到最后一行，并計算每個像素可能連接的累計最小能量M：

由最小能量值M向第一行回溯，尋找最小能量裁縫線路徑經過的像素點，這些像素連接組成的路徑為最優裁縫路徑。

在移除裁縫線過程中，可能會造成左右像素不連貫，因此，本文引入像素均值。如圖3所示，左側圖像中，叉號代表要移除的裁縫線，1代表左相鄰像素，2代表右相鄰像素。由于移除一條裁縫線，左右相鄰像素連接可能不連貫。因此，本文不直接移除圖像中的最佳接縫。為了使目標圖像更加流暢，取左相鄰像素與裁縫線像素的均值作為左側像素（①），右相鄰像素與裁縫線像素的均值作為右側像素（②），取值方式定義如式（17）所示：

圖3 像素移除圖Fig.3 Pixel removal

其中，img(i，j)代表移除的像素點。

3.4 分塊圖像重定向

顯著分塊包含圖像主體區域，非顯著分塊包含背景區域。根據分塊圖像的特點，采用不同的重定向方法更具有合理性。為了保證感興趣區域的完整性，顯著分塊采用SC和SCL相結合的多算子操作；而非顯著分塊由于縫線能量值較小，故采用SC重定向圖像。圖像雖然分為多塊，但在移除像素過程中，各個分塊仍按照設定比例重定向圖像。

（1）顯著分塊

顯著區域是視覺焦點聚集之處，但顯著分塊仍摻雜少量低于分界閾值的縫線，而且移除較多的縫線會造成圖像失真。因此，本文將SC算法和SCL兩種操作相結合。仍然以圖像均值為閾值，計算顯著分塊中低于閾值縫線的數目l，這些縫線對視覺影響較小，使用SC算法移除l條縫線。為了避免視覺效果差，剩余顯著區域使用SCL算法重定向到相應尺寸。SC算法移除能量低的裁縫線不影響視覺效果，SCL重定向能量高的區域保證圖像不失真，二者結合保證顯著區域的完整性。

（2）非顯著分塊

非顯著分塊中大多是背景區域。由于背景信息不太引入注意，因此即使圖像背景稍微不連貫也是可以接受的。對于非顯著區域，列能量值幾乎都低于閾值，所以直接采用SC算法重定向非顯著分塊。

4 結果與分析

4.1 實驗設置與數據集

本文實驗在Windows 10系統下基于python進行，電腦配置是11th Gen Intel（R） Core（TM）i5-11400H @ 2.70 GHz 2.69，16 GB RAM。由于對比實驗基于Matlab進行，本文基于其源碼運行。使用MIT RetargetMe［26］、DUT-OMRON［27］和NJU2000［28］數據集進行實驗。圖像含有不同的結構，人臉、線條、紋理等，有利于針對圖像的不同特點做重定向處理。

4.2 視覺效果對比

為驗證本文方法的有效性，與其他幾種常見的重定向技術進行了比較，分別為首次提出的線裁剪SC算法［11］、拉伸變形的SNS（optimized scaleand-stretch for image resizing）算法［22］、直線代替八連通路徑的CARP（content-aware image resizing based on random permutation）算法［14］和優化累計能量圖的IBOC算法［21］，以此評估本文方法的視覺效果。需要注意的是，CARP算法設定閾值防止移除過多縫線，重定向結果可能達不到相應的尺寸。這里顯示了其能夠達到的尺寸，進行對比。

對第一組圖像進行寬度不變，高度縮放至原圖70%的處理。如圖4所示，圖4（a）縮放至400×210，但CARP只能縮放至400×239。從縮放結果可以看出，SC方法導致墻頂部的兩個角水平一致，且右側與草地銜接部分彎曲；SNS算法中，墻頂部的兩個角也水平一致，且墻體上方明顯變窄；CARP算法中的墻體第二個洞幾乎看不見，且墻體凹凸不平；IBOC算法中墻頂部的兩個角水平一致；本文方法的結果保證了墻體一高一低的視覺差。圖4（b）所有算法重定向至642×344，其顯著區域是荷花，但SC算法和CARP算法的花瓣彎曲；SNS算法的花朵沒有變形，但整體將圖像拉長；IBOC算法中荷花下方的網格發生變形；本文方法保證了荷花圖像的質量。圖4（c）重定向至1 024×526，但CARP重定向至1 024×580，圖中紋理復雜；SC算法導致女生下巴和磚塊邊界嚴重變形；SNS算法墻體上側曲線變窄；CARP算法中，女生眼睛大小不一致；IBOC算法導致墻體發生變形；本文方法保證了女孩的完整性，最大限度地保證了墻體不發生變形。

圖4 圖像高度縮放至原來的70%Fig.4 Image height scaling to the original 70 %

對第二組圖像進行高度不變，寬度縮放至原圖50%的處理。如圖5所示，圖5（a）縮放至200×320，其感興趣區域是塔，SC算法使主體部分嚴重變形；SNS算法致使塔的底端明顯縮??；CARP算法導致塔的頂端左側被移除；本文方法基本保證了圖像的完整性。圖5（b）重定向至200×600，但CARP重定向至259×600。從結果可以看出，SC算法中的蝴蝶觸角和翅膀部分移除；SNS算法中的蝴蝶觸角縮??；CARP算法雖然保證了圖像的整體，但觸角連接處不銜接；本文方法目標圖像中蝴蝶形狀完整，展現了較好的視覺效果。圖5（c）縮放至512×683，但CARP只縮放至723×683。圖中物體多，特征復雜，SC算法導致貓和酒杯扭曲；SNS方法中椅子被移除；CARP算法直線移除，導致貓身體部位不連貫；本文方法的重定向圖像中，貓和桌上的茶具都未變形，盡可能在保證顯著信息不失真的情況下，保證圖像不變形。

圖5 圖像寬度縮放至原來的50%Fig.5 Image width scaling to the original 50 %

對第三組圖像進行高度縮放至原圖60%，寬度縮放至原圖70%的處理。如圖6所示，圖6（a）縮放至420×220，但CARP只縮放至496×247。圖中線條復雜，SC、SNS和IBOC算法均導致仙人球頂部缺失；CARP算法使仙人球的刺變成直線；本文方法保證了仙人球的整體性，視覺效果較好。圖6（b）主體較大，將其縮放至364×325，但CARP只縮放至364×383。SC和IBOC算法使鳥的脖子變長，發生形變；SNS算法中，木樁縮??；CARP算法導致鳥的翅膀凹凸不平；本文方法中，鳥和木樁仍呈一定的比例。圖6（c）縮放至350×147，但CARP只縮放至411×188。SC和IBOC導致男孩變形，同時燈塔桿彎曲；SNS和CARP中，巖石棱角變形；本文方法中，雖然男孩縮小，但保證了主體與背景信息的一致性。圖6（d）所有算法縮放至490×280。從重定向結果可以觀察出，SC和IBOC算法中湖面彎曲向上；SC和SNS算法中的山體被拉長；CARP中的右下角巖石被削減；本文方法中的山體和湖面呈現連貫性。

圖6 圖像寬度和高度分別縮放至原來的70%和60%Fig.6 Image width and height scaling to the original 70% and 60% respectively

圖7 運行時間對比Fig.7 Comparison of running time

綜上所述，本文方法在保護主體信息完整性的同時，保證了背景信息不發生形變。當縮放尺寸較大時，其他方法造成變形或主體信息缺失，但本文方法依然可以保證圖像的整體性和質量。

4.3 運行時間對比

由于SNS算法和IBOC算法基于Matlab實驗，而CARP算法雖然基于python實驗，但由于其不一定達到目標尺寸，因此，只考慮SC算法和本文算法的運行時間。

假設圖像I為m×n，SC算法在移除裁縫線過程中，需要遍歷其左下方、正下方、右下方3個像素點并計算其能量值，故其時間復雜度為O(m×n)。而本文算法將圖像分塊，移除裁縫線時可并行操作，降低了時間復雜度。

單張圖像運行時間對比如表1所示。分別對圖4～圖6進行對比，其縮放尺寸均按照3.2節所示。由表1可知，相同條件下，本文方法的速度明顯快于線裁剪算法。當圖像尺寸較大時，本文算法時間更有優勢，時間消耗接近SC算法的1/10。

表1 運行時間對比Tab.1 Comparison of running time

數據集平均運行時間對比如圖7所示。MIT代表MIT RetargetMe數據集，該數據集尺寸較大，故重定向時速度較慢；DUT代表DUT-OMRON數據集；NJU代表NJU2000數據集。0.3是指對圖像進行高度縮放30%；0.5是指對圖像寬度縮放50%；0.3&0.4是指對圖像進行寬度縮放30%，高度縮放40%。橫坐標代表重定向比例和數據集，縱坐標代表運行時間，斜向柱狀圖代表SC算法運行時間，方格柱狀圖代表本文算法運行時間。經過對比發現，本文方法時間消耗是SC算法的1/3。

從時間復雜度、單張圖像運行時間、數據集運行時間3個維度上衡量，本文方法降低了時間復雜度，提升了運行速度。

4.4 像素位移差

圖像對齊、配準的目的是尋找相同目標。SIFT［29］是一種圖像與最近鄰域對齊的方法。特征提取圖像局部信息，取像素鄰域并獲得128維向量，即在每個像素處提取SIFT描述符表示圖像信息。匹配過程中，數據項約束SIFT描述符的匹配，位移項約束相鄰像素間流向量最小，平滑項約束相鄰像素點的流向量相似，從而實現場景對齊，在圖像和鄰居間建立SIFT流。

SIFT-flow建立密集場景對齊來估計跨場景圖像間的密集對應關系，即以像素位移能量消耗評估重定向圖像的質量。像素點間的位移差越大，圖像越容易發生變形。實驗比較了10幅圖像的最大位移差，結果如表2所示?？梢园l現，本文方法的位移差趨于穩定，說明在犧牲像素點位移差的前提下可以有效保證圖像完整性和提升重定向的運行效率。

表2 基于SIFT-flow的最大位移差Tab.2 Maximum displacement difference based on SIFT-flow

5 結論

圖像發生形變是目前重定向技術中待解決的關鍵難題。本文基于現有的重定向技術使用主成分分析法和分塊來探索圖像完整的可能性。算法由圖像融合、分塊、裁縫線的改進、縮放操作等4部分組成。主成分分析法融合梯度圖和顯著圖，提取包含豐富信息的能量圖；平均裁縫線像素點實現了圖像的連貫性；圖像分塊并行計算且降低圖像的維數，從而減少了計算量。實驗結果表明，本文提出的方法保證了主體信息的完整性，且運行時間明顯降低。目前，本文僅使用閾值來確定多算子操作且易受圖像尺寸和顯著像素影響。未來將研究如何界定多算子操作的閾值，以實現更優的縮放效果。