6 Tổng kết
4.11 Mơ tả việc dự đốn vị trí của một đối tượng [17]
một thời điểm thì sẽ tạo ra đường đi trên cả hai máy quay đó. Dựa vào việc biết được vùng giao của hai góc quay, khi có một khung bao đóng của một đối tượng xuất hiện ở vùng giao của máy quay một thì ta có thể chiếu khung bao đóng này xuống máy quay hai và đo độ trùng lặp với những khung bao đóng xuất hiện ở vùng giao của máy quay hai. Nếu hai khung bao đóng giữa hai máy quay có độ trùng lặp lớn thì hai truy vết ứng với hai khung bao đóng đó sẽ được ghép lại với nhau. Hình 4.13 sẽ minh họa rõ hơn về khoảng cách này.
Hai phép đo nói trên rất hợp lí và phù hợp với bài tốn truy vết trên nhiều máy quay. Tuy nhiên, để có thể dùng dược chúng thì ta phải cần dữ liệu đã được gán nhãn, cụ thể ở đây là các khung bao đóng ứng với id của từng đối tượng. Bởi vì chỉ khi có dữ liệu được dán nhãn thì chúng ta mới dùng được thuật tốn RANSAC [91] để xác định vùng giao giữa hai máy quay và tính được hai phép đo trên. Việc cần dữ liệu dán nhãn không những tốn rất nhiều công sức mà cịn khiến việc truy vết trở nên khơng tổng quát bởi vì khi ta thực hiện truy vết trên nhiều hệ thống máy quay khác nhau thì ta khơng thể nào có thể có dữ liệu đã dán nhãn trên những hệ thống này hết được. Vì vậy, bộ truy vết trong luận văn sẽ không sử dụng hai phép đo này và điều này cũng dẫn tới sự giảm độ chính xác của việc truy vết mà sẽ được trình bày rõ hơn ở phần kiểm thử mơ hình truy vết 5.4.
4.5.1 Gom cụm theo thứ bậc
Thuật toán gom cụm đề xuất là Agglomerative Hierarchical Clustering sử dụng Single Linkage, nghĩa là khoảng cách giữa hai cụm bằng với khoảng cách giữa 2 đối tượng gần nhau nhất trong 2 cụm đó. Nguyên tắc chính của giải thuật này là:
1. Đầu tiên mỗi quỹ đạo đã được truy vết sẽ là những cụm riêng biệt.
2. Sau đó, lần lượt 2 cụm có khoảng cách gần nhau nhất sẽ được gom lại và quá trình này lặp đi lặp lại tới khi khoảng cách nhỏ nhất giữa 2 cụm vượt quá một giá trị ngưỡng cho trước.
Ban đầu, khi khoảng cách giữa từng cặp quỹ đạo đường đi trong tất cả kết quả truy vết được tính dẫn tới độ phức tạp về bộ nhớ làO(n2
2). Sau đó, các giá trị khoảng cách này sẽ được thêm vào một danh sách hàng chờ có độ ưu tiên (priority queue) dựa vào cấu trúc dữ liệu Heap. Ở đây, cặp quỹ đạo đường đi nào có giá trị khoảng cách nhỏ nhất nằm ở đầu của danh sách hàng chờ sẽ bị xóa và hai quỹ đạo đó sẽ được gộp thành một cụm mới. Khoảng cách của các cụm cũ và cụm mới sẽ được tính lại và đưa vào hàng đợi ưu tiên.