请教一个算法

mirnux

我现在有一张图片，图片上有很多区域，有标号，比如1到8
现在需要将一些区域合并到一块，需要合并的区域用等价对表示，比如1和2，用1=2表示
假如加入等价对如下：
1＝2，1＝3， 2＝4， 5＝6，6＝8
那么最终会得到1，2，3，4这四个区域合并，5，6，8这三个区域合并，总共最终的结果有三个大的区域

不知道说清楚没有，用C或者C++都行，我想着用STL，想了大半个下午也想到该怎么做
编程经验有限，希望大家能帮帮忙，非常感谢

net_robber

图像识别是人工智能的范畴

ArXoR

和图像有什么关系? 只是等价类的合并而已吧.
当然, 构建一个以原子区域为顶点的无向图, 最后计算连通分量就行了
用并查集也可以
复杂度都是O(m + n), m是给出的等价关系条数, n 是原子区域个数

[ 本帖最后由 ArXoR 于 2007-4-12 20:16 编辑 ]

zhichiamd

LZ说得清楚点，是灰度图像还是RGB彩色图像

mirnux

是灰度图
这个确实和图像没有直接的关系，应该是数据结构的问题
只是没有看过数据结构，所以不知道怎么下手。。。
想了半天有点晕

mirnux

原帖由 ArXoR 于 2007-4-12 20:14 发表
和图像有什么关系? 只是等价类的合并而已吧.
当然, 构建一个以原子区域为顶点的无向图, 最后计算连通分量就行了
用并查集也可以
复杂度都是O(m + n), m是给出的等价关系条数, n 是原子区域个数

好高深。恩，是等价类的合并

我编程就是在图像中求连通域的，ArXoR真是强

我现在就是首先标定了一遍连通域，然后得到该合并的一些等价对
再来合并的时候就没有办法了，功力不够，希望能多给点指点

比如现在首先得到num个连通域
连通域的表示如下，id就是代表了等价对里的值
typedef struct AREA
{
        int                                id;
        int                             num; //点的个数
        vector<myPoint> points;
} AREA;

现在要做的就是进一步合并

ArXoR

原帖由 mirnux 于 4/12/07 20:44 发表

好高深。恩，是等价类的合并

我编程就是在图像中求连通域的，ArXoR真是强

我现在就是首先标定了一遍连通域，然后得到该合并的一些等价对
再来合并的时候就没有办法了，功力不够，希望能多给点指点

比 ...

构造一个n个顶点的图.
当且仅当有等价对 x = y 时, 在x和y之间连接一条边.
然后连通分量...
和具体的区域怎么表示没有关系

mirnux

n个顶点的图怎么构造怎么操作？又怎么连边？能举个小例子么？
-_-!!
比较弱，不好意思

ArXoR

邻接表...
每个顶点u对应一个链表, 链表中的节点保存了每个从u出发的边的目标点v, 表示一条有向边u->v.

mirnux

先把每次等价对表中的第1个等价对压入一个空链表中，然后以此为树根在等价对表中寻找包含链表中元素的等价对，如果找到，当符合条件的等价对中只有一个元素存在于链表中时，则把另一个元素压入到链表中，并在等价对表中删除这个等价对；当符合条件的等价对中两个元素都存在于链表中，则把重复等价对数目自加1，同时把这个等价对从等价对表中删除；再对链表中下一个标记值在等价对表中进行搜索。一直搜索到链表中所有标记值都不在等价对表中为止，这时链表中的所有标记值标注的连通区域都属于同一个连通域，保存这个链表。然后把链表中所有标记值表示的AREA 中的points 都统一存放到一个newAREA 的points中

这个是别人说的方法，我不知道怎么具体用C++实现，没有操作过链表，刚才看了STL的list也没找到具体的实施方法