Управляющие системы и машины, №2, 2018, стаття 4
DOI: https://doi.org/10.15407/usim.2018.02.031
Водолазский Е.В., Латюк С.А. Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей. Управляющие системы и машины. 2018. № 2. C. 31-41.
УДК 004.318
Є.В. Водолазський, ст. наук. співр.,
С.О. Латюк, інж.-програм. I кат., serhiylatyuk55@gmail.com,
Міжнародний науково-навчальний центр інформаційних технологій та систем НАН та МОН України, просп. Глушкова, 40, Київ 03187, Україна
Блочна модифікація сэмплування за Гибсом для розпізнавання прихованих марковських полів
Вступ. Статтю присвячено демонстрації того, що блокова модифікація семплування за Гібсом може бути конструктивно реалізована та з успіхом застосована у вирішенні задач розпізнавання зображень, зокрема — у вирішенні задач розмітки, до яких зводяться деякі задачі комп’ютерного зору. Відомо, що задачі розмітки полягають в оптимізації функцій від великої кількості дискретних аргументів. Специфіка цих задач полягає в тому, що функція, яку необхідно оптимізувати, є сумою великої кількості доданків, кожен з яких залежить від
невеликої кількості змінних. Множина таких задач утворює NP-повний клас, а відомі поліноміально розв’язні підкласи містять далеко не всі ситуації, які можуть виникнути на практиці. Тому є потреба досліджувати також неточні методи розв’язання задач такого типу, одним з яких є семплування за Гібсом. Сенс застосовувати семплування не у всіх задачах розпізнавання, проте при деяких функціях штрафу воно може бути використане для статистичного оцінювання певних величин.
Мета статті — демонстрація існування конструктивної реалізації блочної модифікації семплування за Гібсом для розпізнавання зображень. Порівняння її роботи зі стандартною реалізацією та пошук текстур, на яких блочна модифікація працює краще. Перевірка придатності запропонованого методу оцінки математичного сподівання для використання при розпізнаванні прихованих марківських полів.
Методи. Блочну модифікацію семплування за Гібсом для розпізнавання зображень побудовано на принципах динамічного програмування. Додаток, що дозволяє генерувати зображення заданої текстури, обирати потрібну модифікацію семплування за Гібсом розв’язку задачі розпізнавання та отримати графіки залежності швидкості розпізнавання кожного алгоритму від часу реалізовано на мові Python з використанням бібліотеки
Cython для написання розширень на мові С.
Результат. Виявлено, що блочна модифікація семплування за Гібсом на так званих «монотонних» текстурах при високому рівні шуму працює краще, ніж стандартний алгоритм. На «діагональних» текстурах, які дуже часто зустрічаються, блочна модифікація працює не гірше, ніж загальновідомий метод. Також виявлено, що на «монотонних» текстурах запропонований метод для оцінки математичного сподівання демонструє кращі результати, ніж загальноприйнятий.
Висновок. Блочну модифікацію семплування за Гібсом можна використати для розпізнавання зображень, завдяки наявності конструктивної реалізації, яка працює за поліноміальний час. Хоча асимптотично одна ітерація блочної модифікації виконується повільніше, ніж одна ітерація стандартного алгоритму семплування за Гібсом, проте на малій кількості міток, на «монотонних» текстурах розпізнавання в цілому відбувалося швидше завдяки блочному семплуванню, що свідчить про спроможність даного алгоритму враховувати певну додаткову інформацію, яка в свою чергу пришвидшує процес розв’язку. А отже, є сенс проводити подальші дослідження в
даній галузі.
Завантажити повний текст в PDF (россійською).
Ключові слова: семплування за Гібсом, Гібсівський самплер, задачі розмітки, розпізнавання прихованих марківських полів.
Отримано 06.07.2018
