将源图像与已知图像库进行比较

Question

我正在为一个朋友的父亲开发一款应用程序。他不幸中风，无法讲话、阅读或拼写，但是他会画出相当详细的图画。

目前我已经开发了一款能够处理绘画图片并检测基本形状（线条、正方形和三角形）的应用程序。该应用程序可以计算每种形状各有多少个，从而区分两个拥有不同数量正方形的图片。

这将会对用户产生很大的认知负担，需要记住所有形状和它们的意义。我目前通过以下代码检测图像中的轮廓：

findContours(maskMat, contours, hierarchy, CV_RETR_LIST, CV_CHAIN_APPROX_SIMPLE);

我的目标是，用户先画出一个形状，然后将其添加到已知图案库中。每次用户画出一张图片时，应用程序会处理每个已知图案并将其与源图像进行比较，并保存相似性值。然后取最高相似性值作为被画出的图像所匹配的最佳已知图像，提供它超过一个阈值。

我已经尝试了OpenCV模式匹配和模板匹配，但结果不可靠。我想请教最好的方法，以便实现我所希望的结果。

我为我的大学讲座制作了一个推广视频，最能说明这个应用程序的功能。如果您感兴趣，可以在这里观看：https://youtu.be/ngMUUIsLHoc

提前感谢您的帮助。

- Ste Prescott

---

你试过使用cv函数matchShapes吗？文档链接：http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html#double%20matchShapes%28InputArray%20contour1,%20InputArray%20contour2,%20int%20method,%20double%20parameter%29 - Micka

你能提供一系列“相同形状”的图片吗？ - Micka

@Micka 最终目标是让应用程序理解Blissymbolics语言。这是一种为那些通过语音难以沟通的人们所教授的已知语言。可以在此处找到一些示例：http://www.the-symbols.net/blissymbolics/dictionary/。 - Ste Prescott

Answer 1

基于描述的方法

根据您的视频，我认为您主要是对比线条绘画而不是详细的素描感兴趣。对于线条绘画，我可以想到以下基于描述的方法。所提出的描述是基于比率的，不会依赖于形状的绝对大小/尺寸，也应该很好地处理变化。

计算形状的描述

您需要计算标准化形状的描述，这将对不同实例之间的小变化具有弹性。如前面的答案中所提到的，形状匹配和基于草图的检索有大量的文献，因此我不会重复。假设您处理的形状是直线或多边形形状，则以下相对简单的方法应该有效。

1. 使用Hough变换检测图像中的所有线条。这里提供了一个非常详细的示例。（http://docs.opencv.org/doc/tutorials/imgproc/imgtrans/hough_lines/hough_lines.html）手绘的线条可能不完全直线，Hough可能无法将它们检测为单个线条，而是多个具有不同斜率和截距的不同线段。您可以将草图限制为仅以线条形式存在，或使用一个线拟合方法来拟合略微不规则的手绘线。

2. 根据X坐标和Y坐标对这些线进行排序。

3. 按从左到右、从底部到顶部（或任何固定的顺序）遍历这些线，并计算每条线的以下属性。

   • 当前线条和下一条线条之间的夹角。（http://www.vitutor.com/geometry/line/angle_lines.html）
   • 相邻（当前和下一个）线条的长度比。
   • 两条线的交点（0-没有交点，1-找到交点）
   • 如果线相交，则计算由当前线中交点创建的两个段的长度比例。（此处有示例https://www.youtube.com/watch?v=G17Nbb1d3Yc）

4. 通过连接上述值创建特征向量，例如，如果草图有三条线，则特征向量的形式为 { theta1, theta2, theta3, lengthRatio1, lengthRatio2, lengthRatio3, segmentRatio1, segmentRatio2, segmentRatio3 }

匹配查询和数据库形状

如上所述，您可以为数据库中的所有形状以及任何新的查询创建特征向量表示。现在，您可以编写一个简单的函数来计算两个向量之间的距离。下面是伪代码。

int numLines; // computed using hough transform
vector<float> featureVector1(vec_size);
vector<float> featureVector1(vec_size);
...
// feature vectors computed as explained//

// Compute error between two vectors //

float angleError = 0.0f, lengthRatioError = 0.0, segmentRatioError = 0.0;

float diff = 0.0;    
// (0,numLines-1) elements of the vector are angles
for(int i=0; i < numLines; i++) {
    diff = abs(featureVector1[i] - featureVector2[i]);
    angleError += diff;
}

diff = 0.0;
// (numLines,2numLines-1) elements of the vector are length ratios
for(int i=numLines; i < 2*numLines-1; i++) {
    diff = abs(featureVector1[i] - featureVector2[i]);
    lengthRatioError += diff;
}

diff = 0.0;
// (2*numLines,3numLines-1) elements of the vector are segment ratios
// These values should be zero for no intersection
for(int i=numLines; i < 2*numLines-1; i++) {
    diff = abs(featureVector1[i] - featureVector2[i]);
    segmentRatioError += diff;
}

// Weights for errors - you should play around with these. 
float w1 = 1.0, w2 = 1.0, w3 = 1.0;
totalError = w1*angleError + w2*lengthRatioError + w3*segmentRatioError;

将查询特征与所有数据库特征进行匹配，并找到距离最小的形状（totalError）。如果距离低于阈值，则宣布匹配成功，否则将查询声明为新的形状并添加到数据库中。

- rs_

---

感谢@rajvi提供详细的答案。我会进一步研究这个问题。如果有任何问题，您是否可以回答并提供更多帮助？ - Ste Prescott

是的，当然。如果您需要任何澄清，请告诉我。 - rs_

Answer 2

首先，这看起来是一个很棒的应用程序。并且有一个很棒的目的。干得好！

对于你的问题，根据视频观察，似乎可以采取以下方法：

1.将每个绘图区域分成（比如）3x3网格，并允许每个区域包含一个基元，比如垂直线、水平线、正方形、圆形、三角形或什么都没有。（这在某种程度上取决于你朋友的家长的运动控制能力）

2.当一张图片完成时，检测这些基元并编码一个（比如）9个字符的关键字，可用于检索相应的图片。例如，如果三角形是T，正方形是S，空白是下划线，则“我要回家”的代码如视频所示为“_T__S____”。

3.当开始一张新图片时，您可以检测每个基元的绘制并使用它来构造一个搜索关键字，其中关键字具有未知字符的“？”。然后，您可以快速从数据库中检索所有可能的匹配项。

例如，如果用户在顶部中间区域绘制了一个三角形，这将被编码为“?T???????”，这将与“_T__S____”以及“_TT______”匹配。

如果限制用户在屏幕的较小区域内绘制不可行，则仍然可以存储表示每个基元的相对位置的编码关键字。

为此，您可以计算每个基元的质心，从左到右，从上到下排序，然后存储它们相对位置的某些表示形式，例如，三角形在正方形上方可能是TVS，其中V表示S在T下方，三角形位于正方形左侧可能是T

希望这有所帮助。祝你好运！

- Dave Durbin

---

谢谢您的建议。这是一种聪明的利用我已有资源的方式，但它需要用户每次以相同的大小绘制形状。因此，如果他画了一个大正方形，覆盖了所有9个段，那么它将与只覆盖4个段的小正方形不同。 - Ste Prescott

你对形状的大小是否有意义或形状是否可以重叠有任何限制吗？似乎即使没有将绘图区域分段，仍然可以使用相对位置来编码密钥，即捕捉三角形在正方形上方而不是在正方形旁边的想法。 - Dave Durbin

你可以通过将边界框适配到草图并将其宽度/高度设置为某个单位长度来将形状归一化为单位长度。你可以通过检测最左、最右、最上和最下的像素来适配边界框，假设周围没有嘈杂的点或线条。如果有一些噪声，你可以使用一些基本的图像处理方法，比如查找连接组件并删除只有几个像素（嘈杂的点等）的组件。 - rs_

Answer 3

1. 基于素描的图像检索。有很多文献研究了如何使用素描作为查询来查找真实图像。虽然不完全符合您的要求，但某些技术可能可以适用于使用素描作为查询来查找素描图像。它们甚至可能不需要修改就可以直接使用。

2. 自动识别手写中文字符（或类似的书写系统）。这方面也有相当多的文献可供参考。虽然存在差异，但这个问题本质上与从图像素描演变而来的书写系统非常相似。可以尝试应用一些相同的技术。

3. 单条线的数量、顺序和位置可能比成品素描更具信息量。有没有一种方法可以捕捉到这个信息？如果用户使用笔画绘图，您可以记录每条线的笔迹轨迹。这将比图像本身的信息内容要多得多。想象一下有人闭着眼睛画一辆汽车。根据轨迹，您可以轻松地确定它是一辆汽车。从图片中可能会更难。

4. 如果按照上述描述捕捉到线条，则匹配问题可以在某种程度上简化为将图像A中的一些线条与图像B中最相似的线条进行匹配（可能存在变形、偏移等情况）。它们还应该与其他线条具有相似的关系：例如，如果图像A中的两条线相交，则图像B中的这两条线条也应该相交，并且在每个线条的长度上位置和角度应该是相似的。为了更加稳健，这应该理想地处理诸如一个图像中的两条线对应于另一个图像中的单个合并线条之类的事情。

- Alex I

Answer 4

鉴于这个库已经存在了很长时间并且似乎维护得很好，可能有助于解决问题的一种方法是使用ImageMagick。让我来演示一下。

1. 使用以下命令安装Pod：

pod 'ImageMagick', '6.8.8-9'

在视图控制器或其他您想要比较图像的视图中，导入以下内容：

#import <wand/MagickWand.h>

创建易于模式的异常“宏”，以便在不必每次编写异常方法时即可检查异常错误：

#define ThrowWandException(wand) { \
char * description; \
ExceptionType severity; \
\
description = MagickGetException(wand,&severity); \
(void) fprintf(stderr, "%s %s %lu %s\n", GetMagickModule(), description); \
description = (char *) MagickRelinquishMemory(description); \
exit(-1); \
}

3 创建比较方法，以比较两个图像：

-(void)compareTwoImages:(UIImage*)firstImage secondImage:(UIImage*)secondImage comparitorSize:(size_t)comparitorSize {

    double diff1, diff2, diff3, diff4, diff5, diff6, diff7, diff8, diff9, diff10, diff11, diff12;

    MagickWandGenesis();
    MagickWand *magick_wand_1 = NewMagickWand();
    NSData * dataObject1 = UIImagePNGRepresentation(firstImage);
    MagickBooleanType status1;
    status1 = MagickReadImageBlob(magick_wand_1, [dataObject1 bytes], [dataObject1 length]);

    if (status1 == MagickFalse) {
        ThrowWandException(magick_wand_1);
    }

    MagickWandGenesis();
    MagickWand *magick_wand_2 = NewMagickWand();
    NSData * dataObject11 = UIImagePNGRepresentation(secondImage);
    MagickBooleanType status11;
    status11 = MagickReadImageBlob(magick_wand_2, [dataObject11 bytes], [dataObject11 length]);

    if (status11 == MagickFalse) {
        ThrowWandException(magick_wand_2);
    }

    MagickScaleImage(magick_wand_2, comparitorSize, comparitorSize);
    MagickScaleImage(magick_wand_1, comparitorSize, comparitorSize);

    MagickWandGenesis();
    MagickWand *magick_wand_3 = NewMagickWand();

    MagickCompareImages(magick_wand_1, magick_wand_2, UndefinedMetric, &diff1);
    MagickCompareImages(magick_wand_1, magick_wand_2, AbsoluteErrorMetric, &diff2);
    MagickCompareImages(magick_wand_1, magick_wand_2, MeanAbsoluteErrorMetric, &diff3);
    MagickCompareImages(magick_wand_1, magick_wand_2, MeanErrorPerPixelMetric, &diff4);
    MagickCompareImages(magick_wand_1, magick_wand_2, MeanSquaredErrorMetric, &diff5);
    MagickCompareImages(magick_wand_1, magick_wand_2, PeakAbsoluteErrorMetric, &diff6);
    MagickCompareImages(magick_wand_1, magick_wand_2, PeakSignalToNoiseRatioMetric, &diff7);
    MagickCompareImages(magick_wand_1, magick_wand_2, RootMeanSquaredErrorMetric, &diff8);
    MagickCompareImages(magick_wand_1, magick_wand_2, NormalizedCrossCorrelationErrorMetric, &diff8);
    MagickCompareImages(magick_wand_1, magick_wand_2, FuzzErrorMetric, &diff10);
    MagickCompareImages(magick_wand_1, magick_wand_2, UndefinedErrorMetric, &diff11);
    MagickCompareImages(magick_wand_1, magick_wand_2, PerceptualHashErrorMetric, &diff12);

    NSLog(@"UndefinedMetric: %.21f", diff1);
    NSLog(@"AbsoluteErrorMetric: %.21f", diff2);
    NSLog(@"MeanAbsoluteErrorMetric: %.21f", diff3);
    NSLog(@"MeanErrorPerPixelMetric: %.21f", diff4);
    NSLog(@"MeanSquaredErrorMetric: %.21f", diff5);
    NSLog(@"PeakAbsoluteErrorMetric: %.21f", diff6);
    NSLog(@"PeakSignalToNoiseRatioMetric: %.21f", diff7);
    NSLog(@"RootMeanSquaredErrorMetric: %.21f", diff8);
    NSLog(@"NormalizedCrossCorrelationErrorMetric: %.21f", diff9);
    NSLog(@"FuzzErrorMetric: %.21f", diff10);
    NSLog(@"UndefinedErrorMetric: %.21f", diff11);
    NSLog(@"PerceptualHashErrorMetric: %.21f", diff12);

    DestroyMagickWand(magick_wand_1);
    DestroyMagickWand(magick_wand_2);
    DestroyMagickWand(magick_wand_3);

    MagickWandTerminus();
}

观察调试器的输出（显然，你需要另一种方法来使用某种“阈值”监视器来确定哪个级别显示“精确或接近匹配”，而不是你自己认为的匹配）。非常重要的一点是，在上面的方法输入中我有一个“size_t”变量用于大小，因为您不能比较不同大小的图像，所以您必须首先将要比较的图像调整为您认为“合理”的大小，然后使用ImageMagick调整两个图像的大小，然后再进行比较。 示例1：

[self compareTwoImages:[UIImage imageNamed:@"book.png"]
           secondImage:[UIImage imageNamed:@"book.png"]
        comparitorSize:32];

[76233:1364823] UndefinedMetric: 0.866871957624008593335

[76233:1364823] AbsoluteErrorMetric: 0.000000000000000000000

[76233:1364823] MeanAbsoluteErrorMetric: 0.000000000000000000000

[76233:1364823] MeanErrorPerPixelMetric: 0.000000000000000000000**

[76233:1364823] MeanSquaredErrorMetric: 0.000000000000000000000

[76233:1364823] PeakAbsoluteErrorMetric: 0.000000000000000000000

[76233:1364823] PeakSignalToNoiseRatioMetric: inf

[76233:1364823] RootMeanSquaredErrorMetric: 0.866871957624008593335

[76233:1364823] NormalizedCrossCorrelationErrorMetric: 0.000000000000000000000

[76233:1364823] FuzzErrorMetric: 0.000000000000000000000

[76233:1364823] UndefinedErrorMetric: 0.866871957624008593335

[76233:1364823] PerceptualHashErrorMetric: 0.000000000000000000000

例子2：

[self compareTwoImages:[UIImage imageNamed:@"book.png"]
             secondImage:[UIImage imageNamed:@"arrow.png"]
          comparitorSize:32];

[76338:1368754] UndefinedMetric: 0.074585376822533272501

[76338:1368754] AbsoluteErrorMetric: 795.000000000000000000000

[76338:1368754] MeanAbsoluteErrorMetric: 0.314410045058480136504

[76338:1368754] MeanErrorPerPixelMetric: 328395.000000000000000000000

[76338:1368754] MeanSquaredErrorMetric: 0.245338692857198115149

[76338:1368754] PeakAbsoluteErrorMetric: 1.000000000000000000000

[76338:1368754] PeakSignalToNoiseRatioMetric: 6.102339529383479899138

[76338:1368754] RootMeanSquaredErrorMetric: 0.074585376822533272501

[76338:1368754] NormalizedCrossCorrelationErrorMetric: 0.000000000000000000000

[76338:1368754] FuzzErrorMetric: 0.571942529580490965913

[76338:1368754] UndefinedErrorMetric: 0.074585376822533272501

[76338:1368754] PerceptualHashErrorMetric: 1827.005561849247442296473

这里有很多数学运算。我没有时间解释所有这些变量，但可以说，比较两个图像使用了一些非常著名的方法。你需要从这里开始测试统计数据，以便根据自己的需求自定义并选择适合你目的的误差阈值。

简单解释：

ImageMagick 是一个经过实战检验的图像处理库，虽然上面列出的这些方法有点“黑盒子”的意味，但正是这种黑盒性质使你节省了时间，而不必转向使用 OpenCV 等其他库。ImageMagick 已经建立了一些非常好的图像处理算法，正是这种历史和开箱即用的“此方法可行”是 ImageMagick 的最大优势之一，考虑到开发自己的图像识别/处理库或方法所需付出的代价。 （顺便说一下，我与 ImageMagick 没有关联，我只是对产品非常满意）

Objective-C 方法中使用的方法源于 ImageMagick Library for IOS。你需要阅读这些方法，但是要知道，它们是用 C 编写的，而不是 Objective-C，这意味着某些内容对于普通的图像 I/O 或其他处理库来说有些陌生。然而，我认为唯一难以理解的部分（假设一个人对 C 代码不熟悉）是如何理解一些变量前面的“&”符号。除此之外，还有声明和使用结构体的问题，但这可以很容易地通过使用 Stack Overflow 来回答，这里有很多相关信息。

我不喜欢你必须为此类应用程序编写自己的库或图像处理算法的想法。我认为你正在为需要帮助的人做一件非常好的事情，如果你能锁定一个 MVP 并使用 ImageMagick，我认为它将比需要重新编写 ImageMagick 已经为你的目的做的一些工作更快地到达那里。

最后一件事要注意的是，ImageMagick 是建立在一些非常低级别的 C 库上的。我需要运行某种处理比较来确定 ImageMagick 在 IOS 设备上的表现与 Image I/O 等内容相比如何。然而，我有一种感觉，这两个图像处理库共享一些相同的图像处理功能和速度。如果有人确定 Image I/O 在测试中绝对更快，请纠正我，但我只是告诉你，这不是你平均的 POD 安装，这是一个强大的机器，幸运的是一些 IOS 开发者他们使用 CoccoaPods 做了一个 IOS 版本。除此之外，ImageMagick 用于所有计算平台，主要是一个命令行工具。

统计数据，数字的含义：

这里是您需要了解调试器输出中显示的统计学背后的数学的资源：

第一个资源已经过时，但仍然相关：

这个链接似乎是最新的：

http://www.imagemagick.org/Usage/compare/

无论您选择使用此库还是其他库，祝您好运。我很喜欢您的应用程序和演示看起来非常惊人！

编辑：我几乎忘了告诉你最重要的一点...如果统计数据返回除了“UndefinedMetric”，“PeakSignalToNoiseRatioMetric”，“RootMeanSquaredErrorMetric”和“UndefinedErrorMetric”之外的所有内容都是“零”，那么你可能已经找到了匹配的图像！

- Larry Pickles

---

哇，谢谢你详细的回答。我会尝试一下并更新给你。 - Ste Prescott

没问题，如果你有问题就问吧，这是一个冒险，让这个代码在IOS上正确运行，但现在它被锁定到了一个点，只要你遵循上面的说明，它应该可以直接放下去。 - Larry Pickles

这是一个很好的示例，展示了如何在iOS下使用ImageMagick的“compare”函数，所以感谢您，并且我会投票支持您...但我担心它们不是正确的工具，因为它们逐像素比较两个图像的匹配情况，所以任何形状、大小、位置、旋转或任何扭曲的微小变化都会导致图像不匹配-尝试制作两个图像并将其中一个向右移动3毫米，这种方法将非常差。我认为SIFT技术会更好一些。https://en.wikipedia.org/wiki/Scale-invariant_feature_transform - Mark Setchell

感谢提供更多信息。我会研究SIFT方法。 - Ste Prescott

如果您提供更详细的答案并附上您发现有用的一些资源，那么仍然可以给予100积分的悬赏。悬赏只剩下11个小时了。 - Ste Prescott

你可能从中受益的一个优势是，你实际上可以在线条绘制时检测到它们的发生-因此，你知道线条的方向和速度，这必须是比算法更具优势，因为算法只能处理完成的图形。我发现最有趣的论文在这里... https://www.cs.ucsb.edu/~sherwood/pubs/SBIM-12-spark.pdf 我感觉自己没有资格给出一个正确的答案，所以我会坚持评论。 - Mark Setchell

Answer 5

我强烈推荐使用“词袋模型”。如果您想使用这样的模型来识别自行车，它将把图像细分为其部件（座椅、轮子、车架、转向）。如果它看到另一张包含两个轮子、座椅和车架的图像，它可能会将这个图片与自行车相匹配（因为很多单词是相似的）。这种方法的问题在于没有考虑单词之间的空间关系。

在这种特定情况下，我认为这种方法会相当好地工作，因为素描往往是许多较小（可识别）对象的组合。而不是每次都必须检测自行车，您可以重复使用更小的检测部件（例如轮子），用于需要检测的其他事物（摩托车、汽车等）。

编辑：OpenCV甚至已经实现了词袋模型。它可以在这里找到。

- Nallath