使用Quadtrees算法的圖像壓縮

Question

所以我基本上試圖在java中使用四叉樹來實現基本的圖像壓縮算法;然而，我真的堅持如何將四個以上的像素變成四叉樹。我的直覺是遞歸。

基本上現在，這是我的想法。這顯然只適用於4像素的圖像。我不應該如何深入挖掘圖像陣列。

if(sideLength == 2){ 
     QuadNode parent = new QuadNode(image.length); 
     for(int i = 0; i < image.length; i++){ 
      for(int j = 0; j < image[0].length; j++){ 
       QuadNode child = new QuadNode(image[i][j], image.length/2); 
       if (j == 0 && i == 0) 
        parent.setQuadrant(UpperLeft, child); 
       if (j == 0 && i == 1) 
        parent.setQuadrant(LowerLeft, child); 
       if (j == 1 && i == 0) 
        parent.setQuadrant(UpperRight, child); 
       if (j == 1 && i == 1) 
        parent.setQuadrant(LowerRight, child); 
      } 
     } 
     return new QuadTree(parent); 
    } 

Answer 1

可以有很多方法來壓縮圖像。以下是使用四叉樹的算法。

這個想法是當您遞歸地劃分圖像時，最小化樹中使用的四叉樹節點的數量。如果該矩形中的所有像素都包含相同的顏色，我們將停止劃分特定節點。

一個示例節點結構如下所示。

class QuadTreeNode 
{ 
    Point topLeft; 
    int width; 
    int height; 
    QuadTreeNode children[4]; 
    int color; 
}; 

如果按照中心劃分圖像，則無法實現最佳壓縮。

現在的主要任務是找出我們應該分裂的地方（i，j）。對於這種動態編程和哈希來說，派上用場。

class HashValue 
{ 
    Point p; // location to cut into quads 
    int count;// To contain number of Quadtree Nodes; 
}; 

HashMap<Rect,HashValue> H; 
int createQuadTree(Rect rect) 
{ 
    if(Hash.find(rect)!= Hash.end()) return Hash[rect]; 

    if(isMonoChromatic(rect))// If all the pixels are of same color we stop dividing. 
    { 
     Hash[rect] = {NULL,1}; 
     return 1; 
    } 

    int x=rect.x,y=rect.y,w =rect.w,h=rect.h; 
    int minCount; 
    Point minCut; 
    for(i=x;i<x+w;i++) 
    { 
     for(j=y;j<x+h;j++) 
     { 
      int val = 1; 
      val= val+ createQuadTree(Rect(x,y,i,j)); 
      val= val+ createQuadTree(Rect(x,j,w-i,j)); 
      val= val+ createQuadTree(Rect(i,y,i,h-j)); 
      val= val+ createQuadTree(Rect(i,j,w-i,h-j)); 
      if(val < minCount) 
      { 
       minCount = val; 
       minCutPoint = {i,j}; 
      } 
     } 
    } 
    Hash[rect] = {minCutPoint,minCount}; 
    return val; 
} 

使用此HashTable可以直接構建QuadTree。它是O（M，N）遞歸步驟的復算法，每一步O（M，N）加到O（M^2，N^2）上。您可以通過對圖像進行一些預處理來降低isMonoChromatic函數的複雜度。

P.S.對不起，很長的職位。我希望它有幫助。