Luận án Kỹ thuật xử lý vùng quan sát và phát hiện bất thường của các đối tượng trong hệ thống camera giám sát (Chuyên ngành: Cơ sở Toán học cho Tin học)

n cứu Luận án tập trung nghiên cứu các vấn đề sau:  Thứ nhất: Hệ thống camera giám sát và các bài toán liên quan;  Thứ hai: Các kỹ thuật chuyển tiếp camera trong hệ thống camera giám sát với nhiều camera;  Thứ ba: Các kỹ thuật phát hiện bất thường trong giám sát video. 3. Những đóng góp mới của luận án Có thể khái quát các kết quả chính của luận án như sau:  Đề xuất kỹ thuật phân vùng giám sát cố định cho các camera trong hệ thống camera giám sát dựa trên quan hệ hình học giữa thị trường quan sát của các camera, giúp giảm thiểu số lần tính toán chuyển tiếp camera thông qua việc giảm thiểu các cạnh của đa giác quan sát trong vùng giao nhau giữa các camera trong hệ thống OVL. Kỹ thuật đề xuất được công bố trong 3 Chuyên san của Tạp chí Công nghệ thông tin và Truyền thông năm 2014.  Đề xuất một cách tiếp cận giải quyết việc chuyển tiếp camera dựa trên việc tính toán sự va chạm của đối tượng chuyển động với đường ranh giới ảo, kỹ thuật đề xuất đã được công bố tại Tạp chí Khoa học Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam năm 2013.  Đề xuất một kỹ thuật giải quyết việc chuyển tiếp camera thông qua việc lựa chọn camera, nhằm giảm thiểu số lần chuyển tiếp camera khi giám sát đối tượng. Kỹ thuật đề xuất đã được trình bày và đăng trong Kỷ yếu Hội nghị Quốc Gia “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin – FAIR” năm 2013.  Đề xuất một kỹ thuật phát hiện chuyển động bất thường dựa vào quỹ đạo chuyển động của đối tượng. Kỹ thuật đề xuất cho phép thao tác trên các quỹ đạo không hoàn chỉnh, đáp ứng được yêu cầu triển khai thời gian thực. Kỹ thuật đề xuất được công bố tại Chuyên san của Tạp chí Công nghệ thông tin và Truyền thông năm 2015. 4. Bố cục luận án Luận án bao gồm phần mở đầu, kết luận và 3 chương nội dung. Chương 1: Tổng quan về chuyển tiếp camera và phát hiện bất thường trong các hệ thống camera giám sát. Các vấn đề chung về giám sát tự động trong hệ thống camera giám sát, cùng với các bài toán liên quan được khảo sát và trình bày trong chương này. Chương 2: Một số kỹ thuật xử lý vùng quan sát trong chuyển tiếp camera. Đề xuất các kỹ thuật xử lý vùng quan sát trong việc giải quyết bài toán chuyển tiếp camera nhằm mục đích giảm thiểu các thao tác tính toán chuyển tiếp 4 camera, từ đó giúp nâng cao hiệu quả hoạt động của hệ thống camera giám sát. Chương 3: Phát hiện bất thường dựa vào quỹ đạo trong giám sát video. Trình bày tóm lược về các hướng tiếp cận, các kỹ thuật đã được áp dụng giải quyết bài toán phát hiện bất thường trong giám sát video, từ đó đề xuất một kỹ thuật phát hiện bất thường trong giám sát video dựa vào phân tích quỹ đạo chuyển động của đối tượng. CHƯƠNG 1: TỔNG QUAN VỀ CHUYỂN TIẾP VÀ PHÁT HIỆN BẤT THƯỜNG TRONG CÁC HỆ THỐNG CAMERA GIÁM SÁT 1.1. Hệ thống camera giám sát tự động Trong phần này, luận án giới thiệu tổng quan về hệ thống camera giám sát tự động cùng với các vấn đề cơ bản của chúng. 1.2. Chuyển tiếp camera và phát hiện bất thường Phần này, luận án trình bày các kỹ thuật, các hướng tiếp cận giải quyết các hai bài toán trong hệ thống camera giám sát tự động, đó là: chuyển tiếp camera và phát hiện bất thường trong giám sát video. 1.3. Kết luận và vấn đề nghiên cứu Trong chương này, luận án đã trình bày những nét tổng quan chung của hệ thống camera giám sát tự động cùng với các vấn đề cơ bản liên quan. Bên cạnh đó, luận án cũng giới thiệu một số tiếp cận trong việc theo vết đối tượng với hệ thống giám sát có nhiều camera, đặc biệt tập trung trình bày các hướng tiếp cận hiện có giải quyết bài toán chuyển tiếp camera và phát hiện bất thường trong hệ thống camera giám sát, đây là hai bài toán có tầm quan trọng và được ứng dụng nhiều trong thực tế. 5 CHƯƠNG 2: MỘT SỐ KỸ THUẬT XỬ LÝ VÙNG QUAN SÁT TRONG CHUYỂN TIẾP CAMERA Trong chương này, luận án trình bày ba đề xuất liên quan đến trả lời câu hỏi: Chuyển tiếp camera được thực hiện khi nào và camera nào được nhận chuyển giao, các đề xuất của luận án tập trung vào việc giảm thiểu việc tính toán chuyển tiếp camera trong hệ thống camera giám sát, từ đó nâng cao được hiệu suất hoạt động của hệ thống. 2.1. Giới thiệu 2.2. Phân vùng giám sát 2.2.1. Giới thiệu Trong phần này, luận án đề xuất một kỹ thuật phân chia vùng quan sát của hệ thống camera thành các vùng con không giao cắt trong môi trường 2D (Hình 2.1.b). (a) Phân vùng giám sát trong môi trường 1D (b) Phân vùng giám sát trong môi trường 2D Hình 2.1. Một số hình thức phân vùng giám sát. 2.2.2. Giao cắt của hai đa giác Định nghĩa 2.1 [đa giác quan sát] Đa giác quan sát của camera là hình chiếu vùng quan sát của camera xuống mặt phẳng 2D. Định nghĩa 2.2 [Điểm giao cắt của hai đa giác quan sát] Cho hai đa giác quan sát A, B. Khi đó một điểm được gọi là điểm giao cắt của hai đa giác A, B nếu nó là giao của một cạnh của đa giác A với một cạnh của đa giác B và không là các đỉnh của A hoặc B. Định nghĩa 2.3 [Giao cắt đơn] 6 Cho hai đa giác quan sát A, B. Khi đó, A, B được gọi là giao cắt đơn nếu: Phần giao của A và B là một đa giác lồi và phần còn lại của mỗi đa giác sau khi loại bỏ phần giao là một đa giác. (a) (b) (c) Hình 2.2. Các trường hợp giao nhau của hai đa giác a). Hai đa giác không giao nhau; b) Hai đa giác giao nhau thuộc loại Giao cắt đơn; c) Hai đa giác giao nhau không là giao cắt đơn Mệnh đề 2.1 A, B là hai đa giác quan sát và A, B là giao cắt đơn. Khi đó số lượng điểm giao cắt giữa A và B không quá 2. 2.2.3. Phân chia vùng quan sát của hệ thống camera 2.2.3.1. Phân vùng giao nhau của hai đa giác Mệnh đề 2.2 [Chia cắt hai đa giác] Cho A, B là hai đa giác quan sát và A, B là giao cắt đơn, nếu tồn tại hai điểm giao cắt thì đường nối hai điểm giao cắt là đường chia cắt mà mỗi đa giác sau khi chia có số cạnh nhỏ nhất (Hình 2.4). Hình 2.22. Chia cắt phần giao giữa hai đa giác 2.2.3.2. Phân vùng quan sát của hệ thống giám sát gồm nhiều camera Với khu vực giám sát đã triển khai có n camera tĩnh, cùng với thông tin về vùng quan sát của mỗi camera, các đa giác quan sát của các camera chồng chéo lên nhau và thuộc loại giao cắt đơn. Thực hiện 7 phân vùng giám sát của hệ thống thành tập các đa giác quan sát của từng camera, tập các đa giác này không giao nhau. Hàm partitionTwoPolygon: Thực hiện phân vùng hai đa giác giao nhau sao cho số cạnh của mỗi đa giác sau khi chia là nhỏ nhất.  Vào: A=(A[1], A[2], ..., A[n]); B=(B[1], B[2], ..., B[m]); trong đó A[i], B[j] là các đỉnh.  Ra: hai đa giác X và Y, thỏa mãn: 𝑨 ∪ 𝑩 = 𝑿 ∪ 𝒀 trong đó 𝑨 ∪ 𝑿 ∩ 𝒀 = ∅; 𝑿 ⊆ 𝑨; 𝒀 ⊆ 𝑩;  Giả mã của hàm partitionTwoPolygon (A, B: polygon) { Tìm hiệu P(P[1], P[2], ..., P[t]) = A\B. Tìm hai giao điểm P[h], P[k] (h< k< t) của mỗi cặp cạnh trong phần giao của A và B. For i = 1 to h 𝑋 = 𝑋 ∪ 𝑃[𝑖]; For i = k to t 𝑋 = 𝑋 ∪ 𝑃[𝑖]; Y = B – X; A = X; B = Y;} Thuật toán PartitionFOV  Vào: Vùng quan sát hệ thống 𝑷 = {𝑷[𝟏], 𝑷[𝟐], . . , 𝑷[𝒏]} (với n nguyên dương). Trong đó, 𝑷[𝒊] = {𝑽𝟏, 𝑽𝟐, . . 𝑽𝒕}, với Vk (xk,yk) là đỉnh của đa giác có tọa độ (xk, yk), các đỉnh được sắp theo thứ tự kim đồng hồ.  Ra: Q=(Q[1], Q[2], ..., Q[n]) thỏa mãn:  n i iQP 1 ][   ; trong đó: 𝐐[𝐢] ∩ 𝐐[𝐣] = ∅ (∀𝒊, 𝒋 ∈ 𝟏. . 𝒏) và 𝐐[𝐢] ∈ 𝐏[𝐢](∀𝒊 ∈ 𝟏. . 𝒏).  Giả mã của thuật toán Nhập thông tin vùng quan sát của n camera: P[i] (i=1..n) 8 Q[]={0}; Q[1]=P[1]; i=1; j=1; While (i  n){ i=i+1; T=P[i]; k=1; While (k<=j){ if(Q[k] giao với T) partitionTwoPolygon(Q[k],T); k=k+1;} j=j+1; Q[j]=T;} Độ phức tạp tính toán: Có thể thấy rằng, với một vùng giám sát có n camera, tại lượt thứ i ta cần thực hiện (i – 1) hàm phân vùng partitionTwoPolygon. Tổng quát, số lần thực hiện: 2 )1(...21 2n n  Do vậy, độ phức tạp của thuật toán PartitionFOV là O(n2). 2.2.4. Thực nghiệm Luận án đã tiến hành cài đặt thử nghiệm thuật toán đề xuất trên trong môi trường Matlab R2010a, với đầu vào là các vùng quan sát của hệ thống camera được Yi Yao triển khai theo thuật toán của Erdem (hình 2.6.b). Mục đích của thực nghiệm là nhằm đưa ra một cách chia vùng quan sát của hệ thống camera đã triển khai thành các vùng con không giao cắt, mỗi vùng con này sẽ được giao cho một camera quản lý. Với kỹ thuật phân vùng như đã đề xuất thì độ bao phủ luôn được đảm bảo cao nhất, đồng thời vùng quan sát được chia thành các đa giác không giao nhau, việc giải quyết bài toán chuyển tiếp camera sẽ thuận lợi hơn rất nhiều khi kết hợp với kỹ thuật đường ranh giới ảo. Kỹ thuật đề xuất đã được công bố trong Chuyên san của Tạp chí Công nghệ thông tin và Truyền thông năm 2014. 9 a) Sơ đồ mặt bằng giám sát b) Sơ đồ bố trí của Yi Yao c) Các vùng chồng lấn và số cạnh của đa giác theo sơ đồ bố trí của Yi Yao d) Kết quả thực hiện theo thuật toán đề xuất Hình 2.6. Phân vùng quan sát cho các camera của hệ thống giám sát 2.3. Chuyển tiếp camera dựa vào đường ranh giới ảo 2.3.1. Đường ranh giới ảo Với ý tưởng tại vùng giao nhau giữa các camera, thực hiện lập các đường ranh giới ảo, nhằm xác định khu vực giám sát của mỗi camera, từ đó thời điểm chuyển giao camera được xác định khi đối tượng chuyển động va chạm với đường ranh giới ảo. Để nâng cao được độ chính xác khi xác định thời điểm chuyển giao đối tượng trong quá trình giám sát, luận án thực hiện tính toán va chạm của đối tượng chuyển động với đường ranh giới ảo trong môi trường 3D thay vì tính toán trong môi trường 2D. Khi đó đối tượng được giám sát và đường ranh giới ảo được mô hình hóa là các khối hộp trong môi trường 3D. -15 -10 -5 0 5 10 15 -20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0 C1 C2 C4 C3 C6 C5 10 Hình 2.11. Đối tượng chuyển động và đường ranh giới ảo trong môi trường 3D 2.3.2. Tính toán va chạm của đối tượng với đường ranh giới ảo Luận án trình bày các tính toán cần thiết để kiểm tra sự va chạm của đối tượng với đường ranh giới ảo trong môi trường 3D. 2.3.3. Kỹ thuật đề xuất 2.3.3.1. Mô hình hệ thống Mô hình của hệ thống được thể hiện trong hình 2.16. Hình 2.16. Mô hình cấu trúc của hệ thống 2.3.3.2. Thuật toán Sơ đồ thực hiện thuật toán được thể hiện trong hình 2.17. 11 ServerWorkstation Phát hiện đối tượng chuyển động Có đối tượng chuyển động Sai Có yêu cầu chuyển tiếp Đúng Theo vết đối tượng Đối tượng đã có nhãn Lưu thông tin đối tượng Cập nhật CSDL đối tượng Tiếp nhận nhãn đối tượng Yêu cầu tiếp nhận chuyển tiếp Khởi tạo CSDL Sinh nhãn mới Va chạm với đường ranh giới ảo Yêu cầu chuyển tiếp Đúng Sai Đúng Yêu cầu cập nhật CSDL Sai Đúng Sai Chọn lựa camera chuyển tiếp Điều phối chuyển tiếp camera Hình 2.17. Sơ đồ thực hiện chương trình của hệ thống 2.3.4. Thực nghiệm Luận án đã tiến hành cài đặt chương trình demo VirtualLine. Chương trình được phát triển trên môi trường Visual C++ 2008 với bộ thư viện mã nguồn mở OpenCV. Đầu vào của chương trình là dữ liệu 12 video kết nối trực tiếp với 3 camera giám sát một căn phòng với thị trường quan sát bị chồng chéo như Hình 2.18. Hình 2.19 thể hiện việc chuyển tiếp theo dõi giữa các camera. Người di chuyển va chạm với đường ranh giới ảo giữa các (đường mầu đỏ) đã được đánh dấu (mầu đỏ) và xuất hiện tại vùng quan sát của camera được chuyển tiếp cùng với thông tin về chỉ số của đối tượng và camera chuyển/nhận bàn giao. Hình 2.18. Sơ đồ mặt bằng bố trí camera (a) Chuyển tiếp giữa camera 1 và camera 2 13 (a) Chuyển tiếp giữa camera 2 và camera 3 Hình 2.19. Chuyển tiếp giữa 2 camera Kết quả thực nghiệm cho thấy, độ chính xác của thời điểm chuyển tiếp với tính toán trong môi trường 3D cao hơn trong môi trường 2D. Kỹ thuật đề xuất đã được đăng tại Tạp chí Khoa học Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam năm 2013. 2.4. Chọn lựa camera dựa trên hướng chuyển động của đối tượng 2.4.1. Dự đoán vị trí và hướng chuyển động của đối tượng Trong phần này luận án sử dụng bộ lọc Kalman để xây dựng mô hình dự báo vị trí và hướng chuyển động của đối tượng. 2.4.2. Biểu diễn mối quan hệ giữa các vùng quan sát của hệ thống Luận án sử dụng danh sách kề để biểu diễn mối quan hệ giữa các vùng quan sát của hệ thống camera. 2.4.3. Thuật toán chọn lựa camera dựa vào hướng chuyển động Gọi A, B tương ứng là tọa độ vị trí của đối tượng tại thời điểm 𝑡1 và 𝑡2: 𝐴(𝑥𝑡1 , 𝑦𝑡1), 𝐵(𝑥𝑡2 , 𝑦𝑡2). Nhằm hạn chế việc chuyển tiếp camera, chiến lược ở đây là tính toán khả năng đối tượng di chuyển (tồn tại) trong vùng quan sát của một camera là lâu nhất. Luận án đề xuất tính toán bằng cách dựng một đường thẳng qua A và B, tìm giao điểm của đường thẳng đó với các cạnh của mỗi đa giác. Giao điểm C tìm được phải thỏa mãn A và C nằm về hai phía của B. Gọi Dj là độ dài đoạn BC của camera thứ j. Khi đó camera được chọn là camera có Dj lớn nhất. 14 Hàm findIntersectPolygon tìm giao điểm C của AB với cạnh của đa giác P.  Vào: P=(P[1], P[2], ..., P[n]); Đỉnh A, B.  Ra: Điểm C là giao của AB với một cạnh của P, thỏa mãn: 𝑨𝑩̅̅ ̅̅ + 𝑩𝑪̅̅ ̅̅ = 𝑨𝑪̅̅ ̅̅  Giả mã của hàm: findIntersectPolygon (P: polygon; A, B: point) { Lập phương trình đường thẳng AB; For i=1 to n do { C= giao điểm AB với cạnh (P[i],P[i+1]); If (𝐴𝐵̅̅ ̅̅ + 𝐵𝐶̅̅ ̅̅ = 𝐴𝐶̅̅ ̅̅ ) return C;}} Thuật toán đề xuất:  Vào: Q=(Q[1], Q[2], ..., Q[n]) là tập đa giác quan sát Vị trí của đối tượng tại thời điểm 𝑡1: 𝐴(𝑥𝑡1 , 𝑦𝑡1) Vị trí dự đoán của đối tượng tại thời điểm 𝑡2: 𝐵(𝑥𝑡2 , 𝑦𝑡2) Đồ thị G=(V, E): Danh sách kề của Ke(i) Chỉ số i (camera đang theo dõi đối tượng)  Ra: Chỉ số t: chỉ số của camera nhận chuyển tiếp.  Giả mã của thuật toán: k = 0; t = 0; C=findIntersectPolygon(Q[Ke(i)[k]], A, B); Dmax= BC ; t=Ke(i)[k]; while (k<length(Ke(i)) do { k++; C=findIntersectPolygon(Q[Ke(i)[k]], A, B); If(dmax< BC ){ dmax= BC ; t=Ke(i)[k];}}  Đánh giá độ phức tạp tính toán 15 Với một vùng giám sát có n camera, tại thời điểm đối tượng ra khỏi khu vực quan sát của camera i thì cần phải duyệt các camera trong danh sách kề với camera đó (Ke(i)), sử dụng hàm findIntersectPolygon thực hiện tìm giao của AB với các cạnh của các đa giác quan sát trong danh sách kề. Do vậy độ phức tạp của thuật toán là O(n2). 2.4.4. Thực nghiệm Hình 2.24 minh họa kết quả thực hiện giải thuật với đầu vào là các vùng quan sát của hệ thống camera được triển khai bởi Eduardo Monari. Kết quả thực nghiệm cho thấy số lần chuyển tiếp camera trong hệ thống với các camera có sự chồng lấn thị trường quan sát đã giảm đáng kể. Hình 2.24. Kết quả thực hiện giải thuật chọn lựa camera Kỹ thuật đề xuất được trình bày và đăng trong Kỷ yếu Hội nghị Quốc Gia “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin – FAIR” năm 2013. 2.5. Kết luận chương 2 Nhằm giải quyết câu hỏi: “Chuyển tiếp camera được thực hiện khi nào và camera nào được nhận chuyển giao?” trong bài toán chuyển tiếp camera, chương này đã đề xuất 3 kỹ thuật, các kỹ thuật đều tập trung vào giảm thiểu các tính toán chuyển tiếp camera của hệ thống, từ đó giúp nâng cao hiệu quả hoạt động của hệ thống giám sát. Thứ nhất: Đề xuất một kỹ thuật phân vùng giám sát cố định cho các camera dựa vào giao cắt đơn, nhằm phân chia vùng quan sát của 16 hệ thống camera thành các vùng con không giao cắt với tiêu chí giảm thiểu số cạnh của các đa giác quan sát sau khi phân vùng, từ đó giảm số lần tính toán chuyển tiếp khi đối tượng di chuyển vào các vùng giao nhau của các camera. Thứ hai: Đề xuất kỹ thuật xác định thời điểm thực hiện chuyển tiếp camera thông qua việc tính toán va chạm của đối tượng với đường ranh giới ảo trong môi trường 3D. Kết quả thực nghiệm cho thấy với kỹ thuật đề xuất thì độ chính xác của việc xác định thời điểm chuyển tiếp đã được tăng lên đáng kể. Thứ ba: Đề xuất một kỹ thuật chọn lựa camera dựa trên hướng chuyển động của đối tượng, giúp giảm số lần chuyển tiếp camera khi đối tượng di chuyển qua các vùng quan sát của các camera trong hệ thống OVL. CHƯƠNG 3: PHÁT HIỆN BẤT THƯỜNG DỰA VÀO QUỸ ĐẠO TRONG CÁC VIDEO GIÁM SÁT Trong chương này, luận án trình bày một số tiếp cận giải quyết bài toán phát hiện bất thường trong camera giám sát. Tiếp theo là đề xuất kỹ thuật phát hiện bất thường dựa vào quỹ đạo chuyển động của đối tượng. 3.1. Giới thiệu 3.1.1. Tiếp cận dựa trên phân tích hình ảnh dòng video Nhóm tiếp cận dựa trên phân tích hình ảnh dòng video sử dụng các kỹ thuật xử lý ảnh, thao tác với các vùng ảnh chuyển động có được từ giai đoạn phát hiện đối tượng chuyển động, kết hợp với các mô hình xác suất, phân cụm, thống kê để phát hiện bất thường. 3.1.2. Tiếp cận dựa vào phân tích quỹ đạo Các tiếp cận dựa trên việc phân cụm quỹ đạo được thực hiện theo sơ đồ được chỉ ra ở hình 3.1. Phần lớn các thuật toán đề xuất dựa trên kỹ thuật phân cụm được thiết kế chủ yếu để phát hiện bất thường 17 trong quỹ đạo hoàn chỉnh, tức là tất cả các điểm dữ liệu từ quỹ đạo được yêu cầu trước khi phân loại nó là bất thường hay không. Điều này rõ ràng là một hạn chế trong ứng dụng giám sát tự động bởi yêu cầu thực hiện trong thời gian thực. Hình 3.1. Phát hiện bất thường dựa vào phân cụm quỹ đạo 3.2. Một số khái niệm, định nghĩa trong mô hình đề xuất  Định nghĩa 3.1 [Quỹ đạo chuyển động] Quỹ đạo chuyển động của đối tượng O là dãy các điểm 𝑡1, 𝑡2, , 𝑡𝑛 thể hiện vị trí tại các thời điểm khác nhau của O, được ký hiệu: 𝑂 = {𝑡1, 𝑡2, , 𝑡𝑛}.  Định nghĩa 3.2 [Độ tương tự giữa hai quỹ đạo] Cho hai quỹ đạo 𝐴 = {𝑎1, 𝑎2, , 𝑎𝑛} và 𝐵 = {𝑏1, 𝑏2, , 𝑏𝑚} Khi đó, độ tương tự giữa hai quỹ đạo A, B, kí hiệu là h(A, B) được xác định như sau: ℎ(𝐴, 𝐵) = 𝑚𝑎𝑥{𝑑(𝐴, 𝐵), 𝑑(𝐵, 𝐴)} (3.1) Trong đó, 𝑑(𝐴, 𝐵), 𝑑(𝐵, 𝐴) được tính theo công thức: 𝑑(𝐴, 𝐵) = 𝑚𝑎𝑥{𝑑(𝑎𝑖, 𝐵): 𝑎𝑖 ∈ 𝐴} (3.2) 𝑑(𝐵, 𝐴) = 𝑚𝑎𝑥{𝑑(𝑏𝑖, 𝐴): 𝑏𝑖 ∈ 𝐵} (3.3) 18 Với 𝑑(𝑎𝑖 , 𝐵), 𝑑(𝑏𝑖, 𝐴) được tính theo công thức: 𝑑(𝑎𝑖 , 𝐵) = min {𝑑(𝑎𝑖 , 𝑏𝑗): 𝑏𝑗 ∈ 𝐵} (3.4) 𝑑(𝑏𝑖, 𝐴) = min {𝑑(𝑏𝑖, 𝑎𝑗): 𝑎𝑗 ∈ 𝐴} (3.5) Trong đó, 𝑑(𝑎𝑖, 𝑏𝑗) được tính như sau: 𝑑(𝑎𝑖, 𝑏𝑗) = 𝑑𝑒(𝑎𝑖 , 𝑏𝑗) + 𝛾𝑑𝑜(𝑎𝑖, 𝑏𝑗) (3.6) Trong đó, 𝑑𝑒(𝑎𝑖 , 𝑏𝑗) là khoảng cách Euclidean giữa 𝑎𝑖 và 𝑏𝑗: 𝑑𝑒(𝑎𝑖, 𝑏𝑗) = √(𝑥𝑖 𝑎 − 𝑥𝑗 𝑏) 2 + (𝑦𝑖 𝑎 − 𝑦𝑗 𝑏) 2 (3.7) Và 𝑑𝑜(𝑎𝑖, 𝑏𝑗) được xác định thông qua véc tơ vận tốc 𝑣𝑎𝑖 tại 𝑎𝑖 và 𝑣𝑏𝑗 tại 𝑏𝑗: 𝑑𝑜(𝑎𝑖, 𝑏𝑗) = 1 − 𝑣𝑎𝑖 . 𝑣𝑏𝑗 |𝑣𝑎𝑖|. |𝑣𝑏𝑗| (3.8) Trong đó, vận tốc tại 𝑎𝑖 và 𝑏𝑗 được xác định: 𝑣𝑎𝑖 = (𝑥𝑖 𝑎 − 𝑥𝑖−1 𝑎 , 𝑦𝑖 𝑎 − 𝑦𝑖−1 𝑎 ) (3.9) 𝑣𝑏𝑗 = (𝑥𝑗 𝑏 − 𝑥𝑗−1 𝑏 , 𝑦𝑗 𝑏 − 𝑦𝑗−1 𝑏 ) (3.10) 𝛾 là tham số nhằm điều chỉnh trọng số của hướng di chuyển.  Định nghĩa 3.3 [Quan hệ liên kết 𝑸𝜽] Cho trước ngưỡng , hai quỹ đạo U, V  T (tập các quỹ đạo) được gọi là quan hệ liên kết theo  và ký hiệu là Qθ(𝑈, 𝑉) nếu tồn tại dãy các quỹ đạo O1, O2, , On sao cho: (i). 𝑈 ≡ 𝑂1 (ii). 𝑉 ≡ 𝑂𝑛 (iii). ℎ(𝑂𝑖, 𝑂𝑖+1) < 𝜃, ∀ 𝑖, 1 ≤ i ≤ n − 1  Mệnh đề 3.1: Quan hệ liên kết Q là một quan hệ tương đương. 19 Luận án đã chứng minh quan hệ liên kết Q thỏa mãn các tính chất: phản xạ, đối xứng, bắc cầu.  Khái niệm Tuyến đường Quan hệ liên kết 𝑄𝜃 giữa các quỹ đạo là một quan hệ tương đương, nên nó phân lớp các quỹ đạo thành các lớp tương đương. Từ nay về sau ta gọi mỗi lớp tương đương là một tuyến đường. Các quỹ đạo trong cùng một tuyến đường thường được xem là có cùng số điểm biểu diễn.  Định nghĩa 3.4 [Đường đại diện của tuyến đường] Cho tuyến đường 𝑅 = {𝑂1, 𝑂2, , 𝑂𝑘}, đường đại diện của tuyến đường 𝑅 là 𝑃 = {𝑝𝑖}|(𝑖 = 1. . 𝑛) được xác định như sau: 𝑝𝑖 = { 1 𝑘 ∑ O𝑗[𝑡𝑖] 𝑘 𝑗=1 } (3.11) Trong đó, k là số lượng quỹ đạo thuộc tuyến đường 𝑅, n là chiều dài quỹ đạo.  Định nghĩa 3.5 [Độ rộng của tuyến đường] Cho tuyến đường 𝑅 = {𝑂1, 𝑂2, , 𝑂𝑘} và 𝑃 = {𝑝𝑖}|(𝑖 = 1. . 𝑛) là đường đại diện của tuyến đường R. Khi đó, độ rộng tuyến đường R ký hiệu là ℎ𝑅 được xác định như sau: ℎ𝑅 = max 𝑖=1..𝑘 {ℎ(𝑂𝑖, 𝑃)} (3.12)  Định nghĩa 3.6 [Quỹ đạo bất thường đối với một tuyến đường] Cho 𝑃 = {𝑝𝑖} là đường đại diện của tuyến đường 𝑅 = {𝑂1, 𝑂2, , 𝑂𝑘} và quỹ đạo 𝑇 ∗ = {𝑡1, 𝑡2, , 𝑡𝑛}, T* được gọi là bất thường đối với R nếu ℎ(𝑇∗, 𝑃) > ℎ𝑅. 20  Khái niệm bất thường Khi giám sát một khu vực bởi camera, các đối tượng (con người) di chuyển theo các quỹ đạo thường hình thành theo các nhóm nhất định (tuyến đường). Trong luận án này, đối tượng có hành vi bất thường là đối tượng có quỹ đạo chuyển động không thuộc bất kỳ tuyến đường nào trong các tuyến đường cho trước, nói cách khác đó là quỹ đạo bất thường với tất cả các tuyến đường cho trước. 3.3. Phân đoạn quỹ đạo Luận án dựa vào tỷ lệ thay đổi vận tốc của đối tượng chuyển động làm tiêu chí thực hiện phân đoạn. Điểm phân đoạn được xác định là điểm mà ở đó tỷ lệ thay đổi vận tốc 𝑟𝑎𝑡𝑒(𝑣𝑖) vượt qua ngưỡng 𝜗. 𝑟𝑎𝑡𝑒(𝑣𝑖) = 𝑚𝑖𝑛 ( 𝑣𝑖 𝑥 − 𝑣𝑖−1 𝑥 𝑣𝑖−1 𝑥 , 𝑣𝑖 𝑦 − 𝑣𝑖−1 𝑦 𝑣𝑖−1 𝑦 ) (3.13) Trong đó, 𝑣𝑖 𝑥, 𝑣𝑖 𝑦 tương ứng là vận tốc theo hướng x và hướng y, chúng được tính là khoảng cách giữa hai điểm lân cận trong cùng một khoảng thời gian: 𝑣𝑖 𝑥 = 𝑥𝑖 − 𝑥𝑖−1 và 𝑣𝑖 𝑦 = 𝑦𝑖 − 𝑦𝑖−1  Định lý 3.1. [Phát hiện bất thường dựa vào quỹ đạo con] Cho P là đường đại diện của một tuyến đường R: 𝑃 = {𝑝1, 𝑝2 , 𝑝𝑛 } với 𝑠𝑒𝑔 = {𝑠𝑒𝑔1, 𝑠𝑒𝑔2, . . , 𝑠𝑒𝑔𝑢} là các điểm phân đoạn của P (1 < 𝑢 < 𝑛). T* là quỹ đạo cần kiểm tra. Khi đó, nếu T* được xác định là là bất thường với quỹ đạo con thứ i (1 ≤ 𝑖 ≤ 𝑢) thì T* là bất thường với mọi quỹ đạo con 𝑙(𝑖 < 𝑙 ≤ 𝑢). 21 3.4. Phát hiện bất thường dựa trên phân đoạn tuyến đường Trong phần này, luận án đề xuất một kỹ thuật gồm hai pha nhằm phát hiện bất thường từ video giám sát dựa trên các phân đoạn của tuyến đường (hình 3.5). Hình 3.5. Sơ đồ khối phát hiện bất thường dựa vào các phân đoạn của tuyến đường  Pha thứ nhất: Khởi tạo Ký hiệu:  𝑅 = {𝑅1, 𝑅2, , 𝑅𝑘} là tập các tuyến đường bình thường;  𝑟𝑖 là số lượng quỹ đạo của tuyến đường 𝑅𝑖 với (1 ≤ 𝑖);  𝑂𝑗 𝑖 là các quỹ đạo thuộc tuyến đường 𝑅𝑖; (1 ≤ 𝑖 ≤ 𝑘), (1 ≤ 𝑗 ≤ 𝑟𝑖)  𝑃 = {𝑃1, 𝑃2, , 𝑃𝑘} tập các đường đại diện của các tuyến đường. 𝑃𝑖 là đường đại diện của tuyến đường 𝑅𝑖;  𝑆𝑂𝑗 𝑖 là quỹ đạo con thứ j của đường đại diện 𝑃𝑖; 𝑆𝑂𝑗 𝑖 = {𝑃𝑖 (𝑝1, 𝑝2, . . 𝑝𝑠𝑒𝑔𝑗)}  Bước 1: Lập nhóm các quỹ đạo cùng một tuyến đường  Bước 2: Xây dựng đường đại diện của mỗi tuyến đường  Bước 3: Tính giá trị ngưỡng 𝑑𝑚𝑎𝑥 Giá trị ngưỡng 𝑑𝑚𝑎𝑥 được xác định theo công thức dưới đây: 𝑑𝑚𝑎𝑥 = min 𝑖=1..𝑘 { max 𝑗=1..𝑟𝑖 {ℎ(𝑂𝑗 𝑖, 𝑃𝑖)}} (3.14) 22  Bước 4: Phân đoạn các đường đại diện tuyến đường.  Pha thứ hai: Phát hiện bất thường dựa vào phân đoạn đường đại diện của tuyến đường.  Thuật toán: Abnormal Detecter Based on Sub – Trajectories of Route (ADB-STR)  Vào:  𝑢𝑚𝑎𝑥: là số quỹ đạo con lớn nhất của tất cả các tuyến đường  k: số lượng tuyến đường  𝑑𝑚𝑎𝑥: giá trị ngưỡng  {𝑆𝑂𝑗 𝑖} (𝑖 = 1. . 𝑘); (𝑗 = 1. . 𝑢𝑚𝑎𝑥): tập các quỹ đạo con của các tuyến đường  T*: quỹ đạo cần kiểm tra  Ra: Giá trị nhị phân Abnormal  Giả mã của thuật toán: j=1; Abnormal=false; While (𝑗 ≤ 𝑢𝑚𝑎𝑥 and Abnormal=false) do 𝑑 = min 𝑖=1..𝑘 (ℎ(𝑇∗, 𝑆𝑂𝑗 𝑖)); if (𝑑 > 𝑑max ) then Abnormal=true; j=j+1; End while;  Đánh giá độ phức tạp tính toán Có thể thấy rằng, với mỗi giá trị của j (𝑗 ≤ 𝑢𝑚𝑎𝑥), ta cần tìm d là giá trị độ tương tự nhỏ nhất giữa quỹ đạo T* với các quỹ đạo con thứ j của k tuyến đường. Tổng quát số lần thực hiện việc tìm d là: 𝑢𝑚𝑎𝑥 × 𝑢𝑚𝑎𝑥 × 𝑘, do vậy độ phức tạp tính toán của thuật toán ADB- STR là O(𝑢𝑚𝑎𝑥2 × 𝑘). 23 3.5. Thực nghiệm Nhằm kiểm chứng kỹ thuật đề xuất, chúng tôi tiến hành thực nghiệm, với bộ dữ liệu quỹ đạo do Piciarelli xây dựng năm 2008, và dữ liệu thu nhận từ các camera giám sát. Kết quả thực nghiệm cho thấy, kỹ thuật đề xuất có thể phát hiện bất thường ngay cả khi đối tượng chưa hoàn thành quỹ đạo chuyển động. Điều này rất có ý nghĩa khi áp dụng đối với hệ thống thực hiện trong chế độ thời gian thực. 3.6. Kết luận chương 3 Chương này, luận án đã đề xuất một kỹ thuật phát hiện bất thường dựa trên phân đoạn đường đại diện của tuyến đường. Kỹ thuật đề xuất dựa trên tính chất các tuyến đường có ảnh hưởng nhất định đối với đối tượng di chuyển trên tuyến đường đó. Bằng cách kết hợp giữa việc sử dụng độ đo tương tự và phân đoạn đường đại diện của mỗi tuyến đường, kỹ thuật đề xuất có thể phát hiện được bất thường ngay cả khi đối tượng