Sortieren von bboxes anhand von Schwerpunkten (centroids)

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
Felix92
User
Beiträge: 133
Registriert: Mittwoch 7. November 2018, 17:57

Huhu,

ich habe gerade folgendes Problem:
Und zwar bekomme ich die bounding boxen im post processing meiner Texterkennung nicht korrekt sortiert (von links nach rechts und oben nach unten)
Die Möglichkeit der Gruppierung in Bereiche/ Konturfindung, etc. anhand des Eingabebildes besteht nicht und würde vermutlich auch nur mittelmäßig funktionieren.

Was habe ich zur Verfügung:
  • shape des Eingabebildes
  • ymin xmin ymax xmax - Koordinaten
Versuche:
  • left-right / top-bottom sort ist fehlgeschlagen, durch einige Outlier (zu ungenau trotz Gewichtung mittels shape)
  • das sortieren über die Mittelpunkte der Boxen das selbe Problem
  • mit Distanzen lässt sich auch schwer arbeiten, da die einzelnen Boxen sehr nah beieinander liegen können bzw. teilweise auch überlappen
Eine Idee wäre noch per Clustering z.B.: DBSCAN erstmal Bereiche zu gruppieren um wiederrum in diesem Crop zu versuchen die Boxen korrekt zu sortieren

Ziel ist es am Ende: die einzelnen Boxen in Linien und Blöcke zu sortieren anhand der Koordinaten der einzelnen Boxen (was sobald die Reihenfolge der Boxen stimmt nicht mehr das Problem ist :roll: )

Hier mal einige Beispiele:
Mittelpunkte der Boxen
Bild
left upper / right upper Ecken
Bild
Und noch ein Beispiel eines anderen Dokumentes
Bild

Vlt. hatte von euch ja schon mal jemand das selbe Problem oder Ideen oder was auch immer :D
Benutzeravatar
pillmuncher
User
Beiträge: 1530
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

Mir ist nicht klar,was du am Ende erreichen willst. Da es um ein Textverarbeitunsprogramm geht: Willst du die konvexen Hüllen der einzelnen Zeilen bzw. Absätze als Ergebnis?
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
Felix92
User
Beiträge: 133
Registriert: Mittwoch 7. November 2018, 17:57

@pillmuncher
Das wäre zumindest ein guter Ansatz um "Textblöcke" zu clustern :)
Aber hier geht es eigentlich mehr darum die roten "Punkte" korrekt von links nach rechts und oben nach unten zu sortieren halt wie man einen Text liest (leichte Verschiebungen auf der y-Achse müssten halt mit abgefangen werden wie oben beschrieben "die Outlier") .. anhand deren Index könnte ich dann die Boxen sortieren .. um mit dem gruppieren in Linien und Blöcke weiter zu machen :)
Vielen Dank für deine Hilfe ;)
Benutzeravatar
Felix92
User
Beiträge: 133
Registriert: Mittwoch 7. November 2018, 17:57

Ich kann halt wirklich nur mit den Koordinaten der Boxen bzw. Berechnungen auf/von diesen Arbeiten ... ich hatte auch schon überlegt eine bitmap der Boxen zu erstellen um darauf mit erode irgendwie eine sinnvolle Maske zu erstellen .. allerdings wird das nicht funktionieren, da die Punkte zu sehr beieinander liegen können .. deshalb bin ich auf der Suche nach etwas, was die Punkte akkurat (inkl. der kleinen Abweichungen auf der y-Achse) sortiert damit wäre mein Problem gelöst (wenn so einfach) ^^
__deets__
User
Beiträge: 14545
Registriert: Mittwoch 14. Oktober 2015, 14:29

Kannst du wirklich nicht auf den Pixeldaten arbeiten? Ein verwandtes Problem habe ich mal so gelöst: https://stackoverflow.com/questions/498 ... -three-col

Ansonsten würde ich mal Paper suchen und studieren - https://www.mathematik.uni-marburg.de/~ ... 04-OCR.pdf Zb, deren Referenzen, usw.
Benutzeravatar
Felix92
User
Beiträge: 133
Registriert: Mittwoch 7. November 2018, 17:57

@__deets__
1. eher nicht und selbst wenn würde es da vermutlich Probleme geben, da die "Dokumente" alles mögliche sein können Handyfotos mit Hintergrund, Flyer, Poster, irgendetwas fotografiertes (die Erkennung funktioniert super mit https://arxiv.org/abs/1911.08947 nur die Sortierung halt nicht ^^) und

Code: Alles auswählen

cv2.getStructuringElement
ist auch ziemlich rechenintensiv/zeitintensiv
2. danke schaue ich mir mal an :)
Benutzeravatar
Felix92
User
Beiträge: 133
Registriert: Mittwoch 7. November 2018, 17:57

Ich habe gerade mal geschaut wo ich noch ran komme ist an die Konturen der bitmap sieht aufjedenfall vielversprechender aus:
Bild
Bild
Benutzeravatar
pillmuncher
User
Beiträge: 1530
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

Felix92 hat geschrieben: Mittwoch 6. Oktober 2021, 21:02 @pillmuncher
... geht es eigentlich mehr darum die roten "Punkte" korrekt von links nach rechts und oben nach unten zu sortieren halt wie man einen Text liest (leichte Verschiebungen auf der y-Achse müssten halt mit abgefangen werden wie oben beschrieben "die Outlier") .. anhand deren Index könnte ich dann die Boxen sortieren ...
Warum nicht umgekehrt? Also erst die Zeilen und Absätze aus den Bounding Boxen der Worte erzeugen und anschließend die Mittelpunkte drüberlegen. Wobei mir immer noch nicht klar ist, was du mit den Punkten am Ende anfangen willst.

A: "Wie muss ich die Pedale und das Lenkrad bedienen, um mit dem Auto nach sag-ich-nicht zu fahren?"
B: "Du willst also eine Wegbeschreibung, sagst aber nicht, wo du hin willst?"
A: "Nein, ich will nur wissen, wie ich die Pedale und das Lenkrad bedienen muss, um nach sag-ich-nicht zu kommen. Die Wegbeschreibung brauch ich dann ja nicht mehr, weil ich an jedem Punkt der Fahrt weiß, in welchem Winkel ich das Lenkrad halten muss und wie tief ich jedes Pedal drücken muss."
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
pillmuncher
User
Beiträge: 1530
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

@Felix92: Schau mal, ob dir diese Bibliothek weiterhilft, die ich vor ein paar Jahren mal gebaut habe: https://github.com/pillmuncher/pyraxial
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
Felix92
User
Beiträge: 133
Registriert: Mittwoch 7. November 2018, 17:57

@pillmuncher
du hast Recht ich war (passend zu deiner Probleminterpretation) etwas "festgefahren" auf den centroids ^^
Die Blöcke habe ich jetzt:
Bild
Über die Linien muss ich mir jetzt nochmal Gedanken machen, falls du einen Vorschlag hast immer gerne gesehen :D

Und natürlich vielen Dank :)
Benutzeravatar
pillmuncher
User
Beiträge: 1530
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

@Felix92: Nachdem ich dein letztes Bild gesehen habe, habe ich, glaube ich, besser verstanden was du möchtest: Bounding Boxen, die sich womöglich nicht direkt überschneiden, aber auf derselben gedachten Linie liegen, sollen in der richtigen Reihenfolge - von links nach rechts - zur selben Zeile hinzugefügt werden.

Jede Bounding Box hat ein ymin und ein ymax. Angenommen, die Boxen b1 und b2 überschneiden sich nicht direkt, gehören aber zur selben Zeile, dann kann man einfach die x-Dimension außer acht lassen und testen:

Code: Alles auswählen

if max(b1.ymin, b2.ymin) <= min(b1.ymax, b2.xmax):
    ... # selbe Zeile
else:
    ... # andere Zeile
Ggf. muss man noch ein paar Pixel draufrechnen oder abziehen, denn es kann sein dass die Zeilen "schief" eingescannt wurden, sodass die y-Bereiche von zu einer Zeile gehörenden Worten sich nicht überschneiden oder umgekehrt, dass sich die y-Bereiche von Worten überschneiden, die zu verschiedenen Zeilen gehören. Man könnte auch einfach pro Zeile die konvexe Hülle der bisher als zur Zeile gehörend identifizierten Worte mitführen und jede neue Box mit dieser vergleichen. Das schöne daran ist, dass diese Hülle ja auch nur wieder eine Bounding Box ist. Mit meiner Bibliothek ist das super einfach zu bewerkstelligen, was daran liegen könnte, dass ich sie genau für diesen Zweck damals gebaut habe, eingescannte Worte zu Zeilen und Absätzen in der richtigen Reihenfolge zusammenzusammeln.
In specifications, Murphy's Law supersedes Ohm's.
__deets__
User
Beiträge: 14545
Registriert: Mittwoch 14. Oktober 2015, 14:29

Das Paper, das ich oben zitiert habe, versucht sowas mit einem leicht modifizierten DFS. Auch und gerade mit unterschiedlichen Hintergruenden.
Benutzeravatar
Felix92
User
Beiträge: 133
Registriert: Mittwoch 7. November 2018, 17:57

@__deets__ ich werde mir das Paper heute abend mal genauer zu Gemüt führen danke :)
@pillmuncher super das schaue ich mir morgen mal genauer an hast du da mit deiner Lib vlt. ein kleines Beispiel parat um in Blöcke und Linien zu gruppieren ?
Als Hintergrund: Ziel des Ganzen ist es die https://github.com/mindee/doctr Lib zu supporten (open source), wenn dort dein Code hilfreich ist verlinke ich das auch sehr gerne :)
Mein Support besteht eher darin einen HOCR-Parser hinzuzufügen um PDF-Dateien mit Textlayer zu erzeugen (um die XML-Datei erzeugen zu können müssen die Koordinaten + Ergebnisse korrekt sein in Reihenfolge) sowie danach ein optimiertes Model zur Texterkennung und um Tabellen aus Dokumenten zu extrahieren.
Hier noch der Link zum Issue: https://github.com/mindee/doctr/issues/512
Ich füge mal noch Testcode hinzu falls du Bock und Zeit hast gerne ein Beispiel mit deiner Lib (PS: das sind alles nur Tests :geek: )
Vielen Dank für deine Hilfe :)
Testcode:

Code: Alles auswählen

import math
import itertools
from scipy.spatial import distance as dist
import cv2
import numpy as np
from PIL import Image
import copy

import quads

from doctr.models import ocr_predictor
from doctr.io import DocumentFile

image = cv2.imread('/home/felix/Desktop/Data/OCR_Data/1.jpg')
img = DocumentFile.from_images('/home/felix/Desktop/Data/OCR_Data/1.jpg')
model = ocr_predictor(det_arch='db_mobilenet_v3_large', reco_arch='crnn_vgg16_bn', pretrained=True)

result = model(img)
#print(result)
#result.show(img)
print(result.render())



#Generate two text boxes a larger one that covers them
def merge_boxes(box1, box2):
    return [min(box1[0], box2[0]),
         min(box1[1], box2[1]),
         max(box1[2], box2[2]),
         max(box1[3], box2[3])]







points = list()
box_centres = list()
max_coords = list()
left_upper_corners = list()
right_upper_corners = list()
normalized_boxes = list()
test_boxes = list()
center_points = list()
boxes = list()
h = None
w = None
for page in result.pages:
    h, w = page.dimensions
    for block in page.blocks:
        for line in block.lines:
            for word in line.words:
                points.append(word.geometry)
                xmin, ymin, xmax, ymax = [tupl for tuploftupls in word.geometry for tupl in tuploftupls]
                xmin = int(xmin * w)
                ymin = int(ymin * h)
                xmax = int(xmax * w)
                ymax = int(ymax * h)
                boxes.append((ymin, ymax, xmin, xmax))
                y_box_heigth = ymax - ymin
                x_box_width = xmax - xmin

                x_y_width_height = [xmin, ymin, xmax-xmin+1, ymax-ymin+1]
                normalized_boxes.append(x_y_width_height)

            #    cv2.rectangle(image, (xmin, ymin), (xmax, ymax), (0, 255, 0), 2)
            #    print(xmin, ymin, xmax, ymax)
            #    print(word)
                x, y = (xmin + xmax) // 2, (ymin + ymax) // 2
                center_points.append((x, y))
                test_boxes.append([[xmin,ymin], [xmax, ymax]])
                # Draw a circle in the center of rectangle
            #    cv2.circle(img=image, center=(x, y), radius=3, color=(255, 0, 0), thickness=3)
                left_upper_corner = (xmin, ymin)
                right_upper_corner = (xmax, ymin)
            #    cv2.circle(image, center=left_upper_corner, radius=3, color=(0, 0, 255), thickness=3)
            #    cv2.circle(image, center=right_upper_corner, radius=3, color=(0, 0, 0), thickness=4)
            #    print(word)

            #    print(f"center: ({x}, {y})")
                left_upper_corners.append(left_upper_corner)
                right_upper_corners.append(right_upper_corner)
                max_coords.append((xmax, ymax))
                box_centres.append((x, y))

print(h)
print(w)
#print(normalized_boxes)
#print(boxes)
#print(center_points)
#print(result.render())
#zipped_list = zip(center_points, boxes)
#sorted_boxes = sorted(zipped_list, key=min([x[1] for x in zipped_list]))
#print(sorted_boxes)
#boxes = [x[1] for x in sorted_boxes]

img = 255 * np.ones((h,w,3), np.uint8)

x, y = w // 2, h // 2 # center of image

boxes = sorted(boxes , key=lambda k: (k[1] * w, k[0]))
i = 0
for ymin, ymax, xmin, xmax in boxes:
    i += 1
    if i == 80:
        break
    cv2.rectangle(image, (xmin, ymin), (xmax, ymax), (0, 255, 0), 2)

cv2.imwrite('x.jpg', image)

center_points = sorted(center_points , key=lambda k: (k[1], k[0]))

#center_points = sorted(center_points, key=lambda x: x[0] + x[1] * w)
i = 0
for center, left_upper, right_upper in zip(center_points, left_upper_corners, right_upper_corners):
    if i == len(center_points)-1:
        break
    cv2.circle(img, center=center, radius=3, color=(0, 0, 255), thickness=3)
#    cv2.circle(img, center=left_upper, radius=3, color=(0, 255, 0), thickness=3)
#    cv2.circle(img, center=right_upper, radius=3, color=(255, 0, 0), thickness=3)
    i += 1

cv2.imwrite('y.jpg', img)


def overlap(source, target):
    # unpack points
    tl1, br1 = source
    tl2, br2 = target

    # checks
    if (tl1[0] >= br2[0] or tl2[0] >= br1[0]):
        return False
    if (tl1[1] >= br2[1] or tl2[1] >= br1[1]):
        return False
    return True

# returns all overlapping boxes
def getAllOverlaps(boxes, bounds, index):
    overlaps = []
    for a in range(len(boxes)):
        if a != index:
            if overlap(bounds, boxes[a]):
                overlaps.append(a)
    return overlaps

def tup(point):
    return (point[0], point[1])

# go through the boxes and start merging
boxes = test_boxes
index_list = list()
merge_margin = 15

# this is gonna take a long time
finished = False
#highlight = [[0,0], [1,1]]
#points = [[[0,0]]]
while not finished:
    # set end con
    finished = True

    # check progress
    print("Len Boxes: " + str(len(boxes)))

    # loop through boxes
    index = 0
    while index < len(boxes)-1:
        # grab current box
        # TODO: rewrite this into function and track merged boxes by index -> also possible if we grow only left to right ?
        # TODO: possible to use also for lines -> grow only left to right : two modus -> "blocks" and "lines"
        # TODO: or compute distance from all boxes inside a block (permutations) and then sort them !??
        curr = boxes[index]

        # add margin
        tl, br = curr[0][:], curr[1][:]
        tl[0] -= merge_margin
        tl[1] -= merge_margin
        br[0] += merge_margin
        br[1] += merge_margin

        # get matching boxes
        overlaps = getAllOverlaps(boxes, [tl, br], index)
        print(overlaps) # TODO: <----- thats the single box indexes !!!!

        # check if empty
        if overlaps:
            # combine boxes
            # convert to a contour
            con = []
            overlaps.append(index)
            for ind in overlaps:

                tl, br = boxes[ind]
                con.append([tl])
                con.append([br])
            con = np.array(con)

            # get bounding rect
            x,y,w,h = cv2.boundingRect(con)

            # stop growing
            merged = [[x,y], [x+w-1, y+h-1]]

            # highlights
            #highlight = merged[:]
            #print(highlight)
            #points = con
            #print(points)

            # remove boxes from list
            overlaps.sort(reverse = True)
            print(overlaps)
            for ind in overlaps:
                del boxes[ind]
            boxes.append(merged)

            # set flag
            finished = False
            break

        index += 1

for box in boxes:
    cv2.rectangle(img, tup(box[0]), tup(box[1]), (0,200,0), 1)
print(boxes)

cv2.imwrite('z.jpg', img)

"""

def calculate_ratio_to_image(h, w, distance):
    return {'height_ratio': (distance * 100) / int(h), 'width_ratio': (distance * 100) / int(w) }


line_indexes = list()
temp_list = list()
for idx, corners in enumerate(left_right_upper_corners):
    if idx == len(left_right_upper_corners)-1:
        break

    cv2.line(image, left_right_upper_corners[idx][1], left_right_upper_corners[idx+1][0], (100, 100, 100), thickness=3, lineType=8)
    max_value_distance = math.sqrt(((left_right_upper_corners[idx][1][0] - left_right_upper_corners[idx+1][0][0]) ** 2) + ((left_right_upper_corners[idx][1][1] - left_right_upper_corners[idx+1][0][1]) ** 2))
#    print(max_value_distance)
    ratio_to_image = calculate_ratio_to_image(h, w, max_value_distance)
#    if ratio_to_image < 12 and idx not in temp_list and idx+1 not in temp_list:
#        temp_list.append(idx)
#        temp_list.append(idx+1)
#    else:

cv2.imwrite('x.jpg', image)
"""


"""
def compute_box_distances(box_points):
    combined_elements = list()
    for idx, box_point in enumerate(box_points):
        if idx == len(box_points)-1:
            break
        max_value_distance = math.sqrt(((int(box_points[idx][0])-int(box_points[idx+1][0]))**2)+((int(box_points[idx][1])-int(box_points[idx+1][1]))**2))
        ratio_to_image = calculate_ratio_to_image(h, w, max_value_distance)
    return None


lines = list()
for idx, max_coord in enumerate(max_coords):
    if idx == len(max_coords)-1:
        break
    max_value_distance = math.sqrt(((int(max_coords[idx][0])-int(max_coords[idx+1][0]))**2)+((int(max_coords[idx][1])-int(max_coords[idx+1][1]))**2))
    ratio_to_image = calculate_ratio_to_image(h, w, max_value_distance)
#    print(max_value_distance)
#    print(ratio_to_image)

blocks = list()
for idx, center in enumerate(box_centres):
    if idx == len(box_centres)-1:
        break
    midpoint_distance = math.sqrt(((int(box_centres[idx][0])-int(box_centres[idx+1][0]))**2)+((int(box_centres[idx][1])-int(box_centres[idx+1][1]))**2))
    ratio_to_image = calculate_ratio_to_image(h, w, midpoint_distance)
#    print(midpoint_distance)
#    print(ratio_to_image)


#print('UP')
#print(box_centres)
#print(len(box_centres))
#permutations = calculate_perm(box_centres)
#print(len(permutations))

#D = dist.euclidean((xA, yA), (xB, yB)) / refObj[2]
#(mX, mY) = midpoint((xA, yA), (xB, yB))

#for perm in permutations:
#   dist = calculate_centr_distances(perm[0], perm[1])
    #print(dist)


#print(points[0])
cv2.imwrite('x.jpg', image)


def organize_elements(result):
    pass




"""
Benutzeravatar
Felix92
User
Beiträge: 133
Registriert: Mittwoch 7. November 2018, 17:57

PS: dort kann wirklich alles reinkommen also auch unterschiedliche Ausrichtungen der Dokumente / Bilder / Flyer oder was auch immer
Ansonsten falls du diesen Part übernehmen wollen würdest als Support mit deiner Lib natürlich auch sehr gerne dann würde ich das HOCR-Zeug hinterher schieben sag mir Bescheid wie du magst :)
Benutzeravatar
pillmuncher
User
Beiträge: 1530
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

@__deets__: Deutsche Flug-Sicherung? ;)

Ich würde auch nicht jede Bounding Box mit jeder anderen vergeichen, sondern zB. ein auf einem Intervall-Baum basierenden Line Sweep Verfahren anwenden. Etwa so:

Code: Alles auswählen

class Box(typing.NamedTuple):
    xmin: int
    ymin: int
    xmax: int
    ymax: int

def collect_words_in_lines(boxes):
    events = sorted(chain.from_iterable(((box.ymin, False, box), (box.ymax, True, box)) for box in boxes))
    status = IntervalTree()
    line = set()
    for _, is_ymax, box in events:
        line.add(box)
        line.update(status.overlap(box.ymin, box.ymax))
        if is_ymax:
            status.discard(box.ymin, box.ymax, box)
            if status.is_empty():
                yield sorted(line)
                line = set()
        else:
            status.add(box.ymin, box.ymax, box)
Mit dem IntervalTree, den ich verwendet habe, ist dieser Code nicht lauffähig. Deswegen sollte er als Pseudo-Code verstanden werden, der nur dazu dient, das Prinzip zu veranschaulichen.
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
Felix92
User
Beiträge: 133
Registriert: Mittwoch 7. November 2018, 17:57

@pillmuncher
Hast du https://pypi.org/project/intervaltree/ verwendet ? :) ich schaue mir das morgen mal genauer an danke erstmal :)
Ein kleines Beispiel mit deiner Lib wäre trotzdem cool einfach um es schneller testen zu können :wink:
Benutzeravatar
pillmuncher
User
Beiträge: 1530
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

@Felix92: Beispiele sind im doctext und auch in der API-Doc: https://pillmuncher.github.io/pyraxial/pyraxial.html
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
pillmuncher
User
Beiträge: 1530
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

@Felix92: Die neue API-Doc-Adresse ist: https://pillmuncher.github.io/pyraxial
In specifications, Murphy's Law supersedes Ohm's.
Antworten