Chương 1 của tài liệu tham khảo [20]. Bộ lọc Kalman giải quyết một vấn đề tổng quát sau: Trạng thái dự đoán (predicted state) 𝑥𝑛 ∈ ℜ của một quá trình rời rạc được mô tả bởi phương trình sai phân tuyến tính ngẫu nhiên (linear stochastic difference equation) [20]: 𝑥𝑡 = 𝐴𝑥𝑡−1 + 𝐵𝑢𝑡−1 + 𝑤𝑡−1 (2.16) Và trạng thái đo lường (measurement state) có được là: 𝑧𝑡 = 𝐻𝑥𝑡 + 𝑣𝑡 (2.17) Biến ngẫu nhiên 𝑤𝑡 và 𝑣𝑡 là nhiễu quá trình (processing noise) và nhiễu đo lường (measurement noise). Chúng được coi là độc lập và là nhiễu trắng có phân bố chuẩn: w ~ N(0,Q) v ~ N(0, R) Nguồn gốc tính toán của bộ lọc (the computational Origins of the Filter). Gọi 𝑥̂𝑡̅ ∈ 𝑅𝑛 là ước lượng trạng thái tiền nghiệm (priori) tại bước t dựa vào quá trình trước đó (ước lượng của 𝑥̂𝑡̅ ); 𝑥̂𝑡 ∈ 𝑅𝑛 là ước lượng trạng thái hậu nghiệm CHƯƠNG 2: LÝ THUYẾT BỘ LỌC PHẦN TỬ 10 HVTH: TRẦN XUÂN BỬU THẠCH Kết hợp PCA và PF để phân đoạn và tách đặc trưng ảnh x-quang GVHD: PGS.TS LÊ TIẾN THƯỜNG (posteriori) tại bước t cho bởi phép đo (ước lượng của 𝑥̂𝑡 ).
Chúng ta định nghĩa sai số ước lượng tiên nghiệm và hậu nghiệm như sau: Ước lượng tiên nghiệm: 𝑒𝑡̅ = 𝑥𝑡 − 𝑥̂𝑡̅ Ước lượng hậu nghiệm: 𝑒𝑡 = 𝑥𝑡 − 𝑥̂𝑡 Hiệp phương sai của lỗi ước lượng tiền nghiệm: 𝑃𝑡̅ = 𝐸[𝑒𝑡̅ (𝑒𝑡̅ )𝑇 ] Hiệp phương sai của lỗi ước lượng hậu nghiệm: 𝑃𝑡 = 𝐸[𝑒𝑡 (𝑒𝑡 )𝑇 ] Từ đó ta có ước lượng như sau: 𝑥𝑡 = 𝑥̂𝑡̅ + 𝐾(𝑧𝑡 − 𝐻𝑥̂𝑡̅ ) (2.18) Trong đó K là độ lợi Kalman: 𝑃𝑡̅ 𝐻 𝑇 𝐾𝑡 = 𝐻𝑃𝑡̅ 𝐻 𝑇 + 𝑅 (2.19) Bộ lọc Kalman thực hiện ước lượng một quá trình bằng cách sử dụng một dạng của điều khiển phản hồi (feedback control): bộ lọc ước lượng trạng thái của quá trình tại một thời điểm sau đó có được phản hồi từ các đo đạc (có nhiễu). Như vậy, các phương trình của bộ lọc Kalman được chia thành hai nhóm: cập nhật trạng thái theo thời gian (time update) và cập nhật trạng thái theo giá trị đo lường (measurement update). Các phương trình cập nhật theo thời gian để dự đoán (projecting forward) trạng thái hiện tại và vector hiệp phương sai lỗi nhằm ước lượng trạng thái tiên nghiệm cho bước tiếp theo. Các phương trình cập nhật theo giá trị đo lường dùng để cung cấp phản hồi - ví dụ như kết hợp một giá trị đo lường mới với ước lượng tiên nghiệm để có được ước lượng trạng thái hậu nghiệm.
CHƯƠNG 2: LÝ THUYẾT BỘ LỌC PHẦN TỬ 11 HVTH: TRẦN XUÂN BỬU THẠCH Kết hợp PCA và PF để phân đoạn và tách đặc trưng ảnh x-quang GVHD: PGS.TS LÊ TIẾN THƯỜNG 2.2 Bộ lọc Kalman mở rộng Trong thực tế có rất nhiều hệ thống không phải tuyến tính (phi tuyến tính, non- linear), trong trường họp này áp dụng bộ lọc Kalman sẽ cho sai số lớn. Để khắc phục hạn chế trên, có rất nhiều phương pháp được đưa ra nhằm tuyến tính hóa (linearize) hệ thống bằng các hàm xấp xỉ như bộ lọc Kalman mở rộng, Unscented Kalman Filter, Bộ Lọc Phần Tử. Một trong những cách tuyến tính hóa hệ thống một cách đơn giản là áp dụng khai triển chuỗi Taylor bậc 1. Đó chính là bộ lọc Kalman mở rộng [21].
Vấn đề ước lượng trạng thái một cách tổng quát trong [21] như sau: 𝑥𝑡 = 𝑓(𝑥𝑡−1 , 𝑢𝑡−1 ) + 𝑤𝑡−1 (2.20) Với 𝑤𝑡−1 là nhiễu hệ thống có phân bố Gaussian và hiệp phương sai là Q. Vì có nhiễu nên trạng thái của hệ thống là bất định. Người quan sát chỉ quan sát được đo lường của hệ thống khi có quan hệ với hệ thống thông qua phương trình đo lường: 𝑧𝑡 = 𝑔(𝑥𝑡 ) + 𝑣𝑡 (2.21) Trong đó 𝑣𝑡 là nhiễu đo lường có phân bố Gaussian và hiệp phương sai là R. Nhiệm vụ của bộ lọc là dựa vào quan sát và mô hình hệ thống để ước lượng tối ưu (có thể) trạng thái của hệ thống.
Như đã nói ở trên, nếu cả hai phương trình trên là tuyến tính và nhiễu tác động lên hệ thống là nhiễu Gaussian thì bộ lọc Kalman là bộ lọc tối ưu được sử dụng cho trường hợp này. Nếu ít nhất một trong hai phương trình ở trên là phi tuyến, ta phải sử dụng các phương pháp xấp xỉ tuyến tính. Bộ lọc Kalman mở rộng sử dụng phương pháp xấp xỉ dựa vào triển khai Taylor bậc 1. Khi đó các phương trình trạng thái và đo lường được xấp xỉ bằng cách tuyến tính như sau: CHƯƠNG 2: LÝ THUYẾT BỘ LỌC PHẦN TỬ 12 HVTH: TRẦN XUÂN BỬU THẠCH Kết hợp PCA và PF để phân đoạn và tách đặc trưng ảnh x-quang GVHD: PGS.TS LÊ TIẾN THƯỜNG 𝑥𝑡+1 = 𝑥̃𝑡+1 + 𝐴(𝑥𝑡 − 𝑥̂𝑡 ) + 𝑊𝑤𝑡 (2.23) Để tuyến tính hóa dựa vào khai triển Taylor bậc 1, các ma trận chuyển trạng thái A, ma trận đo H là các ma trận Jacobian, được xác định như sau: 𝜕𝑓[𝑖] 𝐴[𝑖,𝑗] = (𝑥̂ , 𝑢 , 0) 𝜕𝑥[𝑗] 𝑡 𝑡 (2.25) Trong đó: 𝑥̂𝑡 là dự đoán (projected, predicted) và 𝑥̃𝑡 là ước lượng (estimated) của trạng thái 𝑥𝑡.
Phần trên đã trình bày hai giải pháp ước lượng trạng thái đối tượng như: xử lý tín hiệu tuần tự áp dụng các thuật toán dựa trên bộ lọc Kalman cho trường hợp bài toán là tuyến tính và nhiễu là Gaussian; trường hợp là phi tuyến và nhiễu là phi Gaussian thì lựa chọn phổ biến nhất là bộ lọc Kalman mở rộng. Nhưng cả hai bộ lọc trên có hiệu suất kém với sai số hệ thống lớn, không hội tụ và thiếu độ chắc chắn. Từ đó bộ lọc phần tử là giải pháp tốt cho hệ thống phi tuyến và được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau. Yêu cầu quan trọng nhất của việc ước lượng trạng thái là làm sao cho trạng thái ước lượng của các bộ lọc phải đạt đến độ chính xác cao so với trạng thái thật phải đạt nhỏ nhất.
Điều này đã được phương pháp lọc phần tử khắc phục được nhược điểm đó. Nó được biết như là phương pháp ước lượng tốt nhất hiện nay.2 sẽ trình bày chi tiết về phương pháp bộ lọc phần tử. CHƯƠNG 2: LÝ THUYẾT BỘ LỌC PHẦN TỬ 13 HVTH: TRẦN XUÂN BỬU THẠCH Kết hợp PCA và PF để phân đoạn và tách đặc trưng ảnh x-quang GVHD: PGS.TS LÊ TIẾN THƯỜNG 2. Bộ lọc phần tử Vào khoảng năm 1998, cùng với sự ra đời của thuật toán CONDENSATION, một loạt các thuật toán lọc tổng quát dựa vào phương pháp tuần tự Monte Carlo (Sequential Monte Carlo - SMC) với nhiều tên gọi khác nhau như bộ lọc Bootstrap (Bootstrap Filters), bộ lọc phần tử (Particle Filters), bộ lọc Monte Carlo (Monte Carlo Filters) được ra đời, đã giúp giải quyết bài toán lọc tổng quát một cách triệt để.
Các phương pháp này không đòi hỏi phải đặt ra bất kỳ giả định nào về hệ, ngoài ra, chúng còn rất linh động, mềm dẻo, dễ cài đặt, có khả năng mở rộng để thực hiện trong môi trường tính toán song song và đặc biệt là hoạt động rất hiệu quả trong trường hợp bài toán tổng quát. Gần đây, các phương pháp này được thống nhất gọi với tên gọi là bộ lọc phần tử. Bộ lọc phần tử hiện đang được áp dụng trong rất nhiều lĩnh vực như mô hình hóa tài chính, kinh tế lượng (Econometrics), theo dõi đối tượng, dẫn đường cho tên lửa (Missle Guidance), di chuyến dựa vào địa hình (Terrain Navigation), thị giác máy tính, mạng neuron, máy học, robot,. ứng dụng của bộ lọc phần tử trong thị giác máy tính đang được rất nhiều người quan tâm, đặc biệt là trong lĩnh vực theo vết đối tượng dựa vào thông tin thị giác.1 Cơ sở lý thuyết Ta nhắc lại một số các quy ước toán học và phát biểu của bài toán lọc cần quan tâm.
Không mất tính tổng quát, ta xét một hệ (có thể là một hệ tín hiệu; hệ cơ học trong đó có các đại lượng vị trí, vận tốc, gia tốc;.) có không gian trạng thái được mô hình hóa bởi một hàm phân phối phi tuyến, phi Gauss, thỏa hai giả định của bài toán lọc Bayes đệ quy như sau: Chuỗi trạng thái của hệ thỏa giả định về hệ Markov bậc I [19] 𝑝(𝑥𝑡 |𝑥0:𝑡−1 ) = 𝑝(𝑥𝑡 |𝑥𝑡−1 ) (2.26) Các giá trị đo có được tại một thời điểm t bất kỳ chỉ phụ thuộc vào trạng thái CHƯƠNG 2: LÝ THUYẾT BỘ LỌC PHẦN TỬ 14 HVTH: TRẦN XUÂN BỬU THẠCH Kết hợp PCA và PF để phân đoạn và tách đặc trưng ảnh x-quang GVHD: PGS.TS LÊ TIẾN THƯỜNG của hệ tại thời điểm đó.27) Các trạng thái{𝑥𝑡 ; 𝑡 ∈ 𝑁}, 𝑥𝑡 ∈ 𝑋 của hệ có phân phối xác suất ban đầu 𝑝(𝑥0 ) và xác suất chuyến trạng thái 𝑝(𝑥 |𝑥𝑡−1 ), {𝑧𝑡 ; 𝑡 ∈ 𝑁}, 𝑧𝑡 ∈ 𝑌 là quan sát tương ứng với các thời điểm trạng thái. Đồng thời, ta định nghĩa 𝑥0:𝑡 ≜ {𝑥0 , 𝑥1 , … , 𝑥𝑡 }, 𝑧1:𝑡 ≜ {𝑧1 , … , 𝑧𝑡 } lần lượt là chuỗi trạng thái và chuỗi quan sát cho đến thời điểm t. Vậy hệ đang xét có thế được đặc trưng bởi các hàm phân phối xác suất như sau: 𝑝(𝑥0 ) 𝑝(𝑥𝑡 |𝑥𝑡−1 ), 𝑡 ≥ 1 𝑝(𝑧𝑡 |𝑥𝑡 ), 𝑡 ≥ 1 Mục tiêu của bài toán lọc là tìm được lời giải cho phân phối xác suất hậu nghiệm 𝑝(𝑥0:𝑡 |𝑧1:𝑡 ) và các đại lượng đặc trưng của nó (quan trọng nhất là phân phối lề 𝑝(𝑥𝑡 |𝑧1:𝑡 ), còn được gọi là phân bố độ lọc - filtering distribution) và kỳ vọng toán học: 𝐼(𝑓𝑡 ) = 𝐸𝑝(𝑥0:𝑡 |𝑧1:𝑡 ) [𝑓𝑡 (𝑥0:𝑡 )] ≜ ∫ 𝑓𝑡 (𝑥0:𝑡 ) 𝑝(𝑥0:𝑡 |𝑧1:𝑡 )𝑑𝑥0:𝑡 (2. Các ví dụ về hàm này bao gồm trung bình có điều kiện (Conditional Mean) 𝑓𝑡 (𝑥0:𝑡 ) = 𝑥0:𝑡 hoặc hiệp phương sai có điều kiện (Conditional Covariance): 𝑇 𝑓𝑡 (𝑥𝑡 ) = 𝑥𝑡 𝑥𝑡𝑇 − 𝐸𝑝(𝑥𝑡 |𝑧1:𝑡 ) [𝑥𝑡 ]𝐸𝑝( 𝑥 |𝑧 [𝑥𝑡 ] (2.29) 𝑡 1:𝑡 ) CHƯƠNG 2: LÝ THUYẾT BỘ LỌC PHẦN TỬ 15 HVTH: TRẦN XUÂN BỬU THẠCH Kết hợp PCA và PF để phân đoạn và tách đặc trưng ảnh x-quang GVHD: PGS.TS LÊ TIẾN THƯỜNG Tại một thời điếm t bất kỳ, hàm phân phối xác suất hậu nghiệm được cho bởi quy tắc Bayes như sau : 𝑝(𝑧1:𝑡 |𝑥0:𝑡 )𝑝(𝑥0:𝑡 ) 𝑝(𝑥0:𝑡 |𝑧1:𝑡 ) = ∫ 𝑝(𝑧1:𝑡 |𝑥0:𝑡 )𝑝(𝑥0:𝑡 ) 𝑑𝑥0:𝑡 (2.30) Và phương trình đệ quy để tính phân phối xác suất đồng thời 𝑝(𝑥0:𝑡+1 |𝑧1:𝑡+1 ) được cho bởi: 𝑝(𝑧𝑡+1 |𝑥𝑡+1 )𝑝(𝑥𝑡+1 |𝑥𝑡 ) 𝑝(𝑥0:𝑡+1 |𝑧1:𝑡+1 ) = 𝑝(𝑥0:𝑡 |𝑧1:𝑡 ) (2.32) Phương trình cập nhật: 𝑝(𝑧𝑡 |𝑥𝑡 )𝑝(𝑥𝑡−1 |𝑧1:𝑡−1 ) 𝑝(𝑥𝑡 |𝑧1:𝑡 ) = ∫ 𝑝(𝑧1:𝑡 |𝑥0:𝑡 )𝑝(𝑥0:𝑡 ) 𝑑𝑥0:𝑡 (2.