Усреднее

[ukku]

Добрый день! Есть матрица, необходимо ее усреднить.
$m(i,j) = 0.5m(i,j) + 0.5\{m(i+1,j) + m(i-1,j) + m(i,j+1) + m(i,j-1)\}$
Возможно ли как-то произвести подобное усреднение, без использования промежуточной матрицы ? Не могу сообразить.

[Sonic86]

Ну Вы можете выразить $m_{ij}$ через элементы, не равные $m_{ij}$, затем запишите $S = \sum\limits_{i,j} m_{ij}$ через это соотношение и потом через $S$ и потом Вы увидите, чему равно $S$, а значит задача бессмысленна...

Мне тут телепатят по-другому:
Вы хотите подсчитать $m_{ij}:= \frac{1}{2}(m_{ij}+m_{i-1j}+m_{i+1j}+m_{ij-1}+m_{ij+1})$.
Если так, то надо подумать....

[ukku]

Sonic86 в сообщении #445775 писал(а):

Мне тут телепатят по-другому:
Вы хотите подсчитать $m_{ij}:= \frac{1}{2}(m_{ij}+m_{i-1j}+m_{i+1j}+m_{ij-1}+m_{ij+1})$.
Если так, то надо подумать....

Ой, я ошибся, второй множитель 0,125 должен быть, но это не суть. Если возможны варианты с $m_{ij}:= \frac{1}{5}(m_{ij}+m_{i-1j}+m_{i+1j}+m_{ij-1}+m_{ij+1})$, думаю мне тоже сойдет.

[Sonic86]

Если матрица $n \times n$, то можно для $j$-го шага хранить полоску $3 \times n$ старых значений. На $j$-м шаге пересчитывается $j$-я строка старой матрицы (новые значения сохраняются в нее же).

[ukku]

Sonic86 в сообщении #445779 писал(а):

Если матрица $n \times n$, то можно для $j$-го шага хранить полоску $3 \times n$ старых значений. На $j$-м шаге пересчитывается $j$-я строка старой матрицы (новые значения сохраняются в нее же).

Так принципиально от создания промежуточной матрицы не отличается, даже медленней наверное будет. Вначале была мысль, что бы при подсчете $m(i,j)$ вносить поправку в $m(i+1,j)$ и в $m(i,j+1)$. Только не могу сообразить какую, если это вообще возможно.

[Sonic86]

ukku писал(а):

Так принципиально от создания промежуточной матрицы не отличается,

Матрица $3 \times n$ весит меньше, чем $n \times n$, хотя ее пересчет равносилен созданию трех копий исходной матрицы по числу операций.
А я не понял! Вы число операций хотите сэкономить или память? Если число операций, то исходный способ с созданием промежуточной матрицы для пересчета одной клетки состоит всего лишь из создания копии значения, собственно пересчета значения матрицы и копирования значения обратно (ну + еще чистка памяти) - всего лишь 2 "лишних" простеньких операции. Вряд ли это можно еще упростить. А если нужно экономить память - другое дело.

[ukku]

Память не важна, важна скорость. Ну 2 лишний операции, при десятке матриц в каждой из которых несколько десятков тысяч значений с десяток-другой раз в секунду, не очень лишние :) Но особой оптимизации тут видно нету :(

[svv]

В Вашем случае фильтр описывается матрицей
$C=\begin{bmatrix}0 & 1/8 & 0 \\ 1/8 & 1/2 & 1/8 \\ 0 & 1/8 & 0 \end{bmatrix}$

Если бы матрица фильтра $C$ была равна произведению двух векторов: $C=a b^\top$, т.е. $c_{ik}=a_i b_k$, например:
$C=\begin{bmatrix}p^2 & pq & p^2 \\ pq & q^2 & pq \\ p^2 & pq & p^2 \end{bmatrix}=\begin{bmatrix}p\\q\\p\end{bmatrix} \begin{bmatrix}p & q & p\end{bmatrix}$
(чем не усреднение?), то была бы возможна такая оптимизация: сначала обработать столбцы фильтром $a$, затем строки фильтром $b$.
Понятно, чтобы среднее не менялось, должно быть $2p+q=1$.

[Sonic86]

svv писал(а):

(чем не усреднение?), то была бы возможна такая оптимизация: сначала обработать столбцы фильтром $a$, затем строки фильтром $b$.

Во блин! А я до этого тоже допер! Только я соответствующей терминологии не знаю. Поэтому смогу объяснить простым языком
То есть вместо $m_{ij}:= km_{ij}+l(m_{i-1j}+m_{i+1j}+m_{ij-1}+m_{ij+1})$ делается 2 итерации:
сначала $m_{ij}:= Am_{ij}+B(m_{i-1j}+m_{i+1j})$, а потом $m_{ij}:= Am_{ij}+B(m_{ij-1}+m_{ij+1})$. Это равносильно общей формуле $m_{ij}:= km_{ij}+l(m_{i-1j}+m_{i+1j}+m_{ij-1}+m_{ij+1}) + r(m_{i-1,j-1}+m_{i+1,j-1}+m_{i+1,j-1}+m_{i+1,j+1})$, где $r \neq 0$, но очень мало (т.е. мы добавили в сумму не только смежные ячейки, но и смежные по диагонали, но с очень маленьким весом). Если я правильно угадал смысл задачи, это изменение формулы должно быть несущественно.
Параметры $A,B$ нужно подобрать (в частности $A^2 = k = \frac{1}{2}$), но за $O(1)$ операций. Тогда каждую матрицу можно пересчитать, выделяя не $3n$, а всего $3$ новых переменных (в 1-й части пересчитываются отдельно строки - нужно помнить 2 старых значения + еще одно, в второй части - столбцы - итого $2 \cdot 2 \cdot 3n^2$ присваиваний, что, конечно, хуже). Можете попробовать. Сильно хуже точно не будет. Код будет тоже не сильно сложный.

[ukku]

svv, Sonic86, спасибо, можно попробовать.