Shape Analysis & Measurement - Purdue University
Shape Analysis& MeasurementMichael A. Wirth, Ph.D.University of GuelphComputing and Information ScienceImage Processing Group 2004
Shape Analysis & Measurement The extraction of quantitative featureinformation from images is the objec ti v e o fimage analysis. The objective may be:– shape quantification– count the number of structures– characterize the shape of structures2
Shape Measures The most common object measurementsmade are those that describe shape.– Shape measurements are physical dimensionalmeasures that characterize the appearance of anobject.– The goal is to use the fewest necessary measuresto characterize an object adequately so that it maybe unambiguously classified.3
Shape Measures The performance of any shapemeasurements depends on the quality of theoriginal image and how well objects are preprocessed.– Object degradations such as small gaps, spurs,and noise can lead to poor measurement results,and ultimately to misclassifications.– Shape information is what remains once location,orientation, and size features of an object havebeen extracted.– The term pose is often used to refer to location,orientation, and size.4
Shape Descriptors What are shape descriptors?– Shape descriptors describe specific characteristicsregarding the geometry of a particular feature.– In general, shape descriptors or shape featuresare some set of numbers that are produced todescribe a given shape.5
Shape Descriptors– The shape may not be entirely reconstructablefrom the descriptors, but the descriptors fordifferent shapes should be different enough thatthe shapes can be discriminated.– Shape features can be grouped into two classes:boundary features and region features.6
Distances The simplest of all distance measurements isthat between two specified pixels (x1,y1) and(x2,y2). There are several ways in which distancescan be defined:– Euclideand ( x1 x2 )2 ( y1 y 2 )2– Chessboardd max ( x1 x2 , y1 y 2)7
Distances– City-blockd x1 x2 y1 y 2EuclideanChessboardCity-block8
Area The area is the number of pixels in a shape.Net AreaConvex Area The convex area of an object is the area of theconvex hull that encloses the object.9
AreaOriginal ImageNet AreaFilled Area10
Perimeter The perimeter [length] is the number of pixelsin the boundary of the object.– If x1, ,xN is a boundary list, the perimeter is givenby:perimeter N -1N -1 d xi 1ii 1i x i 1– The distances di are equal to 1 for 4-connectedboundaries and 1 or 2 for 8-connectedboundaries.11
Perimeter For instance in an 8-connected boundary, thedistance between diagonally adjacent pixelsis the Euclidean measure2– The number of diagonal links in N4–N8, and theremaining N8–(N4–N8) links in the 8-connectedboundary are of one pixel unit in length. Thereforethe total perimeter is:perimeter ( 2 1)N4 (2 2)N812
Perimeter The convex perimeter of an object is theperimeter of the convex hull that encloses theobject.convex perimeterobject perimeter13
Major Axis The major axis is the (x,y) endpoints of thelongest line that can be drawn through theobject.– The major axis endpoints (x1,y1) and (x2,y2) arefound by computing the pixel distance betweenevery combination of border pixels in the objectboundary and finding the pair with the maximumlength.14
Major Axis Length The major-axis length of an object is the pixeldistance between the major-axis endpointsand is given by the relation:major-axis length ( x2 x1 )2 ( y 2 y1 )2– The result is measure of object length.15
Major Axis Angle The major-axis angle is the angle betweenthe major-axis and the x-axis of the image: y 2 y1 major-axis angle tan x2 x1 – The angle can range from 0 to 360 .– The result is a measure of object orientation. 116
Minor Axis The minor axis is the (x,y) endpoints of thelongest line that can be drawn through theobject whilst remaining perpendicular with themajor-axis.– The minor axis endpoints (x1,y1) and (x2,y2) arefound by computing the pixel distance betweenthe two border pixel endpoints.17
Minor Axis Length The minor-axis length of an object is the pixeldistance between the minor-axis endpointsand is given by the relation:minor-axis length ( x2 x1 )2 ( y 2 y1 )2– The result is measure of object width.18
Major and Minor AxesMajor AxisMinorAxis19
Compactness Compactness is defined as the ratio of thearea of an object to the area of a circle withthe same perimeter.4π areacompactness ( perimeter )2– A circle is used as it is the object with the mostcompact shape.– The measure takes a maximum value of 1 for acircleπ 4– A square has compactness 20
Compactness– Objects which have an elliptical shape, or aboundary that is irregular rather than smooth, willdecrease the measure.– An alternate formulation:( perimeter )2compactness 4π area– The measure takes a minimum value of 1 for acircle– Objects that have complicated, irregularboundaries have larger compactness.21
Compactnesslow compactnesscompactness 0.764 compactness 0.66822
Elongation In its simplest form elongation is the ratiobetween the length and width of the objectbounding box:elongation widthbounding-boxlengthbounding-box– The result is a measure of object elongation, givenas a value between 0 and 1.– If the ratio is equal to 1, the object is roughlysquare or circularly shaped. As the ratiodecreases from 1, the object becomes moreelongated.23
Elongation This criterion cannot succeed in curvedregions, for which the evaluation ofelongatedness must be based on maximumregion thickness.– Elongatedness can be evaluated as a ratio of theregion area and the square of its thickness.– The maximum region thickness (holes must befilled if present) can be determined as the numberd of erosion steps that may be appliedbefore theareaelongation region totally disappears.2d224
Elongationlengththwidhigh elongationlow elongation25
Eccentricity Eccentricity is the ratio of the length of theshort (minor) axis to the length of the long(major) axis of an object:axislengthshorteccentricity axislengthlong– The result is a measure of object eccentricity,given as a value between 0 and 1.– Sometimes known as ellipticity.26
Eccentricityhigh eccentricitylow eccentricity27
Eccentricity Eccentricity can also be calculated usingcentral moments:eccentricity ( µ02 µ20 )2 4 µ11area28
Measures of “Circularity” Sometimes it is useful to have measures thatare sensitive only to departures of a certaintype of circularity:e.g.convexity (measures irregularities)roundness (excludes local irregularities)29
Circularity or Roundness A measure of roundness or circularity (area-toperimeter ratio) which excludes local irregularitiescan be obtained as the ratio of the area of an objectto the area of a circle with the same convexperimeter:4π arearoundness (convex perimeter )2– This statistic equals 1 for a circular object and less than 1 foran object that departs from circularity, except that it isrelatively insensitive to irregular boundaries.30
Circularityroundness 0.584roundness 0.44731
Sphericity Sphericity measures the degree to which anobject approaches the shape of a “sphere”.sphericity RinscribingRcircumscribing– For a circle, the value is the maximum of 1.032
Convexity Convexity is the relative amount that anobject differs from a convex object.– A measure of convexity can be obtained byforming the ratio of the perimeter of an object’sconvex hull to the perimeter of the object itself:convex perimeterconvexity perimeter33
Convexity– This will take the value of 1 for a convex object,and will be less than 1 if the object is not convex,such as one having an irregular boundary.convexity 1.0convexity 0.483convexity 0.34934
Aspect Ratio The aspect ratio measures the ratio of theobjects height to its width.heightaspect ratio width35
Caliper Dimensions Caliper or feret diameters are the distancesbetween parallel tangents touching oppoisitesides of an object.– At orientation θ, the caliper diameter is:max ( x sinθ y cosθ ) min ( x sinθ y cosθ )( xy ) A( x , y ) A– Certain caliper diameters are of special interest: The width of an object (θ 0 )max ( y ) min ( y )( x , y ) A( x , y ) A36
Caliper Dimensions The height of an object (θ 90 )max ( x ) min ( x )( x , y ) A( x , y ) A The maximum caliper diameter is one definitionof an objects length.37
Curl The curl of an object measures the degree towhich an object is “curled up”.lengthcurl fibre lengthfibre widthbreadthlengthfiber length38
Curl As the measure of curl decreases, the degreeto which they are “curled up” increases.perimeter- (perimeter)2 16 areafibre length 4areafibre width fibre length39
Convex Hull The convex hull of an object is defined to bethe smallest convex shape that contains theobject.40
Solidity Solidity measures the density of an object. A measure of solidity can be obtained as theratio of the area of an object to the area of aconvex hull of the object:areasolidity convex area41
Solidity– A value of 1 signifies a solid object, and a valueless than 1 will signify an object having anirregular boundary, or containing holes.solidity 1.0solidity 0.782solidity 0.59242
Shape Variances Sometimes a shape should be comparedagainst a template.– A circle is an obvious and general templatechoice. The circular variance is the proportionalmean-squared error with respectto solid circle.– It gives zero for a perfectcircle and increases alongshape complexity andelongation.43
Shape Variances Elliptic variance is defined similarly to thecircular variance. An ellipse is fitted to theshape (instead of a circle) and the meansquared error is measured.44
Rectangularity Rectangularity is the ratio of the object to thearea of the minimum bounding rectangle.– Let Fk be the ratio of region area and the area of abounding rectangle, the rectangle having thedirection k. The rectangle direction is turned indiscrete steps as before, and rectangularitymeasured as a maximum of this ratio Fkrectangularity max(Fk )k– Rectangularity has a value of 1 for perfectlyrectangular object45
Bounding Box The bounding box or bounding rectangle ofan object is a rectangle which circumscribesthe object. The dimensions of the boundingbox are those of the major and minor axes.– The area of the bounding box is:area (major axis length) (minor axis length)– The minimum bounding box is the minimum areathat bounds the shape.46
Bounding Boxbounding boxes47
Direction Direction is a property which makes sense inelongated regions only. If the region iselongated, direction is the direction of thelonger side of a minimum bounding rectangle.– If the shape moments are known, the direction θcan be computed as:2µ11 1 1 θ tan 2 µ20 µ02 48
Direction Elongatedness and rectangularity areindependent of linear transformationstranslation, rotation, and scaling. Direction is independent on all lineartransformations which do not include rotation. Mutual direction of two rotating objects isrotation invariant.49
Orientation The overall direction of the shape.50
Topological Descriptors Topological properties are useful for globaldescriptions of objects in an image.– Features that do not change with elasticdeformation of the object.– For binary regions, topological features include thenumber of holes in a region, and the number ofindentations, or protrusions.– One topological property is the number ofconnected components.51
Topological Descriptors The number of holes H and connectedcomponents C in an image can be used todefine the Euler number.– The Euler number is defined as the number ofcomponents minus the number of holes:Euler number C - H– This simple topological feature is invariant totranslation, rotation and scaling.52
Boundary Descriptors The shape of a region can be represented byquantifying the relative position ofconsecutive points on its boundary. A chain code consists of a starting locationand a list of directions d1,d2, ,dN provides acompact representation of all the informationin a boundary.– The directions di are estimates of the slope of theboundary.53
Boundary Descriptors Chain codes are based on 4- or 8connectivity:3 2 1405 6 7e.g.2,1,0,7,7,0,1,154
Boundary Descriptors The k-slope of the boundary at (xi,yi) can beestimated from the slope of the line joining(xi-k/2,yi-k/2) and (xi k/2,yi k/2) for some small,even value of k. Calculated as an angle of: y i k 2 y i k 2tan x i k 2 xi k 2 1 measured in a clockwise direction, with ahorizontal slope taken to be zero.55
Boundary Descriptors: Curvature The k-curvature of the boundary at (xi,yi) canbe estimated from the change in the k-slope: 1 y i k y i 1 y i y i k tan tan xi k xi xi xi k (mod2π )56
Boundary Descriptors: Curvature The curvature (κ) of an object is a local shapeattribute.– Convex shapes yield positive curvatures– Concave shapes yield negative curvatures57
Boundary Descriptors: BendingEnergy The total bending energy EC is a robust globalshape descriptor.– The bending energy of a boundary may beunderstood as the energy necessary to bend a rodto the desired shape and can be calculated as asum-of-squares of the boundary curvature κ(p)over the boundary length L.Ec L1L2κ(p) p 12πR Ec – The minimum value 2π/R is obtained for a circle ofradius R.58
Boundary Descriptors: BendingEnergy For example:chain-code:0 0 2 0 1 0 7 6 0 0curvature:0 2 –2 1 –1 –1 –1 2 0sum of squares: 0 4 4 1 1 1 1 4 0Bending Energy 1659
Boundary Descriptors:Total Absolute Curvature This descriptor is a measure of the totalabsolute curvature in an object:κ total L1L κ ( p)p 12π κ total – The minimum value is found for all convex objects.60
Moment Analysis The evaluation of moments represents asystematic method of shape analysis.– The most commonly used region attributes arecalculated from the three low-order moments.– Knowledge of the low-order moments allows thecalculation of the central moments, normalisedcentral moments, and moment invariants.61
Spatial Moments To define the (p,q)th-order moment:mpq M 1 N 1p qx y for p, q 0,1,2,.x 0 y 0 The zeroth-order moment m00 simplyrepresents the sum of the pixels contained inan object and gives a measure of the area(because x0 y0 1)62
Spatial Moments The first-order moments in x (m10) and y (m01)normalised by the area can be used tospecify the location of an object:– The centre of gravity, or centroid of an object is ameasure of the object’s location in the image.– It has two components, denoting the row andcolumn positions of the point of balance of theobject. m10 m01 centroid ( x , y ) , m00 m00 63
Spatial Momentsyx, yθx64
Central Moments The central momentsµ pq (i.e. p q 1)represent descriptors of a region that arenormalised with respect to location.M 1 N 1µ pq ( x x ) ( y y )pqfor p q 1x 0 y 065
Normalised Central Moments The central moments can be normalised withrespect to the zeroth moment to yield thenormalised central moment:γηpq µ pq µ00γ (p q) 2 1 The most commonly normalised centralmoment is η11, the first central moment in xand y.– This provides a measure of the deviation from acircular region shape. A value close to zerodescribes a region that is close to circular.66
Central Moments Central moments are translation invariant:– i.e. two objects that are identical except for havingdifferent centroids, will have identical values of– Central moments are not rotationally invariantµpq Central moments are not rotationally invariant– they will change if an object is rotated.67
Central Moments The second-order central moments:µ2022m10m01m10 m01 m20 µ02 m02 µ11 m11 m00m00m00 The second-order moments measure howdispersed the pixels in an object are fromtheir centroid:– µ20 measures the object’s spread over rows– µ02 measures the object’s spread over columns– µ11 is a cross-product term representing spread inthe direction in which both row and column indicesincrease.68
Principal Axes Principal axes of an object can be uniquelydefined as segments of lines crossing eachother orthogonally in the centroid of the objectand representing the directions with zerocross-correlation. This way, a contour is seenas an realization of a statistical distribution.69
Principal Axes Principal (major and minor) axes are definedto be those axes that pass through thecentroid, about which the moment of inertia ofthe region is, respectively maximal orminimal.– The orientation of the 1major 2µaxis: 111θ 2 tan µ20 µ02 which is measured clockwise, with the horizontaldirection taken as zero.– This can be used to find the minimum boundingbox.70
Moment Invariants Normalisation with respect to orientationresults in rotationally invariant moments.– The first two are the following functions of thesecond-order central moments:φ1 η20 η022φ2 (η20 η02 ) 4η112– The first of these statistics is the moment ofinertia, a measure of how dispersed, in anydirection, the pixels in an object are from theircentroid.– The second statistic measures whether thisdispersion is isotropic or directional.71
Moment Invariantsφ1 η20 η022φ2 (η20 η02 ) 4η112φ3 (η30 3η12 ) ( 3η21 η03 )2φ4 (η03 η12 ) (η21 η03 )22272
Central Momentsµ10 µ01 0µ11 m11 m10 m01 m002m00µ20 m20 m102m00µ02 m02 m01µ30 m30 3 xm20 2m10 x 2µ03 m03 3 ym02 2m01y 2µ12 m12 2ym11 xm02 2m10 y 2µ21 m21 2 xm11 ym20 2m01x 273
References:Moments1.2.3.4.Pohlman, K.A., Powell, K.A., Obuchowski, N.A., Chilcote, W.A.,Grunfest-Bronlatowski, S., “Quantitative classification of breasttumours in digitized mammograms”, Medical Physics, 1996, 23:pp.1337-1345 (masses)Rangayyan, R.M., El-Faramawy, N.M., Desautels, J.E.L., Alim,O.A., “Measures of acutance and shape classification of breasttumors”, IEEE Transactions on Medical Imaging, 1997, 16:pp.799-810 (masses)Shen, L., Rangayyan, R.M., and Desautels, J.E.L., “Application ofshape analysis to mammographic calcifications”, IEEETransactions on Medical Imaging, 1994, 13: pp.263-274(calcifications)Wei, L., Jianhong, X., Micheli-Tzanakou, E., “A computationalintelligence system for cell classification”, Proceedings of theIEEE International Conference on Information TechnologyApplications in Biomedicine, 1998, pp.105-109 (blood cells)74
Radial Distance Measures The shape of a structure of interest can bedetermined by analysing its boundary, thevariations and curvature of which constitutethe information to be quantified.– Transform the boundary into a 1D signal andanalysing its structure.– The radial distance is measured from the centralpoint (centroid) in the object to each pixel x(n),y(n) on the boundary.75
Radial Distance Measures Generally the centroid is used as the centralpoint, and the radial distance:d (n ) [ x(n ) x ] [ y (n ) y ]22n 0,1,., N 1is obtained by tracing allN pixels of the boundary.d76
Radial Distance Measures To achieve scale invariance, the normalisedradial distance r(n) is obtained by normalisingd(n) with the maximal distance The number of times the signal r(n) crossesits mean and other similar metrics can beused as a measure of boundary roughness.– Kilday, J., Palmieri, F., and Fox, M.D., “Classifying mammographiclesions using computerized image analysis”, IEEE Transactions onMedical Imaging, 1993, 12: pp.664-66977
Radial Distance Measures The sequence r(n) is further analysed toextract shape metrics such as the entropy:KE hk log hkk 1where hk is the k-bin probability histogramthat represents the distribution of r(n) as wellas the statistical moments:mp N 11N [ r ( n )]pn 078
Ra
Shape Analysis & Measurement The extraction of quantitative feature information from images is the objective of image analysis. The objective may be: – shape quantification – count the number of structures – characterize the shape of structures. 3 Shape Measures
Purdue Printing Services The School of Pharmacy and Pharmaceutical Sciences Purdue University Heine Pharmacy Building, Room 104 575 Stadium Mall Drive West Lafayette, IN 47904-2091 (765) 494-1361 (765) 494-7800 Fax www.pharmacy.purdue.edu The Purdue Pharmacist is published three times a year for alumni
A Very Merry Christmas to All Boiler OUT Times, Volume 1 Issue 3, 12/12/2017 Edited by Ayo Adetunji aadetunj@purdue.edu and Yichen Fan fan151@purdue.edu Published by Boiler OUT Volunteer Program boilerout@purdue.edu Center for Intercultural Learning, Mentorship, Assessment and Research (CILMAR) Purdue University Young Hall, Room 120
92,699 Purdue alumni are members of fraternities, sororities and cooperative houses. 30% of Purdue alumni that served on either the Purdue Board of Trustees, PRF Board of Directors, Purdue Alumni Foundation Board, or boards for the colleges/schools from 2009-2019 were members of FSCL
alpha gamma delta at purdue university, alpha phi at purdue university, andy mohr nissan, annex of richmond, another broken egg , another broken egg of . chi omega sorority at indiana university kitchen remodel, coca-cola, comcast of kokomo, community hospital north emergency psychiatric department, community hospital north peds icu .
Purdue University 550 Stadium Mall Drive West Lafayette, IN 47907 Email: mdfrisbee@purdue.edu . Planet Earth: Foundations of Earth Science (EAPS 100), Purdue University, 2015, 2016, 2017 Introduction to Earth Sciences (GEOL1121) Lab Courses, Georgia Southern University, 2013 .
Purdue University - West Lafayette, IN ABSTRACT The Purdue University Mach 4 Quiet Flow Ludwieg Tube has been converted to the Purdue Transonic Educational Facility. The conversion involved removing the Mach 4 converging-diverging nozzle and replacing it with
This Sustainable Landscape Plan is a comprehensive look at Purdue University's forward-thinking approach to landscape design, maintenance, and operations. . Soilmaker, a business based on land leased from Purdue University, produces high-quality synthetic soil using leaves, brush, and grass clippings from Purdue and .
rotational motion and astrophysics can have impacts on our lives, as well on the environment/society. This application and development of skills can be achieved using a variety of approaches, including investigation and problem solving. The Unit will cover the key areas of kinematic relationships, angular motion, rotational dynamics, gravitation, general relativity, and stellar physics .
