Rendering a text image using texture map character center encoding with character reference encoding

• US 8,760,451 B2
• Filed: 06/30/2011
• Issued: 06/24/2014
• Est. Priority Date: 06/30/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cornell, Brian
• Primary Examiner(s): Wu, Xiao
• Assistant Examiner(s): He, Yingchun
• Application Number:
  US13/174,403
• Publication Number:
  US 20130002680A1
• Time in Patent Office: 1,090 Days
• Field of Search: None
• US Class Current: 345/467
• CPC Class Codes: G06F 40/109 Font handling; Temporal or kinetic typography
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A graphics or image rendering system, such as a map image rendering system, receives image data from an image database in the form of vector data that defines various image objects, such as roads, geographical boundaries, etc., and textures defining text strings to be displayed on the image to provide, for example, labels for the image objects. The imaging rendering system renders the images such that the individual characters of the text strings are placed on the image following a multi-segmented or curved line. In doing so, the image rendering system creates and reads a texture map that stores pixelated text characters of the text strings to be rendered in the image as a set of glyphs and that also stores first encoding data defining the center position of each text character as stored in a glyph and second encoding data referencing the location of the glyph to be used as the text character. This center position encoding enables the system to determine whether, in any particular instance, a text character of a text string should be rendered in the image at a particular position along the line or at a different position along the line while maximizing the storage efficiency of the texture map used to store the text string by allowing text characters repeated in a text string to be stored only once in the texture map.

Claims

1. A computer-implemented method for rendering a text image on a display device, comprising:

accessing, using a computer device, an image lookup table having a set of encoded data for two or more text characters associated with a text string of two or more text characters to be rendered in an image;

reading, using a computer device, the set of encoded data from the image lookup table to determine first and second encoding data for one of the text characters associated with the text string, the first encoding data for the one of the text characters defining information about the position of the text character in the text string and the second encoding data for the one of the text characters defining a reference to a field of pixels in the image lookup table storing a set of pixel values defining the image to be rendered for the one of the text characters;

determining, using the computer device, pixel values for the one of the text characters from the referenced field of pixels for the one of the text characters as stored within the image lookup table to analyze for rendering at a particular position within the image;

determining, using the computer device, a center position of the one of the text characters stored in the field of pixels defined by the second encoding data for the one of the text characters based on the first encoding data for the one of the text characters; and

rendering, using the computer device, pixels of the one of the text characters at a particular position within the image based on the location of the center position of the one of the text characters.

2. The computer-implemented method of claim 1, wherein rendering the pixels of the one of the text characters at the particular position within the image based on the location of the center position of the one of the text characters includes determining if the center position of the one of the text characters, when rendered in a text box on the image, will be within a range of the text box and rendering the pixels of the one of the text characters at the particular position within the image when the center of the one of the text characters, when rendered in the text box on the image, will be within the range of the text box.

3. The computer implemented method of claim 1, further including not rendering the pixels of the one of the text characters at the particular position within the image when the center of the one of the text characters, when rendered in the text box on the image, will be outside of the range of the text box.

4. The computer-implemented method of claim 1, wherein reading the set of encoding data includes reading the first encoding data specifying a width of the text character.

5. The computer-implemented method of claim 1, wherein reading the set of encoding data includes reading the first encoding data stored for a particular column of pixels of the one of the text characters, the first encoding data specifying the distance from the particular column of pixels of the one of the text characters to a column of pixels at the center of the one of the text characters.

6. The computer-implemented method of claim 1, wherein reading the set of encoding data includes reading first encoding data stored in the image lookup table at a position adjacent to the second encoding data.

7. The computer-implemented method of claim 1, wherein reading the set of encoding data includes reading the first encoding data stored in a row of the image lookup table having first encoding data information defining, for each of a plurality of columns of the image lookup table, the distance from a column location to the column location of the center of the one of the text character.

8. The computer-implemented method of claim 7, wherein reading the set of encoding data includes reading the second encoding data from a row of the image lookup table associated with the row of the first encoding data, the second encoding data having a fixed location with respect to one of the columns of the first encoding data.

9. The computer-implemented method of claim 7, wherein reading the set of encoding data includes reading the second encoding data from a row of the image lookup table associated with the row of the first encoding data, the second encoding data starting at the column of the image lookup table at which the first encoding data indicates is the center column of the text character.

10. The computer-implemented method of claim 1, wherein the first encoding data for the one of the text characters is stored in a first row of encoding data spanning multiple columns of the image lookup table and wherein the second encoding data for the one of the text characters is stored in a second row of encoding data spanning a plurality of columns of the text image lookup table defining a subset of the multiple columns of the image lookup table used by the first encoding data, and wherein reading the first encoding data associated with the one of the text characters to determine a center position of the one of the text characters includes reading first encoding data for a particular column of pixels of the one of the text characters located in the field of pixels defined by the second encoding data of the one of the text characters.

11. The computer-implemented method of claim 1, wherein the image lookup table is two-dimensional texture map.

12. An image rendering engine, comprising;

a processor;

a memory coupled to the processor;

a display device coupled to the processor;

a text string lookup table stored in the memory that includes a set of glyphs and one or more sections of encoding data, wherein each glyph is stored as a field of pixels defining a displayable image associated with a text character, and wherein each section of encoding data defines a text string of two or more text characters to be rendered in an image, wherein each section of encoding data includes two or more sets of character encoding data with each set of character encoding data including first encoding data defining information about a position of a particular text character in the text string from which the center position of the particular text character can be determined and second encoding data defining a reference to one of the glyphs to define the identity of the particular text character in the text string; and

a routine, stored in the memory, that executes on the processor to read the first and second encoding data of a particular set of character encoding data for a text character to determine a position of one or more pixels stored with a glyph associated with the text character within the text string to be rendered in an image.

13. The image rendering engine of claim 12, wherein the routine determines a center of the text character of the glyph referenced by the second encoding data using the first encoding data associated with the particular set of character encoding data.

14. The image rendering engine of claim 12, including a further routine stored in the memory that executes on the processor to render pixels located at one or more positions within the field of pixels of one of the glyphs at a particular position within an image on the display device based on the first encoding data defining the location of the center position of the text character referenced by the second encoding data.

15. The image rendering engine of claim 14, wherein the further routine renders the pixels located at the one or more positions within the field of pixels of the one of the glyphs at the particular position within the image based on the first encoding data by determining if the center position of the text character, when rendered in a text box on the image, will be within a range of the text box and by rendering the pixels located at the one or more positions within the field of pixels of the one of the glyphs at the particular position within the image when the center of the text character, when rendered in the text box on the image, will be within the range of the text box.

16. The image rendering engine of claim 12, wherein the first encoding data includes encoding data specifying a width of a text character defined by a glyph.

17. The image rendering engine of claim 12, wherein the first encoding data for a particular text character includes first encoding data at each of a set of pixel columns for the particular text character specifying a distance from the pixel column of the first encoding data to the center pixel column of the particular text character defined by a glyph referenced by the second encoding data for the particular text character.

18. The image rendering engine of claim 12, wherein the first encoding data of each text character in the text string is stored at a position in the text string lookup table adjacent to the second encoding data of each text character.

19. The image rendering engine of claim 12, wherein the second encoding data of one of the text characters of one of the sections of sets of encoding data refers to the same glyph as the second encoding data of a different one of the text characters of the one of the sections of sets of encoding data.

20. The image rendering engine of claim 12, wherein the second encoding data of one of the text characters of one of the sections of sets of encoding data refers to the same glyph as the second encoding data of one of the text characters of a second one of the sections of sets of encoding data.

21. The image rendering engine of claim 12, wherein each of the sets of sections of encoding data includes the first encoding data stored in a row of the text string lookup table defining, for each of a plurality of columns of the text string lookup table, the distance from a column location to the column location of the center of a pixel column of the text character referenced by the second encoding data.

22. The image rendering engine of claim 21, wherein each of the sections of sets of encoding data includes the second encoding data stored in a fixed location in the text string lookup table with respect to one of the columns of the first encoding data.

23. The image rendering engine of claim 22, wherein second encoding data is stored starting at a column location of the text string lookup table at a column that is indicated by the first encoding data to be the center position of a text character.

24. The image rendering engine of claim 12, wherein the first encoding data for one of the text characters is stored in a first row of encoding data spanning multiple columns of the text string lookup table and wherein the second encoding data for the one of the text characters is stored in a second row of encoding data spanning a plurality of columns of the text string lookup table defining a subset of the multiple columns of the text string lookup table used by the first encoding data, and wherein the first encoding data for the one of the text characters defines a center position of the one of the text characters located in the field of pixels of the glyph defined by the second encoding data of the one of the text characters.

25. The image rendering engine of claim 12, wherein the first encoding data for each text character is stored in a row of the text string lookup table above the second encoding data for each text character.

26. The image rendering engine of claim 12, wherein the sets of character encoding data for one of sections of encoding data are stored as a single line of sets of character encoding data with the first encoding data for each text character within the one of the sections of encoding data sharing at least one common row in the text string lookup table but not having any overlapping columns in the text string lookup table.

27. The image rendering engine of claim 12, wherein the sets of character encoding data for one of sections of encoding data are stored as a two or more lines of sets of character encoding data with the first encoding data for each text character in the same line of sets of character encoding data sharing at least one common row in the text string lookup table but not having any overlapping columns in the text string lookup table and with the first encoding data for each text character in different lines of sets of character encoding data not sharing any rows of the text string lookup table.

28. The image rendering image of claim 27, wherein first encoding data for at least one text character in a first one of the lines of sets of character encoding data includes a column that overlaps with a column of a first encoding data of a different text character in a second one of the lines of sets of character encoding data.

29. The image rendering image of claim 27, wherein the at least one text character and the different text character are adjacent text characters in the text string defined by the section of encoding data.

30. A method of creating a text string lookup table, comprising:

storing, in a computer memory at memory positions defining the text string lookup table, a set of glyphs, wherein each glyph is stored as a field of pixels defining a displayable image associated with a text character such that multiple pixels are stored in the memory for each glyph; and

storing, in the computer memory at memory positions defining the text string lookup table, one or more sections of encoding data, wherein each section of encoding data defines a text string of two or more text characters to be rendered in an image and wherein each section of encoding data includes two or more sets of character encoding data with each set of character encoding data defining a text character of the text string and including first encoding data defining information about a position of a text character in the text string from which the center position of the text character can be determined and second encoding data defining a reference to one of the glyphs to define the identity of the text character in the text string.

31. The method of claim 30, wherein storing the first encoding data for each text character includes storing first encoding data defining the center position of a text character of the text string, the first encoding data for each of the sets of character encoding data being coordinated in location within the memory defining the text string lookup table with the second encoding data of the same set of character encoding data.

32. The method of claim 30, wherein storing the first encoding data for each text character includes storing first encoding data specifying a distance to a center of a text character at each of a set of different pixel positions of each text character.

33. The method of claim 30, wherein storing the first encoding data for each text character includes storing encoding data at each of a set of pixel columns for the particular text character specifying a distance from the pixel column of the encoding data to the center pixel column of the particular text character defined by a glyph referenced by the second encoding data for the particular text character.

34. The method of claim 30, wherein storing the first encoding data for each text character includes storing the first encoding data of each text character in the text string at a position in the text string lookup table adjacent to the second encoding data of each text character.

35. The method of claim 30, wherein storing the second encoding data of one of the text characters of one of the sections of sets of encoding data refers to the same glyph as the second encoding data of a different one of the text characters of the one of the sections of sets of encoding data.

36. The method of claim 30, wherein storing the second encoding data of one of the text characters of one of the sections of sets of encoding data refers to the same glyph as the second encoding data of one of the text characters of a second one of the sections of sets of encoding data.

37. The method of claim 30, wherein storing each of the sets of sections of encoding data includes storing the first encoding data in a row of the text string lookup table defining, for each of a plurality of columns of the text string lookup table, the distance from the column location to the column location of the center of a pixel column of the text character referenced by the second encoding data.

38. The method of claim 37, wherein storing each of the sections of sets of encoding data includes storing the second encoding data in a fixed location in the text string lookup table with respect to one of the columns of the first encoding data.

39. The method of claim 30, wherein storing the first encoding data for one of the text characters includes storing the first encoding data in a first row of encoding data spanning multiple columns of the text string lookup table and wherein storing the second encoding data for the one of the text characters includes storing the second encoding data in a second row of encoding data spanning a plurality of columns of the text string lookup table defining a subset of the multiple columns of the text string lookup table used by the first encoding data.

40. The method of claim 30, further including storing the sets of character encoding data for one of sections of encoding data as a single line of sets of character encoding data with the first encoding data for each text character within the one of the sections of encoding data sharing at least one common row in the text string lookup table but not having any overlapping columns in the text string lookup table.

41. The method of claim 30, further including storing the sets of character encoding data for one of sections of encoding data as two or more lines of sets of character encoding data with the first encoding data for each text character in the same line of sets of character encoding data sharing at least one common row in the text string lookup table but not having any overlapping columns in the text string lookup table and with the first encoding data for each text character in different lines of sets of character encoding data not sharing any rows of the text string lookup table.

42. The method of claim 30, including storing first encoding data for at least one text character in a first one of the lines of sets of character encoding data in a column that overlaps with a column for a different text character in a second one of the lines of sets of character encoding data.