Texterkennung in Vektorgrafik(HPGL) oder in Bitmaps(TIFF...)

[zafira]

hallo zusammen,

ich habe eine frage: ich möchte aus grafiken, die originär als HPGL (also vektorformat) vorliegen, text extrahieren. von diesem text weiß ich nur die ausrichtung (horizontal, vertikal) und die ungefähre position in der grafik - also muß nicht die gesamte grafik "gescannt" werden. Es handelt sich nicht um fließtext von 1000 seiten, sondern um strings in einem umfang von ca. 20 - 30 zeichen. allerdings handelt es sich um CAD-zeichensätze, die nicht unbedingt an jeder windows/linux-hausecke gefunden werden. für die einzelnen fonts müßte man sich dann eben ein eigenes alphabet mit den geometrischen ausprägungen selbst definieren.

das parsen der datei stellt nicht das problem dar, sondern der aus aus einzelnen linien- (oder auch kreisbogen-)segmenten bestehenden zeichen. nach etwas recherche im web kristallisierten sich - bislang - 2 mögliche wege heraus:

- bilderkennung mit Fast Fourier Transformation, wobei ich die genaueren mathematischen hintergründe noch nicht erforscht habe - entsprechende literaturhinweise/links zu tutorials über das "wie, wann und warum" für "durchschnittsmenschen" sind gerne willkommen. stichwort: wie erkenne ich aus einem "strichhaufen" ein einzelnes zeichen?

- texterkennung (OCR): nun angesichts deer eingeschränkten zeichenlänge (siehe oben 20-30) sehe ich das eher in der region "kanonen auf spatzen"....

für den fall, daß sich die HPGL-dateien nicht originär bearbeiten ließen, könnte ich mir noch eine temporäre konvertierung in ein pixelformat (tiff oder png) vorstellen. vielleicht gibts ja auch einen ganz anderen lösungsansatz?

danke für eure hoffentlich - zahlreichen - antworten!

zaf

ich komme mir mit meiner frage vor wie der rudi assauer in der veltins werbung: nur angucken, nicht anfassen... die fragestellung scheint viele zu interessieren, aber geantwortet hat noch keine(r)

[Sr4l]

Speichert das CAD Format nicht in Textformat wo der Text dann mit Positionsangabe im Klartext stehet?


Ich habe folgendee OCR Anwendung schon erfolgreich eingesetzt:
http://sourceforge.net/projects/tesseract-ocr
Doch habe ich keine Erfahrung wie es sich verhält, wenn nicht nur Text im Bild ist.

[zafira]

Hallo,

bei der vektorgeometrie handelt es sich um HPGL, also eine ursprünglich für die guten alten stiftplotter entwickelte sprache. die stiftsteuerung wurde zu anfangs mit reinen liniensegmenten durchgeführt. d. h. der plotter machte auch bei kreisbögen eine approximation aus vielen kleinen liniensegmenten. im laufe der zeit kamen dann weitere sprachelemente hinzu, so daß die späteren plotter durchaus dann auch richtige kreise zeichnen konnten.

lange rede kurzer sinn. HPGL liegt in ASCII vor (teilweise sind auch steuerzeichen drin, die einen HEX-editor notwendig machen) und ich würde die texte die als "strichhaufen" vorliegen gerne wieder als texte haben, zumindest als einzelne zeichen.

ich habe vor vielen jahren mal was gehört von der fourier transformation um geometrische ähnlichkeiten zu untersuchen. dort wird ein ortsbild in den fourierraum transferiert und in eben diesem sind geometrische untersuchungen leichter durchführbar als im ortsraum. [/b]

[BlackJack]

Wie allgemein muss dass den sein? Wenn immer die gleiche Schriftart mit dem selben Programm geplottet wurde, könnte es ja sein, dass für den gleichen Buchstaben immer die gleiche Strichfolge benutzt wird und die sich damit als Muster in den HPGL-Daten erkennen lassen, dass sich nur durch Position und Skalierung unterscheidet.

Wenn dann noch die Software existiert könnte man die einzelnen Zeichen plotten um diese Muster zu ermitteln.

[zafira]

Wie allgemein muss dass den sein? Wenn immer die gleiche Schriftart mit dem selben Programm geplottet wurde, könnte es ja sein, dass für den gleichen Buchstaben immer die gleiche Strichfolge benutzt wird und die sich damit als Muster in den HPGL-Daten erkennen lassen, dass sich nur durch Position und Skalierung unterscheidet.

Wenn dann noch die Software existiert könnte man die einzelnen Zeichen plotten um diese Muster zu ermitteln.

ich kann schon aus einigen HPGL-files ein alphabet erstellen. und es muß auch nicht sehr allgemein sein, da vermutlich nur einige wenige verschiedene fonts verwendet wurden.

der erste ansatz war auch, daß ich die liniensegmente sammle und gruppiere, um damit ein muster erkennen zu können. aber die sache steigt exponentiell an, da es sich bei den liniensegmenten um vektoren handelt und die richtungen dann unterschiedlich sein können. auf dem papier spielt das natürlich keine rolle, für die analyse jedoch schon.

dies wäre ein ansatz nach dem motto: ein klein wenig ist besser als gar nix. ich bin der meinung, daß es irgendwie auch noch eleganter gehen muß.

zaf

[thelittlebug]

Irgendwie erinnert mich das Problem an die "Mousegestures" im Opera. Da wird ja die Bewegung der Mouse als Vektoren gehandhabt und dann erkannt. Irgendwie solltest du vorher aber versuchen einzelne Zeichen herauszufiltern.

Ich würde dazu die ganzem Bewegungen des Stiftes in Linien umwandeln und dann mit einem Quadtree gruppieren.
Sollten sich nun BEreiche im Quadtree finden die eine bestimmte Anzahl an Vektoren enthält die alle auch in etwa die größe eines Buchstabens ergeben..... blablabla....
So, oder so ähnlich

lgherby

[veers]

Quick & Dirty: in ein Bitmap Konvertieren, Text so genau wie möglich Lokalisieren. Dannach einfach jeweils Blockweise mit einer Datanbank von Samples vergleichen. Dürfte, wenn ich das Problem richtig einschätze, schon reichen. Vermutlich musst du das ganze noch etwas unscharf machen - mehrere Samples für die Blocks nehmen und vergleichen.

Ist nicht elegant oder generisch Anwendbar aber vermutlich in einem Nachmittag geschrieben.

[thelittlebug]

na gut, dann könnte man gleich ne OCR drüberlaufen lassen. sowas gibts fertig für die commandline: http://www.gocr.de/

damit hat man eigentlich fast nur noch die aufgabe die vectordaten in bitmaps umzuwandeln. und siehe da, die software hp2xx kann hpgl dateien in bitmaps umwandeln, auch für die commandline

damit wird die aufgabe vielleicht doch zum 3 zeilen bashscript

lgherby

[zafira]

hallo zusammen,

also ich habe das mal probiert. die ergebnisse sind... nicht so wirklich prickelnd, aber es besteht sicher noch optimierungspotential. der gocr brachte tendentiell etwas bessere ergebnisse als tesseract.

trotzdem würde mich die mathematik hinter der fourier transformation mit vektoren (über pixelbilder findet sich so manches) interessieren. weiß da jemand was drüber? ich weiß, daß es ein etwas theoretisches thema ist, aber vielleicht ist schon mal jemand über sowas drüber gestolpert?

grüße

zafira

[thelittlebug]

Wenn mich nicht alle täuscht ist die fft immer an Vektoren vorzunehmen, also auch wenn du es an Sound oder Bitmapdateien verwendest.

Der Unterschied ist imho ob ich es an 1D, 2D od. 3D Daten verwende und das suchen von FFT oder DFT Algo's für 2D sollte nicht so die Aufgabe sein, oder versteh ich irgendetwas falsch?

Zeig mal Beispieldaten, deine Aufgabe ist noch immer sehr generell da wir keine echten Anhaltspunkte haben.
Aber für welchen Weg du dich im Endeffekt auch entscheiden wirst, eines bleibt dir sicher nicht erspart: Das Aufbereiten der Daten.

Fang einmal damit an bevor du dich in Gebiete wagst in denen es "seltsam" wird. Aus einem Strichhaufen, wie du Ihn selbst nennst, wirst du auch nicht viel mehr herausbekommen als einen FFT Haufen.

Meine Lösungsstrategie hab ich bereits einmal kurz anklingen lassen, hier nun etwas genauer.
1. Du weißt wo sich die Buchstaben in etwa befinden. Wunderbar, alles andere muss weg. Geht ja schnell.
2. Alles was nicht gezeichnet wird muss weg ( Stift ist oben und drückt nicht aufs Papier )
3. Lass dir ein paar andere Sachen einfallen unerwünschtes zu entfernen. Z.b. wäre es ja durchaus möglich anhand der Linienlänge wieder ein paar Linien zu entfernen -> Linie länger als Linien eines Buchstaben sein könnten -> iiiiih, weg damit. Vielleicht finden sich ja auch noch andere Anhaltspunkte, vielleicht Stifttyp und/oder Farbe.
4. Wandel was überbleibt in irgendetwas absolutes um damit du absolute Koordinaten hast mit 2 absoluten Punkten die eine Linie spannen.
5. Mit absoluten Koordinaten hast du nun durchaus eine Chance Buchstaben oder zumindest Blöcke aus dem ganzem herauszufiltern. Alternativ wandel es in ein Pixelformat um ( beachte: vernünftige Linienbreite, hohe DPI (300), vernünftige Buchstabengröße, SW ) um es dann bereits aufbereitet durch eine OCR zu werfen.

Alternativ, da ich nicht über die Menge der Daten bescheid weiß, hätte ich bei < 1000 Blättern eine günstige Praktikantin eingestellt
Die sollte das auch in 2 Tagen erledigt haben.

lgherby

edit: ein Punkt in einer Bitmap ist auch ein Vektor der eine x und eine y Koordinate hat.

[zafira]

hallo littlebug,

ja, das mit der geometriebereinigung dachte ich mir auch, als ich die ersten versuche gemacht habe. prinzipiell ist das auch ein gangbarer ansatz. aber jetzt wacht das tier in mir auf das tier auf und mich würde der andere ansatz interessieren.

also, agenommen ich habe 3 2D-linien. die linien haben die koordinaten (semikolon ist koordinatentrenner, komma dezimaltrenner):

L1 = (0;0) (10;30)
L2 = (10;30) (20;0)
L3 = (3,33;10) (16,67;10)

in vektorieller schreibweise:

a1 = (10-0;30-0) = (10;30)
a2 = (20-10;0-30) = (10;-30)
a3= (16,67-3,33;10-10) = (13,33;0)

hoffe, der input hilft dir.

zafira

[CM]

trotzdem würde mich die mathematik hinter der fourier transformation mit vektoren (über pixelbilder findet sich so manches) interessieren. weiß da jemand was drüber? ich weiß, daß es ein etwas theoretisches thema ist, aber vielleicht ist schon mal jemand über sowas drüber gestolpert?

Das ist mir zu vage: Ich weiß nicht was es heitß eine FT auf "Vektoren" anzuwenden. Aber was ich mir vorstellen kann ist, daß die Translationsinvarianz einer FF bei der Mustererkennung hilft. Außerdem fällt es mittels FT rel. leicht unterschiedliches Spannen von Grauwerten zu behandeln.

Lange Rede kurzer Sinn: Nach dem bisher geschriebenen glaube ich nicht, daß die Anwendung von FTs Dir irgendwie weiterhilft. -- Aber ich kann mich da auch irren.

Gruß,
Christian

PS Link zum Einlesen in Fouriertransformationen: http://mathworld.wolfram.com/FourierTransform.html

[thelittlebug]

L1 = (0;0) (10;30)
L2 = (10;30) (20;0)
L3 = (3,33;10) (16,67;10)

in vektorieller schreibweise:

a1 = (10-0;30-0) = (10;30)
a2 = (20-10;0-30) = (10;-30)
a3= (16,67-3,33;10-10) = (13,33;0)

Das ist keine "vektorielle" Schreibweise. Du verwechselst das gerade mit absoluten und relativen Angaben. Ich würde wie bereits gesagt zuerst mal das ganze in absolute Koordinaten umwandeln damit ich in etwa auf folgendes komme:
p1 = (10,30)
p2 = (10,-30)
p3 = (13.33,0)
l1 = (0,1)
l2 = (1,2)

Damit hätte ich 3 Punkte und 2 Linien (ist nur ein Beispiel). Mit dieser Art von Daten lässts sichs dann relativ einfach arbeiten.
-> Bereite die Daten so auf wie sie eine Renderingengine benötigen würde, OpenGL und DirectX wären hier 2 prominentere Beispiele.

relativ = Stiftbewegung
absolut = wo fängt oder hört der Stift zu Zeichen auf

lgherby

[thelittlebug]

Lange Rede kurzer Sinn: Nach dem bisher geschriebenen glaube ich nicht, daß die Anwendung von FTs Dir irgendwie weiterhilft. -- Aber ich kann mich da auch irren.

Ich bin da der selben Meinung.