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

 

4 myśli na temat “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. Dziękuję za opinię i merytoryczny komentarz.
      Ad 1. Jak zauważyłeś to przykład. Chciałem pokazać ogólną ideę, w jaki sposób się wykonywać obliczenia. Bez powiązania z konkretnym przypadkiem.
      Ad 2. Dokładność obliczeń w tym wypadku faktycznie powodować problemy przy nieznaczących różnicach w wartości współczynnika w odniesieniu do poszczególnych wzorców.
      Ad 3. O odległości Hamminga nie czytałem, więc dziękuję za sugestię. Powinna być ciekawą opcją do porównania pod kątem dokładności.

      O transformacji Hougha rozmawiałem z promotorem i sugerował jej użycie do wykrywania tabel, ewentualnego obrotu obrazu. Jednak na ten moment nie planuję zajmować się korekcją zniekształceń obrazu.

      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.

        1. Widziałem jeszcze parę innych badań na ten temat np. dspace.ucalgary.ca/bitstream/1880/46551/2/1993-517-22.pdf

          Jeśli wystarczy mi czasu to możliwe, że wykorzystam tę metodę. Korelacja ma tę zaletę, że jest prosta i szybka w implementacji, więc na początek jest wystarczająco dobrą metodą.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *