Unsupervised segmentation controlled by morphological contrast ext

UNSUPERVISED IMAGE SEGMENTATION CONTROLLED BY MORPHOLOGICAL CONTRAST EXTRACTION Fe an MARQUES, Jo di CUNILLERA, An oni GASULL Dep . Teo ia de la Seiial y Comunicaciones E.T.S.E.T.B. - U.P.C. Apdo. 30002 08071 Ba celona, SPAIN e-mail: e an@ sc .upc.es ABSTRACT A no el app oach o unsupe ised image segmen a ion is desc ibed in his pape . This app oach makes use o a Gaussian py amid as mul i esolu ion decomposi ion o analyse images. Compound andom ields a e used o model images a each esolu ion. The hie a chical image model is o med by a S auss p ocess in he lowe le el and a se o whi e Gaussian andom ields in he uppe le el. This basic image model is adap ed o he da a p esen a each esolu ion. Segmen a ions a coa se esolu ions a e used o guide segmen a ions a ines esolu ions. Segmen a ion quali y is con olled, a each le el, by means o mo phological ools. The con ol p ocedu e is based on he esidue be ween he o iginal image and a mo phological cen e ans o m. This p ocedu e checks whe he he cu en segmen a ion con ains all he ele an egions in he scene. I no , he algo i hm in oduces seeds in o he segmen ed image in o de o de ec he new egions. I.- INTRODUCTION Compound Random Fields (CRFs) [1,2] a e nowadays widely used in image p ocessing. Wi hin he amewo k o image segmen a ion, se e al me hods ha e been p oposed elying on such a kind o image models. These me hods a e ei he e y ime demanding [3], i hey use s ochas ic maximisa ion echniques, o e y depending on he ini ial segmen a ion [4], i hey use de e minis ic maximisa ion app oaches. In o de o dec ease he dependency on he ini ial segmen a ion o de e minis ic app oaches, mul iple esolu ion analyses ha e been in oduced in he segmen a ion p ocedu e [5,6]. In hese echniques, coa se esolu ion segmen a ions guide he me hod o be e esul s when segmen ing ines esolu ion images. Howe e , mul i esolu ion echniques s ill a ise some p oblems. In his pape , an unsupe ised mul i esolu ion segmen a ion echnique based on compound andom ields and con olled by ma hema ical mo phology ools is p esen ed. The s uc u e o he This wo k has been pa ially suppo ed by he p ojec TIC-92-0800-COS-03 o he Spanish Go e nmen pape is as ollows. A e his b ie in oduc ion, in Sec ion 11, he basic mul i esolu ion segmen a ion scheme p esen ed in [6] and i s main d awbacks a e p esen ed. Sec ion I11 deals wi h he unsupe ised adap a ion o he model pa ame e s o he da a in he image, in o de o imp o e he pe o mance o he segmen a ion echnique. Sec ion IV p esen s a mo phological s age in oduced o de ec in e io egions. Once an in e io egion has been de ec ed, he p e ious echnique decides whe he his new egion dese es o be included in o he inal segmen a ion. Finally, Sec ion V is de o ed o he p esen a ion o some esul s and conclusions. II.- BASIC MULTJRESOLUTION SCHEME In his sec ion, he mul i esolu ion segmen a ion echnique p esen ed in [6] is ou lined o comple eness pu poses. This echnique makes use o a Gaussian py amid as mul i esolu ion decomposi ion. Mo eo e , i elies on CRFs o model images a each esolu ion. The CRF uppe le el X ( ex u e model) is o med by a se o independen whi e Gaussian andom ields. On i s u n, he CRF lowe le el Q (con ou model) is assumed o be a S auss p ocess [7] de ined on a second o de neighbou hood. Pa ame e s cha ac e ising he ex u e model a e es ima ed om he image da a. The con ou model pa ame e s a e ixed o he whole segmen a ion p ocedu e. These ixed alues a e ob ained om an analysis o hei in luence on he inal segmen a ions esul s [8]. The segmen a ion p ocedu e s a s by segmen ing he coa ses esolu ion in he Gaussian py amid. Once he image a a esolu ion (k) is segmen ed, his esul is used as ini ial segmen a ion o he nex ine esolu ion (k-1). This p ocedu e is i e a ed down o he ines esolu ion ( he image i sel ) is segmen ed. In his way, coa se esolu ion segmen a ions lead he p ocedu e o good quali y inal segmen a ions. Mul iple esolu ion decomposi ions allow o achie e good quali y esul s when using de e minis ic maximisa ion echniques a each esolu ion. Tha is, he dependency o de e minis ic app oaches on he ini ial segmen a ions is almos comple ely emo ed by mul i esolu ion analyses. V-17 0-7803-0946-4/93 $3.00 0 1993 IEEE A each esolu ion le el, he mono esolu ion segmen a ion echnique p oposed in [4] is used. Tha is. he segmen a ion a each le el is pe o med by seeking he pa i ion Q(k) o he image X(k) which maximises he p obabili y P(Q(k)/X(k)). This esul can be achie ed by maximising P(X(k), Q(k)): 1 P(X(k),Q(k)) = Z exp (- T (nl(k)V1 + n2(k)V2)) . .nP(xn(k) / mn(k), 02 (1) n whe e Z is a no malising cons an , T s ands o he empe a u e, nl(k) and n2(k) a e he numbe o cliques in he pa i ion o he le el (k) wi h po en ial V1 and V2 espec i ely [4], and mn(k) and On(k) a e he pa ame e s o he Gaussian andom ield cha ac e ising he egion n. The maximisa ion p ocedu e is ca ied ou by a p og essi e bounda y e inemen o he ini ial segmen a ion. This echnique yields good quali y segmen a ion esul s [6]. Howe e , inal segmen a ions may o e look de ails in he o iginal image. The -on o his lack o de ail is mainly wo old. Fi s , he use o he same pa ame e s o cha ac e ise images h ough he whole decomposi ion does no comple ely exploi he possibili ies o he mul i esolu ion analysis. In addi ion, gi en ha he maximisa ion elies on a bounda y e inemen p ocedu e, o ally in e io egions ( ha is, egions whose con ou s do no ouch o he con ou egions) which a e no p esen in he ini ial segmen a ion canno be de ec ed by his segmen a ion echnique. III.- XMAGE MODEL ADAPTATXON Image da a a di e en decomposi ion le els do no sha e he same ea u es, due o he il e ing p ocedu e in ol ed in he compu a ion o he Gaussian py amid. Thus, di e en model pa ame e s should be used in o de o cha ac e ise he da a a di e en decomposi ion le els. Since uppe le el pa ame e s a e al eady cons an ly upda ed in he basic mul i esolu ion scheme, only lowe le el model pa ame e s ha e o be adap ed. The h ee pa ame e s used in (1) o modelling he lowe le el can be educed o only wo: Ac ually, only he T* pa ame e adap a ion esul s in an imp o emen o he p ocedu e pe o mance [SI. This pa ame e con ols he ela ionship be ween he lowe le el model and he uppe le el model in he CRF. In o de o adap i s alue o he da a con ained a each esolu ion, he in o ma ion o he Laplacian py amid is in oduced in o he p ocedu e. Each le el o he Laplacian py amid (k) con ains he di e ence be ween wo consecu i e le els o he Gaussian py amid. Assuming ha le el (k+l) has been co ec ly segmen ed, he in o ma ion con ained in he le el (k) o he Laplacian py amid gi es an es ima ion o how a his segmen a ion is om ha o le el (k). Tha is, i mos o he pixels a le el (k) o he Laplacian py amid ha e ze o alue, segmen a ion a le el (k+l) o he Gaussian py amid is e y close o ha a le el (k). On he o he hand, o ha e se e al pixels wi h high alues in he Laplacian le el ansla es in o he necessi y o pe o ming se e al co ec ions in he segmen a ion o le el (k+l) so ha he segmen a ion o le el (k) is ob ained. Tha is, new egions ha e o be de ec ed and con ou s ha e o be e ined in o de o con o m o hose o le el (k). The way o ca y ou such asks is by gi ing p io i y o he ex u e in o ma ion wi h espec o he con ou in o ma ion in he CFW [8]. The alue o he T* pa ame e a each esolu ion is he e o e gi en by he ollowing exp ession: whe e Lij(k) is he g ay alue o he pixel (i. j) a le el (k) o he Laplacian py amid. This app oach leads o good esul s, as illus a ed in Figu e 1. In his igu e, he o iginal Came aman image (Figu e l.a), i s Gaussian py amid as well as hei segmen a ions a e shown. The inal segmen a ion (264 egions) is p esen ed as a con ou image (Figu e 1.c) and as a mosaic image (Figu e 1.d). In mosaic images, each egion is illed wi h i s mean g ay alue. I has o be highligh ed ha hese segmen a ions p esen good quali y and imp o e hose ob ained by he basic mul i esolu ion echnique [6]. In addi ion, he T*(k) alues yielded by (3) a e e y close o hese ound manually o be op imal. Ac ually, e en he di e en beha iou ound o ex u ed and non- ex u ed images is espec ed by his es ima ion p ocedu e [8]. Howe e , i has o be no iced ha , in spi e o he abo e commen ed imp o emen , some de ails a e s ill o e looked in he inal segmen a ion (e. g.: he s icks in he ipod, he ae ials o some pa s o he came a and he ace) . This d awback is owing o he p esence o in e io egions in he image, which canno be ex ac ed by means o he p e ious algo i hms. To sol e his p oblem, a s age con olling ha , a each le el o he decomposi ion, he inal segmen a ion does no o e look in e io egions has been in oduced in he algo i hm. -18 whe e Y and CP s and o he open and close il e s espec i ely, and he cen e is de ined as cen e (Y CP, CP Y, I) = Min (Y 0, Max (9 Y, I)) (5) Figu e 1.- Segmen a ion o he Came aman image IV.- SEED EXTRACTION BY MORPHOLOGICAL TOOLS To analyse he p esence o non-de ec ed in e io egions wi hin a segmen a ion, he e o image is buil . This image con ains he di e ence be ween he o iginal image and he mosaic ep esen a ion o i s segmen a ion. Assuming ha segmen a ions ha e been co ec ly pe o med, e o image in o ma ion is mainly ela ed o ex u es in he o iginal image and non- de ec ed in e io egions. The e o e, he main ask is o disc imina e be ween ex u e and non-de ec ed in e io egion in o ma ion. In e io egions appea in he e o image as nea ly la , con as ed a eas; whe eas ex u ed in o ma ion appea s as dense, con as ed luc ua ions. Since ex u ed a eas may yield pixels wi h la ge absolu e alues han hose p oduced by non-de ec ed in e io egions, classical h esholding echniques canno be used. Thus mo phological ools [9] ha e been applied, gi en ha hey a e known o e icien ly pe o m in disc imina ing be ween hese kinds o in o ma ion. Mo phological il e s do no sol e he abo e p oblem. Hence, he necessi y o using o he e kind o ans o ms, such as mo phological esidues. F om he se o di e en esidues ha can be de ined, he esidue be ween he o iginal signal and a mo phological cen e [lo] (con as ex ac ion ans o m) u ns ou o be e y e icien o de ec ing in e io egions. The cen e is compu ed om he open-close, he close-open and he iden i y ope a o s: Con as ex ac o : I I - cen e (Y CP, CP Y, I) I (4) An example using a monodimensional signal is shown in Figu e 2 o illus a ing he pe o mance o he mo phological con as ex ac o . This signal con ains wo con as ed, almos la a eas which a e ela ed o in e io egions as well as h ee con as ed zones wi h apid luc ua ions, ela ed o ex u ed a eas. No e ha he con as ex ac o de ec s bo h in e io egions, yielding only a single connec ed componen o each one o hem (concep o seed). On he o he hand, ex u ed in o ma ion is almos comple ely emo ed. The small emaining componen s can be wi hd awn by pe o ming a cleaning s ep elying on size and g ay le el alue c i e ia [8]. "1 I ."A / con--dm Figu e 2.- Monodimensional example A e he cleaning s ep, he emaining componen s a e used as seeds o de ec ing new egions in he segmen a ion p ocedu e. Tha is, seeds a e added o he p e ious segmen a ion and his new pa i ion is used as ini ial segmen a ion in he p ocedu e desc ibed in Sec ion 111. In his way, seeds do no di ec ly con o m new egions bu he mono esolu ion segmen a ion echnique decides whe he hey dese e o o m a new egion o no . I a seed is conside ed o be ela ed o ai o e looked in e io egion, he segmen a ion me hod inds i s ac ual shape. V.- RESULTS AND CONCLUSIONS The use o mo phological ools allows emo ing apid a ia ions o he signal while p o iding wi h seeds o in e io egions. The e o e, in ex u ed zones, new egions do no appea and hei o e segmen a ion is a oided. On he o he hand, in e io egions a e clea ly de ec ed. This e ec can be Seen in Figu e 3, whe e he segmen a ion o he Came aman image is pe o med using he abo e echnique. Figu e 3.a shows, -19 in i s le -hand side, he segmen a ion a each le el o he py amid, while, in i s igh -hand side, he se o seeds ob ained a each le el. On i s u n, Figu e 3.b shows he seeds ob ained a he bo om o he py amid. Finally, Figu es 3.c and 3.d show he con ou s o he inal segmen a ion (353 egions) and i s mosaic ep esen a ion, espec i ely. The high quali y o he inal segmen a ion can be obse ed. I deals co ec ly wi h la ge ex u ed a eas wi hou wi hd awing any ele an small egion. I is wo h no icing ha he mo phological s ep de ec s ele an in e io egions wi hou in oducing new ones in ex u ed a eas (e. g.: he g ass). This e ec is e en mo e no iceable in he example o Figu e 4. In i , he image p esen s a la ge ex u ed a ea which has been ga he ed in o a ew egions. Fu he mo e, no main de ail in he image has been o e looked and, hus, he ep esen a ion o he hand and he acke is o e y high quali y. The inal segmen a ion o his image con ains 75 egions. I has o be highligh ed ha , in spi e o he quali y o he esul s achie ed by his echnique, i is no ime demanding. Ac ually, he a e age compu a ional load equi ed o segmen ing 256x256 pixel images wi h a Sun Spa c I1 wo ks a ion is o 27 seconds. The cu en wo k is mainly wo old. Fi s , i copes wi h he ex ension o he whole segmen a ion echnique o he case o segmen ing image sequences. In pa allel, we a e applying his segmen a ion me hod o he p oblem o image coding. Tha is, a egion-based image coding scheme is being de eloped. [l] F.-C. Jeng. J. W. Woods "Compound Gauss-Ma ko Random Fields o Image Es ima ion". IEEE T ans. on Signal P oc.., ol. 39, pp. 683-697. 1991. [2] S. Geman, D. Geman, "S ochas ic Relaxa ion, Gibbs Dis ibu ion and he Bayesian es o a ion", IEEE T am. [3] S. Lakshmanan. H. De in. "Simul aneous pa ame e es ima ion and segmen a ion o Gibbs andom ields using simula ed annealing," IEEE T ans. PAMI, ol. 11, pp. [4] F. Ma qub, A. Gasull, T. Reed, M. Kun , "Coding- o ien ed segmen a ion based on Gibbs-Ma ko Random Fields and human isual sys em knowledge", P oc. ICASSP-91, pp. 2749-2752, To on o, May 1991. [5] C. Bouman, B. Liu, "Mul iple esolu ion segmen a ion o ex u ed images," IEEE T ans. PAMI, ol. 13, pp. 99- 113, 1991. [6] F. Ma qubs, J. Cunille a, A. Gasull, "Hie a chical segmen a ion using Compound Gauss-Ma ko Random Fields", P oc. ICASSP 92, pp. III. 53-56, San F ancisco USA, Ma ch 1992. PAMI, ol. 6, pp. 721-741. NOV. 1984. 799-813, 1989. [7] H. De in, P. Kelly, "Disc e e-index Ma ko - ype andom p ocesses", P oc. IEEE, ol. 77, pp. 1485-1510, 1989. [8] F. Ma qub. Mul i esolu ion image segmen a ion based on compound andom ields. Applica ion o image coding. PhD Thesis, UN . Pol. Ca ., Ba celona, 1992. [9] J. Se a, Image Analysis and Ma hema ical Mo phology, ol. I, Academic P ess, London, 1982. [ 101 P. Salembie . I. C. Se a. "Mo phological mul iscale image segmen a ion". Visual Comm. and Image P oc. '92, pp. 620-631, Bos on, 1992 Figu e 3.- Final segmen a ion o he Came aman image Figu e 4.- Segmen a ion o a ex u ed image -20