Appariement de couples d'entiers naturels

[chstez]

Bonjour,
soit un couple d'entiers naturels {A,B} tel que A et B compris entre 0 et 255.
soit une liste de couples d'entiers naturels {w1,w2}, {x1,x2}, {y1,y2}, {z1,z2} ...... répondant à la même définition 0 {A,B} avec {C,D}[U]<{A,B} . Chaque coefficient affecte simultanément les 2 termes du couple. La somme des coefficients est égal à 1.
3/ Exemple numérique : {A,B} ={160,45}
Liste {180,30}, {65,120}, {95,110}, {255,255}, {0,0}
En résumé, trouver {C,D} au plus près de {A,B} par défaut. {C,D} étant le résultat de l'addition des deux "meilleurs" candidats de la liste affectés des coefficients a et b (à trouver avec a+b =1).
Merci de me suggérer des idées, au moins pour la question 1.

[fatal_error]

hi,

1/ Comment définir mathématiquement le couple de la liste le plus "proche" de {A,B} ?

tu peux imaginer que c'est deux points dans le R^2, idem tu peux prendre le norme euclidienne :
d({A,B}, {C,D}) = sqrt( (A-C)^2+(B-D)^2)
ou bien encore la norme 1 :
d({A,B}, {C,D}) = |A-C|+|B-D|

[fatal_error]

pour la 2 :
tu peux t'en sortir avec programmation sous contrainte (linéaire si tu prends la distance avec les valeurs absolues)
pour tout tuple t de k elements possibles {x_i, y_i}
v: vecteur des coefficients (a_0..a_{k-1} de chacun des elements du tuple
C = a_0x_0+...+a_{k-1}x_{k-1}
D = a_0y_0+...+a_{k-1}y_{k-1}
minimiser d({C,B}, obj) //où obj est l'élément que tu veux approcher avec {C,D}
sous contrainte : 0finpour

[chstez]

Merci pour tes réponses.

pour la 1:idem tu peux prendre le norme euclidienne : d({A,B}, {C,D}) = sqrt( (A-C)^2+(B-D)^2)

Tu confirmes mon intention de prendre la norme euclidienne pour comparer les éléments.

pour la 2 : tu peux t'en sortir avec programmation sous contrainte (linéaire si tu prends la distance avec les valeurs absolues)
pour tout tuple t de k elements possibles {x_i, y_i}
v: vecteur des coefficients (a_0..a_{k-1} de chacun des elements du tuple
C = a_0x_0+...+a_{k-1}x_{k-1}
D = a_0y_0+...+a_{k-1}y_{k-1}
minimiser d({C,B}, obj) //où obj est l'élément que tu veux approcher avec {C,D}
sous contrainte : 0<C<255, 0<D<255

Précisions :
C = a_0x_0+...+a_{k-1}x_{k-1} est bien une somme de produits de facteurs?
minimiser d({C,B}, obj) : tu veux dire minimiser d({C,D}?
Je pense programmer (je ne suis qu'un "amateur") en Actionscript. Connaitrais-tu des exemples analogues à mes questions en AS ou en Java?

[fatal_error]

C = a_0x_0+...+a_{k-1}x_{k-1} est bien une somme de produits de facteurs?

oui

a_i sont les coefficients que tu veux determiner, x_i c'est l'asbscisse du point I
par exemple
a_0E + a_1G si on dit {C,D}=a_0{E,F}+a_1{G,H}

minimiser d({C,B}, obj) : tu veux dire minimiser d({C,D}?

non une distance, c'est entre deux points donc tu as
d({C,D}, un autre point)
cet autre point, c'est l'objectif par exemple obj={2,5} et toi tu dois trouver le meilleur {C,D} possible qui minimise la distance.

maintenant, si tu developpes, tobtiens
d({C,D}, un autre point) =sqrt((x_C - a.vx)^2 + (x_D - a.vy)^2)
ou a est le vecteur de coefficient, vx les coordonnees sur x de ta somme de vecteur (par exemple vx=[xE, xG]) vy=[yF,yH] et a.vx designe le produit scalaire.

tu peux chercher le min de d^2 (pour virer la racine carree), parce que x^2 est str croissante sur 0,+,
et il reste plus qu'a deriver par rapport au vecteur de coefficient.

Connaitrais-tu des exemples analogues à mes questions en AS ou en Java?

beurk AS et java, ca suxx.

[chstez]

Merci pour tes réponses.
Je vais éclaicir tout ça à tête reposée...
et risque de te demander quelques éclaircissements plus tard, si tu veux bien.

[chstez]

fatal_error si tu me lis,.........salut.
D'après tes indictations, lumineuses, j'ai testé sur papier ta méthode avec les données simples suivantes et ça marche!
Target T {3,7}
Element A{1,8}; Element B{6,2}; Element C{5,6}
Le but étant de trouver les appariements deux à deux : A,B puis A,C puis B,C qui, pondérés par les coefficients a_0 et a_1 équivalent à T.
Pour A avec B:
T {3} --> 3=a_0+6a_1
T {7} --> 7=8a_0+2a_1
on trouve a_0=36/46 et a_1=17/46 (c'est exprès que je laisse au même dénominateur)
Pour A avec C:
T {3} --> 3=a_0+5a_1
T {7} --> 7=8a_0+6a_1
on trouve a_0=17/34 et a_1=17/34 (pas étonnant, sur le graphique les distances AT et TC sont égales)
Pour B avec C:
T {3} --> 3=6a_0+5a_1
T {7} --> 7=2a_0+6a_1
on trouve a_0=-(17/26) et a_1=36/26
Toutes les vérifications conduisent bien au doublet {3,7}.
On peut en conclure qu'il y a toujours des solutions au problème puisque ce sont des systèmes d'équations linéaires à 2 inconnues. Finalement, la seule contrainte pour moi est de retenir les sytèmes qui ont comme solutions des nombres rationnels positifs pour les deux coefficients. Ici la combinaison 3 ne passe pas.
Comme tu sembles l'avoir deviné, il s'agit de "manipuler" des valeurs RGB : reproduire un code teinte RGB (la cible) à partir de 4 codes teintes RGB pondérés (les candidats), à selectionner dans une liste de n éléments. Sur ces 4 codes teintes RGB 2 sont imposés : le blanc (RGB : 255,255,255) et le noir (RGB : 0,0,0).
Donc il faut que j'étende mon problème :
de 2 éléments à 4 (dont 2 imposés) composés chacun d'un triplet au lieu d'un doublet.
Est-ce faisable d'après toi?
Une autre paire de manches pour moi : programmer un code pour la résolution des équations! Ne me dis pas qu'il me faut apprendre le Python dont tu sembles être un expert!

[Dlzlogic]

Bonjour,
J'ai pas mal travaillé sur le couleurs, alors ce sujet m'intéresse aussi.
La méthode des distances convient autant avec des triplets qu'avec des doublets. Petite astuce, plutôt que comparer des distances, il est plus économique de comparer des carrés pour les doublets ou des cubes pour les triplets.
Si on admet que cette distance correspond à une luminosité il n'est pas sûr que ce soit tout à fait vrai pour les couleurs avec ses 3 composantes.
Donc, ma question : que voulez-vous faire avec ces transformations de couleur ?
A titre d'exemple, je me suis fait une palette de 32 couleurs dégradées du bleu-foncé au rouge-orangé, en passant par le vert, je n'ai pas réussi à faire autrement que de calculer indépendamment les variations de ces 3 composantes.
La transformation en négatif n'est pas très facile non plus. Un jaune fond noir se verra très bien, le négatif sera franchement raté.

[fatal_error]

Donc il faut que j'étende mon problème :
de 2 éléments à 4 (dont 2 imposés) composés chacun d'un triplet au lieu d'un doublet.
Est-ce faisable d'après toi?

oui c'est faisable.
Je note A(255,255,255), D(0,0,0) B et C deux points que tu prends dans ta liste.
Le but c'est toujours de minimiser
d(E, obj), avec E=aA+bB+cC+dD, avec a,b,c et d des coefficients compris entre 0 et 1 (ce qui assurera qu'on reste dans 0 et 255, c'est un coeff de proportionnalité quoi), idéalement, la somme de a,b, c et d fait 1, mais on s'en tape.

On alors à minimiser
dist=(E.x-obj.x)^2 + (E.y-obj.y)^2 + (E.z-obj.z)^2
s.c (sous contraintes) 0<a<1, ..., 0<d<1

on peut déjà enlever la variable d, parce que nimporte quoi fois 0(D=(0,0,0), ca fait 0.
il reste à déterminer a,b,c

mm à partir de là, ya sqp qui résoud ca sous octave, sinon à la mano ca doit rester faisable je pense, mais jme rappèle plus...j'essaie

[fatal_error]

voilà un exemple avec octave:

Code: Tout sélectionner

clear all;
clear global;
x_0=[0 0 0]';

A=[255,255,255];
B=[17,22,13];
C=[125,23,156];
global M = [A;B;C]';
global target=[64,200,32];
function obj = phi (x)
   global M;
   global target;
   a=(x'*M-target);
   obj=sqrt(a*a');
endfunction

lb=zeros(1,length(x_0));
ub=ones(1,length(x_0));
[x, obj, info, iter, nf, lambda] = sqp(x_0, { @phi }, [], [], lb',ub');
obj
x
x'*M
%output :
%{
obj =  194.73
x =

   0.14850
   0.17137
   0.00000

ans =

   81.5683    6.2947   22.5046

%}



le résultat est pas bon, on a [81.5683 6.2947 22.5046] alors qu'on attend [64,200,32];
si on enlève la contrainte 0<x<1 (x représente le vecteur a,b,c), on a bien

Code: Tout sélectionner

%{
obj =  1.7837e-05
x =

   103.169
   -23.993
   -78.925

ans =

    64.000   200.000    32.000

%}


[64.000 200.000 32.000] le résultat attendu, mais on a se trimballe des coeffs négatifs... ce qui n'est pas voulu.


Conclusion, il y a des éléments qui donneront pas une tres bonne "similarité" avec ta target.


reste le problème de porter sqp dans ton langage, je peux éventuellement regarder côté javascript ou c++, mais python java j'y toucherai pas!

edit: on peut peut etre s'en sortir plus facilement en remarquant que la fonction objectif dist peut etre résolue à l'aide de l'algo Levenberg-Marquardt (implem leasqr qui propose aussi la gestion des contraintes sur les paramètres à optimiser.

edit2: en fait on peut virer les contraintes en imposant x'*x (idem si a==-2, on considère a==-2*-2==4, idem la solution qu'on trouve, si jamais optimale pour -2, sera la même que pour 2)

[chstez]

Salut Dlzlogic, c'est sympa de voir du monde s'intéresser au problème.
Mon but est de faire un simulateur de mise à la teinte en synthèse soustractive. C.à.d que l’on dispose d’une teinte de référence (le type –target dans mon exemple) et que par ajouts successifs de quantités virtuelles (les coefficients de mon exemple) de pâtes pigmentaires (la fameuse liste d’éléments de mon exemple) on arrive à contretyper le type. La règle de formulation pigmentaire dans l’industrie veut que l’on ait 4 pigments :
-un pigment de tonalité (R ou Y ou G ou B)
-un pigment nuanceur qui permet de contrôler la teinte sur l’autre axe. Par exemple un pigment Y ou B si le ton est R ou G ou R si le ton est B)
-la présence de pigment blanc ET de pigment noir impératif pour rendre la teinte « robuste » à la fabrication et a l’utilisation.
Etat actuel :
Mon programme tourne très bien : il génère une teinte d’après une liste de pigments que j’ai créée. Il est donc possible de synthétiser cette teinte à partir de la même liste de pigments. Le tout est visualisé à l’écran. L’opérateur ne connaissant pas la formule théorique doit compter sur sa logique et sur son expérience pour réussir. Il sait néanmoins qu’il y a une solution. Il peut même être aidé par les écarts L*a*b* CIE1976 que j’y ai inclus.
Maintenant l’objet de ma demande concerne les teintes normalisées ou standardisées (RAL, AFNOR, Pantone etc...) dont j’ai les codes RGB. Il y en a quelques centaines que je voudrais inclure dans des exercices de synthèse. Il est quasiment impossible de préparer une à une les réponses à toutes les teintes, surtout que la palette pigmentaire peut évoluer (ajout ou retrait de pigments) ! D’où ma recherche d’automatisation de la tâche…
fatal_error : j’ai étendu la technique de calcul à 4 éléments (triplets). Je me suis aussi rendu compte que le noir (0,0,0) était neutre et inopérant. Or, il m’en faut absolument dans la formule pigmentaire. Faut-il « tricher » avec (1,0,0), (0,1,0), (0,0,1) qui visuellement n’ont pas beaucoup d’écart (légèrement rougeâtre, verdâtre ou bleuâtre) mais que le L*a*b* CIE1976 détecte. Ma liste de pigments noirs comporte Black 0 ; (0,0,0) ; Black Y ; (2,2,0) ; Black B ; (0,0,2)

[fatal_error]

Ben dans ce cas là, tu peux considérer prendre 5 couleurs :
blanc, les deux que tu choisis, et les deux blacks ((2,2,0) et (0,0,2) que tu auras à mélanger pour obtenir ton "black final")

[Dlzlogic]

@chstez,
Oups, c'est encore plus compliqué que je ne pensais. Ca me rappelle une anecdote. Un jours j'ai pris un auto-stoppeur. Comme je suis bavard, je lui ai raconté les discussions que l'on avait au bureau à propos de couleurs. Il m'a dit qu'en tant qu'imprimeur, il avait ce type de discussion tous les jours.
Il y a un gros problème avec la visualisation sur un écran, c'est que les couleurs sont apparentes, et surtout réglables. Comme les couleurs sont normalisées, d'ailleurs, je ne suis pas sûr que les critères RGB soient les mêmes.
Il est effectivement très difficile pour un opérateur de savoir s'il doit rajouter du rouge ou diminuer le bleu, mais il est en général assez facile de choisir parmi un échantillon visible, la couleur qui se rapproche le plus de celle qui est affichée.
Je crois me souvenir que j'avais trouvé une méthode basée sur une pondération, il faudrait que je recherche. Mais ma préoccupation n'était pas la même.
Bonne continuation.

[chstez]

Le but de mon simulateur de mise à la teinte n'est pas de reproduire exactement la vision sur ecran des teintes normalisées ou standardisées, ce qui nécessiterait un matériel hors de portée du commun des mortels avec, en plus, étalonnage de l'écran etc...
C'est d'amener l'opérateur à réfléchir sur les bonnes décisions à prendre lors d'une mise à la teinte sachant que dans la réalité (sur une cuve de 10 tonnes par exemple) la quantité ajoutée d'un pigment, et donc ses conséquences coloristiques, ne peut plus être retirée. L'écart relatif entre les teintes, que l'écran soit calibré ou non, reste le même.
Problème du Noir (0,0,0)
Pour rendre le Noir (0,0,0) opérant en le remplaçant par une valeur non nulle, j'ai testé les mesures d'ecarts de teinte, (0,0,0) étant la référence, selon CIE Lab 1976 avec les résultats suivants :
Avec (0,0,1)--> Delta_E_CIE = 0.40376
Avec (0,1,0)--> Delta_E_CIE = 0.53000
Avec (1,0,0)--> Delta_E_CIE = 0.28332
Avec (1,1,1)--> Delta_E_CIE = 0.27417
Avec une variation de 1 (le minimum que l'on puisse faire varier), les delta E ne sont pas négligeables et seront visibles dans des teintes claires ou pastel. (Le delta E est la distance entre les teintes dans l'espace CIE Lab). Ce ne serait pas une bonne méthode. Y en aurait-il une autre ?
Ecrémage des pigments candidats
Si on place la cible et tous les pigments dans R^3 pour visualiser leurs positions relatives, pourrait-on en tirer des critères de selection des pigments "eligibles"? A coup sûr certains pigments ne pourraient apporter que des solutions <0. Pouvoir les éliminer d'emblée serait une bonne chose.

[fatal_error]

s'il te faut a tout pris considérer (0,0,0) tu peux normaliser
E=1/4(aA+bB+cC+dD) (comme une moyenne) en rappelant que a,...,d sont inférieur à 1. ca imposera de prendre un a plus important et donc d existera

ex:

Code: Tout sélectionner

clear all;
clear global;

A=[255,255,255];
B=[17,22,13];
C=[125,23,156];
D=[0,0,0];
global M = [A;B;C;D];
global target=[64,200,32];
x_0=diag(zeros(length(M)))+0.5;
function obj = phi (x)
   global M;
   global target;
   y=tanh(x);
   x=y.*y;%trick: tabh->x in -1;1 then x*x ->x in 0<x<1
   a=(M'*x/4-target');
   obj=sumsq(a);
endfunction

[x, obj, info, iter, nf, lambda] = sqp(x_0, { @phi });
y=tanh(x);
x=y.*y;
obj
regTarget=(M'*x/4)
target
x
%
output:
regTarget =

   68.000
   69.250
   67.000

target =

    64   200    32

x =

   1.0000e+00
   1.0000e+00
   6.9630e-17
   2.1355e-01


%}



regTarget étant le résultat optimal (et moins bon que si on contraint pas le 1/4).

Bien sûr pour des couleurs bien choisies, on a un peu mieux...

Code: Tout sélectionner


A=[255,40,0];
B=[0,255,0];
C=[0,0,128];
D=[0,0,0];

%{output
obj =  1.5939e+04
regTarget =

   63.750
   73.750
   32.000

target =

    64   200    32

x =

   1.00000
   1.00000
   1.00000
   0.21355
%}


[chstez]

s'il te faut a tout pris considérer (0,0,0) tu peux normaliser
E=1/4(aA+bB+cC+dD) (comme une moyenne) en rappelant que a,...,d sont inférieur à 1. ca imposera de prendre un a plus important et donc d existera

C'est quelque chose d'analogue à ta proposition que j'utilise déjà dans mon programme pour la création d'une teinte à partir de 4 pigments de la liste :
E=(1/(a+b+c+d))(aA+bB+cC+dD)
Ca marche très bien, et le triplet (0,0,0,), en minimisant les valeurs du triplet mélange, agit bien comme un ajout de noir. (Tu peux vérifier sur Octave dont je ne connais pas la syntaxe: certaines instructions me sont vraiment enigmatiques).
Trouver E en connaissant a, b, c, d et A, B, C, D n'est donc pas un problème. C'est la démarche inverse que je creuse toujours pour trouver la solution : trouver a, b, c, d en connaissant E et A, B, C, D!
N'ayant pas le privilège de poster des pièces jointes sur le site, je tenvoie sur ton Email un petit fichier Excel. On peut y voir :
- la synthèse d'un triplet pour créer un code teinte.
- le positionnement relatif des 4 pigments sur le graphe par rapport au mélange et à la cible. (on peut "jouer" avec)
- que tous les pigments ne sont pas utilisables pour la synthèse d'une teinte. Cela dépend de l'allure du graphe de la Cible et de celle du pigment "candidat". Il y a 5 "types" de graphe ;
/\ Ouverture -
\/ Ouverture +
/ croissant
\ decroisant
-- croissant (le blanc, le noir, les gris)
Cette constatation va me permettre "d'écrémer" les pigments candidats et de placer dans un tableau temporaire les "élus".
Pour la programmation de la résolution du système d'équations linéaires, quand j'aurai trouvé l'astuce pour a,b,c,d, je pense utiliser la méthode d'élimination de Gauss-Jordan. On a une matrice carrée de 4 x 4. C'est relativement facile à coder (quoique rien n'est simple pour un amateur...) Qu'en penses-tu?

[fatal_error]

Trouver E en connaissant a, b, c, d et A, B, C, D n'est donc pas un problème. C'est la démarche inverse que je creuse toujours pour trouver la solution : trouver a, b, c, d en connaissant E et A, B, C, D!

oui oui.
Le problème c'est que connaissant A,...,E, c'est pas sur qu'il existe a,...d qui vérifient ton égalité.
Le mieux que tu peux faire c'est trouver des a,...d qui minimisent l'écart entre E et aA+...+dD.

C'est ce que le code proposé ci haut fait. Il cherche a,...,d qui minimisent la distance (E-aA+bB+cC+dD)^2
regTarget = (le resultat aA+bB+cC+dD)

68.000
69.250
67.000

E =

64 200 32

x =

1.0000e+00 (==a)
1.0000e+00 (==b)
6.9630e-17 (==c)
2.1355e-01 (==d)

[chstez]

Salut!
Excuse moi pour mon silence, j'étais absent quelques temps.
Je suis toujours sur mon sujet.
Je joins une "modélisation" avec Excel sur le lien suivant :
http://www.filedropper.com/analysetriplets2_1
La méthode Gauss Jordan marche très bien pour résoudre mon système à 4 inconnues (y compris avec le noir (0,0,0)...... quand il n'y a que des solutions positives. Ce n'est pas toujours le cas.

Je reprends mon sujet en essayant de trouver
1/ une méthode pour avoir, dans ce cas, la meilleure solution (la plus proche) avec des solutions uniquement positives. (minimiser la distance dans R^3 -espace CIE Lab)

2/ un système de selection pour limiter le nombre de pigments en se basant sur l'allure de leurs graphes (1ere feuille du fichier) et celui de la cible.
Si il y a suggestions....

[fatal_error]

pour la 1) tu as déjà la réponse
pour la 2) je sais pas. Mais pe quelqu'un d'autre, si tu arrives à l'intéresser typiquement en montrant les courbes + interprétations ici, plutot qu'en collant un lien!

[chstez]

Code: Tout sélectionner

clear all;
clear global;
A=[255,255,255];
B=[17,22,13];
C=[125,23,156];
D=[0,0,0];
global M = [A;B;C;D];
global target=[64,200,32];
x_0=diag(zeros(length(M)))+0.5;
function obj = phi (x)
   global M;
   global target;
   y=tanh(x);
   x=y.*y;%trick: tabh->x in -1;1 then x*x ->x in 0<x<1
   a=(M'*x/4-target');
   obj=sumsq(a);
endfunction
[x, obj, info, iter, nf, lambda] = sqp(x_0, { @phi });
y=tanh(x);
x=y.*y;
obj
regTarget=(M'*x/4)
target
x
%
output:
regTarget =
   68.000
   69.250
   67.000
target =
    64   200    32
x =
   1.0000e+00
   1.0000e+00
   6.9630e-17
   2.1355e-01
%}


Salut,
j'ai essayé de déchiffrer le code octave ci dessus pour en sortir la structure de l'algorithme. J'y suis arrivé partiellement (variables et contraintes), mais bon nombre de points restent obscures ; ex sqp est une méthode interne à octave?
Aurais-tu ou existe-t-il un schéma de l'algorithme utilisé? Ca m'éviterait d'apprendre la syntaxe octave :arf: