Fandom

Students

LAPIS/Disciplinas/Processamento de Imagens:TransfWalsh

< LAPIS | Disciplinas

1,331pages on
this wiki
Add New Page
Talk0 Share

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.

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)

Also on Fandom

Random Wiki