Fast Template Evaluation with Vector Quantization
Applying linear templates is an integral part of many object detection systems and accounts for a significant portion of computation time. We describe a method that achieves a substantial end-to-end speedup over the best current methods, without loss of accuracy. Our method is a combination of approximating scores by vector quantizing feature windows and a number of speedup techniques including cascade. Our procedure allows speed and accuracy to be traded off in two ways: by choosing the number of Vector Quantization levels, and by choosing to rescore windows or not. Our method can be directly plugged into any recognition system that relies on linear templates. We demonstrate our method to speed up the original Exemplar SVM detector [1] by an order of magnitude and Deformable Part models [2] by two orders of magnitude with no loss of accuracy.
Authors have proposed a series of 'tricks' to reduce 
      the memory storage and computational cost of applying linear templates. 
      The presented approximation methods achieve speed-up without significant 
      loss of accuracy. Moreover, the authors aim for methods that trade off 
      between speed-up and accuracy by: choosing number of quantization levels, 
      16-bit or 32-bit arithmetic, and finally choosing to re-score windows or 
      not. More precisely, the key idea is to replace convolution by a look-up 
      table. To make the latter efficient, the authors use k-means as a 
      quantization method effectively reducing dimensionality (authors also 
      report excellence of k-means over PCA in Fig. 2). Finally, the authors 
      introduce different computational models showing achieved speed-up of the 
      proposed methods over the state-of-the-art detection algorithms on Pascal 
      VOC 2007. Similar conclusion is drawn based on the experiments on exemplar 
      SVM. Reference [2] (see below) seems the most related reference. 
      It is not cited in the paper an therefore a comparison is absent. A lot of 
      the ground is already covered in that paper - which takes away from the 
      novelty. [2] proposes an approximation if the filters in a sparse coding 
      way. Also nearest neightbor and pca are considered in [2]. 
      Although the presented idea is interesting and impactful as it 
      contributes to the speeding-up the detection task, the work is too 
      incremental. A replacement of dot-product in the convolution operator has 
      already been introduced in [1]. Considerable speed-up has also been shown 
      in [2] with a sparse intermediate representation and a nearest neighbor 
      approach where the closest part filters are retrieved. Also a pca 
      representation has been considered there as a baseline already. The 
      presented method scales up well as the number of classes grows. Also [3] 
      shows significant speed-up, however [3] seems to be complementary and fits 
      into the 'cascade' section of the paper. Pros: + Authors 
      tackle important problem of speeding up the convolution step that is at 
      heart in many detection systems, but not only. + The proposed methods 
      trades off between accuracy and speed-up + Simplicity of the method 
      + Authors have promised publishing source code. + Paper is 
      generally well written. Cons: - Incremental nature of the paper. 
      - Experiments shown in Table 1, Table 2, and Table 3 are confusing. In 
      particular, why the paper reports different total time for the same method 
      in different tables? Authors should also be more explicit how they have 
      estimated the running time of unaccessible algorithms. - It is not 
      clear which approximation 'trick' contributed the most to the speed-up 
      (simple look-up table, packed look-up table, 16-bit arithmetic, 
      deformation estimates, ...). Authors should make up experiments showing 
      the importance of every 'trick'. - Authors should be more explicit 
      about implementation details. For instance about the programming language 
      being used in the experiments for every method together with the 
      'programming tweaks'. [1] 'Fast, Accurate Detection of 100.000 
      Object Classes on a Single Machine' by T. Dean et. al. [2] 'Sparselet 
      Models for Efficient Multiclass Object Detection' by H. Song et. al. 
      [3] 'Branch and Rank: Efficient, Non-linear Object Detection' by A. 
      Lehmann et. al.