поиск матрицы через оптимизацию

Я ищу алгоритм для решения следующей проблемы:

У меня есть два набора векторов, и я хочу найти матрицу, которая наилучшим образом приближает преобразование от входных векторов к выходным векторам.

векторы 3х1, поэтому матрица 3х3.

Это общая проблема. Моя конкретная проблема - у меня есть набор цветов RGB и другой набор, который содержит желаемый цвет. Я пытаюсь найти преобразование RGB в RGB, которое бы дало мне цвета ближе к желаемым.

Между входным и выходным векторами есть соответствие, поэтому вычисление функции ошибки, которую следует минимизировать, является легкой частью. Но как я могу минимизировать эту функцию?

13.10.2009 10:29:26
Есть ли у вас соответствие между векторами в двух наборах (т.е. установлен 1, вектор 1 должен отображаться в набор 2, вектор 1)?
Drew Hall 13.10.2009 10:32:18
Это какая-то гамма-коррекция? или отображение гистограммы?
RobS 13.10.2009 10:55:33
3 ОТВЕТА
РЕШЕНИЕ

Вы не указываете язык, но вот как я бы подошел к проблеме в Matlab.

  • v1 - это матрица 3xn, содержащая введенные вами цвета в вертикальных векторах
  • v2 также матрица 3xn, содержащая ваши выходные цвета

Вы хотите решить систему

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

Тем не менее, v1 не является напрямую обратимым, поскольку это не квадратная матрица. Matlab решит это автоматически с помощью операции mrdivide (M = v2 / v1), где M - наилучшее решение.

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

Это дает более независимое от языка решение о том, как решить проблему.

2
15.10.2009 22:01:54
Это было бы здорово, я работаю над статическими данными, поэтому я могу сделать снимок в Matlab
shodanex 15.10.2009 18:18:18
Принято из-за ссылки, которая помогла мне найти и найти хорошее объяснение этой проблемы.
shodanex 20.10.2009 07:55:36

Некоторой линейной алгебры должно быть достаточно:

Запишите среднеквадратичную разницу между входами и выходами (сумма квадратов каждой разности между каждым входным и выходным значением). Я предполагаю, что это определение «наилучший пример»

Это квадратичная функция ваших 9 неизвестных матричных коэффициентов.

Чтобы свести его к минимуму, выведите его в отношении каждого из них.

Вы получите линейную систему из 9 уравнений, которую нужно решить, чтобы получить решение (уникальное или пространственное разнообразие в зависимости от входного набора)

Если разностная функция не является квадратичной, вы можете сделать то же самое, но вы должны использовать итерационный метод для решения системы уравнений.

3
13.10.2009 11:17:45
Извините, я думал, что вы попросили описание математики
fa. 13.10.2009 12:09:22

Это классическая задача линейной алгебры, ключевая фраза для поиска - «множественная линейная регрессия».

Мне приходилось кодировать некоторые вариации этого много раз за эти годы. Например, код для калибровки планшета планшета или сенсорного экрана стилуса использует ту же математику.


Вот математика:

Пусть p будет входным вектором, а q соответствующим выходным вектором.

Требуемое преобразование - это матрица 3х3; называем это A .

Для одного входного и выходного вектора p и q существует вектор ошибки e

e = q - A x p

Квадрат величины ошибки является скалярным значением:

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

(где оператор T транспонирован).

То, что вы действительно хотите минимизировать, это сумма значений e по наборам:

Е = сумма ( е )

Этот минимум удовлетворяет матричному уравнению D = 0, где

D (i, j) = частная производная E по A (i, j)

Скажем, у вас есть N входных и выходных векторов.

Ваш набор входных 3-векторов представляет собой матрицу 3xN; называют эту матрицу P . I-й столбец P - это i-й входной вектор.

Таков набор выходных 3-векторов; называют эту матрицу Q .

Когда вы шлифуете всю алгебру, решение

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

(где ^ -1 - обратный оператор - извините за отсутствие индексов или индексов)


Вот алгоритм:

Создайте матрицу 3xN P из набора входных векторов.

Создайте матрицу 3xN Q из набора выходных векторов.

Умножение матрицы R = P x транспонировать ( P )

Вычислить обратное R

Умножение матриц A = Q x транспонирование ( P ) x обратное ( R )

используя процедуры умножения матриц и обращения матриц вашей библиотеки линейной алгебры по вашему выбору.


Тем не менее , матрица аффинного преобразования 3x3 способна масштабировать и вращать входные векторы, но не выполнять никакого преобразования! Это может быть недостаточно общим для вашей проблемы. Обычно хорошей идеей является добавление «1» в конце каждого из 3-векторов, чтобы затем получить 4-вектор, и поиск лучшей матрицы преобразования 3х4, которая минимизирует ошибку. Это не может повредить; это может только привести к лучшему соответствию данных.

5
16.10.2009 23:39:11
Это тоже отличный ответ, но объяснение было лучше (stackoverflow не подходит для математики) в ссылке, которую я обнаружил в ответе Кены. Итак, Кена получила награду.
shodanex 20.10.2009 07:58:01