algorithm - 使用四叉树算法的图像压缩

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;
}

使用此哈希表可以直接构建四叉树。它是复杂的算法，具有 O(M, N) 个递归步骤，每个步骤 O(M,N) 添加到 O(M^2,N^2)。您可以通过对图像进行一些预处理来降低 isMonoChromatic 函数的复杂性。

附言很抱歉这篇文章很长。希望对您有所帮助。