AFAIK the majority of compression in GIF and PNG comes from local similarity. GIF uses run-length encoding. PNG pixels can copy the color to their left, or any of the three pixels above them.

The smoothness of natural images is why Quite Okay Imaging can compete with PNG, despite touching each pixel exactly once.