At SPIE conferences Nonlinear Image Processing VII and VIII a layered graph network for image segmentation was presented. This O(N) method often gave good results but it was not able to segment images with very strong noise. Therefore, the method is modified now. At first, instead of the used 'hard' Pixel Adjacency Graph (PAG) a 'soft' or fuzzy PAG is defined via a degree of adjacency of 4-neighbored pixels. Secondly, the averaging over 4-neighbors is applied recursively using a nonlinear weighting function which is closely connected with the degree of adjacency and which guarantees efficient noise reduction, edge preserving, and adaptation. The discrete nonlinear dynamic equation system describing the averaging process defines a Discrete Time Cellular Neural Network (CNN). Its stable states are the smoothed images. Then the soft PAG describing the edge strength' and the hard PAG defining the segments can be calculated. The method now can cope with strong noise. Some results demonstrate its smoothing and segmenting capability.