圖像處理與識別課程報告-基於二值圖像的邊界提取和4方向鏈碼表示
一、 背景
二、 原理及程序設計
1. 邊界提取
2. 邊界的鏈碼表示
2.1 邊界4方向鏈碼
2.2 邊界的起點歸一化鏈碼
2.3 邊界的差分鏈碼
2.4 起點歸一化的差分鏈碼
三、 程序的運行結果和結果評價
1. 運行結果
2. 結果評價
四、 採用示例圖像驗證程序有效性
1. 測試圖片準備
2. 對測試圖片進行邊界提取和鏈碼表示
五、 參考文獻
附錄:
一、 背景
圖像邊界處理是圖像處理與分析中最基礎內容之一,也是至今沒有得到完滿解決的一類問題,邊界處理技術主要有邊界的提取和表示。邊界在圖像中所佔比例較小,是圖像的一個重要特徵。邊界技術可廣泛應用於工業設計、醫學圖像三維重建、虛擬視景生成、圖像識別等方面,多年以來,一直吸引著許多不同領域的研究人員。邊界表示是以物體邊界為基礎,定義和描述幾何形體的方法。圖像邊界表示在模式識別、圖像處理以及計算機視覺等領域扮演著十分重要的角色。人們對圖像邊界表示進行了大量研究,提出了許多方法,如鏈碼、Fourier級數、有向圖等等。由於鏈碼在有效降低存儲空間的同時能準確表示邊界,使其成為圖像邊界表示使用最廣泛的方法之一 。Yong Kui Liu等根據鏈碼方向出現的概率不同,採用Huffman編碼規則對鏈碼方向進行重新編碼,縮短了平均的編碼碼長。陸宗騏等介紹了鏈碼分析邊界形狀的方法,將其應用到細胞圖像的分割,取得了較好效果。尚振宏等從數字直線的鏈碼特徵得到啟發,以線段元為基本單位進行直線的構造,準確地檢測出圖像中物體邊界中的直線。餘霞等將二維鏈碼編碼擴展到三維空間,對三維心血管進行編碼,實現對不同時刻的三維心血管圖像中心血管中軸線的匹配。
Freeman鏈碼技術是一種用來刻畫數字圖像的邊界的方法。該方法首先需要定義一個方向坐標,常用的兩個方向坐標是如圖1的四方向和八方向坐標。然後根據坐標來對圖像的邊界按照Moore邊界追蹤算法進行數字編碼,使得圖像的邊界被一一地轉換成一個數字序列。如圖1所示,採用四方向坐標只能刻畫出的具有四個方向的邊界,而本報告即是採用四方向坐標來刻畫數字圖像的邊界的。
圖1 左圖為4方向鏈碼坐標,右圖為8方向鏈碼坐標
「4方向鏈碼」表示和「8方向鏈碼」表示的邊界表示方法如圖2所示,選取圖像邊界上紅色標記像素點為鏈碼起始點,沿順時針方向搜索。
由於「4方向鏈碼」存在額外取像素的可能,所以「4方向鏈碼」的鏈碼長度一般比「8方向鏈碼」長。圖2(b)中黃色標記的像素點為「4方向鏈碼點」未標記像素點為「8方向鏈碼點」,圖2(c)中黃色標記的像素點為「8方向鏈碼點」未標記像素點為「4方向鏈碼點」。
圖2(b)的4方向鏈碼:00303232121201。
圖2(c)的8方向鏈碼:007654331。
圖2 (a)為原始圖像,(b)為「4方向鏈碼點」,(c)為「8方向鏈碼點」
二、 原理及程序設計
該報告所述的內容分為兩塊,一是圖像邊界的提取,二是圖像邊界的4方向鏈碼表示,故下文中所述鏈碼均為4方向鏈碼形式。
1. 邊界提取
圖像的表示方法有兩種:一種是基於外部特性的邊界表示和另一種是基於內部特性的區域表示。
邊界和邊緣的定義:圖像的邊界和邊緣是兩個經常別混淆的概念,在數字圖像處理中他們有著不一樣的定義。邊界是指一個區域R的邊界是區域中像素的集合,邊界內的點存在該區域中一個或者多個不在R中鄰點。邊緣是指圖像中灰度發生急劇變化(導數值超過閾值)的區域。邊界只考察其領點是否屬於給定集合,是二值判斷。邊緣考察灰度級的差別,粒度更細。有限區域的邊界形成一條閉合通路。邊緣可能不閉合。當數字圖像是二值圖像時,邊界等於邊緣。
邊界點的提取和判別方法:首先對圖像進行二值化處理,然後遍歷二值圖像的每一個像素,以1值像素為參考點,搜索參考點四周鄰域方向上的像素,確定參考點周圍是否存在至少一個像素為0的點(背景點),若存在,則參考點為邊界點,否則為非邊界點。
邊界表示方法:邊界的表示關注的是圖像中區域的形狀特徵,常用的方法有鏈碼、邊界分段、多邊形近似、標記圖等。
區域表示方法:區域的表示關注的是圖像中區域的的灰度、顏色、紋理等特徵,常用的方法有四叉樹、骨架等。
如下圖2(a)所示,給定一張500x500的灰度+二值化處理後的圖像,中間白色區域是一個200x200的前景區域,背景為黑色。藉助Matlab工具通過編程對下圖2(a)中前景進行4方向搜索的邊界提取所得結果如圖2(b)。
圖2 邊界提取實例
Matlab對圖2(a)進行4方向邊界提取的程序框圖如圖3所示。
圖3 邊界點判斷程序流程圖
l 邊界提取的matlab程序實例如下:
%對灰度和二值化處理的圖像img進行4方向邊界提取並將邊界賦給imgn
[m n]=size(img);
imgn=zeros(m,n); %邊界標記圖像
ed=[-1 1;0 1;1 1;1 0;1 -1;0 -1;-1 -1;-1 0]%從左下角(或下方)像素開始逆時針搜索參考點周圍八領域尋找背景點0,%ed=[0 -1;1 0;0 1;-1 0];
for i=2:m-1
for j=2:n-1
if img(i,j)==1 %如果當前像素是前景像素0或則1
for k=1:8
ii=i+ed(k,1);
jj=j+ed(k,2);
if img(ii,jj)==1 %判斷當前像素周圍是否有背景像素,若有則證明該像素為邊界像素點,後將該邊界像素點標記在imgn圖像(是黑色背景)中
imgn(i,j)=1;
end
end
end
end
end
figure(4);
%subplot(221);
imshow(imgn);%imshow(imgn,[]);
title('灰度+二值圖像內邊界');
1. 邊界的鏈碼表示
2.1 邊界4方向鏈碼
鏈碼通過給定方向和單位長度的線段(單位長度的線段是指單個像素)來表示輪廓或者邊界,鏈碼的建立是一個輪廓(邊界)跟蹤的過程。典型的表示方法是根據鏈的斜率不同分為4方向鏈碼和8方向鏈碼。每一段的方向是用數字編號方法進行編碼。
4方向鏈碼:在鏈碼的四個方向上移動,以數字集合{i|i=0,1,2,3}編碼來表示與x軸的夾角為90°× i的四個方向,如下圖4(a)(b)所示分別為4方向鏈碼表示和坐標表示。
鏈碼表示的優點:能有效降低存儲空間的同時準確的表示目標的邊界,使其成為圖像邊界表示使用最廣泛的方法之一。
圖4 (a)為4方向鏈碼表示,(b)為坐標表示
鏈碼起點:邊界的鏈碼依賴起始點。由於鏈碼的起始點可以任意選擇,對同一邊界如果選用不同的起始點,常常會得到不同的鏈碼,通常鏈碼起點的選取方法是從二值圖像左上角像素點開始,自上而下自左而右逐像素點掃描,當遇到邊界點時開始邊界跟蹤,這樣做的好處是可以確定的知道圖像左上部分不存在邊界點故不必重複搜索。
邊界跟蹤的搜索方向:根據每一條邊界鏈上前一邊界點鏈碼值的奇偶性確定後一邊界點的搜索方向。
終點的確定:每一條邊界鏈跟蹤回到起始點(對於封閉輪廓)或末尾點搜索不到新的後續點(對於非封閉或者岔路線段)即完成一個邊界鏈的跟蹤。
對已知邊界點的處理:每一條邊界鏈,從起始點之後,即從第二點起,每搜索完成一次邊界點,將該邊界點置為前景色1,最後回到起始點或最後一個點,再把起始點置前景色1。
Matlab對圖2(b)的邊界進行4方向鏈碼表示程序框圖如圖5所示。
圖5 圖像邊界進行4方向鏈碼表示程序框圖
l 對圖2(b)的邊界進行4方向鏈碼表示matlab程序如下:
%對imgn邊界進行順時針4方向鏈碼鏈碼表示,並將4方向鏈碼賦給Code
B=bwboundaries(imgn);
[nr,nc]=size(B{1});
Code=[];
Hc=B{1}(2,1)-B{1}(1,1);
%L=B{1}(2,2)-B{1}(1,2);
if Hc<=0%順時針邊界
for i=2:nr
x=B{1}(i,1)-B{1}(i-1,1);
y=B{1}(i,2)-B{1}(i-1,2);
if x==1&&y==0
Code=[Code,3];
%elseif x==1&&y==1
%Code=[Code,1];
elseif x==0&&y==1
Code=[Code,0]; %Code=[Code,2];
%elseif x==-1&&y==1
%Code=[Code,3];
elseif x==-1&&y==0
Code=[Code,1]; %Code=[Code,4];
%elseif x==-1&&y==-1
%Code=[Code,5];
elseif x==0&&y==-1
Code=[Code,2];%Code=[Code,6];
%elseif x==1&&y==-1
%Code=[Code,7];
elseif x==1&&y==1
Code=[Code,[3,0]];
elseif x==-1&&y==1
Code=[Code,[0,1]];
elseif x==-1&&y==-1
Code=[Code,[1,2]];
elseif x==1&&y==-1
Code=[Code,[2,3]];
end
fprintf('4方向鏈碼:\n');
fprintf('Code的列數:');
[r,c]=size(Code);
disp(c);
disp(Code);
Code0=Code';
%xlswrite('LM.xlsx',Code0,'sheet2');%可用於將數據存於表格中
2.2 邊界的起點歸一化鏈碼
起始點歸一化鏈碼:將鏈碼看作一個循環序列,依次取各個邊界點作為起始點,由於所選起始點不同所得鏈碼也各不相同,這時從得到的所有鏈碼中選取構成自然數值最小的碼作為歸一化結果,該最小碼值的點即為歸一化後的起始點。
對2.1中所得鏈碼進行起點歸一化的matlab程序流程圖如圖6所示。
圖6 鏈碼進行起點歸一化的matlab程序流程圖
l 鏈碼進行起點歸一化的matlab程序
%對鏈碼Code進行歸一化得到min,並將歸一化的4方向鏈碼賦給code1
a=Code;
min=Code;
for i=1:size(a,2)
k=a(1);
for j=2:size(a,2)
a(j-1)=a(j);
a(size(a,2))=k;
for i=1:size(a,2)
if a(i)<min(i)
min=a;
end
if a(i)>min(i)
break;
Code1=min;
fprintf('起點歸一化4方向鏈碼:\n');
fprintf('Code1的列數:');
[r,c]=size(Code1);
disp(Code1);
Code1=Code1';
xlswrite('LM.xlsx',Code1,'sheet6');%可用於將數據存於表格中
2.3 邊界的差分鏈碼
鏈碼具有平移不變性,即當邊界平移時,其鏈碼不發生改變。但是,當邊界旋轉時,則鏈碼會改變。若用鏈碼的一階差分碼作為新的碼。(一階差分即為相鄰兩個方向之間的變化值),當原邊界旋轉為新邊界時,其碼鏈改變,但它們的一階差分碼不改變。
差分鏈碼的用途:綜上一階差分碼旋轉不變的特性,所以差分鏈碼可用於處理圖像邊界旋轉後的邊界表示問題。
計算方法:通過計算相鄰兩個元素方向變化(逆時針方向)的數字得到。就是前一個數字變化到後一個數字需要經過的步數,注意是逆時針方向,比如1->1經過0步,1->0經過3步。
對2.1中所得鏈碼進行差分歸一化的matlab程序流程圖如圖7所示。
圖7 鏈碼進行差分歸一化的matlab程序流程圖
l 鏈碼進行差分歸一化的matlab程序
% 對Code差分處理,將Code的差分鏈碼賦給SubCode。
Code2=[Code,Code(1)];%用於生成差分鏈碼時的後補第一元素的鏈碼Code2。
% 生成普通4方向差分鏈碼
SubCode=[];
[r,c] = size(Code2);
for i=2:c
cz=Code2(i)-Code2(i-1);
if cz>=0
SubCode =[SubCode,cz];
elseif cz<0
cz=4+cz;
SubCode =[SubCode,cz];
end
end
fprintf('4方向差分鏈碼:\n');
fprintf('SubCode的列數:');
[r,c]=size(SubCode);
disp(c);
disp(SubCode);
SubCode2=SubCode';
xlswrite('LM.xlsx',SubCode2,'sheet7');%可用於將數據存於表格中
2.4 起點歸一化的差分鏈碼
起點歸一化的差分鏈碼實現同2.2方法一樣,即是用差分鏈碼將原始鏈碼替換後做起點歸一化處理。
對2.3中所得差分鏈碼進行起點歸一化的matlab程序流程圖如圖8所示。
圖8 差分鏈碼進行起點歸一化的matlab程序流程圖
l 差分鏈碼進行起點歸一化的matlab程序
% 對SubCode進行歸一化,並將生成的歸一化差分鏈碼賦給Code3
a=SubCode;
min=SubCode;
for i=1:size(a,2)
k=a(1);
for j=2:size(a,2)
a(j-1)=a(j);
end
a(size(a,2))=k;
for i=1:size(a,2)
if a(i)<min(i)
min=a;
end
if a(i)>min(i)
break;
end
end
end
Code3=min;
fprintf('起點歸一化4方向差分鏈碼:\n');
fprintf('Code3的列數:');
[r,c]=size(Code3);
disp(c);
disp(Code3);
Code3=Code3';
xlswrite('LM.xlsx',Code3,'sheet8');%可用於將數據存於表格中
三、 程序的運行結果和結果評價
1. 運行結果
如圖9所示,給出四幅大小均為500x500的測試圖片,圖片中前景為200x200白色正方形,(a)中正方形各邊與圖片邊界平行,(b)中正方形為(a)中向右平移,(c)中正方形為(a)中正方形繞中心旋轉45度,(d)中正方形為(a)中繞中心旋轉26度。
圖9 用於測試的圖像
分別對圖9中測試圖像求其4方向鏈碼、歸一化4方向鏈碼、差分鏈碼和歸一化差分鏈碼得到運行結果,並將結果整理到表格中,其實部分結果如圖10所示,紅色方框為圖9(a)鏈碼、藍色方框為圖9(b)鏈碼、綠色方框為圖9(c)鏈碼、黃色方框為圖9(d)鏈碼,鏈碼類型順序均與圖10中紅色方框標註相同。
圖10 鏈碼結果
詳細鏈碼數據見附件表LM。
詳細Matlab代碼見附錄。
2. 結果評價
1. 對比紅框和藍框所得鏈碼結果可驗證鏈碼具有平移不變性。
2. 差分鏈碼的運行結果發現圖像中邊界發生旋轉以後,前後所得差分鏈碼並不相同,造成此現象的原因可能有兩個,
① 原始圖像前景旋轉後進行灰度和二值化處理時所得像素矩陣中前景數據並不是只發生了旋轉位移,可能所得邊界數據量發生變化。
② 原始圖像前景旋轉後進行進行邊界提取,然後對邊界進行4方向鏈碼表示所得鏈碼長度發生改變,這是由於4方向鏈碼在對傾斜邊界進行鏈碼獲取時存在額外取像素的現象,而且,邊界傾斜程度不同其額外取像素的程度也不同。
四、 採用示例圖像驗證程序有效性
1. 測試圖片準備
使用作圖軟體生成大小為7*6,背景為白色,前景用黑色表示的測試圖片,如圖11所示。
圖11 用於驗證鏈碼的42像素小圖像
注意:需根據二值圖像中前景點的實際值來調整圖像邊界的點的判斷條件:
①當前景點為1時,則判斷參考點8領域是否存在背景點0,若存在則該點為前景點並在空圖像中將對應參考點坐標的點置為1;
②當前景點為0時,則判斷參考點8領域是否存在背景點1,若存在則該點為前景點並在空圖像中將對應參考點坐標的點置為1。
根據以上兩種情況,對程序中進行4方向邊界提取的代碼部分進行相應修改。
2. 對測試圖片進行邊界提取和鏈碼表示
對圖11測試圖片進行4方向邊界提取需要判斷參考點的8領域方向上是否存在背景點,所生成的邊界圖像理論上如圖12(a)中黃色區域所示,圖12(b)為用matlab對圖11進行邊界提取後所生成的邊界圖像imgn對應的數據矩陣圖,從數據矩陣圖可知,「1」所在位置與圖12(a)中黃色標記的邊界像素點一一對應,由此可以驗證程序對圖像進行4方向邊界提取的正確性。
圖12 圖11測試圖像所對應理論邊界圖像和真實邊界的數據矩陣圖
若選取圖12(a)中紅色像素點為鏈碼起始點,對提取得到的邊界圖imgn進行順時針「4方向鏈碼」表示,所得邊界的理論鏈碼值應為:01003032321212。
如圖13所示,是採用matlab程序對圖11的邊界圖imgn進行「4方向鏈碼」表示的程序運行結果,將下圖中鏈碼結果與理論鏈碼值進行對比,發現兩者完全一致,由此可以驗證程序對圖像邊界進行4方向鏈碼表示的正確性。
圖13 測試圖的4方向鏈碼
對理論鏈碼值進行起點歸一化處理可得理論歸一化鏈碼值為:0030323212111201。
由matlab程序對鏈碼進行起點歸一化後的結果如圖14所示,將其與理論的歸一化鏈碼值進行比較可知,兩者完全相同,由此可以驗證程序對鏈碼進行歸一化表示的正確性。
圖14 測試圖的起點歸一化鏈碼
對理論鏈碼值進行差分處理可得理論差分鏈碼值為:13031331331312。
由matlab程序對鏈碼進行差分處理後的結果如圖15所示,將其與理論差分鏈碼值進行比較可知,兩者完全一致,由此可以驗證程序對鏈碼進行差分表示的正確性。
圖15 測試圖的差分鏈碼
詳細matlab程序見附錄。
五、 參考文獻
[1] 阮秋琦. 數字圖像處理學[M]. 北京: 電子工業出版社,2001. RUAN Q Q. Digital image processing [M]. Beijing: Publishing House of Electronics Industry,2001.( in Chinese)
[2] 劉姍姍,劉君妍,韋玉春.提取圖像定向邊界的結構元素快速設計方法[J].南京師範大學學報( 工程技 術版),2017-06,17(2):57-62.
[3] 裴姍,章騰.基於 Freeman 鏈碼的幾何圖形識別算法[J].計算技術與自動化,2018-09,37(3):115-117.
[4] 唐振軍,章顯全.圖像邊界的鏈碼表示研究[J]圖像處理,2005:105-107.
[5] 鄧仕超,李偉明,龍芋宏,高興宇.一種改進的二值圖像邊界跟蹤與邊界鏈碼獲取算法[J].雷射與光電 子學進展,2018:1-7
附錄:
私信獲取matlab全部代碼!