cvaux.hpp

用OpenCV编写的人脸识别代码

                    if( nodeB->link[node_type::right] != 0 )
                        nodeB->link[node_type::right]->link[node_type::up] = nodeB;
                    nodeC->link[node_type::right] = nodeA;
                    nodeC->link[node_type::left] = nodeB;
                    nodeA->link[node_type::up] = nodeB->link[node_type::up] = nodeC;
                    nodeA->balance = 2 - (idx < nodeC->idx);
                    nodeB->balance = (idx <= nodeC->idx) << 1;
                    nodeC->balance = node_type::center;
                    if( nodeC->link[node_type::up] != 0 )
                        nodeC->link[node_type::up]->
                        link[idx > nodeC->link[node_type::up]->idx] = nodeC;
                    else root = nodeC;
                    return node;
                default:
                    assert( 0 );
                    return node;
                } /* switch */
            } /* if( idx > nodeA->idx ) */
        case node_type::center:
            nodeA->balance = idx > nodeA->idx;
            break;
        case node_type::right:
            if( idx < nodeA->idx )
            {
                nodeA->balance = node_type::center;
                return node;
            }
            else /* idx > nodeA->idx */
            {
                nodeB = nodeA->link[node_type::right];
                switch( nodeB->balance )
                {
                case node_type::right:
                    nodeA->link[node_type::right] = nodeB->link[node_type::left];
                    if( nodeA->link[node_type::right] != 0 )
                        nodeA->link[node_type::right]->link[node_type::up] = nodeA;
                    nodeB->link[node_type::left] = nodeA;
                    nodeB->link[node_type::up] = nodeA->link[node_type::up];
                    nodeA->link[node_type::up] = nodeB;
                    nodeA->balance = nodeB->balance = node_type::center;
                    if( nodeB->link[node_type::up] != 0 )
                        nodeB->link[node_type::up]->
                        link[idx > nodeB->link[node_type::up]->idx] = nodeB;
                    else root = nodeB;
                    return node;
                case node_type::left:
                    nodeC = nodeB->link[node_type::left];
                    nodeC->link[node_type::up] = nodeA->link[node_type::up];
                    nodeA->link[node_type::right] = nodeC->link[node_type::left];
                    if( nodeA->link[node_type::right] != 0 )
                        nodeA->link[node_type::right]->link[node_type::up] = nodeA;
                    nodeB->link[node_type::left] = nodeC->link[node_type::right];
                    if( nodeB->link[node_type::left] != 0 )
                        nodeB->link[node_type::left]->link[node_type::up] = nodeB;
                    nodeC->link[node_type::left] = nodeA;
                    nodeC->link[node_type::right] = nodeB;
                    nodeA->link[node_type::up] = nodeB->link[node_type::up] = nodeC;
                    nodeA->balance = (idx <= nodeC->idx) << 1;
                    nodeB->balance = 2 - (idx < nodeC->idx);
                    nodeC->balance = node_type::center;
                    if( nodeC->link[node_type::up] != 0 )
                        nodeC->link[node_type::up]->
                        link[idx > nodeC->link[node_type::up]->idx] = nodeC;
                    else root = nodeC;
                    return node;
                default:
                    assert( 0 );
                    return node;
                } /* switch */
            } /* if( idx < nodeA->idx ) */
        } /* switch */
    }while( (nodeA = nodeA->link[node_type::up]) != 0 );
    return node;
} /* CvTree<Val, Idx>::create_node */


template <class Val, class Idx> CvTree<Val, Idx>::value_type
                        CvTree<Val, Idx>::query( CvTree<Val, Idx>::idx_type idx ) const
{
    assert( size == 0 || idx < size );
    node_type* node = root;
    while( node != 0 )
    {
        if( node->idx == idx ) return node->val;
        node = node->link[idx > node->idx];
    }
    return 0;
}


template <class Val, class Idx> void CvTree<Val, Idx>::remove( idx_type idx )
{
    assert( size == 0 || idx < size );

    node_type* nodeA = root;
    node_type* nodeB;
    node_type* nodeC;

    /* Find node to be removed */
    while( nodeA != 0 && nodeA->idx != idx ) nodeA = nodeA->link[idx > nodeA->idx];

    /* If node not found return */
    if( nodeA == 0 ) return;

    /* Find node to be placed on deleted node */
    switch( nodeA->balance )
    {
    case node_type::left:
        /* Find top right node */
        assert( nodeA->link[node_type::left] != 0 );
        nodeB = nodeA->link[node_type::left];
        while( nodeB->link[node_type::right] != 0 ) nodeB = nodeB->link[node_type::right];
        break;
    case node_type::right:
        /* Find top left node */
        assert( nodeA->link[node_type::right] != 0 );
        nodeB = nodeA->link[node_type::right];
        while( nodeB->link[node_type::left] != 0 ) nodeB = nodeB->link[node_type::left];
        break;
    case node_type::center:
        /* Is this node terminal ? */
        assert( !((nodeA->link[node_type::left] != 0) ^
                  (nodeA->link[node_type::right] != 0)) );
        if( nodeA->link[node_type::right] != 0 ) /* non terminal node */
        {
            /* Select left branch & find top right node*/
            nodeB = nodeA->link[node_type::left];
            while( nodeB->link[node_type::right] != 0 )
                nodeB = nodeB->link[node_type::right];
        }
        else nodeB = nodeA; /* terminal node */
        break;
    default:
        assert( 0 );
        return;
    }

    /* Copying nodeB to nodeA (replacing node) */
    if( nodeB->link[node_type::up] != 0 )
    {
        nodeB->link[node_type::up]->link[nodeB->idx>nodeB->link[node_type::up]->idx] = 
            nodeB->link[nodeA->balance == node_type::right];
        if( nodeB->link[nodeA->balance == node_type::right] != 0 )
            nodeB->link[nodeA->balance == node_type::right]->link[node_type::up] =
            nodeB->link[node_type::up];
    }
    else /* Deleted node is root node and last */
    {
        root = 0;
        manager.release_node( nodeB );
        return;
    }
    nodeA->idx = nodeB->idx;
    nodeA->val = nodeB->val;
    nodeA = nodeB->link[node_type::up];
    idx = nodeB->idx;
    manager.release_node( nodeB );

    /* Balancing tree :(E3) */
    do{
        switch( nodeA->balance )
        {
        case node_type::left:
            if( idx <= nodeA->idx )
            {
                nodeA->balance = node_type::center;
                break;
            }
            else
            {
                nodeB = nodeA->link[node_type::left];
                switch( nodeB->balance )
                {
                case node_type::left:
                case node_type::center:
                    nodeA->link[node_type::left] = nodeB->link[node_type::right];
                    if( nodeA->link[node_type::left] != 0 )
                        nodeA->link[node_type::left]->link[node_type::up] = nodeA;
                    nodeB->link[node_type::right] = nodeA;
                    nodeB->link[node_type::up] = nodeA->link[node_type::up];
                    nodeA->link[node_type::up] = nodeB;
                    nodeA->balance = 2 - nodeB->balance;
                    nodeB->balance = 2 - (nodeB->balance == node_type::center);
                    if( nodeB->link[node_type::up] != 0 )
                        nodeB->link[node_type::up]->
                        link[nodeB->idx > nodeB->link[node_type::up]->idx] = nodeB;
                    else root = nodeB;
                    nodeA = nodeB;
                    continue;
                case node_type::right:
                    nodeC = nodeB->link[node_type::right];
                    nodeC->link[node_type::up] = nodeA->link[node_type::up];
                    nodeA->link[node_type::left] = nodeC->link[node_type::right];
                    if( nodeA->link[node_type::left] != 0 )
                        nodeA->link[node_type::left]->link[node_type::up] = nodeA;
                    nodeB->link[node_type::right] = nodeC->link[node_type::left];
                    if( nodeB->link[node_type::right] != 0 )
                        nodeB->link[node_type::right]->link[node_type::up] = nodeB;
                    nodeC->link[node_type::right] = nodeA;
                    nodeC->link[node_type::left] = nodeB;
                    nodeA->link[node_type::up] = nodeB->link[node_type::up] = nodeC;
                    nodeA->balance = (nodeC->balance != node_type::left) + 1;
                    nodeB->balance = (nodeC->balance != node_type::right) << 1;
                    nodeC->balance = node_type::center;
                    if( nodeC->link[node_type::up] != 0 )
                        nodeC->link[node_type::up]->
                        link[idx > nodeC->link[node_type::up]->idx] = nodeC;
                    else root = nodeC;
                    nodeA = nodeC;
                    continue;
                default:
                    assert( 0 );
                    return;
                } /* switch( nodeB->balance ) */
            } /* else */
            break;
        case node_type::right:
            if( idx >= nodeA->idx )
            {
                nodeA->balance = node_type::center;
                break;
            }
            else /* idx > nodeA->idx */
            {
                nodeB = nodeA->link[node_type::right];
                switch( nodeB->balance )
                {
                case node_type::right:
                case node_type::center:
                    nodeA->link[node_type::right] = nodeB->link[node_type::left];
                    if( nodeA->link[node_type::right] != 0 )
                        nodeA->link[node_type::right]->link[node_type::up] = nodeA;
                    nodeB->link[node_type::left] = nodeA;
                    nodeB->link[node_type::up] = nodeA->link[node_type::up];
                    nodeA->link[node_type::up] = nodeB;
                    nodeA->balance = 2 - (nodeB->balance == node_type::center);
                    nodeB->balance = (nodeB->balance == node_type::right) << 1;
                    if( nodeB->link[node_type::up] != 0 )
                        nodeB->link[node_type::up]->
                        link[idx >= nodeB->link[node_type::up]->idx] = nodeB;
                    else root = nodeB;
                    nodeA = nodeB;
                    continue;
                case node_type::left:
                    nodeC = nodeB->link[node_type::left];
                    nodeC->link[node_type::up] = nodeA->link[node_type::up];
                    nodeA->link[node_type::right] = nodeC->link[node_type::left];
                    if( nodeA->link[node_type::right] != 0 )
                        nodeA->link[node_type::right]->link[node_type::up] = nodeA;
                    nodeB->link[node_type::left] = nodeC->link[node_type::right];
                    if( nodeB->link[node_type::left] != 0 )
                        nodeB->link[node_type::left]->link[node_type::up] = nodeB;
                    nodeC->link[node_type::left] = nodeA;
                    nodeC->link[node_type::right] = nodeB;
                    nodeA->link[node_type::up] = nodeB->link[node_type::up] = nodeC;
                    nodeA->balance = (nodeC->balance != node_type::right) << 1;
                    nodeB->balance = (nodeC->balance != node_type::left) + 1;
                    nodeC->balance = node_type::center;
                    if( nodeC->link[node_type::up] != 0 )
                        nodeC->link[node_type::up]->
                        link[idx >= nodeC->link[node_type::up]->idx] = nodeC;
                    else root = nodeC;
                    nodeA = nodeC;
                    continue;
                default:
                    assert( 0 );
                    return;
                } /* switch( nodeB->balance ) */
                break;
            }
        case node_type::center:
            nodeA->balance = idx <= nodeA->idx;
            break;
        } /* switch( nodeA->balance ) */
    }while( idx = nodeA->idx, nodeA->balance == node_type::center &&
           (nodeA = nodeA->link[node_type::up]) != 0 );
}


template <class Val, class Idx> CvTree<Val, Idx>::iterator
                                CvTree<Val, Idx>::begin() const
{
    node_type* node = root;
    if( node == 0 ) return CvTreeIterator<node_type>( node );
    while( node->link[node_type::left] != 0 ) node = node->link[node_type::left];
    return CvTreeIterator<node_type>( node );
}


template <class Val, class Idx> CvTree<Val, Idx>::iterator
                                CvTree<Val, Idx>::end() const
{
    node_type* node = root;
    if( node == 0 ) return CvTreeIterator<node_type>( node );
    while( node->link[node_type::right] != 0 ) node = node->link[node_type::right];
    return CvTreeIterator<node_type>( node );
}


template <class Val, class Idx> CvTree<Val, Idx>::storage&
                                CvTree<Val, Idx>::operator =( const storage& another )
{
    clear();
    if( another.get_root() == 0 ) return *this;

    iterator iter = another.begin();
    iterator end = another.end();

    while( iter != end )
    {
        (*this)[iter.get_idx()] = *iter;
        iter++;
    }
    (*this)[iter.get_idx()] = *iter;

    return *this;
}


/****************************************************************************************\
*                                CvNodeIterator implementation                          *
\****************************************************************************************/
template <class Node> CvNodeIterator<Node>::iterator& CvNodeIterator<Node>::operator++()
{
    if( idx < block_type::block_nodes - 1 ) idx++;
    else if( current_block->next != 0 )
    {
        current_block = current_block->next;
        idx = 0;
    }
    return *this;
}


template <class Node> const CvNodeIterator<Node>::iterator
                            CvNodeIterator<Node>::operator++(int)
{
    iterator temp = *this;
    if( idx < block_type::block_nodes - 1 ) idx++;
    else if( current_block->next != 0 )
    {
        current_block = current_block->next;
        idx = 0;
    }
    return temp;
}


/****************************************************************************************\
*                                CvTreeIterator implementation                            *
\****************************************************************************************/
template <class Node> CvTreeIterator<Node>::node_type* CvTreeIterator<Node>::next()
{
    node_type* temp;

    if( node->link[node_type::right] != 0 )
    {
        temp = node->link[node_type::right];
        while( temp->link[node_type::left] != 0 ) temp = temp->link[node_type::left];
        return node = temp;
    }

    temp = node;

    while( temp->link[node_type::up] != 0 )
    {
        if( temp->idx < temp->link[node_type::up]->idx ) break;
        temp = temp->link[node_type::up];
    }

    if( temp->link[node_type::up] == 0 ) return node;

    node = temp->link[node_type::up];
    return node;
}


template <class Node> CvTreeIterator<Node>::iterator
                      CvTreeIterator<Node>::operator++()
{
    next();
    return *this;
}


template <class Node> CvTreeIterator<Node>::iterator
                      CvTreeIterator<Node>::operator++(int)
{
    iterator temp = *this;
    next();
    return temp;
}


/****************************************************************************************\
*                                  CVHistogram imlpementation                           *
\****************************************************************************************/
template <class Storage> void
                      CVHistogram<Storage>::create( int bins0, int bins1, int bins2,
                                                     int bins3, int bins4, int bins5 )