6
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ A problem is image resampling. Other types of interpolation/filtering take larger amounts of surrounding data into account, and using different algorithms to combine them. See Bicubic interpolation; the 3 images on the right show the use of linear vs. bicubic interpolation vs. nearest neighbor (no interpolation). The "see also" section gives some more algorithms like this. Some are better at combining, some are better at preserving sharp features, some take longer to execute etc. $\endgroup$ – Realz Slaw Nov 4 '13 at 13:56
  • $\begingroup$ (continued) Er, I meant a "related problem". Also see dsp.SE, you can cross-post there as well (can you link to the cross posts please? I am curious about SO and dsp.SE answers). $\endgroup$ – Realz Slaw Nov 4 '13 at 14:13
  • $\begingroup$ @RealzSlaw , Additional factors in this particular implementation is that it must be able to run on a comparably weak processor (handheld devices) so short execution time is preferred. It must also take into account that the processed dataset is just a subset of a much larget set. More concretely a view of a map with a set of samplepoints that is a part of a larger map with a superset of samplepoints. $\endgroup$ – Einar Sundgren Nov 4 '13 at 14:31
  • $\begingroup$ You should put those additional factors into the question. Be aware that cs.SE is usually concerned mostly with theoretical efficiency, not actual efficiency. Also, if you are doing different scales, you should look up "mipmaps" (where you preprocess the interpolated images at different scales) and "trilinear interpolation" (where you use two scales and interpolate between them; this is very effective for video-games and multi-resolution textures). Also, you should know that these algorithms tend to be able to efficiently run on a GPU, so your device might be able to take advantage of that. $\endgroup$ – Realz Slaw Nov 4 '13 at 15:27
  • $\begingroup$ Please don't cross-post simultaneously on multiple Stack Exchange sites -- that is frowned upon. Instead, pick one site to post on. If you're not sure where is best to ask, you can check first on meta. Now that you've cross-posted, you can choose one site where you want your question to appear, then click on the "flag" button underneath the question on the 2 other sites to flag it for moderator attention and ask them to close the other clones or merge them with the copy on the 1 site where you want to have it. $\endgroup$ – D.W. Nov 4 '13 at 18:49
8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I did two implementations, one with a gaussian blur and one with a box blur (almost cell averaging) using more than one passes. Both performs well in real time for up to a 1000x1000 grid on a nexus one. Though kernels are calculated in beforehand and stored hardcoded in a separate matrix. $\endgroup$ – Einar Sundgren Nov 28 '13 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.