一.實驗要求
能夠正確的對圖像建立四叉樹；
對于輸入的圖像，四叉樹能夠輸出模糊的結(jié)果
對顏色相近的區(qū)域進行模糊
二.背景知識
PPM文件格式理解
可通過十六進制編輯器 010editor 打開查看二進制信息
官網(wǎng)獲取 010editor
| 信息 | 含義 |
|---|---|
| P6 | 指明PPM的編碼格式 |
| 2156 2156 | 圖像大小為2156*2156 |
| 255 | RGB的每個色彩值范圍為0~255 |
| C0 91 89（16進制第二行） | 表示一個像素的RGB顏色(后面類推) |
用 Photoshop 打開ppm文件查看圖片
四叉樹
四叉樹，又稱四元樹，是一種樹狀數(shù)據(jù)結(jié)構(gòu)。四元樹常應用于二維空間數(shù)據(jù)的分析與分類
四叉樹（Q-Tree）是一種樹形數(shù)據(jù)結(jié)構(gòu)。四叉樹的定義是：它的每個節(jié)點下至多可以有四個子節(jié)點，通常把一部分二維空間細分為四個象限或區(qū)域并把該區(qū)域里的相關(guān)信息存入到四叉樹節(jié)點中 。這個區(qū)域可以是正方形、矩形或是任意形狀。以下為四叉樹的二維空間結(jié)構(gòu)(左)和存儲結(jié)構(gòu)(右)示意圖（注意節(jié)點顏色與網(wǎng)格邊框顏色）：
四叉樹的每一個節(jié)點代表一個矩形區(qū)域（如上圖黑色的根節(jié)點代表最外圍黑色邊框的矩形區(qū)域），每一個矩形區(qū)域又可劃分為四個小矩形區(qū)域，這四個小矩形區(qū)域作為四個子節(jié)點所代表的矩形區(qū)域。（遞歸）
四叉樹把2D空間進行了分組
類似的，較之四叉樹，八叉樹將場景從二維空間延伸到了三維空間。
更多關(guān)于四叉樹的抽象的描述
高斯模糊
它將正態(tài)分布（又名"高斯分布"）用于圖像處理。本質(zhì)上，它是一種數(shù)據(jù)平滑技術(shù)（data smoothing）
原理大概就是，每一個像素都取周邊像素的平均值，“中間點"取"周圍點"的平均值，實現(xiàn)數(shù)值上的一種"平滑化”，圖形上的模糊效果
這里用結(jié)論就好， 具體數(shù)學處理 我們不用太過關(guān)心
用到一個做高斯模糊用的權(quán)重矩陣：
{{0.0453542, 0.0566406, 0.0453542},
{0.0566406, 0.0707355, 0.0566406},
{0.0453542, 0.0566406, 0.0453542}}
對于RGB三個數(shù)值分別經(jīng)過多輪高斯模糊處理詳見后面
三.思路總結(jié)：
- 先將圖片整個像素信息存儲進一個數(shù)據(jù)類型（后面用color構(gòu)成的二維數(shù)組來存）
- 抽象四叉樹結(jié)點，每一個結(jié)點包含一部分二維圖像的信息
- 根據(jù)對應二維圖像像建立四叉樹（圖像的模糊、壓縮）——若其圖像的R或G或B值任意一個大于標準設定方差，則該子葉繼續(xù)往下劃分； 若小于等于，則不再劃分，并將該子葉的矩形區(qū)域內(nèi)的所有RGB值賦予其為平均值
- 再通過高斯模糊處理數(shù)據(jù)（圖像的平滑處理）
- 再將此數(shù)據(jù)輸出到結(jié)果ppm文件
四.代碼實現(xiàn)(由于未到作業(yè)截止時間，只給出代碼框架，后續(xù)更新)
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; //當前像素區(qū)塊的寬度
int height; //當前像素區(qū)塊的高度
int x; //當前像素區(qū)塊左上角頂點像素的橫坐標
int y; //當前像素區(qū)塊左上角頂點像素的縱坐標
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 <iostream>
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) {
求該節(jié)點對應二維圖像的RGB均值
int ave_r = 0;
int ave_g = 0;
int ave_b = 0;
for (int i=x;i<x+width;i++){
for (int j=y;j<y+height;j++){
ave_r += colors[i][j].r;
ave_g += colors[i][j].g;
ave_b += colors[i][j].b;
}
}
ave_r /= width*height;ave_g /= width*height;ave_b /= width*height;
mean_r = ave_r;
mean_g = ave_g;
mean_b = ave_b;
求該節(jié)點的RGB方差
long long fangcha_r = 0;
long long fangcha_g = 0;
long long fangcha_b = 0;
for (int i=x;i<x+width;i++){
for (int j=y;j<y+height;j++){
fangcha_r += (colors[i][j].r - ave_r)*(colors[i][j].r - ave_r);
fangcha_g += (colors[i][j].g - ave_g)*(colors[i][j].g - ave_g);
fangcha_b += (colors[i][j].b - ave_b)*(colors[i][j].b - ave_b);
}
}
fangcha_r /= width*height;fangcha_g /= width*height;fangcha_b /= width*height;
方差滿足一定條件就遞歸建立兒子
if (fangcha <= 1000){
if ( (fangcha_r > fangcha || fangcha_g > fangcha || fangcha_b > fangcha) ){
/*創(chuàng)建各孩子分支*/
// int input_width, int input_height, int x, int y
// |
// children2 | children1
// ______________
// |
// children3 | children4
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);
}
}
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;i<x+width;i++){
for (int j=y;j<y+height;j++){
colors[i][j].r = mean_r;
colors[i][j].g = mean_g;
colors[i][j].b = mean_b;
}
}
if (children1 != nullptr) children1->QuadPrint(colors);
if (children2 != nullptr) children2->QuadPrint(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<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++)//對于每一個點都進行高斯模糊，之前每一個點都處理過了，相當于壓縮后（拋去細節(jié)）再模糊？
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;
}
}
main.cpp
#include "Quadtree.h"
#include <iostream>
using namespace std;
int main(){
char *inFile="/Project/C/Quadtree Adaptive Blurring/yue.ppm";
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]);
將圖片整個像素信息存儲進colors
int i;
color **colors;//[height][width]
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);
給定模糊程度
int FangCha,tolerance;
int FangCha_L[6]={100,300,500,900, 1400,2200};
cout << "input tolerance(1~5):";
cin >> tolerance;
FangCha = FangCha_L[tolerance];
遞歸建立四叉樹
Node *root = new Node(width, height, 0, 0);
root->QuadCreateBranch(colors, FangCha);
樹寫到colors里
root->QuadPrint(colors);
多次高斯模糊
for (int i = 1;i<=20;i++)//這里為20次
Guass(colors,width);
將此數(shù)據(jù)輸出到結(jié)果ppm文件
char *outfile = "/Project/C/Quadtree Adaptive Blurring/result.ppm";
FILE *rf = fopen(outfile, "wb");
fprintf(rf, "P6\n");
fprintf(rf, "%d %d\n", width, width);
fprintf(rf, "255\n");
for (int i = 0; i < width; i++)
fwrite(colors[i], sizeof(color), width, f);
fclose(f);
cout << "Blurring finished, please preview result.ppm with ps" << endl;
}
五. 效果展示
本實現(xiàn)可輸入模糊程度1~5（憑視覺效果讓模糊程度對應方差）
當然也可以自己給定任意非負整數(shù)為方差。
分別對應以下圖片：
程度1（對應方差300）
程度2（對應方差500）
程度3（對應方差900）
程度4（對應方差1400）；（一些比價精細的地方如螃蟹腿，盡管方差很大，但是不希望再繼續(xù)建立子節(jié)點，所以添加條件：圖片大小<100，不再遞歸建立四叉樹）
程度5（對應方差2200） 驚現(xiàn)？！??！（咱可不是黑子）
用寫好的程序模糊處理 自家piu亮的瓜蛋兒~嘿嘿嘿
六.總結(jié)反思
本次作業(yè)個人感覺難在將圖像信息和四叉樹結(jié)構(gòu)對應的抽象上，各個模塊功能的實現(xiàn)還是比較簡單。
代碼個人感覺寫得還是很漂亮，當然做這么一個視覺反饋很直觀的東西還是比較有趣的，出于時間精力有限，后續(xù)同學們有精力還可以嘗試添加可視化可交互的圖像處理小程序，向P圖軟件那樣快捷調(diào)節(jié)模糊程度，或者在選定區(qū)域內(nèi)模糊
當然不足很明顯，本作業(yè)雖然實現(xiàn)了圖片模糊，“屏蔽”掉了圖片的一部分信息，但是借助ppm文件儲存模糊圖片信息，其大小并無顯著改變
文章來源：http://www.zghlxwxcb.cn/news/detail-805275.html
參考文章文章來源地址http://www.zghlxwxcb.cn/news/detail-805275.html
- https://blog.csdn.net/zhanxinhang/article/details/6706217
- https://blog.csdn.net/kinghzkingkkk/article/details/70226214
- https://blog.csdn.net/m0_68136379/article/details/129100656
- https://blog.csdn.net/Quincuntial/article/details/50625389
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法大作業(yè)——四叉樹自適應模糊的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
