Segmentation for connected characters

Question

How can I segment if the characters are connected? I just tried using watershed with distance transform (http://opencv-code.com/tutorials/count-and-segment-overlapping-objects-with-watershed-and-distance-transform/) to find the number of components but it seems that it does not perform well.

1. It requires the object to be separated after a threshold in order to perform well.

Having said so, how can I segment the characters effectively? Need helps/ideas.

As attached is the example of binary image.

An example of heavily connected.

Ans:

@mmgp this is my o/p

Rendering

Can you upload some images you are working on.. so that users can give you better suggestions. – Ghibelline

Uploaded example image @Ghibelline – Rendering

Is it for automatically solving captchas? – Coulisse

@redreggae kind of. but i want to try simple example first. – Rendering

@MizukiKai your example image is only 8-connected: i.imgur.com/slVGi.png. If you consider its skeleton branch points and remove from it, then you get all your separated characters: i.imgur.com/qWsU2.png. ImageSubtract[f, MorphologicalTransform[f, "SkeletonBranchPoints"]]. – Joniejonina

@Joniejonina nice. How did you do that? Mind to explain more about the function you use? – Rendering

@MizukiKai I don't know the exact implementation of the method since Mathematica isn't open source, but all it did there was finding points that were only 8-connected and removed both of them. You could also do something that resembles the inverse of this operation and obtain a similar result (disconnected previously connected components): perform a diagonal fill to eliminate 8-connectivity in the image, subtract this from the image, dilate it by a small horizontal line 2x1, subtract the original image from it. Are your images only mis-connected by this situation ? – Joniejonina

@Joniejonina Sometimes, it is heavily connected. Need time to digest of your explanation. =) – Rendering

@MizukiKai this approach only deals with the slightest connection. If you can provide better examples I might try to come up with something better. – Joniejonina

I am trying to resolve issues like this. Could you please paste the final code? – Fieldfare

Answer 1

I believe there are two approaches here: 1) redo the binarization step that led to these images you have right now; 2) consider different possibilities based on image size. Let us focus on the second approach given the question.

In your smallest image, only two digits are connected, and that happens only when considering 8-connectivity. If you handle your image as 4-connected, then there is nothing to do because there are no two components connected that should be separated. This is shown below. The right image can be obtained simply by finding the points that are connected to another one only when considering 8-connectivity. In this case, there are only two such points, and by removing them we disconnect the two digits '1'.

   

In your other image this is no longer the case. And I don't have a simple method to apply on it that can be applied on the smaller image without making it worse. But, actually, we could consider upscaling both images to some common size, using interpolation by nearest neighbor so we don't move from the binary representation. By resizing both of your images so they width equal to 200, and keeping the aspect ratio, we can apply the following morphological method to both of them. First do a thinning:

Now, as can be seen, the morphological branch points are the ones connecting your digits (there is another one at the left-most digit 'six' too, which will be handled). We can extract these branch points and apply a morphological closing with a vertical line of 2*height+1 (height is from your image), so no matter where the point is, its closing will produce a full vertical line. Since your image is not so small anymore, this line doesn't need to be 1 point-wide, in fact I considered a line that is 6 points-wide. Since some of the branch points are horizontally close, this closing operation will join them in the same vertical line. If a branch point is not close to another, then performing an erosion will remove a vertical line. And, by doing this, we eliminate the branch point related to the digit six at left. After applying these steps, we obtain the following image at left. Subtracting the original image from it, we get the image at right.

   

If we apply these same steps to the '8011' image, we end with the exactly same image as we started with. But this is still good, because applying the simple method that remove points that are only connected in 8-connectivity, we obtain the separated components as before.

Joniejonina

I've love to try it. You are using Mathematica to do it? – Rendering

DO you mean 1st you use morphological closing (SE=(1,2*height+1), 2nd use erosion of the same SE? – Rendering

@MizukiKai I used Mathematica, but these exact operations are available in Matlab too (the only difference is in relation to the branch points when the image is not in skeleton form, that is used only in the first of your images), and it is not exactly hard to implement them. The SE I used for closing is (6, 2*height+1); the SE for erosion doesn't matter much, I used an elementary square 3x3. – Joniejonina

tested according to the steps mentioned but still can't get the same as yours.=='.. – Rendering

@MizukiKai show your code if possible, use something like pastebin.com for that – Joniejonina

@MizukiKai I don't see any morphological thinning there. It is the first step. I also don't see any code for finding the branch points. – Joniejonina

ya..before that I applied thinning first then morphological operations. I don't quite understand the branch points part. – Rendering

@MizukiKai in practical terms, removing a branch point disconnects two branches in the skeleton. So a branch point has to have at least 3 foreground neighbors, while other points in the skeleton would have at most two. Detect those points in the skeleton and see what you get. – Joniejonina

do you know what is the simplest way of doing it in opencv? – Rendering

@MizukiKai a two-pass very simple sketch: pastebin.com/nXsYiGZU (it doesn't rely on anything of any library, it is just assuming that white is 255 and black 0). I don't have any guarantee that this simple method will always give the correct branch points, but looks like so. For your example, it matches perfectly. I will test it a bit. – Joniejonina

how about when there are characters 'Y' involved. I'm afraid the 'Y' will be cut into 2. – Rendering

@MizukiKai like the answer says, there is a branch point in the six at left too, but that didn't cut it into two. This also doesn't mean this won't ever fail, but it won't fail if the 'Y' contains a single branch point. – Joniejonina

@Joniejonina Hi, could you please link the code for thinning the origin image? I am trying to implement Zhang-Suen Thinning Algorithm using Python. However, maybe something wrong, I cannot get result as yours. – Fieldfare

Answer 2

It is common to use "smearing algorithms" for this. Also known as Run Length Smoothing Algorithm (RLSA). It is a method that segments black and white images into blocks. You can find some information here or look around on the internet to find an implementation of the algorithm.

Sigil

I've check this thing out. RLSA is not suitable for segmenting connected characters. But thanks anyways. – Rendering

You can find a presentation about different algorithms here: diuf.unifr.ch/courses/07-08/.../DA08-03-Segmentation.v4.ppt They also use RLSA to segment a page of text into blox, but you can also see different methods like x,y segmentation for disconnecting characters. I've used RLSA for License Plate Recognition in combination with x,y segmentation once and that worked quite well. – Sigil

I've tried the link that you gave but where is the explanation of the method? – Rendering

I couldn't find the information that you was talking about. Pls help. – Rendering

google.com/… Perhaps this link is working? – Sigil

By any chance that you could show me the output of your result using RLSA method (before and after applying it)? – Rendering

I really don't think RLSA is good for doing the task of splitting connected components, actually its main intention is to join close components. It would very likely require bigger and better spaced text (but not necessarily binarily disconnected) to have any chance to correctly tell whether to split or not a block. – Joniejonina

Answer 3

Not sure if I want to help you solve captchas, but one idea would be to use erosion. Depending on how many pixels you have to work with it might be able to sufficiently separate the characters without destroying them. This would likely be best used as a pre-processing step for some other segmentation algorithm.

Burka

but I'm afraid erosion will destroy part of the characters especially when there are numeric '1' which is thin. – Rendering

That is a valid concern. It depends on how many pixels you have in each character. – Burka