Maksymalizacja wydajności przeglądania obrazów: jak może pomóc sortowanie wizualne

TLDR: W styczniu 2022 r. my — Visual Computing Group w HTW Berlin — przeprowadziliśmy eksperyment mający na celu ocenę sortowania obrazów. Wykazano, że obrazy w posortowanych układach znajdują się znacznie szybciej. Nasza nowa miara do oceny sortowania obrazów okazała się znacznie lepsza niż te zwykle używane do opisania postrzeganej jakości sortowania przez ludzi. Ponadto proponowane przez nas metody sortowania były w stanie wygenerować wysokiej jakości sortowanie obrazów znacznie wydajniej w porównaniu z innymi metodami.

W naszym eksperymencie wzięło udział ponad 2000 uczestników, którym jeszcze raz chcielibyśmy w tym miejscu podziękować. Opublikowany artykuł (https://onlinelibrary.wiley.com/doi/epdf/10.1111/cgf.14718) na wyniki eksperymentu mogą być trudne do zrozumienia dla osób niebędących specjalistami. Dlatego postaramy się tutaj w zrozumiały sposób podsumować motywację, wdrożenie i wyniki eksperymentu.

Ludzie mają trudności z rozpoznawaniem wielu obrazów na raz

Chociaż ludzie mogą szybko dostrzegać i rozumieć złożone obrazy, mają trudności z rozpoznawaniem wielu obrazów naraz. Ten problem pojawia się podczas wyszukiwania zdjęć w archiwach zdjęć lub produktów na stronach e-commerce. W takich przypadkach wyszukiwanie jest często bardzo trudne, gdy liczba odpowiednich obrazów jest bardzo duża. Ponieważ na ekranie można zobaczyć jednocześnie tylko 10–20 obrazów, często konieczne jest niekończące się przewijanie nieustrukturyzowanych list, aby znaleźć żądany obraz lub produkt.

Ludzie mogą łatwiej postrzegać obrazy, gdy są wyświetlane w posortowanej kolejności. Powyższy obrazek przedstawia 256 przyborów kuchennych IKEA, po lewej stronie w losowej kolejności, a po prawej posortowane według podobieństwa. Podczas wyszukiwania określonego obrazu, w przypadku nieposortowanym, jedyną opcją jest „skanowanie” obrazów rząd po rzędzie. W posortowanym układzie można szybko zidentyfikować odpowiedni region i skoncentrować wyszukiwanie na tym obszarze.

Cele eksperymentu

Celem przeprowadzonego eksperymentu było ustalenie, w jakim stopniu ludzie są w stanie dostrzec więcej obrazów na raz poprzez odpowiednie ich posortowanie i jak może to skrócić czas wyszukiwania obrazów. W szczególności poruszono następujące kwestie:

• Jakie rodzaje sortowania obrazów ludzie postrzegają jako przyjemne i pomocne?
• W jaki sposób można obiektywnie zmierzyć jakość sortowania wizualnego postrzeganą przez ludzi?
• Jakie metody najlepiej nadają się do efektywnego tworzenia posortowanych aranżacji odpowiadających preferencjom ludzi?

Zanim przedstawimy uzyskane w eksperymencie odpowiedzi na powyższe pytania, chcielibyśmy wyjaśnić zasadę sortowania na prostym przykładzie. Jeśli liczby 6, 5, 2, 8 i 3 mają być posortowane według ich wielkości, oznacza to, że musimy ułożyć liczby w taki sposób, aby każda liczba była większa od poprzedniej.

Ogólnie jest 1∙2∙3 ∙ … ∙ n = n! (czytaj „n silnia”) sposobów ułożenia n obiektów. W przypadku naszych pięciu liczb byłoby już 120 możliwych układów, z czego tylko dwa są posortowane (rosnąco lub malejąco). W przypadku większych zbiorów liczb istnieją wydajne algorytmy wyznaczania sortowania (optymalnego ułożenia).

Jak sortować obrazy?

Jeśli chodzi o sortowanie obrazów, nie jest jasne, jak właściwie wygląda dobre sortowanie ani jak to określić. W porównaniu z sortowaniem liczb istnieją dwie główne różnice: Po pierwsze, wygląd i zawartość obrazów nie są opisywane przez poszczególne liczby, ale przez tak zwane wektory cech. Oznacza to, że każdy obraz jest reprezentowany przez wektor w wielowymiarowej przestrzeni, przy czym wektory podobnych obrazów zwykle znajdują się blisko siebie. Po drugie, posortowane obrazy są zwykle ułożone na siatce 2D, co oznacza, że ​​istnieją sąsiedzi zarówno w kierunku poziomym, jak i pionowym. Liczba możliwych aranżacji ponownie rośnie silniczo wraz z liczbą obrazów. W przypadku ułożenia 100 obrazów na siatce 10×10, jest ich już 100! = 9,3∙10¹⁵⁷ możliwości (liczba o 158 cyfrach) ich ułożenia. Biorąc pod uwagę tak dużą liczbę, nawet najszybsze komputery nie są w stanie wypróbować wszystkich wariantów. Nawet gdyby można było porównać wszystkie układy, nie byłoby jasne, który z nich jest najlepiej posortowany.

Dla zilustrowania zasady sortowania obrazów można posłużyć się przykładem dwuwymiarowego sortowania kolorów. Kolory są opisywane przez składowe koloru czerwonego, zielonego i niebieskiego, dzięki czemu można je przedstawić jako wektory 3D. Aby sortować kolory dwuwymiarowo, tym wektorom 3D należy przypisać pozycję na siatce 2D. Poniższy rysunek przedstawia możliwe posortowane rozmieszczenie 9 ∙ 9 ∙ 9 (= 729) kolorów RGB na siatce 2D z 27 ∙ 27 (= 729) pozycjami.

Różnica między wizualnym sortowaniem obrazów w porównaniu z powyższym przykładem kolorów polega tylko na tym, że wymiary wektorów cech obrazów są znacznie większe. Mniej niż 100 wymiarów wystarczy do opisania wizualnego wyglądu obrazu, podczas gdy do opisania zawartości obrazu mogą być potrzebne tysiące wymiarów. Następnie proces sortowania próbuje umieścić podobne obrazy blisko siebie. Jeśli chcesz wiedzieć, jak faktycznie działają algorytmy sortowania obrazów, możesz przeczytać o tym w naszym artykule.

Używane zestawy obrazów

Przed przeprowadzeniem eksperymentu przeprowadziliśmy testy z różnymi zestawami obrazów o różnych rozmiarach. Okazało się, że przy zbyt wielu obrazach, niektóre z nich były bardzo trudne do znalezienia, niezależnie od ich sortowania. Z pewnością doprowadziłoby to do przerwania pracy wielu uczestników podczas wykonywania zadań wyszukiwania w eksperymencie. Z drugiej strony, przy bardzo małych zestawach, sortowanie obrazów miało niewielki wpływ na czas wyszukiwania, ponieważ poszukiwane obrazy były zwykle rozpoznawane i odnajdywane natychmiast.

W eksperymencie wykorzystano cztery różne zestawy. Pierwszy składał się z 1024 losowo generowanych kolorów RGB i służył jedynie do określenia postrzeganej jakości różnych metod sortowania. Dla trzech innych zestawów obrazów rejestrowano również czas znalezienia żądanych obrazów. Te trzy zestawy zostały wybrane w taki sposób, aby z jednej strony reprezentowały różne scenariusze wyszukiwania, az drugiej nadal istniała znacząca różnica w szybkości wyszukiwania między układami posortowanymi i losowymi. Pierwszy zestaw składał się ze 169 znaków drogowych, tak jak można je było przedstawić na tablicach poglądowych. Drugi zestaw składał się z 256 zdjęć przyborów kuchennych IKEA, tak jak są one zwykle prezentowane na stronach e-commerce. Ostatni zestaw składał się z 400 obrazów dla 70 niepowiązanych wyszukiwanych haseł, które zostały przeszukane z Internetu. Ten zestaw może reprezentować osobiste zdjęcia.

Realizacja eksperymentu

Eksperyment składał się z dwóch części. W pierwszej części rejestrowano preferencje uczestników, prosząc ich o obejrzenie par posortowanych układów obrazów i podjęcie decyzji, który z dwóch układów preferują. Preferowanymi układami były te, które „mają przejrzystą strukturę, zapewniają lepszy przegląd i ułatwiają odnalezienie wyszukiwanych obrazów”. W drugiej części eksperymentu uczestnicy zostali poproszeni o jak najszybsze odnalezienie poszukiwanych obrazów w posortowanych układach. Zbadano, czy preferencje sortowania uczestników umożliwiają również szybsze wyszukiwanie. Ponadto zbadaliśmy, jak dobrze można przewidzieć czas wyszukiwania na podstawie jakości sortowania.

Zbadane metody sortowania i miary jakości

W naszych eksperymentach stosowaliśmy różne metody generowania posortowanych układów. Oprócz map samoorganizujących się (SOM) użyliśmy map samosortujących (SSM), IsoMatch i dyskretnej projekcji t-SNE . Porównaliśmy te metody z naszymi własnymi metodami sortowania przydziału liniowego (LAS) i szybkiego sortowania przydziału liniowego(FLAS). Więcej szczegółów na temat algorytmów stosowanych dla każdej metody można znaleźć w naszej wspomnianej publikacji. Gdy tylko było to możliwe, wygenerowaliśmy wiele aranżacji przy użyciu różnych ustawień parametrów dla każdej metody. Aby mieć przykłady niskiej jakości sortowania do porównania, wygenerowano również niektóre źle posortowane układy (oznaczone jako „niska jakość”). Nie zastosowano przypadkowych układów, ponieważ doprowadziłoby to do przerwania eksperymentu, ponieważ znalezienie obrazów byłoby zbyt trudne.

Istnieją miary oceny układów 2D, ale nie ma badań pokazujących, jak dobrze odzwierciedlają one jakość postrzeganą przez ludzi. Te miary jakości porównują odległości wektorów cech w dużej wymiarowości z wynikowymi odległościami obrazów na siatce 2D. Zwykle używana jest funkcja korelacji krzyżowej lub znormalizowana funkcja energii, ale obie zachowują się podobnie, więc porównaliśmy tylko tę drugą. Zaproponowaliśmy nową miarę o nazwie „ Jakość zachowania odległości ” (DPQ) do oceny układów 2D.

Postrzegana jakość sortowania

Kolejny rysunek przedstawia zrzut ekranu pierwszej części eksperymentu. Wszystkim uczestnikom pokazano 16 par układów i poproszono ich o podjęcie decyzji, czy wolą lewy, czy prawy układ lub uważają je za równoważne.

Aby wykluczyć potencjalny wpływ bezsensownych ocen, w każdym eksperymencie przedstawiono parę skrajnie różnych sortowań jakości. Jeśli uczestnik preferował znacznie gorsze sortowanie w tej parze, jego oceny dla wszystkich sortowań były odrzucane. W sumie zbadano 32 sortowania dla zestawu kolorów i 23 sortowania dla każdego z trzech zestawów obrazów. Odpowiadając niemieckiej piłkarskiej Bundeslidze, gdzie jest 18 drużyn i 18∙17 = łącznie 306 meczów w sezonie, co odpowiada 153 różnym pojedynkom, w tym eksperymencie było 496 możliwych par dla zestawu kolorów i 253 możliwych par dla każdego z trzech zestawów obrazów.

Podobne podejście do piłki nożnej zastosowano do oceny wszystkich porównań, w których mecz może zakończyć się zwycięstwem, porażką lub remisem. W porównaniu dwóch sortowań preferowane sortowanie otrzymało jeden punkt. Jeśli oba sortowania zostały ocenione jako równe, oba otrzymały pół punktu. W przeciwieństwie do piłki nożnej, w której w ciągu sezonu rozgrywane są dwa mecze między dwiema drużynami, każda para sortująca była oceniana co najmniej 35 razy przez różnych uczestników. Na podstawie tych ocen określono średni wynik dla każdego sortowania w parze. Te dwa wyniki, które sumują się do 1, opisują stosunek, w którym jedno sortowanie zostało ocenione lepiej niż drugie. W celu ogólnego porównania wszystkich sortowań zsumowano otrzymane przez nich wyniki ze wszystkich porównań par.

Miara jakości, która ocenia jakość sortowania, powinna ściśle odpowiadać ocenie jakości użytkowników. Poniższe liczby pokazują korelację średniej oceny sortowania przez użytkowników (wynik użytkownika) w porównaniu z dwoma zbadanymi miarami jakości. Tutaj E'1 oznacza powszechnie używaną „znormalizowaną funkcję energii”, a DPQ oznacza zaproponowaną przez nas „Jakość zachowania odległości”. Kolory symboli reprezentują różne metody sortowania.

Te dwie liczby pokazują, że nasza nowa miara DPQ ma wyższą korelację z ocenami użytkowników, co oznacza, że ​​lepiej nadaje się do przewidywania jakości sortowania postrzeganej przez ludzi.

Czasy wyszukiwania

W drugiej części eksperymentu użytkownikom pokazywano różne posortowane układy, z których każdy miał znaleźć cztery losowe obrazy. Po znalezieniu obrazu natychmiast wyświetlał się następny. Zastosowane sortowania były takie same jak w pierwszej części eksperymentu.

Oczywiście trudność znalezienia obrazów zależy w dużej mierze od wyszukiwanych obrazów, ponieważ niektóre obrazy są bardziej zauważalne niż inne. Ponadto uczestnicy różnią się zdolnościami wyszukiwania. Przy zaledwie kilku próbach te dwa aspekty mogą znacznie zniekształcić wyniki. Jednak łącznie wykonano ponad 28 000 takich zadań wyszukiwania. Oznacza to, że dla każdego sortowania przeprowadzono ponad 400 wyszukiwań po cztery obrazy. Tak duża liczba zrekompensowała zarówno różną trudność zadań poszukiwawczych, jak i nierówne umiejętności uczestników.

Kolejne rysunki pokazują rozkład czasów wyszukiwania dla 23 różnych sortowań dla zestawu znaków drogowych i obrazów internetowych (obrazy internetowe). Mediany czasów wyszukiwania dla różnych sortowań są pokazane jako kolorowe znaczniki. Ponownie pokazuje to silniejszą (ujemną) korelację czasów wyszukiwania z naszą miarą DPQ w porównaniu ze znormalizowaną funkcją energii.

Porównując sortowania umożliwiające szybkie wyszukiwanie z tymi, które zostały wysoko ocenione, również zaobserwowano silną zgodność. Jednak dla szybkiego wyszukiwania ważniejsze było, aby wszystkie podobne obrazy były ułożone bardzo blisko siebie, nawet jeśli w rezultacie globalny układ sortowania został oceniony nieco gorzej. Następny rysunek po lewej stronie pokazuje sortowanie, które zostało ocenione najwyżej dla zestawu obrazów internetowych, a po prawej sortowanie, w którym obrazy zostały znalezione najszybciej. Po lewej stronie przejścia są płynniejsze, podczas gdy po prawej wszystkie powiązane obrazy są blisko siebie, co skutkuje trudnymi przejściami.

Porównanie metod sortowania

Ostatnim krokiem było lepsze zrozumienie działania różnych metod sortowania. Ponieważ czas pracy w dużym stopniu zależy od sprzętu, podane czasy służą jedynie jako wartości orientacyjne. Ponieważ jakość zachowania odległości ma wysoką korelację z preferencjami użytkownika, wykorzystano ją do porównania jakości sortowania algorytmów w zależności od wymaganego czasu obliczeń.

Na kolejnym rysunku przedstawiono uzyskaną jakość sortowania w funkcji wymaganego czasu obliczeń dla badanych metod przy zmianie parametrów metody. W przypadku mniejszych zestawów danych, takich jak 256 obrazów przyborów kuchennych, nasza metoda FLAS zapewnia najlepszy kompromis między jakością a czasem obliczeń. LAS i t-SNE mogą zapewnić nieco wyższą jakość, ale są od 10 do 100 razy wolniejsze. W przypadku 1024 losowych kolorów RGB nasze metody LAS i FLAS osiągnęły najwyższą jakość sortowania.

Kolejnym badaniem było zbadanie, jak zachowują się jakość i czas obliczeń dla zestawów obrazów o różnych rozmiarach. W tym celu wybrano ustawienia parametrów oznaczone ⦿ na poprzednim rysunku. Podczas gdy SOM, SSM, LAS i FLAS mogą generować lepsze sortowanie dla większej liczby obrazów, sortowanie dla t-SNE i IsoMatch uległo pogorszeniu.

Wyniki eksperymentu

Ogólnie byliśmy bardzo zadowoleni z wyników eksperymentu, ponieważ na postawione wcześniej pytania można było jasno odpowiedzieć. Wykazano, że ludzie mogą znaleźć obrazy znacznie szybciej w posortowanych układach. Analizując sortowanie obrazów, które ludzie uważają za przyjemne i pomocne, stwierdzono, że duże lokalne podobieństwo sąsiednich obrazów jest ważniejsze niż globalne utrzymywanie relacji podobieństwa wszystkich obrazów. Ponadto nasza propozycja nowej oceny jakości sortowania obrazów była znacznie lepsza niż poprzednie metody w odzwierciedlaniu jakości postrzeganej przez ludzi.

Stało się jasne, że proponowane przez nas metody sortowania LAS i FLAS mogą zapewnić sortowanie wysokiej jakości, a FLAS jest również bardzo wydajny. Ponadto nasze metody oferują różne opcje wpływania na sortowanie, takie jak stałe pozycjonowanie niektórych obrazów lub możliwość korzystania z układów innych niż prostokątne. Metoda FLAS (wraz z wykresem obrazu) jest tak szybka, że ​​możliwe staje się wizualne eksplorowanie milionów obrazów. Navigu.net jest przykładem takiego narzędzia do wizualnej eksploracji obrazu.

Więcej informacji na temat naszych badań można znaleźć na stronie www.visual-computing.com .