This article presents a mathematical definition of texture – the Julesz ensemble Omega(h), which is the set of all images (defined on Z-squared) that share identical statistics h. Then texture modeling is posed as an inverse problem: given a set of images samples from an unknown Julesz ensemble Omega(h*), we search for the statistics h* which define the ensemble. A Julesz ensemble Omega(h) has an associated probability distribution q(I;h), which is uniform over the images in the ensemble and has zero probability outside. in a companion paper[32], q(I;h) is shown to be the limit distribution of the FRAME (Filter, Random Field, And Minimax Entropy) model[35] as the image lattice A –> Z-squared. This conclusion establishes the intrinsic lnk between the scientific definition of texture on Z-squared and the mathematical models of texture on fintite lattices. It brings two advantaages to computer vision. 1). The engineering practice of synthesizing texture images by matching statistics has been put on a mathematical foundation. 2). We are released from the burden of learning the expensive FRAME model in feature pursuit, model selection and texture synthesis. In this paper, an efficient Markov chain Monte Carlo algorithm is proposed for sampling Julesz ensembles. The algorithm generates random texture images by moving along the directions of filter coefficients and thus extends the traditional single site Gibbs sampler. This paper also compares four popular statistical measures in the literature, namely, moments, rectified functions, marginal histograms and joint histograms of linear filter responses in terms of their descriptive abilities. Our experiments suggest that a small number of bins in marginal histograms are sufficient for capturing a variety of texture patterns. We illustrate our theory and algorithm by successfully synthesizing a number of natural textures