算法来检测两幅图像重叠行 [英] Algorithm to detect overlapping rows of two images

问题描述

让我们说我有2图像A和B如下。

Let's say I have 2 images A and B as below.

注意，A的底部与B的顶部重叠ñ行像素，记为两个红色长方形。 A和B具有相同的列数，但是的可能的有不同的行数。

Notice that the bottom of A overlaps with the top of B for n rows of pixels, denoted by the two red rectangles. A and B have the same number of columns but might have different number of rows.

两个问题：

• 由于A和B，如何确定 N 高效？
• 如果B是一种方式，它的像素的30％-50％是完全取代以某种方式改变（例如，想象中的左上方显示＃的票/答案/意见被替换为广告标志）。如何确定 N ？

• Given A and B, how to determine n efficiently?
• If B is somehow changed in a way that 30%-50% of its pixels are completely replaced (for example, imagine the top left area showing # of votes/answers/views is replaced with an ad banner). How to determine n?

如果任何人都可以指向一个算法或更好，但在任何语言的实现（preferred C / C ++，C＃，Java和JavaScript），它是非常AP preciated。

If anyone can point to an algorithm or better yet, an implementation in any language (preferred C/C++, C#, Java and JavaScript), it is much appreciated.

推荐答案

FFT的解决方案可能是更复杂的比你所期望的。 对于一个一般的问题，这可能是唯一可靠的方法。

The FFT solution might be more complex than you were hoping for. For a general problem, that might be the only robust way.

对于一个简单的解决方案，你需要开始作出假设。 例如，你能保证图像的列排队（除非所提到的变化）？这允许你去减少@nm建议的路径

For a simple solution, you need to start making assumptions. For example, can you guarantee that the columns of the images line up (barring the noted changes)? This allows you to go down the path suggested by @n.m.

您可以剪切图像成直条，并考虑行匹配，如果带了足够比例搭配？

Can you cut the image into vertical strips, and consider a row matches if a sufficient proportion of the strips match?

[这可以重做使用了几道次差列偏移，如果我们需要稳健的。]

[ This could be redone to use a few passes with difference column offsets if we need to be robust to that.]

这给了像：

class Image
{
public:
    virtual ~Image() {}
    typedef int Pixel;
    virtual Pixel* getRow(int rowId) const = 0;
    virtual int getWidth() const = 0;
    virtual int getHeight() const = 0;
};

class Analyser
{
    Analyser(const Image& a, const Image& b)
        : a_(a), b_(b) {}
    typedef Image::Pixel* Section;
    static const int numStrips = 16;
    struct StripId
    {
        StripId(int r = 0, int c = 0)
            : row_(r), strip_(c)
        {}
        int row_;
        int strip_;
    };
    typedef std::unordered_map<unsigned, StripId> StripTable;
    int numberOfOverlappingRows()
    {
        int commonWidth = std::min(a_.getWidth(), b_.getWidth());
        int stripWidth = commonWidth/numStrips;
        StripTable aHash;
        createStripTable(aHash, a_, stripWidth);
        StripTable bHash;
        createStripTable(bHash, b_, stripWidth);
        // This is the position that the bottom row of A appears in B.
        int bottomOfA = 0;
        bool canFindBottomOfAInB = canFindLine(a_.getRow(a_.getHeight() - 1), bHash, stripWidth,  bottomOfA);
        int topOfB= 0;
        bool canFindTopOfBInA =  canFindLine(b_.getRow(0), aHash, stripWidth, topOfB);
        int topOFBfromBottomOfA = a_.getHeight() - topOfB;
        // Expect topOFBfromBottomOfA == bottomOfA
        return bottomOfA;
    }
    bool canFindLine(Image::Pixel* source, StripTable& target, int stripWidth, int& matchingRow)
    {
        Image::Pixel* strip = source;
        std::map<int, int> matchedRows;
        for(int index = 0; index < stripWidth; ++index)
        {
            Image::Pixel hashValue = getHashOfStrip(strip,stripWidth);      
            bool match =  target.count(hashValue) > 0;
            if (match)
            {
                ++matchedRows[target[hashValue].row_];
            }
            strip += stripWidth;
        }
        // Can set a threshold requiring more matches than 0
        if (matchedRows.size() == 0)
            return false;
        // FIXME return the most matched row.
        matchingRow = matchedRows.begin()->first;
        return true; 
    }
    Image::Pixel* getStrip(const Image& im, int row, int stripId, int stripWidth)
    {
        return im.getRow(row) + stripId * stripWidth;
    }
    static Image::Pixel getHashOfStrip(Image::Pixel* strip, unsigned width)
    {
        Image::Pixel hashValue = 0;
        for(unsigned col = 0; col < width; ++col)
        {
            hashValue |= *(strip + col);
        }
    }
    void createStripTable(StripTable& hash, const Image& image, int stripWidth)
    {
        for(int row = 0; row < image.getHeight(); ++row)
        {
            for(int index = 0; index < stripWidth; ++index)
            {
                // Warning: Not this simple!
                // If images are sourced from lossy intermediate and hence pixels not _exactly_ the same, need some kind of fuzzy equality here.
                // Details are going to depend on the image format etc, but this is the gist.
                Image::Pixel* strip = getStrip(image, row, index, stripWidth);
                Image::Pixel hashValue = getHashOfStrip(strip,stripWidth);      
                hash[hashValue] = StripId(row, index);
            }
        }
    }

    const Image& a_;
    const Image& b_;

};

这篇关于算法来检测两幅图像重叠行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！