title: Detect black dots from color background
body: <h2>My short question</h2>
  
  <p>How to detect the black dots in the following images? (I paste only one test image to make the question look compact. More images can be found <a href="https://www.dropbox.com/sh/y1nwwsy0o96bkyf/AADq8iMo1YJ2XJbgMkSAlmIfa" rel="nofollow noreferrer">→here←</a>).</p>
  
  <p><img src="https://i.stack.imgur.com/6abIc.jpg" alt="enter image description here"></p>
  
  <h2>My long question</h2>
  
  <p>As shown above, the background color is roughly blue, and the dots color is "black". If pick one black pixel and measure its color in RGB, the value can be <img src="https://i.stack.imgur.com/kPTwy.png" alt="enter image description here"> (0, 44, 65) or <img src="https://i.stack.imgur.com/tqUzJ.png" alt="enter image description here"> (14, 69, 89).... Therefore, we cannot set a range to tell the pixel is part of the black dot or the background.</p>
  
  <p>I test 10 images of different colors, but I hope I can find a method to detect the black dots from more complicated background which may be made up of three or more colors, as long as human eyes can identify the black dots easily. Some extremely small or blur dots can be omitted.</p>
  
  <h2>Previous work</h2>
  
  <p>Last month, I have asked <a href="https://stackoverflow.com/questions/23364703/extract-black-objects-from-color-background">a similar question</a> at stackoverflow, but have not got a perfect solution, some excellent answers though. Find more details about my work if you are interested.</p>
  
  <p>Here are the methods I have tried:</p>
  
  <ol>
  <li><p><strong>Converting to grayscale or the brightness of image.</strong> The difficulty is that I can not find an adaptive threshold to do binarization. Obviously, turning a color image to grayscale or using the brightness (HSV) will lose much useful information. <a href="http://en.wikipedia.org/wiki/Otsu%27s_method" rel="nofollow noreferrer">Otsu algorithm</a> which calculates adaptive threshold can not work either.</p></li>
  <li><p><strong>Calculating RGB histogram</strong>. In my last question, <em>natan</em>'s method is to estimate the black color by histogram. It is time-saving, but the adaptive threshold is also a problem.</p></li>
  <li><p><strong>Clustering</strong>. I have tried <a href="http://en.wikipedia.org/wiki/K-means_clustering" rel="nofollow noreferrer">k-means clustering</a> and found it quite effective for the background that only has one color. The shortage (see my own answer) is I need to set the number of clustering center in advance but I don't know how the background will be. What's more, it is too <strong>slow</strong>! My application is for real time capturing on iPhone and now it can process 7~8 frames per second using k-means (20 FPS is good I think).</p></li>
  </ol>
  
  <h2>Summary</h2>
  
  <p>I think not only similar colors but also adjacent pixels should be "clustered" or "merged" in order to extract the black dots. Please guide me a proper way to solve my problem. Any advice or algorithm will be appreciated. There is no free lunch but I hope a better trade-off between cost and accuracy.</p>