Multi-classifier selection and monitoring for MMR-based image recognition

A MMR system that uses multiple classifiers for predicting, monitoring, and adjusting index tables for image recognition comprises a plurality of mobile devices, a pre-processing server or MMR gateway, and an MMR matching unit, and may include an MMR publisher. The MMR matching unit includes a plurality of recognition unit and index table pairs corresponding to classifiers to be applied to received image queries, as well as an image registration unit for storing and monitoring performance data for the classifiers. The MMR matching unit receives the image query and identifies, using a classifier set, a result including a document, the page, and the location on the page corresponding to the image query. The present invention also includes methods for monitoring online performance of a multiple classifier image recognition system, for classifier selection and comparison, and for offline classifier prediction.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to techniques for indexing and searching for mixed media documents formed from at least two media types, and more particularly, to recognizing images and other data using multiple-index Mixed Media Reality (MMR) recognition that uses printed media in combination with electronic media to retrieve mixed media documents.

2. Background of the Invention

Document printing and copying technology has been used for many years in many contexts. By way of example, printers and copiers are used in commercial office environments, in home environments with personal computers, and in document printing and publishing service environments. However, printing and copying technology has not been thought of previously as a means to bridge the gap between static printed media (i.e., paper documents), and the “virtual world” of interactivity that includes the likes of digital communication, networking, information provision, advertising, entertainment and electronic commerce.

Printed media has been the primary source of communicating information, such as news papers and advertising information, for centuries. The advent and ever-increasing popularity of personal computers and personal electronic devices, such as personal digital assistant (PDA) devices and cellular telephones (e.g., cellular camera phones), over the past few years has expanded the concept of printed media by making it available in an electronically readable and searchable form and by introducing interactive multimedia capabilities, which are unparalleled by traditional printed media.

Unfortunately, a gap exists between the electronic multimedia-based world that is accessible electronically and the physical world of print media. For example, although almost everyone in the developed world has access to printed media and to electronic information on a daily basis, users of printed media and of personal electronic devices do not possess the tools and technology required to form a link between the two (i.e., for facilitating a mixed media document).

Moreover, there are particular advantageous attributes that conventional printed media provides such as tactile feel, no power requirements, and permanency for organization and storage, which are not provided with virtual or digital media. Likewise, there are particular advantageous attributes that conventional digital media provides such as portability (e.g., carried in storage of cell phone or laptop) and ease of transmission (e.g., email).

One particular problem in the prior art is that the image recognition process is computationally very expensive and can require seconds if not minutes to accurately recognize the page and location of a pristine document from an input query image. This can especially be a problem with a large data set, for example, millions of pages of documents. Thus, there is a need for mechanisms to improve the accuracy, and thus speed, with which recognition can be performed.

SUMMARY OF THE INVENTION

The present invention overcomes the deficiencies of the prior art with an MMR system that uses multiple classifiers for predicting, monitoring, and adjusting index tables for image recognition. The system is particularly advantageous because it provides more accurate search results. The system is also advantageous because its unique architecture can be easily adapted and updated.

In one embodiment, the MMR system comprises a plurality of mobile devices, a computer, a pre-processing server or MMR gateway, and an MMR matching unit. Some embodiments also include an MMR publisher. The mobile devices are communicatively coupled to the pre-processing server or MMR gateway to send retrieval requests including image queries and other contextual information. The pre-processing server or MMR gateway processes the retrieval request and generates an image query that is passed on to the MMR matching unit. The MMR matching unit includes a plurality of recognition unit and index table pairs corresponding to classifiers to be applied to received image queries, as well as an image registration unit for storing and monitoring performance data for the classifiers. The MMR matching unit receives the image query and identifies, using a classifier set, a result including a document, the page, and the location on the page corresponding to the image query. A recognition result is returned and performance data for the classifiers used is stored and analyzed.

The present invention also includes a number of novel methods including a method for monitoring online performance of a multiple classifier image recognition system, for classifier selection and comparison, and for offline classifier prediction.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

An architecture for a mixed media reality (MMR) system100capable of receiving query images and returning document pages and location as well as receiving images, hot spots, and other data and adding such information to the MMR system is described. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the invention. It will be apparent, however, to one skilled in the art that the invention can be practiced without these specific details. In other instances, structures and devices are shown in block diagram form in order to avoid obscuring the invention. For example, the present invention is described in one embodiment below with reference to use with a conventional mass media publisher, in particular a newspaper publisher. However, the present invention applies to any type of computing systems and data processing in which multiple types of media including electronic media and print media are used.

Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment. In particular the present invention is described below in the context of two distinct architectures and some of the components are operable in both architectures while others are not.

System Overview

FIG. 1Ashows an embodiment of an MMR system100ain accordance with the present invention. The MMR system100acomprises a plurality of mobile devices102a-102n, a pre-processing server103, and an MMR matching unit106. In an alternative embodiment, the pre-processing server103and its functionality are integrated into the MMR matching unit106. The present invention provides an MMR system100afor image recognition in an adaptable multi-classifier system. The MMR system100ais particularly advantageous because its unique architecture can be easily adapted and updated to provide more accurate search results.

The mobile devices102a-102nare communicatively coupled by signal lines132a-132n, respectively, to the pre-processing server103to send a “retrieval request.” A retrieval request includes one or more of “image queries,” other contextual information, and metadata. In one embodiment, an image query is an image in any format, or one or more features of an image. Examples of image queries include still images, video frames and sequences of video frames. The mobile devices102a-102nare mobile computing devices such as mobile phones, which include a camera to capture images. It should be understood that the MMR system100awill be utilized by hundreds or even millions of users. Thus, even though only two mobile devices102a,102nare shown, those skilled in the art will appreciate that the pre-processing server103may be simultaneously coupled to, receive and respond to retrieval requests from numerous mobile devices102a-102n. Alternate embodiments for the mobile devices102a-102nare described in more detail below with reference toFIGS. 2A and 2B.

As noted above, the pre-processing server103is able to couple to hundreds if not millions of mobile computing devices102a-102nand service their retrieval requests. The pre-processing server103also may be communicatively coupled to the computer110by signal line130for administration and maintenance of the pre-processing server103. The computer110can be any conventional computing device such as a personal computer. The main function of the pre-processing server103is processing retrieval requests from the mobile devices102a-102nand returning recognition results back to the mobile devices102a-102n. In one embodiment, the recognition results include one or more of a Boolean value (true/false) and if true, a page ID, and a location on the page. In other embodiments, the recognition results also include one or more from the group of actions, a message acknowledging that the recognition was successful (or not) and consequences of that decision, such as the sending of an email message, a document, actions defined within a portable document file, addresses such as URLs, binary data such as video, information capable of being rendered on the mobile device102, menus with additional actions, raster images, image features, etc. The pre-processing server103generates an image query and recognition parameters from the retrieval request according to one embodiment, and passes them on to the MMR matching unit106via signal line134. The pre-processing server103also may perform some image tracking computation according to one embodiment. Embodiments and operation of the pre-processing server103are described in greater detail below with reference toFIG. 3A.

The MMR matching unit106receives the image query from the pre-processing server103on signal line134and sends it to one or more of recognition units to identify a result including a document, the page and the location on the page corresponding to the image query, referred to generally throughout this application as the “retrieval process.” The result is returned from the MMR matching unit106to the pre-processing server103on signal line134. In addition to the result, the MMR matching unit106may also return other related information such as hotspot data. The MMR matching unit106also includes components for receiving new content and updating and reorganizing index tables used in the retrieval process. The process of adding new content to the MMR matching unit106is referred to generally throughout this application as the “registration process.” Various embodiments of the MMR matching unit106and is components are described in more detail below with reference toFIG. 4A-8.

FIG. 1Bshows an embodiment of a MMR system100bin accordance with the present invention. The MMR system100bcomprises a plurality of mobile devices102a-102n, an MMR gateway104, an MMR matching unit106, an MMR publisher108and a computer110. The present invention provides, in one aspect, an MMR system100bfor use in newspaper publishing. The MMR system100bfor newspaper publishing is particularly advantageous because provides an automatic mechanism for a newspaper publisher to register images and content with the MMR system100b. The MMR system100bfor newspaper publishing is also advantageous because it has a unique architecture adapted to respond to image queries formed of image portions or pages of a printed newspaper.

The mobile devices102a-102nare similar to those described above, except that they are communicatively coupled by signal lines132a-132n, respectively, to the MMR gateway104to send a “retrieval request,” rather than to the pre-processing server103. It should be understood that the MMR system100bwill be utilized by hundreds or even millions of users that receive a traditional publication such as a daily newspaper.

As noted above, the MMR gateway104is able to couple to hundreds if not millions of mobile computing devices102a-102nand service their retrieval requests. The MMR gateway104is also communicatively coupled to the computer110by signal line130for administration and maintenance of the MMR gateway104and running business applications. In one embodiment, the MMR gateway104creates and presents a web portal for access by the computer110to run business applications as well as access logs of use of the MMR system100b. The computer110can be any conventional computing device such as a personal computer. The main function of the MMR gateway104is processing retrieval requests from the mobile devices102a-102nand returning recognition results back to the mobile devices102a-102n. The types of recognition results produced by the MMR gateway104are similar to those described above in conjunction with pre-processing server103. The MMR gateway104processes received retrieval requests by performing user authentication, accounting, analytics and other communication. The MMR gateway104also generates an image query and recognition parameters from the retrieval request, and passes them on to the MMR matching unit106via signal line134. Embodiments and operation of the MMR gateway104are described in greater detail below with reference toFIG. 3B.

The MMR matching unit106is similar to that described above in conjunction withFIG. 1A, except that the MMR matching unit106receives the image query from the MMR gateway104on signal line134as part of the “retrieval process.” The result is returned from the MMR matching unit106to the MMR gateway104on signal line134. In one embodiment, the MMR matching unit106is coupled to the output of the MMR publisher108via signal lines138and140to provide new content used to update index tables of the MMR matching unit106. In an alternate embodiment, the MMR publisher108is coupled to the MMR gateway104by signal line138and the MMR gateway104is in turn coupled by signal line136to the MMR matching unit106. In this alternate environment, MMR gateway104extracts augmented data such as hotspot information, stores it and passes the image page references and other information to the MMR matching unit106for updating of the index tables.

The MMR publisher108includes a conventional publishing system used to generate newspapers or other types of periodicals. In one embodiment, the MMR publisher108also includes components for generating additional information needed to register images of printed documents with the MMR system100. The information provided by the MMR publisher108to the MMR matching unit106includes an image file, bounding box data (x,y coordinates of the boxes that surround characters or words), hotspot data, and a unique page identification number. In the symbols of embodiment, this is a document in portable document format by Adobe Corp. of San Jose Calif. and bounding box information.

Referring now toFIGS. 2A and 2B, the first and second embodiments of the mobile device102will be described.

FIG. 2Ashows a first embodiment of the coupling132between the mobile device102and the pre-processing server103or MMR gateway104, according to the above-described embodiments of system100a,100b. In the embodiment ofFIG. 2A, the mobile device102is any mobile phone (or other portable computing device with communication capability) that includes a camera. For example, the mobile device102may be a smart phone such as the Blackberry® manufactured and sold by Research In Motion. The mobile device102is adapted for wireless communication with the network202by a communication channel230. The network202is a conventional type such as a cellular network maintained by wireless carrier and may include a server. In this embodiment, the mobile device102captures an image and sends the image to the network202over communications channel230such as by using a multimedia messaging service (MMS). The network202can also use the communication channel230to return results such as using MMS or using a short message service (SMS). As illustrated, the network202is in turn coupled to the pre-processing server103or MMR gateway104by signal lines232. Signal lines232represent a channel for sending MMS or SMS messages as well as a channel for receiving hypertext transfer protocol (HTTP) requests and sending HTTP responses. Those skilled in the art will recognize that this is just one example of the coupling between the mobile device102and the pre-processing server103or MMR gateway104. In an alternate embodiment for example, Bluetooth®, WiFi, or any other wireless communication protocol may be used as part of communication coupling between the mobile device102and the pre-processing server103or MMR gateway104. The mobile device102and the pre-processing server103or MMR gateway104could be coupled in many other ways understood by those skilled in the art (e.g., direct data connection, SMS, WAP, email) so long as the mobile device102is able to transmit images to the pre-processing server103or MMR gateway104and the pre-processing server103or MMR gateway104is able to respond by sending document identification, page number, and location information.

Referring now toFIG. 2B, a second embodiment of the mobile device102is shown. In this second embodiment, the mobile device102is a smart phone such as the iPhone™ manufactured and sold by Apple Computer Inc. of Cupertino Calif. The second embodiment has a number of components similar to those of the first embodiment, and therefore, like reference numbers are used to reference like components with the same or similar functionality. Notable differences between the first embodiment and the second embodiment include a quality predictor plug-in204that is installed on the mobile device102, and a Web server206coupled by signal line234to the network202. The quality predictor plug-in204analyzes the images captured by the mobile device102. The quality predictor plug-in204provides additional information produced by its analysis and includes that information as part of the retrieval request sent to the pre-processing server103or MMR gateway104to improve the accuracy of recognition. In an alternate embodiment, the output of the quality predictor plug-in204is used to select which images are transmitted from the mobile device102to the pre-processing server103or MMR gateway104. For example, only those images that have a predicted quality above a predetermined threshold (e.g., images capable of being recognized) are transmitted from the mobile device102to the pre-processing server103or MMR gateway104. Since transmission of images requires significant bandwidth and the communication channel230between the mobile device102and the network202may have limited bandwidth, using the quality predictor plug-in204to select which images to transmit is particularly advantageous.

The second embodiment shown inFIG. 2Balso illustrates how the results returned from the pre-processing server103or MMR gateway104, or other information provided by the quality predictor plug-in204, can be used by the mobile device102to access hotspot or augmented information available on a web server206. In such a case, the results from the pre-processing server103or MMR gateway104or output of the quality predictor plug-in204would include information that can be used to access Web server206such as with a conventional HTTP request and using web access capabilities of the mobile device102.

It should be noted that regardless of whether the first embodiment or the second embodiment of the mobile device102is used according toFIGS. 2A and 2B, the mobile device102generates a retrieval request that includes: a query image, a user or device ID, a command, and other contact information such as device type, software, plug-ins, location (for example if the mobile device includes a GPS capability), device and status information (e.g., device model, macro lens on/off status, autofocus on/off, vibration on/off, tilt angle, etc), context-related information (weather at the phone's location, time, date, applications currently running on the phone), user-related information (e.g., id number, preferences, user subscriptions, user groups and social structures, action and action-related meta data such as email actions and emails waiting to be sent), etc.

Referring now toFIG. 3A, one embodiment of the pre-processing server103is shown. This embodiment of the pre-processing server103comprises an operating system (OS)301, a controller303, a communicator305, a request processor307, and applications312, connected to system bus325. Optionally, the pre-processing server103also may include a web server304, a database306, and/or a hotspot database404.

As noted above, one of the primary functions of the pre-processing server103is to communicate with many mobile devices102to receive retrieval requests and send responses including a status indicator (true=recognized/false=not recognized), a page identification number, a location on the page and other information, such as hotspot data. A single pre-processing server103can respond to hundreds or millions of retrieval requests. For convenience and ease of understanding only a single pre-processing server103is shown inFIGS. 1A and 3A, however, those skilled in the art will recognize that in other embodiments any number of pre-processing servers103may be utilized to service the needs of a multitude of mobile devices102. More particularly, the pre-processing server103system bus325is coupled to signal lines132a-132nfor communication with various mobile devices102. The pre-processing server103receives retrieval requests from the mobile devices102via signal lines132a-132nand sends responses back to the mobile devices102using the same signal lines132a-132n. In one embodiment, the retrieval request includes: a command, a user identification number, an image, and other context information. For example, other context information may include: device information such as the make, model or manufacturer of the mobile device102; location information such as provided by a GPS system that is part of the mobile device or by triangulation; environmental information such as time of day, temperature, weather conditions, lighting, shadows, object information; and placement information such as distance, location, tilt, and jitter.

The pre-processing server103is also coupled to signal line130for communication with the computer110. Again, for convenience and ease of understanding only a single computer110and signal line130are shown inFIGS. 1A and 3A, but any number of computing devices may be adapted for communication with the pre-processing server103. The pre-processing server103facilitates communication between the computer110and the operating system (OS)301, a controller303, a communicator305, a request processor307, and applications312. The OS301, controller303, communicator305, request processor307, and applications312are coupled to system bus325by signal line330.

The pre-processing server103processes the retrieval request and generates an image query and recognition parameters that are sent via signal line134, which also is coupled to system bus325, and to the MMR matching unit106for recognition. The pre-processing server103also receives recognition responses from the MMR matching unit106via signal line134. More specifically, the request processor307processes the retrieval request and sends information via signal line330to the other components of the pre-processing server103as will be described below.

The operating system301is preferably a custom operating system that is accessible to computer110, and otherwise configured for use of the pre-processing server103in conjunction with the MMR matching unit106. In an alternate embodiment, the operating system301is one of a conventional type such as, WINDOWS®, Mac OS X®, SOLARIS®, or LINUX® based operating systems. The operating system301is connected to system bus325via signal line330.

The controller303is used to control the other modules305,307,312, per the description of each below. While the controller303is shown as a separate module, those skilled in the art will recognize that the controller303in another embodiment may be distributed as routines in other modules. The controller303is connected to system bus325via signal line330.

The communicator305is software and routines for sending data and commands among the pre-processing server103, mobile devices102, and MMR matching unit106. The communicator305is coupled to signal line330to send and receive communications via system bus325. The communicator305communicates with the request processor307to issue image queries and receive results.

The request processor307processes the retrieval request received via signal line330, performs preprocessing and issues image queries sent to MMR matching unit106via signal line134. In various embodiments, the preprocessing may include feature extraction and recognition parameter definition. The request processor307also sends information via signal line330to the other components of the pre-processing server103. The request processor307is connected to system bus325via signal line330.

The one or more applications312are software and routines for providing functionality related to the processing of MMR documents. The applications312can be any of a variety of types, including without limitation, drawing applications, word processing applications, electronic mail applications, search application, financial applications, and business applications adapted to utilize information related to the processing of retrieval quests and delivery of recognition responses such as but not limited to accounting, groupware, customer relationship management, human resources, outsourcing, loan origination, customer care, service relationships, etc. In addition, applications312may be used to allow for annotation, linking additional information, audio or video clips, building e-communities or social networks around the documents, and associating educational multimedia with recognized documents.

System bus325represents a shared bus for communicating information and data throughout pre-processing server103. System bus325may represent one or more buses including an industry standard architecture (ISA) bus, a peripheral component interconnect (PCI) bus, a universal serial bus (USB), or some other bus known in the art to provide similar functionality. Additional components may be coupled to pre-processing server103through system bus325according to various embodiments.

The pre-processing server103optionally also includes a web server304, a database306, and/or a hotspot database404according to various embodiments.

The web server304is a conventional type and is responsible for accepting HTTP requests from web clients and sending responses along with data contents, such as web pages, documents, and linked objects (images, etc.) The Web server304is coupled to data store306such as a conventional database. The Web server304is adapted for communication via signal line234to receive HTTP requests from any communication device, e.g., mobile devices102, across a network such as the Internet. The Web server304also is coupled to signal line330as described above to receive Web content associated with hotspots for storage in the data store306and then for later retrieval and transmission in response to HTTP requests. Those skilled in the art will understand that inclusion of the Web server304and data store306as part of the pre-processing server103is merely one embodiment and that the Web server304and the data store306may be operational in any number of alternate locations or configuration so long as the Web server304is accessible to mobile devices102and computers110via the Internet.

In one embodiment, the pre-processing server103also includes a hotspot database404. The hotspot database404is shown inFIG. 3Awith dashed lines to reflect that inclusion in the pre-processing server103is an alternate embodiment. The hotspot database404is coupled by signal line436to receive the recognition responses via line134. The hotspot database404uses these recognition responses to query the database and output via line432and system bus325the hotspot content corresponding to the recognition responses. This hotspot content is included with the recognition responses sent to the requesting mobile device102.

Referring now toFIG. 3B, one embodiment of the MMR gateway104is shown. This embodiment of the MMR gateway104comprises a server302, a Web server304, a data store306, a portal module308, a log310, one or more applications312, an authentication module314, an accounting module316, a mail module318, and an analytics module320.

As noted above, one of the primary functions of the MMR gateway104is to communicate with many mobile devices102to receive retrieval requests and send responses including a status indicator (true=recognized/false=not recognized), a page identification number, a location on the page and other information such as hotspot data. A single MMR gateway104can respond to hundreds or millions of retrieval requests. For convenience and ease of understanding only a single MMR gateway104is shown inFIGS. 1B and 3B, however, those skilled in the art will recognize that in other embodiments any number of MMR gateways104may be utilized to service the needs of a multitude of mobile devices102. More particularly, the server302of the MMR gateway104is coupled to signal lines132a-132nfor communication with various mobile devices102. The server302receives retrieval requests from the mobile devices102via signal lines132a-132nand sends responses back to the mobile devices102using the same signal lines132a-132n. In one embodiment, the retrieval request includes: a command, a user identification number, an image and other context information. For example, other context information may include: device information such as the make, model or manufacturer of the mobile device102; location information such as provided by a GPS system that is part of the mobile device or by triangulation; environmental information such as time of day, temperature, weather conditions, lighting, shadows, object information; and placement information such as distance, location, tilt, and jitter.

The server302is also coupled to signal line130for communication with the computer110. Again, for convenience and ease of understanding only a single computer110and signal line130are shown inFIGS. 1B and 3B, but any number of computing devices may be adapted for communication with the server302. The server302facilitates communication between the computer110and the portal module308, the log module310and the applications312. The server302is coupled to the portal module308, the log module310and the applications312by signal line330. As will be described in more detail below, the module cooperates with the server302to present a web portal that provides a user experience for exchanging information. The Web portal308can also be used for system monitoring, maintenance and administration.

The server302processes the retrieval request and generates an image query and recognition parameters that are sent via signal line134to the MMR matching unit106for recognition. The server302also receives recognition responses from the MMR matching unit106via 5 signal line134. The server302also processes the retrieval request and sends information via signal line330to the other components of the MMR gateway104as will be described below. The server302is also adapted for communication with the MMR publisher108by signal line138and the MMR matching unit106via signal line136. The signal line138provides a path for the MMR publisher108to send Web content for hotspots to the Web server304and to provide other information to the server302. In one embodiment, the server302receives information from the MMR publisher108and sends that information via signal line136for registration with the MMR matching unit106.

The web server304is a conventional type and is responsible for accepting requests from clients and sending responses along with data contents, such as web pages, documents, and linked objects (images, etc.) The Web server304is coupled to data store306such as a conventional database. The Web server304is adapted for communication via signal line234to receive HTTP requests from any communication device across a network such as the Internet. The Web server304is also coupled to signal line138as described above to receive Web content associated with hotspots for storage in the data store306and then for later retrieval and transmission in response to HTTP requests. Those skilled in the art will understand that inclusion of the Web server304and data store306as part of the MMR gateway104is merely one embodiment and that the Web server304and the data store306may be operational in any number of alternate locations or configuration so long as the Web server304is accessible to mobile devices102and computers110via the Internet.

In one embodiment, the portal module308is software or routines operational on the server302for creation and presentation of the Web portal. The portal module308is coupled to signal line330for communication with the server302. In one embodiment, the web portal provides an access point for functionality including administration and maintenance of other components of the MMR gateway104. In another embodiment, the web portal provides an area where users can share experiences related to MMR documents. In yet another embodiment, the web portal but an area where users can access business applications and the log310of usage.

The log310is a memory or storage area for storing a list of the retrieval requests received by the server302from mobile devices102and all corresponding responses sent by the server302to the mobile device. In another embodiment, the log310also stores a list of the image queries generated and sent to the MMR matching unit106and the recognition responses received from the MMR matching unit106. The log310is coupled to signal line330for access by the server302.

The one or more business applications312are software and routines for providing functionality related to the processing of MMR documents. In one embodiment the one or more business applications312are executable on the server302. The business applications312can be any one of a variety of types of business applications adapted to utilize information related to the processing of retrieval requests and delivery of recognition responses such as but not limited to accounting, groupware, customer relationship management, human resources, outsourcing, loan origination, customer care, service relationships, etc.

The authentication module314is software and routines for maintaining a list of authorized users and granting access to the MMR system100. In one embodiment, the authentication module314maintains a list of user IDs and passwords corresponding to individuals who have created an account in the system100b, and therefore, are authorized to use MMR gateway104and the MMR matching unit106to process retrieval requests. The authentication module314is communicatively coupled by signal line330to the server302. But as the server302receives retrieval requests, they can be processed and compared against information in the authentication module314before generating and sending the corresponding image query on signal line134. In one embodiment, the authentication module314also generates messages for the server302to return to the mobile device102when the mobile device is not authorized, the mobile device has not established an account, or the account for the mobile device102is locked such as due to abuse or lack of payment.

The accounting module316is software and routines for performing accounting related to user accounts and use of the MMR system100b. In one embodiment, the retrieval services are provided under a variety of different economic models such as but not limited to use of the MMR system100bunder a subscription model, a charge per retrieval request model or various other pricing models. In one embodiment, the MMR system100bprovides a variety of different pricing models and is similar to those currently offered for cell phones and data networks. The accounting module316is coupled to the server302by signal line330to receive an indication of any retrieval request received by the server302. In one embodiment, the accounting module316maintains a record of transactions (retrieval request/recognition responses) processed by the server302for each mobile device102. Although not shown, the accounting module316can be coupled to a traditional billing system for the generation of an electronic or paper bill.

The mail module318is software and routines for generating e-mail and other types of communication. The mail module318is coupled by signal at330to the server302. In one embodiment, the mobile device102can issue retrieval requests that include a command to deliver a document or a portion of a document or other information via e-mail, facsimile or other traditional electronic communication means. The mail module318is adapted to generate and send such information from the MMR gateway104to an addressee as prescribed by the user. In one embodiment, each user profile has associated addressees which are potential recipients of information retrieved.

The analytics module320is software and routines for measuring the behavior of users of the MMR system100b. The analytics module320is also software and routines for measuring the effectiveness and accuracy of feature extractors and recognition performed by the MMR matching unit106. The analytics module320measures use of the MMR system100bincluding which images are most frequently included as part of retrieval requests, which hotspot data is most often accessed, the order in which images are retrieved, the first image in the retrieval process, and other key performance indicators used to improve the MMR experience and/or a marketing campaign's audience response. In one embodiment, the analytics module320measures metrics of the MMR system100band analyzes the metrics used to measure the effectiveness of hotspots and hotspot data. The analytics module320is coupled to the server302, the authentication module314and the accounting module316by signal line330. The analytics module320is also coupled by the server302to signal line134and thus can access the components of the MMR matching unit106to retrieve recognition parameters, images features, quality recognition scores and any other information generated or used by the MMR matching unit106. The analytics module320can also perform a variety of data retrieval and segmentation based upon parameters or criteria of users, mobile devices102, page IDs, locations, etc.

In one embodiment, the MMR gateway104also includes a hotspot database404. The hotspot database404is shown inFIG. 3with dashed lines to reflect that inclusion in the MMR gateway104is an alternate embodiment. The hotspot database404is coupled by signal line436to receive the recognition responses via line134. The hotspot database404uses these recognition responses to query the database and output via line432the hotspot content corresponding to the recognition responses. This hotspot content is sent to the server302so that it can be included with the recognition responses and sent to the requesting mobile device102.

Referring now toFIGS. 4A and 4B, two embodiments for the MMR matching unit106will be described. The basic function of the MMR matching unit106is to receive an image query, send the image query for recognition, perform recognition on the images in the image query, retrieve hotspot information, combine the recognition result with hotspot information, and send it back to the pre-processing server103or MMR gateway104.

FIG. 4Aillustrates a first embodiment of the MMR matching unit106. The first embodiment of the MMR matching unit106comprises a dispatcher402, a hotspot database404, an acquisition unit406, an image registration unit408, and a dynamic load balancer418. The acquisition unit406further comprises a plurality of the recognition units410a-410nand a plurality of index tables412a-412n. The image registration unit408further comprises an indexing unit414and a master index table416.

The dispatcher402is coupled to signal line134for receiving an image query from and sending recognition results to the pre-processing server103or MMR gateway104. The dispatcher402is responsible for assigning and sending an image query to respective recognition units410a-410n. In one embodiment, the dispatcher402receives an image query, generates a recognition unit identification number, and sends the recognition unit identification number and the image query to the acquisition unit406for further processing. The dispatcher402is coupled to signal line430to send the recognition unit identification number and the image query to the recognition units410a-410n. The dispatcher402also receives the recognition results from the acquisition unit406via signal line430. One embodiment for the dispatcher402will be described in more detail below with reference toFIG. 5.

An alternate embodiment for the hotspot database404has been described above with reference toFIGS. 3A-3Bwherein the hotspot database is part of the pre-processing server103or MMR gateway104. However, the preferred embodiment for the hotspot database404is part of the MMR matching unit106as shown inFIG. 4A. Regardless of the embodiment, the hotspot database404has a similar functionality. The hotspot database404is used to store hotspot information. Once an image query has been recognized and recognition results are produced, these recognition results are used as part of a query of the hotspot database404to retrieve hotspot information associated with the recognition results. The retrieved hotspot information is then output on signal line134to the pre-processing server103or MMR gateway104for packaging and delivery to the mobile device102. As shown inFIG. 4A, the hotspot database404is coupled to the dispatcher402by signal line436to receive queries including recognition results. The hotspot database404is also coupled by signal line432and signal line134to the pre-processing server103or MMR gateway104for delivery of query results. The hotspot database404is also coupled to signal line136to receive new hotspot information for storage from the MMR publisher108, according to one embodiment.

The acquisition unit406comprises the plurality of the recognition units410a-410nand a plurality of index tables412a-412n. Each of the recognition units410a-410nhas and is coupled to a corresponding index table412a-412n. In one embodiment, each recognition unit410/index table412pair is on the same server. The dispatcher402sends the image query to one or more recognition units410a-410n. In one embodiment that includes redundancy, the image query is sent from the dispatcher402to a plurality of recognition units410for recognition and retrieval and the index tables412a-nindex the same data. In the serial embodiment, the image query is sent from the dispatcher402to a first recognition unit410a. If recognition is not successful on the first recognition unit410a, the image query is passed on to a second recognition unit410b, and so on. In yet another embodiment, the dispatcher402performs some preliminary analysis of the image query and then selects a recognition unit410a-410nbest adapted and most likely to be successful at recognizing the image query. Those skilled in the art will understand that there are a variety of configurations for the plurality of recognition units410a-410nand the plurality of index tables412a-412n. Example embodiments for the acquisition unit406will be described in more detail below with reference toFIGS. 6A-6B. It should be understood that the index tables412a-412ncan be updated at various times as depicted by the dashed lines434from the master index table416.

The image registration unit408comprises the indexing unit414, the classifier performance database415, and the master index table416. The image registration unit408has an input coupled to signal on136to receive updated information from the MMR publisher108, according to one embodiment, and an input coupled to signal line438to receive updated information from the dynamic load balancer418. The image registration unit408is responsible for maintaining the master index table416and migrating all or portions of the master index table416to the index tables412a-412n(slave tables) of the acquisition unit406. In one embodiment, the indexing unit414receives images, unique page IDs, and other information; and converts it into index table information that is stored in the master index table416. In one embodiment, the master index table416also stores the record of what is migrated to the index table412. The indexing unit414also cooperates with the MMR publisher108according to one embodiment to maintain a unique page identification numbering system that is consistent across image pages generated by the MMR publisher108, the image pages stored in the master index table416, and the page numbers used in referencing data in the hotspot database404. The image registration unit408also includes the classifier performance database415for storing performance data associated with various classifiers associated with index tables412. The image registration unit408, in conjunction with the classifier performance database415and the dynamic load balancer work together to perform both offline and online analyses and updates to the classifiers being used. Exemplary embodiments for the image registration unit408is shown and described in more detail below with reference toFIGS. 7A-7B.

The dynamic load balancer418has an input coupled to signal line430to receive the query image from the dispatcher402and the corresponding recognition results from the acquisition unit406. The output of the dynamic load balancer418is coupled by signal line438to an input of the image registration unit408. The dynamic load balancer418provides input to the image registration unit408that is used to dynamically adjust the index tables412a-412nof the acquisition unit406. In particular, the dynamic load balancer418monitors and evaluates the image queries that are sent from the dispatcher402to the acquisition unit406for a given period of time. Based on the usage, the dynamic load balancer418provides input to adjust the index tables412a-412n. For example, the dynamic load balancer418may measure the image queries for a day. Based on the measured usage for that day, the index tables may be modified and configured in the acquisition unit406to match the usage measured by the dynamic load balancer418.

FIG. 4Billustrates a second embodiment of the MMR matching unit106. In the second embodiment, many of the components of the MMR matching unit106have the same or a similar function to corresponding elements of the first embodiment. Thus, like reference numbers have been used to refer to like components with the same or similar functionality. The second embodiment of the MMR matching unit106includes the dispatcher402, the hotspot database404, and the dynamic load balancer418similar to the first embodiment of the MMR matching unit106. However, the acquisition unit406and the image registration unit408are different from that described above with reference toFIG. 4A. In particular, the acquisition unit406and the image registration unit408utilize a shared SQL database for the index tables and the master table. More specifically, there is the master index table416and a mirrored database418that includes the local index tables412a-n. Moreover, a conventional functionality of SQL database replication is used to generate the mirror images of the master index table416stored in the index tables412a-412nfor use in recognition. The image registration unit408is configured so that when new images are added to the master index table416they are immediately available to all the recognition units410. This is done by mirroring the master index table416across all the local index tables412a-nusing large RAM (not shown) and database mirroring technology.

Referring now toFIG. 5, an embodiment of the dispatcher402shown. The dispatcher402comprises a quality predictor502, an image feature order unit504, and a distributor506. The quality predictor502, the image feature order unit504, and the distributor506are coupled to signal line532to receive image queries from the pre-processing server103or MMR gateway104.

The quality predictor502receives image queries and generates a recognizability score used by the dispatcher402to route the image query to one of the plurality of recognition units410. The dispatcher402also receives recognition results from the recognition units410on signal line530. The recognition results include a Boolean value (true/false) and if true, a page ID, and a location on the page. In one embodiment, the dispatcher402merely receives and retransmits the data to the pre-processing server103or MMR gateway104.

The image feature order unit504receives image queries and outputs an ordering signal. The image feature order unit504analyzes an input image query and predicts the time required to recognize an image by analyzing the image features it contains. The difference between the actual recognition time and the predicted time is used to adjust future predictions thereby improving accuracy. In the simplest of embodiments, simple images with few features are assigned to lightly loaded recognition units410so that they will be recognized quickly and the user will see the answer immediately. In one embodiment, the features used by the image feature order unit504to predict the time are different than the features used by recognition units410for actual recognition. For example, the number of corners detected in an image is used to predict the time required to analyze the image. The feature set used for prediction need only be correlated with the actual recognition time. In one embodiment, several different features sets are used and the correlations to recognition time measured over some period. Eventually, the feature set that is the best predictor and lowest cost (most efficient) would be determined and the other feature sets could be discarded.

The distributor506is also coupled to receive the output of the quality predictor502and image feature order unit504. The distributor506includes a FIFO queue508and a controller510. The distributor506generates an output on signal line534that includes the image query and a recognition unit identification number (RUID). Those skilled in the art will understand that in other embodiments the image query may be directed to any particular recognition unit using a variety of means other than the RUID. As image queries are received on the signal line532, the distributor506receives the image queries and places them in the order in which they are received into the FIFO queue508. The controller510receives a recognizability score for each image query from the quality predictor502and also receives an ordering signal from the image feature order unit504. Using this information from the quality predictor502and the image feature order unit504, the controller510selects image queries from the FIFO queue508, assigns them to particular recognition units410and sends the image query to the assigned recognition unit410for processing. The controller510maintains a list of image queries assigned to each recognition unit410and the expected time to completion for each image (as predicted by the image feature order unit504). The total expected time to empty the queue for each recognition unit410is the sum of the expected times for the images assigned to it. The controller510can execute several queue management strategies. In a simple assignment strategy, image queries are removed from the FIFO queue508in the order they arrived and assigned to the first available recognition unit410. In a balanced response strategy, the total expected response time to each query is maintained at a uniform level and query images are removed from the FIFO queue508in the order they arrived, and assigned to the FIFO queue508for a recognition unit so that its total expected response time is as close as possible to the other recognition units. In an easy-first strategy, images are removed from the FIFO queue508in an order determined by their expected completion times—images with the smallest expected completion times are assigned to the first available recognition unit. In this way, users are rewarded with faster response time when they submit an image that's easy to recognize. This could incentivize users to carefully select the images they submit. Other queue management strategies are possible.

Referring now toFIGS. 6A and 6B, embodiments of the acquisition unit406will be described.

FIG. 6Aillustrates one embodiment for the acquisition unit406where the recognition unit410and index table412pairs are partitioned based on whether the classifiers they contain are in use612as the current classifier set. As shown inFIG. 6A, the acquisition unit406comprises a plurality of recognition units410a-gand a plurality of index tables412a-g. The plurality of recognition units410a-gis coupled to signal line430to receive image queries from the dispatcher402. Each of the plurality of recognition units410a-gis coupled to a corresponding index table412a-g, and is associated with a particular classifier. The recognition units410extract features from the image query and compare those image features to the features stored in the index table according to the classifier to identify a matching page and location on that page. Various aspects of classifier selection and updating are described in conjunction withFIGS. 10-15B.

Example recognition and retrieval systems and methods are disclosed in U.S. patent application Ser. No. 11/461,017, titled “System And Methods For Creation And Use Of A Mixed Media Environment,” filed Jul. 31, 2006, U.S. patent application Ser. No. 11/461,279, titled “Method And System For Image Matching In A Mixed Media Environment,” filed Jul. 31, 2006; U.S. patent application Ser. No. 11/461,286, titled “Method And System For Document Fingerprinting Matching In A Mixed Media Environment,” filed Jul. 31, 2006; U.S. patent application Ser. No. 11/461,294, titled “Method And System For Position-Based Image Matching In A Mixed Media Environment,” filed Jul. 31, 2006; U.S. patent application Ser. No. 11/461,300, titled “Method And System For Multi-Tier Image Matching In A Mixed Media Environment,” filed Jul. 31, 2006; U.S. patent application Ser. No. 11/461,147, titled “Data Organization and Access for Mixed Media Document System,” filed Jul. 31, 2006; U.S. patent application Ser. No. 11/461,164, titled “Database for Mixed Media Document System,” filed Jul. 31, 2006; U.S. patent application Ser. No. 11/461,109, titled “Searching Media Content For Objects Specified Using Identifiers,” filed Jul. 31, 2006; U.S. patent application Ser. No. 12/059,583, titled “Invisible Junction Feature Recognition For Document Security Or Annotation,” filed Mar. 31, 2008; U.S. patent application Ser. No. 12/121,275, titled “Web-Based Content Detection In Images, Extraction And Recognition,” filed May 15, 2008; U.S. patent application Ser. No. 11/776,510, titled “Invisible Junction Features For Patch Recognition,” filed Jul. 11, 2007; U.S. patent application Ser. No. 11/776,520, titled “Information Retrieval Using Invisible Junctions and Geometric Constraints,” filed Jul. 11, 2007; U.S. patent application Ser. No. 11/776,530, titled “Recognition And Tracking Using Invisible Junctions,” filed Jul. 11, 2007; and U.S. patent application Ser. No. 11/777,142, titled “Retrieving Documents By Converting Them to Synthetic Text,” filed Jul. 12, 2007; and U.S. patent application Ser. No. 11/624,466, titled “Synthetic Image and Video Generation From Ground Truth Data,” filed Jan. 18, 2007; which are incorporated by reference in their entirety.

As shown inFIG. 6A, the recognition unit410/index table412pairs are grouped into two general categories: index tables412with classifiers currently in use612(412a-c), and index tables412with classifiers not currently in use614(412d-g). It should be noted that the use of three recognition units410and index tables412as the first group612is merely by way example and used demonstrate a relative proportion as compared with the number of recognition units410and index tables412in the second group614. The number of recognition units410and index tables412in any particular group612,614may be modified based on the total number of recognition units410and index tables412. Furthermore, the number of recognition units410and index tables412in any particular group612,614, may be adapted so that it matches the profile of all users sending retrieval request to the acquisition unit406for a given publication.

FIG. 6Billustrates a second embodiment for the acquisition unit406wherein the recognition units410and index tables412are partitioned based upon the type of recognition algorithm they implement. In the second embodiment, the recognition units410are also coupled such that the failure of a particular recognition unit to generate a registration result causes the input image query to be sent to another recognition unit for processing. Furthermore, in the second embodiment, the index tables412include feature sets that are varied according to different device and environmental factors of image capture devices (e.g., blur, etc.).

The second embodiment of the acquisition unit406includes a plurality of recognition units410a-410e, a plurality of the index tables412a-412eand a result combiner610. In this embodiment, the recognition units410a-410eeach utilize a different type of recognition algorithm. For example, recognition units410a,410b, and410cuse a first recognition algorithm; recognition unit410duses a second recognition algorithm; and recognition unit410euses a third recognition algorithm for recognition and retrieval of page numbers and locations. Recognition units410a,410d, and410eeach have an input coupled signal line430by signal line630for receiving the image query. The recognition results from each of the plurality of recognition units410a-410eare sent via signal lines636,638,640,642, and644to the result combiner610. The output of the result combiner610is coupled to signal line430.

In one embodiment, the recognition units410a,410b, and410ccooperate together with index tables1,2, and3,412a-412ceach storing image features corresponding to the same pages but with various modifications, e.g., due to different device and environmental factors. For example, index table1412amay store image features for pristine images of pages such as from a PDF document, while index table2412bstores images of the same pages but with a first level of modification, and index table3412cstores images of the same pages but with a second level of modification. In one embodiment, the index tables1,2, and3,412a-412care quantization trees. The first recognition unit410areceives the image query via signal line630. The first recognition unit410acomprises a first type of feature extractor602and a retriever604a. The first type of feature extractor602receives the image query, extracts the Type1features, and provides them to the retriever604a. The retriever604auses the extracted Type1features and compares them to the index table1412a. If the retriever604aidentifies a match, the retriever604asends the recognition results via signal line636to the result combiner610. If however, the retriever604awas unable to identify a match or identifies a match with low confidence, the retriever604asends the extracted Type1features to the retriever604bof the second recognition unit410bvia signal line632. It should be noted that since the Type1features already have been extracted, the second recognition unit410bdoes not require a feature extractor602. The second recognition unit410bperforms retrieval functions similar to the first recognition unit410a, but cooperates with index table2412bthat has Type1features for slightly blurry images. If the retriever604bidentifies a match, the retriever604bsends the recognition results via signal line638to the result combiner610. If the retriever604bof the second recognition unit410bis unable to identify a match or identifies a match with low confidence, the retriever604bsends the extracted features to the retriever604cof the third recognition unit410bvia signal line634. The retriever604cthen performs a similar retrieval function but on index table3412c. Those skilled in the art will understand that while one pristine set of images and two levels of modification are provided, this is only by way of example and that any number of additional levels of modification from 0 to n may be used.

The recognition units410dand410eoperate in parallel with the other recognition units410a-c. The fourth recognition unit410dcomprises a second type of feature extractor606and a retriever604d. The Type2feature extractor606received the image query, possibly with other image information, parses the bounding boxes or other feature identifiers, and generates Type2coding features. These Type2features are provided to the retriever604dand the retriever604dcompares them to the features stored in index table4412d. In one embodiment, index table4412dis a hash table. The retriever604didentifies any matching pages and returns the recognition results to the result combiner610via signal line642. The fifth recognition unit410eoperates in a similar manner but for a third type of feature extraction. The fifth recognition unit410ecomprises a Type3feature extractor608and a retriever604e. The Type3feature extractor608receives the image query, possibly with other image information, or other feature identifiers, parses the image and generates Type3features and the features that are provided to the retriever604eand the retriever604ecompares them to features stored in the index table5412e. In one embodiment, the index table5412eis a SQL database of character strings. The retriever604eidentifies any matching strings and returns the recognition results to the result combiner610via signal line644. In one exemplary embodiment the three types of feature extraction include the invisible junction recognition algorithm, brick wall coding, and path coding.

The result combiner610receives recognition results from the plurality of recognition units410a-eand produces one or a small list of matching results. In one embodiment, each of the recognition results includes an associated confidence factor. In another embodiment, context information such as date, time, location, personal profile, or retrieval history is provided to the result combiner610. These confidence factors along with other information are used by the result combiner610to select the recognition results most likely to match the input image query. The above described embodiments are not meant to be exclusive or limiting, and may be combined according to other embodiments.

Image Registration Unit408

FIG. 7Ashows an embodiment of the image registration unit408. The image registration unit408comprises an indexing unit414, a classifier performance database415, and a master index table416. The indexing unit414comprises an image alteration generator703, a plurality of feature extractors704a-c, modules752-764, and a plurality of master index tables416a-c. The image registration unit408also includes other control logic (not shown) that controls the updating of the index tables412from the master index table416. The image registration unit408can update the index tables412of the acquisition unit406in a variety of different ways based on various criteria such performing updates on a periodic basis, performing updates when new content is added, performing updates based on usage, performing updates for storage efficiency, etc.

The classifier performance database415stores classifier set information and associated performance data for the classifiers sets as a group and as individual classifiers, including decision percentages for each classifier, an interval specification for specific time range, a pointer to the image queries associated with the internal, a classifier identification, and the listed decisions for the image query, such as identity, confidence value, and run time. The performance data for a set of classifiers includes percent correctly identified image queries, percent rejected in each queries, and percent error produced by the classifiers, as well as over all run time and time spent in each classifier.

The image alteration generator703of the indexing unit414has an input coupled in signal line730to receive an image and a page identification number. The image alteration generator703has a plurality of outputs and each output is coupled by signal lines732,734, and736to feature extractors704a-c, respectively. The image alteration generator703passes a pristine image and the page identification number to the output and signal line732. The image alteration generator703then generates a first altered image and outputs it and the page identification number on signal line734to feature extractor704b, and a second altered image, altered differently than the first altered image, and outputs it and page identification number on signal line736to feature extractor704c.

The feature extractors704receive the image and page ID, extract the features from the image and send them along with the page ID to a respective index table updater706. The outputs of the plurality of feature extractors704a-care coupled to the plurality of index table updaters706a-c. For example, the output of feature extractor704ais coupled to an input of index table updater706a. The remaining feature extractors704b-care similarly coupled to respective index table updaters706b-c. The index table updaters706are responsible for formatting the extracted features and storing them in a corresponding master index table416. While the master index table416is shown as three separate master index tables416a-c, those skilled in the art will recognize that all the master index tables could be combined into a single master index table or into a few master index tables. In the embodiment including the MMR publisher108, once the index table updaters706have stored the extracted features in the index table416, they issue a confirmation signal that is sent via signal lines740and136back to the MMR publisher108.

The indexing unit414further comprises a results recorder752, a decision monitor754, an alert monitor756, a classifier selector758, a fixed classifier analyzer760, a classifier set performance analyzer762, and a classifier switching calculator764.

The results recorder752is software and routines for receiving and recording the results of the recognition according to a classifier set, e.g., as part of a method for monitoring online performance of a multiple-classifier image recognition system discussed inFIG. 10according to one embodiment. The results may be received via dynamic load balancer418. The recognition results may include, in addition to page identification and x, y location on the page where the image query occurs, the time when each image query arrived, metadata associated with the image query, e.g., model of camera used, optical characteristics of the camera, identifying information such as mobile device102owner, identification number for the mobile device102, identities of the classifiers that provided decisions, and the classifier architecture used.

The decision monitor754is software and routines for monitoring decision percentages for the classifiers and comparing them to expected decision percentages for the classifiers. The alert monitor756triggers alerts to the system controller when various thresholds are exceeded. For example, if the difference between the actual and expected decision percentages exceed a predetermined threshold for a subinterval, an alert is triggered. Also, an alert is triggered when too many alerts are triggered during a short period of time such that they exceed an alert threshold.

The classifier selector758is software and routines for performing the classifier selection process described in conjunction with FIGS.12and13A-13B. The classifier selection process determines a set of classifiers for a set of image queries, and the performance data for the set of classifiers, by applying all available classifiers to the set of image queries. The performance data for the selected set includes percent correctly identified image queries, percent rejected, and percent error produced by the classifiers, as well as over all run time and time spent in each classifier.

The fixed classifier analyzer760is software and routines for performing the fixed classifier analysis described in conjunction with FIGS.12and13-A-13B. The fixed classifier analyzer760applies a fixed set of classifiers to a set of image queries received during an interval, and outputs performance data associated with the fixed set of classifiers. The performance data includes percent correct, percent rejected, percent error, and run times

The classifier set performance analyzer762is software and routines for performing the classifier set performance analysis as described in conjunction with FIGS.12and13A-13B. The classifier set performance analysis compares the selected classifier set and its performance data with the fixed classifier set and its performance data. The classifier set performance analysis computes a distance measure between the respective performances of two classifier sets on the same set of image queries. This distance measure takes into account the algorithmic performance and the run times.

A classifier switching calculator764is software and routines for performing the classifier switching calculation described in conjunction withFIGS. 13A-13B. From the classifier set performance analysis on the classifier sets, the resulting best classifier set for the interval is compared to the classifier set for the previous interval to determine whether a change in classifier sets should be made.

FIG. 7Bshows an embodiment of the image registration unit408. The image registration unit408comprises an image alteration generator703, a plurality of Type1feature extractors704a-c, a plurality of Type1index table updaters706a-c, a Type2feature extractor708, a Type2index table updater710, a Type3feature extractor712, a Type3index table updater714and a plurality of master index tables416a-e. The image registration unit408also includes other control logic (not shown) that controls the updating of the working index tables412from the master index table416. The image registration unit408can update the index tables412of the acquisition unit406in a variety of different ways based on various criteria such performing updates on a periodic basis, performing updates when new content is added, performing updates based on usage, performing updates for storage efficiency, etc.

The image alteration generator703has an input coupled in signal line730to receive an image and a page identification number. The image alteration generator703has a plurality of outputs and each output is coupled by signal lines732,734, and736to Type1extractors704a-c, respectively. The image alteration generator703passes a pristine image and the page identification number to the output and signal line732. The image alteration generator703then generates a first altered image and outputs it and the page identification number on signal line734to Type1feature extractor704b, and a second altered image, altered differently than the first altered image, and outputs it and page identification number on signal line736to Type1feature extractor704c.

The Type1feature extractors704receive the image and page ID, extract the Type1features from the image and send them along with the page ID to a respective Type1index table updater706. The outputs of the plurality of Type1feature extractors704a-care coupled to input of the plurality of Type1index table updaters706a-c. For example, the output of Type1feature extractor704ais coupled to an input of Type1index table updater706a. The remaining Type1feature extractors704b-care similarly coupled to respective Type1index table updaters706b-c. The Type1index table updaters706are responsible for formatting the extracted features and storing them in a corresponding master index table416. While the master index table416is shown as five separate master index tables416a-e, those skilled in the art will recognize that all the master index tables could be combined into a single master index table or into a few master index tables. In the embodiment including the MMR publisher108, once the Type1index table updaters706have stored the extracted features in the index table416, they issue a confirmation signal that is sent via signal lines740and136back to the MMR publisher108.

The Type2feature extractor708and the Type3feature extractor712operate in a similar fashion and are coupled to signal line738to receive the image, a page identification number, and bounding box information. The Type2feature extractor708extracts information from the input needed to update its associated index table416d. The Type2index table updater710receives the extracted information from the Type2feature extractor708and stores it in the index table416d. The Type3feature extractor712and the Type3index table updater714operate in a like manner but for Type3's feature extraction algorithm. The Type3feature extractor712also receives the image, a page number, and bounding box information via signal line738. The Type3feature extractor712extracts Type3information and passes it to the Type3index table updater714. The Type3index table updater714stores the information in index table5416e. The architecture of the registration unit408is particularly advantageous because it provides an environment in which the index tables can be automatically updated, simply by providing images and page numbers to the image registration unit408. According to one embodiment, Type1feature extraction is invisible junction recognition, Type2feature extraction is brick wall coding, and Type3feature extraction is path coding.

As shown inFIG. 8, one embodiment of the quality predictor502comprises recognition algorithm parameters802, a vector calculator804, a score generator806and a scoring module808. The quality predictor502has inputs coupled to signal line532to receive an image query, context and metadata, and device parameters. The image query may be video frames, a single frame or image features. The context and metadata includes time, date, location, environmental conditions, etc. The device parameters include brand, type, macro block on/off, gyro or accelerometer reading, aperture, time, exposure, flash, etc. Additionally, the quality predictor502uses certain parameters of the recognition algorithm parameters802. These parameters of the recognition algorithm parameters802can be provided to the quality predictor502from the acquisition unit406or the image registration unit408. The vector calculator804computes quality feature vectors from the image to measure its content and distortion, such as its blurriness, existence and amount of recognizable features, its luminosity, etc. The vector calculator804computes any number of quality feature vectors from one to n. In some cases, the vector calculator804requires knowledge of the recognition algorithm(s) to be used, and the vector calculator804is coupled by signal line820to the recognition algorithm parameters802. For example, if an Invisible Junctions algorithm is employed, the vector calculator804computes the number of junction points in the image as a measure of its recognizability. All or some of these computed features are then input to score generator806via signal line824. The score generator806is also coupled by signal line822to receive recognition parameters for the recognition algorithm parameters802. The output of the score generator806is provided to the scoring module808. The scoring module808generates a recognition score using the recognition scores provided by the score generator806and applies weights to those scores. In one embodiment, the result is a single recognizability score. In another embodiment, the result is a plurality of recognizability scores ranked from highest to lowest.

Methods

FIG. 9is a flowchart of a general method for generating and sending a retrieval request and processing the retrieval request with an MMR system100. The method begins with the mobile device102capturing902an image. A retrieval request that includes the image, a user identifier, and other context information is generated by the mobile device102and sent904to the pre-processing server103or MMR gateway104. The pre-processing server103or MMR gateway104processes906the retrieval request by extracting the user identifier from the retrieval request and verifying that it is associated with a valid user. The pre-processing server103or MMR gateway104also performs other processing such as recording the retrieval request in the log310, performing any necessary accounting associated with the retrieval request and analyzing any MMR analytics metrics. Next, the pre-processing server103or MMR gateway104generates908an image query and sends it to the dispatcher402. The dispatcher402performs load-balancing and sends the image query to the acquisition unit406. In one embodiment, the dispatcher402specifies the particular recognition unit410of the acquisition unit406that should process the image query. Then the acquisition unit406performs912image recognition to produce recognition results. The recognition results are returned914to the dispatcher402and in turn the pre-processing server103or MMR gateway104. The recognition results are also used to retrieve916hotspot data corresponding to the page and location identified in the recognition results. Finally, the hotspot data and the recognition results are sent918from the pre-processing server103or MMR gateway104to the mobile device102.

Referring now toFIG. 10, a method for monitoring online performance of the multiple-classifier image recognition system is shown according to one embodiment of the present invention. In general, the method monitors classifier performance during an interval of time, and triggers alerts if actual performance deviates from the expected performance for a classifier. The method begins by applying1002a classifier set to image queries received during a time interval. A classifier set includes multiple index tables412, each corresponding to a classifier, e.g., as discussed in conjunction withFIG. 6A. As image queries are received by the acquisition unit406, they are processed according to the classifiers associated with each index table412. The recognition results produced by the classifiers are recorded1004, e.g. in classifier performance database415. According to one embodiment, in addition to the page identification and x, y location on the page where the image query occurs, the results include the time when each image query arrived, metadata associated with the image query, e.g., model of camera used, optical characteristics of the camera, identifying information such as mobile device102owner, identification number for the mobile device102, identities of the classifiers that provided decisions, and the classifier architecture used. In addition, decision percentages for each classifier in the classifier set, i.e., what percentage of all image queries are processed by that classifier, are monitored1006, e.g. by indexing unit414.

Using an expected decision percentage for each classifier and the classifier set, the indexing unit414calculates1008the difference between the monitored decision percentage and an expected decision percentage. The expected decision percentage may be determined from stored classifier performance data resulting from a classifier selection process, as discussed in conjunction withFIG. 12. For example, the performance data may be stored in classifier performance database415. Next, the indexing unit414determines1010whether the calculated difference is greater than the performance threshold for the classifier. If the difference is not greater, the process returns to step1006, and monitoring continues. If the difference is greater than the performance threshold for the classifier, a performance alert is triggered1012for the classifier. The indexing unit414may further keep a record of performance alerts.

It is then determined1014whether the number of performance alerts for the classifier set is greater than an alert threshold. If it is not greater, the process returns to step1002and the classifier set continues to be applied. If the number of performance alerts is greater than the threshold, the indexing unit414may propagate a change1016from the current classifier set to a best performing classifier set for the interval. According to one embodiment, the best performing classifier set for the interval is determined in a similar manner as discussed in conjunction with FIGS.12and13A-13B, except that it occurs online. In this example, a switching cost associated with the change from the current classifier set to the best performing classifier set could be lowered to propagate the change1016.

Referring now toFIG. 11, a method for dynamic load balancing according to one embodiment is described. This method relates generally to the operations performed by the dynamic load balancer418ofFIG. 4A. The method begins by monitoring1102image queries and recognition results transferred between the dispatcher402and the acquisition unit406on signal line430. The dynamic load balancer418monitors the image queries and corresponding recognition results for some pre-defined period such as a day. In particular, the actual distribution of images successfully found and in which index tables412a-nthey were found is monitored. The dynamic load balancer418generates1104load balancing control signals specifying a configuration for the working index tables412a-nof the acquisition unit406. For example, based on usage measured by the dynamic load balancer418for the prior day, expected usage can be predicted and the working index tables412a-nof the acquisition unit406loaded with content appropriately. For example, n index tables are loaded with the newspaper content for the current day while m index tables are loaded with the newspaper content of past days. Thus there are a total of n+m servers. Based on past history, the present invention t expects n/(n+m) queries will be for the newspaper of the current day. The indexing unit414of the image registration unit408then receives new images for the current day's newspaper. Based upon the generated load balancing signals generated in step1104, some (e.g., n) of the working index tables412a-nare loaded with the new images while the existing information in the working index tables412a-nare reconfigured such that they can be stored in the remaining (e.g., m=all working index tables−n) working index tables412a-nthat are not utilized to store the new images.

In one embodiment, operation of the acquisition unit406is modified or optimized to match the configuration of the working index tables412a-n. In particular, the acquisition unit406upon receiving an image query, first attempts to recognize1108the image query with recognition units410and index tables412configured with the images of the current day's newspaper. Next, the method determines1110whether recognition was successful. If so the method returns1118the result and the method is complete. If not, the method attempts to recognize1112the image query with recognition units410and index tables412configured with images of past days newspapers. Again the method determines1114whether recognition was successful. If so, the method returns1118the result and the method is complete. If not, the method returns1116a signal indicating that recognition was unsuccessful and the method is complete. While the load balancing method was described above with reference to use of a periodic division of the data for a newspaper, those skilled in the art will understand that the load-balancing method may be applied for dividing the data based on any other usage criteria and that the image data may be any type of images other than newspapers.

Referring now toFIG. 15A, a generalized version of a method for initialization and generation of the classifier is shown. The method begins by defining1502a range and sampling interval for the noise factors (e.g., focus blur, motion blur, dynamic range, etc.). This method generates1504a classifier at each point in a multidimensional space. Each classifier is then applied1506to the data set (DT). Finally, a performance of the classifier on the data set is recorded1508.

Referring now toFIG. 15B, another embodiment of the method for initialization and generation of classifiers is shown. The methodFIG. 15Bprovides an example of classifier generation where the noise is Gaussian blur σ, x motion blur and y motion blur. The method begins by defining1520the range and sampling interval for the Gaussian blur σ, x motion blur and y motion blur. For example, the Gaussian blur σ equals s0to sgby interval si; the motion blur in the x direction, dx, equals dx0to dxxby interval dxi; and the motion blur in the y direction, dy, equals dy0to dyyby interval dyi. Next the method applies1522the Gaussian blur σ, x motion blur and y motion blur to a pristine image set (P) to produce image set P′. For example, for each pristine object image p in the pristine image set P, this step applies Gaussian blur σ, s0to sgfor each interval si, x motion blur dx0to dxxfor each interval dxiand y motion blur dy0to dyyby interval dyi, and adds the resulting images to image set P′. Next, the method generates1524a classifier from P′. For example, the method generates a classifier C for sigma, dx, dyfor a point in a multidimensional space. The method then applies the classifier C sigma, dx, dyto recognize1526the images in training set DT. The method records1528the classifier performance including the number of images recognized, the identity of the images and an average confidence score, for example the average number of inliers for invisible junctions. Then the classifier C is added to a classifier results set (CR). Next, the method determines1530whether the classifier is the best performing and if so identifies1530the classifier as such (best classifier=(sigma, dx, dy)). For example, the classifier is the best performing if it has the highest number of images recognized and the highest average confidence score among all the classifiers tested up to this point. The method next determines1532whether there are any additional classifiers. In other words, the method determines whether there are any points in the multi-dimensional space of possible values for Gaussian blur, x motion blur and y motion blur for which a classifier has not been generated. If so, the method returns to step1522and generates a classifier for one of those points and repeats steps1524to step1532. On the other hand, if there are no additional classifiers to be generated the method is complete and ends.

FIG. 12is a flow diagram showing a conceptual model for classifier selection and comparison according to one embodiment of the present invention. Using result data stored in classifier performance database415, a classifier selection process1202is performed. The classifier selection process1202determines a set of classifiers for a set of image queries, and the performance data for the set of classifiers, by applying all available classifiers to the set of image queries. The selected classifier set1204is stored in the classifier performance database415, as is the associated performance data at1206. According to one embodiment, the performance data stored in classifier performance database415for each classifier includes an interval specification for a specific time range, a pointer to the image queries associated with the interval, a classifier identification, and the listed decisions for the image query, such as identity, confidence value, and run time. The performance data for the selected set1204includes the percentage of correctly identified image queries, percent rejected, and percent error produced by the classifiers, as well as over all run time and time spent in each classifier. Note that the percentages should add up to 100%. An “error” means a false positive in which an image query is incorrectly recognized. In addition, the percentage of images recognized by each classifier is produced.

Using a fixed classifier set1210, result data stored in classifier performance database415also is used for a fixed classifier analysis1208. The fixed classifier analysis1208applies a fixed set of classifiers to a set of image queries received during an interval, and outputs performance data1212associated with the fixed set of classifiers. Similar set performance data is produced for the fixed classifier analysis1208, including percent correct, percent rejected, percent error, and run times. In addition, a classifier set performance analysis1214can be performed that compares the selected classifier set1204and its performance data1206from the classifier selection process1202with the fixed classifier set1210and its performance data1212from the fixed classifier analysis1208. The classifier set performance analysis1214computes a distance measure between the respective performances of two classifier sets on the same set of image queries. This distance measure takes into account the algorithmic performance and the run times. An example classifier selection performance (CSP) distance measure is CSP distance (CS1, CS2)=WR*(Reject %1−Reject %2)+WE*(Error %1−Error %2)+WT*(Time1−Time2), where WR, WE, and WT are weights that express the significance of rejects, errors, and run time differences in comparing the two sets of classifiers. In this example, the weights can be set as desired, e.g., the weights could be set to favor a low error rate.

FIGS. 13A-13Bshow a flowchart of a method of classifier set prediction according to one embodiment of the present invention. In general, the method computes a sequence of classifier sets that should be applied during a future time interval and the times during that interval when the sets should be changed. The predictions are based on historical time intervals corresponding to the future time intervals, on the assumption that one of the historical time intervals will predict the data that will be received during the future time interval. The method could be performed on a regular interval, e.g., at the end of each day. The method begins by dividing1302a future time interval into a number of subintervals determined by a minimum sub interval width, referred to as “minimum subintervals” herein. Next, historic time interval data corresponding to a minimum subinterval is retrieved1304. One or more historic time intervals may be used. For example, a future time interval may be tomorrow, Sep. 17, 2008, and a minimum subinterval may be one hour. For the subinterval noon to 1 p.m., the historic intervals could be the same day and time last week, the same day and time last year, and the same time yesterday.

The method then determines (or selects)1306a best performing classifier set for the minimum subinterval. This determination in1306may include many substeps. First, classifier selection (1202) may be used to determine1308the best classifiers and performance data from a complete classifier set for image queries received during the historic time interval(s). In this example, a complete classifier set is all available classifiers. Then it is determined1312whether there are additional historic intervals for which to perform this determination. If not, the process proceeds toFIG. 13B. If there are additional historic intervals, the classifier selection determination1308repeats chronologically on the intervals, and once complete for the last historic interval, the best classifier set across the historic intervals is selected1314. The process then proceeds toFIG. 13B. Next, the determination is made1316whether the best classifier set for the minimum interval is different from a current (or initial) classifier set for the immediately previous minimum subinterval. If the classifier sets are different, the potential performance gain for changing from the current classifier set to the best classifier set for the minimum subinterval is calculated1318. This process1318includes a fixed classifier analysis1208and classifier set performance analysis1214according to one embodiment. First, performance data is determined1320for classifiers in the current classifier set for image queries received during the historic time interval. Next, the difference between the current classifier set performance data and the best classifier set performance data is calculated1322. Then, a determination in1324is made whether the difference exceeds a switching threshold (classifier set switch calculation1406). If the difference does not exceed the switching threshold, then the current classifier set is maintained1326. This result also holds from a determination1316that the best classifier set for the minimum interval is not different from the current classifier set. If the difference does exceed the switching threshold, the classifier set will change1328from the current classifier sent to the best classifier set for the minimum subinterval when the minimum subinterval begins. Switching cost is the time and effect on system performance of switching from one set of classifiers to another. The switching costs can be high in a large image recognition system with hundreds of servers, in which switching could require replication of large numbers of databases across many computers, and can be affected by how recently the last switch was made. Switching costs may be higher following a switch, until the throughput of the system has stabilized to a rate at least as good as before the previous switch. Finally, a determination1330is made whether this is the last minimum subinterval in the interval, or is additional subintervals exist. If it is the last minimum subinterval, the process ends. If it is not the last minimum subinterval, the method returns to step1304and the process repeats for the next minimum subinterval.

FIG. 14is a flow diagram showing an embodiment of a conceptual model for the classifier set prediction method ofFIGS. 13A-13Band performance monitoring. Using data stored in the classifier performance database415, data for historic intervals a, b, c are run through the classifier selection process1202. The results are selected classifier sets1204and performance data1206corresponding to each of the historical intervals. Next, classifier set performance analysis1214is performed pairwise on the classifier sets. The result is the best classifier set for the interval1402. This result is compared to the classifier set for the previous interval1404using the classifier set switch calculation1406to determine whether a change in classifier sets should be made.