使用Quadtrees算法的图像压缩

所以我基本上试图在java中使用四叉树来实现基本的图像压缩算法;然而，我真的坚持如何将四个以上的像素变成四叉树。我的直觉是递归。使用Quadtrees算法的图像压缩

基本上现在，这是我的想法。这显然只适用于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); 
    }

来源

2014-10-30 recurrenceprobs

可以有很多方法来压缩图像。以下是使用四叉树的算法。

这个想法是当您递归地划分图像时，最小化树中使用的四叉树节点的数量。如果该矩形中的所有像素都包含相同的颜色，我们将停止划分特定节点。

一个示例节点结构如下所示。

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.对不起，很长的职位。我希望它有帮助。

来源

2014-10-31 04:18:01 satyajanga

使用Quadtrees算法的图像压缩

回答

相关问题