Chương 1: Giới thiệu Chương 2: Lý thuyết để xây dựng mô hình cảnh báo tai nạn cho ôtô Chương 3: Thực hiện và kết quả đạt được Chương 4: Kết luận và hướng phát triển 4 Luan van Chương 2 LÝ THUYẾT XÂY DỰNG MÔ HÌNH HỆ THỐNG CẢNH BÁO TAI NẠN CHO ÔTÔ 2.1 Lý thuyết nhận dạng đối tượng 2.1 Phương pháp dựa trên màu sắc Phương pháp này thường được sử dụng trong xác định biển báo giao thông hay các vật thể có những màu sắc đặc trưng với nguyên tắc là tìm một vùng ảnh có chứa màu sắc đặc trưng của biển báo (biển báo giao thông chủ yếu có năm màu: xanh, đỏ, vàng, trắng, và đen), dựa trên phương pháp phân ngưỡng đơn giản hoặc phân ngưỡng ảnh cao cấp. Khuyết điểm chính của phương pháp này là trong thực tế màu sắc có xu hướng không đáng tin cậy, mà phụ thuộc vào các thời điểm trong ngày, điều kiện thời tiết, bóng râm,… Không gian màu RGB (Red – Green – Blue) được đánh giá là rất nhạy cảm với ánh sáng, do đó nhiều nhà nghiên cứu đã chọn phân ngưỡng dựa trên màu sắc trong các không gian màu khác như HSV (Hue – Satuation – Value), không gian màu Lab (Lightness – a chanel (chứa giá trị màu từ Green tới Red) – b chanel (chứa giá trị màu từ Blue tới Yellow))… Trong "Color-Based Road Detection in Urban Traffic Scenes" của Y. Zhang [5] đề xuất một hệ thống thị giác màu sắc dựa trên phát hiện làn xe từ cảnh sát giao thông. Trong "Lane detection with moving vehicle in the traffic scenes" Hsu-Yung Cheng [6] sử dụng màu sắc tính năng để phát hiện dòng làn đường và sử dụng kích thước, hình dáng và chuyển động để xóa bỏ khu vực đường sai.2 Phương pháp dựa trên hình dạng Trong nhiều tài liệu được công bố đến hiện nay thì phát hiện biển báo giao thông dựa trên hình dạng cũng có nhiều nghiên cứu đem lại kết quả khả quan.
Tuy nhiên có lẽ phương pháp dựa trên hình dạng phổ biến nhất là sử dụng phép biến đổi Hough. Phép biến đổi Hough là một kĩ thuật dùng để xác định một hình dạng ngẫu nhiên 5 Luan van trong ảnh. Ý tưởng cơ bản là sử dụng một cạnh của ảnh, mỗi điểm ảnh của cạnh ảnh có khả năng là tâm của đối tượng nếu như điểm ảnh đó nằm trên biên. Kĩ thuật này sớm ra đời trong lịch sử thị giác máy tính.
Nó đã đựợc mở rộng và thay đổi với nhiều biến thể khác nhau như là: - Nghiên cứu của Loy và Barnes [7] được xem là phương pháp hiệu quả cho việc nhận dạng biển báo giao thông. Loy và Barnes đã đề xuất bộ phát hiện đa giác đều tổng quát và chỉ sử dụng nó để phát hiện biển báo giao thông. Bộ phát hiện dựa trên phép biến đổi đối xứng xuyên tâm nhanh, về mặt tổng quan nó tương tự như phép biến đổi Hough. Khuyết điểm chính của hướng tiếp cận này là bán kính của đa giác phải được biết trước, và đây là điều không dễ thực hiện.
Ở đây có thể được giải quyết bằng cách thử nhiều bán kính nhưng nó tiêu tốn quá nhiều thời gian xử lý. - Nghiên cứu của Paulo và Correia [8] dựa trên nguyên tắc tìm hình dạng đặc trưng được sử dụng là bộ phát hiện góc và sau đó giả thiết là vị trí của đa giác đều bằng cách quan sát mối liên hệ giữa các góc. Paulo và Correia xác định biển báo tam giác và tứ giác bằng cách áp dụng bộ phát hiện góc Haaris để xác định vùng đặc trưng, và sau đó tìm kiếm phần còn lại của góc trong sáu khu vực kiểm soát được định nghĩa trước đó của vùng này. Hình dạng được xác định dựa trên hình của vùng kiểm soát mà góc được tìm thấy.
- Gavrila [9] sử dụng biến đổi khoảng cách dựa trên mẫu phù hợp để xác định hình dạng. Một ý tưởng cơ bản để tìm thấy hình dạng đặc trưng là dựa trên một mẫu phù hợp (Ví dụ là một tam giác đều) so với ảnh DTs (Distance Transforms). Để tìm ra mẫu phù hợp tối ưu, sử dụng các phép biến đổi cơ bản như phép xoay, phép tỉ lệ, phép dời.3 Thuật toán Support Vector Machine (SVM) Nhận dạng đối tượng có thể sử dụng thuật toán Support Vector Machine. Support Vector Machine là phương pháp phân lớp dựa trên lý thuyết thống kê của Vapnik và Alexei Chervonenkis xây dựng vào năm 1960.
Và được sử dụng nhiều trong các ứng dụng nhận dạng chữ viết tay [10], nhận dạng khuôn mặt, phân loại tài 6 Luan van liệu, tin sinh học, … So với các phương pháp phân loại khác, khả năng phân loại của SVM là tương đương hoặc tốt hơn đáng kể. Ý tưởng của thuật toán SVM là xây dựng một mô hình để phân loại một đối tượng có thuộc hay không thuộc vào nhóm đối tượng cần quan tâm. Thuật toán SVM sẽ biểu diễn các điểm trong không gian và xác định ranh giới giữa hai nhóm đối tượng sao cho khoảng cách giữa tập dữ liệu được huấn luyện tới ranh giới là xa nhất có thể. Tiến hành xét một bài toán đơn giản là tách hai lớp với tập dữ liệu mẫu đã được huấn luyện.
Và sau đó ta có thể mở rộng phương pháp cho nhiều trường hợp tổng quát mà dữ liệu thậm chí không thể tách được phân lớp.Với xi, i = 1, 2, …, N là tập các vector đặc trưng của bộ huấn luyện X. Và nó sẽ thuộc về một trong hai lớp và được giả sử rằng tập dữ liệu sẽ được phân lớp tuyến tính. Với mục tiêu là sẽ xây dựng mặt siêu phẳng để tách chính xác các phân lớp mẫu được huấn luyện được cho bởi phương trình sau: 𝑔(𝑥) = 𝑤 𝑇 𝑥 + 𝑤0 = 0 (2.1) Trong đó w là vector trọng số, w0 là độ dịch. Với phương trình (2.
1) ta sẽ xác định được mặt siêu phẳng theo như mô tả trong hình 2. Trong trường hợp này mặt siêu phẳng là đường thẳng đậm đen liền nét tách hai phân lớp tuyến tính. Mặt siêu phẳng giúp dễ dàng tách được hai phân lớp w1 , w2. Tuy nhiên trong thực tế mặt siêu phẳng sẽ có nhiều hơn một, ở đây ta có thể dựng được hai mặt siêu phẳng được đánh dấu lần lượt là h1 và h2.
Vấn đề cần giải quyết được đặt ra là sẽ chọn mặt siêu phẳng nào để dùng làm ranh giới tách hai phân lớp dữ liệu. Trong trường hợp hình 2.1, thuật toán SVM sẽ xác định mặt siêu phẳng dùng để tách phân lớp dựa theo khoảng cách cực đại giữa hai mẫu dữ liệu đã được huấn luyện. 1 có thể dễ dàng thấy được khoảng cách do đó mặt siêu phẳng 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ề, mặt siêu phẳng này còn được gọi là mặt siêu phẳng lề tối đa.
7 Luan van Hình 2.1: Tách hai phân lớp tuyến tính với một mặt siêu phẳng Độ lớn của lề (margin) được cho như sau: 1 1 2 ‖𝑤‖ + ‖𝑤‖ = ‖𝑤‖ (2.2) Từ phương trình (2.2) 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 wT x w0 (2.3) 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ề.
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.2, cho 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.2: Tách hai phân lớp tuyến tính với hai mặt siêu phẳng 8 Luan van Nếu tập dữ liệu huấn luyện là khả tách tuyến tính thì ta có các ràng buộc sau: wT xi w0 1 if yi 1 (2.4) wT xi w0 1 if yi 1 (2.5) Hai mặt siêu phẳng có phương trình wT xi w0 1 được gọi là mặt siêu phẳng hỗ trợ. 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 (hình 2.3: Ví dụ minh họa về độ lớn của lề Cực đại hóa: 1 2 y y x x N N N T i 1 i i 1 j 1 i j i j i j (2.6) Với các ràng buộc sau: i 0 (2.8) Trong đó các hệ số Lagrange i , i 1, 2, , N 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: w i 1 i yi xi N (2.9) Để xác định được độ dịch w0 ta chọn xi sao cho i 0 , sau đó sử dụng điều kiện Karush-Kuhn-Tucker như sau: 9 Luan van i yi wT xi w0 1 0 (2.10) Với i 0 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ợ.4, 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).4: Minh họa các mẫu được gọi là Support Vector 2.4 Trích xuất đặc trưng bằng Histogram of gradient (HOG) 2.1 Giới thiệu Được đề xuất bởi Bill Triggs và Navel Dalal vào năm 2005 tại viện nghiên cứu INRIA. Ý tưởng chính trong đặc trưng HOG là hình dạng và trạng thái của vật có thể được đặc trưng bằng sự phân bố về cường độ gradient (insensity gradients) và của các hướng biên (edge direction).
Toán tử HOG được thực hiện bằng cách chia nhỏ bức ảnh thành nhiều vùng nhỏ khác nhau, được gọi là cells. Histogram về các hướng của gradients sẽ được tính cho mỗi điểm nằm trong cell. Kết hợp các histogram của từng cell này lại thì sẽ có được biểu diễn bằng histogram của bức ảnh ban đầu. Một cách để tăng cường hiệu năng nhận dạng, người ta có thể tính một ngưỡng cường độ gradient cho một vùng lớn của ảnh (blocks), sau đó sử dụng giá trị này để chuẩn hóa cho các cell trong blocks.
Kết quả cho bước chuẩn hóa này có dạng là vector đặc trưng và dễ dàng thay đổi khi điều kiện ánh sáng thay đổi.