\documentclass[a4paper,12pt,lithuanian]{article}

\usepackage[lithuanian]{babel}
%\usepackage[utf8x]{inputenc}
\usepackage{lietuvybe}
\usepackage{type1cm}
%\usepackage[L7x]{fontenc}
%\usepackage{ae,aecompl}
\usepackage[a4paper,margin=2.3cm]{geometry}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{hyperref}
\usepackage[all]{hypcap}
\usepackage{amsmath}
\usepackage{multirow}
\input{baltic}

\makeatletter
\renewcommand\normalsize{\@setfontsize\normalsize{13pt}{23pt}}\normalsize
\makeatother

\def\sech{\mathop{\rm sech}\nolimits}

\renewcommand{\topfraction}{0.85}
\renewcommand{\textfraction}{0.1}
\renewcommand{\floatpagefraction}{0.75}

\setlength{\emergencystretch}{3em}

\newtheorem{apibrezimas}{apibr��imas}


\begin{document}

\newcommand{\atandu}{\mathop{\mathrm{atan2}}}

%\input{ch_summ_title_lt.tex}

\section{Vaizd� vidurkinimas ir po�ymi� i�skyrimas}

\subsection{Glodus vienmatis eksponentinis filtras}

Apibr��ime eksponentin� tolyd� kintamojo $x$ filtr� formule
\begin{equation}
\label{eq:ef}
v_\sigma(x) = \left(1 + \frac{|x|}{\sigma} \right) e^{-\frac{|x|}{\sigma}},   x \in (-\infty,\infty).
\end{equation}
�ia $\sigma$ yra filtro parametras. Kad filtro reik�m�s gest� begalyb�je, reikalausime, kad $\sigma>0$. Nesunku patikrinti, kad su bet kokia fiksuota parametro $\sigma>0$ reik�me filtras yra du kartus tolyd�iai diferencijuojamas at�vilgiu kintamojo $x$. Tod�l �� filtr� vadinsime {\em glod�iu eksponentiniu filtru}.

Bet kokiam signalui $u=u(x)$, filtravimo operacija apibr��iama formule

\begin{equation}\label{konvoliucija}
( u \star v_\sigma)(x) = \int_{-\infty}^\infty u(y) v_\sigma(x-y) dy = \int_{-\infty}^\infty v_\sigma(y)u(x-y) dy.
\end{equation}
Skaitmenini� signal� atveju laikoma, kad 
\begin{equation}\label{skaitmeninis}
 u(x) = \sum_{n=-\infty}^\infty u_n \delta(x-n),
\end{equation}
kur $\delta=\delta(x)$ yra delta-dirako funkcija pasi�yminti savybe
\begin{equation}\label{dirako}
 \int_{-\infty}^\infty \delta(y) \phi(y) dy = \phi(0)
\end{equation}
visoms glod�ioms integruojamoms funkcijoms $\phi=\phi(x)$.Pasinaudoj� (\ref{skaitmeninis}) ir (\ref{dirako}) lygyb�mis, gauname toki� filtravimo operacijos i�rai�k�:

\begin{equation}\label{konvoliucija}
( u \star v_\sigma)_n = \sum_{m=-\infty}^\infty u_m v_\sigma(n-m) = \sum_{m=-\infty}^\infty v_\sigma(m)u_{n-m}, n = 0,\pm1, \pm2, \cdots.
\end{equation}
Atlikime filtravimo operacij� �vienetiniam� skaitmeniniam signalui, t. y. signalui
$$u(x) = \sum_{n=-\infty}^\infty \delta(x-n).$$
Pasinaudoje filtravimo formul�, visiems sveikiesiems $n$, gausime
$$
( u \star v_\sigma)_n = \sum_{m=-\infty}^\infty v_\sigma(n-m) = \sum_{m=-\infty}^\infty v_\sigma(m) = \sum_{m=-\infty}^\infty (1+\frac{|m|}{\sigma})e^{-\frac{|m|}{\sigma}}.$$
Pritaik� geometrin�s progresijos  sumos formul� rasime
$$
\sum_{m=-\infty}^\infty e^{-\frac{|m|}{\sigma}} = \frac{1+e^{\frac{-1}{\sigma}}}{1-e^{\frac{-1}{\sigma}}}.$$
Kadangi
$$
\sum_{m=0}^\infty m e^{m t} = (\sum_{m=0}^\infty e^{m t})^\prime_t=\frac{e^t}{(1-e^t)^2},$$
tai galutinai gauname
\begin{equation}\label{qsigma}
( u \star v_\sigma)_n = \sum_{m=-\infty}^\infty (1+\frac{|m|}{\sigma})e^{-\frac{|m|}{\sigma}}=
\frac{\sigma(1-e^{\frac{-2}{\sigma}})+2e^{\frac{-1}{\sigma}}}{\sigma(1-e^{\frac{-1}{\sigma}})^2}=\frac{1}{q(\sigma)}.
\end{equation}
Modifikuosime glodaus eksponentinio filtro apibr��im� taip, kad jo atsakas � vienetin� skaitmenin� signal� b�t� lygus 1. Kad tai pasiekti pakanka (\ref{eq:ef}) de�ini�j� pus� padauginti i� normuojan�io daugikli $q(\sigma)$ apibr��to formule (\ref{qsigma}). Tokiu b�du gauname toki� normuot� eksponentinio filtro i�rai�k�:
\begin{equation}
\label{eq:nef}
v_\sigma(x) = \frac{\sigma(1-e^{\frac{-1}{\sigma}})^2}{\sigma(1-e^{\frac{-2}{\sigma}})+2e^{\frac{-1}{\sigma}}}\left(1 + \frac{|x|}{\sigma} \right) e^{-\frac{|x|}{\sigma}},   x \in (-\infty,\infty).
\end{equation}

Kei�iant eksponentinio filtro parametr� $\sigma$ galima pasiekti norim� signalo vidurkinimo lyg�. Kuo $\sigma$ ar�iau nuliui, tuo filtravimo operacija ma�iau glodina filtruojam� signal� ir atvirk��iai didinant parametro $\sigma$ reik�m� didiname vidurkinimo laipsn�. 
\begin{figure}[htp]
\centering
\includegraphics[scale=1]{figures/expo_filtras}
\label{fig:expo_filtras}
\caption{Glod�i� eksponentini� filtr� $v_\sigma$ grafikai. M�lynas $\sigma=1$, juodas $\sigma=2$, �alias $\sigma=8$}
\end{figure}

I�siai�kinsime kaip efektyviai atlikti skaitmeninio signalo vidurkinim� eksponentiniu filtru. Reali� skaitmenini� signal� �inom� skaitmenini� reik�mi� kiekis b�na baigtinis. Tarkime �inome
$$u_0, u_1, u_2, \cdots, u_{N-1}$$
reik�mes. Laikysime, kad filtruojamo signalo kra�tin�s reik�m�s $u_0$ ir $u_{N-1}$ prat�stos tolyd�iai, t. y.
$$ u_n\equiv u_0, \mbox{ kai } n<0 $$
ir
$$ u_n\equiv u_{N-1}, \mbox{ kai } n\ge N.$$
Kad supaprastinti formules, prad�ioje nera�ysime normuojan�io daugiklio. I�skaidysime filtravimo operacijos sum� � dvi dalis:
$$
( u \star v_\sigma)_n = \sum_{m=-\infty}^\infty v_\sigma(m)u_{n-m}=
	-u_n+\sum_{m=0}^\infty (1+\frac{m}{\sigma})e^{\frac{-m}{\sigma}}u_{n-m}+
	\sum_{m=0}^\infty (1+\frac{m}{\sigma})e^{\frac{-m}{\sigma}}u_{n+m}.$$
U�ra�ydami i�skaidymo formul� pasinaudojome filtro simetri�kumu, t. y. savybe $v_\sigma(x)=v_\sigma(-x)$.
Prad�ioje raskime
\begin{equation}\label{uv0p}
(u\star v0_\sigma^+)_n=\sum_{m=0}^\infty e^{\frac{-m}{\sigma}}u_{n-m}.
\end{equation}
Kadangi visiems neigiamiems indeksams $u_{n-m}=u_0$, tai 
$$(u\star v0_\sigma^+)_0=\frac{1}{1-e^{\frac{-1}{\sigma}}}u_0.$$
Teigiamiems indeksams $n>0$  galime u�ra�yti rekurentin� ry��
$$(u\star v0_\sigma^+)_{n}=e^{\frac{-1}{\sigma}}(u\star v0_\sigma^+)_{n-1}+u_n.$$
Dabar apskai�iuokime
\begin{equation}\label{uv1p}
(u\star v1_\sigma^+)_n=\sum_{m=0}^\infty me^{\frac{-m}{\sigma}}u_{n-m}.
\end{equation}
D�l kairiosios kra�tin�s s�lygos gauname
$$(u\star v1_\sigma^+)_0=\frac{e^{\frac{-1}{\sigma}}}{(1-e^{\frac{-1}{\sigma}})^2}u_0,$$
o teigiamiems indeksams $n>0$  galime u�ra�yti s�ry��
\begin{eqnarray}
(u\star v1_\sigma^+)_{n}&=&\sum_{m=0}^\infty me^{\frac{-m}{\sigma}}u_{n-m}=\sum_{m=0}^\infty (m+1)e^{\frac{-m-1}{\sigma}}u_{n-1-m}\nonumber\\
&=&e^{\frac{-1}{\sigma}}((u\star v1_\sigma^+)_{n-1}+(u\star v0_\sigma^+)_{n-1}), n = 1,2,\cdots,N-1.\label{v1prec}
\end{eqnarray}

Analogi�kai raskime
\begin{equation}\label{uv0m}
(u\star v0_\sigma^-)_n=\sum_{m=0}^\infty e^{\frac{-m}{\sigma}}u_{n+m}.
\end{equation}
Kadangi visiems indeksams $m\ge 0$ $u_{N-1+m}=u_{N-1}$, tai 
$$(u\star v0_\sigma^-)_{N-1}=\frac{1}{1-e^{\frac{-1}{\sigma}}}u_{N-1}.$$
Likusiems indeksams $n$  galime u�ra�yti s�ry��
$$(u\star v0_\sigma^-)_{n}=e^{\frac{-1}{\sigma}}(u\star v0_\sigma^-)_{n+1}+u_n.$$
Liko apskai�iuoti
\begin{equation}\label{uv1m}
(u\star v1_\sigma^-)_n=\sum_{m=0}^\infty m e^{\frac{-m}{\sigma}}u_{n+m}.
\end{equation}
D�l de�iniosios kra�tin�s s�lygos gauname
$$(u\star v1_\sigma^-)_{N-1}=\frac{e^{\frac{-1}{\sigma}}}{(1-e^{\frac{-1}{\sigma}})^2}u_{N-1},$$
o kitiems indeksams $n\ge 0$  galioja s�ry�is
\begin{eqnarray}
(u\star v1_\sigma^-)_{n}&=&\sum_{m=0}^\infty me^{\frac{-m}{\sigma}}u_{n+m}=\sum_{m=0}^\infty (m+1)e^{\frac{-m-1}{\sigma}}u_{n+1+m}\nonumber\\
&=&e^{\frac{-1}{\sigma}}((u\star v1_\sigma^-)_{n+1}+(u\star v0_\sigma^-)_{n+1}), n = N-2,N-3,\cdots,0.\label{v1mrec}
\end{eqnarray}
Galutin�s filtravimo formul�s su normuojan�iu daugikliu atrodo taip:
\begin{equation}\label{rec_filtr}
( u \star v_\sigma)_n =q(\sigma)((u\star v0_\sigma^+)_n+\frac{(u\star v1_\sigma^+)_n}{\sigma}+(u\star v0_\sigma^-)_n+\frac{(u\star v1_\sigma^-)_n}{\sigma}-u_n).
\end{equation}

\subsection{Filtruoto vienma�io signalo i�vestin�s}
Pateiktos formul�s tinka pradinio skaitmeninio signalo greitam glodinimui. Kad apskai�iuoti $v0^+_n$ ,  $v0^-_n$, $v1^+_n$ ir  $v1^-_n$ reikia vienos daugybos ir vienos sud�ties, o galutiniam normuotam filtravimo rezultatui gauti reikia atlikti dar dvi daugybas ir tris sud�ties/atimties operacijas, taigi m�s� filtravimo algoritmo sud�tingumas yra 6 daugybos ir 7 sud�ties operacijos  vienam ta�keliui.  Ta�iau praktikoje da�nai reikia ne tik suglodinti pradin� signal� bet ir �vertinti jo pirm�j� ir antr�j� i�vestines. I�vestin�s da�niausiai yra aproksimuojamos pirmosios ir antrosios eil�s skirtumais. Ta�iau m�s� atveju galima apskai�iuoti tiksliai filtruoto signalo i�vestines. Formaliai diferencijuodami gauname
\begin{equation}\label{konvoliucijis_isvestine}
( u \star v_\sigma)^\prime(x) = \int_{-\infty}^\infty u(y) v_\sigma^\prime(x-y) dy = \frac{-q(\sigma)}{\sigma^2}\int_{-\infty}^\infty u(y)(x-y)e^{-\frac{|x-y|}{\sigma}} dy.
\end{equation}
Diskre�iu atveju tiksli filtruoto signalo i�vestin�s formul� su normuojan�iu daugikliu atrodo taip:
\begin{equation}\label{konvoliucijos_diskreti_isvestine}
( u \star v_\sigma)^\prime_n =  \frac{-q(\sigma)}{\sigma^2}\sum_{m=-\infty}^\infty me^{-\frac{|m|}{\sigma}} u_{n-m}=\frac{-q(\sigma)}{\sigma^2}((u \star v1^+_\sigma)_n-(u \star v1^-_\sigma)_n).
\end{equation}
I� (\ref{konvoliucijos_diskreti_isvestine}) formul�s matome, kad i�saugojus tarpinius glodinimo filtravimo rezultatus, i�vestines apskai�iavimo papildomos s�naudos yra minimalios, tiksliau, kad apskai�iuoti filtruoto skaitmeninio signalo i�vestin� viename ta�kelyje $n$ reikia atlikti vien� sud�ties ir daugybos operacij�.

Analogi�kai rasime tiksli� antrosios eil�s i�vestin�s formul�. Formaliai diferencijuodami du kartus filtravimo rezultat�, gauname
\begin{equation}\label{konvoliucijos_isvestine_antra}
( u \star v_\sigma)^{\prime\prime}(x) = \int_{-\infty}^\infty u(y) v_\sigma^{\prime\prime}(x-y) dy = \frac{-q(\sigma)}{\sigma^2}\int_{-\infty}^\infty u(y)(1-\frac{|x-y|}{\sigma})e^{-\frac{|x-y|}{\sigma}} dy.
\end{equation}
Diskre�iu atveju filtruoto signalo antrosios eil�s i�vestin�s formul� yra tokia:
\begin{eqnarray}
( u \star v_\sigma)^{\prime\prime}_n &=&  \frac{-q(\sigma)}{\sigma^2}\sum_{m=-\infty}^\infty (1-\frac{|m|}{\sigma})e^{-\frac{|m|}{\sigma}} u_{n-m}\nonumber\\
&=&\frac{-q(\sigma)}{\sigma^2}((u \star v0^+_\sigma)_n-\frac{(u \star v1^+_\sigma)_n}{\sigma}+(u \star v0^-_\sigma)_n-\frac{(u \star v1^-_\sigma)_n }{\sigma}-u_n).\label{konvoliucijos_diskreti_antra_isvestine}
\end{eqnarray}
Taigi v�l gauname ekonomi�k� tiksl� antrosios eil�s i�vestin�s apskai�iavimo algoritm�, kurio sud�tingumas yra 2 daugybos ir 4 sud�ties/atimties operacijos. Reikia pasteb�ti, kad jei m�s� filtras neb�t� du kartu tolyd�iai diferencijuodamas, tai formalus i�vestini� �k�limas po konvoliucijos (filtravimo) integral� �enklu duot� klaidingas formules. Ta�iau net ir su glod�iu filtru gauname, kad konstantos antrosios eil�s i�vestin� yra nenulin�, o etalonini� signal� $u_n=n$ ir $u_n=n^2$ vidurkintos reik�m�s ir j� i�vestin�s tiksliai nesutampa su laukiamomis reik�m�mis. Kad i�taisyti �ias filtr� ydas, reikalausime, kad visi filtrai b�t� apskai�iuot� pagal (\ref{uv0p}), (\ref{uv1p}), \ref{uv0m} ir \ref{uv1m} i�rai�kas funkcij� tiesiniai dariniai, vidurkintas signalas nekeist� vienetin� ($u_n=1$ )ir kvadratin� ($u_n=n^2$) signalus, tiesinio signalo ($u_n=n$)  i�vestin� b�t� lygi vienetiniam signalui ir  ir kvadratinio signalo $u_n=n^2$  i�vestin� b�t� lygi konstantai $2$. Pagal �ias s�lygas gauname tokias galutines formules:
\begin{eqnarray}
\overline{u}_n & = & a_0((u\star v0_\sigma)_n-u_n)+b_0(u\star v1_\sigma)_n, \mbox{ (vidurkintas signalas) } \label{u_vid}\\
\overline{u}^\prime_n &=& a_1(u \star v1^+_\sigma)_n+b_1(u \star v1^-_\sigma)_n,
\mbox{ (vidurkinto signalo i�vestin�) } \label{u_vid_isv}\\
{\overline{u}^{\prime\prime}}_n &=& a_2((u \star v0_\sigma)_n-u_n)+b_2(u\star v1_\sigma)_n, \mbox{  (antrosios eil�s i�vestin�) }, \label{u_vid_antra_isv}
\end{eqnarray}
kur
\begin{eqnarray}
{v0_\sigma}_n & = & {v0_\sigma^+}_n+{v0_\sigma^-}_n,  \label{v0}\\
{v1_\sigma}_n & = & {v1_\sigma^+}_n+{v1_\sigma^-}_n,  \label{v1}\\
q^0(\sigma) &=& \sum_{m=-\infty}^\infty e^{-\frac{|m|}{\sigma}} = (1+e^{\frac{-1}{\sigma}})/(1-e^{\frac{-1}{\sigma}}), \label{q0}\\
q^1(\sigma) &=& \sum_{m=-\infty}^\infty |m|e^{-\frac{|m|}{\sigma}} = 2*e^{\frac{-1}{\sigma}}/(1-e^{\frac{-1}{\sigma}})^2, \label{q1}\\
q^2(\sigma) &=& \sum_{m=-\infty}^\infty m^2e^{-\frac{|m|}{\sigma}} = 2e^{\frac{-1}{\sigma}}(1+e^{\frac{-1}{\sigma}})/(1-e^{\frac{-1}{\sigma}})^3, \label{q2}\\
q^3(\sigma) &=& \sum_{m=-\infty}^\infty |m|^3e^{-\frac{|m|}{\sigma}} = 2e^{\frac{-1}{\sigma}}(1+4*e^{\frac{-1}{\sigma}}+e^{\frac{-2}{\sigma}})/(1-e^{\frac{-1}{\sigma}})^4, \label{q3}
\end{eqnarray}
o daugikliai $a$ ir $b$ randami i� lyg�i�
\begin{eqnarray}
a_0 q^0(\sigma)+b_0 q^1(\sigma) &=& 1,\\
a_0 q^2(\sigma)+b_0 q^3(\sigma) &=& 0,\\
a_1 q^2(\sigma)+b_1 0& =&-1,\\
a_1 0+b_1*q^2(\sigma) &=&1,\\
a_2 q^0(\sigma)+b_2 q^1(\sigma) &=& 0,\\
a_2 q^2(\sigma)+b_2 q^3(\sigma) &=& 2..
\end{eqnarray}
Alternatyvus koeficent� $a_0$ ir $b_0$ apibr��imo variantas:
\begin{eqnarray}
 a_0 &=& \frac{a_2}{a_2 q^0-b_2 q^1}, \label{a0Alter}\\
 b_0 &=& \frac{-b_2}{a_2 q^0-b_2 q^1}. \label{b0Alter}
\end{eqnarray}
Skai�iuojant $a_0$ ir $b_0$ pagal �ias formules vidurkinta konstanta
i�lieka ta pa�ia konstanta ir i�laikoma simetrija: $a_0=\mbox{const } a_2$, $b_0=\mbox{const } b_2$.

\subsubsection{Praktin� vienma�i� signal� vidurkinimo u�duotis}
{\em
Para�yti program�, kuri apskai�iuot� duoto skaitmeninio signalo suglodinim� eksponentiniu filtru ir rast� suglodinto signalo pirm�sias ir antr�sias i�vestines. Algoritmo testavimui imkite tokius duomenis:
$$ u_n = \left\{ \begin{array}{rcl}
-1, &\mbox{ kai }& n<100,\\
3, &\mbox{ kai } &n<200,\\
2, &\mbox{ kai } &n<300,
\end{array}\right.
$$
$$
\sigma=2.
$$
}
Dumenys kiekvieno algoritmo �ingsnio testavimui: $\sigma = \frac{1}{\log2}$,
$$\begin{array}{rccccc}

u&=&64&32&64&128,\\
{(u\star v0_\sigma^+)}&=&128&96&112&184,\\
{(u\star v1_\sigma^+)}&=&128&128&112&112,\\
{(u\star v0_\sigma^-)}&=&128&128&192&256,\\
{(u\star v1_\sigma^-)}&=&176&224&256&256.\end{array}$$
$a_0=\frac{13}{27}$, $b_0=\frac{-1}{9}$, $a_1=\frac{-1}{12}$, $b_1=\frac{1}{12}$
$a_2=\frac{-2}{27}$, $b_2=\frac{1}{18}.$\\
$$\begin{array}{cccccc}

\overline u &=& \frac{13}{27}192 - \frac{1}{9}304&\frac{13}{27}192 - \frac{1}{9}352&\frac{13}{27}240 - \frac{1}{9}368&\frac{13}{27}312 - \frac{1}{9}368,\\
\overline u &=& \frac{176}{3}&\frac{160}{3}&\frac{223}{3}&\frac{327}{3},\\
\overline u^\prime &=& 4&8&12&12,\\
\overline u^{\prime\prime} &=& \frac{8}{3}&\frac{15}{3}&\frac{7}{3}&\frac{-8}{3}.\end{array}$$

%Kontrolin�s testavimo duomen� reik�m�s: $\overline u_{100} = 1.720,  \overline u^\prime_{100}=0.500, \overline u^{\prime\prime}_{100}=-0.059$.

Atlikite filtravim� etaloniniams duomenis $u_n=1$, $u_n=n$ ir $u_n=n^2$ ir pakomentuokite gautus filtravimo rezultatus.

�ioje ir kitose programose neb�tina realizuoti vartotojo grafin� s�saj�.

{\em Vertinama iki 0.75 egzamino bal�. Jei d�l nepateisinam� prie�as�i� atsiskaitoma v�liau nei keturios savait�s nuo pirm�j� pratyb�, u� kiekvienos savait�s v�lavim� vertinimas ma�inamas 0.25 balo.}
\input{dvimatisVidurkinimas.tex}

\begin{thebibliography}{}
%

\bibitem{bib:zc} Bill Green, http://www.pages.drexel.edu/~weg22/edge.html
\bibitem{bib:skelet} K\'alm\'an Pal\'agyi, Vengrija, http://www.inf.u-szeged.hu/~palagyi/skel/skel.html
\bibitem{bib:skeletRealizacijos} K. Stukas, J. Janauskas, �. Gruodis, M. Bra�i�kis, http://www.mif.vu.lt/~bastys/academic/ATE/skaiciai/skaiciu\_atp.htm\#Praktinis
\bibitem{bib:rutovic} D. Rutovitz, Pattern Recognition, J. Roy. Statist. Soc., vol. 129, pp. 504-530, 1966.
\bibitem{bib:ypatingiTaskai} Feng Zhao and Xiaoou Tang, CISST�02 International Conference, http://mmlab.ie.cuhk.edu.hk/2002/CISST02\_Fingerprint.pdf, (Lokali kopija http://mif.vu.lt/~bastys/academic/ATE/pirshtai/CISST02\_Fingerprint.pdf)
\bibitem{bib:ZhangSuen} T. Y. Zhang, C. Y. Suen, A fast parallel algorithm for thinning digital patterns, Communications of the ACM, v.27 n.3, p.236-239, March 1984.\\
Realizacija Java kalba: http://www.mif.vu.lt/atpazinimas/skaiciai/skelet/ZhangSuen.java

\end{thebibliography}

\end{document}

\end{document}
