Комментарии 33
Спасибо, очень интересная статья и алгоритм нужный
НЛО прилетело и опубликовало эту надпись здесь
Здорово.
А работает ли вычитание производных если штрих-код сфотографирован под углом? А для QR-кодов?
Вдобавок хочу дать ссылку на открытый проект ZXing, где ребята из Гугла реализовали чтение множества типов штрих-кодов с фотографий:
code.google.com/p/zxing/
В частности очень популярно их приложение для Android.
А работает ли вычитание производных если штрих-код сфотографирован под углом? А для QR-кодов?
Вдобавок хочу дать ссылку на открытый проект ZXing, где ребята из Гугла реализовали чтение множества типов штрих-кодов с фотографий:
code.google.com/p/zxing/
В частности очень популярно их приложение для Android.
>> А работает ли вычитание производных если штрих-код сфотографирован под углом?
Как говорят авторы алгоритма, алгоритм хорошо работает в диапазоне наклонов от -30° до +30°. Что довольно неплохо, ИМХО.
>> А для QR-кодов?
Описанный выше алгоритм работает только для 1D штрих-кодов.
Хотя ничто не мешает изменить алгоритм под QR-коды: вместо вычитания сделать сложение производных (в QR-кодах есть и горизонтальные, и вертикальные градиенты).
>> Вдобавок хочу дать ссылку на открытый проект ZXing
Да, отличный проект, знаю такой. У него есть одно важное преимущество: он работает с большим количеством различных типов штрих-кодов (1D и 2D) и сам способен распознавать их тип. Но это же преимущество в то же время приводит и к серьезному недостатку: для каждого отдельного типа штрих-кода распознаваемость намного хуже, чем в алгоритмах, специализированных именно под этот тип штрих-кода. Если я правильно понял, то он вообще никак не локализует штрих-код на картинке. И при больших искажениях, таких как дефокусировка и низкое разрешение, он дает совсем плохие результаты.
Как говорят авторы алгоритма, алгоритм хорошо работает в диапазоне наклонов от -30° до +30°. Что довольно неплохо, ИМХО.
>> А для QR-кодов?
Описанный выше алгоритм работает только для 1D штрих-кодов.
Хотя ничто не мешает изменить алгоритм под QR-коды: вместо вычитания сделать сложение производных (в QR-кодах есть и горизонтальные, и вертикальные градиенты).
>> Вдобавок хочу дать ссылку на открытый проект ZXing
Да, отличный проект, знаю такой. У него есть одно важное преимущество: он работает с большим количеством различных типов штрих-кодов (1D и 2D) и сам способен распознавать их тип. Но это же преимущество в то же время приводит и к серьезному недостатку: для каждого отдельного типа штрих-кода распознаваемость намного хуже, чем в алгоритмах, специализированных именно под этот тип штрих-кода. Если я правильно понял, то он вообще никак не локализует штрих-код на картинке. И при больших искажениях, таких как дефокусировка и низкое разрешение, он дает совсем плохие результаты.
посмотрите исходники — почти для каждого типа есть два класса — быстрый Detector и медленный Decoder.
Для обычных штрих-кодов, например, детектор ищет светлый обрамляющий прямоугольник, и лишь потом пытается прочесть данные.
code.google.com/p/zxing/source/browse/trunk/core/src/com/google/zxing/common/detector/MonochromeRectangleDetector.java
мне кажется, такая реализация намного быстрее чем считать гистограмму яркости и т.п. На мобильниках это весьма важно.
Для обычных штрих-кодов, например, детектор ищет светлый обрамляющий прямоугольник, и лишь потом пытается прочесть данные.
code.google.com/p/zxing/source/browse/trunk/core/src/com/google/zxing/common/detector/MonochromeRectangleDetector.java
мне кажется, такая реализация намного быстрее чем считать гистограмму яркости и т.п. На мобильниках это весьма важно.
Хорошо, обязательно посмотрю. Как разберусь, напишу.
Гистограмма яркости считается за линейное время от количества пикселей, в чем проблема ее посчитать? Остальные шаги требуют еще меньше операций )
Да, но линейное время линейному времени рознь. Выигрыш, допустим, в 2-3 раза, может быть существенен. В любом случае надо читать исходный код и сравнивать.
Сложновато обогнать гистограмму по коефициенту:
Тут единственная дорогая операция – чтение/запись памяти. Хотя вообще по идее и это не проблема так как гистограмма помещается в кеш.
for (int i = 0; i < size; i++)
hist[image[i] - min]++;
Тут единственная дорогая операция – чтение/запись памяти. Хотя вообще по идее и это не проблема так как гистограмма помещается в кеш.
К сожалению, гистограмма — не единственное тонкое место. Как я упомянул в статье, там сначала идет предобработка: вычитание модулей производных + усредняющий фильтр 31x31. Это занимает большую часть времени работы алгоритма.
Кстати, вопрос в студию: правда ли, что можно реализовать усредняющий фильтр такого размера (31x31) всего за несколько операций на пиксель?
Кстати, вопрос в студию: правда ли, что можно реализовать усредняющий фильтр такого размера (31x31) всего за несколько операций на пиксель?
«если взять изображение как разницу горизонтальной и вертикальной производной» а если он повернут? попробуйте покрутить его и для разных углов попробовать. думаю выйдет не очень.
Согласен, выйдет не очень. Но тут ничего не поделаешь — пользователю самому придется выравнивать телефон горизонтально. Хотя как я уже сказал выше, допустимый диапазон углов составляет от -30° до +30°, поэтому строгая горизонтальность не нужна. Небольшой наклон допустим.
А вообще все познается в сравнении: если взять, например, то же Яндекс Маркет приложение для Android, то там вообще надо подгонять камеру телефона так, чтобы штрих-код встал четко под прямоугольник. Когда я ехал в трясущейся маршрутке, я просто физически не смог этого сделать.
Или, например, лазерный сканер. Если присмотреться, то можно заметить, как продавщицы в супермаркете частенько поворачивают упаковку товара, чтобы штрих-код распознался системой. А ведь в лазерном сканере качество считывания намного выше, чем в камере телефона.
Так что мой вывод таков: фотографировать штрих-код издалека все равно проще, чем подносить камеру так, чтобы штрих-код четко попадал в зону считывания. Приложений, которые работают по второму принципу полно, а первых, насколько мне известно, пока еще нет.
А вообще все познается в сравнении: если взять, например, то же Яндекс Маркет приложение для Android, то там вообще надо подгонять камеру телефона так, чтобы штрих-код встал четко под прямоугольник. Когда я ехал в трясущейся маршрутке, я просто физически не смог этого сделать.
Или, например, лазерный сканер. Если присмотреться, то можно заметить, как продавщицы в супермаркете частенько поворачивают упаковку товара, чтобы штрих-код распознался системой. А ведь в лазерном сканере качество считывания намного выше, чем в камере телефона.
Так что мой вывод таков: фотографировать штрих-код издалека все равно проще, чем подносить камеру так, чтобы штрих-код четко попадал в зону считывания. Приложений, которые работают по второму принципу полно, а первых, насколько мне известно, пока еще нет.
Хм, как выяснилось гугловский ZXing тоже производит локализацию штрих-кода. Осталось только понять, какой алгоритм лучше: описанный в статье или ZXing.
если вы пишете диплом для себя, то уж стоит искать хорошие решения. так аргумент «у остальных так же» не очень. мне удалось подобрать последовательность фильтров, которая неплохо выделяет потенциальные области, где могут быть штрих коды, причем мой метод абсолютно инвариантен к поворотам. потом области надо проверить самому. завтра покажу код если интересно.
Во-первых, суть статьи не в том, чтобы показать, что метод локализации хорош, а в том, чтобы показать действенность метода на реальной задаче. В данном случае, на локализации штрих-кодов.
Во-вторых, «хорошесть» вашего метода не отменяет «хорошесть» описанного мною. Просто ваш может быть немного лучше.
В-третьих, в дипломе я не занимаюсь локализацией, так как локализация уже разработана многими. Вот и вы предлагаете свой метод. Моя задача ограничена именно распознаванием уже локализованного штрих-кода.
В-четвертых, инвариантность относительно поворота в моей работе не нужна, так как дальнейший алгоритм распознавания все равно не работает с наклоненными штрих-кодами (такова плата за низкое разрешение и дефокусировку).
В-пятых, хорошие решения есть, но далеко не все их можно достать в Интернете. Вот вы придумали метод, взяли бы да и опубликовали статью. И я бы в своем дипломе, к примеру, мог бы сослаться на него.
Во-вторых, «хорошесть» вашего метода не отменяет «хорошесть» описанного мною. Просто ваш может быть немного лучше.
В-третьих, в дипломе я не занимаюсь локализацией, так как локализация уже разработана многими. Вот и вы предлагаете свой метод. Моя задача ограничена именно распознаванием уже локализованного штрих-кода.
В-четвертых, инвариантность относительно поворота в моей работе не нужна, так как дальнейший алгоритм распознавания все равно не работает с наклоненными штрих-кодами (такова плата за низкое разрешение и дефокусировку).
В-пятых, хорошие решения есть, но далеко не все их можно достать в Интернете. Вот вы придумали метод, взяли бы да и опубликовали статью. И я бы в своем дипломе, к примеру, мог бы сослаться на него.
Кстати, да, мне интересно, я бы посмотрел код, а еще лучше, краткое его описание.
Спасибо, очень интересно. А как насчет инвариантности к освещению? И еще, если можно, этот алгоритм можно применять для любых классов? Или есть какие-то требования?
если освещение изменяется равномерно (либо все темнее, либо все светлее) то результат будет одинаковый. в этом и преимущество.
Если имеется в виду именно средняя яркость всего изображения, то да, от нее ничего не зависит.
А вот если средняя яркость левой половинки картинки меньше, чем правой (неравномерная освещенность фотографии, например), то, к сожалению, метод уже не работает. В таком случае приходится применять всякие ухищрения.
А вот если средняя яркость левой половинки картинки меньше, чем правой (неравномерная освещенность фотографии, например), то, к сожалению, метод уже не работает. В таком случае приходится применять всякие ухищрения.
>> И еще, если можно, этот алгоритм можно применять для любых классов? Или есть какие-то требования?
Хороший вопрос, в общем-то:) Думаю, можно ответить так: чем лучше классы описываются гауссовым распределением и чем меньше их гистограммы перекрываются, тем надежнее будет метод.
Хороший вопрос, в общем-то:) Думаю, можно ответить так: чем лучше классы описываются гауссовым распределением и чем меньше их гистограммы перекрываются, тем надежнее будет метод.
спасибо, хорошо описано.
в последней ссылке «Сайт людей, которые придумали эффективный алгоритм распознавания штрих-кода UPC (англ.)» потерялась «l» в конце ссылки «htm».
в последней ссылке «Сайт людей, которые придумали эффективный алгоритм распознавания штрих-кода UPC (англ.)» потерялась «l» в конце ссылки «htm».
Из тюнинга — можно пройтись по диагонали при составлении гистограммы — результат примерно как логарифмировать гистограмму, а количество операций меньше.
Не совсем понял, поясните, пожалуйста.
Логарифмирование гистограммы по основанию 2 даст в итоге значения степеней двойки которые для изображения 640*480 будут варьироваться в диапазоне примерно 1-20, 0 естественно отбрасывается при логарифмировании. При вычислении гистограммы по главной диагонали image[i][i] значения тоже будут лежать в данных диапазонах за меньшим числом операций и экспериментально будут очень близки к результату, полученному логарифмированием.
Картинки сдохли ;) а еще и из Эдинбурга :-)
Спасибо, хорошее описание. А если «горбов» неизвестное число? Есть ли обобщение на такой вариант?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Обнаружение объектов методом Оцу