cvlee.cpp.svn-base

来自「非结构化路识别」· SVN-BASE 代码 · 共 1,445 行 · 第 1/5 页

/*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*/

/* Reconstruction of contour skeleton */

#include "_cvaux.h"
#include <time.h>

#define CV_IMPL CV_EXTERN_C


#define NEXT_SEQ(seq,seq_first) ((seq) == (seq_first) ? seq->v_next : seq->h_next)
#define SIGN(x) ( x<0 ? -1:( x>0 ? 1:0 ) )

const float LEE_CONST_ZERO = 1e-6f;
const float LEE_CONST_DIFF_POINTS = 1e-2f;
const float LEE_CONST_ACCEPTABLE_ERROR = 1e-4f;

/****************************************************************************************\
*                                    Auxiliary struct definitions                                 *
\****************************************************************************************/

template<class T>
struct CvLeePoint
{
    T x,y;
};

typedef CvLeePoint<float> CvPointFloat;
typedef CvLeePoint<float> CvDirection;

struct CvVoronoiSiteInt;
struct CvVoronoiEdgeInt;
struct CvVoronoiNodeInt;
struct CvVoronoiParabolaInt;
struct CvVoronoiChainInt;
struct CvVoronoiHoleInt;

struct CvVoronoiDiagramInt
{
    CvSeq* SiteSeq;
    CvSeq* EdgeSeq;
    CvSeq* NodeSeq;
    CvSeq* ChainSeq;
    CvSeq* ParabolaSeq;
    CvSeq* DirectionSeq;
    CvSeq* HoleSeq;
    CvVoronoiSiteInt* reflex_site;
    CvVoronoiHoleInt* top_hole;
};

struct CvVoronoiStorageInt
{
    CvMemStorage* SiteStorage;
    CvMemStorage* EdgeStorage;
    CvMemStorage* NodeStorage;
    CvMemStorage* ChainStorage;
    CvMemStorage* ParabolaStorage;
    CvMemStorage* DirectionStorage;
    CvMemStorage* HoleStorage;
};

struct CvVoronoiNodeInt
{
    CvPointFloat  node;
    float         radius;
};

struct CvVoronoiSiteInt
{
    CvVoronoiNodeInt* node1;
    CvVoronoiNodeInt* node2;
    CvVoronoiEdgeInt* edge1;
    CvVoronoiEdgeInt* edge2;
    CvVoronoiSiteInt* next_site;
    CvVoronoiSiteInt* prev_site;
    CvDirection* direction;
};

struct CvVoronoiEdgeInt
{
    CvVoronoiNodeInt* node1;
    CvVoronoiNodeInt* node2;
    CvVoronoiSiteInt* site;
    CvVoronoiEdgeInt* next_edge;
    CvVoronoiEdgeInt* prev_edge;
    CvVoronoiEdgeInt* twin_edge;
    CvVoronoiParabolaInt* parabola;
    CvDirection*  direction;
};

struct CvVoronoiParabolaInt
{
    float map[6];
    float a;
    CvVoronoiNodeInt* focus;
    CvVoronoiSiteInt* directrice;
};

struct CvVoronoiChainInt
{
    CvVoronoiSiteInt * first_site;
    CvVoronoiSiteInt * last_site;
    CvVoronoiChainInt* next_chain;
};

struct CvVoronoiHoleInt
{
    CvSeq* SiteSeq;
    CvSeq* ChainSeq;
    CvVoronoiSiteInt* site_top;
    CvVoronoiSiteInt* site_nearest;
    CvVoronoiSiteInt* site_opposite;
    CvVoronoiNodeInt* node;
    CvVoronoiHoleInt* next_hole;
    bool error;
    float x_coord;
};

typedef CvVoronoiSiteInt* pCvVoronoiSite;
typedef CvVoronoiEdgeInt* pCvVoronoiEdge;
typedef CvVoronoiNodeInt* pCvVoronoiNode;
typedef CvVoronoiParabolaInt* pCvVoronoiParabola;
typedef CvVoronoiChainInt* pCvVoronoiChain;
typedef CvVoronoiHoleInt* pCvVoronoiHole;
typedef CvPointFloat* pCvPointFloat;
typedef CvDirection* pCvDirection; 

/****************************************************************************************\
*                                    Function definitions                                *
\****************************************************************************************/

/*F///////////////////////////////////////////////////////////////////////////////////////
//    Author:  Andrey Sobolev
//    Name:    _cvLee
//    Purpose: Compute Voronoi Diagram for one given polygon with holes
//    Context:
//    Parameters:
//      ContourSeq : in, vertices of polygon.
//      VoronoiDiagramInt : in&out, pointer to struct, which contains the 
//                       description of Voronoi Diagram.
//      VoronoiStorage: in, storage for Voronoi Diagram.
//      contour_type: in, type of vertices.
//                    The possible values are CV_LEE_INT,CV_LEE_FLOAT,CV_LEE_DOUBLE.
//      contour_orientation: in, orientation of polygons.
//                           = 1, if contour is left - oriented in left coordinat system
//                           =-1, if contour is left - oriented in right coordinat system
//      attempt_number: in, number of unsuccessful attemts made by program to compute 
//                          the Voronoi Diagram befor return the error
//
//    Returns: 1, if Voronoi Diagram was succesfully computed 
//             0, if some error occures
//F*/
OPENCVAPI int  _cvLee(CvSeq* ContourSeq,
                      CvVoronoiDiagramInt* pVoronoiDiagramInt,
                      CvMemStorage* VoronoiStorage,
                      CvLeeParameters contour_type,
                      int contour_orientation,
                      int attempt_number);

/*F///////////////////////////////////////////////////////////////////////////////////////
//    Author:  Andrey Sobolev
//    Name:    _cvConstuctSites
//    Purpose : Compute sites for given polygon with holes
//                     (site is an edge of polygon or a reflex vertex).
//    Context:
//    Parameters:
//            ContourSeq : in, vertices of polygon
//       pVoronoiDiagram : in, pointer to struct, which contains the 
//                          description of Voronoi Diagram
//           contour_type: in, type of vertices.  The possible values are 
//                          CV_LEE_INT,CV_LEE_FLOAT,CV_LEE_DOUBLE.
//    contour_orientation: in, orientation of polygons.
//                           = 1, if contour is left - oriented in left coordinat system
//                           =-1, if contour is left - oriented in right coordinat system
//     Return: 1, if sites were succesfully constructed 
//             0, if some error occures
//F*/
OPENCVAPI int _cvConstuctSites(CvSeq* ContourSeq,
                            CvVoronoiDiagramInt* pVoronoiDiagram,
                            CvLeeParameters contour_type,
                            int contour_orientation);

/*F///////////////////////////////////////////////////////////////////////////////////////
//    Author:  Andrey Sobolev
//    Name:    _cvConstructChains
//    Purpose : Compute chains for given polygon with holes.
//    Context:
//    Parameters:
//       pVoronoiDiagram : in, pointer to struct, which contains the 
//                          description of Voronoi Diagram
//     Return: 1, if chains were succesfully constructed 
//             0, if some error occures
//F*/
OPENCVAPI int _cvConstructChains(CvVoronoiDiagramInt* pVoronoiDiagram);

/*F///////////////////////////////////////////////////////////////////////////////////////
//    Author:  Andrey Sobolev
//    Name:    _cvConstructSkeleton
//    Purpose: Compute skeleton for given collection of sites, using Lee algorithm
//    Context:
//    Parameters:
//      VoronoiDiagram : in, pointer to struct, which contains the 
//                       description of Voronoi Diagram.
//    Returns: 1, if skeleton was succesfully computed 
//             0, if some error occures
//F*/
OPENCVAPI int _cvConstructSkeleton(CvVoronoiDiagramInt* pVoronoiDiagram);

/*F///////////////////////////////////////////////////////////////////////////////////////
//    Author:  Andrey Sobolev
//    Name:    _cvConstructSiteTree
//    Purpose: Construct tree of sites (by analogy with contour tree).
//    Context:
//    Parameters:
//      VoronoiDiagram : in, pointer to struct, which contains the 
//                       description of Voronoi Diagram.
//    Returns: 
//F*/
OPENCVAPI void _cvConstructSiteTree(CvVoronoiDiagramInt* pVoronoiDiagram);

/*F///////////////////////////////////////////////////////////////////////////////////////
//    Author:   Andrey Sobolev
//    Name:     _cvReleaseVoronoiStorage
//    Purpose : Function realease storages. 
//                  The storages are divided into two groups:
//                  SiteStorage, EdgeStorage, NodeStorage form the first group;
//                  ChainStorage,ParabolaStorage,DirectionStorage,HoleStorage form the second group.
//    Context:
//    Parameters:
//        pVoronoiStorage: in,
//        group1,group2: in, if group1<>0 then storages from first group released   
//                           if group2<>0 then storages from second group released
//    Return    :
//F*/
OPENCVAPI void _cvReleaseVoronoiStorage(CvVoronoiStorageInt* pVoronoiStorage, int group1, int group2);

/*F///////////////////////////////////////////////////////////////////////////////////////
//  Author:  Andrey Sobolev
//  Name:  _cvConvert
//  Purpose :  Function convert internal representation of VD (via 
//                  structs CvVoronoiSiteInt, CvVoronoiEdgeInt,CvVoronoiNodeInt) into 
//                  external representation of VD (via structs CvVoronoiSite2D, CvVoronoiEdge2D,
//                  CvVoronoiNode2D) 
//    Context:
//    Parameters:
//        VoronoiDiagram: in
//        VoronoiStorage: in
//        change_orientation: in, if = -1 then the convertion is accompanied with change 
//                            of orientation
//