TỔNG QUAN VỀ VISUAL ODOMETRY VÀ STEREO CAMERA
Khái niệm Visual Odometry
Ước lượng chuyển động của camera, đặc biệt là camera stereo, đóng vai trò quan trọng trong lĩnh vực robot và các hệ thống hỗ trợ lái xe Ngoài ra, công nghệ này còn được ứng dụng trong nhiều hệ thống khác như hệ thống tự hành, định vị và xác định vị trí.
Việc xác định vị trí thường dựa vào cảm biến đo tốc độ bánh xe hoặc các thiết bị cảm biến IMUs Odometry là phương pháp xác định vị trí và hướng di chuyển của thiết bị thông qua việc đo vòng xoay của bánh xe Kỹ thuật odometry truyền thống được áp dụng chủ yếu cho các thiết bị có bánh xe hoặc di chuyển trên đường ray Tuy nhiên, hiện nay, odometry không còn phù hợp với các phương pháp điều khiển chuyển động không theo chuẩn, chẳng hạn như robot đi bằng chân.
Phương pháp odometry truyền thống gặp những vấn đề như sau:
Sự chính xác phụ thuộc vào độ chính xác của thiết bị đo vòng xoay của bánh xe rô bốt
Bề mặt mà rô bốt di chuyển phải phẳng
Bánh xe có thể bị trƣợt khi di chuyển trên sàn
Sai số về vị trí đƣợc tích lũy
Trong những năm gần đây, hệ thống camera đã trở nên rẻ hơn, nhỏ gọn hơn và có tốc độ xử lý nhanh hơn, cho phép chụp ảnh với tốc độ cao và xử lý ảnh thời gian thực Để ước lượng chính xác chuyển động của camera, chúng ta sử dụng phương pháp Visual Odometry, dựa trên các cặp ảnh liên tiếp Phương pháp này giúp khắc phục những nhược điểm hiện có trong việc theo dõi chuyển động.
Visual Odometry là kỹ thuật xác định vị trí và hướng di chuyển của robot thông qua việc phân tích liên tục các hình ảnh từ camera Phương pháp này không chỉ nâng cao độ chính xác trong chuyển động của robot mà còn cải thiện hiệu suất của các thiết bị điều khiển.
Trang 5 bị khác khi di chuyển trên bất kì bề mặt nào Visual Odometry đƣợc ứng dụng ngày càng rộng rãi trong các lĩnh vực nghiên cứu về người máy và thị giác máy tính Ƣớc lƣợng sự chuyển động của camera, đặc biệt là stereo camera, là một nhiệm vụ quan trọng trong lĩnh vực rô bốt và các hệ thống hỗ trợ người lái Nó còn là tiền đề cho những ứng dụng nhƣ phát hiện vật thể, hệ thống tự hành, hệ thống đồng thời xác định vị trí, vẽ lại quỹ đạo và rất nhiều những ứng dụng khác
Hầu hết các ứng dụng về Visual Odometry đều dựa vào thuật toán sau:
Đọc ảnh vào: có thể sử dụng một camera hoặc hai hay nhiều camera khác nhau
Hiệu ch nh lại ảnh vào cho phù hợp với từng phương pháp xử lí khác nhau
Phát hiện đặc điểm ảnh: định nghĩa những vùng cần thiết và bắt những điểm đặt trƣng thông qua các khung ảnh
Xác định sự tương quan giữa những đặc điểm bắt được ở những khung ảnh liên tiếp nhau
Dùng thuật toán để ƣớc lƣợng sự chuyển động của camera dựa vào mối tương quan ở trên
Dùng những bộ lọc để cập nhật hiệu ch nh để giảm sai số
Ta lập bảng so sánh các phương pháp định vị với nhau như sau:
Phương pháp Những ưu điểm Những nhược điểm
Positioning System) hệ thống định vị trí toàn cầu Độ chính xác cao
(1 cm) Thực hiện dễ dàng Giá thành vừa phải
Không làm việc trong nhà
Sóng siêu âm và hồng ngoại
Giá thành thấp Rất khó để có sự hoạt động ổn định của hệ thống
Có nhiều lỗi khác nhau Dùng tia Laser Độ chính xác cao
Visual Odometry Giá thành thấp
Có độ chính xác cũng khá cao
Việc thực thi gặp nhiều khó khăn
Ch vận hành trong những điều kiện có ánh sáng tương đối tốt
Stereo camera
Camera stereo là một thiết bị chụp hình sử dụng hai hoặc nhiều ống kính, mỗi ống kính được trang bị một cảm biến hình ảnh hoặc khung phim riêng biệt Nhờ vào cấu trúc này, camera stereo có khả năng mô phỏng chức năng của đôi mắt con người, cho phép ghi lại hình ảnh ba chiều sống động.
Hình 1.1: Ảnh thu đƣợc khi dùng một camera
Để phân biệt các điểm nằm trên cùng một đường thẳng, việc sử dụng một camera đơn lẻ là không đủ Do đó, cần sử dụng camera stereo để đạt được độ chính xác cao hơn trong việc nhận diện và phân tích hình ảnh.
Khoảng cách giữa hai ống kính của một camera Stereo tiêu biểu tương đương với khoảng cách giữa hai mắt của con người, khoảng 6.35 cm Hiện nay, có nhiều loại camera Stereo khác nhau trên thị trường.
Hình 1.2: Ảnh thu đƣợc khi dùng hai camera
Các mẫu stereo camera có thể dùng trong đề tài:
Hình 1.3: Các mẫu camera có thể dùng trong đề tài
Những ứng dụng Visual Odometry trên thế giới
1.3.1 Ứng dụng trong Mobile robot:
Visual Odometry đã đƣợc sử dụng một cách rộng rãi trong các ứng dụng về rô bốt
Hình 1.4: Mô hình rô bốt Các bước thực hiện Visual Odometry
Hình 1.5: Các bước thực hiện thuật toán Visual Odometry
Thuật toán SURF được áp dụng để xác định các điểm đặc trưng từ cặp ảnh trái phải Kích thước của vòng tròn biểu thị kích thước của các điểm đặc trưng được phát hiện Bên cạnh đó, thuật toán SURF có khả năng phân biệt giữa các điểm đặc trưng blob sáng trên nền tối (màu xanh) và các điểm đặc trưng blob tối trên nền sáng (màu đỏ).
Hình 1.6: Điểm đặc trƣng blob thu đƣợc khi dùng thuật toán SURF
Thực hiện matching các điểm đặc trƣng thu đƣợc:
Hình 1.7: Kết quả thu đƣợc sau khi thực hiện matching Kết quả thu đƣợc so sánh giữa visual odometry và GPS:
Hình 1.8: Sự dịch chuyển của camera và xây dựng 3D Sai số thu đƣợc khi thực hiện visual odometry:
1.3.2 Ứng dụng trong mô hình máy bay trực thăng tự điều khiển:
Hình 1.9: Mô hình máy bay trực thăng có ứng dụng Visual Odometry
Máy bay có khả năng di chuyển theo 6 bậc tự do, với một camera stereo được lắp đặt phía trước cơ cấu hạ cánh dài khoảng 50cm, đảm bảo độ chính xác cao cho mỗi chuyến bay.
Hình 1.10: Stereo camera trên máy bay
Bài viết này đề cập đến việc sử dụng bộ định vị toàn cầu GPS, thiết bị đo quán tính IMU và máy tính PC 104 chạy hệ điều hành Linux để xử lý ảnh Camera có tốc độ bắt ảnh 30 Hz, giúp nâng cao khả năng thu thập dữ liệu chính xác và hiệu quả.
Hình 1.11: Thuật toán điều khiển Kết quả ƣớc lƣợng khi ch dùng Visual Odometry:
Hình 1.12: Kết quả ƣớc lƣợng
1.3.3 Visual Odometry sử dụng Stereo camera
Sau khi phát hiện điểm đặc trƣng và tiến hành matching các điểm đặc trƣng ta thu đƣợc kết quả nhƣ sau:
Hình 1.13: Mô hình rô bốt và kết quả matching điểm đặc trƣng Thuật toán Visual Odometry
Thuật toán Visual Odometry ước lượng chuyển động bằng cách sử dụng các phương pháp như Harris, SIFT và SURF, kết hợp với odometry từ cảm biến ở bánh xe, cho ra các kết quả đáng chú ý.
Hình 1.15 trình bày sự so sánh các kết quả thu được từ việc áp dụng các thuật toán tương tự trong môi trường bên ngoài, cho thấy những kết quả đáng chú ý như sau.
Hình 1.16: Kết quả thu được khi rô bốt chạy ở môi trường bên ngoài
Bảng tổng hợp các kết quả thu đƣợc:
Bảng sai số sử dụng các thuật toán khác nhau khi ta cho rô bốt chạy thành một vòng kín với nhiều lần khác nhau:
Mục tiêu đề tài
Mục tiêu của nghiên cứu là phát triển hệ thống xử lý ảnh 3D tốc độ cao, nhằm nâng cao độ chính xác của hệ thống định vị 3D.
Hệ thống này đƣợc gắn vào đối tƣợng di động có chức năng xác định góc nghiêng 3D và vị trí 3D của đối tượng theo 3 phương x, y, z
Hệ thống hoàn thiện sẽ tích hợp các phương pháp như INS và GPS, mở rộng khả năng ứng dụng trong nhiều lĩnh vực phù hợp với điều kiện hiện tại và tiềm năng phát triển thực tiễn tại Việt Nam trong những năm tới.
Thiết bị y tế được gắn vào các khớp chính giúp thu thập thông tin quan trọng trong quá trình theo dõi và điều trị bệnh nhân sau chấn thương cơ và khớp Ngoài ra, thiết bị này cũng được sử dụng cho các vận động viên điền kinh để đánh giá sức mạnh và xác định những điểm cần cải thiện trong giai đoạn xuất phát và tăng tốc.
Rô bốt di động đóng vai trò quan trọng trong việc điều khiển và giám sát các hoạt động cấp phát thuốc trong bệnh viện, đồng thời thực hiện nhiệm vụ thăm dò tại những khu vực nguy hiểm như nhà máy điện nguyên tử và khu vực có bom khủng bố, nơi yêu cầu độ chính xác cao.
Giám sát đô thị và tài nguyên môi trường tại Việt Nam đang được cải thiện nhờ việc sử dụng máy bay không người lái Công nghệ này cho phép thu thập hình ảnh từ cùng một vị trí và độ cao vào nhiều thời điểm khác nhau, từ đó cung cấp dữ liệu chính xác phục vụ cho công tác quản lý và bảo vệ môi trường.
Công nghiệp đang nâng cao khả năng kiểm soát và giám sát cần cẩu dỡ hàng tại cảng, đồng thời cải thiện robot bốc dỡ hàng tự động trong kho hàng, yêu cầu cài đặt vị trí đầu tiên của lô hàng Trong lĩnh vực quân sự, việc phối hợp triển khai điều khiển và giám sát máy tên lửa cũng đang được chú trọng.
Các bước thực hiện mục tiêu của đề tài bao gồm
Đọc ảnh stereo đồng thời từ 2 camera dùng Visual studio 2010: độ phân giải
640 x 480 pixels và tốc độ khoảng 5 khung hình trong 1 giây
Hiệu ch nh ảnh đọc về để phù hợp với thuật toán
Phát hiện các điểm đặc trưng của ảnh và tìm mối tương quan các điểm đặc trƣng giữa những khung hình liên tiếp
Sử dụng Visual Studio 2010, bài viết trình bày cách lập trình thuật toán Gauss-Newton và RANSAC để ước lượng và tính toán khoảng dịch chuyển của camera Phương pháp này đạt độ chính xác với sai số khoảng 5%, dựa trên các thông số đã cho.
Tọa độ thiết bị theo các trục X,Y,Z
Giá trị các góc Pitch,Yaw,Roll
Tổng khoảng cách đã di chuyển
Trong bài viết này, chúng tôi sẽ vẽ lại quãng đường di chuyển của camera trên MATLAB và so sánh với quãng đường được ghi nhận từ dữ liệu GPS cùng với các cảm biến INS Việc so sánh này giúp đánh giá độ chính xác và hiệu suất của các phương pháp định vị khác nhau.
Những nội dung cần giải quyết
Sử dụng Matlab và Visual Studio 2010 trên máy tính để xử lý ảnh tính toán các thuật toán Visual Odometry Sau đây là công việc cần đƣợc giải quyết:
Develop a driver to connect the Bumblebee2 stereo camera to a computer using Visual Studio 2010 and the Triclops library Subsequently, program in MATLAB to simultaneously capture images from the left and right cameras at a rate of approximately five frames per second.
Đo đạc các thông số hiệu ch nh bên trong và bên ngoài của camera
Sử dụng phương pháp hai bộ lọc Corner detector và Blob detector để tìm kiếm điểm đặc trƣng của ảnh là các góc và blob
Dùng thuật toán Non-maximum để lọc các điểm góc và blob, loại bỏ các điểm đặc trƣng đã bắt đƣợc có mức xám thấp hơn ngƣỡng đã chọn
Thực hiện matching các điểm đặc trƣng giữa hai cặp ảnh trái phải liên tiếp nhau
Thực hiện thuật toán để loại bỏ outlier
Ƣớc lƣợng ma trận xoay và tịnh tiến của camera dùng thuật toán Gauss-Newton và Ransac
Các báo cáo nghiên cứu khoa học liên quan
Trong những năm gần đây, Visual Odometry đã thu hút sự quan tâm của nhiều nhà nghiên cứu trên toàn thế giới Trong tương lai, công nghệ này hứa hẹn sẽ được ứng dụng rộng rãi trong nhiều lĩnh vực của đời sống con người.
Các báo cáo khoa học liên quan đến đề tài này thường tập trung vào những nội dung sau:
- Xây dựng lại môi trường ba chiều từ stereo camera, tài liệu tham khảo số
- Định vị vị trí và vẽ lại quãng đường di chuyển của mobile robot, tài liệu tham khảo số [6], [7], [9], [15], [16], [18]
CƠ SỞ LÝ THUYẾT CỦA ĐỀ TÀI
Các khái niệm cơ bản trong xử lý ảnh
2.1.1 Phần tử ảnh (pixel) Ảnh trong thực tế là một ảnh liên tục về không gian và về giá trị độ sáng Để có thể xử lý ảnh bằng máy tính cần thiết phải tiến hành số hóa ảnh Trong quá trình số hóa, người ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hóa về không gian) và lƣợng tử hóa thành phần giá trị (rời rạc hóa biên độ giá trị) mà về nguyên tắc mắt thường không phân biệt được hai điểm kề nhau Trong quá trình này người ta sử dụng khái niệm pixel hay phần tử ảnh Như vậy ảnh là tập hợp của các pixel Mỗi pixel gồm một cặp tọa độ m, n và màu sắc Một pixel có thể lưu trữ 1, 4, 8 hay 24 bit
Tín hiệu ảnh thuộc loại tín hiệu đa chiều: tọa độ(x,y,z), độ sáng(λ), thời gian(t) Ảnh tĩnh trong không gian 2 chiều đƣợc định nghĩa là một hàm 2 biến
S(x,y), với S là giá trị biên độ (đƣợc biểu diễn bằng màu sắc) tại vị trí không gian
+ Ảnh tương tự S(x, y): (x,y) liên tục, S liên tục
+ Ảnh số S(m,n): (m,n) rời rạc, S rời rạc
Một bức ảnh, được cấu thành từ một tập hợp các điểm ảnh, có thể được phân chia thành các vùng ảnh nhỏ hơn gọi là ROIs (vùng quan tâm) Ảnh số trong không gian rời rạc được tạo ra từ ảnh tương tự trong không gian liên tục thông qua quá trình số hóa, mà có thể hiểu đơn giản là chuyển đổi các tín hiệu liên tục thành dạng số.
+Ảnh tương tự được chia thành M hàng, N cột
+ Giao của hàng và cột đƣợc gọi là: pixel
+ Giá trị biên độ của pixel tại tọa độ nguyên (m,n) là s(m,n): là trung bình độ sáng trong pixel đó S(m,n) ≤ L (L số mức xám dùng biểu diễn ảnh) M, N thường được
Trang 18 chọn là M=N=2K (K=8,9,10) L =2B , B là số bít mã hóa cho độ sáng (biên độ) mỗi pixel Ảnh số đƣợc biểu diễn bởi ma trận 2 chiều.Các phần tử của nó là biểu diễn cho các pixel số hóa Ta kí hiệu 1 ảnh số là S(M,N) Ta nói ảnh có độ phân giải
MxN Ký hiệu s(m,n) để ch ra một phần tử ảnh
Hình 2.1: Ảnh tương tự và ảnh số
Mức xám là kết quả của việc mã hóa cường độ sáng của từng điểm ảnh thành giá trị số thông qua quá trình lượng tử hóa Các phương pháp mã hóa kinh điển thường sử dụng 16, 32 hoặc 64 mức, trong khi mã hóa 256 mức là phổ biến nhất hiện nay.
= 256 nên mỗi pixel đƣợc mã hóa bởi 8 bit
Ảnh đen trắng bao gồm hai loại chính: ảnh nhị phân và ảnh đa cấp xám Ảnh nhị phân có hai mức giá trị, 0 và 1, trong khi ảnh đa cấp xám có nhiều hơn hai mức Số mức L trong ảnh được xác định dựa trên tiêu chí lượng tử hóa, thường được chọn là 32 hoặc 64.
128 và 256 Trong đó ảnh đa cấp xám 256 mức là ảnh có chất lượng cao và thường đƣợc sử dụng
Ảnh nhị phân mã hóa mỗi pixel trên một bit, trong khi ảnh xám với 256 mức sử dụng 1 byte (8 bit) Ảnh nhị phân có cấu trúc đơn giản, với các phần tử ảnh được xem như phần tử logic Loại ảnh này thường được sử dụng để phân biệt giữa ảnh và nền, cũng như để nhận diện biên và các điểm khác.
Hình 2.2: Dải phổ điện từ
Màu sắc của tia sáng là cảm giác mà nó tạo ra ở mắt người, trong khi màu sắc của vật thể phụ thuộc vào ánh sáng phát ra từ chúng trong dải phổ nhìn thấy Tùy thuộc vào ngữ cảnh, màu sắc có thể được diễn tả qua nhiều mô hình màu khác nhau, nhưng không có mô hình nào hoàn toàn đầy đủ cho mọi khía cạnh của màu Vì vậy, việc sử dụng các mô hình màu khác nhau là cần thiết để miêu tả các tính chất nhận biết khác nhau của màu sắc.
+ Mô hình màu RGB: ánh sáng Red, Green, Blue ứng dụng cho màn hình, Ti Vi + Mô hình HSV: Nhận thức con người
+ Mô hình CYK: Máy in
Chúng ta đi sâu vào một số mô hình màu sau:
According to Thomas's color theory proposed in 1802, all colors can be created by combining three primary colors: Red, Green, and Blue These colors form the foundation of the additive color system, known as RGB.
Trang 20 thống tọa độ Cartesian – hệ thống tọa độ Decac: mỗi màu cơ bản đều đƣợc mã hóa bởi 8 bit, vậy với ba màu phối hợp nhau tạo thành 256 3 = 16.777.216 màu thứ cấp mà mắt người có thể cảm nhận được Ảnh màu được lưu trữ từng màu riêng biệt nhƣ ảnh đa cấp xám Ứng với một pixel của ảnh màu sẽ chiếm 3 byte, do đó ảnh màu sẽ chiếm bộ nhớ gấp ba lần ảnh đa cấp xám cùng kích thước
Hình 2.3: Không gian màu và các màu cơ bản RGB
Hệ màu trừ bao gồm ba màu cơ bản: Xanh Lơ (Cyan), Tím (Magenta) và Vàng (Yellow), tương ứng với các màu bù trong không gian màu RGB Mối quan hệ giữa hai hệ màu này rất quan trọng trong lĩnh vực thiết kế và in ấn.
Hình 2.4: Các màu cơ bản của hệ màu CMY
Mô hình màu HSV (Hue, Saturation, Value) :
Dựa trên cảm nhận màu sắc của con người, ánh sáng màu được hình thành từ sự kết hợp của ánh sáng đơn sắc Mắt người có khả năng nhận biết hàng chục màu sắc nhưng lại có thể phân biệt tới hàng ngàn màu khác nhau Mô hình HSV được phát triển từ mô hình RGB; khi quan sát hình hộp RGB theo đường chéo từ trắng đến đen, ta có thể hình dung hình chóp nón, từ đó tạo ra hình nón trong mô hình HSV.
Hình 2.5: Không gian màu HSV
Có ba thuộc tính chủ yếu trong cảm nhận màu:
+ Hue: bước sóng của ánh sáng, được biểu diển bằng góc từ 0 0 – 360 0 giúp ta phân biệt các màu khác nhau
+ Saturation: độ bão hòa, đo độ tinh khiết của ánh sáng gốc S nằm trong khoảng [0-1]
+ Value (brightness): cường độ hay độ chói ánh sáng V có giá trị trong khoảng [0-1], V = 0 có màu đen
Mô hình HSV trực giác hơn mô hình RGB Bắt đầu từ Hue (H cho trước và
V=1, S=1) Thay đổi S: bổ sung hay bớt trắng; thay đổi V: bổ sung hay bớt đen đến khi có màu mong muốn
2.1.6 Các định dạng cơ bản
Kỹ thuật xử lý ảnh đã phát triển qua nhiều định dạng khác nhau, bao gồm ảnh đen trắng IMG, ảnh đa cấp xám và ảnh màu như PCX, GIF, JPEG Ảnh IMG là định dạng đen trắng với 16 byte đầu chứa thông tin cần thiết và được nén theo từng dòng Ảnh PCX, một trong những định dạng cổ điển, sử dụng mã RLE để nén dữ liệu nhưng không hiệu quả bằng IMG Ảnh GIF tiết kiệm không gian lưu trữ, với ảnh đen trắng có kích thước nhỏ hơn gốc từ 5-7 lần, nhưng hiệu quả nén kém với ảnh 256 màu Cuối cùng, ảnh JPEG sử dụng chuẩn nén cho ảnh tone liên tục và được ứng dụng rộng rãi trong lưu trữ ảnh, truyền thông, và y học.
Mô hình camera và hiệu ch nh các thông số
Ảnh PNG là định dạng hình ảnh sử dụng công nghệ nén dữ liệu tiên tiến, giúp bảo toàn thông tin gốc mà không làm mất dữ liệu Được phát triển để cải thiện và thay thế định dạng GIF, tập tin PNG bao gồm 8 byte ký hiệu với chữ “PNG” và 2 dấu xuống dòng, sắp xếp theo số lượng các thành phần, mỗi thành phần chứa thông tin về hình ảnh Cấu trúc này được thiết kế để đảm bảo tính tương thích với các phiên bản cũ khi sử dụng định dạng PNG.
2.2 Mô hình camera và hiệu chỉnh các thông số:
Một số thông số kỹ thuật của Bumblebee 2:
Mô hình camera đơn giản nhất là mô hình pinhole, trong đó ảnh của một điểm được tạo ra từ giao điểm của các tia sáng đi từ điểm đó đến tâm quang học và mặt phẳng ảnh.
Hình 2.6: Mô hình pinhole camera
Tiêu cự f là khoảng cách từ tâm quang học đến mặt phẳng ảnh, như thể hiện trong hình 2.1 Trong đó, Z là khoảng cách từ camera đến đối tượng, X là độ dài của đối tượng, và x là ảnh của đối tượng trên mặt phẳng ảnh Công thức liên quan là -x/f = X/Z.
Chúng ta sẽ tái cấu trúc mô hình camera pinhole thành một dạng mới để dễ dàng quan sát hơn Trong mô hình này, vị trí của tâm quang học và mặt phẳng ảnh sẽ được thay đổi, với sự khác biệt là đối tượng nằm cùng hướng với ảnh của nó trên mặt phẳng ảnh.
Hình 2.7: Mô hình mới của pinhole camera
Mỗi điểm trong không gian phát ra một tia sáng, và tất cả các tia sáng này hội tụ tại tâm quang học Đường thẳng từ tâm quang học vuông góc với mặt phẳng ảnh được gọi là trục quang, trong khi giao điểm giữa trục quang và mặt phẳng ảnh được gọi là điểm trực giao Ảnh của đối tượng chính là giao điểm của các tia sáng từ đối tượng đến tâm quang học trên mặt phẳng ảnh Trong tam giác đồng dạng, ta có mối quan hệ x f = X Z, và dấu âm biến mất khi ảnh của đối tượng đã được đảo ngược lên trên.
Theo lý thuyết, điểm trực giao được coi là trọng tâm của bức ảnh, nhưng thực tế cho thấy rằng trọng tâm này không nhất thiết phải nằm trên trục quang.
Trang 26 đinh nghĩa thêm 2 thông số mới là C x, C y để mô hình một tọa độ trên mặt phẳng ảnh Kết quả là một điểm Q trong không gian có tọa độ là (X, Y, Z) đƣợc chiếu lên mặt phẳng ảnh tại một điểm có tọa độ ( xscreen, y screen ) :
Công thức trên bao gồm hai tiêu cự khác nhau là f x và f y, vì ảnh có hình chữ nhật thay vì hình vuông, dẫn đến mỗi chiều có một tiêu cự riêng biệt.
2.2.3 Cơ bản về h nh học v ph p chiếu:
Quan hệ giữa một điểm trong không gian Q (X, Y, Z) và một điểm trên mặt phẳng ảnh q(x, y) được gọi là phép chiếu Để thuận tiện khi làm việc với phép chuyển đổi này, chúng ta sử dụng hệ tọa độ đồng nhất Hệ tọa độ đồng nhất biểu diễn một điểm trong không gian n chiều dưới dạng một vector (n + 1) chiều, ví dụ như (X, Y, Z) trở thành (X, Y, Z, W), với điều kiện rằng bất kỳ hai điểm nào có giá trị tỉ lệ thì chúng được coi là tương đương.
Trong trường hợp này, mặt phẳng ảnh được coi là không gian chiếu hai chiều, và các điểm trên mặt phẳng này sẽ được biểu diễn dưới dạng một vector ba chiều q.
Trong không gian chiếu, tất cả các điểm có giá trị t lệ tương đương, cho phép chúng ta khôi phục tọa độ pixel bằng cách chia cho q3 Điều này dẫn đến việc sắp xếp các thông số định nghĩa camera (f x, f y, C x, C y) thành một ma trận 3x3, được gọi là ma trận thông số camera Hình chiếu của các điểm trong không gian lên mặt phẳng ảnh được rút ra theo một dạng đơn giản.
] [ ] Nhân ra ta sẽ có w = Z và điểm q ở trong hệ tọa độ đồng nhất, ta nên chia với w (hay Z) để khôi phục lại tọa độ cũ
2.2.4 Sự biến dạng của thấu kính:
Mô hình pinhole lý tưởng cung cấp một cách nhìn hữu ích cho hình học 3D, nhưng thực tế, lượng ánh sáng đi qua pinhole rất hạn chế, dẫn đến việc phải chờ đợi lâu để tích lũy đủ ánh sáng cho một bức ảnh sử dụng được Đối với camera tốc độ cao, cần có sự hội tụ ánh sáng trên một diện tích rộng, với ánh sáng hội tụ tại tâm quang học Để đạt được điều này, việc sử dụng thấu kính là cần thiết, vì thấu kính có khả năng tập trung một lượng lớn ánh sáng vào một điểm, giúp tạo ra ảnh nhanh hơn, mặc dù điều này có thể gây ra một số biến dạng.
Trong lý thuyết, thấu kính được định nghĩa là không bị biến dạng, nhưng thực tế không có thấu kính nào lý tưởng do quá trình chế tạo Hai loại biến dạng thường gặp là biến dạng xuyên tâm và biến dạng tiếp tuyến Biến dạng xuyên tâm xảy ra khi các thấu kính camera làm biến đổi vị trí của các pixel gần cạnh ảnh, với hình ảnh minh họa cho thấy ánh sáng xa trung tâm hội tụ nhiều hơn ánh sáng gần Biến dạng này thường gặp ở camera giá rẻ và ít thấy ở camera chất lượng cao.
Hình 2.8: Biến dạng xuyên tâm
Trang 28 Đối với biến dạng xuyên tâm, sự biến dạng bằng 0 tại trung tâm của ảnh và tăng dần khi đi xa tâm Biến dạng xuyên tâm của ảnh được đinh dạng lại bằng phương trình sau:
Trong bài viết này, (x, y) đại diện cho vị trí ban đầu của điểm bị biến dạng trên ảnh, trong khi (xcorrect, ycorrect) là vị trí mới sau khi đã hiệu chỉnh sự biến dạng Hình 2.9 minh họa tọa độ của các điểm trên một lưới bị biến dạng theo kiểu xuyên tâm.
Hình 2.9: Biến dạng xuyên tâm càng nhiều đối với những điểm xa tâm ảnh
Hình học ảnh
Mặt phẳng ảnh nằm ở vị trí f dọc theo trục z
f đƣợc gọi là tiêu cự
2.3.1 Mối quan hệ giữa các hệ trục tọ độ
Hình 2.17: Mối quan hệ giữa các hệ trục tọa độ Tọa độ điểm 3 chiều (X,Y,Z) đƣợc chiếu thành điểm 2chiều (x,y)
Hình 2.18: Các bước tính được tọa độ điểm ảnh 2 chiều khi biết tọa độ 3 chiều
Hình 2.19: Các bước xây dựng tọa độ điểm 3D từ tọa độ điểm ảnh
2.3.2 Mối quan hệ giữa tọ độ camera và tọ độ mặt phẳng ảnh
Hình 2.20: Quan hệ giữa tọa độ của camera và tọa độ mặt phẳng ảnh
Từ quy tắc tam giác đồng dạng ta có:
2.4 Hệ tọ độ Homogeneous Để biểu diễn điểm hai chiều (x,y) bởi điểm ba chiều (x ’ , y ’ , z ’ ) ta thêm vào tọa độ thứ ba.Ta có mối quan hệ:
Ta suy ra đƣợc mối quan hệ giữa tọa độ ba chiều và tọa độ của camera
2.5 Mối quan hệ giữa tọ độ camera và tọ độ chuẩn
Hệ tọa độ camera và hệ tọa độ chuẩn liên hệ với nhau qua hai ma trận xoay và tịnh tiến:
Hình 2.21: Mối quan hệ giữa hệ tọa độ chuẩn và hệ tọa độ camera
2.6 Mối quan hệ giữa tọ độ mặt phẳng ảnh và tọ độ điểm ảnh
Thông số bên trong của camera mô tả phép biến đổi giữa hệ tọa độ mặt phẳng ảnh và tọa độ điểm ảnh
Hình 2.22: Mối quan hệ giữa hệ tọa độ điểm ảnh và hệ tọa độ mặt phẳng ảnh
O x và O y đƣợc gọi là tâm ảnh hay điểm chính
Trong một vài trường hợp một hay nhiều hệ tọa độ bị lật lại:
Hình 2.23: Mối quan hệ giữa hệ tọa độ điểm ảnh và hệ tọa độ mặt phẳng ảnh
2.7 thu êt về h nh học 3D
Giả sử chúng ta có một camera stereo với hai camera trái và phải được căn chỉnh đồng phẳng, đảm bảo rằng một điểm sẽ nằm trên cùng một hàng trong cả hai ảnh trái và phải, tương tự như kết quả đạt được sau quá trình chỉnh sửa stereo (stereo rectification) Cả hai camera này đều có cùng tiêu cự f l = f r.
Khi chọn một điểm P trong không gian, ta có thể xác định ảnh của điểm P trên hai camera trái và phải với tọa độ lần lượt là p l (x l, y) và p r (x r, y) Do hai điểm này nằm trên cùng một hàng, tọa độ y sẽ giống nhau Độ chênh lệch d (theo đơn vị pixel) giữa p l và p r được tính bằng d = x l - x r Từ độ chênh lệch d, ta có thể suy ra khoảng cách Z của điểm P đến camera Hình 2.23 minh họa rõ ràng cách tính khoảng cách Z dựa trên d thông qua tam giác đồng dạng.
Với T là khoảng cách giữa hai camera trái và phải, f là tiêu cự
Hình 2.24: Mối quan hệ giữa khoảng cách đến vật và disparity
Khoảng cách Z sẽ t lệ nghịch với độ chênh lệch d, khi d càng nhỏ thì khoảng cách Z càng lớn và ngƣợc lại
Khi có đƣợc khoảng cách Z thì việc xác định tọa độ X, Y của điểm P trở nên dễ dàng Nếu ta có một điểm có tọa độ pixel là ( x, y) thì :
Nếu chúng ta nắm rõ thông số của camera và độ chênh lệch d giữa một điểm trên hai ảnh trái và phải, ta có thể xác định tọa độ 3D của điểm đó.
Hình 2.25: Khoảng cách vật t lệ nghịch với độ chênh lệch d
Triclops là một thư viện do Point Grey, một trong những công ty hàng đầu thế giới về camera kỹ thuật số, phát triển Thư viện này được thiết kế nhằm cung cấp cho người dùng các hàm hữu ích để phân tích thông tin 3D từ ảnh của các camera stereo mà Point Grey cung cấp.
Trong thư viện Triclops, các thao tác như hiệu chỉnh stereo, chỉnh sửa dạng và tái lập stereo được thực hiện thông qua hàm triclopsStereo (TriclopsContext context) Biến context chứa đầy đủ thông tin về camera và các hình ảnh mà camera đã chụp Trước khi thực hiện hàm triclopsStereo, cần thiết lập một số thông số bằng các hàm quy ước Sau đó, người dùng chỉ cần gọi các hàm tương ứng trong thư viện để lấy thông tin cần thiết.
Trang 41 Để lấy một ảnh về ta dùng hàm : triclopsGetImage( const TriclopsContext context, TriclopsImageType imageType, TriclopsCamera camera, TriclopsImage* image );
Thông số quan trọng nhất trong việc lấy ảnh là imageType, xác định loại ảnh mà bạn muốn, bao gồm ảnh thô, ảnh đã qua hiệu chỉnh hoặc ảnh chứa thông tin về độ chênh lệch Thêm vào đó, thông số camera cho phép bạn chọn giữa camera bên trái hoặc bên phải để lấy ảnh.
Triclops còn hỗ trợ thêm hàm triclopsRCD16ToXYZ() để chuyển một điểm từ một điểm trong ảnh thành tọa độ 3D của chính điểm đó
Trong nhiều ứng dụng, việc hiểu mối quan hệ giữa các hình ảnh là rất quan trọng để trích xuất thông tin cần thiết Chẳng hạn, thông qua mối liên hệ giữa hai khung hình từ camera, ta có thể xác định được chuyển động, tốc độ của camera và khoảng cách từ camera đến các vật thể xung quanh.
Trong nhiều ứng dụng, mối quan hệ giữa các điểm quan trọng trong khung hình được sử dụng để tính toán mối quan hệ giữa các khung hình, giúp giảm thiểu thời gian tính toán Thay vì phân tích tất cả các điểm ảnh, thuật toán này tập trung vào các điểm góc, một yếu tố quan trọng được nhiều ứng dụng ưa chuộng.
2.9.1 Các ứng dụng sử dụng điểm đặc trƣng điểm góc:
Sử dụng đặc trưng góc để xác định mối quan hệ giữa các điểm ảnh trong các khung hình khác nhau là một bước quan trọng trong nhiều ứng dụng xử lý ảnh và thị giác máy tính.
Nhận dạng và phát hiện vật thể
Bám và vẽ quỹ đạo chuyển động
2.9.2 Những yêu cầu của phát hiện góc:
Tất cả “true corner” phải đƣợc phát hiện
Tất cả “false corner” phải đƣợc loại bỏ
Các điểm góc đƣợc định vị tốt
Bộ phát hiện góc có độ ổn định cao
Bộ phát hiện góc có khả năng chống lại nhiễu
Bộ phát hiện góc có khả năng tính toán nhanh
Hình 2.26: Các vị trí phát hiện góc
Bộ phát hiện góc bên trái trong hình có vị trí tốt hơn so với bộ phát hiện bên phải Mặc dù vị trí lý tưởng là điều mong muốn trong nhiều ứng dụng, nhưng trong một số trường hợp, như thuật toán phát hiện vật thể, vị trí cụ thể của tất cả các điểm góc trên vật thể lại không quá quan trọng.
Trong nhiều ứng dụng của rô bốt tự hành, việc xác định các điểm góc từ hình ảnh thu được từ camera là rất quan trọng để tìm ra mối quan hệ giữa chúng Tuy nhiên, chất lượng hình ảnh kém, ánh sáng không ổn định và sự thay đổi của môi trường xung quanh có thể gây ra sai lệch trong quá trình phát hiện góc.
Hình 2.27: Sự sai lệch trong phát hiện điểm đặc trƣng góc
Bộ phát hiện góc cần có khả năng khử nhiễu hiệu quả để xác định chính xác vị trí góc, ngay cả khi hình ảnh bị xoay.
Trong các ứng dụng yêu cầu xử lý thời gian thực, bộ phát hiện góc cần có thời gian tính toán nhanh chóng Do đó, nhiều ứng dụng thường sử dụng các bộ phát hiện góc đơn giản với hiệu suất cao Các loại góc khác nhau cũng được áp dụng để đáp ứng nhu cầu đa dạng của các bài toán thực tiễn.
Hình 2.28: Các phương pháp phát hiện góc Thời gian ra đời của các bộ phát hiện góc khác nhau:
Hình 2.29: Sự ra đời của các bộ phát hiện góc
2.9.3 Các phương pháp phát hiện góc:
Có ba phương pháp chính để phát hiện góc trong hình mức xám: mối quan hệ cạnh, phương pháp hình học và phương pháp tương quan.
Phương pháp mối quan hệ cạnh
2.9.4 Thuật toán phát hiện góc:
Các bước trong thuật toán phát hiện góc:
Áp dụng bộ dò tìm góc, quá trình này sẽ đọc ảnh và tính toán “cornerness measure” cho mỗi điểm ảnh “Cornerness measure” là chỉ số cho biết mức độ mà bộ dò tìm góc xác định một điểm ảnh có phải là góc hay không Thuật toán tạo ra một cửa sổ nhỏ với tâm là điểm ảnh cần tính toán, và kết quả cuối cùng sẽ là một tập hợp các điểm thỏa mãn “cornerness measure”, được gọi là bản đồ góc (cornerness map).
Thƣ viện triclops
Triclops là thư viện do Point Grey, một trong những nhà cung cấp camera kỹ thuật số hàng đầu thế giới, phát triển Thư viện này được thiết kế để hỗ trợ người dùng trong việc phân tích thông tin 3D từ các camera stereo của Point Grey, mang lại nhiều hàm hữu ích cho việc xử lý hình ảnh.
Trong thư viện Triclops, các thao tác như hiệu chỉnh stereo, chỉnh sửa hình dạng và tái định hình stereo được thực hiện thông qua hàm triclopsStereo (TriclopsContext context) Biến context chứa đầy đủ thông tin về camera và các bức ảnh mà camera đã chụp Trước khi thực hiện hàm triclopsStereo, cần định nghĩa một số thông số cần thiết Sau khi thiết lập, người dùng chỉ cần gọi các hàm tương ứng trong thư viện để lấy thông tin mong muốn.
Trang 41 Để lấy một ảnh về ta dùng hàm : triclopsGetImage( const TriclopsContext context, TriclopsImageType imageType, TriclopsCamera camera, TriclopsImage* image );
Thông số quan trọng nhất trong việc lấy ảnh là imageType, xác định loại ảnh mong muốn, bao gồm ảnh thô, ảnh đã hiệu chỉnh màu sắc và thẳng hàng, hoặc ảnh chứa thông tin về độ chênh lệch Thông số camera cho phép chọn camera bên trái hoặc bên phải để lấy ảnh.
Triclops còn hỗ trợ thêm hàm triclopsRCD16ToXYZ() để chuyển một điểm từ một điểm trong ảnh thành tọa độ 3D của chính điểm đó.
Phát hiện góc
Trong nhiều ứng dụng, việc hiểu mối quan hệ giữa các hình ảnh là cần thiết để trích xuất thông tin quan trọng Chẳng hạn, từ mối quan hệ giữa hai khung hình thu được từ camera, ta có thể xác định chuyển động, tốc độ của camera và khoảng cách từ camera đến các vật cản trong môi trường xung quanh.
Trong nhiều ứng dụng, việc tính toán mối quan hệ giữa các khung hình thường dựa vào các điểm quan trọng, giúp giảm thiểu thời gian xử lý Thay vì phải xem xét tất cả các điểm ảnh, thuật toán này cho phép xác định mối liên hệ dựa trên các điểm góc, một yếu tố quan trọng thường được sử dụng trong nhiều ứng dụng.
2.9.1 Các ứng dụng sử dụng điểm đặc trƣng điểm góc:
Sử dụng điểm đặc trưng làm góc để xác định mối quan hệ giữa các điểm ảnh trong các khung hình khác nhau là một bước quan trọng trong nhiều ứng dụng xử lý ảnh và thị giác máy tính.
Nhận dạng và phát hiện vật thể
Bám và vẽ quỹ đạo chuyển động
2.9.2 Những yêu cầu của phát hiện góc:
Tất cả “true corner” phải đƣợc phát hiện
Tất cả “false corner” phải đƣợc loại bỏ
Các điểm góc đƣợc định vị tốt
Bộ phát hiện góc có độ ổn định cao
Bộ phát hiện góc có khả năng chống lại nhiễu
Bộ phát hiện góc có khả năng tính toán nhanh
Hình 2.26: Các vị trí phát hiện góc
Bộ phát hiện góc bên trái trong hình có vị trí tốt hơn bộ phát hiện góc bên phải Mặc dù vị trí lý tưởng là điều mong muốn trong nhiều ứng dụng, nhưng trong một số trường hợp, như thuật toán phát hiện vật thể, vị trí chính xác của tất cả các điểm góc trên vật thể không phải là yếu tố quan trọng.
Trong các ứng dụng của robot tự hành, việc xác định các điểm góc từ hình ảnh camera là rất quan trọng để tìm ra mối quan hệ giữa chúng Tuy nhiên, chất lượng hình ảnh kém, ánh sáng không ổn định và sự thay đổi của môi trường xung quanh có thể gây ra sai lệch trong quá trình phát hiện góc.
Hình 2.27: Sự sai lệch trong phát hiện điểm đặc trƣng góc
Bộ phát hiện góc có thể xác định sai vị trí khi hình bị xoay, do đó cần phải có khả năng giảm thiểu ảnh hưởng của nhiễu.
Trong nhiều ứng dụng yêu cầu xử lý thời gian thực, bộ phát hiện góc cần có thời gian tính toán nhanh Do đó, người ta thường sử dụng các bộ phát hiện góc đơn giản để đáp ứng yêu cầu này Các loại góc khác nhau được áp dụng tùy thuộc vào từng ứng dụng cụ thể.
Hình 2.28: Các phương pháp phát hiện góc Thời gian ra đời của các bộ phát hiện góc khác nhau:
Hình 2.29: Sự ra đời của các bộ phát hiện góc
2.9.3 Các phương pháp phát hiện góc:
Có ba phương pháp chính để phát hiện góc trong hình mức xám, bao gồm mối quan hệ cạnh, phương pháp hình học và phương pháp tương quan.
Phương pháp mối quan hệ cạnh
2.9.4 Thuật toán phát hiện góc:
Các bước trong thuật toán phát hiện góc:
Bộ dò tìm góc sẽ đọc ảnh và tính toán "cornerness measure" cho mỗi điểm ảnh, cho biết mức độ mà điểm ảnh đó có thể là góc Thuật toán sử dụng một cửa sổ nhỏ với tâm là điểm ảnh cần phân tích, và kết quả sẽ là một bản đồ các điểm thỏa mãn tiêu chí cornerness measure, được gọi là cornerness map.
Ngưỡng Cornerness Map là một bộ phát hiện điểm góc, trong đó góc được định nghĩa là điểm lớn nhất cục bộ trong cornerness map Tuy nhiên, cornerness map có thể chứa nhiều điểm lớn nhất cục bộ với giá trị cornerness nhỏ, không phải là góc Để tránh nhận diện những điểm này là góc, cần thiết lập một ngưỡng cho cornerness map, trong đó các giá trị dưới ngưỡng sẽ được gán về 0 Việc chọn ngưỡng phụ thuộc vào từng ứng dụng và yêu cầu thử sai, với ngưỡng cần đủ cao để loại bỏ các local maximum không phải góc, nhưng cũng phải đủ thấp để giữ lại các local maximum đúng là góc Trong thực tế, không có ngưỡng nào hoàn hảo để loại bỏ tất cả các điểm không phải góc mà vẫn giữ lại các điểm góc, do đó giá trị ngưỡng phải được chọn dựa trên ứng dụng cụ thể.
Non-maximal Suppression là một thuật toán quan trọng trong việc xác định các điểm góc trong bản đồ cornerness Thuật toán này sẽ đặt giá trị cornerness của một điểm về 0 nếu giá trị này không lớn hơn giá trị cornerness của tất cả các điểm lân cận trong một khoảng cách nhất định Sau khi áp dụng thuật toán, các điểm góc được xác định sẽ là những điểm có giá trị cornerness khác không, giúp cải thiện độ chính xác trong việc phát hiện các đặc trưng hình ảnh.
Hình 2.30: Các bước trong thuật toán phát hiện góc
Hình 2.31: Ảnh minh họa thuật toán phát hiện góc
Thuật toán Non-Maximum Suppression
Non-maximum suppression là kỹ thuật được sử dụng để xác định các điểm tối đa trong một vùng của ảnh Thuật ngữ này lần đầu tiên xuất hiện trong lĩnh vực phát hiện cạnh, nhằm mục đích giảm độ dày của các cạnh, giúp chúng trở nên rõ ràng hơn trong ảnh đầu vào.
Ngƣỡng phân loại những điểm góc thu đƣợc
Tập hợp những điểm góc thu đƣợc
Những điểm góc thỏa mãn ngƣỡng
Dùng thuật toán Non-maximal Suppression
Thu đƣợc điểm góc mong muốn
Trang 46 một đường mỏng NMS sẽ theo một hướng vuông góc với cạnh Kitchen và Rosenfeld mở rộng NMS để phát hiện những điểm đặc trƣng trong hình theo hai chiều Điểm đặc trƣng đƣợc chọn ở đây là điểm góc
Non-maximum suppression là một bước xử lý quan trọng trong các ứng dụng thị giác máy tính, đóng vai trò là thuật toán tiền xử lý hiệu quả cho các hệ thống xử lý thời gian thực Thuật toán này không chỉ đơn giản mà còn dễ dàng áp dụng trong nhiều lĩnh vực khác nhau.
Thuật toán Non-maximum suppression (NMS) được tính toán bằng cách xác định Local Maximum lớn hơn tất cả các điểm ảnh xung quanh Đối với n điểm ảnh, số điểm ảnh lân cận theo một chiều là (2n+1), và trong mảng 2 chiều, số điểm ảnh lân cận là (2n+1) x (2n+1) NMS đóng vai trò quan trọng trong nhiều thuật toán thị giác máy tính, bao gồm xây dựng điểm 3 chiều và nhận dạng vật thể.
Thuật toán NMS hoạt động qua hai vòng lặp: vòng lặp ngoài quét qua tất cả các điểm ảnh và vòng lặp trong kiểm tra từng điểm ảnh với các điểm lân cận Khi một điểm ảnh lân cận có cường độ cao hơn cường độ chuẩn, vòng lặp trong sẽ kết thúc Thuật toán yêu cầu 2n phép so sánh cho mỗi điểm ảnh nếu không có sự thoát sớm Để phân tích độ phức tạp trung bình, ta xem xét xác suất p(i) cho việc vòng lặp trong thoát ở lần lặp thứ i, với điều kiện rằng điểm ảnh lân cận thứ i phải lớn nhất so với các điểm ảnh trước đó, bao gồm cả điểm ảnh chuẩn hiện tại.
Trong vòng lặp thứ hai, điểm ảnh hiện tại không được thoát ra trước vòng lặp thứ i, và điểm ảnh này phải lớn hơn những điểm ảnh đã được kiểm tra, điều này xảy ra với một xác suất nhất định.
Trong mỗi vòng lặp, có sự so sánh giữa điểm ảnh chuẩn và điểm lân cận thứ i, với tổng số i lần so sánh diễn ra trong vòng lặp thứ i Do đó, số lần so sánh cho mỗi điểm ảnh được xác định là:
2.10.1.2 B điểm lân cận Để đạt đƣợc kết quả tính toán tốt hơn trong NMS chúng ta xem x t với trường hợp số điểm lân cận nhỏ nhất cho ph p, điểm ảnh trung tâm ch cần được so sánh theo một hướng lân cận Thuật toán 1 đạt được độ tính toán tối ưu của sự so sánh một điểm ảnh trong trường hợp xấu nhất theo trên chúng ta cần tới 1.5 sự so sánh trên một điểm ảnh trong khi đó thuật toán 1 ch mất 0.815
Thuật toán 1 bắt đầu từ điểm ảnh bên trái ngoài cùng của ảnh, I[0],…I[W-1], tại hàng 1 với i=1 Nếu điểm ảnh i hiện tại có mức xám lớn hơn hai điểm lân cận trái và phải, thì local maximum đã được xác định Khi đó, nếu điểm ảnh i+1 nhỏ hơn điểm ảnh i lân cận trái, nó không thể là local maximum, và quá trình xử lý sẽ tiếp tục với điểm i+2.
Nếu điểm ảnh hiện tại có mức xám nhỏ hơn điểm bên phải, thì điểm bên phải sẽ trở thành điểm so sánh Thuật toán tiếp tục phân tích độ phức tạp để xác định xác suất p(B) của một dãy kích thước B và số lượng so sánh c(B) để tìm điểm cực đại địa phương Trong trường hợp đầu tiên, với kích thước dãy cố định là 2, có 2 sự so sánh Trong các trường hợp khác, thuật toán tăng i cho mỗi lần so sánh, và khi kiểm tra cuối cùng sai, i được tăng lên 2, dẫn đến số lần so sánh c(B) được tính toán.
Thuật toán 1: Một chiều NMS cho 3 điểm lân cận
Mũi tên trong hình minh họa sự so sánh giữa điểm ảnh hiện tại và các điểm lân cận Bắt đầu từ điểm đầu tiên, chỉ cần so sánh một lần với điểm được đánh dấu tròn là điểm lớn nhất, trong khi điểm lân cận bên phải sẽ bị làm mờ Thuật toán tiếp tục với điểm có giá trị 2, yêu cầu hai so sánh với điểm trước và sau Đồng thời, giá trị 1 bên phải cũng sẽ bị làm mờ vì nhỏ hơn giá trị 2 Mỗi điểm ảnh trong thuật toán này cần một sự so sánh.
Thuật toán 3 được hình thành từ việc khái quát hóa thuật toán 1 với n điểm lân cận Trong quá trình thực hiện, vòng lặp while-loop sẽ chia ngõ vào thành các khối động (dynamic blocks) tại mỗi thời điểm.
Trang 49 của cấu trúc một block phải thỏa mãn tính chất sau: trong một block có chính xác một local maximum i với ch những điểm lân cận trong block mới đƣợc xem xét và những điểm lân cận ngoài block sẽ bị bỏ qua
Thuật toán giữ lại điểm local maximum i trong block hiện tại và mở rộng block về phía bên phải cho đến khi bao gồm toàn bộ các điểm lân cận của điểm i Trong quá trình mở rộng, các điểm lân cận của i sẽ được kiểm tra, và block sẽ dừng lại khi tất cả các điểm lân cận đã được kiểm tra hoặc khi điểm lân cận lớn nhất của i vượt qua giá trị của i, trở thành điểm local maximum mới.
Trong khoảng từ a đến b, nếu i là một local maximum và nằm trong các điểm lân cận từ i - n (với a ≤ i - n), thì không cần kiểm tra lại Ngược lại, nếu a > i - n, cần phải kiểm tra lại và loại trừ các điểm lân cận bên trái từ i - n đến a - 1.
Tính toán điểm lớn nhất cục bộ:
8 if (chkpt ≤ j-n OR I[j] ≥ pmax[chkpt] )
Thuật toán 3: 1D N S cho (2n+1) điểm lân cận
Khó khăn của 2D NMS là nó không tách biệt Vì thế một giả thiết khác cần đƣợc đƣa ra
Tổng sai lệch tuyệt đối
Tổng sai lệch tuyệt đối là một thuật toán đơn giản và phổ biến được sử dụng để đo độ giống nhau giữa hai khối ảnh Thuật toán này hoạt động bằng cách tính toán sự sai lệch tuyệt đối giữa các điểm ảnh trong khối, sau đó tổng hợp sự khác nhau giữa các điểm ảnh để thực hiện so sánh.
Tổng sai lệch tuyệt đối là công cụ quan trọng được áp dụng trong nhiều lĩnh vực như nhận dạng vật thể, tính toán bản đồ disparity cho ảnh stereo và ước lượng chuyển động.
Sử dụng tổng sai lệch tuyệt đối để xác định phần ảnh tương đồng nhất với mẫu ảnh 3x3 trong ảnh có kích thước 3x5 điểm ảnh, với mỗi điểm ảnh có độ lớn từ 0 đến 9.
Trong ảnh, có ba vị trí cần tìm: bên trái, tâm và bên phải Để tính giá trị SAD, ta cần lấy giá trị tuyệt đối của sự khác nhau giữa các cặp điểm ảnh so sánh, ví dụ như sự khác nhau giữa 2 và 2 là 0,4, trong khi giữa 2 và 1 là 3,7.
8 là 1 Sau khi tính toán SAD ta sẽ thu đƣợc:
Tổng các vùng cho kết quả lần lượt là 20, 25 và 17, cho thấy phần bên phải ảnh tương đồng nhất với mẫu ảnh nhờ vào sự sai lệch nhỏ nhất.