filevpstudio

ABenchmarkforRastertoVectorConversionSystemsIhsinT.
Phillips1andAtulK.
Chhabra21DepartmentofComputerScience/SoftwareEngineering,SeattleUniversity,Seattle,Washington98122,USAyun@seattleu.
edu2BellAtlanticNetworkSystems,AdvancedTechnologies,500WestchesterAvenue,WhitePlains,NY10604,USAatul@Basit.
COMAbstract.
ThispaperpresentsabenchmarkforevaluatingtheRastertovectorconversionsystems.
Thebenchmarkisdesignedforevaluatingtheperformanceofgraphicsrecognitionsystemsonimagesthatcontainstraightlines(solidordashed),circles(solidordashed),partialarcsofcircles(solidordashed),aswellas,boundingboxesoftextblockswithintheimages.
Thisbenchmarkgivesascientificcomparisonofvectorizationsoftwareandusespracticalperformanceevaluationmethodsthatcanbeappliedtocompletevectorizationsystems.
Threesystemswereevaluatedunderthisbenchmarkandtheirperformanceresultsarepresentedinthispaper.
Wehopethatthisbenchmarkwillhelpassessthestateoftheartingraphicsrecognitionandhighlightthestrengthsandweaknessesofcurrentvectorizationtechnologyandevaluationmethods.
Keywords:Engineering-drawing,Benchmark,PerformanceEvaluation,RasterotVectorConversion.
1IntroductionDrivenbytheneedtoconvertalargenumberofhardcopyengineeringdrawingsintoCADfiles,rastertovectorconversionhasbeenafieldofintenseresearchforthelastthreedecades.
Inadditiontoresearchprototypesinseveralacademicandindustrialresearchcenters,severalcommercialsoftwareproductsarecur-rentlyavailabletoassistusersinconvertingrasterimagestovector(CAD)files.
However,theprocessofselectingtherightsoftwareforagivenvectorizationtaskisstilladifficultone.
Althoughtrademagazineshavepublishedsurveysofthefunctionalityandeaseofuseofvectorizationproducts[1],ascientific,welldesigned,comparisonoftheauto-vectorizationcapabilityoftheproductsisnotavailable.
Respondingtothisneed,twographicsrecognitioncompetitionswereheldrecently[2,3].
Thebenchmarkwepresenthereisdesignedforevaluatingtheperformanceofgraphicsrecognitionsystemsonimagesthatcontainstraightlines(solidordashed),circles(solidordashed),partialarcsofcircles(solidordashed),aswellas,boundingboxesoftextblockswithintheimages.
(Thepreliminaryversionofthebenchmarkwepresentinthispaperwasusedin[4]competition.
)Although243theevaluator[5]weadoptedandusedinthisbenchmarkislimitedtotheabovesevenentitytypes,nevertheless,itisuseful,sinceallengineeringdrawingsuseonlyacombinationofthesegeometricelements.
Upgradingthebenchmarkisstraightforward.
Wejustneedtoprovidetheevaluatorthenewentityparameterinformationandtheperformanceevaluationcriteria.
Thisbenchmarkgivesascientificcomparisonofvectorizationsoftwareandusespracticalperformanceevaluationmethodsthatcanbeappliedtocompletevectorizationsystems.
Threesystemswereevaluatedunderthisbenchmarkandtheirperformanceresultsarepresentedinthispaper.
Wehopethatthisbench-markwillhelpassessthestateoftheartingraphicsrecognitionandhighlightthestrengthsandweaknessesofcurrentvectorizationtechnologyandevaluationmethods.
Thispaperisorganizedasfollows.
Insection3,thebenchmarkspecificationsarepresented.
Theperformanceevaluationandperformancemeasurementsaredescribedinsection4.
Theperformanceevaluationresultsofthethreesystemsaregiveninsection5.
Ourdiscussionisgiveninsection6.
2BenchmarkSpecifications2.
1OperatingPlatformsTheoperatingplatformsforthisbenchmarkarePC'srunningMicroSoftWin-dows95,SunSPARCstationsrunningSolaris2.
5.
1,andSiliconGraphicsIndyrunningIrix6.
2.
However,allparticipantschosetousePC'sandSGImachinesatthisbenchmark.
2.
2DataSetTheimagesusedinthisbenchmark(bothfortrainingandtesting)areselectedfromtheUW-IIIdocumentimagedatabase[6].
Themethodology[7,8]usedingroundtruthingimagesintheUWdocumentdatabaseserieshasbeenproventobeveryreliable,thereforeimagesinanyoftheseriesaresuitableforbench-marks.
WeselectonlyCADimagesfromtheUW-IIIdatabase.
Ourintentionofthesyntheticimageselectionwere:tokeepthebenchmarksimpleinordertoencourageparticipation,andtosatisfyourdomainconstraint:imagescanonlycontaintext,lines,arcs,andcircles.
However,theselectedimagesarecom-plex,"reallife"archiveddrawings.
Eachoftheseimageshasinthemover500objectentitiesoflines,arcs,circles,andtext.
(Wehaveremovedentitiesotherthanthesefourtypesfromtheoriginalimages.
)Someartificialdistortionswereadded,randomly,totheseselectedimages,tohelpmakethemresemblerealim-ages.
Thedistortionweresimple,suchaschangingthethicknessoflines,thelengthofdashesandgapsindashedlines,andtheorientationandsizeoftext.
Withintheselectedimages,therearefourkindsofdrawings-Mechanical,architectural,andtwodistincttypesofutilitydrawings.
Theimagesarecarefullypartitionedintotwosetssothattheimagesinthetrainingsetandthetestingsethavesimilarcharacteristics.
Figure1shownatrainingimage.
2442.
3InputandOutputSpecifications:FileFormatOnlybi-tevelimageswereusedinthisbenchmark.
TheimageswereinTIFF6.
0CCITTGroup4format.
Thesoftwareforgeneratingsyntheticimageswasbuiltusingseveralpubliclyavailablecomponents[9,10,11].
Thesoftware,severalsampleimagesandtheassociatedgroundtruth(VEC)filesweremadeavailablethroughthebenchmarkwebsite[3].
2.
4OutputSpecification:VectorFileFormatInordertomaketheevaluationsimple,wespecifiedasimplervectorfileformat(theVEC~ormat)lookslikebelow:ZVEC-I.
Oxsizeysize[dpi]LClDxlylx2y2widthACIDxcenterycenterradiusstart_angleendanglewidthCCIDxcenterycenterradiuswidthTxlylx2y2orientationfontHeightfontWidthFactorfontStrokeWidthZTEXTThefirstlineistheVECfileindicator,followsbyalistofentitydescriptions.
Thefirstletterofeachentitydescriptionstandsfortheentitytype:Lforline,Aforarc,Cforcircle,andTfortext.
Thesecondletterindicatedwetherasolid(continue)oradashedentity.
Theremainingaretheattributesofeachoftheentities.
Thex-ycoordinatesystemmusthaveitsoriginatthetopleft-handcorneroftheimagewiththeyaxispointingdownwardandthexaxispointingtotheright.
Theunitsofthexandycoordinatesshouldbeinpixels.
3PerformanceEvaluationBeforethebenchmarking,weprovidedtheparticipantsasetoftrainingimagesforthedeterminationoftheoptimalparametersoftheirsystemsoneachofthetestimagecategories.
Thetrainingimagesresemblethosetestimages.
Thepredeterminedparametersofthesystemswereusedinthisbenchmark.
Inturn,theparticipantsprovidedthebenchmarkingcommitteetheexecutablesoftheirrecognitionsoftwareandthepredetermined(trained)parametersoftheirsystemsforeachimagecategory.
Eachoftheparticipatingsystemsweretestedonthesamesetoftestimages.
Therecognitionresultofaparticipatingsystemonatestimageismatched,bytheperformanceevaluatoragainstthecorrespondinggroundtruthofthetestimage.
Thematchingresultsarethenumbersofone-to-onematches,one-to-manymatches,many-to-onematches,aswellasthenumbersoffalse-alarmsandmisses.
(Acompletedescriptionoftheevaluatorisgivenin[12].
)2453.
1PerformanceMeasurements:MetricsPerformancemeasurementsforarecognitionsystemcanbeformulated,usingalinearcombinationofsomeorallofthematchingresults:thecountsofthematches,thefalse-alarms,andthemisses.
Letone2onebethecountoftheone-to-onematches,one2manybethecountoftheone-to-manymatches,many2onebethecountofthemany-to-onematches,false_alarmbethecountofthefalse-alarms,missesbethecountofthemisses,Nbethecountoftheentitiesinthegroundtruthfile,andMbethecountoftheentitiesintheresultfile.
Wedefinethefollowingsystemperformancemeasurements:one2oneone2many-TheDetectionRate,DetectionRate=wl'~+w2"N+w3"many2oneDetectionRateis,roughly,thepercentageofthegroundtruthen-N"titiesbeingdetected.
Here,wlshouldweightmorethanthatofw2andw3sinceoneshouldfavoraone-to-onematchovertheothertwotypesofmatches.
Forthisbenchmark,w~andw2weresetto1.
-TheMisses'Rate,MissRate~ni88~sMissRateisthepercentageofthe--N"groundtruthentitieswhichwerenotdetectedbytherecognitionsystem.
NotethatDetectionRateandMissRatemaynotnecessaryadduptoone,becauseofthefactorsinvolveinthecomputationofDetectionRate.
-TheFalse-alarmRate,FalseAlarmRate=/alse_alarmFalseAlarmRateisMthepercentageofthedetectedentitiesproducedbythesystembutdonothavetheircorrespondencesinthegroundtruth.
one2one~one2many-TheRecognitionAccuracyRate,AccuracyRate=w4.
rWs"M.
.
.
.
.
"rrnany2oneAceuracyRateindicates,roughly,thepercentageofthede-w6-M"tectedentitieswithintheresultfilehavetheirmatchesinthegroundtruthentities.
Thus,onecanconsiderAccuracyRateasameasurementoftheoverallaccuracyrateofarecognitionsystem.
Again,oneshouldhavemoreweightonw4thanthatofw5andw6tofavortheone-to-onematches.
Forthisbenchmark,w4andw5weresetto1.
-ThePost-editingCost,EditingCost=wvfalse_alarms+ws.
misses+w9.
one2many+w10many2one.
EditingCostisanestimatedcostforahumanpost-editingefforttoclean-uptherecognitionresult.
ItshouldbeclearthatahigherEditingCostrequiresahigherpost-editingeffort.
Entitiesmissingfromtheresultfileneedtobeaddedandthosefalse-alarmsneedtoberemoved.
Moreover,foreachone-to-manymatch,oneneedtoremovethemany(thosepartialmatches)fromtheresultfileandaddtherealonetoit.
Andforeachmany-to-onematch,itrequiresoneremovalandmanyadditions.
Notethat,wvisthefactorforonedeletioneffortandw8isthefactorforoneinsertioneffort,thetwofactorsshouldbeweightedaccordingtothepost-editingtooloneuseforadeletionandaninsertionduringthepostcleaning.
Theweightsassigntow9andwl0aremorecomplex;theyaredependedonthemethodoneusedinthecountingofthesetwotypesofmatches.
Forexample,theevaluatorweusedinthisbenchmarkgivesonecountforaone-to-manyandonecountforamany-to-one.
Forthisbenchmark,wesetw7andwstoone,andassignedzerotobothw9andwio.
2464BenchmarkResultsandPerformanceAnalysisThreeparticipatingsystemsweretestedinthisbenchmark;twowerecommercialproductsandonecamefromanuniversity.
Thetestimagesusedinthisbench-markconsistsoffourmechanicaldrawings,onearchitecturaldrawing,twoutilitydrawingsandonestructuraldrawing,atotalofeighttestimages.
Eachofthreeparticipatingsystemsweretestedonalltheseeightimages.
Theirrecognitionre-sultswereevaluatedandthesystemperformancemeasurementswerecomputed.
Recallthattheperformanceevaluatorusesanacceptancethresholdtodeterminewhetherapairisamatch.
(Amatchiswhenthematchscoreofthepairisequalorhigherthanthisacceptancethreshold.
)Thematchingcriteriaforapairofentitiesdefinedin[5]isroughlyasimilaritymeasurement.
Whentheacceptancethresholdissethigh,theevaluatoracceptsonlythosepairsthatareverysimilar(havinghighmatchingscores).
Loweringtheacceptancethreshold,theevaluatorloweritsmatchrequirement.
Weexpectthatwithahighacceptancethreshold,onlythosesystemswithhighrecognitionprecisioncanscorehighintheirper-formancemeasurements,andforthosenot-too-goodsystems,theperformancemeasurementswouldbelow.
However,weareinterestedtoknowthetrendsofthesystemperformancewithrespecttothechangesintheacceptancethresh-old.
Ourtheoryisthatforthosehighrecognitionprecisionsystems,lowingtheacceptancethresholdvaluemayincreasetheirperformancealittle,notdras-tically.
Ontheotherhand,forthosenot-too-goodsystems,theirperformancemeasurementsmayincreasegreatlywhentheevaluator'sacceptancethresholdissetlower.
Thus,usingavariousacceptancethresholdsintheevaluationmayrevealthestabilityofarecognitionsystem.
Withtheaboveconceptsinmind,nineacceptancethresholdswereusedintheperformanceevaluation-from.
5to.
9,inthestepsof.
05.
Thatis,foreachrecognitionresultfileproducedbyasystem,weobtainedninesetsofmatch-ingcountsusingthesenineacceptancethresholds.
Thisinterm,persystem,pertestimage,wecomputedninesetsofperformancemeasurements.
Therearetotalofeighttestimagesusedinthisbenchmark.
Theresultsoftheperfor-mancemeasurementsDetectionRate,MissRate,FalseAlarmRate,Accuraeyrate,EditCostwithrespecttotheninethresholds,forthethreeparticipatingareavailableuponrequests.
4.
1AnalysisofPerformanceCharacteristicsWeareinterestedinlearningwhethertheperformancecharacteristicsofrecogni-tionsystemscanbeobservedthroughthechangesoftheevaluator'sacceptancethreshold.
Wearehappytoreportthatwedidindeedobservesomeperformancecharacteristicsoftheseparticipatingsystems.
Toillustratethetrendofchangeintheperformanceofthethreeparticipatingsystemswithrespecttothenineacceptancethresholds,weplotofthecountsofthefalse-alarmsvs.
themisses.
Duetothelimitedspace,asampleoftheplotisgiveninFigure2-4.
Figure2(3and3also)containsthreenine-pointcurves(onecurvepersystem)wheretheninepointscorrespondtotheninethresholdsused.
247Thefirstpointoneachcurvecorrespondstoathresholdof0.
5andthelastpointoneachcurvecorrespondstoathresholdof0.
9.
Weobservedthefollowings.
-Ingeneral,allthreecurvesineachoftheplotsshowupwardtrends.
Thatis,astheacceptancethresholdisincreased,allthreesystemsproducemoremissesandmorefalse-alarms.
-Ingeneral,thefirstthreeorfourpointsonmostofthecurves(theycorre-spondtothethresholdvalues0.
5,0.
55,0.
6,and0.
65)eitherformatightcluster,orhaveequalorhighercountsofmissesandfalse-alarmsthanthecountsforthepointscorrespondingto0.
65,0.
7or0.
75thresholds.
Thein-terpretationforthistrendmaybethatusinganacceptancethresholdbelow.
65doesnotyieldabetterevaluationforagivensystem.
Or,itmaybethattheperformancemeasurementsproducedbytheevaluatorusingthresholdsbelow0.
65arenotreliable(wesuspectthatwiththeacceptancethresh-oldsettoolow,theevaluatormaybemakingmatchingerrorsconsequentlyresultinginmoremissesandfalse-alarms.
)Wearecurrentlyinvestigatingthis.
-Inmostofthecases,allsystemsproducemorefalse-alarmsthanmisses.
ThismaybepartlyduetooneofthefoUowingreasons.
(1)Atpresent,theevaluatordoesnotmatchanydashedentitytoanysolidentity.
So,ifadashed-lineinatestimageisdetectedbyavectorizationsystemasseverallittlestraightlinesegments,theevaluatorproducescountsofonemiss(dashedqine)andseveralfMse-alarms(littlelinesegments.
)(2)Whenatextstringinatestimageisnotcorrectlydetectedasatextregion,itisoften'vectorized'intoseveralsmalllines,arcs,etc.
Inthiscase,theevaluatorcurrentlyproducescountsofonemiss(themissingtextstring)andseveralfalse-alarms(thelittle~vectors').
Wealsoobservedsomeperformancecharacteristicsforeachofthethreesys-tems.
Forexample,weobservedonesystemhasthesmallestincreasesinthecountsofmissesandinthecountsoffalse-alarms.
Ifwetaketheamountofin-creases,withrespecttotheincreaseintheacceptancethreshold,asanindicatorofthestabilityofasystem,thissystemwinovertheothertowbyasignificantmargin.
Thesamesystemalsoproducesmuchfewermissesthantheothertwo.
Forthefourmechanicaldrawings,thesystemwhichwasdesignedspecificformechanicaldrawingsproducesmuchfewerfalse-alarmsandfewermissesthantheothertwosystems.
Itisapparentthatcustomizingasystemforaspecifictypeofdrawingscanleadtoasignificantimprovementinperformance.
TheSystem-Chasbeendesignedspecificallyformechanicaldrawingrecognition.
ItisclearfromtheabovethatSystem-Cperformsbetteronmechanicaldrawingsthantheothertwosystems.
5DiscussionThebenchmarklimiteditselftoaquantitativeevaluationoftheautomaticvec-torizationcapabilityoftheparticipatingsystems.
Severalotherconstraintswere248imposedeitherduetolackoftimeandresourcesorinordertokeeptheevalua-tionprotocolsimple.
Theprimaryconstraintswereasfollows.
(1)Onlysyntheticbi-levelimageswereusedforbothtrainingandtesting.
(2)Theonly'noise'intheimageswasintheformofthicknessoflines,lengthofdashesandgapsindashedlines,andtheorientationandsizeoftext.
No'imagenoise'wasadded.
(3)Weonlytestedattheimageresolutionof200dotsperinch.
(4)Weonlytestedfordetectionofstraightlines,arcs,circles,andtext.
Detectionofpoly-lines,dimensioning,objects,symbols,etc.
wasnottested.
(5)Onlyonekindofdashedlinewasused.
Thiswasthesimpledash-dashline.
(6)Nomatchwasattemptedbetweendashedentitiesandsolidentities.
Therearesomeknownshortcomingsinourevaluationprocesswhichwewilladdressinthenearfuture.
Ifavectorizationsystemerroneouslyrecognizesadashedlineasasequenceofshortcontinuouslines,thenourevaluationmethodassignsasinglemissbutalargenumberoffalse-alarms(becausewedonotattempttomatchadashedlinewithcontinuouslinesegments).
Weneedtoallowmatchingofdashedlineswithseveralsmalllinesegments,butthisshouldbepenalizedsomewhatduetothefragmentationintroduced.
Ifatextregioninnotcorrectlyidentified,thenweassignasinglemissac-companiedwithalargenumberoffalse-alarms.
Thishappensbecauseifatextregionisnotcorrectlyidentified,thenthevectorizationsoftwarewillinvariablytryto'vectorize'theregion.
Theresultingshortlines('vectors')willcountasfalse-alarmsbecausewedonotattempttomatchatextareawithanyothertypeofentity.
Inordertocorrectthemisinterpretation,oneonlyneedstoboxatextregionandmarkitastext(wearenottalkingaboutOCRhere.
OCRisoutsidethescopeofthisbenchmark).
Thisisaverysimplepost-processingoperation.
Therefore,thiskindoferrorshouldnotbepenalizedsoheavily.
Gatheringdatatotestandcomparegraphicsrecognitionsystemsisverytimeconsuming.
Thisbenchmarkonlyusedsyntheticimageswithassociatedgroundtruth.
Futurebenchmarksshouldincludesyntheticimageswithimagedegradationandrealimageswithmanuallycreatedgroundtruth.
Thegraphicsrecognitioncommunityneedstocollaborateinbui]dingadatabaseofimagesandgroundtruthfiles.
Therealstrengthsandweaknessesofasystemarerevealedbystresstestingthesystem.
Wecanaccomplishthisbytestingtheperformanceofavectorizationsystemwithincreasingimagedegradationandincreasingimagecomplexity.
Thisshouldbeattemptedinafuturebenchmark.
Futurebenchmarkswillhopefullyattractparticipationfrommanymorevec-torizationsoftwarecompanies.
Allthesystemsthatwetestedinthisbenchmarkareamongthebestproductsorresearchprototypesavailableforvectorization.
Alargernumberofsystemsinthebenchmarkwillprovideusbroadertrendsandwillgiveusarealassessmentofthestateofthetechnology.
References1.
DavidByrnes.
Raster-to-vectorcomesofagewithAutoCADRelease14.
CADA-LYST,pages48-70,December1997.
2492.
R.
KasturiandI.
Phillips.
Thefirstinternationalgraphicsrecognitioncontestdashed-linerecognitioncompetition.
GraphicsRecognition:MethodsandAppli-cations,FirstInternationalWorkshop,UniversityPark,PA,USA,August1995.
3.
A.
ChhabraandI.
Phillips.
WebpagefortheSec-ondInternationalGraphicsRecognitionContest-RastertoVectorConversion.
http://graphics.
nynexst.
com/iapr-tcl0/contest.
html.
4.
ProceedingsofSecondIAPRWorkshoponGraphicsRecognition,Nancy,France,August1997.
5.
I.
Phillips,J.
Liang,andR.
Haralick.
Aperformanceevaluationprotocolforengineering-drawingrecognitionsystems.
InProceedingso]SecondIAPRWork-shoponGraphicsRecognition,pages333-346,Nancy,France,August1997.
6.
I.
Phillips.
Users'referencemanual.
CD-ROM,UW-IIIDocumentImageDatabase-III.
7.
I.
Phillips,J.
Ha,R.
Haralick,andD.
Dori.
Theimplementationmethodologyforthecd-romenglishdeocumentdatabase.
InProceedingsofthe2ndInternationalConferenceonDocumentAnalysisandRecognition(ICDAR'93),pages484-487,Tsukuba,Japan,,October1993.
8.
I.
Phillips,S.
Chen,andR.
Haralick.
Cd-romdocumentdatabasestandard.
InProceedingsofthe2ndInternationalConferenceonDocumentAnalysisan'dRecog-nition(ICDAR'93),pages478-483,Tsukuba,Japan,,October1993.
9.
VOGLE,apublicdomaindeviceportablegraphicslibrary,ftp://munnari.
oz.
au/pub/graphics/vogle.
tar.
gz.
UsedfortheHersheyfontsandthesoftwareforren-deringthefonts.
10.
SamLeffierandSiliconGraph~-";,Inc.
TIFFsoftwaredistribution.
ftp://ftp.
sgi.
com/graphics/tiff/tii~-v3.
4beta036-tar.
gz.
Usedforrenderingthetrainingandtestim-agesinTIFFCCITTGroup4format.
11.
D.
Knuth.
Theportablerandomnumbergenerator,http://www-cs-faculty.
stanford.
edu/knuth/programs.
html.
AlsopublishedinTheArtofComputerPro-gramming,Volume2/SeminumericalAlgorithms,3rdedition,section3.
6.
Addison-Wesley~Reading,MA,USA,1997.
12.
I.
Phillips,J.
Liang,R.
Haralick,andA.
Chhabra.
Aperformanceevaluationpro-tocolforgraphicsrecognitionsystems.
InK.
TombreandA.
Chhabra,editors,GraphicsRecognition:MethodsandApplications,SecondInternationalWorkshop,Nancy,France,August1997,SelectedPapers,LectureNotesinComputerScience.
Springer~Berlin,1998.
toappear.
140"2~-_~,~riL.
250l-J.
.
.
.
.
J.
llOl-1~I.
I.
Fig.
1.
Trainingimagemech.
tif(mechanicaldrawing)901308120~110E5100Z80I150200.
~3ds29.
tif:368entitiesIIIIINector-e---MDUS-~--VPstudio-+--I400450+III250300350No.
offalsealarmsFig.
2.
Performancecurvesofthesystemsfortheimageds29.
tif(imageofamechanicaldrawing)160ds30.
tif:443entities150140"E(D130"5d120Z110-ds31.
tif:627entities,Gi:[~[]IIi/VectoroMDUS-~-VPstudio-+--III+100iIi200250300350550I/fii141400450500No.
offalsealarmsFig.
3.
Performancecurvesofthesystemsfortileimageds30.
tif(imageofamechanicaldrawing)I!
.
.
fi09E"55Z2202102001901801701601502O0I7III/VectorOMDUS-E~-VPstudio-+--251fIIIIII250300350400450500No.
offalsealarmsFig.
4.
Performancecurvesofthesystemsfortheimageds31.
tif(imageofamechanicaldrawing)