Detectings small circles on game minimap

Question

i am stuck on this problem for like 20h.

The quality is not every good because on 1080p video, the minimap is less than 300px / 300px

I want to detect the 10 heros circles on this images:

Like this:

For background removal, i can use this:

The heroes portrait circle radius are between 8 to 12 because a hero portrait is like 21x21px.

With this code

Mat minimapMat = mgcodecs.imread("minimap.png");
Mat minimapCleanMat = Imgcodecs.imread("minimapClean.png");
Mat minimapDiffMat = new Mat();
Core.subtract(minimapMat, minimapCleanMat, minimapDiffMat);

I obtain this:

Now i apply circles detection on it:

    findCircles(minimapDiffMat);
    public static void findCircles(Mat imgSrc) {
        Mat img = imgSrc.clone();

        Mat gray = new Mat();
        Imgproc.cvtColor(img, gray, Imgproc.COLOR_BGR2GRAY);

        Imgproc.blur(gray, gray, new Size(3, 3));

        Mat edges = new Mat();
        int lowThreshold = 40;
        int ratio = 3;
        Imgproc.Canny(gray, edges, lowThreshold, lowThreshold * ratio);

        Mat circles = new Mat();
        Vector<Mat> circlesList = new Vector<Mat>();

        Imgproc.HoughCircles(edges, circles, Imgproc.CV_HOUGH_GRADIENT, 1, 10, 5, 20, 7, 15);

        double x = 0.0;
        double y = 0.0;
        int r = 0;

        for (int i = 0; i < circles.rows(); i++) {
            for (int k = 0; k < circles.cols(); k++) {

                double[] data = circles.get(i, k);
                for (int j = 0; j < data.length; j++) {
                    x = data[0];
                    y = data[1];
                    r = (int) data[2];
                }
                Point center = new Point(x, y);
                // circle center
                Imgproc.circle(img, center, 3, new Scalar(0, 255, 0), -1);
                // circle outline
                Imgproc.circle(img, center, r, new Scalar(0, 255, 0), 1);

            }
        }

        HighGui.imshow("cirleIn", img);
    }

Results is not ok, detecting only 2 on 10:

I have tried with knn background too:

With less success. Any tips ? Thanks a lot in advance.

Answer 1

The problem is that your minimap contains highlighted parts (possibly around active players) rendering your background removal inoperable. Why not threshold the highlighted color out from the image? From what I see there are just few of them. I do not use OpenCV so I gave it a shot in C++ here is the result:

int x,y;
color c0,c1,c;
picture pic0,pic1,pic2;
    // pic0 - source background
    // pic1 - source map
    // pic2 - output
// ensure all images are the same size
pic1.resize(pic0.xs,pic0.ys);
pic2.resize(pic0.xs,pic0.ys);
// process all pixels
for (y=0;y<pic2.ys;y++)
 for (x=0;x<pic2.xs;x++)
    {
    // get both colors without alpha
    c0.dd=pic0.p[y][x].dd&0x00FFFFFF;
    c1.dd=pic1.p[y][x].dd&0x00FFFFFF;         c=c1;
    // threshold           0xAARRGGBB   distance^2
    if (distance2(c1,color(0x00EEEEEE))<2000) c.dd=0;   // white-ish rectangle
    if (distance2(c1,color(0x00889971))<2000) c.dd=0;   // gray-ish path
    if (distance2(c1,color(0x005A6443))<2000) c.dd=0;   // gray-ish path
    if (distance2(c1,color(0x0021A2C2))<2000) c.dd=0;   // aqua water
    if (distance2(c1,color(0x002A6D70))<2000) c.dd=0;   // aqua water
    if (distance2(c1,color(0x00439D96))<2000) c.dd=0;   // aqua water
    if (distance2(c1,c0               )<2500) c.dd=0;   // close to background
    pic2.p[y][x]=c;
    }
pic2.save("out0.png");
pic2.pixel_format(_pf_u);   // convert to gray scale
pic2.smooth();              // blur a little
pic2.save("out1.png");
pic2.threshold(0,80,765,0x00000000);    // set dark pixels (<80) to black (0) and rest to white (3*255)
pic2.pixel_format(_pf_rgba);// convert back to RGB
pic2.save("out2.png");

So you need to find OpenCV counter parts to this. The thresholds are color distance^2 (so I do not need sqrt) and looks like 50^2 is ideal for <0,255> per channel RGB vector.

I use my own picture class for images so some members are:

xs,ys is size of image in pixels
p[y][x].dd is pixel at (x,y) position as 32 bit integer type
clear(color) clears entire image with color
resize(xs,ys) resizes image to new resolution
bmp is VCL encapsulated GDI Bitmap with Canvas access
pf holds actual pixel format of the image:

enum _pixel_format_enum
    {
    _pf_none=0, // undefined
    _pf_rgba,   // 32 bit RGBA
    _pf_s,      // 32 bit signed int
    _pf_u,      // 32 bit unsigned int
    _pf_ss,     // 2x16 bit signed int
    _pf_uu,     // 2x16 bit unsigned int
    _pixel_format_enum_end
    };

color and pixels are encoded like this:

union color
    {
    DWORD dd; WORD dw[2]; byte db[4];
    int i; short int ii[2];
    color(){}; color(color& a){ *this=a; }; ~color(){}; color* operator = (const color *a) { dd=a->dd; return this; }; /*color* operator = (const color &a) { ...copy... return this; };*/
    };

The bands are:

enum{
    _x=0,   // dw
    _y=1,

    _b=0,   // db
    _g=1,
    _r=2,
    _a=3,

    _v=0,   // db
    _s=1,
    _h=2,
    };

Here also the distance^2 between colors I used for thresholding:

DWORD distance2(color &a,color &b)
    {
    DWORD d,dd;
    d=DWORD(a.db[0])-DWORD(b.db[0]); dd =d*d;
    d=DWORD(a.db[1])-DWORD(b.db[1]); dd+=d*d;
    d=DWORD(a.db[2])-DWORD(b.db[2]); dd+=d*d;
    d=DWORD(a.db[3])-DWORD(b.db[3]); dd+=d*d;
    return dd;
    }

As input I used your images:

pic0:

pic1:

And here the (sub) results:

out0.png:

out1.png:

out2.png:

Now just remove noise (by blurring or by erosion) a bit and apply your circle fitting or hough transform...

[Edit1] circle detector

I gave it a bit of taught and implemented simple detector. I just check circumference points around any pixel position with constant radius (player circle) and if number of set point is above threshold I found potential circle. It is better than use whole disc area as some of the players contain holes and there are more pixels to test also ... Then I average close circles together and render the output ... Here updated code:

    int i,j,x,y,xx,yy,x0,y0,r=10,d;
    List<int> cxy;  // circle circumferece points
    List<int> plr;  // player { x,y } list
    color c0,c1,c;
    picture pic0,pic1,pic2;
        // pic0 - source background
        // pic1 - source map
        // pic2 - output
    // ensure all images are the same size
    pic1.resize(pic0.xs,pic0.ys);
    pic2.resize(pic0.xs,pic0.ys);
    // process all pixels
    for (y=0;y<pic2.ys;y++)
     for (x=0;x<pic2.xs;x++)
        {
        // get both colors without alpha
        c0.dd=pic0.p[y][x].dd&0x00FFFFFF;
        c1.dd=pic1.p[y][x].dd&0x00FFFFFF;         c=c1;
        // threshold           0xAARRGGBB   distance^2
        if (distance2(c1,color(0x00EEEEEE))<2000) c.dd=0;   // white-ish rectangle
        if (distance2(c1,color(0x00889971))<2000) c.dd=0;   // gray-ish path
        if (distance2(c1,color(0x005A6443))<2000) c.dd=0;   // gray-ish path
        if (distance2(c1,color(0x0021A2C2))<2000) c.dd=0;   // aqua water
        if (distance2(c1,color(0x002A6D70))<2000) c.dd=0;   // aqua water
        if (distance2(c1,color(0x00439D96))<2000) c.dd=0;   // aqua water
        if (distance2(c1,c0               )<2500) c.dd=0;   // close to background
        pic2.p[y][x]=c;
        }
//  pic2.save("out0.png");
    pic2.pixel_format(_pf_u);   // convert to gray scale
    pic2.smooth();              // blur a little
//  pic2.save("out1.png");
    pic2.threshold(0,80,765,0x00000000);    // set dark pixels (<80) to black (0) and rest to white (3*255)

    // compute player circle circumference points mask
    x0=r-1; y0=r; x0*=x0; y0*=y0;
    for (x=-r,xx=x*x;x<=r;x++,xx=x*x)
     for (y=-r,yy=y*y;y<=r;y++,yy=y*y)
        {
        d=xx+yy;
        if ((d>=x0)&&(d<=y0))
            {
            cxy.add(x);
            cxy.add(y);
            }
        }

    // get all potential player circles
    x0=(5*cxy.num)/20;
    for (y=r;y<pic2.ys-r;y+=2)  // no need to step by single pixel ...
     for (x=r;x<pic2.xs-r;x+=2)
        {
        for (d=0,i=0;i<cxy.num;)
            {
            xx=x+cxy.dat[i]; i++;
            yy=y+cxy.dat[i]; i++;
            if (pic2.p[yy][xx].dd>100) d++;
            }
        if (d>=x0) { plr.add(x); plr.add(y); }
        }

//  pic2.pixel_format(_pf_rgba);// convert back to RGB
//  pic2.save("out2.png");

    // average all circles too close together
    pic2=pic1;  // use original image again
    pic2.bmp->Canvas->Pen->Color=TColor(0x0000FF00);
    pic2.bmp->Canvas->Pen->Width=3;
    pic2.bmp->Canvas->Brush->Style=bsClear;
    for (i=0;i<plr.num;i+=2) if (plr.dat[i]>=0)
        {
        x0=plr.dat[i+0]; x=x0;
        y0=plr.dat[i+1]; y=y0; d=1;
        for (j=i+2;j<plr.num;j+=2) if (plr.dat[j]>=0)
            {
            xx=plr.dat[j+0];
            yy=plr.dat[j+1];
            if (((x0-xx)*(x0-xx))+((y0-yy)*(y0-yy))*10<=20*r*r) // if close
                {
                x+=xx; y+=yy; d++;  // add to average
                plr.dat[j+0]=-1;    // mark as deleted
                plr.dat[j+1]=-1;
                }
            }
        x/=d; y/=d;
        plr.dat[i+0]=x;
        plr.dat[i+1]=y;
        pic2.bmp->Canvas->Ellipse(x-r,y-r,x+r,y+r);
        }
    pic2.bmp->Canvas->Pen->Width=1;
    pic2.bmp->Canvas->Brush->Style=bsSolid;
//  pic2.save("out3.png");

As you can see the core of code is the same I just added the detector in the end.

I also use mine dynamic list template so:

List<double> xxx; is the same as double xxx[];
xxx.add(5); adds 5 to end of the list
xxx[7] access array element (safe)
xxx.dat[7] access array element (unsafe but fast direct access)
xxx.num is the actual used size of the array
xxx.reset() clears the array and set xxx.num=0
xxx.allocate(100) preallocate space for 100 items

And here the final result out3.png:

As you can see it is a bit messed up when the players are very near (due to circle averaging) with some tweaking you might get better results. But on second taught it might be due to that small red circle nearby ...

I used VCL/GDI for the circles render so just ignore/port the pic2.bmp->Canvas-> stuff to what ever you use.

Answer 2

As the populated image is lighter in the blue areas around the heroes, your background subtraction is of virtually no use.

I tried to improve by applying a gain of 3 to the clean image before subtraction and here is the result.

The background has disappeared, but the outlines of the heroes are severely damaged.

I looked at your case with other approaches and I consider that it is a very difficult one.

Answer 3

What I do when I want to do image processing is first open the image in a paint editor (I use Gimp). Then I manipulate the image the until I end up with something that defines the parts I want to detect. Generally, RGB is bad for a lot of computer vision tasks, and making it gray scale solves only a part of the problem. A good start is trying to decompose the image to HSL instead. Doing so on the first image, and only looking at the Hue channel gives me this:

Several of the blobs are quite well defined.

Playing a bit with the contrast and brightness of the Hue and Luminance layers and multiplying them gives me this:

It enhances the ring around the markers, which might be useful.

These methods all have corresponding functionality in OpenCV.

It's a tricky task and you will most likely require several different filters and techniques to succeed. Hope this helps a bit. Good luck.