Recently, much attention has been paid on the recognition of graphical objects, like company logos and trademarks. Recognizing these objects facilitates the recognition of document class. Some promising results have been achieved by using Autoassociator-based Artificial Neural Networks (AANN) also in the presence of homogeneously distributed noise. However, the performance drops significantly when dealing with spot-noisy logos, where strips or blobs produce a partial obstruction of the pictures.In this paper, we propose a new approach for training AANNs especially conceived for dealing with spot noises. The basic idea is that of introducing a new norm for assessing the reproduction error in AANNs. The proposed algorithm, which is referred to as Spot-Backpropagation (S-Bp), is significantly much more robust with respect to spot-noise than classical Euclidean norm-based Backpropagation (Bp). Our experimental results are based on a database of 88 real logos that are artificially corrupted by spot-noise.