Đây là một vấn đề lớn, vì vậy tôi đã chọn viết trả lời khá dài để cố gắng phân tích vấn đề thành các phần dễ giải quyết hơn.
Điều quan trọng là việc so sánh được thực hiện bằng cách sử dụng tài nguyên tính toán và thời gian có sẵn: Tôi nghi ngờ một giải pháp mất hàng tháng để chạy sẽ rất hữu ích trong cơ sở dữ liệu video động. Và kích thước của cơ sở dữ liệu có thể làm cho việc sử dụng các tài nguyên điện toán đám mây không khả thi. Vì vậy, chúng tôi thực sự quan tâm đến chi phí địa phương của từng so sánh trong một số miền khác nhau: 1) Lưu trữ dữ liệu, 2) tính toán tài nguyên và 3) thời gian.
Một chi phí quan trọng để xem xét là việc khai thác dữ liệu cần thiết từ mỗi video đối với bất cứ số liệu so sánh là được sử dụng. Khi dữ liệu được trích xuất có sẵn, thì chi phí thực hiện so sánh phải được xem xét. Cuối cùng, các so sánh cần thiết để phù hợp với tất cả các video với nhau phải được thực hiện.
Chi phí của hai bước đầu tiên là O (1) về số lượng video. Chi phí của bước cuối cùng phải tồi tệ hơn O (1), có khả năng tồi tệ hơn nhiều. Vì vậy, mục tiêu chính của chúng tôi nên giảm thiểu chi phí của bước cuối cùng, ngay cả khi nó có nghĩa là thêm nhiều bước đơn giản, sớm.
Các thuật toán tối ưu cho quá trình này rất nhiều sẽ phụ thuộc vào các đặc tính của cơ sở dữ liệu, mức độ mà đơn và nhiều trận tồn tại. Nếu 100% video khớp với một số video khác thì chúng tôi sẽ muốn giảm thiểu chi phí của một trận đấu thành công. Tuy nhiên, trường hợp nhiều khả năng là các trận đấu sẽ rất hiếm, vì vậy chúng tôi sẽ muốn giảm thiểu chi phí của một trận đấu không thành công. Đó là để nói, nếu có một cách nhanh chóng và bẩn thỉu để nói "hai video này không thể khớp được", thì chúng ta nên sử dụng nó trước, trước khi chúng tôi bắt đầu xác nhận một trận đấu trước.
Để mô tả cơ sở dữ liệu Thử nghiệm này sẽ cho thấy cách các video dư thừa "được nhóm lại": Nếu một video nhất định có kết quả phù hợp, thì khả năng kết hợp đó có nhiều hơn một kết quả phù hợp Tỷ lệ phần trăm của tất cả các trận đấu cũng là một phần của một trận đấu nhiều? Quá trình này sẽ mang lại một 'mô hình' của cơ sở dữ liệu (một phân bố thống kê) sẽ được sử dụng để hỗ trợ lựa chọn thuật toán và điều chỉnh hệ thống. sẽ cho rằng các trận đấu tương đối hiếm. Sau tất cả, nếu có rất nhiều trận đấu, vide os sẽ "gộp", làm cho cơ sở dữ liệu nhỏ hơn một cách hiệu quả và do đó làm cho vấn đề trở nên đơn giản hơn. Giả sử vấn đề vẫn khó khăn nhất có thể.
Tôi muốn ủng hộ cách tiếp cận phân loại đa cấp, nơi chúng tôi sẽ tạo chuỗi các thuật toán liên tục thực hiện quyết định nhị phân của "hai video này không khớp"/"hai video này có thể khớp". Chỉ có thuật toán cuối cùng trong chuỗi cần xuất câu trả lời "Hai video này khớp nhau".
Thuật toán phân loại/đối sánh có thể không thành công theo một hoặc cả hai cách: False Positive (video không phù hợp bị sai lệch là trùng khớp) và False Negative (video trùng khớp được gắn nhãn sai là không phù hợp). Mỗi quyết định sai lầm này có một loạt các xác suất liên quan đến nó, và chúng tôi muốn giảm thiểu cả hai.
Vì chúng tôi đang xây dựng một thuật toán, chúng tôi muốn các thuật toán rất tốt trong việc xác định không khớp mà không có lỗi, nghĩa là chúng phải có tỷ lệ Từ chối sai rất thấp và chúng tôi không quan tâm nhiều đến tỷ lệ Chấp nhận sai . Ví dụ, bản sao video của Wierd Al có thể trông và âm thanh rất giống với bản gốc và chúng tôi có thể không thể hiển thị nó không khớp với bản gốc cho đến sau trong đường dẫn thuật toán.
Cách đơn giản nhất, nhanh nhất, thuật toán đáng tin cậy nhất nên được chạy đầu tiên, kể từ khi đa số áp đảo rộng lớn của các bài kiểm tra sẽ mang lại "không phù hợp" kết quả. Việc kiểm tra đơn giản nhất là tìm kiếm các tệp giống hệt nhau trong cơ sở dữ liệu, một cái gì đó được thực hiện bởi nhiều hệ thống tệp nhanh và đơn giản và các tiện ích bảo trì cơ sở dữ liệu. Sau khi quét này được chạy, chúng ta có thể giả định rằng chúng ta sẽ thực sự cần mở và đọc các tệp video để phát hiện sự khác biệt.
Vì so sánh video tương đối khó khăn, hãy bắt đầu với âm thanh. Hãy nghĩ về cơ sở dữ liệu như là một bộ sưu tập MP3 đầu tiên có thể chứa các bản sao. Xét cho cùng, nếu chúng ta có được một kết hợp âm thanh tốt, rất có khả năng chúng ta sẽ có một trận đấu video và ngược lại. Chúng tôi có thể nói âm thanh là một đại diện 'công bằng' cho video một cách an toàn.May mắn thay, một tìm kiếm web nhanh chóng sẽ mang lại nhiều dấu vân tay và các gói so sánh âm thanh đáng tin cậy, nhanh chóng và trưởng thành. Dấu vân tay âm thanh cần phải được tạo cho mỗi video trong cơ sở dữ liệu. Video thiếu bản âm thanh sẽ tự động rơi vào tập hợp "có thể khớp".
Nhưng có một 'hình ảnh xác thực' ở đây: Còn giọng nói thì sao? Nếu một video nhất định được mã hóa hai lần, có và không có giọng nói, chúng có phù hợp hay không? Điều gì về âm thanh tiếng Pháp so với tiếng Tây Ban Nha hoặc tiếng Anh? Nếu tất cả những điều này được coi là phù hợp, thì có thể cần bỏ qua kiểm tra âm thanh. Tại thời điểm này, chúng tôi biết các mục hệ thống tập tin là "đủ khác biệt" và chúng tôi biết các bản âm thanh là "đủ khác biệt" (nếu được kiểm tra), điều đó có nghĩa là chúng tôi không thể xem dữ liệu video nữa. May mắn thay, điều này cần phải được thực hiện chỉ cho một phần nhỏ của cơ sở dữ liệu video, vì vậy chúng tôi có thể chịu đựng một số chi phí. Như trước đây, chúng tôi sẽ vẫn muốn đầu tiên cố gắng nhanh chóng loại bỏ nhiều trận đấu hơn trước khi chúng tôi cố gắng gắn nhãn một trận đấu một cách tích cực.
Vì chúng tôi cần thay đổi độ phân giải (ví dụ: từ 1080p đến iPod), chúng tôi sẽ cần một cách để mô tả thông tin video không chỉ độc lập với độ phân giải mà còn chịu được thêm nhiễu và/hoặc dữ liệu bị mất như là một phần của việc thay đổi độ phân giải. Chúng ta phải chịu đựng những thay đổi về tốc độ khung hình (giả sử, từ 24 fps của phim đến 30 khung hình/giây). Ngoài ra còn có những thay đổi tỷ lệ khung hình để xem xét, chẳng hạn như từ 4: 3 NTSC đến 16: 9 HD. Chúng tôi muốn xử lý các thay đổi không gian màu, chẳng hạn như từ màu sang đơn sắc.
Sau đó, có các biến đổi ảnh hưởng đến tất cả những điều này cùng một lúc, chẳng hạn như chuyển mã giữa HD và PAL, đồng thời có thể ảnh hưởng đến không gian màu, tỷ lệ khung hình, tỷ lệ cỡ ảnh và độ phân giải. Việc mô tả đặc tính cũng phải chịu được một số mức độ cắt và/hoặc điền, chẳng hạn như sẽ xảy ra từ một chuyển đổi qua lại giữa tỷ lệ khung hình 4: 3 và 16: 9 (hộp thư, nhưng không quét quét &). Chúng tôi cũng nên xử lý các video đã bị cắt bớt, chẳng hạn như xóa các khoản tín dụng khỏi phần kết thúc của một phim truyện. Và, rõ ràng, chúng ta cũng phải xử lý sự khác biệt được tạo ra bởi các bộ mã hóa khác nhau được cho ăn một luồng video giống hệt nhau.
Đó là danh sách khá! Hãy xem xét một số điều chúng tôi có thể chọn không tính đến: Tôi nghi ngờ không thể tìm thấy kết quả phù hợp khi hình ảnh cong vênh, mặc dù thực tế rằng cong vênh không biến dạng là không phổ biến, đặc biệt trong phim có màn hình rộng 35mm được quét mà không tái tạo lại hình dạng (những người gầy cao). Chúng tôi cũng có thể chọn không thành công khi có hình mờ lớn ở giữa khung hình, mặc dù chúng tôi sẽ muốn chịu đựng các hình mờ nhỏ hơn ở các góc. Và cuối cùng, có thể không khớp các video bị bóp méo theo thời gian hoặc không gian bị lộn xộn, chẳng hạn như khi một người là một người yêu thích video khác hoặc đã bị lật sang trái sang phải.
Điều đó có nghĩa là che phủ không gian video? Hy vọng rằng nó là rõ ràng lý do tại sao nó là quan trọng để bắt đầu với hệ thống tập tin và âm thanh! Tức là, trước tiên hãy nghĩ về cơ sở dữ liệu của bạn giống như một bộ sưu tập MP3 trước khi xem nó như một bộ sưu tập video.
Bỏ qua âm thanh, video chỉ là chuỗi thứ tự các hình ảnh tĩnh. Vì vậy, chúng tôi đang thực sự tìm kiếm một hoặc nhiều thuật toán so sánh hình ảnh kết hợp với một hoặc nhiều thuật toán so sánh chuỗi thời gian. Điều này có thể là một trong hai cặp thuật toán riêng biệt (mô tả từng khung hình, sau đó mô tả chuỗi các khung), hoặc nó có thể được hợp nhất thành một thuật toán đơn (xem xét sự khác nhau giữa các khung).
Bản thân hình ảnh có thể bị phân hủy sâu hơn, thành hình ảnh 'cấu trúc' đơn sắc và màu 'lớp phủ'. Tôi tin rằng chúng tôi có thể bỏ qua thông tin màu một cách an toàn, nếu nó thuận tiện về mặt tính toán để thực hiện điều đó.
Từ trên, có vẻ như tôi đã giả định rằng chúng tôi sẽ phải giải mã hoàn toàn video để thực hiện bất kỳ so sánh nào trên video.Đó không nhất thiết phải là trường hợp, mặc dù so sánh dữ liệu được mã hóa có nhiều khó khăn để hạn chế tính hữu dụng của nó. Một ngoại lệ đáng kể đối với điều này là đối với các mã hóa video cấp đối tượng, chẳng hạn như MP4, nơi mà các so sánh nhiều khung hình rất cao đã được thực hiện. Thật không may, so sánh đối tượng giữa các dòng MP4 đã không nhìn thấy nhiều nghiên cứu và tôi biết không có gói nào có thể thực hiện chức năng này. Nhưng nếu bạn tìm thấy, hãy sử dụng nó!
Hầu hết các luồng video kỹ thuật số khác đều sử dụng các lược đồ mã hóa như MPEG2, Quicktime hoặc tương tự. Tất cả các lược đồ này đều sử dụng khái niệm khung chính và khung khác nhau, mặc dù mỗi khung thực hiện khác nhau. Khi các video khác nhau đang được so sánh (các video không có cùng kích thước), các khung chính và khung khác biệt sẽ không phù hợp với bất kỳ mức độ hữu ích nào. Tuy nhiên, điều này không có nghĩa là không thể, và các gói tồn tại cố gắng trích xuất thông tin hữu ích từ các luồng như vậy mà không thực hiện giải mã đầy đủ. Nếu bạn tìm thấy một trong số đó là nhanh chóng, nó có thể rơi vào một loại "tại sao không thử nó" của các xét nghiệm. Một trong những mẹo tôi sẽ sử dụng thay vì giải mã khung hoàn toàn, thay vào đó tôi sẽ giải mã chúng thành các kênh thành phần riêng biệt (HSV, HSL, YUV, bất cứ điều gì) và không phải tất cả các cách để framebuffer RGB (trừ khi đó là những gì được mã hóa, tất nhiên). Từ đây, tôi sẽ tạo ra các khung màu và độ chói (màu) riêng biệt để so sánh có thể được thực hiện trong các miền liên quan. Giải mã tất cả các cách để một framebuffer RGB có thể giới thiệu các lỗi mà có thể làm cho việc tìm kiếm các trận đấu khó khăn hơn.
Tiếp theo, tôi sẽ hủy thông tin màu. Vì video đơn sắc phải khớp với màu gốc, chúng tôi chỉ đơn giản là không quan tâm đến màu sắc!
Làm thế nào để chuỗi kết quả đơn sắc tốt nhất có thể được so sánh với một chuỗi khác có thể xuất hiện rất khác, nhưng vẫn có thể có thể phù hợp? Đã có nhiều thập kỷ nghiên cứu trong lĩnh vực này, phần lớn được phân loại theo "phát hiện kết hợp bất biến quy mô". Thật không may, rất ít nghiên cứu này đã được áp dụng trực tiếp để xác định thời điểm video thực hiện hoặc không khớp.
Vì mục đích của chúng tôi, chúng tôi có thể tiếp cận vấn đề này từ một số hướng. Đầu tiên, chúng ta phải biết cho chính mình cái gì là và không phải là một trận đấu trong miền đơn sắc. Ví dụ: chúng tôi không quan tâm đến sự khác biệt cấp pixel, vì ngay cả khi hai video phù hợp nhưng khác nhau có cùng độ phân giải, chúng tôi phải chịu đựng một số mức độ nhiễu do những thứ như sự khác biệt của bộ mã hóa.
Cách đơn giản (nhưng chậm) là chuyển đổi từng hình ảnh thành một biểu mẫu độc lập với cả độ phân giải và tỷ lệ cỡ ảnh. Một biến đổi như vậy là vào miền tần số không gian, và FFT 2D là lý tưởng cho việc này. Sau khi loại bỏ thành phần ảo, thành phần thực có thể bị cắt ngắn ở tần số cao để loại bỏ nhiễu và tần số thấp để loại bỏ các hiệu ứng tỷ lệ khung hình, sau đó chuẩn hóa theo thang đo tiêu chuẩn loại bỏ sự khác biệt về độ phân giải. Dữ liệu kết quả trông giống như một hình ảnh nhỏ lẻ kỳ lạ có thể được so sánh trực tiếp giữa các luồng video.
Có nhiều chiến lược chuyển đổi khung có thể khác, hiệu quả hơn nhiều so với FFT và tìm kiếm văn bản sẽ làm nổi bật chúng. Thật không may, tôi biết vài trong số đó đã được triển khai trong các thư viện phần mềm dễ sử dụng như FFT.
Khi chúng tôi đã chuyển đổi các khung đơn sắc thành miền nhỏ hơn và hữu ích hơn, chúng tôi vẫn phải thực hiện so sánh với một luồng khác từ một video khác. Và video đó gần như chắc chắn không phải là một kết quả khung hình để khung, vì vậy một so sánh đơn giản chắc chắn sẽ thất bại. Chúng tôi cần so sánh sẽ tính đến sự khác biệt về tài khoản trong miền thời gian, bao gồm các khung hình được thêm/xóa và sự khác biệt về tốc độ khung hình.
Nếu bạn nhìn vào chuỗi các khung FFT, bạn sẽ nhận thấy một số hành vi rất khác biệt.Cảnh mờ dần đột ngột và cực kỳ dễ phát hiện, vết cắt cũng có thể được phân biệt và thường chỉ có những thay đổi chậm thấy trong FFT giữa các lần cắt. Từ chuỗi các FFT, chúng ta có thể gắn nhãn mỗi khung hình như là hình ảnh đầu tiên sau khi cắt/mờ dần, hoặc như một khung giữa các vết cắt/mờ dần. Điều quan trọng là thời gian giữa mỗi lần cắt/phai, độc lập với các khung số giữa chúng, tạo ra một chữ ký hoặc dấu vân tay phần lớn độc lập với tốc độ khung hình.
Lấy dấu vân tay này của toàn bộ video mang lại dữ liệu nhỏ hơn rất nhiều so với chính video đó. Nó cũng là một chuỗi các con số tuyến tính, một vectơ chuỗi thời gian đơn giản, giống như âm thanh và có thể được phân tích bằng nhiều công cụ tương tự.
Công cụ đầu tiên là thực hiện mối tương quan, để xác định xem mẫu hình cắt giảm trong một video có khớp gần với video trong một video khác hay không. Nếu có sự khác biệt đáng kể, thì các video khác nhau. Nếu họ là một trận đấu gần, sau đó chỉ một vài FFTs sau mỗi lần cắt tương quan cần được so sánh để xác định xem các khung hình có tương tự đủ để phù hợp hay không.
Tôi sẽ không đi vào so sánh 2D FFT ở đây, vì có nhiều tài liệu tham khảo giúp thực hiện công việc tốt hơn nhiều so với tôi có thể.
Lưu ý: Có nhiều thao tác khác (ngoài 2D FFT) có thể áp dụng cho các khung đơn sắc để lấy vân tay bổ sung. Việc biểu diễn nội dung hình ảnh thực tế có thể được tạo ra bằng cách trích xuất các cạnh bên trong của hình ảnh (theo nghĩa đen giống như dấu vân tay FBI), hoặc bằng cách chọn lọc làm nổi bật hình ảnh và thực hiện thao tác 'blobbing' (tạo danh sách liên kết các mô tả vùng liên quan). Theo dõi sự tiến hóa của các cạnh và/hoặc các đốm màu giữa các khung có thể được sử dụng không chỉ để tạo ra các danh sách cắt, mà còn có thể được sử dụng để trích xuất các đặc tính hình ảnh cao cấp có thể bị mất bằng cách sử dụng 2D FFT.
Chúng tôi đã xây dựng một chuỗi các thuật toán so sánh phải rất nhanh trong việc tìm kiếm các kết quả không phù hợp và không đòi hỏi quá nhiều thời gian để xác định kết quả phù hợp. Than ôi, có thuật toán không phải là giải pháp! Chúng ta phải xem xét một số vấn đề liên quan đến cách các thuật toán này nên được thực hiện tốt nhất.
Trước tiên, chúng tôi không muốn mở và đọc từng tệp video nhiều lần hơn mức cần thiết, nếu không CPU có thể ngừng chờ dữ liệu từ đĩa. Chúng tôi cũng không muốn đọc thêm bất kỳ tệp nào khác ngoài tệp cần thiết, mặc dù chúng tôi không muốn ngừng đọc quá sớm và có khả năng bỏ lỡ một trận đấu sau đó. Thông tin có nên mô tả mỗi video được lưu hay nó nên được tính toán lại khi cần thiết? Giải quyết các vấn đề này sẽ cho phép một hệ thống so sánh video hiệu quả và hiệu quả được phát triển, thử nghiệm và triển khai.
Chúng tôi đã chỉ ra rằng có thể so sánh các video với một số hy vọng tìm được các kết quả phù hợp với điều kiện rất biến đổi, với hiệu quả tính toán.
Phần còn lại được để lại dưới dạng bài tập cho người đọc. ; ^)
+1 cho câu hỏi rất thú vị - nhưng điều này chắc chắn cần các thẻ khác nhau. PHP sẽ không phải là ngôn ngữ được lựa chọn ở đây. –
Tôi đồng ý @Pekka. – Josh
tôi cũng đồng ý: O dunno lý do tại sao tôi đặt ở đó: D –