Luận văn tốt nghiệp cao học

MỤC LỤC

MỤC LỤC ..................................................................................................................1
LỜI CAM ĐOAN ......................................................................................................4
DANH MỤC CHỮ VIẾT TẮT ................................................................................5
DANH MỤC HÌNH VẼ ............................................................................................6
MỞ ĐẦU ....................................................................................................................7
Chƣơng I: TỔNG QUAN VỀ XỬ LÝ VIDEO VÀ PHÁT HIỆN ĐỐI TƢỢNG
CHUYỂN ĐỘNG ......................................................................................................9
1.1.

Khái niệm về video ................................................................................9

1.2.

Khái niệm về video tƣơng tự ................................................................9

1.2.1.

Tín hiệu video tƣơng tự.....................................................................9

1.2.2.

Các chuẩn video tƣơng tự ...............................................................11

1.2.3.

Các thiết bị video tƣơng tự .............................................................11

1.3.

Khái niệm về video số .........................................................................11

1.3.1.

Tín hiệu video số ..............................................................................11

1.3.2.

Các chuẩn video số ..........................................................................12

1.3.3.

Ƣu điểm của video số ......................................................................14

1.3.4.

Nhƣợc điểm của video số ................................................................14

1.3.5.

Các phƣơng pháp xử lý trên video số ............................................14

1.3.5.1. Phát hiện chuyển động ..................................................................15
1.3.5.2. Ước lượng chuyển động ................................................................20
Chƣơng II: PHÁT HIỆN, ĐÁNH DẤU VÀ PHÂN LOẠI ĐỐI TƢỢNG
CHUYỂN ĐỘNG TRONG VIDEO .......................................................................25
2.1. Phát hiện đối tƣợng ...................................................................................25
2.1.1. Phát hiện nổi trội .................................................................................26

2.1.1.1. Mô hình trừ nền có khả năng thích ứng ......................................26
2.1.1.2. Mô hình hỗn hợp Gaussian tương thích ......................................26
2.1.1.3. Sự khác biệt theo thời gian ...........................................................28
2.1.2. Bƣớc hậu xử lý điểm ảnh ....................................................................28
1


Luận văn tốt nghiệp cao học

2.1.3. Phát hiện các vùng liên tục .................................................................29
2.1.4. Bƣớc hậu xử lý vùng ...........................................................................29
2.1.5. Trích rút các đặc trƣng của đối tƣợng ..............................................30
2.2. Đánh dấu đối tƣợng ...................................................................................30
2.2.1. Tham chiếu tƣơng tự với các đối tƣợng cơ bản ...............................32
2.2.2. Điều khiển sự chồng chéo của các đối tƣợng ....................................33
2.2.2.1. Các đối tượng bị che khuất ...........................................................33
2.2.2.2. Phát hiện các đối tượng tách ra ....................................................34
2.2.2.3. Lược đồ cơ sở tham chiếu tương ứng...........................................34
2.2.3. Phát hiện các đối tƣợng dời đi và các đối tƣợng biến mất ..............34
2.3. Phân loại đối tƣợng ...................................................................................35
2.3.1. Phân loại dựa trên mẫu hình chiếu ...................................................35
2.3.2. Cơ sở dữ liệu mẫu hình chiếu ............................................................35
2.3.3. Ma trận phân loại................................................................................36
2.4. Thuật toán phát hiện và theo dõi đối tƣợng............................................37
2.4.1. Thuật toán phát hiện chuyển động dựa trên kỹ thuật trừ nền .......38
2.4.2. Thuật toán theo dõi đối tƣợng ...........................................................39
Chƣơng III: KẾT QUẢ ĐẠT ĐƢỢC TRONG QUÁ TRÌNH THỰC HIỆN ....41
3.1. Sơ đồ thực hiện ..........................................................................................41
3.2. Phần cứng đƣợc sử dụng ..........................................................................41
3.2.1. Động cơ Servo ......................................................................................41

3.2.1.1. Hoạt động của động cơ servo ........................................................42
3.2.1.2. Vai trò của Vôn kế .........................................................................42
3.2.1.3. Các giới hạn quay ..........................................................................43
3.2.2. Mạch Arduino UNO ...........................................................................43
3.2.2.1. Vi điều khiển ..................................................................................45
3.2.2.2. Năng lượng ....................................................................................45
3.2.2.3. Các chân năng lượng ....................................................................45
3.2.2.4. Bộ nhớ ............................................................................................45

2


Luận văn tốt nghiệp cao học

3.2.2.5. Các cổng vào/ra .............................................................................46
3.3. Các phần mềm đƣợc sử dụng ...................................................................47
3.3.1. Phần mềm Visual Studio 2010 Ultimate ...........................................48
3.3.2. Thƣ viện mã nguồn mở OpenCV 2.4 ................................................48
3.4. Kết quả mô phỏng .....................................................................................50
KẾT LUẬN ..............................................................................................................54
XU HƢỚNG PHÁT TRIỂN TƢƠNG LAI ...........................................................55
TÀI LIỆU THAM KHẢO ......................................................................................56

3


Luận văn tốt nghiệp cao học

LỜI CAM ĐOAN
Lời đầu tiên tôi xin chân thành cảm ơn tới các thầy cô trong Viện Điện tử Viễn thông, trường Đại học Bách khoa Hà Nội đã cho tôi một môi trường học tập

và nghiên cứu. Tôi cũng xin gửi lời cảm ơn đến các thầy cô trong Viện Đào tạo Sau
đại học đã quan tâm giúp đỡ chúng tôi, tạo điều kiện cho các học viên có điều kiện
thuận lợi để học tập và nghiên cứu. Đặc biệt tôi xin gửi lời cảm ơn sâu sắc đến thầy
giáo TS. Phạm Văn Tiến đã tận tình chỉ bảo, hướng dẫn và sửa chữa cho nội dung
của luận văn này.
Tôi xin cam đoan rằng nội dung của luận văn này là hoàn toàn do tôi tìm hiểu,
nghiên cứu và viết ra. Tất cả đều được tôi thực hiện cẩn thận và có sự định hướng
của giáo viên hướng dẫn.
Tôi xin chịu trách nhiệm với những nội dung đã trình bày trong luận văn này.
Tác giả
Nguyễn Hoài Nam

4


Luận văn tốt nghiệp cao học

DANH MỤC CHỮ VIẾT TẮT
Từ viết tắt

Giải nghĩa tiếng Anh
Electrically Eraseble

EEPROM

Programmable Read Only
Memory

JPEG
LED

MPEG

NTSC

Joint Photographic Experts
Group

Giải nghĩa tiếng Việt
Bộ nhớ có khả năng lập trình
lại được
Nhóm các chuyên gia ảnh

Light Emmitting Diode

Điốt phát quang

Moving Picture Coding

Nhóm chuyên gia mã hóa phim

Experts Group

ảnh

National Television System

Hệ truyền hình sử dụng ở Bắc

Committee


Mỹ
Hệ truyền hình sử dụng ở Châu

PAL

Phase Alternating Line

PWM

Pulse Width Modulation

Điều chỉnh độ rộng xung

Sequential Color with

Hệ truyền hình sử dụng ở

Memory

Đông Âu

Serial Perippheral Interface

Giao tiếp ngoại vi nối tiếp

Static Random Access

Bộ nhớ truy xuất ngẫu nhiên

Memory


tĩnh

SECAM
SPI
SRAM

5

Âu


Luận văn tốt nghiệp cao học

DANH MỤC HÌNH VẼ
Hình 1.1. Quét liên tục. Các dòng quét bắt đầu từ A đến B, tiếp tục đến C và
cứ thế đến D rồi quay trở lại A [8]. ..................................................................10
Hình 1.2. Quét xen kẽ. Dòng quét bắt đầu từ A đến B, chuyển qua C và tiếp
tục cho đến khi tới D sẽ trở về E và tiếp tục quét đến F [8]. ............................10
Hình 1.3. Chuỗi ảnh [8]. ...................................................................................12
Hình 1.4. Các chuẩn về studio số [8] ...............................................................13
Hình 1.5. Các chuẩn về ảnh và video nén số [8] ..............................................14
Hình 1.6. Phép chiếu phối cảnh của một đoạn thẳng [4] .................................15
Hình 1.7. Kết quả của phương pháp so sánh sự khác biệt [4]. .........................17
Hình 1.8. Hai đối tượng trong phương pháp trừ nền [4] ..................................18
Hình 2.1. Sơ đồ khối hệ thống [11] ..................................................................25
Hình 2.2. Sơ đồ hệ thống đánh dấu đối tượng [1] ............................................31
Hình 2.3. Phương pháp tham chiếu đối tượng phù hợp cơ bản [1] ..................32
Hình 2.4. Sơ đồ thuật toán phát hiện chuyển động dựa trên kỹ thuật trừ nền
[10] ...................................................................................................................39

Hình 2.5. Lưu đồ thuật toán bám theo đối tượng [10] .....................................40
Hình 3.1. Sơ đồ khối mô hình thực nghiệm .....................................................41
Hình 3.2. Cấu tạo động cơ servo [14] ..............................................................42
Hình 3.3. Mạch điều khiển Arduino UNO [16] ...............................................44
Hình 3.4. Các cổng vào/ra trên mạch Arduino UNO [16] ...............................46
Hình 3.5. Bảng điều khiển cài đặt màu sắc cần quan sát .................................50
Hình 3.6. ảnh gốc của tín hiệu thu được, vật thể màu hồng cần quan sát được
đánh dấu trong vòng tròn màu đỏ. ....................................................................51
Hình 3.7. ảnh cần quan sát là điểm màu trắng. ................................................52

6


Luận văn tốt nghiệp cao học

MỞ ĐẦU
Hiện nay phần lớn lượng thông tin con người thu vào là dưới dạng hình ảnh.
Thông tin dưới dạng hình ảnh là thông tin trực quan nên con người dễ dàng tiếp
nhận nó. Với sự ra đời của nhiều máy móc hiện đại như là máy ảnh số, máy quay
số, các máy thu hình, máy vi tính… thì lượng thông tin con người thu được càng
nhiều. Con người không chỉ muốn tiếp thu thông tin một cách thụ động mà còn
muốn biết cách xử lý nó, làm cho nó hữu ích hơn. Do đó con người đã tiến hành
nghiên cứu các phương pháp xử lý tín hiệu video để phục vụ cho các nhu cầu cần
thiết của mình. Việc nghiên cứu về ảnh số và video số đã phát triển rộng rãi. Các
trường đại học đều có một ngành riêng để nghiên cứu vấn đề này gọi là ngành thị
giác máy tính (computer vision).
Bên cạnh đó, hệ thống camera quan sát ngày càng được sử dụng một cách
rộng rãi với mục đích hỗ trợ an ninh cho các cửa hàng, công ty, … Từ yêu cầu thực
tế được đặt ra, việc xây dựng một hệ thống phát hiện và theo dõi chuyển động từ tín
hiệu video thu được thông qua hệ thống camera quan sát với sự hỗ trợ của kỹ thuật

theo vết trong lĩnh vực thị giác máy tính (computer vision) là một điều cần thiết. Do
đó, luận văn này phân tích tín hiệu video phát hiện và kiểm soát đối tượng chuyển
động.
Trên định hướng đó, luận văn được chia thành ba chương như sau:
Chƣơng 1: Tổng quan về xử lý video và phát hiện đối tƣợng chuyển động
Chương này sẽ trình bày các khái niệm về video, các chuẩn video tương tự và
video số, các khái niệm về chuyển động và ước lượng chuyển động.
Chƣơng 2: Phát hiện, đánh dấu, phân loại đối tƣợng chuyển động trong
video
Trong chương này sẽ trình bày các phương pháp phát hiện đối tượng, đánh
dấu đối tượng, phân loại các đối tượng chuyển động và thuật toán phát hiện đối
tượng chuyển động, thuật toán bám theo đối tượng.
Chƣơng 3: Kết quả đạt đƣợc trong quá trình thực hiện

7


Luận văn tốt nghiệp cao học

Chương này sẽ mô phỏng kết quả đạt được thông qua các cộng cụ hỗ trợ là
Visual Studio C++ 2010 Ultimate, OpenCV 2.4, và Arduino 1.0.6.Chương trình mô
phỏng sẽ cho thấy sự phát hiện đối tượng mới xuất hiện trong khu vực cần quan sát
và tự động bám theo sự di chuyển của đối tượng.
Do điều kiện về thời gian và kiến thức hiểu biết về lĩnh vực này còn hạn chế,
nên luận văn không thể tránh được những thiếu sót, rất mong được sự đóng góp ý
kiến của mọi người.
Tôi xin chân thành cảm ơn thầy giáo TS. Phạm Văn Tiến, đã tận tình giúp đỡ,
tạo điều kiện thuận lợi và hiệu chỉnh cho luận văn. Cám ơn các thầy giáo, cô giáo
Viện Điện tử - Viễn thông đã giúp đỡ tôi hoàn thành cuốn luận văn này.


8


Luận văn tốt nghiệp cao học

Chƣơng I: TỔNG QUAN VỀ XỬ LÝ VIDEO VÀ PHÁT HIỆN ĐỐI TƢỢNG
CHUYỂN ĐỘNG
1.1. Khái niệm về video
Video hay còn gọi là chuỗi ảnh (image sequence) tượng trưng cho thông tin
hình ảnh. Đó là một chuỗi các hình ảnh truyền liên tục theo thời gian [8].
S = f(x,y,t)
trong đó:

(1.1)
x,y € R: tọa độ của điểm ảnh (thông tin về không gian).
t € R: thông tin về thời gian.

Dựa trên công thức, ta có thể thấy ảnh tĩnh là một trường hợp đặc biệt của
video. Khi đó nó là một chuỗi các ảnh không thay đổi theo thời gian.
i,j € R … x,y € R

F(x,y,t1) = F(x,y,t2);

(1.2)

Video thường được thu, lưu trữ, chuyển đổi ở dạng tương tự (analog) nên
chúng ta sẽ bắt đầu từ video tương tự.
1.2. Khái niệm về video tƣơng tự
1.2.1. Tín hiệu video tương tự
Tín hiệu video tương tự được xem như là tín hiệu điện một chiều theo thời

gian f(t) và được lấy mẫu theo chiều dọc. Việc lấy mẫu theo chu kỳ này được gọi là
quét (scanning). Các phương pháp quét thường được sử dụng nhất là quét liên tục
(progressive scanning) và quét xen kẽ (interlace scanning) [8].
 Quét liên tục
A
C

B

D

9


Luận văn tốt nghiệp cao học

Hình 1.1. Quét liên tục. Các dòng quét bắt đầu từ A đến B, tiếp tục đến C và
cứ thế đến D rồi quay trở lại A [8].
- Mỗi ảnh hay còn được gọi là frame là dữ liệu được lấy mẫu theo thời gian.
- Mỗi ảnh này được quét liên tục từng dòng ngang và từ trên xuống dưới với
tốc độ là ∆t giây.
- Phương pháp này thường được dùng trong công nghiệp máy tính với tốc độ
∆t = 1/72 giây.
 Quét xen kẽ
E

A

B
C


F
D
Hình 1.2. Quét xen kẽ. Dòng quét bắt đầu từ A đến B, chuyển qua C và tiếp
tục cho đến khi tới D sẽ trở về E và tiếp tục quét đến F [8].
Vì mắt người phát hiện ra hình ảnh chớp khi tần số quét dưới 50Hz nên tần số
quét của máy bao giờ cũng phải lớn hơn 50Hz. Tuy nhiên khi áp dụng trong các
ngành công nghiệp khác như là ngành truyền thông thì gặp khó khăn về vấn đề băng
thông do kích thước quá lớn. Từ đó xuất hiện phương pháp quét xen kẽ. Phương
pháp này chia dòng quét thành dòng chẵn và dòng lẻ (gọi là field) và quét các dòng
chẵn trong khoảng thời gian ∆t rồi chuyển qua quét các dòng lẻ. Vì thế tần số quét
sẽ giảm đi một nửa [8].
Một số thông số quan trọng của tín hiệu video:

10


Luận văn tốt nghiệp cao học

- Độ phân giải theo chiều dọc (vertical resolution): thông số này liên quan
đến số dòng quét trên 1 frame.
- Tỉ lệ co (aspect ratio): tỉ lệ giữa chiều rộng và chiều ngang của frame.
1.2.2. Các chuẩn video tương tự
- Component Analog Video ( video tương tự hợp thành): chuẩn video này sử
dụng các thành phần mà RGB hoặc YCrCb (YIQ hoặc YUV).
- Composite Video (video tổng hợp):
+ NTSC (National Television Standards Committee): xuất hiện vào năm
1952, hiện tại được sử dụng ở Bắc Mỹ và Nhật Bản. Có 262.5 dòng trên 1
field hay là 525 dòng trên 1 frame, 60 field trên 1 giây và có tỉ lệ co là 4:3.
+ PAL (Phase Alternating Line) và SECAM (Sequential Color And

Memory): được phát triển vào những năm 1960 và ngày nay thường được
dùng ở Châu Âu. Ở Việt Nam cũng dùng chuẩn này. Các thông số kỹ thuật:
625 line trên 1 frame, 50 field trên 1 giây.
1.2.3. Các thiết bị video tương tự
Các thiết bị video tương tự có thể được chia làm 3 loại: loại dành cho truyền
thông, loại có chất lượng chuyên nghiệp, loại dành cho người tiêu dùng.
Video được quay bởi máy quay thông thường và được lưu trong băng hoặc
được quay bởi các máy quay dùng trong phim trường và tạo thành phim (24 hình/s).
Hầu hết tín hiệu video tương tự được lưu dựa trên kỹ thuật từ ngoại trừ đĩa
laser là dùng kỹ thuật quang.
1.3. Khái niệm về video số
1.3.1. Tín hiệu video số
Tín hiệu video số được lưu trữ dưới dạng số. Do đó, chúng được lấy mẫu và
lượng tử hóa. Tín hiệu video số là một thông tin 3 chiều gồm 2 chiều không gian và
1 chiều thời gian hay còn gọi là chuỗi ảnh số với mỗi ảnh số là một ảnh được lấy
mẫu và lượng tử hóa.

11


Luận văn tốt nghiệp cao học

chiều dọc

chiều thời gian

chiều ngang
Hình 1.3. Chuỗi ảnh [8].
1.3.2. Các chuẩn video số
Việc trao đổi giữa các ứng dụng và các sản phẩm video số đã đưa ra các chuẩn

video số. Các chuẩn này bao gồm:
- Chuẩn nén: dùng để trao đổi thông tin trong dạng nén của video.
- Chuẩn các độ phân giải hiển thị: dùng trong công nghiệp máy tính.
- Chuẩn studio số: được dùng trong ngành công nghiệp tivi.
- Chuẩn về giao tiếp mạng dùng trong công nghiệp truyền thông.

12


Luận văn tốt nghiệp cao học

ITU-R 601

ITU-R 601

CIF

525/60

625/50

NTSC

PAL/SECAM

Lum (Y)

720

720


360

Chroma (U, V)

360

360

180

Lum (Y)

480

576

288

Chroma (U, V)

480

576

144

Interlacing

2:1


2:1

1:1

Temporal rate

60

50

30

Aspect ration

4:3

4:3

4:3

165.9

165.9

37.3

Number of active pels/line

Number of active lines/pic


Raw data rate (Mbps)

Hình 1.4. Các chuẩn về studio số [8]

CCITT G3/G4

Binary images (non-adaptive)

JBIG

Binary images

JPEG

Still frame gray scale and color images

H.261

ISDN applications (px64 kbps)

H.263

PSTN applications (less than 64 kbps)

H.263+

Low-bitrate PSTN applications (underway)

MPEG-1


Optical storage media (1.5 Mbps)

MPEG-2

Generic coding (4-20 Mbps)

MPEG-4

Object-based functionalities (underway)

13


Luận văn tốt nghiệp cao học

Hình 1.5. Các chuẩn về ảnh và video nén số [8]
1.3.3. Ưu điểm của video số
So với video tương tự thì video số lại có nhiều ưu điểm quan trọng. Video
tương tự cung cấp cho chúng ta một số rất giới hạn các hoạt động tương tác như là:
chọn kênh, chỉnh tới lui hay là quay chậm trên băng video. Ngoài ra để hiển thị tín
hiệu theo chuẩn này (ví dụ NTSC) trên một hệ thống máy dùng chuẩn khác (ví dụ
PAL) ta cần có một bộ chuyển đổi tín hiệu đắt tiền. Với tín hiệu số ta không cần
phải chuyển đổi các tín hiệu này. Ngoài ra, ta còn có thể chỉnh sửa, tạo các hiệu ứng
đẹp trên tín hiệu video số. Video số không chỉ có vai trò giải trí mà nó còn cung cấp
cho chúng ta nhiều thông tin quan trọng trong nhiều lĩnh vực như là các ảnh giám
sát quân sự, điều khiển giao thông, và trích thông tin từ các dữ liệu ảnh và video [8].
1.3.4. Nhược điểm của video số
Nhược điểm của video số đó là nó đòi hỏi khối lượng lưu trữ lớn với băng
thông rộng để truyền tải. Với tín hiệu tivi chất lượng tối đa cần 1440 điểm ảnh trên

một dòng, 1050 dòng cho một frame độ sáng, 720 điểm trên một dòng và 525 dòng
trên một frame màu sắc. Bởi vì mỗi giây có 30 frame và 8 bit/pixel nên kết quả cuối
cùng xấp xỉ 545 Mps. Đây là một yêu cầu quá lớn. Do đó hiện nay người ta đang
nghiên cứu các phương pháp nén video để giảm kích thước khi truyền tải [8].
1.3.5. Các phương pháp xử lý trên video số
Video số có nhiều thông tin trực quan hơn là ảnh số. Lý do chính là do video
số có chứa thông tin về chuyển động trong khi ảnh số chỉ là ảnh chụp một cảnh tĩnh.
Các chuỗi ảnh động luôn hàm chứa các thông tin về chuyển động, các chuyển động
này là một tín hiệu nhạy cảm đối với thị giác con người. Con người có thể dễ dàng
nhận biết được các đối tượng ngay khi chúng chuyển động thậm chí chúng rất khó
thấy khi đứng yên. Vì thế các phương pháp xử lý video số cũng khác so với các
phương pháp xử lý ảnh số. Vận động là thông tin quan trọng trong xử lý video số
bởi vì vận động mang rất nhiều thông tin về mối quan hệ không gian và thời gian
giữa các đối tượng trong ảnh. Các phương pháp cơ bản trong xử lý video số là phát
hiện chuyển động và ước lượng chuyển động. Phát hiện chuyển động thường được

14


Luận văn tốt nghiệp cao học

áp dụng trong các hệ quan sát (phát hiện đối tượng di chuyển hoặc là đứng yên),
còn ước lượng chuyển động thường được áp dụng trong nén video số. Ngoài ra còn
có các phương pháp xử lý khác được áp dụng vào mức tiền xử lý như là lọc nhiễu…
các phương pháp này áp dụng trên từng frame giống như trong xử lý ảnh số [8].
1.3.5.1. Phát hiện chuyển động
a. Sơ nét về chuyển động
Chuyển động theo các khái niệm trong vật lý là sự thay đổi vị trí giữa vật này
và vật kia. Tức là khi xét tới sự chuyển động thì ta phải xét là nó chuyển động so
với cái gì. Khi xét tới chuyển động ta thường đặt nó vào một hệ quy chiếu quán

tính. Một vật thể đứng yên trên hệ quy chiếu này nhưng lại chuyển động khi xét nó
vơi hệ quy chiếu khác. Ví dụ khi ta đứng yên thì có thể coi là ta đứng yên so với hệ
quy chiếu gắn với trái đất, nhưng khi đưa vào hệ quy chiếu gắn với mặt trời thì ta lại
chuyển động. Điều này có ý nghĩa rất quan trọng khi ứng dụng vào camera tự động.
Chuyển động trong thực tế là chuyển động 3D nhưng khi con người tiếp nhận thì nó
trở thành chuyển động 2D. Do đó, phép toán chuyển đổi ảnh 3D thành ảnh 2D mà
mắt con người cảm nhận được là phép chiếu phối cảnh [4].
z
P1

P2

O

y

tâm chiếu
mặt phẳng chiếu
x

Hình 1.6. Phép chiếu phối cảnh của một đoạn thẳng [4]
Chuyển động trong thế giới thực 3D qua phép chiếu phối cảnh sẽ biến thành
chuyển động trong mặt phẳng 2D. Tuy nhiên, con người nhận biết chuyển động qua
sự thay đổi độ sáng của điểm ảnh. Do đó có những chuyển động mà con người

15


Luận văn tốt nghiệp cao học


không có cảm nhận được như là chuyển động của quả cầu đồng màu. Từ đó ta có
phương pháp phát hiện chuyển động đầu tiên đó là so sánh sự khác biệt theo thời
gian.
b. Phương pháp so sánh sự khác biệt
Chúng ta xác định độ sai khác Dk,

k-1

giữa frame thứ k và thứ (k-1) như sau

[4]:
Dk, k-1 = Fk – Fk-1

(1.3)

trong đó: Fk là frame tại thời điểm k
Nếu camera tĩnh, sự thay đổi ánh sáng rất nhỏ và nhiễu không đáng kể thì một
điểm được coi là chuyển động nếu độ khác biệt của nó lớn hơn 0 và ngược lại sẽ
đứng yên.
Tuy nhiên trong thực tế các điều kiện trên khó có thể xảy ra. Do đó để loại bỏ
các điểm mà chúng ta phát hiện sai do nhiễu gây ra, ta có thể dùng một ngưỡng T
thích hợp [4].
1

nếu |Dk, k-1(x,y)| > T

Mk, k-1(x,y) =

(1.4)
0


ngược lại

Với Mk, k+1 được gọi là mặt nạ chuyển động ở thời điểm k, nếu bằng 1 thì điểm
đó được coi là chuyển động và bằng 0 thì điểm đó được coi là đứng yên. T là
ngưỡng thích hợp có thể là một giá trị cụ thể được xác định trong quá trình thực
nghiệm hoặc dựa trên các thuật toán.

frame thứ k - 1

frame thứ k

mặt nạ chuyển động

16


Luận văn tốt nghiệp cao học

Hình 1.7. Kết quả của phương pháp so sánh sự khác biệt [4].
Ưu điểm của phương pháp này là đơn giản và dễ cài đặt do đó tốc độ sẽ nhanh.
Tuy nhiên, nhược điểm của phương pháp này là những vùng thật sự chuyển động
nhưng do đồng màu nên sẽ được hiểu là đứng yên và những vùng thật sự đứng yên
thì lại cho là chuyển động.
Để khắc phục nhược điểm trên, ta có một thuật toán so sánh khác biệt cải tiến
[4]:
- Bước 1: Tạo cấu trúc Pyjamid Gaussian trong đó mỗi frame được đặc trưng
bởi nhiều độ phân giải khác nhau. Bắt đầu xử lý ở mức phân giải thấp nhất.
- Bước 2: Với mỗi điểm ở phân giải hiện tại, tính toán độ khác biệt chuẩn
hóa:

FDNk,r(x,y) =

𝑥 ,𝑦 ∈𝑁 𝑓 𝑥,𝑦 ,𝑘 − 𝑓 𝑥,𝑦,𝑟 |∇𝑓 𝑥,𝑦,𝑟 |
2
𝑥 ,𝑦 ∈𝑁 |∇𝑓 𝑥,𝑦,𝑟 | +𝑐

(1.5)

trong đó:
N: là các điểm trong lân cận của x.
∇𝑓 𝑥, 𝑦, 𝑟 : là gradient của mật độ ảnh tại điểm (x,y)
𝑓 𝑥, 𝑦, 𝑘 : là frame ở thời điểm k
c: là hằng số
Nếu khác biệt chuẩn hóa này cao hơn độ khác biệt ở độ phân giải trước thì
thay thế độ khác biệt trước đó bằng độ khác biệt ở mức hiện tại. Nếu không thì vẫn
giữ nguyên giá trị trước đó.
- Bước 3: lặp lại bước 2 cho tất cả các độ phân giải.
- Bước 4: Lấy ngưỡng với sự khác biệt chuẩn hóa ở mức phân giải cao nhất.
c. Phương pháp trừ nền
Phương pháp trên cũng dựa trên sự so sánh 2 ảnh, nhưng không phải là 2 ảnh
liên tiếp trong chuỗi ảnh mà là giữa các ảnh trong chuỗi ảnh với một ảnh tham chiếu
gọi là ảnh nền. Ảnh nền là cảnh thu được khi không có đối tượng chuyển động nào
hết. Gọi B là ảnh nền thu được, ta có độ khác biệt giữa ảnh nền và ảnh thứ k trong
chuỗi ảnh [4].
Dk = F k – B

(1.6)
17



Luận văn tốt nghiệp cao học

Nếu ít nhiễu và không có sự thay đổi của ánh sáng thì điểm có tọa độ (x,y)
được xem là tĩnh nếu Dk(x,y) = 0 và ngược lại. Tuy nhiên trong thực tế luôn có
nhiễu vì vậy ta phải dùng ngưỡng để hạn chế nhiễu [4].
Mk(x,y) =

1
0

𝑛ế𝑢 𝐷𝑘 𝑥, 𝑦 > 𝑇
𝑛𝑔ượ𝑐 𝑙ạ𝑖

(1.7)

Với Mk là mặt nạ chuyển động, điểm (x,y) được xem là chuyển động khi
Mk(x,y) = 1 là đứng yên khi Mk(x,y) = 0.
Trong thực tế, ảnh luôn biến đổi do sự thay đổi độ sáng vì thế ta phải luôn cập
nhật nền lại. Gọi Bk là nền ở thời điểm k. Ta có nền ở thời điểm (k+1) được cập
nhật như sau [4]:
α * Bk(x,y) + (1 – α)Fk(x,y)

nếu Mk(x,y) = 0

Bk+1(x,y) =

(1.8)
Bk(x,y)

nếu Mk(x,y) = 1


với α là một hằng số được gọi là tỉ lệ học phản ánh mức độ cập nhật
nền nhanh hay chậm.

ảnh nền

hai đối tượng
được phát hiện

ảnh thứ k

mặt nạ chuyển động

Hình 1.8. Hai đối tượng trong phương pháp trừ nền [4]
Phương pháp trừ nền cho kết quả tốt hơn so với phương pháp so sánh sự khác
biệt khi xử lý các đối tượng đồng màu. Tuy nhiên, nó có một nhược điểm là khi ảnh
nền chứa một đối tượng đứng yên, sau đó đối tượng này chuyển động thì phương
pháp trên sẽ phát hiện ra 2 đối tượng chuyển động chứ không phải là 1. Để giải

18


Luận văn tốt nghiệp cao học

quyết vấn đề trên người ta phải sử dụng ảnh nền không có đối tượng chuyển động
nào trong đó hết hoặc có thể dựa vào các thuật toán tạo ảnh nền.
Ngoài ra còn có một hướng tiếp cận mới trong phương pháp trừ nền đó là dựa
trên mô hình xác suất thống kê. Ý tưởng chính ở đây là đưa ra một mô hình thống
kê cho nền. Thường có hai mô hình thống kê đó chính là đơn phương thức
(unimodal) và đa phương thức (multimodal). Trong mô hình đơn phương thức mỗi

điểm được mô hình với phân phối xác suất đơn thường là phân phối Gaussian η(x,
y, µk, Σk, trong đó µk là giá trị trung bình, Σk là ma trận liên hiệp phương sai của
phân phối ở frame t. Những điểm mà màu quan sát được đủ gần (hay còn gọi là
khớp) với phân phối nền thì được phân thành điểm nền hay là điểm đứng yên và
ngược lại là điểm chuyển động. Vì nền luôn luôn thay đổi nên ta phải cập nhật lại
mô hình nền như sau [4]:
µt+1 = (1 – α) * µt + α * dt

(1.9)

Σt+1 = (1 – α) * Σt + α * dt * dtT

(1.10)

với α là hằng số chỉ mức độ điều chỉnh mô hình nền nhanh hay chậm.
Đối với mô hình nền đa phương thức (multimodal), chúng ta cần đến nhiều
phân phối xác suất độc lập với nhau để mô hình mỗi điểm ảnh. Mỗi phân phối được
gán với một trọng số đặc trưng cho mức độ ưu tiên của chúng. Chỉ một vài phân
phối đầu tiên với trọng số lớn mới được dùng để mô hình cho nền. Một phân phối
mới của sự quan sát sẽ được cập nhật vào mô hình nền nếu như nó không khớp bất
cứ phân phối nào đặc trưng cho mô hình nền, ngược lại nó trọng số của các phân
phối sẽ được cập nhật lại như sau [4]:
(1 – β) wt+1,i + β

i=m

Wt+1,i =

(1.11)
(1 – β) wt+1,i


i≠m

với m là chỉ số phân phối khớp với phân phối mới của sự quan sát, β
được gọi là tỉ lệ học trọng số.
d. Phương pháp dựa trên Optical Flow

19


Luận văn tốt nghiệp cao học

Các chuyển động của đối tượng trong 3D được gây ra chuyển động 2D trong
mặt phẳng ảnh được gọi là Optical Flow. Optical Flow tương ứng với sự cảm nhận
chuyển động của mắt người [8].
Phương pháp Optical flow thực hiện bằng cách sử dụng các vector có hướng
của các đối tượng chuyển động theo thời gian để phát hiện các vùng chuyển động
trong một ảnh.
1.3.5.2. Ước lượng chuyển động
Thông tin về chuyển động rất quan trọng trong xử lý ảnh và nén video. Nén
ảnh là phương pháp nhằm giảm số bit cần thiết để đặc trưng video. Trong khi các kỹ
thuật xử lý video là các phương pháp biến đổi trên chuỗi ảnh như là nâng cao chất
lượng chuỗi ảnh. Việc phân lớp trên có ý nghĩa quan trọng trong việc đưa ra đích
của việc ước lượng chuyển động tức là liên quan đến việc chọn mô hình xử lý sao
cho phù hợp. Trong nén video thì các tham số chuyển động được ước lượng đều dẫn
đến một việc là đạt được tỉ lệ nén cao nhất. Do đó, các chuyển động được tính toán
không cần phải giống với các chuyển động thật của điểm ảnh miễn là ta đạt được
một tỉ lệ bit tối thiểu. Tuy nhiên, trong xử lý video thì các chuyển động thật của các
điểm ảnh lại là điều chúng ta quan tâm. Để phát triển một thuật toán ước lượng
chuyển động thì cần có 3 yếu tố chính: mô hình, tiêu chuẩn và chiến thuật tìm kiếm

[8].
a. Các mô hình chuyển động
Có 2 mô hình cần thiết trong ước lượng chuyển động: mô hình chuyển động
(là cách đặc trưng vận động trong một chuỗi ảnh) và mô hình quan sát (là mô hình
mà có sự liên quan của các tham số chuyển động với mật độ ảnh). Trong mô hình
chuyển động ta lại có mô hình chuyển động theo không gian và theo thời gian.
- Mô hình chuyển động theo không gian
Hầu hết các chuyển động đều là sự kết hợp của phép chiếu các chuyển động
của đối tượng trong cảnh 3D và chuyển động của camera. Trong khi chuyển động
của camera ảnh hưởng đến chuyển động của toàn bộ hay hầu hết các điểm ảnh thì
chuyển động của đối tượng chỉ ảnh hưởng tới các điểm tương ứng với hình chiếu

20


Luận văn tốt nghiệp cao học

của đối tượng. Nói chung chuyển động phụ thuộc rất nhiều yếu tố như là các phép
chiếu, mô hình của đối tượng 3D… Ta xét trường hợp đơn giản nhất của chuyển
động là chuyển động tịnh tiến của đối tượng 3D. Khi đó vector vận tốc tức thời của
điểm x trong mặt phẳng ảnh sẽ là [8]:
V(x) =

𝑏1
𝑏2

(1.12)

Trong đó các tham số b = (b1, b2)T = (v1, v2)T phụ thuộc vào góc quay của
camera và các tham số trong chuyển động tịnh tiến 3D. Mô hình tịnh tiến 2D này

ứng dụng rất nhiều trong thực tế đặc biệt là trong nén video vì nó đưa ra một xấp xỉ
gần đúng với hầu hết ảnh trong tự nhiên. Khi chuyển động của vật thể 3D có thêm
các chuyển động affine thì ta có mô hình chuyển động affine với 6 tham số [8].
V(x) =

𝑏1
𝑏2

+

𝑏3 𝑏4
𝑏5 𝑏6

x

(1.13)

Rõ ràng mô hình chuyển động tịnh tiến là trường hợp đặc biệt của mô hình
chuyển động affine. Hầu hết các mô hình chuyển động phức tạp đều đưa ra rất tốt
nhưng tùy vào từng ứng dụng. Không phải lúc nào chúng cũng cải thiện được sự
chính xác trong ước lượng chuyển động. Nói chung, số tham số càng nhiều thì việc
mô tả chuyển động càng chính xác hơn.
- Mô hình chuyển động theo thời gian
Quỹ đạo của một điểm ảnh riêng biệt được vẽ trong không gian (x, y, t) của
một chuỗi ảnh có thể được xem như là tùy ý bởi vì chúng phụ thuộc và vận động
của đối tượng. Trong trường hợp đơn giản nhất, quỹ đạo của chúng là tuyến tính.
Giả sử, chúng ta có vận tốc vt(x) giữa thời gian t = tk-1 và thời gian τ (τ> t) là một
hằng số, một quỹ đạo tuyến tính có thể được trình bày như sau [8]:
X(τ) = x(t) + vt(x)( τ – t) = x(t) + dt,τ(x)


(1.14)

Trong đó dt,τ(x) = vt(x)( τ – t) là một vector dịch chuyển được đo theo hướng
thời gian. Cho nên đối với chuyển động tuyến tính, nhiệm vụ của chúng ta là tìm 2
thành phần của vector vận tốc v hay vector dịch chuyển d của mỗi điểm x.
Một sự mở rộng trong tự nhiên của mô hình quỹ đạo tuyến tính là mô hình
đường cong bậc 2. Khi đó ta có thêm một đại lượng mới là gia tốc của một điểm
[8]:
21


Luận văn tốt nghiệp cao học

1

x(τ) = x(t) + vt(x)( τ – t) + at(x)(τ - t)2
2

(1.15)

Trong đó gia tốc at là đạo hàm của vận tốc vt. Các mô hình trên đòi hỏi 2 (đối
với tuyến tính) hoặc 4 (đối với bậc 2) tại mỗi điểm x. Để giảm gánh nặng tính toán,
mô hình tham số theo không gian có thể kết hợp với các mô hình trên.
- Vùng hỗ trợ
Tập điểm x mà trong đó các mô hình không gian và thời gian áp dụng được
gọi là vùng hỗ trợ. Sự lựa chọn của một mô hình và vùng hỗ trợ là một trong các
yếu tố quyết định đến tính chính xác của ước lượng các tham số chuyển động.
Thông thường khi cho một mô hình chuyển động, vùng hỗ trợ càng nhỏ thì việc xấp
xỉ càng tốt hơn, bởi vì với vùng hỗ trợ lớn thì chuyển động có thể phức tạp và do đó
ta phải có mô hình chuyển động phức tạp hơn. Thông thường vùng hỗ trợ (ℜ) có thể

thuộc 1 trong 4 loại sau [8]
+ ℜ là toàn bộ ảnh: Mô hình chuyển động được áp dụng cho toàn bộ ảnh.
Mô hình này thích hợp cho việc ước lượng chuyển động của camera.
+ ℜ là một điểm ảnh: Mô hình này áp dụng cho một điểm ảnh. Trong
trường hợp này ta thường sử dụng mô hình không gian tịnh tiến kết hợp
với mô hình tuyến tính hoặc bậc 2.
+ ℜ là một khối điểm hình chữ nhật: Các mô hình vận động sẽ được áp
dụng trên một khối điểm ảnh hình chữ nhật. Trong trường hợp đơn giản
nhất, các khối này không phủ lên nhau và hợp của chúng sẽ bao phủ toàn
bộ ảnh. Trong trường hợp này mô hình chuyển động không gian tịnh tiến
kết hợp với mô hình chuyển động thời gian tuyến tính được xem là mô
hình hiệu quả nhất và đã được áp dụng trong các chuẩn nén video như là
MPEG-1, MPEG-2…
+ ℜ là một vùng bất kì: Các mô hình vận động sẽ áp dụng trên các điểm
thuộc vào R. Ở đây vùng R sẽ tương ứng với các đối tượng. Kỹ thuật này
đã được áp dụng trong chuẩn nén MPEG-4.
- Mô hình quan sát

22


Luận văn tốt nghiệp cao học

Khi chuyển động được ước lượng (và được quan sát bằng mắt người) dựa trên
sự thay đổi cường độ sáng, màu hoặc cả hai, các mối quan hệ giả định giữa các
tham số chuyển động và mật độ ảnh đóng một vai trò rất quan trọng. Giả thuyết hợp
lý thường thấy là cường độ sáng vẫn không đổi theo quỹ đạo chuyển động (đối
tượng không thay đổi độ sáng khi di chuyển). Đối với các ảnh được lấy mẫu theo
thời gian điều này có ý nghĩa là [8]:
Ik(x(tk)) = Ik-1(x(tk-1))


(1.16)

Sử dụng công thức trong mô hình chuyển động theo thời gian với t = tk-1, 𝜏 = tk
và giả thuyết rằng chúng ta lấy mẫu ảnh theo không gian, ta có:
Ik(n) = Ik-1(n-d)

(1.17)

Tuy nhiên, chúng ta không thể sử dụng công thức trên để tìm d trong thực tế vì
nhiễu q. Công thức trên được viết lại như sau:
Ik(n) = Ik-1(n-d) + q(n)

(1.18)

Do đó d được tính bằng cách tối thiểu hàm lỗi giữa Ik(n) và Ik-1(n-d).
b. Tiêu chuẩn ước lượng
Có rất nhiều tiêu chuẩn ước lượng tùy thuộc vào yêu cầu của bài toán. Trong
nén ảnh thì lỗi dự đoán của bộ ước lượng là rất quan trọng. Còn trong phép nội suy
bù đắp chuyển động thì lỗi nội suy cực đại lại là mối quan tâm. Ngoài ra tùy thuộc
vào khả năng xử lý mà việc ước lượng chuyển động được thực hiện trên đó. Nói
chung các tiêu chuẩn ước lượng đều có mục đích chung là cực tiểu hóa hàm lỗi [8]:
εk(n) = Ik(n) – Ĩk(n)

∀ n thuộc A

(1.19)

trong đó Ĩk(n) = Ik-1(n – n(d)) được gọi là ước lượng bù đắp chuyển động của
Ik(n).

c. Chiến thuật tìm kiếm
Khi mô hình chuyển động đã được xác định và kết hợp với một tiêu chuẩn ước
lượng, bước cuối cùng là phát triển một chiến lược hiệu quả cả về tính phức tạp và
chất lượng lời giải để ước lượng các tham số chuyển động. Đối với một số ít các
tham số vận động yêu cầu yêu cầu không gian trạng thái nhỏ thì chiến lược thường
dùng nhất khi tối thiểu hàm lỗi là so khớp. Trong hướng này, các ước lượng bù đắp

23


Luận văn tốt nghiệp cao học

chuyển động Ik(n) = Ik-1(n - d(n)) cho các ứng viên chuyển động d được so sánh với
ảnh gốc Ik(n) trong vùng hỗ trợ của mô hình vận động. Ứng viên nào khớp nhất đối
với tiêu chuẩn đã đưa sẽ được chọn để ước lượng. Ngoài ra ta còn có nhiều phương
pháp ước lượng nữa mà chúng ta sẽ không nói tới: kỹ thuật dựa trên gradient, thuật
toán độ tin cậy cao nhất được chọn đầu tiên …[8]

24


Luận văn tốt nghiệp cao học

Chƣơng II: PHÁT HIỆN, ĐÁNH DẤU VÀ PHÂN LOẠI ĐỐI TƢỢNG
CHUYỂN ĐỘNG TRONG VIDEO
2.1. Phát hiện đối tƣợng
Tổng quan về phát hiện, phân loại, đánh dấu đối tượng chuyển động trong
video với thời gian thực được mô tả trong hình vẽ
Khởi tạo,
cập nhật


Thu nhận ảnh
ảnh hiện thời

Mô hình nền

ảnh nền

Cập nhật

Phát hiện nổi trội
Bản đồ nổi trội, ảnh hiện thời
Trích rút đặc trƣng
và đối tƣợng
Các đối tượng cùng với các đặc trưng
Cập nhật

Phân loại đối tƣợng

Đánh dấu đối tƣợng
Đường đi của
đối tượng

Kiểu của đối tượng

Xử lý đối tƣợng
Hình 2.1. Sơ đồ khối hệ thống [11]
Hệ thống này có thể phân biệt được các đối tượng thoáng qua hoặc đứng yên
từ các đối tượng nền tĩnh trong các cảnh động; phát hiện và phân biệt các đối tượng
di chuyển và biến mất; phân loại các đối tượng đã được phát hiện vào trong các

nhóm khác nhau, như người, nhóm người, xe cộ, …; đánh dấu các đối tượng và tạo
ra thông tin về đường đi ngay cả các trường hợp bị che khuất và phát hiện ánh sáng
trong hình ảnh của video [11].

25