Antwort mit KI erzeugt
Komprimierungsverfahren Quadtree
Ein Quadtree ist eine baumartige Datenstruktur, die dazu verwendet wird, zweidimensionale räumliche Daten effizient zu speichern und zu verwalten. Beim Komprimierungsverfahren Quadtree wird das Raster in vier gleich große Quadranten aufgeteilt. Jeder Quadrant kann wiederum weiter unterteilt werden, bis die Quadranten entweder homogen sind oder eine bestimmte Mindestgröße erreicht haben. Homogen bedeutet in diesem Kontext, dass alle Werte innerhalb des Quadranten gleich sind.
Schrittweise Erklärung zur Komprimierung des gegebenen Rasters:
Gegebenes Raster:
\(
\begin{array}{cccccccc}
2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 \\
2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 \\
2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 & 5 & 5 & 5 & 5 \\
2 & 2 & 2 & 2 & 5 & 5 & 5 & 5 \\
2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\
2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\
2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\
\end{array}
\)
Schritt 1: Erste Unterteilung
Wir teilen das Raster in vier Quadranten auf:
\(
\begin{array}{cccc|cccc}
2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 \\
2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 \\
2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 & 5 & 5 & 5 & 5 \\
\hline
2 & 2 & 2 & 2 & 5 & 5 & 5 & 5 \\
2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\
2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\
2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\
\end{array}
\)
Schritt 2: Überprüfung der Quadranten
1.
Quadrant 1 (links oben, 4x4):
\(
\begin{array}{cccc}
2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 \\
\end{array}
\)
Dieser Quadrant ist homogen (alle Elemente sind 2), daher wird er nicht weiter unterteilt.
2.
Quadrant 2 (rechts oben, 4x4):
\(
\begin{array}{cccc}
2 & 2 & 3 & 3 \\
2 & 2 & 3 & 3 \\
2 & 2 & 2 & 2 \\
5 & 5 & 5 & 5 \\
\end{array}
\)
Dieser Quadrant ist nicht homogen und muss weiter unterteilt werden.
3.
Quadrant 3 (links unten, 4x4):
\(
\begin{array}{cccc}
2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 \\
\end{array}
\)
Dieser Quadrant ist homogen (alle Elemente sind 2), daher wird er nicht weiter unterteilt.
4.
Quadrant 4 (rechts unten, 4x4):
\(
\begin{array}{cccc}
5 & 5 & 5 & 5 \\
4 & 4 & 5 & 5 \\
4 & 4 & 5 & 5 \\
4 & 4 & 5 & 5 \\
\end{array}
\)
Dieser Quadrant ist nicht homogen und muss weiter unterteilt werden.
Schritt 3: Weitere Unterteilung von Quadrant 2 und Quadrant 4
Quadrant 2 (weiter unterteilt):
\(
\begin{array}{cc|cc}
2 & 2 & 3 & 3 \\
2 & 2 & 3 & 3 \\
\hline
2 & 2 & 2 & 2 \\
5 & 5 & 5 & 5 \\
\end{array}
\)
Quadrant 4 (weiter unterteilt):
\(
\begin{array}{cc|cc}
5 & 5 & 5 & 5 \\
4 & 4 & 5 & 5 \\
\hline
4 & 4 & 5 & 5 \\
4 & 4 & 5 & 5 \\
\end{array}
\)
Beide Unterteilungen zeigen, dass wir zu tieferen Ebenen des Quadtrees gelangen müssen. Die weiteren kleinen Quadranten innerhalb von Quadrant 2 und Quadrant 4 werden für Homogenität überprüft und falls notwendig, weiter unterteilt, bis nur homogene Quadranten übrigbleiben.
Python-Code zur Illustration
Hier ist ein Beispiel, wie man dies in Python umsetzen könnte:
python
class QuadtreeNode:
def __init__(self, value=None):
self.value = value
self.children = None
def build_quadtree(grid, x, y, size):
first_value = grid[x][y]
homogeneous = True
for i in range(size):
for j in range(size):
if grid[x+i][y+j] != first_value:
homogeneous = False
break
if not homogeneous:
break
node = QuadtreeNode(first_value if homogeneous else None)
if not homogeneous:
half_size = size // 2
node.children = [
build_quadtree(grid, x, y, half_size),
build_quadtree(grid, x, y + half_size, half_size),
build_quadtree(grid, x + half_size, y, half_size),
build_quadtree(grid, x + half_size, y + half_size, half_size),
]
return node
def print_quadtree(node, indent=0):
if node.children is None:
print(" " * indent + str(node.value))
else:
for child in node.children:
print_quadtree(child, indent + 1)
# Gegebenes Raster
grid = [
[2, 2, 2, 2, 2, 2, 3, 3],
[2, 2, 2, 2, 2, 2, 3, 3],
[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 5, 5, 5, 5],
[2, 2, 2, 2, 5, 5, 5, 5],
[2, 2, 2, 2, 4, 4, 5, 5],
[2, 2, 2, 2, 4, 4, 5, 5],
[2, 2, 2, 2, 4, 4, 5, 5],
]
# Quadtree erstellen
quadtree = build_quadtree(grid, 0, 0, len(grid))
# Quadtree ausgeben
print_quadtree(quadtree)
Dieser Code zeigt, wie man das Raster in einen Quadtree umwandeln und diesen ausgeben kann. Dabei wird geprüft, ob ein Quadrant homogen ist (alle Felder haben denselben Wert) und gegebenenfalls in vier kleinere Quadranten unterteilt.
