Значення форми

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Значення форми (англ. – shape context) – характеристика опису, що використовується в розпізнаванні об’єктів. Термін було запропоновано Сержем Белонгі та Джинтендра Маліком в їхній статті "Matching with Shape Contexts" (2000).[1]

Теорія[ред.ред. код]

Характеристика призначена для опису форм з метою вимірювання їхньої подібності та відновлення точкових відповідностей.[1] Основною ідеєю є вибір n точок контуру форми. Для кожної точки pi форми розглядаються n − 1, векторів, отриманих шляхом з’єднання точки pi з усіма іншими точками. Множина усіх цих векторів є описом локалізованої форми локалізованої в цій точці, але цей опис є занадто деталізованим. Ключова ідея полягає в тому, що розподіл по відносній позиції є надійним, компактним і характерним ідентифікатором. Таким чином, для точки pi, груба гістограма відносних координат решти n − 1 точок,

h_i(k) = \#\{q \ne p_i  :  (q - p_i) \in \mbox{bin}(k)\}

визначається як форма контексту p_i. Стовпчики гістограми (англ. – bins) зазвичай приймають рівномірними в полярних координатах. Підтвердження факту, що форма контексту є характерним ідентифікатором, можна побачити на рисунку нижче, де зображено форми контекстів двох різних варіантів написання літери «А».

Shapecontext.jpg

На рис. (a) і (b) зображено точки контурів двох форм. На рис. (c) є зображення в полярних координатах, призначене для розрахунку значення форми. На рис. (d) зображено значення форми для круга, на рис. (e) – значення форми ромба, на рис. (f) – значення форми трикутника. Як можна помітити з рисунків (d) та (e) , значення форми для двох тісно пов’язаних точок, дуже схожі, в той час як значення форми на рисунку (f) істотно відрізняється.

Тепер для того, щоб ідентифікатор ознаки (характеристики) був корисний, він повинен мати інваріанти. Зокрема, він має бути інваріантним відносно перенесення, масштабування, наявності невеликих завад та залежати від повороту. Незмінність значення форми при перенесенні є зрозумілою. Незмінність при масштабуванні досягається за рахунок нормалізації всіх радіальних відстаней середнім значенням відстані \alpha між всіма парами точок форми.[2][3] Для нормалізації також може бути використана медіанна відстань.[1][4] Емпірично продемонстровано, що при використанні множини синтетичних точок для експериментів[5] , значення форми є стійким до деформації, шумів і відхилень.[4]

Можна забезпечити стійкість значення форми також і при повороті. Один зі способів – виміряти кути в кожній точці по відношенню до напрямку дотичної в цій точці (оскільки точки обираються на краях). В результаті буде отримано абсолютно стійкий до повороту ідентифікатор. Але це не завжди бажано, оскільки деякі локальні характеристики втрачають їхнє описове значення, якщо вимірюються не по відношенню до того ж базису. Багато додатків не використовують стійкість до повороту, щоб, наприклад відрізняти цифри «6» та «9».

Використання в зіставленні форм[ред.ред. код]

Завершена система, що використовує значення форми для зіставлення, складається з таких кроків:

  1. Довільним чином обрати множину точок, що лежать на краях відомої форми та множину точок, що належать невідомій формі.
  2. Для кожної точки, знайденої на кроці 1, обрахувати значення форми.
  3. Зіставити кожну точку відомої форми з точкою невідомої форми. Для зменшення кількості співставлень, спершу потрібно обрати перетворення (наприклад, афінне), що перетворює межі відомої форми в межі невідомої форми. Потім обрати точку невідомої форми, що найбільш точно відповідає кожній перетвореній точці відомої форми.
  4. Обчислити відстань між значеннями форми для кожної пари точок цих двох форм. Варто використати зважену суму відстаней між значеннями форми, відстань обробки зображення та силу вигину (міра, що вказує наскільки сильні перетворення потрібні, щоб зрівняти дві форми).
  5. Для визначення невідомої формі, використовуйте Класифікатор найближчого сусіда, щоб порівняти його форму з формою відомих об'єктів.

Деталі реалізації[ред.ред. код]

Крок 1: Визначення списку точок на краях форми[ред.ред. код]

Цей підхід припускає, що форма об'єкта, по суті, визначається скінченною підмножиною точок, що належать внутрішнім або зовнішнім контурам об'єкта. Множина цих точок може бути отримана за допомогою детектора країв Канні (англ. – Canny edge detector) і вибору випадкового набору точок з цих країв. Зверніть увагу, що ці точки не повинні і в більшості випадків не відповідають ключовим точкам, таким як максимуми кривизни або точкам перегину (англ. – inflection points). Бажано обирати форми з приблизно рівномірним інтервалом, хоча це не критично.[2]

Крок 2: Обчислення значення форми[ред.ред. код]

Цей крок докладно описаний у розділі Теорія.

Крок 3: Розрахунок матриці вартості[ред.ред. код]

Розглянемо дві точки p і q, для яких маємо нормалізовані гістограми з K стовпцями – g(k) і h(k). Оскільки значення форми – розподіли представлені у вигляді гістограм, то закономірно використати статистичний χ2 тест в якості "вартості форми контексту" для двох точок:

C_S = \frac{1}{2}\sum_{k=1}^K \frac{[g(k) - h(k)]^2}{g(k) + h(k)}

Це значення змінюється в діапазоні від 0 до 1.[1] Окрім показника вартості значення форми, може бути використаний показник додаткової вартості, що ґрунтується на зовнішньому вигляді. Наприклад, це може бути міра несхожості тангенса кута (застосовується при розпізнаванні цифр):

C_A = \frac{1}{2}\begin{Vmatrix}
 \dbinom{\cos(\theta_1)}{\sin(\theta_1)} - \dbinom{\cos(\theta_2)}{\sin(\theta_2)}
\end{Vmatrix}

Це половина довжини хорди одиничного кола між одиничними векторами з кутами \theta_1 і \theta_2. Знайдене значення також змінюється від 0 до 1. Загальна вартість співставлення двох точок може бути розрахована як зважена сума двох вищезгаданих вартостей:

C = (1 - \beta)C_S + \beta C_A\!\,

Тепер для кожної точки pi першої форми та точки qj другої форми, потрібно розрахувати загальну вартість, як описано вище, і позначити це значення Ci,j. Обраховані значення вартостей для всіх точок формують матрицю вартостей.

Крок 4: Знаходження такого зіставлення, яке мінімізує загальну вартість[ред.ред. код]

Результат зіставлення

Тепер потрібно знайти таке попарне співставлення кожної точки pi першої форми, з точкою qj другої форми, що мінімізує загальну вартість зіставлення:

H(\pi) = \sum_i C\left (p_i,q_{\pi (i)} \right )

Це може бути виконано за час O(N^3) , використовуючи угорський метод (Hungarian method) , хоча існують більш ефективні алгоритми.[6] Щоб отримати надійну обробку відхилень, можна додати "штучні" вузли, які мають постійну, але досить велику вартість співставлення по відношенню до матриці вартостей. Це змусить алгоритм зіставляти точки, що є відхиленнями, з штучно введеними точками тільки у випадку, якщо немає реального зіставлення.

Крок 5: Моделювання перетворень[ред.ред. код]

Враховуючи безліч відповідностей між скінченною множиною точок двох фігур перетворення T : \Bbb{R}^2 \to \Bbb{R}^2 може бути оцінене як співставлення будь-якої точки однієї фігури з точкою іншої фігури. Кілька варіантів такого перетворення описані нижче.

Афінне перетворення[ред.ред. код]

Афінне перетворення є стандартним вибором: T(p) = Ap + o\!. Розв’язок методом найменших квадратів матриці A і вектор зміщення o обчислюють наступним чином:

o = \frac{1}{n}\sum_{i=1}^n \left (p_i - q_{\pi(i)} \right ),
      A = (Q^+ P)^t

Де P = \begin{pmatrix}
             1 & p_{11} & p_{12} \\
             \vdots & \vdots & \vdots \\
             1 & p_{n1} & p_{n2}
\end{pmatrix} з аналогічним виразом для Q\!. Q^+\! є псевдо оберненою матрицею для Q\!.

Крок 6: Обчислення значення форми[ред.ред. код]

Тепер знайдемо відстань між значеннями двох форм P\! і Q\!. Ця відстань є зваженою сумою трьох значень:

Відстань значення форми: це симетрична сума вартості зіставлень значень форми для точок з найкращою відповідністю:

D_{sc}(P,Q) = \frac{1}{n}\sum_{p \in P} \arg \underset{q \in Q}{\min} C(p,T(q)) + \frac{1}{m}\sum_{q \in Q} \arg \underset{p \in P}{\min} C(p,T(q))

де T(•) – це розраховане перетворення, що перетворює точки форми Q в точки форми P.

Вартість входження: Після встановлення відповідностей та правильно перетворення одного зображення в інше, можна визначити вартість входження, як суму квадратів різниць інтенсивностей в вікні Гаусса навколо відповідних точок зображення:

D_{ac}(P,Q) = \frac{1}{n}\sum_{i=1}^n\sum_{\Delta \in Z^2} G(\Delta)\left [I_P(p_i + \Delta) - I_Q(T(q_{\pi(i)}) + \Delta)\right ]^2

де I_P\! та I_Q\! зображення в градаціях сірого кольору (I_Q\! зображення після перетворення) і G\! Гауссівська функція.

Вартість перетворення: Остаточна вартість D_{be}(P,Q)\!\, вимірює перетворення, що потрібні, щоб вирівняти два зображення.

Тепер маючи спосіб обчислення відстані між двома формами, можемо застосувати класифікатор (k-NN) найближчого сусіда з відстанню, яка визначається як відстань форми. Результати застосування наведені в наступному розділі.

Результати[ред.ред. код]

Розпізнавання цифр[ред.ред. код]

Автори Серж Белонгі та Джинтендра Малік випробували їхній підхід на базі даних рукописних цифр. Більше, ніж 50 алгоритмів було протестовано на цій базі даних. База містить 60,000 навчальних зразків і 10,000 тестових зразків. Коефіцієнт помилок для цього підходу становив 0.63% для використаних 20,000 навчальних зразків. На даний момент, найнижчий рівень помилок становить 0.35%.

Пошук торгових марок[ред.ред. код]

Значення форми були використані для отримання найбільш подібних торгових знаків з бази даних за запитом (корисно при виявленні порушень, що стосуються товарних знаків). Жоден візуально схожий товарний знак не був пропущений алгоритмом (перевірено вручну авторами).

Зовнішні посилання[ред.ред. код]

Джерела[ред.ред. код]

  1. а б в г S. Belongie and J. Malik(2000). "Matching with Shape Contexts". IEEE Workshop on Contentbased Access of Image and Video Libraries (CBAIVL-2000).
  2. а б S. Belongie, J. Malik, and J. Puzicha Shape Matching and Object Recognition Using Shape Contexts // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 24 (April 2002) (24) С. 509–521. DOI:10.1109/34.993558.
  3. S. Belongie, J. Malik, and J. Puzicha(July 2001). "Matching Shapes". Eighth IEEE International Conference on Computer Vision (July 2001).
  4. а б S. Belongie, J. Malik, and J. Puzicha(2000). "Shape Context: A new descriptor for shape matching and object recognition". NIPS 2000.
  5. H. Chui and A. Rangarajan(June 2000). "A new algorithm for non-rigid point matching". CVPR, 44–51.
  6. R. Jonker and A. Volgenant A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems // Computing. — 38 (1987) (4) С. 325–340. DOI:10.1007/BF02278710.