“Intelligent scissors for image composition” by Mortensen and Barrett

We present a new, interactive tool called Intelligent Scissors which we use for image segmentation and composition. Fully automated segmentation is an unsolved problem, while manual tracing is inaccurate and laboriously unacceptable. However, Intelligent Scissors allow objects within digital images to be extracted quickly and accurately using simple gesture motions with a mouse. When the gestured mouse position comes in proximity to an object edge, a live-wire boundary “snaps” to, and wraps around the object of interest. Live-wire boundary detection formulates discrete dynamic programming (DP) as a two-dimensional graph searching problem. DP provides mathematically optimal boundaries while greatly reducing sensitivity to local noise or other intervening structures. Robustness is further enhanced with on-the-fly training which causes the boundary to adhere to the specific type of edge currently being followed, rather than simply the strongest edge in the neighborhood. Boundary cooling automatically freezes unchanging segments and automates input of additional seed points. Cooling also allows the user to be much more free with the gesture path, thereby increasing the efficiency and finesse with which boundaries can be extracted. Extracted objects can be scaled, rotated, and composited using live-wire masks and spatial frequency equivalencing. Frequency equivalencing is performed by applying a Butterworth filter which matches the lowest frequency spectra to all other image components. Intelligent Scissors allow creation of convincing compositions from existing images while dramatically increasing the speed and precision with which objects can be extracted.

1. A.A. Amini, T. E. Weymouth, and R. C. Jain, “Using Dynamic Programming for Solving Variational Problems in Vision,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 2, pp. 855-866, Sept. 1990.
2. D.H. Ballard, and C. M. Brown, Computer Vision. Englewood Cliffs, NJ: Prentice Hall, 1982.
3. R. Bellman and S. Dreyfus, Applied Dynamic Programming. Princeton, NJ: Princeton University Press, 1962.
4. Y. E Chien and K. S. Fu, “A Decision Function Method for Boundary Detection,” Computer Graphics and Image Processing, vol. 3, no. 2, pp. 125-140, June 1974.
5. D. Daneels, et al., “Interactive Outlining: An Improved Approach Using Active Contours,” in SPIE Proceedings of Storage and Retrieval for Image and Video Databases, vol 1908, pp. 226-233, Feb. 1993.
6. E.W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, pp. 269-270, 1959.
7. M.M. Fleck, “Multiple Widths Yield Reliable Finite Differences,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no. 4, pp. 412-429, April 1992.
8. M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active Contour Models,” in Proceedings of the First International Conference on Computer Vision, London, England, pp. 259- 68, June 1987.
9. D. Marr and E. Hildreth, “A Theory of Edge Detection,” in Proceedings of the Royal Society of London–Series B: Biological Sciences, vol. 207, no. 1167, pp. 187-217, Feb. 1980.
10. A. Martelli, “An Application of Heuristic Search Methods to Edge and Contour Detection,” Communications of the ACM, vol. 19, no. 2, pp. 73-83, Feb. 1976.
11. U. Montanari, “On the Optimal Detection of Curves in Noisy Pictures,” Communications of the ACM, vol. 14, no. 5, pp. 335-45, May 1971.
12. E. N. Mortensen, B. S. Morse, W. A. Barrett, and J. K. Udupa, “Adaptive Boundary Dectection Using ‘Live-Wire’ Two- Dimensional Dynamic Programming,” in IEEE Proceedings of Computers in Cardiology, pp. 635-638, Oct. 1992.
13. N. J. Nilsson, Principles of Artificial Intelligence. Palo Alto, CA: Tioga, 1980.
14. D. L. Pope, D. L. Parker, D. E. Gustafson, and E D. Clayton, “Dynamic Search Algorithms in Left Ventricular Border Recognition and Analysis of Coronary Arteries,” in IEEE Proceedings of Computers in Cardiology, pp. 71-75, Sept. 1984.
15. D. J. Williams and M. Shah, “A Fast Algorithm for Active Contours and Curvature Estimation,” CVGIP: Image Understanding, vol. 55, no. 1, pp. 14-26, Jan. 1992.