Phân đoạn video (tiếng Anh Video Segmentation) là tiến trình phân hoạch chuỗi video thành các tập hợp rời rạc các khung liên tiếp đồng nhất theo một số tiêu chí xác định trước. Thông thường phân đoạn video là chia chúng thành các shot, lần bấm máy quay video hay cảnh. Nếu video được xem như trình tự hữu hạn các khung hình thì phân đoạn video theo thời gian là phân hoạch chúng thành những đoạn video không chồng lấn nhau.
Shot[sửa]
Trong quá trình dựng video, các trình tự khung hình của mỗi lần bấm máy quay được cắt, tách và chèn lần lượt để tạo phiên bản video đã biên tập. Thành phần chính của video là shot. Shot là trình tự liên tục các khung hình thuộc về một lần bấm máy quay trong video. Cảnh video là nhóm shot liên tục để hình thành tập ngữ nghĩa ý nghĩa. Hình 1 mô tả mô hình dữ liệu video bao gồm tệp, cảnh và shot của video.
Mục đích phân hoạch video là tìm ra ranh giới thời gian phân tách các chuỗi khung hình đồng nhất trực quan. Chuyển từ shot này sang shot khác trong video có thể là đột ngột (hard cut) hay chuyển đổi dần dần (gradual) do các hiệu ứng đặc biệt. Hiệu ứng được sinh ra khi trộn hai shot như hòa tan (dissolve), mờ dần (fade). Hiệu ứng mờ dần vào (fade in) xảy ra khi cảnh xuất hiện dần dần, mờ dần ra (fade out) khi cảnh mất đi dần dần. Hiệu ứng hòa tan từ một cảnh này sang cảnh khác, trong đó cảnh thứ nhất mờ dần vào và cảnh thứ hai mờ dần ra. Video còn có thể được phân đoạn trên cơ sở các đặc trưng văn bản, âm thanh, ảnh và chuyển động. Có nhiều kỹ thuật khác nhau được áp dụng để tách biên các shot, bao gồm (1) Tính toán sự khác biệt trên cơ sở pixel, (2) Sự khác biệt trên cơ sở thống kê (đối sánh mẫu), (3) Sự khác biệt trên cơ sở biến đổi khung hình, (4) Sự khác biệt trên cơ sở lược đồ và (5) Sự khác biệt trên cơ sở cạnh.
Phương pháp phân đoạn video[sửa]
Ý tưởng cơ bản được sử dụng trong hầu hết các phương pháp phân đoạn video là đối sánh các khung hình liên tiếp để xác định thời điểm có sự thay đổi lớn về nội dung. Phương pháp này cần định nghĩa độ đo và ngưỡng để đối sánh các khung hình liên tục. Độ đo đơn giản là tổng mức độ chênh lệch giữa điểm ảnh-điểm ảnh của hai khung hình liên tiếp, sự khác biệt về giá trị tuyệt đối của cường độ pixel giữa hai khung liên tiếp. Nếu sự chênh lệch vượt quá ngưỡng xác định trước thì biên shot tồn tại giữa hai khung hình. Sự khác biệt khung hình theo pixel nhạy cảm với nhiễu, chuyển động của vật thể và của máy ảnh, do vậy dẫn đến phát hiện sai. Hiệu năng phân đoạn video được cải thiện bằng cách đối sánh khối hay đối sánh lược đồ ảnh thay vì đối sánh các pixel đơn lẻ trong các khung hình. Nguyên lý của phương pháp này là chuyển động đối tượng ít gây ra sự khác biệt giữa các lược đồ khung hình. Nếu tìm thấy sự khác biệt lớn thì có thể là biên của lần bấm máy quay. Lựa chọn ngưỡng cho các phương pháp đối sánh rất quan trọng, nếu ngưỡng quá thấp dẫn tới một lượng lớn phát hiện sai, ngưỡng quá cao dẫn tới bỏ sót nhiều biên đoạn video. Xác định ngưỡng phù hợp thường được thực hiện bằng thực nghiệm. Kỹ thuật đối sánh giá trị điểm ảnh hay đối sánh lược đồ chỉ hiệu quả với tách biên shot biến đổi đột ngột (hardcut). Các kỹ thuật cơ sở này không xem xét phân bổ không gian màu điểm ảnh khung hình, nó không thể nhận biết biên giữa hai khung hình của hai cảnh khác nhau nhưng có lược đồ màu tương tự. Việc phân đoạn video có hiệu ứng là khá khó khăn. Sự khác biệt giữa các khung hình biến đổi dần dần lớn hơn các khung hình trong shot nhưng nhỏ hơn ngưỡng của shot. Đã có nhiều kỹ thuật khác nhau được đề xuất, bao gồm tách shot sử dụng hai ngưỡng, liên kết giá trị ngưỡng với độ lệch trung bình và độ lệch chuẩn của phân phối chênh lệch khung hình, sử dụng cửa sổ nhiều khung hình trượt trên toàn bộ video để phát hiện các biên của shot.
Phần lớn video được lưu trữ dưới dạng nén (xt. Nén video), do vậy đã có nhiều kỹ thuật phân đoạn video trực tiếp trên video nén. MPEG là chuẩn nén video hay được sử dụng. Hai loại thông tin được sử dụng để phân đoạn video nén theo chuẩn MPEG là các hệ số biến đổi cosine rời rạc DCT và thông tin chuyển động. Trong MPEG, DCT được áp dụng cho mỗi khối ảnh 8x8. Hệ số đầu tiên trong 64 hệ số DCT được gọi là hệ số DC, biểu diễn cường độ trung bình của khối. Có thể tổ hợp các hệ số DC của mỗi khối để tạo thành ảnh DC. Ảnh DC nhỏ bằng 1/64 ảnh gốc nhưng chứa các đặc trưng chính của ảnh gốc. Do vậy, nhiều nghiên cứu đề xuất phân đoạn video trên cơ sở ảnh DC. Có thể sử dụng độ đo khoảng cách khung hình-khung hình cho các ảnh DC này. Việc tính toán khoảng cách hai ảnh liên tiếp trên cơ sở ảnh DC sẽ nhanh hơn nhiều đối với việc tính toán khoảng cách trên các ảnh gốc.
Để phát hiện ranh giới cảnh, cần xác định nhóm ảnh cùng chứa thông tin liên quan ngữ nghĩa, ví dụ như cùng một vị trí vật lý hoặc cùng một hành động của đối tượng trong video. Trong khi biên shot tương đối dễ được nhận biết thì việc nhận biết biên cảnh là khá khó khăn. Các kỹ thuật có thể sử dụng là phân tích âm thanh rãnh tiếng và phân cụm shot.
Lịch sử phát triển[sửa]
Năm 1991, lần đầu tiên các phương pháp tách shot được Nagasaka và cộng sự công bố. Nagasaka mô tả phương pháp chỉ mục đối tượng video bằng cách trước hết tách shot video, sau đó tìm các đối tượng quan trọng trong các khung hình.
Năm 1993, 1994 Hampapur và Swanberg đề xuất các phương pháp tách shot video nén MPEG và JPEG chuyển động. Hampapur đề xuất tiệm cận PĐV hướng mô hình, nhận biết các biên shot trên cơ sở mô hình video. Zhang và cộng sự đề xuất phương pháp đối sánh kép sử dụng hai ngưỡng để tách shot. Ngưỡng thứ nhất để tách shot biến đổi đột ngột và ngưỡng thứ 2 để tách shot biến đổi dần dần.
Năm 1994, Arman và cộng sự đề xuất tách shot bằng biến đổi cosine rời rạc (DCT), trong đó phân tích khung hình I (x.t Nén video) trên các luồng video JPEG và MPEG.
Năm 1995, Zhang và cộng sự mở rộng tiệm cận DCT bằng cách phân tích khung hình B và P của luồng video MPEG. Tương tự, Yeo sử dụng các giá trị DC của các hệ số DCT để đối sánh các khung hình trong video nén. Zabih và cộng sự đề xuất phương pháp tách shot trên cơ sở tách cạnh các khung hình trước khi đối sánh. Hauptman và Smith sử dụng cảnh, tín hiệu âm thanh và văn bản liên quan để phân đoạn video trong dự án thư viện video số tại Trường đại học Carnegie Mellon.
Năm 1998, Wei, Drew và Li đề xuất phương pháp tách shot khi video thay đổi chiếu sáng bằng cách chuẩn hóa ảnh màu trước khi tách shot. Yu và Wolf đề xuất kỹ thuật tách shot trên cơ sở biến đổi sóng con (DWT) với giả thiết rằng khi các khung hình video biến đổi dần dần thì các thành phần tần số cao của ảnh sẽ giảm. Boreczky và Huang đề xuất các kỹ thuật phân đoạn video bằng âm thanh.
Năm 1999, Dimitrova và cộng sự đề xuất phương pháp tự động tách biên của cảnh video bằng siêu lược đồ màu.
Năm 2002, Mark Liaoff và cộng sự đề xuất thuật toán tách biên shot hiệu ứng hòa tan (dissolve), tránh phát hiện sai các chuyển động bằng cách sử dụng mô hình phân bổ nhị thức để xác định một cách hệ thống ngưỡng phân biệt hòa tan từ các chuyển động.
Năm 2004, Jesús Bescós mô tả hệ thống phần mềm thời gian thực tách shot biến đổi đột ngột và biến đổi dần dần.
Năm 2007, Tan và cộng sự đề xuất độ đo lược đồ màu khối (blocked color histogram – BCH) để đối sánh các khung hình trong tách biên shot.
Năm 2008, Yufeng Li và cộng sự đề xuất phương pháp tách shot trên cơ sở lý thuyết thông tin, sử dụng biến đổi sóng con để tách đặc trưng màu và kết cấu để phát hiện biên shot.
Năm 2013, Zhe Ming Lu và cộng sự đề xuất kỹ thuật tách shot nhanh trên cơ sở biến đổi SVD và đối sánh mẫu.
Phân đoạn video thường là bước đầu tiên trong lập chỉ mục và truy xuất video tự động dựa trên nội dung (xt. Tìm kiếm video theo nội dung). PĐV được sử dụng để duyệt video, tóm tắt video tự động, nén video dựa trên đối tượng và phát hiện, theo dõi đối tượng trong video. Các hệ thống như video theo yêu cầu, thư viện video số, đào tạo từ xa, giải trí số, gọi điện bằng video, v.v. đều sử dụng phân đoạn video.
Tài liệu tham khảo[sửa]
- Dalton Meitei Thounaojam, Amit Trivedi, Kh. Manglem Singh and Sudipta Roy, A Survey on Video Segmentation, Advances in Intelligent Systems and Computing, 2014.
- Guojun Lu, Multimedia Database Management Systems, Artech House, 1999.
- King Ngi Ngan, Hongliang Li (Editors), Video Segmentation and Its Applications, Springer Science-Business Media, 2011.
