相关疑难解决方法(0)

我更喜欢尽可能少的正式定义和简单的数学.

昨天我把干净的洗衣店的袜子配对,弄清楚我做的方式效率不高.我正在做一个天真的搜索 - 挑选一个袜子并"迭代"堆,以找到它的对.这需要迭代在n/2*N/4 = N ² /8上平均的袜子.

作为一名计算机科学家,我在想我能做什么？当然,为了实现O(NlogN)解决方案,我们会想到排序(根据大小/颜色/ ...).

哈希或其他非就地解决方案不是一种选择,因为我无法复制我的袜子(尽管如果可能的话可能会很好).

所以,问题基本上是:

给出一堆n袜子,包含2n元素(假设每个袜子只有一对匹配),有效配对多达对数额外空间的最佳方法是什么？(我相信如果需要的话我会记住那些信息.)

我将感谢一个解决以下方面的答案:

• 大量袜子的一般理论解决方案.
• 袜子的实际数量并不是那么大,我不相信我的配偶和我有超过30双.(并且很容易区分我的袜子和她的袜子;这也可以使用吗？)
• 它是否等同于元素清晰度问题？

在过去的几年里,我参与过的最有趣的项目之一是关于图像处理的项目.我们的目标是建立一个能够识别可口可乐"罐头"的系统(请注意,我正在强调'罐头'这个词,你会在一分钟内看到原因).您可以在下面看到一个示例,其中可以使用缩放和旋转在绿色矩形中识别.

对项目的一些限制:

• 背景可能非常嘈杂.
• 该罐可以具有任何规模或旋转,甚至方向(在合理的限度内).
• 图像可能有一定程度的模糊性(轮廓可能不完全笔直).
• 图像中可能有可口可乐瓶,算法应该只检测罐头!
• 图像的亮度可能会有很大差异(因此您不能过多依赖颜色检测).
• 该罐可以部分地隐藏在两侧或中间,可能部分地隐藏了一瓶后面.
• 有可能是没有能像在所有的,在这种情况下,你必须找到什么,写一条消息这样说.

所以你最终可能会遇到这样棘手的事情(在这种情况下,我的算法完全失败):

我不久前做了这个项目,并且做了很多乐趣,我有一个不错的实现.以下是有关我的实施的一些细节:

语言:使用OpenCV库在C++中完成.

预处理:对于图像预处理,即将图像转换为更原始的形式以给出算法,我使用了两种方法:

1. 将颜色域从RGB更改为HSV并基于"红色"色调进行过滤,饱和度高于某个阈值以避免橙色样色,并过滤低值以避免暗色调.最终结果是二进制黑白图像,其中所有白色像素将表示与该阈值匹配的像素.显然,图像中仍有很多废话,但这会减少您必须使用的维度数量.
2. 使用中值滤波进行噪声滤波(取所有邻居的中值像素值并用该值替换像素)以减少噪声.
3. 使用Canny边缘检测过滤器在2个先前步骤之后获取所有项目的轮廓.

算法:我为这个任务选择的算法本身取自这本关于特征提取的神奇书籍,称为广义霍夫变换(与常规Hough变换有很大不同).它基本上说了几件事:

• 您可以在不知道其解析方程的情况下描述空间中的对象(这是这种情况).
• 它可以抵抗图像变形,例如缩放和旋转,因为它基本上会针对比例因子和旋转因子的每个组合测试图像.
• 它使用算法将"学习"的基本模型(模板).
• 轮廓图像中剩余的每个像素将根据从模型中学到的内容投票给另一个像素,该像素应该是对象的中心(就重力而言).

最后,你得到了一张投票的热图,例如,这里所有罐子轮廓的像素都会投票给它的引力中心,所以你会在同一个像素对应的投票中得到很多票.中心,并将在热图中看到如下峰值:

一旦你有了这个,一个简单的基于阈值的启发式可以给你中心像素的位置,你可以从中获得比例和旋转,然后围绕它绘制你的小矩形(最终的比例和旋转因子显然将相对于你原始模板).理论上至少......

结果:现在,虽然这种方法在基本情况下起作用,但在某些方面却严重缺乏:

• 这非常慢!我并没有强调这一点.处理30个测试图像需要将近一整天,显然是因为我有一个非常高的旋转和平移比例因子,因为一些罐子非常小.
• 当瓶子出现在图像中时,它完全丢失了,并且由于某种原因,几乎总是发现瓶子而不是罐头(可能因为瓶子更大,因此有更多的像素,因此更多的选票)
• 模糊图像也不好,因为投票在中心周围的随机位置以像素结束,因此以非常嘈杂的热图结束.
• 实现了平移和旋转的方差,但没有取向,这意味着没有直接面对相机物镜的罐子被识别出来.

你能帮助我改进我的特定算法,只使用OpenCV功能来解决上面提到的四个具体问题吗？

我希望有些人也会从中学到一些东西,毕竟我认为不仅要问问题的人应该学习.:)