Về một phương pháp phát hiện đối tượng chuyển động

JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 122-130 This paper is available online at VỀ MỘT PHƯƠNG PHÁP PHÁT HIỆN ĐỐI TƯỢNG CHUYỂN ĐỘNG Nguyễn Văn Hùng Viện Vũ khí, Tổng cục Công nghiệp Quốc phòng Email: hungitd@yahoo.com Tóm tắt. Bài báo đề xuất phương pháp phát hiện đối tượng chuyển động trên cơ sở so sánh sự khác biệt giữa ba khung ảnh liên tiếp với nhau và có sự kết hợp với ảnh nền. Trong nội dung có đưa ra một số khái niệm định nghĩa mới về điểm chuyển động, đường và vùng chuyển động liên thông. Ngoài ra thuật toán cũng kế thừa các phép toán hình thái, thuật toán tính số vùng chuyển động liên thông. Cùng với thuật toán đề xuất trong nội dung có trình bầy thử nghiệm kết quả của thuật toán và được so sánh, đánh giá với các thuật toán có trước. Từ khóa: Điểm, đường, vùng chuyển động, vùng chuyển động liên thông. 1. Mở đầu Phát hiện và bám theo đối tượng chuyển động là bài toán được giới khoa học và công nghệ quan tâm nghiên cứu nhiều trong thời gian gần đây. Lí do đơn giản bài toán được ứng dụng rộng rãi trong các hệ thống giám sát bảo vệ, các hệ thống giám sát giao thông, các hệ thống phục vụ cho an ninh quốc phòng. Hiện nay có hai hướng tiếp cận chủ yếu để giải quyết bài toán này. Hướng thứ nhất, là sử dụng kĩ thuật trừ nền được giới thiệu ở các tài liệu [2, 3, 4, 10]; Hướng thứ hai, là sử dụng kĩ thuật xác định sự khác biệt giữa các ảnh liên tiếp được giới thiệu ở các tài liệu [6, 7, 8, 9]. Mặc dù các kĩ thuật này đã đạt được một số hiệu quả nhất định, song nó lại có một số lỗi trong các ứng dụng phát hiện đối tượng chuyển động, chẳng hạn nó chỉ ra được vùng chuyển động nhưng lại không đồng nhất được các điểm trên đối tượng chuyển động. Để khắc phục nhược điểm trên, bài báo đề xuất thuật toán kết hợp giữa kĩ thuật xác định sự khác biệt giữa các ảnh liên tiếp và kĩ thuật trừ nền. 2. Nội dung nghiên cứu 2.1. Một số khái niệm và định nghĩa 2.1.1. Ma trận mặt nạ chuyển động Xét dãyN ảnh (frame) trên tập video có kích thước w×h. Gọi Fk là ma trận cường độ xám của ảnh thứ k (k = 1..N), B là ma trận cường độ xám của ảnh nền. Không mất 122 Về một phương pháp phát hiện đối tượng chuyển động tính tổng quát giả sử B = F1. Trong thực tế ảnh nền có thể thay đổi theo thời gian vì vậy việc cập nhật nền theo qui tắc nào đó là rất cần thiết và được trình bầy ở phần thực nhiệm. Xác định ma trận Dk,k−1 như sau: Dk,k−1(i, j) = |Fk(i, j)− Fk−1(i, j)|; i = 1..w; j = 1..h. (2.1) Dk,B(i, j) = Dk, 1(i, j) = |Fk(i, j)−B(i, j)| (2.2) Trong đó i, j tương ứng là chỉ số hàng và cột của ma trận, nó cũng tương ứng với điểm ảnh P (i, j) trên ảnh thứ k. Ở điều kiện lí tưởng không có nhiễu (chẳng hạn camera đứng yên, cường độ ánh sáng không thay đổi...) thì điểm ảnh P (i, j) được coi là điểm chuyển động nếuDk,k−1(i, j) khác 0 và ngược lại sẽ được coi là điểm đứng yên. Trong thực tế giả thiết nêu trên khó thỏa mãn, vì vậy người ta có thể dùng một ngưỡng T , là số được xác định bằng thực nghiệm, tùy theo môi trường đặt camera để loại bỏ nhiễu. Từ ma trận Dk,k−1 và ngưỡng T đã xác định, ta xây dựng ma trậnMk,k−1 như sau: Mk,k−1 = { 1 → if(Dk,k−1(i, j) > T ) 0 → else (2.3) Tương tự như trên ta xây dựng ma trậnMk,B(i, j): Mk,B(i, j) = { 1 → if(Dk,B(i, j) > T ) 0 → else (2.4) Mk,k−1 được gọi là ma trận mặt nạ chuyển động ở thời điểm k. Nếu Mk,k−1(i, j) bằng 1 thì điểm ảnh P (i, j) tương ứng được coi là chuyển động so thời điểm trước đó và bằng 0 thì điểm ảnh P (i, j) được coi là đứng yên. - Đường chuyển động là đường chỉ đi qua các điểm chuyển động - Vùng chuyển động liên thông là vùng mà giữa hai điểm chuyển động bất kí tồn tại ít nhất một đường chuyển động . - Đối tượng Obj được coi là chuyển động nếu nó chứa ít nhất một vùng chuyển động liên thông. 123 Nguyễn Văn Hùng 2.1.2. Phép toán hình thái - Chúng ta gọi 8 phần tử lân cận của phần tử Mk,k−1(i, j) là láng giềng 8 của Mk,k−1(i, j). - Phép dãn nở (Dilation) Xét ma trậnMk,k−1, ta gọi việc xác định ma trận M theo (5) là phép dãn nở của ma trậnMk,k−1, kí hiệuM = Dila(Mk,k−1) M(i, j) = { 1, Nếu có ít nhất một láng giềng 8 củaMk,k−1(i, j) có giá trị 1 0, Nếu ngược lại (2.5) - Phép xói mòn (Erosion) Xét ma trận Mk,k−1, ta gọi việc xác định ma trận M theo (6) là phép xói mòn ma trậnMk,k−1, kí hiệuM = Eros(Mk,k−1) M(i, j) = { 0, Nếu có ít nhất một láng giềng 8 củaMk,k−1(i, j) có giá trị 0 1, Nếu ngược lại (2.6) Các phép toán Dila(Mk,k−1), Eros(Mk,k−1) được gọi là các phép toán hình thái của ma trận Mk,k−1. Phép toán hình thái được đề cập trong [2, 4]. Phép toán hình thái Dila(Mk,k−1),Eros(Mk,k−1) có tác dụng loại bỏ các vùng chuyển động không liên thông. Để minh họa hai phép toán hình thái trên ta có thể xem ví dụ minh hoạ: Đầu vào là một ma trận có chứa các các giá trị 1 và 0 thể hiện ở Hình 1.a. Sau khi thực hiện phép Dila kết quả ở Hình 1.b; khi thực hiện phép Eros kết quả thể hiện ở Hình 1.c; a b c Hình 1. Minh họa hai phép toán hình thái 124 Về một phương pháp phát hiện đối tượng chuyển động 2.1.3. Thuật toán tính số vùng chuyển động liên thông Thuật toán tính số vùng chuyển động liên thông theo sơ đồ khối tại Hình 1: kí hiệu là Count_V (M). Trong đó có hàm Min là hàm lấy giá trị nhỏ nhất trong 4 giá trị bên trong. Hình 3.a là ma trận đầu vào: ô trắng là giá trị 1, ô đen giá trị 0; Hình 3.b là kết quả sau khi chạy thuật toán tính vùng chuyển động liên thông; Quá trình đánh nhãn và đếm số vùng chuyển động được trình bầy ở trên cho thấy khi ta thực hiện các thuật toán trên với ma trận mặt nạ chuyển động thì ta tách được các cùng chuyển động có các nhãn tương ứng. Ví dụ ở trên có hai vùng chuyển động tương ứng. Hình 2. Thuật toán tính vùng chuyển động a b Hình 3. Ví dụ minh họa thuật toán ở Hình 1 125 Nguyễn Văn Hùng 2.2. Thuật toán xác định vùng chuyển động Căn cứ vào những định nghĩa trên, chúng tôi đề xuất thuật toán mới phát hiện chuyển động trong frame hiện tại dựa trên thông tin khác biệt giữa 2 frame liền trước và frame liền sau nó, cùng với thông tin frame nền được thể hiện theo 5 bước sau: • Bước 1. Xét frame thứ k áp dụng công thức (2.3) tính:Mk,k−1;Mk,k+1. • Bước 2. Áp dụng công thức (2.4) tínhMk,B . • Bước 3. Xác định ma trậnMotionk theo công thức (2.7): Motionk = (Mk,BANDMk,k−1) OR (Mk,BAND Mk,k+1) (2.7) • Bước 4. Thực hiện các phép toán: Dila(Motionk), Eros(Motionk), Vk = Count_V (Motionk). Vk là số vùng chuyển động liên thông. • Bước 5. Tại mỗi vùng, xác định cặp điểm có toạ độ lớn nhất (max) và nhỏ nhất (min). Từ cặp điểm min, max ta vẽ hình chữ nhật bao quanh vùng chuyển động. Kí hiệu là DrawRec(Motionk). 2.3. Sơ đồ khối thể hiện thuật toán đề xuất Kết hợp các phần trình bầy ở trên, ta có sơ đồ thuật toán phát hiện chuyển động trong một file video thể hiện ở Hình 4 dưới đây. 2.4. Kết quả thử nghiệm 2.4.1. Dữ liệu đầu vào thử nghiệm Dữ liệu quay tại đường Hoàng Quốc Việt thành phố Hà Nội vào các buổi sáng ngày thường. Dữ liệu dạng file AVI, chuẩn nén Cinepak Codec; Bit Rate 64 Kbps; kích thước 640× 480; thời lượng mỗi đoạn video khoảng 60 giây. 2.4.2. Một số kĩ thuật xử lí trong thực nghiệm - Tiền xử lí: + Chuyển ảnh về ảnh xám theo công thức: Ảnh xám= 0.3×R+0.59×G+0.11×B (R,G,B là ba gam mầu của ảnh mầu). + Thay đổi độ phân giải từ: 640 × 480 thành ảnh có độ phân giải 160× 120. Bằng cách tính trung bình cộng bốn điểm hàng xóm thành một điểm. - Ngưỡng T trong thực nghiệm chọn giá trị từ 25 đến 35. - Cập nhật lại nền: B = Fk nếu tổng giá trị các phần tử trong ma trận mặt nạMb,k nhỏ hơn 5% độ lớn của ảnh (w × h). 126 Về một phương pháp phát hiện đối tượng chuyển động Hình 4. Sơ đồ khối thuật toán phát hiện chuyển động đề xuất. 2.4.3. Kết quả thử nghiệm Với dữ liệu trên chúng tôi phân biệt được các đối tượng chuyển động và đánh số theo thứ tự từ 1 đến n. Chương trình thử nghiệm đã xử lí tốt được việc loại bỏ được các chuyển động không cần thiết như chuyển động của lá cây, các chuyển động nhỏ. Điểm còn tồn tại của thuật toán là: với các cảnh quay chứa khung ảnh chuyển động có vùng chồng lấn thì chương trình không tách được thành hai chuyển động riêng biệt mà gộp lại thành một khối đối tượng chuyển động. 127 Nguyễn Văn Hùng 2.4.4. Một số hình ảnh minh hoạ của chương trình Hình 5. Khung hình hiện tại và nền được cập nhật tương ứng của video1 Hình 6. Khung hình hiện tại và nền được cập nhật tương ứng của video2 Hình 7. Khung hình hiện tại và nền được cập nhật tương ứng của video 103 khi có chồng lấn 128 Về một phương pháp phát hiện đối tượng chuyển động 2.4.5. Bảng thống kê kết quả thử nghiệm giữa ba thuật toán Trong thử nghiệm chúng tôi chạy cùng dữ liệu trên 100 đoạn file AVI khác nhau với 3 thuật toán: 1. Thuật toán đề xuất; 2. Thuật toán trừ nền; 3. Thuật toán kết hợp của chúng tôi. Hình 7 thể hiện kết quả của các thử nghiệm này. Hình 8. Biểu đồ so sánh tỉ lệ phát hiện đúng của ba thuật toán 3. Kết luận Bài báo đề xuất phương pháp phát hiện đối tượng chuyển động trên cơ sở so sánh sự khác biệt giữa ba khung ảnh liên tiếp với nhau và có sự kết hợp với ảnh nền. Trong nội dung có đưa ra một số khái niệm định nghĩa mới về điểm chuyển động, đường và vùng chuyển chuyển động liên thông. Ngoài ra thuật toán cũng kế thừa các phép toán hình thái, thuật toán tính số vùng chuyển động liên thông. Bài báo trình bày thử nghiệm với việc phát hiện và đánh dấu các phương tiện tham gia giao thông, cũng như so sánh kết quả gữa các thuật toán truyền thống với thuật toán đề xuất. TÀI LIỆU THAM KHẢO [1] A.M. Tekalp, 1955. Digital Video Processing. Prentice Hall. [2] LIU Ya, AI Haizon, XU Guangyou, 2001. Moving Object Detection and Traching Based on Background Subtraction. [3] Chris Stauffer, W.E.L Grimson. Adaptive background mixture models for real-time tracking. [4] Liyuan Li, Weimin Huang, Irene Y.H. Gu, Qi Tian, 2003. Foreground Object Detection from Videos Containing Complex Background. 129 Nguyễn Văn Hùng [5] Pierre Soille, Morphological Image Analysis: Principles and Applications. Springer-Verlag New York, Inc. Secaucus, NJ, USA c©2003. [6] Y. LIU, A. HAIZHO, X. GUANGYOU, 2001. Moving object detection and tracking based on background subtraction. Proceeding of Society of Photo-Optical Instrument Engineers (SPIE), 4554, pp. 62-66. [7] C. WREN, A. AZARBAYEJANI, T. DARELL, A. PENTLAND, 1997. Pfinder: Real-time tracking of the human body, IEEE Trans. Pattern Analysis and Machine Intelligence, 19, pp. 780–785. [8] N. A. OGALE. A survey of techniques for human detection from video. Department of Computer Science, University of Maryland, College Park. [9] W. ABD-ALMAGEED, M. HUSSEIN, M. ABDELKADER, L. DAVIS, 2007. Real-Time Human Detection and Tracking from Mobile Vehicles, Proc of 2007 IEEE Intel. Transportation Systems Conf., Seattle, USA, Sept.30-Oct.3, pp. 149-157. [10] Marwa abd el Azeem Marzouk, 2010. Modified background subtraction algrorithm for motion detection in surveillance systems. Vol. 1, No. 2, pp.112-123. ABSTRACT A moving object detection method based on comparing the differences and background subtraction This paper proposed methods of detecting moving objects based on comparing differences between three consecutive frames, combined with the background image. Content has given a new definition of concept point motion, sugar and the shifting joint motion. The algorithm also inherits the mathematical morphology, the algorithm of the cross-motion. Along with the proposed algorithm in the content are presented test results of the algorithm and a comparison and evaluation of the algorithm. 130