Chương 1 TỔNG QUAN 1. ĐỀ TÀI “TĂNG TỐC QUÁ TRÌNH PHÁT HIỆN VÀ PHÂN LOẠI PHƯƠNG TIỆN GIAO THÔNG BẰNG GPU“ 1. TỔNG QUAN Đề tài được chia làm hai giai đoạn chính: Giai đoạn 1: Hiện thực giải thuật nhằm phát hiện và phân loại giao thông Giai đoạn 2: Tăng tốc giải thuật bằng GPU Trong đó, các giải thuật được lựa chọn và hiện thực ở giai đoạn 1 sẽ ảnh hưởng đến giai đoạn 2. Yêu cầu đặt ra là giải thuật phải có khả năng tăng tốc bằng GPU.
Trong lĩnh vực thị giác máy tính, quá trình phát hiện và phân loại phương tiện giao thông không phải là mới, đã có nhiều giải thuật được đề xuất. Tuy nhiên, các giải thuật chỉ có thể áp dụng với một hoặc một vài tập dữ liệu đầu vào nhất định, với dữ liệu là giao thông ở Việt Nam thì các giải pháp hiện có vẫn chưa thể giải quyết được bài toán. Một thách thức khác của đề tài là lựa chọn đặc trưng của đối tượng xe nhằm phát hiện và phân loại. Có rất nhiều đặc trưng có thể áp dụng như các đặc trưng toàn cục: màu sắc, độ lớn, khung xe…hoặc các đặc trưng cục bộ như SIFT, SURF, Histogram of Gradient…tuy nhiên, việc kết hợp giữa các đặc trưng trên nhằm đáp ứng tương đương với hệ thống thị giác của con người là chưa thể.
Đa phần các giải pháp hiện có tìm cách kết hợp các đặc trưng dựa trên mô hình lý thuyết thống kê, đánh trọng số các loại đặc trưng, tuy nhiên các giải pháp trên vẫn chỉ có thể áp dụng cho một tập dữ liệu cố định. Nhằm lựa chọn các giải thuật thích hợp, các mô hình giải thuật hiện tại có thể phân loại dựa trên hai tiêu chí: Độ chính xác và Tốc độ. Như vậy sẽ có tổng cộng 4 nhóm giải thuật: 3 Độ Chính Xác Tốc Độ Giải Thuật Nhóm 1 Cao Cao Nhóm 2 Cao Thấp Nhóm 3 Thấp Cao Nhóm 4 Thấp Thấp Rõ ràng, các giải thuật thuộc nhóm 1 là lý tưởng, tuy nhiên hiện tại vẫn chưa có mô hình đáp ứng được. Ngược lại, các giải thuật ở nhóm 4 không thể ứng dụng thực tế.
Vấn đề còn lại là lựa chọn các giải thuật nằm trong nhóm 2 và nhóm 3. Đối với các giải thuật thuộc nhóm 3, với độ chính xác thấp, nhưng tốc độ cao thì việc tăng tốc sẽ không có ý nghĩa thực tế (do không thay đổi được độ chính xác). Vì vậy, đề tài sẽ tìm kiếm và lựa chọn các giải thuật thuộc nhóm 2, các giải thuật có độ chính xác cao nhưng tốc độ còn thấp để thực hiện Lập trình bằng GPU là mô hình SIMT (đơn chỉ lệnh, đa luồng) vì vậy, các giải thuật lựa chọn cũng phải thoả mãn tiêu chí này. Với các ràng buộc và yêu cầu trên, trong khuôn khổ đề tài, phương pháp đề xuất kết hợp một loạt các giải thuật chính như Gaussian Mixture Model, Optical Flow, Dense SIFT, Bag of Word kết hợp với các giải thuật hỗ trợ như K-Mean, MeanShift nhằm giải quyết bài toán 4 Chương 2 CƠ SỞ LÝ THUYẾT 2.
RÚT TRÍCH ĐẶC TRƯNG 2. SIFT Một cách trực quan, giải thuật SIFT (Scale Invariant Feature Transform) mô phỏng lại hệ thống thị giác con người. Khi càng di chuyển đến gần một vật thể cần quan sát, con người sẽ càng nhìn vật thể rõ ràng hơn và phát hiện một số điểm đặc biệt trên vật thể. Các điểm đặc biệt này có thể giúp con người phân biệt vật thể này với vật thể khác, ngoài ra các điểm đặc biệt này sẽ không mất đi khi càng tiến đến gần đến vật thể kể từ thời điểm phát hiện ra nó.
Giải thuật SIFT được mô tả theo ngôn ngữ toán học như sau Đầu vào của giải thuật SIFT là một tập N2 điểm ảnh của một khung hình có kích thước NxN. Chỉ có một tỉ lệ nhỏ 0 < α < 1 của các điểm ảnh này có thể trở thành điểm cực trị. Ngoài ra, trong số các điểm cực trị, chỉ có một tỉ lệ nhỏ các điểm là có thể trở thành điểm trọng yếu (keypoint). Gọi tỉ lệ các điểm trọng yếu này là 0 < β < 1.
Như vậy, với một khung hình NxN, sẽ có α β N2 điểm trọng yếu. Ngoài ra, hướng của tập N2 điểm sẽ được kiểm tra lần lượt, nhằm tìm kiếm các điểm có độ lớn đáng kể, các điểm này sẽ được thêm vào tập các điểm trọng yếu. Gọi tỉ lệ các điểm được thêm vào là 0 < γ < 1, tổng số điểm trọng yếu được thêm vào là γN2. Sau khi tìm được các điểm trọng yếu, các điểm này sẽ được tính toán đặc tả (descriptor) nhằm tạo thành các vector đặc trưng.
Tổng số vector đặc trưng của giải thuật SIFT là (αβ + γ)N2 cho một khung hình NxN với α, β, γ, là các tỉ lệ đặc trưng. Giải thuật SIFT được tiến hành qua các phân đoạn chính 5 Hình 1 - Các bước chính của giải thuật SIFT 2. Phát hiện cực trị Ở bước đầu tiên, giải thuật xác định các điểm bất biến đối với các phép biến đổi quay, dịch chuyển và ít bị ảnh hưởng bởi nhiễu và một số biến dạng nhỏ. Phát hiện các điểm này có thể được tiến hành bằng cách tìm kiếm các đặc trưng ổn định cho tất các các mức scale.
Giai đoạn này, giải thuật sẽ lần lượt tính các mức scale trong không gian Gaussian Scale, ma trận kết quả của DoG (Difference of Gaussian) và cực trị thông qua nhiều octave. Giá trị cực trị của DoG sẽ đảm bảo tính bất biến với phép biến đổi co giãn cục bộ 6 Gọi I là một khung ảnh kích thước NxN, với 0 ≤ x,y < N, hàm Gaussian rời !! ! !! ! ! rạc, 2 chiều là 𝐺 𝑥, 𝑦, 𝜎 = 𝑒 !!! , Scale của khung ảnh I được định nghĩa: !!! ! 𝐿 𝜎 = {𝐺 𝑥, 𝑦, 𝜎 ∗ 𝐼 𝑥, 𝑦 : 0 ≤ 𝑥, 𝑦 < N} Trong đó, “*” là phép toán tổng chập (convolution), I(x, y) là giá trị của pixel tại điểm x, y Một cách tổng quát, mức scale thứ k của khung ảnh ( k ≥ 1) được định nghĩa: 𝐿 𝑘𝜎 = {𝐺 𝑥, 𝑦, 𝑘𝜎 ∗ 𝐼 𝑥, 𝑦 : 0 ≤ 𝑥, 𝑦 < N} Với mỗi điểm ảnh I(x, y), scale được tính bằng cách áp dụng phép nhân của ma trận Gaussian kích thước w x w đặt ở vị trí pixel I. Chẳng hạn, giả sử điểm I(x, y) là điểm trung tâm của cửa sổ 5x5.001*ix+2,x+2 Ix-2, y-2 Ix-2, y-1 Ix-2, y Ix-2, y+1 Ix-2, y+2 0.001 Ix-1, y-2 Ix-1, y-1 Ix-1, y Ix-1, y+1 Ix-1, y+2 0.003 Ix, y-2 Ix, y-1 Ix, y Ix, y+1 Ix, y+2 0.004 Ix+1, y-2 Ix+1, y- Ix+1, y Ix+1, y+1 Ix+1, 1 y+2 0.003 Ix+2, y-2 Ix+2, y- Ix+2, y Ix+2, y+1 Ix+2, 0.001 1 y+2 7 Hình 2 - Áp dụng Gaussian cửa sổ 5x5 cho một pixel Thông thường, giá trị w sẽ được chọn là số lẻ, như vậy các điểm ảnh xung quanh !!! !!! I(x, y) là I(x + u, y + v) với − ≤ 𝑢, 𝑣 ≤ . Đối với toàn bộ NxN điểm ảnh, độ phức tạp sẽ là O(w2N2) Xét s ≥1 là một số nguyên, tổng số scale là k = 21/s.
Xét σ0 là giá trị khởi tạo cho σ cho bộ lọc Gaussian. Định nghĩa σi = kiσ cho 0 ≤ i < s+ 3; 𝐿!! = 𝐼 là ảnh gốc ban đầu. Với mỗi thành phần I(x, y), 𝐿!!!! = G(x, y, σi)* 𝐿!! 𝑥, 𝑦 với 0 ≤ i < s+3. Giải thuật tính tuần tự các mức Scale !! !!! !!! !!! !!!!! !!!!! 𝐿!! 𝐿!! 𝐿!! … 𝐿!!!! 𝐿!!!! 𝐿!!!! (1.1) được gọi là một mức octave.
Có thể hiểu toàn bộ quá trình trên nhằm tạo ra một loạt khung ảnh được làm mờ ở các mức độ khác nhau và toàn bộ các khung ảnh này được gọi là một mức octave Hình 3 - Không gian Scale – 1rd Octave 8 Ở bước tiếp theo, giải thuật sẽ được lặp lại nhưng ở độ phân giải khác của khung ảnh. Độ phân giải của một khung ảnh có thể giảm theo cơ số 2 bằng cách lấy mẫu ở mọi điểm ảnh của khung ảnh theo mẫu checkerboard. Dãy Octave được tính ở độ phân giải ban đầu gọi là mức 0, dãy Octave ở mức j tương ứng là ! !! ! !!! ! !!! !!! ! !!!!! ! !!!!! ! 𝐿! 𝐿! 𝐿! … 𝐿!!! 𝐿!!! 𝐿!!! (1.2) với 0 < j ≤ 𝑠-1, 𝑠 là tổng số octave cần tính (mỗi octave tương ứng với một độ phân giải khác nhau) Độ phức tạp cho quá trình tính s + 3 mức scales của khung ảnh trong một octave là O(N2w2(s+3)). Do đó, với tổng số 𝑠 octaves, mỗi octave ở độ phân giải j cần !! !!! ! ! 𝑂( !! 𝑤 ! 𝑠), độ phức tạp là 𝑂 ! !!! !! 𝑤 𝑠 = 𝑂(𝑁 ! 𝑤𝑠) ! Như vậy, ta có tổng cộng (s+3) mức scales 𝐿! cho 𝑠 octaves, với 0 ≤ i < s+3, 0 ≤ j < 𝑠.
Với octave thứ j cố định, định nghĩa sai khác Gaussian thứ i ở octave j là ! ! ! 𝐷! = 𝐷!!! − 𝐷! 9 Hình 4 - Sai khác Gaussian ! !! Tổng số mức scales ở octave j là N/2j x N/2j. Như vậy tìm 𝐷! cần !! phép toán trừ (!!!)! ! ma trận, với tất cả s+2 phép trừ ma trận Gaussian ở octave j yêu cầu hay !! !! ! ! !!! !! 𝑂( !! ). Độ phức tạp trên tổng số 𝑠 octaves là 𝑂 !!! !! = 𝑂(𝑠𝑁 ! ) 10 ! ! ! Sắp sếp kết quả 3 ma trận 𝐷!!! , 𝐷! , 𝐷!!! thành 3 lớp (Hình 5), mỗi thành phần ! ! 𝐷! (𝑥, 𝑦) có tổng cộng 26 giá trị xung quanh. Định nghĩa 𝐷! (𝑥, 𝑦) là một điểm cực ! trị nếu và chỉ nếu 𝐷! (𝑥, 𝑦) mang giá trị lớn hơn hoặc nhỏ hơn nhiều so với toàn bộ 26 điểm lân cận Hình 5 - Điểm cực trị Phát hiện điểm cực trị cần 26 phép trừ ma trận với độ phức tạp là hằng số.
Xét tất cả ! !! các điểm ảnh thành phần của 𝐷! ở octave thứ j, cần 𝑂( !! ). Với toàn bộ 𝑠 octaves, ! !!! (!!!) ! cần 𝑂 !!! = 𝑂(𝑠𝑁 ! ) !! 2. Phát hiện điểm trọng yếu Với tổng số αN2 điểm cực trị phát hiện ở trên, tồn tại một số điểm nằm dọc theo cạnh của ảnh hoặc những điểm có độ tương phản thấp, các điểm này không ổn định trong quá trình biến đổi khung ảnh [25]. Sau khi loại bỏ các điểm này, β tỉ lệ các điểm còn lại sẽ trở thành điểm trọng yếu (αβN2 điểm).