---
# System prepended metadata

title: Kognitive Systeme

---

<style>
/* bessere Erkennbarkeit der kleinen Überschriften */
.markdown-body h5{font-size: 1.05em;}
.markdown-body h4{font-size: 1.15em;}
.markdown-body h3{font-size: 1.8em;}
.markdown-body h2{font-size: 2.4em;}
.markdown-body h1{font-size: 3em;}
</style>

# Kognitive Systeme
## Signalverarbeitung
* Dirac-Distribution
    * Definition:
$$
\delta(f)=\lim_{\epsilon\rightarrow 0}\int_{-\infty}^\infty \delta_{\epsilon}(x)f(x)dx=f(0)
$$
    * Eigenschaften:
        * Symmetrie: $$\delta_\epsilon(-x) = \delta_\epsilon(x)$$
        * Grenzwertbetrachtung:$$\lim_{\epsilon\rightarrow0}\delta_\epsilon(x)=
        \begin{cases}
        0 & x\neq0\\
        \infty & x=0
        \end{cases}$$
        * Flächenerhaltung:
        $$\int_{-\infty}^{\infty}\delta_\epsilon(x)dx=1$$
        * Siebeigenschaft
        $$\int_{-\infty}^\infty\delta(x-\tau)g(x)dx=g(\tau)$$
* Faltung
$$
\begin{array}{ll}
    (f\ast g)(t)=\int_{-\infty}^\infty f(t-\tau)g(\tau)\,d\tau &\text{(kontinuierlich)} \\
    (f\ast g)[i] = \sum_{j\;=\;-\infty}^\infty f[i-j]g[j] & \text{(diskret)}
\end{array}
$$
* Abtastung (Sampling)
    * Idealisiert: Multiplikation eines Signals mit einem Dirac-Kamm
* Abtasttheorem (Nyquist-Shannon)
    * Kontinuierliches, bandbegrenztes Signal mit Grenzfrequenz $F$ muss mit einer Frequenz $> 2*F$ abgetastet werden
    * Bandbegrenzung: Durch Tiefpassfilter
* Quantisierung
    * $y$-Achse wird in n gleichgroße Intervalle unterteilt (üblich: $n=2^b$)
    * Diskretes Signal $f[i]$ wird quantisiert zu $q[i]$ (über Intervallzugehörigkeit)
    * Anzahl der Quantisierungsstufen bestimmt Auflösung
    * Feinere Auflösung $\rightarrow$ bessere Qualität, speicherintensiver
    * Quantisierungsfehler (gleichv. Signal): $$e[i]=(f_\max-f_\min)/(2n)$$
* Aliasing
* Fourierreihe
    * Voraussetzung: Periodische Funktion $f(t)$ (mit Periode $T$)
    * Lässt sich durch Überlagerungen von trigonometrischen Funktionen annähern $$f(t)=\frac{a_0}{2}+\Sigma_{n=1}^{\infty}a_n \cos(\omega nt)+b_n \sin(\omega nt),\;\;\omega=\frac{2\pi}{T}$$
    * Darstellung im Komplexen: $$\begin{array}{lr}f(t)=\Sigma_{n=-\infty}^{n=+\infty}\;c_n\cdot e^{in\omega t}, & c_n=\begin{cases}\frac{1}{2}a_0 & n=0\\\frac{1}{2}(a_n-ib_n)&n>0\\\frac{1}{2}(a_{-n}+ib_{-n})&n<0\end{cases}\end{array}$$
* Zeitkontinuierliche Fouriertransformation
    * Erweiterung der Fourierreihe auf nicht-periodische Funktionen $$F(\omega)=\int_{-\infty}^{+\infty}f(t)e^{-i\omega t}dt,\;\; \omega = 2\pi f $$
    * $\omega$ ist die Kreisfrequenz [^kreisfrequenz]
    * Inverse Transformation: $$f(t)=\frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega) e^{i\omega t}d\omega$$
[^kreisfrequenz]: https://de.wikipedia.org/wiki/Kreisfrequenz
* Zeitdiskrete Fouriertransformation (DTFT)
* Diskrete Fouriertransformation (DFT)
* Schnelle Fouriertransformation (FFT)
* Kurzzeitspektralanalyse
* Fensterung
* (Auto-/Kreuz-)korrelation

## Klassifikation
* Template Matching
* Pattern Recognition
    * Supervised / Unsupervised
    * Parametric / Non-Parametric
    * Linear / Non-Linear
* Bayes
* K-Nearest Neighbor
* Perzeptronen
    * Perzeptronen sind Algorithmen für das überwachte Lernen (supervised learning) binärer Klassifikatoren [^perzeptronen]
    * Binäre Klassifikatoren sind Funktionen, die entscheiden können, ob eine Eingabe, die durch einen Zahlenvektor repräsentiert wird, zu einer spezifizierten Klasse gehört
[^perzeptronen]: https://en.wikipedia.org/wiki/Perceptron
* Multilayer Perceptrons
* Gaussian Classifier
* Parzen Windows
* Principal Component Analysis (PCA)
* Risk / Minimum Error Rate Classification
* Linear Discriminant Functions
* Fisher-Linear Discriminant
* Mixture Gaussians

## Machine Learning
* Hierarchical Clustering
    * Die Hierarchische Clusteranalyse ist eine Methode, deren Ziel es ist, eine Hierarchie aus Clustern zu bauen. Die Strategien für diese Methode lassen sich in zwei Typen aufteilen: divisiv und agglomerativ.
* Neural Networks
* Deep Neural Net Hybrids (Between Deep Neural Nets and Hidden Markov Models)
* Neural Models
    * Back-Propagation
    * "Deep" Neural Networks
    * Boltzman Machines
    * Decision Tree Classifiers
    * Feature Map Classifiers
    * Learning Vector Quantizer
    * High Order Networks
    * Radial Basis Functions
    * Modified Nearest Neighbor
    * ART
    * TPNNs / Concolutional Nets

## Spracherkennung
* Mahalanobis-Distanz
* Markov-Ketten
### Hidden-Markov-Modelle
* **Markov-Kette 1. Ordnung**
#### 3 Probleme


| Name        | Beschreibung                                                                    | Algorithmus                       |
| ----------- | ------------------------------------------------------------------------------- |:--------------------------------- |
| Evaluation  | gegeben beobachtete Sequenz und Modell, finde Wahrscheinlichkeit                | Forward- oder Viterbi-Algorithmus |
| Dekodierung | gegeben beobachtete Sequenz und Modell, finde wahrscheinlichste Zustandssequenz | Viterbi-Algorithmus               |
| Training    | ändere Modellparameter um Wkt beobachteter Sequenzen zu optimieren              | Forward-Backward-Algorithmus      |

## Bildverarbeitung
### Geometrische 3D-Transformationen
* Rotationsmatritzen:
  $$ R_X(\theta) = 
     \begin{bmatrix}
     1    &    0    &    0    \\
     0    &    \cos(\theta)    &    -\sin(\theta)    \\
     0    &    \sin(\theta)    &    \cos(\theta)    \\
     \end{bmatrix}
     \\
     R_Y(\theta) = 
     \begin{bmatrix}
     \cos(\theta)    &    0    &    \sin(\theta)    \\
     0               &    1    &    0               \\
     -\sin(\theta)   &    0    &    \cos(\theta)    \\
     \end{bmatrix}
     \\
     R_Z(\theta) = 
     \begin{bmatrix}
     \cos(\theta)    &    -\sin(\theta)     &    0    \\
     \sin(\theta)    &     \cos(\theta)     &    0    \\
     0               &     0                &    1    \\
     \end{bmatrix}
  $$
  * Invertierung: $R^{-1}=R^T$
  * Drehung um mitgedrehte Achsen: $R_{X'Y'Z'}(\alpha, \beta, \gamma) = R_X(\alpha) \cdot R_Y(\beta) \cdot R_Z(\gamma)$
  * Drehung um raumfeste Achsen: $R_{ZYX}(\alpha, \beta, \gamma) = R_X(\alpha) \cdot R_Y(\beta) \cdot R_Z(\gamma)$
* Homogener Vektor:
  $$\begin{bmatrix}x\\y\\z\\1\end{bmatrix}$$
* Homogene Transformationsmatrix mit Rotation $R$ und Translation $t$:
    $$\left[\begin{array}{c@c@c|c}&&&\\&R&&t\\&&&\\\hline0&0&0&1\\\end{array}\right]$$
* Homogene Transformationematritzen
* Quaternionen
  * wie komplexe Zahlen, aber mit $i,j,k$
  $$
      i^2 = j^2 = k^2 = -1 \\
      ij =  -ji = k \\
      jk = -kj = i \\
      ki = -ik = j
  $$
  * Multiplikationsregel:
  $$
      qr = (q_{\operatorname{real}} \cdot r_{\operatorname{real}} - q_{\operatorname{imag}} \cdot r_{\operatorname{imag}}, q_{\operatorname{imag}} \times r_{\operatorname{imag}} + q_{\operatorname{real}} \cdot r_{\operatorname{imag}} + r_{\operatorname{real}} \cdot q_{\operatorname{imag}})
  $$
   * Dabei ist das Kreuzprodukt so definiert \[[Wikipedia](https://de.wikipedia.org/wiki/Kreuzprodukt)\]:
   $$
   \begin{bmatrix}x_1\\y_1\\z_1\end{bmatrix}
   \times
   \begin{bmatrix}x_2\\y_2\\z_2\end{bmatrix}
   :=
   \begin{bmatrix}
       y_1 z_2-z_1 y_2 \\
       z_1 x_2 - x_1 z_2 \\
       x_1 y_2 - y_1 x_2
   \end{bmatrix}
   $$
### Bildgenerierung
* Lochkamera-Modell
    * Parameter:
        * $f$: Brennweite
    * Ursprung des Koordinatensystems liegt im Loch
    * Projektion eines Szenenpunkts $(X,Y,Z)$ auf einen Bildpunkt $(u,v)$:
        $$
        \begin{bmatrix}
          u \\ v \\ w
        \end{bmatrix} = -\frac{f}{Z}
        \begin{bmatrix}
          X \\ Y \\ Z
        \end{bmatrix}
        $$
    * Skizze:
        ![](https://i.imgur.com/4CLMI4N.png)
* Erweitertes Kameramodell
    * Parameter:
        * $f_x$: Brennweite x-Richtung in Pixeln
        * $f_y$: Brennweite y-Richtung in Pixeln
    * Projektion eines Szenenpunktes $(X,Y,Z)$ im Kamerakoordinatensystem auf einen Bildpunkt $(u,v)$:
        $$
        \begin{bmatrix}
          u w \\ v w \\ w
        \end{bmatrix}=
        K \cdot
            \begin{bmatrix}
              X \\ Y \\ Z
            \end{bmatrix},
        K = 
        \begin{bmatrix}
        f_x &  0  & c_x \\
        0   & f_y & c_y \\
        0   &  0  &  1  \\
        \end{bmatrix}
        $$
        K ist dabei die intrinsische Kallibiriermatrix.
    * Projektion eines Szenenpunktes $(X,Y,Z)$ im Weltkoordinatensystem auf einen Bildpunkt $(u,v)$:
      $$
        \begin{bmatrix}
          u w \\ v w \\ w
        \end{bmatrix}=
        P \cdot
            \begin{bmatrix}
              X \\ Y \\ Z \\ 1
            \end{bmatrix},
        P = 
        \left[
        \begin{array}{c@c@c|r}
          \\
          & K R & & K t
          \\
          \\
        \end{array}
        \right]
        $$
    * Skizze:
      ![](https://i.imgur.com/HUiTYH8.png)
### Bildrepräsentation
  * Monochrombild:
    $Img:[0..n-1] \times [0..m-1] \to [0..q]$ 
  * Farbbild (RGB, also additiv):
    $Img:[0..n-1] \times [0..m-1] \to [0..R] \times [0..G] \times [0..B]$
  * CMY: wie RGB, aber subtraktiv
  * HSI-Farbraum:
      * trennt Helligkeit von Farbwert
        :point_right: unempfindlich gegen Belichtungsänderungen 
      * :::spoiler Umrechnung RGB zu HSI
        $$
            \begin{align}
                c &= \arccos{\frac{2R-G-B}{2 \sqrt{(R-G)^2+(R-B)(G-B)}}} \\ \\
                H &= \begin{cases}
                        c & B<G \\
                        360° - c & B \geq G
                     \end{cases} \\ \\
                 I &= \frac{R+G+B}{3} \\ \\
                 S &= 1 - \frac{\min(R,G,B)}{I}
            \end{align}
        $$
        :::
  * Umrechnung RGB zu monochrom:
    $g = 0.299\cdot R + 0.587\cdot G + 0.114 \cdot B$

### Bildvorverarbeitung
| Grundoperator      | Ergebnis abhängig von         | Anwendung                                          |
| ------------------ | ----------------------------- |:-------------------------------------------------- |
| Punktoperatoren    | nur vom einzelnen Pixel       | Helligkeit / Kontrast / Binarisierung / Gewichtung |
| Lokale Operatoren  | nur von Umgebung eines Pixels | Glättung / Kantenerkennung                         |
| Globale Operatoren | vom gesamten Bild             |                                                    |

##### Homogene Punktoperatoren:
* unabhängig von Position (=Koordinaten) des Pixels:
  $Img'(u,v) = f(Img(u,v))$
* Implementierung mit Lookup-Table / in Hardware
* Unterscheidung:
  * **Affine Punktoperatoren**:
      * spezielle homogene Punktoperatoren mit $f$ der Form $f(x) = a \cdot x + b$
      * zur Helligkeitsänderung / Kontraständerung / Invertierung
  * **Nicht-affine Punktoperatoren**
      * zum Ausgleich von Sensor-Nichtlinearitäten, Gewichtung, Binarisierung
##### Histogramm und Quantile:
* **Grauwerthistogramm**: Wie oft kommt welcher Grauwert vor?
  $H(x) = |\{(u,v):I(u,v) = x\}|$
* **Akkumuliertes Histogramm**: 
  $H_a(x) = \sum_{k=0}^{x}{H(k)}$
* **Quantilsfunktion**:
  $H_q(p) = \inf{\{x \in \{0,\ldots,q\} : H_a(x) \geq p \cdot H_a(q)\}}$
##### Automatische Kontrastanpassung
* **Spreizung**:
    affine Punktoperation mit $a=\frac{q}{\max - \min}, b=-a \cdot \min$
    (in der Praxis nicht robust bei einzelnen Extrempixeln)
* **Histogrammdehnung**:
  affine Punktoperation mit $a=\frac{q}{H_q(p_{max})-H_q(p_{min})}, b=-a \cdot \min$
* **Histogrammausgleich**:
  * homogene (nicht-affine) Punktoperation mit
    $f(x) := H_n(x):= \operatorname{round}(\frac{q}{H_a(q)} \cdot H_a(x))$
  * erhöht Kontrast in stark vertretenen Grauwertbereichen
  * kann manchmal Kontrast auch vermindern


##### Bildglättung
###### Mit lokalen Operatoren (Glättungsfiltern)
| Name                     | Maske                                                                                | Idee                                                                                                   |
| ------------------------ | ------------------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------ |
| Rechteckfilter           | $\frac{1}{9}\cdot\begin{bmatrix}1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}$   | Mittelwert der Nachbarn                                                                                |
| $3 \times 3$-Gaussfilter <br>($\sigma = 0.85$) | $\frac{1}{16}\cdot\begin{bmatrix} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 1 \end{bmatrix}$ | Gewichtung nach Distanz $$f(x,y) = \frac{1}{2 \pi \sigma ^ 2} e ^ {- \frac{x^2 + y^2}{2 \sigma ^ 2}}$$ |

##### Kantendetektion
###### Mit lokalen Operatoren (Kantendetektionsfiltern)
| Name    |                                             Maske 1                                              |                                            Maske 2                                             | Idee, Anwendung                                                                                                                                                      |
| ------- |:------------------------------------------------------------------------------------------------:|:----------------------------------------------------------------------------------------------:| -------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| Prewitt |       $P_x= \begin{bmatrix}   -1 & 0 & 1 \\   -1 & 0 & 1 \\   -1 & 0 & 1   \end{bmatrix}$        |   $P_y=   \begin{bmatrix}    -1 & -1 & -1 \\    0 & 0 & 0 \\    1 & 1 & 1    \end{bmatrix}$    | **Idee:** Gradienten ausrechnen<br>**Anwendung:**<br>1. Prewitt-Operator $M \approx \sqrt{P_x(I)^2+P_y(I)^2}$<br> 2. Schwellwertfilterung                            |
| Sobel   |    $S_x=    \begin{bmatrix}    -1 & 0 & 1 \\    -2 & 0 & 2 \\    -1 & 0 & 1    \end{bmatrix}$    |   $S_y=    \begin{bmatrix}    -1 & -2 & -1 \\    0 & 0 & 0 \\    1 & 2 & 1    \end{bmatrix}$   | **Idee:** wie Prewitt, aber Gauß-Gewichtung der Differenzen <br>**Anwendung:**<br>1. Sobel-Operator $M \approx \sqrt{S_x(I)^2+S_y(I)^2}$<br> 2. Schwellwertfilterung |
| Roberts |   $R_x =         \begin{bmatrix}            -1 & 0 \\             0 & 1         \end{bmatrix}$   | $R_y =       \begin{bmatrix}             0 & -1 \\             1 &  0 \\        \end{bmatrix}$ | **Idee:** Diagonale Kantendetektion<br>**Anwendung:** $R(I)(x,y) = \|R_x(I)(x,y) + R_y(I)(x,y)\|$                                                                    |
| Laplace | $LP =    \begin{bmatrix}     0 &  1 &  0 \\     1 & -4 &  1 \\     0 &  1 &  0    \end{bmatrix}$ |                                             *N/A*                                              | **Idee:** Kanten sind 0-Durchgänge der 2. Ableitung.<br>**Anwendung:**<br>wegen Rauschempfindlichkeit Laplace of Gaussian (erst Gauss, dann Laplace)                                 |

###### Mit Canny (="optimaler" Mehrschrittalgorithmus)
1. Rauschunterdrückung (Gauss)
2. Gradientenberechnung mit Prewitt oder Sobel
   $+$ Berechnung der Richtung und Einteilung in Quadranten
3. Non-Maximum-Suppression
   (Gradient muss lokales Maximum sein in Quadrantenrichtung)
5. Hysterese-Schwellwertverfahren
    * 2 Schwellwerte (high/low)
        1. Akzeptiere alle mit Gradientbetrag > high
        2. und rekursiv alle 8 benachbarten falls deren Gradientenbetrag > low
##### Fourier-Transformation in der Bildverarbeitung
- [ ] :warning: fehlt noch (Foliensatz Bildverarbeitung II, Folien 83-89)
### Segmentierung
* Schwellwertfilterung
    * manuell
    * Multilevel Otsu
* Nach Farbe
    * histogrammbasiert
    * Mahalanobis
    * Klassifizierung mit neuronalen Netzen
    * Intervallschranken im HSV-Farbraum
* Morphologische Operationen
    | Name       | Was                                        | Effekt                                                       |
    | ---------- | ------------------------------------------ | ------------------------------------------------------------ |
    | Erosion    | 1 wenn Maske Teilmenge von Bild                  | Objekte werden verkleinert, Dünnes verschwindet              |
    | Dilatation | 1 wenn Schnittmenge von Maske und Bild nichtleer | Objekte werden verbunden, vergrößert, Hohlräume geschlossen. |
    * Opening: Erosion, dann Dilatation
    * Closing: Dilatation, dann Erosion
* Segmentierung durch Bewegung
* Region Growing
* Kanten finden
    * Iterative Endpoint Fit
    * Hough-Transformation
* Punktmerkmale
    * Harris Corner Detector
    * Sum of Squared Differences
    * Sum of Absolute Differences
    * Kreuzkorrleation
    * Zero Mean Normalized Cross-Correlation
* HMC
* Gesichtserkennung
## Wissen und Planung
- [ ] To be Done
* Einführung
    * Wissensdatenbanken
* Logik
* Aussagenlogik
* Aussagenlogische Deduktion
    * Resolution
    * Horn-Klauseln
    * DPLL
* Prädikatenlogik
* Planungssprachen
    * STRIPS
    * ADL
* Planungsstrategien
    * Suche im Zustandsraum
        * A*-Algorithmus
    * Partial Order Planning
    * Planungsgraphen
        * Weltmodelle
## Robotik
- [ ] To be Done
* Umgebungskarten
    * Unterscheidung in Freiraum (gesamter Raum ohne Hindernisse) und Hindernisraum
    * Bewegung nur im Freiraum möglich
    * Konfigurationsräume: Räume, deren Dimensionen die für die Planung relevanten Parameter sind
        * Können Planung unterstützen (z.B. Hindernisse vergrößern) 
* Bahnplanung
    * Findet im Freiraum statt
    * Gegeben: Karte des Raumes, in dem geplant werden soll
    * Ansatz: Wegenetz im Raum anlegen, als Graph repräsentieren, Wegsuche im Graphen
        * Polygonzerlegung
            * Sehr effizient für 2D-Karten
            * Raum in Polygone zerlegen
                * Von jeder Hindernisecke aus eine Trennlinie nach oben und unten bis zur nächsten Hinderniskante ziehen
                * Polygone entweder komplett frei oder komplett unpassierbar
                * Wegenetz durch die Freiraumpolygone anlegen
        * Quadtrees
        * Voronoi-Diagramme
        * Sichtgraphen
    * Alternativer Ansatz: Potentialfeldmethode
* Sichtgraphen
* Voronoi-Diagramme
* Potentialfeld-Methode
* Arbeitsräume
* Kinematik, Dynamik, Hardware, ...
* Kinematische Kette
    * Basiswechsel