matrice trouver grâce à l'optimisation

Question

Je cherche algorithme pour résoudre le problème suivant:

J'ai deux ensembles de vecteurs, et je veux trouver la matrice qui correspond le mieux approximative de la transformation des vecteurs d'entrée aux vecteurs de sortie.

les vecteurs sont 3x1, donc la matrice est 3x3.

Ceci est le problème général. Mon problème particulier est que j'ai un ensemble de couleurs RVB, et un autre ensemble qui contient la couleur désirée. J'essaie de trouver une transformation RGB à RGB qui me donnerait des couleurs plus proches des couleurs désirées.

Il existe une correspondance entre les vecteurs d'entrée et de sortie, donc le calcul d'une fonction d'erreur qui doit être minimisée est la partie facile. Mais comment puis-je minimiser cette fonction?

Answer 1

Vous ne spécifiez pas de langue, mais voici comment j'aborderais le problème dans Matlab.

• v1 est une matrice 3XN, contenant vos couleurs d'entrée dans des vecteurs verticaux
• v2 est également une matrice de 3XN contenant les couleurs de votre sortie

Vous voulez résoudre le système

M*v1 = v2 
M = v2*inv(v1) 

Cependant, v1 n'est pas directement inversible, puisqu'il ne s'agit pas d'une matrice carrée. Matlab résoudra cela automatiquement avec l'opération mrdivide (M = v2/v1), où M est la meilleure solution.

eg: 
>> v1 = rand(3,10); 
>> M = rand(3,3); 
>> v2 = M * v1; 
>> v2/v1 - M 

ans = 

    1.0e-15 * 

    0.4510 0.4441 -0.5551 
    0.2220 0.1388 -0.3331 
    0.4441 0.2220 -0.4441 

>> (v2 + randn(size(v2))*0.1)/v1 - M 
ans = 

    0.0598 -0.1961 0.0931 
    -0.1684 0.0509 0.1465 
    -0.0931 -0.0009 0.0213 

This donne une solution plus agnostique langue sur la façon de résoudre le problème.

Answer 2

Certains algèbre linéaire devrait être suffisant:

Écrire la différence quadratique moyenne entre les entrées et les sorties (la somme des carrés de chaque différence entre chaque valeur d'entrée et de sortie). Je suppose que ceci est la définition du "meilleur approximatif"

Ceci est une fonction quadratique de vos 9 coefficients de matrice inconnus.

Pour le minimiser, dérivez-le par rapport à chacun d'eux.

Vous obtiendrez un système linéaire de 9 équations que vous avez à résoudre pour obtenir la solution (unique ou une variété de l'espace en fonction de l'ensemble d'entrée)

Lorsque la fonction de différence n'est pas quadratique, vous pouvez faire la même chose mais vous devez utiliser une méthode itérative pour résoudre le système d'équation.

Answer 3

Il s'agit d'un problème d'algèbre linéaire classique, la phrase clé à rechercher est "régression linéaire multiple".

J'ai dû coder une variation de ceci plusieurs fois au cours des années. Par exemple, le code pour calibrer une tablette numériseur ou un écran tactile stylet utilise les mêmes calculs.

---

Voici le calcul:

Soit p être un vecteur d'entrée et q le vecteur de sortie correspondant.

La transformation que vous voulez est une matrice 3x3; appelez le A.

Pour une seule entrée et le vecteur de sortie p et q, il y a un vecteur d'erreur e

e = q - A x p

Le carré de l'amplitude de l'erreur est une valeur scalaire:

e T x e = (q - A x p) T x (q - A x p)

(où l'opérateur T est transposé).

Qu'est-ce que vous voulez vraiment réduire au minimum la somme des e valeurs sur les jeux:

E = somme (e)

Cela satisfait minimum l'équation de la matrice D = 0 où

D (i, j) = la dérivée partielle de E par rapport à A (i, j)

Disons que vous avez entrée N et des vecteurs de sortie.

Votre ensemble d'entrée 3-vecteurs est une matrice 3xN; appeler cette matrice P. La ième colonne de P est le ième vecteur d'entrée.

Ainsi est l'ensemble des vecteurs de sortie 3; appelez cette matrice Q.

Lorsque vous broyer à travers l'ensemble de l'algèbre, la solution est

A = Q xP T x (Px P T)^-1

(où^-1 est l'opérateur inverse - désolé de ne pas avoir d'exposants ou d'indices)

---

est ici l'algorithme:

Créer la matrice 3xN P de l'ensemble des vecteurs d'entrée.

Créez la matrice 3xN Q à partir de l'ensemble des vecteurs de sortie.

Matrice Multiply R = P x transposition (P)

Calculer la inverseOf R

Matrice Multiply A = Q x transposition (P) x inverse (R)

en utilisant les routines de multiplication matricielle et d'inversion de matrice de votre bibliothèque d'algèbre linéaire de choix.

---

Cependant, transformer une matrice 3x3 affines est capable d'évoluer et faire tourner les vecteurs d'entrée, mais pas faire une traduction! Ce n'est peut-être pas assez général pour votre problème. C'est généralement une bonne idée d'ajouter un "1" à la fin de chacun des 3-vecteurs pour faire ensuite un 4-vectoriel, et de chercher la meilleure matrice de transformation 3x4 qui minimise l'erreur. Cela ne peut pas faire de mal; cela ne peut que conduire à un meilleur ajustement des données.