Los quadtrees son un método eficaz para almacenar y localizar datos de puntos en un plano bidimensional. Otro uso efectivo de quadtrees es en el campo de la manipulación de imágenes.
A diferencia del almacenamiento de puntos, en la manipulación de imágenes obtenemos un quadtree completo con los Nodes hoja que consisten en píxeles individuales de la imagen. Debido a esto, podemos utilizar una array para almacenar los Nodes del árbol. Esto lleva a que se necesite menos memoria (en comparación con la representación vinculada) para el procesamiento.
El nivel más bajo del quadtree contendría N Nodes equivalentes al número de píxeles de la imagen. El siguiente nivel contendría N/4 Nodes.
Por lo tanto, el número total de Nodes necesarios se puede encontrar mediante: N + N / 4 + N / 16 + … + 1.
Para obtener un límite superior podemos usar la suma de la progresión geométrica hasta el infinito
Nodes = N / (1 – 1 / 4 ) = 4 / 3 * N
Este es el tamaño de la array necesaria.
Por lo tanto, la cantidad de memoria necesaria es O(N)
class Point(object): def __init__(self, x, y): self.x = x self.y = y class Pixel(object): def __init__(self, color = [0, 0, 0], topLeft = Point(0, 0), bottomRight = Point(0, 0)): self.R = color[0] self.G = color[1] self.B = color[2] self.topLeft = topLeft self.bottomRight = bottomRight
El código anterior en Python que se muestra demuestra la definición de clase de un píxel.
Inserción
A diferencia de un quadtree clásico, para la manipulación de imágenes, podemos insertar todos los Nodes en complejidad de tiempo O(N).
Primero, insertamos todos los Nodes hoja directamente en las últimas N posiciones de la array. El siguiente fragmento de código demuestra esto:
# Store leaves into array count = 0 for i in range(image.size[0] - 1, 0, -2): for j in range(image.size[1] - 1, 0, -2): self.tree[self.size - 1 - 4 * count] = Pixel(self.image[i, j], Point(i, j), Point(i, j)) self.tree[self.size - 2 - 4 * count] = Pixel(self.image[i, j - 1], Point(i, j - 1), Point(i, j - 1)) self.tree[self.size - 3 - 4 * count] = Pixel(self.image[i - 1, j], Point(i - 1, j), Point(i - 1, j)) self.tree[self.size - 4 - 4 * count] = Pixel(self.image[i - 1, j - 1], Point(i - 1, j - 1), Point(i - 1, j - 1)) count += 1
En el fragmento anterior, self.tree es la array de Nodes, self.size es el tamaño total de la array y self.image son los píxeles de la imagen, se usa count para recorrer el árbol.
Para los Nodes que no son hojas, los valores R, G, B se calculan tomando el promedio de los valores de los hijos.
topLeft y bottomRight se obtienen tomando los valores máximo y mínimo de x e y de los hijos.
# Calculate and create parent nodes for i in range(self.size - 4 * count - 1, -1, -1): self.tree[i] = Pixel( [(self.tree[4 * i + 1].R + self.tree[4 * i + 2].R + self.tree[4 * i + 3].R + self.tree[4 * i + 4].R) / 4, (self.tree[4 * i + 1].G + self.tree[4 * i + 2].G + self.tree[4 * i + 3].G + self.tree[4 * i + 4].G) / 4, (self.tree[4 * i + 1].B + self.tree[4 * i + 2].B + self.tree[4 * i + 3].B + self.tree[4 * i + 4].B) / 4], self.tree[4 * i + 1].topLeft, self.tree[4 * i + 4].bottomRight)
Aquí podemos ver, tomamos los valores de R, G, B de los cuatro niños y los dividimos por 4, obteniendo así el promedio.
El cálculo de estos valores ocurre en el tiempo O(1) asumiendo que se conocen los valores de los niños. Como nos estamos moviendo en orden inverso, los valores de los hijos se calculan antes que los de los padres.
Por lo tanto, la inserción se produce en O (N).
Aplicación en la manipulación de imágenes
Digamos que deseamos convertir una imagen de alta calidad en una miniatura . Una vez que hemos creado un quadtree para la imagen, seleccionando una altura del quadtree podemos seleccionar la calidad de la imagen que obtenemos. Si la altura es igual a la altura del quadtree, conservamos la imagen original. A menor altura obtenemos imágenes de menor calidad.
En caso de que no queramos reducir la calidad de la imagen, podemos intentar comprimir la imagen mediante lo que se conoce como “poda”. En este se eliminan las hojas con colores cercanos al de sus progenitores. Esto se hace continuamente hasta que no se puedan quitar más hojas. Luego se toma el nivel más bajo para formar la imagen, utilizando solo Nodes de hoja. Si bien esto no reduce drásticamente la calidad de la imagen, puede conducir a una pequeña compresión de la imagen.
Código completo:
from PIL import Image
import math
class Point(object):
def __init__(self, x, y):
self.x = x
self.y = y
class Pixel(object):
def __init__(self, color = [0, 0, 0],
topLeft = Point(0, 0),
bottomRight = Point(0, 0)):
self.R = color[0]
self.G = color[1]
self.B = color[2]
self.topLeft = topLeft
self.bottomRight = bottomRight
class quadtree():
def __init__(self, image):
# Total number of nodes of tree
self.size = 0
# Store image pixelmap
self.image = image.load()
# Array of nodes
self.tree = []
self.x = image.size[0]
self.y = image.size[1]
# Total number of leaf nodes
size = image.size[0] * image.size[1]
# Count number of nodes
while(size >= 1):
self.size += size
size /= 4
size = image.size[0] * image.size[1]
# Initialize array elements
for i in range(0, self.size):
self.tree.append(Pixel())
# Store leaves into array
count = 0
for i in range(image.size[0] - 1, 0, -2):
for j in range(image.size[1] - 1, 0, -2):
self.tree[self.size - 1 - 4 * count] = Pixel(self.image[i, j],
Point(i, j),
Point(i, j))
self.tree[self.size - 2 - 4 * count] = Pixel(self.image[i, j - 1],
Point(i, j - 1),
Point(i, j - 1))
self.tree[self.size - 3 - 4 * count] = Pixel(self.image[i - 1, j],
Point(i - 1, j),
Point(i - 1, j))
self.tree[self.size - 4 - 4 * count] = Pixel(self.image[i - 1, j - 1],
Point(i - 1, j - 1),
Point(i - 1, j - 1))
count += 1
# Calculate and create parent nodes
for i in range(self.size - 4 * count - 1, -1, -1):
self.tree[i] = Pixel(
[(self.tree[4 * i + 1].R + self.tree[4 * i + 2].R + self.tree[4 * i + 3].R + self.tree[4 * i + 4].R) / 4,
(self.tree[4 * i + 1].G + self.tree[4 * i + 2].G + self.tree[4 * i + 3].G + self.tree[4 * i + 4].G) / 4,
(self.tree[4 * i + 1].B + self.tree[4 * i + 2].B + self.tree[4 * i + 3].B + self.tree[4 * i + 4].B) / 4],
self.tree[4 * i + 1].topLeft,
self.tree[4 * i + 4].bottomRight)
def disp(self, level):
start = 0
# Calculate position of starting node of height
for i in range(0, level):
start = 4 * start + 1
# Invalid height given
if (start > self.size):
return
# Create a new image
img = Image.new("RGB", (self.x, self.y), "black")
pixels = img.load()
# Move from starting to last node on given height
for i in self.tree[start : 4 * start]:
x1 = i.topLeft.x
y1 = i.topLeft.y
x2 = i.bottomRight.x
y2 = i.bottomRight.y
for x in range(x1, x2 + 1):
for y in range(y1, y2 + 1):
# Set colour
pixels[x, y] = (i.R, i.G, i.B)
# Display image
img.show()
Este artículo es una contribución de Aditya Kamath . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA