Binary Partitioning, Perceptual Grouping, And . - NTNU
1364IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,VOL. 25,NO. 11,NOVEMBER 2003Binary Partitioning, Perceptual Grouping, andRestoration with Semidefinite ProgrammingJens Keuchel, Christoph Schnörr, Christian Schellewald, and Daniel CremersAbstract—We introduce a novel optimization method based on semidefinite programming relaxations to the field of computer visionand apply it to the combinatorial problem of minimizing quadratic functionals in binary decision variables subject to linear constraints.The approach is (tuning) parameter-free and computes high-quality combinatorial solutions using interior-point methods (convexprogramming) and a randomized hyperplane technique. Apart from a symmetry condition, no assumptions (such as metric pairwiseinteractions) are made with respect to the objective criterion. As a consequence, the approach can be applied to a wide range ofproblems. Applications to unsupervised partitioning, figure-ground discrimination, and binary restoration are presented along withextensive ground-truth experiments. From the viewpoint of relaxation of the underlying combinatorial problem, we show the superiorityof our approach to relaxations based on spectral graph theory and prove performance bounds.Index Terms—Image partitioning, segmentation, graph cuts, perceptual grouping, figure-ground discrimination, combinatorialoptimization, relaxation, convex optimization, convex programming.æ1INTRODUCTION1.1Motivation and Overviewproblems occur in almost all fields ofcomputer vision and pattern recognition. One of themost important design decisions concerns the compromisebetween the adequacy of the optimization criterion and thedifficulty in computing the solution. An inadequate optimization criterion will not solve the application problem, nomatter how easy it is to compute the optimum. Conversely,sophisticated criteria that can only be optimized afterelaborate parameter tuning or with sufficient a priori knowledge (e.g., a good starting point) are useless in practice aswell. For this reason, optimization approaches are attractivewhich help in making a “good” compromise in this sense.In this paper, we introduce a novel optimization technique,which is based on semidefinite programming relaxations, to thefield of computer vision and apply it to minimize quadraticfunctionals defined over binary decision variables and subjectto linear constraints. Numerous problems in computer vision,including partitioning and grouping, lead to combinatorialoptimization problems of this type. In contrast to relatedwork, no specific assumptions are made with respect to thefunctional form besides a symmetry condition. As a consequence, our approach covers graph-optimization problems, unsupervised and supervised classification tasks,and first-order Markov random field estimates withoutdepending on specific assumptions or problem formulations.Therefore, it can be utilized for a wide range of applications.The combinatorial complexity of the optimization task isdealt with in two steps: First, the decision variables areOPTIMIZATION. The authors are with the CVGPR-Group, Department of Mathematics andComputer Science, University of Mannheim, D-68131 Mannheim, Germany. E-mail: {jkeuchel, schnoerr, cschelle, cremers}@uni-mannheim.de.Manuscript received 29 Apr. 2002; revised 28 Jan. 2003; accepted 6 May2003.Recommended for acceptance by M.A.T. Figueiredo, E.R. Hancock, M. Pelillo,and J. Zerubia.For information on obtaining reprints of this article, please send e-mail to:tpami@computer.org, and reference IEEECS Log Number 118619.0162-8828/03/ 17.00 ß 2003 IEEElifted to a higher-dimensional space where the optimizationproblem is relaxed to a convex optimization problem.Specifically, the resulting semidefinite program comprisesa linear objective functional that is defined over a cone insome matrix space and a number of application-dependentlinear constraints. Second, the decision variables arerecovered from the global optimum of the relaxed problemby using a small set of randomly computed hyperplanes.Using this optimization technique amounts to a compromise as follows. Advantageous properties are:þ The original combinatorial problem is transformed to anoptimization problem which is convex. As a consequence,the global optimum of the transformed problem can becomputed under mild conditions.þ Using an interior-point algorithm, an -approximation tothis global optimum can be numerically determined inpolynomial time.þ No tuning parameters are necessary.þ In contrast to spectral relaxation, no choice of a suitablethreshold value is necessary. This makes our approachespecially suited for unsupervised classification tasks.On the negative side, we have: The number of variables of the optimization problem issquared.This limits the application to problems with up to severalhundred variables, which is, however, sufficient for manyproblems related to image partitioning and perceptualgrouping. Furthermore, the increase in the problem dimension is necessary in order to approximate an intricatecombinatorial problem by a simpler convex optimizationproblem! Intuitively, nasty combinatorial constraints in theoriginal space are lifted to a higher-dimensional matrixspace where these constraints can be better approximatedby convex sets that, in turn, are more convenient fornumerical optimization. Hence, we add:þ High-quality combinatorial solutions can be computed bysolving an appropriate convex optimization problem.Published by the IEEE Computer Society
KEUCHEL ET AL.: BINARY PARTITIONING, PERCEPTUAL GROUPING, AND RESTORATION WITH SEMIDEFINITE PROGRAMMING1365Fig. 1. (a) A color scene and (b) a gray-value scene comprised of some natural textures. How can we partition such scenes into coherent groups inan unsupervised way based on pairwise (dis)similarities between local measurements?“High-quality” means that the solutions obtained are notfar from the unknown global optimum (the computation ofwhich is NP-hard and, thus, intractable) in terms of theoriginal optimization criterion.The absence of any specific assumptions about theobjective criterion as well as the “þ-properties” listed abovemotivated this investigation.1.2 Partitioning, Grouping, and RestorationIn this section, we illustrate three problems that lead todifferent instances of the class of optimization problemsconsidered in this paper. By this, we would like to indicate thesignificance of this problem class for computer vision and toexemplify some nontrivial specific problems. More formalproblem definitions will be given in the following sections.Fig. 1 shows two images taken from the VisTex-databaseat MIT [61]. A common goal of low-level computer vision is topartition such images in an unsupervised way into coherentgroups based on some locally computed features (color,texture, motion, .). To this end, the representation of imagesby graph structures has recently attracted the interest ofresearchers [58], [35], [26], [10]. We will show that, whenusing our approach, some of the assumptions made in theliterature concerning admissible objective criteria can bedropped. Moreover, we study in detail the unsupervisedbipartitioning of images by constrained minimal cuts of theunderlying graphs and show that, from the optimizationpoint of view, our convex approximation provides a tighterrelaxation of the underlying combinatorial optimizationproblem than recently suggested methods which are basedon spectral graph theory.Fig. 2a shows a section of an office table from the top.Probably most human observers focus on the (partiallyoccluded) keyboard first. A typical problem of computervision is to model such global decisions by solving anoptimization problem defined in terms of locally extractedprimitives [55], [33], [63]. In this context, the optimizationcriterion is considered as a saliency measure with respect todecision variables indicating which primitives belong to theforeground or background, respectively. We will show thatquadratic saliency measures which have been considered asdifficult [63] due to their combinatorial complexity canconveniently be dealt with using our approach.Fig. 2b shows a noisy map of Iceland. The restoration ofsuch images has a long history, in particular in the contextof Markov random fields [29], [28], [64], [43]. We will showbelow that such binary restoration problems can bemodeled under less restrictive conditions than those usedby previous approaches.1.3Related Work1.3.1 Optimization Approaches in Computer VisionMany energy-minimization problems in computer visionlike image labeling and partitioning, perceptual grouping,graph matching, etc., involve discrete decision variablesand, therefore, are intrinsically combinatorial by nature.Accordingly, optimization approaches to efficiently compute good minimizers have a long history in the literature.An important class of optimization approaches is based onstochastic sampling which was introduced by Geman andGeman [29] and has been widely applied in the Markovrandom field (MRF) literature [43], [64]. As is well-known,corresponding algorithms are very slow due to the annealingFig. 2. (a) Section of an office table shown from the top. The keyboard probably first attracts the attention of the observer. How can we compute thisfigure-ground discrimination (global decision) based on pairwise (dis)similarities between local measurements? (b) A noisy binary image (map ofIceland) to be restored.
1366IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,schedules prescribed by theory. Nevertheless, there has beena renewed interest during the last years in conjunction withBayesian reasoning [40] and complex statistical models (e.g.,[71], [68]). For further aspects, we refer to [23].To speed up computations, approaches for computingsuboptimal Markov random field estimates like the ICMalgorithm [5], the highest-confidence-first heuristic [11],multiscale approaches [32], and other approximations [67],[9] were developed. A further important class of approachescomprises continuation methods like Leclerc’s partitioningapproach [42], the graduated-non-convexity strategy byBlake and Zisserman [6], and various deterministic (approximate) versions of the annealing approach in applications like surface reconstruction [27], perceptual grouping[33], graph matching [31], or clustering [54], [34].Apart from simulated annealing (with annealing schedules that are unpractically slow for real-world applications),none of the above-mentioned approaches can guarantee tofind the global minimum and, in general, this goal is elusivedue to the combinatorial complexity of these minimizationproblems. Consequently, the important question concerningthe approximation of the problem arises: How good is acomputed minimizer relative to the unknown global optimum? Can a certain quality of solutions in terms of itssuboptimality be guaranteed in each application? To the bestof our knowledge, none of the approaches above (apart fromsimulated annealing) seems to be immune against gettingtrapped in some poor local minimum and, hence, does notmeet these criteria.A further problem relates to the algorithmic properties ofthese approaches. Apart from simple greedy strategies[5], [11], most approaches involve some (sometimeshidden) parameters on which the computed local minimumcritically depends. A typical example is given by theartificial temperature parameter in deterministic annealingapproaches and the corresponding iterative annealing schedule. It is well-known [56] that such approaches exhibitcomplex bifurcation phenomena, the transitions of which(that is, which branch to follow) cannot be controlled by theuser. Furthermore, these approaches involve highly nonlinearnumerical fixed-point iterations that tend to oscillate in aparallel (synchronous) update mode (see [33, p. 906] and [50]).Our approach belongs to the mathematically well-understood class of convex optimization problems and contributesto both of the problems discussed above. First, there exists aglobal optimum under mild assumptions that, in turn, leadsto a suboptimal solution of the original problem, along withclear numerical algorithms to compute it. Abstracting fromthe computational process, we can simply think of a mappingtaking the data to this solution. Thus, evidently, no hiddenparameter is involved. Second, under certain conditions,bounds can be derived with respect to the quality of thesuboptimal solution. At present, these bounds are not tightwith respect to the much better performance measured inpractice. Yet, it should be noted that, for alternativeoptimization approaches, performance bounds and a corresponding route of research seem to be missing.11. A recent notable exception with respect to a more restricted class ofoptimization problems is [10].VOL. 25,NO. 11,NOVEMBER 2003Fig. 3. Representing image partitions by graph cuts: The weights of alledges cut provide a measure for the (dis)similarity of the resultinggroups.1.3.2 Graph Partitioning, Clustering, PerceptualGroupingAs illustrated in Section 1.2, there is a wide range of problemsto which our optimization approach can be applied. While anin-depth discussion of all possible applications is notpossible, we next briefly discuss work that relates to theapplications we use to illustrate our optimization approach.Graph partitioning. Approaches to unsupervised imagesegmentation by graph partitioning have been proposed by[46], [58], [26], and references therein. Images are representedby graphs GðV ; EÞ with locally extracted image features asvertices V and pairwise (dis)similarity values as edgeweights w : E V V ! IRþ0 (Fig. 3). A classical approachfor the efficient computation of suboptimal cuts is based onthe spectral decomposition of the Laplacian matrix [21]. Thisapproach has found applications in many different fields [46].Accordingly, Shi and Malik [58] propose the “normalizedcut” criterion which minimizes the weight of a cut subject tonormalizing terms to prevent unbalanced cuts. The resultingcombinatorial problem is relaxed using methods fromspectral graph theory. For a survey of further work in thisdirection, we refer to [62]. Based on [37], Gdalyahu et al. [26]suggest to compute partitions as “typical average” cuts of theunderlying graph using a stochastic sampling method.Although this approach is very interesting, it does notdirectly relate to an optimization criterion and, therefore,will not be further discussed.It has been criticized in [26] that methods based on spectralgraph theory are not able to partition highly skewed datadistributions and noncompact clusters. We will show below,however, that a straightforward remedy is to base thesimilarity measure on a suitable path metric. Furthermore,our approach yields a tighter relaxation of the underlyingcombinatorial problem and, hence, most likely better suboptimal solutions.Recent approaches to supervised graph partitioning(image labeling) include [35], [10] and references therein.These authors consider the case of nonbinary labels xi andthe following class of optimization criteria:XXDi ðxi Þ þPi;j ðxi ; xj Þ:ð1Þi2Vði;jÞ2EWhile Boykov et al. [10] require Pi;j ð ; Þ to be a semi-metric,Ishikawa [35] makes the stronger assumption Pi;j ðxi ; xj Þ ¼P ðxi xj Þ, with P being convex. In this paper, we consider thecase of binary labels and do not make any assumptions with
KEUCHEL ET AL.: BINARY PARTITIONING, PERCEPTUAL GROUPING, AND RESTORATION WITH SEMIDEFINITE PROGRAMMINGrespect to pairwise interaction terms Pi;j . Unlike a semimetric, for example, Pi;j may not vanish for xi ¼ xj or can benegative.Clustering. The approaches to unsupervised imagepartitioning discussed above may also be understood asclustering methods, of course. In this paper, we focus in detailon image bipartitioning by computing constrained minimalcuts of the underlying graph. Consecutive partitions thuslead to a hierarchical clustering method (cf. [38]).An important issue, in this context, is cluster normalization in order to avoid too unbalanced partitions. In general,normalization criteria lead to rational nonquadratic terms ofthe cost functional [19], [34] to which our optimizationapproach cannot be directly applied. Below, however, weinvestigate cluster normalization by imposing various linearconstraints, as introduced by Shi and Malik [58] as arelaxation of their specific nonquadratic normalizationcriterion. Recently, the (natural) use of path-metrics for(dis)similarity-based clustering was also advocated in [22].Perceptual grouping. There is a vast literature onperceptual grouping in vision. For a survey, we refer to [55]and, e.g., [36], [1], and references therein. In this paper, wemerely focus from an optimization point-of-view on thequadratic saliency measure of Herault and Horaud [33], theapplication of which has been considered difficult due to itscombinatorial complexity [63]. We show below that thisgrouping criterion can conveniently be optimized using ourapproach.1.3.3 Mathematical ProgrammingOptimization methods based on semidefinite programmingare relatively novel techniques that have been successfullyapplied to optimization problems in such diverse fields asnonconvex and combinatorial optimization, statistics, orcontrol theory. For a survey, we refer to [65].The method used in this paper for relaxing combinatorialconstraints goes back to the seminal work of Lovász andSchrijver [44]. Concerning interior-point methods for convexprogramming, we refer to numerous textbooks [48], [66], [69]and surveys [59], [65].To recover a combinatorial solution from the globaloptimum of the relaxation, we adopt the randomized hyperplane technique developed by Goemans and Williamson [30].For a classical optimization problem from combinatorialgraph theory (max-cut), these authors were able to show thatsuboptimal solutions cannot be worse than 14 percent relativeto the unknown global optimum. Besides the convenientalgorithm design based on convex optimization, this fact hasmotivated our work.1.4 Organization of the PaperIn Section 2, we formally define three optimization problemsrelated to unsupervised partitioning (Section 2.1), perceptualgrouping, or figure-ground discrimination (Section 2.2), andbinary image restoration (Section 2.3). The mathematicalrelaxation of the corresponding combinatorial problem classis the subject of Section 3. We explain the derivation of acorresponding semidefinite program (Section 3.1), its feasibility (Section 3.2), related algorithms (Section 3.3), performance bounds (Section 3.4), and the superiority of convexrelaxation to spectral relaxation (Section 3.5). In Section 4, wediscuss numerical results for real scenes and ground-truthexperiments. We conclude and indicate further work inSection 5.13671.5 NotationThe following notation will be used throughout the paper.For basic concepts from graph theory, we refer to, e.g., [18].e: vector of all ones: e ¼ ð1; . . . ; 1Þ .DðxÞ: diagonal matrix with vector x on its diagonal: Dii ¼ xi .DðXÞ: matrix X with off-diagonal elements set to zero.I: unit matrix I ¼ DðeÞ.S n : space of symmetric n n matrices X ¼ X.S nþ : set of matrices X 2 S n which are positive semidefinite.X Y : standard matrix scalar product X Y ¼ Tr½X Y .GðV ; EÞ: undirected graph with vertices V ¼ f1; . . . ; ngand edges E V V .w: weight function of the graph G: w : E ! IRþ0.wðSÞ: sum of edge-weights of the subgraph induced by thevertex subset S V .S : complement V n S of the vertex subset S V .wð SÞ: weight of a cut defined by the partition S; S .W : weighted adjacency matrix of graph G : Wij ¼ wði; jÞ;ði; jÞ 2 E.L: Laplacian matrix of graph G: L ¼ DðW eÞ W . k ðLÞ: eigenvalues 1 ðLÞ . . . n ðLÞ of the Laplacianmatrix L of graph G.kxk: Euclidean norm of the vector x: kxk ¼ x x.2PROBLEM STATEMENT: BINARY COMBINATORIALOPTIMIZATIONIn this section, we formally define optimization criteriaaccording to the problems introduced in Sect
þ High-quality combinatorial solutions can be computed by solving an appropriate convex optimization problem. 1364 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 11, NOVEMBER 2003. The authors are with the CVGPR-Group, Department of Mathematics and Computer Science, University of Mannheim, D-68131 Mannheim, Ger-many.
Binary prices Binary prices rautmann (2013 Binary no price Epstein (2002 Binary prices al. (2014 Binary maximis- seek- er- t al. (2010 Binary individ- price al. 2014 Binary prices Binary sset prices Halevy (2019 Auction y Binary diffi- sig- nals Liang (2019 sm y Binary erreac- news al. (2012 Auction y Binary under- signals et y Gaussian erreac .
sequence from memory. Size sorting Print out some worksheets with objects to sort by size (search for “size sorting worksheet”). Encourage the children to discuss bigger File Size: 2MBPage Count: 38People also search forvisual perceptual skills otvisual perceptual worksheetsvisual perceptual puzzlesdiy visual perceptual gamesvisual perceptual skills pdfvisual perception adults
MERCEDES BARCHILON BEN-AVand DOV SAGI The Weizmann Institute of Science, Rehovot, Israel and JOCHEN BRAUN California Institute of Technology, Pasadena, California Perceptual organization is thought to involve an analysis ofboth textural discontinuities and perceptual grouping. In earl
Oracle's approach to "partitioning" LMS's interpretation of "installed and/or running" "Soft partitioning" vs. "hard partitioning", and Oracle's "Partitioning Policy" Oracle in VMware and the Mars case Case background - Oracle initiated an audit of Mars and requested deployment details for the
Oracle 12c R1 Interval-Reference partitioning Partition Maintenance on multiple partitions Asynchronous global index maintenance Online partition MOVE, Cascading TRUNCATE, Partial indexing Oracle 12c R2 Auto-list partitioning Multi-column list [sub]partitioning Online partition maintenance operations Online table conversion to partitioned table
Lecture #1: Bits, Bytes, and Binary CS106E Spring 2018, Young The binary number system underlies all modern computers. In this lecture we'll take a look at the binary number system and some of the implications of using binary numbers. Having a solid grounding in binary will set us up to explore digital images and digital music in the next two .
Binary compounds are those that are composed of only two elements. There are three types of binary compounds: binary covalent compounds, binary ionic compounds and binary acids. Examples of binary covalent compounds include water (H 2O), carbon monoxide (CO), and carbon dioxide CO 2. The naming convention for bina
And there are also only two options of the outcome that is: right or wrong. Hence, Binary Options are also known as Binary Bets or Binary Transactions. This simplicity, the simple two-way choice, is one of the main reasons why Binary Options have been so successful since their beginning. Binary Options exist since 2008 and in 2012 it became .
