Sensing lena-massively distributed compression of sensor images

The sensor broadcast problem: in our setup, sensors measure each one pixel of an image that unfolds over a field, and broadcast a rate constrained encoding of their measurements to every other sensor-the goal is for all sensors to form an estimate of the entire image is considered. In recent work, we proposed a protocol that uses wavelets to decorrelate sensor data, taking advantage of the compact support of the basis functions to keep costly inter-sensor communication at a minimum. In this paper, we prove an asymptotic optimally result for these protocols: the rate of growth for the traffic they generate is Θ(log(n/D)) (n nodes, total distortion D), matching exactly the rate of growth of the rate/distortion function. We thus close the gap between theory and practice for this new form of massively distributed (one pixel/sensor) image compression, by providing the first efficient and provably optimal algorithms to solve the sensor broadcast problem.