Cara cepat / efisien untuk mendekomposisi koefisien filter 2D integer yang dapat dipisahkan

Saya ingin dapat dengan cepat menentukan apakah kernel 2D yang diberikan koefisien integer dapat dipisahkan menjadi dua kernel 1D dengan koefisien integer. Misalnya

 2   3   2
 4   6   4
 2   3   2

dipisahkan menjadi

 2   3   2

dan

 1
 2
 1

Tes sebenarnya untuk pemisahan tampaknya cukup mudah menggunakan aritmatika integer, tetapi penguraian menjadi filter 1D dengan koefisien integer terbukti menjadi masalah yang lebih sulit. Kesulitan tampaknya terletak pada kenyataan bahwa rasio antara baris atau kolom mungkin non-integer (fraksi rasional), misalnya dalam contoh di atas kita memiliki rasio 2, 1/2, 3/2 dan 2/3.

Saya tidak benar-benar ingin menggunakan pendekatan tugas berat seperti SVD karena (a) ini relatif mahal secara komputasi untuk kebutuhan saya dan (b) masih belum tentu membantu untuk menentukan koefisien integer .

Ada ide?

INFORMASI LEBIH LANJUT

Koefisien mungkin positif, negatif atau nol, dan mungkin ada kasus patologis di mana jumlah salah satu atau kedua vektor 1D adalah nol, misalnya

-1   2  -1
 0   0   0
 1  -2   1

dipisahkan menjadi

 1  -2   1

dan

-1
 0
 1

Saya telah mengambil @Phononjawaban dan memodifikasinya sehingga menggunakan pendekatan GCD pada baris atas dan kolom kiri, bukan pada jumlah baris / kolom. Ini tampaknya menangani kasus-kasus patologis sedikit lebih baik. Itu masih bisa gagal jika baris atas atau kolom kiri semuanya nol, tetapi kasing ini dapat diperiksa sebelum menerapkan metode ini.

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

Banyak terima kasih kepada @Phonondan @Jason Runtuk ide-ide orisinal untuk ini.

Oke! Posting kode MATLAB, akan memposting penjelasan malam ini atau besok

% 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

Mungkin saya meremehkan masalahnya, tetapi sepertinya Anda bisa:

• $N$$M$$\mathbf{A}$$\mathbf{a_i}$$i = 0, 1, \ldots , N-1$

• $j > 0$

  • $\mathbf{a_j}$$\mathbf{a_0}$$j$$\mathbf{r_j}$
  • $\mathbf{r_j}$
  • $\mathbf{r_j}$$\mathbf{a_j}$$\mathbf{a_0}$$j$$0$$\mathbf{x}$
  • $\mathbf{a_j}$$\mathbf{a_0}$

• $\mathbf{x}$

• $\mathbf{x_{norm}}$ $$\mathbf{x_{scaled}} = K\mathbf{x_{norm}}, K = 1, 2, \ldots, M$$ $K$$M$

Bukan metode yang paling elegan, dan kemungkinan ada cara yang lebih baik, tetapi harus bekerja, cukup sederhana untuk diterapkan, dan harus relatif cepat untuk matriks berukuran sedang.

$x \otimes y \otimes z$$A$$|A - x \otimes y \otimes z|$
$x\ y\ z$
$y$$z$$x$$x\ y\ z\ x\ y\ z\ ...$ gantinya.

(Dari perkiraan-konvolusi-sebagai-jumlah-konvolusi-terpisah pada math.stackexchange.)