Распознавание картин без распознавания

Обычно распознавание чего угодно реализуется с помощью технологий компьютерного зрения и машинного обучения. Нейросети “скармливают” набор изображений, по которым она учится узнавать предметы.

Но что делать, если распознавать нужно сразу на мобильном устройстве, а дообучать модель в случае увеличения количества классов нет возможности из-за ограничений на стороне клиента? В таком случае использовать нейросеть не получится.

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

Что распознаем

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

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

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

1. Возможность легко расширять классы

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

2. Быстрая скорость распознавания

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

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

Классические алгоритмы не требуют обучения Они могут работать на гораздо менее мощном железе за счет меньшей вычислительной сложности

О ключевых точках

Основным понятием для нашего приложения в процессе распознавания являются ключевые точки.

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

Ключевые точки - характерные точки изображения, т.е. точки, которые сильнее всего отличаются от других областей. Математически ключевая точка является областью с наиболее высоким значением градиента. Например, на шахматной доске характерной точкой будет переход из черной клетки в белую. А у полностью белой доски характерных точек не будет.

Поиск ключевых точек реализован с помощью OpenCV. Используя стандартный оператор OpenCV мы также ищем производную изображения.

Внутри OpenCV есть детектор и дескриптор ключевых точек KAZE, который выполняет поиск этих самых ключевых точек, а затем для каждой точки генерирует вектор признаков. Алгоритм читает градиент вокруг этой точки во всех направлениях, и для каждого направления выдается число, которое описывает эту точку. Это и является описанием ключевой точки. Благодаря этому описанию мы можем сравнить точки между собой, сравнивая расстояние между векторами.

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

Разработка прототипа

Для проверки гипотезы об эффективности подхода с поиском ключевых точек мы разработали прототип. А чтобы клиенту было проще проверять работу алгоритма, мы создали Телеграмм-бот: клиент отправляет в чат изображение, оно отправляется на сервер, где его обрабатывает алгоритм, результат определется отправляется обратно в Телеграмм вместе с некоторыми параметрами - фото экспоната, время работы алгоритма.

Прототип позволил нам понять, что подход с ключевыми точками - не только рабочий, но и оптимальный в рамках ограничения этого проекта. Все, что нам осталось сделать на этом этапе - улучшить качество определения, которое на момент создания прототипа было в районе 60%, и сделать так, чтобы алгоритм быстро работал на мобильных устройствах.

Улучшение качества распознавания

Чтобы достичь более высокого качества определения, наша команда пробовала использовать разные детекторы и дескрипторы ключевых точек (SIFT, ORB, KAZE), перебирали их параметры, занимались предобработкой входных изображений. В итоге остановились на KAZE, как наилучшем.

Дескрипторы особых точек - алгоритмы, которые дают ключевым точкам математическое описание, т.е. вектор признаков.

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

Однако такое решение имеет в себе подвох. Из-за большого количества дубликатов ключевых точек скоринг начал работать некорректно. Проще всего объяснить что пошло не так на простом примере.

Наш датасет не сбалансирован. Один класс содержит 10 фотографий, другой - 3, третий - 15. Например, у нас есть 2 фотографии Паши в классе “Паша” и 10 фотографий Глаши в классе “Глаша”. При описываемом выше подходе, алгоритм определит ключевые точки со всех трех фотографий Паши и объединит их в одну группу, то же самое сделает с десятью фотографиями Глаши.

А теперь дадим алгоритму на вход фото Паши. Ключевые точки фотографии Паши совпадают с ключевыми точками класса “Паша”, и по идее никаких проблем с определением кто перед нами быть не должно. Алгоритм видит, например, 7 ключевых точек на фотографии, видит эти же 7 ключевых точек в классе “Паша” и дает этому классу 14 баллов (ведь в классе “Паша” у нас 2 фотографии, а ключевые точки с двух фото мы объединили в одну группу, породив дубликаты). Однако так получилось, что и Глаша, и Паша - люди, и у них есть много общего: нос, глаза, рот, волосы, уши. Для алгоритма они имеют довольно много схожих ключевых точек, например, две.

Из-за выполненного ранее объединения ключевых точек разных фотографий в одну кучу, две ключевые точки Паши, схожие с ключевыми точками Глаши, дают классу “Глаша” не 2 балла, а целых 20, ведь в классе “Глаша” 10 фотографий, по две схожие ключевые точки на каждом фото. Таким образом побеждает класс “Глаша” из-за большого количества дубликатов.

Решить эту проблему получилось, когда мы заменили группы похожих ключевых точек одним цетроидом - усредненным вектором признаков. После этих изменений мы достигли 87-88% качества. Мы планировали поднять качество выше 88%, путем определения требований к датасету.

Ускорение поиска расстояния

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

Для ускорения работы мы заменили этот алгоритм на HNSW - приближенный поиск дистанции. Данный алгоритм строит граф, в котором строится пространство с иерархией. После внедрения HNSW скорость поиска расстояния между точками увеличилась в разы - если раньше определение занимало несколько секунд, то теперь оно занимает от 1 до 3 fps.

Определение границ экспоната

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

В рамках нашего подхода решить подобную задачу проще для “плоских” объектов, таких как картины, чем для объемных, таких как статуи. Определение границ объекта можно осуществить с помощью линейных преобразований: у нас хранятся ключевые точки и их взаимное расположение как целевого объекта, так и сохраненного в библиотеке, благодаря линейным преобразованиям мы можем вычислить насколько они отклонились.

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

Ограничения подхода

Подход распознавания изображений по ключевым точкам был выбран нами не зря - он отвечал задачам клиента и поставленным изначально ограничениям. Несмотря на то, что подход отвечал требованиям, он не лишен недостатков.

Во-первых, ограничением является сам критерий распознавания - ключевые точки. Не все объекты могут их иметь, например, “Черный квадрат” Малевича наше приложение не смогло бы определить, т.к. у картины с одним цветом характерных точек нет.

Во-вторых, не просто дать количественную оценку нашей уверенности в результате классификации.

Как считается оценка неопределенности: для каждой картины мы считаем количество точек, которые совпали. У каждой картины будет разное количество баллов - у первого класса, например, 3 точки, у второго класса - 2 точки и т.д. У какого класса больше баллов, к тому классу и относится наша картина. Когда классов очень много, в знаменатель уходит все количество баллов, в числитель - баллы победителя. Если суммировать баллы по всем кандидатам, получится, например, 100. У победителя 10 баллов, у всех остальных по 1 баллу, но если поделим 10 на 100 - получится очень низкая уверенность.

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

Разработка прототипа для музея картин

Пока проект в работе и клиент думает над реализацией, мы решили реализовать мобильный прототип для местного музея картин. Протестировали его в боевых условиях и даже сняли видео.

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