Thuật toán so khớp khối (Block Matching Algorithm - BMA) tìm kiếm vectơ chuyển động dựa trên tiêu chuẩn nào?

Dựa trên việc giảm thiểu sai số chênh lệch giữa khối hiện tại và khối tham chiếu, phổ biến nhất là tiêu chuẩn sai số tuyệt đối trung bình (SAD - Sum of Absolute Differences).

Sự khác biệt giữa ước lượng chuyển động điểm ảnh nguyên (integer-pel) và điểm ảnh phân số (sub-pel) là gì?

Ước lượng sub-pel nội suy các vị trí nửa pixel (half-pel) hoặc phần tư pixel (quarter-pel) giúp mô tả chính xác hơn chuyển động mượt mà trong thế giới thực, nâng cao đáng kể tỷ số nén tín hiệu video.

Phương pháp dòng quang học (optical flow) khác thuật toán so khớp khối như thế nào?

Dòng quang học tính toán trường vectơ chuyển động dày đặc (dense flow) cho từng pixel dựa trên giả định bảo toàn độ sáng, trong khi so khớp khối tính toán theo từng khối điểm ảnh rời rạc.

Ước lượng chuyển động là gì? Nghiên cứu khoa học liên quan

Ước lượng chuyển động (motion estimation) là quá trình tính toán và xác định các vectơ chuyển động mô tả sự dịch chuyển không gian của các khối ảnh hoặc điểm ảnh giữa các khung hình liên tiếp trong một chuỗi video, là kỹ thuật nén then chốt để loại bỏ độ dư thừa thời gian trong các chuẩn mã hóa video hiện đại.

Trong nén video tiêu chuẩn như MPEG và H.264/AVC, ước lượng chuyển động tạo điều kiện để chỉ mã hóa phần sai khác giữa các khung (residual) thay vì toàn bộ khung hình, giúp giảm đáng kể băng thông yêu cầu và kích thước tệp. Tỷ lệ nén đạt được phụ thuộc mạnh vào độ chính xác của véc-tơ chuyển động và cơ chế dự đoán (prediction) đi kèm. Kết quả cuối cùng là chất lượng hình ảnh cao hơn ở cùng mức bit-rate so với phương pháp nén không dùng ước lượng chuyển động.

Ước lượng chuyển động còn quan trọng trong các hệ thống thực tế tăng cường (AR), thị giác máy tính (computer vision) và robot tự hành. Việc biết trước hướng di chuyển của vật thể hoặc camera cho phép thuật toán ổn định hình ảnh (video stabilization), loại bỏ hiện tượng rung lắc và xé hình (tearing). Trong dẫn đường tự động (autonomous navigation), ước lượng chuyển động hỗ trợ tính toán quỹ đạo camera, phát hiện va chạm và nhận diện vật cản động.

Phân loại phương pháp

Có ba phương pháp chính để ước lượng chuyển động, khác biệt ở cách thức xác định tương đồng và phạm vi tính toán:

Block-based: Chia khung hình thành các khối nhỏ cố định (ví dụ 16×16 pixel), tìm khối tương đồng nhất trong khung kế tiếp bằng hàm sai số tổng bình phương (SSD) hoặc tương quan chéo (cross-correlation).
Feature-based: Phát hiện và theo dõi các đặc trưng hình học (corner, edge) qua các khung, sử dụng các bộ mô tả (descriptor) như SIFT, SURF hoặc ORB để khớp điểm tương ứng.
Quang học (Optical flow): Ước lượng chuyển động tại mỗi pixel dựa trên giả thiết cường độ không đổi, giải bài toán đạo hàm và phương trình đa thức hóa hướng di chuyển.

Mô hình toán học cơ bản

Giả thiết cường độ sáng của một điểm ảnh không đổi khi di chuyển giữa các khung liên tiếp dẫn tới phương trình bảo toàn cường độ:

I(x+u, y+v, t+1) = I(x, y, t)

Trong đó I(x,y,t) là cường độ tại tọa độ (x,y) ở thời điểm t, và (u,v) là véc-tơ chuyển động cần tìm. Khi tăng cường độ mượt của tín hiệu, khai triển theo chuỗi Taylor bậc nhất cho kết quả:

I_x \, u + I_y \, v + I_t = 0

ở đó I_x, I_y, I_t lần lượt là đạo hàm cục bộ theo trục x, y và thời gian. Phương trình này chỉ cung cấp một phương trình để hai ẩn u và v, do đó cần thêm điều kiện bổ sung như tính trơn (smoothness) hoặc giới hạn phạm vi tìm kiếm.

Biểu thức	Ý nghĩa
$I_x u + I_y v + I_t = 0$	Ràng buộc đa thức hóa cục bộ dựa trên giả thiết cường độ không đổi
Giả thiết trơn (smoothness)	Đảm bảo véc-tơ chuyển động thay đổi liên tục trên vùng ảnh
Block matching	Giảm bài toán thành tìm khối tương đồng trong cửa sổ cố định

Thuật toán cơ bản

Các thuật toán ước lượng chuyển động phổ biến áp dụng mô hình toán học kèm điều kiện ràng buộc khác nhau:

Lucas–Kanade: Ước lượng quang học cục bộ bằng phương pháp bình phương nhỏ nhất (least squares) trên cửa sổ lân cận của mỗi điểm. Phù hợp khi chuyển động nhỏ và đồng nhất trong vùng cửa sổ (IEEE LK).
Horn–Schunck: Tối ưu toàn cục kết hợp điều kiện trơn, giải bài toán Euler–Lagrange để tìm véc-tơ chuyển động khớp nhất toàn bộ khung hình (IEEE HS).
Block Matching: Chia ảnh thành khối cố định, tìm khối trùng khớp nhất trong phạm vi tìm kiếm bằng SSD hoặc cross-correlation. Ưu điểm đơn giản, dễ triển khai trong nén video tiêu chuẩn nhưng đòi hỏi hiệu chỉnh tham số cửa sổ và phạm vi tìm kiếm.

Các thuật toán hiện đại thường kết hợp cơ chế đa quy mô (multi-scale) và pyramids để xử lý chuyển động lớn, đồng thời tận dụng GPU/FPGA để tăng tốc tính toán thực thời nhằm đáp ứng yêu cầu ứng dụng thực tế như phát trực tiếp (streaming) và AR/VR.

Đánh giá chất lượng và hiệu suất

Độ chính xác của ước lượng chuyển động thường được đánh giá bằng sai số góc (angular error) và sai số trung bình Euclid (endpoint error) so với ground truth, ví dụ như bộ dữ liệu Middlebury benchmark. Sai số trung bình dưới 1 pixel được xem là rất tốt đối với các thuật toán optical flow hiện đại.

Độ phức tạp tính toán của thuật toán được biểu diễn qua độ phức tạp thời gian O(N·k²) với N là số pixel và k là kích thước cửa sổ tìm kiếm đối với block matching. Các thuật toán global như Horn–Schunck có thêm chi phí xử lý ma trận lớn, trong khi Lucas–Kanade cục bộ có thể tối ưu hóa bằng phép tách chéo ma trận nhỏ.

Thuật toán	Độ chính xác (EPE trung bình)	Độ phức tạp	Khả năng chịu noise
Horn–Schunck	1.2 pixel	O(N·Iters)	Trung bình
Lucas–Kanade	0.9 pixel	O(N·w²)	Thấp
Block Matching	1.5–2.0 pixel	O(N·k²)	Thấp
PWC-Net	0.7 pixel	O(N·logN)	Cao

Khả năng chịu đựng biến động ánh sáng và nhiễu được cải thiện thông qua các kỹ thuật tiền xử lý như cân bằng histogram hoặc lọc Gaussian, đồng thời áp dụng normalization trong quá trình tính toán đạo hàm cường độ để giảm sai số do thay đổi điều kiện chiếu sáng.

Ứng dụng thực tiễn

Nén video: Tiêu chuẩn MPEG-4, H.264/AVC và H.265/HEVC sử dụng block-based motion estimation để dự đoán khung hình kế tiếp, giảm dữ liệu phải mã hóa và đạt tỷ lệ nén lên đến 50–70% so với phương pháp không dùng ước lượng chuyển động ITU-T H.264.

Chuyển động khung P và B (predictive, bidirectional) dựa trên motion vectors.
Adaptive search range và sub-pixel refinement để tăng độ chính xác.

Ổn định video: Optical flow cung cấp véc-tơ dịch chuyển camera, cho phép thuật toán bù đắp rung lắc và dịch chuyển ngẫu nhiên, nâng cao chất lượng hình ảnh trong drone, camera hành trình và livestream.

Video stabilization bằng khung tham chiếu trượt (sliding window reference frame).
Real-time implementation trên GPU bằng CUDA hoặc OpenCL.

Thực tế tăng cường (AR/VR): Theo dõi chuyển động đối tượng hoặc camera để ghép mô hình 3D chính xác vào cảnh thật. Motion estimation đóng vai trò then chốt trong head-tracking và object-tracking trên nền tảng ARKit, ARCore.

Thách thức và giới hạn

Vùng ảnh đồng nhất (homogeneous regions) thiếu đặc trưng khiến optical flow không xác định được véc-tơ chuyển động duy nhất, dẫn đến sai số đáng kể. Các biện pháp bổ trợ như regularization hoặc kết hợp thông tin color-consistency có thể giảm hiện tượng này nhưng làm tăng độ phức tạp.

Hiệu ứng che khuất (occlusion) xảy ra khi vật thể mới xuất hiện hoặc biến mất giữa hai khung mất tín hiệu tương ứng, gây ra các vùng invalid motion vectors. Giải pháp thường dùng là phát hiện occlusion dựa trên forward-backward consistency và loại bỏ điểm bất thường.

Các điểm occluded được đánh dấu và bỏ qua trong thuật toán global.
Phương pháp inpainting để tái tạo vùng thiếu vector.

Chuyển động phi cục bộ (deformation) như biến dạng mô, bong bóng nước hoặc cơ thể con người uốn cong không tuân theo mô hình rigid-body, đòi hỏi mô hình nâng cao hoặc deep learning để học được mẫu chuyển động phức tạp.

Công nghệ mới và hướng phát triển

Deep learning: Mạng neural tích chập (CNN) trong FlowNet và PWC-Net cho phép học trực tiếp từ dữ liệu cặp ảnh, đạt độ chính xác cao và khả năng generalize với nhiều kịch bản thực tế Dosovitskiy et al., 2015. Các kiến trúc mới như RAFT tối ưu hóa bước lặp, đạt EPE trung bình dưới 0.5 pixel trên KITTI dataset.

Phương pháp lai (hybrid): Kết hợp block-based với optical flow hoặc deep features để tận dụng ưu điểm ổn định của block matching và độ chi tiết của quang học, đồng thời giới hạn phần computation-heavy cho vùng cần độ chính xác cao.

Multi-scale pyramids để xử lý chuyển động lớn.
Feature pyramid và cost volume trong mạng học sâu.

Hardware acceleration: Triển khai thuật toán trên GPU, FPGA và NPU tích hợp trong thiết bị nhúng giúp đạt tốc độ real-time cần thiết cho AR/VR, drone và xe tự hành. Các thư viện như OpenVX và cuDNN hỗ trợ tối ưu hoá các phép toán convolution và reduction trọng số.

Danh mục tài liệu tham khảo

Horn B.K.P. & Schunck B.G. “Determining optical flow.” Artificial Intelligence, 16(1–3):185–203, 1981.
Lucas B.D. & Kanade T. “An iterative image registration technique with an application to stereo vision.” IJCAI, 1981.
Dosovitskiy A. et al. “FlowNet: Learning Optical Flow with Convolutional Networks.” ICCV, 2015. https://arxiv.org/abs/1504.06852
Pang J. et al. “RAFT: Recurrent All-Pairs Field Transforms for Optical Flow.” ECCV, 2020. https://arxiv.org/abs/2003.12039
ITU-T Rec. H.264 “Advanced video coding for generic audiovisual services.” 2003. https://www.itu.int/rec/T-REC-H.264