Brevet FR2892537A1 — publié le 20070427

- 1- " Procédé pour redimensionner un objet graphique." La présente invention concerne un procédé pour redimensionner un 5 objet graphique structuré, de préférence objet graphique vectoriel, de façon à obtenir un objet graphique intermédiaire de taille différente. D'une façon générale, il existe de plus en plus de solutions disponibles pour les graphistes pour directement élaborer un graphisme pour des applications visuelles sans que cela nécessite la traduction, par un lo programmeur, de leur travail en code informatique. Par exemple, Macromedia Director permet à des graphistes d'établir des applications simples de multimédia. Le HTML et les éditeurs "Flash" leur permettent de construire des pages Web et des graphismes pour des applications Web. Plus récemment, IntuiKit propose une solution pour fusionner des graphismes avec des 1s composants logiciels traditionnels de plus grandes applications, voir notamment le document : S. Chatty, S. Sire, J. Vinot, P. Lecoanet, C. Mertz, et A. Lemort; "Revisiting visual interface programming: Creating GUI tools for designers and programmers." Dans Proceedings of the ACMUIST, pages 267-276; Addison-Wesley, Oct. 2004. Cependant, beaucoup de graphistes sont 20 disposés à aller plus loin et à prendre plus de contrôle dans la programmation des interfaces utilisateurs. Une fois utilisés dans une application interactive, leur graphisme est souvent adapté pour refléter des changements de contexte ou des variations de données, et le contrôle de ces changements devrait faire partie de leur travail. En particulier, certains graphistes 25 souhaiteraient contrôler l'agencement visuelle et ses changements. En effet, une fois impliqués dans la conception visuelle des interfaces utilisateurs graphiques, les graphistes peuvent faire plus que fournir simplement un graphisme statique à des programmeurs qui vont ensuite l'incorporer dans des applications. Ils sont disposés à décrire des contraintes 3o sur la façon dont les visuels devraient être modifiés une fois adaptés à une nouvelle taille ou une fois utilisés pour représenter des données dynamiques. Un certain nombre de techniques automatisées sont disponibles pour contrôler l'agencement des interfaces visuelles. Elles s'étendent de la simple remise à l'échelle des objets graphiques à une optimisation plus 35 complexe et à des algorithmes de résolution de contraintes. Cependant, la - 2 plupart des techniques sont destinées aux programmeurs et ne fournissent pas un niveau de contrôle suffisamment élevé pour les graphistes. Elles ne tiennent pas compte du fait que l'oeil est un instrument subjectif et que des déformations doivent être appliquées aux objets afin de créer une illusion de remise à l'échelle sans heurt. En conséquence, les graphistes doivent choisir entre accepter une remise à l'échelle sous-optimale des objets, fournissant un graphisme pour chaque taille prévue, ou demander aux programmeurs d'élaborer une fonction spécifique pour chaque objet. On connaît le document "Inferring constraints from multiple io snapshots", D. Kurlander and S. Feiner. ACM Trans. Graph., 12(4):277-304, 1993, qui décrit un système, "Chimera system", permettant de déduire, à partir de plusieurs graphismes, des invariants géométriques tels que des incidences, des distances relatives et des pentes. Cependant, ce système peut impliquer des contraintes excessives ou des règles fortuites, 15 ce qui nécessite parfois d'élaborer un grand nombre d'exemples pour évacuer toute contrainte indésirable. En outre, la recherche étendue des invariants-est processus cou eux. L'un des problèmes techniques que la présente invention se propose de résoudre, est que le redimensionnement des objets graphiques actuels 20 peut aboutir à des objets graphiques redimensionnés dans lesquels le contenu informatif n'est plus visible, donc accessible. La présente invention a pour but de remédier aux inconvénient précités en proposant un procédé de redimensionnement simplifié, rapide et applicable à des graphismes vectoriels. 25 On atteint au moins l'un des objectifs précités avec un Procédé pour redimensionner un objet graphique structuré, de préférence un objet graphique vectoriel, de façon à obtenir un objet graphique intermédiaire de taille différente, ce procédé comprenant les étapes suivantes : élaboration d'une pluralité de reproductions dudit objet graphique, 3o chaque reproduction présentant un dimensionnement donné, extraction d'un ensemble de matrices de transformation affine pour chaque reproduction, application d'une interpolation orthogonale sur les matrices de transformations affines de façon à déduire des matrices 35 intermédiaires de transformation affine pour tout objet graphique - 3 intermédiaire de taille différente de celle desdites reproductions; ladite interpolation orthogonale consistant en une interpolation séparée de la première ligne des matrices de transformation selon au moins la largeur, et de la deuxième ligne des matrices de transformation selon au moins la hauteur; et - déduction des caractéristiques géométriques dudit objet graphique intermédiaire à partir des matrices intermédiaires. La présente invention s'applique principalement sur des graphismes structurés, c'est à dire des graphismes avec des primitives dotées de lo transformations affines et non sur des graphismes bitmap. D'une façon générale, une transformation affine est caractérisée par une matrice homogène comportant six coefficients. La présente invention se distingue clairement des algorithmes existants d'interpolation d'une seule matrice globale consistant à un 15 redimensionnement naïf de type remise à l'échelle. En effet, selon l'invention chaque reproduction est dotée de plusieurs matrices de transformations, une par primitive graphique. On extrait cet ensemble de matrices pour chaque exemple et on les interpole deux à deux, par exemple, si le graphisme est constitué d'un triangle et d'un carré, on interpole la matrice associée au 20 triangle de la reproduction 1 avec celle associée au triangle de la reproduction 2, puis on fait de même avec la matrice associée au carré. Interpoler plusieurs matrices permet de générer des déformations locales. La présente invention est notamment remarquable par le fait que les variables d'interpolation comprennent au moins la largeur et la hauteur de 25 l'objet graphique intermédiaire recherché. Contrairement aux algorithmes existants utilisés notamment dans le domaine des animations (flash, par exemple), on utilise ici la dimension comme variable d'entrée et non pas le temps. L'interpolation orthogonale consiste à réaliser uniquement des 3o interpolations linéaires entre, d'une part les largeurs des reproductions et la première ligne des matrices de transformation affine, et d'autre part les hauteurs des reproductions et la seconde ligne des matrices de transformation affine. En fait, l'interpolation génère une fonction pour laquelle le domaine de départ est bidimensionnel et comprend la largeur et la hauteur, 35 et le domaine d'arrivé est constitué des matrices de transformation. - 4- En fait, chaque reproduction est une copie déformée de l'objet graphique, et cette reproduction est visuellement acceptable par l'homme du métier. On élabore donc un nombre limité de reproductions à des tailles différentes. Les dimensionnements intermédiaires vont être déduits par algorithme. La présente invention peut donc être scindée en deux grandes étapes : une première étape d'élaboration de copies à des tailles données, puis une seconde étape de détermination dudit objet graphique à des tailles différentes. Avec la présente invention, les objets graphiques peuvent être modifiés tout en respectant un certain nombre de contraintes notamment basées sur les reproductions prédéfinies. Ces reproductions prédéfinies sont comme des jalons traçant un chemin qui est obligatoirement emprunté par toute modification de l'objet graphique. Ainsi, chaque modification de l'objet graphique aboutit à un objet graphique qui est visuellement acceptable. is Par ailleurs, la présente invention peut avantageusement s'appliquer aux objets définis par des fichiers au format SVG ("scalable vector graphics"). Elle peut s'intégrer à des outils de conception actuels et permettre à l'homme du métier qui peut être un graphiste d'avoir une part importante, vis à vis d'un programmeur, dans la conception d'une application graphique par 20 exemple. Par rapport notamment au document de Chimera, la présente invention aborde une approche complètement nouvelle. En effet, au lieu de rechercher explicitement des invariants comme dans Chimera, on utilise une technique simple d'interpolation qui préserve des invariants comme conséquence 25 normale de ses propriétés mathématiques. L'un des avantages est que les calculs de redimensionnement sont très rapides, même avec des vecteurs graphiques extrêmement complexes. Ladite interpolation peut être de type polynomial, mais de préférence elle est de type linéaire par morceaux. En fait, il s'agit d'un algorithme linéaire 30 lorsque appliqué à deux reproductions. Mais lorsque le nombre de reproductions est supérieur à deux, on utilise l'interpolation linéaire par morceaux ("piecewise linear" en langue anglaise). D'une façon générale, chaque reproduction présente une structure arborescente semblable à celle de l'objet graphique initial. Chaque reproduction comporte donc le même 35 nombre de primitives graphiques, donc le même nombre de matrices de - 5 transformation. L'interpolation linéaire par morceaux permet de considérer les matrices disposées dans des emplacements identiques de l'arborescence de chaque reproduction, et ce deux par deux. En d'autres termes, si l'on prend une transformation T comme fonction s d'un scalaire t représentant, par exemple le temps. On note t la variable d'entrée et T la variable de sortie. On suppose connus les deux points (tl,T1) et (t2,T2). Les techniques d'interpolation permettent de déduire la matrice T pour chaque t compris entre ti et t2, la plus simple de ces techniques est l'interpolation linéaire de la matrice des coefficients. L'homme du métier io comprendra aisément que l'on parle de techniques d'interpolation lorsque l'on recherche un point compris entre deux points prédéterminés, et que l'on désignera par techniques d'extrapolation lorsque l'on recherche un point non compris entre deux points prédéterminés. Dans le domaine des graphismes vectoriels, la géométrie est is généralement décrite par des transformations affines. De telles transformations sont par exemple une translation et une mise à l'échelle, utiles pour le codage de l'emplacement et de la taille des primitives graphiques, aussi bien qu'une rotation et un cisaillement. Les transformations affines sont dans la plupart des cas formulés en utilisant des coordonnées 20 homogènes de sorte que les six coefficients qui caractérisent la transformation puissent être regroupés dans une seule matrice T de transformation : a11 a12 a13 - Q21 a22 a23 0 0 1 x 1 T L'interpolation orthogonale selon l'invention permet de simplifier les 25 calculs et d'accélérer le traitement. En effet, lorsqu'on est en présence de plus de deux reproductions, en appliquant l'interpolation orthogonale, on fait une hypothèse simplificatrice qui ramène le calcul au cas de deux interpolations linéaires monovariées. Cette hypothèse est que la largeur agit seulement sur les trois coefficients de la matrice de transformation qui 3o contribuent à la coordonnée x d'un point transformé (la première ligne de la matrice). De la même manière, les trois coefficients sur la deuxième ligne 20 6 sont linéairement interpolés avec la hauteur. Cette technique simple d'interpolation de transformation est donc appelée interpolation orthogonale. Encore plus précisément, avec la définition mathématique de l'interpolation orthogonale, on peut introduire la notion de compatibilité entre s des exemples (des reproductions) en terme d'interpolation orthogonale. Définition 1 : on définit un exemple comme étant un couple E=(w, h,T), où EE 9Î et T est une matrice de transformation 2-D. Définition 2 : deux exemples E1=(wl,hl,T1) et E2=(w2,h2,T2) sont dits compatibles en terme d'interpolation orthogonale lorsque : l0 w1= w2 = {a,' = a2' }j e [1,3] et hl = h2 = {a;' = az' }j e [1,3] où a et aZ sont des coefficients des matrices T1 et T2 respectivement. Définition 3 : soit E1=(wl,hl,T1) et E2=(w2,h2,T2) deux exemples 15 compatibles. L'interpolant orthogonal de El et E2 est la fonction : - lin lin lin I(wl,ai ) (w) ~(wl,ai ),(w2,âz2 ) (1'0 1(w1,a13),(w2,as) (w) lin ( \ lin lin ~(hl,ar),(h2,az )lhl ~(hl,ai2),(h2,ap)(h) 1(hl.ai3),(h2,a;3)(h) 0 0 1 - -1(xl,,,I),(x2,,,2) est I"'interpolant linéaire de (xl,yl) et (x2,y2), c'est à dire, la fonction (x,y)H (x2ùx)yl+(xùxl)y2 si xl≠x2 et (x,y)ù>yl sinon. x2ùxl - - a; et a sont des coefficients des matrices Ti et T2 respectivement. La définition peut être généralisée à plus de deux exemples, c'est à dire étendue à en remplaçant l'in par l'interpolant linéaire par morceaux. 25 Lorsque l'interpolation orthogonale est appliquée sur des transformations affines , on peut introduire des objets géométriques concrets, c'est à dire des points, des lignes, des formes, pour comprendre son effet sur les objets graphiques. La déduction des formes géométriques est réalisée de façon conventionnelle en appliquant, en local, les matrices obtenues par 30 interpolation orthogonale sur l'une des reproductions. IE1,E2 (wh)HT= où . - 7 Selon l'invention, pour deux reproductions dont les matrices de transformation affine sont Ti et T2, on note IT1,T2 un interpolant orthogonal permettant de générer une famille de matrices de transformations intermédiaires (il y a autant d'interpolants que de valeurs de w1,hi,w2,h2); et pour Pl, P2 et P des points obtenus par transformation d'un même point du plan via Ti, T2 et la transformation intermédiaire IT1,T2 respectivement, on déduit P(x,y) à partir de Pl(xl,yi) et P2(x2,y2) en utilisant la formule suivante : h" I(wl,xl),(w2,x2) (W) I ``" (h) (hl,Yl),(h2,Y2) avec IT,,T, = I(w ,h1,TI),(w2,h2,T2) , c'est à dire P .Â io une interpolation orthogonale ayant comme sortie des matrices T, et comme variables des largeurs w et des hauteurs h. Ainsi, on voit que P résulte simplement de la double interpolation linéaire de P1 et P2 selon l'axe x et l'axe y séparément. D'autres avantages et caractéristiques de l'invention apparaîtront à 15 l'examen de la description détaillée d'un mode de mise en oeuvre nullement limitatif, et des dessins annexés, sur lesquels : - La figure 1 est une vue de trois reproductions d'un objet graphique; - La figure 2 est un organigramme illustrant des étapes successives mises en oeuvre dans la présente invention; 20 Les figures 3a et 3b illustrent le redimensionnement d'objet graphique selon l'art antérieur; - La figure 3c illustre le redimensionnement d'un objet graphique selon la présente invention; La figure 4 est une spécification de type SVG de l'objet graphique de 25 la figure 3c; - La figure 5 illustre une interprétation géométrique de l'interpolation orthogonale; et - Les figures 6a à 6e illustrent les propriétés conservatives d'une interpolation orthogonale. 30 Sur la figure 1, on voit trois reproductions qui sont des copies d'un objet graphique. Chaque copie est de taille différente et a été élaborée de façon à ce qu'elle soit visuellement acceptable, c'est à dire que des éléments essentiels restent distinctifs. Ces reproductions sont des copies clés à partir desquelles le procédé selon l'invention est mis en oeuvre. Sur la figure 2, on - 8 extrait à l'étape 4, pour chaque copies 1, 2 et 3, un ensemble de matrices de transformation affine 5, 6 et 7 respectivement. Ensuite, on applique une interpolation orthogonale à l'étape 8 sur l'ensemble des matrices de transformation affine. Le résultat est une fonction qui pour une largeur et une hauteur données fournit les matrices de transformation affine correspondant à l'objet graphique 9 de dimension respectant lesdites largeur et hauteur données. On voit sur les figures 3a et 3b le redimensionnement d'un objet graphique selon l'art antérieur. On remarque que les éléments essentiels, comme le "OK", ne restent pas distinctifs quel que soit la taille de l'objet graphique. Alors que sur la figure 3c selon la présente invention, les copies clés ont été élaborées de telle sorte que le "OK" reste visible pour toute taille de l'objet graphique. Sur cette figure 3c, on a préservé et respecté les contraintes liées au texte, la largeur des bordures et les contours des rectangles. Les spécifications SVG de l'objet de la figure 3c sont représentées sur la figure 4 avec trois parties d'un bouton et leur boîte limite. Pour une même rangée, les boutons de différentes tailles ont été élaborés de telle sorte que chacun d'eux apparaît visuellement acceptable pour l'homme du métier, un graphiste par exemple. Ces critères de visibilité acceptable peuvent être aisément fixés par l'homme du métier. Les boutons de tailles intermédiaires sont donc déduits par le procédé selon l'invention. Le schéma de la figure 5 illustre une interprétation géométrique de l'interpolation orthogonale. L'axe des ordonnées représente la hauteur h, alors que l'axe des abscisses représente la largeur w. Sur ce schéma, on a appliqué une transformation intermédiaire T à un point O, avec T = I( (Q o),Tl),( 1,I),T2) (0.75,0.25) Ti et T2 sont deux reproductions dont les matrices de transformation affine. P1, P2 et P sont des points obtenus par transformation d'un même point du plan via Ti, T2 et la transformation intermédiaire IT1,T2 respectivement. La méthode reste vraie lorsque les transformations intermédiaires sont appliquées à des formes ou des tuples de points : calculer une transformation IT1,T2 interpolée avant de l'appliquer à un tuple de points est identique à appliquer les deux transformations Ti et T2 puis une interpolation sur chaque point comme décrit ci-dessus. - 9 L'interpolation orthogonale peut aussi s'appliquer à des graphismes comportant plusieurs formes, chacune ayant sa propre transformation. Soit deux tuples de formes et (S2',...,SZ) obtenus après avoir appliqué et (TI,...,Tn) à un tuple de formes initial. L'interpolation orthogonale peut facilement se généraliser à des tuples de transformations en réalisant une interpolation sur chaque paire (T,`,TZ') de façon séparée. Des objets composites intermédiaires peuvent encore être obtenus par une interpolation directe de chaque paire de points (P',P2) , avec et ~PZ,...,P2 } étant tous les points obtenus en décomposant les formes et (S2' ,...,S2 . Sur la figure 6 sont représentées des transformations d'un ensemble de graphismes vers d'autres graphismes de façon à mettre en évidence les propriétés conservatives de l'interpolation orthogonal. Une propriété conservative pour l'interpolation orthogonale est une propriété géométrique qui, si vérifiée sur deux tuples de formes obtenus après application de et (T2 ,...,T2), est encore vérifiée sur n'importe lequel des tuples intermédiaires obtenus par interpolation orthogonale. Des propriétés conservatives intéressantes peuvent être déduites de la propriété dite d'indépendance structurelle, et du fait que, comme pour des transformations affines, l'interpolation orthogonale conserve les combinaisons affines des points. Certaines de ces propriétés sont (voir la figure 6) : Figure 6a. Conservation des mesures algébriques projetées. Si une fois projeté sur un axe donné, un vecteur a la même mesure algébrique sur les deux exemples, alors cette valeur restera constante. En conséquence, les distances "horizontale" et "verticale" sont préservées, à condition que les points soient gardés du même côté l'un de l'autre. Ceci permet des spécifications des bordures et des marges. Figure 6b. Conservation des rapports relatifs. Si trois points sont alignés par le même rapport de distance sur les deux exemples, alors ils demeureront alignés et le rapport de distance demeurera le même. Par conséquent, des points médians sont préservés. Cette propriété est utile dans la mesure où des rapports constants semblent être utilisés par les graphistes. Figure 6c. Conservation des sommets confondus. Si deux points coïncident sur les deux exemples, alors ils coïncideront toujours. Par conséquent, deux formes qui se réunissent par la même paire de points sur 15 - 10 chaque exemple demeureront en contact. Ceci permet la spécification des relations d'incidence entre différentes primitives graphiques. Figure 6d. Conservation de parallélisme. Si deux lignes sont parallèles sur les deux exemples, alors elles seront toujours parallèles. Les graphistes peuvent en particulier s'attendre à cet invariant pour les lignes horizontales et verticales, même si cela reste vrai pour n'importe quelle orientation. Les parallélogrammes sont également préservés, ainsi que les rectangles parallèles aux axes principaux. Figure 6e. La conservation des combinaisons affines. On peut noter que 10 l'alignement est une propriété conservative seulement si la combinaison affine est respectée. Les techniques décrites dans la présente invention peuvent être mises en oeuvre dans des outils de dessins conventionnels de l'homme du métier. Bien sûr, l'invention n'est pas limitée aux exemples qui viennent d'être décrits et de nombreux aménagements peuvent être apportés à ces exemples sans sortir du cadre de l'invention. REVENDICATIONS 1. Procédé pour redimensionner un objet graphique structuré de façon à obtenir un objet graphique intermédiaire de taille différente, ce procédé 5 comprenant les étapes suivantes : - élaboration d'une pluralité de reproductions dudit objet graphique, chaque reproduction présentant un dimensionnement donné, - extraction d'un ensemble de matrices de transformation affine pour chaque reproduction, lo - application d'une interpolation orthogonale sur les matrices de transformations affines de façon à déduire des matrices intermédiaires de transformation affine pour tout objet graphique intermédiaire de taille différente de celle desdites reproductions; ladite interpolation orthogonale consistant en une interpolation 15 séparée de la première ligne des matrices de transformation selon au moins la largeur, et de la deuxième ligne des matrices de transformation selon au moins la hauteur; et - déduction des caractéristiques géométriques dudit objet graphique intermédiaire à partir des matrices intermédiaires. 20 2. Procédé selon la revendication 1, caractérisé en ce que ladite interpolation est de type linéaire par morceaux. 3. Procédé selon l'une quelconque des revendications précédentes, 25 caractérisé en ce que pour deux reproductions dont les matrices de transformation affine sont Ti et T2, et IT1,TZ un interpolant orthogonal permettant de générer une famille de matrices de transformations intermédiaires; et pour Pi, P2 et P des points obtenus par transformation d'un même point du plan via Ti, T2 et IT1,T2 respectivement, alors on déduit 30 P(x,y) à partir de P1(x1,yl) et P2(x2,y2) en utilisant la formule suivante : (lin? (ll'1,x1),(w2,x2) (w) I(hl, l),(h2,ï2) h j avec IT1,T2 I(wl,hl,T1),(w2.h2,T2) , c'est à dire P r X \Y/ une interpolation orthogonale ayant comme variable des matrices T, des largeurs w et des hauteurs h.- 12 4 Procédé selon la revendication 1, caractérisé en ce que ladite interpolation est de type polynomial.