Rozpoznawanie znaków – współczynnik korelacji #1

Ostatnie parę dni spędziłem na przygotowywaniu obrazków dużych liter oraz cyfr, które posłużą jako wzorzec przy rozpoznawaniu znaków wykrytych przy pomocy histogramu. Nie było to nic wartego dłuższego wspominania, ale dzięki temu mogę zacząć pisanie serca systemu.

[latexpage]

Na pierwszy ogień pójdzie rozpoznawanie znaków wykorzystujące współczynnik korelacji.  Według cioci Wikipedii współczynnik ten określa w jakim stopniu dwie zmienne są współzależne. Z kolei książka Włodzimierza Kwiatkowskiego pt. „Metody automatycznego rozpoznawania wzorców” sugeruje analogię do odległości między obiektem badanym i wzorcem do którego jest porównywany.

Mówiąc prostszym językiem – im wartość współczynnika jest bliżej do liczby 1, tym obiekt jest bardziej podobny do wzorca. Z kolei im bliżej -1 tym w większym stopniu obiekty są swoimi przeciwieństwami. Wartość 0 oznacza, że są różne.

 

Aby wyznaczyć współczynnik korelacji dla zbinaryzowanego obrazka zawierającego znak oraz dla wzorca należy przekształcić obraz z postaci macierzy o wymiarach X na Y na wektor o długości X*Y. Uzyskane wektory powinny mieć tę samą wartość, więc przed przekształceniem wskazane jest przeskalowanie rozpoznawanego znaku do wymiarów obrazu odniesienia.

Gdy uzyskamy odpowiednie wektory powinniśmy poddać je normalizacji, czyli podzielić ich współrzędne przez długość wektora. Obliczenie długości sprowadza się do obliczenia sumy kwadratów każdej współrzędnej, a następnie wyciągnięcie pierwiastka kwadratowego z tej sumy.

Wzór:

\begin{equation}

\biggl{\vec{v}} = \sqrt{{v_1}^2 + {v_2}^2 + … +{v_n}^2}

\end{equation}

Przykład:

\begin{equation}
\vec{v} = [1, 3, 5, 0, 3, 2]
\end{equation}

\begin{equation}
||\vec{v}|| = \sqrt{1^2 +  3^2 + 5^2 + 0^2 +  3^2 + 2^2]}
\end{equation}

\begin{equation}
||\vec{v}|| = 6,9282
\end{equation}

Normalizacja wektora spowoduje, że będą miały one tę samą długość, czyli 1. Pomoże nam to w dalszych obliczeniach.
Nadeszła pora na grande finale – obliczenie współczynnika korelacji. Wyznaczymy go przy pomocy zwykłego mnożenia i dodawania. Wzór matematyczny na wyznaczenie wartości współczynnika to:

\begin{equation}

\rho = \frac{\vec{x}\circ\vec{y}}{||\vec{x}||\cdot ||\vec{y}||}

\end{equation}

Słownie – jest to stosunek iloczynu skalarnego wektora znaku i wektora wzorca do iloczynu długości tych wektorów.

Dzięki temu, że znormalizowaliśmy wektory, w mianowniku będziemy mieli mnożenie 1 x 1, co można pominąć. Tak więc obliczenia sprowadzają się do sumy mnożenia współrzędnych wektorów.

\begin{equation}

\vec{x}\circ\vec{y} = x_{1}y_{1} + x_{2}y_{2} + … +  x_{n}y_{n}

\end{equation}

Współczynnik korelacji dla wektorów x = [1,0,0,1,2] oraz y = [0,0,2,1,1] wynosi

\begin{equation}

||\vec{x}|| = 2,4495

\end{equation}

\begin{equation}

||\vec{y}|| = 2,4495

\end{equation}

Wektory po normalizacji:

\begin{equation}

\hat{\vec{x}} = [0,4082; 0; 0; 0,4082; 0,8165]

\end{equation}

\begin{equation}

\hat{\vec{y}} = [0; 0; 0,8165; 0,4082; 0,4082]

\end{equation}

Obliczenie współczynnika korelacji:

\begin{equation}

\vec{x}\circ\vec{y} = 0,4082\cdot 0 + 0 \cdot 0 + 0\cdot 0,8165 + 0,4082\cdot 0,4082 + 0,8165\cdot 0,4082

\end{equation}

\begin{equation}

\vec{x}\circ\vec{y} = 0,1666 + 0,3333

\end{equation}

\begin{equation}

\vec{x}\circ\vec{y} = 0,4999

\end{equation}

 

Zdaję sobie sprawę, że dzisiaj było dość dużo matematyki, ale mam nadzieję, że została podana w przyswajalnej wersji.

 

EDIT – brakująca literatura:

  • Metody automatycznego rozpoznawania wzorców, W. Kwiatkowski, Warszawa 2007
  • https://pl.wikipedia.org/wiki/Wsp%C3%B3%C5%82czynnik_korelacji

 

2 myśli w temacie “Rozpoznawanie znaków – współczynnik korelacji #1”

  1. Fajny wpis.Będę obserwował dalej rozwój tego projektu. Mam jednak kilka uwag
    1. Jeżeli obraz binaryzujesz to masz wartości {1, 0} a w przykładzie wektor ma wartość 2
    2. Zastanawiam się czy jest sens normalizować najpierw wektory. O ile matematycznie jest to bez znaczenia, to numerycznie zwiększamy błąd związany z obliczeniami zmiennoprzecinkowymi.
    3. Zastanawiam się czy liczenie korelacji ma sens i czy będzie wnosiła dużo więcej niż zwykłe liczenie Odległość Hamminga (https://pl.wikipedia.org/wiki/Odleg%C5%82o%C5%9B%C4%87_Hamminga), i będzie tylko porównywaniem ile pixeli różni się od wzorca. A przez to algorytm nie będzie odporny na obroty, czy bardziej prozaiczne przesunięcia i skalowania.

    Jak by nie wychodziło z korelacją polecam poczytać o transformacie Hougha (a dokładnie odmianie GHT)

    1. Transformata hougha nie tylko jest stosowana do wykrywania linii prostych.
      ivrl.epfl.ch/research/text_detection_recognition

      Aczkolwiek jeżeli zakładasz że obraz będzie bez obrotów to korelacja może wyjść. Chętnie zobaczę jak wyjdzie.

Skomentuj Anonim Anuluj pisanie odpowiedzi

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *