Время прочтения: 4 мин.

ORB – бесплатная, быстрая и эффективная альтернатива алгоритмам обнаружения ключевых точек SIFT и SURF. Алгоритм не патентован, а значит, его использование в любых проектах не ограничивается. Входит в состав opencv.

Для задачи поиска изображений по фрагменту на Python необходимы библиотеки numpy и opencv.

Загрузка изображений и перевод в монохром:

query_img = cv2.imread('query.jpg')
original_img = cv2.imread('original.jpg') query_img_bw = cv2.cvtColor(query_img, cv2.IMREAD_GRAYSCALE)
original_img_bw = cv2.cvtColor(original_img, cv2.IMREAD_GRAYSCALE)

Поиск ключевых точек и дескрипторов:

orb = cv2.ORB_create()
queryKP, queryDes = orb.detectAndCompute(query_img_bw,None)
trainKP, trainDes = orb.detectAndCompute(original_img_bw,None)

Сравнение дескрипторов ключевых точек и сортировка результатов по расстоянию Хамминга:

matcher = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
matches = matcher.match(queryDes,trainDes)
matches = sorted(matches, key = lambda x:x.distance)

matches будет содержать массивы объектов – результатов сравнения дескрипторов. Для каждого такого массива атрибут distance будет содержать значение расстояния Хэмминга.

Иллюстрация сравнения:

final_img = cv2.drawMatches(query_img, queryKP, 
                            original_img, trainKP, matches[:20],None)
   
final_img = cv2.resize(final_img, (1000,650))

Отображение результата, отрисованы и сопоставлены первые 20 ключевых точек:

cv2.imshow("Matches", final_img)
cv2.waitKey()
Результат работы алгоритма

Для поиска исходного изображения фрагмента среди множества изображений предлагается:

  1. Создать список с результатами сравнения для каждого изображения.
  2. Отсортировать результаты сравнения (то есть, каждый элемент списка) по расстоянию Хэмминга.
  3. Для каждого элемента списка брать сумму его первых пяти (или больше, но эмпирическим путём было установлено, что для большинства случаев достаточно пяти) расстояний Хэмминга. Элемент с наименьшей суммой и будет результатом сравнения с искомым изображением.

При искажении изображения, в зависимости от способа искажения, качество работы алгоритма может сильно пострадать, например:

Результат работы алгоритма с искажением изображения для поиска (поворот)
Результат работы алгоритма с искажением изображения для поиска (наклон, вращение)
Результат работы алгоритма с искажением изображения для поиска (наклон, вращение) и обрезкой исходного изображения
Результат работы алгоритма с искажением исходного изображения (уменьшение разрешения до 30% от начального)
Результат работы алгоритма с искажением изображения для поиска (повышение яркости)
Результат работы алгоритма с искажением изображения для поиска (повышение яркости) и обрезкой исходного изображения
Результат работы алгоритма с искажением изображения для поиска (обращение цветов)

Как видно из примеров, наибольшее влияние на работу алгоритма оказывает обращение цветов изображения. Это происходит из-за того, что, так как алгоритм работает с монохромными изображениями, ключевые точки содержат в себе пиксели определённой яркости. И, если цвета обращены, то, в том же месте изображения, где ранее была ключевая точка, будут пиксели с другими характеристиками.

Также, стоит отметить, что, даже при условии уменьшения количества совпадений ключевых точек при искажении искомого изображения, расстояние Хэмминга найденных верно совпадающих точек будет минимальным, что позволит успешно применять алгоритм даже при наклонах и/или поворотах изображения, применяя метод, описанный выше.

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