Block transform

Block Bases

Block orthonormal bases are obtained by dividing the time axis in consecutive intervals [ a p , a p + 1 ] with

lim p → − ∞ a p = − ∞ and lim p → ∞ a p = ∞ .

The size l p = a p + 1 − a p of each interval is arbitrary. Let g = 1 [ 0 , 1 ] . An interval is covered by the dilated rectangular window

g p ( t ) = 1 [ a p , a p + 1 ] ( t ) = g ( t − a p l p ) .

Theorem 1. constructs a block orthogonal basis of L 2 ( R ) from a single orthonormal basis of L 2 [ 0 , 1 ] .

Theorem 1.

if { e k } k ∈ Z is an orthonormal basis of L 2 [ 0 , 1 ] , then

{ g p , k ( t ) = g p ( t ) 1 l p e k ( t − a p l p ) } ( p , k ) ∈ Z

is a block orthonormal basis of L 2 ( R )

Proof

One can verify that the dilated and translated family

{ 1 l p e k ( t − a p l p ) } ( p , k ) ∈ Z

is an orthonormal basis of L 2 [ a p , a p + 1 ] . If p ≠ q , then ⟨ g p , k , g q , k ⟩ = 0 since their supports do not overlap. Thus, the family { g p , k ( t ) = g p ( t ) 1 l p e k ( t − a p l p ) } ( p , k ) ∈ Z is orthonormal. To expand a signal f in this family, it is decomposed as a sum of separate blocks

f ( t ) = ∑ p = − ∞ + ∞ f ( t ) g p ( t ) ,

and each block f ( t ) g p ( t ) is decomposed in the basis { 1 l p e k ( t − a p l p ) } ( p , k ) ∈ Z

Block Fourier Basis

A block basis is constructed with the Fourier basis of L 2 [ 0 , 1 ] :

{ e k ( t ) = e x p ( i 2 k π t ) } k ∈ Z

The time support of each block Fourier vector g p , k is [ a p , a p + 1 ] of size l p . The Fourier transform of g = 1 [ 0 , 1 ] is

g ^ ( w ) = sin ⁡ ( w / 2 ) w / 2 e x p ( i w 2 )

and

g ^ p , k ( w ) = l p g ^ ( l p w − 2 k π ) e x p ( − i 2 π k a p l P ) .

It is centered at 2 k π l p − 1 and has a slow asymptotic decay proportional to l p − 1 | w | − 1 . Because of this poor frequency localization, even though a signal f is smooth, its decomposition in a block Fourier basis may include large high-frequency coefficients. This can also be interpreted as an effect of periodization.

Discrete Block Bases

For all p ∈ Z , we suppose that a p ∈ Z . Discrete block bases are built with discrete rectangular windows having supports on intervals [ a p , a p − 1 ] :

g p [ n ] = 1 [ a p , a p + 1 − 1 ] ( n ) .

Since dilations are not defined in a discrete framework,we generally cannot derive bases of intervals of varying sizes from a single basis. Thus,Theorem 2. supposes that we can construct an orthonormal basis of C l for any l > 0 . The proof is straightforward.

Theorem 2.

Suppose that { e k , l } 0 ⩽ k < l is an orthogonal basis of C l for any l > 0 . The family

{ g p , k [ n ] = g p [ n ] e k , l p [ n − a p ] } 0 ⩽ k < l p , p ∈ Z

is a block orthonormal basis of l 2 ( Z ) .

A discrete block basis is constructed with discrete Fourier bases

{ e k , l [ n ] = 1 l e x p ( i 2 π k n l ) } 0 ⩽ k < l

The resulting block Fourier vectors g p , k have sharp transitions at the window border, and thus are not well localized in frequency. As in the continuous case, the decomposition of smooth signals f may produce large-amplitude, high-frequency coefficients because of border effects.

Block Bases of Images

General block bases of images are constructed by partitioning the plane R 2 into rectangles { [ a p , b p ] × [ c p , d p ] } p ∈ Z of arbitrary length l p = b p − a p and width w p = d p − c p . Let { e k } k ∈ Z be an orthonormal basis of L 2 [ 0 , 1 ] and g = 1 [ 0 , 1 ] . We denote

g p , k , j ( x , y ) = g ( x − a p l p ) g ( y − c p w p ) 1 l p w p e k ( x − a p l p ) e j ( y − c p w p ) .

The family { g p , k , j } ( p , k , j ) ∈ Z 3 is an orthonormal basis of L 2 ( R 2 ) .

For discrete images,we define discrete windows that cover each rectangle

g p = 1 [ a p , b p − 1 ] × [ c p , d p − 1 ] .

If { e k , l } 0 ⩽ k < l is an orthogonal basis of C l for any l > 0 , then

{ g p , k , j [ n 1 , n 2 ] = g p [ n 1 , n 2 ] e k , l p [ n 1 − a p ] e j , w p [ n 2 − c p ] } ( k , j , p ) ∈ ( Z ) 3

is a block basis of l 2 ( R 2 )