type_definition.h

mean-shift. pointer sample

/*! \file
  \verbatim
  
    Copyright (c) 2007, Sylvain Paris and Fr閐o Durand

    Permission is hereby granted, free of charge, to any person
    obtaining a copy of this software and associated documentation
    files (the "Software"), to deal in the Software without
    restriction, including without limitation the rights to use, copy,
    modify, merge, publish, distribute, sublicense, and/or sell copies
    of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be
    included in all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    DEALINGS IN THE SOFTWARE.

  \endverbatim
*/


#ifndef __TYPE_DEFINITION__
#define __TYPE_DEFINITION__

#include <algorithm>
#include <set>
#include <vector>

#include <ext/hash_set>

#if (ARRAY_DENSITY == SPARSE) || (ARRAY_DENSITY == ADAPTIVE) 
#  include "sparse_array_n.h"
#endif


#include "config.h"

#include "array.h"
#include "array_n.h"
#include "channel_image.h"
#include "color.h"
#include "geom.h"
#include "hash_tools.h"
#include "sorting_tools.h"



typedef unsigned int size_type;
typedef float        real_type;
// typedef double        real_type;

const size_type space_dimension = FEATURE_DIMENSION;
const size_type value_dimension = space_dimension + 1;


typedef int label_type;
const label_type NO_LABEL        = 0;
const label_type SADDLE_LABEL    = -1;

typedef std::vector<label_type> label_list_type;
typedef std::vector<size_type>  count_list_type;

typedef Array_2D<real_type>  gray_image_type;
typedef Array_3D<real_type>  gray_movie_type;

typedef Array_2D<label_type> label_image_type;
typedef Array_3D<label_type> label_movie_type;

typedef Array_2D<real_type>  density_image_type;
typedef Array_2D<bool>       bool_image_type;

typedef Geometry::Vec<3,real_type>           vector_color_type;
typedef Array_2D<vector_color_type>          vector_image_type;
typedef Array_3D<vector_color_type>          vector_movie_type;

typedef Geometry::Vec<R_DIMENSION,real_type> vector_texture_type;
typedef Array_2D<vector_texture_type>        vector_texture_image_type;

typedef RGB_color<real_type>     rgb_color_type; 
typedef Array_2D<rgb_color_type> rgb_image_type;
typedef Array_3D<rgb_color_type> rgb_movie_type;

typedef LAB_channel_image<real_type> lab_image_type;

#ifdef DENSITY_ONLY

typedef real_type SR_value_type;

#define DENSITY(x) x

#else

typedef Geometry::Vec<value_dimension,real_type> SR_value_type;

#define DENSITY(x) ((x)[value_dimension-1])

#endif


typedef int key_coef_type;
// typedef char key_coef_type;

#if ARRAY_DENSITY == DENSE
typedef Array_ND<space_dimension,SR_value_type> SR_domain_type;
typedef Array_ND<space_dimension,bool>          bool_SR_domain_type;
typedef Array_ND<space_dimension,unsigned int>  uint_SR_domain_type;
typedef Array_ND<space_dimension,int>           int_SR_domain_type;
typedef Array_ND<space_dimension,label_type>    label_SR_domain_type;
#endif


#if ARRAY_DENSITY == SPARSE
typedef Sparse_array_ND<space_dimension,SR_value_type,key_coef_type>  SR_domain_type;
typedef Sparse_array_ND<space_dimension,bool,key_coef_type> bool_SR_domain_type;
typedef Sparse_array_ND<space_dimension,unsigned int,key_coef_type> uint_SR_domain_type;
typedef Sparse_array_ND<space_dimension,int,key_coef_type> int_SR_domain_type;
typedef Sparse_array_ND<space_dimension,label_type,key_coef_type> label_SR_domain_type;
#endif


#if ARRAY_DENSITY == ADAPTIVE
template <typename T>
struct Adaptive_storage{
  typedef Array_ND<space_dimension,T> dense_type;
  typedef Sparse_array_ND<space_dimension,T,key_coef_type> sparse_type;
  dense_type*  dense;
  sparse_type* sparse;
};

typedef Adaptive_storage<SR_value_type> SR_domain_type;
typedef Adaptive_storage<bool>          bool_SR_domain_type;
typedef Adaptive_storage<unsigned int>  uint_SR_domain_type;
typedef Adaptive_storage<int>           int_SR_domain_type;
typedef Adaptive_storage<label_type>    label_SR_domain_type;
#endif

// typedef std::set<label_type> label_set_type;
typedef __gnu_cxx::hash_set<label_type> label_set_type;

typedef Geometry::Vec<space_dimension,real_type>     realN_type;
typedef Geometry::Vec<space_dimension,key_coef_type> intN_type;


typedef Sorting_tools::Labelled_data<real_type,intN_type> valued_index_type;
typedef std::vector<valued_index_type>                    valued_index_list_type;

typedef Sorting_tools::Labelled_data<real_type,label_type> valued_label_type;
typedef std::vector<valued_label_type>                     valued_label_list_type;

typedef std::vector<intN_type> index_list_type;



#ifdef USE_PCA_REDUCTION

typedef
Geometry::Matrix<FEATURE_DIMENSION,INPUT_FEATURE_DIMENSION,real_type>
pca_matrix_type;

typedef
Geometry::Matrix<INPUT_FEATURE_DIMENSION,FEATURE_DIMENSION,real_type>
back_pca_matrix_type;

typedef Geometry::Vec<INPUT_FEATURE_DIMENSION,real_type> input_feature_type;

#else

typedef realN_type input_feature_type;

#endif // END OF use_pca_reduction

typedef realN_type feature_type;

#ifdef IMAGE_MODE
typedef Array_2D<feature_type>       feature_array_type;
typedef Array_2D<input_feature_type> input_feature_array_type;
#endif

#ifdef MOVIE_MODE
typedef Array_3D<feature_type>       feature_array_type;
typedef Array_3D<input_feature_type> input_feature_array_type;
#endif



inline label_type get_label(const label_type       l,
			    const label_list_type& relabel){
  
  label_type res = l; 
  while(relabel[res] != res) res = relabel[res];
  return res;
}



struct cluster_type{
  label_type      label;
  intN_type       summit_index;
  real_type       summit_density;
  label_list_type neighbor;

  cluster_type(const label_type l = NO_LABEL,
	       const intN_type& i = intN_type(),
	       const real_type  d = 0)
    :label(l),summit_index(i),summit_density(d){}
  
  inline bool has_neighbor(const label_type& l,
			   const label_list_type& relabel) const{
	
    for(label_list_type::const_iterator n = neighbor.begin(),
	  n_end = neighbor.end();
	n != n_end;++n){
      
      if (get_label(*n,relabel) == l) return true;
    }
    return false;
  }
  
  inline bool operator<(const cluster_type& c) const{
    return summit_density < c.summit_density;
  }

  static inline bool are_neighbors(const cluster_type& c1,
				   const cluster_type& c2,
				   const label_list_type& relabel){
    return (c1.neighbor.size() < c2.neighbor.size()) ?
      c1.has_neighbor(c2.label,relabel) :
      c2.has_neighbor(c1.label,relabel);
  }
};

typedef std::vector<cluster_type> cluster_list_type;


#define KEEP_SADDLE_HISTORY

struct saddle_type {
  label_type major;
  label_type minor;

  SR_value_type value;
  real_type  persistence;

#ifdef KEEP_SADDLE_HISTORY
  label_type first_major;
  label_type first_minor;
#endif
  

  inline saddle_type(const cluster_type& c1,
		     const cluster_type& c2,
		     const SR_value_type& v){

    value = v;
    
    if (c1 < c2){
      major       = c2.label;
      minor       = c1.label;
      persistence = c1.summit_density - DENSITY(value);
    }
    else{
      major       = c1.label;
      minor       = c2.label;
      persistence = c2.summit_density - DENSITY(value);
    }  

#ifdef KEEP_SADDLE_HISTORY
    first_major = major;
    first_minor = minor;
#endif
  }

  inline bool operator<(const saddle_type& s) const{
    return persistence < s.persistence;
  }
  
};

typedef std::vector<saddle_type> saddle_list_type;




#if defined(GRAY_MODE)  && defined(IMAGE_MODE)
typedef gray_image_type input_data_type;
#endif

#if defined(COLOR_MODE) && defined(IMAGE_MODE)
typedef vector_image_type input_data_type;
#endif

#if defined(TEXTURE_MODE) && defined(IMAGE_MODE)
typedef vector_texture_image_type input_data_type;
#endif

#if defined(GRAY_MODE)  && defined(MOVIE_MODE)
typedef gray_movie_type input_data_type;
#endif

#if defined(COLOR_MODE) && defined(MOVIE_MODE)
typedef vector_movie_type input_data_type;
#endif




#ifdef IMAGE_MODE

typedef label_image_type output_label_type;
typedef rgb_image_type   rgb_data_type;

#define FOR_ALL_PIXELS \
  for(size_type x = 0,x_end = width; x < x_end;++x) \
  for(size_type y = 0,y_end = height;y < y_end;++y) 

    
#define PIXEL x,y
#define PREVIOUS_PIXEL x-1,y

#define SIZES width,height
    
#endif



    
#ifdef MOVIE_MODE
    
typedef label_movie_type output_label_type;
typedef rgb_movie_type   rgb_data_type;

#define FOR_ALL_PIXELS \
  for(size_type x = 0,x_end = width; x < x_end;++x) \
  for(size_type y = 0,y_end = height;y < y_end;++y) \
  for(size_type f = 0,f_end = depth; f < f_end;++f)


#define PIXEL x,y,f
#define PREVIOUS_PIXEL x-1,y,f

#define SIZES width,height,depth
 
#endif



#endif