リフティングウェーブレットによる信号と画像の抽出

(1)

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

リフティングウェーブレットによる信号と画像の抽出

高野, 茂

Graduate School of Information Science and Electrical Engineering, Kyushu University

(2)

(3)

Signal and Image Extraction by Lifting Wavelets

February 2001

(4)

Abstract

Internet has enabled us to access huge digital signal and image databases easily. It is very important to search such databases for desired signals and images fast on Internet.

So far, many signal and image retrieval systems have been developed. However, almost all retrieval systems d pend on keyword indexing which must be done by human hands as a preprocessing. We have another type of retrieval systems that are called retrieval by contents. These retrieval systems do not require keyword indexing. Such retrieval systems should posses an ability to extract parts of signal and image. For the extraction of subsignal and subimag s, w ne d to d teet similar signal and images to query ones from time eries and a r fer n im g . A t mplate matching technique, which is a typical matching m thod for ignal and im ge ften used for the det ction of su bsignals and subimag s. How ver his t hniqu n cds lot of computational efforts and does not have robustness in d tccti n.

The concern with the application of wavelet theory to signal and image analysis has been growing for the la t several years. Wavelet transform i a useful tool for various signal and image processing application such a signal and image compression, edge detection, computer vision and so on. JPEG2000, which is a next generation image compression format, has been constructed ba ed on wavelet theory.

In this thesis, we propose several learning and extraction methods for signal and image based on lifting wavelet transforms. The lifting wavelet transform includes free parameters that are adjustable adaptive to signals and images. Our idea is to learn these parameters so that they have some char act ristics of query of signals and images. Concretely we learn the parameters so as to vanish large high frequency components of the training signals and images. The extraction of subsignals and subimages is done by applying the learnt lifting wavelet transforms to reference signals and images.

(5)

Acknow ledgrnents

I am extremely thankful to my supervisor, Prof. Koichi Niijima for giving me contin

uous and valuable advice throughout my doctoral research with devotion and patience.

I would also like to thank Prof. Setsuo Arikawa and Prof. Fumihiro Matsuo for their valuable and adequate comments, of many occasions.

I appreciate the support of the Department of Informatics. The pleasant environment of the department and the cooperation of the teaching faculty and staff helped me a lot to promote my research.

F inally, I would like to xt nd my gratitude for support and encouragements to my parents.

(6)

Detection of geomagnetic sudden commencements (SC)

4.1 What is SC? . . . . . 4.2 Automatic detection of SC

Geomagnetic horizontal

(

H

)

component data .

Detection of SC by real-type lifting wavelet transforms

38 38 41 41 41 4.2.1

4.2.2 4.2.3 4.2.4

Detection of SC by integer-type Haar dual lifting wavelet transforms 50 Conclusion . . . 57

5

Learning and extraction theory for images

⁵⁹

5.1 L arning and extraction th ory of real-typ lifting wavelet transforms 59 5.1.1 Learning of r al-t p lifting wavelet transforms

5.1.2 Extraction by r al-t pe lifting wavel t tran form

59 64 5.2 Learning and extra tion theory of integer-typ Haar lifting wav let transforms 66

5.2.1 5.2.2

Learning of int er-t pe Haar lifting wavel t transform . . Extraction by integer-typ Haar lifting wav let transforms

5.3 Learning and extraction heory of integer-type Haar dual lifting wavelet transforms . . .

.

66 70

71 5.3.1 Learning of integer-typ Haar dual lifting wavel t transforms 72 5.3.2 Extraction by int ger-typ Haar dual lifting wavelet transforms 74

6

Extraction of subimages

6.1 Facial image extraction by high frequency components

76 77 6.2 Facial image extraction by real-type lifting wavelet transforms 78

(8)

7 General conclusion 91

(9)

Chapter 1 Introduction

By th rapid progres of Intern t w hav been able to get asily digital signals and images from huge databa es on Int rn t. Therefore, it is important to develop signal and image retrieval systems for finding requir d . ignal and images fast from such databases. Almost all current signal and imag r tri val y. t ms depend on k yword ind xing. Recently, retrieval of ignal and imag , b nt nt ha been focused which does not need labeling by human hands

[7 14 22 27].

u h a method r quir s th extraction of particular

components from a time series signal and an image. So far template matching methods have been used for detecting the target signal and image from the reference ones. In the template matching process, th amount of computation is proportional to the product of the size of a template query and original data. Therefore, this process needs a lot of time when the size of each of ignal and imag i very large.

Recently, wavelet th ory develop d by Moret

[13]

has been successfully used in various signal and image processing applications

[2, 6, 10, 17, 19, 21, 29].

Particularly, it has proved to be a powerful tool for various data compression applications

[1, 8, 16 30].

(10)

signal and image.

In this thesis, we propose a method for the extraction of particular component from a time series signal, and target subimage from a large reference image, which is based on a lifting wavelet theory. The lifting wavelet transform is biorthogonal wavelet with controllable free parameters, which was developed by Sweldens

[18].

The lifting wavelets can be designed by adapting the original signal and image, which are called second gen

eration wavelets. We cause the fr e parameters to learn the feature of required signals and images, and we construct new wavel t transforms containing th e learnt param ters.

Applying the learnt lifting wavelet tr n forms to the unknown signal and image, th tar

get signal and image can b xtra t d from the original ones. Recently such techniques were used to design lifting wav l t filt r for the compre sion of the electrocardiogram signal

[9]

but this t chniqu i no on rned with signal and image detection. There ar two typ of tran form in lif in w v let real-type and int ger-type. The former transform map r al to r al f r ignal and image component , and when input data consists of sequ nces of integers, th re ulting transformed outputs no longer consist of integers. The integer-typ lifting wavelet transforms map integers to integers, which are important for lossless r pr s ntations

[3].

This thesis propos s a learning theory of these two kinds of lifting wav 1 t transform and an extraction method for the particular signal and image by using the learnt transforms. We construct new int ger-type lifting wavelet transforms based on Haar wavelet transform, and prove that these transforms are invert

ible

[24, 26].

In the learning of fre parameters included in our integer-type Haar lifting transforms a condition for determining such parameters is inequality. Therefore, we can realise the robust learning and xtracting for the input training signals and images. This thesis mainly stresses on this robustness.

Now we describe outline of each chapter in more detail. In Chapter

2,

we g1ve a

(11)

brief review of the first and s cond generation wavelets. At first, we introduce how to construct the biorthogonal wavel t filters which give rise to fir t generation wavelets.

Wavelet decomposition and reconstruction formulae are constructed by using the set of biorthogonal wavelet filters. Then we pr sent Haar wavelet and convolution-type wavelet

[

¹⁵

]

as two typical examples of first generation wavelets. In Section 2.2, we explain the real-type lifting, integer-type Haar lifting and dual lifting wavelet transforms as the second generation wavelets. And then, we prove that the integer-type Haar lifting and dual lifting wavelet transform are inv rtibl transforms.

In Chapter 3 we d v lop two m thods for learning and detecting target points from unknown signals by u ing th real-typ and integer-type lifting wavelet transforms. First, a learning method for the r al-typ lifting wavelet transform using training signals which contain target points ha b n de rib d. Free parameter in th lifting scheme are tuned so that th d compo high frcqu ncy mponent around the targ t points are vanished.

The detail of learning i pr rn t d in S ti n 3 .1.1. In S ction 3 .1. 2 a detection m thod has been described which u es th real-type learnt wavel t transform by the learning technique of the previous section. Section 3.2 extends the learning and detecting method using the integer-type Haar lifting wavel t transform. In Section 3.2.1, to learn and detect robustly for noise the parameters in the integer-type Haar dual lifting wavelet transform are determined to have some feature of training signals using the condition in the form of inequality. The detection method by the learnt transform has be n detailed in Section 3.2.2.

In Chapter 4, we show that our 1 arning and detecting theory is very useful for auto

(12)

teet automatically SCs from these H-components data at Kakioka, Honolulu, Hermanus and San Juan stations.

In Chapter

5,

we propose three algorithms each for learning the feature of training images and extracting target subimages from a large reference image by using real-type lifting, integer-type Haar lifting and dual lifting wavelet transforms. Learning method de

termines free parameters in the lifting or dual lifting wavelet transform using the training images. In Section

5.1.1,

th learning m thod for images using the real-type lifting wavelet transforms has been giv n

[23, 25].

Th parameter in the real-type lifting scheme are determined so that two high fr qu ncy omponents in vertical and horizontal directions, of the training imag ar vani h ur learning method computes these parameters fast by solving simultan ous lin ar equations. The learnt param t rs have the feature of the target subimages. In S ction

5.1.2,

th extraction m thod for imag s by applying a wavel t transform containing uch para1net rs to th r f r nee image ha been explained

[24].

Also it is check d wh th r th high frequency components are vanished or not, to detect the target subimage . S ction

5.2

extends our l arning and extraction theory for integer-type lifting wav l t tran form . In Section

5.2.1,

the parameters have been computed so that two types of low fr qu ncy components, in v rtical and horizontal di

rections of the training images are liminat d. These parameters are d termined to have the robustness for the training imag s by minimizing the energy subject to the vanishing condition in the form of inequality. Then the extraction algorithm by the learnt integer

type Haar lifting wavelet transforms has been explained in Section

5.2.2.

In Section

5.3,

we give the learning and extraction methods by using the integer-type Haar dual lifting wavelet transforms in th same way as in Section

5.2

except for the learning of param ters

[26].

Chapter

6

is devoted to show simulation results of subimage extraction. In all simu-

(13)

lations, it has been tried to xtract facial parts from a snapshot. Chapter 7 is the closing chapter with concluding remarks and plans for future work.

(14)

Chapter 2 Lifting wavelets

Wavelets are a very useful tool for r pre nting general functions or data sets. Therefore, wavelets have been u e in a lot of ar uch as mathematics, engineering, computer scienc , statistic , physi s etc. Wav l t fun tions are traditionally defined as the dyadic translates and dilates of one parti ular func ion which b long to a quare integrable function space on real numb r ^. u h wavelets are a type of discrete wavelets and are derived from di cr te aling fun tion . Th se wavelets ar oft n called first generation wavelets. One of the most important prop rties of discret wavelets is multiresolution analysis develop d by Mallat

[11, 12).

In multiresolution framework, Mallat d rived fast transforms that decompose a signal into low frequency components and high frequency components and conversely, recon

struct the original signal from th e components. Such tran forms contain only coefficients of discrete scaling and wavelet functions. These coefficients are frequently called scaling and wavelet filters, which are usually biorthogonal filters.

Sweldens developed a simple construction of wavelets that are not translates and di

lates of each other but still preserve all the powerful propertie of first generation wavelets

[18).

These wavelets are referred to as second generation wavelets. The second g neration

wavelet filters are constructed only by lifting the set of the biorthogonal filter . Thes

(15)

new wavelet filters are called lifting wavelet filters.

In this chapter, we describe general theory of first and second generation wavelets.

In the beginning, we show how to construct the biorthogonal wavelet filters for first generation wavelets. Wavelet decomposition and reconstruction formulae for signals and images are constructed by using the set of biorthogonal wavelet filters. We present Haar wavelet and convolution-type wavelet as two typical examples of first generation wavelets.

Then, we explain the lifting wav l ts which are biorthogonal wavelets with controllable free param ters. Lastly w prove that the integer-type Haar lifting and dual lifting wavelets have decomposition and r con truction formulae.

2.1 First generation wavelets 2.1.1 Biorthogonal wavelet filters

Let Z be a set of int g rs and

L2 (R)

a pace of square integrable functions on th real lineR. W start with a t of scaling functions

{¢j,k

(2.3),

we can apply the Hilbert d composition th or m to g t

(2.4)

where

Wj

i a complement spa of

Vj

and

Vj

is orthogonal to

Wj

in the sense that any function f in

wj

satisfie

can be written as

m m

(2.5)

(2.6)

The function

'1/Jj,m(x)

is known as a wavelet basis function or simply wavelet. Due to

(2.5),

the wavelet functions

'1/Jj,m (

x

)

satisfy

(2.7)

(17)

To introduce biorthogonal functions for

'1/Jj,m (x),

let the dual scaling functions

¢j,k (x)

satisfy a two-scale relation

(2.8)

where

hk,l

are two-scale coefficients. Since the inclusion

"Yj

^C

"Yj+1

holds by virtue of the two-scale relation

(2.8)

we can decompose

Vj+1

as

- - -

Vj+l

=

Vj

^EB

wj,

where

wj

is a complement pace of

"Yj

and

"Yj

is orthogonal to

wj

in the sense that any function f in

wj

satisfies

<

J cPj,m'

>=

0. (2.9)

The space

wj

has the ba i fun tion

-j,m (

X

)

of the form

By the inclusion

Wj

^c

"Yj+1, ;f;j,m(x)

can be expanded as

J;j,m(x)

=

� 9m,l¢j+l,l(x). (2.10)

l

Due to

(2.9),

the basis functions

;f;j,m(x)

satisfy

<

'1/Jj,m cPj,k

^>=

0. (2.11)

Furthermore, it is easy to show that the dual basis functions

{/;j' ,m' (x)

are biorthogonal to the wavelet functions

'1/Jj,m(x),

that is,

(18)

5k,k'

<

L hk,l¢j+l,l, L 'hk',l'¢j+l,l'

^>

l l'

L hk,l L 'hk',l'

^<

¢j+l,l, ¢j+l,l'

^>

l l'

L hk,l'hk',l·

l

Next,

(2.6), (2.10)

^and

(2.12)

^give

Likewis

, (2.7)

^and

(2.11)

^yield

l

0,

5mm' , · (2.13)

These are called biorthogonal conditions. From now on w call a set of coefficients

{ hk,l, hk,l, gm,l, ?lm,t}

satisfying th conditions

(2.13),

biorthogonal wavelet filters.

2.1.2 Wavelet decomposition and reconstruction formulae for signals

Let f(x) be a signal in the space

Vj+l·

Then f(x) can be expanded using the basis of

(2.14)

where

(19)

On th other hand, the decomposition relation

(2.4)

implies that

f(x)

can be expres ed as

(2.15)

From

(2.14)

_and

(2.15),

_{we have}

Lcf+1¢j+l,i(x)

⁼

Lci¢j,i(x)

⁺

Ldil/Jj,i(x). ^(2.16) i

The d composition formula for

q+1

are d riv d as follows: Multiplying both sides of

(2.16)

by the function

J;j,k (x)

and integrating the resulting equation, we have

L cf+l

<

¢j+l,i, J;j,k

^>=

L ci

<

¢j,i, J;j,k

^{> +}

L d{

<

1/Jj,i, J;j,k

^>^.

i

The left hand side is equal to

Lt hk,lc{+1

b au of

(2. 3)

_and

(2.8).

The right hand side is equal to

cJc

by virtue of

(2.3)

_and

(2. 7).

Ther fore we can g t

(2.17)

Next, multiplying both id of

(2.16)

by the function

�j,m (x)

and integrating the resulting equation give

for the sam reason as above.

dj

"" - _i+l

m = � 9m

,l

^C{,

^(2.18)

l

The relations

(2.17)

_and

(2. 18)

are called the decomposition formulae of

q+1,

whereas

hk,l

and 9m,l ar termed as lowpass and highpass filters, respectively. We call

c{

^low

frequency components, and

dfn

high frequency components of

c{+1.

q+1 d:tn.

(20)

This is called the reconstruction formula, where hk,l and 9m,l ar reconstruction filters.

The formulae (2.17), (2.18) and (2.19) imply that the coefficients c{+1 are equivalent to { c{, ^d�}. Although cf+1 do not represent signal f (

x

) exactly, we will assume cf+1 to be a signal from now on.

- ... - - -

Here we introduce four operators H, G, H and G, such that b = H a ,

c

= G a ,

b

= Ha

and

^c

= _G a . More explicitly

bk = � hk,tat, l

bk = � hk,lat, l

Cm = � ?Jm,lal, l

Cm = �9m,lal.

l

These are referred as filt r op rator . fi and G are lowpass and highpass decomposition

filter op rators, respectively wher asH and G are reconstruction filter operators. Fig.2.1

illustrates wavelet decompo ition and re on truction algorithms.

(21)

c 1

-

G

c 0

- -

H G

c -1

- -

H G

c -2

CD

downsampling H ^-

-

G

-

H Wavel t d composition algorithm

CD

upsampling G

c 1

(22)

2.1.3 Wavelet decomposition and reconstruction formulae for Images

To simplify the onward discussion, we concentrate only on wavelet decomposition from level 1 to 0 and wavelet reconstruction only from level 0 to 1.

Let

f(x, y)

represent an image in

V1

®

V1,

where

i,j

Then

f(x, y)

can be expr ^s d a

f(x y)

=

L Cl,jch,i(Y)¢h,j(x), i,j

where

i,j

(2.20)

The indices i and j are th lo ation in verti al and horizontal directions, respectively.

As

(Vo

EB

Wo)

®

(Vo

EB

Wo)

f(x, y)

i j

From (2.20) and (2.21), we have

L Cl,jcih,i(Y )¢1,j (x) i,j

i,j i,j

(23)

The decomposition formulae are derived as follows: Multiplying both sides of

(2.22)

^by

the

¢o,k (y) ¢o,k' ( x)

and integrating the resulting equation with respect to

y

and

x,

we have

L Cl,j

<

cfh,i, ¢o,k

> <

c/h,j, ¢o,k'

>

i,j

The left hand side equal

0 -

we obtain

D?nk , I:- gm,ihk,]Ci,j -

¹

(2.24) i,j

EZ,m L hk,i9m,jClj, (2.25)

i,j

F�,m' L- - gm,igm' ,j i,j cl

^·

(2.26) i,j

CZ k', D� k' E2 m' , F� m'

(24)

original image

Clj

^from

cz,k'' D!,k' EZ,m'

_and

F:;,m'

by the formula

k,k' m,k

k,m m,m'

We call

(2.27)

a wavelet r construction formula for images.

2.1.4 Two examples of the first generation wavelet

Example 1: Haar wavelet filters and transform

(2.27)

First, we introduce the set of Haar wavel t filters which are the simplest filters. The Haar wavelet filt rs

{ ^hk,l, hk,l 9m,l ?Jm,l}

are d fin d as follows:

h

_k,l -h -h

^-

{ 1//2, l=2k,l=2k+1,

-

k,l - l-2k

_-

0 oth rwise

{ ^1//2 ^l=2m,

9m,l = ^?Jm,l = ^!Jt-2m = -1//2, l =2m+ 1,

0, otherwise.

The indices

l - 2k

^and

l - 2m

mean the down-sampling by two.

Let

cf+1

be an original signal. Then Haar wavelet decomposition formulae for the signal, as derived from

(2.17)

^and

(2.18),

^ar

1 ( ^"+1 ^'+1 )

v'2 ^�m + ^�m+1 1 ( ^'+1 ^'+1 )

v'2 ^{�m+1- �m}

^·

(2.28) (2.29)

Conversely, the original signal

cf+1

can be restored from

cfn

^and

dfn

by the following equations

_j +1 1 (

^. ^.

)

C'2m v'2 ^dm + d::n , _i +1 1 (

^. ^.

)

C'2m+1 v'2 ^{dm -} d::n .

(25)

30080

30070

30060

30050

30040

30030

30020

30010

30000

29990

29980

0 400

(a) Original signal c1.

42560 r---.---.---.---.---r---,---r--, 135 ,---,,---,.---,---,---,---,---,�

·2000c,olddar- ·2000 d_old c�ar -

425-40 130

125 42520

120 42500

115

95

00 �-��-��-�--�--�--�--��

300 400 500 600 700 0 100 200 300 400 500 600 700

(b) Low frequency components c0. (c) High frequency components d0.

Fig. 2.2: Haar wavelet decomposition.

� ^{( C�,n}

� ( C� n - D�,n - E� n

⁺

F�,n) .

Fig.2.3 illustrates Haar wavelet d composition for an image.

(27)

Fig. 2.3: Lena imag

(

^up

)

and it Haar wavel t decomposition

(

^down

)

^.

(28)

Example 2: Convolution-type wavelet filters and transform

Another wavelet filters are the convolution-type wavelet filters derived in

[

15

]

. The de

composition and reconstruction filters

{hk,l, hk,l, 9m,l, .9m,t}

of convolution-type are defined as follows:

hk,l

=

O!t-2k' 9m,l

⁼

f3t-2m,

hk,l

=

(p

*

a)t-2k .9m,l

=

(p

*

J3)l-2m·

The parameter

p

is a thr -dim en ional vector p ⁼

(p_1, p0, p1)

and * denotes the discrete convolution symbol. If we choo e

p_1

⁼

p1

⁼ -0.5 and

p0

⁼2 the reconstruction filters

al

and

f3t

take values given in Tabl 2.1 and are symmetric as shown in Fig.2.4 and Fig.2.5.

In Table 2.2, we show th d compo ition filters

(p

*

a)l

and

(p

*

f3)t

which ar easily computed from

D!t

and

f3t

giv n in Table 2.1 and are al o symmetric as shown in Fig.2.6 and Fig.2. 7.

(29)

Table 2.1: The reconstruction filters

at

_and

f3t·

l

at f3t

-7 -0.000023342437

-6 -0.000118322123

-5 -0.000389002680

-4 -0.002317266249

-3 -0.007181850389

-2 0.353553390 93 -0.074595873421 -1 0. 70710 7811 7 -0.196528378993 0 0.353553390593 0.562325895710

1 -0.196528378993

2 -0.074595873421

3 -0.007181850389

4 -0.002317266249

5 -0.000389002680

6 -0.000118322123

7 -0.000023342437

(30)

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0 -4

0.6

0.5

0.4

0.3

0.2

0.1

0

-0.1

-0.2

'a.dat' -

-3 -2 -1 0 2

Fig. 2.4: Graph of th reconstruction filters at.

3

'b.dat'-

\·(

-8 -6 -4 -2 0 2 4 6 8

Fig. 2.5: Graph of the reconstruction filters f3t·

4

-

(31)

-5 0.000439788826

-4 -0.000849105964

-3 -0.176776695297 0.024092869057 -2 0.353553390 93 -0.047336632151 -1 1. 0606601717 1 -0.636921769131 0 0.353553390593 1.321180170413 1 -0.176776695297 -0.636921769131

2 -0.047336632151

3 0.024092869057

4 -0.000849105964

5 0.000439788826

6 -0.000030471688

(32)

1 .2 .---r----.---,---,----.,.---,---,---,

0.8

0.6

0.4

0.2

0

-0.2

'pa.dat' -

-5 -4 -3 -2 -1 0 2

Fig.

^2.6:

Graph of the

^d

ompo ition filters (p

*

a)t·

3

1 .4 .---..,.----.----.----,----,---r----r---r---,r---,

1.2 'pb.dat' -

0.8 0.6 0.4 0.2 0 -0.2 -0.4 -0.6 -0.8

-10 -8 -6 -4 -2 0 2 4 6 8

Fig.

^2.7:

Graph of the decomposition filters (p

*

f3)t·

10

(33)

2.2 Second generation wavelets

2.2.1 Real-type lifting wavelet transforms

The lifting wavelet filters are constructed by lifting initial lowpass decomposition and highpass reconstruction filters which include controllable free parameters. We denote an old set of biorthogonal wavelet filt rs by

{ h%l,1, h%�1, g��, g��}

and construct a new set of

wavelet filters

{ hk,l, hk,l 9m,l, 9m,l}

as follows:

h_ k,l hold k,l

h k,l h-old k,l

+

""

�

Sm,k9m,l' -old 9ml

9m,l

gold ml

^_

""

�

m S hold m,k k,l -old

9mt k

(2.30)

where

sm,k

denote free param ter filters, and

hk,L

^and

9m,L

^{are lowp}

hk,L

and

9m,l

are lowpass and highpass decomposition and high pas r con truction filt rs r spectively. These filters are called lifting wavel t filt rs. A far as the biorthogonality of lifted wavelet filters is concerned, Sweld n

[1 ]

prov d h foll wing th orem:

Theorem 2.1

Assume that a set of filters {h%�1, h%�1, g��' g��} satisfies the biorthogonal condition (2.13). Then, the set of filters { hk,L, hk,L 9m,L 9m,t} given in (2. 30) also satisfies the biorhogonal condition (2.13).

In simple words, this result says that for any choice of parameters

sk,m,

biorthogonality of the new filters is preserved.

The dual lifting wavelet filters are con tructed from biorthogonal wavelet filters, which include controllable free parameters. We construct a new et of wav let filters

{hk,t, hk,t, 9m,L, 9m,l}

^as^follows:

(34)

c 1

if old

_{c 0}^----(

s s ^{c 1}

(;old cold*

Fig.

2.8:

Lifting wavelet transform.

where

sk,m

denote free parameters. The orthogonality of the resulting wavelet filters is assured due to the following re ult by Sweldens

[18].

Theorem 2.2 Assume that a et of filters {h%�1, h%�1, g��, g��} satisfies the biorthogonal condition {2.13). Then, the set of filter {hk t hk,t, 9m,t, 9m,t} given in {2.31) also satisfies the biorhogonal condition {2.13).

It simply says that for any choi of param t r

-k,m,

biorthogonality of the new filters is preserved.

c 1

if old

-

s ^{c 1}

(;old

,__ ^____ do

cold*

Fig.

2.9:

Dual lifting wavelet transform.

(35)

2.2.2 Integer-type lifting wavelet transforms

Let us denote a signal consisting of integers by

c[.

Then, an integer version of Haar wavelet transform can be written as

(2.32) (2.33)

where

l

z

J

denotes the largest integer not exceeding ^z. The integers

c�

and

d�

denote low and high frequency components of the original signal

c[,

respectively.

Our integer-type lifting scheme is design d by lifting the low frequency component

c�

and by rounding-off the lifting term a follows:

(2.34) (2.35)

where

sm,k

indicate free r al param t r . Conversely, the original signal

c[

can be restored from

c�

and

d�,

as is given in Takano and Niijima

[24].

Theorem 2.3

Reconstruction formulae for (2. 34) and {2. 35) are given by c� - lL Sm,kd�J - l d�/2 J,

k do 1

m

+

In the onward discussion, we analyse the decomposed components.

We shall build an integer-ty pe dual lifting scheme by lifting the high frequency com

ponent

d�

and by rounding-off the lifting term as follows:

d�

^-

lL sk,mc�J, k

(2.38) (2.39)

where

sk,m

indicate free real param t r . Conversely, we can restore the original signal

c[

from

c�

and

d�,

as has been explained in Takano and Niijima

[26].

Theorem 2.4

The decomposition formulae (2.38) and {2.39) are invertible and the in- verse is given by

c�- l(d�

+

lL Sk,mc�J )/2 J, k

d�

+

C�m

+

lL Sk,mc�J.

k

Proof. For simplicity, we put q ⁼

lL:k sk,mc�J.

(i) In the case of

c�m

+

c�m+l

=

2p

with integer

p, (2.38)

and

(2.39)

y ield

2p- 2c�m-

(2.40) (2.41)

(2.42)

(37)

From this, it follows that

However, since we have

1

d� + q

c2m

= p- 2

because of

(2.42),

the value of

d� + q

_{is even.} Consequently,

1 -

- ld� + qj

c2m- P

2 .

The resulting equation is equal to

(2.40).

(

_ii

)

In the case of ^c

�

m

+

c

�

m+1

= 2p + 1, (2.38)

_and

(2.39)

_give

This leads to

From

(2.43),

we can obtain

Consequently,

2p + 1-2

c

�

m

-

q.

1

d�+q-1

c2m

= p- 2

l d� + q J = d� + q -1 . 2 2

Combining

(2.44)

and

(2.45),

we get

(2.43)

(2.44)

(2.45)

(38)

The equation

(2.41)

is derived from

(2.33)

and

(2.39).

0 Theorem

2.4

also guarantees that the original signal c

t

is equivalent to low and high frequency components

{

^c

�

^,

d�}.

(39)

Chapter 3 Learning and detection theory for signals

In this chapter, we propos a novel m thod for learning and detecting target points from unknown signals. First, we d crib a l arning method for lifting wav lets using training signals which contain target point . To b oncrete free param t rs in the lifting wavelet are tuned so a to vanish d compo d high fr quency component around the target points.

The learnt lifting wavelets have the feature of target ones. Applying such wavelets to the test signals, we can detect desirable points.

3.1 Learning and detection theory of real-type lifting wavelet transforms

3.1.1 Learning of real-type lifting wavelet transforms

We denote an input signal by c

[

^. In this section, we focus the dual lifting wavelet filt rs presented in Section

2.2.1.

By applying the high pass filters

(2.31)

to the input signal c

f

^,

we can compute new high frequency components. It can be writt n as

(40)

where we put

d� L9m,tcf l

L(g:�- L Sk,mh��f)cf

l k

dAo m- "' �cksk,m, Ao- k

JO m

⁼

� "' 9 - m,ll' old cl l

(3.1)

Here,

d�

^and

c�

indicate the high and the low frequency components obtained by applying the old filters

g��

and

hk�f

to

c}.

The high fr quency components

d�

represent the details

of the signal

c}.

Now, we investigate th distribution of the high frequency components

d�

computed for the signal shown in Fig. 2.2. As is clear from Fig.

3.1,

the distribution

16 r---r---.----.---,---.---r---r-----.--,------,

'Distnbulton'-

12

10

Fig.

3.1:

Distribution of

d�.

is mainly focused around zero and behaves like a generalized Gaussian distribution. This means that the information of the input signal

c}

concentrates on the large magnitude of high frequency components. Thus large high frequency components of the signal certainly express the feature of the input signal. However, all of them do not necessarily represent the feature of target points.

(41)

To obtain the feature of the target points in a signal, we determine free parameter

sk,m

so as to vanish the high frequency component

d�

in

(3.1).

An equation for determining

sk,m

takes the form

Since this equation includes several free parameters

sk,m

^{for each} ^m, we prepare

2N

training signals

c('v, v = 1, 2, ... , 2N

that include target events, and impose on them the following conditions:

v=1,2 . .. 2N (3.2)

k=m-

where we put

We hav

2N

+

1

unknown variabl s

sk,m,

but the number of equations in

(3.2)

is

2N.

One more equation is needed for det rmining

sk,m

^uniquely. The equation is a condition that

the summation of the highpa filter

?Jm,l

is zero, that is,

""""' """"' (-old m+N """"' - h-old)

⁰

D.9m,l = _{D .9m,l-} _D _{Sk,m k,l} =

^·

l l k=m-N

Since

g��

, satisfy

Ll g�� = ,

0 and

Ll hklf , =

const., this condition is equivalent to

m+N L _Skm

⁼ 0.

k=m-N

Writing

(3.2)

and

(3.3)

in the matrix form, we have

.... Q,l .... Q,l .... Q,l

(3.3)

(42)

We can solve

(3.4)

by the Gaussian elimination method. Substituting the solution

sk,m

into

(2.30),

high pass filters

?Jm,l

can be obtained.

3.1.2 Detection by real-type lifting wavelet transforms

We describe a detection theory of the target event in unknown signals. Using the param-

eters

sk,m

learnt in the previous section, we make filters for detection as follows:

- -old m+N � - h-old 9p,l

⁼

9p,l - D Sk,m k-m+p,l·

k=m-N

(3.5)

Now, we use the l arnt filters

.9p,l

to d teet the occurrences of target events in test signals.

Let

ci'r

be a test signal containing th target event. First, we compute the high frequency components

d�,r

by th l arnt highpass wavelet filters

[Jp,l

from

ci'r

as follows:

where we put

d�,r

⁼

_� ^{[Jp,l ll} r

l

�-old

1

r m+N � D gplcl - D

l k=m-

JO,r _p

�h-old l,r

D p,lcl ' l

�-old l,r

We summarize our detection algorithm:

Let us denote an input signal con isting of integers by

c[.

In this section, we concentrate on the integer-type Haar dual lifting wavelet transform:

d� d�- ll:: sk,mc�j,

k

where

c�

and

d�

represent the low and high frequency components obtained by applying the integer-type Haar wavelet transform

(2.32)

and

(2.33).

Of course, both components

(44)

By putting dc:n

⁼

0, we can

1

t sk,m have the feature at the position

m

where a target event occurred. To determine sk,m from much more target events, we prepare

L

training signals and impose on them the following conditions:

where we put

CO,v m JO,v m

1,v 1 v lc2m +2c2m+l J,

v = 0, ^· ^·^·

,

^L-

^1,

v =

0,

^·^·^·

,

L-

1,

l,v 1,v

_O _L

1 2m+

¹^-

c2m

^{v =} ^'

. ^{. .}

^-

^.

Since the symbol l·J denote round d in eger arithmetic ( 3. 7) ar equivalent to JO,v

^<

m+

"""'

- AO,v

<

JO,v + 1

m

^- ⁶

k,m k m '

k=m-N

^v⁼

0,

^·^·^·

,

L-

1. ( 3.7 )

( ^3.8 )

These inequalities yield a domain urround d by

L

hyper-planes in th

2N

+ 1-dimensional space. This domain means that h par am t

r

-k,m have freedom to d termine. It is very important to verify whether this domain is empty or not. This dep nds on the low and high frequency components. In the case of

L :::; 2N

+ 1, the domain is not empty. In simulations given in Chapter

4,

we choose

L = 2N.

We can not determine sk,m only by ( ^3.8 ) . To determine the parameters stably we consider a minimization probl m subj ct to ( ^3.8 )

m+N L (sk,m)2 --+min .. ( ^3.9 )

k=m-N

This minimization problem can be solved by the use of the penalty method which is

"""' (- )2

K"""'

(dAO,v """' - AO,v)2 ( """' - AO,v dAO,v 1 ) ²

m+N L-1 ( ^m+N ^m+N

)

k= ;:_ ^N

Sk,m

⁺

17::o

m -

k= ;:_ ^N

Sk,mCk + +

k= ;:_ ^N

Sk,mCk - m - +

--+

min. ( ^3.10 )

where z�

⁼

z2 for z

^> ^0,

and

0

otherwise, and

K

is a penalty constant. The problem

( ^3.10 ) can be solved by gradient methods such as the steepest decent method.

(45)

3.2.2 Detection by integer-type Haar lifting wavelet transforms

Let

c [

^'

r

be an unknown test signal. To detect the target events in the test signal, we use the learnt parameters

sk,m

in the previous section.

First, we compute the following low and high frequency components using the integer- type Haar wavelet transform

(2.38)

^and

(2.39).

c_O,r p JO,r

p

l,r

⁺

l,r l c2p 2 c2p+

¹

J '

l,r l,r

c2p+l - C2p

^·

Then, using the parameters -

k m

^d t rmin d in the previous section, we compute new high frequency components

d � r

^by

do r - dAO,r l m+

""""""

- AO,r J

p - p

^- ^L

Sk mCk-m+p

^·

(3.11)

k=m-N

The computed

d � ,r

are int ger .

Using the same algorithm as given in Section

3.1.2,

we can find the location p so as to maximize the quantity

(46)

Chapter 4 Detection of geomagnetic sudden commencements ( ^SC )

4.1 What is SC?

The earth's magneto phere i suddenly ompr ssed wh n it is collided with the interplane- tary shock mitted from th un. Sudd n in r ase of the magn tic field called geomagnetic sudden commencement

(

_SC

)

_i b rv d in the magneto phere. n the ground it is detected almost simultaneously all over the world.

The study of SC is important because SCs can be used as a probe to study transient response of the complex s st m consi ting of the magnetosph re ionosphere and el ctri- cally conducting earth to sudd n incr ase of the dynamic pressur in the solar wind. It is desirable to det ct and to accumulate as many SCs as possible to make statistical studies of the SC phenomena. Real time det ction of SCs is also important because SCs are frequently follow d by severe g omagnetic storms during which many hazardous accidents such as anomalies of electronic circuits on board satellites, large scale power line failures at high latitudes may occur.

The SC at low latitude is typically observed as a sharp increase of the geomagnetic horizontal

(

_H

)

component. This sharp increase can b expressed as high frequency compo

nents which are obtained by a wavelet decomposition of the H-components. The wavelet

(47)

decomposition is carried out by using lowpass and high pass wavelet filters

[5].

Intuitively, it seems that the high frequency components enable us to detect the SC phenomena.

However, this is not useful according to our experience.

Since a geomagnetic SC often occurs as a sharp increase of the H-components, it may appear in the high frequency components. As a simple algorithm for automatic detection of geomagnetic SCs, it is considered to find the time ^mwhen the absolute value of the high frequency components computed by

(2.18)

is large. To examine this simple algorithm, by using it, we compute the high frequency components of geomagnetic horizontal com

ponents in Kakioka station shown in Fig.

4.1.

The time when SC phenomena occurred is

10:22

which was indicated using th arrow in Fig.

4.1 (

a

)

. The absolute value of high frequency compon nt at this time how v r is not always the largest.

To solve this problem, we apply two d tection algorithms using r al-type lifting wavelet and integer-type lifting wavelet tran form which were described in the previous chapter.

The real-type lifting wavelet tran form i onstructed using th convolution-type wavelet filters

[ 15 J

as initial filters.

(48)

30170 �---�---�---r---�---�---�---�

30160

30150

30140

30130

30120

30110

30100 L---�---�---�---�---�---�---�

0 200 400 GOO BOO 1000 1200 1400

(a)

42570 L_ __ __._ ____ _.__ __ �---'----�---'---l-..J

0 200 400 600 BOO 1 000 1200 1400

(b)

^(c)

Fig. 4.1: (a) Geomagnetic horizontal components on May 21, 1990,

(b)

the low frequency components for (a), and (c) the high frequency components for (a).

(49)

4.2 Automatic detection of SC

4.2.1 Geomagnetic horizontal (H) component data

We describe the H-component data collected in World Data Center C2 (WDC-C2) for Geomagnetism, Kyoto. Four ampling types of data have been stored in WDC-C2, Kyoto.

These data types are geomagnetic on second, one minute, one hour and one year value data.

In simulations, we us th H-components of geomagnetic 1 minute value data. This data has been stored in WDC-C2, Kyoto sine 1975 and the complete size of this data is about 300Mbytes in Kakioka station.

4.2.2 Detection of SC by real-type lifting wavelet transforms

As training ignal , w u 4 whol dar H-compon nts dated May 6, 1988 January 20, 1989, March 16, 1989 and 1ay 7 19 9 in Kakioka station. These training signals contain typical SCs as shown in Fig. 4.2. We denote these training signals by ^c

t

^'v, ^{v =}^1,^{2, 3, 4.}

Therefore, the number of ^-

k,m

appearing in th lifting term is five and the equation (3.4)

is written as

�0,1 �0,1 c0,1 �o 1 �0,1 d0,1

Cm-2 �0,2 Cm-1 �0,2 co,2 m Cm+l �0,2 Cm+2 �0,2 Sm-2,m Sm-1,m d0,2 m

Cm-2 �0,3 Cm-1 �0,3 co,3 m cm+1 �0,3 Cm+2 �0,3 Sm,m d0,3 m

^(4.1)

Cm-2 �0,4 Cm-1 �0,4 co,4 m Cm+1 �0,4 Cm+2 �0,4 Sm+l,m d0,4 m

Cm-2 Cm-1 m Cm+1 Cm+2 m

1 1 1 1 1

Sm+2,m

0

The index ^m denotes the time of SC in each of the training signals. Solving ( 4.1) we can obtain the parameters

sk,m

and construct an adaptive filter

§m,l

using (2.31). We

(50)

r +-SC

;'1..1"'

/

30100 6----,J

May 6 1988 January 20, 1989

March 16, 1989 May 7 1989

Fig. 4.2: Training ignal containing SCs at Kakioka station.

automatic detection of SCs. Fig. 4.4 shows the computed values Im for the H-components of Fig. 4.1

(

^a

)

. The largest peak in Fig. 4.4 denotes SC, but the largest peak of the high frequency components in Fig. 4.1 appears in different time. This implies that SCs can not be detected using only the high frequency components.

Since the SCs occur at the same time in the world, we try to detect SCs at other

stations Honolulu Harmanus, and San Juan which are located at the same latitude as Kakioka station. To determine the filter for d tection of SCs at each station, we prepare 4 whole day H-components during the same days as at Kakioka station. These training

signals contain typical SCs as shown in Fig. 4.5. Using these training signals, we can learn the free parameters sk,m contained in the lifting term of

(

^2.31

)

at each station. We illustrate the learnt filters in Fig. 4.6.

(51)

1.5

0.5

·0.5

·1

!! I.

I\

I \ i \

1/\.

,I \

/ \

\ / \!

^___ ^{__ _}

' I ^v

\;

_v

·1.5 L..---'---'---'----'---'---'----'----'----'---'

·10 ·8 ·6 -4 ·2 10

Fig. 4.3: Filter learnt for SC signals in Fig.4.2

1.6 'De1ee110n'-

1.4 1.2

0.8 0.6 0.4

[I�

^Jo. ^II

0.2

0 0 200 400 600

800

¹⁰⁰⁰ ¹²⁰⁰ ¹⁴⁰⁰ ¹⁶⁰⁰

Fig. 4.4: Computed values Im for Fig. 4.l

(

^a

)

^.

In the same way as at Kakioka station, we detected the SC phenomena at each station as listed in Table 4.2, Table 4.3 and Table 4.4.

(52)

moo0 L __ ...___ _ __._ __ ...___ _ _._ __ ..___ _ _.___ __ ._,

May 6, 1988

� _L

ⁱ

!\

'', ^!'..,\ t'

' . r,. "'\.J.

l,'

_j

\_/"'

January 20, 1989

March 16, 1989

May 7, 1989

i I

�.

tj

2'7060 0._ _ _.__ __ .___ _ _.__ __ .___ _ _.__ __ .___ _ _._,

I, -1:

; Hr l

27180 l

27170 ,.,./'"'l. _,} \

,,j'

271&0 \1 'J

r,\1

! t\

... , .. ·" .. �·" \!.

/1 _l

i '\ .

\! \.../../

211200 L __ ...___ _ _.__ __ ...___ _ __._ __ ..___ _ _._ __ L..J

Fig. 4.5: Training signals containing SCs at Honolulu (left column), Hermanus (middle

(53)

20 ,----r----.----.----.----.----.----.---.----.---�

15

10

-5

-10

-15

-20 -10

10

-5

-10 -8

/\

____

/ \\

_\

\

I

\

I

\ i

-6

\i

_v

II \

\ I\

f\

I

^\

I \

I ^\

I '

I \

//-··^--

! :

-2

(a)

! I

I

\

.. /\

\

\ \I

\I v

I I

I i I !

I i i I

!

\ \

_'v'^// "---·-···-··

't:cr: .. ·"av.:;:t:t.di:: --

10

-15 L_ ^__^__;_^____^..L-^__---l. ____ _._ __ ___.. ____ _._ ___ L__ __ _._ ____ .._ __ _J

-10 -8 -6 -4 -2 10

1.5

0.5

-0.5

-1.5

"

I \

/\

(b)

Il

l

\\

I\

!

\

_{II \,}

I i

''/ \

\ ^{I \}I ^\

" / _'-..:' \ i ;

I \/.r

^.....___.-·-···

\ i

\ \ I

[',, i

\

_t _I! ^�

\

i v

リフティングウェーブレットによる信号と画像の抽出