The design of automatic systems dedicated to satellite image classification has received considerable attention. However, the current systems still cannot compare with human photo-interpreters. A promising approach consists in integrating structural knowledge into the classification process, i.e., using information about the shape of and the spatial relations between the regions that are to be determined. The present work tackles this issue, and relies on soft computing techniques. First, a fuzzy classifier produces a fuzzy partition of the image. Then, the defuzzified (crisp) partition is tried to be improved. According to the membership degrees in the fuzzy partition, the system selects a set of pixels and associates a set of candidate classes with each of them. The initial crisp partition is improved by reassigning each selected pixel to one of the classes it may belong to. This is performed by a combinatorial optimization strategy. The aim is to maximize the adequacy between the regions defined by the crisp partition and the structural knowledge which is available. First experiments on remote sensing data show the applicability of our approach.