Detecting and splitting square objects in an image

Question

I have the following source image with random squares in black color:

Questions:

1. How can I detect how many squares are there in it? And how to get information about width, height, and start position (x,y) for each square?

2. How can I separate from combine square to a single square (can separately become 2 squares / 3 squares / more / automatically) as shown below:

i am already make some simple simulation according to this problem, here is my code in matlab, now this code completely work to detect square, but when i change the image source to sample file with square, it has some error

%% First Initialisation tic; % Start timer. clc; % Clear command window. clear; close all; % Close all figure windows except those created by imtool. imtool close all; clearvars; % Get rid of variables from prior run of this m-file. workspace; % Make sure the workspace panel is showing.

%Source
%RGB = imread('Result.png');
RGB = [
     0   0   0   0 255 255 255  0   0;
     0   0   0   0 255 255 255  0   0;
     0   0   0   0 255 255 255 255 255;
    255 255 255 255 0   0   0   0   0;
    255 255 255 255 0   0   0   0   0;
     0   0   0   0 255 255 255  0   0;
     0   0   0   0 255 255 255  0   0;
    255 255 255 255 0   0   0   0   0;
    255 255 255 255 0   0   0   0   0;
    ];
figure;
imshow(RGB);
caption = sprintf('Source Image');
title(caption, 'FontSize', 13);


%%Make It White
white=Make_Image_White(RGB);
figure;
imshow(white);
caption = sprintf('White Image');
title(caption, 'FontSize', 13);
RGB=white;

%save x,y location
[yy xx] = find( RGB == 0 );

%%Prepare Struct Variabel to Save vertical Black Line
RectLine=struct('Line',[],'PosX',[],'PosY',[],'Width',[],'Height',[]);

%start counting vertical black line
startNew=0;
line=0;
limit=0;

for repeat = 1 : size(find(RGB==0),1)
    if startNew==0
        line=line+1;
        fprintf('Start The-%d Line....\n',line);
        startNew=1;
        Height=0;
        if limit==1
            PosY=yy(repeat-1);
            PosX=xx(repeat-1);
            fprintf(' =-=-=-=-=-=-=-=-=-=-=-=-Continue \n'); % Message sent to command window.                
            fprintf(' New Box Detection ==> %d \n', line); % Message sent to command window.                
            fprintf('   Position (x,y) => (%d,%d) \n', PosX, PosY); % Message sent to command window.                
            fprintf('   Counting X-%d : (x,y) -> [ %d , %d ] \n', repeat-1, xx(repeat-1), yy(repeat-1)); % Message sent to command window.                
%            fprintf('xx(repeat)==tempX && tempY+1==yy(repeat)\n\r');
%            fprintf('%d==%d && %d==%d\n\r',xx(repeat-1),xx(repeat-1),tempY-1,yy(repeat-1));
            fprintf(' 1.* add height+1 ==> Counting X-%d : (x,y) -> [ %d , %d ] \n', repeat-1, xx(repeat-1), yy(repeat-1)); % Message sent to command window.                
            tempX=xx(repeat);
            Height=Height+1;    
            tempY=yy(repeat-1);
            startNew=startNew+1;
        else
            PosY=yy(repeat);
            PosX=xx(repeat);
            tempX=0;
            tempY=0;
        end
        Width=1;
        startY=PosY;
        startX=PosX;        
        if limit==0
            fprintf(' =-=-=-=-=-=-=-=-=-=-=-=- Real\n'); % Message sent to command window.                
            fprintf(' New Line Detection ==> %d \n', line); % Message sent to command window.                
            fprintf('   Position (x,y) => [ %d , %d ] \n', PosX, PosY); % Message sent to command window.                
            fprintf('   Counting X-%d : (x,y) -> [ %d , %d ] \n', repeat, xx(repeat), yy(repeat)); % Message sent to command window.                
        end

    end

    if (RGB(yy(repeat),xx(repeat),1)==0)
%            fprintf(' =-=Tes Titik [%d,%d] \n',xx(repeat),yy(repeat)); % Message sent to command window.                
        if tempX==0
%            fprintf('%d==%d && %d==%d\n',xx(repeat),tempX,tempY+1,yy(repeat));
            fprintf(' %d.a add height+1 ==> Counting X-%d : (x,y) -> [ %d , %d ] \n', startNew, repeat,xx(repeat), yy(repeat)); % Message sent to command window.                
            tempX=xx(repeat);
            Height=Height+1;    
            tempY=tempY+1;
            startNew=startNew+1;
        elseif xx(repeat)==tempX && tempY+1==yy(repeat)
 %           fprintf('xx(repeat)==tempX && tempY+1==yy(repeat)\n\r');
 %           fprintf('%d==%d && %d==%d\n\r',xx(repeat),tempX,tempY+1,yy(repeat));
            fprintf(' %d.b add height+1 ==> Counting X-%d : (x,y) -> [ %d , %d ] \n', startNew, repeat,xx(repeat), yy(repeat)); % Message sent to command window.                
            Height=Height+1;     
            tempX=xx(repeat);
            tempY=tempY+1;
            startNew=startNew+1;
            if repeat == size(find(RGB==0),1)
                RectLine(line).Line=line;
                RectLine(line).PosX=PosX;
                RectLine(line).PosY=PosY;
                RectLine(line).Width=Width;
                RectLine(line).Height=Height;                
            end
        else
%            fprintf('xx(repeat)==tempX && tempY+1==yy(repeat)\n');
%            fprintf('%d==%d && %d==%d\n',xx(repeat),tempX,tempY+1,yy(repeat));
            limit=1;            
            startNew=0;
            RectLine(line).Line=line;
            RectLine(line).PosX=PosX;
            RectLine(line).PosY=PosY;
            RectLine(line).Width=Width;
            RectLine(line).Height=Height;                
            tempX=xx(repeat);    
        end
    end;
end

fprintf('\n\nStart Combine Line become Box\n');
RectBox=struct('Box',[],'PosX',[],'PosY',[],'Width',[],'Height',[]);
startBox=1;
for line = size(RectLine,1) : size(RectLine,2)
    fprintf(' ************************** Line %d\n',line);
    Width=0;
    fprintf('  Start Point (%d,%d) Height = %d ** Width=%d\n',RectLine(line).PosX,RectLine(line).PosY,RectLine(line).Height,Width);
    if startBox>1
        exist=0;
        for cek = size(RectBox,1) : size(RectBox,2)
            if (RectLine(line).PosX >= RectBox(cek).PosX) && (RectLine(line).PosX <= RectBox(cek).PosX+RectBox(cek).Width-1) ...
                && (RectLine(line).PosY >= RectBox(cek).PosY) && (RectLine(line).PosY <= RectBox(cek).PosY+RectBox(cek).Height-1)
                if (RectLine(line).Height == RectBox(cek).Height)
                    exist=1;  
                elseif (RectLine(line).Height > RectBox(cek).Height)
                    RectLine(size(RectBox,2)+1).Line=size(RectBox,2)+1;
                    RectLine(size(RectBox,2)+1).PosX=RectLine(line).PosX;
                    RectLine(size(RectBox,2)+1).PosY=RectLine(line).PosY;
                    RectLine(size(RectBox,2)+1).Width=1;
                    RectLine(size(RectBox,2)+1).Height=RectLine(line).Height - RectBox(cek).Height;
                end
            end

            if exist==1
                fprintf('  ** Line Start From (%d,%d) -> Already Exist On Box %d\n',RectLine(line).PosX,RectLine(line).PosY,cek);
                break;
            end
        end
        if exist==0
            for x=RectLine(line).PosX : size(RGB,2)
                fprintf('      Cek Find Start Position looping at %d -> (%d,%d)\n',x,RectLine(line).PosX,RectLine(line).PosY);
                fprintf('      find(RGB(%d:%d,%d:%d))\n',RectLine(line).PosY,RectLine(line).PosY+RectLine(line).Height-1,RectLine(line).PosX,x);
                if find(RGB(RectLine(line).PosY:RectLine(line).PosY+RectLine(line).Height-1,RectLine(line).PosX:x))
                    fprintf('  --> Save %d - Box\n',startBox);
                    fprintf('      Start Position (%d,%d)\n',RectLine(line).PosX,RectLine(line).PosY);
                    fprintf('      Width=%d ** Height=%d\n',Width,RectLine(line).Height);
                    RectBox(startBox).Box=startBox;
                    RectBox(startBox).PosX=RectLine(line).PosX;
                    RectBox(startBox).PosY=RectLine(line).PosY;
                    RectBox(startBox).Width=Width;
                    RectBox(startBox).Height=RectLine(line).Height;    
                    startBox=startBox+1;
                    break;
                elseif x==size(RGB,2)
                    Width=Width+1;
                    fprintf(' b--> Save %d - Box\n',startBox);
                    fprintf('      Start Position (%d,%d)\n',RectLine(line).PosX,RectLine(line).PosY);
                    fprintf('      Width=%d ** Height=%d\n',Width,RectLine(line).Height);
                    RectBox(startBox).Box=startBox;
                    RectBox(startBox).PosX=RectLine(line).PosX;
                    RectBox(startBox).PosY=RectLine(line).PosY;
                    RectBox(startBox).Width=Width;
                    RectBox(startBox).Height=RectLine(line).Height;    
                    startBox=startBox+1;
                    break;
                else
                    up0=0;
                    down0=0;
%                    fprintf('Y RGB=%d,%d \n',RectLine(line).PosY-1,x);
                    if RectLine(line).PosY>1
                        if (RGB(RectLine(line).PosY-1,x)>0)
                            up0=1;
                        else
                        end     

                    else
                        up0=1;
                    end

 %                   fprintf('X RGB=%d,%d \n',RectLine(line).PosY+RectLine(line).Height,x);
                    if (RectLine(line).PosY+RectLine(line).Height) <= size(RGB,1)
                        if (RGB(RectLine(line).PosY+RectLine(line).Height,x)>0)
                            down0=1;
                        end   
                    else
                        down0=1;
                    end
%                    fprintf('posy=%d,x=%d,height=%d-->tot=%d\n',RectLine(line).PosY, x, RectLine(line).Height, RectLine(line).PosY + RectLine(line).Height);
%                    fprintf('Status Up=%d ---- Down=%d\n',up0,down0);
                    if (up0==1) && (down0==1)
                        Width=Width+1;
                        fprintf('    Position (%d,%d) -> Width+1 => %d\n',x,RectLine(line).PosY,Width);                        
                    else
                        fprintf('c  --> Save %d - Box\n',startBox);
                        fprintf('      Start Position (%d,%d)\n',RectLine(line).PosX,RectLine(line).PosY);
                        fprintf('      Width=%d ** Height=%d\n',Width,RectLine(line).Height);
                        RectBox(startBox).Box=startBox;
                        RectBox(startBox).PosX=RectLine(line).PosX;
                        RectBox(startBox).PosY=RectLine(line).PosY;
                        RectBox(startBox).Width=Width;
                        RectBox(startBox).Height=RectLine(line).Height;    
                        startBox=startBox+1;
                        break;
                    end
                end
            end
        end
    else
         for x=RectLine(line).PosX : size(RGB,2)
             fprintf('      Cek Find Start Position looping at %d -> (%d,%d)\n',x,RectLine(line).PosX,RectLine(line).PosY);
             fprintf('      find(RGB(%d:%d,%d:%d))\n',RectLine(line).PosY,RectLine(line).PosY+RectLine(line).Height-1,RectLine(line).PosX,x);

            if find(RGB(RectLine(line).PosY:RectLine(line).PosY+RectLine(line).Height-1,RectLine(line).PosX:x))
                fprintf('  --> Save %d - Box\n',startBox);
                fprintf('      Start Position (%d,%d)\n',RectLine(line).PosX,RectLine(line).PosY);
                fprintf('      Width=%d ** Height=%d\n',Width,RectLine(line).Height);
                RectBox(startBox).Box=startBox;
                RectBox(startBox).PosX=RectLine(line).PosX;
                RectBox(startBox).PosY=RectLine(line).PosY;
                RectBox(startBox).Width=Width;
                RectBox(startBox).Height=RectLine(line).Height;    
                startBox=startBox+1;
                break;
            elseif x==size(RGB,2)
                Width=Width+1;
                fprintf(' b--> Save %d - Box\n',startBox);
                fprintf('      Start Position (%d,%d)\n',RectLine(line).PosX,RectLine(line).PosY);
                fprintf('      Width=%d ** Height=%d\n',Width,RectLine(line).Height);
                RectBox(startBox).Box=startBox;
                RectBox(startBox).PosX=RectLine(line).PosX;
                RectBox(startBox).PosY=RectLine(line).PosY;
                RectBox(startBox).Width=Width;
                RectBox(startBox).Height=RectLine(line).Height;    
                startBox=startBox+1;
                break;
            else
                Width=Width+1;
                fprintf('    Position (%d,%d) -> Width+1 => %d\n',x,RectLine(line).PosY,Width);
            end
        end
    end
end

RectBox 

expectation result like this

https://i.sstatic.net/onUeJ.jpg

Answer 1

oh, thank GOD, i already found the problem. it is because of different dimension of the image, in my small simulation, i use 1 dimension, do when i want to get (x,y) position, i just do

%save x,y location
[yy xx] = find( RGB == 0 );

so, when i change the source to sample image, that sample image have 3 dimension, when i do this command

%save x,y location
[yy xx] = find( RGB == 0 );

on the xx part, it will be multiply by 3, it will become xx*3 so, i add some command before it

%change dimension 3 become 1
if size(RGB,3) > 1 
    RGB = rgb2gray(RGB); 
end

%save x,y location
[yy xx dimension] = find( RGB == 0 );

after this, all program work nice.

by the way, this code execution take time, because it check one by one all pixel, anybody have any solution to cut the time please ?

thank for your help

Answer 2

the code is not in matlab but it can be easily converted into it since i only use the most basic operations other than the drawing routines.

The key idea is simply to just detect the minimum rectangle size first. The black ones are in fact not squares, they are rectangles. You do this by scanning horizontally and vertically and finding continuous region of black areas. The minimum pixel length in each direction forms the minimum rectangle size.

import cv2
import numpy as np
im=cv2.imread('QfOab0P.png')
cv2.imshow('im',im)

# the following deal with jpeg artifacts and squares will contain clean squares at the end
squares = np.zeros((im.shape[0],im.shape[1]),np.uint8)

for y in xrange(im.shape[0]):
    for x in xrange(im.shape[1]):
        if (sum(im[y,x,:])<40):
            squares[y,x]=255
squares=cv2.erode(squares,np.ones((5,5),np.uint8))
squares=cv2.dilate(squares,np.ones((5,5),np.uint8))


# we need to detect minimum size of the square
szx = {}
szy={}
# scan vertically
for x in xrange(im.shape[1]):
    sz = 0
    for y in xrange(im.shape[0]):
        if squares[y,x]==255:
            sz += 1
        elif sz>0:
            if sz not in szy:
                szy[sz]=0
            szy[sz]+=1
            sz = 0
    if sz > 0:
        if sz not in szy:
            szy[sz]=0
        szy[sz]+=1
        sz = 0
# scan horizontally
for y in xrange(im.shape[0]):
    sz = 0
    for x in xrange(im.shape[1]):
        if squares[y,x]==255:
            sz += 1
        elif sz>0:
            if sz not in szx:
                szx[sz]=0
            szx[sz]+=1
            sz = 0
    if sz > 0:
        if sz not in szx:
            szx[sz]=0
        szx[sz]+=1
        sz = 0
szx = {k:v for k,v in szx.iteritems() if v>10} # dicard spurious small values caused by imperfect thresholding
szy = {k:v for k,v in szy.iteritems() if v>10}

sqsz = [min(szx.keys()),min(szy.keys())]
# now we may need to refine the values so that we can differentiate between 56 vs 57 in this example
sqsz[0] = int(round(float(im.shape[1])/int(im.shape[1]/float(sqsz[0]))))
sqsz[1] = int(round(float(im.shape[0])/int(im.shape[0]/float(sqsz[1]))))
print sqsz
if im.shape[0]%sqsz[1]!=0 or im.shape[1]%sqsz[0]!=0:
    print 'square size detection failed'
# since you know the minimum square size, you can do whatever you wish
# here's an example where the black squares are numbered
# of course you can get fancy and move the blocks around if you want to
sq_cnt =0
for yi in xrange(im.shape[0]/sqsz[1]):
    for xi in xrange(im.shape[1]/sqsz[0]):
        x = xi*sqsz[0]
        y = yi*sqsz[1]
        patch = im[y:y+sqsz[1],x:x+sqsz[0],:]
        if patch.sum()<100000:#this should be ideally equal to zero but due to jpeg,black is not always black
            #this is a black square
            cv2.putText(im,str(sq_cnt),(x+sqsz[0]/2,y+sqsz[1]/2),cv2.FONT_HERSHEY_SIMPLEX,0.5,(255,255,255),2)
            sq_cnt+=1
        cv2.rectangle(im,(x,y),(x+sqsz[0],y+sqsz[1]),(255,255,0))
cv2.imshow('sq',squares)
cv2.imshow('with_squares',im)
cv2.imwrite('with_squares.jpg',im)
cv2.waitKey(0)

Answer 3

I don't use Matlab, but here are some ideas implemented using ImageMagick (just at the command line) that you can hopefully adapt.

If you threshold your image and detect edges, like this:

convert chess.png -threshold 10 -edge 1 result.png

If you now erode using a 1x3 rectangular structuring element, you will remove the horizontal lines and get this:

convert chess.png -threshold 10 -edge 1 -morphology erode rectangle:1x3 result.png

You can now scan across the image by rows and look for white pixels which will tell you where the edges of the blocks are.

Then you can apply the same technique across the image the other way:

convert chess.png -threshold 10 -edge 1 -morphology erode rectangle:3x1 result.png

You can then deduce your square size from the smallest gap between white pixels detected either vertically or horizontally.

Then you can apply "Blob Analysis" or "Connected Component Analysis" to the thresholded image to find the black squares:

convert chess.png -threshold 10 -negate       \
    -define connected-components:verbose=true \
    -connected-components 4 output.png

Sample Output

Objects (id: bounding-box centroid area mean-color):
  0: 420x399+0+0 144.3,166.8 78660 srgb(0,0,0)
  3: 240x285+180+114 287.5,256.0 34200 srgb(255,255,255)
  6: 120x171+300+171 374.5,256.0 13680 srgb(0,0,0)
  5: 120x114+0+171 69.5,237.0 10260 srgb(255,255,255)
  2: 120x114+300+57 369.5,104.0 10260 srgb(255,255,255)
  1: 120x57+120+0 179.5,28.0 6840 srgb(255,255,255)
  4: 60x57+300+114 329.5,142.0 3420 srgb(0,0,0)
  7: 60x57+60+342 89.5,370.0 3420 srgb(255,255,255)
  8: 60x57+180+342 209.5,370.0 3420 srgb(255,255,255)
  9: 60x57+240+342 269.5,370.0 3420 srgb(0,0,0)

And each line tells us the height and width of a blob and its top-left corner. I'll draw those blobs onto the original image in red:

You can actually also deduce the size of the squares in your original image by looking at the GCD of the dimensions of the blobs - they are all multiples of around 60.

So, now you can also do the second part of your question. Look at the blob that is 120x57, that must be 2 squares by 1 square.

Answer 4

To answer the first part of your question:

I = imread('866PX.jpg');

%Split your image into smaller elements
I2 = mat2cell(I,repmat(40,10,1),repmat(42,10,1),3); 

%if an element has more than half of its pixels = 0 then this element is a black square.
for ii = 1:10
    for jj = 1:10
        ind(ii,jj) = sum(I2{ii,jj}(:)>0)>(numel(I2{1,1})/2);
    end
end

imshow(ind)
%number of black square
nbr = sum(~ind(:))

RESULT:

Answer 5

The black squares are completely black (RGB value [0,0,0]) so you can threshold with a very low value and you will have a mask that only keeps the squares (better approaches exist but you can start with this one)

Then you can run some edge detector to keep only the edges.

If you then add the pixels column-wise and row-wise, the peaks will correspond to those columns and rows belonging to the edges of the squares.

Since you know the squares have the same size, you can extrapolate the missing columns and rows in case some of them don't have a black square that gives you a peak.

Another approach would be running Hough transform and keeping only perfectly horizontal and vertical lines which will correspond to the edges of the squares.