Efficient affinity-based edit propagation using K-D tree

Kun Xu, Yong Li, Tao Ju, Shi Min Hu, Tian Qiang Liu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

149 Scopus citations


Image/video editing by strokes has become increasingly popular due to the ease of interaction. Propagating the user inputs to the rest of the image/video, however, is often time and memory consuming especially for large data. We propose here an efficient scheme that allows affinity-based edit propagation to be computed on data containing tens of millions of pixels at interactive rate (in matter of seconds). The key in our scheme is a novel means for approximately solving the optimization problem involved in edit propagation, using adaptive clustering in a high-dimensional, affinity space. Our approximation significantly reduces the cost of existing affinity-based propagation methods while maintaining visual fidelity, and enables interactive stroke-based editing even on high resolution images and long video sequences using commodity computers.

Original languageEnglish
Title of host publicationProceedings of ACM SIGGRAPH Asia 2009, SIGGRAPH Asia '09
StatePublished - 2009
EventACM SIGGRAPH Asia 2009, SIGGRAPH Asia '09 - Yokohama, Japan
Duration: Dec 16 2009Dec 19 2009


ConferenceACM SIGGRAPH Asia 2009, SIGGRAPH Asia '09


Dive into the research topics of 'Efficient affinity-based edit propagation using K-D tree'. Together they form a unique fingerprint.

Cite this