1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
package de.se.rwth;


import edu.vu.isis.regtrack.common.Matrix;

public class Main {

  public static void main(String[] args) {
    long start = 0;
    try {
      Matrix[] imges1 = generateData();
      Matrix[] imges2 = generateData();
      Matrix[] imges3 = generateData();
      Matrix[] imges4 = generateData();
      start = System.currentTimeMillis();
      Thread t1 = new Thread() {
        public void run() {
          spectralCluster(imges1);
        }
      };
      Thread t2 = new Thread() {
        public void run() {
          spectralCluster(imges2);
        }
      };
      Thread t3 = new Thread() {
        public void run() {
          spectralCluster(imges3);
        }
      };
      Thread t4 = new Thread() {
        public void run() {
          spectralCluster(imges4);
        }
      };
      t1.start();
      t2.start();
      t3.start();
      t4.start();

      t1.join();
      t2.join();
      t3.join();
      t4.join();
    } catch (Exception ex) {
      ex.printStackTrace();
    }
    long duration = System.currentTimeMillis() - start;
    System.out.println("execution took "+duration +" ms");
  }

  public static void spectralCluster(Matrix[] imges) {

    //tic;
    //calculate the similarity / similarity matrix
    Matrix similarity = calculateAffinity(imges[0], imges[1], imges[2]);

    //compute the degree matrix
    Matrix degree = new Matrix(2500, 2500);
    for (int i = 0; i < similarity.numRows(); ++i) {
      double sumVal = 0;
      for (int j = 0; j < similarity.numCols(); ++j) {
        sumVal += similarity.valueAt(i, j);
      }
      degree.setValueAt(i, i, sumVal);
    }

    // compute the normalized laplacian
    Matrix nLaplacian = degree.
		matrixInvert().
		matrixSqrt().
		matrixMultiply(similarity).
		matrixMultiply(degree.matrixInvert().matrixSqrt());

    //perform the eigen value decomposition
    //[eigVectors, eigValues] =eig(nLaplacian);
    Matrix eigVectors = new Matrix(2500, 2500);
    Matrix eigValues = new Matrix(2500, 2500);
    nLaplacian.getEigens(eigValues, eigVectors);

    //select k largest eigen vectors
    int k = 4;
    int counter = 0;
    Matrix eigenvectors = new Matrix(2500, k);
    for (int i = (eigVectors.numCols() - (k - 1)) - 1; i < eigVectors.numRows(); i++) {
      for (int j = 0; j < 2500; j++) {
        eigenvectors.setValueAt(j, counter, eigVectors.valueAt(j, i));
      }
      counter = counter + 1;
    }


    //construct the normalized matrix U from the obtained eigen vectors
    Matrix U = new Matrix(2500, 4);
    for (int i = 0; i < eigenvectors.numRows(); i++) {
      double sumVal = 0;
      for (int j = 0; j < eigenvectors.numCols(); j++) {
        sumVal = Math.pow(eigenvectors.valueAt(i, j), 2);
      }
      double n = Math.sqrt(sumVal);
      for (int j = 0; j < eigenvectors.numCols(); j++) {
        U.setValueAt(i, j, eigenvectors.valueAt(i, j) / n);
      }
    }
    //perform kmeans clustering on the matrix U
    //[IDX, C] =kmeans(real(U), k);
    //toc;
  }


  public static Matrix calculateAffinity(Matrix img1, Matrix img2, Matrix img3) {
    Matrix similarity = new Matrix(2500, 2500);
    int counter2 = 0;
    for (int j = 0; j < img1.numCols(); ++j) {
      for (int i = 0; i < img1.numCols(); ++i) {
        int counter1 = 0;
        for (int j2 = 0; j2 < img1.numCols(); ++j2) {
          for (int i2 = 0; i2 < img1.numCols(); ++i2) {
            double dist =
                Math.sqrt((img1.valueAt(i, j) - img1.valueAt(i2, j2)) * 
				    (img1.valueAt(i, j) - img1.valueAt(i2, j2)) +
                    (img2.valueAt(i, j) - img2.valueAt(i2, j2)) * 
					(img2.valueAt(i, j) - img2.valueAt(i2, j2)) +
                    (img3.valueAt(i, j) - img3.valueAt(i2, j2)) * 
					(img3.valueAt(i, j) - img3.valueAt(i2, j2)));
            similarity.setValueAt(counter1, counter2, Math.exp(-dist / (2)));
            counter1 = counter1 + 1;
          }
        }
        counter2 = counter2 + 1;
      }
    }
    return similarity;
  }


  public static Matrix[] generateData() {
    //D = im2double(imread('lena.png'));
    Matrix img1 = generateMatrix(50, 50);
    Matrix img2 = generateMatrix(50, 50);
    Matrix img3 = generateMatrix(50, 50);

    return new Matrix[]{
        img1, img2, img3
    };
  }

  public static Matrix generateMatrix(int n, int m) {
    Matrix mat = new Matrix(n, m);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        mat.setValueAt(i, j, getRandomNumberBetween(0, 255) / 255.0d);
      }
    }
    return mat;
  }

  public static int getRandomNumberBetween(int min, int max) {
    return min + (int) (Math.random() * ((max - min) + 1));
  }
}