Bài toán nhận dạng đối tượng chuyển động trong video

- 4 - Chương 2 - BÀI TOÁN NHẬN DẠNG ĐỐI TƯỢNG CHUYỂN ĐỘNG TRONG VIDEO 2.1 - Một số khái niệm 2.1.1 - Cấu trúc Video Video được cấu thành từ một tập liên tiếp các khung hình - frame, còn được gọi là ảnh, ghi nhận lại các hình ảnh quan sát được của các sự kiện xảy ra trong một khoảng thời gian. Có hai dạng tín hiệu video thông dụng là: tín hiệu tuần tự (analog) và tín hiệu video số (digital). Luận văn này sử dụng dữ liệu hình ảnh thu nhận từ Camera, nên chúng ta chỉ xem xét đến video được biểu diễn dưới dạng số và bỏ qua phần tín hiệu âm thanh của video. Mô hình cấu trúc một chuỗi video bao gồm các thành phần sau (Hình 2 - 1): • Frame - khung hình là thành phần cơ bản trong chuỗi video. Mỗi khung hình tương ứng với một ảnh trong thế giới thực tại một thời điểm xác định. • Shot là một dãy các khung hình liên tiếp được camera ghi nhận không có sự ngắt quãng nào xảy ra. Shot là một đơn vị cơ bản để xây dựng phân tích nội dung video. • Các shot liên tiếp nhau được kết hợp lại thành một cảnh (scene) dựa trên nội dung. • Tất cả các scene tạo thành một chuỗi video. - 5 - Video Scenes Shots Frame Hình 2 - 1: Mô hình cấu trúc của Video [1] 2.1.2 - Key - frame Key - frame là một đặc trưng tóm tắt được dùng để mô tả nội dung nổi bật, chính yếu của một chuỗi Video, nó được xem như là một đại diện của một chuỗi những khung hình liên tục trong một thời gian của Video. Các frame khác và key - frame có sự khác nhau nhỏ hơn một ngưỡng cho trước. Việc truy xuất và chỉ mục hóa Video thường rất hay sử dung key - frame vì nó có khả năng giảm được một lượng dữ liệu lớn trùng lắp trong Video. Có nhiều phương pháp xác định key - frame khác nhau, nhưng chúng tựu chung dựa trên sự so sánh ảnh của từng cặp khung hình. 2.2 - Tổng quan về phương pháp phát hiện đối tượng chuyển động trong video dựa vào phân đoạn ảnh Có rất nhiều khái niệm khác nhau về phân đoạn video [2] [4] [5] [6] [7] [9] [10] [11]. Tổng quát, phân đoạn video là một quá trình chia một chuỗi các khung hình thành các vùng ngữ nghĩa sao cho mỗi vùng có thể được xem như một đối tượng ngữ nghĩa độc lập. - 6 - frame 0 frame 7 frame 14 frame 21 frame 28 (a) Ảnh gốc frame 0 frame 7 frame 14 frame 21 frame 28 (b) Kết quả phân đoạn Hình 2 - 2: Minh họa kết quả phân đoạn video [1] Có hai hình thức phân đoạn video: phân đoạn theo thời gian và phân đoạn theo không gian. Mục đích của phân đoạn theo thời gian là để xác định các vùng trong khung hình mà ở đó xảy ra sự di chuyển của các đối tượng. Phân đoạn theo không gian mục đích là để chia khung hình thành các vùng ngữ nghĩa theo một tiêu chuẩn cho trước. Một vài đặc trưng thông dụng được sử dụng để đưa ra các tiêu chuẩn trong phân đoạn theo không gian như sự di chuyển, màu sắc, kết cấu, các tính chất hình học... [4] [7] Các đặc trưng khác nhau và chuẩn đồng nhất khác nhau dẫn đến kết quả khác nhau trên cùng một dữ liệu. Chẳng hạn, phân đoạn dựa trên màu, phân đoạn dựa trên cấu trúc [7], phân đoạn dựa trên sự di chuyển thường có kết quả các bản đồ phân đoạn khác nhau. • Phân đoạn dựa trên màu sử dụng bản đồ màu hoặc các kĩ thuật phân tích đặc trưng trong không gian màu để chia khung hình thành các vùng đồng nhất về màu. Tiếp theo là quá trình trộn vùng dựa trên thông tin di chuyển từ sự ước lượng di chuyển. • Phân đoạn di chuyển (hay còn được gọi là phân đoạn dòng sáng) là phương pháp phân đoạn bằng cách phân lớp các điểm ảnh trong mỗi khung hình thành các nhóm sao cho các điểm ảnh thuộc cùng một nhóm sẽ có sự di chuyển giống nhau. Những nhóm này có thể có hoặc không có ngữ nghĩa. - 7 - Sau đó, các nhóm này được trộn lại dựa trên thông tin di chuyển có được từ thao tác ước lượng di chuyển. • Ước lượng di chuyển (motion estimation) là quá trình xác định mức độ di chuyển của các điểm ảnh trong khung hình. • Phát hiện sự di chuyển (motion detection) là quá trình xác định các điểm ảnh có sự di chuyển bề mặt. So với phân đoạn dựa trên sự di chuyển, phát hiện di chuyển xác định các đường biên tốt hơn và chi phí tính toán thấp hơn. • Phát hiện sự thay đổi (change dectection) là một công cụ phân đoạn theo thời gian nhằm mục đích xác định các thay đổi trong một tập hay một chuỗi ảnh tại hai thời điểm khác nhau. Phát hiện thay đổi sẽ phân chia mỗi khung hình thành hai vùng: thay đổi và không thay đổi trong trường hợp camera đứng yên hoặc vùng thay đổi toàn cục và vùng thay đổi cục bộ trong trường hợp camera di chuyển. Trong trường hợp camera đứng yên thì vùng không đổi được xem là khung hình nền, vùng thay đổi được xem là ảnh bề mặt và nó chứa các đối tượng mà ta cần xác định. Trong trường hợp camera di chuyển tạo ra sự di chuyển toàn cục, chúng ta phải ước lượng chính xác sự di chuyển của camera. Sau khi ước lượng, ta áp dụng phương pháp phát hiện thay đổi như trong trường hợp camera đứng yên. • Kết hợp các phương pháp trên để thống kê được hình nền tĩnh của khung cảnh. Từ đó sẽ dễ dàng nhận ra được các đối tượng chuyển động. Phương pháp này dựa trên một ý tưởng đơn giản là một phân đoạn ảnh ở trong trạng thái tĩnh trong một khoảng thời gian đủ lâu, thì sẽ được xem như là thành phần của hình nền. • Thông tin di chuyển là một trong những thành phần chính, là đặc trưng quan trọng được sử dụng để phân đoạn video. Lý do là: o Sự di chuyển mang nhiều thông tin về các mối quan hệ không gian - thời gian giữa các đối tượng trong khung hình. o Các tính chất ảnh như cường độ và màu, có một sự tương quan rất cao theo hướng di chuyển, chúng không thay đổi nhiều khi được theo dõi - 8 - trong cảnh (ví dụ màu của chiếc xe không thay đổi khi nó di chuyển qua cảnh), và được dùng để loại bỏ thông tin dư thừa theo thời gian. Để phân đoạn di chuyển hay phân đoạn màu, đòi hỏi chúng ta phải thực hiện ước lượng di chuyển trong khung hình, chi phí để thực hiện quá trình này là tương đối cao và thao tác phức tạp. Trong khi quá trình phát hiện di chuyển có chi phí tính toán thấp hơn nhưng có độ chính xác về không gian cao. Do đó phương pháp phân đoạn dựa trên sự phát hiện thay đổi để rút trích các đối tượng ngữ nghĩa trong chuỗi video đã được áp dụng phổ biến hơn. Luận văn này chỉ tập trung xét phương pháp phân đoạn dựa trên quá trình phát hiện thay đổi, kết hợp với phương pháp thống kê khung hình nền trong quá trình thay đổi. 2.3 - Thuật toán phát hiện đối tượng chuyển động Chương này trình bày về các phương pháp cơ bản phát hiện các đối tượng chuyển động trong một đoạn phim video. Bài toán này bao gồm 4 bước chính: • Rút trích đặc trưng của ảnh. • Phân tích các đặc trưng. • Nhận biết các đối tượng chuyển động. • Lọc nhiễu. • Thống kê khung hình nền. 2.3.1 - Lý thuyết cơ bản trong phát hiện chuyển động Phát hiện chuyển động là một kỹ thuật được dùng nhiều trong các ứng dụng liên quan tới ảnh, đó là các hệ thống video giám sát, các ứng dụng đa phương tiện... Về cơ bản, phát hiện chuyển động là một quá trình xác định sự khác nhau về trạng thái của các đối tượng bằng cách quan sát chúng tại các thời điểm khác nhau. Ví dụ, các camera an ninh sẽ theo dõi và phát hiện có kẻ đột nhập khi thấy có sự thay đổi của hình ảnh. - 9 - Các kĩ thuật phát hiện chuyển động khác nhau có thể được sử dụng trong điều kiện camera chuyển động hay cố định. Với camera chuyển động, thuật toán phải tính toán để xác định các điểm ảnh có cùng vector chuyển động so với vector mẫu sẽ được coi là cố định. Với camera cố định, việc phát hiện chuyển động sẽ đơn giản hơn, đó là xác định khung hình nền cố định và các đối tượng chuyển động. Trong luận văn này, bài toán được áp dụng cho một camera đứng yên. Phát hiện chuyển động là một công việc phân đoạn về thời gian nhằm mục đích xác định các chuyển động trong các tập khung hình hay trong một chuỗi khung hình tại hai thời điểm khác nhau. Chúng ta ký hiệu ma trận ảnh cần kiểm tra là Mi tại khung hình t với: Mi = Fi(x, y, t). Trong đó: • Fi là hàm lấy các giá trị của ảnh. • x, y là tọa độ của điểm ảnh. • t chỉ ra khung hình thứ t trong chuỗi hình ảnh video. Bài toán phát hiện chuyển động bao gồm việc tìm kiếm đối với từng khung hình t một ma trận nhị phân Mo trong đó các điểm ảnh sẽ chứa giá trị biểu thị cho việc điểm ảnh (x, y) trong Mi có chuyển động so với khung hình đối chiếu Mis. Ma trận Mo với hàm xác định Fo(x, y, t) được định nghĩa như sau: nếu xảy ra sự thay đổi tại vị trí (x, y) tại thời điểm t ngược lại Mo = ⎩⎨ ⎧= 0 1 ),,( tyxFo Trong đó: • Mi: Ma trận điểm ảnh của khung hình hiện thời t với hàm giá trị Fi(x, y, t). • Mis: Ma trận điểm ảnh của khung hình đối chiếu s với hàm giá trị Fi(x, y, s), thông thường khung hình đối chiếu là khung hình nền. Có nhiều phương pháp khác nhau để xây dựng ma trận Mo. Hàm Fo được dùng để xây dựng ma trận Mo được định nghĩa như sau: - 10 - Fo(x, y, n) = F( Fi(x, y, t), Fi(x, y, s)) Phát hiện chuyển động là một phương pháp được sử dụng trong hầu hết các ứng dụng xử lý ảnh video. Về cơ bản, thuật toán phát hiện chuyển động bao gồm bốn bước chính: • Rút trích đặc trưng. • Phân tích đặc trưng. • Nhận biết chuyển động. • Lọc nhiễu. Sơ đồ khối của phương pháp được trình bày trong Hình 2 - 3. Phân tích đặc trưng (Fc) Rút trích đặc trưng (Fa) Mi Nhận biết chuyển động (Fo) Lọc nhiễu (Ff) Ma Mc Mo M’ Hình 2 - 3: Sơ đồ khối phương pháp phát hiện chuyển động Rút trích đặc trưng Đây là bước lấy các thông số của các điểm ảnh tại từng khung hình biến đổi thành một ma trận chứa các giá trị. Phép biến đổi này thường là hàm Fa với các tham số là độ sáng, màu sắc... Ma trận đặc trưng Ma được định nghĩa như sau: Ma = Fa(x, y, t) = F(Fi(x, y, t)) Phân tích đặc trưng Đây là bước quan trọng để xác định độ sai khác của khung hình hiện thời với khung hình nền mẫu. Kết quả là một ma trận Mc chứa các sai khác giữa 2 khung hình. Hàm tính khoảng cách Fc giữa 2 giá trị đặc trưng thường là phép trừ bậc một. Hàm Fc được định nhĩa như sau: Fc(x, y, t) = F(Fa(x, y, t), Fa(x, y, s)) Trong đó: - 11 - • Fa(x, y, t): Giá trị đặc trưng của điểm ảnh (x, y) tại khung hình hiện thời t. • Fa(x, y, s): Giá trị đặc trưng của điểm ảnh (x, y) tại khung hình đối chiếu s. Nhận biết chuyển động Từ kết quả của bước phân tích đặc trưng, thuật toán sẽ nhận biết các điểm ảnh nào là đứng yên, điểm ảnh nào là chuyển động so với khung hình nền mẫu. Kết quả của bước phân tích này là một ma trận Mo chứa các giá trị nhị phân: chuyển dộng hay không chuyển động. Hàm nhận biết chuyển động Fo này thường là phép so sánh giá trị của Mc với một ngưỡng Kt, ngưỡng này thường là ngưỡng thực nghiệm. Fo được định nghĩa như sau: nếu Mc(x, y, n) > Kt ngược lại ⎩⎨ ⎧= 0 1 ),,( tyxFo Lọc nhiễu Lọc nhiễu là bước lọc bỏ các nhiễu trong kết quả có được, nhiễu này thường là nhiễu của camera hay nhiễu trong quá trình rút trích đặc trưng và nhận biết chuyển động. Đơn giản là lọc bỏ các vùng chuyển động có bao đóng nhỏ hơn một ngưỡng thực nghiệm nào đó. 2.3.2 - Chi tiết thuật toán phát hiện chuyển động Dựa trên lý thuyết cơ bản được trình bày ở trên, trong mục này tôi sẽ trình bày chi tiết về thuật toán phát hiện chuyển động. Mô hình của thuật toán như sau (Hình 2 - 4) - 12 - Phân tích đặc trưng Nhận biết chuyển động Khung hình hiện thời Tổng hợp khung hình nền Khung hình đối chiếu Rút trích đặc trưng (Fa) Đo khoảng cách đặc trưng (Fc) Lọc nhiễu (Ff) Vùng chuyển động Lấy ngưỡng Nhận biết chuyển động (Fo) Hậu xử lý Rút trích đặc trưng Hình 2 - 4: Mô hình thuật toán phát hiện chuyển động - 13 - 2.3.2.1 - Rút trích đặc trưng Đây là quá trình chuyển đổi từ ma trận ảnh đầu vào Fi(x, y, t) thành ma trận chứa các giá trị đặc trưng. Kết quả của bước rút trích đặc trưng là một chuỗi các ma trận Ma(x, y, t). Các đặc trưng cơ bản: • Cường độ sáng. • Màu sắc. • Độ chiếu sáng. • Độ tương phản. Chương trình thực nghiệm lấy thông tin cường độ sáng từ mỗi thành phần của khung hình thông qua thuật toán được trình bày ở Phụ lục 1. 2.3.2.2 - Cường độ sáng Đây là đặc trưng cơ bản và thường được dùng nhất trong phát hiện chuyển động. Đối với camera đơn sắc thì chuỗi ảnh đầu vào Mi(x, y, t) chính là chuỗi các ma trận chứa các giá trị độ sáng. Trường hợp camera màu gồm 3 thành phần màu cơ bản (RGB), độ sáng sẽ được tính theo công thức sau: Fa(x, y) = W1R(x, y) + W2G(x, y) + W3B(x, y) Trong đó: • Wi là các trọng số mô tả cho các độ nhạy khác nhau của hệ thống HVS đối với các thành phần màu. • R(x, y), G(x, y), B(x, y) là 3 giá trị màu của điểm ảnh (x, y). Chương trình thực nghiệm dùng cường độ sáng làm đặc trưng để phát hiện chuyển động. Tham khảo source code ở phần Phụ lục 2. 2.3.2.3 - Màu sắc Đây là đặc trưng quan trọng thứ hai, màu sắc được lấy từ ba bộ cảm biến của camera (RGB). Trong một số ứng dụng đặc thù, màu sắc của đối tượng chuyển động sẽ mang một ngữ nghĩa riêng. - 14 - 2.3.2.4 - Đặc trưng bất biến về độ chiếu sáng Khi độ chiếu sáng thay đổi, các phương pháp truyền thống dựa trên cường độ sáng của ảnh không thể phát hiện chuyển động do các dao động của các giá trị cường độ sáng tạo ra các xác thực sai. Vấn đề này có thể được khắc phục bằng cách sử dụng các đặc trưng bất biến khi độ chiếu sáng thay đổi, còn được gọi là các đặc trưng bất biến của độ chiếu sáng. Các đường mức, các bản đồ cạnh, mô tả vector của các vùng ảnh là các đặc trưng có tính chặt chẽ cao hơn so với đặc trưng cường độ sáng của ảnh trong việc phát hiện chuyển động ở trường hợp độ chiếu sáng thay đổi. Phương pháp dựa trên sự biểu diễn ảnh đường mức sử dụng yếu tố sự thay đổi về độ chiếu sáng toàn cục làm biến đổi về số lượng, nhưng không thay đổi tính chất hình học của các đường mức. Một đường mức λ là một đường biên của tập mức. Một tập mức Sλ bao gồm tất cả các vị trí điểm ảnh có giá trị độ sáng ít nhất bằng λ: }),,(:),{( λλ ≥= tyxFayxS Ảnh chứa các đường mức có thể được diễn đạt như một bản đồ đường mức, Fa(x, y, t). Một bản đồ đường mức có thể được định nghĩa như sau: nếu Fa(x, y, t) = λi với i = 1,..., N ngược lại ⎩⎨ ⎧= 0 1 ),,( tyxFa Trong đó: • N là số lượng đường mức được xét để tạo bản đồ đường mức. 2.3.3 - Phân tích đặc trưng Phần này trình bày về thuật toán tính toán ma trận khác biệt giữa khung hình hiện thời và khung hình nền mẫu. Đồng thời cũng xin trình bày thuật toán lấy khung hình đối chiếu. 2.3.3.1 - Kỹ thuật lấy khung hình đối chiếu. Xác định khung hình đối chiếu là một bước rất quan trọng ảnh hưởng tới kết quả của thuật toán. Có 2 phương pháp xác định khung hình đối chiếu: cố định và động. Chương trình thực nghiệm dùng phương pháp lấy khung hình đối chiếu động. - 15 - 2.3.3.2 - Phương pháp xác định khung hình đối chiếu cố định Trong phương pháp xác định khung hình đối chiếu cố định, khung hình nền được chụp trước trong những thời điểm khác nhau với những điều kiện khác nhau. Các khung hình nền này sau đó sẽ được dùng để so sánh trong những điều kiên cụ thể. Ví dụ trời sáng thì dùng khung hình nền sáng, trời tối, trời mưa thì dùng khung hình nền khác… Đây là một phương pháp đơn giản, nó cho phép phát hiện các đối tượng trong cảnh ngay cả khi đối tượng đứng yên. Hơn nữa, nó làm giảm các hiệu ứng khung hình nền không bị bao phủ và cải tiến việc phát hiện các đối tượng chuyển động chậm. 2.3.3.3 - Phương pháp xác định khung hình đối chiếu động Trong phương pháp xác định khung hình đối chiếu động, khung hình đối chiếu sẽ được xác định trong một tập các khung hình vừa xảy ra. Có nhiều phương pháp lấy khung hình đối chiếu động, về cơ bản có hai phương pháp sau: Phương pháp lấy khung hình đối chiếu là khung hình ngay phía trước: Fc(x, y, n) = T(Mi(x, y, t), Mi(x, y, t - 1)) Phương pháp này có ưu điểm là làm giảm sự phát hiện các bóng. Tuy nhiên, nó tạo ra nhiễu cho phần khung hình nền không bị bao phủ bởi đối tượng chuyển động, chỉ nhận được vùng biên của đối tượng chuyển động chứ không nhận được hoàn toàn đối tượng. Một hạn chế nữa là phương pháp này phát hiện các vùng ảnh chuyển động chậm kém. Một cải tiến đưa ra là chuẩn hóa khung hình Mi(x, y, t - 1) (khung hình trước đó) trước khi so sánh. Bước tối ưu này sẽ chuẩn hóa sự biến đổi bên trong ảnh chịu tác động bởi các yếu tố môi trường. Phương pháp sử dụng khung hình nền làm khung hình đối chiếu: Thông thường thì khung hình đầu tiên của chuỗi video sẽ được chọn để làm khung hình đối chiếu, phương pháp này giả thiết rằng không có các đối tượng bề mặt trong cảnh lúc bắt đầu chuỗi video. Khi đó hàm khác biệt có dạng: Fc(x, y, t) = F(Fa(x, y, t), Fa(x, y, 0)) - 16 - Trong đó: • Fa(x, y, t) là giá trị đặc trưng của điểm ảnh (x, y) tại khung hình hiện thời t. • Fa(x, y, 0) là giá trị đặc trưng của điểm ảnh (x, y) tại khung hình đầu tiên t = 0. Hình 2 - 5: Ví dụ mô tả phương pháp đối chiếu khung hình nền [10] Đây là một phương pháp đơn giản, gần giống như phương pháp lấy khung hình đối chiếu là khung hình nền cố định. Tuy nhiên, lời giải này không phải luôn phù hợp với thực tế. Vì trong nhiều ứng dụng, khung hình đầu tiên của chuỗi thường chứa đối tượng bề mặt. Và nó sẽ không thích hợp trong trường hợp chuỗi video dài như bài toán điều khiển nút giao thông mà luận văn này đang nhắm đến. Có nhiều thuật giải được đưa ra để xây dựng lại khung hình đối chiếu bằng cách tích hợp thông tin khung hình nền từ một chuỗi các khung hình, các kĩ thuật này còn được gọi là phương pháp lấy khung hình nền phù hợp hoàn cảnh (adaptive background). Một vùng nhớ của khung hình nền sẽ lưu giữ khung hình nền đã được cập nhật (updated - background) trong quá trình phát hiện chuyển động. Một bộ lọc về thời gian sẽ tích hợp thông tin từ các khung hình trong quá khứ để cập nhật khung hình nền này. Khung hình nền động trong bộ nhớ này sẽ được dùng trong phép so sánh với khung hình hiện thời để phát hiện các vùng chuyển động. Ma trận giá trị đặc trưng của khung hình nền Fa(x, y, t) = F’a(x, y, t) là kết quả của trung bình trọng số các khung hình trong quá khứ: F’a(x, y, t) = (1 - α)Fa(x, y, t) + α F’a(x, y, t - 1) - 17 - Với F’a(x, y, 0) = Fa(x, y, 0) và 0 < α < 1. Giá trị α có thể được xác định dựa trên kết quả thống kê trong một cửa sổ các điểm ảnh trong chuỗi khung hình. Trong trường hợp đơn giản hơn giá trị α là một hằng số. Chỉ những điểm ảnh không bị chuyển động mới thật sự được cập nhật. Quá trình cập nhật sẽ tạo ra một khung hình nền cho dù chuỗi ảnh có các đối tượng khác đang nằm trên nền, tức là nền bị bao phủ bởi các đối tượng di động khác. Với khung hình đối chiếu được cập nhật động sẽ khắc phục việc thay đổi khung hình nền khi các điều kiện thời tiết và ánh sáng thay đổi. Một nhược điểm của phương pháp này là bóng của các đối tượng chuyển động (shadow) cũng được xem như một đối tượng chuyển động. Giải pháp để khắc phục khuyết điểm này sẽ được giải quyết trong phần mở rộng. 2.3.3.4 - So sánh kết quả hai phương pháp sử dụng khung hình đối chiếu: Hình 2 - 6: Khung hình có đối tượng đang di chuyển - 18 - Hình 2 - 7: Kết quả theo phương pháp đối chiếu khung hình trước đó Hình 2 - 8: Ảnh nền Hình 2 - 9: Kết quả theo phương pháp đối chiếu với khung hình nền cập nhật động - 19 - Trong trường hợp này, kết quả nhận được bằng phương pháp sử dụng khung hình nền làm khung hình đối chiếu tốt hơn so với phương pháp sử dụng khung hình trước đó. Tuy nhiên với phương pháp sử dụng khung hình nền cố định, nếu trường hợp khung hình nền có chứa đối tượng đang di chuyển vào thời điểm bắt đầu thì hiệu quả sẽ không cao hơn so với phương pháp dùng khung hình nền động. Trong hai phương pháp sử dụng khung hình nền động, phương pháp sử dụng khung hình trước đó làm khung hình đối chiếu có kết quả không tốt bằng phương pháp sử dụng khung hình nền được cập nhật động. Ngoài ra phương pháp sử dụng khung hình n