luan van thac si - luan van thac si kinh te - luan an tien - luan van 1 of 95.

BỘ GIAO THÔNG VẬN TẢI

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

TRƢỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM

VÕ PHƢỚC SƠN

XÂY DỰNG CHƢƠNG TRÌNH NHẬN DẠNG
BIỂN BÁO GIAO THÔNG

LUẬN VĂN THẠC SĨ NGÀNH KỸ THUẬT

HẢI PHÒNG, 2016

Footer Page - Footer Page - kho luan van - tai lieu - 123doc- tieu luan - khoa luan-tai chinh ngan hang - thuong mai -


luan van thac si - luan van thac si kinh te - luan an tien - luan van 2 of 95.

BỘ GIAO THÔNG VẬN TẢI

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

TRƢỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM

VÕ PHƢỚC SƠN

XÂY DỰNG CHƢƠNG TRÌNH NHẬN DẠNG



luan van thac si - luan van thac si kinh te - luan an tien - luan van 4 of 95.

LỜI CẢM ƠN
Hoàn thành Luận văn Thạc sĩ này, trước hết tôi xin bày tỏ lòng biết ơn sâu sắc
tới TS. Nguyễn Hữu Tuân, người hướng dẫn khoa học đã tận tình hướng dẫn và giúp
đỡ tôi trong suốt thời gian thực hiện Luận văn.
Nhân dịp này tôi xin bày tỏ lòng biết ơn đến các Thầy Cô Viện đào tạo Sau đại
học trường Đại học Hàng Hải Việt Nam, đã giúp đỡ tôi trong suốt thời gian học tập và
hoàn thành Luận văn Thạc sĩ này.
Cuối cùng tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp chính là nguồn động
viên, khích lệ vô giá đã đi cùng tôi trong suốt những năm tháng phấn đấu, rèn luyện
để có được sản phẩm khoa học này.
Hải Phòng, ngày 15 tháng 3 năm 2016
Học viên

Võ Phước Sơn

Footer Page - Footer Page - kho luan van - tai lieu - 123doc- tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai


luan van thac si - luan van thac si kinh te - luan an tien - luan van 5 of 95.

MỤC LỤC

LỜI CAM ĐOAN ........................................................................................................... 2
LỜI CẢM ƠN ................................................................................................................ 3
MỤC LỤC ...................................................................................................................... 4
DANH MỤC CÁC CHỮ VIẾT TẮT VÀ KÝ HIỆU .................................................... 6

SVM, SURF VÀ ỨNG DỤNG TRONG NHẬN DẠNG ............................................ 32
BIỂN BÁO GIAO THÔNG ......................................................................................... 32
3.1. SVM ................................................................................................................. 32
3.2. Các mô hình sửa dụng SVM phổ biến............................................................. 34
3.3. SIFT và SUFR trong phân lớp dữ liệu............................................................. 36
3.4. Nhâ ̣n da ̣ng biể n báo giao thông ....................................................................... 44
3.5. Ứng dụng thực tế ............................................................................................. 45
3.5.1. Dữ liê ̣u huấ n luyê ̣n .................................................................................... 45
3.5.2. Nhâ ̣n da ̣ng biể n báo giao thông ................................................................. 46
3.6. Đánh giá ........................................................................................................... 47
Chương 4 ................................................................................................................... 49
ỨNG DỤNG THỰC TẾ............................................................................................... 49
KẾT LUẬN .................................................................................................................. 52
TÀI LIỆU THAM KHẢO ............................................................................................ 53

Footer Page - Footer Page - kho luan van - tai lieu - 123doc- tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai


luan van thac si - luan van thac si kinh te - luan an tien - luan van 7 of 95.

DANH MỤC CÁC CHỮ VIẾT TẮT VÀ KÝ HIỆU

Chữ viết tắt

Giải thích

SVM

Support Vector Machine


47

Footer Page - Footer Page - kho luan van - tai lieu - 123doc- tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai


luan van thac si - luan van thac si kinh te - luan an tien - luan van 9 of 95.

DANH MỤC CÁC HÌNH

Số hình

Tên hình

Trang

1.1

Sơ đồ tồng quát một hệ nhận dạng

7

1.2

Quá trình xử lý ảnh

8

1.3

Các bước cơ bản trong quá trình xử lý ảnh


21

2.5

Các đặc trưng Haar like mở rộng

21

2.6

Biển báo giao thông

26

2.7

Hình ảnh ở góc độ không tốt

27

2.8

Biển báo có chất lượng cao

29

3.1

Minh họa bài toán 2 phân lớp bẳng phương pháp SVM

41

3.6

Lọc haar wovelet

41

3.7

Mô tả đặc trưng chuẩn của SURF

42

3.8

Kỹ thuật so khớp đặc trưng

43

3.9

Dữ liệu biển báo người đi bộ qua đường

45

3.10

Các loại biển báo giao thông


các vấn đề nhận dạng mẫu – đã được nghiên cứu và phát triển khá nhiều trong thời
gian trở lại đây. Không quá khó để liệt kê ra một vài giải thuật được nghiên cứu và
phát triển nhằm giải quyết bài toán trên, tuy nhiên kết quả hầu hết đều chỉ dừng lại ở
việc giải quyết vấn đề nhận dạng biển báo cơ bản. Trong khi đó, yêu cầu thực tế từ
việc nhận dạng các loại biển báo giao thông là khá lớn. Việc định hình và phát triển
một ý tưởng nhằm phát triển bài toán trên là một vấn đề không đơn giản.
Có thể điểm qua một vài kết quả nghiên cứu được cho là đáng chú ý tại thời
điểm hiện tại đối với nhận dạng biển báo giao thông. Ví dụ mạng neural là một giải
pháp đáng tin đối với các vấn đề phân lớp dữ liệu nói chung, cũng như nhận dạng
biển báo nói riêng, tuy nhiên việc phân tích để tìm ra các đặc trưng phù hợp và hiệu
quả đang là một vấn đề gây nhiều khó khăn trong nghiên cứu và thực nghiệm.
Nói vậy để thấy rằng, việc xây dựng được một giải thuật phù hợp giải quyết bài
toán đặt ra là một vấn đề khó, chưa kể đến việc phát triển và xây dựng mô hình ứng
dụng có thể triển khai thực tế còn cần thêm một khoảng thời gian dài nghiên cứu và
phát triển.
1 tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai
Footer Page - Footer Page - kho luan van - tai lieu - 123doc-


luan van thac si - luan van thac si kinh te - luan an tien - luan van 12 of 95.

Vấn đề khó đầu tiên được đặt ra đối với các bài toán nhận dạng nói chung nằm
ở cách xây dựng tập đặc trưng phù hợp cho mỗi mẫu đối tượng biển báo. Kế đó là các
phương pháp phân lớp cụ thể đối với tập đặc trưng thu được. Xung quanh vấn đề này,
có nhiều cách tiếp cận được đặt ra. Trong đó, bản luận văn tập trung nghiên cứu và
phát triển các giải thuật SVM trong phân lớp dữ liệu, cụ thể trong trường hợp này là
biển báo giao thông, với nền tảng cơ bản dựa trên việc sử dụng các đặc trưng có cấu
trúc và phi cấu trúc, kết hợp với các giải thuật SVM và hàm nhân cụ thể, nhằm nghiên
cứu và đưa ra hướng phát triển hợp lí nhất cho vấn đề nêu trên.
Mục tiêu của đề tài: Nghiên cứu và ứng dụng giải thuật SVM và đặc trưng cục

hình nào đó và gán cho chúng vào một lớp (gán cho đối tượng một tên gọi) dựa theo
những quy luật và các mẫu chuẩn. Quá trình nhận dạng dựa vào những mẫu học biết
trước gọi là nhận dạng có thầy hay học có thầy (supervised learning), trong trường
hợp ngược lại gọi là học không có thầy (non supervised learning). Chúng ta sẽ lần
lượt giới thiệu các khái niệm này.
Chương 1 tập trung xây dựng các khái niê ̣m cơ bản về nhận dạng cũng như xử
lý ảnh, nhằ m cung cấ p các kiế n thức cơ bản , làm tiền đề luận cứ cho các lý luận học
thuật ở các chương sau này.
1.1.1. Quá trình nhận thức của con ngƣời là quá trình nhận dạng
Các thực thể xã hội (con người, doanh nghiệp, quốc gia) muốn tồn tại thì phải
đáp ứng được tốt nhất các như cầu và đòi hỏi của mình. Để làm được điều này, các
thực thể xã hội phải tìm mọi cách có hiệu quả nhất tác động lên các đối tượng, từ đó
mới có giải pháp sử dụng có hiệu quả đối tượng thuộc phạm vi tác động của mình.
Đây là quá trình nhận thức của con người đối với các đối tượng.
Quá trình nhận thức của con người về một đối tượng nào đó là quá trình quan
sát, tìm hiểu, giả thiết (phân tích) đối tượng đó để tìm ra các quy luật tồn tại và biến
đổi của nó (tổng hợp).
- Trước một đối tượng cần nhận biết, ban đầu con người còn chưa biết, họ phải vận
dụng tất cả các tri thức vốn có để tạm hiểu đối tượng, tức là để tổng hợp sơ lược các
hiểu biết về đối tượng.

3 tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai
Footer Page - Footer Page - kho luan van - tai lieu - 123doc-


luan van thac si - luan van thac si kinh te - luan an tien - luan van 14 of 95.

- Tiếp đó con người phải tiến hành quá trình phân tích, đó là thao tác trí tuệ diễn ra
trong đầu của người nghiên cứu (chủ thể tư duy), nhằm tách ra từ đối tượng những
đặc điểm, thuộc tính bộ phân, những mối liênhê ̣ và quan hệ giữa chúng để nhận thức


đối tượng thông thường có rất nhiều nét đặc trưng (dấu hiệu) nhưng thực tế người ta
chỉ lựa chọn một số hữu hạn các dấu hiệu tiêu biểu. Tiếp đó người ta tìm trong các
dấu hiệu trên các thành phần quan trọng nhất tương ứng với các thuộc tính cơ bản
nhất của đối tượng cho bởi các thông số. Các thuộc tính khi có thể đo lường được thì
gọi là các thuộc tính định lượng, khi không thể đo lường được thì gọi là các thuộc tính
định danh và được nhận các giá trị trong không gian độ đo µ. Từ các kết quả cho bởi
không gian độ đo µ, ứng dụng quy tắc phân loại f đối tượng sẽ được phân loại hoàn
toàn thành các lớp được biểu diễn trong không gian Euclide là Xj với:
(1.1)
Các lớp Xj thành một phân hoạch φ(X) cho ta cách nhận dạng các đối tượng.
1.1.1.2. Phân loại dạng
Dạng có thể chia thành các loại khác nhau tùy theo tiêu thức và thủ tục được sử
dụng để phân loại.
- Theo tính chất của đối tƣợng nghiên cứu, dạng được chia thành ba loại: dạng
hệ thống có nhiều người (Một doanh nghiệp, một lớp người, một quốc gia, một khối
nước, nhân loại…), dạng không có con người và dạng một người (nhân dạng).
- Theo tính chất vật lí của đối tƣợng nghiên cứu, dạng chia thành: dạng vật
(doanh nghiệp, nhà nước, thiết bị, chữ viết, âm thanh) và dạng người.
- Theo công cụ để nhận dạng, dạng chia thành: dạng nhận theo ngôn ngữ “tắt
mở” và dạng nhận theo các ngôn ngữ khác. Ngôn ngữ “tắt mở” hoặc ngôn ngữ “0 1”
hay ngôn ngữ “âm dương” là ngôn ngữ mà các giác quan con người thường sử dụng
để nhận biết đối tượng. Từ sự nhận viết của các giác quan, các tín hiệu nhận biết tắt
mở được thông báo về hệ thần kinh trung ương và con người nhận thức được đối
tượng. Trong 5 giác quan của con người, giác quan thị giác được sử dụng nhiều nhất.
Nhiều nhà nghiên cứu đã kết luận: 80% lượng thông tin con người thu nhận được từ
thế giới bên ngoài là nhờ thị giác. Dạng nhận được bằng ngôn ngữ tắt mở thường

5 tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai
Footer Page - Footer Page - kho luan van - tai lieu - 123doc-

.

Vấn đề chủ yếu là thiết kế một hệ thống ho ̣c thuâ ̣t có thể đối sánh đối tượng trong ảnh
với mẫu chuẩn và quyết định gán cho chúng vào một lớp . Việc đối sánh nhờ vào các

6 tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai
Footer Page - Footer Page - kho luan van - tai lieu - 123doc-


luan van thac si - luan van thac si kinh te - luan an tien - luan van 17 of 95.

phương thức ra quyết định dựa trên một công cụ gọi là hàm phân lớp hay hàm ra
quyết định
Học không giám sát:Kỹ thuật học này phải tự định ra các lớp khác nhau và
xác định các tham số đặc trưng cơ bản cho từng lớp . Học không có thày đương nhiên
là khó khăn hơn . Một mặt , do số lớp không được biết trước , mặt khác những đặc
trưng của các đố i tươ ̣ng cũng không biết trước. Kỹ thuật này nhằm tiến hành mọi cách
gộp nhóm có thể và chọn lựa phương pháp tố t nhấ t có thể

. Bắt đầu từ tập dữ liệu ,

nhiều thủ tục xử lí khác nhau nhằm phân lớp và nâng cấp dần để đạt được phương
pháp phân lớp chính xác nhất.
Nhìn chung, dù là mô hình nào và kỹ thuật nhận dạng ra sao, một hệ thống nhận
dạng có thể tóm tắt theo sơ đồ sau:

Đối tượng

Tiền xử lý


tính, xử lý ảnh và đồ hoạ đó phát triển một cách mạnh mẽ và có nhiều ứng dụng thực
tế trong cuộc sống . Xử lý ảnh và đồ hoạ cũng đóng một vai trò vô cùng quan trọng
trong tương tác người máy.
Quá trình xử lý ảnh được xem như quá trình thao tác với ảnh đầu vào nhằm đưa
ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể ta ̣o nên một
ảnh có chấ t lươ ̣ng tố t hơn.

Ảnh
“Tốt hơn”
XỬ LÝ ẢNH

Ảnh

Kết luận

Hình1.2. Quá trình xử lí ảnh
Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh như đặc trưng cường
độ sáng hay một dấu hiệu nào đó tại một vị trí nào đó của đối tượng trong không gian
và nó cũng có thể đươ ̣c coi như một hàm n b iến P(c1, c2,..., cn). Do đó, ảnh trong xử lý
ảnh có thể xem như ảnh n chiều.
Sơ đồ tổng quát của một hệ thống xử lý ảnh:

8 tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai
Footer Page - Footer Page - kho luan van - tai lieu - 123doc-


luan van thac si - luan van thac si kinh te - luan an tien - luan van 19 of 95.
Hệ quyết định
Thu nhận ảnh
(Scanner,


Ảnh thu nhận

Ảnh mong muốn

Hình1.4. Ảnh thu nhận và ảnh mong muốn

9 tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai
Footer Page - Footer Page - kho luan van - tai lieu - 123doc-


luan van thac si - luan van thac si kinh te - luan an tien - luan van 20 of 95.

Để khắc phục người ta sử dụng các phép chiếu, các phép chiếu thường được xây
dựng trên tập các điểm điều khiển.
Giả sử (Pi, Pi’) i = 1, n có n các tập điều khiển
Tìm hàm f: Pi  f (Pi) sao cho
n


i 1

f ( Pi )  Pi '

2

 min

(1.5)


n
n
n
 
n
2

0
a
x

b
x
y

c
x

xi xi'




1 i
1 i i
1 i


i 1
i 1

 i 1
n
n
n
 

'
0

 a1 xi   b1 y i  nc1   xi
i 1
i 1
 i 1
 c1

Giải hệ phương trình tuyến tính tìm được a1, b1, c1
Tương tự tìm được a2, b2, c2
 Xác định được hàm f
Khử nhiễu
Có 2 loại nhiễu cơ bản trong quá trình thu nhận ảnh
- Nhiều hệ thống : nhiễu có quy luật và cũng có thể khử bằng các phép
biến đổi.
10 tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai
Footer Page - Footer Page - kho luan van - tai lieu - 123doc-


luan van thac si - luan van thac si kinh te - luan an tien - luan van 21 of 95.

- Nhiễu ngẫu nhiên : nhiễu không rõ nguyên nhân và có thể khử bằ ng cách sử
dụng các phép lọc.


luan van thac si - luan van thac si kinh te - luan an tien - luan van 22 of 95.

thể (entity), được xác định một cách ang áng (vaguely defined) và có thể gán cho nó
một tên gọi nào đó”. Ví dụ mẫu có thể là ảnh của vân tay, hay ảnh của một vật nào đó
được chụp. Khi biết một mẫu nào đó, để nhận dạng hoặc phân loại mẫu đó có thể:
- Hoặc phân loại có mẫu, chẳng hạn phân tích phân biệt, trong đó mẫu đầu vào
được định danh như một thành phần của một lớp đã xác định.
- Hoặc phân loại không có mẫu: trong đó các mẫu được gán vào các lớp khác
nhau dựa trên một tiêu chuẩn đồng dạng nào đó. Các lớp này cho đến thời điểm phân
loại vẫn chưa biết hay chưa được định danh.
Hệ thống nhận dạng tự động bao gồm ba khâu tương ứng với ba giai đoạn chủ yếu
sau đây:
- Thu nhận dữ liệu và tiền xử lý dữ liê ̣u.
- Biểu diễn dữ liệu.
- Nhận dạng.
Bốn cách tiếp cận khác nhau trong lý thuyết nhận dạng bao gồ m:
- Đối sánh mẫu dựa trên các đặc trưng đã được trích chọn.
- Phân loại mẫu thố ng kê.
- Đối sánh dựa trên cấu trúc.
- Phân loại dựa trên neural network.
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 mô ̣t cách “tối ưu” do đó cần sử dụng cùng một lúc nhiều phương pháp cũng như
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 được sử dụng khi nhận
dạng và đã có những kết quả có triển vọng dựa trên các thiết kế các hệ thống lai(hybrid
system) bao gồm nhiều mô hình kết hợp.
1.3 Tổng kết
Nhận dạng là một khái niệm không hề mới trong những năm trở lại đây. Đó là
quá trình phân hoạch các đối tượng dựa trên một mô hình cụ thể nào đó. Hiện nay,
khoa học nhận dạng đang đưa ra rất nhiều ứng dụng trong thực tiễn. Qua đó cũng cho

Chương 2 của bản đồ án tập trung nghiên cứu các vấn đề của nhận dạng nói
chung, cũng như nhận dạng biển báo giao thông nói riêng , từ đó phân tích và đưa ra
các vấn đề có thể gặp phải đối với không gian bài toán nhận dạng biển báo giao
thông đang được đề cập tới . Từ đó đi ̣nh hướng cho viê ̣c giới thiê ̣u các kỹ thuật phân
lớp cụ thể sau này.
2.1. Các vấn đề học thuật
2.1.1. Xây dựng đặc trƣng cho đối tƣợng biển báo
Việc xây dựng một mô hình phù hợp cho các bài toán phân lớp nói chung và
nhận dạng nói riêng phụ thuộc vào khá nhiều yếu tố. Nhằ m tâ ̣p trung vào nội dung
chính của bản luận văn (phát hiện và nhận dạng đối tượng ảnh ), quá trình tiền xử lí
đối với ảnh đầu vào không được bàn tới quá nhiều ở đây. Về cơ bản, một hệ thống
phân lớp tốt cần đảm bảo 2 yếu tố: xây dựng được tập hợp các đặc trưng phù hợp, đủ
tính khái quát đối với đối tượng, và có một mô hình phân lớp phù hợp với tập hợp các
đặc trưng đang có. Việc giải quyết tốt 2 yếu tố này đảm bảo tính chính xác trong quá
trình làm việc của hệ thống phân lớp dữ liệu tương ứng.
Khá nhiều các phương pháp trích rút đặc trưng đã được đưa ra nghiên cứu và
phát triển, nhằm đưa ra được một tập đặc trưng có khả năng tổng quát hoá dữ liệu,
14 tieu luan - khoa luan-tai chinh ngan hang - thuong mai - tai
Footer Page - Footer Page - kho luan van - tai lieu - 123doc-


luan van thac si - luan van thac si kinh te - luan an tien - luan van 25 of 95.

đồng thời cũng đảm bảo được các đặc trưng nổi bật để có thể phân lớp dữ liệu một
cách dễ dàng. Tất nhiên, việc tiệm cận được một phương pháp có thể làm việc tốt đối
với mọi loại dữ liệu và yêu cầu phân lớp là rất khó khăn, khi mà mỗi dữ liệu đều có
những đặc trưng riêng biệt. Việc bài toán nhận dạng biển báo đã được nghiên cứu và
phát triển một thời gian, một phần nào đó giúp cho việc lựa chọn phương pháp trích
rút hợp lí đối với đối tượng chữ viết có thêm nhiều góc nhìn khác nhau.
Việc lựa chọn tập các đặc trưng, nhằm biểu diễn đối tượng đối với các dữ liệu