Иерархический алгоритм поиска приближенного ближайшего соседа в пространстве пирамидальных представлений изображений

Abstract

Предлагается алгоритм поиска приближенного ближайшего соседа к предъявляемому изображению в пространстве пирамидальных представлений с нарастающей размерностью. Алгоритм обеспечивает логарифмический порядок вычислительной сложности по размерности исходных изображений, но сохраняет линейный порядок сложности по мощности набора данных. Приводятся эмпирические распределения погрешностей поиска относительно ближайшего соседа и численные оценки вычислительной сложности алгоритма для поиска изображений рукописных цифр из базы данных MNIST и для координатной привязки зашумленных изображений к аэрокосмической карте местности из сетевого сервиса Google Maps. Возможно понижение линейного порядка сложности поиска по мощности набора данных за счет предварительного отбора изображений на решающем дереве в пространстве представлений малой размерности.