A fast parallel method for synthesis of random patterns

A new method for generation of nonhomogeneous, anisotropic random patterns defined on a square lattice is presented. First a hierarchy of seed structures is derived by recursively deleting the sites of the square lattice. This decimation process is parallel, and employs local ordering of i.i.d. random numbers. At every level of the hierarchy the surviving seeds expand and incorporate the decimated sites into cells. The ensemble of cells down-projected onto the square lattice defines a random tessellation whose coarseness increases with the level in the hierarchy. Nonhomogeneous random patterns are obtained by concatenating cells taken from different levels; anisotropic patterns by employing unequal weights in the generation process. The underlying hierarchical structure assures that the random patterns are synthesised in O[log(image_size)]time.