We know that a convolution can be replaced by a multiplication with a Toeplitz / Circulant Matrix. Meaning, assume I have convolution kernel $ h $ and matrix $ I $ (Of size $ m \times m $ for example), then there is a matrix $ H $ of size $ m^2 \times m^2 $ such that $ h \ast I $ is the same as $ H I^{cs} $ Where cs for column stacked image resized to $m \times m$ (reshape(H*I(:), [m, m])).
My question is - how to construct $H$? I know that every row of $H$ is responsible for single entry of the resulting multiplication (H(1,:)*I(:) gives the (1,1) entry of the convolution result), so I can try to work very hard to calculate each entry of $H$ (e.g. if the kernel $h$ is of size $3 \times 3$, than the convolution result in entry (i,j) is:
$$ h_{11}\cdot I(i-1,j-1) + h_{12}\cdot I(i-1,j) + h_{13}\cdot I(i-1,j+1) + h_{21}\cdot I(i,j-1) + h_{22}\cdot I(i,j) + h_{23}\cdot I(i,j+1) + h_{31}\cdot I(i+1,j-1) + h_{32}\cdot I(i+1,j) + h_{33}\cdot I(i+1,j+1) $$
except for near the edges of $I$. so it's somewhat possible with a lot of hard work to construct $H$ such that when multiplying by $I^{cs}$ I will get that result). But is there a 'generic' way for this construction? Or perhaps a made MATLAB function?
I am aware of the convmtx2() function in MATLAB, but the resulting matrix is not in the proper dimensions (not even square).
No comments:
Post a Comment