<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/using-clustering-to-find-points-in-an-image/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://privefl.github.io/blog/using-clustering-to-find-points-in-an-image/"> Florian Privé</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<section>
<p>In this post, I present my new <a rel="nofollow" href="https://github.com/privefl/img2coord" target="_blank">package {img2coord}</a>. This package can be used to retrieve coordinates from a scatter plot (as an image).</p>
<div>
<pre><code>devtools<span>::</span><span>install_github</span>(<span>&quot;privefl/img2coord&quot;</span>)</code></pre>
</div>
<p>Have you ever made a plot, saved it as a png and moved on? When you come back to it, it is sometimes difficult to read the values from this plot, especially if there is no grid inside the plot.<br>
Making this package was also a good way to practice with clustering.</p>
<div>
<h2>A very simple example</h2>
<div>
<h3>Saving a plot as PNG</h3>
<div>
<pre><code>file &lt;-<span> </span><span>tempfile</span>(<span>fileext =</span> <span>&quot;.png&quot;</span>)
<span>png</span>(file, <span>width =</span> <span>600</span>, <span>height =</span> <span>400</span>)
<span>set.seed</span>(<span>1</span>)
<span>plot</span>(<span>c</span>(<span>0</span>, <span>runif</span>(<span>20</span>), <span>1</span>))
<span>dev.off</span>()</code></pre>
</div>
<pre><code>## png 
##   2</code></pre>
</div>
<div>
<h3>Reading the PNG in R</h3>
<div>
<pre><code>(img &lt;-<span> </span>magick<span>::</span><span>image_read</span>(file))</code></pre>
</div>
<p><img src="https://i2.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-3-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
</div>
<div>
<h3>Get pixel indices from points</h3>
<div>
<pre><code>## grayscale
img_mat &lt;-<span> </span>img2coord<span>:::</span><span>img2mat</span>(img)
<span>dim</span>(img_mat)</code></pre>
</div>
<pre><code>## [1] 400 600</code></pre>
<div>
<pre><code>list.contour &lt;-<span> </span>img2coord<span>:::</span><span>get_contours</span>(img_mat)
img_mat_in &lt;-<span> </span>img2coord<span>:::</span><span>get_inside</span>(img_mat, list.contour)
<span>dim</span>(img_mat_in)</code></pre>
</div>
<pre><code>## [1] 264 507</code></pre>
<div>
<pre><code><span>head</span>(ind &lt;-<span> </span><span>which</span>(img_mat_in <span>></span><span> </span><span>0</span>, <span>arr.ind =</span> <span>TRUE</span>))</code></pre>
</div>
<pre><code>##      row col
## [1,] 256  14
## [2,] 257  14
## [3,] 254  15
## [4,] 255  15
## [5,] 256  15
## [6,] 257  15</code></pre>
</div>
<div>
<h3>Cluster pixel indices</h3>
<div>
<pre><code><span>set.seed</span>(<span>1</span>)
km &lt;-<span> </span><span>kmeans</span>(ind, <span>centers =</span> <span>22</span>)</code></pre>
</div>
<div>
<pre><code><span>library</span>(ggplot2)
myplot &lt;-<span> </span><span>function</span>(points, centers) {
  p &lt;-<span> </span><span>ggplot</span>() <span>+</span><span> </span>
<span> </span><span>geom_tile</span>(<span>aes</span>(col, row), <span>data =</span> <span>as.data.frame</span>(points)) <span>+</span><span> </span>
<span> </span><span>geom_point</span>(<span>aes</span>(col, row), <span>data =</span> <span>as.data.frame</span>(centers), <span>col =</span> <span>&quot;red&quot;</span>) <span>+</span><span> </span>
<span> </span>bigstatsr<span>::</span><span>theme_bigstatsr</span>() <span>+</span><span> </span>
<span> </span><span>coord_equal</span>()
  <span>print</span>(p)
}
<span>myplot</span>(ind, km<span>$</span>centers)</code></pre>
</div>
<p><img src="https://i2.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-8-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<p>Even when using the true number of clusters, <em>kmeans</em> get trapped in a local minimum (this is clearly not the best solution!), depending on the initialisation of centers. One possible solution would be to use many initialisations; let’s try that.</p>
<div>
<pre><code><span>set.seed</span>(<span>1</span>)
km &lt;-<span> </span><span>kmeans</span>(ind, <span>centers =</span> <span>22</span>, <span>nstart =</span> <span>100</span>, <span>iter.max =</span> <span>100</span>)</code></pre>
</div>
<pre><code>## Warning: did not converge in 100 iterations

## Warning: did not converge in 100 iterations</code></pre>
<div>
<pre><code><span>myplot</span>(ind, km<span>$</span>centers)</code></pre>
</div>
<p><img src="https://i2.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-9-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<p>It is better but not optimal.</p>
</div>
<div>
<h3>Using hclust to get centers</h3>
<div>
<pre><code>get_centers &lt;-<span> </span><span>function</span>(points, clusters) {
  <span>do.call</span>(<span>&quot;rbind&quot;</span>, <span>by</span>(points, clusters, colMeans, <span>simplify =</span> <span>FALSE</span>))
}

d &lt;-<span> </span><span>dist</span>(ind)
hc &lt;-<span> </span><span>hclust</span>(d)
centers &lt;-<span> </span><span>get_centers</span>(ind, <span>cutree</span>(hc, <span>k =</span> <span>22</span>))
<span>myplot</span>(ind, centers)</code></pre>
</div>
<p><img src="https://i2.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-10-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<p><code>hclust()</code> works well for this example.</p>
</div>
<div>
<h3>Get the number of clusters</h3>
<p>What if we don’t know the number of clusters (representing the initial points)? A statistic that could help us determine the number of clusters to use is the silhouette.</p>
<div>
<pre><code>K_seq &lt;-<span> </span><span>seq</span>(<span>10</span>, <span>30</span>)
stat &lt;-<span> </span><span>sapply</span>(K_seq, <span>function</span>(k) {
  <span>mean</span>(cluster<span>::</span><span>silhouette</span>(<span>cutree</span>(hc, k), d)[, <span>3</span>])
})
<span>plot</span>(K_seq, stat, <span>pch =</span> <span>20</span>); <span>abline</span>(<span>v =</span> <span>22</span>, <span>lty =</span> <span>3</span>)</code></pre>
</div>
<p><img src="https://i1.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-11-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
</div>
</div>
<div>
<h2>A less simple example</h2>
<div>
<pre><code>file &lt;-<span> </span><span>tempfile</span>(<span>fileext =</span> <span>&quot;.png&quot;</span>)
<span>png</span>(file, <span>width =</span> <span>600</span>, <span>height =</span> <span>400</span>)
<span>set.seed</span>(<span>1</span>)
y &lt;-<span> </span><span>c</span>(<span>0</span>, <span>runif</span>(<span>100</span>), <span>1</span>)
<span>plot</span>(y, <span>cex =</span> <span>runif</span>(<span>102</span>, <span>min =</span> <span>0.5</span>, <span>max =</span> <span>1.5</span>))
<span>dev.off</span>()</code></pre>
</div>
<pre><code>## png 
##   2</code></pre>
<div>
<pre><code>(img &lt;-<span> </span>magick<span>::</span><span>image_read</span>(file))</code></pre>
</div>
<p><img src="https://i1.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-13-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<div>
<pre><code>img_mat &lt;-<span> </span>img2coord<span>:::</span><span>img2mat</span>(img)
list.contour &lt;-<span> </span>img2coord<span>:::</span><span>get_contours</span>(img_mat)
img_mat_in &lt;-<span> </span>img2coord<span>:::</span><span>get_inside</span>(img_mat, list.contour)
ind &lt;-<span> </span><span>which</span>(img_mat_in <span>></span><span> </span><span>0</span>, <span>arr.ind =</span> <span>TRUE</span>)</code></pre>
</div>
<div>
<pre><code>hc &lt;-<span> </span>flashClust<span>::</span><span>hclust</span>(d &lt;-<span> </span><span>dist</span>(ind))
K_seq &lt;-<span> </span><span>seq</span>(<span>50</span>, <span>150</span>)
stat &lt;-<span> </span><span>sapply</span>(K_seq, <span>function</span>(k) {
  <span>mean</span>(cluster<span>::</span><span>silhouette</span>(<span>cutree</span>(hc, k), d)[, <span>3</span>])
})
<span>plot</span>(K_seq, stat, <span>pch =</span> <span>20</span>); <span>abline</span>(<span>v =</span> <span>102</span>, <span>lty =</span> <span>3</span>)</code></pre>
</div>
<p><img src="https://i0.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-15-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<div>
<pre><code>(K_opt &lt;-<span> </span>K_seq[<span>which.max</span>(stat)])</code></pre>
</div>
<pre><code>## [1] 85</code></pre>
<div>
<pre><code>centers &lt;-<span> </span><span>get_centers</span>(ind, <span>cutree</span>(hc, <span>k =</span> K_opt))
<span>myplot</span>(ind, centers)</code></pre>
</div>
<p><img src="https://i1.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-16-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<p>The silhouette statistic is giving a good yet not optimal solution in this situation. Using the true number of points, we would get:</p>
<div>
<pre><code>centers &lt;-<span> </span><span>get_centers</span>(ind, <span>cutree</span>(hc, <span>k =</span> <span>102</span>))
<span>myplot</span>(ind, centers)</code></pre>
</div>
<p><img src="https://i1.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-17-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<p>If someone has a better statistic to (automatically) find the number of clusters, please share it and I’ll update this post.</p>
</div>
<div>
<h2>Putting everything together as a package</h2>
<p>Finally, after you get the center of all points (pixel clusters), you can interpolate the values based on the values of axe ticks.</p>
<div>
<pre><code>coord &lt;-<span> </span>img2coord<span>::</span><span>get_coord</span>(
  file, 
  <span>x_ticks =</span> <span>seq</span>(<span>0</span>, <span>100</span>, <span>20</span>),
  <span>y_ticks =</span> <span>seq</span>(<span>0</span>, <span>1</span>, <span>0.2</span>),
  <span>K_min =</span> <span>50</span>, <span>K_max =</span> <span>150</span>
) </code></pre>
</div>
<p><img src="https://i2.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-18-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<p>This works better here because I combined the silhouette statistic with a gini coefficient (measure of dispersion) of the number of pixels in each cluster (assuming that they should have approximately the same number). Let’s have a look at the combined statistic:</p>
<div>
<pre><code>stat &lt;-<span> </span><span>attr</span>(coord, <span>&quot;stat&quot;</span>)
<span>plot</span>(<span>names</span>(stat), stat, <span>pch =</span> <span>20</span>); <span>abline</span>(<span>v =</span> <span>102</span>, <span>lty =</span> <span>3</span>) </code></pre>
</div>
<p><img src="https://i1.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-19-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<p>If you don’t get the right number of clusters the first time, you can use the plot generated by <code>img2coord::get_coord()</code> to adjust <code>K</code>.</p>
<div>
<pre><code>coord &lt;-<span> </span>img2coord<span>::</span><span>get_coord</span>(
  file, 
  <span>x_ticks =</span> <span>seq</span>(<span>0</span>, <span>100</span>, <span>20</span>),
  <span>y_ticks =</span> <span>seq</span>(<span>0</span>, <span>1</span>, <span>0.2</span>),
  <span>K =</span> <span>102</span>  ## 99 + 3
) </code></pre>
</div>
<p><img src="https://i1.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-20-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<p>Let’s verify the coordinates we get:</p>
<div>
<pre><code><span>round</span>(coord<span>$</span>x, <span>2</span>)</code></pre>
</div>
<pre><code>##   [1]   1.00   2.01   3.01   4.00   4.99   6.01   7.00   8.00   9.01  10.01
##  [11]  10.98  11.99  12.99  14.01  15.00  15.98  17.01  18.00  18.98  20.00
##  [21]  20.99  22.00  23.00  23.99  24.98  26.00  26.99  28.01  29.00  29.98
##  [31]  31.01  31.99  33.02  34.00  35.02  35.98  37.00  38.01  38.99  40.00
##  [41]  40.99  41.99  42.99  44.01  44.97  45.98  47.01  48.00  49.00  50.00
##  [51]  51.01  51.98  52.99  53.99  55.00  56.00  57.01  58.01  59.00  60.02
##  [61]  61.00  62.00  62.98  64.01  64.99  65.98  67.00  68.01  68.98  70.00
##  [71]  70.98  72.00  73.00  74.01  75.00  76.01  77.00  78.00  79.02  79.98
##  [81]  81.00  82.01  82.98  84.00  85.01  85.99  87.01  87.98  88.99  89.99
##  [91]  90.98  92.00  93.00  94.01  95.00  95.89  96.87  97.99  99.00 100.00
## [101] 101.01 101.99</code></pre>
<div>
<pre><code><span>plot</span>(coord<span>$</span>y, y, <span>pch =</span> <span>20</span>); <span>abline</span>(<span>0</span>, <span>1</span>, <span>col =</span> <span>&quot;red&quot;</span>)</code></pre>
</div>
<p><img src="https://i0.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-21-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
</div>
<div>
<h2>Handling large images</h2>
<div>
<pre><code>url &lt;-<span> &quot;https://goo.gl/K6Y7D1&quot;</span>
<span>library</span>(img2coord)
(img &lt;-<span> </span><span>img_read</span>(url))</code></pre>
</div>
<p><img src="https://i0.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-22-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<div>
<pre><code><span>get_coord</span>(img, <span>seq</span>(<span>0</span>, <span>20</span>, <span>5</span>), <span>seq</span>(<span>94</span>, <span>102</span>, <span>2</span>), <span>K_min =</span> <span>40</span>, <span>K_max =</span> <span>80</span>)</code></pre>
</div>
<pre><code>## Error: Detected more than 10000 pixels associated with points (21358).
##   Make sure you have a white background with no grid (only points).
##   You can change 'max_pixels', but it could become time/memory consuming.
##   You can also downsize the image using `img_scale()`.</code></pre>
<p>The green points are spanning 21,358 pixels, which could be a lot to process, depending on your computer. To solve this problem, you can do:</p>
<div>
<pre><code>img <span>%>%</span>
<span> </span><span>img_scale</span>(<span>0.4</span>) <span>%>%</span>
<span> </span><span>get_coord</span>(<span>seq</span>(<span>0</span>, <span>20</span>, <span>5</span>), <span>seq</span>(<span>94</span>, <span>102</span>, <span>2</span>), <span>K_min =</span> <span>40</span>, <span>K_max =</span> <span>80</span>)</code></pre>
</div>
<p><img src="https://i0.wp.com/privefl.github.io/blog/knitr_files/post-cluster-points_files/figure-html/unnamed-chunk-24-1.png?w=80%25&ssl=1" data-recalc-dims="1"></p>
<pre><code>## $x
##  [1] -0.0005401687  0.3343468897  0.6664667098  0.9992303467  1.3337481120
##  [6]  1.6671560578  1.9997172265  2.3332269701  2.6674887594  2.9991939098
## [11]  3.3326859175  3.6672015650  4.0000566377  4.3329094030  4.6674459579
## [16]  5.0009192485  5.3326185095  5.6478368286  6.0464367945  6.3329501844
## [21]  6.6663573828  6.9839799351  7.3513525635  7.6674682785  8.0006621331
## [26]  8.3329974666  8.6657575234  8.9999189758  9.3339407034  9.6666009658
## [31] 10.0001231324 10.3173252500 10.6778169496 10.9989528978 11.3335964907
## [36] 11.6665738876 11.9994145980 12.3336165187 12.6676553366 12.9992455320
## [41] 13.3331964821 13.6668686496 13.9813979399 14.3425396058 14.6672323938
## [46] 15.0002253318 15.3330976683 15.6669750015 16.0007098735 16.3322818494
## [51] 16.6663301257 17.0005035442 17.3333809139 17.6663416006 18.0009680691
## [56] 18.3172429708 18.6798897677 18.9998067488 19.3333374006 19.6570288544
## [61] 20.0116006657
## 
## $y
##  [1] 103.18007 101.68089 102.91175 101.28109 100.89144 100.36108  98.59931
##  [8]  99.06933  99.90900  98.61988 100.39017  96.87960 100.38054  97.52969
## [15] 101.77948  98.63014  99.10885  98.62457  98.58221  99.06001  99.97088
## [22]  99.09976  98.96014  98.68939  99.77109  98.78963  95.94976  97.51865
## [29]  97.07733  96.58967  98.21105  98.69922  98.53481  97.74167  97.24962
## [36]  97.65023  98.70168  99.77109  97.02095  94.91963  97.65023  96.46068
## [43]  95.23798  95.39595  94.64729  93.14815  95.35968  95.04774  95.82991
## [50]  94.43923  94.96829  96.84944  93.94962  93.35852  97.42928  94.07914
## [57]  94.23708  97.51029  95.68894  94.35497  94.16229
## 
## attr(,&quot;stat&quot;)
##        40        41        42        43        44        45        46 
##  1.991872  2.074327  2.140775  2.270267  2.341965  2.529008  2.758398 
##        47        48        49        50        51        52        53 
##  2.920247  3.119059  3.244979  3.377485  3.715905  4.083564  4.563417 
##        54        55        56        57        58        59        60 
##  5.104999  5.841044  6.441349  6.551265  7.246189  8.165916  8.842711 
##        61        62        63        64        65        66        67 
## 10.167292  8.357433  6.887889  5.708635  4.889674  4.274374  3.788661 
##        68        69        70        71        72        73        74 
##  3.384619  3.082882  2.836479  2.630589  2.451460  2.292444  2.162840 
##        75        76        77        78        79        80 
##  2.054934  1.947805  1.870104  1.784646  1.701550  1.630990</code></pre>
</div>
<div>
<h2>Conclusion</h2>
<p>We have seen that <code>hclust()</code> was performing better than <code>kmeans()</code> (for this example). For some reason I don’t understand yet, initializing <code>kmeans()</code> with centers from <code>hclust()</code> works even better.</p>
<p>Then, we have seen how to determine the number of clusters. Finally, we have seen that using a particular statistic, specifically designed for this problem, improved the solution.</p>
<p>Of course, this could be improved a lot. For example, this won’t work for plots having a background color or some grid inside. Feel free to bring your ideas. BTW, thanks <a rel="nofollow" href="https://twitter.com/robincura" target="_blank">Robin</a> who brought some nice ideas that improved this package a lot.</p>
<p>Have a look at <a rel="nofollow" href="https://github.com/privefl/img2coord" target="_blank">the GitHub repo</a>.</p>
</div>
</section>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://privefl.github.io/blog/using-clustering-to-find-points-in-an-image/"> Florian Privé</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/UPpJ8v-G1sA" height="1"></a></div>