The complexity of images critically influences our impression of them and our assessment of their beauty. However, there is no consensus on the best way to formalize an objective measure of complexity for images. Moreover, studies relating subjective assessments of complexity and beauty to objective measures are hampered by the use of hand-crafted stimuli, inhibiting generalization. To tackle these issues, we generated 2D black-and-white patterns using cellular automata, collected ratings of their subjective complexity and beauty from 80 participants, and assessed the relationship between these ratings and objective measures of complexity (density, asymmetry, entropy, local spatial complexity, Kolmogorov complexity). We also introduced “intricacy” which quantified the number of components in patterns using a graph-based approach. We found that a weighted combination of local spatial complexity and intricacy was an effective predictor (R²test=0.46) of subjective complexity. This implies that people’s complexity ratings depend on the number of distinct elements in the pattern along with their local spatial distribution – complexity judgments are therefore determined by integrating global and local image features. Furthermore, we found a positive linear relationship between beauty and complexity ratings, with a negative linear influence of disorder, namely asymmetry and entropy, and a negative interaction between the two (R²test=0.64). This implies there is beauty in complexity as long as there is sufficient order. Lastly, we found some evidence for individual differences with subjects displaying varying degrees of preference towards intricacy (in their complexity assessments) and dislike of disorder (in their beauty assessments).