功力不夠只能那別人的代碼研究,不知怎么的我怎么會翻到這個東東的.
首先把代碼貼出來把,分析的時候肯定是支離破碎的.
//
This function splits the input sequence or set into one or more equivalence classes and
//
returns the vector of labels - 0-based class indexes for each element.
//
predicate(a,b) returns true if the two sequence elements certainly belong to the same class.
//
//
The algorithm is described in "Introduction to Algorithms"
//
by Cormen, Leiserson and Rivest, the chapter "Data structures for disjoint sets"
template<typename _Tp,
class
_EqPredicate>
int
partition(
const
vector<_Tp>& _vec, 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
;
vector
<
int
> _nodes(N*
2
);
int
(*nodes)[
2
] = (
int
(*)[
2
])&_nodes[
0
];
//
The first O(N) pass: create N single-vertex trees
for
(i =
0
; i < N; i++
)
{
nodes[i][PARENT]
=-
1
;
nodes[i][RANK]
=
0
;
}
//
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;
while
( nodes[root2][PARENT] >=
0
)
root2
=
nodes[root2][PARENT];
if
( root2 !=
root )
{
//
unite both trees
int
rank = nodes[root][RANK], rank2 =
nodes[root2][RANK];
if
( rank >
rank2 )
nodes[root2][PARENT]
=
root;
else
{
nodes[root][PARENT]
=
root2;
nodes[root2][RANK]
+= rank ==
rank2;
root
=
root2;
}
assert( nodes[root][PARENT]
<
0
);
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;
while
( nodes[root][PARENT] >=
0
)
root
=
nodes[root][PARENT];
//
re-use the rank as the class label
if
( nodes[root][RANK] >=
0
)
nodes[root][RANK]
= ~nclasses++
;
labels[i]
= ~
nodes[root][RANK];
}
return
nclasses;
}
首先說下并查集,主要功能是就是將相似的元素分為一類,有點像聚類,但是聚類沒有具體的相似測試.如果我們有{1,1,3,3,4,4,4,4,4,5,5,6,6},直接可以看出來這個可以分成{{1,1},{3,3},{4,4,4,4,4},{5,5},{6,6}}.當然這個前提是兩個元素相似等于相等.普通的可以這樣做,先排序再相連的兩個元素比較,如相等,再往后移動,具體可以看 http://www.haskell.org/haskellwiki/99_questions/1_to_10 第9題.
這個是在一維的情況下,但是如果到了二維呢,(x1,y1)是不可以排序的的,就像實數點是可以排序,但是復數卻不可以一樣.這個時候可以定義`相似`,可以這樣仍為如果(x1,y1),(x2,y2)的歐式距離小于某個值就認為相似.這個時候再分類就可以了.
相似是兩個元素的比較操作,在代碼中體現為 '_EqPredicate predicate=_EqPredicate()'可以作為參數傳給它的.
并查集的基本結構可以是這樣的.
(截圖來自<數據結構與算法分析-C語言版>)
每個元素有一個指向父親指針,如果2個元素相同就可以把其中一個元素的父親指向另一個.如下
當然由于元素的結構簡單,可以直接使用數組代替,數組的位置為元素的value,數組的值為它爹的地址.如
{0,1,2,3,3,4} ?可以認為0,1,2,3是單元素,第4個它爹是3,第5個元素它爹是4 可以看成{0,1,2,3<-4<-5}.所以上面的圖可以寫成
當然圖中指向0認為是單個元素.
在OpenCV代碼中表現為
for
(i =
0
; i < N; i++
)
{
nodes[i][PARENT]
=-
1
;
nodes[i][RANK]
=
0
;
}
OpenCV中使用的指向-1.其中的RANK等會兒再說.
如何合并兩個值呢,簡單的情況是兩個元素都沒有爹,但是如果這兩個元素都有爹呢,如果爹一樣,pass,已經在同一個類別里了,如果不一樣呢,還要繼續判斷.其實這里可以聯想到<編程之美>上的一道題目'
3.6 編程判斷兩個鏈表是否相交
',其實解法很簡單,先分別找爹的爹的爹....的爹..如果它們的老祖宗相等就可以認為是相等的,pass.如果不等,對它們的祖宗合并.
找祖宗的代碼如下..
//
find root
while
( nodes[root][PARENT] >=
0
)
root
=
nodes[root][PARENT];
while
( nodes[root2][PARENT] >=
0
)
root2
=
nodes[root2][PARENT];
合并祖宗可以簡單的如合并單個元素一樣的,單個的點指向另一個點,但是這種情況下,最壞的情況如下,{1<-2<-3<-4<-5...<-n-1<n}.如果比較n-1,和n元素.這時的情況就是.需要遍歷2n-1次元素,如果在合并是有一種情況.
1
/ | \
2 3 ..n 這種情況就是特好的了,反正都是同一類,誰當爹都一樣(這話有問題的),這種情況下只需要2次就可以找到了.
當然這個術語叫
路徑壓縮
,代碼如下.
//
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;
}
優化查找的另一種方法就是合并的時候,不直接簡單的將一個元素認為是爹,當爹的條件首選是資歷老{Rank}必須要大,最后的效果就是樹盡量平衡.避免單鏈表的情況,當然術語叫
Rank合并
代碼如下:
//
unite both trees
int
rank = nodes[root][RANK], rank2 =
nodes[root2][RANK];
if
( rank >
rank2 )
nodes[root2][PARENT]
=
root;
else
{
nodes[root][PARENT]
=
root2;
nodes[root2][RANK]
+= rank ==
rank2;
root
=
root2;
}
最后就是標出每個元素所在的類別了.從第一個元素開始,直接訪問它的祖宗,設置類別.此時OpenCV作者有一次體現了功力深厚的時候,直接在RANK上填寫類別,反正樹已經建好了,RANK沒用了,RANK上的值都是非負的,就用~來區分,設置元素時在用~改回去,使用~而不用-的原因估計是位操作比較快吧.
最后說下應用.
1.聚集頂點. 相似條件歐式距離<10.
before.
after.
部分代碼如下.
1
struct
PointLike{
2
PointLike(
int
thresh){
3
this
->thresh =
thresh;
4
}
5
bool
operator
()(cv::Point p1,cv::Point p2){
6
int
x = p1.x -
p2.x;
7
int
y = p1.y -
p2.y;
8
return
x*x+y*y <=thresh*
thresh;
9
}
10
int
thresh;
11
};
12
13
PointLike plike(
20
);
14
std::vector<
int
>
labels;
15
int
count;
16
count =
cv::partition(pts_v,labels,plike);
17
18
for
(size_t i =
0
;i<pts_v.size();i++
)
19
{
20
cv::circle(after,pts_v[i],
2
,colorTab[labels[i]]);
21
}
2.合并重疊的矩形.(人臉識別里用的)
相似條件(重疊面積占小矩形面基的75%)
before:
after:
部分代碼如下:
1
struct
RectLike{
2
RectLike(
double
p){
3
this
->p =
p;
4
}
5
bool
operator
()(cv::Rect r1,cv::Rect r2){
6
int
area1 =
r1.area();
7
int
area2 =
r2.area();
8
//
相交Rect面積
9
int
area =
overlap_rect_area(r1,r2);
10
return
area1<area2?area>=p*area1:area>=p*
area2;
11
}
12
double
p;
13
};
14
15
RectLike rLike(
0.75
);
16
std::vector<
int
>
labels;
17
int
count;
18
count =
cv::partition(rects_v,labels,rLike);
19
20
for
(size_t i =
0
;i<rects_v.size();i++
)
21
{
22
cv::rectangle(after,rects_v[i],colorTab[labels[i]]);
23
}
好了總算寫結束了.
其實還有很多的應用的.
推薦 http://mindlee.net/2011/10/21/disjoint-sets/ .
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
