|
[编辑]
内存存储（memory storage)[编辑]
CvMemStorageGrowing 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 );
函数 cvCreateMemStorage 创建一内存块并返回指向块首的指针。起初，存储块是空的。头部（即：header)的所有域值都为 0，除了 block_size 外. [编辑]
CreateChildMemStorage创建子内存块 CvMemStorage* cvCreateChildMemStorage( CvMemStorage* 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 );
函数 cvReleaseMemStorage 释放所有的存储（内存）块 或者 将它们返回给各自的 parent（如果需要的话）。 接下来再释放 header块（即：释放头指针 head 指向的块 = free(head)）并清除指向该块的指针（即：head = NULL)。在释放作为 parent 的块之前，先清除各自的 child 块。 [编辑]
ClearMemStorage清空内存存储块 void cvClearMemStorage( CvMemStorage* storage );
函数 cvClearMemStorage 将存储块的 top 置到存储块的头部（注：清空存储块中的存储内容）。该函数并不释放内存（仅清空内存）。假使该内存块有一个父内存块（即：存在一内存块与其有父子关系），则函数就将所有的块返回给其 parent. [编辑]
MemStorageAlloc在存储块中分配一内存缓冲区 void* cvMemStorageAlloc( CvMemStorage* storage, size_t 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 );
函数 cvMemStorageAlloString 在存储块中创建了一字符串的拷贝。它返回一结构，该结构包含字符串的长度（该长度或通过用户传递，或通过计算得到）和指向被拷贝了的字符串的指针。 [编辑]
SaveMemStoragePos保存内存块的位置（地址） void cvSaveMemStoragePos( const CvMemStorage* storage, CvMemStoragePos* pos );
函数 cvSaveMemStoragePos 将存储块的当前位置保存到参数 pos 中。 函数 cvRestoreMemStoragePos 可进一步获取该位置（地址）。 [编辑]
RestoreMemStoragePos恢复内存存储块的位置 void cvRestoreMemStoragePos( CvMemStorage* storage, CvMemStoragePos* 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 );
函数 cvCreateSeq 创建一序列并且返回指向该序列的指针。函数在存储块中分配序列的头部作为一个连续躯体，并且设置结构的 flags域, elem_size域, header_size域 和 storage域 的值为被传递过来的值，设置 delta_elems 为默认值（可通过函数 cvSetSeqBlockSize 重新对其赋值），清空其他的头 部域，包括前sizeof(CvSeq) 个字节的空间。 [编辑]
SetSeqBlockSize设置序列块的大小 void cvSetSeqBlockSize( CvSeq* seq, int delta_elems );
函数 cvSetSeqBlockSize 会对内存分配的粒度产生影响。 当序列缓冲区中空间消耗完时，函数为 delta_elems 个序列元素分配空间。如果新分配的空间与 之前分配的空间相邻的话，这两个块就合并，否则，就创建了一个新的序列快。因此，参数值越大，序列中出现碎片的可能性就越小，不过内存中更多的空间将被浪费。当序列被创建后，参数 delta_elems 大小将被设置为 默认大小（1K).之后， 就可随时调用该函数，并影响内存分配。 函数可以修改被传递过来的参数值，以满足内存块的大小限制 。 [编辑]
SeqPush添加元素到序列的尾部 char* cvSeqPush( CvSeq* seq, void* element=NULL );
函数 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 );
函数 cvSeqPop 从序列中删除一元素。如果序列已经为空，就报告一错误。函数时间复杂度为 O(1). [编辑]
SeqPushFront在序列头部添加元素 char* cvSeqPushFront( CvSeq* seq, void* element=NULL );
函数 cvSeqPushFront 类似于 cvSeqPush， 不过是在序列头部添加元素。时间复杂度为O(1). [编辑]
SeqPopFront删除序列的头部元素 void cvSeqPopFront( CvSeq* seq, void* element=NULL );
函数 cvSeqPopFront 删除序列的头部元素。如果序列已经为空，就报告一错误。函数时间复杂度为 O(1). [编辑]
SeqPushMulti添加多个元素到序列尾部或头部。 void cvSeqPushMulti( CvSeq* seq, void* elements, int count, int in_front=0 );
函数 cvSeqPushMulti 在序列头部或尾部添加多个元素。 元素按输入数组中的顺序被添加到序列中，不过它们可以添加到不同的序列中 [编辑]
SeqPopMulti删除多个序列头部或尾部的元素 void cvSeqPopMulti( CvSeq* seq, void* elements, int count, int in_front=0 );
函数 cvSeqPopMulti 删除多个序列头部或尾部的元素。 如果待删除的元素个数超过了序列中的元素总数，则函数删除尽可能多的元素 。 [编辑]
SeqInsert在序列中添加元素 char* cvSeqInsert( CvSeq* seq, int before_index, void* element=NULL );
函数 cvSeqInsert 移动 从被插入的位置到序列尾部元素所在的位置的所有元素，如果 指针 element 不位 null, 则拷贝 element 中的元素到指定位置。函数返回指向被插入元素的指针。 [编辑]
SeqRemove从序列中删除指定的元素。 void cvSeqRemove( CvSeq* seq, int index );
函数 cvSeqRemove 删除seq中指定索引（位置）的元素。如果这个索引超出序列的元素个数，会报告出错。企图从空序列中删除元素，函数也将报告错误。函数通过移动序列中的元素来删除被索引的元素。 [编辑]
ClearSeq清空序列 void cvClearSeq( CvSeq* 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) )
函数 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 );
函数 cvSeqElemIdx 返回元素的索引，如果该元素不存在这个序列中，则返回一负数。 [编辑]
cvSeqToArray拷贝序列中的元素到一个连续的内存块中 void* cvCvtSeqToArray( const CvSeq* seq, void* elements, CvSlice slice=CV_WHOLE_SEQ );
函数 cvCvtSeqToArray 拷贝整个序列或部分序列到指定的缓冲区中，并返回指向该缓冲区的指针. [编辑]
MakeSeqHeaderForArray构建序列 CvSeq* cvMakeSeqHeaderForArray( int seq_type, int header_size, int elem_size,
void* elements, int total,
CvSeq* seq, CvSeqBlock* block );
函数 cvMakeSeqHeaderForArray 初始化序列的头部。序列块由用户分配（例如：在栈上）。该函数不拷贝数据。创建的序列只包含一个块，和一个 NULL指针，因此可以读取指针，但试图将元素添加到序列中则多数会引发错误。 [编辑]
SeqSlice为各个序列碎片建立头 CvSeq* cvSeqSlice( const CvSeq* seq, CvSlice slice,
CvMemStorage* storage=NULL, int copy_data=0 );
函数 cvSeqSlice 创建一序列，该序列表示输入序列中特定的一部分 （slice),。新序列要么与原序列共享元素要么拥有自己的一份拷贝。因此，如果 有人需要去 处理 该部分序列，但函数却没有 slice 参数， 则使用该函数去获取该序列。. [编辑]
CloneSeq创建序列的一份拷贝 CvSeq* cvCloneSeq( const CvSeq* seq, CvMemStorage* storage=NULL );
函数 cvCloneSeq 创建输入序列的一份完全拷贝。调用函数 cvCloneSeq (seq, storage) 等同于调用 cvSeqSlice(seq, CV_WHOLE_SEQ, storage, 1). [编辑]
SeqRemoveSlice删除序列的 slice部分 void cvSeqRemoveSlice( CvSeq* seq, CvSlice slice );
函数 cvSeqRemoveSlice 删除序列中的 slice 部分 [编辑]
SeqInsertSlice在序列中插入一数组 void cvSeqInsertSlice( CvSeq* seq, int before_index, const CvArr* from_arr );
函数 cvSeqInsertSlice 在指定位置插入 来自数组from_arr中 所有元素。数组 from_arr 可以是一个 矩阵也可以是另外一个 序列。 [编辑]
SeqInvert将序列中的元素进行逆序操作 void cvSeqInvert( CvSeq* 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 );
函数 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 );
函数 cvSeqSearch 查找序列中的元素。如果序列已被排序，则使用二分查找（时间复杂度为 O(log(N))否则使用简单线性查找。若查找的元素不存在，函数返回 NULL 指针，而索引值设置为序列中的元素数（如果使用的是线性查找）或 满足表达式 seq(i) > elem 的最小的 i. [编辑]
StartAppendToSeq将数据写入序列中，并初始化该过程 void cvStartAppendToSeq( CvSeq* seq, CvSeqWriter* 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 );
函数 cvStartWriteSeq 是 函数 cvCreateSeq 和函数 cvStartAppendToSeq 的组合。 指向被创建的序列的指针存放在 writer->seq 中, 通过函数cvEndWriteSeq 返回（因当在最后调用） [编辑]
EndWriteSeq完成写入操作 CvSeq* cvEndWriteSeq( CvSeqWriter* writer );
函数 cvEndWriteSeq 完成写入操作并返回指向被写入元素的序列的地址。同时，函数会截取最后那个不完整的序列块，将块的剩馀部分返回到内存中之后，序列就可以被安全的读和写。 [编辑]
FlushSeqWriter根据写入状态，刷新序列头部 void cvFlushSeqWriter( CvSeqWriter* writer );
函数 cvFlushSeqWriter 用来使用户在写入过程中每当需要时读取序列元素，比如说，核查制定的条件。函数更新序列的头部，从而使读取序列中的数据成为可能。不过，写入并没有被关闭，为的是随时都可以将数据写入序列。在有些算法中，经常需要刷新，考虑使用 cvSeqPush 代替该函数。 [编辑]
StartReadSeq初始化序列中的读取过程 void cvStartReadSeq( const CvSeq* seq, CvSeqReader* reader, int 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 );
函数 cvGetSeqReaderPos 返回当前的 reader 位置 （在 0 到 reader->seq->total - 1 中） [编辑]
SetSeqReaderPos移动读取器到指定的位置。 void cvSetSeqReaderPos( CvSeqReader* reader, int index, int is_relative=0 );
函数 cvSetSeqReaderPos 将 read 的位置移动到绝对位置，或相对于当前的位置（相对位置） [编辑]
集合[编辑]
CvSetCollection 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 );
函数 CvCreateSet 创建一具有特定头部节点大小和元素类型的空集。并返回指向该集合的指针。 [编辑]
SetAdd占用集合中的一个节点 int cvSetAdd( CvSet* set_header, CvSetElem* elem=NULL, CvSetElem** inserted_elem=NULL );
函数 cvSetAdd 分配一新的节点，将输入数据拷贝给它（可选），并且返回指向该节点的指针和节点的索引值。索引值可通过节点的flags域的低位中获得。函数的时间复杂度为 O(1), 不过，存在着一个函数可快速的分配内存。（见 cvSetNew) [编辑]
SetRemove从点集中删除元素 void cvSetRemove( CvSet* set_header, int index );
函数 cvSetRemove 从点集中删除一具有特定索引值的元素。如果指定位置的节点为空，函数将什么都不做。函数的时间复杂度为 O(1), 不过,存在一函数可更快速的完成该操作，该函数就是 cvSetRemoveByPtr [编辑]
SetNew添加元素到点集中 CvSetElem* cvSetNew( CvSet* set_header );
函数 cvSetNew 是 cvSetAdd 的变体，内联函数。它占用一新节点，并返回指向该节点的指针而不是索引。 [编辑]
SetRemoveByPtr删除指针指向的集合元素 void cvSetRemoveByPtr( CvSet* set_header, void* elem );
函数 cvSetRemoveByPtr 是一内联函数，是函数 cvSetRemove 轻微变化而来的。该函数并不会检查节点是否为空 -- 用户负责这一检查。 [编辑]
GetSetElem通过索引值查找相应的集合元素 CvSetElem* cvGetSetElem( const CvSet* set_header, int index );
函数 cvGetSetElem 通过索引值查找相应的元素。函数返回指向该元素的指针，如果索引值无效或相应的节点为空，则返回 0。 若函数使用 cvGetSeqElem 去查找节点，则函数支持负的索引值。 [编辑]
ClearSet清空点集 void cvClearSet( CvSet* 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 );
函数 cvCreateGraph 创建一空图并且返回指向该图的指针。 [编辑]
GraphAddVtx插入一顶点到图中 int cvGraphAddVtx( CvGraph* graph, const CvGraphVtx* vtx=NULL,
CvGraphVtx** inserted_vtx=NULL );
函数 cvGraphAddVtx 将一顶点加入到图中，并返回定点的索引 [编辑]
GraphRemoveVtx通过索引从图中删除一顶点 int cvGraphRemoveVtx( CvGraph* graph, int index );
函数 cvGraphRemoveAddVtx 从图中删除一顶点，连同删除含有此顶点的边。如果输入的顶点不属于该图的话，将报告删除出错（不存在而无法删除）。返回值为被删除的边数，如果顶点不属于该图的话，返回 -1。 [编辑]
GraphRemoveVtxByPtr通过指针从图中删除一顶点 int cvGraphRemoveVtxByPtr( CvGraph* graph, CvGraphVtx* vtx );
函数 cvGraphRemoveVtxByPtr 从图中删除一顶点，连同删除含有此顶点的边。如果输入的顶点不属于该图的话，将报告删除出错（不存在而无法删除）。返回值为被删除的边数，如果顶点不属于该图的话，返回 -1。 [编辑]
GetGraphVtx通过索引值查找图的相应顶点 CvGraphVtx* cvGetGraphVtx( CvGraph* graph, int vtx_idx );
函数 cvGetGraphVtx 通过索引值查找对应的顶点，并返回指向该顶点的指针，如果不存在则返回 NULL. [编辑]
GraphVtxIdx返回定点相应的索引值 int cvGraphVtxIdx( CvGraph* graph, CvGraphVtx* vtx );
函数 cvGraphVtxIdx 返回与顶点相应的索引值 [编辑]
GraphAddEdge通过索引值在图中加入一条边 int cvGraphAddEdge( CvGraph* graph, int start_idx, int end_idx,
const CvGraphEdge* edge=NULL, CvGraphEdge** inserted_edge=NULL );
函数 cvGraphAddEdge 连接两特定的顶点。如果该边成功地加入到图中，返回 1； 如果连接两顶点的边已经存在，返回 0； 如果顶点没被发现（不存在）或者起始顶点和尾部顶点是同一个定点，或其他特殊情况，返回 -1。 如果是后者（即：返回值为负），函数默认的报告一个错误。 [编辑]
GraphAddEdgeByPtr通过指针在图中加入一条边 int cvGraphAddEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx,
const CvGraphEdge* edge=NULL, CvGraphEdge** inserted_edge=NULL );
函数 cvGraphAddEdge 连接两特定的顶点。如果该边成功地加入到图中，返回 1； 如果连接两顶点的边已经存在，返回 0； 如果顶点没被发现（不存在）或者起始顶点和尾部顶点是同一个定点，或其他特殊情况，返回 -1。 如果是后者（即：返回值为负），函数默认的报告一个错误 [编辑]
GraphRemoveEdge通过索引值从图中删除顶点 void cvGraphRemoveEdge( CvGraph* graph, int start_idx, int end_idx );
函数 cvGraphRemoveEdge 删除连接两特定顶点的边。若两顶点并没有相连接（即：不存在由这两个顶点连接的边），函数什么都不做。 [编辑]
GraphRemoveEdgeByPtr通过指针从图中删除边 void cvGraphRemoveEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx );
函数 cvGraphRemoveEdgeByPtr 删除连接两特定顶点的边。若两顶点并没有相连接（即：不存在由这两个顶点连接的边），函数什么都不做。 [编辑]
FindGraphEdge通过索引值在图中查找相应的边 CvGraphEdge* cvFindGraphEdge( const CvGraph* graph, int start_idx, int end_idx ); #define cvGraphFindEdge cvFindGraphEdge
函数 cvFindGraphEdge 查找与两特定顶点相对应的边，并返回指向该边的指针。如果该边不存在，返回 NULL. [编辑]
FindGraphEdgeByPtr通过指针在图中查找相应的边 CvGraphEdge* cvFindGraphEdgeByPtr( const CvGraph* graph, const CvGraphVtx* start_vtx,
const CvGraphVtx* end_vtx );
#define cvGraphFindEdgeByPtr cvFindGraphEdgeByPtr
函数 cvFindGraphEdgeByPtr 查找与两特定顶点相对应的边，并返回指向该边的指针。如果该边不存在，返回 NULL [编辑]
GraphEdgeIdx返回与该边相应的索引值 int cvGraphEdgeIdx( CvGraph* graph, CvGraphEdge* edge );
函数 cvGraphEdgeIdx 返回与边对应的索引值。 [编辑]
GraphVtxDegree（通过索引值）统计与顶点相关联的边数 int cvGraphVtxDegree( const CvGraph* graph, int 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 );
函数 cvGraphVtxDegreeByPtr 返回与特定顶点相关联的边数，包括以该顶点为起始顶点的和尾部顶点的 [编辑]
ClearGraph删除图 void cvClearGraph( CvGraph* graph );
函数 cvClearGraph 删除该图的所有顶点和边。时间复杂度为 O(1). [编辑]
CloneGraph克隆图 CvGraph* cvCloneGraph( const CvGraph* graph, CvMemStorage* 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 );
函数 cvCreateGraphScanner 创建一结构用来深度遍历搜索树。函数 cvNextGraphItem 要使用该初始化了的结构 -- 层层遍历的过程。 [编辑]
NextGraphItem逐层遍历整个图 int cvNextGraphItem( CvGraphScanner* 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 );
函数 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 );
函数 cvInitTreeNodeIterator 用来初始化树的迭代器。 [编辑]
NextTreeNode返回当前节点，并将迭代器 iterator 移向当前节点的下一个节点 void* cvNextTreeNode( CvTreeNodeIterator* tree_iterator );
函数 cvNextTreeNode 返回当前节点并且更新迭代器（iterator) -- 并将 iterator 移向（当前节点）下一个节点。换句话说，函数的行为类似于表达式 *p++ (通常的 C 指针 或 C++ 集合迭代器）。 如果没有更多的节点（即：当前节点为最后的节点），则函数返回值为 NULL. [编辑]
PrevTreeNode返回当前节点，并将迭代器 iterator 移向当前节点的前一个节点 void* cvPrevTreeNode( CvTreeNodeIterator* tree_iterator );
函数 cvPrevTreeNode 返回当前节点并且更新迭代器（iterator) -- 并将 iterator 移向（当前节点的）前一个节点。换句话说，函数的行为类似于表达式 *p-- (通常的 C 指针 或 C++ 集合迭代器）。 如果没有更多的节点（即：当前节点为头节点），则函数返回值为 NULL. [编辑]
TreeToNodeSeq将所有的节点指针（即：指向树结点的指针）收集到线性表 sequence 中 CvSeq* cvTreeToNodeSeq( const void* first, int header_size, CvMemStorage* storage );
函数 cvTreeToNodeSeq 将树的节点指针挨个的存放到线性表中。存放的顺序以深度为先。 [编辑]
InsertNodeIntoTree将新的节点插入到树中 void cvInsertNodeIntoTree( void* node, void* parent, void* frame );
函数 cvInsertNodeIntoTree 将另一个节点插入到树中。函数不分配任何内存，仅仅修改树节点的连接关系。 [编辑]
RemoveNodeFromTree从树中删除节点 void cvRemoveNodeFromTree( void* node, void* frame );
函数 cvRemoveNodeFromTree 从树中删除节点。它不会释放任何内存，仅仅修改树中节点的连接关系 |
|
|
