Розроблення методів розв’язання задач великої розмірності. Розробка комп’ютерної технології текстурної сегментації зображень в прикладних задачах. Побудування моделі текстурного зображення, задання текстур за допомогою марковських випадкових полів.
Аннотация к работе
Національна академія наук України Міжнародний науково-навчальний центр інформаційних технологій та системОсоблива увага присвячена дослідженню можливості знаходження точного розвязку відповідної оптимізаційної задачі, яку називають задачею розмітки. В загальному випадку задача розмітки є NP-повною, для таких задач пропонується знаходити частину точного розвязку, для чого сформульовані відповідні достатні умови. Також в роботі запропонована нова модель текстурного зображення, на підставі якої розглянуто байєсівські задачі розпізнавання з різними штрафними функціями, і для адитивної штрафної функції запропоновано метод знаходження наближеного розвязку задачі. В общем случае задача разметки является NP-полной, для таких задач в работе предлагается находить часть точного решения, а именно, если значение искомой оптимальной разметки не удается определить за полиномиальное время во всех пикселах, то можно попытаться определить за полиномиальное время значение этой разметки в некоторых пикселах. Для нахождения части точного решения в работе предлагается использовать вспомогательные супермодулярные задачи разметки, которые, как известно из общей теории оптимизации, образуют полиномиально разрешимый класс задач.· побудовано модель текстурного зображення, в якій сегментація і кожна з текстур задаються за допомогою окремих марковських випадкових полів; задача прикладний текстура марковський Цей підхід розширює клас практично вирішуваних задач, коли точний розвязок всієї задачі в цілому не може бути знайдений, і замість відмови від прийняття рішення відшукується оптимальна розмітка певної частини пікселів. До (max, ) задач, крім задачі текстурної сегментації зображень, зводяться також: задача реставрації зашумленого зображення, задача відновлення рельєфу за стереопарою зображень, задача пошуку оптичного потоку тощо. Розроблені методи спрощення NP-повних (max, ) задач, а також методи розвязання супермодулярних (max, ) задач великої розмірності суттєво розширюють можливості розвязання всіх задач, які можуть бути сформульовані як (max, ) задачі, в тому числі і тих, які названі вище. Наведені в роботі приклади показують, що використання допоміжних супермодулярних (max, ) задач дозволяє визначити значення оптимальної розмітки початкової задачі в деяких пікселах поля зору (іноді більше ніж в 90% пікселів).