Which algorithms are usable for heatmaps and what are their pros and cons

Problem Detail: 

This is a cross post from Stack Overflow, and DSP at Stackexchange since I cannot really decide which part of Stackexchange is most fitting. If this is the wrong place please tell me and I'll remove the question.

I have a matrix with numerical data. The matrix contains values from 0 to an arbitrary integer value.

Each element of the matrix is equivalent to a coordinate on a map.

I want to display that data as a heatmap overlayed the original map.

The three approaches I have found so far are

1. Linear interpolation. I guess the interpolation is don from the original datapoint to some set distance away from it in each direction.

2. Average of surrounding cells. Each empty cell gets the average value of the eight adjacent cells.

3. Gaussian blur as suggested on the SO thread.

4. Box blur with 1..n passes.

Are there any more methods? What are the pros and cons of the different approaches? What is a good source, online or print, for a discussion on heatmaps or similar problems?

Asked By : Einar Sundgren

Answered By : mags

If I have understood your question correctly (an illustrative example would have been helpful), I would recommend either Gaussian blurring or linear interpolation depending on the behavior you are after. Both are simple and should perform relatively fast even on a handheld device.

Linear interpolation (or rather bilinear interpolation) is simple but requires a square heat sample grid and you get some boundary effects that might be undesirable. The method is the most representative since "empty cells" (i.e., cells without heat information) are simply empty because of sparse sampling and not because they are void of heat. The interpolation tries to fill in the missing heat information in the empty cells by looking at the nearby heat samples.

Cell averaging will give you an equally high response in a cell neighboring the heat sample as in the heat sample cell itself (granted that the average is computed for all cells including the cells containing heat samples). If the average is computed for empty cells only (i.e., for cells with no heat information) then the cells with the heat sample will keep its full signal while adjacent cells will contain an average, which in a sparse sample grid will be 1/8 of the heat sample, resulting in a distribution almost as misleading as only using the original heat samples.

Gaussian blurring with a wide enough kernel is simple and gives a better representation of the impact of the heat samples than the cell averaging. However, the values in the blurred heat map for the empty cells will only be affected by the heat "spread" from the sample cells. So if the heat map is sparse, there will likely be empty cells on equal distance between two heat cells that do not get any heat information at all.

I hope this helps.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16699