Đặt vấn đề Qua phần tổng quan ta có thể thấy khả năng ứng dụng to lớn và đa dạng của công nghệ quét 3D, từ đó ta cũng thấy nhu cầu cần có một thuật toán cải thiện về độ chính xác và thời gian thực thi. Tuy nhiên, với rất nhiều thuật toán được phân tích trên, ta cần có một định hướng nghiên cứu rõ ràng. Trong quét 3D Bị động ta chia thành 2 phương pháp chính là Cục bô (Local) và Toàn cục (Global) và sẽ được phân tích chi tiết ở mục sau. Rõ ràng hai vấn đề cần quan tâm của quét và tái dựng 3D chính là độ chính xác và thời gian quét.
Mặc dù các thuật toán Toàn cục cho kết quả chính xác nhưng tài nguyên tính toán cao và khó để chuyển đổi thành các thuật toán song song. Đó là lí do trong khoảng thập niên gần đây, ta thấy sự chậm lại trong các công bố nghiên cứu cho giải thuật Toàn cục, tham khảo nền tảng trực tuyến Middleburry [6] để cập nhật các thuật toán mới. Ngược lại, ta lại thấy rất nhiều cải tiến được áp dụng cho các phương pháp Cục bộ, lí do bản thân các phương pháp này cần ít tài nguyên tính toán, thích hợp cho các ứng dụng thời gian thực, cùng với sự phát triển của các camera phân giải cao giúp tăng độ chính xác hơn rất nhiều. Vì lí do đó, luận văn tập trung vào nghiên cứu cải tiến phương pháp Cục bộ, cụ thể là sử dụng stereo camera.
Cho đến hiện nay, nhược điểm của stereo camera là khi quét những chi tiết có 4 Luận văn thạc sĩ Đỗ Ngọc Bình Phương đặc trưng bề mặt không rõ ràng sẽ cho kết quả không chính xác. Đồng thời, thời gian tính toán cho phương pháp cục bộ truyền thống khi áp dụng vào stereo camera cũng khá lâu do khoảng so sánh độ sâu (disparity range) khá lớn và phải được ước tính bởi người dùng. Bằng cách đề xuất một phương án kết hợp nhiều thuật toán hiện đại như: thuật toán dời ảnh [7], thuật toán học sâu HED (Holistically-nested- edge) [8] và phân tích superpixel [9] để tiền xử lý. Từ đó ứng dụng phương pháp Cục bộ lên kết quả đó để tận dụng khả năng tính toán đơn giản của phương pháp Cục bộ, và đồng thời cải thiện độ chính xác bằng cách tạo ra thêm nhiều đặc trưng trên bề mặt vật cũng như giảm thời gian tính toán.3 Chi tiết một số công trình nghiên cứu về stereo camera 1.
Định nghĩa stereo camera Nguyên lý chính của stereo camera là sử dụng “Thị giác hai mắt” (Binocular vision) [1]. Trong sinh học, đây là một dạng thị giác mà hai mắt người nhận biết chiều sâu dựa trên độ chồng lấp của hình ảnh ghi nhận từ mỗi mắt. Trong những năm gần đây, có rất nhiều các ứng dụng khai thác nguyên lý này, ví dụ như Thực tế ảo (Virtual reality) và được nhiều hãng công nghệ tên tuổi phát triển như Sony, Microsoft, Google, hay Facebook. Dựa trên nguyên lý này, stereo-camera sử dụng (a) (b) Hình 1.
Cách sắp xếp stereo camera (a) Trục các camera giao nhau (b) Trục các camera song song 5 Luận văn thạc sĩ Đỗ Ngọc Bình Phương hai cảm biến hình ảnh để ghi nhận chiều sâu của vật thể.5 cho thấy có hai cách sắp xếp stereo-camera như sau: Trong hai cách trên, cách sắp xếp hai camera song song với nhau được đề nghị vì sẽ cho độ chồng lấp hình ảnh nhiều nhất cũng như thuận tiện cho thuật toán tìm độ sâu. Khi hai camera không song song với nhau, một bước tiền xử lý cần được thực hiện gọi là Hiệu chỉnh (Rectification) để đưa cặp ảnh stereo về góc nhìn song song nhau. Sau khi hiệu chỉnh, công thức tìm độ sâu, theo [10] được đưa ra như sau: Hình 1. Biểu diễn hình học cho tính toán mô hình stereo camera Trong đó một điểm P bất kì trong không gian sẽ được chiếu tương ứng lên hai mặt phẳng ảnh của stereo-camera là PL và PR tương ứng ở ảnh trái và ảnh phải.
Hai điểm này được gọi là một cặp điểm tương ứng (corresponding points). Mặt phẳng được hình thành bởi tâm của hai camera và P là một mặt phẳng epipole. Các giao điểm của mặt phẳng này với hai mặt phẳng ảnh được gọi là đường epipolar. Ta có thể thấy một cặp điểm tương ứng của điểm P nằm trên các đường epipolar tương ứng ở mỗi ảnh.
Tuy nhiên, sẽ có một sự dịch chuyển vị trí, được gọi là độ chênh lệch (disparity). Giả sử gốc của hệ tọa độ nằm ở tâm của camera bên trái. Không mất tính tổng quát, áp dụng định lý Thales cho tam giác và đường song song với cạnh của tam giác, chúng ta có: 6 Luận văn thạc sĩ Đỗ Ngọc Bình Phương x xL (1. z f Áp dụng tương tự cho tam giác và đường thẳng x b xR (1.
z f Cuối cùng độ sâu được tính bằng công thức: bf bf (1.2 Hiệu chỉnh ảnh (Rectification) Như đã thể hiện ở trên, cặp điểm tương ứng của một điểm P tùy ý trên đối tượng sẽ nằm trên cặp đường thẳng epipolar tương ứng ở ảnh trái và phải. Tuy nhiên, trong Hình 1.7a, việc tìm các đường epipole tương ứng trong toàn bộ ảnh là một nhiệm vụ khó khăn. Quá trình hiệu chỉnh sẽ giúp biến đổi các hình ảnh sao cho các đường epipolar tương ứng sẽ song song với nhau (cùng tọa độ y), Hình 1. Do đó, vấn đề tìm kiếm disparity giảm từ việc tìm kiếm toàn bộ hình ảnh thành tìm kiếm trên từng dòng (có cùng toạ độ y).
Sẽ có những trường hợp không thể hiệu chỉnh ảnh, ví dụ các ảnh pushroom [11]. Các đường epipolar không thẳng mà là hyperbola. Tác giả [11] đã đề xuất phương pháp cộng gộp chi phí để khớp điểm từ 16 hướng để bao phủ hình ảnh 2 chiều. Tuy nhiên, hầu hết các trường hợp đều khả thi và nên hiệu chỉnh để giảm độ phức tạp tính toán.
Ảnh stereo (a) trước (b) sau hiệu chỉnh 7 Luận văn thạc sĩ Đỗ Ngọc Bình Phương Nghiên cứu cho thấy có nhiều phương pháp khác nhau để hiệu chỉnh hình ảnh. [12] liệt kê một số thuật toán như thuật toán Robert et al. [13] giảm thiểu sự biến dạng của tính trực giao xung quanh tâm của các bức ảnh; Hartley [14] giảm thiểu thị sai trong các điểm tương ứng được sử dụng cho quá trình hiệu chỉnh, phương pháp này được áp dụng cho thư viện stereoRectify-Uncalibrated () trong OpenCV; ngoài ra Loop và Zhang [15], đề xuất phân tách phép biến đổi thành ba bước nhỏ hơn: Biến đổi projective, Biến đổi similarity và biến đổi shearing, sau đó tối thiểu biến dạng của mỗi biến đổi. Mức độ biến dạng của ảnh khác nhau ở từng phương pháp.
Tuy nhiên, nhìn chung tất cả các thuật toán đều cố gắng hiệu chỉnh ảnh với độ biến dạng ít nhất và làm cho các đường epipolar ngang hàng với nhau (cùng toạ độ y).8 cho thấy kết quả thử nghiệm khi sử dụng phương pháp Hartley và Zhang, phương pháp Zhang cho độ biến dạng ít hơn, vì vậy ta sẽ sử dụng phương pháp Zhang để hiệu chỉnh và được trình bày chi tiết ở chương sau. Phương pháp (a) Hartley cho biến dạng (được khoanh tròn) (b) Zhang không cho biến dạng trên cùng ảnh đầu vào 1.3 Tìm các cặp điểm tương ứng Tìm kiếm đại lượng disparity là một quá trình tìm các cặp điểm tương ứng trong cặp ảnh stereo và ghi nhận độ lệch từ vị trí của chúng ở hai ảnh của camera trái và camera phải (Tạm gọi là trùng khớp điểm). Vấn đề này đã được các nhà khoa học nghiên cứu từ rất lâu trong lĩnh vực thị giác máy tính [16-17]. Số lượng các phương pháp vẫn đang tăng lên và được nền tảng trực tuyến được Middlebury stereo ghi nhận và đánh giá.
Việc đánh giá các phương pháp thường được thực hiện bằng cách so sánh disparity từ các ảnh ground truth (nghĩa là các hình ảnh có chiều sâu 8 Luận văn thạc sĩ Đỗ Ngọc Bình Phương thực tế) với disparity lấy được từ các thuật toán. Cách đánh giá này cũng sẽ được áp dụng ở phần đánh giá phương pháp trong luận văn này. Hiện tại, vẫn chưa có một phương pháp nào mang lại kết quả nhanh nhất và đáng tin cậy nhất, điều này mở ra cơ hội cho các nghiên cứu cải thiện hiệu suất và tốc độ của nó. Theo nghiên cứu của Scharstein [17] đã tổng quát hóa quy trình khớp điểm thành bốn bước: 1.
Tính toán chi phí để trùng khớp điểm, 2. Cộng gộp chi phí, 3. Tính toán chênh lệch / Tối ưu hóa và 4. Tinh chỉnh chênh lệch; trong khi Fuhr et al.
Tuy nhiên, dù cho là giải thuật Cục bộ hay Toàn cục thì cũng đều phải thực thi bốn bước trên. Kỹ thuật Cục bộ sử dụng thông tin xung quanh một pixel để tính toán độ chênh lệch của nó. Theo bốn bước trên, trong bước đầu tiên và thứ hai, các thuật toán thường dùng là độ lệch bình phương của cường độ ảnh (Squared intensity differences), chênh lệch cường độ ảnh tuyệt đối (Absolute intensity differences), Bình thường hóa tương quan chéo (Normalized cross-correlation) và chi phí trùng khớp nhị phân (Binary matching cost) [16]. Nhìn chung, thuật toán đại diện cho bước này và chủ yếu được sử dụng là Sum of absolute intensity differences – SAD).
Ví dụ: [18] đã sử dụng kỹ thuật này để tính chi phí phù hợp cho robot di động của họ. Công thức cho SAD được thể hiện như bên dưới: SAD( x, y, D) ( i , j )W ( x , y ) | I L (i, j ) IR (i D, j ) | .4) Trong phương trình trên, W ( x, y ) là một cửa sổ hình chữ nhật tạo bởi các pixel xung quanh pixel cần được xét; do đó kích thước ( x, y) là số nguyên lẻ. I (i, j ) là cường độ của một pixel tại tọa độ (i, j ) ; là sự chênh lệch về vị trí ở ảnh trái và ảnh phải của một pixel.9 đưa ra một ví dụ trực quan về trùng khớp điểm bằng phương pháp SAD [18]. Chi phí trùng khớp điểm là sự khác biệt tuyệt đối (absolute difference) của giá trị cường độ giữa các pixel (các pixel này được chuyển đổi thành ảnh xám greyscale) trong các cửa sổ tìm kiếm và bước cộng gộp là lấy tổng của các khác biệt này, vì vậy được đặt tên SAD.
Cuối cùng, hai pixel ở ảnh trái và ảnh phải 9 Luận văn thạc sĩ Đỗ Ngọc Bình Phương có SAD nhỏ nhất (trong số các pixel nằm trong khoảng disparity range được xét) sẽ là hai pixel tương ứng (Phương pháp chọn này được gọi là phương pháp Winner- Take-all).