Tramac's Space

Keep trying

第8章 轮廓

发表于 更新于 分类于 阅读次数： Valine：

内存

OpenCV使用内存存储器(memory storage)来统一管理各种动态对象的内存。内存存储器在底层被实现为一个有许多相同大小的内存块组成的双向链表，通过这种结构，OpenCV可以从内存存储器中快速的分配内存或将内存返回给内存存储器。

内存存储器可以通过以下四个函数访问：

1
2
3
4
5
6
7
8
// 创建一个内存存储器
CvMemStorage* cvCreateMemStorage(int block_size=0);
// 释放内存存储器中分配的内存
void cvReleaseMemStorage(CvMemStorage** storage);
// 清空内存存储器
void cvClearMemStorage(CvMemStorage* storage);
// 从一个内存存储器中申请空间
void* cvMemStorageAlloc(CvMemStorage* storage, size_t size);

序列

序列是内存存储器中可以存储的一种对象。序列是某种结构的链表。OpenCV中序列可以存储多种不同的结构。序列在内存被实现为一个双端队列(deque)。因此，序列可以实现快速的随机访问，以及快速删除顶端的元素，但是从中间删除元素则稍慢些。
结构CVSeq的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct CvSeq{
    int flags;
    int header_size;
    CvSeq* h_prev;	// 指向前一序列
    CvSeq* h_next;	// 指向下一序列
    CvSeq* v_prev;
    CvSeq* v_next;
    int total;
    int elem_size;
    char* block_max;
    char* ptr;
    int delta_elems;
    CvMemStorage* storage;
    CvSeqBlock* free_blocks;
    CvSeqBlock* first;
}
  • 创建序列
1
2
3
4
5
6
7
// 序列分配函数
CvSeq* cvCreateSeq(
    int seq_flags,	// 组织数据的方式
    int header_size,	// 序列的头大小
    int elem_size,	// 序列要存储的元素的大小
    CvMemStorage* storage	// 指定内存存储器
);
  • 删除序列
1
2
// 清空序列中的所有元素
void cvClearSeq(CvSeq* seq);
  • 直接访问序列中的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 随机访问某个元素
char* cvGetSeqElem(seq, index);

// 打印序列中的所有碘元素
for (int i = 0; i < seq->total; ++i) {
    CvPoint* p = (CvPoint*)cvGetSeqElem(seq, i);
    printf("(%d, %d)\n", p->x, p->y);
}
// 检测一个元素是否在序列中
int cvSeqElemIdx(
    const CvSeq* seq,
    const void* element,
    CvSeqBlock** block=NULL
);
  • 切片、复制和移动序列中的数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 深度复制一个序列，并创建一个完全独立的序列结构
CvSeq* cvCloneSeq(
    const CvSeq* seq,
    CvMemStorage* storage=NULL
);
// 复制一个序列的子序列，或者仅为子序列创建一个头，和原来序列共用元素空间
CvSeq* cvSeqSlice(
    const CvSeq* seq,
    CvSlice slice,
    CvMemStorage* storage=NULL,
    int copy_data=0
);
// 删除序列
void cvSeqRemoveSlice(
    CvSeq* seq,
    CvSlice slice
);
// 添加序列
void cvSeqInsertSlice(
    CvSeq* seq,
    int before_index,
    const CvArr* from_arr
);
// 通过比较函数，对序列中的元素进行排序，或搜索一个序列
// 函数原型
typedef int (*CvCmpFunc)(const void* a, const void* b, void* userdata);
// 对序列排序
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
);
// 对序列进行逆序操作
void cvSeqInvert(CvSeq* seq);
// 拆分序列
int cvSeqPartition(
    const CvSeq* seq,
    CvMemStorage* storage,
    CvSeq** labels,
    CvCmpFunc is_equal,
    void* userdata
);
  • 将序列作为栈来使用

序列内部实现是一个双端队列。因此，我们可以高效地从序列的任意一段访问序列，这样我们可以将学列当做一个栈使用。
下面给出一些关于栈使用的函数：

1
2
3
4
5
6
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);
  • 插入和删除元素
1
2
char* cvSeqInsert(CvSeq* seq, int before_index), void* element=NULL;
void cvSeqRemove(CvSeq* seq, int index);
  • 序列中块的大小
1
2
// 改变块的大小
void cvSetSeqBlockSize(CvSeq* seq, int delta_elems);
  • 序列的读取和写入

当使用序列时，如果需要最高的性能，可以使用一些特殊的函数修改序列。这些函数通过专门的结构来保存序列的当前状态，这样使得很多后续操作都可以在更短的时间内完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 初始化序列写结构CvSeqWriter
void cvStartWriteSeq(
    int seq_flags,
    int header_size,
    int elem_size,
    CvMemStorage* 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);

与之对应的读操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 初始化读结构
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);
  • 序列和数组

有时候可能需要将序列转换成数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 复制序列的全部或部分到一个连续内存数组中
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
);

查找轮廓

一个轮廓一般对应一系列的点，也就是图像中的一条曲线。表示方法可能根据不同情况而有所不同。有多种方法可以表示曲线。在OpenCV中一般用序列来存储轮廓信息。序列中的每一个元素是曲线中一个点的位置。

1
2
3
4
5
6
7
8
9
// 寻找轮廓函数
int cvFindContours(
    IplImage* img,
    CvMemStorage* storage,
    CvSeq** firstContour,
    int headerSize=sizeof(CvContour),
    CvContourRetrievalMode mode=CV_RETR_LIST,
    CvChainApproxMethod method=CV_CHAIN_APPROX_SIMPLE
);
  • 使用序列表示轮廓

序列中保存一系列的点，这些点构成轮廓。轮廓是点的序列，可以用来表示图像空间中的曲线。
常用的处理函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 与CVFindContours()类似，不过每次返回一个轮廓
CvContourScanner cvStartFindContours(
    CvArr* image,
    CvMemStorage* storage,
    int header_size=sizeof(CvContour),
    int mode=CV_RETR_LIST,
    int method=CV_CHAIN_APPROX_SIMPLE,
    CvPoint offset=cvPoint(0,0)
);
// 查找下一个轮廓
CvSeq* cvFindNextContour(CvContourScanner scanner);
// 轮廓替换
void cvSubstituteContour(CvContourScanner scanner, CvSeq* new_counter);
// 结束查找
CvSeq* cvEndFindContour(CvContourScanner* scanner);
// 将Freeman链转换为多边形表示
CvSeq* cvApproxChains(
    CvSeq* src_seq,
    CvMemStorage* storage,
    int method=CV_CHAIN_APPROX_SIMPLE,
    double parameter=0,
    int minimal_perimeter=0,
    int recursive=0
);
  • Freeman链码

一般情况下，通过cvFindContours获取的轮廓是一系列顶点的序列。另一种表达方法是当mehod设置为CV_CHAIN_CODE时，生成的轮廓是通过Freeman链码的方式返回。在Freeman链码中，多边形被表示为一系列的位移，每一个位移有8个方向，使用0-7表示。

1
2
3
4
// 初始化Freeman链cvChainPtReader结构
void cvStartReadChainPoints(CvChain* chain, CvChainPtReader* reader);
// 读取链码中的每个点
CvPoint cvReadChainPoint(CvChainPtReader* reader);
  • 绘制轮廓

一个经常用到的功能是在屏幕上绘制检测到的轮廓。

1
2
3
4
5
6
7
8
9
10
void cvDrawContours(
    CvArr* img,
    CvSeq* contour,
    CvScalar external_color,
    CvScalar holo_color,
    int max_level,
    int thickness=1,
    int line_type=8,
    CvPoint offset=cvPoint(0, 0)
);

深入分析轮廓

当分析一个图像的时候，针对轮廓常用的操作有识别和处理，另外相关的还有多种对轮廓的处理，如简化或拟合轮廓，匹配轮廓到模板。

  • 多边形逼近

当我们绘制一个多边形或者进行形状分析的时候，通常需要使用多边形逼近一个轮廓，使得定点数目变少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 轮廓逼近函数
CvSeq* cvApproxPoly(
    const void* src_seq,
    int header_size,
    CvMemStorage* storage,
    int method,
    double parameter,
    int recursive=0
);
// 寻找关键点函数
CvSeq* cvFindDominantPoints(
    CvSeq* contour,
    CvMemStorage* storage,
    int method=CV_DOMINANT_IPAN,
    double parameter1=0,
    double parameter2=0,
    double parameter3=0,
    double parameter4=0,
)
  • 特性概括

轮廓处理中经常遇到的另一个任务是计算一些轮廓变化的概括特性。这可能包含长度或其他一些反映轮廓整体大小的度量。另一个有用的特性是轮廓矩，可以用来概括轮廓的总形状特性。
长度

1
2
3
4
// 计算轮廓的长度
double cvArcLength(const void* curve, CvSlice slice=CV_WHOLE_SEQ, int is_closed=-1);
// 计算轮廓的面积
double cvContourArea(const CvArr* contour, CvSlice slice=CV_WHOLE_SEQ);

边界框
长度和面积只是轮廓的简单特性，更复杂一些的特性描述应该是矩形边界框，圆形边界框或椭圆边界框。

1
2
3
4
5
6
7
8
9
10
// 获取矩形边界框
CvRect cvBoundingRect(CvArr* points, int update=0);
// 获取一个包围轮廓最小的长方形
CvBox2D cvMInAreaRect2(const CvArr* points, cvMemStorage* storage=NULL);
// CvBox2D结构体的定义
typedef struct CvBox2D(
    CvPoint2D32f center;
    CvSize2D32f size;
    float angle;
) cvBox2D;

圆形和椭圆形边界

1
2
3
4
5
6
7
8
// 获取圆形外接圆
int cvMInEnclosingCircle(
    const CvArr* points,
    CvPoint2D32f* center,
    float* radius
);
// 获取最佳拟合椭圆
CvBox2D cvFitEllipse2(const CvArr* points);
  • 几何

在处理CVBox2D或多边形边界的时候，经常需要进行多边形以及边界框的重叠判断。下面是一些常用的函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 根据输入的2个矩形计算，得出最小外包矩形
CvRect cvMaxRect(const CvRect* rect1, const CvRect* rect2);
// 计算矩形的四个顶点
void cvBOxPoints(CvBox2D box, CvPoint2D32f pt[4]);
// 从mat中初始化序列
CvSeq* cvPointSeqFromMat(
    int seq_kind,
    const CvArr* mat,
    CvContour* contour_header,
    CvSeqBlock* block
);
// 测试一个点是否在多边形内部
double cvPointPolygonTest(
    const CvArr* contour,
    CvPoint2D32f pt,
    int measure_dist
);

轮廓的匹配

在实际应用中，一个跟轮廓相关的最常用到的功能是匹配两个轮廓。如果有两个轮廓，如何比较它们；或者如何比较一个轮廓和一个抽象模板。

  • 矩

比较两个轮廓最简洁的方式是比较它们的轮廓矩。简单的说，矩是通过对轮廓上所有点进行积分运算而得到的一个粗略特征。

1
2
3
4
5
6
7
8
9
10
// 计算轮廓矩
void cvContoursMoments(CvSeq* contour, CvMoments* moments);
// 用于保存结果的CvMoments结构的定义
typedef struct CvMoments{
    double m00, m10, m01, m20, m11, m02, m30, m21, m12, m03;
    double mu20, mu11, mu02, mu30, mu21, mu12, mu03;
    double inv_sqrt_m00;
} CvMoments;
// 获取特定的矩
double cvGetSpatialMoment(CvMoments* moments, int x_order, int y_order);
  • 再论矩

直接计算得到的矩并不是做比较时最好的参数。具体来说，经常会用到的是归一化的矩，因此，不同大小但是形状相同的物体会有相同的值，并且不依赖于坐标系的选择。

1
2
3
4
5
6
7
8
// 计算图像的矩
void cvMoments(const CvArr* image, CvMoments* moments, int isBinary=0);
// 计算中心距
double cvGetCentralMoment(CvMomens* moments, int x_order, int y_order);
// 计算归一化矩
double cvGetNormalizedCentralMoment(CvMomens* moments, int x_order, int y_order);
// 计算Hu不变矩
void cvGetHuMoments(CvMoments* moments, CvHuMoments* HuMoments);

Hu矩是归一化中心矩的线性组合。之所以这样做是为了能够获取代表图像某个特征的矩函数，这些矩函数对某些变化如缩放、旋转和镜像映射具有不变形。

  • 使用Hu矩进行匹配

很自然，使用Hu矩我们想要比较两个物体并且判明它们是否相似。

1
2
3
4
5
6
7
// 比较函数
double cvMatchShapes(
    const void* object1,
    const void* object2,
    int method,
    double parameter=0
);

提供的物体可以是灰度图像也可以是轮廓。如果是图像，会根据指定的方法先计算矩。

  • 等级匹配

有时，简单的相似度度量(比如矩)并不足够，所以就引出了轮廓树。轮廓树是用来描述一个特定形状内各部分的等级。编码得到的二分轮廓树包含了原始轮廓的形状信息，一旦被建立，就可以很有效的对比两个轮廓。这个过程开始定义两个树节点的对应关系，然后比较对应节点的特性。最后的结果就是两个树的相似度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 从轮廓生成轮廓树
CvContourTree* cvCreateContourTree(
    const CvSeq* contour,
    CvMemStorage* storage,
    double threshold
);
// 从轮廓树生成轮廓
CvSeq* cvContourFromContourTree(
    const CvContourTree* tree,
    CvMemStorage* storage,
    CvTermCriteria criteria
);
// 轮廓树匹配
double cvMatchContourTrees(
    const CvContourTree* tree1,
    const CvContourTree* tree2,
    int method,
    double threshold
);
  • 轮廓的凸包和凸缺陷

另一个理解物体形状或轮廓的有用的方法是计算一个物体的凸包然后计算其凸缺陷。很多复杂物体的特性能很好的被这种缺陷表现出来。
下面是是三个关于凸包和凸缺陷的重要函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define CV_CLOCKWISE 1
#define CV_COUNTER_CLOCKWISE 2
// 计算已知轮廓的凸包
CvSeq* cvConvexHull2(
    const CvArr* input,
    void* hull_storage=NULL,
    int orientation=CV_CLOCKWISE,
    int return_points=0
);
// 检查一个已知轮廓是否是凸的
int cvCheckContourConvexity(const CvArr* contour);
// 在已知轮廓是凸包的情况下计算凸缺陷
CvSeq* cvConvexityDefects('
    const CvArr* contour,
    const CvArr* convexhull,
    CvMemStorage* storage=NULL
);
// 缺陷结构体的描述
typedef struct CvConvexityDefect{
    CvPoint* start;
    CvPoint* end;
    CvPoint* depth_point;
    float depth;
} CvConvexityDefect;

  • 成对几何直方图

    Freeman链码编码是对一个多边形的序列如何“移动”的描述，每个这样的移动有固定的长度和特定的方向。Freeman链码编码的用处很多，因为它支持了成对几何直方图(PGH)的基本思想。
    PGH实际上是链码编码直方图(CCH)的一个扩展或延伸。CCH是一种直方图，用来统计一个轮廓Freeman链码编码每一种走法的数字。该直方图有旋转不变形的性质。
    PGH的使用和FCC相似，一个重要的不同是，PGH的描述能力更强，因此在尝试解决复杂问题的时候很有用，比如说大量的形状需要被辨识，并且或者有很多背景噪声的时候。

    1
    2
    // 计算PGH的函数
    void cvCalaPGH(const CvSeq* contour, CvHistogram* hist);