Глобальный алгоритм назначения ближайших соседей Jonker-Volgenant
[ возвращает таблицу assignments,unassignedrows,unassignedcolumns] = assignjv(costmatrix,costofnonassignment)assignments обнаружений на дорожки с помощью алгоритма Йонкера-Волгенанта. Алгоритм JV находит оптимальное решение глобальной задачи назначения ближайшего соседа (GNN), находя набор назначений, которые минимизируют общую стоимость назначений. Алгоритм Йонкера-Волгенанта решает назначение GNN в двух фазах: начинается с алгоритма аукциона и заканчивается алгоритмом кратчайшего пути Дейкстры.
Стоимость каждого потенциального присвоения содержится в матрице затрат, costmatrix. Каждая матричная запись представляет стоимость возможных присвоений. Строки матрицы представляют дорожки, а столбцы - обнаружения. Все возможные присвоения представлены в матрице затрат. Чем ниже стоимость, тем больше вероятность выполнения задания. Каждая дорожка может быть назначена самое большее одному обнаружению, и каждое обнаружение может быть назначено самое большее одному дорожке. Если количество строк превышает количество столбцов, некоторые дорожки не назначаются. Если количество столбцов превышает количество строк, некоторые обнаружения не назначаются. Можно задать запись costmatrix на Inf запретить назначение.
costofnonassignment представляет собой стоимость оставления не назначенных треков или обнаружений. Более высокие значения увеличивают вероятность того, что каждый существующий объект назначен.
Функция возвращает список неназначенных треков, unassignedrows, и список неназначенных обнаружений, unassignedcolumns.
Используйте assignjv, чтобы назначить три обнаружения двум трекам.
Начните с двух предсказанных местоположений дорожки в координатах x-y.
tracks = [1,1; 2,2];
Предположим, что получены три обнаружения. По крайней мере, одно обнаружение не будет назначено.
dets = [1.1, 1.1; 2.1, 2.1; 1.5, 3];
Создайте матрицу затрат путем определения стоимости назначения обнаружения дорожке в качестве евклидова расстояния между ними. Установите стоимость неприсоединения равной 0,2.
for i = size(tracks,1):-1:1 delta = dets - tracks(i,:); costMatrix(i,:) = sqrt(sum(delta .^ 2,2)); end costofnonassignment = 0.2;
Используйте алгоритм аукциона, чтобы назначить обнаружения трекам.
[assignments, unassignedTracks, unassignedDetections] = ...
assignjv(costMatrix,costofnonassignment);Просмотр присвоений.
disp(assignments)
1 1 2 2
Показать, что нет неназначенных треков.
disp(unassignedTracks)
Отображение неназначенных обнаружений.
disp(unassignedDetections)
3
Постройте график обнаружения для отслеживания назначений.
plot(tracks(:, 1), tracks(:, 2), '*', dets(:, 1), dets(:, 2), 'o') hold on xlim([0,4]) ylim([0,4]) legend('tracks', 'detections') assignStr = strsplit(num2str(1:size(assignments,1))); text(tracks(assignments(:,1),1) + 0.1, ... tracks(assignments(:,1),2) - 0.1, assignStr); text(dets(assignments(:,2),1) + 0.1, ... dets(assignments(:,2),2) - 0.1, assignStr); text(dets(unassignedDetections(:),1) + 0.1, ... dets(unassignedDetections(:),2) + 0.1, 'unassigned');
Трек к назначениям обнаружения:
Обнаружение 1 назначается дорожке 1.
Обнаружение 2 назначено дорожке 2.
Обнаружение 3 не назначено.
[1] Сэмюэл С. Блэкман и Пополи, Р. Проект и анализ современных систем слежения. Artech House: Норвуд, Массачусетс. 1999.