Tài liệu Nghiên cứu giải pháp nâng cao tốc độ xử lý tín hiệu trong hệ thống thị giác nổi tt

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ ĐOÀN VĂN TUẤN NGHIÊN CỨU GIẢI PHÁP NÂNG CAO TỐC ĐỘ XỬ LÝ TÍN HIỆU TRONG HỆ THỐNG THỊ GIÁC NỔI Chuyên ngành: Kỹ thuật điện tử Mã số: 9 52 02 03 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT Hà Nội - 2019 CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ - BỘ QUỐC PHÒNG Ngƣời hƣớng dẫn khoa học: 1. TS Hà Hữu Huy 2. PGS. TS Bùi Trung Thành Phản biện 1: PGS.TS. Hoàng Mạnh Thắng Trường Đại học Bách khoa Hà Nội Phản biện 2: PGS.TS. Lê Nhật Thăng Học viện Công nghệ Bưu chính Viễn thông Phản biện 3: TS. Vũ Lê Hà Viện Khoa học và Công nghệ quân sự Luận án được bảo vệ tại Hội đồng đánh giá luận án cấp Viện và họp tại viện Khoa học và Công nghệ quân sự vào hồi .... giờ ..... ngày.... tháng..... năm 2019 Có thể tìm hiểu luận án tại: - Thư viện Viện Khoa học và Công nghệ quân sự - Thư viện Quốc gia Việt Nam MỞ ĐẦU 1. Tính cấp thiết của đề tài Ngày nay, khoa học kỹ thuật phát triển mạnh mẽ điển hình là cuộc cách mạng công nghiệp 4.0 được khởi xướng từ nước Đức năm 2013. Một trong các yếu tố làm nên cuộc cách mạng công nghiệp 4.0 là robot sẽ dần thay sức lao động của con người và cùng con người làm việc trong các nhà máy, công xưởng. Do đó, robot phải xử lý thông tin trong môi trường 3 chiều (3D) thông qua hệ thống thị giác để định hướng, định vị, nhận dạng và xác định chính xác vị trí các vật xung quanh được gọi là thị giác nổi hay thị giác robot 3D. Ngoài ra, thị giác nổi còn được ứng dụng trong nhận dạng, tái tạo, định vị, phẫu thuật, xe tự hành, xây dựng bản đồ và trong nghệ thuật. Con người mong muốn tạo ra được hệ thị giác robot giống như thị giác của con người, hệ thị giác đơn giản nhất là sử dụng stereo camera bao gồm hai camera thay cho hai mắt của con người kết hợp với hệ thống nhúng xử lý dữ liệu đóng vai trò như bộ não. Thông tin ảnh stereo camera được xử lý thông qua các thuật toán trên nền tảng xử lý như CPU, DSP, GPU, FPGA và ASIC kết hợp với các ngôn ngữ thực hiện như Matlab, OpenCV, CUDA…. Một hệ thống như vậy được gọi là hệ thống thị giác nổi. Các thách thức lớn đối với hệ thống thị giác nổi dùng stereo camera là nguồn dữ liệu từ ảnh stereo camera ngày càng tăng, tốc độ thực hiện đòi hỏi đáp ứng thời gian thực, độ tin cậy cao và dung lượng bộ nhớ hữu hạn. Để giải quyết bài toán này, một trong các giải pháp hiệu quả nhất là phát triển các thuật toán xử lý, trong khi các nền tảng xử lý chưa phát triển kịp theo nhu cầu của con người. 2. Mục đích nghiên cứu Nghiên cứu các giải pháp cụ thể để cải tiến thuật toán lan truyền tin cậy BP nhằm tăng tốc độ thực hiện và giảm dung lượng bộ nhớ yêu cầu khi thực hiện bản đồ độ chênh lệch của ảnh stereo camera có độ phân giải cao, mật độ điểm tương ứng dày trong hệ thống thị giác nổi ứng dụng cho thị giác robot 3D. 3. Đối tƣợng, phạm vi nghiên cứu Luận án tập trung nghiên cứu giải pháp giảm năng lượng chi phí của thuật toán toàn cục lan truyền tin cậy BP thực hiện bản đồ độ chênh lệch của ảnh stereo camera có độ phân giải cao, mật độ điểm tương ứng dầy. Ảnh stereo camera được lấy từ tập dữ liệu kiểm thử. Nghiên cứu, đề xuất giải pháp cải tiến thuật toán lan truyền tin cậy BP nhằm nâng cao hiệu quả thực hiện bản đồ độ chênh lệch. 4. Phƣơng pháp nghiên cứu Luận án tập trung nghiên cứu giải pháp giảm giá trị chi phí của thuật toán lan truyền tin cậy thực hiện bản đồ độ chênh lệch từ ảnh stereo camera có độ phân giải cao, mật độ điểm tương ứng dầy. Phân tích các thuật toán cải tiến thuật toán BP từ đó đề xuất giải pháp nhằm giảm giá trị chi phí của thuật toán BP và lựa chọn nền tảng xử lý phù hợp nhằm đạt được mục đích đề ra của luận án. Từ phân tích toán học, biểu thức hóa các tham số, luận án dùng các công cụ mô phỏng, dữ liệu từ tập dữ liệu kiểm thử để chứng minh tính đúng đắn của các kết quả nghiên cứu. 5. Ý nghĩa khoa học và thực tiễn của luận án Bản đồ chênh lệch (disparity map) của ảnh stereo camera có vai trò rất quan trọng trong thị giác Robot 3D. Từ bản đồ độ chênh lệch, kết hợp với phép đạc tam giác sẽ cho bản đồ độ sâu và ước lượng khoảng cách từ camera đến vật được. Kĩ thuật này được áp dụng rộng rãi trong công nghiệp, robot, phẫu thuật, xe tự hành, định vị và xây dựng bản đồ. Luận án đã đề xuất hai giải pháp giảm hàm chi phí cho thuật toán lan truyền tin cậy BP. Giải pháp thứ nhất thực hiện giảm số lượng các nút trong mô hình trường ngẫu nhiên Markov thông qua các vòng lặp dùng phương pháp chia thô đến mịn CTF mức 1. Giải pháp thứ hai thực hiện kết hợp giữa thuật toán cục bộ CT (Census transform) và thuật toán toàn cục BP đã cải thiện giảm năng lượng chi phí của nút xuất phát ban đầu khi thực hiện lan truyền thông điệp của thuật toán BP. 6. Bố cục của luận án Toàn bộ luận án gồm 137 trang trình bày thành 3 chương, 40 hình vẽ, 29 bảng và 14 biểu đồ. Chƣơng 1: TỔNG QUAN THỊ GIÁC NỔI VÀ XỬ LÝ TÍN HIỆU TRONG HỆ THỐNG THỊ GIÁC NỔI 1.1. Tổng quan thị giác nổi Thị giác nổi là thành phần rất quan trọng trong thị giác máy và được nhiều nhà khoa học nghiên cứu và phát triển trong hai thập kỉ gần đây. Hệ thống thị giác nổi được áp dụng khá rộng rãi trong nhiều lĩnh vực như robot, xe tự hành, y khoa, nghệ thuật, giải trí và đặc biệt trong cuộc các mạng công nghiệp 4.0. [59]. Con người muốn tạo ra một hệ thị giác robot làm việc được trong môi trường 3 chiều gần giống với thị giác con người được gọi là hệ thống thị giác nổi như Hình 1.1, khi đó robot và con người cùng nhau hoạt động sản xuất, tương tác lẫn nhau [107] . Khối thông tin ảnh Khối xử lý thông tin ảnh Khối phát triển ứng dụng Hình 1.1. Sơ đồ khối hệ thống thị giác nổi 1.2. Mô hình camera 1.3. Phƣơng pháp hiệu chuẩn camera Phương pháp hiệu chuẩn camera sẽ quyết định đến tốc độ thực hiện và độ tin cậy của các tham số bên trong và bên ngoài của camera. Hiện nay có một số phương pháp hiệu chuẩn ảnh kinh điển như Hall [39], Salvi [37], Tsai [91] và Weng [76] dựa trên các mô hình camera tương ứng. Mỗi mô hình sẽ có phương pháp hiệu chuẩn thích hợp và có ưu và nhược điểm khác nhau. 1.4. Phƣơng pháp hiệu chỉnh ảnh Các phương pháp hiệu chỉnh ảnh đều làm tối ưu quá trình đồng nhất của ảnh stereo camera và nâng cao độ tin cậy xử lý thông tin ảnh. Phương pháp hiệu chỉnh được chia làm hai dạng. Dạng thứ nhất, các phương pháp hiệu chỉnh sau khi đã hiệu chuẩn [9], [105]. Dạng thứ hai, các phương pháp hiệu chỉnh thực hiện mà không hiệu chuẩn [26]. 1.5. Các thuật toán so khớp Trong khoảng hai thập kỉ qua, đã có rất nhiều thuật toán so khớp được đề xuất. Thuật toán so khớp được phân loại theo ảnh stereo camera. Các thuật toán so khớp cho ảnh stereo camera có độ phân giải cao, mật độ điểm tương ứng thưa như SIFT [10], SURF [66] thường được dùng cho hệ thị giác nổi có yêu cầu tốc độ cao và dung lượng bộ nhớ yêu cầu thấp tuy nhiên không yêu cầu độ tin cậy cao, thường được áp dụng vào các hệ thống định vị, xây dựng bản đồ hay SLAM [36] và các xe tự hành. Các thuật toán so khớp cho ảnh stereo camera có độ phân giải cao, mật độ điểm tương ứng dầy như [7], [44] thường được dùng cho các hệ thị giác nổi yêu cầu độ tin cậy cao, thường được áp dụng vào các hệ kiểm tra sản phẩm trong công nghiệp, hệ thị giác 3D của thị giác robot và trong phẫu thuật hay tái tạo đối tượng, tuy nhiên, độ phức tạp tính toán lớn và dung lượng bộ nhớ yêu cầu cao. Thuật toán so khớp cho ảnh stereo camera có độ phân giải cao, mật độ điểm tương ứng dầy được chia làm ba loại chính là thuật toán cục bộ [15], [101], thuật toán toàn cục [48], [78] và thuật toán lai [24], [90]. 1.6. Nền tảng xử lý trong hệ thống thị giác nổi - Nền tảng xử lý dùng CPU - Nền tảng xử lý dùng DSP - Nền tảng xử lý dùng GPU - Nền tảng xử lý dùng FPGA/ASIC 1.7. Đánh giá các nền tảng xử lý trong hệ thị giác nổi Từ CPU→DSP→GPU→FPGA→ASIC, hiệu suất xử lý tăng tuần tự, trong khi chi phí và công suất tiêu thụ giảm tương ứng. Thuật toán thị giác nổi có tính linh hoạt hơn và chu kỳ phát triển ngắn, trong khi phần cứng thực hiện có chu kỳ thiết kế dài hơn với độ linh hoạt thiết kế kém hơn bởi vì đồng thời phải xem xét tối ưu thuật toán và thu thập bản đồ phần cứng. Từ quan điểm của thực tiễn, hệ thống phần cứng xử lý thị giác nổi cần được tiếp cận hơn cho hệ thống thị giác nổi thời gian thực bởi vì nó tiêu thụ công suất thấp và giá thành rẻ hơn. 1.8. Các hƣớng nghiên cứu nhằm nâng cao hiệu quả của hệ thống thị giác nổi - Phương pháp phân đoạn ảnh và tối ưu hóa phân cấp - Điều chỉnh vùng đồng nhất và không nhìn thấy - Phương pháp cải thiện tối thiểu giá trị chi phí cho sự so khớp của điểm ảnh - Phương pháp tối ưu hóa liên kết - Phương pháp sắp sếp bộ nhớ - Phương pháp cải tiến thiết kế VLSI 1.9. Kết luận chƣơng 1 Chương 1 đã trình bày tổng quan các thành phần chính của hệ thống thị giác nổi bao gồm hai khối chính là khối thông tin ảnh và khối xử lý thông tin ảnh. Mỗi thành phần cũng đã được phân tích và đưa ra được các đánh giá vai trò ảnh hưởng của nó đến hệ thống. Khối thông tin ảnh bao gồm hai thành phần chính là stereo camera và hiệu chuẩn camera. Khối này cung cấp các thông số về ảnh stereo camera như kích thước và mức độ chênh lệch độ sâu của ảnh, thông số bên trong và thông số bên ngoài stereo camera. Các thông số cũng ảnh hưởng đến độ tin cậy của hệ thống. Khối xử lý thông tin ảnh sẽ quyết định chính đến hiệu quả của hệ thống bao gồm cả phần mềm và phần cứng. Phần mềm là ngôn ngữ lập trình thực hiện các thuật toán xử lý bao gồm các thuật toán hiệu chỉnh ảnh, các thuật toán so khớp. Trong đó thì vai trò của thuật toán so khớp sẽ ảnh hưởng chủ yếu đến hiệu quả của hệ thống. Phần cứng là các nền tảng xử lý thực hiện các thuật toán xử lý và nó cũng đóng vai trò nâng cao hiệu quả của hệ thống thị giác nổi. Ngoài ra, việc lựa chọn phù hợp giữa nền tảng xử lý và thuật toán so khớp cũng ảnh hướng đến tốc độ thực hiện của hệ thống thị giác nổi. Phần cứng được lựa chọn thực hiện là nền tảng xử lý GPU của Nvidia GXT 750Ti với bộ nhớ 2GB, 460 nhân và băng thông 128 bit dùng phần mềm CUDA 7.5 và trình biên dịch QT creator kết hợp với CPU Intel core i7, RAM 8 GB với hệ điều hành Window 8.1. Nền tảng xử lý GPU được lựa chọn vì nó hỗ trợ cấu trúc xử lý song song, có nhiều nhân xử lý, băng thông rộng và bộ nhớ ngày càng được tăng lên phù hợp với chương trình thực nghiệm của luận án. Chƣơng 2: NGHIÊN CỨU CÁC THUẬT TOÁN LAN TRUYỀN TIN CẬY BP VÀ XÂY DỰNG CÁC PHƢƠNG PHÁP NÂNG CAO TỐC ĐỘ XỬ LÝ TRONG HỆ THỐNG THỊ GIÁC NỔI 2.1. Trƣờng ngẫu nhiên Markov Trường ngẫu nhiên Markov (MRF: Markov Random Field) là một nhánh của lý thuyết xác suất. Trường ngẫu nhiên Markov được sử dụng như là một công cụ để xử lý các mô hình hóa dữ liệu ảnh, được kết hợp với các thuật toán tiên tiến hiện nay. Ngoài ra, trường ngẫu nhiên Markov được sử dụng như là các phương tiện tạo ra các kết quả suy luận về hình ảnh. Các suy luận liên quan về hình ảnh cơ bản và cấu trúc khuôn hình sẽ giải quyết các vấn đề như tái tạo lại ảnh, phân đoạn ảnh, thị giác nổi và tạo dán nhãn đối tượng. Mô hình trường ngẫu nhiên Markov thường có hai dạng là dạng hình cây và dạng hình lưới. 2.2. Thuật toán lan truyền tin cậy BP ứng dụng cho thị giác nổi Thuật toán lan truyền tin cậy BP sử dụng các thông điệp chứa các giá trị chênh lệch của điểm tương ứng và di chuyển giữa các nút theo phương pháp lặp để thực hiện suy luận trên mô hình đồ thị. Phương pháp này cung cấp suy luận chính xác với các mô hình dạng cây và cung cấp suy luận gần đúng cho mô hình dạng lưới. Thuật toán lan truyền tin cậy được áp dụng để xác định MAP trong các mô hình trường ngẫu nhiên Markov cho các vấn đề về thị giác nổi. 2.3. Thuật toán cục bộ CT Thuật toán cục bộ CT (Census transform) là thuật toán biến đổi thống kê cục bộ không tham số, nó không phụ thuộc vào điều kiện ánh sáng của ảnh [86]. Nguyên lý hoạt động của CT là biến đổi mỗi điểm ảnh thành một chuỗi bit có độ dài N bit với kiến trúc không gian cục bộ. Đối với mỗi điểm ảnh lân cận ngoại trừ điểm trung tâm sẽ biến đổi tương ứng thành một bit trong chuỗi N bit theo ngưỡng nếu giá trị cường độ sáng (intensity), bit lân cận lớn hơn giá trị cường độ bit trung tâm thì tương ứng với bit bằng 1 ngoài ra thì bit bằng 0. 2.4. Các giải pháp cải tiến tốc độ xử lý của thuật toán lan truyền tin cậy BP - Tính toán song song. - Giảm độ phức tạp tính toán. - Giảm dung lượng bộ nhớ yêu cầu khi thực hiện. - Tối thiểu thông điệp cập nhật. - Tối ưu cách thức truy cập bộ nhớ. - Tái sử dụng bộ nhớ. - Nâng cao độ tin cậy. - Tối ưu hóa liên kết. - Lựa chọn thuật toán xử lý và nền tảng xử lý phù hợp Đề tài luận án đề xuất hai giải pháp để nâng cao tốc độ xử lý cho thuật toán lan truyền tin cậy BP là giải pháp giảm hàm chí phí và giải pháp tối ưu hóa kết hợp. 2.5 Đề xuất giải pháp giảm hàm chi phí 2.5.1. Thuật toán đề xuất 1 Mô hình thuật toán đề xuất 1 (CFBP) được xây dựng dựa trên mô hình trường ngẫu nhiên Markov dạng hình lưới, nút có liên kết 4 như Hình 2.16. Xét G = (E, V) trong đó G là mô hình đồ thị, E là tập các nút , V là tập các cạnh. Nút là nhãn được gán giá trị độ chênh lệch cường độ sáng của điểm tương ứng trên ảnh trái và ảnh phải của ảnh stereo camera, thường được gọi là giá trị dữ liệu hay hàm dữ liệu. Cạnh là nhãn được gán giá trị độ chênh lệch của hai nút lân cận, thường được gọi là giá trị nhẵn hay hàm nhẵn. Hình 2.16. Sơ đồ mô hình thuật toán đề xuất 1 Từ mô hình thuật toán đề xuất 1 cho thấy thuật toán đề xuất đã sử dụng phương pháp chia thô đến mịn CTF mức 1 như Hình 2.17 để giảm số lượng các nút sau các vòng lặp. Phương pháp chia thô đến mịn CTF (Coarse to Fine) dùng để suy luận giảm số lượng các nút theo các mức. Sau khi thực hiện CTF mức l thì số lượng nút trên vòng lặp hiện tại sẽ giảm S=2x2l lần so với số lượng nút tại vòng lặp trước đó. Giá trị chi phí để thực hiện suy luận 4 nút về 1 nút được xác định theo công thức (2.36). Thông điệp trong thuật toán đề xuất lan truyền theo sơ đồ song song như Hình 2.18. Nút xuất phát ban đầu được lựa chọn là nút có gán nhãn (0, 0) với các '  0. giá trị thông điệp ban đầu được đặt được đặt là m0'  0 và m0,0 Hình 2.17. Sơ đồ cấu trúc chia thô đến mịn CTF mức 1 Hình 2.18. Sơ đồ lan truyền thông điệp Giá trị chi phí khi thực hiện chia thô đến mịn CTF mức 1 là: 1 (2.36) E CTF 1 ( x)    ( xi ) 4 i[1,4] Số lần thực hiện CTF mức 1 là k2' và được xác định theo công thức (2.37). Xét ảnh stereo camera có độ phân giải là m, n và k trong đó m là số lượng điểm ảnh theo hàng, n là số lượng điểm ảnh theo cột và k là số lượng các mức chênh lệch độ sâu của ảnh. k2'  log 2 m (2.37) Số vòng lặp k1' được thực hiện trong mỗi lần chia thô đến mịn CTF mức 1 được xác định là: k1'  k log2 m  1 + Tính toán giá trị chi phí lan truyền thông điệp (2.38) E ' ( x)   ' ( xi )  iE   (x , x ) ' i i , jV j (2.39) Hàm giá trị nhẵn được xác định là độ chênh lệch của hai nút nên có thể được biểu diễn như: (2.40)  ' ( xi , x j )   ' ( xi  x j ) E ' ( x)   ' ( xi )  iE  i , jV  ' ( xi  x j ) (2.41) Thuật toán đề xuất 1 dựa trên phương pháp lặp, với sự lan truyền thông điệp tin cậy qua các nút. Mỗi thông điệp là một véc tơ, độ dài của véc tơ là số lượng mức chênh lệch độ sâu của điểm ảnh tương ứng và ký liệu là k ' . Thông điệp chứa giá trị chênh lệch được gán cho mỗi nhãn, giá trị này thể hiện độ tin cậy cho mỗi nút mà nó truyền đến từ các nút lân cận và được ký hiệu là m ' . Thông điệp cập nhật tại vòng lặp t được xác định là: t 1) (2.42) mi'(t ) j ( x j )  min(  ' ( xi  x j )   ' ( xi )   ms'( i ( xi )) xi sN ( i )\ j trong đó s là các cạnh của nút i ngoại trừ cạnh đến nút j. mi'(t ) j ( x j )  min(  ' ( xi  x j )  h' ( xi )) trong đó h' ( xi )   ' ( xi )   xi sN ( i )\ j (2.43) t 1) ms'( i ( xi ) Hàm giá trị chi phí nhẵn được xác định theo mô hình tuyến tính.  ' ( xi  x j )  min( p' xi  x j , q' ) (2.44) trong đó p ' là hệ số tỉ lệ tăng, q ' là ngưỡng dừng tăng Khi đó thông điệp cập nhật được xác định: mi'(t ) j ( x j )  min(min( p' xi  x j , q' )  h' ( xi )) (2.45) Sau T vòng lặp thì độ tin cậy của mỗi nút được xác định là: b' j ( x j )   ' ( x j )   mi'(T )j ( x j ) (2.46) xi iN ( j ) trong đó N là các nút lân cận nút j. Nút x '*j được lựa chọn và xác định theo công thức: x'*j  arg min b' j ( x j ) Hàm chi phí được xác định: (2.47) E ' ( x)   I L ( x, y)  I R ( x  xi , y)  iE  i , jV min( p ' xi  x j , q ' ) (2.48) trong đó I L ( x, y ) là độ xám của ảnh trái tại tọa độ ( x, y ) , I R ( x  xi , y) là độ xám của ảnh phải tại tọa độ ( x  xi , y ) của ảnh stereo camera. 2.5.2. Thuật toán đề xuất 2 Mô hình thuật toán đề xuất 2 (CFCSBP) có cấu trúc giống với mô hình đề xuất 1 như Hình 2.20, tuy nhiên, có điểm khác giữa hai mô hình này là trong khi thuật toán đề xuất 1 phải thực hiện số vòng lặp bằng với số mức chênh lệch của ảnh còn thuật toán đề xuất 2 có số vòng lặp thay đổi theo hệ số Z '' theo công thức (2.50) so với mức chênh lệch của ảnh. Hình 2.20. Sơ đồ mô hình thuật toán đề xuất 2 Xét ảnh stereo camera có độ phân giải là m, n và k trong đó m là số lượng điểm ảnh theo hàng, n là số lượng điểm ảnh theo cột và k là số lượng các mức chênh lệch độ sâu của ảnh. Số lần thực hiện chia thô đến mịn CTF mức 1 được xác định theo công thức (2.49) với lý do như lựa chọn như k2' . k2''  log 2 m (2.49) Số vòng lặp k1'' được thực hiện trong mỗi mức chia thô đến mịn CTF mức 1 được xác định là: k1''  k Z (log 2 m  1) '' (2.50) trong đó Z '' là hệ số độ sâu thay đổi. Tính toán giá trị chi phí cho lan truyền thông điệp của thuật toán đề xuất 2 được thực hiện giống như của thuật toán đề xuất 1 chỉ khác ở chỗ thuật toán đề xuất 1 phải thực hiện k '  k1'  k2' vòng lặp còn thuật toán đề xuất 2 thực hiện k ''  k1''  k2'' vòng lặp 2.6. Đề xuất giải pháp tối ƣu hóa kết hợp 2.6.1. Thuật toán đề xuất 3 Mô hình thuật toán đề xuất 3 (CTBP) được xây dựng dựa trên mô hình trường ngẫu nhiên Markov dạng Hình lưới, nút có liên kết 4 như Hình 2.22. Xét G = (E, V) trong đó G là mô hình đồ thị, E là tập các nút , V là tập các cạnh. Nút là nhãn được gán giá trị độ chênh lệch cường độ sáng của điểm tương ứng trên ảnh trái và ảnh phải của ảnh stereo camera, thường được gọi là giá trị dữ liệu hay hàm dữ liệu. Cạnh là nhãn được gán giá trị độ chênh lệch của hai nút lân cận, thường được gọi là giá trị nhẵn hay hàm nhẵn. V1, V2, V3, V4 và E1, E2, E3, E4 tương ứng là các nút và các cạnh của phần 1, phần 2, phần 3 và phần 4 của mô hình thuật toán đề xuất 3. Hình 2.22. Sơ đồ mô hình thuật toán đề xuất 3 Từ mô hình thuật toán đề xuất 3 cho thấy, nút xuất phát lan truyền thông điệp được gán nhãn (0,0) trên mô hình thuật toán lan truyền tin cậy BP đã được thay bằng nút xuất phát lan truyền thông điệp là nút được gán m n nhãn  ,  trên mô hình thuật toán đề xuất 3. Quá trình tìm điểm tương  2 2 m n ứng cho nút được gán nhãn  ,  được thực hiện thông qua phương  2 2 pháp cục bộ CT như công thức (2.35) với cửa sổ 3  3 và dải quét xCT = 10. Ảnh được hiệu chỉnh làm 4 phần qua điểm tương ứng được xác định qua CT. Mỗi phần sẽ được lan truyền thông điệp tin cậy theo thuật toán BP với sơ đồ lan truyền như Hình 2.18, nút xuất phát được là nút được gán nhãn m n  ,  . Cả 4 phần của mô hình sẽ được thực hiện đồng thời.  2 2 +Tính giá trị chi phí Vì 4 phần của mô hình có kích thước như nhau nên phương pháp tính giá trị chi phí là giống nhau. + Tính toán giá trị chi phí lan truyền thông điệp cho phần 1 của mô hình Tính toán giá trị chi phí lan truyền thông điệp của thuật toán đề xuất 3 giống như tính toán giá trị chi phí lan truyền thông điệp của thuật toán đề xuất 3, chỉ khác nhau ở kích thước các nút lan truyền. Thuật toán đề xuất 3 có nút xuất lan truyền là nút được gán nhãn (0,0) trong khi thuật toán đề m n xuất 3 có nút xuất phát lan là nút được gán nhãn  ,  .  2 2 2.6.2. Thuật toán đề xuất 4 Mô hình thuật toán đề xuất 4 (CTCSBP) được xây dựng dựa trên mô hình trường ngẫu nhiên Markov dạng hình lưới, nút có liên kết 4 giống như thuật toán đề xuất 3 như Hình 2.22. Tuy nhiên, có điểm khác giữa hai mô hình này là trong khi thuật toán đề xuất 3 phải thực hiện số vòng lặp bằng với số mức chênh lệch của ảnh còn thuật toán đề xuất 4 có số vòng lặp thay đổi theo tỉ lệ Z '''' theo công thức (2.71) so với mức chênh lệch của nút. V1, V2, V3, V4 và E1, E2, E3, E4 tương ứng là các nút và các cạnh của phần 1, phần 2, phần 3 và phần 4 của mô hình đề xuất 4. Nguyên lý hoạt động và tính toán giá trị chi phí cho lan truyền thông điệp của thuật toán đề xuất 4 được thực hiện giống như của thuật toán đề xuất 3 chỉ khác ở chỗ thuật toán đề xuất 3 phải thực hiện k ''' vòng lặp còn thuật toán đề xuất 4 thực hiện k '''' vòng lặp. Hình 2.24. Sơ đồ mô hình thuật toán đề xuất 4 k (2.71) k ''''  '''' Z 2.7. Phƣơng pháp đánh giá thuật toán Hai phép đo chất lượng dựa trên dữ liệu chuẩn đã biết [29]: + Độ lệch chuẩn RMSE (Root_Mean_Squared_Error) giữa tính toán bản đồ chênh lệch dC(x,y) và bản đồ chênh lệch chuẩn dT(x,y): 1 2 1 2 R    dc ( x, y )  dT ( x, y )   N ( x, y )  ở đây N là tổng số điểm ảnh + Tỉ lệ các điểm khớp xấu 1 B   ( d C ( x, y )  d T ( x , y )   d ) N ( x, y ) (2.82) (2.83) trong đó  d là ngưỡng đánh giá lỗi chênh lệch. 2.8. Kết luận chƣơng 2 Chương 2 luận án đã trình bày cơ sở lý thuyết của thuật toán lan truyền tin cậy BP là trường ngẫu nhiên Markov bao gồm lý thuyết đồ thị kết hợp với lý thuyết xác suất. Nghiên cứu, ứng dụng thuật toán lan truyền tin cậy BP xác định bản đồ chênh lệch của ảnh stereo camera có độ phân giải cao, mật độ điểm tương ứng dầy. Phân tích, đánh giá các thuật toán lan truyền tin cậy BP cải tiến thực hiện bản đồ sai lệch của ảnh stereo camera, từ đó đưa ra các hướng để cải tiến nâng cao tốc độ xử lý tín hiệu của thuật toán lan truyền tin cậy BP ứng dụng trong hệ thống thị giác nổi. Từ các phân tích và đánh giá các thuật toán đã thực hiện, đề tài luận án đã đề xuất hai giải pháp nâng cao tốc độ xử lý tín hiệu của thuật toán lan truyền tin cậy BP ứng dụng trọng hệ thống thị giác nổi là giải pháp giảm hàm chi phí và giải pháp tối ưu hóa kết hợp. Cả hai giải pháp đều có mô hình dựa trên mô hình trường ngẫu nhiên Markov dạng lưới, nút có liên kết 4. Giải pháp giảm hàm chi phí được biểu diễn qua hai thuật toán đề xuất là thuật toán lan truyền tin cậy dùng chia thô đến mịn CFBP gọi là thuật toán đề xuất 1 và thuật toán đề xuất lan truyền tin cậy có độ sâu thay đổi dùng chia thô đến mịn CFCSBP gọi là thuật toán đề xuất 2. Giải pháp tối ưu hóa kết hợp là sự kết hợp giữa thuật toán cục bộ CT và thuật toán toàn cục lan truyền tin cậy BP, được biểu diễn qua hai thuật toán đề xuất là thuật toán lan truyền tin cậy kết hợp biến đổi thống kê CTBP gọi là thuật toán đề xuất 3 và thuật toán lan truyền tin cậy có độ sâu thay đổi kết hợp biến đổi thống kê CTCSBP gọi là thuật toán đề xuất 4. Chƣơng 3: THỰC NGHIỆM CÁC THUẬT TOÁN ĐỀ XUẤT VÀ ĐÁNH GIÁ KẾT QUẢ 3.1. Công cụ và dữ liệu thực nghiệm Hệ thống thực nghiệm như Hình 3.1 với cấu hình PC được mô tả trong Bảng 3.1 và ảnh stereo camera trong tập dữ liệu kiểm thử [30] được mô tả trong Bảng 3.2. Hình 3.1. Hệ thống thực nghiệm Bảng 3.1. Mô tả cấu hình PC Desktop Phần cứng Phần mềm CPU RAM Card màn hình Hệ điều Phần mềm ứng hành dụng Intel 8GB Geforce GTX750 Ti Window QT Creator 5.8 core Bộ nhớ trong: 2GB 8.1 OpenCV 3.0 i7 Core: 460 nhân 64 bit Visual Studio 2013 BUS: 128 bit CUDA Bảng 3.2. Tập dữ liệu kiểm thử Bản đồ Ký Tên Độ chênh Kích thức Ảnh trái Ảnh phải chênh lệch hiệu ảnh lệch chuẩn #1 Baby 620x555 300 #2 Aloe 641x555 270 #3 Cloth 626x555 290 #4 Flower 656x555 pots 251 #5 Bowlin 665x555 g 240 #6 Book 695x555 200 3.2. Chỉ số đánh giá độ tin cậy RMSE 3.3. Kết quả thực nghiệm 3.3.1. Thuật toán BP tiêu chuẩn Tốc độ thực hiện bản đồ chênh lệch của thuật toán lan truyền tin cậy BP [78] trên hệ thống Hình 3.1 có cấu hình được mô tả thông số như Bảng 3.1 và dữ liệu kiểm thử Bảng 3.2 được thể hiện trên Bảng 3.3. Bảng 3.3. Tốc độ thực hiện của thuật toán BP (ms) Ảnh #1 #2 #3 #4 #5 #6 TT BP 439 457 442 473 478 494 3.3.2. Thuật toán đề xuất 1 Kết quả bản đồ chênh lệch của ảnh stereo camera Bảng 3.2 khi thực hiện dùng thuật toán đề xuất 1 được thể hiện trên Hình 3.3. (a) (b) (c) (d) (e) (f) Hình 3.3. Bản đồ chênh lệch dùng thuật toán 1: (a), (b), (c), (d), (e) và (f) là bản đồ chênh lệch tương ứng của các ảnh #1, #2, #3, #4, #5 và #6. Tốc độ thực hiện bản đồ chênh lệch của thuật toán đề xuất 1 trên hệ thống Hình 3.1 có cấu hình được mô tả thông số như Bảng 3.1 và dữ liệu kiểm thử Bảng 3.2 được thể hiện trên Bảng 3.6. Bảng 3.6. Tốc độ thực hiện của thuật toán đề xuất 1 (ms) Ảnh #1 #2 #3 #4 #5 #6 TT CFBP 206 217 213 224 227 235 3.3.3. Thuật toán đề xuất 2 Kết quả bản đồ chênh lệch của ảnh stereo camera Bảng 3.2 khi thực hiện dùng thuật toán đề xuất 2 với hệ số độ sâu thay đổi Z ''  3 được thể hiện trên Hình 3.4. (a) (b) (c) (d) (e) (f) Hình 3.4. Bản đồ chênh lệch dùng thuật toán 2: (a), (b), (c), (d), (e) và (f) là bản đồ chênh lệch tương ứng của các ảnh #1, #2, #3, #4, #5 và #6. Tốc độ thực hiện bản đồ chênh lệch của thuật toán đề xuất 2 với hệ số Z  3 trên hệ thống Hình 3.1 có cấu hình được mô tả thông số như Bảng 3.1 và dữ liệu kiểm thử Bảng 3.2 được thể hiện trên Bảng 3.9. Bảng 3.9. Tốc độ thực hiện của thuật toán đề xuất 2 (ms) Ảnh #1 #2 #3 #4 #5 #6 TT CFCSBP 191 199 195 203 204 211 3.3.2. Thuật toán đề xuất 3 Kết quả bản đồ chênh lệch của ảnh stereo camera Bảng 3.2 khi thực hiện dùng thuật toán đề xuất 3 kết hợp với thuật toán CT có cửa sổ 3x3 và xCT  10 được thể hiện trên Hình 3.5. '' (a) (b) (c) (d) (e) (f) Hình 3.5. Bản đồ chênh lệch dùng thuật toán 3: (a), (b), (c), (d), (e) và (f) là bản đồ chênh lệch tương ứng của các ảnh #1, #2, #3, #4, #5 và #6. Tốc độ thực hiện bản đồ chênh lệch của thuật toán đề xuất 3 với thuật toán CT có cửa sổ 3  3 và dải quét xCT  10 trên hệ thống Hình 3.1 có cấu hình được mô tả thông số như Bảng 3.1 và dữ liệu kiểm thử Bảng 3.2 được thể hiện trên Bảng 3.12. Bảng 3.12. Tốc độ thực hiện của thuật toán đề xuất 3 (ms) Ảnh #1 #2 #3 #4 #5 #6 TT CTBP 182 185 182 187 188 191 3.3.2. Thuật toán đề xuất 4 Kết quả bản đồ chênh lệch của ảnh stereo camera Bảng 3.2 khi thực hiện dùng thuật toán đề xuất 4 với hệ số độ sâu thay đổi Z ''''  3 được thể hiện trên Hình 3.6. (a) (b) (c) (d) (e) (f) Hình 3.6. Bản đồ chênh lệch dùng thuật toán 4: (a), (b), (c), (d), (e) và (f) là bản đồ chênh lệch tương ứng của các ảnh #1, #2, #3, #4, #5 và #6. Tốc độ thực hiện bản đồ chênh lệch của thuật toán đề xuất 4 với hệ số độ sâu thay đổi Z ''''  3 trên hệ thống Hình 3.1 có cấu hình được mô tả thông số như Bảng 3.1 và dữ liệu kiểm thử Bảng 3.2 được thể hiện trên Bảng 3.15. Bảng 3.15. Tốc độ thực hiện của thuật toán đề xuất 4 (ms) Ảnh #1 #2 #3 #4 #5 #6 TT CTCSBP 83 84 83 89 92 94 3.4. Đánh giá thuật toán đề xuất 3.4.1. Đánh giá thuật toán đề xuất 1 với thuật toán BP Tốc độ thực hiện bản đồ chênh lệch của ảnh stereo camera phụ thuộc vào các yếu tố như thuật toán thực hiện (kỹ năng lập trình), trình biên dịch, cấu hình của hệ thống và dữ liệu đầu vào. Do vậy, để đánh giá tốc độ thực hiện của thuật toán đề xuất 1 và thuật toán BP [78], luận án đã thực hiện hai thuật toán này trên cùng một hệ thống thực nghiệm như Hình 3.1 với các thông số được thể hiện trong Bảng 3.1 và tập dữ liệu kiểm thử như Bảng 3.2. Kết quả so sánh tốc độ giữa hai thuật toán được mô tả trong Bảng 3.18 và Biểu đồ 3.1. Bảng 3.18. So sánh tốc độ thực hiện của thuật toán 1 và BP (ms) Ảnh Thuật toán BP Thuật toán đề xuất 1 Tốc độ tăng #1 439 206 113,11% #2 457 217 110,60% #3 442 213 107,51% #4 473 224 111,16% #5 478 227 110,57% #6 494 235 110,21% Bảng 3.18 cho thấy, đối với các ảnh kiểm thử có kích thước tương đương nhau và có mức chênh lệch khác nhau thì thời gian thực hiện gần như không thay đổi khi thực hiện cùng một thuật toán. Điều này cho thấy tốc độ thực hiện bản đồ chênh lệch không phụ thuộc vào độ phức tạp và độ chênh lệch của ảnh mẫu mà chỉ phụ thuộc vào độ phân giải của ảnh. Ngoài ra, Bảng 3.18 còn thể hiện rằng tốc độ của thuật toán đề xuất 1 tăng 113,11% so với thuật toán BP tiêu chuẩn khi thực hiện ảnh # 1 trong Bảng