我需要计算二进制图像中物体的长度（对象内像素之间的最大距离）。由于它是二进制图像，因此我们可以将其视为具有值0（白色）和1（黑色）的2D数组。我需要的是一个聪明（最好是简单的）算法来执行此操作。请记住，图像中有许多对象。
澄清图像：
澄清图像：
示例输入图像：
5个回答
3
如果一个对象的边界是凸形的，且没有三个顶点在一条直线上（即没有顶点可以被移除而不改变多边形），那么我认为这个问题很简单：你只需随机选择两个点，并使用简单的梯度下降搜索来找到最长的线：
Start with random vertices A, B
See if the line A' - B is longer than A - B where A' is the point left of A; if so, replace A with A'
See if the line A' - B is longer than A - B where A' is the point right of A; if so, replace A with A'
Do the same for B
repeat until convergence
我建议为每个种子斑点找到凸包，去除所有“多余”的顶点（以确保收敛），然后运行上述算法。
构建凸包是一个O(n log n)的操作，其中n是边界像素的数量。对于这样的小对象应该相当高效。编辑：我刚想起来，凸包算法的O(n log n)需要对点进行排序。如果边界点是连接组分析的结果，则它们已经被排序。因此，整个算法应该在O(n)时间内运行，其中n是边界点的数量。（不过这是很多工作，因为你可能需要编写自己的凸包算法或修改一个算法来跳过排序。）
添加：回应评论
如果您不需要100％的准确性，可以简单地将椭圆拟合到每个斑点上，并计算主轴的长度：这可以从中心矩（如果我没记错的话，它只是协方差矩阵的最大特征值的平方根）中计算出来，因此它是O（n）操作，并且可以在对图像进行单次扫描时高效地计算。 它的额外优势是它考虑了斑点的所有像素，而不仅仅是两个极端点，即它受噪声的影响要少得多。
- Niki
4
啊，是的，计算连通组件并对每个连通组件求凸包将为您提供一个很好的近似值，前提是形状有些复杂。 - ldog
@gmatt：这不是近似值。我很确定他正在寻找的极端点始终在凸包上。使用凸包不会添加任何新点，它只会删除无法成为解决方案的点。 - Niki
实际上，我认为简单的边缘检测可能比在每个单独的 blob/形状上进行完整的凸包更好地得到轮廓。此外，我不认为梯度下降是做这件事的最佳方式，因为它需要太多资源。 - ldog
1@gmatt：这个“梯度下降”算法的最坏情况性能需要进行N个距离计算，其中N是边界点的数量。我怀疑你无法加快速度。凸包是瓶颈，但需要确保收敛。如果你看到任何改进算法的方法，请发布出来！ - Niki
1
我认为你可以考虑使用广度优先搜索算法。
基本思路是循环遍历图像中的每一行和列，如果您还没有访问过该节点（节点是带有彩色像素的行和列），那么您将运行广度优先搜索。您将访问可能的每个节点，并跟踪对象的最大和最小点。
这是一些C++示例代码（未经测试）：
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
// used to transition from given row, col to each of the
// 8 different directions
int dr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dc[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
// WHITE or COLORED cells
const int WHITE = 0;
const int COLORED = 1;
// number of rows and columns
int nrows = 2000;
int ncols = 2000;
// assume G is the image
int G[2000][2000];
// the "visited array"
bool vis[2000][2000];
// get distance between 2 points
inline double getdist(double x1, double y1, double x2, double y2) {
double d1 = x1 - x2;
double d2 = y1 - y2;
return sqrt(d1*d1+d2*d2);
}
// this function performs the breadth first search
double bfs(int startRow, int startCol) {
queue< int > q;
q.push(startRow);
q.push(startCol);
vector< pair< int, int > > points;
while(!q.empty()) {
int r = q.front();
q.pop();
int c = q.front();
q.pop();
// already visited?
if (vis[r][c])
continue;
points.push_back(make_pair(r,c));
vis[r][c] = true;
// try all eight directions
for(int i = 0; i < 8; ++i) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 0 || nr >= nrows || nc < 0 || nc >= ncols)
continue; // out of bounds
// push next node on queue
q.push(nr);
q.push(nc);
}
}
// the distance is maximum difference between any 2 points encountered in the BFS
double diff = 0;
for(int i = 0; i < (int)points.size(); ++i) {
for(int j = i+1; j < (int)points.size(); ++j) {
diff = max(diff,getdist(points[i].first,points[i].second,points[j].first,points[j].second));
}
}
return diff;
}
int main() {
vector< double > lengths;
memset(vis,false,sizeof vis);
for(int r = 0; r < nrows; ++r) {
for(int c = 0; c < ncols; ++c) {
if (G[r][c] == WHITE)
continue; // we don't care about cells without objects
if (vis[r][c])
continue; // we've already processed this object
// find the length of this object
double len = bfs(r,c);
lengths.push_back(len);
}
}
return 0;
}
- dcp
6
如果你只想找到边界上的两个点，那么触及种子的每个像素听起来是低效的。 - Niki
包含的列表几乎比代码本身还长！你在哪里使用复数？！ - ldog
@gmatt - 抱歉，这是我的编程竞赛模板中的内容，我总是有一个留下它们的习惯，但我同意对于这个论坛来说，这可能不是一个好主意。感谢您指出这一点。 - dcp
@nikie - 有时候简单就是最好的。如果图像不太大，就像上面OP提供的例子一样，那么我认为上述算法可能已经足够高效了。但如果我们要处理10亿个像素，那么我同意BFS可能无法胜任。 - dcp
1转念一想，我认为这甚至不会起作用：如果不知道相应的“最大”点，就无法判断一个点是否是“最小”点。我尝试理解C++代码，但我很确定这也行不通：你认为
max<pair<int,int> >是做什么的？ - Niki@nikie - 是的，说得好。我修改了我的代码以跟踪在BFS中遇到的点，并在最后添加了一个循环来查找任意两个点之间的最大距离。再次说明，这可能不如其他方法高效，但我认为它很简单。: )。感谢指出我的错误。 - dcp
1
一个非常粗糙、蛮力的方法是首先识别所有边缘像素（任何与非黑色像素相邻的对象中的黑色像素），并计算所有可能的边缘像素对之间的距离。其中最长的距离将给出对象的长度。
如果对象总是像样本中的那些一样，您可以通过仅评估对象内具有最高和最低x和y值的像素来加快速度。
如果对象总是像样本中的那些一样，您可以通过仅评估对象内具有最高和最低x和y值的像素来加快速度。
- MusiGenesis
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
rice.png，http://www.mathworks.co.jp/access/helpdesk/help/toolbox/images/rice.gif - Jacob