Chương 1: Trình bày giới thiệu tổng quan về bài toán phân loại ảnh. Ứng dụng rộng rãi đa dạng của phân loại ảnh trong cuộc sống, từ đó nêu lên ý nghĩa khoa học và ý nghĩa thực tiễn của đề tài luận văn. Thông qua những tài liệu nghiên cứu được 17 trong và ngoài nước, tác giả đặt ra mục tiêu và phương pháp thực hiện cho luận văn của mình, và cuối cùng là tóm tắt sơ lược nội dung trình bày của luận văn. Chương 2: Tóm lược lý thuyết được sử dụng trong luận văn: giải thuật SIFT dùng để trích xuất đặc trưng trong ảnh, mô hình Bow và giải thuật K-means dùng để tạo từ điển kết hợp giải thuật LLC để tạo bộ mô tả cho các đặc trưng của ảnh, cuối cùng là bộ phân loại SVM tuyến tính dùng cho việc huấn luyện và phân loại ảnh.
Chương 3: Mô tả cách thiết kế phần mềm ứng dụng phân loại xe dựa trên lý thuyết nghiên cứu ở chương 2. Trong đó sẽ giới thiệu sơ lược về tính năng của ứng dụng, cách cấu hình và sử dụng thư viện mã nguồn mở OpenCV chuyên về xử lý ảnh tích hợp với bộ thư viện giao diện tương tác MFC của Microsoft trên IDE Visual Studio. Chương 4: Trình bày kết quả ứng dụng và so sánh giữa việc kết hợp giải thuật LLC vào mô hình Bow với mô hình Bow truyền thống dựa trên thông tin về thời gian huấn luyện, độ chính xác trung bình, và thời gian nhận dạng một ảnh đầu vào. Chương 5: Kết luận dựa kết quả đạt được từ lý thuyết và thực nghiệm, cuối cùng đưa ra định hướng phát triển.
18 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT 2.1 Tổng quan về phân loại ảnh Lĩnh vực phân loại ảnh hiện nay đang được quan tâm nghiên cứu và ứng dụng rất nhiều. Phân loại ảnh được sử dụng trong nhiều ứng dụng như: nhận dạng khuôn mặt, vật thể, cảnh vật… Dùng trong phân tích nội dung video: nhận dạng hoạt động, sự kiện, tổng hợp… Dùng trong quản lý thông tin thị giác: đánh dấu, tìm kiếm khôi phục ảnh… và rất nhiều các ứng dụng như tự nhận diện khuôn mặt trong ảnh (Facebook, Google+), nhận diện ảnh và truyền thông xã hội (Kooaba). Ngày nay số lượng ảnh càng ngày càng lớn, việc phân loại ảnh bằng cách thủ công, tức là nhìn vào nội dung tấm ảnh sau đó gán chúng vào một hay nhiều lớp cụ thể nào đó không còn hiệu quả nữa. Hệ thống quản lý tập tin ảnh gồm nhiều ảnh cho nên việc làm này sẽ tốn rất nhiều thời gian, công sức và do đó là không khả thi.
Do vậy mà phải có các phương pháp phân loại tự động. Một trong những mô hình phân loại ảnh tự động phổ biến được sử dụng rộng rãi hiện này là Bow.2 Mô hình túi từ Bow 2.1 Giới thiệu Mô hình túi từ Bow là mô hình rất phổ biến trong các ứng dụng nhận dạng. Mô hình Bow mượn từ bài toán phân loại văn bản. Trong một văn bản có chứa rất nhiều từ, tương tự trong một bức ảnh có nhiều đặc trưng và mỗi đặc trưng được xem như là một từ.
(Nguồn: internet) Hình 2-1 Tương quan giữa hình ảnh và văn bản 19 Và trong mỗi loại văn bản khác nhau lại chứa những từ, cụm từ mang ngữ nghĩa đặc trưng mà khi đọc lên con người ta có thể biết được nó là loại văn bản gì. Điều đó cũng tương tự cho những đặc trưng trong một bức ảnh. (Nguồn: Recognizing and Learning Object Categories: Year 2007, Li Fei Fei) Hình 2-2 Sự khác nhau giữa hai loại văn bản Dựa vào tần số xuất hiện của các từ chuyên biệt cho từng loại văn bản, người ta có thể phân loại cho văn đó. Tương tự cho việc phân loại ảnh.
Sự khác nhau giữa các biểu đồ biểu diễn tần số xuất hiện của các đặc trưng được dùng làm đầu vào cho quá trình phân loại. (Nguồn: Recognizing and Learning Object Categories: Year 2007, Li Fei Fei) Hình 2-3 Biểu đồ tần số của các ảnh mô hình Bow 20 Mô hình túi từ gồm các bước cơ bản sau: + Đầu tiên là trích xuất các đặc trưng trong tất cả các bức ảnh. (Nguồn: Recognizing and Learning Object Categories: Year 2007, Li Fei Fei) Hình 2-4 Trích xuất đặc trưng của ảnh + Sau đó gom tất cả các đặc trưng lại với nhau, tạo thành bộ từ điển chung: (Nguồn: Recognizing and Learning Object Categories: Year 2007, Li Fei Fei) Hình 2-5 Tạo bộ từ điển từ những đặc trưng của các ảnh + Biểu diễn mỗi ảnh bằng biểu đồ tần số xuất hiện của các đặc trưng trong ảnh: (Nguồn: Recognizing and Learning Object Categories: Year 2007, Li Fei Fei) Hình 2-6 Biểu đồ tần số dùng để phân loại ảnh + Cuối cùng là dùng biểu đồ này đưa qua bộ phân loại để huấn luyện và tiến hành phân loại.2 Mô hình Hệ thống phân loại ảnh cơ bản Bow được mô tả bởi mô hình sau: 21 Hình 2-7 Mô hình Bow Để phát hiện và trích xuất các đặc trưng người ta có rất nhiều lựa chọn: Harris- Affine, Hessian-Affine, MSER, IBR &EBR, Salient region detector, SIFT, HOG (Histogram of Oriented Gradients), SUFT, CENTRIST, filter-based. Đề tài luận văn đã chọn SIFT với độ ổn định, chính xác cao, ít bị ảnh hưởng bởi góc nhìn, ảnh bị xoay.
Hình 2-8 Bước trích xuất đặc trưng Từ những đặc trưng đó ta sẽ tạo thành bộ từ điển với số lượng từ được định nghĩa trước, có rất nhiều giải thuật làm được điều này: K-means clustering, Vocabulary tree, Gaussian Mixture model, Randomized clustering forest, Information loss minization, Latent mixture model, Compact codebooks. Với những cụm dữ liệu lớn, 22 giải thuật K-means thường được tin dùng vì tính toán đơn giản, hội tụ nhanh để đạt tối ưu địa phương. Giải thuật này cũng được tin dùng trong đề tài luận văn. Hình 2-9 Nhóm các đặc trưng lại thành cụm Hình 2-10 Dùng một đặc trưng đại diện cho một cụm Từ mỗi tấm ảnh cần nhận dạng được trích xuất rất nhiều đặc trưng, mỗi đặc trưng này cần được mã hóa dựa vào bộ từ điển.
Phương pháp mã hóa được sử dụng trong mô hình Bow truyền thống là lượng tử vec-tơ VQ. Mỗi đặc trưng sẽ được biểu diễn bằng một vec-tơ có số phần từ bằng số từ trong từ điển, và tất cả các phần tử đều bằng 0 trừ phần tử ở vị trí k, tương ứng với vị trí đặc trưng K trong từ điển giống với đặc 23 trưng của ảnh đưa vào nhất. Việc tìm kiếm đặc trưng của ảnh đầu vào tương ứng với đặc trưng nào trong từ điển sẽ dùng giải thuật Brute Force Matcher. (Nguồn: internet) Hình 2-11 Vec-tơ lượng tử biểu diễn thông qua bộ từ điển Với hình trên là những vec-tơ mã hóa cho 3 đặc trưng đầu vào có đặc điểm tương tự, giống với đặc trưng thứ ba, thứ nhất, và thứ hai theo thứ tự trong từ điển.
Đây gọi là mã hóa đặc trưng. Một bức ảnh sẽ có nhiều đặc trưng, mỗi đặc trưng được mã hóa theo từ điển, ta cần tổng hợp các mã này lại để biểu diễn chung cho một tấm ảnh. Có nhiều cách để tổng hợp. Ta có thể dùng phép tính tổng, phép lấy giá trị lớn nhất, hoặc hỗn hợp giữa hai phương pháp.
(Nguồn: internet) Hình 2-12 Kết hợp các vec-tơ lượng tử Dưới đây là ví dụ về phép tính tổng: (Nguồn: Locality-constrained Linear Coding for Image Classification, Jiniun Wang) 24 Hình 2-13 Vec-tơ thể hiện tần số xuất hiện các từ trong từ điển Những vec-tơ thể hiện tần số này sẽ là dữ liệu đầu vào cho các bộ phân loại. Có thể sử dụng nhiều phương pháp như: bộ SVM tuyến tính hoặc phi tuyến, Nearest- neighbor, Boosting, Naive Bayes, Hierarchical Baysian. (Nguồn: internet) Hình 2-14 Phân loại dựa vào các vec-tơ tần số Nhiều bài báo và nghiên cứu cho thấy phương pháp Bow kết hợp bộ SVM phi tuyến sẽ cho ra kết quả phân loại cao, tuy nhiên thời gian xử lý sẽ lâu do tính toán phức tạp. Đề tài này sẽ cải tiến khâu tổng hợp các mã đặc trưng sử dụng giải thuật mã hóa tuyến tính cục bộ LLC để có thể sử dụng bộ SVM tuyến tính để giảm thời gian huấn luyện, nhận dạng, và nâng cao độ chính xác.3 SIFT Một thuật toán tiêu biểu và có hiệu quả khá cao là dựa theo các đặc trưng cục bộ bất biến trong ảnh: SIFT do David Lowe đưa ra từ năm 2004 và đến nay đã có nhiều cải tiến trong thuật toán.
Đặc trưng được trích chọn trong SIFT là các điểm đặc biệt 25 (keypoint), các điểm này kèm theo các mô tả về nó và một vec-tơ có lấy keypoint làm điểm gốc. Có bốn giai đoạn chính được thực hiện trong thuật toán để trích xuất các điểm đặc biệt và các đặc trưng của nó bao gồm: a. Dò tìm cực trị trong không gian đo (Scale-space Extrema Detection): Bước đầu tiên này sẽ áp dụng hàm sai khác Gaussian (DoG - Deffirence of Gaussisan) để tìm ra các điểm có khả năng làm điểm đặc trưng tiềm năng (candidate keypoints), đó là những điểm rất ít phụ thuộc (bất biến) vào sự thu phóng ảnh và xoay ảnh. Lọc và trích xuất các điểm đặc biệt (Keypoint localization): Từ những điểm tiềm năng ở trên sẽ lọc và lấy ra tập các điểm đặc trưng tốt nhất (keypoints).
Gán hướng cho các điểm đặc trưng (Oriented Assignment): Mỗi điểm đặc trưng sẽ được gán cho một hoặc nhiều hướng dựa trên hướng gradient của ảnh. Mọi phép toán xử lý ở các bước sau này sẽ được thực hiện trên những dữ liệu ảnh mà đã được biến đổi tương đối so với hướng đã gán, kích cỡ và vị trí của mỗi điểm đặc trưng. Nhờ đó, tạo ra một sự bất biến trong các phép xử lý này. Bộ mô tả điểm đặc trưng (Keypoint Description): Các hướng gradient cục bộ được đo trong ảnh có kích cỡ cụ thể nào đó trong vùng lân cận với mỗi điểm đặc trưng.
Sau đó, chúng sẽ được biễu diễn thành một dạng mà cho phép mô tả các tầng quan trọng của quá trình bóp méo hình dạng cục bộ và sự thay đổi về độ sáng. Tập các điểm đặc biệt thu được thường phụ thuộc rất ít vào các phép biến đổi cơ bản như xoay, phóng to, thu nhỏ, tăng giảm cường độ sáng… Vì vậy có thể xem đây là các đặc trưng mang tính cục bộ của ảnh. Để đối sánh và nhận dạng hai ảnh thì ta tìm tập keypoint giống nhau trong hai ảnh, dựa vào hướng và tỉ lệ để có thể biết đối tượng trong ảnh gốc đã xoay, thu phóng bao nhiêu so với ảnh đem đối sánh. Cách tiếp cận của thuật toán này dựa vào điểm bất biến cục bộ của ảnh, chúng được trích xuất ra, được định hướng và mô tả sao cho hai keypoint ở hai vùng khác nhau thì khác nhau.