kalman.readme

This package implements a Kalman filter as described in the paper "A Statistical Algorithm for Esti

KALMAN FILTER PACKAGE

	This package implements a Kalman filter as described in the
paper "A Statistical Algorithm for Estimating Speed from Single Loop
Volume and Occupancy Measurements" by D. J. Dailey.

	The filter uses volume (in vehicles/hour) and occupancy (as a
percent, 0-100) to produce a speed (in miles/hour).

FILES

	Makefile	makefile
	kalman.c	C source code
	kalman_p.h	Prototypes for private functions
	kalman.h	General header file:  data structures,
			defines, and prototypes for public functions
	kalman_demo	Simple demo program which uses the kalman
			filter to compute speed from canned data
	kalman.dat	Canned data for demo program


BUILDING THE FILTER

	"make" builds the Kalman filter and the demo program.

	"make demo" builds the Kalman filter, the demo, and runs the demo.


IMPORTANT NOTE

	The Kalman filter requires two consecutive good data points to
report a result.  This means:

	(1) when it is started, it will not return a speed until the
	    third iteration

	(2) if a sensor reports bad data or no data, there will be no
	    speed reported for that iteration or the next

	(3) the filter will not start for a sensor until two good
	    data points have been received on consecutive iterations.


USING THE FILTER IN YOUR CODE

	Allocate a kalman_t for each sensor
	Initialize this kalman_t with kalman_initialize()
	Set kalman parameters to non-default values if needed
	Loop:
		Receive data
		Scale volume/occupancy
		Call kalman_filter() which returns TRUE/FALSE
		Examine return value, use if valid

Example:

	kalman_t *k;		/* pointer to kalman struct */
	double occupancy	/* occupancy, 0-100 */
	int volume;		/* volume, vehicles/hr */
	int valid;		/* validity flag for speed estimate */
	double speed, length;	/* speed and length from filter */

	k = (kalman_t *) malloc(sizeof(kalman_t));
	if (!k) {
		/* handle error */;
		break;
	}

	/* initialize, set Kalman parameters */

	kalman_initialize(k);
	kalman_set_initial_speed(k, 55.0);

	while(1) {
		/* obtain volume and occupancy values
		 * scale occupancy to 0-100
		 * scale volume to vehicles/hour */

		valid = kalman_filter(k, occupancy, volume, &speed, &length);
		if (valid) {
			/* use valid value */
			printf("got valid speed = %5.2f\n", speed);
		}
		else
			printf("no speed estimate\n");
	}


DATA STRUCTURES

	The struct kalman_t in kalman.h contains all the information
used by the filter, as well as internal information about its state.


VALID DATA

	The filter expects volume in vehicles per hour and occupancy
as a percentage.  

	Valid data is defined as:
		volume > 0
		occupancy > 0 and occupancy < 100%

	The filter does not start until two consecutive valid data
points are received.  Once the filter starts, it handles invalid
data but does not return a speed value.

USABLE VS UNUSABLE

	kalman_filter returns TRUE if the speed estimate is deemed
usable, FALSE otherwise.  Under certain conditions, speed and length
are returned even if kalman_filter() returns FALSE.  These values 
should not be used, they are provided so that the filter may be
monitored.

SETTING COEFFECIENTS, PARAMETERS AND CONSTANTS

	The following constants are defined in kalman.h:

	DEFAULT_L		Mean length of vehicles at sensor
	DEFAULT_SIGMA_S		Variability of speed
	DEFAULT_SIGMA_NO	Std dev of occupancy/volume ratio
	DEFAULT_A		AR[2] coefficients, experimentally derived
	DEFAULT_B			using least-squares forward/backward
	DEFAULT_INITIAL_SPEED	Initial speed estimate

	The initial speed is used only when the filter is restarted,
	other parameters are used on each iteration.

	To change these for all sensors, change the #define.
	Alternatively, you can set coefficients on a per-sensor
	basis with kalman_set_{field}:

		kalman_set_initial_speed(k, 55.0);


FILTER STATE AND OPERATION

	The filter requires two consecutive valid data points to
properly initialize.  Once it is initialized, it runs until the
length goes negative.

	This gives us three states:

	initial: no data has been loaded
		 transitions: moves to "first" if good data received
			      stays on "initial" otherwise

	first:   first data point loaded
		 transitions: moves to "running" if good data received
			      moves to "initial" otherwise

	running: filter is running
		 transitions: moves to "initial" if length goes negative
			      stays on "running" otherwise

	If the state is "initial", then bad data is ignored.  If good
data is received, it is loaded into the filter and the state changed
to "first", indicating that another data point is needed.  The filter
always returns FALSE.

	If the state is "first", then another data point is needed.
If good data is received, it is loaded into the filter and the
filter is run.  The state is changed to "running"  The calculated speed
is not yet usable, so the return value is FALSE.  If good data is not
received, then the filter moves back to "initial" state.

	If the state is "running", the filter has been initialized
and can handle bad data.  If good data is received, it is loaded and
the filter is run.  If the estimated length is negative, then the
filter is restarted and FALSE returned.  If the estimated length is
outside contraints, the estimated values are still returned, but
the return value is FALSE.  If the estimated length is within
constraints, the speed estimate is deemed rosbust and the return
value is TRUE.  If bad data is received, the filter is loaded with
nulls and run.  The resulting value may not be used so FALSE is
returned.  FALSE is also returned if the data from the previous
iteration was bad.

	This can be expressed in pseudocode:

	initial: no data has been loaded
		 actions: if good data received
				load into filter
                          return FALSE
		 transitions: moves to "first" if good data received
			      stays on "initial" otherwise

	first:   first data point loaded
		 actions: if good data received
				load into filter
				run filter
                          return FALSE
		 transitions: moves to "running" if good data received
			      moves to "initial" otherwise

	running: filter is running
		 actions: if good data received
				load into filter
			  else
				load nulls into filter
			  run filter
			  if length is negative
				restart filter
				return FALSE
			  if data from this or previous run was null
				return FALSE
			  if data is within length constraints
				return TRUE
			  else
				return FALSE
		 transitions: moves to "initial" if length goes negative
			      stays on "running" otherwise

	The math is explained in the paper.

$Id: kalman.README,v 1.4 1996/12/17 21:53:52 kint Exp $