Задача компьютерного зрения разбивается на множество самых разных частных подзадач, но ни одна из них не является простой. Но если пытаться найти некую общую основу, то выйдет что и человеческое и машинное зрение основаны на том, что сейчас именуется матрицей пикселей. Ну или более древне - таблицами чисел. Именно поэтому постановки задач в матричной форме столь часты.
Однако из-за того что все эти операции выполняются над массивами чисел, то всегда существует интерес как делать это проще и быстрей.
Одна из возможных простых постановок задач берёт две числовые матрицы $A, B$ "совместимых" размеров так, чтобы минимизировать критерий качества $\min\limits_{K,R}{\|AK-RB\|}^2$ построенный на матричной норме Фробениуса ${\|X\|}^2=\mathrm{tr}\{X^TX\}=\mathrm{tr}\{XX^T\}$. В данном случае мне важно напомнить что эту квадратичную норму можно задать через след матрицы. Фактически приведённый минимум соответствует банальному методу наименьших квадратов, только в матричной форме. Что касается самих матриц, то матрица $A$ представляет собой исходное изображение, в общем случае - прямоугольной формы. А матрица $B$ - шаблон для сравнения.
При этом идеей автора этого критерия качества был поиск минимума для диагональной матрицы $K$ и ортогональной матрицы $R$. Если разобрать это выражение как есть, то произведение $AK$ представляет собой постолбцовое умножение на определённый числовой коэффициент и влечёт за собой использование квадратной матрицы $K$, то есть диагональной в "классическом" смысле. Своего рода усиление или ослабление интенсивности "сигнала" исходного изображения до "номинала" сравнительного шаблона. А так как исходное изображение может содержать шаблон в повёрнутом и/или скошенном виде, то его необходимо соответственно скорректировать $RB$.
Если действовать формально, то квадратичный критерий можно развернуть в виде двух матриц
$$M_1=K^TA^TAK-K^TA^TRB-B^TR^TAK+B^TR^TRB$$ и $$M_2=AKK^TA^T-RBK^TA^T-AKB^TR^T+RBB^TR^T.$$
Фактически можно рассматривать два критерия качества $J_1=\mathrm{tr}\{M_1\}$ и $J_2=\mathrm{tr}\{M_2\}$ зависящих от "параметров оптимизации" - матриц $K$ и $R$. Причём в случае $J_1$ ортогональность матрицы $R$, то есть $R^TR=I$ немного упрощает выражение.
Если уметь чуть больше чем обычный выпускник универа, то есть дифференцировать по
матрице, то для поиска экстремумов у нас получится четыре выражения.
$$\frac{\partial J_1}{\partial K}=2\left[A^TAK-A^TRB\right]=0$$ $$\frac{\partial J_1}{\partial R}=-2AKB^T=0$$ $$\frac{\partial J_2}{\partial K}=2\left[A^TAK-A^TRB\right]=0$$ $$\frac{\partial J_2}{\partial R}=2\left[RBB^T-AKB^T\right]=0.$$
Первое что бросается в глаза - это совпадение первой и третьей частной производной. А так же возможность записать их и четвёртую производную по другому: $A^T(AK-RB)=0$ и $-(AK-RB)B^T=0$ которые, с теоретической точки зрения, должны доставлять минимум исходному критерию качества. Это вроде как хорошо, но необходимость согласовывать размерность матриц $A_{m\times n}K_{n\times n}-R_{m\times m}B{m\times n}$ приводит к наличию (в общем случае) матриц $A^TA$ размерности $n\times n$ и $BB^T$ размера $m\times m$. Если ориентироваться на типичные камеры, то $m\ne n$ и с точки зрения математики даже в лучшем случае только одна из этих матриц будет невырожденной, то есть для неё можно вычислить обратную. Для второго произведения всегда уже будет фигурировать псевдообратная.
Но и это в рамках современных численных методов (как теории, так и практики) вопрос решаемый. Куда хуже сказывается наше желание получать матрицу $R$ ортогональной, то есть невырожденной. А вот здесь, если без хитростей, то придётся полагать $m<n$, то есть количество строк в изображении должно быть меньше - так называемая альбомная, или "горизонтальная" ориентация.
Но и это всё, уж простите за просторечие, фигня на палочке. Дело в том, что производные $J_2$ по сути дают одно и тоже, то есть найти два неизвестных параметра по одному единственному условию никак не получится. С $J_1$ формально не так, но само по себе условие экстремума $AKB^T=0$ в качестве "гарантированного" решения ничего кроме бессмысленного $K\equiv 0$ не предлагает.
Однако матрицы $A,B$ сами по себе ненулевые и вообще задача на минимизацию, так что можно поставить вспомогательную задачу $\|AKB^T\|\rightarrow 0$. Используя правила дифференцирования матричного следа точным решением будет $K=A^TB$. Его подстановка в четвёртую частную производную даст $R=AA^T$.
После этого, делая формальную подстановку $A^TAK-A^TRB=A^TAA^TB-A^TAA^TB\equiv 0$ мы можем убедиться что такие матрицы $K,R$ будут формальным минимумом.
Магия, фокусы или опыт - рассматривайте это как хотите. Формальное решение задачи найти можно. Только вот смысла в нём? Матрица $K$ явно не диагональная, а матрица $R$ - и близко не ортогональная. Более того, взять только диагональные элементы произведения $A^TB$ и "как-то" ортонормировать $AA^T$ неверно и по сути и по факту, так как всегда есть разница между теорией и практикой когда берутся не то точные аналитические решения. Задача минимизации должна решаться правильно. То есть если мы выберем некоторую диагональную $K$ привязанную к произведению $A^TB$, то лучшее теоретическое $R=AA^T$ в реальности таковым уже не будет и стартовать придётся от формального решения $R=AKB^T{\left(BB^T\right)}^{-1}$ в котором фигурирует обратная матрица которая может и не существовать для реальных исходных матриц. Поэтому правильное формально решение записывается через псевдообратную матрицу $R=AKB^+$. Вот только её опять нужно ортонормализировать!
Вот так и получается, что "логически правильная" постановка задачи имеет некоторое аналитическое решение, только вот оно не удовлетворяет установленным ограничениям.
Комментарии
Отправить комментарий