C++缓存设计建议

Question

我有一个具有多种图像类型（RGB、灰色...）的 C++ 应用程序，每种类型都有旋转或缩放等属性。每个图像类型都是通过其他类型的一些计算生成的。例如，旋转的 GrayImage 是通过旋转 GrayImage 生成的，而 GrayImage 又是通过“灰化”RGBImage 生成的。

我想设计一个带有方法 GetX(...) 的缓存类，用于缓存各种图像（可能还有计算路径中的所有图像）。 该类还知道如何生成每个图像，以防它不在缓存中。

该类必须满足一些约束：

1. 由于我们正在处理不同类型和表示形式（RGB、灰度等）的图像，因此缓存必须返回一个具体类，以便调用代码能够在不进行某种转换的情况下使用它。因此，缓存机制必须保存包含具体类型的不同缓存结构。 （如果我错了请纠正我）

   map<...,RGBImage> 
   地图<...,GrayImage> 
   

   例如。

2. 缓存必须能够灵活地适应图像计算的变化。只要代码的更改不是太大，就可以接受。

我的当前版本为每种图像类型附加了一个 Key 结构。 有GrayKey、RGBKey等等。各种键都包含缩放和旋转等属性，并且可以具有特定于图像的属性（例如 GrayKey 的 toGrayConvertingMethod）。 缓存保存以下形式的地图：

    map <XKey,XImage>

GetX(...) 方法接收 Key 结构作为请求旋转灰度图像的参数。 不过，这种实现迫使缓存应用大量逻辑来计算图像。它必须检查 GrayKey 是否请求旋转图像并采取相应措施。 我想以一种更优雅的方式“编码”这种图像计算关系，但似乎找不到。

有什么建议吗？

多谢。

Answer 1

也许你可以使用 Boost.MultiIndex 做一些事情容器？它将允许您创建一个类型来存储图像数据及其操作方式的详细信息，然后根据您想要的键组合查找值。如果您以前没有使用过它，它可能看起来有点令人畏惧，但我在下面附上了一个示例。

显然，我的示例仅处理缓存机制的存储/检索部分，如果您将其组合在一起，如果查找失败，可以生成图像，它应该做您想做的一切。扩展它也很容易......需要查找额外的参数吗？您只需向 ImageCache typedef 添加另一个索引即可。

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/tag.hpp>

#include <boost/shared_array.hpp>

#include <algorithm>
#include <iostream>
#include <utility>

// A cache item, stores the image data, and any values we need to 
// index on.
struct ImageCacheItem
{
    enum RgbMode { RGB_MODE_COLOUR, RGB_MODE_GREYSCALE };

    // Im not sure how much copying goes on in the container,
    // so using a smart pointer to prevent copying large amounts
    // of data.
    boost::shared_array<char> imageBuffer;

    double  rotation;
    double  scale;
    RgbMode rgbMode;

    ImageCacheItem(double r, double s)
    : rotation(r), scale(s)
    {
    }
};

// These are "tag" structures, they are used as part of the 
// multi_index_container as a way to distinguish between indicies.
struct ByRotation {};
struct ByScale {};
struct ByRgb {};
struct ByRotationScale {};

// Typedef of the container itself.
typedef boost::multi_index_container<
    ImageCacheItem, // The data type for the container.  
                    // Note there is no "key" type, as the key values 
                    // are extracted from the data items theselves.
    boost::multi_index::indexed_by<

        // Define an index for the rotation value
        boost::multi_index::ordered_non_unique<
            boost::multi_index::tag<ByRotation>,
            BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, double, rotation)
        >,

        // Define an index for the scale value
        boost::multi_index::ordered_non_unique<
            boost::multi_index::tag<ByScale>,
            BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, double, scale)
        >,

        // Define an index for the rgb value
        boost::multi_index::hashed_non_unique<
            boost::multi_index::tag<ByRgb>,
            BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, ImageCacheItem::RgbMode, rgbMode)
        >,

        // Define an index by rotation + scale
        boost::multi_index::hashed_unique<
            boost::multi_index::tag<ByRotationScale>,
            boost::multi_index::composite_key<
                ImageCacheItem,
                BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, double, rotation),
                BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, double, scale)
            >
        >

    >
> ImageCache;

// Utility typedefs, you'll want these to shorten the iterator
// data types when you're looking things up (see main).
typedef ImageCache::index<ByRotation>::type      ImageCacheByRotation;
typedef ImageCache::index<ByScale>::type         ImageCacheByScale;
typedef ImageCache::index<ByRgb>::type           ImageCacheByRgb;
typedef ImageCache::index<ByRotationScale>::type ImageCacheByRotationScale;

int main()
{
    // Create the cache and add time "images" to it.
    ImageCache cache;
    cache.insert(ImageCacheItem(10, 10));
    cache.insert(ImageCacheItem(10, 20));
    cache.insert(ImageCacheItem(20, 20));

    // look up the images with scale of 20.
    typedef ImageCacheByScale::iterator ScaleIter;

    std::pair<ScaleIter, ScaleIter> scaleResult = cache.get<ByScale>().equal_range(20);
    std::cout << "Found " << std::distance(scaleResult.first, scaleResult.second) << " Results" << std::endl;

    // look up the image with rotation = 10 && scale = 20.
    ImageCacheByRotationScale::iterator rsResult = cache.get<ByRotationScale>().find(boost::make_tuple(10, 20));
    std::cout << "Found " << (rsResult != cache.get<ByRotationScale>().end() ? 1 : 0) << " Results" << std::endl;

    return 0;
}

编辑：它是一个很大的...

我尝试扩展上面的示例，以在缓存中查找与您搜索的内容最接近的图像，但是带有偏差，因此如果您想要旋转 45，比例为 10，如果没有找到精确匹配，则将倾向于其中一个属性相同而另一个属性为 0 的结果（即比例为 10，但是0旋转，所以你需要做的就是旋转）。

该代码被注释以解释其作用，但基本上，它使用模板递归按顺序搜索索引，一旦索引找到一些匹配项，它就会尝试按相关性顺序对它们进行排序，并返回最佳匹配项。要添加另一个属性，您需要执行以下操作：

1. 将属性添加到 ImageCacheItem
2. 将属性的比较添加到 ImageCacheSimilarity
3. （可选） 将与其匹配的另一个索引添加到ImageCache typedef

它可能不是最佳解决方案，但我认为它涵盖了您在评论中提到的用例。

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/tag.hpp>

#include <boost/mpl/list.hpp>
#include <boost/optional.hpp>
#include <boost/ref.hpp>
#include <boost/shared_array.hpp>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
#include <typeinfo>

// A cache item, stores the image data, and any values we need to 
// index on.
struct ImageCacheItem
{
    enum RgbMode { RGB_MODE_COLOUR, RGB_MODE_GREYSCALE };

    // Im not sure how much copying goes on in the container,
    // so using a smart pointer to prevent copying large amounts
    // of data.
    boost::shared_array<char> imageBuffer;

    double  rotation;
    double  scale;
    RgbMode rgbMode;

    ImageCacheItem(double r, double s)
    : rotation(r), scale(s)
    {
    }
};

// Calculates the similarity between two ImageCacheItem objects.
int ImageCacheSimilarity(const ImageCacheItem& item, const ImageCacheItem& target)
{
    const double EPSILON = 0.0000001;

    int score = 0;

    // 2 points for an exact match
    // 1 point if the value is 0 (e.g. not rotated, so can be used as a starting point)
    // -1 point otherwise
    score += (std::fabs(item.rotation - target.rotation) < EPSILON) 
        ? 2 
        : ((std::fabs(item.rotation) < EPSILON) ? 1 : -1);

    score += (std::fabs(item.scale - target.scale) < EPSILON) 
        ? 2 
        : ((std::fabs(item.scale) < EPSILON) ? 1 : -1);

    score += (item.rgbMode == target.rgbMode) ? 2 : 0;

    return score;
}

// Orders ImageCacheItem objects based on their similarity to a target value.
struct ImageCacheCmp
{
    const ImageCacheItem& target;

    ImageCacheCmp(const ImageCacheItem& t)
    : target(t)
    {
    }

    bool operator()(const ImageCacheItem& a, const ImageCacheItem& b)
    {
        return (ImageCacheSimilarity(a, target) > ImageCacheSimilarity(b, target));
    }
};

// These are "tag" structures, they are used as part of the 
// multi_index_container as a way to distinguish between indicies.
struct ByRotation {};
struct ByScale {};
struct ByRgb {};
struct ByRotationScale {};

// Typedef of the container itself.
typedef boost::multi_index_container<
    ImageCacheItem, // The data type for the container.  
                    // Note there is no "key" type, as the key values 
                    // are extracted from the data items theselves.
    boost::multi_index::indexed_by<

        // The order of indicies here will affect performance, put the 
        // ones that match against the most fields first.  Its not required
        // to make it work, but it will reduce the number of matches to 
        // compare against later on.

        // Define an index by rotation + scale
        boost::multi_index::hashed_unique<
            boost::multi_index::tag<ByRotationScale>,
            boost::multi_index::composite_key<
                ImageCacheItem,
                BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, double, rotation),
                BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, double, scale)
            >
        >,

        // Define an index for the rotation value
        boost::multi_index::ordered_non_unique<
            boost::multi_index::tag<ByRotation>,
            BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, double, rotation)
        >,

        // Define an index for the scale value
        boost::multi_index::ordered_non_unique<
            boost::multi_index::tag<ByScale>,
            BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, double, scale)
        >,

        // Define an index for the rgb value
        boost::multi_index::hashed_non_unique<
            boost::multi_index::tag<ByRgb>,
            BOOST_MULTI_INDEX_MEMBER(ImageCacheItem, ImageCacheItem::RgbMode, rgbMode)
        >
    >
> ImageCache;

// Type of the vector used when collecting index results.  It stores
// references to the values in the cache to minimise copying.
typedef std::vector<boost::reference_wrapper<const ImageCacheItem> > ImageCacheResults;

// Utility class for overload resolution
template <int I>
struct Int2Type
{
    enum { value = I };
};

void FindMatches(
    const ImageCacheItem& item, 
    const ImageCache& cache, 
    ImageCacheResults& results,
    const Int2Type<boost::mpl::size<ImageCache::index_type_list>::type::value>&)
{
    // End of template recursion
}

template <int I>
void FindMatches(
    const ImageCacheItem& item, 
    const ImageCache& cache, 
    ImageCacheResults& results,
    const Int2Type<I>&)
{
    // Get the index being searched
    typedef typename ImageCache::nth_index<I>::type Index;

    // This type knows how to extract the relevant bits of ImageCacheItem
    // for this particular index.
    typename Index::key_from_value keyExtractor;

    // Look for matches in the index.
    std::pair<typename Index::const_iterator, typename Index::const_iterator> iter = 
        cache.get<I>().equal_range(keyExtractor(item));

    // If we found any results, add them to 'results', otherwise
    // continue to the next index.
    if (iter.first != iter.second)
    {
        results.reserve(std::distance(iter.first, iter.second));

        for ( ; iter.first != iter.second; ++iter.first)
        {
            results.push_back(boost::cref(*iter.first));
        }
    }
    else
    {
        FindMatches(item, cache, results, Int2Type<I + 1>());
    }
}

boost::optional<ImageCacheItem> FindClosestImage(const ImageCacheItem& item, const ImageCache& cache)
{
    // Find exact/partial matches according to the indicies.
    ImageCacheResults results;
    FindMatches(item, cache, results, Int2Type<0>());

    // If no matches were found, return an empty value
    if (results.empty())
    {
        return boost::optional<ImageCacheItem>();
    }

    // We got this far, so we must have some candiates, the problem is
    // we dont know which is the best match, so here we sort the results
    // based on proximity to the "item".  However, we are only interested
    // in the best match, so do a partial_sort.
    std::partial_sort(results.begin(), results.begin() + 1, results.end(), ImageCacheCmp(item));

    return results.front().get();
}

int main()
{
    // Create the cache and add some "images" to it.
    ImageCache cache;
    cache.insert(ImageCacheItem(10, 20));
    cache.insert(ImageCacheItem(10, 10));
    cache.insert(ImageCacheItem(10, 2));
    cache.insert(ImageCacheItem(20, 20));
    cache.insert(ImageCacheItem(30, 20));
    cache.insert(ImageCacheItem(30, 0));

    // Look for an image similar to rotation = 30 && scale = 2.
    boost::optional<ImageCacheItem> result = FindClosestImage(ImageCacheItem(30, 2), cache);

    // Have to check if result is value before usage, it would be empty 
    // if not match is found.
    if (result)
    {
        std::cout << "Found (" << result->rotation 
                  << ", " << result->scale << ")" 
                  << std::endl;
    }
    else
    {
        std::cout << "No Results" << std::endl;
    }

    return 0;
}

Answer 2

您是否考虑过使用瘦访问器来灰化和旋转彩色图像？ Adobe 的通用图像库（现在是 boost 的一部分）以这种方式使用一些聪明的迭代器

Answer 3

您是否考虑过使用 STL 容器？使用地图或集来存储对图像的引用。可以快速查找您是否已经创建了图像。