BoVW – незаслуженно забытый бейзлайн

Миша

Я вообще очень сильно люблю всякие классические методы CV (сейчас всё выглядит намного скучнее, везде сплошные сетки) и периодически мне приходилось использовать вот эту забавную вещь, про которую почему-то мало кто знает: bag of visual words.

Интересно это может быть по нескольким причинам:
• Быстро обучается
• Заводится на крохотных датасетах
• Даёт не самые ужасные метрики
• Не зависит от размера входного изображения (если нормализовать вектора)
• И самое важное: это какая-то необычная прикольная идея, которую можно быстро попробовать

Сразу оговорюсь: перфоманса на уровне сеток на больших датасетах ждать не стоит (иначе все бы сейчас использовали этот подход), но на маленьких может и правда неплохо работать. Например, я использовал этот подход на датасете с фотками мусора для сортировки (≈10 классов и ≈3500 картинок) и это работало лучше сеток. Ещё это неплохо работает для задачек с почерком (об этом, возможно, напишу позже).

И, наконец, про то как это варить.

Для начала нам потребуется что-то, что умеет выплёвывать кучу дескрипторов для изображения. Для кейпоинт-детектора возьмём SIFT, а для дескрипторов… да в целом какая разница, тоже возьмём SIFT.

Чтобы узнать про SIFT больше можно глянуть несколько видео из вот этого шикарного курса на ютубе или прочитать оригинальную статью.

SIFT-кейпоинты на радостном пёселе, какая прелесть :3

Натравим наш SIFT на весь датасет и запомним все дескрипторы, их будет очень много, даже для уменьшенной версии картинки с сибой ину их 171 штука. Кстати, если вы используете OpenCV, то можете смело переводить дескрипторы из float32 в uint8, будет ощутимо дешевле по памяти.
После того, как мы это сделали нужно обучить k-Means на всех дескрипторах датасета, причём с достаточно большим k (смотрите на свой датасет, конечно, но обычно работает что-то в пределах 800-5000), для этого удобно использовать minibatch версию из sklearn. Таким образом мы получим метку кластера для каждого дескриптора (и для каждого кейпоинта). На этом моменте уже можно догадаться почему метод называется Bag of Visual Words : действительно, мы просто используем метки кластеров как id слов и делаем из них BOW. После получения векторов можно делать с ними всё что захочется: tf-idf, различные нормализации (потому что количество кейпоинтов на картинке не фиксировано) и так далее. Классически на преобразованные вектора дальше натравливался SVM с какой-нибудь кастомной ядерной функцией. К счастью (или нет), мы с вами живём в 2022, поэтому можем спокойно запускать поверх свои любимые бустинги и не задумываться над сложными вещами 😉

Конечно же, эту простую идею можно сильно модифицировать. Так появились soft-BoVW и FV (вектора Фишера). Последние, кстати, были топ-1 на ImageNet до алекснета с акьюраси 50.9, что для 2011 достаточно неплохо, правда?

Расскажу только про soft-BoVW, потому что не хочу грузить математикой и далеко не самой очевидной интуицией из FV (но если всё-таки хотите – пишите в комментарии).

Что же такое soft-BoVW? Всё очень просто. Вместо того, чтобы обучать k-Means, мы обучаем GMM (которая смесь гауссиан), и для каждого дескриптора получаем не одно значение, метку кластера, а вектор, в котором каждая i-ая ячейка – это плотность i-ой компоненты.

Здесь оценивается плотность каждой из 4-х компонент GMM возле дескриптора x_t
(очевидно, что она будет больше для 4 и 1, чем для 2 и 3)

Таким образом, мы получаем вектор длины N для каждого дескриптора, где N – кол-во компонент в GMM, после чего суммируем все такие вектора для одного изображения.
Благодаря такому подходу “мусорные” кейпоинты из фона попадают далеко от центров компонент и не вносят большого веса в результирующий вектор (по крайней мере в теории). На практике же самая неудобная здесь вещь – руками писать GMM, который бы влезал в память для большого кол-ва компонент. Если вдруг соберётесь – советую инициализировать его средние с помощью k-Means.

Пока писал пост появилась пара идей что ещё можно с этим попробовать сделать:
• Okapi BM25 вместо tf-idf для наивного BoVW + сетка поверх
• Wasserstein distance для сравнения изображений после soft-BoVW