Object identification method for portable devices

An object identification method for wireless portable devices for a user equipped with a portable wireless imaging device to be able to obtain information and services related to imaged objects, where the object identification is performed at least partially by a remote computational facility, and where the object identification is based on acquired images of the object. The method includes an imaging device, capable of taking one-dimensional or two dimensional images of objects; a device capable of sending the coded image through a wireless channel to remote facilities; algorithms and software for processing and analyzing the images and for extracting from them symbolic information such as digits, letters, text, symbols or icons; algorithms and software facilitating the identification of the imaged objects based on the information gathered from the image and the information available in databases; and algorithms and software for offering various information or services to the user of the imaging device based on the information gathered from the image and the information available in databases.

DETAILED DESCRIPTION OF THE PREFERRED BODIMENT Various other objects, features and attendant advantages of the present invention will become fully appreciated as the same becomes better understood when considered in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the several views. FIG. 1 is an exploded view of an embodiment of the present invention showing all the system components. Item 101 is the imaging device, as described previously. In terms of novel additions, the imaging device may contain image compression algorithms specially optimized for the task of image compression for optimal identification rather than optimal appearance. For example, for the identification of printed text/numerals. The system can convert the image into a binary black and white image for better compression, even though it makes the image less visually appealing. Potentially, the device may run specific software—e.g. code written In J2ME, to optimize the image taking operation. In item 102 the imaging operation is performed through the camera Field Of View (FOV). Part of the novelty of the invention lies in the understanding that through the remote server one can stitch several images to form the complete image required for identifying the object (see also FIG. 4 ). Item 103 represents a potential identifying mark, such as a barcode. One aspect of the novel method is that the barcode is not read using a specially designed device but rather using a general purpose imaging device. Item 104 represents another potential identifying mark, such as the printed text in a document. In the case of e.g. a newspaper, the headings or even just fragments of text in a story/advertisement could serve as identifying information. In item 105 , once the image or set of images is acquired it is transmitted through any wireless/wireline combination of data transmission paths to the remote server. The remote server could be far apart e.g. in the central office of a wireless cellular operator, or it could be a few meters away from the imaging device and connected to it by a WLAN such as Bluetooth. Item 106 is the remote server, which then proceeds to apply the described sequence of algorithms, which can be a combination of known and novel algorithms. Appendix A provides a detailed description of the algorithms for barcode detection and decoding. The processing server applies such sequences of algorithms that result in the identification of the imaged object. Item 107 is the remote server itself (or a different remote server connected to it). Server 107 can, based on the object identification information, extract information about the object from databases/public data networks such as the internet. For example, the ISBN number of a book could be used to perform an HTTP GET request to a web site such as Amazon in order to retrieve the product's price, reviews about it etc. FIG. 2 is a view of the processing flow for a sample application of the invention. Item 201 is the imaging device (as described as item 101 in FIG. 1 ). Item 202 is the image of a standard UPC barcode on a commercial product. Item 203 is the part of the image that has been extracted by either the imaging device or by the remote server and contains the information necessary for object identification. The algorithms required to implement this stage are described in Appendix A. Item 204 is the string of identifying numbers that has been extracted using algorithms such as those described in Appendix A. Item 205 is the server, which then formulates e.g. an HTTP request or a database SQL query to retrieve more information about the product—e.g. price, availability, qualities, rating, limitations on sale etc. Item 206 is the target device. The retrieved information is then reformatted for display on the screen of the target device—so for example graphics may be taken out or reduced in color depth or size before they are sent to the device 206 , and the binary format in which they are packaged has to be adapted to the recipient device. This can be done by the remote server or by a different entity. In item 207 the server's response may include menu options and perform activities on the display device, so the product can be bought or inquired about. Item 208 shows that the same information (or more information) can also be sent aft to other display devices such as the user's personal computer, e-mail account etc. This can enable richer interaction at a later time when the user is near a more powerful device. The content is adapted in any case to the different target devices. FIG. 3 is a view of the processing flow for another sample application of the invention. Item 301 is the imaging device (as described as item 101 in FIG. 1 ). Item 302 is the image of a part of a newspaper page. Item 303 is the image after image processing operations have been performed on it to decrease the file size and/or improve the object identification's chances. In this example the image is binarized after some local histogram equalization operations. In item 304 , the OCR engine running on the remote server identifies the part of the image containing legible text and extracts the maximum number of characters and their relative geometrical position. This information is then used, in conjunction with a database of the newspaper itself, to identify the relevant story/segment. It should be noted that for identification purposes even a very partial success in the character recognition task should be sufficient. In item 305 , again the results are reformatted and transcoded optimally to the target device—which is not necessarily the original imaging device 301 . FIG. 4 is a description of the data flow in the system according to one embodiment of the invention. Item 401 is the imaging device (as described as item 101 in FIG. 1 ). Item 402 is another potential imaging device with a line scanner rather than a two dimensional imager. Item 403 is the data transmission apparatus in cases where the image acquisition part of the device is connected to the data transmission apparatus through a cable or some special wireless connection. Item 404 is the original acquired image prior to any manipulation. Item 405 is the compressed image prior to sending, where the image compression parameters and algorithm may have been optimized for object identification purposes rather than for visual appeal. Item 406 is the remote server system, which may be comprised of a series of servers where the image processing operations between these servers are distributed (either on a per image basis or on a per-request basis) for optimizing the computational resources and/or the total response time. The distribution may be performed via commercial load balancing equipment or by proprietary load balancing software. Items 407 and 408 are two separate images that have been acquired and can be stitched together in the remote server to form one complete image. Item 409 the image is then rotated to the right angle for OCR detection (see Appendix A for a detailed discussion of this operation), where the algorithm measures the image angle using the line pattern of the barcode. In item 410 , the part of the image containing numerals is extracted using a special algorithm (see Appendix A). In item 411 , OCR operations then take place on the remote server, where again parallel processing may take place to enable testing many more image parameter configurations or OCR fonts, or several different OCR engines may be run in parallel and the final result determined by some form of voting mechanism. In item 412 , the string of the decoded numbers (which may contain some errors) is sent for interpretation to better decide e.g. the type of the barcode (UPC,EAN, some proprietary format etc.). Some error correction algorithms may be used at this stage to utilize the inherent redundancy in the digits to correct for identification errors. Finally, in item 413 , the extracted text is sent to other computer lingual interpretation. Based on the above figures, the object identification method for wireless portable devices includes the following operations: 1. An imaging device, capable of taking one-dimensional or two-dimensional images of objects. 2. A device capable of sending the coded image through a wireless channel to remote facilities. 3. Algorithms and software for processing and analyzing the images and for extracting from them symbolic information such as digits, letters, text, symbols or icons. 4. Algorithms and software facilitating the identification of the imaged objects based on the information gathered from the image and the information available in databases. 5. Algorithms and software for offering various information or services to the user of the imaging device based on the information gathered from the image and the information available in databases. The imaging device 101 is a unit capable of acquiring images, storing and/or sending them. The wireless device is capable of sending images to remote facilities. The algorithms perform compression artifact correction, noise reduction, color corrections, geometric corrections, imager non-uniformity correction, etc., and various image processing enhancement operations to better facilitate the operation of the next stage of image understanding algorithms. The algorithms are implemented as a plurality of software objects residing on one or more computational devices. Also included are algorithms performing, among other operations, digit recognition, printed and handwritten text recognition, symbol, logo and watermark recognition, and general shape recognition. The algorithms are implemented as a plurality of software objects residing on one or more computational devices, possibly including the imaging device and/or the wireless device. Software for utilizing the information extracted in the previous computation stages for data storage, extraction and/or communication with a plurality of internal and/or external applications, such as databases, search engines, price comparison sites etc. The imaging device 101 is a unit capable of acquiring images, storing and/or sending them. The imaging device is a device capable of capturing single or multiple images or video streams and converting them to digital information. It is equipped with the proper optical and electro-optical imaging components and with computational and data storage components. The imaging device can be a digital camera, a PDA with an internal or external camera, a cellular phone with an internal or external camera, or a portable computational device (e.g. laptop, palmtop or Webpad™-like device) with an internal or external camera. The wireless device is capable of sending images to remote facilities. The wireless device is a device capable of transferring information wirelessly to remote or nearby locations. It is capable of getting the information from the imaging device for processing and transmission. It can also be capable of receiving information wirelessly or using a wired connection. It can also be capable of performing some processing operations reducing the load of sending the raw image to the remote server or even of reducing the computational load on the server by performing other image processing and image analysis operations. The wireless device can be a cellular phone, a wireless PDA, a Webpad™-like device communicating on a local wireless area network, a device communicating using infrared or acoustic energy, etc. The algorithms perform compression artifact correction, noise reduction, color corrections, geometric corrections, imager non-uniformity correction, etc., and various image processing enhancement operations to better facilitate the operation of the next stage of image understanding algorithms. The algorithms are implemented as a plurality of software objects residing on one or more computational devices. The image processing algorithms are numerical and symbolic algorithms for the manipulation of images and video streams. The algorithms perform compression artifact correction, noise reduction, color corrections, geometric corrections, imager non-uniformity correction, etc., and various image processing enhancement operations to better facilitate the operation of the next stage of image understanding algorithms. The algorithms are implemented as a plurality of software objects residing on one or more computational devices. The algorithms can be implemented as software running on a general purpose processor, DSP processor, special purpose ASIC and/or FPGA's. They can be a mixture of custom developed algorithms and libraries provided by other developers or companies. They can be arranged in any logical sequence, with potential changes in the sequence of processing or parameters governing the processing determined by image type, computational requirements or outputs from other algorithms. Another aspect of the invention is a collection of algorithms performing, among other operations, digit recognition, printed and handwritten text recognition, symbol, logo and watermark recognition, and general shape recognition. The algorithms are implemented as a plurality of software objects residing on one or more computational devices. The image processing algorithms are numerical and symbolic algorithms for the manipulation of images and video streams. The algorithms perform, among other operations, digit recognition, printed and handwritten text recognition, symbol, logo and watermark recognition, and general shape recognition. The algorithms are implemented as a plurality of software objects residing on one or more computational devices. The algorithms can be implemented as software running on a general purpose processor, DSP processor, special purpose ASIC and/or FPGA's. They can be a mixture of custom developed algorithms and libraries provided by other developers or companies. They can be arranged in any logical sequence, with potential changes in the sequence of processing or parameters governing the processing determined by image type, computational requirements or outputs from other algorithms. The algorithms may reside on a different system belonging to a different entity than the image processing algorithms or the application software. Another aspect of the invention is software for utilizing the information extracted in the previous computation stages for data storage, extraction and/or communication with a plurality of internal and/or external applications, such as databases, search engines, price comparison sites etc. The application software provides the overall functionality of the service, based on the information extracted in the previous algorithmic stages. It is software for data storage, extraction and/or communication with a plurality of internal and/or external applications, such as databases, search engines, price comparison sites etc. The application software can be implemented as code running on a general purpose processor, DSP processor, special purpose ASIC and/or FPGA's. It can be a mixture of custom developed software and libraries provided by other developers or companies. This software may reside on a different system belonging to a different entity than the rest of the system. The imaging device captures one or more images or video sequences, which are (potentially) processed on this device and then transferred to the wireless device or the wireless transmission section of the complete device. The data is then transmitted and transferred through some kind of data network or networks to servers which process the information using the above-described algorithms, and then uses the extracted information for various applications. The servers (or other connected entities) may then send information back through the network to the wireless device, or to other devices such as a personal computer or set-top box. A large portion of the processing algorithms may be reside on the portable device, and there may be a dynamically changing division of the algorithms running on the different parts of the system based on relative computational loads and desired user response times, changing imaging and wireless bandwidth conditions. The application software executing for a given image or image sequence may be determined based on the image content itself, rather than being fixed. The application software to be used may be chosen by the user based on pre-configured parameters or during the operation. The outputs of the application software may be sent back to the user through any channel. The principle of operation is that using images or image sequences or video sequences, a computer can decode the identity of the imaged object, for example a labeled product, a printed form, a page from a book or newspaper, a bill, a membership card, a receipt, a business card, a medical prescription etc. This saves the user the time and effort of inputting the object identity and/or unique information pertaining to the object such as values in numerical fields, addresses in a business card, etc. The imaging device captures images or video sequences, which are (potentially) processed on this device and then transferred to the wireless device or the wireless transmission section of the complete device. The data is then transmitted and transferred through a data network or networks to servers which process the information using the above-described algorithms, and then uses the extracted information for various applications. The servers (or other connected entities) may then send information back through the network to the wireless device, or to other devices such as a personal computer or set-top box. With respect to the above description then, it is to be realized that the optimum dimensional relationships for the parts of the invention, to include variations in size, materials, shape, form, function and manner of operation, assembly and use, are deemed readily apparent and obvious to one skilled in the art, and all equivalent relationships to those illustrated in the drawings and described in the specification are intended to be encompassed by the present invention. Therefore, the foregoing is considered as illustrative only of the principles of the invention. Further, since numerous modifications and changes will readily occur to those skilled in the art, it is not desired to limit the invention to the exact construction and operation shown and described, and accordingly, all suitable modifications and equivalents may be resorted to, falling within the scope of the invention. 
 Appendix A: Algorithms for Barcode Detection and Extraction This is a description of the algorithms relevant for utilization of an image of a barcode on the object in order to identify the object by its barcode number. The algorithm consists of 6 main steps (that will be described in details in the following paragraph): 1) Identify the barcode in the image, by recognizing regions in the image which resemble barcodes (uniformity in one axis and change in the other, etc.) regardless of the image rotation, the tilt of the image plane to the camera and the scale (to a reasonable extent). 2) Based on the above identification, recognize the dimensions, orientation and location of the barcode. 3) Extract a normalized image strip of the digits accompanying the barcode—this strip is now of constant size and is not skewed. 4) Read the digits in the extracted strip, achieving improved quality by utilizing the barcode specific information: relative location of digits, fonts, barcode checksum. 5) Combining the OCR results with a direct optical reading of the barcode's lines, using super-resolution, will further enhance accuracy of reading. 6) Invoking an application specific operation, based on the identified product id (e.g. presenting the web page for this product).