Intentando entender el concepto de Quadtree y aplicarlo al almacenamiento de la información para colorear de una imagen

Question

He leído tantos artículos, pero ninguno parece responder a esta pregunta. O tal vez simplemente no estoy entendiendo. Estoy intentando construir un quadtree para que pueda representar una imagen. Los nodos de hoja deben contener píxeles y los nodos de hoja tendrán el valor medio de píxeles de sus elementos secundarios.

Mi pregunta es:

¿Cómo funciona que los nodos hoja sólo tienen píxeles? ¿Por qué los otros nodos tienen píxeles? ¿Y cómo sabemos cuántas veces subdividimos nuestro nodo raíz original para representar esa imagen dada? ¿Acabamos de subdividirlo n veces, donde n es la altura y el ancho (para un cuadrado)?

Editar: Entonces, ¿cómo puedo realizar un seguimiento de los nodos hoja, así que sé cuándo añadir píxeles en ese lugar? En este momento tengo una función auxiliar que divide las regiones para mí, manteniendo un registro de ancho y alto.

Answer 1

Los cuatricromos funcionan mejor para imágenes cuadradas cuyo tamaño es una potencia de 2 (por ejemplo, la mayoría de las texturas). No debe pensar en cada nodo como representando un "pixel". En cambio, piense que representa un "bloque cuadrado de píxeles de tamaño 2^k". En el caso de hojas finales, k es 0, por lo que cada nodo de hoja representa un bloque cuadrado de píxeles de tamaño 1, es decir, un único píxel. Los nodos internos en el árbol representan secciones de imagen cada vez más grandes.

Answer 2

¿cómo funciona que los nodos hoja solo tienen píxeles? ¿Por qué los otros nodos no tienen píxeles?

Esto depende de para qué esté usando el Quadtree. Puede vincular cualquier tipo de información a los otros nodos, es decir, un puntero a la esquina superior izquierda y el ancho/alto del rectángulo que describe este nodo, pero no lo necesitará en la mayoría de los casos (o necesita elementos como los valores promedio que puede precalcular para acelerar).

Y cómo sabemos cuántas veces a subdividen nuestra nodo raíz original para representar que da imagen?

Con cada subdivisión, que la mitad de la anchura y la altura de una región, por lo que para una imagen cuadrada de tamaño n que necesita para subdividir log2(n) veces, para obtener una imagen no cuadrada de tamaño n*m que necesita como máximo max(log2(n), log2(m)) pasos.

Answer 3

¿Por qué solo los nodos hoja tienen píxeles? Pregúntate si un nodo que no sea hoja tiene un píxel, entonces, ¿qué tendrían sus hijos? Como no se puede subdividir un píxel, la respuesta obviamente no es nada; no puede haber tales nodos.

¿Cómo sabemos cuántas veces para subdividir? Bueno, hay múltiples formas de hacerlo, por supuesto, dependiendo de por qué estás construyendo el quadtree. En general, las áreas de la imagen con más entropía - más "detalle" - deben subdividirse más, mientras que las áreas de menor entropía y "más planas" se pueden dividir menos. Hay varios algoritmos diferentes para elegir cuándo y dónde subdividir. En general, comparan valores de píxeles dentro de una región y se dividen cuando las diferencias están por encima de algún umbral.

Answer 4

Creo que la mejor manera de responder a su pregunta es responder dos preguntas que no haya formulado.

• ¿Qué es un quadtree?
• ¿Cómo puede ser esto aplicado a sistemas de modelado de densidad errática?

Un quadtree es un árbol binario en dos dimensiones. Es por eso que hay (hasta) cuatro niños por cada nodo no hoja. Esto le permite aplicar un índice a un plano de la misma manera que una base de datos usa un árbol binario o alguna variación del mismo para indexar una única dimensión, con las mismas propiedades de representación de espacio de fase dispersas altamente ventajosas.

La aplicación de esta a la compresión de imágenes y visualización progresiva es bastante obvio: si lo hace un árbol-paseo limitado a una profundidad de n, entonces obtendrá 4^n elementos de información de fichero que abarca todo el espacio de la imagen. Si tienes un nivel más profundo, cada píxel se divide en cuatro. JPEG2000 funciona así, si no recuerdo mal. Dije "elementos de información de imagen" porque no necesitan ser de un solo bit; los artículos podrían ser ARGB de 32 bits o cualquier otra propiedad (o propiedades) que describa el espacio en ese punto.