Brevet FR2871611A1 — publié le 20051216

La présente invention concerne un procédé de mise à l'échelle d'une image numérique en mode point (BitMap). Elle s'applique notamment, mais non exclusivement à l'affichage d'images sur des écrans graphiques présentant une définition relativement réduite, et/ou associés à des moyens de calcul de faible puissance, tels que ceux utilisés dans les véhicules automobiles. Elle s'applique également à l'affichage d'images dans une fenêtre d'écran de taille variable ou en vue d'effectuer des effets spéciaux tels que la rotation apparente du plan de l'image, sans nécessiter de moyens de calculs puissants. Actuellement, il existe des procédés très simples, mais qui sont limités à des multiplications ou divisions d'échelle par un facteur entier (x2 ou /2), dans lesquels on dédouble ou supprime les points de l'image dans le ratio souhaité. Ces procédés s'avèrent peu satisfaisants en terme de qualité d'image affichée. Il existe également des procédés complexes dans lesquels les points d'image ajoutés pour agrandir l'image sont calculés en fonction des points adjacents, et dans lesquels les points d'image adjacents aux points supprimés pour réduire l'image sont modifiés pour conserver une part de l'information ainsi supprimée. Il s'avère que ces procédés nécessitent d'importantes ressources mémoire et de puissance de calcul, ce qui les rend incompatibles avec les calculateurs embarqués dans 20 les véhicules automobiles. La présente invention a pour but de supprimer ces inconvénients. Cet objectif est atteint par la prévision d'un procédé de mise à l'échelle d'une image numérisée constituée d'un ensemble de pixels à répartition matricielle à deux dimensions, en vue d'être affichée dans une zone d'affichage à répartition de pixels matricielle à deux dimensions, présentant au moins une dimension modifiée par rapport à une dimension correspondante de l'image à afficher. Selon l'invention, ce procédé comprend des étapes consistant à : déterminer dans un espace numérique discret les positions respectives des points d'une droite présentant une pente égale à un facteur d'échelle de la dimension modifiée de l'image à afficher, en fonction de nombres de rangs de pixels suivant la dimension modifiée, respectivement de l'image et de la zone d'affichage, et copier ou dupliquer sélectivement dans la zone d'affichage les pixels de l'image sur la base d'une transformation définie dans l'espace numérique discret par la droite qui établit la correspondance des rangs de pixels suivant la dimension modifiée entre l'image et la zone d'affichage. Selon un mode de réalisation de l'invention, ce procédé comprend au moins une boucle de traitement portant sur la dimension modifiée de la zone d'affichage par rapport à l'image, la boucle de traitement comprenant pour chaque rang de pixels de la dimension modifiée de la zone d'affichage des étapes consistant à : - déterminer le rang de pixels correspondant dans l'image à afficher en fonction de la position du point de la droite situé au même rang que le rang de pixels suivant la dimension modifiée, extraire des pixels de l'image situés dans le rang de pixels déterminé, et insérer les pixels extraits dans le rang de pixels de la zone d'affichage. Avantageusement, les positions respectives des points de la droite sont déterminées au fur et à mesure dans la boucle de traitement. Selon un mode de réalisation de l'invention, les deux dimensions de la zone d'affichage sont différentes des dimensions de l'image à afficher, le procédé comprenant une seconde boucle de traitement portant sur l'autre dimension. De préférence, les deux boucles de traitement sont imbriquées l'une dans l'autre. Alternativement, les deux boucles de traitement sont exécutées l'une après l'autre. Selon un mode de réalisation de l'invention, la zone d'affichage présente au moins une dimension réduite par rapport à l'image à afficher, certains pixels de l'image n'étant pas extraits et placés dans la zone d'affichage, en fonction des positions respectives des points de la droite. Selon un autre mode de réalisation de l'invention, la zone d'affichage présente au moins une dimension dilatée par rapport à l'image à afficher, tous les pixels de l'image étant extraits et placés dans la zone d'affichage, et certains pixels de l'image étant n outre dupliqués dans la zone d'affichage, en fonction des positions respectives des points de la droite. Selon un autre mode de réalisation de l'invention, les étapes (a) et (b) sont exécutées en boucle avec un facteur d'échelle variant progressivement jusqu'à une valeur prédéfinie. Selon un autre mode de réalisation de l'invention, les positions respectives des 30 points de la droite sont déterminées à l'aide de l'algorithme de Bresenham. Un mode de réalisation préféré de l'invention sera décrit ci-après, à titre d'exemple non limitatif, avec référence aux dessins annexés dans lesquels: La figure 1 représente schématiquement une image dont on souhaite changer l'échelle et l'image obtenue à l'aide du procédé selon l'invention; La figure 2 représente un graphe illustrant le procédé selon l'invention; La figure 3 montre plus en détail le graphe représenté sur la figure 2 appliqué à une réduction des dimensions de l'image; La figure 4 montre plus en détail le graphe représenté sur la figure 2 appliqué à un agrandissement des dimensions de l'image. Le procédé de mise à l'échelle d'une image selon l'invention est basé sur le principe que pour la plupart des images, une opération de retrait ou d'ajout de pixels contigus qui composent l'image, fait apparaître des informations fondamentales de l'image originale, si cette opération est effectuée avec une répartition correcte. Bien entendu, ce principe n'est pas équivalent aux filtres complexes qui conduisent à de meilleurs résultats de réduction ou d'agrandissement d'image. D'un point de vue théorique, la mise à l'échelle d'une image consiste à appliquer un facteur d'échelle à chacun des axes horizontal et vertical de l'image dont l'échelle est modifiée, ce facteur pouvant bien entendu être différent sur chaque axe. Si l'on considère un seul axe dont l'échelle est modifiée, d étant le nombre de pixels ou points de l'image d'origine suivant cet axe et d' le nombre de pixels ou points suivant ce même axe de l'image que l'on cherche à obtenir, le facteur d'échelle est alors égal à r = d'/d. La figure 1 illustre le procédé selon l'invention de mise à l'échelle d'une image. Sur cette figure, l'image initiale 1 à redimensionner présente d, pixels en largeur et d2 pixels en hauteur. L'image finale 2 que l'on cherche à obtenir présente d', pixels en largeur et d'2 20 pixels en hauteur. Selon l'invention, il s'agit ensuite d'identifier en fonction du facteur d'échelle les pixels qui doivent être retirés ou dupliqués dans l'image finale pour garantir une bonne répartition des lignes et colonnes modifiées de l'image. A cet effet, pour une réduction de l'image initiale suivant l'axe horizontal (longueur des lignes) de l'image, on définit dans un espace numérique discret un rectangle dont la longueur correspond au nombre d (égal à d,) de points des lignes de l'image initiale et dont la largeur correspond au nombre d' (égal à d',) de points des lignes de l'image finale, et on trace le segment diagonal 3 de ce rectangle (Figure 2). On opère de même, selon l'axe vertical de l'image, avec le nombre de lignes (d = d2; d' = d'2) de l'image. On définit ainsi deux rectangles, à savoir un pour l'axe horizontal et un pour l'axe vertical de l'image, avec leur segment diagonal correspondant aux rapports de réduction respectivement r, = d',/d, et r2 = d'2/d2. De manière analogue, dans le cas d'une dilatation, on définit un ou des rectangles dont la longueur correspond au nombre de lignes ou de points par ligne de l'image finale, 35 et la largeur au nombre de lignes ou de points par ligne de l'image initiale. Selon l'invention, il s'agit ensuite de tracer ce segment diagonal sous une forme numérisée optimale dans l'espace numérique discret. A cet effet, on met en oeuvre un algorithme de tracé optimal de segments de droite dans un espace numérique discret, tel que l'algorithme de Bresenham qui présente l'avantage de n'utiliser que des nombres entiers et de ne mettre en oeuvre que des opérations arithmétiques simples (additions, soustractions, comparaisons et décalages multiplications ou divisions par 2). La figure 3 représente ce rectangle de dimensions d x d' dans le cas d'une réduction de l'image dont le facteur d'échelle suivant un axe (horizontal ou vertical) est 213. Sur cette figure, on a repéré en zones pointillées les points constituant le segment diagonal sous une forme numérisée optimale, obtenu par exemple à l'aide de l'algorithme de Bresenham. II s'agit en outre de transformer, respectivement selon l'axe vertical le nombre de lignes de l'image initiale en un nombre réduit correspondant à celui de l'image finale, et selon l'axe horizontal chaque ligne 4 de l'image initiale en une ligne réduite 5. Cette transformation consiste à retirer de l'image initiale soit les lignes, soit les pixels des lignes conservées, dont le point de même rang sur le segment diagonal 3 est adjacent par un côté au point de rang précédent sur ce segment. Les lignes et les pixels des lignes conservées, à retirer de l'image initiale correspondent donc aux points marqués d'une croix sur la figure 3. La réduction d'image suivant une dimension (par exemple selon l'axe vertical) peut alors être réalisée par l'algorithme suivant: Copier la ligne de rang 0 de l'image initiale 1 vers la ligne de rang 0 de l'image finale 2 Y1 = 0 Pour chaque ligne 4 de rang y de l'image initiale 1, à partir du rang 1 { Déterminer le rang Y correspondant au rang y dans le segment diagonal numérisé optimal Si Y Y1 alors Copier la ligne de rang y de l'image initiale 1 dans la ligne de rang Y de l'image finale 2 Y1 = Y Si l'image doit être réduite également suivant son autre dimension, l'opération de copie d'une ligne de l'image initiale vers une ligne de l'image finale, mentionnée dans l'algorithme précédent est sensiblement identique: Copier le pixel de rang 0 de la ligne de rang y de l'image initiale 1 vers le pixel de rang 0 de la ligne de rang Y de l'image finale 2 X1 = 0 Pour chaque pixel de rang x dans la ligne à copier de l'image initiale 1, à partir du rang 1 Déterminer le rang X correspondant au rang x dans le segment diagonal numérisé optimal Si X X1 alors Copier le pixel de rang x de la ligne de rang y de l'image initiale 1 au pixel de rang X dans la ligne de rang Y de l'image finale 2 Xl = X Bien entendu, si le facteur d'échelle est différent suivant les deux dimensions de l'image, il est nécessaire de déterminer le segment diagonal optimal pour chacune des 20 deux dimensions. Un procédé sensiblement inverse est employé pour la dilatation du nombre de lignes et de pixels par ligne de l'image initiale, comme cela est illustré par la figure 4. Cette figure représente un rectangle de dimensions d x d' dont le rapport de dilatation suivant un axe (horizontal ou vertical) est 312. Sur cette figure, on a repéré en zones pointillées les points constituant le segment diagonal 3 sous une forme numérisée optimale. Pour effectuer une dilatation, chaque point de chaque ligne 6 de l'image initiale est recopié. Il est en outre dupliqué dans la ligne correspondante de l'image finale s'il présente sur le segment diagonal numérisé optimal le même rang qu'un pixel (pixels repérés par les flèches 8) adjacent par un coté à un pixel de rang précédent. Le procédé selon l'invention permet ainsi de transformer chaque ligne 6 de l'image initiale en une ligne dilatée 7. La dilatation d'image suivant une dimension peut être réalisée à l'aide de l'algorithme suivant: Copier la ligne de rang 0 de l'image initiale 1 dans la ligne de rang 0 de l'image finale 2 Y1 = 0 10 15 Pour chaque ligne 4 de rang y de l'image initiale 1, à partir de la ligne de rang y = 1 Déterminer le rang Y correspondant au rang y dans le segment 5 diagonal numérisé optimal Si Y YI alors f Copier la ligne de rang y de l'image initiale 1 dans la ligne de rang Y de l'image finale 2 YI = Y } Sinon Dupliquer la ligne de rang y-1 de l'image initiale 1 dans la ligne de rang Y de l'image finale 2 Si l'image doit être dilatée également suivant son autre dimension, l'opération de copie d'une ligne de rang y de l'image initiale vers la ligne de rang Y de l'image finale, 20 mentionnée dans l'algorithme précédent est sensiblement identique: Copier le pixel de rang 0 de la ligne de rang y de l'image initiale 1 dans le pixel de rang 0 de la ligne de rang Y de l'image finale 2 Xl = 0 Pour chaque pixel de rang x dans la ligne à copier de l'image initiale 1, à partir du pixel de rang x = 1 Déterminer le rang X correspondant au rang x dans le segment diagonal numérisé optimal Si X X1 alors f Copier le pixel de rang x de la ligne de rang y de l'image initiale 1 dans le pixel de rang X de la ligne de rang Y de l'image finale 2 Xl = X t Sinon 15 Dupliquer le pixel de rang x-1 de la ligne de rang y de l'image initiale 1 au pixel de rang X dans la ligne de rang Y de l'image finale 2 5} I Si la mise à l'échelle (réduction ou dilatation) doit être effectuée suivant les deux dimensions de l'image, le procédé de mise à l'échelle comporte deux boucles imbriquées. Alternativement, la mise à l'échelle de l'image peut être effectuée par deux boucles exécutées l'une après l'autre, réalisant la recopie ou la duplication d'abord des lignes de l'image initiale suivant une dimension, puis de l'image obtenue à la suite de l'exécution de la première boucle suivant l'autre dimension. En variante, la mise à l'échelle d'une image peut être obtenue par l'algorithme suivant (les boucles sont effectuées sur les rangs de l'image finale au lieu de l'image initiale) : Pour chaque ligne 5 de rang Y de l'image finale 2 Déterminer le rang y correspondant au rang Y dans le segment diagonal numérisé optimal Copier la ligne de rang y de l'image initiale 1 dans la ligne de rang Y de l'image finale 2 / L'opération de copie d'une ligne de l'image initiale vers une ligne de l'image finale est sensiblement identique: Pour chaque pixel de rang X de la ligne de rang y à copier de l'image finale 2 Déterminer le rang x correspondant au rang X dans le segment diagonal numérisé optimal Copier le pixel de rang x de la ligne y de l'image initiale dans le pixel de rang X de la ligne Y de l'image finale 2 / Comme cela apparaît sur la figure 3 dans le cas d'une réduction d'image (rapport d'/d D'une manière analogue sur la figure 4 qui illustre le cas d'une dilatation d'image (rapport d'Id > 1), certains rangs X ou Y de l'image finale 2 correspondent à des rangs x ou y identiques dans l'image initiale 1. II en résulte que tous les pixels de l'image initiale sont copiés dans l'image finale, et que certains pixels de l'image initiale sont en outre dupliqués dans l'image finale. Il est à noter que le segment diagonal numérisé optimal ne comporte aucune discontinuité et aucun doublon (tous les pixels du segment diagonal du second rang à l'avant dernier rang sont adjacents à deux et seulement deux autres pixels du segment diagonal, soit par un côté, soit par un angle). Cela signifie que tous les rangs de l'image initiale suivant la dimension à mettre à l'échelle correspondent à au moins un rang de l'image finale et réciproquement, chaque rang de l'image (image initiale ou finale) la plus grande suivant la dimension à mettre à l'échelle correspondant à un seul rang de l'image la plus petite (image initiale ou finale) suivant cette dimension. L'algorithme décrit ci-avant peut être optimisé en calculant au préalable pour chaque axe (horizontal et vertical) de l'image dont la dimension est modifiée, les coordonnées dans l'espace numérique discret des points du segment diagonal numérisé optimal. Ces coordonnées sont mémorisées dans une table établissant la correspondance entre les rangs des lignes de l'image finale avec ceux des lignes de l'image initiale. En d'autres termes, chaque table fournit pour chaque rang de l'image finale suivant une dimension, la position dans l'image initiale du rang correspondant à recopier, et réciproquement. Alternativement, si les ressources mémoire du calculateur ne permettent pas déterminer et mémoriser préalablement les coordonnées respectives des points du segment diagonal numérisé optimal, l'algorithme de tracé de ce segment (détermination des coordonnées des points de ce segment) peut également être intégré aux boucles de traitement décrites ci-avant dans lequel il est déterminé progressivement au fur et à mesure de la constitution de l'image finale. Dans ce cas, on détermine les coordonnées initiales (0,0) et finales (d, d') du segment diagonal, on applique l'algorithme de tracé du segment numérique optimal, et pour chaque point de ce segment obtenu à chaque itération de l'algorithme, on copie le pixel (respectivement la ligne) du rang correspondant de l'image initiale vers l'image finale si l'ordonnée du point du segment est différente de celle du point précédent, et on élimine le pixel (respectivement la ligne) du rang correspondant ou duplique le pixel (respectivement la ligne) du rang précédent si l'ordonnée du point du segment est identique à celle du point précédent. Comme, on peut le remarquer dans les algorithmes décrits ci-avant, le procédé selon l'invention ne comporte aucune opération arithmétique complexe, telle que des multiplications ou divisions de nombres réels, coûteuses en temps de calcul. La simplicité du procédé selon l'invention lui permet d'être mis en oeuvre par un calculateur ne présentant pas d'importantes ressources mémoire et de puissance de calcul. Grâce à l'invention, le procédé selon l'invention peut ainsi également être utilisé pour obtenir certains effets spéciaux comme la mise en rotation apparente du plan d'une l'image consistant à réduire progressivement une dimension de l'image, éventuellement en introduisant un décalage des lignes suivant l'autre dimension (zone d'affichage en forme de parallélogramme). Dans ce cas, le procédé de mise à l'échelle est exécuté en boucle avec un facteur d'échelle suivant au moins une dimension variant progressivement jusqu'à une valeur prédéfinie. REVENDICATIONS 1. Procédé de mise à l'échelle d'une image numérisée (1) constituée d'un ensemble de pixels à répartition matricielle à deux dimensions, en vue d'être affichée dans une zone d'affichage (2) à répartition de pixels matricielle à deux dimensions, présentant au moins une dimension modifiée par rapport à une dimension correspondante de l'image à afficher, caractérisé en ce qu'il comprend des étapes consistant à : (a) déterminer dans un espace numérique discret les positions respectives des points d'une droite (3) présentant une pente égale à un facteur d'échelle de la dimension modifiée de l'image (1) à afficher, en fonction de nombres de rangs de pixels suivant la dimension modifiée, respectivement de l'image et de la zone d'affichage (2), et (b) copier ou dupliquer sélectivement dans la zone d'affichage les pixels de l'image sur la base d'une transformation définie dans l'espace numérique discret par la droite (3) qui établit la correspondance des rangs de pixels suivant la dimension modifiée entre l'image et la zone d'affichage. 2. Procédé selon la revendication 1, caractérisé en ce qu'il comprend au moins une boucle de traitement portant sur la dimension modifiée de la zone d'affichage (2) par rapport à l'image, la boucle de traitement comprenant pour chaque rang de pixels de la dimension modifiée de la zone d'affichage des étapes consistant à : déterminer le rang de pixels correspondant dans l'image (1) à afficher en fonction de la position du point de la droite situé au même rang que le rang de pixels suivant la dimension modifiée, extraire des pixels de l'image situés dans le rang de pixels déterminé, et 25 insérer les pixels extraits dans le rang de pixels de la zone d'affichage. 3. Procédé selon la revendication 2, caractérisé en ce que les positions respectives des points de la droite (3) sont déterminés au fur et à mesure dans la boucle de traitement. 4. Procédé selon la revendication 2 ou 3, caractérisé en ce que les deux dimensions de la zone d'affichage (2) sont différentes des dimensions de l'image (1) à afficher, le procédé comprenant une seconde boucle de traitement portant sur l'autre dimension. 5. Procédé selon la revendication 4, caractérisé en ce que les deux boucles de traitemént sont imbriquées l'une dans l'autre. 6. Procédé selon la revendication 4, caractérisé en ce que les deux boucles de traitement sont exécutées l'une après l'autre. 7. Procédé selon l'une des revendications 1 à 6, caractérisé en ce que la zone d'affichage (2) présente au moins une dimension 5 réduite par rapport à l'image (1) à afficher, certains pixels de l'image n'étant pas extraits et placés dans la zone d'affichage, en fonction des positions respectives des points de la droite (3). 8. Procédé selon l'une des revendications 1 à 6, caractérisé en ce que la zone d'affichage (2) présente au moins une dimension dilatée par rapport à l'image (1) à afficher, tous les pixels de l'image étant extraits et placés dans la zone d'affichage, et certains pixels de l'image étant n outre dupliqués dans la zone d'affichage, en fonction des positions respectives des points de la droite (3). 9. Procédé selon l'une des revendications 1 à 8, caractérisé en ce que les étapes (a) et (b) sont exécutées en boucle avec un 15 facteur d'échelle variant progressivement jusqu'à une valeur prédéfinie. 10. Procédé selon l'une des revendications 1 à 9, caractérisé en ce que les positions respectives des points de la droite (3) sont déterminés à l'aide de l'algorithme de Bresenham.