Pochodne i krawędzie

20.04.2010 - Krzysztof Dryś
TrudnośćTrudnośćTrudnośćTrudność

W tym artykule zajmiemy się szukaniem krawędzi na obrazach. Najpierw dowiemy się, po co się to robi. Potem nauczymy się szukać krawędzi przy pomocy komputerów. W tym celu posłużymy się takimi pojęciami jak: kwantyle, maksima lokalne i pochodne. Okażą się one bowiem, zupełnie niespodziewanie, bardzo przydatne w tym zagadnieniu. To pozwoli nam tworzyć obrazki z ,,wyszukanymi'' już krawędziami takie, jak ten obok.

W artykule Proste przetwarzanie obrazów można przeczytać o paru podstawowych filtrach wykrywających krawędzie na obrazku. Tutaj postaramy się zrozumieć dokładniej jak one działają i jaka stoi i jaka stoi za nimi teoria.

Po co nam krawędzie?

No dobrze, ale tak właściwie dlaczego chcielibyśmy umieć wykrywać krawędzie? Pierwsza odpowiedź brzmi: dlatego, że to ciekawe! Wykrywanie krawędzi to zadanie z którym człowiek bardzo dobrze sobie radzi. Właściwie to rozpoznawanie kształtów jest jedną z pierwszych rzeczy, których uczy się dziecko. Nauczyliśmy już komputery mówić i liczyć - dlaczego nie mielibyśmy ich nauczyć czegoś, wydawałoby się dużo łatwiejszego?

Przypomnienie

Jak zawsze, gdy w przetwarzaniu czarno-białych obrazów, każdy z nich jest jest zadany jako macierz $ U $ liczb naturalnych. Wartość każdego piksela pamiętamy na 8 bitach. Największa liczba jaką umiemy zapisać na 8 bitach to 255. Oznacza to, że:

$ 0 \leq U[i,k] \leq 255 $

Jeżeli $ U[i,j] = 0 $, to piksel jest czarny. Natomiast jeżeli $ U[i,j] = 255 $, to piksel jest biały. Pośrednie wartości oznaczają różne odcienie szarości.

Zanim nauczymy się rozróżniać gruszki i jabłka musimy umieć powiedzieć: tu zaczyna się jeden obiekt, a tutaj drugi.

Rozpoznawanie kształtów

Żeby nauczyć się rozpoznawać różne kształty, trzeba najpierw umieć powiedzieć: tutaj jeden obiekt się zaczyna, a drugi kończy. Miejsce, gdzie jeden obiekt przechodzi w drugi, to właśnie krawędź. Dlatego jeżeli chciemy nauczyć komputery rozróżniać owoce, musielibyśmy najpierw go nauczyć rozpoznawania krawędzi. To oznacza, że jednym z zastosowań naszego problemu jest właśnie komputerowe rozpoznawanie kształtów. Oczywiście rozpoznawania krawędzi jest dopiero pierwszym krokiem, ale za to bardzo ważnym!

Definicja krawędzi

Pytanie o definicję krawędzi może wydawać się dosyć zabawne. Ale zanim zaczniemy rozwiązywać problem, musimy go dobrze sformułować Bo potem może okazać się, że rozwiązaliśmy coś zupełnie innego! Chcielibyśmy, żeby wykryte krawędzie miały następujące cechy:

  • Miały szerokość jednego piksela. Bo czy ktoś słyszał kiedyś o szerokiej prostej?
  • Były krzywymi zamkniętymi. Bo jeżeli krawędź oddziela gruszkę od tła, to musi oddzielać ją całą.
  • Były niewrażliwe na szumy na obrazkach. Czyli innymi słowy: żeby wykrywały te krawędzie, które nas interesują

Do dzieła!

Spróbujmy stworzyć nasz pierwszy program wykrywający krawędzie. Jak już powiedzieliśmy, krawędź to miejsce, gdzie coś się zmienia - gdzie jeden obiekt przechodzi w drugi. Spróbujmy bezpośrednio wykorzystać tę definicję.

Jeżeli obrazek przechowujmy w tablicy $ u[i,j] $ to prostą miarą zmienności obrazka jest $ u[i,j] - u[i+1,j] $. Jeżeli ta wartość jest bliska zera, to znaczy, że $ u $ nie zmienia się specjalnie. Jeżeli natomiast $ u[i,j] - u[i+1,j] $ jest odległe od zera (lub równoważnie: $ |u[i,j] - u[i+1,j]| $ jest duże), to znaczy, że obrazek istotnie się zmienia w punkcie $ (i,j) $. Spróbujmy przerobić tę intuicję na algorytm:

1
2
3
4
5
 u - obrazek wejściowy
 v - obrazek wyjściowy
 Dla i = 1..n
    Dla j = 1..m
        v[i,j] = |u[i,j] - u[i+1,j]|
alternative text Obrazek, którym będziemy się dzisiaj zajmować.
alternative text Efekt działania pierwszego algorytmu. Aby poprawić widoczność, obrazek został rozjaśniony.

Nieźle jak na pierwszy raz, prawda? Nasz algorytm znalazł większość krawędzi. Problem w tym, że nie wszystkie! Za to znalazł trochę niepotrzebnych rzeczy. Zdecydowanie nie spodziewaliśmy się znaleźć tyle krawędzi w górach. Poza tym wynikowy obrazek nie do końca na odpowiada z jeszcze jednego powodu. Chcielibyśmy, żeby w macierzy $ v $ były tylko dwie wartości: 0 i 255. Jedna mówiłaby: tutaj jest krawędź, a druga tutaj nie ma krawędzi. Natomiast nasz obrazek zawiera wiele wartości pośrednich, które nie mają ładnej interpretacji.

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com