Luận văn Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp

,t) y x đường mức gốc đường mức gốc Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 9 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Hình 3 : Sự tiến triển của hai đường tròn 2. Các đặc tính hình học của đường cong có thể được dễ dàng xác định từ phương trình Level Set φ. Vectơ pháp tuyến φ φ ∇ ∇=n và độ cong của mỗi tập đồng mức là φ φκ ∇ ∇∇= . 3. Mô hình Level Set không thay đổi trong trường hợp nhiều chiều. 4. Dựa trên nghiệm mạnh của phương trình đạo hàm riêng Level Set để đảm bảo tính duy nhất, và sự hợp lệ của nghiệm yếu. 5. Nghiệm xấp xỉ của phương trình Level Set có được nhờ mô hình tính toán dựa trên luật bảo toàn hyperbolic. Nghiệm xấp xỉ của phương trình Level Set Như đã đề cập ở trên, ta cần một nghiệm xấp xỉ cho phương trình Level Set để chuyển bài toán từ liên tục sang rời rạc, và một trong những nghiệm đơn giản nhất là: [15] ( ) ( ) ( ) ( )( ) 2/122221 0,min0,maxmin0,max φφφφφφ yijyijxijxijnijnij DDDDt +−+−+ ++Δ−= (1.2.2) Trong đó F = 1 Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 10 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái ( ) ( )xD jijixij Δ−= ++ /,,1 φφφ , ( ) ( )xD jijixij Δ−= −− /,1, φφφ ( ) ( )yD jijiyij Δ−= ++ /,1, φφφ , ( ) ( )yD jijiyij Δ−= −− /1,, φφφ Kỹ thuật Narrow Band Phương pháp đưa trên phụ thuộc vào việc tính toán sự tiến triển của tất cả các đường mức, chứ không chỉ riêng đường mức gốc (zero level set) tương xứng. Điều này đòi hỏi một sự tính toán phức tạp, và càng phức tạp hơn khi phương pháp Level Set chuyển bài toán hơn một chiều so với bài toán gốc (chiều thời gian). Để cải tiến phương pháp, ta cần có một sự thay đổi trong kỹ thuật duyệt, tức là chỉ tính toán trong lân cận của đường mức gốc. Kỹ thuật này được gọi là phương pháp dải hẹp (Narrow Band). Độ phức tạp tính toán của kỹ thuật này trong không gian 3 chiều cho N3 điểm trên lưới giảm từ O(N3) xuống còn O(kN2), với k là số lượng ô trong Narrow Band. Dẫn đến chi phí tính toán được rút gọn đáng kể. Ý tưởng cơ bản của phương pháp này là đánh dấu các điểm trên lưới với một trong các nhãn alive3 , land mines4 hoặc far away5, phụ thuộc vào chúng nằm trong, nằm trên, hoặc nằm ngoài band. Ở mỗi bước tiến triển, một điểm land mines sẽ trở thành alive, và band được cập nhật trở lại với những lân cận của điểm land mines vừa tìm. Hình 4 Kỹ thuật đánh dấu điểm trong phương pháp Narrow Band Kỹ thuật Narrow Band là tiền đề của một thuật toán hiệu quả hơn, đó là thuật lan truyền nhanh (Fast Marching Level Set) sẽ được trình bày trong phần kế. 3 alive : biểu diễn những điểm đá thuộc về đường cong 4 land mines hay trial : biểu diễn những điểm sẽ được chọn gần nhất đề ghép vào đường cong 5 far away : biểu diễn những điểm chưa được xét để ghép vào đường cong, hay đường cong sẽ phải cần một khoảng thời gian khá lớn mới đến được các điểm này. alive land mines far away Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 11 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Phương pháp Fast Marching Phương trình Eikonal Bây giờ, chúng ta tiếp tục tìm hiểu phương pháp Fast Marching Level Set [3], một lời giải hiệu quả cho bài toán đường cong chuyển động trong trường hợp vận tốc F không đổi dấu. Cũng xét bài toán như trên nhưng đường cong chuyển động với vận tốc ),(0),( yxyxFF ∀>= (hoặc ),(0),( yxyxF ∀< ). Với vận tốc luôn dương đường cong sẽ luôn “phình ra” như trong ví dụ bơm quả bóng, và với vận tốc luôn âm đường cong sẽ luôn “co lại” như trong ví dụ viên nước đá bỏ vào chậu nước nóng. Phương trình Level Set : ( ) 0,, =∇+ φφ zyxFt (1.3.1a) Giới hạn bài toán trong trường hợp 2 chiều, và ta biểu diễn sự tiến triển của đường cong trên lưới điểm N*N. Gọi T(x, y) là thời điểm mà đường cong đi qua điểm (x, y). Ta có thể xác định được hàm T(x, y) do tính chất đường cong “phình ra” hoặc “co lại” nên nó luôn đi qua mỗi điểm trên lưới điểm chỉ một lần duy nhất. Từ công thức : “đường đi = vận tốc * thời gian”. Khi xét bài toán một chiều ta có dx dTF=1 (1.3.1b) Hình 5: quãng đường = vận tốc * thời gian Còn trong trường hợp nhiều chiều, ∇T vuông góc với đường mức thời điểm T, và phương trình (1.3.1b) trở thành 1=∇ FT (1.3.1c) dT dx T(x) Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 12 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Phương trình (1.3.1c) là một dạng của phương trình Eikonal (1). Hình 6: Biểu diễn mặt nón T Một vài tính chất của phương pháp Fast Marching - Chuyển bài toán từ mô hình động sang mô hình tĩnh, đường cong được cập nhật theo chiều tăng từ giá trị nhỏ nhất đến giá trị lớn nhất của T. - Tương tự phương pháp Level Set : không thay đổi tính chất trong trường hợp nhiều chiều, có thể thu được nghiệm xấp xỉ bằng cách “rời rạc hóa” và giải nghiệm yếu cho phương trình Eikonal. Nghiệm xấp xỉ của phương trình Eikonal Ta xét bài toán hai chiều giới hạn trong ô [0, 1] x [0, 1] và tưởng tượng đường cong ban đầu nằm trên trục y = 0, và vận tốc F làm đối tượng chuyển động trên trục x. Sử dụng phương pháp xấp xỉ gradient, ta tìm một nghiệm trong ô đơn vị của phương trình [9]. [ ] 22222 1)0,min()0,max()0,min()0,max( FTDTDTDTD yijyijxijxij =+++ +−+− hoặc có thể viết gọn hơn: ( ) ( )[ ] 222 10,min(),0,max(max)0,min(),0,max(max FTDTDTDTD yijyijxijxij =−+− +−+− (1.3 .2) (1) phương trình Eikonal: ∑ = =⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ∂ ∂n i ix u 1 2 1 Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 13 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái với jj ijjiy ij jj jiijy ij ii jijix ij ii jiijx ij yy TT TD yy TT TD xx TT TD xx TT TD − −=− −=− −=− −= + ++ − −− + ++ − −− 1 1, 1 1, 1 ,,1 1 ,1 ;;; Thuật toán Fast Marching Level Set (FMLS) Điểm mấu chốt để xây dựng thuật toán FMLS là ta sẽ đưa bài toán lan truyền về một chiều theo T, tăng dần từ giá trị thấp nhất đến giá trị cao nhất. Ý tưởng chính ở đây là ta sẽ đánh dấu tất cả các điểm trong lưới tương tự phương pháp Narrow Band. Ở mỗi bước, ta tìm một vị trí trong các lân cận của đường cong tại bước đó, có giá trị thời điểm đường cong đi qua T(x,y) là nhỏ nhất để ghép vào đường cong mới. Hay nói cách khác, ta sẽ chọn nơi mà đường cong đến sớm nhất để tạo thành đường cong mới. Vì lý do này thuật toán Fast Marching còn có một tên gọi khác là “Dijkstra like Marching” (tựa Dijkstra6). Thuật toán Fast Marching được mô tả như sau: 1. Khởi tạo (a) Đánh dấu nhãn alive và đặt thời gian tiếp cận Tij = 0 cho tất cả các điểm thuộc về đối tượng, và đưa vào tập hợp A. (b) Đánh dấu nhãn trial và đặt thời gian tiếp cận Tij = ijF 1 cho tất cả các điểm lân cận A, và đưa vào tập hợp Narrow Band. (c) Đánh dấu nhãn far away và đặt thời gian tiếp cận Tij = ∞ cho tất cả các điểm còn lại và đưa vào tập hợp Far Away. 2. Lan truyền (a) Bắt đầu bước lặp: Đặt minTrial = (imin, jmin) là điểm trong Narrow Band có thời gian tiếp cận nhỏ nhất, nếu không tồn tại thì kết thúc thuật toán. (b) Thêm điểm (imin, jmin) vào A, và xóa nó trong Narrow Band (c) Kiểm tra 4 lân cận của minTrial: (imin – 1, jmin), (imin, jmin – 1), (imin + 1, jmin), (imin , jmin + 1) thuộc tập hợp Far Away hay 6 Dijkstra: là thuật toán tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh khác trong đồ thị có trọng số không âm. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 14 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Narrow Band. Nếu lân cận thuộc Far Away, xóa nó trong Far Away và thêm vào Narrow Band. (d) Cập nhật lại thời gian tiếp cận Tij cho các lân cận của minTrial từ phương trình (2.6) với nghiệm lớn nhất. (e) Quay lại bước lặp. Hình 7: Minh họa thuật toán Fast Marching. Ta xét ví dụ minh họa để hiểu rõ thuật toán Fast Marching. Giả sử đường cong ban đầu là đường tròn điểm màu đen trong hình a). Bước khởi tạo, điểm này được gán nhãn alive, và các lân cận A,B,C và D xung quanh nó được gán nhãn trial. Bước lặp, ta chọn điểm mang nhãn trial có giá trị thời điểm tiếp cận T(x,y) nhỏ nhất, giả sử ta chọn được điểm A. Cập nhật điểm A vào đường cong (đánh dấu alive), cập nhật các lân cận của nó vào Narrow Band và tiếp tục bước lặp (hình c). Giả sử điểm trial có giá trị T nhỏ nhất trong 5 điểm trial là D. Ta đánh dấu D nhãn alive, đường cong bây giờ được mở rộng thành 3 điểm, và Narrow Band cũng tăng kích thước lên thành 6 điểm (hình d) Và bước lặp được tiếp tục khi không còn điểm trial nào nữa. a) b) c) d) e) f) Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 15 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Đến đây ta sẽ nghĩ ngay đến câu hỏi : tại sao thuật toán trên hoạt động và đem lại kết quả ? Và câu trả lời là: đường cong luôn luôn tiến ra tại vị trí nhỏ nhất trong Narrow Band, những điểm khác trong Narrow Band và trong Far Away có thời gian tiếp cận nhỏ hơn không gây ảnh hưởng gì đến điểm này. Bước cập nhật thời gian tiếp cận cho các điểm lân cận sẽ tạo một thời gian mới luôn lớn hơn thời gian tiếp cận của các điểm alive, bởi vì ta đã chọn thời gian cập nhật là nghiệm lớn của phương trình Eikonal. Do đó ta có thể lan truyền đường cong rộng dần ra, chọn điểm trial có thời gian tiếp cận nhỏ nhất và điều chỉnh lại lân cận của nó, cứ tiếp tục như vậy mà không cần phải quay lại các điểm đã xét trước. Phương pháp Fast Marching cũng tương tự nguyên lý Huygens trong vật lý, mỗi điểm alive và điểm minTrial xem như một nguồn sóng và sóng sẽ lan truyền sang các điểm lân cận và các điểm này trở thành nguồn sóng mới. Chi tiết các bước trong thuật toán FMLS Xác định minTrial Ở bước 2a) của thuật toán ta cần phải xác định vị trí có thời gian tiếp cận nhỏ nhất trong Narrow Band. Để tăng hiệu quả hơn cho việc tìm kiếm, ta tổ chức Narrow Band theo cấu trúc Heap(1)gồm 3 chức năng: thêm, xóa phần tử nhỏ nhất, và cập nhật giá trị. Chức năng xóa phần tử được thực hiện trong thời gian tính toán hằng O(1), còn thêm và cập nhật được thực hiện với độ phức tạp O(logN) với N là số phần tử trong Heap. Như vậy bước xác định giá trị nhỏ nhất trong Narrow Band từ độ phức tạp tìm kiếm thông thường O(N), ta đã giảm xuống còn O(logN). Cập nhật thời gian tiếp cận Ở đây, chúng ta chứng tỏ rằng thuật toán FMLS đưa ra một kết quả mà tất cả các điểm đều thỏa phương trình Eikonal rời rạc: (1) Heap: (còn gọi Priority Queue) là một hằng đợi có giá trị của phần tử i luôn nhỏ hơn tại giá trị của phần tử 2*i và 2*i+1, và do đó phần tử 0 là phần tử có giá trị nhỏ nhất trong hằng đợi. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 16 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái ( ) ( )( ) ( ) ( )( )[ ] 222 0,min,0,maxmax0,min,0,maxmax ijyijyijxijxij fTDTDTDTD =−+− +−+− với 22 /1 ijij Ff = Do tính chất lan truyền theo chiều tăng dần của thời điểm đường cong tiếp cận T(x, y), chúng ta chỉ cần chỉ ra rằng bất một vị trí trial nào được chuyển thành alive thì sẽ không có điểm nào trong các lân cận của nó có thời gian tiếp cận được tính lại nhỏ hơn bất kỳ thời gian tiếp cận nào của các điểm alive. Chúng ta sẽ kiểm định kết quả này trong không gian hai chiều, không gian ba chiều được chứng minh tương tự. Hình 8: Cập nhật thời gian tiếp cận Xét lưới điểm trên. Chúng ta cần ước tính giá trị mới T tại điểm tâm của lưới để thay thế vào giá trị ?, dựa vào giá trị của các điểm lân cận. Không mất tính tổng quát, ta giả sử rằng giá trị A tại điểm trái của lưới là nhỏ nhất trong tất cả các giá trị trial, và cần chỉ ra rằng khi ta tính lại giá trị của điểm tâm của lưới(Trecomputed-from-A), thì nó không thể nhỏ hơn A. Có tất cả bốn trường hợp (1) không có vị trí nào trong các lân cận B,C hoặc D là alive (2) một trong các lân cận này là alive (3) hai trong các lân cận này là alive (4) tất cả các lân cận naỳ là alive. (1) A, B, C, và D là trial, A nhỏ nhất A ? B C D Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 17 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Trong trường hợp này, tất cả các lân cận quanh tâm đều hoặc là trial hoặc là far away. Khi A là giá trị nhỏ nhất, chúng ta chuyển giá trị đó thành alive và tính lại giá trị tâm. Ta chứng minh A ≤ Trecomputed-from-A ≤ A+f. 1. Trường hợp A+f ≤ min(B, D). ⇒ Trecomputed-from-A = (A+f) (thỏa) 2. Trường hợp A+f > min(B, D) = B. (không mất tính tổng quát, giả sử B ≤ D. Phương trình trở thành : (Trecomputed-from-A – A)2 + ( Trecomputed-from-A – B)2=f2 ABfdoTTf AB −>>−−=Δ 0)(2 22 Chọn nghiệm lớn: 2 )(2 22 ABBA Afromrecoputed TTfTT T −−++=−− B ABABBA T TTTTTT >−−−++> 2 )()(2 22 Như vậy, ta đã chứng minh được rằng A ≤ Trecomputed-from-A ≤ A+f. (2) B là “alive”, A, C và D là “trial”, A là giá trị trial nhỏ nhất Trong trường hợp này, A vừa được cập nhật bởi vì nó là giá trị trial nhỏ nhất. Chúng ta sẽ chứng minh rằng khi chúng ta tính lại Trecomputed-from-A , giá trị mới của nó vẫn phải lớn hơn A. Trong vài bước trước, khi B được chuyển từ trial sang alive, các giá trị A, C, D đều là trial, do đó phải lớn hơn. Điều này có nghĩa là khi B được chuyển từ trial sang alive thì B ≤ Trecomputed-from-B ≤ B+f (theo trường hợp (1)), hơn nữa khi giá trị tâm không được chọn là giá trị trial nhỏ nhất, chúng ta phải có A ≤ B+f. Từ trên, ta có thể có được B ≤ A ≤ Trecomputed-from-A ≤ B + f (3) C là “alive”, A, C và D là “trial”. A là giá trị trial nhỏ nhất. Trong trường hợp này, do ta đang xét bài toán theo chiều tăng từ trái sang nên A không gây ảnh hưởng đến điểm giữa. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 18 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Vậy ta đã chứng minh xong, khi cập nhật một giá trị T mới thì nó sẽ không nhỏ hơn tất cả các giá trị alive và điểm minTrial, điều này đảm bảo sự lan truyền sẽ tăng dần theo chiều T(x,y), thời gian đường cong tiếp cận đến điểm (x,y). Thuật toán Multi - Class Fast Marching Bây giờ ta xét đến một biến thể của thuật toán Fast Marching, thuật toán Multi-Class Fast Marching [4, 5, 6, 10] được Sifakis và Tziritas đưa ra năm 2001, nhằm thực hiện phương pháp lan truyền Fast Marching trên nhiều đường cong cùng lúc. Ý tưởng cải tiến ở đây là mỗi điểm thay vì nếu được gán nhãn trial thì nó mang theo một danh sách các đường cong mà nó tiếp cận đến, gọi là TrialList, và thời gian tiếp cận bây giờ là thời gian tiếp cận của đường cong đến nó sớm nhất. Thuật toán được mô tả như sau: Khởi tạo thời gian tiếp cận T(x, y) Khởi tạo danh sách các nhãn Trial List (x, y, ci) ∈ {alive, trial, far away} Trong khi (Narrow Band chưa rỗng) { Chọn (imin, jmin) là điểm có giá trị Tmin trong Narrow Band Đánh dấu nhãn (imin, jmin) là alive cho đường cong đến nó sớm nhất. Thêm các lân cận của (imin, jmin) vào Narrow Band Cập nhật thời gian tiếp cận cho các lân cận (imin, jmin) } Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 19 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Một minh họa cho thuật toán Multi-Class Fast Marching. Từ các đường cong ban đầu, chuyển động với vận tốc hằng F = 1, thuật toán chạy ở các buớc 5%, 10%, 30%, 60% và 100%. Kết quả thu được là lược đồ Voronoi. Hình 9: Thuật toán Multi-Class Fast Marching Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 20 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái PHÁT HIỆN SỰ THAY ĐỔI CỦA đối TượNG TRONG DÃY ẢNH LIÊN TIẾP “Phát hiện và định vị đối tượng thay đổi trong dãy ảnh liên tiếp” là một trong những vấn đề chủ yếu trong phân tích chuyển động video, cũng như những ứng dụng theo dõi đối tượng di chuyển, ước lượng chuyển động hỗ trợ các hệ thống an ninh, quốc phòng. Vấn đề này cũng được sử dụng nhiều trong việc nén video, nhất là theo chuẩn MPEG, hoặc trong các kỹ thuật “blue-screening”. Trong trường hợp ảnh được chụp từ một camera tĩnh, thì cơ sở chung để phát hiện chuyển động là phân tích sự thay đổi màu sắc giữa hai frame ảnh liên tiếp và từ đó sẽ đưa ra kết luận về đối tượng đang thay đổi giữa hai frame ảnh này. Phương pháp đơn giản nhất là kỹ thuật trừ ảnh (hay xor ảnh). Nếu sự khác biệt giữa hai frame ảnh lớn hơn một ngưỡng nào đó thì ta sẽ báo động có sự thay đổi giữa chúng. Phương pháp này đặc biệt tối ưu về tốc độ nhưng cho kết quả không tốt trong trường hợp ảnh bị nhiễu và không xác định được đối tượng chuyển động một cách chính xác. Các kỹ thuật phức tạp hơn là sử dụng bộ lọc Kalman, sử dụng mô hình Markov ẩn cũng có được kết quả khả quan nhưng tốc độ không được cao lắm. Trường hợp ảnh được chụp từ một camera di chuyển, vấn đề sẽ trở nên khó hơn. Ta cần phải xét đến vector chuyển động cũng như hệ số phóng to thu nhỏ của máy ảnh. Trong phần này chúng em xin trình bày một trong những phương pháp phát hiện đối tượng thay đổi dựa trên thuật toán Fast Marching Level Set và Region Growing, giải quyết tương đối hiệu quả vấn đề trên trong trường hợp camera tĩnh. Tóm tắt phương pháp sử dụng FM LS và SRG Ban đầu từ các kiểm định thống kê và nguyên lý hợp lý cực đại ta sẽ đánh dấu nhãn những pixel chắc chắn thuộc về đối tượng (đánh dấu nhãn động), và những pixel chắc chắn thuộc về nền (đánh dấu nhãn tĩnh). Bước tiếp theo, thuật Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 21 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái toán Fast Marching Level Set được sử dụng để lan truyền hai tập hợp pixel đã đánh dấu nhãn ở trên sang những pixel chưa được gán nhãn, và hình thành đối tượng đã thay đổi giữa hai ảnh. Do bước này chỉ quan trọng hóa về mặt tốc độ thuật toán và chỉ sử dụng độ chênh lệch cường độ xám nên kết quả sẽ không vừa vặn hoàn toàn đối tượng. Kết quả chính xác sẽ có được ở bước kế tiếp. Từ đường biên của đối tượng có từ bước trên, ta sử dụng thuật toán Fast Marching hai lần đề tiến nó theo hai hướng đối nghịch: vào trong và ra ngoài, tạo thành hai đường cong nằm hẳn bên trong và bên ngoài đối tượng. Cuối cùng, áp dụng thuật toán tăng vùng (SRG) với vùng được tạo từ hai đường cong trên, ta sẽ được kết quả như ý. Phát hiện đối tượng chuyển động Thiết lập mô hình thống kê Đặt d(x,y) = I(x,y,t+1) – I(x,y,t) biểu diễn độ chênh lệch cường độ xám tại pixel (x,y), với I(x,y,t) và I(x,y,t+1) lần lượt là cường độ xám của pixel (x,y) trong frame tại hai thời điểm t và t+1. Đặt D = {d(x,y), (x,y) ∈ [0, chiều dài ảnh] x [0, chiều rộng ảnh]}. Mỗi pixel được đánh dấu bởi một trong hai nhãn: động (mobile) hoặc tĩnh (static). Với Θ(x,y) là nhãn của pixel (x,y), theo quy ước thống kê ta viết: H0 : Θ(x,y) = static H1 : Θ(x,y) = mobile Đặt pD|static(d|static) và pD|mobile(d|mobile) lần lượt là hàm mật độ xác suất của độ chênh lệch cường độ xám dưới hai giả thuyết H0 và H1. Các hàm mật độ xác suất này độc lập với vị trí của pixel, và luôn tuân theo luật phân phối Laplace hoặc Gauss. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 22 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Ta sử dụng hàm phân phối Laplace(1) với kỳ vọng bằng 0 để mô tả sự tương quan thống kê của các pixel đối với hai giả thuyết trên. Để đơn giản ta sử dụng ký hiệu 0 và 1 cho nhãn tĩnh và động. Do vậy, hàm mật độ xác suất của độ chênh lệch cường độ xám dưới hai giả thiết H0, H1 : ),( 2 )),(|),(( yxdlellyxyxdp λ−λ==Θ với l∈ {0,1} (2.2.1a) và hàm mật độ xác suất tổng hợp của độ chênh lệch cường độ xám : )|()|()( || mobiledpPstacticdpPdp mobileDmobilestaticDstaticD ⋅+⋅= (2.2.1b) Trong hai hàm phân phối trên, {Pl , λl ; l∈{static, mobile}} là các tham số chưa biết. Ta sẽ sử dụng nguyên lý hợp lý cực đại và giải thuật kết nhóm Bayes để ước lượng chúng (phụ lục). Gán nhãn khởi tạo ban đầu Các nhãn khởi tạo ban đầu có được từ các kiểm định thống kê với độ tin cậy cao nhất. Kiểm định đầu tiên sẽ xác định các pixel động và sau đó các kiểm định tiếp theo sẽ xác định các pixel tĩnh. Thuật toán Fast Marching sẽ lan truyền tiếp tục với các nhãn đã đánh dấu trước. Nên để hạn chế sai số cho sự lan truyền này, các nhãn động được kiểm định trên từng pixel và các nhãn tĩnh được kiểm định trên các khối pixel. Điều này giúp các pixel động và tĩnh không thể gần nhau, tạo điều kiện tốt cho việc lan truyền sau này. Đánh dấu nhãn động Kiểm định đầu tiên xác định các nhãn động với độ tin cậy cao nhất. Xác suất báo động lỗi được đặt rất nhỏ, gọi là PFA (trong phần cài đặt, PF (1) Luật phân phối Laplace: là phân phối của đại lượng ngẫu nhiên X có hàm mật độ phân phối: θλλθλ −−= xexf 2 ),,( với λ > 0, θ là tham số cho trước Các đặc trưng số: Kỳ vọng EX = θ, Phương sai DX = 2 1 λ Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 23 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái được chọn bằng 1E-7). Do sử dụng phân phối Laplace, nên ngưỡng chênh lệch mức xám cho nhãn động có được chọn như sau: FP T 1ln1 0 1 λ= (2.2.2.1) ⇒ Tập mẫu các nhãn động: { }1),(:),( TyxdyxMobile >= Đánh dấu nhãn tĩnh Các kiểm định tiếp theo được sử dụng với mục đích tìm ra các vị trí tĩnh với độ tin cậy cao nhất. Xét một dãy 6 ô kích thước (2w+1)2, w = 2,...,7, và các ngưỡng tương ứng cho nhãn tĩnh được thiết lập theo λ1. Đặt Bw là tập hợp các pixel được đánh dấu nhãn tĩnh khi kiểm định các ô có chỉ số w. .7,...2, ),(:),( 1 = ⎭⎬ ⎫ ⎩⎨ ⎧ <++= ∑ ∑ −= −= wlykxdyxB w wk w wl l w λ γ (2.2.2.2) Với γw là các giá trị thu được từ thực nghiệm. w 2 3 4 5 6 7 γw 0.4 1.6 3.5 7.0 12.0 20.0 ⇒Tập mẫu các pixel tĩnh : Υ6 2 wB = = w Static Ví dụ: Kết quả của quá trình đánh dấu nhãn cho hai frame ảnh liên tiếp. Trong hai bức ảnh này màu xanh biểu thị các điểm đánh dấu tĩnh, màu vàng biểu thị các điểm đánh dấu động và màu xám là các điểm chưa xác định được nhãn. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 24 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Hình 10: Đánh dấu các mẫu ban đầu Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 25 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Lan truyền nhãn Thuật toán Fast Marching Level Set đđược áp dụng với hai tập pixel mẫu: động và tĩnh tìm được ở phần trên. Đường biên của mỗi tập pixel sẽ được mở rộng với một vận tốc riêng tùy thuộc mỗi loại nhãn và độ chênh lệch cường độ xám. Vận tốc lan truyền đđược thiết lập dựa trên nguyên lý xác suất Bayes Với vị trí s có nhãn l và độ chênh lệch cường độ xám d, vận tốc lan truyền sẽ là: vl(s) = Pr{l(s), d(s)} Có thể viết lại như sau: ∑∑ ≠ + == lk k l slsdp sksdpsksdp slsdpsv {l(s)}Pr)(|)(( {k(s)}Pr))(|)((1 1 {k(s)}Pr))(|)(( {l(s)}Pr))(|)(()( (2.2.3) Vì thế tốc độ lan truyền dựa trên các tỉ lệ hợp lý (likelihood) và các xác suất tiên nghiệm (priori). Tỉ lệ hợp lý có thể được đánh giá dựa vào tính chất dữ liệu, còn xác suất tiên nghiệm có thể ước lượng trên toàn ảnh hoặc đđơn giản hơn cho tất cả bằng nhau (P0 = P1 = ½). Trong trường hợp quyết định lựa chọn giữa nhãn động và nhãn tĩnh theo phân phối Laplace, tỉ lệ hợp lý là hàm exp của độ chênh lệch cường độ xám d(x,y). Trong cách tổ chức theo pixel, xử lí các quyết định này rất phức tạp. Hơn nữa, vật thể chuyển động không theo khuôn mẫu nào cả, các thành phần khác nhau của nó di chuyển cũng khác nhau. Trong các vùng có cùng cường độ xám, sự khác nhau của frame ảnh rất nhỏ khi đối tượng chuyển động. Vì vậy, tập hợp đối tượng động của frame trước nên được sử dụng trong việc xác định xác suất tiên nghiệm trong quá trình lan truyền. Theo phương trình (2.2.1a) và (2.2.1b) hai tốc độ lan truyền có thể đđược viết lại như sau Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 26 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái ),()( 00 11 0 10 ),( ),(1 1),( yxde yxQ yxQ yxv λλ λ λ −+ = ),()( 11 00 1 10 ),( ),( 1 1),( yxde yxQ yxQ yxv λλ λ λ −−+ = với tham số λ0 và λ1 đã đđược ước lượng trước đđó. Từ các phân tích thống kê của sự phân phối dữ liệu hỗn hợp, chúng ta có sự ước lượng xác suất tiên nghiệm cho hai loại nhãn. Đây chỉ là sự ước lượng chứ không phải là công thức chính xác của xác suất tiên nghiệm. Tuy nhiên, các pixel đã gán nhãn ban đầu không cần thiết tuân theo phân phối xác suất như vậy, bởi vì sự nhận dạng ban đầu dựa vào lượng chuyển động có thể là biến đổi không gian hoặc thời gian. Chúng ta định nghĩa tham số β đđể đo sự khác nhau của hai phân phối xác suất như sau : )ˆˆ(4 01 10 10 ˆ ˆ PP PP PP + ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛=β với 1ˆˆˆ 10 =++ uPPP . uPˆ là phần trăm các pixel chưa được gán nhãn. Trong trường hợp đó β sẽ là tỉ lệ của xác suất tiên nghiệm. Thêm vào đó, v1(x,y) trong frame trước cũng được đưa vào cho việc tính toán. β ζηηαθ )),(),(),(( ),( ),( 01 1 0 1 yxyxyxe yxQ yxQ −+−= )1),(2ln(),( −= yxyx δα , với δ(x,y) là khoảng cách từ điểm (x,y) đến vùng động trong frame trước, và n1(x,y), n2(x,y) là số pixel lân cận (x,y) đã được gán nhãn động và tĩnh. Cuối cùng, tốc đđộ loang chính xác của nhãn tĩnh là: ζηηθλλ λ λβ )),(),(()|,()|( 0 1 0 100101 1),( yxyxyxde yxv −−+−+ = Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 27 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái và của nhãn động là: ζηηαθλλ λ λ β )),(),(),(()|,()|( 1 0 1 10110 11 1),( yxyxyxyxde yxv +−−+−−+ = Các tham số còn lạiđđược thiết lập theo thực nghiệm: ζ = 0.1T1, θ0 = 4ζ, θ1 = 5ζ+4 Chúng ta sử dụng thuật toán Fast Marching đđể mở rộng các đường biên sang những vùng chưa được gán nhãn. Để cóđđược đđường biên chính xác, và có được một tiêu chuẩn dừng tốt ta sử dụng cách tiếp cận Level Set kiềm chế các điểm biên. Cách tiếp cận này không chú trọng đến sự mềm mại của đường biên, mà chỉ chú trọng đến hiệu quả tính toán. Vì vậy tốc độ lan truyền phụ thuộc vào những đặc tính riêng của điểm ảnh, chứ không phụ thuộc vào độ cong của đường biên. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 28 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Hình 11: Kết quả quá trình lan truyền nhãn bởi thuật toán Fast Marching Định vị đối tượng Khởi tạo Giai đoạn phát hiện thay đổi được sử dụng để khởi tạo cho quá trình xác định biên đối tượng. Chúng ta có nhận xét rằng vùng thay đổi “lý tưởng” chính là vùng thuộc về đối tượng tại hai thời điểm liên tiếp. Chúng ta đặt vùng này là: )}1,,(),,({)1,( +∪=+ tjiOtjiOttC trong đó O(i,j,t) là tập các pixel thuộc về đối tượng tại thời điểm t. Tương tự ta có : )},,()1,,({),1( tjiOtjiOttC ∪−=− Nên )})1,,({)}1,,(({)},,({)1,(),1( +∩−∪=+∩− tjiOtjiOtjiOttCttC Qua đó chúng ta thấy rằng phần giao của 2 vùng thay đổi liên tiếp sẽ là sự khởi tạo tốt hơn từng vùng trong quá trình định vị đối tượng. Tuy nhiên trong một số trường hợp thì Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 29 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái )})1,,({)}1,,(({)},,({ +∩−⊃ tjiOtjiOtjiO Nếu điều này xảy ra thì : )1,()1,()},,({ −∩+= ttCttCtjiO Như vậy chúng ta sẽ sử dụng phần giao này để khởi tạo cho quá trình xác định biên của đối tượng. Tạo vùng chứa biên Trong phần này ta sẽ tìm một vùng đủ lớn để chứa biên của đối tượng. Để đạt được yêu cầu này ta sẽ dùng đường biên ban đầu (có được từ phần trước) mở rộng về hai phía để có được đường biên trong nằm trên đối tượng và đường biên ngoài nằm trên nền. Trong mọi trường hợp, đường biên của đối tượng nằm giữa 2 đường biên này. Ta có nhận xét rằng khi tạo đường biên trong thì những điểm trên nền sẽ tiến nhanh, còn những điểm trên đối tượng sẽ tiến chậm hơn để có được kết quả chính xác. Đối với đường biên ngoài thì ngược lại. Chúng ta giả sử rằng cường độ ảnh trên nền được mô tả bằng phân phối Gauss với kì vọng là ⁄μ và phương sai là 2σ , đồng thời điều kiện này cũng thoả trong cục bộ. Khi đó hàm mật độ phân phối xác suất của thống kê này là 22 )( 2 1)( σ μ πσ −− = x exf Vận tốc để tạo hai đường biên được xác định dựa vào nguyên lý xác suất tiên nghiệm và được xác định dựa vào sự chênh lệch giữa giá trị ⁄μ và Ι 2 2)( σ μ−Ι trong đó Ι là giá trị trung bình của cường độ trong của sổ 3x3 với điểm đang xét là tâm. Giá trị của thống kê này càng nhỏ nghĩa là phù hợp với nền. Như vậy ta có được vận tốc mở rộng của hai đường biên là : - Đối với đường biên trong : 2 )(4 1 1 σ μ−− + = I b b ec v Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 30 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái - Đối với đường biên ngoài: bo vv −= 1 Trong đó hằng số Π Δ= 2σo b b P Pc . bP , oP lần lượt là xác suất của pixel nằm trên nền và trên đối tượng. Chúng ta cũng giả sử rằng cường độ các pixel trên đối tượng phân phối trong khoảng Δ (từ 0 đến 255). μ và σ là những giá trị đã được đề cập trong phần trên. Trong những trường hợp vùng nền không đồng nhất, vùng chứa biên đối tượng được xác định bằng việc thiết lập các vận tốc là hằng số. Khi cài đặt chương trình, hai vận tốc nhận giá trị bằng 0.5. Độ lớn của vùng “không chắc chắn“ - vùng chứa biên đối tượng - được xác định bằng việc đặt ngưỡng của thời gian tiếp cận trong thuật toán FMLS mà giá trị ngưỡng này phụ thuộc vào độ lớn và chuyển động của đối tượng. Sau giai đoạn này chúng ta có được ba vùng trong frame ảnh cần phân đoạn, cụ thể như sau: vùng thuộc về nền, vùng thuộc về đối tượng cần tìm biên, vùng chứa biên của đối tượng và ta gọi vùng này là vùng không chắc chắn . Hình 12: Kết quả khi tạo vùng chứa biên đối tượng Vùng chứa biên đối tượng được minh hoạ bằng màu thực của ảnh trong khi nền và đối tượng có màu xanh và đỏ. Lọc biên đối tượng Trong phần này chúng ta sẽ sử dụng thuật toán Seeded Region Growing (SRG) để xác định biên của đối tượng. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 31 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái SRG là một trong những phương pháp được sử dụng trong quá trình phân đoạn ảnh. Phương pháp này yêu cầu chúng ta phải cung cấp một hay một số vùng đã có nhãn ban đầu và các vùng này được coi như là tập “mầm” của giải thuật. Giải thuật phát triển các tập này cho tới khi tất cả các pixel của frame ảnh được xử lý hết. Thuật toán Seeded Region Growing ban đầu được giới thiệu bởi Rolf Adams và Leanne Bischof[7] vào năm 1994 dựa trên khái niệm này. Đầu tiên ta sẽ xác định những thành phần nối kết với vùng “không chắc chắn” thuộc về nền và đối tượng. Trên biên của hai vùng này chúng ta sẽ đặt những điểm đại diện mà những điểm này sẽ được sử dụng để tính vector màu trung bình cục bộ trong hệ màu CIE Lab. Sự khác biệt về tính chất màu của pixel ứng viên với vùng đã có nhãn dựa vào các vector màu này và khoảng cách Euclidean. Cụ thể ta đặt T là tập của những pixel không thuộc về các tập mầm nhưng có các lân cận của nó thuộc về một trong các tập này. Theo định nghĩa trên thì: ⎭⎬ ⎫ ⎩⎨ ⎧ ≠∉= Υ ΥΙn n ii AxNAxT 1 1 0)(| ta có N(x) là tập các lân cận của x. Chúng ta xét 8 lân cận của mỗi pixel x. Tại mỗi bước của giải thuật ta lấy 1 pixel từ tập T-pixel này chưa có nhãn- và đưa vào một trong những tập Ai mà N(x) có phần giao, gán nhãn nó như nhãn của tập này. Tuy nhiên thuật toán này lại phụ thuộc vào thứ tự của pixel được lấy ra bởi vì thứ tự các pixel được lấy ra khác nhau sẽ cho ta kết quả khác nhau. Vấn đề này được giải quyết bởi Andrew Mehnert and Paul Jackway [8] khi họ đưa ra cách giải quyết là chọn phần tử có độ chênh lệch về tính chất màu từ các tập mầm là nhỏ nhất. Sau đó chúng ta cập nhật lại tính chất màu của tập này đồng thời đưa các lận cận của nó vào tập T. Thuật toán kết thúc khi tất cả các pixel đã có nhãn. Để xác định độ chênh lệch về cường độ từ 1 pixel đến 1 tập hợp ta dùng công thức : |0)(:)(|)( ≠−= xNAimeanAixIx Ιδ Trong đó I(x) là cường độ của pixel x trong frame ảnh đang xét. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 32 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Nếu pixel ta đang xét có N(x) có phần giao hơn một tập hợp thì chúng ta phải quyết định tập nào để có được giá trị của )(xδ . Cách giải quyết tốt nhất là chọn tập thứ i thoả : )}(min{)( ix δδ = . Sau khi mỗi pixel được gán nhãn, vector màu tương ứng sẽ được cập nhật để có được giá trị mới phù hợp với vùng mà nó đại diện. Khi giải thuật kết thúc, mỗi pixel của frame ảnh được gán một trong hai nhãn: thuộc về nền hay thuộc về đối tượng. Khi thực hiện giải thuật SRG chúng ta cần một cấu trúc dữ liệu để lưu trữ các pixel trong quá trình xử lý và cấu trúc này được gọi là Sequentially Sorted List (SSL). Thuật toán: Bước 1: Đánh dấu nhãn cho tập hợp ban đầu theo từng nhóm của chúng. Bước 2: Tính vector màu của các tập hợp này trong một hệ màu nhất định. Bước 3: Tính giá trị (.,.)δ của tất cả các lân cận của tập ban đầu và đưa chúng vào trong SSL. Bước 4: Trong khi (SSL chưa rỗng) thì: Bước 4.1: chọn pixel đầu tiên Y trong SSL và gán nhãn cho nó như nhãn của tập hợp mà nó “giáp ranh”. Đồng thời cũng loại pixel này ra khỏi SSL. Bước 4.2: cập nhật vector màu của tập hợp mà pixel Y giáp ranh. Bước 4.3: kiểm tra các lân cận của Y để cập nhật SSL: Bước 4.3.1: nếu pixel chưa có mặt trong SSL thì tính giá trị (.,.)δ của các pixel này và insert chúng vào trong SSL. Bước 4.3.2: nếu pixel đã có mặt trong SSL thì cập nhật lại giá trị của (.,.)δ . Bước 5: Kết thúc. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 33 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Hình 13: Kết quả sau khi sử dụng thuật toán SRG Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 34 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Kết quả và hướng phát triển Thực hiện Mô hình thực hiện: Hình 14: Mô hình thực hiện Chương trình minh họa được cài đặt bằng ngôn ngữ Java dựa trên các lớp chính với các chức năng như sau: - VideoSegmentation.java: thực hiện toàn bộ thuật toán. - ChangDetect.java: thực hiện bước phát hiện các đối tượng. - Localization.java: thực hiện bước định vị đối tượng. - MLClassify.java: phân lớp Bayes và ước lượng Maximum Likelihood. Ảnh 2 Ảnh xám 1 Ảnh 1 Ảnh xám 2 xám hóa xám hóa Chênh lệch mức xám Đối tượng thay đổi Fast Marching Phân lớp ML Kết quả chính xác Seeded Region Growing Trích vùng chứa biên Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 35 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái - FastMarching.java: thuật toán Multi-Class Fast Marching. - CreateUncertaintyZone.java: tạo vùng chứa biên đối tượng sử dụng 2 lần thuật toán Fast Marching. - SeedRegionGrowing.java: phát hiện biên đối tượng sử dụng thuật toán tăng vùng. Kết quả thực nghiệm Chương trình được thực hiện trên dãy ảnh 320*240 24 bit màu, và có được những kết quả như sau: Cấu trúc file ảnh Số đối tượng chuyển động Mức độ chính xác Thời gian trung bình Thời gian cao nhất Hall Monitor JPG 2 98% 1.5 giây 2.0 giây Hướng phát triển Đề tài “Phát hiện và định vị đối tượng trong dãy ảnh liên tiếp bằng sử dụng thuật toán Fast Marching và Seed Region Growing” là một đề tài mở. Nếu có được cơ hội tiếp tục thực hiện, chúng em hy vọng sẽ mở rộng vấn đề sang dãy ảnh được chụp từ một camera di động hoặc cao hơn là một đoạn film bất kỳ. Đề tài được ứng dụng trong việc nén video theo dạng MPEG, hệ thống theo dõi từ xa, hoặc kết hợp với các phương pháp nhận dạng đề thành hệ thống phòng chống trộm Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 36 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái tài liệu tham khảo [1] R.Duda, P.Hart. Pattern Classification and Scence Analysis. New York: Willey- Interscience, 1973. [2] G.McLachlan, D. Peel và W. Whiten. Maximum likelihood clustering via normal mixture model. Signal Processing: Image Communication, 8:105-111, 1996. [3] J.Sethian. Level Set Methods and Fast Marching Methods. Cambridge University Press, 1999. [4] E.Sifakis, G.Tziritas. Fast marching to moving object location, in: Proceed-ings of the Second International Conference on Scale-Space Theories in Computer Vision, Corfou, Greece, 1999. [5] E.Sifakis, I.Grinias và G.Tziritas. Video segmentation using Fast Marching and Region Growing algorithms. EURASIP Journal on Applied Signal Processing, pages 379-388, April 2002. [6] E.Sifakis, G.Tziritas. Moving object localisation using a Fast Marching algorithms. Signal Processing: Image Communication, 16:963 – 976, [7] R.Adams, L.Bischof, Seeded region growing, IEEE Trans. on PAMI, Vol. 16, No. 6, June 1994, pp. 641 –647 [8] A.Mehnert, P.Jackway, An improved seeded region growing algorithm, Pattern Recognition Letters, Vol. 18, 1997, pp. 1065-1071 [9] E. Rouy, A. Tourin, A Viscosity Solutions Approach to Shape From Shad-ing, SIAM J.Num, Anal, 29, 3.pp.867-884, 1992. [10] E.Sifakis, C.Garcia, và G.Tziritas, Bayesian Level Set for Image Segment- ation. J.of Visual Communication and Image Representation, 13:44-64, March/June 2002 [11] Lương Mạnh Bá - Nguyễn Thanh Thuỷ: Nhập môn Xử Lý Aûnh Số - Nhà Xuất Bản Khoa Học và Kỹ Thuật 1999. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 37 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái [12] R.Gonzalez, E.Woods: Digital Image Processing, Addison Wesley Publish-ing Company, 1997 [13] J.Sethian. Fast MarchingMethods. SIAM Review, 41:199-235, 1999. [14] J.Sethian. A Fast Marching Level Set method for monotonically advancing fronts. Proc. Nat. Acad. Sci, 93:1591 – 1595, 1996. [15] J.Sethian. Theory, algorithms, and application of level set methods for pro- pagation interfaces. Acta Numerica, pages 309-395, 1996. [16] Và một số website: color/ Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 38 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái phụ lục Ước lượng tham số bằng phương pháp hợp lý cực đại Giả sử đám đông có một hoặc nhiều các đặc trưng chưa biết (chẳng hạn θ). Ta căn cứ vào mẫu quan sát được mà ước lượng một giá trị hợp lý cho đặc trưng này (gọi là θˆ ). Giả sử ta tiến hành n mẫu quan sát độc lập (X1, .., Xn) được kết quả là (x1,.., xn). Ta xét hàm ∏ = = n k kn xfxxL 1 1 ),(),..,,( θθ là xác suất để ta nhận được mẫu cụ thể đang xét và gọi là hàm hợp lý, trong đó f(x, θ) là hàm mật độ của X với tham số θ. Ta sẽ đi tìm ước lượng của θ là θˆ sao cho hàm hợp lý L(θ, x1,.., xn) đạt giá trị cực đại, nghĩa là: ),..,,(maxargˆ 1 nxxL θθ θ= Như vậy ước lượng hợp lý nhất của θ là giá trị làm cho xác suất nhận được mẫu đang xét là lớn nhất. Ứng dụng trong đề tài: Ước lượng giá trị λ trong phân phối Laplace kỳ vọng 0 (sử dụng ở phần 3.1) xi exf λλλ −= 2 ),( ∏ = − ∑⎟⎠ ⎞⎜⎝ ⎛== = n i xn in n i i exfxxL 1 1 1 2 ),(),..,,( λλλλ (*) Vì hàm ln(x) là hàm đồng biến, nên ta xét ( )nxxL ,..,,ln 1λ thay vì xét hàm ),..,,( 1 nxxL λ . ∑ = −⎟⎠ ⎞⎜⎝ ⎛= n i in xnxxL 1 1 2 ln),..,,(ln λλλ Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 39 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Giá trị ước lượng λˆ là giá trị làm (*) đạt cực đại, nên sẽ là nghiệm của phương trình: 0 ),..,,(ln 1 =∂ ∂ λ λ nxxL ⇔ 0ˆ 1 1 =− ∑ = n i ixn λ ⇔ ∑ = = n i ix n 1 λˆ Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 40 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Giải thuật phân lớp bằng phương pháp xác suất Phân lớp là một trong những giai đoạn mở đầu và quan trọng trong nhiều lãnh vực nhận dạng, xử lý ảnh. Khoảng cách luôn là công cụ thường dùng để phân lớp, một phần tử được xếp vào lớp mà nó có độ đo khoảng cách đến lớp đó nhỏ nhất. Ở đây, ta xét một phương “tự nhiên” hơn dựa vào xác suất Bayes và phương pháp hợp lý cực đại. Giả sử tập hợp X cần được phân thành k lớp. Xác suất đề phần tử x được xếp vào lớp i là )|( ixP . Và một cách rất tự nhiên ta chọn nhóm cần xếp cho x là nhóm ix sao cho xác suất x rơi vào nhóm ix là cao nhất. Thuật toán có thể được mô tả như sau: Bước khởi tạo: - Phân X ngẫu nhiên thành k lớp. - Tính xác suất để phần tử x rơi vào lớp i: P(x|i) Bước lặp: - Với mỗi phần tử x ta chọn lớp ix có P(x|xi) cao nhất - Tính lại xác suất - Tiếp tục thực hiện cho đến khi không còn sự thay đổi nào. Ứng dụng trong đề tài: Tại bước ước lượng các tham số (phần 3.1) ta chỉ cần phân tập hợp các chênh lệch mức xám thành 2 lớp : “động” và “tĩnh”. Ta cải tiến thuật toán trên để thời gian phân lớp được nhanh hơn. Ban đầu sắp xếp các chênh lệch mức xám |d(n)| tăng dần và chọn một ngưỡng (no, |do|) là ranh giới của hai lớp. Bước tiếp theo ta viết hàm phân phối xác suất biểu diễn khả năng của một điểm thuộc về vùng “động” hay “tĩnh”, tuân theo luật phân phối Laplace với các tham số được ước lượng ở trên. Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 41 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Hình 15: Phân lớp động và tĩnh || 2 ),( dl lellabeldf λ λ −== 0 0 0 0 |)(| n id n i ∑ ==λ , 1 |)(| 0max 1 1 max 0 −−= ∑ += nn id n niλ Tiếp đó trong bước lặp thay vì phải cập nhật toàn bộ, ta chỉ cần dịch chuyển no qua phải hoặc qua trái tùy theo nó được phân phối vào vùng nào. n |d(n)| |d0| no độngtĩnh Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 42 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Hình 16: Kết quả phân lớp bằng phương pháp xác suất Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 43 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái Hệ màu CieLab Hệ màu Cie Lab biểu diễn màu thông qua 3 giá trị L, a, b được CIE giới thiệu vào năm 1976. Ta có thể biểu diễn hệ màu này bằng hệ trục sau: Hình 17: Hệ màu CIE Lab Trong đó trục đứng L* biểu diễn độ sáng của màu, mang giá trị từ 0 (đen) đến 100 (trắng). Hai trục còn lại có cả giá trị âm và dương(trong khoảng từ -120 đến +120). Trên trục a, giá trị dương trên chỉ sắc độ đỏ, giá trị âm chỉ sắc độ xanh lục. Trên trục b, giá trị dương chỉ sắc độ vàng, giá trị âm chỉ sắc độ xanh dương. Công thức chuyển đổi từ CIE Lab Trước tiên, chuyển từ RGB sang CIE XYZ XYZ của màu trắng (255, 255, 255) X0 = 0.607 * 255 + 0.174 * 255 + 0.200 * 255 Y0 = 0.299 * 255 + 0.587 * 255 + 0.114 * 255 Z0 = 0.000 * 255 + 0.066 * 255 + 1.116 * 255 XYZ của màu cần chuyển (R, G, B) X = 0.607 * R + 0.174 * G + 0.200 * B Y = 0.299 * R + 0.587 * G + 0.114 * B Z = 0.000 * R + 0.066 * G +1.116 * B Chuẩn hóa XYZ Tiểu luận: Phát hiện và định vị sự thay đổi của đối tượng trong dãy ảnh liên tiếp Trang 44 GVHD: ThS Phạm Thế Bảo SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái X = X / X0 Y = Y / Y0 Z = Z / Z0 0088560 0088560 3903 160116 31 .Y .Y Y*. Y*.L ≤ > ⎪⎩ ⎪⎨ ⎧ −= a = 500.0*(fX-fY) b = 200.0*(fY-fZ) với 0088560X 0088560X 116 16X7877 X fX 31 . . *. ≤ > ⎪⎩ ⎪⎨ ⎧ + = 0088560Y 0088560Y 116 16Y7877 Y fY 31 . . *. ≤ > ⎪⎩ ⎪⎨ ⎧ + = 0.008856Z 0.008856Z 116 16Z*7.787 Z fZ 31 ≤ > ⎪⎩ ⎪⎨ ⎧ + = Ta nhận được các giá trị của L, a, b trong hệ màu CieLab.