Однако, точность у обоих сервисов заметно снижается из-за того, что этикетка искажена цилиндрической поверхностью.
Особенно это заметно у Google Vision — любой текст за пределами центральной части этикетки практически не читается, хотя человек с легкостью его распознает. В этой статье я опишу, как обратить искажение и увеличить точность распознавания продуктов.
Прежде всего рассмотрим, что из себя представляет искажение.
Прямоугольная этикетка, будучи наклеенной на цилиндр, имеет характерную форму бочки (b на схеме выше). Кривая ABC в данном случае, в довольно хорошем приближении, — эллипс, т.к. мы видим окружность (сечение цилиндра) под углом. Множество горизонтальных линий этикетки аналогично трансформируется во множество эллипсов на фотографии.
Самое интересное, что для разворачивания этикетки, достаточно указать 6 маркеров (ABCDEF):
И используя их, построить полную сетку поверхности:
Имея сетку поверхности, мы можем развернуть каждую плитку по отдельности, и получить исходную поверхность:
Код библиотеки доступен на гитхабе. Удобство этого метода в то, что входные параметры для обратного преобразования — визуально определяемые характеристики этикетки (углы и верхняя, нижняя точки), что позволяет полностью автоматизировать процесс.
Следующая часть посвящена определению маркеров. Рабочий код доступен только частично в ветке на гитхабе, т.к. реально работающее решение покрыто хаками и шаманством, так что выкладывать в гитхаб такую жесть просто не позволяет совесть.
Этап первый — конвертируем изображение в черно-белый вариант.
Затем нужно получить контуры бутылки с этикеткой. Для этого мы используем трансформацию sobel. Если вкратце, то этот фильтр сначала размывает изображение, а затем вычитает его из исходного. В итоге равномерные области остаются темными, а края (изменения) — светлыми.
Следующее, что нужно сделать — это определить две наиболее заметные вертикальные линии, которые, если повезет, являются краями бутылки. В данном случае это так и есть, но если фотографировать бутылку, стоящую рядом с другими бутылками, то это уже не так.
Чтобы определить эти линии, используем преобразование Хафа. Суть методики в том, что берем множество линий, идущих через весь экран, и считаем среднее значение пикселей (к примеру, берем линии, идущие с верхней части картинки в нижнюю часть). Эти значения переносим на новую координатную плоскость и получаем что-то вроде тепловой карты. На этой тепловой карте ищем два экстремума — они и есть боковые линии.
На схеме ниже видно, как левая линия переходит в точку на новой координатной плоскости:
С эллипсами чуть сложнее, но зная, что преобразование Хафа можно применять на любые математически заданные кривые, воспользуемся этим методом снова, но на этот раз будем искать множество кривых-эллипсов.
Но для начала нужно привести задачу к двумерному виду. Зная, что бутылка центрально симметричная, возьмем центральную ось за Y координату, а одну из сторон — за X. В качестве значений на новой координатной плоскости возьмем множество эллипсов, построенных между центральной осью и боковой стороной. Это возможно благодаря тому, что произвольная точка боковой стороны и центральной оси имеют только один способ соединения. Возможно, это не очень очевидно с первого взгляда, но куда проще для понимания, если обратиться к параметрической формуле эллипса:
x = a * cos(t)
y = b * sin(t)
Точно таким же образом найдем два искомых экстремума, которые определят два эллипса этикетки (кривые A-B, F-E). Теперь, когда у нас есть все необходимые параметры этикетки (боковые кривые, а также верхний и нижний эллипсы), мы можем применить алгоритм из первой части статьи и выполнить обратное преобразование.
Что можно улучшить. Во-первых, алгоритм не учитывает искажение перспективы самого эллипса, как следствие, боковые фрагменты этикетки растягиваются чуть сильнее, чем следует. Чтобы внести поправку, нужно знать реальный угол обзора камеры, либо, хотя бы, использовать наиболее типичный для телефона (можно подобрать эмпирически).
Во-вторых, преобразование Хафа довольно неустойчиво работает в сложных условиях — например, когда в кадр попадают рядом стоящие бутылки, и края интересующей бутылки могут определиться неправильно.
В третьих, если этикетка не прямоугольной формы (к примеру, эллиптической), то маркеры будут определены неправильно, и трансформация только сильнее исказит изображение.
На практике, куда интереснее использовать нейронную сеть для определения маркеров, т.к. ее можно тренировать, используя и сложные примеры, чтобы, как минимум, алгоритм не выполнял траснсформацию, если маркеры невозможно определить. Но пока я еще не пробовал применять нейронку для этой задачи, так что, возможно, это будет тема отдельной статьи :)
Комментарии (42)
Tyusha
23.09.2018 19:06+1Неплохо. Несколько замечаний.
1). Не надо усложнять задачу нейронной сетью. Сейчас анализ изображений и нейронная сеть стали синонимами, но в узких задачах это не нужно. Не стоит заморачиваться отсеиванием пейзажа, который может давать мешающие контуры. Пользователь вашей программы заинтересован сосканировать этикетку, и у него есть несколько попыток, если что-то не получилось. Другое дело, если бы вы работали с единственной фотографией, которую невозможно переснять.
2). Я вижу гораздо больше проблем для этикеток вида 1.allegroimg.com/s1440/01c82d/96505f864bb09b4139713eeb3cb1, где присутствуют прямоугольники или же прямые линии в рисунке на самой этикетке.
3). Я бы предложила иной алгоритм для вашей задачи. Попросить пользователя снять видео или 2-3 фото, проворачивая бутылку. Далее вы находите ключевые точки, и зная, что значительная их часть (кроме фоновой обстановки) находится на цилиндре, вычисляете координатную сетку. Такому алгоритму будет всё равно, какой формы этикетка, и что на ней нарисовано.krabdb
23.09.2018 22:31+2Как постоянный пользователь vivino, покупающий вино каждый день, могу отметить, что ваш п.3 не очень удобен. Предложение снимать бутылку вина с разных ракурсов приводит к необходимости брать бутылку с полки. Обычно в процессе обсуждения с кавистом отбираю для себя несколько вариантов и сразу снимаю их на полке/в шкафу. Как вы представляете себе отбор из 10 бутылок, когда каждую необходимо снять, потом одной рукой держать, а второй снимать?
Kesha_kh
24.09.2018 00:04Поддерживаю, особенно если учесть что съемка зачастую происходит после употребления содержимого бутылки
Nepherhotep Автор
23.09.2018 23:31+1Я бы не сказал, что здесь будет усложнение нейросетью — как раз наобарот, если задача включает слишком много дополнительных условий и исключений, то это подходящая задача для нейронки. А с точки зрения пользователя, он не станет постоянно переснимать, а просто проигнорирует фичу, либо заминусует приложение.
Nepherhotep Автор
23.09.2018 23:432). Я вижу гораздо больше проблем для этикеток вида 1.allegroimg.com/s1440/01c82d/96505f864bb09b4139713eeb3cb1, где присутствуют прямоугольники или же прямые линии в рисунке на самой этикетке.
Обычно более длинная линия определяется лучше, чем более контрастная, но короткая. Тем не менее, такие этикетки действительно определяются не так хорошо. Еще есть очень распространенная ситуация, когда этикетка наклеена не по всей ширине бутылки, и тогда края ее растягиваются слишком сильно (хотя трасформированая этикетка все-равно лучше читается, чем оригинальная).Tyusha
24.09.2018 01:15Преобразование Хафа ничего не знает про длину линий. Большая яркость линии для Хафа всё равно что большая длина.
x67
24.09.2018 01:56+2- Во главе всех задач стоит пользователь. И если вы создаете продукт который должен быть лучшим, чтобы быть успешным (а агрегаторы и сервисы для обмена опытом, которым относится Вивино относятся именно к таким продуктам), то ваш совет очень вреден. Именно заморочиться стоит, потому что несколько попыток — плохой ux, особенно учитывая, что есть еще миллион причин, по которым что то может пойти не так, например плохая связь в магазине или слишком широкий асортимент.
- А можно предложить пользователю написать все данные руками и отправить по электронной почте — тогда даже приложение делать не придется
К слову, вивино очень хорошо и очень быстро распознает этикетки в последнее время, чему я несказанно радуюсь, будучи в магазине.
Nepherhotep Автор
24.09.2018 05:06Во главе всех задач стоит пользователь. И если вы создаете продукт который должен быть лучшим, чтобы быть успешным (а агрегаторы и сервисы для обмена опытом, которым относится Вивино относятся именно к таким продуктам), то ваш совет очень вреден. Именно заморочиться стоит, потому что несколько попыток — плохой ux, особенно учитывая, что есть еще миллион причин, по которым что то может пойти не так, например плохая связь в магазине или слишком широкий асортимент.
Да, в идеале сканирование этикеток должно быть таким же, как и баркодов — держишь камеру, а когда продукт распознан, то экран сам перключит на результат. На практике, можно использовать сервис распознавания картинок vuforia — он примерно так и работает — шлет поток изображений на сервер в real-time, пока не распознает продукт с нужной степенью вероятности. Но мы от vuforia отказались из-за кривого REST API на добавление таргетов в базу и немилосердного ценника при большой базе продуктов.
Сейчас используем tineye, но он, к сожалению, работает по принципу запрос-ответ, поэтому realtime распознавания не поддерживается (если только не слать пачками запросы на сервис, но т.к. биллинг идет на каждый запрос, то получится весьма дорого). Так что функциональностью пришлось пожертвовать в угоду ценника — сейчас получается 1 цент на запрос, при этом база продуктов практически неограничена (на практике — это около 300к вин).Tyusha
24.09.2018 14:54держишь камеру, а когда продукт распознан, то экран сам перключит на результат
Я это и имела ввиду. Просьба пользователя повернуть бутылку при этом не такая уж и сложная.
А попробуйте прямо на клиенте распознавать. Тот алгоритм, который сейчас у вас, мне кажется, должен неплохо шевелиться и на смартфоне.
Alex_ME
23.09.2018 19:41Что если применить поиск ключевых точек, например FAST найдет углы, скорее всего это будут края этикетки. Еще как-то отсеять точки, найденные в других местах, параметры покрутить…
Nepherhotep Автор
23.09.2018 23:38Нужен метод, как распознать среди всего многообразия нужные фичи, я не сильно представляю, какие методики для этого применять.
Kwent
24.09.2018 13:00Мы решали похожу задачу — поиск картины по фото пользователя (250к картин, время обработки запроса ~ 1 сек), думаю, метод к вам вполне применим, вот даже пару статей написали: habr.com/company/singularis/blog/421187
Вам добавить поверх распознавание текста, которое у вас уже есть, и вообще конфетка.
алгоритм не учитывает искажение перспективы самого эллипса
Может не понял, а в чем проблема взять точки ACFD, сказать, что они прямоугольник (для большинства этикеток это так), и сделать обратное перспективное преобразование на основе этого, эллипсы волшебным образом разве не исправятся тоже?Nepherhotep Автор
24.09.2018 18:19Да, если бы мы делали свой собственный поиск картинки вместо tineye, то возможно смогли бы сделать процесс распознавания куда более интерактивным. Но как обычно — пока мажорными фичами остаются закругленные кнопочки в корзине товаров (грубо говоря), такие фичи лежат на полке и ждут своего времени :)
На счет обратного перспективного преобразования — он работает для прямоугольника, а здесь целая сетка прямоугольников, и у каждой ячейки этикетки — свои параметры этого преобразования.Kwent
24.09.2018 18:28А вы случайно не знаете где достать базу винных этикеток? :)
На счет обратного перспективного преобразования — он работает для прямоугольника, а здесь целая сетка прямоугольников, и у каждой ячейки этикетки — свои параметры этого преобразования.
Просто вы там писали про угол наклона камеры, а если исправить общее искажение (бутылка была не под 90 градусов к камере), то его влияние нивелируется.Nepherhotep Автор
24.09.2018 18:48+1Перспективное искажение эллипсов будет в любом случае, т.к. разные части этикетки имет разное расстояние — центральная часть чуть ближе. На практике, точки A, C, D, F — это не крайние точки, а лучи по касательной от глаза наблюдателя, но по большому счету, этими искажениями можно пренебречь :)
Базу этикеток (примерно 50к продуктов) можно достать, к примеру, здесь — api.wine.com/wiki
Качество многих картинок, правда, не очень, но для распознавания хватает :)
furtaev
23.09.2018 19:44А что за приложение-то? Самое главное и не написали.
0o0
23.09.2018 22:10vivino
вторая строчкаNepherhotep Автор
23.09.2018 22:36Нет, не vivino, написал двусмысленно. Приложение — интернет магазин для продажи вин в США. Название не пишу, так как приложения нацелены на локального пользователя.
Nepherhotep Автор
23.09.2018 22:40Приложение сильно нацелено на локального пользователя, поэтому не пишу название. А так — интернет магазин для продажи вин.
lolhunter
24.09.2018 09:10А есть какой-нибудь интерфейс?
У нас похожая задача — с картинок бутылок делать разверстку.
Указать точки вообще не проблема — проблема именно разворачивать картинку руками.Nepherhotep Автор
24.09.2018 11:31А что такое разверстка бутылки? Это как этикетка, только вся поверхность, включая стекло?
lolhunter
24.09.2018 15:40Да. Текстура на 3д модель Основная проблема — этикетка.
Nepherhotep Автор
24.09.2018 16:49Речь идет о том, чтобы натянуть текстуру на 3д модель? Или получить текстуру с бутылки?
Если натянуть текстуру — то это суперстандартная задача из 3д моделирования.
А чтобы получить текстуру — то можете сделать интерфейс, в котором указать 6 ключевых точек руками, а затем вызвать функцию ниже:
unwrapper = LabelUnwrapper(src_image=imcv, percent_points=points) dst_image = unwrapper.unwrap()
где imcv — это numpy массив изображения, а percent_points — координаты точек в процентах от размера изображения (если удобнее, то можно использовать pixel_points, чтобы указывать координаты в пикселях, см github.com/Nepherhotep/unwrap_labels/blob/master/unwrap.py#L17)
barabanus
24.09.2018 12:20Машинное обучение не нужно там, где можно написать алгоритм. Вы же не будете писать нейронку, которая сортирует массив?
Получение градиента изображения — хорошо. Нахождение линий цилиндра — тоже, хотя надо написать свое преобразование Хафа, поскольку в имплементации OpenCV есть два дефекта: он не взвешивает точки по силе градиента (т.е. для него пиксели бинарны — или ноль, или не ноль) и не возвращает аккумулятор. Имея аккумулятор можно, например, брать в анализ только самые сильные линии. Можно размывать (не забывая про wrap around) по rho, чтобы получить самые сильные толстые линии. Правда, на Питоне его не напишешь, слишком медленный язык, разве что на Cython.
Как альтернатива, можно использовать LSD детектор (в том же OpenCV), он быстрый и хорошо находит фрагменты линии. Далее их можно соединять и получать длинные отрезки.
Следующий момент — поскольку у нас уже есть две линии, то можно их преобразовать, чтобы сделать их параллельными. Это в том числе упростит поиск эллипсов.
Еще вариант — собрать точки градиента и рассмотреть задачу как задачу оптимизации модели цилиндра под перспективными искажениями, как это делается в фотограмметрии.
А вообще классная задача, такие приятно решать.Kwent
24.09.2018 13:22+1Машинное обучение не нужно там, где можно написать алгоритм
Везде можно написать алгоритм => машинное обучение не нужно?
Видите ли, мне кажется, что у вас не совсем правильное понимание машинного обучения.
Вот, например:
Получение градиента изображения — хорошо. Нахождение линий цилиндра — тоже, хотя надо написать свое преобразование Хафа
Свертки в процессе обучения построят свое преобразование, которое намного лучше будет решать конкретно эту задачу. Все аналитические преобразования по сути частные случаи того, что сеть может построить сама (за редкими исключениями). И как правило, качество будет лучше.
Еще вы почему-то не замечаете, что основную работу делают Google и Tineye, вы думаете, они работают на аналитических алгоритмах?
Машинное обучение на текущем этапе лучший способ решить подобные задачи, смиритесь и используйте это, а не противьтесь. Аналитика — это подбор методов и параметров силами человека, ML — силами машины.
Правда, на Питоне его не напишешь, слишком медленный язык, разве что на Cython.
Не уверен, но думаю тот же Numpy не сильно медленней будет, в задачах CV слухи о низкой производительности питона в большинстве случаев слухи, так как очень много самых разных производительных библиотек, где питон дергает только методы, которые чаще всего на C/C++.barabanus
24.09.2018 13:41Дело в том, что здесь у нас строгая математическая модель цилиндра и строгая математическая модель проекции цилиндра на плоскость. Зачем обучать нейронную сеть, тратить ресурсы, память, если вся необходимая информация у нас уже есть? Грубо говоря, массив надо просто отсортировать. А для машинного обучения, чтобы модель обнаружила нужные свертки, надо еще предоставить миллион изображений под разными углами, и все ради чего, ради нескольких формул, которым она обучится, но которые, при этом, были известны априори?
Это похоже на случай с простой задачей на собеседовании, когда надо вывести, какие числа от одного до ста делятся на пять, какие на семь, а какие и на пять, и на семь. Конечно, можно построить модель перцептрона, но зачем? Нейронки хороши там, где модель данных неизвестна или не может быть строго сформулирована. Применение нейронки в таких задачах скорее выдает необразованность специалиста в этой области.
Что касается производительности Python в задачах CV, то если дергать только стандартные методы, то все ок. В компьютерном зрении приходится много экспериментировать, поэтому Питон здесь хорошо работает. Но проблема Питона в том, что он осуществляет постоянную аллокацию/деаллокацию маленьких объектов, поэтому если надо делать какие-то низкоуровневые микрооперации, то Питон сильно уступает C/C++. Иногда в сотни раз! Попробуйте реализовать преобразование Хафа, чтобы это было быстро на Питоне.Kwent
24.09.2018 14:01Дело в том, что здесь у нас строгая математическая модель цилиндра и строгая математическая модель проекции цилиндра на плоскость
Тогда я вас не так понял, я про весь комплекс задач: нахождение нужных точек на этикетке, распознавание текста и самой этикетки. Исключительно для выравнивания цилиндра вопросов нет :)
то он осуществляет постоянную аллокацию/деаллокацию маленьких объектов
Ну, массивы Numpy вполне себя ведут как массивы C++ (то есть им надо заранее указать размер, их можно передавать по ссылке, переписывать значения без аллокаций и тд), так же есть все необходимые операции для работы с этими массивами. Я не спорю, что дефолтные типы данных питона (списки, словари и тд) медленные, я также не спорю, что плюсы быстрее, но при правильном использовании питона в CV он уступает в единицы раз (1,5-2), а не в сотни, а скорость разработки значительно быстрее все-таки. Поэтому для прототипирования питон лучше, в продакшене лучше переписать конечно. Если совсем заморочиться, то можно написать преобразование Хафа на PyTorch или TF и гонять их на видеокарте со скоростью звука.
А от вызова написать быстрое преобразование Хафа спешу откланяться)barabanus
24.09.2018 15:00NumPy удобен, но на каждую операцию он создает новый объект в памяти, даже если записать `a[:] = b + c`. Это приводит к поразительному количеству аллокаций/деаллокаций там, где на плюсах будет прямая работа со структурами в стеке. Это хорошо, если задачу можно векторизовать и привести к операциям на матрицах большого размера, и то — на С++ при грамотном использовании SIMD инструкций и грамотном использовании кэша получится быстрее. Но иногда процесс итеративный и нелинейный, для каждой строки матрицы данных может понадобится разное количество итераций, в итоге Python вязнет, как в болоте.
Nepherhotep Автор
24.09.2018 18:24+2На практике, numpy работает достаточно быстро, а если есть бутылочное горлышко — то можно (и нужно) оптимизировать только его (как я и делал для преобразования Хафа github.com/Nepherhotep/unwrap_labels/blob/detect_ellipses/c_avg_for_ellipse.pyx)
Конечно, если весь проект посвящен только обработке изображений, то изначальное использование C++ будет более оптимальным вариантом.
Nepherhotep Автор
24.09.2018 18:12+2Нейронная сеть нужна, чтобы найти 6 маркеров — определить их в многообразии нестандартных вариантов (бутылка среди других бутылок, нестандартные этикетки, линии на этикетке). Теоретически, конечно, это всего-лишь цилиндр, но дьявол кроется в деталях. Что касается развертывания, когда сетка уже построена — питон получается вполне быстрым, т.к. на самом деле, работают сишные модули расширения от OpenCV, а инициализация 100 небольших массивов (ячейки сетки) в самом питоне — очень быстрая операция.
На счет преобразования Хафа, я могу сказать точную разницу между Python и Cython, т.к. писал оба варианта — отличие в 200 раз.
robo2k
24.09.2018 12:34Я так и не понял, как именно выполняется разворот изображения на плоскость?
Kwent
24.09.2018 13:32+1Обратными перспективными преобразованиями по тем точкам с сетки поверхности (картинка в статье есть), а тут код github.com/Nepherhotep/unwrap_labels/blob/master/unwrap.py
NihilSherrKhaine
24.09.2018 16:53Насчёт решения с полками. Можно попробовать YOLO(Можно и чего попроще, но реал тайм важен для юзера всё же) натренировать под это дело, а его выход: боксы с каждой бутылкой вина, просто передавать в имеющийся алгоритм для разворачивания этикеток. И учитывая то, что бутылки редко стоят не вертикально, должно работать. Точно видел на гите пару реализаций для андроида.
Сразу предполагаю здесь проблему: если бутылки на полках стоят слишком близко, окна YOLO могут несколько перекрывать друг друга. Но это легко отловить и можно некоторой эвристикой просто в нужных случаях чуточку обрезать окна по бокам.Kwent
24.09.2018 18:07И прям в реал тайме выводить оценку рядом с каждой бутылкой на полке! Хочу такое, очень :)
Nepherhotep Автор
24.09.2018 18:30Да, если бы мы сделали свой поиск по изображениям, как вы с картинами, то можно было бы и такое сварганить :)
А пока мы используем tineye с ценником 1 цент за поиск, то поточные поисковые запросы обойдутся слишком дорого (к тому же, можем нарваться на тротлинг). Разве что, если ее детектировать, и трекать, а запрос на распознавание делать только один раз, когда мобильное приложение «захватило» ее.
NihilSherrKhaine
24.09.2018 18:40Немного покопался в YOLO и сопутствующей информации.
Есть довольно много тредов на гите насчёт переобучения YOLO под свои нужды. В том числе под единственный класс. Вопрос только в переносимости на андроид, тут я не специалист, конечно.
Предполагаю ещё такие проблемы, идущие уже с YOLO:
1) Может встать проблема с бутылками не от вина. Пользователь может не очень одобрить результаты для бутылок не подходящей формы, характерной для прочего алкоголя. Отсеивать может быть чуток сложновато, но обычно бутылки на витрине несколько кластеризованы, так что если с этим будут избыточные проблемы, можно предварительно устроить простенькую кластеризацию, которой нужно просто прямоугольником вырвать кусок фотографии.
2) В тестовой выборке хорошо бы поиграть с расположением бутылок относительно центра съёмки. Всё же на данный момент бутылка фотографируется без отклонений в угле, так как располагается в центре и является единственной. И здесь может быть ряд проблем, которые так просто не устраняются. Возможно будет разумно ограничить пользователя некоторой «зоной» фотографии, в которой он может рассчитывать получить результат, а зону отпозиционировать уже методом проб и ошибок исходя из средней дистанции, с которой производят фотографии.Kwent
24.09.2018 19:48Рекомендую еще посмотреть SSD (сильно больше вариантов реализаций, к тому же Yolo очень кастомное решение и порог входа там выше) и TensorFlow Lite
sasha1024
Интересно.