我需要获取一张大图片中小图位置的坐标（例如，我需要在森林照片中搜索特定的树。如果找到子图像，则结果可能类似于：x=120 y=354）。
是否有快速算法可用？
我正在使用Delphi（如果需要也可以使用Java）。
在大图中快速找到小图
3
- Blizzy
2
2如果示例应用程序确实是“在照片中找到树”，那么你手头上有一个人工智能问题，看起来很容易，但很难解决。删除你的“Delphi”标签并添加一个“语言无关”的标签，因为编程语言是无关紧要的。为了了解你所问的问题为什么很困难，这相当于：“在机场人群照片中找到坏人的照片”。你注意到警察没有这个吗？“在图像中找到这个水印”是一个完全不同的问题！ - Cosmin Prund
你应该在dsp.stackexchange.com上提问，而不是在这里。你要查找的图像是否可以旋转或缩放？ - endolith
6个回答
4
编辑：关于理论的一些事情：
简而言之，对于图像应用滤波器有两个“空间”可供选择：颜色空间或频率空间。如果您决定使用频率空间（这里是频率），则有两种类型的滤波器：卷积和相关（这里）。为了简单起见，我们假设将相关性简单地应用于“乘法运算”。使用图像频率空间中的相关性可以衡量图像的相似度。如果灰度梯度相似，则两个图像相似。这由协方差测量。（也许有人可以帮我在这里插入公式。）交叉相关系数是归一化的协方差（插入公式：） 如果将此放入搜索“模型”和“参考图像”之间亲和力的算法中（模型是您在参考图像中搜索的小部分），则会得到matlab代码，我也对其进行了注释。代码使用的公式是： FT([f°g] (m,n))=F(u,v)*G°(u,v)。其中F是fft，G°是G的复共轭（G是模型的fft）
请定义快速。 :) 我想到的解决方案将需要fft，它很快，但可能不如您所需的快。它在I图像中搜索小的“I_ausschnitt”图像，并给出具有最高“可能性”的位置。
在Matlab中，这个函数将起作用。我希望您可以将其放入Delphi中。 :)
I = im2double(imread('Textiltextur.tif')); // This is our reference image
I_model = imcrop( I, [49 36 42 28] ); // Our model - what we want so search in I
[X Y] = size( I ); // Get the size of the reference image.
f = fft2(I); // Perform the fast fourier transform->put the image into frequency space.
f_model = fft2(I_model ,X,Y); // Perform the fft of the model but do this in the size of the original image. matlab will center I_model and set other pixel to zero
w = conj(model ); // Complex conjugated
g = real( ifft2(w.*f)); // .* will perform a komponent wise multiplicaion e.g. [0][0]*[0][0], [0][1]*[0][1] and not a matrix mul.
gs =im2uint8(mat2gray(g)); // Convert the resulting correlation into an grayscale image with larger values->higher correlation
// Rest of the code is for displaying only
figure(1);
imshow(gs);
colormap hsv
figure;
[ XX YY] = meshgrid(1:Y,1:X );
colormap hsv
surfc(XX,YY,double(gs)), title('3D Korrelation')
min_corr = min(min(gs))
max_corr = max(max(gs))
%axis([1 X 1 Y min_corr max_corr])
colorbar
编辑：这只适用于灰度图像。
- InsertNickHere
5
我已经研究了Boyer-Moore算法，看起来这是适合这个任务的算法，但问题的复杂性在于我需要在二维空间中进行搜索，而不是线性搜索。 - Blizzy
1不需要使用Boyer-Moore算法。 - Hannes Ovrén
我认为你应该注释你的代码正在做什么。并不是每个人都熟悉卷积、傅里叶变换和相关性之间的联系，或者为什么你可能想要使用它们。 :) - Hannes Ovrén
@kigurai，你是对的，我很抱歉。我会尽快添加注释。 - InsertNickHere
只有当源和目标具有相同的方向和大小时，交叉相关才能起作用。如果它们可以相对旋转或缩放，那么它将无法工作。 - endolith
2
一种可能的方法是使用Boyer-Moore字符串搜索算法：http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm。当然，您需要根据您的图像搜索问题进行调整。
假设大图像有N个像素，小图像有M个像素，则平均情况下性能为N/M，这相当不错。
假设大图像有N个像素，小图像有M个像素，则平均情况下性能为N/M，这相当不错。
- Mathiasdm
6
我已经研究了Boyer-Moore算法，看起来这是适合这个任务的算法，但问题的复杂性在于我需要在二维空间中进行搜索，而不是线性搜索。 - Blizzy
1你可以做的一件简单的事情是逐行遍历图像（将图像视为一行）。作为Boyer-Moore算法中的子字符串，你可以使用子图像的第一行。虽然比使用整个子图像要慢，但实现起来应该很简单。 - Mathiasdm
1除非图像是未压缩、未修改的图像，否则很可能会失败（因为它需要找到相同的像素值）。如果 OP 需要处理的图像是照片（最有可能是 JPG 格式），那么这肯定会失败：JPEG 压缩是在块级别而不是行或像素级别进行的。打开 JPEG 文件，裁剪其中一部分并将其保存为新的 JPEG 文件将生成略微不同的像素值。 - Cosmin Prund
1不，不，不，不，不。这只在非常特殊的情况下才能起作用，正如Cosmin Prund所指出的那样。
这种问题在计算机视觉中很常见，有许多算法可以完成这项工作。
任何具有CV或图像处理经验的人都不会点赞这个。 - Hannes Ovrén
除非图像完全相同，否则这是行不通的。如果一个像素为（12,45,123），而另一个像素为（12,46,123），它们将不匹配。交叉相关将匹配即使图像有噪声或轻微差异，但只有在方向和比例相同的情况下。 - endolith
回顾这4年后，这确实是一个有点愚蠢的答案 :-) - Mathiasdm
1
它非常快（在1600x900上无法找到，90ms内可以找到），而且是您能够找到的唯一一个。
欢迎任何加速。已检查在Win7/Win10 x64，XE2，XE5下使用24位位图正常工作。
它的作用是从文件中加载子图像并在屏幕上搜索它（通过角落颜色来识别图像，如果匹配则按照所附图像进行搜索），但您可以轻松地适应它。
uses
System.Generics.Collections;
type
TSubImageInfo = record
X: integer;
Y: integer;
Color: integer;
end;
function ImageSearch(const ASubimageFile: string): TRect;
var
X, Y, K, _Color: integer;
_SubImageInfo: TSubImageInfo;
_SubImageInfoList: TList<TSubImageInfo>;
_SmallWidth, _SmallHeight, _BigWidth, _BigHeight: integer;
_MatchingPixels: integer;
_LTColor, _RTColor, _LBColor, _RBColor: integer;
_FirstPixels: TList<TSubImageInfo>;
_Offset: TPoint;
_Desktop: HDC;
_ScreenBitmap: TBitmap;
_SubimageBitmap: TPNGImage;
_Pos: TPoint;
begin
Result.Left := -1;
Result.Top := Result.Left;
Result.Height := Result.Left;
Result.Width := Result.Left;
if not FileExists(ASubimageFile) then
Exit;
_SubImageInfoList := TList<TSubImageInfo>.Create;
_ScreenBitmap := TBitmap.Create;
_SubimageBitmap := TPNGImage.Create;
_FirstPixels := TList<TSubImageInfo>.Create;
try
_SubimageBitmap.LoadFromFile(ASubimageFile);
if (_SubimageBitmap.Height < 3) or (_SubimageBitmap.Width < 3) then
Exit; // Image is too small
X := 0;
Y := _SubimageBitmap.Height div 2;
while X < _SubimageBitmap.Width - 1 do
begin
_SubImageInfo.X := X;
_SubImageInfo.Y := Y;
_Color := _SubimageBitmap.Canvas.Pixels[X, Y];
_SubImageInfo.Color := _Color;
_SubImageInfoList.Add(_SubImageInfo);
X := X + 3;
end;
Y := 0;
X := _SubimageBitmap.Width div 2;
while Y < _SubimageBitmap.Height - 1 do
begin
_SubImageInfo.X := X;
_SubImageInfo.Y := Y;
_Color := _SubimageBitmap.Canvas.Pixels[X, Y];
_SubImageInfo.Color := _Color;
_SubImageInfoList.Add(_SubImageInfo);
Y := Y + 3;
end;
X := 0;
Y := _SubimageBitmap.Height div 4;
while X < _SubimageBitmap.Width - 1 do
begin
_SubImageInfo.X := X;
_SubImageInfo.Y := Y;
_Color := _SubimageBitmap.Canvas.Pixels[X, Y];
_SubImageInfo.Color := _Color;
_SubImageInfoList.Add(_SubImageInfo);
X := X + 3;
end;
Y := 0;
X := _SubimageBitmap.Width div 4;
while Y < _SubimageBitmap.Height - 1 do
begin
_SubImageInfo.X := X;
_SubImageInfo.Y := Y;
_Color := _SubimageBitmap.Canvas.Pixels[X, Y];
_SubImageInfo.Color := _Color;
_SubImageInfoList.Add(_SubImageInfo);
Y := Y + 3;
end;
X := 0;
Y := (_SubimageBitmap.Height div 4) + (_SubimageBitmap.Height div 2);
while X < _SubimageBitmap.Width - 1 do
begin
_SubImageInfo.X := X;
_SubImageInfo.Y := Y;
_Color := _SubimageBitmap.Canvas.Pixels[X, Y];
_SubImageInfo.Color := _Color;
_SubImageInfoList.Add(_SubImageInfo);
X := X + 3;
end;
Y := 0;
X := (_SubimageBitmap.Width div 4) + (_SubimageBitmap.Width div 2);
while Y < _SubimageBitmap.Height - 1 do
begin
_SubImageInfo.X := X;
_SubImageInfo.Y := Y;
_Color := _SubimageBitmap.Canvas.Pixels[X, Y];
_SubImageInfo.Color := _Color;
_SubImageInfoList.Add(_SubImageInfo);
Y := Y + 3;
end;
_Desktop := GetDC(0);
_ScreenBitmap.PixelFormat := pf32bit;
_ScreenBitmap.Width := Screen.Width;
_ScreenBitmap.Height := Screen.Height;
BitBlt(_ScreenBitmap.Canvas.Handle, 0, 0, _ScreenBitmap.Width,
_ScreenBitmap.Height, _Desktop, 0, 0, SRCCOPY);
_MatchingPixels := 0;
_SmallWidth := _SubimageBitmap.Width - 1;
_SmallHeight := _SubimageBitmap.Height - 1;
_BigWidth := _ScreenBitmap.Width;
_BigHeight := _ScreenBitmap.Height;
_LTColor := _SubimageBitmap.Canvas.Pixels[0, 0];
_RTColor := _SubimageBitmap.Canvas.Pixels[_SmallWidth, 0];
_LBColor := _SubimageBitmap.Canvas.Pixels[0, _SmallHeight];
_RBColor := _SubimageBitmap.Canvas.Pixels[_SmallWidth, _SmallHeight];
for X := 1 to 3 do
begin
for Y := 1 to 3 do
begin
_SubImageInfo.X := X;
_SubImageInfo.Y := Y;
_SubImageInfo.Color := _SubimageBitmap.Canvas.Pixels[X, Y];
_FirstPixels.Add(_SubImageInfo);
end;
end;
X := 0;
while X < _BigWidth - _SmallWidth do
begin
Y := 0;
while Y < _BigHeight - _SmallHeight do
begin
_Color := _ScreenBitmap.Canvas.Pixels[X, Y];
_Offset.X := 0;
_Offset.Y := 0;
for K := 0 to _FirstPixels.Count - 1 do
begin
if (_Color = _FirstPixels[K].Color) then
begin
_Offset.X := _FirstPixels[K].X;
_Offset.Y := _FirstPixels[K].Y;
Break;
end;
end;
// Check if all corners matches of smaller image
if ((_Offset.X <> 0) or (_Color = _LTColor)) and
(_ScreenBitmap.Canvas.Pixels[X + _SmallWidth, Y] = _RTColor) and
(_ScreenBitmap.Canvas.Pixels[X, Y + _SmallHeight] = _LBColor) and
(_ScreenBitmap.Canvas.Pixels[X + _SmallWidth, Y + _SmallHeight]
= _RBColor) then
begin
// Checking if content matches
for K := 0 to _SubImageInfoList.Count - 1 do
begin
_Pos.X := X - _Offset.X + _SubImageInfoList[K].X;
_Pos.Y := Y - _Offset.Y + _SubImageInfoList[K].Y;
if (_ScreenBitmap.Canvas.Pixels[_Pos.X, _Pos.Y] = _SubImageInfoList
[K].Color) then
_MatchingPixels := _MatchingPixels + 1
else
begin
_Pos.X := X - _Offset.X - 1 + _SubImageInfoList[K].X;
_Pos.Y := Y - _Offset.Y + 1 + _SubImageInfoList[K].Y;
if (_ScreenBitmap.Canvas.Pixels[_Pos.X, _Pos.Y]
= _SubImageInfoList[K].Color) then
_MatchingPixels := _MatchingPixels + 1
else
begin
_MatchingPixels := 0;
Break;
end;
end;
end;
if (_MatchingPixels - 1 = _SubImageInfoList.Count - 1) then
begin
Result.Left := X - _Offset.X;
Result.Top := Y - _Offset.Y;
Result.Width := _SubimageBitmap.Width;
Result.Height := _SubimageBitmap.Height;
Exit;
end;
end;
Y := Y + 3;
end;
X := X + 3;
end;
finally
FreeAndNil(_FirstPixels);
FreeAndNil(_ScreenBitmap);
FreeAndNil(_SubimageBitmap);
FreeAndNil(_SubImageInfoList);
end;
end;
它的作用是从文件中加载子图像并在屏幕上搜索它（通过角落颜色来识别图像，如果匹配则按照所附图像进行搜索），但您可以轻松地适应它。
- Edijs Kolesnikovičs
1
有许多不同的技术可以在图像中找到子图像。
最直接的方法是在较大的图像上使用您的小图像的2D相关。这将相当缓慢但易于实现。它仅在子图像与原始图像对齐（无旋转）且比例相同的情况下有效。
如果不是这种情况（您具有旋转和/或比例变化），则需要更高级的东西。我的选择是使用SIFT或SURF等特征检测算法。
并且要重申我在大多数先前答案中提出的观点：使用为1D字符串设计的算法（Boyer-Moore）进行图像处理是错误的。如果这样做，您很可能会花费数小时来实现和适应在当前上下文中不起作用的东西，而您可以使用其他更好的算法。
- Hannes Ovrén
5
1从评论中看来，@Blizzy 的意思是“精确”匹配，因此这真的是一个模式匹配问题，而不是模式识别的问题。在视觉领域确实很罕见。 - Roman Shapovalov
2考虑到所使用的图像压缩，我认为数据不完全相同是高风险的。除非百分之百确定不会有影响，否则我绝不会假设像素完美匹配。
此外，在图像中测试所有可能的 blob 位置可能比特征提取方法慢。 - Hannes Ovrén
一个模式匹配算法应该更快，只要它适合这个任务。如果模式具有恒定的大小，则像素数量是线性的。在实践中，我们很少需要对每个像素进行多次比较（除非图像中填充了流行的纹理）。如果您运行特征提取，则需要首先检测角落，这可能不比模式匹配简单。然后，特征提取和特征匹配将需要更多时间。所以我认为这不是使用它的原因，但是... - Roman Shapovalov
有趣的问题是特征提取是否比交叉相关方法更快。X-corr允许一定的差异（例如由压缩引起的差异），但不允许旋转、缩放或简单的扭曲，只允许平移（对吧？）。直觉上，由于搜索空间要小得多，应该更快，但谁知道呢。这可能取决于FFT实现。 - Roman Shapovalov
当您使用LockBits并具有精确的ARGB像素数据时怎么办？原帖作者表示它将是一个完全匹配。但问题是，如何在二维空间中执行Boyer-Moore算法？ - mikew
0
如果您正在寻找完全匹配（即您要查找的模式与图像中要查找的区域之间没有任何差异），则实际上可以使用Boyer Moore算法。将其适应于查找2D模式应该相当简单。
假设您要查找的模式大小为20x20像素。您可以构建一个将灰度值（或颜色）映射到模式图像中位置的表格。现在，您可以通过大步骤浏览搜索图像，从19/19像素开始：如果此像素包含不包含在模式中的灰度值，则可以跳过此位置及其周围20x20区域中的所有位置。因此，您将检查的下一个像素将位于搜索图像中的39/19处。如果它包含在模式图像中出现在3个位置的像素，则可以相对于您在搜索图像中的当前位置（39/19）测试这三个位置。
请注意，此算法有两个假设：
假设您要查找的模式大小为20x20像素。您可以构建一个将灰度值（或颜色）映射到模式图像中位置的表格。现在，您可以通过大步骤浏览搜索图像，从19/19像素开始：如果此像素包含不包含在模式中的灰度值，则可以跳过此位置及其周围20x20区域中的所有位置。因此，您将检查的下一个像素将位于搜索图像中的39/19处。如果它包含在模式图像中出现在3个位置的像素，则可以相对于您在搜索图像中的当前位置（39/19）测试这三个位置。
请注意，此算法有两个假设：
- 你只能找到完全匹配的图像。对于现实世界中的图像来说，这几乎是不可能的，除非模式图像直接从搜索图像中提取出来。如果源图像和模式图像是从同一张照片上扫描出来的，使用相同的扫描仪也很难奏效。如果在提取模式后，模式或源图像使用了有损压缩（如jpeg），那么它将无法工作。
- 加速取决于使用的灰度级数。如果你正在一个二进制图像中寻找一个二进制模式，则此算法将无法以O(n/m)的时间运行。
- Niki
7
是的，子图像将是完全匹配的。我会尝试实现你的算法。谢谢你的回答。 - Blizzy
1正如其他答案所指出的那样：在这种情况下，Boyer-Moore算法不是一个好选择。 - Hannes Ovrén
这不对吗？你不能从（19,19）跳到（39,19）。假设你的20x20针图像位于位置（1,0）到（20,19）。你会直接跳过它。也许我漏掉了什么。我也在尝试弄清楚如何在二维空间中使用Boyer-Moore(-Horspool)，但对我来说很复杂。 :( - mikew
如果你要寻找一个精确匹配，那么你可以安全地跳过20个像素。你只需要从像素值到模板中位置构建一个查找表。然后根据LUT检查从位置（19,19）开始的偏移量。如果没有偏移匹配，则可以跳过之间的像素并测试(39,19)。 - Niki
啊，我现在明白了。如果检查的草堆像素与针头中的任何一个不匹配，那么我们可以跳过整个针头大小。你会如何构建二维查找表？ - mikew
显示剩余2条评论
-1
对于2D位置匹配问题，我会采取实用的方法：
从0到Larger.Height - Smaller.Height和从0到Larger.Width - Smaller.Width扫描较大位图中的每一行，以查找Smaller.TopLeft匹配像素。当找到时：
如果Smaller.TopRight、Smaller.BottomLeft和Smaller.BottomRight都等于较大位图中相应的像素（所有角落都匹配），则启动该部分的完全比较。
确保所有比较都尽早失败（在任何不匹配后不继续比较）。
平均而言，您只需要扫描不到50%的较大位图，并且不会启动许多失败的完全比较。
- Despatcher
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接