Đề án tốt nghiệp

Tìm hiểu một số
phương pháp phát hiện
đối tượng đột nhập

 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 1
I CM N
Sau thi gian thc tp và nghiên cu ti trng HDL Hi Phòng em ã
hoàn thành vic tìm hiu  tài: Tìm hiu mt s phng pháp phát hin i
ng t nhp, trong thi gian làm  án tt nghip em ã nhn c s giúp
 ht sc nhit tình ca Th.s Ngô Trng Giang và cùng vi s n lc ca
n thân nên em ã hoàn thành  tài c giao.
Em xin chân thành cm n s giúp  ca các thy cô khoa công ngh
thông tin, thy giáo Th.s Ngô Trng Giang và toàn th các bn sinh viên
khoa Công ngh thông tin, trng i hc Dân lp Hi Phòng cùng vi gia
ình ã ng h giúp  và to mi u kin thun li cho em trong sut quá
trình hc tp và nghiên cu  hoàn thành tt  án tt nghip này.
i Phòng, tháng 07 nm 2007
Sinh viên
Nguyn Qunh Nga
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 2
C LC
I CM N 1
U 4
CHNG 1: NG QUAN V X LÝ VIDEO 5

2.2.4. Nhn xét 40
2.3. Phát hin i tng chuyn ng da vào kt cu 40
2.3.1. Gii thiu 40
2.3.2. Toán t mu nh phân cc b 41
2.3.3. Phng pháp phát hin i tng chuyn ng 42
2.4. Phát hin i tng chuyn ng da vào s bin thiên cc b ca
véct kt c u SP 45
2.4.1. Gii thiu 45
2.4.2. Biu din video vi vect kt cu SP 47
2.4.3. Phát hin i tng chuyn ng da trên bin thiên cc b 48
CHNG 3: TH NGHIM PHÁT HIN I TNG T NHP 50
3.1. Mô t bài toán 50
3.2. Môi trng test 50
3.3. t s giao d in 50
3.4. ánh giá 52
T LUN 54
TÀI LIU THAM KHO 55
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 4
U
Ngày nay, s phát trin ca công ngh thông tin ã xâm nhp vào
u ht các mt ca i sng xã hi vi nhng ng dng rng rãi h tr cho
con ngi trên nhiu lnh vc, trong ó có lnh vc an toàn an ninh, chng
xâm nhp.Vic m bo an ninh là mt vn  quan trng và cn thit
(Vd : Trong các nút giao thông quan trng, trong các siêu th, trong các ngân
hàng hay bo tàng là nhng ni mà vn  an ninh c t lên hàng u ).
Có nhiu phng pháp nhm m bo an ninh sao cho t c hiu qu
cao, trong ó có phng pháp áp dng các h thng camera  quan sát s
chuyn ng ca các i tng trong khu vc. Ngày nay vi s tin b vt
c ca khoa hc, ta có th xây dng mt h thng cnh báo tng phát

Scene 1
Shot 1
Frame 1 Frame 2
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 6
n video có th to cm giác chuyn ng, các khung hình phi
c quay vi tc  phù hp. Mt ngi ch có th nhn c 24 hình/giây,
u nh ln lt 24 hình hoc nhiu hn 24 hình c phát trong mt giây thì
t s không nhn ra c s ri rc gia nhng khung hình, mà ch thy
nhng cnh liên tc. Có nhiu h video và mi h có tc  quay khác nhau
nh : NTSC 30 hình/giây, PAL 24 hình/giây, SECAM 29.99 hình/giây.
Khung hình là n v c bn nht ca d liu video. Theo chun ca h
NTSC thì mt giây có 30 khung hình, vy mt phút có 1800 khung hình, mt
gi có 60x1800 = 108000 khung hình. Có th thy rng s lng khung hình
cho mt n video thng là rt ln, cn phi có mt n v cp cao hn cho
video s.
Shot (lia): là n v c s ca video. Mt lia là mt n v vt lý ca
dòng video, gm các chui mt hay nhiu khung hình liên tip, không th
chia nh hn, ng vi mt thao tác camera n.
Nhng khung hình này liên tip theo thi gian mô t mt hành ng liên
c, và c gii hn bi 2 chuyn cnh.
Hình 1.3: n c s
Biên shot Biên shot
Shot i Shot i+2Shot i+1
Chuyn cnh
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 7
t n video có th có nhiu n c s, mà cng có th ch là mt
n c s. Nhng n c si din cho toàn bn video, và truy xut
n chúng cng coi nh là truy xut n chính n video. T chc nhng

Ø Wipe: là hin tng cnh chy theo mt ng trên màn hình, trong
khi ó cnh mi xut hin phía sau ng ó.
Các hiu ng ó to nên s bin i cho các khung hình, to nên các
chuyn cnh. Ct cng to nên chuyn cnh t ngt; fade, chng m và wipe
o nên chuyn cnh dn dn.
Hình 1.5: t s loi Wipe c bn
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 9
1.3. Các thuc tính c trng ca video
1.3.1. Color
i mi mt nh u có mt biu  màu  biu din s phân b màu
trong nh, biu  màu không ph thuc vào vic quay nh, dch chuyn nh,
chiu nhìn nh mà ph thuc vào vào h màu và các phng pháp nh lng
c dùng.
Hình 1.6: Biu  màu ca 4 loi nh c bn (a) nh ti (b) nh sáng
(c)nh tng phn thp (d) nh tng phn cao
1.3.2. Texture
ây là mt c trng quan trng ca b mt, ni xy ra vic lp li mu
 bn. Có hai dng biu din Texture ph bin: biu din dng ma trn ng
thi và biu din Tamura.
- Ma trn ng thi mô t hng và khong cách gia các m nh, ta
có th trích chn c các thng kê có ý ngha. Ngc li, ngi ta thy rng
entropi và mô-men chênh lch nghch o li có kh nng phân bit tt nht.
(a) (b)
(c) (d)
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 10
- Biu din Tamura c thúc y nh các nghiên cu v tâm lí trong
vic thu nhn trc giác ca con ngi, nó bao gm các thuc tính o tính thô,
 tng phn, hng, tính trn, tính cân i và  thô ráp. Các c tính này

Các k thut phân n có thc chia thành 3 loi: phân n da vào
ngng, phân n da trên phát hin cnh, phân n bng phng pháp n
vùng. Phân n da vào ngng s bin i mt nh u vào f thành mt
nh nh phân u ra g da trên mt ngng T cho trc nh sau:
( )



<
≥
=
Tjiffor
Tjiffor
jig
),(0
,1
),(
(1.1)
i i và j là các ta  X và Y, g(i,j) =1 ch ra rng m nh (i,j) thuc
i tng và ngc li g(i,j)= 0 ch ra rng m nh thuc v nn. T là giá
tr ngng trong không gian c trng. Vi mt s ngng cho trc ta có th
chia mt nh thành các i tng.
Hoc mt phng pháp phân n khác cng da vào ngng là: rút
trích các c trng ca mi khung hình trong n video, ri tính toán s
khác bit gia c trng ca các khung hình liên tip, sau ó so sánh nhng
khác bit này vi mt ngng cho trc. Mi khi s khác bit vt quá
ngng thì có ngha là tìm thy c mt n c s. T vn  s dng c
n c s 1 n c s 2 n c s 3
Biên n c s Biên n c s
Chuyn cnh

1.5.  thut trnh
Hiu theo ngha hp, tr hai nh có cùng kích thc là vic xây dng nh
i t s khác bit ca hai nh. Theo ngha rng hn, trnh là vic tính
toán  chênh lch gia hai nh trên mt c trng nh nào ó nh cng ,
màu sc, texture (kt cu), shape (hình dáng), chuyn ng…
Có nhiu k thut trnh khác nhau, nhng có th chia thành 3 loi:
- a vào m nh: So sánh các cp m nh tng ng trên hai nh.
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 14
- a vào khi: Chia nh thành các min và so sánh các min tng
ng.
- a vào biu : So sánh s phân b ca thuc tính nào ó ca nh.
t hp các loi này vi các thuc tính so sánh ca nh, ta s có nhiu
 thut trnh khác nhau.
1.5.1. a vào so sánh m nh
ây là phng pháp  tính toán s sai khác gia hai frame bng vic
tính toán các giá tr, nó mô t mi thay i v cng m nh trong các
nh. Có nhiu phng pháp  tính s sai khác này, Nagasaka và Tanaka ã
a ra mt phng pháp tính tng toàn b nhng thay i khác nhau v
ng m nh gia hai khung hình nh là  chênh lch khung D(f
1,
f
2
).
∑∑
−
=
−
=
−

Nguyn Qunh Nga – CT701 Trang 15
(1.3)
( )
∑∑
−
=
−
=
×
=
1
0
1
0
21
,
1
),(
X
x
Y
y
yxDP
YX
ffD
(1.4)
u t l sm nh thay i D(f
1
, f
2




=
0
1
, yxDP
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 16
Trong ó i là frame ang xét, và
δ
là chiu dài trung bình ca thay i
 ca camera. Nu Fr(i) nh hn mt ngng cho trc thì mt chp sáng
c phát hin ti v trí frame th i và ngc li. Khi ó ngi ta u chnh
 sai khác giá trm nh bng cách chia nó cho cng  ca m nh
trên khung hình th hai.
∑∑
−
=
−
=
−
×
=
1
0
1
0
2
21

() ()
{}
∑
∈
−
BGRi
iii
yxfyxfw
,,
21
,,
(1.7)
1.5.2. a vào khi
Trái ngc vi hng tip cn s dng các c tính toàn cc ca c
khung hình, hng tip cn phân khi s dng các c tính cc b nhm tng
tính c lp vi các di chuyn ca camera và i tng. Mi khung hình c
chia thành b khi. Các khi trên khung hình f
1
 c so sánh vi khi
ng ng trên khung hình f
2
. V c bn,  chênh lch gia hai khung hình
c tính nh sau:
∑
−
=
b
k
k
kffDPCffD

µµσσ
λ














−
+
+
=
(1.9)
Trong ó
kk 21
,
µ
µ
là giá tr cng  trung bình ca khi th k, và
kk 21
,
σ

k
〉
λ
, ng Nu ngc li
( )



=
0
1
,,
21
kffDP
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 18
nh có th cha thông tin v không gian nhiu chng nào có th. Các ca
 c sc so sánh và tính  chênh lch mc xám hoc giá tr màu ca
các m nh. Khi giá tr chênh lch ln mt ngng nào ó thì xem nh
min ang xét ã thay i. Khi s min thay i ln hn mt ngng khác thì
 chuyn cnh do ngt ã xy ra. Thc nghim ã chng minh rng hng
tip cn này cho tc  nhanh hn phng pháp so sánh tng cp m, thm
chí c phng pháp biu  xét di ây.
Hình 1.13: Các ca s c s trong thut toán so sánh thc
1.5.3. a vào so sánh biu 
Phng pháp o s khác bit gia các frame di dng giá tr màu
không mnh do chuyn ng ca camera và i tng có th gây ra s khác
bit giá trm nh quá ln. Có th dùng biu  màu hoc biu  mc xám
 tính toán s sai khác gia hai khung hình vì s phân b màu gia các
frame liên tc không b nh hng nhiu bi chuyn ng ca camera và

là biu  mc xám ca nh th n, k là giá tr hp lí ca
c xám G.
Có th s dng thêm trng s nu có mt s màu (mc xám) c xem
xét quan trng hn vi mc tiêu so sánh.
∑
=
−=
G
k
kHkHkwffD
0
2121
)()()(),(
(1.12)
Trong ó w(k) là trng sng vi giá tr màu (mc xám ) k.
Swain và Ballard li s dng s giao nhau ca biu c so sánh:
Hình 1.14: So sánh hai biu 
Vùng biu  chung nhau, phn gch chéo trong hình 1, cho bit 
ng t v ni dung hai nh có thc nh ngha nh sau:
∑
=
−=
G
k
kHkHffS
0
212,1
))()(min()(
(1.13)
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp

=
−
−
−=−=
G
k
G
k
kHkH
kHkH
ffSffD
0
21
0
21
221
))()(max(
))()(min(
1),1(1),(
(1.15)
Phng pháp khác bit v biu  màu c s dng nhiu và thông
ng nht vì nó tính toán nhanh, n gin và hiu qu trong vic phát hin
chuyn cnh t ngt, chuyn cnh rõ ràng, hoc có s dch chuyn nh ca
i tng và s dch chuyn nh ca camera. Nhng vi chuyn cnh dn
n, các nh t t mi, an xen ln nhau, làm cho khác bit vc trng
gia các khung hình liên tip tng i nh, không  vt qua ngng
xác nh ã t ra, dn n khó phát hin c chuyn cnh. Nu nh ngng
xác nh thp quá thì s tìm ra nhiu n d tha, nu t ngng quá cao
thì không phát hin c chuyn cnh. Mt khác, trong trng hp camera
hay i tng chuyn ng nhanh cng to ra s khác bit tng i ln gia

.
Hình 1.15: Phát hin chuyn cnh dn dn bng phng pháp
so sánh cp
u  chênh lch gia các khung hình liên tip gim xung di
ngng T
l
mà so sánh tích ly cha vt T
h
thì b qua v trí F
s
và vic tìm
kim bt u vi mt bin i dn dn khác. Tuy nhiên, có nhiu bin i dn
n mà chêch lch gia các khung hình liên tip u nh hn ngng bé T
l
.
n  này có th gii quyt d dàng bng cách t giá tr chp nhn c
cho phép ch mt s lng nht nh các khung hình liên tip có chêch lch
thp trc khi loi trng hp bin i ang xét. Nh vy, phng pháp so
sánh cp có th phát hin chuyn cnh t ngt và chuyn cnh dn dn cùng
t lúc. Qua kt qu thc nghim cài t thut toán và so sánh các k thut
phân n khác nhau và thy rng so sánh cp là phng pháp n gin và
phân n rt tt.
 án tt nghip Tìm hiu mt s phng pháp phát hin i tng t nhp
Nguyn Qunh Nga – CT701 Trang 22
Nhc m ca phng pháp này là:
- Biu  ch mô t s phân b các giá tr m nh (màu hay mc
xám) ch không cha ng các thông tin nào v không gian. Nh vy hai nh
có cùng biu  màu nhng vn có th có ni dung khác nhau do không gian
phân b khác nhau
Hình 1.16: Các nh có cùng biu  màu nhng ni dung khác nhau

1
2121
),,(),(
(1.16)
Vi
∑
=
−=
G
j
kjHkjHffDP
0
2121
),(),().(
(1.17)
Trong ó H(j,k) là giá tr biu  ti mc xám j ng vi khi th k.
Hng tip cn khác trong k thut trnh da vào biu  cc bc
Swanberg a ra. S chênh lch DP(f
1
, f
2
, k) gia các khi c tính bng
cách so sánh biu  màu RGB s dng công thc sau:
{ }
∑∑
∈=
−
=
BGRc
G

 sai khác gia hai khung hình c tính bng t l các m nh có 
chênh lch ln hn d.
Y
X
countS
ffD
*
.
),(
21
=
(1.20)
Chúng ta có th s dng cách khác là dùng các i lng thng kê cho
ng min, nh biu  chng hn. Phng pháp này có khá nhiu sai sót
trong phát hin cnh phim.