logo标签列表

检测两幅图像重叠行的算法

imagealgorithmimage-processing
5

假设我有以下两张图片A和B。

enter image description here

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

两个问题：

  • 给定A和B，如何高效地确定n？
  • 如果以某种方式更改B，使其30％-50％的像素完全被替换（例如，想象左上角显示的投票/答案/查看次数被广告横幅替换），如何确定n？

如果有人能指出任何语言（首选C / C ++，C＃，Java和JavaScript）中的算法或更好的实现，将不胜感激。

你是否已经预设了A的底部等于B的顶部？如果没有，那么查找匹配区域的复杂度为O(WHH)。 - Vesper
我不确定是否理解您的问题。关于第一个问题，A底部恰好与B顶部对齐，尽管匹配行数（或像素行）未知（需要确定）。就第二个问题而言，所谓匹配的B顶部可能已经被更改了30%至50%。 - Buu
对于仍在2021年寻找此问题的人，我几年前也遇到过这个问题，并且只是坐下来使用opencv和scikit-image一次性解决了这个问题（希望如此）。我已经在https://dev59.com/SbDla4cB1Zd3GeqP50sw#67328088上发布了全面的答案。 - Mike 'Pomax' Kamermans
5个回答
9
如果我理解正确的话，您可能想查看两个图像的灰度版本的归一化交叉相关。对于具有大图像或大重叠区域的情况，在频域使用图像（或重叠区域）的FFT最有效，并称为相位相关。
在您的情况下，我会采取以下基本步骤：
  1. 提取第一个图像的底部一半和第二个图像的顶部一半。
  2. 将两个图像补丁转换为灰度。
  3. 对每个图像补丁执行FFT（这里涉及到窗口和填充的一些细节）。
  4. 计算两个FFT的复共轭（与空间域中的相关性相同）。
  5. 对结果进行反FFT。
  6. 找到上述峰值以获得最佳对齐两个图像的XY偏移量。
找到顶部和底部图像补丁之间的相对偏移后，您可以轻松地按照所需计算n。
如果你想进行实验而不必从头开始编写代码，OpenCV有许多模板匹配函数可供尝试。详情请见此处。 如果图像的某部分已经发生了变化 - 例如横幅广告 - 上述过程仍然可以给出最佳匹配，并且在第6步中找到的峰值大小可以表示匹配的“信心”程度 - 因此您可以大致了解两个区域的相似程度。
3
我用ImageMagick试着做了一下这个。以下是我所做的动画，以及接下来的解释和代码。
首先，我使用webkit2png获取了几个StackOverflow页面，并将它们命名为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))
这个非常低效，但是对于精美的动画表示赞扬！ - Nuthatch
@MarkSetchell，所以我最终使用SSIM和模板匹配为自己几年前的问题实现了这个功能，https://dev59.com/SbDla4cB1Zd3GeqP50sw#67328088 对您可能会很有趣。 - Mike 'Pomax' Kamermans
2
傅里叶变换（FFT）的解决方案可能比您预期的更复杂。对于一般问题，这可能是唯一可靠的方法。
要想得到简单的解决方案，您需要开始做出一些假设。例如，您能保证图像的列对齐（除了所述的更改）吗？这使您可以按照@n.m建议的路径继续进行。
您可以将图片切成垂直条，如果足够比例的条匹配，则认为该行匹配？
[如果我们需要对此进行鲁棒性处理，可以使用带有差异列偏移量的几个通道来重新完成此操作。]
这样就得到了如下内容：
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_;

};
这是一个不错的折中方案，考虑到你所描述的假设 - 如果可以假定列对齐，也许考虑使用基于行的校验和进行匹配会是一个好主意？ - Roger Rowland
嗯。Op特别希望在整行中允许一些更改，那么基于整行的校验和如何处理？ - Keith
好的观点 - 我想可能可以标记那些完全匹配的行，因此可能会得到一些连续匹配的行，以及一些不匹配的行，从而识别出变化。我只是在这里随便想想... - Roger Rowland
我知道你的想法。使用任何简化算法都很容易构造出可以产生错误匹配的数据。这是否是一个问题将取决于实际的数据集。 - Keith
Keith，谢谢你。问题：1.循环索引应该从0到stripWidth还是从0到numStrips？2.我的图像总是JPEG格式，您建议如何进行“模糊相等”？3.如果A的最后一行仅包含噪声（最简单的情况：黄色背景，因此可以匹配B中的许多线条；另一种情况：也是背景，不一定在整个线条上具有相同的颜色，但在A和B中仍然具有重复的图案背景），这个算法不会找到错误的正例吗？ - Buu
0

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

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

你能详细说明一下你所说的“排序行并合并”的意思吗？ - Buu
如果让我排序两个数组，比如数字或字符串，我能理解。但这是两个像素行的数组，按照什么标准进行排序呢？ - Buu
我还是不明白。假设我根据每行的哈希值对数组进行排序和合并；现在原来重叠的行将分散在合并后的数组中。此外，由于“噪声”行（如黄色背景、分隔符等）可能会出现在它们之间，因此A的每一行都将跟随B的重叠行。我不知道该如何处理这个合并结果。 - Buu
好的，我会详细解释一下。你不需要对行本身进行排序，而是对指向原始行的辅助索引或指针数组进行排序。然后在合并时，你不会创建一个合并的数组，而是标记A中的这个项目等于B中的那个项目，然后丢弃两个项目，而不是将它们移动到合并的数组中。 - n. m.
1
排序行将提供一个非连续的原始匹配集，而他需要连续匹配。-1 - Vesper
显示剩余3条评论
0

类似下面这样的代码可能会有所帮助：

首先，从下往上遍历图像A，搜索其中有重要信息的行。例如，可以通过计算跨行的总颜色变化量来确定“信息”。比如，如果相邻的两个像素的颜色分别为#ffffff和#ff0000，则将2.0添加到总数中。准备一系列阈值，并锁定达到该阈值的第一行。这个系列可以是“10.0、0.1*行长度、0.15*行长度……”等等，直到一个合理的限制。然后，从最上面发现的位置向下遍历这个数组，取出相应的行并在B中从底部向上搜索其匹配项。如果找到了，并且阈值足够大，则取数组中的下一个并计算其匹配项的位置，进行比较。如果成功，就锁定了B相对于A的正确偏移量，它等于height_of_A - first_row_index + first_row_match_index。如果失败，则继续搜索下一行。如果所有匹配都失败了，则从A的最后一行开始，从B的第一行开始搜索，直到从A的底部找到的第一行的偏移量。如果再次失败，则答案为0。当然，如果使用JPEG图像，则使用阈值匹配，因为A和B中的像素可能不完全相同，也许还需要容忍不匹配的像素。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接