Clustering and Performance Test (50 clusters, 20,000 frames)

Posted: April 25, 2013 at 10:13 am

The spiking clustering time has been solved! The change in the code was to mark both clusters and scratch units for removal after a merge, whereas previously only clusters would be marked. This test had a very small number of clusters (less than the number of regions in a single frame) so that any issues with spiking clustering time would appear earlier. The following plot shows quite stable time for clustering and rendering, so we’re ready for some longer-term tests:

20000_debug_performanceTestG

The initial spike in total update time is the time for CUDA compilation for GPU segmentation operations. The mean rendering time (segmentation + clustering + rendering) is ~2 seconds with a variance of 0.084. The aim is to get it down to 1s (target frame-rate), and move the segmentation into a second thread to run on the second core. Following is the clustering implementation in its current state:

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
// Destructive clustering. (BSAS)
// TODO this does not keep track of parms for measure of variance. Is there a running version of a variance calculation?
void clustering::cluster(std::list<percepUnit> &scratch, std::list<percepUnit> &units, string FGBG) {
    list<percepUnit>::iterator scratchUnit, unit;
    list<percepUnit> newUnits;
    float similarityTresh; // threshold at which to consider percepts mergeable.
    int maxClusters;

    // Struct to store pointers to percepUnits + their distance.
    struct percepUnitDist{
        percepUnit *scratchUnit;
        percepUnit *unit;
        float dist;
    };

    vector<percepUnitDist> dists; // caches all distances
    vector<percepUnitDist>::iterator distIter;
    vector<float> minDists; // for each scratchUnit gives the distance to the nearest percepUnit.
    vector<float>::iterator minDistsIter;

    // different thresholds depending on FG or BG clustering
    if (FGBG == "BG") {
        similarityTresh = 2.3; // was 2.3
        maxClusters = 1000; // 1000
    } else if (FGBG == "FG") {
        similarityTresh = 20; // colour channels are not normalized.
        maxClusters = 1000; // 1000
    } else {
        similarityTresh = 0; // no merging
        cout << "FGBG argument was not FG or BG, returning." <<endl;
        return;
    }

    // If the number of clusters is smaller than the maxClusters
    if (units.size() < maxClusters) {
        //cout << "< maxClusters" << endl;

        // make new clusters as needed
        // For every scratch percepUnit:
        for (scratchUnit = scratch.begin(); scratchUnit != scratch.end(); scratchUnit++) {
            // For every percepUnit:
            for (unit = units.begin(); unit != units.end(); unit++) {

                // Some units were already processed and removed, ignore those.
                if ((not scratchUnit->remove) and (not unit->remove)) {

                    // compare pairs
                    float dist = featureDist(*scratchUnit, *unit, FGBG);
                    //cout << "DISTANCE: " << dist << endl;

                    // TODO this is a hard thresh, but what if you cache all distances and then
                    // pick the n nearest for merging, where n = the number of pairs: percepUnits.size()
                    // This is how this number was arrived at as a starting point.
               
                    if (dist < similarityTresh) {
                        // add new units to the list:
                        percepUnit newUnit = mergePerceps(*scratchUnit, *unit);
                        newUnit.activation = 1; // activate unit.
                        newUnits.push_back( newUnit );

                        // mark parents for deletion.
                        unit->remove = true;
                        scratchUnit->remove = true;
                    }
                }
            }
        }

        // add scratch units to the end of units for future clustering.
        units.insert(units.end(), scratch.begin(), scratch.end());

    } else {
        //cout << "> maxClusters" << endl;

        // Two scratch units may be merged with the same cluster!      
        // Only merge with existing clusters.
        // For every scratch percepUnit:
        for (scratchUnit = scratch.begin(); scratchUnit != scratch.end(); scratchUnit++) {
            float minDist=2025.1172; // This is the max possible distance in unnormalized CIELuv, and much larger than the normalized dist.
            // For every percepUnit:
            for (unit = units.begin(); unit != units.end(); unit++) {

                // compare pairs
                float dist = featureDist(*scratchUnit, *unit, FGBG);
                //cout << "distance: " << dist << endl;

                // Put pairs in a structure that caches their distances
                percepUnitDist percepDist;
                percepDist.scratchUnit = &(*scratchUnit); // address of where scratchUnit points to.
                percepDist.unit = &(*unit);
                percepDist.dist = dist;

                // Figure out the percepUnit that is closest to this scratchUnit.
                if (dist < minDist)
                    minDist = dist;
           
                dists.push_back(percepDist); // append dist struct
            }
            minDists.push_back(minDist); // append the min distance to the nearest percepUnit for this particular scratchUnit.
        }

        // Loop through dists and merge all the closest pairs.
        // Loop through all dists
        for (distIter = dists.begin(); distIter != dists.end(); distIter++) {
            // Loop through all minDists for each scratchUnit.
            for (minDistsIter = minDists.begin(); minDistsIter != minDists.end(); minDistsIter++) {
                // if this is the closest cluster, and the closest cluster has not already been merged, and the scratch has not already been merged.
                // TODO this means that a mergable percept may be ignored! (blindness)
                // What should happen is we activate the percept that was previously merged.
                if (*minDistsIter == distIter->dist and not distIter->unit->remove and not distIter->scratchUnit->remove) {
                    //cout << "Will merge units at this distance: " << *minDistsIter << endl;

                    percepUnit newUnit = mergePerceps(*(distIter->scratchUnit), *(distIter->unit));
                    newUnit.activation = 1; // activate unit.
                    newUnits.push_back( newUnit );

                    // mark parents for deletion.
                    // TODO what happens if the unit here is one that has already been merged with a scratch unit?
                    // Since we don't test for remove it stays in the cue and could be merged with another unit.
                    distIter->unit->remove = true;
                    distIter->scratchUnit->remove = true;
                }
            }
        }
    }

    // Debugging spikes in clustering time.
    if (scratch.size() > 0) {
        /*if (FGBG == "FG") {
            cout << "DEBUG numNewUnitsFG " << frameNum << " " << newUnits.size() << endl;
            cout << "DEBUG numScratchFG " << frameNum << " " << scratch.size() << endl;
            cout << "DEBUG extraNewUnitsFG " << frameNum << " " << ((int)newUnits.size() - (int)scratch.size()) << endl;
        } else {
            cout << "DEBUG numNewUnitsBG " << frameNum << " " << newUnits.size() << endl;
            cout << "DEBUG numScratchBG " << frameNum << " " << scratch.size() << endl;
            cout << "DEBUG extraNewUnitsBG " << frameNum << " " << ((int)newUnits.size() - (int)scratch.size()) << endl;
        }*/


        if (((int)newUnits.size() - (int)scratch.size()) > 20)
            this->quit = true;
    }

    // Remove the percepts that have been marked for removal.
    units.erase(remove_if(units.begin(), units.end(), removePercepsMarkedForRemoval), units.end());

    // Add merged untils onto the end of units.
    units.insert(units.end(), newUnits.begin(), newUnits.end());
   
}