Avoiding detection can provide significant survival advantages for prey, predators, or the military; conversely, maximizing visibility would be useful for signalling. One simple determinant of detectability is an animal's colour relative to its environment. But identifying the optimal colour to minimize (or maximize) detectability in a given natural environment is complex, partly because of the nature of the perceptual space. Here for the first time, using image processing techniques to embed targets into realistic environments together with psychophysics to estimate detectability and deep neural networks to interpolate between sampled colours, we propose a method to identify the optimal colour that either minimizes or maximizes visibility. We apply our approach in two natural environments (temperate forest and semi-arid desert) and show how a comparatively small number of samples can be used to predict robustly the most and least effective colours for camouflage. To illustrate how our approach can be generalized to other non-human visual systems, we also identify the optimum colours for concealment and visibility when viewed by simulated red–green colour-blind dichromats, typical for non-human mammals. Contrasting the results from these visual systems sheds light on why some predators seem, at least to humans, to have colouring that would appear detrimental to ambush hunting. We found that for simulated dichromatic observers, colour strongly affected detection time for both environments. In contrast, trichromatic observers were more effective at breaking camouflage.