Получение градиента двухвариантной функции

Question

Я делаю некоторую обработку видео, для каждого кадра мне нужно получить градиент функции бивариата. Функция представлена ​​в виде двумерного массива значений типа double. Где домен - это индексы строк и столбцов, а диапазон - это двойное значение соответствующих значений индексов. Или, проще говоря, функция f определяется для double[][] matrix в качестве таких:

f(x,y)=matrix[x][y]

Я пытаюсь использовать для этого библиотеку Apache Commons Math:

SmoothingPolynomialBicubicSplineInterpolator iterpolator = new SmoothingPolynomialBicubicSplineInterpolator();
BicubicSplineInterpolatingFunction f = iterpolator.interpolate(xs, ys, matrix.getData());
    for (int i = 0; i < ans.length; i++) {
        for (int j = 0; j < ans[0].length; j++) {
            ans[i][j] = f.partialDerivativeY(i, j); 
        }
    }

• с хз, как отсортированный массив х индексов (0,1,...,matrix.getRowDimension() - 1)
• То же самое в измерении столбцов (0,1,...,matrix.getColumnDimension() - 1)

Проблема в том, что для типичной матрицы размером 150X80 это занимает столько же, сколько 1.4 секунд, чтобы бежать, что делает его совершенно неуместным для моих нужд. Итак, как начинающий пользователь этой библиотеки и программного числового анализа в целом, я хочу знать:

1. Я делаю что-то неправильно?
2. Есть ли другой, более быстрый, способ, которым я могу выполнить эту задачу?
3. Есть ли еще одна библиотека с открытым исходным кодом (предпочтительно maven-friendly), которая предлагает решение?

Answer 1

Числовое разграничение - это целая тема, простой гугл должен собрать достаточно материала, чтобы вы могли с ним работать (может быть достаточно только вики). Есть параметры вашей проблемы, которые я не могу знать, поэтому я могу говорить здесь только широко, но есть прямые методы определения градиента в данной точке, то есть те, которые не требуют интерполяции. См. Википедию для формул (начиная от простого f(x+1)-f(x)где h=1для более высокого порядка). Расчет частных производных является простым O(NM) цикл с простой формулой внутри (интерполяция не требуется).

Специфика может стать песчаной:

1. Формулы более высокого порядка должны быть уменьшены для ребер или полностью исключены.
2. Ваши точные требования к скорости могут сделать более сложные формулы бесполезными (в зависимости от платформы иногда время поиска формул более высокого порядка делает их слишком медленными; опять же, это зависит от кэша и т. Д.). Это легко проверить, формулы просты; код их и тест.
3. Конкретная реализация также зависит от ваших требований к ошибкам. Теория предоставляет границы ошибок, так что они будут играть роль в том, какая формула вам нужна; но опять же, есть компромисс с требованиями к скорости. В свою очередь, это может быть практически снижено, если вы знаете особенности типов матриц, которые вы будете обрабатывать, если такая вещь известна.

Реализацию можно сделать еще проще (и, возможно, быстрее), если у вас есть существующие инструменты свертки, поскольку этот метод на самом деле является просто сверткой матрицы (обратите внимание; технически это называется взаимной корреляцией).