Histograms

Collaboration diagram for Histograms:

Functions
int	HistogramBuild (float *VolumeSource, long Nx, long Ny, long Nz, double Frequency[], float Value[], int *Status)
int	HistogramEqualize (double Frequency[], float Value[], float EqualizedValue[], long HistogramLength, long *NumberOfClasses, double Tolerance)
int	HistogramGetSize (float *VolumeSource, long Nx, long Ny, long Nz, long *HistogramLength, int *Status)
int	HistogramKMeans (double Frequency[], float Value[], float QuantizedValue[], long HistogramLength, long *NumberOfClasses, double Tolerance, int *Status)

Detailed Description

Function Documentation

HistogramBuild()

int HistogramBuild	(	float *	VolumeSource,
		long	Nx,
		long	Ny,
		long	Nz,
		double	Frequency[],
		float	Value[],
		int *	Status
	)

Build histogram. Computation of the frequencies of occurrence of data values. VolumeSource is a (float)volume of size (Nx x Ny x Nz). Value[] is a (float)array of length previously determined by HistogramGetSize. The returned content of Value[] is sorted in strict ascending order. Frequency[] is a (double)array of length previously determined by HistogramGetSize.

success: return(!ERROR); failure: return(ERROR)

HistogramEqualize()

int HistogramEqualize	(	double	Frequency[],
		float	Value[],
		float	EqualizedValue[],
		long	HistogramLength,
		long *	NumberOfClasses,
		double	Tolerance
	)

Equalize histogram. Construction of the lookup table: Value[k] <-> EqualizedValue[k]. EqualizedValue[] satisfies:

sum(k in K(n0)) Frequency[k] ~=~ sum(k in K(n1)) Frequency[k]
for all n0, n1 in [0L, NumberOfClasses - 1L]

where ~=~ means "is about equal to", and where K(n) is a domain such that

EqualizedValue[k0] = (sum(k1 in K(n)) Frequency[k1] * Value[k1])
   / (sum(k2 in K(n)) Frequency[k2])
for all k0 in K(n)

under the constraint

DistinctElements(QuantizedValue[]) == NumberOfClasses

Frequency[] is a (double)array of length HistogramLength. The content of Frequency[] must be strictly positive. The content of Frequency[] must have unit sum. Value[] is a (float)array of length HistogramLength. The content of Value[] must be sorted in strictly ascending order. EqualizedValue[] is a returned (float)array of length HistogramLength.

On input, NumberOfClasses indicates the desired number of classes. On output, NumberOfClasses returns the effective number of classes. NumberOfClasses is no greater than (1.0 / max(Frequency[])), and never increases.

It may happen that the only solution that satisfies all constraints is undesirable e.g., Frequency[] = {0.9, 0.1}; Value[] = {10.0F, 90.0F}; NumberOfClasses = 2L; (desired) results in QuantizedValues[] = {18.0F, 18.0F}; NumberOfClasses = 1L; (actual)

success: return(!ERROR); failure: return(ERROR)

HistogramGetSize()

int HistogramGetSize	(	float *	VolumeSource,
		long	Nx,
		long	Ny,
		long	Nz,
		long *	HistogramLength,
		int *	Status
	)

Get size of histogram. Determination of the number of differing data values in a volume. VolumeSource is a (float)volume of size (Nx x Ny x Nz).

success: return(!ERROR); failure: return(ERROR)

HistogramKMeans()

int HistogramKMeans	(	double	Frequency[],
		float	Value[],
		float	QuantizedValue[],
		long	HistogramLength,
		long *	NumberOfClasses,
		double	Tolerance,
		int *	Status
	)

Histogram K means. Construction of the lookup table: Value[k] <-> QuantizedValue[k]. Minimization of sum(k) Frequency[k] * (Value[k] - QuantizedValue[k])^2. under the constraint DistinctElements(QuantizedValue[]) == NumberOfClasses.

Frequency[] is a (double)array of length HistogramLength. The content of Frequency[] must be strictly positive. The content of Frequency[] must have unit sum. Value[] is a (float)array of length HistogramLength. The content of Value[] must be sorted in strictly ascending order. QuantizedValue[] is a returned (float)array of length HistogramLength.

On input, NumberOfClasses indicates the desired number of classes. On output, NumberOfClasses returns the effective number of classes. NumberOfClasses never increases.

Important cases that go undetected (unfortunately):

1. convergence to a non-global optimum e.g., Frequency[] = {0.25, 0.25, 0.25, 0.25}; Value[] = {1.0F, 2.0F, 10.0F, 20.0F}; NumberOfClasses = 3L; results in the local optimum QuantizedValues[] = {1.0F, 2.0F, 15.0F, 15.0F}; instead of the true global optimum QuantizedValues[] = {1.5F, 1.5F, 10.0F, 20.0F};
2. there may be more than one global optimum e.g., Frequency[] = {1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0}; Value[] = {-1.0F, 0.0F, 1.0F}; NumberOfClasses = 2L; results in the global optimum QuantizedValues[] = {-0.5F, -0.5F, 1.0F}; the other global optimum is ignored QuantizedValues[] = {-1.0F, 0.5F, 0.5F};

success: return(!ERROR); failure: return(ERROR)