| 主权项 |
1. 一种基于哈密顿路径的图像式迷宫设计方法，其特征在于，所述方法在计算机中是依次按以下步骤实现的：步骤(1)：对原图像进行预处理，并求得哈密顿路径；步骤(1. 1)，把所述原图像从彩色空间转换到灰度空间，得到灰度图像，利用等比例映射的方法将该灰度图像扩缩到设定的大小，然后设定阈值将该灰度图像二值化，不断调节该阈值的大小，使二值化后的所述被扩缩了的灰度图像能够表达所述原图的主体轮廓内容；步骤(1. 2)，把步骤(1.1)得到的所述二值化后的图像分割成一个个相同大小的矩形窗口，如果所述矩形窗口内的0像素点总数与该矩形窗口内总像素点数之比达到设定的比例阈值，则将整个矩形窗口内的所有像素点都赋值为像素值0，否则赋值为像素值1，最后得到一小格化图像，首先调节所述矩形窗口的大小，使整个图像轮廓内容不丢失，然后调节所述比例阈值的大小，直到整个图像具有连通性为止，最后，对所述小格化图像进行缩放，使一个矩形窗口对应一个像素点，所述像素点的值取所述对应矩形窗口内的像素值，使得所述小格化图像变为点图；步骤(1. 3)，求出步骤(1.2)所述点图的最大连通域，对所述最大连通域内的像素点赋值为像素值0，对所述最大连通域外的像素点赋值为像素值1，确定所述最大连通域所在的矩形区域，再重新调节所述点图的大小，使该点图正好包含所述最大连通域，求所述最大连通域的步骤如下：步骤(1. 3.1)，设定0像素点表达所述点图的主体轮廓内容，用点集簇来代表所述点图的各个连通域，每个点集代表所述点图中一个连通域中的所有0像素点，初始时，所述每个点集中只包含所述点图中的一个不同的0像素点；步骤(1. 3.2)，如果一个0像素点属于另一个0像素点的4连通区域内，则称这两个像素点连通，若一个点集中存在一个像素点与另一个点集中的一个像素点连通，则这两个点集可合并，若所述点集簇中存在可合并的两个点集，则将这两个点集合并成一个点集，不断执行此操作，直到所述点集簇中不再存在可合并的两个点集，最后，所述点集簇中像素点总数最多的点集就是所求的最大连通区域；步骤(1. 4)，采用启发式哈密顿算法求出步骤(1.3)所述点图中的一条近似哈密顿路径，且必须保证该近似哈密顿路径的起点和终点所对应的像素点位于该点图的边缘，步骤为：步骤(1. 4.1)，用当前路径代表当前已被选择的像素点以及它们所对应的边，实际在计算机中，所述当前路径只需保存像素点，而无需保存它们所对应的边，从所述点图的边缘随机选取一个0像素点加入到所述当前路径中，由于此时该当前路径中只有一个像素点，则该0像素点既是该当前路径的起点，也是该当前路径的终点，将该当前路径的终点称为当前结点；步骤(1. 4.2)，用点集代表所述当前结点的4连通域内的0像素邻接点，去掉该点集中所述当前结点在所述当前路径上的紧邻像素点，如果该点集中存在未处理过的结点，则该当前路径可扩展，从该点集中选择一个度最小且未处理过的像素点，将其加入到所述当前路径的末尾，作为新的当前结点，转(1.4.2)，否则，依次按三种情况处理：1.若所述当前路径的起点存在于所述点集中，则进行圈扩展，转(1.4.2)；2.若所述点集中存在让所述当前路径进行旋转变换后可扩展的像素点，从中选择一个这样的像素点，将该当前路径进行旋转变换，该当前路径的新终点作为新的当前结点，然后转(1.4.2)：3.如果两条路径中的像素点数相同，则称两条路径等长，如果所述点集中存在一个这样的像素点，它使所述当前路径进行旋转变换后所得到的新的终点，没有在以往的等长的当前路径中作为终点出现过，则从所述点集中选取一个这样的像素点，将所述当前路径进行旋转变换，然后转(1.4.2)，否则，转(1.4.3)；步骤(1. 4.3)，步骤(1.4.2)结束后，如果所述当前路径上的像素总数等于所述点图中的0像素总数，转(14.5)，否则，将该当前路径前后调换，则原终点变为新的起点，原起点变为新的终点，新的终点作为新的当前结点，然后转(1.4.2)，如果步骤(1.4.2)结束后，所述当前路径上的像素总数等于所述点图中的0像素总数，则转(1.4.5)，否则转(1.4.4)；步骤(1. 4.4)，采用合作贪吃的方法来继续扩展所述当前路径，所述合作贪吃的方法是，假设所述当前路径上任意两个相邻的结点V1、V2，如果V1和V2横向邻接，V3、V4分别是V1、V2纵向邻接的结点，且V3和V4横向邻接，则将V3、V4一起插入V1、V2之间，如果V1和V2是纵向邻接，V3、V4分别是V1、V2横向邻接的结点，且V3和V4纵向邻接，则将V3、V4一起插入V1、V2之间，如此处理路径中的每一个相邻对，直到没有新的相邻对允许再插入当前路径中；步骤(1. 4.5)，扩展结束后，则必须将该当前路径的起点和终点转变为位于所述点图的边缘，不断对该当前路径进行旋转变换直至成功为止；步骤(2)：根据步骤(1)中求得的近似哈密顿路径，构造出以该近似哈密顿路径为解的迷宫；迷宫由一个个小矩形构成，矩形的数目M*N与步骤(1.3)所得到点图的大小一致，则步骤(1)所求得的路径中的点对应于迷宫相应位置的矩形，每个矩形的大小可根据实际需要而定，构造迷宫的步骤如下：步骤(2. 1)，首先构造一个完整迷宫，即所构成迷宫的每个矩形的四边都是完整的，点集是一个临时区域，用来临时存储所述点图中的一些像素点，path代表步骤(1)中所求得的近似哈密顿路径，path中的起点作为当前结点；步骤(2. 2)，将所述当前结点标记为已处理，并将与其4连通的像素点加入所述点集中，如果该当前结点是path中唯一的一个点，转(2.3)，否则，将该当前结点与它在path上的紧邻点所对应的两个迷宫矩形之间的边去掉，去掉path中的起点，path中新的起点作为新的当前结点转(2.2)；步骤(2. 3)，如果所述点图中所有的像素点都被标记为已处理，则转(2.4)，否则，如果所述当前结点的4连通区域中存在未处理过的像素点，则从所述当前结点的4连通区域中选取一个未处理的像素点作为继任点，并将这两个点所对应的迷宫矩形之间的边去掉，将继任点作为新的当前结点，转(2.3)，否则，从所述点集中选择一个未处理过的像素点作为当前结点，从该当前结点的4连通区域中选取一个已处理的像素点，将这两个像素点所对应的两个迷宫矩形之间的边去掉，当前结点不变，转(2.3)；步骤(2. 4)，在迷宫中，以设定的迷宫求解法求得以所述近似哈密顿路径的起点和终点分别为出口和入口的解，并对其作标志。 |
