algoritmos deantialiasing - dialnetdialnet.unirioja.es/descarga/articulo/4902768.pdfalgoritmos...

ALGORITMOSDEANTIALIASING

Ing. Gabriel Mañana Guichón1

Resumen

Se presentan los algoritmos desarrollados parael trazado de lineas suaves y aplicación de textosobre imágenes, como ejemplo del trabajo deinvestigación que se lleva a cabo en el campodel filtrado de imágenes o antialia.sing.

Introducción

Los elementos discretos que componen unaimagen digital2, llamados plxeles (de pictureelement), son generados por un proceso demuestreo de una imagen contlnua'', en el domi-nio del espacio y en el dominio del color. Lasmuestras son tomadas en las posiciones deter-minadas por Una retícula (la técnica se llama

point sampling) definida en el espacio de losenteros (Figura 1).

Cuando se aplica una transformación espaciala una imagen (rotación, reducción, ampliación,etc.), los pixeles de la imagen resultante songenerados con una nueva retícula de muestreoque por lo general no coincide con los númerosenteros (Figura 2). Dado que la imagen de entradaestá definida solamente en posiciones enteras, sehace necesario aplicar un proceso de reconstruc-ción que interpole una función continua a partir delas muestras. Esta función puede ser entoncesmuestreada en posiciones arbitrarias, obtenién-dose así los pixeles de la imagen final.

Este proceso de interpolación es llamado recons-trucción de imágenes yel proceso de reconstruc-retícula de muestreo

imagen en imagen enespacio continuo espacio discreto

FIGURA 1. Retícula de muestreo utilizada en la digitalización de una imagen continua.

Departamento de Sistemas, Facultad de Ingeniería. Universidad Nacional de Colombia.

2 En este caso excluimos las imágenes sintéticas, Le•. generadas por computador.

3 Transformaciones geométricas de imágenes digitales, L. F. Niño y G. Hernández.

Ingenierla e Investigación 25

QUINCE AÑOS DE INGENIERfA DE SISTEMAS

,--- retícula demuestreopara rotaciónde 45°

imagen resultante

FIGURA 2. Ejemplo de una retícula de muestreo utilizada para una rotación.

ción seguido de un nuevo muestreo es llamadoconiontarnente remuestreo de imágenes.

La siguiente figura (Figura 3) muestra el marcoconceptual del procesamiento de imágenes di-gitales referenciado en este artículo. En un prin-cipio la imagen digital es obtenida por medio deun sistema electrónico de adquisición (básica-mente puede estar compuesto de una cámarade video y un equipo conversor análogo-digital,donde hay una primera etapa de muestreo). Enseguida pasa por una etapa de remuestreocompuesta de un proceso de reconstrucción dela señal continua y un nuevo proceso de mues-treo en las posiciones deseadas. La posiciónexacta de las nuevas muestras estará determi-nada por la transformación espacial en particu-lar que se aplique. Para evitar distorsiones enla imagen final se utilizan técnicas de filtradodigital (antialiasing) fundamentadas en la teoríadel muestreo.

Teoría del muestreo

La teoría del muestreo es una herramienta fun-damental en el estudio de sistemas digitales,

26 Ingenierfa e Investigación

específicamente en tareas tales como el proce-samiento de imágenes digitales. Nos provee elfundamento matemático necesario para el aná-lisis de señales discretas, dándonos una visiónprecisa de los problemas que surgen con elmuestreo de señales continuas, así como unabuena idea de las posibles soluciones. Para es-to nos brinda una elegante formulación mate-mática que describe la relación existente entre.una señal continua y sus muestras. En el casoque nos interesa esta formulación será utilizadaen la solución de problemas relacionados conla reconstrucción de imágenes y la aparición dedistorsiones o aliasing.

Por reconstrucción nos referimos al proceso deinterpolación aplicado a las muestras y por alia-sing a las distorsiones causadas por la presen-cia, en la señal continua, de altas frecuenciasque no son reproducibles en la imagen resultan-te dadas las limitaciones impuestas por la reso-lución del dispositivo de salida (monitor, etc.).

Además de definir los límites teóricos del proce-so de reconstrucción de una señal continua apartir de una entrada discreta, la teoría del

QUINCE AÑOS DE INGENIERIA DE SISTEMAS

muestreosistema deadquisición deimágenesdigitales

algoritmos de barrido

remuestreo (resampling)

reconstrucciónimagende entrada

transformacionesespaciales

imagende salidamuestreo

teoría delmuestreo

FIGURA 3. Marco conceptual del procesamiento digital de imágenes.

muestreo nos permite establecer la calidad delas diferentes técnicas de filtrado o antialiasing.

Aliasing

A través de las técnicas de reconstrucción deimágenes se resuelve uno de los primeros pro-blemas que aparecen al trabajar en un dominiodiscreto: muestrear en posiciones arbitrariasuna entrada originalmente discreta. Otro proble-ma aparece sin embargo al evaluar la salida dis-creta. Este problema, que hace parte de la etapade remuestreo, se describe a continuación.

La imagen resultante, como ya se ha visto, hasido generada a partir de un muestreo puntualde la imagen de entrada reconstruida. Pormuestreo puntual nos referimos a un procesode muestreo "ideal" donde el valor de cada pun-to es tomado en forma independiente de susvecinos. Esto es, cada punto en la imagen deentrada tiene influencia en un punto, y solo uno,de la imagen de salida.

Cuando se aplica una transformación espacial,con el muestreo puntual son descartados inter-valos completos de la imagen de entrada. Siesta imagen de entrada varía en forma suave,la información perdida puede ser recuperadapor medio de interpolación, esto es, reconstruc-ción. Sin embargo, si los intervalos descartadosson lo suficientemente complejos (la imagen deentrada varía en forma abrupta en intensidad),el proceso de interpolación puede resultar defi-ciente y por ende la información descartada,irrecuperable. En este caso se dice que la señalo imagen de entrada ha sido submuestreada(undersampled) y cualquier intento de recons-trucción dará origen a distorsiones o aliasing.Estas distorsiones, causadas por la presenciade altas frecuencias no reproducibles, apare-cen en forma de bordes escalonados o patronesde Moiré.

El filtrado empleado para contrarrestar estosefectos es llamado antialiasing y se fundamentaen los principios bien establecidos por la teoríadel muestreo. Una técnica típica de filtrado se

Ingeniarla e Investigación 27

QUINCE AÑOS DE INGENIERíA DE SISTEMAS

basa en el desenfoque de la imagen de entradaantes de ser remuestreada. Esto permite quelos puntos muestreados hayan sido influidospor los puntos vecinos que luego serán descar-tados. De esta forma las distorsiones puedendisminuirse pero no ser eliminadas. Una ima-gen de salida totalmente libre de distorsionessolo puede ser obtenida muestreando a una fre-cuencia lo suficientemente alta, como lo dicta lateoría del muestreo. Sin embargo, las limitacio-nes impuestas por la resolución del dispositivode salida por lo general impiden esta alternativay por lo tanto se recurre a "suavizar" la imagende entrada antes de volverla a muestrear.

Si bien los principios de la teoría del muestreoofrecen sendos fundamentos teóricos paraafrontar el problema de las distorsiones, existenlimitaciones prácticas en la implementación delos filtros ideales propuestos por esta teoría. Deaquí que se hayan propuesto numerosos algo-ritmos para lograr soluciones aproximadas. Eneste artículo se presenta un algoritmo para eltrazado de líneas suaves, basado en el conoci-do algoritmo de Bresenham yen una técnica defiltrado llamada EWA (Elliptical Weighted Ave-rage) propuesta por Greene y Heckbert en1986, y un algoritmo para la reducción de losbordes escalonados en la aplicación de textosobre imágenes, basado en una técnica llama-da supermuestreo o posñltrado. Antes, sin em-bargo, se hace una breve revisión de la teoríadel muestreo y su aplicación en el filtrado deimágenes.

El problema básico enfrentado se conoce comoreconstrucción de señales y puede ser plantea-do de la siguiente forma+

- Dada una señal continua g(x) y su contra-parte muestreada gs(x), ¿son suficientes lasmuestras que componen gs(x) para describirexactamente g(x)?

- Si este es el caso, ¿cómo puede ser recons-truida g(x) a partir de gs(x)?

La solución se encuentra en el dominio de lafrecuencia donde es utilizado el análisis espec-tral para examinar el espectro de la informaciónmuestreada. Las conclusiones derivadas delanálisis de este problema serán útiles en la eta-pa de remuestreo y serán indicativas del filtradonecesario para evitar las distorsiones.

El importante teorema del muestreo nos permi-te relacionar la resolución de la retícula demuestreo con la naturaleza de la imagen, másespecíficamente con las frecuencias espacialespresentes en la imagen. En forma intuitiva sepuede notar que cuanto más compleja (en tér-minos de detalle) sea la imagen, más densadeberá ser la retícula para poder reproducir es-tos detalles. En términos formales el teoremadel muestreo establece lo siguiente:

Una señal continua univariada, limitada en frecuen-ciaSI puede ser reproducida completamente a partirde un conjunto de muestras tomadas a intervalos re-gulares. El intervalo entre las muestras debe ser me-nor a un medio del período de la componente demayor frecuencia de la señal.

Esto último equivale a decir que la frecuenciamínima de muestreo debe ser mayor al doblede aquella de la componente de mayor frecuen-cia de la señal. Esta frecuencia mínima demuestreo, conocida como la frecuencia deNyquist, corresponde a la distancia mínima en-tre las copias de los espectros de la señal. Enla Figura 4 se pueden apreciar los efectos demuestrear una función sinusoidal a una fre-cuencia mayor que la frecuencia de Nyquist (a),a una frecuencia igual (b), a una frecuencia me-nor (c) y por último a una frecuencia bastantemenor (d). En el primer caso el intervalo demuestreo es claramente menor a la mitad delperíodo de la onda seno y por lo tanto no haypérdida de información. En el segundo caso el

4 En esta parte se asume un conocimiento básico sobre la teoria de Fourier (análisis y síntesis).

5 Esto con el fin de evitar espectros de extensión infinita, imposibles de reproducir sin superposición.

28 Ingenierla e Investigación


g(x) puntos de.s=~

intervalo demuestreo

(a)

g(x)

(e)

g(x)

x

(b)

g(x)/ñal original

x

"'~ñal interpolada

(d)

FIGURA 4. Representación en el dominio del espacio del muestreo de una onda seno.

intervalo de muestreo es igual a la mitad delperíodo y de esta manera las muestras coinci-den con el paso por cero de la onda seno. Esevidente que en este caso no se obtiene infor-mación alguna sobre la función muestreada(por los puntos de muestreo pasan infinitas on-das seno diferentes). Cuando el intervalo demuestreo es mayor que la mitad del período,casos (c) y (d), las muestras generan ondas se-no de menor frecuencia que la onda original.Estas frecuencias menores son conocidas co-mo alias de la onda original y de ahí la deriva-ción del término aliasing .

Esta situación puede ser generalizada conside-rando estos casos en el dominio de la frecuen-cia para una función g(x) cualquiera. Estafunción puede representar, por ejemplo, la va-riación (continua) de la intensidad en una líneade pixeles (scanline).

En la Figura 5 aparece la representación en eldominio de la frecuencia del muestreo y recons-trucción de una onda seno. En la parte (a) de lafigura aparece el espectro de frecuencia de laseñal de entrada g(x), donde se puede apreciarla distribución de energía en el ancho de banda,presentando una concentración en el rango delas bajas frecuencias.

En la parte (b) aparece el espectro de frecuen-cia de la función utilizada para el muestreo ofiltro, consistente en una serie de Irneas que seextienden (teóricamente) hasta infinito, separa-das por fs que es la frecuencia de muestreo. Lafunción de muestreo puede ser la función impul-so o función delta de Dirac, o la función delta deKronecker si se está operando en un dominiodiscreto. Cuando una función Impulso es apli-cada a un filtro, un impulso modificado se pro-



la) espectro de I g( f) Ifrecuencia de ~x)

Áfmax fs f

(b) espectro defrecuencia de lafunción ele muestreo

~ ~ ~f

fs

(el espectro deIgs(f)1frecuenciel de la

función muestreada

Á~ ~f

(d] filtro pa88 bajosideal r Ifl < f_h( f) =

.,.. .."'. O Ifl~fmax. ..,. ...'. ..

fmax f

le) función g(x)reconstruida

Áf

FIGURA 5. Muestreo y reconstrucción de una onda seno.



duce a la salida, conocido como respuesta alimpulso del filtro.

En un sistema gráfico, la respuesta al impulsoaparece como la imagen producida por el siste-ma, como respuesta a un punto (ideal) en laimagen de entrada. En este caso el impulsopuede ser asimilado a un punto blanco, infinite-simalmente pequeño, sobre un fondo comple-tamente negro.

Para muestrear en el dominio del espacio semultiplica g(x) por la función de muestreo. Elproceso equivalente en el dominio de la fre-cuencia es llamado convolución e involucra alespectro de frecuencia de la función de mues-treo y al espectro de frecuencia de g(x). El re-sultado -convolución de (a) y (b)- es el espectrode frecuencia que se ve en la parte (e), espectrode la versión muestreada de g(x). Esta versiónmuestreada es entonces multiplicada por un fil-tro de reconstrucción, o núcleo de convoluciónen el dominio de la frecuencia (d), para repro-ducir la señal original (e).

En la Figura 6 se muestra el proceso anteriorpero ahora utilizando una frecuencia de mues-treo menor que la frecuencia de Nyquist. En laparte (c) se puede ver que en el espectro defrecuencia de la versión muestreada aparecenlos espectros de frecuencia de g(x) traslapados.De esta manera, las altas frecuencias (corres-pondientes a detalles en la imagen) aparecencomo interferencia en las regiones de bajas fre-cuencias (e), equivalentes a distorsiones en laimagen de salida.

Estas distorsiones pueden ser reducidas de dosmaneras diferentes. La primera consiste en au-mentar la frecuencia de la retícula de muestreo,esto es, aumentar la resolución de la matriz depixeles utilizada (monitor, etc.). Esto conllevadesventajas técnicas y económicas obvias. Porotra parte, el espectro de frecuencia de una ima-gen puede extenderse infinitamente, por lo queaumentar la frecuencia de muestreo no necesa-riamente resuelve el problema.

La segunda forma se basa en la aplicación defiltros digitales que atenúan las altas frecuen-cias presentes en la imagen, tratando de ajustarla señal a una frecuencia de muestreo predeter-minada (resolución). En computación gráfica seutilizan básicamente dos métodos para eliminaro reducir las distorsiones causadas por el alia-sing: el primero es conocido como muestreo poráreas (area sampling) o prefiltrado y el segundocomo supermuestreo o posfiltrado (supersam-pling). Un tercer método, aún en investigación,es el llamado muestreo irregular, no uniforme oestocástico, donde se utiliza una retícula en lacual la posición de los puntos de muestreo hasido determinada probabilísticamente (median-te una técnica de tipo Monte Carla, por ejem-plo). Dentro de este enfoque se han desarro-llado algoritmos tales como el muestreo dePoisson (Poisson Sampling) y el muestreo pordifusión de puntos (Point-difussion Sampling)entre otros.

Los algoritmos presentados más adelante sonejemplos de técnicas demuestreo por áreas -tra-zado de líneas suaves- y de posfiltrado-elimina-ción de bordes escalonados en la aplicación detexto. A continuación se presenta una breve revi-sión de estas dos técnicas de filtrado.

Prefiltrado o muestreo por áreas

La idea clave detrás de la técnica del muestreopor áreas está en considerar que el pixel desalida representa un área y no un punto comose asume en el muestreo puntual (point sam-pling). Este debe ser visto entonces como unaventana a la imagen de entrada. En vez demuestrear un punto, se aplica un filtro pasaba-jos sobre el área proyectada y se determina asíel contenido de información que está siendoefectivamente mapeado al pixel en la imagende salida. El filtro pasabajos lleva a cabo la eta-pa de prefiltrado yel área proyectada se conocecomo preimagen. Al limitar la frecuencia de laimagen de entrada antes de ser remuestreada,el filtro ayuda a disminuir las distorsiones.



(a) espectro de I g( f) Ifrecuencia de g(x)

Áfmax r, f

lb) espectro defrecuencia de lafunción de muestreo

~ ~ ~f

fs < 2fmax

(e) espectro de19s(f)1frecuencia de la

función muestreada

~f

(d) filtro pasa bajosideal

fh(f)

Ifmax f

(e) función g(x)reconstruida

~f

FIGURA 6. Muestreo y reconstrucción de una onda seno, utilizando una frecuencia de muestreo inadecuada (fs < 2fs).



Esta técnica fue desarrollada por Catmull en1978. Si bien la técnica original planteada porCatmull es prohibitiva en términos computacio-nales, ésta ha dado origen a múltiples enfoquesprácticos.

El algoritmo se basa esencialmente en trabajara nivel de sub-pixel en el dominio continuo dela imagen, calculando el área efectiva del pixelque es cubierta por el elemento gráfico (línea,polígono, etc.) y utilizando este valor como fac-tor de intensidad. En el caso particular que nosinteresa (línea), se utiliza la siguiente función"para calcular la fracción de círculo cubierta porun semiplano (Figura 7):

Ahora, teniendo en cuenta que r = 1/2, el áreade intersección entre una línea de ancho 2a yun pixel se puede expresar en términos de lafunción cov (d) y en términos del ancho de laHnea:

TABLA 1Intersección línea-pixel*

rango de p fracción de círculo

a < r

O 5: P < a 1 - cov(a-p) - cov(a+p)a 5: p < roa cov(p-a) - cov(p+a)

roa 5: p cov(p-a)

a ;:: r

O 5: P < a 1 - cov(a-p)a 5: p cov(p-a)

* Kelvin Thompson, Nth Graphics, Ud., Austin, Texas.

La fracción obtenida multiplicada por el área delcírculo (1tr2), representa el área efectiva de in-tersección.

La razón de modelar el pixel de salida (p.e. mo-nitor) como un círculo corresponde a la técnica

d >= r, O

cov( d, r)d.Jr2 - d2= 1 d1

d < r, - - - - arcsen-2 1t r2 1t r

FIGURA 7.

6 Resultado de integrar la ecuación del semicírculo entre d y r.



de filtrado propuesta por Greene y Heckbert en1986 (con orígenes en Feibush, Levoy y Cook,1980), Y la razón se encuentra en el hecho deque el mapeo inverso de un círculo (su preima-gen en el espacio de la textura) siempre es unaelipse. Sin importar el tamaño, ecentricidad uorientación, la forma es invariante y este hechoes explotado por el método. Esta técnica estábasada en algoritmos desarrollados para el ma-peo de texturas.

Supermuestreo o posfiltrado

El proceso de utilizar más de una muestra porpixel es conocido como supermuestreo. Se uti-liza una retícula de muestreo más densa que laretícula de salida. Si se tiene una relación de 3a 1, por ejemplo, se tienen 9 muestras por cadapixel de salida. El valor de este pixel se calculaa partir del promedio de las muestras tomadasen las respectivas preimágenes.

Formalmente el método consiste en tres eta-pas, pero en la práctica la segunda y la tercerase combinan en una sola:

1. El dominio continuo de la imagen es mues-treado a n veces la resolución del monitor odispositivo de salida. En la práctica esto sig-nifica que la imagen es generada a una re-solución n veces mayor que la resolución delmonitor.

2. La imagen muestreada es sometida a un fil-tro pasa bajos a la frecuencia de Nyquist delmonitor.

3. La imagen filtrada es remuestreada a la re-solución del monitor.

Los algoritmos desarrollados dentro de estatécnica difieren en el valor de n yen la forma delfiltro utilizado. Usualmente para una resoluciónde 512 x 512 se utiliza un supermuestreo de2048 x 2048 (n = 4). La imagen de alta resolu-ción generada es reducida a la resolución finalde 512 x 512 promediando el valor de los pixe-les y esto equivale a aplicar una convolución


con un filtro cuadrado (box filter). Aplicando unfiltro cuyos pesos cambian a través de su núcleose pueden obtener mejores resultados. Crow(1981) por ejemplo plantea la utilización de"ventanas de Barlett", tres de la cuales se mues-tran en la siguiente tabla:

TABLA 2Ventanas de Barlett utilizadas

en el posfiltradode una imagen supermuestreada

3x3 5x5 7x71 2 1 1 2 3 2 1 1 2 3 4 321242 24642 2 4 6 8 6421 2 1 3 6 9 6 3 3 6 9 12 963

24642 4 8 12 16 12 8 41 2 3 2 1 3 6 9 12 963

2 4 6 8 6421 2 3 4 321

El mecanismo radica en centrar la ventana so-bre un pixel de la supermuestra y calcular lasuma de los productos de cada pixel por el pesocorrespondiente en núcleo del filtro. Este valor,dividido por la suma de los pesos del núcleo, esel valor del pixel correspondiente en la imagende salida. Desplazando la ventana a través dela imagen de alta resolución se obtienen los pi-xeles de la imagen filtrada.

Un efecto secundario del supermuestreo estáen el desenfoque de la imagen original. Estoocurre a causa de la integración que se lleva acabo entre los vecinos de cada pixel. Esto sig-nifica que existe un compromiso en la eleccióndel tamaño del filtro. Un filtro grande tendrá unafrecuencia de corte más baja y por lo tanto serámás eficiente al reducir las distorsiones causa-das por el aliasing. Sin embargo, el efecto dedesenfoque será mayor y adicionalmente serámás costoso en términos computacionales.


Algoritmo para el trazadode líneas suaves

El algoritmo se basa en calcular la intensidad decada pixel de acuerdo al área que es cubierta porla línea. Para esto se utiliza una extensión del al-goritmo de Bresenham y la función desarrolladaen la sección 3 (Tabla 1). En cada iteración, elalgoritmo usual avanza un pixel en la dirección deleje mayor y cero o uno en la dirección del ejemenor, para determinar la posición del siguientepixel. En el ejemplo de la Figura 8, el eje mayor esel eje X (pendiente en el rango [-1,1]).

cular esta distancia se utiliza la relación queexiste entre la distancia vertical y la distanciaperpendicular del pixel a la línea:

p V J1+1m2

línea con pendiente m

• pixeles centrales encontrados con el algoritmo de Bresenham

pixeles encontrados mediante los 'ciclos ortogonales'

FIGURAS.

A este algoritmo se le agregan dos ciclos, lla-mados "ciclos ortogonales", dentro del cicloprincipal. Una vez determinada la posición delpixel central, el primer ciclo examina los pixelesadyacentes en la dirección positiva del eje me-nor y el segundo examina los pixeles adyacen-tes en la dirección negativa. En cada pixelvisitado, el algoritmo calcula la distancia quehay desde el centro del pixel a línea central delsegmento que se está pintando. Esta distanciaes utilizada (generalmente a través de una ta-bla) para calcular el área efectiva del pixel quees cubierta por el segmento de línea. Para cal-

l/línea con antialiasing: basado en el algoritmode Kelvin Thompson,Nth Graphics, Austin, Texas.1/

1/1/ equipo:1/ pixeles:1/ enteros:

Silícon Graphics, Personal Iris 35RGBA/8 bits@canal32 bits

1/ PIXELtypedef unsigned char BYTE;typedef struct PIXEL PIXEL;struct PIXEL {

BYTE r:BYTE g;BYTE b;BYTE a;

11 rojo1/ verde11 azul11 opacidad



};

1/ punto fijotypedef int FXD;

1/ macros# define FXD_FRACCION# define FXD_ZERO# define ANCHO_MAX

16O1280 1/ monitor: 1024 x 1280

# define SWAP (x, y)# define AOOR (x, y)

( (x)"=(y)"=(x)"=(y) )( (x)+(y*ANCHO_MAX) )

1/ intercambia dos enteros1/20 -> 10

# define AREA (d)# define VP_FACTOR (m)

1/ tablas precalculadasarea [d]factor [m]

1/ d en [O, 255]11 dist. vertical -> dist. perp.11 sqrt (1/(1+m"2»

# define FXOMUL (fx1, fx2) ( (fx1 «FXO_FRACCION)*fx2) 11 multiplicación punto fijo

# define BLEND (el, cf) ( (((255-(cl»*(cf» » 8) + (cl» 11 cl: color línea {O, 255}11 cf: color fondo {O, 255}

# define OY_GT _OX# define OY_LT_ZERO

12

11 abs (dy) > abs (dx)11 dy <O

1/ incremento p/pixeles adyacentesstatic int incAdy {4} = {AOOR(1, O),ADOR(O, 1), AOOR(1, O),AOOR(O, -1)};

11 incremento p/pixeles diagonalesstatic int incDiag {4} = {ADOR(1, 1), AOOR{1, 1}, AOOR(1, -1), AOOR(1, -1)};

1/ incremento p/pixeles ortogonalesstatic int incORT {4} = {AOOR(O, 1), AOOR(1 , O), AOOR(1, O)};

extern FXD fxPmax; 1/ máxima distancia perpendicular;1/1/2 ancho de línea + radío del pixel

l/línea c/antialiasing del punto (xi, yi) al punto (xf, yf),1/ color (r, g, b), opacidad a, sobre imagen en buffer pBuf

voidlínea_aa (int xi, int yi, int xf, int yf, BYTE r, BYTE g, BYTE b, BYTE a, PIXEL* pBuf){



int nBres;int nAdylnc;int nDiaglnc;

int nAdyDirlnc;int nDiagDirlnc;int nOrtDirlnc;

FXD fxDistBres;FXD fxlncAdyBres;FXD fxlncDiagBres;"FXD fxDistCur;FXD fxlncOrtCur;

int nDX;int nDY;int nDir;

FXD fxPendiente;

PIXEL* pBres;PIXEL* pCur;

register float fOPregister float fFACT;

if (xi> xf){

SWAP (xi, xf);SWAP (YI, YF);

}

11 DELTASnDX = xf - xi:nDY = yf - yi;

11 categoría s/pendientenDir = O;if (nDY < O){

1/ variable de decisión, algoritmo de Bresenham1/ incremento adyacente p/nBres11 incremento diagonal p/nBres

11 incremento en la dirección p/pixel adyacente11 incremento en la dirección p/pixel diagonál1/ incremento en la dirección p/pixel ortogonal

1/ distancia perpendicular, pixel Bresenham1/ incremento adyacente, pixel Bresenham1/ incremento diagonal, pixel Bresenham1/ distancia perpendicular, pixel visitado1/ incremento ortogonal, pixel visitado

1/ delta en x1/ delta en y1/ categoría según pendiente dy/dx

1/ pendiente dY/dx

1/ dirección pixel Bresenham1/ dirección pixel visitado

= (float)a/255.0; 1/ opacidad línea {O, 1}

1/ siempre de izquierda a derecha

1/ dx > O

I/0~m<1I/m<O

nDir I=DY_LT_ZERO;nDY = -nDY; 1/ siempre m > O (simetría)

}if (nDY > nDX) 1/ abs(m) > 1{

nDir I=DY_GT _DX;SWAP(nDX, NDY); 1/ siempre primer cuadrante (simetría)

Ingenierfa e Investigación 37


11 direcciones inicialespBres = pBuf + ADDR( (Iong)xi, (Iong)yi );nAdyDirlnc = incAdy[nDir];nDiagDirlnc = incDiag[nDir];nOrtDirlnc = incOrt[nDir];

11 distancias perpendicularesfxPendiente = (nDY« FXD_FRACCION) I nDX;fxlncOrtCur = VP_FACTOR (fxPendiente);fxlncAdyBres = FXDMUL (fxPendiente, fxlncOrtCur);fxlncDiagBres = fxlncOrtCur - fxlncAdyBres;fxDistBres = FXD_ZERO;

11 BresenhamnAdylncnDiaglncnBres

= nDY« 1;= (nDY - nDX)« 1;= nAdylnc - nDX;

do {

11 pixel centralfFACT = fOP*AREA (abs (fxDistBres»;pBres ->r = BLEND «BYTE) (fFACT*r), pBres->r);pBres ->g = BLEND «BYTE) (fFACT*g), pBres->g);pBres ->b = BLEND «BYTE) (fFACT*b), pBres->b);

"ciclo ortogonal tfor ( fxDistCur = fxlncOrtCur - fxDistBres, pCur = pBres + nOrtDirlnc;

fxDistCur < fxPmax;fxDistCur += fxlncOrtCur; pCur += nOrtDirlnc )

{

fFACTpBres -> rpBres-> 9pBres-> b

}

=fOP*= BLEND «BYTE) (tFACT*r), pBres-> r);= BLEND «BYTE) (fFACT*g), pBres-> g);= BLEND «BYTE) (fFACT*b), pBres-> b);

" ciclo ortogonal !tor ( txDistCur = txlncOrtCur + fxDistBres, pCur = pBres - nOrtDirlnc;

fxDistCur < fxPmax;fxDistCur += fxlncOrtCur; pCur = nOrtDirlnc)

{fFACTpBres->rpBres->gpBres->b


= tOP* AREA(abs(fxDistCur»;= BLEND «BYTE) (tFACT*r), pBres->r);= BLEND «BYTE) (tFACT*g), pBres->g);= BLEND «BYTE) (tFACT*b), pBres->b);


}

" próximo pixel s/algoritmo de Bresenhamif (nBres < O)

{ nBres += nAdylnc;pBres += nAdyDirlnc·sizeof(PIXEL);fxDistBres += fxlncAdyBres;

}else{ .

nBres += nDiaglnc;pBres += nDiagDirlnc·sizeof(PIXEL);fxDistBres += fxlncDiagBres;

}

-nDX;

} while (nDx >= O);

} "línea_aa

Algoritmo para la aplicaciónde texto con filtrado

El algoritmo está basado en la técnica presen-tada en la sección 4. A continuacióñ se analizanlas partes más relevantes del código desarro-llado para un programa que se utiliza en la ge-neración de totodocurnentos bajo ambienteMS-Windows. En esta aplicación se debía solu-cionar el problema de aplicar texto sobre imá-genes, en cualquiera de las fuentes disponiblesy con suavizado de bordes escalonados.

En primer lugar se aplica el texto en un disposi-tivo de memoria (CreateCompatibleBitmap)KERNEL_SIZE veces más grande que el áreade texto original. KERNEL_SIZE es el tamañodel núcleo de filtrado utilizado y puede ser 3, S,7, o un valor mayor, dependiendo de la calidadfinal deseada, equipo destino, etc .. Aquí se de-be tener en cuenta que luego, al hacer el re-

muestreo de la imagen para retornar a la reso-lución de pantalla, el número de multiplicacio-nes y sumas crece según el cuadrado deltamaño del núcleo. Adicionalmente, y como semencionó antes, el efecto de desenfoque tam-bién crece con el tamaño del núcleo.

" se aplica el texto en un dispositivo de memoria

HDC hdc - GetDC (pOwner->HWindow);

" crea un 'device context' compatible con el monitorHDC hMemDC - CreateCompatibleDC(hdc);if (hMemDC -- NULL) .{

return FALSE;}

" ancho/alto de área de textoint nTextWidth - rText.righ - rText.feft;int nTextHeigth - rText.bottom - rText.top;

Ingenierfa e Investigación 39


1/ se crea un bitmap compatible, KERNEL_SIZE vecesmás grande

nTextWidth *_ KERNEL_SIZE;nTextHeight *_ KERNEL_SIZE;

HBITMAP hBitmap _ CreateCompatibleBitmap(o hdc,

nTextWidth,nTextHeight) ;

if (hBitmap .... NULL){

DeleteDC(hMemDC);return FALSE;

1/ se selecciona el bitmap creado como objeto gráficoen usoHBITMAP hPrevObject _ SelectObject(hMemOC, hBitmap);

1/ se borra el bitmapBitBit (hMemDC,

O,O,nTextWidth,nTextHeight,hdc,O,O,BLACKNESS);

1/ se pinta el texto en el dispositivo de memoriapText->apply(pOwner->HWindow,

hMemDc,rText.lett,rText.top,SRCCOPY);

1/ recupera objeto gráfico previo,l/libera dispositivo de memoriaSelectObject(hMemDc, hPrevObject);DeleteDC(hMemDC) ;

La función miembro applyt), de la clase Text,simplemente agranda el tamaño de la letraacorde a KERNEL_SIZE y luego pinta sobre eldispositivo destino:

LOGFONT If;

_fmemcpy (&If, &lfFont, sizeof(LOGFONT));

if (antiAliasO)


If.lfHeight*=KERNEL_SIZE;

}

HFONT hfFont _ CreateFontlndirect(&If);

HFONT hfPrevFont _ SelectObject(hdc, hfFont);

SetTextColor(hdc, geteolorO);SetBkMode(hdc, TRANSPARENT);

TextOut ( hdc,r.left - nHscrollPos,r.top - nVscrollPos,szText,strlen(szText»;

SelectObject(hdc, hfPrevFont);DeleteObject(hfFont) ;

Una vez generada la imagen con el texto, dealta resolución, se le aplica un proceso de de-senfoque (blur) de radio de efecto 2, 3, o mayor,dependiendo como siempre del equipo destino,tamaño de la letra, estilo (normal, negrita, etc.)y calidad final deseada.

Una vez aplicado el proceso de desenfoque sedebe reducir la imagen a la resolución del mo-nitqr. Para esto se utiliza un núcleo de interpo-lación apropiado, una ventana de Barlett porejemplo (ver Tabla 2), que se hace pasar sobrela imagen, avanzando KERNEL_SIZE en cadapaso. Cada vez que el núcleo es centrado sobrela imagen se toman KERNEL_SIZE*KER-NEL_SIZE muestras, que promediadas segúnlos pesos del núcleo conforman el valor del pixelen la imagen de salida.

Esta imagen con el texto ya suavizado se com-pone fácilmente con la imagen de fondo, pixela pixel, teniendo en cuenta el factor de compo-sición asignado (opacidad) para el texto.


BIBllOGRAFIA

ANGEL, Edward, Computer Graphics, Addison-Wesley, MA, 1990.

BRESENHAM, J.E., Ambiguities in Incremental UneRastering, IEEE Computer Graphics and Appli-cations, 7(5), pp. 31-43, 1987.

CATMULL, E., A Hidden-Surface Algorithm with An-tialiasing, Computer Graphics, 12(3), pp. 6-11,1975.

CROW, F.C., A Comparison o, Antialiasing Techni-ques, IEEE Computer Graphics and Applica-tions, 1(1), pp. 40-49, 1981.

HARRINGTON, S., ComputerGraphics: A Program-ming Approach, McGraw-HiII, NY, 1983.

NIÑO, LUIS., Y HERNÁNDEZ, GERMÁN., "Trans-formaciones Geométricas de Imágenes Digita-les", Memorias del Tercer Encuentro deGeometría y sus Aplicaciones, Universidad Pe-dagógica, 1993.

THOMPSON, Kelvin, Graphics Gems, AcademicPress, MA, pp. 40-48, 105-106, 1990.

WATT, Alan, Fundamentals o, Three-DimensionalComputerGraphics, Addíson-wesley, GB, 1989.

WOLBERG, George, Digitallmage Warping, IEEEComputer Society Press, Los Alamitos, CA,1990.


algoritmos deantialiasing - dialnetdialnet.unirioja.es/descarga/articulo/4902768.pdfalgoritmos...

Documents