Eine kleine Algebra für achsenparallele Rechtecke
Verfasst: Freitag 23. März 2012, 06:31
Vor einiger Zeit habe ich mit PIL gearbeitet. PIL repräsentiert achsenparallele Rechtecke mittels Tupeln:Öfters musste ich Bounding Boxen (kleinste umschließende Rechtecke) bilden:Das habe ich mir ungefähr 15 sec angeschaut und beschlossen, dass ich derlei Code nicht in meiner näheren Umgebung haben möchte. Statt dessen habe ich eine BoundingBox-Klasse gebaut. Die hat zwar funktioniert, hat mir aber nicht gefallen. Deswegen habe ich letzte Woche etwas darüber nachgedacht und festgestellt, dass ich a) keine Klasse brauche, sondern nur Funktionen auf Tupeln, und b), dass achsenparallele Rechtecke eine Algebra bilden, genauer gesagt einen nach unten beschränkten vollständigen Verband.
(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:Damit ist der Verband auch vollständig, d.h. für jedes Paar von Rechtecken a und b liefern sowohl boundingbox als auch overlap wieder ein Rechteck, und sei es das "leere" Rechteck ().
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:In beiden Fällen wird, sofern kein Rechteck übergeben wurde, () zurückgegeben. Das ist der Tatsache geschuldet, dass ja auch die leere Menge eine Teilmenge von V ist, und zur Verbands-Vollständigkeit gehört, dass jeder Teilmenge von V wieder ein Element von V zugeordnet werden kann. Für die leere Menge ist dies das Null-Element.
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:
Was bringt das nun für die Praxis? Eine Aufgabe in unserem Projekt war, über einer Menge von rechteckigen Bildausschnitten die Bounding Boxen von "zusammenhängenden Bereichen" zu finden. Das muss man sich so vorstellen, dass man aus einem Bild erst mittels floodfill o.ä. rechteckige Ausschnitte generiert und nun feststellen will, welche zusammenhängenden Teilbilder sich daraus ergeben. Man kann auch sagen: die Bounding Boxen über den Mengen sich transitiv überlappender Ausschnitte. Das läßt sich leicht rekursiv definieren: zwei Rechtecke a und b überlappen sich transitiv, wenn sie sich entweder direkt überlappen oder wenn es ein Rechteck c gibt, das beide transitiv überlappt.
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:Damit lässt sich definieren:Das Erzeugen der Paare ist leider O(n^2). Aber das liegt an der Aufgabe, man kann es AFAICS nicht reduzieren. Naja, vielleicht mittels eines R-Trees.
Alan 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.
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.