Bài giảng Xử lý ảnh - Chương 6: Nhận dạng ảnh - Trần Thúy Hà

THS. TRẦN THÚY HÀ
BỘ MÔN: KỸ THUẬT ĐIỆN TỬ - KHOA KTDT1
Trang 42
 Quá trình nhận dạng
Lựa chọn mô hình biểu diễn đối tượng
Lựa chọn luật ra quyết định (phương pháp nhận dạng) 
và suy diễn quá trình học
Học nhận dạng
 Khi mô hình biểu diễn đã được xác định
Mô hình tham số
Mô hình cấu trúc
 Đến quá trình học nhằm cải thiện, điều chỉnh việc phân lớp
 Nhận dạng là tìm ra quy luật và thuật toán để gán đối
tượng vào lớp của nó
Quá trình nhận dạ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 43
Học có giám sát dựa vào kiến thức biết trước.
Kỹ thuật này dựa vào một thư viện mẫu
chuẩn.
Mẫu cần nhận dạng sẽ được so sánh với mẫu
chuẩn để xác định thuộc loại nào.
Vấn đề chủ yếu là thiết kế hệ thống có thể so
sánh đối tượng với mẫu nên tương đối rõ
ràng về kết quả và dễ đánh giá hiệu quả.
Học có giám sát (Supervised learning)
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 44
Học không giám sát phải tự định ra các lớp
khác nhau và xác định đặc trưng của từng
lớp
Khó khăn để xác định tính chính xác của kiểu
học này vì không có thư viện mẫu để so sánh
Kỹ thuật nhằm hợp các nhóm theo một cách
tối ưu nhất.
Học không giám sát (Unsupervised learning)
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 45
Trong kỹ thuật này thì đối tượng được
biểu diễn bằng một vector nhiều chiều.
Mỗi chiều là một tham số thể hiện một
đặc điểm của đối tượng đó
Một số khái niệm
Phân hoạch không gian
Hàm phân lớp hoặc hàm ra quyết định
6.2. Nhận dạng dựa theo không gian
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 46
Giả sử không gian đối tượng X
Phân hoạch không gian
 miXX i ,...,2,1, 
XCC ii ,
XCjiCC i
m
i
ji 
 1
,, 
Thì P là phân hoạch không gian X thành các lớp
sao cho
Trong trường hợp thông thường thì không gian
chỉ có thể được phân tách từng phầ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 47
Để phân đối tượng ra các lớp ta cần xác định
số lớp và ranh giới giữa các lớp đó
Hàm phân lớp sẽ giúp phân biệt các lớp
Nếu có k lớp thì phải có k-1 hàm phân lớp
Hàm phân lớ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 48
 Gọi {gi} là lớp các hàm phân lớp. Lớp hàm này được
định nghĩa như sau:
 nếu ∀ i ≠ k, gk(X) > gi(X) thì ta quyết định X ∈ lớp k.
 Như vậy để phân biệt k lớp, ta cần k-1 hàm phân
biệt. Hàm phân lớp g thường là hàm tuyến tính
kk XWXWWXg ...)( 110
trong đó:
- Wi là các trọng số gán cho các thành phần Xi.
- W0 là trọng số để viết cho gọ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 49
Trong trường hợp g là tuyến tính, người ta nói
là việc phân lớp là tuyến tính hay siêu phẳng
(Hyperplane).
Các hàm phân biệt thường được xây dựng dựa
trên khái niệm khoảng cách hay dựa vào xác
suất có điều kiện.
 Nếu khoảng cách nhỏ hơn một ngưỡng τ nào
đấy thì coi 2 đối tượng là giống nhau và gộp
chúng vào một lớp. Ngược lại, nếu khoảng
cách lớn hơn ngưỡng, có nghĩa là chúng khác
nhau và tách thành 2 lớ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 50
Một số thuật toán tiêu biểu
Thuật toán dựa vào khoảng cách lớn 
nhất
Thuật toán k trung bình (K-mean)
Thuật toán ISODATA
Thuật toán k láng giềng (K-nearest 
neighbor)
Thuật toán nhận dạng không gian (thuật toán nhận dạng trong tự
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 51
Đây là thuật toán dựa vào K phần tử đầu tiên
trong không gian (xác định K lớp với K đã
cho trước)
Cách chọn K là tìm K lớp sao cho khoảng
trung bình giữa các phần tử và tâm của lớp
các phần tử này thuộc là nhỏ nhất
Dựa vào công thức:
Thuật toán K trung bình (K - means)
1
1
,
N
k j j k
j
Z X X C
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 52
Các bước thực hiện:
1. Chọn ngẫu nhiên K tâm (centroid) cho K 
cụm (cluster). Mỗi cụm được đại diện bằng 
các tâm của cụm.
2. Tính khoảng cách giữa các đối tượng đến K 
tâm (thường dùng khoảng cách Euclidean).
3. Nhóm các đối tượng vào nhóm gần nhất.
4. Xác định lại tâm mới cho các nhóm.
5. Thực hiện lại bước 2 cho đến khi không có sự 
thay đổi nhóm nào của các đố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 53
Ví dụ: phân lớp cho ảnh I sau theo thuật toán K-means:
 Giả sử ta muốn phân thành 2 nhóm
 k = 2
1 2 4 5
1 1 3 4
I
A B C D
1 2 4 5
1 1 3 4
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 54
Với một tập gồm m đối tượng
Khoảng cách giữa các đối tượng có thể được xác
định như là đại lượng để phân lớp
Khoảng cách lớn nhất ứng với phần tử xa nhất
tạo nên lớp mới
Sự phân lớp sẽ hình thành dần dần dựa vào việc
tính khoảng cách giữa các đối tượng và các lớp
Thuật toán khoảng cách lớn 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 55
Bước 1:
Chọn hạt nhân ban đầu: Xi ∈ C1 là lớp g1 với Z1 là 
phần tử trung tâm (phần tử có khoảng cách trung 
bình tới các phần tử khác tron g1)
Tính tất cả các khoảng cách Dj1 = D(Xj,Z1) với j = 
1..m
Tìm Dk1 lớn nhất. Xk là phần tử xa nhất của nhóm 
g1
Xk trở thành phần tử trung tâm Z2 của lớp mới g2.
Tính d1=D12=D(Z1,Z2)
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 56
Bước 2:
Tính các khoảng cách Dj1,Dj2 với j = 1..m
Đặt Dk là khoảng cách lớn nhất
Điều kiện kết thúc
Nếu Dk < θd1 kết thúc thuật toán (phân 
lớp xong)
Nếu không sẽ tạo nên lớp g3 có Xk là phần 
tử trung tâm Z3
Tính d3=(D12+D13+D23)/3
Thuật toán lặp đi lặp lại cho đến khi kết thú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 57
ISODATA là Iterative Self Organizing
Data Analysis
Thuật toán này tương đối mềm dẻo và
không cố định các lớp
Thuật toán ISODATA
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 58
Các bước:
 Lựa chọn phân hoạch dựa vào các tâm bất kỳ (kết
quả không phụ thuộc vào tâm ban đầu này)
 Phân vùng bằng cách đặt các điểm vào lớp có tâm
gần nhất dựa vào khoảng cách
 Tách đôi lớp ban đầu nếu khoảng cách lớn hơn
ngưỡng t1
 Xác định phân hoạch mới dựa vào các tâm vừa xác
định cho đến khi không có tâm mới
 Nhóm các vùng theo ngưỡng t2
 Lặp các bước trên cho đến khi thỏa mãn tiêu chuẩn
phân hoạch
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 59
Thuật toán này dựa vào vị trí của đối tượng
cần xét để xác định lớp đối tượng đó thuộc về
là lớp nào
Các mẫu sẽ được biểu diễn trên không gian 
đối tượng
Mỗi đối tượng cần xác định lớp sẽ tìm k 
mẫu gần nhất xung quanh
Đối tượng đầu vào này sẽ thuộc lớp có số 
lượng lớn nhất trong số k láng giềng
Thuật toán K láng giề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 60
Vì thuật toán chọn số đông để quyết
định việc phân lớp nên thông thường
lớp lớn nhất trong tập mẫu thường có
xu hướng thống trị
Để làm giảm việc này thì trọng số liên
quan đến khoảng cách có thể được thêm
vào, và mẫu càng xa sẽ có ảnh hưởng ít
hơn so với mẫu ở gầ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 61
Ngoài cách biểu diễn định lượng thì còn tồn
tại kiểu đối tượng định tính
Ví dụ mối quan hệ giữa các đối tượng hoặc
dạng của đối tượng
Giả sử đối tượng có thể được biểu diễn bởi
một chuỗi ký tự và mỗi ký tự sẽ thể hiện một
đặc tính
Hàm phân biệt sẽ là hàm logic nhận diện các
từ có cùng độ dài
Nhận dạng dựa theo cấu trú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 62
Có hai giai đoạn trong quy trình nhận
diện:
Xác định quy tắc xây dựng
Xác định các dạng dựa vào các quy 
tắc đó
Trong hai giai đoạn thì xác định quy tắc
xây dựng là rất khó khăn và là vấn đề
chính cần giải quyết trong quy trình
nhận diện dạng 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 63
Mạng nơron bao gồm nhiều phần tử xử
lý đơn giản hoạt động song song.
Tính năng của hệ thống phụ thuộc vào
cấu trúc liên kết giữa các nơron và
trọng số của các liên kết này
Trong mạng nơron có các nơron đầu
vào và các nơron đầu ra
Nhận diện dựa trên mạng Nơron
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 64
Mạng Hopfield là mạng nơ ron
1 lớp NN
Ánh xạ dữ liệu tín hiệu vào sang tín hiệu ra
theo kiểu tự kết hợp
Nếu tín hiệu vào là X thuộc miền D thì tín 
hiệu ra Y cũng thuộc miền D
Mạng Hopfield mô phỏng khả năng hồi
tưởng của não người (nhận ra người quen khi
nhận ra các nét quen trên khuôn mặt)
Mạng Hopfield
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 65
Mạng Hopfield có một lớp ra có kích thước
bằng kích thước tín hiệu vào, liên kết nơ ron
là đầy đủ.
 Mạng Hopfield yêu cầu tín hiệu vào có giá
trị lưỡng cực -1 và 1
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 66
 Wij là trọng số của liên kết giữa nơ
ron thứ i với nơ ron thứ j



j ijij
j ijij
i sw
sw
a


,1
,1
Hàm kích hoạt tại các nơ ron là:
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 67
 Mạng Hopfield học có giám sát
 Giả sử có p mẫu học tương ứng với các
vector tín hiệu vào Xs, s=1..p
 Mạng cần xác định bộ trọng số W sao cho
Xs=f(Xs,W) với mọi s=1..p
 Ta xây dựng ma trận trọng số W như sau:
 
ji
jixx
w
p
s
sisj
ij
,0
,
1
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 68
Giả sử đưa vào mạng vector tín hiệu X
Việc tính toán đầu ra Y cho tín hiệu X là quá trình
lặp lại:
Đặt X0=X
Tính Yt là tín hiệu đầu ra tương ứng với Xt lan 
truyền trong mạng một lần
Nếu Yt khác Xt thì tiếp tục với t=t+1 và Xt+1 = Yt
Nếu Yt=Xt thì dừng lại và kết quả của mạng là 
Yt
W không thay đổi trong quá trình tính 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 69
Một vài tình huống có thể nảy sinh
Mạng không dừng 
Mạng có thể đưa ra luân phiên một 
vài mẫu học hoặc ảnh ngược của 
chúng
Mạng dừng và Xt=X 
X đã được đoán đúng dựa trên mẫu 
học, X có thể là một trong các mẫu 
đã 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 70
Một vài tình huống có thể nảy sinh (tt)
Mạng dừng với Xt là Xs nào đó trong mẫu 
đã học 
Mạng đã phục hồi nguyên dạng của X 
chính là Xs
Mạng dừng với Xt không thuộc mẫu đã 
học 
Chỉ ra một vector mới có thể dùng để cập 
nhật trọng số
Mạng dừng với Xt là ảnh ngược của các 
trường hợp 2,3,4
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 71
Mạng Kohonen tập trung vào mối liên
hệ có tính cấu trúc trong các vùng lân
cận hoặc trong toàn thể không gian mẫu
Trong mạng Kohonen các vector tín
hiệu vào gần nhau sẽ được ánh xạ sang
các nơ ron trong mạng lân cận nhau
Mạng Kohonen hay bản đồ Kohonen hoặc bản đồ tự tổ chứ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 72
Mạng Kohonen rất gần với mạng sinh học về
cấu tạo lẫn cơ chế học
Mạng Kohonen có một lớp kích hoạt là các
nơ ron được phân bố trong mặt phẳng hai
nhiều kiểu lưới vuông hoặc lục giác
Phân bố này làm cho mỗi nơ ron có cùng số
nơ ron trong từng lớp láng giềng và các đầu
vào tương tự nhau sẽ kích hoạt các nơ ron
gần nhau (không gian 2 chiều sẽ phải được
cuộn để thành một không gian liên tiế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 73
Tất cả các nơ ron ở lớp kích hoạt được
nối đầy đủ với lớp vào mỗi kết nối này
sẽ có một trọng số
Các nơ ron trên lớp kích hoạt chỉ nối
với các lớp lân cận nên khi có tín hiệu
đầu vào sẽ chỉ tạo ra kích hoạt địa
phương
Vùng được kích hoạt sẽ chỉ ra vị trí của
tín hiệu đầu vào trong không gian đố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 74
Việc học của mạng kohonen dựa trên kỹ
thuật cạnh tranh không cần mẫu học.
Trọng số của các nơ ron được khởi tạo bằng
một số bất kỳ nhỏ
Mạng được học qua một lượng lớn mẫu gần
nhau và thường nhiều lần theo các vòng lặp
Tại một thời điểm chỉ có một nơ ron duy nhất
C trong lớp kích hoạt được lựa chọn với
nguyên tắc là nơ ron C có vector trọng số gần
với tín hiệu vào 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 75
Sau khi có nơron C, các trọng số wci
được hiệu chỉnh nhằm cho gần với trọng
số mong muốn (đầu vào)
Nếu tín hiệu vào xsi và trọng số wci tạo
kết quả ra quá lớn thì phải giảm trọng
số và ngược lạ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 76
Với
s là thứ tự bước
D(t) là vector đầu vào t
u là số thứ tự của nơ ron C được chọn
θ(u,v,s) là hàm tỷ lệ khoảng cách giữa nơ ron v 
và u (có thể là hàm ngưỡng hoặc hàm Gaussian)
))()()((),,()()1( swtDssvuswsw vvv 
Tỉ lệ giảm hoặc tăng trọng số sẽ nhỏ dần theo
thời gian và khoảng cách sai số giữa vector đầu
vào và vector trọng số với công thứ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 77
Vì mạng Kohonen được huấn luyện dựa vào
sự kích hoạt địa phương và các nơ ron lân
cận nên các đối tượng gần nhau sẽ kích hoạt
các nơ ron gần nhau
Khi chuyển một tín hiệu đầu vào vào mạng
thì một vùng nơ ron sẽ được kích hoạt cho
chúng ta thấy tín hiệu đầu vào này thuộc
vùng dữ liệu nào