Encontrar a matriz através da otimização

Question

Estou procurando um algoritmo para resolver o seguinte problema:

Eu tenho dois conjuntos de vetores e quero encontrar a matriz que melhor se aproximam da transformação dos vetores de entrada nos vetores de saída.

Os vetores são 3x1, então a matriz é 3x3.

Este é o problema geral. Meu problema específico é que tenho um conjunto de cores RGB e outro conjunto que contém a cor desejada. Estou tentando encontrar uma transformação RGB para RGB que me daria cores mais próximas dos desejados.

Há correspondência entre os vetores de entrada e saída; portanto, calcular uma função de erro que deve ser minimizada é a parte mais fácil. Mas como posso minimizar essa função?

Answer 1

Você não especifica um idioma, mas eis como eu abordaria o problema no Matlab.

• V1 é uma matriz 3xn, contendo suas cores de entrada em vetores verticais
• V2 também é uma matriz 3xn que contém as cores da sua saída

Você quer resolver o sistema

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

No entanto, V1 não é diretamente invertível, pois não é uma matriz quadrada. O MATLAB resolverá isso automaticamente com a operação MRDivide (M = V2/V1), onde M é a solução mais adequada.

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

este fornece uma solução mais agnóstica de linguagem sobre como resolver o problema.

Answer 2

Este é um problema clássico de álgebra linear, a frase principal a ser pesquisada é "regressão linear múltipla".

Eu tive que codificar alguma variação disso muitas vezes ao longo dos anos. Por exemplo, o código para calibrar um tablet digitalizador ou a tela de toque da caneta usa a mesma matemática.

---

Aqui está a matemática:

Deixar p ser um vetor de entrada e q o vetor de saída correspondente.

A transformação que você deseja é uma matriz 3x3; chame-o UMA.

Para um único vetor de entrada e saída p e q, há um vetor de erro e

e = q - UMA x p

O quadrado da magnitude do erro é um valor escalar:

eT x e = (q - UMA x p) T X (q - UMA x p)

(onde o operador T é transposto).

O que você realmente deseja minimizar é a soma de e valores sobre os conjuntos:

E = soma (e)

Este mínimo satisfaz a equação da matriz D = 0 onde

D(i, j) = o derivado parcial de E em relação a UMA(eu j)

Digamos que você tenha n vetores de entrada e saída.

Seu conjunto de vetores de entrada é uma matriz 3xn; Chame essa matriz P. A i -ésada coluna de P é o i -ésimo vetor de entrada.

O mesmo acontece com o conjunto de vetores 3 de saída; Chame essa matriz Q.

Quando você tritura toda a álgebra, a solução é

UMA = Q x PT X (P x PT) ^-1

(onde ^-1 é o operador inverso-desculpe por nenhum superestradias ou subscritos)

---

Aqui está o algoritmo:

Crie a matriz 3xn P Do conjunto de vetores de entrada.

Crie a matriz 3xn Q Do conjunto de vetores de saída.

Matriz multiplicar R = P x transposição (P)

Calcule o inverso de R

Matriz multiplicar UMA = Q x transposição (P) x inverso (R)

Usando as rotinas de multiplicação da matriz e inversão da matriz da sua biblioteca de álgebra linear de escolha.

---

No entanto, uma matriz de transformação afim 3x3 é capaz de escalar e girar os vetores de entrada, mas não fazendo qualquer tradução! Isso pode não ser geral o suficiente para o seu problema. Geralmente, é uma boa idéia anexar um "1" no final de cada um dos 3 vetores para fazer um vetor de 4 e procurar a melhor matriz de transformação 3x4 que minimiza o erro. Isso não pode doer; Isso só pode levar a um ajuste melhor dos dados.

Answer 3

Alguma álgebra linear deve ser suficiente:

Escreva a diferença média ao quadrado entre entradas e saídas (a soma dos quadrados de cada diferença entre cada valor de entrada e saída). Suponho isso como definição de "melhor aproximação"

Esta é uma função quadrática dos seus 9 coeficientes de matriz desconhecidos.

Para minimizá -lo, deriva -o em relação a cada um deles.

Você obterá um sistema linear de 9 equações que você deve resolver para obter a solução (única ou uma variedade de espaço, dependendo do conjunto de entrada)

Quando a função de diferença não é quadrática, você pode fazer o mesmo, mas precisa usar um método iterativo para resolver o sistema de equações.