1 #include <functional>
2 #include <algorithm>
3 #include <limits>
4 #include <cmath>
5 #include "sdet_region_classifier.h"
6 #include "sdet_graph_img_seg.h"
7 #include "vul/vul_timer.h"
8 #if 0
9 void sdet_region_classifier::find_iou_clusters(const std::map<unsigned, sdet_region_sptr >& regions){
10 vul_timer t;
11 vgl_rtree<V_, B_, C_> tr; // the rtree
12 // insert regions in the rtree
13 std::map<unsigned, sdet_region_sptr>::const_iterator rit = regions.begin();
14 for(;rit != regions.end(); ++rit){
15 vgl_box_2d<float> bb =(*rit).second->bbox();
16 if(!bb.is_empty())
17 tr.add(rit->second);
18 }
19 std::cout << "insert in rtree in " << t.real() << " msec" << std::endl;
20 t.mark();
21 // find sets of high int over union regions
22 float iou_thresh = 0.5f;
23 rit = regions.begin();
24 for(;rit != regions.end(); ++rit){
25 vgl_box_2d<float> bb =(*rit).second->bbox();
26 unsigned lab = (*rit).second->label();
27 std::vector<sdet_region_sptr> intersecting_regions;
28 tr.get(bb, intersecting_regions);
29 std::map<unsigned, float> iou_index;
30 for(std::vector<sdet_region_sptr>::iterator iit = intersecting_regions.begin();
31 iit != intersecting_regions.end(); ++iit){
32 if((*iit)->label() == lab){
33 iou_index[lab]=1.0f;
34 continue;
35 }
36 float iou = (*iit)->int_over_min_area(bb); //JLM
37 if(iou>iou_thresh)
38 iou_index[(*iit)->label()]=iou;
39 }
40 if(iou_index.size())
41 iou_clusters_[lab]=iou_index;
42 }
43 std::cout << "find IOU clusters in " << t.real() << " msec" << std::endl;
44 }
45 #endif
find_iou_clusters(const std::map<unsigned,sdet_region_sptr> & regions)46 void sdet_region_classifier::find_iou_clusters(const std::map<unsigned, sdet_region_sptr >& regions){
47 vul_timer t;
48 vgl_rtree<V_, B_, C_> tr; // the rtree
49 // insert regions in the rtree
50 auto rit = regions.begin();
51 for(;rit != regions.end(); ++rit){
52 vgl_box_2d<float> bb =(*rit).second->bbox();
53 if(!bb.is_empty())
54 tr.add(rit->second);
55 }
56 std::cout << "insert in rtree in " << t.real() << " msec" << std::endl;
57 t.mark();
58 // find sets of high int over union regions
59 std::set<unsigned> already_clustered;
60 float iou_thresh = 0.25f;
61 rit = regions.begin();
62 for(;rit != regions.end(); ++rit){
63 vgl_box_2d<float> bb =(*rit).second->bbox();
64 unsigned lab = (*rit).second->label();
65 auto ait = already_clustered.find(lab);
66 if(ait != already_clustered.end())
67 continue;
68 std::vector<sdet_region_sptr> intersecting_regions;
69 tr.get(bb, intersecting_regions);
70 std::map<unsigned, float> iou_index;
71 for(auto & intersecting_region : intersecting_regions){
72 if(intersecting_region->label() == lab){
73 iou_index[lab]=1.0f;
74 already_clustered.insert(lab);
75 continue;
76 }
77 unsigned labi = intersecting_region->label();
78 ait = already_clustered.find(labi);
79 if(ait != already_clustered.end())
80 continue;
81 float iou = intersecting_region->int_over_min_area(bb); //JLM
82 if(iou>iou_thresh){
83 iou_index[labi]=iou;
84 already_clustered.insert(labi);
85 }
86 }
87 if(iou_index.size())
88 iou_clusters_[lab]=iou_index;
89 }
90 std::cout << "find IOU clusters in " << t.real() << " msec" << std::endl;
91 }
compute_iou_cluster_similarity()92 void sdet_region_classifier::compute_iou_cluster_similarity(){
93 for(auto cit0 = iou_clusters_.begin();
94 cit0 != iou_clusters_.end(); ++cit0){
95 unsigned lab0 = cit0->first;
96 const std::map<unsigned, float>& iou_index0 = cit0->second;
97 std::map<unsigned, region_sim> sim_map;
98 for(auto cit1 = cit0;
99 cit1 != iou_clusters_.end(); ++cit1){
100 unsigned lab1 = cit1->first;
101 if(lab0 == lab1)
102 continue;//skip equal labels
103 const std::map<unsigned, float>& iou_index1 = cit1->second;
104 //if iou_index1 contains lab0 then skip the entire cluster (for now)
105 auto iit = iou_index1.find(lab0);
106 if(iit != iou_index1.end())
107 continue;
108 // see if clusters intersect
109 bool intersect = false;
110 for(auto iit0 = iou_index0.begin();
111 iit0 != iou_index0.end()&&!intersect; ++iit0){
112 unsigned labi0 = iit0->first;
113 for(auto iit1 = iou_index1.begin();
114 iit1 != iou_index1.end()&&!intersect; ++iit1){
115 unsigned labi1 = iit1->first;
116 if(labi1 == labi0)
117 intersect = true;
118 }
119 }
120 if(intersect)
121 continue;
122 // iterate through the clusters and find the most similar region pair
123 float max_s = 0.0f;
124 region_sim max_rsim;
125 for(auto iit0 : iou_index0){
126 unsigned labi0 = iit0.first;
127 const sdet_region_sptr& r0 = diverse_regions_[labi0];
128 const bsta_histogram<float> h0 = diverse_hists_[labi0];
129 for(auto iit1 : iou_index1){
130 unsigned labi1 = iit1.first;
131 const sdet_region_sptr& r1 = diverse_regions_[labi1];
132 const bsta_histogram<float>& h1 = diverse_hists_[labi1];
133 float s = similarity(r0, h0, r1, h1);
134 if(s>max_s){
135 max_s = s;
136 max_rsim.ri_= labi0;
137 max_rsim.rj_= labi1;
138 max_rsim.s_ = max_s;
139 }
140 }
141 }
142 sim_map[lab1]=max_rsim;
143 }
144 region_sim self_rsim;
145 self_rsim.ri_ = lab0;
146 self_rsim.rj_ = lab0;
147 self_rsim.s_ = 2.0f;
148 sim_map[lab0]=self_rsim;
149 cluster_similarity_[lab0]=sim_map;
150 }
151 }
remove_diverse_region(unsigned label)152 void sdet_region_classifier::remove_diverse_region(unsigned label){
153 auto dit = diverse_regions_.find(label);
154 if(dit != diverse_regions_.end())
155 diverse_regions_.erase(dit);
156 auto hit = diverse_hists_.find(label);
157 if(hit != diverse_hists_.end())
158 diverse_hists_.erase(hit);
159 }
160
compute_hist_of_nbrs()161 void sdet_region_classifier::compute_hist_of_nbrs(){
162 for(auto & diverse_region : diverse_regions_){
163 unsigned lab = diverse_region.first;
164 const std::set<unsigned>& nbrs = diverse_region.second->nbrs();
165 auto nit = nbrs.begin();
166 bsta_histogram<float> hn = diverse_hists_[*nit]; ++nit;
167 while(nit != nbrs.end()){
168 if(*nit == lab)
169 continue;
170 bsta_histogram<float>& hi = diverse_hists_[*nit];
171 if(!merge_hists(hi, hn, hn)){
172 std::cout << "compute hist of neighbors -- failed! " << *nit << std::endl;
173 return;
174 }
175 ++nit;
176 }
177 neighbors_hists_[lab] = hn;
178 }
179 }
compute_bright_regions()180 void sdet_region_classifier::compute_bright_regions(){
181
182 for(auto & diverse_hist : diverse_hists_){
183 unsigned lab = diverse_hist.first;
184 bsta_histogram<float>& hr = diverse_hist.second;
185 bsta_histogram<float>& hn = neighbors_hists_[lab];
186 float hr_median = hr.value_with_area_above(0.5f);//median
187 float hn_median = hn.value_with_area_above(0.5f);
188 float delta = 0.025*(hr_median + hn_median);
189 if(hr_median>(hn_median+delta))
190 bright_regions_.insert(lab);
191 }
192 }
193 float sdet_region_classifier::
compute_partition_quality(std::map<unsigned,std::map<unsigned,region_sim>> const & cluster_sim)194 compute_partition_quality(std::map< unsigned, std::map<unsigned, region_sim> > const& cluster_sim){
195 auto nf = static_cast<float>(cluster_sim.size());
196 float neu_sum = 0.0f, den_sum = 0.0f;
197 for(const auto & sit : cluster_sim){
198 unsigned lab = sit.first;
199 const std::map<unsigned, region_sim>& rsim = sit.second;
200 for(auto rit : rsim)
201 if(rit.first == lab)
202 neu_sum += rit.second.s_;
203 else
204 den_sum += rit.second.s_;
205 }
206 float q = (nf-1.0f)*neu_sum/den_sum;
207 return q;
208 }
merge_similarity_map(std::map<unsigned,std::map<unsigned,region_sim>> const & sim_before,std::map<unsigned,std::map<unsigned,region_sim>> & sim_after,unsigned labi,unsigned labj,unsigned new_label)209 bool sdet_region_classifier::merge_similarity_map(std::map< unsigned, std::map<unsigned, region_sim> > const& sim_before,
210 std::map< unsigned, std::map<unsigned, region_sim> >& sim_after,
211 unsigned labi, unsigned labj, unsigned new_label){
212 auto sit = sim_before.find(labi);
213 if(sit == sim_before.end()){
214 std::cout << labi << " not in similarity matrix" << std::endl;
215 return false;
216 }
217 sit = sim_before.find(labj);
218 if(sit == sim_before.end()){
219 std::cout << labj << " not in similarity matrix" << std::endl;
220 return false;
221 }
222 sit = sim_before.find(new_label);
223 if(sit != sim_before.end()){
224 std::cout << new_label << " not unique" << std::endl;
225 return false;
226 }
227 // find similarities to both labi and labj
228 std::map<unsigned, region_sim> simi, simj;
229 for(const auto & sit : sim_before){
230 unsigned lab = sit.first;
231 const std::map<unsigned, region_sim>& rsim = sit.second;
232 if(lab == labi){
233 for(auto itr : rsim){
234 unsigned labr = itr.first;
235 simi[labr] = itr.second;
236 if(labr == labj)
237 simj[labr] = itr.second;
238 }
239 }else if(lab == labj){
240 for(auto itr : rsim){
241 unsigned labr = itr.first;
242 simj[labr] = itr.second;
243 if(labr == labi)
244 simi[labr] = itr.second;
245 }
246 }else{
247
248 for(auto itr : rsim){
249 unsigned labr = itr.first;
250 if(labr == labi)
251 simi[lab] = itr.second;
252 if(labr == labj)
253 simj[lab] = itr.second;
254 }
255 }
256 }
257 //fill out the similarity table except for the merged rows and cols
258 //assume that the merged label will be at the last row and col
259 for(const auto & sit : sim_before){
260 unsigned lab = sit.first;
261 std::map<unsigned, region_sim> temp;
262 const std::map<unsigned, region_sim>& rsim = sit.second;
263 // skip the merged rows
264 if(lab == labi || lab == labj)
265 continue;
266 for(auto rit : rsim){
267 unsigned labr = rit.first;
268 // skip the merged cols
269 if(labr == labi||labr == labj)
270 continue;
271 temp[labr] = rit.second;
272 }
273 sim_after[lab]=temp;
274 }
275
276 // fill in the last row (new_label)
277 std::map<unsigned, region_sim> temp;
278 region_sim& rsimi = simj[labi];
279 region_sim& rsimj = simi[labj];
280 if(rsimi.s_>rsimj.s_)
281 temp[new_label]=rsimi;
282 else
283 temp[new_label]=rsimj;
284 sim_after[new_label] = temp;
285 // fill in the last column (new_label)
286 for(auto riti = simi.begin();
287 riti != simi.end(); ++riti){
288 unsigned labri = riti->first;
289 if(labri == labi)
290 continue;
291 for(auto ritj = simj.begin();
292 ritj != simj.end(); ++ritj){
293 unsigned labrj = ritj->first;
294 if(labrj == labj)
295 continue;
296 if(labri == labrj){
297 std::map<unsigned, region_sim>& rsim = sim_after[labri];
298 region_sim& rsimi = simj[labri];
299 region_sim& rsimj = simi[labrj];
300 if(rsimi.s_>rsimj.s_)
301 rsim[new_label]=rsimi;
302 else
303 rsim[new_label]=rsimj;
304 }
305 }
306 }
307 return true;
308 }
309