hikmeans.c

Go to the documentation of this file.

/*
Copyright (C) 2007-12 Andrea Vedaldi and Brian Fulkerson.
All rights reserved.

This file is part of the VLFeat library and is made available under
the terms of the BSD license (see the COPYING file).
*/

#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_uint32 *ids,
                     vl_size N, vl_size M,
                     vl_uint32 id, vl_size *N2)
{
  vl_uindex i ;
  vl_size 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(*new_data) * M * count);
    count = 0;
    for (i = 0 ; i < N ; i ++) {
      if (ids[i] == id) {
        memcpy(new_data + count * M,
               data + i * M,
               sizeof(*new_data) * M);
        count ++ ;
      }
    }
    *N2 = count ;
    return new_data ;
  }
}

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

  node->filter = vl_ikm_new (tree -> method) ;
  node->children = (height == 1) ? 0 : vl_malloc (sizeof(*node->children) * 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) ;

  /* recursively process each child */
  if (height > 1) {
    vl_uindex k ;
    for (k = 0 ; k < K ; ++k) {
      vl_size partition_N ;
      vl_size partition_K ;
      vl_uint8 *partition ;

      partition = vl_hikm_copy_subset
        (data, ids, N, tree->M, (vl_uint32)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 > (signed)tree->depth - (signed)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) {
    vl_uindex 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);
  }
}

VlHIKMTree *
vl_hikm_new (int method)
{
  VlHIKMTree *f = vl_calloc (sizeof(VlHIKMTree), 1) ;
  f->max_niters = 200 ;
  f->method = method ;
  return f ;
}

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

void
vl_hikm_init (VlHIKMTree *f, vl_size M, vl_size K, vl_size 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 ;
}

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

void
vl_hikm_push (VlHIKMTree *f, vl_uint32 *asgn, vl_uint8 const *data, vl_size N)
{
  vl_uindex i, d ;
  vl_size M = vl_hikm_get_ndims (f) ;
  vl_size depth = vl_hikm_get_depth (f) ;

  /* for each datum */
  for(i = 0 ; i < N ; i++) {
    VlHIKMNode *node = f->root ;
    d = 0 ;
    while (node) {
      vl_uint32 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] ;
    }
  }
}

/* ---------------------------------------------------------------- */
/*                                              Setters and getters */
/* ---------------------------------------------------------------- */

vl_size
vl_hikm_get_ndims (VlHIKMTree const* f)
{
  return f->M ;
}

vl_size
vl_hikm_get_K (VlHIKMTree const *f)
{
  return f->K ;
}

vl_size
vl_hikm_get_depth (VlHIKMTree const *f)
{
  return f->depth ;
}


int
vl_hikm_get_verbosity (VlHIKMTree const *f)
{
  return f->verb ;
}

vl_size
vl_hikm_get_max_niters (VlHIKMTree const *f)
{
  return f-> max_niters ;
}

VlHIKMNode const *
vl_hikm_get_root (VlHIKMTree const *f)
{
  return f->root ;
}

void
vl_hikm_set_verbosity (VlHIKMTree *f, int verb)
{
  f->verb = verb ;
}

void
vl_hikm_set_max_niters (VlHIKMTree *f, int max_niters)
{
  f->max_niters = max_niters ;
}