Statistical region merging

Statistical Region Merging

Richard Nock and Frank Nielsen

Abstract—This paper explores a statistical basis for a process often described in computer vision:image segmentation by region merging following a particular order in the choice of regions.We exhibit a particular blend of algorithmics and statistics whose segmentation 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 segmentation 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 noise corruption,handle occlusion,authorize the control of the segmentation 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 segmentations obtained.

Index Terms—Grouping,image segmentation.

æ竹炭颈椎枕

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 observation is rooted in the early part of the20th century,the adaptation and automation of the segmentation(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 search of what caused the observed data[1].In this respect,the grouping problem can be roughly presented 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 seg-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 focuses 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].These 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 expenses 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 sets 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 uses this test,and builds the segmentation on the basis of(essentially)local decisions.This locality in decisions has to preserve global properties,such as those 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 case,a good region merging algorithm has to find a good balance between preserving 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 essential 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 these two components interact together,and can benefit from each o

ther.This might be partially due to the fact that most approaches use assump-tions on distributions,more or less restrictive,which would make any theoretical insight into how region merging works restricted to such settings and,therefore,of possibly moder-ate interest(,[10]for related criticisms).

Our aim in this paper is to propose a path and its milestones from a novel model of image generation,the theoretical properties of possible segmentation approaches to a practical,readily available system of image segmentation, and its extensions to miscellaneous problems related to image segmentation.First,the key idea of this model is to really formulate image segmentation as an inference problem[1].It is the reconstruction of regions on the observed image,based on an unknown theoretical(true)image on which the true regions we seek are statistical regions whose borders are defined from a simple axiom.Second,we show the existence of a particular blend of statistics and algorithmics to process observed 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 segmentation:overmerging,that is,the fact that some observed region may contain more than one true region.The algorithm does not suffer neither undermerging,nor the—-most frequent—hybrid cases where observed regions may partially span several 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.Nielsen is with Sony Computer Science Laboratories Inc.,3-14-13

Higashi Gotanda,Shinagawa-Ku,Tokyo141-0022,Japan.

E-mail:Frank.

Manuscript received8Aug.2003;revised26Jan.2004;accepted1Apr.2004.

Recommended for acceptance by R.Basri.

For information on obtaining reprints of this article,please send e-mail to:

,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 segmentation close 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 noise 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 segmentation scale in a simple manner.

The next section presents our model of image generation.Section 3details our analysis and algorithm,first for the gray-level setting,and then for color images.Section 4presents our experiments.The last two sections conclude and detail the code availability.

2P RELIMINARY N OTATIONS

AND

M ODELS

The notation j :j stands for cardinal.The observed image,I ,contains j I j pixels,each containing R ed-G reen-B lue (RGB )values,each of the three belonging to the set f 1;2;...;g g (in practice,we would have g ¼256).We have deliberately

chosen not to use complex formulations of the colors,such as the L Ãu Ãv Ãspace [10].

I is an observation of a perfect scene I Ãwe do not know of,in which pixels are perfectly represented by a family of distributions ,from which each of the observed color channel is sampled.In I Ã,the optimal (or true,or statistical )regions represent 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 observed RGB values.Fig.2presents an example of a color channel for one pixel in I Ãand how to generate the corresponding observed color channel of the pixel in I .In each pixel of I Ã,each color channel is replaced by a set 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 these 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 observed 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 segmen-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 supposed 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 segmentation found by our segmentation 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 observed pixel of I

Fig.3.Schematic view of some theoretical image I Ã,and a corresponding observed image I .Only the average over R ;G ;B of the theoretical pixels’first moments are shown in I Ã.According to the homogeneity property (see text),(a)shows the true (optimal)segmentation of I .a is the process generating the observed image (see 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 case 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,essentially,for practical purposes: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 segmenta-tion.Notice that Q is a parameter which makes sense: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 coarseness of the segmentation,with the possibility to build a hierarchy of coarse-to-fine (multiscale)segmentations 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 presented 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 segmentation algorithm.

3.1Merging Predicate

Our first result is based 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 set A k for each k .Suppose 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=

ðc k Þ2 !

:ð1ÞFrom this theorem,we obtain the following result on the

deviation of observed 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 observed 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

ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ12Q 1j R j þ1j R 0j ln 2 s :ð2ÞProof.Suppose 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 Suppose we do N merging tests in I .Then,with probability !1ÀðN Þ,all couples of regions ðR;R 0Þwhose 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 setting (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 observed 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 devise a merging predicate is

straightforward:In this case,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 see 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 set of

regions with l pixels and b ðR Þ¼g ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ

ð1=ð2Q j R jÞÞln ðjR j R j j = Þp .Remark that provided regions R and R 0are not empty,

b ðR;R 0Þ ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ

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)used as merging threshold:it holds for both others as well.The center quantity is the merging threshold we use.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 ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃb 2ðR Þþb 2ðR 0Þp false otherwise:

ð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 segmentation of I Ã.To make it clear why we should strive to fulfill A ,let us first recall the three types of error a segmentation can suffer.First,undermerging represents the case where one or more regions obtained are strict subparts of true regions.Second,overmerging represents the case where some regions obtained strictly contain more than one true region.Third,there is the “hybrid”(and most probable)case where s

ome regions obtained contain more than one strict subpart of true regions.We have already partially outlined this in the preceeding section related to the merging predicate:together with P (4),A makes it possible to control the segmentation 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 set of regions of the ideal (optimal)segmentation of I (defined from I Ã,see Fig.3)and s ðI Þthe set of regions in our segmentation of I .

Theorem 2.With probability !1ÀOðj I j Þ,the segmentation 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 whose merging is tested,satisfy j R ÀR 0j b ðR;R 0Þ.Since b ðR;R 0Þ ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃb 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 segmentation 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 segmentation.We define this error as the weighted average of the (absolute)channel differences over all nonempty intersec-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 ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃj 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 (<ﬃﬃﬃ6p );second,it is proven for the largest merging threshold in (3).Last,if we ignore log-terms,the error incurred by our segmentation is driven by g ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ

cap3j s ÃðI Þj =ðj I j Q Þp ,a

close order approximation to the optimum [12].

3.3Color Images The merging predicate

for the RGB setting is:PðR;R 0Þ¼

true if 8a 2f R ;G ;B g ;j R 0a ÀR a j ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃb 2ðR Þþb 2ðR 0Þ

p false

otherwise:

>><

>>:

ð7Þ

Here,R a denotes the observed average for color channel a in region R .Provided invariant A holds as in Section 3.2,our predicate preserves 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 set of these couples.Let f ðp;p 0Þbe a real-valued function,with p and p 0pixels of I .Our segmentation algorithm,S RM (for Statistical Region Merging)is simple.We first sort the couples of S I in increasing order of f ð:;:Þ,and then traverse 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 choose f ð:;:Þso as to approximate A as best as possible.

The next section reviews some choices we have made for f ð:;:Þ,each of constant time computation.Because we do not update the list of merging tests after merging two regions,a simple ordering based 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,segments our largest images (512Â512)in about one second on an Intel Pentium 1IV 2.40GHz processor.

4E XPERIMENTAL R ESULTS

Our model of image generation makes implicitly the assumption that observed 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 otherwise 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 used 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 second choice for f a ð:;:Þconsists of extending convolu-tion kernels classically used in edge detection for pixel-wise 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 chosen 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 case,and it uses 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.5presents 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 segmentation 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 segmentation,although tailor-made for textured images,obtains a segmentation of the grass with many holes,a common drawback of region-merging techniques [9].

4.2Random Noise Corruption

We have chosen to study the way S RM handles noise with our two choices for f a ð:;:Þ,against two

hard noise 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:.

chosen uniformly in f 1;2;...;g g for transmission noise (t ðq Þ),or

.chosen uniformly in f 1;g g (the extremes)for salt and

pepper noise (s ðq Þ).

Fig.6shows different images corrupted with increasing amounts of noise,and the results of [8]and S RM .From 45percent noise,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 noise levels and for both ways of computing f a ð:;:Þ,indicating that the algorithm seems to reach its limits.To handle larger noise NOCK

AND NIELSEN:STATISTICAL REGION MERGING 5

Fig.4.An experimental display of the importance of sorting.Regions obtained in the segmentations

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 chosen 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 set of points of I that are within Manhattan distance 2Áto p 0(for some integer Á!0),and that are closer 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 whose abscissae are those 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 segmentations 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 segmentation 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 noise 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,seems 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 presented.Then,in a second 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 these 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 noise of this video-extracted picture).4.4Controlling the Scale of the Segmentation

Some authors have emphasized the need to control the coarseness of a segmentation [7],[3],[4].The objective of multiscale segmentation is to get a hierarchy of segmenta-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 case,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 noise extensions for (8)(w/o)and Sobel-type filters (w),with Á¼10.(See text for the segmentation

conventions.)

Fig.8.Results on images with occlusions.The largest regions found by S RM are displayed for each image.

本文发布于:2024-09-22 05:24:06，感谢您对本站的认可！

本文链接：https://www.17tex.com/tex/2/202391.html

上一篇：一站多机智能化无人机指挥控制站

下一篇：初中全册英语常用3500词分类大全