Groupe d’études et de recherche en analyse des décisions

Graph Theoretic Approach to Random Field Simulation

Michael A. Kouritzin Monash University, Australie

There is tremendous need to simulate and process correlated random fields in real time. Applications range from target detection to effective CAPTCHA generation to image recognition. Unfortunately, the real-time constraint excludes Gibb’s sampler and other Monte Carlo Markov chain resampling techniques based upon the whole joint distribution of the field. One must be content with simulating a field that matches less information. Herein, we discuss a graph theoretic method of simulating correlated random fields that match vertex or site probabilities as well as covariances along any desired edges. Application to CAPTCHA generation and optical character recognition will also be discussed. Finally, some properties of the produced fields will be given.