Je leest:

Computer puzzelt manuscripten bij elkaar

Computer puzzelt manuscripten bij elkaar

Auteur: | 2 november 2011

De Cairo Geniza – een verzameling Joodse manuscripten – geeft een uniek kijkje in de geschiedenis tussen 950 en 1250 na Christus. Helaas zijn de blaadjes verspreid over musea en bibliotheken overal ter wereld. Onderzoekers proberen nu met de computer de fragmenten weer bij elkaar te brengen.

Rond 1800 werden ze ontdekt en nu zijn ze verspreid over de hele wereld: manuscriptfragmenten uit de geniza (opslagruimte) van een synagoog in Cairo, Egypte. Omdat het gebruikelijk is documenten in geniza’s na verloop van tijd te verbranden, zijn de manuscripten erg bijzonder. De Cairo Geniza (zo heet de verzameling) geeft een uniek kijkje in de geschiedenis tussen 950 en 1250 na Christus.

Veel van de manuscriptfragmenten van de Cairo Geniza werden gevonden in de Ben Ezra Synagogue in Fustat, in het oude deel van Cairo (Egypte).

Helaas is het voor wetenschappers niet eenvoudig de documenten te bestuderen, omdat ze opgeslagen zijn in verschillende bibliotheken. De grootste verzameling fragmenten — ongeveer 193.000 van de 280.000 stukjes — bevindt zich in Cambridge (Engeland), maar er zijn ook grote collecties in New York (VS) en Manchester (Engeland). Gelukkig worden steeds meer fragmenten gedigitaliseerd. Er is echter nog steeds een probleem: welke fragmenten horen bij elkaar en vormen samen een manuscript?

Met de computer

Onderzoekers van Tel Aviv University (Israel) en het Friedberg Genizah Project hebben een systeem ontwikkeld dat zogeheten joins kan bepalen; groepen fragmenten die afkomstig zijn uit hetzelfde document. Met beeldverwerkingstechnieken analyseren ze een verzameling gescande bladzijden en op basis daarvan beoordelen ze steeds of twee fragmenten bij elkaar horen.

Het vergelijken van twee gescande bladzijden bestaat uit meerdere stappen. Elk fragment wordt voorbewerkt (figuur links) en daarna op twee manieren geanalyseerd (figuur rechts). Op basis van de analyse wordt bekeken of ze bij elkaar horen.
Wolf et al., 2011

Wat het analyseren onder andere moeilijk maakt, is dat er bij het scannen geen rekening is gehouden met eventuele automatische analyse. Dat wil zeggen, de achtergrond is niet altijd hetzelfde, de fragmenten liggen niet per se recht, soms is er een liniaal in beeld gelegd, etc. De foto moet daarom worden bewerkt voordat er metingen kunnen worden gedaan. Dat zie je in het linker plaatje hierboven: het systeem selecteert eerst het fragment in de foto, zet het recht en maakt er een zwart-wit plaatje van (zodat de computer er snel mee kan werken).

Waar zijn de rechte lijnen?

Een van de stappen bij de analyseren is het bepalen van de oriëntatie van de regels: staat de tekst recht of ietsje schuin en hoeveel dan? Het systeem gebruikt hiervoor de Hough-transform van het plaatje, een veelgebruikte techniek om de rechte lijnen in een afbeelding te bepalen.

Voor het maken van de Hough-transform wordt eerst voor elke pixel bepaald op welke rechte lijnen het zou kunnen liggen (zie illustratie hieronder).

Het zwarte punt kan onder andere liggen op de rode, groene of blauwe lijn.

De mogelijke lijnen zijn te omschrijven met de formule x*cos(t) + y*sin(t) = R, waarbij R de lengte is van de normaal tussen de oorsprong en de lijn in kwestie, en t de hoek tussen de normaal en de x-as. Als je hiervan uitgaat, kun je voor elke pixel in het plaatje een lijstje maken van R/t-combinaties, waarbij elke combinatie staat voor een bepaalde lijn waarop het punt kan liggen. Als je dat lijstje plot (de t op de x-as en de R op de y-as), krijg je dus voor elke pixel een reeks punten die je kunt verbinden. Deze plot — met voor elke pixel van het plaatje een lijn — heet de Hough-transform.

De Hough-transform brengt de rechte lijnen op de foto in kaart. Een witte vlek in de plot geeft namelijk aan dat er veel pixels zijn die op een lijn liggen met een bepaalde R/t-combinatie. Oftewel, die pixels liggen op dezelfde lijn. En aangezien het gaat om veel pixels, is het waarschijnlijk een lijn die ook duidelijk zichtbaar is in de foto.

Links zie je twee rechte lijnen aangegeven op de foto: de roze lijn heeft een kleine, negatieve t en een kleine R, de groene lijn heeft een grote t (ongeveer 90) en een grote R. De pixels van zo’n rechte lijn hebben in de Hough-transform allemaal een punt bij die bepaalde R/t-combinatie; daar komt dus een grote witte plek. Dat zie je in de rechter figuur. Bij een grote t en grote R (rechtsboven) zit een witte plek en die correspondeert dus met de groene rechte lijn aangegeven op de foto.

Recht lezen

De foto’s van de Cairo Geniza bevatten geen echte rechte lijnen, maar de pixels van de letters op een regel liggen wel steeds op een lijn. Dat zie je terug in de Hough-transform (zie hieronder), want als je goed kijkt, zie je bij -90° en +90° tien losstaande lijnen: die corresponderen met de tien regels tekst die horizontaal op het vel staan.

De regels tekst op het blad corresponderen met de afzonderlijke lijnen in de Hough-transform.
Wolf et al., 2011

De computer kan berekenen waar die duidelijke lijnen te zien zijn, want dat is bij de t waar de variantie het hoogst is. Zo bepaalt het systeem hoe de regels tekst op papier staan: is de variantie bijvoorbeeld het hoogst bij t=45, dan staat de tekst gedraaid in een hoek van 45°.

Van tekst naar getallen

De oriëntatie van de tekst is van belang, omdat het systeem een projection profile maakt van de tekst. Dan worden de pixels per kolom bij elkaar opgeteld, horizontaal en verticaal (zie afbeelding hieronder). Als je dit profiel maakt zonder te letten op de draaiing van de tekst, klopt er weinig van het resultaat.

De stok van de p bevat bijvoorbeeld veel pixels en op die plek heeft het profiel dan ook een hoge waarde.

Aan de hand van het profiel meet het systeem een aantal kenmerken van de tekst, zoals het aantal regels, de regelafstand en de hoogte van een regel. Dit zijn de ‘fysieke metingen’ in het schema aan het begin van dit artikel. Voor het analyseren van het handschrift detecteert het systeem ook de keypoints van de afbeelding; punten in het fragment die extra opvallen. Hiervoor gebruikt het de SIFT-techniek (zie kader).

SIFT

SIFT staat voor scale invariant feature transform. Het is een methode om punten op de afbeelding te vinden die zo kenmerkend zijn, dat ze ook terug te vinden zijn op een andere foto van hetzelfde onderwerp. De techniek zoekt vooral plekken waar er een groot verschil is tussen donker en licht, zoals aan de rand van een object. In het artikel ‘3D van platte foto’s’ lees je meer over het gebruik van SIFT-keys.

De fysieke metingen en de keypoints zijn eigenlijk niets anders dan getallen. Het manuscriptfragment wordt zo dus vertaald in een rij van waarden, dat noem je de feature vector. Een computer kan daar gemakkelijker mee overweg dan met een plaatje.

Aanleren

Nu gaan we terug naar het oorspronkelijke doel: bepalen of twee fragmenten tot hetzelfde document behoren. Hiervoor kijk je naar de feature vectors van de twee stukjes. Hoe meer die op elkaar lijken, hoe waarschijnlijker het is dat de teksten uit één document komen. Ze hebben dan namelijk ongeveer dezelfde lettergrootte, regelafstand en/of keypoints. Maar hoe weet je hoe gelijk twee feature vectors zijn, of beter gezegd, hoe weet de computer dat? In feite is dat een kwestie van aanleren.

In het systeem bevindt zich een classifier, een (wiskundig) programma dat van een ingevoerd object, zoals een feature vector, kan bepalen in welke groep het thuishoort. Oftewel, als je een manuscriptfragment hebt, geeft de classifier aan tot welk document het behoort. Daarvoor moet het programma wel weten hoe het een object moet beoordelen; wanneer behoort iets tot groep A (document A) en wanneer niet? Dat leer je de classifier aan met een training set, een verzameling fragmenten waarvan je weet welke bij elkaar horen. De classifier leert met die informatie wat de ene groep onderscheidt van de andere. In onderstaande figuur zie je bijvoorbeeld dat je op basis van de grootte van het bloemblad kunt weten met welk type iris je te maken hebt.

Elke stip is een bloem: een Iris Setosa is weergegeven met blauw, een Iris Versicolor met rood en een Iris Virginica met groen. De plek van een stip hangt af van de gemeten lengte en breedte van het bloemblaadje. Zo zie je dat de Sotasa-variant beduidend kleinere blaadjes heeft dan de andere soorten.

Nieuwe paren

Van de Cairo Geniza maakten de onderzoekers een training set met bekende joins; paren fragmenten die zeker weten bij elkaar horen. Hiermee leerde de classifier te beoordelen wanneer er sprake is van een join. Toen de onderzoekers vervolgens nieuwe fragmenten per twee invoerden, kon de classifier zeggen ze wel of geen join waren.

De resultaten waren wisselend. Bij een test op de collectie van één instituut klopte het in tachtig procent van gevallen. Er werd echter ook een test gedaan met fragmenten afkomstig uit verschillende collecties, waar het systeem vooral handig voor is (dan hoeven onderzoekers niet heen en weer te reizen). Hier kwam het systeem met negenduizend mogelijke joins, waarvan de top tweeduizend handmatig werd geïnspecteerd. Slechts vierentwintig procent van de gedetecteerde joins bleek correct.

Dit zijn twee van de joins die zijn gevonden met de computer.
Wolf et al., 2011

Ondank de enigszins tegenvallende resultaten, heeft het onderzoek toch zo’n duizend nieuwe joins opgeleverd. Dat is best veel in vergelijking met de paar duizend die experts tot nu toe hebben gevonden. Het systeem kan echter nog niet zonder handmatige controle functioneren, daarvoor is de herkenningsscore te laag. Maar een mooie aanvulling en een stap in de goede richting is het wel.

Bron

Wolf et al., ‘Identifying Join Candidates in the Cairo Genizah’, Int. J. Comput. Vision 94, 1 (August 2011), 118-135. doi: 10.1007/s11263-010-0389-8

Lees meer over beeldverwerking en -herkenning op Kennislink:

Oeps: Onbekende tag `feed’ met attributen {"url"=>"https://www.nemokennislink.nl/kernwoorden/beeldherkenning/patroonherkenning/beeldverwerking/index.atom?m=of", “max”=>"7", “detail”=>"minder"}

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 02 november 2011

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.