前景区提取程序、前景区提取装置以及前景区提取方法

具体实施方式

下面参考附图详细描述本发明的优选实施例。下面所述的实施例是本发明应用于通过将用户所画的提示线(手绘线)用作提示，将图像划分成前景和背景，从图像中裁剪出物体区的图像编辑装置。这里，“前景”指的是显示像人物和物品那样的搜索目标的图像，而“背景”指的是除了搜索目标之外的图像。

图1是示出按照本实施例的图像编辑装置S的大概配置例子的图形。

如图1所示，图像编辑装置S包括操作单元1、显示单元2、驱动单元3、存储单元4、输入/输出接口单元5、和系统控制单元6，并且系统控制单元6和输入/输出接口单元5经由系统总线7被连接。顺便提一下，个人计算机可以用作图像编辑装置S。

操作单元1由例如键盘和鼠标组成，并接受来自用户的操作指令，并将指令的内容输出到系统控制单元6作为指令信号。

显示单元2由例如CRT(阴极射线管)显示器、液晶显示器等组成，并显示像字符和图像那样的信息。

驱动单元3从像软盘、CD(致密盘)和DVD(数字多功能盘)那样的盘状DK(记录媒介)中读出数据等，同时，将数据等记录在盘状DK(记录媒介)上。

输入/输出接口单元5进行操作单元1或存储单元4与系统控制单元6之间的接口处理。

存储单元4由例如硬盘驱动器组成，并存储操作系统(O/S)、各种程序和数据。这里，存储在存储单元4中的程序包括动态图像编辑应用程序(含有本发明的前景区提取程序)。

动态图像编辑应用程序通过记录在像CD-ROM(只读光盘存储器)那样的盘状DK上或在安装使用之前从与网络NW连接的服务器下载来提供。

系统控制单元6包括CPU(中央处理单元)6a、ROM(只读存储器)6b、和用作主存储器和图像存储器的RAM(随机访问存储器)6c。系统控制单元6通过执行进行前景区提取处理的动态图像编辑应用程序，用作显示控制部件、接受部件、分色彩空间识别部件、色彩距离计算部件、从属判断部件、成本计算部件、和确定部件。

这里，将参照图2描述前景区提取处理。

图2是示出系统控制单元6的前景区提取处理的例子的流程图。

显示在图2中的处理从例如激活动态图像编辑应用程序开始。当开始处理时，系统控制单元6使显示单元2显示运动图像中通过操作单元1指示的静止图像(步骤S1)。

接着，系统控制单元6接受包含在显示图像中的前景区中的至少一个前景像素和包含在该图像中的背景区中的至少一个背景像素的指定(步骤S2)，并且将像素登记成确定前景像素和确定背景像素(存储在RAM的登记区中)。例如，前景像素可以通过用户用鼠标在所希望前景区(物体区)中画出的提示线来指定，而背景像素可以通过用户用鼠标在所希望背景区中画出的提示线来指定。

图3是示出画在照片图像的前景区和背景区中的提示线的例子的图形。在图3中的例子中，将与提示线51重叠的多个像素指定成前景像素，而将与提示线52重叠的多个像素指定成背景像素。顺便提一下，在图3中的例子中，狗的物体区是用户所希望的前景区。如果在图3中树是用户所希望的前景区，则树的物体区变成前景区，而包括狗的其它区域变成背景区。

接着，系统控制单元6进行分色彩空间识别处理(步骤S3)。在分色彩空间识别处理中，将上面指定的至少一个前景像素和至少一个指定背景像素的每一个设置成基准像素，并且从通过划分三维RGB色彩空间产生的多个分色彩空间中识别每个基准像素所属的基准水桶(下文称为“水桶”)。

图4是示出用划分数是s的格网划分RGB色彩空间产生的水桶的图形。在图4中的例子中，示出了每种色彩的亮度从0到255的具有R(红色)、G(绿色)、和B(蓝色)三轴的RGB色彩空间，并且将R，G和B的每一种都划分成四段(s＝4)。于是，RGB色彩空间被划分成64个水桶。虽然在本例中将RGB色彩空间划分成64个水桶，但划分水桶的数量可以更多或更少。

这里，基准像素p(＝p_r，p_g，p_b)所属的水桶b(p)可以按照下面的公式(1)计算：

[数学1]

$b\left(p\right)=[\frac{p_r}{256}s,\frac{p_g}{256}s,\frac{p_b}{256}s]$

如图4所示，前景像素61所属的基准水桶62和背景像素63所属的基准水桶64用相同方式标识，基准水桶62被登记成前景集群(换句话说，被登记成前景色群)，而基准水桶64被登记成背景集群(换句话说，被登记成背景色群)(这样的聚类叫做使用水桶的聚类方法)。按照上述提示线，将各自提示线上的多个像素指定成前景像素和背景像素，并且登记各自像素所属的前景集群和背景集群。

顺便提一下，例如，在前景区中可能出现如图5所示的纹理图案(图案的延续部分)。在这样的纹理图案中，由于甚至在同一前景区中，构成纹理图案的色彩空间中的至少两种色彩之间的距离也会变大，所以难以将图像划分成前景和背景。因此，在本实施例中，如果在前景区中出现纹理图案，则以这样的方式通过用户所画的提示线73登记至少两个前景色集群，即指定与构成纹理图案的至少两种相互不同(色彩空间中色彩的距离远大于固定距离)颜色(在图5中的例子，区域71中的色彩和区域72中的色彩)的每一种相对应的前景像素。于是，即使存在纹理图案，也可以正确地将图像划分成前景和背景。

图6是示出在前景区中出现纹理图案时的登记前景色集群和背景色集群的图形。在这种情况下，如图6所示，登记了两个前景色集群，并且与构成纹理图案的每种色彩相对应的各自前景像素属于每个前景色集群。纹理图案可能出现在背景区中，在那种情况下，与前景区的情况一样，登记至少两个背景色集群。

接着，系统控制单元6确定是否存在还没有确定属于前景还是背景的像素(步骤S4)，如果存在这样的像素(步骤S4：是)，系统控制单元6转到步骤S5，如果不存在这样的像素(步骤S4：否)，因为完成了前景和背景的划分，所以系统控制单元6在终止处理之前，将前景区裁剪成用户所希望的物体区(步骤S10)。

另一方面，在步骤S5中，系统控制单元6从与基准像素(前景像素或背景像素)相邻(与上下、左右之一相邻)的相邻像素中识别还未识别的一个、两个或更多个扩大选取候选者(grow candidate)作为扩大选取候选者。

图7A、图7B和图7C是示出如何将图像中的像素确定为前景或背景的图形。在图7A中的例子中，在初始阶段识别与用户指定的前景像素81相邻的像素83和84以及与用户指定的背景像素82相邻的像素85和86作为扩大选取候选者。

接着，系统控制单元6对每个扩大选取候选者进行色彩距离计算处理(步骤S6)。在色彩距离计算处理中，计算RGB色彩空间中基准像素和与之相邻的扩大选取像素之间的色彩距离。色彩距离D(p_i，p_j)可以通过下面的公式(2)来计算：

[数学2]

D(p_i，p_j)＝‖p_i-p_j‖²

＝(p_i，r-p_j，r)²+(p_i，g-p_j，g)²+(p_i，b-p_j，b)²

其中，p_i＝(＝(p_i，r，p_i，g，p_i，b))表示扩大选取目的地像素(扩大选取候选者)，和p_j＝(＝(p_j，r，p_j，g，p_j，b))表示扩大选取源像素(基准像素)。

接着，系统控制单元6进行从属判断处理，以判断已经计算了色彩距离的扩大选取候选者属于前景色集群还是背景色集群(步骤S7)。在从属判断处理中，通过上面显示的公式(1)计算扩大选取候选者p_i所属的水桶b(p_i)。因此，按照使用水桶的聚类方法，当与例如传统k-means方法(通过对k个集群的每一个赋予代表性原型(平均值(mean))，并将每个个体指定给最接近原型进行聚类的方法)相比，可以更快地(计算量较少地)判断扩大选取候选者属于前景色集群还是背景色集群。

通过与扩大选取候选者相联系来存储指示判断结果的信息。

接着，系统控制单元6进行成本计算处理，该成本计算处理根据为扩大选取候选者计算的色彩距离D(p_i，p_j)、和基于扩大选取候选者属于为扩大选取候选者确定的前景色集群还是背景色集群的权重，为每个扩大选取候选者计算扩大选取成本(步骤S8)。扩大选取成本cost_i可以通过下面的公式(3)来计算：

[数学3]

cost_i＝c₁(p_i)·D(p_i，p_j)+C₂(pi)·cost_j

其中，C₁(p_i)和C₂(p_i)表示基于属于上述集群的权重。更具体地说，C₁(p_i)是色彩距离D(p_i，p_j)的权重，旨在处理纹理图案。另一方面，C₂(p_i)是扩大选取成本的累计条件，旨在处理后面所述的飞地。cost_j表示扩大选取源像素是扩大选取候选者时的扩大选取成本。当用户指定一个像素时，因为第一步不计算扩大选取成本，所以cost_j＝0。

C₁(p_i)通过下面的公式(4)来表示：

[数学4]

$C_1\left(p_i\right)=$

$1(p_i\in K1,p_i\notin K2)$

$2(p_i\in K1,p_i\in K2\mathrm{or}{p}_i\notin K1,p_i\notin K2)$

$4(p_i\notin K1,p_i\in K2)$

其中，当扩大选取源像素p_j是前景像素时，K1是前景色集群和K2是背景色集群，而当扩大选取源像素p_j是背景像素时，K1是背景色集群和K2是前景色集群。

按照公式(4)，当扩大选取源像素p_j是前景像素时，如果扩大选取候选者p_i只属于前景色集群，则C₁(p_i)＝1；如果扩大选取候选者p_i属于前景色集群和背景色集群两者，或既不属于前景色集群也不属于背景色集群，则C₁(p_i)＝2；和如果扩大选取候选者p_i只属于背景色集群，则C₁(p_i)＝4。另一方面，当扩大选取源像素p_j是背景像素时，如果扩大选取候选者p_i只属于背景色集群，则C₁(p_i)＝1；如果扩大选取候选者p_i属于前景色集群和背景色集群两者，或既不属于前景色集群也不属于背景色集群，则C₁(p_i)＝2；和如果扩大选取候选者p_i只属于前景色集群，则C₁(p_i)＝4。

图8是示出在图像中存在纹理图案时扩大选取成本的幅度的图形。

如图8所示，当像素从前景迁移(飞行)到前景(或从背景迁移(飞行)到背景)时，C₁(p_i)变小，导致较小的扩大选取成本，而当像素从前景迁移到背景(或反过来)时，C₁(p_i)变大，导致较高的扩大选取成本。

于是，即使存在纹理图案，也可以通过将色彩距离D(p_i，p_j)乘以权重值来把图像划分成前景和背景。

C₁(p_i)取公式(4)中的值1、2和4之一，但大小关系最重要，例如，C₁(p_i)可以取0.5、1和2的值。但是，当C₁(p_i)取1、2和4的值时，可以将扩大选取成本的计算当作整数算术来进行，并且考虑到截断误差，最好采用2的乘方。

另一方面，C₂(p_i)通过下面的公式(5)来表示：

[数学5]

C₂(p_i)＝

0(p_i∈K1)

1(否则)

按照公式(5)，当扩大选取源像素p_j是前景像素时，如果扩大选取候选者p_i只属于前景色集群，则C₂(p_i)＝0；如果扩大选取候选者p_i不只属于前景色集群，则C₂(p_i)＝1。另一方面，当扩大选取源像素p_j是背景像素时，如果扩大选取候选者p_i只属于背景色集群，则C₂(p_i)＝0；如果扩大选取候选者p_i不只属于背景色集群，则C₂(p_i)＝1。

也就是说，如果扩大选取候选者p_i显而易见地属于前景色集群或背景色集群，则C₂(p_i)＝0，因此，不累计扩大选取成本(cost_j)。另一方面，如果扩大选取候选者p_i不是显而易见地属于前景色集群或背景色集群，则C₂(p_i)＝1，因此，累计扩大选取成本(cost_j)。通过以这种方式累计扩大选取成本(cost_j)，可以正确地处理飞地。

这里，飞地指的是被前景区围住的背景区(或被背景区围住的前景区)并对应于例如环形区的中心部分。按照将提示线用作提示把图像划分成前景和背景的方法，系统控制单元6不能将例如被前景区围住的飞地识别成背景区，除非将提示线加入飞地中。因此，当扩大选取成本超过阈值T时，必需将前景和背景颠倒过来，以便使系统控制单元6可以识别飞地。阈值T可以通过下面的公式(6)来计算：

[数学6]

T＝max{D(F_b，B_d)，D(F_d，B_b)}

其中，F_b表示最大亮度的前景色，F_d表示最小亮度的前景色，B_b表示最大亮度的背景色，和B_d表示最小亮度的背景色。也就是说，阈值T是最大亮度的前景色F_b与最小亮度的背景色B_d之间的距离D(F_b，B_d)和最小亮度的前景色F_d与最大亮度的背景色B_b之间的距离D(F_d，B_b)的较大者(max)。

但是，由于在飞地的轮廓部分(例如，与前景区的边缘部分)中一般存在反混叠(轮廓部分中的模糊)，所以轮廓部分中的相邻像素之间的色彩距离较小，因此难以根据阈值T正确地将前景和背景颠倒过来。因此，在本实施例中，如上所述，通过当C₂(pi)＝1时累计扩大选取成本(cost_j)以便增大扩大选取成本，可以在飞地中正确地将前景和背景颠倒过来。

图9A和9B是示出在图像中存在反混叠时不累计扩大选取成本(图9A)和累计扩大选取成本(图9B)的比较例子的图形。

在图9A中的例子中，因为不累计扩大选取成本，所以在像素之间不会超过阈值T，而在图9B中的例子中，累计扩大选取成本，因此，从像素91迁移到像素92时的扩大选取成本可能超过阈值T。

当像上述那样计算每个扩大选取候选者的扩大选取成本时，系统控制单元6进行前景/背景确定处理，以便将所计算扩大选取成本最小的扩大选取候选者确定为前景像素或背景像素(步骤S9)。例如，将扩大选取候选者确定为与用于计算色彩距离(上述步骤S6)的基准像素相同的前景像素或背景像素(如果相邻基准像素是前景像素，则将扩大选取候选者确定为前景像素)。下文将以这种方式确定的扩大选取候选者当作新基准像素来管理。

在图7B中的例子中，对于确定为背景像素的具有最小扩大选取成本的像素85，将与像素85相邻的像素87和88标识成新扩大选取候选者。

然后，在返回到步骤S4之后，系统控制单元6确定是否存在还没有确定属于前景还是背景的像素，如果存在这样的像素(步骤S4：是)，系统控制单元6转到步骤S5。接着，系统控制单元6从与新基准像素相邻的相邻像素当中识别未标识成扩大选取候选者的像素，并且像上述那样，对扩大选取候选者进行色彩距离计算处理(步骤S6)、从属判断处理(步骤S7)、成本计算处理(步骤S8)、和前景/背景确定处理(步骤S9)。通过重复这样的处理直到不存在扩大选取候选者，一个一个地将图像中的像素确定为前景像素或背景像素，并且当如图7C所示，图像中的所有像素都确定为前景像素或背景像素时，在步骤S10中从图像中裁剪前景区作为用户所希望的物体区。

随着接近图7C中的状态，可能存在与某个扩大选取候选者相邻的多个基准像素，在这样的情况下，计算到每个基准像素的色彩距离和扩大选取成本，并且将扩大选取候选者确定为与扩大选取成本最小的基准像素相同的前景像素或背景像素。

按照本实施例，如上所述，通过识别用户指定的前景像素和背景像素所属的每个基准水桶，事先登记前景色集群和背景色集群，与前景像素或背景像素相邻的相邻像素被识别为扩大选取候选者，对每个扩大选取候选者进行通过使用水桶的聚类方法的色彩距离计算处理和从属确定处理，根据从上述处理中获得的色彩距离D(p_i，p_j)和基于扩大选取候选者属于前景色集群还是背景色集群的权重计算每个扩大选取候选者的扩大选取成本，将扩大选取成本最小的扩大选取候选者确定为前景像素或背景像素，并且重复这样的处理直到不存在扩大选取候选者，因此，可以高速地裁剪出用户所希望的物体区(前景区)。

当在前景区或背景区中出现纹理图案时，在指定构成纹理图案的至少两种相互不同色彩的每一种的像素以便登记每个集群(前景色集群或背景色集群)之后，像上述那样计算扩大选取成本，因此，即使在图像中存在纹理图案，也可以正确地将图像划分成前景和背景。

并且，通过根据上述累计条件增加扩大选取成本，即使在飞地的轮廓部分中存在反混叠，也可以在飞地中正确地将前景和背景颠倒过来。

作为利用按照本实施例的图像编辑装置S的形式，除了利用例如作为独立计算机的个人计算机之外，也可以将图像编辑装置S的配置和功能合并到在因特网上为使用提供各种信息服务的万维网服务器等中。