Оглавление
1. OpenCV шаг за шагом. Введение.
2. Установка.
3. Hello World.
4. Загрузка картинки.
...
28. Преобразование Хафа
29. Интегральное изображение
30. Трансформация изображения — аффинные преобразования, гомография
31. Типы данных OpenCV — хранилище памяти, последовательность

На шаге про преобразование Хафа, вы, возможно, обратили внимание, на непонятные типы данных CvMemStorage и CvSeq, которые использовались в примерах использования функций cvHoughLines2() и cvHoughCircles()

OpenCV использует сущность хранилища памяти (memory storage — CvMemStorage) в своих методах, для которых требуется хранить динамические объекты. Фактически, хранилище памяти — это связанный список блоков памяти.

Типы CvMemStorage и CvSeq объявлены в cxtypes.h (2.1) или modules\core\include\opencv2\core\types_c.h (2.2 и далее)

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

#define CV_STORAGE_MAGIC_VAL    0x42890000

typedef struct CvMemStorage
{
    int signature;
    CvMemBlock* bottom;           /* First allocated block.                   */
    CvMemBlock* top;              /* Current memory block - top of the stack. */
    struct  CvMemStorage* parent; /* We get new blocks from parent as needed. */
    int block_size;               /* Block size.                              */
    int free_space;               /* Remaining free space in current block.   */
}
CvMemStorage;

#define CV_IS_STORAGE(storage)  \
    ((storage) != NULL &&       \
    (((CvMemStorage*)(storage))->signature & CV_MAGIC_MASK) == CV_STORAGE_MAGIC_VAL)


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


/*********************************** Sequence *******************************************/

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.           */
    schar* data;              /* Pointer to the first element of the block. */
}
CvSeqBlock;


#define CV_TREE_NODE_FIELDS(node_type)                               \
    int       flags;             /* Miscellaneous 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.       */

/*
   Read/Write sequence.
   Elements can be dynamically inserted to or deleted from the sequence.
*/
#define CV_SEQUENCE_FIELDS()                                              \
    CV_TREE_NODE_FIELDS(CvSeq);                                           \
    int       total;          /* Total number of elements.            */  \
    int       elem_size;      /* Size of sequence element in bytes.   */  \
    schar*    block_max;      /* Maximal bound of the last block.     */  \
    schar*    ptr;            /* Current write pointer.               */  \
    int       delta_elems;    /* Grow seq this many at a time.        */  \
    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;

Методы для работы с хранилищем памяти:

CVAPI(CvMemStorage*)  cvCreateMemStorage( int block_size CV_DEFAULT(0));

— создание хранилища памяти
block_size — размер блока хранилища в байтах (если 0 — то используется значение по-умолчанию: 64Kb)

функция создаёт хранилище памяти и возвращает указатель на него. В исходном положении все поля заголовка хранилища, кроме block_size, равны 0.

CVAPI(void)  cvReleaseMemStorage( CvMemStorage** storage );

— освобождает хранилище памяти
storage — двойной указатель на хранилище памяти

CVAPI(void)  cvClearMemStorage( CvMemStorage* storage );

— очищает хранилище памяти
storage — указатель на хранилище памяти

функция не освобождает память.

Один тип объектов, которые могут храниться в хранилище памяти — это последовательность (sequence).
Сами по себе, последовательности являются связанными списками других структур.
Фактически, последовательность — это двусторонняя очередь (deque)

Функции OpenCV для работы с последовательностью:

CVAPI(CvSeq*)  cvCreateSeq( int seq_flags, int header_size,
                            int elem_size, CvMemStorage* storage );

— создание последовательности
seq_flags — флаг создаваемой последовательности (можно комбинировать используя оператор побитового ИЛИ):

#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
#define CV_SEQ_ELTYPE_PTR            CV_USRTYPE1
#define CV_SEQ_ELTYPE_PPOINT         CV_SEQ_ELTYPE_PTR  /* &(x,y) */
#define CV_SEQ_ELTYPE_INDEX          CV_32SC1  /* #(x,y) */
#define CV_SEQ_ELTYPE_GRAPH_EDGE     0  /* &next_o, &next_d, &vtx_o, &vtx_d */
#define CV_SEQ_ELTYPE_GRAPH_VERTEX   0  /* first_edge, &(x,y) */
#define CV_SEQ_ELTYPE_TRIAN_ATR      0  /* vertex of the binary tree   */
#define CV_SEQ_ELTYPE_CONNECTED_COMP 0  /* connected component  */
#define CV_SEQ_ELTYPE_POINT3D        CV_32FC3  /* (x,y,z)  */

#define CV_SEQ_KIND_BITS        3
#define CV_SEQ_KIND_MASK        (((1 << CV_SEQ_KIND_BITS) - 1)<<CV_SEQ_ELTYPE_BITS)

/* types of sequences */
#define CV_SEQ_KIND_GENERIC     (0 << CV_SEQ_ELTYPE_BITS)
#define CV_SEQ_KIND_CURVE       (1 << CV_SEQ_ELTYPE_BITS)
#define CV_SEQ_KIND_BIN_TREE    (2 << CV_SEQ_ELTYPE_BITS)

/* types of sparse sequences (sets) */
#define CV_SEQ_KIND_GRAPH       (3 << CV_SEQ_ELTYPE_BITS)
#define CV_SEQ_KIND_SUBDIV2D    (4 << CV_SEQ_ELTYPE_BITS)

header_size — размер заголовка последовательности (должен быть больше или равен sizeof(CvSeq))
elem_size — размер элемента последовательности в байтах (размер должен соответствовать типу последовательности. Например, для последовательности точек: тип элемента CV_SEQ_ELTYPE_POINT, то параметр elem_size должен быть sizeof(CvPoint) )
storage — указатель на хранилище памяти последовательности

функция создаёт последовательность и возвращает указатель на неё.

CVAPI(void)  cvClearSeq( CvSeq* seq );

— очищает последовательность
seq — указатель на последовательность

функция удаляет все элементы из последовательности (не возвращает память, занимаемую блоками, т.о. память снова может быть использована последовательностью ).

Методы для работы с последовательностью:

CVAPI(schar*)  cvSeqPush( CvSeq* seq, const void* element CV_DEFAULT(NULL));

— добавление нового элемента в последовательность
seq — указатель на последовательность
element — указатель на элемент для добавления

функция добавляет элемент в конец последовательности и возвращает указатель на этот элемент. Если функции передаётся нулевой указатель (NULL), то функция просто выделяет место для еще одного элемента.

CVAPI(schar*)  cvSeqPushFront( CvSeq* seq, const void* element CV_DEFAULT(NULL));

— добавление нового элемента в начало последовательности
seq — указатель на последовательность
element — указатель на элемент для добавления

По действию, функция аналогична функции cvSeqPush(), но добавляет новый элемент не в конец, а в начало последовательности.

CVAPI(void)  cvSeqPop( CvSeq* seq, void* element CV_DEFAULT(NULL));

— удаляет последний элемент последовательности

CVAPI(void)  cvSeqPopFront( CvSeq* seq, void* element CV_DEFAULT(NULL));

— удаляет первый элемент последовательности

#define CV_FRONT 1
#define CV_BACK 0

CVAPI(void)  cvSeqPushMulti( CvSeq* seq, const void* elements,
                             int count, int in_front CV_DEFAULT(0) );

— помещает несколько новых элементов в конец/начало последовательности

seq — последовательность
elements — добавляемые элементы
count — число элементов для добавления
in_front — флаг, определяющий куда будут добавлены элементы:
CV_BACK — в конец последовательности
CV_FRONT — в начало последовательности

CVAPI(void)  cvSeqPopMulti( CvSeq* seq, void* elements,
                            int count, int in_front CV_DEFAULT(0) );

— удаляет несколько элементов с конца или начала последовательности
seq — последовательность
elements — удаляемые элементы
count — число элементов для удаления
in_front — флаг, определяющий откуда будут удалены элементы

CVAPI(schar*)  cvSeqInsert( CvSeq* seq, int before_index,
                            const void* element CV_DEFAULT(NULL));

— добавление элементов в середину последовательности

// cvSeqInsert(seq,0,elem) == cvSeqPushFront(seq,elem)

CVAPI(void)  cvSeqRemove( CvSeq* seq, int index );

— удаляет элемент из середины последовательности

Непосредственный доступ к элементам последовательности:

CVAPI(schar*)  cvGetSeqElem( const CvSeq* seq, int index );

— возвращает указатель на элемент последовательности в соответствии с его номером(индексом).
seq — последовательность
index — номер элемента

Пример обхода всех элементов последовательности точек и отображение их координат:

for( int i=0; i<seq->total; ++i ) {
	CvPoint* p = (CvPoint*)cvGetSeqElem ( seq, i );
	printf("(%d,%d)\n", p->x, p->y );
}

И ещё два способа получения координат точек последовательности:

// получение координат точек
for( int i=0; i<seq->total; ++i ) {
	CvPoint* p = CV_GET_SEQ_ELEM( CvPoint, seq, i );
	printf(" (%d,%d)\n", p->x, p->y );
}

// объявление считывалки точек
CvSeqReader reader;
// инициализация считывалки точек
cvStartReadSeq( result, &reader, 0 );
// две точки
CvPoint pt[2];

// достаем точки из последовательности точек и рисуем линии
for (int i=0;i<result->total-1;i++) {
	CV_READ_SEQ_ELEM( pt[0], reader );
	CV_READ_SEQ_ELEM( pt[1], reader );
	cvLine(img, pt[0], pt[1], CV_RGB(255,0,0));
}

Указатели на хранилище памяти и последовательности используются многими функциями OpenCV, для сохранения в них результатов своей работы (найденных контуров, полученных ключевых точек и т.п.)

Пример использования последовательности можно посмотреть на шаге про преобразование Хафа, в примерах использования функций cvHoughLines2() или cvHoughCircles()

total хранит общее число элементов последовательности и поэтому, перебор и отображение всех кругов, найденных методом cvHoughCircles() производится циклом:

// пробегаемся по всем элементам последовательности
for( int i = 0; i < results->total; i++ ) {
	// получение i-го элемента последовательности
	float* p = (float*) cvGetSeqElem( results, i );
	CvPoint pt = cvPoint( cvRound( p[0] ), cvRound( p[1] ) );
	// рисуем круг
	cvCircle( src, pt, cvRound( p[2] ), CV_RGB(0xff,0,0) );
}

Далее: 32. Нахождение контуров и операции с ними