AI Cho Mọi Người

AI Cho Mọi Người

Stereo matching

Stereo matching là một lĩnh vực nghiên cứu trong computer vision, nhằm tính khoảng cách từ camera đến các object. Stereo matching dùng hệ thống gồm 2 camera (gọi là stereo camera) để bắt trước cặp mắt của con người trong việc tính khoảng cách.

Thông tin về chiều sâu (hay khoảng cách tới các object) được ứng dụng rộng rãi trong xây dựng mô hình 3D, xe tự hành, và cho cả các ứng dụng khác trong computer visioin như tracking, detection, hay segmentation.

Hình sau mô tả tổng quan về stereo matching.

Stereo camera được dùng để chụp các ảnh trái và phải, gọi là cặp ảnh stereo. Cặp ảnh này chính là input cho thuật toán stereo matching để tìm depth map cho ảnh trái và ảnh phải. Depth map là một ảnh; trong đó giá trị của mỗi pixel là giá trị khoảng cách. Khi thiết lập hệ thống camera (gồm calibration và rectification) xong, chúng ta có thể ánh xạ pixel trong ảnh đến các vị trị trong không gian thực. Hình sau mô tả các bước cần thiết lập cho hệt thống stereo matching. Kết quả của bước stereo matching là disparity map, cho biết thông tin disparity cho tất cả pixel.

Ở bài đầu tiên học về stereo matching này, các bạn chỉ cần nhớ vài ý chính sau

– Stereo matching dùng stereo camera, là hệ thống gồm 2 camera.
– Depth map chứa khoảng cách cho mọi pixel của ảnh input.
– Stereo matching hiện được ứng dụng rộng rãi, và vẫn được tiếp tục nghiên cứu.
– Khi tìm hiểu về stereo matching, bạn sẽ gặp thuật ngữ disparity map. Disparity map chính là dạng ‘dữ liệu thô’ của depth map. Hai map này có thể chuyển đổi qua lại bằng một công thức đơn giản. Ở bài này, các bạn có thể coi 2 map này là như nhau.

Phát biểu bài toán: cho 2 ảnh trái và ảnh phải, với mỗi pixel p bên ảnh trái, tìm pixel tương ứng q bên ảnh phải. Biết rằng tọa độ dòng của 2 pixel bằng nhau (\(y_p = y_q\)) và tọa độ cột của q lệch trái tối đa là \(D\) (\(x_q = x_p – d\) với \(d \in [0, D]\)). Hình sau minh họa hai pixel tương ứng giữa cặp ảnh trái và phải.

Ở hình trên, hai pixel p và q là 2 pixel tương ứng nhau giữa cặp ảnh trái và phải. Hai điểm này có tọa độ \(y\) bằng nhau và tọa độ x khác nhau. Độ lệch giữa tọa độ x của pq chính là giá trị disparity cho pixel p của ảnh trái.

Phương pháp dựa vào pixel (SM1)

Giờ chúng ta lập luận và giải bài toán stereo matching. Từ ví dụ minh họa ở trên, chúng ta có thể quan sát thấy cặp điểm tương ứng (p, q) nên có màu như nhau, hay ít nhất là rất giống nhau. Một điểm ngoài không gian thực được chụp bởi 2 camera vào cũng một thời điểm, thì điểm này ở 2 ảnh trái phải nên có màu giống nhau.

Nghĩa là, với mỗi pixel p bên ảnh trái, chúng ta sẽ so sánh màu với D pixel q bên ảnh phải (vì \(x_q = x_p – d\) với \(d \in [0, D]\), nên ta có D pixel q để so sánh), vị trí nào cho màu giống nhau nhất, thì pixel đó là pixel tương ứng.

Từ lập luận trên ta xây dựng được công thức sau

$$
\begin{array}{l}
d_p = \mathop {\arg \min }\limits_{d \in D} \left( {C\left( {p,q} \right)} \right) \\
where\,\,\,C\left( {p,q} \right) = \left( {L(p) – R(q)} \right)^2 \\
and\,\,\,\,q = \left( {x_p – d,y_p } \right) \\
\end{array}
$$

trong đó, \(d_p\) là giá trị disparity tìm được cho pixel p; L và R là ảnh trái và ảnh phải; \(C\left( {p,q} \right)\) là cost function, tính độ khác nhau về màu giữa p và q; và D là disparity range, độ lệch tối đa giữa \(x_p\) và \(x_q\).

Chúng ta sẽ xử dụng cặp ảnh stereo, có tên là Tsukuba để kiểm tra thuật toán chúng ta sẽ cài đặt. Cặp ảnh Tsukuba gồm ảnh trái và ảnh phải, và ảnh ground truth dùng để so sánh với disparity map và đánh giá mức độ chính xác của các thuật toán stereo matching. Ảnh Tsukuba có chiều cao height = 288, chiều rộng width = 384, và disparity range = 16. Đây là các giá trị được cho trước với mỗi stereo matching dataset.

Các bạn download hình Tsukuba ở link sau
https://www.dropbox.com/s/d8xblp2k5xmzfbe/Tsukuba.zip?dl=0

 

Ý tưởng của phương pháp SM1 được minh họa ở hình sau

Mỗi pixel p bên ảnh trái sẽ được so sánh màu với các pixel q bên ảnh phải. Pixel q nào có cost nhỏ nhất thì q đó là pixel tương ứng với p. Từ đó tính được disparity cho pixel p bằng cách tính độ lệch tọa độ x giữa hai pixel tương ứng.

Chúng ta sẽ dùng ảnh grayscale thay cho ảnh màu để đơn giản hóa bài toán cũng như việc cài đặt. Việc thay đổi này không ảnh hưởng nhiều đến độ chính xác của thuật toán.

Source code cho thuật toán chúng ta vừa lập luận như sau

# aivietnam.ai
# simple stereo matching using pixel-wise matching

import numpy as np
from PIL import Image

def stereo_matching(left_img, right_img, disparity_range):
   
    # đọc ảnh trái và ảnh phải, rồi chuyển sang ảnh grayscale
    left_img  = Image.open(left_img).convert('L')
    left      = np.asarray(left_img)
    
    right_img = Image.open(right_img).convert('L')
    right     = np.asarray(right_img) 
    
    # cho trước chiều rộng và chiều cao của ảnh
    height = 288
    width  = 384
    
    # tạo disparity map
    depth = np.zeros((height, width), np.uint8)               
    scale = 255 / disparity_range
      
    for y in range(height):        
        for x in range(width):
            
            # tìm j tại đó cost có giá trị min
            disparity = 0
            cost_min  = (int(left[y, x]) - int(right[y, x]))**2
            
            for j in range(1, disparity_range):                
                cost = 255**2 if (x - j) < 0 else (int(left[y, x]) - int(right[y, x - j]))**2
                
                if cost < cost_min:
                    cost_min = cost
                    disparity = j
                            
            # đã tìm được j (lưu ở biến disparity) để cost min
            # gán j đó vào disaprity map
            # nhân cho scale để nhìn thấy rõ ràng (không cần scale cũng được)
            depth[y, x] = disparity * scale
                                
    # chuyển dữ liệu từ ndarray sang kiểu Image và lưu xuống file
    Image.fromarray(depth).save('disparity_map.png')
     
if __name__ == '__main__':
    disparity_range = 16 # cho cặp ảnh Tsukuba
    stereo_matching("left.png", "right.png", disparity_range)

 

Hình sau thể hiện kết quả disparity map cho chương trình trên

Kết quả rõ ràng không như chúng ta mong đợi. Nguyên nhân là quá trình chụp ảnh bị ảnh hưởng nhiễu từ rất nhiều yếu tố như ánh sáng, độ sáng, phản xạ ánh sáng vào 2 camera không giống nhau; thêm vào đó là nhiễu từ sensor ảnh,… làm cho điều giả định 2 pixel tương ứng có cùng màu không còn đúng trong thực tế.

Phương pháp dựa vào window (SM2)

Từ yếu điểm của phương pháp SM1, chúng ta có thể bắt chước các phương pháp trong thống kê để giảm nhiễu bằng cách dựa vào một pixel window thay vì chỉ một pixel đơn thuần. Nói cách khác, với mỗi pixel p, chúng ta sẽ lấy được một window \(W_p\) các pixel với tâm của W tại p. Tương tự, chúng ta sẽ tính được D window \(W_q\) bên ảnh phải.

Sau đó, chúng ta sẽ tính độ khác biệt về màu giữa các cặp window \((W_p, W_q)\). Pixel q cho cặp \((W_p, W_q)\) giá trị khác biệt nhỏ nhất là pixel tương ứng với p.

Công thức cho phương pháp dựa vào window như sau

$$
\begin{array}{l}
d_p = \mathop {\arg \min }\limits_{d \in D} \left( {C\left( {p,q} \right)} \right) \\
where\,\,\,C\left( {p,q} \right) = \sum\limits_{(u,v) \in (W_p ,W_q )} {\left( {L(u) – R(v)} \right)^2 } \\
and\,\,\,\,q = \left( {x_p – d,y_p } \right) \\
\end{array}
$$

Ý tưởng của SM2 được minh họa dùng cặp hình Tsukuba như sau

Mỗi pixel p bên ảnh trái, window \(W_p\) sẽ được tạo với tâm window ở vị trí pixel p.  Window \(W_p\) sẽ được  so sánh màu với các  window \(W_q\) có tâm tại pixel q bên ảnh phải. Window \(W_q\) nào có cost nhỏ nhất thì pixel q đó là pixel tương ứng với p. Từ đó tính được disparity cho pixel p bằng cách tính độ lệch tọa độ x giữa hai pixel tương ứng.

Source code cho thuật toán chúng ta vừa lập luận như sau

# aivietnam.ai
import numpy as np
from PIL import Image

def stereo_matching_ssd(left_img, right_img, kernel_size, disparity_range):
   
    # đọc ảnh trái và ảnh phải, rồi chuyển sang ảnh grayscale
    left_img  = Image.open(left_img).convert('L')
    left      = np.asarray(left_img)
    
    right_img = Image.open(right_img).convert('L')
    right     = np.asarray(right_img) 
    
    # cho trước chiều rộng và chiều cao của ảnh
    height = 288
    width  = 384
    
    # tạo disparity map
    depth = np.zeros((height, width), np.uint8)   
    
    kernel_half = int( (kernel_size-1) / 2)
    scale = 255 / disparity_range
      
    for y in range(kernel_half, height-kernel_half):  
        print(".", end=" ")
        
        for x in range(kernel_half, width-kernel_half):
            
            # tìm j tại đó cost có giá trị min
            disparity = 0
            cost_min  = 65534
            
            for j in range(disparity_range): 
                ssd = 0
                ssd_temp = 0 
                
                for v in range(-kernel_half, kernel_half):
                    for u in range(-kernel_half, kernel_half):
                        ssd_temp = 255**2 
                        if (x+u-j) >= 0:
                            ssd_temp = (int(left[y+v, x+u]) - int(right[y+v, (x+u) - j]))**2 
                        ssd += ssd_temp         
                
                if ssd < cost_min:
                    cost_min = ssd
                    disparity = j
            
            # gán j cho cost_min vào disaprity map
            depth[y, x] = disparity * scale
                                
    # chuyển dữ liệu từ ndarray sang kiểu Image và lưu xuống file
    Image.fromarray(depth).save('disparity_map_ssd.png')

if __name__ == '__main__':
    disparity_range = 16 # cho cặp ảnh Tsukuba
    kernel_size = 5
    stereo_matching_ssd("left.png", "right.png", kernel_size, disparity_range)

 

Hình sau thể hiện kết quả disparity map cho chương trình trên

Kết quả của phương pháp này cải thiện đáng kể so với phương pháp dựa vào pixel. Trong thực tế, các thuật toán còn sử dụng thêm các bước post-processing để tăng độ chính xác.

Vấn đề khi ảnh có độ sáng khác nhau

Kiểm tra thuật toán SM2 dùng các cặp ảnh Aloe. Ảnh Aloe có chiều cao height = 370, chiều rộng width = 427, và disparity range = 64. Các bạn có thể download ảnh ở link sau.

Các bạn download hình Tsukuba ở link sau
https://www.dropbox.com/s/ssw3dkq2o7bqsn0/Aloe.zip?dl=0

 

Kết quả cho cặp 1 (left image, right image 1): Hai ảnh trái phải có cùng độ sáng. Ở cặp ảnh này, SM2 có kết quả tốt như kỳ vọng. Những lỗi ở disparity map có thể loại bằng cách dùng thêm các phương pháp post-processing.

Kết quả cho cặp 2 (left image, right image 2): Hai ảnh trái phải không cùng độ sáng. Ở cặp ảnh này, SM2 không có khả năng xây dụng disparity map chính xác. Vấn đề nằm ở hàm cost \(C(p,q)\) đã không quân tâm đến vấn đề này khi thiết kế.

Kết quả cho cặp 3 (left image, right image 3): Hai ảnh trái phải không cùng độ sáng. Tương tự như trên, SM2 cho ra disparity map không chính xác. Hàm cost \(C(p,q)\) cần được thiết kế lại sao cho thuật toán làm việc được trong điều kiệu ánh sáng khác nhau giữa 2 ảnh trái và phải.

 

Bài tập 1: Tại sao kết quả cho cặp 2 và cặp 3 lại tệ như vậy so với kết quả cho cặp 1 . (Giải thích dựa vào hàm cost của SM2).

Bài tập 2 (kỹ thuật lập trình, khó): Hàm stereo_matching_ssd() cài đặt chưa tối ưu. Chương trình có thể chạy hết cả vài phút khi cho window_size lớn. Hãy phân tích vì sao chương trình chưa tối ưu và tìm cách khắc phục.

Anh em có thể chạy tay thuật toán SM2 sẽ thấy được vấn đề. Anh em cho window_size=3 để chạy tay cho nhanh.