Tài liệu Kết hợp so khớp spatial pyramid và máy véctơ hỗ trợ svm trong nhận dạng khung cảnh tự nhiên

1 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ---------------------------------------- NGUYỄN THỊ NGỌC HÀ KẾT HỢP SO KHỚP SPATIAL PYRAMID VÀ VECTO HỖ TRỢ SVM TRONG NHẬN DẠNG KHUNG CẢNH TỰ NHIÊN Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 Người hướng dẫn khoa học: PGS. TS TỪ MINH PHƯƠNG TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2012 2 MỞ ĐẦU Với sự bùng nổ của dữ liệu ảnh, việc nhận dạng ảnh theo các lớp ngữ nghĩa là một trong những nhu cầu cơ bản cho việc quản lý và truy vấn ảnh dựa trên nội dung. Thêm nữa, nhận dạng ảnh là một trong những bài toán cơ bản trong lĩnh vực thị giác máy tính và ứng dụng máy học đã nhận được sự quan tâm của nhiều nhà khoa học trên thế giới. Bài toán nhận dạng ảnh có rất nhiều thách thức từ việc ảnh được chụp dưới nhiều góc độ khác nhau, điều kiện chiếu sáng khác nhau, sự đa dạng các thể hiện của cùng một lớp ngữ nghĩa cũng như sự phức tạp của thông tin nền trong ảnh. Để giải quyết bài toán nhận dạng ảnh có 4 hướng tiếp cận, đó là so khớp mẫu, nhận dạng thống kê, nhận dạng dựa vào cấu trúc và nhận dạng theo mạng nơron. Trong đó, hướng tiếp cận dựa trên so khớp mẫu được áp dụng rộng rãi và mang lại kết quả cao trong bài toán nhận dạng ảnh nói riêng và trong thị giác máy tính nói chung. Biểu diễn một ví dụ đơn lẻ bằng tập các đặc trưng cục bộ hoặc các bộ phận bao gồm nó thường rất hữu ích. Ví dụ, trong thị giác máy tính, một hình ảnh có thể được mô tả bởi các đặc trưng cục bộ được trích chọn từ các điểm hấp dẫn “nhô ra” (salient interest points) của ảnh. Tương tự như vậy trong xử lý ngôn ngữ tự nhiên, các tài liệu và chủ đề được đặc trưng bởi túi các từ (bag of words). Tuy nhiên, việc đánh giá độ giống nhau giữa các mẫu theo phương pháp này là một thách thức khi tập các đặc trưng gồm nhiều yếu tố, các yếu tố không có thứ tự. Để so sánh tập các đặc trưng này, các nhà nghiên cứu thường cố gắng sử dụng những giải pháp phù hợp tốn ít 3 chi phí nhất, tuy nhiên đây lại là những tính toán tốn kém và trở nên không khả thi khi tập này có kích thước lớn. Những phương pháp trước đây nhận đầu vào là các véctơ với mỗi chiều tương ứng là một đặc trưng toàn cục riêng biệt. Nhược điểm của những phương pháp này là không tính tới vị trí tương đối của các đặc trưng, giải quyết với những đặc trưng tương ứng rõ ràng, điều này làm cho việc tính toán tốn kém, hạn chế việc sử dụng những đầu vào có phạm vi lớn; Do đó để cải thiện những nhược điểm này Kristen Grauman và Trevor Darrell đã phát triển phương pháp so khớp phân cấp (Pyramid Matching – viết tắt là PM) – một hàm so khớp thời gian tuyến tính mới thông qua tập các đặc trưng không có thứ tự. Mặc dù vậy phương pháp này vẫn còn nhược điểm đó là bỏ qua thông tin về không gian của bức ảnh; một phương pháp mới ra đời nhằm giải quyết nhược điểm trên đó là phương pháp so khớp không gian phân cấp (Spatial Pyramid Matching – SPM). Với những lý do nêu trên tôi đã lựa chọn đề tài: “Kết hợp so khớp spatial pyramid và máy véctơ hỗ trợ SVM trong nhận dạng khung cảnh tự nhiên” - Mục đích nghiên cứu:  Nghiên cứu trích chọn đặc trưng cục bộ bất biến (Scale Invariant Feature Transform – SIFT)  Tìm hiểu phương pháp SPM  Nghiên cứu phương pháp học máy SVM  Xây dựng chương trình demo từ những nghiên cứu và tìm hiểu nói trên. - Đối tượng và phạm vi nghiên cứu: 4  Trích chọn đặc trưng SIFT: đây là giải thuật do David 25 KẾT LUẬN VÀ KIẾN NGHỊ G.Lowe đưa ra từ năm 2004.  Phương pháp SPM: đây là phát triển từ phương pháp PM do Kristen Grauman và Trevor Darrell phát triển.  Phương pháp học máy SVM: SVM là một kỹ thuật mới và có nhiều triển vọng, được phát triển bởi Vapnik và các Kết luận Luận văn định hướng nội dung nghiên cứu vào phương pháp SPM, mô hình kết hợp SPM và phương pháp học máy SVM và ứng dụng vào bài toán nhận dạng khung cảnh tự nhiên. đồng sự tại AT&T Bell Labs. Dựa vào nghiên cứu, phân tích xây dựng phần mềm nhận dạng khung cảnh tự nhiên Từ những nghiên cứu trên đây, tôi thấy phương pháp SPM mô tả ảnh tốt thông qua một chuỗi các độ phân giải khác nhau, do vậy có thể mô tả thông tin tổng quát ở độ phân giải thô, cũng như Nội dung chính của luận văn được tổ chức thành 3 chương. thông tin chi tiết của ảnh ở độ phân giải mịn hơn. Ngoài ra, SPM có Chương 1. Tổng quan. Giới thiệu bài toán nhận dạng khả năng xử lý tốt trên tập hợp các đặc trưng không thứ tự như PM. ảnh,các hướng tiếp cận bài toán, mô hình chung của hệ thống nhận Sự kết hợp của SPM với trích chọn đặc trưng SIFT và SVM cho thấy dạng và một số ứng dụng của nhận dạng. đạt được hiệu quả cao. Mô hình trên cho phép đạt kết quả cao hơn so với cách tiếp cận kết hợp SIFT và SVM trên cơ sở dữ liệu phân loại Chương 2. Cơ sở lý thuyết. Trình bày những lý thuyết cơ khung cảnh MIT scene. bản về trích chọn đặc trưng SIFT, so khớp phân cấp không gian SPM và phương pháp học máy SVM được sử dụng trong luận văn. Chương 3. Kết hợp SPM và SVM để nhận dạng. Giới thiệu sơ lược về bộ dữ liệu sử dụng, các công cụ, tham số sử dụng để xây dựng chương trình ứng dụng SPM kết hợp học máy SVM trong nhận dạng khung cảnh. Ngoài ra, trong chương 3 cũng so sánh hiệu quả phân loại của phương pháp đề xuất và phương pháp kết hợp SIFT và SVM. Phần kết luận và kiến nghị tổng kết những kết quả đã đạt được của luận văn và hướng phát triển nghiên cứu tiếp theo. Kiến nghị Nghiên cứu phân loại ảnh dựa trên hướng tiếp cận kernel. 24 3.5 5 So sánh phương pháp thực nghiệm và phương pháp kết hợp SIFT và SVM Kết quả thực nghiệm kết hợp SIFT và SVM như sau Chương 1 - TỔNG QUAN 1.1 Bài toán nhận dạng ảnh Nhận dạng ảnh dựa trên lý thuyết về nhận dạng. Nhận dạng Kích thước từ điển Độ chính xác M = 16 M = 100 M = 200 là quá trình phân loại các đối tượng được biểu diễn theo một mô hình nào đó vào một lớp dựa theo quy luật và các mẫu chuẩn. Quá trình 69.32% 83.68% 80.58% bao gồm việc xác định các lớp của đối tượng sao cho có thể phân biệt. Bảng 3.3 Kết quả phân loại khung cảnh kết hợp SIFT và SVM Hệ thống nhận dạng sẽ thực hiện 2 việc: huấn luyện và nhận Từ bảng 3.2 và bảng 3.3 chúng ta có thể thấy rằng khi phân dạng. Trong quá trình huấn luyện, các đặc trưng sẽ được trích chọn loại với cùng một cơ sở dữ liệu MIT sence so thì phương pháp kết phù hợp cho việc biểu diễn và bộ phân loại sẽ được huấn luyện để hợp SPM và SVM có độ chính xác cao hơn so với phương pháp kết phân chia không gian đặc trưng. Quá trình nhận dạng, bộ phân loại đã hợp SIFT và SVM. được huấn luyện gán một mẫu đầu vào vào một trong các lớp dựa trên các đặc trưng đó. Một mô hình sẽ được xây dựng dựa trên các dữ liệu huấn luyện và mô hình này sẽ được sử dụng để phân loại một dữ liệu mới vào các lớp. Hình 1.1 Quá trình huấn luyện và nhận dạng của hệ thống nhận dạng 6 23 1.2 Các hướng tiếp cận trong bài toán nhận dạng Có 4 hướng tiếp cận chính cho bài toán nhận dạngError! Reference source not found. :  Nhận dạng dựa vào so khớp mẫu  Nhận dạng thống kê  Nhận dạng dựa vào cấu trúc  Nhận dạng dựa vào mạng nơron 1.2.1 So khớp mẫu Hình 3.8 Ảnh cần nhận dạng khung cảnh So khớp là một thuật toán chung trong nhận dạng, nó được sử dụng để xác định những điểm giống nhau giữa hai thực thể (các điểm, các góc, hình dạng…). Trong so khớp mẫu, các mẫu cần nhận dạng là biết trước và được so khớp với các mẫu đã lưu trữ, có tính tới các trường hợp mẫu bị quay, thay đổi tỉ lệ và bị tịnh tiến. 1.2.2 Nhận dạng thống kê 1.2.3 Nhận dạng dựa vào cấu trúc 1.2.4 Nhận dạng theo mạng nơron 1.3 Mô hình chung của hệ thống nhận dạng Về cơ bản, một hệ thống nhận dạng thường gồm các khối chính, phù hợp với các giai đoạn xử lý sau: Hình 3.9 Ảnh được nhận dạng sau khi chạy chương trình 22 7 Ngoài ra, từ bảng 3.2 ta có thể thấy tỉ lệ phân loại tăng dần từ mức 0 tới mức 2 nhưng từ mức 2 sang mức 3 thì tỉ lệ phân loại bị giảm (trừ trường hợp kích thước từ điển M = 16). Như vậy có nghĩa Ảnh Trích chọn đặc trưng là mức cao nhất của phân cấp L = 3 ảnh được chia nhỏ quá mịn do đó hiệu quả phân loại cơ bản giống với mức phân cấp L = 2. Với kích thước từ điển M = 16, hiệu quả phân loại không tốt bằng M = 100 và M = 200, tuy nhiên tỉ lệ phân loại cũng ở mức chấp nhận. Do kích thước từ điển M = 16 thì các đặc trưng có mật độ cao Phân loại hơn và không gian nhỏ hơn nhiều so với M = 100 và M = 200 nên hiệu suất phân loại tiếp tục cải thiện khi chuyển từ L = 2 sang L = 3. Hình 1.2 Mô hình chung của hệ thống nhận dạng 3.3.2 Nhận dạng khung cảnh cho một ảnh 1.4 Một số ứng dụng của nhận dạng 3.3.2.1 Tập huấn luyện 1.5 Kết luận chương Giống tập huấn luyện như phần xác định khung cảnh cho nhiều Trong chương này chúng ta đã tìm hiểu bài toán nhận dạng ảnh, các hướng tiếp cận để giải quyết bài toán. Luận văn của tôi theo ảnh. 3.3.2.2 Tập kiểm tra: Gồm một ảnh cần nhận dạng khung cảnh. 3.3.2.3 Quy trình thực nghiệm Với tập huấn luyện và kiểm tra ta đều tiến hành thực nghiệm với kích thước từ điển M =16, M =100, M =200 với lần lượt 4 mức phân cấp L =0, L =1, L =2, L =3. 3.3.1.3 Kết quả thực nghiệm Hình 3.4 và 3.5 dưới đây minh họa cho việc nhận dạng khung cảnh một ảnh: hướng tiếp cận so khớp mẫu với trích chọn đặc trưng SIFT kết hợp kernel phân cấp không gian SPM. Đây được coi là một công cụ mạnh, mềm dẻo, do đó, khả năng ứng dụng của nó là rất lớn. Trong chương tiếp theo, chúng ta sẽ nghiên cứu cơ sở lý thuyết được sử dụng trong luận văn. 8 Chương 2 - CƠ SỞ LÝ THUYẾT 2.1 Trích chọn đặc trưng cục bộ bất biến SIFT Để so sánh hoặc phân loại ảnh, cách tiếp cận thông thường là biểu diễn ảnh dưới dạng véc tơ đặc trưng bằng cách sử dụng các kỹ thuật tạo và trích chọn đặc trưng. Véctơ đặc trưng sau đó được sử dụng làm đầu vào cho các phương pháp phân loại hoặc để tính độ tương tự giữa các ảnh với nhau. Có rất nhiều dạng đặc trưng được đề 21 Chúng ta cùng tìm hiểu cụ thể file pyramids_all _16_0.mat, các file còn lại tương tự. File này lưu trữ lược đồ phân cấp đặc trưng của các ảnh trong tập huấn luyện (hoặc tập kiểm tra), là một ma trận kích thước (NxZ) với N là số lượng ảnh trong tập, Z được tính theo công thức: Z = , trong đó M là kích thước từ điển, L là mức phân cấp . Sau khi tiến hành thực nghiệm tôi thu được kết quả tỉ lệ phân loại các ảnh đúng tên khung cảnh như sau: xuất và sử dụng trong phân loại ảnh. Trong phạm vi luận văn, tôi chọn sử dụng đặc trưng cục bộ bất biến, viết tắt là SIFT làm đặc trưng biểu diễn ảnh. 2.1.1 Tổng quan về SIFT Phương pháp trích chọn đặc trưng SIFT được tiếp cận theo phương pháp thác lọc, theo đó phương pháp được thực hiện lần lượt theo các bước sau:  Dò tìm cực trị trong không gian đo (Scale space Extrema Detection)  Lọc và trích xuất các điểm đặc biệt (Keypoint Localization)  Gán hướng cho các điểm đặc trưng (Oriented Assignment)  Bộ mô tả điểm đặc trưng (Keypoint Descriptor) Bảng 3.2 Kết quả phân loại. Nội dung các ô là tỷ lệ ảnh được nhận dạng đúng Từ bảng kết quả 3.2, ta có thể thấy với cả 3 loại kích thước từ điển hầu như tỉ lệ phân loại tăng dần từ mức 0 tới mức 3. Ở mức 0 tương ứng với mô hình BoF chuẩn thì tỉ lệ phân loại đều nhỏ hơn so với các mức 1, 2, 3. Điều này chứng tỏ so với mô hình BoF chuẩn thì so khớp SPM cho kết quả phân loại tốt hơn. 20 Chúng ta cùng tìm hiểu cụ thể file histograms_16.mat, các file còn lại tương tự. File này lưu trữ lược đồ đặc trưng của các ảnh 9 2.1.2 Giải thuật SIFT 2.1.2.1 Dò tìm cực trị cục bộ trong tập huấn luyện (hoặc tập kiểm tra), là một ma trận kích thước (NxM) với N là số lượng ảnh trong tập, M là kích thước từ điển.  File lưu trữ lược đồ phân cấp đặc trưng tương ứng với 2.1.2.2 Lọc và trích xuất các điểm đặc biệt 2.1.2.3 Gán hướng cho các điểm đặc biệt kích thước từ điển và mức phân cấp, có định dạng: 2.1.2.4 Tạo bộ mô tả cục bộ pyramids_all_sizedictionary_level.mat. Bao gồm: 2.2 So khớp không gian phân cấp (SPM) o pyramids_all_16_0.mat Sau khi đã xác định được đặc trưng, chẳng hạn đặc trưng o pyramids_all_16_1.mat SIFT như mô tả ở trên, ta có thể so sánh hai ảnh với nhau bằng cách o pyramids_all_16_2.mat xác định các đặc trưng SIFT giống nhau giữa hai ảnh. Hai ảnh càng o pyramids_all_16_3.mat có chung nhiều đặc trưng SIFT giống nhau càng được coi là giống o pyramids_all_100_0.mat nhau. Tuy nhiên cách so sánh như vậy không tính tới vị trí tương đối o pyramids_all_100_1.mat o pyramids_all_100_2.mat o pyramids_all_100_3.mat o pyramids_all_200_0.mat o pyramids_all_200_1.mat o pyramids_all_200_2.mat Sau khi trích chọn đặc trưng thì mỗi ảnh được đại diện bởi o pyramids_all_200_3.mat tập các véc tơ đặc trưng trong không gian d chiều. Như vậy việc so của các vùng giống nhau giữa hai ảnh. Trong phần này, tôi sẽ giới thiệu một phương pháp cho phép phần nào sử dụng được các thông tin về vị trí tương đối giữa các vùng giống nhau giữa các ảnh. Phương pháp có tên Spatial Pyramid Matching, viết tắt là SPM. 2.2.1 So khớp phân cấp (Partial Matching) sánh hai ảnh với nhau trở thành việc đánh giá độ tương đồng của hai tập véc tơ đặc trưng. Gọi X, Y là hai tập véc tơ đặc trưng trong không gian d chiều. Grauman và Darrell đã đề xuất phương pháp so khớp phân cấp (viết tắt là PM) để ước lượng độ tương đồng giữa hai tập véc tơ này. 10 19 So khớp phân cấp thực hiện bằng cách thay thế chuỗi các lưới điểm 3.3.1.2 Quy trình thực nghiệm thô tăng dần và thu được tổng số các so khớp tại mỗi độ phân giải (resolution). Tại mỗi độ phân giải bất kỳ, hai điểm được gọi là so khớp nếu chúng rơi vào cùng một vùng con của lưới điểm; các so Với tập huấn luyện và kiểm tra ta đều tiến hành thực nghiệm với kích thước từ điển M =16, M =100, M = 200 với lần lượt 4 mức phân cấp L = 0, L =1, L =2, L = 3. khớp được tìm thấy ở độ phân giải mịn có trọng số cao hơn những so 3.3.1.3 Kết quả thực nghiệm khớp ở độ phân giải thô. Với tập huấn luyện và kiểm tra ta đều thu được các file dữ liệu:  File lưu trữ đặc trưng của các ảnh, có định dạng: dictionary_sizedictionary.mat. Bao gồm: o dictionary_16.mat o dictionary_100.mat o dictionary_200.mat Chúng ta cùng tìm hiểu cụ thể file dictionary_16.mat, các file Hình 2.5 Bên trái: So khớp cục bộ giữa tập các đặc trưng. Bên còn lại tương tự. File này lưu trữ đặc trưng của các ảnh trong tập phải: So khớp phân cấp với đầu vào là hai tập véc tơ đặc trưng. huấn luyện (hoặc tập kiểm tra), là một ma trận kích thước (Nx128) Cụ thể, chúng ta xây dựng một chuỗi lưới điểm tại các độ với N là kích thước từ điển. l phân giải 0, 1, …L; Như vậy lưới điểm ở mức l có 2 vùng con dọc theo mỗi chiều, tổng số sẽ có D = 2dl vùng con. Gọi histogram của X và Y tại lưới điểm này, do đó và và là (i) là số điểm của tập X và Y rơi vào vùng con thứ i của lưới điểm. Số lượng so khớp tại mức l được cho bởi hàm histogram intersection: (2.8) Để ngắn gọn, ta sẽ thay bởi .  File lưu trữ lược đồ đặc trưng tương ứng với kích thước điển từ của các ảnh, có histograms_sizedictionary.mat. Bao gồm: o histograms_16.mat o histograms_100.mat o histograms_200.mat. định dạng: 18 11 Lưu ý: số các so khớp ở mức l cũng bao gồm tất cả các so khớp ở mức l+1. Vì vậy, số các so khớp mới ở mức l là = 0, 1, …L-1). Trọng số (l tương ứng ở tỉ lệ l là nghịch đảo tỉ lệ chiều rộng giữa các vùng con được định nghĩa ở tỉ lệ tương ứng. Trọng số này được dùng để bù cho việc so khớp trên nhiều vùng có tỉ lệ khác nhau bởi đặc trưng cục bộ dễ tìm thấy sự so khớp ở những vùng rộng lớn hơn. Kết hợp lại chúng ta có một định nghĩa nhân so Bảng 3.1 Một số công cụ, thư viện sử dụng trong thực nghiệm Ngoài các công cụ, thư viện trên tôi còn tiến hành xây dựng 2 file xử lý dựa trên ngôn ngữ Matlab, cụ thể như sau:  (X,Y) = = + + (2.9) regMultiImg: kết hợp các module con, nhận dạng khung cảnh cho nhiều ảnh.  khớp phân cấp như sau: regSigImg: kết hợp các module con, nhận dạng khung cảnh cho một ảnh. 2.2.2 So khớp không gian phân cấp (SPM) Một trong những điểm yếu chính của PM đó là bỏ qua thông tin không gian đặc trưng cục bộ trong ảnh. Do đó để khắc phục nhược điểm này Lazebnik và các cộng sự đã đề xuất phương pháp so 3.2.3 Độ đo đánh giá độ chính xác của quá trình thực nghiệm khớp biểu diễn không gian phân cấp, viết tắt là SPM. 3.4 Kết quả thực nghiệm 3.3.1 Nhận dạng khung cảnh cho nhiều ảnh 3.3.1.1 Tập huấn luyện Gồm 8 lớp (coast, forest, highway, mountain, opencountry, insidecity, street, tallbuilding) của cơ sở dữ liệu MIT scenes, mỗi lớp chọn ngẫu nhiên 50 ảnh trong 100 ảnh để làm dữ liệu huấn luyện. 3.3.1.2 Tập kiểm tra: Gồm 50 ảnh còn lại của mỗi lớp kể trên. Hình 2.6 Lược đồ minh họa biểu diễn không gian phân cấp. 12 17 SPM sử dụng một chuỗi các lưới có kích thước khác nhau để thuật toán Kmeans được sử dụng để xây dựng từ điển từ tập các đặc chia ảnh thành các vùng con (subregion) và sau đó sử dụng mô hình trưng SIFT vừa được trích chọn. Trong luận văn tôi tiến hành thực túi đặc trưng, viết tắt là BoF để thống kê tổng hợp đặc trưng cục bộ nghiệm với 3 kích thước khác nhau của từ điển M = 16, M = 100 và trên các vùng con cố định thay vì sử dụng trên toàn ảnh như trong mô M = 200. hình BoF cổ điển, cuối cùng tập hợp các mô hình BoF trên các vùng con được nối lại theo thứ tự được định nghĩa trước để mô hình cho ảnh. Thực nghiệm tiến hành với các ảnh trong cơ sở dữ liệu MIT scene 8 lớp , tại địa chỉ: http://people.csail.mit.edu/torralba/code/spatialenvelope/spatial_enve Hình 2.7 dưới đây minh họa việc xây dựng phân cấp 3 mức cho một ảnh. Giả sử ảnh có 3 loại đặc trưng kí hiệu là hình tròn, hình thoi và hình chữ thập. Đầu tiên, ta chia ảnh thành 3 mức độ phân giải lope_256x256_static_8outdoorcategories.zip. Mỗi lớp tôi chọn 100 ảnh, lấy ngẫu nhiên 50 ảnh là tập huấn luyện, số còn lại dùng làm tập kiểm tra. khác nhau (level 0, level 1, level 2). Tiếp theo với mỗi mức độ phân giải và mỗi loại đặc trưng ta đếm số lượng đặc trưng rơi vào vùng Tất cả các thực nghiệm đều được thực hiện 10 lần với việc con. Cuối cùng, ta tính toán trọng số cho mỗi lược đồ phân cấp dựa lựa chọn ngẫu nhiên tập huấn luyện và tập kiểm tra, tỉ lệ phân loại theo công thức (2.9) được lưu sau mỗi lần chạy chương trình. Kết quả phân loại cuối cùng được tính là tỉ lệ phân loại trung bình sau 10 lần chạy riêng biệt. Việc phân loại khung cảnh trong chương trình sử dụng phương pháp học máy SVM với phân loại đa lớp, áp dụng chiến lược “một với tất cả” (one – versus – all). 3.2.2 Công cụ phần mềm sử dụng Hình 2.7 Ví dụ xây dựng phân cấp 3 mức. 16 Chương 3 - KẾT HỢP SPM VÀ SVM ĐỂ NHẬN DẠNG 13 2.3 Phương pháp học máy véc tơ hỗ trợ SVM SVM là một họ các phương pháp dựa trên cơ sở các hàm nhân (kernel) để tối thiếu hóa rủi ro cấu trúc. Phương pháp SVM ra Dựa vào cơ sở lý thuyết đã trình bày, luận đời từ lý thuyết học thống kê do Vapnik và Chervonenkis xây dựng. văn tiến hành áp dụng phương pháp so khớp spatial SVM sử dụng thuật toán học nhằm xây dựng một siêu phẳng làm cực pyramid với trích chọn đặc trưng SIFT kết hợp SVM tiểu hóa độ phân lớp sai của một đối tượng dữ liệu mới. Độ phân lớp để nhận dạng khung cảnh tự nhiên. sai của một siêu phẳng được đặc trưng bởi khoảng cách bé nhất tới 3.1 Các khối xử lý chính siêu phẳng đó. Đặc trưng cơ bản quyết định khả năng phân lớp là khả năng phân lớp những dữ liệu mới dựa vào những tri thức đã tích lũy được trong quá trình huấn luyện. Sau quá trình huấn luyện nếu hiệu suất tổng quát hóa của bộ phân lớp cao thì thuật toán huấn luyện được đánh giá là tốt. Hiệu suất tổng quát hóa phụ thuộc vào hai tham số là sai số huấn luyện và năng lực của máy học. Trong đó sai số huấn luyện là tỉ lệ lỗi phân lớp trên tập dữ liệu huấn luyện. Còn năng lực của máy học được xác định bằng kích thước Vapnik – Chervonenkis (kích thước VC). Đại lượng này được xác định bằng số điểm cực đại Hình 3.1 Các khối xử lý chính trong bài toán nhận dạng khung mà họ hàm có thể phân tách hoàn toàn trong không gian đối tượng. cảnh tự nhiên Một tập phân lớp tốt là tập phân lớp có năng lực thấp nhất (có nghĩa 3.2 Thiết lập tham số và các công cụ sử dụng cho thực nghiệm 3.2.1 Thiết lập tham số và xây dựng tập dữ liệu ảnh Trong luận văn tôi sử dụng SIFT với mật độ dày (dense SIFT) bằng cách sử dụng bộ mô tả SIFT trên vùng chữ nhật kích thước 16x16 pixel trên một lưới điểm khoảng cách 8 pixel. Sau đó, là đơn giản nhất) và đảm bảo sai số huấn luyện nhỏ. Phương pháp SVM được xây dựng trên ý tưởng này. 14 15 2.3.1 Phân lớp tuyến tính 2.3.3.2 Một số hàm kernel cơ bản 2.3.2 Vấn đề lề mềm và kernel 2.3.4 SVM cho bài toán đa lớp 2.3.3 Hàm Kernel 2.3.3.1 Giới thiệu về kernel Trong trường hợp dữ liệu không thể phân chia tuyến tính, cách tiếp cận sử dụng SVM là ánh xạ các véc tơ trong không gian gốc sang một không gian mới, thường là có số chiều lớn hơn. Vấn đề là việc tính toán các ánh xạ này có thể có độ phức tạp tính toán lớn. Để tránh việc tính toán các ánh xạ, một kỹ thuật được sử dụng là dùng các hàm nhân. Hàm nhân cho phép tính tích vô hướng giữa hai véc tơ trong không gian mới mà không cần biết ánh xạ thực của các véc tơ trong không gian đó. Hình 2.11 Sử dụng Kernel để áp dụng phân loại trên không gian đặc trưng