Mở đầu Với sự phát triển của ngành truyền thông và mạng xã hội đã dẫn đến sự gia tăng đáng kể về số lượng video được đăng tải hàng ngày. Vì vậy, truy vấn và quản lí lượng thông tin khổng lồ đó ngày càng trở thành một thách thức đối với lĩnh vực thị giác máy tính (Computer Vision). Đồng thời, với lượng dữ liệu như vậy thì ta sẽ hỗ trợ người dùng tìm kiếm như thế nào? Với những thách thức trên, hội nghị Multi Media Modeling đã tổ chức dé tài nghiên cứu về hình thức truy van tương tác để học hỏi, đánh giá cũng như xem xét sự hiệu quả của các hệ thống tham gia qua Video Browser Showdown. Trước khi bắt đầu tìm hiểu về bài toán truy vấn thông tin đa phương tiện ta hãy nhắc lại một số khái niệm liên quan về lĩnh vực thị giác cũng như các bài toán liên quan như: ảnh, phân loại ảnh, bài toán nhận dạng, một vài ứng dụng của bài toán nhận dạng và sau đó thực hiện tìm hiểu một số nghiên cứu liên quan đã từng được áp dụng.
Kiến thức cơ sở và các nghiên cứu liên quan 2.2 Giới thiệu một sô khái niệm cơ bản và các bài toán liên quan 2.1 Một số khái niệm cơ ban Điểm anh (Pixel): Được coi là đơn vị nhỏ nhất cầu thành nên một tam ảnh. Mỗi tắm ảnh được cấu tạo nên từ hàng trăm hay hàng nghìn và có thể có đến hàng triệu pixel. Mỗi pixel có trách nhiệm lưu trữ về màu sắc hay cường độ. Các kiểu ảnh phổ biến: ¢ Ảnh nhị phân (ảnh trắng đen): Mỗi điểm ảnh chỉ có 2 màu, giá trị thường nằmở là 0 hoặc 1 hay là 0 và 255 tùy theo mục đích sử dụng.
Giá trị điểm ảnh bằng 0 là tối nhất (màu đen) và ngược lại 1 hoặc 255 là sáng nhất (màu trắng).1: Minh hoạ ảnh trắng đen. Nguồn Internet! - Ảnh xám (grayscale): Tương tự như ảnh trang đen nhưng hình ảnh lại hiển !https:/'www.com/media/images/src/459. Kiến thức cơ sở và các nghiên cứu liên quan thị thêm được độ sâu của màu hay ta còn có thể hiểu giá trị của mỗi pixel có thể nằm trong [0,1] hoặc [0,255] tùy theo dãy màu (Hình 2.2: Minh họa hình ảnh đen trắng. Nguồn Internet! ¢ Anh màu: Mỗi điểm ảnh được tạo nên bởi ba kênh màu sắc chính là đỏ (red), xanh lá (green), xanh dương (blue) và đây được gọi là hệ màu RGB.
Ta cũng có thể hình dung đối với ảnh xám (grayscale), mỗi điểm ảnh có thể nằm trong khoảng từ [0,255] thì tương tự ở đây ta có 3 màu sắc làm việc kết hợp với nhau để tạo nên một bức ảnh màu hoàn chỉnh (Hình 2.3: Minh hoa cách hiển thị một tam ảnh màu.at/dktOP ”http://www.com/images/color-channels-RGB. Kiến thức cơ sở và các nghiên cứu liên quan Dữ liệu ghi hình (Video): Dữ liệu ghi hình hay video là một dạng thông tin đa phương tiện được tập hợp từ rất nhiều ảnh tĩnh nối tiếp nhau có thể kèm theo âm thanh. Mỗi ảnh tĩnh trong chuỗi nối tiếp nhau của video sẽ được gọi là frame. Video shots: Các video ngoài việc được chia ra ở cấp độ nhỏ là các frame, nó còn được cấu tạo ở một cấp độ khác cao hơn so với các frame là các video shot.
Một video được tạo nên một hoặc nhiều video shot. Ranh giới giữa shot frame cuối cùng của video shot so với frame đầu tiên của video shot kế tiếp được gọi là shot boundary. Khung hình (Frame): Như đã được nêu ở trên là frame là một phần trong chuỗi nối tiếp nhau để tạo nên video, một frame được biểu diễn ở dang một tam ảnh và dưới góc nhìn của máy tính, ảnh là một ma trận hai chiều (ảnh trắng đen) hoặc là một tensor có ba chiều (ảnh RGB, HSV,. Ảnh được cấu tạo nên từ các điểm ảnh (pixel).
Dữ liệu âm thanh (Audio): Dữ liệu âm thanh hay audio là một loại thông tin đa phương tiên mà con người có thể tiếp nhận được bằng thính giác. Audio mang day đủ các tính chất của sóng như tần số, bước sóng, chu ki,. Dữ liệu đa phương tiện (Multimedia): Dữ liệu đa phương tiện (Multimedia) là kiểu dữ liệu được kết hợp từ nhiều dạng nội dung khác nhau. Dữ liệu đa phương tiện bao gồm tổ hợp văn bản, audio, hình ảnh, video, .và những nội dung mang tính tương tác.
Kiến thức cơ sở và các nghiên cứu liên quan 2.1 Khái niệm Fuzzy search (tim kiếm mờ) hay còn gọi là Approximate search (tim kiếm xấp xi) là khái niệm để chỉ kỹ thuật để tìm kiếm một chuỗi gần giống hoặc tương đương so với một chuỗi cho trướ. Việc sử dụng Fuzzy search vào hệ thống sẽ giúp cho người dùng dễ dàng tiếp cận được với nội dung tìm hơn khi mà người dùng có thể tìm kiếm nội dung cần tìm, ngay cả khi họ không nhớ chính xác nội dung tìm kiếm.2 Một số thuật toán So sánh substring là thuật toán đơn giản nhất để tìm kiếm gần chính xác, phương pháp này người dùng sẽ nhập vào một chuỗi và sau đó hệ thống sẽ trả về kết quả các chuỗi mà có chứa chuỗi mà người dùng nhập. Khoảng cách Levenshtein là số bước ít nhất để biến một chuỗi A thành chuỗi B thông qua ba phép biến đổi: thêm ký tự, bót ký tự, thay đổi ký tự. Chuỗi con chung dài nhất hay còn gọi là Longest common substring, là một chuỗi chung dài nhất hai chuỗi.
Ta có thể áp dụng thuật toán tìm chuỗi con chung dài nhất của hai chuỗi, sau đó so sánh độ dài của nó với độ dài của chuỗi cần tìm kiếm, nếu nó lớn hơn một giá trị định mức nào đó thì coi như chuỗi đang so sánh thoã mãn kết quả.3 Bài toán truy van video Đối với bài toán truy van video ta có thể ánh xạ về bài toán truy vấn hình ảnh. Với bài toán truy vấn hình ảnh ta có ¢ Đầu vào: hình ảnh, ký tự, chuỗi câu mang thông tin mà ta muốn tìm kiếm. Kiến thức cơ sở và các nghiên cứu liên quan + Đầu ra: danh sách các hình ảnh mang nội dung tương tự với nội dung của đầu vào. Như vậy để đưa bài toán truy vấn hình ảnh ta cần thực hiện một số bước tiền xử lí.
Đầu tiên ta thực hiện gan id cho các video có trong kho dữ liệu, tiếp theo ta chia nhỏ các video thành các video shot va gan id cho các video shot dựa trên id của video ta đã gán trước đó. Sau khi chia nhỏ video thành các video shot ta thực hiện gom cụm các frame của video shot lại thành một frame đại diện cho video shot, cuối cùng dùng các phương pháp trích xuất đặc trưng để tạo ra một không gian vector phục vụ cho qua trình tìm kiếm.1 Các đặc trưng cơ bản của video Key-frames Feature là những khung hình chính (key-frames) biểu diễn những nội dung chính, đặc điểm chính có trong một video. Thông thường, các kỹ thuật tìm kiếm sẽ tiến hành rút trích ra key-frames và thực hiệm tìm kiếm video theo đó. Object Features ta có thể địch nôm na là đặc trưng của đối tượng bao gồm các đặc trưng về màu, kích thước, vị trí,.
Các đặc trưng này được sử dụng ở hệ thống vitrivr [4], [5] hay [6], người dùng sẽ truy vấn dựa trên một số đặc trưng của đối tượng như vị trí, số lượng vật thể hay màu sắc. Audio Features hay có thể hiểu là đặc trưng về âm thanh, thông thường các đoạn video sẽ luôn có âm thanh, các âm thanh này có thể là tiếng nhạc cụ của ghi ta, của dương cầm, vĩ cầm hay thậm chí tiếng xe cộ và người nói,. Một số hệ thống sử dụng đặc trưng về âm thanh như vitrivr [4] và [7], người dùng sẽ được lựa chọn một hay nhiều nhãn âm thanh trong hệ thống để thực hiện truy £ van. Kiến thức cơ sở và các nghiên cứu liên quan 2.2 Các kỹ thuật lập chỉ mục trong không gian đa chiều Với các bài toán tìm kiếm video thì thường ta sẽ gặp các bộ dữ liệu lớn mà trong trường hợp ở khóa luận này thi bộ dữ liệu V3C1 sẽ lên đến 1.
Nếu như không tổ chức lưu trữ dữ liệu một cách hiệu quả cũng như không thực hiện index thì thời gian tim kiếm của hệ thống sẽ không đáp ứng được yêu cầu thực tiễn. Thêm vào đó số chiều rất lớn của không gian đặc trưng video sẽ khiến việc này càng trở nên cắn thiết nều muốn truy vấn một cách hiệu quả. Sau day, chúng tôi xin trình bày một số kĩ thuật index trong không gian đa chiều. + IndexFlatL2, đây là phương pháp lập chỉ mục phổ biến nhất ở các hệ thong truy vấn hiện nay, dữ liệu sẽ được đưa về một không gian vector và sử dung khoảng cách L2 (hay còn được biến đến là khoảng cách Eaculidean) để tim kiếm.
Phương pháp này có độ chính xác cao nhưng vì phải tính khoảng cách cho từng dữ liệu trong cơ sở dữ liệu nên có tốc độ thực thi lâu. * K-d tree là một phương pháp phổ biến phân chia không gian phụ thuộc vào. K-d tree sẽ phân chia tập dữ liệu thành một cây nhị phân với mỗi node sẽ là một điểm trong không gian K chiều, với các node không có lá có thể được coi như là một siêu phẳng được tạo ra để chia cắt không gian thành hai phần. * Partioning Index là một kỹ thuật phân vùng các chỉ mục với mỗi vùng sẽ chứa chỉ mục của một vùng dif liệu duy nhất.
Mô hình truy vấn video đơn giản Với bài toán truy vấn video, thường luông giải quyết chung như hình 2.4 với các bước như tiền xử lí dif liệu, rút trích đặc trưng, đánh chỉ mục, lưu trữ và thực hiện xây dựng bộ tìm kiếm. Kiến thức cơ sở và các nghiên cứu liên quan Bộ dữ liệu ban đầu Tìm kiếm 7 Kết quả / Ỷ Mô-đun rút trích đặc |! Bann chị mục =a trưng. | Bộ dữ liệu da được xử lí Hình 2.4: Kiến trúc chung để giải quyết bài toán. ! Mô hình tìm kiếm video cơ bản gồm các thành phần sau: * Phân đoạn video.
Các video trong cơ sở dữ liệu sẽ được phân đoạn thành những shot với độ dài ngắn hơn so với video ban đầu hay ta cũng có thể gọi là shot boundary. Trong quá trình này, thường một số hệ thống sẽ tiền hành rút trích luôn ca keyframes như SOMHunter [5] hay VIRET [8]. 5 Rút trích đặc trưng. Sau khi có các keyframes và shot boundary, ta sẽ tiến hành rút trích đặc trưng trên các shot boundary, keyframes này.
Các features mà ta có thể rút trích được như màu sắc chính (dominant color), các vật thể (object), âm thanh, văn bản cảnh (scene text) hay xây dựng các feature vector để biểu diễn cho các shot này.