В речта си, Александър Kraynov каза по какъв начин Yandeks.Kartinki струпани дублиращи се изображения. С други думи, на изолирани и филтрира дубликати изображения. Когато основната идея е да се подчертаят контурите на изображението през филтъра за куче. след това намерете ключови точки и да получат своите дръжки.
Групиране на дубликати се свежда до търсене описатели мачове. Това е "цифровизация" на ключови моменти от статия Групирането търсенето на второ копие.
Но аз бих искал малко по-подробно, за да разберете какъв вид дръжки и как да ги търси.
описания
Ключови точки - пунктовете, които в идеалния случай не трябва да се променят, когато променя или изменя образа.
Описания - е, най-общо, извивките на характеристиките и представянето на ключовите точки в достъпен формат, за да тествате за един мач.
Търсене ефективно изтъкнат ключови точки, техните описания, както и съвпадението на методи за проверка, все още е на дневен ред.
Но е необходимо да се започне от някъде, така че нека се обърнем към помощта на OpenCV библиотека.
Първото нещо, което хваща окото на - тя се справя SURF.
Това обещание извънредно точност. Което се потвърждава и след изпитването.
Но има някои нюанси.
Описания SURF - е вектор на 128 (или 64) номера на една ключова точка. Проверка се извършва в случайно намери най-близката точка (или дори две). Колкото по-близо точки, толкова по-добре.
Оказва се, че изображението с 1000 точки се нуждаят 128 000 номера с плаваща запетая.
Освен това, много за откриване на точките е доста сложна операция и изисква значително време. Което не позволява ефективно използване на този алгоритъм за малки устройства. В допълнение, самата алгоритъм затворен и патентовани (САЩ).
След като прочетете пресее и да сърфирате, исках нещо по-просто за изпълнение, с възможност да се прилага една малка сървър или устройство.
възприятие хешове
И бяха открити във възприятията или възприятие хешове.
Проблемът, който е, че най-малко една малка хеш промяна на изображението също леко се променя.
Проверка за съвпадение се извършва чрез преброяване на броя на различни позиции между две хешове. Т.е. преброяване на разстояние Хаминг. Колкото по-малка е, по-малко отделни елементи, толкова по съвпадението.
Този метод е предназначен за търсене на пълни или частични изображения дубликати. Т.е. когато значителна промяна в съотношението на екрана или намеса в съдържанието прави невъзможно да се провери за един мач, защото хешове са подчертано различни.
С други думи, перцептивни хешове не са подходящи за търсене poludublikatov.
На тази основа е направен опит да се съчетаят СЪРФ дескриптори и възприятие хешове с цел да се реши проблема с намирането на размита poludublikatov.
Методът се основава на групирането на точки, така че центровете на клъстерите съответстват на оригиналното изображение и kropnutyh. Друг избор е направен от пластира около температурата на реплика и получаване възприятие хешове. В резултат на едно изображение даде около 200 рязане култури и техните хешове.
При този метод, има две и половина основни недостатъка:
1. изпитване с ниска скорост за мача на голям набор от хешове. Търсене на 1 милион хешове отнема 20 секунди
2. Ниска скорост от приемните точки
3. ниска точност, много неверни положителни резултати, за голямо търсене на целевата база данни, не е подходящ за всички снимки, тя изисква предварително умереност и т.н.
Самата идея, че ще бъде от картината създава определен брой снимки (пръстов отпечатък), който може да бъде просто в сравнение с всеки друг, очарован.
Затова беше взето решение да се опитаме да намерим решения на тези проблеми.
Ниска степен на вземане на проби
Сложността на намиране и отчитане на разстоянието на Хеминг в голям набор от данни е отделен проблем и изисква независим подход.
След няколко изследователски теми Оказа се, че има много решения на този проблем.
Тя е била избрана и прилагана най-ефективните на съществуващия алгоритъм, наречен HEngine. което позволи на
60 пъти ускоряване проба от базата данни.
SURF и ключови точки
Тъй като ние работим с двоични хешове или пръстови отпечатъци, както и съвпадение вярвам Хеминг разстояние, това е странно да се използва такава машина като прибоя и би било необходимо да се помисли за други методи за получаване на ключовите точки и дескриптори.
Като цяло, OpenCV предвижда два вида етикети:
- Дръжки за плаваща запетая
- И двоични описания
Тук двоични описания като никой друг подход за нашия проблем, защото тя се използва и Хеминг разстояние, за да проверите за мачове.
ORB: ефективна алтернатива да пресее или SURF
OpenCV вече е в отлична алтернатива на прибоя, което не е достатъчно, че една отворена и без лицензионни ограничения, така че дори по-бързо, по-лесно и [1].
ORB - това Oriented FAST и да се завърти КРАТКО - подобрена версия на детектора и комбинацията от точки и FAST двоични описания КРАТКО.
ORB има един основен протест за нас - с размерите на 32 байта на описания в една точка.
Проверка за един мач - е сумата от разстоянията Хеминг за всеки байт от ЕВРОВОК (първо в сравнение с първата, втората на втория, и така нататък).
В нашия проблем се разбира, че една точка дава една стойност, а след това се превръща 32, които са необходими също така да обобщим със съответния индекс (първо с първата, втората на втория, и така нататък) в базата данни приемник.
Тъй като нашата хеш е номер на 64-битов, необходимият 32-байт Характеристиката се свие до 8 байта, а не много за губене в точността.
След няколко теста, беше решено да се опитате тези 32 байта, представени като матрица от 16 × 16 бита. След това тази матрица, за да премине през възприятие хеш PHash. Резултатът е, че само номер 64-битов.
Сега стигаме до пълно описание на концепцията.
Как работи индексиране
1. Снабдете ключови термини и описания ORB, изберете необходимия брой точки на изображението.
2. Получените 32 байта на описания присъстват под формата на малко 16 х 16 матрица.
3. Превръщане на матрицата в номера на 64bit използване PHash.
4. Запазване на 64bit отпечатъците в MySQL.
5. Изберете желаната Хеминг разстоянието и пуснете демон HEngine, който ще извърши търсенето.
Как работи търсенето
Извършване на идентични стъпки 1 - 3 от индексиране, но само за исканото изображение.
4. Направете заявка демон HEngine, която връща всички хешове в посочения диапазон.
5. Ако искате да филтрирате неподходящи резултати.
Фигура 1. Limit разстоянието Хеминг 7. Грей точка - Намерих го ключовият момент. Зелени - съвпадащи точки. Червен - ORB съвпадение стандарт пълнотекстово търсене.
И какъв е резултатът?
В резултат на това ние успяхме да решим няколко проблема:
- да се намери начин да бъдат преброени бързо разстоянието на Хеминг в голям набор от данни
- да се отървете от големи и неудобни SURF
- да се увеличи скоростта на освобождаване от ключовите точки на техните пръстови отпечатъци
- и не губи много в точността.
Кой позволи да се намери образа на фрагмент от нея, както и размита poludublikaty без големи изчислителни ресурси.
Като се има предвид, че в зависимост от настройките, алгоритъмът, описан от двоични описания ORB произвежда около 1000 хешове картина.
На базата на 1 000 изображения, получени 1 милион хешове в базата данни. И пълен списък на всички изображения в базата данни за минута и половина.
За сравнение, в своя доклад krainov Kraynov Александър обяснява, че търсенето на дубликати на 1 милион изображения те отнеме около две минути.
Свързани статии