\begin{comment}
\chapter{تأملی بیشتر بر مفهوم «\res»}\label{Chap:Resolution}
%\section{تأملی بیشتر بر مفهوم «\res»}
    در مقدمه  از «\res» به عنوان تعداد پیکسل های تصویر یاد کردیم. اما خواهیم
     دید که نیاز به تعریف بهتری داریم. اگر تصویری داشته باشیم و ابعادش را با
 چهار بار تکرار هر پیکسل چهار برابر نماییم، آیا به \res بالاتری رسیده ایم؟ یا
 فرض کنید که یک فیلتر مات کننده را روی تصویر اعمال نموده ایم و تصویر حاصل با
                     همان اندازه ی تصویر اولیه است. آیا \res هر دو برابر است؟
\res یک تصویر را نمی توان به راحتی معادل با اندازه‌ی پیکسل یا با بالاترین فرکانس موجود در تصویر 
دانست (اضافه کردن نویزبه تصویر \res را افزایش نمی دهد ولی فرکانس را افزایش می دهد).
هم \res بودن دو تصویر به این معنی است که یکی از روی دیگری با استفاده از درونیابی 
قابل حصول است یا ویژگی های بارز در دو تصویر یکسانند \cite{Lin04fundamental}.
 «\res» چیزی فراتر از تعداد پیکسل های تصویر
   بایستی باشد. در واقع «\res» با میزان توانائی تشخیص جزئیات تصویر مرتبط است.
 موسسه ی بین المللی استانداردسازی (\lr{ISO}) روش دقیقی را برای اندازه گیری دقت یک
                                             دوربین دیجیتال معرفی نموده است.

      «\res» بصری با پرفرکانس ترین الگوی سیاه و سفید خطوط که این خطوط هنوز در
    تصویر با چشم قابل تمیز باشند اندازه گیری می شود. این معیار با واحد پهنای
  طول بر ارتفاع تصویر بیان می شود (\lr{LW/PH})\LTRfootnote{Line Widths per Picture Height (LW/PH)}.
 این استاندارد همچنین روشی برای
   محاسبه ی پاسخ فرکانس مکانی (\lr{SFR})\LTRfootnote{Spatial Frequency Response (SFR)} معرفی نموده است. 
پاسخ فرکانس مکانی درتصویربرداری دیجیتال معادل تابع انتقال مادولاسیون
 (\lr{MTF})\LTRfootnote{Modulation Transfer Function (MTF)} در سیستم های
   تصویربرداری آنالوگ است. این تابع تغییرات بین بیشترین و کمترین مقادیر قابل
  رویت را به عنوان تابعی از فرکانس مکانی (تعداد خطوط سیاه و سفید در میلیمتر)
     بدست می  دهد. این مقدار با استفاده از یک تصویر شامل لبه های سیاه و سفید
     اریب اندازه گیری شده و بر حسب فرکانس مکانی نسبی (متناسب با فرکانس نمونه
 برداری) پهنای خط بر ارتفاع تصویر یا دایره بر میلیمتر در سنسور تصویر بیان می
                                                                        شود.
     شکل \ref{fig:ISOResChart} نمودار \res که در استاندارد \lr{ISO} برای اندازه گیری \res دوربین های دیجیتال
 بکار می رود را نشان می‌دهد.


\begin{figure}[h]
\centerline{\includegraphics[width=.95\textwidth]{fig/ISOResChart}}
\centering         
\caption[نمودار \res که در استاندارد \lr{ISO} بکار می رود.]
{نمودار \res که در استاندارد \lr{ISO} برای اندازه گیری \res دوربین های دیجیتال بکار می رود.}
\label{fig:ISOResChart}
\end{figure}

\begin{definition} \res نوری، معیاری برای توانائی یک سیستم دوربین یا یک جزء از یک
   سیستم دوربین برای نمایش جزئیات است. \res تصویر اندازه ای برای میزان جزئیات
                                                   قابل دید در یک تصویر است.
\end{definition}
%Aliasing: مشکل «بدنمائی» تصویر به خاطر ناکافی بودن تعداد نقاط نمونه برداری
%  شده برای نمایش مناطق با فرکانس بالای صحنه می باشد و معمولاً خودش را به صورت
%          الگوهای مصنوعی یا لبه های دندانه ای نشان می دهد. نشان داده شده است
%\cite{Vandewalle06thesis} که اگر مشکل بدنمائی تصاویر ورودی خیلی حاد نباشد، می توان با
%    استفاده از نواحی بدون مشکل بدنمائی تصاویر، آنها را نسبت به یک تصویر مرجع
%                                                                 تنظیم نمود.
%روشهای مختلفی برای تنظیم در چنین حالتی ارائه شده اند که می تواند در
%   کاربردهای متنوعی از عکس های معمولی تا تصاویر ماهواره ای مورد استفاده قرار  گیرد.
%از آنجا که برای بیشتر اصطلاحاتی که در ادامه خواهند آمد، معادل فارسی خوب سراغ نداشتم، آنها را به همان فرم انگلیسی ذکر
%نموده‌ام. امیدوارم  که  تا زمان تکمیل پروژه، معادل فارسی مناسبی برای آنها پیدا نمایم.
%\item[\SR کور ]%(Blind superresolution) ]
%به حل مسئله‌ی \SR بدون دانستن \psf ،% Blind superresolution گفته می‌شود که یکی از مسائل چالش برانگیز در این حوزه است.
\end{comment}
\chapter{برخی اصطلاحات و مفاهیم مورد استفاده در رساله }\label{Chap:Definitions}
\section{اصطلاحات }

\begin{description}

\item[ \res نوری]، معیاری برای توانائی یک سیستم دوربین یا یک جزء از یک سیستم دوربین برای نمایش جزئیات است. \res تصویر اندازه‌ای برای میزان جزئیات قابل دید در یک تصویر است. هم \res بودن دو تصویر به این معنی است که یکی از روی دیگری با استفاده از درونیابی قابل حصول است یا ویژگی های بارز در دو تصویر یکسانند \citep{Lin04fundamental}.  «\res» چیزی فراتر از تعداد پیکسل های تصویر است. در واقع «\res» با میزان توانائی تشخیص جزئیات تصویر مرتبط است.
\item[مسئله‌ی معکوس(\lr{Inverse Problem})]:
به برآورد پارامترهای یک مدل از روی داده‌های مشاهده شده، که در بسیاری از علوم با آن مواجهیم، مسئله‌ی معکوس گفته می‌شود. 
%از زاویه‌ای دیگر یک مسئله‌ی معکوس را می‌توان به صورت زیر بیان نمود: 
مسائل معکوس عموماً \lr{ill-posed} هستند.
\item[\lr{ill-posed}]:
برای تعریف این دسته از مسائل ابتدا بایستی مسائل \lr{well-posed} را تعریف نماییم. بر اساس تعریف هادامارد یک مسئله 
در قالب مدل ریاضی یک پدیده‌ی فیزیکی، \lr{well-posed} خواهد بود هرگاه:
\begin{enumerate}
\item یک جواب برای آن وجود داشته باشد،
\item جواب منحصربفرد باشد و
\item در یک توپولوژی معقول، جواب به صورت پیوسته به داده بستگی داشته باشد.
\end{enumerate}
مسئله‌ای که \lr{well-posed } نباشد، \lr{ill-posed} نامیده می‌شود.
به عنوان مثال مسئله‌ی مستقیم معادله‌ی گرما با شرایط آغازین، یک مسئله‌ی \lr{well-posed} است ولی مسئله‌ی معکوس آن \lr{ill-posed} است.
\item[\lr{Regularization}]:
اگر مسئله \lr{well-posed} باشد، با احتمال زیاد می‌توان یک الگوریتم رایانه‌ای پایدار برای حل آن داشت. اما اگر مسئله \lr{well-posed}
نباشد برای حل عددی آن، مسئله نیاز به فرمولبندی  مجدد دارد. معمولاً این کار با لحاظ کردن فرضیات اضافی مانند \lr{smooth} بودن جواب
یا محدود کردن نُرم صورت می‌پذیرد. به این فرآیند \lr{regularization } گفته می‌شود.
\item[\lr{ill-conditioned}]:
حتی اگر یک مسئله \lr{well-posed} باشد، ممکن است \lr{ill-conditioned} باشد، به این معنی که یک خطای کوچک در داده‌ی ورودی ممکن است سبب
خطاهای بسیار بزرگتر در جوابها شود. یک مسئله‌ی \lr{ill-conditioned} با \lr{condition number} بزرگ مشخص می‌شود.
\item[\lr{Condition number}]:
در آنالیز عددی، \lr{condition number} یک مسئله، میزان \lr{amenability} آن به محاسبات رقومی می‌باشد. یک مسئله با \lr{condition number} کم،
\lr{well-conditioned }، و یک مسئله با \lr{condition number} زیاد، \lr{ill-conditioned} نامیده می‌شود. برای مثال \lr{condition number} مرتبط با
دستگاه معادلات خطی $Ax=b$،  حدی  (\lr{bound}) درباره‌ی اینکه پس  از تقریب زدن   جواب، $x$ چقدر غیردقیق است به ما خواهد داد.
به عبارت ساده‌تر \lr{condition number} تقریبی از تغییرات \lr{ $x$}بر حسب تغییرات  $b$ را بدست می‌دهد. لذا اگر \lr{condition number} بزرگ باشد،
یک خطای کوچک در $b$ منجر به یک خطای بزرگ در $x$ خواهد شد. \lr{condition number} به صورت دقیق‌تر با محاسبه‌ی ماکزیمم نرخ خطای نسبی 
در $x$ تقسیم بر خطای نسبی در $b$ تعریف می‌شود. 
%اگر $e$ خطای $b$ باشد، خطا در جوابِ $A^{-1}b$ عبارت خواهد بود از $A^{-1}e$.
%نرخ خطای نسبی در جواب به خطای نسبی در $b$ به صورت زیر خواهد بود:
%\[ \frac{\Vert A^{-1} e\Vert / \Vert A^{-1} b\Vert}{\Vert e\Vert / \Vert b\Vert} \]
%\item[Croos-validation]
\item[\lr{Overdetermined system}]:
یک دستگاه  معادلات خطی \lr{overdetermined} نامیده می‌شود، هرگاه تعداد معادلات از تعداد مجهولات بیشتر باشد. این حالت هنگامی اتفاق می‌افتد
که سیستم بیش از حد مقید (\lr{overconstrained}) شده باشد. یک شیوه‌ی حل معمول برای پیدا کردن یک جواب تقریبی چنین سیستمی، روش کمترین مربعات
(\lr{least squares}) است. 
%برای دستگاه $Ax=b$ فرمول کمترین  مربعات به صورت  $\hat{x}=(A^TA+\Gamma^T\Gamma)^{-1}A^Tb$ در واقع جوابی تقریبی برای
%$ min_x ||Ax-b|| $ می‌باشد. \\
یک دستگاه معادلات \lr{underdetermined} گفته می‌شود هرگاه تعداد مجهولات از تعداد معادلات بیشتر باشد.
\end{description}
\section{مدلهای حرکت دوبعدی}
در این رساله به دفعات از مدلهای حرکت اقلیدسی و پروجکتیو نام برده شد. بسیاری از اوقات حرکت بین دو تصویر از یک صحنه با یکی از مدلهای پارامتری ذکر شده در جدول \ref{tab:MotionModels} قابل مدل نمودن می‌باشد.  شکل \ref{fig:MotionModels} این مدلها را به صورت ملموس‌تری نشان می‌دهد\citep{Pham06thesis,Dubrofsky07mthesis}. 

\begin{table}[ht]
\caption{مدلهای تبدیل.}
\label{tab:MotionModels}
\centering
\begin{tabular}{|r|c|l|r|}
\hline نام مدل & درجه آزادی & تبدیل مختصات & توضیح \\ 
\hline انتقالی & ۲ & $\begin{aligned} x'=x+t_x \\ y'=y+t_y \end{aligned}$  &  انتقال دوبعدی\\ 
\hline اقلیدسی & ۳ & $\begin{aligned} x'=xcos\theta - ysin\theta+t_x \\ y'=xsin\theta+ycos\theta+t_y \end{aligned}$  &  انتقالی+دوران \\ 
\hline مشابهت & ۴ & $\begin{aligned} x'=sxcos\theta - sysin\theta+t_x \\ y'=sxsin\theta+sycos\theta+t_y  \end{aligned}$  & اقلیدسی+تغییرمقیاس \\ 
\hline آفین & ۶ & $\begin{aligned} x'=a_{11}x+a_{12}y+t_x \\ y'=a_{21}x+a_{22}y+t_y \end{aligned}$  & مشابهت+اریب‌شدگی \\ 
\hline  پروجکتیو & ۸ & $\begin{aligned} x'&=(m_1x+m_2y+m_3)/D \\ y'&=(m_4x+m_5y+m_6)/D \\ D&=m_7x+m_8y+1 \end{aligned}$  & آفین+\lr{keystone+chirping} \\ 
\hline  شارنوری & $\infty $ & $\begin{aligned} x'=x+v_x(x,y) \\ y'=y+v_y(x,y) \end{aligned}$  &  حرکت آزاد\\ 
\hline 
\end{tabular} 
\end{table}

\begin{figure}[t]
\centering 
\includegraphics[width=.8\textwidth]{fig/MotionModels.PNG}
\caption{نمایش مدلهای حرکت (تبدیل) }
\label{fig:MotionModels} %% label for entire figure
\end{figure}

\section{هوموگرافی}
یک هوموگرافی نقاط همگن در فضای دوبعدی را به نقاط همگن دیگری در فضای دوبعدی نگاشت می‌کند. 
 هوموگرافی تبدیلی برگشت‌پذیر از نقاط و خطوط در صفحهٔ پروجکتیو $P^2$ است. یک نقطهٔ $(x,y)$ در فضای دوبعدی در نمایش همگن بوسیلهٔ یک بردار $\mathbf{x}=(x_1,x_2,x_3)$ نمایش داده می‌شود که در آن $x=\frac{x_1}{x_3}$ و $y=\frac{x_1}{x_3}$.
یک نگاشت از $P^2$ به $P^2$ یک پورجکتیویتی است\citep{Hartley2004book} اگر و فقط اگر یک ماتریسِ$3\times3$ نامنفرد $H$ وجود داشته باشد که برای هر نقطه در $P^2$ که با بردار  $\mathbf{x}$ نمایش داده می‌شود، نگاشت آن با $H\mathbf{x}$ برابر باشد.
به عبارت دیگر، برای محاسبهٔ هوموگرافی که هر نقطهٔ $\mathbf{x}_i$ را به متناظرش $\mathbf{x}'_i$ نگاشت کند، کافیست که ماتریس هوموگرافی $H$ را بدست آوریم.

معمولاً ماتریس هوموگرافی با پیدا کردن ویژگیهای متناظر دو تصویر، مانند گوشه‌ها، نقاط کلیدی \lr{SIFT} و خطوط تخمین زده می‌شود. 
شناخته‌شده‌ترین روش تخمین ماتریس هوموگرافی الگوریتم تبدیل خطی مستقیم (\lr{DLT\LTRfootnote{Direct Linear Transform}}) است \citep{Hartley2004book}.  فرض کنید چهار زوج نقطهٔ متناظر در دو تصویر در دست هستند،  $\mathbf{x}_i\leftrightarrow\mathbf{x}'_i$   و تبدیل با رابطهٔ
  $\mathbf{x}'_i = H\mathbf{x}_i$
  نشان داده می‌شود که در آن:
\[\mathbf{x}'_i=(x'_i,y'_i,w'_i)^\top  \]
و
\[ H=\left[
\begin{array}{ccc}
h_1 & h_2 & h_3 \\ 
h_4 & h_5 & h_6 \\ 
h_7 & h_8 & h_9
\end{array} 
\right]\]
در ادامه از نمایش زیر برای  ماتریس $H$  که هر سطر آن با یک $\mathbf{h}^{j\top}$ نشان داده می‌شود نیز  استفاده خواهیم کرد:
\[ \mathbf{h}=\left(
\begin{array}{c}
\mathbf{h}^1 \\ 
\mathbf{h}^2 \\ 
\mathbf{h}^3
\end{array} 
\right)\]
جهت  $\mathbf{x}_i$ و $\mathbf{x}'_i$ یکسان است ولذا ضرب خارجی آنها بردار صفر خواهد بود: 
 $\mathbf{x}'_i\times H\mathbf{x}_i=\mathbf{0}$. 
 با تعریف $H$ به صورت $\mathbf{h}$  در بالا داریم:
 \[ H\mathbf{x}_i=\left(
\begin{array}{c}
\mathbf{h}^{1\top}\mathbf{x}_i \\ 
\mathbf{h}^{2\top}\mathbf{x}_i \\ 
\mathbf{h}^{3\top}\mathbf{x}_i
\end{array} 
\right)\]
بنا به تعریف دترمینانی ضرب خارجی\footnote{
اگر
 $A=a_1\mathbf{i}+a_2\mathbf{j}+a_3\mathbf{k}$
و
 $B=b_1\mathbf{i}+b_2\mathbf{j}+b_3\mathbf{k}$
آنگاه:
$A\times B=\left\vert
\begin{array}{ccc}
\mathbf{i} & \mathbf{j} & \mathbf{k} \\ 
a_1 & a_2 & a_3 \\ 
b_1 & b_2 & b_3
\end{array}
\right\vert $
}
می‌توان نوشت:
\[\mathbf{x}'_i\times H\mathbf{x}_i = \left(
\begin{array}{c}
y'_i\mathbf{h}^{3\top}\mathbf{x}_i - w'_i\mathbf{h}^{2\top}\mathbf{x}_i\\ 
w'_i\mathbf{h}^{1\top}\mathbf{x}_i - x'_i\mathbf{h}^{3\top}\mathbf{x}_i\\ 
x'_i\mathbf{h}^{2\top}\mathbf{x}_i - y'_i\mathbf{h}^{1\top}\mathbf{x}_i
\end{array} 
\right)\]
از آنجا که 
$\mathbf{h}^{j\top}\mathbf{x}_i\ = \mathbf{x}_i^\top\mathbf{h}^{2}$
رابطهٔ فوق سه معادله به ما خواهد داد که  که می‌توان آنرا به صورت زیر بازنویسی نمود:
\begin{equation}\label{eq:DLT_Ah}
\left[
\begin{array}{ccc}
0^\top & -w'_i\mathbf{x}_i^\top & y'_i\mathbf{x}_i^\top \\ 
w'_i\mathbf{x}_i & 0^\top & -x'_i\mathbf{x}_i^\top \\ 
- y'_i\mathbf{x}_i^\top & x'_i\mathbf{x}_i^\top & 0^\top
\end{array} 
\right]
\left(
\begin{array}{c}
\mathbf{h}^1 \\ 
\mathbf{h}^2 \\ 
\mathbf{h}^3
\end{array} 
\right)=0
\end{equation}
معادلهٔ فوق به صورت $\mathbf{A}_i\mathbf{h}=0$ است که $\mathbf{A}_i$ یک ماتریس ۳ در ۹ می‌باشد. در خصوص حل این دستگاه، حالت \lr{Over-determined} ، تباهیدگی\LTRfootnote{Degenerate} و نرمال‌کردن مختصات مباحث مختلفی وجود دارد که خارج از حیطهٔ این پیوست است. با مفروضات فوق، الگوریتم \lr{DLT} به صورت نشان داده شده در الگوریتم \ref{alg:DLT}  خواهد بود.
\begin{algorithm}[t]
\caption{الگوریتم \lr{DLT} برای تخمین ماتریس هوموگرافی \citep{Hartley2004book}.} \label{alg:DLT}
\begin{algorithmic}[1]
\REQUIRE $n\geq4$ زوج نقطهٔ متناظر در دو تصویر 
${\mathbf{x}_i\leftrightarrow\mathbf{x}'_i}$،\\
\ENSURE ماتریس هوموگرافی $H$ به نحوی‌که: 
$\mathbf{x}'_i = H \mathbf{x}_i$.
  \STATE برای هر زوج نقطهٔ متناظر
$\mathbf{x}_i\leftrightarrow\mathbf{x}'_i$ 
ماتریس $\mathbf{A}_i$ را با استفاده از رابطهٔ \ref{eq:DLT_Ah} محاسبه کنید.
  \STATE ماتریس‌های ۹ ستونی  $\mathbf{A}_i$ را در قالب یک ماتریس $\mathbf{A}$ ۹ ستونی ترکیب کنید. 
  \STATE تجزیهٔ مقادیر منفرد \lr{(SVD)}  ماتریس $\mathbf{A}$ را بدست آورید. بردار واحد متناظر با کمترین مقدار منفرد جواب $\mathbf{h}$ خواهد بود.
  \STATE  ماتریس هوموگرافی $H$ با تغییر شکل $\mathbf{h}$ حاصل خواهد شد.
\end{algorithmic}
\end{algorithm}
\section{نقاط کلیدی \texorpdfstring{\lr{SIFT}}{SIFT}}
یکی از ویژگیهای مشهوری که در تخمین ماتریس هوموگرافی بکار گرفته شده است «\sift »
\lr{(SIFT\LTRfootnote {\lr{Scale Invariant Feature Transform (SIFT)}})}
 هستند \citep{Brown02invariant,Lowe04distinctive}.  این ویژگی‌ها نسبت به تغییر مقیاس یا دوران تصویر مقاوم بوده و بر اثر تغییر در روشنایی یا زاویه دید دوربین تا حد زیادی نامتغیر هستند. این ویژگی‌ها از نظر مکانی و فرکانسی در محل‌های مناسبی قرار گرفته‌اند و شانس کمی برای آسیب دیدن از نویز دارند. با این روش می‌توان تعداد زیادی ویژگی را با کارآیی مناسب  و قدرت تشخیص بالا (برای شناسایی اشیاء یا صحنه‌ها) استخراج کرد \citep{Nikanjam86Panorama}.
  هر نقطه کلیدی با مختصات آن $(x,y)$، جهت $(\theta)$، مقیاس $(\sigma)$ و یک بردار ۱۲۸ تائی به عنوان توصیف‌کنندهٔ آن\LTRfootnote{Keypoint Descriptor} نشان داده می‌شود. این بردار ۱۲۸ تائی به گونه‌ای محاسبه می‌شود که مستقل از دوران تصویر باشد. برای پیداکردن نقاط متناظر در دو مجموعه نقاط (مثلاً دو تصویر)‌از بردارهای توصیف کنندهٔ آنها استفاده می‌شود. 
  %از ویژگیهای موقعیت، جهت و مقیاس هر نقطه  \citep{VedaldiSIFT}
  
چهار مرحله اصلی پردازش برای تولید این ویژگی‌ها به قرار زیر است:
\begin{enumerate}
\item شناسایی نقاط بیشینه/ کمینه (اکسترمم\LTRfootnote{Extremum}) در فضای مقیاس\LTRfootnote{Scale Space}-
در این مرحله فضای همه مقیاس‌ها و نقاط تصویر جستجو می‌شود. این کار با استفاده از تابع تفاضل گوسی با کارآیی مناسب صورت می‌گیرد و نقاطی را که نسبت به تغییر مقیاس و جهت حساس نیستند، شناسایی می‌کند.
\item تعیین محل نقطه‌کلیدی\LTRfootnote{Keypoint}-
در هر موقعیت کاندید مدل مناسبی برای تعیین محل و مقیاس ایجاد می‌شود. نقاط کلیدی بر اساس میزان پایداریشان انتخاب می‌شوند.
\item انتساب جهت\LTRfootnote{Orientation}-
برای هر نقطه‌کلیدی براساس جهت گرادیان محلی تصویر یک یا دو جهت، تعیین می‌شود. همه عملگرهای بعدی روی داده‌های تبدیل‌یافته تصویر (جهت، مقیاس و محل) اعمال می‌شود و بدین ترتیب مقاوم بودن آنها نسبت به این تبدیل‌ها تضمین می‌شود.
\item توصیف‌کننده‌ی  نقطه‌کلیدی- 
گرادیان محلی تصویر در همسایگی هر نقطه‌ی  کلیدی و در مقیاس مربوطه محاسبه می‌شود. سپس به شیوه‌ای بازیابی می‌شود که نسبت به تغییر شکل و نور تا حد زیادی مقاوم باشد.
\end{enumerate}  

این رویکرد \sift  نامیده شده  و هر تصویر را به مجموعه‌ای از نقاط مقاوم نسبت به تغییر مقیاس تبدیل می‌کند که هر کدام یک ویژگی محلی را نشان می‌دهند.
در ادامه توضیحی بیشتر بر هر یک از مراحل فوق خواهیم داشت.

\subsection{شناسایی نقاط اکسترمم در فضای مقیاس}
با استفاده از فیلتر کردن آبشاری کاندیدهای نقاط کلیدی پیدا می‌شوند. اولین گام در شناسایی نقاط کلیدی، پیدا کردن موقعیت‌ها و مقیاس‌هایی است که از نماهای متفاوت یک شئ به دست می‌آیند. پیدا کردن موقعیت‌هایی در تصویر که نسبت تغییرات به مقیاس نامتغیر هستند بوسیله جستجوی ویژگی‌های پایدار در همه مقیاس صورت می‌گیرد .
نقاط مورد نظر برای ویژگیهای \lr{SIFT}، اکسترمم‌های محلی فیلترهای تفاضل گوسی در فضای مقیاس هستند.  برای تصویر ورودی $I$ و فیلتر گوسین $G(x,y,\sigma)=1/(2\pi\sigma^2)exp^{-(x^2+y^2)/\sigma^2}$،‌تصویر فیلتر شده (مات شده) $L$ با کانولوشن آن دو حاصل خواهد شد:
\[L(x,y,\sigma) = G(x,y,\sigma)*I(x,y)\]
نتیجه کانولو یک تصویربا یک فیلتر تفاضل گوسین $G(x,y,k\sigma)-G(x,y,\sigma)$ با استفاده از $L$ به صورت زیر قابل بیان خواهد بود:
\[D(x,y,\sigma)=L(x,y,k\sigma)-L(x,y,\sigma)\]
که در واقع چیزی نیست جز تفاضل تصاویر مات شده در مقیاس‌های $\sigma$ و $k\sigma$.  شکل \ref{fig:DOG} رویکرد کارایی برای ساختن $D$ نشان می‌دهد.  تفاضل تصاویر مجاور هم محاسبه می‌شود تا تفاضل گوسی در ستون سمت راست شکل \ref{fig:DOG} تولید شود.
\begin{figure}[t]
\centering 
\includegraphics[width=.8\textwidth]{fig/DOG.png}
\caption{محاسبه تفاضل گوسی }
\label{fig:DOG} %% label for entire figure
\end{figure}

شکل \ref{fig:Einstein} عملیات فوق را برای تصویر انشتین نشان می‌دهد. شکل \ref{fig:Einstein_Gaussian} تصویر انشتین  که در  اکتاوهای مختلف مات شده است را نشان می‌دهد. شکل \ref{fig:Einstein_DOG} تفاضلات تصاویر فوق، که همان $L$ها در اکتاوهای مختلف هستند را نشان می‌دهد.
\begin{figure}
\centering 
\subfigure[تصویر انشتین که در اکتاوهای مختلف مات شده است.]{\label{fig:Einstein_Gaussian} %% label for first subfigure
\includegraphics[width=1\textwidth]{fig/Einstein_Gaussian.JPG}
}
\subfigure[تفاضلات تصاویر فوق.]{\label{fig:Einstein_DOG} %% label for second subfigure
\includegraphics[width=1\textwidth]{fig/Einstein_DOG.JPG}
}
\caption{یک نمونه از تصاویر مات شده و تفاضلات گوسی آن}
\label{fig:Einstein} %% label for entire figure
\end{figure}
یک اکسترمم محلی در این فضای مقیاس (شکل \ref{fig:DOG_extremum}) با مقایسه یک نقطه با ۸ همسایه خود در همان مقیاس و ۹ خانه همسایهٔ متناظرش در هر یک از سطوح مقیاس مجاورش مقایسه می‌گردد. اگر پیکسل یک کمینه/بیشنیهٔ محلی بود، به عنوان یک نقطهٔ کاندید برگزیده می‌شود.
\begin{figure}
\centering 
\includegraphics[width=.6\textwidth]{fig/DOG_extremum.png}
\caption{فضای مقیاس تفاضل گوسی}
\label{fig:DOG_extremum} %% label for entire figure
\end{figure}

\begin{comment}
برای هر نقطهٔ کاندید پیدا شده:
\begin{itemize}
\item با درونیابی داده‌های مجاور آن، موقعیت آن به صورت دقیق برآورد می‌شود،
\item نقاط کلیدی با کنتراست پایین حذف می‌شوند،
\item نقاط روی لبه‌ها حذف می‌شوند و
\item به هر نقطهٔ کلیدی یک جهت منتسب می‌شود.
\end{itemize}
\end{comment}
با درونیابی داده‌های مجاور هر نقطهٔ کاندید، موقعیت آن به صورت دقیق برآورد می‌شود. پس از آن با انجام فیلترهایی همچون اعمال یک حد آستانه، برخی از نقاط کاندید حذف می‌شوند. 
نقاط کاندید اولیه و نقاط باقیماندهٔ نهایی پس از فیلتر کردن آنها برای تصویر انشتین در شکل \ref{fig:Einstein_KeypointDetection} نشان داده شده‌است. به این ترتیب تا این مرحله موقعیت و مقیاس هر نقطهٔ کلیدی مشخص می‌شود. 
%پیدا کردن موقعیت دقیق و مقیاس با یک روش کمینه‌سازی مشابه روش لوکاس-کاناد انجام می‌پذیرد (بخش ۴ مقاله لوو و انتهای بخش ۲ فایل راهنمای ودالدی و ص۱۵ sift.ppt).
\begin{figure}[t]
\centering 
\subfigure[بیشینهٔ تفاضلات گوسی در مقیاس‌های مختلف.]{\label{fig:Einstein_KeypointDetection_a} %% label for first subfigure
\includegraphics[width=.45\textwidth]{fig/Einstein_KeypointDetection_a.JPG}
}
%\subfigure[باقیماندهٔ نقاط کلیدی پس از حذف نقاط با کنتراست پایین.]{\label{fig:Einstein_KeypointDetection_a} %% label for second subfigure
%\includegraphics[width=.31\textwidth]{fig/Einstein_KeypointDetection_b.JPG}
%}
\subfigure[باقیماندهٔ نقاط کلیدی پس از حذف تعدادی از آنها.]{\label{fig:Einstein_KeypointDetection_c} %% label for first subfigure
\includegraphics[width=.45\textwidth]{fig/Einstein_KeypointDetection_c.JPG}
}
\caption{نقاط اکسترمم انتخاب شده در تصویر انشتین}
\label{fig:Einstein_KeypointDetection} %% label for entire figure
\end{figure}
%تصاویر انشتین و برخی مطالب از Local Features Tutorial, MATLAB SIFT tutorial
به منظور مشخص کردن جهت هر نقطهٔ کلیدی، یک هیستوگرام جهت با استفاده از جهت گرادیان‌ها در همسایگی هر نقطه‌کلیدی تشکیل می‌شود. این کار روی تصویر مات شده $L(x,y,\sigma)$در نزدیکترین مقیاس به مقیاس نقطهٔ کلیدی که در مرحلهٔ قبل پیدا شد، صورت می‌پذیرد لذا همه محاسبات در شرایط نامتغیر بامقیاس انجام می‌شود. اندازه $(m(x,y))$ و جهت گرادیان $(\theta(x,y))$ در هر نقطه به صورت زیر محاسبه می‌شود:
\[m(x,y)=\sqrt{(L(x+1,y)-L(x-1,y))^2+(L(x,y+1)-L(x,y-1))^2}\]
\[\theta(x,y)=\tan^{-1}((L(x+1,y)-L(x-1,y))/(L(x,y+1)-L(x,y-1)))\]
  هیستوگرام جهت 36 خانه  دارد که محدوده 360 درجه را می‌پوشاند. قله‌های این هیستوگرام جهت‌های غالب در گرادیان‌های محلی را نشان می‌دهند. متناظر با  بلندترین قله‌های هیستوگرام (بزرگتر از ۸۰درصد ماکزیمم) نقاط کلیدی ایجاد می‌شود. 
به این ترتیب موقعیت، جهت و مقیاس هر نقطه کلیدی مشخص گردید. شکل \ref{fig:Einstein_Keypoints} نقاط کلیدی استخراج شده برای تصویر انشتین را نشان می‌دهد که فلش‌ها بیانگر مقیاس و جهت هر نقطهٔ کلیدی هستند.
\begin{figure}
\centering 
\includegraphics[width=.45\textwidth]{fig/Einstein_Keypoints.JPG}
\caption{نقاط کلیدی استخراج شده که فلش‌ها بیانگر مقیاس و جهت هر نقطهٔ کلیدی هستند.}
\label{fig:Einstein_Keypoints} %% label for entire figure
\end{figure}

%روشن است که ویژگیهای محاسبه شده فوق مستقل از دوران 
به جز ویژگیهای محاسبهٔ شدهٔ فوق (موقعیت، حهت و مقیاس) هر نقطهٔ کلیدی یک توصیف‌کننده  در قالب یک آرایهٔ ۱۲۸تایی دارد که مستقل از جهت و موقعیت نقطه است. این آرایه شامل مقادیر گرادیان در اطراف نقطه کلیدی است. جهت گرادیان نسبت به جهت نقطه‌ کلیدی دوران می‌یابد تا نتیجه کار نسبت به تغییر جهت مقاوم باشد. 

 در شکل \ref{fig:SIFT_Descriptors} یک آرایه 2×2 از هیستوگرام‌های جهت را مشاهده می‌کنید. در تصویر سمت راست 8 جهت برای هر هیستوگرام مشاهده می‌شود و طول هر پیکان متناسب با تعداد مدخل‌های هیستوگرام رسم شده است.  آزمایش‌های  \citep{Lowe04distinctive} مشخص کرده است که بهترین نتیجه با یک آرایه 4×4 از هیستوگرام‌هایی که در هر خانه 8 جهت دارند،‌ بدست می‌آید.  بنابراین طول بردار توصیف کننده ۱۲۸ می‌باشد.
این بردار به نحوی تغییر داده می‌شود که نسبت به تغییرات روشنایی تأثیرپذیری کمی داشته باشد. ابتدا بردار به طول واحد نرمال می‌شود. تغییر در کنتراست تصویر که منجر به ضرب شدن یک ثابت در گرادیان کنتراست‌های مشابه می‌شود، با نرمال‌سازی بی‌اثر می‌شود. تغییر در روشنایی تصویر که منجر به جمع شدن مقدار هر پیکسل با یک عدد ثابت می‌شود نیز تأثیری بر مقادیر گرادیان ندارد زیرا گرادیان از تفاضل پیکسل‌ها محاسبه می‌شود. بنابراین توصیف‌کننده نسبت به تغییرات نور نامتغیر است. 
%تغییرات غیرخطی نور نیز گرچه اندازه گرادیان را تغییر می‌دهند اما تأثیر چندانی بر جهت گرادیان ندارند. بنابراین با حذف اندازه‌هایی که بزرگتر از 0.2 هستند و نرمال‌سازی مجدد آنها به مقدار واحد، تأثیر گرادیان‌های بزرگ کم‌شده و تأکید بر جهت گرادیان در تطبیق بیشتر می‌شود.
\begin{figure}
\centering 
\includegraphics[width=.8\textwidth]{fig/SIFT_Descriptors.PNG}
\caption{تولید توصیف‌کننده‌های نقطه کلیدی.}
\label{fig:SIFT_Descriptors} %% label for entire figure
\end{figure}

از آنجا که این بردار توصیف کننده مستقل از انتقال، مقیاس و دوران شکل است در کاربردهای مختلف شناسائی اشیاء و همچنین به عنوان یک ویژگی مهم در ثبت‌تصویر مبتنی بر ویژگی بکار گرفته شده است. \cite{Mikolajczyk05performance} نشان داده است که از بین ویژگیهای مختلف تصاویر، نقاط کلیدی \lr{SIFT} بیشترین کارائی را در ثبت تصویر مبتنی بر ویژگی دارند.

\section{الگوریتم  \texorpdfstring{\lr{RANSAC}}{RANSAC}}
در مبحث هوموگرافی اشاره شد که به مجموعه‌ای از ویژگیهای کلیدی متناظر در دو تصویر برای تخمین ماتریس هوموگرافی نیاز است. در هر تصویر مجموعه‌ای از ویژگیها -مثلاً نقاط کلیدی \lr{SIFT}- داریم که مشخص نیست هر ویژگی در یک تصویر متناظر با کدام ویژگی در تصویر دیگر است. به علاوه ممکن است در هر تصویر ویژگیهایی داشته باشیم که متناظری در تصویر دیگر نداشته باشند.  روشهای مختلفی به این منظور پیشنهاد شده است که می‌توان گفت از این میان الگوریتم
 \lr{RANSAC\LTRfootnote{RANdom SAmple Consensus (RANSAC)}}
  \citep{Fischler81random}  مشهورترین آنها در زمینه‌ی حذف \outliers  و تخمین مدل نگاشت می‌باشد. 
ایده‌ی اصلی  در این الگوریتم عبارت است از تخمین پارامترهای مدل با استفاده از حداقل تعداد داده‌های ممکن و سپس بررسی صدق کردن سایر داده ها در مدل برآورد شده. در هر دور به صورت تصادفی تعدادی داده انتخاب شده و بر اساس آنها یک مدل برآورد می شود. با این فرض که داده‌های دورتر از حدی  خاص \outlier هستند، مدلی که بیشترین تعداد داده‌ها را تحت پوشش قرار دهد به عنوان مدل انتخاب شده و داده‌های نامناسب  بر اساس آن مشخص می‌شوند.



%\item [Parallax]: به صفحه‌ی ۲۰۸ از \cite{Hartley2004book} مراجعه شود.


