主权项 |
一种融合直连通约束的图像分割方法,其特征在于包括以下步骤:步骤一,添加前、背景线索;读入一幅图像后,采用鼠标、触摸屏或者手写笔等输入设备,通过在图像上勾画不同颜色的线条指定部分前、背景像素;步骤二,构造图与能量函数;图像可以表示成一个无向图G=<ν,ε>,ν为图G中的节点集合,ε为边的集合;图G中的每个节点p(p∈v)对应图像的一个像素或过分割后的超像素;假定交互式标定的部分前景像素属于集合F,背景像素属于集合B,其余像素属于集合U,则图像分割可视为一个二元标记问题,即为集合U中的每个节点分配一个唯一的标记l<sub>p</sub>∈{1,0},l<sub>p</sub>=1表示前景,l<sub>p</sub>=0表示背景;上述标记分配问题可通过最小化以下能量函数求解:<maths num="0001"><math><![CDATA[<mrow><mi>E</mi><mrow><mo>(</mo><mi>L</mi><mo>)</mo></mrow><mo>=</mo><munder><mo>Σ</mo><mrow><mi>p</mi><mo>∈</mo><mi>v</mi></mrow></munder><msub><mi>E</mi><mn>1</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>)</mo></mrow><mo>+</mo><mi>λ</mi><munder><mo>Σ</mo><mrow><mo>(</mo><mi>p</mi><mo>,</mo><mi>q</mi><mo>)</mo><mo>∈</mo><mi>ϵ</mi><mo>,</mo><msub><mi>l</mi><mi>p</mi></msub><mo>≠</mo><msub><mi>l</mi><mi>q</mi></msub></mrow></munder><msub><mi>E</mi><mn>2</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>,</mo><msub><mi>l</mi><mi>q</mi></msub><mo>)</mo></mrow><mo>+</mo><munder><mo>Σ</mo><mrow><mi>p</mi><mo>∈</mo><mi>α</mi></mrow></munder><msub><mi>E</mi><mn>3</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>)</mo></mrow><mo>-</mo><mo>-</mo><mo>-</mo><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow>]]></math><img file="FDA0001005752600000011.GIF" wi="1492" he="118" /></maths>式中,E<sub>1</sub>(l<sub>p</sub>)与E<sub>3</sub>(l<sub>p</sub>)是单元项,表示将节点p(p∈ν)标记为l<sub>p</sub>∈{1,0}时的代价,E<sub>2</sub>(l<sub>p</sub>,l<sub>q</sub>)是二元项,用于表示相邻像素分别取不同标记时的代价;λ为权重;E<sub>1</sub>(l<sub>p</sub>)、E<sub>2</sub>(l<sub>p</sub>,l<sub>q</sub>)和E<sub>3</sub>(l<sub>p</sub>)又分别称作颜色约束项、梯度约束项和直连通几何约束项;按照E<sub>1</sub>(l<sub>p</sub>)的定义,节点p的颜色与指定的前景部分的颜色相似度越大,l<sub>p</sub>取前景标记的可能性越大,即l<sub>p</sub>=1;反之亦然;按照E<sub>2</sub>(l<sub>p</sub>,l<sub>q</sub>)的定义,相邻节点间的梯度值越大,作为分割边界的可能性越大;按照E<sub>3</sub>(l<sub>p</sub>)的定义,违背直连通约束的节点将直接标记为背景;E<sub>3</sub>(l<sub>p</sub>)是强制约束,权重λ的大小对其不产生影响,λ仅用于调节E<sub>2</sub>(l<sub>p</sub>,l<sub>q</sub>)相对于E<sub>1</sub>(l<sub>p</sub>)的重要性;(1)定义颜色约束项、梯度约束项E<sub>1</sub>(l<sub>p</sub>)和E<sub>2</sub>(l<sub>p</sub>,l<sub>q</sub>);对于E<sub>1</sub>(l<sub>p</sub>),首先,通过对F和B中的像素进行K‑means聚类,得到64个前景类簇<img file="FDA0001005752600000012.GIF" wi="222" he="71" />和64个背景类簇<img file="FDA0001005752600000013.GIF" wi="250" he="70" />然后,将E<sub>1</sub>(l<sub>p</sub>)定义为:<maths num="0002"><math><![CDATA[<mfenced open = "{" close = ""><mtable><mtr><mtd><mrow><msub><mi>E</mi><mn>1</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>=</mo><mn>1</mn><mo>)</mo></mrow><mo>=</mo><mn>0</mn></mrow></mtd><mtd><mrow><msub><mi>E</mi><mn>1</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>=</mo><mn>0</mn><mo>)</mo></mrow><mo>=</mo><mi>∞</mi></mrow></mtd><mtd><mrow><mo>∀</mo><mi>p</mi><mo>∈</mo><mi>F</mi></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>E</mi><mn>1</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>=</mo><mn>1</mn><mo>)</mo></mrow><mo>=</mo><mi>∞</mi></mrow></mtd><mtd><mrow><msub><mi>E</mi><mn>1</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>=</mo><mn>0</mn><mo>)</mo></mrow><mo>=</mo><mn>0</mn></mrow></mtd><mtd><mrow><mo>∀</mo><mi>p</mi><mo>∈</mo><mi>B</mi></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>E</mi><mn>1</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>=</mo><mn>1</mn><mo>)</mo></mrow><mo>=</mo><msub><mi>f</mi><mn>1</mn></msub><mrow><mo>(</mo><msubsup><mi>D</mi><mi>p</mi><mi>F</mi></msubsup><mo>,</mo><msubsup><mi>D</mi><mi>p</mi><mi>B</mi></msubsup><mo>)</mo></mrow></mrow></mtd><mtd><mrow><msub><mi>E</mi><mn>1</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>=</mo><mn>0</mn><mo>)</mo></mrow><mo>=</mo><msub><mi>f</mi><mn>0</mn></msub><mrow><mo>(</mo><msubsup><mi>D</mi><mi>p</mi><mi>F</mi></msubsup><mo>,</mo><msubsup><mi>D</mi><mi>p</mi><mi>B</mi></msubsup><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mo>∀</mo><mi>p</mi><mo>∈</mo><mi>U</mi></mrow></mtd></mtr></mtable></mfenced>]]></math><img file="FDA0001005752600000014.GIF" wi="1077" he="255" /></maths><maths num="0003"><math><![CDATA[<mrow><msub><mi>f</mi><mn>1</mn></msub><mrow><mo>(</mo><msubsup><mi>D</mi><mi>p</mi><mi>F</mi></msubsup><mo>,</mo><msubsup><mi>D</mi><mi>p</mi><mi>B</mi></msubsup><mo>)</mo></mrow><mo>=</mo><mfrac><msubsup><mi>D</mi><mi>p</mi><mi>F</mi></msubsup><mrow><msubsup><mi>D</mi><mi>p</mi><mi>F</mi></msubsup><mo>+</mo><msubsup><mi>D</mi><mi>p</mi><mi>B</mi></msubsup></mrow></mfrac></mrow>]]></math><img file="FDA0001005752600000015.GIF" wi="486" he="149" /></maths><maths num="0004"><math><![CDATA[<mrow><msub><mi>f</mi><mn>0</mn></msub><mrow><mo>(</mo><msubsup><mi>D</mi><mi>p</mi><mi>F</mi></msubsup><mo>,</mo><msubsup><mi>D</mi><mi>p</mi><mi>B</mi></msubsup><mo>)</mo></mrow><mo>=</mo><mfrac><msubsup><mi>D</mi><mi>p</mi><mi>B</mi></msubsup><mrow><msubsup><mi>D</mi><mi>p</mi><mi>F</mi></msubsup><mo>+</mo><msubsup><mi>D</mi><mi>p</mi><mi>B</mi></msubsup></mrow></mfrac></mrow>]]></math><img file="FDA0001005752600000016.GIF" wi="490" he="151" /></maths>式中,<img file="FDA0001005752600000021.GIF" wi="184" he="72" />分别表示像素p到前、背景颜色分布的距离,其表达式分别为:<maths num="0005"><math><![CDATA[<mrow><msubsup><mi>D</mi><mi>p</mi><mi>F</mi></msubsup><mo>=</mo><munder><mrow><mi>m</mi><mi>i</mi><mi>n</mi></mrow><mrow><mi>k</mi><mo>=</mo><mn>1</mn><mo>,</mo><mn>..</mn><mo>,</mo><mn>64</mn></mrow></munder><mo>|</mo><mo>|</mo><msub><mi>C</mi><mi>p</mi></msub><mo>-</mo><msubsup><mi>C</mi><mi>k</mi><mi>F</mi></msubsup><mo>|</mo><mo>|</mo></mrow>]]></math><img file="FDA0001005752600000022.GIF" wi="469" he="95" /></maths><maths num="0006"><math><![CDATA[<mrow><msubsup><mi>D</mi><mi>p</mi><mi>B</mi></msubsup><mo>=</mo><munder><mrow><mi>m</mi><mi>i</mi><mi>n</mi></mrow><mrow><mi>k</mi><mo>=</mo><mn>1</mn><mo>,</mo><mn>..</mn><mo>,</mo><mn>64</mn></mrow></munder><mo>|</mo><mo>|</mo><msub><mi>C</mi><mi>p</mi></msub><mo>-</mo><msubsup><mi>C</mi><mi>k</mi><mi>B</mi></msubsup><mo>|</mo><mo>|</mo></mrow>]]></math><img file="FDA0001005752600000023.GIF" wi="466" he="86" /></maths>E<sub>2</sub>(l<sub>p</sub>,l<sub>q</sub>)定义为:<maths num="0007"><math><![CDATA[<mrow><msub><mi>E</mi><mn>2</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>,</mo><msub><mi>l</mi><mi>q</mi></msub><mo>)</mo></mrow><mo>=</mo><mfrac><mn>1</mn><mrow><mn>1</mn><mo>+</mo><msubsup><mi>D</mi><mrow><mi>p</mi><mo>,</mo><mi>q</mi></mrow><mn>2</mn></msubsup></mrow></mfrac></mrow>]]></math><img file="FDA0001005752600000024.GIF" wi="435" he="135" /></maths>式中,D<sub>p,q</sub>=||C<sub>p</sub>‑C<sub>q</sub>||表示节点p和q之间的颜色差;C<sub>p</sub>、C<sub>q</sub>分别表示节点p和q的颜色值;<img file="FDA0001005752600000025.GIF" wi="190" he="63" />分别表示前景类簇和背景类簇中第k个类簇的颜色值;(2)定义直连通几何约束项E<sub>3</sub>(l<sub>p</sub>)直连通几何约束项的定义也是基于用户输入的线条,其基本原理是:如果像素p被背景线遮住,对于任意前景线的中心点不可见,则认为p违背直连通约束,将p直接标记为背景,即l<sub>p</sub>=0;E<sub>3</sub>(l<sub>p</sub>)定义为:<maths num="0008"><math><![CDATA[<mrow><msub><mi>E</mi><mn>3</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>=</mo><mn>1</mn><mo>)</mo></mrow><mo>=</mo><mi>∞</mi><mo>,</mo><msub><mi>E</mi><mn>3</mn></msub><mrow><mo>(</mo><msub><mi>l</mi><mi>p</mi></msub><mo>=</mo><mn>0</mn><mo>)</mo></mrow><mo>=</mo><mn>0</mn><mo>,</mo><mo>∀</mo><mi>p</mi><mo>∈</mo><mi>α</mi></mrow>]]></math><img file="FDA0001005752600000026.GIF" wi="773" he="66" /></maths>该约束项规定位于α区域内的像素被硬性判定为背景像素;区域α定义为被遮挡区域,即对于任意前景线条中心点,区域α内部的节点均不可见;在只有一条背景线和一条前景线的情况下,将标记的前景线的中心点表示为O,将背景线的起点和终点分别记为X和Y,射线OX和OY围成了一片向外扩张的扇形区域,直线XY将扇形区域进一步分成了两部分α和β;对于任意一个像素点p,判断其是否属于α区域的方法如下:1)若∠XOY>∠pOX且∠XOY>∠pOY,则p∈α∪β,即射线OX与射线OY围成的扇形区域;2)如果p∈α∪β,且∠pYO>∠XYO,则p∈α,即像素p属于α区域;在同一幅图像上,对于M条前景线和N条背景线,叠加后的α区域可表示为:α=(α<sub>11</sub>∪α<sub>12</sub>∪...∪α<sub>1n</sub>∪...∪α<sub>1N</sub>)∪(α<sub>21</sub>∪α<sub>22</sub>∪...∪α<sub>2n</sub>∪...∪α<sub>2N</sub>)∪...∪(α<sub>M1</sub>∪α<sub>M2</sub>∪...∪α<sub>mn</sub>∪...∪α<sub>MN</sub>)式中,α<sub>mn</sub>表示第m条前景线条与第n条背景线条所形成的被遮挡区域;步骤三,采用图割算法求能量函数的最优解;采用Y图割算法求能量函数(1)的最优解,得到分割结果;如对分割效果不满意,可返回步骤一,继续添加前、背景线索;每添加一条线条,无论是为了指定部分前景还是背景,都将触发一次融合直连通约束的分割过程。 |