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

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

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

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

${\displaystyle C_{S}={\frac {1}{2}}\sum _{k=1}^{K}{\frac {[g(k)-h(k)]^{2}}{g(k)+h(k)}}}$

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

${\displaystyle C_{A}={\frac {1}{2}}{\begin{Vmatrix}{\dbinom {\cos(\theta _{1})}{\sin(\theta _{1})}}-{\dbinom {\cos(\theta _{2})}{\sin(\theta _{2})}}\end{Vmatrix}}}$

Це половина довжини хорди одиничного кола між одиничними векторами з кутами ${\displaystyle \theta _{1}}$ і ${\displaystyle \theta _{2}}$. Знайдене значення також змінюється від 0 до 1. Загальна вартість співставлення двох точок може бути розрахована як зважена сума двох вищезгаданих вартостей:

${\displaystyle C=(1-\beta )C_{S}+\beta C_{A}\!\,}$

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

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

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

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

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

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

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

${\displaystyle o={\frac {1}{n}}\sum _{i=1}^{n}\left(p_{i}-q_{\pi (i)}\right),A=(Q^{+}P)^{t}}$

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

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

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

${\displaystyle 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.

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

${\displaystyle 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}}$

де ${\displaystyle I_{P}\!}$ та ${\displaystyle I_{Q}\!}$ зображення в градаціях сірого кольору (${\displaystyle I_{Q}\!}$ зображення після перетворення) і ${\displaystyle G\!}$ Гауссівська функція.

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

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

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

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