區(qū)域生長算法 全局分類 C++ & matlab
// 注：本內容為作者原創(chuàng)，禁止在其他網(wǎng)站復述內容以及用于商業(yè)盈利，如需引用，請標明出處：http://www.rzrgm.cn/lv-anchoret/
今天我們來介紹用C++算法如何來實現(xiàn)圖像分割算法中的區(qū)域生長算法
我們解決的是對一整張圖像所有內容進行區(qū)域生長分類，當然，如果是對圖像中的某一類型進行區(qū)域生長可能更容易一些
個人理解
區(qū)域生長算法需要確定一個閾值，這個值代表同一類圖像信息灰度值的差值，比如，我要一個人臉圖（假設眼睛是藍色的），頭發(fā)是黑色的但是不同光線反射原因或者位置不同，圖像中顯示的灰度顏色值有5、10、3等，雖然灰度值不一樣，但是他們代表的都是黑色，都是頭發(fā)，區(qū)域生長，就是把這些相似灰度值的一類事物統(tǒng)一標注顯示，這也就達到了分類識別的目的，關于閾值，比如上述的頭發(fā)，我們需要將所有是頭發(fā)的像素點都標注出來，那么我們的閾值就應該設置為10，如果設置為3，可能灰度值為3和5的點會統(tǒng)一識別，但是10就被排除在外了。
算法核心就是一個bfs，設立一個種子點，向四周擴張，如果相鄰的點的灰度值相對于種子點在閾值范圍之內，那么，我們把它識別并包含統(tǒng)一進來，擴張完畢之后，所有相似的一類圖像將被統(tǒng)一標注。
關于標注我們還需要說一下，一開始，想起了四色定理，即用四種顏色就可以吧整個地圖分類標注且相鄰類別顏色不同，后來想了想還不如把同一類型區(qū)域中的所有點都設置為種子點灰度像素值。
之后想起來我們光線追蹤一直用的ppm彩色文件格式，索性將灰度值轉成rgb彩色圖看著更爽
區(qū)域生長算法流程
1. 找種子點
2. 擴張原則
3. 終止條件
數(shù)據(jù)介紹
我們的數(shù)據(jù)是一張灰度圖 ： 見 紋理相冊夾中的第二張圖
我們處理輸出的是一張彩色圖像，圖像格式是我們光線追蹤的文件格式 .ppm，用我們光線追蹤的圖片解析器（ppmviewer）就能打開（沒有的也沒關系，搜索一下，下載不超過十幾秒，超輕量級ppm解讀器）
我們都知道，C/C++ 中讀取圖像麻煩，特別是這種.jpg復雜格式數(shù)據(jù)，所以，我們用matlab先把圖像讀出來，輸出到一個TXT中，存儲為二維矩陣形式，然后用C++代碼讀取TXT文件內容，存儲到一個二維數(shù)據(jù)序列中。（都有代碼在后面）
我們側重實現(xiàn)算法本身，所以關于圖像的讀取和寫入我們不做過多描述
算法介紹
算法自命名：首次左上區(qū)域生長算法
時間復雜度：O(圖像大小*種子數(shù)量*log（種子數(shù)量）)
一、區(qū)域生長的三大要素確立：
（1）生長合并規(guī)則：
用戶自定義閾值，根據(jù)種子點和當前點的差值，如果在閾值之內，那么合并，將當前點的灰度值設為種子灰度值
（2）種子選取：
將圖像左上角第一個點作為第一個種子，在擴張的過程中第一個不符合生長合并規(guī)則的位置，作為下一次生長的種子，即首次選定，后期自適應確定。
（3）算法結束：
種子為空
二、優(yōu)缺點
該算法的優(yōu)點： 針對大型全局生長而衍生
該算法種子不會將同一個位置作為種子多次重復生長（時間空間復雜度優(yōu)化）
某個種子在開始生長時，如果已經(jīng)被包含于另一個種子的生長區(qū)域中，那么該種子將不會進行生長（時間復雜度優(yōu)化）
該算法的缺點： 首次選定法不能用合適的灰度代表整個區(qū)域，只能是坐標小的點的灰度值
生長出來的區(qū)域可能不是很完美，因為該區(qū)域是由該區(qū)域坐標最小的點生長而成的。
三、灰度值轉rgb算法設計
因為要將單一的灰度值映射到r、g、b,使其代表的顏色具有獨特性
這個可以自己設計，我的設計如下：
四、構架設計
含有一個類 —— regional
數(shù)據(jù)成員
_img：用于存儲圖像灰度矩陣
reset：用于記錄某個位置的灰度是否被重置
_delt：閾值
成員函數(shù)
readfile：讀圖像灰度矩陣文件
bfs：進行區(qū)域生長
out：輸出處理后的圖像灰度矩陣
readout：讀取處理后的圖像灰度矩陣文件
gograph：將灰度圖像轉為rgb圖像，由于ppmview顯示空間有限，所以將此圖劃分為6塊（將原圖像分為3行2列的6塊），分別輸出6個圖像
流程圖如下：
五、數(shù)據(jù)結構設計：（C++描述）
用bfs算法進行的話，必然需要隊列，但是種子們不能用隊列去存，某個種子進行生長的時候可以用隊列記錄每一個生長狀態(tài)
此法采用8領域進行生長
用隊列存儲當前種子生長過程中的狀態(tài)點，進行bfs擴展，確定該種子生長所形成的區(qū)域
用set容器存儲各個種子，保證了種子點唯一性，即優(yōu)點2，同時，set容器還會根據(jù)位置自動排序，所以導致了缺點2，其次，set容器的存取操作的時間復雜度均為O(n log n)
Bfs狀態(tài)采用只包含x、y坐標的一個結構體
六、效果與討論
采用C++描述的首次左上區(qū)域生長算法針對2012*1881的灰度衛(wèi)星圖像矩陣數(shù)據(jù)處理時間為：78.9s
閾值為20
圖1
首先藍色圈所代表的部分，如果是水域的深淺，那么這一塊還是被劃分的很清楚的，大致分了5部分
再看下閾值為25的圖
圖2
如我們所預期的那樣，圖1中藍色圈的水深劃分等級更少了
其次，我們看圖1的紅色圈代表的水體，內部中間劃分出來的區(qū)域更小了，或者說水體的邊緣區(qū)域擴張了。
再如，黑色圈代表的水域，中間的黑色圈有一塊東西，它的區(qū)域更小了，不利于捕捉細微的水內狀況
如果圖1的黑色內的小黑圈部分看不太清楚，那么可以看一下下面這個，都是一樣的
XnView打開效果
圖3
如果把黃色部分看做是豎著的地質錘，那么圖2顯然少了錘頭~
還有水邊一片房子聚集地，也被基本劃分為一種色調
圖4
而針對下圖以及圖4以及原圖上方一片森林山脈，將各種處理方法進行疊加，效果可能會更好，方案如下：
有很多星星點點的噪聲，可以選擇先去噪聲，但是，效果也不是很好
如果要將其納入到統(tǒng)一的大片區(qū)域中，還是選擇先做一個平滑處理，將其尖銳的邊緣過渡更加平滑些，再進行區(qū)域生長，加以閾值調整，星點可能會減少，可能還存在一些，但是不會那么顯眼，和周圍環(huán)境的色差不會那么大了
圖5
七、代碼
matlab 代碼
matlab：
function writetxt I = imread('poyanghu.jpg'); fid = fopen('image.txt','w'); [x,y] = size(I); fprintf(fid,'%d %d\n',x,y); for i = 1:x for j = 1:y fprintf(fid,'%d ',I(i,j)); end fprintf(fid,'\n'); end fclose(fid);
C++:
regional.h
//regional.h
#pragma once namespace region { constexpr int dir[8][2] { {-1,-1}, {-1, 0}, {-1, 1}, { 0,-1}, { 0, 1}, { 1,-1}, { 1, 0}, { 1, 1} }; constexpr size_t H = 2012; constexpr size_t L = 1881; class regional { public: struct pos { int _x, _y; pos(const int a, const int b) :_x(a), _y(b) { } bool operator<(const pos& p)const { if (_x == p._x) return _y < p._y; return _x < p._x; } }; public: regional(const size_t delt); void readfile(); void bfs(); void out(); void readout(); void gograph()const; private: short _img[2012 + 1][1881 + 1]; bool reset[H + 1][L + 1]; size_t _delt; }; }
regional.cpp
#include "regional.h" #include <iostream> #include <fstream> #include <queue> #include <set> using namespace std; using namespace region; regional::regional(const size_t delt) :_delt(delt) { memset(reset, false, sizeof reset); } void regional::readfile() { ifstream infile; infile.open("image.txt"); if (!infile.is_open()) cerr << "open failed" << endl; int x, y; infile >> x >> y; for (int i = 1; i <= x; ++i) for (int j = 1; j <= y; ++j) infile >> _img[i][j]; infile.close(); } void regional::bfs() { queue<pos> Qcurrent; set<pos> Qnew; Qnew.insert(pos(1, 1)); while (Qnew.size()) { Qcurrent.push(*Qnew.begin()); Qnew.erase(Qnew.begin()); if (reset[Qcurrent.front()._x][Qcurrent.front()._y])//該種子點已經(jīng)訪問過 { Qcurrent.pop(); continue; } while (Qcurrent.size()) { pos seed = Qcurrent.front(); reset[seed._x][seed._y] = true; Qcurrent.pop(); for (int trans = 0; trans < 8; ++trans) { pos p(seed._x + dir[trans][0], seed._y + dir[trans][1]); if (p._x > 0 && p._x <= H && p._y > 0 && p._y <= L && !reset[p._x][p._y]) if (abs(_img[p._x][p._y] - _img[seed._x][seed._y]) < _delt) { _img[p._x][p._y] = _img[seed._x][seed._y]; reset[p._x][p._y] = true; Qcurrent.push(p); } else Qnew.insert(p); } } } } void regional::out() { ofstream outfile; outfile.open("outall.txt"); if (!outfile.is_open()) cerr << "open failed" << endl; for (int i = 1; i <= H; ++i) { for (int j = 1; j <= L; ++j) outfile << _img[i][j] << " "; outfile << endl; } outfile.close(); } void regional::readout() { ifstream infile("outall.txt"); if (!infile.is_open()) { cerr << "error open" << endl; } for (int i = 1; i <= H; ++i) for (int j = 1; j <= L; ++j) infile >> _img[i][j]; infile.close(); } void regional::gograph()const { ofstream file; auto left = [&](int cnt) { for (int i = (cnt - 1) * 700 + 1; i <= 700 * cnt; ++i) for (int j = 1; j <= 1000; ++j) file << (int)((0.2 + float(_img[i][j] % 10) / 10)*_img[i][j]) << " " << (int)((0.5 + float(_img[i][j] % 10) / 10)*_img[i][j]) << " " << (int)((0.7 + float(_img[i][j] % 10) / 10)*_img[i][j]) << endl; }; auto right = [&](int cnt) { for (int i = (cnt - 1) * 700 + 1; i <= 700 * cnt; ++i) for (int j = L - 1000 + 1; j <= L; ++j) file << (int)((0.2 + float(_img[i][j] % 10) / 10)*_img[i][j]) << " " << (int)((0.5 + float(_img[i][j] % 10) / 10)*_img[i][j]) << " " << (int)((0.7 + float(_img[i][j] % 10) / 10)*_img[i][j]) << endl; }; file.open("slip1'.ppm"); file << "P3" << endl; file << 1000 << " " << 700 << endl; file << "255" << endl; left(1); file.close(); file.open("slip2'.ppm"); file << "P3" << endl; file << 1000 << " " << 700 << endl; file << "255" << endl; right(1); file.close(); file.open("slip3'.ppm"); file << "P3" << endl; file << 1000 << " " << 700 << endl; file << "255" << endl; left(2); file.close(); file.open("slip4'.ppm"); file << "P3" << endl; file << 1000 << " " << 700 << endl; file << "255" << endl; right(2); file.close(); file.open("slip5'.ppm"); file << "P3" << endl; file << 1000 << " " << 700 << endl; file << "255" << endl; left(3); file.close(); file.open("slip6'.ppm"); file << "P3" << endl; file << 1000 << " " << 700 << endl; file << "255" << endl; right(3); file.close(); }
main.cpp
#include "regional.h" using namespace region; #include <iostream> #include <fstream> #define stds std:: int main() { regional reg(25); reg.readfile(); reg.bfs(); reg.out(); //reg.readout(); reg.gograph(); stds cout << "complished" << stds endl; return 0; }
感謝您的閱讀，生活愉快~
浙公網(wǎng)安備 33010602011771號