# فصل ۱۰: قطعه‌بندی تصویر — از پیکسل تا شیء

```{figure} chapter-10-assets/images/fig10_00_concept_map.png
:name: fig-ch10-concept-map
:width: 96%

نقشۀ مفهومی فصل: قطعه‌بندی از دو ایدۀ بنیادی «ناپیوستگی» و «شباهت» به خانواده‌های لبه، آستانه، ناحیه، خوشه، گراف و آبخیز می‌رسد. این شکل برای همین فصل از نو طراحی شده است.
```

## اهداف یادگیری

پس از مطالعۀ این فصل، انتظار می‌رود دانشجو بتواند تفاوت دیدگاه‌های مبتنی بر ناپیوستگی و شباهت را توضیح دهد؛ مشتق‌های گسسته، گرادیان، لاپلاسین، LoG و مراحل Canny را از نظر ریاضی تفسیر کند؛ تبدیل هاف را در فضای پارامترها توضیح دهد؛ آستانۀ Otsu را از واریانس درون‌کلاسی و بین‌کلاسی استخراج کند؛ رشد ناحیه، تقسیم--ادغام، K-means، SLIC، برش گراف و Watershed را به‌صورت الگوریتمی دنبال کند؛ و محدودیت‌ها و پارامترهای اصلی هر روش را تشخیص دهد.

```{admonition} مبنای متن و تکمیل علمی
:class: note

متن اصلی این صفحه از نسخۀ نهایی LaTeX پیوست‌شده توسط مدرس حفظ و به MyST Markdown تبدیل شده است. توضیح‌های افزوده، شکل‌های بازطراحی‌شده و منابع تکمیلی با برچسب یا عنوان مشخص از متن اصلی قابل تشخیص‌اند. شکل‌های استخراج‌شده از کتاب در بستۀ سایت بازنشر نشده‌اند و شکل‌های اصیلِ آموزشی جایگزین شده‌اند.
```

## فایل‌های اجرایی این فصل

- <a href="/assets/downloads/courses/image-processing/gonzalez/chapter-10/chapter10_examples.py" download>کد مستقل Python فصل ۱۰</a>
- <a href="/assets/downloads/courses/image-processing/gonzalez/chapter-10/Chapter10_Code_Examples.zip" download>بستۀ ZIP کدها و Notebook مثال‌ها</a>
- <a href="/assets/downloads/courses/image-processing/gonzalez/chapter-10/Chapter10_Original_Figures.zip" download>بستۀ ZIP شکل‌های اصیل فصل</a>


## چرا قطعه‌بندی؟

قطعه‌بندی یا Image Segmentation فرایند تقسیم تصویر به نواحی معنادار است. در فصل‌های قبل، عملیات عمدتاً روی خود تصویر انجام می‌شد: بهبود کنتراست، فیلترکردن، تبدیل فوریه و مورفولوژی. در این فصل سؤال عوض می‌شود: «کدام پیکسل‌ها به یک شیء یا ناحیه تعلق دارند؟» این تغییر، گذار از پردازش سطح پایین به تحلیل تصویر است.

هدف قطعه‌بندی تولید یک تصویر زیباتر نیست؛ هدف تولید یک نمایش ساختاری است. خروجی می‌تواند نقشۀ دودویی، مجموعه‌ای از مرزها، یا یک تصویر برچسب‌دار باشد که در آن هر پیکسل شمارۀ ناحیۀ خود را دارد. کیفیت این مرحله روی اندازه‌گیری، تشخیص و طبقه‌بندی بعدی اثر مستقیم دارد.

```{admonition} برداشت مفهومی
:class: note

دو خانوادۀ اصلی ایده‌ها در سراسر فصل تکرار می‌شوند: ۱) پیدا کردن **ناپیوستگی**‌ها، مثل لبه؛ ۲) پیدا کردن **شباهت**‌ها، مثل نواحی با شدت یا رنگ مشابه. بسیاری از الگوریتم‌ها ترکیبی از این دو دیدگاه‌اند.
```

اگر دامنۀ تصویر را با $R$ و نواحی را با $R_1,\ldots,R_n$ نشان دهیم، یک قطعه‌بندی مطلوب باید کل تصویر را بپوشاند، نواحی جدا از هم باشند، هر ناحیه نسبت به یک ویژگی $Q$ همگن باشد و ادغام نواحی مجاور همگنی را نقض کند: $$\bigcup_{i=1}^n R_i=R,\qquad R_i\cap R_j=\varnothing\;(i\neq j),\qquad Q(R_i)=\mathrm{TRUE}.$$

## نقشۀ فصل

این فصل مطابق سازمان کتاب از آشکارسازی نقطه، خط و لبه شروع می‌کند؛ سپس به آستانه‌گذاری، رشد/تقسیم/ادغام ناحیه، خوشه‌بندی و superpixel، برش گراف، آبخیز و در پایان استفاده از حرکت می‌رسد. بنابراین دانشجو باید بداند که فصل فقط «لبه‌یابی» نیست؛ لبه‌یابی تنها یکی از دروازه‌های ورود به مسئلۀ قطعه‌بندی است.

## آشکارسازی نقطه، خط و لبه

### مشتق در تصویر گسسته: از تعریف ریاضی تا کرنل لاپلاسین

یکی از مهم‌ترین ایده‌ها در آشکارسازی لبه این است که لبه در تصویر، ناحیه‌ای است که شدت روشنایی در آن به‌سرعت تغییر می‌کند. بنابراین اگر بتوانیم «میزان تغییر شدت» را اندازه بگیریم، می‌توانیم به محل لبه‌ها برسیم. ابزار ریاضی طبیعی برای اندازه‌گیری تغییر، مشتق است.

اما یک تفاوت اساسی وجود دارد: در ریاضیات پیوسته، تابع در تمام نقاط تعریف شده است، درحالی‌که تصویر دیجیتال فقط روی نقاط گسستۀ شبکۀ پیکسل‌ها در دسترس است. بنابراین ابتدا باید ببینیم چگونه مفهوم مشتق را از حالت پیوسته به حالت گسسته منتقل می‌کنیم.

#### از مشتق پیوسته به تفاضل محدود

برای یک تابع پیوستۀ یک‌بعدی $f(x)$، مشتق در نقطۀ $x$ به صورت

$$f'(x)=
\lim_{\Delta x\rightarrow 0}
\frac{f(x+\Delta x)-f(x)}{\Delta x}$$

تعریف می‌شود.

این رابطه می‌گوید مشتق، نرخ تغییر مقدار تابع نسبت به مکان است. هرچه تغییر $f$ در یک فاصلۀ کوچک بزرگ‌تر باشد، قدرمطلق مشتق نیز بزرگ‌تر خواهد بود.

در یک تصویر دیجیتال نمی‌توانیم $\Delta x$ را به صفر میل دهیم، زیرا کوچک‌ترین جابجایی قابل مشاهده برابر فاصلۀ بین دو پیکسل مجاور است. اگر فاصلۀ نمونه‌برداری را یک واحد پیکسل در نظر بگیریم،

$$\Delta x=1,$$

در نتیجه ساده‌ترین تقریب مشتق برابر است با

$$\frac{\partial f}{\partial x}
\approx
f(x+1,y)-f(x,y).$$

به این تقریب، Forward Difference یا تفاضل پیشرو گفته می‌شود.

به همین ترتیب در راستای $y$ داریم

$$\frac{\partial f}{\partial y}
\approx
f(x,y+1)-f(x,y).$$

بنابراین مشتق در تصویر دیجیتال در ساده‌ترین شکل چیزی جز **تفاضل شدت دو پیکسل مجاور** نیست.

```{admonition} برداشت مفهومی
:class: note

اگر دو پیکسل مجاور تقریباً شدت یکسانی داشته باشند، مشتق نزدیک صفر است. اگر شدت آنها بسیار متفاوت باشد، قدرمطلق مشتق بزرگ می‌شود. پس نواحی یکنواخت پاسخ کوچک و لبه‌ها پاسخ بزرگ ایجاد می‌کنند.
```

#### یک مثال عددی ساده

فرض کنید یک سطر از تصویر چنین مقادیر شدتی داشته باشد:

$$f(x)=
\begin{bmatrix}
    10 & 10 & 10 & 10 & 80 & 80 & 80
\end{bmatrix}.$$

اگر تفاضل پیکسل‌های مجاور را محاسبه کنیم، تقریب مشتق اول می‌شود

$$f'(x)\approx
\begin{bmatrix}
    0 & 0 & 0 & 70 & 0 & 0
\end{bmatrix}.$$

در قسمت‌های یکنواخت، اختلاف دو پیکسل صفر است؛ اما در محل تغییر از $10$ به $80$، مقدار بزرگی برابر $70$ ظاهر می‌شود.

این دقیقاً همان چیزی است که از یک آشکارساز لبه انتظار داریم.

#### تفاضل پیشرو، پسرو و مرکزی

تقریب مشتق اول منحصر به رابطۀ قبلی نیست. سه تقریب متداول عبارت‌اند از

$$\text{Forward:}\qquad
\frac{\partial f}{\partial x}
\approx
f(x+1,y)-f(x,y),$$

$$\text{Backward:}\qquad
\frac{\partial f}{\partial x}
\approx
f(x,y)-f(x-1,y),$$

و تفاضل مرکزی

$$\text{Central:}\qquad
\frac{\partial f}{\partial x}
\approx
\frac{f(x+1,y)-f(x-1,y)}{2}.$$

تفاضل مرکزی از اطلاعات دو طرف نقطۀ مورد نظر استفاده می‌کند و از نظر تقارن، نمایش طبیعی‌تری از مشتق در نقطۀ مرکزی است.

اگر فاصلۀ واقعی نمونه‌برداری برابر $h$ باشد، رابطۀ دقیق‌تر تفاضل مرکزی به صورت

$$\frac{\partial f}{\partial x}
\approx
\frac{f(x+h,y)-f(x-h,y)}{2h}$$

خواهد بود. در تصاویر دیجیتال معمولاً $h=1$ پیکسل در نظر گرفته می‌شود.

#### چگونه مشتق اول به یک فیلتر تبدیل می‌شود؟

رابطۀ

$$f(x+1,y)-f(x,y)$$

را می‌توان به صورت اعمال ضرایب روی دو پیکسل مجاور نوشت. بنابراین یک کرنل ساده برای مشتق افقی می‌تواند به صورت

$$\begin{bmatrix}
    -1 & 1
\end{bmatrix}$$

باشد.

برای تفاضل مرکزی نیز می‌توان از

$$\frac{1}{2}
\begin{bmatrix}
    -1 & 0 & 1
\end{bmatrix}$$

استفاده کرد.

پس مفهوم مهم این است که **عمل مشتق‌گیری گسسته را می‌توان به صورت یک فیلتر مکانی پیاده‌سازی کرد**. کرنل روی تصویر حرکت می‌کند و در هر نقطه ترکیب وزن‌دار پیکسل‌های همسایه را محاسبه می‌کند.

همین ایده در ادامه به فیلترهای شناخته‌شده‌ای مانند Prewitt و Sobel منتهی می‌شود.

#### مشتق دوم از کجا می‌آید؟

اکنون به مشتق دوم می‌رسیم. در حالت پیوسته داریم

$$f''(x)=\frac{d}{dx}\left(\frac{df}{dx}\right).$$

یعنی مشتق دوم، مشتقِ مشتق اول است.

برای رسیدن به شکل گسسته، مشتق اول را با تفاضل دو نمونه تقریب می‌زنیم:

$$f'(x)\approx f(x+1)-f(x).$$

یک نمونه قبل‌تر نیز داریم

$$f'(x-1)\approx f(x)-f(x-1).$$

اکنون تغییر مشتق اول را محاسبه می‌کنیم:

$$f''(x)
\approx
f'(x)-f'(x-1).$$

با جایگذاری دو رابطۀ بالا:

$$f''(x)
\approx
[f(x+1)-f(x)]
-
[f(x)-f(x-1)].$$

پرانتزها را باز می‌کنیم:

$$\boxed{
    f''(x)
    \approx
    f(x+1)-2f(x)+f(x-1)
}$$

این رابطه بسیار مهم است. توجه کنید که مشتق دوم در هر نقطه از سه نمونه استفاده می‌کند:

$$f(x-1),\qquad f(x),\qquad f(x+1).$$

ضرایب آنها به ترتیب برابرند با

$$1,\qquad -2,\qquad 1.$$

پس مشتق دوم یک‌بعدی را می‌توان با کرنل

$$\boxed{
    \begin{bmatrix}
        1 & -2 & 1
    \end{bmatrix}
}$$

محاسبه کرد.

این همان پلی است که ما را از تعریف ریاضی مشتق دوم به یک فیلتر دیجیتال می‌رساند.

#### معنای شهودی مشتق دوم

فرض کنید سه پیکسل متوالی چنین باشند:

$$\begin{bmatrix}
    50 & 50 & 50
\end{bmatrix}.$$

مشتق دوم در پیکسل وسط برابر است با

$$50-2(50)+50=0.$$

پس در ناحیۀ ثابت پاسخ صفر است.

حال فرض کنید

$$\begin{bmatrix}
    50 & 50 & 100
\end{bmatrix}.$$

داریم

$$50-2(50)+100=50.$$

بنابراین تغییر سریع شدت پاسخ بزرگی ایجاد می‌کند.

اما تفاوت مهم مشتق اول و دوم این است که مشتق دوم به **تغییر شیب** حساس است. به همین دلیل در اطراف یک لبه معمولاً مقادیر مثبت و منفی تولید می‌کند.

#### رفتار مشتق اول و دوم در یک لبۀ پله‌ای

برای درک بهتر، سیگنال ایده‌آل زیر را در نظر بگیرید:

$$f=
\begin{bmatrix}
    0&0&0&0&100&100&100&100
\end{bmatrix}.$$

مشتق اول تقریباً در محل تغییر یک پاسخ بزرگ ایجاد می‌کند:

$$\Delta f=
\begin{bmatrix}
    0&0&0&100&0&0&0
\end{bmatrix}.$$

حال اگر از این نتیجه دوباره مشتق بگیریم، مشتق دوم در دو طرف تغییر علامت‌های مخالف ایجاد می‌کند:

$$\Delta^2 f
\sim
\begin{bmatrix}
    0&0&100&-100&0&0
\end{bmatrix}.$$

بنابراین مشتق دوم معمولاً در یک طرف لبه مثبت و در طرف دیگر منفی است. محل عبور پاسخ از مثبت به منفی یا برعکس، Zero Crossing نامیده می‌شود و می‌تواند نشان‌دهندۀ محل لبه باشد.

```{admonition} نکتۀ تدریسی
:class: tip

روی تخته ابتدا یک تابع پله‌ای بکشید. زیر آن مشتق اول را رسم کنید که در محل تغییر یک قله دارد. سپس مشتق دوم را رسم کنید که در دو طرف لبه دو پاسخ با علامت مخالف ایجاد می‌کند. نقطۀ بین این دو پاسخ همان محل عبور از صفر است. این شکل ساده برای فهم Laplacian و بعداً LoG بسیار مهم است.
```

#### تعمیم مشتق دوم از سیگنال یک‌بعدی به تصویر دوبعدی

تا اینجا فقط در راستای $x$ حرکت می‌کردیم. اما تصویر تابعی دوبعدی است:

$$f=f(x,y).$$

بنابراین تغییرات می‌توانند هم در راستای افقی و هم در راستای عمودی رخ دهند.

مشتق دوم نسبت به $x$ برابر است با

$$\frac{\partial^2 f}{\partial x^2}
\approx
f(x+1,y)-2f(x,y)+f(x-1,y).$$

این رابطه فقط سه پیکسل افقی را بررسی می‌کند و می‌توان آن را با کرنل

$$H_x=
\begin{bmatrix}
    0&0&0\\
    1&-2&1\\
    0&0&0
\end{bmatrix}$$

پیاده‌سازی کرد.

به همین ترتیب در راستای $y$:

$$\frac{\partial^2 f}{\partial y^2}
\approx
f(x,y+1)-2f(x,y)+f(x,y-1),$$

که کرنل متناظر آن

$$H_y=
\begin{bmatrix}
    0&1&0\\
    0&-2&0\\
    0&1&0
\end{bmatrix}$$

است.

پس $H_x$ تغییرات مرتبۀ دوم در راستای افقی و $H_y$ تغییرات مرتبۀ دوم در راستای عمودی را اندازه می‌گیرد.

#### رسیدن به لاپلاسین

اگر فقط مشتق دوم در راستای $x$ را بگیریم، نسبت به جهت حساس خواهیم بود. برای آنکه تغییرات دوبعدی را در هر دو راستای اصلی در نظر بگیریم، دو مشتق دوم را با هم جمع می‌کنیم.

عملگر Laplacian برای تصویر پیوسته به صورت

$$\boxed{
    \nabla^2 f
    =
    \frac{\partial^2 f}{\partial x^2}
    +
    \frac{\partial^2 f}{\partial y^2}
}$$

تعریف می‌شود.

اکنون تقریب‌های گسسته را جایگذاری می‌کنیم:

$$\nabla^2 f(x,y)
\approx
\big[
f(x+1,y)-2f(x,y)+f(x-1,y)
\big]
+
\big[
f(x,y+1)-2f(x,y)+f(x,y-1)
\big].$$

با جمع کردن جملات:

$$\boxed{
    \nabla^2 f(x,y)
    =
    f(x+1,y)+f(x-1,y)
    +f(x,y+1)+f(x,y-1)
    -4f(x,y)
}$$

این رابطه را باید با دقت نگاه کرد. برای محاسبۀ خروجی در پیکسل مرکزی:

-   پیکسل سمت راست با ضریب $+1$،

-   پیکسل سمت چپ با ضریب $+1$،

-   پیکسل بالا با ضریب $+1$،

-   پیکسل پایین با ضریب $+1$،

-   و خود پیکسل مرکزی با ضریب $-4$

وارد محاسبه می‌شوند.

پس این رابطه مستقیماً به ماتریس زیر تبدیل می‌شود:

$$\boxed{
    H_{\nabla^2}=
    \begin{bmatrix}
        0&1&0\\
        1&-4&1\\
        0&1&0
    \end{bmatrix}
}$$

این ماتریس همان کرنل چهارهمسایگی Laplacian است.

#### چرا دقیقاً عدد $-4$ در مرکز ظاهر شد؟

این عدد حفظی نیست.

از مشتق دوم در راستای $x$، ضریب پیکسل مرکزی برابر $-2$ بود:

$$\begin{bmatrix}
    1&-2&1
\end{bmatrix}.$$

از مشتق دوم در راستای $y$ نیز یک $-2$ دیگر برای همان پیکسل مرکزی داریم. بنابراین

$$-2+(-2)=-4.$$

به همین دلیل با جمع دو کرنل

$$\begin{bmatrix}
    0&0&0\\
    1&-2&1\\
    0&0&0
\end{bmatrix}
+
\begin{bmatrix}
    0&1&0\\
    0&-2&0\\
    0&1&0
\end{bmatrix}$$

به

$$\boxed{
    \begin{bmatrix}
        0&1&0\\
        1&-4&1\\
        0&1&0
    \end{bmatrix}
}$$

می‌رسیم.

```{admonition} برداشت مفهومی
:class: note

بنابراین ماتریس لاپلاسین یک فرمول جادویی یا حفظی نیست. این ماتریس مستقیماً از تعریف مشتق دوم ساخته شده است:

$$\text{مشتق دوم افقی}
    +
    \text{مشتق دوم عمودی}
    =
    \text{Laplacian}.$$

اگر دانشجو این مسیر را بفهمد، دیگر لازم نیست کرنل لاپلاسین را حفظ کند.
```

#### مثال عددی دوبعدی

فرض کنید همسایگی یک پیکسل به صورت زیر باشد:

$$F=
\begin{bmatrix}
    10&10&10\\
    10&50&80\\
    10&80&80
\end{bmatrix}.$$

کرنل لاپلاسین را روی آن قرار می‌دهیم:

$$H=
\begin{bmatrix}
    0&1&0\\
    1&-4&1\\
    0&1&0
\end{bmatrix}.$$

خروجی در پیکسل مرکزی برابر است با

$$10+10+80+80-4(50).$$

بنابراین

$$\nabla^2 f=180-200=-20.$$

علامت منفی نشان می‌دهد که پیکسل مرکزی نسبت به ترکیب همسایه‌های اصلی خود رفتار متفاوتی دارد. در نواحی کاملاً یکنواخت، خروجی صفر خواهد بود.

برای مثال اگر تمام پیکسل‌ها برابر $50$ باشند،

$$50+50+50+50-4(50)=0.$$

پس لاپلاسین نواحی ثابت را حذف و تغییرات سریع شدت را برجسته می‌کند.

#### نسخۀ هشت‌همسایگی لاپلاسین

در کرنل قبلی فقط چهار همسایۀ بالا، پایین، چپ و راست شرکت داشتند. اگر چهار همسایۀ قطری را نیز وارد کنیم، کرنل به شکل

$$\boxed{
    \begin{bmatrix}
        1&1&1\\
        1&-8&1\\
        1&1&1
    \end{bmatrix}
}$$

درمی‌آید.

در این حالت هشت همسایه هرکدام ضریب $+1$ دارند، بنابراین برای آنکه مجموع ضرایب صفر باقی بماند، ضریب مرکز باید $-8$ باشد.

مجموع ضرایب کرنل واقعاً صفر است:

$$8(1)-8=0.$$

صفر بودن مجموع ضرایب ویژگی مهم فیلترهای مشتقی است؛ زیرا اگر تصویر در یک ناحیه مقدار ثابت $C$ داشته باشد،

$$8C-8C=0.$$

یعنی ناحیۀ ثابت پاسخی ایجاد نمی‌کند.

در برخی منابع علامت تمام ضرایب برعکس انتخاب می‌شود؛ مثلاً

$$\begin{bmatrix}
    0&-1&0\\
    -1&4&-1\\
    0&-1&0
\end{bmatrix}.$$

این دو قرارداد از نظر مکان آشکارسازی تغییرات معادل‌اند و فقط علامت پاسخ را عوض می‌کنند. هنگام ترکیب تصویر لاپلاسین با تصویر اصلی باید به این قرارداد علامت توجه کرد.

#### رابطۀ مشتق اول، گرادیان و مشتق دوم

برای تصویر دوبعدی، مشتق اول به صورت بردار گرادیان نوشته می‌شود:

$$\nabla f=
\begin{bmatrix}
    \dfrac{\partial f}{\partial x}\\[6pt]
    \dfrac{\partial f}{\partial y}
\end{bmatrix}.$$

اندازۀ گرادیان

$$|\nabla f|
=
\sqrt{
    \left(\frac{\partial f}{\partial x}\right)^2+
    \left(\frac{\partial f}{\partial y}\right)^2
}$$

شدت تغییر را نشان می‌دهد.

پس می‌توان تفاوت را چنین خلاصه کرد:

$$\boxed{
    \begin{array}{c}
        \text{مشتق اول}
        \\[2mm]
        \Downarrow
        \\
        \text{گرادیان}
        \\
        \Downarrow
        \\
        \text{بزرگی تغییر شدت و جهت آن}
\end{array}}
\qquad\qquad
\boxed{
    \begin{array}{c}
        \text{مشتق دوم}
        \\[2mm]
        \Downarrow
        \\
        \text{Laplacian}
        \\
        \Downarrow
        \\
        \text{تغییر شیب و عبور از صفر}
\end{array}}$$

گرادیان علاوه بر شدت تغییر، اطلاعات جهت نیز دارد؛ اما لاپلاسین یک کمیت اسکالر است و جهت لبه را مستقیماً در اختیار ما قرار نمی‌دهد.

#### چرا مشتق به نویز حساس است؟

فرض کنید شدت واقعی تصویر تقریباً ثابت باشد، اما به علت نویز مقادیر

$$100,\quad 101,\quad 99,\quad 102,\quad 98$$

ایجاد شده باشند. مشتق‌گیری اختلاف بین نمونه‌های مجاور را محاسبه می‌کند؛ بنابراین همین نوسان‌های کوچک نیز پاسخ تولید می‌کنند.

این موضوع برای مشتق دوم شدیدتر است، زیرا مشتق دوم تغییرات مشتق اول را اندازه می‌گیرد. به بیان ساده، هرچه مرتبۀ مشتق بالاتر رود، حساسیت به تغییرات سریع و در نتیجه به نویز بیشتر می‌شود.

به همین علت در بسیاری از آشکارسازهای لبه ابتدا تصویر را هموار می‌کنند و سپس مشتق می‌گیرند. ایدۀ Laplacian of Gaussian (LoG) دقیقاً از همین موضوع ناشی می‌شود: ابتدا اثر نویز با هموارسازی گاوسی کاهش می‌یابد و سپس لاپلاسین برای یافتن تغییرات شدت محاسبه می‌شود.

### آشکارسازی نقطه

#### اصلاً منظور از «نقطه» چیست؟

در اینجا منظور از نقطه، صرفاً یک پیکسل هندسی نیست. تمام تصویر از پیکسل تشکیل شده است؛ بنابراین اگر بگوییم «می‌خواهیم پیکسل پیدا کنیم»، معنای خاصی ندارد.

منظور از **نقطۀ منفرد** یا Isolated Point پیکسلی است که شدت آن به طور محسوسی با پیکسل‌های اطرافش تفاوت دارد.

برای مثال، دو همسایگی زیر را در نظر بگیرید:

$$A=
\begin{bmatrix}
    50&50&50\\
    50&50&50\\
    50&50&50
\end{bmatrix},
\qquad
B=
\begin{bmatrix}
    50&50&50\\
    50&200&50\\
    50&50&50
\end{bmatrix}.$$

در همسایگی $A$، پیکسل مرکزی هیچ ویژگی خاصی ندارد. مقدار آن $50$ است و تمام همسایه‌ها نیز مقدار $50$ دارند.

اما در $B$، پیکسل مرکزی مقدار $200$ دارد، درحالی‌که تمام اطراف آن تقریباً $50$ هستند.

بنابراین پیکسل مرکزی در $B$ یک نقطۀ روشن منفرد است.

به همین ترتیب،

$$C=
\begin{bmatrix}
    180&180&180\\
    180&20&180\\
    180&180&180
\end{bmatrix}$$

دارای یک نقطۀ تاریک منفرد در مرکز است.

پس مسئلۀ آشکارسازی نقطه را می‌توان چنین بیان کرد:

**آیا پیکسل مرکزی به طور غیرعادی با محیط اطراف خود متفاوت است؟**

#### چرا بحث آشکارسازی نقطه بعد از مشتق آمده است؟

در بخش قبل دیدیم که مشتق به تغییرات شدت حساس است.

در یک ناحیۀ یکنواخت مانند

$$\begin{bmatrix}
    50&50&50\\
    50&50&50\\
    50&50&50
\end{bmatrix}$$

تغییر قابل توجهی وجود ندارد.

اما اگر فقط یک پیکسل متفاوت باشد،

$$\begin{bmatrix}
    50&50&50\\
    50&200&50\\
    50&50&50
\end{bmatrix},$$

هنگامی که از اطراف به مرکز می‌رسیم، شدت ناگهان افزایش می‌یابد و بلافاصله پس از عبور از مرکز دوباره کاهش پیدا می‌کند.

یعنی در فاصلۀ بسیار کوتاهی دو تغییر شدید داریم:

$$50
\longrightarrow
200
\longrightarrow
50.$$

این دقیقاً حالتی است که یک عملگر مشتقی، به‌خصوص مشتق دوم، به آن پاسخ قوی می‌دهد.

به همین دلیل می‌توان از ایدۀ لاپلاسین که در بخش قبل آموختیم برای آشکارسازی نقاط منفرد استفاده کرد.

#### استفاده از لاپلاسین برای آشکارسازی نقطه

کرنل هشت‌همسایگی لاپلاسین را در نظر بگیرید:

$$H=
\begin{bmatrix}
    1&1&1\\
    1&-8&1\\
    1&1&1
\end{bmatrix}.$$

این ماسک را روی تصویر حرکت می‌دهیم.

در هر مکان، مقدار خروجی $R(x,y)$ از ضرب ضرایب ماسک در پیکسل‌های متناظر و جمع آنها به دست می‌آید.

اگر همسایگی را به صورت

$$\begin{bmatrix}
    z_1&z_2&z_3\\
    z_4&z_5&z_6\\
    z_7&z_8&z_9
\end{bmatrix}$$

بنویسیم، پاسخ ماسک برابر است با

$$R=
z_1+z_2+z_3+z_4
-8z_5
+z_6+z_7+z_8+z_9.$$

پیکسل $z_5$ همان پیکسل مرکزی است که می‌خواهیم بررسی کنیم.

#### اگر ناحیه یکنواخت باشد چه اتفاقی می‌افتد؟

فرض کنید تمام پیکسل‌ها مقدار $50$ داشته باشند:

$$F=
\begin{bmatrix}
    50&50&50\\
    50&50&50\\
    50&50&50
\end{bmatrix}.$$

پاسخ ماسک می‌شود

$$R=
8(50)-8(50).$$

بنابراین

$$R=0.$$

این نتیجه بسیار مهم است:

```{admonition} برداشت مفهومی
:class: note

اگر پیکسل مرکزی شبیه محیط اطراف خود باشد، پاسخ آشکارساز نقطه تقریباً صفر است.
```

#### حال یک نقطۀ روشن قرار دهیم

اکنون تصویر کوچک زیر را در نظر بگیرید:

$$F=
\begin{bmatrix}
    50&50&50\\
    50&200&50\\
    50&50&50
\end{bmatrix}.$$

ماسک همان است:

$$H=
\begin{bmatrix}
    1&1&1\\
    1&-8&1\\
    1&1&1
\end{bmatrix}.$$

هشت همسایه هرکدام مقدار $50$ دارند. بنابراین مجموع سهم آنها برابر است با

$$8\times50=400.$$

سهم پیکسل مرکزی نیز برابر است با

$$-8\times200=-1600.$$

پس

$$R=400-1600=-1200.$$

قدر مطلق پاسخ بسیار بزرگ است:

$$|R|=1200.$$

بنابراین متوجه می‌شویم که در این مکان اتفاق غیرعادی افتاده است.

#### اگر نقطه تاریک باشد چه؟

حال فرض کنید زمینۀ تصویر روشن و پیکسل مرکزی تاریک باشد:

$$F=
\begin{bmatrix}
    200&200&200\\
    200&50&200\\
    200&200&200
\end{bmatrix}.$$

پاسخ برابر است با

$$R=8(200)-8(50),$$

یعنی

$$R=1600-400=1200.$$

باز هم

$$|R|=1200.$$

پس هم نقطۀ روشن روی زمینۀ تاریک و هم نقطۀ تاریک روی زمینۀ روشن قابل آشکارسازی هستند.

فقط علامت پاسخ آنها متفاوت است.

#### معنای علامت پاسخ

با قرارداد ماسک

$$\begin{bmatrix}
    1&1&1\\
    1&-8&1\\
    1&1&1
\end{bmatrix}$$

داریم:

$$\begin{array}{c|c}
    \text{نوع نقطه} & \text{علامت تقریبی پاسخ}\\
    \hline
    \text{نقطۀ روشن روی زمینۀ تاریک} & R<0\\
    \text{نقطۀ تاریک روی زمینۀ روشن} & R>0
\end{array}$$

اگر فقط بخواهیم بدانیم «آیا یک نقطۀ غیرعادی وجود دارد یا نه»، معمولاً علامت برای ما مهم نیست و قدرمطلق پاسخ را بررسی می‌کنیم:

$$|R(x,y)|.$$

#### از پاسخ فیلتر چگونه تصمیم می‌گیریم؟

در تصویر واقعی پاسخ دقیقاً صفر یا $1200$ نخواهد بود، زیرا نویز، بافت و تغییرات طبیعی شدت نیز وجود دارند.

بنابراین یک آستانه $T$ تعیین می‌کنیم و می‌گوییم:

$$g(x,y)=
\begin{cases}
    1, & |R(x,y)|>T,\\[2mm]
    0, & |R(x,y)|\leq T.
\end{cases}$$

در این رابطه:

-   $R(x,y)$ پاسخ فیلتر در نقطۀ $(x,y)$ است؛

-   $T$ آستانۀ تصمیم است؛

-   $g(x,y)=1$ یعنی نقطۀ مورد نظر آشکار شده است؛

-   $g(x,y)=0$ یعنی آن مکان نقطۀ منفرد محسوب نمی‌شود.

```{admonition} نکتۀ تدریسی
:class: tip

برای تدریس این قسمت، بهتر است ابتدا اصلاً فرمول ننویسید.

روی تخته این دو ماتریس را کنار هم بکشید:

$$\begin{bmatrix}
        50&50&50\\
        50&50&50\\
        50&50&50
    \end{bmatrix}
    \qquad
    \begin{bmatrix}
        50&50&50\\
        50&200&50\\
        50&50&50
    \end{bmatrix}.$$

از دانشجو بپرسید:

«اگر بخواهیم با یک عدد بگوییم پیکسل وسط چقدر با محیطش متفاوت است، چه کاری می‌توانیم انجام دهیم؟»

پاسخ طبیعی این است که مقدار مرکز را با اطراف مقایسه کنیم.

بعد ماسک لاپلاسین را نشان دهید و محاسبۀ

$$8(50)-8(200)=-1200$$

را انجام دهید.

در این صورت دانشجو می‌فهمد ماسک چرا کار می‌کند، به جای اینکه فقط یک ماتریس $3\times3$ را حفظ کند.
```

#### تفاوت نقطه و لبه

این تفاوت برای ادامۀ فصل بسیار مهم است.

در نقطۀ منفرد، تغییر شدت در یک ناحیۀ بسیار کوچک و تقریباً در تمام جهت‌های اطراف پیکسل اتفاق می‌افتد:

$$\begin{bmatrix}
    50&50&50\\
    50&200&50\\
    50&50&50
\end{bmatrix}.$$

اما در لبه، تغییر شدت در امتداد یک مرز ادامه پیدا می‌کند. مثلاً:

$$\begin{bmatrix}
    50&50&200\\
    50&50&200\\
    50&50&200
\end{bmatrix}.$$

در مثال دوم دیگر یک نقطۀ منفرد نداریم؛ یک مرز عمودی بین ناحیۀ تیره و روشن داریم.

بنابراین:

$$\boxed{
    \begin{array}{c}
        \text{نقطه}\\
        \Downarrow\\
        \text{تغییر محلی و منفرد}
\end{array}}
\qquad\qquad
\boxed{
    \begin{array}{c}
        \text{لبه}\\
        \Downarrow\\
        \text{تغییر شدت در امتداد یک مرز}
\end{array}}$$

در بخش بعد خواهیم دید که برای آشکارسازی خطوط و لبه‌ها، ساختار و جهت همسایگی نیز اهمیت پیدا می‌کند.

```{admonition} پرسش کلاسی / امتحانی
:class: important

در تصویر زیر

$$\begin{bmatrix}
        100&100&100\\
        100&160&100\\
        100&100&100
    \end{bmatrix}$$

پاسخ ماسک

$$\begin{bmatrix}
        1&1&1\\
        1&-8&1\\
        1&1&1
    \end{bmatrix}$$

را در پیکسل مرکزی محاسبه کنید.

سپس توضیح دهید چرا بزرگ بودن قدرمطلق این پاسخ می‌تواند نشان‌دهندۀ وجود یک نقطۀ منفرد باشد.
```

### آشکارسازی خط

در بخش قبل دیدیم که یک نقطۀ منفرد را می‌توان به دلیل تفاوت شدید آن با همسایگی اطرافش آشکار کرد. اکنون یک ساختار پیچیده‌تر را در نظر می‌گیریم: **خط**.

#### منظور از خط در یک تصویر دیجیتال چیست؟

برای شروع، تصویر دودویی زیر را در نظر بگیرید:

$$F=
\begin{bmatrix}
    0&0&1&0&0\\
    0&0&1&0&0\\
    0&0&1&0&0\\
    0&0&1&0&0\\
    0&0&1&0&0
\end{bmatrix}.$$

در این تصویر، ستون وسط یک خط عمودی روشن روی زمینۀ تاریک است.

حال تصویر دیگری را در نظر بگیرید:

$$F=
\begin{bmatrix}
    0&0&0&0&0\\
    0&0&0&0&0\\
    1&1&1&1&1\\
    0&0&0&0&0\\
    0&0&0&0&0
\end{bmatrix}.$$

این بار یک خط افقی داریم.

بنابراین برخلاف «نقطۀ منفرد»، در آشکارسازی خط فقط متفاوت بودن یک پیکسل از اطراف کافی نیست. پیکسل‌های متفاوت باید یک **آرایش جهت‌دار** تشکیل دهند.

این کلمۀ «جهت» اساس آشکارسازی خط است.

```{admonition} برداشت مفهومی
:class: note

در آشکارسازی نقطه می‌پرسیدیم:

$$\text{آیا پیکسل مرکزی با اطراف خود متفاوت است؟}$$

اما در آشکارسازی خط می‌پرسیم:

$$\text{آیا چند پیکسل متفاوت، در یک جهت مشخص کنار یکدیگر قرار گرفته‌اند؟}$$
```

#### چرا ماسک آشکارساز خط باید جهت‌دار باشد؟

همسایگی زیر را در نظر بگیرید:

$$F_h=
\begin{bmatrix}
    10&10&10\\
    100&100&100\\
    10&10&10
\end{bmatrix}.$$

واضح است که ردیف وسط نسبت به بالا و پایین روشن‌تر است. بنابراین یک خط افقی از مرکز این همسایگی عبور می‌کند.

اگر بخواهیم ماشینی این وضعیت را تشخیص دهیم، باید به پیکسل‌های ردیف وسط وزن مثبت و به پیکسل‌های بالا و پایین وزن منفی بدهیم.

مثلاً:

$$H_h=
\begin{bmatrix}
    -1&-1&-1\\
    2& 2& 2\\
    -1&-1&-1
\end{bmatrix}.$$

اکنون پاسخ فیلتر برابر است با

$$R_h=\sum_{i=1}^{3}\sum_{j=1}^{3}
H_h(i,j)F_h(i,j).$$

برای مثال فوق:

$$R_h=
-3(10)+2(100+100+100)-3(10),$$

پس

$$R_h=-30+600-30=540.$$

پاسخ بسیار بزرگ است؛ بنابراین شواهد قوی برای وجود یک خط افقی داریم.

#### چرا ضرایب ماسک برابر $2$ و $-1$ انتخاب شده‌اند؟

این ضرایب را نباید صرفاً حفظ کرد.

ماسک

$$H_h=
\begin{bmatrix}
    -1&-1&-1\\
    2&2&2\\
    -1&-1&-1
\end{bmatrix}$$

دو کار انجام می‌دهد.

اول، به جهت مورد نظر وزن مثبت بیشتری می‌دهد. برای خط افقی، این جهت همان ردیف وسط است.

دوم، مجموع ضرایب ماسک صفر است:

$$(-1-1-1)+(2+2+2)+(-1-1-1)=0.$$

این ویژگی بسیار مهم است.

اگر ناحیه‌ای کاملاً یکنواخت باشد، مثلاً

$$F=
\begin{bmatrix}
    50&50&50\\
    50&50&50\\
    50&50&50
\end{bmatrix},$$

پاسخ ماسک برابر خواهد بود با

$$R_h=50\sum H_h(i,j)=0.$$

پس آشکارساز به یک ناحیۀ ثابت پاسخ نمی‌دهد.

اما اگر ردیف وسط متفاوت باشد، تعادل ضرایب از بین می‌رود و پاسخ بزرگی ایجاد می‌شود.

```{admonition} برداشت مفهومی
:class: note

بنابراین این ماسک در واقع سؤال زیر را می‌پرسد:

$$\text{آیا ردیف وسط به طور محسوسی با دو ردیف اطراف متفاوت است؟}$$

اگر پاسخ مثبت باشد، احتمال وجود یک خط افقی زیاد است.
```

#### ساخت آشکارسازهای جهت‌دار

اکنون همان ایده را برای جهت‌های مختلف به کار می‌بریم.

برای خط افقی:

$$H_{0}=
\begin{bmatrix}
    -1&-1&-1\\
    2& 2& 2\\
    -1&-1&-1
\end{bmatrix}.$$

برای یکی از جهت‌های قطری:

$$H_{45}=
\begin{bmatrix}
    2&-1&-1\\
    -1& 2&-1\\
    -1&-1& 2
\end{bmatrix}.$$

برای خط عمودی:

$$H_{90}=
\begin{bmatrix}
    -1& 2&-1\\
    -1& 2&-1\\
    -1& 2&-1
\end{bmatrix}.$$

و برای قطر دیگر:

$$H_{-45}=
\begin{bmatrix}
    -1&-1& 2\\
    -1& 2&-1\\
    2&-1&-1
\end{bmatrix}.$$

در هر ماسک، ضرایب $2$ در راستایی قرار گرفته‌اند که قرار است آشکار شود.

بنابراین شکل خود ماسک به ما می‌گوید به چه جهتی حساس است.

#### یک مثال: چرا آشکارساز افقی به خط عمودی پاسخ ضعیف‌تری می‌دهد؟

فرض کنید همسایگی شامل یک خط عمودی روشن باشد:

$$F_v=
\begin{bmatrix}
    10&100&10\\
    10&100&10\\
    10&100&10
\end{bmatrix}.$$

اگر ماسک افقی

$$H_h=
\begin{bmatrix}
    -1&-1&-1\\
    2&2&2\\
    -1&-1&-1
\end{bmatrix}$$

را اعمال کنیم، سهم ستون روشن در ضرایب مثبت و منفی پخش می‌شود و پاسخ قوی مخصوص خط افقی ایجاد نمی‌شود.

اما اگر ماسک عمودی

$$H_v=
\begin{bmatrix}
    -1&2&-1\\
    -1&2&-1\\
    -1&2&-1
\end{bmatrix}$$

را اعمال کنیم، هر سه پیکسل روشن دقیقاً روی ضرایب $2$ قرار می‌گیرند.

بنابراین پاسخ بسیار بزرگ‌تری خواهیم داشت.

پس ماسک‌ها صرفاً تغییر شدت را آشکار نمی‌کنند؛ بلکه **آرایش مکانی تغییرات شدت** را نیز بررسی می‌کنند.

#### بانک آشکارسازهای جهت‌دار

حال فرض کنید از قبل نمی‌دانیم خط موجود در تصویر چه جهتی دارد.

در این صورت تصویر را با هر چهار ماسک فیلتر می‌کنیم:

$$R_0(x,y)=H_0*f,$$

$$R_{45}(x,y)=H_{45}*f,$$

$$R_{90}(x,y)=H_{90}*f,$$

$$R_{-45}(x,y)=H_{-45}*f.$$

علامت $*$ در اینجا نشان‌دهندۀ اعمال فیلتر مکانی است.

در هر پیکسل چهار پاسخ داریم:

$$R_0,\qquad
R_{45},\qquad
R_{90},\qquad
R_{-45}.$$

اکنون بزرگ‌ترین قدرمطلق پاسخ را انتخاب می‌کنیم:

$$R_{\max}(x,y)
=
\max
\left\{
|R_0|,
|R_{45}|,
|R_{90}|,
|R_{-45}|
\right\}.$$

جهت متناظر با این بیشینه نیز تخمینی از جهت ساختار محلی است:

$$\hat{\theta}(x,y)
=
\arg\max_{\theta}
|R_{\theta}(x,y)|.$$

مثلاً اگر

$$|R_{45}(x,y)|
>
|R_0(x,y)|,\quad
|R_{45}(x,y)|
>
|R_{90}(x,y)|,\quad
|R_{45}(x,y)|
>
|R_{-45}(x,y)|,$$

می‌گوییم ساختار محلی در این نقطه بیشتر شبیه یک خط $45^\circ$ است.

```{admonition} نکتۀ تدریسی
:class: tip

در اینجا اصطلاح «بانک فیلتر» را برای دانشجو روشن کنید.

بانک فیلتر چیز پیچیده‌ای نیست. یک تصویر واحد را به چند آشکارساز مختلف می‌دهیم:

$$f(x,y)
    \longrightarrow
    \left\{
    H_0,\,
    H_{45},\,
    H_{90},\,
    H_{-45}
    \right\}.$$

هر فیلتر یک سؤال متفاوت می‌پرسد:

-   آیا اینجا خط افقی وجود دارد؟

-   آیا اینجا خط عمودی وجود دارد؟

-   آیا اینجا خط $45^\circ$ وجود دارد؟

-   آیا اینجا خط $-45^\circ$ وجود دارد؟

چهار پاسخ را با هم مقایسه می‌کنیم و پاسخ بزرگ‌تر نشان می‌دهد ساختار محلی بیشتر با کدام جهت سازگار است.
```

#### از پاسخ فیلتر تا تصمیم نهایی

وجود یک پاسخ بزرگ به تنهایی کافی نیست. معمولاً آستانه‌ای مانند $T$ تعریف می‌کنیم:

$$g(x,y)=
\begin{cases}
    1,& R_{\max}(x,y)>T,\\
    0,& R_{\max}(x,y)\le T.
\end{cases}$$

اگر فقط به یک جهت خاص علاقه‌مند باشیم، مثلاً خطوط عمودی، نیازی به اجرای هر چهار آشکارساز نیست و می‌توانیم بنویسیم

$$g_v(x,y)=
\begin{cases}
    1,& |R_{90}(x,y)|>T,\\
    0,& \text{otherwise}.
\end{cases}$$

به این ترتیب فقط نقاطی باقی می‌مانند که پاسخ قوی به آشکارساز عمودی دارند.

#### یک محدودیت بسیار مهم: منظور از خط در این روش، خط باریک است

ماسک‌های $3\times3$ فوق برای ساختارهایی طراحی شده‌اند که نسبت به اندازۀ ماسک باریک باشند.

برای فهم مسئله، یک خط ضخیم را در نظر بگیرید:

$$\begin{bmatrix}
    0&1&1&1&0\\
    0&1&1&1&0\\
    0&1&1&1&0\\
    0&1&1&1&0\\
    0&1&1&1&0
\end{bmatrix}.$$

اگر ماسک کوچک کاملاً داخل بخش روشن خط قرار گیرد، از دید ماسک آن ناحیه تقریباً یکنواخت است.

بنابراین ممکن است پاسخ در مرکز خط کوچک یا حتی صفر شود.

در این حالت بهتر است ساختار را یک «ناحیۀ باریک» بدانیم که دارای دو لبه است و ابتدا لبه‌های آن را آشکار کنیم.

```{admonition} برداشت مفهومی
:class: note

پس آشکارساز خط محلی را نباید با یک آشکارساز عمومی برای هر نوع خط اشتباه گرفت.

ماسک‌های $3\times3$ برای یافتن **ساختار خطی باریک و محلی** بسیار قابل فهم و مفیدند، اما برای یافتن یک خط بلند، شکسته یا دارای نویز، روش دیگری لازم است.
```

#### از آشکارسازی محلی خط تا تبدیل هاف

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

فرض کنید پس از آشکارسازی لبه، مجموعه‌ای از نقاط $$\mathcal{E}=\{P_i=(x_i,y_i)\}_{i=1}^{N_E}$$ در اختیار داریم. مسئله این است که از میان این نقاط، خط یا خط‌های موجود در تصویر را پیدا کنیم.

#### یک مثال عددی ساده از هاف در فضای کارتزین $(a,b)$

قبل از ورود به نمایش $(\rho,\theta)$، بهتر است ایدۀ تبدیل هاف را با معادلۀ آشنای خط

$$\boxed{
    y=ax+b
}$$

ببینیم.

در این بخش برای سادگی، خط‌های کاملاً عمودی را در نظر نمی‌گیریم؛ زیرا برای خط عمودی شیب $a$ نامتناهی می‌شود. هدف فعلاً فقط فهم ایدۀ **فضای پارامترها** است.

فرض کنید سه نقطۀ زیر در تصویر پیدا شده‌اند:

$$P_1=(1,3),
\qquad
P_2=(2,5),
\qquad
P_3=(3,7).$$

می‌خواهیم ببینیم آیا این سه نقطه روی یک خط مشترک قرار دارند و اگر چنین است، پارامترهای آن خط یعنی $a$ و $b$ چیست.

##### نقطۀ اول
برای نقطۀ

$$P_1=(1,3)$$

معادلۀ خط

$$y=ax+b$$

باید برقرار باشد. بنابراین

$$3=a(1)+b.$$

پس

$$\boxed{
    b=3-a.
}$$

این رابطه بسیار مهم است.

یک نقطه در صفحۀ $xy$ به تنهایی یک خط مشخص نمی‌کند؛ بی‌نهایت خط می‌تواند از آن عبور کند.

مثلاً اگر

$$a=0,$$

داریم

$$b=3,$$

و خط

$$y=3$$

از نقطۀ $P_1$ عبور می‌کند.

اگر

$$a=1,$$

آنگاه

$$b=2,$$

و خط

$$y=x+2$$

نیز از همان نقطه عبور می‌کند.

اگر

$$a=2,$$

داریم

$$b=1,$$

و خط

$$y=2x+1$$

نیز از همان نقطه عبور می‌کند.

پس نقطۀ

$$P_1=(1,3)$$

در فضای پارامترهای $(a,b)$ به رابطۀ

$$\boxed{
    b=3-a
}$$

تبدیل می‌شود.

یعنی:

$$\boxed{
    \text{یک نقطه در صفحۀ تصویر}
    \longrightarrow
    \text{یک خط در فضای }(a,b)
}$$

##### نقطۀ دوم
اکنون نقطۀ

$$P_2=(2,5)$$

را در نظر می‌گیریم.

از

$$y=ax+b$$

داریم

$$5=2a+b.$$

بنابراین

$$\boxed{
    b=5-2a.
}$$

پس در فضای $(a,b)$، نقطۀ دوم نیز یک خط ایجاد می‌کند:

$$b=5-2a.$$

##### تقاطع دو خط در فضای پارامترها
اکنون دو رابطه داریم:

$$b=3-a$$

و

$$b=5-2a.$$

اگر دو نقطۀ $P_1$ و $P_2$ روی یک خط مشترک باشند، باید یک زوج $(a,b)$ وجود داشته باشد که هر دو رابطه را هم‌زمان ارضا کند.

پس دو عبارت $b$ را برابر قرار می‌دهیم:

$$3-a=5-2a.$$

بنابراین

$$a=2.$$

حال مقدار $a=2$ را در یکی از روابط قرار می‌دهیم:

$$b=3-2.$$

پس

$$b=1.$$

بنابراین نقطۀ تقاطع دو خط در فضای پارامترها برابر است با

$$\boxed{
    (a,b)=(2,1).
}$$

این زوج پارامتر دقیقاً یک خط در صفحۀ اصلی تصویر را مشخص می‌کند:

$$\boxed{
    y=2x+1.
}$$

##### نقطۀ سوم چه می‌کند؟
حال نقطۀ سوم را بررسی می‌کنیم:

$$P_3=(3,7).$$

از

$$y=ax+b$$

داریم

$$7=3a+b.$$

پس

$$\boxed{
    b=7-3a.
}$$

اکنون پارامترهایی را که قبلاً پیدا کردیم امتحان می‌کنیم:

$$a=2,
\qquad
b=1.$$

داریم

$$7-3(2)=1.$$

پس

$$b=1.$$

یعنی خط سوم در فضای $(a,b)$ نیز از همان نقطۀ

$$\boxed{
    (a,b)=(2,1)
}$$

عبور می‌کند.

بنابراین هر سه نقطۀ تصویر

$$(1,3),
\qquad
(2,5),
\qquad
(3,7)$$

از یک خط مشترک پشتیبانی می‌کنند:

$$\boxed{
    y=2x+1.
}$$

##### معنای هندسی مثال
در صفحۀ اصلی $xy$ سه نقطه داشتیم:

$$P_1,\quad P_2,\quad P_3.$$

اما در فضای پارامترهای $(a,b)$، هر نقطه به یک خط تبدیل شد:

$$P_1:
\qquad
b=3-a,$$

$$P_2:
\qquad
b=5-2a,$$

$$P_3:
\qquad
b=7-3a.$$

هر سه خط در نقطۀ

$$\boxed{
    (a,b)=(2,1)
}$$

به یکدیگر می‌رسند.

این نقطه در فضای پارامترها یعنی:

$$a=2,
\qquad
b=1.$$

بنابراین در صفحۀ تصویر خط متناظر عبارت است از

$$\boxed{
    y=2x+1.
}$$

##### خلاصۀ بسیار مهم
$$\boxed{
    \begin{array}{ccc}
        \text{صفحۀ تصویر }(x,y)
        &
        &
        \text{فضای پارامتر }(a,b)
        \\[2mm]
        (1,3)
        &\longrightarrow&
        b=3-a
        \\[2mm]
        (2,5)
        &\longrightarrow&
        b=5-2a
        \\[2mm]
        (3,7)
        &\longrightarrow&
        b=7-3a
    \end{array}
}$$

و

$$\boxed{
    \text{تقاطع در }(a,b)=(2,1)
}$$

یعنی

$$\boxed{
    \text{خط در تصویر: }y=2x+1.
}$$

```{admonition} برداشت مفهومی
:class: note

این مثال کل ایدۀ تبدیل هاف را نشان می‌دهد:

یک نقطۀ تصویر یک خط در فضای پارامترها تولید می‌کند.

اگر چند نقطۀ تصویر روی یک خط مشترک باشند، خط‌های متناظر آنها در فضای پارامترها در یک نقطۀ مشترک به هم می‌رسند.

مختصات آن نقطه همان پارامترهای خط است.

در این مثال:

$$(a,b)=(2,1)$$

و بنابراین خط اصلی

$$y=2x+1$$

است.
```

#### نمایش خط در فضای پارامترها

نمایش آشنای خط $$y=mx+b$$ برای خط‌های نزدیک به عمودی مناسب نیست، زیرا در آن حالت $$m\rightarrow\infty.$$ به همین دلیل در تبدیل هاف از نمایش نرمال استفاده می‌کنیم: $$\boxed{\rho=x\cos\theta+y\sin\theta.}$$ در این رابطه:

-   $\rho$ فاصلۀ عمود از مبدأ تا خط است؛

-   $\theta$ زاویۀ بردار عمود بر خط با محور مرجع است.

اگر $$\mathbf{n}=
\begin{bmatrix}
    \cos\theta\\
    \sin\theta
\end{bmatrix},
\qquad
\mathbf{p}=
\begin{bmatrix}
    x\\y
\end{bmatrix},$$ آنگاه $$\rho=\mathbf p^T\mathbf n
=x\cos\theta+y\sin\theta.$$

```{figure} chapter-10-assets/images/fig10_02_hough_geometry.png
:name: fig-ch10-hough-geometry
:width: 78%

بازطراحی آموزشی نمایش نرمال خط در تبدیل هاف. بردار نرمال با زاویۀ $\theta$ و طول $\rho$، خط را با رابطۀ $\rho=x\cos\theta+y\sin\theta$ مشخص می‌کند.
```

#### هاف کلاسیک: چه چیزی را پیمایش می‌کنیم؟

فرض کنید یکی از نقاط لبه $$P_i=(x_i,y_i)$$ باشد. یک نقطه به تنهایی یک خط را تعیین نمی‌کند؛ بی‌نهایت خط می‌تواند از آن عبور کند. بنابراین زاویه‌های مختلف بردار نرمال را امتحان می‌کنیم.

مثلاً اگر $$-90^\circ\leq\theta<90^\circ$$ و گام زاویه $$\Delta\theta=1^\circ$$ باشد، زاویه‌های مجاز عبارت‌اند از $$-90^\circ,-89^\circ,\ldots,0^\circ,\ldots,89^\circ.$$

این مجموعه را به صورت فشرده می‌نویسیم: $$\boxed{\theta_k=\theta_{\min}+k\Delta\theta.}$$

در این رابطه $k$ فقط شمارۀ زاویه است. برای هر زاویۀ $\theta_k$، **فقط یک** مقدار $\rho$ محاسبه می‌شود: $$\boxed{\rho_{ik}=x_i\cos\theta_k+y_i\sin\theta_k.}$$

```{admonition} برداشت مفهومی
:class: note

در هاف کلاسیک، $\theta$ پیمایش می‌شود، اما $\rho$ برای هر $\theta$ مستقیماً از معادلۀ خط به دست می‌آید. بنابراین $\rho$ را یکی‌یکی جست‌وجو نمی‌کنیم.
```

برای مثال اگر $$P=(2,3)$$ باشد، آنگاه $$\rho(\theta)=2\cos\theta+3\sin\theta.$$ پس $$\theta=0^\circ\Rightarrow\rho=2,$$ $$\theta=45^\circ\Rightarrow
\rho=\frac{5\sqrt2}{2},$$ و $$\theta=90^\circ\Rightarrow\rho=3.$$

بنابراین یک نقطه مجموعه‌ای از زوج‌های $$(\rho_{i1},\theta_1),
(\rho_{i2},\theta_2),\ldots$$ تولید می‌کند.

#### چرا محور $\rho$ را خانه‌بندی می‌کنیم؟

خانه‌بندی $\rho$ برای جست‌وجوی آن نیست؛ برای **شمارش مقادیر نزدیک به هم** است.

فرض کنید در یک زاویۀ مشخص، برای چهار نقطه داشته باشیم: $$\rho_1=51.2,\qquad
\rho_2=50.8,\qquad
\rho_3=51.1,\qquad
\rho_4=83.7.$$ سه مقدار اول بسیار نزدیک‌اند. اگر پهنای خانه را $$\Delta\rho=1$$ بگیریم، می‌توانیم بازۀ $$50.5\leq\rho<51.5$$ را یک خانه در نظر بگیریم. در این صورت سه مقدار اول در یک خانه قرار می‌گیرند و فراوانی آن خانه برابر 3 می‌شود.

پس $\Delta\rho$ فقط دقت شمارش در محور $\rho$ را تعیین می‌کند.

#### آرایۀ انباشتگر: جدول فراوانی دوبعدی

اکنون یک جدول دوبعدی تعریف می‌کنیم:

-   یک محور برای $\theta$؛

-   یک محور برای $\rho$.

این جدول را Accumulator می‌نامیم و با $$A(j,k)$$ نمایش می‌دهیم. در ابتدا $$A(j,k)=0.$$

برای هر نقطۀ $P_i$ و هر زاویۀ $\theta_k$: $$\rho_{ik}=x_i\cos\theta_k+y_i\sin\theta_k$$ را محاسبه می‌کنیم، خانۀ $\rho$ متناظر را پیدا می‌کنیم و می‌نویسیم: $$\boxed{A(j,k)\leftarrow A(j,k)+1.}$$

پس تعریف مفهومی انباشتگر بسیار ساده است: $$\boxed{
    A(\rho,\theta)
    =
    \text{فراوانی پشتیبانی نقاط تصویر از خط }(\rho,\theta).
}$$

یعنی Accumulator یک هیستوگرام دوبعدی از رأی‌ها در فضای $(\rho,\theta)$ است.

#### چرا یک خط قله ایجاد می‌کند؟

فرض کنید نقاط زیادی تقریباً روی خطی با پارامترهای $$(\rho_0,\theta_0)$$ قرار داشته باشند. برای همۀ آنها تقریباً داریم: $$x_i\cos\theta_0+y_i\sin\theta_0\approx\rho_0.$$

پس وقتی الگوریتم به زاویۀ $\theta_0$ می‌رسد، تعداد زیادی از نقاط تقریباً همان $\rho_0$ را تولید می‌کنند. در نتیجه رأی‌ها در اطراف $$(\rho_0,\theta_0)$$ تجمع می‌کنند.

بنابراین: $$\boxed{
    \text{خط واقعی}
    \Longrightarrow
    \text{ناحیۀ پرتراکم در فضای }(\rho,\theta).
}$$

اگر چند خط در تصویر وجود داشته باشد، چند ناحیۀ پرتراکم یا چند قله داریم.

#### مثال عددی بسیار ساده

نقاط $$(2,1),\quad(2,2),\quad(2,3),\quad(2,4)$$ همه روی خط $$x=2$$ قرار دارند.

برای $$\theta=0^\circ$$ داریم: $$\rho=x\cos0^\circ+y\sin0^\circ=x.$$ پس هر چهار نقطه $$\rho=2$$ تولید می‌کنند. بنابراین خانۀ $$(\rho,\theta)=(2,0^\circ)$$ چهار رأی می‌گیرد: $$A(2,0^\circ)=4.$$

این مقدار بزرگ یعنی چهار نقطه از همان خط پشتیبانی کرده‌اند.

#### آیا باید محل تقاطع منحنی‌ها را حل کنیم؟

برای یک نقطۀ ثابت $$P_i=(x_i,y_i)$$ رابطۀ $$\rho_i(\theta)=x_i\cos\theta+y_i\sin\theta$$ اگر در صفحۀ $(\theta,\rho)$ رسم شود یک منحنی ایجاد می‌کند. اگر چند نقطه دقیقاً هم‌خط باشند، منحنی‌های آنها در پارامترهای خط مشترک از یک نقطه عبور می‌کنند.

این فقط یک **تفسیر هندسی** است. در پیاده‌سازی معمول هاف، لازم نیست دستگاه معادلات تقاطع این منحنی‌ها را حل کنیم. الگوریتم عملی همان رأی‌گیری است: $$\boxed{
    \text{نقطه}
    \rightarrow
    \text{پیمایش }\theta
    \rightarrow
    \text{محاسبۀ }\rho
    \rightarrow
    \text{افزایش فراوانی}.
}$$

#### از فراوانی به چگالی: اثر نویز

در تصویر واقعی نقاط دقیقاً روی یک خط ریاضی قرار نمی‌گیرند. نویز، ضخامت لبه، خطای آشکارسازی، پیکسلی بودن مختصات و ناهمواری مرز باعث می‌شوند پارامترهای حاصل در اطراف مقدار واقعی پخش شوند.

پس به جای یک نقطۀ دقیق $$(\rho_0,\theta_0)$$ معمولاً یک ابر از رأی‌ها در اطراف آن داریم.

از این دیدگاه، انباشتگر یک تخمین گسسته از چگالی پشتیبانی در فضای پارامترها است.

#### انباشتگر به عنوان تخمین هیستوگرامی چگالی

فرض کنید همۀ رأی‌ها را به صورت $$\mathcal V=
\{\mathbf v_m\}_{m=1}^{M},
\qquad
\mathbf v_m=
\begin{bmatrix}
    \rho_m\\
    \theta_m
\end{bmatrix}$$ جمع کرده باشیم.

اگر $B_{jk}$ یک خانۀ فضای پارامتر باشد: $$A_{jk}
=
\sum_{m=1}^{M}
\mathbf 1[\mathbf v_m\in B_{jk}].$$

اگر بر تعداد کل رأی‌ها و مساحت خانه تقسیم کنیم: $$\hat p_{\mathrm{hist}}(\rho,\theta)
\approx
\frac{A_{jk}}
{M\,\Delta\rho\,\Delta\theta}.$$

پس انباشتگر را می‌توان یک **تخمین هیستوگرامی چگالی** دانست.

#### مشکل هیستوگرام و انگیزۀ KDE

هیستوگرام به مرز خانه‌ها حساس است. ممکن است سه رأی بسیار نزدیک $$50.95,\qquad51.02,\qquad51.08$$ به دلیل قرار گرفتن مرز خانه در $\rho=51$، بین دو خانه تقسیم شوند.

در Kernel Density Estimation یا KDE به جای قرار دادن هر رأی در یک خانۀ خشک، هر رأی یک کرنل نرم در اطراف خود ایجاد می‌کند.

#### KDE در فضای $(\rho,\theta)$

برای رأی‌های $$(\rho_m,\theta_m),\qquad m=1,\ldots,M$$ تخمین چگالی را می‌توان به صورت $$\boxed{
    \hat p(\rho,\theta)
    =
    \frac{1}{M}
    \sum_{m=1}^{M}
    K_{h_\rho,h_\theta}
    (\rho-\rho_m,\theta-\theta_m)
}$$ نوشت.

برای کرنل گاوسی: $$K=
\frac{1}{2\pi h_\rho h_\theta}
\exp\left[
-\frac12
\left(
\frac{(\rho-\rho_m)^2}{h_\rho^2}
+
\frac{d_\theta(\theta,\theta_m)^2}{h_\theta^2}
\right)
\right].$$

در این رابطه:

-   $h_\rho$ پهنای کرنل در راستای $\rho$ است؛

-   $h_\theta$ پهنای کرنل در راستای زاویه است؛

-   $d_\theta$ اختلاف زاویه‌ای مناسب است.

اگر چند رأی به یک خط مشترک مربوط باشند، کرنل‌های آنها روی هم قرار می‌گیرند و یک مد یا قلۀ چگالی ایجاد می‌کنند.

```{admonition} برداشت مفهومی
:class: note

Accumulator می‌پرسد: «در هر خانۀ پارامتر چند رأی افتاده است؟»

KDE می‌پرسد: «در هر نقطۀ فضای پارامتر، با در نظر گرفتن همسایگی نرم، چگالی پشتیبانی چقدر است؟»
```

#### پهنای کرنل و مقیاس دو محور

اگر $h_\rho$ و $h_\theta$ خیلی کوچک باشند، سطح چگالی پرنوسان و حساس به نویز می‌شود. اگر خیلی بزرگ باشند، قله‌های دو خط نزدیک ممکن است ادغام شوند.

همچنین $\rho$ واحد پیکسل و $\theta$ واحد زاویه دارد، پس فاصله باید مقیاس‌بندی شود: $$d^2
=
\left(
\frac{\rho_1-\rho_2}{h_\rho}
\right)^2
+
\left(
\frac{d_\theta(\theta_1,\theta_2)}{h_\theta}
\right)^2.$$

#### معادل بودن نمایش‌های خط در مرز زاویه

در نمایش نرمال: $$\boxed{
    (\rho,\theta)\equiv(-\rho,\theta+\pi).
}$$

بنابراین در پیاده‌سازی KDE باید مرز زاویه را درست مدیریت کرد. یک روش عملی این است که نسخه‌های معادل $$(\rho_m,\theta_m),\qquad
(-\rho_m,\theta_m+\pi),\qquad
(-\rho_m,\theta_m-\pi)$$ را نیز هنگام محاسبۀ چگالی در نظر بگیریم و در پایان نتیجه را به بازۀ اصلی زاویه برگردانیم.

#### یافتن قله‌های KDE با Mean Shift

پس از ساخت سطح چگالی $$\hat p(\rho,\theta)$$ باید مدهای آن را پیدا کنیم. Mean Shift یک روش تکراری برای حرکت به سمت ناحیۀ پرچگال‌تر است.

از نقطۀ $$(\rho^{(t)},\theta^{(t)})$$ شروع می‌کنیم. برای هر رأی وزن $$w_m^{(t)}
=
\exp\left[
-\frac12
\left(
\frac{\rho_m-\rho^{(t)}}{h_\rho}
\right)^2
-\frac12
\left(
\frac{d_\theta(\theta_m,\theta^{(t)})}{h_\theta}
\right)^2
\right]$$ را می‌سازیم.

به‌روزرسانی $\rho$: $$\boxed{
    \rho^{(t+1)}
    =
    \frac{\sum_m w_m^{(t)}\rho_m}
    {\sum_m w_m^{(t)}}.
}$$

برای زاویه، با در نظر گرفتن اختلاف زاویه‌ای: $$\boxed{
    \theta^{(t+1)}
    =
    \theta^{(t)}
    +
    \frac{
        \sum_m w_m^{(t)}
        d_\theta(\theta_m,\theta^{(t)})
    }{
        \sum_m w_m^{(t)}
    }.
}$$

تکرار تا زمانی ادامه می‌یابد که جابه‌جایی بسیار کوچک شود. با چند بذر مختلف، مدهای مختلف پیدا می‌شوند. مدهای نهایی نزدیک به هم ادغام می‌شوند.

#### زنجیرۀ هاف کلاسیک از دو دیدگاه

نسخۀ کلاسیک: $$\boxed{
    \text{نقاط لبه}
    \rightarrow
    \text{پیمایش }\theta
    \rightarrow
    \text{محاسبۀ }\rho
    \rightarrow
    \text{Accumulator}
    \rightarrow
    \text{قله‌ها}
    \rightarrow
    \text{خط‌ها}
}$$

نسخۀ چگالی: $$\boxed{
    \text{نقاط لبه}
    \rightarrow
    \text{پیمایش }\theta
    \rightarrow
    \text{محاسبۀ }\rho
    \rightarrow
    \text{رأی‌های }(\rho,\theta)
    \rightarrow
    \text{KDE}
    \rightarrow
    \text{Mean Shift}
    \rightarrow
    \text{مدها}
    \rightarrow
    \text{خط‌ها}
}$$

#### هزینۀ محاسباتی هاف کلاسیک

اگر $N_E$ نقطۀ لبه و $N_\theta$ زاویۀ آزمایش‌شده داشته باشیم: $$\boxed{
    O(N_E N_\theta)
}$$ محاسبۀ رأی لازم است.

اگر $N_\theta$ ثابت باشد، هزینه نسبت به $N_E$ خطی است، ولی ضریب ثابت می‌تواند بزرگ باشد. حافظۀ انباشتگر نیز تقریباً $$O(N_\rho N_\theta)$$ است.

#### روش دو-نقطه‌ای: تولید مستقیم فرضیۀ خط

اکنون به جای یک نقطه و تعداد زیادی زاویه، دو نقطۀ لبه را انتخاب می‌کنیم: $$P_i=(x_i,y_i),
\qquad
P_j=(x_j,y_j).$$

از دو نقطۀ متمایز دقیقاً یک خط عبور می‌کند، پس: $$\boxed{
    (P_i,P_j)
    \rightarrow
    (\rho_{ij},\theta_{ij}).
}$$

تعریف می‌کنیم: $$\Delta x=x_j-x_i,
\qquad
\Delta y=y_j-y_i.$$

بردار جهت: $$\mathbf d=
\begin{bmatrix}
    \Delta x\\
    \Delta y
\end{bmatrix},$$ و یک بردار عمود: $$\mathbf n=
\begin{bmatrix}
    \Delta y\\
    -\Delta x
\end{bmatrix}.$$

اگر $$L=\sqrt{\Delta x^2+\Delta y^2},$$ بردار واحد نرمال: $$\hat{\mathbf n}
=
\frac1L
\begin{bmatrix}
    \Delta y\\
    -\Delta x
\end{bmatrix}.$$

پس $$\boxed{
    \theta_{ij}
    =
    \operatorname{atan2}(-\Delta x,\Delta y)
}$$ و $$\boxed{
    \rho_{ij}
    =
    x_i\cos\theta_{ij}
    +
    y_i\sin\theta_{ij}.
}$$

#### چرا هر زوج فقط یک فرضیه است؟

دو نقطۀ انتخاب‌شده الزاماً از یک خط فیزیکی نیامده‌اند. بنابراین هر زوج فقط یک فرضیۀ خط می‌سازد.

زوج‌های نامرتبط، نقاط پراکنده در فضای پارامتر ایجاد می‌کنند؛ ولی زوج‌هایی که واقعاً از یک خط آمده‌اند در اطراف پارامترهای همان خط تجمع می‌کنند: $$\boxed{
    \text{زوج‌های درست}
    \rightarrow
    \text{ابر متراکم در }(\rho,\theta).
}$$

#### KDE در روش دو-نقطه‌ای

اگر از $S$ زوج، فرضیه‌های $$\mathcal H=
\{(\rho_s,\theta_s)\}_{s=1}^{S}$$ را بسازیم، مسئله مستقیماً به تخمین چگالی تبدیل می‌شود: $$\boxed{
    \hat p_{\mathrm{pair}}(\rho,\theta)
    =
    \frac1S
    \sum_{s=1}^{S}
    K_{h_\rho,h_\theta}
    (\rho-\rho_s,\theta-\theta_s).
}$$

مدهای این چگالی کاندیدهای خطوط واقعی‌اند. Mean Shift همانند بخش قبل می‌تواند این مدها را پیدا کند.

در این روش اگر چند خط در پنجره وجود داشته باشد، انتظار چند مد داریم: $$(\hat\rho_1,\hat\theta_1),
\ldots,
(\hat\rho_K,\hat\theta_K).$$

#### مقایسۀ نهایی دو دیدگاه

هاف کلاسیک: $$\boxed{
    P_i
    \rightarrow
    \{\theta_k\}
    \rightarrow
    \{(\rho_{ik},\theta_k)\}
    \rightarrow
    \text{فراوانی/چگالی}
    \rightarrow
    \text{مدها}
    \rightarrow
    \text{خط‌ها}.
}$$

روش دو-نقطه‌ای: $$\boxed{
    (P_i,P_j)
    \rightarrow
    (\rho_{ij},\theta_{ij})
    \rightarrow
    \text{چگالی فرضیه‌ها}
    \rightarrow
    \text{KDE}
    \rightarrow
    \text{Mean Shift}
    \rightarrow
    \text{مدها}
    \rightarrow
    \text{اعتبارسنجی}
    \rightarrow
    \text{خط‌ها}.
}$$

```{admonition} نکتۀ تدریسی
:class: tip

ترتیب تدریس پیشنهادی:

ابتدا یک نقطۀ لبه رسم کنید و نشان دهید که یک نقطه خط را تعیین نمی‌کند. سپس چند $\theta$ انتخاب کنید و برای هرکدام فقط یک $\rho$ محاسبه کنید. در این مرحله تأکید کنید که $\rho$ جست‌وجو نمی‌شود.

بعد چند نقطۀ تقریباً هم‌خط رسم کنید و نشان دهید که در زاویۀ درست، تقریباً یک $\rho$ مشترک تولید می‌کنند. اینجا Accumulator را به عنوان جدول فراوانی معرفی کنید.

سپس نویز را اضافه کنید؛ رأی‌ها دیگر در یک خانه نمی‌افتند و یک ناحیۀ پرتراکم می‌سازند. از همین جا KDE به عنوان نسخۀ نرم هیستوگرام و Mean Shift به عنوان روش یافتن قله‌های چگالی معرفی شود.

در پایان، دو نقطه رسم کنید و یادآوری کنید که دو نقطۀ متمایز یک خط یکتا می‌سازند. از اینجا روش دو-نقطه‌ای و چگالی فرضیه‌های خط به طور طبیعی به دست می‌آید.
```

```{admonition} پرسش کلاسی / امتحانی
:class: important

1.  چرا در هاف کلاسیک $\theta$ پیمایش می‌شود ولی $\rho$ مستقیماً محاسبه می‌شود؟

2.  Accumulator از نظر آماری چه چیزی را اندازه می‌گیرد؟

3.  چرا در داده‌های نویزی بهتر است از ناحیۀ پرتراکم صحبت کنیم؟

4.  تفاوت اصلی Accumulator و KDE چیست؟

5.  Mean Shift چگونه مدهای چگالی را پیدا می‌کند؟

6.  چرا بررسی تمام زوج‌ها در روش دو-نقطه‌ای الزاماً ارزان نیست؟

7.  چرا پس از یافتن مد در فضای پارامتر باید پشتیبانی آن را روی نقاط اصلی تصویر دوباره بررسی کرد؟
```

### گرادیان: اندازه و جهت تغییر شدت روشنایی

در تصویر یک‌بعدی، مشتق به ما می‌گفت شدت روشنایی با حرکت در امتداد محور چقدر تغییر می‌کند. اگر

$$f(x)$$

شدت روشنایی باشد، مقدار

$$\frac{df}{dx}$$

نرخ تغییر شدت را در راستای $x$ نشان می‌دهد.

اما تصویر دوبعدی است:

$$f(x,y).$$

بنابراین از یک نقطۀ تصویر می‌توان در جهت‌های مختلف حرکت کرد. ممکن است شدت در جهت افقی به سرعت تغییر کند، در جهت عمودی تقریباً ثابت باشد، یا بیشترین تغییر در یک جهت مورب اتفاق بیفتد.

پس دیگر یک مشتق به تنهایی کافی نیست.

#### دو مشتق جزئی چه چیزی را اندازه می‌گیرند؟

در یک نقطۀ

$$(x,y)$$

دو مشتق جزئی اصلی تعریف می‌کنیم:

$$g_x
=
\frac{\partial f}{\partial x},
\qquad
g_y
=
\frac{\partial f}{\partial y}.$$

$g_x$ می‌گوید اگر فقط در راستای $x$ حرکت کنیم، شدت با چه سرعتی تغییر می‌کند.

به طور مشابه، $g_y$ نرخ تغییر شدت را در راستای $y$ نشان می‌دهد.

برای مثال اگر

$$g_x=10,
\qquad
g_y=0,$$

باشد، تغییر اصلی شدت در جهت $x$ اتفاق افتاده است.

اگر

$$g_x=0,
\qquad
g_y=10,$$

باشد، تغییر اصلی در جهت $y$ است.

اما اگر

$$g_x=3,
\qquad
g_y=4,$$

باشد، تغییر فقط در هیچ‌یک از دو محور نیست؛ جهت واقعی تغییر ترکیبی از هر دو مؤلفه است.

به همین دلیل دو مشتق را در یک بردار جمع می‌کنیم:

$$\boxed{
    \nabla f(x,y)
    =
    \begin{bmatrix}
        g_x\\[1mm]
        g_y
    \end{bmatrix}
    =
    \begin{bmatrix}
        \dfrac{\partial f}{\partial x}\\[3mm]
        \dfrac{\partial f}{\partial y}
    \end{bmatrix}
}$$

که به آن **بردار گرادیان** می‌گوییم.

#### گرادیان واقعاً چه معنای هندسی دارد؟

گرادیان فقط کنار هم گذاشتن دو مشتق نیست. این بردار یک خاصیت هندسی بسیار مهم دارد:

**گرادیان در جهت بیشترین افزایش شدت روشنایی قرار دارد.**

برای اینکه دلیل این جمله روشن شود، یک جهت دلخواه را در صفحۀ تصویر در نظر بگیرید.

بردار واحد در زاویۀ $\phi$ را می‌توان نوشت:

$$\mathbf{u}
=
\begin{bmatrix}
    \cos\phi\\
    \sin\phi
\end{bmatrix}.$$

اکنون می‌خواهیم بدانیم اگر از نقطۀ $(x,y)$ کمی در جهت $\mathbf{u}$ حرکت کنیم، شدت با چه سرعتی تغییر می‌کند.

این کمیت را **مشتق جهتی** می‌نامیم:

$$D_{\mathbf{u}}f.$$

برای تابع دوبعدی داریم:

$$\boxed{
    D_{\mathbf{u}}f
    =
    \nabla f^{T}\mathbf{u}
}$$

بنابراین

$$D_{\mathbf{u}}f
=
g_x\cos\phi
+
g_y\sin\phi.$$

#### چرا جهت گرادیان جهت بیشترین تغییر است؟

فرض کنید اندازۀ گرادیان برابر $M$ و زاویۀ آن برابر $\alpha$ باشد.

پس می‌توان گرادیان را به صورت

$$\nabla f
=
M
\begin{bmatrix}
    \cos\alpha\\
    \sin\alpha
\end{bmatrix}$$

نوشت.

مشتق جهتی در جهت $\phi$ می‌شود:

$$D_{\mathbf{u}}f
=
M
\begin{bmatrix}
    \cos\alpha&
    \sin\alpha
\end{bmatrix}
\begin{bmatrix}
    \cos\phi\\
    \sin\phi
\end{bmatrix}.$$

بنابراین

$$D_{\mathbf{u}}f
=
M
\left(
\cos\alpha\cos\phi
+
\sin\alpha\sin\phi
\right).$$

با استفاده از رابطۀ مثلثاتی

$$\cos(\phi-\alpha)
=
\cos\phi\cos\alpha
+
\sin\phi\sin\alpha,$$

داریم:

$$\boxed{
    D_{\mathbf{u}}f
    =
    M\cos(\phi-\alpha).
}$$

اکنون معنی هندسی گرادیان کاملاً روشن می‌شود.

برای مشاهدهٔ عددی و هندسی این نتیجه، در پیوست [\[app:gradient-directional-derivative\]](#app:gradient-directional-derivative){reference-type="ref" reference="app:gradient-directional-derivative"} تابع دوبعدی

$$f(x,y)=x^2+2y^2$$

بررسی شده است. در نقطۀ $P_0=(1,1)$، گرادیان، اندازۀ آن و مشتق جهتی برای تمام جهت‌های ممکن محاسبه می‌شوند. شکل [\[fig:gradient-geometry-app\]](#fig:gradient-geometry-app){reference-type="ref" reference="fig:gradient-geometry-app"} نشان می‌دهد که بردار گرادیان بر منحنی هم‌مقدار عبوری از نقطه عمود است، و شکل [\[fig:directional-derivative-angle-app\]](#fig:directional-derivative-angle-app){reference-type="ref" reference="fig:directional-derivative-angle-app"} به طور عددی نشان می‌دهد که مشتق جهتی دقیقاً در $\phi=\alpha$ بیشینه، در جهت‌های عمود بر گرادیان صفر و در جهت مخالف گرادیان کمینه می‌شود.

بیشترین مقدار $\cos(\phi-\alpha)$ برابر 1 است و هنگامی رخ می‌دهد که

$$\phi=\alpha.$$

پس

$$D_{\mathbf{u}}f=M$$

و تغییر شدت بیشینه است.

یعنی:

$$\boxed{
    \text{جهت بیشترین افزایش شدت}
    =
    \text{جهت گرادیان}.
}$$

در جهت مخالف گرادیان،

$$\phi=\alpha+180^\circ,$$

داریم

$$D_{\mathbf{u}}f=-M.$$

یعنی در این جهت بیشترین **کاهش** شدت رخ می‌دهد.

و اگر

$$\phi=\alpha+90^\circ,$$

باشد،

$$D_{\mathbf{u}}f=0.$$

یعنی در جهت عمود بر گرادیان، در تقریب موضعی شدت تغییر نمی‌کند.

#### اندازۀ گرادیان

اندازۀ بردار گرادیان از رابطۀ طول بردار دوبعدی به دست می‌آید:

$$\boxed{
    M(x,y)
    =
    \|\nabla f(x,y)\|
    =
    \sqrt{
        g_x^2(x,y)+g_y^2(x,y)
    }.
}$$

این مقدار بسیار مهم است.

اگر

$$M(x,y)\approx0,$$

باشد، شدت در اطراف آن نقطه تقریباً ثابت است.

اگر

$$M(x,y)$$

بزرگ باشد، شدت در آن محل به سرعت تغییر می‌کند.

از آنجا که لبه‌ها محل تغییر سریع شدت هستند، اندازۀ گرادیان را می‌توان به عنوان معیاری برای **قدرت لبه** در نظر گرفت:

$$\boxed{
    M\text{ بزرگ}
    \quad\Longrightarrow\quad
    \text{لبۀ قوی‌تر}.
}$$

بنابراین با محاسبۀ $M(x,y)$ برای تمام پیکسل‌ها، یک تصویر جدید با همان اندازۀ تصویر اولیه به دست می‌آید که معمولاً آن را **تصویر اندازۀ گرادیان** یا Gradient Magnitude Image می‌نامیم.

در این تصویر معمولاً نواحی تقریباً یکنواخت تیره‌اند و مکان تغییرات شدید شدت روشن‌تر ظاهر می‌شود.

#### جهت گرادیان

از مؤلفه‌های

$$g_x,\qquad g_y$$

می‌توان جهت بردار گرادیان را نیز محاسبه کرد.

در شکل ساده می‌نویسیم:

$$\alpha(x,y)
=
\tan^{-1}
\left(
\frac{g_y}{g_x}
\right).$$

اما در پیاده‌سازی عددی بهتر است از تابع دوورودی

$$\boxed{
    \alpha(x,y)
    =
    \operatorname{atan2}
    \left(
    g_y(x,y),g_x(x,y)
    \right)
}$$

استفاده شود.

علت آن است که رابطۀ

$$\tan^{-1}\left(\frac{g_y}{g_x}\right)$$

به تنهایی نمی‌تواند ربع زاویه را به طور مطمئن مشخص کند و هنگامی که

$$g_x=0$$

باشد نیز تقسیم بر صفر ایجاد می‌شود.

تابع atan2 علامت هر دو مؤلفه را بررسی می‌کند و جهت صحیح بردار را تعیین می‌کند.

#### یک مثال عددی ساده

فرض کنید در نقطه‌ای از تصویر محاسبه کرده‌ایم:

$$g_x=3,
\qquad
g_y=4.$$

پس بردار گرادیان

$$\nabla f
=
\begin{bmatrix}
    3\\
    4
\end{bmatrix}$$

است.

اندازۀ آن:

$$M
=
\sqrt{3^2+4^2}
=
5.$$

و جهت آن:

$$\alpha
=
\operatorname{atan2}(4,3)
\approx
53.13^\circ.$$

پس در این نقطه سریع‌ترین افزایش شدت در جهت تقریباً

$$53.13^\circ$$

رخ می‌دهد و نرخ این افزایش برابر

$$5$$

است.

اگر در جهت مخالف حرکت کنیم، بیشترین کاهش شدت را خواهیم داشت.

اگر در جهت

$$53.13^\circ+90^\circ
=
143.13^\circ$$

حرکت کنیم، تغییر شدت در تقریب موضعی صفر است.

#### چرا گرادیان بر لبه عمود است؟

این نکته یکی از مهم‌ترین مفاهیم آشکارسازی لبه است.

یک لبۀ ایده‌آل را تصور کنید که دو ناحیه با شدت‌های متفاوت را از هم جدا می‌کند.

اگر **در امتداد خود لبه** حرکت کنیم، تا زمانی که روی همان مرز حرکت می‌کنیم شدت تغییر زیادی نمی‌کند.

اما اگر **عمود بر لبه** حرکت کنیم، از یک ناحیۀ شدت به ناحیۀ دیگر وارد می‌شویم؛ بنابراین تغییر شدت بیشینه است.

از طرف دیگر می‌دانیم گرادیان در جهت بیشترین تغییر شدت قرار دارد.

پس:

$$\boxed{
    \text{جهت گرادیان}
    \perp
    \text{جهت لبه}.
}$$

اگر جهت گرادیان

$$\alpha$$

باشد، یکی از نمایش‌های جهت هندسی لبه برابر است با

$$\boxed{
    \beta
    =
    \alpha+90^\circ
}$$

که البته زاویه‌های خطوط به پیمانۀ $180^\circ$ معادل‌اند.

یعنی

$$\beta
\equiv
\alpha+90^\circ
\pmod{180^\circ}.$$

#### تفسیر دیگر: خطوط هم‌شدت

این موضوع را می‌توان از دید دیگری نیز فهمید.

فرض کنید مجموعه‌ای از نقاط تصویر دارای شدت ثابت $c$ باشند:

$$f(x,y)=c.$$

این نقاط یک منحنی هم‌شدت یا Level Curve تشکیل می‌دهند.

اگر روی این منحنی حرکت کنیم، مقدار $f$ ثابت می‌ماند. بنابراین مشتق جهتی در راستای مماس بر منحنی صفر است.

اگر بردار مماس را $\mathbf t$ بنامیم:

$$\nabla f^{T}\mathbf t=0.$$

دو بردار که ضرب داخلی آنها صفر است بر یکدیگر عمودند. بنابراین

$$\boxed{
    \nabla f
    \perp
    \mathbf t.
}$$

لبۀ موضعی نیز تقریباً مانند یک منحنی هم‌شدت یا مرز تغییر شدت رفتار می‌کند. به همین دلیل گرادیان بردار نرمال لبه است.

به همین علت در برخی متون به گرادیان در محل لبه Edge Normal نیز گفته می‌شود.

#### علامت گرادیان چه اطلاعاتی می‌دهد؟

اندازۀ گرادیان

$$M=\sqrt{g_x^2+g_y^2}$$

همیشه نامنفی است و فقط قدرت تغییر را نشان می‌دهد.

اما خود مؤلفه‌های $g_x$ و $g_y$ علامت دارند.

برای مثال اگر در راستای $x$

$$g_x>0,$$

باشد، با حرکت در جهت مثبت $x$، شدت افزایش می‌یابد.

اگر

$$g_x<0,$$

باشد، شدت کاهش می‌یابد.

پس دو لبه با قدرت مساوی، یکی از تاریک به روشن و دیگری از روشن به تاریک، می‌توانند اندازۀ گرادیان یکسان ولی جهت گرادیان مخالف داشته باشند.

بنابراین:

$$\boxed{
    M
    \rightarrow
    \text{قدرت تغییر}
}$$

در حالی که

$$\boxed{
    \alpha
    \rightarrow
    \text{جهت و قطبیت تغییر}.
}$$

#### تقریب سریع اندازۀ گرادیان

محاسبۀ دقیق اندازۀ گرادیان نیازمند توان دوم، جمع و جذر است:

$$M
=
\sqrt{g_x^2+g_y^2}.$$

در برخی پیاده‌سازی‌ها برای کاهش هزینۀ محاسبات از تقریب

$$\boxed{
    M
    \approx
    |g_x|+|g_y|
}$$

استفاده می‌شود.

این کمیت دقیقاً برابر طول اقلیدسی بردار نیست، اما معمولاً تغییرات نسبی قدرت لبه را به خوبی حفظ می‌کند.

برای مثال اگر

$$g_x=3,
\qquad
g_y=4,$$

اندازۀ دقیق برابر است با

$$M=5,$$

در حالی که تقریب سریع می‌دهد:

$$|3|+|4|=7.$$

پس مقدار عددی تغییر کرده است، اما همچنان نقطه‌ای با مؤلفه‌های گرادیان بزرگ، پاسخ بزرگی خواهد داشت.

در نتیجه اگر هدف اصلی مقایسۀ قدرت لبه‌ها یا آستانه‌گذاری باشد، این تقریب در برخی کاربردها مفید است.

#### گرادیان در تصویر گسسته

تمام روابط بالا برای تابع پیوستۀ

$$f(x,y)$$

نوشته شدند. اما تصویر دیجیتال فقط در مختصات صحیح نمونه‌برداری شده است.

پس مشتق واقعی در دسترس نیست و باید آن را با تفاضل محدود تقریب بزنیم.

برای مثال می‌توان نوشت:

$$g_x(x,y)
\approx
f(x+1,y)-f(x,y),$$

و

$$g_y(x,y)
\approx
f(x,y+1)-f(x,y).$$

یا از تفاضل مرکزی استفاده کرد:

$$g_x(x,y)
\approx
\frac{
    f(x+1,y)-f(x-1,y)
}{2},$$

$$g_y(x,y)
\approx
\frac{
    f(x,y+1)-f(x,y-1)
}{2}.$$

پس در تصویر دیجیتال، گرادیان در عمل از دو فیلتر مشتق‌گیر به دست می‌آید:

$$f
\longrightarrow
g_x,
\qquad
f
\longrightarrow
g_y.$$

سپس از این دو تصویر، دو تصویر دیگر می‌سازیم:

$$M(x,y)
=
\sqrt{
    g_x^2+g_y^2
},$$

و

$$\alpha(x,y)
=
\operatorname{atan2}(g_y,g_x).$$

بنابراین برای هر پیکسل چهار کمیت مرتبط داریم:

$$\boxed{
    f(x,y),\qquad
    g_x(x,y),\qquad
    g_y(x,y),\qquad
    M(x,y),\alpha(x,y).
}$$

#### از تفاضل ساده تا ماسک‌های Prewitt و Sobel

تفاضل دو پیکسل نسبت به نویز حساس است. به همین دلیل معمولاً مشتق را با استفاده از یک همسایگی، مثلاً $3\times3$، تخمین می‌زنیم.

یکی از ساده‌ترین انتخاب‌ها اپراتور Prewitt است. با قرارداد متداول محورهای تصویر، دو ماسک را می‌توان به صورت

$$H_x
=
\begin{bmatrix}
    -1&0&1\\
    -1&0&1\\
    -1&0&1
\end{bmatrix},
\qquad
H_y
=
\begin{bmatrix}
    -1&-1&-1\\
    0&0&0\\
    1&1&1
\end{bmatrix}$$

نوشت.

پس

$$g_x
=
H_x*f,
\qquad
g_y
=
H_y*f.$$

اپراتور Sobel به پیکسل‌های مرکزی وزن بیشتری می‌دهد:

$$H_x
=
\begin{bmatrix}
    -1&0&1\\
    -2&0&2\\
    -1&0&1
\end{bmatrix},
\qquad
H_y
=
\begin{bmatrix}
    -1&-2&-1\\
    0&0&0\\
    1&2&1
\end{bmatrix}.$$

وزن‌های

$$1,\;2,\;1$$

مقداری هموارسازی نیز ایجاد می‌کنند و به همین دلیل Sobel معمولاً نسبت به تفاضل بسیار ساده رفتار مناسب‌تری در حضور نویز دارد.

```{admonition} برداشت مفهومی
:class: note

به ماسک $H_x$ و $H_y$ نباید فقط به عنوان دو ماتریس حفظی نگاه کرد.

هرکدام در اصل می‌پرسند:

«شدت دو طرف این نقطه در یک جهت مشخص چقدر با هم فرق دارد؟»

پاسخ این دو پرسش، دو مؤلفۀ بردار گرادیان را تشکیل می‌دهد.
```

#### یک نکتۀ بسیار مهم در نام‌گذاری جهت

بین سه مفهوم باید تفاوت گذاشت:

$$\boxed{
    \text{جهت تغییر شدت}
}$$

$$\boxed{
    \text{جهت گرادیان}
}$$

و

$$\boxed{
    \text{جهت امتداد لبه}.
}$$

دو مورد اول یکسان‌اند، ولی مورد سوم $90^\circ$ با آنها اختلاف دارد.

برای مثال اگر گرادیان افقی باشد، تغییر شدت در جهت افقی اتفاق افتاده است. پس مرزی که این تغییر را ایجاد کرده معمولاً عمودی است.

به زبان ساده:

$$\boxed{
    \text{لبۀ عمودی}
    \Longrightarrow
    \text{تغییر افقی شدت}
    \Longrightarrow
    \text{گرادیان افقی}.
}$$

و برعکس:

$$\boxed{
    \text{لبۀ افقی}
    \Longrightarrow
    \text{تغییر عمودی شدت}
    \Longrightarrow
    \text{گرادیان عمودی}.
}$$

این نکته هنگام تفسیر خروجی Sobel، Canny و روش‌های اتصال لبه بسیار مهم است.

#### نویز و گرادیان

گرادیان از مشتق مرتبه اول ساخته می‌شود و مشتق نسبت به تغییرات سریع حساس است.

نویز نیز معمولاً شامل تغییرات سریع شدت در مقیاس کوچک است. بنابراین مشتق می‌تواند نویز را تقویت کند.

به همین علت در بسیاری از آشکارسازهای لبه ابتدا تصویر را هموار می‌کنیم و سپس گرادیان را محاسبه می‌کنیم:

$$f
\longrightarrow
f_s
\longrightarrow
\nabla f_s.$$

برای مثال در آشکارساز Canny ابتدا هموارسازی گاوسی انجام می‌شود و بعد اندازۀ گرادیان و جهت آن محاسبه می‌شوند.

پس یک اصل مهم در آشکارسازی لبه این است:

$$\boxed{
    \text{مشتق‌گیری}
    \;\Longrightarrow\;
    \text{حساسیت به نویز}
}$$

و در نتیجه

$$\boxed{
    \text{هموارسازی مناسب قبل از مشتق‌گیری}
}$$

می‌تواند پایداری آشکارسازی را افزایش دهد.

#### خلاصۀ مفهومی گرادیان

در هر نقطۀ تصویر:

$$\boxed{
    \nabla f
    =
    \begin{bmatrix}
        g_x\\
        g_y
    \end{bmatrix}
}$$

یک بردار است.

طول آن:

$$\boxed{
    M
    =
    \sqrt{g_x^2+g_y^2}
}$$

شدت یا قدرت تغییر را نشان می‌دهد.

زاویۀ آن:

$$\boxed{
    \alpha
    =
    \operatorname{atan2}(g_y,g_x)
}$$

جهت بیشترین افزایش شدت را نشان می‌دهد.

و جهت امتداد لبه تقریباً برابر است با

$$\boxed{
    \beta
    =
    \alpha+90^\circ
    \pmod{180^\circ}.
}$$

بنابراین:

$$\boxed{
    \begin{array}{c}
        M\text{ کوچک}
        \rightarrow
        \text{ناحیۀ تقریباً یکنواخت}
        \\[2mm]
        M\text{ بزرگ}
        \rightarrow
        \text{تغییر شدید شدت / کاندید لبه}
        \\[2mm]
        \alpha
        \rightarrow
        \text{جهت نرمال لبه}
        \\[2mm]
        \alpha+90^\circ
        \rightarrow
        \text{جهت امتداد لبه}
    \end{array}
}$$

```{admonition} نکتۀ تدریسی
:class: tip

برای توضیح گرادیان روی تخته، یک مرز عمودی بکشید که سمت چپ آن تیره و سمت راست آن روشن باشد.

ابتدا از دانشجو بپرسید:

«اگر در امتداد عمودی این مرز حرکت کنیم، شدت چقدر تغییر می‌کند؟»

پاسخ: تقریباً هیچ.

سپس بپرسید:

«اگر از چپ به راست از مرز عبور کنیم چه می‌شود؟»

پاسخ: شدت به سرعت تغییر می‌کند.

پس جهت بیشترین تغییر افقی است و بردار گرادیان افقی خواهد بود، در حالی که خود لبه عمودی است.

با همین مثال، رابطۀ

$$\text{Gradient}
    \perp
    \text{Edge}$$

بدون حفظ کردن فرمول قابل فهم می‌شود.
```

```{admonition} پرسش کلاسی / امتحانی
:class: important

در نقطه‌ای از یک تصویر داریم

$$g_x=6,
    \qquad
    g_y=8.$$

1.  اندازۀ گرادیان را به دست آورید.

2.  زاویۀ گرادیان را محاسبه کنید.

3.  جهت تقریبی امتداد لبه را تعیین کنید.

4.  توضیح دهید چرا جهت لبه و جهت گرادیان یکسان نیستند.

5.  اگر هر دو مؤلفۀ گرادیان دو برابر شوند، اندازۀ گرادیان چه تغییری می‌کند و جهت آن چه تغییری می‌کند؟
```

### ماسک‌های Roberts، Prewitt و Sobel

هر سه روش تقریب مشتق اول‌اند. تفاوت اصلی در هندسه و وزن‌دهی همسایگی است. Sobel به دلیل وزن ۲ در سطر/ستون مرکزی، اندکی هموارسازی را همراه با مشتق‌گیری انجام می‌دهد. ماسک‌های متداول Sobel: $$G_x=\begin{bmatrix}-1&-2&-1\\0&0&0\\1&2&1\end{bmatrix},\qquad
G_y=\begin{bmatrix}-1&0&1\\-2&0&2\\-1&0&1\end{bmatrix}.$$ نام‌گذاری $x$ و $y$ ممکن است در منابع با قرارداد چرخیده دیده شود؛ آنچه مهم است فهم راستای تغییر است.

```{figure} chapter-10-assets/images/fig10_01_step_derivatives.png
:name: fig-ch10-step-derivatives
:width: 88%

نمونۀ اصیل از یک لبۀ پله‌ای و پاسخ تفاضل اول و دوم. پاسخ مشتق اول در محل تغییر شدت بزرگ می‌شود و مشتق دوم در دو سوی گذار تغییر علامت می‌دهد.
```

### لاپلاسین

لاپلاسین مشتق دوم دوبعدی است: $$\nabla^2 f=\frac{\partial^2f}{\partial x^2}+\frac{\partial^2f}{\partial y^2}.$$ یک ماسک متداول: $$\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}$$ و نوع هشت‌همسایگی: $$\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}.$$ لاپلاسین جهت لبه را نمی‌دهد و نسبت به نویز حساس است، اما برای تعیین گذر از صفر و ساخت آشکارسازهای دقیق مفید است.

### هموارسازی گاوسی و LoG

برای کاهش حساسیت مشتق دوم به نویز، ابتدا تصویر با گاوسی هموار و سپس لاپلاسین گرفته می‌شود. این دو عمل را می‌توان در فیلتر Laplacian of Gaussian (LoG) ترکیب کرد: $$h(x,y)=-\frac{1}{\pi\sigma^4}\left[1-\frac{x^2+y^2}{2\sigma^2}\right]
\exp\left[-\frac{x^2+y^2}{2\sigma^2}\right].$$ پارامتر $\sigma$ مقیاس را کنترل می‌کند: $\sigma$ کوچک جزئیات ریز و نویز را نگه می‌دارد؛ $\sigma$ بزرگ ساختارهای درشت‌تر را برجسته می‌کند.

#### اعمال لاپلاسین روی تصویر هموارشده

پس از هموارسازی، مشتق دوم تصویر را با عملگر لاپلاسین محاسبه می‌کنیم:

$$\nabla^2 f_s
=
\frac{\partial^2 f_s}{\partial x^2}
+
\frac{\partial^2 f_s}{\partial y^2}.$$

اما

$$f_s=G*f.$$

پس

$$\nabla^2 f_s
=
\nabla^2(G*f).$$

از خطی بودن مشتق و کانولوشن می‌توان مشتق را روی خود کرنل گاوسی اعمال کرد:

$$\boxed{
    \nabla^2(G*f)
    =
    (\nabla^2 G)*f.
}$$

این نتیجه بسیار مهم است.

یعنی دو مرحلۀ

$$f
\longrightarrow
G*f
\longrightarrow
\nabla^2(G*f)$$

را می‌توان به صورت یک مرحلۀ فیلترکردن نوشت:

$$\boxed{
    f
    \longrightarrow
    (\nabla^2G)*f.
}$$

تابع

$$\nabla^2G$$

را Laplacian of Gaussian یا به اختصار LoG می‌نامیم.

#### استخراج ریاضی رابطۀ LoG

```{figure} chapter-10-assets/images/fig10_05_log_zero_crossing.png
:name: fig-ch10-log-zero-crossing
:width: 82%

مقطع شعاعی LoG برای یک $\sigma$ نمونه. عبور از صفر در $r=\sqrt{2}\sigma$ نشان می‌دهد چرا پاسخ LoG در اطراف ساختارها تغییر علامت می‌دهد.
```

از گاوسی نرمال‌شده شروع می‌کنیم:

$$G(x,y)
=
\frac{1}{2\pi\sigma^2}
\exp
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right].$$

برای کوتاه‌شدن روابط، تعریف می‌کنیم

$$C=
\frac{1}{2\pi\sigma^2},$$

و بنابراین

$$G(x,y)
=
C
\exp
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right].$$

##### مشتق اول نسبت به $x$
ابتدا نسبت به $x$ مشتق می‌گیریم:

$$\frac{\partial G}{\partial x}
=
C
\exp
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right]
\frac{\partial}{\partial x}
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right].$$

مشتق عبارت داخل توان برابر است با

$$\frac{\partial}{\partial x}
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right]
=
-\frac{x}{\sigma^2}.$$

پس

$$\frac{\partial G}{\partial x}
=
-\frac{x}{\sigma^2}
C
\exp
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right].$$

ولی عبارت

$$C
\exp
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right]$$

همان $G(x,y)$ است. بنابراین

$$\boxed{
    \frac{\partial G}{\partial x}
    =
    -\frac{x}{\sigma^2}G.
}$$

##### مشتق دوم نسبت به $x$
اکنون دوباره نسبت به $x$ مشتق می‌گیریم:

$$\frac{\partial^2G}{\partial x^2}
=
\frac{\partial}{\partial x}
\left(
-\frac{x}{\sigma^2}G
\right).$$

با استفاده از قاعدۀ مشتق حاصل‌ضرب:

$$\frac{\partial^2G}{\partial x^2}
=
-\frac{1}{\sigma^2}G
-
\frac{x}{\sigma^2}
\frac{\partial G}{\partial x}.$$

از رابطۀ قبلی

$$\frac{\partial G}{\partial x}
=
-\frac{x}{\sigma^2}G$$

استفاده می‌کنیم:

$$\frac{\partial^2G}{\partial x^2}
=
-\frac{1}{\sigma^2}G
+
\frac{x^2}{\sigma^4}G.$$

پس

$$\boxed{
    \frac{\partial^2G}{\partial x^2}
    =
    \left(
    \frac{x^2}{\sigma^4}
    -
    \frac{1}{\sigma^2}
    \right)G.
}$$

##### مشتق دوم نسبت به $y$
کاملاً مشابه داریم

$$\boxed{
    \frac{\partial^2G}{\partial y^2}
    =
    \left(
    \frac{y^2}{\sigma^4}
    -
    \frac{1}{\sigma^2}
    \right)G.
}$$

##### تشکیل لاپلاسین
تعریف لاپلاسین در دو بعد:

$$\nabla^2G
=
\frac{\partial^2G}{\partial x^2}
+
\frac{\partial^2G}{\partial y^2}.$$

پس

$$\nabla^2G
=
\left(
\frac{x^2}{\sigma^4}
-
\frac{1}{\sigma^2}
\right)G
+
\left(
\frac{y^2}{\sigma^4}
-
\frac{1}{\sigma^2}
\right)G.$$

جملات را جمع می‌کنیم:

$$\nabla^2G
=
\left[
\frac{x^2+y^2}{\sigma^4}
-
\frac{2}{\sigma^2}
\right]G.$$

بنابراین

$$\boxed{
    \nabla^2G
    =
    \frac{x^2+y^2-2\sigma^2}{\sigma^4}
    G.
}$$

اکنون مقدار خود $G$ را جایگذاری می‌کنیم:

$$\nabla^2G
=
\frac{x^2+y^2-2\sigma^2}{\sigma^4}
\frac{1}{2\pi\sigma^2}
\exp
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right].$$

پس

$$\nabla^2G
=
\frac{x^2+y^2-2\sigma^2}
{2\pi\sigma^6}
\exp
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right].$$

حال صورت را به شکل دیگری می‌نویسیم:

$$x^2+y^2-2\sigma^2
=
-2\sigma^2
\left[
1-
\frac{x^2+y^2}{2\sigma^2}
\right].$$

بنابراین

$$\nabla^2G
=
-\frac{2\sigma^2}
{2\pi\sigma^6}
\left[
1-
\frac{x^2+y^2}{2\sigma^2}
\right]
\exp
\left[
-\frac{x^2+y^2}{2\sigma^2}
\right].$$

با ساده‌سازی:

$$\boxed{
    \nabla^2G(x,y)
    =
    -\frac{1}{\pi\sigma^4}
    \left[
    1-
    \frac{x^2+y^2}{2\sigma^2}
    \right]
    \exp
    \left[
    -\frac{x^2+y^2}{2\sigma^2}
    \right].
}$$

این همان تابع Laplacian of Gaussian است.

#### رابطۀ نهایی چه چیزی به ما می‌گوید؟

رابطۀ LoG از سه بخش تشکیل شده است:

$$\nabla^2G(x,y)
=
\underbrace{
    -\frac{1}{\pi\sigma^4}
}_{\text{ضریب مقیاس}}
\;
\underbrace{
    \left[
    1-\frac{x^2+y^2}{2\sigma^2}
    \right]
}_{\text{تغییر علامت}}
\;
\underbrace{
    \exp
    \left[
    -\frac{x^2+y^2}{2\sigma^2}
    \right]
}_{\text{پوش گاوسی}}.$$

بخش نمایی باعث می‌شود اثر فیلتر با دورشدن از مرکز کاهش یابد.

عامل

$$1-\frac{x^2+y^2}{2\sigma^2}$$

باعث می‌شود پاسخ در یک شعاع مشخص علامت عوض کند.

برای یافتن محل تغییر علامت کافی است بنویسیم

$$1-\frac{x^2+y^2}{2\sigma^2}=0.$$

بنابراین

$$x^2+y^2
=
2\sigma^2.$$

اگر

$$r^2=x^2+y^2$$

باشد:

$$r^2=2\sigma^2$$

و در نتیجه

$$\boxed{
    r=\sqrt{2}\,\sigma.
}$$

پس LoG در اطراف مرکز یک ناحیۀ یک‌علامت و در بیرون آن ناحیه‌ای با علامت مخالف دارد و مرز بین آنها در شعاع

$$\sqrt{2}\sigma$$

قرار می‌گیرد.

این تغییر علامت منشأ شکل معروف Mexican Hat در نمایش سه‌بعدی LoG است.

#### نقش LoG در آشکارسازی لبه

اگر تصویر را با LoG فیلتر کنیم:

$$g(x,y)
=
(\nabla^2G)*f,$$

در محل‌هایی که شدت تقریباً ثابت است، پاسخ تقریباً صفر خواهد بود.

در اطراف یک تغییر شدت، پاسخ مشتق دوم معمولاً در یک طرف لبه یک علامت و در طرف دیگر علامت مخالف دارد.

بنابراین محل لبه را می‌توان از **عبور از صفر** یا Zero Crossing پاسخ LoG پیدا کرد:

$$\boxed{
    g(x,y)
    \text{ از مثبت به منفی یا از منفی به مثبت عبور کند}
    \Rightarrow
    \text{کاندید لبه}.
}$$

پس کل مسیر آشکارسازی به صورت

$$\boxed{
    f
    \longrightarrow
    G*f
    \longrightarrow
    \nabla^2(G*f)
    \longrightarrow
    \text{Zero Crossing}
    \longrightarrow
    \text{لبه}
}$$

است.

و به دلیل خطی بودن مشتق و کانولوشن می‌توان همان مسیر را به صورت

$$\boxed{
    f
    \longrightarrow
    (\nabla^2G)*f
    \longrightarrow
    \text{Zero Crossing}
}$$

پیاده‌سازی کرد.

```{admonition} برداشت مفهومی
:class: note

نقش دو بخش LoG را جداگانه به خاطر بسپارید:

$$\boxed{
        G
        \rightarrow
        \text{کاهش نویز و تعیین مقیاس}
    }$$

و

$$\boxed{
        \nabla^2
        \rightarrow
        \text{آشکارسازی تغییرات شدت با مشتق دوم}.
    }$$

پس LoG در واقع تلاش می‌کند دو خواستۀ متضاد را با هم جمع کند: پیش از مشتق‌گیری نویز را کاهش دهد، اما پس از آن تغییرات مهم شدت را آشکار کند.
```

### آشکارساز Canny: منطق مرحله‌به‌مرحله

Canny را بهتر است یک «زنجیرۀ تصمیم» بدانیم نه یک ماسک واحد. مراحل اصلی عبارت‌اند از: هموارسازی گاوسی، محاسبۀ گرادیان، نازک‌سازی با nonmaximum suppression، آستانه‌گذاری دوگانه و اتصال لبه‌ها با hysteresis.

در nonmaximum suppression، مقدار گرادیان فقط وقتی نگه داشته می‌شود که در راستای گرادیان از دو همسایۀ خود بزرگ‌تر باشد. نتیجه، لبه‌های تقریباً یک‌پیکسلی است. سپس دو آستانه $T_H$ و $T_L$ داریم: نقاط بالاتر از $T_H$ لبۀ قوی، بین دو آستانه لبۀ ضعیف، و پایین‌تر از $T_L$ حذف می‌شوند. لبۀ ضعیف تنها وقتی باقی می‌ماند که به لبۀ قوی متصل باشد.

```{figure} chapter-10-assets/images/fig10_06_canny_pipeline.png
:name: fig-ch10-canny-pipeline
:width: 100%

آزمایش بازتولیدپذیر روی تصویر مصنوعی: ورودی نویزی، هموارسازی گاوسی، اندازۀ گرادیان و ماسک لبه‌های قوی. شکل برای توضیح منطق زنجیرۀ Canny بازطراحی شده است.
```

## آستانه‌گذاری

### ایدۀ پایه

اگر هیستوگرام تصویر شامل دو جمعیت نسبتاً جدا، مثلاً شیء و زمینه، باشد می‌توان با آستانه $T$ تصویر را دودویی کرد: $$g(x,y)=\begin{cases}
1,&f(x,y)>T\\
0,&f(x,y)\le T.
\end{cases}$$ این ساده‌ترین شکل قطعه‌بندی است. اما موفقیت آن وابسته به جدایی آماری کلاس‌ها و یکنواختی روشنایی است.

```{figure} chapter-10-assets/images/fig10_07_otsu.png
:name: fig-ch10-threshold-otsu
:width: 95%

هیستوگرام دومدی مصنوعی و واریانس بین‌کلاسی Otsu. خط‌چین آستانه‌ای را نشان می‌دهد که $\sigma_B^2(k)$ را بیشینه می‌کند.
```

### آستانۀ سراسری و آستانۀ متغیر

در آستانۀ سراسری یک $T$ برای کل تصویر داریم. اگر روشنایی زمینه در نقاط مختلف تغییر کند، یک آستانه کافی نیست. در آستانه‌گذاری محلی یا تطبیقی، $T=T(x,y)$ و از آمار همسایگی مانند میانگین، میانه یا انحراف معیار محلی استفاده می‌شود.

### اثر نویز و روشنایی نامساوی

دو عامل کلاسیک شکست آستانه‌گذاری، نویز و سایه/گرادیان روشنایی‌اند. نویز پهنای قله‌های هیستوگرام را افزایش می‌دهد و هم‌پوشانی کلاس‌ها را بیشتر می‌کند. روشنایی نامساوی نیز ممکن است یک شیء واحد را در بخش‌های مختلف به دو کلاس متفاوت ببرد. پیش‌پردازش هموارسازی و تصحیح زمینه می‌تواند مسئله را ساده کند.

### آستانه‌گذاری تکراری

یک روش ساده این است که ابتدا $T$ حدس زده شود، پیکسل‌ها به دو گروه تقسیم شوند، میانگین گروه‌ها $\mu_1,\mu_2$ محاسبه و آستانۀ جدید برابر $$T_{new}=\frac{\mu_1+\mu_2}{2}$$ قرار داده شود. این روند تا کوچک شدن تغییر $T$ ادامه می‌یابد.

### روش Otsu: مبنای آماری و استخراج کامل روابط

روش Otsu یک روش آستانه‌گذاری سراسری است که آستانه را مستقیماً از هیستوگرام تصویر تعیین می‌کند.

ایدهٔ اصلی آن این است که با انتخاب یک آستانه، پیکسل‌های تصویر را به دو کلاس تقسیم کنیم، به گونه‌ای که:

$$\boxed{
    \text{پیکسل‌های داخل هر کلاس تا حد ممکن به یکدیگر شبیه باشند}
}$$

و در عین حال

$$\boxed{
    \text{دو کلاس تا حد ممکن از یکدیگر جدا باشند}.
}$$

این ایده از نظر آماری به دو بیان معادل منجر می‌شود:

$$\boxed{
    \text{کمینه‌کردن پراکندگی داخل کلاس‌ها}
}$$

یا

$$\boxed{
    \text{بیشینه‌کردن جدایی بین دو کلاس}.
}$$

روش Otsu معمولاً از بیان دوم استفاده می‌کند.

#### هیستوگرام به عنوان توزیع احتمال شدت

فرض کنید تصویر دارای $L$ سطح شدت باشد:

$$0,1,2,\ldots,L-1.$$

برای یک تصویر 8 بیتی:

$$L=256.$$

اگر $n_i$ تعداد پیکسل‌هایی باشد که شدت آنها برابر $i$ است و تعداد کل پیکسل‌ها برابر

$$N=\sum_{i=0}^{L-1}n_i$$

باشد، هیستوگرام نرمال‌شده را به صورت

$$\boxed{
    p_i=\frac{n_i}{N}
}$$

تعریف می‌کنیم.

پس

$$p_i\geq0$$

و

$$\boxed{
    \sum_{i=0}^{L-1}p_i=1.
}$$

بنابراین می‌توان $p_i$ را احتمال تجربی مشاهدهٔ شدت $i$ در تصویر دانست.

#### تقسیم تصویر به دو کلاس با آستانه $k$

یک آستانهٔ کاندید $k$ را در نظر می‌گیریم:

$$0\leq k<L-1.$$

آنگاه دو کلاس تشکیل می‌شوند:

$$\boxed{
    C_1(k)=\{0,1,\ldots,k\}
}$$

و

$$\boxed{
    C_2(k)=\{k+1,k+2,\ldots,L-1\}.
}$$

احتمال تعلق یک پیکسل به کلاس اول:

$$\boxed{
    P_1(k)
    =
    \sum_{i=0}^{k}p_i
}$$

و برای کلاس دوم:

$$\boxed{
    P_2(k)
    =
    \sum_{i=k+1}^{L-1}p_i
    =
    1-P_1(k).
}$$

پس

$$\boxed{
    P_1(k)+P_2(k)=1.
}$$

در واقع $P_1$ و $P_2$ فقط نشان می‌دهند چه سهمی از کل پیکسل‌ها در هر کلاس قرار گرفته است.

#### میانگین شدت هر کلاس

میانگین شدت کلاس اول برابر است با

$$\boxed{
    m_1(k)
    =
    \frac{
        \displaystyle\sum_{i=0}^{k}i\,p_i
    }{
        P_1(k)
    }.
}$$

به همین ترتیب برای کلاس دوم:

$$\boxed{
    m_2(k)
    =
    \frac{
        \displaystyle\sum_{i=k+1}^{L-1}i\,p_i
    }{
        P_2(k)
    }.
}$$

این روابط فقط زمانی معنی دارند که

$$0<P_1(k)<1,$$

زیرا در غیر این صورت یکی از کلاس‌ها خالی خواهد بود.

از تعریف $m_1(k)$ داریم

$$m_1(k)P_1(k)
=
\sum_{i=0}^{k}i\,p_i.$$

و چون

$$P_1(k)
=
\sum_{i=0}^{k}p_i,$$

نتیجه می‌شود

$$\sum_{i=0}^{k}
\left(i-m_1(k)\right)p_i
=
\sum_{i=0}^{k}i\,p_i
-
m_1(k)\sum_{i=0}^{k}p_i
=0.$$

پس

$$\boxed{
    \sum_{i=0}^{k}
    \left(i-m_1(k)\right)p_i
    =0.
}$$

این همان خاصیت معروف میانگین است: مجموع انحراف‌ها از میانگین، با وزن احتمال‌ها، صفر است.

برای کلاس دوم نیز دقیقاً داریم

$$\boxed{
    \sum_{i=k+1}^{L-1}
    \left(i-m_2(k)\right)p_i
    =0.
}$$

#### میانگین کل تصویر

میانگین کل شدت‌های تصویر برابر است با

$$\boxed{
    m_G
    =
    \sum_{i=0}^{L-1}i\,p_i.
}$$

چون تمام پیکسل‌های تصویر یا در کلاس اول‌اند یا در کلاس دوم، می‌توان این مجموع را به دو قسمت تقسیم کرد:

$$m_G
=
\sum_{i=0}^{k}i\,p_i
+
\sum_{i=k+1}^{L-1}i\,p_i.$$

ولی

$$\sum_{i=0}^{k}i\,p_i
=
P_1m_1$$

و

$$\sum_{i=k+1}^{L-1}i\,p_i
=
P_2m_2.$$

پس

$$\boxed{
    m_G
    =
    P_1m_1+P_2m_2.
}$$

یعنی میانگین کل تصویر، میانگین وزن‌دار میانگین دو کلاس است.

#### واریانس هر کلاس

واریانس شدت در کلاس اول برابر است با

$$\boxed{
    \sigma_1^2
    =
    \frac{
        \displaystyle
        \sum_{i=0}^{k}
        (i-m_1)^2p_i
    }{
        P_1
    }.
}$$

بنابراین با ضرب دو طرف در $P_1$:

$$\boxed{
    P_1\sigma_1^2
    =
    \sum_{i=0}^{k}
    (i-m_1)^2p_i.
}$$

به همین ترتیب:

$$\boxed{
    \sigma_2^2
    =
    \frac{
        \displaystyle
        \sum_{i=k+1}^{L-1}
        (i-m_2)^2p_i
    }{
        P_2
    }
}$$

و بنابراین

$$\boxed{
    P_2\sigma_2^2
    =
    \sum_{i=k+1}^{L-1}
    (i-m_2)^2p_i.
}$$

پس $P_1\sigma_1^2$ سهم کلاس اول از پراکندگی داخلی و $P_2\sigma_2^2$ سهم کلاس دوم از پراکندگی داخلی است.

#### واریانس درون‌کلاسی

واریانس درون‌کلاسی را به صورت

$$\boxed{
    \sigma_W^2
    =
    P_1\sigma_1^2
    +
    P_2\sigma_2^2
}$$

تعریف می‌کنیم.

یعنی:

$$\sigma_W^2
=
\sum_{i=0}^{k}(i-m_1)^2p_i
+
\sum_{i=k+1}^{L-1}(i-m_2)^2p_i.$$

این کمیت می‌گوید اعضای هر کلاس تا چه اندازه حول میانگین همان کلاس پراکنده‌اند.

اگر آستانه مناسب باشد، انتظار داریم هر کلاس نسبتاً همگن باشد و در نتیجه

$$\sigma_W^2$$

کوچک شود.

بنابراین از یک دیدگاه می‌توان آستانهٔ مطلوب را چنین تعریف کرد:

$$\boxed{
    k^\star
    =
    \arg\min_k
    \sigma_W^2(k).
}$$

#### واریانس کل تصویر

واریانس کل تصویر نسبت به میانگین سراسری $m_G$ برابر است با

$$\boxed{
    \sigma_G^2
    =
    \sum_{i=0}^{L-1}
    (i-m_G)^2p_i.
}$$

این مقدار فقط به خود تصویر بستگی دارد و به انتخاب آستانه وابسته نیست.

اکنون مجموع را به دو کلاس تقسیم می‌کنیم:

$$\sigma_G^2
=
\sum_{i=0}^{k}
(i-m_G)^2p_i
+
\sum_{i=k+1}^{L-1}
(i-m_G)^2p_i.$$

برای فهم روش Otsu باید ببینیم هر یک از این دو قسمت چگونه تجزیه می‌شود.

#### سهم کلاس اول در واریانس کل

برای کلاس اول داریم

$$\sum_{i=0}^{k}
(i-m_G)^2p_i.$$

برای ارتباط دادن $m_G$ با میانگین خود کلاس، $m_1$ را داخل عبارت اضافه و کم می‌کنیم:

$$i-m_G
=
(i-m_1)+(m_1-m_G).$$

پس

$$(i-m_G)^2
=
\left[
(i-m_1)+(m_1-m_G)
\right]^2.$$

با بسط مربع:

$$(i-m_G)^2
=
(i-m_1)^2
+
2(i-m_1)(m_1-m_G)
+
(m_1-m_G)^2.$$

اکنون برای تمام شدت‌های کلاس اول جمع می‌کنیم:

$$\begin{aligned}
    \sum_{i=0}^{k}(i-m_G)^2p_i
    ={}&
    \sum_{i=0}^{k}(i-m_1)^2p_i
    \\
    &+
    2(m_1-m_G)
    \sum_{i=0}^{k}(i-m_1)p_i
    \\
    &+
    (m_1-m_G)^2
    \sum_{i=0}^{k}p_i.
\end{aligned}$$

جملهٔ میانی صفر است، زیرا قبلاً نشان دادیم:

$$\sum_{i=0}^{k}(i-m_1)p_i=0.$$

پس:

$$\sum_{i=0}^{k}(i-m_G)^2p_i
=
\sum_{i=0}^{k}(i-m_1)^2p_i
+
(m_1-m_G)^2
\sum_{i=0}^{k}p_i.$$

ولی

$$\sum_{i=0}^{k}(i-m_1)^2p_i
=
P_1\sigma_1^2$$

و

$$\sum_{i=0}^{k}p_i=P_1.$$

بنابراین:

$$\boxed{
    \sum_{i=0}^{k}(i-m_G)^2p_i
    =
    P_1\sigma_1^2
    +
    P_1(m_1-m_G)^2.
}$$

این رابطه معنای بسیار روشنی دارد.

سهم کلاس اول در واریانس کل از دو قسمت تشکیل شده است:

$$\boxed{
    P_1\sigma_1^2
}$$

که نشان‌دهندهٔ پراکندگی اعضای کلاس اول حول میانگین خود کلاس است،

و

$$\boxed{
    P_1(m_1-m_G)^2
}$$

که نشان می‌دهد میانگین کلاس اول تا چه اندازه از میانگین کل تصویر فاصله دارد.

پس:

$$\boxed{
    \text{سهم کلاس اول در واریانس کل}
    =
    \text{پراکندگی داخل کلاس}
    +
    \text{فاصلهٔ مرکز کلاس از مرکز کل}.
}$$

#### سهم کلاس دوم در واریانس کل

کاملاً مشابه کلاس اول داریم:

$$\boxed{
    \sum_{i=k+1}^{L-1}
    (i-m_G)^2p_i
    =
    P_2\sigma_2^2
    +
    P_2(m_2-m_G)^2.
}$$

#### تجزیهٔ اصلی واریانس

اکنون دو سهم را با هم جمع می‌کنیم:

$$\begin{aligned}
    \sigma_G^2
    ={}&
    P_1\sigma_1^2
    +
    P_2\sigma_2^2
    \\
    &+
    P_1(m_1-m_G)^2
    +
    P_2(m_2-m_G)^2.
\end{aligned}$$

دو جملهٔ اول همان واریانس درون‌کلاسی‌اند:

$$\boxed{
    \sigma_W^2
    =
    P_1\sigma_1^2
    +
    P_2\sigma_2^2.
}$$

دو جملهٔ بعدی را واریانس بین‌کلاسی تعریف می‌کنیم:

$$\boxed{
    \sigma_B^2
    =
    P_1(m_1-m_G)^2
    +
    P_2(m_2-m_G)^2.
}$$

پس به رابطۀ بنیادی می‌رسیم:

$$\boxed{
    \sigma_G^2
    =
    \sigma_W^2
    +
    \sigma_B^2.
}$$

این رابطه اساس ریاضی روش Otsu است.

#### معنای واریانس بین‌کلاسی

رابطهٔ

$$\sigma_B^2
=
P_1(m_1-m_G)^2
+
P_2(m_2-m_G)^2$$

می‌گوید میانگین هر کلاس چه اندازه از میانگین کل تصویر فاصله دارد.

اگر دو کلاس تقریباً یک میانگین داشته باشند، یعنی

$$m_1\approx m_2,$$

جدایی آنها ضعیف است.

در مقابل، اگر دو میانگین از یکدیگر فاصله زیادی داشته باشند، جدایی دو کلاس زیاد است.

پس $\sigma_B^2$ معیاری از **جدایی کلاس‌ها** است.

#### چرا بیشینه‌کردن واریانس بین‌کلاسی معادل کمینه‌کردن واریانس درون‌کلاسی است؟

از رابطۀ

$$\sigma_G^2
=
\sigma_W^2
+
\sigma_B^2$$

داریم

$$\sigma_W^2
=
\sigma_G^2-\sigma_B^2.$$

از آنجا که

$$\sigma_G^2$$

برای تصویر ثابت است، هرچه

$$\sigma_B^2$$

بزرگ‌تر شود،

$$\sigma_W^2$$

کوچک‌تر خواهد شد.

بنابراین:

$$\boxed{
    \arg\min_k\sigma_W^2(k)
    =
    \arg\max_k\sigma_B^2(k).
}$$

روش Otsu از صورت دوم استفاده می‌کند.

#### استخراج رابطۀ معروف Otsu

اکنون می‌خواهیم

$$\sigma_B^2
=
P_1(m_1-m_G)^2
+
P_2(m_2-m_G)^2$$

را ساده کنیم.

می‌دانیم

$$m_G=P_1m_1+P_2m_2.$$

پس

$$\begin{aligned}
    m_1-m_G
    &=
    m_1-P_1m_1-P_2m_2
    \\
    &=
    (1-P_1)m_1-P_2m_2.
\end{aligned}$$

ولی

$$1-P_1=P_2.$$

بنابراین:

$$\boxed{
    m_1-m_G
    =
    P_2(m_1-m_2).
}$$

به طور مشابه:

$$\begin{aligned}
    m_2-m_G
    &=
    m_2-P_1m_1-P_2m_2
    \\
    &=
    (1-P_2)m_2-P_1m_1.
\end{aligned}$$

چون

$$1-P_2=P_1,$$

داریم:

$$\boxed{
    m_2-m_G
    =
    -P_1(m_1-m_2).
}$$

اکنون این دو رابطه را در $\sigma_B^2$ قرار می‌دهیم:

$$\begin{aligned}
    \sigma_B^2
    ={}&
    P_1
    \left[
    P_2(m_1-m_2)
    \right]^2
    \\
    &+
    P_2
    \left[
    -P_1(m_1-m_2)
    \right]^2.
\end{aligned}$$

پس:

$$\sigma_B^2
=
P_1P_2^2(m_1-m_2)^2
+
P_2P_1^2(m_1-m_2)^2.$$

عامل مشترک می‌گیریم:

$$\sigma_B^2
=
P_1P_2(m_1-m_2)^2
(P_1+P_2).$$

ولی

$$P_1+P_2=1.$$

بنابراین:

$$\boxed{
    \sigma_B^2(k)
    =
    P_1(k)P_2(k)
    \left[
    m_1(k)-m_2(k)
    \right]^2.
}$$

این همان رابطۀ مشهور روش Otsu است.

#### تفسیر رابطۀ نهایی

رابطۀ

$$\sigma_B^2
=
P_1P_2(m_1-m_2)^2$$

دو جزء مهم دارد.

جزء اول:

$$(m_1-m_2)^2$$

فاصلهٔ میانگین دو کلاس را اندازه می‌گیرد.

هرچه

$$|m_1-m_2|$$

بزرگ‌تر باشد، جدایی شدت دو کلاس بیشتر است.

جزء دوم:

$$P_1P_2$$

به اندازهٔ نسبی کلاس‌ها مربوط است.

اگر یکی از کلاس‌ها تقریباً خالی باشد، مثلاً

$$P_1\approx0,$$

آنگاه

$$P_1P_2\approx0.$$

پس حتی اگر دو میانگین ظاهراً دور باشند، چنین تقسیم‌بندی‌ای امتیاز زیادی نخواهد گرفت.

بنابراین Otsu فقط فاصلۀ میانگین‌ها را زیاد نمی‌کند، بلکه وزن آماری دو کلاس را نیز در نظر می‌گیرد.

#### فرمول محاسباتی سریع

برای پیاده‌سازی بهتر است برای هر آستانه $m_1$ و $m_2$ را از ابتدا محاسبه نکنیم.

میانگین تجمعی را تعریف می‌کنیم:

$$\boxed{
    m(k)
    =
    \sum_{i=0}^{k}i\,p_i.
}$$

در این صورت

$$\boxed{
    m_1(k)
    =
    \frac{m(k)}{P_1(k)}.
}$$

از طرف دیگر:

$$m_G
=
m(k)
+
\sum_{i=k+1}^{L-1}i\,p_i.$$

پس

$$\boxed{
    m_2(k)
    =
    \frac{
        m_G-m(k)
    }{
        P_2(k)
    }.
}$$

اکنون:

$$m_1-m_2
=
\frac{m}{P_1}
-
\frac{m_G-m}{P_2}.$$

با مخرج مشترک:

$$m_1-m_2
=
\frac{
    mP_2-P_1m_G+P_1m
}{
    P_1P_2
}.$$

چون

$$P_1+P_2=1,$$

داریم

$$mP_2+P_1m=m.$$

پس:

$$\boxed{
    m_1-m_2
    =
    \frac{
        m(k)-P_1(k)m_G
    }{
        P_1(k)P_2(k)
    }.
}$$

با جایگذاری در رابطۀ واریانس بین‌کلاسی:

$$\sigma_B^2
=
P_1P_2(m_1-m_2)^2,$$

به دست می‌آید:

$$\boxed{
    \sigma_B^2(k)
    =
    \frac{
        \left[
        m(k)-P_1(k)m_G
        \right]^2
    }{
        P_1(k)P_2(k)
    }.
}$$

و چون

$$P_2(k)=1-P_1(k),$$

می‌توان نوشت:

$$\boxed{
    \sigma_B^2(k)
    =
    \frac{
        \left[
        m_G P_1(k)-m(k)
        \right]^2
    }{
        P_1(k)\left[1-P_1(k)\right]
    }.
}$$

این فرم برای پیاده‌سازی بسیار مناسب است.

#### انتخاب آستانۀ بهینه

برای تمام آستانه‌های ممکن مقدار

$$\sigma_B^2(k)$$

را محاسبه می‌کنیم و آستانه‌ای را انتخاب می‌کنیم که این مقدار را بیشینه کند:

$$\boxed{
    k^\star
    =
    \arg\max_{k}
    \sigma_B^2(k).
}$$

فقط مقادیری معتبرند که

$$0<P_1(k)<1.$$

پس از یافتن $k^\star$، تصویر دودویی به صورت

$$\boxed{
    g(x,y)
    =
    \begin{cases}
        0,
        &
        f(x,y)\leq k^\star,
        \\[2mm]
        1,
        &
        f(x,y)>k^\star
    \end{cases}
}$$

تشکیل می‌شود.

#### مثال عددی ساده

```{figure} chapter-10-assets/images/fig10_07_otsu.png
:name: fig-ch10-otsu-variance
:width: 95%

مثال تصویری مکمل: بیشینۀ واریانس بین‌کلاسی با آستانۀ انتخابی Otsu متناظر است.
```

فرض کنید تصویر فقط شش سطح شدت داشته باشد:

$$0,1,2,3,4,5$$

و هیستوگرام آن به صورت زیر باشد:

$$\begin{array}{c|cccccc}
    i
    &
    0&1&2&3&4&5
    \\
    \hline
    n_i
    &
    4&2&1&1&2&4
\end{array}$$

تعداد کل پیکسل‌ها:

$$N=14.$$

پس:

$$p_i=\frac{n_i}{14}.$$

میانگین کل:

$$m_G
=
\frac{
    0(4)+1(2)+2(1)+3(1)+4(2)+5(4)
}{
    14
}
=
2.5.$$

اکنون آستانۀ $k=2$ را در نظر می‌گیریم.

کلاس اول:

$$C_1=\{0,1,2\}$$

و کلاس دوم:

$$C_2=\{3,4,5\}.$$

احتمال کلاس اول:

$$P_1
=
\frac{4+2+1}{14}
=
\frac{7}{14}
=
0.5.$$

پس:

$$P_2=0.5.$$

میانگین کلاس اول:

$$m_1
=
\frac{
    0(4)+1(2)+2(1)
}{
    7
}
=
\frac{4}{7}
\approx0.5714.$$

میانگین کلاس دوم:

$$m_2
=
\frac{
    3(1)+4(2)+5(4)
}{
    7
}
=
\frac{31}{7}
\approx4.4286.$$

پس:

$$\sigma_B^2(2)
=
P_1P_2(m_1-m_2)^2.$$

بنابراین:

$$\sigma_B^2(2)
=
(0.5)(0.5)
(0.5714-4.4286)^2$$

و در نتیجه:

$$\boxed{
    \sigma_B^2(2)
    \approx3.7194.
}$$

اگر همین محاسبه برای تمام آستانه‌ها انجام شود:

$$\begin{array}{c|c}
    k
    &
    \sigma_B^2(k)
    \\
    \hline
    0 & 2.5000\\
    1 & 3.5208\\
    2 & 3.7194\\
    3 & 3.5208\\
    4 & 2.5000
\end{array}$$

بیشترین مقدار برای

$$\boxed{
    k^\star=2
}$$

به دست می‌آید.

پس آستانۀ Otsu در این مثال برابر 2 است.

#### ضریب جدایی

می‌توان کیفیت جدایی کلاس‌ها را با نسبت

$$\boxed{
    \eta(k)
    =
    \frac{
        \sigma_B^2(k)
    }{
        \sigma_G^2
    }
}$$

نیز بیان کرد.

از آنجا که

$$\sigma_G^2
=
\sigma_W^2+\sigma_B^2,$$

داریم

$$\boxed{
    0\leq\eta(k)\leq1.
}$$

مقدار نزدیک صفر نشان‌دهندۀ جدایی ضعیف و مقدار نزدیک یک نشان‌دهندۀ جدایی قوی‌تر دو کلاس است.

#### یک سوءبرداشت رایج

روش Otsu مستقیماً درۀ بین دو قلۀ هیستوگرام را پیدا نمی‌کند.

معیار واقعی آن

$$\boxed{
    P_1P_2(m_1-m_2)^2
}$$

است.

در تصاویر دارای دو مد مشخص، آستانۀ حاصل اغلب در نزدیکی درۀ بین دو مد قرار می‌گیرد، اما این نتیجهٔ بیشینه‌شدن جدایی آماری دو کلاس است، نه جست‌وجوی مستقیم کم‌ارتفاع‌ترین نقطۀ هیستوگرام.

#### شرایط مناسب و محدودیت‌ها

روش Otsu هنگامی عملکرد خوبی دارد که بتوان تصویر را با یک آستانۀ سراسری به دو گروه نسبتاً متمایز تقسیم کرد.

این روش ممکن است در شرایط زیر عملکرد ضعیف‌تری داشته باشد:

-   روشنایی در سراسر تصویر یکنواخت نباشد؛

-   توزیع شدت دو کلاس هم‌پوشانی زیادی داشته باشد؛

-   نویز شدید باشد؛

-   یکی از کلاس‌ها نسبت به دیگری بسیار کوچک باشد؛

-   تصویر ذاتاً بیش از دو کلاس مهم داشته باشد.

در چنین شرایطی، تصحیح روشنایی، هموارسازی، آستانه‌گذاری محلی یا روش‌های چندآستانه‌ای می‌توانند مناسب‌تر باشند.

#### الگوریتم نهایی

مراحل روش Otsu را می‌توان چنین خلاصه کرد:

1.  هیستوگرام نرمال‌شده را محاسبه کنید:

    $$p_i=\frac{n_i}{N}.$$

2.  میانگین کل را محاسبه کنید:

    $$m_G
        =
        \sum_{i=0}^{L-1}i\,p_i.$$

3.  برای هر آستانه $k$، محاسبه کنید:

    $$P_1(k)
        =
        \sum_{i=0}^{k}p_i$$

    و

    $$m(k)
        =
        \sum_{i=0}^{k}i\,p_i.$$

4.  اگر

    $$P_1(k)=0
        \qquad\text{یا}\qquad
        P_1(k)=1,$$

    آن آستانه را نادیده بگیرید.

5.  واریانس بین‌کلاسی را محاسبه کنید:

    $$\sigma_B^2(k)
        =
        \frac{
            [m_GP_1(k)-m(k)]^2
        }{
            P_1(k)[1-P_1(k)]
        }.$$

6.  آستانه‌ای را انتخاب کنید که

    $$\sigma_B^2(k)$$

    را بیشینه کند.

در نتیجه:

$$\boxed{
    k^\star
    =
    \arg\max_k
    \sigma_B^2(k).
}$$

```{admonition} برداشت مفهومی
:class: note

مبنای ریاضی روش Otsu در رابطۀ زیر خلاصه می‌شود:

$$\boxed{
        \sigma_G^2
        =
        \sigma_W^2
        +
        \sigma_B^2.
    }$$

و چون واریانس کل تصویر ثابت است:

$$\boxed{
        \min\sigma_W^2
        \quad\Longleftrightarrow\quad
        \max\sigma_B^2.
    }$$

برای دو کلاس:

$$\boxed{
        \sigma_B^2
        =
        P_1P_2(m_1-m_2)^2.
    }$$

پس آستانۀ Otsu آستانه‌ای است که کلاس‌های حاصل را از نظر شدت تا حد ممکن از یکدیگر جدا می‌کند.
```

#### ارتباط با روش‌های آستانه‌گذاری محلی

روش استاندارد Otsu یک آستانۀ سراسری تولید می‌کند:

$$k^\star
=
\text{یک عدد برای کل تصویر}.$$

اما می‌توان همین معیار را در همسایگی‌های محلی نیز اعمال کرد.

در این حالت برای هر ناحیه یک هیستوگرام محلی ساخته می‌شود و آستانۀ Otsu همان ناحیه محاسبه می‌شود.

پس آستانه به تابعی از مکان تبدیل می‌شود:

$$T=T(x,y).$$

این روش برای تصاویری با روشنایی غیر یکنواخت می‌تواند مناسب‌تر باشد، هرچند هزینۀ محاسباتی بیشتری دارد.

#### تعمیم به چند آستانه

ایدهٔ واریانس بین‌کلاسی به بیش از دو کلاس نیز قابل تعمیم است.

اگر $K$ کلاس داشته باشیم، با احتمال‌های

$$P_1,P_2,\ldots,P_K$$

و میانگین‌های

$$m_1,m_2,\ldots,m_K,$$

آنگاه

$$\boxed{
    \sigma_B^2
    =
    \sum_{j=1}^{K}
    P_j
    (m_j-m_G)^2.
}$$

در این حالت باید چند آستانه را همزمان انتخاب کنیم تا این معیار بیشینه شود.

با افزایش تعداد کلاس‌ها، تعداد ترکیب‌های ممکن آستانه‌ها سریع افزایش می‌یابد و مسئله محاسباتی دشوارتر می‌شود.

#### پیچیدگی محاسباتی

پس از تشکیل هیستوگرام، لازم نیست تمام پیکسل‌ها برای هر آستانه دوباره بررسی شوند.

برای تصویر 8 بیتی فقط

$$L=256$$

سطح شدت وجود دارد.

پس بعد از محاسبۀ هیستوگرام، جست‌وجوی آستانه روی حداکثر 256 سطح انجام می‌شود.

اگر $N$ تعداد پیکسل‌ها باشد، تشکیل هیستوگرام دارای مرتبهٔ

$$O(N)$$

و جست‌وجوی آستانه دارای مرتبهٔ

$$O(L)$$

است.

بنابراین پیچیدگی کلی را می‌توان تقریباً

$$\boxed{
    O(N+L)
}$$

در نظر گرفت.

## قطعه‌بندی ناحیه‌ای

### ایدهٔ بنیادی قطعه‌بندی ناحیه‌ای

در روش‌های مبتنی بر لبه، ابتدا نقاطی را پیدا می‌کنیم که در آنها شدت تصویر به سرعت تغییر می‌کند و سپس تلاش می‌کنیم این نقاط را به مرزهای معنادار تبدیل کنیم. در قطعه‌بندی ناحیه‌ای، دیدگاه برعکس است:

$$\boxed{
    \text{به جای یافتن مرزها، خود ناحیه‌های همگن را مستقیماً پیدا می‌کنیم.}
}$$

فرض کنید کل ناحیهٔ مکانی تصویر را با $R$ نمایش دهیم. هدف قطعه‌بندی آن است که $R$ را به زیرناحیه‌های

$$R_1,R_2,\ldots,R_n$$

تقسیم کنیم، به گونه‌ای که هر زیرناحیه از نظر معیار مورد نظر همگن باشد و دو ناحیهٔ مجاور را نتوان بدون از دست رفتن این همگنی با یکدیگر ادغام کرد.

از دید ریاضی، یک قطعه‌بندی مطلوب معمولاً شرایط زیر را ارضا می‌کند:

$$\boxed{
    \bigcup_{i=1}^{n}R_i=R
}$$

یعنی هیچ پیکسلی از تصویر بدون برچسب باقی نماند،

$$\boxed{
    R_i\cap R_j=\varnothing,
    \qquad i\neq j
}$$

یعنی هر پیکسل فقط به یک ناحیه تعلق داشته باشد، و هر $R_i$ نیز باید یک مجموعهٔ متصل باشد.

اگر $Q(R)$ یک گزارهٔ منطقی برای بیان همگنی ناحیه باشد، انتظار داریم

$$\boxed{
    Q(R_i)=\mathrm{TRUE}
}$$

برای همهٔ ناحیه‌های نهایی برقرار باشد. همچنین اگر $R_i$ و $R_j$ دو ناحیهٔ مجاور نهایی باشند، معمولاً باید

$$\boxed{
    Q(R_i\cup R_j)=\mathrm{FALSE}
}$$

باشد؛ زیرا در غیر این صورت می‌شد آنها را نیز با یکدیگر ادغام کرد.

این روابط، اساس ریاضی بسیاری از الگوریتم‌های رشد ناحیه، تقسیم--ادغام، خوشه‌بندی و روش‌های گرافی را تشکیل می‌دهند.

### همسایگی و اتصال

شباهت شدت به تنهایی برای تشکیل یک ناحیه کافی نیست. دو پیکسل ممکن است شدت یکسان داشته باشند، ولی در دو قسمت کاملاً جدا از تصویر قرار گرفته باشند. بنابراین مفهوم اتصال جزء جدایی‌ناپذیر قطعه‌بندی ناحیه‌ای است.

برای پیکسل

$$p=(x,y)$$

همسایگی چهارگانه را به صورت

$$N_4(p)=
\{(x-1,y),(x+1,y),(x,y-1),(x,y+1)\}$$

تعریف می‌کنیم.

در اتصال هشت‌گانه، چهار همسایهٔ قطری نیز افزوده می‌شوند:

$$N_8(p)=N_4(p)\cup
\{(x-1,y-1),(x-1,y+1),(x+1,y-1),(x+1,y+1)\}.$$

در نتیجه، ناحیه فقط مجموعه‌ای از پیکسل‌های مشابه نیست؛ بلکه مجموعه‌ای از پیکسل‌های مشابه و متصل است.

```{admonition} برداشت مفهومی
:class: note

اگر شرط اتصال را حذف کنیم، ممکن است تمام پیکسل‌های خاکستری با مقدار مثلاً $100$، هرچند در نقاط پراکندهٔ تصویر باشند، یک ناحیه محسوب شوند. این نتیجه از دید هندسی معمولاً بی‌معنی است.
```

### رشد ناحیه

Region Growing یکی از روشن‌ترین روش‌های قطعه‌بندی ناحیه‌ای است. ایدهٔ آن بسیار ساده است:

$$\boxed{
    \text{از یک یا چند بذر شروع کن و فقط پیکسل‌های مشابه و متصل را به ناحیه اضافه کن.}
}$$

هر نقطهٔ شروع را یک بذر یا Seed می‌نامیم. سه جزء اصلی الگوریتم عبارت‌اند از انتخاب بذر، تعریف معیار شباهت، و تعریف همسایگی و قاعدهٔ توقف.

#### ساده‌ترین معیار شباهت

فرض کنید تصویر خاکستری با $f(x,y)$ نمایش داده شود و بذر

$$s=(x_s,y_s)$$

باشد. ساده‌ترین معیار این است که پیکسل $p$ پذیرفته شود اگر شدت آن به شدت بذر نزدیک باشد:

$$\boxed{
    |f(p)-f(s)|\leq T.
}$$

در این رابطه $T$ تلرانس مجاز است. اگر $T$ خیلی کوچک باشد، ناحیه ممکن است ناقص باقی بماند. اگر $T$ خیلی بزرگ باشد، رشد می‌تواند از مرز جسم عبور کند و وارد ناحیه‌های ناخواسته شود.

#### الگوریتم ساده و روشن رشد ناحیه

برای یک بذر و اتصال چهارگانه، رویهٔ عملی را می‌توان چنین نوشت:

1.  بذر $s$ را انتخاب کنید.

2.  ناحیه را با $R=\{s\}$ مقداردهی اولیه کنید.

3.  همسایه‌های بذر را در یک صف قرار دهید.

4.  اولین پیکسل $p$ را از صف بردارید.

5.  اگر $p$ قبلاً بررسی نشده و $$|f(p)-f(s)|\leq T$$ باشد، آن را به $R$ اضافه کنید.

6.  اگر $p$ پذیرفته شد، همسایه‌های بررسی‌نشدهٔ آن را نیز به صف اضافه کنید.

7.  مراحل 4 تا 6 را تا زمانی ادامه دهید که صف خالی شود.

پس الگوریتم فقط در امتداد پیکسل‌های پذیرفته‌شده حرکت می‌کند. در نتیجه حتی اگر در نقطه‌ای دور از تصویر پیکسلی با شدت مناسب وجود داشته باشد، تا زمانی که مسیر متصلی از پیکسل‌های پذیرفتنی به آن نرسیده باشد، عضو ناحیه نمی‌شود.

#### مثال عددی کامل از رشد ناحیه

```{figure} chapter-10-assets/images/fig10_08_region_growing.png
:name: fig-ch10-region-growing
:width: 82%

تصویر عددی و ماسک ناحیۀ رشدکرده برای مثال آموزشی متن. شرط شباهت به تنهایی کافی نیست و اتصال مکانی نیز باید برقرار باشد.
```

تصویر کوچک زیر را در نظر بگیرید:

$$F=
\begin{bmatrix}
    11&10&12&80&81\\
    10&12&11&79&82\\
    9&11&12&78&80\\
    10&13&11&77&81\\
    12&10&9&76&83
\end{bmatrix}.$$

بذر را پیکسل سطر سوم و ستون دوم انتخاب می‌کنیم:

$$s=(3,2),
\qquad
f(s)=11.$$

فرض کنید اتصال چهارگانه و آستانه

$$T=3$$

باشد. پس هر پیکسلی که به صورت متصل به ناحیه برسد و شرط

$$|f(p)-11|\leq3$$

را ارضا کند، پذیرفته می‌شود. یعنی بازهٔ مجاز شدت‌ها

$$8\leq f(p)\leq14$$

است.

در ابتدا

$$R_0=\{(3,2)\}.$$

چهار همسایهٔ آن عبارت‌اند از

$$(2,2),\quad(4,2),\quad(3,1),\quad(3,3).$$

شدت آنها به ترتیب

$$12,\quad13,\quad9,\quad12$$

است و هر چهار مقدار شرط شباهت را ارضا می‌کنند. پس به ناحیه افزوده می‌شوند.

از این پیکسل‌ها دوباره به همسایه‌هایشان می‌رویم. این فرایند ادامه پیدا می‌کند و تمام پیکسل‌های سه ستون اول به ناحیه متصل می‌شوند.

اما هنگامی که رشد به ستون چهارم می‌رسد، مقادیری مانند

$$76,\;77,\;78,\;79,\;80$$

دیده می‌شوند و مثلاً

$$|78-11|=67>3.$$

پس این پیکسل‌ها رد می‌شوند و رشد از آن مرز عبور نمی‌کند.

ماسک نهایی ناحیه برابر است با

$$\boxed{
    M=
    \begin{bmatrix}
        1&1&1&0&0\\
        1&1&1&0&0\\
        1&1&1&0&0\\
        1&1&1&0&0\\
        1&1&1&0&0
    \end{bmatrix}.
}$$

این مثال نشان می‌دهد که رشد ناحیه در واقع ترکیب دو شرط است:

$$\boxed{
    \text{شباهت}+\text{اتصال}.
}$$

#### نسخهٔ تطبیقی: مقایسه با میانگین ناحیه

مقایسه با مقدار ثابت بذر همیشه بهترین انتخاب نیست. ممکن است شدت جسم به آرامی تغییر کند. در چنین حالتی معیار مناسب‌تر آن است که پیکسل جدید با میانگین فعلی ناحیه مقایسه شود:

$$\boxed{
    d(p,R)=|f(p)-\mu_R|
}$$

و پیکسل هنگامی پذیرفته شود که

$$\boxed{
    |f(p)-\mu_R|\leq T.
}$$

اگر ناحیه در حال حاضر $n$ پیکسل و میانگین $\mu_R$ داشته باشد و پیکسل جدید با شدت $f(p)$ پذیرفته شود، میانگین جدید از رابطهٔ

$$\boxed{
    \mu_R^{\mathrm{new}}
    =
    \frac{n\mu_R+f(p)}{n+1}
}$$

به دست می‌آید.

این روش می‌تواند تغییر آرام شدت داخل جسم را بهتر دنبال کند. اما چون $\mu_R$ پس از هر پذیرش تغییر می‌کند، ترتیب بررسی پیکسل‌ها ممکن است روی نتیجه اثر بگذارد.

#### رشد رقابتی چند ناحیه

اگر چند بذر

$$s_1,s_2,\ldots,s_K$$

داشته باشیم، می‌توان $K$ ناحیه را همزمان رشد داد.

برای هر پیکسل مرزی $p$ و ناحیه $R_k$، یک فاصله تعریف می‌کنیم:

$$d(p,R_k)=|f(p)-\mu_k|.$$

در نسخهٔ سادهٔ رقابتی، پیکسلی انتخاب می‌شود که کمترین فاصله را با یکی از ناحیه‌ها داشته باشد:

$$\boxed{
    (p^\star,k^\star)
    =
    \arg\min_{p,k}d(p,R_k).
}$$

سپس

$$p^\star\rightarrow R_{k^\star}.$$

بعد از افزودن پیکسل، میانگین آن ناحیه به‌روز می‌شود و فرایند ادامه پیدا می‌کند. در عمل، یک Priority Queue می‌تواند کاندیداها را بر حسب مقدار $d(p,R_k)$ مرتب کند. این دیدگاه به خانوادهٔ Seeded Region Growing نزدیک است.

#### انتخاب بذر و قاعدهٔ توقف

بذرها می‌توانند توسط کاربر، آستانه‌گذاری اولیه، مینیمم‌ها یا ماکزیمم‌های محلی، مراکز خوشه‌ها، یا اطلاعات قبلی از شکل و محل جسم انتخاب شوند.

قاعدهٔ پایهٔ توقف این است:

$$\boxed{
    \text{رشد هنگامی متوقف می‌شود که هیچ پیکسل مرزی شرط ورود را ارضا نکند.}
}$$

اما در مسائل واقعی می‌توان شروط دیگری نیز افزود؛ مثلاً

$$|R|\leq A_{\max},
\qquad
\sigma_R^2\leq T_\sigma,$$

یا محدودیت روی شکل، کشیدگی، بافت یا رنگ.

##### انتخاب خودکار بذر با استفاده از Mean Shift
در روش رشد ناحیه، یکی از مسائل مهم انتخاب بذرهای مناسب است. اگر محل ناحیه‌های مورد نظر از قبل معلوم نباشد، می‌توان از یک روش خوشه‌بندی ناپارامتری مانند Mean Shift برای یافتن نواحی پرتراکم در فضای ویژگی استفاده کرد و از آنها برای تولید بذرهای اولیه بهره گرفت.

Mean Shift مستقیماً تعداد خوشه‌ها را از قبل تعیین نمی‌کند. ایدۀ آن این است که نقاط فضای ویژگی به سمت بیشینه‌های محلی چگالی، که **مد** نامیده می‌شوند، حرکت کنند.

برای یک تصویر خاکستری می‌توان هر پیکسل را، علاوه بر شدت، با مختصات مکانی آن نمایش داد. برای مثال:

$$\mathbf z_i
=
\begin{bmatrix}
    x_i/h_s\\
    y_i/h_s\\
    f_i/h_r
\end{bmatrix},$$

که در آن $h_s$ پهنای باند مکانی و $h_r$ پهنای باند شدت است.

در یک بیان ساده، اگر $\mathbf y^{(t)}$ مکان فعلی یک نقطه در فضای ویژگی باشد، به‌روزرسانی Mean Shift با یک کرنل گاوسی را می‌توان به صورت

$$\boxed{
    \mathbf y^{(t+1)}
    =
    \frac{
        \displaystyle
        \sum_{i=1}^{N}
        w_i^{(t)}\mathbf z_i
    }{
        \displaystyle
        \sum_{i=1}^{N}
        w_i^{(t)}
    }
}$$

نوشت که در آن

$$w_i^{(t)}
=
\exp
\left[
-\frac{
    \|\mathbf y^{(t)}-\mathbf z_i\|^2
}{2}
\right].$$

بنابراین در هر تکرار، نقطه به سمت میانگین وزن‌دار نقاط پرتراکم اطراف خود حرکت می‌کند.

بردار جابه‌جایی

$$\boxed{
    \mathbf m(\mathbf y^{(t)})
    =
    \mathbf y^{(t+1)}
    -
    \mathbf y^{(t)}
}$$

را بردار Mean Shift می‌نامیم.

تکرار تا زمانی ادامه پیدا می‌کند که تغییر بسیار کوچک شود:

$$\boxed{
    \left\|
    \mathbf y^{(t+1)}
    -
    \mathbf y^{(t)}
    \right\|
    <
    \varepsilon.
}$$

نقطۀ نهایی تقریباً یک مد چگالی در فضای ویژگی است.

اگر تعداد زیادی از پیکسل‌ها به یک مد یا مدهای بسیار نزدیک همگرا شوند، می‌توان آنها را متعلق به یک گروه مشابه در نظر گرفت. ناحیه‌های متصل و پایدار حاصل از این خوشه‌بندی می‌توانند به عنوان ناحیه‌های کاندید برای استخراج بذرهای رشد ناحیه استفاده شوند.

به صورت مفهومی:

$$\boxed{
    \text{پیکسل‌ها}
    \longrightarrow
    \text{Mean Shift}
    \longrightarrow
    \text{مدهای چگالی}
    \longrightarrow
    \text{گروه‌های مشابه}
    \longrightarrow
    \text{بذرهای اولیه}
    \longrightarrow
    \text{Region Growing}.
}$$

مزیت این روش آن است که انتخاب بذر صرفاً به یک مقدار شدت از پیش تعیین‌شده وابسته نیست و می‌تواند ساختار واقعی توزیع ویژگی‌های تصویر را در نظر بگیرد.

```{admonition} برداشت مفهومی
:class: note

باید بین دو قاعدۀ توقف تفاوت گذاشت.

در Mean Shift تکرار زمانی متوقف می‌شود که جابه‌جایی در فضای ویژگی بسیار کوچک شود:

$$\|\mathbf y^{(t+1)}-\mathbf y^{(t)}\|<\varepsilon.$$

اما پس از تعیین بذرها، توقف خودِ الگوریتم رشد ناحیه همچنان بر اساس قاعدۀ رشد است:

$$\boxed{
        \text{هیچ پیکسل همسایۀ جدیدی شرط ورود به ناحیه را ارضا نکند}.
    }$$

بنابراین معیار همگرایی Mean Shift را نباید با قاعدۀ توقف Region Growing یکی دانست.
```

#### نشت ناحیه

یکی از مشکلات مشهور رشد ناحیه، Leakage است. اگر در مرز جسم شکافی با شدت مشابه داخل جسم وجود داشته باشد، رشد ممکن است از آن شکاف عبور کند و وارد زمینه شود.

راه‌های متداول کاهش این مشکل عبارت‌اند از هموارسازی ملایم تصویر، استفاده از میانگین جاری ناحیه، محدودکردن رشد با نقشهٔ گرادیان، استفاده از چند بذر رقابتی، و اعمال محدودیت اندازه یا شکل.

### تقسیم و ادغام ناحیه‌ها

در رشد ناحیه از ناحیه‌های کوچک شروع می‌کنیم و آنها را بزرگ می‌کنیم. روش Region Splitting and Merging از جهت مخالف نیز استفاده می‌کند:

$$\boxed{
    \text{ناحیهٔ بزرگ}\rightarrow
    \text{تقسیم}\rightarrow
    \text{ناحیه‌های همگن}\rightarrow
    \text{ادغام ناحیه‌های مشابه مجاور}.
}$$

#### گزارهٔ همگنی

برای هر ناحیه $R$، یک گزاره $Q(R)$ تعریف می‌کنیم. یک مثال ساده:

$$\boxed{
    Q(R):\quad
    \max_{p\in R}f(p)-\min_{p\in R}f(p)\leq T.
}$$

یعنی ناحیه هنگامی همگن تلقی می‌شود که دامنهٔ تغییر شدت داخل آن از $T$ بیشتر نباشد.

معیار دیگر می‌تواند واریانس باشد:

$$\boxed{
    Q(R):\quad
    \sigma_R^2\leq T_\sigma.
}$$

#### مرحلهٔ تقسیم

از کل تصویر $R$ شروع می‌کنیم. اگر

$$Q(R)=\mathrm{TRUE},$$

نیازی به تقسیم نیست. اگر

$$Q(R)=\mathrm{FALSE},$$

ناحیه را به چهار ربع تقسیم می‌کنیم. هر ربعی که هنوز شرط همگنی را نقض کند دوباره به چهار قسمت تقسیم می‌شود. ساختار حاصل یک Quadtree است.

#### مرحلهٔ ادغام

تقسیم صرف معمولاً تعداد زیادی بلوک کوچک تولید می‌کند. پس بعد از تقسیم، ناحیه‌های مجاور $R_i$ و $R_j$ را بررسی می‌کنیم. اگر

$$\boxed{
    Q(R_i\cup R_j)=\mathrm{TRUE},
}$$

آن دو را ادغام می‌کنیم. فرایند تا زمانی ادامه پیدا می‌کند که هیچ ادغام جدیدی ممکن نباشد.

#### الگوریتم سادهٔ تقسیم--ادغام

1.  با کل تصویر به عنوان یک ناحیه شروع کنید.

2.  هر ناحیه‌ای را که $Q(R)=\mathrm{FALSE}$ است به چهار قسمت تقسیم کنید.

3.  مرحلهٔ قبل را تا رسیدن به ناحیه‌های همگن یا حداقل اندازه ادامه دهید.

4.  ناحیه‌های مجاور را بررسی کنید.

5.  اگر اتحاد دو ناحیه شرط $Q$ را ارضا کرد، آنها را ادغام کنید.

6.  مراحل ادغام را تا زمانی ادامه دهید که هیچ ادغام جدیدی رخ ندهد.

#### مثال عددی سادهٔ تقسیم--ادغام

```{figure} chapter-10-assets/images/fig10_09_split_merge.png
:name: fig-ch10-split-merge
:width: 68%

نمایش اصیل مثال تقسیم به ربع‌ها و ادغام ناحیه‌های مجاور همگن.
```

تصویر کوچک زیر را در نظر بگیرید:

$$F=
\begin{bmatrix}
    20&21&99&100\\
    19&20&101&99\\
    22&21&98&100\\
    20&19&100&102
\end{bmatrix}.$$

معیار همگنی را به صورت

$$Q(R):\quad \max(R)-\min(R)\leq5$$

تعریف می‌کنیم.

برای کل تصویر:

$$102-19=83>5,$$

پس کل تصویر همگن نیست و باید تقسیم شود.

چهار ربع $2\times2$ به دست می‌آیند:

$$R_1=
\begin{bmatrix}
    20&21\\19&20
\end{bmatrix},
\qquad
R_2=
\begin{bmatrix}
    99&100\\101&99
\end{bmatrix},$$

$$R_3=
\begin{bmatrix}
    22&21\\20&19
\end{bmatrix},
\qquad
R_4=
\begin{bmatrix}
    98&100\\100&102
\end{bmatrix}.$$

دامنهٔ تغییر در این چهار ناحیه به ترتیب $2,2,3,4$ است؛ پس هر چهار ناحیه به تنهایی همگن‌اند.

اکنون $R_1$ و $R_3$ مجاورند. اگر آنها را ادغام کنیم، تمام مقادیر سمت چپ تصویر در بازهٔ

$$19\leq f\leq22$$

قرار دارند و بنابراین

$$22-19=3\leq5.$$

پس ادغام مجاز است. به همین ترتیب $R_2$ و $R_4$ نیز ادغام می‌شوند، زیرا

$$102-98=4\leq5.$$

اما دو نیمهٔ چپ و راست را نمی‌توان ادغام کرد، زیرا

$$102-19=83>5.$$

پس نتیجهٔ نهایی دو ناحیه است: ناحیهٔ کم‌شدت در سمت چپ و ناحیهٔ پرشدت در سمت راست.

### خوشه‌بندی برای قطعه‌بندی ناحیه‌ای

می‌توان هر پیکسل را به صورت یک بردار ویژگی در نظر گرفت. برای تصویر خاکستری:

$$\mathbf z_p=[f(p)].$$

برای تصویر رنگی:

$$\mathbf z_p=[R(p),G(p),B(p)]^T.$$

می‌توان مختصات مکانی را نیز اضافه کرد:

$$\mathbf z_p=[R,G,B,\lambda x,\lambda y]^T.$$

هدف خوشه‌بندی این است که پیکسل‌هایی با ویژگی‌های مشابه در یک گروه قرار گیرند.

#### روش K-means

فرض کنید $K$ خوشه داشته باشیم. تابع هدف K-means معمولاً به صورت

$$\boxed{
    J=
    \sum_{k=1}^{K}
    \sum_{\mathbf z_p\in C_k}
    \left\|\mathbf z_p-\boldsymbol{\mu}_k\right\|^2
}$$

تعریف می‌شود، که در آن

$$\boldsymbol{\mu}_k
=
\frac{1}{|C_k|}
\sum_{\mathbf z_p\in C_k}\mathbf z_p$$

مرکز خوشهٔ $k$ است.

الگوریتم ساده:

1.  $K$ مرکز اولیه انتخاب کنید.

2.  هر پیکسل را به نزدیک‌ترین مرکز نسبت دهید: $$L(p)=\arg\min_k\|\mathbf z_p-\boldsymbol{\mu}_k\|^2.$$

3.  میانگین هر خوشه را دوباره محاسبه کنید.

4.  مراحل 2 و 3 را تا ثابت‌شدن برچسب‌ها یا کوچک‌شدن تغییر مراکز تکرار کنید.

```{admonition} برداشت مفهومی
:class: note

K-means به تنهایی شرط اتصال مکانی را تضمین نمی‌کند. دو مجموعهٔ دور از هم می‌توانند فقط به دلیل شباهت رنگ یا شدت، یک برچسب یکسان دریافت کنند. افزودن مختصات $x,y$ به بردار ویژگی یا پردازش مؤلفه‌های متصل بعد از خوشه‌بندی می‌تواند این مشکل را کاهش دهد.
```

### سوپرپیکسل‌ها و الگوریتم SLIC

سوپرپیکسل مجموعه‌ای از پیکسل‌های مجاور و مشابه است که به عنوان یک واحد بزرگ‌تر در پردازش‌های بعدی استفاده می‌شود. هدف این نیست که از ابتدا اشیای نهایی تصویر را دقیقاً تشخیص دهیم؛ هدف آن است که تعداد عناصر پردازشی را کاهش دهیم و در عین حال مرزهای اصلی تصویر تا حد زیادی حفظ شوند.

روش SLIC یک نسخهٔ محلی و کارآمد از ایدهٔ K-means است.

#### فضای ویژگی و فاصله در SLIC

```{figure} chapter-10-assets/images/fig10_10_slic_concept.png
:name: fig-ch10-slic-concept
:width: 78%

طرح آموزشی جست‌وجوی محلی SLIC و نقش همزمان نزدیکی مکانی و شباهت رنگی.
```

برای تصویر رنگی معمولاً بردار

$$\mathbf z=[L,a,b,x,y]^T$$

در فضای رنگ CIELAB استفاده می‌شود.

فاصلهٔ رنگی:

$$\boxed{
    d_c=
    \sqrt{(L_i-L_k)^2+(a_i-a_k)^2+(b_i-b_k)^2}
}$$

و فاصلهٔ مکانی:

$$\boxed{
    d_s=
    \sqrt{(x_i-x_k)^2+(y_i-y_k)^2}.
}$$

اگر تصویر $N$ پیکسل داشته باشد و حدود $K$ سوپرپیکسل بخواهیم، فاصلهٔ تقریبی مراکز اولیه برابر است با

$$\boxed{
    S\approx\sqrt{\frac{N}{K}}.
}$$

برای ترکیب فاصلهٔ رنگی و مکانی می‌توان نوشت

$$\boxed{
    D=
    \sqrt{
        d_c^2+
        \left(\frac{m}{S}\right)^2d_s^2
    }.
}$$

پارامتر $m$ میزان فشردگی سوپرپیکسل‌ها را کنترل می‌کند. $m$ بزرگ‌تر، وزن فاصلهٔ مکانی را بیشتر می‌کند و ناحیه‌ها منظم‌تر و فشرده‌تر می‌شوند. $m$ کوچک‌تر اجازه می‌دهد مرز سوپرپیکسل بیشتر از ساختار رنگی تصویر پیروی کند.

#### الگوریتم سادهٔ SLIC

1.  $K$ مرکز اولیه را تقریباً روی یک شبکه با فاصلهٔ $S$ قرار دهید.

2.  هر مرکز را در یک همسایگی کوچک به نقطه‌ای با گرادیان کمتر منتقل کنید تا مرکز دقیقاً روی لبه قرار نگیرد.

3.  برای هر مرکز فقط پیکسل‌های ناحیهٔ حدود $2S\times2S$ اطراف آن را بررسی کنید.

4.  فاصلهٔ $D$ هر پیکسل تا مرکزهای ممکن را محاسبه کنید و پیکسل را به نزدیک‌ترین مرکز نسبت دهید.

5.  مرکز هر خوشه را با میانگین ویژگی‌های اعضای آن به‌روز کنید.

6.  تا همگرایی تکرار کنید.

7.  در پایان، اتصال مکانی سوپرپیکسل‌ها را کنترل کنید و مؤلفه‌های بسیار کوچک را به همسایهٔ مناسب متصل کنید.

### قطعه‌بندی مبتنی بر گراف

در دیدگاه گرافی، تصویر را به یک گراف وزن‌دار تبدیل می‌کنیم:

$$\boxed{G=(V,E).}$$

هر گره می‌تواند یک پیکسل یا سوپرپیکسل باشد و یال‌ها ارتباط بین گره‌های همسایه را نشان می‌دهند.

وزن یال باید میزان شباهت دو گره را نشان دهد. یک مثال رایج:

$$\boxed{
    w_{ij}
    =
    \exp\!\left[-\frac{(f_i-f_j)^2}{2\sigma_I^2}\right]
    \exp\!\left[-\frac{\|\mathbf x_i-\mathbf x_j\|^2}{2\sigma_x^2}\right].
}$$

دو پیکسل نزدیک و هم‌شدت وزن بزرگی می‌گیرند؛ دو پیکسل دور یا با شدت بسیار متفاوت وزن کوچکی خواهند داشت.

#### برش سادهٔ گراف

اگر گره‌ها را به دو مجموعهٔ $A$ و $B$ تقسیم کنیم، هزینهٔ برش برابر است با

$$\boxed{
    \operatorname{cut}(A,B)
    =
    \sum_{i\in A}\sum_{j\in B}w_{ij}.
}$$

کمینه‌کردن صرف این مقدار مشکل دارد: الگوریتم ممکن است یک گرهٔ ضعیفاً متصل را جدا کند و یک برش کم‌هزینه ولی بی‌معنی بسازد.

#### برش نرمال‌شده

```{figure} chapter-10-assets/images/fig10_11_graph_cut.png
:name: fig-ch10-graph-cut
:width: 75%

نمایش سادهٔ گرافی از دو گروه با اتصال داخلی قوی و یال بین‌گروهی ضعیف؛ ایدۀ برش، جداسازی گروه‌ها با هزینهٔ مناسب است.
```

برای جلوگیری از برش‌های بسیار نامتوازن، معیار Normalized Cut تعریف می‌شود.

ابتدا

$$\operatorname{assoc}(A,V)
=
\sum_{i\in A}\sum_{j\in V}w_{ij}.$$

سپس

$$\boxed{
    \operatorname{Ncut}(A,B)
    =
    \frac{\operatorname{cut}(A,B)}{\operatorname{assoc}(A,V)}
    +
    \frac{\operatorname{cut}(A,B)}{\operatorname{assoc}(B,V)}.
}$$

هدف آن است که $\operatorname{Ncut}(A,B)$ کمینه شود.

اگر ماتریس شباهت را با $W$ و ماتریس قطری درجات را با

$$D_{ii}=\sum_jw_{ij}$$

نمایش دهیم، تقریب طیفی مسئله به دستگاه مقدار ویژهٔ تعمیم‌یافته

$$\boxed{
    (D-W)\mathbf y=\lambda D\mathbf y
}$$

منجر می‌شود. بردار ویژهٔ مربوط به دومین مقدار ویژهٔ کوچک برای تقسیم گراف به دو بخش به کار می‌رود.

### قطعه‌بندی آبخیز

در روش Watershed تصویر یا یک تابع مشتق‌شده از آن را به صورت یک سطح توپوگرافی در نظر می‌گیریم. مختصات $x,y$ مکان‌اند و مقدار تابع مانند ارتفاع است. مینیمم‌های محلی مانند کف دره‌ها هستند.

اگر آب از این مینیمم‌ها بالا بیاید، ناحیه‌هایی تشکیل می‌شوند که Catchment Basin نامیده می‌شوند. هنگامی که آب دو حوضه در آستانهٔ اتصال قرار گیرد، بین آنها سدی ساخته می‌شود. این سدها همان خطوط آبخیز و در نتیجه مرزهای قطعه‌بندی هستند.

#### چرا معمولاً روی گرادیان اجرا می‌شود؟

```{figure} chapter-10-assets/images/fig10_12_watershed.png
:name: fig-ch10-watershed
:width: 84%

برداشت توپوگرافی Watershed: حوضه‌ها از مینیمم‌ها رشد می‌کنند و مرز میان حوضه‌های رقیب به خط آبخیز تبدیل می‌شود.
```

برای تصویر $f$، معمولاً یک نقشهٔ ارتفاع از اندازهٔ گرادیان می‌سازیم:

$$\boxed{
    g(x,y)=\|\nabla f(x,y)\|.
}$$

داخل ناحیه‌های تقریباً یکنواخت

$$g(x,y)\approx0,$$

در حالی که روی مرزهای قوی $g(x,y)$ بزرگ است. پس ناحیه‌های داخلی شبیه دره و لبه‌ها شبیه دیواره‌های بلند می‌شوند.

#### الگوریتم سادهٔ آبخیز کنترل‌شده با نشانگر

فرض کنید چند نشانگر

$$M_1,M_2,\ldots,M_K$$

داریم.

1.  تصویر ارتفاع، مثلاً $g=\|\nabla f\|$، را محاسبه کنید.

2.  به هر نشانگر یک برچسب متفاوت بدهید.

3.  پیکسل‌های همسایهٔ نشانگرها را در یک صف اولویت قرار دهید؛ اولویت برابر ارتفاع $g(p)$ است.

4.  پیکسلی را که کمترین ارتفاع را دارد از صف خارج کنید.

5.  اگر همسایه‌های برچسب‌دار آن فقط یک برچسب داشته باشند، همان برچسب را به پیکسل بدهید.

6.  اگر پیکسل بین دو یا چند ناحیهٔ با برچسب متفاوت قرار گرفته باشد، آن را مرز آبخیز در نظر بگیرید.

7.  همسایه‌های بررسی‌نشدهٔ پیکسل را وارد صف کنید.

8.  تا خالی‌شدن صف ادامه دهید.

این الگوریتم را می‌توان نوعی رشد رقابتی ناحیه‌ها روی یک سطح ارتفاعی دانست.

#### بیش‌قطعه‌بندی

اگر تمام مینیمم‌های محلی به عنوان بذر آبخیز استفاده شوند، نویز می‌تواند تعداد زیادی مینیمم کوچک ایجاد کند و در نتیجه تصویر به تعداد بسیار زیادی ناحیه شکسته شود. این مشکل را Oversegmentation می‌نامیم.

راهکار اصلی، استفاده از آبخیز کنترل‌شده با نشانگر است:

$$\boxed{
    \text{به جای همهٔ مینیمم‌ها، فقط نشانگرهای معتبر را نگه می‌داریم.}
}$$

نشانگرها می‌توانند با آستانه‌گذاری، فاصلهٔ اقلیدسی، عملیات مورفولوژیک، دانش قبلی یا تعامل کاربر تولید شوند.

### رابطهٔ مفهومی روش‌های این فصل

اگرچه روش‌های این فصل ظاهراً متفاوت‌اند، همگی حول دو ایده می‌چرخند:

$$\boxed{\text{شباهت داخل ناحیه}}
\qquad\text{و}\qquad
\boxed{\text{تفاوت بین ناحیه‌ها}}.$$

در رشد ناحیه، شباهت مستقیماً هنگام افزودن هر پیکسل آزموده می‌شود. در تقسیم--ادغام، همگنی یک بلوک یا اتحاد دو بلوک بررسی می‌شود. در K-means، مجموع فاصله از مراکز خوشه‌ها کمینه می‌شود. در SLIC، شباهت رنگی و نزدیکی مکانی همزمان دخالت دارند. در روش‌های گرافی، شباهت به صورت وزن یال‌ها نمایش داده می‌شود. در آبخیز، لبه‌های قوی به صورت موانع توپوگرافی بین حوضه‌ها ظاهر می‌شوند.

### مقایسهٔ روش‌ها

  **روش**            **ایدهٔ اصلی**                                          **مزیت**                                             **محدودیت اصلی**
  ------------------ ------------------------------------------------------ ---------------------------------------------------- -----------------------------------------
  رشد ناحیه          رشد از بذر با استفاده از شباهت و اتصال                 بسیار قابل فهم و مناسب برای ناحیه‌های همگن            حساس به بذر و امکان نشت
  تقسیم--ادغام       تقسیم بازگشتی بلوک‌های ناهمگن و ادغام همسایه‌های مشابه   ساختار منظم و مناسب برای معیارهای آماری ناحیه        ممکن است اثر بلوکی ایجاد کند
  K-means            کمینه‌کردن فاصله از مراکز خوشه                          ساده و قابل تعمیم به ویژگی‌های چندبعدی                اتصال مکانی را ذاتاً تضمین نمی‌کند
  SLIC               خوشه‌بندی محلی همزمان در فضا و رنگ                      کاهش شدید تعداد واحدهای پردازشی و حفظ مناسب مرزها    خروجی معمولاً مرحلهٔ میانی است
  Graph Cut / Ncut   تقسیم گراف با توجه به وزن شباهت                        چارچوب ریاضی قوی و استفاده از اطلاعات محلی و جهانی   ساخت و حل گراف می‌تواند پرهزینه باشد
  Watershed          سیلاب‌کردن سطح توپوگرافی از نشانگرها                    مرزهای متصل و مناسب برای اجسام چسبیده                بدون نشانگر مناسب مستعد بیش‌قطعه‌بندی است

### راهنمای انتخاب روش

اگر جسم مورد نظر از نظر شدت یا رنگ نسبتاً یکنواخت است و محل تقریبی آن را می‌دانیم، رشد ناحیه انتخاب طبیعی است. اگر کل تصویر را می‌خواهیم به بلوک‌های همگن تقسیم کنیم و بتوانیم یک گزارهٔ $Q(R)$ مناسب تعریف کنیم، تقسیم--ادغام مناسب است. اگر فقط ویژگی‌ها مهم‌اند و اتصال مکانی مسئلهٔ اصلی نیست، K-means ساده و مؤثر است. اگر هدف کاهش ابعاد مسئله و حفظ تقریبی مرزهاست، SLIC مفید است. اگر روابط بین پیکسل‌ها و بهینه‌سازی سراسری اهمیت دارد، روش‌های گرافی مناسب‌اند. اگر اجسام چسبیده‌اند یا مرزها بهتر است از روی نقشهٔ گرادیان استخراج شوند، آبخیز کنترل‌شده با نشانگر گزینهٔ مهمی است.

### خلاصهٔ فصل

مفهوم مرکزی قطعه‌بندی ناحیه‌ای این است که تصویر را به مجموعه‌هایی متصل، مجزا و همگن تقسیم کنیم. در ساده‌ترین شکل:

$$\boxed{\text{ناحیه}=\text{شباهت}+\text{اتصال}.}$$

در رشد ناحیه این تعریف مستقیماً به الگوریتم تبدیل می‌شود. در تقسیم--ادغام، همگنی با گزارهٔ $Q(R)$ کنترل می‌شود. در خوشه‌بندی، همگنی با فاصله در فضای ویژگی تعریف می‌شود. در روش‌های گرافی، همگنی با وزن یال و هزینهٔ برش نمایش داده می‌شود. در آبخیز، جدایی ناحیه‌ها از توپولوژی سطح و موانع گرادیانی به دست می‌آید.

```{admonition} نکتۀ تدریسی
:class: tip

برای تدریس رشد ناحیه، بهتر است ابتدا همان ماتریس $5\times5$ این فصل روی تخته نوشته شود. یک بذر انتخاب کنید و فقط چهار سؤال را تکرار کنید: آیا پیکسل همسایه است؟ آیا قبلاً بررسی شده است؟ آیا شدت آن شرط شباهت را ارضا می‌کند؟ اگر پذیرفته شد، همسایه‌های جدید آن کدام‌اند؟ با چند تکرار، دانشجو بدون نیاز به حفظ‌کردن شبه‌کد، مکانیزم رشد ناحیه را می‌بیند.
```

```{admonition} پرسش کلاسی / امتحانی
:class: important

1.  چرا شباهت شدت بدون شرط اتصال برای تعریف ناحیه کافی نیست؟

2.  تفاوت مقایسه با شدت بذر و مقایسه با میانگین جاری ناحیه چیست؟

3.  در مثال عددی رشد ناحیه، اگر $T$ از 3 به 70 افزایش یابد چه اتفاقی می‌افتد؟

4.  چرا تقسیم صرف می‌تواند ناحیه‌های مجاور با خواص مشابه ایجاد کند؟

5.  در K-means چرا افزودن مختصات $x,y$ می‌تواند کیفیت قطعه‌بندی ناحیه‌ای را بهتر کند؟

6.  پارامتر $m$ در SLIC چه تعادلی ایجاد می‌کند؟

7.  چرا کمینه‌کردن سادهٔ $\operatorname{cut}(A,B)$ ممکن است یک گرهٔ منفرد را جدا کند؟

8.  چرا اجرای مستقیم آبخیز روی یک تصویر نویزی معمولاً باعث بیش‌قطعه‌بندی می‌شود؟
```

### منابع علمی تکمیلی 

1.  R. Adams and L. Bischof, Seeded Region Growing, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, No. 6, pp. 641--647, 1994, DOI: 10.1109/34.295913.

2.  R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Süsstrunk, SLIC Superpixels Compared to State-of-the-Art Superpixel Methods, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 34, No. 11, pp. 2274--2282, 2012.

3.  J. Shi and J. Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, No. 8, pp. 888--905, 2000, DOI: 10.1109/34.868688.

4.  Y. Boykov and M.-P. Jolly, Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images, ICCV, pp. 105--112, 2001.

5.  L. Vincent and P. Soille, Watersheds in Digital Spaces: An Efficient Algorithm Based on Immersion Simulations, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, No. 6, pp. 583--598, 1991.

## پیوست: نمایش عددی و هندسی مشتق جهتی و گرادیان

در این پیوست می‌خواهیم رابطۀ

$$D_{\mathbf{u}}f
=
M\cos(\phi-\alpha)$$

را نه فقط به صورت جبری، بلکه روی یک تابع دوبعدی واقعی مشاهده کنیم.

تابع اسکالر زیر را در نظر می‌گیریم:

$$\boxed{
f(x,y)=x^2+2y^2.
}$$

این تابع را می‌توان مانند یک تصویر پیوسته در نظر گرفت که در هر نقطۀ $(x,y)$ یک مقدار اسکالر دارد. تفاوت فقط در این است که به جای شدت روشنایی، مقدار تابع $f$ را بررسی می‌کنیم.

نقطۀ

$$P_0=(1,1)$$

را انتخاب می‌کنیم.

مشتق‌های جزئی تابع عبارت‌اند از

$$\frac{\partial f}{\partial x}=2x,
\qquad
\frac{\partial f}{\partial y}=4y.$$

پس در $P_0$ داریم

$$g_x=2,
\qquad
g_y=4.$$

بنابراین بردار گرادیان برابر است با

$$\boxed{
\nabla f(1,1)
=
\begin{bmatrix}
2\\
4
\end{bmatrix}.
}$$

اندازۀ گرادیان:

$$M
=
\sqrt{2^2+4^2}
=
\sqrt{20}
\approx
4.4721.$$

زاویۀ گرادیان نیز

$$\alpha
=
\operatorname{atan2}(4,2)
\approx
63.435^\circ$$

است.

حال یک جهت دلخواه با زاویۀ $\phi$ تعریف می‌کنیم:

$$\mathbf{u}
=
\begin{bmatrix}
\cos\phi\\
\sin\phi
\end{bmatrix}.$$

مشتق جهتی در نقطۀ $P_0$ برابر است با

$$D_{\mathbf{u}}f
=
\nabla f^T\mathbf{u}.$$

پس در این مثال

$$D_{\mathbf{u}}f
=
\begin{bmatrix}
2&4
\end{bmatrix}
\begin{bmatrix}
\cos\phi\\
\sin\phi
\end{bmatrix},$$

و در نتیجه

$$\boxed{
D_{\mathbf{u}}f
=
2\cos\phi+4\sin\phi.
}$$

از طرف دیگر چون

$$M\cos\alpha=2,
\qquad
M\sin\alpha=4,$$

داریم

$$\begin{aligned}
M\cos(\phi-\alpha)
&=
M\cos\phi\cos\alpha
+
M\sin\phi\sin\alpha
\\
&=
2\cos\phi+4\sin\phi.
\end{aligned}$$

پس مستقیماً مشاهده می‌کنیم که

$$\boxed{
D_{\mathbf{u}}f
=
M\cos(\phi-\alpha).
}$$

اکنون سه حالت مهم روشن می‌شوند.

اگر

$$\phi=\alpha,$$

آنگاه

$$D_{\mathbf{u}}f=M.$$

یعنی سریع‌ترین افزایش تابع دقیقاً در جهت گرادیان اتفاق می‌افتد.

اگر

$$\phi=\alpha+90^\circ,$$

داریم

$$D_{\mathbf{u}}f=0.$$

یعنی حرکت در راستای عمود بر گرادیان، در مرتبۀ اول مقدار تابع را تغییر نمی‌دهد. این همان راستای مماس بر منحنی هم‌مقدار است.

و اگر

$$\phi=\alpha+180^\circ,$$

آنگاه

$$D_{\mathbf{u}}f=-M,$$

یعنی بیشترین کاهش تابع در جهت مخالف گرادیان رخ می‌دهد.

برای نمونه اگر جهت دلخواه را

$$\phi=20^\circ$$

انتخاب کنیم:

$$D_{\mathbf{u}}f
=
2\cos20^\circ
+
4\sin20^\circ
\approx
3.2475.$$

این مقدار از $M\approx4.4721$ کوچک‌تر است، زیرا جهت $20^\circ$ با جهت گرادیان $\alpha\approx63.435^\circ$ منطبق نیست.

```{figure} chapter-10-assets/images/fig10_03_gradient_geometry.png
:name: fig-ch10-gradient-geometry
:width: 78%

منحنی‌های هم‌مقدار $f(x,y)=x^2+2y^2$ در کنار بردار گرادیان و مماس. گرادیان بر منحنی هم‌مقدار عمود و در جهت بیشترین افزایش است.
```

شکل بالا یک نکتۀ مهم را به صورت هندسی نشان می‌دهد. منحنی‌های رسم‌شده منحنی‌های

$$f(x,y)=c$$

هستند. حرکت روی هر یک از این منحنی‌ها مقدار تابع را تغییر نمی‌دهد. بنابراین مشتق جهتی در راستای مماس بر منحنی صفر است. از سوی دیگر، گرادیان بر همین مماس عمود است.

اکنون مشتق جهتی را برای تمام زوایای

$$0^\circ\leq\phi\leq360^\circ$$

محاسبه می‌کنیم.

```{figure} chapter-10-assets/images/fig10_04_directional_derivative.png
:name: fig-ch10-directional-derivative
:width: 86%

تغییر مشتق جهتی با زاویۀ $\phi$. بیشینه در $\phi=\alpha$، صفر در جهت عمود بر گرادیان و کمینه در جهت مخالف گرادیان رخ می‌دهد.
```

نمودار دوم به روشنی نشان می‌دهد که رابطۀ

$$D_{\mathbf{u}}f
=
M\cos(\phi-\alpha)$$

فقط یک رابطۀ جبری نیست. این رابطه تمام رفتار هندسی تغییر تابع در اطراف نقطه را توصیف می‌کند:

$$\boxed{
\begin{array}{ccl}
\phi=\alpha
&\Longrightarrow&
D_{\mathbf{u}}f=M
\\[2mm]
\phi=\alpha\pm90^\circ
&\Longrightarrow&
D_{\mathbf{u}}f=0
\\[2mm]
\phi=\alpha+180^\circ
&\Longrightarrow&
D_{\mathbf{u}}f=-M.
\end{array}
}$$

بنابراین گرادیان هم **جهت** سریع‌ترین افزایش و هم **مقدار** آن افزایش را مشخص می‌کند.

### کد بازتولید مثال‌ها

منطق عددی گرادیان، مشتق‌های Sobel، Otsu، رشد ناحیه و نرمال‌سازی نمایش در فایل اجرایی همراه فصل یکپارچه شده است:

- <a href="/assets/downloads/courses/image-processing/gonzalez/chapter-10/chapter10_examples.py" download>کد Python فصل ۱۰</a>
- <a href="/assets/downloads/courses/image-processing/gonzalez/chapter-10/Chapter10_Code_Examples.zip" download>بستۀ ZIP شامل Notebook فصل ۱۰</a>

شکل‌های هندسی گرادیان این صفحه نیز به‌صورت اصیل برای نسخۀ Jupyter Book بازطراحی شده‌اند و نسخۀ نهایی آنها در پوشۀ `images/` همین بسته قرار دارد.

## پرسش‌های مرور فصل

1. چرا شرط اتصال در تعریف یک ناحیه، مستقل از شباهت شدت، ضروری است؟
2. تفاوت پاسخ مشتق اول و دوم به یک لبۀ پله‌ای چیست و این تفاوت در آشکارسازی لبه چه اهمیتی دارد؟
3. در تبدیل هاف کلاسیک چرا $\theta$ پیمایش می‌شود اما $\rho$ از رابطه محاسبه می‌شود؟
4. چرا بردار گرادیان بر امتداد لبه عمود است؟
5. افزایش $\sigma$ در LoG چه اثری بر مقیاس ساختارهای آشکارشده و حساسیت به نویز دارد؟
6. نقش آستانه‌های پایین و بالای Canny و hysteresis چیست؟
7. با استفاده از رابطۀ $\sigma_G^2=\sigma_W^2+\sigma_B^2$ توضیح دهید چرا Otsu می‌تواند واریانس بین‌کلاسی را بیشینه کند.
8. در رشد ناحیه، مقایسۀ پیکسل با مقدار بذر چه تفاوتی با مقایسه با میانگین جاری ناحیه دارد؟
9. چرا K-means به تنهایی اتصال فضایی را تضمین نمی‌کند و SLIC چگونه مختصات فضایی را وارد معیار شباهت می‌کند؟
10. چرا Watershed بدون marker مناسب مستعد بیش‌قطعه‌بندی است؟

## منابع تکمیلیِ راستی‌آزمایی‌شده

این منابع برای کنترل علمی و تکمیل آموزشی استفاده شده‌اند؛ ترتیب فصل از متن پیوست‌شده حفظ شده است.

- R. C. Gonzalez and R. E. Woods, *Digital Image Processing*, 4th ed., Pearson, 2018. منبع کتابی اصلی فصل.
- N. Otsu, “A Threshold Selection Method from Gray-Level Histograms,” *IEEE Transactions on Systems, Man, and Cybernetics*, 9(1), 62–66, 1979. DOI: `10.1109/TSMC.1979.4310076`.
- J. Canny, “A Computational Approach to Edge Detection,” *IEEE TPAMI*, 8(6), 679–698, 1986. DOI: `10.1109/TPAMI.1986.4767851`.
- R. Adams and L. Bischof, “Seeded Region Growing,” *IEEE TPAMI*, 16(6), 641–647, 1994. DOI: `10.1109/34.295913`.
- D. Comaniciu and P. Meer, “Mean Shift: A Robust Approach Toward Feature Space Analysis,” *IEEE TPAMI*, 24(5), 603–619, 2002. DOI: `10.1109/34.1000236`.
- R. Achanta et al., “SLIC Superpixels Compared to State-of-the-Art Superpixel Methods,” *IEEE TPAMI*, 34(11), 2274–2282, 2012. DOI: `10.1109/TPAMI.2012.120`.
- J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” *IEEE TPAMI*, 22(8), 888–905, 2000. DOI: `10.1109/34.868688`.
- L. Vincent and P. Soille, “Watersheds in Digital Spaces: An Efficient Algorithm Based on Immersion Simulations,” *IEEE TPAMI*, 13(6), 583–598, 1991. DOI: `10.1109/34.87344`.


---

**یادداشت تدوین:** شکل‌های موجود در این صفحه بازطراحی/تولید شده‌اند و تصاویر استخراج‌شده از صفحات کتاب Gonzalez در بستهٔ انتشار قرار نگرفته‌اند.