The problem of shrinking the connected components of binary images to small residues is addressed. A new parallel algorithm is presented with the lowest known worst case time complexity as measured by iteration counts, i.e., ?(nc+nr)/2? iterations where the foreground of the image is contained within a rectangular region of size ncxnr pixels. The new algorithm also demonstrates superior average iteration counts in comparison with other shrinking algorithms on test images. The new algorithm uses a fully parallel application of an operator with an 8 pixel support. It reduces all connected components in any two-dimensional (2D) binary image to certain small 1, 2, or 3 pixel residues. It is potentially useful for component counting, as a fundamental step in connected component labeling algorithms implemented with fine grain realizations in 2D mesh computing architectures, and in other applications requiring preservation of foreground topology (connectivity).