neal young / Roy18Exploiting

Minimization of labeling effort for person reidentification in camera networks is an important problem as most of the existing popular methods are supervised and they require large amount of manual annotations, acquiring which is a tedious job. In this work, we focus on this labeling effort minimization problem and approach it as a subset selection task where the objective is to select an optimal subset of imagepairs for labeling without compromising performance. Towards this goal, our proposed scheme first represents any camera network (with k number of cameras) as an edge weighted complete kpartite graph where each vertex denotes a person and similarity scores between persons are used as edgeweights. Then in the second stage, our algorithm selects an optimal subset of pairs by solving a triangle free subgraph maximization problem on the kpartite graph. This subgraph weight maximization problem is NPhard (at least for k larger than 3) which means for large datasets the optimization problem becomes intractable. In order to make our framework scalable, we propose two polynomial time approximatelyoptimal algorithms. The first algorithm is a 1/2approximation algorithm which runs in linear time in the number of edges. The second algorithm is a greedy algorithm with subquadratic (in number of edges) timecomplexity. Experiments on three stateoftheart datasets depict that the proposed approach requires on an average only 815% manually labeled pairs in order to achieve the performance when all the pairs are manually annotated.
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.