FANDOM


Transformada de Walsh

Andréia Teixeira Pilla


Resumo Edit

Este trabalho descreve a transformada de Walsh, apresentando sua definição, funcionamento, aplicações e implementação.

Introdução Edit

A transformada de Walsh consiste de uma função inicialmente estudada em 1923 por Joseph Walsh. Esta transformada é bastante utilizada em processamento de sinais, podendo ter diversas variações e generalizações como por exemplo a transformada rápida de Walsh ou a trasnformada discreta que é a transformada que será abordada neste trabalho.

Organização do trabalho Edit

Este trabalho está organizado da seguinte forma: primeiramente será apresentada a definição da transformada e a sua fórmula. Na próxima seção, será apresentada a implementação. Após a implementação serão apresentadas as aplicações da transformada e para finalizar o trabalho serão apresentados os resultados da mesma e as considerações finais.

Transformada de Walsh Edit

As funções deWalsh consistem de sequencias de pulsos quadrados onde os estados permitidos são somente 1 e -1, de modo que as transições possam ocorrer apenas em intervalos fixos de uma determinada unidade de tempo. O estado inicial é sempre +1 e as funções satisfazem certas relações ortogonais. Em particular, as funções de Walsh 2^n de ordem n consistem das linhas da matriz H_{2^n} de Hadamard quando organizada na ordem de sequencia. Na figura a seguir podem ser observada 2^n funções Walsh de comprimento 2^n para n=1, 2 e 3 (WEISSTEIN, 2004).

WalshFunctions 800
Gráficos da Função de Walsh


A seguir serão apresentadas as equações utilizadas na transformada de Walsh. Segundo Gonzalez (2003), quando N=2^n, a transformada de Walsh de uma função f(x), denotada por W(u), é obtida pela substituição do núcleo a seguir na transformada de Fourier:

g(x,u)=\frac{1}{N} \prod_{i=0}^{n-1} (-1)^{b_i(x)b_{n-1-i}(u)}

Isto gera a seguinte equação, que corresponde a equação da transformada de Walsh:

W(u)=\frac{1}{N} \sum_{N-1}^{x=0} f(x) \prod_{i=0}^{n-1} (-1)^{b_i(x)b_{n-1-i}(u)}


Na figura a seguir é possível observar como ficaria a aplicação desta formula a diferentes valores:


Exemplo



Implementação Edit


# Funcao para converter decimal para binario


#funcao que calcula o valor de b a ser colocado na formula apresentada anteriormente
def calcularb( i, j, x, y ):
    tamx    = len(x) - 1
    tamy    = len(y) - 1
    indicex = tamx - i
    indicey = tamy - j
    
    bi   = -1
    bj   = -1
    
    if ( x == '0' ) or ( x == '1' and indicex > 0 ) or ( indicex < 0 ):
        bi = 0 
    else:
        bi = x[indicex]
        
    if ( y == '0' ) or ( y == '1' and indicey > 0 ) or ( indicey < 0 ): 
        bj = 0
    else:
        bj = y[indicey]

    return bi, bj
        

#funcao que calcula a potencia da formula
def potencia( n, i, x, y, u, v ):
    j = n - 1 - i #índice do 2º e 4º b
    bi = 0
    bj = 0
    mult1 = 0
    mult2 = 0
    bi, bj = calcularb( i, j, Denary2Binary(x), Denary2Binary(u) )    
    mult1 =  int(bi)*int(bj)    
    bi, bj = calcularb( i, j, Denary2Binary(y), Denary2Binary(v) )
    mult2 =  int(bi)*int(bj)
    return mult1+mult2

#funcao que calcula o núcleo da equacao que foi apresentado anteriormente, aplicando a funcao de potencia acima
def nucleo( n, i, x, y, u, v ):
    pot = potencia( n, i, x, y, u, v )
    ncl = (-1)**pot
    return ncl


#funcao da transformada de walsh
def walsh( f, n, N ):
    ii  = 0
    ncl = 0
    u   = 0
    v   = 0
    lin  = f.shape[0]
    col  = f.shape[1]
    W = zeros((lin,col)) #imagem transformada
    fxyinterno  = 0
    fxyexterno   = 0
    resultnucleo = 0
    for i in range( f.shape[0] ):
        for j in range( f.shape[1] ):
            for a in range( N ):
                for b in range( N ):
                    u = i
                    v = j
                    ncl = nucleo( n, ii, i, j, u, v )
                    #print ncl
                    fxyinterno = 0
                    for ii in range(n):                        
                        resultnucleo = f[a,b]*ncl #faz f(x,y)*cada resultado do núcleo
                        fxyinterno   = fxyinterno + resultnucleo # faz a soma de f(x,y)*nucleo de i=0 até i = n-1
                        #print resultnucleo

                    W[i,j] = fxyinterno/N
                    resultnucleo = 0
    return W



Aplicação Edit

Dentre as aplicações existentes da Transformada de Walsh e possíveis aplicações, pode-se citar a utilização de algoritmos para detecção de sinal sísmico, baseados na transformada de Walsh (GOFORTH e HERRIN, 1981), que possuem uma capacidade de detecção comparável a um analista humano e são bastante utéis para ajudar a detectar terremotos.

A transformada pode ser utilizada também na área de reconhecimento de padrões para reconhecimento de caracteres (CHUNG e HUANG, 1987) ou até mesmo reconhecimento facial (NIXON e JIA, 1994), que são funcionalidades muito importantes atualmente, principalmente o reconhecimento facial que vem se tornando cada vez mais utilizado para questões de segurança. Além disso, a transformada tem inúmeras aplicações na área de design auxiliado por computador (CAD - computer-aided design) (CLARKE et al, 1997).

Resultados Edit

A seguir são apresentadas imagens e o resultado obtido em cada uma delas após aplicar a transformada de Walsh.


Resultado1


Resultado2

Conclusões Edit

A transformada estudada possui diversas aplicações práticas que podem ser muito úteis em diversas áreas. A transformada pode ser utilizada para ajudar a otimizar e solicionar diversas funcionalidades importantes existentes atualmente como reconhecimento facil, reconhecimento de caracteres e até mesmo detecção de terremotos. Foi interessante perceber que a função tem aplicações reais e de grande importância.

Referências Edit

[1] CHUANG, Ma-Lung; HUANG, Jun S. Separating similar complex Chinese characters by Walsh transform. 1987.

[2] CLARKE, E. M et al. Spectral Transforms for Large Boolean Functions with Applications to Technology Mapping. 1997. Pittsburgh, PA, USA.

[3] GOFORTH, Tom; HERRIN, Eugene. An automatic seismic signal detection algorithm based on the Walsh transform. 1981. New York, NY, USA.

[4] GONZALEZ, Rafael C.; WOODS, Richard E. Processamento de Imagens Digitais. 2003. Eitora Edgard Blücher. São Paulo, SP, Brasil.

[5] NIXON, Mark S.; JIA, Xiaoguang. Analysing front view face profiles for face recognition via the Walsh transform. 1994. New York, NY, USA.

Anexo Edit

# -*- coding: cp1252 -*-
from Numeric import *
from im import *

def Denary2Binary(n):
    bStr = ''
    if n < 0:  raise ValueError, "must be a positive integer"
    if n == 0: return '0'
    while n > 0:
        bStr = str(n % 2) + bStr
        n = n >> 1
    return bStr

def calcularb( i, j, x, y ):
    tamx    = len(x) - 1
    tamy    = len(y) - 1
    indicex = tamx - i
    indicey = tamy - j
    
    bi   = -1
    bj   = -1
    if ( x == '0' ) or ( x == '1' and indicex > 0 ) or ( indicex < 0 ):
        bi = 0 
    else:
        bi = x[indicex]
        
    if ( y == '0' ) or ( y == '1' and indicey > 0 ) or ( indicey < 0 ): 
        bj = 0
    else:
        bj = y[indicey]

    return bi, bj
        

def potencia( n, i, x, y, u, v ):
    j = n - 1 - i #índice do 2º e 4º b
    bi = 0
    bj = 0
    mult1 = 0
    mult2 = 0
    bi, bj = calcularb( i, j, Denary2Binary(x), Denary2Binary(u) )    
    mult1 =  int(bi)*int(bj)    
    bi, bj = calcularb( i, j, Denary2Binary(y), Denary2Binary(v) )
    mult2 =  int(bi)*int(bj)
    return mult1+mult2


def nucleo( n, i, x, y, u, v ):
    pot = potencia( n, i, x, y, u, v )
    ncl = (-1)**pot
    return ncl

def walsh( f, n, N ):
    ii  = 0
    ncl = 0
    u   = 0
    v   = 0
    lin  = f.shape[0]
    col  = f.shape[1]
    W = zeros((lin,col)) #imagem transformada
    fxyinterno  = 0
    fxyexterno   = 0
    resultnucleo = 0
    for i in range( f.shape[0] ):
        for j in range( f.shape[1] ):
            for a in range( N ):
                for b in range( N ):
                    u = i
                    v = j
                    ncl = nucleo( n, ii, i, j, u, v )
                    #print ncl
                    fxyinterno = 0
                    for ii in range(n):                        
                        resultnucleo = f[a,b]*ncl #faz f(x,y)*cada resultado do núcleo
                        fxyinterno   = fxyinterno + resultnucleo # faz a soma de f(x,y)*nucleo de i=0 até i = n-1
                        #print resultnucleo

                    W[i,j] = fxyinterno/N
                    resultnucleo = 0
    return W


#imagem a ser testada...imagens muito grandes e complexas tornam a execução do código bastante lenta 
f = array([[1,3,5,7,9,6,7,8],[0,2,4,6,8,6,7,8],[1,1,1,1,1,6,7,8],[2,2,2,2,2,6,7,8],[3,3,3,3,3,6,7,8],[1,3,5,7,9,6,7,8],[1,3,5,7,9,6,7,8],[1,3,5,7,9,6,7,8]])
imshow(f);


N = 2**2
print 'N=',N
WW = walsh ( f, 2, N)
imshow(WW)

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.