TRECVID 2007 - BBC Rushes Summarization Baseline Methods

Tôi cũng đã từng không hiểu lắm về cái gọi là baseline methods nên giờ muốn giải thích thêm một chút về thuật ngữ này cho các bạn chưa biết hiểu thêm.

Thông thường, khi bạn nghiên cứu về một vấn đề, một bài toán nào đó, ví dụ ở đây là generate a summary clip of an input video, bước đầu tiên là tìm hiểu xem đã có ai làm về bài toán này chưa (trực tiếp hay gián tiếp), sau đó trong bước evaluation, bạn phải so sánh proposed method của bạn với các state-of-the-art methods trước đó để chứng minh rằng phương pháp của bạn là có ý nghĩa (contribution). Thông thường là vậy, nhưng có một số bài toán chưa có ai làm trước đó, hoặc nếu có chỉ gần gần giống mà thôi, vậy thì làm sao mà so sánh? Câu trả lời chính là so sánh với baseline method. Nói một cách rõ hơn, baseline method là các phương pháp đơn giản mà ai cũng có thể nghĩ đến khi giải quyết bài toán này. Tôi ko chắc là giải thích đủ rõ ràng nên đành lấy ví dụ để giải thích vậy. Ví dụ trong face recognition, baseline method chính là dùng PCA, trong document classification, baseline methods là dùng TF/IDF, bag of words model. Còn trong bài toán summarization này, baseline method là các phương pháp được CMU cài đặt với tóm tắt như sau:

1. CMU Uniform Baseline Summaries

The uniform baseline of 4% summaries is about as simple as you can make it. We select 1 second for every 25 seconds of original video. This 1 second chunk starts at 12.5 seconds into the current 25 second window and ends at 13.5 seconds.

Vì yêu cầu summary clip chỉ có kích thước tối đa 4% (=1/25) so với original video clip nên phương pháp này sẽ dùng uniform sampling. Nghĩa là họ sẽ chia original video clip thành các đoạn đều nhau, mỗi đoạn 25 seconds. Sau đó trong mỗi đoạn 25 seconds đó, trích ra một đoạn chỉ dài 1 second nằm ở giữa (từ 12.5 - 13.5). Cách này cực kì đơn giản, nên được gọi baseline là vậy.

2. CMU Color Cluster Baseline Summaries

We used our own shot boundary detector. The threshold of detecting sufficient differences between adjacent frames was lowered compared to broadcast news, to detect shot boundaries where there is dramatic motion. Hence there were more shots ('denser') than you would normally see, with 26268 shots in the development set.

From each shot we extracted a keyframe, and partitioned the keyframe into a 5x5 grid. In each grid cell, we extracted the mean and standard deviation of hue, saturation and value (HSV color space). All keyframes for a video were used in K-means clustering, with the number of clusters set to the number of seconds (rounded down) in the 4% summary.

From each cluster, the shot closest to the centroid was selected. One second from the middle of this shot was used for inclusion in the summary.

Thuật toán baseline này thì phức tạp hơn một chút, nghĩa là có dùng shot boundary detection đơn giản để identify các shot, sau đó với mỗi shot chỉ chọn ra một keyframe rồi dùng K-means để group các keyframes này thành các clusters. Số clusters được đặt bằng chính số lượng thời gian của summary clip (ví dụ summary clip chỉ có tối đa 60 seconds thì số clusters K = 60). Với mỗi cluster, chọn ra keyframe gần centroid nhất, từ keyframe này, trích ra 1 second từ shot tương ứng.

Có thể thấy hai thuật toán này khá đơn giản, được gọi là baseline vì ai cũng có thể nghĩ tới. Thách thức đối với các nhóm là làm thế nào để beat these baseline methods này.

Tôi cũng có một số ý tưởng, trao đổi ở đây, hi vọng mọi người có thể góp ý. Những ý tưởng này phải được implement sao cho kết quả phải submit vào cuối tuần sau 13 May.

1. Redundancy at frame level

Nếu các bạn đã từng dùng máy quay film, sẽ thấy khi chúng ta quay một vật nào đó, số lượng frame sẽ khá nhiều. Ví dụ bạn đưa máy quay trong khoảng 0.5 second thôi thì lúc đó số frame cũng đã là 15 frames rồi (gsử tốc độ là 30fps). Chính vì vậy mà trong summary clip, chúng ta phải cố gắng làm giảm redundancy ở mức này. Một thuật toán shot boundary detection đơn giản, sử dụng color histograms để so sánh hai frames liên tiếp, nếu khoảng cách nhỏ hơn một threshold nào đó, thì sẽ xem như thuộc về 1 shot, ngược lại sẽ tách thành 2 shots. Cách này về cơ bản cũng tương tự như bước 1 ở thuật toán baseline thứ 2 của CMU.

Như vậy, output của bước này sẽ là các fragments (tôi gọi là fragments chứ ko gọi là shots như CMU). Mỗi fragments chứa một tập các frames có color histogram gần như tương tự nhau.

2. Redundancy at segment level

Theo qui ước của NIST, summary clip sẽ gồm nhiều segments, mỗi segments mô tả một object/scene (e.g. woman and 2 puppets looking at a map) hay một event/motion (e.g. woman and 2 puppets walk off to the right). Như vậy, bước tiếp theo là làm thế nào để group các fragments thành các segments. Ví dụ trong segment "women and 2 puppets looking at a map" có thể chỉ có 1 fragment, nhưng segment "women and 2 puppets walk off to the right" phải bao gồm một số fragments mô tả chuyển động của women and 2 puppets.

Giả sử chúng ta biết được các segment boundaries, lúc này vấn đề còn lại là làm thế nào để biết 2 segments là giống nhau. Ví dụ giả sử event "women and 2 puppets walk of to the right" phải diễn đi diễn lại nhiều lần theo ý của đạo diễn thì chúng ta sẽ có vài segments như vậy, nhưng trong summary clip chỉ cần 1 segment là đủ. Cách giải quyết có thể là chúng ta dùng clustering các fragments, sau đó mỗi segment sẽ được mô tả bằng cách dùng label của các cluster này. Ví dụ seg_1: 0 1 3 2 4 6 (nghĩa là segment này có 6 fragments, fragment đầu tiên thuộc về cluster 0), seg_2: 0 7 1 3 5 2 6. Khó khăn ở đây là 2 segments tương tự nhau có thể có độ dài (= số lượng fragments) khác nhau. Mặc dầu vậy, nếu dùng BoW model, tôi nghĩ có thể là OK.

Tuy nhiên, vấn đề khó nhất hiện nay là segment boundaries. Làm thế nào để xác định nó. Cho nên bài toán tôi muốn giải quyết hiện nay đó là: Giả sử tôi có một chuỗi như sau: c1 c2 c3 ... (ví dụ 0 1 3 2 4 6 = fragment 0 thuộc cluster 0, fragment 1 thuộc về cluster 1, fragment 2 thuộc về cluster 3, etc). Làm thế nào để tìm ra các segments như mô tả ở trên.

Lê Đình Duy

Xem đầy đủ bài viết tại http://ledduy.blogspot.com/2009/07/trecvid-2007-bbc-rushes-summarization_13.html