{"id":"429ade16-d370-4937-aa36-81b760d6c124","arxiv_id":"1908.03323","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"Variational level-set models with ADMM/FFT solvers yield exact convex hulls for clean binary images and approximate hulls that ignore outliers.","lead":"This paper proposes two level-set based variational algorithms that compute the convex hull of 2D binary images, one exact and one robust to outlier pixels. The outlier-tolerant model is the main new contribution, aimed at image-processing tasks where masks are noisy.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The exactness claim depends on an unproven converse of Theorem 2.1: Δφ≥0 in slev_c^φ does not imply convexity for multi-component objects, so the (EC) minimizer can be a disconnected union rather than the convex hull.","rationale":"The paper's most valuable contribution is the outlier-penalized model (OC), which addresses a real gap in the literature, and the numerical section is thorough: nine images, multiple object cases, COCO examples, and parameter-sensitivity studies. The exact model's central claim, however, rests on the characterization of convexity by Δφ≥0 in a sublevel set. The text proves only that convexity implies this inequality (Theorem 2.1); the reverse implication is asserted by reference to [25,32] and is not obviously true. The two-disk counterexample shows that with c=0 the constraint is satisfied by a disconnected, nonconvex set, and since that set has smaller area and lower energy than the true convex hull, the global minimizer of (EC) cannot be the hull. The paper's own Figure 7 shows that the choice of c determines whether the output is separate hulls or one hull, so the 'exact' model requires a data-dependent c threshold to deliver the convex hull of multiple objects. The error tables do not test this regime: they use c=20 on single objects. This is a load-bearing gap, but it is repairable; an explicit sufficiency proof under a connectedness or automatic c-selection condition would settle it. The outlier model is heuristic and its errors under 10% are acceptable as an approximate method, so it is less affected. The reader's CONDITIONAL verdict is appropriate; no verdict change is needed.","tokens_in":14599,"tokens_out":11034,"duration_ms":119773,"concrete_test":"Run Algorithm 4.1 on a binary image of two well-separated disks (e.g., radius 20, centers 80 apart on a 256×256 grid) with c=0 and with c=30. Compare {φ≤0} to the true convex hull and to the union of the two disks using the paper's Hausdorff error (5.1). If the c=0 output is the disconnected union (large error vs. the hull) while the c=30 output is the hull, then the exactness claim is parameter-dependent and the sufficiency of (2.5) is disproved for multi-object inputs; if the c=0 output is unexpectedly convex, the counterexample must be re-examined.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1 builds the 'exact' model (EC) on the assertion, imported from [25,32], that the constraint Δφ≥0 in slev_c^φ (Eq. (2.5), used as (3.7)) characterizes convexity of the zero sublevel set. Theorem 2.1 only proves the forward direction: convexity of Ω1 implies Δφ≥0 in Ω. The converse is not proved in this text, and it is false for disconnected sets. Take Ω0 as two disjoint disks. The SDF of the union satisfies |∇φ|=1 and Δφ=1/r>0 inside each disk and on its boundary, hence Δφ≥0 in slev_0^φ. But slev_0^φ is the union of the two disks, which is not convex. This feasible set has smaller area and smaller ∫−φ than the true convex hull, so the minimizer of (EC) with c=0 is the disconnected union, not the convex hull. For the model to return the hull of multiple objects, c must be chosen larger than half the inter-object distance, a data-dependent threshold not derivable from the model; the paper's discussion in Section 5.1 (Figure 7) confirms this, but the abstract's 'exact model ... for one or multiple objects' is therefore only conditional. The 2% error tables (Table 1) do not address this because they use c=20 with single objects. Thus the central exactness claim is not established as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes two level-set variational models for computing the convex hull of binary objects in 2D. The exact model (EC) minimizes a weighted objective in the signed distance function φ subject to the Eikonal constraint |∇φ|=1, a sublevel-set Laplacian constraint Δφ≥0, and the enclosure constraint φ≤0 on the input set; the outlier-robust model (OC) replaces the hard enclosure by a hinge penalty λ(mφ)_+. Both models are solved by ADMM with FFT-based solvers under a periodic boundary assumption. Numerical tests on nine images report relative Hausdorff errors below 2% against quickhull for the exact model and below about 10% for the outlier model, with additional experiments on multiple objects, noisy images, and isolated point sets.","tokens_in":15059,"tokens_out":10676,"duration_ms":117258,"significance":"The outlier-robust formulation is a useful idea: classical convex hull algorithms do not tolerate outliers, and the proposed continuous level-set relaxation offers a differentiable alternative that can be extended to higher dimensions. The reported experiments are reasonably convincing at the level of the examples shown, and the parameter stability across images is a practical strength. However, the central theoretical claim of exactness is not established in the manuscript: the convexity characterization is imported from prior work without a self-contained proof, the objective functional is modified heuristically, and the multiple-object exactness claim is conditional on a data-dependent choice of the parameter c, as the paper's own Section 5.1 demonstrates.","major_comments":[{"comment":"The constraint Δφ≥0 in slev_c^φ is used as a convexity-enforcing condition, but Theorem 2.1 proves only the forward direction: convexity of Ω1 implies Δφ≥0 in Ω. The converse is not proved in this manuscript and, as stated, is false for multi-component sets. For Ω0 consisting of two disjoint disks, the SDF of the union satisfies |∇φ|=1 and, inside each disk, Δφ=1/r>0, so Δφ≥0 holds in slev_0^φ even though the zero sublevel set is disconnected and nonconvex. Since the union has smaller area than the true convex hull, the minimizer of (EC) with c=0 is not the convex hull. Section 5.1 (Figure 7) implicitly acknowledges this by requiring c to exceed half the inter-object distance to merge objects, a data-dependent choice that is not derived from the model. The abstract's claim of an exact model for one or multiple objects is therefore only conditional; the authors should either prove the needed converse with precise conditions on c, Ω0, and the periodic setting, or substantially restate the claim.","section":"Section 2, Theorem 2.1 and Eq. (2.5); Section 3.1, Eq. (3.7)"},{"comment":"The objective is switched from the area functional (or the equivalent ∫-φ functional) to the weighted combination ∫(-ωφ + μ|∇H(φ)|) with the justification \"Based on our numerical test.\" No theorem or parameter analysis shows that the minimizer of this weighted functional under constraints (3.6)-(3.8) coincides with the SDF of the convex hull. For a pair of distant disks, the perimeter term can favor the disconnected union over the hull depending on the relative values of ω and μ, so the exactness claim depends on an unexamined parameter regime. The authors should either prove a range of (ω,μ) for which the minimizer is the convex hull, or explicitly present (EC) as a heuristic model whose empirical accuracy is measured in Section 5.","section":"Section 3.1, Eq. (3.5)"},{"comment":"The periodic boundary assumption changes the notion of distance in the SDF (2.1): the distance is to the boundary of the periodic replication of the object, not to the original object's boundary. Thus for objects whose support is close to the image boundary, the model computes a hull of the periodically replicated union, which can differ from the convex hull of the input object. The suggestion to pad zeros is practical but is not analyzed; an object near the boundary of the padded domain still interacts with its periodic copies. This limitation should be stated explicitly and tested, or the model should be restricted to objects with sufficient margin.","section":"Section 2, periodic extension paragraph"},{"comment":"The φ update in Algorithm 4.1 is described as an approximation: Eq. (4.21) is obtained by moving nonlinear terms to the right-hand side and evaluating them at φ^t, and Eq. (4.22) further adds a proximity term. No proof is given that the fixed point of this approximate update solves the original optimality condition (4.20), nor that the ADMM scheme converges to a minimizer of (EC). Since the paper claims an exact model, the solver should be shown to converge to a solution of the stated constrained problem; otherwise the reported 2% errors are only evidence about the specific discretized algorithm, not about the variational model.","section":"Section 4.1, Eqs. (4.21)-(4.22)"}],"minor_comments":[{"comment":"The terms ρ1/2||Δφ−z_1^{t+1}||² and ρ2/2||∇φ−z_2^{t+1}||² appear to be swapped; they should read ρ1/2||∇φ−z_1||² and ρ2/2||Δφ−z_2||² to match the definitions z1=∇φ and z2=Δφ.","section":"Section 4.1, Eq. (4.19)"},{"comment":"The phrase \"we loot at the level-set curves\" should be \"we look at the level-set curves.\"","section":"Section 5.1, Figure 7 caption"},{"comment":"The table header \"F rog\" contains an unintended space; it should read \"Frog.\"","section":"Table 1"},{"comment":"The algorithm attributed to Gram in reference [12] is conventionally called the Graham scan; the spelling should be corrected.","section":"Section 1, introduction"},{"comment":"\"Here we use the same technique with [25]\" should be \"the same technique as in [25]\" or \"the same technique used in [25].\"","section":"Section 4.1, paragraph after Eq. (4.21)"},{"comment":"\"star fish\" is more standardly written as \"starfish.\"","section":"Section 5.3, Figure 15 caption"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's theoretical core is drawn from the authors' own prior work [25,32], and the present text does not state precisely which result is being imported or what the exact conditions are. Since the imported criterion fails for the multi-component case as stated in this paper, the authors should be asked to provide a self-contained statement and proof, or a precise citation with theorem number, of the convexity characterization they rely on. The numerical experiments are appropriate in scope, but the multiple-object experiments in Figures 7 and 8 lack quantitative comparison and should be augmented if the multiple-object claim is retained."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing to know: the outlier-robust model and its ADMM-FFT solver are the real contribution here; the 'exact' model's headline claim that the zero sublevel set is the convex hull for one or multiple objects is not actually proved, and the stress-test example (two disks) shows why. For c=0, the constraint Δφ≥0 in slev_0 is satisfied by the disconnected union, so the minimizer of (EC) can be non-convex. The paper's own Section 5.1 admits c must be chosen larger than half the inter-object distance to merge objects, which is data-dependent and not derived from the model. That doesn't sink the method for single objects, but it does sink the unqualified abstract claim.\n\nWhat's genuinely new: the λ(mφ)_+ outlier penalty gives a clean variational way to ignore isolated outliers in hull extraction, and the FFT-based ADMM solver is a plausible extension of the authors' convexity-prior machinery. The experiments on the Weizmann silhouettes show errors under 2% for the exact model and under 10% for the outlier model, and the multi-object demonstrations (cars, Pokemon) are visually sensible. The paper is clearly written and the discretization is spelled out.\n\nThe soft spots are proportionate. First, the convexity characterization is imported from [25,32] and only the forward direction is stated; the converse 'Δφ≥0 in slev_c implies convex' is asserted, not proved, and is false for disconnected sets. Second, the switch from ∫(1−H(φ)) to ∫−ωφ+μ|∇H(φ)| is justified 'based on numerical test' rather than by a proof that the minimizer is still the convex hull. Third, the periodic boundary assumption is an extra modeling choice that changes the distance geometry and is not fully interrogated. Fourth, there are a lot of free parameters (ω, μ, ν, λ, c, ρ's, δ) and the choice of c does real work in the multi-object case. No code or runtime comparison against, say, a robust CGAL-style hull with preprocessing is provided, so the practical claim of advantage is not fully quantified.\n\nWho this is for: people working on level-set shape priors and image-based hull extraction from noisy masks. It deserves a serious referee—the outlier model is worth engaging with—but the exactness claims need to be either proved or substantially qualified before publication.","headline":"The outlier model is a genuinely useful contribution, but the exact model's multi-object convexity claim rests on an unproven converse that fails for disconnected sets.","tokens_in":15504,"tokens_out":4442,"would_cite":false,"duration_ms":44621,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","68U10","35A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that the exact convex hull of one or multiple binary objects is the zero sublevel set of a minimizer of an area-based energy, subject to a signed-distance constraint and a Laplacian convexity constraint, and that the…","keywords":["convex hull","level set method","signed distance function","variational model","ADMM","outlier rejection","binary image","convexity constraint"],"falsifier":"Give Algorithm 4.1 a binary image whose exact convex hull is known, run it with the paper's parameters, and compare the returned zero sublevel set with quickhull; a relative Hausdorff error above 2% would contradict the reported bound. More directly, construct a periodic function with $|\\nabla\\varphi|=1$, $\\varphi\\le 0$ on a nonconvex set, and $\\Delta\\varphi\\ge 0$ in $\\mathrm{slev}_c^\\varphi$; if such a function exists for any $c>0$, the convexity criterion (2.5) is insufficient and the exact-model claim collapses.","tokens_in":66,"feed_emoji":"📐","tokens_out":7768,"duration_ms":134476,"temperature":0.7,"pith_summary":"This paper proposes two variational models that find convex hulls of 2D binary images by searching for a level-set function rather than polygon vertices. The first model minimizes the area of the zero sublevel set while forcing the signed distance function to satisfy $|\\nabla\\varphi|=1$, to be nonpositive on the object, and to have nonnegative Laplacian inside its sublevel sets; the paper claims this returns the exact convex hull. The second model replaces the enclosure constraint with a penalty on the distance from each point to the zero sublevel set, so outliers and noise can be excluded. Numerical experiments report relative Hausdorff errors under 2% for the exact model and under about 10% for the outlier model, and the method also handles multiple objects and isolated point sets.","feed_headline":"Variational model returns convex hulls with under 2% error","feed_subtitle":"A level-set model recovers the hull as a zero sublevel set; a relaxed version ignores outliers.","key_machinery":"The load-bearing object is the periodic signed distance function $\\varphi$, whose zero sublevel set $\\{x\\mid \\varphi(x)\\le 0\\}$ represents the hull. The identity doing the work is that, for a convex region, the curvature of level-set curves is nonnegative, and with $|\\nabla\\varphi|=1$ this curvature equals the Laplacian $\\Delta\\varphi=\\mathrm{div}(\\nabla\\varphi/|\\nabla\\varphi|)$; hence the constraint $\\Delta\\varphi\\ge 0$ inside the sublevel set is used to enforce convexity. The alternating direction method of multipliers splits the problem: $z_1$ is a normalized gradient projection, $z_2$ clips the Laplacian to be nonnegative inside the sublevel set, $z_3$ enforces nonpositivity on the object, and the $\\varphi$ update solves a fourth-order linear PDE by two second-order FFT inversions under periodic boundary conditions.","core_discovery":"The central claim is that the zero sublevel set of the minimizer of the exact model (EC), with objective $\\int_\\Omega(-\\omega\\varphi+\\mu|\\nabla H(\\varphi)|)\\,dx$, constraints $|\\nabla\\varphi|=1$, $\\Delta\\varphi\\ge 0$ in $\\mathrm{slev}_c^\\varphi$, and $\\varphi\\le 0$ on the input object, is exactly $\\mathrm{Conv}(\\Omega_0)$. Because the convex hull is the smallest convex set containing the object, minimizing its area under these constraints selects it. The relaxed problem (OC) adds $\\lambda(m\\varphi)_+$ to the objective and drops the enclosure constraint, so the hull can leave outliers outside when enclosing them is too costly. The paper reports that Algorithm 4.1 computes exact hulls with relative errors under 2% compared with quickhull, and Algorithm 4.2 filters most outliers with errors under roughly 10%.","pith_inferences":["We infer that the level-set formulation could serve as a differentiable convex-hull layer in learning pipelines, because the output $\\varphi$ is a smooth function of the input mask through the PDE solve, unlike vertex-based hull algorithms.","The parameter $c$ can be read as a convexity scale: small $c$ yields the minimal hull of each component, while larger $c$ merges components, producing a family of approximate hulls between component-wise and global hulls.","A natural testable extension is to run the same models on 3D binary volumes; the convexity criterion $\\Delta\\varphi\\ge 0$ in sublevel sets and the FFT solver extend formally, but the paper only claims 2D results."],"forward_implications":["If the exact model is correct, the convex hull of any binary mask can be obtained as a rasterized region $\\{x\\mid\\varphi(x)\\le 0\\}$ without extracting polygon vertices.","The same parameter $c$ in the constraint $\\Delta\\varphi\\ge 0$ in $\\mathrm{slev}_c^\\varphi$ controls whether separated objects receive individual hulls or one merged hull, since larger $c$ merges nearby convex regions.","The outlier model gives a convex hull that can ignore noise; adjusting $\\lambda$ trades off excluding outliers against including thin protruding parts of the object.","The method also applies to sets of isolated points, not only connected regions, as demonstrated in Section 5.3."],"supporting_citations":[{"why":"Supplies the theorem that a convex set's signed distance function has nonnegative Laplacian, and the FFT-based technique for solving the periodic PDEs.","marker":"[25]"},{"why":"Imported convexity shape prior establishing the equivalence between convexity and the nonnegative-Laplacian constraint in sublevel sets; the exact model's correctness rests on it.","marker":"[32]"},{"why":"Quickhull is the benchmark algorithm the paper compares against when reporting relative errors under 2%.","marker":"[3]"},{"why":"Defines the relative distance error formula used to quantify the accuracy of the computed hulls.","marker":"[28]"},{"why":"Shows how a single level-set function with the Laplacian constraint represents multiple convex objects, supporting the choice of c for merging or separating hulls.","marker":"[26]"},{"why":"Supplies the nine test images whose ground-truth masks are used in the exact-model experiments.","marker":"[1]"}],"fun_headline_variants":["Variational level-set model recovers convex hulls and filters outliers","Exact convex hulls via level sets, relaxed model handles outliers","Level-set minimization gives convex hulls with <2% error","New variational approach to convex hulls, outlier-resistant","Convex hulls from variational level sets, robust to outliers"],"cache_read_input_tokens":17536,"weakest_assumption_plain":"The whole construction rests on the imported claim that requiring the Laplacian of a periodic signed distance function to be nonnegative inside its sublevel sets is enough to guarantee the zero sublevel set is convex; if that equivalence fails for some $c$ or for periodic functions, the minimizer of (EC) need not be a convex hull.","fun_headline_variants_meta":{"raw":{"variants":["Variational level-set model recovers convex hulls and filters outliers","Exact convex hulls via level sets, relaxed model handles outliers","Level-set minimization gives convex hulls with <2% error","New variational approach to convex hulls, outlier-resistant","Convex hulls from variational level sets, robust to outliers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00128,"raw_usage":{"total_tokens":5203,"prompt_tokens":890,"completion_tokens":4313,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":506,"completion_tokens_details":{"reasoning_tokens":4227}},"tokens_in":506,"tokens_out":4313,"duration_ms":33822,"temperature":1.0,"reasoning_tokens":4227,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:17:40.118447+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Give Algorithm 4.1 a binary image whose exact convex hull is known, run it with the paper's parameters, and compare the returned zero sublevel set with quickhull; a relative Hausdorff error above 2% would contradict the reported bound. More directly, construct a periodic function with $|\\nabla\\varphi|=1$, $\\varphi\\le 0$ on a nonconvex set, and $\\Delta\\varphi\\ge 0$ in $\\mathrm{slev}_c^\\varphi$; if such a function exists for any $c>0$, the convexity criterion (2.5) is insufficient and the exact-model claim collapses.","supporting_citations":[{"cited_title":"Convex Shape Priors for Level Set Representation","cited_arxiv_id":"1811.04715","evidence_quote":"Supplies the theorem that a convex set's signed distance function has nonnegative Laplacian, and the FFT-based technique for solving the periodic PDEs."},{"cited_title":"Convexity Shape Prior for Level Set based Image Segmentation Method","cited_arxiv_id":"1805.08676","evidence_quote":"Imported convexity shape prior establishing the equivalence between convexity and the nonnegative-Laplacian constraint in sublevel sets; the exact model's correctness rests on it."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Quickhull is the benchmark algorithm the paper compares against when reporting relative errors under 2%."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the relative distance error formula used to quantify the accuracy of the computed hulls."},{"cited_title":"Luo, X.-C","cited_arxiv_id":null,"evidence_quote":"Shows how a single level-set function with the Laplacian constraint represents multiple convex objects, supporting the choice of c for merging or separating hulls."},{"cited_title":"Alpert, M","cited_arxiv_id":null,"evidence_quote":"Supplies the nine test images whose ground-truth masks are used in the exact-model experiments."}],"review_version":1}