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