# Connexions

You are here: Home » Content » The Binary Filter Tree

### Lenses

What is a lens?

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

#### In these lenses

• eScience, eResearch and Computational Problem Solving

This module is included inLens: eScience, eResearch and Computational Problem Solving
By: Jan E. OdegardAs a part of collection: "Image Coding"

Click the "eScience, eResearch and Computational Problem Solving" link to see all content selected in this lens.

### Recently Viewed

This feature requires Javascript to be enabled.

# The Binary Filter Tree

Module by: Nick Kingsbury. E-mail the author

Summary: This module introduces the binary filter tree.

Recall that for image compression (see The 2-band Filter Bank), the purpose of the 2-band filter bank in the Haar transform is to compress most of the signal energy into the low-frequency band.

We may achieve greater compression if the low brand is further split into two. This may be repeated a number of times to give the binary filter tree, shown with 4 levels in Figure 1.

In 1-D, this is analogous to the way the 2-D Haar transform was extended to the multi-level Haar transform.

For an NN-sample input vector xx, the sizes and bandwidths of the signals of the 4-level filter tree are:

Table 1
Signal No. of samples Approximate pass band
xx NN 012 fs 0 1 2 fs
y1 y1 N2 N 2 1412 fs 1 4 1 2 fs
y01 y01 N4 N 4 1814 fs 1 8 1 4 fs
y001 y001 N8 N 8 11618 fs 1 16 1 8 fs
y0001 y0001 N16 N 16 132116 fs 1 32 1 16 fs
y0000 y0000 N16 N 16 0132 fs 0 1 32 fs

Because of the downsampling (decimation) by 2 at each level, the total number of output samples = NN, regardless of the number of levels in the tree.

The H 0 H 0 filter is normally designed to be a lowpass filter with a passband from 0 to approximately 14 1 4 of the input sampling frequency for that stage; and H1 H1 is a highpass (bandpass) filter with a pass band approximately from 14 1 4 to 12 1 2 of the input sampling frequency.

When formed into a 4-level tree, the filter outputs have the approximate pass bands given in Table 1. The final output y0000 y0000 is a lowpass signal, while the other outputs are all bandpass signals, each covering a band of approximately one octave.

An inverse tree, mirroring Figure 1, may be constructed using filters G0 G0 and G1 G1 instead of H0 H0 and H1 H1 , as shown for just one level in part (b) of this figure. If the PR conditions of this previous equation and this previous equation are satisfied, then the output of each level will be identical to the input of the equivalent level in Figure 1, and the final output will be a perfect reconstruction of the input signal.

## Multi-rate filtering theorem

To calculate the impulse and frequency responses for a multistage network with downsampling at each stage, as in Figure 1, we must first derive an important theorem for multirate filters.

### Theorem 1

The downsample-filter-upsample operation of Figure 2(a) is equivalent to either the filter-downsample-upsample operation of Figure 2(b) or the downsample-upsample-filter operation of Figure 2(c), if the filter is changed from Hz H z to Hz2 H z 2 .

#### Proof

From Figure 2(a):

y ^ n={ix(n2i)hi  if  n is even0  if  n is odd y ^ n i x n 2 i h i n is even 0 n is odd
(1)
Take z-transforms:
Y ^ z=n y ^ nzn=even nix(n2i)hizn Y ^ z n y ^ n z n even n i x n 2 i h i z n
(2)
Reverse the order of summation and let m=n2i m n 2 i : therefore,
Y ^ z=ihieven mxmzmz-2i=ihiz-2ieven mxmzm=Hz212(Xz+Xz)=12(Hz2Xz+Hz2Xz)=12(Yz+Yz) Y ^ z i h i even m x m z m z -2 i i h i z -2 i even m x m z m H z 2 1 2 X z X z 1 2 H z 2 X z H z 2 X z 1 2 Y z Y z
(3)
where Yz=Hz2Xz Y z H z 2 X z

This describes the operations of Figure 2(b). Hence the first result is proved.

The result from line 3 in Equation 3

Y ^ z=12(Xz+Xz)Hz2= X ^ zHz2 Y ^ z 1 2 X z X z H z 2 X ^ z H z 2
(4)
shows that the filter Hz2 H z 2 may be placed after the down/up-sampler as in Figure 2(c), which proves the second result.

## General results for M:1 subsampling

It can be shown that:

• Hz H z becomes HzM H z M if shifted ahead of an M:1 downsampler or following an M:1 upsampler.
• M:1 down/up-sampling of a signal Xz X z produces:
X ^ z=1Mm=0M1Xzei2πmM X ^ z 1 M m 0 M 1 X z 2 m M
(5)

## Transformation of the filter tree

Using the result of Equation 3, Figure 1 can be redrawn as in Figure 3 with all downsamplers moved to the outputs. (Note Figure 3 requires much more computation than Figure 1.)

We can now calculate the transfer function to each output (before the downsamplers) as:

H01 z= H0 z H1 z2 H01 z H0 z H1 z 2
(6)
H001 z= H0 z H0 z2 H1 z4 H001 z H0 z H0 z 2 H1 z 4
(7)
H0001 z= H0 z H0 z2 H0 z4 H1 z8 H0001 z H0 z H0 z 2 H0 z 4 H1 z 8
(8)
H0000 z= H0 z H0 z2 H0 z4 H0 z8 H0000 z H0 z H0 z 2 H0 z 4 H0 z 8
(9)
In general the transfer functions to the two outputs at level kk of the tree are given by:
H k , 1 =i=0k2 H0 z2i H1 z2k1 H k , 1 i 0 k 2 H0 z 2 i H1 z 2 k 1
(10)
H k , 0 =i=0k1 H0 z2i H k , 0 i 0 k 1 H0 z 2 i
(11)
For the Haar filters of this equation and this equation from our discussion of the 2-band filter bank, the transfer functions to the outputs of the 4-level tree become:
H01 z=12(z-3+z-2z-1+1) H01 z 1 2 z -3 z -2 z -1 1
(12)
H001 z=12×2(z-7+z-6+z-5+z-4z-3+z-2+z-1+1) H001 z 1 2 2 z -7 z -6 z -5 z -4 z -3 z -2 z -1 1
(13)
H0001 z=14(z-15+z-14+z-13+z-12+z-11+z-10+z-9+z-8z-7+z-6+z-5+z-4+z-3+z-2+z-1+1) H0001 z 1 4 z -15 z -14 z -13 z -12 z -11 z -10 z -9 z -8 z -7 z -6 z -5 z -4 z -3 z -2 z -1 1
(14)
H0000 z=14(z-15+z-14+z-13+z-12+z-11+z-10+z-9+z-8+z-7+z-6+z-5+z-4+z-3+z-2+z-1+1) H0000 z 1 4 z -15 z -14 z -13 z -12 z -11 z -10 z -9 z -8 z -7 z -6 z -5 z -4 z -3 z -2 z -1 1
(15)

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks