آب‌پخشان (پردازش تصویر)

آب‌پخشان (به انگلیسی: (Watershed (image processing) در مطالعه پردازش تصویر، یک تبدیل تعریف شده بر تصاویر سیاه سفید است. این نام به صورت استعاری به یک حوضه آبریز زمین‌شناسی یا تقسیم زهکشی که حوضه‌های زهکشی مجاور را جدا می‌کند، اشاره دارد. تبدیل آب‌پخشان یا کار روی نقشه توپوگرافی تصویر عمل می‌کند، ارتفاع آن را با روشنایی هر نقطه نشان می‌دهد و خطوطی را که در امتداد تپه‌ها قرار دارند پیدا می‌کند.

تعاریف

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

• 
  تسکین دامنه گرادیان
• 
  دامنه گرادیان
• 
  آب پخشان گرادیان
• 
  آب پخشان تسکین گرادیان

آب‌پخشان توسط سیل

در سال ۱۹۷۹ میلادی S. Beucher و C. Lantuejoul ایده این روش را مطرح کردند. ایده اصلی برپایه قرار دادن منبع آب در هر مینیموم موضعی است که نهایتاً منجر به آبرسانی به کل حوضه آبریز از جانب منبع شده و موانعی و سدهایی را در هنگامی که آب منابع مختلف به هم می‌رسد ایجاد خواهد کرد. مجموعه ای از این موانع تشکیل حوضه آب‌پخش را خواهد داد.

آب‌پخشان با فاصله توپوگرافی

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

آب‌پخشان با اصل ریزش آب

به‌طور شهودی، آب‌پخشان جداسازی ناحیه مینیمم از جایی که یک قطره آب می‌تواند به سمت حداقل مقادیر مجزا جریان یابد. فرمولاسیون ایده شهودی در [۴] برای تعریف یک آب‌پخشان از نمودار مبتنی بر لبه ارائه شده‌است.

آب‌پخشان میان پیکسل

S. Beucher و F. Meyer یک پیاده‌سازی الگوریتمی بین پیکسل با روش آب پخشان معرفی کردند. این روش به شرح زیر است:

1. روی هر مینیمم با یک برچسب متمایز برچسب بزنید. مجموعه S را با گره‌های برچسب‌خورده مقدار اولیه دهید.
2. گره x را با حداقل ارتفاع از مجموعه S استخراج کنید و به صورت {F(x) = min{F(y)|y ∈ S است. برچسب x را به هرگره برچسب‌نخورده y مجاور x نسبت دهید و y را در S قرار دهید.

۳. مرحله ۲ را تا زمانی که S خالی شود تکرار کنید.

آب‌پخشان توپولژیکی

نظریات قبلی برحوضه آبریز تمرکز داشتند، اما بر خط جدا کنندهٔ تولید شده تمرکز نداشتند. آب‌پخشان توپولوژیکی توسط G. Bertrand و M. Couprie در سال ۱۹۹۷ معرفی شد،1997 و beneficiate از اساسی زیر را اموال. یک تابع W یک حوضو از ویژگی‌های بنیادین زیر بهره‌مند شد. یک تابع W یک آب‌پخشان تابع F است اگر و تنها اگر W ≤ F و W تضاد بین ناحیه مینیمم F را حفظ کند؛ جایی که تضاد بین دو ناحیه مینیمم M1 و M2 به عنوان حداقل ارتفاع از M1 به M2 صعود کند، تعریف می‌شود. یک الگوریتم کارآمد در این مقاله به تفصیل شرح داده شده‌است.

الگوریتم

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

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

الگوریتم سیل Meyer

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

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

1. مجموعه‌ای از نشانگرها، پیکسل‌هایی که سیل از آن شروع خواهد شد- انتخاب می‌شوند و به هر کدام برچسب متفاوتی داده می‌شود.
2. پیکسل‌های همسایه هر ناحیه علامت‌گذاری شده بر اساس اندازه گرادیان پیکسل در یک صف اولویت قرار می‌گیرند.
3. پیکسل با سطح اولویت پایین‌تر از صف اولویت استخراج می‌شود. اگر همسایه‌های پیکسل استخراج شده قبلاً برچسب یکسانی داشته باشد.
4. انجام گام ۳ تا زمانی که صف اولویت خالی شود. پیکسل‌های برچسب نخورده خطوط آب‌پخشان هستند.

الگوریتم جنگل پوشا بهینه (قطع آب‌پخشان)

آب‌پخشان به عنوان جنگل پوشا بهینه توسط Jean Cousty و همکارانش معرفی شد. آن‌ها پایداری این را فراهم می‌کنند: آن‌ها می‌توانند به‌طور معادل با حوضه آبریزشان (از طریق کاهش سریع ویژگی) یا با "خطوط جدا کننده " که این حوضه‌های آبریز را جدا می‌کنند (از طریق اصل ریزش آب) تعریف شوند. پس آن‌ها از طریق یک قضیه هم‌ارزی، بهینگی را از نظر مینیمم جنگل پوشا ثابت کردند. پس از آن، آن‌ها یک الگوریتم زمانی خطی برای محاسبه آن‌ها معرفی کردند. توجه داشته باشید که ویژگی‌های مشابه در چارچوب‌های دیگر تأیید نشده‌اند و الگوریتم پیشنهادی، هم در تئوری و هم در عملی، کارآمدترین الگوریتم موجود است.

• 
  یک تصویر با استفاده از نشانگر (سبز) و حداقل پوشا جنگل در محاسبه گرادیان تصویر.
• 
  نتیجه این تقسیم بندی با حداقل پوشا جنگل

ارتباط با دیگر الگوریتم‌های بینایی ماشین

برش گراف

در سال 2007 C. Aleneu و همکاران ارتباط برش نمودار با جنگل‌های پوشا بهینه را ایجاد کردند. به دقیق‌تر، آن‌ها نشان دادند که وقتی قدرت وزن نمودار از عدد معینی بالاتر باشد، برشی که انرژی برش گراف را مینیمم می‌کند، برشی با ماکزیمم کردن جنگل پوشا است.

جنگل کوتاه‌ترین مسیر

تبدیل جنگل‌سازی تصویر(IFT) فالکائو و همکاران روشی برای محاسبه جنگل کوتاه‌ترین مسیر است. این توسط J. Cousty و همکاران نشان داده شده‌است که وقتی مارکرهای IFT مربوط به اکسترمم‌های تابع وزن است، برش القا شده با جنگل، یک برش آب‌پخشان است.

ولگشت زن

الگوریتم ولگشت‌زن یک الگوریتم بخش‌بندی است که مسئله ترکیبی دیریکله را حل می‌کند، که در سال ۲۰۰۶ توسط L. Grady برای بخش‌بندی تصویر استفاده شده‌است. در سال 2009 C. Couprie و همکاران اثبات کردند که وقتی قدرت وزن نمودار به بی‌نهایت متمایل شود، برشی که انرژی ولگشت‌زن را مینیمم می‌کند. برشی با ماکزیمم کردن انرژی جنگل پوشا است.

سلسله مراتب

تبدیل آب‌پخشان سلسله مراتبی نتایج را به نمایش نموداری (به عنوان مثال روابط همسایگی مناطق بخش‌بندی شده) تبدیل می‌کند و تبدیل آب‌پخشان بیشتر به صورت بازگشتی اعمال می‌شود. برای جزئیات بیشتر به مراجعه کنید. یک نظریه که آب‌پخشان را به بخش‌بندی‌های سلسله مراتبی ارتباط می‌دهد در منبع مقابل گسترش داده شده‌است.

منابع

• Fernand Meyer. Un algorithme optimal pour la ligne de partage des eaux. Dans 8me congrès de reconnaissance des formes et intelligence artificielle, Vol. 2 (1991), pages 847–857, Lyon, France.
• Luc Vincent and Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583–598.
• L. Najman and M. Schmitt. <g class="gr_ gr_28 gr-alert gr_gramm gr_inline_cards gr_run_anim Grammar only-ins replaceWithoutSep" id="28" data-gr-id="28">Geodesic</g> saliency of watershed contours and hierarchical segmentation. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, Num. 12 (1996), pages ۱۱۶۳–۱۱۷۳.
• J.B.T.M. Roerdink and A. Meijster. The watershed transform: definitions, algorithms, and parallelization strategies. In Fundamenta Informaticae 41 (2000), pp. 187–228.
• Laurent Najman, Michel Couprie <g class="gr_ gr_51 gr-alert gr_gramm gr_inline_cards gr_run_anim Punctuation only-ins replaceWithoutSep" id="51" data-gr-id="51">and</g> Gilles Bertrand. Watersheds, mosaics, and the emergence paradigm. In Discrete Applied Mathematics, Vol. 147, Num. 2–3(2005), Pages ۳۰۱–۳۲۴.
  

پیوند به بیرون

• حوزه تحول با انیمیشن از حوزه آبخیز الگوریتم.
• Topological آبخیز تبدیل با مقالات و سخنرانی اسلاید و کد منبع.
• یک منبع باز آبخیز پلاگین برای ImageJ.
• توپولوژی ToolKit (2D و 3D حوضه بر اساس مورس پیچیده)