Higher-order spatial correlations contribute strongly to visual structure and salience, and are common in the natural environment. One method for studying this structure has been through the use of highly controlled texture patterns whose obvious structure is defined entirely by third- and higher-order correlations. Here we examine the effects that longer-term training has on discrimination of 17 such texture types. Training took place in 14 sessions over 42 days. Discrimination performance increased at different rates for different textures. The time required to complete a visit reduced by 25.4% ( p = 0.0004 ). Factor analysis was applied to data from the learning and experienced phases of the experiment. This indicated that the gain in speed was accompanied by an increase in the number of mechanisms contributing to discrimination. Learning was not affected by sleep quality but was affected by extreme tiredness ( p < 0.01 ). The improved discrimination and speed were retained for 2.5 months. Overall, the effects were consistent with perceptual learning. The observed learning is likely related to the adaptation of innate mechanisms that underlie our ability to identify nonredundant, visually salient structure in natural images. It may involve cortical V2 and appears to involve increased strength, speed, and breadth of connections within our internal representation of this complex perceptual space.