Statistical Region Merging
Richard Nock and Frank Nieln
Abstract—This paper explores a statistical basis for a process often described in computer vision:image gmentation by region merging following a particular order in the choice of regions.We exhibit a particular blend of algorithmics and statistics who gmentation error is,as we show,limited from both the qualitative and quantitative standpoints.This approach can be efficiently approximated in linear time/space,leading to a fast gmentation algorithm tailored to processing images described using most common numerical pixel attribute spaces.The conceptual simplicity of the approach makes it simple to modify and cope with hard noi corruption,handle occlusion,authorize the control of the gmentation scale,and process unconventional data such as spherical images.Experiments on gray-level and color images,obtained with a short readily available C-code,display the quality of the gmentations obtained.
Index Terms—Grouping,image gmentation.
æ
1I NTRODUCTION
I T is established since the Gestalt movement in psychology that perceptual grouping plays a fundamental role in human perception.Even though this obrvation is rooted in the early part of the20th century,the adaptation and automation of the gmentation(and,more generally, grouping)task with computers has remained so far a tantalizing and central problem for image processing.Vision is widely accepted as an inference ,the arch of what caud the obrved data[1].In this respect,the grouping problem can be roughly prented as the transfor-mation of the collection of pixels of an image into a visually meaningful partition of regions and objects.
This postulates implicitly the existence of optimal g-mentation(s)which we should aim at recovering or approx-imating,and this task implies casting the perceptual formulation of optimality into a formalized,well-defined problem.A prominent trend in grouping focus on graph cuts,mapping image pixels onto graph vertices,and the spatial relationships between pixels onto weighted graph edges.The objective is to minimize a cut criterion,given that any cut on this graph yields a partition of the image into (hopefully)coherent visual patterns.Cut criteria range from conventional[2]to more sophisticated criteria,tailored to grouping[3],[4],[5].The are basically global criteria; however,the strategies adopted for their minimization range through a broad spectrum,from local[6]to global optim
iza-tion[5],through intermediate choices[7],[3].Global optimization strategies have the advantage to directly tackle the problem as a whole,and may offer good approximations [5],at possible algorithmic expens though[3],[5].
In this paper,we focus on a different strategy which belongs to the family of region growing and merging techniques[8],[9].In region merging,regions are ts of pixels with homogeneous properties and they are iteratively grown by combining smaller regions or pixels,pixels being elementary regions.Region growing/merging techniques usually work with a statistical test to decide the merging of regions[9].A merging predicate us this test,and builds the gmentation on the basis of(esntially)local decisions.This locality in decisions has to prerve global properties,such as tho responsible for the perceptual units of the image[8].In Fig.1,the grassy region below the castle is one such unit,even when its variability is high compared to the other regions of the image.In that ca,a good region merging algorithm has to find a good balance between prerving this unit and the risk of overmerging for the remaining regions.Fig.1b shows the result of our approach.As long as the approach is greedy, two esntial components participate in defining a region merging algorithm:the merging predicate and the order followed to test the merging of regions.There is a lack of theoretical results on the way the two components interact together,and can benefit from each o
ther.This might be partially due to the fact that most approaches u assump-tions on distributions,more or less restrictive,which would make any theoretical insight into how region merging works restricted to such ttings and,therefore,of possibly moder-ate interest(,[10]for related criticisms).
Our aim in this paper is to propo a path and its milestones from a novel model of image generation,the theoretical properties of possible gmentation approaches to a practical,readily available system of image gmentation, and its extensions to miscellaneous problems related to image gmentation.First,the key idea of this model is to really formulate image gmentation as an inference problem[1].It is the reconstruction of regions on the obrved image,bad on an unknown theoretical(true)image on which the true regions we ek are statistical regions who borders are defined from a simple axiom.Second,we show the existence of a particular blend of statistics and algorithmics to process obrved images generated with this model,by region merging,with two statistical properties.With high prob-ability,the algorithm suffers only one source of error for image gmentation:overmerging,that is,the fact that some obrved region may contain more than one true region.The algorithm does not suffer neither undermerging,nor the—-most frequent—hybrid cas where obrved regions may partially span veral true regions.Yet,there is more:With
.
R.Nock is with the Universite´Antilles-Guyane,De´partement Scientifique
Inter-facultaire/GRIMAAG Lab.,B.P.7209,97278Schoelcher,Martini-
que,France.E-mail:rnock@martinique.univ-ag.fr.
. F.Nieln is with Sony Computer Science Laboratories Inc.,3-14-13
Higashi Gotanda,Shinagawa-Ku,Tokyo141-0022,Japan.县的词语
E-mail:Frank.Nieln@acm.
Manuscript received8Aug.2003;revid26Jan.2004;accepted1Apr.2004.
Recommended for acceptance by R.Basri.
For information on obtaining reprints of this article,plea nd e-mail to:
tpami@computer,and reference IEEECS Log Number TPAMI-0219-0803.
0162-8828/04/$20.00ß2004IEEE Published by the IEEE Computer Society
high probability,this overmerging error is,as we show,formally small as the algorithm manages an accuracy in gmentation clo to the optimum,up to low order terms.The algorithm has some desirable features:It relies on a simple interaction between a merging predicate easily implementable,and an order in merging approximable in linear time.Furthermore,it can be adapted to most numerical feature description spaces (RGB ,HSI ,L Ãu Ãv Ã,etc.).Third,we provide a C-code implementation of this last algorithm,which is a few hundred lines of C,and experi-ments on various benchmark images,as well as comparisons with other algorithms.Last,we show how to extend the algorithm to naturally cope with hard noi and/or sig-nificantly occluded images at very affordable algorithmic complexity.Though running the algorithm does not require tuning its parameters,the control of a statistical complexity parameter makes it possible to adjust the gmentation scale in a simple manner.
The next ction prents our model of image generation.Section 3details our analysis and algorithm,first for the gray-level tting,and then for color images.Section 4prents our experiments.The last two ctions conclude and detail the code availability.
2P RELIMINARY N OTATIONS
AND
M ODELS
The notation j :j stands for cardinal.The obrved image,I ,contains j I j pixels,each containing R ed-G reen-B lue (RGB )values,each of the three belonging to the t f 1;2;...;g g (in practice,we would have g ¼256).We have deliberately
chon not to u complex formulations of the colors,such as the L Ãu Ãv Ãspace [10].
I is an obrvation of a perfect scene I Ãwe do not know of,in which pixels are perfectly reprented by a family of distributions ,from which each of the obrved color channel is sampled.In I Ã,the optimal (or true,or statistical )regions reprent theoretical objects sharing a common homogeneity property :
.
Inside any statistical region and given any color channel 2f R ;G ;B g ,the statistical pixels have the same expectation for this color channel.
.The expectations of adjacent statistical regions are
different for at least one color channel 2f R ;G ;B g .
I is obtained from I Ãby sampling each statistical pixel for obrved RGB values.Fig.2prents an example of a color channel for one pixel in I Ãand how to generate the corresponding obrved color channel of the pixel in I .In each pixel of I Ã,each color channel is replaced by a t of exactly Q independent random variables (r.v.),taking positive values on domains bounded by g=Q ,such that any possible sum of outcomes of the Q r.v.belongs to f 1;2;...;g g .Fig.3gives an example of some true image I Ã(in fact,it is the result of our algorithm,ran on Fig.3b)which displays the expectation of statistical pixels,and the obrved image I generated from I Ã.Given the homogeneity property,frontiers between true regions are connecting pixels with differences in their color expectations,and the ideal gmen-tation of I relies on the frontiers between the statistical regions shown on I Ãin Fig.3.
描写泰山的句子The sampling of each pixel and its color channels are suppod independent from each other.It is important to note that this is the only assumption we make on I Ã,and the frequent independent identically distributed (i.i.d.)assump-
Fig.1.An RGB image and the gmentation found by our gmentation method (regions are white bordered and averaged
inside).
Fig.2.Generation of a single color channel for one pixel from a statistical region O of I Ãto some obrved pixel of I
缅怀亲人
.
Fig.3.Schematic view of some theoretical image I Ã,and a corresponding obrved image I .Only the average over R ;G ;B of the theoretical pixels’first moments are shown in I Ã.According to the homogeneity property (e text),(a)shows the true (optimal)gmentation of I .a is the process generating the obrved image (e also Fig.2),and b is grouping’s objective (i.e.,find the statistical regions’borders,given I ).
tion is relaxed in this model to that of ordinary independence.Inside a statistical region,it can be the ca that all distributions associated to each pixel are different,as long as the homogeneity property is satisfied.This freedom has a counterpart,which led us to introduce Q ,not necessarily to make our model more general,but,esntially,for practical purpos:The conventional choice Q ¼1would actually make it hard to estimate reliably anything for small regions or,equivalently,would make it necessary to consider very large images to improve the statistical accuracy of the gmenta-tion.Notice that Q is a parameter which makes n:It allows us to quantify the statistical complexity of I Ã,the generality of the model,and thestatistical hardnessof the task as well.From an experimental standpoint,tuning Q modifies the statistical complexity of the scene,and makes it possible to control the coarness of the gmentation,with the possibility to build a hierarchy of coar-to-fine (multiscale)gmentations of an image [3].
3T HEORETICAL A NALYSIS
AND
A LGORITHMS
For the sake of simplicity,we first state our theoretical results for a single color band (e.g.,gray-level).On this basis,the extension of the results to more numerical channels,such as RGB ,does not require an involved analysis:It is prented in Section 3.3.Recall that it is enough to give a merging predicate and an order to test region mergings,to completely define our gmentation algorithm.
3.1Merging Predicate
Our first result is bad on the following theorem.Theorem 1(The independent bounded difference in-equality,[11]).Let X ¼ðX 1;X 2;...;X n Þbe a family of n independent r.v.with X k taking values in a t A k for each k .Suppo that the real-valued function f defined on Q k A k satisfies j f ðx ÞÀf ðx 0Þj c k whenever vectors x and x 0differ only in the k th coordinate.Let be the expected value of the r.v.f ðX Þ.Then,for any !0,
Pr ðf ðX ÞÀ ! Þ exp À2 2=
X
k
ðc k Þ2 !
铁皮石斛怎么泡水喝:ð1ÞFrom this theorem,we obtain the following result on the
deviation of obrved differences between regions of I .Here,the notation E ðR Þfor some arbitrary region R is the expectation over all corresponding statistical pixels of I Ãof their sum of expectations of their Q r.v.for the single color band,and R is the obrved average of this color band.Corollary 1.Consider a fixed couple ðR;R 0Þof regions of I .80< 1,the probability is no more than that
jðR ÀR 0ÞÀE ðR ÀR 0
Þj !g
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi12Q 1j R j þ1j R 0j ln 2 s :ð2ÞProof.Suppo we shift the value of the outcome of one r.v.
among the Q ðj R j þj R 0jÞpossible for the couple ðR;R 0Þ.
j R ÀR 0
j is subject to a variation of at most c R ¼g=ðQ j R jÞwhen this modification affects region R (among Q j R j
possible),and at most c R 0¼g=ðQ j R 0jÞfor a change inside R 0(among Q j R 0j possible).We get P
k ðc k Þ2¼Q ðj R jðc R Þ2þj R 0jðc R 0Þ2Þ¼ðg 2=Q Þðð1=j R jÞþð1=j R 0jÞÞ.Using the fact that
组装笔记本the deviation with the absolute value is at most twice that without,and using Theorem 1(solving for )brings our result.t u Suppo we do N merging tests in I .Then,with probability !1ÀðN Þ,all couples of regions ðR;R 0Þwho merging is
tested shall satisfy jðR ÀR 0ÞÀE ðR ÀR 0
Þj b ðR;R 0Þ,with b ðR;R 0Þthe right member of Corollary 1.Remark that N is small:for a single-pass algorithm,N <j I j 2.In our 4-connexity tting (each pixel is connected to its north,south,east,and westneighborswhen theyexist),weevenhave N <2j I j .What we really need to test the merging of two obrved regions R and R 0is a predicate accurate enough when the pixels o
f R [R 0come from the same statistical region of I Ã.From this standpoint,using Corollary 1to devi a merging predicate is
straightforward:In this ca,we have E ðR ÀR 0
Þ¼0and,
thus,with high probability,the deviation j R ÀR 0
j does not exceed b ðR;R 0Þ.The merging predicate on two candidate regions R and R 0could thus be “merge R and R 0iff
j R ÀR 0
j b ðR;R 0Þ,”with b ðR;R 0Þa merging threshold .We shall e hereafter that such a predicate is optimistic :Under some assumption,it tends sometimes to favor overmerging (i.e.,it does more merges than necessary to actually recover I Ã),but this phenomenon formally remains quantitatively small.For both theoretical and practical considerations,we are going to replace this merging predicate by one slightly more ,with a larger merging threshold.This one turns out to theoretically incur the same error (up to low order terms),and it gives very good visual results.Let R l
be the t of
regions with l pixels and b ðR Þ¼g ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ð1=ð2Q j R jÞÞln ðjR j R j j = Þp .Remark that provided regions R and R 0are not empty,
PCMCIA卡b ðR;R 0Þ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
b 2ðR Þþb 2ðR 0Þp <b ðR Þþb ðR 0Þ:ð3ÞHereafter,we prove a quantitative bound on the error
obtained with the largest quantity (the right one)ud as merging threshold:it holds for both others as well.The center quantity is the merging threshold we u.An upperbound on jR l j makes it quite reasonable with regard to b ðR;R 0Þ.Considering that a region is an unordered bag of pixels (each color channel is given 0;1;...;l pixels),we may fix jR l j ðl þ1Þmin f l;g g (we have l þ1choices for the number of pixels having each color channel,which makes jR l j ðl þ1Þg ,and then we reduce this large upperbound by counting the duplicates for l <g ).To summarize,our merging predicate is:
PðR;R 0
Þ¼
true if j R 0ÀR j ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffib 2ðR Þþb 2ðR 0Þp fal otherwi:
ð4Þ3.2Order in Merging
The order in which we test the merging of regions follows a simple invariant A which we define as follows:.
ðAÞ¼def
when any test between two (parts of)true regions occurs,that means that all tests inside each of the two true regions have previously occurred.
NOCK AND NIELSEN:STATISTICAL REGION MERGING 3
It is crucial to note that A does not postulate the knowledge of the gmentation of I Ã.To make it clear why we should strive to fulfill A ,let us first recall the three types of error a gmentation can suffer.First,undermerging reprents the ca where one or more regions obtained are strict subparts of true regions.Second,overmerging reprents the ca where some regions obtained strictly contain more than one true region.Third,there is the “hybrid”(and most probable)ca where s
ome regions obtained contain more than one strict subpart of true regions.We have already partially outlined this in the preceeding ction related to the merging predicate:together with P (4),A makes it possible to control the gmentation error from both the qualitative and quantitative standpoints.The next theorem states that only overmerging occurs with high probability.In this theorem,we define s ÃðI Þas the t of regions of the ideal (optimal)gmentation of I (defined from I Ã,e Fig.3)and s ðI Þthe t of regions in our gmentation of I .
Theorem 2.With probability !1ÀOðj I j Þ,the gmentation on I satisfying A is an overmerging of I Ã,that is:8O 2s ÃðI Þ;9R 2s ðI Þ:O R .Proof.From Corollary 1,with probability >1ÀðN Þ¼1ÀOðj I j Þ,any couple of regions (R;R 0)coming from the same statistical region of I Ã,and who merging is tested,satisfy j R ÀR 0j b ðR;R 0Þ.Since b ðR;R 0Þ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffib 2ðR Þþb 2ðR 0Þp ,our merging predicate PðR;R 0Þ(4)would authorize the merging of R and R 0.Using the fact that A holds together with this property,we first rebuild all true regions of I Ã,and then eventually make some more merges:The gmentation obtained is an overmerging of I Ãwith high probability,as claimed.t u The next theorem shows a quantitative upperbound on the error incurred with respect to the optimal gmentation.We define this error as the weighted average of the (absolute)channel differences over all nonempty interc-tions of regions between s ÃðI Þand s ðI Þ:
Err ðs ðI ÞÞ¼E R \O;R 2s ðI Þ;O 2s ÃðI ÞE ðO ÞÀE ðR Þj j ;
ð5Þ
with E (slanted)denoting the expectation with associated probability measure ðR \O Þ¼j R \O j =j I j .
Theorem 3.80< <1,with probability !1ÀOðj I j Þ:
Err ðs ðI ÞÞ O g ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffij s ÃðI Þj ln j s ÃðI Þj j I j Q ln 1
þg ln j I j s !:ð6Þ
蛤蟆(Proof omitted.)This theorem is interesting for three (mostly)
theoretical reasons.First,the constant hidden in the big-Oh notation is small (<ffiffiffi6p );cond,it is proven for the largest merging threshold in (3).Last,if we ignore log-terms,the error incurred by our gmentation is driven by g ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
j s ÃðI Þj =ðj I j Q Þp ,a
clo order approximation to the optimum [12].
3.3Color Images The merging predicate
for the RGB tting is:PðR;R 0Þ¼
true if 8a 2f R ;G ;B g ;j R 0a ÀR a j ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffib 2ðR Þþb 2ðR 0Þ
p fal
otherwi:
8
>><
>>:
ð7Þ
Here,R a denotes the obrved average for color channel a in region R .Provided invariant A holds as in Section 3.2,our predicate prerves overmerging,and the same bound as that of Theorem 3holds on the error if we measure it as the sum of errors over the three color channels.
3.4Our Algorithm:S RM
In 4-connexity,there are N <2j I j couples of adjacent pixels.Let S I be the t of the couples.Let f ðp;p 0Þbe a real-valued function,with p and p 0pixels of I .Our gmentation algorithm,S RM (for Statistical Region Merging)is simple.We first sort the couples of S I in increasing order of f ð:;:Þ,and then traver this order only once .We make for any current couple of pixels ðp;p 0Þ2S I for which R ðp Þ¼R ðp 0Þ(R ðp Þstands for the current region to which p belongs)the test PðR ðp Þ;R ðp 0ÞÞ,and merge R ðp Þand R ðp 0Þiff it returns true .The objective is obviously to choo f ð:;:Þso as to approximate A as best as possible.
The next ction reviews some choices we have made for f ð:;:Þ,each of constant time computation.Becau we do not update the list of merging tests after merging two regions,a simple ordering bad on radix sorting with color differences as the keys yields a preordering time complexity Oðj I j log ðg ÞÞ—linear in j I j —for our basic implementations of S RM .The merging ste
ps afterward are space/time compu-tational optimal [13],which makes S RM also optimal from both standpoints.The execution time of our basic imple-mentation of S RM ,which is not optimized,gments our largest images (512Â512)in about one cond on an Intel Pentium 1IV 2.40GHz processor.
4E XPERIMENTAL R ESULTS
Our model of image generation makes implicitly the assumption that obrved color variations inside true regions should reasonably be smaller than between true regions.Such an assumption is made explicit in [8].Thus,a good way to approximate A is to capture the between-pixel local gradi-ents,and then compute their maximal per-channel variation in f ð:;:Þ:f ðp;p 0Þ¼max a 2f R ;G ;B g f a ðp;p 0Þ.Below,we review some experiments using S RM .The reader may keep in mind that,unless otherwi stated,the values of the parameters of S RM are the same for all images: ¼1=ð6j I j 2Þ(Corollary 1)and Q ¼32.Furthermore,the images are ud as they ,without any preprocessing.Therefore,there is no extensive domain nor image-dependent tuning of the parameters.
4.1Basic Choices for f ð:;:Þ
We have tested two basic choices to compute f a ðp;p 0Þ.The simplest choice is to pick directly the pixel channel values (p a and p 0a ):
f a ðp;p 0Þ¼j p a Àp 0a j :
ð8Þ
Our cond choice for f a ð:;:Þconsists of extending convolu-tion kernels classically ud in edge detection for pixel-wi gradient estimation.In 4-connexity,neighbor pixels are
either horizontal or vertical.Thus,we only need ^@
x or ^@y between neighbor pixels p and p 0,for each color channel.We have chon Sobel convolution filters,where smoothing is performed by the convolution mask ½121 and the derivative filter is performed by the convolution mask ½À1001 .
4IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,VOL.26,NO.11,NOVEMBER 2004
Regardless of the choice of f a ð:;:Þ,the fact that we do not reorder the merging list during the mergi
ng steps might appear to be quite a strong constraint for efficient approximations to A .The following simple experiment is an advocacy that it is not the ca,and it us our simplest implementation of f a ð:;:Þ(8).Fig.4displays the result of S RM on gray-level images (with ¼1=j I j 2),and the result of the same algorithm in which the order is replaced by a conventional scanning of the image (from left to right and top to bottom)[13].The preordering clearly manages dramatic improvements over conven-tional scanning.
Fig.5prents experiments obtained with our two methods for computing f a ð:;:Þon images for which results are visually different.On images with significant color
gradients,there is a visual advantage to S RM (w)(e.g.,cup ).Notice also the gmentation of S RM (w)on bldg ,a picture exhibiting a large amount of motion blur.Remark from squirrel that S RM is able to isolate regions with high variability (e.g.,the grass),and obtains results even better than [9]on the squirrel image:Their gmentation,although tailor-made for textured images,obtains a gmentation of the grass with many holes,a common drawback of region-merging techniques [9].
4.2Random Noi Corruption
We have chon to study the way S RM handles noi with our two choices for f a ð:;:Þ,against two 纹身小图案女
hard noi types.Each color channel 2f R ;G ;B g of each pixel 2I is transformed with probability q 2½0;1 into a new value:.
chon uniformly in f 1;2;...;g g for transmission noi (t ðq Þ),or
.chon uniformly in f 1;g g (the extremes)for salt and
pepper noi (s ðq Þ).
Fig.6shows different images corrupted with increasing amounts of noi,and the results of [8]and S RM .From 45percent noi,the results of [8]appear to be random,whereas S RM still manages to find most interesting regions of the images.However,on some images,S RM obtained a brutal degradation of its performances for significant noi levels and for both ways of computing f a ð:;:Þ,indicating that the algorithm ems to reach its limits.To handle larger noi NOCK
AND NIELSEN:STATISTICAL REGION MERGING 5
Fig.4.An experimental display of the importance of sorting.Regions obtained in the gmentations
are gray-level averaged with white borders.
Fig.5.Comparison of S RM without specific gradient estimation ((8),center images)and with convoluti
on kernels (right images).Regions
are color averaged with white borders.
Fig. 6.Sample results comparing both versions of S RM and [8].Segmentation conventions are [8]s:region colors are chon at random.
corruption,we have extended both solutions for f a ð:;:Þto more robust estimations,paying no significant additional computational cost.First,we replace p a (8),by a moving average over a region defining a neighborhood around the pixel:f a ðp;p 0Þ¼j N p ðp 0Þa ÀN p 0ðp Þa j .Here,N p ðp 0Þis the region defined by the t of points of I that are within Manhattan distance 2Áto p 0(for some integer Á!0),and that are clor to p 0than they are to p .Whenever Á¼0,this expression matches that of (8).Second,we replace our convolution filter by larger ones,where smoothing is performed by the convolution mask ½12ÁÁÁÁþ1ÁÁÁÁ1 ,and the derivative filter on each color channel is replaced by a local least-square linear regression on points who abscissae are tho of the convolution mask ½ÀÁÀÁþ1ÁÁÁÁ ,and ordinates defined by color channels of the corresponding pixels.Whenever Á¼1,this matches our Sobel filter’s extension in Section 4.1.
Using radix sorting again with f ð:;:Þvalues as the keys,the whole time complexity of our modifications of S RM becomes Oðj I jðlog g þÁÞÞ,which is still linear in j I j if Áis constant.
Fig.7reports results on the castle of Fig.1.Conven-tions for the gmentations results are as follows:[10]’s regions are averaged with the original colors,[8]’s are averaged with random colors,and S RM s follow [10]’s (with white bordered regions).Notice that the number of regions found by [10],[8]explode with corruption,a phenomenon which does not appear for S RM modified.The gmentation time for the three algorithms gives a clear advantage to [8]and S RM modified.This image gives a slight advantage to S RM (w/o)over S RM (w)for noi handling,but we have remarked that both versions perform quite similarly on average.The best value of Á,which controls the local number of pixels on which each gradient approximation is
computed,ems to vary between images,but it always has to remain small so as not to obtain “boxy-shaped”regions.In this respect,Á¼10is not far from the maximal value.
4.3Handling Occlusions
In our model,occlusions make it necessary to relax the 4-connexity constraint on the statistical regions of I Ã.Handling them from an experimental point of view is simple:We first run S RM as already prented.Then,in a cond stage,we run it again with two major modifications on the preordering step:We replace the pixels of I by the regions found after the first step,and replace the 4-
adjacency graph between pixels by the clique graph between the regions.We also replace f a ð:;:Þin (8)by:f a ðR;R 0Þ¼j R 0a ÀR a j .Radix sorting with the f ð:;:Þvalues as the keys brings an overall time complexity Oððj I j þk 2Þlog g Þ,where k is the number of regions found after the first step.The fact that our approach relies on slight overmerging tends to narrow the influence of k in the complexity.Fig.8shows some results obtained,on which S RM has managed to rebuild accurately the principal occluded regions (such as the road on the road image,despite the relative noi of this video-extracted picture).4.4Controlling the Scale of the Segmentation
Some authors have emphasized the need to control the coarness of a gmentation [7],[3],[4].The objective of multiscale gmentation is to get a hierarchy of gmenta-tions at different scales,and get at each scale a level of details compatible with the perceptual organization of the image at this scale.In our ca,controlling the scale is made easy with the tuning of parameter Q :The smaller it is,the harder is the statistical estimation task,and the less
6IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,VOL.26,NO.11,NOVEMBER
2004
Fig.7.Results and comparisons with related approaches of S RM with our noi extensions for (8)(w/o)and Sobel-type filters (w),with Á¼10.(See text for the gmentation
conventions.)
Fig.8.Results on images with occlusions.The largest regions found by S RM are displayed for each image.
