Exponenta Banner

assignkbest

Назначение с использованием k-лучшего глобального ближайшего соседа

Свернуть все на странице

Синтаксис

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment)
[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k)
[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k,algorithm)

Описание

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment) возвращает таблицу назначений, assignments, обнаружений треков с использованием алгоритма Йонкера-Волгенанта. Алгоритм находит глобальное решение ближайшего соседа (GNN), которое минимизирует общую стоимость назначений.

Стоимость каждого потенциального присвоения содержится в матрице затрат, costmatrix. Каждая матричная запись представляет стоимость возможных присвоений. Строки матрицы представляют дорожки, а столбцы - обнаружения. Все возможные присвоения представлены в матрице затрат. Чем ниже стоимость, тем больше вероятность выполнения задания. Каждая дорожка может быть назначена самое большее одному обнаружению, и каждое обнаружение может быть назначено самое большее одному дорожке. Если количество строк превышает количество столбцов, некоторые дорожки не назначаются. Если количество столбцов превышает количество строк, некоторые обнаружения не назначаются. Можно задать запись costmatrix на Inf запретить назначение.

costofnonassignment представляет собой стоимость оставления не назначенных треков или обнаружений. Более высокие значения увеличивают вероятность того, что каждый существующий объект назначен.

Все входы должны быть одинарной точностью или все должны быть двойной точностью.

Функция возвращает список неназначенных треков, unassignedrows, список неназначенных обнаружений, unassignedcolumns, и стоимость назначения, cost.

пример

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k)также определяет число, k, из k - самых глобальных ближайших соседних решений, которые минимизируют общую стоимость назначений. В дополнение к лучшему решению функция использует алгоритм Murty, чтобы найти оставшиеся k решений -1.

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k,algorithm) также задает алгоритм, algorithm, для поиска заданий.

Примеры

свернуть все

Открыть Live Script

Создайте матрицу затрат, содержащую запрещенные назначения. Затем используйте assignkbest функция, чтобы найти 5 лучших решений.

Настройте матрицу затрат так, чтобы она содержала некоторые запрещенные или недопустимые назначения путем вставки Inf в матрицу.

costMatrix = [10 5 8 9; 7 Inf 20 Inf; Inf 21 Inf Inf; Inf 15 17 Inf; Inf inf 16 22];
costOfNonAssignment = 100;

Найдите 5 оптимальных назначений.

[assignments,unassignedrows,unassignedcols,cost] = ...
    assignkbest(costMatrix,costOfNonAssignment,5)
assignments=5×1 cell array
    {4x2 uint32}
    {4x2 uint32}
    {4x2 uint32}
    {4x2 uint32}
    {4x2 uint32}


unassignedrows=5×1 cell array
    {[3]}
    {[3]}
    {[3]}
    {[4]}
    {[5]}


unassignedcols=5×1 cell array
    {0x1 uint32}
    {0x1 uint32}
    {0x1 uint32}
    {0x1 uint32}
    {0x1 uint32}


cost = 5×1

   147
   151
   152
   153
   154

Входные параметры

свернуть все

Матрица затрат, заданная как M -by- N матрица. M - количество дорожек, которые будут назначены, и N - количество обнаружений, которые будут назначены. Каждая запись в матрице затрат содержит стоимость дорожки и назначения обнаружения. Матрица может содержать Inf указывает, что назначение запрещено. Матрица затрат не может быть разреженной матрицей.

Типы данных: single | double

Стоимость неприсоединения, заданная как скаляр, двухэлементный вектор скаляров или двухэлементный массив ячеек векторов.

  • Когда он задан как скаляр, он представляет собой стоимость оставления треков или обнаружений неназначенными. Более высокие значения увеличивают вероятность того, что каждый объект назначен. Значение не может быть установлено на Inf.

  • Если задан как двухэлементные скаляры, первый элемент представляет собой стоимость оставления обнаружений неназначенными, а второй элемент представляет собой стоимость оставления треков неназначенными.

  • Когда задан как двухэлементная камера векторов, каждый элемент в первом векторе представляет стоимость оставления определенного обнаружения неназначенным, а каждый элемент второго вектора представляет стоимость оставления определенного трека неназначенным. Длина первого вектора равна количеству обнаружений, а длина второго вектора равна количеству дорожек.

Типы данных: single | double

Количество лучших решений, заданное в виде положительного целого числа.

Типы данных: single | double

Алгоритм назначения, заданный как 'jv' для алгоритма Йонкера-Вольгенанта, 'munkres' для алгоритма Мункреса, 'auction' для алгоритма аукциона, или 'matchpair' для алгоритма пары совпадений. Когда 'jv' выбран, функция использует эвристику, определенную в [3], чтобы улучшить эффективность алгоритма.

Пример: 'jv'

Типы данных: char | string

Выходные аргументы

свернуть все

Назначение треков обнаружениям, возвращаемое как k-element массив ячеек. k - количество лучших решений. Каждая камера содержит L матрицу i-на-2 из пар трек-индексов и присвоенных индексов обнаружения. L i - количество пар назначения в ith камера решения. Первый столбец каждой матрицы содержит индексы дорожки, а второй - присвоенные индексы обнаружения.

Индексы неназначенных треков, возвращенные как k-element массив ячеек. Каждая камера является вектором P i, где P i = M - L i - количество неназначенных строк в ith камера. Каждый элемент является индексом строки, которой не назначены столбцы. k - количество лучших решений.

Типы данных: uint32

Индексы неназначенных обнаружений, возвращенные как k-element массив ячеек. Каждая камера является вектором Q i, где Q i = M - L i - количество неназначенных обнаружений в ith камера. Каждый элемент является индексом столбца, которому не назначены строки. k - количество лучших решений.

Типы данных: uint32

Общая стоимость решений, возвращенная как k-вектор. Каждый элемент является скалярным значением, суммирующим общую стоимость решения задачи присвоения.

Типы данных: single | double

Ссылки

[1] Murty, Katta G. «Алгоритм для ранжирования всех заданий в порядке увеличения стоимости». Исследование операций 16, № 3 (1968): 682-687.

[2] Сэмюэл Блэкман и Роберт Пополи. Проект и анализ современных систем слежения, Artech House, 1999.

[3] Miller, M. L., et al. Оптимизация метода ранжированного назначения Мерти. Сделки IEEE по аэрокосмическим и электронным системам, том 33, № 3, июль 1997 года, стр. 851-62. DOI.org (Crossref), дои: 10.1109/7.599256.

Расширенные возможности

Генерация кода C/C + +
Сгенерируйте код C и C++ с помощью Coder™ MATLAB ®

.

См. также

Функции

Введенный в R2018b

Документация по Sensor Fusion and Tracking Toolbox

Поддержка