Patent Publication Number: US-9418284-B1

Title: Method, system and computer program for locating mobile devices based on imaging

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application claims priority under 35 U.S.C. §119 of U.S. provisional patent application Ser. No. 61/977,580 filed Apr. 9, 2014, which is incorporated by reference herein. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates generally to a method, system, and computer program to generate a database including objects, or more generally, patterns of pixels, and their location using an imaging device of a mobile device. 
     The present invention also relates generally to a method, system and computer program to provide a location of a mobile device based on positional information associated with pixel patterns from a database that may be generated by the same mobile device. 
     The present invention further relates to a method, system and computer program that guides a device or a person holding a mobile device to a sought destination based partly on image analysis. A navigation technique is thus disclosed to guide a person or automated device to a destination. 
     BACKGROUND OF THE INVENTION 
     Cellular telephones, smartphones and other portable telecommunications devices often include at least one imaging device to take pictures of objects and other patterns of pixels. Images are taken upon command by the user. 
     The images can be used for a variety of different purposes. For example, U.S. Pat. No. 8,807,428 (Morgan), entitled navigation of mobile devices, describes a method for navigation of a mobile device including determining spatial information of at least one beacon detected in an image relative to the image, the image being an image of the beacon within at least part of an environment surrounding the mobile device, and determining a position of the mobile device based on the spatial information. This latter step entails encoded visual information of the beacon and at least two indicators of the beacon detectable only in a restricted wavelength image. The two indicators are located on either side of the encoded visual information. 
     U.S. Pat. No. 8,958,601 (Lin) entitled optical navigation method and device using same, describes an optical navigation method, which includes sequentially obtaining three images, choosing a main reference block in one image, comparing the main reference block and a another image by block matching comparison to determine a first motion vector, resizing the main reference block according to the first motion vector to generate an ancillary reference block having a size smaller than the main reference block, and comparing the ancillary reference block and yet another image by block matching comparison to determine a second motion vector. 
     U.S. Pat. No. 8,983,773 (Hamilton, I I et al.) entitled pictorial navigation, describes methods, systems and program products for providing pictorial information relevant to a geographic location. In the method, a characteristic relevant to a geographic location is selected, a pictorial image database is searched for images having an embedded tag associated with the characteristic, and in response to this searching, at least one image file is retrieved from the database that has an embedded tag correlated to the geographic location characteristic. A physical appearance or an attribute of the location is visually depicted. Characteristics of the at least one image file are analyzed and preferred image data is selected from the at least one image file and formatted for presentation. The formatted image data is associated with the geographic location, and presented in association with the geographic location. Associated image data may indicate a distance and direction from a geographic location. Routing system applications are enabled to present pictorial information with navigation route points. 
     SUMMARY OF THE INVENTION 
     A method for generating a database of pixel patterns with positional information using a mobile device with at least one imaging device in accordance with the invention includes obtaining at least one image using the mobile device including a common pattern of pixels and processing the at least one obtained image based on a size of the pattern of pixels in the image to derive positional information about the pattern of pixels. Each obtained image may also be processed based on angular orientation of the pattern of pixels relative to an imaging direction in which the image was obtained by the mobile device to derive positional information about the pattern of pixels. 
     When multiple images are obtained, each includes a common, stationary pattern of pixels and they are taken from different positions of the mobile device relative to the pattern of pixels. For example, the mobile device is positioned in each of the positions relative to the pattern of pixels at different times, and an image obtaining actuator on the mobile device is pressed while the mobile device is in each of the different positions. A panoramic camera may be attached to the mobile device and images obtained using the panoramic camera. 
     A method for determining location of a mobile device with at least one imaging device in accordance with the invention includes obtaining at least one image including a stationary pattern of pixels using the mobile device, searching through a database of pixel patterns for the obtained pattern of pixels, retrieving positional information about one of the pattern of pixels that is deemed to be a closest match to the obtained pattern of pixels and analyzing in combination with the retrieved positional information, at least one of an angle between an imaging direction in which the image including the closest match pattern of pixels was obtained by the mobile device and an imaging direction in which the at least one image was obtained, and a size differential between the closest match pattern of pixels and the pattern of pixels in the obtained at least one image to derive positional information about a location of the mobile device. That is, only the size may be analyzed to provide positional information, only the angle may be analyzed to provide positional information or both may be analyzed to provide positional information. The database may be generated as described above or may be generated in a different way to store pixel patterns and associated positional information about the location at which the image was taken. 
     The derived positional information may be provided to the mobile device in different ways, e.g., visually and/or audibly. For example, the method may entail displaying on a screen of the mobile device, indications of the location of the mobile device and surrounding structure and optionally the position of the pixel pattern used in the location determination. 
     A navigation method in accordance with the invention includes determining an initial position of a mobile device to be guided as according to any of the techniques mentioned above, and then guiding movement of the mobile device, after the initial position of the mobile device is determined, by analyzing using the processor, movement of the mobile device relative to the initial position. This method may be implemented in a system or computer program. Guiding of the movement of the mobile device may entail obtaining multiple images each including a common pattern of pixels and obtained at different times separated by movement of the mobile device and analyzing, using the processor, the images to determine relative movement of the mobile device. This image analysis to determine relative movement may be performed using known algorithms. 
     Another technique to guide movement of the mobile device entails obtaining multiple images at different times separated by movement of the mobile device and analyzing, using the processor, changes in patterns in the images to determine relative movement of the mobile device. 
     In one embodiment, the method also involves determining an accurate updated position of the mobile device to be guided as according to any of the techniques described above 7, after the movement of the mobile device has been guided by analyzing movement of the mobile device relative to the initial position, and then using this updated position, guiding movement of the mobile device, after the updated position of the mobile device is determined, by analyzing using the processor, movement of the mobile device relative to the updated position. Any processor used may be a common processor that performs all of the steps or different, co-located or physically separated processors. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention, together with further pattern of pixels and advantages thereof, may best be understood by reference to the following description taken in conjunction with the accompanying drawings, wherein like reference numerals identify like elements, and wherein: 
         FIG. 1  is a front view of a first embodiment of a mobile device in which the invention may be applied; 
         FIG. 2  is a rear view of the first embodiment of a mobile device in which the invention may be applied; 
         FIG. 3  is a perspective view of a second embodiment of a mobile device in which the invention may be applied; 
         FIG. 4  is a flow chart of a method for generating a database of positional information for pixel patterns in accordance with the invention; 
         FIG. 5  is a schematic showing the manner in which multiple images including a common, stationary pixel pattern, in this case, a picture on a wall, are obtained; 
         FIG. 6  is a flow chart of a method for using a database of positional information for pixel patterns or objects in accordance with the invention in order to provide a location of a mobile device based on imaging, and a navigation method based on the location provided; and 
         FIG. 7  is a schematic showing use of an angle to determine mobile device location. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring to the accompanying drawings wherein like reference numbers refer to the same or similar elements, the present invention is designed for use with a mobile device with at least one imaging device. As shown in  FIG. 1 , an example of a mobile device  10  is a portable communications device that includes an imaging device  12  on a front side, i.e., that side on which the screen  14  is location, as well as an imaging device  16  on a rear side (see  FIG. 2 ). Another example of a mobile device in which the invention may be applied is a drone  18  as shown in  FIG. 3  that includes an imaging device  20 . A “drone” as used herein will generally mean a pilotless flying vehicle. An example of a common drone for use with the invention is a quad-copter type of drone that may fly inside a building but for which there is no precise way to get an accurate position inside the building. The invention is not limited to the illustrated mobile device  10 , i.e., a communications device and a drone  18 , and encompasses all mobile devices that include an imaging device such as a camera. Examples include laptop computers, tablets, notepads, and the like. 
       FIG. 4  is a flow chart of a method for generating a database of pixel patterns with positional information using a mobile device with at least one imaging device. This database generation is provided as an example of the manner in which a database  22  of pixel patterns and positional information is obtained, for later use by the mobile device  10  in providing positional information based on pixel pattern analysis. Other ways to generate the database  22  are also envisioned as being within the scope and spirit of the invention. For the purposes of this application, database  22  may represent a single database or a plurality of physically separate databases. 
     Typically, for processing purposes, the pixel pattern will be assigned a digital signature, with the digital signature of multiple images being compared to determine which contain a common digital signature indicative of the same pixel pattern. 
     As a first step  24 , a set of images is obtained using the imaging device of the mobile device. This set may include only one image. Alternatively, the set may include a plurality of images taken from different positions of the mobile device relative to a common, stationary pattern of pixels. In the latter case, the set includes the common, stationary pattern of pixels in each image. 
     Obtaining the images when the set includes multiple images may involve positioning the mobile device  10  in each of the positions relative to the pattern of pixels at different times and pressing an image obtaining actuator on the mobile device  10  while the mobile device  10  is in each of the different positions. This actuator may be, as is common, a designated area of the screen  14  of the mobile device  10 . 
     As an alternative, a panoramic camera may be attached to the mobile device  10  and actuated to obtain the single image or plurality of images. 
     These images are processed in a second step  26  to derive positional information about the pixel pattern. This positional information is based on analysis of the position of the mobile device when each image was taken and the appearance of the pixel pattern in each image. Particularly, the pixel pattern is analyzed with respect to its size and/or the angle between the imaging direction and the pixel pattern to derive the positional information. 
     As an example, when a single image is taken in step  24 , the position of the pixel pattern or object in the image is known and the position of the mobile device  10  is known. As such, the angle AT between the imaging direction of the imaging device of the mobile device  10  and the object is known (see  FIG. 7 ). This imaging angle is associated with the pixel pattern, along with the size of the pixel pattern relative to the position of the mobile device  10 . 
     Referring to  FIG. 5 , three different positions of the mobile device  10  are shown, A, B and C, although images in any number of different positions including the common pixel pattern, in this case, a picture  60  on a wall, may be obtained. The image  62 A obtained of the picture  60  when the mobile device  10  is in position A shows the picture  60  to the right of the image. The image  62 B obtained of the picture  60  when the mobile device  10  is in position B shows the picture  60  in the center of the image. The image  62 C obtained of the picture  60  when the mobile device  10  is in position C shows the picture  60  to the left of the image. The angular orientation of the picture  60  is therefore different in the three images  62 A,  62 B and  62 C. In a similar manner, by moving the mobile device  10  closer and farther away from the picture, different images may be obtained with different sizes of the picture  60 . 
     A plurality of sets of images is obtained in the same manner, with each set including a common, stationary pixel pattern, usually but not required to be an object. For example, the pixel pattern may be a pattern of buildings or a number on a building. It is also possible for one or more of the sets to have only a single image and positional information derived therefrom. 
     The positional information about the pixel patterns is stored in the database  22  in association with the pixel patterns, in step  28 . The database  22  may therefore include a form of a table with pixel patterns in a searchable form and positional information to be output. 
     Once generated, the database  22  may be shared with other mobile devices in a manner known to those skilled in the art. Similarly, a database generated using another mobile device may be provided to mobile device  10  to increase the number of pixel patterns and associated positional information stored in the database  22 . 
     As for use of the database  22 , a flow chart of a method for determining location of the mobile device  10  is shown in  FIG. 6  and includes obtaining at least one image including a stationary pattern of pixels using the mobile device  10  in step  30 . In step  32 , a processor of the mobile device  10  searches through the database  22  of pixel patterns for the obtained pattern of pixels, and in step  34 , retrieving positional information about one of the pattern of pixels that is deemed to be a closest match to the obtained pattern of pixels. Algorithms to perform this closest match processing are known to those skilled in the art to which this invention pertains. 
     In step  36 , an analysis is performed to obtain, as a result, the location information about the mobile device  10 . This analysis is typically analysis of an angle between an imaging direction in which the image was obtained by the mobile device  10  and the imaging direction in which the pattern of pixels in the image containing the closest match pixel pattern, and/or analysis of a size of the pattern of pixels in the image relative to the size of the pixel pattern in the image containing the closest match pixel pattern, both considered in combination with the retrieved positional information. 
     As to the angular analysis, it may be known that the image used in the database generation phase was taken from directly in front of the pixel pattern (see position  46  in  FIG. 7 ). During the operational phase, an image is obtained from a position to the left of position  46 , i.e., from position  48 . As such, image analysis will indicate the angle α between the imaging direction, i.e., the direction in which the imaging device is pointing when taking the picture to obtain location information, and the imaging direction in which the image was taken for preparation for storage in the database. This angle can be, mathematically, applied in combination with the position of the mobile device  10  when the image was taken for preparation for storage in the database (position  46 ) in order to derive the current location of the mobile device  10  (position  48 ). That is, position  48  is a function of position  46  and angle α. 
     As to the size analysis, a similar analysis may be performed. If the size of the pixel pattern in the image taken for preparation for storage in the database when the mobile device  10  was in position  46  is known, and the size of the same pixel pattern in the image taken by the mobile device  10  in its current position  48  is determined by image analysis, then the location of the mobile device  10  when seeking its current position  48  is a function of position  46  and the size differential. 
     As an example of a use wherein the size alone is used to provide the position of the mobile device  10 , if the image currently obtained by the mobile device  10  is determined to include an object, such as a monument, and the size of the monument in the currently obtained image is determined to be half that of the size of the monument in the image from the database, then the processor of the mobile device  10  will output that the mobile device  10  is at a distance about twice that of the distance between the monument and the location of the mobile device  10  when the image was taken. A radius of this distance will be output if only one image is used. By using additional images and/or an angular analysis from one or more images, the output location of the mobile device  10  can be improved. Algorithms to perform this enhanced location output would be readily ascertainable by those skilled in the art to which this invention pertains in view of the disclosure herein. 
     The positional information to be provided may be that the mobile device  10  is at a specific distance from the pixel pattern representing an object or some other stationary object, or more general, e.g., a village, city, town, street or building where the object is located. The provided information may simply be that the mobile device  10  is situated in front of the object. A map may be displayed on a screen  14  including the location of the mobile device  10  to enable the viewer to view the screen  14  and know their position relative to indicia on the displayed map. The display on the screen  14  may also include the position of the pixel pattern being used to determine the position of the mobile device  10 . Additionally, a pointer may be used to indicate the angle between the imaging direction of the imaging device of the mobile device  10  and the pixel pattern. Identification of the pixel pattern may also be provided, if known, and associated with the pixel pattern in the database  22 . Any other use of the position of the mobile device  10  determined in the above manner is also contemplated as being within the scope of the invention. 
     The angular analysis may be performed independent of the size analysis or both in combination. Other characteristics of the images may also be used. 
     Although it is possible to provide the location of the mobile device  10  using only a single image containing a pixel pattern that is found in the database, preferably multiple images are obtained and used to provide positional information to improve the accuracy of the location determination of the mobile device  10 . To this end, the method may involve a loop to obtain and analyze additional images, see the link from step  34  to step  30 . Moreover, since it is not guaranteed that a currently obtained image will contain a pixel pattern that can be recognized as being in the database, taking multiple images increases the probability that an object in an image will be recognized. 
     Recognition of an object as being in the database may involve analysis of the images relative to the pixel patterns or digital signatures thereof and to a matching threshold. Only if the analysis determines that the pixel pattern of the currently obtained image is above the matching threshold, then the positional information about the pixel pattern will be output by the processor. 
     The methods explained with reference to  FIGS. 4 and 6  can be executed by a computer program resident in the mobile device  10 . The computer program would be designed to allow for obtaining images, ensuring that the images contain a common pixel pattern to enable derivation of positional information for storage in the database, management of the database and then subsequent use of the database upon receipt of an image with a pixel pattern. 
     The computer program is operable in two different modes. The first mode would be the database generation mode or training phase, explained with reference to  FIG. 4 . This database generation mode is independent of the second mode, i.e., the database use mode explained with reference to  FIG. 6 , and vice versa. The database use mode may use the database generated in accordance with the flow chart in  FIG. 4  or with any other database however generated that includes pixel patterns or objects for example, and positional information about them. A database of geo-tagged objects may be used. Indeed, it is contemplated that a computer program executing the second mode would operate with a pre-existing database, e.g., a database that can be downloaded using the Internet. 
     The second, database use mode is particularly useful when the mobile device  10 ,  18  does not receive a satellite signal from which it can derive its location, e.g., due to weather or lack of coverage. Moreover, the mobile device  10 ,  18  may be one that is not even provided with the ability to process satellite positioning signals. Yet, the mobile device  10  would still be able to determine its location based on the positioning information/pixel pattern database. 
     An important aspect of use of the invention relates to drones. As shown in  FIG. 3 , a drone  18  with an imaging device, such as a camera, and access to a database of pixel patterns and their positional information could be deployed and figure out where it is based solely on images obtained using the imaging device. One or more images would be obtained “in the field” and the drone&#39;s processor would analyze the images, determine whether a pixel pattern in any image may be considered a match to one stored in the database, and for those images with such pixel patterns, retrieve the positional information. The retrieved positional information is analyzed in combination with the angle between the imaging direction and the position of the pixel pattern relative to the center line of the image, and/or the size of the pixel pattern, to determine the location of the drone. By analyzing positional information from multiple pixel patterns, the location determination of the drone is improved. 
     In the foregoing, techniques to use images to determine position of a mobile device  10  including an imager are discussed. Generally, these techniques seek to locate a pattern of pixels that has been previously identified and contained in a database  22  of image data obtained by the imaging device of the mobile device or more likely by the imaging device of another imaging device. By extracting information about the position of an imaging device when an image containing the pattern of pixels was taken and/or the appearance of a fixed pattern of pixels in an image taken by the imaging device of the mobile device when at a known position, it is possible to provide a position of the mobile device  10 . 
     Another issue arises when the mobile device  10  moves and it is desired to quantify this movement. The movement quantification may apply after the initial position of the mobile device  10  has been determined by referring to the database  22 , or the position of the drone  18  has been determined in a similar manner. Referring to  FIG. 6 , in step  50 , after the position of the mobile device  10  has been provided, the relative movement of the mobile device  10  from its initial position is determined and used to guide or navigate the mobile device  10 , or the person holding the mobile device  10  is applicable, to a destination. 
     More specifically, in one technique, the mobile device  10  obtains images including the same identified pattern of pixels (i.e., a fixed object) and through processing based on differences between the appearance of that pattern in a previously obtained image and in the currently obtained image, can determine the relative movement of the mobile device  10 . For example, a monument may appear a fraction of the size in an image taken as the person and the mobile device  10  are walking away from the monument and this size difference can be converted through mathematical processing into an approximation of the movement of the person from the initial determined position. This technique can be used either to determine the relative movement from a known position, and thus the new position, or to confirm or validate a new position derived from a different relative movement determination technique. A map being displayed on a screen of the mobile device  10  may also be updated based on the relative movement of the person and their mobile device  10  from the initial position. 
     In another embodiment, the mobile device  10  can analyze its relative movement to the initial, known position that has been determined based on image analysis, based on optical techniques that do not require image analysis. As an example of such a technique that does not require image analysis, relative movement of the mobile device  10  can be analyzed using a technique similar to that used by an optical or laser mouse to determine the direction and magnitude of movement. Basically, an optical mouse works based on a change in patterns over a sequence of images. A digital signal processor determines how far the mouse has moved and sends the corresponding coordinates to the computer based on such changes. The same change in pattern analysis can be used by the mobile device  10  to provide an estimation of its relative movement from the initial known position. 
     Using similar techniques, it possible to guide a pedestrian to a destination by configuring their mobile device  10  to obtain an image in order to determine a known position and then guide them in a path from the known position to the destination based on analysis or determination of relative movement without requiring another image to be obtained and performing position determination based on this another image. Configuration of the mobile device  10  may entail downloading of a computer program that can perform image analysis to determine the initial position and then the subsequent relative movement analysis and then the display of the movement on a screen of the mobile device  10 . The computer program may also be configured to provide verbal or audio comments to the person to aid in their guidance to the destination. In this case, the computer program would monitor the distance and direction in which the mobile device  10  is moving and issue corrections or commands to provide for the correct path to the destination. 
     This guiding technique might be extremely useful for a museum wherein it is possible to guide a person from an entrance to the museum to a series of objects in the museum simply by initially fixing the person&#39;s position at the entrance to the museum by accessing the database  22 , and then analyzing relative movement from that position. The person is thus guided in a path to the objects using relative movement analysis techniques of their mobile device  10  by means of a processor of the mobile device and a computer program interacting with the processor. The computer program would also interact with the imaging device or other means to enable it to assess the relative movement from the known, initial position. The person could potentially enter the objects they want to see, obtain the position of those objects, and the computer program on the mobile device  10  would configure the necessary relative movement path from the starting point to the objects. 
     Another use is for a drone  18 , e.g., drone navigation inside of a building. The drone  18  would be provided with an imaging device  20  to obtain an image to fix its initial position (see  FIG. 3 ). Then, the drone  18  could be configured to analyze its relative movement from this initial position to conform to a desired path. The drone  18  can thus be guided to a destination from only a single initial position determination using images. Often, a drone  18  has a system like an optical mouse, i.e., a digital signal processor that can analyze changes in patterns over a sequence of images. 
     In both situations, it is possible to obtain an image during the course of the movement to confirm or validate the relative movement from the initial, known position, and again perform position determination using a pattern of pixels in the obtained image. This new position could then be used as the starting point for another path of movement obtained using relative movement analysis techniques. 
     The foregoing techniques may be summarized as a navigation technique wherein the first stage is a feature matching stage wherein the absolute position of the mobile device  10  is determined using image analysis, i.e., reference to the database and an attempt to find the closest match for a pattern of pixels contained in an image (consider it the position at time t). The second stage may be considered visual odometry wherein relative movement is analyzed, controlled or directed by a computer program typically resident at the mobile device  10  or drone  18  to direct the movement or correct the movement. This direction or correction may be achieved, when the mobile device is a smartphone or the like with a display and speaker, by the computer program providing oral and/or visual directions to the person holding the mobile device  10 , and/or displaying a map of the person&#39;s movement relative to the desired movement from the initial known position. The position of the moving mobile device is considered the position at time t+1 second, t+2 seconds, etc. 
     Visual odometry does not rely on a pre-determined collection of patterns. Instead, it is based on motion of pixels to estimate how the camera (or the device to which the camera is attached or housed within) is moving. There is often a drift that accumulates overtime with the visual odometry. Hence, the resetting of the position using the image feature extraction technique is preferably repeated periodically. It may be repeated whenever an accurate position can be obtained or at set intervals, e.g., every minute 
     In the context of this document, computer-readable medium could be any means that can contain, store, communicate, propagate or transmit a program for use by or in connection with the method, system, apparatus or device. The computer-readable medium can be, but is not limited to (not an exhaustive list), electronic, magnetic, optical, electromagnetic, infrared, or semi-conductor propagation medium. The medium can also be (not an exhaustive list) an electrical connection having one or more wires, a portable computer diskette, a random access memory (RAM), a read-only memory (ROM), an erasable, programmable, read-only memory (EPROM or Flash memory), an optical fiber, and a portable compact disk read-only memory (CDROM). The medium can also be paper or other suitable medium upon which a program is printed, as the program can be electronically captured, via for example, optical scanning of the paper or other medium, then compiled, interpreted, or otherwise processed in a suitable manner, if necessary, and then stored in a computer memory. Also, a computer program or data may be transferred to another computer-readable medium by any suitable process such as by scanning the computer-readable medium. 
     Techniques disclosed in U.S. patent application Ser. No. 11/170,337 filed Jun. 29, 2005, now U.S. Pat. No. 7,397,424, Ser. No. 11/549,703 filed Oct. 16, 2006, now U.S. Pat. No. 7,696,923, Ser. No. 12/167,649 filed Jul. 3, 2008, now U.S. Pat. No. 8,565,788, and Ser. No. 12/172,415 filed Jul. 14, 2008, may be used in combination with the inventions disclosed above. All of these applications are incorporated by reference herein. 
     While particular embodiments of the invention have been shown and described, it will be obvious to those skilled in the art that changes and modifications may be made without departing from the invention in its broader aspects, and, therefore, the aim in the appended claims is to cover all such changes and modifications as fall within the true spirit and scope of the invention.