Глобальный алгоритм назначения ближайших соседей 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] Сэмюэл С. Блэкман и Пополи, Р. Проект и анализ современных систем слежения. Artech House: Норвуд, Массачусетс. 1999.