Smith-Waterman Algorithm

http://en.wikipedia.org/wiki/Smith-Waterman

Video summarization (2)

Tên bài báo: Unsupervised Summarization of Rushes Videos - Yang Liu Hong Kong polytechnic University

Input: BBC Rushes Video

Step 1. Video Segmentation
Step 2. Shot clustering
Step 3. Redundant Information and Junk Clip removal
Step 4. Final Summary Generation


Output: Video summary

Ở đây 2 bước 1 và 2 được gộp vào xử lý chung, sử dụng qui hoạch động để gán segment nào thuộc vào cluster nào
Bước số 3: Loại bỏ các redundant và junk bằng cách
Loại bỏ redundant: Mỗi cluster chỉ lấy ra clips dài nhất
Để loại junk clips: tính mean values of gradient theo vertical direction, so sánh với threshold để chỉ ra clips đó là normal hay junk
Bước 4:
- Tính toán số keyframe tối đa được lấy (dựa vào tiêu chí total of length in each summary < 4% original video)
- Keyframes extract:
  + Cách 1: sử dụng lấy mẫu đều: uniform sampling
  + Cách 2: k mean cluster
- Extend each keyframe to one-second clips and concatenating them orderly to get final summary

Video summarization (1)

Tên bài báo: Rushes Video Summarization by Object and Event Understanding - TRECVID 2007 workshop

Feng Wang - City Uninversity of Hong Kong 's method
Để có được summary video từ rushes video, đại học Hong Kong làm như sau
(rushes video ở đây là BBC rushes - Các đoạn phim, trong đó có thể chứa rất nhiều thông tin dư thừa bên trong)


1. Từ video chạy thuật toán shot detection: theo bài "Video partitioning through Temporal slide analysis" - C.W.Ngo
Sử dụng thuật toán extract keyframe theo bài: "An Innovative Algorithm for Keyframe Extraction in Video summarization" - Journal of realtime Image processing 2006

2. Junk Shot Filtering: Loại bỏ các shot sau
- Quá ngắn: < 10 frame/shot
- Các shot chỉ chứa: color bar (dải màu hay nhìn thấy trên TV khi chưa phát gì), các gray, black frame: phương pháp so sánh histogram của các keyframes với các example color bar hay các gray, black frame có sẵn

3. Subshot partition: Chia các shot thành các subshot, đây là  bước khá then chốt và Feng Wang sử dụng khác nhiều trick ở đây
3.1. Tại sao phải chia nhỏ các shot thành các subshots?
Trong rushes video thì các shots không chỉ chứa nội dung phim mà còn các cảnh dư thừa: ví dụ trao đổi giữa đạo diễn và diễn viên, cảnh được đóng đi đóng lại nhiều lần nhắm đảm bảo độ chất lượng...
3.2. Phương pháp partition
Vấn đề ở đây là cần tìm ra các điểm bắt đầu và kết thúc của một subshot
a) Sử dụng thuật toán based on camera motion estimation, sau đó sử dụng Hierarchical  Hidden Markov Model cho việc phân loại: stock, outtake, shaky và partition một shot thành các subshot theo 3 loại này
b) Tìm các retake scence: thông thường khi bắt đầu một cảnh quay, đạo diễn thường giơ tấm bảng (trên đó ghi cảnh bao nhiêu...) --> dựa vào điều này có thể lấy các frame có chứa tấm bảng này làm điểm bắt đầu của một subshot mới
c) Dựa vào các khẩu lệnh của đạo diễn để xác định điểm bắt đầu và điểm kết thúc của một subshot. Ví dụ "action", "cut"
d) feature cuối cùng là audio

4. Repetitive Subshot Removal
Đến đây chúng ta đã có các subshot, trong đó chỉ chứa nội dung liên quan đến phim. Tuy nhiên vẫn có các đoạn dư thừa: thông thường một đoạn kịch bản thường được đóng đi đóng lại nhiều lần --> nhiều subshots giống nhau --> cần được loại bỏ
Với 2 subshot: s1, s2 có hai trường hợp cần quan tâm
- s1 là subshot của s2 --> đơn giản là loại bỏ s1
- s1 và s2 là lặp lại của nhau: trường hợp này chỉ chọn subshot cuối và không loại bỏ tất cả subshot còn lại

5. Video Summarization
Đến đây đã loại bỏ các junk shot, các repetive subshot. Các subshot còn lại hầu hết là liên quan trực tiếp đến phim và useful cho việc summary
5.1. Extract feature from video
5 loại feature được extract
- Set of object
- Set of object motion activity
- List of camera motion
- The scene changes giữa các neighboring frames
- Dialogue or speech clips
5.2. Summarization
Chia các subset thành các clips, mỗi clips có độ dài 1 giây (tức là khoảng 25 frame) và overlap với clips trước 300ms
Mục đích là đi chọn tập V = {v1, v2, ...vd} that are most representive


Step1. Initialize Sum = {};
           C: tập các video clips sắp xếp theo độ representability
Step2: Chọn một cj thuộc C với representability cao nhất
           Sum = Sum + cj
Step3: Loại bỏ tất cả các clips cp mà Rep(cj, cp) > threshold
Step4: Go to step2 nếu C chưa rỗng

Hungarian algorithm

http://en.wikipedia.org/wiki/Hungarian_algorithm

MLE - Maximum Likelihood estimation

http://en.wikipedia.org/wiki/Maximum_likelihood