Extract largest continuous pixel section

[yyyy273]

I have quite a few images that look similar to this one


I am trying to automatically extract the "9" from the image but its proving problematic. I tried..

1. converting the image to a txt file
2. using a C program to read the txt file and find the first black pixel
3. input the x and y values of the first black pixel to the floodfill command, using a different color for each segment
4. use a command I saw on here somewhere that showed you a count of the different pixel colors
5. floodfill all but the largest segment to white

however this seems like an EXTREMELY round-a-bout way of doing it and was wondering if someone could point me in a better direction.

EDIT: I am using C

[fmw42]

floodfill the "9" to red, then change black to white, then change red to black. Not automatic, though, and I don't know any automatic way within IM.

[anthony]

Automatically finding the largest segment is the problem.

This is an image spatial segmentation problem. However -segment is a color segmentation option, so don't even bother trying that.


At this time IM has very little in the way of help. It is an area I would like to see more work in, but at this time it isn't available.

The main problem is getting interested programmers on the IM development team. I am interested, but am bogged down in Image distortions. Fred is also interested and writes a lot of great shell scripts, but is not a C programmer.

[yyyy273]

Have any ideas on how to color each segment so I could use -segment on it?

[anthony]

Interesting idea...

Hmmm do random color flood fills with a list of different colors?

that should make each object a different color!!!

just a idea.

Actually it may be a good technique, if you apply it using a grid of points each with a different color. The colors could come from
say the netscape: image (ignoring white and black) so as to ensure
the best color seperation...

Code: Select all

convert netscape: -unique-colors txt:-

You can then mask out each color, though many will not be present having been floodfilled multiple times. Remember
+opaque or +transparent will make any color not matching the one you give transparent!

Algorithm could be improved by scaning the image, and only floodfilling a point that has not already been flood filled, and thus extracted.

I'll see if I can get a script for you.

It would be faster if we had a 'inverted floodfill' That is a flood fill which will remove everything except the flooded area.

[anthony]

I have a slow shell script version!!!

It takes the input image, looks for a non-transparent pixel.
It then converts the first such pixel found into transparency
compares that to the previous image and outputs the area flood fills (as is), then loops looking for the next non-transparent pixel.

Code: Select all

   segment_image   segment.png   segment.gif

segment.gif will be a multi-image GIF file one image per segment found... script found 14 segments, 2 of them white (background and the circle in the '9'. It does not care at all what the segment colors are. Only that they are the same pure color, as such two background segment were found. If the background was made transparent first, thye would also be discounted.

The script will appear in IM examples scripts area
http://imagemagick.org/Usage/scripts/segment_image

Here is a montage of the results after running the images though
-coalesce -layers optimize to trim the segments to smaller 'layer' images on the vertual canvas.
The montage was created using my 'gif_anim_montage' to use a checkerboard background and a red outline box.


It is VERY slow, but someone with API knowledge could speed it up enormously. Especially by allowing you to continue the search from the last point found, and to avoid disk IO by using in memory image sequences. A small 'fuzz' factor may also be usfull, especially for JPEG input images.

If you get one please pass it back to me.

This script would be a great script to build in to IM as a general spatial segmentation algorithm, so a C solution could be merged into a "-layers segment" type routine.

Some general improvements in using the script an algorithm, that could be made include...

• Replace background with transparency first, so it is ignored.
• Trim the output in to smaller image layers with (virtual offsets). (See above results)
• expand 'neighbor hood' to connect diagonal, connected regions.
• blur-threshold original image to generate segment mask areas allowing 'nearby' segments to join together into one segment. The segmented mask images can then extract the original segments from the original image (using two image list composition -layers composite)

Please try it and let me know what you think and any and all improvements you can make to it.

[fmw42]

This works (manually picking the floodfill point in the "nine".

convert nine.png -fill red -draw "color 75,90 floodfill" -fill white +opaque red -fill black -opaque red nine_test.png

But interestingly:

This works to make the nine red:

convert nine.png -fill red -draw "color 75,90 floodfill" nine_red1.png

But this does not:

convert nine.png -fill red -floodfill +75x+90 black nine_red2.png


Is -floodfill working or am I using it wrong?

Also why should it need to know that the color at 75,90 is black? Why can it not find that by itself like -draw does?

[yyyy273]

[*]Replace background with transparency first, so it is ignored.

convert input.bmp bgnd.png \
-compose ChangeMask -composite newinput.png

could be used in my case because I have a known background. For an IM function implementation you could specify for a known background.

[*]Trim the output in to smaller image layers with (virtual offsets). (See above results)

Could you use -trim +repage?

Also, could you clarify what

sed '1d; / 0)/d; s/:.*//; q'`

from your script does?


Thanks so much for all your help

[el_supremo]

See this thread:
viewtopic.php?f=1&t=10889&hilit=blob+count

I've modified (and corrected) the code I posted in that thread so that it also finds
the largest black blob. It then floodfills that blob with red and saves the new image.

Pete

Code: Select all

#define WIN32_LEAN_AND_MEAN		// Exclude rarely-used stuff from Windows headers
// Windows Header Files:
#include <windows.h>
#include <tchar.h>

#include <wand/MagickWand.h>

// It appears that, for a queue, the worst case memory requirement is 2*height bytes
// whereas for a stack it is on the order of width*height/3 bytes

// To prepare a photo you can usually just change its number of colours to 2
// which reduces the image to black and white. Then use a white paint brush
// to paint over the black areas (such as buildings) which aren't birds. 
// Then save the file as GIF or PNG - but NOT jpg or other lossy compression.

#define MARKED 127
struct queue {
   int y;
   int x;
};
struct queue *queue,*top, *bottom;

int this_count,this_x,this_y,last_count,last_x,last_y;

// This allocates 3*height bytes for the queue and allows the amount
// to be changed easily
#define QUEUE_WIDTH 3
// A macro to add a pixel to the queue if it is within the bounds of the
// image and is black, in which case the pixel is MARKED so that its neighbours
// can't add it again
#define addq(yy,xx) \
	this_count++;\
   if((yy) >= 0 && (yy) < height && (xx) >= 0 && (xx) < width) {\
      if(*(mi + (yy)*width + (xx)) == 0) {\
         top->y = (yy);\
         top++->x = (xx);\
         *(mi + (yy)*width + (xx)) = MARKED;\
         if(top >= queue + ((QUEUE_WIDTH)*height)) {\
            top = queue;\
         }\
         if(top == bottom) {\
            MessageBox(NULL,"Queue Overflow","",MB_OK);\
            return -1;\
         }\
      }\
   }

// Returns -1 on error or a count of the birds (black blobs) in the image.
// If black_count is not NULL, the number of black pixels in the image is returned
// It also finds the largest blob and leaves it size and the x,y coordinate of
// one of its pixels in global variables
int MagickBirdCount(MagickWand *m_wand,int *black_count)
{
   register unsigned char *p;
   register int i,j;
   int height,width,birdcount;
   int x,y;
   int bcount;
   unsigned char *mi = NULL;

   if(m_wand == NULL)return -1;
   height = MagickGetImageHeight(m_wand);
   width = MagickGetImageWidth(m_wand);
   if(height*width < 1)return -1;

   if(MagickGetImageDepth(m_wand) != 8) {
      MessageBox(NULL,"Image depth is not eight bits","",MB_OK);
      return -1;
   }
   // Allocate space for the queue
   queue = (struct queue *)AcquireMagickMemory(height*(QUEUE_WIDTH)*sizeof(struct queue));
   if(queue == NULL) {
      MessageBox(NULL,"AcquireMagickMemory failed to allocate the queue","",MB_OK);
      return -1;
   }

   // Allocate space for the image
   mi = AcquireMagickMemory(height*width);
   if(mi == NULL) {
      MessageBox(NULL,"AcquireMagickMemory failed to allocate image memory","",MB_OK);
      RelinquishMagickMemory(queue);
      return -1;
   }
   // and read it into the new array
   if(!MagickGetImagePixels(m_wand,0,0,width,height,"R",CharPixel,mi)) {
      MessageBox(NULL,"MagickGetImagePixels failed","",MB_OK);
      RelinquishMagickMemory(queue);
      RelinquishMagickMemory(mi);
      return -1;
   }

   // The process is to scan the image until a black pixel is found, add
   // it to the queue and count it as a bird.
   // Then take a pixel off the queue and add back to the queue any of its neighbouring
   // pixels which are black. Repeat this until the queue is empty.
   // Then scan for the next black pixel and repeat until all pixels have been examined
   p = mi;
   birdcount = bcount = 0;

   for(j=0;j<height;j++) {
      for(i=0;i<width;i++,p++) {
         if(*p != 255)bcount++;
         // Skip anything except black
         if(*p)continue;
         // Found a black pixel - count it as a bird
         birdcount++;
         this_count = 0;
         this_y = j;
         this_x = i;
         top = bottom = queue;
         // Add this pixel to the queue
         addq(j,i);
         // Now find and mark all neighbouring pixels which are also black
         while(top != bottom) {
            // Get the next element from the bottom of the queue
            y = bottom->y;
            x = bottom->x;
            bottom++;
            if(top == bottom)top = bottom = queue;
            else if(bottom >= queue + ((QUEUE_WIDTH)*height)) {
               bottom = queue;
            }
            // Now add all the neighbours of this element to the queue
            addq(y-1,x-1);
            addq(y-1,x);
            addq(y-1,x+1);
            addq(y,x-1);
            addq(y,x+1);
            addq(y+1,x-1);
            addq(y+1,x);
            addq(y+1,x+1);
         }
         if(this_count > last_count) {
            last_count = this_count;
            last_y = this_y;
            last_x = this_x;
         }
      }
   }
   if(black_count)*black_count = bcount;
   RelinquishMagickMemory(mi);
   RelinquishMagickMemory(queue);
   return birdcount;
}

int APIENTRY _tWinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPTSTR    lpCmdLine,
                     int       nCmdShow)
{

	MagickWand *m_wand = NULL;
	PixelWand *p_wand = NULL;
	extern int last_count,last_x,last_y;


	MagickWandGenesis();

	m_wand = NewMagickWand();

	if(!MagickReadImage(m_wand,"48879665cd8.png")) {
		MessageBox(NULL,"ReadImage failed","",MB_OK);
		m_wand = DestroyMagickWand(m_wand);
		MagickWandTerminus();
		return 0;
	}

	// This finds the largest blob
	if(MagickBirdCount(m_wand,NULL) == -1) {
		if(m_wand)m_wand = DestroyMagickWand(m_wand);
		if(p_wand)p_wand = DestroyPixelWand(p_wand);
		MagickWandTerminus();
		MessageBox(NULL,"MagickBirdCount failed to find any blobs","",MB_OK);
		return -1;
	}
	// and this flood fills the largest blob with red
	p_wand = NewPixelWand();
	PixelSetColor(p_wand,"red");
	MagickFloodfillPaintImage(m_wand,AllChannels,p_wand,0,NULL,last_x,last_y,MagickFalse);

	// Save the modified image
	MagickWriteImage(m_wand,"blob.gif");

	if(m_wand)m_wand = DestroyMagickWand(m_wand);
	if(p_wand)p_wand = DestroyPixelWand(p_wand);
	
	MagickWandTerminus();

	return 0;
}

[anthony]

Also, could you clarify what

Code: Select all

sed '1d; / 0)/d; s/:.*//; q'`

from your script does?

I needed to find the FIRST non-transparent pixel in the image, which is the next segment to find in the image. Remember that segments that have been found are flood-filled with transparency
to remove them.

The sed script does a text search of the 'txt:' enumerated pixel image format. Then...
1d; just junk the first line, or the header
/ 0)/d; if this string is present pixel is fully-transparent, junk the whole line, (and start again with the next line)
At this point we either have nothing (EOF) or we have found the non-transparent pixel, so....
s/:.*//; Junk anything following the ':' which is color info
q Print the line (default 'sed' action) and then quit!

Basically just return the first non-transparent pixel.

NOTE: I search for ' 0)' rather than something else like 'none'
as pixels may be transparent, and not the color 'none' which represents fully-transparent black!

So the loop is.

• find first non-transparent pixel
• flood fill that pixel to transparency and save into a new image
• use new image to mask previous image to return the segment that was found and print it to the output pipeline (regardless of what color or 'fuzz' was used)
• move new image into old image before looping.

Outside the loop, the images found are concatenated (a multi-image MIFF file format, is just a concatenation!), and then save it to the given file name.

The output can be a multi-image format like GIF, or separate files like PNG or JPEG. User can add a '%02d' in the filename for multiple images, just as in normal IM commands.

For example....

Code: Select all

   segment_image  input.png  gif:- |\
       convert gif:- -layers CompareOverlay segments.gif

or multiple transparent images...

Code: Select all

  segment_image  input.png  segment_%02d.png

or flattened to create 'blue screen' JPEG images...

Code: Select all

  segment_image  input.png miff:- |\
    convert miff:- -bordercolor blue -border 0x0 segment_%02d.jpg

Pipe input works too. for example - remove background first...

Code: Select all

   convert input.png -transparent white miff:- |\
      segment_image - segment_%02d.png

I always try to ensure my scripts are 'pipe' friendly like this, and as I describe in Hints for Better Scripts

Now if we can get a C equivalent, we can build this into IM, for speed, and so all pre and post operations in the same command!

[anthony]

I have replaced the -compose DstOut -composite on individual image pairs, with 'do all in one go' -layers OptimizeTransparency operation in the final command. This will not help the speed for 'C' code though.

[anthony]

See this thread:
viewtopic.php?f=1&t=10889&hilit=blob+count

I've modified (and corrected) the code I posted in that thread so that it also finds
the largest black blob. It then floodfills that blob with red and saves the new image.

Pete

Interesting program and while it solves the problem, it is not very general.

Perhaps you can have a go at converting my shell script to MagickCore so as to generate a image list of segments, and give IM a much needed segmentation operator, for all API's.

[imagetester]

See this thread:
viewtopic.php?f=1&t=10889&hilit=blob+count

I've modified (and corrected) the code I posted in that thread so that it also finds
the largest black blob. It then floodfills that blob with red and saves the new image.

You 've got an error: error C2440: '=' : cannot convert from 'void *' to 'unsigned char *'

mi = AcquireMagickMemory(height*width);

[el_supremo]

I'm using MSVC 7 and it doesn't even give a warning for that statement.

Does a cast make any difference?

mi = (unsigned char *)AcquireMagickMemory(height*width);

Pete

[imagetester]

I'm using MSVC 7 and it doesn't even give a warning for that statement.

Does a cast make any difference?

mi = (unsigned char *)AcquireMagickMemory(height*width);

Pete

Yes the cast solve it!

But still the program is slow, taking approx 10 sec which is enormous if we have thousands of pics.

Any improvement ?!