Abstract:
In an example embodiment, a request that includes a first image is received. A second image and a description are accessed from an item listing. An item identifier that corresponds to the second image is parsed from the description. A first edge in the first image and a second edge in a second image are detected. A match between the first image and the second image is determined based on the detection. The first image is associated with the item identifier. item information corresponding to the item identifier is accessed from web pages. The item information is then transmitted.

Description:
CROSS-REFERENCES TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of and claims the benefit of priority under to U.S. patent application Ser. No. 12/371,882, filed on Feb. 16, 2009, which claims the benefit of priority under to U.S. Provisional Patent Application Ser. No. 61/106,916, filed Oct. 20, 2008, and U.S. Provisional Patent Application Ser. No. 61/033,940, filed Mar. 5, 2008, the benefit of priority of each of which is claimed hereby, and each of which are incorporated by reference herein in their entirety. 
     
    
     FIELD 
       [0002]    The present disclosure relates generally to information retrieval. In an example embodiment, the disclosure relates to identification of items depicted in images. 
       BACKGROUND 
       [0003]    Online shopping and auction websites provide a number of publishing, listing, and price-setting mechanisms whereby a seller may list or publish information concerning items for sale. A buyer can express interest in or indicate a desire to purchase such items by, for example, submitting a query to the website for use in a search of the requested items. 
         [0004]    The accurate matching of a query to relevant items is currently a major challenge in the field of information retrieval, An example of such a challenge is that item descriptions tend to be short and are uniquely defined by the sellers. Buyers seeking to purchase the items might use a different vocabulary from the vocabulary used by the sellers to describe the items. As an example, an item identified in the title as a “garnet” does not match a query “January birthstone” submitted by a buyer, although garnet is known as the birthstone for January. As a result, online shopping and auction websites that use a conventional search engine to locate items may not effectively connect the buyers to the sellers and vice versa. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0005]    The present disclosure is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements and in which: 
           [0006]      FIG. 1  is a user interface diagram showing an image that depicts an item, in accordance with an embodiment, that may be submitted for identification; 
           [0007]      FIG. 2  is a user interface diagram showing a listing of items, in accordance with an embodiment, that match the item depicted in the image of  FIG. 1 ; 
           [0008]      FIG. 3  is a diagram depicting a system, in accordance with an illustrative embodiment, for identifying items depicted in images; 
           [0009]      FIG. 4  is a block diagram depicting an item recognition module, in accordance with an illustrative embodiment, included in a processing system that is configured to identify items depicted in images; 
           [0010]      FIG. 5  is a block diagram depicting modules, in accordance with an embodiment, included in the image recognition module; 
           [0011]      FIG. 6  is a flow diagram depicting a general overview of a method, in accordance with an embodiment, for identifying an item depicted in an image; 
           [0012]      FIG. 7  is a flow diagram depicting a detailed method, in accordance with some embodiments, for identifying an item depicted in an image; 
           [0013]      FIGS. 8 and 9  are diagrams depicting a method of identifying an item depicted in an image based on comparisons with other images, in accordance with an illustrative embodiment; and 
           [0014]      FIG. 10  is a block diagram depicting a machine in the example form of a processing system within which a set of instructions, for causing the machine to perform any one or more of the methodologies discussed herein, may be executed. 
       
    
    
     DETAILED DESCRIPTION 
       [0015]    The description that follows includes illustrative systems, methods, techniques, instruction sequences, and computing machine program products that embody illustrative embodiments of the present invention. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide an understanding of various embodiments of the inventive subject matter. It will be evident, however, to those skilled in the art that embodiments of the inventive subject matter may be practiced without these specific details. In general, well-known instruction instances, protocols, structures and techniques have not been shown in detail. 
         [0016]    The embodiments described herein provide techniques for identifying items depicted in images. Images depicting a variety of items are stored in a repository of, for example, a network-based publication system (e.g., an online shopping website and an online auction website). Users may submit these images for inclusion in item postings, advertisements, or other publications in the network-based publication system. As explained in more detail below, an item depicted in an image may be identified by matching the image with user submitted images stored in the repository. In some embodiments, as explained in more detail below, the match may be based on a comparison of the color histograms of the images. 
         [0017]      FIG. 1  is a user interface diagram showing an image  102  that depicts an item, in accordance with an embodiment, that may be submitted for identification. As depicted, the image  102  is of a painting, and a user can shop for this painting by submitting this image  102  to, for example, an online shopping website. This online shopping website can identify the particular painting depicted in the image  102  and search its inventory for the identified painting. As depicted in  FIG. 2 , the online shopping website found several other paintings that match the painting depicted in the image  102  and lists these paintings for sale. As a result, rather than submitting the name or description of the painting depicted in the image  102 , a user can simply submit the image  102  of the painting to, for example, the online shopping website for identification. The submission of the image  102  of the painting may therefore be faster because a user can effectively submit the painting for sale with just “one click” of a button instead of typing in a name or description of the painting. Furthermore, a user can locate the painting depicted in the image without even knowing the name of the painting. The submission process can also be more accurate because, for example, it does not depend on the user&#39;s knowledge of the painting&#39;s name, which can be erroneous. 
         [0018]    It should be noted that the submission of an image of an item (e.g., image  102  of the painting) for identification may be used in a variety of different applications. As used herein, an “item” refers to any tangible or intangible thing and/or something that has a distinct, separate existence from other things (e.g., goods, services, electronic files, web pages, electronic documents, and land). For example, in addition to a sale of the item, a user may submit an image of the item to a price comparison service, in accordance with an embodiment of the invention. This price comparison service can identify the item depicted in the image and deliver shopping comparison results associated with the item. In another embodiment, a user can submit an image to a search engine (e.g., Internet search engine or website search engine) and the search engine can then retrieve websites or other information associated with the item depicted in the image. In yet another embodiment, a user can submit the image to an online auction website that can identify the item depicted in the image and return a template associated with the item to the user such that the user may then modify the template, if necessary, for use in auctioning the item on the online auction website. A template is an electronic file or document with descriptions and layout information. For example, a template may be a document with a predesigned, customized format and structure, such as a fax template, a letter template, or sale template, which can be readily filled in with information. 
         [0019]      FIG. 3  is a diagram depicting a system  300 , in accordance with an illustrative embodiment, for identifying items depicted in images. As depicted, the system  300  includes client processing systems (e.g., personal computer  304  and mobile phone  306 ), a server  310  hosting a variety of services, and another server  312  hosting an item recognition module  314 , which are all interconnected by way of a computer network  302 . The computer network  302  is a collection of interconnected processing systems that communicate utilizing wired or wireless mediums. Examples of computer networks, such as the computer network  302 , include Local Area Networks (LANs) and/or Wide-Area Networks (WANs), such as the Internet. 
         [0020]    In the example of  FIG. 3 , a client processing system (e.g., personal computer  304  or mobile phone  306 ) transmits an image of an item  309  to the image recognition module  314 , which is hosted on the server  312 . The image may be captured by a camera built-in the mobile phone  306  or by a digital camera  308 , which is configurable to download its stored images to the personal computer  304 . Alternatively, the user may locate the image through, for example, the Internet or other image repositories. 
         [0021]    The image recognition module  314  accesses the image from the client processing systems and, as explained in more detail below, identifies the item  309  depicted in the image with an item identifier. An “item identifier,” as used herein, refers to a variety of values (e.g., alphanumeric characters and symbols) that establish the identity of or uniquely identify one or more items, such as item  309 . For example, the item identifier can be a name assigned to the item  309 . In another example, the item identifier can be a barcode value (e.g., Universal Product Code (UPC)) assigned to the item  309 . In yet another example, the item identifier can be a title or description assigned to the item  309 . 
         [0022]    In an embodiment, the item recognition module  314  may then transmit the item identifier to a service hosted on the server  310  to locate item data. The “item data,” as used herein, refer to a variety of data regarding one or more items depicted in an image that are posted or associated with the image. Such item data, for example, may be stored with the images or at other locations. Examples of item data include titles included in item listings, descriptions of items included in item listings, locations of the items, prices of the items, quantities of the items, availability of the items, a count of the items, templates associated with the items, and other item data. The type of item data requested by the item recognition module  314  depends on the type of service being accessed. Examples of services include online auction websites, online shopping websites, and Internet search engines (or website search engines). It should be appreciated that the item recognition module  314  may access a variety of different services by way of, for example, a Web-exposed application program interface (API). In an alternate embodiment, the item recognition module  314  may be embodied with the service itself where, for example, the item recognition module  314  may be hosted in the server  310  with the other services. 
         [0023]    The system  300  may also include a global positioning system (not shown) that may be attached to or included in the client processing systems. The client processing systems can transmit the coordinates or location identified by the global positioning system to the services hosted on server  310  and, for example, the services can use the coordinates to locate nearby stores that sell the item  309  depicted in the image. 
         [0024]      FIG. 4  is a block diagram depicting an item recognition module  314 , in accordance with an illustrative embodiment, included in a processing system  402  that is configured to identify items depicted in images. It should be appreciated that the processing system  402  may be deployed in the form of variety of computing devices, such as personal computers, laptop computers, server computers, and other computing devices. For example, the processing system  402  may be the server  310  or  312  or the personal computer  304  depicted in  FIG. 3 . In various embodiments, the processing system  402  may be used to implement computer programs, logic, applications, methods, processes, or other software to identify items depicted in images, as described in more detail below. 
         [0025]    The processing system  402  is configured to execute an operating system  404  that manages the software processes and/or services executing on the processing system  402 . As depicted in  FIG. 4 , these software processes and/or services include the item recognition module  314 . Generally, the item recognition module  314  is configured to identify one or more items depicted in an image. The item recognition module  314  may include a request handler module  410 , an image recognition module  412 , and a hosting module  414 . 
         [0026]    The request handler module  410  is configured to interface with other processing systems, such as the client processing systems  304  and  306  of  FIG. 3 . The interface may include the receipt of messages and data from other processing systems by way of Hypertext Transfer Protocol (or other protocols), and also include transmission of messages and data from the item recognition module  314  to other processing systems by way of Hypertext Transfer Protocol. Referring to  FIG. 4 , another processing system in communication with the item recognition module  314  may convert an image into a byte array and open a remote Hypertext Transfer Protocol (HTTP) request to the item recognition module  314 . The byte array is written to a server socket using, for example, HTTP POST, and a separate HTTP GET request may be sent, including global positioning system coordinates of the processing system, if available. The request handler module  410  receives the byte array and converts it into, for example, a Java image object that is then processed by the image recognition module  412 . 
         [0027]    The image recognition module  412  is configured to identify one or more items depicted in an image by comparing the received image with other images of items to identify a match, which is explained in more detail below. The hosting module  414  is configured to interface with other services, which are discussed above. As an example, the image recognition module  412  may transmit a request to a service by way of the hosting module  414  for item data associated with the identified items. This request may include an item identifier, global positioning coordinates, and other information. In turn, the item recognition module  314  receives the requested item data from the service by way of the hosting module  414 . The request handler module  410  may then parse the item data from the service into, for example, a lightweight eXtensible Markup Language (XML) for mobile devices and may transmit the response back to the processing systems that originally requested the item data regarding the items depicted in the image. 
         [0028]    It should be appreciated that in other embodiments, the processing system  402  may include fewer, more, or different modules apart from those shown in  FIG. 4 . For example, the image recognition module  412  may be further split into an image recognition module and a neural network module, which are explained in more detail below. 
         [0029]      FIG. 5  is a block diagram depicting modules  502 ,  504 ,  506 , and  508 , in accordance with an embodiment, included in the image recognition module  412 . As depicted, the image recognition module  412  includes another request handler module  502 , a harvester module  504 , an image tools module  506 , and a neural network module  508 . In general, this other request handler module  502  is configured to process requests made to the image recognition module  412 . The image tools module  506  is configured to process the images using one or more image processing algorithms, such as an edge detection algorithm, which is described in more detail below. 
         [0030]    Generally, the neural network module  508  is configured to identify one or more items depicted in an image through learning and training. As an example, the neural network module  508  can identify matches between images based on learning algorithms. It should be appreciated that a neural network is a type of computer system that is based generally on the parallel architecture of animal brains and can learn by example. As explained in more detail below, the neural network module  508  gathers representative data and then invokes learning algorithms to learn automatically the structure of the data. A Java Object Oriented Neural Engine is an example of a neural network module  508 . Other examples of neural network modules include Feed Forward Neural Networks, Recursive Neural Networks (e.g., Elman and Jordan), Time Delay Neural Networks, Standard Back-Propagation Neural Networks (e.g., Gradient Descent, on-line, and batch), Resilient Back-Propagation (RPROP) Neural Networks, Kohonen Self-Organizing Maps (with WTA or Gaussian output maps), Principal Component Analysis, and Module Neural Networks. 
         [0031]    The harvester module  504  is configured to request item data from a service by way of, for example, an API. As described in more detail below, the harvester module  504  may then parse the item data to identify item identifiers and associate the item identifiers with an image. 
         [0032]      FIG. 6  is a flow diagram depicting a general overview of a method  600 , in accordance with an embodiment, for identifying an item depicted in an image. In an embodiment, the method  600  may be implemented by the item recognition module  314  and employed in the processing system  402  of  FIG. 4 . As depicted in  FIG. 6 , an image depicting an item is accessed at  602 . This image may be submitted by a user to identify the item depicted in the image. Additionally, one or more other images and their associated item identifiers, which identify the items depicted in these other images, are accessed at  604 . These images and item identifiers may be from user-submitted item postings and are stored in and accessed from a repository of, for example, a network-based publication system. For example, a large number of users place or sell items on an auction website and, when placing or selling these items, the users would submit images and descriptions of the items. All these images and their descriptions, which may be used as item identifiers, may be stored in the repository and are accessible by the item recognition module. 
         [0033]    A variety of image identification techniques may be applied to identify the item depicted in the image. As an example, the identification can be based on identifying a match of the image with one of the other images accessed from the repository. In this embodiment, the image is compared with other images at  606 , and a match of the image with at least one of the other images is identified at  608  based on the comparison. Once a match is identified, the item identifier associated with the matched image is accessed and the submitted image is associated with the item identifier at  610 . Since the item identifier identifies the item depicted in the image, the association effectively results in the identification of the item depicted in the image. 
         [0034]    It should be appreciated that a single image may also include multiple items. Each item may be automatically identified or, to assist in the identification, a user may manually point to or designate an approximate location or region of each item in the image as separate items, and the item recognition module can then focus on each designated location to identify a particular item. As a result, for example, if a user wants to list several items for sale, the user can simply take a single picture of all the items and submit the picture in the form of an image to a listing service. The listing service with the item recognition module may then automatically identify and list all the items in the submitted image for sale. 
         [0035]      FIG. 7  is a flow diagram depicting a detailed method  700 , in accordance with another embodiment, for identifying an item depicted in an image. In the method  700 , a request is received to identify an item depicted in an image at  702 . This request may, for example, be received from a client processing system and includes an image submitted by a user. Additionally, one or more other images and their associated item identifiers are accessed at  704  from, for example, a repository of a network-based publication system. 
         [0036]    In an embodiment, to enhance the accuracy of the subsequent item identification, a variety of different image algorithms can be applied to the images. An example is the application of an edge detection algorithm to the images at  706 , in accordance with an alternative embodiment, to detect edges in the images. An image tool module included in the item recognition module, as discussed above, may apply an edge detection algorithm to detect, draw, enhance, or highlight lines, areas, or points of contrast in the image. An example is the application of a Canny edge detector algorithm to extrapolate contrasts of the images. The contrasts effectively serve to highlight the lines, points, or areas that define the item, and the detection of these lines, points, or areas increases the probability of identifying a match between two or more images. Other examples of image algorithms that may be applied to the images include Marching Squares Algorithm and Haar wavelet. 
         [0037]    The identification of items depicted in the image can be based on identifying a match of the image with at least one of the other images accessed from the repository. In an embodiment, at  708 , the images being compared are converted into color histograms, which are representations of distributions of colors in the images. The color histogram of the image is then compared with the color histograms of the other images at  710  to identify a match. As an example, a neural network module compares the color histograms to generate a statistical analysis of the comparison. The statistical analysis may identify a statistical difference or a statistical similarity between the compared color histograms, and the match is based on the resulting statistical analysis. 
         [0038]    The neural network module may then return a set of statistical analysis and associated item identifiers assigned to each set of comparisons. As an example, item identifiers can be correlated with statistical differences using name value pairs, such as “DVD player: .00040040.” Here, the item identifier with the smallest correlated error may be the best match based, in part, on training data. As discussed previously, the neural network module can learn from training using examples from previous comparisons. As an example, if a match is identified, the image and its item identifier identified from the match may be warehoused or stored with a large group of images for training the neural network module to make the identification of items more accurate. In another example, a user can manually confirm that a particular item as depicted in an image is accurate, and this confirmation may also be used to develop training for the neural network module. 
         [0039]    Once a match is identified, the item identifier associated with the matched image is accessed at  712  and associated with the image being submitted at  714 . In the example above, if the item identifier “DVD player” is associated with the matched image from the repository, then the “MD player” is associated with the image being submitted. It should be appreciated that in addition to the application of the edge detector algorithm and the comparison with other images as discussed above, other image identification processes may also be applied to identify items depicted in the image, in accordance with other embodiments of the invention. 
         [0040]    Still referring to  FIG. 7 , a template associated with the item identifier is accessed at  716 , in accordance with an embodiment of the invention. The template may be a pre-built template stored in a data structure and associated with a particular item or item identifier. For example, this template may already include descriptions and attributes of an associated item. The template is then transmitted at  718  in a response to the request. As an example, the template is included in a response and this response is transmitted back to the client processing system that initially requested the identification. 
         [0041]      FIGS. 8 and 9  are diagrams depicting a method of identifying an item depicted in an image based on comparisons with other images, in accordance with an illustrative embodiment. As depicted in  FIG. 8 , a user takes a picture of a car using his mobile phone and submits this picture, in the form of an image  802  to, for example, a listing service that sells cars. Alternatively, the user may take a video of the car and submit one or more frames from the video to the listing service. 
         [0042]    An item recognition module hosted with the listing service receives a request to identify the car depicted in the image from the processing system (e.g., a mobile phone) used by the user. This item recognition module has the capability to identify the type of car depicted in the image  802  by identifying a match of the image  802  with at least one other image of a car. Before identification, an edge detection algorithm is applied to the image  802  to produce an image  804  that highlights the lines of the car depicted in the image  802 . 
         [0043]    As depicted in  FIG. 9 , a number of other images  851 - 855  of cars and their associated item data are accessed. In this embodiment, the item identifiers associated with the images  851 - 855  are not immediately available and instead, the item identifiers are derived from item data associated with the images  851 - 855 . In an embodiment, the item recognition module accesses the item data associated with one or more images  851 - 855  and then parses the item data to identify one or more item identifiers, which, for example, a user may define as a title or barcode value of an item. 
         [0044]    The image  804  thereafter is compared with one or more images  851 - 855 , which may, for example, be extracted from previous listings of cars. In this example, the image  804  is compared with each image  851 ,  852 ,  853 ,  854 , and  855  and, for example, a statistical difference between each pair of images (e.g.,  804  and  851  or  804  and  852 ) is generated for each comparison. In the example of  FIG. 8 b   , the comparison of the image  804  with the image  852  yields the lowest statistical difference. As a result, a match of the image  804  with the image  852  is identified. 
         [0045]    The item identifier associated with the image  852 , which is identified from a parsing of the item data, is then associated with the image  802 . The item recognition module then transmits the item identifier along with other requested item data (e.g., model and make) in a response to the earlier request back to the processing system used by the user. With a match, the listing service can also automatically place the listing of the car in an appropriate category and then list the car with its image  802  for sale on the website. 
         [0046]      FIG. 10  is a block diagram of a machine in the example form of a processing system  900  within which a set of instructions, for causing the machine to perform any one or more of the methodologies discussed herein, may be executed. In alternative embodiments, the machine operates as a standalone device or may be connected (e.g., networked) to other machines. In a networked deployment, the machine may operate in the capacity of a server or a client machine in server-client network environment, or as a peer machine in a peer-to-peer (or distributed) network environment. Embodiments may also, for example, be deployed by Software-as-a-Service (SaaS), Application Service Provider (ASP), or utility computing providers, in addition to being sold or licensed via traditional channels. 
         [0047]    The machine is capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that machine. Further, while only a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein. 
         [0048]    The example processing system  900  includes a processor  902  (e.g., a central processing unit (CPU), a graphics processing unit (GPU) or both), a main memory  904 , and static memory  906 , which communicate with each other via bus  908 . The processing system  900  may further include video display unit  910  (e.g., a plasma display, a liquid crystal display (LCD) or a cathode ray tube (CRT)). The processing system  900  also includes an alphanumeric input device  912  (e.g., a keyboard), a user interface (UI) navigation device  914  (e.g., a mouse), a disk drive unit  916 , signal generation device  918  (e.g., a speaker), and network interface device  920 . 
         [0049]    The disk drive unit  916  includes machine-readable medium  922  on which is stored one or more sets of instructions and data structures  924  (e.g., software) embodying or utilized by any one or more of the methodologies or functions described herein. The instructions and data structures  924  may also reside, completely or at least partially, within main memory  904  and/or within processor  902  during execution thereof by processing system  900 , main memory  904 , and processor  902  also constituting machine-readable, tangible media. 
         [0050]    The instructions and data structures  924  may further be transmitted or received over network  926  via network interface device  920  utilizing any one of a number of well-known transfer protocols (e.g., HTTP). 
         [0051]    While the invention(s) is (are) described with reference to various implementations and exploitations, it will be understood that these embodiments are illustrative and that the scope of the invention(s) is not limited to them. In general, techniques for identifying items depicted in images may be implemented with facilities consistent with any hardware system or hardware systems defined herein. Many variations, modifications, additions, and improvements are possible. 
         [0052]    Plural instances may be provided for components, operations or structures described herein as a single instance. Finally, boundaries between various components, operations, and data stores are somewhat arbitrary, and particular operations are illustrated in the context of specific illustrative configurations. Other allocations of functionality are envisioned and may fall within the scope of the invention(s). In general, structures and functionality presented as separate components in the exemplary configurations may be implemented as a combined structure or component. Similarly, structures and functionality presented as a single component may be implemented as separate components. These and other variations, modifications, additions, and improvements fall within the scope of the invention(s).