Градієнт растрового зображення

Одним із важливих етапів розпізнавання візуальних образів є виділення та векторизація контурів об'єктів. Цей факт уже давно, ще з петрогліфів кам'яної доби, засвоєний художниками. Процес створення малюнка доцільно розбити на два етапи - спершу легенько накидати контури об'єктів олівцем, а вже потім наносити колір фарбами.

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

Розглянемо тепер технічний бік справи. Як правило, контур розділяє два предмета (або об'єкт і фон), що мають різні кольори. Тому при переході через контур колір пікселів картинки змінюється різко, практично стрибком. Нижче подано три картинки. Перша картинка є растровим зображенням кукурудзи (JPEG-формат) тобто оригіналом, друга картинка є взяттям градієнта першої після деякого згладжування, а третя є векторизацією другої.

→ →

В комп'ютері колір пікселя описується одним числом для монохромних зображень (в градаціях сірого), і кількома числами для кольорових зображень (три компоненти для RGB-представлення кольору). Кожна кольорова компонента $F^{[i]}$ є функцією координат $(x,y)$:

$(1)\qquad F^{[i]}=F^{[i]}(x,y)$

Тут індекс $i\in \{1,2,3\}$ позначає один із базових кольорів - червоний, зелений та синій. Для растрової картинки, функції $F^{[i]}$ визначені лише для цілих $(x,y)$, тобто в центрах пікселів. Проводячи згладжування, можна розглядати також значення цих функцій у всіх проміжних точках, тобто вважати координати дійсними числами, що обмежені розмірами картинки:

$(2)\qquad 0<=x<=width;\qquad 0<=y<=height$

Неперервна модель градієнта

Припустимо, що після згладжування функції $F^{[i]}$ стали диференційовними. Сукупність частинних похідних по іксу та ігреку утворює двовимірний вектор градієнта, $\mathbf {G}$ який звісно для кожної компоненти кольору буде свій:

$(3)\qquad \mathbf {G} ^{[i]}=\left\{{\partial F^{[i]} \over \partial x},{\partial F^{[i]} \over \partial y}\right\}$

Кожен з цих векторів характеризується двома параметрами: довжиною та напрямком. Довжина вектора обчислюється як корінь квадратний із суми квадратів його проєкцій:

$(4)\qquad |\mathbf {G} |={\sqrt {G_{x}^{2}+G_{y}^{2}}}$

У застосуванні до зображення, градієнт буде великим на контурах предметів і малим в областях постійного кольору, або в областях де колір змінюється плавно. Цією властивістю можна скористатися для знаходження контурів, наприклад можна виділити всі пікселі, в яких величина градієнта перевищує задане порогове значення.

Очевидно, що три вектора градієнтів для різних компонент кольору є частково залежними один від одного. Наприклад, на межі між червоною і зеленою областю, червоний і зелений градієнт будуть великими, а синій градієнт дорівнюватиме нулю. Очевидно також, що усі ненульові градієнтні вектори (в даному випадку червоний і зелений), будуть ортогональні до контуру. Поміж собою градієнтні вектори можуть бути як співнапрямлені так і протилежно напрямлені.

Сумарний градієнт усіх кольорів

Формула (4) дозволяє знаходити контури монохромного зображення. Цю формулу можна легко узагальнити на випадок кольорового зображення, якщо під коренем брати суму квадратів градієнтів від усіх компонентів кольору:

$(5)\qquad |\mathbf {G} |={\sqrt {\sum _{i}{\left(G_{x}^{[i]}\right)}^{2}+{\left(G_{y}^{[i]}\right)}^{2}}}$

Саме таким чином і був обчислений градієнт зображення кукурудзи (дивіться картинки вище).

Проте з напрямками виникає проблема: лінійні формули додавання векторів можуть давати в сумі нуль, як наприклад при розгляді межі між червоною та зеленою областю.

Комплексний квадрат градієнта

Досить природно можна узагальнити формулу (5) таким чином, щоб зберігалась інформація про напрямки градієнтів. Для цього треба перейти в область комплексних чисел. Розглянемо комплексне число

$(6)\qquad z=G_{x}+iG_{y}$

що містить інформацію як про величину так і про напрям вектора градієнта. Квадрат його є також комплексним числом

$(7)\qquad z^{2}=\left(G_{x}+iG_{y}\right)^{2}=G_{x}^{2}-G_{y}^{2}+2iG_{x}G_{y}$

і також містить інформацію як про величину так і про напрям градієнта. Зауважимо, що протилежно напрямлені вектори мають співнапрямлені комплексні градієнти $(-z)^{2}=z^{2}$. В застосуванні до кольорового зображення це корисна властивість, оскільки на розглянутому вище прикладі межі між червоною та зеленою областями, градієнти різних кольорів будуть посилювати комплексну суму:

$(8)\qquad Q=\sum _{k}{\left(G_{x}^{[k]}+iG_{y}^{[k]}\right)^{2}}=a+bi$

Очевидно, величина градієнта дорівнює квадратному кореню із модуля комплексного числа $Q$:

$(9)\qquad |\mathbf {G} |={\sqrt {|Q|}}={\sqrt[{4}]{a^{2}+b^{2}}}$

а одиничний вектор напрямку $\mathbf {n} =\{n_{x},n_{y}\}$ можна знайти виходячи із формули:

$(10)\qquad (n_{x}+in_{y})^{2}={a+bi \over {\sqrt {a^{2}+b^{2}}}}$

звідки легко знаходимо:

$(11)\qquad n_{x}=\pm {a+m \over 2m},\qquad n_{y}={b \over {2mn_{x}}},\qquad m={\sqrt {a^{2}+b^{2}}}$

Комплексний квадрат градієнта використовується в проекті з відкритим кодом Outliner

Дискретні формули для обчислення градієнта

Маючи в розпорядженні значення функції тільки в дискретних точках пікселів, градієнт можна шукати за допомогою варіації методу скінченних різниць. Широко застосовуються оператор Собеля і оператор Робертса.

Слід зазначити, що оператори Собеля та Робертса діють на чорно-білому зображенні, або на одній із компонент кольору. Для обробки ними кольорової картинки, треба або попередньо трансформувати цю картинку в чорно-білу (що простіше), або скористатися формулами комплексного квадрата градієнта (що буде якіснішим).

Другою проблемою, особливо для оператора Робертса є шуми. Шуми на зображенні можуть бути як об'єктивним фактором, пов'язаним із ворсистістю краю об'єкта чи запиленістю, так і артефактом, пов'язаним з дискретизацією чи із втратами JPEG-кодування. Для зменшення шумів треба попередньо згладжувати зображення, як це робиться в першій стадії алгоритму Кенні по виділенню контурів.