Katholieke Universiteit Leuven Faculteit Ingenieurswetenschappen Departement Computerwetenschappen
Masterproef Begeleider: Sten Govaerts Promotor: Prof. Erik Duval
Augment Japan!
Matthias Vandenbussche - Master of Science in de Ingenieurswetenschappen: Computerwetenschappen - Mens Machine Communicatie Annelies Van der Borght - Master of Science in de Ingenieurswetenschappen: Computerwetenschappen - Mens Machine Communicatie Blog - http://augmentjapan.wordpress.com
November 4, 2011
Inhoudsopgave 1 Situering en probleemstelling
2
2 Doelstelling
2
3 Geleverd werk en resultaten 3.1 Algemene papers . . . . . . . . . . . . . 3.2 Detectie en lokalisatie van tekst . . . . . 3.3 Corrigeren van tekstregio’s . . . . . . . . 3.4 OCR . . . . . . . . . . . . . . . . . . . . 3.5 Vertaalmogelijkheden . . . . . . . . . . . 3.6 Vergelijking van gerelateerde applicaties
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
4 Planning
3 3 4 4 5 7 7 8
5 Belangrijkste moeilijkheden 5.1 Tekstlokalisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Teksttracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Tekstcorrectie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10 10 10 10
6 Dit werk verdient...
10
A Statistieken A.1 Matthias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Annelies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 12 12
B Bestudeerde literatuur B.1 Matthias . . . . . . . B.1.1 Skimmed . . B.1.2 Read . . . . . B.2 Annelies . . . . . . . B.2.1 Skimmed . . B.2.2 Read . . . . .
13 13 13 13 14 14 14
en . . . . . . . . . . . .
gerelateerd werk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C Extra afbeeldingen
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
15
1
1
Situering en probleemstelling
Veel mensen reizen jaarlijks naar het buitenland. Dit kan louter voor het plezier in de vrije tijd zijn of voor het werk (bijvoorbeeld het bezoeken van een andere hoofdzetel van het bedrijf of een deelname aan een conferentie). In beide gevallen worden mensen af en toe geconfronteerd met een taal die ze niet machtig zijn. Zo kunnen ze informatie- en waarschuwingsborden niet lezen, of begrijpen ze een menu in een restaurant niet. Hulp vragen aan de lokale bevolking is niet altijd even makkelijk, aangezien zij mogelijk geen gemeenschappelijke taal spreken. Een aantal oplossingen zijn reeds voor handen, zoals het gebruik van een zakwoordenboek of zakvertaler (de digitale versie van een zakwoordenboek), die toelaten de betekenis van woorden op te zoeken. Zo kunnen mensen een idee krijgen van wat er op een bord staat. Ook online vertaalservices zoals Google Translate1 kunnen eventueel gebruikt worden vanop een mobiele telefoon of een tablet pc. Voor het gebruik van dit soort hulpmiddelen werd er wel een belangrijke veronderstelling gemaakt: de gebruiker moet de woorden kunnen lezen en opzoeken (bvb alfabetisch gesorteerd) of intypen. In Europa is dit meestal geen probleem, aangezien de meeste talen het Latijns schrift gebruiken. Er zijn daarentegen ook landen waarin het schrift zeer sterk verschilt van het Latijns schrift dat we gewoon zijn. Talen zoals het Russisch en het Grieks gebruiken een ander alfabet en talen zoals het Japans en Koreaans gebruiken een ideografisch (gemixt met logografisch) schrift. In het geval van een ander alfabet kan men (met redelijk wat moeite) nog proberen te zoeken in een zakwoordenboek op alfabetische volgorde. Woorden intypen wordt al een heel stuk moeilijker, tenzij de zakvertaler en toetsenbord in het vreemde alfabet heeft. Voor ideografische talen is het probleem nog een stuk groter. Er is geen strikte (of logische) alfabetische volgorde, het aantal tekens is vaak een duizendvoud en als men de taal niet kent ziet men ook geen structuur in de complexe tekens. Aldus is het opzoeken in een zakwoordenboek of het intypen van de tekens een (bijna) onmogelijke opgave. Smartphones zoals de iPhone alsook tablet computers zoals de iPad zijn de dag van vandaag alomtegenwoording. Vaak zijn deze toestellen uitgerust met een camera en ondertussen hebben zij een veel grotere rekencapaciteit dan de mobiele telefoons van enkele jaren geleden. Dit geeft dan ook aanleiding tot applicaties zoals Word Lens2 en OCR Test3 . Hoewel deze applicaties al goed werken en dus zeker nuttig zijn, is er nog ruimte voor uitbreiding en verbetering.
2
Doelstelling
Om de extra problemen die gepaard gaan met talen in een ander schrift te voorkomen, stellen wij een applicatie voor die gebruikt zou kunnen worden op een smartphone (zoals iPhone of een Android phone) of op een tablet pc (zoals een iPad). Een andere mogelijkheid is het gebruik van een virtual reality bril. De beoogde applicatie gebruikt de live video feed van de camera en zoekt hierop naar tekst. De tekst wordt herkend en dan door een online translation service vertaald. De vertaalde tekst wordt op het toestel weergegeven aan de gebruiker, op de plaats van de originele tekst in het beeld. Aldus wordt in het beeld het originele bord vervangen door een vertaalde versie ervan. Specifieke doelstellingen voor onze applicatie zullen voornamelijk betrekking hebben tot de gebruikerservaring en de gebruikersinterface. Dit omdat hier de focus van onze thesis ligt. Voor de hoofdfunctionaliteiten (onder meer Optical Character Recognition (OCR), tekstlokalisatie4 en vertaling) zijn we van plan om bestaande services, libraries en/of algoritmen te gebruiken. We focussen dus niet op het cre¨eren van zo goed mogelijke OCR-resultaten of vertalingen, al zullen we wel de gevonden services, libraries en/of algoritmen met elkaar vergelijken en pogen om de beste combinatie te kiezen. Hieronder een lijst met enkele specifieke doelstelling. • We beogen zo weinig mogelijk handelingen van de gebruiker (idealiter slechts ´e´en klik voor het openen van de applicatie en mogelijk nog wat extra kliks voor de instellingen). Daarom willen 1 http://translate.google.com/ 2 http://itunes.apple.com/be/app/word-lens/id383463868?l=nl&mt=8 3 https://market.android.com/details?id=edu.sfsu.cs.orange.ocr 4 Met
tekstlokalisatie wordt zoeken van tekst in een afbeelding bedoeld.
2
we dat onze applicatie zelf voor de tekstlokalisatie zorgt. De gebruiker moet zelf dus geen regio aanduiden waar de tekst zich bevindt. • De OCR- en vertaalresultaten moeten in near-real-time kunnen berekend worden, zodat de gebruiker niet (lang) moet wachten op de vertaling. – Daarnaast moeten de OCR-resultaten ook zo goed mogelijk zijn. Dit zullen we bepalen door de nauwkeurigheid (# correct herkende karakters / # karakters). – Ook de vertaalresultaten moeten zo goed mogelijk zijn. Dit zullen we bepalen aan de hand van BLEU, NIST en F-Measure. Deze scores worden verder uitgelegd in paragraaf 3.5. • De weergegeven resultaten moeten makkelijk leesbaar zijn voor de gebruiker. Dit betekent onder andere dat de tekst niet heel de tijd mag veranderen wanneer de camera een klein beetje verplaatst wordt en de nieuwe OCR-resultaten lichtjes zouden kunnen verschillen. Met andere woorden, eens er een goed resultaat is en de tekst in beeld blijft, zou het resultaat blijvend op het scherm te zien moeten zijn. • De gebruikersinterface zou zo minimaal mogelijk moeten zijn. Het hoofddoel van onze applicatie is een ’magic lens’ weergave van de realiteit, en de video staat dan ook centraal. Het is niet de bedoeling dat het scherm opgevuld wordt met vele widgets/buttons/options.
3
Geleverd werk en resultaten
Tijdens de eerste maand van onze thesis hebben wij voornamelijk onderzoek gedaan naar de verschillende delen die onze applicatie zal moeten bevatten. Die delen bestaan uit: • het lokaliseren van tekst in een afbeelding of video frame; • het uitsnijden van een tekstregio uit een afbeelding, en die regio klaarmaken voor OCR; • het onderzoeken van de mogelijkheden met betrekking tot OCR, om zo tekst te verkrijgen uit een afbeelding; • het onderzoeken van de mogelijkheden met betrekking tot het vertalen van tekst. Verder hebben we ook al bestaande applicaties die aan ons doel gerelateerd zijn alsook een aantal papers die het totaalconcept beschrijven, bekeken.
3.1
Algemene papers
Tijdens onze literatuurstudie vonden we vier papers die een applicatie beschreven met eenzelfde functie als de gerelateerde applicaties die in paragraaf 3.6 besproken worden. Tabel 1 vat de functionaliteit van de applicaties beschreven in de papers [M et al., 2005, Watanabe et al., 2003, Fragoso et al., 2011, Yang et al., 2002] kort samen. Paper
Video/ Afbeelding
Herkent Japans/ Chinees Ja
Vertaling
Opmerkingen
Afbeelding
Textdetectie: Manueel/ Automatisch Manueel
[1]
Neen
[2]
Afbeelding
Manueel
Ja
Ja
[3] [4]
Video Video
Manueel Automatisch
Neen Ja
Ja Ja
Detecteert woord het dichts bij het midden van het scherm. Resultaat kan naar ander programma (bv. woordenboek) verzonden worden. Geselecteerde tekstregio wordt naar server verstuurd voor OCR en vertaling. Vertaling via Google Translate. Gebruiker kan ook expliciet regio aanduiden indien nodig.
Tabel 1: Vergelijking tussen de applicaties die besproken worden in de algemene papers
3
3.2
Detectie en lokalisatie van tekst
Als deel van onze literatuurstudie hebben we gekeken naar papers over het detecteren en lokaliseren van tekst in afbeeldingen een video streams. We vatten hieronder onze conclusies uit de belangrijkste papers samen. In [Jung et al., 2004] wordt een overzicht gegeven van de verschillende technieken om tekst te detecteren en te localizeren. Er worden vier grote klassen aangehaald: region-based methodes (waaronder connected component-based en edge-based methodes), texture-based methodes (gebruik makend van onder andere Gabor Alters, Wavelet, Fast Fourier Transform (FFT) en spatial variance), tekst extractie in het gecomprimeerde domein (bijvoorbeeld rechtstreeks uit JPEG of MPEG) en binairizatie technieken (met onder andere global, local en adaptive thresholding). [JAIN and YU, 1998] is al een relatief oude paper. Er worden tijden gerapporteerd die lopen van 0.09 tot 0.40 seconden (afhankelijk van de grootte van de afbeelding). Hier staat wel niet bij op welk soort processor. De nauwkeurigheid gaat van 72% tot 99,2%. Verder worden een aantal statistische kenmerken gebruikt om te bepalen of een bepaald deel van de afbeelding tekst is of niet. We zijn niet zeker of deze kenmerken ook voor Japanse karakters gelden. Het algoritme dat in [Ye et al., 2003] beschreven wordt, heeft gemiddeld 0,23 seconden nodig op een Pentium IV. Dit is mogelijk te traag voor onze applicatie al kunnen sommige van hun idee¨en misschien wel gebruikt worden in combinatie met de idee¨en uit andere papers. In [Lyu et al., 2005] wordt een algoritme beschreven dat gebruik maakt van taalinvariante eigenschappen. Zo kan het algoritme goede resultaten halen wanneer talen zoals Engels en Chinees gecombineerd worden. We kregen wel het idee dat deze technieken bedoeld zijn voor het detecteren van tekst die achteraf toegevoegd werd aan de afbeelding of de video (zoals ondertitels) en niet voor tekst uit de afbeelding zelf. Verder wordt er ook niet aangegeven hun snel het algoritme werkt en of het dus bruikbaar is voor real-time detectie. [Ye et al., 2005] beschrijft een algoritme dat in staat is om tekst te lokaliseren in verschillende richtingen. Dit is zeker nuttig omdat Japans zowel in horizontale als in verticale richting geschreven wordt en ook omdat perspectiefvervormingen er voor kunnen zorgen dat de tekst niet recht staat. De nauwkeurigheid bedraagt 94,2% recall rate (#correct gedetecteerde tekstregio’s/#textregio’s) en 2,4% false alarm rate (#foutief gedetecteerde tekstregio’s/#gedetecteerde tekstregio’s). De gemiddelde snelheid bedraagt 8,3 afbeeldingen/s op een Pentium IV. De laatste twee papers [Chen et al., 2004] en [Kim et al., 2005] zijn het meest interessant omdat deze specifiek gaan over het detecteren en lokaliseren van omgevingstekst. Het algoritme in [Chen et al., 2004] werd ontworpen voor het detecteren van tekst op borden om deze dan te kunnen vertalen. In [Kim et al., 2005] worden drie technieken besproken om tekst in een natuurlijke omgeving te detecteren en lokaliseren.
3.3
Corrigeren van tekstregio’s
In onze literatuurstudie hebben we ook gekeken naar papers in verband met het corrigeren van tekstregio’s. Dit om bijvoorbeeld perspectiefvervormingen of slechte belichting aan te passen. In [Mollah et al., 2010] wordt een techniek besproken om tekstregio’s op afbeeldingen van visitekaartjes te corrigeren. Hierbij wordt de tekst wel geroteerd, maar gebeurt er geen volledige perspectiefcorrectie. We zijn reeds begonnen aan het implementeren van deze techniek (zonder het wegfilteren van bedrijfslogo’s) om te kijken of dit al behoorlijke resultaten oplevert. Het algoritme leek echter niet goed te werken op onze testafbeeldingen. De berekende rotatiehoek was steeds 0 of bijna 0, zelfs wanneer visueel duidelijk was dat dit heel wat groter zou moeten zijn. We hebben het algoritme daarom aangepast door lineaire regressie te gebruiken voor het bereken van de rotatiehoek. Dit wordt zowel boven als onder de tekst gedaan en dan wordt het gemiddelde genomen tussen de twee hoeken. [Tong and Zhang, 2010] beschrijft een algoritme om perspectief correctie uit te voeren op een tekstblok. Het resultaat hiervan is een binaire afbeelding, wat in principe ook betere OCR resultaten zou moeten geven. We zijn echter niet zeker of deze methode ook werkt op ´e´en enkele regel tekst, aangezien hun voorbeeld een grote tekstblok was.
4
De methode in [Monnier et al., 2005] is gebaseerd op tekstdocumenten. Hoewel deze typisch meerdere lijnen tekst bevatten en borden meestal niet, is het misschien toch mogelijk om deze methode te gebruiken. De enige voorwaarde is dat we in staat moeten zijn om de basislijn van de tekst te detecteren. Hieruit kunnen dan hopelijk de benodigde vluchtpunten berekend worden. Als dit het geval is kan een perspectiefcorrectie uitgevoerd worden.
3.4
OCR
Omdat OCR-technieken ontwikkelen en verbeteren waarschijnlijk een thesis op zich is, zijn we op zoek gegaan naar bestaande OCR-engines die eenvoudig ge¨ıntegreerd kunnen worden in een andere applicatie. We hebben vier engines (nhocr5 , Tesseract6 , Tesjeract7 en Asprise8 ) en een Cloud service (WiseTREND OCR Cloud 2.09 ) gevonden. Voor het uittesten van de engines hebben we afbeeldingen gebruikt van Japanse borden, die we manueel bijgesneden hebben tot ze alleen de tekst bevatten. Deze afbeeldingen zijn te vinden in appendix C. De resultaten vindt u in tabel 2. Merk op dat Asprise in deze tabel niet voor komt. Dit komt omdat Asprise geen enkel karakter herkende uit heel duidelijke, zelfgemaakte afbeelding, wat ons deed besluiten dat Asprise geen Japans ondersteund. Ook Tesjeract komt niet voor omdat dit een Java Native Interface (JNI) wrapper is voor Tesseract. Verder was er geen gratis testversie van WiseTREND OCR Cloud 2.0, maar werden we verwezen naar een testversie van ABBYY FineReader 11 Professional. We gaan er vanuit dat dit betekent dat die resultaten gelijk zijn (of op zijn minst erg gelijkaardig zijn) aan die van WiseTREND OCR Cloud 2.0. Afbeelding
Originele tekst
nhocr
Tesseract
Afbeelding 2 (b) Afbeelding 2 (c) Afbeelding 3 (b) Afbeelding 3 (c) Afbeelding 3 (d) Afbeelding 3 (e) Afbeelding 4 (b) Afbeelding 4 (c) Afbeelding 5 (b)
自転車を除く 一方通行 自転車を除く 一方通行 止まれ
... 掩¢簸空 ... 方通行 *\Yi
曼自転車を際く 方 各蓉奪ー 方 辟ま雜
止まれ
\.Yi
滞牢蕗蓬
日曜・休日を除く
9E.ffB..\.
旦曼休曰覆際く
日曜・休日を除く
壁舶燕
聾苳休曰覆扁く
略休日を除く
歩行者優先
.#..%
歩行者塵塁
歩行者優先
歩行者優先
.#.fj%
歩行者厦塁
歩行者優先
駐車場
s\. .
Afbeelding 5 (c) Afbeelding 5 (d) Afbeelding 5 (e) Afbeelding 6 (b) Afbeelding 6 (c)
駐車場
. .L.
軍場
この先50m
蛾Wi
塾先5[]m
この先50m
蛾Wi
望先5[1m
進入禁止
.A.k
進入禁止
進入禁止
進入禁止
.A.k
造入禁止
進入禁止
場 /ヨト 齡I
5 http://code.google.com/p/nhocr/ 6 http://code.google.com/p/tesseract-ocr/ 7 http://code.google.com/p/tesjeract/ 8 http://asprise.com/product/ocr/index.php?lang=java 9 http://www.wisetrend.com/wisetrend
ABBYY FineReader 自転車を除ぐ 方通行 自転車を除ぐ 方通行
ocr cloud.shtml
5
しぬ先50111
Afbeelding 7 (b) Afbeelding 7 (c) Afbeelding 8 (b)
Afbeelding 8 (c)
Afbeelding 9 (b) Afbeelding 9 (c) Afbeelding 10 (b) Afbeelding 10 (c) Afbeelding 10 (d)
Afbeelding 10 (e)
御 見 舞 御 見 舞 火 気 厳 禁
抑見癖
ˆ見舞
拿 ぃーー丶ヤ /篆 ヘ ュ ,t塁淵. 附臀蕗 綬濡く 襄杆鵬いて襄 丶I 遁几ノ 苳 jf 几 蔓誓蔓莫 丶丶ベ 儀 牢遷 丁實翁’ 蘆 ,1、實 ゴ こ亨寅一糞エ ユ1 . 4 爽気厳禁
火気厳禁
第2タ ー ナ ル 連 絡 バスのリ逆 第2ターミナル連輅 ノ《スのりば 乗り継ぎ案内
火 気 厳 禁 第2ターミナル連 絡バスのりば 第2ターミナル連 絡バスのりば 乗り継ぎ案内
£沙→.
乗り継ぎ案内
藁2夕ーミナ丿と實 鱸ノてスのりば 第2夕ーミナル迫格 ノ奮スのりば 棄リ継ぎ案内
乗り継ぎ案内
乗り継ぎ案内
棄り継ぎ案内
乗り継ぎ案内
第1旅 客 タ ー ミ ナ ル航空会社 全日空 エアージャパン アエロフロート・ ロシア航空 アエロメヒコ航空
全日空 エアージヤバン es ア エ ロ7口 ‐卜 ロシ7k空 アエ口メヒコG空
鼻†轍 暮夕 ー ミ ナ ル齟輩箋社 全日畳 六 エ アナジヤ ぴ ビ 声ー、 e註 軍 圭 三 實 哀 口 广i号二目霊夏鬘三 アエ囗メヒコ鷺塁
第1旅 客 タ ー ミ ナ ル航空会社 全日空 エアージャパン アエロフロート・ ロシア航空 アエロメヒコ航空
P-さナW瓦理 全B空 エア-ジヤバン es 7エロ7ロ‐卜ロ シアf空 アエロメヒコt空
罵】旅賣ターミナ ル隴空箋社 全曰寶剛所ー エアージヤバン Bsフ7蕗 二1二 百フ口 誓トて 三 聖 箇鷺翼 アエ口メヒコ黛蔓
第1旅客ターミナル 航空会社 全曰空 ―一圈圓圍國麵ー 圈丨國,...國― エアージヤノ\ン 03ア エ ロ フ ロー卜ロシア鎮空 アエロメヒコ航空 第1旅客ターミナル 航空会社 全曰空 エアージヤノ\ン 丨 05ア エ ロ フ ロ ー卜ロ シ ア 航空 アエロメヒコ航空
£z>\.
Tabel 2: Vergelijking van de verschillende OCR-engines
6
気厳禁
3.5
Vertaalmogelijkheden
Aangezien geen van ons beide enige taalstudie heeft gevolgd (en dit evenmin de kern van onze thesis is), hebben we besloten om een bestaande vertaalservice aan te spreken voor de vertalingen. In een eerste iteratie hebben we gezocht naar bestaande online vertaalservices. De services die we bekeken hebben zijn: Google Translate10 , Bing Translator11 , SYSTRANLinks12 , InterTran13 , WordLingo14 , myGengo15 , OneHourTranslation16 en Apertium17 . Apertium kan Japans niet naar Engels vertalen en InterTran’s online demo voor Japans naar Engels werkt niet. myGengo en OneHourTranslation zijn beide services die geen gebruik maken van machine translations (MT), aldus zijn de resultaten niet realtime. De vier overgebleven services hebben allemaal de mogelijkheid om via HTTP (HyperText Transfer Protocol) een API (Application Programming Interface) aan te spreken en zo vertalingen uit te voeren. Deze vier services hebben we dan in een tweede iteratie met elkaar vergeleken. Een objectieve vergelijking van MT werd uitgevoerd op basis van drie veelvoorkomende scores: BLEU (beschreven in [Papineni et al., 2002]), NIST(beschreven in [Doddington, 2002]) en F-Measure (beschreven in [Turian et al., 2003]). Deze waardes vergelijken de resultaten van de MT met referentievertalingen. Uit de berekende score kan men niet de kwaliteit van een vertaalservice aflezen, maar de scores kunnen wel vergeleken worden om te bepalen welke service beter is (waarbij een hogere score beter is). De vergelijking werd uitgevoerd op basis van een set van 100 zinsparen18 Japans - Engels (beschreven in [Utiyama and Isahara, 2003]). De 100 Japanse zinnen bestaan in het totaal uit 3952 karakters (inclusief spaties en punctuatie). De referentievertaling in het Engels heeft in het totaal 1633 woorden. Merk op dat we slechts ´e´en referentievertaling gebruikt hebben, terwijl er vaak meerdere gebruikt worden. Deze hadden we echter niet voorhanden. De resultaten van deze vergelijking zijn terug te vinden in tabel 3. Service Google Translate Bing Translator SYSTRAN WordLingo
BLEU 0.2922 0.2206 0.1022 0.1020
NIST 5.9703 5.5123 3.9890 3.9856
F-Measure 0.6413 0.5885 0.4880 0.4884
Tabel 3: Vergelijking tussen de verschillende vertaalservices Uit deze resultaten kunnen we concluderen dat Google Translate de beste resultaten geeft. We plannen nog wel een extra test-set specifiek gebaseerd op tekst komende van (verkeers-)borden, maar de vertaling van deze set laat nog even op zich wachten...
3.6
Vergelijking van gerelateerde applicaties
We hebben een aantal bestaande apps uitgeprobeerd die lijken op ons doel. Deze apps zijn: Word Lens19 en Pleco20 voor iPhone, en WWWJDICT21 , QQ慧眼 (QQ Hui Yan)22 , Mezzofanti23 en OCR Test24 voor Android. Tabel 4 vergelijkt de verschillende apps en vat alsook de mogelijkheden ervan kort samen.25 10 http://translate.google.com/ 11 http://www.microsofttranslator.com/ 12 http://www.systran.co.uk/translation-products/online-services/systranlinks 13 http://www.tranexp.com/#intertrananchor 14 http://www.worldlingo.com/ 15 http://mygengo.com/ 16 http://www.onehourtranslation.com/ 17 http://wiki.apertium.org/wiki/Main
Page set kan gevonden worden op http://mastarpj.nict.go.jp/%7Emutiyama/jea/ 19 http://itunes.apple.com/be/app/word-lens/id383463868?l=nl&mt=8 20 http://itunes.apple.com/us/app/pleco-chinese-dictionary/id341922306?mt=8 21 https://market.android.com/details?id=org.nick.wwwjdic 22 https://market.android.com/details?id=com.tencent.qqvision 23 http://code.google.com/p/mezzofanti/ 24 https://market.android.com/details?id=edu.sfsu.cs.orange.ocr 25 Een meer gedetaileerde evaluatie van de verschillende apps kan teruggevonden worden op onze thesis blog: http://augmentjapan.wordpress.com/2011/10/23/evaluating-related-apps/ http://augmentjapan.wordpress.com/2011/10/28/evaluating-related-apps-2-0/ 18 De
7
Applicatie
Video/ Afbeelding
Herkent Japans/ Chinees
Video Beide
Tekstdetectie: Manueel/ Automatisch Automatisch Manueel
Neen Ja
Herkent verticale tekst Neen Ja
Word Lens Pleco
Vertaling
WWWJDICT
Afbeelding
Manueel
Ja
Neen
QQ慧眼
Beide
Video: Manueel; Afbeelding: Automatisch
Ja
Neen
Ja, woord per woord
Mezzofanti
Afbeelding
Manueel
Neen
Neen
Ja
OCR Test
Beide
Manueel
Ja
Neen
Ja
Ja Ja, woord per woord Niet op OCR resultaten
Opmerkingen
Bevat meer dan enkel OCR, heeft ook een ingebouwd woordenboek, etc. Video: herkent enkel woord in het midden van het scherm Afbeelding: probeert alle woorden te herkennen Heeft voorgeselecteerde regio voor tekstdetectie. Vertaling via Google Translate. Vertaling enkel op basis van een afbeelding. Video geeft wel OCRresultaten. Vertaling via Google Translate of Bing Translator.
Tabel 4: Vergelijking tussen de verschillende applicaties
4
Planning
In afbeelding 1 ziet u een Gantt chart van onze planning. De kleuren duiden verschillende categorie¨en van taken aan. Alles wat in het verleden ligt (zoals onder andere het schrijven van het verslag) wordt niet weergegeven. ”Schrijven thesistekst” op het einde gebeurt strikt gezien in twee periodes. In de eerste, van 7 mei tot en met 18 mei, werken we aan een eerste draft-versie, die dan ingediend moet worden. Wanneer we deze terugkrijgen, kunnen we deze dan herwerken tot de uiteindelijke thesistekst. Aangezien we deze correctie waarschijnlijk niet meteen terugkrijgen, dient de periode vanaf 19 mei ook als bufferperiode voor de laatste vergelijkende gebruikerstesten. Dit voor het geval bepaalde voorgaande onderdelen uitlopen ten opzichte van de planning.
8
Afbeelding 1: Gantt chart
9
5
Belangrijkste moeilijkheden
Bij het lezen van de papers zijn we op drie belangrijke moeilijkheden gestoten: tekstlokalisatie, teksttracking en tekstcorrectie.
5.1
Tekstlokalisatie
Wanneer men tekst uit een afbeelding of video van een natuurlijke omgeving wil halen om deze daarna te vertalen, zijn er een aantal problemen die opduiken. In de eerste plaats is er een goede methode nodig om tekst in zo’n afbeelding of video te herkennen. Een eerste optie is de gebruiker van de applicatie te laten aangeven waar de tekst zich bevindt. Dit kan bijvoorbeeld door een kader rond de tekst te trekken, maar ook door de gebruiker de tekst kort te laten aanduiden. Een elegantere optie is natuurlijk om dit automatisch te laten gebeuren, wat uiteraard extra moeilijkheden met zich meebrengt. Zo moet de methode niet alleen accuraat zijn, maar ook in een degelijke tijdsspanne gebeuren. Men kan uiteraard niet verwachten dat gebruikers hun camera 1 minuut stil houden om te wachten tot de tekst gelokaliseerd is.
5.2
Teksttracking
Omdat het proces “tekst lokaliseren - OCR - vertalen” behoorlijk intensief is, is het belangrijk om tekst ook te kunnen tracken in een video. Dit laat toe om slechts eenmaal de OCR en vertaling uit te voeren om toch de vertaling te kunnen blijven weergeven aan de gebruiker. Tracking moet daarom op minder dan een framelengte gebeuren, om ook tijd te geven aan o.a. de lokalisatie module, zodat ook nieuwe tekst gedetecteerd kan worden. Er bestaat weinig onderzoek over methodes om tekst in een video te tracken. Dit op zichzelf zal enkele moeilijkheden introduceren in het vervolg van onze de uitwerking.
5.3
Tekstcorrectie
Wanneer gebruikers rondlopen met hun camera, zullen ze niet altijd recht voor de tekst staan. Ook de belichting zal niet altijd overal op het bord gelijk zijn en er kan vuil op het bord hangen of de tekst kan deels vervaagd zijn. Omdat al deze omstandigheden en ook nog vele anderen een negatieve invloed hebben op de kwaliteit van de OCR-resultaten is het belangrijk om deze zo goed mogelijk te kunnen corrigeren.
6
Dit werk verdient...
... een 17/20. Dit omdat we vinden dat we het geleverd werk grondig aangepakt hebben. We hebben niet alleen papers gelezen over alle onderdelen van ons thesisonderwerp, maar ook over het vergelijken van bijvoorbeeld vertaalservices. We kunnen ook al raporteren over een aantal resultaten, zoals onder andere de vergelijking van: vier online vertaalservices, drie OCR-engines en zes gerelateerde, bestaande applicaties. We hebben op dit moment nog geen storyboard, dit omdat we nog even de resultaten van onze enquˆete afwachten.
Referenties X. Chen, J. Yang, J. Zhang, and A. Waibel. Automatic detection and recognition of signs from natural scenes. Image Processing, IEEE Transactions on, 13(1):87 –99, jan. 2004. ISSN 1057-7149. doi: 10.1109/TIP.2003.819223. G. Doddington. Automatic evaluation of machine translation quality using n-gram co-occurrence statistics. In Proceedings of the second international conference on Human Language Technology Research, HLT ’02, pages 138–145, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc. V. Fragoso, S. Gauglitz, S. Zamora, J. Kleban, and M. Turk. Translatar: A mobile augmented reality translator. In Applications of Computer Vision (WACV), 2011 IEEE Workshop on, pages 497 –502, jan. 2011. doi: 10.1109/WACV.2011.5711545. A. K. JAIN and B. YU. Automatic text location in images and video frames. Pattern Recognition, 31 (12):2055 – 2076, 1998.
10
K. Jung, K. I. Kim, and A. K. Jain. Text information extraction in images and video: a survey. Pattern Recognition, 37(5):977 – 997, 2004. ISSN 0031-3203. doi: 10.1016/j.patcog.2003.10.012. J. Kim, S. Park, and S. Kim. Text locating from natural scene images using image intensities. In Document Analysis and Recognition, 2005. Proceedings. Eighth International Conference on, pages 655 – 659 Vol. 2, aug.-1 sept. 2005. doi: 10.1109/ICDAR.2005.232. M. Lyu, J. Song, and M. Cai. A comprehensive method for multilingual video text detection, localization, and extraction. Circuits and Systems for Video Technology, IEEE Transactions on, 15(2):243 – 255, feb. 2005. ISSN 1051-8215. doi: 10.1109/TCSVT.2004.841653. K. M, R. Mine, T. Kameyama, T. Takahashi, M. Yamazaki, and T. Yamaguchi. Camera-based kanji ocr for mobile-phones: practical issues. In Document Analysis and Recognition, 2005. Proceedings. Eighth International Conference on, pages 635 – 639 Vol. 2, aug.-1 sept. 2005. doi: 10.1109/ICDAR.2005.65. A. F. Mollah, S. Basu, and M. Nasipuri. Text/graphics separation and skew correction of text regions of business card images for mobile devices. CoRR, abs/1002.4006, 2010. informal publication. C. Monnier, V. Ablavsky, S. Holden, and M. Snorrason. Sequential correction of perspective warp in camera-based documents. In Document Analysis and Recognition, 2005. Proceedings. Eighth International Conference on, pages 394 – 398 Vol. 1, aug.-1 sept. 2005. doi: 10.1109/ICDAR.2005.216. K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, ACL ’02, pages 311–318, Stroudsburg, PA, USA, 2002. Association for Computational Linguistics. doi: http://dx.doi.org/10.3115/1073083.1073135. L. Tong and Y. Zhang. Correction of perspective text image based on gradient method. In Information Networking and Automation (ICINA), 2010 International Conference on, volume 2, pages V2–312 –V2–316, oct. 2010. doi: 10.1109/ICINA.2010.5636501. J. Turian, L. Shen, and I. D. Melamed. Evaluation of machine translation and its evaluation. In In Proceedings of MT Summit IX, pages 386–393, 2003. M. Utiyama and H. Isahara. Reliable measures for aligning japanese-english news articles and sentences. In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics - Volume 1, ACL ’03, pages 72–79, Stroudsburg, PA, USA, 2003. Association for Computational Linguistics. doi: http://dx.doi.org/10.3115/1075096.1075106. Y. Watanabe, K. Sono, K. Yokomizo, and Y. Okada. Translation camera on mobile phone. In Multimedia and Expo, 2003. ICME ’03. Proceedings. 2003 International Conference on, volume 2, pages II – 177–80 vol.2, july 2003. doi: 10.1109/ICME.2003.1221582. J. Yang, X. Chen, J. Zhang, Y. Zhang, and A. Waibel. Automatic detection and translation of text from natural scenes. In Acoustics, Speech, and Signal Processing (ICASSP), 2002 IEEE International Conference on, volume 2, pages II–2101 –II–2104, may 2002. doi: 10.1109/ICASSP.2002.5745049. Q. Ye, W. Gao, W. Wang, and W. Zeng. A robust text detection algorithm in images and video frames. In Information, Communications and Signal Processing, 2003 and the Fourth Pacific Rim Conference on Multimedia. Proceedings of the 2003 Joint Conference of the Fourth International Conference on, volume 2, pages 802 – 806 vol.2, dec. 2003. doi: 10.1109/ICICS.2003.1292567. Q. Ye, Q. Huang, W. Gao, and D. Zhao. Fast and robust text detection in images and video frames. Image and Vision Computing, 23(6):565 – 576, 2005. ISSN 0262-8856. doi: 10.1016/j.imavis.2005.01.004.
11
Appendices A
Statistieken
Omdat we onze blogposts en blogcomments (op onze eigen blog) steeds samen geschreven hebben, vinden we het niet relevant deze uit te splitsen. Samen hebben we 13 blogposts en 9 blogcomments geschreven. Alle andere statistieken hebben we wel uitgesplitst. De algemene statistieken zijn te vinden in tabel 5, de uitgesplitste uren vindt u in paragraaf A.1 en A.2. Een aantal categorie¨en die gebruikt worden in tabel 6 en 7 moeten misschien nog even verduidelijkt worden. Onder de categorie “evaluatie” hebben we ook het evalueren van andere applicaties onder gebracht. De categorie “implementatie” bevat momenteel het implementeren van algoritmes uit papers, zodat we de verschillende OCR-engines beter kunnen evalueren. Tot slot hebben we ook een categorie “andere”, waaronder alles werd ondergebracht waarvan we vonden dat die niet meteen in ´e´en van de andere categorie¨en thuis hoorde. Het gaat hier dan bijvoorbeeld om het opstellen van de planning en de enquˆete.
Matthias Annelies
#comments op andere blogs 13 12
#tweets 85 59
totaal aantal uren 88:15 95:00
Tabel 5: Algemene statistieken
A.1
Matthias Categorie Eigen blog Blog anderen Literatuur Ontwerp Implementatie Evaluatie Verslag Meeting Andere Totaal
Uren 8:00 10:15 23:15 0:00 14:30 8:15 9:15 3:15 11:30 88:15
Tabel 6: Totaal aantal gewerkte uren voor Matthias, uitgesplitst in categorie¨en
A.2
Annelies Categorie Eigen blog Blog anderen Literatuur Ontwerp Implementatie Evaluatie Verslag Meeting Andere Totaal
Uren 10:00 5:30 24:00 0:00 16:45 8:00 17:15 3:15 10:15 95:00
Tabel 7: Totaal aantal gewerkte uren voor Annelies, uitgesplitst in categorie¨en
12
B
Bestudeerde literatuur en gerelateerd werk
B.1
Matthias
B.1.1
Skimmed
An Overview of the Tesseract OCR Engine (Ray Smith, 2007) A comprehensive method for multilingual video text detection, localization, and extraction (M. R. Lyu et al., 2005) A robust text detection algorithm in images and video frames (Qixiang Ye et al., 2003) Improvement of video text recognition by character selection (T. Mita and O. Hori, 2001) Kanji Character Detection from Complex Real Scene Images based on Character Properties (Lianli Xu et al., 2008) BLEU: a Method for Automatic Evaluation of Machine Translation (Kishore Papineni et al., 2002) Automatic evaluation of machine translation quality using n-gram co-occurrence statistics (George Doddington, 2002) An evaluation tool for machine translation: Fast evaluation for MT research (S. Nießen et al., 2000) Evaluation of machine translation and its evaluation (Joseph P. Turian et al., 2003) Using multiple edit distances to automatically grade outputs from Machine translation systems (Yasuhiro Akiba et al., 2006) Objective evaluation criteria for machine translation (A. J. Petit, 1977) Fast, cheap, and creative: Evaluating translation quality using Amazon’s Mechanical Turk (Chris CallisonBurch, 2009) Re-evaluating machine translation results with paraphrase support (Liang Zhou et al., 2006) Re-evaluating the Role of BLEU in Machine Translation Research (Chris Callison-Burch et al., 2006) JEIDA’s Test-Sets for Quality Evaluation of MT Systems: Technical Evaluation from the Developer’s Point of View (Hitoshi Isahara, 1995) Reliable measures for aligning Japanese-English news articles and sentences (Masao Utiyama and Hitoshi Isahara, 2003) A new robust algorithm for video text extraction (E. Wong, 2003)
B.1.2
Read
TranslatAR: A mobile augmented reality translator (Victor Fragoso et al., 2011) Camera-based Kanji OCR for Mobile-phones: Practical Issues (M Koga et al., 2005) Translation camera on mobile phone (Y. Watanabe et al., 2003) Kanji recognition in scene images without detection of text fields - robust against variation of viewpoint, contrast, and background texture (A. Suzuki et al., 2004) Translation and the Internet: Evaluating the Quality of Free Online Machine Translators (Stephen Hampshire and Carmen Porta Salvia, 2010) Comparative Evaluation of Online Machine Translation Systems with Legal Texts (Chunyu Kit and Tak Ming Wong, 2008) Correction of perspective text image based on gradient method (Lijing Tong and Yan Zhang, 2010) Sequential correction of perspective warp in camera-based documents (Camille Monnier et al., 2005) Text/Graphics Separation and Skew Correction of Text Regions of Business Card Images for Mobile Devices (Ayatullah Faruk Mollah et al., 2010) Multiple target detection and tracking with guaranteed framerates on mobile phones (D. Wagner et al., 2009) Real-time vision-based camera tracking for augmented reality applications (Dieter Koller et al., 1997) A real-time tracker for markerless augmented reality (A. I. Comport et al., 2003) Automatic detection and recognition of signs from natural scenes (Xilin Chen et al., 2004) Automatic detection and translation of text from natural scenes (Jie Yang et al., 2002) Video text recognition using feature compensation as category-dependent feature extraction (M. Mori, 2003) Fast and robust text detection in images and video frames (Q. Ye et al., 2005) Text locating from natural scene images using image intensities (Jisoo Kim et al., 2005) Automatic text location in images and video frames (A. K. Jain and Bin Yu, 1998) Text information extraction in images and video: a survey (K. Jung, 2004)
13
B.2
Annelies
B.2.1
Skimmed
An Overview of the Tesseract OCR Engine (Ray Smith, 2007) From Mirroring to Guiding: A Review of State of the Art Technology for Supporting Collaborative Learning (Amy Soller et al., 2005) Character extraction of license plates from video (Y. T. Cui and Q. Huang, 1997) A Fast Skew Correction Technique for Camera Captured Business Card Images (A. F. Mollah, 2009) Perspective Correction Methods for Camera-Based Document Analysis (L. Jagannathan and C. V. Jawahar, 2005) TextFinder: An Automatic System to Detect and Recognize Text In Images (Victor Wu et al., 1999) Locating text in complex color images (Y. Zhong et al., 1995) Text scanner with text detection technology on image sequences (T. Kurata and M. Kourogi, 2002) Marker-less Vision Based Tracking for Mobile Augmented Reality (D. Beier et al., 2003) Localizing and segmenting text in images and videos (Rainer Lienhart and Axel Wernicke, 2002) Automatic location of text in video frames (Xian-Sheng Hua et al., 2001) Text detection and segmentation in complex color images (C. Garcia and X. Apostolidis, 2000) Extraction of illusory linear clues in perspectively skewed documents (M. Pilu, 2001)
B.2.2
Read
TranslatAR: A mobile augmented reality translator (Victor Fragoso et al., 2011) Camera-based Kanji OCR for Mobile-phones: Practical Issues (M. Koga et al., 2005) Translation camera on mobile phone (Y. Watanabe et al., 2003) Comparative Evaluation of Online Machine Translation Systems with Legal Texts (Chunyu Kit and Tak Ming Wong, 2008) Evaluation of machine translation and its evaluation (Joseph P. Turian, 2003) Translation and the Internet: Evaluating the Quality of Free Online Machine Translators (Stephen Hampshire and Carmen Porta Salvia, 2010) ˘ Design-based research: what we learn when we engage in design of interactive systems (Zeljko Obrenovi´c, 2007) Correction of perspective text image based on gradient method (Lijing Tong and Yan Zhang, 2010) Text information extraction in images and video: a survey (K. Jung, 2004) Text/Graphics Separation and Skew Correction of Text Regions of Business Card Images for Mobile Devices (Ayatullah Faruk Mollah et al., 2010) Sequential correction of perspective warp in camera-based documents (Camille Monnier et al., 2005) Multiple target detection and tracking with guaranteed framerates on mobile phones (D. Wagner et al., 2009) Real-time vision-based camera tracking for augmented reality applications (Dieter Koller et al., 1997) A real-time tracker for markerless augmented reality (A. I. Comport et al., 2003) A comprehensive method for multilingual video text detection, localization, and extraction (M. R. Lyu et al., 2005) A robust text detection algorithm in images and video frames (Qixiang Ye et al., 2003) Automatic detection and recognition of signs from natural scenes (Xilin Chen et al., 2004) Automatic detection and translation of text from natural scenes (Jie Yang et al., 2002) Automatic text location in images and video frames (A. K. Jain and Bin Yu, 1998) Fast and robust text detection in images and video frames (Q. Ye et al., 2005) Text locating from natural scene images using image intensities (Jisoo Kim et al., 2005) Video text recognition using feature compensation as category-dependent feature extraction (M. Mori, 2003)
14
C
Extra afbeeldingen
(a)
(b)
(c)
Afbeelding 2: (a) volledige foto (b) kleur (c) grijswaarden
(a)
(b)
(c)
(d)
(e)
Afbeelding 3: (a) volledige foto (b) bovenaan kleur (c) bovenaan grijswaarden (d) onderaan kleur (e) onderaan grijswaarden
(a)
(b)
(c)
Afbeelding 4: (a) volledige foto (b) kleur (c) grijswaarden
(a)
(b)
(c)
(d)
(e)
Afbeelding 5: (a) volledige foto (b) bovenaan kleur (c) bovenaan grijswaarden (d) onderaan kleur (e) onderaan grijswaarden
15
(a)
(b)
(c)
Afbeelding 6: (a) volledige foto (b) kleur (c) grijswaarden
(a)
(b)
(c)
Afbeelding 7: (a) volledige foto (b) kleur (c) grijswaarden
(a)
(b)
(c)
Afbeelding 8: (a) volledige foto (b) kleur (c) grijswaarden
16
(a)
(b)
(c)
Afbeelding 9: (a) volledige foto (b) kleur (c) grijswaarden
(a)
(b)
(c)
(d)
(e)
Afbeelding 10: (a) volledige foto (b) bovenaan kleur (c) bovenaan grijswaarden (d) onderaan kleur (e) onderaan grijswaarden
17