• Open Source Computer Vision Library

Cxcore动态结构

Wikipedia,自由的百科全书

目录

内存存储(memory storage)

CvMemStorage

Growing memory storage

typedef struct CvMemStorage
{
    int signature;
    struct CvMemBlock* bottom;/* first allocated block */
    struct CvMemBlock* top; /* the current memory block - top of the stack */
    struct CvMemStorage* parent; /* borrows new blocks from */
    int block_size; /* block size */
    int free_space; /* free space in the top block (in bytes) */
} CvMemStorage;

内存存储器是一个可用来存储诸如序列,轮廓,图形,子划分等动态增长数据结构的底层结构。它是由一系列以同等大小的内存块构成,呈列表型 ---bottom 域指的是列首,top 域指的是当前指向的块但未必是列尾.在bottom和top之间所有的块(包括bottom, 不包括top)被完全占据了空间;在 top和列尾之间所有的块(包括块尾,不包括top)则是空的;而top块本身则被占据了部分空间 -- free_space 指的是top块剩余的空字节数。

新分配的内存缓冲区(或显式的通过 cvMemStorageAlloc 函数分配,或隐式的通过 cvSeqPush, cvGraphAddEdge等高级函数分配)总是起始于当前块(即top块)的剩余那部分,如果剩余那部分能满足要求(够分配的大小)。分配后,free_space 就减少了新分配的那部分内存大小,外加一些用来保存适当列型的附加大小。当top块的剩余空间无法满足被分配的块(缓冲区)大小时,top块的下一个存储块被置为当前块(新的top块) -- free_space 被置为先前分配的整个块的大小。

如果已经不存在空的存储块(即:top块已是列尾),则必须再分配一个新的块(或从parent那继承,见 cvCreateChildMemStorage)并将该块加到列尾上去。于是,存储器(memory storage)就如同栈(Stack)那样, bottom指向栈底,(top, free_space)对指向栈顶。栈顶可通过 cvSaveMemStoragePos保存,通过 cvRestoreMemStoragePos 恢复指向, 通过 cvClearStorage 重置。

CvMemBlock

内存存储块结构

typedef struct CvMemBlock
{
	struct CvMemBlock* prev;
	struct CvMemBlock* next;
} CvMemBlock;

CvMemBlock 代表一个单独的内存存储块结构。 内存存储块中的实际数据存储在 header块 之后(即:存在一个头指针 head 指向的块 header ,该块不存储数据),于是,内存块的第 i 个字节可以通过表达式 ((char*)(mem_block_ptr+1))[i] 获得。然而,通常没必要直接去获得存储结构的域。

CvMemStoragePos

内存存储块地址

typedef struct CvMemStoragePos
{
    CvMemBlock* top;
    int free_space;
} CvMemStoragePos;

该结构(如以下所说)保存栈顶的地址,栈顶可以通过 cvSaveMemStoragePos 保存,也可以通过 cvRestoreMemStoragePos 恢复。

CreateMemStorage

创建内存块

CvMemStorage* cvCreateMemStorage( int block_size=0 );
block_size 
存储块的大小以字节表示。如果大小是 0 byte, 则将该块设置成默认值 -- 当前默认大小为64k.

函数 cvCreateMemStorage 创建一内存块并返回指向块首的指针。起初,存储块是空的。头部(即:header)的所有域值都为 0,除了 block_size 外.

CreateChildMemStorage

创建子内存块

CvMemStorage* cvCreateChildMemStorage( CvMemStorage* parent );
parent 
父内存块

函数 cvCreateChildMemStorage 创建一类似于普通内存块的子内存块,除了内存分配/释放机制不同外。当一个子存储块需要一个新的块加入时,它就试图从parent 那得到这样一个块。如果 parent 中 还未被占据空间的那些块中的第一个块是可获得的,就获取第一个块(依此类推),再将该块从 parent 那里去除。如果不存在这样的块,则 parent 要么分配一个,要么从它自己 parent (即:parent 的 parent) 那借个过来。换句话说,完全有可能形成一个链或更为复杂的结构,其中的内存存储块互为 child/ parent 关系(父子关系)。当子存储结构被释放或清除,它就把所有的块还给各自的 parent. 在其他方面,子存储结构同普通存储结构一样。

子存储结构在下列情况中是非常有用的。想象一下,如果用户需要处理存储在某个块中的动态数据,再将处理的结果存放在该块中。在使用了最简单的方法处理后,临时数据作为输入和输出数据被存放在了同一个存储块中,于是该存储块看上去就类似下面处理后的样子: Dynamic data processing without using child storage.

结果,在存储块中,出现了垃圾(临时数据)。然而,如果在开始处理数据前就先建立一个子存储块,将临时数据写入子存储块中并在最后释放子存储块,那么最终在 源/目的存储块 (source / destination storage) 中就不会出现垃圾, 于是该存储块看上去应该是如下形式:Dynamic data processing using a child storage.

ReleaseMemStorage

释放内存块

void cvReleaseMemStorage( CvMemStorage** storage );
storage 
指向被释放了的存储块的指针

函数 cvReleaseMemStorage 释放所有的存储(内存)块 或者 将它们返回给各自的 parent(如果需要的话)。 接下来再释放 header块(即:释放头指针 head 指向的块 = free(head))并清除指向该块的指针(即:head = NULL)。在释放作为 parent 的块之前,先清除各自的 child 块。

ClearMemStorage

清空内存存储块

void cvClearMemStorage( CvMemStorage* storage );
storage 
存储存储块

函数 cvClearMemStorage 将存储块的 top 置到存储块的头部(注:清空存储块中的存储内容)。该函数并不释放内存(仅清空内存)。假使该内存块有一个父内存块(即:存在一内存块与其有父子关系),则函数就将所有的块返回给其 parent.

MemStorageAlloc

在存储块中分配一内存缓冲区

void* cvMemStorageAlloc( CvMemStorage* storage, size_t size );
storage 
内存块.
size 
缓冲区的大小.

函数 cvMemStorageAlloc 在存储块中分配一内存缓冲区。该缓冲区的大小不能超过内存块的大小,否则就会导致运行时错误。缓冲区的地址被调整为CV_STRUCT_ALIGN 字节 (当前为 sizeof(double)).

MemStorageAllocString

在存储块中分配一文本字符串

typedef struct CvString
{
    int len;
    char* ptr;
}
CvString;

CvString cvMemStorageAllocString( CvMemStorage* storage, const char* ptr, int len=-1 );
storage 
存储块
ptr 
字符串
len 
字符串的长度(不计算‘\0’)。如果参数为负数,函数就计算该字符串的长度。

函数 cvMemStorageAlloString 在存储块中创建了一字符串的拷贝。它返回一结构,该结构包含字符串的长度(该长度或通过用户传递,或通过计算得到)和指向被拷贝了的字符串的指针。

SaveMemStoragePos

保存内存块的位置(地址)

void cvSaveMemStoragePos( const CvMemStorage* storage, CvMemStoragePos* pos );
storage 
内存块.
pos 
内存块顶部位置。

函数 cvSaveMemStoragePos 将存储块的当前位置保存到参数 pos 中。 函数 cvRestoreMemStoragePos 可进一步获取该位置(地址)。

RestoreMemStoragePos

恢复内存存储块的位置

void cvRestoreMemStoragePos( CvMemStorage* storage, CvMemStoragePos* pos );
storage 
内存块.
pos 
新的存储块的位置

函数 cvRestoreMemStoragePos 通过参数 pos 恢复内存块的位置。该函数和函数 cvClearMemStorage 是释放被占用内存块的唯一方法。注意:没有什么方法可去释放存储块中被占用的部分内存。

序列

CvSeq

可动态增长元素序列(OpenCV_1.0已发生改变,详见cxtypes.h) Growable sequence of elements

#define CV_SEQUENCE_FIELDS() \
    int flags; /* micsellaneous flags */ \
    int header_size; /* size of sequence header */ \
    struct CvSeq* h_prev; /* previous sequence */ \
    struct CvSeq* h_next; /* next sequence */ \
    struct CvSeq* v_prev; /* 2nd previous sequence */ \
    struct CvSeq* v_next; /* 2nd next sequence */ \
    int total; /* total number of elements */ \
    int elem_size;/* size of sequence element in bytes */ \
    char* block_max;/* maximal bound of the last block */ \
    char* ptr; /* current write pointer */ \
    int delta_elems; /* how many elements allocated when the sequence grows (sequence granularity) */ \
    CvMemStorage* storage; /* where the seq is stored */ \
    CvSeqBlock* free_blocks; /* free blocks list */ \
    CvSeqBlock* first; /* pointer to the first sequence block */


typedef struct CvSeq
{
    CV_SEQUENCE_FIELDS()
} CvSeq;

结构CvSeq是所有OpenCV动态数据结构的基础。 在1.0版本中,将前六个成员剥离出来定义成一个宏. 通过不同寻常的宏定义简化了带有附加参数的结构 CvSeq 的扩展。为了扩展 CvSeq, 用户可以定义一新的数据结构或在通过宏CV_SEQUENCE_FIELDS()所包括的 CvSeq 的域后在放入用户自定义的域。

有两种类型的序列 -- 稠密序列和稀疏序列。稠密序列都派生自 CvSeq, 它们用来代表可扩展的一维数组 -- 向量,栈,队列,双端队列。数据间不存在空隙(即:连续存放)-- 如果元素从序列中间被删除或插入新的元素到序列中(不是两端),那么此元素后边的相关元素会被移动。稀疏序列都派生自 CvSet,后面会有详细的讨论。它们都是由节点所组成的序列,每一个节点要么被占用空间要么是空,由 flag 标志指定。这些序列作为无序的数据结构而被使用,如点集,图,哈希表等。

域 header_size(结构的大小) 含有序列头部节点的实际大小,此大小大于或等于 sizeof(CvSeq).当这个宏用在序列中时,应该等于 sizeof(CvSeq),若这个宏用在其他结构中,如CvContour,结构的大小应该大于sizeof(CvSeq); 域 h_prev, h_next, v_prev, v_next 可用来创建不同序列的层次结构。域 h_prev, h_next 指向同一层次结构前一个和后一个序列,而域 v_prev, v_next指向在垂直方向上的前一个和后一个序列,即:父亲和子孙。

域 first 指向第一个序列快,块结构在后面描述。

域 total 包含稠密序列的总元素数和稀疏序列被分配的节点数。

域 flags 的高16位描述(包含)特定的动态结构类型(CV_SEQ_MAGIC_VAL 表示稠密序列,CV_SET_MAGIC_VAL 表示稀疏序列),同时包含形形色色的信息。

低 CV_SEQ_ELTYPE_BITS 位包含元素类型的 ID(标示符)。大多数处理函数并不会用到元素类型,而会用到存放在 elem_size 中的元素大小 。如果序列中包含 CvMat 中的数据,那么元素的类型就与 CvMat 中的类型相匹配, 如:CV_32SC2 可以被使用为由二维空间中的点序列, CV_32FC1用为由浮点数组成的序列等。通过宏 CV_SEQ_ELTYPE(seq_header_ptr) 来获取序列中元素的类型。处理数字序列的函数判断: elem.size 等同于序列元素的大小。除了与 CvMat 相兼容的类型外,还有几个在头 cvtypes.h 中定义的额外的类型。

Standard Types of Sequence Elements

    #define CV_SEQ_ELTYPE_POINT          CV_32SC2  /* (x,y) */
    #define CV_SEQ_ELTYPE_CODE           CV_8UC1   /* freeman code: 0..7 */
    #define CV_SEQ_ELTYPE_GENERIC        0 /* unspecified type of sequence elements */
    #define CV_SEQ_ELTYPE_PTR            CV_USRTYPE1 /* =6 */
    #define CV_SEQ_ELTYPE_PPOINT         CV_SEQ_ELTYPE_PTR  /* &elem: pointer to element of other sequence */
    #define CV_SEQ_ELTYPE_INDEX          CV_32SC1  /* #elem: index of element of some other sequence */
    #define CV_SEQ_ELTYPE_GRAPH_EDGE     CV_SEQ_ELTYPE_GENERIC  /* &next_o, &next_d, &vtx_o, &vtx_d */
    #define CV_SEQ_ELTYPE_GRAPH_VERTEX   CV_SEQ_ELTYPE_GENERIC  /* first_edge, &(x,y) */
    #define CV_SEQ_ELTYPE_TRIAN_ATR      CV_SEQ_ELTYPE_GENERIC  /* vertex of the binary tree   */
    #define CV_SEQ_ELTYPE_CONNECTED_COMP CV_SEQ_ELTYPE_GENERIC  /* connected component  */
    #define CV_SEQ_ELTYPE_POINT3D        CV_32FC3  /* (x,y,z)  */

后面的 CV_SEQ_KIND_BITS 字节表示序列的类型:

Standard Kinds of Sequences

    /* generic (unspecified) kind of sequence */
    #define CV_SEQ_KIND_GENERIC     (0 << CV_SEQ_ELTYPE_BITS)

    /* dense sequence suntypes */
    #define CV_SEQ_KIND_CURVE       (1 << CV_SEQ_ELTYPE_BITS)
    #define CV_SEQ_KIND_BIN_TREE    (2 << CV_SEQ_ELTYPE_BITS)

    /* sparse sequence (or set) subtypes */
    #define CV_SEQ_KIND_GRAPH       (3 << CV_SEQ_ELTYPE_BITS)
    #define CV_SEQ_KIND_SUBDIV2D    (4 << CV_SEQ_ELTYPE_BITS)

CvSeqBlock

连续序列块

typedef struct CvSeqBlock
{
    struct CvSeqBlock* prev; /* previous sequence block */
    struct CvSeqBlock* next; /* next sequence block */
    int start_index; /* index of the first element in the block +
    sequence->first->start_index */
    int count; /* number of elements in the block */
    char* data; /* pointer to the first element of the block */
} CvSeqBlock;

序列块构成一个双向的循环列表,因此指针 prev 和 next 永远不会为 null, 而总是指向序列中的前一个和后一个序列块。也就是说:最后一个序列块的 next 指向的就是序列中的第一个块,而第一个块的 prev 指向最后一个块。域 start_index 和 count 有助于跟踪序列中块的位置。 例如,一个含10个元素的序列被分成了3块,每一块的大小分别为3, 5, 2,第一块的参数 start_index 为 2, 那么该序列的 (start_index, count) 相应为 (2,3),(5,5),(10,2)。第一个块的参数 start_index 通常为 0,除非一些元素已被插入到序列中。  

CvSlice

序列分割

typedef struct CvSlice
{
    int start_index;
    int end_index;
} CvSlice;

inline CvSlice cvSlice( int start, int end );
#define CV_WHOLE_SEQ_END_INDEX 0x3fffffff
#define CV_WHOLE_SEQ  cvSlice(0, CV_WHOLE_SEQ_END_INDEX)

/* calculates the sequence slice length */
int cvSliceLength( CvSlice slice, const CvSeq* seq );

有关序列的一些操作函数将 CvSlice 作为输入参数,默认情况下该参数通常被设置成整个序列(CV_WHOLE_SEQ)。start_index 和 end_index 任何一个都可以是负数或 超过序列长度,start_index 是闭界,end_index 是开界。如果两者相等,那么分割被认为是空分割(即:不包含任何元素)。由于序列被看作是循环结构, 所以分割可以选择序列中靠后的几个元素,靠前的参数反而跟着它们,如 cvSlice(-2,3)。函数用下列方法来规范分割参数:首先, 调用 cvSliceLength 来决定分割的长度,然后, start_index 被使用类似于 cvGetSeqElem 的参数来规范(例如:负数也被允许)。实际的分割操作起始于规范化了的 start_index ,中止于 start_index + cvSliceLength()。(再次假设序列是循环结构)

如果函数并不接受分割参数,但你还是想要处理序列的一部分,那么可以使用函数 cvSeqSlice 获取子序列。  

CreateSeq

创建一序列

CvSeq* cvCreateSeq( int seq_flags, int header_size,
                    int elem_size, CvMemStorage* storage );
seq_flags 
序列的符号标志。如果序列不会被传递给任何使用特定序列的函数,那么将它设为 0, 否则从预定义的序列类型中选择一合适的类型。
header_size 
序列头部的大小;必须大于或等于 sizeof(CvSeq). 如果制定了类型或它的扩展名,则此类型必须适合基类的头部大小。
elem_size 
元素的大小,以字节计。这个大小必须与序列类型相一致。例如,对于一个点的序列,元素类型 CV_SEQ_ELTYPE_POINT 应当被指定, 参数elem_size 必须等同于 sizeof(CvPoint).

函数 cvCreateSeq 创建一序列并且返回指向该序列的指针。函数在存储块中分配序列的头部作为一个连续躯体,并且设置结构的 flags域, elem_size域, header_size域 和 storage域 的值为被传递过来的值,设置 delta_elems 为默认值(可通过函数 cvSetSeqBlockSize 重新对其赋值),清空其他的头 部域,包括前sizeof(CvSeq) 个字节的空间。

SetSeqBlockSize

设置序列块的大小

void cvSetSeqBlockSize( CvSeq* seq, int delta_elems );
seq 
序列
delta_elems 
满足元素所需的块的大小

函数 cvSetSeqBlockSize 会对内存分配的粒度产生影响。 当序列缓冲区中空间消耗完时,函数为 delta_elems 个序列元素分配空间。如果新分配的空间与 之前分配的空间相邻的话,这两个块就合并,否则,就创建了一个新的序列快。因此,参数值越大,序列中出现碎片的可能性就越小,不过内存中更多的空间将被浪费。当序列被创建后,参数 delta_elems 大小将被设置为 默认大小(1K).之后, 就可随时调用该函数,并影响内存分配。 函数可以修改被传递过来的参数值,以满足内存块的大小限制 。

SeqPush

添加元素到序列的尾部

char* cvSeqPush( CvSeq* seq, void* element=NULL );
seq 
element 
添加的元素

函数 cvSeqPush 在序列块的尾部添加一元素并返回指向该元素得指针。如果输入参数为 null, 函数就仅仅分配一空间,留给下一个元素使用。下列代码说明如何使用该函数去创建一空间。

The following code demonstrates how to create a new sequence using this function:

CvMemStorage* storage = cvCreateMemStorage(0);
CvSeq* seq = cvCreateSeq( CV_32SC1, /* sequence of integer elements */
                          sizeof(CvSeq), /* header size - no extra fields */
                          sizeof(int), /* element size */
                          storage /* the container storage */ );
int i;
for( i = 0; i < 100; i++ )
{
    int* added = (int*)cvSeqPush( seq, &i );
    printf( "%d is added\n", *added );
}

...
/* release memory storage in the end */
cvReleaseMemStorage( &storage );

函数 cvSeqPush 的时间复杂度为 O(1). 如果需要分配并使用的空间比较大,则存在一分配较快的函数(见:cvStartWriteSeq 和相关函数)

SeqPop

删除序列尾部元素

void cvSeqPop( CvSeq* seq, void* element=NULL );
seq 
序列
element 
可选参数。如果该指针不为空,就拷贝被删元素到指针指向的位置

函数 cvSeqPop 从序列中删除一元素。如果序列已经为空,就报告一错误。函数时间复杂度为 O(1).

SeqPushFront

在序列头部添加元素

char* cvSeqPushFront( CvSeq* seq, void* element=NULL );
seq 
序列
element 
添加的元素

函数 cvSeqPushFront 类似于 cvSeqPush, 不过是在序列头部添加元素。时间复杂度为O(1).

SeqPopFront

删除序列的头部元素

void cvSeqPopFront( CvSeq* seq, void* element=NULL );
seq 
序列
element 
可选参数。如果该指针不为空,就拷贝被珊元素到指针指向的位置。

函数 cvSeqPopFront 删除序列的头部元素。如果序列已经为空,就报告一错误。函数时间复杂度为 O(1).

SeqPushMulti

添加多个元素到序列尾部或头部。

void cvSeqPushMulti( CvSeq* seq, void* elements, int count, int in_front=0 );
seq 
序列
elements 
待添加的元素
count 
添加的元素个数
in_front
标示在头部还是尾部添加元素
CV_BACK ( = 0) -- 在序列尾部添加元素。
CV_FRONT( != 0) -- 在序列头部添加元素。

函数 cvSeqPushMulti 在序列头部或尾部添加多个元素。 元素按输入数组中的顺序被添加到序列中,不过它们可以添加到不同的序列中

SeqPopMulti

删除多个序列头部或尾部的元素

void cvSeqPopMulti( CvSeq* seq, void* elements, int count, int in_front=0 );
seq 
序列
elements 
待删除的元素
count 
删除的元素个数
in_front
标示在头部还是尾部删除元素
CV_BACK ( = 0) -- 删除序列尾部元素。
CV_FRONT( != 0) -- 删除序列头部元素。

函数 cvSeqPopMulti 删除多个序列头部或尾部的元素。 如果待删除的元素个数超过了序列中的元素总数,则函数删除尽可能多的元素 。

SeqInsert

在序列中添加元素

char* cvSeqInsert( CvSeq* seq, int before_index, void* element=NULL );
seq 
序列
before_index 
元素插入的位置(索引)。如果插入的位置在 0(允许的参数最小值)前,则该函数等同于函数 cvSeqPushFront.如果是在 seq_total(允许的参数最大值)后,则该函数等同于 cvSeqPush.
element 
待插入的元素

函数 cvSeqInsert 移动 从被插入的位置到序列尾部元素所在的位置的所有元素,如果 指针 element 不位 null, 则拷贝 element 中的元素到指定位置。函数返回指向被插入元素的指针。

SeqRemove

从序列中删除指定的元素。

void cvSeqRemove( CvSeq* seq, int index );
seq 
目标序列
index 
被删除元素的索引或位置。

函数 cvSeqRemove 删除seq中指定索引(位置)的元素。如果这个索引超出序列的元素个数,会报告出错。企图从空序列中删除元素,函数也将报告错误。函数通过移动序列中的元素来删除被索引的元素。

ClearSeq

清空序列

void cvClearSeq( CvSeq* seq );
seq 
Sequence.
seq 
序列

函数 cvClearSeq 删除序列中的所有元素。函数不会将内存返回到存储器中,当新的元素添加到序列中时,可重新使用该内存。函数时间复杂度为 O(1).

GetSeqElem

返回索引所指定的元素指针

char* cvGetSeqElem( const CvSeq* seq, int index );
#define CV_GET_SEQ_ELEM( TYPE, seq, index )  (TYPE*)cvGetSeqElem( (CvSeq*)(seq), (index) )
seq 
序列
index 
索引

函数 cvGetSeqElem 查找序列中索引所指定的元素,并返回指向该元素的指针。如果元素不存在,则返回 0。 函数支持负数,即: -1 代表 序列的最后一个元素, -2 代表最后第二个元素,等。如果序列只包含一个块,或者所需的元素在第一个块中,那么应当使用宏, CV_GET_SEQ_ELEM( elemType, seq, index )宏中的参数 elemType 是序列中元素的类型(如:CvPoint), 参数 seq 表示序列, 参数 index 代表所需元素的索引。 该宏首先核查所需的元素是否属于第一个块,如果是,则返回该元素,否则,该宏就调用主函数 GetSeqElem. 如果索引为负数的话,则总是调用函数 cvGetSeqElem。函数的时间复杂度为 O(1), 假设块的大小要比元素的数量要小。

SeqElemIdx

返回序列中元素的索引

int cvSeqElemIdx( const CvSeq* seq, const void* element, CvSeqBlock** block=NULL );
seq 
序列
element 
指向序列中元素的指针
block 
可选参数, 如果不为空(NULL),则存放包含该元素的块的地址

函数 cvSeqElemIdx 返回元素的索引,如果该元素不存在这个序列中,则返回一负数。

cvSeqToArray

拷贝序列中的元素到一个连续的内存块中

void* cvCvtSeqToArray( const CvSeq* seq, void* elements, CvSlice slice=CV_WHOLE_SEQ );
seq 
序列
elemenets 
指向目的(存放拷贝元素的)数组的指针,指针指向的空间必须足够大。
slice 
拷贝到序列中的序列部分。

函数 cvCvtSeqToArray 拷贝整个序列或部分序列到指定的缓冲区中,并返回指向该缓冲区的指针.

MakeSeqHeaderForArray

构建序列

CvSeq* cvMakeSeqHeaderForArray( int seq_type, int header_size, int elem_size,
                                void* elements, int total,
                                CvSeq* seq, CvSeqBlock* block );
seq_type 
序列的类型
header_size 
序列的头部大小。大小必须大于等于数组的大小。
elem_size 
元素的大小
elements 
形成该序列的元素
total 
序列中元素的总数。参数值必须等于数据的大小
seq 
指向被使用作为序列头部的局部变量
block 
指向局部变量的指针

函数 cvMakeSeqHeaderForArray 初始化序列的头部。序列块由用户分配(例如:在栈上)。该函数不拷贝数据。创建的序列只包含一个块,和一个 NULL指针,因此可以读取指针,但试图将元素添加到序列中则多数会引发错误。

SeqSlice

为各个序列碎片建立头

CvSeq* cvSeqSlice( const CvSeq* seq, CvSlice slice,
                   CvMemStorage* storage=NULL, int copy_data=0 );
seq 
序列
slice 
部分序列块
storage 
存放新的序列和拷贝数据(如果需要)的目的存储空间。如果为NULL, 则函数使用包含该输入数据的存储空间。
copy_data 
标示是否要拷贝元素, 如果 copy_data != 0, 则需要拷贝;如果 copy_data == 0, 则不需拷贝。

函数 cvSeqSlice 创建一序列,该序列表示输入序列中特定的一部分 (slice),。新序列要么与原序列共享元素要么拥有自己的一份拷贝。因此,如果 有人需要去 处理 该部分序列,但函数却没有 slice 参数, 则使用该函数去获取该序列。.

CloneSeq

创建序列的一份拷贝

CvSeq* cvCloneSeq( const CvSeq* seq, CvMemStorage* storage=NULL );
seq 
序列
storage 
存放新序列的 header部分和拷贝数据(如果需要)的目的存储块。如果为 NULL, 则函数使用包含输入序列的存储块 。

函数 cvCloneSeq 创建输入序列的一份完全拷贝。调用函数 cvCloneSeq (seq, storage) 等同于调用 cvSeqSlice(seq, CV_WHOLE_SEQ, storage, 1).

SeqRemoveSlice

删除序列的 slice部分

void cvSeqRemoveSlice( CvSeq* seq, CvSlice slice );
seq 
序列
slice 
序列中被移动的那部分

函数 cvSeqRemoveSlice 删除序列中的 slice 部分

SeqInsertSlice

在序列中插入一数组

void cvSeqInsertSlice( CvSeq* seq, int before_index, const CvArr* from_arr );
seq 
序列
slice 
序列中被移动的那部分
from_arr 
从中获取元素的数组

函数 cvSeqInsertSlice 在指定位置插入 来自数组from_arr中 所有元素。数组 from_arr 可以是一个 矩阵也可以是另外一个 序列。

SeqInvert

将序列中的元素进行逆序操作

void cvSeqInvert( CvSeq* seq );
seq 
序列

函数 cvSeqInvert 对序列进行逆序操作 -- 即:使第一个元素成为最后一个,最后一个元素为第一个。

SeqSort

使用特定的比较函数对序列中的元素进行排序

/* a < b ? -1 : a > b ? 1 : 0 */
typedef int (CV_CDECL* CvCmpFunc)(const void* a, const void* b, void* userdata);

void cvSeqSort( CvSeq* seq, CvCmpFunc func, void* userdata=NULL );
seq 
待排序的序列
func 
比较函数,按照元素间的大小关系返回负数,零,正数(见:上面的声明和下面的例子) --相关函数为 C 运行时库中的 qsort, 后者(qsort)不使用参数userdata.
userdata 
传递给比较函数的用户参数;有些情况下,可避免全局变量的使用

函数 cvSeqSort 使用特定的标准对序列进行排序。下面是一个 使用该函数的实例

/* Sort 2d points in top-to-bottom left-to-right order */
static int cmp_func( const void* _a, const void* _b, void* userdata )
{
    CvPoint* a = (CvPoint*)_a;
    CvPoint* b = (CvPoint*)_b;
    int y_diff = a->y - b->y;
    int x_diff = a->x - b->x;
    return y_diff ? y_diff : x_diff;
}

...

CvMemStorage* storage = cvCreateMemStorage(0);
CvSeq* seq = cvCreateSeq( CV_32SC2, sizeof(CvSeq), sizeof(CvPoint), storage );
int i;

for( i = 0; i < 10; i++ )
{
    CvPoint pt;
    pt.x = rand() % 1000;
    pt.y = rand() % 1000;
    cvSeqPush( seq, &pt );
}

cvSeqSort( seq, cmp_func, 0 /* userdata is not used here */ );

/* print out the sorted sequence */
for( i = 0; i < seq->total; i++ )
{
    CvPoint* pt = (CvPoint*)cvGetSeqElem( seq, i );
    printf( "(%d,%d)\n", pt->x, pt->y );
}

cvReleaseMemStorage( &storage );

SeqSearch

查询序列中的元素

/* a < b ? -1 : a > b ? 1 : 0 */
typedef int (CV_CDECL* CvCmpFunc)(const void* a, const void* b, void* userdata);

char* cvSeqSearch( CvSeq* seq, const void* elem, CvCmpFunc func,
                   int is_sorted, int* elem_idx, void* userdata=NULL );
seq 
序列
elem 
待查询的元素
func 
比较函数,按照元素间的大小关系返回负数,零,正数(见:cvSeqSort)
is_sorted 
标示序列是否已经排序
elem_idx 
输出参数;(已查找到)元素的索引值
user_data 
传递到比较函数的用户参数;在某些情况下,有助于避免使用全局变量。

函数 cvSeqSearch 查找序列中的元素。如果序列已被排序,则使用二分查找(时间复杂度为 O(log(N))否则使用简单线性查找。若查找的元素不存在,函数返回 NULL 指针,而索引值设置为序列中的元素数(如果使用的是线性查找)或 满足表达式 seq(i) > elem 的最小的 i.

StartAppendToSeq

将数据写入序列中,并初始化该过程

void cvStartAppendToSeq( CvSeq* seq, CvSeqWriter* writer );
seq 
指向序列的指针
writer 
writer 的状态; 由该函数初始化

函数 cvStartAppendToSeq 初始化将数据写入序列这个过程。通过宏 CV_WRITE_SEQ_ELEM( written_elem, writer ),写入的元素被添加到序列尾部。注意:在写入期间,序列的其他操作可能会产生的错误的结果,甚至破怀该序列(见 cvFlushSeqWriter 的相关描述,有助于避免这些错误)

StartWriteSeq

创建新序列,并初始化写入部分(writer)

void cvStartWriteSeq( int seq_flags, int header_size, int elem_size,
                      CvMemStorage* storage, CvSeqWriter* writer );
seq_flags 
标示被创建的序列。如果序列还未传递给任何处理特定序列类型的函数,则序列值等于0, 否则,必须从之前定义的序列类型中选择一个合适的类型。
header_size 
头部的大小。 参数值不小于 sizeof(CvSeq). 如果定义了某一类型,则该类型不许符合基类的条件。
elem_size 
元素的大小(以字节计);必须与序列类型相一致。例如:如果创建了包含指针的序列(元素类型为 CV_SEQ_ELTYPE_POINT), 那么elem_size 必须等同于 sizeof(CvPoint).
storage 
序列的(在内存)位置
writer 
写入部分 writer 的状态; 由该函数初始化

函数 cvStartWriteSeq 是 函数 cvCreateSeq 和函数 cvStartAppendToSeq 的组合。 指向被创建的序列的指针存放在 writer->seq 中, 通过函数cvEndWriteSeq 返回(因当在最后调用)

EndWriteSeq

完成写入操作

CvSeq* cvEndWriteSeq( CvSeqWriter* writer );
writer 
写入部分 writer 的状态

函数 cvEndWriteSeq 完成写入操作并返回指向被写入元素的序列的地址。同时,函数会截取最后那个不完整的序列块,将块的剩余部分返回到内存中之后,序列就可以被安全的读和写。

FlushSeqWriter

根据写入状态,刷新序列头部

void cvFlushSeqWriter( CvSeqWriter* writer );
writer 
写入部分的状态

函数 cvFlushSeqWriter 用来使用户在写入过程中每当需要时读取序列元素,比如说,核查制定的条件。函数更新序列的头部,从而使读取序列中的数据成为可能。不过,写入并没有被关闭,为的是随时都可以将数据写入序列。在有些算法中,经常需要刷新,考虑使用 cvSeqPush 代替该函数。

StartReadSeq

初始化序列中的读取过程

void cvStartReadSeq( const CvSeq* seq, CvSeqReader* reader, int reverse=0 );
seq 
序列
reader 
读取部分的状态; 由该函数初始化
reverse 
决定遍历序列的方向。如果 reverse 为0,则读取顺序被定位从序列头部元素开始,否则从尾部开始读取

函数 cvStartReadSeq 初始化读取部分的状态。毕竟,顺序读取可通过调用宏 CV_READ_SEQ_ELEM( read_elem, reader ),逆序读取可通过调用宏CV_REV_READ_SEQ_ELEM( read_elem, reader )。这两个宏都将序列元素读进read_elem中, 并将指针移到下一个元素。下面代码显示了如何去使用reader 和 writer.

CvMemStorage* storage = cvCreateMemStorage(0);
CvSeq* seq = cvCreateSeq( CV_32SC1, sizeof(CvSeq), sizeof(int), storage );
CvSeqWriter writer;
CvSeqReader reader;
int i;

cvStartAppendToSeq( seq, &writer );
for( i = 0; i < 10; i++ )
{
    int val = rand()%100;
    CV_WRITE_SEQ_ELEM( val, writer );
    printf("%d is written\n", val );
}
cvEndWriteSeq( &writer );

cvStartReadSeq( seq, &reader, 0 );
for( i = 0; i < seq->total; i++ )
{
    int val;
#if 1
    CV_READ_SEQ_ELEM( val, reader );
    printf("%d is read\n", val );
#else /* alternative way, that is prefferable if sequence elements are large,
         or their size/type is unknown at compile time */
    printf("%d is read\n", *(int*)reader.ptr );
    CV_NEXT_SEQ_ELEM( seq->elem_size, reader );
#endif
}
...

cvReleaseStorage( &storage );

GetSeqReaderPos

返回当前的读取器的位置

int cvGetSeqReaderPos( CvSeqReader* reader );
reader 
读取器的状态.

函数 cvGetSeqReaderPos 返回当前的 reader 位置 (在 0 到 reader->seq->total - 1 中)

SetSeqReaderPos

移动读取器到指定的位置。

void cvSetSeqReaderPos( CvSeqReader* reader, int index, int is_relative=0 );
reader 
reader 的状态
index 
目的位置。如果使用了 positioning mode, 则实际位置为 index % reader->seq->total.
is_relative 
如果不位 0, 那么索引(index) 就相对于当前的位置

函数 cvSetSeqReaderPos 将 read 的位置移动到绝对位置,或相对于当前的位置(相对位置)

集合

CvSet

Collection of nodes

typedef struct CvSetElem
{
    int flags; /* it is negative if the node is free and zero or positive otherwise */
    struct CvSetElem* next_free; /* if the node is free, the field is a
                                    pointer to next free node */
}
CvSetElem;

#define CV_SET_FIELDS()    \
    CV_SEQUENCE_FIELDS()   /* inherits from CvSeq */ \
    struct CvSetElem* free_elems; /* list of free nodes */

typedef struct CvSet
{
    CV_SET_FIELDS()
} CvSet;

在 OpenCV 的稀疏数据结构中, CvSet 是一基本结构。

从上面的声明中可知:CvSet 继承自 CvSeq, 并在此基础上增加了个 free_elems 域,该域是空节点组成的列表。集合中的每一个节点,无论空否,都是线性表中的一个元素。尽管对于稠密的表中的元素没有限制,集合(派生的结构)元素必须起始于整数域,并与结构 CvSetElem 相吻合,因为这两个域对于(由空节点组成)集合的组织是必要的。如果节点为空,flags 为负,next_free 指向下一个空节点。如果节点已被占据空间,flags 为正, flags 包含节点索引值(使用表达式 set_elem->flags & CV_SET_ELEM_IDX_MASKH 获取), flags 的剩余内容由用户决定。宏 CV_IS_SET_ELEM(set_elem.ptr)用来识别特定的节点是否为空。

起初,集合 set 同表 list 都为空。当需要一个来自集合中的新节点时,就从表 list 中去获取,然后表进行了更新。如果表 list 碰巧为空,于是就分配一内存块,块中的所有节点与表 list 相连。结果,集合的 total 域被设置为空节点和非空节点的和。当非空节点别释放后,就将它加到空节点列表中。最先被释放的节点也就是最先被占用空间的节点

在 OpenCV 中, CvSet 用来代表图形(CvGraph), 稀疏多维数组(CvSparseMat), 平面子划分(planner subdivisions)等

CreateSet

创建空的数据集

CvSet* cvCreateSet( int set_flags, int header_size,
                    int elem_size, CvMemStorage* storage );
set_flags 
集合的类型
header_size 
头节点的大小;应该等于 sizeof(CvSet)
elem_size 
元素的大小; 不能小8
storage 
相关容器

函数 CvCreateSet 创建一具有特定头部节点大小和元素类型的空集。并返回指向该集合的指针。

SetAdd

占用集合中的一个节点

int cvSetAdd( CvSet* set_header, CvSetElem* elem=NULL, CvSetElem** inserted_elem=NULL );
set_header 
集合
elem 
可选的输入参数,被插入的元素。如果不为 NULL, 函数就将数据拷贝到新分配的节点。(拷贝后,清空第一个域的 MSB)

函数 cvSetAdd 分配一新的节点,将输入数据拷贝给它(可选),并且返回指向该节点的指针和节点的索引值。索引值可通过节点的flags域的低位中获得。函数的时间复杂度为 O(1), 不过,存在着一个函数可快速的分配内存。(见 cvSetNew)

SetRemove

从点集中删除元素

void cvSetRemove( CvSet* set_header, int index );
set_header 
集合
index 
被删元素的索引值

函数 cvSetRemove 从点集中删除一具有特定索引值的元素。如果指定位置的节点为空,函数将什么都不做。函数的时间复杂度为 O(1), 不过,存在一函数可更快速的完成该操作,该函数就是 cvSetRemoveByPtr

SetNew

添加元素到点集中

CvSetElem* cvSetNew( CvSet* set_header );
set_header 
集合

函数 cvSetNew 是 cvSetAdd 的变体,内联函数。它占用一新节点,并返回指向该节点的指针而不是索引。

SetRemoveByPtr

删除指针指向的集合元素

void cvSetRemoveByPtr( CvSet* set_header, void* elem );
set_header 
集合
elem 
被删除的元素

函数 cvSetRemoveByPtr 是一内联函数,是函数 cvSetRemove 轻微变化而来的。该函数并不会检查节点是否为空 -- 用户负责这一检查。

GetSetElem

通过索引值查找相应的集合元素

CvSetElem* cvGetSetElem( const CvSet* set_header, int index );
set_header 
集合
index 
索引值

函数 cvGetSetElem 通过索引值查找相应的元素。函数返回指向该元素的指针,如果索引值无效或相应的节点为空,则返回 0。 若函数使用 cvGetSeqElem 去查找节点,则函数支持负的索引值。

ClearSet

清空点集

void cvClearSet( CvSet* set_header );
set_header 
待清空的点集

函数 cvClearSet 删除集合中的所有元素。时间复杂度为 O(1).


CvGraph

有向权图和无向权图

#define CV_GRAPH_VERTEX_FIELDS()    \
    int flags; /* vertex flags */   \
    struct CvGraphEdge* first; /* the first incident edge */

typedef struct CvGraphVtx
{
    CV_GRAPH_VERTEX_FIELDS()
}
CvGraphVtx;

#define CV_GRAPH_EDGE_FIELDS()      \
    int flags; /* edge flags */     \
    float weight; /* edge weight */ \
    struct CvGraphEdge* next[2]; /* the next edges in the incidence lists for staring (0) */ \
                                 /* and ending (1) vertices */ \
    struct CvGraphVtx* vtx[2]; /* the starting (0) and ending (1) vertices */

typedef struct CvGraphEdge
{
    CV_GRAPH_EDGE_FIELDS()
}
CvGraphEdge;

#define  CV_GRAPH_FIELDS()                  \
    CV_SET_FIELDS() /* set of vertices */   \
    CvSet* edges;   /* set of edges */

typedef struct CvGraph
{
    CV_GRAPH_FIELDS()
}
CvGraph;

在 OpenCV 图形结构中,CvGraph 是一基本结构。

图形结构继承自 CvSet -- 该部分描绘了普通图的属性和图的顶点,也包含了一个点集作为其成员 -- 该点集描述了图的边缘。利用宏(可以简化结构扩展和定制)使用与其它OpenCV可扩展结构一样的方法和技巧,同样的方法和技巧,我们声明了定点,边和头部结构。虽然顶点结构和边结构无法从CvSetElem 显式地继承时,但它们满足点集元素的两个条件(在开始是有一个整数域和满足 CvSetElem 结构)。 flags 域用来标记顶点和边是否已被占用或者处于其他目的,如:遍历图时(见:cvStartScanGraph 等),因此最好不要去直接使用它们。图代表的就是边的集合。存在有向和无向的区别。对于后者(无向图),在连接顶点 A 到 顶点 B 的边同连接顶点 B 到 顶点 A的边是没什么区别的,在某一时刻,只可能存在一个,即:要么是<A, B>要么是<B, A>.

CreateGraph

创建一个空树

CvGraph* cvCreateGraph( int graph_flags, int header_size, int vtx_size,
                        int edge_size, CvMemStorage* storage );
graph_flags 
被创建的图的类型。通常,无向图为 CV_SEQ_KIND_GRAPH,有向图为 CV_SEQ_KIND_GRAPH | CV_GRAPH_FLAG_ORIENTED.
header_size 
头部大小;可能小于 sizeof(CvGraph)
vtx_size 
顶点大小;常规的定点结构必须来自 CvGraphVtx (使用宏 CV_GRAPH_VERTEX_FIELDS())
edge_size 
边的大小;常规的边结构必须来自 CvGraphEdge (使用宏 CV_GRAPH_EDGE_FIELDS())
storage 
图的容器

函数 cvCreateGraph 创建一空图并且返回指向该图的指针。

GraphAddVtx

插入一顶点到图中

int cvGraphAddVtx( CvGraph* graph, const CvGraphVtx* vtx=NULL,
                   CvGraphVtx** inserted_vtx=NULL );
graph 
vtx 
可选输入参数,用来初始化新加入的顶点(仅大小超过 sizeof(CvGraphVtx) 的用户自定义的域才会被拷贝)
inserted_vertex 
可选的输出参数。如果不为 NULL, 则传回新加入顶点的地址

函数 cvGraphAddVtx 将一顶点加入到图中,并返回定点的索引

GraphRemoveVtx

通过索引从图中删除一顶点

int cvGraphRemoveVtx( CvGraph* graph, int index );
graph 
vtx_idx 
被珊顶点的索引

函数 cvGraphRemoveAddVtx 从图中删除一顶点,连同删除含有此顶点的边。如果输入的顶点不属于该图的话,将报告删除出错(不存在而无法删除)。返回值为被删除的边数,如果顶点不属于该图的话,返回 -1。

GraphRemoveVtxByPtr

通过指针从图中删除一顶点

int cvGraphRemoveVtxByPtr( CvGraph* graph, CvGraphVtx* vtx );
graph 
vtx 
指向被删除的边的指针

函数 cvGraphRemoveVtxByPtr 从图中删除一顶点,连同删除含有此顶点的边。如果输入的顶点不属于该图的话,将报告删除出错(不存在而无法删除)。返回值为被删除的边数,如果顶点不属于该图的话,返回 -1。

GetGraphVtx

通过索引值查找图的相应顶点

CvGraphVtx* cvGetGraphVtx( CvGraph* graph, int vtx_idx );
graph 
vtx_idx 
定点的索引值

函数 cvGetGraphVtx 通过索引值查找对应的顶点,并返回指向该顶点的指针,如果不存在则返回 NULL.

GraphVtxIdx

返回定点相应的索引值

int cvGraphVtxIdx( CvGraph* graph, CvGraphVtx* vtx );
graph 
vtx 
指向顶点的指针

函数 cvGraphVtxIdx 返回与顶点相应的索引值

GraphAddEdge

通过索引值在图中加入一条边

int cvGraphAddEdge( CvGraph* graph, int start_idx, int end_idx,
                    const CvGraphEdge* edge=NULL, CvGraphEdge** inserted_edge=NULL );
graph 
start_idx 
边的起始顶点的索引值
end_idx 
边的尾部顶点的索引值(对于无向图,参数的次序无关紧要,即:start_idx 和 end_idx 可互为起始顶点和尾部顶点)
edge 
可选的输入参数,初始化边的数据
inserted_edge 
可选的输出参数,包含被插入的边的地址。

函数 cvGraphAddEdge 连接两特定的顶点。如果该边成功地加入到图中,返回 1; 如果连接两顶点的边已经存在,返回 0; 如果顶点没被发现(不存在)或者起始顶点和尾部顶点是同一个定点,或其他特殊情况,返回 -1。 如果是后者(即:返回值为负),函数默认的报告一个错误。

GraphAddEdgeByPtr

通过指针在图中加入一条边

int cvGraphAddEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx,
                         const CvGraphEdge* edge=NULL, CvGraphEdge** inserted_edge=NULL );
graph 
start_vtx 
指向起始顶点的指针
end_vtx 
指向尾部顶点的指针。对于无向图来说,顶点参数的次序无关紧要。
edge 
可选的输入参数,初始化边的数据
inserted_edge 
可选的输出参数,包含被插入的边的地址。

函数 cvGraphAddEdge 连接两特定的顶点。如果该边成功地加入到图中,返回 1; 如果连接两顶点的边已经存在,返回 0; 如果顶点没被发现(不存在)或者起始顶点和尾部顶点是同一个定点,或其他特殊情况,返回 -1。 如果是后者(即:返回值为负),函数默认的报告一个错误

GraphRemoveEdge

通过索引值从图中删除顶点

void cvGraphRemoveEdge( CvGraph* graph, int start_idx, int end_idx );
graph 
start_idx 
起始顶点的索引值
end_idx 
尾部顶点的索引值。对于无向图来说,顶点参数的次序无关紧要。

函数 cvGraphRemoveEdge 删除连接两特定顶点的边。若两顶点并没有相连接(即:不存在由这两个顶点连接的边),函数什么都不做。

GraphRemoveEdgeByPtr

通过指针从图中删除边

void cvGraphRemoveEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx );
graph 
start_vtx 
指向起始顶点的指针
end_vtx 
指向尾部顶点的指针。对于无向图来说,顶点参数的次序无关紧要。

函数 cvGraphRemoveEdgeByPtr 删除连接两特定顶点的边。若两顶点并没有相连接(即:不存在由这两个顶点连接的边),函数什么都不做。

FindGraphEdge

通过索引值在图中查找相应的边

CvGraphEdge* cvFindGraphEdge( const CvGraph* graph, int start_idx, int end_idx );
#define cvGraphFindEdge cvFindGraphEdge
graph 
start_idx 
起始顶点的索引值
end_idx 
尾部顶点的索引值。对于无向图来说,顶点参数的次序无关紧要

函数 cvFindGraphEdge 查找与两特定顶点相对应的边,并返回指向该边的指针。如果该边不存在,返回 NULL.

FindGraphEdgeByPtr

通过指针在图中查找相应的边

CvGraphEdge* cvFindGraphEdgeByPtr( const CvGraph* graph, const CvGraphVtx* start_vtx,
                                   const CvGraphVtx* end_vtx );
#define cvGraphFindEdgeByPtr cvFindGraphEdgeByPtr
graph 
start_vtx 
指向起始顶点的指针
end_vtx 
指向尾部顶点的指针。对于无向图来说,顶点参数的次序无关紧要。

函数 cvFindGraphEdgeByPtr 查找与两特定顶点相对应的边,并返回指向该边的指针。如果该边不存在,返回 NULL

GraphEdgeIdx

返回与该边相应的索引值

int cvGraphEdgeIdx( CvGraph* graph, CvGraphEdge* edge );
graph 
edge 
指向该边的指针

函数 cvGraphEdgeIdx 返回与边对应的索引值。

GraphVtxDegree

(通过索引值)统计与顶点相关联的边数

int cvGraphVtxDegree( const CvGraph* graph, int vtx_idx );
graph 
vtx_idx 
顶点对应的索引值

函数 cvGraphVtxDegree 返回与特定顶点相关联的边数,包括以该顶点为起始顶点的和尾部顶点的。统计边数,可以适用下列代码:

CvGraphEdge* edge = vertex->first; int count = 0;
while( edge )
{
    edge = CV_NEXT_GRAPH_EDGE( edge, vertex );
    count++;
}

宏 CV_NEXT_GRAPH_EDGE(edge, vertex) 返回依附于该顶点的下一条边。  

GraphVtxDegreeByPtr

(通过指针)统计与顶点相关联的边数

int cvGraphVtxDegreeByPtr( const CvGraph* graph, const CvGraphVtx* vtx );
graph 
vtx 
顶点对应的指针

函数 cvGraphVtxDegreeByPtr 返回与特定顶点相关联的边数,包括以该顶点为起始顶点的和尾部顶点的

ClearGraph

删除图

void cvClearGraph( CvGraph* graph );
graph

函数 cvClearGraph 删除该图的所有顶点和边。时间复杂度为 O(1).

CloneGraph

克隆图

CvGraph* cvCloneGraph( const CvGraph* graph, CvMemStorage* storage );
graph 
待拷贝的图
storage 
容器,存放拷贝

函数 cvCloneGraph 创建图的完全拷贝。如果顶点和边含有指向外部变量的指针,那么图和它的拷贝共享这些指针。在新的图中,顶点和边可能存在不同,因为函数重新分割了顶点和边的点集。

CvGraphScanner

图的遍历

typedef struct CvGraphScanner
{
    CvGraphVtx* vtx;       /* current graph vertex (or current edge origin) */
    CvGraphVtx* dst;       /* current graph edge destination vertex */
    CvGraphEdge* edge;     /* current edge */

    CvGraph* graph;        /* the graph */
    CvSeq*   stack;        /* the graph vertex stack */
    int      index;        /* the lower bound of certainly visited vertices */
    int      mask;         /* event mask */
}
CvGraphScanner;

结构 cvGraphScanner 深度遍历整个图。 函数的相关讨论如下(看:StartScanGraph)  

StartScanGraph

创建一结构,用来对图进行深度遍历

CvGraphScanner*  cvCreateGraphScanner( CvGraph* graph, CvGraphVtx* vtx=NULL,
                                       int mask=CV_GRAPH_ALL_ITEMS );
graph 
vtx 
开始遍历的(起始)顶点。如果为 NULL, 便利就从第一个顶点开始(指:顶点序列中,具有最小索引值的顶点)
mask
事件掩码(event mask)代表用户感兴趣的事件(此时 函数 cvNextGraphItem 将控制返回给用户)。这个只可能是 CV_GRAPH_ALL_ITEMS (如果用户对所有的事件都感兴趣的话)或者是下列标志的组合:
CV_GRAPH_VERTEXT -- 在第一次被访问的顶点处停下
CV_GRAPH_TREE_EDGE -- 在 tree edge 处停下(tree edge 指连接最后被访问的顶点与接下来被访问的顶点的边)
CV_GRAPH_BACK_EDGE -- 在 back edge 处停下(back edge 指连接最后被访问的顶点与其在搜索树中祖先的边)
CV_GRAPH_FORWARD_EDGE -- 在 forward edge 处停下 (forward edge 指连接最后被访问的顶点与其在搜索树中后裔的边)
CV_GRAPH_CROSS_EDGE -- 在 cross edge 处停下(cross edge 指连接不同搜索树中或同一搜索树中不同分支的边.只有在有向图中, 才存在着一 概念)
CV_GRAPH_ANY_EDGE -- 在 any edge 处停下(any edge 指 任何边,包括 tree edge, back edge, forward edge, cross edge)
CV_GRAPH_NEW_TREE -- 在每一个新的搜索树开始处停下。首先遍历从起始顶点开始可以访问到的顶点和边,然后查找搜索图中访问不到的顶点或边并恢复遍历。在开始遍历一颗新的树时(包括第一次调用 cvNextGraphItem 时的树),产生 CV_GRAPH_NEW_TREE 事件。

函数 cvCreateGraphScanner 创建一结构用来深度遍历搜索树。函数 cvNextGraphItem 要使用该初始化了的结构 -- 层层遍历的过程。

NextGraphItem

逐层遍历整个图

int cvNextGraphItem( CvGraphScanner* scanner );
scanner 
图的遍历状态。被此函数更新。

函数 cvNextGraphItem 遍历整个图,直到用户感兴趣的事件发生(即:调用 cvCreateGraphScanner 时, mask 对应的事件)或遍历结束。在前面一种情况下,函数返回 参数mask 相应的事件,当再次调用函数时,恢复遍历)。在后一种情况下,返回 CV_GRAPH_OVER(-1)。当 mask 相应的事件为 CV_GRAPH_BACKTRACKING 或 CV_GRAPH_NEW_TEEE 时, 当前正在被访问的顶点被存放在 scanner->vtx 中。如果事件与 边edge 相关,那么 edge 本身被存放在 scanner->edge, 该边的起始顶点存放在 scanner->vtx 中, 尾部节点存放在 scanner->dst 中。

ReleaseGraphScanner

完成图地遍历过程

void cvReleaseGraphScanner( CvGraphScanner** scanner );
scanner 
指向遍历器的指针.

函数 cvGraphScanner 完成图的遍历过程,并释放遍历器的状态。

CV_TREE_NODE_FIELDS

用于树结点类型声明的(助手)宏

#define CV_TREE_NODE_FIELDS(node_type)                          \
    int       flags;         /* micsellaneous flags */          \
    int       header_size;   /* size of sequence header */      \
    struct    node_type* h_prev; /* previous sequence */        \
    struct    node_type* h_next; /* next sequence */            \
    struct    node_type* v_prev; /* 2nd previous sequence */    \
    struct    node_type* v_next; /* 2nd next sequence */

宏 CV_TREE_NODE_FIELDS() 用来声明一层次性结构,例如 CvSeq -- 所有动态结构的基本类型。如果树的节点是由该宏所声明的,那么就可以使用(该部分的)以下函数对树进行相关操作。

CvTreeNodeIterator

打开现存的存储结构或者创建新的文件存储结构

typedef struct CvTreeNodeIterator
{
    const void* node;
    int level;
    int max_level;
}
CvTreeNodeIterator;

结构 CvTreeNodeIterator 用来对树进行遍历。该树的节点是由宏 CV_TREE_NODE_FIELDS 声明。

InitTreeNodeIterator

用来初始化树结点的迭代器

void cvInitTreeNodeIterator( CvTreeNodeIterator* tree_iterator,
                             const void* first, int max_level );
tree_iterator 
初始化了的迭代器
first 
(开始)遍历的第一个节点
max_level 
限制对树进行遍历的最高层(即:第 max_level 层)(假设第一个节点所在的层为第一层)。例如:1 指的是遍历第一个节点所在层,2 指的是遍历第一层和第二层

函数 cvInitTreeNodeIterator 用来初始化树的迭代器。

NextTreeNode

返回当前节点,并将迭代器 iterator 移向当前节点的下一个节点

void* cvNextTreeNode( CvTreeNodeIterator* tree_iterator );
tree_iterator 
初始化了的迭代器

函数 cvNextTreeNode 返回当前节点并且更新迭代器(iterator) -- 并将 iterator 移向(当前节点)下一个节点。换句话说,函数的行为类似于表达式 *p++ (通常的 C 指针 或 C++ 集合迭代器)。 如果没有更多的节点(即:当前节点为最后的节点),则函数返回值为 NULL.

PrevTreeNode

返回当前节点,并将迭代器 iterator 移向当前节点的前一个节点

void* cvPrevTreeNode( CvTreeNodeIterator* tree_iterator );
tree_iterator 
初始化了的迭代器

函数 cvPrevTreeNode 返回当前节点并且更新迭代器(iterator) -- 并将 iterator 移向(当前节点的)前一个节点。换句话说,函数的行为类似于表达式 *p-- (通常的 C 指针 或 C++ 集合迭代器)。 如果没有更多的节点(即:当前节点为头节点),则函数返回值为 NULL.

TreeToNodeSeq

将所有的节点指针(即:指向树结点的指针)收集到线性表 sequence 中

CvSeq* cvTreeToNodeSeq( const void* first, int header_size, CvMemStorage* storage );
first 
初始树结点
header_size
线性表的表头大小,大小通常为 sizeof(CvSeq)

函数 cvTreeToNodeSeq 将树的节点指针挨个的存放到线性表中。存放的顺序以深度为先。

InsertNodeIntoTree

将新的节点插入到树中

void cvInsertNodeIntoTree( void* node, void* parent, void* frame );
node 
待插入的节点
parent 
树中的父节点(即:含有子节点的节点)
frame 
顶部节点。如果 节点parent 等同于 节点frame, 则将节点的域 v_prev 设为 NULL 而不是 parent.

函数 cvInsertNodeIntoTree 将另一个节点插入到树中。函数不分配任何内存,仅仅修改树节点的连接关系。

RemoveNodeFromTree

从树中删除节点

void cvRemoveNodeFromTree( void* node, void* frame );
node 
待删除的节点。
frame 
顶部节点。如果 node->v.prev = NULL 且 node->h.prev = NULL, 则将 frame->v.next 设为 node->h.next

函数 cvRemoveNodeFromTree 从树中删除节点。它不会释放任何内存,仅仅修改树中节点的连接关系

Views
Personal tools