Динамические структуры

Материал из CompVision

CvMemStorage

Структура данных с динамически изменяемым объемом.

typedef struct CvMemStorage
{
    struct CvMemBlock* bottom;/* указатель на начало списка блоков */
    struct CvMemBlock* top; /* указатель на используемый в данный момент блок */
    struct CvMemStorage* parent; /* откуда занимать блоки (указатель на родителя)*/
    int block_size; /* размер блока */
    int free_space; /* свобоно в блоке top */
} CvMemStorage;

CvMemStorage - структура нижнего уровня, используемая для хранения динамически растущих структур данных, таких как последовательности, контуры, графы, и т.д. (sequences, contours, graphs, subdivisions).

CvMemStorage организована как список блоков памяти равного размера - поле bottom - указатель на начало списка блоков, и top - указатель на используемый в данный момент блок (не обязательно последний блок списка). Все блоки между bottom и top, не включая top, считаются полностью занятыми; все блоки между top и последним блоком, не включая top, считают свободными и top,считается частично занятым - free_space, содержит число свободных байтов, оставшихся в конце блока top.

Новый буфер памяти, который может быть выделен явно функцией MemStorageAlloc или неявно высокоуровневыми функциями, такими как SeqPush, GraphAddEdge, и т.д., всегда начиная с конца текущего блока, если он там помещается. После распределения free_space - уменьшается на величину, равную размеру выделенного блока плюс некоторое значение, чтобы сохранить выравнивание. Когда распределенный буфер не вписывается в доступную часть блока top, следующий блок памяти принимается как top, и free_space становится равным размеру целого блока.

Если нет больше свободных блоков, выделяется новый блок (или заимствуется от родителя, см. CreateChildMemStorage), и добавляется в конец списка. Таким образом, память ведет себя как стек с bottom - основание стека и пары (top, free_space) - вершина стека. Вершина стека может быть сохранена через SaveMemStoragePos, восстанавливала через RestoreMemStoragePos, или сброшена через ClearStorage.

CvMemBlock

Структура, используемая как блок памяти.

typedef struct CvMemBlock
{
    struct CvMemBlock* prev; // указатель на предыдущий блок
    struct CvMemBlock* next; // указатель на следующий блок
} CvMemBlock;

Действительные данные в этой структуре идут за заголовком, следовательно доступ к i - тому байту может быть получен при помощи выражения:

((char*)(mem_block_ptr+1))[i]

CvMemStoragePos

Положение вершины стека в CvMemStorage.

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

CvMemStoragePos хранит положение вершины стека может быть сохранена при помощи команды SaveMemStoragePos и восстановлена при помощи RestoreMemStoragePos.

CvSeq

Хранилище последовательности элементов, с возможностью динамического изменения размера.

#define CV_SEQUENCE_FIELDS() \
    int flags; /* вспомогательные флаги */ \
    int header_size; /* размер заголовка последовательности */ \
    struct CvSeq* h_prev; /* указатель на предыдущую последовательность */ \
    struct CvSeq* h_next; /* указатель на следующую последовательность  */ \
    struct CvSeq* v_prev; /* указатель на вторую предыдущую последовательность */ \
    struct CvSeq* v_next; /* указатель на вторую следующую последовательность*/ \
    int total; /* общее количество элементов*/ \
    int elem_size;/* размер элемента последовательности в байтах */ \
    char* block_max;/* максимальная граница последнего блока */ \
    char* ptr; /* текущий указатель записи */ \
    int delta_elems; /* количество выделяемых при росте последовательности элементов*/ \
    CvMemStorage* storage; /* указатель на место, где хранится последовательность */ \
    CvSeqBlock* free_blocks; /* список свободных блоков */ \
    CvSeqBlock* first; /* указатель на первый блок последовательности */
 
typedef struct CvSeq
{
    CV_SEQUENCE_FIELDS()
} CvSeq;

CvSeq является основой для всех динамических структур данных библиотеки OpenCV.

Столь необычное определение функции (с использованием макроса CV_SEQUENCE_FIELDS()) упрощает расширение структуры CvSeq дополнительными параметрами. Для расширения CvSeq пользователь может определить новую структуру и разместить пользовательские поля после стандартных полей CvSeq, включенных в макрос CV_SEQUENCE_FIELDS().

Существует два вида последовательностей - плотные и разреженные. Основным типом для плотных последовательностей является CvSeq такие последовательности используются для представления одномерных массивов - векторов, стеков, очередей и дек (deques) с динамически меняющимся размером. Они не имеют свободного места посередине - если элемент удален из середины последовательности или добавлен в середину последовательности элементы с ближайшего конца сдвигаются. Разреженные последовательности имеют CvSet в качестве базового класса и более детально обсуждаются позже. Они являются последовательностями уздов; каждый из которых может быть как занят, так и свободен (состояние определяется специальным флагом) . Такие последовательности используются для неупорядоченных структур данных, таких как, множества элементов, графы, хеш таблицы и так далее.

Поле header_size содержить действительный размер заголовка последовательности и должен быть больше или равен sizeof(CvSeq).

Поля h_prev, h_next, v_prev, v_next могут быть использованы для создания иерархической структуры из отдельных последовательностей. Поля h_prev и h_next указывают на предыдущую и следующую последовательности того же уровня иерархии, а v_prev and v_next указывают на предыдущую и следующую последовательность по вертикали иерархии, то есть, на родителя и на первого потомка. Однако это только имена полей, и они могут быть использованы по усмотрению пользователя.

Поле first указывает на первый блок последовательности, структура которого описана ниже.

Поле total содержит действительное количество элементов для плотной последовательности и количество выделенных узлов для разреженной.

Поле flags содержит специальную подпись (CV_SEQ_MAGIC_VAL для плотных последовательностей и CV_SET_MAGIC_VAL для разреженных последовательностей) в старших 16 битах и вспомогательную информацию о последовательности в младших. Младшие биты CV_SEQ_ELTYPE_BITS содержат идентификатор типа элемента. Болшинство функций, работающих с последовательностями не используют тип элемента, а пользуются информацией о его рамере, содержащейся в поле elem_size. Если последовательность содержит числовые данные для одного из типов CvMat тогда тип элемента соответствует типу элемнта CvMat, т.е., CV_32SC2 может быть использована для последовательности двумерных точек, CV_32FC1 для последовательности значений с плавающей точкой, и т.д. Макрос CV_SEQ_ELTYPE(seq_header_ptr) возвращает тип элементов последовательности. Функции работающие с числовыми последовательностями проверяют, чтобы elem_size соответствовал размеру используемого типа элементов. Кроме типов, совместимых с CvMat, есть дополнительные типы элементов определенные в заголовочном файле cvtypes.h():

Стандартные типы элементов последовательности:

#define CV_SEQ_ELTYPE_POINT          CV_32SC2  /* (x,y) */
#define CV_SEQ_ELTYPE_CODE           CV_8UC1   /* код фримана: 0..7 */
#define CV_SEQ_ELTYPE_GENERIC        0 /* неопределенный тип */
#define CV_SEQ_ELTYPE_PTR            CV_USRTYPE1 /* =6 */
#define CV_SEQ_ELTYPE_PPOINT         CV_SEQ_ELTYPE_PTR  /* &elem: указатель на элемент другой последовательности */
#define CV_SEQ_ELTYPE_INDEX          CV_32SC1  /* #elem: индекс элемента другой последовательности */
#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  /* вершина бинарного дерева   */
#define CV_SEQ_ELTYPE_CONNECTED_COMP CV_SEQ_ELTYPE_GENERIC  /* связные компоненты */
#define CV_SEQ_ELTYPE_POINT3D        CV_32FC3  /* (x,y,z)  */

Биты CV_SEQ_KIND_BITS определяют вид последовательности:

Стандартные виды последовательностей:

/* общий (неопределенный) вид последовательности */
#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)
 
/* подтипы разреженных последовательностей или множеств */
#define CV_SEQ_KIND_GRAPH       (3 << CV_SEQ_ELTYPE_BITS)
#define CV_SEQ_KIND_SUBDIV2D    (4 << CV_SEQ_ELTYPE_BITS)

Оставшиеся биты используются для идентификации различных свойств, особенных для каждого вида и типа элементов. Например, кривая, составленная из точек (CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE_POINT), вместе с флагом CV_SEQ_FLAG_CLOSED, принадлежит типу CV_SEQ_POLYGON или, если установлены другие флаги, его подтипу. Многие функции обработки контуров проверяют тип входной последовательности и сообщают об ошибке если тип не поддерживается. Файл cvtypes.h() содержит полный список всех поддерживаемых предопределенных типов последовательностей и вспомогательный макрос разработанный для получения последовательностей других типов. Определения составных блоков последовательностей даны далее.

CvSeqBlock

Непрерывный блок последовательности.

typedef struct CvSeqBlock
{
    struct CvSeqBlock* prev; /* указатель на предыдущий блок последовательности */
    struct CvSeqBlock* next; /* указатель на следующий блок последовательности */
    int start_index; /* индекс первого элемента блока + sequence->first->start_index */
    int count; /* количество элементов в блоке */
    char* data; /* указатель на первый элемент блока */
} CvSeqBlock;

Блоки последовательности образуют циклический двусвязный список, такой, что указатели prev и next никогда не равны NULL следующим блоком для последнего блока последовательности будет первый блок, а предыдущим для первого будет последний блок последовательности. Поля startIndex и count помогают отслеживать положение блока в последовательности. Например, Если последовательность состоит из 10 элементов и разбита на 3 блока по 3, 5, и 2 элемента, и у первого блока параметр startIndex = 2, тьогда пары (startIndex, count) для блоков последовательности будут иметь значения (2,3), (5, 5), и (10, 2) соответственно. Параметр startIndex первого блока обычно равен 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)
 
/* вычисляет длину фрагмента последовательности */
int cvSliceLength( CvSlice slice, const CvSeq* seq );

Некоторые функции, работающие с последовательностями, принимают параметр типа CvSlice установленный по умолчанию эквивалентным целой последовательности (CV_WHOLE_SEQ). Как startIndex так и endIndex могут принимать отрицательные значения или превышать размер последовательности length, startIndex может находиться в границах последовательности, и endIndex за границами последовательности. Если они равны, фрагмент принимается пустым (не содержит элементов). Вседствие того, что последовательности обрабатываются как циклические структуры, фрагмент может включать несколько элементов из конца последовательности, за которыми следуют несколько элементов из начала последовательности. Например, cvSlice(-2, 3)() в случае 10-и элементной последовательности выделит 5-и элементный фрагмент, содержащий предпоследний (8th), последний (9th), первый (0th), второй (1th) и третий (2nd) элементы. Функция нормализует аргумент следующим образом: сначала вызывается SliceLength для определения длины фрагмента, затем, startIndex преобразуется аналогично аргументу GetSeqElem (разрешены отрицательные индексы). Обработка фрагмента начинается с нормализованного значения startIndex и продолжается SliceLength элементов (принимая во внимание, циклическую структуру последовательности).

Если функция не принимает аргумент типа CvSlice, но Вам нужно обработать только часть последовательности, при помощи функции SeqSlice может быть извлечена подпоследовательность, или сохранить в непрерывный буфер при помощи CvtSeqToArray (возможно, следующей за MakeSeqHeaderForArray) и работать с ним.

CvSet

Множество узлов.

typedef struct CvSetElem
{
    int flags; /* отрицательный если узел свободен, иначе положительный или равен нулю */
    struct CvSetElem* next_free; /* если узел свободен, то поле указывает на следующий свободный узел */
}
CvSetElem;
 
#define CV_SET_FIELDS()    \
    CV_SEQUENCE_FIELDS()   /* унаследовано от [#CvSeq CvSeq] */ \
    struct CvSetElem* free_elems; /* список свободных узлов */
 
typedef struct CvSet
{
    CV_SET_FIELDS()
} CvSet;

Структура CvSet является базовой для разреженных структур данных OpenCV.

Как следует из сказанного выше, CvSet основывается на CvSeq и добавляет поле free_elems, являющееся списком свободных узлов. Каждый узел множества,независимо свободен он или нет, является элементом последовательности. В отличие от элементов плотных последовательностей, элементы множества (и производных структур) должны начинаться с поля целого типа и должны быть способны разместить элементы структуры CvSetElem, т.к. эти два поля (целое, следующее за указателем) необходимы для организации множества узлов со списком свободных узлов. Если узел свободен, поле flags имеет отрицательное значение (старший бит (знаковый) установлен в единицу), и next_free указывает на следующий свободный узел (на первый свободный узел ссылается поле free_elems стуктуры CvSet). Если узел занят, поле flags имеет положительное значение и содержит индекс узла, который может быть получен при помощи выражений (set_elem->flags CV_SET_ELEM_IDX_MASK), остальное содержимое узла определяется пользователем. В частности, занятые узлы, в отличие от свободных не связаны между собой, таким образом, второе поле может быть использовано как для связывания элементов, так и для каких либо других целей. Для определения свободен данный узел или нет можно использовть макрос CV_IS_SET_ELEM(set_elem_ptr).

Вначале множество и список пусты. Когда множеству требуется новый узел, он берется из списка свободных узлов, который затем обновляется. Если список становится пустым, выделяется новый блок последовательности и все узлы внутри этого блока соединяются в список свободных узлов. Таким образом, поле множества total обозначает общее количество узлов, занятых и свободных. Когда занятый узел освобождается, он добавляется в список свободных узлов. Последний освобожденных узел будет занят первым.

В OpenCV CvSet используется для представления графов (CvGraph), разреженных многомерных массивов (CvSparseMat), и плоских подразделений (subdivisions) CvSubdiv2D.

CvGraph

Взвешенный граф или орграф.

#define CV_GRAPH_VERTEX_FIELDS()    \
    int flags; /* флаги вершины */   \
    struct CvGraphEdge* first; /* первое инцидентное ребро */
 
typedef struct CvGraphVtx
{
    CV_GRAPH_VERTEX_FIELDS()
}
CvGraphVtx;
 
#define CV_GRAPH_EDGE_FIELDS()      \
    int flags; /* флаги ребра */     \
    float weight; /* вес ребра */ \
    struct CvGraphEdge* next[2]; /* следующее ребро в списке инцидентных ребер для начальной (0) */ \
                                  /* и конечной (1) вершин ребра */ \
    struct CvGraphVtx* vtx[2]; /* начальная (0) и конечная (1) вершины ребра */
 
typedef struct CvGraphEdge
{
    CV_GRAPH_EDGE_FIELDS()
}
CvGraphEdge;
 
#define  CV_GRAPH_FIELDS()                  \
    CV_SET_FIELDS() /* множество вершин */   \
    CvSet* edges;   /* множество граней */
 
typedef struct CvGraph
{
    CV_GRAPH_FIELDS()
}
CvGraph;

Структура CvGraph является базовой структурой представления графов в OpenCV.

CvGraph является дочерней структурой CvSet - которая содержит общее описание графа и описание его вершин, и содержит в себе другое множество (CvSet) - содержащее информацию о ребрах графа.

Структуры, при помощи которых описаны вершины, грани, и заголовок графа определены тем же способом как и другие расширяемые структуры OpenCV structures - посредством макросов, которые упрощают расширение и модификацию этих структур. В то время как структуры, описывающие ребра и грани не являются наследниками CvSetElem явно, они удовлетворяют обоим условиям элемента множеств: имея целочисленное поле вначале и помещаются внутри структуры CvSetElem. Поля флагов используются для обозначения занятых граней и ребер, а также для других нужд, например, для обхода графа (см. CreateGraphScanner и др.), таким образом лучше не использовать их напрямую. Граф представлен как множество ребер, каждое из которых содержит список инцидентных (непосредственно соединенных с ним) ребер. Списки инцидентности для разных вершин чередуются, для того чтобы как можно меньше информации было продублировано.

Граф может быть ориентированным (орграф) или неориентированным (граф). В последнем случае нет разницы между ребром A->B и ребром B->A. Такое ребро пропускает поток в обоих направлениях.

CvGraphScanner

Структура, описывающая состояние обхода графа.

typedef struct CvGraphScanner
{
    CvGraphVtx* vtx;       /* текущий узел графа (или начало текущего ребра) */
    CvGraphVtx* dst;       /* конечный узел текущего ребра */
    CvGraphEdge* edge;     /* текущее ребро */
 
    CvGraph* graph;        /* граф */
    CvSeq*   stack;        /* стек вершин графа */
    int      index;        /* нижняя граница недавно посещенных вершин */
    int      mask;         /* маска событий */
}
CvGraphScanner;

Структура CvGraphScanner используется для обхода графа в глубину. см. описание cmacro:: CV_TREE_NODE_FIELDS

Вспомогательный макрос для описания узла дерева.

Макрос CV_TREE_NODE_FIELDS() используется для объявления структур, которые могут быть организованы в иерархические структуры (деревья), такие как CvSeq - базовый тип для всех динамических структур. Деревья, состоящие из узлов, при создании которых был использован этот макрос могут быть обработаны при помощи функций, речь о которых пойдет далее в этой секции.

CvTreeNodeIterator

Структура, описывающая состояние обхода деревьев.

typedef struct CvTreeNodeIterator
{
    const void* node;
    int level;
    int max_level;
}
CvTreeNodeIterator;
 
#define CV_TREE_NODE_FIELDS(node_type)                          \
    int       flags;         /* вспомогательные флаги */          \
    int       header_size;   /* размер заголовка последовательности */      \
    struct    node_type* h_prev; /* предыдущая последовательность */        \
    struct    node_type* h_next; /* следующая последовательность */            \
    struct    node_type* v_prev; /* вторая предыдущая последовательность */    \
    struct    node_type* v_next; /* вторая следующая последовательность */

Структура CvTreeNodeIterator используется для обхода деревьев. Каждый из узлов дерева должен начинаться с определенных полей, которые определены при помощи макроса CV_TREE_NODE_FIELDS(...). В терминах C++, каждый узел дерева должен быть структурой “производной” от

struct _BaseTreeNode
{
    CV_TREE_NODE_FIELDS(_BaseTreeNode);
}

CvSeq, CvSet, CvGraph и другие динамические структуры производные от CvSeq удовлетворяют этим требованиям.

ClearGraph

Освобождает граф. Функция стирает все вершины и ребра графа. Функция имеет сложность O(1).

void cvClearGraph(CvGraph* graph);

Параметр: graph - указатель на граф.

ClearMemStorage

Функция сбрасывает вершину хранилища на начало. Эта функция не освобождает памяти. Если у хранилища есть родитель, функция возвращает все блоки родителю.

void cvClearMemStorage(CvMemStorage*  storage);

Параметр: storage - указатель на хранилище.

ClearSeq

Функция удаляет все элементы из последовательности. Функция не возвращает память блоку хранилища(storage block), но эта память будет использоваться позже, когда к последовательности будут добавлены новые элементы. Функция имеет O(1) сложность.

void cvClearSeq(CvSeq* seq);

Параметр: seq - указатель на последовательность.

ClearSet

Функция удаляет все элементы из множества. Сложность Функции O (1).

void cvClearSet(CvSet* setHeader);

Параметр: setHeader - освобождаемое множество.

CloneGraph

Создает копию графа (клон);

CvGraph* cvCloneGraph(const CvGraph* graph, CvMemStorage* storage);

Параметр: graph - граф который копируем. storage - хранилище для размещения копии.

Функция создает полную копию заданного графа. Если у вершины или ребра графа есть указатели на внешние данные, указатели копии будут указывать на эти же данные. Индексы вершин и ребер в новом графе могут отличаться от оригинала, потому что функция проводит дефрагментацию вершин и ребер графа.

CloneSeq

Создает копию последовательности.

CvSeq* cvCloneSeq(const CvSeq* seq, CvMemStorage* storage=NULL);

Параметры: seq - Последовательность storage - блок хранилища, в котором будет размещен заголовок и данные новой последовательности, при их наличии. Если равен NULL, функция использует блок памяти, используемый исходной последовательностью.

Вызов

cvCloneSeq( seq, storage );

является эквивалентом вызова

cvSeqSlice( seq, CV_WHOLE_SEQ, storage, 1 );

Функция создает полную копию входной последовательности и возвращает ее.

CreateChildMemStorage

Создает дочернее хранилище в памяти.

CvMemStorage* cvCreateChildMemStorage(CvMemStorage*  parent);

Функция создает дочернее хранилище, которое подобно обычному хранилищу за исключением различий в распределении памяти / механизме освобождения. Когда дочернее хранилище нуждается в новом блоке, для добавления к списку, оно пытается получить этот блок от родителя. Первый незанятый родительский блок изымается из родительского списка блоков, и добавляется к дочернему хранилищу. Если нет доступных блоков, родитель или выделяет память под блок или заимствует его от своего родителя, если такой имеется. Другими словами может быть организована, цепная, или более сложная структура, хранилища, где каждое хранилище - потомок/родитель другого. Когда дочерняя память освобождена или просто очищена, она возвращает все блоки родителю. В остальном дочернее хранилище - то же самое что и обычное.

Дочернее хранилище может использоваться в следующих ситуациях. Предположите, что пользователь должен обработать динамические данные, размещенные в данном хранилище, и поместить результат в то же самое хранилище.

Не закончено....

Динамическая обработка данных, не используя дочернюю память