BỘ GIÁO DỤC VÀ ĐÀO TẠO

BỘ QUỐC PHÒNG

VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ

NGUYỄN VĂN CĂN

NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT
TOÁN PHÁT HIỆN VÀ PHÂN LOẠI PHƯƠNG TIỆN
TỪ DỮ LIỆU VIDEO GIAO THÔNG

LUẬN ÁN TIẾN SĨ TOÁN HỌC

HÀ NỘI, NĂM 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
BỘ QUỐC PHÒNG
VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ

NGUYỄN VĂN CĂN

NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT
TOÁN PHÁT HIỆN VÀ PHÂN LOẠI PHƯƠNG TIỆN
TỪ DỮ LIỆU VIDEO GIAO THÔNG

Chuyên ngành: CƠ SỞ TOÁN HỌC CHO TIN HỌC
Mã số: 62 46 01 10

LUẬN ÁN TIẾN SĨ TOÁN HỌC

Tôi muốn đặc biệt cảm ơn PGS. TS Ngô Quốc Tạo, TS. Nguyễn Đức
Dũng, phòng Nhận dạng và Xử lý tri thức, thuộc Viện Công nghệ thông tin,
Viện hàn lâm Khoa học Việt Nam; cảm ơn các đồng nghiệp công tác tại Trường
Đại học Kỹ thuật – Hậu cần Công an nhân dân đã có những bàn luận, thảo luận
hữu ích, cài đặt thử nghiệm trong công việc nghiên cứu của tôi.
Cuối cùng, tôi dành luận án này cho gia đình tôi và bạn bè của tôi. Nếu
không có sự hỗ trợ của họ đầy đủ, tôi sẽ không có can đảm để đi qua tất cả
những khó khăn trong việc nghiên cứu.


i

MỤC LỤC

DANH MỤC CÁC KÝ HIỆU ................................................................................................... iii
DANH MỤC CHỮ VIẾT TẮT ................................................................................................. iv
DANH MỤC CÁC BẢNG ......................................................................................................... v
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ................................................................................... vi

MỞ ĐẦU ............................................................................................................... 1
Chương 1. TỔNG QUAN VỀ PHÁT HIỆN VÀ PHÂN LOẠI PHƯƠNG
TIỆN GIAO THÔNG TỪ VIDEO ........................................................................ 8
1.1. Cơ sở lý thuyết và những khái niệm cơ bản ........................................... 8
1.1.1. Dữ liệu video số ............................................................................... 8
1.1.2. Mô-men bất biến ............................................................................ 12
1.1.3. Hình dạng và Khối đối tượng chuyển động ................................... 13
1.1.4. Đường viền đối tượng .................................................................... 13
1.1.5. Nền và đối tượng chuyển động ...................................................... 21
1.1.6. Entropy của khối ............................................................................ 22
1.1.7. Biểu diễn hình dạng đối tượng theo vector khoảng cách .............. 25

2.3. Phương pháp đếm phương tiện giao thông áp dụng mô hình GMM
thích nghi thay đổi ánh sáng kết hợp luồng quang học ............................... 78
2.3.1. Sơ đồ khối tổng quát ...................................................................... 79
2.3.2. Thuật toán phát hiện và gán nhãn cho khối (SLBBI) .................... 82
2.3.3. Thuật toán trích chọn luồng quang học (EBOF) ........................... 83
2.3.4. Kết quả thực nghiệm. ..................................................................... 86
2.4. Kết luận chương 2................................................................................. 91
Chương 3. PHÂN LOẠI PHƯƠNG TIỆN GIAO THÔNG TỪ VIDEO
DỰA TRÊN ĐẶC TRƯNG HÌNH DẠNG ........................................................ 93
3.1. Phân đoạn khối phương tiện dựa trên kích thước ................................. 93
3.1.1. Phân tích kích thước phương tiện .................................................. 93
3.1.2. Thuật toán phân loại theo kích thước ............................................ 95
3.2. Phân loại phương tiện bằng kết hợp kích thước ảnh và hình chiếu
hình dạng khối phương tiện ......................................................................... 98

3.2.1. Ý tưởng phương pháp .................................................................... 99
3.2.2. Giai đoạn chuẩn bị CSDL ............................................................ 100
3.2.3. Thuật toán phân loại dựa trên độ dài và hình chiếu đối tượng .... 101
3.3. Phân loại phương tiện dựa trên đường viền biểu diễn bằng số phức . 103
3.3.1. Sơ đồ khái quát............................................................................. 104
3.3.2. Xấp xỉ độ dài đường viền và thuật toán Douglas Peucker........... 104
3.3.3. Thuật toán CCAVC...................................................................... 107
3.3.4. Kết quả thực nghiệm: ................................................................... 111
3.4. Kết luận chương 3 ............................................................................... 114
PHẦN KẾT LUẬN ........................................................................................... 116
PHỤ LỤC .............................................................................................................. 1
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ ........................................ 118
TÀI LIỆU THAM KHẢO ................................................................................. 119




Vt(x,y)

Giá trị điểm ảnh (x,y) của khung hình đang xét thời gian t

xy

Giá trị trung bình của các điểm ảnh tương ứng của tập hợp điểm ảnh
(x,y) theo các khung hình đang xét

xy

Trung bình độ lệch chuẩn của điểm ảnh (x,y)
Mô hình nền thích nghi biến đổi cosin rời rạc
Khoảng cách Ơclit giữa các mô hình nền thích nghi

P(Xt)
(Xt, , )

Xác suất quan sát của điểm ảnh tại thời điểm t
Hàm mật độ xác suất tại thời điểm t

i,t

Ma trận hiệp phương sai của phân bố Gauss thứ i tại thời gian t

i,t

Giá trị trung bình của các điểm ảnh tại thời điểm t
Biến nhận giá trị 1/0 thể hiện sự phù hợp mô hình của điểm ảnh mới

Lrounded

Khoảng cách giữa các điểm cơ bản trên biên

D(si,c)

Khoảng cách giữa điểm mẫu và trọng tâm đa giác

SIM(D1,D2)

Độ đo tương tự giữa 2 đa giác D1 và D2.


iv
u

Chiều dài đối tượng tính xấp xỉ

v

Chiều rộng đối tượng tính xấp xỉ



Đường viền Vector



Vector cơ sở đường viền


Trừ nền (Background Subtraction Method)

BGS

Thư viện trừ nền (Background Subtraction Library)

CA

Phân tích đường viền (Contour Analys)

CSDL

Cơ sở dữ liệu (Database)

EV

Vector cơ sở (Elementary Vector)

FG

Tiền cảnh (Foreground)

GMM

Mô hình hỗn hợp Gauss (Gauss Mixture Model)

ICF

Hàm tương quan (Intercorrelation Function)


Bảng 3.1. Kết quả thực nghiệm thuật toán CVIL ......................................................... 98
Bảng 3.2. Bảng kết quả thực nghiệm thuật toán VCALOS .......................................103


vii
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1. Cấu trúc phân đoạn của video ............................................................... 8
Hình 1.2. Các biến đổi hình dáng đối tượng trong không gian 2D. .................... 12
Hình 1.3. Biểu diễn đường viền bằng vector số phức ......................................... 14
Hình 1.4. NSP trên đường viền vector ................................................................ 18
Hình 1.5. Biểu diễn đường viền và lược đồ xám ................................................ 21
Hình 1.6. Mô tả hình dạng hình tròn ................................................................... 26
Hình 1.7. Đa giác xấp xỉ đối tượng có n cạnh..................................................... 27
Hình 1.8. Điểm mẫu căng đều trên mỗi cạnh biên .............................................. 28
Hình 1.9. Kiến trúc tổng thể hệ thống CadProTMS ........................................... 31
Hình 1.10. Trạm nghiệp vụ xử lý phạt nguội vượt đèn đỏ ngã tư ...................... 32
Hình 1.11. Cấu trúc hệ thống phát hiện và phân loại xe dựa trên video ............. 33
Hình 1.12. Sơ đồ của hệ thống giám sát giao thông tự động .............................. 35
Hình 1.13. Cấu trúc hệ thống tích hợp phát hiện, phân loại, theo dõi đối tượng 36
Hình 1.14. Cấu trúc hệ thống phát hiện đối tượng chuyển động ........................ 37
Hình 1.15. Lược đồ khái quát phân loại đối tượng dựa trên hình chiếu ............. 38
Hình 1.16. Cấu trúc khái quát hệ thống nhận dạng đối tượng chuyển động ...... 46
Hình 1.17. Sơ đồ xác định vùng nghiên cứu ....................................................... 47
Hình 1.18. Hướng tiếp cận xử lý bài toán ........................................................... 49
Hình 2.1. Lược đồ khái quát thuật toán CCA-GMMOF ..................................... 80
Hình 2.2. Minh họa thuật toán gán nhãn cho khối .............................................. 83
Hình 2.3. Dữ liệu video quay trên đường quốc lộ 5, hướng Hải phòng - Hà Nội
............................................................................................................................. 88
Hình 2.4. Một số hình ảnh từ camera đưa vào thực nghiệm ............................... 89
Hình 2.5. Giao diện kết quả thực nghiệm của hệ thống ...................................... 89

Nhiều nghiên cứu trên thế giới và Việt Nam đã quan tâm đến vấn đề phát
hiện và phân loại phương tiện giao thông, tuy nhiên chưa có nghiên cứu đầy đủ
nào quan tâm đến mức độ dày đặc của phương tiện trên đường, cũng như quan
tâm đặc biệt đến phương tiện giao thông chủ yếu là xe máy và xe ô tô.
Việc lựa chọn phương pháp, thuật toán, hay phối kết hợp các thuật toán sử
dụng trong hệ thống giám sát tự động, cũng như cải tiến một số thông số kỹ
thuật trong thuật toán mang lại lợi ích cho việc phát hiện và phân loại phương
tiện giao thông trong bối cảnh Việt Nam là điều cần thiết có ý nghĩa cả về lý
thuyết và thực tiễn.
Bài toán phát hiện và phân loại phương tiện giao thông dựa trên video là
xét xem tại một thời điểm, trong vùng quan tâm, có những loại phương tiện gì,
số lượng tương ứng. Về ứng dụng, bài toán thuộc nhóm các ứng dụng liên quan


2
đến giao thông thông minh. Bài toán được ứng dụng nhiều trong lĩnh vực quản
lý giao thông, trong nhiều hoạt động an ninh, quốc phòng, kinh tế xã hội, như
cảnh báo trộm, cảnh báo cháy, giám sát bảo vệ các mục tiêu quan trọng, thu thập
các chứng cứ tại những tình huống nhạy cảm.
Yêu cầu cơ bản của bài toán phát hiện và phân loại giao thông là với dữ
liệu đầu vào là video giao thông, yêu cầu đầu ra là loại phương tiện tham gia
giao thông trong vùng quan sát (ô tô, xe máy và các phương tiện thô sơ khác).
Hướng tiếp cận giải quyết bài toán:
Thứ nhất, cần xem xét cấu trúc và phương pháp xử lý dữ liệu video. Cấu
trúc dữ liệu video được kết cấu từ tập các khung hình, tốc độ hiển thị các khung
hình trong một đơn vị thời gian (giây), mỗi khung hình là một ảnh tĩnh,...
Phương pháp xử lý dữ liệu video là việc xử lý lưu trữ, trích chọn khung hình,
phân đoạn, phân tích, trích chọn đặc trưng dựa trên cơ sở dữ liệu (CSDL) tri
thức có sẵn. Từ những tập dữ liệu video, qua quá trình xử lý, mang lại những
thông tin hữu ích theo mục đích yêu cầu của con người.

Yếu tố ảnh hưởng đến phương pháp tiếp cận:
Về màu sắc phương tiện thay đổi liên tục theo thời gian, thêm vào đó có
nhiều loại phương tiện có màu sắc tương đồng nhau, do vậy việc phân loại dựa
trên màu sắc là khó khăn và không mang lại kết quả.
Về hình dạng, các phương tiện có thể đi sát nhau trong khung hình quan
sát, hợp thành các khối và dẫn đến khó xác định được chính xác đó là phương
tiện gì bằng biện pháp thông thường. Đặc biệt trong điều kiện giao thông tại Việt
Nam, mật độ phương tiện di chuyển trên đường dày đặc về mật độ, đa dạng về
chủng loại thì việc phân loại càng khó khăn. Tuy nhiên hình dạng xe ô tô, hình
dạng xe máy, phương tiện thô sơ khác là một tập có thể xác định kể cả khi chúng
hợp khối.
Ngoài việc xác định tập đặc trưng của phương tiện chuyển động trong
video, để có thể nhận dạng, xác định mật độ phương tiện, cần xác định các yếu
tố, tình huống ảnh hưởng đến phương pháp xác định các tập thuộc tính liên quan
đến phương pháp tiếp cận phát hiện và phân loại phương tiện giao thông.
Tình huống liên quan đến chuyển động gồm:


4
 Đối tượng bắt đầu vào vùng quan sát;
 Đối tượng ra khỏi vùng quan sát;
 Đối tượng đang đi rồi dừng lại;
 Đối tượng đang dừng thì chuyển động;
 Nền động (dao động tự nhiên).
Tình huống liên quan đến khối chuyển động gồm:
 Các đối tượng di chuyển cạnh nhau tạo thành một khối đối tượng;
 Đối tượng đang di chuyển tách khối;
 Đối tượng đang di chuyển thì hợp khối.
Tình huống liên quan đến chất lượng ảnh gồm nhiều yếu tố liên quan,
nhưng chủ yếu là:

Thử nghiệm và đánh giá kết quả một số phương pháp đề xuất:
 Thu thập dữ liệu video trên một số cung đường tại đường quốc lộ.
 Viết chương trình thử nghiệm bằng ngôn ngữ lập trình C++ trên môi
trường .NET.
 Đánh giá và phân tích kết quả.
5. Ý nghĩa khoa học và thực tiễn của luận án
Ý nghĩa khoa học:
Làm phong phú hơn về lý luận cho phương pháp phát hiện và phân loại đối
tượng chuyển động trong video.
Tổng hợp và xây dựng một tập các phương pháp trích chọn các đặc trưng
phương tiện chuyển động, biểu diễn và xử lý các đặc trưng của phương tiện theo
từng cấp độ phù hợp cho phân loại và đếm đối tượng, bao gồm:
 Đặc trưng khối chuyển động.
 Đặc trưng hình dạng và kích thước đối tượng.
 Đặc trưng luồng quang học.
 Đặc trưng đường viền đối tượng.
Đề xuất khung làm việc chung cho bài toán xác định mật độ phương tiện
trong video giao thông.
Ý nghĩa thực tiễn:
Mở ra khả năng tính toán mới để xác định đối tượng trong ảnh nhanh hơn;
có sự phân loại tốt hơn, tránh được những thông tin dư thừa do mật độ đối tượng


7
chuyển động dày đặc, đan xen gây ra... phục vụ cho các ứng dụng thực tế như đo
lưu lượng giao thông, xác định hiện trường tai nạn giao thông, chứng thực xe đã
đi qua đoạn đường trong khoảng thời gian t,... phục vụ trong công tác an ninh.
6. Cấu trúc của luận án
Phần mở đầu. Giới thiệu tổng quát bài toán, phương pháp tiếp cận, phạm vi
nghiên cứu, những thách thức đặt ra cho bài toán, hướng nghiên cứu, ý nghĩa

hợp và biên tập tài liệu Quản lý dữ liệu video và tìm kiếm thông tin [20], trong
đó đã xác định khái niệm, cấu trúc video số, cách tổ chức và xem xét cấu trúc dữ
liệu video.
Định nghĩa 1.1. Video số
Video số là một dãy các khung hình liên tiếp, mỗi khung hình tương ứng
với một hình ảnh tĩnh. Khi video được thực hiện, dãy khung hình được hiển thị
tuần tự với một tốc độ nhất định. Tốc độ hiển thị các khung hình thường là 30
hoặc 25 khung hình/giây [20].
Hình 1.1 thể hiện cấu trúc tổng quát của dữ liệu Video: khung hình, cảnh
quay, cảnh.

Hình 1.1. Cấu trúc phân đoạn của video


9
Trong kỹ thuật xử lý dữ liệu video tác động đến nhiều thành phần và các
đối tượng kéo theo của video như: cảnh, cảnh quay, khung hình, ảnh, điểm ảnh,
ngưỡng, tách ngưỡng, đường viền, nền, phép cộng ảnh, phép nhân ảnh với 1
số... Dữ liệu video và những thành phần liên quan được đặc tả hình thức bằng
ngôn ngữ đặc tả hình thức RAISE như sau:
scheme Video=
class
type
Video=Scene-list, /*Video là một danh sách các cảnh*/
Scene=Shot-list, /*Cảnh là một danh sách các cảnh quay*/
Shot=Image-list,

/*Cảnh quay là một danh sách các ảnh*/

Image=Point-set, /*Ảnh là một tập hợp các điểm ảnh*/

tong:Shot->Image
tong(sh) is if len(sh) = 1 then hd(sh)
else hd(sh)+tong(tl(sh))
end,
/:Image><Nat->Image,
/* Định nghĩa ảnh nền */
back1:Shot->Image
back1(sh) is tong(sh)/Shotnumber(sh),
/* Định nghĩa phép nhân ảnh với một số*/
alpha: Real,
*:Real><Image-> Image,
back:Shot->Image /* anh nen*/
back(sh) is if
else

len(sh) = 1 then hd(sh)

alpha*hd(sh)+(1.0-alpha)*back( tl(sh))
end,

/* Định nghĩa ảnh biên */
constraint:Image><Image->Bool,
anhbien:Image->Image
anhbien(I) as I1 post constraint(I,I1),
/* Tách ngưỡng */
constraint:Image><Image><Real->Bool,
tachnguong:Image><Real->Image
tachnguong(I,

threshold)

- Kết cấu (Texture): là một đặc trưng quan trọng của bề mặt khung hình,
nơi xảy ra việc lặp lại mẫu cơ bản. Có hai dạng biểu diễn kết cấu phổ biến: ma
trận đồng thời và Tamura. Ma trận đồng thời mô tả hướng và khoảng cách giữa
các điểm ảnh, ta có thể trích chọn được các thống kê có ý nghĩa. Biểu diễn
Tamura 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 rất quan trọng trong việc tìm hiểu
nội dung ảnh vì nó biểu diễn rất trực quan.
- Hình dạng (Shape): đặc trưng hình dạng có thể được phân chia thành đặc
trưng toàn cục và đặc trưng cục bộ. Đặc trưng toàn cục là đặc trưng thu được từ
toàn bộ hình dáng đối tượng trong ảnh (Ví dụ: chu vi, tính tròn, hướng trục
chính...). Đặc trưng cục bộ là đặc trưng thu được từ việc thao tác với một phần
của ảnh, không phụ thuộc vào toàn bộ ảnh.
- Chuyển động (Motion): Là thuộc tính quan trọng của video. Các đặc
trưng chuyển động như mô-men của trường chuyển động, biểu đồ chuyển động,
các tham số chuyển động toàn cục có thể được trích chọn từ vectơ chuyển động.


12

1.1.2. Mô-men bất biến
Mô-men có nhiều ứng dụng trong kỹ thuật phân đoạn ảnh, đối sánh ảnh và
nhận dạng ảnh. Năm 2004, Chee-Way Chong and và cộng sự nghiên cứu về lý
thuyết môn men và ứng dụng [6]. Từ những năm 1962, tác giả Hu M. K [13] đã
đề cập đến vấn đề hệ số tương quan trong kỹ thuật phân đoạn ảnh. Dựa vào tính
chất bất biến và hệ số tương quan của mô-men để đối sánh và phân loại đối
tượng trong ảnh theo hình chiếu đối tượng trong không gian 2D.
Ứng dụng của mô-men bất biến trong nhận dạng ảnh:
Mô-men bất biến thường được dùng để trích đặc điểm trong xử lý ảnh, và
ghi nhận hình dạng đối tượng và phân lớp. Mô-men có thể cung cấp các đặc
điểm của một đối tượng duy nhất mô tả hình dạng của đối tượng.

- Phân rã X thành các khối con: X=X1+ ... + Xn, với tiêu chuẩn phân rã là
một ngưỡng xác định để các điểm ảnh tạo thành một khối.
- Gán nhãn cho các khối con: Xác định đối tượng có trong khối.
Định nghĩa 1.3. Hình dạng khối đối tượng
Hình dạng khối đối tượng [30] là một đa giác được xấp xỉ lên đường biên
của nó. Biên đối tượng trong ảnh là một tập hợp các điểm ảnh phân biệt giữa
vùng bên trong và bên ngoài đối tượng. Gọi X là đường biên của đối tượng, DG
là đa giác xấp xỉ lên đường biên đối tượng, DT(X) là diện tích khối ảnh đối
tượng, DT(DG) là diện tích của đa giác xấp xỉ lên X. Khi đó:
DT(X)  DT(DG) + , với  là ngưỡng xác định cho phép sai số.
1.1.4. Đường viền đối tượng
Định nghĩa 1.4. Đường viền
Tập hợp tất cả các điểm biên của đối tượng, tạo thành một đường khép kín
bao quanh đối tượng gọi là đường viền của đối tượng, hay nói cách khác đường
viền của một đối tượng là đường biên khép kín bao quanh đối tượng [30].


14
Một số đặc tính của đường viền như độ dài, hình dáng, trọng tâm diện tích
bên trong, rất có ích để tính toán, nhận diện đối tượng là gì. Biểu diễn đường
viền trong ảnh có nhiều cách khác nhau. Trong các hệ thống thị giác máy tính,
một vài định dạng mã hóa đường viền được sử dụng như mã hóa Freeman, mã
hóa 2 chiều, mã hóa đa giác thường được sử dụng.
Phân tích đường viền (CA) [30] cho phép mô tả, lưu trữ, so sánh và tìm ra
các đối tượng biểu diễn dưới dạng đường viền. Đường viền chứa thông tin cần
thiết về hình dạng đối tượng. Không quan tâm nhiều đến các điểm bên trong của
đối tượng. Các trường hợp không quan tâm nhiều đến vùng bên trong đối tượng
nhưng quan tâm nhiều về thể hiện đường viền bên ngoài thì cho phép chuyển về
không gian 2 chiều của ảnh tức là không gian đường viền, từ đó cho phép giảm
thời gian tính toán và độ phức tạp tính toán. CA cho phép giải quyết hiệu quả