Sequences

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

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).

The second category indicates the nature of the sequence, which can be any of the following.

The third category consists of additional feature flags that indicate some other property of the sequence.

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.