Tìm hiểu về lọc Kalman (Kalman filter)

 

Rudolf Kalman (sinh năm 1930) là một nhà toán học Mỹ gốc Hungary được biết đến nhiều nhất vì các công trình về cái gọi là lọc Kalman (Kalman filter). Vì các công trình này mà năm 2009 Kalman được Obama trao tặng National Medal of Science của Mỹ.

Lọc Kalman là một phương pháp thuật toán lọc nhiễu ra khỏi thông tin, và nó được dùng rất nhiều trong các lĩnh vực điều khiển, hàng không, quân sự, vũ trụ, v.v, ví dụ như để ước lượng và điểu khiển quĩ đạo của tên lửa, của phi thuyền. Nó còn được dùng trong rất nhiều lĩnh vực khác, từ nhận dạng tiếng nói cho đến marketing !

Ngoài Kalman, còn có Thiele và Swerling nghĩ ra thuật toán tương tự trước đó, Bucy tham ra vào phát triển lý thuyết, và Stratonovich ở Nga còn phát triển một lý thuyết thuật toán phi tuyến mở rộng hơn từ trước đó. Bởi vậy lọc này còn được gọi là Kalman-Bucy-Stratonovich filter.

Lọc Kalman nhằm ước lượng giá trị đích thực của một cái gì đó, bằng cách dự đoán giá trị của nó và tính độ tin cậy (hay độ bất định) của dự đoán đó, đồng thời đo đạc giá trị (nhưng bị sai số vì có các nhiễu), sau đó lấy một trung bình có trọng giữa giá trị dự đoán và giá trị đo đạc được, làm giá trị ước lượng. Có thể coi nó là một trường hợp của “suy diễn có điều kiện kiểu bayes” (bayesian inference) ?

Mô hình toán học:

(Đây là một mô hình tuyến tính, các trạng thái được viết bởi các vector còn các biến đổi được viết bởi các ma trận).

Gọi x_k là vector giá trị thực sự của một cái gì đó (ví dụ như vị trí của tên lửa) tại thời điểm thứ k. Ta sẽ giả sử x_k biến đổi theo qui luật sau:

x_k = F_k x_{k-1} + B_k u_k + w_k

trong đó F_k là ma trận thay đổi trạng thái (state transition matrix), u_k là vector điểu khiển, B_k là ma trận điều khiển, còn w_k là nhiễu ngẫu nhiên, với giả sử là nó có phân bố Gaussian (phân bố normal nhiều chiều) N(0,Q_k), trong đó Q_k là ký hiệu của ma trận hiệp phương sai tương ứng.

Tại mỗi thời điểm thứ k, có một đo đạc (measurement) trạng thái x_k cho kết quả là

z_k = H_k x_k + v_k

trong đó H_k là ma trận của mô hình quan sát, còn v_k là nhiễu trong lúc đo đạc, và ta giả sử nhiễu này cũng tuân theo một phân bố Gaussian N(0,R_k).

Các mà trận F_k,B_k, H_k được coi là đã biết. Ta giả sử thêm là các nhiễu \{v_1,\hdots,v_k,w_1,\hdots,w_k\} là một bộ biến ngẫu nhiên độc lập và cũng độc lập với trạng thái ban đầu x_0.

Câu hỏi đặt ra là làm sao ước lượng được các trạng thái $x_k$ từ các quan sát z_k ?

Nếu không hề có nhiễu, thì ta chỉ cần đặt x_k = H_k^{-1}. Nhưng vì có nhiễu nên không tính được chính xác x_k mà chỉ có thể ướng lượng nó. Kalman filter là một hàm ước lượng đệ quy (recursive estimator) cho phép làm việc này.

Thuật toán ước lượng như sau: Có thể chia nó thành 2 bước, bước dự đoán ban đầu (predict) và bước điều chỉnh sau đó (update)

Predict:

\hat{x}_{k|k-1} = F_k \hat{x}_{k-1|k-1} + B_k u_k + w_k,

P_{k|k-1} = F_k P_{k-1|k-1} F_k^T + Q_k

Ở đây \hat{x}_{k|k-1} là ký hiệu dự đoán giá trị của x_k dựa trên thông tin về giá trị tại thời điểm k-1, còn $\hat{x}_{k|k}$ là ước lượng giá trị của x_k sau khi đã sử dụng mọi thông tin tại thời điểm k. Ma trận P dùng để chỉ (ước lượng) ma trận hiệp phương sai của ước lượng của x.

Update:

Độ lệch so với quan sát (measurement residual): y_k = z_k - H_k \hat{x}_{k|k-1}

Thặng dư hiệp phương sai (residual covariance): S_k = H_k P_{k|k-1} H_k^{T} + R_k

Kalman tối ưu: K_k = P_{k|k-1} H_k^{T} S_k^{-1}

Ước lượng được điều chỉnh (updated estimate): \hat{x}_{k|k} = \hat{x}_{k|k-1} + K_k y_k

Hiệp phương sai cho ước lượng mới (updated estimate covariance): P_{k|k} = (1 - K_kH_k) P_{k|k-1}

Tài liệu tham khảo:

Trang web về Kalman filter: http://www.cs.unc.edu/~welch/kalman/

Speyer & Chung, Stochastic processes, estimation, and control, 2008. (Có chương về Kalman filter).

Wikipedia

Print Friendly
 

6 comments to Tìm hiểu về lọc Kalman (Kalman filter)

  • shakhi MonsterID Icon shakhi

    Norbert Wiener đã giải quyết bài toán kiểu như này từ 1949 rồi.

  • admin MonsterID Icon admin

    @shakhi

    Tôi không biết gì mấy về các filters, nhưng tôi có đọc người ta viết là các công trình của Kalman là phát triển tiếp theo của filter của Wiener và Kolmogorov (những năm 1940). Phần lõi lý thuyết của Kalman có lẽ không có gì khó khăn đặc biệt, nhưng có khác so với bài toán mà Wiener xét: có phần điều khiển, và có nhiễu ở cả hai vế (vế quan sát, và vế quá trình được quan sát).

  • Sudoku MonsterID Icon Sudoku

    @Shakhi: Wiener filters chi ap dung duoc cho $\{x_k\}$ va $\{y_k\}$ la cac stationary random processes.
    @Admin: Ke ca khi khong co measurement noise, nhieu truong hop $H_k$ khong phai la ma tran vuong, nen $H_k^{-1}$ khong ton tai. Vi du co mot vat chuyen dong tren mat phang nhung ta chi quan sat duoc toa do tren truc hoanh.

  • Đại Ngàn MonsterID Icon Đại Ngàn

    Chào NTZUNG
    Mong A/C có thể chia sẽ vấn đề dùng Kalman filter trong xử lý ảnh để tracking!
    Cảm ơn nhiều!

  • Lại Thế Anh MonsterID Icon Lại Thế Anh

    em chưa bít nhìu về lọc kalman.gần đây e có tham gia 1 đề tài về vấn đề này.nhưng e chưa hiểu về các thuật toán của bộ lọc.a có cách gì giúp e với.thanks

  • Robocon MonsterID Icon Robocon

    Mình cũng đang làm về Kalman trong ước lượng tốc độ động cơ. Phần khó nhất của nó là tìm ra được Ma trận P và Q. Admin có kinh nghiệm về nó không chỉ giáo cho mình với.
    Xin chân thành cám ơn

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Spam Protection by WP-SpamFree