Computer Vision & Pattern Recognition Lab. 김 태 철 (월)

Presentation on theme: "Computer Vision & Pattern Recognition Lab. 김 태 철 (월)"— Presentation transcript:

1 Computer Vision & Pattern Recognition Lab. 김 태 철 2004. 10. 4 (월)
An Introduction to Wavelets (Amara Graps) Computer Vision & Pattern Recognition Lab. 김 태 철 (월) Computer Vision & Pattern Recognition Lab.

2 Computer Vision & Pattern Recognition Lab.
Overview 1. Wavelets Overview 2. Historical Perspective 3. Fourier Analysis 4. Wavelet Transforms versus Fourier Transforms 5. What do some wavelets look like? 6. Wavelet Analysis 7. Wavelet Applications Computer Vision & Pattern Recognition Lab.

3 Computer Vision & Pattern Recognition Lab.
Wavelets Overview 1980년대 초 이론으로 정립되기 시작 순수수학, 양자물리학, 전자공학 등 여러 분야에서 독립적으로 형성 지난 10년 동안 과학자, 공학자들간의 상호교류를 통해 ‘Wavelet’이라는 이름으로 통일 여러 분야에서의 응용성이 확대 √ 수학 – 조화 함수론 √ 양자 물리학- coherent state, renormalization group 이론 √ 신호 영상처리- subband coding 알고리즘 √ 컴퓨터 비젼- stationary subdivision 알고리즘 각 분야에서 새로운 첨단 기술 창조 Computer Vision & Pattern Recognition Lab.

4 2. Historical Perspective
Pre-1930 √ 1807: J.Fourier, Fourier Series 주파수 분석 (Fourier Transform) √ 1909: Haar, Orthonormal Function System 다중 해상도 방법과 웨이블릿의 긴밀한 변환 관계를 쉽게 설명 척도(scale) 분석 (Harr System) The 1930S scale-varying basis Function : Haar basis function √ Brownian motion - Paul Levy wavelet을 이해하기 위한 key √ Another researcher: energy function David Marr : Effective Algorithm for numerical image processing Computer Vision & Pattern Recognition Lab.

5 What are Basis functions?
f(x)가 음악적 톤. 즉, 규칙적인 옥타브 A라고 상상해보자. 그러면, A는 주파수와 진폭의 결합을 이용하여 sin과 cos의 합으로 나타낼 수 있다. 여기서 sin 과 cos을 Basis Function이라고 한다. What are Scale-varying Basis Functions? 0과 1사이의 신호가 있다면 그걸 0에서 1/2과 1/2에서 1로 나눌수 있다. 이렇게 계속해서 정규화된 사이즈로 나뉘어 질수 있는 함수 Computer Vision & Pattern Recognition Lab.

6 2. Historical Perspective (Continue)
1980: A.Grossman & J.Morlet √ 시간-주파수 분석 (Continuous Wavelet Transform) POST-1980 1985(9): S.Mallat, Multiresolution Analysis √ QMF(Quandrature Mirror Filter), 피라미드 알고리즘, 직교 웨이브렛의 공통적인 특징 발견 √ 다중해상도분석 개념 소개, 고속 웨이브렛 변환 알고리즘 개발 √ 디지털 신호처리 분야 연구를 통한 Wavelet 연구가 활발 1987: I.Daubechies, Daubechies’ Orthonormal Wavelets √ Mallat의 다중해상도분석을 이용하여 직교 웨이브렛의 존재성과 구축법 확립 √ 이산형 정규 직교 웨이브렛을 무한 구간으로 확장 √ 오늘날 웨이브렛 응용의 기초가 됨 Computer Vision & Pattern Recognition Lab.

7 Computer Vision & Pattern Recognition Lab.
3. Fourier Analysis 시간 영역 주파수 영역 신호처리 분야의 비약적인 발전의 모태 기본함수(Basis function)로 sine, cosine 함수만 사용 [전역적인 신호 분석] 단점 √ 신호 데이터에 불연속성, 날카롭게 도출된 부분(고주파수 성분)이 포함될 경우, 신호의 특징 분석이 난이 √ 신호의 시간 정보와 주파수 정보를 동시에 파악할 수 없다. Computer Vision & Pattern Recognition Lab.

8 3. Fourier Analysis (Windowed Fourier Transforms)
WFT (Windowed Fourier Transform) 일정한 크기를 가진 창함수와 Fourier 변환의 결합 시간 변화에 따른 주파수 특성을 분석 단점 √ 분석 영역이 시간-주파수에 대해 항상 일정 √ 비정상적인 신호(non-stationary signals)를 효율적으로 분석할 수 없다. Computer Vision & Pattern Recognition Lab.

9 3. Fourier Analysis (Fast Fourier Transforms)
Turkey and Cooley 에 의해 향상된 DFT 알고리즘 (DFT의 고속화) FFT 의 분리성 [ 2차원 연산식  2개의 1차원 연산식 ] : divide & conquer기법 N x N 의 크기 영상의 복잡도 영상의 크기는 2의 지수승 ( 반복적인 데이터 분할) √ 2의 지수승이 아닌경우 : 영 삽입 (zero padding) Computer Vision & Pattern Recognition Lab.

10 4.Wavelet Transforms Versus Fourier Transforms
√ 기본 함수로 sine, cosine 함수 이외에 웨이브렛 모함수 사용 √ 각 주파수 영역에 따라 변화하는 다양한 기저함수 사용 (시간-주파수에 국부적인 성질) √ 가장 적절한 다중해상도 표현 방법 √ 사용분야 음성인식, 정지영상/ 동영상 압축, 오디오 압축, 음악 해석 등 √ 대표적인 wavelet 변환 기법 Orthonormal Wavelet, Biorthonormal Wavelet, Packet Wavelet, Chirplet Wavelet 등의 변환 Computer Vision & Pattern Recognition Lab.

11 4.Wavelet Transforms Versus Fourier Transforms
Similarities between fourier and wavelet transforms √ Both Linear Operation √ FFT와 DWT의 inverse transform matrix는 original의 transpose √ fft는 sines과 cosines를 포함하는 basis function √ wavelet transform은 wavelets 혹은 mother wavelets or analyzing wavelets이라고 불리우는 더 복잡한 basis funtion Computer Vision & Pattern Recognition Lab.

12 4.Wavelet Transforms Versus Fourier Transforms
Dissimilarities between fourier and wavelet transforms √ wavelet funtions are localized in space but fourier sin and cosine functions are not. Computer Vision & Pattern Recognition Lab.

13 Computer Vision & Pattern Recognition Lab.
Continue… FT WT Computer Vision & Pattern Recognition Lab.

14 5. What do some wavelets look like?
Wavelets family는 상관계수의 수와 반복횟수의 의해서 구별되는 웨이블릿의 부분집합 wavelets family는 vanishing moments의 수에 의해 구별 Computer Vision & Pattern Recognition Lab.

15 5. What do some wavelets look like?(continue)
Computer Vision & Pattern Recognition Lab.

16 6. Wavelet Analysis (DWT)
Orthonarmal Wavelet(정규직교 웨이브렛) Wavelet의 가장 큰 특징은 안정 Computer Vision & Pattern Recognition Lab.

17 Computer Vision & Pattern Recognition Lab.
7. Wavelet Applications Computer and Human Vision √ 1980’s 초 David Marr - 로봇에 대한 인공 시각(artifical vision) 연구 시작 √ Human Visual System에서의 영상 처리 – vision filter ( Marr’s operator  ‘Marr wavelet’ ) Computer Vision & Pattern Recognition Lab.

18 Computer Vision & Pattern Recognition Lab.
7. Wavelet Applications FBI fingerprint Compression 원본 이미지 26:1 압축 Computer Vision & Pattern Recognition Lab.

19 Computer Vision & Pattern Recognition Lab.
7. Wavelet Applications Denoising Noisy Data Computer Vision & Pattern Recognition Lab.

20 Computer Vision & Pattern Recognition Lab.
7. Wavelet Applications Musical Tones (Ex.음성, 음악의 합성) Computer Vision & Pattern Recognition Lab.