Bài giảng Xử lý ảnh - Chương 5: Các phương pháp phân vùng ảnh - Trần Thúy Hà

BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 3
CHƯƠNG 5:
CÁC PHƯƠNG PHÁP PHÂN 
VÙNG ẢNH
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 4
 Thông thường để xử lý ảnh thì chúng ta
phải tách được các đối tượng trong ảnh
ra làm các vùng riêng biệt.
Tách chữ, số, ảnh trong văn bản
Tách các vùng cháy rừng để xác định 
độ thiệt hại trong ảnh vệ tinh về cháy 
rừng
Tách các loại vi khuẩn, vi rút trong 
ứng dụng y học
5.1. Phân vùng ảnh
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 5
Hình dáng đối tượng phụ thuộc vào
biên vật thể hoặc một vùng động
nhất thể hiện vị trí của đối tượng
Để phát hiện vùng thì có thể phát
hiện biên giữa các vùng hoặc phát
hiện trực tiếp vùng
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 6
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 7
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 kiểu.
Phân vùng có ba loại khác nhau:
Kỹ thuật cục bộ dựa vào thông tin cục bộ của điểm 
ảnh.
Kỹ thuật toàn thể dựa vào thông tin của toàn ảnh (sơ 
đồ tần suất)
Kỹ thuật tách, hợp, giãn sử dụng khái niệm đồng 
nhất và gần về hình học
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 8
 Trước khi phân vùng thông thường thì
biểu đồ tần xuất ảnh sẽ được làm trơn
5.2. Làm trơn ảnh
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 9
Phân vùng theo ngưỡng là tách 2 vật thể
bằng một ngưỡng chọn tự động
Việc chọn ngưỡng này sẽ thực hiện trên
biểu đồ tần suất.
Và ngưỡng này sẽ phân biệt vùng và
nền.
5.2.1. Phân vùng ảnh theo ngưỡng
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 10
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 11
Giả sử chúng ta có ảnh bao gồm đối tượng và
nền.
Chúng ta giả định là đối tượng và nền là hai
phân phối thống kê riêng biệt
Phân phối nền bao giờ cũng lớn hơn rất nhiều
so với phân bố đối tượng.
Biểu đồ tần suất của ảnh sẽ là tổ hợp của hai
phân phối này.
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 12
 Thuật toán lặp do Ridler và Calvard đưa
ra.
 Đồ thị tần xuất được chia ra làm 2 đoạn
bằng một giá trị ngưỡng θ(0), giá trị này là
giá trị nằm giữa của thang tần suất của
ảnh.
5.2.2. Thuật toán đẳng điệu
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 13
Giá trị trung bình mẫu m(f,0) của đối tượng
và m(b,0) của nền được tính toán theo công
thức:


max
min
max
min
)(
)(
G
Gg
G
Gg
gh
ghg
m(f,k) được tính với Gmin = 0 và Gmax = θ(k)
m(b,k) được tính với Gmin = θ(k)+1và Gmax = 255
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 14
Ngưỡng θ(k) được tính như sau:
( , ) ( , )
( 1)
2
m f k m b k
k
Thuật toán được lặp đi lặp lại cho đến khi
θ(k) = θ(k+1) thì ngưỡng được chọn là
ngưỡng không đổi này
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 15
Ví dụ: Tìm ngưỡng từ thuật toán đẳng điệu
I = [12 34 45 45 46 78 201 78 60];
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 16
Chúng ta giả định là phân phối nền rất lớn
so với phân phối đối tượng và hai phân phối
này là đối xứng.
Và nền là sáng và đối tượng là tối
5.2.3. Thuật toán đối xứng nền
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 17
Đỉnh cực đại maxp tìm được nhờ tiến hành
tìm giá trị cực đại trong lược đồ.
Vì vậy đỉnh maxp có thể coi là đỉnh của phân
phối của nền
Vì vậy bằng việc tính giá trị a sao cho a chỉ
định mốc (1-p%) của nền tính từ maxp
Ta có thể lấy đối xứng sang qua maxp để có
được ranh giới p% của đối tượng nền và là
ranh giới xác định sự phân chia
T = maxp - (a - maxp)
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 18
Giả sử chúng ta chọn p% là 95% thì chúng
ta sẽ tính sao cho diện tích từ a đến max là
bằng 5% của diện tích từ maxp đến max.
Sau đó lấy đối xứng qua maxp vì vậy diện
tích từ T đến max sẽ là 95% tổng diện tích
của phân phối nền, vì vậy T sẽ là ngưỡng
phân tách nền và đối tượng
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 19
Thuật toán tam giác do Zack đề xuất
Thuật toán này cũng sử dụng ý tưởng như
thuật toán trên, đó là tìm ranh giới giữa
phân phối của nền và đối tượng.
5.2.4. Thuật toán tam giác
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 20
Trong thuật toán này thì cách xác định là kẻ
một đường Δ từ đỉnh có số điểm ảnh bằng
max tới điểm có số điểm ảnh là min
Rồi tìm vị trí b sao cho d từ Δ đến Hb là max
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 21
Nếu trong trường hợp mà phân phối đối
tượng và nền là tương đương nhau về độ lớn
Thì ngưỡng chúng ta sẽ chọn ở vị trí cực tiểu
địa phương giữa hai phân phối này
Để giảm nhiễu nên làm trơn bằng hàm làm
trơn.
Ngưỡng với Bimodal Histogram
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 22
Phân vùng ảnh dựa trên thuộc tính quan
trọng nào đó của miền
Mỗi thuộc tính khi sử dụng thì có một tiêu
chuẩn phân đoạn tương ứng.
Thuộc tính:
mức xám,
màu sắc,
kết cấu
5.3. Phân vùng theo miền đồng nhất
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 23
Mức độ hiệu quả thường phụ thuộc vào việc
đánh giá độ thuần nhất.
Thông thường là trung bình và độ lệch 
chuẩn.
Có ba cách tiếp cận chủ yếu:
Phương pháp phân tách-cây tứ phân (split-
quad trees)
Phương pháp hợp (merge)
Phương pháp tách-hợp (split-merge)
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 24
Về nguyên tắc, phương pháp này kiểm
tra tính hợp thức của tiêu chuẩn tổng
thể trên miền lớn. Nếu đã đạt chuẩn thì
việc phân đoạn kết thúc.
Nếu không, vùng được chia nhỏ làm 4
vùng và sử dụng đệ quy để thực hiện
trên từng vùng nhỏ.
Tách cây tứ phân (quad tree)
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 25
 Với ngưỡng  cho trước vùng thuần nhất
phải thỏa mãn điều kiện |max-min|< θ
 với max và min là giá trị độ xám lớn nhất và nhỏ 
nhất trong miền cần chia.
 Hoặc tiêu chuẩn có thể là độ lệch bình
phương trung bình nhỏ hơn θ ( với x là giá
trị trung bình)
 
2
1
)(
1
xx
n
n
i
i
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 26
Trong giải thuật |max-min|< θ , khi miền là đồng
nhất cần tính lại giá trị trung bình và cập nhật lại
ảnh đầu ra. Giá trị trung bình được tính bởi:
 Tổng giá trị mức xám/ tổng số điểm.
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. Vì thế
cây này có tên là cây tứ phân.
Một vùng thoả mãn tiêu chuẩn tạo nên một nút lá,
nếu không sẽ tạo nên một nút trong và 4 nút con
tương ứng của việc chia làm 4 vùng. Mỗi nút lá của
cây biểu diễn một vùng đã phân chia theo tiêu
chuẩn.
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 27
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 28
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 29
Tách cây tứ phân (tổng thể)
Tiêu chuẩn phân vùng ở đây là màu sắc. Nếu mọi điểm
của vùng là màu trắng sẽ tạo nên một nút lá trắng và
tương tự như vậy với nút lá đen. Nút màu ghi có nghĩa
là vùng không thuần nhất và phải tiếp tục chia.
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 30
 Ví dụ: Cho ảnh I(m, n) , hãy phân vùng theo tiêu chí:
ngưỡng θ= 2
2 2 4 4 6 6 8 8
2 2 4 4 6 6 8 8
2 3 5 5 6 7 8 9
8 7 5 5 3 3 2 1
( , )
7 7 5 5 3 3 2 2
7 7 5 5 3 3 2 2
2 2 4 4 6 6 8 9
2 2 4 4 6 6 8 9
I m n
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 31
Ý tưởng là xem xét ảnh từ các miền nhỏ nhất
rồi tổ hợp chúng lại nếu thỏa mãn tiêu chuẩn
của một miền lớn hơn
Tiếp tục thực hiện hợp cho đến khi không
hợp được nữa.
Tiêu chuẩn để hợp hai miền là:
Chúng phải cùng đạt tiêu chuẩn
Chúng phải ở cạnh nhau (liên thông)
Phương pháp hợp
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 32
Phương pháp tách quá chi tiết, và tăng độ phức
tạp rất nhanh
Phương pháp hợp đơn giản hơn nhưng không
cho thấy cấu trúc liên quan giữa các vùng
Ta có thể kết hợp 2 phương pháp trên
Trước tiên tách để tạo cây tứ phân, phân 
đoạn theo hướng từ gốc tới lá
Tiến hành duyệt cây theo hướng ngược lại và 
hợp các vùng có cùng tiêu chuẩn
Phương pháp tách hợp (split-merge)
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 33
 Giải thuật gồm một số bước sau:
 i. Kiểm tra tiêu chuẩn đồng nhất
 i1. Nếu không thoả mãn và số điểm trong vùng lớn hơn một 
điểm, tách làm 4 vùng (trên, dưới, trái, phải) bằng cách gọi 
đệ quy. Nếu kết quả tách xong và không tách được nữa 
chuyển sang bước ii.
 i2. Nếu tiêu chuẩn đồng nhất là thoả mãn thì tiến hành hợp 
vùng và cập nhật giá trị trung bình cho vùng.
 ii. Hợp vùng
 Cần kiểm tra 4 lân cận đã nêu trên. Có thể có nhiều vùng 
thoả mãn khi đó ta chọn vùng tối ưu rồi tiến hành hợp.
 Phương pháp này thu được kết quả số vùng là nhỏ hơn 
phương pháp tách và ảnh được làm trơn hơn.
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 34
 Phân vùng dựa theo đường biên có các bước
sau:
Thực hiện phát hiện và làm nổi biên
Làm mảnh biên
Nhị phân hóa đường biên
Miêu tả đường biên
5.4. Phân vùng dựa theo đường biên
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 35
Về định nghĩa ta có biên là sự thay đổi
đột ngột của mức xám.
Có thể sử dụng các phương pháp phát
hiện biên trực tiếp đã học
Phát hiện biên
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 36
Làm cho biên mảnh chỉ với độ rộng 1 điểm
ảnh.
Trong Laplace thì thường ta sẽ có biên độ
rộng một điểm khi tìm điểm bằng 0 hoặc gần 0
Tuy nhiên trong Grandient thì chúng ta phải
lọc cực đại hoặc cực tiểu địa phương để tạo ra
biên mảnh 1 điểm ảnh
Làm mảnh biên
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 37
Nhị phân hóa đường biên nhằm làm
giảm nhiễu
Loại bỏ đường biên không cần thiết
Tránh trường hợp quá nhiều biên song
song.
Thường sử dụng ngưỡng
Nhị phân hóa đường biên
BÀI GIẢNG MÔN: XỬ LÝ ẢNH
www.ptit.edu.vn GIẢNG VIÊN: THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 38
Để biên có thể được sử dụng thuật tiện thì
phải được mã hóa cho đơn giản
Có thể sử dụng các đơn vị mã hóa để mã hóa
gần đúng như:
điểm
đoạn thẳng
cung tròn
Miêu tả đường biên