The Discrete Cosine Transform in JavaScript

The discrete cosine transform, or “DCT”, is used to convert a signal in the spatial domain (for example, a sound or an image) into an equivalent signal in the frequency domain. This frequency-domain signal can then be processed in some way and converted back to the original spatial-domain signal. The algorithm makes use of the principles of Fourier analysis, which states that any periodic function can be approximated to an arbitrary degree of precision as the sum of a series of sinusoidal waves of various frequencies and amplitudes.

The DCT is used in a variety of data compression formats, especially “lossy” ones, like JPEG and MP3. By discarding the frequency components whose amplitudes fall below a certain threshold, the size of the compressed data can be significantly decreased without unacceptable degradation to the decompressed version. If the discarded data is chosen carefully, it is often possible to minimize this degradation so much that it is undetectable to the casual observer.

A simple version of the DCT is implemented in JavaScript below. The code builds a set of samples, normalizes them, performs the DCT on them, inverts it, and then denormalizes the samples again, displaying a graph of the resulting samples at each step.

DiscreteCosineTransform

<html>
<body>
<script type="text/javascript">
// main

function DiscreteCosineTransformTest()
{
	this.main = function()
	{
		var dctHelper = DiscreteCosineTransformHelper;
		var displaySize = new Coords(600, 100);

		var samplesOriginal = 
		[
			0, 1, 2, 3, 4, 5, 6, 7, 
			7, 6, 5, 4, 3, 2, 1, 0,
			0, 1, 2, 3, 4, 5, 6, 7, 
			7, 6, 5, 4, 3, 2, 1, 0,
			0, 1, 2, 3, 4, 5, 6, 7, 
			7, 6, 5, 4, 3, 2, 1, 0,
			0, 1, 2, 3, 4, 5, 6, 7, 
			7, 6, 5, 4, 3, 2, 1, 0,
		];		

		var samplesNormalizedAndMinMax = dctHelper.samplesNormalize
		(
			samplesOriginal
		);

		var samplesNormalized = samplesNormalizedAndMinMax[0];
		var sampleMin = samplesNormalizedAndMinMax[1];
		var sampleMax = samplesNormalizedAndMinMax[2];

		var samplesInFrequencyDomain = dctHelper.samplesSpatialToFrequencyDomain
		(
			samplesNormalized
		);

		var samplesInSpatialDomain = dctHelper.samplesFrequencyToSpatialDomain
		(
			samplesInFrequencyDomain
		);		

		var samplesDenormalized = dctHelper.samplesDenormalize
		(
			samplesInSpatialDomain,
			sampleMin,
			sampleMax
		);

		// display as graphics
		DisplayHelper.samplesDraw("Original", displaySize, samplesOriginal);
		DisplayHelper.samplesDraw("Normalized", displaySize, samplesNormalized);
		DisplayHelper.samplesDraw("After DCT", displaySize, samplesInFrequencyDomain);
		DisplayHelper.samplesDraw("After Inverse DCT", displaySize, samplesInSpatialDomain);
		DisplayHelper.samplesDraw("Denormalized", displaySize, samplesDenormalized);

		// display as text
		//DisplayHelper.samplesPrint("Samples original: ", samplesOriginal);
		//DisplayHelper.samplesPrint("Samples normalized: ", samplesNormalized);
		//DisplayHelper.samplesPrint("Samples after DCT: ", samplesInFrequencyDomain);
		//DisplayHelper.samplesPrint("Samples after inverse DCT: ", samplesInSpatialDomain);
		//DisplayHelper.samplesPrint("Samples denormalized: ", samplesDenormalized);
	}
}

// classes

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{

	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divide = function(other)
	{
		this.x /= other.x;
		this.y /= other.y;
		return this;
	}

	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		return this;
	}

	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		return this;
	}

	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
}

function DiscreteCosineTransformHelper()
{
	// static class
}
{
	DiscreteCosineTransformHelper.samplesDenormalize = function
	(
		samplesToDenormalize, 
		sampleMin, 
		sampleMax
	)
	{
		var returnValues = [];

		var sampleRange = sampleMax - sampleMin;

		for (var s = 0; s < samplesToDenormalize.length; s++)
		{
			var sampleNormalized = samplesToDenormalize[s];

			var sampleDenormalized = 
				(sampleNormalized + 1) 
				/ 2 
				* sampleRange 
				+ sampleMin;

			returnValues[s] = sampleDenormalized;
		}

		return returnValues;	
	}

	DiscreteCosineTransformHelper.samplesNormalize = function(samplesToNormalize)
	{
		var samplesMinAndMax = MathHelper.minAndMaxOfNumbers
		(
			samplesToNormalize
		);
		var sampleMin = samplesMinAndMax[0];
		var sampleMax = samplesMinAndMax[1];

		var sampleRange = sampleMax - sampleMin;

		var samplesNormalized = [];

		for (var s = 0; s < samplesToNormalize.length; s++)
		{
			var sample = samplesToNormalize[s];

			var sampleNormalized = 
				(sample - sampleMin) 
				/ sampleRange 
				* 2 
				- 1;

			samplesNormalized[s] = sampleNormalized;
		}

		var returnValues = 
		[
			samplesNormalized, sampleMin, sampleMax
		];

		return returnValues;
	}

	DiscreteCosineTransformHelper.samplesSpatialToFrequencyDomain = function
	(
		samplesToConvert
	)
	{
		var samplesTransformed = [];

		var numberOfSamples = samplesToConvert.length;

		for (var i = 0; i < numberOfSamples; i++)
		{
			var sampleTransformed = 0;

			for (var j = 0; j < numberOfSamples; j++)
			{
				sampleTransformed += 
					samplesToConvert[j] 
					* Math.cos
					(
						Math.PI
						* i
						* (j + .5)
						/ numberOfSamples
					);
			}

			samplesTransformed[i] = sampleTransformed;
		}

		return samplesTransformed;
	}

	DiscreteCosineTransformHelper.samplesFrequencyToSpatialDomain = function
	(
		samplesToConvert
	)
	{
		var samplesTransformed = [];

		var numberOfSamples = samplesToConvert.length;

		for (var i = 0; i < numberOfSamples; i++)
		{
			var sampleTransformed = samplesToConvert[0] / 2;

			for (var j = 1; j < numberOfSamples; j++)
			{
				sampleTransformed += 
					samplesToConvert[j] 
					* 2
					* Math.cos
					(
						Math.PI
						* (i + .5)
						* (j)
						/ numberOfSamples
					);
			}

			sampleTransformed /= numberOfSamples;
		
			samplesTransformed[i] = sampleTransformed;
		}

		return samplesTransformed;
	}
}

function DisplayHelper()
{
	// static class
}
{
	// constants
	
	DisplayHelper.ColorSets = 
	[ 
		[ "White", "Gray", "Black" ],
		[ "Black", "Green", "Cyan" ],
	]

	// static methods

	DisplayHelper.samplesDraw = function
	(
		title, 
		sizeInPixels,
		samplesToDraw
	)
	{
		var sampleMinAndMax = MathHelper.minAndMaxOfNumbers(samplesToDraw);
		var sampleMin = sampleMinAndMax[0];
		var sampleMax = sampleMinAndMax[1];
		var sampleRange = sampleMax - sampleMin;
		var sampleMean = (sampleMin + sampleMax) / 2;
	
		var canvas = document.createElement("canvas");
		canvas.width = sizeInPixels.x;
		canvas.height = sizeInPixels.y;

		var graphics = canvas.getContext("2d");

		var colorSetIndex = 1;
		var colorSet = DisplayHelper.ColorSets[colorSetIndex];
		graphics.fillStyle = colorSet[0];
		graphics.fillRect(0, 0, sizeInPixels.x, sizeInPixels.y);
		graphics.strokeStyle = colorSet[1]
		graphics.strokeRect(0, 0, sizeInPixels.x, sizeInPixels.y);
		graphics.fillStyle = colorSet[2];

		var marginInPixels = new Coords(0, 8);
		var sizeInPixelsMinusMargins = sizeInPixels.clone().subtract
		(
			marginInPixels
		).subtract
		(
			marginInPixels
		);
		var midlineOffset = sizeInPixels.clone().divideScalar(2);
		midlineOffset.x = 0;
		var numberOfSamples = samplesToDraw.length;
		var sizeInSamples = new Coords(numberOfSamples, sampleRange);
		var sampleScaleInPixels = sizeInPixelsMinusMargins.clone().divide
		(
			sizeInSamples
		).multiply
		(
			new Coords(1, -1)	
		);
		var sampleOffset = new Coords(0, sampleMean);

		graphics.beginPath();
		graphics.moveTo(0, midlineOffset.y);
		graphics.lineTo(sizeInPixels.x, midlineOffset.y);
		graphics.stroke();

		var samplePos = new Coords(0, 0);
		var drawPos = new Coords(0, 0);

		graphics.beginPath();

		for (var s = 0; s < samplesToDraw.length; s++)
		{
			var sampleValue = samplesToDraw[s];
			samplePos.x = s;
			samplePos.y = sampleValue;

			drawPos.overwriteWith
			(
				samplePos
			).subtract
			(
				sampleOffset
			).multiply
			(
				sampleScaleInPixels
			).add
			(
				midlineOffset
			);

			if (s == 0)
			{
				graphics.moveTo(drawPos.x, drawPos.y);
			}
			else
			{
				graphics.lineTo(drawPos.x, drawPos.y);
			}
		}
		graphics.stroke();

		for (var s = 0; s < samplesToDraw.length; s++)
		{
			var sampleValue = samplesToDraw[s];

			sampleValue = MathHelper.roundNumberToDecimalPlaces
			(
				sampleValue, 2
			);
			samplePos.x = s;
			samplePos.y = sampleValue;

			drawPos.overwriteWith
			(
				samplePos
			).subtract
			(
				sampleOffset
			).multiply
			(
				sampleScaleInPixels
			).add
			(
				midlineOffset
			);

			graphics.beginPath();
			graphics.arc(drawPos.x, drawPos.y, 2, 0, Math.PI * 2);
			graphics.stroke();

			if (sampleValue != 0)
			{
				graphics.fillText("" + sampleValue, drawPos.x, drawPos.y);
			}
		}

		var fontHeightInPixels = 10;
		for (var i = 0; i < 3; i++)
		{
			// hack - Repetition makes it bolder.

			graphics.fillText
			(
				title, 
				0, 
				fontHeightInPixels
			);
		}


		document.body.appendChild(canvas);		
	}

	DisplayHelper.samplesPrint = function(prefix, samplesToPrint)
	{
		var stringToDisplay = prefix;
		var lineBreaks = "<br /><br />";

		var decimalPlacesToRoundTo = 3;

		for (var s = 0; s < samplesToPrint.length; s++)
		{
			var sample = samplesToPrint[s];

			var sampleRounded = MathHelper.roundNumberToDecimalPlaces
			(
				sample, decimalPlacesToRoundTo
			);

			stringToDisplay += sampleRounded + ", "
		}

		document.write(stringToDisplay);
		document.write(lineBreaks);
	}
}

function MathHelper()
{
	// static class
}
{
	MathHelper.minAndMaxOfNumbers = function(numbersToFindMinAndMaxOf)
	{
		var min = numbersToFindMinAndMaxOf[0];
		var max = numbersToFindMinAndMaxOf[0];
	
		for (var i = 1; i < numbersToFindMinAndMaxOf.length; i++)
		{
			var number = numbersToFindMinAndMaxOf[i];

			if (number < min)  			
			{
  				min = number;
  			}
  			else if (number > max)
			{
				max = number;
			}
		}

		var returnValues = [ min, max ];

		return returnValues;	
	}

	MathHelper.roundNumberToDecimalPlaces = function(numberToRound, decimalPlaces)
	{
		var multiplier = Math.pow(10, decimalPlaces);

		var returnValue = Math.round
		(
			numberToRound
			* multiplier
		) / multiplier;

		return returnValue;
	}
}

// run

new DiscreteCosineTransformTest().main();

</script>
</body>
</html>

Notes

  • I actually touched on this subject in a previous post, but at the time I referred to it as the “Fourier” transform, which is not technically accurate because, from what I can gather, a “real” Fourier transform uses imaginary numbers (!). Also, the code in that post is less general, and pretty messy to boot. Hopefully this version will provide a more elegant illustration. Hey, at the very least, this one has pictures.
  • In actual practice, no one would use this version of the algorithm because it’s O(n^2), which means that its running time increases with the square of the number of samples. The “fast Fourier transform” manages to do the same thing in O(n ln n) time, which is a significant improvement for large data sets. I gather that it does this by recursively splitting the samples into even and odd sets, and then performing some further steps on the parts. It’s a more complicated procedure, though, and as of this writing I don’t understand it.
Advertisements
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

2 Responses to The Discrete Cosine Transform in JavaScript

  1. Very useful post, thanks a lot! Your Javascript code though contains quite a few style problems (way too many newlines) which makes it hard to read, and contains an implied global in the samplesSpatialToFrequencyDomain function (sampleTransformed).

  2. I would write that function like this:

    samplesSpatialToFrequencyDomain: function (samples) {
    var i, j, sample;
    var len = samples.length;
    var ret = [];

    for (i = 0; i < len; i += 1) {
    sample = 0;
    for (j = 0; j < len; j += 1) {
    sample += samples[j] * Math.cos(Math.PI * i * (j – 0.5) / numberOfSamples)
    }
    ret[i] = sample;
    }
    return ret;
    },

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s