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

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

Теорія

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

h_{i}(k)=\#\{q\neq p_{i}:(q-p_{i})\in {\mbox{bin}}(k)\}

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

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

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

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

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

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

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

Деталі реалізації

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

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

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

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

Крок 3: Розрахунок матриці вартості

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

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}\!\,

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

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

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

H(\pi )=\sum _{i}C\left(p_{i},q_{\pi (i)}\right)

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

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

Враховуючи безліч відповідностей між скінченною множиною точок двох фігур перетворення $T:\mathbb {R} ^{2}\to \mathbb {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) найближчого сусіда з відстанню, яка визначається як відстань форми. Результати застосування наведені в наступному розділі.

Результати

Розпізнавання цифр

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

Пошук торгових марок

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

Див. також

MNIST (база даних)

Примітки

↑ ^а ^б ^в ^г S. Belongie and J. Malik (2000). Matching with Shape Contexts (PDF). IEEE Workshop on Contentbased Access of Image and Video Libraries (CBAIVL-2000).
↑ ^а ^б S. Belongie, J. Malik, and J. Puzicha (April 2002). Shape Matching and Object Recognition Using Shape Contexts (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 24 (24): 509—521. doi:10.1109/34.993558. Архів оригіналу (PDF) за 13 травня 2013. Процитовано 14 грудня 2012.
↑ S. Belongie, J. Malik, and J. Puzicha (July 2001). Matching Shapes (PDF). Eighth IEEE International Conference on Computer Vision (July 2001). Архів оригіналу (PDF) за 13 травня 2013. Процитовано 14 грудня 2012.
↑ ^а ^б S. Belongie, J. Malik, and J. Puzicha (2000). Shape Context: A new descriptor for shape matching and object recognition. NIPS 2000.
↑ H. Chui and A. Rangarajan (June 2000). A new algorithm for non-rigid point matching. CVPR. Т. 2. с. 44—51.
↑ R. Jonker and A. Volgenant (1987). A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing. 38 (4): 325—340. doi:10.1007/BF02278710.

Посилання

Matching with Shape Contexts [Архівовано 18 грудня 2012 у Wayback Machine.]
MNIST database of handwritten digits [Архівовано 7 квітня 2021 у Wayback Machine.]
Columbia Object Image Library (COIL-20) [Архівовано 21 грудня 2012 у Wayback Machine.]
Caltech101 Database [Архівовано 6 грудня 2013 у Wayback Machine.]
The clustering agglomerative hierarchical algorithm [Архівовано 5 березня 2016 у Wayback Machine.]
Пошук образів за їх інваріантними та параметричними ознаками [Архівовано 5 березня 2016 у Wayback Machine.]
Пошук образів за індексами кластерів фрагментів зображень [Архівовано 20 травня 2018 у Wayback Machine.]

[shape_1-1] а ^б ^в ^г S. Belongie and J. Malik (2000). Matching with Shape Contexts (PDF). IEEE Workshop on Contentbased Access of Image and Video Libraries (CBAIVL-2000).

[shape_2-2] а ^б S. Belongie, J. Malik, and J. Puzicha (April 2002). Shape Matching and Object Recognition Using Shape Contexts (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 24 (24): 509—521. doi:10.1109/34.993558. Архів оригіналу (PDF) за 13 травня 2013. Процитовано 14 грудня 2012.

[shape_3-3] S. Belongie, J. Malik, and J. Puzicha (July 2001). Matching Shapes (PDF). Eighth IEEE International Conference on Computer Vision (July 2001). Архів оригіналу (PDF) за 13 травня 2013. Процитовано 14 грудня 2012.

[shape_4-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. Т. 2. с. 44—51.

[6] R. Jonker and A. Volgenant (1987). A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing. 38 (4): 325—340. doi:10.1007/BF02278710.

[1]

[2]

[3]

[4]

[5]

[6]