10
\$\begingroup\$

Children are very good at classifying objects and counting them. Computers seem to have more trouble. This is a simplified version of this problem. Can you write a small program that can classify and count objects in an image?

The problem: Given an image containing one or more circles and rectangles, return 2 integers with the count of circles and count of rectangles.

Rules

  • The input image will be black figures on a white background in any bitmap format you choose.
  • The image width and height will be between 100 and 1000 pixels.
  • Figures will be fully contained within the image.
  • Figures will have 1 pixel line width.
  • Images will not use anti-aliasing. They will be black on white only.
  • Figures may touch, intersect, or be inside another figure.
  • Intersecting figures will have a maximum of 4 common pixels.
  • Circles will have a diameter of 20 pixels or more.
  • Rectangle sides will be 10 or more pixels long.
  • You may not use any built-ins or libraries that recognize shapes, or any other function that makes this challenge trivial.
  • Return or print 2 integers with the counts of circles and rectangles.

Example 1

Example 1

Answer: 3 4

Example 2:

enter image description here

Answer: 4 13

This is a code golf challenge, so the shortest program or function in each language will win.

\$\endgroup\$
  • \$\begingroup\$ I can already tell, counting the rectangle will be about counting corners.Circles will be a lot harder though. \$\endgroup\$ – Bálint Apr 30 '16 at 18:15
3
\$\begingroup\$

PHP – 355 bytes

The byte count doesn't include '<image-url>'.

<?php
m('<image-url>');function m($f){$i=imagecreatefrompng($f);$r=f($i,17);$c=f($i,9);echo($c-$r).' '.$r."\n";}function f($i,$k){$w=imagesx($i);$h=imagesy($i);$r=0;for($y=0;$y<$h;$y++)for($x=0;$x<$w;$x++)if(!imagecolorat($i,$x,$y))$r+=g($i,$x,$y,$w,$k);return$r;}function g($i,&$x,$y,$w,$k){$l=$x;while(!imagecolorat($i,$x,$y)&&$x<$w)$x++;return($x-$l>$k)?1/2:0;}

In the two test cases, the URLs I used are http://i.stack.imgur.com/qnIFk.png and http://i.stack.imgur.com/HV9k3.png.

Counts horizontal lines and divides by two to get the number of shapes. Relies on the observation that circles have shorter horizontal segments and rectangles have longer horizontal segments.

Admitted hack, not guaranteed to work for anything other than the test cases!

I tried rotating the images by ± 45° and detecting for horizontal lines. This would be equivalent to checking for diagonal lines and would pick up the circles better, but I couldn't find an interpolation algorithm which left clean enough edges to work with. For example, they might smudge a line into two rows of pixels and mess up the count.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.