Memaksimalkan Efisiensi Tampilan Gambar: Bagaimana Penyortiran Visual Dapat Membantu

TLDR: Pada Januari 2022, kami — Grup Komputasi Visual di HTW Berlin — melakukan eksperimen untuk mengevaluasi penyortiran gambar. Terlihat bahwa gambar dalam susunan terurut ditemukan jauh lebih cepat. Ukuran baru kami untuk mengevaluasi penyortiran gambar terbukti jauh lebih baik daripada yang biasanya digunakan untuk menggambarkan kualitas penyortiran yang dirasakan oleh manusia. Selain itu, metode penyortiran yang kami usulkan mampu menghasilkan penyortiran gambar berkualitas tinggi jauh lebih efisien dibandingkan metode lainnya.

Lebih dari 2000 peserta mengambil bagian dalam eksperimen kami, dan kami ingin berterima kasih lagi kepada mereka di sini. Artikel yang diterbitkan (https://onlinelibrary.wiley.com/doi/epdf/10.1111/cgf.14718) pada hasil percobaan mungkin sulit dipahami oleh non-spesialis. Oleh karena itu, kami akan mencoba merangkum motivasi, implementasi, dan hasil eksperimen dengan cara yang dapat dipahami di sini.

Orang mengalami kesulitan mengenali banyak gambar sekaligus

Meskipun manusia dapat dengan cepat memahami dan memahami gambar yang kompleks, mereka mengalami kesulitan mengenali banyak gambar sekaligus. Masalah ini muncul saat mencari gambar di arsip foto atau produk di website e-commerce. Dalam kasus seperti itu, pencarian seringkali sangat sulit ketika jumlah gambar yang relevan sangat banyak. Karena hanya 10-20 gambar yang dapat dilihat sekaligus di layar, pengguliran tanpa henti melalui daftar yang tidak terstruktur seringkali diperlukan untuk menemukan gambar atau produk yang diinginkan.

Manusia dapat melihat gambar dengan lebih mudah saat ditampilkan dalam urutan yang diurutkan. Gambar di atas menunjukkan 256 item peralatan dapur IKEA, di sebelah kiri dalam urutan acak dan di sebelah kanan diurutkan berdasarkan kesamaan. Saat mencari gambar tertentu, dalam kasus yang tidak disortir, satu-satunya pilihan adalah "memindai" gambar baris demi baris. Dalam susunan yang diurutkan, wilayah yang sesuai dapat diidentifikasi dengan cepat, dan pencarian dapat difokuskan pada wilayah tersebut.

Tujuan Eksperimen

Tujuan dari percobaan yang dilakukan adalah untuk menentukan sejauh mana orang dapat melihat lebih banyak gambar sekaligus melalui penyortiran gambar yang sesuai, dan bagaimana hal ini dapat mengurangi waktu yang diperlukan untuk menemukan gambar. Secara khusus, pertanyaan-pertanyaan berikut ditujukan:

• Jenis penyortiran gambar apa yang menurut orang menyenangkan dan bermanfaat?
• Bagaimana kualitas penyortiran visual, seperti yang dirasakan oleh orang-orang, diukur secara objektif?
• Metode mana yang paling cocok untuk secara efisien membuat pengaturan terurut yang sesuai dengan preferensi orang?

Sebelum menyajikan jawaban yang diperoleh dalam percobaan atas pertanyaan-pertanyaan tersebut di atas, kami ingin menjelaskan prinsip pengurutan dengan menggunakan contoh sederhana. Jika angka 6, 5, 2, 8, dan 3 akan diurutkan menurut ukurannya, artinya kita harus mengatur angka sedemikian rupa sehingga setiap angka lebih besar dari angka sebelumnya.

Secara umum, ada 1∙2∙3 ∙ … ∙ n = n! (baca “n faktorial”) cara menyusun n objek. Dalam kasus lima angka kita, sudah ada 120 kemungkinan susunan, yang hanya dua di antaranya yang diurutkan (naik atau turun). Untuk kumpulan angka yang lebih besar, ada algoritma yang efisien untuk menentukan penyortiran (pengaturan optimal).

Bagaimana cara mengurutkan gambar?

Dalam hal menyortir gambar, tidak jelas seperti apa sebenarnya penyortiran yang baik atau bagaimana menentukannya. Dibandingkan dengan nomor pengurutan, ada dua perbedaan utama: Pertama, tampilan dan konten gambar tidak dijelaskan oleh nomor individu, melainkan oleh apa yang disebut vektor fitur. Ini berarti bahwa setiap gambar diwakili oleh vektor dalam ruang berdimensi tinggi, dengan vektor gambar serupa biasanya terletak berdekatan satu sama lain. Kedua, gambar yang diurutkan biasanya disusun dalam kisi 2D, artinya ada tetangga dalam arah horizontal dan vertikal. Jumlah susunan yang mungkin kembali tumbuh secara faktorial dengan jumlah gambar. Untuk susunan 100 gambar pada grid 10×10, sudah ada 100! = 9,3∙10¹⁵⁷ kemungkinan (bilangan dengan 158 digit) untuk menyusunnya. Mengingat jumlah yang begitu besar, bahkan mustahil bagi komputer tercepat untuk mencoba semua varian. Bahkan jika memungkinkan untuk membandingkan semua pengaturan, tidak akan jelas mana yang paling baik disortir.

Untuk mengilustrasikan prinsip penyortiran gambar, penyortiran warna dua dimensi dapat menjadi contoh. Warna dijelaskan oleh komponen merah, hijau, dan birunya dan dengan demikian dapat direpresentasikan sebagai vektor 3D. Untuk mengurutkan warna secara dua dimensi, vektor 3D ini harus diberi posisi pada kisi 2D. Gambar berikut menunjukkan kemungkinan susunan terurut dari 9 ∙ 9 ∙ 9 (= 729) warna RGB pada grid 2D dengan posisi 27 ∙ 27 (= 729).

Perbedaan pemilahan visual citra dibandingkan dengan contoh warna yang disebutkan di atas hanyalah dimensi vektor fitur citra yang jauh lebih tinggi. Kurang dari 100 dimensi cukup untuk mendeskripsikan tampilan visual suatu gambar, sementara ribuan dimensi mungkin diperlukan untuk mendeskripsikan konten gambar. Proses penyortiran kemudian mencoba memposisikan gambar yang mirip satu sama lain. Jika Anda ingin mengetahui bagaimana sebenarnya algoritma untuk mengurutkan gambar bekerja, Anda dapat membacanya di makalah kami.

Kumpulan gambar bekas

Sebelum melakukan percobaan, kami melakukan pengujian dengan berbagai set gambar dengan ukuran berbeda. Ternyata dengan terlalu banyak gambar, beberapa di antaranya sangat sulit ditemukan, terlepas dari pemilahannya. Hal ini tentunya akan menyebabkan penghentian banyak peserta selama tugas pencarian dalam percobaan. Di sisi lain, dengan set yang sangat kecil, penyortiran gambar memiliki sedikit pengaruh pada waktu pencarian, karena gambar yang diinginkan biasanya dikenali dan segera ditemukan.

Dalam percobaan, empat set yang berbeda digunakan. Yang pertama terdiri dari 1024 warna RGB yang dihasilkan secara acak dan hanya digunakan untuk menentukan kualitas yang dirasakan dari berbagai metode penyortiran. Untuk tiga kumpulan gambar lainnya, waktu untuk menemukan gambar yang diinginkan juga direkam. Ketiga set ini dipilih sedemikian rupa sehingga mewakili skenario pencarian yang berbeda di satu sisi, dan masih ada perbedaan yang signifikan dalam kecepatan pencarian antara pengaturan terurut dan acak di sisi lain. Set pertama terdiri dari 169 rambu lalu lintas seperti yang dapat digambarkan pada papan ikhtisar. Set kedua adalah 256 gambar item peralatan dapur IKEA, seperti yang biasanya ditampilkan di situs web e-niaga. Kumpulan terakhir terdiri dari 400 gambar untuk 70 istilah pencarian yang tidak terkait yang dirayapi dari internet. Set ini bisa mewakili foto pribadi.

Implementasi percobaan

Percobaan terdiri dari dua bagian. Pada bagian pertama, preferensi peserta dicatat dengan meminta mereka melihat pasangan susunan gambar yang diurutkan dan memutuskan mana dari dua susunan yang mereka sukai. Pengaturan yang disukai adalah yang “memiliki struktur yang lebih jelas, memberikan ikhtisar yang lebih baik, dan memudahkan untuk menemukan gambar yang dicari”. Pada bagian kedua percobaan, peserta diminta untuk menemukan gambar yang dicari dalam susunan yang diurutkan secepat mungkin. Itu diperiksa apakah preferensi penyortiran peserta juga memungkinkan pencarian lebih cepat. Selain itu, kami menyelidiki seberapa baik waktu pencarian dapat diprediksi menggunakan kualitas penyortiran.

Menyelidiki metode penyortiran dan ukuran kualitas

Dalam percobaan kami, kami menggunakan berbagai metode untuk menghasilkan pengaturan yang diurutkan. Selain Self Organizing Maps (SOM), kami menggunakan Self Sorting Maps (SSM), IsoMatch , dan proyeksi t-SNE diskrit . Kami membandingkan metode ini dengan pendekatan kami sendiri Penyortiran Penugasan Linier (LAS) dan Penyortiran Penugasan Linier Cepat(FLAS). Rincian lebih lanjut tentang algoritme yang digunakan untuk setiap metode dapat ditemukan di publikasi kami yang disebutkan di atas. Jika memungkinkan, kami membuat beberapa pengaturan menggunakan pengaturan parameter yang berbeda untuk setiap metode. Untuk mendapatkan contoh kualitas penyortiran yang rendah sebagai perbandingan, beberapa susunan yang disortir dengan buruk juga dihasilkan (ditunjuk sebagai “Kualitas rendah.”). Pengaturan acak tidak digunakan karena akan menyebabkan interupsi percobaan, karena menemukan gambar akan terlalu sulit.

Ada ukuran untuk mengevaluasi pengaturan 2D, tetapi tidak ada penelitian yang menunjukkan seberapa baik mereka mencerminkan kualitas yang dirasakan oleh manusia. Ukuran kualitas ini membandingkan jarak vektor fitur dalam dimensi tinggi dengan jarak gambar yang dihasilkan pada kisi 2D. Biasanya, korelasi silang atau fungsi energi yang dinormalisasi digunakan, tetapi keduanya berperilaku serupa, jadi kami hanya membandingkan yang terakhir. Kami mengusulkan ukuran baru yang disebut " Kualitas Pelestarian Jarak " (DPQ) untuk mengevaluasi pengaturan 2D.

Kualitas penyortiran yang dirasakan

Gambar berikutnya menunjukkan tangkapan layar dari bagian pertama percobaan. Semua peserta diperlihatkan 16 pasang susunan, dan mereka diminta untuk memutuskan apakah mereka lebih suka susunan kiri atau kanan atau menganggap keduanya setara.

Untuk mengecualikan pengaruh potensial dari evaluasi yang tidak berarti, dalam setiap percobaan disajikan sepasang penyortiran kualitas yang sangat berbeda. Jika seorang peserta lebih menyukai penyortiran yang jauh lebih buruk pada pasangan ini, penilaian mereka untuk semua penyortiran akan dibuang. Secara total, 32 penyortiran untuk set warna dan 23 penyortiran untuk masing-masing dari tiga set gambar diperiksa. Sesuai dengan Bundesliga sepak bola Jerman, di mana ada 18 tim dan total 18∙17 = 306 pertandingan dalam satu musim, yang sesuai dengan 153 pertandingan berbeda, dalam percobaan ini ada 496 kemungkinan pasangan untuk set warna dan 253 kemungkinan pasangan untuk masing-masing dari tiga set gambar.

Pendekatan serupa untuk sepak bola digunakan untuk mengevaluasi semua perbandingan, di mana pertandingan bisa berakhir dengan menang, kalah, atau seri. Dalam perbandingan dua penyortiran, penyortiran yang disukai mendapat satu poin. Jika kedua penyortiran dinilai sama, keduanya menerima setengah poin. Berbeda dengan sepak bola, di mana ada dua pertandingan antara dua tim per musim, setiap pasangan pemilahan dievaluasi setidaknya 35 kali oleh peserta yang berbeda. Dari evaluasi tersebut, ditentukan skor rata-rata untuk setiap penyortiran dalam suatu pasangan. Kedua skor ini, yang berjumlah 1, menggambarkan rasio di mana satu penyortiran dinilai lebih baik daripada yang lain. Untuk perbandingan keseluruhan dari semua penyortiran, skor yang mereka terima dari semua perbandingan pasangan dijumlahkan.

Ukuran kualitas yang mengevaluasi kualitas penyortiran harus sesuai dengan evaluasi kualitas pengguna. Angka-angka berikut menunjukkan korelasi peringkat pengguna rata-rata dari penyortiran (Skor Pengguna) dibandingkan dengan dua ukuran kualitas yang diselidiki. Di sini, E'1 adalah singkatan dari "fungsi energi yang dinormalisasi" yang umum digunakan, dan DPQ adalah singkatan dari "Kualitas Pengawetan Jarak" yang kami usulkan. Warna simbol mewakili metode penyortiran yang berbeda.

Kedua angka tersebut menunjukkan bahwa ukuran DPQ baru kami memiliki korelasi yang lebih tinggi dengan peringkat pengguna, yang berarti lebih cocok untuk memprediksi kualitas penyortiran yang dirasakan oleh manusia.

Waktu pencarian

Pada bagian kedua percobaan, para pengguna diperlihatkan berbagai pengaturan yang diurutkan, di mana masing-masing dari empat gambar acak dapat ditemukan. Begitu sebuah gambar ditemukan, gambar berikutnya segera ditampilkan. Sortasi yang digunakan sama seperti pada percobaan bagian pertama.

Tentu saja, kesulitan menemukan gambar sangat bergantung pada gambar yang dicari, karena beberapa gambar lebih terlihat daripada yang lain. Selain itu, peserta berbeda dalam kemampuan pencarian mereka. Dengan hanya beberapa uji coba, kedua aspek ini dapat mendistorsi hasil secara signifikan. Namun, total lebih dari 28.000 tugas pencarian ini dilakukan. Ini berarti bahwa untuk setiap pengurutan, lebih dari 400 pencarian dilakukan untuk masing-masing empat gambar. Jumlah yang tinggi ini mengimbangi berbagai kesulitan tugas pencarian dan kemampuan peserta yang tidak setara.

Angka berikutnya menunjukkan distribusi waktu pencarian untuk 23 penyortiran yang berbeda untuk kumpulan rambu lalu lintas dan gambar Internet (Gambar Web). Nilai median dari waktu pencarian untuk penyortiran yang berbeda ditampilkan sebagai penanda berwarna. Sekali lagi, ini menunjukkan korelasi yang lebih kuat (negatif) dari waktu pencarian dengan ukuran DPQ kami dibandingkan dengan fungsi energi yang dinormalisasi.

Saat membandingkan penyortiran yang memungkinkan pencarian cepat dengan yang berperingkat tinggi, kesepakatan yang kuat juga diamati. Namun, untuk pencarian cepat, yang lebih penting adalah semua gambar serupa disusun sangat dekat satu sama lain, bahkan jika pengaturan penyortiran global dinilai sedikit lebih buruk sebagai hasilnya. Gambar berikutnya di sebelah kiri menunjukkan pengurutan yang dinilai paling tinggi untuk kumpulan Gambar Web, dan di sebelah kanan adalah pengurutan tempat gambar ditemukan paling cepat. Di sebelah kiri, transisinya lebih halus, sedangkan di sebelah kanan, semua gambar terkait saling berdekatan, menghasilkan beberapa transisi yang sulit.

Perbandingan metode pengurutan

Langkah terakhir adalah untuk mendapatkan pemahaman yang lebih baik tentang kinerja metode penyortiran yang berbeda. Karena runtime sangat bergantung pada perangkat keras, waktu yang diberikan hanya berfungsi sebagai nilai referensi. Karena Kualitas Pengawetan Jarak memiliki korelasi yang tinggi dengan preferensi pengguna, ini digunakan untuk membandingkan kualitas pengurutan algoritme tergantung pada waktu komputasi yang diperlukan.

Gambar berikutnya menunjukkan kualitas penyortiran yang dicapai versus waktu komputasi yang diperlukan untuk metode yang diselidiki sambil memvariasikan parameter metode. Untuk kumpulan data yang lebih kecil seperti 256 gambar peralatan dapur, metode FLAS kami menawarkan kompromi terbaik antara kualitas dan waktu komputasi. LAS dan t-SNE dapat memberikan kualitas yang sedikit lebih tinggi tetapi 10 hingga 100 kali lebih lambat. Untuk 1024 warna RGB acak, metode LAS dan FLAS kami mencapai kualitas penyortiran tertinggi.

Investigasi lain adalah untuk menguji bagaimana kualitas dan waktu komputasi berperilaku untuk kumpulan gambar berukuran berbeda. Pengaturan parameter yang ditandai dengan ⦿ pada gambar sebelumnya dipilih untuk tujuan ini. Sementara SOM, SSM, LAS, dan FLAS dapat menghasilkan penyortiran yang lebih baik untuk lebih banyak gambar, penyortiran untuk t-SNE dan IsoMatch menjadi lebih buruk.

Hasil Eksperimen

Secara keseluruhan, kami sangat puas dengan hasil percobaan, karena pertanyaan yang diajukan sebelumnya dapat dijawab dengan jelas. Telah ditunjukkan bahwa manusia dapat menemukan gambar secara signifikan lebih cepat dalam pengaturan yang diurutkan. Saat menganalisis penyortiran gambar yang menurut orang menyenangkan dan bermanfaat, ditemukan bahwa kesamaan lokal yang tinggi dari gambar tetangga lebih penting daripada mempertahankan hubungan kesamaan semua gambar secara global. Selain itu, proposal kami untuk evaluasi kualitas baru penyortiran gambar secara signifikan lebih baik daripada metode sebelumnya dalam mencerminkan kualitas yang dirasakan oleh manusia.

Menjadi jelas bahwa metode penyortiran yang kami usulkan LAS dan FLAS dapat menghasilkan penyortiran berkualitas tinggi dan FLAS juga sangat efisien. Selain itu, metode kami menawarkan berbagai opsi untuk memengaruhi penyortiran, seperti posisi tetap gambar tertentu atau kemampuan untuk menggunakan tata letak selain persegi panjang. Metode FLAS (bersama dengan grafik gambar) sangat cepat sehingga memungkinkan untuk menjelajahi jutaan gambar secara visual. Navigu.net adalah contoh alat eksplorasi gambar visual semacam itu.

Untuk informasi lebih lanjut tentang penelitian kami, kunjungi www.visual-computing.com .