OGIS PROJECT DOCUMENT 95-008
TITLE: 	Reference Systems
PRIMARY AUTHOR: 
		Name:	Ron Lake
Address:	MacDonald Dettwiler Ltd
		Phone:	+1 604 278 3411
		FAX:		+1 604 278 2936
		Electronic mail:	lake@mda.ca
SECONDARY AUTHOR(S):
		Name:	
		Name:	
DATE:	 September 1994
STATUS:	Proposal
1.	References
[1]	Buehler, Kurt (1994) OGIS Project Document 94-002, Vision, Goals and Requirements.
[2]	Buehler, Kurt (1994) OGIS Project Document 94-003R2 Technical Committee Concept of Operations.
[3]	Louis Auslander, Differential Geomety,  Harper's Series in Modern Mathematics, Harper and Row, New York, 1967.
[4]	Bernard Schutz, Geometrical Methods of Mathematical Physics ,  Cambridge University Press, 1987.
[5]	Brickell F. and Clark R.S., Differential Manifolds     Van Nostrand Reinhold Co., London, 1970.
[6]	DeRose Tony 	"Coordinate Free Geometric Programming", Lecture Notes, SIGGRAPH 91

2.0	Mathematical Background

This section provides the mathematical background for the material in this paper.  In this release it is restricted to the support for the base types and for the affine space and vector space types. Subsequent releases will provide similar support for parametric surfaces, vector and fibre bundles.

2.1	General Notion of a Reference System

A reference system is a means of assigning numeric values to a location or other quantity.  In the most general sense a reference system is a measurement scale and can include both ordinal and cardinal scales.  For the purposes of this note we will restrict the notion of a reference system to a cardinal scale with values in a real vector space.  A reference system is thus a mapping which carries points in some abstract space to tuples in a real valued coordinate vector space.

Our current approach thus does not include reference systems which are based on qualitative associations, nor on topological ones ( "to get to my house take route #7, turn left at highway blvd and go up the hill, i'm the first house on the right").

2.1	Vector Spaces

A Vector Space is a simple structure which can be used as a basis of a reference system. Points in a vector space can be given coordinates by choosing a basis in the vector space.

Let V be a vector space over a R (real numbers) and let V1...Vn be a basis (we will usually be interested in orthonormal bases, but this is not required).  Then a vector v can be written as:

				v = SaiVi

The real numbers (ai) are the coordinates of v.

A basis can thus be said to be a reference system for V.  Note that all vectors v are assumed to be attached at a unique point called the origin.  There are no "free" vectors in a vector space.

Transformations of vector spaces are called linear maps.  A linear map can be expressed as a matrix given a choice of basis for the domain and range vector spaces.  A linear map is define completely by its action on a basis.

2.2	Affine Spaces

An Affine Space corresponds directly to our common sense notion of space.  Vectors as directed line segments can be defined in an affine space as the difference of two affine points.  In fact we can define an affine space in a natural way relative to a vector space as:

An Affine Space is a set S, and vector space V, together with a map (called a difference map) d, d:S x S----> V which satisfies

1.	d(P,Q) + d(Q,R) = d(P,R)  where P,Q,R are elements of S.

A point in an affine space can be given coordinates by choosing a frame in the affine space.  An orthonormal frame consists of a choice of basis for the vector space "attached" at a given point of the affine space. Note that all such spaces are isomorphic to one another.

Transformations of affine spaces are called affine maps. An affine map can be expressed as a translation plus a non-singular linear map.  This can be seen easily in terms of two vector spaces attached at different points of the affine space.  The translation part carries vectors from one location to the other, while the linear map, maps from the basis (frame) at one location to the basis(frame) at the other.  Affine maps on R^3 can be represented as 4 x 4 matrices as follows: 

Given 

		Let Ta(x) = x + a  (translation)

		Let R:V ---> V be a linear map

An affine map A can be represented as:

			A(x) = RoTa(x)

We can write A as a 4 x 4 matrix via

		|  a11 a12 a13 a1 |	where the aij is the matrix of the
		|  a21 a22 a23 a2 |	3d linear map and the ai are the
		|  a31 a32 a33 a3 |	elements of the translation.
		|  0     0    0      1   |

3.0	Abstract Types for Reference Systems

3.1	Base Types

This section outlines the base types which form the foundation of the OGM Spatial Referencing Model.  These base types conform to the weakly typed view of spatial referencing and place little or no constraints on the implementer.  More specific types are derived from these base types based on mathematical constructs.  These derived types model the deeper semantics of spatial reference systems are intended to form the basis of public reference systems which various information communities will implement.

The following base types are part of the OGM Spatial Reference Model:

	Space

	Point

	SpatialReference

		CoordinateTuple
	
	SpatialReferenceDictionary

	SpatialReferenceTransformation
	
	SpaceDictionary

	SpatialReferenceTransformationDictionary

	SpatialTransformation

The informal motivation for these base types is as follows.

A Space is essentially just a point set, although as a base type it does not have any set behaviour.  Typical Spaces include 

	The surface of the earth
	The inertial space of the earth
	A photograph
	A sensor imaging plane
	A land parcel
	A country

Spaces are typically, although not necessarily infinite point sets.

A SpatialReference is a mapping from a Space to a coordinate vector space. A SpatialReference in the base type does not have the explicit behaviour of a map.  Given a SpatialReference we can speak about a point as having coordinates (the image of the point under the SpatialReference).  A SpatialReference gives the Point interface the ability to return its coordinates relative to this Spatial Reference.

A CoordinateTuple is a pairing of a SpatialReference and a value tuple.  The SpatialReference provides the interpretation of the value tuple in addition to the schema of the tuple.  Note that a CoordinateTuple is not a point.  A point is essentially an equivalence class of CoordinateTuples.  This could be viewed as a table of (SpatialReference, Tuple) pairs.

A Point is an element of a Space.  It may or may not be assigned coordinates.  We can speak of a point such as "My House" without first assigning some SpatialReference.  Points are associated with CoordinateTuples through SpatialReferences.

A SpaceDictionary is a collection of Spaces.  A SpaceDictionary is intended to be a public resource so that a collection of users can employ the same dictionary and reference spaces within it.  

A SpatialReferenceDictionary is a collection of SpatialReferences.  It performs a similar function for SpatialReferences as does the SpaceDictionary for Spaces.

A SpatialReferenceTransformation is a mapping from CoordinateTuples to CoordinateTuples.  Note that this is distinguished from a mapping of points which is considered independent of the SpatialReference systems used.

A SpatialReferenceTransformationDictionary is a collection of SpatialReferenceTransformations. It provides a public list of SpatialReferenceTransformations.

A SpatialTransformation is distinguished from a SpatialReferenceTransformation in that the former acts on Points, where as the latter acts on CoordinateTuples.  This distinction is shown in Figure 1.

Figure 1. SpatialTransformations and SpatialReferenceTransformations

3.1.1	Space

A Space represents an infinite collection of points.  Note that a Space provides constructors for Points, that is we do not have a separate SpaceFactory.  

A Space is provided with a default SpatialReference.  This is returned through the Std() function.

	The interface for Space is defined as:

		Interface	Space
		{
		String			Name();
		SpatialReference		SRCreate(Name);
		Point			PCreate(Name);
		Point			PCreate(Name,Tuple,
							    SpatialReference);
		Point			PCreate(Name, CoordinateTuple);
		SpatialReference		Std();
		}

	Note the following:

	1.	PCreate(Name) - creates a point without coordinates.

2.	Std() - returns the default or standard SpatialReference associated with the Space.  This is completely arbitrary.

3.1.2	Point
	
A point is a named element of a Space.  Points are constructed by Spaces as shown in Section 3.1.1.

The interface on Point is:

	Interface 	Point
	{
	String			Name();
	CoordinateTuple		Coord(SpatialReference);
	Boolean			Assign(CoordinateTuple);
	}

3.1.3	SpatialReference

A SpatialReference is a means of assigning coordinates to points.

The interface on SpatialReference is:

	Interface	SpatialReference
	{
	String			Name();
	CoordinateTuple		CCreate(tuple);
	Space			Space();
	}

3.1.4	CoordinateTuple

A CoordinateTuple is a pairing of a tuple of values and a SpatialReference.

The interface on CoordinateTuple is:

	Interface	CoordinateTuple
	{
	Tuple			Values();
	SpatialReference		Referenced();
	}

3.1.5	SpaceDictionary
	
	A SpaceDictionary is a named collection of Spaces.

	The interface on SpaceDictionary is:

		Interface	SpaceDictionary:Collection
		{
		Space			Uses(Name);
		}

3.1.6	SpatialReferenceTransformation

A SpatialReferenceTransformation is a mapping taking CoordinateTuples to CoordinateTuples.

The SpatialReferenceTransformation interface is:

	Interface	SpatialReferenceTransformation
	{
	CoordinateTuple		Evaluate(CoordinateTuple);
	}

3.1.7	SpatialReferenceDictionary

A SpatialReferenceDictionary is a named collection of SpatialReferences.

The SpatialReferenceDictionary interface is:

	Interface SpatialReferenceDictionary:Collection
	{
	SpatialReference		Uses(Name);
	}

3.1.8	SpatialReferenceTransformationDictionary

A SpatialReferenceTransformationDictionary is a queriable collection of SpatialReferenceTransformations.

	The interface to SpatialReferenceTransformationDictionary is:

	Interface 					SpatialReferenceTransformationDictionary:QuerCollection
		{
		SpatialReferenceTransformation Uses(SpatialReference,
								     SpatialReference );
		SpatialReferenceTransformation Uses(Name);
		}

3.1.9	SpatialTransformation

A SpatialTransformation is a map from a Space to a Space.  It carries Points to Points.

	The interface for a SpatialTransformation is:

		Interface SpatialTransformation
		{
		Point	Evaluate(Point);
		}

Note that a SpatialTransformation is constructed relative to SpatialReferences in the domain and range spaces.  

The interface for the SpatialTransformation factory is:

	Interface SpatialTransformationFactory
	{
	SpatialTransformation  Create(	SpatialReference,							SpatialReference):
	}

3.2	AffineSpace Based Reference Systems

The reference systems discussed in this section are based on the assumption that the Spaces are formal Affine Spaces.  See the discussion above in Section 2. for further information about Affine Spaces.  An Affine Space corresponds to our familiar everyday notion of a geometric space.  Locations in the Affine Space are defined relative to frames which are bases attached at some point in the Affine Space.
	
Affine transformations are by definition 1:1 and onto.  Important subtypes of Affine Transformations include:

		orthogonal transformations (rotations)
		skew reflections
		compressions and skew compressions
		orthogonal projections

3.2.1	AffineSpace

	AffineSpace is a derived type from Space.  Its interface is:

		Interface	AffineSpace:Space
		{
		AffinePoint		PCreate(	Name, 
								Tuple,
								Frame);
		AffinePoint		PCreate(Name, CoordinateTuple);
		Vector			PDiff(AffinePoint,AffinePoint);
		AffinePoint		Vadd(Vector);
		Integer			Dimension():
		Frame			SRCreate(AffinePoint,Basis);
		Vector			VCreate(Name,Tuple,Frame);
		Basis				BCreate(ListofVector);
		Float				Distance(AffinePoint, AffinePoint);
		}

	Note the following
	
	1.	PDiff returns the vector defined by a pair of AffinePoints.

2.	Vadd returns the AffinePoint obtained by adding the vector to a given AffinePoint.

3.	VCreate returns a vector in the Tangent Space for which Frame is a basis.

3.2.2	Frame

	A Frame is a reference system for an Affine Space.  A frame provides coordinates for an Affine Point using the constructor Pcreate from the AffineSpace interface.

	A Frame consists of an orthogonal basis and an AffinePoint, the latter representing the location in the AffineSpace where the frame is attached.

	The interface for a Frame is defined as:

		Interface	Frame:SpatialReference
		{
		CoordinateTuple		Ccreate(tuple);
		AffinePoint		Origin();
		Basis				Vectors();
		AffineMap			ACreate(AffinePoint,
							     Basis);
		Frame			FCreate(AffinePoint, Basis);
		}

	The Vectors() function returns the orthogonal basis of the frame.

	The Acreate is an AffineMap constructor.  This yields the map that carries the origin of the current frame into the AffinePoint (argument) and the basis of the current frame into the Basis Argument.  Note that the AffinePoint and Basis arguments must be expressed relative to the Space containing the current frame.

	The FCreate constructors build frames relative to the current frame.

3.2.3	AffinePoint

	An AffinePoint is a point in an AffineSpace.  Its interface is:

		Interface 	AffinePoint:Point
		{
		CoordinateTuple		Coord(Frame);
		Boolean			Assign(Tuple, Frame);
		}

3.2.4	Vector

	A Vector is an element of a VectorSpace.  VectorSpaces are assumed to be finite dimensional over some field of scalars.

	The Vector interface is:

		Interface Vector
		{
		Tuple			Coeff(Basis);
		Boolean			Assign(Tuple,Basis);
		Vector			Vadd(Vector);
		Vector			Smult(Scalar);
		Vector			Id(Vector);
		Vector			VNormalize();
		Float				VNorm();
		Vector			VCross(Vector);
		}

3.2.5	Basis

	A Basis is a maximal linearly independent set of vectors in a VectorSpace.  As an ADT it is essentially a list of vectors.

	The Basis interface is:

		Interface	Basis:SpatialReference
		{
		Vector			Component(Index Integer);
		}

1.	The function Component(Index Integer) returns the Index'th vector in the basis.

3.2.6	VectorSpace

	A VectorSpace is a subtype of Space.  It is an infinite collection of Vectors, but is not of collection type.

	The VectorSpace interface is:

		Interface 	VectorSpace:Space
		{
		Vector			VCreate(Tuple,Basis);
		Integer			Dimension();
		Basis				BCreate(ListofVector);
		}

3.2.7	AffineMap

	An AffineMap is a SpatialTransformation carrying AffinePoints to AffinePoints.

	The AffineMap interface is:

		Interface AffineMap:SpatialTransformation
		{
		AffinePoint	Evaluate(AffinePoint);
		}

	The AffineMap constructor is given as:

		Interface AffineMapFactory
		{
		AffineMap		Create(Frame, Frame);
		}

	Note that there is an AffineMap constructor associated with a Frame.

3.2.8	LinearMap

	A LinearMap is a SpatialTransformation carrying vectors to vectors.

	The LinearMap interface is:

		InterfaceLinearMap:SpatialTransformation
		{
		Vector		Evaluate(Vector);
		}

	The LinearMap constructor is given by

		Interface LinearMapFactory
		{
		LinearMap		Create(Basis,Basis);
		}

3.2.9	ProjectiveMap

	A ProjectiveMap is a SpatialTransformation which carries AfinePoints to AffinePoints.

	The ProjectiveMap interface is:

		Interface	ProjectiveMap:SpatialTransformation
		{
		AffinePoint	Evaluate(AffinePoint);
		}

	The ProjectiveMap constructor is:

		Interface  ProjectiveMapFactory
		{
		ProjectiveMap	Create();
		}

3.2.10	Some Examples

	This section provides some simple examples of the AffineSpace ADT's introduced in this section.

	Example 1 - Simple Example:

		VectorSpace	EarthSpace;
		Frame		F1,F2
		AffinePoint	P,Q,O1
		CoordinateTuple	X,Y,Z
		AffineMap		A;
		Float			Distance
	
		/* Define a reference frame on the earth */	
		F1 	= EarthSpace.Std();

	/* The point Q has coordinates relative to F1
	
	Q 	= EarthSpace.PCreate("My House", (10,20,0), F1);

		/* Create a camera reference frame */

		O1	= F1.Origin();
		v	= EarthSpace.VCreate(F1, (100,10,50));
	F2 	= EarthSpace.FCreate(O1 + v, F1.Vectors);	

	/* Find the coordinates of My House relative to F2 */

	X 	= Q.Coord(F2);

	/* Your house has coordinates (5,2.1,3.4) relative to F2 */

	P	= EarthSpace.PCreate("Your House",F2,(5.2,1,3.4));

	/* How far is your house from my house ? */

	Distance = EarthSpace.Distance(P,Q);

	Note that the Reference Frames F1, F2 could have been created by a different person than the user computing distances or constructing points.

	Example 2:	Aerial Photographs

	Consider Figure 3.2.7-1.  This shows an aerial camera taking a photograph of a ground scene.  We assume in this example that the area involved is small enough that the earth's curvature can be ignored.  Points on and near the surface of the earth are assumed to be modelled by an AffineSpace.  Locations of points within this space are given by the reference Frame F1.  Points in the camera system are given relative to another Frame F2. Points in the image plane of the camera are given relative to still another Frame F3.

Figure 3.2.7-1 Frames of Reference

	To capture the content of Figure 3.2.7-1 we can take either a constructive or associative point of view. In the constructive view point we build all of the reference frames from a starting or base frame.  In the associative approach we create the reference frames in each of the spaces and then relate the points by constructing the appropriate maps.

	Consider the constructive approach first:

		Space 		EarthSpace;
		Frames		F1,F2,F3;
		AffinePoint	O1,O2,O3,Q;
		Vector		LookVector;CX,CY,CZ;EX,EY,EZ,IX,IY;
		Basis			B1, B2, B3;

		/* First the base frame */

		F1 = EarthSpace.Std();

	/* Q is a point in the earth frame of reference */
	
		Q = EarthSpace.PCreate("My House", (20,20,10),F1);

		/* Now the Camera frame */

		O2 	= EarthSpace.PCreate("Camera Origin", 								(20,20,40),F1);
		B1   	= F1.Vectors();
			EX	= B1.Component(1); /* X-axis */

		CZ 	= PDIFF(O2, O1); 
		CZ	= CZ.VNormalize();
		
		CY 	= CX.VCross(EX);
		CX 	= CY.VCross(CZ);

		B2	= EarthSpace.BCreate((CX,CY,CZ));

		F2 	= EarthSpace.FCreate("Camera Frame", 
							O2, B2);

		/* Now the Image Plane - this is just the x-y plane */
		/* of the camera frame with the axes rotated */

		O3	= O2;
		IX	= CX;
		IY	= -CY;
		IZ	= CZ;

		B3	= EarthSpace.BCreate((IX,IY,IZ));
	
		F3	= EarthSpace.FCreate("Image Frame",O3,B3);

		/* We define a Look Vector - this is defined by a point */
		/* in the image plane P and the camera focal point f.    */

		f 	= EarthSpace.PCreate("Focal Point", (0,0,10),F2);
		P	= EarthSpace.PCreate("Image Point", (2.1,3.1,0),F3);

		LookVector = EarthSpace.PDiff(P, f);
		LookVector = LookVector.VNormalize();

Now let us take the associative approach

		Space 		EarthSpace; CameraSpace, ImageSpace
		Frames		F1,F2,F3;
		AffinePoint	O1,O2,O3,Q;
		Vector		LookVector;CX,CY,CZ;EX,EY,EZ,IX,IY;
		Basis			B1, B2, B3;
		OurMap		AffineMap;

		/* First the base frame */

		F1 = EarthSpace.Std();
		
		/* Now the camera frame */

		F2 = CameraSpace.Std();

		/* Now the image frame */
	
		F3 = ImageSpace.Std();

		/* Q is a point in the earth frame of reference */
	
		Q = EarthSpace.PCreate("My House", (20,20,10),F1);

		/* P is a point in the camera frame of reference */

		P = CameraSpace.PCreate("Image Point", (2.1,3.3,0), F2);

		/* f is the camera focal point */;

		f = CameraSpace.PCreate("Focal Point", (0,0,10), F2);

		/ * Associate F2 to F1 by an Affine Map */

		O2 	= EarthSpace.PCreate("Camera Origin", 								(20,20,40),F1);
		B1   	= F1.Vectors();
			EX	= B1.Component(1); /* X-axis */

		CZ 	= PDIFF(O2, O1); 
		CZ	= CZ.VNormalize();
		
		CY 	= CX.VCross(EX);
		CX 	= CY.VCross(CZ);

		B2	= EarthSpace.BCreate((CX,CY,CZ));

		OurMap = EarthFrame.ACreate(F2, O2, B2);
	
		/* Note that (O2,B2) is equivalent to the frame F2 */

		/* The image of a point Q in the Earth Frame under */
		/* OurMap is       */

		Q' 	= OurMap(Q);

	How does this actually work ?  Note that Q' is a point in Camera Space.  Note also that we have simplified matters (unrealistically for a camera) by assuming that this is an orthographic projection, however we will remedy this detail shortly).  When we construct a Frame we build the matrix representation of the Frame relative to the standard Frame of the containing space using the column vectors providing in the constructor.  When we construct a point we compute the coordinates internally relative to the standard Frame of the containing space. If the point is given relative to another Frame we use that Frame's matrix to compute the coordinates of the point relative to the containing space. In all cases points are referenced back to the standard frame of the containing space.  This of course is done "under the covers".  When we construct an AffineMap, as above (OurMap in the example), we build the matrix of that map internally using the column vectors supplied in the constructor (O2,B2).  The other Frame in the constructor (the F2 in the example) is used only to get the
 	target space of the map.

	To be specific we work out some of the details:

	Consider first the vector space case.

	Let V and V' be vector spaces.  Select a basis v1,...vn and v1',,,vn'1 in each.  Let x be a vector in V.  Then there exists coefficients c1...cn such that:

			x = Svi*ci	

	We call the (ci)  a coordinate vector for x.

	Now let T be a linear map, T:V --->V'.  The character of T is determined by its action on the basis vectors.	Hence

			Tvi = Svj'*dji

	Note that this can be interpreted as follows:

			T carries vi to a vector wi in V'	

			The coordinates of wk	are (dik).

			T has a matrix (relative to v1...vn and v1'...vn'		given by (dik).  The column vectors of this matrix
			are the coordinate vectors for wk.	

	Given a basis in V (in this case the vi) and the image of this basis under a linear transformation wi, and further given the coordinates (column vectors) of wi relative to v1,..vn and v1'...vn' we can write down the matrix of T by using for the columns of the matrix, the column vectors of wi.

	Note this same approach carries over to the matrices for Affine transformations ( as 4 x 4 matrices ).

	Frame:
	
	A Frame can be represented internally in terms of a Matrix carrying the space (the container space) standard frame into the frame of interest.

	The constructor (on Space)

	FCreate(AffinePoint, Basis)  can be implemented as:

1.	Use AffinePoint and Basis to construct a 4 x 4 matrixas above.  Get Coordinates of O and Basis elements relative to the Standard frame of the container Space.

		2.  Multiply this matrix by the matrix of the Std Frame.
	
	To create a frame relative to another frame G which has just been constructed by a Space, use the Frame constructor for Frames.

	FCreate(AffinePoint, Basis) can be implemented as:

1.	Use AffinePoint and Basis to construct a 4 x 4 matrixas above.  Get Coordinates of O and Basis elements relative to the current frame.

2.  	Multiply this matrix by the matrix of the current frame.

	To create a point relative to a frame.

	Points:

	PCreate(tuple, Frame)

	Get the Matrix of the Frame and multiply it by the coordinate tuple supplied.  This is the coordinate tuple relative to the creating space with its standard frame.