image.c

Hausdorff Distance for Image Recognition

/*
 *
 * $Header: /usr/u/wjr/src/ADT/RCS/image.c,v 2.5 1994/07/24 23:32:57 wjr Exp $
 *
 * Copyright (c) 1990, 1991, 1992, 1993 Cornell University.  All Rights
 * Reserved.
 *
 * Copyright (c) 1991, 1992 Xerox Corporation.  All Rights Reserved.
 *  
 * Use, reproduction, preparation of derivative works, and distribution
 * of this software is permitted.  Any copy of this software or of any
 * derivative work must include both the above copyright notices of
 * Cornell University and Xerox Corporation and this paragraph.  Any
 * distribution of this software or derivative works must comply with all
 * applicable United States export control laws.  This software is made
 * available AS IS, and XEROX CORPORATION DISCLAIMS ALL WARRANTIES,
 * EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE,
 * AND NOTWITHSTANDING ANY OTHER PROVISION CONTAINED HEREIN, ANY
 * LIABILITY FOR DAMAGES RESULTING FROM THE SOFTWARE OR ITS USE IS
 * EXPRESSLY DISCLAIMED, WHETHER ARISING IN CONTRACT, TORT (INCLUDING
 * NEGLIGENCE) OR STRICT LIABILITY, EVEN IF XEROX CORPORATION IS ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGES.
 */

static char rcsid[] = "@(#)$Header: /usr/u/wjr/src/ADT/RCS/image.c,v 2.5 1994/07/24 23:32:57 wjr Exp $";

/*
 *	image.c - Images.
 *
 * An image is just a rectangular array of some type (several types are
 * implemented here).
 *
 * Exports:
 *	type struct { unsigned char r, g, b } RGB
 *
 *	type ImageType
 *
 *	type GrayImage
 *	type FloatImage
 *	type RGBImage
 *	type DoubleImage
 *	type BinaryImage
 *	type LongImage
 *	type PtrImage
 *	type ShortImage
 *
 *	type GrayPixPtr
 *	type FloatPixPtr
 *	type RGBPixPtr
 *	type DoublePixPtr
 *	type BinaryPixPtr
 *	type LongPixPtr
 *	type PtrPixPtr
 *	type ShortPixPtr
 *
 *	constant ImageType IMAGE_GRAY
 *	constant ImageType IMAGE_FLOAT
 *	constant ImageType IMAGE_RGB
 *	constant ImageType IMAGE_DOUBLE
 *	constant ImageType IMAGE_BINARY
 *	constant ImageType IMAGE_LONG
 *	constant ImageType IMAGE_PTR
 *	constant ImageType IMAGE_SHORT
 *
 *	constant int COLRNG
 *
 *	void *imNew(ImageType type, unsigned width, unsigned height) - create
 *		a new image of the appropriate type. The pointer returned
 *		will be a GrayImage, FloatImage, RGBImage, DoubleImage, 
 *		BinaryImage or WhateverelseImage as appropriate.
 *
 *	void *imNewOffset(ImageType type, unsigned width, unsigned height,
 *			  int xbase, int ybase) - create a new image of
 *		the appropriate type whose addressing begins
 *		at (xbase, ybase).
 *		imNew is equivalent to xbase = ybase = 0.
 *
 *	void imFree(void *im) - free an image.
 *
 *	void imSetOffset(void *im, int newxbase, int newybase) - modify
 *		an image so that its addressing begins at
 *		(newxbase, newybase).
 *
 *	void *imLoad(ImageType type, char *filename) - load an image from
 *		a file. The pointer returned will be of the appropriate
 *		type. Its base will be (0,0).
 *
 *	void *imLoadF(ImageType type, FILE *inFile) - load an image
 *		from a stream. The pointer returned will be of the
 *		appropriate type.
 *
 *	int imSave(void *im, char *filename) - save an image into a file.
 *
 *	int imSaveF(void *im, FILE *outFile) - save an image to a stream.
 *
 *	void *imDup(void *im) - duplicate an image
 *
 *	void *imPromote(void *im, ImageType promoteto) - promote an image to
 *		some higher type.
 *
 *	void imSetPromotion(ImageType promotefrom, ImageType promoteto,
 *			    double slope, double offset) - change the method
 *		of image promotion.
 *
 *	void *imDemote(void *im, ImageType demoteto) - demote an image to some
 *		lower type.
 *
 *	void *imConvert(void *im, ImageType convertto) - convert (promote
 *		or demote as appropriate) an image to some other type.
 *
 *	unsigned imGetWidth(void *im) - get the width of an image.
 *
 *	unsigned imGetHeight(void *im) - get the height of an image.
 *
 *	int imGetXBase(void *im) - get the x-base of an image.
 *
 *	int imGetYBase(void *im) - get the y-base of an image.
 *
 *	int imGetXMax(void *im) - get the maximum valid X value of an image.
 *
 *	int imGetYMax(void *im) - get the maximum valid Y value of an image.
 *
 *	ImageType imGetType(void *im) - get the type of an image.
 *
 *	char *imGetComment(void *im) - get the comment attached to an image.
 *
 *	boolean imSetComment(void *im, char *comment) - set the comment
 *		attached to an image.
 *
 *	macro imRef(void *im, int x, int y) - access an element
 *		of some form of Image.
 *
 *	macro imGetPixPtr(void *im, int x, int y) - get a handle on a pixel of
 *		some form of Image.
 *
 *	macro imPtrRef(void *im, *PixPtr) - dereference a PixPtr of some type.
 *
 *	macro imPtrDup(void *im, *PixPtr) - duplicate a PixPtr of some type.
 *
 *	void imPtrUp(void *im, *PixPtr) - move a PixPtr up in the image.
 *
 *	void imPtrDown(void *im, *PixPtr) - move a PixPtr down in the image.
 *
 *	void imPtrLeft(void *im, *PixPtr) - move a PixPtr left in the image.
 *
 *	void imPtrRight(void *im, *PixPtr) - move a PixPtr right in the image.
 *
 *	boolean imPtrEq(void *im, *PixPtr1, *PixPtr2) - check two PixPtrs
 *		for equality.
 *
 * An image is a rectangular storage area, with each cell being of some
 * type. In this case, the types are unsigned char, float, RGB, double,
 * binary, long, void * and short. Float is large enough for most purposes for
 * image processing; for those for which it is not, DoubleImage is provided;
 * the space costs are much higher for this, so it should be avoided unless
 * necessary. Binary images can store 0 or 1 in each location. By convention,
 * 0 is white and 1 is black in binary images.
 * PtrImages can store a void * pointer at each location. These images may
 * not be saved or loaded.
 * COLRNG is the number of discrete gray levels in a GrayImage, and the number
 * of levels in each component of an RGBImage. COLRNG-1 is the brightest
 * (most white) GrayImage value.
 *
 * N.B. Older versions of this datatype had a different definition for RGB,
 * namely:
 *	typedef unsigned char RGB[3];
 * Due to C's weirdness with arrays, this proved troublesome, so the new
 * definition was installed. However, since some code relies on the old
 * definition, a backwards compatibility mode is available. To get it,
 * #define IMAGE_OLD_RGB
 * before including image.h.
 *
 * imNew creates an Image of the given size, of the appropriate type,
 *	returning (void *)NULL on failure. The Image returned
 *	contains all zeros. The return value should be cast to
 *	the appropriate type.
 *
 * imNewOffset creates an image of the given size, of the appropriate type,
 *	returning (void *)NULL on failure. The valid range of addresses
 *	for the new image is (xbase..xbase+width-1, ybase..ybase+height-1).
 *	Addressing an image with a shifted base may be more efficient than
 *	performing the base shift for each access.
 *
 * imFree frees the given Image.
 *
 * imSetOffset modifies the given image so that its range of addresses
 *	is (newxbase..newxbase+width-1, newybase..newybase+height-1).
 *	The image data is not changed. The pixel which was previously
 *	addressed as imRef(im, imGetXBase(im), imGetYBase(im)) will now
 *	be addressed as imRef(im, newxbase, newybase). imGetXBase(im) and
 *	imGetYBase(im) will be updated to newxbase and newybase.
 *
 * imLoad attempts to load an Image from a file. It checks to see that
 *	what is stored in the file has the appropriate type, and if not
 *	returns NULL. It then attempts to load the image from the file,
 *	and if successful returns the (.*)Image as appropriate. If it
 *	fails, it returns NULL. The base of the loaded image is (0,0),
 *	regardless of what it was when it was saved. The file is closed in
 *	all cases.
 *	If the file does not contain an image of the appropriate type, but
 *	does contain an image of a type which may be promoted to that type
 *	(for example, if it contains a BinaryImage and imLoad is attempting
 *	to load a GrayImage), the image will be read and silently promoted
 *	to the requested type (see imPromote). If such a promotion is not
 *	possible, NULL is returned.
 *	Any comments present in the original file are read in and stored
 *	as the comment associated with the image (see imGetComment).
 *	If more than one comment line was present in the file, then the
 *	contents of the lines will be separated by newlines. There is no
 *	trailing newline; thus, the image read from a file with a single
 *	comment line will contain the contents of that line with no extra
 *	newline. There is a maximum limit on the amount of comments which
 *	will be read from a file of 8192 bytes (including newlines).
 *
 * imLoadF attempts to load an Image from a stdio stream. It performs the
 *	same operations as imLoad, except that it assumes the stream is
 *	open and correctly positioned. After loading, the stream is positioned
 *	to just after the image; it is not closed. If the image cannot be
 *	loaded (i.e. if NULL is returned), the position of the stream (and
 *	what has been written to it) is undefined.
 *
 * imSave attempts to write the given Image out to a file. If successful,
 *	it returns 0. If it fails, it returns -1. Files written by imSave
 *	from IMAGE_FLOAT, IMAGE_DOUBLE, IMAGE_LONG and IMAGE_SHORT images
 *	can only be re-read on same type of machine as they were written,
 *	unless two different machines happen to share a floating point format,
 *	endianness, and	alignment restrictions. Luckily, this is often
 *	the case. It also writes out the comment associated with the image
 *	as a comment in the file. The rules for this are:
 *	- Every newline in the comment string causes a new comment line to
 *	  be begun in the file.
 *	- If any line would be longer than 70 characters, it is broken up.
 *	  If possible, it will be broken at a whitespace character.
 *	If imSave fails (returns -1), the contents of the file are
 *	undefined.
 *
 * imSaveF performs the same function as imSave, except that it writes
 *	to a previously-opened stream. After the save, the stream
 *	is positioned after the newly-written data.
 *
 * imDup makes an exact duplicate of an Image - another Image having
 *	the same size, type and offsets, the same image data, and the same
 *	comment. It returns (void *)NULL if it cannot create the duplicate.
 *
 * imPromote converts an image to a "higher" type of image. The arguments are
 *	the image to be converted and the type into which it should be
 *	converted. It returns (void *)NULL if it cannot create the new image.
 *	Only certain types of conversions are possible with this routine.
 *	They are:
 *	BinaryImages can be promoted to:
 *		GrayImage, ShortImage, LongImage, FloatImage, DoubleImage,
 *		RGBImage
 *	GrayImages can be promoted to:
 *		ShortImage, LongImage, FloatImage, DoubleImage, RGBImage
 *	ShortImages can be promoted to:
 *		LongImage, FloatImage, DoubleImage
 *	LongImages can be promoted to:
 *		DoubleImage
 *	FloatImages can be promoted to:
 *		DoubleImage
 *	The rules of the conversions are:
 *	BinaryImage->GrayImage, ShortImage, LongImage:	(1-COLRNG,COLRNG-1)
 *		0 maps to COLRNG - 1
 *		1 maps to 0
 *	BinaryImage->FloatImage, DoubleImage:		(1,0)
 *		0 maps to 0
 *		1 maps to 1
 *	BinaryImage->RGBImage:				(1-COLRNG,COLRNG-1)
 *		0 maps to {COLRNG-1, COLRNG-1, COLRNG-1}
 *		1 maps to {0, 0, 0}
 *	GrayImage->ShortImage, LongImage, FloatImage, DoubleImage: (1,0)
 *		a pixel with value v in the original image has value v
 *		in the converted image. (i.e. v maps to v)
 *	GrayImage->RGBImage:				(1,0)
 *		v maps to {v, v, v}
 *	ShortImage->LongImage, FloatImage, DoubleImage:	(1,0)
 *		v maps to v
 *	LongImage->DoubleImage:				(1,0)
 *		v maps to v
 *	FloatImage->DoubleImage:			(1,0)
 *		v maps to v
 *	The meaning of the numbers in parentheses are: if a conversion
 *	is labelled (a,b), then a pixel with input value v will be mapped
 *	to av+b. These values are the default ones; they may be changed at
 *	any time with imSetPromotion. Note that these default values are not
 *	transitive: promoting (for example) a BinaryImage to a GrayImage then
 *	to a FloatImage will give different results than promoting the
 *	BinaryImage directly to a FloatImage.
 *	When converting to an RGBImage, all three components are set to the
 *	same value.
 *	These conversions are all those which are strictly "promotions": no
 *	information is lost during the conversion.
 *
 * imSetPromotion alters the parameters of one of the promotions. The
 *	"promotefrom" and "promoteto" ImageTypes must correspond to a
 *	valid promotion. The slope and offset parameters will then be used
 *	for all future promotions from images of type "promotefrom" to images
 *	of type "promoteto". This includes the implicit promotions performed
 *	by imLoad and imLoadF.
 *
 * imDemote converts an Image to an Image of lower type. The conversions
 *	which this routine may perform are:
 *	DoubleImages can be demoted to:
 *		BinaryImage, GrayImage, ShortImage, LongImage, FloatImage,
 *		RGBImage
 *	FloatImages can be demoted to:
 *		BinaryImage, GrayImage, ShortImage, LongImage, RGBImage
 *	LongImages can be demoted to:
 *		BinaryImage, GrayImage, ShortImage, FloatImage, RGBImage
 *	ShortImages can be demoted to:
 *		BinaryImage, GrayImage, RGBImage
 *	GrayImages can be demoted to:
 *		BinaryImage
 *	RGBImages can be demoted to:
 *		BinaryImage, GrayImage, ShortImage, LongImage, FloatImage,
 *		DoubleImage
 *	All these conversions have the property that information may be lost.
 *	Note that some conversions may lose information in both directions
 *	(for example DoubleImage<->RGBImage).
 *	The rules of the conversions are:
 *	DoubleImage->FloatImage:
 *		v maps to v, if v lies in the range of floats
 *		undefined if v does not
 *	DoubleImage->LongImage, ShortImage, GrayImage:
 *		v maps to floor(v) if floor(v) is representable in the
 *		destination
 *		undefined if floor(v) is not
 *	DoubleImage->BinaryImage:
 *		0 maps to 0
 *		non-zero maps to 1
 *	DoubleImage->RGBImage
 *		v maps to {floor(v), floor(v), floor(v)} if floor(v) is
 *		representable in the destination
 *		undefined if floor(v) is not
 *	FloatImage->LongImage, ShortImage, GrayImage:
 *		v maps to floor(v) if floor(v) is representable in the
 *		destination
 *		undefined if floor(v) is not
 *	FloatImage->BinaryImage:
 *		0 maps to 0
 *		non-zero maps to 1
 *	FloatImage->RGBImage
 *		v maps to {floor(v), floor(v), floor(v)} if floor(v) is
 *		representable in the destination
 *		undefined if floor(v) is not
 *	LongImage->ShortImage, GrayImage
 *		v maps to v if v is representable in the destination
 *		undefined if v is not
 *	LongImage->FloatImage
 *		v maps to v (note that accuracy may be lost)
 *	LongImage->BinaryImage
 *		0 maps to 1
 *		non-zero maps to 0
 *	LongImage->RGBImage
 *		v maps to {v, v, v} if v is representable in the destination
 *		undefined if v is not
 *	ShortImage->GrayImage
 *		v maps to v if v is representable in the destination
 *		undefined if v is not
 *	ShortImage->BinaryImage
 *		0 maps to 1
 *		non-zero maps to 0
 *	ShortImage->RGBImage
 *		v maps to {v, v, v} if v is representable in the destination
 *		undefined if v is not
 *	GrayImage->BinaryImage
 *		0 maps to 1
 *		non-zero maps to 0
 *	RGBImage->BinaryImage
 *		If all components are zero, then 1
 *		0 otherwise
 *	RGBImage->anything else
 *		The R, G and B components are first combined by
 *		v = .299R + .587G + .114B
 *		The resulting value is then assigned to the new image pixel.
 *	These conversions are as closely as possibly the inverses of the
 *	conversion routines used by imPromote (i.e. a promotion followed by a
 *	demotion will give the original image back). Note that this makes them
 *	non-transitive, and that there are some conversions which are
 *	demotions in both directions. None of these conversions may be
 *	altered; if another type of conversion is desired, a special routine
 *	may be written.
 *
 * imConvert converts (promotes or demotes) an image to an image of another
 *	type. Any two types of image may be converted between, except for
 *	PtrImages. This routine is a convenience routine which calls
 *	imPromote or imDemote as necessary. As a special case,
 *	converting an image to its original type has the same effect as
 *	imDup EXCEPT that the comment is not copied (no other conversion copies
 *	the comment, so this behaviour is consistent). Note that this form of
 *	conversion is neither a promotion nor a demotion, and so will be
 *	rejected by both imPromote and imDemote.
 *
 * imGetWidth returns the width of the given Image.
 *
 * imGetHeight returns the height of the given Image.
 *
 * imGetXBase returns the X base of the given Image. This is the lowest
 *	valid X value.
 *
 * imGetYBase returns the Y base of the given Image. This is the lowest
 *	valid Y value.
 *
 * imGetXMax returns the highest valid X value of an Image. This is equal to
 *	imGetXBase(im)+imGetWidth(im)-1.
 *
 * imGetYMax returns the highest valid Y value of an Image. This is equal to
 *	imGetYBase(im)+imGetHeight(im)-1.
 *
 * imGetType returns the ImageType of the given Image.
 *
 * imGetComment returns the comment associated with the Image, or NULL if
 *	there is none. This is the comment which was present in the file
 *	from which the image was loaded, if any, or a comment associated
 *	with the image later using imSetComment. Note that the memory
 *	pointed at by this pointer is owned by the Image module, and should
 *	not be freed; it will remain valid until the Image is freed, or the
 *	comment is changed.
 *
 * imSetComment assigns the given string as the comment of the given Image.
 *	It returns TRUE if it is successful, FALSE if it is not. It makes
 *	a copy of the string; the original string is not referred to after
 *	this, and may be freed or altered without affecting the Image's
 *	comment. You can pass in NULL as the new comment. If the comment
 *	could not be changed (i.e. FALSE is returned), then the old comment
 *	remains.
 *
 * imRef gives access to an entry in an Image of some form (it works
 *	for all defined forms of Image). It gives an lvalue: it is valid
 *	to say imRef(i, x, y) = foo;
 *
 * The PixPtr types allow efficient access to contiguous regions of an Image.
 * You get a PixPtr by calling imGetPixPtr, giving the location in the image
 * you would like a handle on. You can then dereference this using
 * imPtrRef. imRef(im, x, y) gives the same value as
 * imPtrRef(imGetPixPtr(im, x, y)); note that this is an lvalue and may be
 * assigned to.
 * The advantage of PixPtrs is that they can be efficiently moved through
 * the image array. For example, if im is a GrayImage:
 * for (x = 0; x < w; x++) {
 *     imRef(im, x, y) = 123;
 *     }
 * can be replaced by:
 * GrayPixPtr pp;
 * pp = imGetPixPtr(im, 0, y);
 * for (x = 0; x < w; x++) {
 *     imPtrRef(im, pp) = 123;
 *     imPtrRight(im, pp);
 *     }
 * which may run more efficiently.
 *
 * imGetPixPtr gets a handle on the (x,y) pixel in the image im, giving a
 *	PixPtr of the appropriate type.
 *
 * imPtrRef dereferences a PixPtr of some type, giving an lvalue of the
 *	appropriate type.
 *
 * imPtrDup duplicates a PixPtr of some type, returning a PixPtr of the same
 *	type, initially referring to the same location in the image.
 *
 * imPtrUp, imPtrDown, imPtrLeft and imPtrRight move a PixPtr through an
 *	Image. imPtrUp effectively decrements the y component of the pixel