
\chapter{استفاده از تجزيه ماتریس در مواجهه با اشیاء متحرک}\label{Chap:QR}
\begin{comment}
در اين فصل بايد مقالات زير را توضيح دهم:
\begin{itemize}
\item \LRE{\lr{\citealp*{Fathy07abackground}}}
\item \LRE{\lr{\citealp*{Amintoosi07icassp}}}
\item \LRE{\lr{\citealp*{Amintoosi07icics}}}
\item \citealp*{Amintoosi87estefadeh}
\item \LRE{\lr{\citealp*{Fathy08outlier}}}
\end{itemize}
\end{comment}
همانگونه که در فصول قبل مشاهده شد، یکی از مشکلات حوزۀ وضوح برتر مواجهه با مقادیر برون هشته است که تکنیک های های معدودی را می توان یافت که بتوانند با وجود آنها به خوبی عمل نمایند. نویز، زووم و اشیاء متحرک در فریمها جزو این مقادیر برون هشته محسوب میشوند. 

به صورت کلی در شیوۀ پیشنهادی فریمهایی از تصاویر ورودی که حاوی اشیائی به جز زمینه میباشند، فیلتر شده و فقط فریمهای زمینه به مرحلۀ بازسازی داده می شوند. شناسائی این فریمها بر اساس شیوهٔ نوینی در مدلسازی زمینه بر اساس تجزیهٔ \lr{QR} ماتریس‌ها می‌باشد که توسط نویسندگان ارائه شده است \citep{Amintoosi07icassp,Amintoosi07icics}.  وجود جابجائی و تفاوتهای تصاویر با وضوح پایین که جزولاینفک مسائل وضوح برترِ شامل چندین تصویر ورودی می باشند، به همراه چگونگی لحاظ کردن راهکار پیشنهادی در فرمولبندی \SR از مواردی هستند که در این فصل به آنها پرداخته خواهد شد
\footnote{مطالب این بخش در قالب مقالات \cite{Amintoosi07icassp,Amintoosi07icics,Amintoosi87estefadeh} و \cite{Fathy07abackground,Fathy08outlier}  منتشر شده است.}.

ابتدا مروری کوتاه به تجزیۀ مقادیر منفرد و تجزیۀ \lr{QR} داشته و سپس نحوۀ استفاده از آن در مسئلۀ وضوح برتر را خواهیم دید.  آخرین بخش به 
نتیجه‌گیری و بیان مزایا و معایب شیوهٔ پیشنهادی اختصاص یافته است.

\section{تجزیهٔ \texorpdfstring{\lr{QR}}{QR}}

شیوه های تجزیۀ مقادیر منفرد\lr{(SVD\LTRfootnote{Singular Value Decomposition})} و تجزیۀ \lr{QR} توسط محققین مختلف به منظور کاهش تعداد قوانین یک پایگاه داده بکار گرفته شده‌اند\citep{Kaynak02complexity,Setnes01rule}. نکتۀ اصلی در استفاده از \lr{SVD} برای کاهش پیچیدگی، آن است که با استفاده از مقادیر منفرد می توان یک سیستم را تجزیه نمود و میزان اهمیت هر یک از اجزاء تجزیه شده را مشخص نمود. 
تجزیۀ مقادیر منفرد یک ماتریس  $P$، را می توان به صورت  $P=UDV^T$ نوشت که در آن $U\in \mathbb{R}^{N\times N}$  و  $V\in \mathbb{R}^{M\times M}$ ماتریس های متعامد  و $D=diag(\sigma_1,\dots,\sigma_M)\in \mathbb{R}^{N\times M}$  یک ماتریس قطری است که درآن $\sigma_1\geq\dots\geq\sigma_M\geq0$ . عناصر روی قطر ماتریس $D$ مقادیر منفرد ماتریس $P$ نامیده می‌شوند.  تجزیۀ QR ماتریس $P$ به صورت  $P\Pi=QR$ نمایش داده میشود که درآن $\Pi\in R^{M\times M}$  یک ماتریس جایگشتی\LTRfootnote{Permutation matrix}  است و ستونهای $Q\in R^{M\times M}$  متعامد یکِّه\LTRfootnote{Orthonormal}  بوده و $R\in R^{M\times M}$  یک ماتریس بالامثلثی  است. قدرمطلق مقادیر روی قطر اصلی$R$ که نزولی هستند، مقادیر \lr{R}   نامیده شده و نشان داده شده است که مقادیر منفرد ماتریس را دنبال می کنند \citep{Setnes01rule}. 
از دیدگاه جبرخطی یک مجموعه از ستونهای یک ماتریس که نتوان هیچ یک از آنها را به صورت ترکیبی از سایرین نوشت، مستقل  از هم محسوب می شوند.  ارتباط استقلال و مقادیر منفرد آن است که اگر بتوان یک ستون را به صورت ترکیبی از سایر ستونها داشت، مقدار منفرد متناظر با آن در تجزیۀ \lr{SVD} صفر خواهد بود. حال اگر ستونی مانند $X$ داشته باشیم که ترکیب دقیقی از سایر ستونها نباشد اما بتوان آنرا به صورت زیر نوشت:
 \[X=\Sigma_iW_iV_i+N, j=1,\dots,n \]
که در آن  $V_i$ نمایانگر ستون $j$ام و $W$ها ضرایب ترکیب و $N$ معرف نویز بوده و میانگین نویز خیلی کمتر از میانگین $X$ باشد، مقدار منفرد متناظر با این ستون بسیار کوچک خواهد بود. موارد فوق دربارۀ مقادیر \lr{R} از تجزیۀ \lr{QR} نیز صادق است.
یک شیوه برای استخراج مهمترین ستونهای ماتریس $P$ را به صورت خلاصه می توان به فرم زیر داشت\citep{Golub96book}:
\begin{enumerate}
\item	تخمین \lr{r}، رتبۀ موثر\LTRfootnote{Effictive rank}  ماتریس $P$.
\item	 محاسبه ماتریس $\Pi$ به نحوی که ستونهای ماتریس   $P_n\in \mathbb{R}^{M\times n}$ در  $P\Pi =\big[ P_n,
P_{N-n}\big]$ بقدر کافی مستقل باشند.
\end{enumerate}
 از نقطه نظر عملیاتی و پیاده سازی، مزیت تجزیۀ \lr{QR} نسبت به \lr{SVD}  آن است که اولاً برنامه هایی همچون \lr{MATLAB} تجزیۀ \lr{QR} را نسبت به تجزیۀ \lr{SVD} با سرعت بیشتری انجام می‌دهند و ثانیاً در پیاده‌سازیهای معمول تجزیۀ \lr{SVD} برخلاف \lr{QR}، مشخص  نمی‌شود که هر مقدار منفرد مربوط به کدام ستون است.

 رشته تصاویر ویدیوئی را درنظر بگیرید که از یک صحنه ایستا با وجود اشیاء متحرک در چند فریم اخذ شده باشند. فرض کنید ماتریس $P$ از کنار هم قرار دادن ستونی شدۀ فریمها ایجاد شده باشد؛ اگر حالتِ ایده‌آل بدون نویز و فرض ثبات کامل دوربین را داشته باشیم، مقادیر $R$ متناظر با ستونهایی که صرفاً شامل زمینه و اشیاء ثابت هستند – به جز یکی – برابر صفر خواهد بود. در \citep{Amintoosi07icassp,Amintoosi07icics} حالتی را که دوربین ثابت بوده و فقط نویز وجود داشته است را بررسی نموده و نشان داده‌ایم که تحت شرایطی مدلسازی زمینه با استفاده از تجزیۀ \lr{QR} از الگوریتم های معمول مدلسازی زمینه کاراتر است\footnote{به \citet{Amintoosi07icics} مراجعه شود}. هدف در بخش بعد ذکر نحوۀ بکارگیری این ایده در وضوح برتر می‌باشد.

\section{شیوهٔ پیشنهادی}
چارچوب کلی روش پیشنهادی در شکل \ref{fig:SR_SchematicDiagram_BG} آمده است. نگاهی دوباره به شکل \ref{fig:SR_SchematicDiagram}  و شکل \ref{fig:SR_SchematicDiagram_BG} روشن می‌سازد که در شیوۀ پیشنهادی یک مرحلۀ فیلترکردن تصاویر ورودی اضافه شده است. مرحلۀ بازسازی با استفاده از خروجی مرحلۀ قبل و با استفاده از همان پارامترهای مرحلۀ ثبت تصویر انجام خواهد شد. 


\begin{figure}
\centering{\includegraphics[width=.9\textwidth]{Images_QR/SR2.pdf}}
\caption[اضافه شدن مرحلۀ شناسائی فریم‌های زمینه]{چارچوب کلی شیوۀ پیشنهادی- اضافه شدن مرحلۀ شناسائی فریم‌های زمینه به چارچوب نشان داده شده در شکل \ref{fig:SR_SchematicDiagram} }
\label{fig:SR_SchematicDiagram_BG}
\end{figure}

در مسائل وضوح برتر، جابجائی های تصاویر ورودی جزو لاینفک سیستم است. با فرض وجود حرکت دوربین استفاده از شیوه‌های معمول مدلسازی زمینه کارا نخواهند بود.  برای رفع این مشکل کافیست عمل شناسائی فریم‌های زمینه به بعد از مرحلۀ ثبت تصویر موکول شود. لیکن کناره‌های تصاویر حاصل از عملیات ثبت تصویر به میزان جابجائی  هر یک نسبت به فریم مرجع، با صفر پر شده و سیاه دیده می‌شوند. این کناره‌ها مانعی جدی برای هر روش شناسائی زمینه خواهند بود. راه حل ساده‌ای که برای این منظور درنظر گرفته شده است، حذف این کناره‌ها از تمام فریم‌ها –موقتاً در این مرحله- می‌باشد. درواقع باید مختصات زیرماتریسی از هر تصویر (که آنها را $(x_1,y_1)$ و $(x_2,y_2)$ می‌نامیم) پیدا شود که همگی نمایش‌دهندۀ یک ناحیه از صحنه باشند. فرض کنید  $(\Delta x_k,\Delta y_k)$  میزان جابجائی برای فریم $k$ام باشد که حاصل مرحلۀ ثبت تصویر بوده است، مقادیر مختصات $y_1$ و $y_2$ را به صورت زیر بدست می آوریم: 
\begin{eqnarray}\label{subImageCoord1}
    y_1=Max\{1,\mathop{Max}_{k}\{ \Delta y_k\}\}\\
    y_2=M+Min\{0,\mathop{Min}_{k}\{ \Delta y_k\}\}
\end{eqnarray}
مختصات $x_1$ و $x_2$  هم به  صورت مشابه بدست می‌آیند.

برای بکاربردن یک روش بازسازی باید زیرماتریسهای تصحیح‌حرکت شده از تصاویر ورودی  که نمایشگر یک ناحیه از صحنه هستند مورد استفاده قرار گیرند.
فرض کنید $F'_k$  (با اندازه $[M^2\times M^2]$ ) عملگر حرکت هندسی بین $k$امین تصویر باوضوح پایین ورودی و اولین تصویر ورودی باشد. فرم تصحیح حرکت شده $k$امین تصویر را که  $\underline{Y'}_k$ می‌نامیم به صورت زیر بدست می‌آید:
\begin{equation}
 \underline{Y'}_k=\underline{F'}_k\underline{Y}_k
\end{equation}
فرض کنید $Y'_k$ (با اندازه $[M\times M]$ ) فرم ماتریسی  $\underline{Y'}_k$ باشد، برای نمایش زیر ماتریسی از آن از تعریف زیرماتریس در جبرخطی استفاده خواهیم کرد:
\begin{definition}
(زیرماتریس): فرض کنید $A$ یک ماتریس  $M\times N$، و $I\subseteq \{1,\ldots,M\}$ و  $J\subseteq \{1,\ldots,N\}$  دو مجموعه $m$ و $n$ عنصری باشند، $A(I|J)$  را زیر ماتریسی از $A$ می نامیم که از حذف سطرها و ستونهایی از A حاصل می شود که اندیس آنها در $I$ و $J$ آمده است.
\end{definition}
تذکر1: نماد فوق را نباید با نماد احتمال شرطی اشتباه گرفت.\\
تذکر2: اگر $I$ تهی باشد هیچ یک از سطرهای $A$ حذف نخواهند شد. به همین ترتیب اگر $J$ تهی باشد، هیچ یک از ستونهای $A$ حذف نمی‌شوند.

حال زیرماتریسی از فرم تصحیح حرکت شدۀ هر فریم که در همه فریمها مشترک است را می‌توان به صورت  $Y'_k(I|J)$ نشان داد که در آن:
\[I= \{1,\ldots,y_1-1,y_2+1,\ldots,M\}\]
\[J=\{1,\ldots,x_1-1,x_2+1,\ldots,N\}\]
تجزیه \lr{QR} بایستی روی ماتریس   $\underline{Y'}$ اعمال شود:
\[\underline{Y'}=\big[\underline{Y'}_1(I|J),\underline{Y'}_2(I|J),\ldots,\underline{Y'}_N(I|J)\big]\]
 اما از آنجا که تجزیۀ \lr{QR} به نُرم ستونهای ماتریس حساس است، به جای $\underline{Y'}$  از گرادیان ماتریس در راستای محور \lr{x}ها استفاده می‌کنیم:
\begin{equation}
\underline{Y''}= \frac{\partial {\underline{Y'}}}{\partial x}
\end{equation}
برای تخمین رتبۀ مؤثر ماتریس  $\underline{Y''}$ از این فرض استفاده می کنیم که حداقل در $\beta$ درصد فریمها زمینه کاملاً قابل رؤیت می باشد. لذا  $(1-\beta)N$ میتواند یک تخمین خوب برای رتبۀ مؤثر باشد. اگر $\{f_1,\ldots,f_N \}$ شماره فریهمای حاصل از ماتریس   $\Pi$  از تجزیۀ \lr{QR} ماتریس  $\underline{Y''}$ باشد، اولین   $(1-\beta)N$ فریم را بعنوان فریمهای حاوی مقادیر برون هشته حذف می کنیم. براساس ماتریس موردتجزیه،  $\beta$ و مجموعه اندیسهای اخیر عملگرهای \lr{OFI(Outlier Frame Indices)} و \lr{NOFI(Non Outlier Frame Indices)} را به صورت زیر تعریف می کنیم:
\begin{definition}
(عملگرهای \lr{OFI} و \lr{NOFI}): به فرض $P\in \mathbb{R}^{M\times N}$ و  $\beta$ داده شده اند و  $\{f_1,\ldots,f_N \}$ نشان دهنده شماره ستونهای $P$ براساس ماتریس  $\Pi$  از تجزیه \lr{QR} ماتریس $P$ است و $M>N$، عملگرهای \lr{OFI} و \lr{NOFI} به صورت زیر درنظرگرفته می شوند:
\begin{eqnarray*}
OFI(P,\beta)=\{f_1,\ldots,f_{(1-\beta)N} \}\\
NOFI(P,\beta)=\{f_{(1-\beta)N+1},f_{(1-\beta)N+2},\ldots,f_{N} \}
\end{eqnarray*}
\end{definition}

محدود ساختن  $\underline{Y}$ به ستونهایی از آن که توسط مجموعه  $NOFI(\underline{Y''},\beta)$ مشخص می شوند به ما مجموعه ای از فریم ها را خواهد داد که هیچ فریم آن دارای مقادیر برون هشته نبوده و برای منظور ما در وضوح برتر مناسب می باشد. به عبارت دیگر  $\underline{Y}\big(
\varnothing |OFI(\underline{Y''},\beta) \big)$ ستونهایی از  $\underline{Y}$ را حذف می کند که اندیس آنها در $OFI(\underline{Y''},\beta)$  آمده است. 
به این ترتیب مسئلۀ وضوح برتر اولیه %(رابطۀ ) 
به صورت زیر در خواهد آمد:
\begin{equation}
\underline{\hat{Z}}=\mathop{\textrm{Arg\,Min}}_{\underline{Z}}
\Big[\sum_{k=1}^{N-n}|| DG_k \underline{Z}-\underline{W}_k ||_p^p
\Big]
\end{equation}
که در آن:
\begin{eqnarray*}
 \underline{W} =  \underline{Y}\big( \emptyset
|OFI(\underline{Y''},\beta) \big),\\
G=F\big( \emptyset |\emptyset|OFI(\underline{Y''},\beta) \big),\\
n=(1-\beta)N
\end{eqnarray*}
 در فرمول فوق $\underline{W}$ و $G$ بیانگر حذف فریمهایی از مجموعه دادگان هستند که اندیس آنها در $OFI(\underline{Y''},\beta)$ آمده است. در شکل \ref{fig:SR_SchematicDiagram_BG} چارچوب کلی کار را پس از اضافه کردن شیوۀ پیشنهادی بین مراحل ثبت تصویر و بازسازی مشاهده کردیم؛ همانگونه که از شکل مذکور و $G=F\big( \emptyset |\emptyset|OFI(\underline{Y''},\beta) \big)$  مشخص است، به مرحلۀ ثبت تصویر جداگانه ای برای بازسازی نیاز نیست. 

\section{نتایج پیاده سازی}
در آزمایشات انجام شده از رشته تصاویر ویدیوئی \lr{Alpaca} استفاده شده است که از سایت پروفسور میلانفر  قابل برداشت می باشد. در این دنباله از تصاویر دو نوع حرکت مشاهده میشود: اولین نوع حرکت ناشی از حرکت دست در حین فیلمبرداری است؛ حرکت دوم ناشی از انتقال مجسمۀ آلپاکا در 10 فریم از سمت راست صحنه به سمت چپ است. دنباله تصاویر اصلی شامل 55 فریم می باشد که در اینجا فقط از 15 فریم آن (فریمهای 38 تا 46 و 50 تا 55) که در طی آنها مجسمه حرکت داشته است استفاده شده است. مقدار پارامتر  $\beta$ برابر با $\frac{1}{3}$ درنظر گرفته شده است. شکل \ref{fig:QR_Order} این ۱۵ فریم را به ترتیب حاصل از ماتریس $\Pi$ نشان می‌دهد (از بالا به پایین و از چپ به راست). شمارهٔ روی هر تصویر بیانگر ترتیب آن در دنبالهٔ اصلی می‌باشد. همانگونه که مشاهده می‌شود تصاویر سطر آخر مربوط به زمینه هستند. در عملیت بازسازی فقط این فریم‌ها مورد استفاده قرار می‌گیرند.

\begin{figure}[t]
\centering
   \includegraphics[width=1\linewidth]{Images_QR/QRorder.pdf}
   \caption[ترتیب فریم‌ها بر اساس ماتریس $\Pi$ حاصل از تجزیهٔ \lr{QR}]{ترتیب فریم‌ها بر اساس ماتریس $\Pi$ حاصل از تجزیهٔ \lr{QR}، از بالا به پایین و از چپ به راست. شمارهٔ روی هر تصویر بیانگر ترتیب آن در دنبالهٔ اصلی می‌باشد.}
   \label{fig:QR_Order}
\end{figure}

شکل \ref{fig:QR} نتایج وضوح برتر با شیوۀ پیشنهادی و چندین روش دیگرِ وضوح برتر را نشان می دهد. برای مرحلۀ بازسازی در شیوهٔ پیشنهادی از روش درونیابی استفاده شده است. خروجی بهتر شیوۀ پیشنهادی از مقایسۀ بصری نتایج شکل \ref{fig:QR} بخوبی مشخص می باشد. به جز روش پیشنهادی و روش \lr{POCS}، سایر شیوه ها از ظهور اثرات شبح مانند ناشی از حرکت آلپاکا رنج می برند.

\begin{figure}[t]
\centering \subfigure[\lr{Nearest}]{\label{fig:QR:NN}\includegraphics[width=.4\textwidth]{Images_QR/Alpaca_NN.jpg}}
\centering 
\subfigure[\lr{Shift \& Add} \citep{Farsiu04fast}] {\label{fig:QR:Shift_and_Add}\includegraphics[width=.4\textwidth]{Images_QR/Alpaca_Shift_and_Add.jpg}}
\centering \subfigure[\lr{Median Shift \& Add}\citep{Farsiu05thesis}] {\label{fig:QR:Median_Shift_and_Add}\includegraphics[width=.4\textwidth]{Images_QR/Alpaca_Median_Shift_and_Add.jpg}}
\centering 
\subfigure[\lr{Shift \& Add + Bilateral}\citep{Farsiu05thesis}]{\label{fig:QR:Shift_and_Add_BTV} \includegraphics[width=.4\textwidth]{Images_QR/Alpaca_Shift_and_Add_BTV.jpg}}
\centering 
\subfigure[\lr{Normalized Convolution}\citep{Pham06robust}]{\label{fig:QR:NC} \includegraphics[width=.4\textwidth]{Images_QR/Alpaca_NC.jpg}}
\centering 
\subfigure[درونیابی]{\label{fig:QR:IN} \includegraphics[width=.4\textwidth]{Images_QR/Alpaca_IN.jpg}}
\centering 
\subfigure[\lr{POCS}]{\label{fig:QR:POCS} \includegraphics[width=.4\textwidth]{Images_QR/Alpaca_POCS.jpg}}
\centering 
\subfigure[شیوهٔ پیشنهادی]{\label{fig:QR:QR} \includegraphics[width=.4\textwidth]{Images_QR/Alpaca_QR.jpg}}
\caption{نتایج مقایسه‌ای شیوهٔ پیشنهادی و چند روش دیگر بر روی ۱۵ فریم انتخاب شده از دنباله تصاویر \lr{Alpaca}.} \label{fig:QR}
\end{figure}

\section{جمع‌بندی}
دراین فصل شیوۀ نوینی برای مسئلۀ وضوح برتر  در حضور اشیاء متحرک پیشنهاد شده است که مبتنی بر بکار گیری یک الگوریتم شناسائی فریم های زمینه قبل از مرحلۀ ثبت تصویر در تکنیکهای وضوح برتر می‌باشد. مرحلۀ بازسازی تصویر، صرفاً روی فریم های انتخاب شده در این قسمت اعمال می شود. نیازی به ثبت تصویر مجدد نبوده و پارامترهای بدست آمده قبل از مرحلۀ شناسائی فریم‌های زمینه مستقیماً در مرحلۀ بازسازی مورد استفاده قرار خواهند گرفت.

برای شناسائی فریم‌های زمینه از شیوۀ ارائه شده توسط نویسندگان استفاده شده است. نتایج آزمایشات انجام شده کارائی بیشتر شیوۀ پیشنهادی را در ایجاد تصویر باوضوح بالاتر  نسبت به شیوۀ معمولِ لحاظ کردن تمام فریم‌ها نشان داده است. 

حذف کل فریمِ شامل شیء متحرک در شیوۀ پیشنهادی، باعث حذف اطلاعات دیگری که می‌توانند در بازسازی مفید باشند نیز می‌شود. در مقالات منتشره، نگارندگان تجزیۀ\lr{QR} را روی بلوکهای کوچک اعمال نموده‌اند. اتخاذ چنین شیوه‌ای در مسئلۀ وضوح برتر می‌تواند موجب استفاده از اطلاعات بیشتر در مرحلۀ بازسازی گردد. 
