In ICCV 2007
Separating Parts from 2D Shapes using Relatability
Xiaofeng Mi and Doug DeCarlo Rutgers University Department of Computer Science & Center for Cognitive Science
Abstract
It’s often important to analyze shapes as made up of parts. But there are two ways to think of how parts fit together. We can characterize the remainder of a shape after a part is removed; here we want to cut the shape so what remains has the simplest possible structure. Alternatively, we can cut out the part so that the part itlf takes on a simple shape. The cuts do not directly give ri to a gmentation of the shape; a point inside the shape may associate with the part, the remainder, neither, or both. We prent a new model for reconstructing the cuts bad on the differential geometry of smoothed local symmetries. The model takes into account relatability (which characterizes clean cuts) to determine part boundaries. Our approach complements and unifies existing work on partbad gmentation of shape, and can be ud to construct interesting simplifications of shapes.
1. Introduction
Perception rearch strongly suggests that the human visual system interprets and reprents the shapes of objects by organizing them into perceptual parts [8, 25]. This insight has been the inspiration for a range of approaches in computer vision for analyzing the part structure of 2D shapes [16, 21, 23]. A common theme in this work is the specification of computations that analyze a shape into a hierarchy by partitioning it bad on its part structure. In the schemes, each point inside the shape belongs to exactly one part, and the parts themlves are compod together into a tree which groups primitive parts naturally into progressively larger complex structured shapes. The schemes provide an exciting foundation for higher-level process such as object recognition. Psychophysical rearch also suggests an alternative conception of how people e parts in shape, however. Koenderink and van Doorn [14], for example, obrve that artists conceptualize shapes as though all the significant parts are elliptical regions, while the hyperbolic patches that connect the parts is insignificant “glue”. Hoff-
man and Richards’s characterization of transversality [8]— according to which the perceptual system understands some articulated objects as complexes of overlapping and interpenetrating elliptical parts—appeals to a similar principle. This view of parts leads to an analysis of shape in which parts
do not directly give ri to a gmentation of the shape. A point inside the shape may associate with exactly one part, with multiple parts, or with no part at all. Figure 1 illustrates the difference between the two conceptions of part structure. It shows two ways of understanding a fish-shape as built from a body and a tail. The gmentation of Figure 1(b) analyzes each point on the shape either as part of the body or as part of the tail. This is the typical approach for shape analysis in computer vision. The analysis of Figure 1(c), in contrast, describes the body and the tail as elliptical mass glued together along their boundary by a hyperbolic transition region. In Figure 1(c), the fish is body plus tail, but not every point in the fish comes from the body or the tail. This conception of object structure is more common in CAD and computer graphics [10, 19] in applications that construct models from parts. Accordingly, we believe that vision techniques that recognize this part structure have a key role to play in a range of interactive applications, such as interfaces for sketching, manipulating and depicting shape.
(a)
(b)
oad是什么(c)
Figure 1. Two ways of analyzing a fish-shape into its body and tail.
This paper offers the first computational investigation of 2D shape analysis that allows for transitions between parts. We make three contributions. • We introduce a computational model that describes the extent and the prominence of the transition areas between a part and the rest of the shape. • We show that the idea of transitions between parts gives ri to a unified mathematical characterization of
neck
limb short cut
Figure 2. Part structure examples
local shape organization. In particular, it distinguishes extended wholes uniformly from various asmblies of parts, such as limbs, necks, and short-cuts. • We provide an implementation of our model, bad on smoothed local symmetry, and illustrate its applicability in interfaces for shape through a study of quenced deletion of parts. The key to our approach is relatability, a measure of how easily two parate curve gments at different locations in space can be joined together into a
single smooth curve. Relatability is typically invoked to explain contour completion behind an occluder [11, 24]. Our approach is to find part boundaries that cut through corresponding points across a local symmetry axis. We place them where the relatability increas quickly, suggesting that we have moved through a transition region to a natural part. This combination of symmetry and relatability allows us to work with simple and robust clear cas of the general definition of relatability and to build on work on part-bad gmentation using symmetry. After a review of related work, we summarize our approach in Section 2. Then we derive mathematical characterizations of local symmetries (Section 3) that are relevant for modeling boundary strength (Section 4). Then we describe our implementation (Section 5) and discuss our results.
Singh et al. [26] further argue for a short-cut rule involving both boundaries and regions: the cuts hit a single local curvature minimum but cross a local axis of symmetry. The three types of connections are shown in Figure 2. Our approach continues this tradition of exploiting both region and boundary information to describe part structure. All of the prior approaches partition shapes into pairs of parts using a single cut that connects two distinct points on the boundary with a line or curve that remains inside the shape—as shown in Figure 1(a) and (b). Rom and Medioni [21] do recognize that a transition region must be adjusted to remove parts cleanly, but they assume that transitions ar
e located in fixed locations around prespecified part boundaries. Their model is good enough to find new symmetries in simplified shapes—an insight we draw from their approach—but we greatly simplify and generalize this insight by modeling transitions explicitly. Junctions between parts have been described as well. Blum and Nagel [3] define ligatures as portions of the symmetry axis that reprent gments of the boundary with negative curvature. August et al. [1] further analyze ligatures to develop more stable descriptions using the medial axis, by simply ignoring the ligatures when forming the parts. Our approach goes beyond this by characterizing parts in a smooth and uniform way using relatability. We revisit the considerations after we prent our model.
2. Our Approach
Here we summarize our approach for parating parts from shapes. Working from the differential geometry of smoothed local symmetries, we can identify reasonable locations to cut the shape so that when a part is removed, no trace of it remains on the rest of the shape. We can do the same for the part itlf, so that it takes on a simple shape. Thus, our approach aims to ignore the transitional region of the shape between the part and the rest of the shape— e Figure 1(c). The remainder of this ction describes smoothed local symmetries [4], and our methodology for locating cuts.
1.1. Related Work
A common computational approach to shape reprentation is to infer a skeleton that describes the local symmetries of the shape [2, 4, 13, 22]. The reprentations enjoy a convergence with psychophysical models [15], and also form the basis of much of the work on the computation of part structure. Approaches bad on local symmetries can locate parts by detecting singularities (shocks) in the entropy scale space of the shape [13]—a formalism that operationalizes the u of symmetry and size to guide part decomposition. The skeletal models can be improved by taking into account the boundary of the shape. In general, negative curvature minima are likely boundaries between perceptual parts [8], and De Winter and Wagemans [5] have shown through psychophysical studies that parts crucially depend both on the boundary and on region geometry. The computational approach of Siddiqi and Kimia [23] achieves this by using symmetry axes to find one kind of part—necks—and using boundary curvature to find another kind of part—limbs.
2.1. Smoothed Local Symmetries (SLS)esnce of beauty
Axial reprentations [22] describe local symmetries in terms of a generator that sweeps along the symmetry axis. For smoothed local symmetries [4] (SLS), the shape is the union of ribbons using a line gment that varies in length along the axis. We start with a simple 2D shape who boundary is reprented by a C 2 continuous curve α : I → R2 , where α and the domain I are constructed to fo
rm an arc-length parameterization. Consider a line gment with end-points at α(u) and α(v) where u and v ∈ I are parametric locations on the boundary curve—e Figure 3(a). The length of the
C(v,u) α’ (u) θ α(v) ϕ L(u,v) α’ (v) C(u,v) p α(u) α(v)
3. Differential Geometry of SLS
u) r(v,
,v) r(u
α(u)
In this ction, we will first study the differential properties of the length L and angles θ and ϕ given any pair of points (u, v) on the curve. Then we limit the ca when the two points form a local symmetry [4, 7]. Details of the derivations are provided in Appendix A.
Figure 3. (a) Local geometry of a generator; (b) Partial tangent circles C(u, v) and C(v, u).
3.1. Geometry of tangent circles
The partial tangent circle C(u, v) is the circle that is tangent to the curve at α(u) and pass through α(v)—its raL dius is r(u, v) = 2 sin θ . See Figure 3(b). We can now state ˜ the partial derivatives of L, θ and ϕ with respect to u and v: L = (− cos θ, cos ϕ) (1)
R π
R π
(a)
(b)
θ = −κ(u) +
1 1 2˜(u,v) , 2˜(v,u) r r 1 2˜(v,u) r
Figure 4. Shape and relatability profiles along symmetry axes
1 ϕ = − 2˜(u,v) , κ(v) − r
,
(2)
gment is simply L(u, v) = α(v) − α(u) , and its direc1 tion is p(u, v) = L(u,v) (α(v) − α(u)). Our description of relatability will require the turning angle between the unit tangents at u and v, which are written α (u) and α (v). Define the angle from α (u) to p as θ(u, v), and the angle from p to α (v) as ϕ(u, v), where θ, ϕ ∈ (−π, π]. Then, the total turning angle will just be θ(u, v) + ϕ(u, v). For the remainder of the paper, we assume (u, v) as the default parameters of the functions when the context is clear.
where κ is the curvature of α (convex parts of the shape have positive curvature). Finally, we state the following, which will be relevant in describing symmetries: (θ + ϕ) = −κ(u), κ(v) (θ − ϕ) = −κ(u) +
1 r (u,v) , −κ(v) ˜
+
1 r (v,u) ˜
.
(3)忍耐英文
2.2. Making cuts
Later in Section 4.1 we will e that the relatability R is defined as the total turning angle, θ + ϕ. We can obrve how R changes as the line gment sweeps along the spine—in this ca, we define the parameterization of the shape along the axis to be increasing in value as we move into the part. We first look within a part. The top row of Figure 4(a) shows veral planar primitives [6], while the cond row of Figure 4(a) shows R. In Figure 4(b), we give examples where the axis goes from one part into the other as well as the corresponding values of the relatability. We notice that the profiles of R going across parts exhibit certain characteristics that we don’t e within a part. Within a part, R starts at 2π and is monotone nonincreasing. When the axis leaves the body of one part and enters into another, it increas, until it totally enters into the other part. Thus, we can locate good places to cut by looking for where relatability increas quickly—where its derivative is positive and large. In the next ction, we derive the expressions needed to make such measurements on shapes.
To formalize the mathematical form of the symmetry, we define the asymmetry A(u, v) of u and v as the difference between θ and ϕ, “wrapped” to the interval (−π, π]. Specifically, A(u, v) is the angle in (−π, π] such that sin A = sin(θ − ϕ) and cos A = cos(θ − ϕ). Two points α(u) and α(v) form a symmetry pair when A(u, v) = 0, which is also known as a local symmetry by Brady and Asada [4]. They also d
efine the loci of mid-points of symmetry pairs as smoothed local symmetries (SLS).
3.2. Geometry along symmetries
By definition, the motion of the two sides of the symmetry pair along the SLS is perpendicular to the gradient of the asymmetry A. Suppo a small step ahead along the axis, ds, effects the parametric motion, du and dv, of the two sides, so that ds = 1 (α (u)du + α (v)dv)—e Fig2 ure 5. At a symmetry pair, θ = ϕ, A · (du, dv) = 0 and r = r(u, v) = r(v, u): the two partial tangent circles co˜ ˜ incide with each other and form a bi-tangent circle, and we can relate du and dv as follows (derived in a different way by Giblin et al. [7]): 1 − κ(u) du + r 1 − κ(v) dv = 0. r (4)
For a normal symmetry axis, the two sides of the symmetry pair move along the curve boundary in opposite directions,
α(v + dv) α(u + du) α(v) ds ds ds
环球职业在线教育
{
α(u)
L(u,v)
Figure 5. Local differential structure of the SLS axis
where wu = 1/r − κ(v) and wv = 1/r − κ(u). From (7) we find that changes in relatability are determined by two quantities: the relatability, and a weighted average of curvatures measured at the symmetry pairs. Note that the dR sign of ds⊥ does not depend on the direction of ds. Finally, we note that the cond derivative of L is proportional to the change of relatability. That is, d2 L dR = csc2 θ . ds2 ds⊥ ⊥ (8)
and thus du and dv have different signs. This occurs when (1/r − κ(u)) and (1/r − κ(v)) have the same sign [7], that is, the bi-tangent circle is either inscribe or circumscribe on both sides. Otherwi, the two sides will move along the curve in the same direction, resulting in a very unintuitive symmetry. The step ds along the SLS axis can be decompod into two components, which are measured perpendicular and parallel to p, as in Figure 5:
1 ds⊥ = 2 (du−dv) sin θ, 1 ds|| = 2 (du+dv) cos θwrong的反义词
Along smoothed local symmetries, a significant increa in dR relatability (a positive value of ds⊥ ) indicates a transition between parts: the crossing of a part boundary.
4.2. Transition strength
The value of (7) is scale dependent—it includes a curvature term. We can remove this scale dependence by multiplying it by r, the radius of the bi-tangent circle—this is proportional to the scale. Definition 4.1. The local strength of the part transition, B, of a symmetry pair is defined as the first derivative of relatability with respect to ds⊥ , normalized by the radius r: B=r dR . ds⊥
(5)
Typically, θ is far from zero and du and dv largely cancel each other when added. In this ca, the parallel component ds|| is very small compared with the perpendicular component ds⊥ . However, when θ is clo to zero, ds|| can dominate the growth of the SLS axis, in which ca, the symmetry axis does not intuitively reflect the symmetry structure of the shape. Thus, we only consider the perpendicular component ds⊥ . From (1) we can compute dL = L · (du, dv) = (−du + dv) cos θ, and: dL = −2 cot θ. ds⊥ (6)
4. Transitions between parts
We now describe how to compute the relatability in terms of local geometry along an SLS axis, show how it can be ud to locate part transitions and asss their strength, and explain how it connects to and unifies existing approaches [23, 26].
4.1. Relatability
We are interested in the relatability between point α(u) and α(v) defined by R(u, v) = minc c |κ(γ)|dγ, where c is any interpolating curve connecting α(u) and α(v) [24]. For a curve parameterized by arc length and when θ and ϕ are of the same sign (and thus are relatable), we can compute R(u, v) = θ + ϕ. Here we have adjusted the original definition from [24] so that perfect relatability is zero. We can also find the change of relatability along the SLS given a small step ds. Given (3) and θ = ϕ, we have dR = −κ(u)du + κ(v)dv, and: dR κ(u)wu + κ(v)wv = −2 csc θ ds⊥ wu + wv (7)
A significant positive strength indicates a potential part transition. In practice, we employ a small positive threshold b. 1 A uful range for b ems to be 1 ≤ b ≤ 1; we u b = 2 . 5 When measuring the strength of an entire part transition, we cannot rely on individual points. For instance, B could be spuriously large due to a sharp corner (in a polygonal approximation). Siddiqi et al. [23] measure the transition strength as the turning angle between the two nearby inflections. We cannot do this: our model of the part transition does not guarantee that two concutive inflections are included (or that they even exist). Instead, we integrate the strength of the transition along the smoothed local symmedR tries that have B > b. In this ca, we integrate ds⊥ (without r), becau the length of the integration interval is scale dR dependent and will cancel the scale in ds⊥ . Such a measure is consi
stent with Hoffman and Singh’s model of boundary strength, which equates the total turning angle at the boundary ction to the turning angle at curvature minima [9]. This motivates the following definition: Definition 4.2. The total strength of a part transition, T , between two parts is defined as the change of relatability across the transitional ction: T =
c
dR ds⊥ , ds⊥
where c is the axis gment with B > b.
b 0.1
1.37
0.3
1.36
0.5
1.36
1.0
1.34
b 0.1
0.53
0.3
0.5
1.0
华通留学0.52
0.51
0.46
0.76
0.76
0.75
0.70
0.31
0.30
0.27
0.18
(a)
(b)
(c)
0.52
0.53
0.52
0.48
0.23
0.22
0.18
0.05
Figure 6. Limb transition (a); short-cut transition (b) and a bend (c). They share the same shape geometry and turning angle on the left side, so the boundary strength is determined by the right side.
0.29
0.28
0.27
0.22
0.13
0.11
0.06
0
0.07
0.05
0.02
0
世界观英文0.01rain是什么意思
0
0
0
By integrating (7), we consider the turning angle on both sides of the shape, which appropriately identifies transitions, and excludes other structures such as bends. Figure 6(a) shows the transitional region of a limb-bad part— in this ca, the curvatures on both sides add together and result in a large value of T . This effectively implements the minima rule [8] for limbs and necks [23]. The strength T of the short-cut in (b) is smaller—about half the strength of (a)—becau only the curving side of the shape contributes. Thus, the same framework also implements the short-cut rule [26]. Finally, the bend in (c), which typically contains negative curvature minima, would have a very small value of T as the terms from either side cancel. (Even though the concave side has higher curvature, the weights in (7) are larger on the outside.) This aspect of our model rves to explain why ligatures on bending structures can be considered as being within a coherent part [1], and are not a transition. The implementation of the strength measure T includes two stages of thresholding to identify a potential part cut. First, we locate continuous SLS gments that have significant local transitional str
engths B > b. Then for each of tho ctions, T is computed—the transition is retained only when T is above a threshold t. Uful values of t range from π to π ; we u t = π . 8 4 6 We examine the effects of varying of b and t on a range of shapes with similar structures in Figure 7. Figure 7(a) shows the effect of adjusting b for simple shapes with a neck transition. Each column of shapes is procesd using the value of b on the top of the figure. As b is incread, the transition region between the shapes become smaller, and the shapes overlap more. Below each shape is the corresponding value of T (divided by π) for the transition. The necks are varied so they become less noticeable as one moves down the columns. The flattest necks on the bottom row are not detected for larger values of the threshold b. Figure 7(b) shows the same variation, but for shapes with a short-cut transition. As expected, the total strength values are a bit less than half of the value for the comparable example in (a). Figure 8 demonstrates the algorithm for the detection of potential transitional areas along the leg of the kangaroo (en later in Figure 11). The values of R and B are plotted on the right (with B scaled by tan−1 ). In this ca, transition 2 is discarded since the value of T < t.
Figure 7. Effects of varying transition strength and b. Below each shape is the corresponding value of T /π (or zero for no transition).
R
3
tan-1B
2
tan-1b
1 1 2 3
Figure 8. The relatability and the local strength along the SLS.
a shallow neck
part line
part line
Figure 9. Shallow necks do not trigger part cuts
A neck is located at the symmetry pair where the gendL erator has locally minimal length. That is, ds⊥ = 0 and > 0. This means that necks are always potentially part cuts. However, if the neck is too shallow, then it does not give ri to a salient place to cut the shape. An example of a shallow neck is prented in Figure 9. The boundary strength B is proportional to the curvatures, which corresponds to the notion of curvature disparity described by Siddiqi and Kimia [23]. Instead, in this ca, this location is interpreted as a bend.
d2 L ds2 ⊥
5. Implementation and Applications
5.1. Tracing SLS
Given a polygonal model with n vertices, identifying smoothed local symmetries by comparing each pair of vertices is quadratic in n. Here we introduce a more efficient algorithm to trace the symmetries of interest. We located the symmetries by detecting and tracing out zero crossings of A in the (u, v) parameter space. We focus on zero crossings that terminate on the boundary of the shape. While this ignores cas where the SLS can form a clod loop [7], the symmetries do not correspond to potential part transitions and are safely overlooked. Our algorithm works with an n × n
grid (which wraps around at the boundaries).
The algorithm starts by locating zero crossings on the boundary at curvature extrema using the symmetry curvature duality theorem [17]. At a curvature-extremum vertex i with curve parameter ui , we assume A(ui , ui ) = 0. Such endpoints are located on the diagonal of the grid. Then, we trace the zeros across the grid using a two-dimensional version of marching cubes [18]. Thus for the first step, we compute the other three corners of its adjacent grid points: A(ui−1 , ui ), A(ui , ui+1 ) and A(ui−1 , ui+1 ). We find a zero crossing, and then move to the neighboring square across the edge that contains the zero. This procedure continues until we reach another boundary vertex—this must eventually occur [7]. In any square that cross the SLS in the parameter space, there are usually two zero crossings along the four sides and the tracing can proceed unambiguously. For the ca when a square contains four zero crossings, we choo the next edge in an anti-clockwi direction. Figure 10(a) shows the complete SLS for the kangaroo. Segments with B > b are drawn with thicker lines. The gments include both peripheral transitional regions that are indicative of part boundaries as well as interior transitional regions that are not. In practice, we identify an initial t of basic parts by following the SLS from each curvature extremum. The algorithm stops whenever a ction with total transitional strength above the threshold t is found. Thus, our algorithm can procee
d without extracting the full SLS, but instead just tho portions that describe the exterior parts.
肼怎么读Cutting boundary of P1 Body line of P1 P1 u1
(a)
(b)
Figure 10. (a) The entire SLS—transitional regions are drawn with thicker lines; (b) Removing the foot—part P1 .
Figure 11. Sequentially deleting parts in the order of increasing radius of medial circles yields the components of a kangaroo shape
5.2. Shape analysis by quential deletion
still怎么读Sequential pruning of basic parts is the typical approach to build a hierarchical description of a shape [20, 21, 23]. To eliminate dependence between scales, parts must be removed cleanly for correct analysis of the shape at coarr scales [21]. Identifying a transitional area between parts, naturally has this effect. When a part is deleted, we also delete the associated transitional area, leavi
ng no trace of the part whatsoever. See Figure 10(b). We get one basic part by following the SLS from u1 . The part P1 is deleted by eliminating the entire transitional area from the SLS; we call this the cutting boundary of the part. The part itlf incorporates none of the transitional area; what remains of the part when the transitional area is removed, together with the exterior boundary of the part, we call the body line of the part. In our implementation, we u a cubic Hermite curve to complete ctions of the boundary of the part and the rest of the shape; other interpolation methods are possible [12]. A hierarchy is constructed by deleting the parts in a quence. We prioritize the deleting order using the radius of bi-tangent circles along the SLS of the transition. Parts of the shape with smaller circles are removed first [13, 23]. Additionally, we group certain parts together and delete them simultaneously when they have similar radius
and area, and have intercting transitional regions. We construct a common cutting boundary by fitting a NURBS curve through the interctions of the parts’ cutting boundaries.
5.3. Results
Figure 11 shows the quence of deletions that leads to the t of the components of the kangaroo shape. Figure 12 shows veral more results. Note how the head and body of the elephant, and the
wrist and palms of the hand, are actually analyzed as overlapping parts. Here the part aris from a transition region along the SLS that heads from the interior of the shape back towards the boundary. Perhaps surprisingly, the result remains intuitive—it recalls the artistic practice of defining shape by sketching overlapping mass. The cas underscore the conceptual distinction between our approach and traditional part-bad gmentations. Figure 13 offers an explicit comparison with the neckbad and limb-bad parts propod by Siddiqi and Kimia [23]. Again, we e that our approach is more flexible about the way it puts parts together—Siddiqi and Kimia have linear cuts only. This flexibility allows our system to find a range of natural parts that don’t fit easily into a gmentation—the tail of the rabbit, the head and trunk of the elephant. It gives the parts themlves a simpler shape, as exemplified by the animals’ bodies. And it means that we
