1// This file is part of OpenCV project.
2// It is subject to the license terms in the LICENSE file found in the top-level directory
3// of this distribution and at http://opencv.org/license.html.
4//
5// Copyright (C) 2013-2016, The Regents of The University of Michigan.
6//
7// This software was developed in the APRIL Robotics Lab under the
8// direction of Edwin Olson, ebolson@umich.edu. This software may be
9// available under alternative licensing terms; contact the address above.
10//
11// The views and conclusions contained in the software and documentation are those
12// of the authors and should not be interpreted as representing official policies,
13// either expressed or implied, of the Regents of The University of Michigan.
14#ifndef _OPENCV_UNIONFIND_HPP_
15#define _OPENCV_UNIONFIND_HPP_
16
17namespace cv {
18namespace aruco {
19
20typedef struct unionfind unionfind_t;
21struct unionfind{
22 uint32_t maxid;
23 struct ufrec *data;
24};
25
26struct ufrec{
27 // the parent of this node. If a node's parent is its own index,
28 // then it is a root.
29 uint32_t parent;
30
31 // for the root of a connected component, the number of components
32 // connected to it. For intermediate values, it's not meaningful.
33 uint32_t size;
34};
35
36static inline unionfind_t *unionfind_create(uint32_t maxid){
37 unionfind_t *uf = (unionfind_t*) calloc(nmemb: 1, size: sizeof(unionfind_t));
38 uf->maxid = maxid;
39 uf->data = (struct ufrec*) malloc(size: (maxid+1) * sizeof(struct ufrec));
40 for (unsigned int i = 0; i <= maxid; i++) {
41 uf->data[i].size = 1;
42 uf->data[i].parent = i;
43 }
44 return uf;
45}
46
47static inline void unionfind_destroy(unionfind_t *uf){
48 free(ptr: uf->data);
49 free(ptr: uf);
50}
51
52/*
53static inline uint32_t unionfind_get_representative(unionfind_t *uf, uint32_t id)
54{
55 // base case: a node is its own parent
56 if (uf->data[id].parent == id)
57 return id;
58
59 // otherwise, recurse
60 uint32_t root = unionfind_get_representative(uf, uf->data[id].parent);
61
62 // short circuit the path. [XXX This write prevents tail recursion]
63 uf->data[id].parent = root;
64
65 return root;
66}
67 */
68
69// this one seems to be every-so-slightly faster than the recursive
70// version above.
71static inline uint32_t unionfind_get_representative(unionfind_t *uf, uint32_t id){
72 uint32_t root = id;
73
74 // chase down the root
75 while (uf->data[root].parent != root) {
76 root = uf->data[root].parent;
77 }
78
79 // go back and collapse the tree.
80 //
81 // XXX: on some of our workloads that have very shallow trees
82 // (e.g. image segmentation), we are actually faster not doing
83 // this...
84 while (uf->data[id].parent != root) {
85 uint32_t tmp = uf->data[id].parent;
86 uf->data[id].parent = root;
87 id = tmp;
88 }
89
90 return root;
91}
92
93static inline uint32_t unionfind_get_set_size(unionfind_t *uf, uint32_t id){
94 uint32_t repid = unionfind_get_representative(uf, id);
95 return uf->data[repid].size;
96}
97
98static inline uint32_t unionfind_connect(unionfind_t *uf, uint32_t aid, uint32_t bid){
99 uint32_t aroot = unionfind_get_representative(uf, id: aid);
100 uint32_t broot = unionfind_get_representative(uf, id: bid);
101
102 if (aroot == broot)
103 return aroot;
104
105 // we don't perform "union by rank", but we perform a similar
106 // operation (but probably without the same asymptotic guarantee):
107 // We join trees based on the number of *elements* (as opposed to
108 // rank) contained within each tree. I.e., we use size as a proxy
109 // for rank. In my testing, it's often *faster* to use size than
110 // rank, perhaps because the rank of the tree isn't that critical
111 // if there are very few nodes in it.
112 uint32_t asize = uf->data[aroot].size;
113 uint32_t bsize = uf->data[broot].size;
114
115 // optimization idea: We could shortcut some or all of the tree
116 // that is grafted onto the other tree. Pro: those nodes were just
117 // read and so are probably in cache. Con: it might end up being
118 // wasted effort -- the tree might be grafted onto another tree in
119 // a moment!
120 if (asize > bsize) {
121 uf->data[broot].parent = aroot;
122 uf->data[aroot].size += bsize;
123 return aroot;
124 } else {
125 uf->data[aroot].parent = broot;
126 uf->data[broot].size += asize;
127 return broot;
128 }
129}
130}}
131#endif
132

source code of opencv/modules/objdetect/src/aruco/apriltag/unionfind.hpp