Web mining to build a landmark database and applications thereof

This invention relates to building a landmark database from web data. In one embodiment, a computer-implemented method builds a landmark database. Web data including a web page is received from one or more websites via one or more networks. The web data is interpreted using at least one processor to determine landmark data describing a landmark. At least a portion of the landmark data identifies a landmark. Finally, a visual model is generated using the landmark data. A computing device is able to recognize the landmark in an image based on the visual model.

BACKGROUND

1. Field of the Invention

This invention generally relates to data mining.

2. Background Art

Landmarks can include easily recognizable, well-known places and buildings, such as, for example, monuments, churches, historical sites, and seats of government. For tourists, visiting landmarks may be important parts of their tours. For this reason, tourists often take photographs or videos of landmarks. Many tourists share their photographs over the Internet through photo-sharing websites, such as a PICASAWEB site.

Automatically recognizing landmarks in images and videos is useful for several reasons. First, by capturing the visual characteristics of landmarks, a landmark recognition engine may identify clean, unobscured landmark images. The clean landmark images may be used in virtual tourism to simulate a tour for a user. Second, a landmark recognition engine may be used to geolocate media and to generate a description of media content. Third, a landmark recognition engine may be used to catalogue media by landmark. When media are catalogued by landmark, they may be used, for example, to provide tour guide recommendations.

To recognize a landmark, a landmark recognition engine correlates an image of a landmark with known images of the landmark. To make the correlation, the landmark recognition engine needs a visual model based on or comprised of known images of the landmark. Thus, a landmark recognition engine relies on a landmark database with a listing of landmarks and corresponding visual models to recognize landmarks.

At present, efforts to automatically generate a landmark database have used data from photo-sharing websites. While this approach has advantages, the resulting landmark database tends to be biased to the interests of a particular user group.

Systems and methods are needed that build a large, comprehensive landmark database from a broader range of publicly available photos.

BRIEF SUMMARY

This invention relates to building a landmark database from web data. In one embodiment, a computer-implemented method builds a landmark database. Web data including a web page is received from one or more websites via one or more networks. The web data is interpreted using at least one processor to determine landmark data describing a landmark. At least a portion of the landmark data identifies a landmark. Finally, a visual model is generated using images determined based on the landmark data. A computing device is able to recognize the landmark in an image based on the visual model.

In another embodiment, a system builds a landmark database. The system includes a web data retriever module configured to receive web data including a web page from one or more websites via one or more networks. A web data interpreter module is configured to interpret the web data to determine landmark data describing a landmark. At least a portion of the landmark data identifies a landmark. Finally, a visual model generator is configured to generate a visual model using images determined based on the landmark data. A computing device is able to recognize the landmark in an image based on the visual model.

By mining web data, embodiments of the present invention can build a large, comprehensive landmark database that may be used to recognize landmarks.

The drawing in which an element first appears is typically indicated by the leftmost digit or digits in the corresponding reference number. In the drawings, like reference numbers may indicate identical or functionally similar elements.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of the present invention mine landmark information from the web to build a landmark database. The landmark database may be used to recognize landmarks in images. By using the vast amount of data available on the web, embodiments may build a landmark database that is large and comprehensive. Accordingly, a landmark recognition engine may recognize a large number of landmarks using the landmark database.

FIG. 1is a diagram illustrating a system100for mining web data to build a landmark database according to an embodiment of the present invention. System100includes a processing module110that builds a landmark database108based on data from websites102retrieved via one or more networks180, such as the Internet. To build landmark database108, processing module110includes a web data extractor module120and visual model generator module130.

In general, system100operates as follows. Web extractor module120retrieves web data from one or more websites102. Web extractor module120interprets the web data to determine landmark information. The landmark information may include a list of landmark names. Using the landmark names, geocoding module140determines a location for each landmark. Also using the landmark names, visual model generator130finds images of each landmark and constructs a visual model of the landmark. The visual model may be used, for example, to recognize a landmark. Finally, the landmark data, landmark locations and visual model are stored in landmark database108. Each of the components are discussed in greater detail below.

In the illustrated embodiment, web extractor module120includes a web data retriever module122configured to retrieve web data from one or more websites102. Web data retriever module122is configured to know where on the Internet to find websites102. For example, web data retriever module122may be configured to navigate through a travel site such as a wikitravel.com site. To navigate through the travel site, web data retriever module122may know the Uniform Resource Locator (URL) patterns to access web data (such as web pages) of the site that describe landmarks. Alternatively, web data retriever module122may know a URL of one or more pages that link to pages that describe landmarks. Either way, web data retriever module122is configured to know or determine the location of web data that includes information about landmarks. An example operation of web data retriever module122is described in detail below.

In other embodiments, web data interpreter module124may extract the landmark data using computer vision techniques instead of or in addition to text parsing. An example operation of web extractor module120is described in detail in later sections with respect toFIG. 3.

The accuracy of the landmark data determined by web data interpreter module124depends on how consistently the web data is formatted. Many travel sites, such as a wikitravel.com site, are formatted fairly consistently. Still, users making contributions to a travel site, for example through a wiki, may raise the possibility that some of the web data is formatted inconsistently.

To deal with inconsistent formatting, error checker module128may apply one or error checking rules to improve the quality of the landmark data. The error checking rules may be heuristics used to determine whether a name is likely a real landmark name as opposed to other text captured by accident. The error checking rules may include checking to see that a landmark name is not too long or that a majority of the words in a landmark name start with a capital letter. If error checker module128determines that a landmark data is inaccurate, then error checker module128may remove the landmark data from the list of landmarks sent onto visual module generator module130and geocoding module140.

In one embodiment, the landmark data parsed from the web data may include a geolocation (e.g. latitude/longitude) of the landmark. In that embodiment, no further geocoding step is necessary. In other cases, geocoding module140may determine a location of the landmark.

Geocoding module140determines landmark locations. In an embodiment, geocoding module140may receive a list of landmarks with each landmark described by some landmark data. The landmark data may include a landmark name and a city, country or continent where the landmark is located. Geocoding module140determines a specific location (such as a latitude/longitude) of the landmark. To determine the location, geocoding module140may access a geocoding service106. Geocoding module140may send a request to geocoding service106. In response, geocoding service106may look up a latitude/longitude location and send the location back to geocoding service106. The request from geocoding service106may include a landmark name and city.

In another embodiment, the landmark data parsed from the web data may include a street address. In that embodiment, the request sent to geocoding service106may include the street address of the landmark. In response to the request, geocoding service106looks up the location of the address and sends the location of the address back to geocoding module140. In some cases, only a partial street address, such as the city name, may be available. In that case, geocoding module140may use the available information to estimate the location of the landmark.

In a third embodiment, geocoding module140may determine a landmark location by correlating an image of a landmark with one or more images with known locations. The landmark image may be determined using an image search as is discussed below. The images with known locations may be part of an image database, photo-sharing website, or a street view image database. The images may have location information embedded, for example, by a digital camera in an Extendable Image File (EXIF) header. The images may be correlated with the landmark image using an image matching algorithm. When geocoding module140finds a match, the location of the matching image is adopted as the landmark location, or an aggregation of the combination of locations from the images is adopted as the landmark location.

Either serially or in parallel with geocoding module140determining the location of the landmark, visual model generator module130generates a visual model of the landmark. To generate the visual model, visual model generator module130first determines images of the landmark based on the landmark data with landmark image module132. Then, visual model generator module130constructs the visual model with visual clustering module138.

Landmark image module132determines images of the landmark based on landmark data. Landmark image module132may request an image search with an image retriever module134. Image retriever module134may generate a search query based on landmark data. Image retriever module134may send the search query to an image search service104. Image search service104may be any image search engine, such as a GOOGLE Image Search engine. In response to the search query, image search service104may send back a set of results.

Image retriever module134may generate the search query to maximize the effectiveness and accuracy of image search service104. To generate the query, image retriever module134may concatenate a landmark name and its city. For example if the landmark name is “Eiffel Tower” and its city is “Paris”, the search query may be “Eiffel Tower Paris”.

Some image search engines, such as the GOOGLE Image Search engine, take individual words in the query as an AND relation. In those embodiments, image retriever module134may use additional rules to ensure better image search results are obtained. For example, image retriever module134may not add country in the query, as adding the country may make the returned images more relevant to the country than to the landmark. If the landmark name consists of less than four words, image search engines may put quotes around the landmark name to ensure that image search service104searches for the an exact phrase. If the landmark consists of four or more words, image retriever module134may not use quotes, as the AND relation between words in the long landmark name may make the query sufficiently distinctive.

Image retriever module134sends a search query and receives a set of search results from image search service104. The search results may have a large number of false positives. To determine a visual model from the image results, the images may undergo visual clustering by a visual clustering module138and pruning by an image checker136. In one embodiment, the visual clustering may occur prior to the pruning. In another embodiment, the pruning may occur prior to the visual clustering.

The images that are useful for constructing a visual model are generally photos of a large portion of the landmark without too many other objects. However, the search results may also include images, for example, of maps, manuals, and logos. Some results may show the landmark obstructed by faces or include large amounts of blank spaces. To deal with this, landmark image module132may use an image checker module136to filter out some of the images. Image checker module136may include one or more classifiers trained to detect undesirable image types.

One possible classifier is trained to distinguish a photographic vs. non-photographic image. The classifier may be trained using an Adaboost algorithm with low-level visual features such as those extracted with a color histogram and hough transform. Also, a face detector may be used to filter out photos where a landmark is obstructed by one or more faces. Image checker module136may use any face detector or image classifier as is known to those of skill in the art of computer vision.

In addition to filtering out undesirable image types, a visual clustering module138may be used to identify similar images in the result set. Given that a large number of the remaining images in the result set are of the landmark, identifying these similar images further helps to narrow the result set. Any visual clustering technique known to those of skill in the art may be used. One such visual clustering technique is discussed in U.S. patent application Ser. No. 12/119,359, “Automatic Discovery of Popular Landmarks”, which is incorporated by reference herein in its entirety. Visual clustering uses object instance recognition techniques that are robust to variations in image capturing conditions, illuminations, scale, translation, clutter and occlusion and, in part, affine transformation. Based on the object recognition, clusters of similar images are formed. The resulting dense clusters of images are highly probable to contain true landmark photos that depict the landmarks from similar perspectives.

The landmark images selected by visual clustering module138may be saved as a visual model in landmark database108along with landmark data identifying the landmark (such as a landmark name). A computing device may use the images to recognize whether a landmark exists in an image, including a photograph or a frame of a video. To recognize whether a landmark exists in an image, a computing device may use visual clustering to determine that an image is similar to the images including the landmark.

In an alternative embodiment, visual model generator module130may use the landmark images to generate a general visual model of the landmark. In that embodiment, the visual model is saved to landmark database108. A computing device may use the visual model to recognize the landmark in images. Any modeling or recognition technique may be used as is known to those of skill in the art.

In one example, the modules of system100may be software modules that run on one or more computing devices. A computing device may include a computer, workstation, distributed computing system, embedded system, stand-alone electronic device, networked device, mobile device, rack server, television, set top box, mobile computing device or other type of computer system. A computing device may include a processor and a memory. The memory may include a primary and a secondary storage device. The computing device may have input and output devices including a user input device and a display device. The computing device may also have a network interface that enables the computing device to communicate over a network.

Image search service104and geocoding service106may be any types of service, including, but not limited to, a web service running on a web server. The web server may be a software component running on a computing device. Similarly, websites102may be any source of web data. In an example, websites102may be web servers addressable over one or more networks, such as the Internet. Again, the web servers may be a software component running on a computing device.

FIG. 2is a flowchart illustrating a method200for mining web data to build a landmark database according to an embodiment of the present invention. Method200may be used in operation of system100inFIG. 1. Method200is described with respect to illustrative examples inFIGS. 3-5. These examples are provided for clarity, and method200should not be limited thereto.

Method200begins by retrieving web data from one or more websites at step202. As discussed above, web data may be retrieved according to the structure of the websites. One example website, a wikitravel.com site, is organized according to a geographical hierarchy. A main page of the wikitravel.com site may include links to pages for each continent. Each continent page includes links to pages for countries in the continent. Each country page includes links to pages for cities in the country. Finally, each city page includes information about landmarks located within the city. The term “city” used in reference to the wikitravel.com site is a flexible concept that includes both an urban area and a larger metropolitan area with suburbs and satellite cities. With this hierarchy, web data may be retrieved recursively from the wikitravel.com site.

In one example operation of step202, a main page of wikitravel may be retrieved. The main page may include a list of links to continent pages that includes a link to a page for Asia. Using the link, the page for Asia is retrieved. The page for Asia may include a list of links to country pages including a link to a page for Japan. Using the link, the page for Japan is retrieved. The page for Japan may include a list of links to city pages including a link to a page for Kyoto. The page for Kyoto is retrieved as illustrated with a page300inFIG. 3. Page300for Kyoto includes information about landmarks located within Kyoto.

After retrieving the web data at step202, the web data is interpreted to determine landmark data at step204. As mentioned earlier, the web data may be one or more web pages formatted in HTML. In the example of a wikitravel article, the HTML document may have a tree structure ed, where the interior nodes may correspond to tagged elements and the leaf nodes store text. A travel guide article may be modeled as d=ed(i, j), td(i, j)}, where ed(i, j) is the jth node at level i of tree edand td(i, j) is the text stored at node ed(i, j). To extract the landmark names, the text of the leaf nodes, td(ileaf, j) is determined to be either landmark or non-landmark names.

To determine whether the text of the leaf nodes is a landmark name, heuristic rules may be used. In the example of a wikitravel.com page, three heuristic rules may be used. If all of the following three conditions are true, then the text may be a candidate for a landmark name. Otherwise, the text may not be a landmark name. First, ed(ileaf, j) must be within a section entitled “See” or “To See” in the HTML document. Second, ed(ileaf, j) must be a child of a node indicating “bullet list” format. Third, ed(lleaf, j) must indicate that the text is in a bold format. An example is illustrated in page300inFIG. 3.

Page300is an HTML document that has a tree structure of HTML elements. Among the leaf elements in the tree, text304and308satisfy the three conditions above. Text304and308are within a section entitled “See” as illustrated by a section header302. Text304and308are child elements of bullets as illustrated by bullets306and310. Finally, text304and308are formatted in boldface. Thus, text304and308are candidates for landmark names.

As mentioned earlier, the quality of the candidate landmark names parsed from the web data depends on the regularity of the data structure. Some text may be incorrectly parsed from the web data. To filter out data incorrectly parsed, one or more error checking rules are applied at step206. As mentioned earlier, the error checking rules may include checking to see if a landmark name is too long or if most of its words are not capitalized. Using these rules some of the candidate landmark names may be rejected. The result is an accurate list of landmark names. Also some of the landmark location information may be recorded as well, such as the city, country or continent where the landmark is located. In the example with a wikitravel.com site, approximately 7000 landmarks may be included in the list.

Using the landmark data, landmark images are retrieved at step208. Landmark images may be retrieved by sending a request to an image search service. The request may include a search query generated using landmark data as described above. In response to the request, the image search service returns results. Example results are illustrated in a page400inFIG. 4.

The result may include some images that are not pictures of the landmark. For example, some images may be maps, logos, etc. At step210, image checking rules may be applied to prune out these false positive search hits. As described above, the image checking rules may include applying image classifiers trained to detect undesirable types of images. In one embodiment, the pruning of step210may occur subsequent to the visual clustering in step212.

Page400shows an example result set returned by an image search engine. Among the results are maps420,422, and424. Map images, such as maps420,422, and424, may not helpful in developing a visual model able to recognize landmark images. For this reason, a classifier trained to detect maps may be used to detect these images. When maps420,422, and424are detected, they may not be removed from the result set.

After some of the false positives are filtered out, visual clustering may be used to generate a visual model at step212. Visual clustering has the ability to identify similar images. In page400, visual clustering may identify images402,404,406,408,410,412,414, and416as being similar. In this way a pool of images of the landmark are identified to use as a visual model. Further, visual clustering may be used to recognize the landmark in other images. In this way, visual clustering narrows the images from the result set and may be used to recognize the landmark in other images.

At step214, a geolocation (e.g., latitude and longitude) of the landmark is determined. As discussed above, the geolocation may be determined by requesting a geolocation from a geocoding service. As mentioned earlier, in the example where landmarks are extracted from a wikitravel site, about 7000 different landmarks, along with city and country information for each landmark, may be determined. In an example, a GOOGLE geocoding service may be used to determine the geolocations. In an example, of the about 7000 different landmarks extracted from wikitravel.com, about 2000 may have geolocations available from the GOOGLE geocoding service. The approximately 2000 geolocations are illustrated in a diagram500inFIG. 5.

FIG. 5shows diagram500with a map of the geocoded locations of landmarks indicated by dots that may be identified in an example embodiment of the present invention. The map shows that the list of landmarks is large and comprehensive. Also, the landmarks identified are widely distributed across the globe as opposed narrowly tailored to the interests of a particular user group.

Examples have been provided with respect to a wikitravel.com site and GOOGLE image search and geocoding services. These examples are illustrative and are not meant to limit the present invention. Embodiments of the present invention may be used to extract landmarks from a wide variety of websites.