Code: Alles auswählen
rect = (left, top, right, bottom)
image_section = some_image.crop(rect)Code: Alles auswählen
r1 = (100, 200, 300, 400)
r2 = (200, 300, 400, 500)
bb = (min(r1[0], r2[0]), min(r1[1], r2[1]), max(r1[2], r2[2]), max(r1[3], r2[3]))
assert bb == (100, 200, 400, 500)(Im Weiteren meine ich achsenparallele Rechtecke, wenn ich von Rechtecken schreibe)
Ein Verband ist eine Struktur, die aus einer Menge von Elementen V und zwei binären Operationen join und meet besteht, die bestimmten Gesetzen gehorchen. In meinem Fall war V die Menge der Rechtecke, join bekam den Namen boundingbox und meet den Namen overlap. boundingbox(a, b) bildet das kleinste Rechteck, das die Rechtecke a und b einschließt. overlap(a, b) liefert das größte Rechteck, das gemeinsam von a und b eingeschlossen wird, also den Bereich, in dem sich a und b überlappen. Das ist notwendigerweise ebenfalls ein Rechteck.
Übrigens kennt man join und meet meist unter den Namen, die sie in der elementaren Mengenlehre haben: Vereiningungsmenge und Schnittmenge. Bezogen auf Rechtecke kann man sich damit anschaulich machen, um was es mir geht: boundingbox(a, b) liefert den Bereich, der a und b vereinigt, und overlap(a, b) liefert den Bereich, in dem sich a und b schneiden.
Der Rechtecks-Verband ist nach unten beschränkt, weil er ein kleinstes Element besitzt. Das ist allerdings nicht das Rechteck mit der kleinsten Fläche, denn Rechtecke mit negativer Fläche gibt es nicht und solche mit der Fläche 0 gibt es unendlich viele, die alle nicht miteinander identisch sind, zB. (1, 1, 1, 1), (2, 2, 2, 2), ... . Was ich mit kleinstes Element meine ist das Null-Element des Verbandes. Ich verwende dafür das leere Tupel, (). Dieses besondere Rechteck besagt: "Ich habe gar keine Fläche". Etwa in dem Fall overlap(a, b), wenn a und b sich nicht überlappen:
Code: Alles auswählen
a = (1, 2, 3, 4)
b = (5, 6, 7, 8)
assert overlap(a, b) == ()In einem vollständigen Verband V lassen sich join und meet zu Operationen auf beliebigen Teilmengen von V verallgemeinern. In Python lässt sich das am einfachsten durch variadische Funktionen ausdrücken:
Code: Alles auswählen
def boundingbox(*rects):
...
def overlap(*rects):
...Für eine ordentliche Algebra gehört es sich, dass sie bestimmte Eigenschaften hat und bestimmte Gesetze erfüllt sind. Diese sind, für beliebige Rechtecke a, b und c:
Code: Alles auswählen
Null-Element: boundingbox(a, ()) == a
overlap(a, ()) == ()
Idempotenz: boundingbox(a, a) == a
overlap(a, a) == a
Kommutativität: boundingbox(a, b) == boundingbox(b, a)
overlap(a, b) == overlap(b, a)
Assoziativität: boundingbox(boundingbox(a, b), c) == boundingbox(a, boundingbox(b, c))
overlap(overlap(a, b), c) == overlap(a, overlap(b, c))
Absorption: boundingbox(a, overlap(a, b)) == a
overlap(a, boundingbox(a, b)) == a
Der Witz ist nun, dass dieses Problem äquivalent zum Problem der Suche nach verbundenen Komponenten in einem Graphen ist. Eine sich transitiv überlappende Menge von Rechtecken lässt sich betrachten als verbundene Komponente: Eine verbundene Komponente ist jede Menge aller miteinander über Pfade verbundenen Knoten in einem Graphen. In einem Graphen kann also es mehrere verbundene Komponenten geben, und diese Komponenten sind disjunkt. Übertragen auf unser obiges Problem: zwei Knoten (Rechtecke) a und b besitzen eine Kante, wenn sie sich direkt überlappen, und einen Pfad, wenn sie sich transitiv überlappen, und jede Menge aller sich transitiv überlappender Rechtecke bildet ein Teilbild.
Es gibt bekannte Algorithmen zur Suche nach verbunden Komponenten. Hier ist einer:
Code: Alles auswählen
from collections import defaultdict
def connected_components(edges):
"""
Given a graph represented by edges (i.e. pairs of nodes), generate its
connected components as sets of nodes.
Time complexity is linear with respect to the number of edges.
"""
neighbors = defaultdict(set)
for a, b in edges:
neighbors[a].add(b)
neighbors[b].add(a)
seen = set()
def component(node, neighbors=neighbors, seen=seen, see=seen.add):
unseen = set([node])
next_unseen = unseen.pop
while unseen:
node = next_unseen()
see(node)
unseen |= neighbors[node] - seen
yield node
return (set(component(node)) for node in neighbors if node not in seen)Code: Alles auswählen
from itertools import combinations
from graph import connected_components
def disjoint_areas(rects):
nodes = set(rects)
nodes.discard(()) # null has no area
edges = (pair for pair in combinations(nodes, 2) if overlap(*pair))
for component in connected_components(edges):
nodes -= component
yield boundingbox(*component)
for rect in nodes:
yield rectAlan Kay sagt es immer wieder: A change in perspective is worth 80 IQ points. Hier haben wir zweimal die Perspektive gewechselt, erst indem wir von einer geometrischen zu einer algebraischen Sichtweise übergegangen sind, und dann, indem wir überlappende Rechtecke als Kanten in einem Graphen angesehen haben.
Hier ist der geradezu lächerlich kurze Code und hier das Tutorial.
