C++ Cache Design Advice

Question

I have a c++ application with several image types(RGB, Gray...) and every type has properties like Rotation or Scale. Every image type is generated via some computation from the other types. For example, A rotated GrayImage is generated by rotating a GrayImage which in turn is generated by "graying" an RGBImage.

I would like to design a cache class with methods GetX(...) that caches the various images (and possibly all images in the computation path). This class would also know how to generate each image in case it is not in the cache.

The class must fulfill some constraints:

Since we are dealing with images of different types and representations(RGB, GrayScale etc.) the cache must return a concrete class for the calling code to be able to use it without some sort of casting. Thus, the cache mechanism must hold different cache structures containing concrete types. (fix me if I'm wrong here)
```
map<...,RGBImage> 
map<...,GrayImage> 
```
for example.
The cache must be flexible to changes in computation of images. Changes to code are acceptable as long as they are not too large.

The current version I have attaches a Key struct to each image type. There's GrayKey, RGBKey and so on. the various keys hold properties like Scale and Rotation and can have properties specific to the image (e.g. toGrayConvertingMethod for GrayKey). The cache holds maps of the form:

    map <XKey,XImage>

GetX(...) method receives a Key struct as parameter requesting a Rotated GrayImage for example. Though, this implementation forces the cache to apply lots of logic for computations of images. It must check whether GrayKey requests a rotated image or not and act accordingly. I would like to "encode" this image computation relationship in a more elegant way but can't seem to find one.

Any suggestions?

Thanks a lot.

I have two quick suggestions: firstly, keep your image computation logic decoupled from your cache implementation. That way you can change either side as your needs change. Secondly, have you looked at one-way hashing schemes for the hash key yet? You could compute your hashes based on the contents of the images and their properties. — Brian Kelly, Jun 17 '11 at 19:55
Who voted to close this as "Not a real question"? Are you drunk? — Ed S., Jun 18 '11 at 00:30

Node · Answer 1 · 2011-06-19T16:32:00.177

Perhaps you could do something using the Boost.MultiIndex container? It would allow you to make a type that stores the image data, and details of how it was manipulated, then lookup values based on whatever combination of keys you want. If you haven't used it before, it could seem a bit daunting, but i've attached an example below.

Obviously, my example only handles the storage/retrieval part of the caching mechanism, if you stick this together which something that can generate the images if the lookups fail, it should do everything you want. Extending it is easy too...need to lookup on extra parameters? you just need to add another index to the 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;
}

Edit: its a big one...

I have had a stab at extending the above example to find the image in the cache that is closest to what you search for, but with a bias, so if you want rotation of 45, and a scale of 10, if no exact match is found, it would favour a result with one of the properties the same, and the other as 0 (i.e. a scale of 10, but 0 rotation, so all you need to do is rotate).

The code is commented to explain what its doing, but basically, it uses template recursion to search through the indices in order, as soon as an index finds some matches, it attempts to sort them in order of relevance, and returns the best match. To add another property, you would need to do the following:

Add the property to ImageCacheItem
Add comparison for the property to ImageCacheSimilarity
(optional) Add another index that matches against it to the ImageCache typedef

It may not be the most optimal solution, but I think it covers the use case you mentioned in your comment.

#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;
}

Thanks for the elaborate example. What do you suggest I do if some images have specific properties? say GrayImage has grayConvertMethod which RGBImage hasn't got. Also, to figure out which image I need to compute I would have to test each parameter separately which complicates code. (e.g. if rotation is nonzero I would look for a zero rotation with same scale image to generate the rotated one from) I was hoping for some elegant solution. Perhaps a Key inheritance tree to "encode" the image generation hierarchy with the possibility to "reduce" to the predecessor Key. — leo, Jun 18 '11 at 18:06

score 1 · Answer 2 · answered Jun 17 '11 at 19:54

1

Have you considered using thin accessors to gray and rotate your color image? Adobe' generic image library (now part of boost) uses some clever iterators that way

answered Jun 17 '11 at 19:54

totowtwo

2,101
1
14
21

I need to actually store the images themselves rather than just views because the cache should own the pixels themselves. I also believe adobe's library doesn't account for rotation, scaling etc. Which is what I need to remember for every image. The library could generate images for me but can it say "this image is rotated by 30 degrees"? – leo Jun 17 '11 at 22:29

score 0 · Answer 3 · edited May 23 '17 at 11:57

0

Did you consider using an STL container? Use a map or set to store references to the images. The have fast lookup to see if you've already created an image.

edited May 23 '17 at 11:57

Community

1
1

answered Jun 17 '11 at 19:41

Jay

13,803
4
42
69

I did mention using a map in my original message. This only solves part of the problem. The main issue is separating image computation logic from the cache logic (or at least making them easy to change) and being able to say "this image has been rotated X degrees compared to the original" – leo Jun 17 '11 at 22:33

C++ Cache Design Advice

3 Answers3

Linked