Geekly articles weekly

Konversi gambar hitam dan putih ke grafik ASCII menggunakan dekomposisi matriks non-negatif


Secara umum, mengonversi gambar ke grafik ASCII adalah tugas yang agak memakan waktu, tetapi ada algoritma yang mengotomatisasi proses ini. Artikel ini membahas pendekatan yang diusulkan oleh peneliti Paul D. O'Grady dan Scott T. Rickard dalam "Konversi Seni ASCII Otomatis Gambar Biner Menggunakan Kendala Non-Negatif . " Metode yang mereka gambarkan melibatkan mewakili proses konversi gambar sebagai masalah optimisasi dan menyelesaikan masalah ini menggunakan dekomposisi matriks non-negatif. Di bawah ini adalah deskripsi dari algoritma yang dimaksud, serta implementasinya:

Deskripsi algoritma


Gambar asli dibagi menjadi beberapa blok ukuran M \ kali N dimana M. dan N - lebar dan tinggi satu karakter dalam piksel. Jika lebar \ tinggi gambar bukan kelipatan dari lebar \ tinggi karakter, maka gambar dipotong atau ditambah dengan area putih dengan ukuran yang diinginkan.


Masing-masing K blok yang diperoleh setelah partisi direpresentasikan sebagai vektor dengan panjang R = M * N yang nilainya adalah intensitas warna piksel gambar (nilai dari 0 hingga 255, di mana piksel putih sesuai dengan nilai 0 dan piksel hitam sesuai dengan 255). Vektor yang dihasilkan harus dinormalisasi menggunakan norma l_2 :

v_i = \ frac {v_i} {\ sqrt {\ sum ^ R_ {k = 1} {v ^ 2_k}}}}


Vektor yang dinormalisasi ditulis ulang dalam bentuk kolom, sehingga membentuk matriks V ukurannya R \ kali K .

Matriks yang dihasilkan V perlu direpresentasikan sebagai produk dari matriks W dan H semua elemen yang non-negatif:

V_ {R \ kali K} = W_ {R \ kali L} H_ {L \ kali K}

Matriks W diketahui sebelumnya: itu dibangun mirip dengan matriks V , tetapi alih-alih bagian dari gambar asli, gambar dari semua simbol yang digunakan dalam pembuatan grafik ASCII digunakan. Jika kit yang berlaku termasuk L. karakter kemudian matriks W akan memiliki ukuran R \ kali L .
Tetap hanya memilih matriks H sehingga dapat meminimalkan nilai dari beberapa fungsi tujuan yang mencirikan perbedaan antara V dan bekerja WH . Ketergantungan berikut digunakan sebagai fungsi seperti itu:

D (V, W, H, \ beta) = \ sum_ {ik} \ bigg ({v_ {ik} \ frac {v_ {ik} ^ {\ beta-1} - [WH] ^ {\ beta-1} _ {ik}} {\ beta (\ beta-1)}} + [WH] ^ {\ beta-1} _ {ik} \ frac {[WH] _ {ik} -v_ {ik}} {\ beta } \ bigg)

Ungkapan ini pada dasarnya menggabungkan beberapa fungsi objektif: kapan \ beta = 2 itu dikonversi ke kuadrat dari jarak Euclidean (Squared Euclidean Distance), ketika \ beta \ rightarrow 1 mendekati jarak Divergensi Kullback-Leibler, dan pada \ beta \ rightarrow 0 - Untuk jarak Itakura-Saito (Itakura-Saito Divergence).

Pemilihan matriks langsung H diproduksi sebagai berikut: H diinisialisasi dengan nilai acak dari 0 hingga 1, setelah itu nilainya diperbarui secara iteratif sesuai dengan aturan berikut (jumlah iterasi diatur sebelumnya):

h_ {jk} = h_ {jk} \ frac {\ sum ^ R_ {i = 1} {w_ {ij} \ frac {v_ {ik}} {[WH] ^ {2- \ beta} _ {ik}} }} {\ jumlah ^ R_ {i = 1} {w_ {ij} [WH] ^ {\ beta-1} _ {ik}}}

Setiap nilai h_ {ij} sesuai dengan tingkat kesamaan saya karakter dari set dengan j -bagian gambar.


Jadi, untuk menentukan karakter mana yang harus diganti j bagian, cukup untuk menemukan nilai maksimum dalam j kolom matriks H . Nomor baris di mana nilai ini berada akan menjadi jumlah karakter yang diinginkan dalam set. Anda juga dapat memasukkan beberapa nilai ambang. \ epsilon , dan jika nilai maksimum yang ditemukan kurang dari ambang ini, maka bagian gambar diganti dengan spasi. Menggunakan spasi dapat memiliki efek positif pada tampilan gambar yang dihasilkan dibandingkan dengan menggunakan simbol dengan tingkat kemiripan yang rendah.

Implementasi


Algoritma ini diimplementasikan dalam C #. Grafik ASCII dihasilkan menggunakan 95 karakter (dari 0x20 hingga 0x7E) dengan ukuran 11x23 piksel; Font yang digunakan adalah Courier. Di bawah ini adalah kode sumber untuk fungsi untuk mengkonversi gambar asli ke gambar ASCII:

public static char[,] ConvertImage( Bitmap image, double beta, double threshold, ushort iterationsCount, ushort threadsNumber, Action<int> ProgressUpdated) { int charNumHor = (int)Math.Round((double)image.Width / glyphWidth); int charNumVert = (int)Math.Round((double)image.Height / glyphHeight); int totalCharactersNumber = charNumVert * charNumHor; int glyphSetSize = wNorm.ColumnCount; Matrix<double> v = SplitImage(image, charNumVert, charNumHor); Matrix<double> h = Matrix<double>.Build.Random( glyphSetSize, totalCharactersNumber, new ContinuousUniform()); int progress = 0; ushort step = (ushort)(iterationsCount / 10); for (ushort i = 0; i < iterationsCount; i++) { UpdateH(v, wNorm, h, beta, threadsNumber); if((i + 1) % step == 0) { progress += 10; if(progress < 100) { ProgressUpdated(progress); } } } var result = GetAsciiRepresentation(h, charNumVert, charNumHor, threshold); ProgressUpdated(100); return result; }

Pertimbangkan setiap langkah secara individual:

1) Kami menghitung berapa banyak karakter yang sesuai dengan lebar dan tinggi gambar:

 int charNumHor = (int)Math.Round((double)image.Width / glyphWidth); int charNumVert = (int)Math.Round((double)image.Height / glyphHeight);

Dengan menggunakan nilai yang dihitung, kami membagi gambar asli ke dalam blok ukuran yang diperlukan. Untuk setiap blok, kami menulis nilai intensitas warna piksel di kolom matriks yang sesuai V (jika perlu, kami memperluas gambar asli dengan menambahkan nilai nol yang sesuai dengan piksel putih ke matriks), setelah itu kami menormalkan semua kolom:

 private static Matrix<double> SplitImage( Bitmap image, int charNumVert, int charNumHor) { Matrix<double> result = Matrix<double>.Build.Dense( glyphHeight * glyphWidth, charNumHor * charNumVert); for (int y = 0; y < charNumVert; y++) { for (int x = 0; x < charNumHor; x++) { for (int j = 0; j < glyphHeight; j++) { for (int i = 0; i < glyphWidth; i++) { byte color = 0; if ((x * glyphWidth + i < image.Width) && (y * glyphHeight + j < image.Height)) { color = (byte)(255 - image.GetPixel( x * glyphWidth + i, y * glyphHeight + j).R); } result[glyphWidth * j + i, charNumHor * y + x] = color; } } } } result = result.NormalizeColumns(2.0); return result; }

2) Isi matriks H nilai acak dari 0 hingga 1:

 Matrix<double> h = Matrix<double>.Build.Random( glyphSetSize, totalCharactersNumber, new ContinuousUniform());

Kami menerapkan aturan pembaruan beberapa kali pada elemen-elemennya:

 for (ushort i = 0; i < iterationsCount; i++) { UpdateH(v, wNorm, h, beta, threadsNumber); if((i + 1) % step == 0) { progress += 10; if(progress < 100) { ProgressUpdated(progress); } } }

Memperbarui elemen-elemen matriks secara langsung diimplementasikan sebagai berikut (sayangnya, masalah yang terkait dengan pembagian dengan nol diselesaikan menggunakan beberapa kruk):

 private static void UpdateH( Matrix<double> v, Matrix<double> w, Matrix<double> h, double beta, ushort threadsNumber) { const double epsilon = 1e-6; Matrix<double> vApprox = w.Multiply(h); Parallel.For( 0, h.RowCount, new ParallelOptions() { MaxDegreeOfParallelism = threadsNumber }, j => { for (int k = 0; k < h.ColumnCount; k++) { double numerator = 0.0; double denominator = 0.0; for (int i = 0; i < w.RowCount; i++) { if (Math.Abs(vApprox[i, k]) > epsilon) { numerator += w[i, j] * v[i, k] / Math.Pow(vApprox[i, k], 2.0 - beta); denominator += w[i, j] * Math.Pow(vApprox[i, k], beta - 1.0); } else { numerator += w[i, j] * v[i, k]; if (beta - 1.0 > 0.0) { denominator += w[i, j] * Math.Pow(vApprox[i, k], beta - 1.0); } else { denominator += w[i, j]; } } } if (Math.Abs(denominator) > epsilon) { h[j, k] = h[j, k] * numerator / denominator; } else { h[j, k] = h[j, k] * numerator; } } }); }

3) Langkah terakhir adalah memilih simbol yang sesuai untuk setiap bagian gambar dengan menemukan nilai maksimum dalam kolom matriks H :

 private static char[,] GetAsciiRepresentation( Matrix<double> h, int charNumVert, int charNumHor, double threshold) { char[,] result = new char[charNumVert, charNumHor]; for (int j = 0; j < h.ColumnCount; j++) { double max = 0.0; int maxIndex = 0; for (int i = 0; i < h.RowCount; i++) { if (max < h[i, j]) { max = h[i, j]; maxIndex = i; } } result[j / charNumHor, j % charNumHor] = (max >= threshold) ? (char)(firstGlyphCode + maxIndex) : ' '; } return result; }

Gambar yang dihasilkan ditulis ke file html. Kode sumber lengkap dari program ini dapat ditemukan di sini .

Contoh gambar yang dihasilkan


Di bawah ini adalah contoh gambar yang dihasilkan pada berbagai nilai parameter \ beta dan jumlah iterasi. Gambar asli memiliki ukuran 407x500 piksel, masing-masing, gambar yang dihasilkan memiliki ukuran 37x22 karakter.


Kesimpulan


Dalam algoritma yang dipertimbangkan, kerugian berikut dapat dibedakan:

  1. Pemrosesan gambar yang panjang: tergantung pada ukuran gambar dan jumlah iterasi, pemrosesannya dapat berlangsung dari beberapa puluh detik hingga beberapa puluh menit.
  2. Buruknya kualitas pemrosesan detail gambar. Misalnya, upaya untuk mengubah gambar wajah manusia memberikan hasil berikut:


Pada saat yang sama, mengurangi jumlah bagian dengan meningkatkan kecerahan dan kontras gambar dapat secara signifikan meningkatkan tampilan gambar yang dihasilkan:


Secara umum, terlepas dari kekurangan di atas, kita dapat menyimpulkan bahwa algoritma memberikan hasil yang memuaskan.

Source: https://habr.com/ru/post/id463193/

More articles:


All Articles