image - 检测两个图像的重叠行的算法

Question

假设我有 2 个图像 A 和 B，如下所示。

在此处输入图像描述

请注意，对于像素行，A 的底部与 B 的顶部重叠n，由两个红色矩形表示。A 和 B 具有相同的列数，但可能具有不同的行数。

两个问题：

给定A和B，如何n有效地确定？
如果 B 以某种方式发生更改，使其 30%-50% 的像素被完全替换（例如，想象显示投票/答案/视图数的左上角区域被广告横幅替换）。如何确定n？

如果有人可以指出一种算法或更好的任何语言（首选 C/C++、C#、Java 和 JavaScript）的实现，我们将不胜感激。

score 8 · Accepted Answer

如果我理解正确，您可能想查看两幅图像灰度版本的标准化互相关。如果您有大图像或大重叠区域，则使用图像（或重叠区域）的 FFT 在频域中最有效地完成此操作，称为相位相关。

在您的情况下，我将采取的基本步骤如下：

提取第一张图像的下半部分和第二张图像的上半部分。
将两个图像块都转换为灰度。
对每个图像块执行 FFT（这里有一些与窗口和填充有关的细节）。
计算两个 FFT 的复共轭（与空间域中的相关性相同）。
对结果进行逆 FFT。
找到上面的峰值以获得最佳对齐两个图像的 XY 偏移。

找到顶部和底部图像块之间的相对偏移后，您可以根据需要轻松计算n。

如果您想进行实验而不必从头开始编写上述代码，OpenCV 有许多模板匹配功能，您可以轻松尝试。有关详细信息，请参见此处。

如果任一图像的一部分已被更改 - 例如通过横幅广告 - 上述过程仍然给出最佳匹配，并且您在步骤 6 中找到的峰值幅度表明匹配“置信度” - 因此您可以获得大致了解这两个领域的相似程度。

score 3 · Accepted Answer

我在 ImageMagick 上做了一些小游戏。这是我所做的动画，解释和代码如下。

在此处输入图像描述

首先，我抓取了几个 StackOverflow 页面，使用webkit2png、调用它们a.png和b.png.

然后我从左上角裁剪了一个矩形b.png和一个宽度相同的列，但全高a.png

这给了我这个：

在此处输入图像描述

还有这个

在此处输入图像描述

我现在将第二页的较小矩形覆盖到第一页的条带底部。然后我通过从另一个减去一个来计算两个图像之间的差异，并注意当差异为零时，图片必须相同，并且输出图像将是黑色的，所以我找到了它们重叠的点。

这是代码：

#!/bin/bash
# Grab page 2 as "A" and page 3 as "B"
# webkit2png -F -o A http://stackoverflow.com/questions?page=2&sort=newest
# webkit2png -F -o B http://stackoverflow.com/questions?page=3&sort=newest

BLOBH=256  # blob height
BLOBW=256  # blob width

# Get height of x.png
XHEIGHT=$(identify -format "%h" x.png)

# Crop a column 256 pixels out of a.png that doesn't contain adverts or junk, into x.png
convert a.png -crop ${BLOBW}x+0+0 x.png

# Crop a rectangle 256x256 pixels out of top left corner of b.png, into y.png
convert b.png -crop ${BLOBW}x${BLOBH}+0+0 y.png

# Now slide y.png up across x.png, starting at the bottom of x.png
# ... differencing the two images as we go
# ... stop when the difference is nothing, i.e. they are the same and difference is black image
lines=0
while :; do
   OFFSET=$((XHEIGHT-BLOBH-1-lines))
   if [ $OFFSET -lt 0 ]; then exit; fi
   FN=$(printf "out-%04d.png" $lines)
   diff=$(convert x.png -crop ${BLOBW}x${BLOBH}+0+${OFFSET} +repage \
           y.png \
           -fuzz 5% -compose difference -composite +write $FN \
           \( +clone -evaluate set 0 \) -metric AE -compare -format "%[distortion]" info:)
   echo $diff:$lines
   ((lines++))
done
n=$((BLOBH+lines))

score 2 · Accepted Answer

FFT 解决方案可能比您希望的要复杂。对于一般问题，这可能是唯一可靠的方法。

对于一个简单的解决方案，您需要开始做出假设。例如，你能保证图像的列是对齐的（除非注意到的变化）？这使您可以沿着@nm 建议的路径前进

你能把图像切成垂直条，如果有足够比例的条匹配，则考虑一行匹配？

[如果我们需要对此保持稳健，可以重做一些具有不同列偏移的通道。]

这给出了类似的东西：

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_;

};

score 0 · Accepted Answer

如果行完全匹配，则对两个图像中的行进行排序并合并。你的副本就在那里。然后转到原始图像，找到 A 中最长的连续重复条纹，使得 B 中的相应行也是连续的。或者只是查看相应图像的顶部和底部附近。

如果有横幅广告，首先想到的是将图像分成几个垂直条，然后分别对每对条进行处理。

score 0 · Accepted Answer

这样的事情可能会有所帮助：

首先，从下向上遍历图像A，搜索其中有重要信息的一行。例如，可以通过计算跨行的总颜色偏移来计算“信息”。比如说，两个相邻像素的颜色为 #ffffff 和 #ff0000 - 将 2.0 添加到总数中。准备好一系列阈值，并锁定达到该阈值的第一行。该系列可以是“10.0, 0.1*row length, 0.15*row length, ...”到一个合理的限制。然后，从发现的最上层向下遍历这个数组，取对应的行并从倒过来在 B 中搜索它的匹配项。如果找到，并且阈值足够大，则取数组中的下一个并计算其匹配的位置，并进行比较。如果成功，您已经锁定了 B 相对于 A 的正确偏移量，它等于height_of_A - first_row_index + first_row_match_index. 如果失败继续搜索下一行。如果所有匹配都失败，则从 B 的第一行开始搜索 A 的最后一行，直到从 A 底部找到的第一行的偏移量。如果再次失败，则答案为 0。当然，如果使用JPEG 图像使用阈值匹配，因为 A 和 B 中的像素可能不精确，可能对不匹配的像素也有容差。

image - 检测两个图像的重叠行的算法

5 回答 5

Related

Reference