Эксперимент с сортировкой изображений
Улучшаем эффективность просмотра изображений с помощью визуальной сортировки
Главная мысль: В январе 2022 года мы — группа специалистов по визуальным вычислениям HTW Berlin — провели эксперимент, в ходе которого оценивали сортировку изображений. Исследование показало, что люди находят отсортированные изображения гораздо быстрее. Наш новый метод измерения оценки качества сортировки изображений оказался значительно лучше тех, которые обычно используют для описания того, как люди воспринимают качество сортировки. Кроме того, предложенные нами методы генерации сортировок оказались гораздо более эффективными по сравнению с другими.
В нашем эксперименте приняли участие более 2000 человек. Мы хотели бы еще раз поблагодарить их за это. Мы опубликовали статью о результатах эксперимента, но неспециалистам она может показаться сложной для понимания. Поэтому здесь мы попытаемся кратко и в понятной форме изложить мотивы, которые подтолкнули нас к эксперименту, процесс его проведения и результаты.
Людям трудно обрабатывать много изображений одновременно
Несмотря на то, что человек может быстро воспринимать и понимать суть сложных изображений, ему трудно обрабатывать множество изображений одновременно. Эта проблема возникает при поиске картинок в фотостоках или товаров в интернет-магазинах. Когда количество подходящих изображений очень велико, трудно найти то, что нужно. С экрана человек может одновременно обработать информацию только с 10-20 изображений. Для поиска нужного изображения или товара часто приходится бесконечно скроллить неупорядоченные списки.
Люди легче воспринимают изображения, когда они отсортированы. На изображении выше — 256 кухонных принадлежностей ИКЕА. Слева они расположены в хаотичном порядке, справа — отсортированы по общим признакам. При поиске конкретного изображения в неотсортированном виде единственный вариант просмотра — «сканирование» изображений ряд за рядом. При сортировке можно быстро определить подходящую область и искать именно там.
Цели эксперимента
Цель проведённого эксперимента — определить, в какой степени люди способны обрабатывать большее количество изображений одновременно благодаря правильно подобранной сортировке. И как она может сократить время поиска изображения. В частности, в ходе эксперимента мы пытались получить ответы на следующие вопросы:
- Какие виды сортировки изображений люди воспринимают как удобные и полезные?
- Как можно объективно измерить восприятие качества сортировки людьми?
- Какие методы лучше всего подходят для создания эффективной сортировки, которая соответствует предпочтениям людей?
Что на самом деле означает слово «сортировка»?
Прежде чем представить полученные в ходе эксперимента ответы на вопросы, мы хотели бы объяснить принцип сортировки на простом примере. Если числа 6, 5, 2, 8 и 3 нужно отсортировать по величине, это означает, что нам следует расположить их таким образом, чтобы каждое из них было больше предыдущего.
В общем случае существует 1 × 2 × 3 × ... × n = n! (читается «n-факториал») способов расположить n объектов. В случае с нашими пятью числами существует 120 возможных вариантов их расположения (1 × 2 × 3 × 4 × 5 = 120). Из них только в двух случаях числа будут отсортированы: по возрастанию или убыванию. Для большого состава чисел существуют эффективные алгоритмы сортировки, или их оптимального расположения.
Как сортировать изображения?
Когда речь идёт о сортировке изображений, не совсем понятно, как выглядит хорошая сортировка и как её определить. Если сравнивать её с сортировкой чисел, есть два основных отличия:
- Во-первых, не отдельные числа, а так называемые векторы признаков описывают внешний вид и содержание изображений. Вектор признаков состоит из значений, которые соответствуют некоторому набору признаков определённого объекта. Это означает, что каждое изображение представлено вектором в многомерном пространстве, причем векторы похожих изображений обычно находятся близко друг к другу.
- Во-вторых, отсортированные изображения обычно расположены на двухмерной сетке, что означает наличие у них соседей как по горизонтали, так и по вертикали. Число возможных вариантов расположения опять же увеличивается в разы с ростом числа изображений. Для расположения 100 изображений на сетке 10×10 существует уже 100! = 9,3∙10¹⁵⁷ вариантов (число, которое состоит из 158 цифр). При таком большом количестве вариантов даже самые мощные компьютеры не в состоянии обработать их все. Даже если бы можно было сравнить все варианты, осталось бы непонятно, какой из них лучше отсортирован.
Для иллюстрации принципа сортировки изображений примером может служить двухмерная сортировка цветов RGB. Красная, зелёная и синяя составляющие описывают цвета, и поэтому их можно представить в виде трёхмерных векторов. Чтобы отсортировать цвета в двухмерном пространстве, этим трёхмерным векторам необходимо присвоить положение на двухмерной сетке. На следующем рисунке показано отсортированное расположение 9 × 9 × 9 (= 729) цветов RGB на двухмерной сетке с 27 × 27 (= 729) позициями.
Разница между визуальной сортировкой изображений по сравнению с примером с цветами, упомянутым выше, заключается лишь в том, что векторов с признаками изображений гораздо больше. Для описания внешнего вида изображения достаточно менее 100 характеристик, в то время как для описания содержания изображения могут потребоваться тысячи характеристик. Затем в процессе сортировки алгоритм будет пытаться располагать похожие изображения рядом друг с другом. Если вы хотите узнать, как на самом деле работают алгоритмы сортировки изображений, вы можете прочитать об этом в нашей статье.
Используемые наборы изображений
Перед проведением эксперимента мы протестировали различные наборы изображений. Наборы включали разное количество изображений. Оказалось, что если изображений слишком много, то найти определённое изображение было слишком трудно, независимо от сортировки. Это, безусловно, привело бы к тому, что в ходе эксперимента многие участники прекратили бы выполнять задания по их поиску. С другой стороны, при очень маленьких выборках сортировка изображений практически не влияла на время поиска, так как нужные изображения было легко увидеть и найти.
В эксперименте мы использовали четыре различных набора изображений. Первый состоял из 1024 случайно сгенерированных цветов RGB. Его мы использовали только для определения того, как участники оценивают качество различных методов сортировки.
Для трёх других наборов изображений мы, кроме прочего, фиксировали время поиска нужных картинок. Эти три набора мы выбирали таким образом, чтобы, с одной стороны, они представляли различные сценарии поиска, а с другой — разница в скорости поиска нужного изображения в случае с сортировкой и в случае с хаотичным расположением изображений оставалась значимой.
Первый набор состоял из 169 дорожных знаков, расположенных так, как их обычно изображают на стендах.
Второй набор включал 256 изображений кухонных принадлежностей ИКЕА. Мы представили их так, как обычно их располагают на сайтах электронной коммерции.
Последний набор содержал 400 изображений, которые мы взяли из Интернета. Они соответствовали 70 несвязанным между собой поисковым запросам и состояли из фотографий.
На изображении ниже — четыре набора, которые мы использовали в исследованиях. Каждый из них представлен в виде той сортировки, которую участники оценили, как самую лучшую.
Эксперимент состоял из двух частей. В первой мы фиксировали предпочтения участников — предлагали им посмотреть пары отсортированных изображений и решить, какая компоновка из двух им больше нравится. Мы просили участников выбрать те, которые «наиболее чётко организованы, обеспечивают лучший обзор и облегчают поиск изображений».
Во второй части эксперимента мы просили участников как можно быстрее найти определённые изображения, которые были отсортированы. Мы проверяли, позволяют ли предпочтения участников в отношении сортировки ускорить поиск. Кроме того, мы изучали, насколько хорошо можно предсказать время поиска, учитывая качество сортировки.
Исследуемые методы создания сортировки и подходы к оценке её качества
В наших экспериментах мы использовали различные методы для создания сортировок. Помимо самоорганизующихся карт (SOM), мы использовали самосортирующиеся карты (SSM), IsoMatch и Стохастическое вложение соседей с t-распределением.
Мы сравнили эти методы с нашими собственными методами Linear Assignment Sorting (LAS)* и Fast Linear Assignment Sorting (FLAS)**. Более подробную информацию об алгоритмах, которые используются в каждом методе, можно найти в нашей публикации, упомянутой выше.
*Примечание переводчика. Linear Assignment Sorting (LAS) — метод сортировки, основанный на применении линейного задания (linear assignment) для определения порядка элементов. Он применяется для упорядочивания набора объектов на основе их сходства или различия. В методе LAS каждому объекту присваивается определенный вес или оценка, отражающая его положение или значимость относительно других объектов. Затем используется задача линейного задания, чтобы найти оптимальный порядок объектов, максимизирующий или минимизирующий суммарную оценку.
**Fast Linear Assignment Sorting (FLAS) — оптимизированная версия Linear Assignment Sorting (LAS), которая обеспечивает более эффективную производительность. FLAS был разработан с целью ускорить процесс сортировки при использовании линейного задания. Он использует оптимизации и алгоритмические улучшения, чтобы снизить вычислительную сложность и время выполнения задачи линейного задания.
По мере возможности мы сгенерировали несколько компоновок с картинками. Для этого мы использовали различные настройки параметров при применении каждого метода. Чтобы у нас были примеры низкого качества сортировки для сравнения, мы также создали несколько плохо отсортированных компоновок. Мы обозначили их как «low Qual.» (с англ. «низкокачественные»). Случайные компоновки мы не использовали. Это привело бы к срыву эксперимента, поскольку найти изображение в них было бы слишком сложно.
Существуют методы оценки двухмерных композиций, но нет исследований, которые бы показывали, насколько хорошо они отражают воспринимаемое людьми качество сортировки. Эти методы измерения качества сортировки сравнивают расстояния между векторами признаков в многомерном пространстве с результирующими расстояниями между изображениями на двухмерной сетке. В таких случаях используют кросскорреляцию или функцию нормализованной энергии*. Но они обе ведут себя одинаково, поэтому мы выбрали последнюю. Мы предложили новый метод измерения качества сортировок под названием «Качество сохранения расстояния» (Distance Preservation Quality (DPQ)** для оценки 2D-сортировки.
*Примечание переводчика. Функция нормализованной энергии используется для оценки объектов или элементов данных на основе их энергетических характеристик. В анализе данных, энергия объекта может быть определена как мера его важности, значимости или интенсивности в контексте конкретной задачи или области. Её вычисляют на основе различных факторов, таких как амплитуда, вариация, плотность, отклонение от среднего или других свойств объекта.
**Примечание переводчика. DPQ — метрика или показатель, который используется для оценки того, насколько хорошо алгоритм или метод сохраняет расстояния между объектами или точками данных в пространстве. Она позволяет измерить степень сохранения геометрической структуры данных при преобразовании или обработке.
Воспринимаемое качество сортировки
На следующем рисунке вы увидите скриншот первой части эксперимента. Всем участникам мы показали 16 пар компоновок и предложили им решить, какой из них они отдадут предпочтение, или, возможно, они посчитают их равноценными.
Чтобы исключить потенциальное влияние бессмысленных оценок, в каждом эксперименте мы предъявляли пару сортировок, которые сильно отличались по качеству. Если участник предпочитал значительно худшую сортировку в этой паре, мы отбрасывали все его оценки сортировок. Всего мы исследовали 32 сортировки для набора цветов и по 23 сортировки для каждого из трёх наборов изображений.
В немецкой футбольной Бундеслиге есть 18 команд. Они проводят 18×17 = 306 игр в сезоне (18 умножаем на 17, потому что каждая команда не может быть парой самой себе), что соответствует 153 различным матчам.
По аналогии в нашем эксперименте было 496 возможных пар для набора цветов (32×31=992, 31, потому что каждый элемент не может быть парой самому себе. 992 делим на 2, потому что в паре участвует 2 элемента) и 253 возможные пары для каждого из трёх наборов изображений (23*22/2).
Для оценки всех сравнений мы использовали подход, аналогичный тому, который применяют в футболе, где матч может закончиться победой, поражением или ничьей. При сравнении двух сортировок предпочтительная сортировка получала один балл. Если участник оценивал обе сортировки как равные, то обе получали по полбалла. В отличие от футбола, где за сезон организаторы проводят две игры между двумя командами, разные участники оценивали каждую пару сортировок не менее 35 раз. На основе этих оценок мы определяли средний балл для каждой сортировки в паре. Эти два балла, которые в сумме равны 1 (0,5+0,5 или 0+1), описывают соотношение, в котором одну сортировку участники оценивали лучше другой. Для общего сравнения всех сортировок полученные ими оценки от всех парных сравнений суммировались.
Критерий, который определяет качество сортировки, должен в точности соответствовать оценке качества пользователями. На следующих рисунках показана корреляция между средней пользовательской оценкой сортировок (User Score) и оценками двух исследуемых методов оценки качества сортировок. Здесь E'₁ — широко используемая нормализованная функция энергии, а DPQ — предложенный нами метод «качества сохранения расстояния». Цвета символов — это различные методы создания сортировок.
1024 цвета RGB: Корреляция между оценками пользователей, оценками нормализованной функции энергии (слева) и оценками DPQ (качеством сохранения расстояния) (справа). Можно заметить, что сортировки, которые получили более высокие оценки от людей, считаются более худшими согласно оценкам нормализованной функции энергии. И наоборот, оценки качества, полученные методом DPQ (метода качества сохранения расстояния), (справа) соответствуют сортировкам с лучшими оценками пользователей
Наборы изображений: Корреляция между оценками пользователей, оценками нормализованной функции энергии (слева) и оценками DPQ (метода качества сохранения расстояния) (справа). Символы обозначают наборы изображений: дорожные знаки (⬢), кухонные принадлежности (▲) и картинки из поисковых запросов в Интернете (★)
Эти две схемы показывают, что наш новый метод измерения оценки качества сортировок DPQ хорошо коррелирует с оценками качества пользователями. Это означает, что он лучше подходит для прогнозирования того, как люди воспринимают сортировку с позиции качества.
Время поиска
Во второй части эксперимента пользователям показывали различные сортировки. В каждой из них им нужно было найти четыре случайных изображения. Как только они находили изображения, сразу же появлялась следующая сортировка. Сортировки были теми же, что и в первой части эксперимента.
Конечно, сложность поиска изображений сильно зависит от искомых изображений, так как некоторые изображения более заметные, другие — менее. Кроме того, у каждого участника свои способности к поиску. При небольшом количестве испытаний эти два аспекта могут существенно исказить результаты. Однако в общей сложности участники выполнили более 28 000 заданий на поиск нужного изображения. Это означает, что каждой сортировке соответствует более 400 поисков четырёх изображений. Такое большое количество тестов компенсировало как различную сложность поисковых заданий, так и неравные способности участников.
На схемах ниже вы видите распределение времени поиска для 23 различных сортировок с набором дорожных знаков и изображений из поисковых запросов в Интернете. Медианные значения времени поиска различных сортировок отмечены цветными маркерами. Это снова показывает более сильную корреляцию между временем поиска и оценками качества сортировок, выполненными при помощи нашего метода измерения качества сортировок DPQ по сравнению с функцией нормализованной энергии.
Корреляция медианного времени поиска с оценками качества, рассчитанные при помощи функции нормализованной энергии (слева) и нашим методом измерения качества сортировок DPQ (справа)
Мы наблюдали хорошую корреляцию между сортировками, которые обеспечивали быстрый поиск, и сортировками с высокими оценками качества. Однако для быстрого поиска было важнее, чтобы все похожие изображения были расположены максимально близко друг к другу, даже если в результате общая компоновка оценивалась несколько хуже. На следующем рисунке слева показана сортировка набора изображений, которая получила наивысшую оценку качества. А справа — сортировка, которая позволяла быстрее всего находить изображения. Слева переходы более плавные, а справа все связанные изображения расположены близко друг к другу, что приводит к резким переходам.
Сравнение методов сортировки
На последнем этапе мы хотели понять, какой из методов создания сортировки наиболее эффективен. Поскольку время выполнения сортировки в значительной степени зависит от технических возможностей, временные показатели, которые мы приводим ниже, используются только в качестве справочных значений. Поскольку метод оценки качества сортировок DPQ хорошо коррелирует с предпочтениями пользователей, мы применяли именно его для оценки корреляции между качеством алгоритмов сортировки и требуемым временем вычислений.
На следующем рисунке представлена корреляция между достигнутым качеством сортировки и временем, требуемым для вычислений, при использовании различных методов создания сортировки. Для небольших наборов данных, таких как 256 изображений кухонных принадлежностей, наш метод FLAS предлагает наилучший компромисс между качеством сортировки и временем вычислений. LAS и t-SNE могут обеспечить немного более высокое качество сортировки, но работают в 10-100 раз медленнее. Для 1024 случайных цветов RGB наши методы LAS и FLAS сгенерировали сортировки самого высокого качества.
Среднее качество сортировки (DPQ) 256 изображений кухонных принадлежностей (сверху) и 1024 цветов RGB (снизу) по сравнению со средним временем, требуемым для генерации сортировок, в разрезе различных методов создания сортировки
Ещё мы исследовали корреляцию между качеством сортировки и временем вычислений для наборов, которые содержали разное количество изображений. Для этой цели мы выбрали параметры, отмеченные ⦿ на рисунке выше. В то время как SOM, SSM, LAS и FLAS могут генерировать сортировку более высокого качества для большего количества изображений, качество сортировки при использовании методов t-SNE и IsoMatch стало хуже.
Корреляция между средним достигнутым качеством сортировки и необходимым временем для её генерации для 256 (●), 1024 (⏺) и 4096 (⬤) случайных цветов RGB в разрезе различных методов сортировки
Результаты эксперимента
В целом, мы были очень довольны результатами эксперимента, поскольку получили чёткие ответы на поставленные ранее вопросы. Результаты исследования показали, что люди значительно быстрее находят изображения, если они представлены в отсортированном виде. При анализе сортировки изображений, которую люди находят удобной и полезной, мы обнаружили, что высокое локальное сходство соседних изображений важнее, чем глобальное поддержание признаков сходства всех изображений. Более того, наше предложение использовать новый метод оценки качества сортировки изображений оказалось значительно лучше предыдущих методов для отражении качества, воспринимаемого человеком.
Стало ясно, что предложенные нами методы создания сортировки LAS и FLAS могут производить высококачественную сортировку, а FLAS ещё и очень эффективен, если учитывать фактор времени при генерации сортировок. Кроме того, наши методы предлагают различные варианты влияния на сортировку, например, фиксированное расположение определенных изображений или возможность использовать не прямоугольную компоновку. Метод FLAS работает настолько быстро, что становится возможным визуально исследовать миллионы изображений. Navigu.net — пример такого инструмента визуального исследования изображений. Если вы дочитали до этого момента и всё ещё заинтересованы, приглашаем вас принять участие в эксперименте: experiment.visual-computing.com, чтобы достичь ещё более точных результатов.
В нашем Телеграм-канале UX Teddy публикуем так же переводы практических статей из блога UX Movement — подписывайтесь!