Analýza struktury dokumentu

Mendelova univerzita v Brně Provozně ekonomická fakulta

Analýza struktury dokumentu Diplomová práce

Vedoucí práce: Ing. Petra Talandová, Ph. D.

Bc. Tereza Nováčková

Brno 2010

Zde bych ráda poděkovala především vedoucí mé diplomové práce ing. Petře Talandové, Ph. D. za rady a nápady, které mi velmi pomohly.

Prohlašuji, že jsem tuto práci vyřešila samostatně s použitím literatury, která je uvedena v seznamu v závěru práce.

V Brně dne 24. května 2010

....................................................

Abstract Nováčková, T. Document structure analysis. Diploma thesis. Brno, 2010. Diploma thesis deals with document analysis based on structure. This thesis concurs on thesis Automated documents quality recognition (Talandová, 2009). Produce of this thesis is except survey of current situation in this research area also project solution for creation web application that in future would be principle for document quality recognition. Keywords document analysis, structure, method

Abstrakt Nováčková, T. Analýza struktury dokumentu. Diplomová práce. Brno, 2010. Diplomová práce se zabývá analýzou dokumentu založenou na struktuře. Práce navazuje na práci Automatizované hodnocení kvality dokumentů (Talandová, 2009). Výsledkem práce je kromě přehledu současné situace v této oblasti výzkumu také návrh řešení pro vytvoření webové aplikace, která by měla v budoucnu sloužit jako základ pro hodnocení kvality dokumentů. Klíčová slova analýza dokumentu, struktura, metoda

4

Obsah 1 Úvod a cíl práce 1.1 Úvod . . . . . . 1.2 Cíl . . . . . . . 1.3 Metodika práce 1.4 Struktura práce

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

2 Přehled současné situace 2.1 Úvod do problematiky . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Analýza struktury dokumentu – fyzická analýza . . . . . . 2.1.2 Analýza obsahu dokumentu – logická analýza . . . . . . . 2.2 Přehled metod pro analýzu dokumentů . . . . . . . . . . . . . . . 2.2.1 Analýza dokumentů založená na vizuálních informacích . . 2.2.2 Analýza dokumentů založená na strukturních informacích . 2.3 Formáty pro strukturní analýzu . . . . . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . .

6 6 7 8 8

. . . . . . .

9 9 9 12 13 13 16 19

3 Využití metod analýzy dokumentu

23

4 Analýza a porovnání metod 29 4.1 Hodnocení metod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Návrh řešení 5.1 Návrh pro postup získání struktury dokumentu . . . . . . . . . . . . 5.2 Návrh na webovou aplikaci . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Návrh struktury XML . . . . . . . . . . . . . . . . . . . . . . . . . .

37 38 39 40

6 Hodnocení navrženého řešení

43

7 Diskuze

45

8 Závěr

47

9 Literatura

49

Přílohy

54

A Tok konverze

55

5

1 1.1

Úvod a cíl práce Úvod

Rychlý rozvoj v oblasti komunikačních a informačních technologií vede k neustálé potřebě vytvářet, měnit a získávat nové informace. S množstvím informací se zvyšuje také množství dokumentů jak v papírové tak především v elektronické podobě. Z tohoto důvodu je nutné neustále vyvíjet a zkoumat nové metody, jak s těmito dokumenty zacházet. Mezi tyto nové způsoby zacházení s dokumenty patří také převádění papírových dokumentů do elektronické formy. To je výhodné například proto, že tím odpadá nutnost skladovat velké objemy papírů, které zabírají mnoho prostoru nebo je naopak umožněno používáním elektronických kopií dokumentů chránit původní papírové dokumenty před poškozením. Dalším způsobem je převádění dokumentů v elektronických formátech do jiných formátů, které jsou pro další zpracovávání vhodnější. Převody dokumentů způsobují potřebu vývoje metod pro analýzu stránky dokumentu, které umožní zjistit strukturu i obsah dokumentů uložených v různých formátech, ale i rozeznat základní prvky dokumentů převedených z papírové podoby například skenováním. Tato problematika je velmi rozsáhlá a složitá a neustále jsou vyvíjeny nové metody i celé systémy s cílem pracovat efektivněji a s co nejnižší chybovostí. Tyto metody či systémy využívají řadu různých pracovních postupů a principů a není možné vytvořit jejich vyčerpávající přehled, proto je orientace mezi nimi velmi obtížná. Negativním následkem rozvoje informačních technologií, který umožňuje velmi snadné vytváření a šíření dokumentů pro všechny uživatele, je pokles úrovně grafické úpravy a časté ignorování typografických pravidel ze strany uživatelů, ale bohužel často i samotných textových procesorů či dalších aplikací. Pro čtenáře se tak stává řada takto vytvořených dokumentů méně přehledných a to může vést k řadě dalších problémů. Například pro obchodní firmu, která nemá svoje nabídky zpracované na přijatelné úrovni, mohou být důsledkem ztráty zákazníků a tím i zisku. Podobných příkladů negativního dopadu špatně zpracovaných dokumentů lze najít ještě mnoho. Proto dalším následkem zvyšujícího se množství dokumentů je i potřeba tyto dokumenty hodnotit právě z hlediska jejich kvality, posouzením podle typografických pravidel, pravopisu i grafické úpravy. Touto oblastí výzkumu se zabývá práce Automatizované hodnocení kvality dokumentů (Talandová, 2009). Na tuto studii navazuje tato práce o analýze struktury dokumentu a společně s dalšími prácemi, které teprve vzniknou, vytvoří v budoucnu rozsáhlejší projekt zaměřený na hodnocení kvality dokumentů. „Za cíl si klade především převést hodnocení v neexaktní oblasti, která se týká typografie, grafiky a designu, do exaktní oblasti matematiky s následným hodnocením s využitím automatizovaných prostředků.ÿ (Talandová, 2009)

6

Celý tento projekt by měl napomoci vytvářet nové dokumenty v souladu se standardizovanými pravidly pro typografickou úpravu dokumentů. Dokumenty se tím stanou pro čtenáře přehlednější a estetičtější, bude se v nich snadněji orientovat a zpracovávat jejich obsah, což bude mít rozsáhlý přínos v mnoha oblastech.

1.2

Cíl

Cílem této práce je navrhnout řešení, které v budoucnu umožní vytvoření základní aplikace pro hodnocení kvality dokumentů, především z typografického hlediska. Účelem této aplikace bude snaha o zvýšení typografické úrovně publikovaných dokumentů. Každému uživateli bude v aplikaci umožněno provést jednoduchou kontrolu typografické kvality dokumentu prostřednictvím analýzy struktury stránky. Aby bylo možné tohoto cíle dosáhnout, je nejprve nutné splnit dílčí cíle, které tomuto hlavnímu cíli předcházejí. Prvním z těchto dílčích cílů je seznámení se s pojmem analýza dokumentu a s dalšími souvisejícími pojmy, metodami a postupy, které se pro analýzu stránek dokumentů používají. Následně dojde také k seznámení se s formáty dokumentů, které jsou vhodné pro analýzu stránek dokumentů z pohledu struktury, tj. s formáty, které jsou schopny nějakým způsobem uchovávat informace o struktuře stránky. Dále bude provedeno zmapování současné situace v analýze dokumentů, opět s důrazem na strukturu. Zmapování bude spočívat především v uvedení relevantních zdrojů pro tuto problematiku. Metody uvedené v těchto zdrojích zde budou stručně popsány a bude vytvořen jejich základní přehled. V další části budou vybrány metody zaměřující se na analýzu struktury, pokud takové existují, přičemž tyto metody budou analyzovány a navzájem porovnány, případně budou uvedeny aplikace těchto metod. S ohledem na základní cíl práce budou stanovena kritéria pro hodnocení těchto metod. Tato kritéria budou posuzovat vybrané metody z hlediska jejich možností, použitelnosti a dalších charakteristik. Kritéria budou ohodnocena váhami, aby bylo možné určit jejich důležitost. Na základě provedeného hodnocení bude vybrána metoda použitelná pro návrh řešení webové aplikace. V další kapitole bude popsán návrh řešení, které umožní využít zvolenou metodu v rámci webové aplikace. Pokud nebude možné použít některou z hodnocených metod, bude zde uveden návrh vlastního řešení včetně požadavků na aplikaci. Právě tento návrh by v budoucnu měl sloužit jako základ pro hodnocení kvality dokumentů a tím navázat na práci Automatizované hodnocení kvality dokumentů (Talandová, 2009). Celá práce bude přínosem v teoretické rovině, protože se zaměřuje na problematiku analýzy stránky z pohledu struktury, která zatím nepatří k často řešeným oblastem, a vede k návrhu aplikace, která bude uživateli přístupná a užitečná jako nástroj pro hodnocení kvality dokumentů.

7

1.3

Metodika práce

Pro dosažení cíle a vypracování celé práce budou nejprve prozkoumány relevantní zdroje, které se touto problematikou zabývají. Na základě informací zjištěných z vybraných zdrojů budou popsány základní pojmy, které se v souvislosti s analýzou dokumentů objevují, a bude vypracován přehled základních metod zabývajících se analýzou struktury i vizuální analýzou. Metody pro analýzu struktury budou prozkoumány podrobněji a výběr z nich bude ohodnocen podle určitých kritérií a analyzován. Dojde k provedení tzv. vícekriteriální analýzy, kdy se jednotlivým kritériím přiřadí váhy odpovídající důležitosti kritéria. Váhy se stanoví bodovací metodou. Přiřazením vah jednotlivým kritériím bude dosaženo přesnějšího hodnocení. Zde je ale třeba zdůraznit, že hodnocení metod je subjektivní záležitostí. Podle ohodnocení bude vybrána metoda nejlépe splňující daná kritéria, která se stane základem pro návrh řešení. Pokud budou všechny hodnocené metody nevyhovující, přistoupí se k navržení nového řešení. Návrh řešení může v budoucnu vést k vytvoření aplikace pro základní hodnocení kvality dokumentů z typografického hlediska prostřednictvím provedení analýzy struktury vstupního dokumentu. Nakonec se výsledky celého průzkumu možných metod vyhodnotí jak po stránce teoretické, tak i po stránce praktické. Zhodnoceno bude také navržené řešení z hlediska jeho přínosnosti.

1.4

Struktura práce

Zde je uveden stručný popis stěžejních kapitol práce. Kapitola 2: Přehled současné situace. Kapitola se věnuje uvedení čtenáře do problematiky analýzy dokumentu a vysvětlení důležitých pojmů. Je zde uveden základní přehled důležitých metod pro analýzu a popis formátů, které se pro analýzu struktury hodí. Kapitola 3: Využití metod analýzy dokumentu. Podrobně popisuje vybrané metody pro analýzu struktury. Kapitola 4: Analýza a porovnání metod. Podle stanovených kritérií a přidělených vah hodnotí vybrané metody. Kapitola 5: Návrh řešení. Kapitola navrhuje řešení podle zvolené metody. Kapitola 6: Hodnocení navrženého řešení. Kapitola hodnotí klady a zápory řešení navrženého v předchozí kapitole.

8

2

Přehled současné situace

Cílem této kapitoly je seznámit čtenáře se základními pojmy, které se v souvislosti s analýzou dokumentu objevují. Dále jsou zde uvedeny metody, které se v této oblasti využívají. Tyto metody jsou rozděleny podle toho, zda pracují pouze s vizuálními informacemi či zda se orientují na strukturu. Konečně následuje popis formátů, které jsou pro analyzování struktury dokumentů nejvhodnější.

2.1

Úvod do problematiky

Dokumentem se rozumí tištěný či elektronický materiál, který obsahuje především text a jeho obsah je uspořádán do stránek. Existuje mnoho definic pojmu dokument. Dokument je „jakákoliv entita obsahující informace, včetně strojově čitelných záznamů, mikrodokumentů a tištěných i netištěných médiíÿ či „jakýkoliv předmět, který byl zhotoven tiskem nebo jiným způsobem a lze jej katalogizovat nebo indexovatÿ (TDKIV, 2001-2002). Analýza je vědecká metoda a znamená rozbor či členění. Celek je dekomponován na elementární části za účelem identifikace podstatných vlastností základních částí celku tak, aby bylo možné poznat jejich zákonitosti a podstatu. Analýza dokumentu probíhá ve dvou úrovních: analýza struktury a analýza obsahu. Analýzou struktury se rozumí fyzická analýza, analýzou obsahu logická analýza. Tato práce se zabývá především analýzou struktury, tou se rozumí hledání prvků na stránce a jejich odlišení od pozadí stránky a od sebe navzájem. 2.1.1

Analýza struktury dokumentu – fyzická analýza

Účelem fyzické analýzy je rozdělení stránek dokumentu na jednotlivé prvky (elementy) a základní určení jejich typu. Ve výsledku fyzické analýzy jsou tedy známy informace o umístění prvků na stránce, jejich rozměrech, tvaru a vzájemných vztazích. Pro získání těchto informací se používá segmentace, nebo také analýza rozložení. Metody fyzické analýzy rozeznávají fyzické objekty na stránce. Vstupní data jsou považována za obraz. Pro analýzu je tedy možné použít obecný postup analýzy obrazů, který se skládá z pěti kroků. • • • • •

snímaní a digitalizace předzpracování segmentace popis nalezených oblastí či objektů klasifikace a rozpoznávání objektů

9

Segmentace hledá oblasti či objekty v obraze. Rozděluje obraz na oblasti, které se nepřekrývají nebo se překrývají pouze částečně. Pokud nalezené oblasti jednoznačně korespondují s objekty vstupního obrazu, jedná se o kompletní segmentaci. Další variantou je částečná segmentace, kdy dojde k rozdělení obrazu do samostatných oblastí, které jsou vzhledem k určitým vlastnostem homogenní. Těmito vlastnostmi mohou být, jas, textura, barva, odrazivost. Prvním přínosem segmentace je redukce objemu zpracovávaných dat. Pro segmentaci se používají metody prahování, narůstání oblastí, barvení, srovnání se vzorem nebo detekce hran. • Prahování: jde o nejstarší a zároveň pro svou jednoduchost a hardwarovou nenáročnost i nejpoužívanější metodu. Princip metody spočívá v tom, že se stránka dělí na jednotlivé bloky podle srovnání s určitou prahovou hodnotou, kterou může být například jas. Správná volba prahu je zásadní pro zisk úspěšného výsledku. Hodnotu prahu je možné určit manuálně na základě pokusů nebo pomocí metod pro automatické určování prahu. Většinou nelze použít stejnou prahovou hodnotu (globální prahování) pro celou plochu obrazu. Potom se určuje lokální práh, který je funkcí polohy. Je tedy určen jen pro část obrazu. Proto je obraz rozdělen na podobrazy a lokální práh se určuje pro každý podobraz zvlášť, nezávisle na ostatních výsledcích. Pokud pro podobraz postup určení lokálního prahu selže, určí se práh interpolací sousedních prahů. Je možné zvolit i prahování s více prahy, výsledkem je pak obraz s velmi omezeným počtem jasových úrovní. Prahová hodnota se určuje většinou analýzou tvaru histogramu. Pokud jsou v obraze objekty s podobným jasem jasově odlišné od pozadí, je histogram dvouvrcholový, kdy jeden vrchol značí četnost obrazových elementů pozadí, druhý četnost obrazových elementů objektů. Práh se potom určí jako hodnota jasu, jejíž četnost odpovídá minimu ležícímu mezi dvěma maximy. Histogram může být i vícevrcholový. Pak lze určit více hodnot prahu, přičemž pro každý z určených prahů je výsledek segmentace jiný. Je možné použít i jednodušší metodu procentního prahování, a to v případě, že je předem známa vlastnost, kterou má obraz po segmentaci mít. Práh se zde určuje tak, aby byla tato vlastnost splněna – pomocí histogramu. Mnoho oblastí obrazu má konstantní odrazivost či pohltivost povrchu, proto je možné použít jasovou konstantu prahu a oddělit tak objekty od pozadí. Prahování se používá především pro jednodušší případy, v ideálním případě je výsledkem kompletní segmentace do oblastí. • Detekce hran: hrany jsou místa, kde dochází ke změnám barvy či jasu, ty se spojují do řetězců nebo také hranic. Hrany můžeme najít na hranici mezi objekty nebo na rozhraní světla a stínu (skokové hrany) či v místech trojrozměrných hran objektů (trojúhelníkové hrany). Většina metod pro detekci hran se zakládá na metodách výpočtu gradientu a tvoří silné hraniční linie. Gradient udává změnu hodnoty obrazové funkce. Pro zjištění významných hran bez ohledu na směrové vlastnosti hran se často používá všesměrový lineární Lapla-

10

ceův operátor. Gradientní operátory se dál používají pro ostření obrazu, tzn. pro získání strmějších hran. Mechanismy pro detekci hran můžeme rozdělit podle technik, které používají, a to na detektory hran založené na první derivaci, založené na druhé derivaci, detektory nepracující s derivacemi a detektory pracující ve Frekvenční oblasti. Detektory založené na první derivaci: Robertsův, Sobelův, Cannyův Detektory pracující s druhou derivací: D. Marr a E. Hildreth Metodu detekce hran lze spojit s prahováním, tím dojde k odstranění nevýrazných hran, které mohou být šumem. Tato metoda se příliš nehodí pro texty, protože zde hrany nejsou dostatečně zřetelné. • Narůstání oblastí: tato metoda se používá, pokud je v obraze šum a je tedy obtížné hledat hranice. Dokument je při ní rozdělován do souvislých, z určitého hlediska homogenních oblastí. Kritérium homogenity je založeno na jasových vlastnostech, komplexnějších formách popisu, na vytvářeném modelu segmentovaného obrazu. Spojování oblastí vychází z počátečního rozložení, při kterém každý obrazový element reprezentuje samostatnou oblast. Pokud dvě sousední oblasti splňují kritérium homogenity, dojde k jejich spojení do oblasti jedné. Kritérium homogenity je zastoupeno popisem, ten je většinou založen na jasových vlastnostech. Popisy oblastí se srovnávají statickými testy, pokud dojde ke shodě, oblasti se spojí a vznikne tak nová oblast. Pokud už není možné žádné oblasti spojit, je proces ukončen. Výsledek spojování oblastí je závislý na pořadí, v jakém jsou oblasti ke spojování vybírány. Štěpení a spojování využívá pyramidální reprezentaci obrazu a zachovává dobré vlastnosti obou přístupů. • Hledání vzorů: tato metoda je vhodná pro hledání známých objektů v obraze, srovnávání dvou snímků či určování relativního pohybu objektů. Pokud obraz neobsahuje šum, je úloha velmi snadná. Situace se komplikuje, pokud je vzor v obraze zvětšený či natočený apod. Ostatní metody: segmentace podle textury (typu povrchu), segmentace podle typografických změn v dokumentu (Fuss a kol.), přístup Slocomba a Ambekara (1998), kteří se nezaměřují na text, ale na typografické charakteristiky, postup začíná detekcí bílých míst a z nich plyne rozložení textu, je zde uplatněn postup shora dolů, neprovádí se analýza až na úroveň pixelů, ale pracuje se s celými znaky.

11

Dalším pojmem úzce souvisejícím s analýzou struktury dokumentu je analýza rozložení dokumentu. Tento pojem ve své definici splývá s pojmem segmentace, takže je možné je považovat za synonyma. Stejně jako u segmentace je úkolem analýzy rozložení najít homogenní bloky nebo jejich oddělovače a rozdělit tak dokument do oblastí (objektů), které se pokud možno nepřekrývají. Metody, které se pro to používají nejčastěji, jsou analýza zdola nahoru a analýza shora dolů. Lze také tyto přístupy kombinovat (hybridní metody). Metoda zdola nahoru se používá nejčastěji. Začíná u pixelů, které postupně sdružuje, podle jejich charakteru. Postupně tak vznikají homogenní oblasti, čili prvky stránky. Tato metoda je vhodná především pro hledání souvislých ploch, pokud lze oblasti porovnat například podle odlišného jasu nebo barvy. Pro text tato metoda není příliš vhodná. Metoda shora dolů znamená, že se problém postupně dělí na menší a menší podproblémy, které lze jednoduše řešit. Každá úroveň je číslována a představuje jinou úroveň abstrakce. Při analýze struktury dokumentu se tedy postupuje tak, že se obraz postupně dělí na homogenní oblasti. Ty se potom analyzují nebo dál dělí podle nastavení citlivosti. Pro zpřesnění analýzy je vhodné oba přístupy kombinovat, pokud je segmentace příliš detailní, je možné oblasti opět spojit a naopak. 2.1.2

Analýza obsahu dokumentu – logická analýza

Tato problematika není stěžejní částí práce, proto je zde uvedena pouze ve stručnosti, pro utvoření základního přehledu. Existuje předem definovaná množina typů (tříd) a každý prvek může být přiřazen právě jednomu typu. Logická analýza představuje proces, kdy každému prvku je přiřazena třída. Tento proces se nazývá klasifikací a je nutné, aby byl co nejpřesnější. Jeho výstupem má být informace o tom, jaké typy objektů se v analyzovaném obrazu nacházejí, tedy co obraz obsahuje. Pokud tedy aplikujeme tento proces na dokument, jeho účelem je určit typy prvků, které se nacházejí na stránce. Pro logickou analýzu existuje řada metod. Jendou z nich je metoda Hu a Ingolda (1993), kteří popisují strukturu dokumentu pomocí grafu. Kombinují metody prohledávání shora dolů a zdola nahoru s fuzzy logikou. V Ishinatiho (1999) metodě dochází ke vzájemné spolupráci analýzy rozložení a logické analýzy s tím, že si systémy navzájem předávají své výsledky, a to i opakovaně, což vede k zpřesňování. Gori a kol. (2003) popisují několik různých postupů pro získávání informací o struktuře dokumentu, které vedou k popisu logické struktury. Tyto postupy zahrnují segmentaci stránky s klasifikací oblastí, klasifikaci na úrovni pixelů se segmentací stránky či segmentaci stránky a následnou klasifikaci pixelů a oblastí. Metody Radka Burgeta (2006, 2007) a Aumann a kol. (2006) se shodně zabývají extrakcí prvků z dokumentu podle vizuálních informací. Aumann a kol. používají strojové učení a ručně označkované dokumenty zde slouží jako vzory, Burget navr12

huje sestavení modelu dokumentu, ze kterého se vybírají jen důležité rysy s cílem použití pro další analýzu. Logickou strukturu znázorňuje strom vizuálních oblastí. Problém porozumění dokumentu se tedy skládá ze tří téměř autonomních úrovní: fyzické, logické a prezentační. Na fyzické úrovni jsou výstupem analýzy propojené segmenty, logická úroveň je spojena s interpretací získaného rozložení dokumentu. Na logické úrovni jsou generovány meta-informace, například prvek „textÿ z fyzické úrovně zde může být označen jako „titulÿ, „autorÿ apod. Na prezentační úrovni jsou dokumenty připraveny pro prohlížení. Konečné místo určení může být monitor, tiskárna či textový editor či procesor – musí být schopno vyrenderovat novou verzi dokumentu podobnou vzhledem i obsahem původnímu dokumentu. To zajišťují formáty zaměřené na prezentaci, jako je PDF, a ovladače tiskárny. Proces porozumění dokumentu tedy probíhá tak, že jsou zjištěny segmenty na stránce, jsou k nim přiřazeny meta-informace a nakonec je umožněno prohlížení nebo tisk.

2.2

Přehled metod pro analýzu dokumentů

Účelem této kapitoly je uvést stručný přehled základních metod, které se používají pro analýzu dokumentů. Tyto metody jsou rozděleny podle toho, jestli při analýze vycházejí pouze z vizuálních informací, nebo jestli se zaměřují na strukturu dokumentu. 2.2.1

Analýza dokumentů založená na vizuálních informacích

Metod pro analýzu dokumentů z hlediska vizuální informace existuje celá řada. Vzhledem k jejich velkému množství není možné vytvořit zde vyčerpávající přehled těchto metod, proto jsou zde uvedeny pouze nejznámější. Lovegrove, Brailsford (1995) popisují ve své práci metody, výsledky a význam analýzy PDF dokumentů. Při analýze a třídění dokumentů ve formátu PDF nejdřív dochází k rozkladu stránky na geometrické prvky, které tvoří určité bloky (segmenty). Tyto bloky jsou vymezeny pomocí určitých značek, v závislosti na jejich typu. PDF stránka je tedy rozdělena na oblasti obsahující text s podobnými atributy. Informace o těchto atributech je uložena v každém uzlu stromové struktury PDF stránky. Strojové učení zde pomáhá zjistit logické vztahy mezi jednotlivými bloky, určenými při původním rozkladu stránky na geometrické prvky. Celá segmentace stránky je rozdělena na čtyři fáze, nejprve jsou slova seskupena do řádků, poté se segmentují textové oblasti, následně jsou podle řádkování vytvořeny bloky pro odstavce a v poslední fázi jsou zjištěny geometrické vztahy mezi bloky určující jejich nadřazenost a podřazenost. Problémem tohoto algoritmu je práce s otočenými stránkami, nebo stránkami, kde je text rozdělen na více sloupců. Pro tyto případy je nutné algoritmus upravit například zavedením rotační matice. Strojové učení je využito i v metodě popsané Rosenfeldem a kol. (2002). Popisují obecný postup pro získávání struktury dokumentů na základě jejich vizuálních

13

vlastností a pozice v rozložení dokumentu, který je použitelný pro všechny formáty dokumentů s vizuálními a typografickými informacemi. Zároveň uvádí konkrétní implementaci pro formát PDF nazvaný PES. Každý okomentovaný dokument slouží jako šablona, se kterou jsou porovnávány další dokumenty, hlavně podle formuláře souřadnic, protože pole stejných typů bývají často umístěny v dokumentech na přibližně stejných místech. Hlavní snahou je fyzickou či vizuální reprezentaci dokumentu přeměnit do komplexní struktury nezávislé na typu dokumentu skládajících se z vnořených objektů a vztahů mezi nimi. Tento krok se nazývá seskupení a právě tyto struktury následně slouží jako šablony. Proces porovnávání s dalšími objekty se nazývá mapování. Další metoda, která strojové učení využívá je popsána ve článku Aumann a kol. (2006). Většina vizuálních informací v dokumentech je zpracováním textu jako lineární sekvence slov ignorována. Zde je navržen algoritmus, který má této ztrátě zabránit a umožnit automatické extrahování konkrétních oblastí dokumentu založené na vizuálním formátování bez ohledu na jejich sémantický obsah za pomoci strojového učení. Systému je nejprve poskytnut soubor ručně označených trénovacích dokumentů a na jejich základě se systém učí hledat odpovídající pole v budoucích dokumentech. „Typographic and visual information is an integral part of textual documents. Most information extraction systems ignore most of this visual information, processing the text as a linear sequence of words...We present an algorithm that allows to automatically extract specific fields of the document, based exclusively on the visual formatting of the document, without any reference to the semantic content. ÿ (Aumann a kol., 2006)1 Zajímavý postup analýzy dokumentu popisuje Chao (2003). Uvedená metoda zpracovává dokumenty ve formátu PDF. Soustředí se na oddělení pozadí stránky od popředí stránky dokumentu na základě segmentace a porovnání textových prvků na všech stránkách. Tím je možné rozlišit statické a dynamické prvky stránek dokumentu a tak oddělit pozadí stránek. Výzkum analýzy rozložení dokumentu za posledních několik let popisuje Breuel (2003). Uvádí zde řadu nově vyvinutých geometrických algoritmů a systém analýzy rozložení na nich založený a použitelný pro celou řadu jazyků. Systém se skládá z nezávislých softwarových modulů a ty se mohou přizpůsobit různým jazykům a aplikacím. Dál popisuje nový přístup k analýze rozložení, který se skládá z několika kroků: jsou vyhledány maximální obdelníky bílých míst, dál jsou vyhledány řádky textu, které respektují sloupcovou konstrukci dokumentu, na základě vztahu a ob1

Typografické a vizuální informace jsou nedílnou součástí textových dokumentů. Většina systémů pro extrakci většinu těchto vizuálních informací ignoruje zpracováním textu jako lineární sekvence slov. . .Uvádíme algoritmus, který umožňuje automaticky získat specifická pole dokumentu, založený výhradně na vizuálním formátování dokumentu bez ohledu na semantický obsah.

14

sahu přilehlých řádků textu se identifikuje vertikální struktura rozložení (nadpisy, názvy atd.), určí se pořadí čtení. Nový přístup k analýze rozložení dokumentu uvádí Shafait a kol. (2008). Současné metody pro analýzu rozložení dokumentu se spoléhají na určité předpoklady o rozložení dokumentu, pokud ale tyto předpoklady nejsou splněny, není možné tyto metody přizpůsobit. Proto je nutná manuální kontrola výsledků, kterou ale není možné provádět pro každou stránku dokumentu. Práce popisuje nový přístup k analýze rozložení, který má tyto problémy vyřešit. Antonacopoulos a Bridson (2007) analyzují výkonnost metod pro analýzu rozložení. Článek poskytuje detailní informace různých úrovní, které mohou pomoci zlepšit řešení konkrétních problémů. Srovnává výsledky segmentace pozadí dokumentu. Esposito a kol. (1995) popisují hybridní přístup k analýze rozložení dokumentu, obraz je nejdřív rozdělen metodou shora dolů a bloky jsou pak seskupeny metodou zdola nahoru za účelem tvorby komplexního rozložení komponent. Lee a kol. (2001) navrhují novou metodu pro analýzu rozložení stránky. Při automatickém převádění papírových dokumentů do elektronické podoby je geometrická analýza nutností, avšak odlišnosti ve velikostech a fontech písma, mezerách apod. způsobují obtíže při navrhování algoritmu, který by byl obecně použitelný. Proto je zde navržen takový algoritmus, který má otevřené parametry a to umožňuje přizpůsobení segmentace konkrétnímu dokumentu. Velký přehled metod používajících techniky geometrické analýzy rozložení uvádí dokument Cattoni a kol. (1998). Popisuje některé metody pro vyhodnocení algoritmů rozkladu stránky a informace o aktuálním stavu oboru. Analýzu on-line dokumentů popisují Jain a Namboodiri (2001). Uvádějí, hierarchický přístup pro získávání homogenních oblastí v on-line dokumentech, nezaměřují se pouze na segmentaci řádků textu, ale na pochopení rozvržení celé stránky. Nejprve jsou jednotlivé črty rozděleny na textové a netextové. Klasifikují se na základě jejich délky a zakřivení. Netextové jsou pak spojeny do homogenních oblastí na základě jejich blízkosti tak, aby byly rozpoznány řídící tabulky a diagramy. Řídící tabulky mají řádky i sloupce oddělené čárami, neřídící tabulky mají text uspořádaný ve sloupcích bez oddělujících čar. V poslední fázi jsou klasifikovány tabulky, diagramy, text a klíčová slova. Na základě prostorových vztahů mezi obrázky a textem v dokumentu mohou být zjištěny popisky a titulky, vyhledávání dokumentů se může provádět na základě nalezených klíčových slov či diagramů. Analýze HTML dokumentů se věnují dvě metody: metoda Radka Burgeta a Michaela Kunce (2008) a metoda Kovacevice a kol. (2003). První z nich se zabývá zpracováním dokumentů ve formátu HTML, navržený postup je však aplikovatelný i pro dokumenty jiných formátů. Prvním krokem metody je kompletní renderování HTML stránky. Nad ní je provedena vizuální segmentace tak, že vznikne hierarchická struktura vizuálních oblastí dokumentu. Metoda segmentace je založena na principu postupného spojování oblastí do větších celků, jde tedy o analýzu zdola nahoru. Jejím výsledkem je hierarchický strom detekovaných vizuálních oblastí. Pro 15

ně jsou podle tabulky vypočteny vizuální atributy. Pro každou oblast jsou určeny významné rysy a na jejich základě se provádí klasifikace. Cílem klasifikace je zjištění, které vizuální oblasti odpovídají význačným prvkům. Kovacevic a kol. (2003) navrhují využití hierarchické reprezentace zahrnující souřadnice každého HTML objektu na stránce. Pomocí vizuální analýzy rozložení a zařazení oblastí stránky do funkčních komponent vytváří třídící stroj pro kategorizaci stránky. Používá tzv. M-stromy, ve kterých jsou umístěny objekty podle toho, jakou část struktury HTML stránky tvoří. Každý uzel stromu nese informaci o své pozici na stránce. 2.2.2

Analýza dokumentů založená na strukturních informacích

Na tento typ analýzy je možné nahlížet ze dvou úhlů pohledu. Prvním je analýza, která přímo vychází ze strukurních informací uložených přímo v dokumentech, například ve formě značek, které mohou určité formáty obsahovat. Druhý úhel pohledu chápe analýzu struktury jako metodu, která vede k získání struktury původního dokumentu a výsledek ukládá do vhodného formátu podporujícího uchování strukturních informací. Druhý způsob chápání analýzy struktury dokumentu je podstatně častější a následující přehled uvádí zdroje popisujících systémy a metody, které ho využívají. Systém WISDOM++ (Altamura a kol., 2000) je schopen převádět dokumenty vzniklé oskenováním papírových do strukturního formátu XML. Následující systémy také ukládají výsledek analýzy dokumentu ve formátu XML, narozdíl od WISDOM++ ale na vstupu vyžadují výhradně dokument ve formátu PDF. „WISDOM++ is a document processing system that operates in five steps: document analysis, document classification, document understanding, text recognition with an OCR, and text transformation into HTML/XML format... The adoption of an XML format is even better, since it can facilitate the retrieval of documents in the Web.ÿ 2 Systém XED (Rigamoti a kol., 2005, Hadjar a kol., 2004) je nástroj reverzního inženýrství pro PDF dokumenty, který umožňuje získání původní struktury dokumentu. Nejdříve je obnovena struktura PDF s cílem zlepšit možnosti vyhledávání, dále jsou odstraněny nadbytečné informace a vyčištěná struktura uložena v kanonickém tvaru. V dřívější verzi tohoto systému bylo možné ukládat strukturu ve formátu XML, zde je navrženo ukládání v kanonickém formátu, kde se ukládají nově získané informace a vyčištěný PDF soubor. 2

WISDOM++ je systém pro zpracování dokumentů, který působí v pěti krocích: analýza dokumentu, klasifikace dokumentu, porozumění dokumentu, rozpoznávání textu s OCR, transformace textu do HTML/XML. . .Přijetí formátu XML je ještě lepší, protože může usnadnit vyhledávání dokumentů na webu.

16

Systém pro konverzi PDF dokumentů do strukturovaného formátu XML popsaný Déjeanem a Meunierem (2006) nejprve extrahuje různé streamy obsažené v PDF dokumentech (text, bitmapové a vektorové obrázky) a pak aplikuje různé komponenty ve správném pořadí pro vyjádření logicky strukturovaného XML. Některé tyto komponenty jsou obvyklé pro analýzu dokumentů, některé jsou specifické pro PDF. Také prezentuje grafické uživatelské rozhraní pro konrolu, korekci a ověření komponent analýzy. Chao a Fan (2004) popisují systém pro extrakci rozložení a obsahu PDF dokumentu. Kromě toho je systém schopen identifikovat logické prvky na stránce dokumentu. Takto získané logické prvky a rozložení je možné dál využít jako šablonu při vytváření nových dokumentů. „Most PDF documents are untagged and do not have basic high-level document logical structural information, which makes the reuse or modification of the documents difficult. We developed techniques that identified logical components on a PDF document page. The outlines, style attributes and the contents of the logical components were extracted and expressed in an XML format. These techniques could facilitate the reuse and modification of the layout and the content of a PDF document page.ÿ (Chao a Fan, 2004)3 Dalšími systémy pracujícími se stejnými formáty dokumentů jsou JPpedal, pdf2xml a LegDoC (Chanod a kol., 2005). JPedal je knihovna pro PDF formát určená k extrakci textu. Pdf2xml je volně šiřitelný modul pro příkazový řádek převádějící dokumenty formátu PDF do formátu XML. Stejnou charakteristiku má i systém LegDoC, rozdílem je pouze to, že je zde možné na vstupu zpracovat dokument i v jiném formátu, než pouze PDF. To umožňuje také zajímavý modul html2xml, který je vyvíjen současně s pdf2xml a dalšími moduly po jiné formáty. Na vstupu je vyžadován dokument ve formátu html a ten je následně převeden do XML, který je schopen uchovat strukturu lépe. Jde o rychlý a výkonný nástroj, který je volně šiřitelný. Následující zdroje odpovídají prvnímu úhlu pohledu na analýzu struktury, tj. vycházejí při analýze ze strukurních informací přímo obsažených v analyzovaných dokumentech. Hardy a Brailsford (2002) uvádějí možnost vytvoření označkovaného PDF dokumentu z původního XML dokumentu. V dřívějších verzích formátu PDF nebylo možné uchovávat strukturní informace, proto se pro jejich uchovávání nejčastěji používal formát XML. Dnešní verze už uchování strukturních informací umožňují ve 3

Většina PDF dokumentů nejsou označkované a neobsahují informace o logické struktuře na vyšší úrovni, což způsobuje obtíže při opakovaném použití či modifikaci dokumentů. Vyvinuli jsme techniky, které identifikují logické komponenty na stránce PDF dokumentu. Náčtr, atributy stylu a obsah logických komponent byl extrahován a vyjádřen ve formátu XML. Tyto techniky mohou usnadnit opětovné použití a modifikace rozložení nebo obsahu stránky PDF dokumentu.

17

formě tzv. označkovaných PDF souborů. Plugin zmíněný v této práci je určen pro Adobe Acrobat a umožňuje zobrazení dvou oken na obrazovce, v prvním okně je původní XML soubor a v druhém okně je nově vytvořený označkovaný PDF soubor, které mají představovat stejný obsah i strukturu. Toto srovnání umožňuje sledovat sobě odpovídající položky struktury a jejich změny, aby bylo možné zjistit, zda proces vytváření vnitřní stromové struktury označkovaného PDF dokumentu byl proveden správně. Zajímavým zdrojem je také článek Giuseppe a kol. (2002). Zabývá se zjišťováním podobností mezi XML dokumenty, které jsou pro účely tohoto porovnávání považovány za stromy prvků. Dvojice značek (tagů) zde vymezuje oblast dokumentu obsahující informace spojené s prvkem. Každý prvek může obsahovat další prvky a nestrukturovaná data. Atributy prvků jsou považovány za další prvky – sub-prvky. Dva dokumenty mají stejnou strukturu, pokud si názvy obsažených prvků a způsob jejich propojení odpovídají. Kostra dokumentu je považována za časovou sérii. Jakmile je navštíven uzel ve stromové struktuře, je vypuštěn signál obsahující informace týkající se značky. Výsledný signál potom představuje původní dokument jako časovou sérii. Pro porovnání dokumentů jsou porovnány jejich signály. Podobné problematice se věnují také Nierman a Jagadish (2002). Jejich práce se zabývá rekonstrukcí DTD u dokumentů, kde chybí. Do souborů ukládá podobné dokumenty a těm potom přiděluje společné DTD. Je tedy nezbytné určit míru podobnosti mezi soubory. To je vyřešeno sestavením stromu vzdáleností, které znázorňují míru podobnosti, a výpočtem vzdálenosti pro každou dvojici dokumentů. Pro zajímavost je možné zmínit systém AIDAS (Anjewierden, 2001), který slouží především k získání logické struktury z PDF dokumentů a vychází z toho, že fyzická struktura obsahuje podněty pro logickou strukturu, která může být získána postupně. Každému prvku logické struktury je automaticky přiřazen index, který vypovídá buď o obsahu prvku, nebo o tom, kde může být použit. PDF představuje soubor instrukcí, po jejich provedení je vygenerován bitmapový obraz vyrenderovaný grafickým zařízením do finální podoby. Struktura rozložení je získána z instrukcí, které jsou převedeny na text, grafiku a obrázkové objekty. Logická struktura je následně získávána kombinací analýzy shora-dolů a zdola nahoru.

18

2.3

Formáty pro strukturní analýzu

Některé souborové formáty obsahují strukturní informace, které se k analýze dokumentu dají použít. Jde především o formáty XML a PDF. V omezené míře je možné použít i jiné formáty obsahující strukturní značky, jako jsou HTML, SGML či RTF. Strukturní značky popisují skladbu dokumentu, například typy prvků, vztahy mezi nimi, vlastnosti a uspořádání. XML – Extensible Markup Language Jazyk XML se vyvinul ze staršího jazyka SGML a je jeho zjednodušenou verzí. XML je jazyk značně flexibilní a lze ho snadno přizpůsobit různým potřebám. Jde o formát hojně využívaný pro výměnu dat mezi aplikacemi či pro publikování dokumentů, konverze do jiných formátů je snadná. XML umožňuje výměnu dat mezi různými platformami i výzkumnými skupinami. XML také podporuje spolupráci s databázemi. Je to formát všeobecně přijímaný v mnoha oblastech včetně softwarových firem a výzkumných pracovníků. XML je značkovací jazyk pro textové dokumenty. XML má logickou i fyzickou strukturu. Logická struktura umožňuje rozdělit dokument na jednotky a podjednotky, tzv. elementy, fyzická struktura umožňuje rozložit dokument na entity, které mohou být skladovány odděleně v různých datových souborech, takže mohou být znovu použity a data nepatřící do XML (obrázky) mohou být zahrnuty referenčně. Každá jednotka informací se nazývá entita a každá entita má přiřazený název pro umožnění identifikace. Jediná entita, která nemá své jméno, je entita dokumentu. Data jsou v XML uložena jako textové řetězce, které jsou umístěny mezi textové značky (tagy), které tato data popisují. XML tagy jsou flexibilní, je tedy umožněna tvorba a interpretace meta-informací. Flexibilita tagů se projevuje i na zvýšení rozmanitosti objektů stránky získaných segmentací stránky na fyzické úrovni procesu porozumění dokumentu, na zvýšení využitelnosti meta-informací na logické úrovni a poskytovaní specifických instrukcí na prezentační úrovni. Značky, které jsou pro konkrétní aplikaci přípustné, lze zjistit z definice typu dokumentu (DTD). Textový řetězec spolu s příslušnou značkou je označován jako element. Elementy mohou mít své atributy – jde o textové řetězce s omezenou strukturou nesoucí doplňkové informace k elementům, jako jsou velikost písma či zarovnání. Další součástí struktury XML jsou sekce CDATA. Sekce CDATA slouží k zápisu těch částí textu, které obsahují speciální znaky, například pokud je potřeba vypsat část nějakého programového kódu. XML dokument může dál obsahovat komentáře a zpracovací instrukce. Zpracovací instrukce (procesní instrukce) slouží k přidání nestandardních dat do XML dokumentu, například stylových souborů či skriptů. Značkování dokumentu popisuje jeho strukturu, je tedy možné zjistit, které elementy jsou navzájem propojené, kromě toho je značkováním možné popsat i sémantiku dokumentu, tj. vyznačit element pro datum, osobu apod. Struktura je znázorněna formou stromu. XML je tedy jazykem strukturálním a sémantickým, není

19

jazykem prezentačním, neurčuje, jak má být dokument zobrazován. DTD stanovuje formální soubor pravidel pro definici logické struktury, definuje elementy, které mohou být v dokumentu použity, kde mohou být použity a jaké jsou jejich vzájemné vztahy. DTD může být zcela nebo částečně uloženo v horní části dokumentu nebo v samostatném datovém souboru (externí DTD), na který je potom z horní části dokumentu odkazováno. Dokumenty ve formátu XML musí splňovat pravidla správné formulace, například je nutné, aby počáteční značka měla i svoji koncovou a elementy se nepřekrývaly, aby existoval právě jeden kořenový element, aby hodnoty atributů byly uzavřeny v uvozovkách a nevyskytovaly se dva atributy se stejným názvem u jednoho elementu apod. Je nutné také zmínit rozdíl mezi XML souborem a XML dokumentem. XML dokument může být uložen v jediném XML souboru, ale může se také skládat z několika provázaných XML souborů. Také je možné, aby jeden XML soubor byl součástí několika XML dokumentů. Toto je možné díky entitám a dalším odkazujícím mechanismům, které XML formát podporuje. Díky všem výše uvedeným vlastnostem XML formátu je při analýzách dokumentů využíván velmi často, právě díky schopnosti uchovávat hierarchickou strukturu dokumentu po jeho analyzování. Hitz a kol. (1999) otevírají nové možnosti využití XML pro analýzu dokumentů. „In document recognition, the problem of data representation turns up over and over again. With every new algorithm, we are faced with the problem of how to represent this data usefully. Some general data formats have been developed for this purpose, but none of them is extensible and general enough to hold for all different situations. This variety of different formats prevents the easy exchange of data between different environments, platforms and even between different researchers. We think that through the use of Extensible Markup Language XML technology we could overcome this problem.ÿ (Hitz a kol., 1999)4 V analýze dokumentu lze tento formát použít dvěma způsoby: k reprezentaci dosažených výsledků analýzy logické struktury dokumentu a k ukládání a reprezentaci všech druhů dalších údajů, které jsou během rozpoznávacího procesu získány. Pro vizualizaci výsledků není nutné vytvářet vlastní prohlížeče, protože jednoduchý vzhled dat v XML prohlížeči je dostačující.

4

Při rozpoznávání dokumentů se problém reprezentace dat objevuje znovu a znovu. S každým novým algoritmem čelíme problému, jak reprezentovat tato data účinně. Pro tento účel byly vyvinuty některé obecné formáty, ale žádný z nich není dostatečně rozšiřitelný a obecný, aby platil ve všech různých situacích. Toto množství různých formátů brání snadné výměně dat mezi různými prostředími, platformami a dokonce i mezi různými výzkumnými pracovníky. Myslíme, že použitím XML technologie můžeme překonat tento problém.

20

PDF – Portable document format PDF se stalo univerzálním nástrojem pro výměnu dokumentů, ale současné nástroje pro tvorbu PDF se často zaměřují pouze na zachování rozložení stránky, ale fyzickou nebo logickou strukturu neukazují. Zachování těchto struktur by ale mohlo vést k výraznému zlepšení při vyhledávání díky přesnější indexaci. Zároveň PDF nabízí mnoho funkcí a bohatou syntaxi. To ale vede k větší složitosti a funkce se tak stávají hůře použitelné. Konvertory generující PDF dokumenty jsou sice schopné vkládat informace o struktuře, ale jejich hlavním cílem zůstává zachování vzhledu dokumentu, proto pokud jsou strukturní informace uchovány, jsou uchovány pouze na nízké úrovni. Tento formát neobsahuje informace o logické struktuře dokumentu. Strukturu PDF dokumentů je možné posuzovat ze čtyř úhlů pohledu. Jako na objekty obsažené v dokumentech, strukturu souboru PDF, strukturu dokumentu PDF a podle obsahu streamů. Objekty v dokumentech PDF mohou být logické hodnoty, reálná i celá čísla, jména, řetězce, pole, slovníky, streamy, nepřímé objekty a prázdné objekty. Struktura dokumentu PDF se skládá z hlavičky, těla, referenční tabulky a paty. Hlavička udává verzi PDF, tělo obsahuje objekty dokumentu, referenční tabulka obsahuje reference na nepřímé objekty souboru a umožňuje tím rychlý přístup. Každý dokument obsahuje jednu tabulku, každému nepřímému objektu je přiřazen jeden řádek tabulky. Pata obsahuje odkazy na referenční tabulku a důležité objekty souboru. Struktura dokumentu PDF je popsána hierarchickou strukturou objektů. Těmito objekty bývají nejčastěji slovníky, základním objektem a zároveň kořenem stromové struktury je katalogový slovník. Součástí struktury dokumentu je strom stránek, který tvoří dva typy slovníků – seznam stránek obsahující všechny stránky dokumentu a slovník stránky. Streamy jsou objekty, ve kterých je uchováván zobrazovaný obsah stránky, včetně způsobu, jakým má být obsah zobrazen. Existuje několik typů streamů a pro každý z nich se používají jiné operátory. Kromě analýzy podle strukturní informace je možné využít i analýzu na základě vizuální informace. Tento přístup je velmi rozšířený, existuje zde řada variant a metod, při kterých je stránka brána jako výchozí bod a postupně se získávají informace o dílčích objektech a struktuře dokumentu. Lze uplatnit postup shora dolů i zdola nahoru, případně jejich kombinaci. Uchovávání struktury v PDF dokumentech je koncepčně podobné, jako u XML nebo SGML. Výhodou je, že PDF soubor může být zobrazen nebo vytištěn na jakékoliv platformě vždy se stejnou věrností. SGML – Standard Generalized Markup Language SGML je univerzální značkovací metajazyk, který umožňuje definovat další znač21

kovací jazyky jako svoji podmnožinu. Jde o jazyk nezávislý na platformě či aplikaci. Dokumenty ve formátu SGML jsou uchovávány jako ASCII text. SGML umožňuje definovat elementy, které se v dokumentu mohou vyskytovat a jejich vzájemné vztahy prostřednictvím DTD. SGML dokument se skládá z textového obsahu slov spolu se značkami pro syntaxi. Tyto značky (tagy) indikují hranice a vztahy mezi prvky (elementy) dokumentu. Je to jazyk komplexní, ale z důvodu přílišné složitosti není rozšířený na takovou míru, jako je například XML nebo HTML, které vznikly jako jeho podmnožina. „Each markup language defined using SGML is called a document type, whose formal definition in SGML syntax is the Document Type Definition or DTD. One of the best known document types is HyperText Markup Language or HTML, the set of elements used for creating documents for the Internet’s World Wide Web.ÿ (Glushko, 1996)5 Většinu SGML dokumentů je možné automaticky převést do formátu XML. Existuje jen málo softwarů, které SGML podporují se všemi jeho vlastnostmi, hlavní činnost SGML je publikační. HTML – Hypertext Markup Language Jde o značkovací jazyk, který se vyvinul ze SGML pro účely internetu, je tedy poznamenán vývojem webových prohlížečů. HTML dokumenty jsou textové soubory obsahující HTML značky (tagy), které určují vzhled stránky. Značky mohou být strukturální, popisné nebo stylistické a uzavírají se do špičatých závorek. Zpracovává je webový prohlížeč. Značky spolu s textem, který je mezi ně uzavřen, tvoří elementy dokumentu a mají svoje atributy a DTD definované pro danou verzi HTML. RTF – Rich Text Format Jde o značkovací formát pro uložení textu. Obsahuje velké množství formátovacích příkazů a je nezávislý na platformě a aplikaci. Umožňuje výměnu mezi různými programy pro zpracování textu při které je schopen zachovat vzhled a formát dokumentu. RTF dokumenty jsou uchovávány jako ASCII text.

5

Každý značkovací jazyk definovaný pomocí SGML se nazývá typ dokumentu, formální definice v syntaxi SGML je Document Type Definition nebo DTD. Jeden z nejznámějších typů dokumentu je HyperText Markup Language nebo HTML, skupina prvků pro vytváření dokumentů pro World Wide Web.

22

3

Využití metod analýzy dokumentu

Tato kapitola se zabývá podrobnějším průzkumem metod vhodných pro analýzu struktury dokumentu. Následující metody se zabývají analýzou PDF souborů za účelem získání jejich struktury a tuto strukturu následně uchovávají ve formátu XML. PDF byl vybrán jako vstupní formát, protože jde o formát velmi rozšířený, ale jeho zpracování z hlediska struktury je zatím záležitostí spíše opomíjenou. XML byl vybrán jako výstupní formát, protože bylo zjištěno, že ze všech formátů, které jsou schopné uchovávat strukturní informace, je tento nejvíc rozšířený a snadno přizpůsobitelný konkrétním požadavkům. Xed Rigamoti a kol. (2005), Hadjar a kol. (2004) popisují nový nástroj Xed, který je schopen získat původní strukturu rozložení dokumentu a uložit ji v podobě kanonického tvaru. Kromě kanonického tvaru umí tento nástroj svoje výsledky uložit i ve formátech SVG nebo XML. Xed je nástroj vyvinutý v Javě a zaměřuje se na vyčištění PDF dokumentů od nadbytečných informací a získání jejich struktury. Vychází z běžných přístupů pro analýzu dokumentů, při analýze využívá převod do formátu TIFF. „Nowadays a huge number of documents are either created or converted in PDF format. PDF became the universal exchange format. The main advantage of this format is its portability, viewing and printing abilities. Although PDF allows to embed structural information, usual PDF converters don’t use them.ÿ 6 V první fázi dochází ke zjištění základních oblastí, jako jsou text a obrázky. PDF soubor je převeden do stromové struktury obsahující normalizované PDF objekty, strom je následně interpretován jako virtuální dokument a je uložen do SVG souboru pro každou stránku dokumentu zvlášť. To umožňuje hodnocení kvality rozkladu původního PDF dokumentu. Druhá fáze je zaměřena na získání fyzické struktury dokumentu, tedy na rozpoznání homogenních objektů jako jsou bloky, řádky a slova. Stromová struktura z předchozí fáze se zde mění na kanonický tvar. Kanonický tvar je založen na tom, že všechna primitiva obsažená v původním textu jsou vyjádřena jednoznačným způsobem, výsledný dokument je jednoznačný, další výzkumy a aplikace založené na výsledcích Xed jsou snadno přenositelné, což umožňuje překonat způsob, jakým jsou informace prezentovány, kódovány a organi6

V dnešní době je velké množství dokumentů vytvářeno nebo převáděno do formátu PDF. PDF se stal univerzálním formátem pro výměnu informací. Hlavní výhodou tohoto formátu je přenositelnost a vlastnosti pro zobrazování a tisk. Ačkoliv PDF umožňuje vložit informace o struktuře, obvykle to PDF konvertory nepoužívají.

23

zovány, kanonický formát může být také použit pro prezentaci výsledků metod pro analýzu dokumentu. Hlavním úkolem tohoto formátu je rozdělit dokument do sad správně definovaných primitiv, textový obsah stránky je nejprve rozdělen do bloků, bloky jsou rozděleny do řádků a nakonec do slov, prázdných míst a čísel. Grafické prvky jsou označeny horizontálními nebo vertikálními liniemi nebo cestami. Obrázky jsou prezentovány s informacemi o oblasti v původním dokumentu a odkazem na původní zdrojový soubor. V poslední fázi je získána logická struktura dokumentu, která popisuje význam textových entit a vztahy mezi nimi. Nejdříve jsou textové entity označeny, například jako nadpisy, titulky, autor, tělo. Takto označené entity jsou potom zahrnuty do modelu dokumentu, který pro každou třídu dokumentu definuje jeho gramatiky, tj. hierarchii logických jednotek. Beta verze tohoto systému pro zkušební či soukromé využití je na internetu k dispozici ke stažení. Systém extrakce rozložení Chao a Fana Chao a Fan (2004) navrhují systém pro získání logické struktury, rozložení a obsahu dokumentu ve formátu PDF. Nejprve rozdělují stránku PDF dokumentu do tří vrstev: text, obraz a vrstva vektorové grafiky. Každá tato vrstva se potom stává samostatným PDF dokumentem. Pro zjištění prvků logické struktury je potom možné analyzovat tyto tři PDF dokumenty přímo nebo je převést do bitmapových obrázků a provést segmentaci obrázku. Po získání přehledu o každé komponentě je možné extrahovat atributy stylu komponenty a její obsah. Pro textové komponenty jde o font, řádkování, velikost, barvu, styl textu a textové řetězce jako obsah. Pro obrázkové komponenty je extrahován tvar obrázku, případně maska a jako obsah datový tok každého obrázku do obrazového souboru. Pro komponenty vektorové grafiky se identifikuje cesta objektu v rámci komponenty a je vytvořen SVG soubor pro každou komponentu vektorové grafiky. Cílem je nalezení logických prvků a jejich rozložení včetně extrahovaného obsahu a tím otevřít možnost vytvořit šablony použitelné pro vytváření nových dokumentů. „Most of the studies gave limited consideration to overlaid and arbitrarily shaped blocks. In this paper, we present our techniques that automatically segmented a PDF document page into different logical structure regions such as text blocks, images blocks, vector graphics blocks and compound blocks.ÿ (Chao a Fan, 2004)7

7

Mnoho studií dává pouze omezený prostor překrývání a různě tvarovaným blokům. V této práci uvádíme techniky, které automaticky segmentují stránky PDF dokumentů do různých oblastí logické struktury, jako jsou textové bloky, obrázkové bloky, bloky vektorové grafiky a složené bloky.

24

Systém konverze Déjeana a Meuniera Déjean a Meunier (2006) uvádějí, že PDF se používá například jako formát pro výměnu informací mezi organizacemi, často je jediným přípustným formátem. Ačkoli umožňuje vytvoření souborů obsahujících informace o struktuře, většina PDF souborů tyto informace neobsahuje. Důvodem může být to, že se PDF soubory často získávají z jiných formátů. XML je formát, který kromě jiných výhod, umožňuje uložení dokumentů včetně metadat a strukturních informací. Jde o systém, který spoléhá výhradně na data extrahovaná z PDF a nepoužívá převod do pomocných formátů. PDF soubor je považován za posloupnost stránek, které se skládají z libovolné kombinace textu, grafiky a obrázků. Text se skládá ze znaků a informace o rozložení, grafika obsahuje vektorové informace a obrázky jsou obdelníkovými objekty. Tento systém pro konverzi nejprve získává původní informace obsažené v PDF, jako jsou text, základní a externí objekty. Aby bylo možné získat logickou strukturu dokumentu, je sestavena tabulka obsahu (TOC), která zároveň prezentuje hieararchické uspořádání. Bylo zjištěno, že extrahované textové toky nemusí odpovídat pořadí čtení a mohou odpovídat různým objektům (znak, slovo, řádek), proto je nutné provedení rekonstrukce slov a čtení. Textové objekty jsou segmentovány na základě vzdálenosti mezi znaky a geometrické polohy. Využívá se zde tvorba textových slovníků, které potom pomáhají určit další slova. Co se týče grafiky složené z vektorových informací je největším problémem seskupení všech vektorů, které tvoří jeden obrázek. Stránka je nejdřív rozdělí na textové zóny a zóny obrázků. Zde může být použita řada metod, je ale výhodou použít informace obsažené přímo v PDF souboru. Výsledné dokumenty jsou organizovány do bloků a ne do stránek. Bloky se skládají z hlavičky, těla a paty. Každá z těchto tří částí obsahuje buď textová data, nebo blok, hlavička a pata jsou volitelné. Toto obecné schéma umožňuje zachycení nejčastější struktury, která může být v dokumentech nalezena. Systém je schopen nalezené vektorové struktury ukládat ve vektorovém formátu SVG a tam, kde je to možné, využívá k analýze původní PDF objekty. Je vyvíjen jako součást aplikací, které tvoří systémy pro řízení podnikového obsahu ECM (Enterprise Content Management). WISDOM++ Altamura a kol. (2000) představují systém WISDOM++. Tento systém pracuje s naskenovanými dokumenty, které převádí do formátu XML. K porozumění dokumentu využívá strojové učení za použití souboru pravidel pro učení. Elementy zde nemají atributy, informace, které atributy běžně nesou, se připojují formou souboru stylů (CSS). DTD vytvořené ve Wisdom++ neobsahuje definici elementu, protože cílem není výslovná reprezentace struktury, ale aby byl zobrazen dokument obdobný pů25

vodnímu, toho může být dosaženo pomocí XSL specifikace. XSL je jazyk používaný pro vyjádření stylů, odkaz na externí šablonu stylů je uveden v prvním řádku XML souboru. WISDOM++ je schopný definovat CSS soubor pro každou třídu dokumentu. Systém využívá získané informace o rozložení dokumentu pro převod do strukturního formátu, kterým může být XML nebo HTML. Převod dokumentů do strukturovaného formátu není jednoduchý, protože je třeba brát v potaz mnoho faktorů, aby bylo možné nový dokument vygenerovat tak, aby byl co nejvíc podobný tomu původnímu. Převod do strukturního formátu probíhá ve dvou fázích: nejprve je vytvořena hierarchická soustava tabulek, které přesně reprezentují nejvyšší úroveň struktury rozložení, potom je zformátován text a propojeny bitmapy. Tvorba tabulek je nevyhnutelná, protože ani HTML, ani XML neumožňují umísťování textu či obrázků na obrazovce podle souřadnic o pozici. Každá položka v tabulce je zformátována podle textového obsahu. Aby bylo možné obnovit původní formátování je každý řádek získaný jako výstup z OCR porovnán s řádkem struktury rozložení. V budoucnu je plánováno rozšířit možnosti hypertextových struktur XML a HTML dokumentů vytvářením indexů a přidáváním odkazů na bibliografické citace. LegDoC Chanod a kol. (2005) uvádí integrovaný rámec LegDoC pro konverzi formátů typu PDF, PS a HTML do formátu XML. Projekt je zaměřen na automatizaci různých úkolů a masovou konverzi dokumentů do XML. Funguje na principu rozkladu velkých problémů na menší už řešitelné podproblémy. Pro podproblém potom vybere vhodnou metodu (analýza logické struktury, strojové učení, dolování dat), která ho vyřeší. Schéma cílového dokumentu je poskytnuto jako DTD nebo W3C XML schéma a po provedení konverze jsou dokumenty strukturovány podle tohoto schématu. Tok konverze je znázorněn na obrázku 3 v příloze A. Systém poskytuje také nástroje pro hodnocení a modelování konverze, ale také nástroje pro různé případy konverze. Systém se skládá z několika částí. První se stará o převod formátů do surového XML pomocí převodníků pro různé formáty. Tyto převodníky jsou schopné plného rozeznání znaků, řádků a atributů pro renderování (font, souřadnice), ale jejich schopnosti rozeznat logickou strukturu nebo sémantiku jsou omezené. Druhou částí je předzpracování. Zde jsou surovému XML dokumentu přiřazeny indexy, které umožňují sledování a ladění kroků konverze. Třetí částí je logická analýza, při které dochází k vytvoření struktury podle tabulky obsahu (TOC), rekonstrukci pořadí čtení, detekci záhlaví a zápatí apod. Další částí je sémantická analýza, která rozpoznává entity a obsah dokumentu. Zde je použito výhod strojového učení. Část vizualizace zahrnuje pomoc pro vizualizaci a validaci průběžných i závěrečných kroků konverze. Konverzní management představuje soubor dohod pro požadavky na transformaci a platnost dílčích kroků. 26

JPedal JPedal je komerční nástroj pro extrakci textu. Jde o knihovnu vyvinutou v Java pro PDF aplikace, která umožňuje extrahovat texty, poznámky, obrázky a formuláře. Výsledkem může být čistý text nebo XML soubor uchovávající informace o rozložení stránky a stylu. Extrahovaná data mohou být také seřazena podle pořadí čtení předložených dokumentů. Tato aplikace je dostupná v demo verzi zdarma nebo v placené plné verzi. pdf2xml Jedná se o volně šiřitelný nástroj příkazového řádku, který umožňuje převedení dokumentu ve formátu PDF do formátu XML. Je schopen seskupit text do řádků, snížit efekt stínu, seskupit řádky textu podle fontu, který používají, včetně textu psaného kurzívou. Nevýhodou tohoto systému je, že umí rozeznat pouze obrázky, ale ne tabulky či vektorovou grafiku. Nejvyšším uzlem výstupního souboru je pdf2xml s atributem pages, který udává počet stran. Nejvyšší uzel může obsahovat další uzel title, pokud má stránka titulek. Dalšími uzly pak jsou page pro stránky s atributy, které udávají šířku a délku. Uzly jednotlivých stránek mohou obsahovat značky pro font písma, které mají atributy pro velikost a barvu, případně pro kurzívu či tučné písmo. Samotný text na stránkách se objevuje mezi značkami text s atributy uchovávajícími informace o umístění textu a jeho šířce a výšce. Se stejnými atributy se objevují značky pro obrázky a odkazy. Systém je součástí knihovny Xpdf. Pro jeho úspěšnou instalaci je nejprve nutné instalovat xpdf a libxml2.

27

Z výše uvedených informací je zřejmé, že formát PDF se pro strukturní analýzu používá z větší části pouze jako vstupní formát. I když od verze 6 už je možné vytvářet PDF dokumenty obsahující informace o struktuře, jde o poměrně málo využívanou možnost. Důvodem je především to, že většina PDF souborů vzniká konverzí z jiných formátů a PDF je chápáno spíš jako formát umožňující šířit dokumenty tak, aby jejich vzhled byl nezávislý na zobrazovacím zařízení a nebylo možné dokumenty snadno modifikovat. Využití původní struktury u PDF dokumentů, které strukturní informace obsahují, je při analýze možné, ale vzhledem k už zmíněnému nízkému počtu takto vytvořených dokumentů lze polemizovat nad tím, jestli by takto navržené řešení bylo efektivní. Dalším možným formátem pro strukturní analýzu je SGML. Tento formát byl ale pro svou složitost z větší části nahrazen XML a HTML, které se z něj vyvinuli. HTML je také formátem, který je schopen strukturní informace uchovat a v některých systémech se pro tento účel také využívá. Nicméně bylo prokázáno, že XML je ještě vhodnější. Stěžejním formátem pro strukturní analýzu se tedy stává XML, protože je snadno modifikovatelné, jednoduché a přenositelné a pro uchování zjištěné struktury dokumentu nejvhodnější, nicméně u většiny výše zmíněných metod není možné zjistit, jak přesně výstupní XML struktura vypadá a z jakých prvků se skládá, protože mnohé z nich existují pouze jako součást probíhajících výzkumů a pro běžného uživatele nejsou dostupné.

28

4

Analýza a porovnání metod

Cílem této kapitoly je hodnocení metod pro analýzu struktury a následně výběr metody s nejlepším hodnocením. Pro porovnání byly vybrány metody, které zpracovávají soubory v PDF formátu jako vstupní soubory a jejich výstupem je struktura ve formátu XML. Soubory v PDF formátu byly za vstup vybrány proto, že se tento formát hojně využívá a získáním jeho struktury je možné jeho využití ještě zvýšit. XML formát jako výstup byl vybrán pro svou snadnou modifikovatelnost a rozšířenost.

4.1

Hodnocení metod

Výše uvedené systémy používají pro získání struktury a její uložení do výsledného formátu různé metody. Tyto metody je třeba ohodnotit, aby bylo možné dospět k závěru, která z metod funguje nejlépe. Hodnocení těchto metod bude probíhat na základě předem stanovených kritérií. Ty lze rozdělit na obecná kritéria, která je možné aplikovat na hodnocení jakýchkoliv metod, a specifická kritéria, která jsou určena na základě konkrétních charakteristik vybraných metod. Obecná kritéria: Automatizovatelnost: metoda musí být schopna pracovat bez zásahu uživatele pouze na základě analýzy uživatelem zadaného vstupního dokumentu. Vytvoření struktury stránky: informace získané na základě působení metody musí vést k vytvoření či zpřesnění struktury stránky. Práce s neúplnými či nepřesnými daty: metoda umí doplnit neúplná či nepřesná data a je schopna nejít řešení problému v dostatečně přesné formě. Využívání vzorů: prvky s obdobnými nebo stejnými charakteristikami musí být na základě podobnosti klasifikovány stejně. Spolehlivost: typ musí být k prvku přiřazen spolehlivě a správně, tzn. chybovost metody musí být nízká. Kromě těchto obecných kritérií je nutné určit také kritéria specifická pro dané metody. Těmi jsou: Tvorba výstupního souboru: musí být zřejmé, jakým způsobem je výsledná struktura vytvářena. Struktura výstupního souboru: je zřejmé, z jakých prvků se výsledná struktura skládá a jaké mají mezi sebou vztahy. Modifikovatelnost výstupního souboru: zda uživatel je schopen ovlivnit výslednou strukturu například zadáním parametrů. Možnosti výstupu: metoda umí v případě potřeby uchovat výslednou strukturu i v jiném formátu, než je XML. Zachování stylu: metoda je schopná zachovat styl vstupního souboru například formou připojení externího stylového souboru nebo pomocí atributů připojených k elementům. 29

Možnosti vstupu: metoda umožňuje zpracovat na vstupu i soubory jiného formátu, než je PDF, například HTML. Využití původní struktury: metoda umí využít strukturní informace obsažené v původním vstupním dokumentu. Uživatelské rozhraní: metoda má přehledné uživatelské rozhraní umožňující snadnou orientaci uživatele. Přístupnost metody: metoda je uživateli snadno přístupná, například formou webové aplikace. Metody jsou ohodnoceny pomocí číselné stupnice, která odpovídá počtu bodů: 0 . . . metoda dané kritérium nesplňuje 1 . . . metoda kritérium téměř splňuje 2 . . . metoda kritérium splňuje bez výhrad Vzhledem k tomu, že všechna zvolená kritéria nemají stejnou důležitost, je každému z nich přiřazena váha. Tyto váhy důležitost vyjadřují a díky nim je možné kritéria hodnotit přesněji. Existuje několik metod pro stanovení vah při vícekriteriální analýze. Pro tento případ se hodí bodovací metoda. Při ní je každému kritériu přiřazen počet bodů podle předem určené bodovací stupnice, čím vyšší počet bodů, tím je kritérium důležitější. Počet bodů u jednotlivých kritérií je vydělen součtem všech přidělených bodů a tím je získána váha kritéria. Vzorec pro výpočet: vi = Pk

pi

i=1

pi

pi . . . celková bodová hodnota přiřazená kritériu i vi . . . váha kritéria i Bodovací stupnice byla stanovena v intervalu od 1 do 5. Bodové hodnocení a vypočtená váha jednotlivých kritérií jsou zobrazeny v tabulce 1.

30

Tab. 1: Hodnocení důležitosti kritérií

kritérium automatizovatelnost vytvoření struktury stránky práce s neúplnými či poškozenými daty využívání vzorů spolehlivost tvorba výstupního souboru struktura výstupního souboru modifikovatelnost výstupního souboru možnosti výstupu zachování stylu možnosti vstupu využití původní struktury uživatelské rozhraní přístupnost metody součet

přidělené body

váha

4 5 2 2 4 3 5 3 1 1 2 1 3 5 41

0,098 0,122 0,049 0,049 0,098 0,073 0,122 0,073 0,024 0,024 0,049 0,024 0,073 0,122 1

31

Porovnávané metody: Na základě vlastností a charakteristik metod uvedených v předchozí kapitole bylo vybráno následujících šest metod použitých v šesti systémech, které budou navzájem porovnány. Těmito systémy jsou: • Xed (Rigamoti a kol., 2005, Hadjar a kol., 2004), popis systému viz strana 23. • Systém pro extrakci rozložení a obsahu z dokumenů ve formátu PDF (Chao a Fan, 2004), popis systému viz strana 24. • Systém pro konverzi PDF dokumentů do strukturovaného formátu (Déjean a Meunier, 2006), popis systému viz strana 25. • JPedal, popis systému viz strana 27. • LegDoC (Chanod a kol., 2005), popis systému viz strana 26. • pdf2xml, popis systému viz strana 27. Pokud není možné z dostupných informací zjistit, zda metoda zadané kritérium splňuje nebo nesplňuje, je automaticky hodnocena nulou. Body budou po ohodnocení všech metod vynásobeny váhou kritéria a sečteny pro každou metodu zvlášť. Metoda s největším počtem bodů bude tedy nejlépe splňovat zadaná kritéria. V následující části této práce bude rozhodnuto, zda splněná a nesplněná kritéria dané metody umožňují její zpracování v rámci návrhu, který bude uveden v další kapitole. Vybrané metody se zabývají analýzou struktury vstupních souborů ve formátu PDF a výsledek analýzy ukládají ve formátu XML. Na základě výše stanovených hodnotících kritérií, jejich vah a hodnotící stupnice byla pro vybrané metody sestavena tabulka 2. Z tabulky je zřejmé, že všechny hodnocené systémy jsou schopny pracovat automaticky, uživatel pouze zadá vstupní soubor a systém potom provede analýzu samostatně. Proto jsou všechny metody hodnoceny pro kritérium automatizovatelnost dvěma body. Stejně tak je tomu i u druhého kritéria, vytvoření struktury stránky. Všechny metody vedou k vytvoření struktury stránky, proto jsou opět hodnoceny dvěma body. Pouze u jediného systému se podařilo zjistit, že podporuje práci s neúplnými či poškozenými daty, a to u systému JPedal. Uvádí, že pokud se na vstupu objeví poškozený dokument, který není zakódován, pokusí se systém ručně identifikovat objekty. Pokud není identifikace možná, dojde k odeslání chybového hlášení. JPedal je proto hodnocen dvěma body. Ostatní metody tuto možnost vůbec neuvádějí, proto je hodnocení nula bodů. Hodnocení dvou bodů u dalšího kritéria – využívání vzorů – dosáhly dva systémy – konverzní systém Déjeana a Meuniera, který při zpracovávání dokumentu vytváří slovníky, podle kterých potom hodnotí další nalezená slova, a LegDoC, který používá strojové učení pro tvorbu předloh. U ostatních systémů se práce se vzory nepodařila zjistit.

32

Posledním obecným kritériem je spolehlivost. Ta byla hodnocena jedním bodem u metod Chaa a Fana, protože u jejich systému na testovacím souboru 200 stran provedl chybu v analýze na osmnácti stránkách (chybovost je tady 9 %). Stejný počet bodů získal systém Déjeana a Meuniera (autoři uvádí chybovost do 10ti %). Dvoubodového hodnocení dosáhl systém Xed, jehož chybovost se pohybovala kolem 1 % a systém LegDoC s chybovostí 2 %. Systém JPedal je hodnocen nulou, chybovost se u něj nepodařilo zjistit. Systém pdf2xml spolehlivost neuvádí, proto je zde hodnocení 0 bodů. Prvním ze specifických kritérií je tvorba výstupního souboru, tedy zda je možné zjistit, jak přesně je výstupní struktura vytvářena. Pouze u systémů JPedal a pdf2xml nebylo možné algoritmus tvorby struktury stránky zjistit, proto jsou hodnoceny nula body. U ostatních metod je toto kritérium splněno dostačujícím způsobem, proto jsou hodnoceny dvěma body. Horší hodnocení získaly metody u dalšího kritéria – struktury výstupního souboru, které udává, zda je možné zjistit, z jakých prvků se výsledná struktura skládá. Toto bylo stručně popsáno u systému Xed a systému Déjeana a Meuniera. Nejlepšího hodnocení dosáhl systém pdf2xml, u kterého byla výstupní struktura popsána vyčerpávajícím způsobem. U ostatních hodnocených metod nebylo možné skladbu výsledné struktury zjistit. Kritérium modifikovatelnost výstupního souboru uvádí, zda uživatel může nějakým způsobem ovlivnit vznik výsledné struktury, například volbou parametrů, a tím získat strukturu přizpůsobenou konkrétním požadavkům. To podporuje systém Déjeana a Meuniera, kde je možné přizpůsobit proces konverze a nastavit jednotlivé kroky, proto je hodnocen dvěma body, stejně jako systém LegDoC, který umožňuje totéž. U systému Chaa a Fana je přímo uvedeno, že není možné výstup ovlivnit, u ostatních metod není toto kritérium uvedeno, proto je hodnocení nula bodů. Možnosti výstupu uvádějí, zda je metoda schopná v případě nutnosti použít pro výstup i jiný formát, než je XML. Zde je nejlépe hodnocen systém Xed, jehož novější verze umí kromě XML použít i kanonický tvar. Ostatní metody toto kritérium nesplňují dokonale a jsou hodnoceny jedním bodem, umí pouze použít vektorový formát SVG pro obrázky a grafiku. JPedal umí převést PDF na obrázkový formát, což ale neodpovídá podmínce o uchování struktury. Systém LegDoC možnosti jiného výstupního formátu než je XML neuvádí a systém pdf2xml jiné formáty nepodporuje. Zachovat styl původního dokumentu i u výsledné struktury jsou schopny tři metody: JPedal, LegDoC a metoda Chao a Fana. JPedal a LegDoC neuvádějí způsob, jakým styl zachovávají, proto jsou ohodnoceny jedním bodem, Chao a Fan používají atributy. Další tři systémy možnost zachování stylu neřeší. Co se týče kritéria možnosti vstupu, které má uvádět, zda je systém schopen zpracovat dokumenty i v jiném formátu, než je PDF, je zde pouze systém LegDoC hodnocen dvěma body. Je totiž schopen zpracovávat různé formáty. Další hodnocené metody toto nepodporují, proto jsou všechny ohodnoceny nulou.

33

Další kritérium – využití původní struktury – uvádí zajímavou možnost použít původní strukturu vstupního souboru, pokud je k dispozici. Touto možností se zabývá pouze jediný systém, a to konverzní systém Déjeana a Meuniera, který extrahuje textové toky z PDF, pokud je to možné. Ostatní metody se zabývají pouze rozkladem dokumentu na základě vizuálních informací. Další kritérium hodnotí existenci uživatelského rozhraní. Bylo zjištěno, že z hodnocených systémů uživatelské rozhraní nemají dva, a to konverzní systém popsaný Chao a Fanem a systém pdf2xml. Proto jsou hodnoceny nulou bodů, ostatní systémy jsou hodnoceny dvěma body. Poslední kritérium uvádí, zda je pro uživatele možné snadno se k použití systému dostat, tj. kritérium přístupnost metody. Systém JPedal existuje buď v demo verzi jako webová aplikace, nebo v placené plné verzi, proto přístup k systému je poměrně jednoduchý a systém obdržel dva body. Stejný počet bodů získal systém pdf2xml, který je volně šiřitelný a bezplatný. Pro systém Xed je možné najít odkazy ke stažení, nicméně jsou už zastaralé, proto získává jeden bod. U ostatních tří systémů se přístup k nim nepodařilo zjistit, nebyly nalezeny odkazy ke stažení ani žádné podobné informace. Jsou hodnoceny nulou bodů. Výsledkem hodnocení jednotlivých metod je zjištění, že konverzní systém popsaný v článku Hervé Déjeana a Jean-luc Meuniera a konverzní systém LegDoC, dosáhly stejného hodnocení, a to 17 bodů z celkového počtu 28. Druhé nejlepší hodnocení získal systém Xed, který dosáhl 14 bodů a pouze o bod méně získal systém JPedal. Po přidělení vah hodnoceným systémům bylo zjištěno, že nejlepšího hodnocení dosáhl systém LegDoC. Konverzní systém popsaný v článku Hervé Déjeana a Jean-luc Meuniera: A System for Converting PDF Documents into Structured XML format má oproti ostatním hodnoceným metodám podstatnou výhodu, a to, že je schopen využít původní struktury souboru ve formátu PDF, protože to je problematika, která je doposud prozkoumána jen velmi málo a přitom tím lze práci výrazně ulehčit. Bohužel zde algoritmus extrakce původní struktury není popsán příliš podrobně. Další výhodou je možnost přizpůsobení výstupní struktury díky možnosti nastavit všechny kroky konverze individuálně, což umožňuje také systém LegDoC. Velkou nevýhodou se naopak stává to, že nezachovává styl původního dokumentu, čímž nezaručuje, že výsledný dokument se bude původnímu podobat, ale soustředí se pouze na to, aby byla získána struktura. LegDoC sice zachování stylu umožňuje, není ale možné zjistit, jakým způsobem. Stejně tak ani jeden z nejlépe bodovaných systémů nedokáže pracovat s poškozenými a neúplnými daty, to ale nedokáže většina zkoumaných systémů. Velkou výhodou LegDoCu oproti systému Déjeana a Meuniera je to, že je schopen na vstupu zpracovat celou řadu formátů a tím se z něj může po uvedení do praxe stát velmi univerzální nástroj. Další výhodou LegDocu je vysoká spolehlivost udávaná na vzorových datech, která je srovnatelná se systémem Xed. Nevýhodou obou systémů například oproti systému Xed je nemožnost uložit strukturu v jiném formátu, než je XML. Zde se jeví kanonický tvar navržený v sys34

tému Xed jako velká výhoda, protože je nezávislý na typu dokumentu. Další nevýhodou je, že oba systémy zatím nejsou uvedeny do praxe a fungují pouze jako součást výzkumných prací, proto není možné si jejich funkčnost vyzkoušet. Systém pdf2xml sice nedosáhl dobrého hodnocení, ale je zde třeba zdůraznit, že jako jediný z hodnocených systémů dosáhl plného počtu bodů u kritérií, která byla stanovena jako nejdůležitější. Jde tedy o systém, který vede k vytvoření struktury stránky, je zcela zřejmé, jak výsledná struktura vypadá a zároveň je volně přístupný.

35

automatizovatelnost vytvoření struktury stránky práce s neúplnými či poškozenými daty využívání vzorů spolehlivost tvorba výstupního souboru struktura výstupního souboru modifikovatelnost výstupního souboru možnosti výstupu zachování stylu možnosti vstupu využití původní struktury uživatelské rozhraní přístupnost metody součet

kritérium váha 0,2 0,24 0 0 0,2 0,15 0,12 0 0,05 0 0 0 0,15 0,12 1,22

body 2 2 0 0 2 2 1 0 2 0 0 0 2 1 14

Xed

0 0 10

0

1 2 0

0

0

2

0 1

0

2

body 2

0 0 0,76

0

0,02 0,05 0

0

0

0,15

0 0,1

0

0,24

váha 0,2

Chao a Fan

2 0 17

2

1 0 0

2

1

2

2 1

0

2

0,15 0 1,27

0,05

0,02 0 0

0,15

0,12

0,15

0,1 0,1

0

0,24

body váha 2 0,2

Déjean a Meunier

2 0 17

0

0 1 2

2

0

2

2 2

0

2

0,15 0 1,29

0

0 0,02 0,1

0,15

0

0,15

0,1 0,2

0

0,24

body váha 2 0,2

LegDoC

2 2 13

0

1 1 0

0

0

0

0 1

2

2

0,15 0,24 1,07

0

0,02 0,02 0

0

0

0

0 0,1

0,1

0,24

body váha 2 0,2

JPedal

0 2 8

0

0 0 0

0

2

0

0 0

0

2

0 0,24 0,93

0

0 0 0

0

0,24

0

0 0

0

0,24

body váha 2 0,2

pdf2xml

Tab. 2: Hodnocení metod

36

5

Návrh řešení

Tato kapitola má vést k návrhu řešení pro vytvoření webové aplikace pro strukturní analýzu. V předchozí kapitole byly ohodnoceny nejvhodnější systémy pro analýzu struktury. Nejlepšího hodnocení dosáhly konverzní systém popsaný v článku Hervé Déjeana a Jean-luc Meuniera: A System for Converting PDF Documents into Structured XML format a systém LegDoC. Velmi zajímavý je také systém Xed, a to díky možnosti uchovat strukturu v kanonickém tvaru. Většina hodnocených systémů bohužel není uvedena do praxe nebo není možné zjistit, jakým způsobem přesně je výstupní struktura ve formátu XML vytvářena či nesplňují jiná důležitá kritéria. Proto není možné z nich při návrhu řešení vycházet a je nutné navrhnout nový systém tak, aby lépe vyhovoval požadavkům na získanou strukturu a byl přístupný prostřednictvím internetu jakémukoliv uživateli. Výsledná struktura výstupu bude vycházet z toho, že celý dokument je vlastně posloupností stránek. Tyto stránky dokumentu lze rozdělit na prvky a prvky je dál možné obecně rozdělit na textové a netextové. Textovými prvky se rozumí například odstavce a nadpisy, poznámky pod čarou, číslování stran atd., netextovými zase grafika a obrázky, například grafy, loga apod. O rozdělení stránky na prvky se stará fyzická analýza, typy prvků má za úkol zjistit logická analýza. Úkolem navrhované aplikace bude v první řadě provedení fyzické analýzy. Typy prvků budou určovány pouze v rámci velikosti písma či jako netextové obrázkové objekty. Tento návrh má v budoucnu vést k vytvoření webové aplikace, která bude schopna získat z importovaného PDF souboru základní informace o objektech, které obsahuje. Pro vstupní formát bylo vybráno PDF, protože se velmi často používá, ale je těžké jej nějakým způsobem modifikovat či z něj získat nějaké informace o struktuře. Existuje sice možnost tvorby označkovaných PDF dokumentů, nicméně použití nástrojů, které toto umožňují je náročné, proto je označkovaných PDF dokumentů jen velmi malá část z celkového množství všech PDF dokumentů. Výstupem aplikace je struktura popsaná jazykem XML tak, aby bylo možné provést rekonstrukci umístění objektů a stránce. XML byl vybrán jako výstupní formát, protože jde o formát univerzální, snadno použitelný a snadno modifikovatelný, který je schopen informace o struktuře velmi dobře uchovávat. Výsledkem analýzy vstupního PDF dokumentu je získání informací o rozložení textových a netextových objektů na stránce. Tyto objekty jsou popsány souřadnicemi a rozměrem. Tyto dva údaje, které jsou nezbytné pro následné vybudování struktury a její uložení do formátu XML, budou získány segmentací původního PDF dokumentu. Takto vytvořená aplikace potom najde využití například při hodnocení kvality dokumentů a jejich korekci, kdy se na každou stránku importovaného PDF dokumentu namapuje schéma rozmístění objektů na stránce a tím bude možné zjistit snadněji některé typografické chyby. Například pokud bude objekt označen jako odstavec velkého písma a bude se jednat o poslední řádek stránky, je jisté, že jde

37

o typografickou chybu. Tím, že navržená aplikace tento odstavec znázorní, bude jednodušší chybu tohoto typu odhalit.

5.1

Návrh pro postup získání struktury dokumentu

Tato podkapitola má za úkol nastínit, jakým způsobem je možné zpracovat vstupní PDF dokument, aby bylo možné získat požadovanou strukturu. Každá strana PDF dokumentu bude segmentována a tím dojde k nalezení hledaných objektů, tj. odstavců různého typu, slov, znaků a netextových objektů. Cílem zde navrhované metody pro segmentaci stránky je především získání informací o souřadnicích a rozměrech jednotlivých objektů. Dále je potřebné, aby byla metoda schopná odlišit textové a netextové objekty a případně u textových objektů velikost písma, tj. odstavce psané malým písmem, odstavce psané středním písmem a odstavce psané velkým písmem. Tento problém by mělo vyřešit vytvoření homogenních bloků, tedy částí textu stránky se stejnými vlastnostmi. Nejprve je nutné segmentovat na stránce slova. Ta budou následně spojena do řádků a řádky se spojí do požadovaných bloků. Tím dojde k získání textových objektů. Pro segmentaci netextových objektů lze použít například analýzu zdola nahoru. Jde tedy pouze o fyzickou analýzu, určování typů jednotlivých objektů už pro účely aplikace není nutné. Vzhledem k tomu, že nejprve je nutné získat znaky a slova, jeví se jako nejvhodnější metoda segmentace metoda zdola nahoru. Ta postupuje od pixelů a postupně je sdružuje až po získání jednotlivých znaků. Tyto znaky je pak možné ohraničit obdelníky (bounding boxes) a tím získat potřebné souřadnice a rozměry. Na základě mezer mezi znaky, které se mohou určit například jako vzdálenost mezi ohraničujícími obdelníky nebo jako množství světlých pixelů mezi tmavými, budou jednotlivé znaky spojeny do slov. Kolem těchto nově vytvořených slov mohou být opět vytvořeny obdelníky pro získání souřadnic a rozměrů. Tímto způsobem lze postupovat až po získání homogenních odstavců. Neustálým vytvářením nových ohraničujících obdelníků budou získávány nové souřadnice a rozměry a zároveň uchovávány rozměry určující velikost znaků. Podle této velikosti bude možné segmentovat odstavce s větším, středním či malým písmem. Pokud na začátku segmentace nebude identifikován znak, ale nějaký jiný objekt, bude automaticky považován za netextový a opět kolem něj bude vytvořen ohraničující obdelník. Pokud se budou ohraničující obdelníky netextových objektů překrývat, dojde k jejich spojení a tím bude možné získat celý netextový objekt. Takto navržený způsob segmentace by měl být schopen uchovat veškeré potřebné informace pro další analýzu, nicméně je možné použít i jiné metody. Cenným pomocníkem by mohl být například vyhledávač slov firmy Adobe8217;s Acrobat až word-finder, který je schopen najít slova v dokumentu a poskytnout souřadnice všech čtyř rohů ohraničujícího obdelníku daného slova. Dále je možné použít segmentační metodu pro obrázkový formát a provést konverzi PDF do odpovídajícího 38

formátu ještě před zpracováním. Jako velmi vhodná varianta se jeví i využití volně šiřitelného nástroje pdf2xml, který je schopen uchovat informace o umístění textu a obrázků spolu s informacemi o stylu textu.

5.2

Návrh na webovou aplikaci

Vstupem aplikace bude dokument ve formátu PDF. Uživatel zvolí možnost importovat soubor, vybere dokument, který chce zpracovat a svoji volbu potvrdí. Tím se příslušný dokument uloží na server, kde se bude dál zpracovávat. Zároveň se dokument zobrazí v okně aplikace. Importovat bude možné jednostránkové i vícestránkové dokumenty. Na straně serveru bude provedena segmentace dokumentu podle výše popsané metody (případně jiné metody zvolené programátorem aplikace). Výsledek segmentace bude uložen do formátu XML a odeslán zpět uživateli. Aplikace potom podle nově získaného XML souboru vykreslí nad původním dokumentem schéma, které bude zobrazovat výsledek segmentace a bude tak ohraničovat nalezené objekty. Uživatel bude mít možnost si XML soubor vytvořený na základě segmentace původního dokumentu uložit. Jako výstup aplikace uživatel tedy obdrží informace o objektech na stránce, jejich souřadnice a rozměry, zda jsou textové či netextové, případně o jaký typ odstavce se jedná. Tyto informace budou obsaženy ve výstupním XML souboru, který si bude uživatel mít možnost uložit, na jehož základě bude vykresleno už zmiňované schéma. Uživatelské rozhraní by se mělo dělit do dvou oken. V prvním okně bude zobrazen původní PDF soubor importovaný uživatelem, ve druhém okně bude zobrazeno schéma odpovídající rozmístění objektů podle informací uvedených ve výsledném XML dokumentu. Toto schéma bude namapované na původním dokumentu, jak je možné vidět na obrázku 2. Ve schématu budou zobrazeny odstavce psané velkým písmem, které mohou indikovat nadpisy, odstavce psané středním písmem pro normální text, odstavce psané malým písmem například pro poznámky a obrázky jako netextové elementy. Schéma bude vykresleno na základě získaného XML dokumentu. XML dokument bude osahovat informace o struktuře původního dokumentu. Tat dvě okna zajistí uživateli snadné porovnání a kontrolu původního i nového dokumentu. Nad těmito dvěma okny by mělo být jednoduché menu pro práci s aplikací obsahující možnosti importu dokumentu, provedení segmentace importovaného dokumentu a uložení výsledné struktury získané segmentací. Uživatelské rozhraní by mělo být přehledné a příjemné. Toho lze docílit správným formátováním. Aplikace by měla být pro uživatele snadno přístupná, aby jí mohl použít kdokoliv. Aplikace by dál měla obsahovat možnost exportu a uložení výsledného dokumentu, tcož uživateli umožní s nově získaným strukturním dokumentem dál pracovat a využívat ho.

39

Protože návrh má sloužit jako základ pro hodnocení kvality dokumentů, je třeba, aby výsledné schéma bylo přehledně a pokud možno barevně označeno. Návrh na vzhled výstupu aplikace viz obrázek 2. Orámování modrou barvou odpovídá odstavci psanému střední velikostí písma, orámování zelenou barvou odpovídá odstavci psanému malým písmem, orámování červenou odpovídá netextovému prvku.

Obr. 1: Návrh na výstup aplikace

Vzhledem k tomu, že výsledkem návrhu má být webová aplikace, je možné využít například programovací jazyk PHP, který vytvoří základ aplikace, doplněný o CSS pro vytvoření příjemného uživatelského rozhraní. Výsledné schéma nad původním PDF dokumentem bude možné vykreslit například pomocí jazyka HTML. Pokud by použití aplikace bylo vázáno registrací uživatele a následně jeho přihlášením prostřednictvím loginu a hesla, bylo by možné propojit aplikaci na straně serveru s databází a uchovávat tak výsledky segmentací všech dokumentů, které uživatel do aplikace zadá. Tak by byl uživatel schopen si výsledná schémata zobrazit kdykoliv a nemusel by je vždy ukládat. V uživatelském rozhraní by se pak objevily nové možnosti pro registraci uživatele, přihlášení uživatele, odhlášení uživatele a možnost otevření nového okna zobrazující odkazy na výsledky segmentací uložených v databázi.

5.3

Návrh struktury XML

Základem pro návrh XML struktury je získání informací o objektech v původním dokumentu, především souřadnic a rozměrů jednotlivých objektů.

40

Základním elementem struktury XML bude element pro stránku strana. Tento element bude obsahovat dva další elementy, element text pro textové prvky, element netext pro netextové prvky. Může je obsahovat v jakékoliv kombinaci. Element text bude obsahovat další element pro odstavce odstavec. Element netext obsahuje další element obrazek. Element odstavec obsahuje buď element velke_pismo, nebo element male_pismo, nebo element stredni_pismo, ty budou odrážet velikost písma daného odstavce a povedou například k detekci nadpisů na stránce (v případě velke_pismo) či poznámek pod čarou (v případě male_pismo) nebo normálního textu v odstavci (v případě stredni_pismo). Jejich elementem bude element slovo obsahující element znak. Souřadnice a rozměry jednotlivých objektů budou v XML uloženy jako atributy k elementům text a netext. Souradnice_X a souradnice_Y odpovídají souřadnicím nalezeného objektu, strana_X a strana_Y prezentují délku stran X a Y nalezeného objektu. Následuje návrh DTD (Document Type Definiton) pro navrženou aplikaci, který určí, jaké elementy se ve výsledném XML dokumentu mohou vyskytovat. Struktura DTD je znázorněna na obrázku



41

Obr. 2: Schéma struktury XML dokumentu

42

6

Hodnocení navrženého řešení

Při zpracovávání této práce byl proveden podrobný průzkum dostupných materiálů a na jeho základě lze usoudit, že problematika strukturní analýzy dokumentů ještě není dostatečně prozkoumána. Existuje sice několik systémů, které umožňují analyzovat vstupní dokument za účelem získání jeho struktury, ale informace o nich jsou velmi roztříštěné a neúplné, což komplikuje možnost jejich širšího využití. Například u většiny systémů není z přístupných informací možné zjistit, jak přesně vytvořená struktura daného systému vypadá. Největším problémem je však skutečnost, že většina z těchto systému není pro uživatele volně přístupná nebo není přístupná vůbec. Z tohoto důvodu bylo navrženo vlastní řešení pro vytvoření přístupné webové aplikace. Toto řešení slouží ke zpracování dokumentů uložených ve formátu PDF do strukturního formátu XML. Jako vstupní formát bylo vybráno PDF, protože jde o formát hojně využívaný. Jeho nevýhodou je ale to, že se používá pouze jako formát pro výměnu informací, který je jen těžce modifikovatelný či nějakým způsobem dál zpracovatelný, protože většinou neobsahuje žádné strukturní informace. Tím je i hodnocení kvality dokumentu značně zkomplikováno. Hlavním přínosem navrženého řešení se stává získání struktury. Aplikace vytvořená podle tohoto řešená umožní uživateli strukturu PDF dokumentu získat. Tím bude možné zhodnotit kvalitu dokumentu. Výsledná struktura bude vykreslena a uživatel tak bude schopen okamžitě zjistit případné špatné umístění prvků na stránce vstupního dokumentu. Další výhodou tohoto řešení je uchovávání nalezené struktury ve vhodném formátu. Tímto formátem je XML, protože je univerzální, snadno modifikovatelné a z formátů, které jsou schopné strukturní informace uchovat, nejpoužívanější. Z tohoto důvodu nebude mít uživatel žádný problém, pokud bude chtít s výslednou strukturou dál pracovat. S předchozím bodem souvisí také další výhoda navrženého řešení, tou je struktura výstupního XML dokumentu. DTD a struktura pro výstup aplikace byla navržena tak, aby se v případě potřeby dala snadno upravit a přizpůsobit momentálním požadavkům. Nevýhodou navrženého řešení je to, že není schopné rozeznávat od sebe různé netextové prvky. Pokud tedy dokument bude obsahovat tabulky, grafy a obrázky, budou všechny označeny jako element obrázek. Ale jak již bylo zmíněno výše, struktura výstupního XML dokumentu byla navržena tak, aby ji bylo možné snadno pozměnit s ohledem na konkrétní požadavky, proto je možné v případě zpřesnění rozeznávání netextových elementů přizpůsobit i strukturu výstupního XML dokumentu. Stejný problém se týká i textových elementů. Řešení je navrženo pro rozlišení odstavců psaných velkým, malým nebo středním písmem, dál je možné odlišit jednotlivá slova a znaky. Může ale dojít k situaci, že uživatel bude potřebovat přesnější určení typu elementů, například nadpisy, titulky apod. To už je ale záležitostí logické analýzy, která není v souladu s cíly této práce. 43

Výsledky a zejména spolehlivost aplikace vytvořené podle uvedeného návrhu budou značně závislé na zvolené metodě segmentace. Vhodnost vybrané metody segmentace stránky bude nejprve třeba experimentálně ověřit a teprve na základě pokusů vybrat tu nejvhodnější.

44

7

Diskuze

Při postupu vedoucímu k plnění cílů této práce bylo nejprve nutné zjistit a prostudovat dostupné zdroje. Těmito zdroji byly především odborné články, protože tištěných knih, které se věnují této oblasti a jsou aktuální, je velmi málo. Odborných článků je naopak k dispozici mnoho a problémem se stává výběr těch nejdůležitějších. K dispozici je sice několik zdrojů, které uvádějí předhled metod a článků, které je popisují, jsou však obvykle sestavovány podle hledisek, která jsou pro účel této práce nevhodná. V odborných článcích jsou často informace neúplné a někdy není možné zjistit důležitá fakta. To se stalo jednou z hlavních překážek při průzkumu současné situace. Na základě studia těchto zdrojů bylo zjištěno, že oblast analýzy dokumentů je velmi rozsáhlá, ale zejména z hlediska rozpoznávání dokumentů podle vizuáních informací. Struktura je při rozpoznávání dokumentů používáná spíše sporadicky a pokud ano, jde především o porovnávání různých dokumentů podle jejich struktury. Tento způsob analýzy ale není v souladu s hlavním cílem této práce, proto jsou zde tyto metody uvedeny pouze pro úplnost. Na základě těchto informací byl vytvořen přehled nejznámějších metod pro vizuální analýzu dokumentů, ale i těch, které se věnují porovnávání struktur dokumentů. To se stalo jedním z podstatných přínosů této práce. Z metod pro vizuální analýzu dokumentů byly vybrány ty, jejichž výsledkem je zisk struktury a její uložení ve vhodném formátu. Ukázalo se, že nejvhodnějším formátem pro ukládání zjištěné struktury je formát XML. Vybrané metody byly ohodnoceny vícekriteriální analýzou. Jak se ukázalo, jednotlivá kritéria nemají stejnou důležitost, proto jim byly přiřazeny váhy prostřednictvím bodovací metody, které tuto důležitost vyjadřují. Tak došlo ke zjištění, že z vybraných metod žádná nesplňovala daná kritéria na takové úrovni, aby mohla být použita pro návrh řešení. Výběr vhodných kritérií pro hodnocení metod a přiřazení důležitosti těmto kritériím se stalo jednou z nejdůležitějších součástí této práce. Stanovení jiných hodnotících kritérií či přiřazení jiných vah by významně ovlivnilo dosažené výsledky. Z tohoto důvodu bylo vyvinuto velké úsilí, aby hodnocení metod bylo co nejobjektivnější. Dalším důležitým faktorem pro úspěšné uchování struktury analyzovaného dokumentu tak, aby bylo možné s ní dál pracovat, je správně navržená DTD určující uchovávané prvky a jejich vzájemné vztahy. Je nutné, aby byla navržena způsobem, při kterém bude možné rozeznat základní typy prvků a v případě potřeby DTD jednoduše upravit. Tento požadavek se v navrženém řešení povedlo splnit. Výsledkem celé práce je návrh pro vytvoření aplikace sloužící k základnímu hodnocení kvality dokumentů. Ten je také největším přínosem celé práce. Jde o návrh na vytvoření webové aplikace, která by, narozdíl od hodnocených metod a systémů, byla uživateli volně přístupná a splňovala potřebná kritéria.

45

Kvalita nebude v navrhované aplikaci posuzována z hlediska grafické úpravy či pravopisu, ale z hlediska typografických pravidel. Výstupní XML dokument je schopen uchovat jednotlivá slova, proto by v budoucnu bylo možné hodnotit i pravopisné hledisko, například tvorbou slovníků a následným porovnáváním nalezených slov se slovníky.

46

8

Závěr

Téma této diplomové práce Analýza struktury dokumentu je zaměřeno na metody věnující se analýze dokumentů z hlediska jejich struktury. Práce se zabývá především zjištěním, jaké metody jsou k dispozici a jakým způsobem a kde fungují. Zjištění a prostudování těchto metod se stalo východiskem pro naplnění hlavního cíle této práce. Tímto cílem bylo navržení řešení, které v budoucnu povede k vytvoření webové aplikace. Vytvořená aplikace se stane základem pro hodnocení kvality dokumentů a tak naváže na práci Automatizované hodnocení kvality dokumentů (Talandová, 2009). Analýza dokumentu je velmi rozsáhlá oblast výzkumu a existuje mnoho odborných publikací, které se jí věnují. Pro vytvoření přehledu metod pro analýzu dokumentů, který byl také jedním z cílů práce, byly vybrány relevantní články, které byly rozděleny podle toho, zda analýza probíhá na základě vizuálních informací nebo jestli se věnuje také struktuře. Na základě získaných informací bylo zjištěno, že analýza struktury dokumentu je chápána buď jako analýza založená na informacích o struktuře přímo uložených ve formátu dokumentu nebo jako metoda, která vede k získání struktury dokumentu a jejímu uložení do vhodného formátu, který uchování strukturních informací podporuje. S tím souvisí další část této práce, a to přehled formátů umožňujících uchovávat strukturní informace. Opět byl uveden jejich popis a na základě zjištěných informací byl vybrán nejvhodnější formát – XML. Metody analýzy založené na informacích o struktuře přímo uložených ve formátu dokumentu jsou v současné době využívány pouze pro porovnávání struktur různých dokumentů. K jinému účelu se původní struktura uložená v dokumentech nevyužívá, proto není možné tento typ metod pro hodnocení kvality dokumentu použít. Bylo tedy nutné při návrhu řešení použít metody, které analýzou strukturu dokumentu získají (například segmentací stránek dokumentu) a uloží ji pro další použití. Existuje několik systémů, které tímto způsobem fungují, nicméně ani ty se nezaměřují na hodnocení kvality vstupních dokumentů a nesplňují důležitá kritéria, aby je bylo možné pro tento účel použít. Jejich podrobný popis i hodnocení prostřednictvím vícekriteriální analýzy je v práci také uveden. Z tohoto důvodu bylo přistoupeno k tvorbě vlastního řešení. Byla navržena metoda segmentace stránek dokumentu, následně také způsob jejího uložení ve formátu XML a konečně návrh na výstup aplikace. Tím je původní stránka dokumentu, na které jsou namapovány prvky získané strukturní analýzou. Díky tomu je uživatel hned schopen odhalit některé typografické chyby. Například prvek označený jako odstavec psaný velkým písmem, který se vyskytuje na konci stránky, je potenciální chybou. Lze tedy konstatovat, že využití strukturních informací, ať už jsou získány analýzou či jsou přímo obsažené v dokumentech, pro hodnocení kvality dokumentů, je nový přístup, kterému zatím nebyla věnována pozornost. Návrh řešení uvedený 47

v této práci tedy může mít v budoucnu velký přínos pro tuto oblast výzkumu. Navrženou aplikaci bude možné v budoucnu rozšířit o automatické hodnocení kvality a tím dojde k vytvoření unikátního projektu.

48

9

Literatura

Adobe Corporation PDF Reference, version 1.7 [online]. 2007. Dostupné z http://www.adobe.com/devnet/acrobat/pdfs/pdf reference.pdf. Anjewierden, A. AIDAS: Incremental Logical Structure Discovery in PDF Documents [online]. 2001. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.1502. Antonacopoulos, A., Bridson, D. Performance Analysis Framework for Layout Analysis Methods [online]. 2007. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.593. Aumann, Y. a kol. Visual Information Extraction [online]. 2006. Dostupné z http://www.springerlink.com/content/5g272110h503707u/fulltext.pdf. Altamura, O. a kol.Transforming Paper Documents into XML Format with WISDOM++ [online]. 2000. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.4193. Breuel, T. High performace document layout analysis [online]. 2003. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.1303. Burget, R. Visual Structure of Web Documents [online]. 2007. Dostupné z http://www.fit.vutbr.cz/research/pubs/TR/2006/sem uifs/s060313slidy2.pdf. Burget, R. Vizuálně orientované modelování dokumentů na WWW [online]. 2006. Dostupné z http://www.datakon.cz/2006/datakon2006 sbornik.pdf. Cattoni, R. a kol.Geometric Layout Analysis Techniques for Document ImageUnderstanding: a Review [online]. 1998. Dostupné z http://citeseer.ist.psu.edu/330609.html. Coenen, F. Top down analysis review [online]. 1999. Dostupné z http://www.csc.liv.ac.uk/~frans/OldLectures/2CS21_Ada/week6/topDown.html. Čerba, O. Přednášky z předmětu Počítačová kartografie [online]. Dostupné z http://gis.zcu.cz/studium/pok/Materialy/Book/index.html. Déjean, H., Meunier, J-L. A System for Converting PDF Documents into Structured XML format [online]. 2006. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.4946.

49

Esposito, F. a kol. A Knowledge-Based Approach to the Layout Analysis [online]. 1995. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.411. Fuss, C. a kol.Inferring Structure Information from Typography [online]. Dostupné z http://www.springerlink.com/content/py61l7j8fufl4t0g/fulltext.pdf. Gori, M. a kol. Artificial Neural Networks for Document Analysisand Recognition [online]. 2003. Dostupné z http://www.dsi.unifi.it/~simone/ANNxDAR/TR-DSI-01-03.pdf. Giuseppe, S. F. a kol. Detecting Structural Similarities between XML Documents [online]. 2002. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.980. Glushko, R. J. How Practical is Practical SGML? [online]. 1996. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.2518. Graupmann, J. a kol. COMPASS: A Concept-based Web Search Engine for HTML, XML, and Deep Web Data [online]. 2004. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.9000. Hadjar, K. a kol. Xed: a new tool for eXtracting hidden structures from Electronic Documents [online]. 2004. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.2061. Hardy, R. B., Brailsford, D. F. Mapping and Displaying Structural Transformations between XML [online]. 2002. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.3020. Harold, E. R., Means, W. S. XML v kostce: pohotová referenční příručka. 1. vyd. Praha: Computer Press, 2002. ISBN 80-7226-712-4. Hitz, O. a kol. Using XML in document recognition [online]. 1999. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.5055. Hu, T., Ingold, R. A Mixed Approach Toward an Efficient Logical Structure Recognition From Document Images [online]. 1993. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.1114.

50

Chanod, J-P. a kol. From Legacy Documents to XML: A Conversion Framework [online]. 2005. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.73.1502. Chladil, I. XML versus SGML [online]. Dostupné z http://web.quick.cz/ichladil/commerce/xml_intro22.cs.html. Chao, H. Background pattern recognition in multi-page PDF document [online]. 2003. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.7989. Chao, H., Fan, J. Layout and Content Extraction for PDF Documents [online]. 2004. Dostupné z http://www.springerlink.com/content/b928plaetk53ax91/. Ishitani, Y. Document Image Analysis with Cooperative Interaction between Layout Analysis and Logical Structure Analysis [online]. 1999. Dostupné z http://www.science.uva.nl/events/dlia99/final papers/yasuto.pdf. Jain, A. K., Namboodiri, A. M.Structure in On-line Documents[online]. 2001. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.7751. Knihovnický institut NK ČR. TDKIV: Česká terminologická databáze z oblasti knihovnictví a informační vědy [online]. 2001-2002. Dostupné z http://sigma.nkp.cz/cze/ktd. Kolektiv autorů. Wikipedie, otevřená encyklopedie [online] Dostupné z http://cs.wikipedia.org/. Kolektiv autorů. Stránky projektu JPedal [online] Dostupné z http://www.jpedal.org/. Kolektiv autorů. Stránky projektu pdf2xml [online] Dostupné z http://www.mobipocket.com/dev/pdf2xml/. Kosek, J. Co přináší XML nového[online]. 2000-2001. Dostupné z http://www.kosek.cz/clanky/swn-xml/ar01s02.html. Kovacevic, M. a kol. Web Page Classification Using Visual Layout Analysis[online]. 2003. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.2708. Kraus, V. Struktura souboru PDF [online]. 1999. 51

Dostupné z http://www-kiv.zcu.cz/~herout/html_sbo/pdf/4.htm. Kunc, M., Burget, R. Klasifikace prvků dokumentu na základě jejich vizuálních vlastností[online]. 2008. Dostupné z http://znalosti2008.fiit.stuba.sk/download/articles/znalosti2008-Kunc.pdf. Lee, S. a kol. Parameter-Free Geometric Document Layout Analysis[online]. 2001. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.1769. Linka, A. a kol. Zpracování obrazu a jeho statistická analýza [online] Dostupné z http://e-learning.tul.cz/cgi-bin/elearning/elearning.fcgi?ID_tema=67& stranka=publ_tema. Lovegrove, W. S., Brailsford, D. F. Document analysis of PDF files: methods, results and implications [online]. 1995. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.8781. Nierman, A., Jagadish, H. V. Evaluating Structural Similarity in XML Documents [online]. 2002. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.988. Rigamonti, M. a kol. Towards a Canonical and Structured Representation of PDF Documents through Reverse Engineering [online]. 2005. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.4020. Rosenfeld, B. a kol. Structural extraction from visual layout of documents [online]. 2002. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.8823. Shafait, F. a kol. Structural Mixtures for Statistical Layout Analysis [online]. Dostupné z http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.8226. Simske, S. J. The Use of XML and XML-Data to Provide Document Understanding at the Physical, Logical and Presentational Levels [online]. Dostupné z http://www.science.uva.nl/events/dlia99/final_papers/simske.pdf. Slocombe, D., Ambekar, J. Document Structure Identification: A New Paradigm [online]. 1998. Dostupné z http://www.infoloom.com/gcaconfs/WEB/paris98/slocombe.HTM.

52

Talandová, P. Automatizované hodnocení kvality dokumentů. Disertační práce. MZLU v Brně, 2009. Thompson, H. S. XED: An XML document instance editor [online]. 2000. Dostupné z http://www.ltg.ed.ac.uk/~ht/xed.html. Železný, M. Strukturální metody rozpoznávání [online]. 2003. Dostupné z http://147.228.47.19/courses/smr/Smr-031021.pdf. Železný, M. Zpracování digitalizovaného obrazu [online]. Dostupné z http://147.228.47.19/courses/zdo/ZDO_aktual_060217.pdf.

53

Přílohy

A

Tok konverze

Obr. 3: Tok konverze

55