四叉树图像模糊（C代码及实现思路）

原创文章，参考文章见末尾，仅供学习交流使用，如果对你有帮助，请一键三连~

代码如有需要会整理上传~

一.实验要求

能够正确的对图像建立四叉树；
对于输入的图像，四叉树能够输出模糊的结果
对颜色相近的区域进行模糊

二.实现思路

背景知识理解
PPM文件格式理解
PPM 是通过RGB三种颜色显现的图像（pixmaps）每个图像文件的开头都通过2个字节「magic number」来表明文件格式的类型（PBM, PGM, PPM），以及编码方式（ASCII 或 Binary），magic number分别为P1、P2、P3、P4、P5、P6
本次的magic number为P6（二进制的ppm文件类型）

前三行为ppm文件的“头部分”信息，然后第四行开始为二进制数据。

21562156的图像大小，RGB的每个色彩值范围为0-255，也就是数8个byte表示一个R或者G或者B的颜色，83个byte（即3Byte）表示一个RGB颜色，UE查看器中矩形内的3Byte就是该文件的一个像素点。通过Photoshop可以查看该值颜色就是我们图片中显示的颜色。

四叉树理解
四叉树（Q-Tree）是一种树形数据结构。四叉树的定义是：它的每个节点下至多可以有四个子节点，通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。这个区域可以是正方形、矩形或是任意形状。以下为四叉树的二维空间结构(左)和存储结构(右)示意图（注意节点颜色与网格边框颜色）：

四叉树的每一个节点代表一个矩形区域（如上图黑色的根节点代表最外围黑色边框的矩形区域），每一个矩形区域又可划分为四个小矩形区域，这四个小矩形区域作为四个子节点所代表的矩形区域。（递归）

四叉树把2D空间进行了分组

高斯模糊理解
它将正态分布（又名"高斯分布"）用于图像处理。本质上，它是一种数据平滑技术（data smoothing）
原理：每一个像素都取周边像素的平均值，"中间点"取"周围点"的平均值。在数值上，这是一种"平滑化"。在图形上，就相当于产生"模糊"效果，"中间点"失去细节。显然，计算平均值时，取值范围越大，"模糊效果"越强烈。
正态分布的权重：计算平均值的时候，我们只需要将"中心点"作为原点，其他点按照其在正态曲线上的位置，分配权重，就可以得到一个加权平均值。

高斯函数：上面的正态分布是一维的，图像都是二维的，所以我们需要二维的正态分布。

正态分布的密度函数叫做"高斯函数"（Gaussianfunction）。其中，μ是x的均值，σ是x的方差。因为计算平均值的时候，中心点就是原点，所以μ等于0。

其二维函数形式为：

权重矩阵：假定中心点的坐标是（0,0），σ=1.5，则模糊半径为1的权重矩阵如下：

这9个点的权重总和等于0.4787147，如果只计算这9个点的加权平均，还必须让它们的权重之和等于1，因此上面9个值还要分别除以0.4787147，得到最终的权重矩阵：

计算高斯模糊：每个像素点的R/G/B值乘以自己的权重值，将这些值个值加起来，就是中心点的高斯模糊的值。对所有点重复这个过程，就得到了高斯模糊后的图像，对RGB三个通道分别做高斯模糊。
思路总结：
先通过对图像建立四叉树（图像的模糊、压缩）
若其图像的R或G或B值任意一个大于标准设定方差，则该子叶继续往下划分；
若小于等于，则不再划分，并将该子叶的矩形区域内的所有RGB值赋予其为平均值
再通过高斯模糊处理图像（图像的平滑处理）

对于RGB三个通道分别做处理，经过多轮高斯模糊，具体处理思想见上

三、代码实现（代码均按顺序出现）

头文件等处理：

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    #define VAR 500 //标准设定方差
    //enum boolean {FALSE,TRUE};
    //typedef enum boolean Bool;
    typedef enum  //设定Bool值
    {
        TRUE = 1,
        FALSE = 0,
    }Bool;

读取图像和输出图像函数：

读取原理：使用结构体储存RGB数值，建立二维矩阵

这里我对原函数做了修改，让color变为全局变量并且读取图像函数返回宽度值

    typedef struct color
    {
        unsigned char r;
        unsigned char g;
        unsigned char b;
    } color;
    color** colors;

读图像函数

    int readImage(int p, char *inFile, char *outFile)
    {
        FILE* f = fopen(inFile, "rb");
        char u[3]; // placehoder
        int width, height, max_value;
        fscanf(f, "%s%d%d%d%c", u, &width, &height, &max_value, &u[0]);
        int i;
       //color **colors;
        colors = (color **)malloc(width*sizeof(color*));
        for (i = 0; i < height; i++)
            colors[i] = (color *)malloc(width*sizeof(color));
        
        for (i = 0; i < height; i++)
            fread(colors[i], sizeof(color), width, f);
        fclose(f);
        //colorss = colors;
        /*
        for(int i = 0;i<width;i++)
        {
            for(int j = 0;j<height;j++)
            {
                printf("(%d,%d):%d,%d,%d\n",i,j,colors[i][j].r,colors[i][j].g,colors[i][j].b);
            }
        }
        */
        return width;
        
}

输出图像函数：

    void printImage(char *fileName, int width)
    {
        FILE *f = fopen(fileName, "wb");
        fprintf(f, "P6\n");
        fprintf(f, "%d %d\n", width, width);
        fprintf(f, "255\n");
        int i;
        for (i = 0; i < width; i++)
            fwrite(colors[i], sizeof(color), width, f);
        fclose(f);
        
    }

建立四叉树并“压缩”图像（实际大小并未压缩，只做形象比喻）

    typedef struct quadtree  //建立四叉树
    { 
        int left;
        int right;
        int up;
        int down;
        struct quadtree *one;
        struct quadtree *two;
        struct quadtree *three;
        struct quadtree *four;  
    } QTree;
    int division(int a, int b)//分四个区域时的一个小算法，防止分重叠
    {
        if((a + b) % 2 == 1)
            return (a+b-1) / 2;
        else
            return (a+b) / 2;
    }
    Bool ismakenewdepth(QTree *root) //计算要不要往下划分，如果要，实现进一步划分，如果不要，则直接赋平均值
    {
        /*
        for(int j=0;j<root->right;j++)
        {
            if(colors[1][1].r)
            ;
            else if(colors[1][1].r)
            ;
            else
                printf("%d",j);
        }
        */
        double rvar = 0, gvar = 0, bvar = 0, gave = 0,  rave = 0, bave = 0;
        for(int i=root->left; i<root->right; i++)//处理每一块现分区域
            for(int j=root->down; j<root->up; j++)
            {
                rave += (int)(colors[j][i].r);
                gave += (int)(colors[j][i].g);
                bave += (int)(colors[j][i].b);//现分区域的所有r值加和
            }
        int summ = (root->up - root->down) * (root->right - root->left);
        rave /= summ;//除以最小单元块数得平均值
        gave /= summ;
        bave /= summ;
    
        for(int i=root->left; i<root->right; i++)//类似原理得现分区域的方差
            for(int j=root->down; j<root->up; j++)
            {
                rvar += (rave - (double)(colors[j][i].r)) * (rave - (double)(colors[j][i].r));
                gvar += (gave - (double)(colors[j][i].g)) * (gave - (double)(colors[j][i].g));
                bvar += (bave - (double)(colors[j][i].b)) * (bave - (double)(colors[j][i].b));
            }
        rvar /= summ;
        gvar /= summ;
        bvar /= summ;
        if(rvar > VAR || gvar > VAR || bvar >VAR)//判断现分区域每个单元间的方差是否太大，太大则需要递归
            //继续拆分
            {
                QTree *twoo = (QTree*)malloc(sizeof(QTree));//左上区域（第一象限）拆分的时候左上不动，动右下,其它区域同理
                twoo->up = root->up;
                twoo->down = division(root->down , root->up);
                twoo->left = root->left;
                twoo->right = division(root->right , root->left);
                twoo->one = NULL;
                twoo->two = NULL;
                twoo->three = NULL;
                twoo->four = NULL;
                root->two = twoo;
                QTree *threee = (QTree*)malloc(sizeof(QTree));
                threee->up = division(root->up , root->down);
                threee->down = root->down;
                threee->left = root->left;
                threee->right = division(root->right , root->left);
                threee->one = NULL;
                threee->two = NULL;
                threee->three = NULL;
                threee->four = NULL;
                root->three = threee;
                QTree *onee = (QTree*)malloc(sizeof(QTree));
                onee->up = root->up;
                onee->down = division(root->down , root->up);
                onee->left = division(root->left , root->right);
                onee->right = root->right;
                onee->one = NULL;
                onee->two = NULL;
                onee->three = NULL;
                onee->four = NULL;
                root->one = onee;
                QTree *fourr = (QTree*)malloc(sizeof(QTree));
                fourr->up = division(root->up , root->down);
                fourr->down = root->down;
                fourr->left = division(root->left , root->right);
                fourr->right = root->right;
                fourr->one = NULL;
                fourr->two = NULL;
                fourr->three = NULL;
                fourr->four = NULL;
                root->four = fourr;
                return TRUE;//继续拆分
            }
        
        else //要是方差不大，就给现分区域内所有的r都赋予平均值，g,b同理
        {
            for(int i = root->left; i < root->right; i++)
                for(int j = root->down; j < root->up; j++)
            {
                colors[j][i].b = bave;
                colors[j][i].g = gave;
                colors[j][i].r = rave;
            }
            
            return FALSE;//方差满足要求
        }
    }
    void recur(QTree *root) //递归函数，从根节点开始按要求完全划分
    {
        Bool r = ismakenewdepth(root);
        if(r == FALSE)
            return;
        
        recur(root->one);//要是一直不满足方差要求，就一直划分下去，其中新建结点已经在ismakenewdepth中弄过了
        recur(root->two);
        recur(root->three);
        recur(root->four);
    }
    void runQTree(int width)  //建立根节点并完全划分
    {
        QTree *root = (QTree*)malloc(sizeof(QTree));//建立一个最大矩形的根节点
        root->down = 0;
        root->left = 0;
        root->right = width;//建立类似于第一象限的坐标系的感觉
        root->up = width;
        root->one = NULL;
        root->two = NULL;
        root->three = NULL;
        root->four = NULL;
        recur(root);//一直递归下去
    }

对已经用四叉树处理过的图像进行高斯模糊（此处设定半径为1，所以省略了计算步骤直接给出矩阵）：

    /*第二部分：高斯模糊*/
    void Guass(int width)//对处理过的图像（细分矩阵的程度不同）进行高斯模糊，半径为1
    {
        double quanzhong[3][3] = {{0.0453542, 0.0566406, 0.0453542}, 
                                  {0.0566406, 0.0707355, 0.0566406}, 
                                  {0.0453542, 0.0566406, 0.0453542}};
        for(int i=1; i<width-1; i++)
            for(int j=1; j<width-1; j++)
            {
                double gave = 0, rave = 0, bave = 0;
                for(int k=-1; k<=1; k++)//对于每一个点都进行高斯模糊，之前每一个点都处理过了，相当于压缩后（抛去细节）再模糊？
                    for(int l=-1; l<=1; l++)
                    {
                        rave += (double)(colors[j+k][i+l].r) * quanzhong[k+1][l+1] / 0.4787147;
                        gave += (double)(colors[j+k][i+l].g) * quanzhong[k+1][l+1] / 0.4787147;
                        bave += (double)(colors[j+k][i+l].b) * quanzhong[k+1][l+1] / 0.4787147;
                    }
                colors[j][i].r = rave;
                colors[j][i].g = gave;
                colors[j][i].b = bave;
            }
    }

主函数

    int main()
    {
        
        int tolerance = 0;
        char *inFile;
        char *outFile;
        
        tolerance = atoi("6");
        inFile = "C:/myUC/exer2/a.ppm";   //设定文件地址
        outFile = "C:/myUC/exer2/b.ppm";
        int a  = readImage(tolerance, inFile, outFile);//读图像
        printf("%d",a);//可检查是否读入
        /*
        for(int i = 0;i<5;i++)
        {
            for(int j = 0;j<5;j++)
            {
                printf("(%d,%d):%d,%d,%d\n",i,j,colors[i][j].r,colors[i][j].g,colors[i][j].b);
            }
        }
        */
        runQTree(a);//四叉树处理图像
        for (int i = 1;i<=20;i++)//多次高斯模糊，这里为20次
        {
            
            Guass(a);
        }
        
        printImage(outFile, a);//输出图像
        
        for(int i = 0;i<a;i++)//程序结束，释放动态分配的空间
        {
            free(colors[i]);
        }
        free(colors);
    }