Система за разпознаване на символи

Задача #6 от конкурса на Telerik и PC Magazine Bulgaria, сезон 2011/2012

Кръг на Johnson Controls

 

Фирма производител на електронни устройства иска да автоматизира тестването на дисплеи. С необходимата камера са прихванати изображения от дисплея и са записани във файл. За завършване на автоматизацията трябва да се проектира и реализира система, която разпознава символи в съществуващите изображения и връща низ от разпознатите символи в текстов файл.

Алгоритмична задача

Вашата задача е да създадете алгоритъм, който търси символи във входно изображение с размер 320х240 пиксела. Алгоритмът трябва да създаде изходно изображение, което има два пъти по-голяма височина от входното, т.е. с размери 320х480. Изходното изображение се състои от две изображения. Първото е входното изображение, а второто е преобразувано от първото по следния начин: всеки намерен символ е ограден в правоъгълник, като символът е оцветен по подходящ начин (цветовете на заградените и маркирани символи трябва да се различават с просто око). Символите се търсят в предварително зададени региони.

Намерените символи трябва да се изведат в текстов файл. Всички символи от един регион от входното изображение трябва да са на един ред в текстовия файл. Ако между символите в един регион има поне един интервал, то в текстовия файл между тях трябва да има точно един интервал. Броят на редовете в текстовия файл трябва да е равен на броя на дадените региони. Ред в изходния файл не може да започва или завършва с интервал.

Входни данни

Входните данни се четат от файл с изображение snapshot.png (стандартен PNG файл с размери 320×240 с 32-битова палитра) и входен текстов файл с име regions.txt. На всеки ред от входния текстов файл е зададен по един регион. Регионите са не-повече от 10. Всеки регион е описан с четири цели числа записани с по точно един интервал между тях „X Y W H”. X и Y са координати на горния ляв ъгъл на региона (X по хоризонтала, Y по вертикала), W е широчината, а H е височината на региона в пиксели. На един ред може да има данни само за един регион. Горният ляв ъгъл на входното изображение има координати (0, 0), които нарастват надясно по X координатата и надолу по Y координатата.

Изходни данни

Алгоритъмът трябва да създаде изходно PNG изображение с име output.png и текстов файл с име strings.txt. Файловете трябва да бъдат записани на същото място, където е входното изображение (т.е. в същата директория).

Ограничения

• Фонът на входното изображение е оригинално черен (преди заснемането с камера).

• Всички символи оригинално (преди заснемането с камера) са едноцветни и с един и същ цвят, изписани в anti-aliasing стил (без резки граници по контура).
• Цветът на символите от изображението-резултат трябва да се различава от цвета им във входното изображение.
• Шрифтът на търсените символи във входното изображение е или Arial или Fixedsys.
• Размерът на шрифта е цяло число от 16 до 72 пиксела.
• Символите са разположени водоравно. Не може да са удебелени, наклонени или задраскани.
• В един регион може да има елементи само от един и същи вид – тип и размер на шрифта.
• Регионите не могат да се застъпват (нямат общи точки).
• Символите не могат да се застъпват (нямат общи точки).
• При снимането с камера може да се получават леки дефекти и неточности: липсващи пиксели, излишни пиксели, леко изменение на цвета на някои пиксели и подобни.

Пример

Примерен вход:

snapshot.png	regions.txt
	0 0 320 5050 56 270 2050 100 270 50 85 164 89 39 10 211 260 25

Във входа е дадено входно PNG изображение и са описани пет региона, в които се очаква да е изписан някакъв текст.

Примерен съответен изход:

output.png	strings.txt
	PRNDL -18°C ^ 905km to E v 132874 km

Приложна задача

Да се реализира приложение, което предоставя потребителски интерфейс за зареждане на PNG изображение, избиране на региони в него и извършва разпознаването на символите в него. Минимална изисквана функционалност на приложението (всяка реализирана и работеща функционалност носи точки):

• Избор на изображение, избор на региони за разпознаване, визуализация
• Зареждане и ползване на алгоритъм за разпознаване на образи(.exe), работещ по описания начин (може да има и вграден алгоритъм в приложението, но трябва да може да бъде заменян с друг чрез потребителския интерфейс)
• Генериране и визуализиране на изображение с маркирани разпознати символи
• Запазване на генерирани изображения с разпознати символи

Задачата дава възможност да се добавят много други функционалности от състезателите. Всяка допълнителна работеща функционалност ще получи допълнителни точки.

Критерии за оценяване

Критерии за алгоритмичната задача

Оценяването ще се извърши с тестове (входни файлове). Коректността на работата на алгоритъма ще бъде оценена според резултатите от изпълнението (изходни файлове) на всеки един тест поотделно. Оценката за алгоритмичната част е сборът на резултатите от всички тестове. Максималната възможна оценка за алгоритмичната част е 10 точки.

* Правилно подредени символи в един ред наричаме символите от един регион подредени отляво надясно (т.е. текста да съответства на този в изображението). Подредбата на редовете със символи в изхода трябва да е същата като тази на регионите във входа. Т.е. първият ред от изхода съдържа символите във първия регион означен във входа и т.н.

** Правоъгълник, чиито страни са успоредни на страните на изображението (т.е. хоризонтални и вертикални); Възможно най-малкият правоъгълник около символа, който не закрива пиксели от символа)

*** Цветът в изходното изображение трябва да има разлика поне 60 единици от цвета във входното изображение, по скалата от 0 до 255, в поне един от RGB компонентите; Цветът трябва да е 100% еднакъв за целия символ; Символът в изходното изображение трябва лесно да се различава по цвят от цвета от фона, т.е. да има разлика от цвета на фона поне 60 единици, по скалата от 0 до 255, в поне един от RGB компонентите

Критерии за приложната задача

Оценяването на предложените от участниците в конкурса решения на приложната задача ще се извърши от специализирано жури по-следните критерии:

Оценката за приложната част е сбор от точките за отделните критерии. Максималната възможна оценка за приложната част е 10 точки.

Допълнителни изисквания

• Задачите позволяват използването на различни езици за програмиране и технологии (например PHP, C, C++, C#, Delphi, Python, WPF, XAML, Windows Forms, Java, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows среда съгласно общите условия на конкурса.
• За алгоритмичната част се изисква да бъде предаден пълният сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), използвайте подходящ компилатор (потърсете в Интернет).
• За приложната част се изисква да бъде предаден пълен сорс код. Състезателите имат право да изберат начина, по който тяхното приложение ще бъде стартирано, така че това да е удобно в Windows среда (приложението може бъде и уеб-базирано). Тъй като оценяването на приложната част ще бъде извършвано и от гледната точка на потребител (а потребителите искат да стартират едно приложение възможно най-бързо и лесно), по-сериозни затруднения при намирането и стартирането на приложението ще намалят неговия краен резултат.

 

Анализ на шести кръг и резултати

Ето, мина и предпоследният кръг на състезанието на PC Magazine и Телерик, а за задачата трябва да благодарим на Johnson Controls. Следва и големият финал, на който класиралите се ще трябва да се срещнат в София, в борба за големите награди, но за това – после. Преди това ще поговорим малко за този кръг, както обичайно правим. От всички кръгове, които сме имали досега, този беше привидно най-труден. Истината не е съвсем такава, но така или иначе трябва да похвалим състезателите, които участваха и предадоха добри решения на задачата. Разбира се, имаше по малко от всичко – както хубави резултати, така и не толкова. Трябва да се отбележи, че този кръг промени генералното класиране и десетте отбора, които ще се класират на финалния кръг не са съвсем същите като преди. За разлика от преди, в тази статия ще има не една таблица с резултати, а две – една за резултатите от този кръг и една с резултатите досега. А за липса на разлика от преди, можете да ги видите най-отдолу на тази статия (приятно scroll-ване).

За оценяването и резултатите от алгоритмичната част

Изискванията за алгоритмичната част този път бяха далеч от стандартните. Трябваше да се работи с изображения, а още повече – да се разпознават символи в тези изображения. И докато на пръв поглед разпознаването на текст от образ (т.нар. Optical Character Recognition) изглежда непосилно, едно по-дълбоко вглеждане разкрива, че задачата от този кръг не е нещо изключително.  Да, има доста сложни алгоритми, за разпознаване на символи, но те се прилагат, когато много неща са неизвестни – например шрифт, размер, наклон, цветови нюанси, артефакти по символите и така нататък.  В тази задача, тези неща бяха до голяма степен пояснени. Дори тривиално решение с обикновено сравняване на пиксели и отчитане на прилика би пожънало известни успехи (предвид, че са дадени 2 шрифта и всички ползвани размери). Също така има доста решения с отворен код, засягащи точно този проблем. С две думи казано – приканваме състезателите да подхождат по-решително към сложни на вид проблеми, защото те не винаги са толкова тежки, колкото изглеждат.

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

Състезателите, които предадоха решения бяха положили старания и резултатите се проявиха още с първите тестове. Дори понякога алгоритмите се престараваха и разпознаваха неща, които не беше нужно, но им е простено. Два отбора се бяха заели с тази част, като тук единият се справи значително по-добре и съответно получи пълните 10 точки (както е по регламент), а другият отбор – съответната част от тези точки.

За оценяването и резултатите от приложната част

Абстрахирайки се от самия разпознаващ алгоритъм, можем да твърдим, че приложната част не беше никак сложна. Е, не видяхме всичко, на което се надявахме, но все пак имаше интересни решения. При едно от състезаващите се решения дори имаше документация от няколко страници, която, за наша радост, се състоеше предимно от картинки.

Ако трябва да бъдем кратки – резултатите от приложната част се противопоставиха на тези от алгоритмичната. Отборът, който там имаше ролята на догонващ, тук беше лидер. Той получи съответно водещ резултат в тази част, като този резултат се базираше на неговата ползваемост, лесна употреба и степента, в която имплементираше изисканите в условието функционалности, както и на дизайнът на потребителския си интерфейс. Нашето жури, както обикновено, направи комплексна оценка върху всички тези показатели, като разбира се взе предвид и нещата, които бяха изпипани докрай и постави оценките на участващите в тази част решения, които можете да видите по-надолу.

Крайни резултати

Това е класирането базирано на крайните резултати от шести кръг на състезанието, образувани от сбора на точките от алгоритмичните и приложните части, предадени от състезателите. Поздравления на всички за резултатите! Благодарим Ви за участието!

 

Отбор	Краен резултат	Алгоритъм	Приложение
Димитър Дилянов Иванов	13	10	3
Марио Стоилов и Ивайло Кирилов	9	4	5

Решенията на участниците от всички кръгове са публично достъпни и след обявяването на резултатите за съответния кръг могат да бъдат намерени на този адрес:

http://pcmagazine-telerik-contest.googlecode.com/svn/trunk/

Генерално класиране и отбори, поканени да участват на финалния кръг

Тук ще приложим класирането от всички кръгове досега. Нека напомним, че всички тези кръгове ще дадат на 10 отбора правото да участват в големия финал, където ще бъдат раздадени големите награди. С други думи, тези резултати ще определят единствено кой ще участва на финала. На самия финал ще има значение единствено кой ще се представи най-добре – без да се вземат предвид резултатите дотук. Така че призоваваме всички класирали се отбори да дадат най-доброто от себе си на финалния кръг на състезанието.

Ето генералното класиране, в което първите 10 отбора ще имат възможността да се състезават на финала за големите награди: