OpenCV源码解析：partition分类（聚类）

浅浅的花香味﹌ 2022-05-15 02:55 225阅读 0赞

功能：把数据类型为\_Tp的一组集合进行聚类，也就是根据相似或相同的某特征进行归类，最后分成若干个类别。  
这里是以相似矩形的分类为例进行讲解，重点内容都在注释中。整体过程就是先判断两个矩形是否相似，如果相似，就决让其中一个做父节点，一个做子节点，然后再检查这个关系是否影响了其他节点的关系，如果有影响，就调整。

检查完之后就沿所有的节点找到顶级父节点，如果该 父节点还没有分类，就分类成一个新的分类值（nclasses），并把下一个类的值设为nclasses++, 直到完成所有的节点。  
Predicate函数使用的是（class CV\_EXPORTS SimilarRects），使用实例请参考CascadeDetect.cpp中的groupRectangles。

## partition函数 ##

template<typename \_Tp, class \_EqPredicate> int  
partition( const std::vector<\_Tp>& \_vec, std::vector<int>& labels,  
          \_EqPredicate predicate=\_EqPredicate())  
\{  
    int i, j, N = (int)\_vec.size();  
    const \_Tp\* vec = &\_vec\[0\];

const int PARENT=0;  
    const int RANK=1;

std::vector<int> \_nodes(N\*2);  
    int (\*nodes)\[2\] = (int(\*)\[2\])&\_nodes\[0\];  // 定义一个2维组nodes来处理\_nodes\[\]

// The first O(N) pass: create N single-vertex trees  
    for(i = 0; i < N; i++)  
    \{  
        nodes\[i\]\[PARENT\]=-1;  
        nodes\[i\]\[RANK\] = 0;  
\}

// 注意：  
    // root表示i的根节点  
    // root2表示j的根节点  
    // The main O(N^2) pass: merge connected components  
    for( i = 0; i < N; i++ )  
    \{  
        int root = i;

// find root  
        while( nodes\[root\]\[PARENT\] >= 0 )  
            root = nodes\[root\]\[PARENT\];

for( j = 0; j < N; j++ )  
        \{  
            if( i == j || !predicate(vec\[i\], vec\[j\])) // 如果是同一个矩形；或者，两个矩形不相似，则继续找下一个  
                continue;  
            int root2 = j;  // 找到和vec\[i\]相似的矩形

while( nodes\[root2\]\[PARENT\] >= 0 )  
                root2 = nodes\[root2\]\[PARENT\]; // 找到相似矩形的根矩形

if( root2 != root ) // 如果这个根矩形和当前root不是同一个，就合并  
            \{  
                // 改变一下root1和root的父子关系  
                // unite both trees  
                int rank = nodes\[root\]\[RANK\], rank2 = nodes\[root2\]\[RANK\];  
                if( rank > rank2 ) // 谁rank大谁做父节点  
                    nodes\[root2\]\[PARENT\] = root;（root rank不变）  
                else  
                \{  
                    nodes\[root\]\[PARENT\] = root2;  
                    nodes\[root2\]\[RANK\] += rank == rank2; // 如果同rank的做了子节点，就升一级  
                    root = root2;  
                \}  
                CV\_Assert( nodes\[root\]\[PARENT\] < 0 );

// 因为上面root1和root关系的改变可能影响到节点  
               // 这里再整理一次，直到最终的父节点全部处理完  
                int k = j, parent;  
                // compress the path from node2 to root  
                while( (parent = nodes\[k\]\[PARENT\]) >= 0 )  
                \{  
                    nodes\[k\]\[PARENT\] = root;  
                    k = parent;  
                \}

// compress the path from node to root  
                k = i;  
                while( (parent = nodes\[k\]\[PARENT\]) >= 0 )  
                \{  
                    nodes\[k\]\[PARENT\] = root;  
                    k = parent;  
                \}  
            \}  
        \}  
    \}

// Final O(N) pass: enumerate classes  
    labels.resize(N);  
    int nclasses = 0;

for( i = 0; i < N; i++ )  
    \{  
        int root = i;  
        // 找到该i节点的根节点  
        while( nodes\[root\]\[PARENT\] >= 0 )  
            root = nodes\[root\]\[PARENT\];

// 如果该根节点还没有分类，就设置一个新的分类值（nclasses），并把下一个类的值设为nclasses++   
        // re-use the rank as the class label  
        if( nodes\[root\]\[RANK\] >= 0 )  // 如果该节点RANK还没有设置（也就是该根节点还没有分类）  
            nodes\[root\]\[RANK\] = ~nclasses++;  // 取反是得到对应的负数，用来表示该节点已经分类  
        labels\[i\] = ~nodes\[root\]\[RANK\];   
    \}

return nclasses; // 返回总类别个数  
\}

## 相似的矩形的判断方法：SimilarRects类 ##

class CV\_EXPORTS SimilarRects  
\{  
public:  
    SimilarRects(double \_eps) : eps(\_eps) \{\}  
    inline bool operator()(const Rect& r1, const Rect& r2) const  
    \{  
        // delta为最小长宽和的eps/2倍 = \[(width + height)/2\] \* eps  
        double delta = eps\*(std::min(r1.width, r2.width) + std::min(r1.height, r2.height))\*0.5;

// 如果矩形的四个顶点的位置差别都小于delta，则表示相似的矩形  
        return std::abs(r1.x - r2.x) <= delta &&  
               std::abs(r1.y - r2.y) <= delta &&  
               std::abs(r1.x + r1.width - r2.x - r2.width) <= delta &&  
               std::abs(r1.y + r1.height - r2.y - r2.height) <= delta;  
    \}  
    double eps;  
\};