Trần Thị Tuyết
NHẬN DẠNG BIỂN BÁO GIAO THÔNG ĐƯỜNG BỘ
Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI – 2013
2
Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: TS. NGUYỄN ĐỨC DŨNG
Phản biện 1: …………………………………………………………
Phản biện 2: …………………………………………………………
Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ….. giờ ……. ngày ….. tháng ….. năm …………
Có thể tìm hiểu luận văn tại: – Thư viện của Học viện Công nghệ Bưu chính Viễn thông
1
MỞ ĐẦU Lý do chọn đề tài Ngày nay, khi tốc độ phát triển kinh tế, công nghiệp và dịch vụ ngày càng tăng, nhu cầu giao thông đi lại của con người càng trở thành vấn đề quan trọng. Tuy nhiên, Việt Nam giao thông luôn là một vấn đề nóng của xã hội. Từ quy mô phát triển đến cơ sở hạ tầng. Ý thức tự giác và cảnh giác của người tham gia giao thông tại Việt Nam lại chưa cao. Theo số liệu thống kê của Ủy ban An toàn giao thông Quốc gia, trong 9 tháng đầu năm 2013, cả nước đã xảy ra 23.619 vụ tai nạn, làm chết 6.908 người và 25.002 người bị thương. Từ tình hình thực tế giao thông tại Việt Nam, có nhiều nguyên nhân gây ra các vụ tai nạn giao thông đường bộ, nhưng phần lớn là do tài xế không làm chủ tốc độ, không quan sát hoặc không kịp nhận ra các loại biển báo và tín hiệu giao thông. Đây là những nguy hiểm đã được cảnh báo trước nhưng tai nạn vẫn thường xuyên xảy ra, gây không ít thiệt hại về tính mạng và tài sản của người tham gia giao thông.
2
Cho đến nay vấn đề này được nhiều nghiên cứu trên thế giới quan tâm. Nhưng những biển báo giao thông được nghiên cứu không phải dùng cho giao thông đường bộ tại Việt Nam. Trong khi đó tình hình nghiên cứu biển báo giao thông tại Việt Nam vẫn còn nhiều hạn chế và chưa đầy đủ. Vì vậy, luận văn đã chọn đề tài “Nhận dạng biển báo giao thông đường bộ” để nghiên cứu với mục đích hiểu được nền tảng công nghệ, các lý thuyết cơ bản trong bài toán xử lý ảnh và áp dụng trong việc nhận dạng biển báo giao thông một cách tự động. Mục đích nghiên cứu –
Nghiên cứu tìm hiểu các phương pháp nhận
dạng biển báo giao thông và cài đặt thử nghiệm chương trình phát hiện và nhận dạng biển báo giao thông đường bộ từ hình ảnh tĩnh và video thu về, sau đó hiển thị thông tin cảnh báo dưới dạng hình ảnh. Đối tượng và phạm vi nghiên cứu Biển báo giao thông đường bộ ở Việt Nam. Phương pháp nghiên cứu
3
– Tìm hiểu bộ ảnh biển báo giao thông đường bộ tại Việt Nam, thu thập hình ảnh, video biển báo giao thông từ các nguồn khác nhau (google image, tự chụp, …) – Tìm hiểu phương pháp phát hiện biển báo giao thông dựa trên trích chọn đặc trưng Haar-like kết hợp với bộ tăng tốc Adaboost. – Tìm hiểu phương pháp nhận dạng biển báo giao thông đường bộ: Luận văn có sử dụng phương pháp phân tích thành phần chính Principal Components Analysis (PCA) và máy vector hỗ trợ Support Vector Machine (SVM) để nhận dạng biển báo giao thông. – Cài đặt chương trình thử nghiệm và đánh giá kết quả nhận dạng. Bố cục luận văn Luận văn chia thành ba phần chính: Phần mở đầu, phần nội dung và phần kết luận. Phần mở đầu: Nêu lên lý do chọn đề tài, đối tượng và phạm vi nghiên cứu và phương pháp nghiên cứu của đề tài. Phần nội dung:
4
Chương 1: Tổng quan về xử lý ảnh. Chương này trình bày những lý thuyết cơ bản về xử lý ảnh, tổng quát các phương pháp phổ biến trong quá trình phát hiện và nhận dạng đối tượng. Chương 2: Phát hiện và nhận dạng ảnh. Phát biểu bài toán nhận dạng biển báo giao thông và trình bày nền tảng công nghệ, chi tiết các thuật toán hỗ trợ trong việc phát hiện và nhận dạng biển báo bao gồm: Trích chọn đặc trưng Haar-like, bộ tăng tốc Adaboost, phân tích thành phần chính PCA và bộ phân lớp SVM. Chương 3: Cài đặt và thử nghiệm. Tác giả sử dụng ngôn ngữ VC++ MFC của bộ Visual Studio 2008, và bộ thư viện xử lý ảnh mã nguồn mở OpenCV của Intel để xây dựng chương trình. Sau đó phân tích và đánh giá kết quả nhận dạng. Cuối cùng là Phần kết luận và hướng phát triển của đề tài.
5
Chương 1. TỔNG QUAN VỀ XỬ LÝ ẢNH 1.1 Một số khái niệm trong xử lý ảnh 1.1.1 Xử lý ảnh là gì? 1.1.2 Một số khái niệm 1.2 Một số phương pháp biểu diễn ảnh 1.2.1 Mã loạt dài 1.2.2 Mã xích 1.2.3 Mã tứ phân. 1.3 Các phương pháp phát hiện biên ảnh 1.3.1 Một số khái niệm 1.3.2 Kỹ thuật phát hiện biên trực tiếp 1.3.2.1 Phương pháp Gradient 1.3.2.2 Kỹ thuật phát hiện biên Laplace 1.3.2.3 Kỹ thuật phát hiện biên theo phương pháp Canny 1.3.3 Phát hiện biên gián tiếp 1.3.4 Phân vùng ảnh 1.3.4.1 Phân vùng ảnh theo ngưỡng biên độ 1.3.4.2 Phân vùng ảnh theo vùng đồng nhất 1.3.4.3 Phân vùng ảnh theo kết cấu bề mặt 1.4 Phương pháp trích chọn đặc trưng ảnh Khái niệm. Có thể hiểu trích chọn đặc trưng là quá trình rút trích các đặc trưng đại diện cho ảnh, được gọi là các chi tiết đặc trưng. Các chi tiết đặc trưng này yêu cầu phải có
6
thuộc tính là khả năng bảo toàn tính đặc thù để phân biệt có trong ảnh, đồng thời phải có tính cô đọng, hỗ trợ chặt chẽ cho quá trình đối sánh và ít bị tác động bởi nhiễu hoặc sai lệch trong ảnh. Ngoài ra, còn yêu cầu phải dễ tính toán. 1.4.1 Đặc trưng Haar-like. 1.4.2 Đặc trưng Histogram of Oriented Gradients (HOG) 1.5 Các phương pháp nhận dạng đối tượng
1.5.1 Phương pháp Neural Networks (NN) Mạng noron nhân tạo (Artifical Neural Networks) mô phỏng lại mạng noron sinh học là một cấu trúc khối gồm các đơn vị tính toán đơn giản được liên kết chặt chẽ với nhau trong đó các liên kết giữa các noron quyết định chức năng của mạng. Về cơ bản mạng Neural là một mạng các phần tử (gọi là neural) kết nối với nhau thông qua các liên kết (các liên kết này được gọi là trọng số liên kết) để thực hiện một công việc cụ thể nào đó. Khả năng xử lý của mạng neural được hình thành thông qua quá trình hiệu chỉnh trọng số liên kết giữa các neural, nói cách khác là học từ tập hợp các mẫu huấn luyện. Ưu điểm: – Dễ cài đặt cùng với khả năng học và tổng quát hoá rất cao.
7
– Tốc độ xử lý nhanh – Linh hoạt và dễ bảo trì: Nhược điểm: – Tính chậm và xác suất không cao không có quy tắc tổng quát để xác định cấu trúc mạng và các tham số học tối ưu cho một (lớp) bài toán nhất định. – Tiêu chuẩn thu thập cơ sở dữ liệu huấn luyện còn khắt khe. – Đòi hỏi thời gian xử lý cao với mạng một mạng Neural lớn.
1.5.2 Phương pháp Support Vector Machine (SVM) Cho trước một tập huấn luyện, các ảnh được biểu diễn dưới dạng vector. Trong không gian vector, mỗi vertor được biểu diễn bởi một điểm. Phương pháp SVM sẽ tìm một siêu phẳng quyết định để phân chia không gian vector thành hai lớp. Chất lượng của siêu phẳng này phụ thuộc vào khoảng cách giữa các vector, tức là phụ thuộc vào các đặc trưng của ảnh. Ưu điểm: – Cho kết quả nhận dạng với độ chính xác cao – Bài toán huấn luyện SVM thực chất là bài toán QP trên một tập lồi, do đó SVM luôn có nghiệm toàn cục và duy nhất, đây chính là điểm khác biệt rõ nhất giữa
8
SVM so với phương pháp mạng Neural, vì mạng Neural vốn tồn tại nhiều điểm cực trị địa phương. Nhược điểm:
– Hạn chế lớn nhất của SVM là tốc độ
phân lớp rất chậm, tùy thuộc vào số lượng các véc tơ hỗ trợ. – Giai đoạn huấn luyện SVM đòi hỏi bộ nhớ rất
lớn, do đó các bài toán huấn luyện với số lượng mẫu lớn sẽ gặp trở ngại trong vấn đề lưu trữ. Hiệu quả phân lớp của SVM phụ thuộc vào hai yếu tố: giải bài toán QP và lựa chọn hàm nhân. 1.5.3 Phương pháp Linear Discriminant Analysis Mục đích của LDA – Linear Discriminant
Analysis là tìm cách phân loại các đối tượng (người, sự vật,…) vào một trong hai hay nhiều lớp đã được xác định trước dựa vào các đặt trưng (feature) dùng để mô tả đối tượng (ví dụ như các đặc trưng dùng để mô tả đối tượng khách hàng là giới tính, tuổi, nghề nghiệp, thu nhập,…) Ưu điểm:
– Dễ dàng hơn để đào tạo, phương sai thấp,
hiệu quả hơn nếu mô hình là chính xác. – LDA làm việc tốt khi số mẫu là lớn.
9
Nhược điểm: – LDA gặp phải vấn đề khi tổng số mẫu huấn luyện ít hơn so với kích thước của không gian đặc trưng.
1.5.4 Phương pháp Naive Bayes (NB) Ý tưởng cơ bản của cách tiếp cận NB là sử dụng xác suất có điều kiện. Ưu điểm: Cho độ chính xác cao khi kết hợp với các phương pháp khác. Nhược điểm: – Chi phí thời gian để đếm mẫu – Phải kết hợp với các phương pháp khác
1.5.5 Phương pháp Principal Component Analysis PCA (Principal Component Analysis) là một thuật toán được sử dụng để tạo ra một ảnh mới từ ảnh ban đầu. Ảnh mới này có kích thước nhỏ hơn nhiều so với ảnh ban đầu nhưng vẫn mang những đặc trưng cơ bản nhất của ảnh cần nhận dạng. Nói một cách ngắn gọn, mục tiêu của PCA là tìm một không gian mới (với số chiều nhỏ hơn không gian cũ). Các trục tọa độ trong không gian mới được xây dựng sao cho trên mỗi trục, độ biến thiên của dữ liệu trên đó là lớn nhất có thể. Ưu điểm:
10
– Tìm được các đặc tính tiêu biểu của đối tượng cần nhận dạng mà không cần phải xác định các thành phần và mối quan hệ giữa các thành phần đó. – Thuật toán có thể thức hiện tốt với các ảnh có độ phân giải cao, do PCA sẽ thu gọn ảnh thành một ảnh có kích thước nhỏ hơn. – PCA có thể kết hợp với các phương pháp khác để mang lại hiệu quả nhận dạng cao hơn Nhược điểm: – PCA chỉ làm việc với dữ liệu numeric – PCA rất nhạy với nhiễu. – Không phù hợp với các mô hình phi tuyến do PCA hoàn toàn dựa trên các biến đổi tuyến tính. – Cài đặt thuật toán phức tạp Kết luận chương 1
11
Hình 2.1 Đặc trưng Haar-like cơ bản Đặc trưng haar-like được mở rộng ra và được chia thành 3 tập đặc trưng như sau:
12
(1). Đặc trưng theo cạnh
(2). Đặc trưng theo đường
(3). Đặc trưng xung quanh tâm Hinh 2.2 Đặc trưng Haar-like mở rộng Dựa theo các đặc trưng trên, giá trị của đặc trưng Haar-like: f(x) = Tổng
vùng đen(các
mức xám của pixel) –
Tổng vùng trắng(các mức xám của pixel) “Integral Image” (ảnh chia nhỏ) Integral Image tại vị trí (x,y) bằng tổng các giá trị điểm ảnh phía trên và bên trái của (x,y). Tổng các điểm ảnh trong một hình chữ nhật (kể cả trường hợp xoay 45º) bất kì đều có thể được tính nhanh dựa trên integral image tại 4 đỉnh của nó : Sum (D ) = 4 + 1 – (2 + 3)
P1
C
B
P2
P4
Hình 2.4 Ví dụ cách tính nhanh tổng các điểm ảnh của vùng D trên ảnh 2.5 Phát hiện biển báo giao thông 2.5.1 Tiếp cận Boosting Nguyên lý cơ bản của boosting là sự kết hợp các phân lớp yếu (weak classification) thành một phân lớp mạnh (strong classification). Trong đó, phân lớp yếu là các bộ phân loại đơn giản chỉ cần có độ chính xác trên 50%. Bằng cách này, chúng ta nói bộ phân loại đã được “boost”. 2.5.2 Thuật toán Adaboost Thuật toán AdaBoost tuân theo các bước sau: [4] 1. Cho một tập gồm n mẫu có đánh dấu (x1, y1), (x2, y2),… (xn, yn) với xk ∈ (xk1, xk2, … , xkm) là vector đặc trưng và yk ∈ (-1, 1) là nhãn của mẫu (1 ứng với object, -1 ứng với background). 2. Khởi tạo trọng số ban đầu cho tất cả các mẫu:
14
với m là số mẫu đúng (ứng với object và y = 1) và l là số mẫu sai (ứng với background và y = -1).
3. Xây dựng T phân loại yếu : Lặp t = 1, …, T. Với mỗi đặc trưng trong vector đặc trưng, xây dựng một phân loại yếu hj với ngưỡng θj và n
lỗi εj.
Chọn ra hj với εj nhỏ nhất, ta được ht:
ht : X {1, 1} Cập
wt 1,k
nhật
lại
trọng
số:
Trong đó: t
Zt: Hệ số dùng để đưa Wt+1 về đoạn [0,1] (normalization factor) T
4. Phân loại mạnh được xây dựng : H ( x) sign( t ht ( x)) t 1
15
2.6 Nhận dạng biển báo giao thông 2.6.1 Phương pháp phân tích thành phần chính PCA 2.6.1.1 Giới thiệu phương pháp PCA. 2.6.1.2 Thuật toán PCA Mục tiêu của phương pháp PCA là “giảm số chiều” của 1 tập vector sao cho vẫn đảm bảo được “tối đa thông tin quan trọng nhất” Vector x ban đầu có N chiều
Không gian N chiều với hệ cơ sở v1, v2,…,vn
Ánh xạ tuyến tính T cần tìm (phép chiếu)
Vector y chỉ còn K chiều