數(shù)字圖像在掃描過(guò)程中失真模型和不變提取

數(shù)字圖像在打印掃描過(guò)程中的失真模型和不變量Ching-YungLinandShih-FuChangDepartmentofElectricalEngineeringColumbiaUniversityNewYork,NY10027,{cylin,一張經(jīng)過(guò)打印掃描，通常會(huì)導(dǎo)致產(chǎn)生過(guò)濾、旋轉(zhuǎn)、縮放、剪切，對(duì)：打印，掃描，旋轉(zhuǎn)，縮放，剪切，水印1如今，打印和掃描已經(jīng)被廣泛應(yīng)用于圖像的和分發(fā)，圖像在和打 2換效果(??????)模擬的。從圖1可以看到，用戶可以隨意的選擇掃描的任一區(qū)變化會(huì)導(dǎo)致離散傅里葉系數(shù)產(chǎn)生顯著的變化。所以，相比于??????模型，??????3顏色變化感的讀者可以在文獻(xiàn)[3]中找到大量的參考文獻(xiàn)。我們的研究對(duì)象用戶平常使用的主要是基于本色調(diào)技術(shù)，他是利用人類視覺(jué)系統(tǒng)的立∑∑??[??,?? ?????,???????),

∈[?

,

],??∈

,??(??1,??2)= 101 2 2 2 0 ??01??02??1??2方向的??????（每英寸內(nèi)像素點(diǎn)的個(gè)數(shù)）值的倒數(shù)，??1和??2是圖像support點(diǎn)的范圍。然后，打印的就是原始??加上附??′(??1,??2)=??[??(??1,??2)???1(??1,??2)+(??(??1,??2)???2(??1,??2))???1]???(??1, ??(??1,：??1(??1,??2)=????(??1,??2)?????(??1, 其中????(??1,??2)是的點(diǎn)擴(kuò)散函數(shù)，????(??1,??2)是掃描儀的探測(cè)器和光點(diǎn)擴(kuò)??(??)=???(???????)??+????+ 上式包括了和掃描儀的聯(lián)合????、????和伽馬調(diào)整。??2表示噪音能量是一般情況下，掃描過(guò)程有以下步驟：首先，用戶把一張或者是原始的打印件放在掃描儀的平臺(tái)上，如果擺放的位置確的話，這一步會(huì)產(chǎn)生得到較高分辨率的掃描圖像，因?yàn)楹蛼呙鑳x的分辨率往往是不同的，這也會(huì)導(dǎo)致通過(guò)掃描儀掃描得到的的尺寸與原始圖像往往是不同的。最終掃描得到的是通過(guò)從打印失真的圖像中??????抽樣得到的，但是往往帶有額外的掃描 2(a)原始圖像；(b)旋轉(zhuǎn)和裁剪后帶有完整原始圖真的類型在圖2中進(jìn)行了展示。????= 其中??G可能表示??????????????????????????????…，其中??,??,??分別表示旋轉(zhuǎn)、縮放和裁剪。θ角，即????=????????(??1,??2)=??(??1cos?????2sin??,??1sin??+??2cos??)??(??1cos?????2sin??,??1sin??+??2cos??)=????(??1, 如果原始圖像沿??1軸縮放了??1倍，沿??2軸縮放了??2倍，即????=??????(??,??)=??(??1, ??1

)?????1??1,??2??2=??????1,相移（信息丟失相移（信息丟失 由于信息丟失所導(dǎo)致的傅里葉系數(shù)的變化可以從兩個(gè)方向進(jìn)行思考：第棄的部分?????得來(lái)的。所以就有等式：|????(??1,??2)|=|??(??1,??2)??????(??1, 在表1中進(jìn)行了表示。 0]

cos sin

] ]+[ 22和

?sin ??={ (??1???2)∈

例是一樣的。所以也只有在圖像在兩個(gè)方向上的縮放比例一樣時(shí)公式(5)才能被 3：四種計(jì)算離散傅里葉變化系數(shù)的方法，離散傅里葉變換窗口的印掃描過(guò)程在連續(xù)域的幾何失真可以用公式(9)表示，其中??1=??2。而在連續(xù)傅2快速傅里葉變換的能夠較快的計(jì)算離散傅里葉如是通過(guò)使用不帶零填補(bǔ)的原始圖像來(lái)計(jì)算離散傅里葉變換系數(shù)的。這兩種方法經(jīng)常被用來(lái)計(jì)算2??提取圖像的離散3()3((b)3()對(duì)文獻(xiàn)中 離散傅里葉變換系數(shù)的一般性，這被叫做離散時(shí)傅里葉變換系數(shù)(Discrete-TimeFourierTransform(DTFT)0大??0）5(b)說(shuō)明頻率取樣間隔(??0=1???)是由的周倍時(shí)，在5(b)和5(c)中對(duì)離散傅里葉變換因子的提取水平是一樣的，只是在信0的圖像?????的傅里葉級(jí)數(shù)系數(shù)在同一指標(biāo)下應(yīng)該是相同的，也就是說(shuō)? ,??]=??(??, ??1??1, ??1 1 2)=?? )=?? ??

)=????1, ??1其中????1,????2是縮放之后的尺寸，??1,??2是原始圖像的尺寸，加上在空間域離散化的關(guān)系，我們可以在圖像縮放的情形下得到離散傅里葉系數(shù)?????如下：????[??1, ?中看出該方法的性能，值得注意的是????或者????，因?yàn)閮蓮垐D像里的抽樣圖它們的尺寸是????1×????2，那么在進(jìn)行縮放和裁剪后的離散傅里葉系數(shù)是：| [?????]|=|???[??1,??2]+ [?????

??1 ?[?????]=?????[??1,??2]+ ????1 在公式(13)中，當(dāng)圖像裁剪的區(qū)域包括整個(gè)原始圖像即??1,??2≥1時(shí)，被丟棄小閾值要視不同的系統(tǒng)設(shè)計(jì)和特定的而定。對(duì)于公式(14)，嚴(yán)格來(lái)說(shuō)???在非整數(shù)區(qū)域是沒(méi)有定義的，但是因?yàn)???是對(duì)??抽樣得到的，我們可以根據(jù)原始圖像的傅里葉系數(shù)直接令?[??1

]=??

??1,??2??1 ??1??1129×129能夠得到應(yīng)用變得更加。在這種情況下，公式(13)和(14)里的??1和??2應(yīng)該被縮放加相移（信息丟失相移（信息丟失相移（信息丟失縮放加相移（信息丟失2：在離散空間域進(jìn)行操作后離散傅里葉系數(shù)的變化。似于圖(4)中圖像產(chǎn)生的像素不連續(xù)導(dǎo)致的。如果旋轉(zhuǎn)后的圖像包括整從圖5(b)和5(d)可以發(fā)現(xiàn)，掩碼的支撐因子和重復(fù)周期越大，旁瓣脈沖的量級(jí) 旋轉(zhuǎn)和裁剪后

5把離散傅里葉變換當(dāng)作一個(gè)頻率分析工具，我們可以使幾何失真之后的定尺（比如256256然后進(jìn)行基2快速傅里葉變（在均勻縮放的情況下，正如我們?cè)?.2.1討論的，不均勻縮放在打印掃描過(guò)程中可以跟單獨(dú)的??????有兩種方法可以用來(lái)在進(jìn)行離散傅里葉變換之前把圖像不均勻的縮放到標(biāo)]log log |????????(log??,??)|=|??(log??+log??,??+ 其中每個(gè)坐標(biāo)(??1??2)都由(??cos????sin??)代替，公式(15)可以很容易的由公式(6)和(7)化簡(jiǎn)。已知一個(gè)不均勻縮放的離散傅里葉變換系數(shù)跟連續(xù)傅里內(nèi)插法在對(duì)數(shù)極坐標(biāo)點(diǎn)中獲得系數(shù)，圖6(a)和6(b)的對(duì)數(shù)極坐標(biāo)映射展示在圖74產(chǎn)生的循環(huán)轉(zhuǎn)移的打印掃描過(guò)程中獲得一個(gè)不變的1??8所示，圖像首先被壓縮到標(biāo)準(zhǔn)尺寸（例如256×256然后零填補(bǔ)至原尺寸的（512×512（傅里葉——梅林系數(shù)：????。這些步驟的目的是使得到的|????下一步就是把從1到??間的每個(gè)角對(duì)應(yīng)的|????|的??????值加起來(lái)，這里面還需要包|????||????|值在最后的和中不會(huì)部旋0°10°或者7°沿角度計(jì)算傅里葉梅林量級(jí)的??0(??)=∑沿角度計(jì)算傅里葉梅林量級(jí)的??0(??)=∑??1(??)=??0(??)+??0(??+??(??)=??1(??)??????)????=??(??),??=??1?6我們用EPSONstylusEXInkjet和HPScanjet4C掃描儀對(duì)我們的模型分辨率為384×256的彩像,在打印后的物理尺寸是5.32’’×3,54’’，然后用75??????進(jìn)行掃描，為了驗(yàn)證關(guān)于圖像像素失真的推論，我們裁剪、縮放并估掃描圖像像素值之間的映射關(guān)系，易知公式4可以很恰當(dāng)?shù)哪M映射函數(shù)的分布。我們用最佳的估計(jì)方法來(lái)估計(jì)值為(8.3,0.6,35,20)的(??,??,????,????)。MSE的估73.58.9(d)中，我們向大家展示了原始像素和二次掃描圖像的伽馬者符合公式(2)的??1，后者滿足公式(4)的??2。在圖9(e)中我們可以看到原始圖像性模型，例如??=1，在公式(4)9(c)中我們可以看到線性回歸模型的結(jié)果，音的范圍比較大，這點(diǎn)是跟圖9(e)類似的。 9：二次掃描圖像的像素值失真。(a)384X256]，(b)二次掃描圖像廉價(jià)的用戶噴墨和掃描儀（和掃描儀不能處理??????大于300的圖不一樣。在這些情況下，這些通過(guò)這些機(jī)器得到的需要經(jīng)過(guò)用戶進(jìn)一步處理Lenna圖像[512X512]作為例子來(lái)呈現(xiàn)描述特征向量的性能，10中進(jìn)行展示，從原始圖像和失真圖像中提取的特征向量的相關(guān)始圖像的任何信息，在這些試驗(yàn)中(????????????????)=(34,100,8°,0.2，我們發(fā)現(xiàn)當(dāng)就是說(shuō)從尺寸大于128X128的縮放中提取的特征向量幾乎和從原始圖像中提取出的一樣。只有當(dāng)??0.12時(shí)，圖像的校正因子??0.610(b)JPEG壓縮的情況下測(cè)試了模型的魯棒子大于10時(shí)，??>0.947。意思是在兩個(gè)坐標(biāo)軸方向上的裁剪比例是相同的，我們選擇的裁剪因子??1??2=0.6~1，通過(guò)裁剪區(qū)間(??1??2)的比例來(lái)展示結(jié)果。不均勻裁剪指在各個(gè)坐標(biāo)剪設(shè)置??2=1，??1在區(qū)間0.6~1之間，不同的方法得到的裁剪也不一樣，這積的0.6在通常的情況下會(huì)得到比較好的效果。是這種裁剪方式不常見(jiàn)，而且在這種情況下我們可以通過(guò)再次裁剪以得到一10(e)顯示了旋轉(zhuǎn)失真的實(shí)驗(yàn)結(jié)果，圖像先旋轉(zhuǎn)一個(gè)角度(±3°)，然后裁剪，(d，(e放（??1=??2=0.4）JPEG&反差調(diào)整，(g)??????，像素失真模型(??,??,????,????)=(8.3,0.6,35,20)，噪音??2=74 幾何失真加像素值失從圖10(f)中可以看出我們模型對(duì)于由旋轉(zhuǎn)、縮放、裁剪、JPEG壓縮和反差調(diào)整聯(lián)合組成的具有非常好的魯棒性，在測(cè)試中，在±3°范圍內(nèi)旋轉(zhuǎn)，在保持最大面積下進(jìn)行嚴(yán)格裁剪即不帶有任何背景，縮放因子??1=??2=0.4，JPEG壓縮參數(shù)????=75或者反差調(diào)整參數(shù)??=1.2??=1????=0????=10。跟圖10(e)相比，我們可以發(fā)現(xiàn)特征向量的失要是由旋轉(zhuǎn)和裁剪造成的，而由JPEG壓縮、圖像增亮和反差調(diào)整產(chǎn)生的失真誤差是可以忽略不計(jì)的。我們?cè)趫D10(g)展示了RSC何像素值失結(jié)合的模型的。圖9中估計(jì)的參數(shù)被應(yīng)用于此實(shí)驗(yàn)，我們?cè)谠囼?yàn)中加了額外的高斯噪聲(??8.5)，因?yàn)閳D像的影響更大一些，與圖10(f)相比，這兩種情況的實(shí)驗(yàn)結(jié)果是類似的。我們測(cè)9(a)9(b)的實(shí)際二次掃且算得他們的校正因子??=8觀全，數(shù)像印程發(fā)改研究????操作[5]為我們的實(shí)驗(yàn)做了理論支持并且給對(duì)特征向量的驗(yàn)分析也了準(zhǔn)備，時(shí)也預(yù)了我們模型的有性。感第一作者的工作一部分由NEC支持。我們也要感謝MattMiller博士、JeffBloom博士和IngemarCox博士與我們和探討觀點(diǎn)。最后我們要感謝SareBrock對(duì)本文的校正。參考文X.Feng,J.NewellandR.Triplett,“NoiseMeasurementTechniqueforScanners,”SPIEvol.2654SolidStateSensorArraysandCCDCameras,Jan.1996.H.Wong,W.Kang,F.GiordanoandY.Yao,“PerformanceEvaluationofAHigh-QualityTDI-CCDColorScanner,”SPIEvol.1656High-ResolutionSensorsandHybridSystems,Feb1992. G.SharmaandH.Trussell,“DigitalColorImaging,”IEEETrans.onImageProcessing,Vol.6,No.7,July1997.C.-Y.Lin,“PublicWatermarkingSurvivingGeneralScalingandCrop:AnApplicationforPrint-and-ScanProcess,”MultimediaandSecurityWorkshopatACMMultimedia99,Orlando,FL,Oct.1999.C.-Y.Lin,M.Wu,M.L.Miller,I.J.Cox,J.BloomandY.M.Lui,“GeometricDistortionResilientPublicWatermarkingforImages,”SPIESecurityandWatermarkingofMultimediaContentII,SanJose,Jan2000.DistortionModelingandInvariantExtractionforDigitalImagePrint-and-ScanProcessColumbiaUniversityNewYork,NY10027,{cylin,Afteranimageisprinted-and-scanned,itisusually luminanceadjusted,aswellasdistortedbynoises.Thispaperpresentsmodelsfortheprint-and-scanprocess,consideringbothpixelvaluedistortionandgeometricdistortion.Weshowpropertiesofthediscretized,rescannedimageinboththespatialandfrequencys,thenfurther yzethechangesintheDiscreteFourierTransform(DFT)coefficients.Basedontheseproperties,weshowseveraltechniquesforextractinginvariantsfromtheoriginalandrescannedimage,withpotentialapplicationsinimage experimentsshowthevalidityoftheproposedmodelandtherobustnessoftheinvariants.:Printing,Scanning,Rotation,Scaling,Crop,WatermarkingTodaytheprint-and-scan(PS)processiscommonlyusedforimagereproductionanddistribution.Itispopulartotransformimagesbetweentheelectronicdigitalformatandtheprintedformat.Therescannedimagemaylooksimilartotheoriginal,butmayhavebeendistortedduringtheprocess.Forsomeimagesecurityapplications,suchaswatermarkingforcopyrightprotection,usersshouldbeabletodetecttheembeddedwatermarkevenifitisprinted-and-scanned.Inimageauthenticationcases,therescannedimagemaybeconsideredasauthentic,becauseitisareproductionoftheoriginal.LittleworkhasbeendonetounderstandthechangesthatdigitalimagesundergoafterthePSprocess.Mostworkdiscussesindividualmodelsofprintingorscanning.Inthispaper,webeginwiththecharacteristicsofthePSprocess.Then,inSection3,weproposeamodelthatcanbeusedtoyzethedistortionofadiscretizeddigitalimageafterthePSprocessinthespatialand.Then,wewillyzethevariationsofDFTcoefficients,leadingtoimportantpropertiesforextractinginvariants.InSection4,wediscussseveralmethodsthat

canbeusedtoextractinvariantsofthePSprocess.Someexperimentalresults,includinganysisofthefeaturevectorproposedin[5],areshowninSection5.InSection6,wemakeasummaryanddiscusssomefuturework.Propertiesoftheprint-and-scanDistortionoccursinboththepixelvaluesandthegeometricboundaryoftherescannedimage.Thedistortionofpixelvaluesiscausedby(1)theluminance,contrast,gammacorrectionandchromnancevariations,and(2)theblurringofadjacentpixels.Thesearetypicaleffectsoftheprinterandscanner,andwhiletheyareperceptibletothehumaneye,theyaffectthevisualqualityofarescannedimage.DistortionofthegeometricboundaryinthePSprocessiscausedbyrotation,scaling,andcrop(RSC).Althoughitdoesnotintroducesignificanteffectsonthevisualquality,itmayintroduceconsiderablechangesatthesignallevel,especiallyontheDFTcoefficientsoftherescannedimage.Itshouldbenotedthat,ingeneralimageeditingprocesses,geometricdistortioncannotbeadequaymodeledbythewell-knownrotation,scaling,andtranslation(RST)effects,becauseofthedesignoftoday’sGraphicUserInterface(GUI)forthescanningprocess.FromFigure1,wecanseethatuserscanarbitrarilyselectarangeforthescannedimage.Weuse“crop”todescribethisoperation,becausetherescannedimagesarecroppedfromanareainthepreviewwindow,includingtheprintedimageandbackground.TheRSTmodel,whichhasbeenwidelyusedinpatternrecognition,isusuallyusedtomodelthegeometricdistortionontheimageofanobservedobject.Inthosecases,themeaningofRSTisbasedonafixedwindowsize,whichisusuallypre-determinedbythesystem.However,inthePSprocess,thescannedimagemaycoverpartoftheoriginalpictureand/orpartofthebackground,andmayhaveanarbitrarilycroppedsize.Thesechanges,especiallythatofimagesize,willintroducesignificantchangesoftheDFTcoefficients.Therefore,insteadofRST,aRSCmodelismoreappropriatetorepresentthePSprocess.WewilldiscussthisinmoredetailinSection3.wehaveavirtualfinitesupportimage,x,whichisreconstructedfromtheoriginaldiscreteimage,x0, t[T,Tx(t,t)x[n,n](tnT,tnT 2 1 01 101 2 t[T,T 2 Figure1:Typicalcontrolwindowsofscanningprocesses.Usershavethefreedomtocontrolscanningparameters,aswellasarbitrarilycropthescannedimage.[source:MicrotekModelingoftheprint-and-scanInthissection,wefirstproposeahypotheticalofthepixelvaluedistortions.Toourknowledge,thereisnoexistingappropriatemodelintheliteraturetodescribethepixelvaluedistortionsinPSprocess.Therefore,weproposethefollowinghypotheticalmodelbasedonourexperimentsand[1][2].Althoughmoreexperimentsareneededtoverifyitsvalidity,wehavefoundthismodelisappropriateinourexperimentsusingdifferentprintersandscanners,asitshowsseveralcharacteristicsofrescannedimages.InSection3.2,weyzethegeometricdistortioninthePSprocess,andthenfocusonthechangesofDFTcoefficientsforinvariantsextraction.Thesemodelscanbeappliedtogeneralgeometric

whereTo1andTo2aretheinverseofDPI(dotsperinch)valuesinthet1andt2directions,andT1andT2aretherangeofsupportoftheimage.Then,theprintedimagewillbeaditheredversionofxwithadditionalnoises.Combiningwithscanningprocess,weassumethepixelvaluedistortioninthePSprocesscanbemodeledaswherex′(t1,t2)istheoutputdiscreteimage,Kistheresponsivityofthedetector,ands(t1,t2)isthesamplingfunction.Therearetwocomponentsinsidethebracket.Thefirsttermmodelsthesystempointspreadfunction,1(t1,t2)p(t1,t2)s(t1,t2) wherep(t1,t2)isthepointspreadfunctionofprinter,ands(t1,t2)isthedetectorandopticalpointspreadfunctionofscanner.Inthesecondterm,2isahigh-passfilter,whichisusedtorepresentthehighernoisevarianceneartheedges,andN1isawhiteGaussianrandomnoise.Thenoisepowerisstrongerinthemovingdirectionofthecarriageinscanner,becausethesteppedmotionjitterintroducesrandomsub-pixeldrift.Thisindicatesthat2isnotsymmetricinbothdirectionsInEq.(2),theresponsivityfunction,K,satisfiesthisdistortions,althoughaspecialcase(thePSprocess)isconsideredhere.

K(x)(xx

PixelvalueWeareinterestedinmodelingthevariationofluminancevaluesofcolorpixelsbeforeandafterthePSprocess,becauseweonlyuseluminanceasthemainplaceforembeddinginformation(e.g.watermarking)orextractingfeaturesinoursystem.Readerswhoareinterestedincolorvariationcanfindextensivereferencesin[3].OurfocusisonthepopularconsumerPSdevicessuchascolorinkjetprintersandflatbedscanners.Consumerprintersarebasedonhalftoning,whichexploitsthespatiallosscharacteristicsofthehumanvisualsystem.Colorhalftoneimagesutilizealargenumberofsmallcoloreddots.Varyingtherelativepositionsandareasofthedotsproducesdifferentcolorsandluminancevalues.Thelosspropertyisusuallyshowninthespreadfunctionofthescanner.Discreteimagesareconvertedtocontinuousimagesafterprinting.Inthecontinuousphysical,assume

whichincludesthecombinedAC,DCandgammaadjustmentsintheprinterandscanner.N2representsthatpowerofnoisesisafunctionofpixelvalue.Itincludesthermalnoisesanddarkcurrentnoises.ThevarianceofN2isusuallylargerondarkpixels,becausesensorsarelesssensitivetotheirlowreflectivity.Fromthismodel,wecanyzethelow-passfilteringpropertiesontheFouriercoefficientsanddescribethehighnoisevariancesinthehighbandcoefficients.SometestsofitsvalidityareshowninSection5.GeometricIngeneral,thescanningprocessfollowsacustomaryprocedure.First,auserplacesapicture(ortheprintedoriginalimage)ontheflatbedofthescanner.Ifthepictureisnotwellplaced,thisstepmayintroduceasmallorientation,orarotationof90,180or270onthescannedimagewithasmallorientation1.Then,thescannerscansthewholeflatbedtogetalow-resolutionpreviewoftheimage.Afterthisprocess,theuserselectsacropwindowtodecideanappropriaterangeofthe

reconstructedtobecontinuous,thenmanipulated,andsampledagain.Therefore,acontinuous-definitionofgeometricdistortionswillbemoreappropriate.ExamplesoftheimagesaftergeneralgeometricdistortionsareshowninFigure2.Inthissection,weproposeageneralmodel,includingmulti-stageRSCinthecontinuousspatial ,anddiscusshowtosimplifyit.WealsoshowthechangeofFouriercoefficientsafterRSC.SinceDFTisusuallyusedforfrequency- ysisofdiscreteimages,wewilldiscusstheimpactofRSCintheDFT,andthenshowhowtochooseanappropriatemethodtocalculateDFTcoefficientsforinvariantsextraction.Continuous-modelsforgeometricdistortionandthedefinitionofRSCConsideringageneralcaseofthegeometricdistortionintroducedbymultiplestagesofrotation,scaling,andcrop,thedistortedimagecanberepresentedasxG=G whereGisthegeometricdistortionoperator.Forinstance,GmayequaltoRRSCSRCSRSSC…,whereR,SandC,aretheoperatorsofrotation,scalingandcrop,respectively.WefirstshowtheindividualeffectofRSC.Iftheimageisrotatedbycounter-clockwisely,i.e.,xR=Rx,Figure2:Generalgeometricdistortionofimages:(a)rotationand withbackgroundandthewhole

x(t,t)x(tcostsin,tsintcos)FR1 X(f1cosf2sin,f1sinf2cos)XRR1 whereXistheFouriertransformof

rotationand withbackgroundandpartoftherotationand withpartoftheimage,(e)scaling,cropwithoutbackground,(g)cropwith

Iftheoriginalimageisscaledby1inthet1-axis2inthet2-axis,i.e.,xS=Sx,(h)scalingand ,and(i)rotation,scaling,and x(t,t)x(t,t)FX(f,f)X(f,f)S1 112 S1picture.Usually,itincludesonlyapartoftheoriginalimage,orthewholepicturewithadditionalbackground(a.k.a.zeropadding).Thescannerthenscansthepictureagainwithahigherresolutiontogetascannedimage.Thesizeofthisimageisusuallydifferentfromtheoriginal,becausetheresolutioninthescannerandtheprintermaybedifferent.ThefinalscanneddiscreteimageisobtainedbysamplingtheRSCversionoftheprinting-distortedimagewithadditionalscanningnoise.ImagesarediscretizedatbothendsofthePSprocess,whiletheyarecontinuousintheintermediatestagesofaprintout.Weshouldnoticethatimagesarefirst1Inourtests,thesmallorientationisnotcommon,becausepicturesor sareusuallyplacedinthecorneroftheflatbed.Eveniftheyarenotwellplaced,therotationangleisgenerallywithinasmallangle,e.g.,

Wedefinecropastheprocessthatcropstheimageinaselectedarea(whichmayincludepartofbackground)atGUIwindow.Cropintroducesthreeeffectsontheimage:(1)translationoftheoriginpointoftheimage,(2)changeofthesupportofimage,and(3)informationlossinthediscardedarea.Theycanbeconsideredasacombinationoftranslationandmasking.Itiswellknownthattranslationintroducesonlyphaseshiftinthefrequency.Maskingincludesthesecondandthethirdeffects.Inthecontinuous,theeffectofchangingsupportisnotevident,becauseFouriertransformusesaninfinitesupport,andignoresit.However,inthediscrete,changingthesupportofimagewillchangetheimagesize.ThisresultsinsignificanteffectsonDFTcoefficients.WewillfurtherdiscussitinSection3.2.2.OperationsinOperationsinthecontinuousChangePhaseshiftTable1:ChangeofFouriercoefficientsafteroperationsinthecontinuousspatial. informationlosscanbeconsideredintwoways.First,thecroppedimagecouldbeamultiplicationoftheoriginalimagewithamaskingwindow,whichintroducesblurring(withthesincfunction)intheFourier.Theothermethodistoconsiderthecroppedimage, xC,asa

subtractionofthediscardedarea,image,x.Then,thisequation,

,fromthexCx

Figure3:FourcommonmethodstocalculateDFTcoefficients.ThelengthandwidthofDFTwindoware:(a)theimage|XC(f1,f2)||X(f1,f2)XC(f1,f2) (b)afixedlargerectangle,(c)thesmallestrectanglewith2widthandheight,(d)thesmallestsquareincludingtherepresentsthecropeffectinthecontinuous.Wefindthatthesecondmethodisabetterwaytodescribethecropeffect.FromEqs.(6)~(8),wecanseethatrotationand/orscalinginthespatialresultsinrotationand/orscalinginthefrequency,respectively,whilecropintroducesphaseshiftand/orinformationloss.TheseareshowninTable1.GeometricdistortionofRSCcanalsoberepresentedbyusingcoordinatemapandmasking.Forinstance,ageometricdistortionofsinglerotation,scalingandcrop,sequentially,canbedescribedby

canEq.(5)besimplified.Or,Eq.(5)canalsobesimplified,ifrotationisnotallowed.Ifweonlyfocusonasimpleprint-and-scanprocess,thenthegeometricdistortionoftheimageisaspecialcaseofEq.(5).Themanipulationsareintheorderofrotation,scaling,andcrop.Wenoticethat,withoutdeliberateadjustment,thescalingfactorinthisprocessisusuallythesameinbothdirections.Therefore,thegeometricdistortionofPSprocessinthecontinuouscanbedescribedbyEq.(9)withthe1=2.InthecontinuousFourier,thechangesareacombinationofEqs.(6)~(8).Unlikescaling,cropusuallyresultsint1'

differentimagesizethatdoesnotkeeptheaspectratiot'0sincos

the

2 2 xx',(t1,t2

22

Discrete-modelsforgeometricWefirstdefinethegeometricdistortionsinthediscrete.Thediscretizedimageissampledfromdistortedcontinuousimage,xG.Aswehavementioned,Misamaskingfunctionandx′istheimageaftercoordinatemap.Eqs.(9)and(10)showthatRSCcanbeconsideredasRST+masking.HowtosimplifyEq.(5)?OnesolutionistoreducemultipleRSCoperationstoacombinationofsinglerotation,scaling,andcrop.First,adjacentsimilaroperations,e.g.,RRR,canberepresentedbyasingleoperation.Second,fromEq.(9),wecaneasilyverifythatRC,SCareallinter-changeable.Inotherwords,arotationoperationaftercropcanbesubstitutedbya(different)cropoperationafterrotation.WenoticethatRSisnotinter-changeableunlessthescalingfactorsint1andt2dimensionsarethesame.Therefore,onlyinthecasethatimagesarescaledwiththesameaspectratio

geometricdistortionisbetterdescribedinthe.Therefore,whenwerefertoarotateddiscreteimage,thatmeanstheimageisconvertedtothecontinuous,thenrotated,andsampledagainusingtheoriginalsamplingrate.Inpractice,discreteimagesmaynotbereallyconvertedtothecontinuous,butitispossibletouseinterpolationtoapproximatethisoperation.Thesamedefinitionappliestoscalingandcrop.Itshouldbenotedthat,becauseusingafixedsamplingrateonthescaledcontinuousimageisthesameasusingadifferentsamplingrateontheoriginalimage,“changeofsamplingrate”and“scaling”indicatethesameoperationinthediscrete-models.Itiswellknownthat,inpracticalimplementation,DFTcoefficientscanbeobtainedbyusingradix-2FFTwithzeropadding.SomeotherfastmethodsofcalculatingFigure4:DFTcoefficientsareobtainedfromtherepeatedDFTwithoutusingradix-2FFTarealsoavailable.Forexample,calculatesDFTcoefficientsbyusingthe

showstheeffectofzeropadding.Themorewepadzeroesoutsidetheimage,thesmallerthesamplingintervalinthefrequencywillbe.Usingtheseproperties,wecanmodelthechangeofDFTcoefficients,whicharecalculatedfromthefourcasesinFigure3,aftergeometricCaseI:DFTsizeequalstheimageInthefirstcase,iftheimageisscaled,thentheoriginalsizewithoutzeropadding.Oneofthetwomethodsisusuallyusedforcalculating2-DDFTofthesampledimage.TheyareshowninFigures3(a)and3(c).

Xsameindices.ThatX~[n,n]X(n,n)X(n,Figures3(b)and3(d)showsomealternatives

SX(n1,n2)~STTTTintheliterature.Allofthesemethodscanbeused obtainDFTcoefficients.However,different TTX[n1,n2methodsintroducedifferentresponsestothecoefficientsaftergeometricdistortion.Unfortunay,thisphenomenonisusuallyoverlooked.Inthefollowingparagraphs,wewillshowsomegeneralpropertiesofDFTcoefficients,andthenyzethem.

whereTS1,TS2arethesizesofthescaledimage,andT1,T2aresizesoftheoriginalimage.Addingtheconcernofdiscretizationinthespatial,wecangettheDFTcoefficientsinthescaledcase,X?asSGeneralpropertiesofDFT SWefirstshowtherelationshipsbetweencontinuousFouriercoefficientsandDFT.Onceacontinuousimageisdiscretized,itsFouriercoefficients eperiodic(andarecontinuous).TheyarecalledtheDiscrete-Time

whereX?istheDFToforiginalimage.Eq.(12)indicatesthat,afterscaling,theDFTcoefficientsateachindicesstillthesameastheoriginalwithonly(sampling)aliasingnoises.WecanseethispropertyfromFigure5(c).FourierTransform(DTFT)coefficients.Forimages,becausetheirsupportisfinite,wecanperiodicallyrepeat

shouldbenotedthatX?

X?orX?

X?,becauseitinthespatial.ThiswilldiscretizesDTFTcoefficients,andgetsDFTcoefficients.Inotherwords,DFTcoefficientsaresampledfromtheFourierspectrumoftherepeateddiscreteimage(seeFigure4).Alternatively,ifwefirstconsidertheperiodicityofanimageandthenconsideritsdiscreteproperty,DFTcoefficientswillbethesameasFourierSeries(FS)coefficients,withadditionalnoiseintroducedbyaliasingFigure5showshowDFTcoefficientschangedifferentspatialsamplingrateanddifferentDFTsize.Figure5(a)isacontinuous1DsignalanditscorrespondingFouriercoefficients.Thissignalisthendiscretized.TheDFTcoefficients(DFTwindowsizeT0)ofthediscretizedsignalarethesamplesinthe.Figure5(b)showsthatthefrequencysamplinginterval(f0=1/T0)isdeterminedbytherepetitionperiod(T0),i.e.,thesizeofDFT.ItisobviousthatDFTsizeplaysanimportantroleinthefinalcoefficients.Forexample,considerthecasewhentheDFTsizekeepsafixedratiotothesignal/imagesize.Then,inFigure5(c),ifthesignalisupsampled(orscaled)by2,wecanseethatthesamplingpositionoftheDFTcoefficientsinFigure5(b)and5(c)arethesame,withonlydifferenceinthealiasingeffect.Thisisdifferentfromthecontinuouscase,wherescalinginthecontinuousresultsinscalinginthecontinuousFourier.Figure5(d)

numbersofsamplingpointsaredifferenceinthesetfT fS Tt2T0fSFigure5:TherelationshipofDFTcoefficientsandFouriercoefficients:(a)theoriginalcontinuoussignal,(b)thediscretizedsignal(c)theup-sampledsignal(orenlargedsignalina2-Dimage),and(d)thezero-paddedsignal.OperationsinthediscreteDFTCaseAlmostOperationsinthediscreteDFTCaseAlmostScalingPhaseshift+CasePhaseshift+CasePhaseshift+loss)+CaseScalingindimensionandnoeffect*intheotherScalingPhaseshift+Inthiscase,thesizeofthecroppedimagewillbetheDFTsize.Ifweassumethissizetobe1T1x2T2,thentheDFTcoefficientsafterscalingandcropare,|X?[n,n]||X?[n,n]N?[n,n 1

SC1

1 SC1N?[n,n]X?[n,n] C1 InEq.(13),ifthecroppedareaincludetheentireoriginalimage,i.e.,12>=1,thentheeffectofthediscardedareacanbeignored.Ifthecropratiosaretoosmall,thenthepowerlossinthediscardedareamaynotbejustignoredasnoises.Thereliableminimumthresholdsthatcanbeconsideredasnoisesdependonthesystemdesignandspecificimages.InEq.(14),strictlyspeaking,thereisnodefinitioninX?atthenon-integerpositions.But,

*:Nochangesonsamplingpositionsbutmayintroducedifferentaliasingeffect.SeeEq.(12).Table2:ChangeofDFTcoefficientsafteroperationsin X?[n,n]X(n,n) TTFouriercoefficients.Inpracticalapplications,thesevaluesaregenerallyobtainedfrominterpolation.IncaseswhereDFTsizeequalsimagesize,rotationinthespatialresultsinthesamerotationinthefrequency.SeveralpropertiesofthechangeofDFTcoefficientsaftergeometricdistortionsarelistedinTable2.Intheotherthreecases,thesepropertiescanbereadilyverifiedbysimilarmethodsinthefirstcase.Thus,wewillonlydiscussthemlater.CaseII:DFTsizeisafixedlargeWhencalculatingDFT,ifthenumberofDCTcoefficientsisfixed,thenthepropertiesofRSCoperationsarethesameintheDFTandthecontinuousFourier.WecanseeitbycomparingTableIandTableII.Inthiscase,previousdiscussionsofthecontinuouscasesareallvalidintheDFT.However,thismethodisnotpracticalbecauseitrequiresaverylargefixed-sizeDFTwindowforallimages.IncaseswhereDFTsizeisafixedlargerectangle,(13)and(14)arestillapplicable,but1and2shouldbereplacedby1and2.CaseIII:DFTsizeisthesmallestrectanglewithradix-2widthandheightThethirdcaseinFigure3(c)iswidelyused,butintroducesanunpredictablescalingeffect,ifimagesizeschangeacrosstheboundaryoftworadix-2values,