Get rectangle bounds for each letter in a image

So I'm trying to fill an ArrayList<Rectangle> with the bounds of each letter of an image file.

For example, given this .png image:

I want to fill an ArrayList<Rectangle> with 14 Rectangle(one rectangle for each letter)

We can assume that the image will contain only 2 colors, one for the background and one for the letters, in this case, pixels will be either white or red.

At first, I thought I could search for white columns in between the letters, then if I found a completely white column I could get for example the width by getting the lowest red pixel value and the highest red pixel value and width = maxX-minX and so on:

x = minX;
y = minY;
w = maxX-minX;
h = maxY-minY;

letterBounds.add(new Rectangle(x,y,w,h));

The problem is that there's no space in between the letters, not even 1 pixel:

My next idea was for each red pixel I find, look for a neighbor that hasn't been seen yet, then if I can't find a neighbor I have all the pixels to get the bounds of that letter. But with this approach, I will get 2 rectangles for letters like "i" I could then write some algorithm to merge those rectangles but I don't know how that will turn out with other multi part letters, and before I try that I wanted to ask here for more ideas

So do you guys have any ideas?

You can use the OpenCV cv2.findContours() function. Instead of using the cv2.drawcontours() function for drawing the contours, which will highlight the outline of the letter, you could instead draw a rectangle on the image by using the cv2.rectangle and by extracting the coordinates from cv2.findContours() function.

I think two step algorithm is enough to solve the problem if not using library like OpenCV.

1. histogram
2. seam calculation

1. histogram

C.....C..C...
.C.C.C...C...
. C.C....CCCC
1111111003111

• dot(.) means background color(white)
• C means any colors except background color(in your case, red)

accumulating the number of vertical pixels with non-background color generates histogram.

        *
        *
******..****
0123456789AB

It is clear the boundary exists at 6 and 7

2. seam calculation

Some cases like We, cannot be solved by histogram because there is no empty vertical lines at all.

Seam Carving algorithm gives us some hints

• https://en.wikipedia.org/wiki/Seam_carving

More detail implementation is found at

• princeton.edu - seamCarving.html

Energy calcuation for a pixel

The red numbers are not color values for pixels, but energy values calculated from adjacent pixels.

The vertical pathes with minimal energy give us the boundary of each characters.

3. On more...

Statistical data is required to determine whether to apply the seam carving or not.

• Max and min width of characters

Even if histogram give us vertical boundaries, it is not clear there are two or more characters in a group.