%% Eduardo Martinez Pedroza.
%%
%% Note from the author:  My dissertation document was created with this file. It passed the general formatting guidelines for PhD dissertations
%% of the Graduate College at the University of Oklahoma. I accept no responsibility in connection with the use of this file. Use it under your own risk.
%%

\documentclass[12pt]{report}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Standard AMS packages
\usepackage{amssymb, amsmath, amsthm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  For mathematical diagrams
\usepackage{xypic}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% For inserting graphic files
\usepackage{graphicx} %
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{float}
\usepackage{pdflscape}
\usepackage{graphics}
\usepackage{algorithm}
\usepackage{algorithmic}
%\usepackage{stfloats}
\usepackage{dblfloatfix}
\usepackage{cite}
\usepackage{subfig}
\usepackage{multirow}
\usepackage{amsmath}
\usepackage{url}
\usepackage{rotating}
% \linespread{2}
\usepackage[table]{xcolor}

\usepackage{graphicx}
% \usepackage{amsthm}
%\usepackage{booktabs}
\usepackage{amsmath,amssymb}
\usepackage[normalem]{ulem}
\usepackage{kbordermatrix} %http://www.hss.caltech.edu/~kcb/TeX/kbordermatrix.sty
\usepackage{blkarray}
\usepackage{color}
\usepackage{color}
\newtheorem{thm}{Theorem}%[section]
%\newtheorem{cor}[thm]{Corollary}
\newtheorem{cor}{Corollary}%[section]%[chapter]
\newtheorem{prop}{Proposition}%[section]%[chapter]
\newtheorem{lem}{Lemma}%[section]%[chapter]
\newtheorem{fact}{Fact}%[section]%[chapter]
% \theoremstyle{definition}
\newtheorem{rem}{Remark}%[section]
\newtheorem{property}{Property}
\newtheorem{definition}{Definition}%[section]%[chapter]
\newtheorem{exam}{Example}%[section]%[chapter]
% \numberwithin{equation}{section}
% \numberwithin{definition}{section}
% \numberwithin{lem}{section}
% \numberwithin{thm}{section}
% \numberwithin{rem}{section}
% \numberwithin{figure}{section}
\usepackage{algorithm}
\usepackage{algorithmic}
% \usepackage{algorithmicx}
\usepackage{enumerate}
\usepackage{slashbox}
\usepackage{dblfloatfix}
\usepackage{cite}
\usepackage{subfig}
\usepackage{multirow}

% \definecolor{myred}{rgb}{1,0,0} 
% \definecolor{myblue}{rgb}{0,0,1}

%  \def\showcomment{}

\definecolor{myred}{rgb}{0,0,0} 
\definecolor{myblue}{rgb}{0,0,0}
\definecolor{samred}{rgb}{1,0,0}

\ifdefined\showcomment
  \newcommand{\ths}[1]{{\textcolor{green}{#1}}}
  \newcommand{\scc}[2]{{\textcolor{green}{#2}} {\textcolor{red}{(#1)}}}
  \newcommand{\comm}[1]{\emph{\textcolor{red}{\textbf{SC:}#1}}}
 \newcommand{\delete}[1]{\sout{#1}}
 \newcommand{\replace}[2]{{\textcolor{green}{#1}} \sout{#2}}
\else
  \newcommand{\ths}[1]{#1} % remove comment
  \newcommand{\scc}[2]{#2} % remove comment
  \newcommand{\comm}[1]{} % remove comment
  \newcommand{\delete}[1]{} % remove comment
\newcommand{\replace}[2]{#1}
\fi



\renewcommand*\contentsname{Table of Contents}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Hyper-references
%\usepackage[pdftex, plainpages=false]{hyperref}   %To be use with PDF-TEX

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Graduate college required margins
% \usepackage[left=1.8in, top=1.4in, right=1.4in, bottom=1.4in]{geometry}

\usepackage[left=1.6in, top=1in, right=1in, bottom=1in]{geometry}
% \usepackage[left=2in, top=1.5in, right=1.5in, bottom=1.5in]{geometry}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% line spacing
\usepackage{setspace}
    %\singlespacing
    %\onehalfspacing
    \doublespacing
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% To set the chapter sizes
\usepackage{titlesec}
 
\titleformat
{\chapter} % command
[display] % shape
{\bfseries\large} % format
{\centering CHAPTER \ \thechapter} % label
{0.5ex} % sep
{
%     \rule{\textwidth}{1pt}
%     \vspace{1ex}
    \centering
} % before-code
[
%  \vspace{-0.5ex}%
% \rule{\textwidth}{0.3pt}
] % after-code
 
 
 \titleformat{\section}
 {\normalfont\large\bfseries}
 { \thesection}{.5cm}{}
%  
% \titlespacing{\section}{12pc}{1.5ex plus .1ex minus .2ex}{1pc}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Personal Environments and Commands
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
% \newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}{Example}
\numberwithin{equation}{chapter}
\numberwithin{figure}{chapter}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% My commands
\newcommand{\reals}{\mathbb{R}}   %Real numbers' symbol
\newcommand{\hyperbolic}{\mathbb{H}}  %Hyperbolic symbol
\newcommand{\complex}{\mathbb{C}} %Complex numbers' symbol
\newcommand{\integers}{\mathbb{Z}}   %Integer numbers' symbol
\newcommand{\presentation}[2]{\langle \, #1  \, | \, #2 \,  \rangle}
\newcommand{\GammaH}{Cayley (G, X\cup \widetilde{\mathcal{H}}) }
\newcommand{\Hs}{\{ H_i \}_{i=1}^m}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% THESIS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

% \ifdefined\showcomment
%   \newcommand{\ths}[1]{{\textcolor{green}{#1}}}
%   \newcommand{\scc}[2]{{\textcolor{green}{#2}} {\textcolor{red}{(#1)}}}
%   \newcommand{\comm}[1]{\emph{\textcolor{red}{\textbf{SC:}#1}}}
%  \newcommand{\delete}[1]{\sout{#1}}
%  \newcommand{\replace}[2]{{\textcolor{green}{#1}} \sout{#2}}
% \else
%   \newcommand{\ths}[1]{#1} % remove comment
%   \newcommand{\scc}[2]{#2} % remove comment
%   \newcommand{\comm}[1]{} % remove comment
%   \newcommand{\delete}{} % remove comment
% \newcommand{\replace}[2]{#1}
% \fi


\title{IMAGE AND VIDEO ENHANCEMENT USING SPARSE CODING, BELIEF PROPAGATION AND MATRIX COMPLETION}
\author{NAFISE BARZIGAR}
\date{November 2014}

\pagenumbering{roman}
{%% PAGE NUMBERING ROMAN

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TITLE PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\singlespacing

\newpage
\thispagestyle{empty}
\begin{center}
{ %\large
UNIVERSITY OF OKLAHOMA
\par
\vspace{0.16in}
GRADUATE COLLEGE
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
IMAGE AND VIDEO ENHANCEMENT USING SPARSE CODING, BELIEF PROPAGATION AND MATRIX COMPLETION
\par
% \vspace{0.17in}
% RELATIVELY HYPERBOLIC GROUPS
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A DISSERTATION
\par
\vspace{0.17in}
SUBMITTED TO THE GRADUATE FACULTY
\par
\vspace{0.17in}
in partial fulfillment of the requirements for the
\par
\vspace{0.17in}
Degree of
\par
\vspace{0.17in}
DOCTOR OF PHILOSOPHY
\par
\vfill
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
By
\par
\vspace{0.17in}
NAFISE BARZIGAR
\par
%\vspace{0.05in}
Norman, Oklahoma
\par
%\vspace{0.05in}
2014
}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% SIGNATURE PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\thispagestyle{empty}
\begin{center}
{%\large
IMAGE AND VIDEO ENHANCEMENT USING SPARSE CODING, BELIEF PROPAGATION AND MATRIX COMPLETION
\par
%\vspace{0.17in}
% RELATIVELY HYPERBOLIC GROUPS
% \par
\vspace{0.9in}
A DISSERTATION APPROVED FOR THE
\par
%\vspace{0.17in}
SCHOOL OF ELECTRICAL AND COMPUTER ENGINEERING
\par
\vspace{0.9in}
BY
\par
\vfill
\begin{flushright}
\begin{tabular}{cr}
\hline
\  \  \  \  \  \  \  & Dr. Samuel Cheng, Chair\\
 \\ &  \\
  \\ &  \\
\hline
  & Dr. Pramode Verma, Co-chair \\
\\ & \\
 \\ &  \\
\hline
& Dr.  Jerzy Bodurka\\
\\   & \\
 \\ &  \\
\hline
  & Dr. James Sluss \\
 \\ &  \\
  \\ &  \\
\hline
   & Dr. William Ray \\
\end{tabular}
\end{flushright}
}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% COPYRIGHT PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\thispagestyle{empty}
\   \
\par
\vfill
\begin{center}
\copyright \    Copyright by NAFISE BARZIGAR \   2014

All rights reserved.
\end{center}
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ACKNOWLEDGEMENTS PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter*{Acknowledgements}
I would never have been able to finish my dissertation without the guidance of my committee members, help from friends, and support from my family and 
husband.

I would like to express my deepest gratitude to my advisor, Dr. Samuel Cheng, for his great guidance, caring, patience, and providing me with an excellent atmosphere for doing research. The joy and enthusiasm he has for his research was contagious and motivational for me, even during tough times in the Ph.D. pursuit. And special thanks to Dr. Pramode Verma for his trust, mentoring, support, and providing me the opportunities to assist in teaching telecommunications classes and managing the telecommunication lab. Thank you. I appreciate all his contributions of time, ideas, and funding to make my Ph.D. experience productive and stimulating.

To the members of my doctoral committee Dr. James Sluss, Dr. Jerzy Bodurka, and Dr. William Ray, I express my gratitude for their advice and suggestions at the beginning of my research work. Particular thanks to Dr. Jerzy Bodurka for his kind support, encouragement, and his faith in me. I would like to thank the OU Tulsa Graduate College Dean, Dr. William Ray, for providing me the  opportunities to assist in teaching the ``Stochastic Processes'' course.	

I would like to thank Mrs. Renee Wagenblatt for her kind support, help and patiently editing my writing. I am grateful for the opportunity to meet talented and supportive researchers and students at OU-Tulsa. I extend a big ``thank you'' to our OUSAM lab group, specially Lijuan, Shuang, Feng, and Anusha, and to Dr. Bodurka's expert lab members at Laureate Institute for Brain Research (LIBR).

I express my deepest gratitude to many friends who have meant so much to me and who have provided much encouragement, especially Atie, Somaye, Saeed, Alireza, Mohammad, Mahnaz, Soode, Amirreza, Aziz, Hajagha, Parisa, Athena, Sepideh, Mahsa, Fahime, my ``Safora'' classmates, Nilo, Andy, Mrs. Borbor, Mrs. Fallah, Mr. Ahmadinia, Mr. Steve Trinkle, and Dr. Salimian.

I especially thank my beloved mom, dad, sisters, and brothers. My hard-working parents have sacrificed their lives for my siblings and myself and provided unconditional love and care. I love them so much, and I would not have made it this far without them. Special thanks to Amin, my husband as well as his wonderful family who all have been supportive and caring.

The best outcome from these past five years is finding my best friend, soul-mate, and husband, Amin. I married the best person out there for me. There are no words to convey how much I love him. Amin has been a true and great supporter and has unconditionally loved me during my good and bad 
times. 
% and for being a excellent mentor.  I am grateful for having had the opportunity to work with him.
% 
% I also wish to thank ....

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TABLE OF CONTENTS PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{
% \singlespacing
\tableofcontents
\listoftables
\listoffigures
}
\newpage

} %% END PAGE NUMBERING ROMAN


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% INTRODUCTION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter*{Abstract}
Super resolution as an exciting application in image processing was studied widely in the literature. This dessertion presents new approaches to  video super resolution, based on sparse coding and belief propagation. 
% I employ two novel techniques for my proposed approach. 
First, 
% \scc{what candidate pixels? need to describe why not how}
\ths{find} 
% {{the best matches as }}
\ths{candidate match pixels on multiple frames using sparse coding and belief propagation}. Second, incorporate information from these candidate pixels 
%and average out noises 
% by exploiting self-similarity of candidate pixels 
{ with weights computed
using the Nonlocal-Means (NLM) method {in the first approach or using SCoBeP method in the second approach}}. 
% to average out the noise among similar patches. 
The effectiveness of the proposed methods is demonstrated for both synthetic and real video sequences in the \ths{experiment} section. In addition, the experimental results show that my models are naturally robust in handling super resolution on video sequences {{\replace{affected by scene motions and/or small camera motions}{with motions in camera or scene}}}. 

Moreover, in this dissertation, I describe a denoising method using low-rank matrix completion. In the proposed denoising approach, I present a patch-based video denoising algorithm by grouping similar patches and then formulating the problem of removing noise using a decomposition approach for low-rank matrix completion. Experiments show that the proposed approach robustly removes mixed noise such as impulsive noise, Poisson noise, and Gaussian noise from any natural noisy video. Moreover, my approach outperforms state-of-the-art denoising techniques such as VBM3D and 3DWTF in terms of both time and quality. My technique also achieves significant improvement over time against other matrix completion methods.



\chapter{INTRODUCTION}
\pagenumbering{arabic}
Today, with advances in sensor design, the given image is relatively clean for digital cameras, but it remains noisy and blurry for low-grade and mobile phone cameras. Thus the super resolution problem is still of acute importance, and I present a novel learned image model method, which outperforms the-state-of-the-art, super resolution task on real and synthetic low sequences. 
Sparse representation techniques are beginning to show significant impact on image processing \cite{mairal2009non,dabov2007image,yang2010image,wang2010resolution}\replace{.}{, often on denoising and super resolution where the goal is not just to obtain a compact high-fidelity representation of the observed image, but also to extract semantic information} 
Also, the results of these methods illustrate that the sparse representation can be correctly recovered from the downsampled signals.

In addition, Images %of similar or differing 
\ths{from various}
modalities need to be denoised as a pre-processing step for many planning, navigation, detection, data-fusion and visualization tasks in medical applications \cite{maintz1998survey,roozgard2012Malignant}. Video sequences are often corrupted by noise during acquisition or transmission. CT slices are often corrupted by noise during acquisition or transmission. \scc{bad sentence, noise becomes active sound awkward}{Noises are added in the CT slices during acquisition by CT scanner sensors \cite{ali2010ga}. Some noise sources located in camera hardware became active during image acquisition under some lighting conditions. Other noise sources are over transmission channels. Most video denoising algorithms proposed in the literature assume additive white Gaussian noise, which can be categorized into pixel domain and transform domain methods. However, I consider Impulsive/Poisson/Gaussian noise in my work and will show how robust my denoising method is.} The goal of my denoising method is to keep only the reliable pixels and get rid of all other un-reliable pixels I find as noise. For each patch in the reference frame, I find the similar patches in the other frames using a block matching algorithm. The found matches will be vectorized and then stacked into a matrix. The reliable pixel values in the matrix are between the mean $\pm$ standard deviation of all elements in the same row. The main step will be done by applying the matrix completion approach \cite{ma2014decomposition} on the incomplete matrix. The output of matrix completion is a noise free full matrix. Then, the average value of each row in the full matrix can recover the denoised patch. Repeating the same procedure for all blocks of reference frame can build a denoised frame.

%  Plenty of works have emerged lately based on this problem such as computer vision \cite{tomasi1992shape} and machine learning \cite{graepel2002kernel,abernethy2006low,amit2007uncovering}.
% }}
% \scc{too vague}{On the heels of compressed sensing, a new technique for acquiring information from a highly incomplete matrix has been recently emerged.} 
%  \scc{order not right, you explained matrix completion in the next paragraph}{In the simplest case of matrix completion, the problem is to recover an incomplete matrix from a small sample of its entries. The recovery can be for a matrix with incomplete data or even corrupted information.}



\section{Classic Super Resolution}\label{SR_Back} 
% \cite{farsiu2004fast}
Super resolution reconstruction attempts to estimate one high quality result $\mathcal{X}$ out of several \replace{lower resolution and potentially noisy}{low quality} images $\begin{Bmatrix} \mathcal{Y}_t \end{Bmatrix}^T_{t=1}$. 
% \delete{which are typically noisy, LR observations.}
A popular way to model LR images $\begin{Bmatrix} \mathcal{Y}_t \end{Bmatrix}^T_{t=1}$ from a pseudo HR image $\mathcal{X}$ is through a sequence of operations \replace{including}{. The operations include} geometrical wrapping $F_t$, linear space-invariant blurring $H$, spatial decimation $D_t$, and zero-mean white Gaussian noise $\varepsilon_t$. The model \replace{can be summarized with}{is represented by} the following equation:
\begin{equation}
\mathcal{Y}_t = DHF_t\mathcal{X}+\varepsilon_t,\ \ \  t=1,2,3,...,{T},
\label{eq:SRmodel}
\end{equation}
where ${T}$ is the number of available LR frames. Note that I assume $H$ and $D$ are identical for all frames in the sequence.
% As I briefly described, $F_v$ is the geometric wrap operator between the latent clean and sharp frame $\mathcal{X}$ and the $v^{th}$ low-resolution frame  $\begin{Bmatrix} \mathcal{Y}_v \end{Bmatrix}^T_{v=1}$. The blur matrix $H$ denotes the camera's point spread function (PSF), and $D$ represents the subsampling operator. $\varepsilon_v$ is actually assumed as an additive Gaussian noise term and


The recovery of $\mathcal{X}$ from $\begin{Bmatrix} \mathcal{Y}_t \end{Bmatrix}^T_{t=1}$ using the above mentioned model requires us to solve an inverse problem. The maximum\textit{ a posteriori} probability estimate of $\mathcal{X}$ \replace{can be obtained}{is given} by minimizing the following \replace{objective}{penalty} function with respect to $\mathcal{X}$:
\begin{equation}
\epsilon^2_{MAP}(\mathcal{X}) = \frac{1}{2}\sum_{t=1}^{T}\left \| DHF_t\mathcal{X}-\mathcal{Y}_t \right \|^2_2 +\lambda \cdot TV(\mathcal{X}),
\label{eq:MAP}
\end{equation}
{{where \ths{the first summation term ensures that the  projections of the estimate $\mathcal{X}$ looks similar to the LR images and}  \ths{the second term,} $\lambda \cdot TV(\mathcal{X})$, \replace{acts as a prior and}{as a prior, which} helps to remove artifacts from the final solution and improves the rate of convergence \cite{rudin1992nonlinear}.


% can be introduced to help to remove artifacts from the final solution and improve the rate of convergence.
}}
% maximum-likelihood (ML)
% {\color{red}{Reviewer 1:In section IV.B (second part) please state your cost function first, then describe how it is optimized. Right now there are $\epsilon_{DB}$ and $\epsilon_{ML}$, so it is not clear what the cost function is.
% 
% 
% Reviewer 3: The major drawback of the proposed algorithm is the lack of rigorousness and a proof of convergence of the proposed methodology. Particularly, the authors have failed to give a rigorous algorithm because,
% a) do not use the observation model they defined in (2); rather, they modify the standard super-resolution data-likelihood term appearing in (2) in order to introduce a new data-likelihood term in place of the last in (11). This is performed without any rigorous justification, despite the fact that it subsequently introduces NL-means in the method.
% b) the prior model they use is a TV prior, though the term prior used herein is not accurate, since the authors do not use probabilistic methods. however, they claim that prior knowledge to the problem is incorporated also by the weights computed in the first step by SCoBeP. I feel that using two sources of priors is a bit  awkward in the point of view of an  image processing expert.
% 
% The modeling must be the following:
% define a two (or more) term function of the original image and the low-resolution images. the first term must be the data-likelihood term, where no prior information must be included. The second (or other)terms must be the prior knowledge or else, the constraints incorporated for the solution. The estimate of the HR image is taken by minimizing this function. However, the authors propose two functions independently from each other, $\epsilon_{DB}$ and $\epsilon_{ML}$, and they minimize each one independently, while maintaing artificially a connection between them by using Z in both of them. I would expect the connecting variable to be X and not the observations Z. This is not clearly a rigorous algorithm and this does not make sense to me.
% 
% 
% 
% }}


% \comm{Explain the expression first, move the description about TV up here}
{{

% can be computed in a few ways, I continue with the assumption that ${W_{t}}$ are known and I will explain their computation in Section (\ref{SR_Weight}).

% \delete{My mission is minimizing the function (\ref{eq:MAP}) that has two terms: $\epsilon^2_{ML}$ and a regularization.}
% (such as TV which helps to remove artifacts from the final solution and improves the rate of convergence \cite{rudin1992nonlinear}). 
{ {Since $H$ and $F_t$ are space-invariant operators in (\ref{eq:MAP}), they can be considered as block circulant matrices (assuming a cyclic boundary treatment) that they commute  \cite{farsiu2004fast,farsiu2004advances}.}}
\replace{This allows one to solve \eqref{eq:MAP} in the following two steps}{
Following the methods developed in} \cite{farsiu2004fast,protter2009super,Protter09generalizingthe,farsiu2004advances}\replace{.}{, I also define $\mathcal{Z}=H\mathcal{X}$ as a blurred version of the HR frame $\mathcal{X}$, and we}
\replace{First,}{first} minimize the following penalty function with respect to $\mathcal{Z}$:
\begin{equation}
\epsilon^2_{ML}(\mathcal{Z}) = \frac{1}{2}\sum_{t=1}^{T}\left \| DF_t\mathcal{Z}-\mathcal{Y}_t \right \|^2_{2},
\label{eq:PMLZ}
\end{equation}
\ths{where $\mathcal{Z}$ can be interpreted as a blurred version of the HR frame $\mathcal{X}$ and thus should be approximately equal to $H\mathcal{X}$.} { {This step estimates the blurry high-resolution image $\mathcal{Z}$ from the collection of the low resolution images $\mathcal{Y}$. For a more general case with multiple input patches, I will modify $\epsilon^2_{ML}$ in (\ref{eq:PMLZ}) to (\ref{eq:ML}) as shown in Section \ref{DeblurDenoise_Steps}.}}

Then, \ths{impose the constraint of the closeness of $\mathcal{Z}$ and $H\mathcal{X}$} and incorporate \ths{back the} regularization \ths{term} to obtain \replace{the following objective function:}{an approximate MAP estimator as follows:}

\begin{equation}
\epsilon^2_{MAP}(\mathcal{X})=\left \| H\mathcal{X}-\mathcal{Z} \right \|_2^2+\lambda \cdot TV(\mathcal{X}),
\label{eq:ZX}
\end{equation}
\ths{where $\mathcal{X}$ can be obtained through minimizing \eqref{eq:ZX} { {in Section \ref{SR_Weight}. Since $H$ is usually singular, this stage is an under-determined problem and needs regularization (see \cite{pan2006efficient,osher2005iterative} for more detail).}}}

% substitute $\mathcal{Z}=H\mathcal{X}$ back to \eqref{eq:PML}, I have
% Since $H$ and $F_v$ are space-invariant operators in (\ref{eq:PML1}), they can be considered as block circulant matrices. As a result, they commute ($F_vH=HF_v$ and $F_v^TH^T = H^TF_v^T$). Also, following the methods developed in \cite{farsiu2004fast,protter2009super,Protter09generalizingthe}, I define 
% $\mathcal{Z}=H\mathcal{X}$ as the blurred version of the HR image $\mathcal{X}$, and rewrite (\ref{eq:PML}) as
% \begin{eqnarray}\nonumber
% \epsilon^2_{ML}(\mathcal{Z})&=
% &\frac{1}{2}\sum_{v=1}^{T}\sum_{b=1}^{n}\sum_{[q,l]\in \mathcal{I}}\sum_{[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlv})}}\mathcal{W}[i,j,q,l,b,v] 
% \\ \nonumber
% &&\times \left \| DR^H_{q,l}\mathcal{Z}-R^L_{i,j}y_v \right \|^2_2 ,\\ 
% \label{eq:PMLZ}
% \end{eqnarray}
% and I can solve for $\mathcal X$ approximately using two-part optimization
% \cite{farsiu2004fast,protter2009super,Protter09generalizingthe}.
% The key idea is that $\epsilon^2_{MAP}$ can be shown to be smaller than $\epsilon^2_{ML} + \epsilon^2_{DB}$ by triangle inequality. 
% % \begin{equation}
% % \epsilon^2_{ML}(\mathcal{Z}) = \frac{1}{2}\sum_{u=1}^{U}\sum_{v=1}^{T}\left \| DF_u\mathcal{Z}-\mathcal{Y}_v \right \|^2_{\mathcal{W}_{u,v}}.
% % \label{eq:PMLZ}
% % \end{equation}
% Then, I use the found $\mathcal{Z}$ to estimate $\mathcal{X}$ by minimizing 
\replace{In summary,}{More precisely,} \replace{one}{we} can break \replace{the}{our} minimization problem \ths{in \eqref{eq:MAP}} in two steps:
\begin{enumerate}
 \item compute a blurred version of HR $\mathcal{Z}$ by minimizing (\ref{eq:PMLZ}). \label{step1}
 \item estimate the deblurred frame $\mathcal{X}$ from the found blurred HR $\mathcal{Z}$ in step \ref{step1}.
\end{enumerate}


As the second step only involves the %a well-known 
classic deblurring problem, many potential techniques can be applied here. In my proposed approaches, I \replace{adopt}{have only tested}  the \textit{Adaptive Kernel Total Variation} (AKTV) regularized locally-adaptive kernel regression in a variational approach developed by Takeda \textit{et al.} \cite{takeda2008deblurring}, which can simultaneously interpolate and deblur in one integrated step. However, one can generally incorporate any deblurring techniques into the proposed method. 
% \cite{chan1998total,beck2009fast,biemond1990iterative,wang2007fast} for more information about this field. 



% As for the first step, one can show that $\mathcal{Z}$ can be computed as
% \cite{Protter09generalizingthe}
% %  (see Appendix)
% % Thus, I concentrate on the first step in finding a blurry HR frame $\mathcal{Z}$.
% \begin{equation}
% \hspace{-15pt}
% \mathcal{Z}[q,l] = \frac{\sum_{v=1}^{V}\sum_{b=1}^{n}\sum_{[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlv})}}\mathcal{W}[i,j,q,l,b,v]y_v[i,j]}{\sum_{v=1}^{V}\sum_{b=1}^{n}\sum_{[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlv})}}\mathcal{W}[i,j,q,l,b,v]}.
% \label{eq:finalz}
% \end{equation}
}}


% {\color{red}{
% I should find the best set of $D, H$, and $F$, which can represent the model and show that the distance between the simulated and the original $\begin{Bmatrix} \mathcal{Y}_v \end{Bmatrix}^V_{v=1}$ is minimum. Thus, I can minimize this penalty term with respect to $\mathcal{X}$ by zeroing its derivative
% 
% \begin{equation}
% \frac{\partial \epsilon^2_{ML}(\mathcal{X})}{\partial \mathcal{X}} = \sum_{v=1}^{V}F^T_vH^TD^T(DHF_v\mathcal{X}-\mathcal{Y}_v)=0,
% \label{eq:MLZero}
% \end{equation}
% which leads to the relationship
% \begin{equation}
% (\sum_{v=1}^{V}F^T_vH^TD^TDHF_v)\hat{\mathcal{X}}_{ML} = \sum_{v=1}^{V}F^T_vH^TD^T\mathcal{Y}_v.
% \label{eq:MLopen}
% \end{equation}
% 
% Then, I introduce TV-regularization to help remove artifacts from the final solution and improve the rate of convergence \cite{rudin1992nonlinear}. So (\ref{eq:ML}) becomes
% \begin{equation}
% \epsilon^2_{MAP} (\mathcal{X})= \epsilon^2_{ML}(\mathcal{X})+ \lambda .TV(\mathcal{X}),
% \label{eq:MAP}
% \end{equation}
% where the above can be interpreted as the \textit {a posteriori} probability (MAP) in Bayesian Statistics with $\lambda TV(X)$ as a prior.
% 
% Substitute (\ref{eq:ML}) into (\ref{eq:MAP}); and I have the MAP estimate to be the minimizer of 
% \begin{equation}
% \epsilon^2_{MAP} (\mathcal{X})= \frac{1}{2}\sum_{v=1}^{V}\left \| DHF_v\mathcal{X}-\mathcal{Y}_v \right \|^2_2 + \lambda .TV(\mathcal{X}),
% \end{equation}
% which can be found by an iterative algorithm \cite{farsiu2004fast,chantas2007super,Protter09generalizingthe,takeda2009super}. 
% 
% }}
\section{Background of NLM Filter}\label{SR_RW}
The whole entity of a self-similar object is exactly like or similar to a part of itself. As a consequence, parts of it can show the same statistical properties at many scales. \replace{Based on this presumption, non-local self-similarity techniques have}{A Non-local self-similarity technique has} been widely used in \ths{areas} such as image denoising \cite{buades2005non,buades2006review}, texture synthesis \cite{efros1999texture}, and super resolution \cite{zhang2010non,protter2009super,Protter09generalizingthe}. For example, the NLM filter\ths{, which} is based on the assumption that image content is likely to repeat itself within its neighborhood\ths{, is applied successfully to image denoising}. \replace{Its key idea is that}{Accordingly,} one can denoise a pixel $[i,j]$ by performing weighted average around its neighborhood \cite{buades2006review}. More precisely, denote $\mathcal{Y}[i,j]$ as the intensity of pixel $[i,j]$, then the intensity of denoised pixel $[q,l]$, $\mathcal{X}[q,l]$, can be 
written as

\begin{equation}
\mathcal{X}[q,l] = \frac{\sum_{(i,j) \in \mathcal{N}(q,l)}  \mathcal{W}[i,j,q,l] \mathcal{Y}[i,j]}{\sum_{(i,j) \in \mathcal{N}(q,l)} \mathcal{W}[i,j,q,l]},
\label{eq:1}
\end{equation}
where $\mathcal{N}(q,l)$ denotes a neighborhood around pixel $[q,l]$, and  $\mathcal{W}[i,j,q,l]$ is a weight that is decreased with the distances between pixels $[i,j]$ and $[q,l]$, and increased with the similarity of the patches centering at the two pixels. { {The formula in (\ref{eq:1}) describes the NLM filter where denoising each pixel is done by averaging all pixels in its neighborhood. However, this averaging is not performed blindly  and instead each pixel in the relevant neighborhood is assigned a weight which corresponds to the probability that the pixel $\mathcal{Y}[i,j]$ and the pixel $\mathcal{X}[q,l]$, prior to the additive noise degradation, had the same value.}}

NLM filter computes the weight based on both radiometric proximity and geometric proximity between the pixels. The radiometric part is estimated by computing the Euclidean distance between two image patches centered around these two included pixels. Let us consider $R_{q,l}$ as the matrix that extracts a patch with fixed and predefined size \ths{of} $g \times g$ pixels at its position $[q,l]$ in the image\replace{. Hence}{, hence}, $R_{q,l}\mathcal{Y}$ \replace{is equivalent to the $g \times g$}{yields a} matrix \replace{representing the}{with the size of $g \times g$ as an} extracted patch of $\mathcal{Y}$ at position of $[q,l]$. 
% \delete{The function $f$ is in charge of the geometric distance, and it may have many forms such as a Gaussian, a box function, or a constant.}
\ths{As } NLM estimation is a zero-order regression, only the zero-order basis is used for estimation. Therefore, the NLM weights look like
\begin{equation}
\begin{align}
\mathcal{W}[i,j,q,l]=&exp\left \{ -\frac{\left \| R_{q,l}\mathcal{Y}-R_{i,j}\mathcal{Y} \right \|_2^2}{2\sigma^2}\right \}\\ \times &f(\sqrt{(q-i)^2+(l-j)^2}),
\label{eq:2}
\end{align}
\end{equation}
where $\sigma$ manages the effects of radiometric differences between two patches and 
when the intensities of the two \replace{patches}{pixels} are far away, the weight becomes very small and \ths{thus} can be ignored. 
Whereas the function $f$ is in charge of the geometric distance, and it may have many forms such as a Gaussian, a box function, or a constant \cite{Protter09generalizingthe,protter2009super}. { {Since there are various other ways to choose the weights in (\ref{eq:1}),{{ in this chapter I will restrict my choice to SCoBeP \cite{barzigar2012scobep} and NLM as described in Sections \ref{SCoBeP_SR} and \ref{SR_Weight}.}}

%  combine the SCoBeP \cite{barzigar2012scobep} and NLM weights because of their simplicity and accuracy.





% {\color{red}{Reviewer 2: This content is not new, it is very much what was seen in [5]. Does not it belong in the background too?
% 
% ICIP reviewer: The cost function (7) is the one first written by Protter et al. [3]. Stating that “one can borrow the idea of NLM filter [6]”, the authors introduce the cost function as if the authors came up with. }}
{{

\section{NLM \replace{for}{to} Super Resolution}\label{DeblurDenoise_Steps}

Since self-similarities \replace{exist}{can be found} in \replace{most}{the} natural images, one can \replace{also use}{take advantage of} the NLM algorithm to \replace{take advantage}{use} the non-local \replace{similarity property of natural images in the superresolution problem.}{similarities of the multi patches in the other frames of the sequence. Therefore, I try to encourage each patch in my resulting frame to look like other patches in the sequence. However, it is reasonable to try to extend this intuitive idea to perform super resolution using similarities.} 
% Here, I have two reasons to start with the penalty function (\ref{eq:PMLZ}) to use the NLM for the super resolution; first, I desire a closeness between the HR image $\mathcal{X}$ and the input images $\begin{Bmatrix} \mathcal{Y}_t \end{Bmatrix}^T_{t=1}$, and second,


\ths{In essence, one may extract a target patch information from multiple patches instead of one patch per each LR frame. }
% \delete{As I would like each patch in my resulting image $\mathcal{X}$ to look like other patches in the sequence,}
%  However, there is not such a fit for every pair. 
% To obtain a HR patch in the classic super resolution as mentioned in Section \ref{SR_Back}, only one patch is used, but I can take advantage of the NLM to use multi patches in the non local neighborhood. 
% \delete{
%  I introduce weights to determine which of theses pairs are alike, and I can follow 
% \cite{Protter09generalizingthe,protter2009super} 
% to  approximate $\epsilon^2_{ML}$ in (\ref{eq:PMLZ}) instead as}
\ths{This allows us to modify $\epsilon^2_{ML}$ in (\ref{eq:PMLZ}) instead to \cite{Protter09generalizingthe,protter2009super} }
% To approximate the prior in \eqref{eq:2}, one can borrow the idea of NLM filters in super resolution \cite{Protter09generalizingthe,protter2009super}.
% , thus, I follow  \cite{protter2009super} to modify the MAP formulation in (\ref{eq:ML}) by proposing following probabilistic MAP (PMAP) to choose which of these pairs behave alike: 
% \comm{M?}
% % the ML formulation in (\ref{eq:ML}) by proposing following probabilistic ML (PML) to choose which of these pairs behave alike:
% % \comm{NEED REWRITE, IT ISN'T EVEN CORRECT. READ [3] AGAIN CAREFULLY!}
% 
% \begin{equation}
% \epsilon^2_{PMAP}(\mathcal{X}) = \frac{1}{2}\sum_{t=1}^{T}\left \| DHF_t\mathcal{X}-\mathcal{Y}_t \right \|^2_{W_{t}} +\lambda . TV(\mathcal{X}),
% \label{eq:PML1}
% \end{equation}
% where weights ${W_{t}}$ are diagonal matrices defined on LR images. I continue with the assumption that ${W_{t}}$ are known. In Section (\ref{SR_Weight}), I will offer one possible way to compute the weights ${W_{t}}$. 
% Essentially, I can consider $\mathcal W[i,j,q,l]$ in \eqref{eq:2} as a prior probability that the pixel $[q,l]$ in the reference image should be mapped to the pixel $[i,j]$ in a LR image. Thus I can follow  \cite{Protter09generalizingthe,protter2009super} to approximate $\epsilon^2_{ML}$ in (\ref{eq:PMLZ}) instead as
\begin{eqnarray}\nonumber
\epsilon^2_{ML}(\mathcal{Z})&=
&\frac{1}{2}\sum_{t=1}^{T}\sum_{[q,l]\in \mathcal{I}}\sum_{[ri,rj]\in {\mathcal{N}(q,l)}}\mathcal{W}[i,j,q,l,t]
\\ \nonumber
&&\times \left \| DR^H_{q,l}\mathcal{Z}-R^L_{i,j}\mathcal{Y}_t\right \|^2_2 ,\\ 
\label{eq:ML}
\end{eqnarray}
where %$\mathcal{W}$ is a weight matrix assigned to each pixel and 
$\mathcal{I}$ is the set of pixel coordinates of the entire frame $\mathcal{X}$, \ths{$\mathcal{N}(q,l)$ is a neighborhood of the pixel $[q,l]$, and}  
% Note that $\mathcal W[i,j,q,l,t]$ can be interpreted as the prior probability as described above mapping from a pixel in the reference frame to a corresponding pixel in the $t^{th}$ LR frame $\mathcal{Y}_t$. 
$\mathcal W[i,j,q,l,t]$ can be interpreted as a weight that the pixel $[q,l]$ in the reference frame should be mapped to the pixel $[i,j]$ in the $t^{th}$ LR frame $\mathcal{Y}_t$. $R^H_{q,l}$ and $R^L_{i,j}$ \ths{are defined} as \ths{the} HR and LR patch extraction operators respectively, where the size of the extracted patches are related to the resolution ratio $r$ as follows. Let the size of patches extracted by $R^L_{i,j}$ and $R^H_{q,l}$ be $g \times g$ and $k \times k$, respectively. I have $k = r(g-1)+1$. Note that $k$ is not \ths{set} precisely \ths{as} $rg$ \replace{to}{size and we} avoid \replace{the need of}{using} extrapolation. {{The detail in computing $\mathcal W$ will be deferred to Section \ref{SCoBeP_SR} {{and \ref{SR_Weight}}}}}. 


%  Note that I have also swapped the order of the warping operation and the decimation and blurring operation since they approximately commute.




% Just as in \eqref{eq:MAP}, I can further incorporate regularization to $\epsilon^2_{ML}$ to  obtain an approximate MAP estimator. 
% Define
% \begin{equation}
% \epsilon^2_{DB}(\mathcal{X})=\left \| H\mathcal{X}-\mathcal{Z} \right \|_2^2+\lambda \cdot TV(\mathcal{X}).
% \label{eq:ZX}
% \end{equation}
% and 
% substitute $\mathcal{Z}=H\mathcal{X}$ back to \eqref{eq:PML}, I have
% \begin{eqnarray}\nonumber
% \epsilon^2_{ML}(\mathcal{Z})&=
% &\frac{1}{2}\sum_{v=1}^{V}\sum_{b=1}^{n}\sum_{[q,l]\in \mathcal{I}}\sum_{[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlv})}}\mathcal{W}[i,j,q,l,b,v] 
% \\ \nonumber
% &&\times \left \| DR^H_{q,l}\mathcal{Z}-R^L_{i,j}y_v \right \|^2_2 ,\\ 
% \label{eq:PMLZ1}
% \end{eqnarray}
% and I can solve for $\mathcal X$ approximately using two-part optimization
% \cite{farsiu2004fast,protter2009super,Protter09generalizingthe}.
% % The key idea is that $\epsilon^2_{MAP}$ can be shown to be smaller than $\epsilon^2_{ML} + \epsilon^2_{DB}$ by triangle inequality. 
% % % \begin{equation}
% % % \epsilon^2_{ML}(\mathcal{Z}) = \frac{1}{2}\sum_{u=1}^{U}\sum_{v=1}^{V}\left \| DF_u\mathcal{Z}-\mathcal{Y}_v \right \|^2_{\mathcal{W}_{u,v}}.
% % % \label{eq:PMLZ}
% % % \end{equation}
% % Then, I use the found $\mathcal{Z}$ to estimate $\mathcal{X}$ by minimizing 
% More precisely, I can break my minimization problem in two steps:
% \begin{enumerate}
%  \item compute a blurred version of HR $\mathcal{Z}$ by minimizing (\ref{eq:PMLZ1}). \label{step1}
%  \item estimate the deblurred image $\mathcal{X}$ from the found blurred HR $\mathcal{Z}$ in step \ref{step1}.
% \end{enumerate}

% 
% As the second step only involves the %a well-known 
% classic deblurring problem, many potential techniques can be applied here. In my proposed approach, I have only tested the total-variation regularized deblurring method developed by Getreuer \cite{TVreg2009}. However, one can generally incorporate any deblurring techiques into the proposed method. 



% \cite{chan1998total,beck2009fast,biemond1990iterative,wang2007fast} for more information about this field. 
As for the first step, one can show that \ths{the optimum} $\mathcal{Z}$ can be computed as
\cite{Protter09generalizingthe} 
%  (see Appendix)
% Thus, I concentrate on the first step in finding a blurry HR image $\mathcal{Z}$.
\begin{equation}
\hspace{-15pt}
\mathcal{Z}[q,l] = \frac{\sum_{t=1}^{T}\sum_{[ri,rj]\in {\mathcal{N}(q,l)}}\mathcal{W}[i,j,q,l,t]\mathcal{Y}_t[i,j]}{\sum_{t=1}^{T}\sum_{[ri,rj]\in {\mathcal{N}(q,l)}}\mathcal{W}[i,j,q,l,t]}.
\label{eq:finalz}
\end{equation}
}}
\section{Contribution of My Dissertation}
The contributions of the proposed approach can be summarized as follows: 

$(i)$ Decomposing each reference image patch into a linear combination of a few elements from a basis set,  which increases the expressiveness of basis patches that allows the reconstruction of edges with high fidelity{{, and avoids the need of accurate motion estimation}}. 

$(ii)$ Identifying the best similar matches based on the local and the geometric characteristics using factor graph, which efficiently trade off both characteristics optimally. 

\ths{$(iii)$ Incorporating SCoBeP to efficiently sift through pixels from all LR images and thus resulting much more accurate non-local candidates for subsequent estimation.}

$(iv)$ Demonstrating competitive performance of the proposed methods with both synthetic and real video sequences. 

{$(v)$} Breaking the locality constraint in the conventional restoration methods using NLM method, which provides similarity by exploiting the redundancy between overlapping patches.

{{$(vi)$} Exploiting 
% the output of SCoBeP and bypassing NLM in 
both SCoBeP output and the NLM technique in calculating weights to facilitate tradeoff between computational complexity and performance.
% reduce the computational complexity with minimum impact on the performance.
}

{$(vii)$} Incorporating belief propagation into sparse coding, which increases the effect of each neighboring LR pixel on the candidate points.

{$(viii)$} relying on basic vector operations instead of utilizing SVD in video denoising, which the approach is immediately applicable to matrices of any field (including finite field matrices). 

The rest of my dissertation is structured as follows. I give a brief summary of related work and review the background of super resolution and NLM filter in the next chapter. In Section \ref{SR_PropsedMethod}, I introduce my proposed methods: SCoBeP-SR {{and SCoBeP-NLM}}. Implementation issues are also presented in detail in this section. Section \ref{ExResult} presents the experimental results and compares my results with that of the existing super resolution methods. Moreover, I will introduce the concept of my video deoising method using block matching filtering and matrix completion method in Chapter \ref{MatrixVideo}. I further show my simulation results in Section \ref{Denoisingesults}. Finally, Chapter \ref{conclusion} concludes the work has been done throughout this dissertation. 

% future work is outlined and concluding remarks are made in Section \ref{conclusion}.
%  provides operating directly on the real images.

\chapter{A SUPER RESOLUTION METHOD FOR VIDEO WITH CAMERA AND OBJECT MOTION USING SCoBeP}

\section{Introduction}
Super resolution tries to combine several low resolution (LR) images from a scene and produces one higher resolution image with better optical resolution. This is an inverse problem that is commonly tackled by integrating denoising, deblurring, and \ths{upsampling}.
%  \delete{operators.}

Fig.~\ref{inversproblem_SR} illustrates this inverse process and presents how the LR sequence may be modeled using an original higher resolution frame. During imaging, the blurring \replace{effect can be modeled}{operation can be characterized} by the optical point spread function (PSF). The scene may \replace{then be}{become} warped due to camera or object motion. \replace{Moreover}{However}, the motion effect might not be the same for all frames in the sequence.  \replace{A fixed decimation operator is typically used to model}{The operator models} the effect of sampling by the image sensor.  The 
% \delete{fixed decimation}
operator is characterized by the resolution ratio between the original higher resolution frame and the LR sequence.  The noise, which in most applications assumed to be white i.i.d. Gaussian, is added to the LR frames. The outcome of the super resolution reconstruction problem depends on the involved operators and noise characteristics of the above mentioned model. 
% Super resolution is a well known problem and appropriately treated in the literature.

A wide variety of super resolution methods have been studied in the last two decades \cite{irani1991improving, chan2008evaluation,protter2009super,farsiu2004fast,bonchev2010improving,Protter09generalizingthe,mitzel2009video,danielyan2008image,takeda2009super,zhang2010non}.  Huang and Tsai were the first to address the multiframe super resolution problem using a frequency domain approach that works for band limited and noise-free images \cite{tsai1984multiframe}. Later, it was extended by others, such as \ths{Kim {\em et al.}} 
who proposed a super resolution method on noisy and blurred images \cite{kim1990recursive}. {{Pleg and Irani \cite{irani1991improving} also suggested a different approach \ths{for} the super resolution problem based on the iterative backprojection (IBP) method adopted from computer aided tomography (CAT).}} Recently, an iterative multiframe super resolution method was presented in \cite{takeda2009super} that relied on extending the steerable kernel method in space-time. {{However, the approach \replace{assumes the input}{assumed to work on the locally smooth} frames \replace{only contain smooth textures}{ except at the edges}. 
% \scc{redo, add citation to justifiy your accusation}
% {Also, it still needs to estimate a pixel-wise motion in regions with the larger motion.}
Also, it has difficulties to estimate a pixel-wise motion in regions with the larger motion \cite{liu2011bayesian}.}}

 \begin{landscape}
\begin{figure}
  \centering
  \subfloat{\label{fig:cc24}\includegraphics{Figs_tables/SR_Model1}}                
%    \vspace{-5pt}              
  \caption{ {A general model of multi-frame super resolution.}}
  \label{inversproblem_SR}
%  \vspace{-17pt}
\end{figure}

\begin{figure*}[!t]
  \centering
  \subfloat{\label{fig:cc24}\includegraphics[width=16cm]{Figs_tables/SCoBeP_model}}                
%     \vspace{-20pt}              
  \caption{ {Block diagram representation of {{my models.}}}}
% \vspace{-15pt}
  \label{dg:model} 
\end{figure*}
\end{landscape}

% camera position changing
In dealing with camera position variation, a few attempts have been made through a global motion model \cite{farsiu2004fast,bonchev2010improving,tsai1984multiframe,chantas2007super}. Bonchev and Alexiev suggested a method of super resolution that used the information from several LR frames by controlling the camera position in frequency domain  when taking frames \cite{bonchev2010improving}. Also, in \cite{chantas2007super} a maximum a posteriori (MAP) was adopted to 
\replace{provide coarse estimates of}{optimize the coarse estimation of} rotation and translation between images. The authors claimed that such estimation \ths{step} provided enough accuracy to effectively remove \ths{the effect of} the rotational and coarse (super-pixel) translational motion between the images. {{Although that algorithm incorporates smoothness priors as a constraint to reconstruct the HR images, using these smoothness priors might not lead to smooth results \cite{li2009example}.}}
% {\color{green}{There is also a great number of registered super resolution approaches that predominantly rely on the-state-of-the-art methods documented in the literature \cite{tian2011survey}}}.
A number of super resolution approaches using Total Variation (TV) regularization terms have been \replace{explored}{exploited} in the last decade, e.g., the approach by Mitzel \textit{et al.} in \cite{mitzel2009video}, where their method is not restricted to any particular motion model and they do not assume that the motion is known. In another work, Farsiu \textit{et al.} suggested a multiframe super resolution method \replace{by}{based on} applying \ths{constraints on} the $L_1$ norm \replace{of}{on} both the bilateral TV regularization \ths{term} and the data fusion term \replace{to produce}{for producing} a sharp, high resolution (HR) image \cite{farsiu2004fast}. The researchers also registered the LR images with respect to a reference frame before starting the super resolution process.  { {
{Liu and Sun in \cite{liu2011bayesian} proposed a Bayesian framework for adaptive video super resolution that deals with video super resolution by also simultaneously estimating underlying large motion.
Moreover, they jointly estimated the flow field and the noise level in a coarse-to-fine manner on a Gaussian image pyramid using the HR image and the blur kernel.
}}
% The motion, noise and blur with the HR image were jointly estimated using sparse image, flow, and kernel priors. 
}

% Working with low resolution (LR) images taken by digital cameras is difficult because various devices produce different low resolution images.
% The prior works  
% In this work, I address the challenging problem of image and video super resolution by removing the need for pre-processing step of image registration. 

In this work, I \replace{focus}{operate directly} on video frames that suffer from non-homogeneous noise, atmosphere or camera blur, motion and down-sampling effects. Also, as real videos can be taken from \ths{both} fixed or movable cameras, I \replace{also consider}{work on both the} frames affected by scene motions and/or {{small camera motions. Note that as I will see in the coming sections, the approach I introduced here works well for such scenario.
%\footnote{\scriptsize{{{Note that when I are talking about the large motions in this chapter, I mean speeds (in units of pixels/frame) which are larger than the typical support of the SCoBeP window, or the moving object's width along the motion trajectory. In the latter case, even when the motion speed is slow, I are likely to have temporal aliasing locally.}}}}. 
My method is complementary to approaches such as 
\cite{liu2011bayesian}, which considers the superresolution of sequences with larger camera motions but little or no scene motions.
% It is out of the scope of this chapter to develop a super resolution method or motion estimation method that generally applies to all situations. Instead, I focus on the sequences affected by scene motions or small camera motions in this work.
}}

I propose to solve the super resolution problem using a novel framework \replace{taking advantage of}{based on} two \replace{recently developed}{new} techniques\replace{:}{ of} SCoBeP \cite{barzigar2012scobep} and Nonlocal-Means (NLM) \cite{buades2006review}.{{ My approaches are based on the concept of Sparse Coding and Belief Propagation (SCoBeP) which is earlier introduced in \cite{barzigar2012scobep} for 2-D signals (images). %A specific extension of these concepts to 3-D signals for video super resolution \replace{is}{are} \replace{an objective}{one of the main subjects} of this chapter.
{ It turns out that the technique is well-suited for super resolution of video (a 3-D signal) as I explore in this chapter. }
}} 

\replace{As a summary of my approaches}{To be more specific}, I first build an overcomplete dictionary out of all block features of LR frames as shown in Fig.~\ref{dg:model}. {{Different from \cite{yang2011exploiting}, I am not generating HR/LR patch pairs from the frames by exploiting self-similarities.}}
% Note that because the dictionary is constructed by padding the features directly, no extra time is spent on training. 
For each pixel of the initial estimate of the HR frame, I then select a set of candidate pixels out of the constructed dictionary using sparse coding \cite{mairal2010online}. The match score of each candidate pixel will be evaluated taking both local and neighboring information into account using belief propagation  \cite{kschischang2001factor}. The best matches will be selected as the candidates with the highest scores. 
\replace{An}{For an} occluded pixel or any pixel not covered by the LR frames \ths{is likely to be identified since} the match scores \replace{in this case}{of the found candidate pixels} will be significantly smaller than a typical maximum score when a match pixel actually exists. \ths{Finally,} {{in my first proposed method, }}the NLM approach exploits similarity in patches around candidate pixels to average out the noise among similar patches \cite{Protter09generalizingthe} {{and in my second proposed method, a pixel is reconstruct from multiple candidate pixels with the weights  extracted directly from the output of SCoBeP.}}

In the experiment section, I also illustrate that the proposed methods can perform well on real LR videos (besides ``phantom'' LR videos generated artificially) and can reconstruct image edges with high fidelity. Although the NLM filtering has shown great potentials for image denoising and superresolution \cite{buades2006review}, it is only effective when a reference patch can be identified to accurately represent the targeted patch. 
{{Moreover, NLM approaches generally have very high computational complexity. I will show in this chapter reference patches can be effectively found by SCoBeP. Further, I will also show that the NLM step may be skipped completely (as demonstrated in the second method) with only a small performance penalty but a significant (about three times) speed-up.}}


%  exploiting the redundancy between overlapping patches.




% The rest of this chapter is structured as follows. I give a brief summary of related work and review the background of super resolution and NLM filter in the next section. In Section \ref{SR_PropsedMethod}, I introduce my proposed methods: SCoBeP-SR {{and SCoBeP-NLM}}. Implementation issues are also presented in detail in this section. Section \ref{ExResult} presents the experimental results and compares my results with that of the existing super resolution methods. Finally, future work is outlined and concluding remarks are made in Section \ref{conclusion}.


% \comm{reformat the table, have the second column entries aligned left}
\begin{table}[!t]
\renewcommand{\arraystretch}{1.2}
\caption{\replace{Summary}{Summery} of \replace{Notation}{Notations} }
\label{table_Notation}
\centering
%  \rowcolors{2}{gray!25}{white}
\scalebox{1}{
\begin{tabular}{c p{9.5cm}}  
  \hline
 \hline
  \textbf{ Notation} &  \textbf{Description} \\
  \hline
%   \hline
 
\rowcolor{gray!13}
{$\mathcal{X}$  }    & the reconstructed HR frame\\

   

  {$\mathcal{Y}_t$  }    & the LR frame at $t$ \\

\rowcolor{gray!13}

 {$y_t$  }    & the interpolated LR frame at $t$ \\

{$T$  }    & the number of available LR frames\\

   \rowcolor{gray!13}

  {$\mathcal{Z}$  }    & the blurred version of the reconstructed HR frame\\

  {$\mathcal{N}(q,l)$  }    & a neighborhood around pixel $[q,l]$\\

   \rowcolor{gray!13}

{$R_{ql}$  }    & the matrix that extracts a patch centered around pixel $[q,l]$\\

{$r$  }    & the resolution (magnification) ratio\\

   \rowcolor{gray!13}

 {$n$  }    & the number of candidate pixels \\

{$X_{ql}$  }    & the vectorized patch at pixel $[q,l]$ in the reference frame\\

   \rowcolor{gray!13}

 {$D_{t}$  }    & the dictionary constructed from the $t^{th}$ LR frame $\mathcal{Y}_t$\\



 {$\alpha_{qlt}$  }    & the sparse representation vector of a patch centered around pixel $[q,l]$ in $t^{th}$ LR frame \\

\rowcolor{gray!13}

    {$Y_{qlt}$  }    & the vectorized patch at pixel $[q,l]$ in the $t^{th}$ LR frame $\mathcal{Y}_t$\\ 


       {$\mathcal{W}[i,j,q,l,b,t]$  }    &  the weight mapping from a pixel in the reference frame to $b^{th}$ candidate pixel in the $t^{th}$ interpolated LR frame $y_t$\\
   
  
\rowcolor{gray!13}
      {$cp$  }    & an $n \times 2$ matrix storing the locations of the candidate pixels\\


   
%      {$b$  } 	&  the dummy candidate pixel index \\  
     
    


   
   {$\rho_{qlt}$ }    & the prior probability of pixel $[q, l]$ in the reference frame mapping to the $b^{th}$ candidate pixel in $t^{th}$ interpolated LR frame\\ 

% \rowcolor{gray!13}
%       {$\hat{\alpha}_{qlt}$  }    & updated $\alpha_{qlt}$ using belief propagation\\


% length-$n$ vector storing the corresponding values of $\alpha_{qlt}$\\

%  \multirow{2}{*}   
% {$\xi$ }     & scaling factor\\

% \rowcolor{gray!13}
%       {$\phi^{(b)}_{qlt}$  }    & the extracted patch at the $b^{th}$ candidate pixel scaled by the prior\\
% \rowcolor{gray!13} & probability $\rho_{qlt}$ \\



%  {$\begin{Bmatrix} y_v \end{Bmatrix}^V_{v=1}$}    & Low resolution and noisy images\\

 \hline
  \hline

\end{tabular}
}
\end{table}

\section{Related Work And Background}\label{Introduction_SR}
% Today, with advances in sensor design, the given image is relatively clean for digital cameras, but it remains noisy and blurry for low-grade and mobile phone cameras. Thus the super resolution problem is still of acute importance, and I present a novel learned image model method, which outperforms the-state-of-the-art, super resolution task on real and synthetic low sequences.
Sparse representation \cite{yang2010image} and self-similar-based techniques \cite{protter2009super,zhang2010non} have been used in super resolution in recent years.{{
% \delete{It is worth to talk about the relations of some recent super resolution works to these techniques.}
\replace{In this section, I will review}{Thus, as I show next,} how some of the recent works \replace{use}{take different routes in using} these techniques \replace{in}{, such as} recovering the downsampled signals and computing the similarity of image patches.}}

% {{I now start to discuss several specific works where sparse representation modeling is shown to be highly effective.}}
% Sparse representation techniques are beginning to show significant impact on image processing \cite{mairal2009non,dabov2007image,yang2010image,wang2010resolution}\replace{.}{, often on denoising and super resolution where the goal is not just to obtain a compact high-fidelity representation of the observed image, but also to extract semantic information} 
% Also, the results of these methods illustrate that the sparse representation can be correctly recovered from the downsampled signals.
{{
% For example, %about sparsity 
In \cite{yang2010image,wang2010resolution}, a large set (of the order of a hundred thousand) of patches randomly sampled from natural images to train an LR and a HR dictionaries. The main idea consists of seeking in the database for a sparse representation of each patch of the LR input, followed by using this representation to generate the HR output.}}
{{Yang \textit{et al.} \cite{yang2011exploiting} proposed a super-resolution method that exploits self-similarities and group
structural constraints of image patches using only one single input frame.  In this algorithm, the patch self-similarity within the image is exploited and the group sparsity then will be introduced for better regularization in the reconstruction process.}}
%  a computed sparse representation adaptively chooses
% the most relevant patch bases in the dictionary were chosen to represent each patch of the given LR image. 
% the sparse property of image patches is modeled as the sparse prior to recover the HR image patches. The dictionary pair for LR and HR were also trained from a large number of patch pairs randomly sampled from natural images.
% Marial \textit{et al.} in \cite{mairal2009non} proposed a sparse coding approach by presenting that similar patches share the same dictionary elements in their sparse decomposition on denoising and demosaicking. \delete{The authors also introduced an idea that image self-similarities can be used to improve learned sparse models with simultaneous sparse coding, which ensures similar patches to admit similar sparse decompositions.}
Another recent example based on an enhanced sparse representation in transform domain is block-matching 3-D filter (BM3D) \cite{dabov2007image},{{ which uses a block matching technique to find a set of similar 2D blocks}}. Danielyan \textit{et al.} have extended (BM3D) in \cite{danielyan2008image} for image and video super resolution.{{ They produce a sparse representation of the true signal in the transform domain to exploit the similarity among the blocks.
In contrast to the sparse representation approaches \replace{discussed above}{here} \replace{where they use information from only one corresponding pixel per LR frame to reconstruct a target pixel}{that are only seeking one corresponding pixel for each target pixel}, \replace{my first approach incorporates the NLM method to take advantage information from multiple matched pixels for the reconstruction.}{I want to look for multiple matches from each LR frame.}}}



% their approach requires explicit motion estimation and thus can not take care of the sequences with arbitrary motions \cite{takeda2009super}. Since in my proposed method where I identify the best similar matches for each pixel based on SCoBeP, I avoid the need of accurate motion estimation. This is one of the motivations of my chapter.

 % offline dictionary -Sparse

% Recent works have supported the idea that a sparse linear combination of elements from a \replace{suitably}{suitable} chosen over-complete dictionary can represent image patches properly \cite{yang2010image,mairal2009non}, where a dictionary is a basis set composed of the image patches. 
%  { { However, it is difficult to learn a universal LR/HR dictionary pair representing various LR/HR structure pairs. The lack of some fine image structures from the reconstructed edges is easily observed. Since in my proposed method I build a dictionary out of all block features of the LR images, the required image structures will be added to the dictionary automatically, and the reconstructed edges will be much sharper.}}



% \textcolor{green}{Self-similarity}
% Non local mean
{{I now turn to a discussion of certain works associated with self-similar-based technique.}}
Plenty of works have emerged lately based on self-similarity for natural image and video processing. The self-similarity property shows that the image content desires to repeat itself within some neighborhoods. 
Non local self-similarity has been effectively applied to many aspects of image processing \cite{efros1999texture,mairal2009non,protter2009super}. Following this insight, Buades \textit{et al.} used this approach in image denoising, which is known as the NLM method \cite{buades2006review}. The NLM method was used also in image restoration explicitly exploits self-similarities in natural images \cite{buades2006review,protter2009super}. 
{{Liu and Freeman in \cite{liu2010high} proposed a video denoising approach to use an approximate k-nearest neighbor (AKNN) algorithm to approximately but rapidly seek the most similar patches for a given video. As
pointed out in \cite{do2011combination}, \cite{liu2010high} takes into account only similar blocks for a given video and thus could be classified as a ``closest structure'' method, while one can call the original NLM method \cite{buades2006review} a ``closest space'' method in the sense that it uses only closest blocks in a small window.
}}
{{Moreover, Marial \textit{et al.} in \cite{mairal2009non} extended the NLM method in denoising and demosaicking using \replace{the}{this} idea that similar patches have similar sparsity patterns.}}
Also, in \cite{zhang2010non}, Zhang \textit{et al.} proposed a non-local kernel regression method for image and video super resolution, which exploits both non-local self-similarity and local structural regularity in a single model. 
% However, their method was limited to the simple motion patterns and cannot handle image wrapping \scc{citation}{well}. 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           Distinct from the local kernel regression, the NLM method estimates the \replace{value of a pixel}{pixel value} from all possible patches collected from a search area, and breaks the locality constraint in the restoration algorithms. Protter \textit{et al.} \cite{Protter09generalizingthe} generalized this denoising method to perform multiframe super resolution reconstruction with no explicit motion estimation. In that work, computing the similarity of video frame patches resulted in 
probabilistic estimates of motion. 

% {\color{red} NEED TO PUT REPLY 1 FOR REVIEWER 3 SOMEWHERE}

Prior works have been limited to block matching in restricted neighborhoods.
{ {\ths{These neighborhoods determine the candidate matches of target pixels and thus have a significant impact on SR performance. 
However, they have always been assigned with limited sizes and regular shapes (e.g., as rectangular blocks) in prior works and hence}
 often do not \replace{include}{result in} the best match patches. \replace{Due}{Also, due} to this poor block matching, \replace{the prior techniques}{their results} \replace{could}{will} suffer from block artifacts \ths{in some test cases} \cite{Protter09generalizingthe,villena2009bayesian}.
% However, the work is insufficient to guarantee the perfect motion estimation and will fail to achieve a HR image from the arbitrary sequences \cite{takeda2009super}. 

\begin{figure}[t]
 \center
   \subfloat[]{\label{fig:n11f}\includegraphics[width=12cm]{Figs_tables/Foreman_NCC}} 
\vspace{-8pt}
    \subfloat[]{\label{fig:n12f}\includegraphics[width=12cm]{Figs_tables/Foreman_SCoBeP}}
     \caption{{ {Candidate points obtained by KNN and sparse coding. The images in (a) shows that KNN tends to result in candidate points with poor diversity. And thus it can easily miss including the true corresponding point as one of its candidate points. In contrast, the images in (b) show that the candidate points of sparse coding tend to diversify and thus is more likely to include the true corresponding point.} }}
%      \vspace{-18pt}
   \label{n-candidates}
\end{figure}

{{In contrast, {{the advantage of SCoBeP registration is that the chosen candidates will have better ``diversity'' when compared with the AKNN or even the {\it exact} K-nearest neighobor (KNN) approach (see Fig.~\ref{n-candidates}). This originates from the induced orthogonality of the patches when sparsity is imposed in the solution. In the KNN case, when a smooth patch is incorrectly matched to a patch, the next best ``matches'' are likely around the neighborhood of the wrong patch and it ends up incorrect matching for all patches. The better ``diversity'' actually affords SCoBeP a larger search window compared with other registration without sacrificing the robustness of the approach \cite{barzigar2012scobep}.}}}} In this chapter, I take advantage of SCoBeP to select from each LR frame a set of candidate pixels which are likely to be most similar to the target pixel.}}
\ths{As a result, for each pixel and per LR frame, I have an irregular neighborhood that can include any pixel in the frame. This significantly improves the block matching performance that directly links to the overall SR performance.} 


% \delete{To the best of my knowledge, this is the first time a method explicitly is modeled based on two new techniques of sparse representation and similarity.}





% Additionally, I achieve better results than Gnl-Means \cite{Protter09generalizingthe} and Optical flow \cite{brox2004high} which show SCoBeP can find the accurate location for each object that are missed by other methods. These comparable results show that SIFT flow and Optical flow has some weaknesses compare to SCoBeP. Generally, they are more sensitive to scene deformation and can not synthesize test image if there are many changes of the test image comparing to the reference image. In contrast, SCoBeP appears to be more robust in handling complex scenes with multi objects and wide-baseline views.

% \cite{survey1} and \cite {survey2} fully reviewed the solution 




% \section{Background}\label{SR_Background}
% In this section I briefly describe the background of super resolution and NLM filter.



\section{Proposed Method}\label{SR_PropsedMethod}

% \comm{Write down the intuition the algorithm first.}

{{The key to apply NLM to super resolution efficiently depends on how I can \replace{identify}{assign} the appropriate \replace{neighboring set}{neighbor} ($\mathcal{N}(q,l)$) for each pixel and also how I can choose the appropriate weighting function. 
% and it is efficient \scc{I don't know what you are talking about, doesn't sound like any rational reason}{because since the warping operation could vary from pixels to pixels, and also integrating all possible warping operations is too expensive, SCoBeP can handle these problems with providing some candidate pixel locations, and weight the found candidate pixels to show the probability that these pixels and the pixel on the HR image had the same value.
}
\ths{In particular, the neighborhood $\mathcal{N}(q,l)$ has significant effect on the performance of the NLM filter. The neighborhood should be sufficiently large to take advantage ``non-local'' benefit of the algorithm. However, this also significantly increases the complexity of the algorithm.} 


{{
\ths{Ideally, I would like the neighborhood set $\mathcal{N}(q,l)$ to cover the entire frame. That is, to allow each pixel to take into account information from any pixel of every LR frame and let the weight variable $\mathcal{W}[i,j,q,l,t]$ to take care of the significance of the contribution. This, of course, will lead to unrealistic computational load if I blindly look into every pixel of every LR frame. What I need is an intelligent preprocessing step to identify pixels that are likely to provide useful information to the target pixel no matter where the formers locate. The described problem above is closely related to image registration, and 
% . However, unlike conventional (dense) image registration that are only seeking one corresponding pixel for each target pixel,
I want to look for multiple matches from each reference frame (i.e., an LR frame in this case).}}} 
% \delete{This \replace{can be}{is} achieved by using SCoBeP 
% % \cite{barzigar2012scobep} 
% to provide these candidate pixel locations and weights.}

% \replace{
% \delete{In this chapter, I try to maintain a good balance between complexity and performance by exploiting the non-local \replace{image}{SCoBeP} registration method %\cite{barzigar2012scobep} 
% to identify candidate points for each pixel.}}{In order for the NLM weights to be computed using non local neighbor pixels, the pixels within a local neighborhood do not contribute precisely to the estimation of the current pixel value. There are many ways to calculate the weights for (\ref{eq:2}), I chose to calculate my weights based on the SCoBeP %\cite{barzigar2012scobep} 
% and NLM weights because of their simplicity and accuracy.}
% % \scc{It doesn't connect with the above paragraph!}
%  
% \delete{Now the challenging work is how to employ and extend the SCoBeP to compute the locations and values of candidate pixels in the sequence.} 

{{{
\ths{While many registration methods can be used, I chose to use SCoBeP \cite{barzigar2012scobep} for the aforementioned purpose as SCoBeP naturally identifies multiple matched pixels and returns the corresponding match scores as needed in this application. \replace{In summary,}{Motivated by the success of the SCoBeP,} 
% \cite{barzigar2012scobep}, 
for each pixel in the initial estimate of the HR frame, I \ths{use SCoBeP to} select from each LR frame a set of $n$ candidate pixels which are likely to be most similar to the target pixel. The similarity between a target pixel and a candidate pixel, which will be characterized by a weight, {{will be used by the SCoBeP method as to be described in Section \ref{SCoBeP_SR} {{or the NLM \ths{filter} as to be described in Section \ref{SR_Weight}.}}}}} 



\replace{For the rest of this section, I will review the SCoBeP registration technique in the context of superresolution and provide}{In this section I show, how SCoBeP can use the image self-similarities to encourage similar patches to admit similar sparse coefficients.
Also, this section describes} the implementation details of my proposed super resolution methods, SCoBeP-SR{{ and SCoBeP-NLM}}, {{which are based on sparse coding, belief propagation and NLM. I divide the super resolution process into two steps as shown in Sections \ref{SCoBeP_Conf} and \ref{SCoBeP_SR} {{or \ref{SR_Weight}}}.}}


% {\color{red}{Reviewer 1: In section IV.A please state the energies for the sparse coding and the belief propagation steps. Pointing to [14] is not enough, the chapter should be (roughly) self-contained. For sparse coding, please also give a short description of the method.
% 
% 
% Reviewer 2: It is not clearly written, and very hard to understand. Even with the reference to the authors’ other chapter, this chapter should be stand-alone, and the method clearly described. Thus, this section needs elaboration, and “Algorithm 1” needs also some strengthening. Or, it should belong in the background section.
% 
% 
% Reviewer 3: The length of the chapter could be larger , by first, explaining better the SCoBeP algorithm or at least give a link (a figure might help) with the present problem. }}

{{
\subsection{Use SCoBeP \cite{barzigar2012scobep} to compute the locations and prior probabilities of 
% \scc{what candidate pixels, need to describe in earlier paragraph}
{candidate pixels}}\label{SCoBeP_Conf}

% \comm{better move this paragraph to above}


The proposed method described here is inspired by my recent work, SCoBeP \cite{barzigar2012scobep}. First, I extract the features from all interpolated LR frames $\begin{Bmatrix} y_t \end{Bmatrix}^T_{t=1}$ 
% $\mathcal{Y}_v$ 
and the reference frame $\mathcal{X}$. 
To extract \replace{the}{dense} features, I consider a patch of size $(2h+1)^2$ containing neighboring pixels around each pixel on the reference and LR frames, where $h$ is a positive integer. For each pixel {$[p,q]$} 
% \scc{not consistent, you use $[p,q]$ earlier}{} 
in the reference frame $\mathcal{X}$, I vectorized the patch centered around the pixel {$[p,q]$} 
% \scc{not consistent, you use $[p,q]$ earlier}{}
 to a feature vector $X_{ql} \in \mathbb{R}^{S\times 1}$, where $S = (2h+1)^2$. 
% \delete{A 3-D reference feature image $X \in \mathbb{R}^{M\times N \times S}$ is then constructed from $X_{ql}$ as follows}

% \begin{equation}
% X =
% \begin{bmatrix}
% X_{1,1}&X_{1,2}&\cdots&X_{1,N} \\
% X_{2,1} & X_{2,2} & \cdots & X_{2,N} \\
% \vdots & \vdots & \ddots & \vdots \\
% X_{M,1} & X_{M,2} & \cdots & X_{M,N} \\
% \end{bmatrix}.
% \end{equation}


In this dissertation, I focus myself on only using block features even though the proposed approach can generally be applied to other features (such as SIFT-features). Thus, each feature considered here is essentially a vectorized block centered around a pixel in a frame.

Second, to match the extracted features of the reference frame to the corresponding extracted features of the $t^{th}$ interpolated LR frame $y_t$, I create a dictionary which contains all feature vectors of $y_t$. More precisely, a dictionary $D_{t} \in \mathbb{R}^{ S\times MN}$ {{($M$ and $N$ are the height and width of the interpolated LR frame $y_t$ minus $h$ from each side)}} is constructed with all possible vector $Y_{qlt} \in \mathbb{R}^{S \times 1}$ as $D_{t}$'s column vectors, where $Y_{qlt}$ is created in the same manner as $X_{ql}$  but from the $t^{th}$ interpolated LR frame $y_t$ instead.  Thus, I can write $D_{t}$ as
% \scc{$X_{1,2,t}$ is not defined, and are u sure $X$ is supposed in the dictionary!?}
{
\begin{equation}
D_{t} = [Y_{1,1,t} Y_{1,2,t} \cdots Y_{1,N,t} Y_{2,1,t} \cdots Y_{M,N,t}].
\label{eq:yql}
\end{equation}
}
I then normalize dictionary $D_{t}$ to guarantee the norm of each feature vector to be 1.	

Third, to identify the candidate $Y_{qlt}$ that looks most similar to the input $X_{ql}$ in the reference frame, I apply sparse coding to each extracted features of the reference frame. Sparse coding will reconstruct a reference patch at pixel $[q,l]$ as a linear combination of LR patches. Denote $\alpha_{qlt}$ as the sparse vector where each element corresponds to a coefficient in this combination.  Note that $\alpha_{qlt}$ should be sparse, i.e., it should be 0 for most coefficients.

 Mathematically, I try to solve the following sparse coding problem of finding the most sparse coefficient vector $\alpha_{qlt}$ such that 
\begin{equation}
X_{ql} =  D_{t} \alpha_{qlt}.
\label{eq:y_sparse}
\end{equation}

\begin{landscape}
\begin{figure}[t]
   \begin{center}
       \scalebox{1}{
           \includegraphics[width=12cm]{Figs_tables/SparseCoding_WC}}
   \end{center}
%    \vspace{-10pt}
           \caption{ {{Sparse representation of a feature vector $X_{ql}$ with a dictionary $D_{t}$: $\alpha_{qlt}$ as a sparse vector constructs the feature vector $X_{ql}$ using a few columns \ths{(highlighted in gray)} of dictionary $D_{t}$.
%  \delete{The columns highlighted with gray markers in $D_{t}$ form $X_{ql}$, a sparse linear combination.}
}}}
% \vspace{-17pt}
           \label{SparseCoding_WC}
\end{figure}
\end{landscape}


The sparse vector $\alpha_{qlt}$ is the representation of $X_{ql}$, which has few number of non-zeros coefficients. Thus, $\alpha_{qlt}$ describes how to construct $X_{ql}$ as a linear combination of a few columns (also referred to as atoms) in $D_{t}$. The locations of the nonzero coefficients in $\alpha_{qlt}$ specifically point out which $Y_{ql}$ in the dictionary $D_{t}$ is used to build $X_{ql}$ and the values of the non-zero coefficients in $\alpha_{qlt}$ show what ``portions'' thereof are used for its construction.
As shown in Fig.~\ref{SparseCoding_WC}, \ths{one expected that} most of the coefficients in $\alpha_{qlt}$ \replace{obtained by sparse coding}{vector} are zero, and \ths{the bases of} those non-zero coefficients correspond to the highlighted gray columns in $D_{t}$. Thus, $X_{ql}$ \replace{can be written}{is generated} as a sparse linear combination of those highlighted gray columns.

To solve (\ref{eq:y_sparse}), besides linear programming, many other suboptimal techniques have been proposed including orthogonal matching pursuit \cite{yang2010fast}, Subspace Pursuit (SP) \cite{dai2009subspace} and gradient projection \cite{maleh2007sparse}\replace{. In this work,}{which} I employed Subspace Pursuit (SP) \cite{dai2009subspace}. After finding the sparse representation vector $\alpha_{qlt}$, to select the $n$ candidate pixels, I simply pick those corresponding to {{$n$ largest absolute value of coefficients}} in $\alpha_{qlt}$. I denote $cp_{qlt}$ as an $n \times 2$ matrix storing the locations of these candidate pixels and $\rho_{qlt}$ as the length-$n$ vector storing the corresponding values of $\alpha_{qlt}$. 
% \scc{Do I really use this as prior or I compute the distance between patches again?}
\replace{I will take the normalized $|\rho_{qlt}|$}{
Each coefficient in $\rho_{qlt}$ serves} as a prior probability of matching the reference patch at $[q,l]$ to a patch of the interpolated LR frame $y_t$ taking only local characteristics into account but ignoring geometric characteristics of the matches.   
% {{\delete{Note that since the coefficients in $\rho_{qlt}$ can take negative value, I can normalize each of them by taking its relative absolute value to the total.}}}

Finally, to incorporate geometric characteristics, I model the problem by a factor graph and apply belief propagation to update probabilities $\rho_{qlt}$ (for more details, see \cite{barzigar2012scobep}).



I assume the operations such as warping and blurring in the maximum \textit{a posteriori} probability equation 
% \scc{deadlink!}
{\eqref{eq:MAP}} are known. However, this is not true in practice. In particular, while the blurring operation can be approximated to be more or less constant over the entire scene, the warping operation could vary from pixels to pixels. One way to handle the unknown warping problem is to adopt the Bayesian formulation and integrate all possible warping operations, this is of course too expensive to compute. Fortunately,
%  \scc{really? i see candidate match locations, but not candidate warping operations.}
{the SCoBeP step has already provided us some candidate match locations.} So (\ref{eq:finalz}) becomes
% \comm{I don't think equation is correct/precise. what do you mean by $[ri,rj] \in \mathcal{N}$?}
\begin{equation}
\hspace{-15pt}
\mathcal{Z}[q,l] = \frac{\sum_{t=1}^{T}\sum_{b=1}^{n}\sum_{[i,j]|[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]\mathcal{Y}_t[i,j]}{\sum_{t=1}^{T}\sum_{b=1}^{n}\sum_{[i,j]|[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]},
\label{eq:finalz1}
\end{equation}
\replace{where}{Note that} $\mathcal{W}[i,j,q,l,b,t]$  
% is obtained as described in the next subsection,} 
can be interpreted as the weight mapping from a pixel in the reference frame to $b^{th}$ candidate pixel in the $t^{th}$ interpolated LR frame $y_t$.{{
% , which can be obtained as various other ways, in this chapter I will restrict my choice to SCoBeP-SR and SCoBeP-NLM as described in the next subsections,}}
Since there are various other ways to choose the weights in (\ref{eq:finalz1}), in this chapter I will restrict my choice to SCoBeP-SR weights and SCoBeP-NLM weights as described in the next subsections.}}

\begin{algorithm} [t]
\caption{Super Resolution framework using SCoBeP - estimate version of HR frame $\mathcal{X}$ }
\begin{algorithmic} 
\renewcommand{\algorithmicrequire}{\textbf{Inputs :}}
\renewcommand{\algorithmicensure}{\textbf{Output :}}
\REQUIRE {LR and noisy frames  $\begin{Bmatrix} \mathcal{Y}_t \end{Bmatrix}^T_{t=1}$, resolution ratio $r$, weight patch $R$, frame number $t_c$ and the maximum number of iterations}
\renewcommand{\algorithmicrequire}{\textbf{Initialize}}
\REQUIRE { \textbf{:}}
\begin{itemize}
%  \item Generate a higher resolution sequence $\begin{Bmatrix} \mathcal{\check{Y}}_t \end{Bmatrix}^T_{t=1}$ by applying bicubic interpolation to all the LR images.
 \item Set $\mathcal{Z}$ as the bicubic interpolated frame of $\mathcal{Y}_{t_c}$
%  = \mathcal{\check{Y}}_0$
%  \item Set $\xi$ and $\omega$ to be the all-zero image with the same size as $\mathcal{Z}$
\end{itemize}
\renewcommand{\algorithmicrequire}{\textbf{Iterate :}}
\REQUIRE {while the maximum number of iterations is not reached}
\renewcommand{\algorithmicrequire}{\textbf{Use SCoBeP to find candidate pixels :}}
\REQUIRE {For each increased resolution frame $y_t$}
\begin{itemize}
\item Extract dense feature
\item Construct dictionary $D_t$  
\item Find the initial estimates of candidate pixel probabilities $\rho_{qlt}$ and candidate pixel locations $cp_{qlt}$
\item Apply belief propagation to refine $\rho_{qlt}$ and $cp_{qlt}$
\end{itemize}
\renewcommand{\algorithmicrequire}{\textbf{Find the blurred HR frame :}}
\REQUIRE {For each pixel location $[q,l]$ on the HR frame $\mathcal{Z}$ and for $b \in \{1,2,\cdots,n\}$, for each pixel location $[i,j]$ such that $[ri,rj] \in \mathcal{N}(cp^{(b)}_{qlt})$ }
% \newline
\begin{itemize}
\item {{Compute weights:}}
 \begin{enumerate}
    \item {{SCoBeP-SR weights:    
    $\mathcal{W}[i,j,q,l,b,t]= I ({cp}_{qlt}^b = [i,j]) \rho^{(b)}_{qlt}$
\textit{OR}}}
    \item {{SCoBeP-NLM weights:
 
    $\mathcal{W}[i,j,q,l,b,t]=\rho^{(b)}_{qlt} exp\left \{ -\frac{{\left \|R_{q,l}\mathcal{Z}-R_{cp^{(b)}_{qlt} }{y_t} \right \|_2^2}}{2\sigma^2}\right \}\newline \quad \times f(\sqrt{(q-ri)^2+(l-rj)^2+\xi(t-t_c)^2})$}}
\end{enumerate}
\item Compute $\mathcal{Z}$, the blurred version of reconstructed HR frame:
$\mathcal{Z}[q,l] = \frac{\sum_{t=1}^{T}\sum_{b=1}^{n}\sum_{[i,j]|[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]\mathcal{Y}_t[i,j]}{\sum_{t=1}^{T}\sum_{b=1}^{n}\sum_{[i,j]|[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]}$
\end{itemize}
\renewcommand{\algorithmicrequire}{\textbf{End of Iteration}}
\REQUIRE {}
\renewcommand{\algorithmicrequire}{\textbf{Perform deblurring :}}
\REQUIRE {$\mathcal{X}=$TV$deblur(\mathcal{Z})$ }
\renewcommand{\algorithmicrequire}{\textbf{Output :}}
\REQUIRE {a HR frame $\mathcal{X}$ }
\end{algorithmic}
\label{tb:algorithm}
\end{algorithm}

{{
\subsection{Calculate Weights for SCoBeP-SR} \label{SCoBeP_SR}
% While the algorithm performs favorably comparing with other recent approaches as illustrated in the next section, the algorithm is quite complex and I realized that the source of most computation is originated from the NLM component. 

As SCoBeP has naturally identified pixels that are most likely to be relevant to a target pixel and also output the corresponding ``weight'' of the relevant pixels. 
% This suggested us that NLM is probably not essential in my SCoBeP based SR algorithm. 
Thus, I have introduced and implemented a new SCoBeP based SR algorithm, SCoBeP-SR, where ``mixing'' weights and candidates are extracted from the SCoBeP step only. 
% I have named this algorithm SCoBeP-SR in contrast of the original algorithm, SCoBeP-NLM which I will describe in the next subsection.

% Essentially the same original formulation of SCoBeP-NLM can be retained for SCoBeP-SR. The only difference, as mentioned above, is how the weight is computed. 
The method for calculating $\mathcal{W}[i,j,q,l,b,t]$ for SCoBeP-SR is based on the materials that \replace{have been}{were} developed in {section} \ref{SCoBeP_Conf}.
As some candidate locations and the corresponding belief are available from the SCoBeP output. I will simply assign the weights as zero except the candidate locations and the weights precisely as the beliefs output from SCoBeP. More precisely, I define 

\begin{align}
\mathcal{W}[i,j,q,l,b,t]= I ({cp}_{qlt}^b = [i,j]) \rho^{(b)}_{qlt},
\label{eq:weight2}
\end {align}
where $I ({cp}_{qlt}^b = [i,j])$ is an indicator function which is equal to $1$ if ${cp}_{qlt}^b = [i,j]$ and $0$ otherwise.
To maintain the original formulation, the neighborhood function of a patch $\mathcal{P}$ will just equal to the patch itself. That is, $\mathcal{N} (\mathcal{P}) = \mathcal{P}$.

}}

{{

\subsection{Calculate Weights for SCoBeP-NLM}\label{SR_Weight}

% Essentially the same original formulation of SCoBeP-SR can be retained for SCoBeP-NLM. The only difference is how the weight is computed. 
In this subsection, the method for estimating $\mathcal{W}[i,j,q,l,b,t]$, based on the materials that \replace{have been}{were} developed in \replace{Sections}{section} \ref{SR_RW} and \ref{SCoBeP_Conf}\ths{,} is proposed as follows:

\begin{landscape}
\begin{figure} [t]
   \begin{center}
       \scalebox{.5}{
           \includegraphics{Figs_tables/ScoBePweight}}
   \end{center}
%    \vspace{-10pt}
           \caption{ {{{Candidate pixel and weight computation in SCoBeP. For the patch in the middle frame, SCoBeP weights the found candidate pixels along the space-time.}}}
% {Suppose I estimate a pixel at the middle frame in the input video, my SCoBeP weights the found candidate pixels along the space-time.}
}
% \vspace{-17pt}
           \label{Weights}
\end{figure}
\end{landscape}
% \comm{Again, I don't think equation is actually correct. when q=ri and l=rj,  there will be a local maximum because of f regardless of value of $cp_{qlt}$. something has to be wrong.}  
% \begin{equation}
\begin{align}\nonumber
\mathcal{W}[i,j,q,l,b,t]=&\rho^{(b)}_{qlt} exp\left \{ -\frac{\left \|R_{q,l}\mathcal{Z}-R_{cp^{(b)}_{qlt}}y_t \right \|_2^2}{2\sigma^2}\right \}\\ \times&f(\sqrt{(q-ri)^2+(l-rj)^2+ \xi (t-t_c)^2}),
\label{eq:weight}
\end {align}
% \end{equation}
where
% \begin{equation}
%  \phi^{(b)}_{qlt} = %\rho^{(b)}_{qlt}
%  R_{cp^{(b)}_{qlt}}y_t
% \label{eq:U}
% \end{equation}
% is the extracted patch at the $b^{th}$ candidate pixel scaled by the prior probability found during the SCoBeP step}},
 $t_c$ is the frame number of the output frame (see Fig.~\ref{Weights}), \ths{and $\xi$ is a scaling factor taking into account the difference in scale along the temporal and spatial dimensions. }
% {{Since $[i,j]$ can be anywhere in the interpolated LR image $y_t$, the value of $(q-ri)^2$ and $(l-rj)^2$ may ignore the value of $(t-t_c)^2$, thus I scale up $(t-t_c)^2$ by factor $\xi$.}}
Note that I denote here  $\rho^{(b)}_{qlt}$ as the $b^{th}$ element of $\rho_{qlt}$ (the probability of pixel $[q,l]$ in the reference frame mapping to the $b^{th}$ candidate pixel in $t^{th}$  interpolated LR frame), and $cp^{(b)}_{qlt}$ as the $b^{th}$ row of $cp_{qlt}$ (the $b^{th}$ candidate location described by $cp_{qlt}$). Hence, $R_{cp^{(b)}_{qlt}}$ in \eqref{eq:weight} extracts a patch at the position $cp^{(b)}_{qlt}$ from frame $y_t$.
To follow the \replace{notation}{notations} easily, I summarized them in Table \ref{table_Notation}.


Note that computing weights involves the knowledge of the unknown frame $\mathcal{Z}$. For first iteration, the weights are computed by using an estimated version of $\mathcal{Z}$, which is \ths{a} scaled-up \ths{frame generated} by a conventional image interpolation algorithm such as bicubic, bilinear, or the lanczos method \cite{burger2009principles,keys1981cubic,wolberg1990digital}. For the remaining iterations, the weights are computed using the estimated $\mathcal{Z}$ obtained in the previous iteration. The main procedure for my proposed methods are summarized in Algorithm \ref{tb:algorithm}, and also graphically depicted in Fig.~\ref{dg:model}. {{Note that in Algorithm \ref{tb:algorithm}, one can either pick SCoBeP-SR weights or SCoBeP-NLM weights for computing the weights.}}
}}

{{
As a summary of my approaches, I was able to write and minimize my cost function which has two terms: 
\begin{eqnarray}
\nonumber
\lefteqn{\epsilon^2_{MAP}(\mathcal{X})=}\\ \nonumber
&&\frac{1}{2}\sum_{t=1}^{T}\sum_{[q,l]\in \mathcal{I}}\sum_{b=1}^{n}\sum_{[i,j]|[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]
\\
&&\times \left \| DR^H_{q,l}H\mathcal{X}-R^L_{i,j}\mathcal{Y}_t\right \|^2_2 +\lambda \cdot TV(\mathcal{X}). 
\label{eq:Final_MAP}
\end{eqnarray}

As described in Section \ref{SR_Back}, I followed \cite{farsiu2004fast,protter2009super,Protter09generalizingthe} and decomposed (\ref{eq:Final_MAP}) into two steps:
\begin{enumerate}
 \item compute a blurred version of HR $\mathcal{Z}$ which $\mathcal{Z} = H\mathcal{X}$ by minimizing
\begin{eqnarray}
\nonumber
\lefteqn{\epsilon^2_{ML}(\mathcal{Z})= }\\ \nonumber
&&\frac{1}{2}\sum_{t=1}^{T}\sum_{[q,l]\in \mathcal{I}}\sum_{b=1}^{n}\sum_{[i,j]|[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]
\\ 
&&\times \left \| DR^H_{q,l}\mathcal{Z}-R^L_{i,j}\mathcal{Y}_t\right \|^2_2 ,
\label{eq:ML}
\end{eqnarray}

 \item estimate the deblurred frame $\mathcal{X}$ from the found blurred HR $\mathcal{Z}$ in step \ref{step1}:
\begin{equation}
\epsilon^2_{MAP}(\mathcal{X})=\left \| H\mathcal{X}-\mathcal{Z} \right \|_2^2+\lambda \cdot TV(\mathcal{X}),
\label{eq:ZX}
\end{equation}
\end{enumerate}

{{I introduced the first step in Sections \ref{SCoBeP_Conf}, \ref{SCoBeP_SR}{{, and \ref{SR_Weight}}}}}, and as the second step is the conventional deblurring problem, many works can be applied here, which I simply adopted (AKTV) regularized locally-adaptive kernel regression in a variational approach developed by Takeda \textit{et al.} \cite{takeda2008deblurring}.  
}}

% {\color{red}{
% 
% \subsection{Use SCoBeP \cite{barzigar2012scobep} to compute the location and weights of candidate pixels}\label{SCoBeP_Conf}
% For each pixel in the initial estimate of the HR image, I select from each LR image a set of $n$ candidate pixels which are likely to be most similar to the target pixel. The similarity between a target pixel and a candidate pixel, which will be characterized by a weight, will be used by NLM as to be described in subsequent sections.
% 
% The proposed method described here is inspired by my recent work, SCoBeP \cite{barzigar2012scobep}. First, I extract the features from all interpolated LR images 
% % $\mathcal{Y}_v$ 
% and the reference image $\mathcal{X}$. In this chapter, I focus ourselves on only using block features even though the proposed approach can generally be applied to other features (such as SIFT-features). Thus, each feature considered here is essentially a vectorized block centered around a pixel in an image. Second, to match the extracted features of the reference image to the corresponding extracted features of the $v^{th}$ interpolated LR image $\mathcal{Y}_v$, I create a dictionary which contains all feature vectors of $\mathcal{Y}_v$ and apply sparse coding to each extracted features of the reference image. Sparse coding will reconstruct a reference patch at pixel $[q,l]$ as a linear combination of LR patches. Denote $\alpha_{qlv}$ as the weight vector where each element corresponds to a coefficient in this combination.  Note that $\alpha_{qlv}$ should be sparse, i.e., it should be 0 for most coefficients. To select the $n$ candidate pixels, I simply pick those corresponding to $n$ largest coefficients in $\alpha_{qlv}$.
I denote $cp_{qlv}$ as an $n \times 2$ matrix storing the locations of these candidate pixels and $\rho_{qlv}$ as the length-$n$ vector storing the corresponding values of $\alpha_{qlv}$. Each coefficient in $\rho_{qlv}$ serves as a prior probability of matching the reference patch at $[q,l]$ to a LR patch of $\mathcal{Y}_v$ taking only local characteristic into accounts but ignoring geometric characteristics of the matches. Finally, to incorporate geometric characteristics, I model the problem by a factor graph and apply belief propagation to update probabilities $\rho_{qlv}$ (for more details, see \cite{barzigar2012scobep}).

% {{
% \begin{algorithm} [t]
% \caption{SCoBeP-SR - estimate version of HR frame $\mathcal{X}$ }
% \begin{algorithmic} 
% \renewcommand{\algorithmicrequire}{\textbf{Inputs :}}
% \renewcommand{\algorithmicensure}{\textbf{Output :}}
% \REQUIRE {LR and noisy frames  $\begin{Bmatrix} \mathcal{Y}_t \end{Bmatrix}^T_{t=1}$, resolution ratio $r$, weight patch $R$, frame number $t_c$ and the maximum number of iterations}
% \renewcommand{\algorithmicrequire}{\textbf{Initialize}}
% \REQUIRE { \textbf{:}}
% \begin{itemize}
% %  \item Generate a higher resolution sequence $\begin{Bmatrix} \mathcal{\check{Y}}_t \end{Bmatrix}^T_{t=1}$ by applying bicubic interpolation to all the LR images.
%  \item Set $\mathcal{Z}$ as the bicubic interpolated frame of $\mathcal{Y}_{t_c}$
% %  = \mathcal{\check{Y}}_0$
% %  \item Set $\xi$ and $\omega$ to be the all-zero image with the same size as $\mathcal{Z}$
% \end{itemize}
% 
% \renewcommand{\algorithmicrequire}{\textbf{Iterate :}}
% \REQUIRE {while the maximum number of iterations is not reached}
% \renewcommand{\algorithmicrequire}{\textbf{Use SCoBeP to find candidate pixels :}}
% \REQUIRE {For each increased resolution frame $y_t$}
% 
% \begin{itemize}
% \item Extract dense feature
% \item Construct dictionary $D_t$  
% \item Find the initial estimates of candidate pixel probabilities $\rho_{qlt}$ and candidate pixel locations $cp_{qlt}$
% \item Apply belief propagation to refine $\rho_{qlt}$ and $cp_{qlt}$
% \end{itemize}
% 
% \renewcommand{\algorithmicrequire}{\textbf{Find the blurred HR frame :}}
% \REQUIRE {For each pixel location $[q,l]$ on the HR frame $\mathcal{Z}$ and for $b \in \{1,2,\cdots,n\}$, for each pixel location $[i,j]$ such that $[ri,rj] \in \mathcal{N}(cp^{(b)}_{qlt})$ }
% \begin{itemize}
% 
% \item Compute weights:
% % \begin{enumerate}
%  
% $\mathcal{W}[i,j,q,l,b,t]= I ({cp}_{qlt}^b = [i,j]) \rho^{(b)}_{qlt}$
% 
% % with 
% % ${\phi}^{(b)}_{qlt} =  R_{cp^{(b)}_{qlt} }{y_t}$
% % \end{enumerate}
% \item Compute $\mathcal{Z}$, the blurred version of reconstructed HR frame:
% 
% % \begin{enumerate}
% $\mathcal{Z}[q,l] = \frac{\sum_{t=1}^{T}\sum_{b=1}^{n}\sum_{[i,j]|[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]\mathcal{Y}_t[i,j]}{\sum_{t=1}^{T}\sum_{b=1}^{n}\sum_{[i,j]|[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]}$
% % $\mathcal{Z}[q,l] = \frac{\sum_{t=1}^{T}\sum_{b=1}^{n}\sum_{[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]\mathcal{Y}_t[i,j]}{\sum_{t=1}^{T}\sum_{b=1}^{n}\sum_{[ri,rj]\in {\mathcal{N}(cp^{(b)}_{qlt})}}\mathcal{W}[i,j,q,l,b,t]} $
% % \end{enumerate}
% % \item Update Inputs: $\xi [i,j]= \xi [i,j]+ \mathcal{W}[i,j,q,l,b,t]\mathcal{Y}_t[i,j]$
% 
% % \item Update Weights: $\omega [i,j]= \omega [i,j]+ \mathcal{W}[i,j,q,l,b,t]$
% \end{itemize}
% 
% \renewcommand{\algorithmicrequire}{\textbf{End of Iteration}}
% \REQUIRE {}
% 
% % \renewcommand{\algorithmicrequire}{\textbf{Normalize :}}
% % \REQUIRE {$\mathcal{Z} = \xi [q,l] / \omega [q,l] $}
% \renewcommand{\algorithmicrequire}{\textbf{Perform deblurring :}}
% \REQUIRE {$\mathcal{X}=$TV$deblur(\mathcal{Z})$ }
% \renewcommand{\algorithmicrequire}{\textbf{Output :}}
% \REQUIRE {a HR frame $\mathcal{X}$ }
% \end{algorithmic}
% \label{tb:algorithm2}
% \end{algorithm}}}


\section{Experimental Results}\label{ExResult}
% 
% \begin{figure*} [t!]
%   \centering
%   \centering
%   \subfloat{\label{fig:cc21}\includegraphics[height=4.25cm]{Figs_tables/Mlow/18}}                
%   \subfloat{\label{fig:cc22}\includegraphics[height=4.25cm]{Figs_tables/MElad/18}}
%   \subfloat{\label{fig:cc23}\includegraphics[height=4.25cm]{Figs_tables/MLanczos/18}}
%   \subfloat{\label{fig:cc24}\includegraphics[height=4.25cm]{Figs_tables/MZ0_Miss_18}}                
% \subfloat{\label{fig:cc24}\includegraphics[height=4.25cm]{Figs_tables/MSCoBeP-SR_Miss_18}} 
%    \vspace{-10pt}
% %  \end{figure} 
% % \begin{figure}
%   \centering
%   \subfloat{\label{fig:cc21}\includegraphics[height=4.25cm]{Figs_tables/Mlow/23}}                
%   \subfloat{\label{fig:cc22}\includegraphics[height=4.25cm]{Figs_tables/MElad/23}}
%   \subfloat{\label{fig:cc23}\includegraphics[height=4.25cm]{Figs_tables/MLanczos/23}}
%   \subfloat{\label{fig:cc24}\includegraphics[height=4.25cm]{Figs_tables/MZ0_Miss_23}}       
%   \subfloat{\label{fig:cc24}\includegraphics[height=4.25cm]{Figs_tables/MSCoBeP-SR_Miss_23}} 
%     \vspace{-25pt}
%   \end{figure*} 
%  \begin{figure*}
%   \centering
%   \subfloat[]{\label{fig:cc21}\includegraphics[height=4.25cm]{Figs_tables/Mlow/28}}                
%   \subfloat[]{\label{fig:cc22}\includegraphics[height=4.25cm]{Figs_tables/MElad/28}}
%   \subfloat[]{\label{fig:cc23}\includegraphics[height=4.25cm]{Figs_tables/MLanczos/28}}
%   \subfloat[]{\label{fig:cc24}\includegraphics[height=4.25cm]{Figs_tables/MZ0_Miss_28}}      
%     \subfloat[]{\label{fig:cc24}\includegraphics[height=4.25cm]{Figs_tables/MSCoBeP-SR_Miss_28}}                    
%   \caption{ {Results for the $18^{th}$, $23^{th}$, and $28^{th}$ frame from the ``Miss America'' sequence. From Left column to Right column: LR frame; GNL-Means \cite{Protter09generalizingthe}; Lanczos interpolation \cite{wolberg1990digital}; {{result of the proposed SCoBeP-NLM; result of the proposed SCoBeP-SR.}} The PSNR values for all the frames are also shown in Fig.~\ref{ex:plot}(a).}}
%   \label{ex:Miss_America}
% % \vspace{-17pt}
% \end{figure*}

In this section, I consider in two separated subsections with two different sets of experiments\footnote{\scriptsize{The image frames of  the result sequences using SCoBeP-NLM and SCoBeP-SR are available at http://students.ou.edu/B/Nafise.Barzigar-1/software/SCoBeP-NLM.html.}}. I utilize four test sequences (Miss America, Foreman, Suzie and Stefan) in Section \ref{Ex:old} to compare the performance of my proposed methods with the state-of-the-art methods \cite{takeda2009super,Protter09generalizingthe,babacan2011variational}. In that section I will first generate synthetic LR sequences and next apply super resolution methods to the degraded sequences. I will then compare the results to the ground truth (the original sequences).
Also, in Section \ref{Ex:new}, I will illustrate additional examples that will assess my super resolution methods for real video sequences. 
Comparison will be made against the multi-image super resolution method proposed by Farsui \textit{et al.} \cite{farsiu2004fast}, 3-D ISKR method \cite{takeda2009super}, super resolution Using TV prior method \cite{babacan2011variational} and a single image up-sampling using the Lanczos algorithm \cite{wolberg1990digital}, which were implemented using the software provided by their authors.



\begin{landscape}
\begin{figure*}[t]
%   \centering
%   \subfloat{\label{fig:cc21}\includegraphics[height=4cm]{Figs_tables/FLowQuality_0003}}                
%   \subfloat{\label{fig:cc22}\includegraphics[height=4cm]{Figs_tables/FSR_NLM_0003}}
%   \subfloat{\label{fig:cc23}\includegraphics[height=4cm]{Figs_tables/FLanczos_0003}}
%   \subfloat{\label{fig:cc24}\includegraphics[height=4cm]{Figs_tables/FZ0_Foreman_3}}                
%    \vspace{-10pt}
%  \end{figure} 
% \begin{figure}
  \centering
  \subfloat{\label{fig:cc21}\includegraphics[height=3.2cm]{Figs_tables/FLowQuality_0008}}                
  \subfloat{\label{fig:cc22}\includegraphics[height=3.2cm]{Figs_tables/FSR_NLM_0008}}
  \subfloat{\label{fig:cc23}\includegraphics[height=3.2cm]{Figs_tables/FLanczos_0008}}
  \subfloat{\label{fig:cc24}\includegraphics[height=3.2cm]{Figs_tables/FZ0_Foreman_8}}    
  \subfloat{\label{fig:cc24}\includegraphics[height=3.2cm]{Figs_tables/FSCoBeP-SR_Foreman_frame8}}         
   \vspace{-10pt}
%  \end{figure} 
% \begin{figure}
  \centering
  \subfloat{\label{fig:cc21}\includegraphics[height=3.2cm]{Figs_tables/FLowQuality_0013}}                
  \subfloat{\label{fig:cc22}\includegraphics[height=3.2cm]{Figs_tables/FSR_NLM_0013}}
  \subfloat{\label{fig:cc23}\includegraphics[height=3.2cm]{Figs_tables/FLanczos_0013}}
  \subfloat{\label{fig:cc24}\includegraphics[height=3.2cm]{Figs_tables/FZ0_Foreman_13}}  
  \subfloat{\label{fig:cc24}\includegraphics[height=3.2cm]{Figs_tables/FSCoBeP-SR_Foreman_frame13}}                
   \vspace{-48pt}
%  \end{figure} 
% \begin{figure}
%   \centering
%   \subfloat{\label{fig:cc21}\includegraphics[width=2cm]{Figs_tables/FLowQuality_0018}}                
%   \subfloat{\label{fig:cc22}\includegraphics[width=2cm]{Figs_tables/FSR_NLM_0018}}
%   \subfloat{\label{fig:cc23}\includegraphics[width=2cm]{Figs_tables/FLanczos_0018}}
%   \subfloat{\label{fig:cc24}\includegraphics[width=2cm]{Figs_tables/FZ0_Foreman_18}}                
%    \vspace{-10pt}
  \end{figure*} 
 \begin{figure*}
  \centering
  \subfloat[]{\label{fig:cc21}\includegraphics[height=3.2cm]{Figs_tables/FLowQuality_0023}}                
  \subfloat[]{\label{fig:cc22}\includegraphics[height=3.2cm]{Figs_tables/FSR_NLM_0023}}
  \subfloat[]{\label{fig:cc23}\includegraphics[height=3.2cm]{Figs_tables/FLanczos_0023}}
  \subfloat[]{\label{fig:cc24}\includegraphics[height=3.2cm]{Figs_tables/FZ0_Foreman_23}}   
  \subfloat[]{\label{fig:cc24}\includegraphics[height=3.2cm]{Figs_tables/FSCoBeP-SR_Foreman_frame23}}              
%    \vspace{-25pt}
%  \end{figure} 
% \begin{figure}
%   \centering
%   \subfloat[]{\label{fig:cc21}\includegraphics[width=2cm]{Figs_tables/FLowQuality_0028}}                
%   \subfloat[]{\label{fig:cc22}\includegraphics[width=2cm]{Figs_tables/FSR_NLM_0028}}
%   \subfloat[]{\label{fig:cc23}\includegraphics[width=2cm]{Figs_tables/FLanczos_0028}}
%   \subfloat[]{\label{fig:cc24}\includegraphics[width=2cm]{Figs_tables/FZ0_Foreman_28}}                
%    \vspace{-20pt}              
  \caption{ {Results for the $8^{th}$, $13^{th}$ and $23^{th}$ frame from the ``Foreman'' sequence. From Left column to Right column: LR frame; GNL-Means \cite{Protter09generalizingthe}; Lanczos interpolation \cite{wolberg1990digital}; {{result of the proposed SCoBeP-NLM; result of the proposed SCoBeP-SR.}} Also, the PSNR values for all the frames are shown in Fig.~\ref{ex:plot}(b).}}
%   \vspace{-17pt}
  \label{ex:Foreman}
\end{figure*}
\end{landscape}




\subsection{Evaluation On Synthetic Sequences}\label{Ex:old}
In this section, to evaluate my performance, I present some super resolution examples using existing sequences such as Miss America, Foreman, Suzie, and Stefan. The sequences in this section contain object motions only in the scene and no camera movement.
% ; therefore, the sequences do not globally suffer from any large displacement to compensate motion.
All tests in this section were processed in the following manner: All 30 frames were involved in the reconstruction of each frame. The similar block size used for computing weight ($R$) was $13 \times 13$ and was not changed for various tests. The low patch extraction operator $R^L_{i,j}$ extracts only one pixel, therefore the $R^H_{q,l}$ extracts a patch of size $3 \times 3$ pixels. Also, the search area (the size of neighborhood $\mathcal{N}$) is $31 \times 31 $ pixels. I set the parameter $\sigma = 2.2$ and the maximum number of \replace{iterations}{iteration} equal to $2$ for all sequences.

\begin{landscape}
\begin{figure} [t]
\centering
  \subfloat[Miss America]{\label{subfig:MissAmerica}\includegraphics[width=7cm]{Figs_tables/Plot_Miss_New}}  
   \subfloat[Foreman]{\label{subfig:Foreman}\includegraphics[width=7cm]{Figs_tables/Plot_Foreman_new}}     
   \subfloat[Suzie]{\label{subfig:Suzie}\includegraphics[width=7cm]{Figs_tables/Plot_Suzie_New}} 
  \caption{{{ { PSNR values of each super resolved frame by Lanczos \cite{wolberg1990digital}, GNL-Means \cite{Protter09generalizingthe}, and the proposed method for (a) the results of Miss America shown in Fig.~\ref{ex:MissZoom1}, (b) the results of Foreman shown in Fig.~\ref{ex:Foreman}, and (c) the results of Suzie shown in Fig.~\ref{ex:Suzie}. 
  The average PSNR values for all frames for the Miss America example are $34.12 [dB]$ (Lanczos), $35.09 [dB]$ (GNL-Means \cite{Protter09generalizingthe}),{{ $35.73 [DB]$ (SCoBeP-SR)}} and $35.94 [dB]$ (SCoBeP-NLM) and the average PSNR values for the Foreman example are $28.51 [dB]$ (Lanczos), $29.01 [dB]$ (GNL-Means \cite{Protter09generalizingthe}), {{$29.71 [DB]$ (SCoBeP-SR)}} and $29.80 [dB]$ (SCoBeP-NLM), and also the average PSNR values for the Suzie example are $29.73 [dB]$ (Lanczos), $29.79[dB]$ (GNL-Means \cite{Protter09generalizingthe}), {{$30.56 [DB]$ (SCoBeP-SR)}} and $30.77 [dB]$ (SCoBeP-NLM), respectively.}}}}
  \label{ex:plot}
\end{figure}
\end{landscape}


\begin{landscape}
\begin{figure*}
  \centering
  \subfloat{\label{fig:cc21}\includegraphics[height=2.5cm]{Figs_tables/SLowQuality_0003}}                
  \subfloat{\label{fig:cc22}\includegraphics[height=2.5cm]{Figs_tables/SSR_NLM_0003}}
  \subfloat{\label{fig:cc23}\includegraphics[height=2.5cm]{Figs_tables/SLanczos_0003}}
  \subfloat{\label{fig:cc24}\includegraphics[height=2.5cm]{Figs_tables/SZ0_Suzie_3}} 
   \subfloat{\label{fig:cc24}\includegraphics[height=2.5cm]{Figs_tables/SSCoBeP-SR_Suzie_frame3}}           
%    \vspace{-10pt}
%  \end{figure} 
% \begin{figure}
%   \centering
%   \subfloat{\label{fig:cc21}\includegraphics[height=3cm]{Figs_tables/SLowQuality_0008}}                
%   \subfloat{\label{fig:cc22}\includegraphics[height=3cm]{Figs_tables/SSR_NLM_0008}}
%   \subfloat{\label{fig:cc23}\includegraphics[height=3cm]{Figs_tables/SLanczos_0008}}
%   \subfloat{\label{fig:cc24}\includegraphics[height=3cm]{Figs_tables/SZ0_Suzie_8}}                
%    \vspace{-10pt}
%  \end{figure} 
% \begin{figure}
%   \centering
%   \subfloat{\label{fig:cc21}\includegraphics[height=3cm]{Figs_tables/SLowQuality_0013}}                
%   \subfloat{\label{fig:cc22}\includegraphics[height=3cm]{Figs_tables/SSR_NLM_0013}}
%   \subfloat{\label{fig:cc23}\includegraphics[height=3cm]{Figs_tables/SLanczos_0013}}
%   \subfloat{\label{fig:cc24}\includegraphics[height=3cm]{Figs_tables/SZ0_Suzie_13}}                
%    \vspace{-22pt}
%  \end{figure} 
%  \begin{figure}

%   \centering
%   \subfloat{\label{fig:cc21}\includegraphics[height=2.5cm]{Figs_tables/SLowQuality_0018}}                
%   \subfloat{\label{fig:cc22}\includegraphics[height=2.5cm]{Figs_tables/SSR_NLM_0018}}
%   \subfloat{\label{fig:cc23}\includegraphics[height=2.5cm]{Figs_tables/SLanczos_0018}}
%   \subfloat{\label{fig:cc24}\includegraphics[width=2cm]{Figs_tables/SZ0_Suzie_18}}                
 \vspace{-10pt} 
% \end{figure*} 
% \begin{figure*} 
\centering
  \subfloat[]{\label{fig:cc21}\includegraphics[height=2.5cm]{Figs_tables/SLowQuality_0023}}                
  \subfloat[]{\label{fig:cc22}\includegraphics[height=2.5cm]{Figs_tables/SSR_NLM_0023}}
  \subfloat[]{\label{fig:cc23}\includegraphics[height=2.5cm]{Figs_tables/SLanczos_0023}}
  \subfloat[]{\label{fig:cc24}\includegraphics[height=2.5cm]{Figs_tables/SZ0_Suzie_23}}
 \subfloat[]{\label{fig:cc24}\includegraphics[height=2.5cm]{Figs_tables/SSCoBeP-SR_Suzie_frame23}}                 
%    \vspace{-22pt}
%  \end{figure} 
% \begin{figure}
%   \centering
%   \subfloat[]{\label{fig:cc21}\includegraphics[width=2cm]{Figs_tables/SLowQuality_0028}}                
%   \subfloat[]{\label{fig:cc22}\includegraphics[width=2cm]{Figs_tables/SSR_NLM_0028}}
%   \subfloat[]{\label{fig:cc23}\includegraphics[width=2cm]{Figs_tables/SLanczos_0028}}
%   \subfloat[]{\label{fig:cc24}\includegraphics[width=2cm]{Figs_tables/SZ0_Suzie_28}}                
%                 
  \caption{ {Results for the $3^{th}$ and $23^{th}$ frame from the ``Suzie'' sequence. From Left column to Right column: LR frame; GNL-Means \cite{Protter09generalizingthe}; Lanczos interpolation \cite{wolberg1990digital}; {{result of the proposed SCoBeP-NLM; result of the proposed SCoBeP-SR.}} Also, the PSNR values for all the frames are shown in Fig.~\ref{ex:plot}(c).}}
  \label{ex:Suzie}
\end{figure*}
\end{landscape}

% 
% \begin{table*}[!t]
% \renewcommand{\arraystretch}{1.3}
% \caption{AVERAGE PSNR FOR THE TWO VIDEO SEQUENCES}
% \label{table_example}
% \centering
% \begin{tabular}{|c||c|c|c|c|}  
%   \hline
%   \textbf{ Sequence} & \textbf{Nearest Neighborhood} & \textbf{Lanczos \cite{wolberg1990digital}} & \textbf{GNL-Means \cite{Protter09generalizingthe}} & \textbf{Proposed Method} \\
%   \hline
%   \hline
% %   \multirow{2}{*}
%     {Miss America} 	& 32.4 & 34.12 & 35.09 & 35.94\\  \hline
%     {Foreman  } 	& 27.45 & 28.51 & 29.01 & 29.80\\  \hline
%  {Suzie} 	& 28.94 & 29.73 & 29.79 & 30.77\\
%   \hline
% \end{tabular}
% \label{tb:average}
% \end{table*}

\begin{landscape}
    \centering
 \begin{table*}[!b]
% \renewcommand{\arraystretch}{1}
% \caption{PSNR (Top) and SSIM (Bottom) FOR $8^{th}$ and $13^{th}$ FRAMS OF MISS AMERICA SEQUENCE}
\caption{PSNR for $8^{th}$ and $13^{th}$ frames of Miss America Sequence}
\begin{tabular}{|p{2.5cm}|p{2.5cm}||p{2.5cm}|p{2.5cm}|p{2.5cm}|p{2.5cm}|p{2.5cm}|p{2.5cm}|}  
  \hline
%  \multicolumn {2}{|c||} 
{\textbf{Miss America Sequence}} & \textbf{Nearest Neighborhood} & \textbf{Lanczos \cite{wolberg1990digital}} & \textbf{GNL-Means \cite{Protter09generalizingthe}} & \textbf{3-D ISKR \cite{takeda2009super}}& \textbf{SCoBeP-NLM} & \textbf{SCoBeP-SR} \\
  \hline
  \hline
%   \multirow{2}{*}
 {$8^{th}$ frame   }
% & PSNR	
& 32.97 &  34.76 & 34.49 & 35.53 & 36.28  & 36.20\\ 
% \cline{2-7}  	& SSIM & 0.85 & 0.89  & 0.90 & 0.90 & 0.91\\ \hline \hline
   \hline
% \multirow{2}{*}
 { $13^{th}$ frame 	}
% & PSNR
& 32.74 & 34.48 & 35.33 & 35.15 & 36.33 & 36.02\\ 
%  \cline{2-7}	& SSIM& 0.84 &  0.90 & 0.91 & 0.90 & 0.91 \\
   \hline

\end{tabular}
\label{tb:8-13frames}
 \end{table*}
\label{table_example}
\end{landscape}

\begin{landscape}
\begin{figure*}[h]
\centering
\subfloat{\label{fig:farsui_large}\includegraphics[width=3cm]{Figs_tables/SGT_28}}
  \subfloat{\label{fig:cc21}\includegraphics[width=3cm]{Figs_tables/SLowQuality_0028}}                
  \subfloat{\label{fig:cc22}\includegraphics[width=3cm]{Figs_tables/SSR_NLM_0028}}
  \subfloat{\label{fig:cc23}\includegraphics[width=3cm]{Figs_tables/SLanczos_0028}}
  \subfloat{\label{fig:cc24}\includegraphics[width=3cm]{Figs_tables/SZ0_Suzie_frame28_DEB}}
 \subfloat{\label{fig:cc24}\includegraphics[width=3cm]{Figs_tables/SCoBeP-SR_Suzie_frame28}}
\vspace{-10pt}
  \centering
\subfloat{\label{fig:farsui_large}\includegraphics[width=3cm]{Figs_tables/SGT_18}}
  \subfloat{\label{fig:cc21}\includegraphics[width=3cm]{Figs_tables/SLowQuality_0018}}                
  \subfloat{\label{fig:cc22}\includegraphics[width=3cm]{Figs_tables/SSR_NLM_0018}}
  \subfloat{\label{fig:cc23}\includegraphics[width=3cm]{Figs_tables/SLanczos_0018}}
  \subfloat{\label{fig:cc24}\includegraphics[width=3cm]{Figs_tables/SZ0_Suzie_frame18_DEB}}
  \subfloat{\label{fig:cc24}\includegraphics[width=3cm]{Figs_tables/SCoBeP-SR_Suzie_frame18}}                
\vspace{-10pt}
\centering
  \subfloat{\label{fig:cc31}\includegraphics[height=3cm]{Figs_tables/GT_18_Crop}}
  \subfloat{\label{fig:cc31}\includegraphics[height=3cm]{Figs_tables/low18}}                
  \subfloat{\label{fig:cc32}\includegraphics[height=3cm]{Figs_tables/Elad18}}
  \subfloat{\label{fig:cc33}\includegraphics[height=3cm]{Figs_tables/Lanczos18}}
  \subfloat{\label{fig:cc34}\includegraphics[height=3cm]{Figs_tables/P18}} 
\subfloat{\label{fig:cc24}\includegraphics[width=3.06cm]{Figs_tables/SCoBeP-SR_Suzie_Zoom_frame18}}
% \vspace{-10pt}
              
%    \vspace{-10pt}
% %  \end{figure*} 
% %   \begin{figure*}
% \centering
%   \subfloat{\label{fig:cc31}\includegraphics[width=4cm]{Figs_tables/SSuzie-LR_small28_line}}                
%   \subfloat{\label{fig:cc32}\includegraphics[width=4cm]{Figs_tables/SSuzie-Elad_small28_line}}
%   \subfloat{\label{fig:cc33}\includegraphics[width=4cm]{Figs_tables/SSuzie-Lancsoz_small28_line}}
%   \subfloat{\label{fig:cc34}\includegraphics[width=4cm]{Figs_tables/SSuzie-SCOBeP_small28_line}}                
\caption{ {Video super resolution for Suzie sequence: (frame $28$ and $18$ with the resolution ratio 3, PSNR in brackets). From Left column to Right column: Ground truth; LR frame; GNL-Means \cite{Protter09generalizingthe} [PSNR: $29.87$ - $29.86$]; Lanczos interpolation \cite{wolberg1990digital} [PSNR: $29.41$ - $29.27$]; SCoBeP-NLM [PSNR: $30.95$ - $30.75$]; SCoBeP-SR [PSNR: $30.55$ - $30.71$].}}
  \label{ex:suzie}
\end{figure*}
\end{landscape}


\begin{landscape}
\begin{figure*} [htb]
  \centering
\subfloat{\label{fig:farsui_large}\includegraphics[width=3.75cm]{Figs_tables/FGT_22_Crop}}
  \subfloat{\label{fig:farsui_large}\includegraphics[width=3.75cm]{Figs_tables/FElad_22_Zoom}}  \subfloat{\label{fig:farsui_large}\includegraphics[width=3.75cm]{Figs_tables/Foreman_ISKR_22}}
  \subfloat{\label{fig:farsui_large}\includegraphics[width=3.7cm]{Figs_tables/FNLKR_22_ZoomIn}}
  \subfloat{\label{fig:SCoBeP-large}\includegraphics[width=3.75cm]{Figs_tables/FZ0_22_Zoom}}                
    \vspace{-10pt}
%     \end{figure*} 
%     \begin{figure*}
  \centering
\subfloat{\label{fig:farsui_large}\includegraphics[width=3.75cm]{Figs_tables/FGT_28_Crop}}
  \subfloat{\label{fig:farsui}\includegraphics[width=3.75cm]{Figs_tables/FElad__28_Zoom}}
 \subfloat{\label{fig:farsui}\includegraphics[width=3.75cm]{Figs_tables/Foreman_ISKR_28}}
 \subfloat{\label{fig:farsui}\includegraphics[width=3.7cm]{Figs_tables/FNLKR_Zoom_28}}
  \subfloat{\label{fig:ScoBep}\includegraphics[width=3.75cm]{Figs_tables/FZ0__28_Zoom}}                
  \caption{ {Video super resolution for Foreman sequence: From Left column to Right column: Ground truth; GNL-Means \cite{Protter09generalizingthe}; 3-D ISKR \cite{takeda2009super}; NLKR \cite{zhang2010non}; {result of the proposed SCoBeP-NLM.}}}
  \label{ex:ForemanZoom}
\end{figure*}
\end{landscape}

\begin{landscape}
\begin{figure*} [t]
  \centering
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/MGT_8}}
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/MLanczos_0008}}  
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/Miss_Elad8}}   
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/Miss_ISKR8}}   
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/SRUsingTVprior_8Miss_newversiopn}}
\subfloat[]{\label{fig:SCoBeP-large}\includegraphics[height=3.8cm]{Figs_tables/Miss_SCoBeP8}}   
\subfloat[]{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/SCoBeP-SR_Miss_frame22}}  
\vspace{-27pt} 
\centering
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/MGT_13}}
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/MLanczos_0013}}
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/Miss_Elad13}}  
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/Miss_ISKR13}}
% \vspace{-7pt} 
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/SRUsingTVprior_13Miss_newversion}}           
\subfloat{\label{fig:SCoBeP-large}\includegraphics[height=3.8cm]{Figs_tables/Miss_SCoBeP13}} 
\subfloat{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/SCoBeP-SR_Miss_frame13}}  
\caption{ {Video super resolution for Miss America sequence; frame 8 (top) and frame 13 (bottom): From left to right: Ground truth; Lanczos interpolation \cite{wolberg1990digital}; GNL-Means \cite{Protter09generalizingthe}; 3-D ISKR \cite{takeda2009super}; super resolution Using TV prior \cite{babacan2011variational}; SCoBeP-NLM; SCoBeP-SR.}}
%   \vspace{-20pt} 
  \label{ex:MissZoom1}
\end{figure*}
\end{landscape}

% 
% \begin{figure*} [t]
%   \centering
% \subfloat[]{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/MGT_13}}
% \subfloat[]{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/MLanczos_0013}}
% \subfloat[]{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/MMiss_Elad13}}  
% \subfloat[]{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/MMiss_ISKR13}}
% % \vspace{-7pt} 
% \subfloat[]{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/MSRUsingTVprior_13Miss_newversion}}
% % \subfloat[]{\label{fig:farsui_large}\includegraphics[height=5cm]{Figs_tables/MMiss_13_Vande_POCS}}              
% \subfloat[]{\label{fig:SCoBeP-large}\includegraphics[height=3.8cm]{Figs_tables/MMiss_SCoBeP13}} 
% \subfloat[]{\label{fig:farsui_large}\includegraphics[height=3.8cm]{Figs_tables/SCoBeP-SR/SCoBeP-SR_Miss_frame13}}  
% 
% \caption{ {Video super resolution for Miss America sequence (frame 13): (a) Ground truth; (b) Lanczos interpolation \cite{wolberg1990digital}; (c) GNL-Means \cite{Protter09generalizingthe};  (d) 3-D ISKR \cite{takeda2009super}; (e) super resolution Using TV prior \cite{babacan2011variational}; (f) SCoBeP-NLM; (g) SCoBeP-SR.}}
%   \label{ex:MissZoom2}
% \end{figure*}

% \begin{landscape}
\begin{figure} [t]
  \centering
\subfloat{\includegraphics[height=5.2cm]{Figs_tables/SLR_22}}   
\subfloat{\includegraphics[height=5.2cm]{Figs_tables/SLR_22_Zoom}} 
\vspace{-9pt} 
\subfloat{\includegraphics[height=5.2cm]{Figs_tables/SISKR_22}}  
\subfloat{\includegraphics[height=5.2cm]{Figs_tables/SISKR_22_Zoom}}
\vspace{-9pt} 
\subfloat{\includegraphics[height=5.2cm]{Figs_tables/SSCoBeP_22}} 
\subfloat{\includegraphics[height=5.2cm]{Figs_tables/SSCoBeP_22_Zoom}} 
% \vspace{-9pt}
%    \vspace{-10pt}     
 \caption{ {Video psuper resolution for Stefan sequence: From top to bottom column: LR frame; 3-D ISKR \cite{takeda2009super};  result of the proposed SCoBeP-NLM.}}
%  \vspace{-17pt} 
  \label{ex:Stefan}
\end{figure}
% \end{landscape}


% The method GNL-Means \cite{protter2009super} provides an appropriate example for comparison. First of all, both GNL-Means and my work are estimated based on the non-local similarity concept, thus the same kind of view is exploited in both methods. Second, the HR and SR reconstructed sequences are available online, so, they make the experiments in a fair situation. Finally, GNL-Means presented high quality results.



To generate the LR frames, first, I degrade the test sequences by blurring the videos with a $3 \times 3$ uniform point spread function (PSF) and downsampling them by a resolution ratio of $3:1$ in both horizontal and vertical directions. Then the white Gaussian noise with standard deviation of $\sigma_{noise} =2$ is added to each frame. {{ Two of the selected LR sequences, Foreman and Suzie for frame numbers $8, 13, 23$, and frame numbers $3, 23$ are shown in Figs.~\ref{ex:Foreman}(a), and \ref{ex:Suzie}(a), respectively. Then, I upscale the degraded videos using the Lanczos interpolation \cite{wolberg1990digital}, the GNL-Means method \cite{Protter09generalizingthe}, and my proposed methods. Figs.~\ref{ex:Foreman}(b)--(e), and \ref{ex:Suzie}(b)--(e), respectively, show the results.
% Three of the selected LR sequences, Miss America, Foreman and Suzie for frame numbers $18, 23, 28$, frame numbers $8, 13, 23$, and frame numbers $3, 23$ are shown in Figs.~\ref{ex:Miss_America}(a), \ref{ex:Foreman}(a), and \ref{ex:Suzie}(a), respectively. Then, I upscale the degraded videos using the Lanczos interpolation \cite{wolberg1990digital}, the GNL-Means method \cite{Protter09generalizingthe}, and my proposed methods. Figs.~\ref{ex:Miss_America}(b)--(e), \ref{ex:Foreman}(b)--(e), and \ref{ex:Suzie}(b)--(e), respectively, show the results.
}}



The graphs\footnote{\scriptsize{The PSNR results of 3D-ISKR \cite{takeda2009super} are not listed as they are not available in their original paper.}} in Fig.~\ref{ex:plot} show the frame by frame PSNR
% \footnote{\scriptsize{Peak Signal to Noise Ratio $= 10\ \ log_{10}(255^2/Mean\ \ Square \ \ Error) [dB]$.}} 
values of Miss America, Foreman and Suzie. My proposed methods beats the GNL-Means method in all frames by a significant margin for all sequences. The average PSNR values for my proposed methods and the compared methods are shown in the caption of Fig.~\ref{ex:plot}.
% all frames for the Miss America example are $34.12 [dB]$ (Lanczos), $35.09 [dB]$ (GNL-Means \cite{protter2009super}), and $35.47 [dB]$ (SCoBeP-NLM) and the average PSNR values for Foreman example are $28.51 [dB]$ (Lanczos), $29.01 [dB]$ (GNL-Means \cite{protter2009super}), and $29.36 [dB]$ (SCoBeP-NLM), and also the average PSNR values for the Suzie example are $29.73 [dB]$ (Lanczos), $29.79 [dB]$ (GNL-Means \cite{protter2009super}), and $30.65 [dB]$ (SCoBeP-NLM), respectively (see Table (\ref{tb:average})). Besides the increased PSNR values (Table (\ref{tb:average})), 


% {\color{red}  Reviewer 1: There is however one thing about the experimental section that irritates me: the comparison images are all much lighter than those of the proposed method. This makes comparison hard, so I say major and not minor revision. This issue needs to be fixed.
% 
% 
% 
% Reviewer 2:  I do not understand why the contrast has changed in the proposed algorithm's result. This is very undesirable – the super-resolved image should maintain the characteristics of the original sequence. It also makes the comparison the state-of-the-art problematic, as it is comparing two different things.
% 
% }
% Although my SR images are not perceptually as sharp as those by the GNL-Means method \cite{Protter09generalizingthe}, I can observe that in terms of ringing artifacts, my results are indeed much cleaner and provide the same reconstructed image details.

The PSNR results of $8^{th}$ and $13^{th}$ frames of the Miss America sequence are summarized in Table \ref{tb:8-13frames}, showing that the proposed methods again constantly outperform the current state-of-the-art methods. Note that the results from 3-D ISKR method is cited directly from \cite{takeda2009super}. In Fig.~\ref{ex:suzie}, I show the PSNR result and a clear visual comparison on the Suzie sequence.
As shown in Fig.~\ref{ex:suzie}, although the GNL-Means method \cite{Protter09generalizingthe} acts well at regular-structured areas, it suffers from block artifacts\footnote{Please note that I have adopted the terminology ``block artifact'' from \cite{zhang2010non}. The terminology is different from the artifacts typically found in low bitrate compressed image by old JPEG.} due to poor block matching. In contrast, my proposed methods performs remarkably well for both regular and detail structures and is free of these artifacts. {{In Fig.~\ref{ex:ForemanZoom}, I further show the results of Foreman sequence compared with the GNL-Means method \cite{Protter09generalizingthe}, 3-D ISKR method \cite{takeda2009super} and NLKR \cite{zhang2010non}. The super resolution results on Miss America sequence in frames $8$ and $13$ and Stefan sequence are also given in  Figs.~\ref{ex:MissZoom1} and \ref{ex:Stefan}, respectively for visual comparison. The proposed methods outperform the other methods by notable improvement.}}




{{

Moreover, I examined how my methods perform under various noise levels. I added white Gaussian noise with standard deviation $\sigma_n$ (varying from $0$ to $2$) to the LR sequences, where the sequence with $\sigma_n = 0$ was degraded by the downsampling process only. Table \ref{tb:FormanNoisy} shows that both SCoBeP-NLM and SCoBeP-SR are able to produce fine details when the noise level is increasing. For a clear comparison on varying noise level, I show the results of a noise added Foreman sequence in Fig.~\ref{ex:ForemanNoisy}, where I compared my algorithms with the state-of-the-art 3-D ISKR \cite{takeda2009super}.




\begin{figure} [t]
  \centering
\subfloat{\label{fig:farsui_large}\includegraphics[width=5cm]{Figs_tables/FNoisy_1.2_1}}
\subfloat{\label{fig:farsui_large}\includegraphics[width=5cm, height = 4.7 cm ]{Figs_tables/FNoisy_2_1}}
\vspace{-10pt}

\subfloat{\label{fig:farsui_large}\includegraphics[width=5cm]{Figs_tables/F3D_ISKR_Noisy_1.2_1}}
\subfloat{\label{fig:farsui}\includegraphics[width=5cm]{Figs_tables/F3D_ISKR_Noisy_2_1}}
\vspace{-10pt}

\subfloat{\label{fig:farsui_large}\includegraphics[width=5cm]{Figs_tables/FSCoBeP_NLM_Noisy_1.2_1}}  
\subfloat{\label{fig:farsui}\includegraphics[width=5cm]{Figs_tables/FSCoBeP_NLM_Noisy_2_1}}
\vspace{-10pt}

\subfloat{\label{fig:SCoBeP-large}\includegraphics[width=5cm]{Figs_tables/FSCoBeP_SR_Noisy_1.2_1}} 
\subfloat{\label{fig:ScoBep}\includegraphics[width=5cm]{Figs_tables/FSCoBeP_SR_Noisy_2_1}}           
%     \vspace{-9pt}
%     \end{figure*} 
%     \begin{figure*}
%   \centering                 
\caption{ {{{Video super resolution for Foreman sequence with noise: I added synthetic additive white Gaussian noise (AWGN) to the input LR sequence, with the noise level $\sigma_n=1.20$ (left) and $\sigma_n=2.00$ (right). 
  From top to bottom column: Noisy LR; 3-D ISKR \cite{takeda2009super}; SCoBeP-NLM; SCoBeP-SR.}}}}
  \label{ex:ForemanNoisy}
%    \vspace{-20pt}
\end{figure}




\begin{landscape}
\begin{table}[t]
\renewcommand{\arraystretch}{2}
% \caption{PSNR (Top) and SSIM (Bottom) FOR $8^{th}$ and $13^{th}$ FRAMS OF MISS AMERICA SEQUENCE}
\caption{Noise Addition: PSNR for $1^{st}$ frame of Foreman Sequence}
\label{table_example}
\centering
% \scriptsize
\begin{tabular}{|c||c|c|c|c|c|}  
  \hline
%  \multicolumn {2}{|c||} 
{}  & \textbf{Lanczos \cite{wolberg1990digital}} &  \textbf{3-D ISKR \cite{takeda2009super}}& \textbf{SCoBeP-NLM} & \textbf{SCoBeP-SR} \\
  \hline
  \hline
%   \multirow{2}{*}
 {$\sigma_n=0.00$}
% & PSNR	
& 28.51  & 28.94 & 29.88 & 29.76\\ 
% \cline{2-7}  	& SSIM & 0.85 & 0.89  & 0.90 & 0.90 & 0.91\\ \hline \hline
   \hline
% \multirow{2}{*}
 {$\sigma_n=1.20$n}
% & PSNR
&  28.44  & 28.93 & 29.86 & 29.74\\ 
%  \cline{2-7}	& SSIM& 0.84 &  0.90 & 0.91 & 0.90 & 0.91 \\
   \hline
 {$\sigma_n=1.60$}
% & PSNR
&  28.36  & 28.87 & 29.83 & 29.73 \\ 
%  \cline{2-7}	& SSIM& 0.84 &  0.90 & 0.91 & 0.90 & 0.91 \\
   \hline
 {$\sigma_n=2.00$}
% & PSNR
&  28.25  & 28.86 & 29.75 & 29.68\\ 
%  \cline{2-7}	& SSIM& 0.84 &  0.90 & 0.91 & 0.90 & 0.91 \\
   \hline
\end{tabular}
\label{tb:FormanNoisy}
\end{table}
\end{landscape}







}}

\subsection{Evaluation on Real video Sequences}\label{Ex:new}
In this section, I turn to some real sequences, where I apply my proposed methods \replace{directly to the captured sequences without altering the frames}{ without any changes or generating the LR frames}. Note that there are no published methods that \replace{have tested on}{perform super resolution on} \replace{real}{such general} sequences\replace{. As no standard sequence is available, I have captured a sequence for testing and with camera motion intentionally introduced. We}{, we} choose the multi-image super resolution method proposed by Farsui \textit{et al.} \cite{farsiu2004fast}, 3-D ISKR method \cite{takeda2009super}, super resolution Using TV prior method \cite{babacan2011variational} and a single image up-sampling using the Lanczos algorithm \cite{wolberg1990digital} for comparison because their source \replace{codes are available publicly.}{code is available.} 
% \delete{Also, for this set of real video sequences, the camera can move when recording the video.}
\replace{Since no ground truth is available for a real sequence, I cannot evaluate the resulting HR frames with objective measure such as PSNR.}{In order to apply my methods directly to the frames taken by the camera, I do not have their HR frames to compare and calculate the PSNR,}
\replace{However, the perceptual quality illustrate the robustness of}{ but the visual comparison can show how robust} my proposed methods on real videos. 

{{ 
% \delete{The real sequence example shown in} 
Fig.~\ref{ex:Navajo} \replace{shows the superresolution results for }{is a spatial upscaling example using a part of} a real Navajo Sculpture video sequence ($70 \times 80$ pixels, $30$ frames). \replace{One can see some ``blocking'' artifacts in the original sequence due to its low resolution as}{As seen in the input frames} shown in Fig.~\ref{ex:Navajo}\subref{fig:Low}.
% \delete{, the video has real compression artifacts (i.e., blocking)}
In Fig.~\ref{ex:Navajo}\subref{fig:SCoBeP}, I illustrate the ability of my proposed methods \replace{in removing these artifacts and resulting in}{to remove blocks effectively and present} a clear output. I also show the \replace{superresolution}{upscaled} results by the Lanczos interpolation \cite{wolberg1990digital}, Farsui \textit{et al.} method \cite{farsiu2004fast}, 3-D ISKR method \cite{takeda2009super}, and  \ths{the} TV prior method \cite{babacan2011variational}
%  in Fig.~\ref{ex:Navajo}\subref{fig:Lanczos-large}-\subref{fig:SRUsingTV-large}
% the Lanczos interpolation \cite{wolberg1990digital} and Farsui \textit{et al.} method \cite{farsiu2004fast} 
with \replace{three time magnification per each dimension}{a resolution ratio of $1:3$} (i.e., \replace{an}{the} output resolution \replace{of}{is} $210 \times 240$ pixels) in Fig.~\ref{ex:Navajo}\subref{fig:Lanczos}--\subref{fig:SRUsingTV}, respectively.
As shown in Fig.~\ref{ex:Navajo}, the Farsui \textit{et al.} method \cite{farsiu2004fast} and the TV prior method \cite{babacan2011variational} \replace{introduce}{generate} severe block artifacts (\replace{near}{see} the \textit{mouth} and the \textit{eyes} in Figs.~\ref{ex:Navajo}\subref{fig:Farsui} and \ref{ex:Navajo}\subref{fig:SRUsingTV} respectively), and \ths{the} 3-D ISKR method \cite{takeda2009super} \replace{does not}{can not} preserve the \replace{line texture}{straight structure} well 
% \delete{due to the non robustness of its spatial-temporal kernel}
and generates the ghost image \ths{as shown} in Fig.~\ref{ex:Navajo}\subref{fig:ISKR}\replace{. In contrast,}{, unlike} my proposed methods do not suffer from these artifacts.

The computational complexity of SCoBeP-SR can be determined by considering the following two steps: 1) computing the locations and prior probabilities of the candidate pixels, 2) calculating weights via the NLM and SCoBeP {{or only SCoBeP.}}
The complexity associated with the computing the location and weights of the candidate pixels takes $70\%$ of the overall complexity{{ in SCoBeP-NLM.
Since I replace NLM weight with SCoBeP weight in Algorithm \ref{tb:algorithm} and I found the probabilities for the candidate matches in the previous step it can significantly reduce computation complexity and storage requirement.}}
Just to put things into perspective, note that the current implementation requires approximately
$700$ s per frame for the Algorithm \ref{tb:algorithm} using SCoBeP-NLM weights,{{ and $230$ s for Algorithm \ref{tb:algorithm}}} using SCoBeP-SR weights in the most demanding case {{like ``Navajo'' sequence with high-resolution frame size of $250 \times 220$,}} 
with the current pure Matlab implementation on a Pentium 3 GHz (11-GB RAM) machine. { In comparison, ISKR takes approximately $5784$ s per frame.}  }}


% and that method has to employ an image registration step before super resolution, unlike my proposed method that does not require this step.
% Just to put things into perspective, {{ for the Algorithm \ref{tb:algorithm},}} it takes approximately $700$ s per frame for the most demanding case {{ like ``Suzie'' sequence with high-resolution frame size of $210 \times 250$,}} 
% \replace{with the current pure Matlab implementation on a Pentium 3 GHz (11-GB RAM) machine.}{.} }}


%  Even though my approach is tested and designed for video applications, it can be adopted trivially for images also. 

\begin{figure}
  \centering
\subfloat[]{\label{fig:Low}\includegraphics[width=3cm, height = 3cm]{Figs_tables/Navajo_Low}}
\subfloat[]{\includegraphics[width=3cm, height = 3cm]{Figs_tables/Navajo_Low_Zoom}}   
%       \vspace{-10pt}
\ \ \subfloat[]{\label{fig:Lanczos}\includegraphics[width=3cm, height = 3cm]{Figs_tables/Navajo_Lanczos}}
 \subfloat[]{\includegraphics[width=3cm, height = 3cm]{Figs_tables/Navajo_Lanczos_Zoom}} 
      \vspace{-10pt}
      
\subfloat[]{\label{fig:Farsui}\includegraphics[width=3cm, height = 3cm]{Figs_tables/Navajo_Farsui}}
\subfloat[]{\includegraphics[width=3cm, height = 3cm]{Figs_tables/Navajo_Farsui_Zoom}} 
%  \vspace{-10pt} 
\ \ \subfloat[]{\label{fig:ISKR}\includegraphics[width=3cm, height = 3cm]{Figs_tables/ISKR_3D_Navajo}}
\subfloat[]{\includegraphics[width=3cm, height = 3cm]{Figs_tables/Navajo_ISKR_Zoom}}  
      \vspace{-10pt}
      
\subfloat[]{\label{fig:SRUsingTV}\includegraphics[width=3cm, height = 3cm]{Figs_tables/NSRUsingTV}}
\subfloat[]{\includegraphics[width=3cm, height = 3cm]{Figs_tables/NSRUsingTV_Zoom}}  
% \vspace{-10pt}
\ \ \subfloat[]{\label{fig:SCoBeP}\includegraphics[width=3cm, height = 3cm]{Figs_tables/Navajo_Z0}}
\subfloat[]{\includegraphics[width=3cm, height = 3cm]{Figs_tables/Navajo_Z0_Zoom}}  
      \vspace{-10pt}
      
\subfloat[]{\label{fig:SCoBeP}\includegraphics[width=3cm, height = 3cm]{Figs_tables/SCoBeP-SR_Navajo_frame-1}}
\subfloat[]{\includegraphics[width=3cm, height = 3cm]{Figs_tables/SCoBeP-SR_Navajo_frame-2}}  
  \caption{ {Multi-frame super resolution for real frames: ``Navajo'' sequence. (a,b) LR frame; (c,d) Lanczos interpolation; (e,f) Farsui \textit{et al.} \cite{farsiu2004fast} method; (g,h) 3-D ISKR \cite{takeda2009super}; (i,j) super resolution Using TV prior \cite{babacan2011variational}; (k,l) SCoBeP-NLM; (m,n) SCoBeP-SR.}}
  \label{ex:Navajo}
%   \vspace{-20pt}
  \end{figure} 

\chapter{DENOISING METHOD USING BLOCK MATCHING FILTERING AND LOW-RANK MATRIX COMPLETION}\label{MatrixVideo}

\section{Introduction}
{{The recovery of an unknown low-rank or approximately low-rank matrix from very limited information is a recent fast growing interest.
%  Plenty of works have emerged lately based on this problem such as computer vision \cite{tomasi1992shape} and machine learning \cite{graepel2002kernel,abernethy2006low,amit2007uncovering}.
}}
% \scc{too vague}{On the heels of compressed sensing, a new technique for acquiring information from a highly incomplete matrix has been recently emerged.} 
%  \scc{order not right, you explained matrix completion in the next paragraph}{In the simplest case of matrix completion, the problem is to recover an incomplete matrix from a small sample of its entries. The recovery can be for a matrix with incomplete data or even corrupted information.}
Consider a large matrix with only a small portion of known entry, an interesting problem is to fill the missing entry assuming the matrix has low-rank. 
% Matrix completion and, generally Low-rank matrix recovery is only as important, and because of its described problem will become increasingly studied in following years. 
The problem, which is referred to as matrix completion, or more precisely low-rank matrix completion, has gained increasing interests in research communities in recent years. 
So far, this problem has been studied in many applications such as collaborative filtering \cite{srebro2004learning}, system identification \cite{candes2009matrix}{, computer vision \cite{tomasi1992shape}, machine learning \cite{graepel2002kernel,abernethy2006low,amit2007uncovering}}}, global positioning \cite{singer2008remark} and remote sensing \cite{schmidt1986multiple}. 
% This problem has several interesting applications including the so-called collaborative filtering problem \cite{srebro2004learning}. 
An example is the famous Netflix challenge where a huge matrix is used to represent the rating of a movie given by a user. Of course, a typical user will only rate very few movie titles. Therefore, an algorithm will be needed to complete the matrix to predict the ratings of all movies among all users. 




It has been shown theoretically that under certain assumptions the matrix can be recovered with very high accuracy \cite{candes2009exact,candes2009power,keshavan2010matrix}. Their approaches convert the rank minimization problem into a nuclear norm minimization problem instead and thus can be solved using semidefinite program (SDP). However, 
% \scc{since I mentioned this, the readers will expect us to include complexity analysis of my method}
{the complexity grows rather rapidly with the size of the matrix $n$ ($\sim n^3$).} 
Candes and Recht \cite{candes2009exact} showed that one can perfectly recover most low-rank matrices from what appears to be an in complete set of entries, and they proved in some condition, most $n \times n$ matrices of rank $r$ can be perfectly recovered by solving a simple convex optimization program. Also, the authors claimed that their method is accurate even when the few observed entries are corrupted by a small amount of noise. In another work, the problem of recovering low-rank and sparse matrices using a greedy algorithm was discussed for large matrix sizes \cite{waters2011sparcs}.
Several efficient algorithms have been proposed including Singular Value Thresholding (SVT) \cite{SVT:08}, Atomic Decomposition for Minimum Rank Approximation (ADMiRA) \cite{ADMiRA:09}, Fixed Point Continuation with Approximate (FPCA) \cite{FPCA:09}, Accelerated Proximal Gradient (APG) \cite{APGL:09}, Subspace Evolution and Transfer (SET) \cite{dai2009set}, Singular Value Projection (SVP) \cite{SVP:09}, OptSpace \cite{keshavan2010matrix}, and LMaFit \cite{LMaFit:10}, where OptSpace and SET are based on Grassmann manifold optimization, SVT and SVP uses iterative hard thresholding (IHT) to facilitate matrix shrinkage, FPCA utilizes Bregman iterative algorithm and Monte Carlo approximate SVD, and LMaFit adopts successive over-relaxation (SOR). 

In this chapter, I use a decomposition method \cite{ma2014decomposition} to allow very efficient divide-and-conquer approach when known entries are relatively very few. 
% \scc{unclear, probably needs to find a new name for trimming.}
{A simple ``trimming'' method ed in that work will recover the decomposed ``cluster'' matrix.} % is recovered through a simple ``trimming'' method. 
However, the decomposition method can also be combined with any other existing matrix completion techniques to yield further gain.
One advantage of the decomposition approach \cite{ma2014decomposition} is that unlike most existing approaches it does not utilize SVD but only relies on basic vector operations. Therefore, the approach is immediately applicable to matrices of any field (including finite field matrices). This opens up opportunities for new applications.
% To compare with other methods, I apply to video denoising. The proposed method significantly outperforms the-state-of-the-art denoising techniques such as VBM3D. I also compare it to other denoising techniques using matrix completion. My method results in comparable performance with significantly lower computation complexity.
 


% The rest of the chapter is organized as follows. In the next section, I will introduce the concept of my matrix completion method and the inference algorithm. I further apply my proposed matrix completion to video denoising and will show my simulation results in Section \ref{nafiss:videodenoising}, followed by a brief conclusion in Section \ref{nafiss:conclusion}.




% \section{Proposed Matrix Completion Method} \label{rick:ProposedDMC}
% 
% This section describes \ths{the rationale and} the implementation details of my proposed matrix completion method.
% I will \replace{introduce}{fix my notation, describe} the problem precisely in Section \ref{MinRank}, and present several properties to be used in the later sections. Sections \ref{sect:diag} and \ref{sect:sdiag} will describe the decomposition procedures and present my main results. Section \ref{sect:trimming} will describe the 
% % \scc{need explanation}
% {trimming process} {\color{myblue}{to recover the decomposed ``cluster'' matrix}}.
% 
% 
% \subsection{Minimum Rank, Junk Rows and Columns, Equivalence}
% \label{MinRank}
% 
% Let us start with a few words on notation.
% When things are clear, lines of partition in matrices may be omitted. {\color{black}{The $?$ sign may represent an unknown entry, a row or a column of unknown entry, or a matrix of unknown entry. Similarly, this rule applies to the $0$ sign as well.}} {\color{black}To increase readability, I use bold font for vectors and norman font for other scalars and matrices.}
% 
% \subsubsection{Minimum Rank of Incomplete Matrix}
% 
% Given a finite size matrix $M$ over field $\mathbb{F}$ to be completed, let
% \begin{equation}
%  S(M)=\{\bar M | \bar M \mbox{ is a completion of } M\}. %         (1)
% \label{rick:1}
% \end{equation}
% % $ S(M)=\{\bar M | \bar M \mbox{ is a completion of } M\}$.          (1)
% 
% If $ M$ is already completed, then $ S(M)=\{M\}$.
% I define
% \begin{equation}
% mr(M) \triangleq \min_{\bar M \in S(M)} \mbox{rank} \bar M. %              (2)
% \label{rick:2}
% \end{equation}
% % $ mr(M)=\min_{\bar M \in S(M)} \mbox{rank} \bar M$.              (2)
% 
% Such minimum exists 
% %even for matrices of infinite size
%  because $ \mbox{rank} (S(M)) \subset \mathbb{N}$ and hence $ \exists \bar M \in S(M)$ such that 
% \begin{equation}
% \mbox{rank} \bar M= mr M.
% \label{rick:new1.3}
% \end{equation}
% If $M= \begin{pmatrix} A & B \\ C & D \end{pmatrix}$, then 
% \begin{equation}
%  \exists \bar A \in S(A) \mbox{ such that } mr(M) = mr 
% \begin{pmatrix} \bar A & B \\ C & D \end{pmatrix}, 
% \label{rick:new1.4}
% \end{equation}
% as I can always find $\bar A$ from $\bar M$ in \eqref{rick:new1.3}. I list in the following other obvious properties of $mr(M)$ that will be used later on:
% % The following properties are self-evident and I list them here without proof.
% %Here I list some properties that will be quoted:
% % \begin{property}
% %  fsf
% \begin{align}
%  &mr (M) \le \mbox{rank} \bar M,  \qquad \forall \bar M\in S(M),       
% \label{rick:3} \\ % (3) 
% & mr(M) \le mr(P) \mbox{ if  $P$ is any partial completion of  $M$, } 
% \label{rick:4} \\ %(4)
%  &mr([A | B]) \le mr A + mr B,    
% \label{rick:5}  \\ %                               (5)
% & mr M^t = mr M,  
% \label{rick:6} \\ %                                            (6)
% %  &mr \left( \left(\begin{matrix} A & B \\ C & D \end{matrix}\right)\right) \ge mr(A),
%  &mr \left(\begin{matrix} A & B \\ C & D \end{matrix}\right) \ge mr(A),
% \label{rick:7} \\ \nonumber
% &mr M = mr N \mbox{ if $ N$ can be obtained from $ M$ } 
%  \\ %      (8)
%  &\mbox{ through interchanging of columns/rows.} 
% \label{rick:8}    %  (8)
% \end{align}
% % $ mr (M) \le \mbox{rank} \bar M$, $ \forall \bar M\in S(M) $       (3)
% % $ mr(M) \le mr(P)$ if $ P$ is any partial completion of $ M$ (4)
% % $ mr([A B]) \le mr A + mr B$                                   (5)
% % $ mr M^t = mr M$                                              (6)
% % \end{property}
% 
% 
% 
% 
% % $ mr M = mr N$ if $ N$ can be obtained from $ M$ through
% % exchanges of columns and exchanges of rows.      (8)
% 
% \subsubsection{Junk Row and Junk Column}
% \begin{definition}
% A row (column) contains entirely either zero or unknown  will be referred as a junk row (column).
% \label{def:9}
% \end{definition}
% % If a row(column) contains entirely either zero or unknown, then
% % I say it is a junk row(column).                     (9)
% Certainly, I have 
% % I have the following property.
% % \begin{prop}
% \begin{equation}
% \label{rick:10}
%  mr(\mathbf{J})=0 \mbox { if }  \mathbf{J} \mbox{ is a junk row (column), }                   %(10)
%  \end{equation}
% since I can always complete $\mathbf{J}$ entirely by zero entries.
% 
% % \end{prop}
% 
% % Thm 1
% \begin{thm}
% \label{thm:1}
% Let $ M=[\mathbf{J}| N]$ where $\mathbf{J}$ is a junk column, then
% $ mr M= mr N$.
% \end{thm}
% 
% \begin{proof}
% By \eqref{rick:5}, % and Property \ref{rick:10}, % (5)
% I have
% $ mr M \le mr \mathbf{J} + mr N = mr N$.
% % (by (10)).
% On the other hand $ mr M \ge mr N$ by \eqref{rick:7}. %(7). 
% Hence
% $ mr M=mr N$.
% \end{proof}
% % 
% % proof:
% % end of proof.
% 
% Thanks to \eqref{rick:6}, I have the following corollary:
% % Corollary 1
% \begin{cor}
% \label{cor:1}
% $ mr \left( \left[ \begin{matrix} \mathbf{J} \\ N \end{matrix} \right] \right) = mr N$ if $ \mathbf{J}$ is a junk row.
% \end{cor}
% \ths{In essence, junk rows and columns are redundant as their existence does not increase the minimum rank of an incomplete matrix.}
% 
% % $ mr \left( \left[ \begin{matrix} J \\ N \end{matrix} \right] \right) = mr N$ if $ J$ is a junk row.
% 
% \subsubsection{Equivalence}
% I say $ M$ is equivalent to $ N$ and write $ M \sim N$ iff $ N$ can be
% obtained from $ M$ through row interchanging, column interchanging, 
% and junk rows and columns deletion and augmentation.
% %By Lemma 1 {\color{myred}(where is lemma one?)} 
% By Theorem \ref{thm:1} 
% %  Corollary \ref{cor:1}
% and \eqref{rick:8}, I have
% \begin{equation}
%  M \sim N \Rightarrow mr M = mr N.                                    
% \label{rick:11}
% %(11) 
% \end{equation}
% 
% 
% \subsection{Unknown-diagonalization}
% \label{sect:diag}
% Define 
% \begin{equation}
% \mbox{u-diag}(B_1,B_2,\cdots,B_n)\triangleq 
% % \left[
% \begin{pmatrix} 
% B_1 & \mathbf{ ?} &\cdots & \mathbf{ ?}\\
% \boldsymbol{?} &B_2&\cdots&\ \mathbf{ ?}\\
% \vdots&&\ddots\\
% \mathbf{ ?}&\mathbf{ ?}&\cdots&B_n
% \end{pmatrix}
% % \right]
% . \label{rick:12}
% \end{equation}
% 
% %                    (12)
% % I say $M$ 
% % where $ U_{i,j}$ are matrices consist of unknown entries.
% I say $M$ is u-diagonalizable\footnote{\color{myred}I use $u$ in u-diagonalizable as an abbreviation for {\em unknown}.}  iff  $M \sim \mbox{u-diag} (A,B)$,
% and both $ A$ and $B$ contain at least one nonzero known entry. 
% \ths{I want to know if an incomplete matrix is u-diagonalizable as one can complete a u-diagonal matrix efficiently with the following theorem.}
% 
% % Thm 2
% \begin{thm}
% Let $ M\sim \mbox{u-diag}(B_1,\cdots,B_n)$, then
% $ mr M= max_{1\le i\le n} mr (B_i)$. 
% \label{thm:2}
% \end{thm}
% 
% \begin{proof}
% By \eqref{rick:11} and induction, all I need to show is when
% $ M=\mbox{u-diag}(A,B)$.
% Let $ mr A=a$ and $ mr B=b$, by \eqref{rick:7} I have
% \begin{equation}
%  mr M \ge max (a, b) \label{rick:13} % (by 7)                      (13)
% \end{equation}
% 
% Let $ \bar A$, $ \bar B$ be completions of $ A$ and $ B$, respectively
% such that
% $ \mbox{rank} \bar A= a$ and $ \mbox{rank} \bar B=b$ (c.f. \eqref{rick:new1.3}), then by \eqref{rick:4},
% \begin{equation}
% mr M\le mr \left( \mbox{u-diag}(\bar A, \bar B) \right) % (by 4).                     
% \label{rick:14} %(14)
% \end{equation}
% 
% % $ mr M\le \mbox{u-diag}(\bar A, \bar B)$ (by 4).                     (14)
% Combining \eqref{rick:13} and \eqref{rick:14}, I conclude that
% \begin{equation}
%  max(a,b) \le mr M \le mr \left( \mbox{u-diag}(\bar A, \bar B) \right).
% \label{rick:15} 
% %             (15)
% \end{equation}
% 
% By \eqref{rick:8}, I can simply assume the first $ a$ columns
% of $ \bar A$ form a basis of $ Col \bar A$ ; and the first $ b$ columns
% of $ \bar B$ form a basis of $ Col \bar B$.
% % (I type A' as \bar A; B' as \bar B for simplicity.)
% Without loss of generality, let us assume $ a\ge b$. I complete the
% ﻿﻿matrix $ \mbox{u-diag}(\bar A,\bar B)$ by filling up the columns: 
% % {\color{samred} (Only bold the $A$ but not the index $i$. That is $\bar {\mathbf A}_i$.)}
% \begin{align} 
% \left[ \begin{matrix}
%        \bar {\mathbf A}_i \\ \mathbf{ ?}
%        \end{matrix}
% \right] & \Rightarrow
% \left[ \begin{matrix}
%         \bar {\mathbf A}_i\\ \bar {\mathbf B}_i
%        \end{matrix}
% \right], %& \mbox{for $i \le b$}, 
% \nonumber
% \\
% \left[ \begin{matrix}
%         \mathbf{ ?} \\ \bar {\mathbf B}_i 
%        \end{matrix}
% \right] & \Rightarrow
% \left[ \begin{matrix}
%         \bar {\mathbf A}_i\\ \bar {\mathbf B}_i
%        \end{matrix}
% \right], & \mbox{for $1 \le i \le b$},
% \label{rick:new2.5}
%  \\
% \left[ \begin{matrix}
%         \bar {\mathbf A}_i \\ \mathbf{ ?}
%        \end{matrix}
% \right] & \Rightarrow
% \left[ \begin{matrix}
%        \bar {\mathbf A}_i\\ \bar 0
%        \end{matrix}
% \right], & \mbox{for $b+1 \le i \le a$}.
% \label{rick:new2.6}
% \end{align}
% For $i > a$, I make use of the fact that $\bar {\mathbf A}_i$ is a linear combination of 
% $\bar {\mathbf A}_k | k \le a \}$. 
% {\color{myred} Let $ \bar {\mathbf A}_i=\sum_{k=1}^a a_{i,k} \bar {\mathbf A}_k$}. I fill
% \begin{align}
% \left[ \begin{matrix}
%         \bar {\mathbf A}_i \\ \mathbf{ ?}
%        \end{matrix}
% \right] & \Rightarrow
% \left[ \begin{matrix}
%         \bar {\mathbf A}_i\\ \sum_{k=1}^a a_{i,k}\bar {\mathbf B}_k
%        \end{matrix}
% \right], & \mbox{for $i > a$},
% \label{rick:new2.7}
% \end{align}
% \ths{where $\bar {\mathbf B}_k= 0$, $b < k \le a$}.
% Similarly,
% \begin{align}
% \left[ \begin{matrix}
%         \mathbf{ ?} \\ \bar {\mathbf B}_i
%        \end{matrix}
% \right] & \Rightarrow
% \left[ \begin{matrix}
%        \sum_{k=1}^b b_{i,k}\bar {\mathbf A}_k \\  \bar {\mathbf B }_i
%        \end{matrix}
% \right], & \mbox{for $i > b$}, 
% \label{rick:new2.8} 
% \end{align}
% where {\color{myred} $\bar {\mathbf B}_i=\sum_{k=1}^b b_{i,k}\bar {\mathbf B}_k$}.
% 
% % where %for $i > a$, $k \le a$, $j > b$, and $l \le b$,
% % $a_{i,k}$ and $b_{j,l}$ are coefficients of $\bar A_i$ represented by
% % $Col \bar A$ and $\bar B_j$ represented by $Col \bar B$, respectively. 
% % That is, $ \bar A_i = \sum_{k=1}^a a_{i,k}\bar A_k$ and
% %  $ \bar B_j = \sum_{l=1}^b b_{j,l}\bar B_l$.
% 
% % I splice $ \bar A_i$ by $ \bar B_i$; $ \bar B_i$ by $ \bar A_i$ for $ 1 \le i \le b$; $ \bar A_i$ by $ 0$ for $ b+1\le i\le a$. For $ i>a$, I make use of the fact that $ \bar A_i$ is a linear combination of $ \{\bar A_k | k\le a\}$. I splice $ \bar A_i = \sum_{k=1}^a a_{i,k}\bar A_k$ by $ \sum_{k=1}^a a_{i,k}\bar B_k$ for $ i>a$. Similarly, I splice 
% % \begin{equation}
% %  \bar B_i=\sum_{k=1}^b b_{i,k}\bar B_k \mbox{ by }
% % \sum_{k=1}^b b_{i,k} \bar A_k \mbox{ for } i>b.   
% % \label{rick:16}
% % \end{equation}
% 
% % $ \sum_{k=1}^b b_{i,k} \bar A_k$ for $ i>b$.   (16)
% 
% Now I have a completed $ \mbox{u-diag}(\bar A,\bar B)$ and the first $ a$ of its columns
% $ \left[\begin{matrix}\bar {\mathbf A}_1\\\bar {\mathbf B}_1 \end{matrix}\right]$, $ \left[\begin{matrix}\bar {\mathbf A}_2\\\bar {\mathbf B}_2\end{matrix}\right]$,$ \cdots$,$ \left[\begin{matrix}\bar {\mathbf A}_b\\\bar {\mathbf B}_b\end{matrix}\right]$,$ \left[\begin{matrix}\bar {\mathbf A}_{b+1}\\{\bf 0}\end{matrix}\right]$,$ \cdots$,$ \left[\begin{matrix}\bar {\mathbf A}_a\\{\bf 0}\end{matrix}\right]$ form a basis for its column space. Hence it has rank $a$. By \eqref{rick:3}, $ mr \left( \mbox{u-diag}(\bar A,\bar B) \right)\le a$ and hence by \eqref{rick:15} and $ max(a,b)=a$, I get $ mr M=a=mr \left( \mbox{u-diag} (A,B) \right)$ as wanted.
% \end{proof}
% 
% % Remark
% \begin{rem}
% \label{rem:2.1}
% Suppose $A$ has been completed by $\bar A$ and $a= \mbox{rank}(\bar A)$. Then if the number of column of $B=n \le a$, then I can complete $B$ arbitrarily \ths{without increasing the rank of the output} and \replace{fill the unknowns in $B$ with \eqref{rick:new2.5} alone as if $b=n$.}{ do the completion in 
% \eqref{rick:new2.5}-\eqref{rick:new2.8} 
% as if $b=n$.} More generally, given $M=\mbox{u-diag}(\bar A,B)$ with $\bar A$ is completed. Then the 
% completing 
% process of $B$ can be stopped once I know that the final $\mbox{rank} B$ will be no greater than $\mbox{rank} \bar A$ no matter how I \replace{fill in the remaining unknowns in}{do the remaining completion on} $B$. For example, if $\mbox{s}(B) \le \mbox{rank} \bar A$, where
% \begin{align}
%  \mbox{s}(B) \triangleq  \min (\mbox{number of column of $B$}, \mbox{number of row of $B$}), 
% \label{rick:new2.9}
% \end{align}
% % 
% % $\min (\mbox{number of column of $B$}, \mbox{number of row of $B$}) \le  \mbox{rank} \bar A$, 
% then I can complete $B$ arbitrarily to start with.
% \end{rem}
% 
% \ths{I will call the submatrices $B_1, B_2, \cdots, B_n$ in Theorem \ref{thm:2} as clusters, where a cluster is a matrix that cannot be further u-diagonalized. I will defer to Section \ref{sect:trimming} for discussion of how a cluster can be filled. In the following, I will first present a more general decomposition that can be applied to matrices that are not u-diagonalizable. 
% } 
% 
% 
% 
% \subsection{Sub Unknown-diagonalization}
% \label{sect:sdiag}
% 
% \begin{definition}
%  A matrix $C$, not u-diagonalizable, becomes u-diagonalizable after deleting a row or a column is called sub u-diagonalizable. The row (column) is called conjoined row (column).  
% \label{def:2.2}
% \end{definition}
% 
% Before I describe this main theorem in this section, I need to introduce the following lemma. 
% 
% 
% \begin{lem}
%  $mr [\mathbf{v} | M]=mr M$ if $\forall \bar M \in S(M)$,
% $Col (\bar M) \cap S(\mathbf{v}) \neq \mathbb{\phi}$,.
% \label{lem:4.1}
% \end{lem}
% \begin{proof}
%  By (1.9) I already have
% $mr[\mathbf{v}| M] \ge mr M$.                   
% Let $\bar M \in S(M)$ such that $\mbox{rank} \bar M=mr M$ (c.f. \eqref{rick:2}).
% Then pick a $\bar {\mathbf v} \in S(\mathbf{v}) \cap Col(\bar M)$. From \eqref{rick:3}, I get
% $mr [\mathbf{v} | M] \le \mbox{rank} [\bar {\mathbf v} | \bar M]=\mbox{rank} \bar M=mr M$.       
% \end{proof}
% 
% 
% % {\color{red} ADD THE PART HERE}
% % {\color{samred} (Don't bold question marks below.)}
% {\color{myblue}{
% 
% \begin{thm}
% \label{thm:5}
% Let $M= 
% % \begin{pmatrix}
% % v_1 & B1& &       & \mathbf{ ?} \\
% % v_2  & &     B2  &\\
% % \vdots & & &           \ddots& \\
% % v_n &     \mathbf{ ?} &&     &     Bn 
% % \end{pmatrix}
% % $
% % $
% \begin{pmatrix} 
% \mathbf{v}_1 &B_1 & \mbox{ ?} &\cdots & \mbox{ ?}\\
% \mathbf{v}_2 &\mbox{ ?} &B_2&\cdots&\mbox{ ?}\\
% \vdots&\vdots&&\ddots\\
% \mathbf{v}_n &\mbox{ ?}&\mbox{ ?}&\cdots&B_n
% \end{pmatrix},$
% where $B_i$ are matrices, $\mathbf{v}_i$ are vectors that
% $\left [ 
% \begin{matrix}
% \mathbf{v}_1 \\
% \mathbf{v}_2 \\
% \vdots \\
% \mathbf{v}_n  
%  \end{matrix}
% \right ]$ is not a junk column{\color{black}{\footnote{Note that
% $
% \left [ 
% \begin{matrix}
%   \mathbf{v}_1 \\ \mathbf{v}_2 \\ \vdots \\ \mathbf{v}_n
%  \end{matrix}
% \right ]
% $
%  is a conjoined column and $M$ becomes 
% u-diagonalizable without it. 
% }}}, then
% $mr M= \max_i  mr  
% % \left[\begin{matrix} v_i | B_i \\ 1 | \ ? \end{matrix}\right]
% % \begin{blockarray}{( c| c)} v_i & B_i \\ 1 & ? \end{blockarray}
% \left(
% \begin{array}{c|c}
% \mathbf{v}_i & B_i \\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)
% $.
% \end{thm}
% 
% 
% 
% \begin{proof}
% I will show the case when $n=2$; cases of higher $n$ are easy to be generalized. Let
% $M=\begin{pmatrix} \mathbf{u} & A & \mbox{ ?} \\
% \mathbf{v} &\mbox{ ?} & B\end{pmatrix}$ with 
% $\left [ 
% \begin{matrix}
%   \mathbf{u} \\\mathbf{v} 
%  \end{matrix}
% \right ]
% $ is not a junk column. If $\mathbf{u}$ is not a junk column, then $\mathbf{u}$ contains a nonzero element. By Lemma \ref{lem:4.1} (row version), 
% % {\color{samred}(? below needs to be bold, they are vectors)}
% {\color{black}{
% \begin {align}
% %   mr M =
% %  \left[
% % \begin{matrix} u | A \\ 1 | \ ? \end{matrix}
% % \begin{blockarray}{( c| c)} u & A \\ 1 & ? \end{blockarray}
%  mr \left(
% \begin{array}{c|c}
% \mathbf{u} & A \\ 
% 1 & \boldsymbol{?}
% \end{array}
% \right)
% % \right]
%  = mr [\mathbf{u} | A] \leqslant mr M ,\ \mbox{(c.f. \eqref{rick:7})}.
% \end {align} }}
% If $\mathbf{u}$ is a junk column, then $\mathbf{v}$ contains a nonzero element $\lambda$. 
% Obviously 
% \begin {align}
%  mr  
% % \left[\begin{matrix} u | A \\ 1 | \ ? \end{matrix}\right] 
% \left(
% \begin{array}{c|c}
% \mathbf{u} & A \\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)
% = mr 
% %  \left[\begin{matrix} u | A \\ \lambda | \ ? \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \mathbf{u} & A \\
%  \lambda & \boldsymbol{?} 
% \end{array}
% \right)
%  \leqslant mr M, \ \mbox{(c.f. \eqref{rick:7}, \eqref{rick:8})}.        
% \end {align}
% 
% By symmetry, I also have $mr 
% %  \left[\begin{matrix} v | B \\ 1 | \ ? \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \mathbf{v} & B\\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)
%  \leqslant mr M $ and hence I have shown 
% \begin {align}
% mr M \geqslant max ( mr 
% %  \left[\begin{matrix} u | A \\ 1 | \ ? \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \mathbf{u} & A\\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)
% , mr  
% % \left[\begin{matrix} v | B \\ 1 | \ ? \end{matrix}\right] 
% \left(
% \begin{array}{c|c}
% \mathbf{v} & B\\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)
% ).
% \end {align}
% {\color{black}{Next, I will complete the proof by showing that $\exists \bar M \in S(M)$ s.t.
% \begin {align}
% \mbox{rank} \bar M = \mbox{max} ( mr 
% %  \left[\begin{matrix} u | A \\ 1 | \ ? \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \mathbf{u} & A\\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)
% , mr 
% %  \left[\begin{matrix} v | B \\ 1 | \ ? \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \mathbf{v} & B\\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)
% ).
% \label{eqn:star}
% \end {align}}}
% 
% Let $a = mr  
% % \left[\begin{matrix} u | A \\ 1 | \ ? \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \mathbf{u} & A\\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)
% - 1$ and $b = mr  
% % \left[\begin{matrix} v | B \\ 1 | \ ? \end{matrix}\right] 
% \left(
% \begin{array}{c|c}
% \mathbf{v} & B\\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)- 1$. Without loss of generality, I assume $a \geqslant b$.  
% % {\color{samred}(? should be bold, they are vectors. So do $\bar{A}_0$ and so on also... please read the rest of the section carefully. you make me worry if you really understand the material since you don't seem to realize what are vectors and what are not)}
% Let 
% $
% % \left[\begin{matrix} \bar A_0 | \bar A \\ 1\ |\bar X \end{matrix}\right] 
% \left(
% \begin{array}{c|c}
% \bar {\mathbf A}_0 & \bar A\\
%  1 & \bar{\mathbf X }
% \end{array}
% \right)
% \in S \left( 
% % \left[\begin{matrix} u | A \\ 1 | \ ? \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \mathbf{u} & A\\
%  1 & \boldsymbol{?} 
% \end{array}
% \right)
% \right)$  with rank $a + 1$; $
% % \left[\begin{matrix} \bar B_0 | \bar B \\ 1\ |\bar Y \end{matrix}\right] 
% \left(
% \begin{array}{c|c}
% \bar{\mathbf B}_0 & \bar B \\ 
% 1\ &\bar {\mathbf Y }
% \end{array}
% \right)
% \in S \left( 
% % \left[\begin{matrix} v | B \\ 1 | \ ? \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \mathbf{v} & B \\
%  1 & \ \boldsymbol{?} 
% \end{array}
% \right)
% \right)$  with rank $b + 1$.
% 
% By \eqref{rick:8}, I may assume $\left \{ \left[\begin{matrix} \bar{\mathbf A}_0 \\ 1 \end{matrix}\right], \left[\begin{matrix} \bar { \mathbf{A}_1} \\ \bar X_1 \end{matrix}\right], \cdots , \left[\begin{matrix} \bar{\mathbf A}_a \\ \bar X_a \end{matrix}\right] \right \}$ forms a basis for $Col 
% % \left[\begin{matrix} \bar A_0 | \bar A \\ 1 \; \, |\bar a \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \bar {\mathbf A}_0 & \bar A \\
%  1  & \bar {\mathbf X}  
% \end{array}
% \right)
% $;
% $\left \{ \left[\begin{matrix} \bar{\mathbf B}_0 \\ 1 \end{matrix}\right], \left[\begin{matrix} \bar{\mathbf B}_1 \\ \bar Y_1 \end{matrix}\right], \cdots , \left[\begin{matrix} \bar{\mathbf B}_b \\ \bar Y_b \end{matrix}\right] \right \}$ forms a basis for $Col 
% % \left[\begin{matrix} \bar B_0 |\bar B \\ 1 \; \,|\bar b \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \bar{\mathbf B}_0 & \bar B \\
%  1 & \bar{\mathbf Y} 
% \end{array}
% \right)
% $.
% 
% Then I complete the matrix $\begin{pmatrix}
%                               \bar{\mathbf A}_0 & \bar{A} & ? \\ \bar{\mathbf B}_0 & ? & \bar{B}
%                              \end{pmatrix}$ to $\bar{M}$ by \eqref{rick:new2.5}-\eqref{rick:new2.8} but with $k$ started from 0. The first $a+1$ columns of $\bar{M}$ will form a basis for $Col(\bar{M})$ and hence $\mbox{rank} \bar{M} = a+1 $ and I have \eqref{eqn:star}.
% 
% 
% \end{proof}
% 
% 
% 
% 
% }
% 
% }
% 
% 
% 
% 
% % \begin{definition}
% % \label{definition:3.1}
% % Let $u$ be a vector and $A$ be a matrix. I define 
% %  $zero(u, A)$ as $1$ if  $\forall [\bar u | \bar A]\in S([u | A])$
% %  (c.f. \eqref{rick:1})
% % with $\mbox{rank} [\bar u | \bar A]= mr [u | A]$, then $\bar u= {\bf 0}$.
% % Otherwise, I define $zero(u, A)$ as $0$.
% % \end{definition}
% % 
% % % Let $u$ be a vector and $A$ be a matrix.
% % % Define $zero(u, A)$ as $1$ if  $\forall [\bar u | \bar A]\in S([u | A])$
% % % %  (c.f. \eqref{rick:1})
% % % with $\mbox{rank} [\bar u | \bar A]= mr [u | A]$, then $\bar u= {\bf 0}$.
% % % Otherwise, I define $zero(u, A)$ as $0$.
% % 
% % \noindent
% % E.g.
% % $
% 
% 
% \subsubsection{How to decompose sub u-diagonalizable matrix}
% 
% % Definition 3.2
% 
%  \begin{definition}
% \label{definition:3.3}
% Given two vectors $\mathbf{v}$ and $\mathbf{w}$ of same length, I say $\mathbf{v}$ is a {\em donor} for $\mathbf{w}$ $(\mathbf{v} \succeq \mathbf{w})$ iff all of the \replace{known positions of $\mathbf{w}$ are also known positions in $\mathbf{v}$}{unknown positions of $\mathbf{v}$ are also unknown in $\mathbf{w}$}. In order words, after some row interchanging $[\mathbf{w} | \mathbf{v}]
% = 
% \begin{pmatrix}
%  \bar {\mathbf r} & \bar{\mathbf d} \\
%  \boldsymbol{?}  &  \mathbf{n}
% \end{pmatrix}
% $ with $\bar{\mathbf r}$ and $\bar{\mathbf d}$ \replace{contain only known elements}{are completed}. Clearly, $\mathbf{v} \succeq  \mathbf{w}$ and $\mathbf{w} \succeq \mathbf{u}$ imply $\mathbf{v} \succeq \mathbf{u}$. However, if $\mathbf{v} \succeq \mathbf{w}$ and $\mathbf{w} \succeq \mathbf{v}$, I do not have $\mathbf{v}=\mathbf{w}$. Vectors $\mathbf{v}$ and $\mathbf{u}$ are said to be {\em comparable} if either $\mathbf{v} \succeq \mathbf{w}$ or $\mathbf{w} \succeq \mathbf{v}$.    
%  \end{definition}
% 
% 
% \begin{thm}
% \label{thm:3.2}
%  Conjoined row (column) does not have donors among other rows of the sub u-diag matrix.
% \end{thm}
% 
% \begin{proof}
%  Let $C$ be the sub u-diag  matrix, then it must have the following structure (after some row and column interchanging):  
% $
% C = \begin{pmatrix}
%  A & ? \\
%            ? & B  \\
%            \mathbf{u} & \mathbf{v}
% \end{pmatrix}, 
% $
% where $\mathbf{u}$ cannot be entirely unknown, otherwise $C$ is u-diagonalizable. Now, rows in $[? | B]$ cannot be donors of $[\mathbf{u} | \mathbf{v}]$, the conjoined row. Similarly $\mathbf{v}$ cannot be entirely unknown and hence, rows in $[A | ?]$ cannot be donors of $[\mathbf{u}| \mathbf{v}]$ neither.  
% \end{proof}
% 
% Therefore if $C$ is a sub u-diagonalizable, I will not miss the chance of decomposing it if I have tested every row and column that does not have a donor. That is to blackout the suspicious row (column) and then carrying out the decomposition mentioned in Section \ref{sect:diag}. I would like to call the decomposed components as {\em sub-clusters}. For example,
% $
% \left [ \begin{matrix}
%  A \\\mathbf{u}
% \end{matrix}
% \right ]$
% and $
% \left [ 
% \begin{matrix}
%      B \\\mathbf{v}
%     \end{matrix}
% \right ]$
% are sub-clusters of the $C$ in the proposition.  
% 
% Unlike cluster that cannot be further u-diagonalized, sub-clusters can be sub u-diagonalizable. For example
% $C=\begin{pmatrix}
% A & ? & ?  \\     
%  \mathbf{u} & \mathbf{v} & \boldsymbol{?}   \\ 
% ? & B & ?    \\
% \boldsymbol{?} & \mathbf{x} & \mathbf{y}     \\
% ? & ? & D  
%  \end{pmatrix},$
% where both $[\mathbf{u} | \mathbf{v} | \boldsymbol{?}]$ and $[\boldsymbol{?}| \mathbf{x}| \mathbf{y}]$ are conjoined rows. In that case, I may first decompose $C$ into sub-clusters
% $\left [
% \begin{matrix}
%   A \\\mathbf{u}
%  \end{matrix}
% \right ]$
% and 
% $\begin{pmatrix}
%   \mathbf{v} & \boldsymbol{?} \\ B & ? \\\mathbf{x} & \mathbf{y} \\ ? & D
%  \end{pmatrix}$.
%  Then I may further decompose the later into
% $\left [\begin{matrix}
%   \mathbf{v} \\ B \\ \mathbf{x} 
%  \end{matrix}
% \right ]$
% and 
% $\left [
% \begin{matrix}
%   \mathbf{y} \\ D
%  \end{matrix}
% \right ]$, if necessary. 
% 
% \begin{rem}
%  There is a trade-off between the complexity of searching for conjoined rows (columns) and the gain obtained for further decomposition. Even though a conjoined row cannot have any donors from Theorem \ref{thm:3.2}, verifying that for a row can be computationally consuming itself.
% 
% However, as one can easily see that the row with the maximum number of known elements will generally have no donor\footnote{It is not true of course when another row has the same maximum number of known elements and exactly the same locations of known elements.}. Therefore, such rows are usually good candidates of a conjoined row and they are easy to find. Thus, in my implementation, I only check such rows for the simplicity of implementation. However, other variation of conjoined row searching can be easily adopted to the sub u-diagonalization approach. 
% \end{rem}
% 
% 
% 
% 
% \subsection{Trimming}
% 
% \label{sect:trimming}
% 
% % Theorem 4 
% \begin{thm}
% \label{thm:4}
% Let $\mathbf M_{d_i}$ be the $d_i$-th column of $M$ and donor (c.f. def \ref{definition:3.3})
% of a vector $\mathbf{v}$ for $1\le i \le t$, such that after some row interchanging,
% $[\mathbf{v} | \mathbf M_{d_1} \mathbf M_{d_2} \cdots \mathbf M_{d_t}]=
% % \begin{pmatrix}
% % \bar r | \bar D \\
% %                              ?  | N    
% % \end{pmatrix}
% \left(
% \begin{array}{c|c}
% \bar {\mathbf r} & \bar D \\
% \boldsymbol{?}  & N 
% \end{array}
% \right)
% $
%  with $\bar {\mathbf r}$ and $\bar D$ are completed.
% If $\bar{\mathbf r}\in Col (\bar D)$, then $mr[\mathbf{v} | M]= mr M$. 
% \end{thm}
% 
% \begin{proof}
% Thanks to \eqref{rick:8}, I may start with
% $
% [\mathbf{v} |M]=
% % \begin{pmatrix}
% %  \bar r |  \bar D A \\
% % ? | N B
% % \end{pmatrix}
% \left(
% \begin{array}{c|c}
%  \bar {\mathbf r} &  \bar D A \\
% \boldsymbol{?} & N B
% \end{array}
% \right).
% $
% 
% % [v | M]=[\bar r | \bar D A
% % 
% %           ? |  N   B].
% 
% Pick $a_i\in \mathbb F$ such that 
% \begin{equation}
% \bar {\mathbf r}=\sum a_i \bar{\mathbf D}_i. 
% \label{rick:new4.1} %(4.1)
% \end{equation}
% 
% 
% Then $\forall
% \bar M=
% \left [
% \begin{matrix}
%  \bar D \bar A \\
% \bar N \bar B 
% \end{matrix}
% \right ]
% \in S(M)$,
% % [\bar D \bar A
% %        \bar N \bar B]\in S(M)$, 
% I complete $\mathbf{v}$ to 
% \begin{align}
%  \bar {\mathbf v}=
% \left [
% \begin{matrix}
% \bar {\mathbf r} \\
%         \sum a_i\bar{\mathbf N}_i 
% \end{matrix}
% \right ]
% \in S(\mathbf{v})\cap Col (\bar M). 
% \label{rick:new4.2}% (4.2)
% \end{align}
% 
% 
% (Note that $\mbox{rank}[\bar {\mathbf v} | \bar M]= \mbox{rank} \bar M$.)
% Now Lemma \ref{lem:4.1} implies $mr[\mathbf{v} | M]=mr M$.
%  \end{proof}


% \subsubsection{Trimming Process}
% 
% I test column by column to see if I can make use of Theorem \ref{thm:4} to trim away any column $\mathbf{v}$ from a given matrix, {\color{myblue} which can be a cluster or sub-cluster mentioned in the previous section. } I call this process as {\em column trimming}.  
% When I find a column satisfying the condition of Theorem \ref{thm:4}, I will mark down the dependency relation between it and its donor (i.e. 
% \eqref{rick:new4.1}) in order. Then I black it out and go for the next column. 
% 
% Similarly, I have row trimming. 
% {\color{myblue}
% Notice that the trimming process and the sub u-diagonalizable testing can be carried out together, thanks to Theorem \ref{thm:3.2}. The theorem also tells us that trimmed cluster is still a cluster, i.e., not u-diagonalizable. However, it can be a sub-cluster.}
% 
% An uninterrupted (c.f. Remark 
% \ref{rem:2.1}) 
% % and \ref{rem:3.1}) 
% trimming process starts with a column trimming followed by a row trimming, or the other way round. Then I carry out these two kinds of trimming one after the other, until there is no more reduction in the matrix. 
% After the trimmed matrix gets completed, I restore, in reverse order, the blackouts with the completed forms given by \eqref{rick:new4.2}.  
% 
% 
% 
% 
% 
% {\color{myred}
% I haven't made any approximation in my completion procedure. My algorithm 
% can be dovetailed with any other method, without compromising the lowest rank 
% they can find for a given matrix. 
% % But I also have my own approximation method and are going to discuss.
% }




% \begin{algorithm} [t]
% \caption{{
% % Decomposition Approach for Low-rank Matrix Completion- estimate completed version of matrix 
% % \scc{case isn't consistent! some sentences start with upper, some with lower}
% {U-DiagFillMatrix(M)} }}
% \begin{algorithmic} 
% \renewcommand{\algorithmicrequire}{\textbf{Inputs :}}
% \renewcommand{\algorithmicensure}{\textbf{Output :}}
% \REQUIRE { \ths{an} incomplete matrix $M$ }
% \renewcommand{\algorithmicrequire}{\textbf{Complete the matrix M:}}
%  \REQUIRE {\replace{given the}{For} incomplete matrix $M$ do:}
% \begin{enumerate}[--]
% \item 
% % Scan the matrix to find the clusters:
% $c=ScanCluster(M)$
% 
% \item $M_a = ArrangeMatrix(M,c)$
% 
% \end{enumerate}
% \renewcommand{\algorithmicrequire}{\- \- \-  \textbf{-- Cluster trimming and partial filling:}}
% \REQUIRE {\replace{for}{For} each cluster $B_i$ in the arranged matrix $M_a$:}
% \begin{enumerate}[$\bullet$]
% \item \- \- \-  $M_t^i=\ths{Trimming}(B_i)$
% \item \- \- \-  $F_i=FillCluster(B_i,M_t^i)$
% \item \- \- \-  $Update (M_a,F_i)$
% \end{enumerate}
% \begin{enumerate}[--]
% \item $M_f= FillOffDiag(M_a,\begin{Bmatrix} M_t^i \end{Bmatrix}^n_{i=1},c)$
% \item $\hat{M}=RevertMatrix(M_f,c)$
% \end{enumerate}
% \renewcommand{\algorithmicrequire}{\textbf{Output :}}
% \REQUIRE {a complete matrix $\hat M $ }
% \end{algorithmic}
% \label{nafiss:DMC1}
% \end{algorithm}
% 
% 
%  
% 
% 
% 
% \begin{algorithm} [t]
% \caption{
% % Decomposition Approach for Low-rank Matrix Completion (Theorem \ref{thm:5})- estimate completed version of matrix
% SubU-DiagFillMatrix(M) {\color{myblue}{(Theorem \ref{thm:5})}} }
% \begin{algorithmic} 
% \renewcommand{\algorithmicrequire}{\textbf{Inputs :}}
% \renewcommand{\algorithmicensure}{\textbf{Output :}}
% \REQUIRE {an incomplete matrix $M$ }
% 
% 
% \renewcommand{\algorithmicrequire}{\textbf{Initialize}}
% \REQUIRE { \textbf{:}}
% \begin{itemize}
% \item 
% % Scan the matrix to find the clusters:
% $c=ScanCluster(M)$
% % \item 
% % \scc{you won't implement that, right? why calling this if M ends up to be decomposable?}{\delete{$[M_v,c_v,v]=RemoveConjoinedCol(M)$}}
% \item if $c$ shows \ths{that} more than one cluster \ths{are} found from \ths{the} previous step, 
% % \ths{v is the column with minimum number of unknowns, there is no way that v can't be found,}
% % {\delete{or $v$ is empty vector}},
% \ths{output $\hat{M} = U$-$DiagFillMatrix(M)$ (Algorithm \ref{nafiss:DMC1}) and exit.}
% % {go to Algorithm \ref{nafiss:DMC1}, 
% % Otherwise the incomplete matrix $M${\color{myblue}{ can have the following structure (after some row and column interchanging):}}}
% 
% \item 
% % \replace
% {$i = FindConjoinedColIndex(M)$}
% % {$[M_v,c_v,v]=RemoveConjoinedCol(M)$}
% \vspace{10pt}
% 
% 
% 
% \item \ths{$c_v = ScanCluster(M_{\backslash i})$, where $M_{\backslash i}$ is the submatrix of $M$ excluding column $i$.}
% \item \ths{$M_a = ArrangeMatrix(M_{\backslash i},c_v)$}
% \item \ths{$\mathbf{v} = ArrangeColumn(\mathbf M_{i},c_v)$, where $\mathbf M_{i}$ is the $i^{th}$ column of $M$} 
% 
% % \item if $c$ contains only one cluster and $v$ is not empty vector
% % if(length(c) == 1 && length(fmask)>=1 && ~isempty(fmask{1}))
% 
% \end{itemize}
% 
% \vspace{10pt}
% \renewcommand{\algorithmicrequire}{\textbf{Complete the matrix \replace{$M$}{$M_v$}:}}
% \REQUIRE{}
% 
% \renewcommand{\algorithmicrequire}{\- \- \-  \textbf{-- Cluster trimming and partial filling:}}
% \REQUIRE {for each cluster $B_i$ in\delete{the arranged matrix} \replace{$M_a$}{$M_v$} \ths{and the respective $\mathbf{v}_i$ in $\mathbf{v}$ (c.f. \eqref{eqn:vma})}:}
% {\color{myblue} {
% \begin{enumerate}[$\bullet$]
% \item \- \- \- $\hat{B_i} = PadCluster(B_i,\mathbf{v}_i)$
% % \item \- \- \- $M_f=FillNewCluster(M_a,c_v)$
% \item \- \- \- $\hat{F_i}= U$-$DiagFillMatrix(\hat{B_i})$ (Algorithm \ref{nafiss:DMC1})
% % \item \- \- \- 
% % \delete{$F_i = UnPadCluster(\hat{F_i})$}
% % \item \- \- \- 
% % \delete{$Update (M_v,F_i)$}
% \end{enumerate}
% % {\color{myblue} {
% \begin{enumerate}[--]
% \item \ths{$\tilde{M}=BuildSubDiagMatrixByClusters(\{\hat{F}_i\}_{i=1}^n)$}
% \item $\hat{M}_{\backslash i}=RevertMatrix(\replace{\tilde{M}_{\backslash 1}}{M_v},c_v)$ 
% % \ths{reverts the submatrix of $\tilde{M}$ (excluding the first column) and output to the submatrix of $\hat{M}$ (excluding column $i$)}
% \item \ths{$\hat{\mathbf{M}}_i = RevertColumn(\tilde{\mathbf{M}}_{1},c_v)$ 
% % reverts the first column of $\tilde{M}$ and outputs to the $i^{th}$ column of $\hat{M}$
% }
% % \item $M_a = RemoveAddedRow (M_a)$
% % \item apply Algorithm \ref{nafiss:DMC1} on the $M_a$ to fill the parts are still unknown. The result will be returned in $\hat M$. 
% \end{enumerate}
% }}
% \renewcommand{\algorithmicrequire}{\textbf{Output :}}
% \REQUIRE {a complete matrix $\hat M$ }
% \end{algorithmic}
% \label{nafiss:DMC}
% \end{algorithm}
% 
% 
% 
% 
% 
% \subsection{Implementation}
% \replace{Using the results developed in the earlier subsections, I will now present two prototype matrix completion algorithms: one based on unknown diagonalization and the other based on unknown sub-diagonalization. The key steps of the algorithms are summarized in Algorithm \ref{nafiss:DMC1} and Algorithm \ref{nafiss:DMC}, and the detail implementation of each step is presented in the following. }
% {
% To be more precise, I now summarize the two previously described algorithms. First, I describe in Algorithm \ref{nafiss:DMC1} the basic procedure that I were developed in this Section. Second, the specific version that expressed and proofed in Theorem \ref{thm:5} will be explained in Algorithm \ref{nafiss:DMC}.}
% % , is as follows.
% % The main procedure for my proposed decomposition approach for low-rank matrix completion is summarized in Algorithm \ref{nafiss:DMC}.
% 
% \vspace{20pt}
% 
% \textbf{Implementation Details:} \label{nafiss:DMCNotation}
% \begin{itemize}
% % % % % % % % % Algorithm 1
% \item $c=ScanCluster(M)$ \ths{finds the clustering information and outputs the row and column indexes of each potential cluster as a data structure $c$.} {\color{black}{For a target row, I mark all columns that correspond to known entries on that row as columns of the target row's cluster. I then scan through each such column and mark the rows that correspond to known entries on the respective column. The resulting rows will cover all the rows belong to the same cluster of the target row. This step will be repeated to all rows sequentially except those that have been marked to be belonged to some clusters in prior steps. 
% $c$ will then store the total number of clusters and the column and row indices of each cluster.}}
% % For the worst case that no two rows are in a same cluster, I will need to scan through all rows. 
% % \scc{bad, it doesn't say any thing precise, what do the two lists do?!}{\delete{scans matrix $M$ to find the  {\color{myblue} {cluster indexes}} $c$ which stores sequentially two lists of row and column indexes {\color{myblue} {per cluster}}.}}
% 
% % \scc{it doesn't do that!}{\delete{This scanning step estimates the lowest possible rank of each cluster by identifying independent rows and columns (see Theorem \ref{thm:1} and Corollary \ref{cor:1}).}} 
% 
% 
% 
% 
% \item $M_a = ArrangeMatrix(M,c)$ rearranges the matrix $M$ \replace{into}{in} $M_a$ using \delete{the {\color{myblue} {cluster indexes}}} $c$ \ths{by reordering rows and columns}. \replace{The resulting $M_a$ will have}{Hence, using this rearranging function, matrix $M$ becomes in} the format of 
% \begin{equation}
% % \left[\begin{matrix} 
% % B_1 & \mbox{\bf ?} &\cdots & \mbox{\bf ?}\\
% % \mbox{\bf ?} &B_2&\cdots&\mbox{\bf ?}\\
% % \cdots&&\cdots\\
% % \mbox{\bf ?}&\mbox{\bf ?}&\cdots&B_n\end{matrix}\right], 
% \begin{pmatrix} 
% B_1 & \mbox{?} &\cdots & \mbox{ ?}\\
% \mbox{ ?} &B_2&\cdots&\mbox{ ?}\\
% \vdots&&\ddots\\
% \mbox{ ?}&\mbox{ ?}&\cdots&B_n
% \end{pmatrix},
% \end{equation} 
% where \replace{submatrices $B_1, B_2, \cdots, B_n$ are clusters.}{matrix $B_i$ is a cluster. In other words, the input matrix $M$ will be partitioned into clusters $B_1$, $B_2$, $\cdots $, $B_n$, where $n$ is the number of clusters.}
% 
% % \item             The remaining unknown elements of the clusters are filled by the dependency relationship $c$. 
% 
% 
% \item $M_t^i=Trimming(B_i)$ finds the dependency of each column and row to the others columns and rows. This can be solved efficiently using QR decomposition.  When a column/row can be represented by the other columns/rows, it will be removed from the basis choices in the cluster $B_i$. The data structure $M_t^i$ \replace{stores}{shows} the dependency relationship of {\color{myblue}{columns and rows}} in the cluster $B_i$ (see Theorem \ref{thm:4}). {\color{black}{More precisely, $M_t^i$ will tell which column is independent from the rest (basis column). And how a trimmed column should be represented in terms of the basis columns.}} 
% 
% \item $F_i=FillCluster(B_i,M_t^i)$ fills the unknown elements of the cluster $B_i$ using the dependency relationship $M_t^i$. 
% \ths{Unknowns that lie on a basis choice (i.e., a column vector that cannot be ``trimmed'' in the previous step) will be filled with zeros. Unknowns that lie on a ``trimmed'' column will be filled {\color{black}{according to Equation \eqref{rick:new4.2} of Theorem \ref{thm:4}}} so that the rank of the cluster will not increase.} 
% {\color{black}{In other words, a trimmed column will be constructed as linear combination of basis columns according to $M_t^i$. }}
% % The cluster $B_i$ is tested column by column to see if any column can be trimmed away from the cluster $B_i$. After finding the proper column satisfying the condition of Theorem \ref{thm:4}, the dependency relationship $M_t^i$ between it and its column will be marked. Similarly, the row trimming will be applied afterward. 
% 
% 
% 
% % \scc{the reference was wrong!}
% {\delete{Note that the unknown elements of the cluster $B_i$ should be filled without increasing the rank of the cluster (see Theorem \ref{thm:2}).}}
% 
% \item $Update (M_a,F_i)$ replaces the corresponding submatrix in $M_a$ using filled clusters $F_i$. 
% 
% \item
% %  \scc{I remember that I mentioned about using $L$, but at least you have to check consistency, right? It was $n$ just a paragraph before!}
% {$M_f= FillOffDiag(M_a,\begin{Bmatrix} M_t^i \end{Bmatrix}^n_{i=1},c)$} fills the ''off-diagonal`` elements in the matrix $M_a$ using the {\color{myblue}{dependency relationships}} $\begin{Bmatrix} M_t^i \end{Bmatrix}^n_{i=1}$, the clusters relationship $c$ to ensure the entire matrix has \ths{a rank no larger than the rank of the lowest rank cluster {\color{black}{according to Equations \eqref{rick:new2.5}-\eqref{rick:new2.8} (see Theorem \ref{thm:2}).}}} 
% % \scc{reference was wrong again...}
% % {\delete{the lowest possible rank  (see Theorem \ref{thm:3.2})}.} \delete{Moreover, $n$ is the number of cluster.}
% 
% % % % % % % % % % Algorithm 2
% 
% \item $\hat{M}=RevertMatrix(M_f,c)$ reverts each coefficient in the filled matrix $M_f$ to its original location in the input matrix $M$ using \delete{the {\color{myblue}{cluster indexes}}} $c$.
% 
% 
% \item 
% % \replace
% {$i=FindConjoinedColIndex(M)$}
% % {$[M_v,c_v,v]=RemoveConjoinedCol(M)$} 
% % removes the non junk vector $v$ from the matrix $M$ 
% \replace{finds a potential}{removes the} conjoined column \delete{vector}$\mathbf{v}$ \ths{as the column vector} with the minimum number of unknowns \ths{(c.f. Definition \ref{def:2.2})} and \replace{returns the column index.}{rearrange the rest in {\color{myblue}{u-diagonalizable}} matrix $M_v$ with the format of }
% 
% \delete{where matrix $B_i$ is a cluster (Definition \ref{def:2.2}). Cluster indexes $c_v$ stores sequentially two lists of row and column indexes of $M_v$.}
% 
% 
% 
% %  To remove the non junk vector, first, a mask matrix with the same size as $M$ is created with zero at corresponding zero coefficients in $M$ and $1$ at the remaining coefficients. A sum function then treats the columns of mask matrix as vectors, returning a row vector of the sums of each column. The index of the biggest coefficient in the row vector is the non junk vector $v$ index in $M$, and $M_v$ is the remained matrix after removing the non junk vector $v$ from $M$.
% 
% %  first one zero matrix with the same size as $M$ is created, which filled with one in the corresponding non zero coefficients in $M$. 
% 
% \item \ths{$\mathbf{v}= ArrangeColumn(\mathbf M_{i},c_v)$ reorders the coefficients in $\mathbf M_{i}$, the $i^{th}$ column of $M$, according to $c_v$. The matrix $[\mathbf{v} | M_a]$ should be equivalent to $M$ through column and row interchanging, where $M_a = ArrangeMatrix(M_{\backslash i}, c_v)$ and $M_{\backslash i}$ is the submatrix of $M$ excluding $\mathbf M_{i}$. Moreover, I should have $[\mathbf{v}|M_a]$ with the structure
% \begin{equation}[\mathbf{v}|M_a] =
% \begin{pmatrix} 
% \mathbf{v}_1 &B_1 & \mbox{ ?} &\cdots & \mbox{ ?}\\
% \mathbf{v}_2 &\mbox{ ?} &B_2&\cdots&\mbox{ ?}\\
% \vdots&\vdots&&\ddots\\
% \mathbf{v}_n &\mbox{ ?}&\mbox{ ?}&\cdots&B_n
% \end{pmatrix}.
% \label{eqn:vma}
% \end{equation}}
% \item $\hat{B_i} = PadCluster(B_i,\mathbf{v}_i)$ vertically concatenates the column $\mathbf{v}_i$ to the cluster $B_i$ and then adds to the end a row with all unknowns except the first coefficient being one, i,e., 
% % vertically concatenates the column $v_i$ to the cluster $B_i$ and adds a unknown row in the end, with $1$ in the first coefficient, e.g.
%  $ \hat{B_i} = 
% % \left[\begin{matrix} v_i | B_i \\ 1 \; \!  | \ 0 \end{matrix}\right]
% \left(
% \begin{array}{c|c}
% \mathbf{v}_i & B_i \\
%  1 & \boldsymbol{?}
% \end{array}
% \right).
% $
% 
% % \item $M_f=FillNewCluster(M_a,c_v)$ runs Algorithm \ref{nafiss:DMC1} to fill output matrix $M_f$.
% 
% % \item 
% 
% \delete{$F_i = UnPadCluster(\hat{F_i})$ remove the added rows from the matrix $\hat{F_i}$.}
% 
% \item \ths{$\tilde M = BuildSubDiagMatrixByClusters(\{\hat{F}_i \}_{i=1}^n)$ constructs a sub unknown-diagonized matrix using clusters $\hat{F}_i$, $i=1,\cdots,n$, {\color{black}{according to the proof of Theorem \ref{thm:5} (See explanation after Equation \eqref{eqn:star})}}. $\tilde M$ should have rank no larger than the rank of the largest rank clusters.
% }
% 
% \item $\hat{M}_{\backslash i}=RevertMatrix(\replace{\tilde{M}_{\backslash 1}}{M_v},c_v)$ \ths{reverts the submatrix of $\tilde{M}$ (excluding the first column) and output to the submatrix of $\hat{M}$ (excluding column $i$).}
% 
% \item \ths{$\hat{\mathbf{M}}_i=RevertColumn(\tilde{\mathbf{M}}_1,c_v)$ reorders the coefficients of the column vector $\tilde{\mathbf{M}}_1$ according to $c_v$. Note that along with $\hat{{M}}_{\backslash i} = RevertMatrix(\tilde{{M}}_{\backslash 1}, c_v)$, $[\hat{\mathbf{M}}_i | \hat{{M}}_{\backslash i}]$ is equivalent to $[\tilde{\mathbf{M}}_1 | \tilde{{M}}_{\backslash 1}]$ through row and column exchanges. } 
% 
% \end{itemize}
% \subsection{\replace{Complexity analysis}{Experimental Results??!!}}
% 
% The computational complexity of low-rank matrix completion can be determined by considering the following three steps: 1) scanning matrix to find the clusters, 2) in each cluster, finding the dependency of each column and row to the other columns and rows, respectively\delete{ and removing a column which can be represented by the other columns from the basis choices in the cluster}, and 3) filling the clusters and ``off-diagonal'' elements in the matrix.
% 
% 
% %  finding candidate points via sparse coding, and 3) applying BP.
% % For analysis the time complexity, I start from the first  step of the SCoBeP. In this step, the heaviest part is the feature extraction. 
% Assume the input matrix has $p$ rows and $q$ columns.
% % Assume the size of the input matrix is $n \times m$, which $n$ and $m$ are the number of rows and columns, respectively.
% \replace{For the worst case, the}{The} required time of scanning matrix to find the clusters will be $O(p q)$ \replace{ since one has to scan through all elements of the matrix.}{, where scanning matrix through the rows or columns has the same time complexity.}
% For finding the dependencies and removing the dependent columns and rows,
% % which can be represented by the other columns/rows from the basis choices, 
% the time depends on {\color{black}{the number of cluster $n$}} and the size of clusters. One can take advantage of QR decomposition and \replace{the complexity will}{complexity can} be about \replace{$O(p'q'^2)$}{$O(pq^2)$} for \ths{the} column trimming \ths{of a cluster with size $p' \times q'$}, and since the cluster sizes are approximately proportional to $\frac{p}{n}$ and $\frac{q}{n}$, therefore the complexity of column trimming is $O\big(\frac{p}{n} (\frac{q}{n})^2 n\big) =  O(\frac{pq^2}{n^2})$. As a result, the time complexity for finding columns and rows dependencies is $O\big(\frac{p^2q + q^2p}{n^2}\big)$. 
% 
% Similar complexity can be argued for filling the clusters. For filling a column that involved a cluster with width $\hat q$, and assuming that {\color{black}{the rank \ths{of the filled matrix} is $r$}}, the first $r$ column can be filled directly and so complexity will be just $O(rp)$. But for the rest of the $(\hat {q}-r)$ columns, it needs to be computed as the weighted sum of the first $r$ columns, and so the complexity will be $O\big((\hat {q}-r)rp\big)$. \ths{Thus, the total complexity for filling $n$ clusters will be $O\big(n(rp+(\hat{q}-r)rp)\big)\approx O\big(n(rp+(q/n-r)rp)\big)= O\big(rp(n+q-rn)\big)=O(rpq)$}  \replace{since one}{One} may approximate $\hat {q}$ as $\frac{q}{n}$ \ths{and $n \le q$}. 
% % Maybe I should just leave the rank $r$ there as a parameter. 
% % Since I have to repeat the process of filling unknown elements for all column/row of the clusters, 
% \delete{Moreover, the time complexity in the worst case is $O(rpq)$.}
% % and in the typical case, is $O\big(\frac{rpq}{n}\big)$. 
% 
% Consequently, the total time complexity of \replace{Algorithm \ref{nafiss:DMC1} for the}{my proposed approach in the worst case will be $O\big(p^2q + q^2p + rpq\big)$, and in the} typical case will be $O\big(pq + \frac{p^2q + q^2p}{n^2}+ \replace{rpq}{\frac{rpq}{n}}\big)$.
% \ths{For Algorithm \ref{nafiss:DMC}, excluding the step of $FindConjoinedColIndex(M)$ (of complexity $O(pq)$), the rest essentially has the same complexity $O\big(pq + \frac{p^2q + q^2p}{n^2}+ \replace{rpq}{\frac{rpq}{n}}\big)$ as Algorithm \ref{nafiss:DMC1}. However, $n$ will be the number of sub-clusters in this case. 
% % }
% 
% 
% 
% 
% 
%  
% Just to put things into perspective, note that the current implementation  requires approximately $0.1$ s per matrix with size $1500 \times 1500$ for  Algorithm \ref{nafiss:DMC1} and $0.8$ s for Algorithm \ref{nafiss:DMC} in {the most demanding case} when running with pure Matlab on a Pentium 3 GHz (11-GB RAM) machine.
% }
% 
% 
% 
% 
% 
% {\color{black}{
% \section{Simulation result for Matrix Completion}
% In this section, to demonstrate how my proposed method is capable to efficiently recover low-rank matrices, I evaluate my proposed method on a series of matrix completion problems. My experiments can be divided into \textit{Random Matrix Completion Problems} and \textit{Real Matrix Completion Problems}.
% 
% \subsubsection{Experiments on random matrix completion problems}
% In this subsection, I evaluate my proposed method on a few random matrix completion problems. First, I test the sensitivity of my proposed method to the rank estimation using an increasing number of coefficients strategy. In this test, I maintained the size of the matrices consistent, $q=p=1,000$ and varied the number of coefficients $K$ from $100$ to $800$. A summary of computational results is presented in Table \ref{nafiss:smallProblem}. The final matrix rank ``$Rank$'' and average CPU time ``$Time$'' corresponding to this set of $K$ values are reported in this table. This table reveals that my proposed method runs significantly faster than all other solvers to achieve a comparable accuracy. Moreover, the other solvers are essentially dominated by my proposed solver with respect to the obtained final low ranks.  
% 
% 
% 
% \begin{sidewaystable}
%     \centering
% % \begin{table*}[ht]
% % \renewcommand{\arraystretch}{1}
% \caption{ {Comparison of six solvers on small problems with varying rank and number of coefficients}}
% % \label{table_example}
% % \centering
% \begin{tabular}{|c|c||c|c||c|c||c|c||c|c||c|c||c|c|}  
%   \hline
%   \multicolumn{2}{|c||}  {\textbf{ Problem}}  & \multicolumn{2}{c||}  {\textbf{FPCA \cite{FPCA:09}} } & \multicolumn{2}{c||}  {\textbf{APGL \cite{APGL:09}}}  & \multicolumn{2}{c||}  {\textbf{SVT \cite{SVT:08}} } & \multicolumn{2}{c||}  {\textbf{LMaFit1 \cite{LMaFit:10}} }& \multicolumn{2}{c||}  {\textbf{LMaFit2 \cite{LMaFit:10}} }& \multicolumn{2}{c|}  {\textbf{Proposed method} }\\
%   \hline
%   \hline
% %   \multirow{2}{*}
%     {$p$ = $q$} & $K$ & $Rank$ & $Time$ & $Rank$ & $Time$& $Rank$ & $Time$& $Rank$ & $Time$& $Rank$ & $Time$& $Rank$ & $Time$\\  \hline
%     {1000} & 100 &1 & 11.08& 76&3.43 & 1&44.76 &2 &0.36 &3 &0.34 &1 &0.05 \\ \hline
%     {1000} & 150 &1 & 10.65&113 &8.08 & 4&17.64 &2 &0.35 &4 &0.28 &1 &0.08 \\ \hline
%     {1000} & 200 &4 & 11.96&144 &14.43 &10&80.37 & 3&0.40 & 5& 0.33& 1&0.11 \\ \hline
%     {1000} & 250 &4 & 11.16&150 &29.27 &9&98.35 & 4&0.37 & 6& 0.35& 1&0.14 \\ \hline    
%     {1000} & 300 &3 & 10.86&150 &20.00 & 14& 103.20& 4&0.34 &7 &0.35 &1 &0.16 \\ \hline
%     {1000} & 350 &5 & 10.28&150 &100.97 & 16& 117.12& 4&0.28 &7 &0.26 &2 &0.17 \\ \hline
%     {1000} & 400 &5 &10.23 &150 &58.71 &10 &136.00 & 5&0.31& 8&0.39 &2 &0.20 \\ \hline
%     {1000} & 450 &7 &9.97 & 150&88.73 &12 &148.86 & 5&0.34& 10&0.33 &3 &0.21 \\ \hline
%     {1000} & 500 &9 &10.08 &150 & 120&17 &168.00 &10 &0.40 &9 &0.42 & 3&0.21 \\ \hline    
%     {1000} & 550 &10 &11.61 & 150&134.30 &18 &189.40 &7 &0.28 &13 &0.33 & 4&0.23 \\ \hline    
%     {1000} & 600 & 11&10.04 &150 &130.15 & 20&211.20 &9 &0.39 &14 &0.36 &5 &0.25 \\ \hline    
%     {1000} & 650 & 12&11.40 &150 &128.72 & 17&226.05 &11 &0.37 &14 &0.40 &5 &0.26 \\ \hline    
%     {1000} & 700 & 11& 11.52& 150&117.34 & 23&249.85 &10 &0.53 &15 & 0.50& 5&0.26 \\ \hline    
%     {1000} & 750 & 14& 10.22& 150&134.35 & 21&253.15 &11 &0.45 &14 & 0.41& 6&0.27 \\ \hline    
%     {1000} & 800 & 13&10.48 & 150&132.36 &20 &276.80 &11 &0.43 &14 &0.39 & 6&0.30 \\      
%   \hline
% \end{tabular}
% \label{nafiss:smallProblem}
% % \end{table*}
% \end{sidewaystable}
% 
% In the second test, I consider applying matrix completion algorithms to randomly generated low-rank matrix approximation problems varying the size and the rank of the matrix, and the number of coefficients $K$. The purpose of this test is to find a low-rank approximation to a mathematically full-rank matrix, where it can have the lower rank in a short time. I compared my proposed method  with LMaFit1 and LMaFit2, where the other solvers APGL, FPCA and SVT were excluded from this comparison since they would have demanded excessive CPU times. A summary of the computational results is presented in Table \ref{nafiss:largeProblem}. In this table, ``$Time$'' denotes the average CPU time, and ``$Rank$'' denotes the rank of the recovered solution for each solver.
% 
% 
% \begin{landscape}
% \begin{table}
% \renewcommand{\arraystretch}{1.85}
% \caption{ {Comparison of three solvers on problems with varying size, rank of the matrix and number of coefficients}}
% \label{table_example}
% \centering
% % \scriptsize
% \begin{tabular}{|c|c||c|c||c|c||c|c|}  
%   \hline
%   \multicolumn{2}{|c||}  {\textbf{ Problem}}  & \multicolumn{2}{c||}  {\textbf{LMaFit1 \cite{LMaFit:10}} }& \multicolumn{2}{c||}  {\textbf{LMaFit2 \cite{LMaFit:10}} }& \multicolumn{2}{c|}  {\textbf{Proposed method} }\\
%   \hline
%   \hline
% %   \multirow{2}{*}
%     {$p$ = $q$} & $K$ & $Rank$ & $Time$& $Rank$ & $Time$& $Rank$ & $Time$\\  \hline
%     {1000} & 300 & 4&0.34 &7 &0.35 &1 &0.16 \\ \hline
%     {1000} & 400  & 5&0.31& 8&0.39 &2 &0.20 \\ \hline 
%     {1000} & 500  &10 &0.40 &9 &0.42 & 3&0.21 \\ \hline  \hline  
%      
%     {5000} & 1500 & 18& 0.37&20 &0.36 &3 &1.03\\ \hline
%     {5000} & 2000 & 22 &0.41 &26 &0.45 & 4&1.39\\ \hline 
%     {5000} & 2500 &25 &0.41  &27 &0.43&8 &1.52\\ \hline \hline
%       
%     {10000} & 1000 & 20 & 2.47&23 & 3.64 &1 & 0.79\\ \hline     
%     {10000} & 1500 & 8& 1.32&9 &1.57 & 2&1.17 \\ \hline
%     {10000} & 2000 & 42& 2.12&51 &2.54 &2 & 1.86\\ \hline \hline
%  
%     {20000} & 1500 & 15 &7.75 &18 & 8.40&1 & 1.61\\ \hline
%     
%     
%   \hline
% \end{tabular}
% \label{nafiss:largeProblem}
% \end{table}
% \end{landscape}
% 
% 
% 
% 
% 
% \begin{figure}
% \centering
%  \includegraphics[width=15cm]{Pics/Plot_Rank_K}
% \caption{ {Final Rank of FPCA \cite{FPCA:09}, SVT \cite{SVT:08}, LMaFit1 \cite{LMaFit:10}, LMaFit2 \cite{LMaFit:10}, and the proposed method on small problems with varying rank and number of coefficients. Note that the input matrix has $1000$ rows and $1000$ columns.}}
% \label{nafiss:Plot_Rank_K}
% \end{figure}
% 
% 
% 
% 
% \subsubsection{Experiments on real matrix completion problems} \label{nafiss:realmatrix}
% 
% \begin{sidewaystable}
%     \centering
% % \begin{table*}[t]
% % \renewcommand{\arraystretch}{1}
% \caption{ {Numerical results on real data sets.}}
% % \label{table_example}
% \centering
% \begin{tabular}{|c|c||c|c|c|c||c|c|c|}  
%   \hline
%   \multicolumn{2}{|c||}  {\textbf{ Problem}}  & \multicolumn{4}{c||}  {\textbf{LMaFit \cite{LMaFit:10}}} &  \multicolumn{3}{c|}  {\textbf{Proposed method} }\\
%   \hline
%   \hline
% %   \multirow{2}{*}
%     {Name} & $p/q$ & $Iter$ & $Time$& $NMAE$ &$Rank$ & $Time$& $NMAE$ & $Rank$\\  \hline
%       jester-1 & $24983/100$ &  30 &3.54 &   0.1946 & 62 & 6.34  & 0.1942 & 100\\ \hline
%      jester-2& $23500/100$ &  35 &5.98 &  0.1960 &62 & 5.51 & 0.1959 & 100\\ \hline
%      jester-3 & $24938/100$ & 169 &8.02 &    0.1970 & 43 & 7.34& 0.1381 & 97 \\ \hline
%      jester-all & $73421/100$ & 35 & 11.15&    0.1869 & 62& 49.69 &  0.1865 & 100\\ \hline
%      \hline
% \end{tabular}
% \label{nafiss:realProblem}
% % \end{table*}
% \end{sidewaystable}
%     
% 
% 
% In this subsection, I consider the low-rank matrix approximation problems based on ``real data'' set, namely, the Jester joke data set\footnote{ The Jester joke data set includes $4.1$ million ratings for $100$ jokes from $73421$ users and is available online on the website: http://www.ieor.berkeley.edu/~goldberg/jester-data/.} \cite{goldberg2001eigentaste} and ``image inpainting''. 
% 
% The Jester joke data set contains four problems ``jester-1'' with $24983$ users who have rated $36$ or more jokes, ``jester-2'' with $23500$ users who have rated $36$ or more jokes, ``jester-3'' with $24938$ users who have rated between $15$ and $35$ jokes, and ``jester-all'' with combining all of the first three data sets.
% 
% let $M$ be the original incomplete data matrix where the $i^{th}$ row of $M$ corresponds to the ratings given by the $i^{th}$ user on the jokes, and $\delta$ be the set of indexes for which $M_{ij}$ is given. Since some of the entries of $M$ are missing, I compute the Normalized Mean Absolute Error (NMAE) to measure the accuracy \cite{goldberg2001eigentaste,LMaFit:10,APGL:09}. The NMAE is defined as
% 
% \begin{equation}
% NMAE = \frac{1}{r_{max}-r_{min}\left | \delta \right |} \sum_{(i,j) \in \delta}{\left | M_{ij}-X_{ij} \right |},
% \label{nafiss:11} 
% \end{equation}
% where $r_{min}$ and $r_{max}$ are the lower and upper bounds for the ratings, and $M_{ij}$ and $X_{ij}$ are the estimated and computed ratings of joke $j$ by user $i$, respectively. Note that I have $r_{min}= -10$ and $r_{max}=10$ and all ratings are scaled to the range $[-10, +10]$.
%  
%  
% Table \ref{nafiss:realProblem} shows the results for the LMaFit method \cite{LMaFit:10} and my proposed method on the real matrix completion problem using the jester joke data set.
% As shown in this table, my proposed method generally returns solutions with lower NMAE than those returned by LMaFit. It is critical to compare two solvers on problem ``jester-3'' where even LMaFit reports a solution with the lower rank of $43$; my solution is more accurate than LMaFit solution and shows the lower NMAE. 
% 

% 
% 
% 

 











% To graphically illustrate the effectiveness of my proposed method, I applied it to image inpainting. In grayscale image inpainting, the value of some of the pixels on the image are missing, and the task here is to fill these missing values. Note that the missing pixel positions in the image inpainting are not randomly distributed. If the image is of low-rank, or of numerical low-rank, the matrix completion solvers can be applied on the image inpainting problem to obtain low-rank approximations. 
% 
% 
% The $512 \times 512$ original grayscale image is shown in Fig. \ref{nafiss:Impainting} (a). Fig. \ref{nafiss:Impainting} (b) was obtained by truncating the SVD of the images to get the images of rank $40$. Fig. \ref{nafiss:Impainting} (c) is the masked image obtained from Fig. \ref{nafiss:Impainting} (b), where $9.30\%$ of the pixels were masked in a non-random fashion. The recovered images of Fig. \ref{nafiss:Impainting} (c) from  LMaFit, APGL, and my proposed method are depicted in Figs. \ref{nafiss:Impainting} (d), (e), and (f). 
% 
% Table \ref{nafiss:Inpaintingtb} shows a summary of the computational results of the image inpainting. Note that in this table, $Rel.err$ \footnote{I used the relative error: $Rel.err := \frac{\left \|  M_{rec} - M \right \|_F}{\left \|  M \right \|_F} $ to estimate the closeness of  $M_{rec}$ to $M$, where $M_{rec}$ is the ``recovered'' image produced by the algorithms, and $M$ is the original image. } denotes the relative error between the original and recovered images. From these figures and the table, I can see my proposed method recover the images significantly better than the other methods with the less relative error.
% 
% 
% 
% 
% }}
% \section{Application to Video Denoising} \label{nafiss:videodenoising}
% {\color{myred}Introduction to video denoising: problem formulation and state-of-the-art.}

Video sequences are often corrupted by noise during acquisition or transmission. Some noise sources located in camera hardware became active during image acquisition under some lighting conditions. Other noise sources are over transmission channels. Most video denoising algorithms proposed in the literature assume additive white Gaussian noise, which can be categorized into pixel domain and transform domain methods. However, I consider Impulsive/Poisson/Gaussian noise in my work and will show how robust my video denoising method is.

Many video denoising methods have been proposed in the last few decades, e.g., \cite{dabov2007video,ref:Chang,selesnick2003video,tomasi1998bilateral}. One of the first methods to address the denoising problem was the bilateral filter, which was proposed by Tomasi and Manduchi \cite{tomasi1998bilateral}. However, this method fails to perform well in when the noise is strong. Selesnick and Li \cite{selesnick2003video} proposed 2D and 3D dual-tree oriented wavelet transforms which give a motion-based multi-scale decomposition for video. They used the proposed transforms for video denoising, where the 2D transform is applied to each frame individually. 


Recently, the idea of patch based sparse coding has been applied to video denoising \cite{mairal2009non,orchard1994overlapped,dabov2007image,dabov2007video}. Marial \textit{et al.} in \cite{mairal2009non} suggested to extend the sparse coding approach by proposing that similar patches share the same dictionary elements in their sparse decomposition on denoising. Another recent example based on an enhanced sparse representation in transform domain is block-matching 3-D filter (BM3D) \cite{dabov2007image}. In BM3D, similar 2D image blocks are grouped into a 3D data array based on the $l_2$ norm distance function. Then, the 3D data array is filtered by wavelet shrinkage or Wiener filter in 3D transform domain. The denoised image is produced from all grouped blocks after applying the inverse 3D transform. The concept of BM3D is generalized to video denoising in VBM3D \cite{dabov2007video}. In VBM3D, the noisy video is processed in a block-wise manner in both spatial and temporal domains. Then, a predictive 
search block-matching is combined with collaborative hard thresholding or collaborative Wiener filtering. 

Unfortunately, prior works have been limited to one specific type of noise, there also exist other types of noise will degrade the performance of the denoising methods. In contrast, my method does not suffer from this limitation and can remove serious mixed noise from video sequences.

In this work, I show that the proposed method can operate directly on the raw noisy images that suffer from non-homogeneous noise. The proposed method is similar to that described in \cite{ji2010robust}. However, I incorporate the matrix completion method \cite{ma2014decomposition} into the denoising algorithm and rather than applying a suboptimal block matching algorithm as in \cite{liu1993new}, I use a near-optimal block matching method \cite{nie2002adaptive} with higher complexity. I can afford latter as the matrix completion method runs significantly faster than other matrix completion methods. 
% I propose to solve the video denoising problem using an image model that utilizes a patch based matching algorithm \cite{nie2002adaptive} and my proposed decomposition approach for matrix completion. 
The goal of my denoising method is to keep only the reliable pixels and get rid of all other un-reliable pixels I find as noise. For each patch in the reference frame, I find the similar patches in the other frames using a block matching algorithm. The found matches will be vectorized and then stacked into a matrix. The reliable pixel values in the matrix are between the mean $\pm$ standard deviation of all elements in the same row. The main step will be done by applying the matrix completion approach \cite{ma2014decomposition} on the incomplete matrix. The output of matrix completion is a noise free full matrix. Then, the average value of each row in the full matrix can recover the denoised patch. Repeating the same procedure for all blocks of reference frame can build a denoised frame.

\section{Denoising Method} 
%  {\color{myred}Describe how decomposition method for matrix completion is applied to video denoising
%  Video Denoising using Decomposition Approach for Low-rank Matrix Completion}

The problem of video denoising can mathematically be shown as 
\begin{equation}
y(x) = z(x) + n(x), 
\label{nafiss:DenoisinProblem} 
\end{equation}
where $z(x)$ is the original video signal and $y(x)$ is the observed video after being corrupted by Gaussian/Poisson/Impulsive noise $n(x)$. $x=(i,j,k) \in X$ are coordinates in the spatio-temporal $3D$ domain $X \subset  \mathbb{Z}^3$, where the first two components $(i,j)$ are the spatial coordinates and the third one $k$ is the time (frame) index. The main procedure for my proposed denoising method is summarized in Algorithm \ref{nafiss:Denoisingalgorithm}.

\vspace{20pt}

\begin{algorithm} [!t]
\caption{Video Denoising using matrix completion- estimate version of denoised image $\mathcal{X}$ }
\begin{algorithmic} 
\renewcommand{\algorithmicrequire}{\textbf{Inputs :}}
\renewcommand{\algorithmicensure}{\textbf{Output :}}
\REQUIRE {noisy video $y$, pixel overlap $v$  }
\renewcommand{\algorithmicrequire}{\textbf{Initialize}}
\REQUIRE { \textbf{:}}
\begin{itemize}
\item Set ${\mathcal{V}}$ and ${\mathcal{W}}$ to be zero images of the same size as the video frame size. 
\end{itemize}
\renewcommand{\algorithmicrequire}{\textbf{Produce the pre-processing step}}
\REQUIRE {\textbf{for removing impulsive noise before patch matching :}}
\begin{itemize}
\item Apply Adaptive Median Filter:

$Y^{am} = AMF (y)$

\end{itemize}
\renewcommand{\algorithmicrequire}{\textbf{Find the denoised patches:}}
\REQUIRE {For each coordinate $x \in \Omega$ with $v$ pixel overlap in each direction do:}
\begin{enumerate}[(a)]
\item $S_x = BM \Big(Y^{am}_x\Big)$
\item $\hat{\mathcal{Z}_{S_x}} = ReliableElements \Big(\mathbf{Y}_{S_x}\Big)$
\item $\check{\mathcal{Z}_{x}} = DMC \Big(\hat{\mathcal{Z}}_{S_x}\Big)$
\item $\hat{z}_{x}= AVG_{row}(\check{\mathcal{Z}_{x}})$
\item ${\mathcal{V}} = {\mathcal{V}} + \hat{z}_{x}$
\item ${\mathcal{W}} = {\mathcal{W}} + \hat{w}_{x}$
\end{enumerate}
\renewcommand{\algorithmicrequire}{\textbf{Normalize :}}
\REQUIRE {$\hat{\mathcal{Z}}$ = ${\mathcal{V}}/{\mathcal{W}}$ }
\renewcommand{\algorithmicrequire}{\textbf{Output :}}
\REQUIRE {a denoised image $\hat{\mathcal{Z}}$ }
\end{algorithmic}
\label{nafiss:Denoisingalgorithm}
\end{algorithm}



\textbf{Implementation Details:} \label{nafiss:Notation}
\begin{itemize}

\item $Y^{am} = AMF (y)$ performs adaptive median filtering using $y$. Because, the video is corrupted by image noise, applying a patch matching algorithm directly on noisy video generates unreliable result. Specifically, the block matching algorithm will suffer from impulsive noise, and its performance will be seriously degraded by strong impulsive noise. Hence, using a preprocessing step to remove impulsive noise before the block matching step will improve the resulting performance. In my work, I simply use the adaptive median filter proposed by Hwang and Haddad in \cite{hwang1995adaptive}.

\item $\Omega \subset X$ is a set that includes the coordinates of the reference blocks. In general, each pixel in the reference image is covered by several patches. I aggregate overlapped patches by a weighted average at each pixel.

\item $Y^{am}_x$ denotes a block of size $q \times q$ in $Y^{am}$, where its center is at $x$.

\item $S_x = BM \Big(Y^{am}_x\Big)$ presents a block matching algorithm using $Y^{am}_x$ as a reference block, where the result is the set $S_x$ containing the coordinates of the matched blocks. Although there are several methods to find the similar matches \cite{barzigar2012scobep,zimmer2008rotationally,dabov2007video,barzigar2013video}, in my work, I use the Adaptive Rood Pattern Search (ARPS) algorithm \cite{nie2002adaptive} because of its computational efficiency. 

\item $\mathbf{Y}_{S_x}$ denotes a matrix formed by stacking the vectorized blocks $Y_{x \in S_x}$ together, where $Y_x $ is a block of size $q \times q$ centered at $x$ in $y$.

\item $\hat{\mathcal{Z}_{S_x}} = ReliableElements \Big( \textbf{Y}_{S_x}\Big)$ discards those matrix elements of $\mathbf{Y}_{S_x}$ that are far away from $mean \pm standard \ deviation$ of its corresponding row, designates them as unreliable elements, and then replaces them by zero. Note that those unreliable elements could be the pixels corrupted by Gaussian/Poisson/Impulsive noise or from mismatched patches obtained from previous step (block matching). Also, keeping the reliable elements, lets us recover the full matrix needed for the next step. 

\item $\check{\mathcal{Z}_{x}} = DMC \Big(\hat{\mathcal{Z}}_{S_x}\Big)$ performs a decomposing approach for low-rank matrix completion algorithm (see Section \cite{ma2014decomposition})
% (Section \ref{rick:ProposedDMC})
using $\hat{\mathcal{Z}}_{S_x}$ and $\check{\mathcal{Z}_{x}}$ that will be a full matrix with noise free elements. Recently, many matrix completion methods have been studied \cite{candes2009matrix,LMaFit:10,keshavan2010matrix}. In my work, I use a decomposing approach for low-rank matrix completion algorithm, because of its computational efficiency.


\item $\hat{z}_{x}= AVG_{row}(\check{\mathcal{Z}_{x}})$ finds the average value of each row in matrix $\check{\mathcal{Z}_{x}}$ and converts the obtained vector to a block. Also, $\hat{z}_{x}$ will be an estimated block of size $q \times q$ centered at $x$ in $\hat{\mathcal{V}}$.

\item $\hat{w}_{x}$ is a patch with the same size as $\hat{z}_{x}$. Note that, all pixel values in $\hat{w}_{x}$ are equal to $1$.
\end{itemize}

\begin{figure*}
 \centering
\subfloat[]{\includegraphics[width=6cm]{Pics/Noisy_Galleon_G02_I03}}
\subfloat[]{\includegraphics[width=6cm]{Pics/Galleon_tvreg_G02_I03}}

\subfloat[]{\includegraphics[width=6cm]{Pics/VBM3D_Galleon_G02_I03}}
\subfloat[]{\includegraphics[width=6cm]{Pics/DMC_Galleon_G02_I03}}
\caption{  {Video denoising for \textit{Galleon} sequence: (PSNR in brackets). From left to right: noisy image; tvregv2 \cite{TVreg2009} [PSNR: 17.8208]; VBM3D algorithm \cite{dabov2007video} [PSNR: 17.9226];  result of the proposed denoising algorithm [PSNR: 21.2437].}}
\label{nafiss:denoising_g_02_I_03}
% \end{center}
\end{figure*}


\begin{landscape}
\begin{table}
 \renewcommand{\arraystretch}{1.1}
\caption{ {Output PSNR of my proposed denoising method for the two video sequences; note that, I kept the Gaussian and Poisson noise constant in all tests}}
\label{table_example}
\centering
% \scriptsize
\begin{tabular}{|c||c|c|c|c|}  
  \hline
 \backslashbox {\textbf{ Impulsive noise density}}{\textbf{ Video name }(frame size)}   & \textbf{Suzie}   & \textbf{Coastguard} \\ 
%  ($234 \times 342$)($288 \times 342$)
   \hline
   \hline
%    \multirow{2}{*}
 {0.10} 	& 26.3679 & 22.6124 \\  \hline
 {0.15} 	& 26.2852& 22.6060 \\  \hline
 {0.20} 	& 26.3810& 22.5819 \\  \hline
 {0.25} 	& 26.3135& 22.6281 \\  \hline
 {0.30} 	& 26.3545& 22.6105 \\  \hline
 {0.35} 	& 26.4119& 22.6163 \\  \hline
 {0.40} 	& 26.2867& 22.6346 \\  \hline
 {0.45} 	& 26.3257& 22.6149 \\  \hline
 {0.50} 	& 26.3257& 22.5907 \\
  \hline
\end{tabular}
\label{nafiss:Impulsivenoise}
\end{table}
% \end{landscape}

\begin{table}[t!]
\renewcommand{\arraystretch}{2}
\caption{ {\color{black}{{PSNR and time comparison for using various matrix completion}}}}
\label{table_example}
 \centering
%  \scriptsize
\begin{tabular}{|c|c||c|c|c|c|c|}  
  \hline
%   \textbf{\scriptsize{Galleon Sequence}} 
\multicolumn{2}{|c||} {}& \textbf{Tempete} & \textbf{Galleon} & \textbf{Coastguard}  \\
  \hline
  \hline
   \multirow{2}{*}
    {\textbf{{Proposed method}}} & $PSNR[dB]$ & 23.37 & 22.73 & 23.57\\ \cline{2-5}
 & $Time (seconds)$ &  240 &  218 & 110	   \\ \hline
\hline
% \multirow{2}{*}
	{\textbf{{Denoising method}}} & $PSNR[dB]$ & 22.79 & 22.60& 23.63 \\ \cline{2-5}
 \textbf{{using OptSpace \cite{keshavan2010matrix}}}& $Time (seconds)$ &  1355 &  1683 & 	538   \\ \hline
 \hline
% \multirow{2}{*}
{\textbf{{Denoising method}}} & $PSNR[dB]$ & 22.78 &22.52& 21.81 \\ \cline{2-5}
 \textbf{{using LMAFIT1 \cite{LMaFit:10}}}& $Time (seconds)$ & 220  & 251  & 119	   \\ \hline
  \hline
  
%   \multirow{2}{*}
  {\textbf{{Denoising method}}} & $PSNR[dB]$ & 21.38 &20.39 & 20.97 \\ \cline{2-5}
 \textbf{{using FPCA \cite{FPCA:09}}}& $Time (seconds)$ & 5828 & 7069  & 1584	   \\ \hline
  
\end{tabular}
\label{nafiss:comparetime}
\end{table}
\end{landscape}

\begin{landscape}
 \begin{table}
\centering
\caption{{Average PSNR for the two video sequences}}
% \begin{table}
% \renewcommand{\arraystretch}{1}
% \centering
\begin{tabular}{|c||c|c|c|c|c|}  
  \hline
  \textbf{ Sequence} & \textbf{Wiener2} & \textbf{VBM3D \cite{dabov2007video}} & \textbf{3DWTF \cite{selesnick2003video}} & \textbf{tvregv2 \cite{TVreg2009}} & \textbf{Proposed denoising Method} \\
  \hline
  \hline
%   \multirow{2}{*}
    {Miss America} 	& 26.6796 & 30.9090 & 24.5168 &28.1036 & 32.1931\\  \hline
    {vtc1nw} 	& 25.5855 & 28.2356 & 22.1496 & 27.7033 & 31.6442\\
  \hline
\end{tabular}
\label{nafiss:averageVideo}
% \end{table}
\label{table_example}
\end{table}
\end{landscape}


\begin{figure*}
\begin{center}
 \includegraphics[width=11cm]{Pics/Plot_coastguard_guass.pdf}
 
 \includegraphics[width=11cm]{Pics/Plot_Suzie_guass.pdf}
\caption{ {PSNR values of VBM3D algorithm \cite{dabov2007video} and proposed denoising method for \textit{Coastguard} and \textit{Suzie} sequences. Note that, I kept the Impulsive noise consistent in all tests.}}
\label{nafiss:plotincreeseGuas}
\end{center}
\end{figure*}





\begin{figure*}
 \centering
% \subfloat[]{\includegraphics[width=4cm]{Pics/Suzie_Noisy_g_02_I_01.pdf}}
\subfloat[]{\includegraphics[width=6cm]{Pics/Noisy_Suzie_02_01}}
\subfloat[]{\includegraphics[width=6cm]{Pics/tvreg2_Suzie_02_01}}

\subfloat[]{\includegraphics[width=6cm]{Pics/VBM3D_Suzie_02_01}}
\subfloat[]{\includegraphics[width=6cm]{Pics/Suzie_02_01}}
%\subfloat[]{\includegraphics[width=4cm]{Pics/Suzie_DMC_g_02_I_01.pdf}}
\caption{  {Video denoising for \textit{Suzie} sequence: (PSNR in brackets). (a) noisy image; (b) tvregv2 \cite{TVreg2009} [PSNR:25.1205]; (c) VBM3D algorithm \cite{dabov2007video} [PSNR:26.5245]; (d) result of the proposed denoising algorithm [PSNR:29.3254].}}
\label{nafiss:denoising_g_02_I_01}
% \end{center}
\end{figure*}


\begin{figure*}
 \centering
\subfloat[]{\includegraphics[width=6cm]{Pics/Noisy_CoustGuard_G02_I03}}
\subfloat[]{\includegraphics[width=6cm]{Pics/tvreg_Galleon_G02_I03}}

\subfloat[]{\includegraphics[width=6cm]{Pics/VBM3D_CoustGuard_G02_I03}}
\subfloat[]{\includegraphics[width=6cm]{Pics/DMC_CoustGuard_G02_I03}}
\caption{  {Video denoising for \textit{Coastguard} sequence: (PSNR in brackets). (a) noisy image; (b) tvregv2 \cite{TVreg2009} [PSNR:20.9469]; (c) VBM3D algorithm \cite{dabov2007video} [PSNR:21.0090]; (d) result of the proposed denoising algorithm [PSNR:23.5725].}}
\label{nafiss:denoising_Coast_g_02_I_03}
% \end{center}
\end{figure*}




\section{Experimental Results on Denoising} \label{Denoisingesults}


\subsection{Natural Image Experimental Results} \label{Denoisingesults}
In this section, I present some video denoising examples to evaluate my performance, using existing sequences such as Miss America, Galleon, and Suzie. All tests in this section were processed in the following manner: All 30 frames were involved in the reconstruction of each image. The block size used for block matching ($q$) was $20 \times 20$ and was not changed for various tests. I obtained a locally consistent solution by allowing patches to overlap, where the overlapped regions ($v$) were $5$ pixels in each direction. Also, for each reference patch, I extracted $5$ most similar patches used in each frame using block matching algorithm.
{\color{myred} For simplicity, I employ the basic version of my algorithm without taking advantage of sub u-diagonalization.}


In Fig. \ref{nafiss:denoising_g_02_I_03}, I show the PSNR result and a clear visual comparison of the Galleon sequence. The original video is seriously corrupted by a significant mixed noise level with Poisson noise, Gaussian white noise of mean zero and variance $0.02$, and Impulsive noise of the noise density $0.03$. As shown in Figures. \ref{nafiss:denoising_g_02_I_03} and \ref{nafiss:denoising_g_02_I_01}, 
VBM3D method \cite{dabov2007video} and tvregv2 \cite{TVreg2009} generate severe artifacts at edge areas, while my proposed denoising method performs remarkably well for the detail structures and is free of these artifacts.




% 
% \begin{figure*}[!t]
%   \centering
%   \subfloat{\label{fig:cc24}\includegraphics[width=4cm]{Pics/Galleon_DMC_g_02_I_03.pdf}}                
%   \subfloat{\label{fig:cc24}\includegraphics[width=4cm]{Pics/Galleon_VBM3D_g_02_I_03.pdf}} 
% %    \vspace{-5pt}              
%   \caption{  {Block diagram representation of SCoBeP-SR.}}\vspace{-15pt}
%   \label{dg:model} 
% \end{figure*}

In Table \ref{nafiss:Impulsivenoise}, I present the PSNR results of the proposed denoising algorithm for a few sequences, where Impulsive noise is changing. This table shows how my algorithm is robust in denoising the corrupted sequences of serious impulsive noise.



\begin{figure}
\begin{center}
 \includegraphics[width=11cm]{Pics/Plot_Miss_frameByframe.pdf}
 
\includegraphics[width=11cm]{Pics/Plot_VTC_frameByframe.pdf}
\caption{  {PSNR values of each denoised frame by VBM3D algorithm \cite{dabov2007video}, 3DWTF \cite{selesnick2003video}, tvregv2 \cite{TVreg2009}, wiener2 and the proposed denoising method for (a) the \textit{Miss America} and (b) the \textit{vtc1nw} sequence.}}
\label{nafiss:plotframebyframe}
\end{center}
\end{figure}


In Graph \ref{nafiss:plotincreeseGuas}, I compare my denoising method with the VBM3D method \cite{dabov2007video}, which is among the state-of-the-art in video denoising. In this comparison, I apply my denoising method on Coastguard and Suzie sequences, for which I changed the Gaussian noise but kept the Poisson and Impulsive noise constant for all methods. Note that, for a fair comparison and also because the VBM3D method \cite{dabov2007video} works on removing just the Gaussian noise from the corrupted video, I ran the adaptive median filter method \cite{hwang1995adaptive} on the test data with a pre-process of removing impulsive noise. In contrast, in my work, I did not use any existing impulsive noise method to detect pixels corrupted by Impulsive noise. The graph in Fig. \ref{nafiss:plotframebyframe} shows the frame by frame PSNR values of Miss America and vtc1nw. Table \ref{nafiss:averageVideo} shows the average PSNR values for my proposed method and the compared methods. My proposed method 
surpasses the VBM3D method \cite{dabov2007video} in all frames by a significant margin for all sequences with more than 2dB. In contrast, while \cite{ji2010robust} also outperform the VBM3D method but with a significantly smaller margin, I conjecture that the gain is due to the near-optimal block matching method \cite{nie2002adaptive} used in my approach. 







{\color{black}{I also replaced my proposed decomposition matrix completion with OptSpace \cite{keshavan2010matrix}, LMAFIT1 \cite{LMaFit:10} and FPCA \cite{FPCA:09} to compare the result and time consumption (see Table \ref{nafiss:comparetime}). It can be seen in Table \ref{nafiss:comparetime} that my method 
% compares well or even better in terms of PSNR, 
has comparable performance in terms of PSNR,
for which it executes much faster than those methods.}}

\subsection{Inpainting Experimental Results}
To graphically illustrate the effectiveness of my proposed method, I applied it to image inpainting. In grayscale image inpainting, the value of some of the pixels on the image are missing, and the task here is to fill these missing values. Note that the missing pixel positions in the image inpainting are not randomly distributed. If the image is of low-rank, or of numerical low-rank, the matrix completion solvers can be applied on the image inpainting problem to obtain low-rank approximations. 

\begin{landscape}
\begin{figure*}[htb]
 \centering
\subfloat[]{\includegraphics[width=5.6cm]{Pics/Boat_gt}}
\subfloat[]{\includegraphics[width=5.6cm]{Pics/Boat_40}}
\subfloat[]{\includegraphics[width=5.6cm]{Pics/Boat_painting}}

\vspace{-10pt}

\subfloat[]{\includegraphics[width=5.6cm]{Pics/Boat_LMaFit}}
\subfloat[]{\includegraphics[width=5.6cm]{Pics/Boat_APGL}}
\subfloat[]{\includegraphics[width=5.6cm]{Pics/Boat_DMC}}
\caption{  {Image inpainting Problem for \textit{Boat} image: (a) Original image; (b) rank 40 image; (c) deterministically $9.30\%$ masked rank 40 image; (d) LMaFit1 \cite{LMaFit:10}; (e) APGL \cite{APGL:09}; (f) result of the proposed method.}}
\label{nafiss:Impainting}
% \end{center}
\end{figure*}
\end{landscape}

The $512 \times 512$ original grayscale image is shown in Fig. \ref{nafiss:Impainting} (a). Fig. \ref{nafiss:Impainting} (b) was obtained by truncating the SVD of the images to get the images of rank $40$. Fig. \ref{nafiss:Impainting} (c) is the masked image obtained from Fig. \ref{nafiss:Impainting} (b), where $9.30\%$ of the pixels were masked in a non-random fashion. The recovered images of Fig. \ref{nafiss:Impainting} (c) from  LMaFit, APGL, and my proposed method are depicted in Figs. \ref{nafiss:Impainting} (d), (e), and (f). 

% \begin{sidewaystable}
%     \centering
% % \begin{table*}[t]
% % \renewcommand{\arraystretch}{1}
% \caption{ {Numerical results on image inpainting}}
% % \label{table_example}
% % \centering
% \begin{tabular}{|c|c||c|c|c|c||c|c|c|c||c|c|c|}  
%   \hline
%   \multicolumn{2}{|c||}  {\textbf{ Problem}}  & \multicolumn{4}{c||}  {\textbf{APGL \cite{APGL:09}} }& \multicolumn{4}{c||}  {\textbf{LMaFit1 \cite{LMaFit:10}} }&  \multicolumn{3}{c|}  {\textbf{Proposed method} }\\
%   \hline
%   \hline
% %   \multirow{2}{*}
%     {$\% mask$} & $r$ & $Iter$ & $Time$& $Rel.err$ &$Rank$ & $Iter$ & $Time$& $Rel.err$ &$Rank$ &   $Time$& $Rel.err$ &$Rank$\\  \hline
%      3.70  & 40 & 33 & 8.37 & 0.1039 & 50 & 195 & 7.29 &
%     0.0818 & 42 & 7.80 & 0.0794  & 40\\ \hline
%     
%      9.30  & 40 & 29 & 2.78 & 0.0354  &  50& 139 & 1.49 &   0.0365 & 40 & 3.45 & 0.0248  &  40\\ \hline
%      
%        15.81 & 40 & 33 & 3.32 &  0.1155  &50  & 258 & 2.74 &    0.1408 &46  & 5.21 & 0.0890   & 40 \\ \hline
% \end{tabular}
% \label{nafiss:Inpaintingtb}
% % \end{table*}
% \end{sidewaystable}
% 
% Table \ref{nafiss:Inpaintingtb} shows a summary of the computational results of the image inpainting. From these figures and the table, I can see my proposed method recover the images significantly better than the other methods with the less relative error.

\subsection{Medical Experimental Results}\label{ExResult}
\ths{To evaluate the performance of the proposed method}, I consider in two separated subsections with two different sets of experiments. 
% We utilize lung test in Section \ref{Ex:synthetic} to compare the performance of my proposed method with the state-of-the-art methods 
\ths{In Section \ref{Ex:synthetic}, 
I will first generate synthetic noisy slices and then apply denoising methods to the degraded slices. I will then compare the results to the ground truth (the original slices) and results generated from other state-of-the-art techniques
\cite{buades2005non,pizurica2006review,bao2003noise}. }
 \ths{Moreover}, in Section \ref{Ex:real}, I will illustrate additional examples that will assess my denoising method for real CT slices. Comparison will be made  against \ths{two state-of-the-art techniques:} the \ths{adaptive multiscale} image denoising algorithm \cite{bao2003noise} and \ths{wavelet} domain image denoising algorithm \cite{pizurica2006review}.
%  which were implemented using the software provided by their authors.

\begin{figure}[h]
\begin{center}
 \includegraphics[height=7cm]{Pics/Plot_02g_95}
\caption{ \comm{why using so many upper case on weird places?} {PSNR values of non-local means algorithm \cite{buades2005non}; wavelet domain image denoising algorithm \cite{pizurica2006review}; adaptive multiscale image denoising algorithm \cite{bao2003noise}; result of the proposed denoising algorithm  for lung CT slices; Note that, I kept the Gaussian noise constant in all tests.}}
\label{nafiss:plotincreeseGuas}
\end{center}
\end{figure}


I also replaced my proposed decomposition matrix completion with OptSpace \cite{keshavan2010matrix} to compare the result and time consumption (Table \ref{nafiss:comparetime}). It can be seen that my method compares well or even betters in terms of PSNR, \ths{and it performs notably} faster than OptSpace \cite{keshavan2010matrix}.

\subsubsection{Evaluation on Synthetic Slices}\label{Ex:synthetic}
To evaluate the performance of my approach, I conducted tests on the data sets LIDC-IDRI \cite{website:LIDCIDRI} where the size of each slice of the CT slices are $512 \times 512$ pixels.
All tests in this section were processed in the following manner: All $6$ slices were involved in the denoised slice. The similar block size used for block matching was $8 \times 8$ and was not changed for various tests. I obtained a locally consistent solution by allowing patches to overlap, where the overlapped regions ($v$) were $5$ pixels in each direction. \ths{Further}, for each reference patch, I extract $5$ most similar patches used in each slice using block matching algorithm.

\begin{table}[t]
% \renewcommand{\arraystretch}{1.3}
\caption{ {\ths{PSNR of my proposed denoising method for the lung slices}; note that, I kept the \ths{variaces of Gaussian and Poisson noises constant} in all tests.}}
\label{table_example}
\centering
\begin{tabular}{|c||c|c|c|c|}  
  \hline
\textbf{ Noise density of Impulsive noise}   & \textbf{Lung Slices} ($362 \times 362$) \\
   \hline
   \hline
%    \multirow{2}{*}
 {0.06} 	& 24.10 \\  \hline
 {0.06} 	& 24.05 \\  \hline
 {0.11} 	& 24.04 \\  \hline
 {0.16} 	& 24.04 \\  \hline
 {0.21} 	& 24.07 \\  \hline
 {0.26} 	& 24.05 \\  \hline
 {0.31} 	& 24.05 \\  \hline
 {0.36} 	& 24.05 \\  \hline
 {0.41} 	& 24.07 \\  \hline
 {0.46} 	& 24.06 \\
  \hline
\end{tabular}
\label{nafiss:Impulsivenoise}
\end{table}

\comm{Check that your upper case convention is consistent}
In Fig. \ref{nafiss:denoising_g_02_I_01}, I show the PSNR result and a clear visual comparison on the CT slices. The original CT slice is \ths{corrupted by 
% significant mixed noise level with 
a mixture of Poisson noise, Gaussian white noise, impulsive noise with significant noise level (variance of Gaussiance noise = $0.02$ and \scc{how do you define noise density?}{noise density} of impulsive noise = $0.01$)}.
% of mean zero and variance $0.02$, and Impulsive noise of the noise density $0.01$. 
As shown in \ths{the} figure, non-local means algorithm \cite{buades2005non}, wavelet domain image denoising algorithm \cite{pizurica2006review}, and adaptive multiscale image denoising algorithm \cite{bao2003noise} generate severe artifacts at edge areas, while my proposed denoising method performs remarkably well for the detail structures and is free of these artifacts.

To quantify my denoising performance, I used the Peak Signal to Noise Ratio (PSNR) measure between the ground truth and denoised CT slice:
\begin{equation}
 PSNR = 10\ \ log_{10}(255^2/Mean\ \ Square \ \ Error) [dB].
\end{equation}



\begin{figure}[h!]
 \centering
\subfloat[]{\includegraphics[height=4cm]{Pics/GT_95}}
\subfloat[]{\includegraphics[height=4cm]{Pics/Noisy_95_g02_I01}}

\subfloat[]{\includegraphics[height=4cm]{Pics/NML_95_2003_02g_01I}}
\subfloat[]{\includegraphics[height=4cm]{Pics/Sanja_90_2003_02g_01I}}

\subfloat[]{\includegraphics[height=4cm]{Pics/Zhang_MI_90_2003_02g_01I}}
\subfloat[]{\includegraphics[height=4cm]{Pics/DMC_95_g02_I01}}
\caption{ {Synthetic experiment 1: (PSNR in brackets). (a) ground truth; (b) noisy slice; (c) non-local means algorithm \cite{buades2005non} [PSNR:20.56]; (d) wavelet domain image denoising algorithm \cite{pizurica2006review} [PSNR:23.26]; (e) adaptive multiscale
 image denoising algorithm \cite{bao2003noise} [PSNR:22.78]; (f) result of the proposed denoising algorithm [PSNR:24.07]. Note that, I kept the Gaussian/Poisson/Impulsive noise constant in all tests.}}
\label{nafiss:denoising_g_02_I_01}
% \end{center}
\end{figure}


\begin{landscape}
\begin{figure*}[!]
 \centering
\subfloat{\includegraphics[height=3.7cm]{Pics/Real_70}}
\subfloat{\includegraphics[height=3.7cm]{Pics/Zhang_MI_70_2003}}
\subfloat{\includegraphics[height=3.7cm]{Pics/Sanja_MRI_70_2003}}
\subfloat{\includegraphics[height=3.7cm]{Pics/DMC_70}}

\vspace{-10pt}
\centering
\subfloat{\includegraphics[height=3.7cm]{Pics/Real_80}}
\subfloat{\includegraphics[height=3.7cm]{Pics/Zhang_MI_80_2003}}
\subfloat{\includegraphics[height=3.7cm]{Pics/Sanja_MRI_80_2003}}
\subfloat{\includegraphics[height=3.7cm]{Pics/DMC_80}}

\vspace{-10pt}
\centering
\subfloat{\includegraphics[width=3.7cm]{Pics/Real_80_Zoom}}
\subfloat{\includegraphics[width=3.7cm]{Pics/Zhang_MI_80_2003_Zoom}}
\subfloat{\includegraphics[width=3.7cm]{Pics/Sanja_MRI_80_2003_Zoom}}
\subfloat{\includegraphics[width=3.7cm]{Pics/DMC_80_Zoom}}
\caption{ {\ths{Non-synthetic (real)} experiment. From left to right: real CT slice; adaptive multiscale
 image denoising algorithm \cite{bao2003noise}; wavelet domain image denoising algorithm \cite{pizurica2006review}; result of the proposed denoising algorithm.}}
\label{nafiss:denoising_g_02_I_03}
% \end{center}
\end{figure*}
\end{landscape}






In Table \ref{nafiss:Impulsivenoise}, I present the PSNR results of the proposed denoising algorithm for a lung CT slices; where impulsive noise is changing. This table shows how my algorithm is robust in denoising of the corrupted slices by serious impulsive noise.
In graph \ref{nafiss:plotincreeseGuas}, I compare my denoising method with adaptive multiscale
 image denoising algorithm \cite{bao2003noise}, wavelet domain image denoising algorithm \cite{pizurica2006review}, and non-local means algorithm \cite{buades2005non}, which are among the state-of-the-art in medical image denoising.


In this comparison, I apply my denoising method on lung slices which I changed the impulsive noise and kept the Poisson and Gaussian noise constant for all methods. My proposed method surpasses the other methods \ths{with} a significant margin for all additive Impulsive Noise.

% My proposed method beats the VBM3D method \cite{dabov2007video} in all frames by a significant margin for all sequences. 








\begin{table}
\renewcommand{\arraystretch}{1.3}
\caption{ {PSNR and time comparison for using various matrix completion for lung slices}}
\label{table_example}
\centering
\begin{tabular}{c||c|c}  
%    \hline
%   \textbf{\scriptsize{Galleon Sequence}} 
& \textbf{{Proposed }} & \textbf{{Denoising method }}  \\
& \textbf{{ method}} & \textbf{{using OptSpace \cite{keshavan2010matrix}}}  \\
  \hline
  \hline
%   \multirow{2}{*}
    \textbf{PSNR  } 	& 21.83 &  21.65 \\ \hline
	\textbf{Time $(seconds)$}	& 118 & 1398\\

%   \hline
\end{tabular}
\label{nafiss:comparetime}
\end{table}


\comm{use non-synthetic experiment instead of real experiment}
\subsubsection{Evaluation On Non-Synthetic Slices}\label{Ex:real}
In this section, I turn to some real slices, where I apply my proposed method without any changes or generating noisy slices. Note that since there are no published methods that perform denoising on such general slices, I choose the adaptive multiscale image denoising algorithm \cite{bao2003noise} and wavelet domain image denoising algorithm \cite{pizurica2006review} for comparison, because their source code is available. 
%In order to apply my method directly to the MR slices, 
\ths{As for the non-synthetic case, while 
I do not have the ground truth and thus cannot evaluate the the methods quantitatively using PSNR,} the visual comparison \ths{illustrates the robustness of} my proposed method when \ths{it is applied directly to real} slices. Note that I used the same slices number, block size, overlapped region, and extracted patches number \ths{for the non-synthetic experiment just as the synthethic case}.



\subsubsection{Evaluation on 3D Images}\label{EXPERIMENTAL}

I evaluate my framework on Lung data sets LIDC-IDRI \cite{website:LIDCIDRI} where the size of each slice of the CT slices are $512 \times 512$ pixels. In general, the evaluation and thus, 3D medical denoising methods is a difficult task. Usually, ground truth data for real noisy data - especially in medical applications - is not available. Therefore, I perform several experiments illustrating the potentials of my approach.
% I choose the state-of-the-are PRI-NLM3D \cite{manjon2012new} by Manj{\'o}n \textit{et al.} for comparison because the source codes are available publicly.
In this section, I will illustrate some examples that will assess my 3D medical denoising method for 3D CT data. Comparison will be made  against \ths{the state-of-the-art technique:} PRI-NLM3D \cite{manjon2012new} by Manj{\'o}n \textit{et al.} because the source codes are available publicly.

All tests in this section were processed in the following manner: All $10$ slices were involved in the denoised slice. The similar 3D block size used for block matching was $7 \times 7 \times 5$ and was not changed for various tests. I obtained a locally consistent solution by allowing 3D patches to overlap, where the overlapped regions $v$ were $5$ voxels in each direction. \ths{Further}, for each reference 3D patch, I extract $4$ most similar 3D patches used in whole 3D data using the proposed 3D block matching algorithm.

% To evaluate the performance of my approach, I conducted tests on the data sets LIDC-IDRI \cite{website:LIDCIDRI} where the size of each slice of the CT slices are $512 \times 512$ pixels.


% To evaluate the performance of the proposed method, I consider two different sets of experiments. As shown in the first row of \scc{what happen to the caption? I can't figure out why I have the extra period.}


\begin{figure}[t]
 \centering

\includegraphics[height=5cm]{Pics/GT1}

% \vspace{10pt}
\includegraphics[height=5cm]{Pics/Noisy1}

% \vspace{10pt}
%\includegraphics[height=3cm]{Pics/NLM3D_3D1}}}
\includegraphics[height=5cm]{Pics/DMC1}

\caption{\small{Experiment 1 (3D display). (a) real 3D CT data; (b) noisy 3D CT data; (c) the 3D result of my proposed denoising method.}}
\label{nafiss:Ex1}
\end{figure}

\begin{figure}[t!]
 \centering
\includegraphics[height=4cm]{Pics/GT2}
\includegraphics[height=4cm]{Pics/Noisy2}

\includegraphics[height=4.15cm]{Pics/NLM3D5-5}
\includegraphics[height=4cm]{Pics/DMC2}


\caption{\small{Experiment 2: (PSNR in brackets). (a) real CT data; (b) noisy CT data; (c) PRI-NLM3D \cite{manjon2012new} [25.28 dB]; (d) the proposed denoising method [29.16 dB].}}
\label{nafiss:Ex2}
% \end{center}
\end{figure}

I first generate synthetic noisy 3D CT data and then apply denoising method to the degraded 3D CT data. The results are compared to the ground truth (the original images).
%  and results generated from other state-of-the-art technique \cite{pizurica2003versatile}. 


Fig. \ref{nafiss:Ex1} shows the result of the my 3D medical denoising with a 3D perspective. In this figure, I decided to show only a part of the CT images because the inside details of the lung are  more important than the tissue around it. Figs. \ref{nafiss:Ex1}(a), \ref{nafiss:Ex1}(b) are the real and the noisy CT image, respectively. Fig. \ref{nafiss:Ex1}(c) shows the result of 3D medical denoising where I used the voxels of the denoised 3D data.

As PRI-NLM3D \cite{manjon2012new} can not remove the mixed noise, for fair of comparison I apply it on the 3D noisy data after removing Impulsive noise.

In Fig. \ref{nafiss:Ex2}, I show the PSNR result and a clear visual comparison on the CT Lung slices. The original CT slice is \ths{corrupted by a mixture of Poisson noise, Gaussian white noise, impulsive noise with significant noise level (variance of Gaussiance noise = $0.02$ and {noise density} of impulsive noise = $0.01$)}.
% of mean zero and variance $0.02$, and Impulsive noise of the noise density $0.01$. 
As shown in \ths{the} figure, PRI-NLM3D \cite{manjon2012new} removes the critical information at edge areas, while my proposed denoising method performs remarkably well for the detail structures and is free of these artifacts. To 

To quantify my denoising performance, I used the Peak Signal to Noise Ratio (PSNR) measure between the ground truth and denoised CT slice.
% \begin{equation}
%  PSNR = 10\ \ log_{10}(255^2/Mean\ \ Square \ \ Error) [dB].
% \end{equation}


% I also show the PSNR result and a clear visual comparison on the Lung CT slices in Fig.~\ref{nafiss:Ex2}.



\subsubsection{Evaluation on Ultrasound}
\ths{To evaluate the performance of the proposed methods}, I now present some experimental results obtained by applying the proposed methods on some ultrasound images.
% consider in two separated subsections with two different sets of experiments. 
% I utilize lung test in Section \ref{Ex:synthetic} to compare the performance of my proposed method with the state-of-the-art methods 
% \ths{In Section \ref{Ex:synthetic}, 
% I will first generate synthetic noisy slices and then apply denoising methods to the degraded slices. I will then compare the results to the ground truth (the original slices) and results generated from other state-of-the-art techniques
% \cite{buades2005non,pizurica2006review,bao2003noise}. }
% \ths{Moreover},
In this section, I will illustrate some examples that will assess my denoising methods for real ultrasound images. Comparison will be made  against \ths{the state-of-the-art technique:} the \ths{wavelet} domain image denoising algorithm \cite{pizurica2006review}.
\begin{landscape}
\begin{table}[b]
\renewcommand{\arraystretch}{1.5}
\caption{  {Time comparison for using various matrix completion}}
\label{table_example}
\centering
\begin{tabular}{c||c|c|c}  
%    \hline
%   \textbf{\scriptsize{Galleon Sequence}} 
& \textbf{\scriptsize{Algorithm }} & \textbf{\scriptsize{Algorithm }}&\textbf{\scriptsize{Denoising method }}  \\
& \textbf{\scriptsize{ using Dense SCoBeP and matrix completion}}&\textbf{\scriptsize{ using Overlapped SCoBeP matrix completion}} & \textbf{\scriptsize{using OptSpace \cite{keshavan2010matrix}}}  \\
  \hline
  \hline
%   \multirow{2}{*}
%     \textbf{\scriptsize{PSNR}  } 	& 21.83 &  21.65 \\ \hline
	\textbf{\scriptsize{Time} $(seconds)$}	& 410 & 120 & 1398\\

%   \hline
\end{tabular}
\label{nafiss:comparetime}
\end{table}
\end{landscape}

I also replaced my proposed decomposition matrix completion with OptSpace \cite{keshavan2010matrix} to compare the result and time consumption (Table \ref{nafiss:comparetime}). It can be seen that my methods \ths{perform notably} faster than OptSpace \cite{keshavan2010matrix}.

% \subsection{Evaluation On Synthetic Slices}\label{Ex:synthetic}
% To evaluate the performance of my approach, I conducted tests on the data sets LIDC-IDRI \cite{website:LIDCIDRI} where the size of each slice of the CT slices are $512 \times 512$ pixels.
All tests in this section were processed in the following manner: All $30$ images were involved in the denoised image. The similar block size used for block matching was $63 \times 63$ and was not changed for various tests. I obtained a locally consistent solution by allowing patches to overlap in denoising algorithm using Overlapped SCoBeP matrix completion, where the overlapped regions ($v$) were $5$ pixels in each direction. \ths{Further}, for each reference patch, I extract $3$ most similar patches used in each image using SCoBeP.

In this work, I apply my proposed methods without any changes or generating noisy images. Note that since there are no published methods that perform denoising on such general images, I choose the wavelet domain image denoising algorithm \cite{pizurica2006review} for comparison, because their source code is available. 
%In order to apply my method directly to the MR slices, 
\ths{As for the non-synthetic case, while 
I do not have the ground truth and thus cannot evaluate the the methods quantitatively using PSNR,} the visual comparison \ths{illustrates the robustness of} my proposed methods when \ths{it is applied directly to real} images. 
% Note that I used the same images number, block size, overlapped region, and extracted patches number \ths{for the non-synthetic experiment just as the synthetic case}.

% \comm{Check that your upper case convention is consistent}
% In Fig. \ref{nafiss:denoising_g_02_I_01}, I show the PSNR result and a clear visual comparison on the CT slices. The original CT slice is \ths{corrupted by 
% significant mixed noise level with 
% a mixture of Poisson noise, Gaussian white noise, impulsive noise with significant noise level (variance of Gaussiance noise = $0.02$ and \scc{how do you define noise density?}{noise density} of impulsive noise = $0.01$)}.
% of mean zero and variance $0.02$, and Impulsive noise of the noise density $0.01$. 
As shown in \ths{the} Figures \ref{nafiss:Breast} and \ref{nafiss:Hepatit}, wavelet domain image denoising algorithm \cite{pizurica2006review} generates severe artifacts at edge areas, while my proposed denoising methods perform remarkably well for the detail structures and are free of these artifacts.

% To quantify my denoising performance, I used the Peak Signal to Noise Ratio (PSNR) measure between the ground truth and denoised CT slice:
% \begin{equation}
%  PSNR = 10\ \ log_{10}(255^2/Mean\ \ Square \ \ Error) [dB].
% \end{equation}


% In Table \ref{nafiss:Impulsivenoise}, I present the PSNR results of the proposed denoising algorithm for a lung CT slices; where impulsive noise is changing. This table shows how my algorithm is robust in denoising of the corrupted slices by serious impulsive noise.
% In graph \ref{nafiss:plotincreeseGuas}, I compare my denoising method with adaptive multiscale
%  image denoising algorithm \cite{bao2003noise}, wavelet domain image denoising algorithm \cite{pizurica2006review}, and non-local means algorithm \cite{buades2005non}, which are among the state-of-the-art in medical image denoising.


% In this comparison, I apply my denoising method on lung slices which I changed the impulsive noise and kept the Poisson and Gaussian noise constant for all methods. My proposed method surpasses the other methods \ths{with} a significant margin for all additive Impulsive Noise.




% \begin{table}[h]
% \caption{An Example of a Table}
% \label{table_example}
% \begin{center}
% \begin{tabular}{|c||c|}
% \hline
% One & Two\\
% \hline
% Three & Four\\
% \hline
% \end{tabular}
% \end{center}
% \end{table}


%    \begin{figure}[thpb]
%       \centering
%       \framebox{\parbox{3in}{We suggest that you use a text box to insert a graphic (which is ideally a 300 dpi TIFF or EPS file, with all fonts embedded) because, in an document, this method is somewhat more stable than directly inserting a picture.
% }}
%       %\includegraphics[scale=1.0]{figurefile}
%       \caption{Inductance of oscillation winding on amorphous
%        magnetic core versus DC bias magnetic field}
%       \label{figurelabel}
%    \end{figure}
   


\begin{figure}[t]
 \centering
\includegraphics[width=6cm]{Pics/Breast_Noisy}
\includegraphics[width=6cm]{Pics/Breast_Sanja}


\includegraphics[width=6cm]{Pics/Breast_Dense}
\includegraphics[width=6cm]{Pics/Breast_OverLap}

\caption{ {\ths{Non-synthetic (real)} experiment. (a) real ultrasound image; (b) wavelet domain image denoising algorithm \cite{pizurica2006review}; (c) the proposed denoising Algorithm using Dense SCoBeP and matrix completion; (d) the proposed denoising Algorithm using Overlapped
SCoBeP matrix completion.}}
\label{nafiss:Breast}
% \end{center}
\end{figure}








% \comm{use non-synthetic experiment instead of real experiment}
% \subsection{Evaluation On Non-Synthetic Ultrasound Images}\label{Ex:real}



\begin{figure}[htb]
 \centering
{\includegraphics[width=5cm]{Pics/Hepatit_Noisy}}
{\includegraphics[width=5cm]{Pics/Hepatit_Sanja}}


 {\includegraphics[width=5cm]{Pics/Hepatit_Dense}}
 {\includegraphics[width=5cm]{Pics/Hepatit_OverLap}}

\caption{ {\ths{Non-synthetic (real)} experiment. (a) real ultrasound image; (b) wavelet domain image denoising algorithm \cite{pizurica2006review}; (c) the proposed denoising Algorithm using Dense SCoBeP and matrix completion; (d) the proposed denoising Algorithm using Overlapped
SCoBeP matrix completion.}}
\label{nafiss:Hepatit}
% \end{center}
\end{figure}


\chapter{CONCLUSION}\label{conclusion}
This work explored several important aspect of image and video enhancment:
\begin{enumerate}
\item In conclusion, I have proposed two novel and efficient super resolution methods based on SCoBeP \cite{barzigar2012scobep} and Nonlocal-Means (NLM) techniques, which finds corresponding patches using sparse coding and demonstrates competitive results in both the synthetic and the real sequences. My techniques perform super resolution by first running sparse coding over an overcomplete dictionary constructed from the LR frames to gather possible match candidates. Belief propagation is then applied to eliminate bad candidates and to select optimum matches. Finally, in the SCoBeP-NLM, the NLM approach exploits similarity in patches around candidate pixels to average out the noise among similar patches. {{While the algorithm performs favorably comparing with other recent approaches as illustrated in the experimental results, the algorithm is quite complex and I realized that the source of most computation is originated from the NLM component. As SCoBeP has naturally identified pixels that are most likely to be relevant to a target pixel and also output the corresponding ``weight'' of the relevant pixels. This suggested us that NLM is probably not essential in my SCoBeP based SR algorithm. Thus, I have also implemented a  SCoBeP based SR algorithm, SCoBeP-SR, where ``mixing'' weights and candidates are extracted from the SCoBeP step only.}}

I conducted experiments on both the synthetic and the real video sequences, where my approaches work well for both types of sequences demonstrating the effectiveness and robustness of my approaches. Furthermore, \replace{unlike many existing}{since super resolution is usually tackled using an image registration method, most of the} 
super resolution \replace{approaches targeting to}{effort has been aimed at providing registered} LR frames \ths{that have been pre-registered} manually \cite{chan2008evaluation} or \replace{have assumed a stationary}{assuming a fixed} camera \cite{zhang2010non,protter2009super}\replace{, the proposed method can handle a sequence captured with a moving camera and do not require preprocessing of the sequence.}{.} 
% \delete{As demonstrated from my experimental results, my proposed method does not suffer from these limitations. }
% {{Performance analysis of super-resolution algorithm remains an interesting area of work, particularly in the scene and camera with the small and large motions. Some results already exist which support these motions, but these results need to be expanded and studied further.}}

{{ As SCoBeP provides decent results in images with \ths{both} significantly and slightly \replace{varying}{different} viewpoints \cite{barzigar2012scobep,roozgard2012medical}, hence, it \replace{will be useful to a wide range of applications such as}{could be very accurate to use in} de-interlacing, surveillance application and medical image super resolution. As for \replace{future}{further} work, I plan to extend my approaches to these areas.}}

% \section{Conclusion}\label{nafiss:conclusion}

\item In addition, I have proposed a novel and efficient denoisinng method using block matching filtering and matrix compleition. A key idea of \cite{ma2014decomposition} is to divide and conquer. The input matrix is partitioned into clusters, and then each cluster is filled separately. A dependency scanning step  estimates the lowest possible rank of each cluster by identifying independent rows. The unknown elements of these independent rows can then be filled arbitrarily without increasing the rank of the cluster.  The remaining unknown elements of the clusters are filled by the dependency relationship obtained earlier. Finally, the "off-diagonal" elements are filled to ensure the entire matrix has the lowest possible rank.

I proposed a block-based video denoising method using the decomposition approach \cite{ma2014decomposition}, in which I keep only reliable pixels and eliminate all unreliable pixels. My denoising method can remove the serious mixed noise from video sequence, while most of the existing methods have been limited to one specific type of noise. 
Quantitative and qualitative experiments with video sequences corrupted by mixed noise have shown that the proposed algorithm outperforms the state-of-the-art methods for the denoising tasks. 
\end{enumerate}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% BIBLIOGRAPHY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{
\singlespacing

\bibliographystyle{IEEEtran}
% \bibliographystyle{plain}
\bibliography{refs}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% DEDICATION PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\newpage
\newpage
\pagenumbering{roman}

\thispagestyle{empty}
{\singlespacing
\begin{center}
{
\par
\vspace{1.2in}
%\large
DEDICATION
\par
\vspace{0.17in}
to
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
My parents and Amin
\par
\vspace{0.17in}
% Luis Eduardo Martinez Villarraga, and
\par
\vspace{0.17in}
% Esperanza Pedroza Paipa
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
For
\par
\vspace{0.17in}
Encouraging me to follow my dreams
\par
\vfill
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
}
\end{center}
}

\end{document}
