← Back to branch summary

~paparazzi-uav/paparazzi/v5.0-manual

« back to all changes in this revision

Viewing changes to sw/ext/opencv_bebop/opencv/doc/py_tutorials/py_imgproc/py_contours/py_contours_hierarchy/py_contours_hierarchy.markdown

  • Committer: Paparazzi buildbot
  • Date: 2016-05-18 15:00:29 UTC
  • Revision ID: felix.ruess+docbot@gmail.com-20160518150029-e8lgzi5kvb4p7un9
Manual import commit 4b8bbb730080dac23cf816b98908dacfabe2a8ec from v5.0 branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
sw/ext/opencv_bebop/opencv/doc/py_tutorials/py_imgproc/py_contours/py_contours_hierarchy/py_contours_hierarchy.markdown
 
1
Contours Hierarchy {#tutorial_py_contours_hierarchy}
 
2
==================
 
3
 
 
4
Goal
 
5
----
 
6
 
 
7
This time, we learn about the hierarchy of contours, i.e. the parent-child relationship in Contours.
 
8
 
 
9
Theory
 
10
------
 
11
 
 
12
In the last few articles on contours, we have worked with several functions related to contours
 
13
provided by OpenCV. But when we found the contours in image using **cv2.findContours()** function,
 
14
we have passed an argument, **Contour Retrieval Mode**. We usually passed **cv2.RETR_LIST** or
 
15
**cv2.RETR_TREE** and it worked nice. But what does it actually mean ?
 
16
 
 
17
Also, in the output, we got three arrays, first is the image, second is our contours, and one more
 
18
output which we named as **hierarchy** (Please checkout the codes in previous articles). But we
 
19
never used this hierarchy anywhere. Then what is this hierarchy and what is it for ? What is its
 
20
relationship with the previous mentioned function argument ?
 
21
 
 
22
That is what we are going to deal in this article.
 
23
 
 
24
### What is Hierarchy?
 
25
 
 
26
Normally we use the **cv2.findContours()** function to detect objects in an image, right ? Sometimes
 
27
objects are in different locations. But in some cases, some shapes are inside other shapes. Just
 
28
like nested figures. In this case, we call outer one as **parent** and inner one as **child**. This
 
29
way, contours in an image has some relationship to each other. And we can specify how one contour is
 
30
connected to each other, like, is it child of some other contour, or is it a parent etc.
 
31
Representation of this relationship is called the **Hierarchy**.
 
32
 
 
33
Consider an example image below :
 
34
 
 
35
![image](images/hierarchy.png)
 
36
 
 
37
In this image, there are a few shapes which I have numbered from **0-5**. *2 and 2a* denotes the
 
38
external and internal contours of the outermost box.
 
39
 
 
40
Here, contours 0,1,2 are **external or outermost**. We can say, they are in **hierarchy-0** or
 
41
simply they are in **same hierarchy level**.
 
42
 
 
43
Next comes **contour-2a**. It can be considered as a **child of contour-2** (or in opposite way,
 
44
contour-2 is parent of contour-2a). So let it be in **hierarchy-1**. Similarly contour-3 is child of
 
45
contour-2 and it comes in next hierarchy. Finally contours 4,5 are the children of contour-3a, and
 
46
they come in the last hierarchy level. From the way I numbered the boxes, I would say contour-4 is
 
47
the first child of contour-3a (It can be contour-5 also).
 
48
 
 
49
I mentioned these things to understand terms like **same hierarchy level**, **external contour**,
 
50
**child contour**, **parent contour**, **first child** etc. Now let's get into OpenCV.
 
51
 
 
52
### Hierarchy Representation in OpenCV
 
53
 
 
54
So each contour has its own information regarding what hierarchy it is, who is its child, who is its
 
55
parent etc. OpenCV represents it as an array of four values : **[Next, Previous, First_Child,
 
56
Parent]**
 
57
 
 
58
<center>*"Next denotes next contour at the same hierarchical level."*</center>
 
59
 
 
60
For eg, take contour-0 in our picture. Who is next contour in its same level ? It is contour-1. So
 
61
simply put Next = 1. Similarly for Contour-1, next is contour-2. So Next = 2.
 
62
 
 
63
What about contour-2? There is no next contour in the same level. So simply, put Next = -1. What
 
64
about contour-4? It is in same level with contour-5. So its next contour is contour-5, so Next = 5.
 
65
 
 
66
<center>*"Previous denotes previous contour at the same hierarchical level."*</center>
 
67
 
 
68
It is same as above. Previous contour of contour-1 is contour-0 in the same level. Similarly for
 
69
contour-2, it is contour-1. And for contour-0, there is no previous, so put it as -1.
 
70
 
 
71
<center>*"First_Child denotes its first child contour."*</center>
 
72
 
 
73
There is no need of any explanation. For contour-2, child is contour-2a. So it gets the
 
74
corresponding index value of contour-2a. What about contour-3a? It has two children. But we take
 
75
only first child. And it is contour-4. So First_Child = 4 for contour-3a.
 
76
 
 
77
<center>*"Parent denotes index of its parent contour."*</center>
 
78
 
 
79
It is just opposite of **First_Child**. Both for contour-4 and contour-5, parent contour is
 
80
contour-3a. For contour-3a, it is contour-3 and so on.
 
81
 
 
82
@note If there is no child or parent, that field is taken as -1
 
83
 
 
84
So now we know about the hierarchy style used in OpenCV, we can check into Contour Retrieval Modes
 
85
in OpenCV with the help of same image given above. ie what do flags like cv2.RETR_LIST,
 
86
cv2.RETR_TREE, cv2.RETR_CCOMP, cv2.RETR_EXTERNAL etc mean?
 
87
 
 
88
Contour Retrieval Mode
 
89
----------------------
 
90
 
 
91
### 1. RETR_LIST
 
92
 
 
93
This is the simplest of the four flags (from explanation point of view). It simply retrieves all the
 
94
contours, but doesn't create any parent-child relationship. **Parents and kids are equal under this
 
95
rule, and they are just contours**. ie they all belongs to same hierarchy level.
 
96
 
 
97
So here, 3rd and 4th term in hierarchy array is always -1. But obviously, Next and Previous terms
 
98
will have their corresponding values. Just check it yourself and verify it.
 
99
 
 
100
Below is the result I got, and each row is hierarchy details of corresponding contour. For eg, first
 
101
row corresponds to contour 0. Next contour is contour 1. So Next = 1. There is no previous contour,
 
102
so Previous = 0. And the remaining two, as told before, it is -1.
 
103
@code{.py}
 
104
>>> hierarchy
 
105
array([[[ 1, -1, -1, -1],
 
106
        [ 2,  0, -1, -1],
 
107
        [ 3,  1, -1, -1],
 
108
        [ 4,  2, -1, -1],
 
109
        [ 5,  3, -1, -1],
 
110
        [ 6,  4, -1, -1],
 
111
        [ 7,  5, -1, -1],
 
112
        [-1,  6, -1, -1]]])
 
113
@endcode
 
114
This is the good choice to use in your code, if you are not using any hierarchy features.
 
115
 
 
116
### 2. RETR_EXTERNAL
 
117
 
 
118
If you use this flag, it returns only extreme outer flags. All child contours are left behind. **We
 
119
can say, under this law, Only the eldest in every family is taken care of. It doesn't care about
 
120
other members of the family :)**.
 
121
 
 
122
So, in our image, how many extreme outer contours are there? ie at hierarchy-0 level?. Only 3, ie
 
123
contours 0,1,2, right? Now try to find the contours using this flag. Here also, values given to each
 
124
element is same as above. Compare it with above result. Below is what I got :
 
125
@code{.py}
 
126
>>> hierarchy
 
127
array([[[ 1, -1, -1, -1],
 
128
        [ 2,  0, -1, -1],
 
129
        [-1,  1, -1, -1]]])
 
130
@endcode
 
131
You can use this flag if you want to extract only the outer contours. It might be useful in some
 
132
cases.
 
133
 
 
134
### 3. RETR_CCOMP
 
135
 
 
136
This flag retrieves all the contours and arranges them to a 2-level hierarchy. ie external contours
 
137
of the object (ie its boundary) are placed in hierarchy-1. And the contours of holes inside object
 
138
(if any) is placed in hierarchy-2. If any object inside it, its contour is placed again in
 
139
hierarchy-1 only. And its hole in hierarchy-2 and so on.
 
140
 
 
141
Just consider the image of a "big white zero" on a black background. Outer circle of zero belongs to
 
142
first hierarchy, and inner circle of zero belongs to second hierarchy.
 
143
 
 
144
We can explain it with a simple image. Here I have labelled the order of contours in red color and
 
145
the hierarchy they belongs to, in green color (either 1 or 2). The order is same as the order OpenCV
 
146
detects contours.
 
147
 
 
148
![image](images/ccomp_hierarchy.png)
 
149
 
 
150
So consider first contour, ie contour-0. It is hierarchy-1. It has two holes, contours 1&2, and they
 
151
belong to hierarchy-2. So for contour-0, Next contour in same hierarchy level is contour-3. And
 
152
there is no previous one. And its first is child is contour-1 in hierarchy-2. It has no parent,
 
153
because it is in hierarchy-1. So its hierarchy array is [3,-1,1,-1]
 
154
 
 
155
Now take contour-1. It is in hierarchy-2. Next one in same hierarchy (under the parenthood of
 
156
contour-1) is contour-2. No previous one. No child, but parent is contour-0. So array is
 
157
[2,-1,-1,0].
 
158
 
 
159
Similarly contour-2 : It is in hierarchy-2. There is not next contour in same hierarchy under
 
160
contour-0. So no Next. Previous is contour-1. No child, parent is contour-0. So array is
 
161
[-1,1,-1,0].
 
162
 
 
163
Contour - 3 : Next in hierarchy-1 is contour-5. Previous is contour-0. Child is contour-4 and no
 
164
parent. So array is [5,0,4,-1].
 
165
 
 
166
Contour - 4 : It is in hierarchy 2 under contour-3 and it has no sibling. So no next, no previous,
 
167
no child, parent is contour-3. So array is [-1,-1,-1,3].
 
168
 
 
169
Remaining you can fill up. This is the final answer I got:
 
170
@code{.py}
 
171
>>> hierarchy
 
172
array([[[ 3, -1,  1, -1],
 
173
        [ 2, -1, -1,  0],
 
174
        [-1,  1, -1,  0],
 
175
        [ 5,  0,  4, -1],
 
176
        [-1, -1, -1,  3],
 
177
        [ 7,  3,  6, -1],
 
178
        [-1, -1, -1,  5],
 
179
        [ 8,  5, -1, -1],
 
180
        [-1,  7, -1, -1]]])
 
181
@endcode
 
182
 
 
183
### 4. RETR_TREE
 
184
 
 
185
And this is the final guy, Mr.Perfect. It retrieves all the contours and creates a full family
 
186
hierarchy list. **It even tells, who is the grandpa, father, son, grandson and even beyond... :)**.
 
187
 
 
188
For examle, I took above image, rewrite the code for cv2.RETR_TREE, reorder the contours as per the
 
189
result given by OpenCV and analyze it. Again, red letters give the contour number and green letters
 
190
give the hierarchy order.
 
191
 
 
192
![image](images/tree_hierarchy.png)
 
193
 
 
194
Take contour-0 : It is in hierarchy-0. Next contour in same hierarchy is contour-7. No previous
 
195
contours. Child is contour-1. And no parent. So array is [7,-1,1,-1].
 
196
 
 
197
Take contour-2 : It is in hierarchy-1. No contour in same level. No previous one. Child is
 
198
contour-2. Parent is contour-0. So array is [-1,-1,2,0].
 
199
 
 
200
And remaining, try yourself. Below is the full answer:
 
201
@code{.py}
 
202
>>> hierarchy
 
203
array([[[ 7, -1,  1, -1],
 
204
        [-1, -1,  2,  0],
 
205
        [-1, -1,  3,  1],
 
206
        [-1, -1,  4,  2],
 
207
        [-1, -1,  5,  3],
 
208
        [ 6, -1, -1,  4],
 
209
        [-1,  5, -1,  4],
 
210
        [ 8,  0, -1, -1],
 
211
        [-1,  7, -1, -1]]])
 
212
@endcode
 
213
 
 
214
Additional Resources
 
215
--------------------
 
216
 
 
217
Exercises
 
218
---------