ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CÔNG NGHỆ
TIỂU LUẬN
MÔN HỌC XỬ LÝ ẢNH
Đề tài
Biên và các phương pháp dò biên ảnh
Ngưòi thực hiện: Trần Quang Duy
Lớp: K10T3
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
HÀ NỘI – 06/2004
Trang 2/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
MỤC LỤC
Phần 1 TỔNG QUAN VỀ BIÊN VÀ CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN 4
1.1. Vị trí của biên trong phân tích ảnh 4
1.2. Biên và các kỹ thuật dò biên 4
1.2.1. Khái niệm về biên 4
1.2.2. Phân loại các kỹ thuật phát hiện biên 5
1.2.3. Qui trình phát hiện biên trực tiếp 5
1.3. Một số phương pháp phát hiện biên cục bộ 6
1.3.1. Phương pháp gradient 6
1.3.2. Phương pháp Laplace 8
1.4. Các phương pháp do biên gián tiếp (phân vùng ảnh) 9
1.4.1. Giới thiệu 9
Phần 2 CHƯƠNG TRÌNH ỨNG DỤNG 10
2.1. Giới thiệu 10
2.2. Các chức năng trong chương trình 10
2.3. Chi tiết các chức năng dò biên và thuật toán 10
2.3.1. Dò biên theo kỹ thuật Gradient 10
2.3.2. Phương pháp dò biên theo kỹ thuật Laplace 12
2.3.3. Phương pháp dò biên gián tiếp 13

đoạn ảnh chủ yếu dựa vào biên.
Một điểm ảnh có thể coi là điểm biên nếu ở đó có sự thay đổi đột ngột
về mức xám. Tập hợp các điểm biên tạo thành biên hay đường bao ảnh của
ảnh (boundary).
Thí dụ, trong một ảnh nhị phân, một điểm có thể gọi là biên nếu đó là
điểm đen và có ít nhất một điểm trắng là lân cận.
Để hình dung tầm quan trọng của biên ta xét ví dụ sau: Khi người hoạ
sĩ vẽ một cái bàn gỗ, chỉ cần vài nét phác thảo về hình dáng như cái mặt
bàn, chân bàn mà không cần thêm các chi tiết khác, người xem đã có thể
Trang 4/26
Trích chọn
đặc tính
Phân
đoạn
Phân loại
Giải thích
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
nhận ra nó là một cái bàn. nếu ứng dụng của ta là phân lớp nhận diện đối
tượng, thì coi như nhiệm vụ đã hoàn thành. Tuy nhiên nếu đòi hỏi thêm về
các chi tiết khác như vân gỗ hay màu sắc,…thì với chừng ấy thông tin là
chưa đủ.
Nhìn chung về mặt toán học người ta coi điểm biên của ảnh là điểm có
sự biến đổi đột ngột về độ xám.Như vậy phát hiện biên một cách lý tưởng là
xác định được tất cả các đường bao trong các đối tượng. Định nghĩa toán
học của biên ở trên là cơ sở cho các kỹ thuật phát hiện biên. Điều quan trọng
là sự biến thiên mức xám giữa các ảnh trong một vùng thường là nhỏ, trong
khi đó biến thiên mức xám của điểm vùng giáp ranh (khi qua biên) lại khá
lớn.
1.2.2. Phân loại các kỹ thuật phát hiện biên
Xuất phát từ định nghĩa toán học của biên người ta thường sử dụng 2

Vì các kỹ thuật làm nổi biên có hiệu ứng phụ là tăng nhiễu , do vậy sẽ
có một số điểm biên giả cần loại bỏ.
b4) liên kết và trích chọn biên.
Như đã nói, phát hiện biên và phân vùng ảnh là một bài toán đối ngẫu.
vì thế cũng có thể phát hiện biên thông qua việc phân vùng ảnh.
1.3. Một số phương pháp phát hiện biên cục bộ
1.3.1. Phương pháp gradient
Phương pháp gradient là phương pháp dò biên cục bộ dựa vào cực
đạii của đạo hàm. Theo định nghĩa, gradient là một véctơ có các thành phần
biểu thị tốc độ thay đổi giá trị của điểm ảnh theo hai hướng x và y . các thành
phần của gradient được tính bởi:
df(x,y)
= fx
≈
f(x+dx,y) – f(x,y)
dx dx
df(x,y)
= fy
≈
f(x,y+dy) – f(x,y)
dy dy
với dx là khoảng cách giữa các điểm theo hướng x ( khoảng các tính bằng số
điểm) và tương tự với dy. Trên thực tế, người ta hay dùng với
dx = dy = 1
Trong kỹ thuật gradient, người ta chia thành 2 kỹ thuật (do dùng 2 toán
tử khác nhau): kỹ thuật gradient và kỹ thuật la bàn. kỹ thuật gradient dùng
toán tử gradient lấy đạo hàm theo hai hướng; còn kỹ thuật la bàn lấy đạo
hàm theo 8 hướng chính: Bắc, Nam, Đông ,Tây và Đông Bắc, Tây Bắc, Đông
Nam, Tây Nam.
1.3.1.1.Kỹ thuật gradient

1
(m,n) (1.3)
Chú ý: để giảm tính toán, công thức 1-2 được tính gần đúng bởi:
Trang 6/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
A
0
= | g
1
(m,n) | + | g
2
(m,n) |
Các toán tử đạo hàm được áp dụng là khá nhiều. ở đây ta chỉ xét một
số toán tử tiêu biểu: toán tử Robert, Sobel, Prewitt…
Trước tiên chúng ta xét toán tử Robert. Toán tử này do Robert đề xuất
vào năm 1965. Nó áp dụng trực tiếp của các công thức đạo hàm tại điểm
(x,y). với mỗi điểm ảnh I(x,y) của I, đạo hàm theo x, theo y được ký hiệu
tương ứng bởi g
x
, g
y
được tính:
g
x
= I(x +1,y) – I(x,y)
g
y
=I(x,y+1) – I(x,y)
điều này tương đương với việc chập ảnh với 2 mặt nạ H
1

1
(m,n) | , | g
2
(m,n) |)
Cần lưu ý rằng, do lạm dụng về ngôn từ, tuy ta lấy đạo hàm của ảnh
nhưng thực ra chỉ là mô phỏng và xấp xỉ đạo hàm bằng kỹ thuật nhân chập
do ảnh số là tín hiệu rời rạc, do vậy đạo hàm không tồn tại.
Trong kỹ thuật Sobel và prewtt người ta sử dụng 2 mặt nạ:
H1 =
-1 0 1
H2 =
-1 -1 -1
-1 0 1 0 0 0
-1 0 1 1 0 1
Ngang (hướng x) Dọc(hướng y)
a) mặt nạ Sobel
H1 =
-1 0 1
H2 =
-1 -2 -1
-2 0 2 0 0 0
-1 0 1 1 2 1
Trang 7/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
Ngang (hướng x) Dọc(hướng y)
b) mặt nạ Prewitt

H
1
=

thuật la bàn lấy đạo hàm theo 8 hướng chính: Bắc, Nam, Đông ,Tây và Đông
Bắc, Tây Bắc, Đông Nam, Tây Nam. Bằng cách sử dụng 8 mặt nạ cho 8
hướng khác nhau.
1.3.2. Phương pháp Laplace
Các phương pháp đánh giá Gradient ở trên làm việc khá tốt khi mà độ
sáng thay đổi rõ nét. Khi mức sáng thay đổi chậm, miền chuyển tiếp trải rộng,
phương pháp cho hiệu quả hơn đó là sử dụng phương pháp đạo hàm bậc
hai gọi là phương pháp Laplace. Kết quả nghiên cứu cho thấy phương pháp
Gradient rất nhậy cảm với nhiễu và thường tạo nên biên kép. Toán tử
Laplace dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ đạo hàm bậc hai. Dưới
đây là 3 kiểu mặt nạ hay dùng.
0 -1 0 -1 -1 -1 1 -2 1
H1=
-1
4 -1
H2
=
-1
8 -1 H2=
-2
8 -2
0 -1 0 -1 -1 -1 1 -2 1
Trang 8/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
Kỹ thuật laplace cho đường biên mảnh, tức là đường biên có độ rộng
bằng một pixel. Tuy nhiên, kỹ thuật này rất nhạy cảm với nhiễu vì đạo hàm
bậc hai thường không ổn định.
1.4. Các phương pháp do biên gián tiếp (phân vùng ảnh)
1.4.1. Giới thiệu
Như phần trên đã trình bày, Nếu bằng cách nào đấy, ta phân được ảnh

2.2. Các chức năng trong chương trình
Chương trình bao gồm các chức năng chính sau:
 Đọc một ảnh nhị phân: ảnh có thể là đen trắng, ảnh màu (16 màu hoặc
256 màu) dạng bitmap (*.bmp).
 Lưu ảnh: lưu ảnh đã biến đổi ra file
 Dò biên ảnh bao gồm các chức năng sau
o Theo kỹ thuật Gradient: bằng cách sử dụng toán tử Sobel và
Prewitt.
o Theo kỹ thuật Laplace: sử dụng toán tử Laplace-H2.
o Dò biên gián tiếp theo phân vùng ảnh: dò biên theo màu của ảnh.
2.3. Chi tiết các chức năng dò biên và thuật toán
2.3.1. Dò biên theo kỹ thuật Gradient
Theo như phần lý thuyết đã trình bày, kỹ thuật Gradient dò biên theo 2
hướng x và y bằng cách sử dụng hai mặt nạ nhân chập theo hai hướng
Chương trình sử dụng hai toán tử là Sobel và Prewitt như sau.
H1 =
-1 0 1
H2 =
-1 -1 -1
-1 0 1 0 0 0
-1 0 1 1 0 1
Ngang (hướng x) Dọc(hướng y)
a) mặt nạ Sobel
Trang 10/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
H1 =
-1 0 1
H2 =
-1 -2 -1
-2 0 2 0 0 0

Để dễ hiểu, phần dưới đây sẽ minh hoạ thêm về giải thuật này:
Ma trận ảnh vào Mặt nạ
Ma trận ảnh ra sau khi nhân chập
b11 b12 b13 b1n
b21 b22 b23 b2n
b31 b32 b33 b3nTrong đó:
b22=(a11*m11)+ (a12*m12)+ (a12*m13)+ (a21*m21) + (a22*m22) +
(a23*m23) + (a31*m31)+ (a32*m32)+ (a33*m33).
Các giá trị nằm trên đường viền được gán =0 (hay giá trị màu nền).
(b11,b12, b1n,b11 bn1,b1n bnn, bn1 bnn)
Đây là công thức tính Gx và Gy
Để tính giá trị điểm ảnh đầu ra, sử dụng công thức: G=|Gx|+ |Gy|
2.3.2. Phương pháp dò biên theo kỹ thuật Laplace
Kỹ thuật Laplace dò biên theo cách tính xấp xỉ đạo hàm bậc hai dựa
trên một mặt nạ. Chương trình sử dụng mặt nạ H2 trong cách dò biên theo kỹ
thuật Laplace.
-1 -1 -1
H2=
-1
8 -1
-1 -1 -1
Trang 12/26
a11 a12 a13 a1n
a21 a22 a23 a2n
a31 a32 a33 a3n
màu của các điểm ảnh.
Giả sử a và b là 2 giá trị màu của 2 điểm ảnh. Khoảng cách màu d
của a và b được tính như sau:
d(a,b)=|Ra-Rb| + |Ga-Gb| + |Ba-Bb|
Trong đó Ra: là giá trị màu đỏ tại điểm ảnh
Ga: là giá trị màu xanh (green)tại điểm ảnh
Ba: là giá trị màu xanh da trời (blue) tại điểm ảnh.
Nếu khoảng cách màu d=0 thì 2 điểm ảnh đó có cùng màu.
Đường biên giữ các vùng chính là các đường biên cần tìm.
Trang 13/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
 Thuật toán tìm đường biên dựa trên sự biến thiên giá trị màu
của các điểm ảnh.
Đầu vào: Ma trận điểm ảnh, khoảng cách màu tối thiểu
Đầu ra: Ma trận điểm ảnh mới (chứa các đường biên tìm thấy).
Giải thuật:
For (mỗi điểm ảnh của ảnh)
{
- Tính khoảng cách màu của điểm ảnh với các điểm ảnh lân
cận: Tính theo 8 hướng của điểm ảnh
if(Nếu có một khoảng cách màu lớn hơn khoảng cách màu
cho phép)
{
- Ghi nhận điểm ảnh này là một điểm biên mới.
}
}
2.4. Chương trình
2.4.1. Giao diện và các chức năng chính
Màn hình chính khi chạy có giao diện như sau:
Trang 14/26

Gx[0][0] = -1; Gx[0][1] = 0; Gx[0][2] = 1;
Gx[1][0] = -1; Gx[1][1] = 0; Gx[1][2] = 1;
Gx[2][0] = -1; Gx[2][1] = 0; Gx[2][2] = 1;
Gy[0][0] = -1; Gy[0][1] = -1; Gy[0][2] = -1;
Gy[1][0] = 0; Gy[1][1] = 0; Gy[1][2] = 0;
Gy[2][0] = 1; Gy[2][1] = 1; Gy[2][2] = 1;
Gradient(Gx,Gy);
// image->Filter(kernel,3,16,0);
UpdateAllViews(NULL);
}
Trang 18/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
bool CDemo3Doc::Gradient(long Gx[3][3], long Gy[3][3])
{
//neu khong co du lieu anh
if(!image->GetDIB()) return false;
// Gradient Algorithm
long sum;
long sumx,sumy;//gia tri tinh gx, gy
long x,y;
//long r,g,b;
long i,j,gx,gy;
//RGBQUAD c;
//CxImage tmp;
BYTE cindex;
//tmp=image->cop
CxImage tmp;
tmp.Copy (*image);
long xmin,xmax,ymin,ymax;
xmin = ymin = 0;

CString s1;
cindex=image-
>GetPixelIndex(x+i,y+j);
gx=Gx[i+1][j+1];
sumx=sumx+ (cindex* gx);
}
//tinh theo chieu y
for( i=-1; i<=1 ; i++)
for(j=-1; j<=1; j++)
{
//lay gia tri mau
cindex=image-
>GetPixelIndex(x+i,y+j);
gy=Gy[i+1][j+1];
sumy=sumy+ (cindex* gy);
}
//lay xap xi
sum=abs(sumx)+abs(sumy);
sum=(BYTE)min(255, sum);
}
//AfxMessageBox(sum);
tmp.SetPixelIndex(x,y,255-(BYTE)sum);
}
}
}
}
//chuyen doi anh
image->Transfer(tmp);
return true;
}

return *img;
}
void CDemo3Doc::OnMethodPrewitt()
{
// TODO: Add your command handler code here
// TODO: Add your command handler code here
if (image==0) return;
if (!image->IsValid()) return;
Trang 21/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
long Gx[3][3];
long Gy[3][3];
Gx[0][0] = -1; Gx[0][1] = 0; Gx[0][2] = 1;
Gx[1][0] = -2; Gx[1][1] = 0; Gx[1][2] = 2;
Gx[2][0] = -1; Gx[2][1] = 0; Gx[2][2] = 1;
/* 3x3 GY Sobel mask. Ref: www.cee.hw.ac.uk/hipr/html/sobel.html */
Gy[0][0] = -1; Gy[0][1]=-2; Gy[0][2] =-1;
Gy[1][0] = 0; Gy[1][1] = 0; Gy[1][2] = 0;
Gy[2][0] = 1; Gy[2][1] = 2; Gy[2][2] = 1;
if(Gradient(Gx,Gy)==false) AfxMessageBox("Khong co du lieu anh");;
UpdateAllViews(NULL);
}
bool CDemo3Doc::Laplace(long G[3][3])
{
//neu khong co du lieu anh
if(!image->GetDIB()) return false;
// Gradient Algorithm
long sum;
// long sumx;
long x,y;

{
//tinh theo chieu x
for( i=-1; i<=1 ; i++)
for(j=-1; j<=1; j++)
{
//lay gia tri mau
cindex=image-
>GetPixelIndex(x+i,y+j);
//lay gia tri ma tran Gx tuong
ung
//gx=Gx[i+1 + 3*[j+1)];
//gx=Gx[j+1 + 3*[i+1)];
g=G[i+1][j+1];
sum=sum+ (cindex* g);
// sum=min(255,sum);
}
sum=(BYTE)min(255, 255-sum);
}
//AfxMessageBox(sum);
tmp.SetPixelIndex(x,y,(BYTE)sum);
//tmp.SetPixelIndex(x,y,0);
}
}
}
}
//chuyen doi anh
// image->Transfer(LamManhBien(&tmp));
Trang 23/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
image->Transfer(tmp);

//CoArray
CxImage tmp;
tmp.Copy (*image);
Trang 24/26
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên
long xmin,xmax,ymin,ymax;
xmin = ymin = 0;
xmax =(long) image->GetWidth(); ymax=(long)image->GetHeight();
for(y=ymin; y<ymax; y++)
{
for(x=xmin; x<xmax; x++)
{
//dat mau trang cho anh tam
tmp.SetPixelColor(x,y,RGB(255,255,255));
}
}
//bc=image->GetPixelIndex (0,0);
//neu anh la 8bit/1pixel
if ((image->GetBpp() ==8) || (image->GetBpp() ==4))
{
for(y=ymin; y<ymax; y++)
{
for(x=xmin; x<xmax; x++)
{
//dat mau den cho anh tam
//tmp.SetPixelColor(x,y,RGB(0,0,0));
c=image->GetPixelColor (x,y);
// if(image->GetPixelIndex (x,y)==image->GetPixelIndex (0,0))
{
c1=image->GetPixelColor(x-1,y);