Believe it or not, there is actually a grain of truth to those scenes in the TV shows and movies where geeky technicians use software to seemingly reconstruct a high-resolution crime scene from a woefully pixelated source image or video. There is actually a way of using software to increase the image quality of enlarged images.
The technique is called super-resolution, and there are two basic approaches. The first approach takes a bunch of similar images of the same object, and then uses an algorithm to create a single image with the best (sharpest) bits from each. The second approach is slightly more magical. In any given image, the same pattern of pixels usually appears multiple times — tiles on a floor, bricks on a wall, wrinkles on a face, spots on a butterfly. In each case, though, because we live in a 3D world, these patterns are slightly different sizes, and each pattern has a slightly different subpixel shift. If you group together enough of these pixel patterns, and take the best subpixels from each, you can work out how that pattern actually looks in reality.
In short, it’s possible to take a blurry or low resolution image, and gain image quality by enlarging it with super-resolution techniques. As you can see from the sample images in this article, super-resolution can produce some startling results.
If you want to play with super-resolution yourself, Supreme is an open source implementation written in Python. Commercial products such as Perfect Resize also implement super-resolution features that are very similar to the one described here. As to why the kingpin of image manipulation, Photoshop, is stuck with boring old bicubic enlargement… who knows.