Computer Vision: Polyhedral ScenesComputer VisionTeaching a Machine to SeeFinding LinesPolyhedral ScenesA Simplified ExampleAnalyzing the ImageLine IntersectionsJunction LabelsLine Intersections (cont.)Line SegmentsLine Segments (cont.)Polyhedral Junctions - ExtendedWaltz’s AlgorithmMore Detailed LabelingMultiple Labels / AmbiguitiesAmbiguitiesAdding ShadowsShade LabelsShade Labels (cont.)A (semi) Complete ImageWaltz Algorithm OverviewAnother Example in ActionHomeworkWorks CitedCOT 4810Topics in Computer ScienceKen GeorgeJanuary 29, 2008A field of Computer Science that deals with processing real world images.Combines different aspects•Low level – image processing•High level – pattern and object recognition1/29/2008Ken George2Computers have no knowledge of “lines” or “surfaces”Can read an image as an array of pixelsCan not inherently relate two or more pixels1/29/2008Ken George3Lines are a basic relationship between pixelsNeed to know lines before we can know shapesLine Finding Algorithms:Hough TransformBurns Line Finder1/29/2008Ken George4“An assembly of solids, each of which is bounded by plane faces”Simple, minimalist scenariosComposed primarily of basic shapes1/29/2008Ken George51/29/2008Ken George6David Huffman and Maxwell Clowes advanced the knowledge of lines and their intersections in 1971 (Dewdney)This work was expanded upon by David Waltz, of the Massachusetts Institute of Technology, into the Waltz Algorithm1/29/2008Ken George7In a scene like our example, lines and edges can intersect in only 5 different ways.1/29/2008Ken George81/29/2008Ken George9These intersection types by themselves are not enough to reconstruct a polyhedral sceneThe line segments themselves must be classified, as well1/29/2008Ken George10Four types line segments:•Concave (-)Meets at < 180o•Convex (+)Meets at > 180o•Obscuring Edges ( ->)Visual Boundary of a solid•Cracks (C)Meeting of two edges on a plane1/29/2008Ken George11Combining these segment labels with the junction types creates a new, expanded list.This list is not complete, nor very large•Severely unlikely and physically impossible combinations have been removed1/29/2008Ken George121/29/2008Ken George13A junction can be made by several different combinations of line segmentsA line’s identity does not change between adjacent junctionsThe list of possible labels can be reduced by looking at neighboring junctions1/29/2008Ken George141/29/2008Ken George15Our computer does not understand concepts such as gravity, support, and balanceThe bottom edge of a pillar could be resting on the ground, or floating in the air – both are equally plausible1/29/2008Ken George161/29/2008Ken George17Shadows are traditionally considered a nuisance in computer vision applicationsThe Waltz algorithms uses shadows as an aidWhen shade lines are considered, new junction types are created•This only occurs when a shade line meets a junction or makes a new one1/29/2008Ken George181/29/2008Ken George19With new junction types to implement, many ambiguities can be cleared upShadow and its directionality can help clarify images that might otherwise be questionable1/29/2008Ken George201/29/2008Ken George21Waltz Algorithm input is not an image, but a list of junctions, lines, and surfacesThe algorithm can be summed up by three steps that are executed at every junction (Dewdney)•Determine the junction type and list of labels•Reduce label choices by examining adjacent junctions•Use the newly reduced list to further reduce neighboring junction’s lists1/29/2008Ken George221/29/2008Ken George23(Schmidt)Why does this image pose a problem to the Waltz Algorithm?Why is the Waltz algorithm not often useful for real life applications?1/29/2008Ken George24Dewdney, A.K. The New Turing Omnibus. New York: Computer Science Press, 1989.Schmidt, Charles F. The Waltz Research on Partitioning a Simple visual World into Objects. 26 January 2008. http://www.rci.rutgers.edu/~cfs/305_html/Gestalt/Waltz2.html1/29/2008Ken
View Full Document