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

تعاریف

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

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

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

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

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

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

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

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

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

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

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

برش گراف

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

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

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

ولگشت زن

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

سلسله مراتب

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