PDF-Doks auf doppelte Seiten vergleichen

[frieder2008]

Liebe Leute,

ich habe ein Datenproblem, bei dem ich via Google nicht weiterkomme, sprich, ein fertiges Tool scheint es nicht zu geben. Bliebe also nur die eigene Programmierung. Zu dem folgendem Thema habe ich aber überhaupt keine Erfahrung:

- Ich habe etwa 180T PDF-Dokumente (mit unterschiedl. Dateinamen)
- jedes PDF hat mind. 1 Seite, manchmal mehrere
- Es ist davon auszugehen, dass manche Seiten in verschiedenen PDF-Dokumenten zugleich / parallel (!) vorhanden sind

Da ich die Daten zu Forschungszwecken benötige, muss ich doppelte Seiten ausschließen.

Welchen Ansatz könnte ich wählen, damit ich idealiter - vor einer Konvertierung in RTF oder gar via mühsamer / fehlerträchtiger Duplikat-Suche auf Basis von TXT-Äquivalenten (die immer ein bisschen anders aussehen...) - solche doppelten Seiten oder Dateien mit gleichen Seiten identifizieren kann?

Bin für jeden Tipp dankbar!

Viele Grüße und schönen Abend wünscht:
der Frieder

[vagtler]

Ohne Konvertierung wird es hart. Ein Ansatz könnte die in http://superuser.com/questions/47320...n-pdf-document beschriebene Vorgehensweise sein.

[Bernhard Geyer]

Zitat von frieder2008:

... dass manche Seiten in verschiedenen PDF-Dokumenten zugleich / parallel (!) vorhanden sind

Da ich die Daten zu Forschungszwecken benötige, muss ich doppelte Seiten ausschließen.

... fehlerträchtiger Duplikat-Suche auf Basis von TXT-Äquivalenten ...

Hier wäre zu definieren wann eine Seite gleich ist und als Duplikat gekennzeichnet werden muss und wann sie nur ähnlich ist.
Oder wäre sogar eine genauere Unterscheidung nötig wie sie z.B. bei http://de.vroniplag.wikia.com/wiki/Home gemacht wurde?
Müssen auch Bilder untersucht werden oder reicht der Text?

[p80286]

Je nachdem mit welchen Parametern das Dokument erstellt wurde, kann es intern ganz anders aussehen als ein Dokument, das z.B. gedruckt genau gleich aussieht.
Ich denke Du solltest mögliche ähnliche Seiten suchen (Textfragmente) und diese dann durch eigenen Augenschein erledigen.

Gruß
K-H

[frieder2008]

Moin zusammen,

zunächst mal Danke für Eure Rückmeldungen. Ja, nach weiterer Recherche sehe ich auch, dass ich zuerst in RTF wechseln muss. Das wollte ich eben machen und stelle eben fest, dass es ausgerechnet dieses Mal Probleme gibt (Adobe Acrobat Pro X): Die PDFs sind nicht geschützt, enthalten bereits super ocr-erkannten Text, aber bei der Konvertierung in RTF ist der Text nur als Bild enthalten. Konvertierung direkt in TXT scheitert gänzlich. Eine Idee, woran das liegen kann? Konvertierung erst in TIFF o.ä. und dann erneut OCR macht ja wenig Sinn, zumal die bestehende Erkennung bereits früher mal sauber korrigiert wurde.

Wenn ich die RTF habe, ist mir das Verfahren einigermaßen klar. Ich hatte gehofft, mir "manuelles" sparen zu können. Da die Seiten - zumindest für den jeweiligen Zeitraum der Erstellung - alle nach dem gleichen FOrmat aufgebaut sind, könnte es klappen via RegEx jeweils den Seitenkopf zu identifizieren und zu vergleichen. Aber ehe ich soweit bin, muss ich erst mal das PDF->RTF-Problem lösen.

Schöne Grüße,
Frieder

Edit: @vagtler: Das wäre in der Tat ein Ansatz, schaue ich mir nochmal genauer an!

[Harry Stahl]

Gängige Vorgehensweise bei Bearbeitung / Anzeige von PDF-Dokumenten ist, die PDF-Datei zu laden und dann sich eine Seite als Bitmap "rendern" zu lassen, die angezeigt werden soll.

Du könntest also entsprechend vorgehen, jede Datei öffnen, jede Seite rendern und von der Bitmap ein Fingerprint erstellen (z.B. MD5) und in eine Datenbank speichern (nebst Seitenzahl, Dateiname). Jedes mal, wenn Du das machst, vergleichst Du, ob der Fingerprint bereits in der Datenbank steht, wenn ja, erhöhst Du einen Zähler und/oder legst zusätzlich eine Information zum Fundort der doppelten Seiten an.

Ich arbeite in meinem PDF-Manager-Programm mit den DEBENU-PDF-Komponenten, die sind sehr schnell und zuverlässig.

[frieder2008]

Hallo Harry,

ok, darauf hätte man natürlich selbst kommen können. Da die einzelnen Seiten sehr wahrscheinlich eine gemeinsame Quelle haben (also alles mal aus einem einzigen Scan stammte und dann dateispezifisch Seiten kombiniert wurden), müsste das mit dem Rendern/Fingerprint hinhauen.

Hast Du zufällig auch einen Tipp zu dem Problem PDF->RTF-Problem?
Edit: Die Alternative, erst alles in TIFF und dann zurück OCR-Erkennung geht zwar, aber die OCR-Erkennungsqualität ist um Meilen schlechter als die bereits in den PDF-Quelldateien vorliegende...

Danke!

Schöne Grüße,
der Frieder

[Dejan Vu]

Blöd ist, wenn die eine Seite um einen Pixel versetzt gerendert wird und einige Graustufen doch anders sind.

D.h. sind die Seiten auch nach dem Rendern identisch, also 1:1 pixelgenau? Ansonsten würde ich die Bitmaps auf Ähnlichkeit hin vergleichen. Alternativ wäre aber es aber auch möglich, die PDF in reinen Text zu überführen und dann mit Diff-Tools 'große Gemeinsamkeiten' herauszufinden. Z.B. über Wortlisten je Seite. Dann kann man einen Ähnlichkeitsindex der Seiten erstellen.

Ähnlichkeitsindex (Seite1,Seite2) = Anzahl identischer Wörter (Seite1, Seite2) / Max (AnzahlWörter(Seite1)AnzahlWörter(Seite2))

Alles > 0.8 ist suspekt.

[Der schöne Günther]

Wollte ich auch grade sagen: Die PDF-Seiten optisch zu vergleichen finde ich auch die beste und zuverlässigste Methode, aber exakt gleich werden die wohl niemals sein. Deshalb müsste man da wirklich auf Ähnlichkeit und nicht Exaktheit prüfen.

[hanvas]

Zitat von Dejan Vu:

Blöd ist, wenn die eine Seite um einen Pixel versetzt gerendert wird und einige Graustufen doch anders sind.

Wenn nur der Text verglichen werden soll dann konvertiert man einfach in ein Schwarzweissbild - das beseitigt Probleme bei nicht übereinstimmenden Graustufen. Grundsätzlich lässt sich bei dieser Art von Problemen sagen das man, wenn man kann, immer alle Informationen weglassen soll die im Moment nicht notwendig sind.

Zitat von Dejan Vu:

D.h. sind die Seiten auch nach dem Rendern identisch, also 1:1 pixelgenau?

Wenn es sich so einfach darstellen würde wäre das Problem ja schon gelöst.

Zitat von Dejan Vu:

Ansonsten würde ich die Bitmaps auf Ähnlichkeit hin vergleichen.

Der Ähnlichkeitsindex von Bildern wäre/ist eine gute Idee wenn es bei dem Vergleich tatsächlich auf optische Gleichheit ankommt und das Ausgangsmaterial dem entspricht. Da gab es ja hier auch mal diese Veröffentlichung :

http://www.delphipraxis.net/144655-b...tion-zncc.html

Als Optimierung / Verbesserung würde ich vorher das zu vergleichende Bild auf die gleiche Größe wie das Referenzbild skalieren, dadurch würden auch gleich aussehende Dokumente erkannt werden wenn beispielsweise eines A4 und eines A5 wäre.

Falls es sich um Formulare handelt kann mann normalerweise die Linienstruktur vergleichen, da die meisten Formulare Striche, Kästen und ähnlichen optische Elemente haben funktioniert das ganz gut. Das wäre dann die Anwendug der Hough-Transformation und ein Graph-Matching.

Wenn inhaltliche Gleichheit gefragt ist dann muss man sich Klarmachen das der gleiche Text vollkommen unterschiedlich aussehen kann, beispielsweise wenn er mal in einer mal in zwei in Spalten formatiert ist, mal mit Grafiken angereichert ist und mal ohne usw. und das der optische Vergleich einen dann vollkommen in die Irre führen kann.

In diesem Fall müsste man zunächst die Elemente/Zonen auf dem Dokument indentifizieren und versuchen festzustellen welcher Art die Zonen sind. Entweder man bastelt das selbst, was aber nicht ohne ist, als erster Ansatzpunkt sei der y-x Cut Algorithmus genannt der ein Dokument in Zonen zerlegen kann oder man greift auf eine OCR/OCR zurück die diese Information auch liefert.

Wenn es kein Geld kosten darf kommt man mit Tesseract ganz gut weiter, es gibt sogar einen Wrapper in FPC dafür.

http://code.google.com/p/tesseract-ocr/

Ich selbst verwende das relativ preisgünstige OCR SDK von Nicomsomft. Kostet für In-House Anwendungen so um die 400 €, ich habe ein wenig mehr als 1200 € dafür bezahlt um meine Anwendungen auch weitergeben zu dürfen :

http://www.nicomsoft.com

Preislisch nach oben offen sind die SDKs von ABBY, Leadtools und vielen anderen.

Anschließend zerlegt man sein Dokument in Zonen. Wenn man es perfekt machen will dann baut man sich aus den Zonen einen Baum der das Dokument beschreibt (bzw. verwendet den oben genannten y-x cut algorithmus der bei richtiger Implementierung einen Baum liefert) und vergleicht die Bäume untereinander. Wenn man es etwas einfacher mag dann vergleicht man zunächst gleichartige Zonen miteinander indem man einen einfachen Feature-Vektor bildet


1. Anzahl der Bildzonen - Anzahl der Bildzonen im Referenzbild
2. Anzahl der Textzonen - Anzahl der Textzonen im Referenzbild
3. Anzahl der Barcodes - Anzahl der Barcodes im Referenzbild
usw.

Für die jeweiligen (nicht Text-Zonen ) sucht man dann die am bestem passenden Übereinstimmen die sich eindeutig bilden lassen. Am Beispiel von Bildzonen :

Vergleiche alle Bildzonen miteinander (beispielsweise mit dem ZNCC) - gruppiere diese Eindeutig so das die Summe der Ähnlichkeiten max. wird

und nimmt diesen Wert in den Eigenschafts-Vektor auf. Das gleiche macht man für Barcodes, Texte usw.

Bei Textzonen muss man aufpassen ob die Aufteilung in Zonen eine Rolle spielt oder ob nur der Text relevant ist. Falls nur der Text relevant ist kann man den Vergleich auf Wortbasis über alle Zonen ziehen und daraus wieder einen Feature-Vektor aufbauen. Entweder man baut den Vektor aus allen vorkommenden Worten auf, oder nur aus bestimmten Schlüsselwörtern. Im Fall 2 ist das aber eher die Prüfung ob zwei Dokument in die gleiche Kategorie fallen.

Beispiel für der, die, das

1. Anzahl des Wortes "der" in Doc 1 - Anzahl in Doc 2
2. Anzahl des Wortes "die" in Doc 1 - Anzahl in Doc 2
3. Anzahl des Wortes "das" in Doc 1 - Anzahl in Doc 2

Falls auch die Lage bzw. der Aufbau des Dokumentes in den Vergleich eingehen soll dann müssen eben die Zonen vergleichen werden und nicht der gesamte Text. Die Prüfung auf einzelen Wörter hat übrigens den Vorteil das Formatierungsanweisungen ausgefiltert werden können.

Die Vektoren auszuwerten ist dann nur noch ein untergeordnetes Problem.

cu Ha-Jö