Глобальный алгоритм назначения ближайшего соседа Munkres
[ возвращает таблицу assignments,unassignedrows,unassignedcolumns] = assignmunkres(costmatrix,costofnonassignment)assignments обнаружения на трассах с использованием алгоритма Манкреса. Алгоритм Манкра получает оптимальное решение глобальной задачи назначения ближайшего соседа (GNN). Оптимальное решение минимизирует общую стоимость назначений.
Стоимость каждого потенциального назначения содержится в матрице затрат, costmatrix. Каждая запись матрицы представляет стоимость возможных назначений. Строки матрицы представляют дорожки, а столбцы представляют обнаружения. Все возможные присвоения представлены в матрице затрат. Чем ниже стоимость, тем больше вероятность выполнения назначения. Каждая дорожка может быть назначена максимум одному обнаружению, и каждая дорожка может быть назначена максимум одному обнаружению. Если число строк больше количества столбцов, некоторые дорожки не назначаются. Если число столбцов превышает число строк, некоторые обнаруженные элементы не назначаются. Можно задать запись costmatrix кому Inf запретить назначение.
costofnonassignment представляет собой стоимость оставления дорожек или обнаружений без назначения. Более высокие значения увеличивают вероятность назначения каждого существующего объекта.
Функция возвращает список неназначенных дорожек, unassignedrowsи список неназначенных обнаружений, unassignedcolumns
Использовать assignMunkres назначение трех обнаружений двум дорожкам.
Начните с двух предсказанных местоположений дорожки в координатах 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] = ...
assignmunkres(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.