Segmenting Shaped by Morphology

[nixscripter]

Hello all.

I looked on the forums and found this old topic about how to segment images:
http://imagemagick.org/discourse-server ... =1&t=18683

And Anthony said:

At this time IM is short on built-in segmentation methods. They are planned but there are just not enough programmers willing to get their hands dirty.

Have any of those plans come to fruition? I haven't seen anything in the help pages.

If not, I have found a different way to solve a similar (but not identical) problem from that thread. My problem is related to textual OCR. I was wondering if anyone had comments, or a more efficient way to do it.

Code: Select all

#!/bin/sh
#
# Created by nixscripter.
# Released into the public domain, in the hopes that it will be useful.
#
# Objective: segments a monochrome image into individual "shapes" based on shape
# boundaries.
# Input: one monochrome image, white background, black foreground. If you want
# it the other way, remove the negate from the first command, but it has only
# been tried with monochrome.
# Output: a series of images, each of the original canvas size, which has a
# white background, and one of the black shapes on it. Each file will be named
# "outputX,Y.png", where X,Y is one point that is unique to the shape contained
# in that image.
#

ORIGINAL=$1
CONVEX="tmpconvex.png"

#
# First, find all the octagonal convex hulls of the various shapes in the image.
# NOTE: Dialated by one just to cover the "loose ends" of certain shapes which
# occur in the original application.
# NOTE 2: Kudos to Anthony's page on Convex Hull!
#
convert "$ORIGINAL" -negate -morphology Close Diamond:1 -morphology Thicken:-1 ConvexHull -morphology Close Diamond -morphology Dilate Diamond:1 "$CONVEX"

#
# Next, make a list of "corner points" -- a set of points, each of which is in
# the convex hull of one shape. Since the convex hull is octagonal, there ought
# to be exactly one of these in every shape.
#
CORNERS=`convert "$CONVEX" -morphology HMT "3:0,0,0 0,1,1 -,1,-" txt:- | grep white | cut -d: -f1`

#
# For each point:
#   Use that point as a point for a flood-fill to find the entire shape
#   Use that filled shape as a mask on the whole image.
#
for point in $CORNERS
do
	# Create a new image with just this one shape's convex hull
	convert "$CONVEX" -fill red -draw "color $point floodfill" -fill white -draw 'color 0,0 replace' -monochrome -negate "tmp${point}.png"
	# And mask the image with it -- and get rid of the "excess" with flatten
	convert "$ORIGINAL" "tmp${point}.png" -alpha Off -compose CopyOpacity -composite -background white miff:- | convert -background white miff:- -flatten "output${point}.png"
	rm -f "tmp${point}.png"
done

[fmw42]

I did it slightly differently in my bash unix script, separate. See link below. It uses compare with a one pixel image to find each white region to floodfill, but it has to iterate by masking out a region after extracting and then do a compare again. However, with a 1-pixel image, compare is rather fast.

Using the convex hull is rather nice in that it gets all the regions in one pass.

[anthony]

The 'label' morphology operator is in the ToDo list. I have the algorithm, and even have the place where the code needs to be added. It just has not been done

At this time I am heavilly involved with IMv7 and developing a new Shell API command that allows 'piping' of options into the command. See http://www.imagemagick.org/Usage/bugs/I ... ipting.txt for details.

[nixscripter]

@Fred: Do you use every point because you are trying to get shapes inside one another, or is there something else my algorithm would miss?

@Anthony: I see. I am curious about what you have, actually. I have looked at some of the internal code and it seems pretty readable. I might try my hand at implementing some of that in the C code. I have read some of the core, and it seems pretty straightforward (he says glibly ).

[fmw42]

@Fred: Do you use every point because you are trying to get shapes inside one another, or is there something else my algorithm would miss?

My script iterates until it has found every isolated region of white in a black background. Right now it is limited to 256 regions, but that could be changed.

[anthony]

@Anthony: I see. I am curious about what you have, actually. I have looked at some of the internal code and it seems pretty readable. I might try my hand at implementing some of that in the C code. I have read some of the core, and it seems pretty straightforward (he says glibly ).

The code is basically a 2-pass system (rather than the one pass per segment found that external scripts use).

In one pass each new region (not background) is given a incrementing (unique) number, which is replicated left-right-down to its neighbours (like a row-by-row floodfill, but using a morphological neighbourhood, which must be symetrical)

This is actually very similar to the algorithim that is used for a 2-pass 'distance from edge' morphology operation (though the distance kernel does not need to be symetrical). In fact I'd use the same row by row loop for BOTH distance and labeling (where the code would be added).

When two region numbers are discovered to be next to each other (according to the morphological neighbourhood), they are recorded in a temporary table, as being actualy the same number (region), and the smaller number is used from that point on.
Between passes the temporary table is updated with the a final label mapping value, and during the second pass all region numbers previously assigned, are replace with the final 'label' number. This essentually merges all the regions that were initially throught to be seperate, but were later found to be the same region.

At the end of the second pass you have all regions uniquely (and consecutivally) numbered (sorted by the top most Y coordinate). You also have a true count of the number of regions. This count can be noted in a image property for later use (via a percent escape).

Note the use of the morphology kernel to define either Z4 (diamond) or Z8 (square) neighbourhoods, or even larger disk kernels. Larger kernels which would allow 'near' regions (separated by a small gap) to be defined as part of the same region. That gap jumping feature can for example label 'words' rather than individual letters in a text image.

[nixscripter]

I have read the code for Euclidian Distance... and I think I can sort of follow it. But I'm having a little trouble connecting that code with what you said.

Is my psudeocode even close?

Code: Select all

function segmentMe (Image* input, Image* output, KernelInfo* kernel)
    create array object_ids
    // generate object IDs for each pixel
    for x = 0 to input row count
        align kernel on the row correctly
        for v = 0 to kernel height
            for u = 0 to kernel width
                result_id = minimize(result, kernel value * pixel under it) // so that the same color means same ID
            end for
            move kernel one pixel right
        end for
         append result_id to object_ids
    end for
    merge adjacent ID items together by color (??)
    // create the separate images
    for id in object_ids
        create new layer on output
        set new layer background to transparency
        set all pixels which have the ID of id to black
    end for
end function

[anthony]

To an extent, though 'x' variable is really a 'y' and while examining a specific point you only need to look at the pixels already examined and which falls within the top half of the kernel that defines the neighbourhood of those examined. This has to be performed in two steps. previous rows, and current row as only part of the current row has so far been exaimned.

Other than the actual pixel assignment, the looping code for that pass is practically identical to the code in "morphology.c" lines 3360 - 3545


Remember the kernel for a labeling function must be symetrical, so only the half the kernel is actually needed for this task.

The first half would be almost identical to the first pass of the distance function. The second half is just a replacement of pixel values so all connecting groups of pixels have the same final value, preferably without leavle gaps between the resulting pixel values. EG: groups are numbered 1,2,3,4... and not 1,2,5,7 that is what the step between the passes works out.

[nixscripter]

And, er, that's the code chunk I'm looking at, the MorphologyPrimitive() function... and it's not clicking.

Hopefully, someone else can get it done faster than I can. In the mean time, I appreciate the commentary.