Visual complexity perception is an important issue in the fields of psychology and computer vision because it leads to the better understanding of the nature of human perception as well as the properties of the objects being perceived. In this study, five important characteristics of texture images that affect visual complexity perception are identified: regularity, understandability, roughness, directionality, and density. Among these, understandability is a deterministic characteristic, which reflects the viewer's prior knowledge and experience. These characteristics significantly affect the visual complexity perception of texture images. In order to achieve our objective, we carried out two experiments involving visual complexity assessment and paired comparison evaluation with 30 respondents. We applied correlation analysis, factor analysis, and multidimensional scaling to analyze the collected data. The experimental results showed that most of the human impressions of visual complexity can be explained by the perceived characteristics of texture images.