TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA CÔNG NGHỆ THÔNG TIN
======***======

I V N THẮNG

ỨNG DỤNG XỬ LÝ ẢNH TRONG
TH O

I Đ I TƯ NG CHU

N ĐỘNG

KHÓA LUẬN T T NGHIỆP ĐẠI HỌC
Chuyên ngành: Tin học

HÀ NỘI – 2014


TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA CÔNG NGHỆ THÔNG TIN
======***======

I V N THẮNG

ỨNG DỤNG XỬ LÝ ẢNH TRONG
TH O

I Đ I TƯ NG CHU

N ĐỘNG

Do thời gian thực hiện không nhiều nên khóa luận không tránh khỏi
những thiếu sót. Rất mong nhận đƣợc sự đóng góp của thầy cô giáo và các
bạn để khóa luận đƣợc hoàn thiện hơn.
Em xin chân thành cảm ơn!
Hà Nội, tháng 05 năm 2014
Sinh viên

BÙI VĂN THẮNG

i


ỜI CAM ĐOAN
Tên em là: BÙI VĂN THẮNG
Sinh viên lớp: K36 – CN Tin học, khoa công nghệ thông tin
Trƣờng Đại học Sƣ phạm Hà Nội 2.
Em xin cam đoan:
1. Đề tài: “Ứng dụng xử lý ảnh trong theo dõi đối tƣợng chuyển động”
là sự nghiên cứu của riêng em, dƣới sự hƣớng dẫn của cô ThS. Lƣu Thị Bích
Hƣơng.
2. Khóa luận hoàn toàn không sao chép của tác giả nào khác.
Nếu sai em xin hoàn toàn chịu trách nhiệm.
Hà Nội, tháng 05 năm 2014
Ngƣời cam đoan

BÙI VĂN THẮNG

ii



2.2.3 Shape ........................................................................................................ 24

iii


2.2.4 Chuyển động (Motion) ............................................................................. 24
2.3 Theo dõi đối tƣợng .......................................................................................... 24
2.3.1 Chính xác hoá đối tƣợng tƣơng ứng (Object matching) .......................... 25
2.3.2 Xử lý nhập nhằng – Occlusion ................................................................. 26
2.3.3 Dự đoán chuyển động .............................................................................. 27
2.4 Bài toán theo dõi đối tƣợng chuyển động ....................................................... 29
2.4.1 Bài toán .................................................................................................... 29
2.4.2 Giải quyết bài toán ................................................................................... 31
2.4.3.1 Khối chính xác hoá đối tƣợng tƣơng ứng ......................................... 33
2.4.3.2 Khối xử lý nhập nhằng giữa các đối tƣợng ....................................... 35
2.4.3.3 Khối dự đoán chuyển động của đối tƣợng ........................................ 36
CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM.......................................................... 42
3.1 Phát biểu bài toán ............................................................................................ 42
3.2 Xây dựng chƣơng trình và thực nghiệm ......................................................... 43
3.2.1 Xây dựng chƣơng trình ............................................................................ 43
3.2.2 Thiết kế chƣơng trình ............................................................................... 44
3.2.3 Thực nghiệm ............................................................................................ 45
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ....................................................................... 50
TÀI LIỆU THAM KHẢO ................................................................................................. 52

iv


DANH MỤC HÌNH VẼ
Hình 1.1: Quá trình xử lý ảnh .....................................................................................4


MỞ ĐẦU
1. Lý do chọn đề tài
Ngày nay, thuật ngữ hệ thống giám sát bằng camera đã ngày càng trở
nên phổ biến và dần trở thành quen thuộc với chúng ta, những ngƣời đang
sống trong thời đại mới, thời đại của nền kinh tế tri thức, trong đó những
thành tựu rực rỡ của công nghệ thông tin đóng vai trò chủ đạo.
Ra đời từ những năm 1960 qua quá trình hoàn thiện và phát triển, ngày
nay một hệ thống giám sát tự động là một trong những hệ thống trợ giúp đắc
lực nhất cho con ngƣời thực hiện theo dõi, giám sát. Với một bài toán giám
sát giao thông, một hệ thống giám sát có thể cho chúng ta biết đƣợc số lƣợng
phƣơng tiện lƣu thông qua đoạn đƣờng, đƣa ra thông tin về tốc độ chuyển
động, đƣờng đi của đối tƣợng đƣợc theo dõi. Một hệ thống giám sát có thể
phát hiện một đám cháy, tự động cảnh báo cháy ở nơi đƣợc quan sát và theo
dõi.
Trong thời đại phát triển cao của công nghệ tự động, nhu cầu về các hệ
thống giám sát theo dõi ngày càng trở nên cấp thiết đặc biệt trong các lĩnh vực
an ninh, quân sự. Chính bởi vậy việc nghiên cứu và xây dựng một hệ thống
giám sát bằng hình ảnh với hiệu quả và tính tin cậy cao đang là mục tiêu của
nhiều nhà khoa học.
Ý thức đƣợc những lợi ích mà hệ thống giám sát thông minh mang lại,
em chọn đề tài khóa luận là: “Ứng dụng xử lý ảnh trong theo dõi đối tượng
chuyển động” để từ đó có thể áp dụng giải quyết bài toán theo dõi giám sát
giao thông – một vấn đề bức bách hiện nay.
2. Mục đích, đối tượng nghiên cứu
Mục đích nghiên cứu: Tìm hiểu, khảo sát thực nghiệm và ứng dụng của hệ
thống giám sát, theo dõi đối tƣợng chuyển động. Dựa trên một số thực nghiệm
về việc sử dụng camera quan sát để phát hiện, theo dõi đối tƣợng chuyển
động và xây dựng chƣơng trình minh họa.


Ngoài các phần mở đầu và kết luận, khóa luận bao gồm các chƣơng
sau:

2


Chƣơng 1: Cơ sở lý thuyết
Nêu các vấn đề cơ bản của xử lý ảnh và các phép toán ứng dụng trong
bài toán theo dõi đối tƣợng chuyển động.
Chƣơng 2: Xử lý ảnh trong theo dõi đối tƣợng chuyển động
Trình bày các vấn đề cần giải quyết trong hệ thống theo dõi, giới thiệu
bài toán theo dõi đối tƣợng chuyển động. Sau đó trình bày một số kỹ thuật
giải quyết vấn đề theo dõi đối tƣợng chuyển động, từ đó đề xuất các phƣơng
pháp và giải quyết giải quyết bài toán.
Chƣơng 3: Chƣơng trình thử nghiệm
Trình bày về việc cài đặt chƣơng trình, xây dựng dữ liệu thực nghiệm,
các quá trình thực nghiệm, kết quả thực nghiệm và các kết quả đánh giá, nhận
xét các xử lý từ thực nghiệm.

3


CHƯ NG 1: C

SỞ Ý THU ẾT

1.1 Xử lý ảnh
Con ngƣời thu nhận thông tin qua các giác quan, trong đó thị giác
đóng vai trò quan trọng nhất. Những năm trở lại đây với sự phát triển của
phần cứng máy tính, xử lý ảnh và đồ hoạ đó phát triển một cách mạnh mẽ và

chọn

Hậu xử

Đối sách rút

xử lý

đặc

lý

ra kết luận

điểm
Hậu xử lý

Hình 1.2: Các bước cơ bản trong một hệ thống xử lý ảnh
1 2 Các vấn đề cơ bản trong xử lý ảnh
1.2.1 Một số khái niệm
 Pixel (Picture Element): Phần tử ảnh
Ảnh trong thực tế là một ảnh liên tục về không gian và về giá trị độ
sáng. Để có thể xử lý ảnh bằng máy tính cần phải tiến hành số hoá ảnh. Trong
quá trình số hoá, ngƣời ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông
qua quá trình lấy mẫu (rời rạc hoá về không gian) và lƣợng hoá thành phần
giá trị (rời rạc hoá biên độ giá trị) mà về nguyên tắc bằng mắt thƣờng không
thể phân biệt hai mức kề nhau. Trong quá trình này, ngƣời ta sử dụng khái
niệm Picture Element mà ta quen gọi hay viết tắt là pixel - phần tử ảnh. Ở đây
cũng cần phân biệt khái niệm pixel hay đề cập đến trong hệ thống đồ hoạ máy
tính. Để tránh nhầm lẫn ta tạm gọi pixel này là pixel thiết bị. Khái niệm pixel

thƣờng đƣợc đặc trƣng bởi tọa độ màu RGB tƣơng ứng với nó trong hệ tọa
độ màu cơ bản sau:

Hình 1.3: Hệ tọa độ màu RGB

6


Về mặt toán học ta có thể xem ảnh nhƣ là một hàm hai biến f(x,y)
với x,y là các biến tọa độ. Giá trị số tại điểm (x,y) tƣơng ứng với giá trị xám
hoặc độ sáng của ảnh. ảnh có thể đƣợc biểu diễn theo một trong hai mô hình
sau đây:
 Mô hình Raster: là mô hình biểu diễn ảnh phổ biến nhất hiện nay. ảnh
đƣợc biểu diễn dƣới dạng ma trận các điểm ảnh. Tùy theo nhu cầu
thực tế mà mỗi điểm ảnh có thể đƣợc biểu diễn bởi một hay nhiều
bit. Mô hình Raster phù hợp cho việc thu nhận và hiển thị ảnh.
 Mô hình vector: bên cạnh mục đích tiết kiệm không gian lƣu trữ, dễ
dàng hiển thị và in ấn, các ảnh biểu diễn theo mô hình vector còn có
ƣu điểm cho phép dễ dàng lựa trọn, sao chép, di chuyển, tìm kiếm,
v.v… Trong mô hình này ngƣời ta sử dụng hƣớng vectot của các điểm
ảnh lân cận để mã hóa và tái tạo ảnh ban đầu. Các ảnh vector đƣợc thu
nhậnh trực tiếp từ các thiết bị số hóa nhƣ Digitalize hoặc chuyển đổi
từ các ảnh Raster thông qua các chƣơng trình vector hóa.
Khi xử lý các ảnh Raster chúng ta có thể quan tâm đến mối quan hệ
trong vùng lân cận của các điểm ảnh. Các điểm ảnh có thể xếp hàng trên
một lƣới hình vuông, hoặc lƣới lục giác hoặc theo một cách hoàn toàn ngẫu
nhiên với nhau. Cách sắp xếp theo lƣới hình vuông đƣợc quan tâm nhiều
nhất và có hai khái niệm sau: điểm 4 – láng giềng và điểm 8 – láng giềng.
Hình vẽ 1.4 dƣới đây mô tả các khái niệm này:


 Giảm số mức xám: Thực hiện bằng cách nhóm các mức xám gần
nhau thành một bó. Trƣờng hợp chỉ có 2 mức xám thì chính là
chuyển về ảnh đen trắng. Ứng dụng: In ảnh màu ra máy in đen trắng.
 Tăng số mức xám: Thực hiện nội suy ra các mức xám trung gian
bằng kỹ thuật nội suy. Kỹ thuật này nhằm tăng cƣờng độ mịn cho ảnh.
1.2.7 Phân tích ảnh
Là khâu quan trọng trong quá trình xử lý ảnh để tiến tới hiểu ảnh.
Trong phân tích ảnh việc trích chọn đặc điểm là một bƣớc quan trọng. Các
đặc điểm của đối tƣợng đƣợc trích chọn tuỳ theo mục đích nhận dạng trong
quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh sau đây:
Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ,
điểm uốn v.v...

8


Đặc điểm biến đổi: Các đặc điểm loại này đƣợc trích chọn bằng việc
thực hiện lọc vùng (zonal filtering). Các bộ vùng đƣợc gọi là “mặt nạ đặc
điểm” (feature mask) thƣờng là các khe hẹp với hình dạng khác nhau (chữ
nhật, tam giác, cung tròn v.v...)
Đặc điểm biên và đường biên: Đặc trƣng cho đƣờng biên của đối
tƣợng và do vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến đƣợc
dùng khi nhận dạng đối tƣợng. Các đặc điểm này đƣợc trích chọn nhờ toán
tử gradient, toán tử la bàn, toán tử Laplace, toán tử “chéo không” (zero
crossing) v.v..
Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các
đối tƣợng chính xác, với tốc độ tính toán cao và dung lƣợng lƣu trữ giảm
xuống.
1.2.8 Nhận dạng
Nhận dạng tự động (automatic recognition), mô tả đối tƣợng, phân

Trong các ứng dụng rõ ràng là không thể chỉ dùng có một cách tiếp
cận đơn lẻ để phân loại “tối ƣu” do vậy cần sử dụng cùng một lúc nhiều
phƣơng pháp và cách tiếp cận khác nhau. Do vậy, các phƣơng thức phân loại
tổ hợp hay đƣợc sử dụng khi nhận dạng và nay đã có những kết quả có
triển vọng dựa trên thiết kế các hệ thống lai (hybrid system) bao gồm
nhiều mô hình kết hợp.
Việc giải quyết bài toán nhận dạng trong những ứng dụng mới nảy
sinh trong cuộc sống không chỉ tạo ra những thách thức về thuật giải, mà
còn đặt ra những yêu cầu về tốc độ tính toán. Đặc điểm chung của tất cả
những ứng dụng đó là những đặc điểm đặc trƣng cần thiết là nhiều, không
thể do chuyên gia đề xuất, mà phải đƣợc trích chọn dựa trên các thủ tục phân
tích dữ liệu.
1.2.9 Nén ảnh
Nhằm giảm thiểu không gian lƣu trữ. Thƣờng đƣợc tiến hành theo
cả hai cách khuynh hƣớng là nén bảo toàn và không bảo toàn thông tin. Nén
không bảo toàn thì thƣờng có khả năng nén cao hơn nhƣng khả năng phục
hồi thì kém hơn. Trên cơ sở hai khuynh hƣớng, có 4 cách tiếp cận cơ bản
trong nén ảnh:

10


 Nén ảnh thống kê: Kỹ thuật nén này dựa vào việc thống kê tần xuất
xuất hiện của giá trị các điểm ảnh, trên cơ sở đó mà có chiến lƣợc mã
hóa thích hợp. Một ví dụ điển hình cho kỹ thuật mã hóa này là *.TIF
 Nén ảnh sử dụng phép biến đổi: Đây là kỹ thuật tiếp cận theo hƣớng
nén không bảo toàn và do vậy, kỹ thuật thƣớng nến hiệu quả hơn.
*.JPG chính là tiếp cận theo kỹ thuật nén này
 Nén ảnh Fractal: Sử dụng tính chất Fractal của các đối tƣợng ảnh, thể
hiện sự lặp lại của các chi tiết. Kỹ thuật nén sẽ tính toán để chỉ cần


N 1 N 1

v(k,l) =



u(m,n) ak,l(m,n) với k,l = 0, 1,..., N-1

m 0 n  0

N 1 N 1

u(m,n) =



v(k,l) a*k,l(m,n) với m,n = 0, 1,..., N-1

k 0 l 0

Trong đó {ak,l (m,n)} gọi là một biến đổi ảnh. Đó chính là tập các hàm
cơ sở (trong xử lý ảnh gọi là các ảnh cơ sở) .
Theo định nghĩa, một biến đổi tƣơng ứng với A là unita và tách đƣợc
(separable unitary transforms) nếu:
AA*T = ATA* = I với A là ma trận biến đổi; A*T là ma trận chuyển vị của A.
Nhìn chung, trong xử lý ảnh số, ta hay dùng biến đổi đơn vị trực giao
và tách đƣợc. Trong ngữ cảnh này, viết dƣới dạng ma trận ta có:
N 1 N 1


Theo công thức trên ta có:
V = A.U.AT =

1 1 1  1 2  1 1 1   5 1
.

.

 = 

2 1 1 3 4  2 1 1  2 0 

U = A*T.V.A* =

1 2 
1 1 1   5 1 1 1 1 
.
.
=
3 4 




 
2 1 1  2 0  2 1 1



Có rất nhiều phép biến đổi đƣợc dùng trong xử lý ảnh nhƣ biến đổi


dxdy

 

u,v biểu diễn tần số không gian.
 

- Biến đổi ngƣợc f(x,y) =

  F ( u, v ) e

2 i ( xu  yv )

dudv



b) Biến đổi Fourrier rời rạc – DFT
Biến đổi DFT đƣợc phát triển dựa trên biến đổi Fourrier cho ảnh số. Ở
đây, ta dùng tổng thay cho tích phân. Biến đổi DFT tính các giá trị của biến
đổi Fourrier cho một tập các giá trị trong không gian tần số đƣợc cách đều.
DFT hai chiều của một ảnh M x N: {u(m,n)} là một biến đổi tách đƣợc
và đƣợc định nghĩa :
N 1 N 1

v(k,l) =

  u(m, n)


m 0 n  0

13


u(m,n) =

1
N

N 1 N 1

  v( k , l ) WN -km WN -ln với 0  m, n  N-1
k 0 l 0

Viết lại công thức trên ta có:
v(k,l) =
u(m,n) =

1
N
1
N

N 1 N 1

  u(m, n) WN (km + ln) với 0  l, k  N-1

m 0 n  0


Hotelling hay phƣơng pháp thành phần chính.
Một số khái niệm và định nghĩa:
X là một biến véc tơ ngẫu nhiên gồm n thành phần xi, i = 1, 2,…, n.
Mỗi thành phần xi là giá trị ngẫu nhiên. Ngƣời ta định nghĩa:


 Kì vọng toán học (Trung bình số học) E[x] =

 xP( x)dx

với P(x) là



hàm mật độ xác suất và x là biến ngẫu nhiên liên tục.
 Mô men toán học:


mk =

 xP( x)dx

= E[xk] với mk gọi là mô men bậc k của x.



 Tính tƣơng quan: Một tín hiệu phụ thuộc vào thời gian
 Hàm tự tƣơng quan của 1 tín hiệu x[t] đƣợc định nghĩa:
ψx = E[x(t).x(t+δ)]


ai,i = xi2 - mi2 ≠ 0 còn ai,j = 0 với i ≠ j.
a) Cơ sở lý thuyết của biến đổi Hotelling
Đây là phép biến đổi không gian n chiều thành không gian m chiều, với
m
= <( X -X)T( X -X)>
n

=


n

=



i  m 1

<  i2 >
n

n

mà  = UTX, do đó  =



i  m 1


Đặt  =  +



i  m 1

i(1 - uiTui).

Để tìm min của  ta dùng phƣơng pháp đạo hàm và dẫn đến việc giải
phƣơng trình:

(R - i)ui = 0

Phƣơng trình trên gọi là phƣơng trình đặc trƣng của R với i là các trị
riêng và ui là các véc tơ riêng tƣơng ứng. Đây chính là cơ sở lý thuyết của
biến đổi Hotelling.

16


b) Biến đổi Hotelling
Khái niệm biến đổi Hotelling:
Cho u là một véc tơ các số thực ngẫu nhiên; véctơ cơ sở của biến đổi
Hotelling là các véc tơ riêng trực giao của ma trận hiệp biến R cho bởi
phƣơng trình:
R k = k k ; 0  k N-1
N 1

Biến đổi Hotelling của u là v = * u và biến đổi ngƣợc u = v =
T

A cho bởi:
E[u(m,n)u(m',n')] = r(m,n;m',n') với 0  m,m',n,n'  N-1
thì ảnh cơ sở của biến đổi Hotelling là các hàm riêng, chuẩn và trực giao k,l
là lời giải của phƣơng trình:
N 1 N 1



r(m,n;m',n') k,l = k,l k,l

m 0 n  0

Theo ký pháp ma trận ta có: Ri = i i với i = 0, 1, ..., N2-1
với i là véc tơ N2 x 1 biểu diễn của k,l và R là ma trận N2 x N2 ánh xạ vào
véc tơ u, R = E[uu].
Nếu R là tách đƣợc thì ma trận  N2 x N2 mà các cột là i sẽ tách đƣợc:
k,l(m,n) = 1  2 hay R = R1  R2
Biến đổi Hotelling của U là V = *Tu = 1*T  2*T
và biến đổi ngƣợc U = 1 V 2

17


1.4 Toán tử xử lý điểm ảnh
Ảnh thô có cấu trúc đơn giản, song lại rất phức tạp về nội dung. Nhƣ
chúng ta biết, ảnh là một tập hợp các điểm ảnh, chứa một lƣợng thông tin khá
lớn. Thƣờng để xử lý ảnh, ngƣời ta hay biểu diễn ảnh dƣới một dạng khác để
có thể làm rõ một số tính chất của chúng. Xử lý điểm ảnh thực chất là dùng
các ánh xạ nhằm biến đổi giá trị của một điểm chỉ dựa vào giá trị của chính nó
mà không quan tâm tới các giá trị của các điểm ảnh khác. Một cách toán học,