Abstract: Traditional texture synthesis techniques use high dimensional vector trees to accelerate image patch matching.They are very deficient,cost a large of memory,and cannot be executed in parallel on GPU.To improve the efficiency of the image patch matching,this paper proposes a random parallel optimized texture synthesis algorithm.This algorithm consists of two steps: initialization step and iterative optimization step.Initialization step samples image patches randomly from the input image and pastes them to the target image.Optimization step applies a parallel random search and a parallel texture patch propagation to iteratively refine synthesis results.According to the property that the distribution probability of appropriate nearest texture patches is inverse to the distance between the last matched patch and the sample patch,we accelerate the texture patch matching by sampling target image patches with the probability distribution.We have implemented our algorithm using CUDA,and it offers substantial performance improvements over the previous state of the art algorithms(50~100X),which enables its use in interactive texture synthesis and texture synthesis for super-size textures.