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

21

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
Paul R
sumber
1
Saya ingat mencoba memikirkan hal ini saat masih kuliah. Saya hampir berhasil, tetapi saya tidak ingat caranya. =) Saya tidak bisa berhenti memikirkannya sekarang setelah Anda menyebutkannya!
Telepon
@Phonon: heh - terus berpikir - saya bisa menggunakan beberapa inspirasi untuk yang ini. ;-)
Paul R
Apakah mungkin untuk melakukan hal yang sama tetapi untuk nilai ganda atau mengambang?
Diego Catalano
@DiegoCatalano: lihat jawaban Denis di bawah ini, dan pertanyaan yang ia tautkan pada math.stackexchange.com - Saya pikir itu mungkin berhasil untuk kasus koefisien floating point yang lebih umum.
Paul R
@ PaulR, Bagaimana orang bisa menghubungi Anda melalui email? Terima kasih.
Royi

Jawaban:

11

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.

Paul R
sumber
10

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
Phonon
sumber
Terima kasih - ini bagus - Saya terbangun tadi malam memikirkan tentang membuat faktor koefisien dll tetapi hanya menggunakan GCD seperti ini jauh lebih sederhana dan elegan. Sayangnya masih ada satu kerutan untuk mengatasi - perlu bekerja dengan koefisien positif dan negatif dan ini dapat menyebabkan kasus-kasus yang merosot, misalnya A=[-2 1 0 -1 2]; B=[2 -3 6 0 -1]; M=A'*B;. Masalahnya di sini adalah sum(A) = 0begitu Sb = [0 0 0 0 0]. Saya akan mencoba memodifikasi algoritma Anda sehingga menggunakan jumlah nilai absolut dari koefisien dan melihat apakah itu membantu. Sekali lagi terima kasih atas bantuan Anda.
Paul R
OK - sepertinya Anda masih bisa mendapatkan GCD dan melakukan penskalaan dengan menggunakan abs(M), yaitu Sa=abs(M)*ones(N,1); Sb=ones(1,N)*abs(M);dan kemudian melanjutkan seperti di atas, tapi saya belum bisa melihat cara mengembalikan tanda ke Sa, Sbpada akhirnya. Saya telah menambahkan contoh patologis yang menggambarkan masalah dalam pertanyaan asli di atas.
Paul R
Saya pikir saya punya solusi yang berfungsi sekarang - saya telah mempostingnya sebagai jawaban yang terpisah, tetapi kreditnya bagi Anda untuk ide yang mendasarinya. Terima kasih lagi !
Paul R
7

Mungkin saya meremehkan masalahnya, tetapi sepertinya Anda bisa:

  • NM.SEBUAHSebuahsayasaya=0,1,...,N-1
  • j>0

    • SebuahjSebuah0jrj
    • rj
    • rjSebuahjSebuah0j0x
    • SebuahjSebuah0
  • x

xk,nHairm=xkminsaya=0N-1xsaya
  • xnHairm
    xscSebuahled=KxnHairm,K=1,2,...,M.
    KM.

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.

Jason R
sumber
Terima kasih - saya pikir saya mungkin menuju ke arah seperti ini sebelum saya terjebak dalam detailnya. Tidak 100% jelas bagi saya bahwa Anda akan selalu sampai pada solusi menggunakan metode ini, tapi bagaimanapun, saya mungkin harus kode ini dan mencobanya dengan beberapa contoh. Saya punya firasat bahwa mungkin perlu diterapkan baik baris-bijaksana dan kolom-bijaksana untuk melihat mana yang menghasilkan solusi "terbaik". Terima kasih telah meluangkan waktu untuk menjelaskan detailnya - saya akan sibuk dengan itu dan memberi tahu Anda cara kerjanya.
Paul R
Tidak bisakah Anda menemukan pembagi umum terbesar dari elemen pertama dari baris, dan menggunakannya untuk menentukan vektor basis Anda?
Jim Clay
@ Jimclay: Ya, itulah yang Anda lakukan pada akhirnya, jika Anda memiliki fungsionalitas itu.
Jason R
3

xyzSEBUAH|SEBUAH-xyz|
x y z
yzxx y z x y z ... gantinya.

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

denis
sumber
1
Cobalah untuk tidak menjawab pertanyaan dengan tautan yang tidak dijelaskan. Lebih baik untuk menjelaskan perincian yang diperlukan dalam jawaban Anda dan menyertakan tautan hanya untuk referensi; dengan begitu jika tautan memecah detail penting dari jawabannya masih ada.
Sam Maloney
@ SamMaloney: Saya tidak melihat alasan mengapa itu perlu. Tautan menjelaskan semuanya secara terperinci. Itu masih akan muncul dalam pencarian Q&A. Jadi mengapa tidak?
Naresh
1
@Naresh Saya hanya menyebutkannya karena salah satu tujuan dari situs pertukaran tumpukan adalah untuk membangun repositori dari pertanyaan yang dijawab untuk referensi di masa mendatang. Jadi, sementara saya mengerti bahwa tautan khusus ini ke situs SE lain dan seharusnya cukup aman, itu adalah praktik terbaik umum untuk tidak mengandalkan tautan yang masih berfungsi beberapa tahun dari sekarang. Memberikan garis besar umum dari "dua metode mudah" ini dalam jawaban akan memastikan bahwa informasi tetap dipertahankan bahkan jika sesuatu terjadi pada pertanyaan terkait. Seperti yang saya katakan, ini lebih merupakan komentar umum tentang praktik terbaik terkait tautan dalam jawaban.
Sam Maloney