Algorithmes pour la réduction de la taille des fonts bitmap

Ceci fait suite à cette question .

Je travaille sur une application C de bas niveau sur laquelle je dois dessiner du texte. J’ai décidé de stocker la police que je veux utiliser sous forme de tableau (noir et blanc, chaque caractère 128×256, peut-être), puis de la réduire à la taille dont j’ai besoin avec un algorithme (en niveaux de gris, afin que je puisse avoir une image brute le lissage des fonts).

Remarque: ceci est un projet de jouet, veuillez ignorer des choses comme faire des calculs au moment de l’exécution ou non.

La question est, quel algorithme?

J’ai regardé 2xSaI , mais c’est plutôt compliqué. Je voudrais quelque chose pour lequel je peux lire la description et élaborer le code moi-même (je suis débutant et je code en C / C ++ depuis un peu moins d’un an).

Des suggestions, n’importe qui?

Merci pour votre temps!

Édition: Veuillez noter que l’entrée est en noir et blanc, la sortie doit être lissée en niveaux de gris.

Déterminez le rectangle dans l’image source qui correspondra à un pixel de destination. Par exemple, si votre image source est 50×100 et votre destination 20×40, le pixel supérieur gauche de la destination correspond au rectangle compris entre (0,0) et (2.2,2.2) dans l’image source. Maintenant, faites une surface moyenne sur ces pixels:

  • L’aire est 2.2 * 2.2 = 4.84. Vous allez redimensionner le résultat de 1 / 4,84.
  • Les pixels à (0,0), (0,1), (1,0) et (1,1) pèsent chacun à 1 unité.
  • Les pixels à (0,2), (1,2), (2,0) et (2,1) pèsent chacun à 0,2 unité (car le rectangle n’en couvre que 20%).
  • Le pixel en (2,2) pèse 0,04 (car le rectangle n’en couvre que 4%).
  • Le poids total est bien sûr de 4 * 1 + 4 * 0,2 + 0,04 = 4,84.

Celui-ci était simple car vous avez commencé par aligner les pixels source et cible de manière uniforme au bord de l’image. En général, vous aurez une couverture partielle sur les 4 côtés / 4 coins du rectangle glissant.

Ne vous embêtez pas avec des algorithmes autres que la moyenne surfacique pour la réduction d’échelle. La plupart d’entre eux sont tout à fait faux (ils entraînent un alias horrible, du moins avec un facteur inférieur à 1/2) et ceux qui ne sont pas tout à fait faux sont bien plus pénibles à mettre en œuvre et ne vous donneront probablement pas de meilleurs résultats. .

Considérez que votre image est un bitmap N * M BW. Pour plus de simplicité, considérons-la char Letter[N][M] , lorsque les valeurs admissibles sont 0 et 1 . Maintenant, considérez que vous voulez le réduire à la unsigned char letter[n][m] . Cela signifie que chaque pixel en niveaux de gris de letter sera calculé en tant que nombre de pixels blancs dans la grande image:

 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); }; 

Notez que les rectangles qui créent des pixels peuvent se chevaucher (dans le cas où les tailles ne sont pas divisibles). Plus le bitmap d'origine est volumineux, mieux c'est.

La mise à l’échelle d’une police bitmap pose le même problème que la mise à l’échelle de tout autre bitmap. La classe générale d’algorithme que vous recherchez est l’ interpolation . Il y a plusieurs façons de le faire – en général, plus le résultat est visuellement précis, plus l’algorithme est compliqué. Vous pouvez commencer par regarder (par ordre croissant de complexité):

  • Voisin le plus proche
  • Interpolation bilinéaire
  • Interpolation bicubique

C’est assez simple. Si tout ce que vous avez est une police bitmap au lieu d’une police de contour, vous avez un choix très limité de choix d’une couleur de pixel anti-aliasing. Par exemple, si la taille du sharepoint police bitmap est exactement quatre fois plus grande que la taille du point d’affichage souhaitée, vous ne pouvez obtenir que 16 choix distincts. Nombre de pixels “allumés” dans le rectangle de mappage 4×4.

Avoir à traiter avec la cartographie fractionnaire est un exercice de programmation, mais pas un qui améliore la qualité.

S’il est acceptable de contraindre la réduction d’échelle à des multiples de 2 (50%, 25%, 12,5%, etc.), un algorithme très simple et plutôt efficace consiste à créer chaque pixel réduit en tant que vote majoritaire de tous les pixels source. Par exemple, à 50%, un carré de quatre pixels forme le pixel réduit: si zéro ou l’un d’eux est activé, la sortie est désactivée; si trois ou quatre sont activés, la sortie est activée. Le cas artistique (pour deux pixels activés), activez ou désactivez toujours l’option, ou observez les autres pixels environnants pour déterminer le départage.