\documentclass{beamer}
% \documentclass[handout]{beamer}
   % classes "beamer", "xcolor" and "pgf" are in the /home/olegm/ directory
 
\usepackage{beamerthemeDresden}
\def \hilite<#1>{
\temporal<#1>{\color{gray}}{\color{blue}}{\color{black}}
} 

\def \hilites<#1>{
\temporal<#1>{\color{white}}{\color{black}}{\color{black}}
} 
\newtheorem{deft}{Definition}
\newtheorem{ther}{Theorem}
\title{Inverse problems and application to image deblurring}

\author{Oleg Makhnin\\ New Mexico Tech\\ Dept. of Mathematics }
\date{October 29, 2010}
\definecolor{mystructure}{rgb}{.5,.5,.5}
\definecolor{mystructure2}{rgb}{1,.99,.92}
% \definecolor{mystructure}{rgb}{.8,.8,1}
% \definecolor{mystructure2}{rgb}{0.1,0.1,1}
\setbeamercolor{structure}{fg=mystructure2, bg=mystructure}


 \newcommand{\giv}{\ | \ }
 
  \newcommand{\hsp}{\hspace*{0.25in}} 
  \newcommand{\vsp}{\vspace*{0.1in}} 
    \newcommand{\vnsp}{\vspace*{-0.1in}} 
   \newcommand{\hnsp}{\hspace*{-0.4in}}
 \newcommand{\umu}{\mbox{\boldmath $\mu$}}
  \newcommand{\bV}{{\bf V}}
  \newcommand{\bW}{{\bf W}}  
    \newcommand{\bY}{{\bf Y}}
    \newcommand{\bx}{{\bf x}}
   \newcommand{\bd}{{\bf d}}
   \newcommand{\be}{{\bf e}}
   \newcommand{\bO}{{\bf 0}}

     \newcommand{\bxhat}{\hat{\bf x}}

        \newcommand{\bX}{{\bf X}}
        \newcommand{\bh}{{\bf h}}
	\newcommand{\bv}{{\bf v}}
 \newcommand{\bSig}{\mbox{\boldmath $\Sigma$}}
 \newcommand{\bbet}{\mbox{\boldmath $\beta$}}
 \newcommand{\Xbar}{\overline{X}}
  \newcommand{\R}{\mathbb{R}}
 
  \newcommand{\parf}[2]{ #1_#2}
  \newcommand{\parfd}[2]{#1_{#2 #2}}
  %  \newcommand{\parf}[2]{\frac{\partial #1}{\partial #2}}
  %   \newcommand{\parfd}[2]{\frac{\partial^2 #1}{\partial #2 \mbox{}^2}}
   \newcommand{\dst}{\displaystyle}
   
   \newcommand{\red}{\color[rgb]{1,0,0}}
   \newcommand{\blue}{\color[rgb]{0,0,1}}
   \newcommand{\brown}{\color[rgb]{0.7,0.3,0}}
   \newcommand{\navy}{\color[rgb]{0.1,0,0.5}}
   \newcommand{\black}{\color[rgb]{0,0,0}}

\begin{document}

\frame{\titlepage}

\section{Intro}
\frame{
\frametitle{}
  \hilite<2> Intro: inverse problems \vsp \\
 %
  \hilite<3> Tikhonov Regularization \vsp \\
  %
  \hilite<4> Image deblurring/ deconvolution \vsp \\ 
   % 
  \hilite<5> CGLS solution, use of $\ell_1$ norm \vsp \\
 %
  \hilite<6> Fourier approach \vsp \\
  %
  \hilite<7> Beyond
}

\frame{
\frametitle{Intro: inverse problems}

 \begin{itemize}[<+->] 
   \item \hnsp
Forward problem 
   $$ G (\bx) = \bd $$ 
 where $\bx$ is the "state" vector (typically hidden) and $\bd$ is your data vector.

 $G$ is assumed known. Its estimation is an additional challenge.

 The equation may be {\blue overdefined} (in this case the solution is fitted in the least squares sense), or \vsp 

 {\blue underdefined} in which case
we have to pick "the best" solution, and some features of "true" $\bx$ might be lost.  

   \item \hnsp
 Linear problem: when $G(\cdot)$ is given by the multipication by the matrix $G$.

   \item \hnsp
Parabola example. 

\end{itemize} 
}


\frame{
\frametitle{Intro: inverse problems}

 \begin{itemize}[<+->] 

 \item \hnsp
Inverse problem: 
  $$ \bx = G^{-1} \bd \hsp ??$$ 

What if $G$ is not square, or square but not invertible? 

 \item \hnsp
In {\blue overdefined} case we can solve approximately, which leads to 
well-known 
   $$ \bxhat = (G^T G)^{-1} G^T \bd$$  

 \item \hnsp
In general, let's say 
   $$ \bx = G^{\sharp} \bd $$ 
 where $G^{\sharp}$ is {\em pseudoinverse} of $G$.
  
   \item \hnsp
 However, noise is usually present:  \hsp  $ G \bx = \bd + \be$ \\
   \hsp and this complicates matters 

\end{itemize} 
}

\section{Tikhonov reg.}

\frame{
\frametitle{Intro: ill-posed problems}
 \begin{itemize}[<+->] 

  \item \hnsp
  Ill-posedness:  Two Ellipses pic \vsp
 
   \item \hnsp 
  Thus, the need to regularize the solution, i.e. pick $G^{\sharp}$ which is not quite the inverse ($G^{\sharp} G \ne I$).  This is known as "noise suppression" in signal processing.
 
  \item \hnsp 
 Tikhonov regularization: instead of optimization problem 
  $$  \bxhat = \arg \min_\bx  \|  G \bx - \bd \|^2 $$
%
  solve the problem 
   $$  \bxhat = \arg \min_\bx \left[ \ \|  G \bx - \bd \|^2  +  \alpha^2  \|  L \bx \|^2  \ \right] $$
 where the latter is a penalty term ($\alpha$ = some scalar parameter).


\end{itemize} 
}

\frame{
\frametitle{Tikhonov reg.: $ \min \left[  \|  G \bx - \bd \|^2 + \alpha^2  \|  L \bx \|^2   \right] $  }
 \begin{itemize}[<+->] 

\item \hnsp
 "0-order Tikhonov regularization"  when $L = I$ \\
 i.e. punish "large" solutions.

 
\item \hnsp  Equivalent to the extended Least Squares problem
  $$ \left[ \begin{array}{c}
          G \\   \alpha L \end{array} \right] \bx = 
    \left[ \begin{array}{c}
         \bd \\ \bO   \end{array} \right] 
$$ 


\item \hnsp 
 Tradeoff between "fit" and "solution norm". Pic: L-curve

\item \hnsp Demo: Filtering a 1-D signal


\end{itemize} 
}

\section{Image deblurring}

\frame{
\frametitle{Image deblurring}
 aka Deconvolution \vsp

 Forward problem: blurring the image $\bx$ by applying some matrix $G$. 

 What $G$ does: transforms a single pixel into a spread-out shape described by {\blue PSF (point-spread function)}. 

 \includegraphics[height = 2in, width = 3.7in]{blur_ex.jpg}

 }



\frame{
\frametitle{Image deblurring}

The image on the rectangular grid is reshaped into the vector $\bx$.

Assume that PSF is known. \vsp

Apply CGLS (Conjugate Gradients for Least Squares) - iterative method with
no need to explicitly form $G$. \vsp 

In fact, stopping CGLS early acts as a regularizer of sorts. \vsp 


}


\frame{
\vnsp
\hnsp \includegraphics[width = 5in, height = 3in]{true_img.jpg}

}

\frame{
\frametitle{}

\vnsp
\hnsp \includegraphics[width = 5in, height = 3in]{restoreCGLS.jpg}

}

\frame{
 \begin{itemize}[<+->] 
   \item \hnsp
 Looks promising: use $L$ = finite difference matrix.
 This supresses wiggly behavior.  \vsp

 Another idea: to reduce smoothing (allow for sharper transitions), we
might use $\ell_1$ norm instead of $\ell_2$ norm. To find the solution, try {\blue IRLS = iteratively reweighted least squares}. It pays extra attention to rows of $G$ that produce large residuals. \vsp

 Again, revisit the toy 1d problem \vsp

  \item \hnsp
So let's use IRLS together with CGLS to iterate towards a better estimate 
 (one iteration inside the other)

 \end{itemize}
}


\frame{ 
 Iterations 1 and 3:\\
\hnsp \includegraphics[width = 3in, height = 3in]{restoreL1_01iter1.jpg}
%  
\hnsp \includegraphics[width = 3in, height = 3in]{restoreL1_01iter3.jpg}


}

\section{Fourier}

\frame{
\frametitle{Fourier methods}

FFT (fast Fourier transform) can be used to do blurring, {\red really fast}. \vsp

 Multiplication in frequency domain = convolution in $\bx$-domain. \vsp

 Inverse Fourier transform does something akin to 
Tikhonov regularization. (After we suppress higher harmonics.) \vsp
  

But: how do we employ the penalty term/ $\ell_1$ norm for it?

 (see the Gibbs phenomenon)
 
} 



\section{Beyond} 

\frame{
\frametitle{Beyond}


\hnsp  What if the PSF is unknown? {\blue ``Blind deconvolution''} \vsp

 Some recent progress has been made: \vsp


 $\bullet$ Shan, Jia and Agarwala, 2008. {\em High-quality Motion Deblurring from a Single Image.} ACM Trans. Graph. 27, 3 \vsp


 $\bullet$   Levin, Weiss, Durand and  W. T. Freeman. {\em Understanding and evaluating blind deconvolution algorithms.}
IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), June 2009. \vsp

Both assume that PSF is the same at each location
}

\frame{
\frametitle{Beyond}
 \begin{itemize}[<+->] 
   \item \hnsp
Other issues: 

   $\bullet$  Denoising \vsp 

   $\bullet$  Image inpainting  \vsp \vsp 

    \item \hnsp 
Possible research projects: 

 $\bullet$ Can we use Fourier methods? If yes, how do we regularize them? \vsp 

  $\bullet$  Allowing for PSF to vary between locations \vsp 


\end{itemize}

}







\frame{
\begin{center} \vspace{.25in} \LARGE{QUESTIONS?} \end{center}
}

\frame[containsverbatim]{
\begin{center} \vspace{.25in} \LARGE{THANK YOU!} \vsp \\

  see \verb"www.nmt.edu/~olegm/talks/Deblur2" 
\end{center}
}

\end{document}





