Ứng dụng kỹ thuật học máy trong nhận dạng biển báo giao thông

You're Reading a Free Preview
Pages 7 to 16 are not shown in this preview.

You're Reading a Free Preview
Pages 20 to 22 are not shown in this preview.

You're Reading a Free Preview
Pages 26 to 32 are not shown in this preview.

GIỚI THIỆU PHƯƠNG PHÁP NHẬN DẠNG BIỂN BÁO GIAO THÔNG

Khái quát phương pháp nhận dạng biển báo giao thông sử dụng trong đề tài

Từ ảnh RGB đầu vào ta xác định vùng ảnh chứa biển báo giao thông nguy hiểm và tách vùng ảnh này ra khỏi ảnh đầu vào. Sau đó trích riêng biển báo và so sánh với cơ sở dữ liệu mẫu trong bộ phân loại để nhận dạng biển báo giao thông nguy hiểm.

Xác định vùng đặc trong chứa biển báo giao thông

Đặc trưng Haar-like

Đặc trưng Haar-like được sử dụng trong việc nhận dạng đối tượng trong ảnh số được phát biểu bởi Viola và Jones gồm 4 đặc trưng cơ bản để xác định một đối tượng trong ảnh. Mỗi đặc trưng Haar-like là sự kết hợp gồm 2 hoặc 3 khối chữ nhật mang giá trị “đen” hoặc “trắng”. Những khối chữ nhật này thể hiện sự liên hệ tương quan giữa các bộ phận trong ảnh mà bản thân từng giá trị pixel không thể diễn đạt được

Hình 2. 1. Đặc trưng theo cạnh

Dựa theo các đặc trưng trên, giá trị của đặc trưng Haar-like được xây dựng bởi độ chênh lệch giữa tổng các pixel của các vùng đen so với tổng các pixel của các vùng trắng.

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]

Như vậy để tính giá trị đặc trưng Haar-like cần phải thực hiện tính toán tổng các vùng pixel trên ảnh. Điều này làm cho chi phí bài toán lớn không thể đáp ứng các tính năng yêu cầu thời gian thực. Do vậy Viola và Jones đã đề xuất ra khái niệm “Integral Image” [ảnh chia nhỏ] để giảm thiểu chi phí cho bài toán tính giá trị của đặc trưng Haar-like để bài toán có thể xử lý với thời gian thực.

Tính “Integral Image” bằng cách sử dụng mảng 2 chiều với kích thước bằng kích thước của ảnh cần tính giá trị đặc trưng Haar-like. Ảnh chia nhỏ ở vị trí [x,y] được tính bằng tổng các giá trị pixel của vùng từ vị trí [0,0] đến vị trí [x-1, y-1]. Việc tính toán đơn giản là thực hiện phép cộng số nguyên nên tốc độ thực hiện được tối ưu hóa.

Hình 2. 5. Cách tính Integral Image của ảnh

Kết quả có được sau khi tính Integral Image, việc tính tổng giá trị pixel trong vùng cần tính thực hiện như sau:

Gọi vùng cần tính tổng các giá trị pixel là vùng “A4”.

P1[x1,y1] = A1;           P2[x2,y2] = A1+A2;

P3[x3,y3] = A1+A3;    P4[x4,y4] = A1+A2+A3+A4;

A4 = P4 + P1 – P2 –P3;

1. Thuật toán tăng tốc Adaboost

Thuật toán tăng tốc Adaboost là thuật toán máy học được cải tiến từ thuật toán Boosting. Với ưu điểm khả năng giải quyết bài toán nhanh chóng, cài đặt đơn giản và dễ dàng, không có các tham số để điều chỉnh và không cần tri thức về bộ học yếu do đó thuật toán tăng tốc Adaboost được sử dụng nhiều trong các ứng dụng về nhận dạng.

Boosting là kĩ thuật nâng cao độ chính xác cho các thuật toán máy học. Năm 1989, Schaire đã đưa ra các chứng minh đầu tiên về thuật toán boosting. Và một năm sau đó Freund đã phát triển thuật toán boosting một cách hiệu quả hơn rất nhiều, mặc dù vẫn còn nhiều hạn chế trong thực tế và chỉ tối ưu trong một số trường hợp. Các thực nghiệm đầu tiên với thuật toán boosting được thực hiện bởi Drucker, Schapire và Simard trong  chương trình  nhận  dạng  ký tự  quang  học [OCR_Optical  Character Recognition]. Mãi đến năm 1995 thuật toán AdaBoost mới chính thức được công bố bởi Freund và Schapire.

Nguyên lý cơ bản của thuật toán Boosting là kết hợp các   bộ phân loại yếu [weak classifiers] thành một bộ phân loại mạnh [strong classifier]. Trong đó bộ phân loại yếu là các bộ phát hiện đơ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át hiện đã được “boost”.

Xét một bài toán phát hiện 2 lớp [mẫu cần nhận dạng sẽ được phân vào 1 trong 2 lớp] với D là tập huấn luyện gồm có n mẫu. Trước tiên, chúng ta sẽ chọn ngẫu nhiên ra n1 mẫu từ tập D [n1 z1 do đó mặt siêu phẳng h2 sẽ được SVM chọn dùng làm ranh giới để tách hai bộ phân lớp. Và khoảng cách cực đại này còn được gọi là lề[margin], mặt siêu phẳng này còn được gọi là mặt

siêu phẳng lề tối đa.

Độ lớn của lề [margin] được cho như sau:

Từ phương trình trên khi thay đổi w và w0 hướng và khoảng cách từ gốc tọa
độ tới mặt siêu phẳng. Bộ phân loại SVM được định nghĩa như sau:

f[x] = sign[wTx + w0 ]

Nếu f[x] = +1 thì x thuộc về phân lớp đang cần quan tâm, và ngược lại nếu f[x]
= -1 thì x thuộc về lớp khác.

Phương pháp máy học SVM là tập các mặt siêu phẳng phụ thuộc vào các tham số w và w0. Mục tiêu của phương pháp SVM là ước lượng hai giá trị này để có thể cực đại hóa lề[margin]. Với giá trị của lề càng lớn thì mặt siêu phẳng phân lớp càng tốt.

Theo hình 2.12 thấy được với độ lớn của lề nhỏ hơn thì khả năng cho kết quả sai sẽ cao hơn.

Hình 2. 12. Ví dụ minh họa về độ lớn của lề [margin]

Nếu tập dữ liệu huấn luyện là khả tách tuyến tính ta có các ràng buộc sau:

wTxi + w0 ≥  +1 nếu yi = +1   [2. 24] wTxi + w0  ≤ -1 nếu yi = -1               

Hai mặt siêu phẳng có phương trình wTxi + w0 = ± 1 được gọi là mặt siêu phẳng hỗ trợ. Theo hình 2.11 thì mặt siêu phẳng hỗ trợ chính là những đường thẳng nằm song song với mặt siêu phẳng h1,h2.

Phương pháp có thể tìm được giá trị w và w0 để xây dựng được mặt siêu phẳng lề tối ưu là phải giải bài toán tối ưu toàn phương [Quadratic Programming].

Cực đại hóa:

Với các ràng buộc sau:

Trong đó các hệ số Lagrange

 là các biến số cần phải tối ưu hóa

Vector w sẽ được tính từ các nghiệm của bài toán toàn phương như sau:

Để xác định độ dịch w0, ta chọn xi sao cho , sau đó sử dụng điều kiện Karush-Kuhn-Tucker [KKT] như sau:

Với là những mẫu nằm gần mặt siêu phẳng nhất và được gọi là các vector hỗ trợ [Support Vector]. Theo hình 2.13 những mẫu được gọi là Support Vector là các mẫu xanh hoặc đỏ được khoanh tròn và nằm trên mặt siêu phẳng hỗ trợ [do dấu của bất đẳng thức bằng +1 nếu đây là mẫu cần quan tâm và bằng -1 với các mẫu còn lại].

Hình 2. 13. Minh họa các mẫu được gọi là Support Vector.

1. Phân lớp phi tuyến [Nonlinear classifier]

Thực tế trong trường hợp tổng quát, mặt phân hoạch có thể là một mặt phi tuyến bất kì [Hình 2.14]. Và ta chỉ cần ánh xạ vector dữ liệu vào không gian đặc trưng có số chiều cao hơn nhiều.

Ví dụ theo hình 2.14 giả sử các mẫu xi  thuộc không gian Rn, không gian này được gọi là không gian giả thiết [hypothesis space]. Để tìm mặt phi tuyến trong không gian này, ta ánh xạ các vector mẫu xi  từ Rn vào một không gian Rd có số chiều lớn hơn [d > n, d có thể bằng ∞]. Rd được gọi là không gia đặc trưng [feature space]. Sau đó

áp dụng phương pháp SVM tuyến tính để tìm ra một siêu phẳng phân hoạch trong không gian đặc trưng Rd. Siêu phẳng này sẽ là ứng với mặt phi tuyến trong không gian Rd.

Hình 2. 14. Một mặt phân chia phi tuyến có thể trở thành một siêu phẳng trong không gian lớn hơn

Trong không gian đặc trưng [feature space] này, các điểm dữ liệu trở thành khả tách tuyến tính, hoặc có thể phân tích với ít lỗi hơn so với trường hợp sử dụng không gian ban đầu. Khi đó, bài toán quy hoạch toàn phương ban đầu trở thành như sau:

Cực đại hóa:

với các ràng buộc sau:

Trong đó k là một hàm nhân [kernel function] thỏa mãn:

Với việc sử dùng hàm nhân [kernel function], thì ta không cần quan tâm về ánh xạ . Bằng cách chọn một hàm nhân phù hợp, ta sẽ xây dựng được nhiều bộ phân loại khác nhau. Ví dụ, chọn nhân đa thức dẫn đến bộ phân loại đa thức, nhân Gaussian dẫn đến bộ phân loại RBF [Radial Basis Functions][1].

CHƯƠNG 3. THIẾT KẾ VÀ XÂY DỰNG CHƯƠNG TRÌNH

1. Chức năng của chương trình

Chương trình được viết  bằng ngôn  ngữ lập trình python, cùng với sự hỗ trợ của bộ thư viện xử lý ảnh OpenCV.

                                                                                                                                                                                                                                            Chương trình được xây dựng có chức năng chính:

O Phát hiện và nhận dạng biển báo qua video clip quay sẵn với định dạng AVI hoặc mp4

                                                                                                                                                                                                                                            Ngoài ra còn có một số chức năng phụ như:

o Tạo bộ cơ sở dữ liệu cho quá trình học nhận dạng.

o Huấn luyện nhận dạng biển báo cho chương trình.

1. Xây dựng cơ sở dữ liệu ảnh biển báo

Ảnh được dùng trong quá trình huấn luyện phát hiện biển báo gồm 2 loại:

Ảnh Positive: là những ảnh có chứa đối tượng cần được phát hiện, cụ thể

là ảnh có chứa biển báo.

Ảnh Negative: là ảnh không chứa đối tượng biển báo.

Quá trình thu thập ảnh cho mục đích huấn luyện, nhóm đồng thời sử dụng nhiều phương pháp khác nhau để có được bộ dữ liệu ảnh.

Các nguồn ảnh được nhóm sử dụng:

Google image.

Ảnh trích xuất từ video clip tự quay hoặc sưu tầm từ YouTube.

Ảnh tự chụp từ thực tế.

Quá trình huấn luyện của máy học đòi hỏi hàng ngàn tấm ảnh ở những điều kiện ánh sáng, tương phản khác nhau, để tạo được bộ ảnh như vậy tốn khá nhiều thời gian nên nhóm đưa ra ý tưởng quay các đoạn video của biển báo sau đó viết một chương trình nhỏ để tách thành các frame ảnh từ đó khiến cho việc sưu tập bộ dữ liệu được nhanh chóng hơn và đặc biệt là có được những tấm ảnh với những đặc trưng đa dạng.

Từ những phương pháp trên nhóm xây dựng được bộ dữ liệu ảnh gồm xxx ảnh

 Positive và yyy ảnh Negative dùng cho việc huấn luyện máy học. Các ảnh được lưu trữ ở định dạng BMP, PPM.

1. Huấn luyện phát hiện biển báo trong ảnh

Để thực hiện quá trình huấn luyện phát hiện các biển báo trong ảnh, nhóm sử dụng thuật toán SVM

Quá trình huấn luyện trải qua 3 bước:

• Chuẩn bị dữ liệu ảnh huấn luyện.
• Lấy mẫu đối tượng từ bộ dữ liệu.
• Huấn luyện máy học.

Tập ảnh Positive có chứa đối tượng biển báo được đặt tên theo thứ tự và chép vào trong thư mục “dataset”.

Hình 3. 1. Tập ảnh Positive trong thư mục “dataset”

1. Huấn luyện nhận dạng biển báo

Quá trình huấn luyện nhận dạng biển báo sử dụng thuật toán  SVM.

Bộ ảnh dùng cho huấn luyện nhận dạng được nhóm tận dụng lại một phần ảnh đã sử dụng cho bước huấn luyện phát hiện biển báo ở trên đồng thời bổ sung thêm một số ảnh cho đa dạng. Ảnh dùng trong quá trình này cần có độ đa dạng về điều kiện môi trường, góc chụp, ánh sáng khác nhau nhằm giúp cho việc nhận dạng sau này được tốt hơn.

Bộ ảnh huấn luyện nhận dạng gồm xxx ảnh, với mỗi loại biển báo cần nhận dạng có số lượng tối thiểu là yy ảnh được lưu vào từng thư mục riêng và được đặt tên theo thứ tự.

Hình 3. 2. Một số mẫu huấn luyện nhận dạng.

Sau huấn luyện chúng ta thu được file data_svm.dat lưu trữ thông số huấn luyện như hình sau:

Sơ đồ hoạt động của chương trình

ĐÁNH GIÁ KẾT QUẢ CHƯƠNG TRÌNH

Sau khi xây dựng chương trình, nhóm thử nghiệm đánh giá chương trình ở  video clip có kích thước 640x480 pixels, mỗi clip có độ dài từ 5 đến 10 giây. Các môi trường được nhóm thử nghiệm đánh giá là:

Môi trường ánh sáng ban ngày từ 7 giờ đến 17 giờ trong điều kiện thời tiết tốt, không mưa, không bị ngược sáng, biển báo rõ ràng không bị che khuất, tốc độ xe đạt từ 35 đến 45 Km/h, đường bằng phẳng. Trong môi trường này nhóm đã sử dụng một tập dữ liệu thử gồm XX video clip để đánh giá thì kết quả thử nghiệm cho thấy tỉ lệ phát hiện được biển báo là 98,62%, tỉ lệ nhận dạng chính xác là 95,44%. Đây là môi trường được nhóm nghiên cứu đánh giá là môi trường lý tưởng để chương trình có thể phát hiện và nhận dạng với tỉ lệ chính xác cao.