Bài giảng Xử lý tín hiệu và mã hóa - Chương 4: Phát hiện biên và phân vùng ảnh - Phạm Việt Hà

Xử lý tín hiệu và mã hóa
(Master program)
Giảng viên: TS. Phạm Việt Hà
Email: phamvietha@gmail.com
ĐT CQ: (04).37544486
Địa chỉ CQ: 122 Hoàng Quốc Việt, Cầu Giấy, Hà Nội
1
Chương 4. Phát hiện biên và phân vùng ảnh
Viện Khoa học Kỹ thuật Bưu điện 2
4.1 Biên và kỹ thuật phát hiện biên
4.1.1 Phương pháp phát hiện biên trực tiếp
4.1.2 Phương pháp phát hiện biên gián tiếp
4.2 Phân vùng ảnh và phương pháp phân vùng ảnh
4.2.1 Phân vùng ảnh dựa theo ngưỡng biên độ
4.2.2 Phương pháp phân vùng ảnh
4.1. Biên và kỹ thuật phát hiện biên
Viện Khoa học Kỹ thuật Bưu điện 3
Biên là vấn đề quan trọng trong trích chọn đặc điểm nhằm tiến tới hiểu ảnh. Cho 
đến nay chưa có định nghĩa chính xác về biên. Trong mỗi ứng dụng người ta đưa
ra các độ đo khác nhau về biên. Một trong có độ đo đó là độ đo về sự thay đổi
đột ngột cấp xám. 
Một số khái niệm cơ bản:
 Điểm biên: Một điểm ảnh được coi là điểm biên nếu có sự thay đổi nhanh
hoặc đột ngột về mức xám (hoặc màu).
Ví dụ đối với ảnh đen trắng, một điểm được gọi là điểm biên nếu nó là điểm đen
và có ít nhất một điểm trắng nằm bên cạnh.
 Đường biên (đường bao): Tập hợp các điểm biên liên tiếp tạo thành một
đường biên hay đường bao.
4.1. Biên và kỹ thuật phát hiện biên
Viện Khoa học Kỹ thuật Bưu điện 4
 Ý nghĩa của đường biên trong xử lý ảnh:
 Đường biên là một loại đặc trưng cục bộ tiêu biểu trong phân tích, nhận
dạng ảnh.
 Thứ hai, người ta sử dụng biên làm phân cách các vùng xám (màu) cách
biệt.
4.1. Biên và kỹ thuật phát hiện biên
Viện Khoa học Kỹ thuật Bưu điện 5
 Phân loại các kỹ thuật phát hiện biên:
 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
đường biên dựa vào biến thiên về giá trị độ sáng (mức xám) của điểm ảnh.
Kỹ thuật chủ yếu là dùng 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.
 Phương pháp gián tiếp: Nếu bằng cách nào đấy ta phân ảnh thành
các vùng ảnh thì đường phân ranh giữa các vùng đó chính là biên.
4.1. Biên và kỹ thuật phát hiện biên
Viện Khoa học Kỹ thuật Bưu điện 6
 Quy trình phát hiện biên:
 B1. Khử nhiễu ảnh
Vì ảnh thu nhận thường có nhiễu, nên bước đầu tiên là phải khử nhiễu. việc
khử nhiễu được thực hiện bằng các kỹ thuật khử nhiễu khác nhau.
B2. Làm nổi biên
Tiếp theo là làm nổi biên bởi các toán tử đạo hàm.
B3. Định vị điểm biên
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 hoặc ngược lại
.
4.1. Biên và kỹ thuật phát hiện biên
Viện Khoa học Kỹ thuật Bưu điện 7
 So sánh phương pháp xác định biên ảnh trực tiếp và gián tiếp:
 Phương pháp phát hiện biên trực tiếp:
Hiệu quả và ít chịu ảnh hưởng của nhiễu
Ảnh có sự biến thiên độ sáng không đột ngột thì phương pháp tỏ ra kém hiệu quả
Kết quả của phương pháp là đường biên
 Phương pháp phát hiện biên gián tiếp:
Khó cài đặt và sử dụng
Ảnh có sự biến thiên độ sáng không đột ngột thì phương pháp áp dụng khá tốt
Kết quả của phương pháp là ảnh biên
4.1.1. Phương pháp phát hiện biên trực tiếp
Viện Khoa học Kỹ thuật Bưu điện 8
4.1.1.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 giá trị cực đại của
đạo hàm. Gradient là vector cho thấy tốc độ thay đổi giá trị độ chói của các điểm
ảnh theo hướng nhất định.
dx và dy là khoảng cách giữa các điểm theo hướng x và y. Trên thực tế thường
dùng dx=1, dy=1.
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 9
Nhận xét: Tuy nói là lấy đạo hàm nhưng thực chất chỉ là mô phỏng và xấp xỉ
đạo hàm bằng các kỹ thuật nhân chập vì ảnh số là tín hiệu rời rạc nên đạo hàm
không tồn tại
Khi ảnh số được biểu diễn như ma trận các điểm ảnh phân bố theo dòng và cột,
gradient rời rạc theo hướng x sẽ là:
Mặt nạ nhân chập theo hướng x là Hx =
Gradient theo hướng y sẽ là:
Mặt nạ nhân chập theo hướng y là Hy =
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 10
 Ví dụ:
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 11
 Ví dụ:
Làm nổi đường biên sử dụng phương pháp
gradient: 
a- ảnh gốc;
b- lấy đạo hàm riêng theo hướng y;
c- lấy đạo hàm riêng theo hướng x;
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 12
 Kỹ thuật Prewitt
Kỹ thuật sử dụng 2 mặt nạ chập xấp xỉ đạo hàm theo 2 hướng x và y:
Các bước tính toán:
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 13
 Kỹ thuật Prewitt
Ví dụ:
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 14
 Kỹ thuật Sobel
Kỹ thuật sử dụng 2 mặt nạ chập xấp xỉ đạo hàm theo 2 hướng x và y:
Các bước tính toán tương tự như Prewitt
+ Bước 1:
+ Bước 2: 
+ Bước 3: Tách ngưỡng theo θ 
1 nếu ≥ θ
I(x, y) =
0 nếu ngược lại
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 15
 Kỹ thuật Sobel
| | + | |= θ =34 
0172070
8017207
8801720
888017
0172070
8017207
8801720
888017
7000000
6700000
5670000
4567000
3456700
2345670
1234567
01000
00100
00010
00001
03440140
160344014
161603440
161616034
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 16
 Kỹ thuật la bàn
 Toán tử la bàn đo gradient theo một số hướng đã chọn. Ta kí hiệu gk
là gradient la bàn theo hướng θk=π/2 +2kπ với k=0,1, 2,7.
 Như vậy ta có gradient E theo 8 hướng ngược chiều kim đồng hồ.
 Bộ lọc H1, H2, H3,, H8 tương ứng với 8 hướng: 0o, 45o, 90o, 135o,
180o,225o,315o.
 Nếu ta kí hiệu , i=1, 2, 8 là gradient thu được theo 8 hướng bởi 8 mặt nạ,
biên độ gradient tại (x, y) được tính như sau:
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 17
 Kỹ thuật la bàn
 Toán tử Kirsh:
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 18
 Kỹ thuật la bàn
Đáp ứng của mặt nạ tại vùng ảnh có độ màu không đổi sẽ bằng 0.
4.1.1.1. Phương pháp Gradient
Viện Khoa học Kỹ thuật Bưu điện 19
Nhận xét:
 Phương pháp gradient tốt cho các ảnh có độ xám biến đổi nhiều. Khi ảnh có độ
xám biến đổi chậm thì dùng phương pháp Laplace.
 Phương pháp Sobel lấy xấp xỉ đạo hàm theo các trục, căn cứ vào điều kiện để
xác định một điểm có phải là biên không.
4.1.1.2. Phương pháp Laplace
Viện Khoa học Kỹ thuật Bưu điện 20
Khi mức xám thay đổi chậm, các đường biên không rõ nét, miền chuyển tiếp
tương đối rộng, phương pháp hiệu quả hơn là dùng đạo hàm bậc hai mà ta gọi là
phương pháp Laplace.
Việc xấp xỉ đạo hàm bậc hai cho tín hiệu rời rạc (tạm thời xét từng chiều) được
thực hiện như sau:
Tương tự: 
4.1.1.2. Phương pháp Laplace
Viện Khoa học Kỹ thuật Bưu điện 21
 Toán tử Laplace hai chiều rời rạc có dạng:
 Dẫn tới: 
 Thông thường người ta dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ rời rạc đạo
hàm bậc hai Laplace. Dưới đây là ba kiểu mặt nạ thường dùng
4.1.1.2. Phương pháp Laplace
Viện Khoa học Kỹ thuật Bưu điện 22
Làm nổi đường biên sử dụng phương pháp Laplace với mặt nạ H1 và H2
4.1.1. Phương pháp phát hiện biên trực tiếp
Viện Khoa học Kỹ thuật Bưu điện 23
 Cần xác định mức ngưỡng (phân ngưỡng) để loại bỏ các điểm ảnh không phải
là điểm cực đại (điểm biên cục bộ) 
4.1.1. Phương pháp phát hiện biên trực tiếp
Viện Khoa học Kỹ thuật Bưu điện 24
Kỹ thuật phát hiện biên trực tiếp:
 Ảnh gốc f(x,y) được đưa vào khối làm nổi đường biên.
 Ảnh G(x,y) là ảnh gốc đã được tăng cường biên độ đường biên giữa các vùng
ảnh.
 Tại khối so sánh, người ta so sánh giá trị các điểm ảnh G(x,y) với mức ngưỡng
T để xác định vị trí các điểm có mức thay đổi độ chói lớn.
 G(x,y) <TL: có sự thay đổi mức chói từ cao xuống thấp
G(x,y) >TH: có sự thay đổi mức chói từ thấp lên cao
TL và TH: là giá trị mức ngưỡng thấp và cao
4.1.1. Phương pháp phát hiện biên trực tiếp
Viện Khoa học Kỹ thuật Bưu điện 25
Kỹ thuật phát hiện biên trực tiếp:
Việc lựa chọn giá trị ngưỡng rất quan trọng trong quá trình xác định đường
biên:
 Khi giá trị T quá cao, các đường biên có độ tương phản thấp sẽ bị mất đi.
 Khi T quá thấp, dễ xảy ra hiện tượng xác định biên sai dưới tác động của
nhiễu.
4.1.2. Phương pháp phát hiện biên gián tiếp
Viện Khoa học Kỹ thuật Bưu điện 26
Quy trình dò biên gián tiếp:
 Xác định điểm biên xuất phát
 Dự báo và xác định điểm biên tiếp theo
 Lặp lại bước 2 cho đến khi gặp điểm xuất phát
Nhận xét: 
khó khăn trong việc khảo sát tính chất của đường biên và phải kiểm tra tất cả 8 
điểm-láng giềng của của mỗi điểm
Thuật toán dò biên tổng quát:
B1. Xác định cặp nền-vùng xuất phát: bằng cách duyệt ảnh từ trên xuống dưới, 
trái sang phải để lựa chọn điều kiển l
B2. Xác định cặp nền-vùng tiếp theo
B3. Lựa chọn điểm biên vùng
B4. Nếu gặp cặp xuất phát thì dừng, nếu không thì quay lại bước 2 
4.1.2. Phương pháp phát hiện biên gián tiếp
Viện Khoa học Kỹ thuật Bưu điện 27
Phương pháp khớp nối lỏng :
Khái niệm láng giềng 4 và láng giềng 8
Với điểm P được bao phủ xung quanh bởi 8 điểm: P0, P1, P8
Láng giềng 8 của P gồm các điểm: P0, P1, P2, P3, P4, P5, P6, P7
Láng giềng 4 của P gồm các điểm: P0, P2, P4, P6.
4.1.2. Phương pháp phát hiện biên gián tiếp
Viện Khoa học Kỹ thuật Bưu điện 28
Phương pháp khớp nối lỏng :
 Xét các điểm p và q là 2 điểm 4 láng giềng.
 I(p), I(q): Giá trị mức xám của điểm p và q
 Nếu thì coi như có cặp biên (p, q).
Ví dụ: Cho ma trận ảnh chọn θ =2 ta có
4.2. Phân vùng ảnh và phương pháp phân vùng ảnh
Viện Khoa học Kỹ thuật Bưu điện 29
Có thể hiểu phân vùng là tiến trình chia ảnh thành nhiều vùng, mỗi vùng chứa
một đối tượng hay nhóm đối tượng cùng tính chất như cùng mức xám, cùng màu
hay cùng độ nhám
Dựa vào đặc tính vật lý của ảnh, người ta có nhiều kiểu phân vùng như phân
vùng đựa vào vùng đồng nhất hay vùng liền kề, phân vùng ảnh dựa vào biên
độ
 Không có kỹ thuật phân đoạn nào là vạn năng, theo nghĩa có thể áp dụng
cho mọi loại ảnh.
 Không có kỹ thuật phân đoạn nào là hoàn hảo.
4.2. 1. Phân vùng ảnh dựa theo ngưỡng biên độ
Viện Khoa học Kỹ thuật Bưu điện 30
Kỹ thuật lấy ngưỡng
Kỹ thuật này dựa trên một ý tưởng hết sức đơn giản. Một tham số θ, gọi là
ngưỡng độ sáng, sẽ được chọn để áp dụng cho một ảnh a[m,n] theo cách sau:
4.2. 1. Phân vùng ảnh dựa theo ngưỡng biên độ
Viện Khoa học Kỹ thuật Bưu điện 31
4.2.1.1 Ngưỡng cố định:
Sử dụng lược đồ xám để xác định. Nếu lược đồ xám có dạng rắn lượn, có nhiều
đỉnh và khe thì sử dụng các khe làm ngưỡng phân vùng
4.2.1.2 Ngưỡng dựa trên lược đồ:
Tính toán để xác định ngưỡng
4.2. 1. Phân vùng ảnh dựa theo ngưỡng biên độ
Viện Khoa học Kỹ thuật Bưu điện 32
4.2.1.2 Ngưỡng dựa trên lược đồ
Thuật toán đẳng liệu
 Chia lược đồ thành 2 đoạn bằng một giá trị ngưỡng khởi động ,tức
là bằng phần nửa thang độ xám động của ảnh.
 Sau đó tính toán độ sáng trung bình của 2 vùng:
 m f,0 của những điểm ảnh thuộc đối tượng
 mb,0 của những điểm ảnh nền.
 Tính giá trị ngưỡng mới
 Quá trình này cứ thế sẽ được tiếp tục với các ngưỡng mới cho đến khi nào giá
trị ngưỡng không thay đổi nữa thì dừng lại.
1
0 2
 B
4.2.2 Phân vùng bằng tách cây tứ phân
Viện Khoa học Kỹ thuật Bưu điện 33
Thuật toán này tạo nên một cây mà mỗi nút cha có 4 nút con ở mọi mức trừ
mức ngoài cùng. Cây này cho ta hình ảnh rõ nét về cấu trúc phân cấp của các
vùng tương ứng với tiêu chuẩn.
 Một vùng thỏa chuẩn sẽ tạo nên một nút lá, nếu không nó sẽ tạo nên một nút
trong và có 4 nút con tương ứng với việc chia làm 4 vùng.
 Ta cứ tiếp tục như vậy cho đến khi phân xong. Các nút của cây biểu diễn số
vùng đã phân
Với ngưỡng θ cho trước, vùng thuần nhất phải thỏa điều kiện:
Độ lệch chuẩn σ < θ 
 Hoặc Max, Min lần lượt là giá trị lớn nhất và nhỏ nhất
của mức xám trong vùng cần chia.
 Giá trị điểm ảnh trong vùng bằng cách lấy trung bình giá trị của vùng đó.
4.2.2 Phân vùng bằng tách cây tứ phân
Viện Khoa học Kỹ thuật Bưu điện 34
Ví dụ: Cho ảnh S(m, n) , hãy phân vùng theo tiêu chí: ngưỡng θ= 2 và
4.2.2 Phân vùng bằng tách cây tứ phân
Viện Khoa học Kỹ thuật Bưu điện 35
Ví dụ: Cho ảnh S(m, n) , hãy phân vùng theo tiêu chí: ngưỡng θ= 2 và
4.2.3 Phân vùng nối hợp (tổng hợp)
Viện Khoa học Kỹ thuật Bưu điện 36
Ý tưởng của phương pháp này là xem xét ảnh từ các miền nhỏ nhất rồi hợp
chúng lại nếu thỏa tiêu chuẩn để được một miền đồng nhất lớn hơn.
 Ta lại tiếp tục với miền thu được cho tới khi không thể hợp được nữa. Số miền
còn lại cho ta kết quả phân đoạn.
4.2.3 Phân vùng tổng hợp
Viện Khoa học Kỹ thuật Bưu điện 37
Phương pháp hợp vùng được thực hiện như sau:
 Giả sử có 2 vùng ω và ω’
 Ta xác định cặp các điểm 4 láng giềng (p, q) sao cho p ω và q ω’ 
 Xác định
 Trong đó I(p), I(q) là giá trị mức xám của điểm p và q, θ1 là giá trị
ngưỡng cho trước. 
4.2.3 Phân vùng tổng hợp
Viện Khoa học Kỹ thuật Bưu điện 38
Phương pháp hợp vùng được thực hiện như sau:
 Gọi b(ω) và b(ω’) là số điểm biên của 2 vùng ω và ω’
 Xét hàm khả năng hợp 2 vùng:
Nếu thì có thể hợp 2 vùng ω và ω’ thành 1 vùng
4.2.3 Phân vùng tổng hợp
Viện Khoa học Kỹ thuật Bưu điện 39
Ví dụ
 Xét khả năng hợp các vùng của ảnh sau, θ1 =3, θ 2 =0.6
4.2.3 Phân vùng tổng hợp
Viện Khoa học Kỹ thuật Bưu điện 40
Ví dụ
 Gọi A, B, C, D, E lần lượt là các vùng chứa mức xám 1, 2, 4, 6, 8
 Ta có bảng 1, đếm số điểm biên các vùng và tính toán các giá trị
4.2.3 Phân vùng tổng hợp
Viện Khoa học Kỹ thuật Bưu điện 41
Ví dụ
 Xác định hợp vùng Bảng 2
Kết luận:
• Có thể hợp được 2 vùng D và E vì 11/10 >θ2
• Có thể hợp được 2 vùng B và C vì 4/6 >θ2