Об эффективности иерархического алгоритма поиска приближенного ближайшего соседа в заданном наборе изображений

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