Fast topology density map

Density map visualizations have been successfully employed in various applications, particularly in the context of urban data analysis. Their computation, however, often relies on costly algorithms that hamper its practical usage. This paper introduces the Fast Topology Density Map (Fast TDM), a new algorithm that integrates graph- and image-based label propagation strategies for efficiently computing density maps based on spatiotemporal data. Fast TDM utilizes the Image-Foresting Transform (IFT) to partition the 2D space based on a given seed pixel set, enabling the computation of an Euclidean distance transform that leads to the creation of cost, label, and density maps simultaneously. Experiments considered different practical scenarios involving the computation and visualization of topology density maps on diverse topologies in terms of complexity, size, and temporal evolution. Experimental results show a significant reduction in computation time when topology density maps are computed using Fast TDM, achieving three times faster performance compared to recently proposed baselines. In addition, qualitative visualization analysis is performed, based on similarities and differences between the computed output maps with those produced by the baselines. Fast TDM can effectively replace counterparts, as it provides expedited computations with similar visual results in most cases.