BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA TOÁN - TIN HỌC
BỘ MÔN ỨNG DỤNG TIN HỌC

LUẬN VĂN TỐT NGHIỆP:

PHÁT HIỆN VÀ ĐỊNH VỊ
SỰ THAY ĐỔI CỦA ĐỐI TƯNG
TRONG DÃY ẢNH LIÊN TIẾP

GVHD : Th.S Phạm Thế Bảo
SVTH : Huỳnh Lê Tấn Tài - 9911178
Hồ Quang Thái
- 9911191

Thành phố Hồ Chí Minh
07 - 2003


Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

Trang 2

lời cảm ơn

Chúng em xin chân thành cảm ơn Ban giám hiệu, các thầy cô giảng
dạy trường Đại Học Khoa Học Tự Nhiên cùng các thầy cô trong khoa Toán
– Tin học đã tận tình hướng dẫn, truyền đạt kiến thức cho chúng em trong
những tháng năm ở giảng đường Đại Học.

1.2.3 Kỹ thuật Narrow Band ....................................................................................10
1.3 Phương pháp Fast Marching ................................................................................. 11
1.3.1 Phương trình Eikonal .......................................................................................11
1.3.2 Nghiệm xấp xỉ của phương trình Eikonal........................................................12
1.3.3 Thuật toán Fast Marching Level Set (FMLS) .................................................13
1.3.4 Chi tiết các bước trong thuật toán FMLS ........................................................15
1.4 Thuật toán Multi - Class Fast Marching .............................................................. 18
CHƯƠNG 2 PHÁT HIỆN SỰ THAY ĐỔI TRONG DÃY ẢNH LIÊN TIẾP ......... 20
2.1 Tóm tắt phương pháp sử dụng FM LS và SRG ................................................... 20
2.2 Phát hiện đối tượng chuyển động ......................................................................... 21
2.2.1 Thiết lập mô hình thống kê.............................................................................21
2.2.2 Gán nhãn khởi tạo ban đầu .............................................................................22
2.2.3 Lan truyền nhãn ..............................................................................................25
2.3 Đònh vò đối tượng .................................................................................................... 28
2.3.1 Khởi tạo ...........................................................................................................28
2.3.2 Tạo vùng chứa biên.........................................................................................29
2.3.3 Lọc biên đối tượng ..........................................................................................30
CHƯƠNG 3 KẾT QUẢ VÀ HƯỚNG PHÁT TRIỂN................................................ 34
3.1 Thực hiện ................................................................................................................. 34
3.2 Kết quả thực nghiệm.............................................................................................. 35
3.3 Hướng phát triển .................................................................................................... 35
TÀI LIỆU THAM KHẢO ............................................................................................ 36
PHỤ LỤC ...................................................................................................................... 38
Ước lượng tham số bằng phương pháp hợp lý cực đại .............................................. 38
Giải thuật phân lớp bằng phương pháp xác suất ...................................................... 40
Hệ màu CieLab............................................................................................................. 43
LỜI MỞ ĐẦU

Trong thời đại bùng nổ thông tin như hiện nay, máy tính ngày càng được sử
dụng rộng rãi trong các lónh vực nghiên cứu khoa học và trong đời sống hàng ngày.

Growing.
Cấu trúc đề tài được phân thành các chương như sau
-

Chương 1: Phương pháp Level Set và phương pháp Fast Marching

-

Chương 2: Phát hiện và đònh vò sự thay đổi của các đối tượng trong dãy
ảnh liên tiếp dựa trên thuật toán Fast Marching và Seeded Region
Growing.

-

Chương 3: Kết quả và hướng phát triển.

TP Hồ Chí Minh, tháng 7 năm 2003

GVHD: ThS Phạm Thế Bảo

SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái


Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

Trang 5

Nhóm thực hiện

GVHD: ThS Phạm Thế Bảo

trường hợp khác của bài toán với F > 0 là khi ta bơm một quả bóng, và quả bóng
đó sẽ lớn dần theo thời gian.

1
2

Fast Marching Methods: phương pháp lan truyền nhanh (tạm dòch)
Level Set Methods: phương pháp tiếp cận dựa trên đường mức (tạm dòch)

GVHD: ThS Phạm Thế Bảo

SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái


Trang 7

Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

t

Hình 1: Sự tiến triển của đường cong

Thoạt nhìn, ý tưởng đơn giản để giải quyết bài toán này là ta sẽ biểu diễn
đường cong thông qua một số điểm đònh vò. Khi đường cong chuyển động với vận
tốc F, thì những điểm đònh vò này cũng chuyển động cùng với vận tốc đó. Bằng
một số công thức vật lý, ta có thể dễ dàng xác đònh vò trí mới của những điểm này,
và từ đó xây dựng lại đường cong. Hiển nhiên, số điểm đònh vò được chọn càng
nhiều thì đường cong được xây dựng càng chính xác.
Tuy nhiên, phương pháp trên sẽ không thực hiện được khi các điểm đònh vò
này chuyển động ngang qua nhau, hay đường cong bò tách ra thành nhiều phần.


x

x
z = φ(x,y,t)
y
đường mức gốc

γ(t)

x

Hình 2: Sự tiến triển của đường tròn theo phương pháp Level Set

Từ công thức (2.1), ta đi tìm sự tương quan giữa φ(x, t) và φ(x, t = 0)
Đạo hàm công thức (2.1), và theo tính chất đạo hàm hàm hợp, ta có:

φt + ∇φ(x(t), t). x’(t) = 0

(1.2.1b)

Do F là vận tốc cùng chiều với vector pháp tuyến, nên x’(t).η = F, với η là vector
pháp tuyến η =

∇φ
.
∇φ

Vì vậy, phương trình (2.2) trở thành :


∇φ

∇φ
.
∇φ

3. Mô hình Level Set không thay đổi trong trường hợp nhiều chiều.
4. Dựa trên nghiệm mạnh của phương trình đạo hàm riêng Level Set để đảm
bảo tính duy nhất, và sự hợp lệ của nghiệm yếu.
5. Nghiệm xấp xỉ của phương trình Level Set có được nhờ mô hình tính toán
dựa trên luật bảo toàn hyperbolic.

Nghiệm xấp xỉ của phương trình Level Set
Như đã đề cập ở trên, ta cần một nghiệm xấp xỉ cho phương trình Level Set
để chuyển bài toán từ liên tục sang rời rạc, và một trong những nghiệm đơn giản
nhất là: [15]

(

φ ijn +1 = φ ijn − Δt max (Dij− xφ ,0 ) + min (Dij+ xφ ) max (Dij− y φ ,0 ) + min (Dij+ y φ ,0 )
2

2

2

)

2 1/ 2


alive
land mines
far away
Hình 4 Kỹ thuật đánh dấu điểm trong phương pháp Narrow Band

Kỹ thuật Narrow Band là tiền đề của một thuật toán hiệu quả hơn, đó là thuật lan
truyền nhanh (Fast Marching Level Set) sẽ được trình bày trong phần kế.

3

alive : biểu diễn những điểm đá thuộc về đường cong
land mines hay trial : biểu diễn những điểm sẽ được chọn gần nhất đề ghép vào đường cong
5
far away : biểu diễn những điểm chưa được xét để ghép vào đường cong, hay đường cong sẽ phải
cần một khoảng thời gian khá lớn mới đến được các điểm này.
4

GVHD: ThS Phạm Thế Bảo

SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái


Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

Trang 11

Phương pháp Fast Marching
Phương trình Eikonal
Bây giờ, chúng ta tiếp tục tìm hiểu phương pháp Fast Marching Level Set
[3], một lời giải hiệu quả cho bài toán đường cong chuyển động trong trường hợp

dx

Hình 5: quãng đường = vận tốc * thời gian

Còn trong trường hợp nhiều chiều, ∇T vuông góc với đường mức thời điểm T, và
phương trình (1.3.1b) trở thành

∇T F = 1

GVHD: ThS Phạm Thế Bảo

(1.3.1c)

SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái


Trang 12

Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

Phương trình (1.3.1c) là một dạng của phương trình Eikonal (1).

Hình 6: Biểu diễn mặt nón T

Một vài tính chất của phương pháp Fast Marching
-

Chuyển bài toán từ mô hình động sang mô hình tónh, đường cong được
cập nhật theo chiều tăng từ giá trò nhỏ nhất đến giá trò lớn nhất của T.


2

(

T ,0),− min( Dij+ x T ,0) + max max( Dij− y T ,0),− min( Dij+ y T ,0

F2

) ]= 1F
2

2

(1.3

.2)

(1)

⎛ ∂u
phương trình Eikonal: ∑ ⎜⎜
i =1 ⎝ ∂x i
n

GVHD: ThS Phạm Thế Bảo

2

⎞
⎟⎟ = 1

truyền về một chiều theo T, tăng dần từ giá trò thấp nhất đến giá trò cao nhất. Ý
tưởng chính ở đây là ta sẽ đánh dấu tất cả các điểm trong lưới tương tự phương
pháp Narrow Band. Ở mỗi bước, ta tìm một vò trí trong các lân cận của đường cong
tại bước đó, có giá trò thời điểm đường cong đi qua T(x,y) là nhỏ nhất để ghép vào
đường cong mới. Hay nói cách khác, ta sẽ chọn nơi mà đường cong đến sớm nhất
để tạo thành đường cong mới. Vì lý do này thuật toán Fast Marching còn có một
tên gọi khác là “Dijkstra like Marching” (tựa Dijkstra6).
Thuật toán Fast Marching được mô tả như sau:
1. Khởi tạo
(a) Đánh dấu nhãn alive và đặt thời gian tiếp cận Tij = 0 cho tất cả
các điểm thuộc về đối tượng, và đưa vào tập hợp A.
(b) Đánh dấu nhãn trial và đặt thời gian tiếp cận Tij = 1

Fij

cho tất

cả các điểm lân cận A, và đưa vào tập hợp Narrow Band.
(c) Đánh dấu nhãn far away và đặt thời gian tiếp cận Tij = ∞ cho
tất cả các điểm còn lại và đưa vào tập hợp Far Away.
2. Lan truyền
(a) Bắt đầu bước lặp: Đặt minTrial = (imin, jmin) là điểm trong
Narrow Band có thời gian tiếp cận nhỏ nhất, nếu không tồn tại
thì kết thúc thuật toán.
(b) Thêm điểm (imin, jmin) vào A, và xóa nó trong Narrow Band
(c) Kiểm tra 4 lân cận của minTrial: (imin – 1, jmin), (imin, jmin – 1),
(imin + 1, jmin), (imin , jmin + 1) thuộc tập hợp Far Away hay

6



Ta xét ví dụ minh họa để hiểu rõ thuật toán Fast Marching.
Giả sử đường cong ban đầu là đường tròn điểm màu đen trong hình a).
Bước khởi tạo, điểm này được gán nhãn alive, và các lân cận A,B,C và D
xung quanh nó được gán nhãn trial.
Bước lặp, ta chọn điểm mang nhãn trial có giá trò thời điểm tiếp cận T(x,y)
nhỏ nhất, giả sử ta chọn được điểm A. Cập nhật điểm A vào đường cong (đánh dấu
alive), cập nhật các lân cận của nó vào Narrow Band và tiếp tục bước lặp (hình c).
Giả sử điểm trial có giá trò T nhỏ nhất trong 5 điểm trial là D. Ta đánh dấu D nhãn
alive, đường cong bây giờ được mở rộng thành 3 điểm, và Narrow Band cũng tăng
kích thước lên thành 6 điểm (hình d)… Và bước lặp được tiếp tục khi không còn
điểm trial nào nữa.

GVHD: ThS Phạm Thế Bảo

SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái


Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

Trang 15

Đến đây ta sẽ nghó ngay đến câu hỏi : tại sao thuật toán trên hoạt động và
đem lại kết quả ? Và câu trả lời là: đường cong luôn luôn tiến ra tại vò trí nhỏ nhất
trong Narrow Band, những điểm khác trong Narrow Band và trong Far Away có
thời gian tiếp cận nhỏ hơn không gây ảnh hưởng gì đến điểm này. Bước cập nhật
thời gian tiếp cận cho các điểm lân cận sẽ tạo một thời gian mới luôn lớn hơn thời
gian tiếp cận của các điểm alive, bởi vì ta đã chọn thời gian cập nhật là nghiệm
lớn của phương trình Eikonal. Do đó ta có thể lan truyền đường cong rộng dần ra,
chọn điểm trial có thời gian tiếp cận nhỏ nhất và điều chỉnh lại lân cận của nó, cứ


Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

[max(max(D

−x
ij

)

(

T ,0 ,− min Dij+ x T ,0

))

2

(

(

)

(

+ max max Dij− y T ,0 ,− min Dij+ y T ,0

)) ] = f
2

(2) một trong các lân cận này là alive
(3) hai trong các lân cận này là alive
(4) tất cả các lân cận naỳ là alive.

(1) A, B, C, và D là trial, A nhỏ nhất

GVHD: ThS Phạm Thế Bảo

SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái


Trang 17

Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

Trong trường hợp này, tất cả các lân cận quanh tâm đều hoặc là
trial hoặc là far away. Khi A là giá trò nhỏ nhất, chúng ta chuyển giá trò đó
thành alive và tính lại giá trò tâm. Ta chứng minh
A ≤ Trecomputed-from-A ≤ A+f.
1. Trường hợp A+f ≤ min(B, D). ⇒ Trecomputed-from-A = (A+f) (thỏa)
2. Trường hợp A+f > min(B, D) = B. (không mất tính tổng quát, giả sử
B ≤ D. Phương trình trở thành :
(Trecomputed-from-A – A)2 + ( Trecomputed-from-A – B)2=f2

Δ = 2 f 2 − (TB − T A ) 2 > 0 do f > B − A
Chọn nghiệm lớn:

Trecoputed − from − A =

T A + TB + 2 f 2 − (TB − T A ) 2

Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

Trang 18

Vậy ta đã chứng minh xong, khi cập nhật một giá trò T mới thì nó sẽ
không nhỏ hơn tất cả các giá trò alive và điểm minTrial, điều này đảm bảo
sự lan truyền sẽ tăng dần theo chiều T(x,y), thời gian đường cong tiếp cận
đến điểm (x,y).

Thuật toán Multi - Class Fast Marching
Bây giờ ta xét đến một biến thể của thuật toán Fast Marching, thuật toán
Multi-Class Fast Marching [4, 5, 6, 10] được Sifakis và Tziritas đưa ra năm 2001,
nhằm thực hiện phương pháp lan truyền Fast Marching trên nhiều đường cong
cùng lúc. Ý tưởng cải tiến ở đây là mỗi điểm thay vì nếu được gán nhãn trial thì
nó mang theo một danh sách các đường cong mà nó tiếp cận đến, gọi là TrialList,
và thời gian tiếp cận bây giờ là thời gian tiếp cận của đường cong đến nó sớm
nhất.

Thuật toán được mô tả như sau:

Khởi tạo thời gian tiếp cận T(x, y)
Khởi tạo danh sách các nhãn Trial List (x, y, ci) ∈ {alive, trial, far away}

Trong khi (Narrow Band chưa rỗng) {
Chọn (imin, jmin) là điểm có giá trò Tmin trong Narrow Band
Đánh dấu nhãn (imin, jmin) là alive cho đường cong đến nó sớm nhất.
Thêm các lân cận của (imin, jmin) vào Narrow Band
Cập nhật thời gian tiếp cận cho các lân cận (imin, jmin)
}



GVHD: ThS Phạm Thế Bảo

SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái


Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

Trang 20

PHÁT HIỆN SỰ THAY ĐỔI CỦA đối TượNG TRONG DÃY ẢNH LIÊN TIẾP
“Phát hiện và đònh vò đối tượng thay đổi trong dãy ảnh liên tiếp” là một
trong những vấn đề chủ yếu trong phân tích chuyển động video, cũng như những
ứng dụng theo dõi đối tượng di chuyển, ước lượng chuyển động hỗ trợ các hệ
thống an ninh, quốc phòng. Vấn đề này cũng được sử dụng nhiều trong việc nén
video, nhất là theo chuẩn MPEG, hoặc trong các kỹ thuật “blue-screening”.
Trong trường hợp ảnh được chụp từ một camera tónh, thì cơ sở chung để
phát hiện chuyển động là phân tích sự thay đổi màu sắc giữa hai frame ảnh liên
tiếp và từ đó sẽ đưa ra kết luận về đối tượng đang thay đổi giữa hai frame ảnh
này. Phương pháp đơn giản nhất là kỹ thuật trừ ảnh (hay xor ảnh). Nếu sự khác
biệt giữa hai frame ảnh lớn hơn một ngưỡng nào đó thì ta sẽ báo động có sự thay
đổi giữa chúng. Phương pháp này đặc biệt tối ưu về tốc độ nhưng cho kết quả
không tốt trong trường hợp ảnh bò nhiễu và không xác đònh được đối tượng chuyển
động một cách chính xác. Các kỹ thuật phức tạp hơn là sử dụng bộ lọc Kalman, sử
dụng mô hình Markov ẩn cũng có được kết quả khả quan nhưng tốc độ không được
cao lắm.
Trường hợp ảnh được chụp từ một camera di chuyển, vấn đề sẽ trở nên khó
hơn. Ta cần phải xét đến vector chuyển động cũng như hệ số phóng to thu nhỏ của
máy ảnh.
Trong phần này chúng em xin trình bày một trong những phương pháp phát

pixel (x,y), với I(x,y,t) và I(x,y,t+1) lần lượt là cường độ xám của pixel (x,y) trong
frame tại hai thời điểm t và t+1.
Đặt D = {d(x,y), (x,y) ∈ [0, chiều dài ảnh] x [0, chiều rộng ảnh]}.
Mỗi pixel được đánh dấu bởi một trong hai nhãn: động (mobile) hoặc tónh
(static). Với Θ(x,y) là nhãn của pixel (x,y), theo quy ước thống kê ta viết:
H0 : Θ(x,y) = static
H1 : Θ(x,y) = mobile
Đặt pD|static(d|static) và pD|mobile(d|mobile) lần lượt là hàm mật độ xác suất
của độ chênh lệch cường độ xám dưới hai giả thuyết H0 và H1. Các hàm mật độ
xác suất này độc lập với vò trí của pixel, và luôn tuân theo luật phân phối Laplace
hoặc Gauss.

GVHD: ThS Phạm Thế Bảo

SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái


Trang 22

Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

Ta sử dụng hàm phân phối Laplace(1) với kỳ vọng bằng 0 để mô tả sự tương quan
thống kê của các pixel đối với hai giả thuyết trên. Để đơn giản ta sử dụng ký hiệu
0 và 1 cho nhãn tónh và động.
Do vậy, hàm mật độ xác suất của độ chênh lệch cường độ xám dưới hai giả
thiết H0, H1 :
λ − λ d ( x, y )
p ( d ( x, y ) | Θ( x, y ) = l ) = l e l
2



λ

2

e

− λ x −θ

với λ > 0, θ là tham số cho trước

Các đặc trưng số: Kỳ vọng EX = θ, Phương sai DX =

GVHD: ThS Phạm Thế Bảo

1

λ2

SVTH: Huỳnh Lê Tấn Tài, Hồ Quang Thái


Trang 23

Tiểu luận: Phát hiện và đònh vò sự thay đổi của đối tượng trong dãy ảnh liên tiếp

được chọn bằng 1E-7). Do sử dụng phân phối Laplace, nên ngưỡng chênh
lệch mức xám cho nhãn động có được chọn như sau:
T1 =



3

4

5

γw

0.4

1.6

3.5

7.0

⇒Tập mẫu các pixel tónh : Static =

6

7

12.0 20.0

6

ΥB

w

động và tĩnh tìm được ở phần trên. Đường biên của mỗi tập pixel sẽ được mở rộng
với một vận tốc riêng tùy thuộc mỗi loại nhãn và độ chênh lệch cường độ xám. Vận
tốc lan truyền đđược thiết lập dựa trên nguyên lý xác suất Bayes
Với vị trí s có nhãn l và độ chênh lệch cường độ xám d, vận tốc lan truyền sẽ
là:
vl(s) = Pr{l(s), d(s)}
Có thể viết lại như sau:

vl ( s ) =

p (d ( s ) | l ( s )) Pr{l(s)}
=
∑ p(d (s) | k (s)) Pr{k(s)}
k

1+ ∑
k ≠l

1
p (d ( s ) | k ( s )) Pr{k(s)}
p (d ( s ) | l ( s ) Pr{l(s)}

(2.2.3)
Vì thế tốc độ lan truyền dựa trên các tỉ lệ hợp lý (likelihood) và các xác suất
tiên nghiệm (priori). Tỉ lệ hợp lý có thể được đánh giá dựa vào tính chất dữ liệu,
còn xác suất tiên nghiệm có thể ước lượng trên toàn ảnh hoặc đđơn giản hơn cho tất
cả bằng nhau (P0 = P1 = ½).
Trong trường hợp quyết đònh lựa chọn giữa nhãn động và nhãn tĩnh theo
phân phối Laplace, tỉ lệ hợp lý là hàm exp của độ chênh lệch cường độ xám d(x,y).
Trong cách tổ chức theo pixel, xử lí các quyết đònh này rất phức tạp. Hơn nữa, vật