{"id":"5d7f0c5f-50a6-4688-b3bb-0097a739d015","arxiv_id":"2509.00231","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"FHT2SP computes a Hough transform in O(w h ln^3 w) time with line-approximation error below λ + 1/2, a constant independent of image size.","lead":"This paper presents FHT2SP, a fast Hough transform that keeps approximation error bounded by a constant for any image size while running in near-linear-log-cubed time. It works by replacing each pixel with a superpixel block and then applying an existing fast transform to the enlarged image.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1 lacks the slope condition bh ≤ bw; without it the EDT bound does not apply to the transformed line and the error guarantee fails.","rationale":"The reader's weakest assumption targeted the EDT bound constant and the informal 'closest superpixel' step. Those are secondary: the EDT constant could be absorbed into the meta-parameter, and the informal step can be made rigorous by analyzing the modulo structure of P (yielding |e| < λ + 1/2). The more serious gap is the unstated requirement bh ≤ bw, without which the EDT bound is applied to a line that is outside FHT2DT's slope range. For the paper's main square-superpixel construction this condition holds, so the headline O(wh ln^3 w) claim is likely valid; however, Theorem 4.1 as stated is not fully correct and should be revised. This warrants a conditional verdict rather than full acceptance.","tokens_in":10490,"tokens_out":41739,"duration_ms":439155,"concrete_test":"On a 64×64 image, set bw=1, bh=3, λ=0.75. The theorem's condition holds (2log2(64)+13=25 < 12·0.75·3=27), but bh/bw=3>1. Run FHT2SP and compute the actual maximum orthotropic error ESP over all (t,s). If ESP ≥ λ+0.5=1.25, the theorem's conclusion fails without bh ≤ bw, confirming the missing slope constraint. A second run with bh=5 further tests the steep-slope regime.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 4.1 claims ESP < λ+1/2 for any odd bw, bh satisfying 2log2(wbw)+13 < 12λbh. The proof relies on the FHT2DT error bound EDT(wbw, hbh) ≤ log2(wbw)/6 + 7/12, but FHT2DT only approximates lines with slopes in [0,1]. The transformed line byC(t,s) in the expanded image (Eq. 2) has slope (bh/bw)·t/(w−1), which can exceed 1 when bh > bw. The subsequent modulo-based st-parametrization (Eq. 3) then represents [byC] as a wrapped line with slope ≤1, which can deviate from the true byC far more than the claimed 1/2 endpoint-rounding error. The inequality in Theorem 4.1 does not enforce bh ≤ bw, so the chain (7)–(8) is invalid for such parameter choices. This is a load-bearing gap because the theorem is the paper's central accuracy guarantee; although Theorem 4.3 uses square superpixels (bh=bw) and thereby avoids the issue, the theorem as stated is overbroad and the proof is incomplete.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes FHT2SP, a superpixel-based fast Hough transform for arbitrary-sized images. Each input pixel is replaced by a bw×bh block whose central column carries the pixel value, the enlarged image is processed with the authors' earlier FHT2DT algorithm, and the resulting Hough image is subsampled. The paper claims O(wh ln^3 w) computational complexity while maintaining a maximum orthotropic approximation error below λ+1/2 for a user-chosen meta-parameter λ∈(0,1]. Theorem 4.1 states the accuracy bound under a condition relating bw, bh, w, and λ; Theorem 4.2 bounds the complexity in terms of the expanded image size; Theorem 4.3 derives the O(wh ln^3 w) result for square superpixels whose linear size is the smallest odd integer satisfying the Theorem 4.1 condition. Experiments on square images up to 4096×4096 report normalized runtime trends consistent with the asymptotic claim and compare accuracy against ASD2, KHM, and FHT2DT.","tokens_in":10852,"tokens_out":8299,"duration_ms":96566,"significance":"If the accuracy proof can be made rigorous, the paper makes a useful contribution: it shows a concrete way to combine the computational efficiency of arbitrary-size fast Hough transforms with constant-bounded approximation error, a trade-off that previous algorithms could not achieve in this regime. The generalization of Brady's superpixel concept to non-power-of-two and non-square blocks is conceptually interesting, and the availability of an open-source Python implementation (the adrt library) is a practical strength. The complexity argument is clean and, apart from the accuracy issue, reduces correctly to the known FHT2DT bounds. However, the central accuracy theorem currently contains load-bearing gaps, so the claimed 'arbitrary-shaped' superpixel generality is not yet established.","major_comments":[{"comment":"The proof applies the FHT2DT error bound EDT(wbw, hbh) ≤ log2(wbw)/6 + 7/12 to the line [byC](bt,bs). That bound is for lines with slopes in [0,1] (predominantly horizontal lines). However, the transformed line byC in Eq. (2) has slope (bh/bw)·t/(w−1), which exceeds 1 whenever bh > bw. The modulo-based definition in Eq. (3) can wrap the endpoint difference to produce a line of slope ≤1, but that wrapped line is not the original straight segment and can deviate from byC by more than the 1/2 endpoint-rounding error. The theorem's condition 2log2(wbw)+13 < 12λbh does not enforce bh ≤ bw, so the chain (7)–(8) is invalid for such parameter choices. The theorem as stated is overbroad; the proof needs either an explicit slope condition (e.g., bh ≤ bw) or a separate argument that the EDT bound applies to the wrapped line. Note that Theorem 4.3 uses square superpixels (bh = bw) and is therefore n","section":"§4.1, Theorem 4.1, Eqs. (2)–(4) and (7)–(8)"},{"comment":"The step from ∥PDT(bt,bs)−byC(t,s)∥_{bI} < λbh to ∥PSP(t,s)−l(t,s)∥_I < λ+1/2 is not rigorously justified. In particular, the assertion that a pattern within λbh of byC intersects central columns only of superpixels closest to those traversed by byC, and the subsequent appearance of the additive 1/2 term, are informal. The subsampling operation involves both a division by bh and a rounding, so the error amplification or contraction needs a precise worst-case analysis. Since Eq. (9) is the conclusion of the accuracy proof, this gap is load-bearing for Theorem 4.1.","section":"§4.1, Eq. (9) and the 'closest superpixels' step after Eq. (8)"},{"comment":"The line [byC] connects the rounded endpoints (0, [byL]) and (wbw−1, [byR]) in the expanded image, so its st-parametrization should be [byC](x) = bs + bt/(wbw−1)·x, not bs + bt/(w−1)·x as written. As printed, Eq. (4) does not describe the line through the rounded endpoints, and the subsequent identification of [byC] with the FHT2DT line of parameters (bt,bs) breaks. This looks like a typo, but it must be corrected because the proof of Theorem 4.1 relies on Eq. (4).","section":"§4.1, Eq. (4)"}],"minor_comments":[{"comment":"The sentence 'for bw ≤ bh, the FHT2SP discrete lines are also patterns' would benefit from a short explanation; the condition for pattern continuity is bw/bh ≤ 1, and the current wording is easy to misread as (or conflate with) the slope condition needed in Theorem 4.1.","section":"§4.1, text near Eq. (5)"},{"comment":"Typo: 't ans s' should be 't and s'.","section":"§4.1, Eq. (9)"},{"comment":"The pseudocode bI(kbw+bn, mbh:(m+1)bh) ← I(k,m) should clarify that the assignment fills the whole column; the notation is slightly ambiguous.","section":"Algorithm 1, line 7"},{"comment":"Reference [23] gives an access date '2025-13-07', which is not a valid date; the day/month appear transposed.","section":"References"},{"comment":"The legend entries '1.0', '0.75', '0.625' would be clearer if labeled with the corresponding λ values, since the reader must match them to the curves.","section":"§5, Figure 3(b)"}],"recommendation":"major_revision","confidential_remarks":"The paper's central idea is promising and the complexity analysis is essentially sound. The main obstacle is Theorem 4.1: as stated, it overclaims the scope of the accuracy bound, and the proof has a missing slope condition plus an informal rounding step. These are fixable, and Theorem 4.3—which uses square superpixels—may already be correct, but the manuscript currently does not support the 'arbitrary-shaped superpixel' claim. I would encourage the authors to revise the theorem, tighten the proof of Eq. (9), and correct Eq. (4). The experiments are supportive but mostly on square images; after revision they should ideally include a non-square case or explicitly state that only square superpixels are considered in practice."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the core idea is good, but Theorem 4.1 as stated has a genuine hole. The paper extends Brady's superpixel trick to arbitrary shapes and bolts it onto your own FHT2DT, getting O(wh ln^3 w) complexity with constant-bounded error. That's a real point in the tradeoff space, and the complexity derivation is clean. The experiments, especially the Shepp–Logan comparison, support the square-superpixel version. The heavy reliance on your prior FHT2DT bound is a dependency, not a circle; that's fine.\n\nThe problem is in the proof of Theorem 4.1. The chain (7)–(8) invokes the FHT2DT error bound for the line [byC] from Equation (4). But that bound only applies to slopes in [0,1]. When bh > bw, the transformed line byC in Equation (2) has slope (bh/bw)·t/(w−1), which can exceed 1. The modulo operation in Equation (3) then represents [byC] as a wrapped line with slope at most 1, and that wrapped line can be far from the original byC—much farther than the claimed 1/2 endpoint-rounding error. The proof silently identifies the two. Your stress-test note is right: the theorem is overbroad as stated.\n\nThat said, the fix is easy: add the condition bh ≤ bw (or restrict to square superpixels). Theorem 4.3 and the experiments already use square superpixels, so the paper's main asymptotic claim survives. The accuracy bound for the square case is plausible, though the '+1/2' step after Equation (9) is still a bit hand-wavy—it needs a sentence or two pointing to why the 'closest superpixel' argument works once slopes are bounded.\n\nOther soft spots are minor: the memory consumption is honestly acknowledged but severe (a 30k×30k effective image for 1024×1024 input at λ=1/8 is a lot), and the proof of Theorem 4.2 is just a reduction to FHT2DT, which is fine. Citation pattern is appropriate, including self-citations to the FHT2DT paper; no padding.\n\nWho's this for? People working on fast Hough/Radon transforms who care about the accuracy–complexity frontier. It deserves a serious referee, but the referee should send it back for a revised Theorem 4.1 rather than accept as is.","headline":"A solid complexity-accuracy tradeoff with a real proof gap in Theorem 4.1; fix the slope restriction and it's a decent paper.","tokens_in":11268,"tokens_out":5470,"would_cite":true,"duration_ms":65781,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that replacing each pixel with a sparse block lets a fast Hough transform keep line-approximation error below λ + 1/2 at O(wh ln^3 w) cost, for images of any shape.","keywords":["Hough transform","fast Hough transform","discrete Radon transform","Brady-Yong algorithm","superpixel","orthotropic error","approximation error","arbitrary-shaped images"],"falsifier":"Compute the FHT2DT error EDT(w,h) for large random (t,s) on images of many sizes; if it ever exceeds (1/6) log2 w + 7/12, the constant behind Theorem 4.1 collapses. Then run FHT2SP with the smallest odd bx satisfying 2 log2(w bx) + 13 < 12 λ bx and measure the maximum orthotropic error; any value reaching or exceeding λ + 1/2 would falsify the main accuracy claim. Also, if normalized complexity TSP(n)/(n^2 ln^3 n) fails to stay bounded as n grows, Theorem 4.3 is wrong.","tokens_in":10452,"feed_emoji":"📐","tokens_out":8842,"duration_ms":99648,"temperature":0.7,"pith_summary":"This paper claims that a Hough transform can be both fast and accurate on images of any shape, a combination previously split between two families of algorithms. The proposed FHT2SP algorithm pads each pixel into an odd-sized block with a single non-zero central column, runs the arbitrary-size FHT2DT transform on the padded image, then subsamples the result. Theorems 4.1–4.3 state that with a suitably chosen block size the line-approximation error is bounded by a constant λ + 1/2 independent of image size, while the arithmetic cost is O(wh ln^3 w) for a w × h image. This matters because large-image applications would no longer have to choose between linearithmic speed with growing error, or constant error at near-cubic cost. Experimental timings and error measurements on images up to 4096 × 4096 support the bounds.","feed_headline":"Constant-accuracy Hough transform runs at near-optimal speed","feed_subtitle":"Generalized superpixels keep line-approximation error under a constant at any image size, with complexity O(wh ln^3 w).","key_machinery":"The superpixel expansion: each input pixel becomes a bw × bh block with a single non-zero column at index bn = (bw − 1)/2 and zeros elsewhere, followed by an FHT2DT transform on the expanded image and a coordinate subsampling of the output. The expansion rescales geometric error—an error smaller than λ bh in expanded coordinates becomes smaller than λ + 1/2 after mapping back to original pixel coordinates. Choosing the smallest odd superpixel side that satisfies the accuracy inequality makes that side grow only like O(log w), converting the FHT2DT cost on the expanded image into O(wh ln^3 w).","core_discovery":"The paper's central claim is that a Hough transform can hold its geometric line-approximation error to a constant while retaining near-optimal computational complexity, for images of arbitrary width and height. The proposed FHT2SP algorithm replaces every input pixel with a bw × bh block whose central column carries the pixel value and whose other entries are zero, runs the arbitrary-size FHT2DT transform on the expanded image, and then subsamples the resulting Hough image at coordinates corresponding to the original lines. Under the condition 2 log2(w bw) + 13 < 12 λ bh, Theorem 4.1 bounds the maximum orthotropic error by λ + 1/2, a constant independent of image size. Theorem 4.2 bounds the","pith_inferences":["A natural next test is rectangular images with anisotropic superpixels bw ≠ bh: the theory permits them, but the experiments are square-only, and anisotropic blocks could cut memory when line slopes are biased.","The memory cost of the w bw × h bh expansion is the practical ceiling; an in-place or streaming version of FHT2DT, which the paper identifies as future work, would unlock very large inputs.","The same 'pad, transform, subsample' pattern may be portable to other discrete Radon or tomography backprojection algorithms, with a similar log-factor cost for constant error.","Because bn is fixed at the block center in the theorem, other placements of the non-zero column would likely trade error for boundary effects—an untested degree of freedom."],"forward_implications":["With λ = 1/2, FHT2SP's worst-case error is below 1, the same order as DSLS-based accurate transforms, while its asymptotic arithmetic is O(wh ln^3 w) rather than near-cubic.","The meta-parameter λ acts as a speed–accuracy dial: smaller λ buys tighter error, and the required superpixel side grows only logarithmically with image width.","Because the algorithm accepts arbitrary w, h and non-square superpixels, line detection can run directly on native image shapes without padding to powers of two.","The sharp constant in Theorem 4.2 means the ln^3 w factor is not an artifact of a loose bound; it is the price of holding the error constant.","For large images, the paper's analysis and experiments place FHT2SP between fast-but-inaccurate transforms and accurate-but-slow transforms, with visual quality matching the accurate baselines."],"supporting_citations":[{"why":"Defines the original fast discrete Radon transform with dyadic patterns for power-of-two images; the base that the generalized algorithm extends.","marker":"[10]"},{"why":"Supplies the FHT2DT algorithm, its EDT(w,h) error bound, and its sharp computational-complexity bound used in Theorems 4.1 and 4.2.","marker":"[11]"},{"why":"Introduces the k × k superpixel construction with one non-zero column and the rest zero, which the paper generalizes to arbitrary shapes.","marker":"[19]"},{"why":"Provides the ASD2 accurate-transform baseline built on digital straight-line segments, used for accuracy and runtime comparison.","marker":"[15]"},{"why":"Provides the KHM accurate-transform baseline with constant 1/2 error, used for accuracy and runtime comparison.","marker":"[16]"},{"why":"Documents the FHT2DT variant and pseudocode used inside FHT2SP as the core summation procedure.","marker":"[20]"},{"why":"Supplies the Lambert W function estimates used to prove the optimal superpixel side is O(log w) in Theorem 4.3.","marker":"[21]"}],"fun_headline_variants":["Hough transform: constant error, near-optimal speed","Fast Hough with bounded error for any image shape","Superpixel Hough keeps error low at scale","Arbitrary-size Hough: constant accuracy, O(wh ln^3 w)","Hough transform error bounded, speed near-optimal"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The whole accuracy bound rests on the previously established estimate that FHT2DT's line-approximation error is at most (log2 w)/6 + 7/12 with exactly that constant; if that constant is not right for large images, the λ + 1/2 guarantee does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Hough transform: constant error, near-optimal speed","Fast Hough with bounded error for any image shape","Superpixel Hough keeps error low at scale","Arbitrary-size Hough: constant accuracy, O(wh ln^3 w)","Hough transform error bounded, speed near-optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000482,"raw_usage":{"total_tokens":2252,"prompt_tokens":812,"completion_tokens":1440,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":556,"completion_tokens_details":{"reasoning_tokens":1369}},"tokens_in":556,"tokens_out":1440,"duration_ms":11410,"temperature":1.0,"reasoning_tokens":1369,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:48:56.122881+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the FHT2DT error EDT(w,h) for large random (t,s) on images of many sizes; if it ever exceeds (1/6) log2 w + 7/12, the constant behind Theorem 4.1 collapses. Then run FHT2SP with the smallest odd bx satisfying 2 log2(w bx) + 13 < 12 λ bx and measure the maximum orthotropic error; any value reaching or exceeding λ + 1/2 would falsify the main accuracy claim. Also, if normalized complexity TSP(n)/(n^2 ln^3 n) fails to stay bounded as n grows, Theorem 4.3 is wrong.","supporting_citations":[{"cited_title":"Fast parallel discrete approximation algorithms for the radon transform,","cited_arxiv_id":null,"evidence_quote":"Defines the original fast discrete Radon transform with dyadic patterns for power-of-two images; the base that the generalized algorithm extends."},{"cited_title":"A fast discrete approximation algorithm for the radon transform,","cited_arxiv_id":null,"evidence_quote":"Introduces the k × k superpixel construction with one non-zero column and the rest zero, which the paper generalizes to arbitrary shapes."},{"cited_title":"On a fast hough/radon trans- form as a compact summation scheme over digital straight line segments,","cited_arxiv_id":null,"evidence_quote":"Provides the ASD2 accurate-transform baseline built on digital straight-line segments, used for accuracy and runtime comparison."},{"cited_title":"Ensemble computation approach to the Hough transform","cited_arxiv_id":"1802.06619","evidence_quote":"Provides the KHM accurate-transform baseline with constant 1/2 error, used for accuracy and runtime comparison."},{"cited_title":"Generalization of brady-yong algorithm for fast hough transform to arbitrary image size,","cited_arxiv_id":null,"evidence_quote":"Documents the FHT2DT variant and pseudocode used inside FHT2SP as the core summation procedure."}],"review_version":1}