Rendition: Reclaiming What a Black Box Takes Away

The premise of our work is deceptively familiar: A black box f(·) has altered an image x → f(x), but only mildly. Recover the image x. This black box might be any number of simple or complicated things: a linear or nonlinear filter, some app on your phone, etc. The latter is a good canonical example for the problem we address: Given only “the app” and an image produced by the app, find the image that was fed to the app. We can run the given image (or any other image) through the app as many times as we like, but we cannot look inside the (code for the) app to see how it works At first blush, the problem sounds a lot like a standard inverse problem [16, 19], but it is not in the following sense: While we have access to the black box f(·) and can run any image through it and observe the output, we do not know how the block box alters the image. Therefore we have no explicit form or model of f(·). Nor are we necessarily interested in the internal workings of the black box. We assume only that the effect of the black box is mild in the sense that f(x) -x has a small Lipschitz seminorm---that is, \|f(x) -x\|≤ δ \|x \| for a sufficiently small δ. And as such, we are seeking to reverse its effect on a particular image, to whatever extent possible. This is what we call the “rendition” (rather than restoration) problem, as it does not fit the mold of an inverse problem (blind or otherwise). We describe general conditions under which this rendition is possible and provide a remarkably simple algorithm that works for both contractive and expansive black box operators. The principal and novel takeaway message from our work is this surprising fact: One simple algorithm can reliably undo a wide class of (not too violent) image distortions.