Maneira rápida / eficiente de decompor coeficientes de filtro 2D inteiros separáveis

21

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
Paul R
fonte
1
Lembro-me de tentar descobrir isso lá na faculdade. Quase consegui, mas não me lembro como. =) Não consigo parar de pensar nisso agora que você mencionou!
Phonon
@Phonon: heh - bem, continue pensando - eu poderia usar alguma inspiração nesse. ;-)
Paul R
É possível fazer a mesma coisa, exceto para valores duplos ou flutuantes?
Diego Catalano
@ DiegoCatalano: veja a resposta de Denis abaixo e a pergunta a que ele se relaciona em math.stackexchange.com - Eu acho que pode funcionar para o caso mais geral de coeficientes de ponto flutuante.
Paul R
@PaulR, Como alguém pode entrar em contato com você por e-mail? Obrigado.
Royi 19/07/16

Respostas:

11

Eu peguei @Phonona 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.

function [X, Y, valid] = separate(M)    % separate 2D kernel M into X and Y vectors 
  X = M(1, :);                          % init X = top row of M
  Y = M(:, 1);                          % init Y = left column of M
  nx = numel(X);                        % nx = no of columns in M
  ny = numel(Y);                        % ny = no of rows in M
  gx = X(1);                            % gx = GCD of top row
  for i = 2:nx
    gx = gcd(gx, X(i));
  end
  gy = Y(1);                            % gy = GCD of left column
  for i = 2:ny
    gy = gcd(gy, Y(i));
  end
  X = X / gx;                           % scale X by GCD of X
  Y = Y / gy;                           % scale Y by GCD of Y
  scale = M(1, 1) / (X(1) * Y(1));      % calculate scale factor
  X = X * scale;                        % apply scale factor to X
  valid = all(all((M == Y * X)));       % result valid if we get back our original M
end

Muito obrigado @Phonone @Jason Rpelas idéias originais para isso.

Paul R
fonte
10

Consegui! A publicação do código MATLAB publicará uma explicação hoje à noite ou amanhã

% Two original arrays
N = 3;
range = 800;
a = round( range*(rand(N,1)-0.5) )
b = round( range*(rand(1,N)-0.5) )

% Create a matrix;
M = a*b;
N = size(M,1);

% Sanity check
disp([num2str(rank(M)) ' <- this should be 1!']);

% Sum across rows and columns
Sa = M * ones(N,1);
Sb = ones(1,N) * M;

% Get rid of zeros
SSa = Sa( Sa~=0 );
SSb = Sb( Sb~=0 );

if isempty(SSa) | isempty(SSb)
    break;
end

% Sizes of array without zeros
Na = numel(SSa);
Nb = numel(SSb);

% Find Greatest Common Divisor of Sa and Sb.
Ga = SSa(1);
Gb = SSb(1);

for l=2:Na
    Ga = gcd(Ga,SSa(l));
end

for l=2:Nb
    Gb = gcd(Gb,SSb(l));
end

%Divide by the greatest common divisor
Sa = Sa / Ga;
Sb = Sb / Gb;

%Scale one of the vectors
MM = Sa * Sb;
Sa = Sa * (MM(1) / M(1));

disp('Two arrays found:')
Sa
Sb
disp('Sa * Sb = ');
Sa*Sb
disp('Original = ');
M
Phonon
fonte
Obrigado - isso é ótimo - eu estava acordado na noite passada pensando em fatorar os coeficientes, etc., mas usar o GCD dessa maneira é muito mais simples e elegante. Infelizmente, ainda há uma ruga a ser resolvida - ela precisa funcionar com coeficientes positivos e negativos e isso pode levar a casos degenerados, por exemplo A=[-2 1 0 -1 2]; B=[2 -3 6 0 -1]; M=A'*B;. O problema aqui é que sum(A) = 0sim Sb = [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.
Paul R
OK - parece que você ainda pode obter os GCDs e fazer o dimensionamento usando 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 para Sa, Sbno final. Adicionei um exemplo patológico que ilustra o problema na pergunta original acima.
Paul R:
Acho que tenho uma solução funcional agora - eu a publiquei como uma resposta separada, mas o crédito é da idéia subjacente. Obrigado novamente !
Paul R
7

Talvez eu esteja banalizando o problema, mas parece que você poderia:

  • NMAaii=0,1,,N1
  • j>0

    • aja0jrj
    • rj
    • rjaja0j0x
    • aja0
  • x

xk,norm=xkmini=0N1xi
  • Depois disso, a lista normalizada de proporções conterá o valor 1 para a linha que possui a menor norma. Você deseja ver se pode escalar esta lista de alguma maneira para gerar uma lista que contém todos os coeficientes inteiros. Uma abordagem de força bruta poderia apenas fazer uma pesquisa linear, ou seja, calcular: Para cada valor de , depois de calcular a lista escalonada de proporções, você precisará verificar cada uma para ver se elas têm valor inteiro (novamente, com alguma tolerância). Defina igual ao maior denominador que você deseja procurar nas proporções entre linhas.xnorm
    xscaled=Kxnorm,K=1,2,,M
    KM

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.

Jason R
fonte
Obrigado - acho que provavelmente estava indo nessa direção antes de me atolar nos detalhes. Não está 100% claro para mim que você sempre chegará a uma solução usando esse método, mas, de qualquer forma, eu provavelmente deveria codificar isso e tentar com alguns exemplos. Tenho um palpite de que talvez seja necessário aplicar tanto a linha quanto a coluna para ver qual produz a "melhor" solução. Obrigado por dedicar um tempo para detalhar os detalhes. Vou me ocupar com isso e informá-lo como funciona.
Paul R
Você não conseguiu encontrar o maior divisor comum dos primeiros elementos das linhas e usá-lo para determinar seu vetor base?
Jim Clay
@ JimClay: Sim, é efetivamente o que você está fazendo no final, se você tiver essa funcionalidade disponível.
Jason R
3

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 . . .xyzA|Axyz|
x y z
yzxx y z x y z ...

(Das convoluções aproximadas à convolução como soma dos separáveis em math.stackexchange.)

denis
fonte
1
Tente não responder perguntas com links inexplicáveis. É melhor explicar os detalhes necessários em sua resposta e incluir o link apenas para referência; Dessa forma, se o link quebrar, os detalhes essenciais da resposta ainda estarão lá.
Sam Maloney
@ SamMaloney: Não vejo razão para isso ser necessário. O link explica tudo em detalhes. Ele ainda aparecerá na pesquisa de perguntas e respostas. Então por que não?
Naresh
1
@Naresh Eu apenas mencionei isso porque um dos objetivos dos sites de troca de pilhas é criar um repositório de perguntas respondidas para referência futura. Portanto, embora eu entenda que esse link específico é para outro site da SE e deve ser razoavelmente seguro, é uma prática recomendada geral não contar com links que ainda funcionem daqui a vários anos. . Dando um esboço geral destes "dois métodos fáceis na resposta seria garantir que a informação é mantida mesmo se algo acontecer com a questão ligada Como eu disse, porém, este foi mais de um comentário geral sobre as melhores práticas em matéria de ligações em respostas.
Sam Maloney