Theo Dõi Đối Tượng Dựa Trên Giải Thuật Di Truyền và Tối Ưu Hoá Bầy Đàn

Ý tưởng về Giải thuật di truyền (GA) xuất hiện từ những năm 50-60 của thế kỷ 20, với tiên phong là Fraser. John Henry Holland là người triển khai ý tưởng này, và năm 1975, ông công bố nền tảng toán học của GA trong cuốn sách "Adaptation in Natural and Artificial System". GA mô phỏng cơ chế chọn lọc tiến hóa trong tự nhiên. Trong mỗi thế hệ, một tập hợp các cá thể mới được tạo ra bằng cách lai ghép các cá thể thích nghi nhất từ thế hệ trước, kết hợp với đột biến ngẫu nhiên. GA có ứng dụng rộng rãi trong nhiều lĩnh vực như tối ưu hóa, học máy, và giải quyết các bài toán phức tạp.

Tối Ưu Hóa Bầy Đàn (PSO) là một thuật toán metaheuristic, lấy cảm hứng từ hành vi xã hội của chim hoặc cá. PSO sử dụng một quần thể các hạt, mỗi hạt đại diện cho một giải pháp tiềm năng cho bài toán tối ưu hóa. Mỗi hạt di chuyển trong không gian tìm kiếm, chịu ảnh hưởng bởi vị trí tốt nhất mà nó đã tìm thấy (pbest) và vị trí tốt nhất mà toàn bộ quần thể đã tìm thấy (gbest). Bằng cách này, các hạt chia sẻ thông tin và hướng tới vùng không gian tìm kiếm có khả năng chứa giải pháp tối ưu. PSO có ưu điểm là đơn giản, dễ cài đặt và có thể tìm kiếm các giải pháp tốt trong thời gian ngắn. Đây là một công cụ mạnh mẽ trong nhiều bài toán thực tế.

Việc phát hiện đối tượng chuyển động có thể được thực hiện bằng nhiều phương pháp khác nhau. Alper Yilmaz, Omar Javed và Mubarak Shah đã phân loại các hướng tiếp cận này thành: phát hiện điểm quan trọng, phân đoạn ảnh, mô hình nền và phân loại có giám sát. Mô hình nền (background modeling) là một phương pháp phổ biến, xây dựng mô hình về khung cảnh tĩnh và sau đó phát hiện các thay đổi để xác định đối tượng chuyển động. Việc lựa chọn phương pháp phù hợp phụ thuộc vào đặc điểm của video và yêu cầu về độ chính xác, tốc độ.

Các phương pháp theo dõi truyền thống thường gặp phải các hạn chế khi đối diện với các điều kiện phức tạp. Chẳng hạn, các phương pháp dựa trên mô hình nền có thể gặp khó khăn khi ánh sáng thay đổi đột ngột hoặc khi có sự xuất hiện của các đối tượng mới trong nền. Các phương pháp dựa trên đặc trưng có thể bị ảnh hưởng bởi sự thay đổi hình dạng của đối tượng hoặc khi đối tượng bị che khuất một phần. Việc lựa chọn và kết hợp các phương pháp theo dõi khác nhau có thể giúp cải thiện độ tin cậy và độ chính xác của hệ thống.

Các thông số của bài toán tìm kiếm phải được mã hoá thành một chuỗi hữu hạn các ký tự trên một tập hữu hạn các ký tự. Chuỗi này tương tự như các chuỗi gen của các cơ thể sinh vật. Có rất nhiều cách để mã hóa tập thông số. Một cách đơn giản là chúng ta có thể mã hoá thành các chuỗi bit trên tập ký tự {0, 1}. Mỗi một chuỗi đại diện cho một điểm tìm kiếm trong không gian. GA xuất phát với một quần thể các chuỗi được khởi tạo một cách ngẫu nhiên sau đó sẽ sản sinh các quần thể tiếp theo thông qua việc sử dụng lựa chọn ngẫu nhiên như một công cụ.

Hàm mục tiêu (fitness function) đóng vai trò quan trọng trong việc đánh giá chất lượng của mỗi cá thể trong quần thể GA. Hàm mục tiêu cần phải phản ánh chính xác mục tiêu của bài toán, trong trường hợp này là tối ưu hóa độ chính xác và tốc độ phát hiện đối tượng. Hàm mục tiêu có thể được xây dựng dựa trên các độ đo như độ chính xác (precision), độ phủ (recall), và thời gian xử lý. Việc thiết kế một hàm mục tiêu phù hợp là yếu tố then chốt để GA có thể tìm ra các giải pháp tối ưu.

PSO có khả năng tìm kiếm không gian tham số hiệu quả hơn GA trong một số trường hợp. Việc sử dụng PSO để điều chỉnh các tham số quan trọng của GA như tỷ lệ lai ghép (crossover rate) và tỷ lệ đột biến (mutation rate) giúp GA thích nghi tốt hơn với bài toán cụ thể và tránh rơi vào các cực trị địa phương. PSO có thể coi như một "bộ điều khiển" cho GA, hướng dẫn quá trình tiến hóa của GA theo hướng tối ưu.

Thuật toán lai GA-PSO hoạt động bằng cách sử dụng PSO để tìm kiếm các giá trị tham số tốt nhất cho GA. Sau đó, GA sử dụng các tham số này để tiến hành quá trình tiến hóa. Quá trình này có thể được lặp lại nhiều lần, với PSO tiếp tục điều chỉnh các tham số của GA dựa trên kết quả của quá trình tiến hóa. Bằng cách này, thuật toán lai GA-PSO có thể tận dụng ưu điểm của cả hai thuật toán, cải thiện khả năng tìm kiếm và đạt được kết quả tốt hơn so với việc sử dụng GA hoặc PSO độc lập.

Dữ liệu thử nghiệm bao gồm một tập hợp các video ghi lại cảnh giao thông từ trên không bằng máy bay không người lái (UAV). Các video này chứa nhiều phương tiện giao thông khác nhau, với các điều kiện ánh sáng và góc nhìn khác nhau. Các tiêu chí đánh giá hiệu quả bao gồm độ chính xác (precision), độ phủ (recall), và thời gian xử lý trên mỗi khung hình. Các tiêu chí này được sử dụng để so sánh hiệu suất của thuật toán đề xuất với các thuật toán phát hiện đối tượng khác.

Kết quả thử nghiệm cho thấy thuật toán kết hợp GA và PSO vượt trội hơn so với các phương pháp phát hiện đối tượng truyền thống như các phương pháp dựa trên mô hình nền (background subtraction) và các phương pháp dựa trên đặc trưng (feature-based methods). Thuật toán đề xuất có độ chính xác cao hơn và khả năng xử lý tốt hơn trong các điều kiện ánh sáng và góc nhìn khác nhau. Điều này chứng tỏ tính hiệu quả của việc kết hợp GA và PSO trong bài toán phát hiện đối tượng.

Luận văn đã đóng góp vào lĩnh vực theo dõi đối tượng bằng cách đề xuất một phương pháp mới dựa trên sự kết hợp giữa GA và PSO. Phương pháp này đã được chứng minh là hiệu quả hơn so với các phương pháp truyền thống trong việc phát hiện và theo dõi đối tượng trong video. Luận văn cũng cung cấp một phân tích chi tiết về các ưu và nhược điểm của thuật toán đề xuất, cũng như các hướng phát triển nghiên cứu trong tương lai.

Trong tương lai, nghiên cứu có thể được mở rộng bằng cách áp dụng thuật toán cho các loại đối tượng khác nhau, chẳng hạn như người đi bộ hoặc động vật. Ngoài ra, việc tích hợp với các kỹ thuật học sâu (deep learning) có thể giúp cải thiện hiệu suất của thuật toán và cho phép xử lý các tình huống phức tạp hơn. Các ứng dụng thực tế tiềm năng bao gồm giám sát giao thông thông minh, hệ thống an ninh và quốc phòng, và các ứng dụng trong lĩnh vực y tế và nông nghiệp.