Enhancement of markup language pages to support spoken queries

[0002] This application claims priority under 35USC § 119(e)(1) of provisional application No. 60/073,826, filed Feb. 5, 1998.

[0003] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.

[0004] This invention relates to markup pages and more particularly to enhancement of markup pages to support spoken queries.

[0005] A system has been described whereby users of hypertext browsers may speak the hinks in hypertext documents using a dynamic-grammar, arbitrary-vocabulary, speaker-independent, continuous speech recognizer. See the following references: Hemphill, Charles T. and Thrift, Philip R., “Surfing the Web by Voice,” Proceeding of Multimedia'95, No. 5-9, San Francisco, Calif. Philip R. Thrift and Charles T. Hemphill “Voice Activated World Wide Web Pages Using Grammatical Metadata (Smart Pages)”, filed U.S. patent office Apr. 10, 1995, Ser. No. 08/419,229. A Protocol for adding natural language grammars to Web pages is described, which is utilized by a client-side speech recognition system to establish human to computer communication. This application is incorporated herein by reference. Charles T. Hemphill “Speaker-Independent Dynamic Vocabulary and Grammars in Speech Recognition”, filed U.S. patent office: Apr. 10, 1995, U.S. Pat. No. 5,774,628. A method for dynamically creating grammars and pronunciations for arbitrary vocabulary tokens and how to incorporate them into a running, speaker-independent recognizer. This application is incorporated herein by reference. Increasingly, however, pages include more and more graphical images that do not explicitly indicate what the user might say to follow a link.

[0006] Other speech recognition systems have tried to cope with selection of graphical images by using speech commands to move the mouse. Such systems allow utterances such as “Mouse Move Up”, Mouse Move Left”, “Mouse Move Faster”, “Mouse Move Slower”, “Mouse Stop”, “Mouse Click”, etc. This method requires many queries and involves waiting for the mouse cursor to travel to the desired spot.

[0007] Another method divides the screen into grid areas (for example, 3 by 3) and lets the user position the mouse by selecting progressively more detailed areas. An interaction in this case might include utterances such as “Enable Grid”, “Grid Area 5” (the grid reconfigures for the smaller area), “Grid Area 1” (the grid again reconfigures), “Grid Area 3”, “Mouse Click”. This method also requires many queries, but eliminates the wait for mouse cursor movement.

[0008] In accordance with one embodiment of the present invention, enhancement of markup pages such as hypertext pages to support spoken queries is provided whereby what to say becomes explicit and associated with a presentation. The enhancement device is coupled to a presentation means and responsive to markup language features for generating and presenting on the presentation means speech activation link queries in explicit locations with respect to the markup language features.

[0009] FIG. 1 is a block diagram of a system according to one embodiment of the present invention;

[0010] FIG. 2 is a diagram illustrating one embodiment of the present invention;

[0011] FIG. 3 illustrates an HTML page;

[0012] FIG. 4 illustrates a flow chart for transforming an HTML page to speakable options;

[0013] FIG. 5 illustrates a transformed HTML page from FIG. 3;

[0014] FIG. 6 illustrates another HTML page with an image without an ALT tag and with area images;

[0015] FIG. 7 illustrates a transformed HTML page from FIG. 6;

[0016] FIG. 8 illustrates a transformed HTML page with overlays; and

[0017] FIG. 9 illustrates a second transformed HTML page with overlays.

[0018] Referring to FIG. 1 there is illustrated a system 10 according to one embodiment of the present invention. The system includes a computer 11 with a display 13. The computer includes a voice recognizer 15, a RAM and/or ROM memory 17 and disk drive 27. The system may also be coupled to a server and database 19. The computer may include a built-in modem or an external modem 23 or an Ethernet, LAN, etc. and a browser 18. The computer 11 also includes, for example, an Internet connection 14 with, for example, a markup language page source such as any Standard Markup Language (SGML) like Hypertext Markup Language, (HTML) or Hand-held Device Markup Language (HDML) from a service provider 16 where links and destination sources are denoted by text and graphics. HTML is a collection of platform-independent styles that define parts of a World Wide Web (WWW) document. The styles are indicated by markup tags.

[0019] HTML documents are plain text ASCII files that are created by any text editor like notepad on a Windows machine. HTML tags mark the elements of a file for the browser. An element is a fundamental component of the structure of a document such as a table, heads, paragraphs and lists. Tags denote various elements in the HTML document and consist of a left angle bracket (<), a tag name, and a right angle bracket (>). The tags are normally paired to start and end an instruction. The end tag is like the start tag except a slash (/) precedes the text within the brackets. The required elements are <html>, <head>, <title> and <body> tags. HTML has six levels of heading denoted by, for example, <H1> for heading 1. A <BR> tag forces a line break with no extra (white) space between lines. A “Beginner's Guide to HTML” is available from NCSA on the Web. HTML's main usefulness is the ability to link text and/or an image to another document or section of a document. A browser highlights the identified text or image with color and/or underlines to indicate that it is a hypertext link. The hypertext-related tag is the anchor <A>. To provide an anchor one starts with <A (include space after A), specifies the document linked to by HREF= “filename” followed by closing right angle bracket (>), enters the text that will serve as the hypertext link in the current document, and enters the ending anchor tag </A>. In the example below, Maine is the hyperlink to the document Mainestats.html.

[0020] (anchor start tag symbol)HREF=“Mainestats.html”>Maine(ending anchor tag symbol).

[0021] One can link to documents in other directories by specifying the relative path from the current document to the linked document. A link to a file NYstats.html located in subdirectory Atlantic States would be:

[0022] (anchor start tag symbol)HREF=“Atlantic States/NYstats.html”(ending anchor tag).

[0023] The WorldWide Web uses Uniform Resource Locations (URLS) to specify the location of resources on other servers. The URL includes the type of resource (e.g. Web, FTP, WAIS, etc.). The syntax is: scheme: 1/ host domain [:port]/path/filename. There are also links to specific sections, links between sections of different documents, links to specific sections within the current document and a “mailto” link to make it easier for the reader to send mail to a specific person or mail alias.

[0024] Most Web browsers can display inline images next to text that are in X Bitmap (XBM), GIF or JPEG format. An example is: <IMG SRC=“ImageName”> where ImageName is the URL of the image file. If the file is a GIF file then the filename ends with .gif. The <IMG> tags can tell the browser the size of the images it is downloading. The optional HEIGHT and WIDTH attributes tell the size in pixels. You can have the images separated from the text and aligned to the left or right or centered or you can have an image aligned with the text. By default the bottom of an image is aligned with the text. You can align images to the top or center of a paragraph using the ALIGN= attributes TOP and CENTER. Some browsers can not display images. The ALT attribute lets one specify text to be displayed instead of an image. For example: <IMG SRC=“UpArrow.gif”ALT=“up”>. The UpArrow.gif is the picture of an upward pointing window.

[0025] The system 10 includes a microphone 25 for speech input with which the speaker accesses and navigates the pages and documents. The computer would include a browser 18 such as Netscape but in this case the browser 18 would be navigated by voice as taught in co-pending applications of Thrift, et al. Ser. No. 08/419,229 and Hemphill Ser. No. 08/419,226 (U.S. Pat. No. 5,774,628) cited above. A speaker 29amay also be provided and coupled to the computer 11. Computer 11 may also contain a voice synthesizer 29 to synthesize speech output. Also, optionally a keyboard and/or mouse 31 may be coupled to the computer 11 for mouse and keyboard inputs to the system 10. In accordance with one embodiment the speaker (user) navigates the pages on the display provided by the service provider over, for example, the Internet using the browser 18.

[0026] According to the present invention illustrated by FIG. 2, the present application provides a speakable page enhancer 20 program in computer 11 that takes, for example, the HTML pages and transforms them to new HTML′ pages which become speech friendly by making all speakable options explicit.

[0027] In one embodiment of the present invention, the speakable page enhancer 20 takes advantage of text alternative tags (ALT tags) in languages such as Hypertext Markup Language (HTML). For example, if a page contains an image (cont4g.gif) with the words “The Digital Future”, the enhancer 20 extracts the ALT tag from the markup language to support selection of the corresponding hypertext link (digfuture.html) by user uttering the ALT tag phrase. The HTML follows (see FIG. 3):

[0028] (anchor start tag symbol)href=“/corp/docs/digfuture,html”>

[0029] <img src=“/corp/graphics/nav/cont4g.gif”

[0030] alt=“The Digital Future”>

[0031] (anchor ending tag)

[0032] The ALT tag words “The Digital Future” do not appear in the page for browsers that support graphics. The hyperlink grammars for these words are created as described in application Ser. Nos. 08/419,229 of Hemphill et al entitled “Voice Activated Hypermedia System Using grammatical Metadata” filed Apr. 10, 1995 and 08/419,226 (U.S. Pat. No. 5,774,628) of Hemphill entitled “Speaker Independent Dynamic Vocabulary and Grammar in Speech Recognition” cited above and incorporated by reference to be compared with speech input at microphone 25 at recognizer 15. The computer includes a voice browser interface 18a.The voice browser interface utilizes the enhancer to create modified or enhanced pages and directs the browser 18 to display the results. The recognizer accesses the acoustic models from memory 17 and phonetic pronunciations from disk drive 27.

[0033] This approach also applies to client side image maps (graphical images divided into rectangular regions) that can also include ALT tags for the individual areas.

[0034] Unfortunately, pages can include graphical images with the following problems:

[0035] Missing ALT tag

[0036] the text represented by pixels in the graphical image does not agree with ALT tag text

[0037] the image contains no text (user can only guess what to say)

[0038] To overcome these problems, the enhancer 20 transforms the original hypertext page to create a new one that makes all speakable options explicit. Depending on user preferences, such a transformation might happen automatically when the browser originally presents the page or automatically at the user's request (for example, after the user says “What can I say?”). This transformation parses the markup language specification (for example, HTML) so it will work with any page conforming to that specification.

[0039] The transformation in the enhancer 20 to make speakable options explicit involves the following steps:

[0040] Input original hypertext page (Step 101 in FIG. 4).

[0041] Parse the page to extract a possible BASE tag reference and client side map (MAP tag) definitions (Step 102). To do the parsing one may use LEX or Lexical Analyzer (found in UNIX systems) for tokenization and YACC (Yet Another Compiler Compiler) also on UNIX systems which takes the tokens and applies the rules.

[0042] Retain any BASE tag for relative references or, if missing, create one using the original page reference. (Step 103)

[0043] For each anchor (A tag) containing a page reference (HREF) but without link text, use the ALT tag text as the link text. (Step 104) In the case of a missing ALT tag, create unique link text as follows:

[0044] For a simple image, use link text such as “Unnamed Image I”, where I is a counter of the number of unnamed images so far in the document. (Step 105)

[0045] For an area (AREA tag), use link text such as “Unnamed Area A, where A is a counter of the number of unnamed areas so far in the document. (Step 106) In this case, also enclose a unique suffix of the area's link reference to aid in spatially aligning the newly created link with the graphical image. (Areas are not necessarily defined in the order that they appear in the graphical image.)

[0046] Output transformed hypertext page. (Step 107)

[0047] This approach applies to HTML and any other structured hypertext markup language. We have provided HTML tags as examples above to improve clarity of the discussion.

[0048] We add the extra markup language so that we cause as little reformatting of the page as possible. In other words, the output should look close to the input, but with the extra information added to aid in voice navigation.

[0049] This approach generalized across framed documents where the image counter I and area counter A are maintained while recursively applying the transformation to subframes. In this case, link references (HREFs) in parent frames are retargeted to the corresponding transformations for the subframes.

[0050] This approach can also eliminate ambiguity within the page. A page may contain several links with the same link texts (for example, “Click Here”), but that lead to different places. In such a case, we can introduce a counter for each repeated link and transform the page to include distinct numbers for each ambiguous reference (for example, “Click Here (3)”). Utterances may then include the numbers to disambiguate the spatial ambiguity.

[0051] After creation of the transformed page, we can talk to the resulting page as we normally would using a capable voice-enabled browser.

[0052] In the simplest case, the transformation simply exposes the ALT tag to the user. The input (see FIG. 3)

[0053] <a href=“/corp/docs/companyinfo.html”>

[0054] <img src=“/corp/graphics/nav/contig.gif” alt=“Company Info”>

[0055] <a>

[0056] becomes(see FIG. 5)

[0057] <a href=“/corp/docs/companyinfo.html”>

[0058] <img src=“/corp/graphics/nav/contig.gif”alt=“Company Info”>

[0059] </a>

[0060] <A HREF=“/corp/docs/companyinfo.html”>Company Info</A><BR>

[0061] This example also illustrates the case where the text in the graphical image (“Company Info/Investor Relations”) fails to match the ALT tag text. Saying the text in the graphical image results in a rejection since the recognizer has no clue about what the graphical image says. Adding the anchor (A tag) using the ALT tag text as shown above on line 4 adds the “Company Info” link that allows the user to proceed by voice. The recognizer 15 will recognize “Company Info” and the viewer is proceed by voice. The recognizer 15 will recognize “Company Info” and the viewer is given the exact words to speak. The words are placed to the right of the graphic or in some way related to in the page so the rendering of browser presents it for use. It could also be flashed on the graphic or within the graphic. The <BR> provides the break to make the space separation as shown in FIG. 5.

[0062] In the next case, the image definition does not include an ALT tag so we add an anchor (A tag) for the user to speak (see FIG. 6, “VISA” image):

[0063] <a href=“http://shopguide.yahoo.com”>

[0064] <img src=“http://us.yimg.com/adv/visa/sm.gif”>

[0065] </a>

[0066] <A HREF=“http://shopguide.yahoo.com”>Unnamed Image 1</A><BR>

[0067] In the case of area tags, we must also create some linkage between the occurrence of the created link text and the original graphical image (the area tags do not necessarily come in the proper order). The following example illustrates this (see FIG. 6, top set of images):

[0068] <a href=“/bin/top3”>

[0069] <img usemap=“#top3” ismap

[0070] src=“http://us.yimg.com/images/main3.1.gif”>

[0071] </a>

[0072] <—The following map may appear anywhere in the document—>

[0073] <map name=“top3”>

[0074] <area shape=rect coords=“0,0,63,58”

[0075] href=“/homex/?http://www.yahoo.com/new/”>

[0076] <area shape=rect coords=“63,0,118,58”

[0077] href=“homex/?http://www.yahoo-com/Entertainment/Cool_Links/>

[0078] <area shape=rect coords=“340,0,396,58”

[0079] href=“/homex/?http://www.yahoo.com/headlines/”>

[0080] <area shape=rect coords=“396,0,459,58”

[0081] href=“/homex/?http://www.yahoo.com/docs/family/more.html”>

[0082] </map>

[0083] becomes (see FIG. 4)

[0084] <a href=“/bin/top3”>

[0085] <img usemap=“#top3” ismap

[0086] src=“http://us.yimg.com/images/main3.1.gif”>

[0087] </a>

[0088] <BR CLEAR=ALL>

[0089] <A HREF=“/homex/?http://www.yahoo com/new/”>

[0090] Unnamed Area 1(new)</A><BR>

[0091] <A HREF=“/homex/?http://www.yahoo.com/Entertainment/Cool_Links/”>

[0092] Unnamed Area 2 (Cool_Links)</A><BR>

[0093] <A HREF=“/homex/?http://www.yahoo.com/headlines/”>

[0094] Unnamed Area 3 (headlines)</A><BR>

[0095] <A HREF=“homes/?http://www.yahoo/com/docs/family/more.html”>

[0096] Unnamed Area 4 (more.html)</A><BR>

[0097] <—Map omitted for brevity—>

[0098] The page transformation approach assumes that we have no control over the display of the browser. If, however, we are given information about the location of graphical images and links on the computer's display, then we can use an alternative presentation.

[0099] Given a page as input and information about the graphical location of elements of the page, we proceed as described above for the page transformation transformed page overlaying the needed speech information in the appropriate location on the screen.

[0100] This approach has the advantage of minimal disruption to the original page rendering on the display. It can be selected as an automatic default option or triggered at the user's request with a phrase such as “What can I say?”. This is illustrated in FIG. 8 by the boxes “Company Info”, “Product/Services”, etc. This is also illustrated for areas and images in FIG. 9 by the boxes ”Unnamed area 1 (new)”, “Unnamed area 2 (cool links)”, etc. and “Unnamed Image 1”.

[0101] The original HTML may be made up of a set of frames. The transformation involves keeping track of the frames and a recursive process. The transformation of the original HTML with context to a filtered HTML includes filtered versions for any frame we find and retargeted sources pointing to filtered versions of the HTML for the frames. The following processes for Transform, Recursive Process, Filter, Parse 1 and Parse 2 achieve this.

[0102] TRANSFORM: Input: URLO (fully qualified URL), FILTER_FILEO (name of a file) Output: FILTER_FILEO (contains modified HTML to expose speakable items, contains links to FRAME_FILTER_FILEi for any links to frames)

[0103] GET_HTML:

[0104] GET_HTML:

[0105] With input URLO, produce output HTMLO

[0106] PROCESS:

[0107] With input URLO, HTMLO, FILTER_FILEO, call FILTER to produce output CONTEXTO, FILTER_FILEO (contents)

[0108] Call RECURSIVE_PROCESS with CONTEXTO, URLO, CONTEXTO

[0109] RECURSIVE_PROCESS: Input: CONTEXT (for FRAME_LIST), URL, CONTEXTO (for indices) Output: Set of files FRAME_FILTER_FILEi for each FRAME_URLi, FRAME_FILEi pair in from FRAME_LIST in CONTEXT fully qualify FRAME_URLi with respect to PAGE_BASE in CONTEXT or URL otherwise

[0110] GET_HTML:

[0111] With input FRAME_URLi, produce output FRAME_HTMLi

[0112] PROCESS:

[0113] With input FRAME_URLi, FRAME_HTMLi, FRAME_FILTER_FILEi, CONTEXTO call FILTER to produce output FRAME_CONTEXTi, FRAME_FILTER_FILEi (contents)

[0114] Call RECURSIVE_PROCESS with FRAME_CONTEXTi, FRAME_URLi, CONTEXTO

[0115] FILTER: Input: URL, HTML, FILTER_FILE, (optional) CONTEXTO Output: CONTEXT, FILTER_FILE (contents)

[0116] Create a CONTEXTO if needed with 0 for AREA_INDEX, IMAGE_INDEX, and FRAME_INDEX

[0117] With HTML, CONTEXTO call parsel to produce MAP_LIST, PAGE_BASE

[0118] If no PAGE_BASE, use URL as PAGE_BASE

[0119] With HTML, PAGE_BASE, MAP_LIST, FILTER_FILE, CONTEXTO call parse2 to produce CONTEXT, FILTER_FILE (contents)

[0120] If CONTEXTO created above, copy AREA_INDEX, IMAGE_INDEX, and FRAME_INDEX to CONTEXT.

[0121] parsel: Input: HTML, CONTEXTO Output: MAP_LIST, PAGE_BASE MAP_LIST is initially empty for each tag in HTML

[0122] If we find a MAP tag,

[0123] make AREA_LIST consisting of the set of HREF, ALT, and TARGET tags for each AREA tag

[0124] if no ALT tag, create one such as “unnamed area AREA_INDEX (HREF_SUFFIX)” where AREA_INDEX comes from CONTEXTO and is then incremented; HREF_SUFFIX consists of an interesting suffix of the HREF in the AREA tag

[0125] add the map name with the corresponding AREA_LIST to MAP_LIST

[0126] If we find a BASE tag, return the HREF as the PAGE_BASE

[0127] parse2: Input: HTML, PAGE_BASE, MAP_LIST, FILTER_FILE, CONTEXTO Output: CONTEXT, FILTER_FILE (contents) FRAME_LIST in CONTEXT is initially empty Set PAGE_BASE for CONTEXT for each tag in HTML, print as described below to FILTER_FILE

[0128] End of HEAD tag, print end of HEAD tag followed by

[0129] <BASE HREF=“PAGE_BASE”>

[0130] If A tag with HREF tag, ALT tag and an IMG (image) link (but no text link), print the following after printing the current A tag:

[0131] <A HREF=“HREF tag value”>ALT tag value</A>

[0132] If A tag with HREF tag, no ALT tag and an IMG (image) link (but no text link), print the following after printing the current A tag:

[0133] <A HREF=“HREF tag value”>Unnamed image IMAGE_INDEX</A>

[0134] where IMAGE_INDEX comes from CONTEXTO and is incremented after.

[0135] If MAP tag, print the MAP tag and all values, find the AREA_LIST corresponding to the MAP name and for each MEMBER of AREA_LIST print (TARGET optional)

[0136] <A HREF=“HREF of MEMBER” TARGET=“TARGET of MEMBER”>ALT text of MEMBER</A>

[0137] If FRAME tag

[0138] Create FILTER_FILE_NEW consisting of FILTER_FILE and FRAME_INDEX from CONTEXTO and increment FRAME_INDEX in CONTEXTO

[0139] Print the FRAME tag, but replace the value of SRC with FILTER_FILE_NEW

[0140] Add the original URL from the SRC tag and FITLER_FILE_NEW to the FRAME_LIST in CONTEXT

[0141] Otherwise, print the tag and arguments as normal.

[0142] For the italicized phrases the values for the phrases should be used.

[0143] While the above process is described in connection with a display, the system can also be used, for example, with a telephone system where in place of the display 13 the presentation is via a speech synthesizer 29 and a speaker 29aindicating a link and the markup language is HDML and the enhancer 20 generates and presents via the speech synthesizer 29 and speaker 29aspeech activation link queries in explicit locations with respect to the synthesized audio output context from the speaker 29a.

[0144] Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.