Locating features in warped images

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.

The invention claimed is: 
     
       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.