In order to improve the robustness and efficiency of the watermark algorithm, a new self-adaptive watermark algorithm based on the texture feature is proposed. This algorithm selects the energy, entropy and contrast of the gray co-occurrence matrix as texture features, rapidly and accurately extracts the strong texture region of host images by the Mean Shift fast clustering algorithm. This algorithm embeds the watermark into the big coefficients in the Contourlet domain of the image strong texture area, adaptively selects the watermark embedding locations and controls the watermark embedding strength through texture clustering outcome. The experiment shows that this algorithm has the strong robustness to the Gauss low pass filter, Wiener filter, median filtering, Salt and pepper noise, Gaussian noise, JPEG compression, shear attack, etc. This algorithm's convergence rate is better than that of both FCM clustering and K-means clustering algorithm. This algorithm has realized blind detection.