Търсене на шаблон в изображение
Проблемът “Локализиране на еталон в изображение”.
В съвременната индустрия автоматизацията на технологичните процеси има водеща роля. Най-новите заводи са напълно или в много висока степен автоматизирани. Обслужващия персонал е сведен до минимум. Това стана възможно с развитието на визуалните системи за управление и контрол. Те имат за цел да осигурят прецизно “зрение” на промишлените роботи, диспечерски станции и др. Един проблем поставен и разискван още през 60-те години на миналия век, лежи в основата на развитието на автоматизацията, а именно “локализиране на еталон в изображение”. Този проблем се явява математически и бързо се появяват предложения за алгоритми за търсене. Същинският проблем идва от това , че в общия случай трябва да се търси не малък еталон (шаблон) в доста по-голямо изображение. Цифровите данни, които трябва да се обработят са твърде много и алгоритмите се оказват неефективни на практика, макар на теория да са добри, поради големите времена нужни да се получи резултат. Търсят се възможности за намаляване обема на съществената информация за шаблона, за да се намали време за търсене и да се запази прецизността на откриване. Към алгоритмите за търсене се предявяват изисквания за откриване на даден шаблон в изображения подложени на зашумяване.
Голямо разнообразие от приложения се нуждаят от решение на поставения проблем. Някои от тях са:
- регистрация на маркери (знаци) върху печатни материали като банкноти, ценни книжа и др.
- промишлени роботи в електрониката, както и за товаро-разтоварни дейности и др.
- за бързо претърсване на сателитни снимки с огромен обем, за отличителни белези.
- за бързо откриване на пръстов отпечатък във все по-големите бази от данни.
Проблемът търсене на шаблон в изображение не се отнася само са графични обекти. Той може да се постави за звукови сигнали, за разпознаване на човешка реч и други. Този проблем се решава чрез различни алгоритми за съпоставяне на множества от подходящо избрани представителни точки от сравняваните изображения и прилагане на различни мерки за оценка на подобие между тях.
Един от алгоритмите за определяне на разстояние между две множества от точки е дистанцията на Хаусдорф. Той измерва близоста на всяка точка от едното от сравняваните множества(например представителните точките от търсения шаблон) до най-близката и точка от другото множество(съставено от представителните точки от изображението) и обратно. За разлика от взаимната корелация, например, при която се търси еднозначно съпоставяне на всяка точка от едното множество със съответстващата и точка от другото множество, тук такова съпоставяне не се прави. С други думи, Hausdorff разстоянието между две множества от представителни точки, които в общия случай имат различен брой елементи, не изисква на всеки елемент от едното множество да се съпоставя единствен елемент от другото множество.
Множествата от представителни точки се формират най-често от точките, разположени по ръбовете, контурите и върховете на ъглите на отделните обекти от изображението, тъй като те носят най-голяма информация за неговите особености. Тези характерни точки могат да бъдат извлечени от изходните изображения по много различни методи и алгоритми, подчиняваики се на различни критерии.
Нашето внимание в тази дипломна работа е насочено както към формирането на множества от представителни точки за сравняваните изображения, така и към едно модифициране на дистанцията на Hausdorff с оглед използване на особеностите на формираните множества от точки, с цел постигане на по-малка изчислителна сложност при запазване достойнствата на самата дистанция.
Алгоритми за търсене над подмножество от шаблона
Другата основна посока за оптимизиране на алгоритмите за търсене е вместо да се търси оценка на съвпадение на цялото изображение, да се избере подмножество от точки, които да представят шаблона. Така задачата се свежда до сравняване на изображенията само в подмножеството от избраните точки. Мерките за подобие са същите, но проблемът е кои точки да изберем, така че търсенето да е ефективно.
Ясно е, че случаен избор на точки или вземане на точки по предварително подготвени фиксирани координати в общия случай няма да са много подходящи. При случаен подбор, ако в изображението отличителните белези са концентрирани в определена малка област статистически вероятността за уцелване на съществена точка е много малка.
Детектори на ръбове
Детекторите на ръбове са едни от основните алгоритми в обработка на изображения. Детекторите на ръбове охарактеризират границите на изображението и за това имат важно значение при процесите с тях, те пренебрегват ненужната информация, докато в същото време контролират важните структурни части на изображението. Те са сравнително добре изследвана област, но непрекъснато се развива в посока тримерно интерпретиране на изображенията. Разглеждаме няколко вида детектори, които въпреки че са принципно различни, дават почти еднакви резултати.
Възможни са много подходи за редуциране на първоначалното множество от точки по ръбовете. При всички случаи се търси прагово ниво разделящо избраните от неизбраните пиксели. Единият начин е да се започне с праг нула и да се увеличава на всяка стъпка като освен това и преброяваме избраните точки при съответното прагово ниво. Този процес продължава докато не достигне достатъчно малък брой точки (характера на праговото ниво гарантира, че с по-ниския праг ще получим повече или същия брой избрани точки). Този начин е известен в теорията на алгоритмите като линейно или тривиално търсене.
Еквипотенциален избор
Използвайки стойността на сивия цвят във всяка точка на изображението като негова трета координата, ние можем да представим пространствения му вид.
В светлината на това представяне на изображението, метриките за дистанция между изображенията могат да се интерпретират, като своебразна оценка на средното евклидово разстояние. Оценката на разстоянието на едно изображение до въведения еталон в този сммисъл позволява същото да бъде припознато като такова или отхвърлено като различно.
Вероятно пространствената интерпретация на изображението е подходяща основа за прилагане върху не я на метода за формиране на D-оптимизирани подмножества, като подмножества, минимизиращи изчисленията, свързани с оценката по корелация или друга дистанция. С други думи тук се предлага еталонното изображение да бъде представено не, чрез пълното си множество пиксели, а чрез подходящо избрани такива, които при това ще запазят и представят в достатъчно висока степен на съответствие пространствената му структура.
Дистанция на Hausdorff между множества от точки
Едни от най-успешните мерки за подобие при сравнение с еталон се основават на определянето на дистанции, тъй като те показват висока устойчивост към липсващи или частично нарушени данни, което се счита за недостатък на корелацията. При методите, използващи дистанции, обектите се представят чрез двоични шаблони, съдържащи информация най-често за координатите на характерните точки на сравняваните изображения.
Една от мерките за определяне на разстоянието между две множества от точки е дистанцията на Hausdorff. Тя измерва близостта на всяка точка от едното от сравняваните множества (например представителните точки от търсения еталон) до най-близката й точка от другото множество (съставено от представителните точки от изображението) и обратно. За разлика от взаимната корелация, например, при която се търси еднозначно съпоставяне на всяка точка от едното множество със съответстващата й точка от другото множество, тук такова съпоставяне не се прави. С други думи, Hausdorff разстоянието между две множества от представителни точки, които в общия случай имат различен брой елементи, не изисква на всеки елемент от едното множество да се съпоставя единствен елемент от другото множество.
Сходни статии:
- Търсене на числа от поредица автор: Веселин Димитров Програмата е създадена с цел намирането на числа от поредица такива, които са по-големи от сбора на всички предхождащи го числа. Програмата позволява да се четат числа...
- Електронни пазари – търсене и предлагане Електронния пазар обхваща всички пазарни участъци, които използват световната мрежа Интернет за транзакции на стоки, услуги и информация. Тъй като повечето от нещата в Интернет имат тенденция да стават безплатни,...