asequence.cpp

微软的基于HMM的人脸识别原代码, 非常经典的说

/*M///////////////////////////////////////////////////////////////////////////////////////
//
//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
//
//  By downloading, copying, installing or using the software you agree to this license.
//  If you do not agree to this license, do not download, install,
//  copy or use the software.
//
//
//                        Intel License Agreement
//                For Open Source Computer Vision Library
//
// Copyright (C) 2000, Intel Corporation, all rights reserved.
// Third party copyrights are property of their respective owners.
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
//   * Redistribution's of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//
//   * Redistribution's in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//
//   * The name of Intel Corporation may not be used to endorse or promote products
//     derived from this software without specific prior written permission.
//
// This software is provided by the copyright holders and contributors "as is" and
// any express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are disclaimed.
// In no event shall the Intel Corporation or contributors be liable for any direct,
// indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused
// and on any theory of liability, whether in contract, strict liability,
// or tort (including negligence or otherwise) arising in any way out of
// the use of this software, even if advised of the possibility of such damage.
//
//M*/

#include "CvTest.h"

static char* struct_names[] = 
{
    "cvStartWriteSeq, cvEndWriteSeq, CV_WRITE_SEQ_ELEM, "
    "cvGetSeqElem, cvSeqElemIdx, "
    "cvStartReadSeq, CV_READ_SEQ_ELEM, "
    "cvSetSeqReaderPos, cvGetSeqReaderPos, "
    "cvSeqPush, cvSeqPop, "
    "cvSeqPushMulti, cvSeqPopMulti, "
    "cvSeqInsert, cvSeqRemove",
    "cvCreateSet, cvSetAdd, cvSetRemove, cvGetSetElem, cvClearSet",
    "cvCreateGraph, cvGraphAddVtx, cvGraphAddEdge, cvGraphRemoveVtx, "
    "cvGraphRemoveEdge, cvFindGraphEdge, cvClearGraph, cvCalcVertexDegree ",
    "cvSortSeq"
};

static char* test_desc = "Verifying results of operations on abstract data types";

static int adt_l = 0, adt_h = ATS_DIM(struct_names)-1;
static int max_struct_size = 0; 
static int storage_block_size = 0;
static int iters = 0;
static int struct_count = 0;
//static int elem_size = 0;
const int elem_size = 7;
typedef struct elem_type
{
    char a[elem_size];
}
elem_type;

static int init_data_struct_params = 0;

static const char* ok_message = "No errors";

#define SEQUENCE_TEST     0
#define SET_TEST          1
#define GRAPH_TEST        2

static void read_data_struct_params( void )
{
    if( !init_data_struct_params )
    {
        int adt;
        
        trsCaseRead( &adt, "/a/seq/set/gr", "a",
                     "Structures to test: \n"
                     "a - all\n"
                     "seq - Sequences\n"
                     "set - Set\n"
                     "gr  - Graph\n" );
        if( adt != 0 ) adt_l = adt_h = adt - 1;

        trsiRead( &struct_count, "2", "number of structures" );
        trsiRead( &max_struct_size, "2000", "maximal number of elements in the struct" );
        //trsiRead( &elem_size, "7", "size of element" );
        trsiRead( &iters, "10", "number of iterations");
        trsiRead( &storage_block_size, "104", "size of storage blocks (bytes)" );

        init_data_struct_params = 1;
    }
}


/****************************************************************************************\
*                          implementation of array sequence                              *
\****************************************************************************************/

typedef  struct  _simple_seq
{
    char* array;
    int   count;
    int   max_count;
    int   elem_size;
}
simple_seq;


simple_seq*  create_simple_seq( int max_count, int elem_size )
{
    simple_seq* seq = (simple_seq*)icvAlloc( sizeof(*seq) + max_count * elem_size);
    seq->elem_size = elem_size;
    seq->max_count = max_count;
    seq->count = 0;
    seq->array = (char*)(seq + 1);
    return seq;
}

void release_simple_seq( simple_seq** seq )
{
    icvFree( seq );
}


char*  simple_seq_elem( simple_seq* seq, int index )
{
    assert( 0 <= index && index < seq->count );
    return seq->array + index * seq->elem_size;
}


void  push_simple_seq_elem( simple_seq* seq, void* elem )
{
    assert( seq->count < seq->max_count );
    memcpy( seq->array + seq->count * seq->elem_size, elem, seq->elem_size );
    seq->count++;
}


void  drop_simple_seq_elem( simple_seq* seq )
{
    assert( seq->count > 0 );
    seq->count--;
}


void  clear_simple_seq( simple_seq* seq )
{
    seq->count = 0;
}


void  remove_simple_seq_elem( simple_seq* seq, int index )
{
    int elem_size = seq->elem_size;
    assert( seq->count > index );
    
    memmove( seq->array + index*elem_size, seq->array + (index + 1)*elem_size,
             (seq->count - index - 1) * elem_size );
    seq->count--;
}


void  insert_simple_seq_elem( simple_seq* seq, int index, void* elem )
{
    int elem_size = seq->elem_size;
    assert( seq->count < seq->max_count );
    
    memmove( seq->array + (index + 1)*elem_size, seq->array + index * elem_size,
             (seq->count - index) * elem_size );
    memcpy( seq->array + index * elem_size, elem, elem_size );
    
    seq->count++;
}


/****************************************************************************************\
*                            implementation of simple set                                *
\****************************************************************************************/

typedef  struct  _simple_set
{
    char* array;
    int   count;
    int   max_count;
    int   elem_size;
    int*  free_stack;
    int   free_count;
}
simple_set;


void  clear_simple_set( simple_set* set )
{
    int i;
    int elem_size = set->elem_size;
    set->count = 0;

    for( i = 0; i < set->max_count; i++ )
    {
        set->array[i*elem_size] = 0;
        set->free_stack[i] = set->max_count - i - 1;
    }
    set->free_count = set->max_count;
}


simple_set*  create_simple_set( int max_count, int elem_size )
{
    simple_set* set = (simple_set*)icvAlloc( sizeof(*set) + max_count *
                                        (elem_size + 1 + sizeof(int)));
    set->elem_size = elem_size + 1;
    set->max_count = max_count;
    set->array = (char*)(set + 1);
    set->free_stack = (int*)(set->array + max_count * set->elem_size);

    clear_simple_set( set );
    return set;
}

void release_simple_set( simple_set** set )
{
    icvFree( set );
}


char*  find_simple_set_elem( simple_set* set, int index )
{
    int idx = index * set->elem_size;
    assert( 0 <= index && index < set->max_count );
    return set->array[idx] ? set->array + idx + 1 : 0;
}


int  add_simple_set_elem( simple_set* set, void* elem )
{
    int idx, idx2;
    assert( set->free_count > 0 );

    idx = set->free_stack[--set->free_count];
    idx2 = idx * set->elem_size;
    assert( set->array[idx2] == 0 );
    set->array[idx2] = 1;
    memcpy( set->array + idx2 + 1, elem, set->elem_size - 1 );
    
    if( idx >= set->count ) set->count = idx + 1;
    return idx;
}


void  remove_simple_set_elem( simple_set* set, int index )
{
    assert( set->free_count < set->max_count &&
            0 <= index && index < set->max_count );
    assert( set->array[index * set->elem_size] == 1 );

    set->free_stack[set->free_count++] = index;
    set->array[index * set->elem_size] = 0;
}


/****************************************************************************************\
*                              implementation of simple graph                            *
\****************************************************************************************/

typedef  struct  _simple_graph
{
    char* matrix;
    int   elem_size;
    int   oriented;
    simple_set* vtx;
}
simple_graph;


void  clear_simple_graph( simple_graph* graph )
{
    int max_vtx_count = graph->vtx->max_count;
    clear_simple_set( graph->vtx );
    memset( graph->matrix, 0, max_vtx_count * max_vtx_count * graph->elem_size );
}


simple_graph*  create_simple_graph( int max_vtx_count, int vtx_size,
                                    int edge_size, int oriented )
{
    simple_graph* graph;

    assert( max_vtx_count > 1 && vtx_size > 0 && edge_size > 0 );
    graph = (simple_graph*)icvAlloc( sizeof(*graph) +
                  max_vtx_count * max_vtx_count * (edge_size + 1));
    graph->vtx = create_simple_set( max_vtx_count, vtx_size );
    graph->elem_size = edge_size + 1;
    graph->matrix = (char*)(graph + 1);
    graph->oriented = oriented;

    clear_simple_graph( graph );
    return graph;
}


void release_simple_graph( simple_graph** graph )
{
    release_simple_set( &(graph[0]->vtx) );
    icvFree( graph );
}


int  add_simple_graph_vertex( simple_graph* graph, void* vertex )
{
    return add_simple_set_elem( graph->vtx, vertex );
}


void  remove_simple_graph_vertex( simple_graph* graph, int index )
{
    int i, max_vtx_count = graph->vtx->max_count;
    int elem_size = graph->elem_size;
    remove_simple_set_elem( graph->vtx, index );

    /* remove all the corresponding edges */
    for( i = 0; i < max_vtx_count; i++ )
    {
        graph->matrix[(i*max_vtx_count + index)*elem_size] = 
        graph->matrix[(index*max_vtx_count + i)*elem_size] = 0;
    }
}


void  add_simple_graph_edge( simple_graph* graph, int idx1, int idx2, void* edge )
{
    assert( find_simple_set_elem( graph->vtx, idx1 ) &&
            find_simple_set_elem( graph->vtx, idx2 ));

    if( graph->oriented )
    {
        int ofs = (idx1*graph->vtx->max_count + idx2)*graph->elem_size;
        assert( graph->matrix[ofs] == 0 );
        graph->matrix[ofs] = 1;
        memcpy( graph->matrix + ofs + 1, edge, graph->elem_size - 1 );
    }
    else
    {
        graph->oriented = 1;
        add_simple_graph_edge( graph, idx1, idx2, edge );
        add_simple_graph_edge( graph, idx2, idx1, edge );
        graph->oriented = 0;
    }
}


void  remove_simple_graph_edge( simple_graph* graph, int idx1, int idx2 )
{
    assert( find_simple_set_elem( graph->vtx, idx1 ) &&
            find_simple_set_elem( graph->vtx, idx2 ));

    if( graph->oriented )
    {
        int ofs = (idx1*graph->vtx->max_count + idx2)*graph->elem_size;
        assert( graph->matrix[ofs] == 1 );
        graph->matrix[ofs] = 0;
    }
    else
    {
        graph->oriented = 1;
        remove_simple_graph_edge( graph, idx1, idx2 );
        remove_simple_graph_edge( graph, idx2, idx1 );
        graph->oriented = 0;
    }
}


char*  find_simple_graph_vertex( simple_graph* graph, int index )
{
    return find_simple_set_elem( graph->vtx, index );
}


char*  find_simple_graph_edge( simple_graph* graph, int idx1, int idx2 )
{
    if( find_simple_graph_vertex( graph, idx1 ) &&
        find_simple_graph_vertex( graph, idx2 ))
    {
        char* edge = graph->matrix + (idx1 * graph->vtx->max_count + idx2)*graph->elem_size;
        if( edge[0] ) return edge + 1;
    }
    return 0;
}


int  calc_simple_graph_vertex_degree( simple_graph* graph, int index )
{
    int i, count = 0;
    int elem_size = graph->elem_size;
    int max_vtx_count = graph->vtx->max_count;
    assert( find_simple_graph_vertex( graph, index ) != 0 );
    
    for( i = 0; i < max_vtx_count; i++ )
    {
        count += graph->matrix[(i*max_vtx_count + index)*elem_size] + 
                 graph->matrix[(index*max_vtx_count + i)*elem_size];
    }

    if( !(graph->oriented))
    {
        assert( count % 2 == 0 );
        count /= 2;
    }
    return count;
}

/*********************** tests ****************************/

/*#define DO_CV_ACTION( func_name, args )            \
    result = func_name args;                         \
    if( result < 0 )                                 \
    {                                                \
        message_string = #func_name " fails";        \
        goto test_exit;                              \
    }*/

#define DO_CV_ACTION( func_name, args ) { func_name args; }


#define CHECK_CONDITION( expr, msg )   \
    if( !(expr) )                      \
    {                                  \
        message_string = (msg);        \
        code = TRS_FAIL;               \
        goto test_exit;                \
    }


static int check_seq_block_consistence( CvSeq* seq, int total, const char** msg )
{
    int sum = 0, code = TRS_OK;
    const char* message_string = *msg;

    CHECK_CONDITION( seq, "Null sequence pointer" );