How to calculate the Rectangles in image

Question

I'm given the image below. I want to get the (x, y) and width and height of the rectangles. enter image description here

I posted what I've tried so far below, but it does not give the good result. So if anyone know please show me a good algorithm to solve this problem. Thanks in advance!

public static List<Rectangle> targetLists(final BufferedImage image) {
        final List<List<Integer>> getPixels = getPixels(image);
        final List<Rectangle> rectangleList = new ArrayList<Rectangle>();
        final List<Integer> setX = new ArrayList<Integer>(new HashSet<Integer>(
                getPixels.get(0)));
        final List<Integer> setY = new ArrayList<Integer>(new HashSet<Integer>(
                getPixels.get(1)));
        List<Integer> xPointsList;
        List<Integer> yPointsList;
        if (setX != null) {
            xPointsList = getListOfExactXandYpoints(setX);
            if (xPointsList != null) {
                yPointsList = getListOfExactXandYpoints(setY);
                if (xPointsList.size() >= yPointsList.size()) {
                    return getRectangleListInXmostPoint(xPointsList,
                            yPointsList, rectangleList);
                } else {
                    return getRectangleListInYmostPoint(yPointsList,
                            xPointsList, rectangleList);
                }
            }
        }
        return null;
    }

private static List<List<Integer>> getPixels(BufferedImage image) {
        final List<List<Integer>> lists = new ArrayList<List<Integer>>();
        final List<Integer> targetsListX = new ArrayList<Integer>();
        final List<Integer> targetsListY = new ArrayList<Integer>();
        for(int y=0; y<image.getHeight(); y++) {
            for(int x=0; x<image.getWidth(); x++) {
                if(Color.BLACK.getRGB() == image.getRGB(x, y)) {
                    targetsListX.add(x);
                    targetsListY.add(y);
                }
            }
        }
        lists.add(targetsListX);
        lists.add(targetsListY);
        return lists;
    }

private static List<Rectangle> getRectangleListInYmostPoint(
            final List<Integer> list1, final List<Integer> list2,
            final List<Rectangle> rectangleList) {
        int step = 0;
        for (int i = 0; i < list1.size(); i += 2) {
            rectangleList.add(new Rectangle(new Point(list2.get(step), list1
                    .get(i)), new Dimension(Math.abs(list2.get(step)
                    - list2.get(step + 1)) + 1, Math.abs(list1.get(i)
                    - list1.get(i + 1) + 1))));
            if (!((step + 2) >= list2.size())) {
                step += 2;
            }
        }
        return rectangleList;
    }

    private static List<Rectangle> getRectangleListInXmostPoint(
            final List<Integer> list1, final List<Integer> list2,
            final List<Rectangle> rectangleList) {
        int step = 0;
        for (int i = 0; i < list1.size(); i += 2) {
            rectangleList.add(new Rectangle(new Point(list1.get(i), list2
                    .get(step)), new Dimension(Math.abs(list1.get(i)
                    - list1.get(i + 1)) + 1, Math.abs(list2.get(step)
                    - list2.get(step + 1) + 1))));
            if (!((step + 2) >= list2.size())) {
                step += 2;
            }
        }
        return rectangleList;
    }

    private static List<Integer> getListOfExactXandYpoints(
            final List<Integer> set) {
        final List<Integer> list = new ArrayList<Integer>(set);
        Collections.sort(list);
        final ListIterator<Integer> iterator = list.listIterator();
        final List<Integer> pointsSet = new ArrayList<Integer>();
        int prev = 0;
        while (iterator.hasNext()) {
            final int i = iterator.next();
            if (pointsSet.size() != 0) {
                if (Math.abs(i - prev) > 15) {
                    pointsSet.add(prev);
                    pointsSet.add(i);
                    prev = i;
                } else {
                    prev = i;
                }
            } else {
                pointsSet.add(i);
                prev = i;
            }
        }
        if (pointsSet.size() != 0) {
            if (pointsSet.size() % 2 == 0) {
                pointsSet.remove(pointsSet.size() - 1);
            }
            pointsSet.add(list.get(list.size() - 1));
        }
        return pointsSet;
    }

Maybe a good starting point would be an edge detection algorithm? — RudolphEst, Jul 04 '13 at 16:35
_the code is very long to put here_ Just put **the relevant code** here, not the full code. Or at least a [SSCCE](http://sscce.org/) of what you did try. And also explain **why** the result you get isn't good — BackSlash, Jul 04 '13 at 16:35
What was your algorithm like. High Level Pseudo code and where it does not work will help us help you. — Ayman, Jul 04 '13 at 16:35
Is there anything other than black rectangles in your input image? — XiaoChuan Yu, Jul 04 '13 at 16:35
http://stackoverflow.com/questions/2783204/flood-fill-using-a-stack has some good information — SSpoke, Jul 04 '13 at 16:53
I have edited my java source code in the answer. to provide coordinates — Gaurav Sharma, Jul 05 '13 at 03:47
@BahramdunAdil this is a veryu interesting question... just out of curiosity, what is your use case - what are you using this algorithm for? — bguiz, Jul 05 '13 at 04:45
Thank you! I am using this algorithm to detect the objects in image one while these object are not present in image two when i wanna compare these two images — Bahramdun Adil, Jul 05 '13 at 13:20

XiaoChuan Yu · Answer 1 · 2013-07-04T18:45:58.083

1

Assuming you are only dealing with rectangles of uniform color in a uniform background then the following approach should work:

Lookup how flood fill works and understand it.
For both steps below, mark each pixel you come across as "visited" so that you don't look at same pixel twice.
Flood fill starting anywhere in image until you find a black pixel p (in other words until you find a rectangle).
For loop through pixels in each of 4 the directions of +x (increasing x) ,-x (decreasing x) ,+y,-y to find borders of the rectangle. In other words, this will give you the min x, max x, min y, and max y values that defines the rectangle.
After the floodfill in previous step terminates, you continue from step 2 flood fill starting from any adjacent background pixel and repeat steps above from there until you explored the whole image.

edited Jul 04 '13 at 18:45

answered Jul 04 '13 at 16:45

XiaoChuan Yu

3,951
1
32
44

Once you have found a rectangle, you don't need to flood fill it. Just go in each cardinal direction as far as possible. – Teepeemm Jul 04 '13 at 18:39
You're right, I forgot it was strictly rectangle for some reason. – XiaoChuan Yu Jul 04 '13 at 18:42
Edited to include your suggestion. – XiaoChuan Yu Jul 04 '13 at 18:46

Gaurav Sharma · Answer 2 · 2013-07-05T05:05:41.347

I have made a java Program for this
Because JPEG is a lossy format, i made tolerence of 30 units in RGB for black
I have edited the source to print the coordinates. Coordinates of vertices A and C will be printed in this for a triangle ABCD as enter image description here
You can download java source from here
Now you know the 2 coordinates, you can easily calculate height and width and the other 2 coordinates.

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import javax.imageio.ImageIO;
import java.util.*;
class GetPixelColor {

static List rectList=new ArrayList();

    //int y, x, tofind, col;
    /**
     * @param args the command line arguments
     * @throws IOException  
     */
    public static void main(String args[]) throws IOException {
    int x1=0,x2=0,y1=0,y2=0;
        try {
            //read image file
            File file1 = new File("pic.jpg");
            BufferedImage image1 = ImageIO.read(file1);

              for (int y = 0; y < image1.getHeight(); y++) {
              for (int x = 0; x < image1.getWidth(); x++) {

                  int c = image1.getRGB(x,y);
                  Color color = new Color(c);
                if(color.getRed()<30 &&color.getGreen()<30 &&color.getBlue()<30 && !contains(new Coordinate(x,y)))
                {
                    x1=x;
                    y1=y;
                    for(int i=x;i< image1.getWidth(); i++)
                    {
                        c = image1.getRGB(i,y);
                        color = new Color(c);
                        if(!(color.getRed()<30 && color.getGreen()<30 && color.getBlue()<30) || i==image1.getWidth())
                        {
                            x2=i;
                            break;
                        }
                    }
                    for(int i=y;i<image1.getHeight();i++)
                    {
                        c = image1.getRGB(x,i);
                        color = new Color(c);
                        if(!(color.getRed()<30 &&color.getGreen()<30 &&color.getBlue()<30) || i==image1.getHeight())
                        {
                            y2=i;
                            break;
                        }
                    }

                    rectList.add(new Rectangle(new Coordinate(x1,y1),new Coordinate(x2,y2)));
                   }
        }
        }} catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("No of rectangles = "+rectList.size()+"\n");
        printRect();
    }
static void printRect()
{
    Rectangle r=null;
    for(int i=0;i<rectList.size();i++)
    {
        r=(Rectangle)rectList.get(i);
        System.out.println("("+r.a.x+","+r.a.y+")      ("+r.b.x+","+r.b.y+")");
    }
}
static boolean contains(Coordinate a)
{
    Rectangle r=null;
    for(int i=0;i<rectList.size();i++)
    {
        r=(Rectangle)rectList.get(i);
        if(a.x>=r.a.x && a.x<=r.b.x && a.y>=r.a.y && a.y<=r.b.y)        
            return true;
    }
    return false;
}
}
class Rectangle
{
    Coordinate a,b;
    Rectangle(Coordinate a,Coordinate b)
    {
        this.a=a;
        this.b=b;
    }
}
class Coordinate
{
    int x,y;
    Coordinate(int x,int y)
    {
        this.x=x;
        this.y=y;
    }
}

How to calculate the Rectangles in image

2 Answers2