فیلتر میانه

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

توضیح الگوریتم

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

فیلتر میانه در فضای یک‌بعدی

در حالتی که ورودی یک بردار یا فضای یک‌بعدی باشد باید به جای هر k عنصر متوالی میانه آن را جایگزین کنیم؛ به عنوان مثال الگوریتم فیلتر میانه با  را برای یک بردار ورودی  را اعمال می‌کنیم، برای اجرای فیلتر میانه باید باشد. در مثال زیر است.

تابع غیرخطی فیلتر میانه در حالت کلی

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

تبدیل محاسبه فیلتر میانه به مجموع میانه‌های دودویی

تحلیل و محاسبه تابع فیلتر میانه با توجه به مقادیر موجود در سیگنال ورودی می‌تواند سخت و هزینه‌بر باشد و در صورتی که بخواهیم تأثیرگذاری چند فیلتر غیرخطی را بر یکدیگر تحلیل کنیم این فرایند سخت‌تر هم می‌شود، از این رو گاهی برای محاسبه تابع غیرخطی فیلتر میانه آن را به چند فیلتر خطی دودویی تبدیل می‌کنند و سپس جمع ایشان را پیدا می‌کنند. برای انجام این کار می‌توان از الگوریتم تجزیه Threshold استفاده کرد. دقت کنید که مزیت اصلی این کار این است که می‌توان میانه بردار دودویی را راحت‌تر از حالت عادی محاسبه کرد، به عنوان مثال میانهٔ بردار دودویی با طول ۳ به شکل زیر قابل محاسبه است.
 باید توجه داشت که عملیات بیتی در سیستم‌های کامپیوتری راحت‌تر و سریع‌تر از جمع اعداد اتفاق می‌افتد.

فیلتر میانه در فضای دوبعدی

برای محاسبه فیلتر میانه در فضای دوبعدی عنصر مرکزین هر زیرماتریس با میانه تمام عناصر اطراف به شعاع k جایگزین می‌شود. شبه‌کد زیر عملکرد این الگوریتم نوشته شده‌است. 
   allocate outputPixelValue[image width][image height]
   allocate window[window width * window height]
   edgex := (window width / 2) rounded down
   edgey := (window height / 2) rounded down
   for x from edgex to image width - edgex
       for y from edgey to image height - edgey
           i = 0
           for fx from 0 to window width
               for fy from 0 to window height
                   window[i] := inputPixelValue[x + fx - edgex][y + fy - edgey]
                   i := i + 1
           sort entries in window[]
           outputPixelValue[x][y] := window[window width * window height / 2]
دقت کنید که این الگوریتم برای پردازش فیلتر میانه برای تصاویر با یک کانال رنگی نوشته شده‌است؛ به عنوان مثال در تصاویری که از مدل رنگی RGB استفاده می‌کنند باید الگوریتم فوق سه بار برای هر سه کانال رنگی اجرا شود، همچنین این الگوریتم مرزهای عکس را در فیلتر لحاظ نمی‌کند. یعنی مقادیر مرزی ماتریس (سطر و ستون اول و آخر) تغییر نمی‌کنند.

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

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

معضلات اجرایی الگوریتم

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