輪廓處理函數(shù)

ApproxChains

用多邊形曲線逼近 Freeman 鏈

CvSeq* cvApproxChains( CvSeq* src_seq, CvMemStorage* storage,
                       int method=CV_CHAIN_APPROX_SIMPLE,
                       double parameter=0, int minimal_perimeter=0, int recursive=0 );

src_seq

• 涉及其它鏈的鏈指針

storage

• 存儲多邊形線段位置的緩存

method

• 逼近方法 (見函數(shù) cvFindContours 的描述).

parameter

• 方法參數(shù)(現(xiàn)在不用).

minimal_perimeter

• 僅逼近周長大于 minimal_perimeter 輪廓。其它的鏈從結(jié)果中除去。

recursive

• 如果非 0, 函數(shù)從 src_seq 中利用 h_next 和 v_next links 連接逼近所有可訪問的鏈。如果為 0, 則僅逼近單鏈。

這是一個單獨(dú)的逼近程序。 對同樣的逼近標(biāo)識，函數(shù) cvApproxChains 與 cvFindContours 的工作方式一模一樣。它返回發(fā)現(xiàn)的第一個輪廓的指針。其它的逼近模塊，可以用返回結(jié)構(gòu)中的 v_next 和 v_next 域來訪問

StartReadChainPoints

初始化鏈讀取

void cvStartReadChainPoints( CvChain* chain, CvChainPtReader* reader );

chain

• 鏈的指針

reader

• 鏈的讀取狀態(tài)

函數(shù) cvStartReadChainPoints 初始化一個特殊的讀取器 (參考 Dynamic Data Structures 以獲得關(guān)于集合與序列的更多內(nèi)容).

ReadChainPoint

得到下一個鏈的點(diǎn)

CvPoint cvReadChainPoint( CvChainPtReader* reader );

reader

• 鏈的讀取狀態(tài)

函數(shù) cvReadChainPoint 返回當(dāng)前鏈的點(diǎn)，并且更新讀取位置。

ApproxPoly

用指定精度逼近多邊形曲線

CvSeq* cvApproxPoly( const void* src_seq, int header_size, CvMemStorage* storage,
                     int method, double parameter, int parameter2=0 );

src_seq

• 點(diǎn)集數(shù)組序列

header_size

• 逼近曲線的頭尺寸

storage

• 逼近輪廓的容器。如果為 NULL， 則使用輸入的序列

method

• 逼近方法。目前僅支持 CV_POLY_APPROX_DP ， 對應(yīng) Douglas-Peucker 算法.

parameter

• 方法相關(guān)參數(shù)。對 CV_POLY_APPROX_DP 它是指定的逼近精度

parameter2

• 如果 src_seq 是序列，它表示要么逼近單個序列，要么在 src_seq 的同一個或低級層次上逼近所有序列 (參考 cvFindContours 中對輪廓繼承結(jié)構(gòu)的描述). 如果 src_seq 是點(diǎn)集的數(shù)組 (CvMat*) ， 參數(shù)指定曲線是閉合 (parameter2!=0) 還是非閉合 (parameter2=0).

函數(shù) cvApproxPoly 逼近一個或多個曲線，并返回逼近結(jié)果。對多個曲線的逼近，生成的樹將與輸入的具有同樣的結(jié)構(gòu)。(1:1 的對應(yīng)關(guān)系).

BoundingRect

計(jì)算點(diǎn)集的最外面（up-right）矩形邊界

CvRect cvBoundingRect( CvArr* points, int update=0 );

points

• 二維點(diǎn)集，點(diǎn)的序列或向量 (CvMat)

update

• 更新標(biāo)識。下面是輪廓類型和標(biāo)識的一些可能組合:

  • update=0, contour ~ CvContour*: 不計(jì)算矩形邊界，但直接由輪廓頭的 rect 域得到。

  • update=1, contour ~ CvContour*: 計(jì)算矩形邊界，而且將結(jié)果寫入到輪廓頭的 rect 域中 header.

  • update=0, contour ~ CvSeq* or CvMat*: 計(jì)算并返回邊界矩形

  • update=1, contour ~ CvSeq* or CvMat*: 產(chǎn)生運(yùn)行錯誤 （runtime error is raised）

函數(shù) cvBoundingRect 返回二維點(diǎn)集的最外面 （up-right）矩形邊界。

ContourArea

計(jì)算整個輪廓或部分輪廓的面積

double cvContourArea( const CvArr* contour, CvSlice slice=CV_WHOLE_SEQ );

contour

• 輪廓 (邊界點(diǎn)的序列或數(shù)組).

slice

• 感興趣輪廓部分的起始點(diǎn)，缺省是計(jì)算整個輪廓的面積。

函數(shù) cvContourArea 計(jì)算整個輪廓或部分輪廓的面積。 對后面的情況，面積表示輪廓部分和起始點(diǎn)連線構(gòu)成的封閉部分的面積。如下圖所示：

備注: 輪廓的方向影響面積的符號。因此函數(shù)也許會返回負(fù)的結(jié)果。應(yīng)用函數(shù) fabs() 得到面積的絕對值。

ArcLength

計(jì)算輪廓周長或曲線長度

double cvArcLength( const void* curve, CvSlice slice=CV_WHOLE_SEQ, int is_closed=-1 );

curve

• 曲線點(diǎn)集序列或數(shù)組

slice

• 曲線的起始點(diǎn)，缺省是計(jì)算整個曲線的長度

is_closed

• 表示曲線是否閉合，有三種情況：

  • is_closed=0 - 假設(shè)曲線不閉合

  • is_closed>0 - 假設(shè)曲線閉合

  • is_closed<0 - 若曲線是序列，檢查 ((CvSeq*)curve)->flags 中的標(biāo)識 CV_SEQ_FLAG_CLOSED 來確定曲線是否閉合。否則 (曲線由點(diǎn)集的數(shù)組 (CvMat*) 表示) 假設(shè)曲線不閉合。

函數(shù) cvArcLength 通過依次計(jì)算序列點(diǎn)之間的線段長度，并求和來得到曲線的長度。

CreateContourTree

創(chuàng)建輪廓的繼承表示形式

CvContourTree* cvCreateContourTree( const CvSeq* contour, CvMemStorage* storage, double threshold );

contour

• 輸入的輪廓

storage

• 輸出樹的容器

threshold

• 逼近精度

函數(shù) cvCreateContourTree 為輸入輪廓 contour 創(chuàng)建一個二叉樹，并返回樹根的指針。如果參數(shù) threshold 小于或等于 0 ,則函數(shù)創(chuàng)建一個完整的二叉樹。如果 threshold 大于 0 ， 函數(shù)用 threshold 指定的精度創(chuàng)建二叉樹：如果基線的截?cái)鄥^(qū)域頂點(diǎn)小于threshold，該數(shù)就停止生長并作為函數(shù)的最終結(jié)果返回。

ContourFromContourTree

由樹恢復(fù)輪廓

CvSeq* cvContourFromContourTree( const CvContourTree* tree, CvMemStorage* storage,
                                 CvTermCriteria criteria );

tree

• 輪廓樹

storage

• 重構(gòu)的輪廓容器

criteria

• 停止重構(gòu)的準(zhǔn)則

函數(shù) cvContourFromContourTree 從二叉樹恢復(fù)輪廓。參數(shù) criteria 決定了重構(gòu)的精度和使用樹的數(shù)目及層次。所以它可建立逼近的輪廓。 函數(shù)返回重構(gòu)的輪廓。

MatchContourTrees

用樹的形式比較兩個輪廓

double cvMatchContourTrees( const CvContourTree* tree1, const CvContourTree* tree2,
                            int method, double threshold );

tree1

• 第一個輪廓樹

tree2

• 第二個輪廓樹

method

• 相似度。僅支持 CV_CONTOUR_TREES_MATCH_I1 。

threshold

• 相似度閾值

函數(shù) cvMatchContourTrees 計(jì)算兩個輪廓樹的匹配值。從樹根開始通過逐層比較來計(jì)算相似度。如果某層的相似度小于 threshold, 則中斷比較過程，且返回當(dāng)前的差值。

計(jì)算幾何

MaxRect

對兩個給定矩形，尋找矩形邊界

CvRect cvMaxRect( const CvRect* rect1, const CvRect* rect2 );

rect1

• 第一個矩形

rect2

• 第二個矩形

函數(shù) cvMaxRect 尋找包含兩個輸入矩形的具有最小面積的矩形邊界。

CvBox2D

旋轉(zhuǎn)的二維盒子

typedef struct CvBox2D
{
    CvPoint2D32f center;  /* 盒子的中心 */
    CvSize2D32f  size;    /* 盒子的長和寬 */
    float angle;          /* 水平軸與第一個邊的夾角，用角度度表示*/
}
CvBox2D;

PointSeqFromMat

從點(diǎn)向量中初始化點(diǎn)序列頭部

CvSeq* cvPointSeqFromMat( int seq_kind, const CvArr* mat,
                          CvContour* contour_header,
                          CvSeqBlock* block );

seq_kind

點(diǎn)序列的類型：一系列點(diǎn)(0),曲線(CV_SEQ_KIND_CURVE),封閉曲線(CV_SEQ_KIND_CURVE+CV_SEQ_FLAG_CLOSED) 等等。

mat

• 輸入矩陣。輸入應(yīng)該是連續(xù)的一維點(diǎn)向量，類型也應(yīng)該是CV_32SC2或者CV_32FC2.

contour_header

• 輪廓頭部，被函數(shù)初始化。

block

• 序列塊頭部，被函數(shù)初始化。

函數(shù)cvPointSeqFromMat 初始化序列頭部，用來創(chuàng)建一個將給定矩陣中的元素形成的"虛擬"序列。沒有數(shù)據(jù)被拷貝。被初始化的頭部可以傳遞給其他任何包含輸入點(diǎn)序列的函數(shù)。沒有額外的元素加入序列，但是一些可能被移除。函數(shù)是cvMakeSeqHeaderForArray 的一個特別的變量，然后在內(nèi)部使用。它返回初始化頭部的指針。需要注意的是，包含的邊界矩形（CvContour 的rect字段）沒有被初始化，如果你需要使用，需要自己調(diào)用cvBoundingRect。

以下是使用例子。

CvContour header;
CvSeqBlock block;
CvMat* vector = cvCreateMat( 1, 3, CV_32SC2 );

CV_MAT_ELEM( *vector, CvPoint, 0, 0 ) = cvPoint(100,100);
CV_MAT_ELEM( *vector, CvPoint, 0, 1 ) = cvPoint(100,200);
CV_MAT_ELEM( *vector, CvPoint, 0, 2 ) = cvPoint(200,100);

IplImage* img = cvCreateImage( cvSize(300,300), 8, 3 );
cvZero(img);

cvDrawContours( img, cvPointSeqFromMat(CV_SEQ_KIND_CURVE+CV_SEQ_FLAG_CLOSED,
   vector, &header, &block), CV_RGB(255,0,0), CV_RGB(255,0,0), 0, 3, 8, cvPoint(0,0));

BoxPoints

尋找盒子的頂點(diǎn)

void cvBoxPoints( CvBox2D box, CvPoint2D32f pt[4] );

box

• 盒子

pt

• 頂點(diǎn)數(shù)組

函數(shù) cvBoxPoints 計(jì)算輸入的二維盒子的頂點(diǎn)。下面是函數(shù)代碼：

void cvBoxPoints( CvBox2D box, CvPoint2D32f pt[4] )
{
    double angle = box.angle*CV_PI/180.
    float a = (float)cos(angle)*0.5f;
    float b = (float)sin(angle)*0.5f;

    pt[0].x = box.center.x - a*box.size.height - b*box.size.width;
    pt[0].y = box.center.y + b*box.size.height - a*box.size.width;
    pt[1].x = box.center.x + a*box.size.height - b*box.size.width;
    pt[1].y = box.center.y - b*box.size.height - a*box.size.width;
    pt[2].x = 2*box.center.x - pt[0].x;
    pt[2].y = 2*box.center.y - pt[0].y;
    pt[3].x = 2*box.center.x - pt[1].x;
    pt[3].y = 2*box.center.y - pt[1].y;
}

FitEllipse

二維點(diǎn)集的橢圓擬合

CvBox2D cvFitEllipse2( const CvArr* points );

points

• 點(diǎn)集的序列或數(shù)組

函數(shù) cvFitEllipse 對給定的一組二維點(diǎn)集作橢圓的最佳擬合(最小二乘意義上的)。返回的結(jié)構(gòu)與 cvEllipse 中的意義類似，除了 size 表示橢圓軸的整個長度，而不是一半長度。

FitLine

2D 或 3D 點(diǎn)集的直線擬合

void  cvFitLine( const CvArr* points, int dist_type, double param,
                 double reps, double aeps, float* line );

points

• 2D 或 3D 點(diǎn)集，32-比特整數(shù)或浮點(diǎn)數(shù)坐標(biāo)

dist_type

• 擬合的距離類型 （見討論）.

param

• 對某些距離的數(shù)字參數(shù)，如果是 0， 則選擇某些最優(yōu)值

reps, aeps

• 半徑 (坐標(biāo)原點(diǎn)到直線的距離) 和角度的精度，一般設(shè)為0.01。

line

• 輸出的直線參數(shù)。2D 擬合情況下，它是包含 4 個浮點(diǎn)數(shù)的數(shù)組 (vx, vy, x0, y0)，其中 (vx, vy) 是線的單位向量而 (x0, y0) 是線上的某個點(diǎn). 對 3D 擬合，它是包含 6 個浮點(diǎn)數(shù)的數(shù)組 (vx, vy, vz, x0, y0, z0)， 其中 (vx, vy, vz) 是線的單位向量，而 (x0, y0, z0) 是線上某點(diǎn)。

函數(shù) cvFitLine 通過求 sum_i:ρ(r_i) 的最小值方法，用 2D 或 3D 點(diǎn)集擬合直線，其中 r_i 是第 i 個點(diǎn)到直線的距離， ρ(r) 是下面的距離函數(shù)之一：

dist_type=CV_DIST_L2 (L₂): ρ(r)=r²/2 (最簡單和最快的最小二乘法)

dist_type=CV_DIST_L1 (L₁): ρ(r)=r

dist_type=CV_DIST_L12 (L₁-L₂): ρ(r)=2?[sqrt(1+r²/2) - 1]

dist_type=CV_DIST_FAIR (Fair): ρ(r)=C²?[r/C - log(1 + r/C)], C=1.3998

dist_type=CV_DIST_WELSCH (Welsch): ρ(r)=C²/2?[1 - exp(-(r/C)²)], C=2.9846

dist_type=CV_DIST_HUBER (Huber): ρ(r)= r²/2, if r < C; C?(r-C/2), otherwise; C=1.345

ConvexHull2

發(fā)現(xiàn)點(diǎn)集的凸外形

CvSeq* cvConvexHull2( const CvArr* input, void* hull_storage=NULL,
                      int orientation=CV_CLOCKWISE, int return_points=0 );

points

• 2D 點(diǎn)集的序列或數(shù)組，32-比特整數(shù)或浮點(diǎn)數(shù)坐標(biāo)

hull_storage

• 輸出的數(shù)組(CvMat*) 或內(nèi)存緩存 (CvMemStorage*)，用以存儲凸外形。 如果是數(shù)組，則它應(yīng)該是一維的，而且與輸入的數(shù)組/序列具有同樣數(shù)目的元素。輸出時，通過修改頭結(jié)構(gòu)將數(shù)組裁減到凸外形的尺寸。

orientation

• 凸外形的旋轉(zhuǎn)方向: 逆時針或順時針 （CV_CLOCKWISE or CV_COUNTER_CLOCKWISE）

return_points

• 如果非零，hull_storage 為數(shù)組情況下,點(diǎn)集將以外形 (hull) 存儲，而不是頂點(diǎn)形式 (indices)。如果 hull_storag 為內(nèi)存存儲模式下則存儲為點(diǎn)集形式(points)。

函數(shù) cvConvexHull2 使用 Sklansky 算法計(jì)算 2D 點(diǎn)集的凸外形。如果 hull_storage 是內(nèi)存存儲倉， 函數(shù)根據(jù) return_points 的值，創(chuàng)建一個包含外形的點(diǎn)集或指向這些點(diǎn)的指針的序列。

例子. 由點(diǎn)集序列或數(shù)組創(chuàng)建凸外形

#include "cv.h"
#include "highgui.h"
#include <stdlib.h>

#define ARRAY  0 /* switch between array/sequence method by replacing 0<=>1 */

void main( int argc, char** argv )
{
    IplImage* img = cvCreateImage( cvSize( 500, 500 ), 8, 3 );
    cvNamedWindow( "hull", 1 );

#if !ARRAY
        CvMemStorage* storage = cvCreateMemStorage();
#endif

    for(;;)
    {
        int i, count = rand()%100 + 1, hullcount;
        CvPoint pt0;
#if !ARRAY
        CvSeq* ptseq = cvCreateSeq( CV_SEQ_KIND_GENERIC|CV_32SC2, sizeof(CvContour),
                                     sizeof(CvPoint), storage );
        CvSeq* hull;

        for( i = 0; i < count; i++ )
        {
            pt0.x = rand() % (img->width/2) + img->width/4;
            pt0.y = rand() % (img->height/2) + img->height/4;
            cvSeqPush( ptseq, &pt0 );
        }
        hull = cvConvexHull2( ptseq, 0, CV_CLOCKWISE, 0 );
        hullcount = hull->total;
#else
        CvPoint* points = (CvPoint*)malloc( count * sizeof(points[0]));
        int* hull = (int*)malloc( count * sizeof(hull[0]));
        CvMat point_mat = cvMat( 1, count, CV_32SC2, points );
        CvMat hull_mat = cvMat( 1, count, CV_32SC1, hull );

        for( i = 0; i < count; i++ )
        {
            pt0.x = rand() % (img->width/2) + img->width/4;
            pt0.y = rand() % (img->height/2) + img->height/4;
            points[i] = pt0;
        }
        cvConvexHull2( &point_mat, &hull_mat, CV_CLOCKWISE, 0 );
        hullcount = hull_mat.cols;
#endif
        cvZero( img );
        for( i = 0; i < count; i++ )
        {
#if !ARRAY
            pt0 = *CV_GET_SEQ_ELEM( CvPoint, ptseq, i );
#else
            pt0 = points[i];
#endif
            cvCircle( img, pt0, 2, CV_RGB( 255, 0, 0 ), CV_FILLED );
        }

#if !ARRAY
        pt0 = **CV_GET_SEQ_ELEM( CvPoint*, hull, hullcount - 1 );
#else
        pt0 = points[hull[hullcount-1]];
#endif

        for( i = 0; i < hullcount; i++ )
        {
#if !ARRAY
            CvPoint pt = **CV_GET_SEQ_ELEM( CvPoint*, hull, i );
#else
            CvPoint pt = points[hull[i]];
#endif
            cvLine( img, pt0, pt, CV_RGB( 0, 255, 0 ));
            pt0 = pt;
        }

        cvShowImage( "hull", img );

        int key = cvWaitKey(0);
        if( key == 27 ) // 'ESC'
            break;

#if !ARRAY
        cvClearMemStorage( storage );
#else
        free( points );
        free( hull );
#endif
    }
}

CheckContourConvexity

測試輪廓的凸性

int cvCheckContourConvexity( const CvArr* contour );

contour

• 被測試輪廓 (點(diǎn)序列或數(shù)組).

函數(shù) cvCheckContourConvexity 輸入的輪廓是否為凸的。必須是簡單輪廓，比如沒有自交叉。

CvConvexityDefect

用來描述一個簡單輪廓凸性缺陷的結(jié)構(gòu)體

typedef struct CvConvexityDefect
{
    CvPoint* start; /* 缺陷開始的輪廓點(diǎn) */
    CvPoint* end; /* 缺陷結(jié)束的輪廓點(diǎn) */
    CvPoint* depth_point; /* 缺陷中距離凸形最遠(yuǎn)的輪廓點(diǎn)(谷底) */
    float depth; /* 谷底距離凸形的深度*/
} CvConvexityDefect;

Picture. 手部輪廓的凸形缺陷.

ConvexityDefects

發(fā)現(xiàn)輪廓凸形缺陷

CvSeq* cvConvexityDefects( const CvArr* contour, const CvArr* convexhull,
                           CvMemStorage* storage=NULL );

contour

• 輸入輪廓

convexhull

• 用 cvConvexHull2 得到的凸外形，它應(yīng)該包含輪廓的定點(diǎn)的指針或下標(biāo)，而不是外形點(diǎn)的本身，即cvConvexHull2 中的參數(shù) return_points 應(yīng)該設(shè)置為 0.

storage

• 凸性缺陷的輸出序列容器。如果為 NULL, 使用輪廓或外形的存儲倉。

函數(shù) cvConvexityDefects 發(fā)現(xiàn)輸入輪廓的所有凸性缺陷，并且返回 CvConvexityDefect 結(jié)構(gòu)序列。

PointPolygonTest

測試點(diǎn)是否在多邊形中

double cvPointPolygonTest( const CvArr* contour,
                           CvPoint2D32f pt, int measure_dist );

contour

• 輸入輪廓.

pt

• 針對輪廓需要測試的點(diǎn)。

measure_dist

• 如果非0，函數(shù)將估算點(diǎn)到輪廓最近邊的距離。

函數(shù)cvPointPolygonTest 決定測試點(diǎn)是否在輪廓內(nèi)，輪廓外，還是輪廓的邊上（或者共邊的交點(diǎn)上），它的返回值是正負(fù)零，相對應(yīng)的，當(dāng)measure_dist=0時，返回值是1, -1,0, 同樣當(dāng) measure_dist≠0 ，它是返回一個從點(diǎn)到最近的邊的帶符號距離。

下面是函數(shù)輸出的結(jié)果，用圖片的每一個象素去測試輪廓的結(jié)果。

MinAreaRect2

對給定的 2D 點(diǎn)集，尋找最小面積的包圍矩形

CvBox2D  cvMinAreaRect2( const CvArr* points, CvMemStorage* storage=NULL );

points

• 點(diǎn)序列或點(diǎn)集數(shù)組

storage

• 可選的臨時存儲倉

函數(shù) cvMinAreaRect2 通過建立凸外形并且旋轉(zhuǎn)外形以尋找給定 2D 點(diǎn)集的最小面積的包圍矩形.

Picture. Minimal-area bounding rectangle for contour

MinEnclosingCircle

對給定的 2D 點(diǎn)集，尋找最小面積的包圍圓形

int cvMinEnclosingCircle( const CvArr* points, CvPoint2D32f* center, float* radius );

points

• 點(diǎn)序列或點(diǎn)集數(shù)組

center

• 輸出參數(shù)：圓心

radius

• 輸出參數(shù)：半徑

函數(shù) cvMinEnclosingCircle 對給定的 2D 點(diǎn)集迭代尋找最小面積的包圍圓形。如果產(chǎn)生的圓包含所有點(diǎn)，返回非零。否則返回零（算法失?。?。

CalcPGH

計(jì)算輪廓的 pair-wise 幾何直方圖

void cvCalcPGH( const CvSeq* contour, CvHistogram* hist );

contour

• 輸入輪廓，當(dāng)前僅僅支持具有整數(shù)坐標(biāo)的點(diǎn)集

hist

• 計(jì)算出的直方圖，必須是兩維的。

函數(shù) cvCalcPGH 計(jì)算輪廓的 2D pair-wise 幾何直方圖 （2D pair-wise geometrical histogram ：PGH), 算法描述見 [Iivarinen97]. 算法考慮的每一對輪廓邊緣。計(jì)算每一對邊緣之間的夾角以及最大最小距離。具體做法是，輪流考慮每一個邊緣做為基準(zhǔn)，函數(shù)循環(huán)遍歷所有其他的邊緣。在考慮基準(zhǔn)邊緣和其它邊緣的時候， 選擇非基準(zhǔn)線上的點(diǎn)到基準(zhǔn)線上的最大和最小距離。邊緣之間的角度定義了直方圖的行，而在其中增加對應(yīng)計(jì)算出來的最大和最小距離的所有直方塊， (即直方圖是 [Iivarninen97] 定義中的轉(zhuǎn)置). 該直方圖用來做輪廓匹配。

平面劃分

CvSubdiv2D

平面劃分

#define CV_SUBDIV2D_FIELDS()        CV_GRAPH_FIELDS()               int  quad_edges;                int  is_geometry_valid;         CvSubdiv2DEdge recent_edge;     CvPoint2D32f  topleft;          CvPoint2D32f  bottomright;

typedef struct CvSubdiv2D
{
    CV_SUBDIV2D_FIELDS()
}
CvSubdiv2D;

平面劃分是將一個平面分割為一組互不重疊的能夠復(fù)蓋整個平面的區(qū)域P(facets)。上面結(jié)構(gòu)描述了建立在 2D 點(diǎn)集上的劃分結(jié)構(gòu)，其中點(diǎn)集互相連接并且構(gòu)成平面圖形，該圖形通過結(jié)合一些無限連接外部劃分點(diǎn)(稱為凸形點(diǎn))的邊緣，將一個平面用邊按照其邊緣劃分成很多小區(qū)域(facets)。

對于每一個劃分操作，都有一個對偶劃分與之對應(yīng)，對偶的意思是小區(qū)域和點(diǎn)(劃分的頂點(diǎn))變換角色，即在對偶劃分中，小區(qū)域被當(dāng)做一個頂點(diǎn)(以下稱之為虛擬點(diǎn))，而原始的劃分頂點(diǎn)被當(dāng)做小區(qū)域。在如下所示的圖例中，原始的劃分用實(shí)線來表示，而對偶劃分用點(diǎn)線來表示。

OpenCV 使用Delaunay's 算法將平面分割成小的三角形區(qū)域。分割的實(shí)現(xiàn)通過從一個假定的三角形(該三角形確保包括所有的分割點(diǎn))開始不斷迭代來完成。在這種情況下，對偶劃分就是輸入的2d點(diǎn)集的 Voronoi圖表。這種劃分可以用于對一個平面的3d分段變換、形態(tài)變換、平面點(diǎn)的快速定位以及建立特定的圖結(jié)構(gòu) (比如 NNG,RNG等等)。

CvQuadEdge2D

平面劃分中的Quad-edge(四方邊緣結(jié)構(gòu))

/* quad-edge中的一條邊緣，低兩位表示該邊緣的索引號，其它高位表示邊緣指針。 */
typedef long CvSubdiv2DEdge;

/* 四方邊緣的結(jié)構(gòu)場 */
#define CV_QUADEDGE2D_FIELDS()         int flags;                         struct CvSubdiv2DPoint* pt[4];     CvSubdiv2DEdge  next[4];

typedef struct CvQuadEdge2D
{
    CV_QUADEDGE2D_FIELDS()
}
CvQuadEdge2D;

Quad-edge(譯者注：以下稱之為四方邊緣結(jié)構(gòu))是平面劃分的基元，其中包括四個邊緣 (e, eRot(紅色) 以及它們的逆（綠色）)。

CvSubdiv2DPoint

原始和對偶劃分點(diǎn)

#define CV_SUBDIV2D_POINT_FIELDS()    int            flags;          CvSubdiv2DEdge first;          CvPoint2D32f   pt;

#define CV_SUBDIV2D_VIRTUAL_POINT_FLAG (1 << 30)

typedef struct CvSubdiv2DPoint
{
    CV_SUBDIV2D_POINT_FIELDS()
}
CvSubdiv2DPoint;

Subdiv2DGetEdge

返回給定的邊緣之一

CvSubdiv2DEdge  cvSubdiv2DGetEdge( CvSubdiv2DEdge edge, CvNextEdgeType type );
#define cvSubdiv2DNextEdge( edge ) cvSubdiv2DGetEdge( edge, CV_NEXT_AROUND_ORG )

edge

• 劃分的邊緣 (并不是四方邊緣結(jié)構(gòu))

type

• 確定函數(shù)返回哪條相關(guān)邊緣，是下面幾種之一：

  • CV_NEXT_AROUND_ORG - 邊緣原點(diǎn)的下一條 (eOnext on the picture above if e is the input edge)

  • CV_NEXT_AROUND_DST - 邊緣頂點(diǎn)的下一條 (eDnext)

  • CV_PREV_AROUND_ORG - 邊緣原點(diǎn)的前一條 (reversed eRnext)

  • CV_PREV_AROUND_DST - 邊緣終點(diǎn)的前一條 (reversed eLnext)

  • CV_NEXT_AROUND_LEFT - 左區(qū)域的下一條 (eLnext)

  • CV_NEXT_AROUND_RIGHT - 右區(qū)域的下一條(eRnext)

  • CV_PREV_AROUND_LEFT - 左區(qū)域的前一條 (reversed eOnext)

  • CV_PREV_AROUND_RIGHT - 右區(qū)域的前一條 (reversed eDnext)

函數(shù) cvSubdiv2DGetEdge 返回與輸入邊緣相關(guān)的邊緣

Subdiv2DRotateEdge

返回同一個四方邊緣結(jié)構(gòu)中的另一條邊緣

CvSubdiv2DEdge  cvSubdiv2DRotateEdge( CvSubdiv2DEdge edge, int rotate );

edge

• 劃分的邊緣 (并不是四方邊緣結(jié)構(gòu))

type

• 確定函數(shù)根據(jù)輸入的邊緣返回同一四方邊緣結(jié)構(gòu)中的哪條邊緣，是下面幾種之一:

  • 0 - 輸入邊緣 (上圖中的e，如果e是輸入邊緣)

  • 1 - 旋轉(zhuǎn)邊緣 (eRot)

  • 2 -逆邊緣 ( e的反向邊緣)

  • 3 - 旋轉(zhuǎn)邊緣的反向邊緣(eRot的反向邊緣， 圖中綠色)

函數(shù) cvSubdiv2DRotateEdge 根據(jù)輸入的邊緣返回四方邊緣結(jié)構(gòu)中的一條邊緣

Subdiv2DEdgeOrg

返回邊緣的原點(diǎn)

CvSubdiv2DPoint* cvSubdiv2DEdgeOrg( CvSubdiv2DEdge edge );

edge

• 劃分的邊緣 (并不是四方邊緣結(jié)構(gòu))

函數(shù) cvSubdiv2DEdgeOrg 返回邊緣的原點(diǎn)。如果該邊緣是從對偶劃分得到并且虛點(diǎn)坐標(biāo)還沒有計(jì)算出來，可能返回空指針。虛點(diǎn)可以用函數(shù)來cvCalcSubdivVoronoi2D計(jì)算。

Subdiv2DEdgeDst

Returns edge destination

CvSubdiv2DPoint* cvSubdiv2DEdgeDst( CvSubdiv2DEdge edge );

edge

• 劃分的邊緣 (并不是四方邊緣結(jié)構(gòu))

函數(shù) cvSubdiv2DEdgeDst 返回邊緣的終點(diǎn)。如果該邊緣是從對偶劃分得到并且虛點(diǎn)坐標(biāo)還沒有計(jì)算出來，可能返回空指針。虛點(diǎn)可以用函數(shù)來cvCalcSubdivVoronoi2D計(jì)算。

CreateSubdivDelaunay2D

生成的空Delaunay 三角測量

CvSubdiv2D* cvCreateSubdivDelaunay2D( CvRect rect, CvMemStorage* storage );

rect

• Rectangle包括所有待加入劃分操作的2d點(diǎn)的四方形。

storage

• 劃分操作的存儲器

函數(shù) cvCreateSubdivDelaunay2D 生成一個空的Delaunay 劃分, 其中2d points可以進(jìn)一步使用函數(shù) cvSubdivDelaunay2DInsert來添加。所有的點(diǎn)一定要在指定的四方形中添加，否則就會報(bào)運(yùn)行錯誤。

SubdivDelaunay2DInsert

向 Delaunay三角測量中插入一個點(diǎn)

CvSubdiv2DPoint*  cvSubdivDelaunay2DInsert( CvSubdiv2D* subdiv, CvPoint2D32f pt);

subdiv

• 通過函數(shù) cvCreateSubdivDelaunay2D.生成的Delaunay劃分

pt

• 待插入的點(diǎn)

函數(shù) cvSubdivDelaunay2DInsert 向劃分的結(jié)構(gòu)中插入一個點(diǎn)并且正確地改變劃分的拓樸結(jié)構(gòu)。如果劃分結(jié)構(gòu)中已經(jīng)存在一個相同的坐標(biāo)點(diǎn)，則不會有新點(diǎn)插入。該函數(shù)返回指向已插入點(diǎn)的指針。在這個截?cái)啵挥?jì)算任何虛點(diǎn)坐標(biāo)。

Subdiv2DLocate

在 Delaunay三角測量中定位輸入點(diǎn)

CvSubdiv2DPointLocation  cvSubdiv2DLocate( CvSubdiv2D* subdiv, CvPoint2D32f pt,
                                           CvSubdiv2DEdge* edge,
                                           CvSubdiv2DPoint** vertex=NULL );

subdiv

• Delaunay 或者是其它分割結(jié)構(gòu).

pt

• 待定位的輸入點(diǎn)

edge

• 與輸入點(diǎn)對應(yīng)的輸入邊緣(點(diǎn)在其上或者其右)

vertex

• 與輸入點(diǎn)對應(yīng)的輸出頂點(diǎn)坐標(biāo)(指向double類型)，可選。

函數(shù) cvSubdiv2DLocate 在劃分中定位輸入點(diǎn)，共有5種類型:

• 輸入點(diǎn)落入某小區(qū)域內(nèi)。 函數(shù)返回參數(shù)　CV_PTLOC_INSIDE 且*edge 中包含小區(qū)域的邊緣之一。

• 輸入點(diǎn)落p在邊緣之上。 函數(shù)返回參數(shù) CV_PTLOC_ON_EDGE 且 *edge 包含此邊緣。

• 輸入點(diǎn)與劃分的頂點(diǎn)之一相對應(yīng)。 函數(shù)返回參數(shù) CV_PTLOC_VERTEX 且 *vertex 中包括指向該頂點(diǎn)的指針；

• 輸入點(diǎn)落在劃分的參考區(qū)域之外。 函數(shù)返回參數(shù) CV_PTLOC_OUTSIDE_RECT且不填寫任何指針。

• 輸入?yún)?shù)之一有誤。函數(shù)報(bào)運(yùn)行錯誤(如果已經(jīng)選則了沉默或者父母出錯模式，則函數(shù)返回CV_PTLOC_ERROR) 。

FindNearestPoint2D

根據(jù)輸入點(diǎn)，找到其最近的劃分頂點(diǎn)

CvSubdiv2DPoint* cvFindNearestPoint2D( CvSubdiv2D* subdiv, CvPoint2D32f pt );

subdiv

• Delaunay或者其它劃分方式

pt

• 輸入點(diǎn)

函數(shù) cvFindNearestPoint2D 是另一個定位輸入點(diǎn)的函數(shù)。該函數(shù)找到輸入點(diǎn)的最近劃分頂點(diǎn)。盡管劃分出的小區(qū)域(facet)被用來作為起始點(diǎn)，但是輸入點(diǎn)不一定非得在最終找到的頂點(diǎn)所在的小區(qū)域之內(nèi)。該函數(shù)返回指向找到的劃分頂點(diǎn)的指針。

CalcSubdivVoronoi2D

計(jì)算Voronoi圖表的細(xì)胞結(jié)構(gòu)

void cvCalcSubdivVoronoi2D( CvSubdiv2D* subdiv );

subdiv

• Delaunay 劃分,其中所有的點(diǎn)已經(jīng)添加 。

函數(shù) cvCalcSubdivVoronoi2D 計(jì)算虛點(diǎn)的坐標(biāo)，所有與原劃分中的某頂點(diǎn)相對應(yīng)的虛點(diǎn)形成了(當(dāng)他們相互連接時)該頂點(diǎn)的Voronoi 細(xì)胞的邊界。

ClearSubdivVoronoi2D

移除所有的虛點(diǎn)

void cvClearSubdivVoronoi2D( CvSubdiv2D* subdiv );

subdiv

• Delaunay 劃分

函數(shù) cvClearSubdivVoronoi2D 移除所有的虛點(diǎn)。當(dāng)劃分的結(jié)果被函數(shù)cvCalcSubdivVoronoi2D的前一次調(diào)用更改時，該函數(shù)被cvCalcSubdivVoronoi2D內(nèi)部調(diào)用 。

還有一些其它的底層處理函數(shù)與平面劃分操作協(xié)同工作，參見 cv.h 及源碼。生成 delaunay.c 三角測量以及2d隨機(jī)點(diǎn)集的Voronoi 圖表的演示代碼可以在 opencv