k-Prototype Learning for 3D Rigid Structures
In this paper, we study the following new variant of prototype learning, called k-prototype learning problem for 3D rigid structures: Given a set of 3D rigid structures, find a set of k rigid structures so that each of them is a prototype for a cluster of the given rigid structures and the total cost (or dissimilarity) is minimized. Prototype learning is a core problem in machine learning and has a wide range of applications in many areas. Existing results on this problem have mainly focused on the graph domain. In this paper, we present the first algorithm for learning multiple prototypes from 3D rigid structures. Our result is based on a number of new insights to rigid structures alignment, clustering, and prototype reconstruction, and is practically efficient with quality guarantee. We validate our approach using two type of data sets, random data and biological data of chromosome territories. Experiments suggest that our approach can effectively learn prototypes in both types of data.
This paper introduces an algorithm to cluster shapes 
      into k groups, each containing rigidly transformed versions of one shape, 
      and computing a prototype for each group. Two new chromatic clustering 
      algorithms are proposed to compute the prototype within a cluster with 
      various quality guarantees. I can see the interest of the proposed 
      algorithm with its theoretical guarantees. However, from a practical 
      standpoint, I am not entirely convinced of the benefits of the resulting 
      method. In particular: - Step 2(a) of the 1 prototype learning 
      algorithm finds the best alignment of each shape to the current prototype. 
      Would is really make a significant difference to simply compute the median 
      of the n points corresponding to point q_j, instead of using the chromatic 
      clustering algorithm? Since the alignment already guarantees a one-to-one 
      correspondence, is it really useful to recompute it with the chromatic 
      clustering algorithm? - It is mentioned that ICP would not be suitable 
      because it does not guarantee a one-to-one correspondence. This is true, 
      but I am not sure how often this problem would occur in practice. 
      Furthermore, since the chromatic clustering algorithm recomputes the 
      correspondences, it may not be relevant at all. - In practice, how 
      important is it to run several iterations of Step 2(a) and (b)? I would 
      expect that, if the clusters found by [11] are good, a single iteration is 
      sufficient. If the clusters are bad, then it would be hard to find a 
      meaningful prototype, anyway. - While the experiments show the good 
      behavior of the algorithm, they do not compare it against other existing 
      methods (e.g., an ICP-based approach, or simpler versions of the algorithm 
      as proposed above). It is thus not clear what the true benefits of the 
      algorithm are. It also seems to me that several references to 
      existing shape analysis works are missing. In particular: - The 
      manifold of 3D shapes has been studied by Kendall, and later by Dryden 
      & Mardia. - A lot of work on the topic has been recently done by 
      Srivastava and colleagues, e.g., Kurtek et al. CVPR'10. - Other shape 
      representations have also been studied, such as level sets (Osher & 
      Fedkiw), or medial surfaces (Bouix et al.). Additional comments: 
      - The multi-level net method seems related to a branch-and-bound 
      approach. Would it be possible to get better guarantees with a proper 
      branch-and-bound approach? For instance, Hartley & Kahl, IJCV'09, 
      studied branch-and-bound to optimize rotations, although in a different 
      context. - In Definitions 5 and 6, why change the notation from P_i to 
      G_i? - Line 233, it should be m median, instead of k. - In the 
      synthetic experiments, were the rigid shapes transformed by random rigid 
      transformations? With the current description, it seems that they just are 
      noisy versions of the prototypes, which would make the task easier.