Công nghệ thông tin & Cơ sở toán học cho tin học

MỘT GIẢI PHÁP THỰC HIỆN BẢN ĐỒ SAI LỆCH CỦA ẢNH
CAMERA KÉP CÓ MẬT ĐỘ DÀY ĐẶC ỨNG DỤNG
CHO ẢNH 3D VÀ BẢN ĐỒ ĐỘ SÂU
Đoàn Văn Tuấn*, Bùi Trung Thành
Tóm tắt: Bản đồ sai lệch là một trong các thông số rất quan trọng trong thị giác
nổi (stereo vision). Từ thông tin bản đồ sai lệch sẽ xác định được ảnh 3D và bản đồ
độ sâu của ảnh. Đã có nhiều thuật toán đề xuất, trong đó thuật toán BP (Belief
propagation) đã được nhiều nhà khoa học nghiên cứu và cải tiến. Đây là thuật toán
suy diễn gần đúng dựa trên mô hình trường ngẫu nhiên Markov với tối ưu toàn cục
cho độ tin cậy cao. Hầu hết các thuật toán BP cải tiến đều lấy điểm khớp ban đầu tại
điểm trên cùng bên trái của ảnh để lan truyền tin cậy xác định bản đồ sai lệch.
Trong bài báo này chúng tôi đề xuất một phương pháp cải tiến mới cho thuật toán
BP, điểm khớp xuất phát ban đầu là điểm trung tâm của ảnh camera kép, sau đó,
thực hiện lan truyền tin cậy để xác định bản đồ sai lệch. Điểm khớp trung tâm được
xác định bằngthuật toán cục bộ CT (Census transfrom). Với phương pháp đề xuất
này cho kết quả 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,5 lần so với thuật toán BP tiêu chuẩn.
Từ khóa: Bản đồ sai lệch, Thị giác nổi nổi, Lan truyền tin cậy, Biến đổi kiểm kê, Camera kép, Bán toàn cục.

1. MỞ ĐẦU
Thị giác nổi (stereo vision) là vấn đề rất
quan trọng trong thị giác máy (computer
vision) [1]. Hệ thống stereo vision có
nhiệm vụ nhận dạng, xác định khoảng cách
từ camera đến vật và tái tạo vật. Stereo
vision được ứng dụng rộng rãi trong nhiều
lĩnh vực như: công nghiệp, y khoa, giải trí,
ôtô tự hành và đặc biệt trong robotics. Bản
đồ sai lệch là thông số rất quan trọng của

stereo vision, đặc biệt ứng dụng cho
robotic thì bản đồ sai lệch của ảnh camera Camera
Camer
a phải
kép có mật độ dầy đặc (dense) đã được
trái
nhiều nhà khoa học nghiên cứu [2], camera
kép như hai mắt của robot. Ảnh camera
Hình 1.Mô hình ảnh camera kép.
kép là hai ảnh cùng chụp một cảnh với góc
nhìn khác nhau như hình 1. Hầu hết các
thuật toán xác định bản đồ sai lệch đều phải tự cân bằng giữa tốc độ thực hiện và độ tin
cậy, để thực hiện tốt được hai việc này là rất khó. Các thuật toán đều phải dựa trên một mô
hình cụ thể. Một trong các mô hình là mô hình trường ngẫu nhiên Markov (MRFs). Mô
hình trường ngẫu nhiên Markov sẽ tạo ra các thuật toán suy diễn [3] có thể thực hiện bản
đồ sai lệch tại các vùng ảnh bị che khuất, độ sâu thay đổi và đồng nhất. Một trong các
thuật toán suy diễn gần đúng là thuật toán BP (Belief Propagation).
Thuật toán BP thực hiện dựa trên các vòng lặp và cho độ tin cậy 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à độ 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 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, đề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 nền hệ thống

100

Đ. V. Tuấn, B. T. Thành, “Một giải pháp thực hiện bản đồ … ảnh 3D và bản đồ độ sâu.”


Nghiên cứu khoa học công nghệ


nhúng GPU [4] hay FPGA [5]. Đa số các thuật toán BP cải tiến đều thực 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.
Tác giả Sun[6] đã biểu diễn BP dùng suy diễn MAP được coi là thuật toán BP chuẩn.
Tác giả Felzenszwalb[7] đã đề xuất 3 phương pháp khắc phục nhược điểm của thuật toán
BP. Thứ nhất là dùng tối thiểu cho hàm chi phí đã giảm thời gian tính toán từ O(L2) xuống
O(L), thứ hai là chia ảnh thành hai phần tương ứng với vòng lặp chẵn và vòng lặp lẻ điều
này mang lại ưu điểm là giảm được bộ nhớ lưu trữ, thứ ba là chia thô và làm mịn điều này
đã giảm được số vòng lặp và bộ nhớ yêu cầu tuy nhiên phải trả giá cho độ chính xác. Tác
giả Li Zhang[8] đề xuất bổ xung tham số ngưỡng cho hàm chi phí, việc làm này cũng
mang lại giảm không gian tìm kiếm đo đó cũng nâng cao được tốc độ. Tác giả Yu-Cheng
Tseng[9] đã đề xuất một giải pháp nhằm giảm bộ nhớ bằng cách chia ảnh thành các khối
độc lập và thực hiện BP riêng từng khối, phương pháp này có ưu điểm là thực hiện nhanh
nhưng độ tin cậy giảm. Để khắc phục nhược điểm này tác giả Chia [10] đã đề xuất như
mỗi khối sẽ được lưu trữ các thông tin của các điểm đường bao của khối do vậy nó cần bổ
xung bộ nhớ cho các thông tin đường bao. Để giảm yêu cầu bộ nhớ cho thông tin đường
bao, tác giả Chao[11] đã đề xuất là tái sử dụng thông tin đường bao nhưng độ phức tạp của
tính toán tăng lên. Tác giả Yang[12] đề xuất giải pháp giảm bộ nhớ bằng cách cố định
không gian sai lệch cho việc chia thô tới mịn.
Đặc điểm chung của các giải pháp cải tiến là điểm khớp xuất phát ban đầu tại vị trí
điểm trên cùng bên trái của ảnh camera kép để lan truyền tin cậy, do đó, khi điểm ảnh
camera kép ban đầu không khớp nó dẫn đến yêu cầu năng lượng chi phí lớn và độ chính
xác không cao. Để khắc phục nhược điểm này, chúng tôi đề xuất một giải pháp mới, điểm
ảnh khớp xuất phát ban đầu là điểm khớp trung tâm của ảnh camera kép được xác định
theo thuật toán CT (Census transform) và lan truyền tin cậy đồng thời theo bốn hướng
dùng xử lý song song. Thật toán CT có hàm biến đổi mạnh và không phụ thuộc cường độ
ánh sang của ảnh [13].
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
quan đến thuật toán thực hiện bản đồ sai lệch như BP và CT. Phần 3 đề xuất thuật toán lan
truyền tin cậy kết hợp biến đổi kiểm kê CTBP. Kết quả thực nghiệm đưa ra trong phần 4;
Kết luận được cho trong phần 5.

2. CÁC NGHIÊN CỨU LIÊN QUAN
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.
Bảng 1. Các kí hiệu và định nghĩa của nó.
Kí hiệu
Định nghĩa
G
Mô hình đồ thị biểu diễn bản đồ sai lệch của ảnh stereo camera.
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
tương đồng trong ảnh stereo camera).
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í
cuat nút với các nút lân cận của nó).
i,j
Biểu diễn nút thứ i và nút lân cận i.
Xi
Biến ngẫu nhiên của nút i.
xi
Sự chuẩn hóa của Xivà Xi là không gian trạng thái của xi (xiϵ Xi)
X
Biến ngẫu nhiên liên kết x.
x
Sự chuẩn hóa các giá trị mô hình đồ thị trong không gian X
p(x)
Xác xuất hậu nghiệm (posterior) MAP.
Xác suất nút i.
 i (x i )

Tạp chí Nghiên cứu KH&CN quân sự, Số 51, 10 - 2017


101


Công nghệ thông tin & Cơ sở toán học cho tin học

 ( xi , x j )
E(x)
D(xi)

Xác suất nút i với nút j lân cận nút i.

V ( xi , x j )

Năng lượng chi phí
Hàm năng lượng chi phí cho nút i
Hàm năng lượng chi phí giữa nút i và nút j lân cận

mit j ( x j )

Thông điệp chuyển từ nút i sang nút lân cận j.

bj (x j )

Độ tin cậy nút j

c
Tỉ lệ tăng của hàm nhẵn
d
Ngưỡng dừng tăng của hàm nhẵn
E(i)\j

Tập các nút i ngoài trừ nút j.
dC(x,y)
Bản đồ sai lệch thực hiện
dT(x,y)
Bản đồ sai lệch mẫu
2.1. Thuật toán BP
Thuật toán BP là thuật toán suy diễn lặp gần đúng dựa trên trường ngẫu nhiên Markov
[3]. Xét mô hình trường ngẫu nhiên Markov (MRF) như hình 2, trong đó, G = (V, E), x=
(xi)iϵV và X = (Xi)iϵV. Xác suất hậu nghiệm (posterior) MAP được xác định là:

p( x)   ( xi )   ( xi , x j )
iV

(1)

iV jV / i

Từ phương trình 1 chúng ta xác định được MAP (maximum a posterior) thông qua
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
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
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
thiểu hóa năng lượng chi phí.

E ( p( x))    log ( xi ) 
iV



 log  ( xi , x j )


(2)

i , jE

Chúng ta đơn giản E(p(x)) thành E(x), khi đó, hàm năng lượng được viết:

E ( x)   D( xi ) 
iV

 V (x , x )
i

(3)

j

i , jE

Trong thị giác nổi thì các nút tương ứng là độ sai lệch và hàm năng lượng chi phí của
cặp nút đến các điểm lân cận dựa trên sự khác nhau giữa các nút. Do vậy hàm:

V ( xi , x j )  V ( xi  x j )

E ( x)   D( xi ) 
iV

(4)

 V (x  x )
i


(5)

j

i , jE

Thông điệp cập nhật tại vòng lặp t được xác định là:

mit j ( x j )  min(V ( xi  x j )  Di ( xi ) 
xi



mst 1i ( xi ))

(6)

sE (i )\ j

Sau T vòng lặp thì độ tin cậy của mỗi nút là:

bj ( x j )  Dj ( f j ) 

T
i j

m

(x j )


(7)

iN ( 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 )

102

(8)

Đ. V. Tuấn, B. T. Thành, “Một giải pháp thực hiện bản đồ … ảnh 3D và bản đồ độ sâu.”


Nghiên cứu khoa học công nghệ

Thông thường hàm năng lượng chi phí nhẵn được xác định theo mô hình tuyến tính.

V ( xi  x j )  min(c xi  x j , d )

(9)

Khi đó thông điệp cập nhật được xác định là:

mit j ( x j )  min(min(c xi  x j , d )  Di ( xi ) 
xi

2.2. Thuật toán CT

Thuật toán CT là thuật toán biến đổi
kiểm 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
[13]. Nguyên lý hoạt động của CT là biến
đổi mỗi điểm ảnh thành 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 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
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 thì tương ứng với bít bằng 1 ngoài ra
thì bít bằng 0.



mst 1i ( xi ))

(10)

sE ( i )\ j

Hình 2. Mô hình MRF.

Chuỗi bít
Khoảng cách
Hamming
CT

Hình 3. Biến đổi CT với cửa sổ 3x3 và khoảng cách Hamming.

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à 30. Các
điểm lân cận có giá trị lớn hơn 30 thì tương ứng với bít bằng 1 ngoài ra thì bít bằng 0. Khi
so sánh chuỗi bít giữa ảnh trái và ảnh phải, đếm số bít khác nhau hai chuỗi bít được gọi là
khoảng cách Hamming và được tính 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ỏ nhất thì được chọn là khớp nhau.

( x0 , y0 )  arg min Hamming(TL ( x, y ), TR ( x  d , y ))

(11)

( x, y )

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
của ảnh camera kép.
3. ĐỀ XUẤT THUẬT TOÁN KẾT HỢP
3.1. Mô tả thuật toán đề xuất
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í
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.

Tạp chí Nghiên cứu KH&CN quân sự, Số 51, 10 - 2017

103


Công nghệ
nghệ thông tin & C
Cơ
ơ sở
s toán học
học cho tin học


(a)
(b)
(c)
(d)
Hình 4. Ảnh hưởng
h ởng của điểm khớp ban đầu: (a) Ảnh camera kép trái, (b) Ảnh camera kép
ph
phải,
ải, (c)Bản đồ sai lệch mẫu vvà
à (d) Bản
Bản đồ sai lệch.
lệch
Đểể khắc phục như
nhược
ợc điểm này, chúng tôi đđềề xuất điểm khớp xuất phát llàà đi
điểm
ểm khớp
trung tâm ccủa
ủa ảnh camera kép. Điểm khớp trung tâm của ảnh camera kép đđư
ợc xác định
ược
dùng phương pháp bi
biến
ến đổi kiểm kkêê CT. Sau khi đđãã xác định
ịnh đđược
ợc điểm khớp trung tâm,
chúng tôi chia ảnh th
thành
nh 4 phần

phần và
và coi đi
điểm
ểm khớp trung tâm llàà đi
điểm
ểm khớp ban đầu để lan
truyền tin cậy cho mỗi phần. Tại mỗi phần, ảnh camera kép đđư
truyền
ược
ợc chia thô tới mịn mức 2
như hhình
ình 5, quá trình này làm gi
giảm
ảm số lư
lượng
ợng ảnh đi 4 lần. Khi chia thô tới mịn mức 2 th
thìì
năng lư
lượng
ợng chi pphí
hí cho m
mỗi
ỗi mức chia đđược
ợc tính theo công thức (12)

E ( x) 

*
i


 D( x )

(12)

i[1,4]

Thông đi
điệp
ệp đđư
ược
ợc lan truyền tin cậy giữa các nút nh
như
ư hình
hình 6 và đồng
ồng thời th
ực hiện BP
thực
cho ccảả bốn phần nhờ vvào
ấu trúc xử lý song song nh
như
ư ph
phần
ần cứng GPU vvàà ph
phần
ần mềm
ào ccấu
CUDA.

Hình 5. Chia thô ttới
ới mịn mức 2.


Hình 6.
6. Sơ đđồ
ồ thông điệp lan truyền.

3.2. Chương tr
trình
ình đ
đề xu
xuấất
Thuậtt toán đ
Thuậ
đềề xu
xuấtt CTBP ((Census
Census Transform Belief Propagation
Propagation))
Đầầu
u vào: Ảnh
Ảnh camera kép có đđộ
ộ phân gi
giảảii cao (m, n, d).
Đầầu
u ra
ra:: Bả
Bản
n đồ
đ sai llệch
ch ảnh
nh camera kép có m
mậtt độ

đ dầy
y đặ
đặcc (m, n).
Các bư
bướ
ớcc thự
thựcc hi
hiện
n:
1. Tìm điểm
đi m khớp
kh p trung tâm ảnh
thuậtt toán CT.
ảnh camera kép dùng thu
2. T
Từ
ừ điểm
đi m khớp
kh p trung tâm, chia ảnh
ảnh thành 4 ph
phầần
n và lấy
l y đi
điểểm
m kh
khớ
ớp
p trung tâm là đi
điểm
m

kh p ban đầ
khớp
đầu
u lan truy
truyềnn tin ccậậy
y cho m
mỗỗii ph
phần
n như hhình
ình 6.
3. Thực
Th c hiệ
hiện
n lan truy
truyềnn tin ccậy
y cả
phầnn đđồng
ng th
thờii như sau:
cả 4 phầ
4. Đặặtt thông điệp
đi p = 0.
5. Thực
Th c hiệ
hiện
n chia thô ttớ
ớii m
n mứ
ình 5.
mịn

mứcc 2 như hhình
6. Tính toán năng lư
lượ
ợng
ng chi phí ttạii mỗi
m i ph
phần
n theo công th
thứcc (12).
7. Cậập
p nhật
nh t thông đi
điệệp
p lan truyền
truy n tin ccậyy xu
xuấtt phát ttừ
ừ điểm
đi m kh
khớpp ban đđầầu
u theo công thứ
thứcc (7).
8. Tính toán đđộ
ộ tin cậ
cậyy ccủaa nút theo công th
thứ
ứcc (8).
9. Nút x*j được
được lựa chọn vvàà xác định
định theo công thức (9).
10. Tính ttổng

ổng năng lư
lượng
ợng chi phí theo công thức (6).

104

Đ. V. Tu
Tuấn,
ấn, B. T. Th
ành, “Một
“Một giải pháp thực hiện bản đồ … ảnh 3D vvà
à bản
bản đồ độ sâu.
sâu.””
Thành,


Nghiên ccứu
ứu khoa học công nghệ

4. KẾT
KẾT QUẢ THỰC NGHIỆM MÔ PHỎNG V
VÀ
À TH
THẢO
ẢO LUẬN
LU ẬN
4.1. D
Dữ
ữ liệu thực nghiệm

Hệệ thống thực nghiệm nh
như
ư hình
hình 7 vvới
ới cấu hhình
ình PC được
ợc mô tả trong bảng 2 vvà ảnh
camera kép trong ttập
ập dữ liệu kiểm thử [14] đđược
ợc mô tả trong bảng 3.

Hình 7.
7 H
Hệệ thống thực nghiệm
nghiệm.
Bảng
ảng 2.
2. Mô ttả
ả cấu hình
hình PC Destop
Destop..
Ph
Phần
ần cứng
Ph
Phần
n mềm
mềm
CPU
RAM

Card màn hình
Hệệ điều hành
hành
Phần
Phần mềm ứng dụng
Intel
8GB Geforce GTX750 Ti
Window 8.1
QT Creator 5.4
core i7
Bộ
ộ nhớ trong: 2GB
64 bít
OpenCV 3.0
Core: 460 nhân
Visual Studio 2013
BUS: 128 bít
CUDA
4.2. Ch
Chỉỉ số đánh giá độ tin cậy RMSE
Để đánh giá độ tin cậy của kết quả thực nghiệm, chúng tôi sử dụng tham số RMSE
Để
(root
root mean squared error: sai ssố
ố toàn
toàn phương trung bbình
ình)) theo công th
thức
ức (13). Tham số
RMSE càng nh

nhỏ
ỏ ccàng
àng ttốt,
ốt, điều đó chứng tỏ kết quả bản đồ sai lệch thực hiện đđược
ợc ccàng
àng
gần
ần vvới
ới bản đồ sai lệch mẫu.
=( ∑
Ký
Độ
ộ sai
Tên ảnh Kích th
thức
ức
hi
hiệu
ệu
lệch
ệch

#1

Baby

620x555

,


|

( , )−

Ảnh trái

( , ))| )

(13)

Bảng
ảng 3. Tập
ập dữ liệu kiểm thử
thử..
Bản
Bản đồ sai lệch
Ảnh phải
mẫu
m

300

Tạp
ạp chí Nghi
Nghiên
ên cứu
cứu KH&CN quân
uân sự,
sự, Số 51, 10 - 2017
2017


105


Công nghệ
nghệ thông tin & C
Cơ
ơ sở
s toán học
học cho tin học

#2

Aloe

641x555

270

#3

Cloth

626x555

290

#4

Flower

pots

656x555

251

#5

Bowling 665x555

240

#6

Book

695x555

200

4.3. K
4.3
Kết
ết quả thực nghiệm vvà
à thảo
thảo luận
Đểể đánh giá hiệu quả của thật toán đề xuất, chúng tôi đđưa
ưa ra m
một
ột số thực nghiệm ccơ

ơ bbản
ản
và so sánh kkết
ết quả với kết quả của
ủa phương
phương pháp đư
được
ợc mô tả trong [7]. Trong thực nghiệm
nghiệm,,
chúng tôi ssử
ử dụng đa dạng ảnh camera kép để kiểm thử với độ phức tạp khác nhau nh
như
ư
bảng
ảng 3 với cấu hhình
ình PC nh
ư bảng
như
bảng 2.
Bảng
Chỉỉ số đánh giá sai số to
toàn
àn phương trung bbình
ình RMSE
RMSE..
Bảng 4. Ch
Ảnh
Thu
Thuật
ật toán BP

Thuật toán đề xuất
Thuật
#1
0.7200
0.7150
#2
1,0921
1,0568
#3
2.2737
1.5560
#4
3.05911
2.9021
#5
4.7338
3.9676
#6
5,0250
3,3840
Kết
ết quả thử nghiệm với 6 mẫu ảnh thu đđư
ược
ợc bản đồ sai lệch nh
như
ư hình
hình 8 và đánh giá đđộ
ộ
tin ccậy
ậy của thuật toán đề xuất với thuật toán BP đư

được
ợc thể hiện trong bảng 4. Để đánh giá
hiệu
ệu quả của thuật toán đề xuất, chúng tôi thực hiện bản đồ sai lệch của 6 mẫu ảnh theo
thuật toán BP nh
thuật
như
ư hhình
ình 9. B
ảng 5 thể hiện hiệu năng thực hiện của thuật toán đề xuất với
Bảng
thuật toán BP dựa tr
thuật
trên
ên hhệệ thống thực
thực nghiệm đđãã mô tả
tả trong bảng 2. Bảng 4 cho thấy thuật
toán đđềề xuất có độ tin cậy cao hhơn
ơn thu
thuật
ật toán BP. Đối với các ảnh #1, #2 vvàà #3 có bbềề mặt
đơn gi
giản
ản sẽ cho kết quả RMSE thấp hhơn
ơn các ảnh #4, #5 vvàà #6 có bbềề mặt ảnh phức tạp.
Điều nnày
Điều
ày lý gi
giải,
ải, đối với các ảnh camera kép có bề mặt đđơn

ơn gi
giản
ản th
thìì sẽ
sẽ thu được
đ ợc bản đồ sai
lệch
ệch gần bản đồ sai lệch mẫu.

106

Đ. V. Tu
Tuấn,
ấn, B. T. Th
ành, “Một
“Một giải pháp thực hiện bản đồ … ảnh 3D vvà
à bản
bản đồ độ sâu.
sâu.””
Thành,


Nghiên cứu khoa học công nghệ

(a)
(b)
(c)
(d)
(e)
(f)

Hình 8. Bản đồ sai lệch dùng thuật toán đề xuất: trong đó (a), (b), (c), (d), (e) và (f) là
bản đồ sai lệch tương ứng của các ảnh #1, #2, #3, #4, #5 và #6.
Bảng 5. Đánh giá hiệu năng thực hiện (ms).
Ảnh
Thuật toán BP
Thuật toán đề xuất
#1
439
182
#2
457
185
#3
442
182
#4
473
187
#5
478
188
#6
494
191
Bảng 5 cho thấy, đối với các ảnh kiểm thử có kích thước tương đương nhau thì thời
gian thực hiện hầu 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 hiệu năng thực hiện bản đồ sai lệch không phụ thuộc vào độ phức tạp của ảnh mẫu
mà chỉ phụ thuộc vào độ phân giải của ảnh. Ngoài ra, bảng 5 còn thể hiện sự hiệu năng của
thuật toán đề xuất tăng khoảng 2,5 lần so với thuật toán BP.


(a)
(b)
(c)
(d)
(e)
(f)
Hình 9. Bản đồ sai lệch dùng thuật toán BP: trong đó (a), (b), (c), (d), (e) và (f) là bản đồ
sai lệch tương ứng của các ảnh #1, #2, #3, #4, #5 và #6.
Các kết quả thực nghiệm được thực hiện trên phần mềm mở OpenCV 3.0. Ngoài ra,
hiện nay còn có phần mềm cũng thực hiện đánh giá bản đồ sai lệch như Matlab [15]. Cả
hai phần mềm này đều là công cụ tốt cho đánh giá bản đồ sai lệch tuy nhiên OpenCV khó
cho người mới tiếp cận nhưng đây là phần mềm mở còn Matlab dễ cho người mới tiếp cận
với những Toolbox có sẵn nhưng phải trả phí khi sử dụng.
5. KẾT LUẬN
Trong bài báo này chúng tôi đề xuất giải pháp cải tiến thuật toán BP [7]. Với những
ảnh camera kép kiểm thử [14] đa dạng về độ phức tạp đã cho kết quả bản đồ sai lệch như
hình 8. Đánh giá hiệu quả của thuật toán đề xuất so với thuật toán BP được thể hiện trong
bảng 4 và bảng 5 trong đó bảng 4 thể hiện so sánh đánh giá độ tin cậy thông qua chỉ số
RMSE còn bảng 5 thể hiện hiệu năng thực hiện thông qua hệ thống PC có cấu hình như
bảng 2.
Chúng tôi đề xuất giải pháp cải tiến thuật toán BP bằng giải pháp thay vì điểm khớp
xuất phát lan truyền tin cậy tại điểm trên cùng bên trái của ảnh camera kép bằng điểm
khớp trung tâm của ảnh. Điểm khớp trung tâm ảnh camera kép được xác định bằng thuật
toán CT. Thuật toán đề xuất cho độ tin cậy cao và hiệu năng thực hiện tăng khoảng 2,5 lần
so với thuật toán BP.
Tạp chí Nghiên cứu KH&CN quân sự, Số 51, 10 - 2017

107



Công nghệ thông tin & Cơ sở toán học cho tin học

Hướng nghiên cứu tiếp theo của bài báo là tìm giải pháp nâng cao xác định điểm khớp
trung tâm của ảnh camera kép để tối ưu hóa năng lượng chi phí khi xác định bản đồ sai
lệch và ứng dụng thuật toán đề xuất vào thị giác robotics. Ngoài ra, còn đánh giá hiệu quả
thuật toán đề xuất dùng phần mềm Matlab.
PHỤ LỤC
Định nghĩa: Khoảng cách Hamming D(x, y) giữa hai véc tơ x,y € F(n) là các hệ số mà
chúng khác nhau. F là một trường hữu hạn
Định luật: D thỏa mãn các đều kiện sau:
1. D(x,y) ≥ 0 và D(x,y) = 0 nếu và chỉ nếu x = y.
2. D(x,y) = D(y,x).
3. D(x,z) ≤ D(x,y) + D(y,z) với mọi y. [16]
TÀI LIỆU THAM KHẢO
[1]. R. Szeliski, "Computer Vision: Algorithms and Applications," Springer-Verlag New
York, 2010.
[2]. M. Stefano, “Stereo vision: Algorithms and Applications,” University of Bologna,
2012.
[3]. A. Blake, P. Kohli, C. Rother, "Markov Random Fields for Vision and Image
Processing," MIT Press, 2011.
[4]. K. Zhang, J. B. Lu, Q. Yang, G. Lafruit, R. Lauwereins and L.V. Gool, “Real-Time
and Accurate Stereo: A Scalable Approach with Bitwise Fast Voting on CUDA”,
IEEE Transactions on Circuits and Systems for Video Technology, vol. 7, no. 21,
2011, pp.867-879.
[5]. S. Jin, J. Cho, X. D. Pham, K. M. Lee, S. K. Park, M. Kim and J. W. Jeon, “FPGA
Design and Implementation of a Real-Time Stereo Vision System”, IEEE
Transactions on Circuits and Systems for Video Technology, vol. 1, no. 20, 2010, pp.
15-26
[6]. Sun, Zheng, Shum, "Stereo matching using belief propagation," IEEE Trans. PAMI,
pp. 787 -800, 2003.

[7]. P. F. Felzenszwalb and D. P. Huttenlocher, "Efficient Belief Propagation for Early,"
Proc. IEEE Int. Conf. Computer Vision and Pattern Recognition, vol. 1, no. 70, pp.
261 - 267, 2004.
[8]. L. Zhang and S. M. Seitz, "Parameter Estimation for MRF Stereo," Proc. IEEE Int'l
Conf. Computer Vision and Pattern Recognition (CVPR '05), pp. 288 - 295, 20 - 25
June 2005.
[9]. N. C. a. T. C. Y. C Tseng, "Low Memory Cost Block - based Belief Propagations for
Stereo Correspondence," 2007 IEEE International conference on Multimedia and
Expo,pp. 1415 - 1418, 2 - 5 july 2007.
[10]. C. K. Liang, C. C. Cheng, Y. C. Lai, L. G. Chen and H. H. Chen, "Hardware
Efficient Belief Propagation," Proc. of IEEE Conf. Computer Vision and Pattern
Recognition, pp. 80 - 87, 20 -25 June 2009.
[11]. Y. C. Tseng and T. S. Chang, "Architecture Design of Belief Propagation for Real
Time Disparity Estimation," IEEE Transaction on Circuits and Systems for Video
Technology, vol. 11, no. 20, pp. 1555 - 1565, 2010.
[12]. L. W. a. N. A. Q. Yang, "A Constant-sapce Belief Propagation Algorithm for Stereo
Matching," IEEE Computer Society Conference on Computer Vision and Pattern

108

Đ. V. Tuấn, B. T. Thành, “Một giải pháp thực hiện bản đồ … ảnh 3D và bản đồ độ sâu.”


Nghiên cứu khoa học công nghệ

Recognition, pp. 1458-1465, 2010.
[13]. Zabih, R. and Woodfill, J., "Non-Parametric Local Transforms for Computing Visual
Correspondence," Proceedingsings of Third European Conference of Computer
Vision, vol. 801, pp. 151 - 158, 1994.
[14]. D. Scharstein and R. Szeliski. Middlebury benchmark..

[15]. Https://www.mathworks.com/help/vision/examples/depth-estimation-from-stereo[16]. video.html
H. Gopalakrishra Gadiyar and P. Padma, “A historical introduction to coding theory
through Hamming’s work,” V. I. T University, Vellore, 2015
ABSTRACT
A SOLUTION TO IMPROVE DISPARITY MAP OF DENSE STEREO CAMERA
APPLICATION 3D IMAGE AND DEPTH MAP
Disparity map is one of the most important parameters of stereo vision. From
disparity map we can derive 3D and deep map of pictures and objects. There are
many proposed algorithms in which Belief Propagation (BP) has been studied and
modified by many researchers. This is an approximation inference algorithm based
on Markov Random Fields model with global optimization for high accuracy.
Almost standard and modified BP algorithms have starting point is on the left-top of
pictures to propagate believable messages in order to derive disparity map. In this
paper, an advanced BP algorithm is proposed whereas the proposed algorithm with
center pixel is started. The center pixel is determined by using global Census
Tranform method. Then, believable messages around to derive disparity map are
propagated. Simulation result on CPU and GPU show that this proposed method
has 2.5 times fasster computing and higher reliability in compared with standard
BP.
Keywords: Disparity map, Stereo vision, Belief propagation, Census transform, Stereo camera, Semi-Global.

Nhận bài ngày 05 tháng 9 năm 2017
Hoàn thiện ngày 05 tháng 10 năm 2017
Chấp nhận đăng ngày 25 tháng 10 năm 2017
Địa chỉ: Trường Đại học Sư phạm Kĩ thuật Hưng Yên.
*
Email:

Tạp chí Nghiên cứu KH&CN quân sự, Số 51, 10 - 2017


109