GEOMETRÍA - FRACTALES

círculo de Ford es un círculo centrado en  y con radio , donde  es una fracción irreducible, es decir, p y q son números enteros primos entre sí.- ....................................:http://es.wikipedia.org/w/index.php?title=Especial:Libro&bookcmd=download&collection_id=3a702753d12d54e1b6e9e6c0903bcc45fa0e01ac&writer=rdf2latex&return_to=C%C3%ADrculo+de+Ford

Círculos de Ford

18FEB20131 comentario

de matesmates en Geometría, Números 

En matemáticas, un círculo de Ford es un círculo centrado en     y  con radio   , donde    es una fracción irreducible, es decir, p y q son números enteros primos entre sí. El círculo de Ford asociado a la fracción p/q se denota como C[p/q] ¿Qué tienen estos círculos de particular? Si los representamos nos daremos cuenta de ello:

Efectivamente: dos círculos de Ford son, o bien disjuntos o bien tangentes entre sí. Curioso, ¿no?

Los círculos de Ford reciben el nombre del matemático estadounidense Lester R. Ford, quien los describió en un artículo en American Mathematical Monthlyen 1938. Algunas propiedades de estos círculos son:

• Si 0<p/q<1 a="" c="" de="" entonces="" ford="" i="" los="" que="" rculos="" son="" style="font-family: Baskerville, 'Times New Roman', Times, serif; font-size: 1.2em; font-stretch: normal; letter-spacing: 0.02em; line-height: normal; margin: 0px; padding: 0px;" tangentes="">p/q

] son precisamente los círculos de Ford de las fracciones que son vecinas de p/q en alguna sucesión de Farey. Por ejemplo, C[2/5] es tangente a C[1/2], C[1/3], C[3/7], C[3/8].

Existe una relación entre el área total de los círculos de Ford y la función zeta de Riemann:

Los círculos de Ford pueden servir para crear arte y si no véanse los resultados del artista Jos Leys.

   

 compresión fractal es un método de compresión con pérdida para imágenes digitales, basado en fractales. El método es el más apropiado para texturas e imágenes naturales, basándose en el hecho de que partes de una imagen, a menudo, se parecen a otras partes de la misma imagen. Los algoritmos fractales convierten estas partes en datos matemáticos llamados «códigos fractales» los cuales se usan para recrear la imagen codificada.- ....................................................:http://es.wikipedia.org/w/index.php?title=Especial:Libro&bookcmd=download&collection_id=8a4873e2f68698f581bf41a8001efb15233d22da&writer=rdf2latex&return_to=Compresi%C3%B3n+fractal

 INTRODUCCIÓN

Actualmente, la mayoría de los codificadores fractales de imagen que se han implementado se basan en el método de Jacquin, al cual se han añadido técnicas o métodos que permiten mejorar sus características de desempeño.

La codificación fractal de una imagen I en escala de grises mediante el método de Jacquin (Jacquin, 1992), separa la imagen en N_R×N_R bloques rangos r_i,j de n×n píxeles, como se indica en la ecuación (1).

(1)

Cada uno de los bloques rangos es aproximado por un bloque dominio d_k,l, el cual es obtenido de la misma imagen I mediante una transformación contractiva w_u:

(2)

donde (x, y) son puntos en un bloque dominio y (x’, y’) pertenecen a un bloque dominio transformado. El valor de z es la luminancia del píxel en el punto (x, y) en el bloque dominio, mientras z’ es la correspondiente al punto (x’, y’) del bloque dominio transformado. Cada bloque dominio tiene 2n×2n píxeles los cuales se traslapan por la mitad.

Para cada uno de los bloques rangos se selecciona el bloque dominio transformado que mejor se le asemeje. El parámetro s_ucontrola el contraste, mientras el parámetro o_u se usa para ajustar el brillo. El índice h escoge el conjunto de parámetros a_u, b_u, c_u y d_u, los cuales seleccionan conjuntamente a una de 8 transformaciones isométricas. Los parámetros e_u y f_u, desplazan al bloque dominio hasta la posición del bloque rango que asemeja.

Debido al gran número de operaciones involucradas en la búsqueda de similitud entre bloques rangos y dominios y a que cada uno de los parámetros que intervienen en la ecuación (2) debe ser calculado en cada comparación entre bloques, el método de Jacquin tiene un tiempo de codificación inconvenientemente grande. Para reducir ese número de operaciones se han utilizado adicionalmente técnicas como: reducción del conjunto de bloques dominios, restricción del valor del parámetro de ajuste de contraste (Lu, 1997), codificación en niveles inferiores de resolución (Gharavi et al., 1997), codificación en árbol cuádruple a través de niveles múltiples de resolución (Lin y Venetsanopoulos, 1996; Rinaldo y Calvagno, 1995), y clasificación de bloques rangos (Fisher, 1995; Lee y Ra, 1998), entre otros. A pesar de las ventajas aportadas por estos métodos, algunos de ellos no se han implementado como circuitos electrónicos debido a su complejidad; y los que se han implementado resultan en circuitos que obtienen baja razón de compresión; o en circuitos con un gran número de elementos de procesamiento.

En este trabajo se presenta una arquitectura simple y rápida para compresión fractal de imágenes, basada en un método que utiliza particionamiento en árbol cuádruple, un esquema de clasificación de bloques de acuerdo a su tamaño y contraste, y codificación fractal predictiva multiresolución (Martínez et al., 2004). La arquitectura aprovecha las características del método de compresión para obtener una implementación sencilla y modular.

MÉTODO DE CODIFICACIÓN

El método de codificación fractal implementado en este trabajo combina diferentes técnicas, con modificaciones a las mismas, para lograr una arquitectura simple y rápida, adecuada para su realización física en circuito integrado.

Reducción del conjunto de bloques dominio: Para reducir el número de comparaciones realizadas al codificar cada bloque rango de p×p píxeles, la búsqueda de similitud es limitada a una ventana con (2L+1)×(2L+1) bloques dominio, centrada en la misma posición que el bloque rango a codificar, teniendo 0£L<(N_R/2). De esta forma, el número de comparaciones por cada bloque rango es de 8(2L+1)². El número de comparaciones entre píxeles, necesarias para codificar la imagen I, es8(2L+1)²p². Aún cuando la calidad de la imagen se reduce, es suficiente para valores L ³ 3.

Codificación en resolución menor: Los bloques que tienen contraste bajo se aproximan bien en los niveles de resolución inferior, lo cual permite codificarlos rápidamente debido a que se tienen bloques con menor número de píxeles, y no es necesario recalcular los parámetros fractales de esos bloques (Martínez et al., 2003). Este aspecto será de gran importancia al presentar la arquitectura propuesta.

Aplicación a niveles múltiples de resolución: La partición en árbol cuádruple es utilizada para aumentar la razón de compresión (Fisher, 1995). Sin embargo, a diferencia del método tradicional (donde los bloques grandes de la partición en árbol cuádruple tienen un gran número de píxeles), el método aquí utilizado realiza la codificación de los bloques con bajo contraste en niveles inferiores de resolución (en donde el número de píxeles es menor). Además, la partición en árbol cuádruple es aplicada a través de los diferentes niveles de resolución de una pirámide de imágenes obtenidas a partir de la decimación de la imagen original I. Este procedimiento se ilustra en la figura 1 usando tres niveles de resolución de imagen.

Considérese una imagen I, con P×P píxeles de resolución, y sus decimaciones Is₁ e Is₂ con resoluciones de (P/2)×(P/2) y(P/4)×(P/4) píxeles respectivamente. La imagen Is₁ es obtenida sub-muestreando en 2 a los renglones y a las columnas de la imagen I, mientras la imagen Is₂ se obtiene sub-muestreando en 2 a los renglones y las columnas de Is₁.

Para formar los bloques rangos en la imagen original I, se aplica sobre ella una partición en árbol cuádruple de tres niveles, teniendo el primer nivel bloques con 4n×4n píxeles, el segundo nivel bloques con 2n×2n píxeles y el tercer nivel bloques conn×n píxeles.

Los bloques del particionamiento en árbol cuádruple son distribuidos en la pirámide de imágenes formada por I, Is₁ e Is₂, por medio un mapeo que asigna los bloques del primer nivel de particionamiento a la imagen Is₂ (que es la de menor resolución); los bloques del segundo nivel del particionamiento los asigna a la imagen Is₁ (de resolución intermedia); y los bloques del primer nivel de particionamiento los asigna a la imagen original I. Esta clasificación a través de los múltiples niveles de resolución de la pirámide de imágenes permite que todos los bloques del particionamiento en árbol cuádruple tengan el mismo número de píxeles en la imagen que les fue asignada,  ya  que  el mapeo  hace la  decimación de los renglones y las columnas de los bloques del particionamiento en un factor de 2 por cada nivel de menor resolución en la pirámide. El siguiente paso consiste en obtener un código fractal para los bloques de la partición en árbol cuádruple asignados a cada nivel de resolución.

Fig. 1: Codificación fractal a través de una pirámide multi-resolución de imágenes.

Los códigos de los bloques rango asignados  a las sub-imágenes Is₁ e Is₂, junto con los códigos de los bloques asignados a la imagen original I, son usados para formar el código fractal completo. Durante la decodificación, este código se itera en una misma resolución, utilizando un decodificador fractal en árbol cuádruple normal. En el método empleado se utiliza siempre un mismo tamaño de bloque para realizar la codificación en los diferentes niveles de resolución, por ello, un mismo tipo de módulo de procesamiento puede realizar la codificación de cada nivel de resolución.

Clasificación de Bloques: Los diferentes métodos existentes (Rinaldo y Calvagno, 1995; Lee y Ra, 1998), requieren de elementos de procesamiento adicionales para llevar a cabo tal clasificación, como el uso de filtros de onditas. En el método utilizado, se realiza una asignación de los umbrales de contraste para cada nivel de particionamiento del árbol cuádruple (Martínez et al., 2003). Así, si se codifica una imagen I usando un árbol cuádruple de N+1 niveles de particionamiento, en el primer nivel son codificados los bloques de p2^N×p2^N píxeles, siempre que su nivel de contraste sea menor o igual que U₁, definido éste como umbral superior. El bloque rango es dividido en cuatro bloques con p2^N-1×p2^N-1 píxeles, si su contraste de bloque es mayor a U₁, y son asignados al segundo nivel del árbol cuádruple. Si un bloque rango del segundo nivel tiene un contraste menor o igual que U₂, entonces el bloque rango es codificado en este nivel de particionamiento. Si, el contraste del bloque rango considerado es mayor que U₂, entonces el bloque rango será partido en cuatro bloques rangos con p2^N-2×p2^N-2píxeles cada uno. En general, si un bloque rango del i-ésimo nivel de particionamiento tiene un contraste menor o igual queU_i, entonces el bloque rango se codifica en este nivel de particionamiento, o en caso de ser mayor que U_i, es dividido en cuatro bloques rangos conteniendo a p2^N-i×p2^N-i píxeles cada uno, hasta que i = N. En este último nivel son codificadas todas las regiones que no lo hayan sido en los niveles anteriores. Ninguna zona se codifica en dos niveles diferentes.

El proceso antes descrito requiere de un módulo para estimar el contraste del bloque como la diferencia entre los valores de luminancia máximo y mínimo. Los procesos de particionamiento y clasificación de bloques en niveles de contraste se realizan antes o simultáneamente con el proceso de codificación fractal. La Figura 1 ilustra, de manera general, el proceso de codificación fractal mediante la clasificación de bloques rangos en múltiples niveles de resolución de acuerdo con su nivel de contraste.

ARQUITECTURA DEL CODIFICADOR

Organización de la arquitectura: Como punto de partida, la imagen a ser codificada se divide en M×M sectores de 32×32píxeles, los cuales a su vez se dividirán en K×K subsectores. Cada unidad de procesamiento tendrá a su vez K×K módulos de codificación fractal, los cuales se encargan de codificar cada uno de los subsectores de la imagen. En la figura 2 se muestra un ejemplo de un sector de imagen, en el cual K = 2. El conjunto de los códigos generados por los K´K módulos de codificación forman los códigos fractales que cada unidad de procesamiento entrega como resultado. Cada módulo codifica a bloques rangos de 2´2 píxeles.

Fig. 2: Cuatro bancos de registros de un sector de imagen de 32´32 píxeles.

La unidad de procesamiento: La arquitectura a bloques de la unidad de procesamiento se muestra en la Figura 3. La imagen a codificar es almacenada en M×M bancos de registros, de 32×32 bytes cada uno. Cada unidad de procesamiento cuenta con 4 módulos de codificación fractal, los cuales realizan en forma paralela la codificación de 4 bloques rango, pertenecientes a los sub-sectores de imagen asignados a ellos. Un decodificador de direcciones se encarga de seleccionar cada píxel, para extraer ya sea un bloque rango, procedente de un solo sub-sector de imagen, o un bloque dominio, integrado por píxeles de cuatro subsectores. Los datos de cada bloque imagen se transmiten píxel a píxel, desde los subsectores de imagen hacia los módulos de codificación fractal, una vez que se indica su dirección dentro del sector de imagen. La dirección de cada píxel dentro del banco de registros de la unidad de procesamiento está dividida en dos partes. La primera especifica en cual de los subsectores se encuentra el píxel deseado, mientras la otra especifica la ubicación relativa del píxel en el subsector. De esta forma, son necesarios dos decodificadores de direcciones: uno para los subsectores de la imagen (Figura 3), y otro para la posición relativa del píxel dentro del subsector de imagen (Figura 4).

El módulo de codificación fractal: constituye la unidad básica encargada de realizar el conjunto de operaciones de codificación: recepción de un bloque rango, recepción de bloques dominio, clasificación de bloques rango, cálculo de valores promedio de los bloques rango y dominio, transformación espacial y de luminancia  de bloques dominio, comparación del bloque rango con el bloque dominio transformado, cálculo del error MAD (mean absolute difference), y selección de la mejor transformación. En la figura 5 se muestra la arquitectura propuesta para el módulo de codificación fractal.

Fig. 3: Arquitectura de la Unidad de Procesamiento Fractal.

Las unidades de procesamiento adquieren el bloque rango accediendo a los píxeles de uno de los cuatro subsectores de imagen que les corresponde procesar. Los módulos de codificación fractal solo pueden recibir los datos de 8×8  bloques rango. Cada uno de los bloques rango de la imagen del subsector debe compararse con todos los bloques dominios contenidos en un sector de imagen, junto con sus 8 transformaciones isométricas. Los bloques dominios son proporcionados a los módulos de codificación por medio de las unidades de procesamiento, las cuales tienen acceso a todos y a cada uno de los datos dentro del sector de imagen.

Cada módulo de codificación fractal recibe, por parte de la unidad de procesamiento, un bloque rango diferente al de otros módulos. Los cuatro módulos de codificación fractal reciben por parte de la unidad de procesamiento un solo bloque dominio, el cual puede ser rotado o reflejado por el módulo de codificación. A medida que son recibidos los píxeles de un bloque rango o un bloque dominio, se calculan los valores promedio de luminancia, tras lo cual se transforma la luminancia del bloque dominio. La transformación de contraste de los bloques dominio se realiza sin multiplicadores, ya que se ha establecido un valor de s = 0.5 para el parámetro de ajuste de contraste. Debe notarse que los píxeles de un bloque dominio son almacenados en 8 registros, y no en 4 como sucede en los métodos tradicionales de dominio decimado.

Fig. 4: Decodificadores de acceso a los píxeles en un subsector de imagen.

Fig. 5: Arquitectura del módulo de codificación fractal.

El método utilizado utiliza una decimación de muestras de imagen similar a la disposición de casillas negras de un tablero de ajedrez. De esta forma, el bloque dominio se reduce, pues consideran solamente los píxeles cuya suma del renglón y la columna en la que se encuentra el píxel produce un número par (Martínez et al., 2004).

El objetivo de este tipo de decimación es obtener mejor calidad de imagen que la lograda en los métodos de dominio decimado, así como mayor rapidez de procesamiento comparada con la del método de dominio expandido, obteniendo calidad de imagen intermedia.

El error absoluto medio MAD se obtiene de la comparación de un bloque rango y un bloque dominio, y después de obtenerlo se compara este error con el obtenido en comparaciones anteriores de ese mismo bloque rango. Si el error MAD de la transformación actual es menor al de transformaciones anteriores, se registran los parámetros fractales de la transformación actual. Si el error MAD de la transformación actual resulta mayor o igual al obtenido en las transformaciones anteriores, se desecha la transformación actual y se procede a realizar otra transformación espacial o a capturar los píxeles de otro bloque dominio.

En la figura 5 se observa que el módulo de codificación cuenta con dos sumadores. Ellos permiten ejecutar en pipeline la diferencia entre píxeles de un bloque rango y de un bloque dominio, y la acumulación de esta diferencia para realizar el cálculo de la MAD de cada bloque rango, disminuyendo casi a la mitad el tiempo que se requiere si se utiliza un solo sumador.

El primer sumador es parte de un acumulador, de dos entradas, las cuales son conectadas a la salida de dos multiplexores que seleccionan las posibles fuentes de datos. El segundo sumador forma parte de un bloque cuya tarea específica es calcular el error absoluto medio de cada bloque dominio transformado, con respecto al bloque rango con que se le compara.

El módulo de codificación fractal cuenta también con un módulo comparador, que sirve para la comparación del error medio absoluto y obtención del menor error medio absoluto al comparar un bloque rango contra todos los dominios transformados; así como la clasificación de un bloque cuando se realiza el particionamiento en árbol cuádruple.