Eu gostaria de poder determinar rapidamente se um determinado kernel 2D de coeficientes inteiros é separável em dois núcleos 1D com coeficientes inteiros. Por exemplo
2 3 2
4 6 4
2 3 2
é separável em
2 3 2
e
1
2
1
O teste real para separabilidade parece ser bastante simples usando aritmética inteira, mas a decomposição em filtros 1D com coeficientes inteiros está provando ser um problema mais difícil. A dificuldade parece estar no fato de que as proporções entre linhas ou colunas podem ser não inteiras (frações racionais); por exemplo, no exemplo acima, temos proporções de 2, 1/2, 3/2 e 2/3.
Eu realmente não quero usar uma abordagem pesada como SVD porque (a) é relativamente computacionalmente caro para minhas necessidades e (b) ainda não ajuda necessariamente a determinar coeficientes inteiros .
Alguma ideia ?
OUTRAS INFORMAÇÕES
Os coeficientes podem ser positivos, negativos ou zero, e pode haver casos patológicos em que a soma de um ou de ambos os vetores 1D é zero, por exemplo
-1 2 -1
0 0 0
1 -2 1
é separável em
1 -2 1
e
-1
0
1
fonte
Respostas:
Eu peguei
@Phonon
a resposta e a modifiquei um pouco para que ela use a abordagem GCD apenas na linha superior e na coluna esquerda, em vez de nas somas de linha / coluna. Isso parece lidar com casos patológicos um pouco melhor. Ainda pode falhar se a linha superior ou a coluna esquerda estiverem com zeros, mas é possível verificar esses casos antes de aplicar esse método.Muito obrigado
@Phonon
e@Jason R
pelas idéias originais para isso.fonte
Consegui! A publicação do código MATLAB publicará uma explicação hoje à noite ou amanhã
fonte
A=[-2 1 0 -1 2]; B=[2 -3 6 0 -1]; M=A'*B;
. O problema aqui é quesum(A) = 0
simSb = [0 0 0 0 0]
. Vou tentar modificar seu algoritmo para que ele use a soma dos valores absolutos dos coeficientes e veja se isso ajuda. Obrigado novamente por sua ajuda.abs(M)
, ou seja,Sa=abs(M)*ones(N,1); Sb=ones(1,N)*abs(M);
e continuar como acima, mas eu ainda não posso ver como restaurar os sinais paraSa
,Sb
no final. Adicionei um exemplo patológico que ilustra o problema na pergunta original acima.Talvez eu esteja banalizando o problema, mas parece que você poderia:
Não é o método mais elegante, e é provável que exista uma maneira melhor, mas deve funcionar, é bastante simples de implementar e deve ser relativamente rápido para matrizes de tamanho modesto.
fonte
Outra maneira é encontrar uma aproximação separável ao seu kernel e ver como está próximo. Duas maneiras de fazer isso, ou seja, minimizar : 1) otimização da força bruta ; isso leva tempo ~ a soma, e não o produto, de seus comprimentos 2) para e fixos ; o ideal é apenas uma projeção; portanto, otimize por sua vez.A | A - x ⊗ y ⊗ z | x y z y z x x y z x y z . . .x⊗y⊗z A |A−x⊗y⊗z|
x y z
y z x x y z x y z ...
(Das convoluções aproximadas à convolução como soma dos separáveis em math.stackexchange.)
fonte