Лісове перетворення зображення (, IFT) — метод цифрової обробки зображень, створений Алешандре Фалканом, Жорже Столфі та Роберто де Аленкар Лотуфо (). Автори показали, що IFT дає змогу заощаджувати час під час обробки двовимірних і тривимірних зображень, а також відео.
Історія
У 1959 році Дейкстра вдосконалив алгоритм обчислення вартості шляхів у загальному графі, який запропонували Мур у 1957 році і Беллман у 1958 році. Через десять років Дайл удосконалив алгоритм за допомогою сортування комірками. Відтоді алгоритм багато разів змінювали й удосконалювали. Саме цю версію вдосконалили Фалкан, Столфі та Лотуфо.
Визначення
Лісове перетворення зображення — це видозмінений алгоритм Дейкстри пошуку найкоротших шляхів, пристосований до кількох джерел (початкових пікселів). Перетворення будує граф із пікселів зображення, а зв'язки між цими точками задають «вартість» шляху. Вартість обчислюють, аналізуючи характеристики шляху між пікселями, наприклад рівень сірого, колір, градієнт тощо. Після завершення перетворення повертаються три величини: попередник, вартість і мітка. Багато операторів цифрової обробки зображень можна реалізувати, обробляючи ці три величини.
Оптимізація
Залежно від обраного оператора цифрової обробки зображень алгоритм можна додатково видозмінити для оптимізації з урахуванням того, що саме використовує цей оператор. Алгоритм також можна оптимізувати, уникаючи повторного обчислення шляхів: для цього вже обчислені значення відстежують у зовнішній довідковій таблиці. «Зворотних дуг» можна позбутися, порівнюючи вартість шляху в обох напрямках і відкидаючи дорожчий шлях. Для деяких шляхів алгоритм може повертати нескінченну вартість; такі шляхи можна виключати з подальших обчислень.
Див. також Обробка зображень Сегментація методом водоподілу Випадковий ліс
Примітки