边缘图像连通区域标记的算法研究和SoPC实现
连通区域标记算法用于从图像中提取目标区域,并计算目标区域的特征参数,是目标检测和目标识别的关键步骤[1],其在工业检测、光学字符识别、机器人目标跟踪等领域有广泛的应用。
目前的连通区域标记算法中,基于等价标号的标记算法需要至少扫描图像两次,并且要处理标记冲突问题,其执行时间过于依赖连通区域的复杂程度[2]。而基于区域生长的标记算法只需扫描图像一次,没有标记冲突问题,对复杂图像适应性好,但目标点数多时搜索效率低,堆栈空间消耗大。
本文所标记的图像是经过边缘检测得的二值边缘图像。相对于原始图像(或其二值图像),边缘图像保留了轮廓信息,目标点数大大减小,适合使用区域生长标记算法。但是,现有的区域生长标记算法一方面需要对每一个目标点进行N×N窗口搜索,搜索效率低并会出现同一像素重复扫描现象;另一方面,如果搜索窗口较小(如最常用的3×3,也称8邻域),虽然干扰少,但是同一个连通区很容易被标记成若干个不同的连通区;而如果增大搜索窗口(如7×7),虽然得到的标记图像连通性好,但是会引入较多干扰点。
1 基于生长算法的区域标记
像素P的上、下、左、右、左上、左下、右上、右下的像素集合为像素P的8邻域,邻域内所有目标点同属于一个连通区。通常采用8邻域生长法则进行连通区域标记。
1.1 8邻域区域生长算法
设边缘图像的背景像素为255,目标像素为0,对其进行8邻域区域生长标记的步骤如下:
(1)按从上到下、从左到右的顺序扫描图像,遇到目标像素P时,标记为新的标记值L;
(2)以P为种子点,将其8邻域内的目标像素标记为L;
(3)将所有与L像素8邻域内相邻的目标像素标记为L,直到该连通区域标记完毕;
(4)继续按顺序扫描图像,重复前三步,直到图像中所有目标像素都标记完毕。
每个连通区域的起始点是按顺序扫描整个图像得到的,而各个连通区域的标记过程是递归调用生长函数的过程。生长函数依次扫描目标点的8邻域,若遇到新的目标点,则将当前目标点的处理过程压栈,转而扫描新目标点的8邻域,如此不断地将目标点压栈。当某一目标点的8邻域内没有新的目标点,则将其弹栈,当所有目标点都弹栈完毕,则该连通区域标记完毕。
1.2 邻域重复扫描问题
在图1中,P0的8邻域和P1、P2、P3、P4的8邻域有4个像素的重叠,与P5、P6、P7、P8的8邻域有2个像素的重叠。按上述的8邻域区域生长算法,当P0与P4均为目标点时(设递归过程由P0 向P4传递),P0、P1、P8、P3、P7这5个像素点被扫描了2次;当P0与P5均为目标点时(设递归过程由P0 向P5传递),P0、P1、P2这3个像素点被扫描了2次。
1.3 8方向邻域生长算法
8方向邻域生长算法的思路是:目标点A和目标点B相邻,从A到B有8个方向,当按某个方向从A传递到B的8邻域搜索时,只搜索B的8邻域中未被A的8邻域覆盖的部分。例如,图1中从P0传递到P4的8邻域搜索时,只搜索P18、P04、P37;从P0传递到P5的8邻域搜索时,只搜索P05、P25、P01、P15、P02。即:
8方向邻域生长算法由9个生长函数组成。对于连通区域的起点,必须搜索8个方向,此时调用主生长函数。在目标点传递的过程中,按其传递方向,按式(1)调用相应的生长函数搜索邻域点。区域标记从起点调用主生长函数开始,过程是8个生长函数互相调用,最后这些函数都返回时,区域标记完毕。
该方法充分利用了从目标点A到目标点B的方向信息,从而在搜索B的邻域时,搜索个数降低为原来的3/8或5/8,平均效率提高了50%。
1.4 边缘端点与区域合并
仅用8邻域搜索连通区,往往得到的连通区域并不完整,连通性不好。图2(a)中,右半部分是圆形左下局部放大图。当按逆时针搜索到图中圆圈标识的“11”时,在其8邻域内没有新的目标点,因此也就和区域“15”断开了。当搜索到某个目标点时,其8邻域内没有新的目标点,则该点就是边缘的“末端”。一个区域可能有多个末端。
在图2(b)中,右半部分是“米”字中心局部放大图。图中圆圈标识的“4”点,其8邻域内有新的目标点(左下点),但最近的“3”点并不在其邻域内,因此两个连通区断开。对于单个像素宽的边缘图像,其走向基本一致;而走向改变较大的点,就是图形的“拐点”,此时容易出现区域断开的现象。
图1中,假设三个目标点的传递顺序是P0到P5,P5再到P02,则P5就是走向拐点。
要改善连通性,可以增大搜索范围,如增大到7×7范围。这样虽然在一定程度上改善了连通性,但是会引入更多的干扰点。而本文的思路是:首先按照上述8方向邻域生长算法搜索连通区域,同时记录边缘“端点”,然后通过比较各个区域的端点,将端点较近的两个区域合并。结合前文的分析,本文认为边缘端点包括3类:区域起点;边缘末端;边缘拐点。这样得到的端点个数少,包含了绝大部分的“断点”。通过不断比较各个区域的端点,相近则将区域合并,最终得到合并后的标记图像。
该方法实质上是在小尺度内搜索连通区,并利用得到的边缘端点在大尺度内进行区域合并,既不引入更多的杂点,又改善了标记图像的连通性,并在保证区域合并正确率的同时,提高了合并效率。
- 基于Nios II的数字音频录放系统的设计(01-08)
- 基于SOPC技术的交通事故自动处理设备(10-05)
- SOPC设计中自定义IP的开发(02-18)
- 基于SOPC技术的软件无线电系统研究(04-07)
- 基于DSP的彩色TFT-LCD数字图像显示技术研究(05-05)
- 3D集成电路将如何同时实现?(04-09)
- 婵°倕鍊瑰玻鎸庮殽閸モ晙鐒婇柛鏇ㄥ灱閺嗐儳鈧鎮堕崕鎶藉煝閼测晜鏆滈柛顐g箓閹鏌熺€涙ê濮囬柣鎾规硶閹峰顢橀悢鍛婄暚缂備礁顑呴鍛淬€冨⿰鍛晳闁跨噦鎷�
闂佺ǹ绻堥崝宥夊蓟閻斿憡濯寸€广儱鎷嬮崝鍛槈閺冨倸孝闁汇劎濮甸敍鎰板箣濠婂懐鎳囨繛鎴炴尰濮樸劑鎮¢敍鍕珰闁糕槅鍘剧粈澶愭煙缂佹ê濮囩€规洖鐭傞幆宥夊棘閸喚宀涢悗瑙勬偠閸庢壆绱為弮鍫熷殑闁芥ê顦~鏃堟煥濞戞ǹ瀚板┑顕呬邯楠炲啴濡搁妷锕€娓愰梻渚囧亞閸犳劙宕瑰鑸碘拹濠㈣埖鐡曠粈瀣归崗鍧氱細妞ゎ偄鎳橀幆鍐礋椤愩倖顔忔俊顐ゅ閸ㄥ灚瀵奸幇顔剧煓閻庯綆浜為悷锟�...
- 婵炴垶鎼╅崢鐐殽閸モ晙鐒婇柛鏇ㄥ灱閺嗐儳鈧鎮堕崕鎶藉煝閼测晜鏆滈柛顐g箓閹鏌熺€涙ê濮囬柣鎾规硶閹峰顢橀悢鍛婄暚缂備礁顑呴鍛淬€冨⿰鍛晳闁跨噦鎷�
缂備緡鍣g粻鏍焵椤掑﹥瀚�30婵犮垼鍩栧畝绋课涢鍌欑剨闁告洦鍨奸弳銉╂煕閳哄喚鏀版い鏂垮閹风娀宕滆閺屻倝鏌ㄥ☉妯侯殭缂佹鎸鹃埀顒傤攰閸╂牕顔忕捄銊﹀珰闁规儳鎳愮粈澶愭煕閺傜儤娅呮い鎺斿枛瀹曘劌螣閻戞ê娓愰梻渚囧亞閸犳洟骞撻鍫濈濡鑳堕鍗炩槈閹垮啩绨婚柟顔奸叄瀵粙鎮℃惔锝嗩啅婵☆偆澧楅崹鍨閹邦喚鐭欓悗锝庝簽閻熷酣鏌i妸銉ヮ伂妞も晪绠戞晥闁跨噦鎷�...
- Agilent ADS 闂佽桨鐒﹂悷銉╊敆閻旂厧鏄ョ痪顓炴媼閸炴煡鎮归崶褍鈷旈柍璇插悑缁鸿棄螖閸曞灚顥�
婵炴垶鎸婚幐鎼侇敊瀹ュ绠抽柛顐秵閸わ箓鏌ㄥ☉妯垮闁告瑥绻樺Λ鍐閿濆骸鏁奸柣鐔哥懐閺嬪儊S闂佸憡鑹剧€氼噣锝為幒妤€绀夐柣鏃囶嚙閸樻挳鏌涘⿰鍐濞村吋鍔楃划娆戔偓锝庝簽鐎瑰鏌i姀鈺冨帨缂侀亶浜跺畷婵嬪煛閸屾矮鎲鹃梺鐑╁亾閸斿秴銆掗崼鏇熷剹妞ゆ挾濮甸悾閬嶆煛閸愩劎鍩f俊顐ユ硶閳ь剚鍐荤紓姘辨閻у挷S...
- HFSS闁诲孩鍐荤紓姘卞姬閸曨垰鏄ョ痪顓炴媼閸炴煡鎮归崶褍鈷旈柍璇插悑缁鸿棄螖閸曞灚顥�
闁荤姍鍐仾缂佽鐒︾粙澶愬箻閹颁礁鏅欓梺鐟版惈閻楁劙顢氶幎鑺ユ櫖閻忕偠妫勫鍧楁⒒閸稑鐏辨い鏂款樀楠炴帡宕峰▎绂⊿闂佹眹鍔岀€氼剚鎱ㄥ☉銏″殑闁芥ê顦扮€氭煡骞栫€涙ɑ鈷掗柡浣靛€濋弫宥囦沪閽樺鐩庨梺鍛婃煛閺呮粓宕戝澶婄闁靛ň鏅滃銊х磼椤栨繂鍚圭紒顔芥そ瀹曠兘寮跺▎鎯уΤ婵炴垶姊绘慨鐢垫暜婢舵劕绠垫い鈥抽敪SS...
- CST閻庣敻鍋婇崰妤冧焊濠靛棭鍟呴柕澶堝€楃粙濠囨倵楠炲灝鈧洟鎮$捄銊﹀妞ゆ挾鍠愬▓宀€绱掔€n亶鍎忔い銊︾矌閹叉鏁撻敓锟�
闂佸搫顦€涒晛危閹存緷铏光偓锝傛櫅閻︽粓鎮规担绛嬪殝缂佽鲸绻堝畷妤呭Ω閳哄倹銆冮柣鐘辩瀵泛顔忕欢缍璗闂佸憡鑹剧€氫即濡村澶婄闁绘棁顕ч崢鎾煕濠婂啳瀚板ù鍏煎姉缁瑧鈧綆浜炵€瑰鏌i姀鈺冨帨缂佽鲸绻堝畷婵嬪煛閸屾矮鎲鹃棅顐㈡祩閸嬪﹪鍩€椤掑倸鏋欓柛銈嗙矌閳ь剚鍐婚梽鍕暜婢舵劕绠垫い鈥愁敍T闁荤姳鐒﹀畷姗€顢橀崨濠冨劅闁哄啫鍊归弳锟�...
- 闁诲繐绻愮€氫即銆傞崼鏇炴槬闁惧繗顕栭弨銊╂煕閳哄喚鏀版い鏂垮閹风娀宕滆閺岋拷
婵炴垶鎸稿ú锝囩箔閳ь剙螖閸屾惮鎴﹀Χ婵傚摜宓侀柛鎰级閸曢箖鎮硅閸ゆ牜妲愬┑鍥ㄤ氦婵炲棗娴烽弰鍌炴偣閸パ冣挃闁宠鍚嬬粙澶嬫姜閹殿喚鈽夐梺闈╄礋閸斿矂鎯冮悩绛圭矗闁瑰鍋涜灇闂佸搫鐗滈崹鍫曘€傞锕€鏄ラ柣鏃€鐏氭禍锝夋倶閻愬瓨绀冮悗姘辨暬閹虫ê顫濋崜褏顦梺鐟扮仛閹搁绮崨鏉戦敜婵﹩鍓涢弶浠嬫煟閵娿儱顏х紒妤佹尰缁嬪顫濋鍌氭暏缂佺虎鍘搁崑锟�...
- 閻庣敻鍋婇崰妤冧焊濠靛牅鐒婇柛鏇ㄥ灱閺嗐儲绻涢弶鎴剶闁革絾妞介獮娆忣吋閸曨厾鈻曢梺绯曟櫇椤㈠﹪顢欓崟顓熷珰闁告挆鈧弻銈夋煕濮橆剛澧︽繛澶涙嫹
闁荤姵鍔﹂崢娲箯闁秴瑙﹂柛顐犲劜閼茬娀鏌¢崶銊︾稇闁汇倕瀚伴獮鍡涙偑閸涱垳顦紓鍌氬暞閸ㄧ敻宕规惔銊ノュ〒姘e亾妞わ絽澧庨幏顐﹀矗濡搫纾块梺闈涙閼冲爼濡靛顑芥灃闁靛繒濮甸悵銈夋煏閸℃洘顦峰ǎ鍥э躬瀹曪綁鏌ㄧ€n剛鍩嶉梺鎸庣☉閺堫剟宕瑰⿰鍛暫濞达絽婀辨竟澶愭煛瀹ュ妫戠紒銊ユ健閺屽懘鏁撻敓锟�...