Cu ceva timp în urmă (aproximativ, oh, a trecut un an!) Întrebarea dacă cineva este interesantă imagine de ansamblu a metodelor moderne de segmentare a documentului de pagini de imagine, am primit un răspuns pozitiv (de la massimus). Și astăzi am decis în cele din urmă să fac această revizuire.
Pe pagină există text și imagini. Este necesar să spargeți textul în blocuri și să selectați fotografiile.
Deci, trebuie să rupem textul în blocuri și să selectăm imaginile. După cum puteți vedea, nu este vorba de tabele, diagrame și alte delicii aici; în plus, de multe ori presupunem că imaginile cu contrast ridicat în timp ce Binarizare bine - adică, granițele lor, în principiu, pot fi găsite lucrând doar cu o imagine alb-negru.
De asemenea, în studii se utilizează adesea conceptele de aspect "Manhattan" și "non-Manhattan". „Manhattan“ - este una în care liniile de delimitare ale tuturor blocurilor (fiecare bloc sau dreptunghiulare sau reprezintă mai multe dreptunghiuri, în care unele părți ale sus și părți generale) „nemanhettensky“ nu satisface astfel de restricții.
Pentru început, vom analiza algoritmi concepuți pentru a lucra cu documentul "Manhattan".
Acesta este algoritmul cel mai vechi - poate primul lucru care vine în minte atunci când vă confruntați cu sarcina de segmentare. În primul rând descris în 1982 îndepărtat, în articolul K.Y. Wong, R.G. Casey, F.M. Wahl. Sistem de analiză a documentelor.
Într-un cuvânt, funcționează astfel: să lăsăm cuvintele verticale și orizontale, zonele conectate rezultate să fie blocate.
Dacă descrieți ceva mai mult, acesta va arăta astfel:
- Luăm imaginea paginii în reprezentarea RLE
- Îndepărtați cursele RLE alb (= o secvență de pixeli albi) cu o lungime mai mică decât lT_horz. Obțineți Image_1
- Imaginea originală este rotită la 90 de grade, iar pe imaginea rotită, eliminați cursele de culoare albă RLE de mai puțin de lT_vert. Rotiți imaginea înapoi și obțineți Image_2
- Facem imagini ȘI Image_1 și Image_2
- Pe imaginea care rezultă, îndepărtați în continuare cursele albe mai mici decât T_Final
Zonele asociate din imagine sunt blocuri prefabricate. Acestea ar trebui să fie împărțite în text și non textuale. În 1982, nu exista încă un astfel de arsenal de instrumente de învățare mecanică, fără ele era dificil - arborele de decizie a fost pictat manual.
Acesta este modul în care imaginile intermediare și blocurile finale arată aproximativ:
Avantajele algoritmului sunt clare - este simplu, funcționează cu imaginea RLE și numai cu ea și, prin urmare, rapidă. Algoritmul în sine nu se bazează în mod clar pe faptul că documentul de intrare este "Manhattan". Cu toate acestea, dacă vă gândiți la aceasta, algoritmul nu va funcționa pe algoritmul "non-Manhattan" - în exemplul de mai jos textul se va lipi de imagine.
Vestea proastă este că, în documentul „Manhattan“ și lipind textul „neteksta“ este, de asemenea, foarte frecvente, SKB se observă.
XY recursiv tăiat
Câțiva ani mai târziu, în 1984, a fost descrisă o metodă mai avansată de segmentare a paginilor, numită tăiere recursivă XY. Este descris în articolul G. Nagy și S. Seth. "Reprezentarea ierarhică a documentelor scanate optic" și în cei 90 de ani dezvoltați activ.
Despre această metodă este deja explicit spus că este potrivit numai pentru documentul Manhattan. Esența metodei este aceea că împărțim alternativ pagina în blocuri, împărțind blocurile pe verticală sau pe orizontală. Asta este, algoritmul este ceva de genul acesta:
- Pregătiți pagina, curățați-o de resturile mici
- Selectați zonele conectate. Puteți chiar unii dintre ei să se unească și să obțină ceva de genul cuvintelor, dacă dintr-o dată cineva știe cum să construiască astfel de asociații în condiții de siguranță. Dar în cadrul acestui post le vom numi "zone conectate".
- Calculăm parametrii globali ai algoritmului, de exemplu, înălțimea și lățimea mediană a simbolului.
Apoi, rulam algoritmul recursiv, pornind de la întreaga pagină:
- Căutăm, de parcă este posibilă împărțirea blocului prin tăiere verticală sau orizontală.
- Dacă ați putea - divizăm și începem în mod recursiv împărțirea fiecăreia dintre părți.
- Dacă nu au putut, ne oprim.
În ceea ce privește punctul de împărțire a blocului. Două metode sunt sugerate: fie pe lumenul alb (poate fi găsit pe proiecția blocului pe o axă orizontală sau verticală), fie pe o linie dreaptă neagră lungă și bine izolată.
Ca urmare a tuturor acestor diviziuni, se obține o structură arborescentă, la fel ca în dreapta din dreapta figurii:
Să spunem cu blândețe, nu cea mai obișnuită configurație, chiar și pentru ziare, să nu mai vorbim de reviste și documente de birou. Dar se întâmplă, în ziare cu siguranță.
O problemă mai gravă a algoritmului este totuși subordonarea sa pragurilor. Spuneți pe un astfel de fragment va fi dificil să separați titlul de text fără a rupe antetul:
Și aici va fi destul de dificil să separăm imaginea de text, bazându-ne doar pe pragurile de distanță:
Desigur, cu atât mai relevante și comune pentru toate prezentate în această problemă posta algoritmi - nu se rupe numerotarea listei numerotate și cum să scape de limitările pe care le am la început (există doar text și imagine cu contrast ridicat).
Segmentarea folosind dreptunghiurile albe maxime
Acum, să vorbim despre ideea segmentării unei pagini utilizând dreptunghiurile albe maxime. Care este "dreptunghiul alb maxim"? Albul înseamnă că nu există puncte negre în el (este clar că imaginea trebuie mai întâi să fie eliminată de mici resturi). Maximal înseamnă că nu poate fi mărită nici la stânga, nici la dreapta, nici în sus, nici în jos, astfel încât să rămână albă. În continuare, în loc de puncte negre, vom lua în considerare domeniile conectate. Ca și în secțiunile recursive, le putem grupa într-un fel, dar din nou nu ne vom ocupa de asta. Este clar că pentru aproape fiecare pagină scanată de astfel de dreptunghiuri albe - zeci de mii. Dar, în scopuri de segmentare, pot fi necesare numai cele mai mari. Un algoritm pentru căutarea lor este propus în articolul lui Thomas M. Breuel. Două algoritmi geometrici pentru analiza aspectului
al doilea algoritm din aceste "două" evidențiază liniile dintre aceste delimitatoare albe, dar, mi se pare, nu este deosebit de important, dacă cineva este interesat, a se vedea articolul.
Să revenim la problema găsirii dreptunghiurilor albe maxime. Puteți introduce conceptul de "calitate" pentru un dreptunghi.
Se numește funcția de calitate Q (r) pentru dreptunghiul r monoton. dacă Q (r1) = 1) este îndeplinită pentru r1 ⊆ r2, iar T2 și Ta sunt două praguri suplimentare. Înțelesul acestei condiții este acela că merită combinate două cuvinte într-o linie, dar dacă aceste două cuvinte au înălțimi diferite, atunci este necesar să se unească celulele cu mai multă prudență.
După ce ați găsit toate celulele pe care doriți să le îmbinați, combinați-le - iar diagrama Voronoi se transformă într-o segmentare gata.
Dezavantajele diagramei Voronoi sunt din nou aceleași - restricțiile depind doar de praguri, aceeași ambiguitate cu imaginile. Avantajul fără îndoială al acestei metode este, de asemenea, acela că conține doar trei parametri care trebuie selectați - și acești parametri sunt specificați în mod explicit.
Acest lucru încheie analiza mea privind progresele științifice legate de segmentarea paginilor. Și știința, cred eu, încă mai spun cuvântul său :)