Mô hình mạng Bayes cho bài toán phân đoạn video

16 Chương 3: Mô hình mạng Bayes cho bài toán phân đoạn video 3.1 Giới thiệu Phương pháp được sử dụng để phân đoạn trong luận văn là mô hình dựa trên xác suất do Wang-Yang đề xuất trong bài báo[57]. Phương pháp này rất gần với công trình của Chang[6] và và Patras[37] về mặt lí thuyết và nguyên lý. Cả 2 phương pháp này dùng MAP-MRF để ước lượng đặc trưng vector chuyển động và các phân vùng đối tượng. Phương pháp đề xuất bởi Chang dựa trên 2 khung hình liên tiếp và không hề dùng phân đoạn cường độ trong quá trình phân đoạn video. Dù thuật toán đã thành công xác định nhiều đối tượng chuyển động trong hoạt cảnh, trong các kết thử nghiệm biên của đối tượng vẫn chưa được chính xác. Phương pháp của Patras dùng phân đoạn cường độ làm khởi tạo và dựa trên 3 khung hình để giải quyết vấn đề che khuất. Tuy nhiên, phương pháp này vẫn lộ rõ những điểm yếu của phương pháp sát nhập các vùng. Phương pháp này không dùng thông tin biên và không tận dụng mối liên hệ giữa thông tin không gian và thông tin thời gian. Phương pháp do Wang Yang đề xuất trong đó đặc trưng thời gian (tức là đặc trưng chuyển động) và đặc trưng không gian (tức là đặc trưng cường độ) kết hợp và tương tác với nhau. Mục đích của sự kết hợp này là tạo ra sự ràng buộc không gian – thời gian trong kết quả phân đoạn. Sự kết hợp và tương tác này được biểu diễn thông qua mạng Bayes. Trường ngẫu nhiên Markov có mục đích để tác động đẩy mạnh quá trình liên kết về không gian giữa các phân vùng. Trong mô hình có 3 trường tương tác với nhau. Đó là vector chuyển động, vùng phân đoạn cường độ và vùng phân đoạn video (đối tượng). Các vùng trong phân đoạn cường độ có thể hợp nhất hoặc tách ra dựa trên thông tin chuyển động. Thông tin biên bị mất trong trường phân đoạn cường độ có thể được khôi phục bằng trường vector chuyển động. 17 Phương pháp này có thể được xem là sự kết hợp của phương pháp dựa trên chuyển động và phương pháp hợp nhất vùng. Quá trình phân đoạn dựa trên 3 ý tưởng chính: - Đầu vào của quá trình phân đoạn là 3 khung hình liên tiếp nhau. Các thông tin không gian và thời gian được rút trình từ dữ liệu của 3 khung hình qua phép tính cực đại hóa xác suất hậu nghiệm. - Xây dựng hàm mục tiêu và quá cực tiểu hóa hàm mục tiêu lặp đi lặp lại để cho ra kết quả tối ưu. - Phép biến đổi khoảng cách áp dụng vào giai đoạn tối ưu cục bộ nhằm kết hợp với thông tin đường biên rút ra được từ kết quả phân đoạn cường độ. 3.2 Phương pháp 3.2.1 Phát biểu bài toán Dữ liệu video là một chuỗi N khung hình với k=1..N. zk,i là đối tượng thứ i trong khung hình gk với i=1..Mk. Với Mk là số đối tượng trong khung hình gk. zk,i là tập các điểm ảnh thuộc đối tượng thứ i trong khung hình gk. Mục tiêu của bài toán là gán nhãn điểm ảnh trong khung hình gk có giá trị nhãn z là i tương ứng với điểm ảnh trong khung hình gk-1 có giá trị nhãn z là i. Hay nói cách khác, với điều kiện cho trước kết quả phân đoạn trong khung hình gk-1 và ba khung hình liên tiếp gk-1, gk, gk+1 cần phải gán nhãn z cho các điểm ảnh trong khung hình gk. Như vậy, vùng zk,i là tập các điểm (x,y) sao cho cực đại hóa xác suất ) 18 3.2.2 Mô hình Đầu vào là một chuỗi các khung hình, giả định rằng không có sự thay đổi về cường độ sáng và không có hiện tượng che khuất. Mô hình bài toán có thể phát biểu như sau: (3.1) Với y k (x) là cường độ của điểm ảnh trong khung hình thứ k tại vị trí x, với k ∈ N, x ∈ X, và X là vùng không gian của mỗi khung hình. d k (x) là vector chuyển động từ khung hình k-1 đến khung hình k. Trường vector chuyển động toàn cục được biểu diễn ngắn gọn là d k . Nhiễu là hiện tượng tất yếu vì vậy một mô hình nhiễu cần được thêm vào mô hình. Giả định rằng đó là nhiễu Gauss, là phân phối độc lập và xác định (i. i. d.) làm nhiễu giá trị cường độ tại các điểm ảnh, do đó mô hình quan sát cho khung hình thứ k trở thành: (3.2) Với g k (x) là cường độ ảnh quan sát tại vị trí x, n k (x) là nhiễu, nhiễu này độc lập có giá trị trung bình là 0 và variance là . Trong nghiên cứu này, phân đoạn video được xem là bài toán gom nhóm các điểm ảnh thuộc cùng một đối tượng chuyển động độc lập trong hoạt cảnh. Để giải quyết vấn đề che khuất, giả thiết là mỗi điểm x, khung hình hiện hành g k không thể bị che khuất ở cả khung hình trước và sau. Do đó phương pháp dựa trên 3 khung hình liên tiếp dùng cho bài toán này. Cho trước các khung hình liền nhau của chuỗi video quan sát g k–1 , g k , g k+1. Cần phải ước lượng phân phối xác xuất có điều kiện kết hợp của trường vector chuyển động d k , trường phân đoạn cường độ s k , và trường phân đoạn đối tượng (hay video) z k . Dùng luật Bayes, ta có: (3.3) 19 Với p(d k , s k , z k | g k , g k–1 , g k+1 ) là hàm mật độ xác suất hậu nghiệm (pdf) của 3 trường, và mẫu số ở vế phải là hằng số chưa biết. Mô hình mạng Bayes trong hình (3.1) thể hiện sự tương tác giữa d k , s k , z k , g k , g k–1 , g k+1 Hình 3.1: Mô hình mạng Bayes cho bài toán phân đoạn video. Từ 3 khung hình liên tiếp có thể ước lượng được trường chuyển động dk. Trường phân đoạn cường độ sk gồm nhiều vùng, mỗi vùng có sự đồng nhất về cường độ nghĩa là sự biến thiên cường độ tương đối nhỏ. Để xác định các đối tượng chuyển động, các vùng này phải được tách ra thành các vùng khác nhau, trong đó mỗi vùng con đồng nhất về chuyển động. Nghĩa là trong một vùng nếu có nhiều nhóm điểm ảnh với chuyển động khác nhau thì cần phải được tách ra thành các vùng mới. Hơn nữa, nếu 2 vùng có tương đồng về cường độ, đến một thời điểm nào đó có cùng chuyển động thì cần phải được hợp nhất thành một vùng. Điều này có nghĩa là trường vector chuyển động là tác nhân khiến các vùng trong trường phân đoạn cường độ hợp nhất và tách ra thành vùng nhất quán về không gian – thời gian. Mối quan hệ độc lập có điều kiện hàm ý trong mạng Bayes cho phép ta biểu diễn phân phối kết hợp ngắn gọn hơn. Dùng luật dẫn xuất[25], mật độ xác suất kết hợp có thể được phân tích như sau sk zk gk dk gk-1,gk+1 20 (3.4) Cực đại xác suất hậu nghiệm (MAP) ước lượng 3 trường là (3.5) 3.2.3 Sự ràng buộc không gian và thời gian Mật độ xác suất có điều kiện p(g k–1 , g k+1 | g k , d k ) cho thấy sự phù hợp của giá trị vector chuyển động với điều kiện biết trước là 3 khung hình liên tiếp. Giả định là xác suất được xác định bằng trường ngẫu nhiên của DFD[50]. Có thể tính DFD ngược và DFD thuận tại vị trí x như sau: (3.6.1) (3.6.2) Kí hiệu vector là e k (x). Với giả định nhiễu Gauss là nhiễu i. i. d. và e k (x) là phân phối chuẩn Gauss một biến có giá trị trung bình bằng 0. Hệ số tương quan của và là (3.7) Giả định rằng, các quan sát độc lập có điều kiện, mật độ xác suất có thể phân tích thành: 21 (3.8.1) Với (3.8.2) Với Σ e là ma trận hiệp phương sai với mỗi vị trí x, và hệ số tương quan ρ được tính theo công thức (3.7) Biểu thức p(g k | s k ) cho thấy mức độ phù hợp của phân đoạn cường độ với hoạt cảnh. Giả định rằng phân phối Gauss hiện diện tại mỗi vùng phân đoạn trong khung hình hiện hành và mật độ xác xuất có điều kiện với mỗi vùng phân đoạn, mật độ xác suất có điều kiện có thể được phân tích thành : (3.9.1) (3.9.2) s k (x) là nhãn chỉ số vùng của x là cường độ trung bình trong vùng có nhãn là sk. là phương sai của tại mỗi vùng Hàm pdf p(s k ) biểu diễn xác xuất tiền nghiệm của trường phân đoạn cường độ. Để khuyến khích sự hình thành các vùng liên tục, mật độ p(s k ) được mô hình bằng trường ngẫu nhiên Markov[15]. Nghĩa là, nếu N x là lân cận của điểm ảnh x, thì phân phối có điều kiện của biến đơn tại vị trí x chỉ phụ thuộc vào các biến trong vùng lân cận N x . Theo nguyên lí Hammersley-Clifford, hàm mật độ của phân phối Gibbs có dạng 22 (3.10) với C là một tập các nhóm c, V là hàm tiềm năng đặc trưng cho nhóm. Một nhóm là tập các điểm ảnh là lân cận của nhau, và hàm tiềm năng V chỉ phụ thuộc vào các điểm bên trong nhóm c. Ràng buộc không gian có thể áp dụng bằng hàm tiềm năng nhóm 2 điểm ảnh. (3.11) Với là hàm delta Kronecker và ||⋅|| kí hiệu khoảng cách Euclidean. Do đó, 2 điểm ảnh lân cận sẽ có thiên hướng thuộc về cùng một lớp hơn là thuộc 2 lớp khác nhau. Ràng buộc tăng lên khi khoảng cách giữa các điểm lân cận giảm. Biểu thức p(d k | z k ) là mật độ xác suất điều kiện của trường vector chuyển động khi biết trước trường phân đoạn video. Để đẩy mạnh liên kết không gian, ta mô hình bằng phân phối Gibbs với hàm tiềm năng sau đây. (3.12) Ràng buộc giữa 2 điểm của vector chuyển động chỉ áp dụng khi 2 điểm ảnh lân cận có cùng nhãn phân đoạn video. Nếu 2 điểm thuộc 2 vùng phân đoạn video khác nhau thì ràng buộc triệt tiêu. Nếu 2 điểm thuộc cùng một vùng phân đoạn và có vector chuyển động khác nhau thì hàm tiềm năng tăng khi khoảng cách 2 điểm giảm. Tức là hàm này sẽ đẩy mạnh việc tách vùng. Hàm này tách vùng càng mạnh 23 tại những điểm biên, là nơi tiếp giáp của 2 vùng có chuyển động khác nhau. Như vậy, tóm lại hàm đóng vai trò là lực đẩy tách một vùng ra thành nhiều vùng khác nhau khi những vùng này có các mô hình chuyển động khác nhau. Biểu thức cuối cùng p(z k | s k ) biểu diễn mật độ xác xuất hậu nghiệm của trường phân đoạn video với điều kiện biết trước trường phân đoạn cường độ. Cường độ được mô hình bằng phân phối Gibbs với các hàm tiềm năng sau (3.13) Biểu thức đầu tiên bên vế phải của biểu thức (3.13) liên quan đến liên kết không gian trong phân đoạn video, trong khi biểu thức thứ 2 nhằm làm cho 2 điểm ảnh lân cận có cùng một nhãn phân đoạn video khi chúng ở trong một vùng của trường phân đoạn cường độ. Khi 2 điểm có chung nhãn phân đoạn video (hay có nghĩa là 2 điểm nằm trong một vùng phân đoạn video) thì hàm mục tiêu bằng 0 có nghĩa là hàm mục tiêu không có tác động lên 2 điểm này. Khi 2 điểm không cùng thuộc một vùng phân đoạn video nhưng thuộc cùng một vùng phân đoạn cường độ, thì giá trị hàm mục tiêu sẽ tăng lên khi khoảng cách giữa 2 điểm càng nhỏ. Trong trường hợp như vậy, có tác dụng hợp nhất các vùng trong phân đoạn cường độ hay nói cách khác là lực tác động làm cho các vùng được hợp nhất. Hệ số α để điều chỉnh mức độ ràng buộc trên phân đoạn cường độ. Kết hợp các biểu thức pdf, ước lượng MAP: 24 các trọng số λ 1 , λ 2 , λ 3 , và λ 4 điều chỉnh sự tác động của từng biểu thức thành phần đến kết quả cuối cùng. 3.2.4 Chú giải mô hình mạng Bayes Trong mô hình này, phân đoạn video bị tác động bởi cả thông tin không gian và thông tin thời gian. Hướng của các liên kết trong mô hình mạng Bayes không có nghĩa là sự ảnh hưởng giữa tác nhân và kết quả mà chỉ là thể hiện xác suất có điều kiện. Hình 3.2: Mô hình mạng Bayes đơn giản cho bài toán phân đoạn video. Khung hình hiện hành có thể được xem là nguyên nhân của khung hình kế tiếp. Ngay cả trong chuỗi ảnh với thứ tự đảo ngược cũng có thể áp dụng quy trình này. zk dk gk-1 ,gk+1 sk gk 25 Do đó khung hình hiện hành có thể xem là nguyên nhân của khung hình trước đó (trong chuỗi có thứ tự ngược). Trong mô hình này, g k có thể xem là nguyên nhân của cả khunh hình trước đó và khung hình tiếp theo. Ước lượng trường vector chuyển động dựa trên sự sai biệt giữa khung hình hiện hành và 2 khung hình kề bên. So với hình (3.1), trong hình (3.2), g k+1 và g k–1 bị tách ra nhằm thể hiện rõ mối tường quan này. Từ cấu trúc của mạng Bayes hình 3.2, ta có (3.15) So sánh với (3.8), hệ số tương quan của và là 0 trong (3.15). Trong mạng Bayes ở hình 3.2 đã bỏ qua sự tương tác giữa DFD thuận và DFD ngược. Vì vậy, mô hình mạng Bayes trong hình 3.2 chỉ là trường hợp đặc biệt và đơn giản của mô hình 3.1 Trong (3.13), khi tham số α thành 0 thì ràng buộc từ phân đoạn cường độ không còn nữa. Phương pháp suy biến thành phương pháp dựa trên vector chuyển động. Trong khi đó, nếu α tiến về vô cực, đường biên trong trường phân đoạn video cũng chính là biên trong trường phân đoạn cường độ, và phương pháp này suy biến thành phương pháp dựa trên hợp nhất các vùng. Biểu thức 3.13 cho thấy rõ phương pháp này là sự tổng hợp giữa phương pháp dựa trên chuyển động và phương pháp dựa trên hợp nhất các vùng. 26 3.3 Ước lượng MAP 3.3.1 Ước lượng lặp Khi các trường giá trị đều chưa biết, cực tiểu trực tiếp (3.14) rất khó. Quá trình tính giá trị cực tiểu do Wang Yang[57] đề xuất qua 2 bước. Đây là một quá trình ước lượng lặp xoay vòng, giá trị trường d k và s k tính dựa trên trường phân đoạn z k . Khi có được giá trị ước lượng d k và s k , cập nhật trường z k . Và quá trình đó lặp lại. Hình 3.3: Mô hình ước lượng lặp. Bước 1: Cập nhật d k và s k khi biết trước ước lượng trong trường phân đoạn video z k . Từ cấu trúc mạng Bayes được đề xuất, ta có thể thấy là d k và s k độc lập có điều kiện khi cho trước trường phân đoạn video z k và 3 khung hình liên tiếp. Ước lượng kết hợp có thể phân tích thành (3.16) Dùng luật dẫn xuất, ước lượng MAP thành (3.17.1) (3.17.2) zk dk, sk Bước 2 Bước 1 27 Bước 2: cập nhật z k khi biết trước ước lượng của trường chuyển động d k và trường phân đoạn cường độ s k . (3.18) Hình 3.4 Lân cận 24 điểm ảnh. Phương pháp này sử dụng hệ 24 điểm lân cận nay còn gọi là hệ lân cận bậc 5 (hình 3.4) và hàm tiềm năng dựa trên nhóm 2 điểm ảnh. Dùng biểu thức trong (3.14) MAP Bayes ước lượng trong (3.17) và (3.18) có thể có được bằng cách cực tiểu hóa những hàm mục tiêu. (3.19.1) 28 (3.19.2) (3.19.3) Với N x là vùng lân cận của điểm ảnh tại x. 3.3.2 Tối ưu cục bộ Mô hình ICM dùng thuật giải tham lam để cực tiểu hóa và lặp lại quá trình này để đạt kết quả tối ưu. Với điều kiện cho trước dữ liệu quan sát và các nhãn ước lượng khác nhau, nhãn phân đoạn sau đó được cập nhật bằng cách tối ưu cục bộ hàm mục tiêu tại mỗi điểm. Nhằm tăng độ chính xác kết quả phân đoạn tại biên, áp dụng tối ưu cục bộ vào biên đối với trường phân đoạn cường độ. Xây dựng phép biến đổi khoảng cách[3] lên trường phân đoạn cường độ. Mỗi điểm ảnh x trong ảnh biến đổi khoảng cách có giá trị DTk(x) Là khoảng cách giữa điểm ảnh x và điểm biên gần nhất đễn. Một điểm x gọi là biên nếu có ít nhất một điểm y trong vùng lên cận sao cho nhãn phân đoạn cường độ s k (y) và s k (x) khác nhau. Biểu thức trong (3.19.3) thay bằng 29 (3.20.1) (3.20.2) Với Biểu thức θ(x) để đánh dấu trên điểm ảnh nằm sát biên trong trường phân đoạn cường độ, nếu 2 điểm ảnh cạnh nhau trong cùng một vùng phân đoạn cường độ và không có cùng nhãn phân đoạn video. Hàm U như trên không làm mất tính đối xứng của hàm của hàm tiềm năng 2 điểm ảnh trong MRF. Nhận thấy rằng biểu thức , nhằm xác định 2 điểm thuộc cùng một trường phân đoạn cường độ, đã bị mất trong biểu thức 3.20.2. Điều này có nghĩa là biểu thức 3.20.2 đánh dấu tất cả các điểm nằm gần biên thuộc còn biểu thức 3.20.1 chỉ đánh dấu các điểm biên thuộc về cùng 1 vùng phân đoạn cường độ. Tác giả nhận định rằng, biểu thức 3.20.2 hồi tụ nhanh hơn biểu thức 3.20.1. Như vậy, biểu thức chỉ cần đánh dấu các điểm gần biên thay vì đánh dấu các điểm nằm 2 bên biên. Do đó, ta có được hàm mục tiêu cục bộ được tối ưu liên tục tại mỗi điểm (3.22.1) (3.22.2) (3.22.3) 30 3.3.3 Ước lượng không lặp Nhận thấy rằng quá trình ước lượng lặp gặp một số hạn chế do trường phân đoạn cường độ sau khi tính có thể không được chính xác, sau đó lại tham gia vào quá trình tính trường phân đoạn cường độ và trường vector chuyển động. Điều này có thể gây ra sai số ngày càng lớn trong quá trình ước lượng và làm giảm tính hội tụ của thuật toán. Luận văn đề nghị quá trình ước lượng không lặp. Trong đó giá trị zk ước lượng không ảnh hưởng gì đến việc ước lượng trường dk và zk. Hình 3.5: Mô hình ước lượng không lặp. Bước 1: Ước lượng d k và s k khi không biết trước trường phân đoạn video z k . Từ cấu trúc mạng Bayes được đề xuất, ta có thể thấy là d k và s k độc lập có điều kiện khi cho 3 khung hình liên tiếp. Ước lượng kết hợp có thể phân tích thành (3.23) Dùng luật dẫn xuất, ước lượng MAP thành (3.24.1) zk dk, sk gk-1 gk gk+1 dk+1, sk+1 zk+1 gk+2 Bước 1 Bước 2 31 (3.24.2) Bước 2: cập nhật z k khi biết trước ước lượng của trường chuyển động d k và trường phân đoạn cường độ s k . (Tương tự phần 3.3.1) Biểu thức trong 3.22.1 được thay bằng . Áp dụng phân phối Gibbs và hàm tiềm năng trên 2 điểm lân cận để tính p( (3.25) Do đó các biểu thức tối ưu cục bộ tại (3.22.1), (3.22.2), (3.22.3) thành (3.26.1) (3.26.2) (3.26.3) So với biểu thức 3.22.2, vì vế thứ 2 của biểu thức là hằng số, tức là không biến thiên khi tính cực tiểu nên đã bị loại bỏ khỏi biểu thức 3.26.2. Biểu thức này được ghép vào biểu thức 3.26.3. 3.3.4 Thuật giải ước lượng MAP Thuật giải tính vector chuyển động tại khung hình gk Bước 1: Với mỗi điểm ảnh x=(i,j) và với mỗi vector chuyển động khảo sát 32 Với mtSz là kích thước vector chuyển động giới hạn. Bước 2: Gán vector chuyển động cho điểm x Bước 3: Tại mỗi điểm ảnh x xét các điểm y trong vùng lân cận Nx và các vector chuyển động khảo sát của y . Tính giá trị như công thức 3.26.1 Bước 4: Gán lại vector chuyển động cho điểm x Thuật giải tính nhãn phân đoạn cường độ tại khung hình gk Bước 1: Khởi tạo giá trị trung bình cho m mức phân đoạn, i=1..m. và gán nhãn phân đoạn cường độ khởi tạo cho mỗi điểm x MAXGRAY*(i+1/2)/m sk(x)=gk(x)*m/MAXGRAY Với MAXGRAY là mức xám tối đa. Bước 2: Tại mỗi điểm x, khảo sát các nhãn phân đoạn có thể có sk(x)=1..m , khảo sát các điểm y trong vùng lân cận Nx và tính giá trị theo công thức 3.16.2 Bước 3: Gán nhãn phân đoạn cường độ sk cho điểm x Tại mỗi điểm ảnh x xét các điểm y trong vùng lân cận Nx và các vector chuyển động khảo sát của y . Tính giá trị như công thức 3.26.1 Bước 4: Tính lại giá trị và lặp lại bước 2. (Lặp lại sau một số lần cho trước) Thuật giải tính gán nhãn phân đoạn video tại khung hình gk Bước 1: Tính biến đối khoảng cách DST tại mỗi điểm x trong khung hình gk Bước 2: Tại điểm x có vector chuyển động , giá trị biến đổi khoảng cách 33 DST(x) và nhãn phân đoạn video tại khung hình gk-1. Khảo sát tất cả các nhãn phân đoạn video có thể có zk(x)=0..m. Tính giá trị như công thức 3.26.3 Bước 3: Gán nhãn phân đoạn video cho điểm x 3.3.5 Khởi tạo và các tham số Để có được trường phân đoạn khởi tạo tác giả áp dụng ước lượng MAP như trong[50] và sử dụng phương pháp do Wang và Adelson[56] đề xuất. Trong luận văn này, tập trung vào quá trình phân đoạn video nên trường phân đoạn video khởi tạo xem như đã biết trước. Trường phân đoạn video khởi tạo có thể do người dùng gán nhãn bằng tay hoặc phân đoạn tự động. Để có được hệ số thích hợp, tác giả dùng phương pháp chọn lọc tham số đề xuất bởi Chang[6]. Bộ hệ số (λ 1 , λ 2 , λ 3 , và λ 4 ) được xác định bằng cách cân bằng sự tham gia của các biểu thức trong (3.14). Trong khuôn khổ luận văn, bộ hệ số (λ 1 , λ 2 , λ 3 , và λ 4 ) được lấy từ bài báo của tác giả có điều chỉnh để phù hợp với thuật toán cải tiến.