/* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % SSSSS EEEEE GGGG M M EEEEE N N TTTTT % % SS E G MM MM E NN N T % % SSS EEE G GGG M M M EEE N N N T % % SS E G G M M E N NN T % % SSSSS EEEEE GGGG M M EEEEE N N T % % % % % % Segment an Image with Thresholding and the Fuzzy c-Means Technique. % % % % % % % % Software Design % % John Cristy % % April 1993 % % % % % % Copyright 1995 E. I. Dupont de Nemours and Company % % % % Permission to use, copy, modify, distribute, and sell this software and % % its documentation for any purpose is hereby granted without fee, % % provided that the above Copyright notice appear in all copies and that % % both that Copyright notice and this permission notice appear in % % supporting documentation, and that the name of E. I. Dupont de Nemours % % and Company not be used in advertising or publicity pertaining to % % distribution of the software without specific, written prior % % permission. E. I. Dupont de Nemours and Company makes no representations % % about the suitability of this software for any purpose. It is provided % % "as is" without express or implied warranty. % % % % E. I. Dupont de Nemours and Company disclaims all warranties with regard % % to this software, including all implied warranties of merchantability % % and fitness, in no event shall E. I. Dupont de Nemours and Company be % % liable for any special, indirect or consequential damages or any % % damages whatsoever resulting from loss of use, data or profits, whether % % in an action of contract, negligence or other tortuous action, arising % % out of or in connection with the use or performance of this software. % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Segment segments an image by analyzing the histograms of the color % components and identifying units that are homogeneous with the fuzzy % c-means technique. The scale-space filter analyzes the histograms of % the three color components of the image and identifies a set of classes. % The extents of each class is used to coarsely segment the image with % thresholding. The color associated with each class is determined by % the mean color of all pixels within the extents of a particular class. % Finally, any unclassified pixels are assigned to the closest class with % the fuzzy c-means technique. % % The fuzzy c-Means algorithm can be summarized as follows: % % o Build a histogram, one for each color component of the image. % % o For each histogram, successively apply the scale-space % filter and build an interval tree of zero crossings in % the second derivative at each scale. Analyze this % scale-space ``fingerprint'' to determine which peaks and % valleys in the histogram are most predominant. % % o The fingerprint defines intervals on the axis of the % histogram. Each interval contains either a minima or a % maxima in the original signal. If each color component % lies within the maxima interval, that pixel is considered % ``classified'' and is assigned an unique class number. % % o Any pixel that fails to be classified in the above % thresholding pass is classified using the fuzzy % c-Means technique. It is assigned to one of the classes % discovered in the histogram analysis phase. % % The fuzzy c-Means technique attempts to cluster a pixel by finding % the local minima of the generalized within group sum of squared error % objective function. A pixel is assigned to the closest class of which % the fuzzy membership has a maximum value. % % Segment is strongly based on software written by Andy Gallo, University % of Delaware. % % The following reference was used in creating this program: % % Young Won Lim, Sang Uk Lee, "On The Color Image Segmentation Algorithm % Based on the Thresholding and the Fuzzy c-Means Techniques", Pattern % Recognition, Volume 23, Number 9, pages 935-952, 1990. % % The segment program syntax is: % % Usage: segment [options ...] input_file output_file % % Where options include: % -cluster_threshold value % minimum percent of pixels per cluster % -colorspace type GRAY, OHTA, RGB, XYZ, YCbCr, YIQ, YPbPr, or YUV % -comment string annotate image with comment % -compress type RunlengthEncoded or QEncoded % -density geometry vertical and horizontal density of the image % -display server obtain image or font from this X server % -font name X11 font for displaying text % -interlace type NONE, LINE, or PLANE % -label name assign a label to an image % -matte store matte channel if the image has one % -page geometry size and location of the Postscript page % -quality value JPEG quality setting % -smoothing_threshold value % smoothing threshold of second derivative % -scene value image scene number % -size geometry width and height of image % -treedepth value depth of the color classification tree % -verbose print detailed information about the image % % Change '-' to '+' in any option above to reverse its effect. For % example, specify +matte to store the image without its matte channel. % % By default, the image format of `file' is determined by its magic % number. To specify a particular image format, precede the filename % with an image format name and a colon (i.e. ps:image) or specify the % image type as the filename suffix (i.e. image.ps). Specify 'file' as % '-' for standard input or output. % % */ #include "magick.h" #include "image.h" #include "X.h" #include "utility.h" /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % U s a g e % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Procedure Usage displays the program usage; % % The format of the Usage routine is: % % Usage() % % */ static void Usage() { char **p; static char *options[]= { "-cluster_threshold value", " minimum percent of pixels per cluster", "-colorspace type GRAY, OHTA, RGB, XYZ, YCbCr, YIQ, YPbPr, or YUV", "-comment string annotate image with comment", "-compress type RunlengthEncoded or QEncoded", "-density geometry vertical and horizontal density of the image", "-display server obtain image or font from this X server", "-font name X11 font for displaying text", "-interlace type NONE, LINE, or PLANE", "-label name assign a label to an image", "-matte store matte channel if the image has one", "-page geometry size and location of the Postscript page", "-quality value JPEG quality setting", "-smoothing_threshold value", " smoothing threshold of second derivative", "-scene value image scene number", "-size geometry width and height of image", "-treedepth value depth of the color classification tree", "-verbose print detailed information about the image", (char *) NULL }; (void) printf("Version: %s\n\n",Version); (void) printf("Usage: %s [options ...] input_file output_file\n", client_name); (void) printf("\nWhere options include:\n"); for (p=options; *p != (char *) NULL; p++) (void) printf(" %s\n",*p); (void) printf( "\nChange '-' to '+' in any option above to reverse its effect. For\n"); (void) printf( "example, specify +matte to store the image without an matte channel.\n"); (void) printf( "\nBy default, the image format of `file' is determined by its magic\n"); (void) printf( "number. To specify a particular image format, precede the filename\n"); (void) printf( "with an image format name and a colon (i.e. ps:image) or specify the\n"); (void) printf( "image type as the filename suffix (i.e. image.ps). Specify 'file' as\n"); (void) printf("'-' for standard input or output.\n"); exit(1); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % M a i n % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % */ int main(argc,argv) int argc; char *argv[]; { #define NotInitialized (unsigned int) (~0) char *filename, *option; float cluster_threshold, smoothing_threshold; Image *image, *next_image; ImageInfo image_info; int i, status, x; unsigned int colorspace, compression, matte, scene; /* Initialize program variables. */ client_name=argv[0]; if (argc < 3) Usage(); /* Read image and convert to MIFF format. */ cluster_threshold=1.0; colorspace=RGBColorspace; compression=UndefinedCompression; image=(Image *) NULL; GetImageInfo(&image_info); matte=NotInitialized; scene=0; smoothing_threshold=1.5; /* Check command syntax. */ filename=(char *) NULL; for (i=1; i < (argc-1); i++) { option=argv[i]; if (((int) strlen(option) < 2) || ((*option != '-') && (*option != '+'))) { /* Read input image. */ filename=argv[i]; (void) strcpy(image_info.filename,filename); if (image != (Image *) NULL) Error("input image already specified",filename); image=ReadImage(&image_info); if (image == (Image *) NULL) exit(1); } else switch(*(option+1)) { case 'c': { if (strncmp("cluster_threshold",option+1,2) == 0) { cluster_threshold=0.0; if (*option == '-') { i++; if ((i == argc) || !sscanf(argv[i],"%f",(float *) &x)) Error("Missing value on -cluster_threshold",(char *) NULL); } cluster_threshold=atof(argv[i]); break; } if (strncmp("colorspace",option+1,7) == 0) { colorspace=RGBColorspace; if (*option == '-') { i++; if (i == argc) Error("Missing type on -colorspace",(char *) NULL); option=argv[i]; colorspace=UndefinedColorspace; if (Latin1Compare("gray",option) == 0) colorspace=GRAYColorspace; if (Latin1Compare("ohta",option) == 0) colorspace=OHTAColorspace; if (Latin1Compare("rgb",option) == 0) colorspace=RGBColorspace; if (Latin1Compare("xyz",option) == 0) colorspace=XYZColorspace; if (Latin1Compare("ycbcr",option) == 0) colorspace=YCbCrColorspace; if (Latin1Compare("yiq",option) == 0) colorspace=YIQColorspace; if (Latin1Compare("ypbpr",option) == 0) colorspace=YPbPrColorspace; if (Latin1Compare("yuv",option) == 0) colorspace=YUVColorspace; if (colorspace == UndefinedColorspace) Error("Invalid colorspace type on -colorspace",option); } break; } if (strncmp("comment",option+1,4) == 0) { if (*option == '-') { i++; if (i == argc) Error("Missing comment on -comment",(char *) NULL); } break; } if (strncmp("compress",option+1,3) == 0) { compression=NoCompression; if (*option == '-') { i++; if (i == argc) Error("Missing type on -compress",(char *) NULL); option=argv[i]; if (Latin1Compare("runlengthencoded",option) == 0) compression=RunlengthEncodedCompression; else if (Latin1Compare("qencoded",option) == 0) compression=QEncodedCompression; else Error("Invalid compression type on -compress",option); } break; } Error("Unrecognized option",option); break; } case 'd': { if (strncmp("density",option+1,3) == 0) { image_info.density=(char *) NULL; if (*option == '-') { i++; if ((i == argc) || !sscanf(argv[i],"%d",&x)) Error("Missing geometry on -density",(char *) NULL); image_info.density=argv[i]; } break; } if (strncmp("display",option+1,3) == 0) { image_info.server_name=(char *) NULL; if (*option == '-') { i++; if (i == argc) Error("Missing server name on -display",(char *) NULL); image_info.server_name=argv[i]; } break; } Error("Unrecognized option",option); break; } case 'f': { image_info.font=(char *) NULL; if (*option == '-') { i++; if (i == argc) Error("Missing font name on -font",(char *) NULL); image_info.font=argv[i]; } break; } case 'h': { if (strncmp("help",option+1,2) == 0) { Usage(True); break; } Error("Unrecognized option",option); break; } case 'i': { if (strncmp("interlace",option+1,3) == 0) { image_info.interlace=NoneInterlace; if (*option == '-') { i++; if (i == argc) Error("Missing type on -interlace",(char *) NULL); option=argv[i]; image_info.interlace=UndefinedInterlace; if (Latin1Compare("none",option) == 0) image_info.interlace=NoneInterlace; if (Latin1Compare("line",option) == 0) image_info.interlace=LineInterlace; if (Latin1Compare("plane",option) == 0) image_info.interlace=PlaneInterlace; if (image_info.interlace == UndefinedInterlace) Error("Invalid interlace type on -interlace",option); } break; } Error("Unrecognized option",option); break; } case 'l': { if (strncmp("label",option+1,2) == 0) { if (*option == '-') { i++; if (i == argc) Error("Missing label name on -label",(char *) NULL); } break; } Error("Unrecognized option",option); break; } case 'm': { if (strncmp("matte",option+1,5) == 0) { matte=(*option == '-'); break; } Error("Unrecognized option",option); break; } case 'p': { if (strncmp("page",option+1,2) == 0) { image_info.page=(char *) NULL; if (*option == '-') { i++; if (i == argc) Error("Missing page geometry on -page",(char *) NULL); image_info.page=PostscriptGeometry(argv[i]); } break; } Error("Unrecognized option",option); break; } case 'q': { i++; if ((i == argc) || !sscanf(argv[i],"%d",&x)) Error("Missing quality on -quality",(char *) NULL); image_info.quality=atoi(argv[i]); break; } case 's': { if (strncmp("scene",option+1,2) == 0) { scene=0; if (*option == '-') { i++; if ((i == argc) || !sscanf(argv[i],"%d",&x)) Error("Missing value on -scene",(char *) NULL); } scene=atoi(argv[i]); break; } if (strncmp("size",option+1,2) == 0) { image_info.size=(char *) NULL; if (*option == '-') { i++; if ((i == argc) || !sscanf(argv[i],"%d",&x)) Error("Missing geometry on -size",(char *) NULL); image_info.size=argv[i]; } break; } if (strncmp("smoothing_threshold",option+1,2) == 0) { smoothing_threshold=0.0; if (*option == '-') { i++; if ((i == argc) || !sscanf(argv[i],"%f",(float *) &x)) Error("Missing value on -smoothing_threshold", (char *) NULL); } smoothing_threshold=atof(argv[i]); break; } break; } case 'v': { if (strncmp("verbose",option+1,2) == 0) { image_info.verbose=(*option == '-'); break; } Error("Unrecognized option",option); break; } case '?': { Usage(); break; } default: { Error("Unrecognized option",option); break; } } } if (image == (Image *) NULL) Error("Missing an image file name",(char *) NULL); /* Write images. */ do { if (matte != NotInitialized) image->matte=matte; if (compression != UndefinedCompression) image->compression=compression; if (scene != 0) image->scene=scene; (void) strcpy(image->filename,argv[i]); if (image->previous != (Image *) NULL) (void) sprintf(image->filename,"%s.%u",argv[i],image->scene); /* Transmogrify image as defined by the image processing options. */ MogrifyImage(&image_info,argc,argv,&image); /* Reduce the number of colors in the image. */ SegmentImage(image,colorspace,image_info.verbose,smoothing_threshold, cluster_threshold); if (image_info.verbose) QuantizationError(image); SyncImage(image); status=WriteImage(&image_info,image); if (image_info.verbose) DescribeImage(image); next_image=image->next; DestroyImage(image); image=next_image; } while (image != (Image *) NULL); free((char *) image_info.filename); exit(0); return(False); }