功力不夠只能那別人的代碼研究,不知怎么的我怎么會(huì)翻到這個(gè)東東的.
首先把代碼貼出來把,分析的時(shí)候肯定是支離破碎的.
//
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;
}
首先說下并查集,主要功能是就是將相似的元素分為一類,有點(diǎn)像聚類,但是聚類沒有具體的相似測(cè)試.如果我們有{1,1,3,3,4,4,4,4,4,5,5,6,6},直接可以看出來這個(gè)可以分成{{1,1},{3,3},{4,4,4,4,4},{5,5},{6,6}}.當(dāng)然這個(gè)前提是兩個(gè)元素相似等于相等.普通的可以這樣做,先排序再相連的兩個(gè)元素比較,如相等,再往后移動(dòng),具體可以看 http://www.haskell.org/haskellwiki/99_questions/1_to_10 第9題.
這個(gè)是在一維的情況下,但是如果到了二維呢,(x1,y1)是不可以排序的的,就像實(shí)數(shù)點(diǎn)是可以排序,但是復(fù)數(shù)卻不可以一樣.這個(gè)時(shí)候可以定義`相似`,可以這樣仍為如果(x1,y1),(x2,y2)的歐式距離小于某個(gè)值就認(rèn)為相似.這個(gè)時(shí)候再分類就可以了.
相似是兩個(gè)元素的比較操作,在代碼中體現(xiàn)為 '_EqPredicate predicate=_EqPredicate()'可以作為參數(shù)傳給它的.
并查集的基本結(jié)構(gòu)可以是這樣的.
(截圖來自<數(shù)據(jù)結(jié)構(gòu)與算法分析-C語(yǔ)言版>)
每個(gè)元素有一個(gè)指向父親指針,如果2個(gè)元素相同就可以把其中一個(gè)元素的父親指向另一個(gè).如下
當(dāng)然由于元素的結(jié)構(gòu)簡(jiǎn)單,可以直接使用數(shù)組代替,數(shù)組的位置為元素的value,數(shù)組的值為它爹的地址.如
{0,1,2,3,3,4} ?可以認(rèn)為0,1,2,3是單元素,第4個(gè)它爹是3,第5個(gè)元素它爹是4 可以看成{0,1,2,3<-4<-5}.所以上面的圖可以寫成
當(dāng)然圖中指向0認(rèn)為是單個(gè)元素.
在OpenCV代碼中表現(xiàn)為
for
(i =
0
; i < N; i++
)
{
nodes[i][PARENT]
=-
1
;
nodes[i][RANK]
=
0
;
}
OpenCV中使用的指向-1.其中的RANK等會(huì)兒再說.
如何合并兩個(gè)值呢,簡(jiǎn)單的情況是兩個(gè)元素都沒有爹,但是如果這兩個(gè)元素都有爹呢,如果爹一樣,pass,已經(jīng)在同一個(gè)類別里了,如果不一樣呢,還要繼續(xù)判斷.其實(shí)這里可以聯(lián)想到<編程之美>上的一道題目'
3.6 編程判斷兩個(gè)鏈表是否相交
',其實(shí)解法很簡(jiǎn)單,先分別找爹的爹的爹....的爹..如果它們的老祖宗相等就可以認(rèn)為是相等的,pass.如果不等,對(duì)它們的祖宗合并.
找祖宗的代碼如下..
//
find root
while
( nodes[root][PARENT] >=
0
)
root
=
nodes[root][PARENT];
while
( nodes[root2][PARENT] >=
0
)
root2
=
nodes[root2][PARENT];
合并祖宗可以簡(jiǎn)單的如合并單個(gè)元素一樣的,單個(gè)的點(diǎn)指向另一個(gè)點(diǎn),但是這種情況下,最壞的情況如下,{1<-2<-3<-4<-5...<-n-1<n}.如果比較n-1,和n元素.這時(shí)的情況就是.需要遍歷2n-1次元素,如果在合并是有一種情況.
1
/ | \
2 3 ..n 這種情況就是特好的了,反正都是同一類,誰(shuí)當(dāng)?shù)家粯?這話有問題的),這種情況下只需要2次就可以找到了.
當(dāng)然這個(gè)術(shù)語(yǔ)叫
路徑壓縮
,代碼如下.
//
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;
}
優(yōu)化查找的另一種方法就是合并的時(shí)候,不直接簡(jiǎn)單的將一個(gè)元素認(rèn)為是爹,當(dāng)?shù)臈l件首選是資歷老{Rank}必須要大,最后的效果就是樹盡量平衡.避免單鏈表的情況,當(dāng)然術(shù)語(yǔ)叫
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;
}
最后就是標(biāo)出每個(gè)元素所在的類別了.從第一個(gè)元素開始,直接訪問它的祖宗,設(shè)置類別.此時(shí)OpenCV作者有一次體現(xiàn)了功力深厚的時(shí)候,直接在RANK上填寫類別,反正樹已經(jīng)建好了,RANK沒用了,RANK上的值都是非負(fù)的,就用~來區(qū)分,設(shè)置元素時(shí)在用~改回去,使用~而不用-的原因估計(jì)是位操作比較快吧.
最后說下應(yīng)用.
1.聚集頂點(diǎn). 相似條件歐式距離<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.合并重疊的矩形.(人臉識(shí)別里用的)
相似條件(重疊面積占小矩形面基的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
}
好了總算寫結(jié)束了.
其實(shí)還有很多的應(yīng)用的.
推薦 http://mindlee.net/2011/10/21/disjoint-sets/ .
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
