# US 7,593,022 B2 · Structure-preserving clone brush > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,593,022 B2 - Document ID: US7593022B2 - Status: Granted - Kind: B2 - Application number: 11/951,355 - Filed: 2007-12-06 - Published: 2008-04-17 - Granted: 2009-09-22 - Earliest claimed: 2003-04-30 - Assignees: EveryScape, Inc. - Inventors: Byong Mok Oh; Fredo Durand - Web page: https://patentgrep.com/patent/US7593022B2 ## CPC - G06T 11/60: Creating or editing images; Combining images with text - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract The invention provides tools and techniques for clone brushing pixels in an image while accounting for inconsistencies in apparent depth and orientation within the image. The techniques do not require any depth information to be present in the image, and the data structure of the image is preserved. The techniques allow for color compensation between source and destination regions. A snapping technique is also provided to facilitate increased accuracy in selecting source and destination positions. ## Claims ### Claim 1 A computer program product for clone-brushing in a 2D image, the computer program product comprising a computer readable medium having computer readable program code stored thereon, the computer readable program code including program code for: a) specifying a first world plane in the 2D image; b) providing a source position and a destination position in the 2D image; c) identifying a destination region in the 2D image relative to the destination position; d) determining a source region in the 2D image corresponding to the destination region in the 2D image including: defining a transformation that maps the destination position relative to the first world plane to the source position relative to the first world plane using a homography defined by the first world plane, and identifying pixels in the source region of the 2D image corresponding to pixels in the destination region of the 2D image using the transformation and the homography; e) transforming 2D image information of the source region relative to the first world plane to 2D image information of the destination region; and f) painting in the 2D image by copying the transformed 2D image information to the destination region. ### Claim 2 (depends on 1) The computer program product of claim 1, wherein specifying a first world plane in the 2D image comprises specifying two sets of parallel lines. ### Claim 3 (depends on 1) The computer program product of claim 1, wherein transforming 2D image information further comprises a bilinear interpolation of 2D image information in the source region relative to the first world plane. ### Claim 4 (depends on 1) The computer program product of claim 1 further comprising program code for: providing a first color sample region for the source region; providing a second sample color region for the destination region; and computing a color ratio between the first color sample region and the second color sample region, wherein transforming 2D image information further comprises applying the color ratio to the 2D image information of the source region. ### Claim 5 (depends on 4) The computer program product of claim 4, wherein the color ratio is computed using Gaussian weighted averages of the first and second sample color regions. ### Claim 6 (depends on 4) The computer program product of claim 4, wherein the first color sample region is provided with respect to the first world plane. ### Claim 7 (depends on 1) The computer program product of claim 1, further comprising program code for specifying a second world plane and a relative scale factor in the 2D image, wherein: determining a source region in the 2D image comprises determining a source region in the 2D image relative to the first world plane and corresponding to the destination region relative to the second world plane and the relative scale factor; and transforming 2D image information comprises transforming the 2D image information of the source region relative to the first world plane to 2D image information of the destination region relative to the second world plane and the relative scale factor. ### Claim 8 (depends on 7) The computer program product of claim 7, wherein specifying the second world plane comprises specifying two sets of parallel lines. ### Claim 9 (depends on 7) The computer program product of claim 7, wherein specifying the relative scale factor comprises specifying a line segment of unit length relative to the first world plane and specifying a line segment of unit length relative to the second world plane. ### Claim 10 (depends on 1) A computer program product according to claim 1, wherein the destination position is a snapped destination position. ### Claim 11 (depends on 10) The computer program product of claim 10, wherein determining a snapped destination position comprises searching a collection of candidate destination positions. ### Claim 12 (depends on 1) A computer program product defined by claim 1, wherein the first world plane in the 2D image is not parallel to the plane containing the 2D image. ### Claim 13 (depends on 12) A computer program product defined by claim 12, wherein specifying a first world plane in the 2D image comprises specifying two sets of parallel lines. ### Claim 14 (depends on 12) A computer program product defined by claim 12, wherein transforming 2D image information further comprises a bilinear interpolation of 2D image information in the source region relative to the first world plane. ### Claim 15 (depends on 12) A computer program product defined by claim 12 further comprising program code for: providing a first color sample region for the source region; providing a second sample color region for the destination region; and computing a color ratio between the first color sample region and the second color sample region, wherein transforming 2D image information further comprises applying the color ratio to the 2D image information of the source region. ### Claim 16 (depends on 15) A computer program product defined by claim 15, wherein the color ratio is computed using Gaussian weighted averages of the first and second sample color regions. ### Claim 17 (depends on 15) A computer program product defined by claim 15, wherein the first color sample region is provided with respect to the first world plane. ### Claim 18 (depends on 12) A computer program product defined by claim 12, further comprising program code for specifying a second world plane and a relative scale factor in the 2D image, wherein: determining a source region in the 2D image comprises determining a source region in the 2D image relative to the first world plane and corresponding to the destination region relative to the second world plane and the relative scale factor; and transforming 2D image information comprises transforming the 2D image information of the source region relative to the first world plane to 2D image information of the destination region relative to the second world plane and the relative scale factor. ### Claim 19 A computer program product for clone-brushing in a 2D image, the computer program product comprising a computer readable medium having computer readable program code stored thereon, the computer readable program code including program code for: providing a source position in the 2D image; providing a destination position in the 2D image; identifying a destination region in the 2D image relative to the destination position; determining a source region in the 2D image corresponding to the destination region; providing a first color sample region in the source region; providing a second color sample region in the destination region; computing a color ratio between the first color sample region and the second color sample region; applying the color ratio to 2D image information of the source region and transforming the 2D image information of the source region to 2D image information of the destination region; and painting by copying the transformed 2D image information to the destination region. ### Claim 20 (depends on 19) The computer program product of claim 19, wherein the color ratio is computed using Gaussian weighted averages of the first and second sample color regions. ### Claim 21 A computer program product for clone-brushing in a 2D image, the computer program product comprising a computer readable medium having computer readable program code stored thereon, the computer readable program code including program code for: a) providing a source position in the 2D image; b) providing an initial destination position in the 2D image; c) determining a snapped destination position; d) identifying a destination region in the 2D image relative to the snapped destination position; e) determining a source region in the 2D image corresponding to the destination region; f) transforming 2D image information of the source region to 2D image information of the destination region; and g) painting by copying the transformed 2D image information to the destination region, wherein determining a snapped destination position comprises searching a collection of candidate destination positions and wherein determining a snapped destination position further comprises applying a quality metric to the source position, applying the quality metric to the candidate destination positions, and determining a snapped destination position from the collection of candidate destination positions whose quality is similar to the quality of the source position. ### Claim 22 (depends on 21) The computer program product of claim 21, wherein the quality metric is a Gaussian-weighted color average for a region surrounding the position. ### Claim 23 (depends on 21) The computer program product of claim 21, wherein the quality metric compensates for regional color variation by applying a color ratio. ### Claim 24 A clone-brushing method of painting in a 2D image, the method comprising: a) specifying a first world plane in the 2D image; b) providing a source position and a destination position in the 2D image; c) identifying a destination region in the 2D image relative to the destination position; d) determining a source region in the 2D image corresponding to the destination region in the 2D image including: defining a transformation that maps the destination position relative to the first world plane to the source position relative to the first world plane using a homography defined by the first world plane, and identifying pixels in the source region of the 2D image corresponding to pixels in the destination region of the 2D image using the transformation and the homography; e) transforming 2D image information of the source region relative to the first world plane to 2D image information of the destination region; and f) painting in the 2D image by copying the transformed 2D image information to the destination region, wherein the first world plane in the 2D image is not parallel to the plane containing the 2D image. ### Claim 25 (depends on 24) A method according to claim 24, wherein specifying a first world plane in the 2D image comprises specifying two sets of parallel lines. ### Claim 26 (depends on 24) A method according to claim 24, wherein transforming 2D image information further comprises a bilinear interpolation of 2D image information in the source region relative to the first world plane. ### Claim 27 (depends on 24) A method according to claim 24 further comprising: providing a first color sample region for the source region; providing a second sample color region for the destination region; and computing a color ratio between the first color sample region and the second color sample region, wherein transforming 2D image information further comprises applying the color ratio to the 2D image information of the source region. ### Claim 28 (depends on 27) A method according to claim 27, wherein the color ratio is computed using Gaussian weighted averages of the first and second sample color regions. ### Claim 29 (depends on 27) A method according to claim 27, wherein the first color sample region is provided with respect to the first world plane. ### Claim 30 (depends on 24) A method according to claim 24, further comprising specifying a second world plane and a relative scale factor in the 2D image, wherein: determining a source region in the 2D image comprises determining a source region in the 2D image relative to the first world plane and corresponding to the destination region relative to the second world plane and the relative scale factor; and transforming 2D image information comprises transforming the 2D image information of the source region relative to the first world plane to 2D image information of the destination region relative to the second world plane and the relative scale factor. ### Claim 31 (depends on 30) A method according to claim 30, wherein specifying the second world plane comprises specifying two sets of parallel lines. ### Claim 32 (depends on 30) A method according to claim 30, wherein specifying the relative scale factor comprises specifying a line segment of unit length relative to the first world plane and specifying a line segment of unit length relative to the second world plane.