Nâng cao chất lượng thuật toán lan truyền tin cậy xác định bản đồ sai lệch ứng dụng cho thị giác robot

Nghiên cứu khoa học công nghệ<br /> <br /> NÂNG CAO CHẤT LƯỢNG THUẬT TOÁN LAN TRUYỀN TIN CẬY<br /> XÁC ĐỊNH BẢN ĐỒ SAI LỆCH ỨNG DỤNG CHO THỊ GIÁC ROBOT<br /> Đoàn Văn Tuấn1*, Bùi Trung Thành2<br /> Tóm tắt: Trong bài báo này, chúng tôi đề xuất một phương pháp kết hợp giữa<br /> thuật toán CSBP (Constant Space Belief Propagation) và thuật toán cục bộ CT<br /> (Census Transfrom). Điểm khớp trung tâm ảnh camera kép (Stereo Camera) được<br /> xác định bằng thuật toán CT. Từ điểm khớp trung tâm, chúng tôi chia ảnh thành 4<br /> phần và mỗi phần sẽ thực hiện lan truyền tin cậy dùng thuật toán CSBP với điểm<br /> khớp ban đầu là điểm khớp trung tâm. Với phương pháp đề xuất này cho kết quả<br /> thực hiện bản đồ sai lệch có tin cậy cao hơn và hiệu năng thực hiện nhanh 2,4 lần<br /> so với thuật toán CSBP.<br /> Từ khóa: Bản đồ sai lệch, Thị giác robot, Lan truyền tin cậy với không gian cố định, Biến đổi kiểm kê,<br /> Camera kép.<br /> <br /> 1. MỞ ĐẦU<br /> Bản đồ sai lệch là thông số rất quan<br /> trọng trong thị giác robot (Robot<br /> Vision). Từ thông tin bản đồ sai lệch,<br /> robot xác định được ảnh 3D và bản đồ<br /> độ sâu của vật và được ứng dụng trong<br /> công nghiệp 4.0 [1]. Trong công nghiệp<br /> 4.0, robot dần thay thế sức lao động của<br /> con người, do vậy, con người mong<br /> muốn tạo hệ thị giác robot như hệ thị<br /> giác con người thông qua hệ camera kép<br /> Hình 1. Mô hình ảnh camera kép.<br /> (Stereo Camera) [2]. Camera kép như<br /> hai mắt người. Nguồn tài nguyên bộ nhớ của robot có hạn nên các thuật toán thực hiện bản<br /> đồ sai lệch của hệ camera kép phải tự cân bằng các tiêu chí về độ tin cậy, hiệu năng thực<br /> hiện và yêu cầu tài nguyên bộ nhớ. Tùy theo từng công việc cụ thể thì thị giác robot sẽ lựa<br /> chọn thuật toán thực hiện bản đồ sai lệch có ưu điểm về độ tin cậy, hiệu năng thực hiện và<br /> yêu cầu bộ nhớ. Sẽ rất khó có giải pháp thực hiện tốt được độ tin cậy cao, hiệu năng thực<br /> hiện nhanh và yêu cầu bộ nhớ thấp.<br /> Thị giác robot yêu cầu thực hiện nhanh theo thời gian thực thì các thuật toán thực hiện<br /> bản đố sai lệch của camera kép có mật độ thưa thớt (Sparse) được lựa chọn như thuật toán<br /> SIFT [3] và SURF [4] thường được ứng dụng cho SLAM (Simultataneous Localization<br /> and Mapping). Các thuật toán này có độ tin cậy thấp, số lượng điểm khớp khoảng 30% của<br /> ảnh camera kép bù lại tốc độ thực hiện nhanh và yêu cầu bộ nhớ thấp. Các thuật toán thực<br /> hiện bản đồ sai lệch của camera kép có mật độ phân theo đoạn (Segmentation) [5] thường<br /> cân bằng giữa độ tin cậy, hiệu năng thực hiện và yêu cầu bộ nhớ. Để đáp ứng được độ tin<br /> cậy cao thì thuật toán thực hiện trên camera kép có mật độ dầy đặc (Dense) như thuật toán<br /> SAD [6], CT [7], và BP [8]. Ngoài ra, có một số thuật toán kết hợp giữa thuật toán toàn<br /> cục và thuật toán cục bộ như [9]. Các thuật toán này có độ tin cậy cao nhưng chưa đáp ứng<br /> về hiệu năng cũng như yêu cầu về bộ nhớ. Hiện nay, thuật toán cục bộ đã được một số nhà<br /> sản xuất thực hiện hệ camera kép thương mại như ZED [10].<br /> Thuật toán BP (Belief Propagation) thực hiện dựa trên các vòng lặp và cho độ tin cậy<br /> cao đối với ảnh camera kép có mật độ dầy đặc. Tuy nhiên, thuật toán BP có nhược điểm là<br /> độ phức tạp của tính toán cao và yêu cầu bộ nhớ lớn. Để khắc phục nhược điểm này cần<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 111<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> phải giảm độ phức tạp của tính toán, giảm yêu cầu về bộ nhớ và xử lý song song, tuy nhiên<br /> đều phải trả giá về độ tin cậy. Các thuật toán BP nâng cao được thực hiện song song trên<br /> nền hệ thống nhúng GPU [11] hay FPGA [12]. Đa số các thuật toán BP cải tiến đều thực<br /> hiện trên cấu trúc ảnh dạng lưới với 4 kết nối cho một điểm ảnh.<br /> Trong các thuật toán BP cải tiến, thuật toán CSBP (Constant Space Belief Propagation)<br /> [13] của Yang đã giảm 12,5% yêu cầu bộ nhớ và tăng hiệu năng thực hiện so với thuật<br /> toán BP tiêu chuẩn. Điểm nổi bật của thuật toán CSBP là cố định các mức sai lệch được<br /> chọn cho vòng lặp, do vậy, bộ nhớ sẽ phụ thuộc vào số mức sai lệch được chọn mà không<br /> phụ thuộc vào các mức sai lệch của ảnh camera kép. Điểm hạn chế của thuật toán CSBP là<br /> tăng độ phức tạp tính toán và giảm độ tin cậy so với thuật toán BP.<br /> Để khắc phục nhược điểm của thuật toán CSBP, chúng tôi đề xuất một giải pháp sau,<br /> thay vì điểm khớp xuất phát ban đầu thường được chọn là điểm khớp trên cùng bên trái<br /> của ảnh camera kép bằng điểm khớp tại trung tâm của ảnh. Điểm khớp trung tâm của ảnh<br /> camera kép được xác định dùng thuật toán cục bộ CT (Census transform). Thuật toán CT<br /> có hàm biến đổi mạnh và không phụ thuộc cường độ ánh sang của ảnh [14]. Khi đã xác<br /> định được điểm khớp trung tâm, chúng tôi chia ảnh thành 4 phần và coi điểm khớp trung<br /> tâm là điểm khớp xuất phát thông điệp ban đầu cho mỗi phần và lan truyền tin cậy với số<br /> mức sai lệch được lựa chọn cố định. Thuật toán đề xuất có ưu điểm là tăng được tốc độ<br /> thực hiện và nâng cao được độ tin cậy so với thuật toán CSBP.<br /> Phần còn lại của bài báo được tổ chức như sau: phần 2 trình bày một số kiến thức liên<br /> quan đến thuật toán thực hiện bản đồ sai lệch như CSBP và CT. Phần 3 đề xuất thuật toán<br /> kết hợp giữa CSBP và CT. Kết quả thực nghiệm đưa ra trong phần 4; Kết luận được cho<br /> trong phần 5.<br /> 2. CÁC NGHIÊN CỨU LIÊN QUAN<br /> Bảng 1 sau đây liệt kê một số kí hiệu được sử dụng trong bài báo này.<br /> Bảng 1. Các kí hiệu và định nghĩa của nó.<br /> Kí hiệu Định nghĩa<br /> G Mô hình đồ thị biểu diễn bản đồ sai lệch của ảnh camera kép.<br /> V Tập các nút trên mô hình đồ thị (nút biểu diễn sự sai lệch của cặp ảnh<br /> tương đồng trong ảnh camera kép).<br /> E Tập các cạnh trên mô hình đồ thị (cạnh biểu diễn năng lượng chi phí<br /> cuat nút với các nút lân cận của nó).<br /> i,j Biểu diễn nút thứ i và nút lân cận i.<br /> Xi Biến ngẫu nhiên của nút i.<br /> xi Sự chuẩn hóa của Xi và Xi là không gian trạng thái của xi (xiϵ Xi)<br /> X Biến ngẫu nhiên liên kết x.<br /> x Sự chuẩn hóa các giá trị mô hình đồ thị trong không gian X<br /> p(x) Xác xuất hậu nghiệm (posterior) MAP.<br />  i (x i ) Xác suất nút i.<br />  ( xi , x j ) Xác suất nút i với nút j lân cận nút i.<br /> E(x) Năng lượng chi phí<br /> D(xi) Hàm năng lượng chi phí cho nút i<br /> V ( xi , x j ) Hàm năng lượng chi phí giữa nút i và nút j lân cận<br /> <br /> mit j ( x j ) Thông điệp chuyển từ nút i sang nút lân cận j.<br /> <br /> <br /> <br /> <br /> 112 Đ. V. Tuấn, B. T. Thành, “Nâng cao chất lượng thuật toán… ứng dụng cho thị giác robot.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> bj ( x j ) Độ tin cậy nút j<br /> c Tỉ lệ tăng của hàm nhẵn<br /> d Ngưỡng dừng tăng của hàm nhẵn<br /> k Số mức sai lệch được lựa chọn<br /> E(i)\j Tập các nút i ngoài trừ nút j.<br /> dC(x,y) Bản đồ sai lệch thực hiện<br /> dT(x,y) Bản đồ sai lệch mẫu<br /> 2.1. Thuật toán CSBP<br /> Thuật toán CSBP là thuật toán suy diễn lặp gần đúng dựa trên trường ngẫu nhiên<br /> Markov với không gian mức sai lệch cố định [13]. Xét mô hình trường ngẫu nhiên Markov<br /> (Markov Random Filed: MRF) như hình 2, trong đó, G = (V, E), x= (xi)iϵV và X = (Xi)iϵV.<br /> Từ [8] và bảng 1, xác suất hậu nghiệm (Posterior) MAP được xác định:<br /> p( x)   ( xi )   ( xi , x j ) (1)<br /> iV iV jV / i<br /> <br /> Từ phương trình 1 chúng ta xác định được MAP (Maximum a Posterior) thông qua<br /> phương pháp tích cực đại (Max-Product). Phương pháp tích cực đại tương đương với<br /> phương pháp tổng cực tiểu (Min- Sum). Đối với phương pháp tổng cực tiểu chúng ta đi tìm<br /> năng lượng chi phí cho việc chuyển thông điệp giữa các nút từ đó chúng ta sẽ tìm cách tối<br /> thiểu hóa năng lượng chi phí.<br /> E ( p( x))    log ( xi )    log  ( xi , x j ) (2)<br /> iV i , jE<br /> Chúng ta đơn giản E(p(x)) thành E(x), khi đó, hàm năng lượng được viết:<br /> E ( x)   D( xi )   V (x , x ) i j (3)<br /> iV i , jE<br /> Trong thị giác nổi, các nút là các biến ngẫu nhiên, nó biểu diễn cho mức sai lệch của hai<br /> điểm ảnh trên ảnh camera kép tương ứng. Hàm năng lượng chi phí của cặp nút đến các điểm<br /> lân cận dựa trên sự khác nhau giữa các nút. Do vậy, hàm năng lượng được xác định là:<br /> V ( xi , x j )  V ( xi  x j ) (4)<br /> E ( x)   D( xi )   V (x  x ) i j (5)<br /> iV i , jE<br /> Thông điệp cập nhật tại vòng lặp t được xác định là:<br /> mit j ( x j )  min(V ( xi  x j )  Di ( xi ) <br /> xi<br /> <br /> sE ( i )\ j<br /> mst 1i ( xi )) (6)<br /> <br /> Sau T vòng lặp thì độ tin cậy của mỗi nút là:<br /> bj ( x j )  Dj ( f j )  m<br /> iN ( j )<br /> T<br /> i j ( x j ) (7)<br /> <br /> *<br /> Nút x j được lựa chọn và xác định theo<br /> công thức:<br /> x*j  arg min b j ( x j ) (8)<br /> Thông thường hàm năng lượng chi phí nhẵn<br /> được xác định theo mô hình tuyến tính. Hình 2. Mô hình MRF.<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 113<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> V ( xi  x j )  min(c xi  x j , d ) (9)<br /> Khi đó, thông điệp cập nhật được xác định:<br /> mit j ( x j )  min(min(c xi  x j , d )  Di ( xi ) <br /> xi<br /> <br /> sE ( i )\ j<br /> mst 1i ( xi )) (10)<br /> <br /> 2.2. Thuật toán CT<br /> CT là thuật toán biến đổi kiểm kê cục bộ không tham số, không phụ thuộc vào điều<br /> kiện ánh sáng của ảnh [14]. Nguyên lý hoạt động của CT là biến đổi mỗi điểm ảnh thành<br /> một chuỗi bít có độ dài N bít với kiến trúc không gian cục bộ. Đối với mỗi điểm ảnh lân<br /> cận ngoại trừ điểm trung tâm sẽ biến đổi tương ứng thành một bít trong chuỗi N bít theo<br /> ngưỡng nếu giá trị cường độ (Intensity) bít lân cận lớn hơn giá trị cường độ bít trung tâm<br /> thì tương ứng với bít bằng 1, ngoài ra thì bít bằng 0.<br /> <br /> <br /> <br /> <br /> 85<br /> <br /> <br /> <br /> <br /> Hình 3. Biến đổi kiểm kê với cửa sổ 3x3 và khoảng cách Hamming.<br /> Hình 3 mô tả thuật toán CT với cửa sổ 3x3, giá trị cường độ điểm trung tâm là 35. Các<br /> điểm lân cận có giá trị lớn hơn 35 thì tương ứng với bít bằng 1 ngoài ra thì bít bằng 0.<br /> Thực hiện biến đổi CT ảnh trái và ảnh phải được hai chuỗi bít, so sánh hai chuỗi bít và<br /> đếm số bít khác nhau hai chuỗi bít được gọi là khoảng cách Hamming [15] và được tính<br /> theo công thức (11). Hai điểm ảnh của hai ảnh trái và phải có khoảng cách Hamming nhỏ<br /> nhất được chọn là khớp nhau.<br /> ( x0 , y0 )  arg min Hamming(TL ( x, y), TR ( x  d , y)) (11)<br /> ( x, y )<br /> <br /> trong đó, TL(x, y) và TR(x, y) là các chuỗi bít của điểm ảnh khớp trong ảnh trái và ảnh phải<br /> của ảnh camera kép.<br /> 3. ĐỀ XUẤT THUẬT TOÁN KẾT HỢP<br /> 3.1. Mô tả thuật toán đề xuất<br /> Khi điểm xuất phát ban đầu để lan truyền tin cậy không khớp dẫn đến yêu cầu chi phí<br /> năng lượng lớn và độ tin cậy thấp khi thực hiện bản đồ sai lệch như hình 4.d.<br /> <br /> <br /> <br /> <br /> (a) (b) (c) (d)<br /> Hình 4. Ảnh hưởng của điểm khớp ban đầu: (a) Ảnh camera kép trái,<br /> (b) Ảnh camera kép phải, (c) Bản đồ sai lệch mẫu và (d) Bản đồ sai lệch.<br /> <br /> <br /> 114 Đ. V. Tuấn, B. T. Thành, “Nâng cao chất lượng thuật toán… ứng dụng cho thị giác robot.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Để khắc phục nhược điểm này, chúng tôi đề xuất điểm khớp xuất phát là điểm khớp<br /> trung tâm của ảnh camera kép. Điểm khớp trung tâm của ảnh camera kép được xác định<br /> dùng phương pháp biến đổi kiểm kê. Sau khi đã xác định được điểm khớp trung tâm,<br /> chúng tôi chia ảnh thành 4 phần và coi điểm khớp trung tâm là điểm khớp ban đầu để lan<br /> truyền tin cậy cho mỗi phần. Tại mỗi phần, ảnh camera kép được chia thô tới mịn mức 2<br /> như hình 5, quá trình này làm giảm số lượng ảnh đi 4 lần. Khi chia thô tới mịn mức 2 thì<br /> năng lượng chi phí cho mỗi mức chia được tính theo công thức (12). Số lượng mức sai<br /> lệch được lựa chọn D = 100 mức, có nghĩa là khi mức sai lệch của ảnh camera kép tăng<br /> lên thì hiệu năng thực hiện và yêu cầu về bộ nhớ không đổi (các mức sai lệch của ảnh<br /> camera kép lớn hơn D mức).<br /> E ( x)   D( x )<br /> i[1,4]<br /> *<br /> i (12)<br /> <br /> Tại mỗi mức sai lệch được lựa chọn, thông điệp được lan truyền tin cậy giữa các nút<br /> như hình 6 và đồng thời thực hiện CSBP cho cả bốn phần nhờ vào cấu trúc xử lý song<br /> song như phần cứng GPU và phần mềm CUDA.<br /> <br /> <br /> <br /> <br /> Hình 5. Chia thô tới mịn mức 2. Hình 6. Sơ đồ thông điệp lan truyền.<br /> 3.2. Chương trình đề xuất<br /> Thuật toán đề xuất CTCSBP (Census Transform Constant Space Belief Propagation)<br /> Đầu vào: Ảnh camera kép có độ phân giải cao (M, N, D =100, c = 10, d = 0.7).<br /> Đầu ra: Bản đồ sai lệch ảnh camera kép có mật độ dầy đặc (M, N).<br /> Các bước thực hiện:<br /> 1. Xác định điểm khớp trung tâm ảnh camera kép dùng thuật toán CT theo công thức (11)<br /> với cửa sổ 5x5.<br /> 2. Từ điểm khớp trung tâm, chia ảnh thành 4 phần và lấy điểm khớp trung tâm là điểm<br /> khớp ban đầu lan truyền tin cậy cho mỗi phần như hình 6.<br /> 3. Thực hiện lan truyền tin cậy cả 4 phần đồng thời như sau:<br /> 4. Thực hiện chia thô tới mịn mức 2 như hình 5.<br /> 5. Tính toán năng lượng chi phí dữ liệu tại mỗi mức chia thô tới mịn mức 2 theo<br /> công thức (12).<br /> 6. Lựa chọn D mức sai lệch tương ứng với D vòng lặp.<br /> 7. Tại mỗi mức sai lệch được chọn sẽ thực hiện:<br /> 8. Đặt các thông điệp ban đầu bằng 0.<br /> 9. Cập nhật thông điệp lan truyền tin cậy xuất phát từ điểm khớp ban đầu<br /> theo công thức (10).<br /> 10. Tính toán độ tin cậy của nút theo công thức (7).<br /> *<br /> 11. Nút x j được lựa chọn và xác định theo công thức (8).<br /> 12. Tính tổng năng lượng chi phí theo công thức (5).<br /> 13. Tính tổng năng lượng chi phí của D mức sai lệch.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 115<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> 4. KẾT QUẢ THỰC NGHIỆM MÔ PHỎNG VÀ THẢO LUẬN<br /> 4.1. Dữ liệu thực nghiệm<br /> Hệ thống thực nghiệm như hình 7 với cấu hình PC được mô tả trong bảng 2 và ảnh<br /> camera kép trong tập dữ liệu kiểm thử [16] được mô tả trong bảng 3.<br /> <br /> <br /> <br /> <br /> Hình 7. Hệ thống thực nghiệm.<br /> Bảng 2. Mô tả cấu hình PC Destop.<br /> Phần cứng Phần mềm<br /> CPU RAM Card màn hình Hệ điều hành Phần mềm ứng dụng<br /> Intel 8GB Geforce GTX750 Ti Window 8.1 QT Creator 5.4<br /> core i7 Bộ nhớ trong: 2GB 64 bít OpenCV 3.0<br /> Core: 460 nhân Visual Studio 2013<br /> BUS: 128 bít CUDA<br /> 4.2. Chỉ số đánh giá độ tin cậy RMSE<br /> Để đánh giá độ tin cậy của kết quả thực nghiệm, chúng tôi sử dụng tham số RMSE<br /> (Root Mean Squared Error: sai số toàn phương trung bình) theo công thức (13). Tham số<br /> RMSE càng nhỏ càng tốt, điều đó chứng tỏ kết quả bản đồ sai lệch thực hiện được càng<br /> gần với bản đồ sai lệch mẫu.<br /> 1<br /> 1<br />