Khóa luận Phát hiện - Phân loại - Theo dõi đối tượng chuyển động trong hệ thống giám sát thông minh

ĐẠI HỌC QUỐC GIA TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Lan Hương PHÁT HIỆN - PHÂN LOẠI - THEO DÕI ĐỐI TƯỢNG CHUYỂN ĐỘNG TRONG HỆ THỐNG GIÁM SÁT THÔNG MINH KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công Nghệ Thông Tin HÀ NỘI – 2006 ĐẠI HỌC QUỐC GIA TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Lan Hương PHÁT HIỆN - PHÂN LOẠI - THEO DÕI ĐỐI TƯỢNG CHUYỂN ĐỘNG TRONG HỆ THỐNG GIÁM SÁT THÔNG MINH KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công Nghệ Thông Tin Cán Bộ Hướng Dẫn: PGS-TS. Nguyễn Văn Vỵ HÀ NỘI – 2006 LỜI CẢM ƠN Trước tiên, chúng em muốn gửi lời cảm ơn sâu sắc nhất đến thầy giáo PGS-TS. Nguyễn Văn Vỵ, người đã tận tình hướng dẫn em trong suốt quá trình học tập và làm khóa luận tốt nghiệp. Chúng em xin bày tỏ lời cảm ơn sâu sắc đến những thầy cô giáo đã giảng dạy chúng em trong suốt bốn năm qua, những kiến thức mà chúng em nhận được trên giảng đường đại học sẽ là hành trang giúp chúng em vững bước trong tương lai. Chúng tôi muốn gửi lời cảm ơn sâu sắc đến tất cả bạn bè, và đặc biệt là tập thể lớp K47CA , những người luôn bên chúng tôi trong suốt những tháng năm học tập và rèn luyện. Cuối cùng chúng con xin gửi tới bố mẹ, anh, chị, em và toàn thể gia đình lòng biết ơn và tình cảm yêu thương nhất. Những người luôn kịp thời động viên giúp chúng con vượt qua những khó khăn trong cuộc sống. Hà nội, ngày 20/5/2006 Nhóm Sinh viên: TrầnNguyên Khải La Tuấn Dũng Nguyễn Thị Lan Hương LỜI CAM ĐOAN Chúng tôi xin cam đoan khoá luận tốt nghiệp là do chúng tôi tự làm, không sao chép ở các tài liệu đã có. Những phần có sử dụng tài liệu trong khoá luận sẽ ghi rõ tên tài liệu trong phần tài liệu tham khảo. Mã nguồn thực hiện đều ghi rõ phần tham khảo và phần thực hiện. Hà nội, ngày 20 tháng 5 năm 2006 Nhóm sinh viên: Trần Nguyên Khải La Tuấn Dũng Nguyễn Thị Lan Hương TÓM TẮT Hệ thống giám sát thông minh đang là bài toán thu hút nhiều sự quan tâm và nghiên cứu trong những năm gần đây. Phát hiện, phân loại và theo dõi đối tượng chuyển động là các quá trình cơ bản trong quá trình xử lý hình ảnh – cốt lõi của hệ thống giám sát thông minh bằng hình ảnh. Các quá trình này có quan hệ mật thiết với nhau, quyết định hiệu quả, tính chính xác của hệ thống giám sát thông minh. Trong khóa luận tốt nghiệp này chúng tôi tập trung trình bày quá trình xử lý hình ảnh qua việc thực hiện giải quyết ba bài toán: phát hiện, phân loại và theo dõi đối tượng chuyển động. Chúng tôi đề xuất hướng giải quyết các bài toán bằng các phương pháp, thuật toán khác nhau từ đó đưa ra đánh giá cho từng bài toán cụ thể. Đồng thời, chúng tôi thiết kế và xây dựng thành công module giải quyết được hai bài toán phát hiện và theo dõi đối tương chuyển động. Từ đó, chúng tôi tiến hành thực nghiệm để đưa ra đánh giá khách quan nhất cho các khối xử lý hình ảnh trong một hệ thống giám sát thông minh. Từ khóa: Object Detection, Object Tracking, Object Classification, Video Tracking, Video Surveillance MỤC LỤC DANH MỤC HÌNH VẼ VÀ BẢNG BIỂU Hình 1-1: Mô hình các bài toán cần giải quyết trong hệ thống giám sát 6 Hình 2-1: Cấu trúc phân đoạn video 8 Hình 2-2: Chuyển đổi Lia giữa khung hình thứ 3 và thứ 4 9 Hình 2-3: Bốn khung hình khác nhau song có cùng một biểu đồ màu 10 Hình 2-4: Tổng quan các khối xử lý trong bài toán phát hiện đối tượng 11 Hình 2-5: Phát hiện các vùng ảnh nổi 12 Hình 2-6: Xử lý các vùng ảnh nổi (Foreground Processing) 12 Hình 2-7: Mô tả nhược điểm của phương pháp chênh lệch tạm thời.. 15 Hình 2-8: Xử lý các vùng ảnh nổi 17 Hình 2-9: Tổng quan của một hệ thống xác định và theo dõi. 22 Hình2-10: Các giá trị thông thường của độ phân tán cho người và xe cộ 24 Hình 2-11: Dữ liệu phân loại bi- viriate mẫu training qua 400 ảnh. 25 Hình 2-12: Quá trình phân loại, phải sau một vài khung hình đối tượng mới được xác định đúng. 26 Hình 2-13: Các đường viền của mục tiêu được sự dụng cho việc trích rút các đặc trưng chuyển động 26 Hình 2-14: (a) Elip vừa khớp( fitted elipse) (b) Khung hình sao (c) Biều đồ luồng phân loại 28 Hình 2-15: Tổng quan các khối xử lý trong bài toán theo vết đối tượng 30 Hình 2-16: Minh hoạ sự chính xác hoá đối tượng 31 Hình 2-17. Một ví dụ theo vết có sự nhập nhằng 32 Hình 2-18: Theo vết đối tượng ứng dụng trong hệ thống giám sát giao thông 33 Hình 2-19: Dự đoán trạng thái hiện tại dựa vào Kalman Filter 36 Hình 2-20: Biểu đồ xác định giá trị lớn nhất của hàm mật độ 37 Hình 2-21: Biểu đồ xác định giá trị lớn nhất của hàm mật độ trong khoảng nào đó 2 38 Hình 3-1: Phương pháp tích hợp giải quyết bài toán 40 Hình 3-2: Mô hình chi tiết các khối xử lý 41 Hình 3-3: Khối phát hiện vùng ảnh nổi 42 Hình 3-4: Minh họa thuật toán trừ ảnh 44 Hình 3-5: Minh họa quá trình xử lý các vùng ảnh nổi 48 Hình 3-6: Chi tiết khối xử lý vùng ảnh nổi 49 Hình 3-7: Vector RGB cho điểm ảnh ở vị trí x. 51 Hình 3-8: Xử lý loại bỏ bóng 52 Hình 3-9: Hai khung cảnh liên tiếp khi ánh sáng thay đổi. 53 Hình 3-10: Liên kết các khối ảnh nổi 54 Hình 3-11: Sơ đồ khối của phương pháp phân loại dựa trên hình chiếu 57 Hình 3-12: Các vùng đối tượng cận cảnh phát hiện được mẫu và các hình chiếu được trích rút. 58 Hình 3-13: Hình chiếu mẫu trong cơ sở dữ liệu mẫu với các nhãn 59 Hình 3-14: Hình chiếu đối tượng mẫu và các dấu hiệu khoảng cách gốc và co giãn. 61 Hình 3-15: Ví dụ phân loại đối tượng. 63 Hình 3-16: Lưu đồ kiểu đối tượng cho một đối tượng phát hiện được mẫu. 64 Hình 3-17: Mô hình Module chính xác hoá đối tượng và xử lý nhập nhằng 65 Hình 3-18: Mô hình module xử lý dự đoán chuyển động của đối tượng 66 Hình 3-19: Mô hình hoá thuật toán chính xác hoá đối tượng tương ứng 67 Hình 3-20:Biểu đồ xác định chính xác đối tượng tương ứng 68 Hình 3-21: Mô hình các đối tượng kết hợp với nhau 71 Hình 3-22 :Giải quyết nhập nhằng với biểu đồ màu 72 Hình 3-23: Hệ thống dự đoán chuyển động của đối tượng dựa vào mô hình SSD - MS 75 Hình 4-1: Hai đoạn phim trong điều kiện ít nhiễu 82 Hình 4-2: Đối tượng trong hình bao màu đỏ là đối tượng chuyển động được quan sát 82 Hình 4-3: Hai đoạn phim trong điều kiện nhiều nhiễu 83 Hình 4-4: Đoạn phim hai đối tượng chuyển động chồng chéo 84 Hình 4-5: Vẽ đường đi đối tượng chuyển động 85 Hình 4-6: Giao diện chương trình thực nghiệm 87 Hình 4-7 : Bao đối tượng chuyển động bằng hình bao viền 88 Hình 4-8: Bao đối tượng chuyển động bằng hình bao chữ nhật 89 Hình 4-9: Hình bao hộp chữ nhật với hai đối tượng chuyển động 89 Hình 4-10: Lấy vết đối tượng chuyển động 90 Hình 4-11: Kết quả thu được trong điều kiện quan sát nhiều nhiễu 90 Hình 4-12: Tương ứng chính xác các đối tượng 91 Hình 4-13: Xử lý chồng chéo 92 Hình 4-14: Đường đi và tọa độ chuyển động của đối tượng 93 LỜI NÓI ĐẦU Ngày nay, thuật ngữ hệ thống giám sát bằng video đã ngày càng trở nên phổ biến và dần trở thành quen thuộc với chúng ta, những người đang sống trong thời đại mới, thời đại của nền kinh tế tri thức, trong đó những thành tựu rực rỡ của công nghệ thông tin đóng vai trò chủ đạo. Ra đời từ những năm 1960 qua quá trình hoàn thiện và phát triển, ngày nay một hệ thống giám sát thông minh tự động [6] là một trong những hệ thống trợ giúp đắc lực nhất cho con người thực hiện theo dõi, giám sát. Với một bài toán giám sát giao thông một hệ thống giám sát thông minh có thể cho chúng ta biết được số lượng phương tiện lưu thông qua đoạn đường, đưa ra thông tin về tốc độ chuyển động, đường đi của đối tượng được theo dõi. Với một bài toán phát hiện, dự đoán, hệ thống giám sát thông minh có thể phát hiện một đám cháy, tự động cảnh báo cháy ở nơi được quan sát và theo dõi. Trong thời đại phát triển cao của công nghệ tự động, nhu cầu về các hệ thống giám sát theo dõi thông minh ngày càng trở nên cấp thiết đặc biệt trong các lĩnh vực an ninh, quân sự. Chính bởi vậy việc nghiên cứu và xây dựng một hệ thống giám sát thông minh bằng hình ảnh với hiệu quả và tính tin cậy cao đang là mục tiêu của nhiều nhà khoa học. Ý thức được những lợi ích mà hệ thống giám sát thông minh mang lại, chúng tôi chọn đề tài khóa luận là: ”phát hiện, phân loại và theo dõi đối tượng chuyển động trong hệ thống giám sát thông minh” để từ đó có thể áp dụng giải quyết bài toán theo dõi giám sát giao thông – một vấn đề bức bách hiện nay. Một hệ thống theo dõi giám sát thông minh bằng hình ảnh hoàn chỉnh là một tập các công nghệ thu, truyền, xử lý hình ảnh với kỹ thuật cao. Trong đó quá trình xử lý hình ảnh và đưa ra thông tin là khâu cốt lõi của hệ thống. Quá trình này được thực hiện tuần tự qua việc giải quyết các bài toán: Phát hiện đối tượng, phân loại đối tượng và theo dõi đối tượng chuyển động. Trong phạm vi khóa luận tốt nghiệp này, chúng tôi tập trung trình bày và giải quyết cốt lõi của hệ thống – quá trình xử lý hình ảnh và đưa ra thông tin. Thực chất của quá trình này là việc giải quyết bài toán khai phá dữ liệu đa phương tiện - dữ liệu hình ảnh. Khóa luận tốt nghiệp của chúng tôi được trình bày theo cấu trúc như sau: Chương 1: Tổng quan về bài toán giám sát thông minh Trình bày các vấn đề đặt ra cần giải quyết trong hệ thống theo dõi thông minh, giới thiệu bài toán phát hiện, phân loại, theo dõi đối tượng chuyển động trong hệ thống giám sát thông minh. Chương 2: Một số kỹ thuật cho bài toán phát hiện, phân loại và theo dõi đối tượng chuyển động. Trình bày một số kỹ thuật giải quyết vấn đề phát hiện, phân loại, theo dõi đối tượng chuyển động. Từ đó đề xuất các phương pháp giải quyết cho từng bài toán. Chương 3: Các giải pháp lựa chọn cho vấn đề đặt ra Trình bày cụ thể phương pháp giải quyết cho từng bài toán theo hướng thiết kế các khối xử lý cụ thể. Chương 4: Thực nghiệm và đánh giá Trình bày về việc cài đặt chương trình, xây dựng dữ liệu thực nghiệm, các quá trình thực nghiệm, kết quả thực nghiệm và các kết quả đánh giá, nhận xét các xử lý từ thực nghiệm. Kết luận: Tổng kết bài toán, những kết quả đã đạt được và chưa đạt được. Từ đó, đề xuất mục tiêu hướng tới, hướng nghiên cứu, phát triển tiếp theo. Thực hiện đề tài khóa luận tốt nghiệp này, nhóm chúng tôi gồm: Trần Nguyên Khải La Tuấn Dũng Nguyễn Thị Lan Hương Sinh viên lớp K47CA – Chuyên ngành Công Nghệ Phần Mềm Như đã trình bày ở trên, quá trình xử lý hình ảnh là việc giải quyết tuần tự ba bài toán độc lập. Vì vậy, để giải quyết hoàn thiện bài toán chúng tôi thực hiện phân công nghiên cứu và tìm hiểu từng lớp bài toán con. Trên cơ sở đó, liên kết và tổng hợp giải quyết bài toán chung. Cụ thể: Bài toán 1: Phát hiện đối tượng trong hệ thống giám sát thông minh - Trần Nguyên Khải thực hiện. Bài toán 2: Phân loại đối tượng trong hệ thống giám sát thông minh - La Tuấn Dũng thực hiện. Bài toán 3: Theo vết đối tượng trong hệ thống giám sát thông minh - Nguyễn Thị Lan Hương thực hiên. Cài đặt và thực nghiệm: Trên cơ sở lý thuyết chúng tôi phối hợp cài đặt và thực nghiệm giải quyết hai bài toán phát hiện đối tượng, theo dõi đối tượng chuyển đông. CHƯƠNG 1 TỔNG QUAN VỀ BÀI TOÁN GIÁM SÁT THÔNG MINH 1.1. Giới thiệu 1.1.1. Giới thiệu hệ thống theo dõi giám sát thông minh Ra đời từ những năm 1960 qua quá trình hoàn thiện và phát triển, ngày nay một hệ thống giám sát thông minh tự động [6] là một trong những hệ thống trợ giúp đắc lực nhất cho con người thực hiện theo dõi, giám sát. Từ các hình ảnh thu được từ những nơi được quan sát, ta có thể phát hiện được chuyển dộng của các đối tượng trong các khung hình, có thể xác định được đối tượng đó là người, phương tiện hay vật thể gì. Minh họa rõ hơn, với một bài toán giám sát giao thông một hệ thống giám sát thông minh có thể cho chúng ta biết được số lượng phương tiện lưu thông qua đoạn đường được theo dõi, đưa ra thông tin về tốc độ chuyển động, đường đi của đối tượng được theo dõi. Với một bài toán phát hiện, dự đoán, hệ thống giám sát thông minh có thể phát hiện một đám cháy, tự động cảnh báo cháy ở nơi được quan sát và theo dõi. Hiện nay, trên thế giới các hệ thống giám sát thông minh bằng hình ảnh đã được phát triển và đã chứng minh được hiệu quả nhất định trên một số lĩnh vực như giám sát hoạt động con người [6], giám sát giao thông, ... Song các hệ thống vẫn gặp phải một số tồn tại như hiệu quả của việc quan sát luôn phụ thuộc vào điệu kiện môi trường quan sát, kiểu chuyển động của đối tượng hay các lý do khách quan khác. Chính vì thế mà việc nghiên cứu và phát triển các giải pháp, công nghệ mới vẫn đang được tiến hành nhằm đáp ứng được yêu cầu về một hệ thống giám sát thông minh hoàn thiện nhất. Nghiên cứu và xây dựng một hệ thống giám sát thông minh bằng hình ảnh được thực hiện trong nhiều năm trở lại đây và đó cũng là nội dung và mục đích của khóa luận tốt nghiệp này. 1.1.2. Các bài toán cần giải quyết Một hệ thống giám sát thông minh bằng hình ảnh là một tập hợp các bài toán nhỏ. Nhìn một cách tổng quan: Đầu vào của hệ thống sẽ là hình ảnh thu được tại các điểm quan sát Đầu ra của hệ thống sẽ là các thông tin về chuyển động, hành vi, lớp… của các đối tượng được giám sát. Việc xử lý của hệ thống giám sát thông minh bằng hình ảnh tóm lại có thể hiểu là việc phân tích và xử lý hình ảnh video qua việc giải quyết các bài toán sau: Bài toán 1: Phát hiện các đối tượng chuyển động là bước cơ bản đầu tiên trong bài toán phân tích hình ảnh video, công việc này khái quát lại đó là việc tách các các đối tượng chuyển động trong từ các hình ảnh nền của các đối tượng đó. Phương pháp thường được sử dụng trong bài toán này đó là: phương pháp trừ ảnh nền, các phương pháp dựa trên thống kê, phương pháp chênh lệch tạm thời, và các phương pháp dựa trên luồng thị giác[4]. Bài toán 2: Phân lớp đối tượng là công việc phân loại ra các lớp đối tượng đã được tìm ra theo các lớp đã được định nghĩa trước như: Lớp người, lớp phương tiện, lớp động vật,… Đây là bước cần thiết để có thể tiếp tục phân tích các hoạt động của chúng. Hiện tại có hai hướng chính tiếp cận để giải quyết bài toán này đó là: Hướng tiếp cận dựa trên hình dáng của các vết và hướng tiếp cận dựa trên chuyển động của các đối tượng. Hướng tiếp cận dựa trên hình dáng của đối tượng hoàn toàn dựa vào các tính chất 2D của các vết tìm được, trong khi đó hương tiếp cận dựa trên chuyển động của đối tượng dựa trên các tính chất chuyển động của đối tượng theo thời gian. Bài toán 3: Theo dõi đối tượng đó là công việc đưa ra một chuỗi các hành vi của đối tượng chuyểng động trong một thời gian từ các khung hình thu được. Thủ tục này đưa ra các thông tin về đối tượng được theo dõi như đường đi của đối tượng, tốc độ hay hướng chuyển động của đối tượng. Từ đó có thể dự đoán được hành động của các đối tượng và mô tả được hành động của chúng. Đầu vào của quá trình này đó là các đầu ra các quá trình tìm và phân lớp đối tượng chuyển động. Các bài toán này không những được nghiên cứu và áp dụng trong các hệ thống giám sát mà còn được áp dụng trong các lĩnh vực khác như: thực tại ảo, nén hình ảnh, giao diện người máy, biên tập video và cơ sở dữ liệu đa phương tiện, là các hướng tiếp cận phát triển công nghệ đa phương tiện trong tương lai. 1.2. Khái quát các bài toán cần giải quyết Mô hình khái quát chung cho hệ thống giám sát thông minh: PHÁT HIỆN ĐỐI TƯỢNG PHÂN LỚP ĐỐI TƯỢNG THEO DÕI ĐỐI TƯỢNG THÔNG TIN ĐỐI TƯỢNG CHUYỂN ĐỘNG Hình 1-1: Mô hình các bài toán cần giải quyết trong hệ thống giám sát Trên đây là mô hình tuần tự các bước giải quyết trong một bài toán giám sát bằng hình ảnh. Chúng tôi sẽ tập trung trình bày ba phần xử lý của hệ thống giám sát khi thu nhận được các hình ảnh video thu được từ các địa điểm được giám sát. Đầu vào của bài toán là các khung hình video thu được. Qua quá trình xử lý phát hiện đối tượng chuyển động (Object Detection ) sẽ đưa ra các đối tượng chuyển động trong các khung hình video. Các đối tượng được phát hiện (cụ thể là các vết chuyển động) sẽ qua quá trình phân lớp đối tượng (Object Classification ) để phân lớp các đối tượng đó thuộc lớp nào, sự vật nào. Và cuối cùng là quá trình xử lý để theo dõi đối tượng (Object Tracking) đó là việc tìm ra đường chuyển động của đối tượng, dự đoán chuyển động, và việc xử lý các nhập nhằng trong chuyển động của nhiều đối tượng khác nhau trong một đoạn video. Từ các khung hình thu được ở các nơi quan sát, qua khối xử lý phát hiện đối tượng chuyển động sẽ xác định được đâu là đối tượng chuyển động. Cụ thể hơn, có thể chỉ ra được các đối tượng chuyển động trong đoạn video thu được một cách trực quan. Đầu ra của quá trình này sẽ là các vết, hình dạng của đối tượng chuyển động để làm đầu vào của khối phân loại đối tượng chuyển động. Khối xử lý phát hiện đối tượng chuyển động có thể coi là khối xử lý đâu tiên trong hệ thống giám sát thông minh bằng hình ảnh. Vì hiệu quả, tính chính xác của khối xử lý này sẽ ảnh hưởng đến đầu vào và đầu ra của các khối xử lý tiếp theo. Chính vì thế nó ảnh hưởng lớn đến hiệu quả và tính tin cậy của toàn hệ thống giám sát thông minh. Phân loại đối tượng là khâu trung gian và đóng vai trò quan trọng trong toàn hệ thống, vì đây là đầu vào của khối theo vết đối tượng và cũng là đầu ra của toàn bộ hệ thống. Bởi vậy đây cũng là một phần không thể thiếu trong toàn bộ hệ thống. Khối xử lý theo vết đối tượng là khối xử lý không thể thiếu trong hệ thống giám sát thông minh vì hiệu quả của khối xử lý này ảnh hưởng trực tiếp đến đầu ra của toàn bộ hệ thống. Do đó giải quyết tốt vấn đề theo vết đối tượng sẽ đưa lại tính chính xác và độ tin cậy cho hệ thống giám sát. Vấn đề này đã được nghiên cứu và phát triển trong nhiều năm, song hướng phát triển hoàn thiện các khối xử lý phát hiện, phân loại và theo dõi đối tượng chuyển động vẫn đang được quan tâm. Các hướng tiếp cận mới nhằm phát hiện, phân loại và theo dõi các đối tượng một cách hiệu quả, tính chính xác cao nhất với điều kiện môi trường, hoàn cảnh giám sát khác nhau. Chính vì vậy khóa luận tốt nghiệp này sẽ trình bày các nghiên cứu và thực nghiệm về bài toán phát hiện, phân loại, theo dõi đối tượng chuyển động trong hệ thống theo dõi, giám sát thông minh bằng hình ảnh nhằm mô hình hóa và giải quyết trọn vẹn bài toán phát hiện, phân loại, theo dõi đối tượng chuyển động tiến tới hoàn thiện môt hệ thống giám sát thông minh bằng hình ảnh với hiệu quả tính chính xác cao nhất. CHƯƠNG 2 MỘT SỐ KỸ THUẬT CHO BÀI TOÁN PHÁT HIỆN, PHÂN LOẠI VÀ THEO DÕI ĐỐI TƯỢNG CHUYỂN ĐỘNG 2.1. Tổng quan bài toán phát hiện, phân loại, theo dõi đối tượng chuyển động Bài toán xử lý video là việc xử lý tuần tự các bài toán độc lập. Các bài toán đó là: 2.1.1. Bài toán phát hiện đối tượng chuyển động Đầu vào của bài toán phát hiện đối tượng chuyển động như đã trình bày ở trên đó là các khung hình video [1] thu được từ các điểm quan sát, theo dõi. Như vậy để có thể giải quyết bài toán phát hiện đối tượng chuyển động ta cần nghiên cứu một số đặc điểm của video (đầu vào của bài toán). 2.1.1.1. Các khái niệm cơ bản về video Video là tập hợp các khung hình, mỗi khung hình là một ảnh. Shot (lia) là đơn vị cơ sở của video. Một lia là một đơn vị vật lý của dòng video, gồm các chuỗi các khung hình liên tiếp, không thể chia nhỏ hơn, ứng với một thao tác camera đơn. Scene (cảnh) là các đơn vị logic của dòng video, một cảnh gồm các lia liên quan về không gian và liền kề về thời gian, cùng mô tả một nội dung ngữ nghĩa hoặc một tình tiết. Hình 2-1: Cấu trúc phân đoạn video Khi phim được chiếu, các khung hình lần lượt được hiển thị ở tốc độ nhất định. Tốc độ thường thấy ở các định dạng video khác nhau là 30 và 25 hình/s. Như vậy một giờ video sẽ có số khung hình tương ứng là 108000 hoặc là 90000. Dù là video ở định dạng nào thì nó cũng có dung lượng rất lớn và nếu xử lý với tất cả các khung hình thì thật không hiệu quả. Phân đoạn là quá trình phân tích và chia nội dung hình ảnh video thành các đơn vị cơ sở gọi là các lia (shot). Việc lấy mẫu chính là chọn gần đúng một khung video đại diện cho mỗi lia (hoặc nhiều hơn tùy theo mức độ phức tạp của nội dung hình ảnh của lia) và được gọi là các khung-khóa [1]. Khung – khóa là khung hình đại diện mô tả nội dung chính của shot. Quá trình phân đoạn dữ liệu video tiến hành phân tích, phát hiện sự chuyển đổi từ lia này sang lia khác hay chính là sự phát hiện ranh giới giữa các lia (đó chính là đo sự