-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathfractal-dimension.html
261 lines (182 loc) · 15.7 KB
/
fractal-dimension.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
<!DOCTYPE html>
<html lang="en">
<head>
<link href="/images/favicon.png" rel="icon">
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>trvrm.github.io</title>
<link rel="stylesheet" type="text/css" href="/theme/css/flatly.min.css" />
<link rel="stylesheet" type="text/css" href="/theme/css/style.css" />
<link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet" />
<link href="/theme/css/pygments/tango.css" rel="stylesheet">
<meta name="tags" content="Python" />
</head>
<body>
<section class="hero is-primary">
<!-- Hero header: will stick at the top -->
<div class="hero-head">
<nav class="navbar ">
<div class="navbar-menu is-active">
<div class="navbar-end">
<a class="navbar-item" href="https://twitter.com/trvrm">
<span class="icon"> <i class="fa fa-twitter"></i> </span>
twitter
</a>
<a class="navbar-item" href="https://github.com/trvrm">
<span class="icon"> <i class="fa fa-github"></i> </span>
github
</a>
</div>
</div>
</div>
</div>
<!-- Hero content: will be in the middle -->
<div class="hero-body">
<div class="container has-text-centered">
<p class="title is-1">trvrm.github.io</p>
</div>
</div>
<div class="hero-foot">
<nav class="navbar ">
<div class="navbar-brand is-active">
<a href="/" class="navbar-item" >
trvrm.github.io
</a>
</div>
<div class="navbar-menu is-active">
<div class="navbar-start">
<a class="navbar-item " href="/category/database.html">Database</a>
<a class="navbar-item is-active " href="/category/software.html">Software</a>
<a class="navbar-item " href="/category/systems.html">Systems</a>
</div>
</div>
</nav>
</div>
</section>
<section class="section">
<div class="container has-text-centered">
<p class="title is-3">
<a href="/fractal-dimension.html" rel="bookmark" title="Permalink to Fractal Dimension">
Fractal Dimension
</a>
</p>
<p class="subtitle is-5">
Tue 24 January 2017
</p>
</div>
<hr>
<div class="content ">
<p>Inspired by the <a href="https://www.youtube.com/watch?v=bSfe5M_zG2s">keynote</a> given at PyCon Portland by K Lars Lohn,, I wanted to try my hand
at computing the fractal dimension of a few different images.</p>
<p>This is a very simple implementation of a <a href="https://en.wikipedia.org/wiki/Minkowski%E2%80%93Bouligand_dimension">box counting</a> algorithm.</p>
<p>A couple of ideas are borrowed from https://github.com/twobraids/fracdim.</p>
<p>First some imports:</p>
<div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">pandas</span>
<span class="kn">import</span> <span class="nn">math</span>
<span class="kn">from</span> <span class="nn">IPython.display</span> <span class="kn">import</span> <span class="n">display</span>
<span class="kn">from</span> <span class="nn">PIL</span> <span class="kn">import</span> <span class="n">Image</span>
<span class="kn">import</span> <span class="nn">os</span>
<span class="kn">from</span> <span class="nn">scipy.stats</span> <span class="kn">import</span> <span class="n">linregress</span>
</pre></div>
<p>Then a function to create simple black and white images.</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">bw</span><span class="p">(</span><span class="n">img</span><span class="p">):</span>
<span class="n">gray</span> <span class="o">=</span> <span class="n">img</span><span class="o">.</span><span class="n">convert</span><span class="p">(</span><span class="s1">'L'</span><span class="p">)</span>
<span class="k">return</span> <span class="n">gray</span><span class="o">.</span><span class="n">point</span><span class="p">(</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="mi">0</span> <span class="k">if</span> <span class="n">x</span><span class="o"><</span><span class="mi">128</span> <span class="k">else</span> <span class="mi">1</span><span class="p">,</span> <span class="s1">'1'</span><span class="p">)</span>
</pre></div>
<p>Some sample images. Basically, I expect the fractal dimension of the Canadian
coastline to be higher than that of, say, a square.</p>
<div class="highlight"><pre><span></span><span class="n">texas</span><span class="o">=</span><span class="n">bw</span><span class="p">(</span><span class="n">Image</span><span class="o">.</span><span class="n">open</span><span class="p">(</span><span class="s1">'./images/texas.gif'</span><span class="p">))</span>
<span class="n">tree</span><span class="o">=</span><span class="n">bw</span><span class="p">(</span><span class="n">Image</span><span class="o">.</span><span class="n">open</span><span class="p">(</span><span class="s1">'./images/tree.jpg'</span><span class="p">))</span>
<span class="n">canada</span><span class="o">=</span><span class="n">bw</span><span class="p">(</span><span class="n">Image</span><span class="o">.</span><span class="n">open</span><span class="p">(</span><span class="s1">'./images/Canada.png'</span><span class="p">))</span>
<span class="n">square</span><span class="o">=</span><span class="n">bw</span><span class="p">(</span><span class="n">Image</span><span class="o">.</span><span class="n">open</span><span class="p">(</span><span class="s1">'./images/square.jpg'</span><span class="p">))</span>
</pre></div>
<p>At various different scales, I want to divide each image up into squares and
then count how many squares have at least one black pixel in them.</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">interesting</span><span class="p">(</span><span class="n">image</span><span class="p">):</span>
<span class="c1">#true if any data is 0, i.e. black</span>
<span class="k">return</span> <span class="mi">0</span> <span class="ow">in</span> <span class="nb">set</span><span class="p">(</span><span class="n">image</span><span class="o">.</span><span class="n">getdata</span><span class="p">())</span>
</pre></div>
<p>This function chops an image up into </p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">interesting_box_count</span><span class="p">(</span><span class="n">image</span><span class="p">,</span> <span class="n">length</span><span class="p">):</span>
<span class="n">width</span><span class="p">,</span><span class="n">height</span><span class="o">=</span><span class="n">image</span><span class="o">.</span><span class="n">size</span>
<span class="n">interesting_count</span><span class="o">=</span><span class="mi">0</span>
<span class="n">box_count</span><span class="o">=</span><span class="mi">0</span>
<span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">int</span><span class="p">(</span><span class="n">width</span><span class="o">/</span><span class="n">length</span><span class="p">)):</span>
<span class="k">for</span> <span class="n">y</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">int</span><span class="p">(</span><span class="n">height</span><span class="o">/</span><span class="n">length</span><span class="p">)):</span>
<span class="n">C</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">*</span><span class="n">length</span><span class="p">,</span><span class="n">y</span><span class="o">*</span><span class="n">length</span><span class="p">,</span><span class="n">length</span><span class="o">*</span><span class="p">(</span><span class="n">x</span><span class="o">+</span><span class="mi">1</span><span class="p">),</span><span class="n">length</span><span class="o">*</span><span class="p">(</span><span class="n">y</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span>
<span class="n">chopped</span> <span class="o">=</span> <span class="n">image</span><span class="o">.</span><span class="n">crop</span><span class="p">(</span><span class="n">C</span><span class="p">)</span>
<span class="n">box_count</span><span class="o">+=</span><span class="mi">1</span>
<span class="k">if</span> <span class="p">(</span><span class="n">interesting</span><span class="p">(</span><span class="n">chopped</span><span class="p">)):</span>
<span class="n">interesting_count</span><span class="o">+=</span><span class="mi">1</span>
<span class="k">assert</span> <span class="n">box_count</span>
<span class="k">assert</span> <span class="n">interesting_count</span>
<span class="k">return</span> <span class="n">interesting_count</span>
</pre></div>
<p>This returns pairs of numbers. One represents the scale, the other the (log) count
of boxes at that scale that have black pixels in them.</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">getcounts</span><span class="p">(</span><span class="n">image</span><span class="p">):</span>
<span class="n">length</span><span class="o">=</span><span class="nb">min</span><span class="p">(</span><span class="n">image</span><span class="o">.</span><span class="n">size</span><span class="p">)</span>
<span class="k">while</span><span class="p">(</span><span class="n">length</span><span class="o">></span><span class="mi">5</span><span class="p">):</span>
<span class="n">interesting</span> <span class="o">=</span> <span class="n">interesting_box_count</span><span class="p">(</span><span class="n">image</span><span class="p">,</span><span class="n">length</span><span class="p">)</span>
<span class="k">yield</span> <span class="n">math</span><span class="o">.</span><span class="n">log</span><span class="p">(</span><span class="mf">1.0</span><span class="o">/</span><span class="n">length</span><span class="p">),</span> <span class="n">math</span><span class="o">.</span><span class="n">log</span><span class="p">(</span><span class="n">interesting</span><span class="p">)</span>
<span class="n">length</span><span class="o">=</span><span class="nb">int</span><span class="p">(</span><span class="n">length</span><span class="o">/</span><span class="mi">2</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">counts</span><span class="p">(</span><span class="n">image</span><span class="p">):</span>
<span class="k">return</span> <span class="n">pandas</span><span class="o">.</span><span class="n">DataFrame</span><span class="p">(</span><span class="n">getcounts</span><span class="p">(</span><span class="n">image</span><span class="p">),</span><span class="n">columns</span><span class="o">=</span><span class="p">[</span><span class="s2">"x"</span><span class="p">,</span><span class="s2">"y"</span><span class="p">])</span>
</pre></div>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">dimension</span><span class="p">(</span><span class="n">image</span><span class="p">):</span>
<span class="n">frame</span><span class="o">=</span><span class="n">counts</span><span class="p">(</span><span class="n">image</span><span class="p">)</span>
<span class="k">return</span> <span class="n">linregress</span><span class="p">(</span><span class="n">frame</span><span class="o">.</span><span class="n">x</span><span class="p">,</span><span class="n">frame</span><span class="o">.</span><span class="n">y</span><span class="p">)</span>
</pre></div>
<p>And finally, armed with lists of pairs, we compute the slope we'd get if we
plotted them against each other.</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">analyse</span><span class="p">(</span><span class="n">image</span><span class="p">):</span>
<span class="n">c</span><span class="o">=</span><span class="n">counts</span><span class="p">(</span><span class="n">image</span><span class="p">)</span>
<span class="k">print</span><span class="p">(</span><span class="s2">"Fractal Dimension:"</span><span class="p">,</span><span class="n">linregress</span><span class="p">(</span><span class="n">c</span><span class="o">.</span><span class="n">x</span><span class="p">,</span><span class="n">c</span><span class="o">.</span><span class="n">y</span><span class="p">)</span><span class="o">.</span><span class="n">slope</span><span class="p">)</span>
</pre></div>
<h3>Results</h3>
<div class="highlight"><pre><span></span><span class="n">square</span>
</pre></div>
<p><img alt="png" src="images/fractal_dimension/output_10_0.png" width="300" height="300"></p>
<div class="highlight"><pre><span></span><span class="n">analyse</span><span class="p">(</span><span class="n">square</span><span class="p">)</span>
</pre></div>
<div class="highlight"><pre><span></span>Fractal Dimension: 1.26420823227
</pre></div>
<div class="highlight"><pre><span></span><span class="n">texas</span>
</pre></div>
<p><img alt="png" src="images/fractal_dimension/output_12_0.png" width="300" height="300"></p>
<div class="highlight"><pre><span></span><span class="n">analyse</span><span class="p">(</span><span class="n">texas</span><span class="p">)</span>
</pre></div>
<div class="highlight"><pre><span></span>Fractal Dimension: 1.45764518178
</pre></div>
<div class="highlight"><pre><span></span><span class="n">canada</span>
</pre></div>
<p><img alt="png" src="images/fractal_dimension/output_14_0.png" width="300" height="300"></p>
<div class="highlight"><pre><span></span><span class="n">analyse</span><span class="p">(</span><span class="n">canada</span><span class="p">)</span>
</pre></div>
<div class="highlight"><pre><span></span>Fractal Dimension: 1.52450994232
</pre></div>
<div class="highlight"><pre><span></span><span class="n">tree</span>
</pre></div>
<p><img alt="png" src="images/fractal_dimension/output_16_0.png" width="300" height="300"></p>
<div class="highlight"><pre><span></span><span class="n">analyse</span><span class="p">(</span><span class="n">tree</span><span class="p">)</span>
</pre></div>
<div class="highlight"><pre><span></span>Fractal Dimension: 1.82487974473
</pre></div>
<p><strong>Which is exactly what we expected.</strong></p>
<p>As K Lars Lohn said in his keynote, it's very rewarding when you try something out in Python and the result actually matches neatly up with the theory!</p>
</div>
</section>
<footer class="footer">
<div class="container">
<div class="content has-text-centered">
<p>
Powered by <a href="http://getpelican.com/">Pelican</a>, <a href="http://python.org">Python</a>,
and <a href="http://bulma.io/">Bulma</a>
</p>
<p class="subtitle is-6">Ubi Caritas et Amor, Deus Ibi Est</p>
</div>
</div>
</footer>
</body>
</html>