Компьютерное зрение и геометрическая алгебра.
(то, с чем я развлекаюсь, уже описано в отдельной статье, но я ее не читал потому, что мне интересно самому все вывести)
Сперва про геометрическую алгебру.
Она работает с пространствами под названием ∧Rn, которые строятся из обычных векторных пространств Rn путем расширения их с помощью внешнего произведения A^B и добавлением скаляров.
Внешнее произведение: A^B=-B^A (соответственно, A^A=0), (αA+βB)^C=αA^C+βB^C, A^(B^C)=(A^B)^C. Перемножение двух базисных векторов дает двувектор: e1^e2=e12. Если e12 умножить на e3, получим тривектор e123, для трехмерного пространства R3 он является элементом с наивысшей степенью. Количество перемноженных векторов из исходного пространства называется степенью базисного вектора ГА (скаляр имеет степень 0, e2 - 1, e123 - 3). Размерность пространства ∧Rn равна 2n.
Помимо внешнего произведения есть внутреннее, оно, в отличии от внешнего, коммутативно: A•B=B•A, все остальные аксиомы те же.
В сумме они дают так называемый геометрический продукт: AB=A•B+A^B.
Внутреннее произведение можно уподобить скалярному, а внешнее - векторному. Справедливо только уподобление, поскольку смысл операций различен. Например, внешнее произведение создает обьект, который "перпендикулярен" двум его операндам и "ориентирован" (зависит от порядка операндов), но определен на любом векторном пространстве, не только R3.
Что еще? Можно вводить интересные метрики на пространстве. Например:Внутр.
произв.e1e2e3e0e∞e110000e201000e300100e00000-1e∞000-10К трем векторам трехмерного пространства мы добавили еще два вектора: начало координат e0 и точка в бесконечности e∞. Удобно поставить в соответствие трехмерному вектору v=vxe1+vye2+vze3 следующую конструкцию v=e0+v+(1/2)v2e∞. v•v=0 для любого v (нулевые вектора), при этом маленькие (по модулю) v неотличимы от начала координат, а большие - от точки в бесконечности. Обе специальные точки являются инвариантами всех осмысленных преобразований (вращение, перемещение и растяжение). Также для всех осмысленных преобразований сохраняется условие vv=v•v=0.
Геометрическая алгебра с такой таблицей внутреннего произведения называется конформальной геометрической алгеброй (conformal geometric algebra, буду звать ее КГА). Конформальной она называется потому, что линии при преобразованиях переходят в линии, плоскости - в плоскости, сферы - в сферы и сохраняются углы между линиями.
Про плоскости.
Плоскость-обьект в КГА задается очень просто: P=e∞^A^B^C, то есть, она включает в себя точку на бесконечности и три точки на плоскости.
Проверить четвертую точку D на принадлежность плоскости также очень просто: P^D=0. То же относится и к другим объектам КГА, внешнее произведение объекта и проверяемой точки равно 0: O^p=0.
(кстати, сфера - это внешнее произведение четырех точек на ней, S=A^B^C^D, плоскость просто частный случай, получается)
Про преобразования обьектов.
Преобразования обьектов выполняется с помощью "версоров". Это обьекты четной степени (содержат скаляры, двувектора, четыре-вектора и тп). Парный (conjugate) к версору V обьект V* получается путем умножения всех его элементов на (-1)a(a+1)/2, где a - степень элемента. V=1+e12+e0123, V*=1-e12+e0123.
Через версоры записывается вращение, перемещение и растяжение.
Само же преобразование выглядит так: M'=VMV*. Преобразуемый обьект M "вкладывается" в геометрическое произведение между "половинками" версора. В западной литературе это называется "sandwiching", "обутерброживание". Подходящий термин, по-моему.
Версоры можно сопрягать: U=VT, U*=T*V*.
Версоры - отличная штука! Очень абстрактная.
Однако про их построение я лучше расскажуж потом. Просто сейчас можно обойтись и без них.
Теперь я вернусь к компьютерному зрению.
Я рассмотрю две камеры, на которых есть отображение точки M. На первую она отобразилась в точку m1=(m1x,m1y,1), на вторую в точку m2=(m2x,m2y,1). Вторая камера просто смещена в сторону от первой на вектор t (t²≠0), поворота нет.
Тут есть рисунок, из которого ясно, что точка начала координат O, точка m1 и смещение t образуют плоскость, на которой лежит точка m2, если ее сместить на вектор t.
Итак, наши обьекты:
Что я и хочу сделать.
Итак, получается вот, что: e∞^e0^m1^t^m2=0.
m1, t и m2 состоят из трех слагаемых, e0, собственно, вектора и длины вектора, умноженной на e∞. От первого и третьего слагаемых мы можем избавиться по следующей формуле: A^(αA+B)=A^B. В качестве A мы сперва берем e0, а затем e∞. Каждый из трех сложных множителей сперва теряет первое слагаемое, а затем последнее. Остаются только вектора.
Остается следующая формула: e∞^e0^m1^t^m2=0.
Внешнее произведение трех последних векторов даст нам всего одно слагаемое вида Ce123, где C будет зависить от компонент этих самых векторов. Это будет определитель матрицы 3x3 со строками m1, t и m2.
В принципе, я повторил предыдущий результат для E=TI (единичная матрица вращения). Зато, вроде, нигде не наврал и не срезал углов.
Постараюсь проверить на днях уже на каких-нибудь цифрах.
А потом постараюсь добавить еще и вращение.
Сперва про геометрическую алгебру.
Она работает с пространствами под названием ∧Rn, которые строятся из обычных векторных пространств Rn путем расширения их с помощью внешнего произведения A^B и добавлением скаляров.
Внешнее произведение: A^B=-B^A (соответственно, A^A=0), (αA+βB)^C=αA^C+βB^C, A^(B^C)=(A^B)^C. Перемножение двух базисных векторов дает двувектор: e1^e2=e12. Если e12 умножить на e3, получим тривектор e123, для трехмерного пространства R3 он является элементом с наивысшей степенью. Количество перемноженных векторов из исходного пространства называется степенью базисного вектора ГА (скаляр имеет степень 0, e2 - 1, e123 - 3). Размерность пространства ∧Rn равна 2n.
Помимо внешнего произведения есть внутреннее, оно, в отличии от внешнего, коммутативно: A•B=B•A, все остальные аксиомы те же.
В сумме они дают так называемый геометрический продукт: AB=A•B+A^B.
Внутреннее произведение можно уподобить скалярному, а внешнее - векторному. Справедливо только уподобление, поскольку смысл операций различен. Например, внешнее произведение создает обьект, который "перпендикулярен" двум его операндам и "ориентирован" (зависит от порядка операндов), но определен на любом векторном пространстве, не только R3.
Что еще? Можно вводить интересные метрики на пространстве. Например:Внутр.
произв.e1e2e3e0e∞e110000e201000e300100e00000-1e∞000-10К трем векторам трехмерного пространства мы добавили еще два вектора: начало координат e0 и точка в бесконечности e∞. Удобно поставить в соответствие трехмерному вектору v=vxe1+vye2+vze3 следующую конструкцию v=e0+v+(1/2)v2e∞. v•v=0 для любого v (нулевые вектора), при этом маленькие (по модулю) v неотличимы от начала координат, а большие - от точки в бесконечности. Обе специальные точки являются инвариантами всех осмысленных преобразований (вращение, перемещение и растяжение). Также для всех осмысленных преобразований сохраняется условие vv=v•v=0.
Геометрическая алгебра с такой таблицей внутреннего произведения называется конформальной геометрической алгеброй (conformal geometric algebra, буду звать ее КГА). Конформальной она называется потому, что линии при преобразованиях переходят в линии, плоскости - в плоскости, сферы - в сферы и сохраняются углы между линиями.
Про плоскости.
Плоскость-обьект в КГА задается очень просто: P=e∞^A^B^C, то есть, она включает в себя точку на бесконечности и три точки на плоскости.
Проверить четвертую точку D на принадлежность плоскости также очень просто: P^D=0. То же относится и к другим объектам КГА, внешнее произведение объекта и проверяемой точки равно 0: O^p=0.
(кстати, сфера - это внешнее произведение четырех точек на ней, S=A^B^C^D, плоскость просто частный случай, получается)
Про преобразования обьектов.
Преобразования обьектов выполняется с помощью "версоров". Это обьекты четной степени (содержат скаляры, двувектора, четыре-вектора и тп). Парный (conjugate) к версору V обьект V* получается путем умножения всех его элементов на (-1)a(a+1)/2, где a - степень элемента. V=1+e12+e0123, V*=1-e12+e0123.
Через версоры записывается вращение, перемещение и растяжение.
Само же преобразование выглядит так: M'=VMV*. Преобразуемый обьект M "вкладывается" в геометрическое произведение между "половинками" версора. В западной литературе это называется "sandwiching", "обутерброживание". Подходящий термин, по-моему.
Версоры можно сопрягать: U=VT, U*=T*V*.
Версоры - отличная штука! Очень абстрактная.
Однако про их построение я лучше расскажуж потом. Просто сейчас можно обойтись и без них.
Теперь я вернусь к компьютерному зрению.
Я рассмотрю две камеры, на которых есть отображение точки M. На первую она отобразилась в точку m1=(m1x,m1y,1), на вторую в точку m2=(m2x,m2y,1). Вторая камера просто смещена в сторону от первой на вектор t (t²≠0), поворота нет.
Тут есть рисунок, из которого ясно, что точка начала координат O, точка m1 и смещение t образуют плоскость, на которой лежит точка m2, если ее сместить на вектор t.
Итак, наши обьекты:
- Начало координат (и центр проекции первой камеры) O: O=e0
- Точка m1=e0+m1+(1/2)m1²e∞
- Центр проекции второй камеры: O'=t=e0+t+(1/2)t²e∞
- Плоскость с проецируемой точкой: P=e∞^O^m1^t=e∞^e0^m1^t
- Вторая проекция точки M, m2, в координатах первой камеры: m2=e0+m2+t+(1/2)(m2+t)²e∞
Что я и хочу сделать.
Итак, получается вот, что: e∞^e0^m1^t^m2=0.
m1, t и m2 состоят из трех слагаемых, e0, собственно, вектора и длины вектора, умноженной на e∞. От первого и третьего слагаемых мы можем избавиться по следующей формуле: A^(αA+B)=A^B. В качестве A мы сперва берем e0, а затем e∞. Каждый из трех сложных множителей сперва теряет первое слагаемое, а затем последнее. Остаются только вектора.
Остается следующая формула: e∞^e0^m1^t^m2=0.
Внешнее произведение трех последних векторов даст нам всего одно слагаемое вида Ce123, где C будет зависить от компонент этих самых векторов. Это будет определитель матрицы 3x3 со строками m1, t и m2.
В принципе, я повторил предыдущий результат для E=TI (единичная матрица вращения). Зато, вроде, нигде не наврал и не срезал углов.
Постараюсь проверить на днях уже на каких-нибудь цифрах.
А потом постараюсь добавить еще и вращение.