ikmeans.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 "ikmeans.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h> /* memset */
#include "assert.h"

static void vl_ikm_init_lloyd (VlIKMFilt*) ;
static void vl_ikm_init_elkan (VlIKMFilt*) ;
static int vl_ikm_train_lloyd (VlIKMFilt*, vl_uint8 const*, vl_size) ;
static int vl_ikm_train_elkan (VlIKMFilt*, vl_uint8 const*, vl_size) ;
static void vl_ikm_push_lloyd (VlIKMFilt*, vl_uint32*, vl_uint8 const*, vl_size) ;
static void  vl_ikm_push_elkan  (VlIKMFilt*, vl_uint32*, vl_uint8 const*, vl_size) ;

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

void
vl_ikm_delete (VlIKMFilt* f)
{
  if (f) {
    if (f->centers) vl_free(f->centers) ;
    if (f->inter_dist) vl_free(f->inter_dist) ;
    vl_free(f) ;
  }
}

int
vl_ikm_train (VlIKMFilt *f, vl_uint8 const *data, vl_size N)
{
  int err ;

  if (f-> verb) {
    VL_PRINTF ("ikm: training with %d data\n",  N) ;
    VL_PRINTF ("ikm: %d clusters\n",  f -> K) ;
  }

  switch (f -> method) {
  case VL_IKM_LLOYD : err = vl_ikm_train_lloyd (f, data, N) ; break ;
  case VL_IKM_ELKAN : err = vl_ikm_train_elkan (f, data, N) ; break ;
  default :
    abort() ;
  }
  return err ;
}

void
vl_ikm_push (VlIKMFilt *f, vl_uint32 *asgn, vl_uint8 const *data, vl_size N) {
  switch (f -> method) {
  case VL_IKM_LLOYD : vl_ikm_push_lloyd (f, asgn, data, N) ; break ;
  case VL_IKM_ELKAN : vl_ikm_push_elkan (f, asgn, data, N) ; break ;
  default :
    abort() ;
  }
}

vl_uint32
vl_ikm_push_one (vl_ikmacc_t const *centers,
                 vl_uint8 const *data,
                 vl_size M, vl_size K)
{
  vl_uindex i,k ;

  /* assign data to centers */
  vl_uindex best = (vl_uindex) -1 ;
  vl_ikmacc_t best_dist = 0 ;

  for(k = 0 ; k < K ; ++k) {
    vl_ikmacc_t dist = 0 ;

    /* compute distance with this center */
    for(i = 0 ; i < M ; ++i) {
      vl_ikmacc_t delta = (vl_ikmacc_t)data[i] - centers[k*M + i] ;
      dist += delta * delta ;
    }

    /* compare with current best */
    if (best == (vl_uindex) -1 || dist < best_dist) {
      best = k  ;
      best_dist = dist ;
    }
  }
  return (vl_uint32)best;
}

/* ---------------------------------------------------------------- */
/*                                              Getters and setters */
/* ---------------------------------------------------------------- */

vl_size
vl_ikm_get_ndims (VlIKMFilt const* f)
{
  return f->M ;
}


vl_size
vl_ikm_get_K (VlIKMFilt const* f)
{
  return f->K ;
}

int
vl_ikm_get_verbosity (VlIKMFilt const* f)
{
  return f->verb ;
}

vl_size
vl_ikm_get_max_niters (VlIKMFilt const* f)
{
  return f->max_niters ;
}

vl_ikmacc_t const *
vl_ikm_get_centers (VlIKMFilt const* f)
{
  return f-> centers ;
}

void
vl_ikm_set_verbosity (VlIKMFilt *f, int verb)
{
  f-> verb = VL_MAX(0,verb) ;
}

void
vl_ikm_set_max_niters (VlIKMFilt *f, vl_size max_niters)
{
  f-> max_niters = max_niters ;
}

#include "ikmeans_init.tc"
#include "ikmeans_lloyd.tc"
#include "ikmeans_elkan.tc"