Locating features in warped images

• US 10,482,622 B2
• Filed: 01/29/2018
• Issued: 11/19/2019
• Est. Priority Date: 09/01/2016
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Inc.
• Inventors: Worthington, John
• Primary Examiner(s): Roz, Mark
• Application Number:
  US15/882,312
• Publication Number:
  US 20180150720A1
• Time in Patent Office: 659 Days
• Field of Search: None
• CPC Class Codes: G06F 18/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 3/18 Image warping, e.g. rearranging pixels individually
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 10/945 User interactive design; Environments; Toolboxes

Abstract

Techniques for locating features of interest in warped images are described. For example, a destination image is generated from a source image based on warping a portion of the source image according to a backward map. Each of the two images is associated with a mesh having a tile-based geometry. The backward map maps points from the destination mesh to pixels in the source image. Triangles are formed from the tiles of the destination mesh. A forward map is generated based on the triangles and the backward map. The forward map maps points from the source mesh to pixels in the destination image. A point from the source mesh is identified that corresponds to a pixel of a feature of interest. The forward map is applied to this point to locate a pixel in the destination image. This pixel corresponds to the location of the feature in the destination image.

Claims

1. A computer-implemented method for locating features of interest in displayed images, the computer-implemented method comprising:

outputting, on a display by an image rendering application hosted on a computing device, a source image that comprises a feature of interest, wherein the source image is associated with a source mesh;

accessing, by the image rendering application, a destination image, wherein the destination image is associated with a destination mesh and is generated from the source image based on a backward map, wherein the backward map maps points from the destination mesh to pixels from the source image;

generating, by the image rendering application, a new mesh from the destination mesh by at least changing a geometry of the destination mesh;

generating, by the image rendering application, a forward map based on the new mesh and the backward map, wherein the forward map maps points from the source mesh to pixels from the destination image;

identifying, by the image rendering application, a point from the source mesh, wherein the point from the source mesh corresponds to a pixel of the source image and is associated with the feature of interest;

locating, by the image rendering application, a pixel from the destination image based on the identified point and the forward map; and

outputting, on the display the image rendering application, the destination image, wherein the outputting of the destination image identifies the feature of interest in the destination image based on the located pixel in the destination image.

2. The computer-implemented method of claim 1, wherein the source mesh and the destination mesh have the same geometry, and wherein the new mesh has a different geometry than the geometry of the source mesh and the destination mesh.

3. The computer-implemented method of claim 1, wherein the points of the destination mesh are arranged in geometric shapes of a particular type according to the geometry, wherein the new mesh is generated by at least:

generating, from the geometric shapes, new geometric shapes of a different type according to a different geometry, wherein the new geometric shapes form the new mesh.

4. The computer-implemented method of claim 1, wherein the new mesh is generated by at least applying the backward map to the changed geometry of the destination mesh.

5. The computer-implemented method of claim 1, wherein the points of the destination mesh are arranged in tiles according to the geometry, wherein the new mesh is generated by at least generating triangles from the tiles, and wherein the triangles form the new mesh.

6. The computer-implemented method of claim 5, further comprising:

generating, by the image rendering application, a respective destination matrix for each of the triangles, wherein a destination matrix corresponding to a triangle comprises locations of corners of the triangle, and wherein the forward map is generated based on destination matrices corresponding to the triangles.

7. The computer-implemented method of claim 6, further comprising:

generating, by the image rendering application, source triangles from the triangles based on the backward map and the destination matrices; and

generating, by the image rendering application, a respective source matrix for each of the source triangles, wherein a source matrix corresponding to a source triangle comprises locations of corners of the source triangle.

8. The computer-implemented method of claim 7, further comprising:

generating, by the image rendering application, a forward transformation from each pair of a triangle and a source triangle based on a corresponding destination matrix and a corresponding source matrix.

9. The computer-implemented method of claim 8, further comprising:

identifying, by the image rendering application, that a particular point from the source mesh of the source image falls within an area of a source triangle, wherein the source triangle belongs to a pair of a triangle and a source triangle and is associated with a particular forward transformation; and

generating, by the image rendering application, a forward vector based on the particular point and the particular forward transformation, wherein the forward vector identifies a point from the destination image corresponding to the particular point from the source mesh of the source image.

10. The computer-implemented method of claim 9, wherein the forward map comprises forward vectors generated based on forward transformations applied to points from the source mesh of the source image.

11. A non-transitory computer-readable storage medium storing instructions that, when executed on a computing device, configure the computing device to perform operations comprising:

outputting, on a display, a source image that comprises a feature of interest, wherein the source image is associated with a source mesh;

accessing a destination image, wherein the destination image is associated with a destination mesh and is generated from the source image based on a backward map, wherein the backward map maps points from the destination mesh to pixels from the source image;

generating a new mesh from the destination mesh by at least changing a geometry of the destination mesh;

generating a forward map based on the new mesh and the backward map, wherein the forward map maps points from the source mesh to pixels from the destination image;

identifying a point from the source mesh, wherein the point from the source mesh corresponds to a pixel of the source image and is associated with the feature of interest;

locating a pixel from the destination image based on the identified point and the forward map; and

outputting, on the display, the destination image, wherein the outputting of the destination image identifies the feature of interest in the destination image based on the located pixel in the destination image.

12. The non-transitory computer-readable storage medium of claim 11, wherein the new mesh is generated by at least generating triangles from tiles that form the destination mesh, wherein the triangles form the new mesh, wherein the point from the source mesh is identified from a source triangle, and wherein the operations further comprise:

generating the source triangle by at least applying the backward map to a triangle of the triangles; and

determining that the point from the source mesh belongs to an area defined by the source triangle.

13. The non-transitory computer-readable storage medium of claim 11, wherein the new mesh is generated by at least generating triangles from tiles that form the destination mesh, wherein identifying the point from the source mesh comprises:

generating a source triangle by at least applying the backward map to a triangle of the triangles;

determining that the pixel of the source image belongs to an area defined by the source triangle; and

setting the point from the source mesh as the pixel of the source image.

14. The non-transitory computer-readable storage medium of claim 11, wherein the new mesh is generated by at least generating, from geometric shapes that form the destination mesh and that are of a particular type, new geometric shapes of a different type, and wherein identifying the point from the source mesh comprises:

generating a source geometric shape of the different type by at least applying the backward map to a new geometric shape from the new geometric shapes.

15. The non-transitory computer-readable storage medium of claim 11, wherein the new mesh is generated by at least generating triangles from tiles that form the destination mesh, wherein generating the forward map comprises:

generating a source triangle by at least applying the backward map to a triangle of the triangles;

generating a forward transformation based on the source triangle and the triangle; and

generating a forward vector by applying the forward transformation to the identified point from the source mesh of the source image.

16. The non-transitory computer-readable storage medium of claim 15, wherein the operations further comprise:

determining that the source triangle is flat;

determining locations of three points from the destination mesh of the destination image, wherein the three points correspond to corners of the triangle; and

generating an average location by averaging the locations of the three points, wherein the forward vector maps the identified point from the source mesh of the source image to the average location.

17. A system comprising:

a processor; and

a memory communicatively coupled to the processor and storing instructions of an image rendering application, wherein the instructions, upon execution by the processor, cause the system to perform image rendering operations comprising;

outputting, on a display, a source image that comprises a feature of interest, wherein the source image is associated with a source mesh;

accessing a destination image, wherein the destination image is associated with a destination mesh and is generated from the source image based on a backward map, wherein the backward map maps points from the destination mesh to pixels from the source image;

generating a new mesh from the destination mesh by at least changing a geometry of the destination mesh;

generating a forward map based on the new mesh and the backward map, wherein the forward map maps points from the source mesh to pixels from the destination image;

identifying a point from the source mesh, wherein the point from the source mesh corresponds to a pixel of the source image and is associated with the feature of interest;

locating a pixel from the destination image based on the identified point and the forward map; and

outputting, on the display, the destination image, wherein the outputting of the destination image identifies the feature of interest in the destination image based on the located pixel in the destination image.

18. The system of claim 17, wherein outputting the source image comprises rendering a graphical user interface (GUI) element that identifies the feature of interest in the source image, wherein outputting the destination image comprises rendering the GUI element that identifies the feature of interest in the destination image, and wherein the destination image is generated from the source image by at warping at least a portion of the source image based on the backward map.

19. The system of claim 17, wherein locating the pixel from the destination image comprises storing a location information about the pixel from the destination image based on a shift relative to a location of the identified point from the source mesh of the source image.

20. The system of claim 19, wherein the image rendering operations further comprise:

locating a second pixel from the destination image based on the forward map and a second point from the source mesh of the source image;

determining that a location of the second pixel did not shift relative to a location of the second point; and

selectively storing the location information about the pixel from the destination image and not storing location information about the second pixel based on the pixel from the destination image having a location shift and the second pixel not having a location shift.