001package org.openimaj.demos.sandbox.tldcpp.detector; 002 003import java.util.List; 004 005import org.openimaj.demos.sandbox.tldcpp.videotld.TLDUtil; 006import org.openimaj.math.geometry.shape.Rectangle; 007 008/** 009 * A simple greedy clustering algorithm which puts windows in the same cluster 010 * if they are close to each other, and combines clusters if they are close 011 * 012 * the goal is to find a set of windows which all represent a good location for the object 013 * @author Sina Samangooei (ss@ecs.soton.ac.uk) 014 * 015 */ 016public class Clustering { 017 /** 018 * The windows to compare 019 */ 020 public ScaleIndexRectangle[] windows; 021 022 DetectionResult detectionResult; 023 024 /** 025 * sets a default cutoff of .5f 026 */ 027 public Clustering() { 028 cutoff = .5f; 029 windows = null; 030 } 031 //Configurable members 032 /** 033 * how far overlapped two things must be before they can be in the same cluster 034 */ 035 public float cutoff; 036 037 /** 038 * the pointer to windows is set to null 039 */ 040 public void release() { 041 windows = null; 042 } 043 044 void calcDistances(float [] distances) { 045 float [] distances_tmp = distances; 046 int distances_tmp_index = 0; 047 048 List<Integer> confidentIndices = detectionResult.confidentIndices; 049 050 int indices_size = confidentIndices.size(); 051 052 for(int i = 0; i < confidentIndices.size(); i++) { 053 int firstIndex = confidentIndices.get(0); 054 confidentIndices.remove(0); 055 TLDUtil.tldOverlapOne(windows, firstIndex, confidentIndices,distances_tmp, distances_tmp_index); 056 distances_tmp_index += indices_size-i-1; 057 } 058 059 for(int i = 0; i < indices_size*(indices_size-1)/2; i++) { 060 distances[i] = 1-distances[i]; 061 } 062 063 } 064 065 /** 066 * Clusters the overlap of each window to each other window and 067 * sets the results in the {@link DetectionResult} instance. 068 * 069 * 2 things are saved to {@link DetectionResult}: 070 * - The number of clusters (1 means we have a very good grouping of windows) 071 * - the detector bounding box, a mean of all the bounding boxes in the single cluster 072 */ 073 public void clusterConfidentIndices() { 074 int numConfidentIndices = detectionResult.confidentIndices.size(); 075 float [] distances = new float[numConfidentIndices*(numConfidentIndices-1)/2]; 076 calcDistances(distances); 077 int [] clusterIndices = new int[numConfidentIndices]; 078 cluster(distances, clusterIndices); 079 if(detectionResult.numClusters == 1) { 080 calcMeanRect(detectionResult.confidentIndices); 081 //TODO: Take the maximum confidence as the result confidence. 082 } 083 } 084 085 void calcMeanRect(List<Integer> indices) { 086 087 float x,y,w,h; 088 x=y=w=h=0; 089 090 int numIndices = indices.size(); 091 for(int i = 0; i < numIndices; i++) { 092 ScaleIndexRectangle bb = this.windows[indices.get(i)]; 093// int * bb = &windows[TLD_WINDOW_SIZE*indices.at(i)]; 094 x += bb.x; 095 y += bb.y; 096 w += bb.width; 097 h += bb.height; 098 } 099 100 x /= numIndices; 101 y /= numIndices; 102 w /= numIndices; 103 h /= numIndices; 104 105 Rectangle rect = new Rectangle(); 106 detectionResult.detectorBB = rect; 107 rect.x = (float) Math.floor(x+0.5); 108 rect.y = (float) Math.floor(y+0.5); 109 rect.width = (float) Math.floor(w+0.5); 110 rect.height = (float) Math.floor(h+0.5); 111 112 } 113 114 115 void cluster(float [] distances, int [] clusterIndices) { 116 int numConfidentIndices = detectionResult.confidentIndices.size(); 117 118 if(numConfidentIndices == 1) { 119 clusterIndices[0] = 0; 120 detectionResult.numClusters = 1; 121 return; 122 } 123 124 int numDistances = numConfidentIndices*(numConfidentIndices-1)/2; 125 126 //Now: Cluster distances 127 boolean [] distUsed = new boolean[numDistances]; 128 129 for(int i = 0; i < numConfidentIndices; i++) { 130 clusterIndices[i] = -1; 131 } 132 133 int newClusterIndex = 0; 134 135 int numClusters = 0; 136 while(true) { 137 138 //Search for the shortest distance 139 float shortestDist = -1; 140 int shortestDistIndex = -1; 141 int i1 = 0; 142 int i2 = 0; 143 int distIndex = 0; 144 for(int i = 0; i < numConfidentIndices; i++) { //Row index 145 for(int j = i+1; j < numConfidentIndices; j++) { //Start from i+1 146 147 if(!distUsed[distIndex] && (shortestDistIndex == -1 || distances[distIndex] < shortestDist)) { 148 shortestDist = distances[distIndex]; 149 shortestDistIndex = distIndex; 150 i1=i; 151 i2=j; 152 } 153 154 distIndex++; 155 } 156 } 157 158 if(shortestDistIndex == -1) { 159 break; // We are done 160 } 161 162 distUsed[shortestDistIndex] = true; 163 164 //Now: Compare the cluster indices 165 //If both have no cluster and distance is low, put them both to a new cluster 166 if(clusterIndices[i1] == -1 && clusterIndices[i2] == -1) { 167 //If distance is short, put them to the same cluster 168 if(shortestDist < cutoff) { 169 clusterIndices[i1] = clusterIndices[i2] = newClusterIndex; 170 newClusterIndex++; 171 numClusters++; 172 } else { //If distance is long, put them to different clusters 173 clusterIndices[i1] = newClusterIndex; 174 newClusterIndex++; 175 numClusters++; 176 clusterIndices[i2] = newClusterIndex; 177 newClusterIndex++; 178 numClusters++; 179 } 180 //Second point is in cluster already 181 } else if (clusterIndices[i1] == -1 && clusterIndices[i2] != -1) { 182 if(shortestDist < cutoff) { 183 clusterIndices[i1] = clusterIndices[i2]; 184 } else { //If distance is long, put them to different clusters 185 clusterIndices[i1] = newClusterIndex; 186 newClusterIndex++; 187 numClusters++; 188 } 189 } else if (clusterIndices[i1] != -1 && clusterIndices[i2] == -1) { 190 if(shortestDist < cutoff) { 191 clusterIndices[i2] = clusterIndices[i1]; 192 } else { //If distance is long, put them to different clusters 193 clusterIndices[i2] = newClusterIndex; 194 newClusterIndex++; 195 numClusters++; 196 } 197 } else { //Both indices are in clusters already 198 if(clusterIndices[i1] != clusterIndices[i2] && shortestDist < cutoff) { 199 //Merge clusters 200 201 int oldClusterIndex = clusterIndices[i2]; 202 203 for(int i = 0; i < numConfidentIndices; i++) { 204 if(clusterIndices[i] == oldClusterIndex) { 205 clusterIndices[i] = clusterIndices[i1]; 206 } 207 } 208 209 numClusters--; 210 } 211 } 212 } 213 214 detectionResult.numClusters = numClusters; 215 } 216 217 218}