Bitmaps
A bitmap (BMP) is essentially what you describe, an array of numbers that represent pixel colors. E.g. something like
1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1
Lossless compression
Now, let's define a compression scheme. In our compression scheme, we will have an array of pairs of numbers. E.g.
3, 1, 1, 0, 7, 1
Now, the first thing I want to point out is that this compression scheme represents the same pixels as the first array. The first array has three 1s followed by a single 0 and then seven 1s. And that's what we're representing here. This format is shorter, as it represents multiple pixels with two numbers. The bitmap format has to use one number for each pixel.
Obviously this is a somewhat simplified view of an image (e.g. it's just one row) and a compression scheme. But hopefully this allows you to see how a compression scheme changes the format of an image. This is how a GIF relates to a BMP. GIF uses a compression scheme called Lempel-Ziv-Welch instead of this simplistic one.
What we've described here is a lossless compression scheme. A problem with lossless compression schemes is that for some inputs, the encoded form may be longer than the original. E.g. for
1, 0, 1, 0, 1
The encoding is
1, 1, 1, 0, 1, 1, 1, 0, 1, 1
Well, that was useless. We made the input twice as long.
Another lossless compression
Now, let's consider a different compression scheme. In this one, we will represent the image as overlaid circles. For each circle, we will define a center, a radius, and a color.
Our first bitmap would become
5, 5, 1, 3, 0, 0
This is the same length as our first compression method.
And our second could be either
2, 2, 1, 2, 1, 0, 2, 0, 1
This is three circles centered at the middle element (which in computer counting is number 2, as computers start counting at 0). One circle has radius 2 and color 1. Then we add a circle of color 0 and radius 1. Finally, we have a circle of color 1 and radius 0. In steps, this would be
1, 1, 1, 1, 1
1, 0, 0, 0, 1
1, 0, 1, 0, 1
Or
2, 2, 1, 1, 0, 0, 3, 0, 0
This is the same initial circle but covered by two point circles. In steps, it would be
1, 1, 1, 1, 1
1, 0, 1, 1, 1
1, 0, 1, 0, 1
These are both one shorter than the first encoded version but still longer than the original.
You may wonder why I'm talking about circles and not ranges. The main reason is that circles are closer to what real two dimensional images use.
Lossy compression
We also have the concept of lossy compression schemes. These lossless compression schemes can be turned back into the original bitmap array. Lossy compression schemes may not be reversible.
Let's consider a lossy version of our circles method. In this, we will use a simple rule. We won't store any circles with a radius less than 1. So in our last two encodings, we would instead have
2, 2, 1, 2, 1, 0
and
2, 2, 1
which converted to pixels again are
1, 0, 0, 0, 1
and
1, 1, 1, 1, 1
The first version is only one element longer than the original. The second version is shorter. Both are valid, so the algorithm is free to develop both and pick the shorter one.
We describe images with more restrictive rules as being of lower quality.
This representation of images as overlaid collections of circular shapes is similar to how the Joint Photographic Experts Group or JPEG format works. Its shapes are ellipses rather than circles, but the idea is similar. Rather than our simplistic method, it uses the discrete cosine transform to encode images.
Unlike GIF, JPEG is actually a different way of representing the image. GIF is still pixels. They are just stored in a different way. JPEG is shapes. To view a JPEG, we then convert the shapes into pixels because that's how screens work. In theory, we could develop a screen that did not work this way. Instead of pixels, it could produce shapes so as to better match the JPEG format. Of course, that screen wouldn't be able to show bitmaps. To display a BMP or GIF, we'd have to convert to JPEG.
If you convert a standard GIF, say 300x300 pixels, convert it into a JPEG, and crank the quality way down, the base shapes that it uses should be visible. Many JPEGs avoid these artifacts by starting with a much higher resolution image.
JPEGs scale well because they are shapes rather than pixels. So if you start with an 8000x8000 image, convert it to JPEG, and display it as a 300x300 image, much of the detail that was lost would have been lost anyway. If you converted the 8000x8000 bitmap to a 300x300 bitmap first and then to JPEG, the results will often be of lower quality.
MPEG
We've been talking about still images. The Moving Picture Experts Group or MPEG format uses the same kind of compression as JPEG, but it also does something else. While a simple way of doing video is to send a sequence of still images, MPEG actually sends a frame, followed by some number of frames listing changes, and finishing with an end frame. Because most frames are similar to the previous frame, the list of changes is often smaller than a second image would be.
The sequence normally isn't that long, say five frames. But it helps make the stream smaller than it otherwise would be.
Simplifications
I've ignored a lot. My images only have two colors (1-bit), not the 256 of an 8-bit image and certainly not the 4,294,967,296 of a 32-bit image. Even with 8-bit images, note that you can often choose different palettes for the image. So two 8-bit bitmaps with the same sequences may represent images that look different (same shape but different colors).
My images are single rows, not two dimensional. Most images will have a specific row size stored, making the arrays two-dimensional.
I haven't tried to represent the actual encodings at all. They are much more complex than the simple ones that I used. I did this because I wanted to be able to describe the encodings in this post. I'm not convinced that I could explain Lempel-Ziv much less the more complex Lempel-Ziv-Welch refinement in a single answer. And I don't understand Fourier transforms well enough to explain them at any length.
This is very much a simplified version of actual image handling. However, I feel that for didactic purposes, it is easier to understand than the more complex reality while still hitting the essential points.