K-means clustering

  • O co jde
O co jde

Table of Content

Vstup

  • N d-dimenzionálních vektorů
  • Počet clusterů k

Výstup

  • d-dimenzionální středy clusterů
  • Minimalizované vzdáleností bodů od středů vektorů
  • Clustery vytvoří voronoivy regiony

Minimalizované vzdáleností bodů od středů vektorů

  • Sum of squares
  • MNČ

Použití

  • Geografická data
  • Statistická n-rozměrná data
  • Color quantization

Geografická data

  • 2D vektorů = bodů v ploše
  • 3D vektorů

2D vektorů = bodů v ploše

  • Body v ploše
  • Př. pokud pro stromy se známou polohou chceme vybudovat 3 studny a minimalizovat vzdálenosti pro zalévání
Body v ploše

3D vektorů

  • bodů v prostoru x,y,z
  • barevných pixelů RGB, LAB, HSV

Color quantization

  • Pokud chceme rozdělit pixely na "tmavé" a "světlé" (k=2)
  • Pokud chceme rozdělit pixely na "bílé", "černé" a "zelené" (k=3)
  • Redukce počtu barev

Pokud chceme rozdělit pixely na "tmavé" a "světlé" (k=2)

  • Vstupní obrázky
  • Použití thresholdingu VALUE=80-255
  • Použití thresholdingu VALUE=220-255
  • Použití k-means
Vstupní obrázky
  • Dark
  • Light
DarkLight
Použití thresholdingu VALUE=80-255
  • Dark
  • Light
DarkLight
Použití thresholdingu VALUE=220-255
  • Dark
  • Light
DarkLight
Použití k-means
  • Dark
  • Light
DarkLight

Pokud chceme rozdělit pixely na "bílé", "černé" a "zelené" (k=3)

  • Vstup:
  • Výstup:
Vstup:Výstup:

Redukce počtu barev

Vstup
  • K-means clustering_5498324280790384501.png
K-means clustering_5498324280790384501.png
Výstup
  • K-means clustering_1607084507421311282.png
K-means clustering_1607084507421311282.png

Ukázka v Javě - OpenCV

  • Dependencies
  • Spuštění k-means algoritmu
  • Zjištění středů clusterů

Dependencies

  • compile files("/usr/share/OpenCV/java/opencv-320.jar")
  • System.load("/usr/share/OpenCV/java/libopencv_java320.so");

Spuštění k-means algoritmu

  • public List<ClusterInfo> clusters(Mat sourceImg, int k) {

    Mat samples32f = new Mat();
    Mat allPixelsInOneRow = sourceImg.reshape(1, sourceImg.cols() * sourceImg.rows());

    allPixelsInOneRow.convertTo(samples32f, CvType.CV_32F, 1.0 / 255.0);
    allPixelsInOneRow.release();

    TermCriteria criteria = new TermCriteria(TermCriteria.COUNT, 100, 1);
    Mat labels = new Mat(sourceImg.width()*sourceImg.height(), 1, CvType.CV_32SC1);
    labels.setTo(new Scalar(0));
    Mat centers = new Mat();
    /*kmeans (Mat data, int K, Mat bestLabels, TermCriteria criteria, int attempts, int flags, Mat centers) {*/
    Core.kmeans(samples32f, k, labels, criteria, 1, Core.KMEANS_PP_CENTERS + Core.KMEANS_USE_INITIAL_LABELS, centers); }

Zjištění středů clusterů

  • private List<ClusterInfo> createClustersBinaryImages(Mat sourceImg, Mat pixelLabels, Mat clusterCenters, int k) {
    clusterCenters.convertTo(clusterCenters, CvType.CV_8UC1, 255.0);
    clusterCenters.reshape(k);

    int clusterCentersSize = clusterCenters.rows();
    for (int i = 0; i < clusterCentersSize; i++) {
    double[] centerL = clusterCenters.get(i, 0);
    double[] centerA = clusterCenters.get(i, 1);
    double[] centerB = clusterCenters.get(i, 2);

    double[] centerLab = {centerL[0], centerA[0], centerB[0]}; ...
    }

The End

Thank You!

Yours Respectfully

Powered by Mindslide for Freeplane, using Reveal.js