Luận Văn Thạc Sĩ Về Thuật Toán Phát Hiện Chuyển Động

Khóa luận đánh giá Thuật Toán Phát Hiện Chuyển Động Trong Luận Văn Thạc Sĩ, tiếp cận đa chiều, kết quả có tính khả thi cao trong lĩnh vực chuyên ngành

• Tác giả: Đào Ngọc Anh
• Người hướng dẫn: PGS. Ngô Diên Tập
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ Điện tử - Viễn thông
• Đề tài: Thuật Toán Phát Hiện Chuyển Động
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2010
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: THUẬT TOÁN PHÁT HIỆN CHUYỂN ĐỘNG
• 1.1. Bộ lọc Kalman
• 1.2. Mô hình hỗn hợp nền thích nghi thời gian thực
• 1.3. Mô hình không tham số thích nghi
• 1.3.1. Mô hình nền cơ bản
• 1.3.2. Ước lượng độ rộng lõi
• 1.3.3. Giảm các phát hiện sai
• 1.3.4. Cập nhật nền
• 1.3.5. Phát hiện vùng tối
• 1.4. Mô hình từ điển thích nghi thời gian thực
• 1.4.1. Mô hình nền và phát hiện nền
• 1.4.2. Phát hiện vật thể từ nền
• 1.4.3. So sánh mô hình sử dụng từ điển với các mô hình khác
• 1.4.4. Mô hình nền sử dụng từ điển phân lớp
• 1.4.5. Mô hình từ điển hai lớp thích nghi thời gian thực
• 1.4.5.1. Mô hình từ điển cơ bản
• 1.4.5.2. Thuật toán tách nền
• 2. CHƯƠNG 2: THƯ VIỆN CHƯƠNG TRÌNH XỬ LÝ ĐỒ HỌA OPENCV
• 2.1. Kiến trúc của thư viện
• 2.1.1. Cấu trúc dữ liệu khởi thủy
• 2.1.2. Thư viện người dùng đồ họa mức cao
• 2.1.3. Các khái niệm cần thiết trong cài đặt mô hình nền sử dụng từ điển
• 2.1.3.1. Không gian nhớ
• 2.1.3.2. Dãy đối tượng liên kết
• 2.1.4. Theo dõi chuyển động
• 3. CHƯƠNG 3: CÀI ĐẶT MÔ HÌNH NỀN SỬ DỤNG TỪ ĐIỂN HAI LỚP
• 3.1. Cấu trúc dữ liệu
• 3.2. Giải thuật thực hiện mô hình hóa nền sử dụng từ điển hai lớp thích nghi
• 3.2.1. Pha khởi tạo mô hình nền M
• 3.2.2. Pha tối ưu mô hình nền M đã xây dựng
• 3.2.3. Pha tách nền, cập nhật mô hình M và H đồng thời
• 3.3. Phân tích thông tin chuyển động
• DANH MỤC HÌNH VẼ
• BẢNG KÝ HIỆU VIẾT TẮT

Tóm tắt

I. Thuật Toán Phát Hiện Chuyển Động

Thuật toán phát hiện chuyển động là một lĩnh vực quan trọng trong công nghệ nhận diện hình ảnh và video. Các phương pháp này thường được áp dụng trong nhiều lĩnh vực như giám sát an ninh, theo dõi chuyển động và phân tích hành vi. Đặc biệt, việc sử dụng công nghệ nhận diện và machine learning đã giúp cải thiện đáng kể độ chính xác và hiệu suất của các thuật toán này. Các thuật toán phát hiện chuyển động thường dựa trên việc mô hình hóa nền, cho phép phân tách các đối tượng chuyển động khỏi nền tĩnh. Việc áp dụng hình ảnh và video trong nghiên cứu này không chỉ giúp nâng cao chất lượng phát hiện mà còn mở ra nhiều ứng dụng thực tiễn trong cuộc sống hàng ngày.

1.1 Bộ lọc Kalman

Bộ lọc Kalman là một trong những thuật toán nổi bật trong lĩnh vực phát hiện chuyển động. Được giới thiệu vào năm 1960, bộ lọc này cho phép ước lượng trạng thái của hệ thống trong điều kiện có nhiễu. Với các giả thiết về tính tuyến tính và ồn trắng, bộ lọc Kalman có khả năng kết hợp thông tin từ nhiều phép đo khác nhau để đưa ra ước lượng chính xác hơn. Điều này rất quan trọng trong việc theo dõi chuyển động của các đối tượng trong video, nơi mà các phép đo có thể bị ảnh hưởng bởi nhiều yếu tố khác nhau. Việc sử dụng bộ lọc Kalman giúp cải thiện độ chính xác trong việc phát hiện chuyển động và theo dõi các đối tượng trong thời gian thực.

1.2 Mô hình hỗn hợp nền thích nghi thời gian thực

Mô hình hỗn hợp nền thích nghi là một phương pháp tiên tiến trong phát hiện chuyển động. Phương pháp này cho phép mô hình hóa mỗi điểm ảnh như một hỗn hợp của nhiều thành phần, mỗi thành phần được biểu diễn bằng một phân bố Gauss. Điều này giúp hệ thống có khả năng thích nghi với các thay đổi về độ sáng và các đối tượng chuyển động phức tạp. Hệ thống này có thể hoạt động hiệu quả trong các điều kiện ánh sáng khác nhau và với nhiều loại đối tượng chuyển động. Việc áp dụng mô hình này trong thực tế đã cho thấy sự cải thiện đáng kể trong khả năng phát hiện và theo dõi chuyển động, đặc biệt là trong các ứng dụng giám sát an ninh và phân tích video.

II. Ứng Dụng Trong Nghiên Cứu

Các thuật toán phát hiện chuyển động có nhiều ứng dụng thực tiễn trong nghiên cứu khoa học và công nghệ. Chúng được sử dụng để theo dõi hành vi của đối tượng trong video, phân tích chuyển động trong thể thao, và giám sát an ninh. Việc áp dụng công nghệ thông tin và machine learning trong các thuật toán này đã giúp nâng cao khả năng phân tích và nhận diện. Các nghiên cứu gần đây đã chỉ ra rằng việc sử dụng các mô hình phức tạp như mô hình hỗn hợp nền có thể cải thiện đáng kể độ chính xác trong việc phát hiện chuyển động. Điều này mở ra nhiều cơ hội cho các ứng dụng trong lĩnh vực y tế, giao thông và an ninh.

2.1 Phân Tích Chuyển Động

Phân tích chuyển động là một lĩnh vực nghiên cứu quan trọng trong khoa học máy tính và công nghệ thông tin. Các thuật toán phát hiện chuyển động giúp phân tích hành vi của đối tượng trong video, từ đó đưa ra các quyết định thông minh hơn. Việc áp dụng các phương pháp như phân loại hình ảnh và thuật toán học máy đã giúp cải thiện khả năng phân tích và nhận diện. Các nghiên cứu cho thấy rằng việc sử dụng các mô hình phức tạp có thể giúp phát hiện các hành vi bất thường trong video, từ đó nâng cao khả năng giám sát và bảo vệ an ninh.

2.2 Phát Triển Phần Mềm

Phát triển phần mềm cho các ứng dụng phát hiện chuyển động là một lĩnh vực đang phát triển mạnh mẽ. Các nhà phát triển đang tìm cách tích hợp các thuật toán phát hiện chuyển động vào các ứng dụng thực tế, từ giám sát an ninh đến phân tích video trong thể thao. Việc sử dụng thư viện OpenCV và các công nghệ mã nguồn mở khác đã giúp đơn giản hóa quá trình phát triển và triển khai các thuật toán này. Các ứng dụng này không chỉ giúp nâng cao hiệu quả công việc mà còn mở ra nhiều cơ hội mới trong nghiên cứu và phát triển công nghệ.

Nội dung chính

Tổng quan nghiên cứu

Xử lý tín hiệu hình ảnh, đặc biệt là phát hiện chuyển động, đã trở thành lĩnh vực nghiên cứu quan trọng với nhiều ứng dụng thực tiễn như giám sát an ninh, giao thông thông minh và tương tác người-máy. Theo ước tính, các hệ thống phát hiện chuyển động hiện đại cần xử lý hàng trăm khung hình mỗi giây trong điều kiện môi trường thay đổi liên tục, đòi hỏi thuật toán phải vừa chính xác vừa hiệu quả về mặt tính toán. Luận văn tập trung nghiên cứu các thuật toán phát hiện chuyển động dựa trên mô hình hóa nền, với mục tiêu xây dựng và cải tiến các mô hình nền thích nghi thời gian thực nhằm nâng cao độ chính xác và tốc độ xử lý.

Phạm vi nghiên cứu tập trung vào các thuật toán mô hình nền như bộ lọc Kalman, mô hình hỗn hợp phân phối Gauss (MOG), mô hình không tham số và mô hình từ điển thích nghi, được triển khai và đánh giá trên dữ liệu video thu thập tại môi trường ngoài trời với các điều kiện ánh sáng và chuyển động phức tạp. Ý nghĩa của nghiên cứu thể hiện qua việc cải thiện các chỉ số như tỉ lệ phát hiện đúng, giảm phát hiện sai và tăng tốc độ xử lý khung hình, góp phần nâng cao hiệu quả ứng dụng trong các hệ thống giám sát và nhận dạng chuyển động.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn áp dụng các lý thuyết và mô hình chính sau:

• Bộ lọc Kalman: Mô hình trạng thái tuyến tính với giả thiết ồn trắng phân bố Gauss, cho phép dự đoán và cập nhật trạng thái chuyển động dựa trên các phép đo có độ không chắc chắn khác nhau. Bộ lọc Kalman giúp kết hợp thông tin cũ và mới một cách tối ưu, thích hợp cho việc theo dõi chuyển động trong video.

• Mô hình hỗn hợp nền thích nghi (MOG): Mỗi điểm ảnh được mô hình hóa như một hỗn hợp của K phân phối Gauss, cho phép mô hình hóa nền phức tạp với các chuyển động nhỏ và thay đổi ánh sáng. Mô hình này sử dụng thuật toán cập nhật tham số theo thời gian thực để thích nghi với môi trường.

• Mô hình không tham số thích nghi: Sử dụng ước lượng hàm mật độ xác suất dựa trên các mẫu cường độ điểm ảnh gần nhất, không cần giả thiết phân phối tham số, giúp thích nghi nhanh với các thay đổi môi trường và phát hiện vật thể chuyển động nhạy hơn.

• Mô hình từ điển thích nghi thời gian thực: Mỗi điểm ảnh được biểu diễn bằng một từ điển chứa các từ mã (codewords) đại diện cho các trạng thái nền khác nhau. Mô hình này có khả năng nén dữ liệu cao, thích nghi với các thay đổi cường độ sáng cục bộ và toàn cục, đồng thời cho phép phát hiện vật thể chuyển động ngay trong quá trình học nền.

Các khái niệm chuyên ngành quan trọng bao gồm: phân phối Gauss, hàm mật độ xác suất, thuật toán EM (Expectation-Maximization), mô hình hỗn hợp, từ điển mã hóa, và các thuật toán tìm thành phần liên kết.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu là các chuỗi video thu thập tại môi trường ngoài trời với tốc độ khung hình khoảng 30 fps, bao gồm các cảnh có chuyển động phức tạp như cây cối rung động, phương tiện giao thông và người đi bộ. Cỡ mẫu dữ liệu gồm hàng nghìn khung hình được sử dụng để huấn luyện và đánh giá các mô hình.

Phương pháp phân tích bao gồm:

• Xây dựng và triển khai các thuật toán phát hiện chuyển động dựa trên các mô hình nền đã nêu.
• Sử dụng thuật toán EM để ước lượng tham số trong mô hình hỗn hợp Gauss.
• Áp dụng ước lượng hàm mật độ xác suất không tham số với hàm lõi Gaussian để mô hình hóa điểm ảnh.
• Thiết kế và cập nhật từ điển mã hóa cho từng điểm ảnh trong mô hình từ điển thích nghi.
• So sánh hiệu quả các mô hình qua các chỉ số như tỉ lệ phát hiện đúng, tỉ lệ phát hiện sai, tốc độ xử lý khung hình.
• Thời gian nghiên cứu kéo dài trong khoảng một năm, với các giai đoạn thu thập dữ liệu, phát triển thuật toán, cài đặt và đánh giá thực nghiệm.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả của bộ lọc Kalman trong dự đoán chuyển động: Bộ lọc Kalman cho phép dự đoán trạng thái chuyển động với độ chính xác cao, giảm sai số đo lường xuống khoảng 15-20% so với phương pháp không sử dụng dự đoán. Điều này giúp cải thiện khả năng theo dõi đối tượng chuyển động trong video.

2. Mô hình hỗn hợp nền thích nghi (MOG) nâng cao độ nhạy phát hiện: Mô hình MOG với K từ 3 đến 5 phân phối Gauss đã đạt tỉ lệ phát hiện đúng trên 85% trong các điều kiện ánh sáng thay đổi và chuyển động nền phức tạp. So với mô hình nền tĩnh, MOG giảm phát hiện sai khoảng 30%.

3. Mô hình không tham số thích nghi cho phép phát hiện chuyển động nhạy hơn: Sử dụng ước lượng hàm mật độ xác suất không tham số giúp phát hiện các vật thể chuyển động nhỏ và chậm với độ nhạy tăng khoảng 10% so với MOG, tuy nhiên chi phí tính toán cao hơn khoảng 25%.

4. Mô hình từ điển thích nghi thời gian thực tối ưu về bộ nhớ và tốc độ: Mô hình từ điển cho phép nén dữ liệu nền với trung bình chỉ khoảng 6,5 từ mã cho 5 phút video ngoài trời, giảm dung lượng lưu trữ xuống dưới 10% so với mô hình không tham số. Tốc độ xử lý đạt khoảng 40 khung hình/giây, nhanh hơn 50% so với MOG và mô hình không tham số.

Thảo luận kết quả

Các kết quả cho thấy sự ưu việt của mô hình từ điển thích nghi trong việc cân bằng giữa độ chính xác phát hiện và hiệu quả tính toán. Bộ lọc Kalman đóng vai trò quan trọng trong việc dự đoán trạng thái chuyển động, giúp giảm sai số và tăng độ ổn định của hệ thống. Mô hình MOG và mô hình không tham số đều có ưu điểm trong việc mô hình hóa nền phức tạp, tuy nhiên mô hình không tham số có chi phí tính toán cao hơn, hạn chế ứng dụng trong thời gian thực.

Việc sử dụng mô hình từ điển phân lớp và từ điển hai lớp thích nghi giúp giải quyết các vấn đề về thay đổi cường độ sáng chậm và đa nền, đồng thời cho phép phát hiện vật thể chuyển động ngay trong quá trình học nền. So sánh với các nghiên cứu trước đây, kết quả này phù hợp với xu hướng phát triển các mô hình nền thích nghi có khả năng xử lý dữ liệu lớn và thay đổi môi trường liên tục.

Dữ liệu có thể được trình bày qua các biểu đồ so sánh tỉ lệ phát hiện đúng, phát hiện sai và tốc độ xử lý giữa các mô hình, cũng như bảng thống kê dung lượng bộ nhớ sử dụng.

Đề xuất và khuyến nghị

1. Triển khai mô hình từ điển thích nghi trong các hệ thống giám sát thời gian thực: Đề xuất áp dụng mô hình từ điển hai lớp thích nghi để nâng cao hiệu quả phát hiện chuyển động, giảm thiểu dung lượng lưu trữ và tăng tốc độ xử lý. Thời gian triển khai dự kiến trong 6 tháng, chủ thể thực hiện là các nhóm phát triển phần mềm giám sát.

2. Tích hợp bộ lọc Kalman trong quá trình theo dõi chuyển động: Khuyến nghị sử dụng bộ lọc Kalman để dự đoán trạng thái chuyển động, giúp giảm sai số đo và tăng độ ổn định của hệ thống. Thời gian thực hiện 3 tháng, chủ thể là nhóm nghiên cứu và phát triển thuật toán.

3. Phát triển thuật toán giảm phát hiện sai dựa trên xác suất hoán đổi điểm ảnh: Đề xuất áp dụng phương pháp xác suất hoán đổi để loại bỏ các phát hiện sai do chuyển động nhỏ trong nền, nâng cao độ chính xác phát hiện. Thời gian nghiên cứu và thử nghiệm khoảng 4 tháng, chủ thể là nhóm nghiên cứu xử lý ảnh.

4. Cải tiến mô hình không tham số để giảm chi phí tính toán: Khuyến nghị nghiên cứu các kỹ thuật tối ưu hóa thuật toán ước lượng hàm mật độ xác suất không tham số nhằm giảm chi phí tính toán, mở rộng ứng dụng trong các hệ thống có tài nguyên hạn chế. Thời gian nghiên cứu 6 tháng, chủ thể là nhóm phát triển thuật toán và phần mềm.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành Công nghệ Điện tử - Viễn thông: Luận văn cung cấp kiến thức chuyên sâu về các thuật toán phát hiện chuyển động và mô hình nền, hỗ trợ nghiên cứu và phát triển các đề tài liên quan.

2. Kỹ sư phát triển phần mềm giám sát và an ninh: Các giải pháp và thuật toán được trình bày giúp cải thiện hiệu quả hệ thống giám sát video, giảm thiểu phát hiện sai và tăng tốc độ xử lý.

3. Chuyên gia xử lý ảnh và thị giác máy tính: Luận văn cung cấp các phương pháp mô hình hóa nền thích nghi và kỹ thuật xử lý ảnh nâng cao, phục vụ cho các ứng dụng nhận dạng và theo dõi đối tượng.

4. Doanh nghiệp phát triển thiết bị camera thông minh và hệ thống IoT: Các mô hình nền thích nghi và thuật toán phát hiện chuyển động có thể được tích hợp vào sản phẩm để nâng cao tính năng và hiệu suất.

Câu hỏi thường gặp

1. Bộ lọc Kalman có ưu điểm gì trong phát hiện chuyển động?
   Bộ lọc Kalman giúp dự đoán trạng thái chuyển động dựa trên các phép đo có độ không chắc chắn, giảm sai số đo và tăng độ ổn định theo dõi. Ví dụ, trong giám sát giao thông, Kalman giúp dự đoán vị trí xe khi tín hiệu bị nhiễu.

2. Mô hình hỗn hợp phân phối Gauss (MOG) hoạt động như thế nào?
   MOG mô hình mỗi điểm ảnh như hỗn hợp nhiều phân phối Gauss, cho phép thích nghi với các chuyển động nhỏ và thay đổi ánh sáng. Ví dụ, MOG có thể phát hiện chuyển động của lá cây trong gió mà không nhầm lẫn với vật thể chuyển động.

3. Ưu điểm của mô hình không tham số so với mô hình MOG là gì?
   Mô hình không tham số không cần giả thiết phân phối tham số, thích nghi nhanh với thay đổi môi trường và phát hiện vật thể nhỏ nhạy hơn. Tuy nhiên, nó tiêu tốn nhiều tài nguyên tính toán hơn, hạn chế ứng dụng trong thời gian thực.

4. Mô hình từ điển thích nghi có điểm gì nổi bật?
   Mô hình từ điển thích nghi nén dữ liệu nền hiệu quả, thích nghi với thay đổi cường độ sáng cục bộ và toàn cục, cho phép phát hiện vật thể chuyển động ngay trong quá trình học nền. Ví dụ, nó giúp phát hiện người đứng yên lâu trong cảnh quay mà không bị nhầm với nền.

5. Làm thế nào để giảm phát hiện sai trong môi trường nền thay đổi?
   Sử dụng xác suất hoán đổi điểm ảnh và thành phần liên kết giúp loại bỏ các phát hiện sai do chuyển động nhỏ hoặc nhiễu, nâng cao độ chính xác phát hiện. Ví dụ, các chuyển động nhỏ của cành cây không bị nhận diện nhầm là vật thể chuyển động.

Kết luận

• Luận văn đã phát triển và đánh giá các thuật toán phát hiện chuyển động dựa trên mô hình nền thích nghi, bao gồm bộ lọc Kalman, MOG, mô hình không tham số và mô hình từ điển thích nghi.
• Mô hình từ điển thích nghi thời gian thực cho thấy hiệu quả vượt trội về tốc độ xử lý và dung lượng bộ nhớ, đồng thời duy trì độ chính xác phát hiện cao.
• Bộ lọc Kalman đóng vai trò quan trọng trong việc dự đoán trạng thái chuyển động, giảm sai số và tăng độ ổn định hệ thống.
• Các giải pháp giảm phát hiện sai và mô hình phân lớp từ điển giúp nâng cao độ chính xác và khả năng thích nghi với môi trường thay đổi.
• Các bước tiếp theo bao gồm triển khai thực tế các mô hình trong hệ thống giám sát, tối ưu hóa thuật toán không tham số và mở rộng nghiên cứu ứng dụng trong các lĩnh vực khác.

Call-to-action: Các nhà nghiên cứu và kỹ sư phát triển phần mềm được khuyến khích áp dụng và tiếp tục cải tiến các mô hình nền thích nghi để nâng cao hiệu quả phát hiện chuyển động trong các ứng dụng thực tế.

Trích đoạn nội dung tài liệu

MỞ ĐẦU Lĩnh vực xử lý tín hiệu, cụ thể là xử lý hình ảnh đã phát triển từ lâu với đa dạng các lĩnh vực nhƣ tăng cƣờng chất lƣợng ảnh, tách thành phần nền, dự đoán, theo dõi chuyển động, nhận dạng đối tƣợng,… Với sự phát triển mạnh mẽ trong công nghệ phần cứng máy tính và sự hỗ trợ của các hệ thống mô phỏng, thƣ viện mã nguồn mở thƣ viện xử lý đồ họa đã cho phép thực hiện nhiều thuật toán phức tạp đòi hỏi số lƣợng tính toán lớn đƣợc nghiên cứu, đánh giá, cải tiến và áp dụng trong thực tế. Trong đó, các phƣơng pháp phát hiện chuyển động là một lớp ứng dụng liên quan tới khá nhiều các kĩ thuật trong xứ lý ảnh nhƣ tăng cƣờng chất lƣợng ảnh, mô hình hóa nền – tách nền, theo dõi chuyển động, dự đoán chuyển động,… Do thời gian nghiên cứu và khuôn khổ nội dung Luận văn có hạn nên chúng ta sẽ đi vào tập trung nghiên cứu các thuật toán phát hiện chuyển động dựa trên việc mô hình hóa nền đƣợc trình bày chủ yếu trong chƣơng 1. Các phƣơng pháp mô hình hóa sẽ đƣợc trình bày theo thứ tự phát triển tăng dần. Thứ nhất là mô hình sử dụng bộ lọc Kalman để dự đoán trong việc ƣớc lƣợng nền thích nghi.

Thứ hai là mô hình nền hỗn hợp thích nghi sử dụng K phân bố Gauss để mô hình hóa nền có các chuyển động nhỏ, phức tạp với các tham số mô hình. Thứ ba là mô hình nền không tham số sử dụng các ƣớc lƣợng hàm lõi cho phép thích nghi tốt với thay đổi của môi trƣờng, loại bỏ các yếu tố tham số của mô hình. Thứ tƣ là mô hình nền sử dụng từ điển cho phép mô hình hóa nền phức tạp trong khoảng thời gian dài và thích nghi thời gian thực. Và cuối cùng là mô hình cải tiến của mô hình nền sử dụng từ điển nhằm tăng tốc độ xử lý khung hình và khắc phục vấn đề thích nghi với thay đổi nhỏ trong thời gian dài của mô hình trƣớc đó.

Tiếp đó, ở chƣơng 2 sẽ đi tìm hiểu thƣ viện xử lý đồ họa mã nguồn mở OpenCV. Chúng ta chủ yếu đề cập tới các khái niệm, nguyên mẫu hàm cần thiết cho việc xây dựng chƣơng trình thực hiện mô hình hóa nền sử dụng từ điển nhƣ: khởi thủy cấu trúc dữ liệu, các hàm xử lý đồ họa ngƣời dùng mức cao, các thuật toán xử lý hình ảnh phổ biến… Cuối cùng, ở chƣơng 3 sẽ mô tả quá trình, kết quả xây dựng chƣơng trình, những lƣu ý cụ thể khi cài đặt. Chƣơng trình nguồn thu đƣợc có thể dùng để nghiên cứu thuật toán hoặc sử dụng trong các ứng dụng thƣơng mại liên quan tới nhận dạng chuyển động. THUẬT TOÁN PHÁT HIỆN CHUYỂN ĐỘNG 1.1 Bộ lọc Kalman Đƣợc giới thiệu năm 1960, bộ lọc Kalman đã đƣợc chú ý đặc biệt trong lĩnh vực xử lý tín hiệu.

Bộ lọc Kalman,với các điều kiện ràng buộc, cho phép chúng ta xây dựng một mô hình trạng thái với cực đại xác suất trƣớc mà không cần giữ giá trị của nhiều giá trị đo trƣớc đó. Thay vì phải lƣu lại các giá trị này, chúng ta chỉ cập nhật mô hình trạng thái hệ thống và chỉ giữ lại mô hình để sử dụng ở bƣớc tiếp theo[6]. Trƣớc khi tìm hiểu chi tiết về ý nghĩa thực tế của bộ lọc này, chúng ta hãy phân tích các giả thiết cũng là điều kiện ràng buộc khi sử dụng của bộ lọc. Có 2 giả thiết quan trọng về mặt lý thuyết khi xây dựng bộ lọc Kalman đó là:  Hệ thống đƣợc mô hình hóa là tuyến tính.

Có nghĩa là trạng thái của hệ thống tại thời điểm k có thể đƣợc mô hình hóa nhƣ là tích của một số ma trận (ta sẽ không định nghĩa tƣờng minh các ma trận này) với trạng thái tại thời điểm (k-1).  Ồn trong phép đo là ồn trắng và có phân bố Gauss. Nghĩa là ồn sẽ không tƣơng quan trong miền thời gian và biên độ của nó có thể đƣợc mô hình hóa thông qua giá trị trung bình và phƣơng sai. Ý nghĩa của phép “cực đại hóa xác suất trƣớc của các phép đo đã thực hiện” có nghĩa là một mô hình mới đƣợc xây dựng sau khi thực hiện một phép đo đƣợc tính toán dựa trên mô hình trƣớc đó với độ không chắc của nó và phép đó mới cũng cùng với độ không chắc chắn của nó.

Và mô hình nào đƣợc tìm ra có xác suất cao nhất thì đƣợc gọi là mô hình đƣợc chọn. Với mục đích này, bộ lọc Kalman với 2 điều kiện ràng buộc là cách tốt nhất để kết hợp dữ liệu từ các nguồn khác nhau hoặc từ cùng một nguồn tại các thời điểm khác nhau. Khi có thông tin mới thì chúng ta quyết định thay đổi trên cơ sở thông tin đã có và thông tin mới sử dụng phép lấy trung bình theo trọng số giữa các giá trị này. Giả sử ta thực hiện 2 phép đo xác định vị trí của x.

Do có ồn nên chúng ta có 2 kết quả đo không chắc chắn – theo quan điểm Gauss – là x1 và x2. Bởi vì có độ không chắc chắn Gauss trong phép đo nên chúng có giá trị trung bình và với phƣơng sai chuẩn ζ1 và ζ2. Phƣơng sai ở đây mang thông tin về độ không z 2 chắc chắn của phép đo. Phân bố xác suất mô tả của phép đo là hàm phân bố Gauss.

Trong trƣờng hợp này i = 1,2. Chúng ta kì vọng rằng mật độ xác suất cho giá trị của x cho bởi hai phép đo này sẽ tỉ lệ với. Nhƣ ta đã biết thì tích của 2 phân bố Gauss là một phân bố Gauss tƣơng đƣơng với giá trị trung bình và phƣơng sai chuẩn đƣợc tính nhƣ sau: Do phân bố Gauss cực đại tại giá trị trung bình, mà ta có thể xác định giá trị này một cách dễ dàng thông qua việc tính đạo hàm của p12(x) theo x và cho đạo hàm này bằng 0. Vì hàm phân bố xác suất p(x) luôn khác 0 nên biểu thức trên tƣơng đƣơng với biểu thƣc trong dấu ngoặc bằng 0.

Giải biểu thức đó theo x cho ta mối quan hệ hết sức quan trọng: Nhƣ vậy, giá trị trung bình là trung bình theo trọng số của hai giá trị trung bình của hai phép đo; với trọng số xác định độ không chắc chắn liên quan giữa 2 phép đo. Nếu độ không chắc chắn ζ2 của phép đo thứ 2 đặc biệt lớn thì giá trị trung bình thu đƣợc sẽ gần với giá trị trung bình của x 1 với độ chính xác hơn. Với giá trị trung bình có đƣợc, chúng ta thay vào trong biểu thức xác suất p12(x) và tính đƣợc độ không chắc chắn tƣơng ứng là: z 3 Công thức này nói lên rằng: chúng ta có thể tạo ra một phép đo mới với giá trị trung bình và độ không chắc chắn tƣơng ứng bằng cách kết hợp các phép đo trƣớc đó. Tính chất này của hai phép đo Gauss có nghĩa là: nếu chúng ta có M phép đo thì có thể kết hợp hai phép đo đầu, sau đó kết hợp phép đo thứ 3 với kết quả hai phép đo đó và cứ nhƣ vậy đến hết.

Cuối cùng ta sẽ thu đƣợc kết quả là phép đo tƣơng đƣơng của M phép đo đó mong muốn. Giả sử với mỗi phép đo có , chúng ta có thể tính trạng thái của ƣớc lƣợng hiện tại nhƣ sau: Bƣớc thứ 1, chúng ta có. Ta có biểu thức ƣớc lƣợng: Giản ƣớc biểu thức trên ta có: Tƣơng tự nhƣ vậy ta có: Nhƣ vậy, các công thức trên cho phép chúng ta có thể tách biệt hoàn toàn thông tin cũ với thông tin mới. Đặt hệ số cập nhật là K: Khi đó sẽ thu đƣợc dạng biểu thức đệ quy đơn giản hơn: Ở phần trƣớc, chúng ta nói đến là việc thực hiện nhiều phép đo đối với một đối tƣợng x cố định mà chƣa đề cập đến vấn đề là đối tƣợng đó có thể z 4 chuyển động trong quá trình đo.

Trƣờng hợp này chúng ta sẽ gọi là pha dự đoán. Trong suốt pha dự đoán này, chúng ta sử dụng các thông tin đã biết để dự đoán về kết quả phép đo mới mà hệ thống sẽ diễn ra. Trong thực tế, pha dự đoán đƣợc hoàn thành ngay sau khi một phép đo mới đƣợc thực hiện nhƣng trƣớc khi phép đo mới đƣợc đƣa vào ƣớc lƣợng trạng thái hệ thống. Ví dụ nhƣ khi chúng ta đo vị trí của một ô tô tại thời điểm t và sau đó là (t+dt).

Nếu ô tô đó đang chuyển động với vận tốc v thì chúng ta không thể kết hợp phép đo đó một cách trực tiếp. Đầu tiên, chúng ta cần tiến tịnh tiến mô hình của chúng ta về phía trƣớc dựa trên cơ sở những thông tin đã biết tại thời điểm t vì thế chúng ta có một mô hình không chỉ của hệ thống tại thời điểm t mà cả (t+dt) ngay trƣớc khi thông tin mới đƣợc kết hợp. Theo cách này, thông tin mới nhận đƣợc tại thời điểm (t+dt) phù hợp với cả mô hình cũ và mô hình tại thời điểm (t+dt) của hệ thống. Có 3 loại chuyển động mà chúng ta sẽ xét đến:  Chuyển động tự thân của đối tượng: đây là loại chuyển động mà chúng ta có thể xác định trạng thái hệ thống trực tiếp từ lần đo trƣớc.

Nếu chúng ta đã đo hệ thống tại vị trí x với tốc độ v tại thời điểm t thì sau đó tại thời điểm (t+dt) chúng ta kì vọng hệ thống sẽ ở vị trí (x+v*dt).  Chuyển động được điều khiển: là loại chuyển động do tác động của các yếu tố bên ngoài. Ví dụ phổ biến nhất của loại vận động này là chúng ta biết về yếu tố tác động gây ra vận động đó. Ví dụ nhƣ hệ thống rô-bốt với phần điểu khiển là hệ thống ra lệnh cho nó.

Rõ ràng trong trƣờng hợp này, nếu rô-bốt đã ở vị trí x và chuyển động với vận tốc v tại thời điểm (t+dt) thì chúng ta kì vọng nó sẽ di chuyển không chỉ tới (x+v*dt) mà có thể xa hơn.  Chuyển động ngẫu nhiên: là các chuyển động mà chúng ta không biết hoặc không điều khiển đƣợc. Nhƣ giả thiết trƣớc kia thì chuyển động ngẫu nhiên ở đây cũng có phân bố Gauss hay ít nhất là có thể đƣợc mô hình hóa bởi phân bố này. Nhƣ đã cấp ở trên, để thêm yếu tố chuyển động vào trong mô hình thì chúng ta cần một bƣớc cập nhật trƣớc khi có thể thêm kết quả phép đo mới.