Efficient High-Dimensional Filtering for Image and Video Processing

High-dimensional filters are a fundamental building block for several applications, having recently received considerable attention from the research community. Unfortunately, naive implementations of such an important class of filters are too slow for many practical uses. This dissertation describes three novel approaches to efficiently perform high-dimensional filtering with linear cost in both the number of pixels and in the dimensionality of the space in which the filters operate. Our filters address the main limitations of previous techniques, in addition to providing the fastest performance (both on CPU and GPU) for a variety of real-world applications.