Глобальный алгоритм назначения ближайшего соседа Jonker-Volgenant
[ возвращает таблицу assignments,unassignedrows,unassignedcolumns] = assignjv(costmatrix,costofnonassignment)assignments обнаружений на трассах по алгоритму Йонкера-Волгенера. Алгоритм JV находит оптимальное решение проблемы назначения глобального ближайшего соседа (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] Сэмюэл С. Блэкман и Пополи, Р. Дизайн и анализ современных систем слежения. Дом Артека: Норвуд, Массачусетс. 1999.