Tổng Quan
Vấn đề theo vết đối tượng trong video đã và đang thu hút được nhiều sự
quan tâm của cộng đồng nghiên cứu bởi nó có nhiều ứng dụng hữu ích trong
lĩnh vực giải trí , truyền thông , thị giác máy tính và đa phương tiện , chẳng
hạn như ứng dụng trong xử lý và biên tập video số , trong nén video , trong
các thư viện số , trong các hệ thống giám sát giao thông .v.v Đối tượng
trong video , hay ngắn gọn là đối tượng video , là những thành phần có ý
nghĩa đầy đủ của một khung cảnh . Theo vết đối tượng bao gồm việc theo
vết đường biên , theo vết những chuyển động cục bộ và những biến đổi về
cường độ (độ sáng tối , độ tương phản) của đối tượng đó .
Nội dung chính của luận văn này là nghiên cứu và thực hiện việc theo vết
đối tượng theo hướng tiếp cận mới : sử dụng lưới hai chiều . Theo đó , vấn
đề theo vết đường biên , theo vết những chuyển động cục bộ và những biến
đổi về cường độ sẽ được hợp nhất lại thành vấn đề theo vết lưới 2 chiều .
Lưới ở đây được thiết kế dựa theo nội dung của đối tượng giúp cho việc theo
vết đối tượng được chính xác hơn . Quá trình ước lượng chuyển động tại các
node của lưới được ràng buộc chặt chẽ để bảo toàn kết cấu của lưới
Mục lục
1 Giới Thiệu
1.1 Động lực thúc đẩy
1.2 Một số hướng tiếp cận
1.3 Bố cục luận văn
2 Một Số Khái Niệm Nền Tảng
2.1 Một số lĩnh vực liên quan
2.2 Biến dạng ảnh số
2.3 Video , video tương tự , video số
2.4 Đối tượng video , chuyển động của đối tượng video , ước lượng chuyển
động
2.5 Hiện tượng che phủ
3 Mô Hình Theo Vết Đối Tượng Video
3.1 Tạo lưới
3.2 Ước lượng chuyển động tại các node của lưới
3.3 Lan truyền lưới
4 Cài Đặt và Thử Nghiệm
4.1 Chi tiết cài đặt
4.2 Kết quả thử nghiệm
5 Kết Luận và hướng Phát triển
76 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2872 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Sử dụng lưới hai chiều để theo vết đối tượng trong Video, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
lưới) được giả thiết là vùng có chuyển động đồng nhất và chuyển
động này có thể được biểu diễn chính xác bằng một phép biến đổi không
gian (affine , bilinear , …) . Phép biến đổi này có thể được suy ra từ vectơ
chuyển động tại các đỉnh của mắt lưới đang xét . Thực tế đã cho thấy , biểu
diễn đối tượng và theo vết đối tượng bằng cách sử dụng lưới 2 chiều cho ra
kết quả chính xác hơn và ổn định hơn. Việc xác định vectơ chuyển động tại
từng node riêng lẻ thường đem lại kết quả không như ý do các vectơ tìm
được có thể đan chéo nhau . Để giải quyết vấn đề này , Nakaya [22] đề ra
một phương pháp so khớp sáu cạnh , theo đó một lưới đồng dạng (các phần
tử tức các mắt lưới có hình dạng và kích thước giống nhau – hình 1.3a) được
áp lên đối tượng , các node bên trong sẽ được di chuyển trong một vùng giới
hạn bởi 6 cạnh (hình 1.2) để dò ra vị trí tương ứng trong frame tiếp theo .
Toklu [5] mở rộng phương pháp này bằng cách sử dụng mô hình lưới đồng
dạng phân cấp , theo đó việc ước lượng chuyển động sẽ được thực hiện trên
lưới có mật độ từ thưa đến dày .
Hình 1.2 : phương pháp so khớp sáu cạnh
9
Hình 1.3 : lưới : a) đồng dạng , b) dựa theo nội dung khung cảnh
Tuy nhiên , cả Toklu và Nakaya đều sử dụng lưới đồng dạng , bản thân
dạng lưới được tạo bằng cách chia ảnh ra thành các phần bằng nhau do đó
không phản ánh được nội dung của khung cảnh , mỗi phần tử của lưới có
thể chứa nhiều chuyển động cùng một lúc . Altunbasak giải quyết vấn đề này
bằng cách sử dụng lưới có thiết kế dựa theo nội dung đối tượng (hình 1.3b) .
Tuy nhiên , trong phương pháp này , đối tượng được xem là toàn bộ frame
10
chứ không riêng một đối tượng cụ thể nào . Từ những nghiên cứu trên , luận
văn đề ra một mô hình theo vết đối tượng bán tự động cho phép người dùng
chọn ra đối tượng bất kì , đối tượng sẽ được biểu diễn bằng một lưới tam
giác hai chiều được thiết kế dựa theo nội dung của đối tượng và được theo
vết một cách hoàn toàn tự động ở các frame tiếp theo . Quá trình ước lượng
chuyển động tại các node được ràng buộc chặt chẽ để bảo toàn kết cấu của
lưới .
1.3 Bố cục luận văn
Trong chương 1 này , luận văn đã trình bày những động lực thúc đẩy
nghiên cứu vấn đề theo vết đối tượng , trình bày một số hướng tiếp cận đã
được đề ra . Phần còn lại của luận văn sẽ được tổ chức như sau :
– Ở chương 2 , luận văn sẽ trình bày những khái niệm và nội dung nền tảng
liên quan đến vấn đề theo vết đối tượng .
– Trong chương 3 , luận văn sẽ trình bày chi tiết về mô hình theo vết đối
tượng sử dụng lưới hai chiều mà luận văn đã nghiên cứu và đề ra .
– Ở chương 4 , luận văn sẽ trình bày về phần cài đặt thử nghiệm thực tế .
– Cuối cùng , trong chương 5 , luận văn sẽ đưa ra kết luận và hướng phát
triển tương lai .
11
Chương 2
Những khái niệm và nội dung
nền tảng
2.1 Một số lĩnh vực liên quan
Các phương pháp theo vết đối tượng trong video số thường sử dụng
những kĩ thuật thuộc nhiều lĩnh vực khác nhau . Kết quả của việc theo vết
cũng được ứng dụng trở lại trong nhiều lĩnh vực khác nhau . Trong phần này
, luận văn sẽ giới thiệu sơ qua một số lĩnh vực quan trọng có liên quan , bao
gồm xử lý ảnh số (digital image processing) , đồ họa máy tính (computer
graphics) , thị giác máy tính (computer vision) , đa phương tiện (multimedia)
và xử lý video số (digital video processing) . Riêng biến dạng ảnh số (digital
image warping) , một nhánh của xử lý ảnh , là một lĩnh vực mới được biết
đến và có những nội dung quan trọng nên sẽ được trình bày trong một phần
riêng .
Xử lý ảnh số (digital image processing)
Xử lý ảnh số , đúng như tên gọi của nó , bao gồm việc phân tích và xử lý
các ảnh số bằng máy tính . Mục đính chính của xử lý ảnh là tăng cường mức
độ thu nhận thông tin của con người từ nguồn dữ liệu ảnh và làm cho máy
tính có thể tự động xử lý (lưu trữ , biểu diễn , trao đổi …) các hình ảnh thu
nhận từ môi trường tự nhiên .
12
Hình 2.1 : Xử l ý ảnh
Đồ họa máy tính
Đồ họa máy tính bao gồm tất cả những gì liên quan đến việc sử dụng
máy tính để phát sinh ra hình ảnh . So với xử lý ảnh thì đồ họa máy tính
đóng vai trò như một họa sĩ , còn xử lý ảnh đóng vai trò như một thợ chụp
ảnh .
Thị giác máy tính (computer vision)
Thị giác máy tính là hướng ngược lại của đồ họa máy tính . Trong khi đồ
họa lấy thông tin mô tả cảnh bên ngoài (scene discription) để tạo ra ảnh
trong máy tính thì thị giác máy tính lại từ ảnh bên trong máy tính để suy ra
thông tin mô tả cảnh bên ngoài .
13
Hình 2.2 : Tương quan giữa xử lý ảnh , đồ họa máy tính và thị giác máy tính
Đa phương tiện (multimedia)
Thuật ngữ “đa phương tiện” diễn đạt ý tưởng các thông tin trong máy
tính có thể được biểu diễn bằng các âm thanh , hình ảnh video sinh động chứ
không chỉ giới hạn trong những cách biểu diễn truyền thống (văn bản , ảnh
tĩnh.v.v…) .
Lĩnh vực multimedia đề cập đến việc sử dụng máy tính để tích hợp các
dạng dữ liệu như văn bản , hình ảnh tĩnh , hình ảnh động (video) , âm thanh
hay bất kì dạng dữ liệu số nào .
Xử lý video số
Xử lý video số tức là xử lý luồng dữ liệu video số (digital video
bitstream) , bao gồm các công việc như thu nhận , lưu trữ , phân tích , tổng
hợp , trao đổi .v.v…
14
2.2 Biến dạng ảnh số (digital image warping)
Biến dạng ảnh số , hay rõ hơn là biến đổi (về mặt hình học) ảnh số , là
một nhánh của xử lý ảnh . Biến đổi về mặt hình học (geometric
transformation) là thao tác xác lập lại mối tương quan về vị trí giữa các điểm
trên ảnh . Cốt lõi của biến đổi hình học là ánh xạ một hệ tọa độ này sang một
hệ tọa độ khác . Điều này được thực hiện thông qua một biến đổi không gian
(spatial transformation) , đây là một hàm ánh xạ thiết lập sự tương ứng giữa
các điểm trên ảnh đầu vào và các điểm trên ảnh đầu ra . Hàm ánh xạ này có
thể biểu diễn theo hai cách sau :
[x , y] = [X(u,v) , Y(u,v)]
hay :
[u , v] = [U(x,y) , V(x,y)]
Trong đó [u , v] chỉ vị trí của điểm ảnh trên ảnh input tương ứng với điểm
ảnh ở vị trí [x , y] trên ảnh output ; còn X , Y , U , V là các hàm ánh xạ đặc
trưng cho từng phép biến đổi cụ thể . Do X và Y thực hiện việc ánh xạ từ
ảnh input sang ảnh output nên được gọi là các ánh xạ tiến (forward mapping)
, tương tự , U và V được gọi là các ánh xa lùi (backward mapping) hay ánh
xạ ngược (inverse mapping) . Ánh xạ tiến thực hiện việc sao chép từng pixel
trên ảnh input sang ảnh output tai các vị trí do ánh xạ xác định . Còn ánh xạ
ngược thì thực hiện việc đối chiếu từng vị trí trên ảnh output sang ảnh input ,
sau đó sao chép pixel tại vị trí vừa tìm được trên ảnh input sang vị trí tương
ứng trên ảnh output .
15
Một vấn đề phát sinh là các giá trị vị trí lúc ban đầu là số nguyên , sau khi
qua hàm ánh xạ thì trở thành số thực . Điều này gây ra hiện tượng lỗ hổng và
hiện tượng chồng lên nhau . Lỗ hổng ở đây chỉ những pixel không có đối
tượng nào tương ứng . Còn hiện tượng chồng lên nhau là hiện tượng nhiều
pixel cùng được ánh xạ tương ứng vào một pixel .
Hình 2.3 : Ánh xạ tiến
16
Hình 2.4 : Ánh xạ ngược
Ta có thể giảm bớt hiện tượng này bằng cách chia ảnh ra thành các vùng nhỏ
(patch) , chẳng hạn như chia thành các vùng hình vuông . Việc ánh xạ khi đó
sẽ không thực hiện trên đơn vị điểm ảnh mà thực hiện tại từng vùng . Cách
này giúp bảo toàn kết cấu liền lạc của ảnh .
Trong phần tiếp theo , luận văn sẽ trình bày các phép biến đổi không gian
được sử dụng trong mô hình theo vết đối tượng . Ở đây ta chỉ xét các phép
biến đổi 2 chiều . Việc biểu diễn phép biến đổi được thực hiện trong hệ tọa
độ thuần nhất (Homogeneous Coordinates) , đây là hệ tọa độ do tác giả
Roberts đề ra năm 1965 trong lĩnh vực đồ họa máy tính nhằm đảm bảo tính
nhất quán trong cách biểu diễn các phép biến đổi .
17
2.2.1 Biến đổi affine (Affine transformation)
Phép biến đổi affine là phép biến đổi tuyến tính , thuận nghịch , có dạng
biểu diễn tổng quát như sau :
[ ] 11 1221 22
31 32
0
, ,1 [ , ,1] 0
1
a a
x y u v a a
a a
=
Từ đó suy ra :
11 21 31
12 22 32
x a u a v a
y a u a v a
= + +
= + +
Những tính chất quan trọng của phép biến đổi affine là :
– Bảo toàn đường thẳng : ảnh của một đường thẳng qua phép biến đổi
affine là một đường thẳng
– Bảo toàn tính song song của các đường thẳng : ảnh của hai đường
thẳng song song là hai đườn song son
– Bảo toàn tỉ lệ về khoảng cách : giả sử C là điểm chia đoạn AB theo tỉ
số t . Nếu A’ , B’ , C’ lần lượt là ảnh của A , B , C qua phép biến đổi
affine thì C’ cũng sẽ chia A’B’ theo tỉ số t .
18
Hình 2.5 : Phép biến đổi affine
Một số trường hợp đặc biệt của phép biến đổi affine là : phép tịnh tiến
(translation) , phép quay (rotation) , phép biến đổi tỉ lệ (scale) , phép kéo
xiên (shear) .
Tịnh tiến (Translation)
Gọi Tu , Tv là độ dời tương ứng với u , v , dạng biểu diễn của phép tịnh
tiến là :
[ ]
1 0 0
, ,1 [ , ,1] 0 1 0
1u
x y u v
T Tv
=
Quay (Rotation)
Gọi θ là góc quay , dạng biểu diễn của phép quay là :
19
[ ]
cos sin 0
, ,1 [ , ,1] sin cos 0
0 0 1
x y u v
θ θ
θ θ
= −
Biến đổi tỉ lệ (Scale)
Gọi Su , Sv là các hệ số tỉ lệ tương ứng với u và v , dạng biểu diễn của
phép biến đổi tỉ lệ là :
[ ]
0 0
, ,1 [ , ,1] 0 0
0 0 1
u
v
S
x y u v S
=
Kéo xiên (Shear)
Gọi Hu hệ số kéo xiên theo phương trục hoành , dạng biểu diễn của phép
kéo xiên theo phương trục hoành có dạng :
[ ]
1 0
, ,1 [ , ,1] 0 1 0
0 0 1
uH
x y u v
=
Gọi Hv hệ số kéo xiên theo phương trục tung , dạng biểu diễn của phép
kéo xiên theo phương trục tung có dạng :
20
'
'
xx
w
= '
'
yy
w
=
[ ]
1 0 0
, ,1 [ , ,1] 1 0
0 0 1
vx y u v H
=
2.2.2 Biến đổi phối cảnh (Perspective transformation)
Dạng biểu diễn tổng quát của phép biến đổi phối cảnh là :
[ ] 11 12 1321 22 23
31 32 33
', ', ' [ , , ]
a a a
x y w u v w a a a
a a a
=
Với : ,
Từ đó suy ra :
11 21 31
13 23 33
'
'
a u a v axx
w a u a v a
+ += = + +
12 22 32
13 23 33
'
'
a u a v ayy
w a u a v a
+ += = + +
21
Hình 2.6 : Phép biến đổi phối cảnh
2.3 Video , video tương tự , video số
Việc theo vết đối tượng được thực hiện trên dữ liệu video , chính xác là
trên dữ liệu video số , nên hiểu rõ về dạng dữ liệu này là điều cần thiết .
2.3.1 Video
Thuật ngữ video dùng để chỉ nguồn thông tin hình ảnh trực quan
(pictorial visual information) , bao gồm một chuỗi các ảnh tĩnh (still image)
liên tiếp nhau , được sắp xếp theo chiều thời gian . Video còn được gọi là
ảnh thay đổi theo thời gian (time-varying image) , kí hiệu là s( x1 , x2 , t ) ,
trong đó x1 , x2 là các biến chỉ vị trí trong không gian , còn t là biến thời gian
. Một ảnh tĩnh là một phân bố cường độ theo không gian và phân bố này là
không đổi theo thời gian . Trong khi ảnh thay đổi theo thời gian là một phân
22
bố cường độ theo cả không gian lẫn thời gian . Xét về mặt vật lý , ở cấp thấp
nhất , video tồn tại dưới dạng các tín hiệu .
Tín hiệu là một hàm chứa đựng thông tin [3] , hay nói một cách khác , tín
hiệu là một mô tả chi tiết sự phụ thuộc của một tham số này vào một tham số
khác [2] . Nếu miền giá trị của 2 tham số này là liên tục thì tín hiệu được gọi
là tương tự , nếu miền giá trị là rời rạc thì tín hiệu được gọi là rời rạc hay gọi
là được số hóa . Cũng có những trường hợp , miền giá trị của tham số này là
rời rạc , của tham số kia lại là liên tục , nhưng những trường hợp này rất
hiếm khi xảy ra và tín hiệu lúc đó cũng không có một cách gọi tổng quát nào
. Hầu hết các tín hiệu tương tự xuất hiện trong thế giới tự nhiên , còn các tín
hiệu rời rạc (số) thì xuất hiện trong thế giới máy tính . Cần nhấn mạnh là
máy tính chỉ hiểu được các tín hiệu đã được số hóa .
Ban đầu video được thu nhận , lưu trữ và truyền dẫn dưới dạng tương tự .
Những năm gần đây , sự phát triển mạnh mẽ của công nghệ phần cứng ,
công nghệ xử lý ảnh , cùng với những ưu điểm nổi bật của định dạng số
đang hướng người sử dụng đến với video số .
2.3.2 Video tương tự (analog video)
Tín hiệu tương tự là tín hiệu điện tử một chiều biến đổi theo thời gian , kí
hiệu là f(t) . Cho một ảnh biến đổi theo thời gian ở dạng tương tự (tương
ứng với hình ảnh trong tự nhiên) , kí hiệu là sc( x1 , x2 , t) . Tín hiệu video
tương tự thu được bằng cách lấy mẫu sc( x1 , x2 , t) theo chiều dọc x2 và
chiều thời gian t . Tiến trình lấy mẫu được thực hiện theo chu kì và được gọi
là tiến trình quét (scanning) . Phương pháp quét thường được sử dụng nhất là
23
quét liên tiếp (progressive scanning) và quét luân phiên (interlaced
scanning).
Trong phương pháp quét liên tiếp , cứ sau một khoảng thời gian ∆t , việc
quét lại được thực hiện trên toàn ảnh (hình 1.1) . Phương pháp này thường
được sử dụng đối với các màn hình có độ phân giải và tấn số quét cao .
Hình 2.7 : Phương pháp quét liên tục
Trong phương pháp quét luân phiên , cứ sau một khoảng thời gian ∆t/2 ,
việc quét lại được thực hiện trên các dòng hoặc là chẵn , hoặc là lẻ , nếu ở
lần quét trước là dòng chẵn thì ở lần quét này là dòng lẻ và ngược lại (hình
2.2) . Phương pháp này thường được sử dụng đối với các màn hình có độ
phân giải và tần số quét thấp
Hình 2.8 : Phương pháp quét luân phiên
24
Các thông số kĩ thuật quan trọng của tín hiệu video tương tự là độ phân
giải theo chiều dọc (vertical resolution) , tỉ lệ kích thước (aspect ratio) và tần
số làm tươi (refresh rate) . Tỉ lệ kích thước là tỉ lệ giữa chiều ngang và chiều
dọc . Tần số làm tươi là số lượng frame chiếu trong 1 giây .
Ở trên là trường hợp tín hiệu video đơn sắc (monochromatic video signal)
. Ta có thể mở rộng ra cho trường hợp tín hiệu video nhiều màu sắc . Theo
Lý thuyết ba tác nhân của màu sắc (tri-stimulus theory of color) , mọi màu
sắc đều có thể được tái tạo bằng cách kết hợp 3 màu nguyên tố : đỏ (red – R)
, xanh dương (blue – B) và xanh lá cây (green – G) , theo một tỉ lệ thích hợp
. Hình ảnh nhiều màu sắc sẽ được tạo bằng cách chồng 3 lớp tương ứng với
3 màu nguyên tố lên nhau .
Hiện nay , có nhiều chuẩn video tương tự (analog video standards) đang
được sử dụng , chúng khác nhau về các tham số hình ảnh (chẳng hạn như độ
phân giải theo không gian và thời gian) và cách xử lý màu sắc . Các chuẩn
này có thể được phân thành 3 nhóm :
• Video tương tự đa thành phần (component analog video – CAV)
• Video tổng hợp (composite video)
• S-video
Trong trường hợp video tương tự đa thành phần , các đơn vị cấu thành
tín hiệu video được phân chia thành các tín hiệu video đơn sắc riêng biệt .
Các đơn vị này có thể đơn giản là 3 màu nguyên tố : đỏ , xanh dương , xanh
lá cây , hoặc được biến đổi thành dạng biểu diễn độ sáng – màu sắc
(luminance – chrominance) . Thành phần luminance (kí hiệu là Y) thể hiện
các mức xám (gray level) của video , và được tính từ 3 màu nguyên tố như
sau :
25
Y = 0.30R + 0.59G + 0.11B
Thành phần chrominance chứa đựng thông tin về màu sắc . Ứng với mỗi
chuẩn , thành phần chrominance lại có cách biểu diễn khác nhau , chẳng hạn
như :
Thành phần chrominance được biểu diễn thành I , Q , với :
I = 0.60R + 0.28G – 0.32B
Q = 0.21R – 0.52G + 0.31B
Hoặc thành phần chrominance được biểu diễn thành Cr , Cb , với :
Cr = R – Y
Cb = B – Y
Trong thực tế , tín hiệu video với cách cấu tạo đa thành phần tạo ra chất
lượng màu sắc tốt nhất . Tuy nhiên , điều này đòi hỏi quá trình truyền dẫn
các thành phần phải được đồng bộ hóa chính xác , đồng thời băng thông
cũng phải tăng lên gấp ba lần so với tín hiệu đơn sắc .
Trong trường hợp video tổng hợp , tín hiệu video được định dạng theo
hình thức : các thành phần chrominance được mã hóa vào đầu thành phần
luminance , hợp thành một tín hiệu duy nhất . Điều này giúp tiết kiệm băng
thông và đơn giản hóa quá trình truyền dẫn tín hiệu . Các định dạng video
tổng hợp phổ biến hiện nay là NTSC (National Television System
Committee hay Never Twice the Same Color) , PAL (Phase Alternating
Line) , SECAM (Sequential Couleur Avec Memoire hay Sequential
Chrominance Signal with Memory) . Chuẩn NTSC được sử dụng phổ biến ở
khu vực Bắc Mĩ và Nhật Bản ; chuẩn SECAM được sử dụng ở Pháp , Đông
Âu , Liên Xô và vùng Trung Đông ; chuẩn PAL được sử dụng ở khu vực hầu
hết các khu vực còn lại , bao gồm Tây Âu , Anh , Nam Mĩ , Châu Á .v.v…
26
Một khuyết điểm của video tổng hợp là chất lượng màu sắc tạo ra không
tốt . S–video là một giải pháp trung hòa giữa video tổng hợp và video đa
thành phần .Tín hiệu trong S–video được phân thành 2 bộ phận , một cho
thành phần luminance và một cho các thành phần chrominance đã được tổng
hợp lại . Nhờ vậy , chất lượng màu sắc trong S–video tốt hơn trong video
tổng hợp đồng thời băng thông để truyền tín hiệu S–video cũng tốn ít hơn
băng thông dùng cho video đa thành phần . Chuẩn S–video hiện đang được
sử dụng rộng rãi trong các máy ghi videocasette , máy quay phim .v.v…
Việc thu nhận video tương tự chủ yếu dựa trên công nghệ băng từ , trừ
trường hợp đĩa laser là sử dụng công nghệ quang học .
Với video tương tự , các hình ảnh trong thế giới tự nhiên đã được thu
nhận chính xác . Tuy nhiên , do bản chất của nó , video tương tự cung cấp
cho người dùng rất ít khả năng tương tác và xử lý , chỉ có thể đơn giản như
chuyển kênh TV hay quay tới quay lui , chiếu nhanh chiếu chậm một đoạn
băng . Những năm gần đây , sự phát triển mạnh mẽ của công nghệ phần
cứng , những tiến bộ trong công nghệ xử lý ảnh và nhất là những ưu điểm
nổi bất của định dạng số đang hướng người sử dụng đến với video số . Trong
thế giới số , tận dụng sức mạnh của máy tính , ta có thể dễ dàng thu nhận ,
lưu trữ , biên tập , xử lý và trao đổi hình ảnh video .
2.3.3 Video số
Để có được tín hiệu video , tương tự (analog) hay số (digital) , cần phải
thực hiện việc lấy mẫu ảnh sc( x1 , x2 , t) theo cả chiều không gian và thời
gian . Đối với video tương tự , việc lấy mẫu được thực hiện theo chiều dọc
27
x2 (tung độ) và theo chiều thời gian t . Đối với video số , việc lấy mẫu được
thực hiện trên cả 3 chiều : chiều ngang x1 (hoành độ) , chiều dọc x2 (tung độ)
và chiều thời gian t . Thực chất , để thu được tín hiệu video số , ta cần phải
thực hiện việc số hóa (digitization) , gồm 2 bước : lấy mẫu (sampling) và
lượng tử hóa (quantization) . Lấy mẫu là tiến trình chuyển đổi tín hiệu từ
dạng liên tục theo không gian và thời gian sang dạng rời rạc theo không gian
và thời gian . Sau khi lấy mẫu , các tín hiệu thu được tuy đã ở dạng rời rạc
nhưng chúng vẫn có giá trị ở dạng liên tục . Do đó ta cần phải thực hiện việc
lượng tử hóa , tức là chuyển các giá trị từ dạng liên tục (cụ thể là dạng số
thực) sang dạng rời rạc (số nguyên) .
Hình 2.9 : Quá trình số hóa
Các thông số kĩ thuật quan trọng của video số là độ phân giải theo chiều
dọc (số pixel trên một cột) , độ phân giải theo chiều ngang (số pixel trên một
dòng) , tỉ lệ kích thước (chiều ngang / chiều dọc) và tần số làm tươi . Băng
thông của video được tính theo công thức :
28
FR = Tần số frame (tần số làm tươi)
NL = Số dòng trên 1 frame
HR = Độ phân giải theo chiều ngang
ρ = thời gian chuyển tín hiệu từ giữa 2 dòng kế tiếp nhau
Hầu hết các hệ thống video số đều biểu diễn màu sắc dưới dạng các thành
phần riêng biệt (tương tự video analog đa thành phần) . Ngay cả khi đầu vào
là tín hiệu video tương tự tổng hợp (composite video) thì đầu tiên nó cũng
phải được chuyển sang dạng video tương tự đa thành phần (CAV) , sau đó
từng thành phần sẽ được số hóa để cuối cùng thu được tín hiệu video số .
Việc trao đổi video số giữa các ứng dụng cũng như giữa các hệ thống đòi
hỏi việc chuẩn hóa . Ngành công nghiệp máy tính (computer industry) có
các chuẩn về độ phân giải lúc hiển thị , ngành công nghiệp truyền hình (TV
industry) có các chuẩn về thu phát , ngành công nghiệp truyền thông
(communications industry) có các chuẩn về giao thức mạng .
Do ta chỉ làm việc với video số nên từ đây về sau , khi đề cập đến video tức
là đề cập đến video số .
2.4 Đối tượng video , chuyển động của đối tượng
video , ước lượng chuyển động
Trong phần này , luận văn sẽ trình bày những khái niệm và nội dung cơ
bản của vấn đề theo vết đối tượng .
29
2.4.1 Đối tượng video (video object – VO)
Xét đoạn video quay một khung cảnh , đối tượng trong đoạn video , hay
ngắn gọn là đối tượng video , là những thành phần có ý nghĩa đầy đủ trong
khung cảnh đó . Thật ra , khái niệm đối tượng video rất linh động , nó có thể
là bất kì thành phần trong khung cảnh , miễn sao đó là thành phần mà ta
quan tâm . Phần còn lại của khung cảnh thường được gọi là nền
(background) . Tập hợp tất cả các điểm ảnh thuộc đối tượng tạo thành mặt
phẳng alpha (Alpha plane – AR) của đối tượng đó .
2.4.2 Chuyển động của đối tượng video
Một đoạn video chứa đựng được nhiều thông tin trực quan hơn một ảnh
tĩnh , do video có khả năng thu giữ được chuyển động . Một ảnh tĩnh chỉ có
thể cung cấp cho người xem những thông tin tĩnh về một khung cảnh trong
khi một đoạn video có thể đem lại cho người xem phần động trong khung
cảnh đó .
Hình ảnh mà ta nhìn thấy trong video là hình chiếu của những khung
cảnh 3 chiều lên mặt phẳng 2 chiều (mặt phẳng ảnh) . Do đó , chuyển động
của các đối tượng video cũng chính là hình chiếu chuyển động của các đối
tượng trong không gian 3 chiều lên mặt phẳng ảnh . Tuy nhiên , khi quan sát
các hình ảnh video , không phải lúc nào ta cũng thấy được những chuyển
động thật sự . Nguyên nhân chính là do mắt người nhận ra chuyển động
(trong video) dựa trên sự thay đổi về cường độ của điểm ảnh . Do đó , có
những trường hợp ta không nhận ra được chuyển động , ví dụ : quan sát hình
ảnh một quả bóng đồng màu quay quanh trục qua tâm , mặc dù có chuyển
động xảy ra nhưng do cường độ các điểm ảnh không đổi nên mắt ta không
nhận ra được
30
Hình 2.10 : Quả bóng đồng màu quay quanh trục qua tâm
Lại có những trường hợp ta ngộ nhận chuyển động , ví dụ : ánh sáng môi
trường thay đổi , mặc dù thật sự vật đứng yên nhưng ta vẫn có cảm nhận vật
đã di chuyển
frame k frame k+1
Hình 2.11 : Ánh sáng môi trường thay đổi
Để tách biệt rõ ràng giữa chuyển động thật sự và chuyển động do mắt
người cảm nhận , người ta đưa ra khái niệm luồng thị giác (optical flow).
Theo đó , chuyển động hai chiều (2-D motion) , tức chuyển động thật sự , là
hình chiếu của chuyển động ba chiều lên mặt phẳng ảnh , còn luồng thị giác
là những chuyển động mà mắt người nhận ra được dựa trên những thay đổi
về cường độ của các điểm ảnh theo thời gian . Do thực tế ta chỉ có thể quan
31
sát được luồng thị giác nên từ đây về sau , khi đề cập đến chuyển động tức là
ta đề cập đến luồng thị giác .
Chuyển động của đối tượng video có thể phân thành 2 loại : chuyển động
cục bộ (local motion) và chuyển động toàn cục (global motion) . Chuyển
động cục bộ là chuyển động do bản thân đối tượng tạo ra , là những chuyển
động giữa các bộ phận của đối tượng so với nhau . Còn chuyển động toàn
cục là chuyển động của đối tượng , xét trên tổng thể , so với camera , hay có
thể nói là chuyển động do camera tạo ra .
Hình 2.12 : Chuyển động toàn cục và chuyển động cục bộ
2.4.3 Ước lượng chuyển động (motion estimation)
Ước lượng chuyển động của một điểm ảnh là tìm ra vectơ dịch chuyển
của điểm ảnh đó . Khái niệm về vectơ dịch chuyển d
ur
, được minh họa trong
hình 2.12 . Mở rộng ra , ước lượng chuyển động của một đối tượng là ước
lượng chuyển của tất cả các điểm ảnh thuộc đối tượng đó . Mục đích của
32
việc ước lượng chuyển động là để trả lời cho câu hỏi “chuyển động diễn ra
như thế nào ?” .
Như vậy , việc theo vết đối tượng có thể được xem là việc ước lượng
chuyển động tại các frame liên tiếp nhau , kết quả ước lượng tại frame này là
cơ sở cho việc ước lượng ở frame tiếp theo .
Hìn 2.12 : Vectơ dịch chuyển d
ur
2.5 Hiện tượng che phủ (occlusion)
Trong thực tế , tiến trình theo vết đối tượng video thường gặp phải hiện
tượng che phủ . “Che phủ” đề cập đến hiện tượng các bộ phận của đối tượng
(hay của khung cảnh) bị che đi hay hiện ra do những chuyển động của
33
camera hay của chính đối tượng . Hiện tượng này được phân làm hai loại : tự
che phủ (self-occlusion) và che phủ lẫn nhau (mutual occlusion) . Tự che
phủ chỉ hiện tượng các bộ phận của đối tượng bị che mất đi hay được hiện ra
do những chuyển động của bản thân đối tượng . Che phủ lẫn nhau chỉ hiện
tượng các bộ phận của đối tượng bị che mất đi hay được hiện ra do những
chuyển động của đối tượng khác .
Hình 2.13 : Hiện tượng tự che phủ
Hình 2.14 : Hiện tượng che phủ lẫn nhau
34
Chương 3
Mô hình theo vết đối tượng
sử dụng lưới hai chiều
Xét đoạn video quay một khung cảnh , đối tượng video là những thành
phần có ý nghĩa đầy đủ trong khung cảnh đó . Mặt phẳng alpha (alpha plane
– AR) của một đối tương video được định nghĩa là tập hợp tất cả các điểm
thuộc đối tượng đó .
Theo vết đối tượng bao gồm việc theo vết đường biên (boundary) , theo
vết những chuyển động cục bộ (local motion) và những biến đổi về cường
độ (độ sáng tối , độ tương phản) của đối tượng .
Theo mô hình mà luận văn đề ra , đối tượng video được biểu diễn bằng
một lưới tam giác hai chiều . Lưới được thiết kế dựa theo nội dung của đối
tượng . Việc theo vết đường biên (chuyển động toàn cục) , chuyển động cục
35
bộ cũng như những biến đổi về cường độ giờ trở thành việc theo vết lưới hai
chiều .
Như đã trình bày trong chương 1 , mô hình mà luận văn đề ra là mô hình
bán tự động . Theo đó , người dùng sẽ đảm nhận trách nhiệm chọn frame bắt
đầu , gọi là frame tham chiếu (reference frame) , và trên frame này chọn ra
đối tượng video được quan tâm (tức là xác định mặt phẳng alpha của đối
tượng được quan tâm) . Sau đó , trong các frame tiếp theo , việc theo vết đối
tượng sẽ được thực hiện hoàn toàn tự động .
Tổng quát , tiến trình theo vết đối tượng bao gồm các bước sau :
o Bước 1 : Chọn frame tham chiếu và chọn đối tượng video được quan
tâm
o Bước 2 : Tạo lưới tam giác cho đối tượng
o Bước 3 : Ước lượng chuyển động tại các node của lưới
o Bước 4 : Lan truyền lưới
Bước 1 và 2 được thực hiện tại frame tham chiếu , bước 3 và 4 được thực
hiện tại mỗi frame tiếp theo .
Người dùng chọn ra đối tượng bằng cách xác định mặt phẳng alpha của
đối tượng đó . Đường biên của mặt phẳng alpha được xấp xỉ bằng một đa
giác , gọi là đa giác tham chiều (hình 3.1) . Đa giác này cần được xác định
sao cho càng sát với đường biên càng tốt . Chuyển động của đa giác tham
36
chiếu (tức chuyển động toàn cục của đối tượng) được mô tả bằng các vectơ
dịch chuyển tại các node ứng với các đỉnh của đa giác (corner node) , còn
chuyển động cục bộ bên trong đa giác tham chiếu (bên trong đối tượng)
được mô tả bằng các vectơ dịch chuyển tại các node nằm bên trong đa giác
(inner node) . Vectơ chuyển động tại các node được xác định bằng thuật toán
so khớp khối (block matching) kết hợp với các chiến lược tìm kiếm .
Hình 3.1 : Xấp xỉ đường biên của mặt phẳng alpha
Do mô hình đề ra chưa giải quyết vấn đề che phủ (occlusion) nên giả
thiết là trong suốt quá trình theo vết , kể từ frame bắt đầu (frame tham chiếu)
đến frame kết thúc , không có hiện tượng che phủ xảy ra .
37
Tiếp theo , trong phần 3.1 , luận văn sẽ trình bày chi tiết về việc tạo lưới .
Trong phần 3.2 , luận văn sẽ trình bày về phương pháp xác định vectơ dịch
chuyển của các node lưới . Cuối cùng trong phần 3.3 , luận văn sẽ trình bày
phần lan truyền lưới .
3.1 Tạo lưới
Lưới tam giác là lưới mà mỗi phần tử (mắt lưới) là một tam giác . Tạo
lưới tam giác cho một đối tượng nghĩa là áp một lưới tam giác lên mặt phẳng
alpha của đối tượng đó . Ta chỉ xét dạng lưới tuyến tính , là dạng lưới mà
các cạnh thuộc các mắt lưới đều là đường thẳng , không phải là đường cong .
Do đó , đường biên của đối tượng cần phải được xấp xỉ bằng một polyline
khép kín (đa giác) .
Theo [4] phép tạo lưới tam giác được coi là tối ưu nếu ứng với mỗi tam
giác thành viên của lưới vừa tạo , ba đỉnh của tam giác là ba đỉnh gần nhất
đối với các điểm thuộc miền tam giác đó (hình 3.2) . Có hai tiêu chuẩn
thường được sử dụng để tối ưu hóa phép tạo lưới tam giác đó :
1. Tiêu chuẩn Max-Min : tam giác thành viên được tạo sao cho
cực đại hóa góc nhỏ nhất (hình 3.3)
2. Tiêu chuẩn Vòng tròn : tam giác thành viên được tạo sao cho
vòng tròn ngoại tiếp của nó không chứa đỉnh thuộc tam giác
khác (hình 3.4) .
38
Hình 3.2 : Phép tạo lưới tam giác tối ưu và không tối ưu
Hình 3.3 : Tiêu chuẩn Max-Min
39
Hình 3.4 : Tiêu chuẩn Vòng tròn
Trong mô hình đề ra , luận văn sử dụng lưới tam giác tối ưu và được thiết
kế dựa theo nội dung của đối tượng . Theo [6] , nguyên tắc cơ bản trong việc
thiết kế lưới dựa theo nội dung là đặt các node của lưới lên các cạnh có
cường độ lớn và định vị sao cho giá trị của hàm DFD (Displaced Frame
Difference) tại các mắt lưới là xấp xỉ nhau . Hàm DFD tính tại vị trí (x ,y)
được cho bởi công thức :
DFD(x ,y) = ( IC(x ,y) – IR(x ,y) )P
trong đó , IC(x ,y) và IR(x ,y) là cường độ điểm ảnh tại vị trí (x ,y) trên hai
frame được xét , thường là frame k và frame k-1 hay frame hiện hành và
frame tham chiếu ; còn p là một số nguyên dương , thông thường p=2 .
40
Thuật toán tạo lưới tổng quát bao gồm những bước sau :
o Bước 0 : Khởi tạo tập node = ∅ , chọn các đỉnh của đa giác tham
chiếu đưa vào tập node . Đa giác tham chiếu chính là đường biên bao
ngoài của lưới .
o Bước 1 : Gán nhãn “unmarked” cho tất cả các pixel thuộc đối tượng
o Bước 2 : Tính giá trị DFD trung bình cho tất cả các pixel có nhãn
“unmarked”
( , ) & ( , )
( , ) p
x y AR x y unmarked
avg
DFD x y
DFD
K
∈=
∑
AR là kí hiệu mặt phẳng alpha của đối tượng , K là số lượng pixel có
nhãn “unmarked” , p=2
o Bước 3 : Với mỗi pixel được có nhãn “unmarked” , tính giá trị hàm
lượng giá :
2( , ) | ( , ) |C x y I x y= ∇
|∇I(x,y)| là độ lớn của vectơ gradient cường độ điểm ảnh tại pixel
(x,y)
41
o Bước 4 : Tìm pixel có nhãn “unmarked” và có giá trị C(x,y) cao nhất ,
chọn pixel đó làm node mới và đưa vào tập node của lưới .
o Bước 5 : Lấy node vừa chọn được làm tâm , thực hiện lan rộng vùng
ra các pixel “unmarked” xung quanh cho đến khi giá trị DFDavg của
vùng lớn hơn giá trị DFDavg tính ở bước 2 , đánh dấu “marked” cho tất
cả các pixel trong vùng vừa tạo được .
o Bước 6 : Nếu tất cả các pixel đều đã được đánh dấu “marked” thì
chuyển qua bước 7 , nếu không thì quay lại bước 2 .
o Bước 7 : Thực hiện phép tạo lưới tam giác Delauney trên tập node vừa
chọn được .
Vectơ gradient cường độ điểm ảnh (spatial intensity gradient)
Đạo hàm là một công cụ rất hữu hiệu để đo tốc độ thay đổi của sự vật .
Xét hàm số một biến y = f(x) , đạo hàm theo biến x được cho bởi công thức :
0 0
( ) ( )'( ) lim lim
x h
y f x h f xf x
x h∆ −> −>
∆ + −= =∆
Như đã đề cập trong chương 2 , ảnh tĩnh là một phân bố cường độ theo
không gian , ta có thể biểu diễn ảnh tĩnh như một hàm hai biến I(x, y) với x
ứng với hoành độ , y ứng với tung độ và I(x, y) cho biết cường độ điểm ảnh
tại điểm (x, y) . Đạo hàm của hàm I(x, y) theo biến x cho biết tốc độ thay đổi
42
của cường độ điểm ảnh theo hoành độ , tương tự , đạo hàm theo biến y cho
biết tốc độ thay đổi của cường độ điểm ảnh theo tung độ .
0
( , ) ( , )lim
h
f f x h y f x y
x h−>
∂ + −=∂
0
( , ) ( , )lim
h
f f x y h f x y
y h−>
∂ + −=∂
Khi đó , vectơ gradient cường độ điểm ảnh tại điểm ảnh (x, y) , kí hiệu
∇I(x, y) , được xác định bởi :
( , ) ( ( , ), ( , )) ( , )x y
f fI x y I x y I x y
x y
∂ ∂∇ = ∇ ∇ = ∂ ∂
Và độ lớn của vectơ gradient được xác định bởi :
2 2 2 2| ( , ) | | ( , ) | | ( , ) | ( ) ( )x y
f fI x y I x y I x y
x y
∂ ∂∇ = ∇ + ∇ = +∂ ∂
Đối với ảnh số , |∇Ix(x ,y)| và |∇Iy(x ,y)| được tính xấp xỉ như sau :
| ( , ) | ( , ) ( 1, )xI x y I x y I x y∇ = − −
hay
1| ( , ) | [ ( 1, ) ( 1, )]
2x
I x y I x y I x y∇ = + − −
43
| ( , ) | ( , ) ( , 1)yI x y I x y I x y∇ = − −
hay
1| ( , ) | [ ( , 1) ( , 1)]
2y
I x y I x y I x y∇ = + − −
Phép tạo lưới tam giác Delauney
Phép tạo lưới Delauney là phép tạo lưới tối ưu dựa theo tiêu chuẩn “Vòng
tròn” đã đề cập ở trên , nghĩa là tam giác thành viên được tạo sao cho vòng
tròn ngoại tiếp của nó không chứa đỉnh của tam giác khác .
Đã có nhiều thuật toán tạo lưới tam giác Delauney được đưa ra , tiêu biểu
như :
– Thuật toán Chèn tăng tiến (Incremental Insertion Algorithm) của tác
giả Lawson (Mathematical Software III–1977) và cải tiến của thuật
toán này do tác giả Watson đưa ra năm 1981 (Computer Journal 24) .
– Thuật toán Chia để trị (Divide and Conquer Algorithm) của các tác
giả D. T. Lee và B. J. Schachter (International Journal of Computer
and Information Sciences–1980) và cải tiến của thuật toán này do tác
giả Rex A. Dwyer đưa ra năm 1987 (Algorithmica 2) .
– Thuật toán Đảo dòng (Sweepline Algorithm) do tác giả Steven
Fortune đưa ra năm 1987 (Algorithmica 2) .
Theo [13] , thuật toán Chia để trị và Đảo dòng được đánh giá là tốt hơn
Chèn tăng tiến , rất tiếc là luận văn chưa tìm được những tài liệu mô tả rõ
ràng hai thuật toán này nên không thể trình bày ở đây .
44
Thuật toàn Chèn tăng tiến (Incremental Insertion Algorithm) của tác giả
Watson
Thuật toán được trình bày một cách trực quan như sau :
Cho một tập điểm ứng viên :
Bước 0 : bao tập điểm bằng một lưới tam giác Delauney hợp lệ
45
Bước 1 : lấy ra một đỉnh tùy ý từ tập ứng viên , chèn vào lưới
Bước 2 : Xóa những tam giác nào có vòng tròn ngoại tiếp chứa điểm
vừa chèn vào
46
Bước 3 : Tạo lưới tam giác mới từ các đỉnh của đường bao lồi của
điểm vừa chèn vào và bản thân điểm đó
Bước 1, 2, 3 được lặp cho đến khi không còn điểm nào để chèn vào lưới ,
cụ thể là :
47
Kết quả cuối cùng :
Các điểm Steiner
Trong thực tế , với một tập điểm input bất kì , không phải lúc nào các
thuật toán cũng có thể tạo được lưới tam giác tối ưu , ví dụ như tập điểm
input là các đỉnh của chữ A :
48
Giải pháp cho những trường hợp này là trên các cạnh của lưới ta thêm vào
các điểm mới , gọi là các điểm steiner , sao cho lưới tạo từ tập điểm mới
thỏa được các điều kiện của lưới tối ưu .
Việc thêm vào các điểm steiner còn giúp thiết lập được các ràng buộc về góc
tối thiểu , chẳng hạn như ràng buộc không có tam giác thành viên nào có góc
nhỏ hơn 30° . Có hai luật cơ bản trong quá trình thêm vào các điểm steiner :
– Luật đường tròn xuyên tâm (diametral circle) : ứng với mỗi cạnh của
lưới, dựng đường tròn nhận cạnh đó làm đường kính , nếu có đỉnh thứ ba
lọt vào đường tròn thì thực hiện việc thêm điểm steiner vào trung điểm
của cạnh đang xét .
– Luật đường tròn ngoại tiếp (circumcircle) : nếu một tam giác thành viên
có góc quá nhỏ , không thỏa ràng buộc về góc tối thiểu thì thực hiện việc
thêm điểm steiner vào vị trí tâm đường tròn ngoại tiếp của tam giác đó .
49
3.2 Ước lượng chuyển động tại các node của lưới
Ước lượng chuyển động tại các node của lưới tức là tìm ra vectơ dịch
chuyển của các node đó . Khái niệm về vectơ dịch chuyển đã được trình bày
trong chương 2 . Chuyển động toàn cục của đối tượng (tức chuyển động của
đường biên của lưới) được mô tả bằng các vectơ dịch chuyển tại các node
thuộc đường biên . Còn các chuyển động cục bộ bên trong đối tượng được
mô tả bằng các vectơ dịch chuyển tại các node nằm bên trong đường biên .
Để tìm ra các vectơ này , luận văn sử dụng phương pháp so sánh khối kết
hợp với các chiến lược tìm kiếm .
50
Vectơ dịch chuyển tại một điểm ảnh trên frame k được xác định khi ta
tìm ra vị trí tương ứng của điểm đó trong frame k+1 . Tuy nhiên , nếu chỉ
dựa vào giá trị cường độ của một điểm ảnh thì không đủ để có thể tìm được
chính xác vị trí của điểm ảnh đó trong frame mới . L ý do đơn giản là vì xung
quanh một điểm ảnh thường có nhiều điểm có cùng giá trị cường độ với
điểm ảnh đó . Vậy , nếu không thể chỉ dựa vào thông tin của bản thân điểm
ảnh thì ta có thể kết hợp thêm thông tin từ các điểm láng giềng . Đây chính
là tiền đề của phương pháp so khớp khối . Theo phương pháp này , để tìm ra
vị trí mới của điểm ảnh (x ,y) trên frame k+1 , ta sẽ xét một khối kích thước
N1×N2 có tâm là (x ,y) trên frame k và tìm khối tương ứng trên frame k+1 ,
khi đó vị trí mới của điểm ảnh (x ,y) trên frame k+1 sẽ là vị trí cho kết quả
so sánh khối tốt nhất . Việc tìm kiếm khối tương ứng được giới hạn trong
một vùng kích thước (N1+2M1)×(N2+2M2) , gọi là cửa sổ tìm kiếm (search
window) , nhằm tiết kiệm chi phí tính toán .
51
Ý tưởng trên được áp dụng cho các node để tìm ra vectơ dịch chuyển
tươnng ứng (hình)
Các thuật toán block-matching khác nhau ở những điểm sau :
– Tiêu chuẩn đánh giá việc so khớp
– Chiến lược tìm kiếm
– Cách xác định kích thước khối
3.2.1 Tiêu chuẩn đánh giá
Các tiêu chuẩn thường được sử dụng là Trung bình bình phương sai số
(Mean Square Error–MSE) , Trung bình trị tuyệt đối sai số (Mean Absolute
Error–MAD)
Mean Square Error (MSE)
2
1 2 1 1 2
,1 2
1( , ) [ ( , ) ( , )]k k
x y B
MSE d d I x y I x d y d
N N −∈
= − + +∑
52
trong đó B là khối N1×N2 , Ik(x ,y) là cường độ điểm ảnh tại vị trí (x ,y) trên
frame k , d
ur
=(d1 ,d2) là vectơ dịch chuyển ứng viên .
Mean Absolute Difference (MAD)
1 2 1 1 2
,1 2
1( , ) | ( , ) ( , ) |k k
x y B
MAE d d I x y I x d y d
N N −∈
= − + +∑
3.2.2 Các chiến lược tìm kiếm
Chiến lược ba bước (Three Step Search – TSS)
Chiến lược tìm kiếm này do Koga đề ra năm 1981 . Đây là một chiến
lược rất phổ biến bởi nó đơn giản và hiệu quả . Ý tưởng như sau :
– Bước 1 : Khởi tạo kích thước bước tìm kiếm (k) . Thực hiện việc so khớp
tại chín vị trí : một vị trí tại tâm và tám vị trí tại các lân cận cách tâm một
khoảng ứng với k . Di chuyển tâm đến vị trí có kết quả so khớp tốt nhất .
– Bước 2 : Giảm k đi một nửa , nếu k≤1 thì qua bước 3 . Thực hiện việc so
khớp tại tám vị trí xung quanh tâm tương ứng với k . Di chuyển tâm đến
vị trí có kết quả so khớp tốt nhất . Quay lại bước 2 .
– Bước 3 : Thực hiện việc so khớp tại tám vị trí xung quanh tâm tương ứng
với k . Di chuyển tâm đến vị trí có kết quả so khớp tốt nhất . Đó chính là
vị trí cần tìm .
53
Chiến lược tìm kiếm logarithm (Two Dimensional Logarithmic Search –
TDL)
Chiến lược này được Jain giới thiệu gần như cùng thời điểm với Three
Step Search . Nó được đánh giá là tốt hơn TSS , đặc biệt trong những trường
hợp có cửa sổ tìm kiếm lớn . Ý tưởng của chiến lược như sau :
– Bước 0 : Khởi tạo kích thước bước tìm kiếm (k) .
– Bước 1 : Thực hiện so khớp khối tại vị trí tâm và bốn vị trí : trên , dưới ,
trái , phải của tâm .
– Bước 2 : Nếu vị trí có kết quả so khớp tốt nhất là tại tâm thì giảm k đi
một nửa , nếu k≤1 thì qua bước 3 . Nếu vị trí tốt nhất không là tâm thì di
chuyển tâm đến vị trí mới . Quay trở lại bước 1 .
54
– Bước 3 : Thực hiện việc so khớp tại tâm và tám vị trí lân cận tương ứng
với k . Vị trí cho kết quả tốt nhất chính là vị trí cần tìm .
Chiến lược bốn bước (Four Step Search – FSS)
Chiến lược này do Lai-Man Po và Wing-Chung Ma đưa ra vào năm
1996. Ý tưởng của chiến lược như sau :
– Bước 1 : Bắt đầu với bước tìm kiếm k = 2 . Thực hiện việc so khớp tại
chín vị trí , một tại tâm và tám tại các vị trí lân cận cách tâm một khoảng
k . Nếu vị trí cho kết quả tốt nhất là vị trí tâm thì qua bước 4 , ngược lại
thì qua bước 2 .
– Bước 2 : Di chuyển tâm đến vị trí có kết quả so khớp tốt nhất , k vẫn giữ
nguyên , sau đó xét :
Nếu vị trí tốt nhất là ở góc thì ta xét tiếp năm điểm như trong hình
Nếu vị trí tốt nhất là tại vị trí giữa của cạnh ngang hay cạnh dọc thì
ta xét ba điểm tiếp như trong hình
55
Di chuyển tâm đến vị trí tốt nhất . Nếu đó là vị trí tâm thì qua bước 4 ,
ngược lại thì qua bước 3 .
– Bước 3 : Quay trở lại bước 2
– Bước 4 : k =1 , thực hiện so khớp tại chín vị trí , một tại tâm và tám tại
các vị trí lân cận cách tâm một khoảng k . Vị trí cho kết quả tốt nhất
chính là vị trí cần tìm .
56
3.2.3 Không gian tìm kiếm hợp lệ
Trong quá trình ước lượng chuyển động tại các node của lưới , nếu ta
không giới hạn cửa sổ tìm kiếm của các node trong một không gian tìm kiếm
hợp lệ thì tính toàn vẹn về kết cấu của lưới có thể bị vi phạm , ví dụ :
frame k frame k+1
Để có thể minh họa rõ ràng khái niệm không gian tìm kiếm hợp lệ , ta chia
các node của lưới thành ba loại : node góc (corner node) ứng với các đỉnh
của đa giác tham chiếu , node biên (boundary node) ứng với các điểm steiner
được thêm vào đường biên và node trong (inner node) ứng với các node nằm
trong đường biên .
Corner node
57
Đối với corner node , không gian tìm kiếm hợp lệ là miền được gạch
chéo trong hình
Boundary node
Đối với boundary node , không gian tìm kiếm hợp lệ là đoạn AB
Inner node
Đối với inner node , không gian tìm kiếm hợp lệ là miền đa giác được
gạch chéo
58
3.3 Lan truyền lưới
Dựa vào tập vectơ chuyển động tại các node đã tìm được ở bước trên , ta
thực hiện việc lan truyền lưới , tức là xác định vectơ chuyển động của tất cả
các điểm ảnh còn lại . Theo mô hình lưới hai chiều , mỗi phần tử của lưới
(tức là các mắt lưới) được giả thiết là vùng có chuyển động đồng nhất và
chuyển động này có thể được biểu diễn chính xác bằng một phép biến đổi
không gian (affine , bilinear , …) . Phép biến đổi này có thể được suy ra từ
vectơ chuyển động tại các đỉnh của mắt lưới đang xét . Đối với lưới tam giác
thì phép biến đổi không gian được chọn là phép biến đổi affine , bởi phép
biến đổi này có sáu hệ số tự do và với ba tương ứng điểm ảnh tại ba đỉnh
tam giác , ta có thể được suy ra các hệ số này .
Biểu diễn tổng quát của phép biến đổi affine có dạng :
1 2 3
4 5 6
'
'
a a ax x
a a ay y
= +
Từ ba đỉnh (x1 ,y1) , (x2 ,y2) , (x3 ,y3) tìm ra ba điểm ảnh tương ứng (x’1
,y’1) , (x’2 ,y’2) , (x’3 ,y’3) . Từ ba cặp tương ứng này , ta có thể tính ra các hệ
số tự do trong () bằng cách giải hệ phương trình tuyến tính :
59
' '
1 11 1
' '
2 11 1
' '
3 22 2
' '
4 22 2
' '
5 33 3
' '
6 33 3
1 0 0 0
0 0 0 1
1 0 0 0
0 0 0 1
1 0 0 0
0 0 0 1
a xx y
a yx y
a xx y
a yx y
a xx y
a yx y
=
Sau khi đã xác định xong các hệ số , tất cả các điểm trong tam giác sẽ
được dịch chuyển thông qua phép biến đổi affine vừa tìm được .
60
Chương 4
Cài đặt và thử nghiệm
Toàn bộ mô hình theo vết đối tượng sử dụng lưới hai chiều mà luận văn đề
ra bao gồm bốn nội dung chính :
1. Chọn frame tham chiếu và chọn đối tượng video được quan tâm
2. Tạo lưới tam giác cho đối tượng
3. Ước lượng chuyển động tại các node của lưới
4. Lan truyền lưới
Luận văn đã cài đặt hoàn chỉnh phần chọn frame tham chiếu và xác định mặt
phẳng alpha của đối tượng (nội dung thứ nhất) , cài đặt hoàn chỉnh phần tạo
lưới tối ưu với thiết kế dựa theo nội dung của đối tượng (nội dung thứ hai) .
Trong nội dung thứ ba , luận văn cài đặt xong phần ước lượng chuyển động
tại các corner node , bao gồm phương pháp so khớp khối và các chiến lược
tìm kiếm ; rất tiếc là đối với các inner node và boundary node , do chưa giải
quyết được việc giới hạn không gian tìm kiếm nên không thể thực hiện
61
chính xác được việc ước lượng chuyển động và phần cài đặt đành phải dừng
ở đây .
4.1 Chi tiết phần cài đặt
Công cụ
Chương trình demo được thực hiện trên môi trường Visual C++ 6.0 , các
thư viện sử dụng gồm bộ thư viện Dali của trường đại học Cornell dùng để
giải mã file MPEG và bộ thư viện BCGControlBarPro dùng để tạo giao diện
cho chương trình .
Nội dung chương trình
Chương trình bao gồm các phần chính sau :
1. Lớp MPEGDecoder : giải mã file MPEG
2. Lớp MPEGViewer : hiện thị file MPEG
3. Lớp MPEG : lớp bao ngoài của hai lớp trên
4. Lớp FrameBuffer và Frame : quản lý các bộ đệm dùng trong quá trình
giải mã và hiển thị file MPEG
5. Lớp VideoObject : lưu trữ và xử lý các nội dung liên quan đến đối
tượng video
6. Dll TriMesh : chứa các hàm tạo lưới
7. Lớp TrackingAlgorithm : thực hiện các bước trong quá trình theo vết
đối tượng
4.2 Kết quả thử nghiệm
Mô hình được thử nghiệm trên hai đoạn video số theo chuẩn MPEG-1 ,
được đặt tên là “book1” và “clock1” , mỗi đoạn gồm có 20 frame . Ứng với
62
mỗi đoạn , ba thuật toán so khớp khối ứng với ba chiến lược tìm kiếm
(Three Step Search , Logarithmic Search và Four Step Search) được chạy
thử nghiệm . Tất cả các tính toán đều được thực hiện trên thành phần độ
sáng (luminance – Y) . Do mô hình chưa cài đặt hoàn chỉnh nên hiệu ứng
quan sát được không phải là toàn bộ đối tượng mà chỉ có đường viền của đối
tượng được theo vết mà thôi .
4.2.1 “Book 1”
Mặt phẳng alpha Lưới tam giác
Frame tham chiếu
63
Logarithmic Search
Frame 2 Frame 10
Frame 20
64
Three Step Search
Frame 2 Frame 10
Frame 20
65
Four Step Search
Frame 2 Frame 10
Frame 20
66
4.2.2 “Clock 1”
Mặt phẳng alpha Lưới tam giác
Frame tham chiếu
Logarithmic Search
Frame 2 Frame 10
67
Frame 20
Three Step Search
Frame 2 Frame 10
68
Frame 20
Four Step Search
Frame 2 Frame 10
69
Frame 20
Các kết quả cho thấy , chiến lược Four Step Search đạt được kết quả tốt
nhất , kế đến là Three Step Search , cuối cùng là Logarithmic Search . Có thể
giải thích việc Logarithmic Search cho kết quả kém nhất là do chiến thuật
này xét ít điểm hơn , chỉ khởi đầu với 5 điểm : trên , dưới , trái , phải của
tâm và bản thân vị trí tâm . Trong khi các chiến thuật FSS và TSS đều khởi
đầu với 9 điểm kể cả tâm .
70
Chương 5
Tổng kết và hướng phát triển
Theo vết đối tượng là một đề tài mới thuộc lĩnh vực xử lý video . Với
nhiều ứng dụng hữu ích trong thực tế , đề tài đã và đang thu hút sự quan tâm
của cộng đồng nghiên cứu . Trong phạm vi của mình , luận văn đã trình bày
những nội dung cơ bản của vấn đề theo vết đối tượng , đồng thời đề ra một
mô hình theo vết sử dụng lưới tam giác hai chiều có thiết kế dựa theo nội
dung của đối tượng . Những kết quả cài đặt cụ thể đã phần nào thể hiện được
tính đúng đắn của mô hình .
Thực tế vẫn còn rất nhiều vấn đề cần phải giải quyết . Trước hết là hoàn
chỉnh phần cài đặt của mô hình . Tiếp đó là thực hiện tối ưu hóa từng bước
trong mô hình đề ra , nghiên cách tạo lưới tốt hơn , tìm ra những chiến lược
tìm kiếm mạnh mẽ hơn . Ở bước đầu của mô hình , người sử dụng vẫn phải
đảm nhận nhiều thao tác . Cần tìm ra cách làm giảm bớt trách nhiệm cho
người dùng . Hiện tại , tất cả các tính toán đều được thực hiện trên thành
phần độ sáng (luminance – Y) , những thử nghiệm trên các không gian màu
khác hứa hẹn những kết quả khả quan hơn . Một phần quan trọng nữa cần
phải thực hiện là giải quyết hiện tượng che phủ , điều này sẽ giúp cho mô
hình có thể ứng dụng vào thực tế .
71
Tài liệu tham khảo
[1] A.Murat Tekalp , Digital Video Processing , Prentice Hall , 1995
[2] Steven W. Smith , Digital Signal Processing , California Technical
Publishing , 1997
[3] Nhiều tác giả , Handbook of Image & Video Processing , Academic
Press , 2000
[4] Geogre Wolberg , Digital Image Warping , IEEE Computer Vision
Press , 1990
[5] Cademir Toklu , “Object-Based Digital Video Processing Using 2-D
Meshes” , 1998
[6] Yucel Altunbasak , A.Murat Tekalp , “Occlusion-Adaptive , Content-
Based Mesh Design and Forward Tracking” , 1996
[7] Hoàng Kiếm , Dương Anh Đức , Lê Đình Duy , Cơ Sở Đồ Họa Máy
Tính , Nhà xuất bản Giáo Dục , 2000
[8] Deepak Turaga , Mohamed Alkanhal , “Search Algorithms for Block-
Matching in Motion Estimation” , 1998
[9] Peter van Beek , A.Murat Tekalp , Ning Zhuang , Isil Celasun và
Minghui Xia , “Hierarchical 2D Mesh Representation , Tracking and
Compression for Object-Based Video” , IEEE Transactions On CSVT , 1998
[10] Bilge Gunsel , A.Murat Tekalp và Peter J. L. van Beek , “Content-
Based Access to Video Objects : Temporal Segmentation , Visual
Summarization , and Feature Extraction” , 1997
72
[11] Isil Celasun , Minghui Xia , Peter J. L. van Beek và A.Murat Tekalp ,
“Hierarchical 2D Mesh Design and Compression for Video” , 1999
[12] Jonathan Richard Shewchuk , Triangle , 1996
[13] Jonathan Richard Shewchuk , “Triangle: Engineering a 2D Quality
Mesh Generator and Delaunay Triangulator” , 1996
[14] David L. Marcum , “SIAM Short Course on Unstructured Mesh
Generation” , SIAM Conference on Geometric Design and Computing ,
4 November 2001 Sacramento , CA
[15] Hoàng Kiếm , Trần Hạnh Nhi , Dương Anh Đức , Nhập Môn Cấu Trúc
Dữ Liệu và Thuật Toán , ĐH Khoa Hoc Tự Nhiên , Khoa Công Nghệ Thông
Tin , 2000.
[16] Dave Marshall , “Introduce to Multimedia” , 2001
[17] Pekin Erhan Eren , “Object-Based Digital Video Analysis and
Manipulation For Multimedia Applications” , University of Rochester ,
NewYork , 2002
[18] Yucel Altunbasak and A.Murat Tekalp , “Closed-Form Connectivity-
Preserving Solutions for Motion Compensation Using 2-D Meshes” , IEEE
Transactions on Image Processing , Vol 6 , No.9 , September 1997
[19] Isil Celasun , A.Murat Tekalp , “Optimal 2D Hierarchical Content-
Based Mesh Design and Update for Object-Based Video” , 2000
[20] Ghassan Al-Regib , Yucel Altunbasak , Russell M. Mersereau ,
“Hierarchical Motion Estimation with Content-Based Meshes” , 2003
[21] Ghassan Al-Regib , Yucel Altunbasak , “2-D Motion Estimation with
Hierarchical Content-Based Meshes” , 1999
[22] Y. Nakaya và H. Harashima , “Motion compensation based on spatial
transformation” , IEEE Trans. Circuits and Syst. Video Tech., vol. 3 , pp.
339 - 357 , June 1994
Các file đính kèm theo tài liệu này:
- 19.pdf