One kind of object that can be stored inside a memory storage is a sequence. Sequences are themselves linked lists of other structures. OpenCV can make sequences out of many different kinds of objects. In this sense you can think of the sequence as something similar to the generic container classes (or container class templates) that exist in various other programming languages. The sequence construct in OpenCV is actually a deque, so it is very fast for random access and for additions and deletions from either end but a little slow for adding and deleting objects in the middle.
The sequence structure itself (see Example 8-1) has some important elements that you
should be aware of. The first, and one you will use often, is total. This is the total number of points or objects in the sequence. The next
four important elements are pointers to other sequences: h_prev,
h_next, v_prev, and v_next. These four
pointers are part of what are called CV_TREE_NODE_FIELDS;
they are used not to indicate elements inside of the sequence but rather to connect
different sequences to one another. Other objects in the OpenCV universe also contain these
tree node fields. Any such objects can be assembled, by means of these pointers, into more
complicated superstructures such as lists, trees, or other graphs. The variables h_prev and h_next can be used
alone to create a simple linked list. The other two, v_prev and v_next, can be used to create
more complex topologies that relate nodes to one another. It is by means of these four
pointers that cvFindContours() will be able to represent
all of the contours it finds in the form of rich structures such as contour trees.
Example 8-1. Internal organization of CvSeq sequence structure
typedef struct CvSeq {
int flags; // miscellaneous flags
int header_size; // size of sequence header
CvSeq* h_prev; // previous sequence
CvSeq* h_next; // next sequence
CvSeq* v_prev; // 2nd previous sequence
CvSeq* v_next // 2nd next sequence
int total; // total number of elements
int elem_size; // size of sequence element in byte
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
CvMem Storage* storage; // where the sequence is stored
CvSeqBlock* free_blocks; // free blocks list
CvSeqBlock* first; // pointer to the first sequence block
}As we have alluded to already, sequences can be returned from various OpenCV functions. In addition to this,
you can, of course, create sequences yourself. Like many objects in OpenCV, there is an
allocator function that will create a sequence for you and return a pointer to the
resulting data structure. This function is called cvCreateSeq().
CvSeq* cvCreateSeq( int seq_flags, int header_size, int elem_size, CvMemStorage* storage );
This function requires some additional flags, which will further specify exactly what
sort of sequence we are creating. In addition it needs to be told the size of the sequence
header itself (which will always be sizeof(CvSeq))[103] and the size of the objects that the sequence will contain. Finally, a memory
storage is needed from which the sequence can allocate memory when new elements are added
to the sequence.
These flags are of three different categories and
can be combined using the bitwise OR operator. The first category determines the type of
objects[104] from which the sequence is to be constructed. Many of these types might look a
bit alien to you, and some are primarily for internal use by other OpenCV functions. Also,
some of the flags are meaningful only for certain kinds of sequences (e.g., CV_SEQ_FLAG_CLOSED is
meaningful only for sequences that in some way represent a polygon).
-
CV_SEQ_ELTYPE_POINT (x,y)
-
CV_SEQ_ELTYPE_CODE Freeman code: 0..7
-
CV_SEQ_ELTYPE_POINT Pointer to a point: &(x,y)
-
CV_SEQ_ELTYPE_INDEX Integer index of a point: #(x,y)
-
CV_SEQ_ELTYPE_GRAPH_EDGE &next_o,&next_d,&vtx_o,&vtx_d
-
CV_SEQ_ELTYPE_GRAPH_VERTEX first_edge, &(x,y)
-
CV_SEQ_ELTYPE_TRIAN_ATR Vertex of the binary tree
-
CV_SEQ_ELTYPE_CONNECTED_COMP Connected component
-
CV_SEQ_ELTYPE_POINT3D (x,y,z)
The second category indicates the nature of the sequence, which can be any of the following.
-
CV_SEQ_KIND_SET A set of objects
-
CV_SEQ_KIND_CURVE A curve defined by the objects
-
CV_SEQ_KIND_BIN_TREE A binary tree of the objects
-
CV_SEQ_KIND_GRAPH A graph with the objects as nodes
The third category consists of additional feature flags that indicate some other property of the sequence.
-
CV_SEQ_FLAG_CLOSED Sequence is closed (polygons)
-
CV_SEQ_FLAG_SIMPLE Sequence is simple (polygons)
-
CV_SEQ_FLAG_CONVEX Sequence is convex (polygons)
-
CV_SEQ_FLAG_HOLE Sequence is a hole (polygons)
void cvClearSeq( CvSeq* seq );
When you want to delete a sequence, you can use cvClearSeq(), a routine that clears all elements of the sequence. However,
this function does not return allocated blocks in the memory store either to the store or
to the system; the memory allocated by the sequence can be reused only by the same
sequence. If you want to retrieve that memory for some other purpose, you must clear the
memory store via cvClearMemStorage().
Often you will find yourself wanting to directly access a particular member of a
sequence. Though there are several ways to do this, the most direct way—and the correct
way to access a randomly chosen element (as opposed to one that you happen to know is at
the ends)—is to use cvGetSeqElem().
char* cvGetSeqElem( seq, index )
More often than not, you will have to cast the return pointer to whatever type you
know the sequence to be. Here is an example usage of cvGetSeqElem() to print the elements in a sequence of points (such as might
be returned by cvFindContours(), which we will get to
shortly):
for( int i=0; i<seq->total; ++i ) {
CvPoint* p = (CvPoint*)cvGetSeqElem ( seq, i );
printf("(%d,%d)\n", p->x, p->y );
}You can also check to see where a particular element is located in a sequence. The
function cvSeqElemIdx() does this for you:
int cvSeqElemIdx( const CvSeq* seq, const void* element, CvSeqBlock** block = NULL );
This check takes a bit of time, so it is not a particularly efficient thing to do (the
time for the search is proportional to the size of the sequence). Note that cvSeqElemIdx() takes as arguments a pointer to your sequence
and a pointer to the element for which you are searching.[105] Optionally, you may also supply a pointer to a sequence memory block pointer.
If this is non-NULL, then the location of the block in
which the sequence element was found will be returned.
Sequences are copied with cvCloneSeq(),
which does a deep copy of a sequence and creates another entirely separate sequence
structure.
CvSeq* cvCloneSeq( const CvSeq* seq, CvMem Storage* storage = NULL )
This routine is actually just a wrapper for the somewhat more general routine cvSeqSlice(). This latter routine can pull out just a
subsection of an array; it can also do either a deep copy or just build a new header to
create an alternate "view" on the same data elements.
CvSeq* cvSeqSlice( const CvSeq* seq, CvSlice slice, CvMemStorage* storage = NULL, int copy_data = 0 );
You will notice that the argument slice to cvSeqSlice() is of type CvSlice. A slice can be defined using either the convenience function
cvSlice(a,b) or the macro CV_WHOLE_SEQ. In the former case, only those elements starting at a and continuing through b
are included in the copy (b may also be set to CV_WHOLE_SEQ_END_INDEX to indicate the end of the array). The
argument copy_data is how we decide if we want a "deep"
copy (i.e., if we want the data elements themselves to be copied and for those new copies
to be the elements of the new sequence).
Slices can be used to specify elements to remove from a sequence using cvSeqRemoveSlice() or to insert into a sequence using cvSeqInsertSlice().
void cvSeqRemoveSlice( CvSeq* seq, CvSlice slice ); void cvSeqInsertSlice( CvSeq * seq, int before_index, const CvArr* from_arr );
With the introduction of a comparison function, it is also possible to sort or search a (sorted) sequence. The comparison function must have the following prototype:
typedef int (*CvCmpFunc)(const void* a, const void* b, void* userdata );
Here a and b are
pointers to elements of the type being sorted, and userdata is just a pointer to any additional data structure that the caller
doing the sorting or searching can provide at the time of execution. The comparison
function should return -1 if a is greater than b, +1 if a is less than b, and
0 if a and
b are equal.
With such a comparison function defined, a sequence can be sorted by cvSeqSort(). The sequence can also be searched for an element
(or for a pointer to an element) elem using cvSeqSearch(). This searching is done in order
O(log n) time if the sequence is already
sorted (is_sorted=1). If the sequence is unsorted, then
the comparison function is not needed and the search will take O(n)
time. On completion, the search will set *elem_idx to
the index of the found element (if it was found at all) and return a pointer to that
element. If the element was not found, then NULL is
returned.
void cvSeqSort( CvSeq* seq, CvCmpFunc func, void* userdata = NULL ); char* cvSeqSearch( CvSeq* seq, const void* elem, CvCmpFunc func, int is_sorted, int* elem_idx, void* userdata = NULL );
A sequence can be inverted (reversed) in a single call with the function cvSeqInvert(). This function does not change the data in any
way, but it reorganizes the sequence so that the elements appear in the opposite
order.
void cvSeqInvert( CvSeq* seq );
OpenCV also supports a method of partitioning a sequence[106] based on a user-supplied criterion via the function cvSeqPartition(). This partitioning uses the same sort of comparison function
as described previously but with the expectation that the function will return a nonzero
value if the two arguments are equal and zero if they are not (i.e., the opposite
convention as is used for searching and sorting).
int cvSeqPartition( const CvSeq* seq, CvMem Storage* storage, CvSeq** labels, CvCmpFunc is_equal, void* userdata );
The partitioning requires a memory storage so that it can allocate memory to
express the output of the partitioning. The argument labels should be a pointer to a sequence pointer. When cvSeqPartition() returns, the result will be that labels will now indicate a sequence of integers that have a
one-to-one correspondence with the elements of the partitioned sequence seq. The values of these integers will be, starting at 0 and
incrementing from there, the "names" of the partitions that the points in seq were to be assigned. The pointer userdata is the usual pointer that is just transparently passed to the
comparison function.
In Figure 8-1, a group of 100 points
are randomly distributed on 100-by-100 canvas. Then cvSeqPartition() is called on these points, where the comparison function is
based on Euclidean distance. The comparison function is set to return true (1) if the
distance is less than or equal to 5 and to return false (0) otherwise. The resulting
clusters are labeled with their integer ordinal from labels.
As stated earlier, a sequence in OpenCV is really a linked list. This means, among other things, that it can be accessed efficiently from either end. As a result, it is natural to use a sequence of this kind as a stack when circumstances call for one. The following six functions, when used in conjunction with the CvSeq structure, implement the behavior required to use the sequence as a stack (more properly, a deque, because these functions allow access to both ends of the list).
char* cvSeqPush( CvSeq* seq, void* element = NULL ); char* cvSeqPushFront( CvSeq* seq, void* element = NULL ); void cvSeqPop( CvSeq* seq, void* element = NULL ); void cvSeqPopFront( CvSeq* seq, void* element = NULL ); void cvSeqPushMulti( CvSeq* seq, void* elements, int count, int in_front = 0 ); void cvSeqPopMulti( CvSeq* seq, void* elements, int count, int in_front = 0 );
The primary modes of accessing the sequence are cvSeqPush(),
cvSeqPushFront(), cvSeqPop(), and cvSeqPopFront(). Because these routines act on the ends of the sequence, all
of them operate in O(1) time (i.e., independent of the size of the
sequence). The Push functions return a pointer to the
element pushed into the sequence, and the Pop functions
will optionally save the popped element if a pointer is provided to a location where the
object can be copied. The cvSeqPushMulti() and cvSeqPopMulti() variants will push or pop several items at a
time. Both take a separate argument to distinguish the front from the back; you can set
in_front to either CV_FRONT
(1) or to CV_BACK (0) and so determine from
where you'll be pushing or popping.
char* cvSeqInsert( CvSeq* seq, int before_index, void* element = NULL ); void cvSeqRemove( CvSeq* seq, int index );
Objects can be inserted into and removed from the middle of a sequence by using cvSeqInsert() and cvSeqRemove(),
respectively, but remember that these are not very fast. On average, they take time
proportional to the total size of the sequence.
One function whose purpose may not be obvious at first glance is cvSetSeqBlockSize(). This routine takes as arguments a
sequence and a new block size, which is the size of blocks that will be allocated out of
the memory store when new elements are needed in the sequence. By making this size big you
are less likely to fragment your sequence across disconnected memory blocks; by making it
small you are less likely to waste memory. The default value is 1,000 bytes, but this can
be changed at any time.[107]
void cvSetSeqBlockSize( CvSeq* seq, Int delta_elems );
When you are working with sequences and you want the highest performance, there are some special methods for accessing and modifying them that (although they require a bit of special care to use) will let you do what you want to do with a minimum of overhead. These functions make use of special structures to keep track of the state of what they are doing; this allows many actions to be done in sequence and the necessary final bookkeeping to be done only after the last action.
For writing, this control structure is called CvSeqWriter. The writer is initialized with the function cvStartWriteSeq() and is "closed" with cvEndWriteSeq(). While the sequence writing is "open", new
elements can be added to the sequence with the macro CV_WRITE_SEQ(). Notice that the writing is done with a macro and not a
function call, which saves even the overhead of entering and exiting that code. Using the
writer is faster than using cvSeqPush(); however, not
all the sequence headers are updated immediately by this macro, so the added element will
be essentially invisible until you are done writing. It will become visible when the
structure is completely updated by cvEndWriteSeq().
If necessary, the structure can be brought up-to-date (without actually closing the
writer) by calling cvFlushSeqWriter().
void cvStartWriteSeq( int seq_flags, int header_size, int elem_size, CvMem Storage* storage, CvSeqWriter* writer ); void cvStartAppendToSeq( CvSeq* seq, CvSeqWriter* writer ); CvSeq* cvEndWriteSeq( CvSeqWriter* writer ); void cvFlushSeqWriter( CvSeqWriter* writer ); CV_WRITE_SEQ_ELEM( elem, writer ) CV_WRITE_SEQ_ELEM_VAR( elem_ptr, writer )
The arguments to these functions are largely self-explanatory. The seq_flags, header_size, and elem_size arguments to cvStartWriteSeq()
are identical to the corresponding arguments to cvCreateSeq(). The function cvStartAppendToSeq() initializes the writer to begin adding new elements to
the end of the existing sequence seq. The macro
CV_WRITE_SEQ_ELEM() requires the element to be
written (e.g., a CvPoint) and a pointer to the writer;
a new element is added to the sequence and the element elem is copied into that new element.
Putting these all together into a simple example, we will create a writer and append a hundred random points drawn from a 320-by-240 rectangle to the new sequence.
CvSeqWriter writer;
cvStartWriteSeq( CV_32SC2, sizeof(CvSeq), sizeof(CvPoint), storage, &writer );
for( i = 0; i < 100; i++ )
{
CvPoint pt; pt.x = rand()%320; pt.y = rand()%240;
CV_WRITE_SEQ_ELEM( pt, writer );
}
CvSeq* seq = cvEndWriteSeq( &writer );For reading, there is a similar set of functions and a few more associated macros.
void cvStartReadSeq( const CvSeq* seq, CvSeqReader* reader, int reverse = 0 ); int cvGetSeqReaderPos( CvSeqReader* reader ); void cvSetSeqReaderPos( CvSeqReader* reader, int index, int is_relative = 0 ); CV_NEXT_SEQ_ELEM( elem_size, reader ) CV_PREV_SEQ_ELEM( elem_size, reader ) CV_READ_SEQ_ELEM( elem, reader ) CV_REV_READ_SEQ_ELEM( elem, reader )
The structure CvSeqReader, which is analogous
to CvSeqWriter, is initialized with the
function cvStartReadSeq(). The argument reverse allows for the sequence to be read either in "normal"
order (reverse=0) or backwards (reverse=1). The function cvGetSeqReaderPos() returns an integer indicating the current location of the
reader in the sequence. Finally, cvSetSeqReaderPos()
allows the reader to "seek" to an arbitrary location in the sequence. If the argument
is_relative is nonzero, then the index will be
interpreted as a relative offset to the current reader position. In this case, the index
may be positive or negative.
The two macros CV_NEXT_SEQ_ELEM() and CV_PREV_SEQ_ELEM() simply move the reader forward or backward
one step in the sequence. They do no error checking and thus cannot help you if you
unintentionally step off the end of the sequence. The macros CV_READ_SEQ_ELEM() and CV_REV_READ_SEQ_ELEM() are used to read from the sequence. They will both
copy the "current" element at which the reader is pointed onto the variable elem and then step the reader one step (forward or backward,
respectively). These latter two macros expect just the name of the variable to be copied
to; the address of that variable will be computed inside of the macro.
You may often find yourself wanting to convert a sequence, usually full of points, into an array.
void* cvCvtSeqToArray( const CvSeq* seq, void* elements, CvSlice slice = CV_WHOLE_SEQ ); CvSeq* cvMakeSeqHeaderForArray( int seq_type, int header_size, int elem_size, void* elements, int total, CvSeq* seq, CvSeqBlock* block );
The function cvCvtSeqToArray() copies the content
of the sequence into a continuous memory array. This means that if you have a sequence of
20 elements of type CvPoint then the function will
require a pointer, elements, to enough space for 40
integers. The third (optional) argument is slice, which
can be either an object of type CvSlice or the macro
CV_WHOLE_SEQ (the latter is the default value). If
CV_WHOLE_SEQ is selected, then the entire sequence is
copied.The return value of cvCvtSeqToArray() is a void* pointer which is equal to the elements pointer
provided when the function was called.
The opposite functionality to cvCvtSeqToArray() is
implemented by cvMakeSeqHeaderForArray(). In this case,
you can build a sequence from an existing array of data. The function's first few
arguments are identical to those of cvCreateSeq(). In
addition to requiring the data (elements) to copy in
and the number (total) of data items, you must provide
a sequence header (seq) and a sequence memory block
structure (block). Sequences created in this way are not exactly the same as sequences created by
other methods. In particular, you will not be able to subsequently alter the data in the
created sequence.
[103] Obviously, there must be some other value to which you can set this argument or it
would not exist. This argument is needed because sometimes we want to extend the
CvSeq "class". To extend CvSeq, you create your own struct
using the CV_SEQUENCE_FIELDS() macro in the
structure definition of the new type; note that, when using an extended structure, the
size of that structure must be passed. This is a pretty esoteric activity in which
only serious gurus are likely to participate.
[104] The types in this first listing are used only rarely. To create a sequence whose
elements are tuples of numbers, use CV_32SC2,
CV_32FC4, etc. To create a sequence of elements of your own type, simply
pass 0 and specify the correct elem_size.
[105] Actually, it would be more accurate to say that cvSeqElemIdx() takes the pointer being searched for.
This is because cvSeqElemIdx() is not searching for
an element in the sequence that is equal to *element; rather, it is searching for the element that is at the location
given by element.
[106] For more on partitioning, see Hastie, Tibshirani, and Friedman [Hastie01].
[107] Effective with the beta 5 version of OpenCV, this size is automatically increased if the sequence becomes big; hence you'll not need to worry about it under normal circumstances.