VLFeat.org

Documentation - C API

• Home
• Download
• Documentation
  • Matlab API
  • C API
  • Man pages
• Tutorials
• Applications

hikmeans.c

Go to the documentation of this file.

/* AUTORIGHTS
Copyright (C) 2007-10 Andrea Vedaldi and Brian Fulkerson

This file is part of VLFeat, available under the terms of the
GNU GPLv2, or (at your option) any later version.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "hikmeans.h"

vl_uint8*
vl_hikm_copy_subset (vl_uint8 const * data, 
                     vl_uint * ids, 
                     int N, int M, 
                     vl_uint id, int *N2)
{
  int i ;
  int count = 0;

  /* count how many data points with this label there are */
  for (i = 0 ; i < N ; i++)
    if (ids[i] == id)
      count ++ ;
  *N2 = count ;
  
  /* copy each datum to the buffer */
  {
    vl_uint8 * new_data = vl_malloc (sizeof(vl_uint8) * M * count);    
    count = 0;
    for (i = 0 ; i < N ; i ++)
      if (ids[i] == id)
        {
          memcpy(new_data + count * M, 
                 data     + i     * M, 
                 sizeof(vl_uint8) * M);
          count ++ ;
        }    
    *N2 = count ;
    return new_data ;
  }  
}

static VlHIKMNode * 
xmeans (VlHIKMTree *tree, 
        vl_uint8 const *data, 
        int N, int K, int height)
{
  VlHIKMNode *node = vl_malloc (sizeof(VlHIKMNode)) ;
  vl_uint     *ids = vl_malloc (sizeof(vl_uint) * N) ;

  node-> filter   = vl_ikm_new (tree -> method) ;    
  node-> children = (height == 1) ? 0 : vl_malloc (sizeof(VlHIKMNode*) * K) ;

  vl_ikm_set_max_niters (node->filter, tree->max_niters) ;
  vl_ikm_set_verbosity  (node->filter, tree->verb - 1  ) ;
  vl_ikm_init_rand_data (node->filter, data, tree->M, N, K) ;
  vl_ikm_train          (node->filter, data, N) ;
  vl_ikm_push           (node->filter, ids, data, N) ;
  
  /* recurse for each child */
  if (height > 1) {
    int k ;
    for (k = 0 ; k < K ; k ++) {
      int partition_N ;
      int partition_K ;
      vl_uint8 *partition ;
      
      partition = vl_hikm_copy_subset
        (data, ids, N, tree->M, k, &partition_N) ;
      
      partition_K = VL_MIN (K, partition_N) ;
      
      node->children [k] = xmeans
        (tree, partition, partition_N, partition_K, height - 1) ;
      
      vl_free (partition) ;

      if (tree->verb > tree->depth - height) {
        VL_PRINTF("hikmeans: branch at depth %d: %6.1f %% completed\n", 
                  tree->depth - height,
                  (double) (k+1) / K * 100) ;
      }
    }
  }
  
  vl_free (ids) ;
  return node ;
}

static void 
xdelete (VlHIKMNode *node)
{
  if(node) {
    int k ;
    if (node->children) {
      for(k = 0 ; k < vl_ikm_get_K (node->filter) ; ++k)
        xdelete (node->children[k]) ;
      vl_free (node->children) ;
    }
    if (node->filter) 
      vl_ikm_delete (node->filter) ;
    vl_free(node);
  }
}

VL_EXPORT
VlHIKMTree *
vl_hikm_new (int method)
{
  VlHIKMTree *f = vl_malloc (sizeof(VlHIKMTree)) ;
  f -> M          = 0 ;
  f -> K          = 0 ;
  f -> max_niters = 200 ;
  f -> method     = method ;
  f -> verb       = 0 ;
  f -> depth      = 0 ;
  f -> root       = 0 ;
  return f ;
}

VL_EXPORT
void
vl_hikm_delete (VlHIKMTree *f)
{
  if (f) {
    xdelete (f -> root) ;
    vl_free (f) ;
  }
}

VL_EXPORT
void
vl_hikm_init (VlHIKMTree *f, int M, int K, int depth)
{
  assert(depth > 0) ;
  assert(M     > 0) ;
  assert(K     > 0) ;
  
  xdelete (f -> root) ;
  f -> root = 0;
  
  f -> M = M ;
  f -> K = K ;
  f -> depth = depth ;
}

VL_EXPORT
void
vl_hikm_train (VlHIKMTree *f, vl_uint8 const *data, int N)
{
  f -> root  = xmeans (f, data, N, VL_MIN(f->K, N), f->depth) ;
}

VL_EXPORT
void
vl_hikm_push (VlHIKMTree *f, vl_uint *asgn, vl_uint8 const *data, int N)
{
  int i, d,
    M = vl_hikm_get_ndims (f),
    depth = vl_hikm_get_depth (f) ;
  
  /* for each datum */
  for(i = 0 ; i < N ; i++) {
    VlHIKMNode *node = f->root ;
    d = 0 ;      
    while (node) {
      /*
      vl_uint best = 
        vl_ikm_push_one (vl_ikm_get_centers (node->filter),  
                         data + i * M,
                         M,
                         vl_ikm_get_K (node->filter)) ;
      */
      
      vl_uint best ;
      vl_ikm_push (node->filter, &best, data + i * M, 1) ;
      
      asgn [i*depth + d] = best ;
      ++ d ;
      
      if (!node->children) break ;
      node = node->children [best] ;
    }
  }
}

 

© 2005-10 Andrea Vedaldi and Brian Fulkerson