\documentclass[12pt]{article}
%\pagestyle{myheadings}

\usepackage[magyar]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
%\usepackage{psfrag}
\usepackage[a4paper,left=1.4cm,right=1.4cm,top=1.4cm,bottom=1.4cm]{geometry}                           
\usepackage{amsmath}                      
\usepackage{amssymb}                   
%\usepackage{indentfirst}                  
%\usepackage{verbatim}
\usepackage{color}
%\usepackage[round]{natbib}
\usepackage{lscape}
\usepackage{palatino}
%\usepackage{afterpage}
%\usepackage{rotating}

\title{Wavelet-transzformáció és JPEG2000}
\date{}

\begin{document}

\maketitle
\newpage

\section{Bevezetés}
	
\subsection{Folytonos Wavelet-transzformáció}

A Fourier-, a diszkrét Fourier- (DFT), és diszkrét koszinusz- (DCT) transzformációk harmonikus bázisfüggvényekre épülnek. Az állandósult állapotbeli, harmonikus bázisfüggvények tere alkalmas állandósult állapotbeli, periodikus jelek leírására, de a jeleken belüli tranziens változások, tehát a harmonikus komponensek - pl. időbeli - változásának leírására kevésbé alkalmas. 
Például ismeretes, hogy a DFT (FFT) frekvenciafelbontása $\Delta f=\frac{f_s}{N}$, míg az egy DFT ablakhoz tartozó kerethossz, tehát az időfelbontás $\Delta t = N\frac{1}{f_s}$, ahol $N$ a DFT pontszáma, $f_s$ pedig a mintavételi frekvencia. A pontszámot növelve tehát javul a frekvenciafelbontás, de romlik az időbeli felbontás.

Mivel a Waveletek alapvető jellemzője a tranziens viselkedések jellemzésének képessége, ezért a Waveletre épülő transzformációk a harmonikus bázisfüggvényű transzformációk egy hatékony alternatíváját jelentik. 
%The transforms that we discussed so far have sinusoidal or rectangular basis functions.	A transform based on sinusoids, such as the DFT, can capture only
%frequencies in the steady state, that is, such a transform can enumerate the different
%frequencies present in the signal being analyzed from start to finish but cannot
%capture the moments that such frequencies begin or end. Even though this is possible
%with transforms based on sinusoids, wavelets are more efficient because of their
%inherent property of capturing transients.
Míg a folytonos Fourier transzformáció harmonikus bázisfüggvényei a $-\infty \leq t \leq \infty $ intervallumon konstans amplitúdóval értelmezettek,
a wavelet bázisfüggvények gyorsan lecsengő függvények, melyek egy véges, esetleg végtelen intervallumon értelmezettek.
%Unlike the continuous Fourier transform, which uses complex sinusoids as its basis
%functions, the wavelet transform uses wavelets as its basis functions. Each sinusoidal
%basis function in the Fourier transform exists over an infinite interval with constant
%amplitude. On the other hand, a wavelet is a fast decaying function even though
%it may exist over an infinite interval. 
Egy folytonos időbeli jel folytonos Fourier transzformáltja kizárólag a frekvencia egyváltozós, folytonos függvénye. Ezzel szemben egy folytonos jel folytonos Wavelet transzfromáltja a \textit{skála} (scale) és \textit{eltolás} (shift) kétváltozós függvénye. A skála a jel frekvencia összetevőinek periódusidejével van kapcsolatban. Tehát a kis skála érték nagyfrekvenciás összetevőket, míg a nagy skála érték kisfrekvenciás összetevőket jellemez.


%The Fourier transform of a continuous-time
%signal is a function of the frequency only. But the wavelet transform of a continuous time
%signal is a function of scale and shift. 
%A scale as used in the wavelet transform
%is roughly related to the inverse frequency—small scale implies large frequencies
%and vice versa. 

A Fourier transzformáció esetében a harmonikus összetevők frekvenciája nincsen kapcsolatban egymással, a spektrum folytonos $-\infty 
\leq f \leq \infty$ között. A Wavelet transzformáció esetében a wavelet bázisfüggvények skálázás, és eltolás (dilatáció) segítségével leszármaztathatók egy ún. anya-wavelet (prototípus) függvényből.
%In the Fourier transform of an a periodic signal, all the sinusoidal
%frequencies are not related to each other, that is, the frequencies are continuous. In
%wavelet transform, it is possible to have all the wavelet functions related to a single
%wavelet called the mother wavelet, from which all the wavelet functions are obtained
%by dilation and contraction. Figure 4.1 shows two wavelets scaled by different values.
%These two wavelets are called Daubechies wavelets. The formal definition of the
%CWT follows.
Egy folytonos $f(t)$, $-\infty \leq t \leq \infty$, jel folytonos Wavelet transzformáltja (CWT), melyet jelöljünk $W(s, \tau)$-vel, formailag a következőképpen definiálható:
\begin{equation}\label{eq:cwt}
W(s,\tau)=\int_{-\infty}^{\infty} { f(t) \psi_{s,\tau}(t) \ dt}, 
\end{equation}
ahol $s$ a skála (scale), $\tau$ pedig az eltolás (shift). A $\psi_{s,\tau}(t)$ bázisfüggények eltolással (dilatációval), és nyújtással/zsugorítással (kontrakció) származtathatók az anya-waveletből a következő módon:
\begin{equation}\label{eq:motherwavelet}
\psi_{s,\tau}(t)=\frac{1}{\sqrt{s}} \psi \left( \frac{t-\tau}{s} \right) 
\end{equation}	
A CWT esetében mind a skála, mind a shift paraméterek folytonos változók. 
A skála arányos a wavelet bázisfüggvény hosszával (pl. lecsengési idejével), tehát a nagy skála hosszú lecsengési idejű waveletet jelent, mely a jel kisferekvenciás viselkedését jellemzi.
A kis skálájú bázisfüggvények rövid lecsengési idejű függvények, melyek a jel nagyfrekvenciás (pl. tranziens) viselkedését jellemzik.
Egyszerűen kifejezve tehát a wavelet transzformált skála és eltolás paramétere együttesen a jel adott skálával jellemezhető frekvenciakomponseinek viselkedését írja le az eltolásnak megfelelő időpillanat környezetében.
Az \eqref{eq:motherwavelet} egyenletből belátható, hogy az egy anya-waveletből leszármaztatott összes bázisfügvény energiája egyenlő az anya-wavelet energiájával.
\begin{figure}
	\centering
	\includegraphics[width=0.5\textwidth]{fig/waveletscaling.png}
	\label{fig:waveletscaling}
	\caption{A Daubechies wavelet két különböző skálaparaméter értéke mellett}
\end{figure}
%Scale is proportional to the duration of the wavelet functions. Therefore, large scale
%corresponds to wavelets with a long duration and when a signal is expanded in
%terms of such wavelets, the effect is to capture the long-term behavior. On the other
%hand, small scale implies short duration for the wavelets and the signal expansion
%with small-scale wavelets captures short-term behavior of the signal.we observe that the scale parameter gives a measure of the frequency
%of the signal at a time instant specified by the shift parameter.	
%all the
%wavelets have the same energy,all the wavelets have the same energy equal to that of the mother wavelet	
\subsection{Wavelet-sorfejtés} 

Ha a Wavelet transzformáció skála és shift paraméterei nem folytonos, hanem diszkrét értékeket vesznek fel, akkor a folytonos $f(t)$ jel kifejthető a Wavelet-sorfejtés segítségével.
Ha a skála paraméter 2 egész hatványú értékeit veheti fel (bináris skálázás), és a shift paraméter egész értékeket vehet fel (diadikus transzláció), akkor az $f(t)$ jel kifejthető végtelen számú \textit{skála-függvény} és \textit{wavelet-függvény} összegeként:
%If the scale and shift parameters in equation (4.1) are discrete rather than continuous,
%then it is possible to expand f (t) in a wavelet series, that is, summation rather
%than integral [11, 12]. More specifically, if the scale parameter is allowed to take on
%values that are integer power of two (called binary scaling) and the shift parameter
%is allowed to take on integer values (known as dyadic translation), then the wavelet
%series of f (t) is expanded in terms of (1) infinite sum of scaling functions and (2)
%infinite sum of wavelets. Thus, the wavelet series of f (t) is written as
\begin{equation}\label{eq:waveletseries}
f(t)=\sum_{k} a(j_0,k) \phi_{j_0,k} (t) + \sum_{j=j_0}^{\infty} \sum_{k=-\infty}^{\infty} d(j,k) \psi_{j,k} (t) 
\end{equation}
Az \eqref{eq:waveletseries} kifejezés első tagja tartalmazza a $\phi_{j_0,k}$ bázisfüggvényt egy rögzített skála ($j_0$) mellett a shift paraméter minden lehetséges értékére. A $\phi_{j,k}$ bázisfüggvényeket \textit{skála-függvényeknek} hívjuk, melyek egy prototípus skálafüggvényből nyerhetők bináris skálázás és diadikus transzláció segítségével: 
%The first summation involves the basis functions $\phi_{j_0,k}$ at a fixed
%scale $j_0$ and the summation is over all possible shift values. The functions $\phi_{j,k}$ are
%called scaling functions and are obtained by binary scaling and shifting of a prototype
%function as given by equation
\begin{equation}
\phi_{j,k}(t)= 2^{j/2} \phi(2^j t - k)
\end{equation}
Ezek alapján \eqref{eq:waveletseries} első tagja az $f(t)$ jel egy közelítése hasonlóan pl. a Fourier sor nulla frekvenciájú tagjához (átlagérték). A \eqref{eq:waveletseries} kifejezés második tagja a \textit{wavelet-függvények} végtelen összege, melyek szintén egy prototípus függvényből származtathatók bináris skálázás és diadikus transzláció segítségével: 
%
%
%Also, the first summation in equation (4.7) represents an approximation of f (t) similar
%to the average value given in the Fourier series expansion of a periodic (or periodically
%extended) signal. The second summation in the wavelet series involves the
%dyadic wavelets, which are expressed as
	\begin{equation}
\psi_{j,k}(t)=2^{j/2} \psi(2^j t - k)
\end{equation}
Ebben az esetben is, a Fourier sorfejtés magasabb rendű harmonikusaihoz hasonlóan, a Wavelet-függvények az $f(t)$ jel nagyfrekvenciás, tranziens viselkedését jellemzik.
A Wavelet-sorfejtésben, a \eqref{eq:waveletseries} kifejezésben szereplő $a(j_0,k)$ és $d(j,k)$ együtthatók a folytonos Wavelet transzformáció \eqref{eq:cwt} kifejezésének segítségével a következő módon határozhatók meg:
\begin{equation}
a(j_0,k)=2^{j_0/2} \int_{-\infty}^{\infty} {f(t) \phi_{j_0,k}(t)  \ dt}
\end{equation}
\begin{equation}
d(j,k)=2^{j/2} \int_{-\infty}^{\infty} {f(t) \psi_{j,k}(t)  \ dt}
\end{equation}

\subsection{Diszkrét wavelet transzformáció (DWT)}	

Ha mind a jel, mind pedig a skála- és wavelet-függvények diszkrét idejű függvények, akkor a Wavelet-sorfejtés a Diszkrét Wavelet transzformációt (DWT) eredményezi.
A Wavelet-sorfejtéshez hasonlóan a DWT két sorfejtésből áll: egy közelítő sorfejtésből, és egy részletező sorfejtésből.
%
%If the signal, scaling functions, and wavelets are discrete in time, then the wavelet
%series in equation of the discrete-time signal is called the DWT
%The DWT of a
%sequence consists of two series expansions, one corresponding to the approximation
%and the other to the details of the sequence. The DWT of a
%sequence consists of two series expansions, one corresponding to the approximation
%and the other to the details of the sequence. The formal definition of DWT of an
%N-point sequence $x[n]$ , $0 \leq n \leq N-1$ is given by
A DWT formális definíciója egy N hosszú, véges tartójú diszkrét jelre ($x[n]$ , $0 \leq n \leq N-1$ ):
\begin{equation}
DWT \left\lbrace f(t) \right\rbrace=W_{\phi} (j_0,k) + W_{\psi} (j,k),
\end{equation}
ahol a skála (közelítő) együtthatók: 
\begin{equation}\label{eq:scalecoeff}
W_{\phi} (j_0,k) =\frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x[n] \phi_{j_0,k} [n],
\end{equation}
a wavelet (részlet) együtthatók pedig:
\begin{equation}\label{eq:waveletcoeff}
W_{\psi} (j,k) =\frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x[n] \psi_{j,k} [n] \ \ \ \ \ j\geq j_0.
\end{equation}
Az inverz DWT (rekonstrukció) pedig a következő módon írható fel:
\begin{equation}\label{eq:idwt}
x[n]=\frac{1}{\sqrt{N}} \sum_{k} W_{\phi} (j_0,k) \phi_{j_0,k} [n] + \frac{1}{\sqrt{N}} \sum_{j=j_0}^{\infty} \sum_{k} W_{\psi} (j,k) \psi_{j,k} [n]
\end{equation}

Az \eqref{eq:idwt} kifejezés második tagja egy végtelen sorösszeg, melyet a gyakorlatban véges számú tag összegeként közelítenek. A $j_0=0$ általában, míg $N$ értéke 2 valamely hatványa.



\subsection{Részsávos DWT kódolás}

Tekintsünk egy egy dimenziós, $N$ hosszúságú diszkrét jelet. A jel részsávos kódolása a jel többlépcsős szűrését és alulmintavérelezését jelenti: az első szinten a jelet aluláteresztő, és felüláteresztő szűrőkkel szűrjük. A két szűrő kimeneteit 2:1 arányú alulmintavételezésnek vetjük alá, vagyis minden második mintát eldobunk. Tehát az első szint kimenetén két, $N/2$ hosszúságú szekvenciánk van, egyik a kisfrekvenciás, más a a nagyfekrveniás komponenseket tartalmazza.
A második lépcsőben az első szint aluláteresztő szűrőjének kimenetét ismét ugyanazzal a szűrőpárossal szűrjük, és 2:1 arányban decimáljuk, tehát végeredményben a második szinten két $N/4$ hosszúságú szekvenciát kapunk. Ez a többlépcsős, részsávos szűrés-decimálás folytatható tetszőleges számú szintig, minden egyes szinten az aluláteresztő tagok kimenetének újabb részsávokra történő bontásával. Ezt a technikát \textit{oktávsávos részsávos felbontásnak} hívják, mert minden szinten két részsávra bontjuk az előző szint kimenetét. Az eredeti jel részsávos felbontását a jelfeldolgozás \textit{analízis szakaszának} hívjuk, az ezt megvalósítő szűrőbankot pedig \textit{analízis szűrőbanknak}.
A \textit{rekonstrukciós}, vagy más néven \textit{szintézis szakaszban} az analízis szakasz kimeneti jeleit fordított "irányban" feldolgozva, egy ún. \textit{szintézis szűrőbank} segítségével tudjuk az eredeti jelet, vagy annak egy közeleítését visszaállítani. 

%For the time being, let us consider a 1D sequence of length
%N. Subband coding consists of a sequence or stages of filtering and subsampling
%processes. In the first stage, the input sequence is filtered by two filters, a lowpass
%filter, and a highpass filter. The output of each filter is decimated by a factor of 2,
%that is, only every other output sample is retained at the filter output. 
%In the frequency
%domain, the outputs of the filters occupy the frequency regions below and
%above half the sampling frequency. Note that the two outputs may have overlapping
%frequency regions due to the filter responses. 
%Thus, in the first stage, there are
%two output sequences of length each N/2 corresponding to low and high frequencies.
%In the second stage, the output of the first stage lowpass filter is filtered by
%the same lowpass and highpass filters and decimated by a factor of 2 to give two
%length N/4 output sequences. This process of filtering the output of the lowpass
%filter and decimating is repeated M times. 
%This type of subband coding is called
%the octave-band subband coding because each time only the lowpass region is split
%into two halves. 

%This stage of subband coding where the input signal is decomposed
%into octave frequency bands is known as the analysis stage. In the synthesis or reconstruction
%stage, the procedures are repeated in the reverse direction using another
%set of lowpass and highpass filters. 

Rekonstrukció során tehát először az analízis szakasz utolsó szintjének aluláteresztő szűrőjének kimenetét 2:1 arányban interpoláljuk, majd szűrjük egy szintézis aluláteresztő szűrővel. Ugyanígy, az analízis szakasz utolsó szintjének felüláteresztő szűrőjének kimenetét 2:1 arányban interpoláljuk, majd szűrjük egy szintézis felüláteresztő szűrővel. E két szűrő kimenetét összeadjuk, majd az eljárás tovább folytatva, a megfelelő számú szintézis szakasz ismétlésével visszakapjuk az eredeti, $N$ hosszúságú szekvenciát.

%First, the output of the lowpass filter at
%the Mth stage is upsampled by 2 (zero value inserted between samples) and then
%filtered by a synthesis lowpass filter. Similarly, the output of the highpass filter at
%the Mth stage is upsampled by 2 and then filtered by a synthesis highpass filter.
%The two outputs are added. This process is repeated until a sequence of length N is
%obtained, which is the reconstructed sequence.
Az analízis szakasz 2:1 arányú decimálása, valamint a szintézis szakasz 2:1 arányú interpolálása során  visszaállíthatóság szempontjából kritikus, hogy anti-aliasing, és "image"-spektrum mentes szűrési lépéseket végezzünk. Ennek érdekében az analízis és szintézis szűrőbank szűrőinek meghatározott követelményeket kell teljesíteniük. Ez ilyen típusú szűrőket általábosságban QMF (Quadrature Mirror Filter) szűrőbankoknk hívjuk.

%
%Due to filtering and subsampling by 2, the filtered signals suffer from aliasing
%distortion. Similarly, upsampling followed by filtering introduces image frequency.
%Therefore, use of lowpass and highpass filters with arbitrary frequency responses
%will result in a synthesized signal that suffers from aliasing and image distortions
%even without any signal quantization. This problem is negated when the analysis
%and synthesis filters satisfy certain properties. This results in what is known as the
%quadrature mirror filter bank

A DWT-re épülő részsávos kódolás esetében belátható, hogy a \eqref{eq:scalecoeff} és a \eqref{eq:waveletcoeff} kifejezéskben található skála- és wavelet-függvények egymásba ágyazottak, vagyis egy $j$ skála paraméterhez tartozó skála-, ill. wavelet-függvény kifejezhető a $j+1$ skála paraméterhez tartozó skála, ill. wavelet függvények lineáris kombinációjaként:

%Since the scaling functions are nested, we can express the scaling functions 
%at scale j as a linear combination of the scaling functions in scale j + 1. 

\begin{equation}
\phi [2^jn-k]=\sum_{l} h_0 [l-2k] \sqrt{2} \phi[2^{j+1}n-l], 
\end{equation}
és
\begin{equation}
\psi [2^jn-k]=\sum_{l} h_1 [l-2k] \sqrt{2} \phi[2^{j+1}n-l], 
\end{equation}
ahol $l=m+2k$, és $h_0[m]$ es $h_1[m]$ a lineáris kombinációk együtthatói.

Ezek alapján belátható, hogy a DWT skála-, és wavelet együtthatóira is teljesül, hogy
\begin{equation}
W_{\phi} (j,k) = \sum_{l} h_0 [l-2k] \ W_{\phi} (j+1,l)
\end{equation}

\begin{equation}
W_{\psi} (j,k) = \sum_{l} h_1 [l-2k] \ W_{\psi} (j+1,l)
\end{equation}

A fenti kifejezések jelentősége az, hogy a $j$ skála paraméterhez tartozó skála-együtthatók megkaphatók a $j+1$ skálaparaméterhez tartozó együtthatóknak egy $h_0[-n]$ impulzusválaszú FIR szűrővel vett konvolúciójával, majd a szűrő kimenetének 2:1 arányú decimálásával, ahol $h_0[-n]$ a $h_0[n]$ imupluzválaszú FIR szűrő együtthatóinak időbeli fordítottja. Hasonlóképpen, a $j$ skála paraméterhez tartozó wavelet-együtthatók megkaphatók a $j+1$ skálaparaméterhez tartozó wavelet-együtthatók és egy $h_1[-n]$ impulzusválaszú FIR szűrő konvolúciójaként, majd a szűrő kimenetének 2:1 arányú decimálásával, ahol $h_1[-n]$ a $h_1[n]$ imupluzválaszú FIR szűrő együtthatóinak időbeli fordítottja. A szűrés, decimálás tetszőleges skála-szintig folytatható.

\begin{figure}
	\centering
	\includegraphics[width=0.8\textwidth]{fig/1D_dwt.png}
	\label{fig:1d_dwt_subband}
	\caption{Két szintű oktávsávos 1D DWT: (a) analízis szakasz, (b) szintézis szakasz}
\end{figure}


A jel visszaállítása során elindulunk a legmagasabb skála értékről, interpoláljuk 2:1 arányban a skála- és wavelet-együtthatókat, majd konvolváljuk őket a $g_0[n]$ és $g_1[n]$ impulzusválaszú FIR szűrőkkel. A két szűrő kimenetét összeadva megkapjuk a skála-együtthatókat egy alacsonyabb szinten. Az eljárást ismételve eljutunk a legalsó skála szintre, mely tulajdonképpen az eredeti jel.


%By inspecting equation (4.19), we can interpret the scaling coefficients at scale j
%as being obtained by convolving (or filtering) the scaling coefficients at scale j + 1
%by a filter h0 [-n] and retaining every other output sample. The filter with impulse
%response h0 [-n] is the time-reversed version of the filter h0 [n]. Similarly, we can
%interpret the wavelet coefficients at scale j as being obtained by filtering the wavelet
%coefficients at scale j + 1 by a filter h1 [-n] and retaining every other output sample.
%One can iterate the process of filtering the scaling coefficients by h0 [-n] and wavelet
%coefficients by h1 [-n] followed by subsampling by 2 to as many stages as required.
%However, in practice the number of stages of iteration is fixed at some value such
%that we have at least as many samples left as there are taps in the filters

%To reconstruct the sequence from its scaling and wavelet coefficients, we start
%at the highest scale, upsample the scaling and wavelet coefficients by 2, filter them
%through two filters g0 [n] and g1 [n], and add the two filtered outputs. This results in
%the reconstruction of the scaling coefficients at the next lower scale. The process is
%continued until the full-length signal is obtained. The two reconstruction or synthesis
%filters are simply the time-reversed versions of the corresponding analysis filters	.


\subsection{Wavelet szűrőbankok}

A jel Wavelet-filterbankokkal történő visszaállíthatóságának számos feltétele van. Ez első, hogy a $g_0[n]$ és $g_1[n]$ impulzusválaszú FIR szűrők átviteli karakterisztikájára teljesül, hogy

\begin{equation}\label{eq:powercomp}
|G_0(f)|^2 + |G_1(f)|^2=2
\end{equation}

A gyakorlatban ezenkívül fajta DWT bír jelentőséggel:

\subsubsection{Ortogonális DWT}

Ortogonális DWT felbontás esetén a szűrőbankra teljesül, hogy
\begin{itemize}
	\item A szűrő hossza $L$ páros
	\item páronként teljesül $g_0[n]$ és $g_1[n]$-re, $h_0[n]$ és $h_1[n]$-re, $h_0[n]$ és $g_1[n]$-re, és $g_0[n]$ és $h_1[n]$-re a \eqref{eq:powercomp} feltétel
	\item $g_0[n]$ és $h_0[n]$ szűrők egymás időbeli fordítottjai
	\item $g_1[n]$ és $h_1[n]$ szűrők egymás időbeli fordítottjai
	\item Teljesül, hogy $h_1[n]=(-1)^{n+1} h_0[L-1-n]$
	\item Teljesül, hogy $g_1[n]=(-1)^{n+1} g_0[L-1-n]$
	\item Teljesül, hogy $\sum h_0[n]=\sum g_0 [n]=2$
\end{itemize}

A $h_0[n]$ és $g_0[n]$ szűrők aluláteresztő jellegűek, míg 
$h_1[n]$ és $g_1[n]$ felüláteresztő jellegűek. Ortogonális DWT szűrőbankkal nem lehet linárfázisú karakterisztikát megvalósítani. Ezért bír gyakorlati jelentőséggel a biortogonális DWT szűrőbank: 

\subsubsection{Biortogonálisl DWT}

\begin{itemize}
	\item A szűrő hossza $L$ páros
	\item Mindegyik szűrő lineárfázisú (szimmetrikus együtthatókészlet)
	\item $g_0[n]$ és $h_0[n]$ szűrők nem egymás időbeli fordítottjai
	\item $g_1[n]$ és $h_1[n]$ szűrők nem egymás időbeli fordítottjai
	\item Teljesül, hogy $g_1[n]=(-1)^{n} h_0[n]$
	\item Teljesül, hogy $h_1[n]=(-1)^{n+1} g_0[n]$
	\item Teljesül, hogy $\sum h_0[n]=\sum g_0 [n]=\sqrt{2}$
\end{itemize}

\subsection{2D DWT}

A képtömörítési alkalmazások esetében az úgynevezett szeparábilis 2D DWT-t használják, mely esetben a 2D DWT egyszerűen és hatékonyan implementálható soronként, illetve oszloponként végzett 1D DWT-k egymásutánjaként.

Vegyünk egy $N\times N$-es méretű képet. Ha a kép sorait sorról sorra szűrjük a $h_0[-n]$ és $h_1[-n]$ szűrőegyütthatókkal, és minden szűrő kimenetét 2:1 arányban decimáljuk, akkor a szűrés után két $N\times N/2$ méretű együtthatóblokkot kapunk.
 Ezután, ha a $h_0[-n]$ szűrő kimenetének $N\times N/2$-es együtthatóblokkját  oszloponként szűrjük ismét a $h_0[-n]$ és $h_1[-n]$ szűrőegyütthatókkal, és szűrők kimenetét 2:1 arányban decimáljuk, akkor két $N/2\times N/2$ együtthatóblokkot kapunk eredményül. 
 
 Ezután az előző szint $h_1[-n]$ szűrőjének kimenetének $N\times N/2$-es együtthatóblokkját is oszloponként szűrjük ismét a $h_0[-n]$ és $h_1[-n]$ szűrőegyütthatókkal, és szűrők kimenetét 2:1 arányban decimáljuk, akkor két $N/2\times N/2$ együtthatóblokkot kapunk eredményül. 
 
 Ekkor eljutottunk a kép első szintű 2D DWT felbontásához. A négy darab $N/2\times N/2$ méretű együtthatóblokkot jelöljük rendre $y_{LL_1}$,$y_{HL_1}$, $y_{LH_1}$, $y_{HH_1}$ jelölésekkel. Az első helyen álló L, illetve H betű a sorirányú aluláteresztő ($h_0[n]$), illetve felüláteresztő ($h_1[n]$) szűrést, míg a második helyen álló álló L, illetve H betű az oszlopirányú aluláteresztő, illetve felüláteresztő szűrést jelzi. 
 
 Egy második szintű DWT számításához az $y_{LL_1}$ együtthatóblokk újabb 2D DWT transzformációjával jutunk. Ebben az esetben fa struktúrájú 2D DWT-ről beszélünk. Ha minden szinten nem csak a $y_{LL}$ együtthatókat, hanem mind a négy együtthatóblokkot 2D DWT transzformáljuk, akkor a teljes fa struktúrájú 2D DWT felbontást kapjuk.
 
 \begin{figure}
 	\centering
 	\includegraphics[width=0.9\textwidth]{fig/2D_dwt.png}
 	\label{fig:1d_dwt_subband}
 	\caption{Egy szintű 2D DWT számítása részsávos felbontással: (a) 2D
 		DWT, (b) együtthatók elhelyezkedése, és (c) inverz 2D DWT.}
 \end{figure}
 
 
%
%Starting with the given image of size N \times N pixels, we first filter it row by row by
%the filter h0 [-n] and h1 [-n], and retain every other sample at the filter outputs. This
%gives a set of two DWT coefficients each of size N x N2
%. Next, the DWT coefficients
%of the filter h0 [-n] are filtered again along each column by the same two filters and
%subsampled by 2 to yield two other sets of DWT coefficients of each size N2
%x N2
%.
%Finally, the DWT coefficients due to h1 [-n] are filtered along the columns by the
%same two filters and subsampled to give two other sets of DWT coefficients of each
%size N2
%x N2
%. We thus have one level of DWT of the image in question. Figure 4.9a
%depicts a one-level 2D DWT of an image of size N x N pixels. The four different
%DWT coefficients are labeled yLL1 [m, n], yHL1 [m, n], yLH1 [m, n], and yHH1 [m, n].
%The suffix LL stands for the output of the h0 [-n] filters in both dimensions, HL
%for the output of h1 [-n] along the rows first and then of h0 [-n] along the column,
%LH for the output of h0 [-n] first and then of h1 [-n], and finally HH stands for the
%outputs of h1 [-n] along both dimensions. The suffix 1 refers to the level number.
%The labeling of the four DWT coefficients is shown in Figure 4.9b. The inverse 2D
%DWT of the DWT coefficients to reconstruct the image is shown in block diagram
%form in Figure 4.9c.
%To obtain a second-level 2D DWT, one typically applies 2D DWT on the LL1
%coefficients using the same set of filters. This can be repeated iteratively. This is
%known as the tree-structured 2D DWT. Or, one can apply the computation of 2D
%DWT on each component at level 1 to obtain a level 2 full tree DWT.

A kép visszaállítása az 1D DWT-hez hasonlóan, a legmagasabb szintről indulva, a szintézis szűrőbankok felhasználásával történik.

\subsection{JPEG2000}

A transzformációs képtömörítési eljárások célja a pixelek közötti korreláció csökkentése egy alkalmasan megválasztott transzformált tartományban, amelyben az együtthatók közötti korreláció kisebb, és a jelenergia nagy részét néhány (kis számú) együttható reprezentálja. 
Ha ez teljesül, akkor a transzformáció a jelenergia szempontjából kompakt. Az alapvető különbség a hagyományos JPEG, és a hasonló blokk alapú DCT transzformációt használó eljárások (pl. MPEG) és a wavelet alapú JPEG2000 tömörítés között, hogy a 2D DWT transzformációt jellemzően a kép egészére alkalmazzák, és nem a kép $NxN$-es blokkjaira.
A 2D DWT egy szintjén tehát négy olyan együtthatóblokkot kapunk, mely az egész kép adott szintjéhez tartozó kisfrekvenciás közelítést, valamint a vízszintes, függőleges, és diagonális irányú részleteket (nagyfrekvenciás tartalmat) jellemzi,

%Compression of image data is achieved by removing the correlation among the pixels
%as in predictive coding or by compacting pixel energy in a few coefficients as in
%transform coding. The main difference between transform coding and wavelet domain
%coding is that wavelet transform is typically applied to the whole image unlike the
%transform coding where the transform is applied to subblocks. In two-dimensional (2D) DWT, an image is transformed into four distinct sets of
%coefficients giving an approximation of the image at a lower resolution, and three
%details with orientations in the horizontal, vertical, and diagonal directions.

%In octave-band decomposition the approximation
%coefficients of the first level are again decomposed into four sets of coefficients
%to obtain a two-level 2D DWT. This can be iterated further. On the other hand, in a
%full-tree DWT, each subband at each level is split into four subbands to obtain the
%next higher level DWT

A JPEG2000 tömörítés során a következő fő lépések végrehajtása történik:

\begin{itemize}
	\item Offszet, és komponens transzformáció: 8 bites komponens ábrázolás esetén a komponenseket +128 értékű offszettel írják le, majd komponens transzformáció következik. A komponens transzformáció lehet irreverzibilis, mely általában a hagyományos YCbCr transzformációt jelenti, és kerekítési hibákat visz a képi adatba. A reverzibilis komponens transzformáió (ICT) esetén az YCbCr komponensek a következők:
	\begin{equation*}
	Y = \left\lfloor \frac{R+2G+B}{4} \right\rfloor ;
	C_B = B - G ;
	C_R = R - G ; 
	\end{equation*}

\begin{equation}
	G = Y - \left\lfloor \frac{C_B + C_R}{4} \right\rfloor ;
	R = C_R + G ;
	B = C_B + G.
\end{equation}
 Ez a transzformáció nem jár kerekítési hibákkal, így a transzformáció reverzibilis, ugyanakkor a komponensek gyakorlatilag világosság, illetve színkülönbségi komponensek.
 \item Szelekekre (tile) bontás. A JPEG2000 esetén lehetőség van a kép szeletekre bontására, melyeken eltérű paraméterő tömörítés, skálázható minőség, stb. akalmazható. A legtöbb esetben azonban az egész kép egy szeletben történő tömörítését használják
 \item DWT transzformáció, mely lehet irreverzibilis, vagy reverzibilis. Az irreverzibilis DWT az ún. CDF (Cohen-Daubechies-Feauveau) 9/7 -es waveletet, míg a reverzibilis DWT a CDF 5/3 kerekített, biortogonális waveletet alkalmazza. Az irreverzibilis wavelet kvantálási hibát eredményez, ezért veszteséges.
 \item Kvantálás
 \item Kvantált együtthatók leképzése (Zero-tree coding) és entrópiakódolás
\end{itemize}

\subsubsection{Zero-tree kódolás (EZW)}

A ''zero-tree'' a nulla együtthatók fa struktúrájú elhelyezkedését jelenti. 
Az oktávsávos 2D DWT kódolás esetén az LL sáv minden szinten 4 részsávra osztódik, mely 4 részsáv a következő szintet alkotja.(quad-tree struktúra)
Tehát, bármely szinten az LH, HL és HH részsávok bármely együtthatójéhoz 4  együttható tartozik az eggyel alacsonyabb szinten.
Ha egy LH,HL, vagy HH együttható a legmagasabb szinten nulla, vagy elhanyagolható nagyságú, akkor nagy valószínűséggel az azonos részsávhoz tartozó, alacsonyabb szinteken vele kapcsolatban álló együtthatók is nullák vagy elhanyagolhatóak lesznek.

\begin{figure}
	\centering
	\includegraphics[width=0.8\textwidth]{fig/ezw.png}
	\label{fig:ezw}
	\caption{A 2D DWT fa-struktúrájú ábrázolása}
\end{figure}

Az EZW kódolás a fa struktúra hatékony entrópiakódolását jelenti, melynek korszerűbb, továbbfejlesztett változatait használják a JPEG2000 tömörítésben is.
A legmagasabb szint LH,HL és HH együtthatói az együttható-''családfa'' szüleinek tekinthetők, és az eggyel alacsonyabb szint 4 együtthatói a ''gyermekek''.
Az EZW kódolás során az együtthatók tárolása szukcesszív approximációval (''fokozatos közelítéssel'') iteratíven történik, melynek előnye, hogy tetszőleges iterációs szinten a folyamat leállítható, ha az adatok tárolására szánt bitmennyiség kimerült.
Az algoritmus vázlatosan:

\begin{itemize}
	\item a kép többszintű 2D DWT-jének kiszámítása
	\item A DWT együtthatók dinamikatartományának meghatározása
	\item $T_0$ küszöbszint beállítása a dinamikatartomány közepére
	\item Iteráció kezdete : minden következő iterációban a küszöbszintet a korábbi iteráció küszöbszintjének felére vesszük ($T_{j+1}=T_{j}/2$)
	\begin{itemize}
	\item Kvantálás: $T_j$ küszöbszint alatt ún. ''dead-zone'', azaz mindent nullára kvantálunk
	\item Kvantálás után a kvantált együtthatókhoz szimbólumok rendelése a következők szerint (\textit{domináns lépés}):
	\begin{itemize}
		\item Ha nulla, és minden belőle leszármazott együttható nulla : ZTR (zero-tree root)
		\item Ha az együttható nulla, de nem nulla (szignifikáns) leszármazottjai vannak: ISO (izolált nulla)
		\item Pozitív szignifikáns (POS)
		\item Negatív szignifikáns (NEG)
	\end{itemize}
	\item Két lista kezelése : \textit{domináns} lista, és \textit{szubordináns} lista
		\begin{itemize}
			\item Domináns lista: Adott iterációban még nem szignifikáns együtthatók listája
			\item Szubordináns lista: szignifikáns együthatók kódolt értéke 
		\end{itemize}
	\item \textit{Szubordináns lépés}:	Szignifikáns listáról az együtthatók következő legmagasabb bitsíkjának tárolása (első iterációban az MSB)
	\end{itemize}
		\item Küszöbszint felezése, új iteráció 
		\item Ha a felezett küszöbszint mellett a korábbi küszöbszinthez képest az együttható szignifikánssá válik, akkor eltávolítás a domináns listáról, és áthelyezés a szubordináns listára
\end{itemize}

\begin{figure}
	\centering
	\includegraphics[width=0.4\textwidth]{fig/ezw_zigzag.png}
	\label{fig:ezw_zig}
	\caption{Együtthatók leképzése, és kvantálási sorrend az EZW esetében}
\end{figure}


Az EZW kódolás során az együtthatók vizsgálata minden iterációban azonos sorrendben (cikk-cakk) leképzésben történik. A kvantálási küszöbök felezése miatt, az új iterációban mindig csak a következő bitsík tárolása szükséges.




\begin{figure}
	\centering
	\includegraphics[width=0.8\textwidth]{fig/ezw_quant.png}
	\label{fig:ezw_quant}
	\caption{Szukcesszív approximációs kvantálás, és a kvantálási intervallumok alakulása az EZW iterációkban}
\end{figure}


\subsection{DCP - Digital Cinema Package}

A digitális mozik disztribúciós formátuma, a DCP a JPEG2000-re épülő kizárólag intra-frame tömörítést használja a következő okok miatt: 
A DCT-re épülő blokk alapú kódolást alkalmazó MPEG kodek család (MPEG-1, MPEG-2, H264/AVC, HEVC, stb.) blokkosodási jelenségeket eredményez a blokkok határán, mely a blokkosodást gátló szűrők alkalmazása mellett is (H264,HEVC) láthatóvá válhat a képen - ez a mozikban nem engedhető meg. Ezenkívül az inter-frame, tehát képek közötti korrelációt is csökkentő prediktív kódolás (P és B képek) a hirtelen, gyors mozgásoknál, képváltásoknál a mozgás leképzés romlását eredményezheti, illetve ismét blokkosodást eredményezhet, mely a mozikban szintén nem engedhető meg.

 Az SMPTE által elfogadott digitális film disztribúciós csomag (DCP) formátumának főbb paraméterei:
 
 \begin{itemize}
 	\item JPEG2000 alapú intra-frame tömörítés
 	\item 24, 25, 30, 48, 50, és 60 Hz képfrekvencia támogatás 2K felbontás mellett
 	\item 24, 25, és 30 Hz képfrekvencia támogatás 4K felbontás mellett
 	\item 12 bit/komponens ábrázolás 
 	\item Tisztán exponenciális 2.6 gamma értékű gamma-korrekció
 	\item DCI-P3, vagy CIE XYZ színtér
 	\item Maximum bitráta: 250 Mbps
 	\item Felbontások:
 	 \begin{itemize}
 	 	\item Flat (1998x1080 vagy 3996x2160), 1.85:1 
 	    \item Scope (2048x858 vagy 4096x1716), 2.39:1
 	\item (U)HDTV (1920x1080 vagy 3840x2160), 16:9 
 	\item Full (2048x1080 vagy 4096x2160) 1.9:1 
 	 \end{itemize}
 \end{itemize}
 
\section{Ellenőrző kérdések} 

\begin{itemize}
	\item Mi a kapcsolat a DFT frekvencia és időfelbontása között ? (képlet)
	\item Milyen két paramétere van egy wavelet bázisfüggvénynek, ezek mit fejeznek ki (szemléletesen) ?
	\item  Rajzoljuk le vázlatosan az oktávsávos részsávos kódolás analízis, illetve rekonstrukciós szakaszát.
	\item Mi az alapvető különbség a JPEG és JPEG2000 transzformációs kódolása között ?
\end{itemize}
 
\section{Feladatok}

\subsection{1D DWT} 
 
Vonatkozó MATLAB script: \texttt{dwt\_1D\_example.m}

A script segítségével egy harmonikus, valamint tranziens komponensekből álló 1D diszkrét jel 2 szintű DWT-jét vizsgálhatjuk. 

\begin{itemize}
	\item Plotoljuk ki a jel harmonikus (\texttt{x1}) és tranziens (\texttt{x2}) komponenseit. 
	\item Vizsgáljuk meg az analízis és szintézis FIR szűrőket mind időtartományban, mind frequenciatartományban 
	\item Vizsgáljuk meg az első-, valamint a második szintű skála (approximation), és wavelet (detail) együtthatókat. Figyeljük meg a jel tranzienseinek megjelenési formáját az együtthatókban. Hol, és hogyan jelennek meg, és miért ott ?
	\item A kódban szerepelő \texttt{db8} ortogonális vagy biortogonális wavelet ?
\end{itemize}

\subsection{2D DWT}

Vonatkozó MATLAB script: \texttt{dwt\_2d\_example.m}
 
A script segítségével a cameraman ábra két szintű 2D DWT felbontását tekinthetjük meg.
\begin{itemize}
	\item Az LH,HL és HH részsávok közül mely felelős a vízszintes, a függőleges, és az átlós irányú részletekért ?
\end{itemize} 

\subsection{MATLAB WAVEMENU}

A \texttt{wavemenu} begépelésével egy szerteágazó grafikus toolbox segítségével vizsgálhatjuk a wavelet transzformációt, illetve az arra épülő tömörítési eljárásokat.

\begin{itemize}
	\item A \textit{One Dimensional/Wavelet-1D} gomb segítségével különböző jelekre vizsgálhatunk többszintű wavelet felbontás eredményeit:
	\begin{itemize}
		\item A File/Example analysis/Basic signals alatt ''előregyártott'' példa jelekre vizsgálhatjuk az 1D DWT felbontást
		\item Vizsgáljuk meg a Triangle+Sine és az Electrical consumption jelet db Wavelet 2,4, és 8 szintű felbontása mellett
		\item Értelmezzük a Display mode/Full decomposition at Levels ... szintek állítása esetén az együtthatókat
		\item Vizsgáljuk meg az együtthatók hisztogramjait
		\item Értelmezzük az eredményeket
	\end{itemize}
	\item \textit{A Specialized Tools/True compression 2D} gomb használatával vizsgálhatjuk pl. az EZW tömörítés működését. Töltsünk be egy képet, értelmezzük a grafikus felületet.
	
	\begin{itemize}
		\item Mi a hatása és szerepe a Nb. of encoding loops beállításnak ?
		 \item Milyen hatása van annak, hogy hány szintű DWT felbontás történik ?
		\item Használjuk az Inspect Wavelet tree gombot. Próbáljuk meg értelmezni a látottakat.
	\end{itemize}
\end{itemize}
	
\subsection{JPEG és JPEG2000 összehasonlítása}

Vonatkozó MATLAB script : \texttt{JPEG\_vs\_JPEG2000.m}

A kód segítségével előre beállított minőségi lépcsőket definiálhatunk: a minőségi szintet a JPEG esetében a \texttt{Q\_JPEG} definiálja 1 és 100 között, a JPEG2000 esetében a tömörítési arányt a \texttt{CR\_JPEG2000}, melynek értéke egynál nagyobb (pl. \texttt{CR\_JPEG2000=10} esetén a cél fileméret 10\%-a az eredetinek.) 
A JPEG esetében a minőségi szint nem jelent közvetlenül bitsebességvezérlést.

A kód a beállított lépcsőkkel elvégzi a bemeneti kép kódolását, és az eredményezett fileméret függvényében megjeleníti a PSNR, valamint az SSIM értékeket. Szintén információt kapunk a kódolási, illetve dekódolási időkről.

Ezen kívül lehetőség van a forrásfájl egy adott, megközelítőleg azonos fileméretet eredményező JPEG és JPEG2000 tömörítéssel kódolt változatainak összehasonlítására.



\end{document}
