数据结构与算法大作业

2024-04-05 12:32| 来源: 网络整理| 查看: 265

四叉树自适应模糊一.实验要求二.背景知识PPM文件格式理解四叉树高斯模糊三.思路总结：四.代码实现(由于未到作业截止时间，只给出代码框架，后续更新)Quadtree.hQuadtree.cppmain.cpp 五. 效果展示六.总结反思

一.实验要求

能够正确的对图像建立四叉树；

对于输入的图像，四叉树能够输出模糊的结果

对颜色相近的区域进行模糊

二.背景知识 PPM文件格式理解

可通过十六进制编辑器 010editor 打开查看二进制信息附件三了官网获取 010editor

信息含义P6指明PPM的编码格式2156 2156图像大小为2156*2156255RGB的每个色彩值范围为0~255C0 91 89（16进制第二行）表示一个像素的RGB颜色(后面类推)

用 Photoshop 打开ppm文件查看图片

四叉树

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

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

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

类似的，较之四叉树，八叉树将场景从二维空间延伸到了三维空间。

更多关于四叉树的抽象的描述

高斯模糊

它将正态分布（又名"高斯分布"）用于图像处理。本质上，它是一种数据平滑技术（data smoothing）

原理大概就是，每一个像素都取周边像素的平均值，“中间点"取"周围点"的平均值，实现数值上的一种"平滑化”，图形上的模糊效果

这里用结论就好，具体数学处理我们不用太过关心

用到一个做高斯模糊用的权重矩阵：

{{0.0453542, 0.0566406, 0.0453542}, {0.0566406, 0.0707355, 0.0566406}, {0.0453542, 0.0566406, 0.0453542}}

对于RGB三个数值分别经过多轮高斯模糊处理详见后面

三.思路总结：先将图片整个像素信息存储进一个数据类型（后面用color构成的二维数组来存）抽象四叉树结点，每一个结点包含一部分二维图像的信息根据对应二维图像像建立四叉树（图像的模糊、压缩）——若其图像的R或G或B值任意一个大于标准设定方差，则该子叶继续往下划分；若小于等于，则不再划分，并将该子叶的矩形区域内的所有RGB值赋予其为平均值再通过高斯模糊处理数据（图像的平滑处理）再将此数据输出到结果ppm文件四.代码实现(由于未到作业截止时间，只给出代码框架，后续更新) Quadtree.h struct color{ unsigned char r; unsigned char g; unsigned char b; } ; int operator== (color c1, color c2); //color operator==(const color other); void Guass(color **colors, int width); //对处理过的图像（细分矩阵的程度不同）进行高斯模糊，半径为1 class Node { private: int width; //当前像素区块的宽度 int height; //当前像素区块的高度 int x; //当前像素区块左上角顶点像素的横坐标 int y; //当前像素区块左上角顶点像素的纵坐标 int mean_r; //Rmean int mean_g; //Gmean int mean_b; //Bmean Node *children1; //pointer to four other node Node *children2; //pointer to four other node Node *children3; //pointer to four other node Node *children4; //pointer to four other node public: Node(); ~Node(); Node(int input_width, int input_height, int x, int y); void QuadCreateBranch(color **colors, int fangcha); void QuadPrint(color **colors); }; Quadtree.cpp #include "Quadtree.h" #include using namespace std; Node::Node() { //TODO mean_r = 0; mean_g = 0; mean_b = 0; // p = nullptr; width = 0; height = 0; x = 0; y = 0; children1 =children2 =children3= children4= nullptr; } Node::Node(int input_width, int input_height, int x, int y) { children1 = nullptr; children2 = nullptr; children3 = nullptr; children4 = nullptr; mean_r = 0; mean_g = 0; mean_b = 0; width = input_width; height = input_height; this->x = x; this->y = y; } void Node::QuadCreateBranch(color **colors, int fangcha) { 求该节点对应二维图像的RGB均值 int ave_r = 0; int ave_g = 0; int ave_b = 0; for (int i=x;iQuadCreateBranch(colors,fangcha); children3= new Node(width/2,height/2,x, y+height/2); children3->QuadCreateBranch(colors,fangcha); children4 = new Node(width/2,height/2,x+width/2,y+height/2); children4->QuadCreateBranch(colors,fangcha); } } else { if ( (fangcha_r > fangcha || fangcha_g > fangcha || fangcha_b > fangcha) && width > 100){ children1 = new Node(width/2,height/2, x+width/2, y); children1->QuadCreateBranch(colors, fangcha); children2 = new Node(width/2,height/2,x, y); children2->QuadCreateBranch(colors,fangcha); children3= new Node(width/2,height/2,x, y+height/2); children3->QuadCreateBranch(colors,fangcha); children4 = new Node(width/2,height/2,x+width/2,y+height/2); children4->QuadCreateBranch(colors,fangcha); } } } void Node::QuadPrint(color **colors) { for (int i=x;iQuadPrint(colors); if (children3 != nullptr) children3->QuadPrint(colors); if (children4 != nullptr) children4->QuadPrint(colors); } int operator==(color c1, color c2){ if (c1.b == c2.b && c1.r == c2.r && c1.g == c2.g) return true; return false; } /*第二部分：高斯模糊*/ void Guass(color **colors, 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

【本文地址】

公司简介

联系我们