Каков наилучший способ получить хэш QPixmap? - PullRequest
5 голосов
/ 05 марта 2009

Я занимаюсь разработкой графического приложения с использованием Qt 4.5 и помещаю изображения в QPixmapCache, я хотел оптимизировать это так, чтобы, если пользователь вставляет изображение, которое уже находится в кэше, он использовал его.

Прямо сейчас у каждого изображения есть уникальный идентификатор, который помогает оптимизировать себя на событиях рисования. Однако я понимаю, что, если бы я мог вычислить хэш изображения, я мог бы найти кэш, чтобы увидеть, существует ли он уже, и использовать его (это, конечно, помогло бы больше для дублированных объектов).

Моя проблема в том, что если его большой QPixmap будет вычислять хеш-значения, это замедлит процесс или будет более быстрый путь?

Ответы [ 4 ]

3 голосов
/ 22 августа 2012

На тот случай, если кто-нибудь столкнется с этой проблемой (и не испытывает особого опыта хеширования, в частности чего-то вроде изображения), вот ОЧЕНЬ простое решение, которое я использовал для хеширования QPixmaps и ввода их в таблицу поиска для последующего сравнения :

qint32 HashClass::hashPixmap(QPixmap pix)
{
    QImage image = pix.toImage();
    qint32 hash = 0;

    for(int y = 0; y < image.height(); y++)
    {
        for(int x = 0; x < image.width(); x++)
        {
            QRgb pixel = image.pixel(x,y);

            hash += pixel;
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }
    }

    return hash;
}

Вот сама функция хеширования (вы можете использовать ее в qint64, если хотите меньше коллизий). Как вы можете видеть, я преобразовываю растровое изображение в QImage, просто прохожу его размеры и выполняю очень простой одноразовый хэш для каждого пикселя и возвращаю конечный результат. Есть много способов улучшить эту реализацию (см. Другие ответы на этот вопрос), но это основная суть того, что необходимо сделать.

ОП упоминал, как он будет использовать эту функцию хеширования, чтобы затем построить таблицу поиска для последующего сравнения изображений. Это потребует очень простой функции инициализации поиска - что-то вроде этого:

void HashClass::initializeImageLookupTable()
{
    imageTable.insert(hashPixmap(QPixmap(":/Image_Path1.png")), "ImageKey1");
    imageTable.insert(hashPixmap(QPixmap(":/Image_Path2.png")), "ImageKey2");
    imageTable.insert(hashPixmap(QPixmap(":/Image_Path3.png")), "ImageKey2");
// Etc...
}

Я использую здесь QMap с именем imageTable, который должен быть объявлен в классе как таковой:

QMap<qint32, QString> imageTable;

Затем, наконец, когда вы хотите сравнить изображение с изображениями в вашей справочной таблице (то есть: «какое изображение, из известных мне изображений, может быть это конкретное изображение?»), Вы просто называете хеширующая функция на изображении (которая, я предполагаю, также будет QPixmap) и возвращаемое значение QString позволит вам понять это. Примерно так будет работать:

void HashClass::compareImage(const QPixmap& pixmap)
{
    QString value = imageTable[hashPixmap(pixmap)];
    // Do whatever needs to be done with the QString value and pixmap after this point.
}

Вот и все. Я надеюсь, что это кому-то поможет - это сэкономило бы мне некоторое время, хотя я был счастлив иметь опыт выяснения этого.

3 голосов
/ 05 марта 2009

Пара комментариев по этому поводу:

  1. Если вы собираетесь генерировать ключ хеша / кэша для растрового изображения, вы можете пропустить QPixmapCache и напрямую использовать QCache . Это устранит некоторые накладные расходы на использование QStrings в качестве ключей (если только вы не хотите использовать путь к файлу для поиска элементов)

  2. Начиная с Qt4.4, с QPixmap связано значение хеша (см. QPixmap :: cacheKey () ). В документации утверждается: «Отдельные объекты QPixmap могут иметь один и тот же ключ кэша, только если они ссылаются на одно и то же содержимое». Однако, поскольку Qt использует копирование совместно используемых данных, это может применяться только к скопированным растровым изображениям, а не к двум отдельным растровым изображениям, загруженным из одного и того же изображения. Немного тестирования покажет вам, работает ли оно, и если да, то позволит легко получить хеш-значение.

  3. Если вы действительно хотите создать хороший, довольно быстрый кэш с удалением дубликатов, вам может понадобиться посмотреть собственную структуру данных , которая сортирует по размерам, глубине цвета, типам изображений, и тому подобное. Тогда вам нужно будет только хэшировать фактические данные изображения после того, как вы найдете изображение того же типа с теми же размерами, битовой глубиной и т. Д. Конечно, если ваши пользователи обычно открывают много изображений с такими же вещами, это ничем не помогаю.

  4. Производительность: Не забывайте о бенчмаркинге, добавленном Qt в 4.5, который позволит вам сравнить ваши различные идеи хеширования и посмотреть, какой из них работает быстрее всего. Я еще не проверил это, но выглядит довольно аккуратно.

1 голос
/ 05 марта 2009

Я предполагаю, что вы говорите о том, чтобы на самом деле вычислять хеш по данным изображения, а не получать уникальный идентификатор, сгенерированный QT.
В зависимости от ваших изображений, вам, вероятно, не нужно просматривать все изображение, чтобы вычислить хеш. Может быть, только читать первые 10 пикселей? первая строка сканирования?
Может быть, псевдослучайный выбор пикселей из всего изображения? (с известным семенем, чтобы вы могли повторить последовательность) Не забудьте также добавить размер изображения в хеш.

1 голос
/ 05 марта 2009

Хеш-вычисления должны быть довольно быстрыми (где-то выше 100 МБ / с, если не используется дисковый ввод-вывод) в зависимости от того, какой алгоритм вы используете. Перед хэшированием вы также можете сделать несколько быстрых тестов, чтобы отсортировать потенциальных кандидатов - например, изображения должны иметь одинаковую ширину и высоту, иначе сравнивать их значения хешей бесполезно.

Конечно, вы должны также сохранить значения хеш-функции для вставленных изображений, чтобы вам нужно было только вычислить хэш для новых изображений и не нужно снова вычислять его для кэшированных изображений.

Если изображения достаточно разные, возможно, будет достаточно не хэшировать все изображение, а уменьшенный эскиз или часть изображения (например, первые и последние 10 строк), это будет быстрее, но приведет к большему количеству изображений. столкновения.

...