Nhận dạng sự kiện dựa trên từ điển thị giác

Chương 3 Nhận dạng sự kiện trên ảnh 3.1 Thế nào là sự kiện trên ảnh? Con người ta nhận biết một hành động như thế nào? Nói chung mọi người có xu hướng nghĩ rằng hành động cần phải được định nghĩa bằng một chuỗi các chuyển động của các chi trên cơ thể, diễn ra trong một khoảng thời gian đủ dài. Tuy nhiên câu trả lời thực sự lại nằm ở cơ chế hoạt động của bộ não con người. Thật sự thì hành động có thể được nhận ra và phân loại rất nhanh vì bộ não có khả năng suy đoán và lấp đầy những vùng thông tin còn trống hoặc thiếu. Do đó, không chỉ dữ liệu video mà cả ảnh cũng có thể mô tả hành động, hay nói cách khác là có thể nhận ra hành động của đối tượng trong ảnh (Hình 3.1). Một khi đã được làm quen với mẫu chuyển động của một sự kiện thì một cách ngầm định, bộ não có thể suy ra được những chuyển động trước và sau cái khoảnh khắc chuyển động được ghi nhận. Đây cũng chính là niềm tin của chúng tôi khi khám phá một cách hiểu mới về nhận dạng hành động dựa trên ảnh tĩnh. Một trong những loại ảnh khắc họa rõ nét hành động của con người và có ngữ cảnh có mức độ ngữ nghĩa tương quan cao với hành động, chính là ảnh hoạt động thể thao. Cụ thể hơn, chúng tôi tiến hành nhiều thí nghiệm với các thiết đặt khác nhau để ghi nhận hiệu quả nhận dạng của một phương pháp truyền thống trên ảnh thể thao. Lĩnh vực nhận dạng đối tượng 2D và tìm kiếm đa phương tiện đã ghi nhận những thành công lớn của phương pháp dựa trên từ điển thị giác. Hạn chế mà hướng tiếp cận này mắc phải là sự mất mát thông tin về không gian và hình dạng 15 Hình 3.1: Không cần theo dõi một chuỗi hành động liên tục nhưng con người có thể suy luận được nội dung mà những bức ảnh trên mô tả. Lý do là vì những hành động này trước đó đã được con người quan sát, và lưu lại những thông tin về tư thế chuyển động cũng như cách bố trí của sự vật. Tuy nhiên nếu giả sử ảnh bị chia thành nhiều mảnh nhỏ và không có thứ tự cũng như bố cục về không gian thì liệu con người còn có thể duy trì năng lực nhận diện như lúc ban đầu? khi được gom nhóm thành các “từ thị giác”1. Có một số ý tưởng cho phép bù đắp lượng thông tin mất mát này, hoặc tại bước huấn luyện bộ phân lớp [65], hoặc tìm kiếm phân phối của đặc trưng [22]. Về tổng thể, ta không thể biết được một động tác bổ túc thông tin như vậy có thực sự làm đúng như giả thuyết đặt ra bằng cách phân tích những kết quả trực tiếp, mà chỉ có thể xác nhận một kỹ thuật bổ túc là thành công nếu hiệu suất nhận dạng tổng thể của toàn hệ thống tăng lên. Thực sự thì nhóm các phương pháp theo mô hình từ điển thị giác rất khác nhau về kỹ thuật rút trích đặc trưng, và giai đoạn huấn luyện. Chỉ duy nhất bước trung gian giống nhau, đó là biểu diễn tất cả các mẫu học hay mẫu kiểm nghiệm bằng một “ngôn ngữ chung”, tức là bằng các từ thị giác. Với một mô hình nguyên thủy, các từ thị giác chỉ có khả năng duy nhất là tông quát hóa diện mạo2 của một vùng cục bộ trên ảnh, mà bỏ qua mọi thông tin về vị trí cũng như vị trí tương đối giữa các từ thị giác. Một số công trình sau này [30, 31] lấy thêm các thông tin vị trí tại mỗi đặc trưng, ví dụ khoảng cách chuẩn hóa từ điểm lấy đặc trưng đến trọng tâm 1visual word, visual terminology 2appearance 16 Hình 3.2: Sự kiện đua ngựa nhưng được quan sát từ nhiều hướng khác nhau, với cự ly khác nhau, với nhiều tư thế khác nhau, trong nhiều khung cảnh khác nhau, với một hoặc nhiều đối tượng. Rõ ràng đây là một thách thức đối với các mô hình phức tạp vì thực khó có thể lường hết và bao hàm tất những biến đổi này trong một. Hơn thế, việc huấn luyện cho một mô hình xác suất phức tạp như [10] đòi hỏi công sức lớn để chú thích và gán nhãn cho dữ liệu huấn luyện. hình học của đối tượng, hay góc nghiêng tương đối của điểm đặc trưng so với trục tọa độ ảnh hoặc đối tượng. Một số khác nâng cao độ phức tạp của phương pháp học, ví dụ dùng phân lớp SVM, hoặc mô hình xác suất có các biến ẩn như pLSA3 hay LDA4. Không dừng lại ở đó, một số công trình chú trọng cải thiện kỹ thuật xây dựng codebook, như thay thế nhiều thuật toán gom cụm khác nhau, công thức tính lân cận, các kiểu gán trọng cho lân cận, tối ưu kích thước codebook. Nếu có thêm thông tin vị trí tương đối của các từ thị giác, và dữ liệu huấn luyện được gán nhãn vị trí cho từng đối tượng, thì mô hình không những có khả năng nhận dạng mà còn xác định được vị trí trong ảnh. Tuy nhiên, việc áp dụng mô hình nào bị phụ thuộc mạnh vào đặc điểm của dữ liệu. Các mô hình phức tạp [25, 32, 47] thường đạt state of the art trong những bộ dữ liệu trong môi trường thí nghiệm, nhưng ít khi được ưa chuộng trong các hệ thống thực tế [50,61], một phần vì yêu cầu tính toán lớn, phần còn lại là những giả định trên dữ liệu nhỏ không còn đúng nữa trên dữ liệu thực tế (Hình 3.2). Trở ngại lớn nhất của các mô hình phức tạp học có giám sát là yêu cầu lượng dữ liệu huấn luyện được chú thích, trong khi khối lượng dữ liệu ngày càng tăng. Mặc dù tồn tại các khung hoạt động như Active Learning [45] để giảm đi sức lực gán nhãn, hiện tại chúng chưa đủ hoàn thiện để có thể được áp dụng trong bài toán thực tế. Đóng góp gồm hai điểm của chúng tôi trong chương này là: (i) tấn công bài toán nhận dạng sự kiện bằng cách chú trọng vào ngữ cảnh của sự kiện, và (ii) tìm hiểu 3probabilistic Latent Semantic Analysis 4Latent Dirichlet Analysis 17 và phát hiện những vấn đề còn tồn tại trong bước xây dựng từ điển thị giác. 3.2 Phương pháp Chúng tôi đề xuất mô hình gồm ba bước: (i) dò tìm các điểm đặc trưng, (ii) tính đặc trưng cục bộ, (iii) lượng hóa các đặc trưng. Trong giai đoạn huấn luyện, cả ba bước trên được thực hiện tuần tự. Sau khi đã xây dựng được từ điển thị giác ở bước (iii), thì trong giai đoạn thử nghiệm chỉ có hai bước (i) và (ii) được thưc hiện, sau đó tham chiếu đến từ điển đã tạo sẵn. 3.2.1 Phát hiện đặc trưng Ở bước này, các thông tin thị giác được lựa chọn. Những điểm có tính bất biến đặc trưng được lựa chọn, ví dụ bất biến tỉ lệ, bất biến quay. Thông thường toán tử DoG phát hiện đốm”, hay toán tử Harris-Laplace phát hiện “góc” được sử dụng vào mục đích này. Các kết quả thực nghiệm cho thấy [21,59] một tập thưa các điểm đặc trưng đạt được độ chính xác cao trên các loại đối tượng nhân tạo như xe, nhà cửa, các loại đồ chơi, các đối tượng có texture đơn giản. Ngược lại, lấy mẫu kiểu lưới dày hay kiểu lưới kim tự tháp lại phù hợp hơn với bài toán nhận dạng cảnh [15,22,29]. Đầy đủ hơn, Nowak [34] tiến hành một khảo sát độ hiệu quả của nhiều phương pháp lấy mẫu khác nhau. Chúng tôi sử dụng cả hai chiến thuật lấy mẫu (dựa vào các điểm đặc trưng, và lấy mẫu theo lưới) để đánh giá hiệu quả trên ảnh sự kiện thể thao. Sau khi dò tìm được các điểm quan trọng, vùng lân cận chung quanh điểm đó được mã hóa thành vector đặc trưng SIFT [28] (Hình 3.4). Nhược điểm nghiễm nhiên của các phương pháp dùng từ điển thị giác là việc bỏ qua thông tin về cấu trúc không gian của các từ thị giác, hoặc cả trình tự thời gian (nếu có). Bằng cách dùng mô hình đồ thị xác suất phụ thuộc biểu diễn mối quan hệ giữa từ thị giác với tài liệu chứa nó, và thêm các biến ngẫu nhiên ẩn, [32] bổ sung được hạn chế đó. Một cách đơn giản hơn, là tận dụng sự tương quan cục bộ giữa các điểm đặc trưng. Ảnh đầu vào được chia theo dưới với các ô có kích thước bằng nhau, hơn thế nữa là vài lưới với tỉ lệ lớn nhỏ khác nhau. Tại tâm của mỗi ô lưới, một lân cận tròn được lấy để tính đặc trưng. Các lân cận tròn được lấy sao cho tồn 18 Hình 3.3: So sánh thuận lợi và hạn chế giữa hai phương pháp lấy mẫu (i) dùng toán tử lấy góc Harris-Laplace phối hợp trên không gian tỷ lệ, (ii) lấy mẫu đồng đều trên các lưới tỷ lệ. Có thể nhận thấy phạm vi bao quát của phương pháp (i) lên đặc trưng ảnh là không lớn, trong khi đó phương pháp (ii) bị bắt buộc phải bao quát toàn bộ vùng ảnh. Về mặt cảm nhận, phương pháp (ii) không bỏ sót thông tin. tại khoảng chồng lấp giữa hai ô kề nhau, và đối với các ô có cùng vị trí ở hai tỷ lệ lưới khác nhau. Mặc dù khó có thể “thấy” điều này liệu có ảnh hưởng tốt đến hiệu quả nhận dạng hay không, nhưng kết quả thực nghiệm đã khẳng định [15,29,49]. Thuận lợi của phương pháp lấy mẫu đồng đều là tất cả các vị trí trên ảnh đều được mã hóa thành các vector đặc trưng, do đó không một thông tin nào bị bỏ sót. Ngược lại, với các kỹ thuật sử dụng toán tử dò tìm các điểm bền vững thì tùy thuộc vào loại ảnh và đối tượng trong ảnh mà nó có hiệu quả hay không: ảnh một ngôi nhà hoặc rặng cây sẽ thu hút được nhiều điểm bền vững (vì có nhiều góc và đốm), tuy nhiên ảnh con người với bản chất không nhiều góc cạnh quá, sẽ không thu hút được “sự chú ý” của các toán tử nói trên (Hình 3.3). Nhưng đổi lại các điểm đặc 19 Hình 3.4: Lân cận chung quanh điểm đặc trưng được mã hóa thành vector đặc trưng: chia thành các lưới vuông, mỗi ô lưới tương ứng với một histogram với số bin là lượng hóa giá trị góc gradient, giá trị trong mỗi bin là tích lũy độ lớn các vector hướng gradient, sau đó các histogram được nối lại thành một vector dài. Cấu hình thông dụng là lưới 4x4 với 8 bin histogram, tổng cộng vector có 128 chiều. trưng không còn bất biến tỷ lệ hoặc bất biến quay nữa: đơn giản là vì các điểm được lấy đặc trưng không phải luôn luôn là các điểm góc, các điểm đầu mút, hoặc là các đốm. Một hạn chế khác là số lượng đặc trưng không chứa thông tin cũng tăng lên đáng kể, ví dụ như một vùng texture đồng đều nhưng mọi điểm trong vùng đó đều được mã hóa thành vector đặc trưng, làm cho số lượng thông tin vô ích trở nên lấn át, trong một số trường hợp xấu là gây nhầm lẫn và làm chệch hướng các thuật toán gom cụm. 3.2.2 Xây dựng từ điển thị giác Sau khi rút trích và biểu diễn thành các vector đặc trưng, chúng là đầu vào cho thuật toán gom cụm. Chúng tôi sử dụng thuật toán K-Means vì tính đơn giản và tốc độ. Khoảng cách Euclid được dùng để tính khoảng cách giữa hai điểm trong không gian đặc trưng. Bởi vì có sự tương tự giữa ảnh phong cảnh và ảnh sự kiện thể thao, nên tồn tại nhiều vùng có texture đồng nhất, hoặc vùng phằng, do đó một số lượng lớn đặc trưng gần như tương tự nhau, đặc biệt khi áp dụng chiến thuật lấy mẫu trên lưới. Do vậy trước tiên chúng tôi gom cụm tất cả các vector đặc trưng thô còn 1/2 hay 1/4 số lượng ban đầu. Đây được gọi là các từ thị giác trung cấp. Sau đó các từ trung cấp này được gom cụm một lần nữa để cho ra các từ thị giác tổng 20 quát nhất. Để tăng cường năng lực phân loại của từ điền thị giác trên các sự kiện có diện mạo tương tự nhau, ví dụ sailing - rowing, sailing - snowboarding. Hai giải pháp được thử nghiệm: (i) đứng trên giai đoạn rút trích đặc trưng, chúng tôi xây dựng từ điển thị giác từ các vector đặc trưng lấy ở nhiều mức lưới thưa, dày khác nhau (tạm gọi là từ điển thô + mịn), (ii) đứng trên giai đoạn xây dựng từ điển, chúng tôi tái cấu trúc lại một từ điển vừa chứa các từ thị giác chung ở tất cả các phân lớp, vừa chứa các từ thị giác đặc thù của mỗi phân lớp (tạm gọi là từ điển chung + riêng). Từ điển thô + mịn Giải pháp đầu tiên (Hình 3.5) gom cụm các vector đặc trưng được rút trích ở nhiều mức tỷ lệ từ thô đến mịn. Chúng tôi hy vọng các từ thị giác thô sẽ nắm bắt được các cấu trúc macro của ảnh, còn các từ thị giác mịn sẽ nắm bắt được cấu trúc micro của ảnh, với hy vọng có thể bù vào sự mất mát tính bất biến tỷ lệ. Chi tiết được trình bày ở Thuật toán 1. Cũng có thể dùng một cách khác (Hình 3.6) là tạo ba bộ từ điển, thô, trung bình, và mịn. Các khả năng được ước lượng một cách độc lập trên mỗi từ điển và sau đó được kết hợp thành xác suất hậu nghiệm. Chi tiết được trình bày ở Thuật toán 2. Algorithm 1 Xây dựng từ điển thị giác với nhiều mức tỷ lệ input {Ii}N1 tập ảnh huấn luyện input K kích thước từ điển input {si}Si=1 các mức lưới tỷ lệ output V từ điển thị giác Vi ←  X ←  for Ij ∈ {Ij}Nj=1 do X ← X ∪ sift(Ij, si) end for Vi ← kmeans(X,K) Từ điển chung + riêng Giải pháp thứ hai được lấy cảm hứng một phần từ [?] (Hình 3.8), với đại ý là duy trì đồng thời đặc điểm riêng của mỗi phân lớp và đặc điểm chung của tất cả các 21 Hình 3.5: Giải pháp từ điển thô + mịn: ảnh được rút trích vector đặc trưng với nhiều mức tỷ lệ khác nhau, sau đó gom cụm thành các từ trung gian, được gom cụm lần cuối thành từ điển. Chi tiết xem Thuật toán 1. Algorithm 2 Xây dựng bộ từ điển thị giác với mức tỷ lệ khác nhau input {Ii}Ni=1 tập ảnh huấn luyện input K kích thước từ điển input {si}Si=1 các mức lưới tỷ lệ output {Vi}Si=1 bộ từ điển thị giác for si ∈ {si}Si=1 do Vi ←  X ←  for Ij ∈ {Ij}Nj=1 do X ← X ∪ sift(Ij, si) end for Vi ← kmeans(X,K) end for 22 Hình 3.6: Giải pháp từ điển thô + mịn: ảnh được rút trích vector đặc trưng với nhiều mức tỷ lệ khác nhau, được gom cụm độc lập theo tỷ lệ để tạo thành ba từ điển thô, trung bình, và mịn. Chi tiết xem Thuật toán 2. phân lớp trong một từ điển. Mặt khác, như các vấn đề đã trình bày ở Chương 2, khi gán nhãn một vector đặc trưng cho một từ thị giác chúng ta gặp phải vấn đề nhập nhằng với những đặc trưng nằm gần biên giữa hai vùng của hai từ thị giác khác nhau (Hình 3.7): không chính xác nếu gán hẳn cho một từ nào. Tồn tại một số giải pháp gán “mềm”: gán đồng thời cho tất cả các từ thị giác lân cận với tỷ trọng tỷ lệ nghịch với khoảng cách. Chúng tôi giải quyết cả hai vấn đề trong một giải pháp duy nhất, được trình bày trong Thuật toán 3 và Hình 3.7. 3.2.3 Phân lớp Naive Bayes Trong chương này chúng tôi sử dụng mô hình từ điển thị giác cùng với bộ phân lớp Naive Bayes. Đây là một trong những mô hình tổng hợp cơ bản nhất. Giả sử ta có một N tập ảnh đã được gán nhãn I = {Ii}Ni=1, một tập các phân lớp Cj, j = 1..M , và một tập các từ thị giác V = {vk}Kk=1. Mô hình tổng hợp có nghĩa là phân phối đặc trưng của ảnh bất kỳ có thể được “tổng hợp” hoặc “sinh ra” từ các từ thị giác có trong từ điển, do đó likelihood của một từ vk thuộc về lớp Cj phải được tính trên tất cả các tổ hợp (vk|Cj) có thể. Giả sử rằng dữ liệu huấn luyện được lấy mẫu đồng đều trong không gian ảnh, likelihood được tính bằng cách đếm số lần xuất hiện của các từ thị giác trong dữ liệu như sau: 23 Hình 3.7: Trước tiên tất cả các đặc trưng SIFT ở mỗi phân lớp được gom cụm thành các từ thị giác trung cấp (những chấm nhỏ). Tập hợp tất cả các từ thị giác trung cấp được gom cụm lần nữa để tạo thành các từ thị giác chung (những chấm lớn). Để bổ sung các từ thị giác riêng của mỗi phân lớp sự kiện, các từ thị giác trung cấp được xác định vùng không gian đặc trưng mà nó thuộc về, thực chất là xác định từ thị giác chung nào gần nhất với từ trung cấp đang xét. Cuối cùng, các từ thị giác trung cấp được lựa chọn theo tiêu chí nằm càng xa với trung tâm càng tốt, và chỉ được chọn K từ. Tổng hợp từ chung + từ riêng ở mỗi phân lớp chính là kết quả cuối cùng. Hình 3.8: Giải pháp từ điển chung + riêng: sau khi được gom cụm thành các từ thị giác trung gian, chúng được gom cụm thêm lần nữa và lựa chọn một số lượng cố định những cụm gần nhau nhất. Tiếp theo một số lượng cố định các từ thị giác trung gian (gọi là các từ riêng) của mỗi loại sự kiện được lựa chọn để thêm vào từ điển hiện có. Tiêu chí lựa chọn là lấy những từ có khoảng cách xa nhất so với các từ thị giác chung. Chi tiết xem Thuật toán 3. 24 Algorithm 3 Xây dựng từ điển chung + riêng input {Ii}Ni=1 tập huấn huyện input {Cj}Mj=1 các phân lớp input {Kj}Mj=0 kích thước từ điển output V từ điển thị giác {Vj ← }Mj=0 {Xj ← }Mj=1 for Ii ∈ {I}Ni=1 do for each Cj, j = 1..M do if Ii ∈ Cj then Xj ← Xj ∪ sift(Ii) end if end for end for for each Cj, j = 1..M do Vj ← kmeans(Xj, K) end for V0 ← kmeans( ⋃M j=1 Vj, K0) for each Cj, j = 1..M do L←  for each vkj ∈ Vj, k = 1..K do L(vlj) = minl=1..K ( L2norm(vkj − vl0) ) end for L← sortdec(L) L← L1→Kj Vj ← argvlj(L) end for V ← ⋃Mj=0 Vj 25 P (vk|Cj) = 1 + ∑N i=1 ζ(k, i) K + ∑K s=1 ∑N i=1 1 {Ii ∈ Cj}ζ(s, i) , trong đó ζ(k, i) là số lần từ vk xuất hiện trong ảnh Ii, và 1 {Ii ∈ Cj} bằng 1 nếu điều kiện kèm theo thỏa mãn, và 0 trong trường hợp ngược lại. Laplacian smoothing được sử dụng trong công thức để triệt tiêu khả năng xác suất bị zero. Với giả định độc lập về xác suất có điều kiện, khả năng ảnh Ii thuộc về lớp Cj được tính bằng chuỗi tích tác khả năng của từng từ thị giác có mặt trong ảnh đó, P (Ii|Cj) = K∏ k=1 P (vk|Cj)ζ(k,i) Xác suất hậu nghiệm P (Cj|Ii) được suy ra dễ dàng theo công thức Bayes: P (Cj|Ii) = P (Cj)P (Ii|Cj)∑M m=1 P (Cm)P (Ii|Cm) Lớp Ĉ mà ảnh Ii thuộc về được quyết định bằng cách lựa chọn đại lượng xác suất hậu nghiệm P (Cj|Ii) có giá trị lớn nhất: Ĉ = argmin j P (Cj|Ii) 3.3 Kết quả thí nghiệm 3.3.1 Dữ liệu Chúng tôi thử nghiệm trên bộ dữ liệu ảnh sự kiện thể thao với số lượng 1545 ảnh, tham khảo từ [10], gồm có 8 loại sự kiện (Hình 3.9). Dữ liệu được lựa chọn trên tiêu chí một ảnh được gán thuộc loại sự kiện “X” nếu và chỉ nếu con người nhìn vào và có thể đoán được hoạt động thể thao nào đang được thực hiện. Chúng tôi không giới hạn về góc nhìn, môi trường, cũng như tư thế các vận động viên. Khác với [10], chúng tôi không gán nhãn và chú thích chi tiết các đối tượng trong ảnh, nhằm mục đích tìm hiểu năng lực của các kỹ thuật lấy mẫu mà không cần có thêm hướng dẫn nào khác. Hơn nữa, khi kích thước dữ liệu ngày càng lớn thì chú thích ảnh là một công việc nặng nề và đòi hỏi nhiều sức lao động. 26 Hình 3.9: Tập dữ liệu Princeton dataset [10] gồm 8 loại sự kiện: badminton (194 ảnh), bocce (137 ảnh), croquet (210 ảnh), polo (181 ảnh), rockclimbing (194 ảnh), rowing (250 ảnh), sailing (189 ảnh), snowboarding (190 ảnh) 3.3.2 Bố trí thí nghiệm Chúng tôi thực hiện các thí nghiệm trên máy laptop với cấu hình Core 2 Duo 2.26GHz, 2Gb RAM. Ảnh đầu vào sẽ được thu nhỏ kích thước nếu cần thiết. Trong bước rút trích đặc trưng, chúng tôi sử dụng chương trình được cấp sẵn từ và VLfeat toolbox [53]. Chúng tôi cũng vướng phải những giới hạn về tài nguyên tính toán nên quá trình thí nghiệm phải được điều chỉnh nhiều lần. Cụ thể, K-Means chỉ có thể chạy với K lớn nhất là 1000; 1/5 dữ liệu là tập huấn luyện, còn 4/5 dữ liệu là tập kiểm tra. Dễ thấy tỉ lệ này đặt phương pháp của chúng tôi vào tình thế không có lợi. Tuy nhiên mọi thứ cần phải được chấp nhận vì tài nguyên tính toán rất có hạn. 3.3.3 Phương pháp cơ sở Trước tiên chúng tôi thử nghiệm hiệu quả phân loại của phương pháp cơ sở trên dữ liệu vừa đề cập. Ảnh được rút trích đặc trưng bằng toán tử Harris-Laplace, sau đó mã hóa thành vector SIFT và gom cụm bằng thuật toán K-Means. Với nhiều giá trị K được thử nghiệm, kết quả nhận dạng của mỗi phân lớp sự kiện được trình bày như Hình 3.10. Trong thí nghiệm này, từ điển được xây dựng là “phẳng” và “đơn”, nghĩa rằng chúng tôi không áp dụng bất cứ kỹ thuật tăng cường nào được trình bày trong 3.2.2.Từ đây ta có thể nhận xét ngay là không có một chiều hướng cho thấy sự tương quan thống nhất giữa các loại sự kiện khi K thay đổi. Nhìn chung, tăng kích thước từ điển không giúp hệ thống cải thiện độ chính xác là bao. 27 100 200 300 400 500 600 0 10 20 30 40 50 60 70 80 90 100 Vocabulary size Av er ag e pe rfo rm an ce (% ) badminton bocce croquet polo rockclimbing rowing sailing snowboarding Hình 3.10: Khảo sát số lượng từ vựng trong từ điển để tìm giá trị tối ưu. Kết quả cho thấy mô hình truyền thống BoW không thể hội tụ cho tất cả các phân lớp. mAP=35% 3.3.4 Từ điển thô + mịn Hướng tiếp cận này khai thác đặc trưng ảnh được lấy mẫu đồng đều theo lưới vuông với ba mức tỷ lệ, 10x10, 20x20, và 30x30. Hình 3.11 thể hiện kết quả phân loại 8 sự kiến thể thao. Mặc dù kết quả đạt được tốt hơn của phương pháp cơ sở nhưng nếu so sánh với cách tạo từ điển chung + riêng (Hình 3.14), cách lấy đặc trưng theo nhiều tỉ lệ khác nhau không hiệu quả. Kết luận này sẽ một lần nữa được khẳng định trong phần tiếp theo. 3.3.5 Từ điển chung + riêng Thí nghiệm này chứng tỏ thuật toán xây dựng từ điển chung + riêng hiệu quả hơn thuật toán xây dựng từ điển thô + mịn. Nói cách khác, những cải tiến trong giai đoạn xây dựng từ điển hiệu quả hơn những điểu chỉnh ở giai đoạn rút trích đặc trưng. Trước tiên chúng tôi thử nghiệm bộ từ vựng 1000 từ và đạt kết quả như Hình 3.12. Có thể nhận thấy các sự kiện snowboarding, sailing, và rowing cùng chia sẻ các đối tượng nền như bầu trời xanh và mặt biển; hai sự kiện croquet và sailing có cùng cấu trúc tổ chức không gian (mặt nước - đồng cỏ). Cũng có thể từ nét tương đồng này, kết quả là giá trị trong bảng kết quả của (sailing, croquet) = 14%, 28 .39 .09 .05 .05 .06 .19 .10 .06 .18 .29 .11 .09 .13 .05 .05 .09 .14 .05 .49 .08 .08 .05 .05 .05 .07 .15 .10 .29 .23 .05 .05 .05 .07 .16 .05 .05 .53 .04 .05 .04 .15 .15 .08 .06 .08 .34 .10 .03 .04 .04 .13 .02 .02 .09 .44 .22 .03 .07 .04 .06 .04 .06 .19 .50 badminton bocce croquet polo rockclimbing rowing sailing snowboarding badminton bocce croquet polo rockclimbing rowing sailing snowboarding Hình 3.11: Ma trận kết quả của phương pháp sứ dụng từ điển thô + mịn theo Thuật toán 1; mAP=40.88% (rockclimbing, bocce)=32% cũng có đặc điểm tương tự. Trong thí nghiệm đầu tiên, độ chính xác không khác so với sử dụng từ điển thô + mịn. Ở thí nghiệm tiếp theo, các kích thước từ điển vẫn giữ nguyên 1000 từ nhưng số lượng từ thị giác chung giảm còn 200, ngược lại các từ thị giác riêng tăng lên 100 từ cho mỗi phân lớp. Ta có thể nhận thấy sự gia tăng đáng kể độ chính xác từ 40.62% lên 45.83% (Hình 3.13), tuy nhiên sự kiện và croquet bị giảm mạnh độ chính xác nhưng badminton lại tăng đột biến. Tiếp tục giảm số lượng từ thị giác riêng của mỗi phân lớp còn 50 từ thì độ chính xác tăng nhẹ lên 46.88% (Hình 3.14). Qua 3 thí nghiệm có thể nhận thấy kích thước từ điển nhỏ cho kết quả khả quan hơn, đồng thời số lượng từ thị giác chung không nên nhiều quá, và kết luận tương tự cho số lượng từ thị giác riêng. Để khẳng định hiệu quả của Thuật toán 3, Hình 3.15 thể hiện khả năng P (vk|CJ) của một từ thị giác vk thuộc về lớp Cj.Hiệu quả của phương pháp được thể hiện ở chỗ đối với một phân lớp thì các nhóm từ thị giác riêng của phân lớp đó được sử dụng nhiều hơn hẳn so với các từ khác. Cuối cùng chúng tôi thử nghiệm mô hình kết hợp giữa một từ điển chung + riêng và hai từ điển khác với mức độ thô khác nhau (Hình 3.16). Xác suất hậu nghiệm được tính bằng tổng các xác suất hậu nghiệm cho bởi 3 từ điển. Kết quả cho thấy 29 .34 .21 .08 .01 .02 .04 .20 .09 .09 .40 .11 .04 .05 .13 .11 .06 .13 .13 .49 .03 .01 .04 .09 .08 .10 .15 .08 .39 .04 .09 .07 .07 .06 .32 .03 .00 .34 .16 .03 .05 .17 .08 .04 .01 .03 .34 .25 .07 .03 .02 .14 .01 .02 .04 .42 .32 .01 .11 .03 .00 .00 .02 .29 .53 badminton bocce croquet polo rockclimbing rowing sailing snowboarding badminton bocce croquet polo rockclimbing rowing sailing snowboarding Hình 3.12: Ma trận kết quả cho trường hợp từ điển chung + riêng theo Thuật toán 3, 600(từ chung) + 50(từ riêng)× 8 = 1000 từ thị giác, lấy mẫu đồng đều trên một lưới kích thước 10x10, mAP=40.62% .51 .15 .02 .04 .00 .11 .13 .04 .25 .40 .05 .07 .06 .06 .03 .07 .20 .19 .31 .10 .02 .08 .05 .04 .08 .20 .06 .43 .07 .09 .01 .05 .07 .18 .04 .05 .54 .04 .01 .06 .15 .18 .01 .03 .04 .40 .08 .11 .10 .06 .11 .03 .01 .02 .45 .21 .02 .15 .02 .07 .01 .05 .04 .64 badminton bocce croquet polo rockclimbing rowing sailing snowboarding badminton bocce croquet polo rockclimbing rowing sailing snowboarding Hình 3.13: Ma trận kết quả cho trường hợp từ điển chung + riêng theo Thuật toán 3, 200(từ chung) + 100(từ riêng)× 8 = 1000 từ thị giác, lấy mẫu đồng đều trên một lưới kích thước 10x10, mAP=45.83% 30 .41 .14 .10 .01 .02 .17 .06 .09 .08 .36 .15 .07 .06 .18 .01 .08 .08 .14 .52 .05 .02 .11 .04 .03 .05 .08 .05 .52 .10 .14 .01 .04 .01 .21 .03 .02 .53 .13 .04 .03 .08 .07 .03 .07 .07 .46 .10 .10 .05 .05 .16 .02 .04 .07 .36 .24 .03 .10 .04 .02 .01 .09 .11 .58 badminton bocce croquet polo rockclimbing rowing sailing snowboarding badminton bocce croquet polo rockclimbing rowing sailing snowboarding Hình 3.14: Ma trận kết quả cho trường hợp từ điển chung + riêng theo Thuật toán 3, 200(từ chung) + 50(từ riêng)× 8 = 600 từ thị giác, lấy mẫu đồng đều trên một lưới 10x10, mAP=46.88%. Tăng số lượng lấy mẫu trên 2 lưới 10x10 và 5x5 không làm tăng độ chính xác của thuật toán. visual words e ve n t c at eg or ie s Likelihood Table 100 200 300 400 500 600 1 2 3 4 5 6 7 8 10 20 30 40 50 60 1 badminton 2 bocce 3 croquet 4 polo 5 rockclimbing 6 rowing 7 sailing 8 snowboarding Hình 3.15: Bảng Likelihood các từ thị giác xuất hiện trên các phân lớp. Những vùng càng sáng ứng với khả năng xuất hiện càng cao. Đối với từ điển chung + riêng, ta có thể nhận thấy dải từ thị giác từ 1-200 có nhiều dải sáng, đây là những từ dùng chung giữa các phân lớp; các dải từ 200-250, 250-300, v.v... ứng với từng lớp sự kiện có mức sáng rất cao so với chung quanh, chứng tỏ các từ vựng riêng được sử dụng hiệu quả, từ đó đóng góp vào sự gia tăng độ chính xác trong nhận dạng. Lưu ý hai sự kiện rowing và snowboarding dùng chung các từ thị giác riêng của nhau (góc dưới phải), ứng với kết quả phân loại nhầm lẫn là 11% và 24% trong Hình 3.14. 31 .40 .17 .05 .02 .02 .17 .05 .13 .07 .38 .11 .10 .09 .15 .01 .08 .08 .16 .48 .04 .05 .09 .05 .04 .03 .09 .05 .49 .18 .09 .01 .05 .00 .25 .02 .02 .53 .09 .03 .05 .10 .13 .03 .05 .07 .43 .09 .09 .06 .07 .16 .02 .03 .05 .36 .24 .02 .11 .03 .04 .01 .09 .20 .49 badminton bocce croquet polo rockclimbing rowing sailing snowboarding badminton bocce croquet polo rockclimbing rowing sailing snowboarding visual words e ve n t c at eg or ie s 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 Likelihood Table for 100 visual words, grid size 20x20 10 20 30 40 50 60 1 badminton 2 bocce 3 croquet 4 polo 5 rockclimbing 6 rowing 7 sailing 8 snowboarding visual words e ve n t c at eg or ie s Likelihood Table for 50 visual words, grid size 30x30 5 10 15 20 25 30 35 40 45 50 1 2 3 4 5 6 7 8 10 20 30 40 50 60 1 badminton 2 bocce 3 croquet 4 polo 5 rockclimbing 6 rowing 7 sailing 8 snowboarding Hình 3.16: Ma trận kết quả của phương pháp phối hợp sứ dụng từ điển chung + riêng theo Thuật toán 3, kích thước lưới lấy mẫu 10x10, cùng với hai từ điển thô hơn, kích thước lần lượt là 20x20 và 30x30 theo Thuật toán 2. Kết quả là độ chính xác bị giảm đi còn mAP=44.4%. Hai biểu đồ bên dưới thể hiện bảng Likelihood của các từ điển thô. Có thể nhận thấy không khác biệt lớn giữa các nhóm từ được sử dụng trong từng phân lớp sự kiện, do đó là nguyên nhân làm giảm hiệu suất. rằng mô hình kết hợp này không mang lại hiệu quả và mAP rớt xuống còn 44.4%. Có thể suy ra rằng phương pháp dựa trên từ điển thô + mịn không hiệu quả bằng việc dựa trên từ điển chung + riêng. Một lần nữa cho thấy Thuật toán 3 đạt hiệu quả tốt nhất. 3.4 Thảo luận Những phân tích trên cho thấy có sự “cạnh tranh” giữa các lớp sự kiện. Nếu một lớp sự kiện đạt mức chính xác cao, thì nhất thiết một hoặc nhiều hơn lớp sự kiện khác giảm đi độ chính xác. Sự thật đằng sau hiện tượng này trở nên rõ ràng hơn nếu ta 32 Hình 3.17: So sánh hiệu ứng gom cụm giữa Ball-tree (trái) và K-Means (phải) đặt ra một giả thuyết rằng thuật toán lượng hóa vector (cụ thể ở đây là K-Means trong giai đoạn gom cụm) lạm dụng đặc trưng của lớp này nhưng lại bỏ qua hoặc làm mất đi đặc trưng của lớp khác. Chúng tôi đặc biệt nhấn mạnh rằng hiện tượng này không phải tình cờ xảy ra trong một vài trường hợp ngẫu nhiên, mà được khẳng định là một đặc điểm tồn tại xuyên suốt với các thiết đặt thí nghiệm khác nhau. Trong mọi thí nghiệm, nếu một lớp sự kiện đã lấn át các lớp còn lại với độ chính xác cao, thì trong tất cả những thí nghiệm còn lại, điều đó lại xảy ra. Thú vị ở chỗ, đặc tính lấn át và tỉ lệ nhầm lẫn cao trong ma trận confusion không thể được giải thích chỉ bằng quan sát sự tương đồng hay khác biệt về diện mạo của ảnh. Điều này gợi ý rằng chúng tôi cần thí nghiệm với các thuật toán gom cụm khác nhau để khẳng định đặc điểm này trên cơ sở thực nghiệm. Một số biến thể [30, 36, 37] của thuật toán K-Means như Ball-tree, cây K-Means, được đề xuất để bổ khuyết cho thuật toán truyền thống (Hình 3.17). Hai thí nghiệm trên từ điểm phổ thông + chuyên biệt so với từ điển thô + mịn cho thấy tập trung cải thiện trong giai đoạn xây dựng từ điển sẽ cho kết quả tốt hơn là chú trọng vào tinh chỉnh bước rút trích và biểu diễn đặc trưng. 3.5 Kết luận Trong chương này chúng tôi đã áp dụng mô hình từ điển thị giác truyền thống vào một bài toán mới là nhận dạng sự kiện qua ảnh. Với những đề xuất mới về phương pháp lấy đặc trưng và cách xây dựng từ điển thị giác, hệ thống của chúng tôi đạt được kết quả đáng khích lệ. Chúng tôi thử nghiệm hệ thống mới trên tập dữ liệu khó về các sự kiện thể thao. Về cơ bản, chúng tôi đạt được ba mục tiêu: (i) đề xuất 33 được thuật toán tạo từ điển mới cho phép độ chính xác nhận dạng được tăng lên rõ rệt (ii) là một phương pháp tổng quát để có thể áp dụng được tất cả các sự kiện mà không cần phải thiết kế riêng thuật toán cho từng loại, (iii) không tốn nhiều công sức để gán nhãn và chú thích dữ liệu. 34