Tag: parsowanie

Czasem próba zmierzenia się z (na pozór) niewinnym pytaniem, prowadzi do bardzo interesujących rozwiązań. Myślę, że dzisiejszy gościnny wpis Michała Kurtysa, będzie tego świetnym przykładem. Aby dowiedzieć się ile samorządy wydają na transport publiczny będziemy musieli zmierzyć się z narzędziami do digitalizacji pdf’ów, rozpoznawania tekstu oraz parsowania tabel. Będzie technicznie, będzie ciekawie.

—

Ile pieniędzy samorządy wydają na transport publiczny?
Jak wyekstraktować informacje z plików PDF, które zawierają dane w postaci obrazków?
Budżety samorządów.
Michał Kurtys

Ile pieniędzy wydaje moje miasto na transport publiczny? Czy to dużo?
Kiedyś zasłyszałem, że istotnie niemało. Zajrzałem zatem do budżetu miasta na rok 2013.
Wartość bezwzględna tej liczby wydała się faktycznie odpowiadać tej opinii.
Nie znam się jednak na transporcie. Ta kwota, choć spora, mogła być niezbędna. Postanowiłem zobaczyć więc, jak to wygląda na tle innych miejscowości.
Oczywiście odnosząc się do innych miejscowości w dalszym ciągu nie będzie to dokładne porównanie, chociażby z uwagi na różny stan taboru czy cenę biletów, ale zawsze jest to jakiś punkt odniesienia.

W dalszym ciągu zagadnienie transportu publicznego będzie służyło jako przykład.
Doszliśmy do momentu w którym interesować nas będzie ogólny problem zgromadzenia danych z budżetów samorządów.

Budżety zazwyczaj znajdziemy w biuletynie informacji publicznej danego samorządu, samorząd musi takie informacje publikować. Znalazłem stronę na której są odnośniki do BIP-ów poszczególnych jednostek samorządowych (http://www.bip.gov.pl/subjects/index/4600).

Teoretycznie wystarczyłoby wybrać interesujące nas podmioty (np. rady miast w województwie dolnośląskim).
Następnie dla każdego BIP-a odpalić crawler, który znalazłby dla nas ustawę budżetową.
Sam pisałem taki program w pythonie korzystając z biblioteki Scrapy.
Niestety bez rezultatów. Strony są bardzo zróżnicowane i trudno znaleźć odpowiednią regułę dla poszukiwań.

Sytuację trochę (za chwilę okaże się, że nie całkowicie) ratuje dziennik ustaw.
Dla woj. dolnośląskiego znajduje się pod adresem http://edzienniki.duw.pl/duw/ActByMonthYear.aspx#.

Znajdziemy tam ustawy uchwalone przez samorządy terytorialne, wśród nich oczywiście ustawy budżetowe.
Zacząłem od pobrania wszystkich ustaw z roku 2013. Tym razem nie użyłem biblioteki Scrapy.
Strona ładuje zawartość tabeli w sposób dynamiczny i znacznie wygodniej było skorzystać z biblioteki Selenium.
Skrypt do odczytywania danych z użyciem tej biblioteki można znaleźć tutaj. Nie jest napisany najpiękniej ale działa. [dzcrawler.py]

Następnie wybrałem te ustawy, które:

• zostały uchwalone przez radę miejską lub radę miasta i gminy
• dotyczyły uchwały budżetowej
• nie dotyczyły zmian budżetu

Lista ustaw: [miasta2013.csv]

Interesujące mnie dokumenty pobrałem za pomocą prostego skryptu i programu wget. [downloader.py]

Przyglądając się jednak tym, co udało się pobrać, zostałem niemile zaskoczony niekompletnością listy budżetów.
Przykładowo w pobranych plikach brakuje budżetu dla miasta Lubin. W biuletynie informacji publicznej znajdziemy ją wśród uchwał z dnia 26 lutego 2013.
http://www.bip.um-lubin.dolnyslask.pl/dokument.php?iddok=2449&idmp=49&r=o

Dla tego dnia w dzienniku znajdziemy tylko jeden dokument:

Rada Miejska w Lubinie	Uchwała	2013-02-26 	2013-04-24 	uchwała nr XXXIV/261/13 Rady Miejskiej w Lubinie z dnia 26 lutego 2013r. w sprawie Regulaminu utrzymania czystości i porządku na terenie Gminy Miejskiej Lubin.

Nie wiem dlaczego w dzienniku nie ma wszystkich uchwał.
Co gorsza nie są to pojedyncze przypadki.
W dalszej części będziemy po prostu pracować z mniejszym zbiorem.
Brakujące dokumenty można oczywiście znaleźć i pobrać ręcznie.
Mając w planach automatyzację analiz dla całego kraju, jestem trochę zawiedziony brakiem kompletności i automatyzowalności procesu pozyskiwania budżetów z BIP.

Przyjrzyjmy się ściągniętym danym. Wszystkie ustawy są zapisane w formacie PDF.
Większość dokumentów ma podobną strukturę. Zawierają przede wszystkim bardzo dużo tabel.
Bardzo cieszy fakt, że w prawie każdym dokumencie, znajdziemy tabele, które są niemal identyczne. [patrz rys. 1 ]. Jeszcze bardziej, że jest to pewne podsumowanie. Jeżeli chodzi o problem transportu, to jest w nich wszystko czego potrzebujemy i wszystkie inne moglibyśmy zignorować.

I tu znajdują się wyjątki od reguły. Część dokumentów ma zupełnie oryginalną strukturę np. Wrocław.
Dla każdego takiego przypadku należałoby implementować zmodyfikowany algorytm.
Zajmiemy się zatem tylko większością.

Jak wspomniałem interesujące nas dane są zapisane w tabelach.
Te zaś w praktycznie każdym przypadku są obrazami umieszczonymi w dokumencie, co oznacza, że aby wyciągnąć z dokumentu liczby należy użyć jakiejś biblioteki do rozpoznawania tekstu.
W tym projekcie użyłem silnika Tesseract. Program ten został stworzony przez firmę HP, w 2005 roku jego kod został uwolniony, a teraz jego rozwój sponsoruje Google.
W tej chwili prawdopodobnie jest najlepszym opensourcowym silnikiem OCR. Co ważne w aktualnej wersji potrafi również rozpoznawać język polski bez dodatkowego treningu.
Tesseract udostępnia interfejs dostępny z poziomu linii komend oraz API programisty.
Istnieją również graficzne frontendy zarówno dla systemów Windows jak i Linux.

Zanim jednak odpalimy tesseract potrzebujemy przekonwertować dokument do postaci pliku graficznego takiego jak .png czy .jpg.
Można do tego użyć programu convert z pakietu ImageMagick (wymaga zainstalowanego GhostScripta).
Renderuje on każdą stronę dokumentu z określoną przez użytkownika rozdzielczością (w dpi).

convert -density 600 plik.pdf  obraz%d.png

Alternatywą jest użycie pdfimages (poppler-utils), który po prostu wyciąga wszystkie obrazy z pliku PDF.
W tym przypadku jest to lepsza droga – otrzymujemy faktycznie to czego potrzeba, a i obrazy na pewno będą mieć oryginalną rozdzielczość.

Z nieznanych mi przyczyn odczytując budżet Lwówka Śląskiego zarówno convert jak i pdfimages wpadały w nieskończoną pętlę. Sytuacja na szczęście nie powtórzyła się dla innych miast. Po odczytaniu każdego dokumentu otrzymujemy katalogi z plikami graficznymi.
Oczywiście nie wszystkie z nich przedstawiają tabelę. Zwykle jednak nie-tabele to pojedyncze obrazki. Nawet nie usuwałem ich, po prostu po skanowaniu dadzą pusty wynik.

W obecnej wersji tesseract nie radzi sobie ze złożonym układem graficznym strony z tekstem.
Nie możemy uruchomić tesseracta bezpośrednio na pliku graficznym z tabelą. W wyniku dostalibyśmy po prostu mnóstwo śmieci.

Aby temu zaradzić wytniemy każde pole tabeli i przekażemy je do tesseracta.
Zanim pokażę jak podzielić tabelę, chciałbym poruszyć jeszcze jedną kwestię.

Gdy sam wdrożyłem powyższy pomysł w życie, spotkała mnie niemiła niespodzianka. Rezultat był raczej średnio zadowalający – bardzo często występowały „literówki”.
Kiedy spojrzymy w powiększeniu na tekst zobaczymy, że jest lekko rozmyty. Próbowałem różnych filtrów by poprawić jakość, ale bez większego skutku.
Tesseract pracuje wyłącznie na binarnych obrazach (jeżeli dostaje obraz nie-binarny przeprowadza binaryzację). Pomyślałem więc, że może dla antyaliasowanego tekstu warto byłoby napisać własny silnik?
Poruszyłem ten temat na stackoverflow: http://stackoverflow.com/questions/21827854/ocr-on-antialiased-text
Rozwiązanie było trywialne. Tekst był renderowany z użyciem technologii ClearType, dzięki której tekst wygląda lepiej na ekranach LCD.
Działanie polega na sprytnym „zwiększeniu rozdzielczości” wyświetlacza poprzez wykorzystanie horyzontalnego ustawienia subpixeli.
Wiedząc o tym rozbijamy każdy piksel na 3 subpiksele i zapisujemy ich wartość w odcieniach szarości.
Otrzymamy więc obraz o 3x większej poziomej rozdzielczości niż wejściowy. A to wystarczy, żeby OCR działał jak trzeba.
Jeżeli Czytelnik zainteresowany jest szczegółami to polecam wątek w stackoverflow, czy chociażby artykuł w wikipedii.
Przykładowy kod w pythonie i opencv dokonujący tą operację: [unsubpixel.py]

Teraz możemy wrócić do problemu formatu tabeli. Tabele jak zauważyliśmy nie są skanowane, a renderowane w jakimś programie. Oznacza to, że mamy ułatwione zadanie, ponieważ wszystkie linie są idealnie pionowe lub poziome
Pierwszym krokiem jest zatem znalezienie wszystkich odpowiednio długich linii pionowych i poziomych.
Tak znalezione linie nanosimy na czysty obraz, dostając „szkielet” tabeli (+ w rzadkich przypadkach drobne śmieci).

Teraz wystarczy znaleźć punkty przecięcia linii i wyznaczyć odpowiednie pola.
W bibliotece opencv możemy jednak ułatwić sobie zadanie wykorzystując funkcję findContours.
http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=findcontours#cv.FindContours
Mając dany obraz binarny funkcja ta znajduje kontury obiektów.
Ponadto zwraca również hierarchiczną strukturę kształtów w obrazie. Najlepiej zobaczymy to tutaj:

Obraz pochodzi z dokumentacji opencv:
http://docs.opencv.org/trunk/doc/py_tutorials/py_imgproc/py_contours/py_contours_hierarchy/py_contours_hierarchy.html#contours-hierarchy

Biorąc obiekty na samym dnie hierarchii otrzymamy najbardziej wewnętrzne kształty, czyli pola tablicy.

    vector > contours;
    vector hierarchy;

    Mat lines_img_cpy = lines_img.clone();
    findContours(lines_img_cpy,contours_all, hierarchy, RETR_TREE, CHAIN_APPROX_SIMPLE);
    
    for( unsigned int i=0; i< hierarchy.size(); i++)
    {
        if( hierarchy[i][2]==-1 )
            contours.push_back(contours[i]);
    }

///////////////////////////////////////////////
Tesseract dostarcza również całkiem wygodne api
///////////////////////////////////////////////

    tesseract::TessBaseAPI *api = new tesseract::TessBaseAPI();
	if (api->Init(NULL, "pol")) {
        fprintf(stderr, "Could not initialize tesseract.\n");
        //exit(1);
        return results;
    }

    for (unsigned int i = 0; i < contours.size(); i++)
    {
         int minx = img.cols;
         int maxx = 0;
         int miny = img.rows;
         int maxy = 0;
        for (unsigned int j = 0; j < contours[i].size(); j++)
        {
            minx = min(minx,contours[i][j].x);
            maxx = max(maxx,contours[i][j].x);

            miny = min(miny, contours[i][j].y);
            maxy = max(maxy, contours[i][j].y);

        }
        Mat subimg = img(Range(miny, maxy), Range(minx, maxx));
        api->SetImage(subimg.data, subimg.cols, subimg.rows, 1, img.cols);
        outText = api->GetUTF8Text();
        results.push_back(outText);
		//////////////

Ostatnią rzeczą, którą należy zrobić to uporządkowanie wyników, które dostaliśmy.
Tutaj „idealność” renderowanej tabeli znowu upraszcza sprawę.
Kontury o tej samej współrzędnej y będą tworzyły jeden wiersz.
Trochę inaczej jest w nagłówkach, ponieważ mają one wielopoziomową strukturę.
Gdy jeszcze raz spojrzymy na przykładową tabelę, możemy zauważyć, że w ostatnim wierszu nagłówków szerokości pól są identyczne jak w pierwszym wierszu danych.
To całkiem dobra heurystyka do oddzielenia danych od nagłówków.

Warto wiedzieć które kolumny to przychody, a które koszty.
Aby nie stracić informacji. Przejdziemy po nagłówkach w dół jak po drzewie.
Kolejne kolumny nazwiemy więc:

"LP'  "
"Dz.  "
"Rozdz.  "
"Nazwa  "
"Stan srodkow obrotowych na początek  roku  "	
"Przychody /ogółem  "
"Przychody/w tym dotacja przedmiotowa /Kwota  "
"Przychody  /w tym dotacja przedmiotowa  /zakres dotacji  "
"dotacja celowa inwestycyjna /Kwota  "	

i tak dalej.
Dla każdej tablicy tworzymy dwa pliki wyjściowe:
Jeden zawierający współrzędne pola i jego zawartość.
W drugim wyniki zawierające zapisane wierszami.

Wyniki:
Z powodu wszystkich trudności, które wymieniłem w artykule, ostateczna baza miast jest bardzo skromna.
Oczywiście, część z problemów jest do przeskoczenia. Na pewno przetworzenie plików o „specjalnej” strukturze

Transport:
Skorzystamy z tego, że w pliku zawsze istnieje podsumowująca tabela o w miarę niezmiennym kształcie.
W skrypcie przeszukujemy wyniki skanowania tabel o ilości kolumn równej 16,17 lub 18.
Jeżeli znajdziemy identyfikator Transportu Lokalnego równy „60004”, to wypisujemy wartość wydatków na ten cel.

Koniec końców udało się wyciągnąć wielkość wydatków na transport lokalny w różnych miastach województwa dolnośląskiego.

python.exe list_big.py
Bolesławiec-007_table.txt 3 280 000
Dzierżoniowa-006_table.txt 1 850 000
Kątach-025_table.txt 460 000,00
Oławie-015_table.txt 900 000
Piławie-005_table.txt 250 000
Zgorzelec-029_table.txt 290 000
Złotym-012_table.txt 3 000.00
Świdnicy-014_table.txt 8 636 090
Świebodzicach-008_table.txt 823315