Ph.D Thesis | |

Ph.D Student | Cohen Asaf |
---|---|

Subject | Topics in Scanning of Multidimensional Data |

Department | Department of Electrical and Computer Engineering |

Supervisors | PROF. Neri Merhav |

ASSOCIATE PROFESSOR Tsachy Weissman | |

Full Thesis text |

We investigate several
problems in scanning of multidimensional data arrays, such as universal
scanning and prediction (``scandiction", for short), and scanning of noisy
data arrays. These problems arise in several aspects of image and video
processing, such as predictive coding, filtering and denoising. In predictive
coding of images, for example, an image is compressed by coding the error
sequence resulting from scandicting it. Thus, it is natural to ask what is the
optimal method to scan and predict a given image, what is the resulting minimum
prediction loss, and whether there exist specific scandiction schemes which are
universal in some sense.

More specifically, we investigate the following problems: First, modeling the
data array as a random field, we examine whether there exists a scandiction
scheme which is independent of the field's distribution, yet asymptotically
achieves the same performance as if this distribution was known. This question
is answered in the affirmative for the set of all spatially stationary random
fields and under mild conditions on the loss function.

We then discuss the scenario where a non-optimal scanning order is used, yet
accompanied by an optimal predictor, and derive a bound on the excess loss
compared to optimal scandiction. For individual data arrays, where we show that
universal scandictors with respect to arbitrary finite scandictor sets do not
exist, we show that the Peano-Hilbert scan has a uniformly small redundancy
compared to optimal finite state scandiction.

Finally, we examine the scenario where the random field is corrupted by noise,
but the scanning and prediction (or filtering) scheme is judged with respect to
the underlying noiseless field. A special emphasis is given to the interesting
scenarios of binary random fields communicated through binary symmetric
channels and Gaussian random fields corrupted by additive white Gaussian noise.