NG

I H C KHOA H C T

NHIÊN

KHOA CÔNG NGH THÔNG TIN
B

MÔN CÔNG NGH TRI TH C

K
H
TN

TR

CAO CHÁNH NGUYÊN HI N – KH

NG TR

NG GIANG

C
N
TT

–

Đ


- 0012551
- 0012537

Đ

H

CAO CHÁNH NGUYÊN HI N
KH
NG TR
NG GIANG

K
H
TN

TR

K
H
O
A

C
N
TT

–

NGHIÊN C U PH

ng

i

K
H
TN

h c Khoa h c T nhiên TP. HCM ã t o i u ki n t t cho chúng em th c hi n
tài lu n v n t t nghi p này.

Chúng em xin chân thành cám n quý Th y Cô trong khoa ã t n tình gi ng
d y, trang b cho chúng em nh ng ki n th c quý báu trong nh ng n m h c v a
qua.

em trong su t th i gian th c hi n

ng d n, ch b o và óng góp ý ki n cho chúng

Đ

Ph m Tuy t Trinh ã t n tình h

ình Thúc và Cô Ph m

H

Chúng em xin chân thành cám n Th y Nguy n
tài.


H
O
A

b n

Sinh viên
Cao Chánh Nguyên Hi"n – Kh

ng Tr

Tháng 07/ 2004

Trang 1

Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399

ng Giang


M CL C
CH

NG 1. GI I THI U VÀ

NG C

1.2.


2.5.2
Phát hi n chuy"n c nh tr c ti p ................................................................ 24
2.5.3
Phát hi n chuy"n c nh chuy"n ti p d n .................................................... 28
CH

NG 3. PHÂN O N NH VIDEO. ................................................................31

K
H
O
A

3.1. Gi i thi'u......................................................................................................31
3.1.1
Các k% thu t phân o n nh ...................................................................... 32
3.1.2.
Phân o n và theo v t các vùng Video ..................................................... 34
3.2. Phân vùng và theo v!t b/ng t ng h+p ,c tr ng ........................................36
3.2.1.
Khái quát chung ........................................................................................ 36
3.2.2.
C&u trúc d li u theo không gian và th i gian .......................................... 38
3.2.3.
Gán các i"m m#c tiêu.............................................................................. 39
3.2.3.1. Phân b 'ng u các m#c tiêu............................................................ 39
3.2.3.2. Các i"m có l !ng Gradient nh nh&t .................................................. 39
3.2.4.
Quá trình n( volume ................................................................................. 41
3.2.4.1.


IT

K
H
TN

3.3. Xây d-ng th vi'n ,c tr ng.......................................................................56
3.3.1
Quan sát m t s k t qu phân o n .......................................................... 56
3.3.2.
Trích ch n c tr ng tr c quan................................................................. 58
3.3.3.
Tìm ki m n i dung Video theo không gian và th i gian .......................... 58
3.3.4.
Mô hình truy v&n....................................................................................... 59
NG VIDEO ........................60

Gi i thi'u......................................................................................................60

4.2.

Các mô t quan h'........................................................................................62

H

4.1.

–



5.2. Các khái ni'm: .............................................................................................73
5.2.1.
*nh d ng tính: ........................................................................................ 73
5.3.2.
*nh âm tính : ............................................................................................ 73
5.2.3.
C+a s$ con: ............................................................................................... 73
5.2.4.
c tr ng: ................................................................................................. 73
5.2.5.
*nh tích h!p: ............................................................................................. 74

5.3.

Gi i thu"t h3c phân l p:..............................................................................76

5.4.

Mô hình Phân t ng: .....................................................................................78

5.5.

Hu n luy'n b( phân t ng: ...........................................................................79

5.6.

K!t qu

4nh v4 m,t .....................................................................................82

Đ

H

Gi i thi'u và (ng c) th-c hi'n

K
H
TN

Ch )ng 1.

Ngày nay, v i s phát tri"n c a các k% thu t nén nh Video và truy n thông, ta hoàn toàn

C
N
TT

có th" g+i tr c tuy n m t l !ng l n nh Video s . R&t nhi u các nhà cung c&p n i dung
truy n thông ang phân ph i Video theo yêu c u qua m ng Internet. Ng
ang có các

i dùng t i nhà

ng truy n b ng thông r ng ho c k t n i DSL " xem các hình nh Video

ch&t l !ng cao. Trong khi l !ng d li u Video ang t ng lên nhanh chóng, các ng d#ng
a truy n thông v n còn b gi i h n trong nh ng kh n ng qu n lý n i dung. Do v y ngày

K

n
!c

c tr ng ( trên.

Trong k ch b n v a nêu, k% thu t trên c s( n i dung là m t thành ph n quan tr ng
cung c&p các cách tìm ki m d a vào tính t
ãh

ng t

c tr ng. G n ây, nhi u nghiên c u

ng t i l,nh v c này. M t s ví d# bao g'm QBIC, PhotoBook, VisualSeek, MARS

Trang 5

Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399


và VideoQ [79,85,99,81,21]. M#c tiêu là nh-m cung c&p kh n ng tìm ki m tr c quan
h n và t

ng hoá quá trình chú gi i nh Video theo l i truy n th ng.

Thêm vào ch m#c

c tr ng, m t lo i k% thu t khác nh m t i phân tích và khai phá


!c dùng trong so kh p tính t

ng t tr c quan

ng th c truy v&n ph$ bi n là truy v&n m u và truy v&n b-ng phác th o [21].

M t s nghiên c u ã t p trung vào tìm ki m nh t,nh. S phát tri"n ã lan t i các l,nh
v c nh trích ch n

c tr ng [20],

ot

ng t , ch m#c vector [29,31] và h c ng

ngh,a [74]. Các nghiên c u v tìm ki m Video trên c s(

c tr ng b gi i h n trong Phát

[69,122]. Khi mà các k% thu t tìm nh có th"

K
H
TN

hi n chuy"n c nh (scene cut), trích khoá frame, gom nhóm và duy t qua (browsing)
!c áp d#ng cho tìm ki m Video, các

tr ng duy nh&t c a d li u Video òi h i nh ng gi i pháp cho nhi u v&n
thách th c.

m c th&p, các th c th" ( m c cao nh c nh hay câu chuy n khó có
các

!c dùng " ch n b t

c tr ng (

!c n u ch d a vào

c tr ng ( m c th&p. Nh quan sát trong [117], " gom chính xác ho c phân lo i các

shot, nhi u mô hình ph c t p c n

!c xây d ng d a vào các bi"u di n trung gian ho c

Trang 8

Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399


tu1 thu c l,nh v c nh vùng nh và các

i t !ng, Trong các nghiên c u g n ây, vài mô

hình bi"u di n Video n$i b t nh MPEG-4 ho c MPEG-7 ã
Tóm l i, khi s phát tri"n

!c ch&p nh n.



Các v n

Nh

c n gi i quy!t

ã th o lu n ( trên, vi c t o ch m#c Video liên quan

n các x+ lý phân o n,

phân tích và tóm t t n i dung Video. Phân o n theo th i gian chia lu'ng Video dài thành

các

n v nh nh shot (thay vì dùng các frame riêng l0). Phân o n theo không gian rút

ra các

i t !ng ch a trong Video shot. Nh ng phân o n này làm ta có th" phân tích và

mô hình hoá n i dung Video, xây d ng các c&u trúc nhi u m c mà ng

i dùng có th" tìm

ki m và duy t qua m t cách hi u qu nh&t, nh trình bày trong hình 1.3.
Nhi u v&n
d a trên

thách th c t'n t i khi phân o n các


nh ngh,a m t s

C hai chu2n MPEG-4 và MPEG-7 không tiêu chu2n hoá các ph
công c# rút trích

i t !ng hay

c tr ng [66]. Khi Video

i t !ng và thông tin ch a trong nó ph i

!c bi"u di n d
!c rút trích tr

tr( thành nh ng chu2n qu c t , các công c# phân o n

i t !ng Video và

–

còn thi u.

Ngày nay, các thu t toán phân o n t$ng quát và linh ho t
ó cho th&y h th ng th giác con ng

C
N
TT


i d ng pixel

i t !ng. Trong khi MPEG-4 và MPEG-7 ang

Đ

b&t c mô hình n i dung nào trên c s(

ng pháp và

c khi xây d ng

H

thô nh ng

i dùng

i t !ng. Các nghiên c u g n ây trên MPEG-4

nén nh trên c s(

ng t i các

i. Nó thu c v tr c giác " ng

K
H
TN



m t s tri th c

nh ngh,a

ng t

tr ng d'i dào và m m d0o nh&t " mô t n i dung Video trong nhi u ng d#ng liên quan.

1.3.3

T5o ch6 m7c và tìm ki!m Video
Bi"u di n Video d a trên shot và

i t !ng cung c&p m t n n t ng linh ho t cho

m#c hi n t i ch y u d a vào các

H

vi c t o ch m#c và tìm ki m Video (video indexing and retrieval). Các k% thu t t o ch
c tr ng tr c quan t các khoá frame. Nh ng

ng vào

i t !ng. B-ng cách nh n d ng m i quan h gi a các

các shot khác nhau, ta c/ng có th"

i t !ng trong

[email protected] - 0972.162.399


th i gian th c. Các k% thu t máy h c,

c bi t là cây quy t

nh c/ng

c p. Chúng

!c

tôi c/ng trình bày các thu t toán phát hi n các c nh thay $i d n, và m t s tình hu ng
c bi t nh ch p sáng. Cu i cùng, m t s k t qu

!c trình bày.

Trong Ch )ng 3, chúng tôi trình bày m t h th ng tìm ki m Video dùng các vùng
!c t

ng theo v t. Tr

c h t chúng tôi gi i thi u m t h th ng t

phân o n và theo v t có k t h!p nhi u

c tr ng " có các k t qu theo v t chính xác và

áng tin c y. Sau ó, chúng tôi th o lu n c&u trúc c a th vi n

chuy"n

ng c a

ng c a camera), vi c phát hi n chính xác s chuy"n c nh quay không ph i d

dàng. H n n a, các k% thu t i n nh

!c dùng trong c nh nh tan bi n, m d n và co

l i, ã sinh ra các thay $i khó mà phát hi n
Các thu t toán c t c nh ã

!c.

!c nghiên c u t nh ng n m 90. Ph

b n là o s khác bi t i"m nh gi a các frame d
s l !ng các i"m nh khác nhau
nh&t

i t !ng, thay $i ánh sáng, và

nh m t c nh

camera và c a

!c

!c xu&t ra. Ph


–

0

n u H i ( j ) ≠ 0hayH i +1 ( j ) ≠ 0

Đ

j =1

!c cho

H

b(i công th c sau:
n

o

!c trình bày là t t h n khi thí

o khác. Trong χ 2 -test, kho ng cách gi a hai Histogram

nghi m so v i các

χ i2 =

K
H

ng viên

ng c a

n không th"

xu&t trong [121]. Ph

chuy"n d n. Ng

!c

C
N
TT

v&n

ng c a camera hay chuy"n

–

phân bi t gi a chuy"n

ng

ng l n h n

!c áp d#ng tr


ng ng !c l i và s


vector chuy"n

ng t i

!c tính. T l cao ch ra r-ng chuy"n c nh t i B-frame ho c P-

frame. Nói cách khác, t l th&p trên B-frame ch ra r-ng có m t c nh t i I-frame tr
ng này, chúng tôi s trình bày m t s

s t$ng h!p c a nhi u
th c hi n
• M ts

' phát hi n chuy"n c nh m i v i

c tr ng tr c quan trong c mi n nén và không nén. Công vi c

!c bao g'm các v&n

sau ây.

' hi u qu t$ng h!p chuy"n

ng và các

c tr ng màu trong c mi n nén



ng xung

!c dùng " rút ra các c nh

quay chính xác l i khó có th" tính ( th i gian th c. H n th n a, thay $i
èn ch p th

ng xu&t hi n nhi u trong các Video gia ình,

tv i

a

n m t v&n

K
H
O
A

th" gây ra k t qu phát hi n sai.

Trang 17

Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399

sáng, vd..,
khác có


chuy"n

H

n 0.4 giây cho các video chu2n MPEG.

V i m t P-frame,
ng Rp

ng ng v i m t kho ng th i

Đ

gian 0.2

ng

nh

K
H
TN

frame tr

!c tính t

ng xuyên trong các Video gia ình và trong



ng di n ra trong kho ng 0,02 giây. Do ó các Video th

n 30 frame m t giây, m t flashlight ch

nh h (ng nhi u nh&t là m t frame. M t ví d#

!c trình bày trong hình 2.3.

H

K
H
TN

v flashlight

ng v i 25

trong hình 2.4, giá tr

s tr( l i bình th

xám nh y lên m c cao khi flashlight xu&t hi n.

i u này

–

Nh


c, m t flashlight

K
H
O
A

camera. N u t l Fr(i) nh h n m t ng
frame i và ng !c l i.

Trang 21

Viết thuê luận văn thạc sĩ
[email protected] - 0972.162.399

!c phát hi n t i


K
H
TN
H
Đ

Phát hi'n chuy.n c nh
V i các

C
N

O
A

dùng m t c+a s c#c b
60 frame, và tâm

Gi s+ kích th

b(i giá tr trung bình t

o này. Khi chuy"n c nh trong

c i"m khác nhau, vi c

t m t ng

ng

nh là r&t khó. Ngay c trong cùng Video, các ph n
nh khác nhau.

" tìm ra các gá tr

t t i frame b t

!c

" gi i quy t v&n

nh. Kích th

ng ti p c n là th+ các cách t$ng h!p khác nhau, và sau ó so

" ch n ra cách t t nh&t. V i nhi u ng

ng liên quan trong các cách t$ng

h!p khác nhau, quá trình ch n l a này rõ ràng là c n nhi u th i gian. Chúng tôi xây d ng
các ng

ng

nh " tìm các mô hình quy t

!c x&p x .

nh úng nh&t và

K
H
TN

m t quá trình h c d a trên cây quy t

2.5.1 T ng h+p các ,c tr ng dùng cây quy!t 4nh
Cây qu y t

nh là m t k% thu t máy h c ph$ bi n và

m t cây mà các nút không ph i lá


c tr ng úng s

c tr ng là chìa khoá cho vi c

n gi n, b t&t c các
a

o l i v i nhau

n các gi i pháp không hi u qu .

D a trên các tính ch&t c a d li u nén, ta ch n cây quy t

nh cho I, P và B-frame m t

cách riêng bi t. i u này là do các lo i frame khác nhau có các tính ch&t khác nhau c/ng
c tr ng. Chúng tôi mong r-ng các lu t quy t

K
H
O
A

nh các

nh khác nhau cho các lo i frame

khác nhau. H n n a, các c nh tr c ti p và chuy"n ti p d n c/ng

!c