ĐẠ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


2.3.3. Phương pháp dò biên gián tiếp 12
2.4. Chương trình 13
2.4.1. Giao diện và các chức năng chính 13
2.4.2. Chức năng Gradient 14
2.4.3. Chức năng Laplace 15
2.4.4. Chức năng dò biên gián tiếp(Indirect Method) 16
2.5. Một số hàm và thủ tục chính 17

Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
3
/
25
Phần 1 TỔNG QUAN VỀ BIÊN VÀ CÁC PHƯƠNG PHÁP
PHÁT HIỆN BIÊN

1.1. Vị trí của biên trong phân tích ảnh
Phân tích ảnh là một qua trình gồm nhiều giai đoạn. Đầu tiên là giai đoạn
tiền xử lý ảnh. Sau giai đoạn này, ảnh được tăng cường hay được khôi phục
đề làm nồi các đặc tính ( feature extraction ), tiếp theo là phân đoạn ảnh
(segmentation) thành các phần tử. Thí dụ, như phân đoạn dựa theo biên,
dựa theo vùng,… Và tuỳ theo các ứng dựng, giai đoạn tiếp theo có thể là
nhận dạng ảnh ( phân thành các lớp có miêu tả) hay là giải thích và miêu tả
ảnh. Hình 1.1 mô tả tóm lược các bước của quá trình phân tích ảnh: Ảnh đầu ra của
quá trình tiền XL


25
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
phương pháp phát hiện biên sau:
1.2.2.1. Phương pháp phát hiện biên trực tiếp:
Phương pháp này nhằm làm nổi biên dựa vào sự biến thiên về giá trị độ
sáng của điểm ảnh. kỹ thuật chủ yếu dùng phát hiện biên ở đây là kỹ thuật
đạo hàm. Nếu lấy đạo hàm bậc nhất của ảnh ta có phương pháp Gradient;
nếu lấy đạo hàm bậc hai ta có kỹ thuật Laplace. Hai phương pháp trên được
gọi là phương pháp dò biên cục bộ. ngoài ra người ta còn sử dụng phương
pháp “đii theo đường bao”: dựa vào nguyên lý qui hoạch hoạt động và được
gọi là phương pháp dò biên tổng thể.
1.2.2.2. Phương pháp gián tiếp:
Nếu bằng cách nào đấy , ta phân được ảnh thành các vùng thì đường
phân ranh giữa các vùng đó chính là biên. việc phân vùng ảnh thường dựa
vào kết cấu (texture) bề mặt của ảnh.
Cũng cần lưu ý rằng, kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối
ngẫu của nhau. Thực vậy, dò biên để thực hiện phân lớp đối tượng và một
khi đã phân lớp xong có nghĩa là đã phân vùng được ảnh. Và ngược lại, khi
phân vùng, ảnh đã phân lập được thành các đối tượng, ta có thể phát hiện


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
Kỹ thuật này sử dụng một cặp mặt nạ H
1
và H
2
trực giao ( theo 2 hướng
vuông góc). Nếu định nghĩa g
1

(m,n) | + | g
2
(m,n) |
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
6
/
25
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
và H
2
:

A
2
= max( | g
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

c) mặt nạ đẳng hướng (Isometric)
Gradient được tính xấp xỉ công thức
Gx=Hx

I và Gy=Hy

I (Hx nhân chập với I, Hy nhân chập với I)
Thực tế cho thấy rằng các toán tử Sobel và Prewitt tốt hơn toán tử Sobel bởi
chúng ít nhậy cảm với nhiễu.
1.3.1.2. Kỹ thuật La bàn
Về phương pháp kỹ thuật này tương tự kỹ thuật Gradient. Tuy
nhiên,điểm khác, kỹ thuật Gradient chỉ lấy đạo hàm theo 2 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. 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

vào biên hay những vung liên thông. Tiêu chuẩn để xác định các vùng liên
thông có thể là cùng mức xám, cùng màu, v v… Vùng ảnh là một thuộc tính
quan trọng của ảnh. Nói đến vùng ảnh là nói đến kết cấu bề mặt. Đường bao
quanh một vùng ảnh gọi là biên ảnh.
Một số phương pháp phân vùng chính như:
 Phân vùng ảnh dựa theo ngưỡng biên độ
 Phân vùng ảnh dựa theo miền đồng nhất
 Phân vùng ảnh dựa theo đường biên Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
9
/
25
Phần 2 CHƯƠNG TRÌNH ỨNG DỤNG
2.1. Giới thiệu
Phần 1 đã trình bày khái quát về vai trò và tầm quan trọng của biên trong
quá trình xử lý ảnh. Đồng thời, phần 1 cũng đã trình bày khái niệm về biên
ảnh cũng như các phương pháp dò biên của ảnh nhị phân trong máy tính.
Để áp dụng lý thuyết đã trình bày ở phần 1, Phần này sẽ giới thiệu một
chương trình ứng dụng tìm biên của ảnh. Chương trình này áp dụng các kỹ
thuật do biên trực tiếp là kỹ thuật Gradient và Laplace. Trong kỹ thuật
Gradient, các toán tử Sobel và Prewitt được sử dụng.
Tiếp đó chương trình cũng giới thiệu một phương pháp dò biên gián tiếp
thông qua việc phân vùng ảnh.
Chương trình được viết trên ngôn ngữ Visual C++ 6.0.
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:

25
H1 =

-1 0 1
H2 =

-1 -2 -1
-2 0 2 0 0 0
-1 0 1 1 2 1
Ngang (hướng x) Dọc(hướng y)
b) mặt nạ Prewitt
Giả sử Gx và Gy là 2 ma trận điểm ảnh thu được sau khi nhân chập với 2
mặt nạ theo hai hướng tương ứng. Ma trận điểm ảnh G được tính xấp xỉ theo
công thức sau:
G=|Gx| + |Gy|
 Thuật toán dò biên theo phương pháp Gradient như sau:
Đầu vào: ma trận ảnh cần tìm biên:
mặt nạ I1 và I2
Đầu ra: Một ma trận ảnh (chứa các đường biên được tìm thấy).
Giải thuật
// Gradient Algorithm
For (mỗi điểm ảnh của ảnh)
if(Nếu điểm ảnh nẳm trên đường viền ảnh)
Gán giá trị các điểm ảnh trên đường viền ảnh =0 (hoặc
bằng màu nền ảnh).
else
{

b11 b12 b13 b1n
b21 b22 b23 b2n
b31 b32 b33 b3n Trong đó:
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
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
12
/
25

Gọi G là ma trận điểm thu được sau khi nhân chập ma trận điểm ảnh (của
ảnh cần tìm biên)với mặt nạ H2.

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.
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
13
/
25

 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:


Nhận xét:
 Khi áp dụng hai toán tử này cho ta cùng một kết quả tương tự nhau
 Phương pháp này tạo nên đường biên rất đậm
2.4.3. Chức năng Laplace
Chức năng này bao gồm
 chức năng Laplace-h2: sử dựng mặt nạ H2  Kết quả dò biên theo kỹ thuật Laplace
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
16
/
252.4.4. Chức năng dò biên gián tiếp(Indirect Method)

 Kết quả dò biên theo phương pháp này
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
17
/
252.5. Một số hàm và thủ tục chính

{
//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;
xmax =(long) image->GetWidth(); ymax=(long)image-
>GetHeight();
//neu anh la 8bit/1pixel
if ((image->GetBpp() ==8)||(image->GetBpp() ==4))
{
for(y=ymin; y<ymax; y++)
{
for(x=xmin; x<xmax; x++)
{
sumx=0;
sumy=0;
sum=0;
//kiem tra toa do x,y co nam trong anh hay khong


//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;
}

CxImage CDemo3Doc::LamManhBien(CxImage *img)

posindex=img->GetPixelIndex(x+1,y+1) ;
//neu index tai diem x,y khong lon hon tai diem x-1,y-1
va x+1,y+1 thi loai bo
if ((index<=preindex || index<=posindex))
img->SetPixelColor( x,y,RGB(0,0,0)); //dat mau
den

}
}

}
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;

Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
21
/
25

long Gx[3][3];
long Gy[3][3];

CxImage tmp;
tmp.Copy (*image);
long xmin,xmax,ymin,ymax;
xmin = ymin = 0;
xmax =(long) image->GetWidth(); ymax=(long)image->GetHeight();
//neu anh la 8bit/1pixel
if ((image->GetBpp() ==8) || (image->GetBpp() ==4))
{
for(y=ymin; y<ymax; y++)
{
for(x=xmin; x<xmax; x++)
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
22
/
25

{
sum=0;
//kiem tra toa do x,y co nam trong anh hay khong
if (image->SelectionIsInside(x,y))
{
//xu ly cac toa do o duong vien anh
if(y==0 || y == ymax-1)
sum=0;
else if(x==0 || x==xmax-1)
sum=0;

//tinh xap xi laplace

// image->Transfer(LamManhBien(&tmp));
Tiểu luận môn xử lý ảnh - Biên và các phương pháp dò biên

Trang
23
/
25 image->Transfer(tmp);
return true;
}

void CDemo3Doc::OnMethodLaplace()
{
// TODO: Add your command handler code here
if (image==0) return;
if (!image->IsValid()) return;

long Gx[3][3];

Gx[0][0] = -1; Gx[0][1] =-1; Gx[0][2]= -1;
Gx[1][0] = -1; Gx[1][1] = 8; Gx[1][2]= -1;
Gx[2][0] = -1; Gx[2][1] =-1; Gx[2][2]= -1;
if(Laplace(Gx)==false) AfxMessageBox("Khong co du lieu anh");
UpdateAllViews(NULL);

}

bool CDemo3Doc::DoBien()

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);
c2=image->GetPixelColor(x+1,y);
c3=image->GetPixelColor(x,y-1);
c4=image->GetPixelColor(x,y+1);
c5=image->GetPixelColor(x-1,y-1);
c6=image->GetPixelColor(x+1,y+1);


//dat mau den tai cac diem bien
bc=tmp.GetPixelColor(x,y-1);
//neu diem truoc la diem bien
if(bc.rgbBlue==0 ||bc.rgbGreen ==0 || bc.rgbRed ==0 )
{
tmp.SetPixelColor(x,y,RGB(0,0,0));
}
else
{
tmp.SetPixelColor(x,y,RGB(0,0,0));

}

// }
}

}
}
}

image->Transfer(tmp);
return true;
}

void CDemo3Doc::OnIndirectMethod()
{
// TODO: Add your command handler code here
DoBien();
UpdateAllViews(NULL);