基于深度和子樹約束最小樹形圖的高編碼效率圖像刪除

摘" 要： 圖像刪除是指從一個壓縮圖像集中去除一個或多個圖像，生成一個新的壓縮圖像集。針對當前圖像刪除方法存在搜尋的預測參考圖像不佳，導致編碼效率不足的問題，提出一種基于深度和子樹約束最小樹形圖的高編碼效率圖像刪除方法。該方法充分考慮所有剩余圖像之間的相關性，確定最佳的預測參考。首先，提出一種新的圖像分類方法，將所有圖像分成需編碼圖像、無需編碼圖像和待刪除圖像等三類；其次，設計一種新的深度和子樹約束最小樹形圖法，深入探究需編碼圖像之間以及需編碼圖像和無需編碼圖像之間的關系，構建新壓縮圖像集的最小樹形圖；最后，根據得到的最小樹形圖對需編碼圖像進行壓縮，生成新的壓縮圖像集，實現圖像刪除。實驗結果表明，與現有先進方法相比，所提方法取得了更高的編碼效率，同時卻有著相近的計算復雜度。

關鍵詞： 圖像刪除； 壓縮圖像集； 深度和子樹約束最小樹形圖； 編碼效率； 計算復雜度； 預測參考圖像

中圖分類號： TN919.82?34""""""""""""""""""""""""" 文獻標識碼： A""""""""""""""""""""" 文章編號： 1004?373X（2024）09?0059?07

0" 引" 言

近年來，隨著移動設備的廣泛使用，例如智能手機和平板電腦，人們隨時隨地地拍照產生了非常多的數字照片。這些大量的照片通常存儲在移動設備中，或者上傳并存放到云服務器中[1?2]。對于云中任一張圖片，可能存在有著相似內容的照片，稱之為相似圖像。由一組相似圖像構成的集合可以稱為圖像集。為了進一步降低用于相似圖像的存儲空間，學者們已經提出很多優秀的圖像集壓縮方法[3?9]，利用相似圖像之間存在的冗余信息，將每組相似圖像集合編碼成為一個壓縮圖像集。圖像刪除[10]，是指從一個壓縮圖像集中去除一個或多個圖像，形成一個新的壓縮圖像集。

圖像刪除是一類重要的壓縮圖像集管理技術。壓縮圖像集管理可以大致分為三類：圖像插入、圖像子集合并和圖像刪除。圖像插入[11?12]致力于將多張未壓縮的新拍照片插入到一個相關的壓縮圖像集中。圖像子集合并[13]則是將分別從多個相關壓縮圖像集中選取的多個圖像子集進行合并。然而，與前兩者不同，圖像刪除并不考慮插入或者合并圖像，而是刪除圖像。

圖1展示了圖像刪除的一個示例。在該示例中，從一個壓縮圖像集中刪除2張圖像，生成新的壓縮圖像集。其中，標有斜杠的圖像表示待刪除圖像。為方便理解圖像間的預測參考關系，每個圖像和壓縮圖像集分別采用節點和樹形圖進行表示。可以看出，新的壓縮圖像集保留了剩余圖像間的預測參考關系。

目前，對于如何實現圖像刪除，國內外學者都進行了深入的研究。文獻[11]提出，若待刪除圖像是一個葉子節點，則將它直接刪除，否則使用它的父節點作為它的子節點的新父節點，對子節點進行壓縮編碼。該方法能夠簡單直接地去除圖像，但是當待刪除圖像包含根節點時，由于根節點沒有父節點，則該方法不能實現圖像刪除。文獻[12]提出，每個待刪除圖像僅僅被標記為“刪除”，但是并不去除它的實際信息，除非它是一個葉子節點或者它所有的子孫節點都被標記為“刪除”。可以看出，當葉子節點是待刪除圖像時，該方法能夠直接將其去除。然而，對于其他待刪除節點，只有當它的所有子孫節點全都需要刪除，該方法才能完成去除任務。文獻[10]提出一種新的圖像刪除方法，該方法將所有圖像分為需處理圖像、無需處理圖像和待刪除圖像等三類，其中需處理圖像被進一步分成需編碼圖像和只需解碼圖像，其次從其他需處理圖像中為每個需編碼圖像搜尋合適的新父節點，最后對需編碼圖像進行壓縮編碼。與其他兩種方法[11?12]相比，文獻[10]的方法不僅能夠實現對任意節點的刪除，還具有低的計算復雜度和較高的編碼效率。然而，文獻[10]的方法根本沒有考慮需處理圖像與無需處理圖像之間的相關性，使得為需編碼圖像確定的新父節點并不是最佳，導致編碼效率不足。

針對此問題，本文提出一種基于深度和子樹約束最小樹形圖的高編碼效率圖像刪除方法。該方法充分利用所有剩余圖像之間的相關性，設計新的深度和子樹約束最小樹形圖技術，為需編碼圖像尋找最優的預測參考圖像，盡可能地提高編碼效率。與現有先進圖像刪除方法相比，本文方法具有更高的編碼效率，同時卻有著相近的計算復雜度。

1" 本文提出的圖像刪除方法

在描述所提方法之前，首先給出本文中使用的一些符號的定義：

[Sori]：圖像刪除前的壓縮圖像集；[Tori]：[Sori]的最小樹形圖；[r（Tori）]：[Tori]的根節點；[Snew]：新的壓縮圖像集；[Tnew]：[Snew]的深度和子樹約束最小樹形圖；[r（Tnew）]：[Tnew]的候選根節點；[r（Tnew）]：[Tnew]的根節點；[Nen]：需編碼圖像的個數；[Nun]：無需編碼圖像的個數；[dmax]：壓縮圖像集的深度；[Enew]：[Tnew]的有向邊集合；[T'new]：采用朱劉方法得到的[Snew]在無約束情況下的最小樹形圖；[h（u）]：節點[u]的高度；[Vnew]：[Tnew]的節點集合；[Vdel]：待刪除圖像的節點集合；[Vun]：無需編碼圖像的節點集合；[Ven]：需編碼圖像的節點集合；[Vun，i]：情況2的第[i]個子情況下，無需編碼圖像的節點集合；[Ven，i]：情況2的第[i]個子情況下，需編碼圖像的節點集合；[u+]：節點[u]在[Tori]中的父節點；[u-]：節點[u]在[Tori]中的子節點；[Dnew]：[Snew]的有向圖；[T'new，i]：情況2的第[i]個子情況下，采用朱劉方法得到的[Snew]在無約束情況下的最小樹形圖；[W（T'new，i）]：[T'new，i]的邊權值總和；[Enew，i]：情況2的第[i]個子情況下，[Tnew]的有向邊集合；[Dnew，i]：情況2的第[i]個子情況下，[Snew]的有向圖；[LC（u）]：節點[u]的候選節點層集合；[l'（u）]：[u]在[T'new]中處于的節點層。

圖2描繪了本文方法的架構，其包括三個模塊：新的圖像分類、新的深度和子樹約束最小樹形圖方法以及圖像編碼等。

1） 壓縮圖像集中有些圖像需要被刪除，而其他圖像則需保留，對于剩余圖像中沒有父節點的圖像，例如圖1中需被刪除圖像的子節點，為了將它們融合到[Snew]中，需要為其確定新的父節點，并采用新父節點作為新的預測參考圖像分別對它們進行編碼。還有，對于其他的剩余圖像，則不需要進行編碼。所以，根據以上分析，本文中所有圖像被分成三類：第一類是需編碼圖像，第二類是無需編碼圖像，第三類是待刪除圖像。

2） 為了降低編碼預測代價，有必要為[Snew]構建相應的最小樹形圖[Tnew]。通常，最小樹形圖是由節點集合、有向邊集合以及它們對應的邊權值構成。其中，使用有向邊的起始節點作為預測參考圖像，對終端節點進行壓縮編碼，相應的預測代價則是使用邊權值進行表示。因此，當[Snew]的邊權值總和最小，其就具有最低的總預測代價，也就是說有著高的編碼效率，并且需要充分利用所有剩余圖像間的相關性，為每個需編碼圖像選擇最佳的預測參考，才能獲得足夠高的編碼效率。

可以看出，如何構造[Tnew]直接決定著[Snew]的編碼效率。然而，在建立[Tnew]時不得不考慮兩個約束條件：一是快速訪問壓縮圖像集中的任一圖像而產生的深度條件，即[dmax]，例如圖2中刪除前壓縮圖像集中兩個無需編碼圖像都處于層4，其也是圖像所位于層的最大值，則該圖像集的深度為4；二是剩余圖像間存在的預測參考關系不能改變，例如圖2中兩個無需編碼圖像分別和它們父節點的預測參考關系不改變。剩余圖像及它們的預測參考關系構成的樹形圖稱為子樹，包括一個節點或多個節點以及它們之間的有向邊。

所以，應當在深度和子樹約束的條件下對邊權值總和最小化來構建[Tnew]。在本文中考慮到盡可能地利用所有剩余圖像之間的相關性來提高編碼效率，那么需設計一個新的深度和子樹約束最小樹形圖方法來生成[Tnew]。

3） 通過比較[Tori]和[Tnew]，例如圖2中圖像刪除前后兩個壓縮圖像集的樹形圖，可以發現[Tnew]中只有需編碼圖像更新了其預測參考，而無需編碼圖像的預測參考關系根本沒有改變。于是，使用為需編碼圖像分配的父節點作為新的預測參考圖像，對其進行壓縮編碼生成[Snew]。在編碼中，本文采用幾何變換、光度轉換、基于塊的運動補償以及HEVC殘差編碼等技術[14]。

2" 本文方法中的兩個主要模塊

2.1" 新的圖像分類

由于[Tori]和[Tnew]都分別只有一個根節點，當待刪除圖像中不包含[r（Tori）]時，為了降低復雜度，可以直接將[r（Tori）]作為[Tnew]的候選根節點。因此，本文將考慮[r（Tori）]是否刪除，設計新的圖像分類。

情況1：若[r（Tori）]不是一個待刪除圖像，則令其為[r（Tnew）]；

情況2：若[r（Tori）]需要被刪除，該情況進一步分為[Nen]種子情況，對于第[i （i=1，2，…，Nen）]種子情況，令第[i]個需編碼圖像為[r（Tnew）]。

算法1給出新的圖像分類中2種情況相應的具體步驟。在算法1中，所有的待刪除圖像和剩余圖像分別存放到節點集合[Vdel]和[Vnew]中。對于情況1，若待刪除圖像的子節點屬于[Vnew]，將這些子節點都放入節點集合[Ven]中；那些[Vnew]中不屬于[Ven]的節點，則放在節點集合[Vun]中。可以看出，需編碼圖像和無需編碼圖像分別存儲在[Ven]和[Vun]中。另外，對于情況2中第[i]種子情況，其思路與情況1類似。本文分別使用[Ven，i]和[Vun，i]存儲需編碼圖像和無需編碼圖像。

算法1：新的圖像分類

輸入：[Sori]中所有圖像

輸出：節點集合[Vdel]、[Vnew]、[Vun]、[Ven]、[Vun，i （i=1，2，…，Nen）]和[Ven，i （i=1，2，…，Nen）]等

1.初始化： 令節點集合[Vdel]、[Vnew]、[Vun]、[Ven]、[Vun，i （i=1，2，…，Nen）]和[Ven，i （i=1，2，…，Nen）]等都為空集；

2.將所有的待刪除圖像放入[Vdel]；

3.將所有的剩余圖像放入[Vnew]；

4.for 每個[u∈Vdel] do

5." if [?u-∈Vnew] then

6.""" if 情況1 then

7.""""" [Ven←Ven?{u-}]；

8.""" else

9.""""" for [i←1] to [Nen] do

10.""""" [Ven，i←Ven，i?{u-}];

11.""""" end for

12." end if

13."" end if

14.end for

15." if 情況2 then

16.[Vun←u?u∈Vnew，u?Ven]；

17.else

18." for [i←1] to [Nen] do

19.""" [Vun，i←u?u∈Vnew，u?Ven，i]；

20." end for

21.end if

2.2" 新的深度和子樹約束最小樹形圖法

下面詳細介紹本文提出的深度與子樹約束最小樹形圖法，具體步驟如算法2所示。

算法2：新的深度與子樹約束最小樹形圖法

輸入：節點集合[Vnew]、[Vun]、[Ven]、[Vun，i （i=1，2，…，Nen）]和[Ven，i （i=1，2，…，Nen）]等

輸出：[Tnew]

1. if 情況1 then

2." 令[Enew]為空集;

3." for 每個[u∈Vnew] do

4.""" if [u-∈Vnew] do

5.""""" [Enew←Enew?{（u，u-）}];

6."" end if

7." end for

8." for 每個[u∈Vun]和每個[v∈Ven] do

9.""" [Enew←Enew?{（u，v）u≠v-}];

10." end for

11." for 每個[u∈Ven]和每個[v∈Ven] do

12. [Enew←Enew?{（u，v）u≠v}];

13." end for

14." [Dnew←（Vnew，Enew）];

15." 使用朱劉方法獲取[Dnew]的最小樹形圖[T'new];

16.end if

17.if 情況2 then

18." for [i←1] to [Nen] do

19.""" 令[Enew，i]為空集;

20.""" for 每個[u∈Vnew] do

21.""""" if [u-∈Vnew] do

22.""""""" [Enew，i←Enew，i?{（u，u-）}];

23.""""" end if

24.""" end for

25.""" for 每個[u∈Vun，i]和每個[v∈Ven，i] do

26.""" [Enew，i←Enew，i?{（u，v）u≠v-，v≠r（Tnew）}];

27.""" end for

28.""" for 每個[u∈Ven，i]和每個[v∈Ven，i] do

29."""" [Enew，i←Enew，i?{（u，v）u≠v，v≠r（Tnew）}];

30.""" end for

31." ""[Dnew，i←（Vnew，Enew，i）];

32.""" 使用朱劉方法獲取[Dnew，i]的最小樹形圖[T'new，i];

33." end for

34." [m←argimin（W（T'new，i））];

35." [Vun←Vun，m];

36." [Ven←Ven，m];

37." [Enew←Enew，m];

38." [Dnew←Dnew，m];

39." [T'new←T'new，m];

40.end if

41.[LC（r（T'new））←{1}];

42.for 每個[u∈Venu≠r（T'new）] do

43." [LC（u）←{2 to min（l'（u），dmax-h（u））}];

44.end for

45. for 每個[u∈Vunu≠r（T'new）] do

46." [LC（u）←lc+1?lc∈LC（u+）];

47.end for

48.基于[T'new]和[LC（u）?u∈Vnew]，采用文獻[10]中的[Tnew]生成技術獲得[Tnew]；

1） 本文充分利用需編碼圖像之間以及需編碼圖像與無需編碼圖像之間的關系，建立有向邊集合[Enew]。對于每個需編碼圖像，為其搜尋最合適的預測參考圖像，即新的父節點。另外，與需編碼圖像不同，對于每個無需編碼圖像，不是確定新的父節點，而是保留其預測參考關系。所以，算法2的步驟2～步驟13用于構造情況1的[Enew]。其中，步驟3～步驟7是提取剩余圖像中存在的有向邊，步驟8～步驟10是生成每個無需編碼圖像指向每個需編碼圖像的有向邊，步驟11～步驟13是生成其他需編碼圖像指向每個需編碼圖像的有向邊。還有，對于情況2中第[i]種子情況，類似于情況1，步驟18～步驟30用來產生相應的節點集合[Enew，i]。

2） 借助朱劉方法生成的無約束情況下最小樹形圖來輔助建立深度和子樹約束下的最小樹形圖。對于情況1，步驟14和步驟15用于獲得無約束情況下最小樹形圖[T'new]。另外，對于情況2，先得到每個子情況下的[T'new，i（i=1，2，…，Nen）]，再將其中邊權值總和最小的[T'new，m]作為[T'new]，如步驟31～步驟40所示。

3） 使用節點候選層分配法為每個剩余圖像確定候選層，這里候選層指的是節點在[Tnew]中能夠放置的層，如步驟41～步驟47所示。可以看出，[r（T'new）]就放置在第一層，另外需編碼圖像和無需編碼圖像的節點候選層的影響因素是不一樣的，前者包括[l'（u）]、[dmax]和[h（u）]，這里[h（u）]指的是節點[u]到所有葉子節點的路徑中最長路徑上子孫節點的個數，而后者只有其父節點的節點候選層。

4） 根據得到的[T'new]和所有剩余圖像的節點候選層[LC（u）?u∈Vnew]，使用[Tnew]生成技術[10]獲得[Tnew]。

3" 實驗結果與分析

實驗中，本文采用來自于著名圖像數據集[15?16]和一些先進圖像集管理方法[5，9?10，13]的13種相似圖像，包括“Alcatraz Courtyard”“Buddah Tooth Relic Temple”“Campus” “Canteen”“Car”“Doge Palace”“Duomo”“East Indiaman Gotheborg”“Notre?Dame de Paris”“Pool”“San Francisco Palace of Fine Arts”“Second Ring Road”和“UWO”等。這些相似圖像分別屬于五種不同的類型：建筑物、輪船、行人、汽車和植物等。圖3和表1分別給出每種相似圖像的一個圖例和屬性。

在圖像刪除之前，使用圖像集壓縮技術在深度[dmax]限制條件下對每組相似圖像進行壓縮編碼，生成壓縮圖像集。通常[dmax]越大，訪問時延就越長。因此，[dmax]值設置為從3～6，如表1所示。另外，本文也分別對2種圖像刪除情況進行測試，并且表1還列出了[Sori]中圖像的個數以及待刪除圖像的個數等。在編碼中，采用HEVC參考軟件HM16.6對需編碼圖像進行壓縮。具體設置包括低時延（Low Delay， LD）、有損編碼、TZ搜索、快速編碼選擇、率失真優化量化、采樣自適應補償技術等。量化參數設為22、27、32和37等。實驗是在一臺CPU型號為Intel Xeon E5?2650 2.6 GHz以及內存為64 GB的服務器上進行。

圖3中從左上到右下，分別是以下13種相似圖像的示例：“Alcatraz Courtyard”“Buddah Tooth Relic Temple”“Campus”“Canteen”“Car”“Doge Palace”“Duomo”“East Indiaman Gotheborg”“Notre?Dame de Paris”“Pool”“San Francisco Palace of Fine Arts”“Second Ring Road”和“UWO”等。

3.1" 生成的[Tnew]

圖4展示了“Campus”和“Second Ring Road”的樹形圖[Tori]，其中它們的刪除情況分別為情況2和情況1。圖5給出采用本文方法生成的上述兩種相似圖像的[Tnew]。從圖4a）可以看出：節點3、節點0、節點4和節點7等是待刪除圖像；節點11、節點6、節點9和節點2等都是需編碼圖像；無需編碼圖像包括節點1、節點5、節點10和節點8等。對比圖5a）和圖4a），可以發現圖像刪除后生成的[Tnew]只包含剩余圖像，且其深度為3，滿足[dmax]的限制條件。還有，節點11與節點1之間、節點11與節點5之間、節點11與節點10之間和節點9與節點8之間等的預測參考關系在[Tnew]中都保持不變，并且通過比較圖5b）和圖4b）也能看出，生成的[Tnew]也滿足深度和子樹的限制條件。另外，對于“Campus”，雖然根節點3被刪除，但是本文方法在4個需編碼圖像中選擇節點11作為[r（Tnew）]，并且對于“Second Ring Road”，由于根節點6沒有包含在待刪除圖像中，則本文方法直接將該節點作為[Tnew]的根節點。所以，上述結果表明本文方法能夠在深度和子樹的約束條件下生成圖像刪除后的[Tnew]。

3.2" 計算復雜度

圖6展示了使用文獻[10]方法分別為上述兩種相似圖像得到的新壓縮圖像集的樹形圖。從圖中可以看出，該方法產生的樹形圖深度不超過[dmax]，并且也保留了圖像子集中的預測參考關系。然而，與本文方法不同的是，文獻[10]方法沒有充分考慮所有剩余圖像間的相關性來為需編碼圖像確定最合適的預測參考圖像。以“Campus”為例，對于需編碼圖像如節點2，文獻[10]方法只是在其他需編碼圖像包括節點11、節點6和節點9中為其尋找新的父節點，但是，本文方法不僅在這3個需編碼圖像中，還在無需編碼圖像包括節點1、節點5、節點10和節點8中為其確定最合適的預測參考圖像。

表2列出了本文方法和文獻[10]方法的計算復雜度。從表中結果可以看出，對于每種相似圖像，文獻[10]方法都取得了最少的運行時間。這是因為該方法不僅編碼待刪除圖像的子節點，并且只解碼這些節點到根節點的路徑上的所有節點。例如，對于圖4a），分別編碼4個節點，包括節點11、節點6、節點9和節點2等，解碼6個節點，包括節點3、節點11、節點6、節點9、節點0和節點2等。相比于文獻[10]方法，本文方法花費了更多的時間，這是因為除了分別編碼和解碼上述節點之外，本文方法還要對其他的剩余圖像進行解碼，例如圖4a）中的節點1、節點5、節點10和節點8等。但是，兩種方法之間復雜度的差距非常微小。例如，對于“Campus”，差值只有251.03-251.02 = 0.01 s，如表2所示。

相比于圖像編碼而言，圖像解碼的計算復雜度幾乎可以忽略不計，所以，本文方法取得了與文獻[10]方法相近的復雜度。

3.3" 編碼性能

表3給出了相比于文獻[10]方法，本文方法的BDBR（Bj?ntegaard Delta Bit Rate）和BD?PSNR（Bj?ntegaard Delta Peak Signal?to?Noise Ratio）[17]的結果。從表中結果可以發現，對于每種相似圖像，本文方法都取得了一定的編碼碼率節省和亮度峰值信噪比的提高。例如，對于“UWO”，BDBR節省了6.7%，并且BD?PSNR提高了0.51 dB。究其原因，主要是因為本文方法在為需編碼圖像搜尋新父節點時，不僅考慮文獻[10]方法給出的圖像，還考慮其他的剩余圖像，以便確定最合適的預測參考圖像，并且，BDBR平均節省了3.5%，同時BD?PSNR平均提高了0.25 dB。

4" 結" 語

本文提出一種新的圖像刪除方法。該方法充分考慮剩余圖像之間的相關性，為每個需編碼圖像從其他需編碼圖像和所有無需編碼圖像中確定最佳的預測參考圖像，以提高圖像刪除的編碼效率。為實現此目標，本文首先給出新的圖像分類，接下來設計新的深度和子樹約束最小樹形圖法，最后對需編碼圖像進行壓縮，生成[Snew]。與文獻[10]方法相比，實驗結果表明，本文方法具有更高的編碼效率和相近的計算復雜度。如何在保持高編碼效率的基礎上進一步降低壓縮需編碼圖像的復雜度，將會是今后研究的一個重點方向。

注：本文通訊作者為沙麗娜。

參考文獻

[1] FERRERIA B， RODRIGUES J， LEITAL J， et al. Practical privacy?preserving content?based retrieval in cloud image repositories [J]. IEEE transactions on cloud computing， 2019， 7（3）： 784?798.

[2] SABRY E S， ELAGOOZ S S， ABD EL?SAMIE F E， et al. Image retrieval using convolutional autoencoder， InfoGAN， and vision transformer unsupervised models [J]. IEEE access， 2023， 11： 20445?20477.

[3] ZHANG X F， LIN W S， ZHANG Y B， et al. Rate?distortion optimized sparse coding with ordered dictionary for image set compression [J]. IEEE transactions on circuits and systems for video technology， 2018， 28（12）： 3387?3397.

[4] CORSINI M， BANTERLE F， CIGNONI P， et al. Image sets compression via patch redundancy [C]// 8th European Workshop Visual Information Process. New York： IEEE， 2019： 10?15.

[5] SHA L， WU W， LI B. Image set compression for similar images with priorities [J]. Electronics letters， 2019， 55（5）： 262?264.

[6] ZHANG X， SUN J R， MA S W， et al. Globally variance?constrained sparse representation and its application in image set coding [J]. IEEE transactions on image processing， 2018， 27（8）： 3753?3765.

[7] WU H， SUN X Y， YANG J Y， et al. 3D mesh based inter?image prediction for image set compression [C]// Proceedings of the 2013 IEEE International Conference on Multimedia and Expo. New York： IEEE， 2019： 1690?1695.

[8] YIN W B， SHI Y H， ZUO W M， et al. A co?prediction?based compression scheme for correlated images [J]. IEEE transactions on multimedia， 2020， 22（8）： 1917?1928.

[9] SHA L N， WU W， LI B B. Novel image set compression algorithm using rate?distortion optimized multiple reference image selection [J]. IEEE access， 2018， 6： 66903?66913.

[10] SHA L N， WU W， LI B B. Low?complexity and high?coding?efficiency image deletion for compressed image sets in cloud servers [J]. IEEE transactions on cloud computing， 2023， 11（1）： 608?619.

[11] WU H， SUN X Y， YANG J Y， et al. Lossless compression of JPEG coded photo collections [J]. IEEE transactions on image processing， 2016， 25（6）： 2684?2696.

[12] ZOU R B， AU O C， ZHOU G Y， et al. Personal photo album compression and management [C]// 2013 IEEE International Symposium on Circuits and Systems. New York： IEEE， 2013： 1428?1431.

[13] WU W， SHA L N. Image subset union for compressed image sets in cloud servers [J]. IEEE transactions on cloud computing， 2023， 11（3）： 2603?2613.

[14] SHI Z B， SUN X Y， WU F. Photo album compression for cloud storage using local features [J]. IEEE journal of emerging and selected topics in circuits and systems， 2014， 4（1）： 17?28.

[15] CARL O. Data set page [EB/OL]. [2011?11?13]. http：//www.maths.lth.se/matematiklth/personal/calle/dataset/dataset.html.

[16] PHILBIN J， ZISSERMAN A. The Paris dataset [EB/OL]. [2008?06?28]. http：//www.robots.ox.ac.uk/～vgg/data/parisbuildings/.

[17] YUAN H， ZHAO S Y， HOU J H， et al. Spatial and temporal consistency?aware dynamic adaptive streaming for 360?degree videos [J]. IEEE journal of selected topics in signal processing， 2020， 14（1）： 177?193.

High?coding?efficiency image deletion based on depth? and

subtree?constrained minimum spanning tree

SHA Lina1， WU Wei2

（1. School of Information Engineering， Yangling Vocational amp; Technical College， Xianyang 712100， China;

2. State Key Laboratory of Integrated Services Networks， Xidian University， Xi’an 710071， China）

Abstract： Image deletion aims to remove one or several compressed images from a compressed image set， generating a new compressed image set. Some deficiencies exist in the existing image deletion algorithms， such as unsatisfied coding efficiency due to sub?optimal prediction reference images. To address the issue， a high?coding?efficiency image deletion algorithm based on depth? and subtree?constrained minimum spanning tree （DSCMST） is proposed. In the method， the correlations among all the remaining images are fully considered to determine the most appropriate prediction references. A new image categorization method is advanced， in which all the images are classified into three kinds， named images needed to be encoded， images unneeded to be encoded， and to?be?deleted images. A new DSCMST method is designed to thoroughly explore the relationships among images to be encoded and the relationships among images to be encoded and images not to be encoded， so as to establish the DSCMST of the new compressed image set. According to the obtained DSCMST， the image to be encoded is compressed to generate a new compressed image set to accomplish the image deletion. Experimental results show that the proposed algorithm achieves higher coding efficiency while having basically equivalent complexity in comparison with the existing advanced methods.

Keywords： image deletion; compressed image set; DSCMST; coding efficiency; computational complexity; reference image prediction

DOI：10.16652/j.issn.1004?373x.2024.09.011

引用格式：沙麗娜，吳煒.基于深度和子樹約束最小樹形圖的高編碼效率圖像刪除[J].現代電子技術，2024，47（9）：59?65.

收稿日期：2023?11?28"""""""""" 修回日期：2023?12?19

基金項目：楊凌職業技術學院校內基金項目（ZK22?44、BG2023?005、JG2022003）；國家自然科學基金面上項目（61471277）；111計劃（B08038）

沙麗娜，等：基于深度和子樹約束最小樹形圖的高編碼效率圖像刪除

沙麗娜，等：基于深度和子樹約束最小樹形圖的高編碼效率圖像刪除

作者簡介：沙麗娜（1979—），女，江蘇蘇州人，博士，講師，CCF會員，研究方向為圖像集管理和智能圖像處理。

吳" 煒（1977—），男，安徽黃山人，博士，副教授，博士生導師，CCF會員，中國通信學會高級會員，研究方向包括圖像編碼、視頻碼率控制、智能圖像處理和計算機視覺等。

沙麗娜，等：基于深度和子樹約束最小樹形圖的高編碼效率圖像刪除