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}