基于Boosting学习的图片自动语义标注

第11卷　第4期2006年4月

中国图象图形学报JournalofImageandGraphics

Vol.11,No.4

Apr.,2006

基于Boosting学习的图片自动语义标注

茹立云

马少平

路　晶

(清华大学计算机科学与技术系智能技术与系统国家重点实验室,北京　100084)

摘　要　图片自动语义标注是基于内容图像检索中很重要且很有挑战性的工作。本文提出了一种基于Boosting学习的图片自动语义标注方法,建立了一个图片语义标注系统BLIR(boostingforlinguisticindexingimageretrieval

system)。假设一组具有同一语义的图像能够用一个由一组特征组合而成的视觉模型来表示。2D2MHMM(2维多

分辨率隐马尔科夫模型)实际上就是一种颜色和纹理特殊组合的模板。BLIR系统首先生成大量的2D2MHMM模型,然后用Boosting算法来实现关键词与2D2MHMM模型的关联。在一个包含60000张图像的图库上实现并测试了这个系统。结果表明,对这些测试图像,BLIR方法比其他方法具有更高的检索正确率。

关键词　基于内容图像检索　图像语义标注　Boosting算法　2维多分辨率隐马尔科夫模型(2D2MHMM)中图法分类号:TP37　　文献标识码:A　　文章编号:100628961(2006)0420486206

Boosting2basedAutomaticLini2yun,Jing

(ofandSystem,DepartmentofComputerScienceandTechnology,

TsinghuaUniversity,Beijing100084)

Abstract　Automaticlinguisticindexingofpicturesisanimportantbuthighlychallengingproblemforresearchersincontent2basedimageretrieval.

Inthispaper,aboosting2basedautomaticlinguisticindexingapproachisproposedanda

linguisticindexingsystemcalledBLIR(BoostingforLinguisticindexingImageRetrievalsystem)isbuilt.Itisassumedthatimagesofsamesemanticmeaningcanberepresentedbyamodelcombinedwithagroupoffeatures.2D2MHMMmodelisfoundtobesuchatemplateforonespecialkindofcolorandtexturecombination,whichcorrespondstooneclusterinfeaturespace.ThusinBLIRsystem,alargenumberof2D2MHMMmodelsaregeneratedandaboostingalgorithmisusedtoassociatekeywordswithmodels.Thesystemhasbeenimplementedandtestedonaphotographicimagedatabaseofabout60000images.Resultsdemonstratetheeffectivenessoftheproposedtechniquewhichoutperformsotherapproaches.Keywords　content2basedimageretrieval,linguisticindexingofpictures,Bootstingalgorithm,two2dimensionalmulti2resolutionhiddenMarkovmodel(2D2MHMM)

1　引　言

图像检索的根本问题是一个视觉问题,即让计

算机基于语义来理解数据库中的图片,例如一张包含人物的图片,计算机要把图片中的人物、位置以及其他物体用语言文字来表述出来。如果能做到这一

步,那么现有的图像检索问题实际上就可以转化成技术已经相当成熟的文本检索问题。图片自动语义标注在基于内容图像检索和计算机物体识别中是相当重要的。它的潜在应用领域包括生物医学、商业、军事、教育、数字图书馆和网上检索等。

然而这个视觉问题在现阶段还是不可解的,因为现阶段自然语言理解、图片理解都尚未达到能够

)项目(2004CB318108);国家自然科学基金项目(60223004,60321002,60303005);教育部基金项目:国家重点基础研究发展计划(“973”

科学技术研究重大项目(104236)

收稿日期:2004211209;改回日期:2005206222

第一作者简介:茹立云(1979～　),男。2005年于清华大学计算机科学与技术系获硕士学位。主要研究方向为信息检索、机器学习等。

E2mail:lyru98@

第4期茹立云等:基于Boosting学习的图片自动语义标注　487

实用的地步。但是,图片的很多语义都是和一些颜

色,或纹理,或形状的特征相关的,把这些特征的组合称为视觉特征模型。

因此如果能够自动将与某个语义特征相对应的视觉特征模型找出来,那么图像检索就变成了利用和某个语义特征关联的模型而进行的检索。这样做将会提高基于内容的图像检索的正确率。本文提出了一种基于Boosting学习的图片自动语义标注方法,以此为基础可以得到一种基于内容图像检索系统的架构。基本思想是:首先构造很多的模型,然后在模型和概念之间建立联系,保持一种多对多关系。一个2D2MHMM(2维多分辨率隐马尔科夫模型)模型可以被看作是特征空间中的一个聚类,这样就能产生许多2D2MHMM模型,然后再用Boosting算法将概念与2D2MHMM模型建立连接。在对每个图片进行了语义标注之后,就能以关键词的方式进行检索。

的效果往往不是很好。

Li和Wang提出了一种基于统计建模方法的图片自动语义标注方法。他们用了一种在计算机视觉中用于图片分类的2维多分辨率隐马尔科夫模

[10]

型(2D2MHMM),这种模型的优势在于它可以对任一组图片建立一个统计模型。该统计模型相当于一种特定的纹理。这个方法在具有特定概念的图片上具有很好的效果。

Minka和Li的方法都是假设文字描述的概念可以用一种模型来表达的,而事实上,这种假定往往是不可靠的,因为对于一些比较复杂的概念很难用一种模型来描述。如图1所示是在Corel的图片库中人物(people)概念的表述,可以看出,这种概念是很难用一个特征组合,或者某种纹理来表达的

。

[9]

2　相关工作

域。自20世纪90年代初期以来,研究者已经开发了许多基于内容的图像检索系统。其中的大部分系统用诸如颜色、纹理、形状等特征来表示图像,检索系统主要是检索与查询图像或检索草图视觉相近的图像。然而由于图像底层特征与高层语义之间的不一致性,且由于对大量物体的识别存在很大的困难,因此这些系统一般都不具有自动给图片分配易理解的文本描述(如语义标注)的能力。然而,这个功能对于将图片和文本结合起来是很重要的,并且它能拓宽图片库可能的应用。

将图像跟单词自动关联起来是弥补上述不一致性的一个可能的解决办法。基于学习的语义标注系统首先用大量经过标注的图片来训练,再用这些经过训练

[5]

的模型来标注新的图片。Minka提出了一种基于多个模型的图片理解框架,该系统能帮助用户标出某个概念所在的区域。这个系统对于单幅图片的标注效果很好,但对于图片间的学习和标注的扩展性不是很强。

Barnard和Forsyth使用图像分割的特征来学习

[1～4]

图1　一些概念很难用单个模型来表述

Fig.1　Hardtorepresentsomeconceptwithasinglemodel

3　2维多分辨率隐马尔科夫模型

2维多分辨率隐马尔科夫模型(2D2MHMM)是一

个统计图像建模方法。它试图用统计的方法从训

练图像中学习一种“纹理”。它用一个多层(多分辨率)2维隐马尔科夫模型(2D2HMM)来对图像建立模型。不同分辨率之间的关系就像一棵四叉树,如图2所示。

在每一种分辨率下,用一个2维隐马尔科夫模型对图像建立模型。图像被分成块,假设每个块只依赖于它上方和左方的块。对每个块抽取一个特征向量,2D2HMM的状态也是特征向量,对每个状态,假设其特征向量满足高斯分布。状态通过EM(expectationmaximization)算法来计算,然后用这些状态来训练2D2HMM。概率用Viterbi算法来计算。

[11]

[10]

图片的语义。但是,由于这种做法是建立在对图

片正确分割的基础上的,而图片自动分割仍然是计

[7,8]

算机视觉领域的一个开放性问题。特别对于区域特征不明显的图片,例如人物、建筑等,这种做法

[6]

　488中国图象图形学报第11

卷

(r)

(r)

P{si,j¬(i,j)∈N

(k,l)∈N(r-1)

|sk,l

(r-1)

¬(k,l)∈N

(r-1)

(r-1)

}=

∏

P{si,j:(i,j)∈D(k,l)|sk,l

(r)

}

(r)(r-1)

其中,P{si,j:(i,j)∈D(k,l)|sk,l}可以由在条件

sk,l

(r-1)

r-1

上的转移概率来计算,表示为am,n,l(sk,l)。

()

这样就有了对父分辨率下每个可能状态的一组不同的转移概率am,n,l。先前分辨率的影响通过状态的概率分层地施加。然后式(2)中在所有分辨率下状

图2　2D2MHMM模型中块之间的空间依赖性

Fig.2　Thespatialdependencybetweenblocksin2D2MHMM

态和特征向量的联合概率被导出。

4　基于Boosting学习的图片自动语

对于多分辨率隐马尔科夫模型(MHMM),用R={1,…,R}来表示分辨率集合,其中r=R表示最精细的分辨率。设分辨率r下块的标记集合为(r)R-rR-rN={(i,j)¬0≤i<w/2,0≤j<z/2}。图像

(r)

用所有分辨率下的特征向量来描述,表示为ui,j,

r∈R。特征向量的潜在状态是si,j。在每个分辨率r下,状态集是{1

(r)

(r)

义标注

4.1　Boosting算法

算法是为了解算法的基本思想是:

(1)每个样本都赋予一个权重;

(2)T次迭代,每次迭代后,对分类错误的样本

,2

(r)

,…,Sr}。

(r)

,2D2链。,这样给定父分辨率,当前分辨率下的状态和特征就跟其他先前的分辨率条件独立,所以

(r)(r)(r)

(1)P{si,j,ui,j¬r∈R,(i,j)∈N}=

P{si,j,ui,j¬(i,j)∈N

(1)

(1)

(1)

加大权重,使得下一次的迭代更加关注这些样本。

Ada2Boosting

[12]

是一种常用的Boosting算法,

Ada指Adaptive,即这种Boosting算法具有较强的适

}×

1

|sk,l¬(k,l)∈N()(R-1)

(1)

应性。Ada2Boosting的主要思想是保持一个带有分

}×…×

(R-1)

P{si,j,ui,j¬(i,j)∈N

(2)

(2)

(2)(R)

布特征的训练数据集,每一次迭代时,都调整该数据集的分布特征,从而产生新的分类器。刚开始时,训练数据初始权重是相同的。每一次迭代,算法增加错分类的数据的权重,降低正确分类的数据权重,这样使新的分类器重点放在那些分类困难的数据上。最终的分类器由若干弱分类器加权而成,弱分类器对训练数据的分类能力越强则权重越高。4.2　用Ada2Boosting实现模型与关键词的关联

(2)¬(i,j)∈N|sk,l¬(k,l)∈N}

在最粗糙的分辨率r=1下,假设特征向量由一个单分辨率的2D2HMM产生。在更高一层的分辨率下,假设给定状态下的特征向量的条件分布是一个高斯分布。高斯分布的参数依赖于特定分辨率下的状态。

给定分辨率r-1下的状态,在更好分辨率r下,块之间的统计依赖性受兄弟块(从同一父块传下来的子块)的约束。明确地说,从不同父块传下P{si,j,ui,

(R)

(R)j

假设已经产生了很多的模型,对于区分某个关键词,即是否在某张图片上标注某个关键词,假定在某个模型下仅仅设定一个门限值就可以将两者分开。之所以选择Ada2Boosting算法,是因为(1)由于有的语义概念非常复杂,在每个模型上区分是否包含某个语义概念相当于一个弱的分类器;(2)Ada2Boosting需要的样本数不是很大。(由于语义概念很多,因此具有某个语义概念的样本数不会很多,可以对小样本进行训练是一个重要的条件)

用数据库中所有标注的关键词作为训练数据。

来的子块是条件独立的。此外,给定父块的状态,它的子块状态独立于它们的“叔伯”块(父分辨率下的非父块)的状态。兄弟块之间的状态转换由马尔科夫链的特性支配,这个特性是跟单分辨率下的2D2HMM的假设一样的。然而,状态转移概率依赖

于它们父块的状态。用公式来表示这些假设,分辨率r-1的块(k,l)在分辨率r下的子块用D(k,l)={(2k,2l),(2k+1,2l),(2k,2l+1),(2k+1,2l+1)}表示,根据假设

第4期茹立云等:基于Boosting学习的图片自动语义标注　489

基本思想是:每次从模型中挑出最能在训练集上区

分是否应该标注关键词的模型,然后利用Boosting的方法调整训练数据的权重。以此循环下去,形成模型和关键词的关联。算法如下:

输入:(X1,Y1),(X2,Y2),…,(Xn,Yn)

Yi∈{-1,+1}代表是否标有某个关键词

初始化:D1(i)=,n为训练数据个数

n

　　　其中,Zt为一个归一化分布的值。

Endfor

输出:H(X)=

αh∑

tt

t

(X)(3)

图3是用以上算法生成的框架。

fort=1,…,T

在Dt下,

对于任意模型Mi,训练得门限值fit,得到假设

+1Mi(X)>fit

hit(X)-1Mi(X)≤fit

计算错误率Eit=

i(h(Xi)≠Yi)

图3

　Ada2Boosting生成的框架

Fig.3　ArchitecturegeneratedbyAda2Boosting

∑

Dt(i)

取最佳的模型Mk,Πi,Ekt<Eit

得到弱的假设ht=hkt:Y∈{-1,+1}错误率:Et=选择αti(h(Xi)≠Yi)

∑

Dt(i)

由图3可以看出,过式(3),αt,H(X)表示,,反之则越小。

BLIR的基本思想是:首先生成大量的和语义高度相关的视觉模型,然后利用图3的学习方法把语义概念和视觉模型联系起来,再以关键词的方式进行检索,检索结果按图片标注该关键词可能性的大小进行排序。整个系统架构如图4所示。

-Et2t

Zt

Zt

a

if　ht(Xi)≠Yi,Dt+1(i)=Dt e

-a

else　ht(Xi)=Yi,Dt+1(i)=Dt e图4　BLIR图像语义标注系统架构

Fig.4　ArchitectureofBLIRsystem

5　实验与分析

5.1　实验设置

用Corel图库中600个CD2ROMs的60000张图

片作为实验数据以证明本文方法的有效性,其中每

个CD2ROMs包含100张图片,代表一组图片。每张图片都对应地标注有4个左右的关键词。把数据分成训练集和测试集,首先在训练集上得到每组图片的模型,然后对训练集进行训练得到模型和关键词

　490中国图象图形学报第11卷

的对应关系,这样利用训练后的这种对应关系就可以对测试集中的图片进行标注。利用标注后的结果可以对某个语义概念在数据库中进行检索,并评估正确率。检索结果排序按照式(3)的结果。

实验主要包括两部分,具有相关主题的图像库上的测试以及独立主题的图像库上的测试。所谓相关主题的测试库是指测试集中的图片跟训练集来自于Corel图库同一组CD2ROMs,也就是说把一组CD2ROMs的一些图片用作训练,而剩余的那些图片用作测试;而所谓完全独立主题的测试库是指测试图像来自于跟训练集没有交集的另一组CD2ROMs。5.2　实验结果从600个CD2ROMs中随机选择其中的300个CD2ROMs,并从每个CD2ROM中随机选择60张图片作为训练数据,然后将每个CD2ROM中剩余的40张图片作为第1个实验的测试数据,这样就得到一个拥有300组,每组包含60张,共计18000张图片的训练集。首先对每个CD2ROM一个2D2MHMM,,,;再用Boosting。在实验918个关键词的关键词词典。然后根据式(3)可以得到图像标注关键词词典中任一关键词的可能性大小,在检索某特定关键词的图像时可以通过该可能性的大小来排序。对于每一个语义关键词,通过看检索结果中具有该语义的图片个数来计算检索的正确率。

由于Corel图库的每个CD2ROM内图像具有相似性,该实验主要验证BLIR系统架构的可扩展性。统计对于每个关键词的前100个检索结果的正确

[9]

率,并将本文算法和Li的ALIP系统的算法进行了比较,由于ALIP系统的算法和BLIR系统采用了同样的视觉模型集合,而ALIP系统的方法在模型集合上用了贝叶斯的方法,这个实验主要说明本文机器学习方法的效果。

实验结果如图5和图6所示,其中,图5显示了在训练集上关键词的前100个检索结果的平均正确率,图6显示了在测试集上关键词的前100个检索结果的平均正确率。其中,BLIR方法是指本文BLIR系统的方法,ALIP方法是指Li和Wang的ALIP系统采用的方法。从实验结果可以看出本文方法是相当有效的。

第2

个实验是在完全独立主题的测试库上进行

图5　在训练集上关键词的前100个检索结果正确率

Fig.5　Accuracyafterthefirst100retrievedresultsfor

thekeywordsinthetraining

set

图6　在测试集上关键词的前100个检索结果正确率

Fig.6　Accuracyafterthefirst100retrievedresultsfor

thekeywordsinthetestset

的。从600个CD2ROMs中随机选择其中的300个CD2ROMs,共30000张图片作为训练集,每个CD2ROM对应地生成一个2D2MHMM模型,用另外

的300个CD2ROMs的30000张图片作为测试集。这两个集合没有交叉。同样进行如上的实验,实验结果如图7所示。

从图7中可以看出,没有主题重复的测试结果比有主题重复的结果差些。这表明了本文算法还是

图7　没有主题重复测试集上的实验结果

Fig.7　Resultsfortheirrelevanttestset

第4期茹立云等:基于Boosting学习的图片自动语义标注

imagesbycontentusingcolor,

　491

textureandshape[A].

In:

依赖于描述相同语义内容是视觉相似的这个假设

的。从图7还可以看出,本文算法依然得到了最好的结果。

ProceedingsofSPIEStorageandRetrievalforImageandVideoDatabases[C],SanJose,CA,USA,1993,1908:173～187.2　BatchJR,FullerC,GuptaA,etal.Thevirgeimagesearchengine:

anopenframeworkforimagemanagement[A].

In:Proceedingsof

SPIEStorageandRetrievalforImageandVideoDatabases[C],SanJose,CA,USA,1996,2670:76～87.

3　SmithJR,ChangSF.AnimageandvideosearchenginefortheWorld2WideWeb[A].In:ProceedingsofSPIE[C],SanJose,CA,USA,1997,3022:84～95.4　WangJZ,LiJ,WiederholdG.

SIMPLIcity:Semantics2sensitive

IEEETransactionson

integratedmatchingforpictureslibraries[J].963.

5　MinkaTP,PicardRW.

Interactivelearningusinga“societyof

models”[J].PatternRecognition,1997,30(4):565～581.6　BarnardK,ForsythD.Learningthesemanticsofwordsandpictures

[A].

In:ProceedingsofInternationComputer

on[C,～415.

7　AL.onsnakes,region

andfor2imagesegmentation[J].IonPatternAnalysisandMachineIntelligence,1996,18(9):884～900.

8　ShiJ,MalikJ.Normalizedcutsandimagesegmentation[J].IEEE

TransactionsonPatternAnalysisandMachineIntelligence,2000,22(8):888～905.

9　LiJ,WangJZ.Automaticlinguisticindexingofpicturesbya

statisticalmodelingapproach[J].

IEEETransactionsonPattern

AnalysisandMachineIntelligence,2003,25(10):14.

10LiJ,GrayRM,OlshenRA.Multiresolutionimageclassificationby

hierarchicalmodelingwithtwo2dimensionalhiddenMarkovmodels[J].

IEEETransactionsonInformationTheory,2000,46(5):

1826～1841.

11LiJ,NajmiA,GrayRM.Imageclassificationbyatwo2dimensional

hiddenMarkovmodel[J].IEEETransactionsonSignalProcessing,2000,48(2):517～533.

12FreundY.Anadaptiveversionoftheboostbymajorityalgorithm[J].MachineLearning,2001,43(3):293～318.

6　结　论

基于学习的语义标注系统首先用大量经过标注的图片来训练,再用这些经过训练的模型来标注新

的图片。将图像跟单词自动关联起来是弥补图像高层语义含义与低层特征之间不一致性的一个可能的解决办法。本文提出了一种可以用于图像自动语义标注的架构。在BLIR系统中,用分类后的图像来自动训练数百个模型,然后用boosting学习的方法,在关键词和模型之间建立起一种多对多的联系,借助每个模型的响应来实现对关键词的自动标注。在BLIR系统中选择2D2MHMM作为模型支持。在一个具有60000张图片的图库上进行了实验,并将该算法与Li中的方法进行了比较,,20%的提高,:)模型,如2D2MM,MRSAR等;(2)它能通过Adaboost算法在模型和概念之间生成一个多对多的关系,从而能够表示复杂的概念;(3)它能够提供一个

[9]

PatternAnalysisandMachineIntelligence,2001,23(9):947～

简化的图像检索界面,且具有很高的精度。

文中用单个模型来表示一组图像,但是对一些具有不同表现的复杂图像组,只用一个模型并不能有效地表示它。为了解决这个问题,将考虑采用自适应的方法来对图像组建立模型,即根据图像组的复杂性,系统会自动的判断需要多少个模型来表示它们。

参考文献(References)

1　NiblackW,BarberR,EquitzW,etal.TheQBICproject:querying

本文来源：https://www.bwwdw.com/article/b3nm.html