Abstract
Abstract| Underlying recognition is an organization of objects and their parts into classes and hierarchies. A representation of parts for recognition requires that they be invariant to rigid transformations, robust in the presence of occlusions, stable with changes in viewing geometry, and be arranged in a hierarchy. These constraints are captured in a general framework using notions of a part-line and a partitioning scheme. A proposed general principle of \form from function" motivates a particular partitioning scheme involving two t ypes of parts, neck-based and limb-based, whose psychophysical relevance was demonstrated in 39]. Neckbased parts arise from narrowings in shape, or the local minima in distance between two p o i n ts on the boundary, while limb-based parts arise from a pair of negative curvature minima which h a ve \co-circular" tangents. In this paper, we present computational support for the limb-based and neck-based parts by showing that they are invariant, robust, stable and yield a hierarchy of parts. Examples illustrate that the resulting decompositions are robust in the presense of occlusion and clutter for a range of man-made and natural objects, and lead to natural and intuitive p a r t s which can be used for recognition.
I. Introduction
Underlying recognition is an organization of objects and their parts into classes and hierarchies. In computer vision, the notion of recognition based on \parts" has become increasingly popular. The task of forming high-level object-centered models from low-level image-based features requires intermediate representations and parts serve such a role for robust recognition. Perhaps the most compelling support for this idea is based on recognition in the presence of occlusion: while local features are sensitive to noise and other variations, global structures are susceptible to occlusion by other objects. In contrast, the stable computation of a few parts can lead to recognition that is robust in the presence of occlusions. In addition, objects are often composed of moving or growing parts: while the description of each part remains intact, the relationships between parts change.
I. Introduction
How should parts of a shape be computed? Previous approaches have focused either on the decomposition of its interior region or on the segmentation of its boundary. Blum's idea of shape as a collection of overlapping disks leads to partitioning of the interior shape along branch points of the symmetric axis 6, 7 ] . Other region-based parts include maximally convex parts 38], a description based on the best combination of primitives such a s g e neralized cylinders 5, 2 8 , 2 9 ] , and superquadrics 32, 3] , or the simplest description in some language 22, 3 3 ] . In contrast, contour-based segmentations use boundary features such as high-curvature points 11] whose salience is demonstrated in 2, 4 ]. Koenderink 21] noted that threedimensional shapes are perceived as the composition of elliptic regions with the hyperbolic patches as glue, as evidenced in the works of art, and advocated a decomposition along parabolic lines, or in ection points of the twodimensional shape. Primitive-based boundary partitioning schemes approximate the boundary as the best combination of primitives such as polygons 34], primitive curvature changes, e.g., cranks, bends, bumps, and ends 1], or constant curvature segments 41] .
I. Introduction
A signi cant departure from the traditional techniques is the boundary-based method proposed by Ho man and Richards 14] who advocate that part decomposition should precede part description. They contrast primitive-based approaches with boundary-based methods and propose a theory of parts which relies not on the shape of parts, as captured by primitives, but rather on general principles underlying their formations, or \regularities of nature". The transversality principle, as an example of such a regularity, asserts that \when two arbitrarily shaped surfaces are made to interpenetrate they always meet in a contour of concave discontinuity of their tangent planes". Singularity regularity, or \lawful properties of the singularities of the retinal projection", is a second example. These two regularities lead to a partitioning rule for plane curves: \divide a plane curve i n to parts at negative minima of curvature." Figure 1 illustrates the successful application of this rule to two examples, a face and a hand, which produces intuitive results. This theory explains several gure-ground reversal illusions successfully see 9] for further psychophysical evidence. This partitioning proposal leads to a representation of the shape boundary based on codons, pieces of the boundary bounded by negative curvature minima the curvature maxima and zeros are then used to classify each piece as one of the six possible types 36, 35, 37] . Leyton The shape triangle represents three cooperative/competitive processes acting on shape, namely, parts, protrusions, and bends. Each process is biased to see the shape in its own terms. The sides of the triangle represent c o n tinuums of shapes whose extremes correspond to the node and whose perception varies from one description to another. For a more detailed description see 19] .
I. Introduction
process-analysis views a part as a causal explanation, or as a consequence of historical processes, which is based on a biologically-relevant Symmetry-Curvature duality principle 26]. To merge these extreme views, Kimia, Tannenbaum and Zucker 19] propose a continuum connecting two extremes, and capturing the distinction between, (1) the parts extreme where objects have clearly de ned and distinct segments, e.g., resulting from object composition, and (2) the protrusions extreme, where an object is best described as another whose boundary has been deformed, e.g., due to growth. In 19] , this continuum is viewed in the context of the shape triangle representing three cooperative/competitive processes acting on shape: parts, protrusions, and bends, Figure 2 . The three sides of the triangle represent three separate continuums: the partsprotrusion continuum, the parts-bends continuum and the protrusions-bends continuum, capturing the tension between object composition, boundary deformation and region deformation. In this context, the proposal presented here may be viewed as a study focused on a single node of the shape triangle, namely the parts process.
I. Introduction
Returning to the theory proposed by 14], the distinction presented between the primitive-based and boundarybased methods can be viewed, alternatively, as a distinction between those primitive-based methods acting on the interior region and primitiveless, general-purpose boundarybased techniques. In other words, the boundary/region and primitive/primitiveless distinctions are orthogonal and not necessarily in con ict 20] . We are in general agreement with Ho man and Richards on the limited capability o f primitive-based techniques, whether they are applied to the boundary or the interior. However, we a r g u e f o r a role not only for the boundary, but also for the interior of the shape 20]. For example, by stretching a small portion of the contour of a shape, while retaining it's remaining contours, one can produce new shapes whose parts change drastically 20], Figure 3 (top). As another example, the interaction of negative curvature minima through the interior region can produce \bending", rather than parts, Figure 3 (bottom). In addition, Kimia, Tannenbaum, and Zucker 20] discover parts which are not derived from curvature extrema of the boundary, but are based on \necks" of the objects, Figure 4 . We n o w proceed to develop a formal framework to investigate requirements of a partitioning scheme for recognition.
II. A Framework for Partitioning Shape
In this section we d e v elop a framework for studying partitioning schemes for decomposing visual form. Natural constraints from recognition demand that (1) a partitioning scheme be invariant to rigid transformations, be robust to local deformations and be stable with global transformations (2) a partitioning scheme arrange parts in a hierarchy so that it is suitable for the recognition of objects organized in a taxonomy, for recognition in the presence of resolution e ects, and for e cient recognition. We de ne notions of a part-line and a partitioning scheme and then formally develop the above constraints in this framework towards a general-purpose shape decomposition scheme.
II. A Framework for Partitioning Shape
A signi cant aspect of a partitioning scheme is the way decomposed parts behave under the various changes that may arise in the visual projection. Earlier approaches to partitioning have demanded that part computations be reliable, o r i n variant with time and viewing geometry 28, 1 4 ] . However, observe that three distinct types of changes can occur in the visual world and parts should behave appro- priately with these changes. First, we consider changes in the visual image formation that map to a combination of translations, rotations, and scalings of the two dimensional shape. It is clear that parts of the transformed shape must be exactly the transformed parts of the original shape. This constraint o f invariance leads to computations that are intrinsic to the shape. The second class of changes are localized to certain portions of the shape, for example those due to partial occlusion, movement o f p a r t s , etc. It is natural to demand that such local deformations of the shape do not a ect those parts that are remote to the change. This constraint o f robustness leads to computations that are local to the part under consideration. Finally, c hanges in shape can be global, e.g., d u e t o c hanges in viewpoint, changes in viewing direction, growth, etc. When such c hanges to the two-dimensional shape are slight, we expect that the change in the \part-structure" is also slight. This stability constraint leads to nonbinary part computations.
II. A Framework for Partitioning Shape
A general-purpose decomposition of shape should be based on the interaction between two parts, rather than on their shapes. It is appropriate, then, to explicitly focus on the interface between parts:
II. A Framework for Partitioning Shape
De nition 1 A part-line is a curve whose end points rest on the boundary of the shape, which is entirely embedded in it, and which divides it into two connected c omponents.
II. A Framework for Partitioning Shape
This de nition is general in that it allows for schemes that favor boundary features as well as those that are based on regional properties. A collection of proposed part-lines that divides a shape into connected parts forms a partitioning scheme:
II. A Framework for Partitioning Shape
De nition 2 A partitioning scheme is a mapping of a connected r egion in the image to a nite set of connected r egions separated b y p art-lines.
II. A Framework for Partitioning Shape
We are now in a position to formally develop the notions For example, a translated shape's part-lines should translate by the same amount.
II. A Framework for Partitioning Shape
Second, we demand that variations in the scene and viewing geometry, in particular the occlusion of an object by another, cause no change to part-structure in regions remote to such c hange. To illustrate this point further, observe that the part-structure of the visible portion of a doll, e.g., head, hands, torso, etc. remains invariant t o t h e occlusion or movement of the feet, as in Figure 5 . Let the size of a part-line be the distance between its two e n d points and de ne the local-neighborhood N of a partline as a disk centered on the part-line, whose radius R is a constant proportion of the length L of the part-line: R = L. Based on qualitative experience gained from psychophysical experiments, we select = 2 :5. We should stress, however, that the operation of the algorithm in Section V is not sensitive to the exact choice of . A part-line is contained in some region if its local-neighborhood is contained in the region. Then, De nition 4 A p artitioning scheme is robust if for any two shapes, S 1 and S 2 , w h i c h a r e exactly the same in some neighborhood, N, t h e p artlines fP i g contained i n N for S 1 and S 2 are exactly equivalent.
II. A Framework for Partitioning Shape
Informally, robust schemes must therefore determine partlines \locally", namely, based on information that is obtained from a local neighborhood of the part-line. However, since the part-line size may v ary over the shape, this neighborhood also varies in size.
II. A Framework for Partitioning Shape
The third constraint relates global changes in the shape to the structure of its parts. We require that slight c hanges in the boundary of the object, which m a y arise from changes in viewpoint and viewing direction, deformation of the boundary, etc. , lead to slight c hanges in the parts and their relations. Informally, t wo similar objects must have similar parts. Formally, Fig. 6 . As an object is viewed from larger distances, or when the object is in a di erent plane of focus, its detailed structures may n o longer be distinguishable. The part-structure of the shape should remain stable with variations in viewing distance.
II. A Framework for Partitioning Shape
De nition 5 A p artitioning scheme is stable if slight deformations of the boundary of a shape cause only slight changes in its part-lines.
II. A Framework for Partitioning Shape
Speci cally, slight deformations in the shape are measured by metrics for curves, e.g., the Hausdor metric, while changes in part-lines include changes in their center, size, angle, their disappearance, or their appearance.
II. A Framework for Partitioning Shape
Having dealt with the issue of the behavior of parts under various transformations, we n o w address two further requirements for recognition, namely, the need for stability with changes in resolution, and the need for a hierarchy of parts. First, it is important that part-structure remains stable with changes in resolution, e.g., as an object is seen from varying distances, Figure 6 . The parts at one resolution ought t o h a ve some correspondence with those at another, speci cally, the parts at a coarse resolution must remain at ner resolutions. Second, the need for a hierarchy of parts is well recognized this allows for a taxonomical representation of objects and e cient recognition via coarse-to-ne matching. What is required here is a notion of scale for parts that is compatible with changes in resolution, and which leads to a hierarchical representation. Formally, De nition 6 A p artitioning scheme is scaletuned if when moving from coarse to ne scale, part-lines are only added, not removed, leading to a hierarchy of parts.
II. A Framework for Partitioning Shape
We n o w proceed to develop a general purpose partitioning scheme that is consistent with these requirements.
III. A Partitioning Proposal
Objects in the three-dimensional world project to twodimensional entities, and in the process, much information about their part-structure is lost. O u r t a s k i s t o d e n e a t wo-dimensional notion of parts based on evidence that remains in this lower-dimensional space that leads to the recovery of three-dimensional parts. The recovery of structure, however, is not only a function of the information available in the retinal image but also of the assumptions one makes about properties of the visual world 12, 17] . Hence, in recovering parts we rely both on properties of objects and on the nature of visual projection, leading to a proposal for two kinds of parts, those that are limb- based and those that are neck-based 39]. The notions of necks and limbs were developed as a result of an interaction among psychophysical, \ecological" and computational considerations, in the context of a shock-based representation for shape 20]. While a summary of the psychophysical and ecological support for necks and limbs (discussed in detail in 39]) appears below, in this paper our chief objective is to establish computational support for them, as is related to the recognition of objects in realistic situations involving partial occlusion, the movement o f parts, etc. It is essential to note that parts are computable from shocks Section VI the focus of the present w ork is to establish computational support for our notion of parts.
III. A Partitioning Proposal
Psychophysical support is provided by a series of experiments in which subjects were required to partition a set of shapes, using part-lines, into what the subjects perceived to be their components. Two i n teresting results emerged: (1) a high degree of inter-subject and intra-subject consistency, and (2) an overwhelming overlap between perceived and computed parts. The subjects showed a high degree of consistency when the same shapes were presented in separate trials. Similarly, a high degree of consistency was observed when the same shapes were presented to di erent subjects. Also, there was a close correspondence between the perceived part-lines and computed necks and limbs: a large majority of part-lines perceived were computed as necks or limbs (e.g., 90% for nonsense shapes), and a large majority of computed necks and limbs were perceived as part-lines.
III. A Partitioning Proposal
Ecological support for necks and limbs is derived from a response to the question \Why do objects have f o r m a t all?" Observe that objects do not exist in isolation, rather, they must interact with their environment and with other objects in it. An object's two-dimensional form is in uenced by both the nature of its interaction with other objects in a three-dimensional world and the nature of its projection onto the retinal image. First, as a result of this interaction, biological and man-made entities, whether by evolution or by design, give rise to parts which specialize in their function. When an object specializes function independently in two di erent, but connected regions, the result is often a sharp change in the three dimensional surface of the object, e.g., the join between the beak of a bird and its head. The projection of these sharp changes yields a pair of high curvature points, where the tangent a t o n e point smoothly continues to the tangent at the other point. This is a restatement of the Gestalt principle of \good continuation" for parts, and provides the rst type of parts, the limb-based parts, Figure 7 . Examples of limb-based parts are shown in Figure 8 . In contrast, two portions of an object may specialize function independently, but may b e connected through a symbiotic relationship. Requirements such as space for articulation and economy o f m a s s a t t h e connection lead to a narrowing of the join between them, e.g., the tail of a sh this provides the second type of parts, the neck-based parts, Figure 9 . Examples of neck-based parts are shown in Figure 10 . The above arguments in support of limb-based and neck-based parts together constitute the \form-from-function" principle which m a i ntains that form results from an interaction among objects and between objects and their environment. Second, this principle is complemented by an assumption about the nature of projection of objects which also leads to limb-based parts: a region of an object may partially occlude another, giving rise to a pair of negative c u r v ature discontinuities where the tangent at one discontinuity \smoothly" continues to the tangent at the other discontinuity, Figure 11 . Thus projection may also lead to limb-based parts, whose pairs of negative curvature minima are in fact concave discontinuities.
III. A Partitioning Proposal
Formally, the strongest form of smooth continuation is co-circularity: Fig. 11 . This gure illustrates a sequence of views of a mug and its corresponding t wo-dimensional form. Note the change in perception from a protrusion to a part. Whereas limb-based parts are reminiscent of Ho man and Richard's parts from transversality, there are two important di erences. First, the partitioning is through the region of the shape, via a part-line, and not along its boundary. Second, it is important that the boundary tangents at the pair of negative c u r v ature minima s h o w \good continuation". Observe that when this property d o e s n o t hold, Figures 3 (bottom) and 12, negative c u r v ature minima may not lead to intuitive parts. However, we a r e i n general agreement with Ho man and Richards that parts must derive from a regularity of nature. In fact, the \form-from-function" principle complements and generalizes the transversality principle. Limb-based parts are also related to the detection of \co-linear" T-junctions, part of an early heuristic proposal by Guzm an to group regions that belong to the same object 13]. These \co-linear" T-junctions arise in the special domain of line drawings of polyhedral objects, when one object occludes another.
III. A Partitioning Proposal
We n o w establish computational support for limbs and necks by showing that they meet the constraints of invariance, robustness and stability, and lead to a hierarchy o f parts for recognition. First, the detection of limbs and necks is based on the computation of curvature extrema, co-circularity, and distance function minima. Curvature is an intrinsic quantity and is hence invariant under rotation and translation its extrema are in addition invariant under scaling transformations. Co-circularity is based on relative orientation and relative position. As such, it is invariant under rotation, translation, and scaling. Euclidean distance is invariant under rotation and translation distance minima are in addition invariant under scaling transformations.
Remark 1
The \Limbs-and-Necks" partitioning scheme is invariant.
Remark 1
Second, observe that the limb-neck computations are based on information that is constrained to a local neighborhood N of the part-line. As such, variations in \remote" portions of the shape, namely those outside N, d o n o t a ffect the resulting part-lines. In contrast, for partitioning schemes with a priori de ned primitives, each part-line is the result of an optimization which describes shape as the best tting combination of primitives. As such, globallyoptimized primitive-based parts are a result of a global computation and are not robust in the above sense.
Remark 1
Remark 2 The \Limbs-and-Necks" partitioning scheme is robust. Fig. 15 . Salience of a neck increases as curvature disparity increases. Next, the issue of stability for our scheme is more subtle and requires a further development. Note that so far the notions of necks and limbs are binary in that a part-line is either a neck or not is either a limb or not. However, two factors motivate the need for non-binary part computations. First, consider the behavior of parts on the continuums of deformations represented by the sides of the shape triangle, Figure 2 . Observe h o w the perception of the shapes depicted on the part-protrusion axis changes smoothly from that of a \sausage with parts" to that of a \lasagna noodle with no parts " 19] . A rigid binary inference of parts would lead to instability because the partbased representation of the shape would change abruptly with a very slight c hange at some point on the axis a similar argument holds for the part-bend axis. Second, recall that our goal is the recovery of three-dimensional parts through intermediate two-dimensional parts. Since evidence for three-dimensional parts is often degraded and may not be conclusive, e.g., the sequence of views of a mug as it is rotated, Figure 11 , a part hypothesis must re ect the uncertainty and have an associated measure of strength. As such, a graded partitioning scheme, one which associates a measure of salience with each part-line, re ects a slight change in the shape as a slight c hange in the strengths of its part-lines.
Remark 1
Measures of salience for limbs and necks were psychophysically motivated. For limbs, two factors a ect salience: total curvature and extent. T otal curvature is the actual amount a tangent at one negative c u r v ature minima h a s to bend to align with the tangent at the second negative curvature minima. This measure describes how likely it is for one contour to continue across the limb (via no longer necessarily a circular arc) to the other contour, Figure 13 . Extent is a measure of how likely it is that each side is an independent part, as indicated by the mass across the partline, as computed in a local neighborhood of it, Figure 14 . Similarly, the salience of a neck is a ected by t h e curvature disparity across the part-line, Figure 15 a measure of how \thin" the neck is. Note that the notion of salience is independent of scale, Figure 16 see Section IV. Now, with the above measures of salience, the limb-based and neck-based part computations become stable: when a shape undergoes a slight deformation its negative curvature minima move slightly, leading to small changes in co-circularity, total curvature, extent and hence limb salience similarly, neck location and salience are only slightly changed. This allows for a smooth and stable traversal of the sides of the shape triangle: Remark 3 The \Limbs-and-Necks" partitioning scheme is stable.
IV. Scale and Dynamic Partitioning
Next, we address the notion of scale for parts. This is closely related to a notion of smoothing for shape as shapes are smoothed, small details are removed, including parts, while signi cant features remain. A smoothing space for shape, the entropy scale-space, w as introduced in 18], Figure 27 . Two processes underlie the approximation of shape in this space: reaction rigidly breaks o parts, while di usion melts the boundary into a smoother shape. What is important here is that parts are sorted into a hierarchy of scale using this smoothing process: reaction removes the information locally, while di usion operates globally 18] . In what follows we show h o w scale and salience interact, leading to a partitioning scheme that is scale-tuned.
IV. Scale and Dynamic Partitioning
Observe that local computations (for robustness to local deformations) can lead to global con icts, e.g., t wo p a r tlines may i n tersect or may use the same boundary tangents for continuation, Figure 17 (left). Both salience and scale play a role in resolving con icts. The role for salience is straightforward when two part-lines are in competition with one another the stronger one is selected, Figure 17 (right). For the scheme to be scale-tuned, parts at coarse scales must remain present at all ner scales. To merge these ideas we propose a dynamic partitioning procedure which results in a globally consistent h ypothesis, as illustrated by Figure 18 . First, at the coarsest scale the strongest part-line is selected and the corresponding part is \broken o ." All part-lines in con ict with the chosen part-line are then removed, and the remaining part-lines are considered in order of their salience. This selection process is then repeated for the remaining scales, in order of coarse to ne, until all part-lines are accounted for as either being selected or discarded. As a result, the set of part-lines at any scale is a superset of the set of part-lines at any coarser scale, leading to a hierarchy for parts. Hence, Remark 4 The \Limbs-and-Necks" partitioning scheme is scale-tuned.
IV. Scale and Dynamic Partitioning
As a further illustration, consider the Kanizsa Figure 19 (top left), where the thicker portion of each shape is perceived as occluding the thinner portion of the other. Our partitioning scheme nds eight candidate limbs of about equal salience, but which di er in scale, Figure 19 (top middle). The smaller part-lines (solid), however, disappear due to the smoothing process, and at the same time remove evidence for the existence of the larger part-lines (dashed). Note that the discarded part-lines revive if the competing part-lines are removed by partial occlusion, Figure 19 (top right). In addition, while the accepted limbs are the occluding contours, the discarded ones are the occluded contours. A pair of these hidden limbs whose endpoints are common with visible limbs signal a single object in occlusion, Figures 19 (top middle) , and 24 (bottom middle). Formally, De nition 9 (Hidden Limb) A hidden limb is a discarded limb which shares endpoints with two selected limbs, but uses di erent boundary tangents for continuation.
IV. Scale and Dynamic Partitioning
It is intriguing to note that our partitioning scheme is consistent with our visual perception of parts in Figure 20 , where local evidence for parts overrides our cognitive k n o wledge of the visual scene 17].
V. Algorithms
In this section we present algorithms for computing limbbased and neck-based part-lines 1 by outlining the procedure to process a binary shape, e.g., a region of 1's on a background of 0's, to obtain a set of part-lines. We wish to emphasize two p o i n ts before describing the algorithms. First, the method as described below i n volves a number of parameters whose values are chosen very liberally, k eeping in mind that it is not the selection of arbitrary parameter It is clear from the position of the feet and the occlusion of various body parts that the man and the woman are behind the fence. However, our partitioning scheme applied to the areas formed by the the man's jacket and the woman's skirt, which are merged with the fence, yields short vertical part-lines (solid) perpendicular to the fence. The discarded part-lines (dashed) are long horizontal lines parallel to the fence and are considered hidden limbs. Together, they imply that the man's jacket, and the woman's skirt, occlude the fence, and hence must be in front o f i t ! values that will rule out extraneous part-lines, but the interaction between part-lines. As such, all parameter values were xed and then used for all the examples, including biological as well as nonsense shapes, Section VII. Second, in our implementation the emphasis has been on the development and illustration of ideas. Hence, many of the steps are not optimal and much can be done to improve t h e i r computational e ciency.
ALGORITHM FOR COMPUTING LIMBS
We assume the availability of an ordered list of the shape's contour points in contour-list.
ALGORITHM FOR COMPUTING LIMBS
Detecting Negative Curvature Minima: The detection of negative curvature minima is based on computing changes in orientation, where orientation is computed from the distance transform of the binary shape. First, the distance transform of the shape is computed 10, 2 0 ]. In this representation, the shape is the zero level set of a surface z = ( x y), Figure 21 . Second, the direction of the tangent in the plane z = 0 is given by arctan( ;@ =@x @ =@y ), which gives the orientation at each point on the shape's contour. This computation is motivated by a larger framework for computing shocks 20] . We nd that it gives a robust and accurate estimate of orientation, although other techniques may be used instead. Third, local extrema in curvature are computed as the local extrema in the di erence in average orientation between two neighboring points 2 . F i n a l l y , for a clockwise trace of the shape's boundary, the extrema where the tangent is turning to the left are identi ed and stored in negative-minima-list. In addition, to rule out \weak" curvature extrema that may be present due to discretization but do not represent signi cant c hanges in orientation, the magnitude of the local change in orientation is required to exceed a low threshold (approximately 10 degrees). ( 1) and then select all local extrema of curvature. However, this involves the computation of second derivatives and is less robust than the approach we adopt. the boundary tangents at each endpoint in a local neighborhood of the part-line, 3) computing co-circularity b etween boundary tangents, and nally 4) selecting those part-lines for which t h e c o n tinuation curve b e t ween the co-circular boundary tangents is entirely embedded within the shape. First, two negative curvature minima are paired when a part-line passes through them and divides the contour at each end into two n e i g h borhoods. Second, the \left" and \right" neighborhoods, which are proportional in size to the part-line length L, g i v e rise to the left and right boundary tangents T 1 l T 2 l T 1 r T 2 r , Figure 22 . Third, with one boundary tangent to be selected from each e n dpoint, there are four possible pairings of boundary tangents. The co-circularity o f e a c h pair is computed 31]. Finally, those part-lines with at least one pair of co-circular boundary tangents, for which the continuation curve lies entirely within the shape are stored in candidate-limb-list. The continuation curves used for the examples in this paper are cubic splines. This may be extended to the use of more appropriate subjective contours 40, 8 , 2 7 ] , e.g., the shape o f a b e n t thin beam, minimizing its stored energy 15]. Recently, w e h a ve learned of Nitzberg et al.'s proposal for the use of \elastica", or curves which minimize a sum of length and the square of curvature, as continuations 30].
Con ict Resolution: Con icts between candidate limbs
are resolved by computing a measure of salience for each. As discussed earlier, salience is a function of total (absolute) curvature and extent. First, the computation of total curvature is as follows. Consider the co-circular boundary tangents T 1 l , T 2 l which form angles 1 l , 2 l , with the partline, respectively, Figure 22 . Over the space of curves that smoothly continue T 1 l to T 2 l , the minimum total absolute curvature is easily seen to be 1 l + 2 l , which has a maximum of when the co-circular boundary tangents are parallel. Hence, total curvature is normalized as 1 l + 2 l . Second, extent is computed as the ratio of major to minor axes of the largest ellipse that can be inscribed in the shape, with the part-line as its minor axis, but restricted to lie within the part-line's local neighborhood N. While we h a ve used this crude method as a rst order approximation, the results have proven su ciently robust not to merit further improvement at this stage. Extent attains a maximum when the major axis of the inscribed ellipse coincides with the diameter of the local neighborhood's disk, leading to the normalization of extent a s extent 2 (we u s e d = 2 :5, with L as the radius of the disk). The limbs in candidate-limblist are then ordered by salience, which is computed as the average of (1; 1 l + 2 l ) and extent 2 . When a limb is selected, it is placed in selected-limb-list and all con icting limbs are discarded.
Con ict Resolution: Con icts between candidate limbs
Hidden Limbs: When a discarded limb shares endpoints with two selected limbs, but uses di erent boundary tangents for continuation, it signals occlusion and is recovered as a hidden limb.
ALGORITHM FOR COMPUTING NECKS
We assume the availability of an ordered list of the shape's contour points in contour-list.
ALGORITHM FOR COMPUTING NECKS
Extracting Candidate Necks: Candidate necks are extracted by 1) nding all locally shortest part-lines for which a circle with the part-line as its diameter can be inscribed in the shape, and 2) selecting those whose curvature disparity exceeds a low threshold. First, pairs of contour pieces are considered and the locally shortest part-line through each pair is found, if it exists (note that this brute force technique for computing necks is computationally expensive a reimplementation of our algorithm { as outlined in Section VI { will use much more e cient and elegant second order shock computations). If there are two or more such shortest part-lines for a particular pair of contour pieces, their endpoints are averaged. Among these, part-lines for which a circle can be inscribed in the shape with the partline as its diameter, are selected. Second, only those locally shortest part-lines across which the curvature disparity exceeds a low threshold are placed in candidate-necklist. This is done because the procedure often results in a signi cant n umber of locally shortest part-lines that are present due to discretization, but which do not re ect a signi cant amount of thinning through the shape's region, Figure 24 (top middle).
Con ict Resolution: Con icts between candidate necks
are resolved by computing a measure of salience for each. As discussed earlier, salience is proportional to the curvature disparity across the neck for invariance to scaling transformations the measure used is the product of curvature disparity and part-line length L, where curvature is coarsely computed as a function of the deviation of the boundary away from the direction of the tangent. The necks in candidate-neck-list are then ordered by salience. When a neck is selected, it is placed in selected-neck-list and all con icting necks are discarded. This concludes the computation of necks.
Con ict Resolution: Con icts between candidate necks
The computation of limbs and necks begins at the coarsest scales and proceeds to ner scales, as outlined in Section IV. Limbs and necks that are essentially overlapping are grouped into single part-lines. The resulting set of limbs and necks is the algorithm's nal output. Thus far we h a ve presented computational support for necks and limbs by showing that they are invariant, robust, stable, and scale-tuned. The investigations of parts as necks, however, rst began in the reaction-di usion space of a shape 20], Figure 4 . Speci cally, the necks give rise to second-order shocks: when a shape evolves due to a deformation applied in the normal direction to each boundary point, non-neighboring portions of the boundary may c o llide, giving rise to two cusps, Figure 23 (left). These discontinuities of curvature are second-order shocks which a r e in one-to-one correspondence with neck-based part-lines. For constant deformation, or reaction, the center of the part-line coincides with the location of the shock and its orientation is perpendicular to the boundary tangent a t t h e shock, Figure 23 (left) . The e ect of curvature deformation, or di usion, is to place a measure of salience on the second order shock.
Con ict Resolution: Con icts between candidate necks
Similarly, in the context of the present study, i t i s n o w appropriate to relate limb-based parts to the formation of shocks in the reaction-di usion space as well. Note that when the boundary of a shape deforms by constant deformation, or reaction, each negative curvature minima produces a single discontinuity i n o r i e n tation, Figure 23 (right ) , o r a rst-order shock. Under outward reaction, the endpoints of a limb-based part-line produce a pair of rstorder shocks where the boundary tangent of one smoothly follows onto the boundary tangent of the other, Figure 23 (right). To a rst approximation, these boundary tangents are co-circular. The detection of simultaneously formed co-circular rst-order shocks is an alternate basis for the computation of limb-based parts.
Con ict Resolution: Con icts between candidate necks
The part computations can therefore be based on the computation of shocks in the reaction-di usion space. The question naturally arises as to whether the shock-based computations present a n y advantage over the algorithms presented here. Our goal in departing from the \shape from deformation" framework 20] has been to focus on an independent study of parts, guided by constraints from recognition and chie y motivated by psychophysics. The outcome is a con rmation and a re nement to include limb-based parts. In addition, two n umerical advantages of working within a shock-based framework emerge. First, because the computation of shocks is integrated with computations in scale, it is not necessary to separate part computations and approximations of shape in scale. Second, the evolutionary shock computations are numerically more elegant and e cient than the algorithms presented here. It is our intention to return to part computations based on a representation of shape as shocks of the reaction-di usion space.
VII. Examples
In this section we illustrate our partitioning scheme on several examples of man-made and biological objects. We emphasize that the parameter values used w e r e the same for all examples. The choices were determined by q u a litative experience with a large variety of shapes and the performance of the algorithm is not sensitive to their exact values. Figure 24 demonstrates the process of computing parts for the shape of an F16 ghter jet. Speci cally, note how salience resolves con icts between local part-line hypotheses, resulting in a natural decomposition of the shape and a recovery of the hidden parts, e.g., the rockets. Figure 25 demonstrates the generality of our proposal for partitioning the decompositions are natural for a variety o f b i o l o gical and man-made objects. Figure 26 demonstrates the robustness of the process in the presence of occlusion. Portions of occluded and unoccluded versions of the objects with identical shapes have identical parts, as required by the robustness criterion. Figure 27 shows the computation of parts across scale for four pears 35] note that the similarity in their parts is captured at the coarsest level. Figure 28 illustrates the process of dynamic partitioning for a tank which has been occluded by palm trees. Part computations begin at the coarsest scale, where the scene is described as a smaller blob on top of a larger one, Figure 28 (third row) . At a slightly ner scale a third blob is added to the top of the tank, and so on, leading to a hierarchy of parts for the tank. Observe that the parts recovered for the occluded tank correspond closely to those recovered for an unoccluded version of it, Figure 28 (bottom row). , the parts computed by applying our algorithm (middle), and the parts perceived by a majority of the 14 subjects (right). Note that for shapes (A) through (H), the computed and perceived parts are in exact agreement. Shapes (I), (J), and (K) illustrate discrepancies that occur due to the existence of bent l i m bs, e.g., those manifested as the kangaroo's tail and the elephant's trunk. Shape (L) illustrates the limits of the algorithm's performance when parts of low salience are admitted here a \weak" neck w h i c h breaks o the top part of the rabbit's front ear is computed, but is not perceived.
VIII. Discussion
The validity of our partitioning scheme can be measured against the principles it sought to satisfy, a s w ell as against human performance. Whereas we h a ve previously discussed the former, Figure 29 illustrates the latter. Despite a high degree of correspondence between computed parts and perceived parts, we h a ve observed two minor classes of discrepancies between them: 1) those due to part-bend interactions, and 2) those due to cognitive knowledge of the underlying object. First, consider the part-bend axis of Figure 2 . Observe h o w the perception of the leftmost shape as a \sausage" with four parts changes continuously to one of a snake with a single bent p a r t . Now consider Figure 30 whereas perceptual evidence for \trunks" and \tails" as parts is strong for the shapes on the right of each b o x, leading to clearly partitioned limbs, the evidence is greatly diminished for the shapes on the left, due to bending. Our psychophysical experiments indicate that in such situations, whereas subjects continue to place one endpoint of a part-line at the negative c u rvature minimum, the position of the second endpoint i s somewhat arbitrary 39]. Such parts can only be recovered under a more comprehensive framework 19]. Second, cognitive k n o wledge in uences part perception e.g., familiarity with the underlying object for a recognizable shape, and the existence of a semantic vocabulary for describing its various components may cause a subject to break o parts, even when perceptual evidence is weak 39].
IX. Conclusion
In conclusion, we comment on the relationship between partitioning and recognition. Thus far, we h a ve assumed the availability of a 2D shape, that which comes from the projection of the occluding contour of an object. However, it is well recognized that under general conditions the segmentation of an image into regions corresponding to the projections of distinct objects is not an easy task. In the face of this di culty, h o w can partitioning proceed? It is clear that since segmentation is a di cult task, a partitioning scheme should be able to handle errors in the segmentation process, partially correct segmentations, etc. To this end the limbs-and-necks scheme, being robust to local deformations and stable with slight global deformations, is appropriately designed. A more complete answer, however, lies in viewing parts as an intermediate representation that allows for the ow of bottom-up as well as top-down information. Consider that since part computations are local, edges of the appropriate polarity c a n i n teract to form necks and limbs prior to obtaining a segmentation of the object, Figures 13, 14 and 15, leading to a \parts receptive eld". This constitutes the bottom-up ow of information, i.e., from local edge hypotheses to the more global part hypotheses. Now, part hypotheses can in turn play a n integral role in the segmentation process through the topdown ow of information, i.e., a combination of likely parts can lead to an object hypothesis, followed by a segmentation hypothesis for the image. Such a notion of parts may be key in resolving the bottom-up/top-down bottleneck o f recognition.

{'paper_id': '6636041', 'title': 'Parts of Visual Form: Computational Aspects', 's2_url': 'https://api.semanticscholar.org/CorpusID:6636041', 'source': 'S2ORC'}