Amostras não Uniformes e Reconstrução em Espaços de Translações
20 pág.

Amostras não Uniformes e Reconstrução em Espaços de Translações

Disciplina:matemática aplicada938 materiais13.699 seguidores
Pré-visualização3 páginas
somente as componentes m tais que m = m′N .

Exemplo 1. Considere o spline cu´bico

φ(t) =




2
3
− |t|2 + |t|3

2
, 0 < |t| < 1

(2−|t|)3

6
, 1 ≤ |t| < 2

0, |t| ≥ 2
Sejam L = 3, M = 3 e N = 3. Vamos determinar

f(t) = c0φ(t) + c1φ(t−m) + c2φ(t− 2m),

que satisfaz (
f(2

1

3
), f(4

1

3
), f(8

1

3
))

)
= (2

√
3, 2 + 2

√
3, 2− 2

√
3).

Neste caso Λ = {2, 4, 8}. Assim a matriz A e´ dada pelos elementos das linhas 3, 5 e 9 e
das colunas 1, 4 e 7 da matriz



2
3

31
54

10
27

1
6

4
81

1
162

0 0 0 0

31
54

2
3

31
54

10
27

1
6

4
81

1
162

0 0 0

10
27

31
54

2
3

31
54

10
27

1
6

4
81

1
162

0 0

1
6

10
27

31
54

2
3

31
54

10
27

1
6

4
81

1
162

0

4
81

1
6

10
27

31
54

2
3

31
54

10
27

1
6

4
81

1
162

1
162

4
81

1
6

10
27

31
54

2
3

31
54

10
27

1
6

4
81

0 1
162

4
81

1
6

10
27

31
54

2
3

31
54

10
27

1
6

0 0 1
162

4
81

1
6

10
27

31
54

2
3

31
54

10
27

0 0 0 1
162

4
81

1
6

10
27

31
54

2
3

31
54

0 0 0 0 1
162

4
81

1
6

10
27

31
54

2
3




29 de novembro de 2006 Reginaldo J. Santos

10 2 AMOSTRAS NA˜O UNIFORMES DE SINAIS

ou seja, os coeficientes sa˜o a soluc¸a˜o do sistema




10
27

31
54

4
81

4
81

31
54

10
27

0 1
162

10
27





 c0c1

c2


 =


 2

√
3

2 + 2
√

3

2− 2√3




cuja soluc¸a˜o e´ 
 c0c1

c2


 =


 −10.402213.1042

−4.1715




−0.5 0 0.5 1 1.5 2 2.5 3
−6

−4

−2

0

2

4

6

8

t

y

Figura 1: 3 Pontos com espac¸amento na˜o uniforme e o sinal recuperado do Exemplo 1.

Amostras na˜o Uniformes e Reconst. em Esp. de Translac¸o˜es 29 de novembro de 2006

11

3 Convoluc¸a˜o em Dimensa˜o 2

Definimos a convoluc¸a˜o de duas matrizes X, Y , N1 ×N2, por

(X ∗ Y )mn =
N1−1∑
m′=0

N2−1∑
n′=0

Xext(m−m′)(n−n′)ym′n′,

em que Xext e´ a extensa˜o perio´dica da matriz X ao espac¸o das matrizes

(2N1 − 1)× (2N2 − 1), ou seja,
Xext = (xmn)m=1,...,N1−1,0,1,...,N1−1;n=1,...,N2−1,0,1,...,N2−1.

Usando matrizes a convoluc¸a˜o de duas matrizes X e Y , N1 ×N2, pode ser escrita
como

vet(X ∗ Y ) = bccb(X) vet(Y ),
em que

bccb(X) =




C0 CN1−1 . . . C1
C1 C0 . . . C2
...

...
...

CN1−1 CN1−2 . . . C0


 e

Ck = circulant(xk,.) =




xk0 xk(N2−1) . . . xk1
xk1 xk0 . . . xk2
...

...
...

xk(N2−1) xk(N2−2) . . . xk0




A matriz bccb(X) e´ chamada matriz circulante em blocos com blocos circulan-

tes (BCCB).

Proposic¸a˜o 4. Sejam X e Y matrizes N1 ×N2. A convoluc¸a˜o vet(X ∗ Y ) e´ igual ao
vetor obtido multiplicando as componentes correspondentes das transformadas de Fourier

discreta de dimensa˜o 2 de X e de Y e depois aplicando-se a transformada discreta de

Fourier inversa de dimensa˜o 2. Em termos de matrizes temos

vet(X∗Y ) = bccb(X)Y = 1
N1N2

(FN1⊗FN2)t diag((FN1⊗FN2) vet(X))(FN1⊗FN2) vet(Y ).

29 de novembro de 2006 Reginaldo J. Santos

12 3 CONVOLUC¸A˜O EM DIMENSA˜O 2

Demonstrac¸a˜o. Escrevendo

vet(X) =

N1−1∑
m=0

N2−1∑
n=0

cmnF
N1×N2
mn e vet(Y ) =

N1−1∑
m′=0

N2−1∑
n′=0

dm′n′F
N1×N2
m′n′

em termos da base de Fourier temos que

vet(X ∗ Y ) =
N1−1∑
m=0

N2−1∑
n=0

N1−1∑
m′=0

N2−1∑
n′=0

cmndm′n′(F
N1×N2
mn ∗ F N1×N2m′n′ ) (4)

Mas,

(F N1×N2mn ∗ F N1×N2m′n′ )kl =
N1−1∑
k′=0

N2−1∑
l′=0

e
i2pi

(
m(k−k′)

N1
+

n(l−l′)
N2

)
e

i2pi
(

m
′
k
′

N1
+n

′
l
′

N2

)

= e
i2pi

(
mk

N1
+ nl

N2

) N1−1∑
k′=0

N2−1∑
l′=0

e
i2pi

(
k
′(m′−m)

N1
+ l

′(n′−n)
N2

)

Assim,

F N1×N2mn ∗ F N1×N2m′n′ = N1N2δmm′δnn′F N1×N2mn (5)
Substituindo-se (5) em (4) obtemos

X ∗ Y =
N1−1∑
m=0

N2−1∑
n=0

N1N2cmndmnF
N1×N2
mn .

Logo a transformada de Fourier discreta de dimensa˜o 2 de X ∗ Y e´ dada por

(FN1 ⊗ FN2)(X ∗ Y ) = N21 N22 (cmndmn)

Assim, como a transformada de Fourier discreta de dimensa˜o 2 de X e Y sa˜o dadas por

mat((FN1 ⊗ FN2) vet(X)) = N1N2(cmn) e mat((FN1 ⊗ FN2) vet(Y )) = N1N2(dmn),

enta˜o

(FN1 ⊗ FN2) vet(X ∗ Y ) = diag((FN1 ⊗ FN2) vet(X))(FN1 ⊗ FN2) vet(Y ).

Aplicando-se (FN1 ⊗ FN2)−1 = 1N1N2 F
t

N1
⊗ F tN2 obtemos

vet(X∗Y ) = bccb(X)Y = 1
N1N2

(FN1⊗FN2)t diag((FN1⊗FN2) vet(X))(FN1⊗FN2) vet(Y ).

Amostras na˜o Uniformes e Reconst. em Esp. de Translac¸o˜es 29 de novembro de 2006

13

Corola´rio 5. Seja X = (xmn) uma matriz N1 ×N2.

bccb(X) =
1

N1N2
(FN1 ⊗ FN2)t diag((FN1 ⊗ FN2) vet(X))(FN1 ⊗ FN2).

Portanto bccb(X) e´ diagonaliza´vel, seus autovalores sa˜o as componentes da transformada

de Fourier discreta de dimensa˜o 2 de X com autovetores F N1×N2mn , m = 0, . . . , N1 − 1;
n = 0, . . . , N2 − 1.

Observac¸a˜o. Produto matriz BCCB por vetor pode ser calculado ao custo de

N1N2 log(N1N2) operac¸o˜es usando FFT. Tambe´m sistemas em que a matriz e´ BCCB

podem ser resolvido ao custo de N1N2 log(N1N2) operac¸o˜es, pois

(bccb(X))−1 =
1

N1N2
(FN1 ⊗ FN2)t[diag((FN1 ⊗ FN2) vet(X))]−1(FN1 ⊗ FN2).

Definimos a convoluc¸a˜o de duas matrizes X, (2N1 − 1)× (2N2 − 1), e Y , N1×N2,
por

(X ∗ Y )mn =
N1−1∑
m′=0

N2−1∑
n′=0

X(m−m′)(n−n′)ym′n′.

Usando matrizes a convoluc¸a˜o de duas matrizes X, (2N1 − 1)× (2N2 − 1), e Y , N1 ×
N2, pode ser escrita como

vet(X ∗ Y ) = bttb(X) vet(Y ),

em que

bttb(X) =




T0 T−1 . . . T1−N1
T1 T0 . . . T2−N1
...

...
...

TN1−1 TN1−2 . . . T0


 e

29 de novembro de 2006 Reginaldo J. Santos

14 3 CONVOLUC¸A˜O EM DIMENSA˜O 2

Tk = toeplitz(xk,.) =




xk0 xk(−1) . . . xk(1−N2)
xk1 xk0 . . . xk(2−N2)
...

...
...

xk(N2−1) xk(N2−2) . . . xk0




A matriz bttb(X) e´ chamada matriz Toeplitz em blocos com blocos Toeplitz

(BTTB).

Vamos completar a matriz X com elementos quaisquer (por exemplo zeros) acima e a`

esquerda de forma a obter uma matriz 2N1×2N2 e vamos dividi-la em quatro submatrizes
de mesmo tamanho: [

0 0¯
0¯ X

]
2N1×2N2

=

[
X11 X12
X21 X22

]
,

Vamos estender a matriz acima de forma que seja perio´dica da seguinte forma

X˜ext =




X22 X21 X22 X21
X12 X11 X12 X11
X22 X21 X22 X21
X12 X11 X12 X11




Usando a Proposic¸a˜o 4 na pa´gina 11 temos o seguinte resultado.

Amostras na˜o Uniformes e Reconst. em Esp. de Translac¸o˜es 29 de novembro de 2006

15

Proposic¸a˜o 6. Sejam X, (2N1 − 1)× (2N2 − 1), e Y , N1 × N2. A convoluc¸a˜o X ∗ Y e´
igual a matriz obtida da seguinte forma:

(a) Complete a matriz X com elementos quaisquer (por exemplo zeros) acima e a` es-

querda de forma a obter uma matriz 2N1 × 2N2 e divida-a em quatro submatrizes
de mesmo tamanho: [

0 0¯
0¯ X

]
2N1×2N2

=

[
X11 X12
X21 X22

]
,

(b) Defina

X˜ =

[
X22 X21
X12 X11

]
e Y˜ =

[
Y 0¯
0¯ 0¯

]
2N1×2N2

.

(c) Multiplique as componentes correspondentes das transformadas de Fourier discreta

de X˜ e de Y˜ .

(d) Aplique a transformada discreta de Fourier inversa e toma-se a submatriz N1 ×N2
obtida com os elementos do canto superior esquerdo.

Comando do pacote SINAIMAG:

Z=prodbttb(X,Y) calcula o produto bttb(X) Y para X uma matriz (2N1− 1)× (2N2− 1)
e Y uma matriz N1 ×N2.

29 de novembro de 2006 Reginaldo J. Santos

16 4 AMOSTRAS NA˜O UNIFORMES DE IMAGENS

4 Amostras na˜o Uniformes de Imagens

Vamos considerar uma func¸a˜o de duas varia´veis f : [0, N1]× [0, N2] → R da forma

f(x, y) =

M1−1∑
m=0

M2−1∑
n=0

cmnφ

(
x

a1
−m, y

a2
− n

)
,

para a1, a2 inteiros positivos e φ(x, y) uma func¸a˜o dada. Vamos supor que temos uma

amostra na˜o uniforme da func¸a˜o f

{f(x1, y1), f (x2, y2) , . . . , f (xr, yr)} ,

para Λ = {(x1, y1), (x2, y2), . . . , (xr, yr)} um subconjunto de

{(0, 0), (0, 1), . . . , (0, N2 − 1), . . . , (N1 − 1, 0), . . . , (N1 − 1, N2 − 1)} .

Vamos supor que r ≥ M1M2.
Substituindo-se f nos pontos (xk, yk), para k = 1, . . . , r, obtemos

f(xk, yk) =

M1−1∑
m=0

M2−1∑
n=0

cmnφ

(
xk

a1
−m, yk

a2
− n

)
para k = 1, . . . , r (6)

Para encontrarmos cmn precisamos resolver o sistema linear AX = B, em que

A =

(
φ

(
xk

a1
−m, yk

a2
− n

))
r×M1M2

, B = vet(f(xk, yk)) e

X = vet(cmn) ∈ RM1M2 .
Podemos escrever (6) da seguinte forma

f(xk, yk) =

M1−1∑
m=0

M2−1∑
n=0

cmn↑a1a2φ

(
xk −m

a1
,
yk − n

a2

)
para k = 1, . . . , r

em que

cmn↑a1a2 =

{
cm′n′, se m = a1m

′, n = a2n
′

0, caso contra´rio.

Observe que a matriz A e´ uma submatriz de