#P1845. 影像之结构化特征
影像之结构化特征
题目描述
在影像比对中,有一种方法是利用影像中的边缘(edge)信息,计算每个边缘资讯中具有代表性的结构化特征,以作为比对两张影像是否相似的判断标准。Water-filling 方法是从每个边缘图的一个端点开始,绕着相连的边缘点走并依序编号。若走到某一步时,遇到一个以上不同的连接点,则分成不同路径同时继续走,直到没有任何连接点为止。如果一个点和另一个点为上下左右相邻,就称为连接。
例如,在图 的影像中包含三个边缘图,每个边缘图由一些互相连接的边缘点构成。图中以黑色的方块代表边缘点,白色的方块代表背景。在 Water-filling 方法中,首先,从第一行(row)开始,由左至右,由上至下,先找到第一个黑点并编号为 。接着,找 的下一个尚未编号的连接点并编号为 。依此方法继续往下一个点前进依次编号。在编号 的点之后有两个尚未编号的连接点,此时,则分为两条路线,并同时编号为 继续往下走。当走到没有任何的相连点时,则结束现有边缘图的编号,并继续对影像中的其它边缘图编号。走完图 所有边缘图后所得到的编号如图 所示。所以,走完这三个边缘图所需要的步数分别为 、 及 ;所以,、 及 可以作为代表此张影像的结构化特征。请注意:位于斜对角上的两点不能算做连接,如:
请写一个程序计算每个影像中,以 Water-filling 方法走完其中所有的边缘图后,将每个边缘图需走的步数依走访的顺序列出。
输入格式
输入文件包含一个正方形的影像。每组影像以图的宽度 开头 。接下来的 行代表影像的内容: 表示背景的白点, 表示黑色的边缘点。
输出格式
对每一个输入的影像,以 Water-filling 方法走完所有的边缘图后,先印出此张影像中共有几个边缘图。接着,将每个边缘图需走的步数按升序列出。
10
0000000000
0011110000
0000010000
0011111000
0010110100
0010010110
0011110010
0100010010
0100000110
0100000000
3
3
7
12