【数据结构与算法】图像——四叉树自适应模糊（ppm图像为例）
源于大作业~~
目录
前言
一、实现算法
二、结果展示
三、算法框架
(1) QuadTreeNode.h
(2) 结点扩展、细化模糊层次
(3) 模糊化图像四叉树转为图像
(4) 主函数代码
四、说明
五、结语
六、震惊一百年
七、开源代码——but拒绝抄袭从你我做起
----------------------------------QuadTreeNode.h------------------------------------
----------------------------------QuadTreeFunc.h------------------------------------
----------------------------------QuadImg_todo.cpp---------------------------------
前言
一张图片常常会存在空间冗余，即一大部分区域的色彩值相同，然而存储时却将这些像素块视作不同的色彩值，以满足较好的格式规整化。除了存储图片外，对于图片精度不是很高的要求、或者说要求对图片进行一定的模糊化处理，这种种情况都要求对图片的空间冗余进行降低。
针对模糊处理图片的要求，对图片分成四个象限，用一颗四叉树记录，四叉树的叶子结点记录图片的像素值，中间结点用于评判/细分模糊层次。
这样就可以根据一张图片的冗余/细节的分布，自动地进行选择模糊层次。
关键词：四叉树，自适应模糊，图片处理，空间冗余
一、实现算法
模糊化/降低冗余等等，可以将一块区域的色彩值用一个RGB块代替，而不至于每个色彩都单独备份一个。而这个过程，可以将一块区域的像素值，通过计算、选择出一个代表的像素值，来代替这个区域的所有像素值。针对模糊图片问题，为了保持一定的平滑性，采取中位数/均值等简单方法可以做到，也可以进阶采用高斯模糊等等手段。我采用了简单的均值模糊。
然而，一张图片，总是有部分存在空间冗余，部分边缘细节较多，统一的进行模糊，是不理智且不满足要求的。对此，评判一张图片是否需要模糊化，我们可以通过判断其“离散”情况来选择。最简单的“离散”情况度量，即计算RGB三色的方差。当方差和阈值Tolerance进行比较，小于阈值意味着这一个区域的相似程度足够高可以进行均值模糊；大于阈值则意味着相似程度不够高，需要继续细分细化，再进行上述操作。
对此，可以得出以下递归算法：
①图像计算RGB三色方差D1,D2,D3。
②D1>Tolerance || D2>Tolerance || D3>Tolerance 跳转到③否则跳转到④
③标记子图为中间结点。将子图分为四个区域，对每个子图，跳转到①
④计算子图RGB的均值ER,EG,EB，将这一区域所有的像素RGB值赋为对应均值ER,EG,EB。标记为叶子结点。返回。
一开始，用一个四叉树结点root记录整张图片的像素信息，采用上述递归算法，可以将这一个root结点扩展到一棵树，这棵树的所有的叶子结点记录着整个模糊化后的图的信息。
将整棵树转化为图时，只需要遍历整棵树，将叶子结点的色彩区块信息取出并整合，就可以得到模糊化后的图片。
不是很明白算法？看下面这张图片你就明白了！
对图片划分越细，细节越多；反之越粗糙。对于那些分块后满足阈值要求的图像，就模糊并存储其像素值，否则继续细分——直到满足阈值或图片足够小。
二、结果展示
原图：
Tolerance：0
Tolerance：5
Tolerance：15
Tolerance：25
Tolerance：35
Tolerance：50
Tolerance：100（haha~~）
三、算法框架
因为大作业提交时间还没有截止，所以不方便开源所有代码，这里给出框架。
(1) QuadTreeNode.h
struct Pos //偏移量记录
{int x, y;
};
struct color //像素RGB值记录
{unsigned char r;unsigned char g;unsigned char b;
};
class QuadTreeNode
{
public:
//记录细分的四个子图（valid==false，需要细化的情况下链接子图）
QuadTreeNode *q1, *q2, *q3, *q4; // 1~4象限
//记录子图相对于原图的偏移量，以便树转图
Pos position;
//记录子图的长宽像素数
int height, width;
//记录是否为叶子结点，即是否为模糊化图像信息记录结点
bool valid;
//这一结点对应的范围的色彩信息
color **rgbs;
//记录结点深度int depth;
public:QuadTreeNode(color **r, int wd, int ht);QuadTreeNode(int posx, int posy, int wd, int ht);
//计算是否差异超过Tolerance
bool VarianceCalculate(int Tolerance);
//随机化模糊
bool RandomPuzzyTag();
//计算R均值
int AverageR();
//计算G均值
int AverageG();
//计算B均值
int AverageB();
//模糊化区域void Fuzzify();
};
(2) 结点扩展、细化模糊层次
//以Tolerance为模糊阈值，扩展rt结点（自然少不了递归）
void TreeFuzzifyExtend(QuadTreeNode *rt, int Tolerance){...}(3) 模糊化图像四叉树转为图像
//将四叉树记录的模糊化后的图像像素信息传递给二维数组img[][]
void TreeToImage(QuadTreeNode *rt, color **img){...}(4) 主函数代码
值得说明的是，实验所给的图片为ppm格式，因此读写比较特殊。
#include
#include
#include
#include
#include "QuadTreeNode.h"
// #include "QuadTree.h"
#include "QuadTreeFunc.h"void printImage(char *fileName, int width, color **a);
// color color;// To get ppm image from jpeg file, please visit https://convertio.co/jpg-ppm/
void readImage(int p, char *inFile, char *outFile) // Note that width == height here
{FILE *f = fopen(inFile, "rb");char u[3]; // placehoderint width, height, max_value;fscanf(f, "%s%d%d%d%c", u, &width, &height, &max_value, &u[0]);int i;color **colors, **img;colors = (color **)malloc(height * sizeof(color *));img = (color **)malloc(height * sizeof(color *));for (i = 0; i < height; i++){colors[i] = (color *)malloc(width * sizeof(color));img[i] = (color *)malloc(width * sizeof(color));}for (i = 0; i < height; i++)fread(colors[i], sizeof(color), width, f);fclose(f);//=============================================================QuadTreeNode *rt = new QuadTreeNode(colors, width, height);TreeFuzzifyExtend(rt,100);TreeToImage(rt, img);//=============================================================printImage(outFile, width, img);
}void printImage(char *fileName, int width, color **a) // Note that width == height here
{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(a[i], sizeof(color), width, f);fclose(f);
}// int main(int argc, char **argv)
int main()
{int tolerance = 0;char inFile[100];char outFile[100];// if (argc > 1){// tolerance = atoi(argv[1]);// inFile = argv[2];// outFile = argv[3];strcpy(inFile,"D:\\...\\a.ppm");strcpy(outFile,"D:\\...\\result.ppm");readImage(tolerance, inFile, outFile);}return 0;
} 除了正常的I/O和预处理，自己编写的部分，千言万语汇成主函数的几行话：
四、说明
1、可以采用命令行读取指令的方式，但是为了方便调试，我修改了那部分源代码。可以通过重载的main函数 int main(int argc, char **argv) 来实现。
2、除了均值模糊外，还可以选择中位数模糊
3、随机模糊化处理的部分，被我注释掉了
4、将ppm格式转为jpg格式可以简单的采用python库函数
from PIL import Imageimg = Image.open("D:\\...\\a.ppm")
img.save("D:\\...\\a.jpg")#img.show()5、为了得到更加平滑的处理结果，可以了解一下高斯模糊这种高级的玩意
6、其余源代码将在大作业提交结束后上传开源。
五、结语
无论数据结构与算法还是程序设计等等 ，不要局限于作业，做一些小东西，小项目，小工程，小工具等等，都会让学习变得有趣。谁不想有一个能吹牛逼的本科呢？
=========================================================================
六、震惊一百年
今天打开博客，
什么玩意？
本蒟蒻萌新首被挂名，感慨激动万分——同学们的做作业热情太高涨了！
感觉不开源都对不起这个情况（流汗黄豆）——骑虎难下，亚历山大
七、开源代码——but拒绝抄袭从你我做起
感觉不开源都对不起这个热度了。——但是提供思路与个人细节，具体修缮、编写代码还靠个人，抄袭打灭，对你对我都不好~~
----------------------------------QuadTreeNode.h------------------------------------
#ifndef __QUADTREENODE_H__
#define __QUADTREENODE_H__#ifndef NULL
#define NULL 0
#endif#include
#include
#include
using namespace std;struct Pos
{int x, y;
};struct color
{unsigned char r;unsigned char g;unsigned char b;
};class QuadTreeNode
{
public:QuadTreeNode *q1, *q2, *q3, *q4; // 1~4象限Pos position;int height, width;bool valid;color **rgbs;int depth;
public:QuadTreeNode(color **r, int wd, int ht);// QuadTreeNode(QuadTreeNode *&qtn);QuadTreeNode(int posx, int posy, int wd, int ht);bool VarianceCalculate(int Tolerance);bool RandomPuzzyTag();int AverageR();int AverageG();int AverageB();void Fuzzify();
};void QuadTreeNode::Fuzzify()
{int average_r = AverageR();int average_g = AverageG();int average_b = AverageB();for (int i = 0; i < height; ++i)for (int j = 0; j < width; ++j){rgbs[i][j].r = average_r;rgbs[i][j].g = average_g;rgbs[i][j].b = average_b;}valid = true;
}bool QuadTreeNode::RandomPuzzyTag()
{return depth>5&&((int)rand()%6==0);}bool QuadTreeNode::VarianceCalculate(int Tolerance) // 是否要继续细化
{long long sum = height * width;if(sum<=0)return true;long long v = 0, res;long average_r = AverageR();for (int i = 0; i < height; ++i)for (int j = 0; j < width; ++j)v += pow(abs((int)rgbs[i][j].r - average_r), 2);// res = abs(v / sum);res= v/sum;if (res >= pow(Tolerance, 2)-pow((8-depth)>0?8-depth:0,3))//if (res >= -1)return false;v = 0;int average_g = AverageG();for (int i = 0; i < height; ++i)for (int j = 0; j < width; ++j)v += pow(abs((int)rgbs[i][j].g - average_g), 2);// res = abs(v / sum);res= v/sum;if (res >= pow(Tolerance, 2)-pow((8-depth)>0?8-depth:0,3))return false;v = 0;int average_b = AverageB();for (int i = 0; i < height; ++i)for (int j = 0; j < width; ++j)v += pow(abs((int)rgbs[i][j].b - average_b), 2);// res = abs(v / sum);res= v / sum;if (res >= pow(Tolerance, 2)-pow((8-depth)>0?8-depth:0,3))return false;return true;
}
QuadTreeNode::QuadTreeNode(int posx, int posy, int ht, int wd) : q1(NULL), q2(NULL), q3(NULL), q4(NULL), valid(false)
{position.x = posx;position.y = posy;depth=0;width = wd;height = ht;rgbs = (color **)malloc(height * sizeof(color *));for (int i = 0; i < height; i++)rgbs[i] = (color *)malloc(width * sizeof(color));
}QuadTreeNode::QuadTreeNode(color **r, int wd, int ht) : q1(NULL), q2(NULL), q3(NULL), q4(NULL), valid(false)
{width = wd;height = ht;depth=0;position.x = 0;position.y = 0;rgbs = (color **)malloc(height * sizeof(color *));for (int i = 0; i < height; i++)rgbs[i] = (color *)malloc(width * sizeof(color));for (int i = 0; i < height; ++i)for (int j = 0; j < width; ++j)rgbs[i][j] = r[i][j];
}int QuadTreeNode::AverageR()
{int sumr = 0;for (int i = 0; i < height; ++i)for (int j = 0; j < width; ++j)sumr += ((int)rgbs[i][j].r);return sumr / height / width;
}
int QuadTreeNode::AverageG()
{int sumg = 0;for (int i = 0; i < height; ++i)for (int j = 0; j < width; ++j)sumg += ((int)rgbs[i][j].g);return sumg / height / width;
}int QuadTreeNode::AverageB()
{int sumb = 0;for (int i = 0; i < height; ++i)for (int j = 0; j < width; ++j)sumb += ((int)rgbs[i][j].b);return sumb / height / width;
}#endif// QuadTreeNode::QuadTreeNode(QuadTreeNode *&qtn)
// {
// position = qtn->position;
// height = qtn->height;
// width = qtn->width;
// valid = qtn->valid;
// q1 = qtn->q1;
// q2 = qtn->q2;
// q3 = qtn->q3;
// q4 = qtn->q4;
// rgbs = (color **)malloc(height * sizeof(color *));
// for (int i = 0; i < height; i++)
// rgbs[i] = (color *)malloc(width * sizeof(color));
// for (int i = 0; i < height; ++i)
// for (int j = 0; j < width; ++j)
// rgbs[i][j] = qtn->rgbs[i][j];
// } ----------------------------------QuadTreeFunc.h------------------------------------
#ifndef __QUADTREEFUNC_H__
#define __QUADTREEFUNC_H__#include "QuadTreeNode.h"struct color;void TreeToImage(QuadTreeNode *rt, color **img)
{if (rt->valid){for (int i = 0; i < rt->height; ++i)for (int j = 0; j < rt->width; ++j){img[i + rt->position.x][j + rt->position.y].r = rt->rgbs[i][j].r;img[i + rt->position.x][j + rt->position.y].g = rt->rgbs[i][j].g;img[i + rt->position.x][j + rt->position.y].b = rt->rgbs[i][j].b;}}else{TreeToImage(rt->q1, img);TreeToImage(rt->q2, img);TreeToImage(rt->q3, img);TreeToImage(rt->q4, img);}
}void TreeFuzzifyExtend(QuadTreeNode *rt, int Tolerance)
{if (rt->VarianceCalculate(Tolerance) || rt->width < 10 || rt->height < 10)// if(rt->RandomPuzzyTag() || rt->width < 10 || rt->height < 10){rt->Fuzzify();rt->valid = true;return;}int midwidth = 0, midheight = 0;rt->valid = false;midwidth = rt->width / 2;midheight = rt->height / 2;// subTree1rt->q1 = new QuadTreeNode(rt->position.x, rt->position.y, midheight, midwidth);rt->q1->valid = false;rt->q1->depth = rt->depth + 1;for (int i = 0; i < midheight; ++i)for (int j = 0; j < midwidth; ++j)rt->q1->rgbs[i][j] = rt->rgbs[i][j];// subTree2rt->q2 = new QuadTreeNode(rt->position.x, rt->position.y + midwidth, midheight, rt->width - midwidth);rt->q2->valid = false;rt->q2->depth = rt->depth + 1;for (int i = 0; i < midheight; ++i)for (int j = 0; j < rt->width - midwidth; ++j)rt->q2->rgbs[i][j] = rt->rgbs[i][midwidth + j];// subTree3rt->q3 = new QuadTreeNode(rt->position.x + midheight, rt->position.y, rt->height - midheight, midwidth);rt->q3->valid = false;rt->q3->depth = rt->depth + 1;for (int i = 0; i < rt->height - midheight; ++i)for (int j = 0; j < midwidth; ++j)rt->q3->rgbs[i][j] = rt->rgbs[midheight + i][j];// subTree4rt->q4 = new QuadTreeNode(rt->position.x + midheight, rt->position.y + midwidth, rt->height - midheight, rt->width - midwidth);rt->q4->valid = false;rt->q4->depth = rt->depth + 1;for (int i = 0; i < rt->height - midheight; ++i)for (int j = 0; j < rt->width - midwidth; ++j)rt->q4->rgbs[i][j] = rt->rgbs[midheight + i][midwidth + j];// 递归扩展TreeFuzzifyExtend(rt->q1, Tolerance);TreeFuzzifyExtend(rt->q2, Tolerance);TreeFuzzifyExtend(rt->q3, Tolerance);TreeFuzzifyExtend(rt->q4, Tolerance);
}#endif----------------------------------QuadImg_todo.cpp--------------------------------
#include
#include
#include
#include
#include "QuadTreeNode.h"
// #include "QuadTree.h"
#include "QuadTreeFunc.h"void printImage(char *fileName, int width, color **a);
// color color;// To get ppm image from jpeg file, please visit https://convertio.co/jpg-ppm/void readImage(int p, char *inFile, char *outFile) // Note that width == height here
{FILE *f = fopen(inFile, "rb");char u[3]; // placehoderint width, height, max_value;fscanf(f, "%s%d%d%d%c", u, &width, &height, &max_value, &u[0]);int i;color **colors, **img;colors = (color **)malloc(height * sizeof(color *));img = (color **)malloc(height * sizeof(color *));for (i = 0; i < height; i++){colors[i] = (color *)malloc(width * sizeof(color));img[i] = (color *)malloc(width * sizeof(color));}for (i = 0; i < height; i++)fread(colors[i], sizeof(color), width, f);fclose(f);//=============================================================QuadTreeNode *rt = new QuadTreeNode(colors, width, height);TreeFuzzifyExtend(rt,15);TreeToImage(rt, img);//=============================================================printImage(outFile, width, img);
}//注意！！！/
//因为题目所给的图像长宽相等，所以此处输出时，只传入了width参数，视作height=width!! //
//实际作为一个小型功能软件时需要进行修改！ //
//事实上，readImage()函数本来也视作height=width，不过我已经修改过了，此处需自行修改 //void printImage(char *fileName, int width, color **a) // Note that width == height here
{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(a[i], sizeof(color), width, f);fclose(f);
}// int main(int argc, char **argv)
int main()
{int tolerance = 0;char inFile[100];char outFile[100];// if (argc > 1){// tolerance = atoi(argv[1]);// inFile = argv[2];// outFile = argv[3];strcpy(inFile,"D:\\DataStructuresAndAlgorithms\\homework\\Experiment3-Quadtree-adaptive-fuzzy\\a.ppm");strcpy(outFile,"D:\\DataStructuresAndAlgorithms\\homework\\Experiment3-Quadtree-adaptive-fuzzy\\result.ppm");readImage(tolerance, inFile, outFile);}return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！