Algorithms for downscaling bitmapped fonts

Question

This is a follow-up to this question.

I am working on a low level C app where I have to draw text. I have decided to store the font I want to use as an array (black and white, each char 128x256, perhaps), then I'd downscale it to the sizes I need with some algorithm (as grayscale, so I can have some crude font smoothing).

Note: this is a toy project, please disregard stuff like doing calculations at runtime or not.

Question is, which algorithm?

I looked up 2xSaI, but it's rather complicated. I'd like something I can read the description for and work out the code myself (I am a beginner and have been coding in C/C++ for just under a year).

Suggestions, anyone?

Thanks for your time!

Edit: Please note, the input is B&W, the output should be smoothed grayscale

Answer 1

Figure out the rectangle in the source image that will correspond to a destination pixel. For example if your source image is 50x100 and your destination is 20x40, the upper left pixel in the destination corresponds to the rectangle from (0,0) to (2.2,2.2) in the source image. Now, do an area-average over those pixels:

• Area is 2.2 * 2.2 = 4.84. You'll scale the result by 1/4.84.
• Pixels at (0,0), (0,1), (1,0), and (1,1) each weigh in at 1 unit.
• Pixels at (0,2), (1,2), (2,0), and (2,1) each weigh in at 0.2 unit (because the rectangle only covers 20% of them).
• The pixel at (2,2) weighs in at 0.04 (because the rectangle only covers 4% of it).
• The total weight is of course 4*1 + 4*0.2 + 0.04 = 4.84.

This one was easy because you started with source and destination pixels lined up evenly at the edge of the image. In general, you'll have partial coverage at all 4 sides/4 corners of the sliding rectangle.

Don't bother with algorithms other than area-averaging for downscaling. Most of them are plain wrong (they result in horrible aliasing, at least with a factor smaller than 1/2) and the ones that aren't plain wrong are a good bit more painful to implement and probably won't give you better results.

Answer 2

Consider that your image is a N*M BW bitmap. For simplicity we'll consider it char Letter[N][M], when allowable values are 0 and 1. Now consider that you want to downscale it to the unsigned char letter[n][m]. This will mean that each greyscale pixel from letter will be computed as number of white pixels in the big bitmap:

char Letter[N][M];
unsigned char letter[n][m];
int rect_sz_X = N / n; // the size of rectangle that will map to a single pixel
int rect_sz_Y = M / m; // in the downscaled image
int i, j, x, y;
for (i = 0; i < n; i++) for (j = 0; j < m; j++){
    int sum = 0;
    for (x = 0; x < rect_sz_X; x++) for (y = 0; y < rect_sz_Y; y++)
        sum += Letter[i*rect_sz_X + x][j*rect_sz_Y + y];
    letter[n][m] = ( sum * 255) / (rect_sz_X * rect_sz_Y);
};

Note that the rectangles that creates pixels could overlap (in case when sizes aren't divisible). The larger is your original bitmap, the better.

Answer 3

Scaling a bitmapped font is the same problem as scaling any other bitmap. The general class of algorithm that you're after is interpolation. There's quite a few ways to do this - in general, the more visually accurate the result, the more complicated the algorithm. You could start by looking at (in increasing order of complexity):

• Nearest-neighbour
• Bilinear interpolation
• Bicubic interpolation

Answer 4

It's pretty simple. If all you've got is a bitmapped font instead of an outline font then you have very limited choices in picking an anti-aliasing pixel color. For example, if the bitmapped font point size is exactly four times as large as the desired display point size then you can only ever get 16 distinct choices. The number of 'lit' pixels in the 4x4 mapping rectangle.

Having to deal with fractional mapping is a programming exercise but not one that improves the quality.

Answer 5

If it is acceptable to constrain the downscaling to multiples of 2 (50%, 25%, 12.5%, etc.), then a very simple and fairly good algorithm is to create each downscaled pixel as the majority vote of all the source pixels. For example, at 50%, a square of four pixels are forming the one downscaled pixel: if zero or one of them is on, then the output is off; if three or four are on, then the output is on. The artistic case (for two pixels on), either always choose on or off, or look at other surrounding pixels for tiebreaking.