Manhattan Cutset Sampling and Sensor Networks

Cutset sampling is a new approach to acquiring two-dimensional data, i.e. images, where values are recorded densely along straight lines. This type of sampling is motivated by physical scenarios where data must be taken along straight paths, such as a boat taking water samples. Additionally, it may be possible to better reconstruct image edges by using the dense amount of data collected on straight lines. Finally, an advantage of cutset sampling is in the design of wireless sensor networks. If battery-powered sensors are placed densely along straight lines, then the transmission energy required for communication between sensors can be reduced, thereby extending the lifetime of the network.

A special case of cutset sampling is Manhattan sampling, where data is recorded along evenly-spaced rows and columns. This thesis primarily examines Manhattan sampling in three projects. First, we prove a sampling theorem that gives conditions under which an image can be perfectly reconstructed from its Manhattan samples. This theorem is also generalized to dimensions higher than two. Second, we present several interpolation algorithms for reconstructing two-dimensional natural images from their Manhattan samples. Finally, we study energy-performance tradeoffs of cutset wireless sensor networks, and apply our results to a source localization problem.