Color transformations in digital imaging systems are often implemented with lookup tables (LUTs) that require some form of multidimensional interpolation. Such LUT based transformations typically involve a trade-off between the computational cost, required storage and/or memory, and the resulting accuracy of the transform. In this article, novel methods are proposed for improving some of these quality-cost trade-offs. The methods fall in two categories: (i) those that improve the trade-off between computational cost and quality; and (ii) those that enhance the trade-off between LUT size and quality. Results show that promising trade-offs can be achieved by exploiting the properties of the human visual system, as well as the characteristics of the function being approximated by the LUT.