AbstractWe present a new, interactive tool called Intelligent Scissorswhich we use for image segmentation and composition. Fully auto-mated segmentation is an unsolved problem, while manual tracingis inaccurate and laboriously unacceptable. However, IntelligentScissors allow objects within digital images to be extracted quicklyand accurately using simple gesture motions with a mouse. Whenthe gestured mouse position comes in proximity to an object edge,a live-wire boundary “snaps” to, and wraps around the object ofinterest.Live-wire boundary detection formulates discrete dynamic pro-gramming (DP) as a two-dimensional graph searching problem. DPprovides mathematically optimal boundaries while greatly reducingsensitivity to local noise or other intervening structures. Robust-ness is further enhanced with on-the-fly training which causes theboundary to adhere to the specific type of edge currently being fol-lowed, rather than simply the strongest edge in the neighborhood.Boundary cooling automatically freezes unchanging segments andautomates input of additional seed points. Cooling also allows theuser to be much more free with the gesture path, thereby increasingthe efficiency and finesse with which boundaries can be extracted.Extracted objects can be scaled, rotated, and composited usinglive-wire masks and spatial frequency equivalencing. Frequencyequivalencing is performed by applying a Butterworth filter whichmatches the lowest frequency spectra to all other image compo-nents. Intelligent Scissors allow creation of convincing composi-tions from existing images while dramatically increasing the speedand precision with which objects can be extracted.1. IntroductionDigital image composition has recently received much attentionfor special effects in movies and in a variety of desktop applica-tions. In movies, image composition, combined with other digitalmanipulation techniques, has also been used to realistically blendold film into a new script. The goal of image composition is to com-bine objects or regions from various still photographs or movieframes to create a seamless, believable, image or image sequencewhich appears convincing and real. Fig. 9(d) shows a believablecomposition created by combining objects extracted from threeimages, Fig. 9(a-c). These objects were digitally extracted andcombined in a few minutes using a new, interactive tool calledIntel-ligent Scissors.When using existing images, objects of interest must be extractedand segmented from a surrounding background of unpredictablecomplexity. Manual segmentation is tedious and time consuming,lacking in precision, and impractical when applied to long imagesequences. Further, due to the wide variety of image types and con-tent, most current computer based segmentation techniques areslow, inaccurate, and require significant user input to initialize orcontrol the segmentation process.This paper describes a new, interactive, digital image segmenta-tion tool called “Intelligent Scissors” which allows rapid objectextraction from arbitrarily complex backgrounds. Intelligent Scis-sors boundary detection formulates discrete dynamic programming(DP) as a two-dimensional graph searching problem. Presented aspart of this tool are boundary cooling and on-the-fly training, whichreduce user input and dynamically adapt the tool to specific types ofedges. Finally, we present live-wire masking and spatial frequencyequivalencing for convincing image compositions.2. BackgroundDigital image segmentation techniques are used to extract imagecomponents from their surrounding natural background. However,currently available computer based segmentation tools are typicallyprimitive and often offer little more advantage than manual tracing.Region based magic wands, provided in many desktop applica-tions, use an interactively selected seed point to “grow” a region byadding adjacent neighboring pixels. Since this type of region grow-ing does not provide interactive visual feedback, resulting regionboundaries must usually be edited or modified.Other popular boundary definition methods use active contoursor snakes[1, 5, 8, 15] to improve a manually entered rough approx-imation. After being initialized with a rough boundary approxima-tion, snakes iteratively adjust the boundary points in parallel in anattempt to minimize an energy functional and achieve an optimalboundary. The energy functional is a combination of internalforces, such as boundary curvature, and external forces, like imagegradient magnitude. Snakes can track frame-to-frame boundarymotion provided the boundary hasn’t moved drastically. However,active contours follow a pattern of initialization followed by energyminimization; as a result, the user does not know what the finalboundary will look like when the rough approximation is input. Ifthe resulting boundary is not satisfactory, the process must berepeated or the boundary must be manually edited. We provide adetailed comparison of snakes and Intelligent Scissors in section3.6.Another class of image segmentation techniques use a graphsearching formulation of DP (or similar concepts) to find globallyoptimal boundaries [2, 4, 10, 11, 14]. These techniques differ fromsnakes in that boundary points are generated in a stage-wise optimalcost fashion whereas snakes iteratively minimize an energy func-tional for all points on a contour in parallel (giving the appearanceof wiggling). However, like snakes, these graph searching tech-niques typically require a boundary template--in the form of a man-ually entered rough approximation, a figure of merit, etc.--which isused to impose directional sampling and/or searching constraints.This limits these techniques to a boundary search with one degreeof freedom within a window about the two-dimensional boundarytemplate. Thus, boundary extraction using previous graph search-ing techniques is non-interactive (beyond template specification),losing the benefits of further human guidance and expertise.Intelligent Scissors for Image CompositionEric N. Mortensen1 William A. Barrett2Brigham Young [email protected], Dept. of Comp. Sci., BYU, Provo, UT 84602 (801)[email protected], Dept. of Comp. Sci., BYU, Provo, UT 84602 (801)378-7430The most important difference between previous boundary find-ing techniques and Intelligent Scissors presented here lies not in theboundary defining criteria per se´, but in the method of interaction.Namely, previous