86
\$\begingroup\$

Consider these 10 images of various amounts of uncooked grains of white rice.
THESE ARE ONLY THUMBNAILS. Click an image to view it at full size.

A: A B: B C: C D: D E: E

F: F G: G H: H I: I J: J

Grain Counts: A: 3, B: 5, C: 12, D: 25, E: 50, F: 83, G: 120, H:150, I: 151, J: 200

Notice that...

  • The grains may touch each other but they never overlap. The layout of grains is never more than one grain high.
  • The images have different dimensions but the scale of the rice in all of them is consistent because the camera and background were stationary.
  • The grains never go out of bounds or touch the image boundaries.
  • The background is always the same consistent shade of yellowish-white.
  • Small and large grains are counted alike as one grain each.

These 5 points are guarantees for all images of this sort.

Challenge

Write a program that takes in such images and, as accurately as possible, counts the number of grains of rice.

Your program should take the filename of the image and print the number of grains it calculates. Your program must work for at least one of these image file formats: JPEG, Bitmap, PNG, GIF, TIFF (right now the images are all JPEGs).

You may use image processing and computer vision libraries.

You may not hardcode the outputs of the 10 example images. Your algorithm should be applicable to all similar rice-grain images. It should be able to run in less than 5 minutes on a decent modern computer if the image area is less than 2000*2000 pixels and there are fewer than 300 grains of rice.

Scoring

For each of the 10 images take the absolute value of the actual number of grains minus the number of grains your program predicts. Sum these absolute values to get your score. The lowest score wins. A score of 0 is perfect.

In case of ties the highest voted answer wins. I may test your program on additional images to verify its validity and accuracy.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Surely someone has to try scikit-learn! \$\endgroup\$
    – user9206
    Commented Nov 4, 2014 at 13:50
  • \$\begingroup\$ Great contest! :) Btw - could tell us something about end date of this challenge? \$\endgroup\$
    – cyriel
    Commented Nov 5, 2014 at 3:58
  • 1
    \$\begingroup\$ @Lembik Down to 7 :) \$\endgroup\$ Commented Nov 5, 2014 at 15:09
  • 6
    \$\begingroup\$ One day, a rice scientist is going to come along and be head over heels happy that this question exists. \$\endgroup\$
    – Etheryte
    Commented Nov 5, 2014 at 17:19
  • 2
    \$\begingroup\$ @Nit Just tell them ncbi.nlm.nih.gov/pmc/articles/PMC3510117 :) \$\endgroup\$ Commented Nov 5, 2014 at 17:27

9 Answers 9

57
\$\begingroup\$

Python, Score: 24 16

This solution, like Falko's one, is based on measuring the "foreground" area and dividing it by the average grain area.

In fact, what this program tries to detect is the background, not so much as the foreground. Using the fact that rice grains never touch the image boundary, the program starts by flood-filling white at the top-left corner. The flood-fill algorithm paints adjacent pixels if the difference between theirs and the current pixel's brightness is within a certain threshold, thus adjusting to gradual change in the background color. At the end of this stage, the image might look something like this:

Figure 1

As you can see, it does a pretty good job at detecting the background, but it leaves out any areas that are "trapped" between the grains. We handle these areas by estimating the background brightness at each pixel and painting all equal-or-brighter pixels. This estimation works like so: during the flood-fill stage, we calculate the average background brightness for each row and each column. The estimated background brightness at each pixel is the average of the row and column brightness at that pixel. This produces something like this:

Figure 2

EDIT: Finally, the area of each continuous foreground (i.e. non-white) region is divided by the average, precalculated, grain area, giving us an estimate of the grain count in the said region. The sum of these quantities is the result. Initially, we did the same thing for the entire foreground area as a whole, but this approach is, literally, more fine-grained.


from sys import argv; from PIL import Image

# Init
I = Image.open(argv[1]); W, H = I.size; A = W * H
D = [sum(c) for c in I.getdata()]
Bh = [0] * H; Ch = [0] * H
Bv = [0] * W; Cv = [0] * W

# Flood-fill
Background = 3 * 255 + 1; S = [0]
while S:
    i = S.pop(); c = D[i]
    if c != Background:
        D[i] = Background
        Bh[i / W] += c; Ch[i / W] += 1
        Bv[i % W] += c; Cv[i % W] += 1
        S += [(i + o) % A for o in [1, -1, W, -W] if abs(D[(i + o) % A] - c) < 10]

# Eliminate "trapped" areas
for i in xrange(H): Bh[i] /= float(max(Ch[i], 1))
for i in xrange(W): Bv[i] /= float(max(Cv[i], 1))
for i in xrange(A):
    a = (Bh[i / W] + Bv[i % W]) / 2
    if D[i] >= a: D[i] = Background

# Estimate grain count
Foreground = -1; avg_grain_area = 3038.38; grain_count = 0
for i in xrange(A):
    if Foreground < D[i] < Background:
        S = [i]; area = 0
        while S:
            j = S.pop() % A
            if Foreground < D[j] < Background:
                D[j] = Foreground; area += 1
                S += [j - 1, j + 1, j - W, j + W]
        grain_count += int(round(area / avg_grain_area))

# Output
print grain_count

Takes the input filename through the comand line.

Results

      Actual  Estimate  Abs. Error
A         3         3           0
B         5         5           0
C        12        12           0
D        25        25           0
E        50        48           2
F        83        83           0
G       120       116           4
H       150       145           5
I       151       156           5
J       200       200           0
                        ----------
                Total:         16

A B C D E

F G H I J

\$\endgroup\$
9
  • 2
    \$\begingroup\$ This is a really clever solution, nice work! \$\endgroup\$ Commented Nov 2, 2014 at 20:51
  • 1
    \$\begingroup\$ where does avg_grain_area = 3038.38; come from? \$\endgroup\$
    – njzk2
    Commented Nov 3, 2014 at 16:26
  • 2
    \$\begingroup\$ doesn't that count as hardcoding the result? \$\endgroup\$
    – njzk2
    Commented Nov 3, 2014 at 16:58
  • 5
    \$\begingroup\$ @njzk2 No. Given the rule The images have different dimensions but the scale of the rice in all of them is consistent because the camera and background were stationary. This is merely a value that represents that rule. The result, however, changes according to the input. If you change the rule, then this value will change, but the result will be the same - based on the input. \$\endgroup\$
    – Adam Davis
    Commented Nov 3, 2014 at 19:57
  • 6
    \$\begingroup\$ I'm fine with the average area thing. Grain area is (roughly) constant across images. \$\endgroup\$ Commented Nov 3, 2014 at 23:27
31
\$\begingroup\$

Python + OpenCV : Score 27

Horizontal line scanning

Idea : scan the image, one row at a time. For each line, count the number rice grains encountered (by checking if pixel turns black to white or the opposite). If number of grains for the line increase (compared to previous line), it means we encountered a new grain. If that number decrease, it means we passed over a grain. In this case, add +1 to the total result.

enter image description here

Number in red = rice grains encountered for that line
Number in gray = total amount of grains encountered (what we are looking for)

Because of the way algorithm works, it is important to have a clean, b/w image. Lot of noise produce bad results. First main background is cleaned using floodfill (solution similar to Ell answer) then threshold is applied to produce black and white result.

enter image description here

It is far from perfect, but it produce good results regarding simplicity. There is probably many way to improve it (by providing better b/w image, scanning in other directions (eg : vertical, diagonal) taking the average etc...)

import cv2
import numpy
import sys

filename = sys.argv[1]
I = cv2.imread(filename, 0)
h,w = I.shape[:2]
diff = (3,3,3)
mask = numpy.zeros((h+2,w+2),numpy.uint8)
cv2.floodFill(I,mask,(0,0), (255,255,255),diff,diff)
T,I = cv2.threshold(I,180,255,cv2.THRESH_BINARY)
I = cv2.medianBlur(I, 7)

totalrice = 0
oldlinecount = 0
for y in range(0, h):
    oldc = 0
    linecount = 0
    start = 0   
    for x in range(0, w):
        c = I[y,x] < 128;
        if c == 1 and oldc == 0:
            start = x
        if c == 0 and oldc == 1 and (x - start) > 10:
            linecount += 1
        oldc = c
    if oldlinecount != linecount:
        if linecount < oldlinecount:
            totalrice += oldlinecount - linecount
        oldlinecount = linecount
print totalrice

The errors per image : 0, 0, 0, 3, 0, 12, 4, 0, 7, 1

\$\endgroup\$
25
\$\begingroup\$

Mathematica, score: 7

i = {"https://i.sstatic.net/8T6W2.jpg",  "https://i.sstatic.net/pgWt1.jpg", 
     "https://i.sstatic.net/M0K5w.jpg",  "https://i.sstatic.net/eUFNo.jpg", 
     "https://i.sstatic.net/2TFdi.jpg",  "https://i.sstatic.net/wX48v.jpg", 
     "https://i.sstatic.net/eXCGt.jpg",  "https://i.sstatic.net/9na4J.jpg",
     "https://i.sstatic.net/UMP9V.jpg",  "https://i.sstatic.net/nP3Hr.jpg"};

im = Import /@ i;

I think the functions' names are descriptive enough:

getSatHSVChannelAndBinarize[i_Image]             := Binarize@ColorSeparate[i, "HSB"][[2]]
removeSmallNoise[i_Image]                        := DeleteSmallComponents[i, 100]
fillSmallHoles[i_Image]                          := Closing[i, 1]
getMorphologicalComponentsAreas[i_Image]         := ComponentMeasurements[i, "Area"][[All, 2]]
roundAreaSizeToGrainCount[areaSize_, grainSize_] := Round[areaSize/grainSize]

Processing all the pictures at once:

counts = Plus @@@
  (roundAreaSizeToGrainCount[#, 2900] & /@
      (getMorphologicalComponentsAreas@
        fillSmallHoles@
         removeSmallNoise@
          getSatHSVChannelAndBinarize@#) & /@ im)

(* Output {3, 5, 12, 25, 49, 83, 118, 149, 152, 202} *)

The score is:

counts - {3, 5, 12, 25, 50, 83, 120, 150, 151, 200} // Abs // Total
(* 7 *)

Here you can see the score sensitivity wrt the grain size used:

Mathematica graphics

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Much clearer, thanks! \$\endgroup\$ Commented Nov 4, 2014 at 0:51
  • \$\begingroup\$ Can this exact procedure be copied in python or is there something special Mathematica is doing here that python libraries can't do? \$\endgroup\$
    – user9206
    Commented Nov 4, 2014 at 18:53
  • \$\begingroup\$ @Lembik No idea. No python here. Sorry. (However, I doubt the exact same algorithms for EdgeDetect[], DeleteSmallComponents[] and Dilation[] are implemented elsewhere) \$\endgroup\$ Commented Nov 4, 2014 at 18:56
25
\$\begingroup\$

Python + OpenCV: Score 84

Here is a first naive attempt. It applies an adaptive threshold with manually tuned parameters, closes some holes with subsequent erosion and dilution and derives the number of grains from the foreground area.

import cv2
import numpy as np

filename = raw_input()

I = cv2.imread(filename, 0)
I = cv2.medianBlur(I, 3)
bw = cv2.adaptiveThreshold(I, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 101, 1)

kernel = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (17, 17))
bw = cv2.dilate(cv2.erode(bw, kernel), kernel)

print np.round_(np.sum(bw == 0) / 3015.0)

Here you can see the intermediate binary images (black is foreground):

enter image description here

The errors per image are 0, 0, 2, 2, 4, 0, 27, 42, 0 and 7 grains.

\$\endgroup\$
23
+50
\$\begingroup\$

C# + OpenCvSharp, Score: 2

This is my second attempt. It is quite different from my first attempt, which is a lot simpler, so I am posting it as a separate solution.

The basic idea is to identify and label each individual grain by an iterative ellipse fit. Then remove the pixels for this grain from the source, and try to find the next grain, until every pixel has been labeled.

This is not the most pretty solution. It is a giant hog with 600 lines of code. It needs 1.5 minutes for the biggest image. And I really apologize for the messy code.

There are so many parameters and ways to thinker in this thing that I am quite afraid of overfitting my program for the 10 sample images. The final score of 2 is almost definitely a case of overfitting: I have two parameters, average grain size in pixel, and minimum ratio of pixel / elipse_area, and at the end I simply exhausted all combinations of these two parameters until I got the lowest score. I am not sure whether this is all that kosher with the rules of this challenge.

average_grain_size_in_pixel = 2530
pixel / elipse_area >= 0.73

But even without these overfitting clutches, the results are quite nice. Without a fixed grain size or pixel-ratio, simply by estimating the average grain size from the training images, the score is still 27.

And I get as the output not only the number, but the actual position, orientation and shape of each grain. there are a small number of mislabeled grains, but overall most of the labels accurately match the real grains:

AA BB CC DD EE

FF GG HH II JJ

(click on each image for the full-sized version)

After this labeling step, my program looks at each individual grain, and estimates based on the number of pixels and the pixel/ellipse-area ratio, whether this is

  • a single grain (+1)
  • multiple grains mislabeled as one (+X)
  • a blob too small to be a grain (+0)

The error scores for each image are A:0; B:0; C:0; D:0; E:2; F:0; G:0 ; H:0; I:0, J:0

However the actual error is probably a little higher. Some errors within the same image cancel each other out. Image H in particular has some badly mislabeled grains, whereas in image E the labels are mostly correct

The concept is a little contrived:

  • First the foreground is separated via otsu-thresholding on the saturation channel (see my previous answer for details)

  • repeat until no more pixels left:

    • select the largest blob
    • choose 10 random edge pixels on this blob as starting positions for a grain

    • for each starting point

      • assume a grain with height and width 10 pixels at this position.

      • repeat until convergence

        • go radially outwards from this point, at different angles, until you encounter an edge pixel (white-to-black)

        • the found pixels should hopefully be the edge pixels of a single grain. Try to separate inliers from outliers, by discarding pixels that are a more distant from the assumed ellipse than the others

        • repeatedly try to fit an ellipse through a subset of the inliers, keep the best ellipse (RANSACK)

        • update the grain position, orientation, width and height with the found elipse

        • if the grain position does not change significantly, stop

    • among the 10 fitted grains, choose the best grain according to shape, number of edge pixels. Discard the others

    • remove all pixels for this grain from the source image, then repeat

    • finally, go through the list of found grains, and count each grain either as 1 grain, 0 grains (too small) or 2 grains (too big)

One of my main problems was that I did not want to implement a full ellipse-point distance metric, since calculating that in itself is a complicated iterative process. So I used various workarounds using the OpenCV functions Ellipse2Poly and FitEllipse, and the results are not too pretty.

Apparently i also broke the size limit for codegolf.

An answer is limited to 30000 characters, i am currently at 34000. So I'll have to shorten the code below somewhat.

The full code can be seen at http://pastebin.com/RgM7hMxq

Sorry for this, I was not aware that there was a size limit.

class Program
{
    static void Main(string[] args)
    {

                // Due to size constraints, I removed the inital part of my program that does background separation. For the full source, check the link, or see my previous program.


                // list of recognized grains
                List<Grain> grains = new List<Grain>();

                Random rand = new Random(4); // determined by fair dice throw, guaranteed to be random

                // repeat until we have found all grains (to a maximum of 10000)
                for (int numIterations = 0; numIterations < 10000; numIterations++ )
                {
                    // erode the image of the remaining foreground pixels, only big blobs can be grains
                    foreground.Erode(erodedForeground,null,7);

                    // pick a number of starting points to fit grains
                    List<CvPoint> startPoints = new List<CvPoint>();
                    using (CvMemStorage storage = new CvMemStorage())
                    using (CvContourScanner scanner = new CvContourScanner(erodedForeground, storage, CvContour.SizeOf, ContourRetrieval.List, ContourChain.ApproxNone))
                    {
                        if (!scanner.Any()) break; // no grains left, finished!

                        // search for grains within the biggest blob first (this is arbitrary)
                        var biggestBlob = scanner.OrderByDescending(c => c.Count()).First();

                        // pick 10 random edge pixels
                        for (int i = 0; i < 10; i++)
                        {
                            startPoints.Add(biggestBlob.ElementAt(rand.Next(biggestBlob.Count())).Value);
                        }
                    }

                    // for each starting point, try to fit a grain there
                    ConcurrentBag<Grain> candidates = new ConcurrentBag<Grain>();
                    Parallel.ForEach(startPoints, point =>
                    {
                        Grain candidate = new Grain(point);
                        candidate.Fit(foreground);
                        candidates.Add(candidate);
                    });

                    Grain grain = candidates
                        .OrderByDescending(g=>g.Converged) // we don't want grains where the iterative fit did not finish
                        .ThenBy(g=>g.IsTooSmall) // we don't want tiny grains
                        .ThenByDescending(g => g.CircumferenceRatio) // we want grains that have many edge pixels close to the fitted elipse
                        .ThenBy(g => g.MeanSquaredError)
                        .First(); // we only want the best fit among the 10 candidates

                    // count the number of foreground pixels this grain has
                    grain.CountPixel(foreground);

                    // remove the grain from the foreground
                    grain.Draw(foreground,CvColor.Black);

                    // add the grain to the colection fo found grains
                    grains.Add(grain);
                    grain.Index = grains.Count;

                    // draw the grain for visualisation
                    grain.Draw(display, CvColor.Random());
                    grain.DrawContour(display, CvColor.Random());
                    grain.DrawEllipse(display, CvColor.Random());

                    //display.SaveImage("10-foundGrains.png");
                }

                // throw away really bad grains
                grains = grains.Where(g => g.PixelRatio >= 0.73).ToList();

                // estimate the average grain size, ignoring outliers
                double avgGrainSize =
                    grains.OrderBy(g => g.NumPixel).Skip(grains.Count/10).Take(grains.Count*9/10).Average(g => g.NumPixel);

                //ignore the estimated grain size, use a fixed size
                avgGrainSize = 2530;

                // count the number of grains, using the average grain size
                double numGrains = grains.Sum(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize));

                // get some statistics
                double avgWidth = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) == 1).Average(g => g.Width);
                double avgHeight = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) == 1).Average(g => g.Height);
                double avgPixelRatio = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) == 1).Average(g => g.PixelRatio);

                int numUndersized = grains.Count(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) < 1);
                int numOversized = grains.Count(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) > 1);

                double avgWidthUndersized = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) < 1).Select(g=>g.Width).DefaultIfEmpty(0).Average();
                double avgHeightUndersized = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) < 1).Select(g => g.Height).DefaultIfEmpty(0).Average();
                double avgGrainSizeUndersized = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) < 1).Select(g => g.NumPixel).DefaultIfEmpty(0).Average();
                double avgPixelRatioUndersized = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) < 1).Select(g => g.PixelRatio).DefaultIfEmpty(0).Average();

                double avgWidthOversized = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) > 1).Select(g => g.Width).DefaultIfEmpty(0).Average();
                double avgHeightOversized = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) > 1).Select(g => g.Height).DefaultIfEmpty(0).Average();
                double avgGrainSizeOversized = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) > 1).Select(g => g.NumPixel).DefaultIfEmpty(0).Average();
                double avgPixelRatioOversized = grains.Where(g => Math.Round(g.NumPixel * 1.0 / avgGrainSize) > 1).Select(g => g.PixelRatio).DefaultIfEmpty(0).Average();


                Console.WriteLine("===============================");
                Console.WriteLine("Grains: {0}|{1:0.} of {2} (e{3}), size {4:0.}px, {5:0.}x{6:0.}  {7:0.000}  undersized:{8}  oversized:{9}   {10:0.0} minutes  {11:0.0} s per grain",grains.Count,numGrains,expectedGrains[fileNo],expectedGrains[fileNo]-numGrains,avgGrainSize,avgWidth,avgHeight, avgPixelRatio,numUndersized,numOversized,watch.Elapsed.TotalMinutes, watch.Elapsed.TotalSeconds/grains.Count);



                // draw the description for each grain
                foreach (Grain grain in grains)
                {
                    grain.DrawText(avgGrainSize, display, CvColor.Black);
                }

                display.SaveImage("10-foundGrains.png");
                display.SaveImage("X-" + file + "-foundgrains.png");
            }
        }
    }
}



public class Grain
{
    private const int MIN_WIDTH = 70;
    private const int MAX_WIDTH = 130;
    private const int MIN_HEIGHT = 20;
    private const int MAX_HEIGHT = 35;

    private static CvFont font01 = new CvFont(FontFace.HersheyPlain, 0.5, 1);
    private Random random = new Random(4); // determined by fair dice throw; guaranteed to be random


    /// <summary> center of grain </summary>
    public CvPoint2D32f Position { get; private set; }
    /// <summary> Width of grain (always bigger than height)</summary>
    public float Width { get; private set; }
    /// <summary> Height of grain (always smaller than width)</summary>
    public float Height { get; private set; }

    public float MinorRadius { get { return this.Height / 2; } }
    public float MajorRadius { get { return this.Width / 2; } }
    public double Angle { get; private set; }
    public double AngleRad { get { return this.Angle * Math.PI / 180; } }

    public int Index { get; set; }
    public bool Converged { get; private set; }
    public int NumIterations { get; private set; }
    public double CircumferenceRatio { get; private set; }
    public int NumPixel { get; private set; }
    public List<EllipsePoint> EdgePoints { get; private set; }
    public double MeanSquaredError { get; private set; }
    public double PixelRatio { get { return this.NumPixel / (Math.PI * this.MajorRadius * this.MinorRadius); } }
    public bool IsTooSmall { get { return this.Width < MIN_WIDTH || this.Height < MIN_HEIGHT; } }

    public Grain(CvPoint2D32f position)
    {
        this.Position = position;
        this.Angle = 0;
        this.Width = 10;
        this.Height = 10;
        this.MeanSquaredError = double.MaxValue;
    }

    /// <summary>  fit a single rice grain of elipsoid shape </summary>
    public void Fit(CvMat img)
    {
        // distance between the sampled points on the elipse circumference in degree
        int angularResolution = 1;

        // how many times did the fitted ellipse not change significantly?
        int numConverged = 0;

        // number of iterations for this fit
        int numIterations;

        // repeat until the fitted ellipse does not change anymore, or the maximum number of iterations is reached
        for (numIterations = 0; numIterations < 100 && !this.Converged; numIterations++)
        {
            // points on an ideal ellipse
            CvPoint[] points;
            Cv.Ellipse2Poly(this.Position, new CvSize2D32f(MajorRadius, MinorRadius), Convert.ToInt32(this.Angle), 0, 359, out points,
                            angularResolution);

            // points on the edge of foregroudn to background, that are close to the elipse
            CvPoint?[] edgePoints = new CvPoint?[points.Length];

            // remeber if the previous pixel in a given direction was foreground or background
            bool[] prevPixelWasForeground = new bool[points.Length];

            // when the first edge pixel is found, this value is updated
            double firstEdgePixelOffset = 200;

            // from the center of the elipse towards the outside:
            for (float offset = -this.MajorRadius + 1; offset < firstEdgePixelOffset + 20; offset++)
            {
                // draw an ellipse with the given offset
                Cv.Ellipse2Poly(this.Position, new CvSize2D32f(MajorRadius + offset, MinorRadius + (offset > 0 ? offset : MinorRadius / MajorRadius * offset)), Convert.ToInt32(this.Angle), 0,
                                359, out points, angularResolution);

                // for each angle
                Parallel.For(0, points.Length, i =>
                {
                    if (edgePoints[i].HasValue) return; // edge for this angle already found

                    // check if the current pixel is foreground
                    bool foreground = points[i].X < 0 || points[i].Y < 0 || points[i].X >= img.Cols || points[i].Y >= img.Rows
                                          ? false // pixel outside of image borders is always background
                                          : img.Get2D(points[i].Y, points[i].X).Val0 > 0;


                    if (prevPixelWasForeground[i] && !foreground)
                    {
                        // found edge pixel!
                        edgePoints[i] = points[i];

                        // if this is the first edge pixel we found, remember its offset. the other pixels cannot be too far away, so we can stop searching soon
                        if (offset < firstEdgePixelOffset && offset > 0) firstEdgePixelOffset = offset;
                    }

                    prevPixelWasForeground[i] = foreground;
                });
            }

            // estimate the distance of each found edge pixel from the ideal elipse
            // this is a hack, since the actual equations for estimating point-ellipse distnaces are complicated
            Cv.Ellipse2Poly(this.Position, new CvSize2D32f(MajorRadius, MinorRadius), Convert.ToInt32(this.Angle), 0, 360,
                            out points, angularResolution);
            var pointswithDistance =
                edgePoints.Select((p, i) => p.HasValue ? new EllipsePoint(p.Value, points[i], this.Position) : null)
                          .Where(p => p != null).ToList();

            if (pointswithDistance.Count == 0)
            {
                Console.WriteLine("no points found! should never happen! ");
                break;
            }

            // throw away all outliers that are too far outside the current ellipse
            double medianSignedDistance = pointswithDistance.OrderBy(p => p.SignedDistance).ElementAt(pointswithDistance.Count / 2).SignedDistance;
            var goodPoints = pointswithDistance.Where(p => p.SignedDistance < medianSignedDistance + 15).ToList();

            // do a sort of ransack fit with the inlier points to find a new better ellipse
            CvBox2D bestfit = ellipseRansack(goodPoints);

            // check if the fit has converged
            if (Math.Abs(this.Angle - bestfit.Angle) < 3 && // angle has not changed much (<3°)
                Math.Abs(this.Position.X - bestfit.Center.X) < 3 && // position has not changed much (<3 pixel)
                Math.Abs(this.Position.Y - bestfit.Center.Y) < 3)
            {
                numConverged++;
            }
            else
            {
                numConverged = 0;
            }

            if (numConverged > 2)
            {
                this.Converged = true;
            }

            //Console.WriteLine("Iteration {0}, delta {1:0.000} {2:0.000} {3:0.000}    {4:0.000}-{5:0.000} {6:0.000}-{7:0.000} {8:0.000}-{9:0.000}",
            //  numIterations, Math.Abs(this.Angle - bestfit.Angle), Math.Abs(this.Position.X - bestfit.Center.X), Math.Abs(this.Position.Y - bestfit.Center.Y), this.Angle, bestfit.Angle, this.Position.X, bestfit.Center.X, this.Position.Y, bestfit.Center.Y);

            double msr = goodPoints.Sum(p => p.Distance * p.Distance) / goodPoints.Count;

            // for drawing the polygon, filter the edge points more strongly
            if (goodPoints.Count(p => p.SignedDistance < 5) > goodPoints.Count / 2)
                goodPoints = goodPoints.Where(p => p.SignedDistance < 5).ToList();
            double cutoff = goodPoints.Select(p => p.Distance).OrderBy(d => d).ElementAt(goodPoints.Count * 9 / 10);
            goodPoints = goodPoints.Where(p => p.SignedDistance <= cutoff + 1).ToList();

            int numCertainEdgePoints = goodPoints.Count(p => p.SignedDistance > -2);
            this.CircumferenceRatio = numCertainEdgePoints * 1.0 / points.Count();

            this.Angle = bestfit.Angle;
            this.Position = bestfit.Center;
            this.Width = bestfit.Size.Width;
            this.Height = bestfit.Size.Height;
            this.EdgePoints = goodPoints;
            this.MeanSquaredError = msr;

        }
        this.NumIterations = numIterations;
        //Console.WriteLine("Grain found after {0,3} iterations, size={1,3:0.}x{2,3:0.}   pixel={3,5}    edgePoints={4,3}   msr={5,2:0.00000}", numIterations, this.Width,
        //                        this.Height, this.NumPixel, this.EdgePoints.Count, this.MeanSquaredError);
    }

    /// <summary> a sort of ransakc fit to find the best ellipse for the given points </summary>
    private CvBox2D ellipseRansack(List<EllipsePoint> points)
    {
        using (CvMemStorage storage = new CvMemStorage(0))
        {
            // calculate minimum bounding rectangle
            CvSeq<CvPoint> fullPointSeq = CvSeq<CvPoint>.FromArray(points.Select(p => p.Point), SeqType.EltypePoint, storage);
            var boundingRect = fullPointSeq.MinAreaRect2();

            // the initial candidate is the previously found ellipse
            CvBox2D bestEllipse = new CvBox2D(this.Position, new CvSize2D32f(this.Width, this.Height), (float)this.Angle);
            double bestError = calculateEllipseError(points, bestEllipse);

            Queue<EllipsePoint> permutation = new Queue<EllipsePoint>();
            if (points.Count >= 5) for (int i = -2; i < 20; i++)
                {
                    CvBox2D ellipse;
                    if (i == -2)
                    {
                        // first, try the ellipse described by the boundingg rect
                        ellipse = boundingRect;
                    }
                    else if (i == -1)
                    {
                        // then, try the best-fit ellipsethrough all points
                        ellipse = fullPointSeq.FitEllipse2();
                    }
                    else
                    {
                        // then, repeatedly fit an ellipse through a random sample of points

                        // pick some random points
                        if (permutation.Count < 5) permutation = new Queue<EllipsePoint>(permutation.Concat(points.OrderBy(p => random.Next())));
                        CvSeq<CvPoint> pointSeq = CvSeq<CvPoint>.FromArray(permutation.Take(10).Select(p => p.Point), SeqType.EltypePoint, storage);
                        for (int j = 0; j < pointSeq.Count(); j++) permutation.Dequeue();

                        // fit an ellipse through these points
                        ellipse = pointSeq.FitEllipse2();
                    }

                    // assure that the width is greater than the height
                    ellipse = NormalizeEllipse(ellipse);

                    // if the ellipse is too big for agrain, shrink it
                    ellipse = rightSize(ellipse, points.Where(p => isOnEllipse(p.Point, ellipse, 10, 10)).ToList());

                    // sometimes the ellipse given by FitEllipse2 is totally off
                    if (boundingRect.Center.DistanceTo(ellipse.Center) > Math.Max(boundingRect.Size.Width, boundingRect.Size.Height) * 2)
                    {
                        // ignore this bad fit
                        continue;
                    }

                    // estimate the error
                    double error = calculateEllipseError(points, ellipse);

                    if (error < bestError)
                    {
                        // found a better ellipse!
                        bestError = error;
                        bestEllipse = ellipse;
                    }
                }

            return bestEllipse;
        }
    }

    /// <summary> The proper thing to do would be to use the actual distance of each point to the elipse.
    /// However that formula is complicated, so ...  </summary>
    private double calculateEllipseError(List<EllipsePoint> points, CvBox2D ellipse)
    {
        const double toleranceInner = 5;
        const double toleranceOuter = 10;
        int numWrongPoints = points.Count(p => !isOnEllipse(p.Point, ellipse, toleranceInner, toleranceOuter));
        double ratioWrongPoints = numWrongPoints * 1.0 / points.Count;

        int numTotallyWrongPoints = points.Count(p => !isOnEllipse(p.Point, ellipse, 10, 20));
        double ratioTotallyWrongPoints = numTotallyWrongPoints * 1.0 / points.Count;

        // this pseudo-distance is biased towards deviations on the major axis
        double pseudoDistance = Math.Sqrt(points.Sum(p => Math.Abs(1 - ellipseMetric(p.Point, ellipse))) / points.Count);

        // primarily take the number of points far from the elipse border as an error metric.
        // use pseudo-distance to break ties between elipses with the same number of wrong points
        return ratioWrongPoints * 1000  + ratioTotallyWrongPoints+ pseudoDistance / 1000;
    }


    /// <summary> shrink an ellipse if it is larger than the maximum grain dimensions </summary>
    private static CvBox2D rightSize(CvBox2D ellipse, List<EllipsePoint> points)
    {
        if (ellipse.Size.Width < MAX_WIDTH && ellipse.Size.Height < MAX_HEIGHT) return ellipse;

        // elipse is bigger than the maximum grain size
        // resize it so it fits, while keeping one edge of the bounding rectangle constant

        double desiredWidth = Math.Max(10, Math.Min(MAX_WIDTH, ellipse.Size.Width));
        double desiredHeight = Math.Max(10, Math.Min(MAX_HEIGHT, ellipse.Size.Height));

        CvPoint2D32f average = points.Average();

        // get the corners of the surrounding bounding box
        var corners = ellipse.BoxPoints().ToList();

        // find the corner that is closest to the center of mass of the points
        int i0 = ellipse.BoxPoints().Select((point, index) => new { point, index }).OrderBy(p => p.point.DistanceTo(average)).First().index;
        CvPoint p0 = corners[i0];

        // find the two corners that are neighbouring this one
        CvPoint p1 = corners[(i0 + 1) % 4];
        CvPoint p2 = corners[(i0 + 3) % 4];

        // p1 is the next corner along the major axis (widht), p2 is the next corner along the minor axis (height)
        if (p0.DistanceTo(p1) < p0.DistanceTo(p2))
        {
            CvPoint swap = p1;
            p1 = p2;
            p2 = swap;
        }

        // calculate the three other corners with the desired widht and height

        CvPoint2D32f edge1 = (p1 - p0);
        CvPoint2D32f edge2 = p2 - p0;
        double edge1Length = Math.Max(0.0001, p0.DistanceTo(p1));
        double edge2Length = Math.Max(0.0001, p0.DistanceTo(p2));

        CvPoint2D32f newCenter = (CvPoint2D32f)p0 + edge1 * (desiredWidth / edge1Length) + edge2 * (desiredHeight / edge2Length);

        CvBox2D smallEllipse = new CvBox2D(newCenter, new CvSize2D32f((float)desiredWidth, (float)desiredHeight), ellipse.Angle);

        return smallEllipse;
    }

    /// <summary> assure that the width of the elipse is the major axis, and the height is the minor axis.
    /// Swap widht/height and rotate by 90° otherwise  </summary>
    private static CvBox2D NormalizeEllipse(CvBox2D ellipse)
    {
        if (ellipse.Size.Width < ellipse.Size.Height)
        {
            ellipse = new CvBox2D(ellipse.Center, new CvSize2D32f(ellipse.Size.Height, ellipse.Size.Width), (ellipse.Angle + 90 + 360) % 360);
        }
        return ellipse;
    }

    /// <summary> greater than 1 for points outside ellipse, smaller than 1 for points inside ellipse </summary>
    private static double ellipseMetric(CvPoint p, CvBox2D ellipse)
    {
        double theta = ellipse.Angle * Math.PI / 180;
        double u = Math.Cos(theta) * (p.X - ellipse.Center.X) + Math.Sin(theta) * (p.Y - ellipse.Center.Y);
        double v = -Math.Sin(theta) * (p.X - ellipse.Center.X) + Math.Cos(theta) * (p.Y - ellipse.Center.Y);

        return u * u / (ellipse.Size.Width * ellipse.Size.Width / 4) + v * v / (ellipse.Size.Height * ellipse.Size.Height / 4);
    }

    /// <summary> Is the point on the ellipseBorder, within a certain tolerance </summary>
    private static bool isOnEllipse(CvPoint p, CvBox2D ellipse, double toleranceInner, double toleranceOuter)
    {
        double theta = ellipse.Angle * Math.PI / 180;
        double u = Math.Cos(theta) * (p.X - ellipse.Center.X) + Math.Sin(theta) * (p.Y - ellipse.Center.Y);
        double v = -Math.Sin(theta) * (p.X - ellipse.Center.X) + Math.Cos(theta) * (p.Y - ellipse.Center.Y);

        double innerEllipseMajor = (ellipse.Size.Width - toleranceInner) / 2;
        double innerEllipseMinor = (ellipse.Size.Height - toleranceInner) / 2;
        double outerEllipseMajor = (ellipse.Size.Width + toleranceOuter) / 2;
        double outerEllipseMinor = (ellipse.Size.Height + toleranceOuter) / 2;

        double inside = u * u / (innerEllipseMajor * innerEllipseMajor) + v * v / (innerEllipseMinor * innerEllipseMinor);
        double outside = u * u / (outerEllipseMajor * outerEllipseMajor) + v * v / (outerEllipseMinor * outerEllipseMinor);
        return inside >= 1 && outside <= 1;
    }


    /// <summary> count the number of foreground pixels for this grain </summary>
    public int CountPixel(CvMat img)
    {
        // todo: this is an incredibly inefficient way to count, allocating a new image with the size of the input each time
        using (CvMat mask = new CvMat(img.Rows, img.Cols, MatrixType.U8C1))
        {
            mask.SetZero();
            mask.FillPoly(new CvPoint[][] { this.EdgePoints.Select(p => p.Point).ToArray() }, CvColor.White);
            mask.And(img, mask);
            this.NumPixel = mask.CountNonZero();
        }
        return this.NumPixel;
    }

    /// <summary> draw the recognized shape of the grain </summary>
    public void Draw(CvMat img, CvColor color)
    {
        img.FillPoly(new CvPoint[][] { this.EdgePoints.Select(p => p.Point).ToArray() }, color);
    }

    /// <summary> draw the contours of the grain </summary>
    public void DrawContour(CvMat img, CvColor color)
    {
        img.DrawPolyLine(new CvPoint[][] { this.EdgePoints.Select(p => p.Point).ToArray() }, true, color);
    }

    /// <summary> draw the best-fit ellipse of the grain </summary>
    public void DrawEllipse(CvMat img, CvColor color)
    {
        img.DrawEllipse(this.Position, new CvSize2D32f(this.MajorRadius, this.MinorRadius), this.Angle, 0, 360, color, 1);
    }

    /// <summary> print the grain index and the number of pixels divided by the average grain size</summary>
    public void DrawText(double averageGrainSize, CvMat img, CvColor color)
    {
        img.PutText(String.Format("{0}|{1:0.0}", this.Index, this.NumPixel / averageGrainSize), this.Position + new CvPoint2D32f(-5, 10), font01, color);
    }

}

I am a little embarrassed with this solution because a) I am not sure whether it is within the spirit of this challenge, and b) it is too big for a codegolf answer and lacks the elegance of the other solutions.

On the other hand, I am quite happy with the progress I achieved in labeling the grains, not merely counting them, so there is that.

\$\endgroup\$
6
  • \$\begingroup\$ You know you can reduce that code length by magnitudes by using smaller names and applying some other golfing techniques ;) \$\endgroup\$
    – Optimizer
    Commented Nov 10, 2014 at 20:45
  • \$\begingroup\$ Probably, but I did not want to further obfuscate this solution. It is too obfuscated for my tastes as it is :) \$\endgroup\$
    – HugoRune
    Commented Nov 10, 2014 at 20:48
  • \$\begingroup\$ +1 for the effort and because you are the only one which find a way to display individually each grain. Unfortunately code is a little bloated and rely on lot on hardcoded constants. I would be curious to see how the scanline algorithm i wrote perform on this (on the invidual colored grains). \$\endgroup\$
    – tigrou
    Commented Nov 11, 2014 at 8:19
  • \$\begingroup\$ I really think that this is the right approach for this type of problem(+1 for you), but one thing I wonder, why do you "choose 10 random edge pixels", I would think that you would get better performance if you picked the edge points with the lowest number of nearby edge points(ie parts that stick out), I would think(theoretically) this would eliminate the "easiest" grains first, have you considered this? \$\endgroup\$ Commented Nov 11, 2014 at 23:16
  • \$\begingroup\$ I have thought of it, but not tried it yet. The '10 random starting position' was a late addition, which was easy to add and easy to parallelize. Before that, 'one random starting position' was much better than 'always the top left corner'. The danger of choosing the starting positions with the same strategy each time is that when I remove the best fit, the other 9 will probably be chosen again next time, and over time the worst of those starting positions will stay behind and get chosen again and again. A part that sticks out may just be the remains of an incompletely removed previous grain. \$\endgroup\$
    – HugoRune
    Commented Nov 11, 2014 at 23:35
19
\$\begingroup\$

C++, OpenCV, score: 9

Basic idea of my method is quite simple - try to erase single grains(and "double grains" - 2 (but not more!) grains, close to each other) from image and then count rest using method based on area (like Falko, Ell and belisarius). Using this approach is a bit better than standard "area method", because it is easier to find good averagePixelsPerObject value.

(1st step)First of all we need to use Otsu binarization on S channel of image in HSV. The next step is using dilate operator to improve quality of extracted foreground. Than we need to find contours. Of course some contours are not grains of rice - we need to delete too small contours (with area smaller then averagePixelsPerObject/4. averagePixelsPerObject is 2855 in my situation). Now finally we can start counting grains :) (2nd step) Finding single and double grains is quite simple - just look in contours list for contours with area within specific ranges - if the contour area is in range, delete it from list and add 1 (or 2 if it was "double" grain) to grains counter. (3rd step) The last step is of course dividing area of remaining contours by averagePixelsPerObject value and add result to grains counter.

Images (for image F.jpg) should show this idea better than words:
1st step (without small contours(noise)): 1st step (without small contours(noise))
2nd step - only simple contours: 2nd step - only simple contours
3rd step - remaining contours: 3rd step - remaining contours

Here is the code, it's rather ugly, but should work without any problem. Of course OpenCV is required.

#include "stdafx.h"

#include <cv.hpp>
#include <cxcore.h>
#include <highgui.h>
#include <vector>

using namespace cv;
using namespace std;

//A: 3, B: 5, C: 12, D: 25, E: 50, F: 83, G: 120, H:150, I: 151, J: 200
const int goodResults[] = {3, 5, 12, 25, 50, 83, 120, 150, 151, 200};
const float averagePixelsPerObject = 2855.0;

const int singleObjectPixelsCountMin = 2320;
const int singleObjectPixelsCountMax = 4060;

const int doubleObjectPixelsCountMin = 5000;
const int doubleObjectPixelsCountMax = 8000;

float round(float x)
{
    return x >= 0.0f ? floorf(x + 0.5f) : ceilf(x - 0.5f);
}

Mat processImage(Mat m, int imageIndex, int &error)
{
    int objectsCount = 0;
    Mat output, thresholded;
    cvtColor(m, output, CV_BGR2HSV);
    vector<Mat> channels;
    split(output, channels);
    threshold(channels[1], thresholded, 0, 255, CV_THRESH_OTSU | CV_THRESH_BINARY);
    dilate(thresholded, output, Mat()); //dilate to imporove quality of binary image
    imshow("thresholded", thresholded);
    int nonZero = countNonZero(output); //not realy important - just for tests
    if (imageIndex != -1)
        cout << "non zero: " << nonZero << ", average pixels per object: " << nonZero/goodResults[imageIndex] << endl;
    else
        cout << "non zero: " << nonZero << endl;

    vector<vector<Point>> contours, contoursOnlyBig, contoursWithoutSimpleObjects, contoursSimple;
    findContours(output, contours, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_NONE); //find only external contours
    for (int i=0; i<contours.size(); i++)
        if (contourArea(contours[i]) > averagePixelsPerObject/4.0)
            contoursOnlyBig.push_back(contours[i]); //add only contours with area > averagePixelsPerObject/4 ---> skip small contours (noise)

    Mat bigContoursOnly = Mat::zeros(output.size(), output.type());
    Mat allContours = bigContoursOnly.clone();
    drawContours(allContours, contours, -1, CV_RGB(255, 255, 255), -1);
    drawContours(bigContoursOnly, contoursOnlyBig, -1, CV_RGB(255, 255, 255), -1);
    //imshow("all contours", allContours);
    output = bigContoursOnly;

    nonZero = countNonZero(output); //not realy important - just for tests
    if (imageIndex != -1)
        cout << "non zero: " << nonZero << ", average pixels per object: " << nonZero/goodResults[imageIndex] << " objects: "  << goodResults[imageIndex] << endl;
    else
        cout << "non zero: " << nonZero << endl;

    for (int i=0; i<contoursOnlyBig.size(); i++)
    {
        double area = contourArea(contoursOnlyBig[i]);
        if (area >= singleObjectPixelsCountMin && area <= singleObjectPixelsCountMax) //is this contours a single grain ?
        {
            contoursSimple.push_back(contoursOnlyBig[i]);
            objectsCount++;
        }
        else
        {
            if (area >= doubleObjectPixelsCountMin && area <= doubleObjectPixelsCountMax) //is this contours a double grain ?
            {
                contoursSimple.push_back(contoursOnlyBig[i]);
                objectsCount+=2;
            }
            else
                contoursWithoutSimpleObjects.push_back(contoursOnlyBig[i]); //group of grainss
        }
    }

    cout << "founded single objects: " << objectsCount << endl;
    Mat thresholdedImageMask = Mat::zeros(output.size(), output.type()), simpleContoursMat = Mat::zeros(output.size(), output.type());
    drawContours(simpleContoursMat, contoursSimple, -1, CV_RGB(255, 255, 255), -1);
    if (contoursWithoutSimpleObjects.size())
        drawContours(thresholdedImageMask, contoursWithoutSimpleObjects, -1, CV_RGB(255, 255, 255), -1); //draw only contours of groups of grains
    imshow("simpleContoursMat", simpleContoursMat);
    imshow("thresholded image mask", thresholdedImageMask);
    Mat finalResult;
    thresholded.copyTo(finalResult, thresholdedImageMask); //copy using mask - only pixels whc=ich belongs to groups of grains will be copied
    //imshow("finalResult", finalResult);
    nonZero = countNonZero(finalResult); // count number of pixels in all gropus of grains (of course without single or double grains)
    int goodObjectsLeft = goodResults[imageIndex]-objectsCount;
    if (imageIndex != -1)
        cout << "non zero: " << nonZero << ", average pixels per object: " << (goodObjectsLeft ? (nonZero/goodObjectsLeft) : 0) << " objects left: " << goodObjectsLeft <<  endl;
    else
        cout << "non zero: " << nonZero << endl;
    objectsCount += round((float)nonZero/(float)averagePixelsPerObject);

    if (imageIndex != -1)
    {
        error = objectsCount-goodResults[imageIndex];
        cout << "final objects count: " << objectsCount << ", should be: " << goodResults[imageIndex] << ", error is: " << error <<  endl;
    }
    else
        cout << "final objects count: " << objectsCount << endl; 
    return output;
}

int main(int argc, char* argv[])
{
    string fileName = "A";
    int totalError = 0, error;
    bool fastProcessing = true;
    vector<int> errors;

    if (argc > 1)
    {
        Mat m = imread(argv[1]);
        imshow("image", m);
        processImage(m, -1, error);
        waitKey(-1);
        return 0;
    }

    while(true)
    {
        Mat m = imread("images\\" + fileName + ".jpg");
        cout << "Processing image: " << fileName << endl;
        imshow("image", m);
        processImage(m, fileName[0] - 'A', error);
        totalError += abs(error);
        errors.push_back(error);
        if (!fastProcessing && waitKey(-1) == 'q')
            break;
        fileName[0] += 1;
        if (fileName[0] > 'J')
        {
            if (fastProcessing)
                break;
            else
                fileName[0] = 'A';
        }
    }
    cout << "Total error: " << totalError << endl;
    cout << "Errors: " << (Mat)errors << endl;
    cout << "averagePixelsPerObject:" << averagePixelsPerObject << endl;

    return 0;
}

If you want to see results of all steps, uncomment all imshow(..,..) function calls and set fastProcessing variable to false. Images(A.jpg, B.jpg,...) should be in directory images. Alternatively course you can give name of one image as a parameter from command line.

Of course if something is unclear i can explain it and/or provide some images/informations.

\$\endgroup\$
13
\$\begingroup\$

C# + OpenCvSharp, score: 71

This is most vexing, I tried to get a solution that actually identifies each grain using watershed, but I just. can't. get. it. to. work.

I settled for a solution that at least separates some individual grains and then uses those grains to estimate the average grain size. However so far I cannot beat the solutions with hardcoded grain size.

So, the main highlight of this solution: it does not presume a fixed pixel size for grains, and should work even if the camera is moved or the type of rice is changed.

A.jpg; number of grains:    3; expected    3; error    0; pixels per grain: 2525,0;
B.jpg; number of grains:    7; expected    5; error    2; pixels per grain: 1920,0;
C.jpg; number of grains:    6; expected   12; error    6; pixels per grain: 4242,5;
D.jpg; number of grains:   23; expected   25; error    2; pixels per grain: 2415,5;
E.jpg; number of grains:   47; expected   50; error    3; pixels per grain: 2729,9;
F.jpg; number of grains:   65; expected   83; error   18; pixels per grain: 2860,5;
G.jpg; number of grains:  120; expected  120; error    0; pixels per grain: 2552,3;
H.jpg; number of grains:  159; expected  150; error    9; pixels per grain: 2624,7;
I.jpg; number of grains:  141; expected  151; error   10; pixels per grain: 2697,4;
J.jpg; number of grains:  179; expected  200; error   21; pixels per grain: 2847,1;
total error: 71

My solution works like this:

Separate the foreground by transforming the image to HSV and applying Otsu thresholding on the saturation channel. This is very simply, works extremely well, and I would recommend this for everyone else who wants to try this challenge:

saturation channel                -->         Otsu thresholding

enter image description here --> enter image description here

This will cleanly remove the background.

I then additionally removed the grain shadows from the foreground, by applying a fixed threshold to the value-channel. (Not sure if that actually helps much, but it was simple enough to add)

enter image description here

Then I apply a distance transform on the foreground image.

enter image description here

and find all local maxima in this distance transform.

This is where my idea breaks down. to avoid getting mutiple local maxima within the same grain, I have to filter a lot. Currently I keep only the strongest maximum within a 45 pixel radius, which means not every grain has a local maximum. And I don't really have a justification for the 45 pixel radius, it was just a value that worked.

enter image description here

(as you can see, those are not nearly enough seeds to account for each grain)

Then I use those maxima as seeds for the watershed algorithm:

enter image description here

The results are meh. I was hoping for mostly individual grains, but the clumps are still too big.

Now I identify the smallest blobs, count their average pixel size, and then estimate the number of grains from that. This is not what I planned to do at the start, but this was the only way to salvage this.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using OpenCvSharp;

namespace GrainTest2
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] files = new[]
                               {
                                   "sourceA.jpg", "sourceB.jpg", "sourceC.jpg",
                                   "sourceD.jpg", "sourceE.jpg", "sourceF.jpg",
                                   "sourceG.jpg", "sourceH.jpg", "sourceI.jpg", "sourceJ.jpg",
                               };
            int[] expectedGrains = new[]{3, 5, 12, 25, 50, 83, 120, 150, 151, 200,};

            int totalError = 0;
            int totalPixels = 0;

            for(int fileNo = 0;fileNo markers = new List();
                    using (CvMemStorage storage = new CvMemStorage())
                    using (CvContourScanner scanner = new CvContourScanner(localMaxima, storage, CvContour.SizeOf, ContourRetrieval.External,ContourChain.ApproxNone))
                    {
                        // set each local maximum as seed number 25, 35, 45,...
                        // (actual numbers do not matter, chosen for better visibility in the png)
                        int markerNo = 20;
                        foreach (CvSeq c in scanner)
                        {
                            markerNo += 5;
                            markers.Add(markerNo);
                            waterShedMarkers.DrawContours(c, new CvScalar(markerNo), new CvScalar(markerNo), 0, -1);
                        }
                    }
                    waterShedMarkers.SaveImage("08-watershed-seeds.png");


                    source.Watershed(waterShedMarkers);
                    waterShedMarkers.SaveImage("09-watershed-result.png");


                    List pixelsPerBlob = new List();

                    // Terrible hack because I could not get Cv2.ConnectedComponents to work with this openCv wrapper
                    // So I made a workaround to count the number of pixels per blob
                    waterShedMarkers.ConvertScale(waterShedThreshold);
                    foreach (int markerNo in markers)
                    {
                        using (CvMat tmp = new CvMat(waterShedMarkers.Rows, waterShedThreshold.Cols, MatrixType.U8C1))
                        {
                            waterShedMarkers.CmpS(markerNo, tmp, ArrComparison.EQ);
                            pixelsPerBlob.Add(tmp.CountNonZero());

                        }
                    }

                    // estimate the size of a single grain
                    // step 1: assume that the 10% smallest blob is a whole grain;
                    double singleGrain = pixelsPerBlob.OrderBy(p => p).ElementAt(pixelsPerBlob.Count/15);

                    // step2: take all blobs that are not much bigger than the currently estimated singel grain size
                    //        average their size
                    //        repeat until convergence (too lazy to check for convergence)
                    for (int i = 0; i  p  Math.Round(p/singleGrain)).Sum());

                    Console.WriteLine("input: {0}; number of grains: {1,4:0.}; expected {2,4}; error {3,4}; pixels per grain: {4:0.0}; better: {5:0.}", file, numGrains, expectedGrains[fileNo], Math.Abs(numGrains - expectedGrains[fileNo]), singleGrain, pixelsPerBlob.Sum() / 1434.9);

                    totalError += Math.Abs(numGrains - expectedGrains[fileNo]);
                    totalPixels += pixelsPerBlob.Sum();

                    // this is a terrible hack to visualise the estimated number of grains per blob.
                    // i'm too tired to clean it up
                    #region please ignore
                    using (CvMemStorage storage = new CvMemStorage())
                    using (CvMat tmp = waterShedThreshold.Clone())
                    using (CvMat tmpvisu = new CvMat(source.Rows, source.Cols, MatrixType.S8C3))
                    {
                        foreach (int markerNo in markers)
                        {
                            tmp.SetZero();
                            waterShedMarkers.CmpS(markerNo, tmp, ArrComparison.EQ);
                            double curGrains = tmp.CountNonZero() * 1.0 / singleGrain;
                            using (
                                CvContourScanner scanner = new CvContourScanner(tmp, storage, CvContour.SizeOf, ContourRetrieval.External,
                                                                                ContourChain.ApproxNone))
                            {
                                tmpvisu.Set(CvColor.Random(), tmp);
                                foreach (CvSeq c in scanner)
                                {
                                    //tmpvisu.DrawContours(c, CvColor.Random(), CvColor.DarkGreen, 0, -1);
                                    tmpvisu.PutText("" + Math.Round(curGrains, 1), c.First().Value, new CvFont(FontFace.HersheyPlain, 2, 2),
                                                    CvColor.Red);
                                }

                            }


                        }
                        tmpvisu.SaveImage("10-visu.png");
                        tmpvisu.SaveImage("10-visu" + file + ".png");
                    }
                    #endregion

                }

            }
            Console.WriteLine("total error: {0}, ideal Pixel per Grain: {1:0.0}", totalError, totalPixels*1.0/expectedGrains.Sum());

        }
    }
}

A small test using a hard-coded pixel-per-grain size of 2544.4 showed a total error of 36, which is still bigger than most other solutions.

enter image description here enter image description here enter image description here enter image description here

\$\endgroup\$
1
  • \$\begingroup\$ I think you can use threshold (erode operation might be usefull too) with some small value on result of distance transform - this should split some groups of grains into smaller groups (preferably - with only 1 or 2 grains). Than it should be easier to count those lonely grains. Big groups you can count as most of people here - dividing area by average area of single grain. \$\endgroup\$
    – cyriel
    Commented Nov 5, 2014 at 3:56
10
\$\begingroup\$

HTML + Javascript: Score 39

The exact values are:

Estimated | Actual
        3 |      3
        5 |      5
       12 |     12
       23 |     25
       51 |     50
       82 |     83
      125 |    120
      161 |    150
      167 |    151
      223 |    200

It breaks down (isn't accurate) on the larger values.

window.onload = function() {
  var $ = document.querySelector.bind(document);
  var canvas = $("canvas"),
    ctx = canvas.getContext("2d");

  function handleFileSelect(evt) {
    evt.preventDefault();
    var file = evt.target.files[0],
      reader = new FileReader();
    if (!file) return;
    reader.onload = function(e) {
      var img = new Image();
      img.onload = function() {
        canvas.width = this.width;
        canvas.height = this.height;
        ctx.drawImage(this, 0, 0);
        start();
      };
      img.src = e.target.result;
    };
    reader.readAsDataURL(file);
  }


  function start() {
    var imgdata = ctx.getImageData(0, 0, canvas.width, canvas.height);
    var data = imgdata.data;
    var background = 0;
    var totalPixels = data.length / 4;
    for (var i = 0; i < data.length; i += 4) {
      var red = data[i],
        green = data[i + 1],
        blue = data[i + 2];
      if (Math.abs(red - 197) < 40 && Math.abs(green - 176) < 40 && Math.abs(blue - 133) < 40) {
        ++background;
        data[i] = 1;
        data[i + 1] = 1;
        data[i + 2] = 1;
      }
    }
    ctx.putImageData(imgdata, 0, 0);
    console.log("Pixels of rice", (totalPixels - background));
    // console.log("Total pixels", totalPixels);
    $("output").innerHTML = "Approximately " + Math.round((totalPixels - background) / 2670) + " grains of rice.";
  }

  $("input").onchange = handleFileSelect;
}
<input type="file" id="f" />
<canvas></canvas>
<output></output>

Explanation: Basically, counts the number of rice pixels and divides it by the average pixels per grain.

\$\endgroup\$
8
  • \$\begingroup\$ Using the 3-rice image, it estimated 0 for me... :/ \$\endgroup\$
    – Kroltan
    Commented Nov 3, 2014 at 7:51
  • 1
    \$\begingroup\$ @Kroltan Not when you use the full size image. \$\endgroup\$ Commented Nov 3, 2014 at 11:44
  • 1
    \$\begingroup\$ @Calvin'sHobbies FF36 on Windows gets 0, on Ubuntu gets 3, with the full size image. \$\endgroup\$
    – Kroltan
    Commented Nov 3, 2014 at 11:58
  • 4
    \$\begingroup\$ @BobbyJack The rice is guaranteed to be at more or less the same scale across images. I see no problems with it. \$\endgroup\$ Commented Nov 3, 2014 at 16:02
  • 1
    \$\begingroup\$ @githubphagocyte - an explanation is quite obvious - if you count all white pixels on result of binarization of image and divide this number by number of grains in image you will get this result. Of course exact result may differ, because of used binarization method and other stuff (like operations performed after binarization), but as you can see in other answers, it will be in range 2500-3500. \$\endgroup\$
    – cyriel
    Commented Nov 5, 2014 at 12:45
5
\$\begingroup\$

An attempt with php, Not the lowest scoring answer but its fairly simple code

SCORE : 31

<?php
for($c = 1; $c <= 10; $c++) {
  $a = imagecreatefromjpeg("/tmp/$c.jpg");
  list($width, $height) = getimagesize("/tmp/$c.jpg");
  $rice = 0;
  for($i = 0; $i < $width; $i++) {
    for($j = 0; $j < $height; $j++) {
      $colour = imagecolorat($a, $i, $j);
      if (($colour & 0xFF) < 95) $rice++;
    }
  }
  echo ceil($rice/2966);
}

Self scoring

95 is a blue value which seemed to work when testing with GIMP 2966 is average grain size

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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