Patent Description:
<CIT> discloses a method for estimating pose from a sequence of images including a first pair of stereo images at a first point in time and a second pair of stereo images at a second point in time.

Therefore, there is a need for an approach to providing a higher accuracy reconstruction or triangulation of a feature location from image data.

Examples of a method, apparatus, and computer program for triangulating a location of a feature from a plurality of images are disclosed. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the embodiments of the invention. It is apparent, however, to one skilled in the art that the embodiments of the invention may be practiced without these specific details or with an equivalent arrangement. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the embodiments of the invention.

<FIG> is a diagram of a system capable of triangulating a location of a feature from images, according to one embodiment. Reconstruction of a three-dimensional (3D) environment from two-dimensional (2D) image-based observations is an important function for creating digital map data. The reconstruction process, for instance, is called triangulation, and uses the same observed key point (e.g., image location of an observed object or feature) between pairs of image frames and their associated camera pose information to triangulate the 2D feature (e.g., the image location of the 2D feature) into a 3D environment, e.g., as geographic coordinates (e.g., latitude, longitude, elevation). The 3D triangulated features (e.g., feature geocoordinates) are then used to construct digital map (e.g., as stored in a geographic database <NUM>).

Generally, traditional triangulation approaches take image data (e.g., a sequence of image frames) collected by a camera sensor of a vehicle <NUM> and/or device (e.g., user equipment (UE) <NUM>) in chronological order. Because of this, in the traditional triangulation approaches the feature points (e.g., road paint, signs, poles, etc.) towards the horizon appear at the center of the images first because they are farther away and move outward from the focus-of-expansion in each subsequently collected image as the vehicle <NUM> and/or UE <NUM> move towards the features. By starting from the first chronological images of an image sequence, the same feature in earlier pairs of image frames of the sequence are usually located at the center with little change between the two images of each pair. In other words, the parallax difference between the same feature is each pair can be very small due to proximity to the image center. This, in turn, can lead to large triangulation errors because triangulation depends on parallax to translate an image or pixel location of the observed feature to a real world 3D coordinate. Other triangulation approaches, such as simultaneous localization and mapping (SLAM), also suffer from reconstruction of the 3D features if the associated features appear close to the image center, and consequently lack parallax.

This parallax problem is illustrated in the example <FIG>. As shown in <FIG>, an example image pair <NUM> includes a first image 203a collected earlier in time than a second image 203b. By way of example, the image pair <NUM> can be part of a sequence of images collected by a camera sensor of the vehicle <NUM>. The image sequences an be collected as an image stream every designated time interval (e.g., every second, <NUM> seconds, etc.) or can be a video stream (e.g., a sequence of image frames collected <NUM>, <NUM>, <NUM>, etc. times a second) to show a drive taken by the vehicle <NUM>. In this example, image 203a depicts a sign <NUM> off in the distance near the horizon and center of the image with a pixel location 207a, and image 203b depicts the same sign <NUM> at a slightly later time in the drive at pixel location 207b. Because the drive is still early in the image sequence, the parallax (e.g., difference in apparent location of the sign <NUM>) between the image locations 207a and 207b of the sign is also very small. As indicated above this can lead to large triangulation errors. In addition, because the sign <NUM> is still relatively small in both images, the pixel data representing the sign <NUM> in each image is also relatively. This small amount of pixel data can also make it more difficult for a feature detector (e.g., based on computer vision or a perception stack) to detect and identify the sign <NUM>. Failure to detect can also reduce the system <NUM>'s ability to perform triangulation with accuracy.

Accordingly, service providers face significant technical challenges to improving the accuracy of traditional approaches to feature detection and triangulation to generate accurate 3D map data from image data.

To address these technical challenges, the system <NUM> of <FIG> introduces a capability to use additional sensor data collected from the vehicle <NUM> and/or UE <NUM> (e.g., vehicle or probe trajectory data) to re-sequence the image frames so that images in which the features (e.g., a map feature <NUM>) that appear larger are processed first to triangulate their respective 3D locations. In other words, the system <NUM> provides a solution to the issue of lack of parallax between associated features <NUM> by leverage data that is available (e.g., vehicle trajectory data) to indicate a capture sequence of the images to reverse the chronological order of the images. For example, the system <NUM> runs the vehicle trajectory in reverse to correspondingly reverse the chronological order of a sequence of images captured during a drive by the vehicle <NUM> or UE <NUM>, such that the features <NUM> present in the images appear at the edges of the image and move inward to the image center. This reverse ordering and triangulation of the image data advantageously provides for better parallax and in turn improved 3D triangulations. that are to be used for triangulation appear larger.

In one embodiment, the system <NUM> includes a mapping platform <NUM> for triangulating feature locations from images alone or in combination with a computer vision system <NUM> (e.g., a machine learning-based feature detector) according to the embodiments described herein. As shown in <FIG>, the mapping platform <NUM> includes an image data module <NUM>, a trajectory module <NUM>, a feature detection module <NUM>, and a triangulation module <NUM>. The above presented modules and components of the mapping platform <NUM> can be implemented in hardware, firmware, software, or a combination thereof. It is contemplated that the functions of these components may be combined or performed by other components of equivalent functionality. Though depicted as a separate entity in <FIG>, it is contemplated the mapping platform <NUM> may be implemented as a module of any of the components of the system <NUM>. For example, the mapping platform <NUM> can be a component of the a services platform <NUM> and/or any of the services 115a-115n (also collectively referred to as services <NUM> of the services platform <NUM>). In one embodiment, the mapping platform <NUM> and/or any of the modules <NUM>-<NUM> may be implemented as a cloud-based service, local service, native application, or combination thereof. The functions of the mapping platform <NUM> and/or these modules are discussed with respect to <FIG> and <FIG> below.

<FIG> is a flowchart of a process <NUM> for, at least, triangulating a location of a feature from a plurality of images, according to one embodiment. In various embodiments, the mapping platform <NUM> and/or any of the modules <NUM>-<NUM> may perform one or more portions of the process <NUM> and may be implemented in, for instance, a chip set including a processor and a memory as shown in <FIG>. As such, the mapping platform <NUM> and/or any of the modules <NUM>-<NUM> can provide means for accomplishing various parts of the process <NUM>, as well as means for accomplishing embodiments of other processes described herein in conjunction with other components of the system <NUM>. Although the process <NUM> is illustrated and described as a sequence of steps, its contemplated that various embodiments of the process <NUM> may be performed in any order or combination and need not include all of the illustrated steps.

In step <NUM>, the image data module <NUM> retrieves a plurality of images. The plurality of images is captured by a sensor of a vehicle (e.g., vehicle <NUM> and/or other device such as the UE <NUM>) during a drive so that the images depict features, roads, and/or other environmental features or objects encountered by the vehicle during the drive. It is noted that the any discussion of vehicle in the embodiments described herein are applicable to the vehicle <NUM>, UE <NUM>, and/or any other platform/system capable of capturing the sequence of images described herein. The sensor can be a camera sensor or other type of sensor capable of capturing or producing image data, and wherein the pose data of the camera or sensor indicates a camera position, a camera pointing direction, a camera field of view, or a combination thereof corresponding to each image. The camera sensors and/or other components of the vehicle <NUM> or UE <NUM> are configured to run perception algorithms on the data (e.g., imagery) acquired during the drive. The images can be used to detect any photo-identifiable feature contained in the images. The images can be captured by the camera sensor as still images captured every predetermined period of time or video captured.

In step <NUM>, the trajectory module <NUM> determines a trajectory of the vehicle taken during the drive. The vehicle trajectory includes data relating to the path or direction of the moving vehicle along a path during the drive. The data relating to vehicle trajectory can be available offline. The vehicle trajectory further includes data indicating that the vehicle is traveling towards the feature during the drive. The vehicle trajectory is a time-ordered sequence of location probe points determined by one or more location sensors of the vehicle. The location sensor can include a satellite-based location sensors (e.g., GPS/GNSS), inertial measurement sensors which can increase the localization accuracy by taking into account the vehicle movement, and/or any other location sensor equipped or available to the vehicle <NUM> and/or UE <NUM>. The vehicle trajectory includes probe data that provides time ordered data points, wherein each point provides a vehicle location, heading, and/or equivalent telemetry data that is time stamped. Vehicle speed can also be calculated between any two data points. The vehicle may include GPS or other satellite-based receivers to obtain geographic coordinates from satellites for determining current location and time. Further, the location can be determined by visual odometry, triangulation systems such as A-GPS, Cell of Origin, or other location extrapolation technologies.

In step <NUM>, the image data module <NUM> is configured to select at least a first image and a second image from the plurality of images. The image selection module <NUM> is further configured to arrange the first image and second image in a reverse time order based on respective image capture times determined by using the vehicle trajectory. In other words, the first image was captured at a later time and at a different location than the second image during the drive. Subsequent images will also be arranged reverse time order. In addition or alternatively, the images can be arranged according to an image size of the detected feature and/or proximity to an image edge so that the first image depicts a feature that is also present in the second image at a size that is larger or closer to an image edge than in the second image.

In step <NUM>, after detecting the feature in the first image, the feature detection module <NUM> processes the second image to detect the same feature and to associate the feature as detected in the second image with the feature previously detected in the first image. In other words, the feature detection module <NUM> identifies a feature that appears in both the first and second images. In one embodiment, the feature detection module <NUM> includes or interacts with the computer vision system <NUM> to recognize and detect features (e.g., road paint, signs, poles, and/or any other photo-identifiable feature) across multiple images using a trained machine learning model (e.g., a neural network, support vector machine, decision trees, etc.). As described previously, the images are arranged so that a first image size of the feature in the first image appears larger than a second image size of the feature in the second image. This is due to the fact that the vehicle is closer to the feature in the first image and the vehicle is further away from the feature in the second image and subsequent images. This is because, in one embodiment, the camera is mounted facing forward in the direction of travel and the sequence of images has been reversed based on the vehicle trajectory. Further, in certain embodiments, the first image position of the feature in the first image is closer to an image edge than a second image position of the feature in the second image. The second image position of the feature in the second image and subsequent images moves closer to an image center. Again, this is a consequence of the reversed ordering based on the vehicle trajectory data and the forward facing camera pointing direction. The feature can be any photo-identifiable feature in the images and located at different locations in the images. In certain examples, the feature can initially appear at an image center and remain substantially at the lateral image center in subsequent images, although the feature will increase in size as the vehicle continues to approach the feature and then move towards the top edge of the image as the vehicle approaches passes underneath. This type of feature could be an overhead traffic signal or road sign that is position over the roadway. Similarly, a feature embedded in the roadway (e.g., a sewer cover) can also appear approximately at the lateral center but move towards the bottom edge of the image as the vehicle approaches and passes by.

In step <NUM>, the triangulation module <NUM> processes the detected feature in the first image and the second image to triangulate the location of the feature. The location of the feature is triangulated based on sensor pose data, such as camera pose data, for the first image and the second image, and respective image locations of the detected feature in the first image frame and the second image frame. The processing of the detected feature in the first image and the second image includes calculating a parallax value. A parallax is a displacement or difference in the apparent position of a feature viewed along two different lines of sight, and is measured by the angle or semi-angle of inclination between those two lines. A closer feature has a larger parallax than more distant features when observed from different positions, so parallax can be used to determine distances. The feature is further triangulated based on the calculated parallax value. The approach of the present invention improves the reconstruction, i.e., triangulation of a location of the feature from images and using these improved triangulated results to construct or update digital maps.

In one embodiment, it is contemplated that the embodiments of feature triangulation approach described herein can be applied across any type of feature triangulation approach. This is provided that data such as vehicle trajectory data is available to reverse the order of images with respect to their capture times, and/or that the observed feature (such as a road sign) appears in and leaves the field of view as the vehicle drives past the feature.

<FIG> illustrate a comparison between traditional triangulation (<FIG>) and the triangulation method according to the embodiments described herein (<FIG>) that provides higher accuracy triangulations where camera pose, and associated image-based observations are available. As shown in <FIG>, with traditional triangulation approaches, the feature <NUM> towards the horizon <NUM> appears closer to the center <NUM> of image i and moves outward toward the edge <NUM> of images ii and iii from the focus-of-expansion over time represented by directional arrow <NUM>. With traditional techniques, when two frames observe the same feature, the parallax due to proximity to the image center <NUM> leads to large triangulation errors. Feature association <NUM> exists between images ii and iii, however the feature association <NUM> is missing in image i due to the feature being smaller and closer to center <NUM> and therefore more difficult for the computer vision system <NUM> to detect without a prior association to other images. The feature <NUM> in <FIG> is a road sign and is initially small in image i and grows larger in size as it comes closer to the moving vehicle in images ii and iii. Feature association <NUM> fails with this traditional approach because the feature <NUM> is of small size in image i and the only feature association <NUM> occurs when the feature <NUM> is larger in images ii and iii, which leads to a small parallax and larger triangulation error.

In the example of <FIG>, images i, ii, and iii are processed in reverse time order according to the embodiments of the triangulation approach described herein. For example, the mapping platform <NUM> is used to perform the reverse time order based on available data such as vehicle trajectory data. The feature <NUM> appears larger in image iii and decreases in size in subsequent images ii and i. Feature association <NUM> therefore exists between each of images iii, ii, and i. No missing feature association is present with the present methodology that utilizes reverse time order of the captured images because the initial or baseline association is performed first on images where the feature is likely to be larger in image size and therefore easier for the computer vision system <NUM> to detect accurately. The embodiments of the triangulation approach described herein significantly improve the quality of the triangulated results by solving the problem of lack of parallax between the associated features by leveraging offline data that is available.

In the example of <FIG> the vehicle trajectory data (e.g., indicating vehicle pose data such as vehicle location and heading)and associated features are processed in reverse, such that the feature <NUM> appears at the edge <NUM> of image iii and moves further inward to the center <NUM> of images ii and i. In this way, the embodiments described herein improve parallax and in-turn improves triangulations. In the example of <FIG>, the observed feature <NUM> is represented as a road sign, but can be any photo-identifiable feature adjacent a road segment such as a light post, mileage marker, traffic light, building, monument, etc. With the reverse time order arrangement, the image with the larger feature size will be processed first.

In <FIG>, when image frames are processed in reverse order, the feature <NUM> (e.g., sign) appears large initially in image frame iii, and the feature association <NUM> between frames i, ii, and iii is successful. The feature association <NUM> can now be performed for feature <NUM> of a smaller size in image i. Since feature <NUM> in image frame iii serves as the baseline, and is much larger, the triangulation accuracy is improved. The data obtained and/or processed in the example of <FIG>, can be available offline in certain embodiments.

Returning to <FIG>, in one embodiment, the mapping platform <NUM> has connectivity over a communication network <NUM> to the services platform <NUM> that provides one or more services <NUM>. By way of example, the services <NUM> may also be other third-party services and include mapping services, navigation services, travel planning services, notification services, social networking services, content (e.g., audio, video, images, etc.) provisioning services, application services, storage services, contextual information determination services, location-based services, information-based services (e.g., weather, news, etc.), etc. In one embodiment, the services platform <NUM> uses the output of the mapping platform <NUM> (e.g., triangulated features or map data generated therefrom) to provide services such as navigation, mapping, other location-based services, etc..

In one embodiment, the mapping platform <NUM> may be a platform with multiple interconnected components and may include multiple servers, intelligent networking devices, computing devices, components and corresponding software for predicting sensor error. In addition, it is noted that the mapping platform <NUM> may be a separate entity of the system <NUM>, a part of the one or more services <NUM>, a part of the services platform <NUM>, or included within the vehicle <NUM> and/or UE <NUM> (e.g., as an application <NUM>).

In one embodiment, content providers 121a-<NUM> (collectively referred to as content providers <NUM>) may provide content or data (e.g., including geographic data based on feature triangulation, sensor data, etc.) to a geographic database <NUM>, the mapping platform <NUM>, the services platform <NUM>, the services <NUM>, and the vehicle <NUM>. The content provided may be any type of content, such as map content, textual content, audio content, video content, image content, etc. In one embodiment, the content providers <NUM> may provide content that may aid in predicting sensor error. In one embodiment, the content providers <NUM> may also store content associated with the geographic database <NUM>, mapping platform <NUM>, services platform <NUM>, services <NUM>, and/or vehicle <NUM>. In another embodiment, the content providers <NUM> may manage access to a central repository of data, and offer a consistent, standard interface to data, such as a repository of the geographic database <NUM>.

By way of example, the UE <NUM> can be any type of embedded system, mobile terminal, fixed terminal, or portable terminal including a built-in navigation system, a personal navigation device, mobile handset, station, unit, device, multimedia computer, multimedia tablet, Internet node, communicator, desktop computer, laptop computer, notebook computer, netbook computer, tablet computer, personal communication system (PCS) device, personal digital assistants (PDAs), audio/video player, digital camera/camcorder, positioning device, fitness device, television receiver, radio broadcast receiver, electronic book device, game device, or any combination thereof, including the accessories and peripherals of these devices, or any combination thereof. It is also contemplated that the UE <NUM> can support any type of interface to the user (such as "wearable" circuitry, etc.). In one embodiment, the UE <NUM> may be associated with the vehicle <NUM> or be a component part of the vehicle <NUM>.

In one embodiment, the vehicle <NUM> is configured with various sensors for generating or collecting vehicular sensor data (e.g., imagery data, vehicle trajectory data, etc.), and related geographic/map data, etc. In one embodiment, the sensed data represent sensor data associated with a geographic location or coordinates at which the sensor data was collected. In this way, the sensor data can act as observation data that can be aggregated into location-aware training and evaluation data sets. By way of example, the sensors may include a RADAR system, a LiDAR system, a global positioning sensor for gathering location data (e.g., GPS), a network detection sensor for detecting wireless signals or receivers for different short-range communications (e.g., Bluetooth, Wi-Fi, Li-Fi, near field communication (NFC) etc.), temporal information sensors, a camera/imaging sensor for gathering image data, an audio recorder for gathering audio data, velocity sensors mounted on steering wheels of the vehicles, switch sensors for determining whether one or more vehicle switches are engaged, and the like.

Other examples of sensors of the vehicle <NUM> may include light sensors, orientation sensors augmented with height sensors and acceleration sensor (e.g., an accelerometer can measure acceleration and can be used to determine orientation of the vehicle), tilt sensors to detect the degree of incline or decline of the vehicle along a path of travel, moisture sensors, pressure sensors, etc. In a further example embodiment, sensors about the perimeter of the vehicle <NUM> may detect the relative distance of the vehicle from a physical divider, a lane or roadway, the presence of other vehicles, pedestrians, traffic lights, potholes and any other objects, or a combination thereof. In one scenario, the sensors may detect weather data, traffic information, or a combination thereof. In one embodiment, the vehicle <NUM> may include GPS or other satellite-based receivers to obtain geographic coordinates from satellites for determining current location and time. Further, the location can be determined by visual odometry, triangulation systems such as A-GPS, Cell of Origin, or other location extrapolation technologies. In yet another embodiment, the sensors can determine the status of various control elements of the car, such as activation of wipers, use of a brake pedal, use of an acceleration pedal, angle of the steering wheel, activation of hazard lights, activation of head lights, etc..

In one embodiment, the communication network <NUM> of system <NUM> includes one or more networks such as a data network, a wireless network, a telephony network, or any combination thereof. It is contemplated that the data network may be any local area network (LAN), metropolitan area network (MAN), wide area network (WAN), a public data network (e.g., the Internet), short range wireless network, or any other suitable packet-switched network, such as a commercially owned, proprietary packet-switched network, e.g., a proprietary cable or fiber-optic network, and the like, or any combination thereof. In addition, the wireless network may be, for example, a cellular network and may employ various technologies including enhanced data rates for global evolution (EDGE), general packet radio service (GPRS), global system for mobile communications (GSM), Internet protocol multimedia subsystem (IMS), universal mobile telecommunications system (UMTS), etc., as well as any other suitable wireless medium, e.g., worldwide interoperability for microwave access (WiMAX), Long Term Evolution (LTE) networks, code division multiple access (CDMA), wideband code division multiple access (WCDMA), wireless fidelity (Wi-Fi), wireless LAN (WLAN), Bluetooth®, Internet Protocol (IP) data casting, satellite, mobile ad-hoc network (MANET), and the like, or any combination thereof.

By way of example, the mapping platform <NUM>, services platform <NUM>, services <NUM>, vehicle <NUM>, and/or content providers <NUM> communicate with each other and other components of the system <NUM> using well known, new or still developing protocols. In this context, a protocol includes a set of rules defining how the network nodes within the communication network <NUM> interact with each other based on information sent over the communication links. The protocols are effective at different layers of operation within each node, from generating and receiving physical signals of various types, to selecting a link for transferring those signals, to the format of information indicated by those signals, to identifying which software application executing on a computer system sends or receives the information. The conceptually different layers of protocols for exchanging information over a network are described in the Open Systems Interconnection (OSI) Reference Model.

<FIG> is a diagram of a geographic database, according to one embodiment. In one embodiment, the geographic database <NUM> includes geographic data <NUM> used for (or configured to be compiled to be used for) mapping and/or navigation-related services. In one embodiment, geographic features (e.g., two-dimensional or three-dimensional features) are represented using polygons (e.g., two-dimensional features) or polygon extrusions (e.g., three-dimensional features). For example, the edges of the polygons correspond to the boundaries or edges of the respective geographic feature. In the case of a building, a two-dimensional polygon can be used to represent a footprint of the building, and a three-dimensional polygon extrusion can be used to represent the three-dimensional surfaces of the building. It is contemplated that although various embodiments are discussed with respect to two-dimensional polygons, it is contemplated that the embodiments are also applicable to three-dimensional polygon extrusions. Accordingly, the terms polygons and polygon extrusions as used herein can be used interchangeably.

In one embodiment, the geographic database <NUM> includes high resolution or high definition (HD) mapping data that provide centimeter-level or better accuracy of map features. For example, the geographic database <NUM> can be based on Light Detection and Ranging (LiDAR) or equivalent technology to collect billions of 3D points and model road surfaces, structures, buildings, terrain, and other map features down to the number lanes and their widths. In one embodiment, the HD mapping data capture and store details such as the slope and curvature of the road, parking spots, lane markings, roadside objects such as sign posts, including what the signage denotes, etc. By way of example, the HD mapping data enable highly automated vehicles to precisely localize themselves on the road, and to determine road attributes (e.g., learned speed limit values) to at high accuracy levels.

In one embodiment, geographic features (e.g., two-dimensional or three-dimensional features) are represented using polygons (e.g., two-dimensional features) or polygon extrusions (e.g., three-dimensional features). For example, the edges of the polygons correspond to the boundaries or edges of the respective geographic feature. In the case of a building, a two-dimensional polygon can be used to represent a footprint of the building, and a three-dimensional polygon extrusion can be used to represent the three-dimensional surfaces of the building. It is contemplated that although various embodiments are discussed with respect to two-dimensional polygons, it is contemplated that the embodiments are also applicable to three-dimensional polygon extrusions. Accordingly, the terms polygons and polygon extrusions as used herein can be used interchangeably. In one embodiment, the following terminology applies to the representation of geographic features in the geographic database <NUM>.

"Node" - A point that terminates a link.

"Line segment" - A straight line connecting two points.

"Link" (or "edge") - A contiguous, non-branching string of one or more line segments terminating in a node at each end.

"Shape point" - A point along a link between two nodes (e.g., used to alter a shape of the link without defining new nodes).

"Oriented link" - A link that has a starting node (referred to as the "reference node") and an ending node (referred to as the "non-reference node").

"Simple polygon" - An interior area of an outer boundary formed by a string of oriented links that begins and ends in one node. In one embodiment, a simple polygon does not cross itself.

"Polygon" - An area bounded by an outer boundary and none or at least one interior boundary (e.g., a hole or island). In one embodiment, a polygon is constructed from one outer simple polygon and none or at least one inner simple polygon. A polygon is simple if it just consists of one simple polygon, or complex if it has at least one inner simple polygon.

In one embodiment, the geographic database <NUM> follows certain conventions. For example, links do not cross themselves and do not cross each other except at a node. Also, there are no duplicated shape points, nodes, or links. Two links that connect each other have a common node. In the geographic database <NUM>, overlapping geographic features are represented by overlapping polygons. When polygons overlap, the boundary of one polygon crosses the boundary of the other polygon. In the geographic database <NUM>, the location at which the boundary of one polygon intersects they boundary of another polygon is represented by a node. In one embodiment, a node may be used to represent other locations along the boundary of a polygon than a location at which the boundary of the polygon intersects the boundary of another polygon. In one embodiment, a shape point is not used to represent a point at which the boundary of a polygon intersects the boundary of another polygon.

As shown, the geographic database <NUM> includes node data records <NUM>, road segment or link data records <NUM>, POI data records <NUM>, triangulation data records <NUM>, other records <NUM>, and indexes <NUM>, for example. More, fewer or different data records can be provided. In one embodiment, additional data records (not shown) can include cartographic ("carto") data records, routing data, and maneuver data. In one embodiment, the indexes <NUM> may improve the speed of data retrieval operations in the geographic database <NUM>. In one embodiment, the indexes <NUM> may be used to quickly locate data without having to search every row in the geographic database <NUM> every time it is accessed. For example, in one embodiment, the indexes <NUM> can be a spatial index of the polygon points associated with stored feature polygons.

In exemplary embodiments, the road segment data records <NUM> are links or segments representing roads, streets, or paths, as can be used in the calculated route or recorded route information for determination of one or more personalized routes. The node data records <NUM> are end points corresponding to the respective links or segments of the road segment data records <NUM>. The road link data records <NUM> and the node data records <NUM> represent a road network, such as used by vehicles, cars, and/or other entities. Alternatively, the geographic database <NUM> can contain path segment and node data records or other data that represent pedestrian paths or areas in addition to or instead of the vehicle road record data, for example.

The road/link segments and nodes can be associated with attributes, such as geographic coordinates, street names, address ranges, speed limits, turn restrictions at intersections, and other navigation related attributes, as well as POIs, such as gasoline stations, hotels, restaurants, museums, stadiums, offices, automobile dealerships, auto repair shops, buildings, stores, parks, etc. The geographic database <NUM> can include data about the POIs and their respective locations in the POI data records <NUM>. The geographic database <NUM> can also include data about places, such as cities, towns, or other communities, and other geographic features, such as bodies of water, mountain ranges, etc. Such place or feature data can be part of the POI data records <NUM> or can be associated with POIs or POI data records <NUM> (such as a data point used for displaying or representing a position of a city).

In one embodiment, the geographic database <NUM> can also include triangulation data records <NUM> for storing image pairs, image sequences, detected features, vehicle trajectories, triangulation results, feature associations, and/or related data generated or consumed in the embodiments described herein. In one embodiment, triangulate features can be stored as data fields of the triangulation data data records <NUM>. In one embodiment, the triangulation data records <NUM> can be associated with segments of a road link (as opposed to an entire link). It is noted that the segmentation of the road can be different than the road link structure of the geographic database <NUM>. In other words, the segments can further subdivide the links of the geographic database <NUM> into smaller segments (e.g., of uniform lengths such as <NUM>-meters). In this way, feature triangulation can be performed at a level of granularity that is independent of the granularity or at which the actual road or road network is represented in the geographic database <NUM>.

In one embodiment, the geographic database <NUM> can be maintained by the content provider <NUM> in association with the services platform <NUM> (e.g., a map developer). The map developer can collect geographic data to generate and enhance the geographic database <NUM>. There can be different ways used by the map developer to collect data. These ways can include obtaining data from other sources, such as municipalities or respective geographic authorities. In addition, the map developer can employ field personnel to travel by vehicle along roads throughout the geographic region to observe features (e.g., physical dividers, OPPO, VRU, etc.) and/or record information about them, for example. Also, remote sensing, such as aerial or satellite photography, can be used.

For example, geographic data is compiled (such as into a platform specification format (PSF) format) to organize and/or configure the data for performing navigation-related functions and/or services, such as route calculation, route guidance, map display, speed calculation, distance and travel time functions, and other functions, by a navigation device, such as by the vehicle <NUM>, for example. The navigation-related functions can correspond to vehicle navigation, pedestrian navigation, or other types of navigation. The compilation to produce the end user databases can be performed by a party or entity separate from the map developer. For example, a customer of the map developer, such as a navigation device developer or other end user device developer, can perform compilation on a received geographic database in a delivery format to produce one or more compiled navigation databases.

The processes described herein for providing feature triangulation may be advantageously implemented via software, hardware (e.g., general processor, Digital Signal Processing (DSP) chip, an Application Specific Integrated Circuit (ASIC), Field Programmable Gate Arrays (FPGAs), etc.), firmware or a combination thereof. Such exemplary hardware for performing the described functions is detailed below.

<FIG> illustrates a computer system <NUM> upon which an embodiment of the invention may be implemented. Computer system <NUM> is programmed (e.g., via computer program code or instructions) to provide feature triangulation as described herein and includes a communication mechanism such as a bus <NUM> for passing information between other internal and external components of the computer system <NUM>. Information (also called data) is represented as a physical expression of a measurable phenomenon, typically electric voltages, but including, in other embodiments, such phenomena as magnetic, electromagnetic, pressure, chemical, biological, molecular, atomic, sub-atomic and quantum interactions. For example, north and south magnetic fields, or a zero and non-zero electric voltage, represent two states (<NUM>, <NUM>) of a binary digit (bit). Other phenomena can represent digits of a higher base. A superposition of multiple simultaneous quantum states before measurement represents a quantum bit (qubit). A sequence of one or more digits constitutes digital data that is used to represent a number or code for a character. In some embodiments, information called analog data is represented by a near continuum of measurable values within a particular range.

A processor <NUM> performs a set of operations on information as specified by computer program code related to providing feature triangulation. The computer program code is a set of instructions or statements providing instructions for the operation of the processor and/or the computer system to perform specified functions. The code, for example, may be written in a computer programming language that is compiled into a native instruction set of the processor. The code may also be written directly using the native instruction set (e.g., machine language). The set of operations include bringing information in from the bus <NUM> and placing information on the bus <NUM>. The set of operations also typically include comparing two or more units of information, shifting positions of units of information, and combining two or more units of information, such as by addition or multiplication or logical operations like OR, exclusive OR (XOR), and AND. Each operation of the set of operations that can be performed by the processor is represented to the processor by information called instructions, such as an operation code of one or more digits. A sequence of operations to be executed by the processor <NUM>, such as a sequence of operation codes, constitute processor instructions, also called computer system instructions or, simply, computer instructions. Processors may be implemented as mechanical, electrical, magnetic, optical, chemical or quantum components, among others, alone or in combination.

Computer system <NUM> also includes a memory <NUM> coupled to bus <NUM>. The memory <NUM>, such as a random access memory (RAM) or other dynamic storage device, stores information including processor instructions for providing feature triangulation. Dynamic memory allows information stored therein to be changed by the computer system <NUM>. RAM allows a unit of information stored at a location called a memory address to be stored and retrieved independently of information at neighboring addresses. The memory <NUM> is also used by the processor <NUM> to store temporary values during execution of processor instructions. The computer system <NUM> also includes a read only memory (ROM) <NUM> or other static storage device coupled to the bus <NUM> for storing static information, including instructions, that is not changed by the computer system <NUM>. Some memory is composed of volatile storage that loses the information stored thereon when power is lost. Also coupled to bus <NUM> is a non-volatile (persistent) storage device <NUM>, such as a magnetic disk, optical disk or flash card, for storing information, including instructions, that persists even when the computer system <NUM> is turned off or otherwise loses power.

Information, including instructions for providing feature triangulation, is provided to the bus <NUM> for use by the processor from an external input device <NUM>, such as a keyboard containing alphanumeric keys operated by a human user, or a sensor. A sensor detects conditions in its vicinity and transforms those detections into physical expression compatible with the measurable phenomenon used to represent information in computer system <NUM>. Other external devices coupled to bus <NUM>, used primarily for interacting with humans, include a display device <NUM>, such as a cathode ray tube (CRT) or a liquid crystal display (LCD), or plasma screen or printer for presenting text or images, and a pointing device <NUM>, such as a mouse or a trackball or cursor direction keys, or motion sensor, for controlling a position of a small cursor image presented on the display <NUM> and issuing commands associated with graphical elements presented on the display <NUM>. In some embodiments, for example, in embodiments in which the computer system <NUM> performs all functions automatically without human input, one or more of external input device <NUM>, display device <NUM> and pointing device <NUM> is omitted.

Computer system <NUM> also includes one or more instances of a communications interface <NUM> coupled to bus <NUM>. Communication interface <NUM> provides a one-way or two-way communication coupling to a variety of external devices that operate with their own processors, such as printers, scanners and external disks. In general the coupling is with a network link <NUM> that is connected to a local network <NUM> to which a variety of external devices with their own processors are connected. For example, communication interface <NUM> may be a parallel port or a serial port or a universal serial bus (USB) port on a personal computer. In some embodiments, communications interface <NUM> is an integrated services digital network (ISDN) card or a digital subscriber line (DSL) card or a telephone modem that provides an information communication connection to a corresponding type of telephone line. In some embodiments, a communication interface <NUM> is a cable modem that converts signals on bus <NUM> into signals for a communication connection over a coaxial cable or into optical signals for a communication connection over a fiber optic cable. As another example, communications interface <NUM> may be a local area network (LAN) card to provide a data communication connection to a compatible LAN, such as Ethernet. For wireless links, the communications interface <NUM> sends or receives or both sends and receives electrical, acoustic or electromagnetic signals, including infrared and optical signals, that carry information streams, such as digital data. For example, in wireless handheld devices, such as mobile telephones like cell phones, the communications interface <NUM> includes a radio band electromagnetic transmitter and receiver called a radio transceiver. In certain embodiments, the communications interface <NUM> enables connection to the communication network <NUM> providing feature triangulation.

<FIG> illustrates a chip set <NUM> upon which an embodiment of the invention may be implemented. Chip set <NUM> is programmed to provide feature triangulation as described herein and includes, for instance, the processor and memory components described with respect to <FIG> incorporated in one or more physical packages (e.g., chips). By way of example, a physical package includes an arrangement of one or more materials, components, and/or wires on a structural assembly (e.g., a baseboard) to provide one or more characteristics such as physical strength, conservation of size, and/or limitation of electrical interaction. It is contemplated that in certain embodiments the chip set can be implemented in a single chip.

The processor <NUM> and accompanying components have connectivity to the memory <NUM> via the bus <NUM>. The memory <NUM> includes both dynamic memory (e.g., RAM, magnetic disk, writable optical disk, etc.) and static memory (e.g., ROM, CD-ROM, etc.) for storing executable instructions that when executed perform the inventive steps described herein to provide feature triangulation. The memory <NUM> also stores the data associated with or generated by the execution of the inventive steps.

<FIG> is a diagram of exemplary components of a mobile terminal (e.g., vehicle <NUM>, UE <NUM>, or component thereof) capable of operating in the system of <FIG>, according to one embodiment. Generally, a radio receiver is often defined in terms of front-end and back-end characteristics. The front-end of the receiver encompasses all of the Radio Frequency (RF) circuitry whereas the back-end encompasses all of the base-band processing circuitry. Pertinent internal components of the telephone include a Main Control Unit (MCU) <NUM>, a Digital Signal Processor (DSP) <NUM>, and a receiver/transmitter unit including a microphone gain control unit and a speaker gain control unit. A main display unit <NUM> provides a display to the user in support of various applications and mobile station functions that offer automatic contact matching. An audio function circuitry <NUM> includes a microphone <NUM> and microphone amplifier that amplifies the speech signal output from the microphone <NUM>. The amplified speech signal output from the microphone <NUM> is fed to a coder/decoder (CODEC) <NUM>.

The MCU <NUM> receives various signals including input signals from the keyboard <NUM>. The keyboard <NUM> and/or the MCU <NUM> in combination with other user input components (e.g., the microphone <NUM>) comprise a user interface circuitry for managing user input. The MCU <NUM> runs a user interface software to facilitate user control of at least some functions of the mobile station <NUM> to provide feature triangulation. The MCU <NUM> also delivers a display command and a switch command to the display <NUM> and to the speech output switching controller, respectively. Further, the MCU <NUM> exchanges information with the DSP <NUM> and can access an optionally incorporated SIM card <NUM> and a memory <NUM>. In addition, the MCU <NUM> executes various control functions required of the station. The DSP <NUM> may, depending upon the implementation, perform any of a variety of conventional digital processing functions on the voice signals. Additionally, DSP <NUM> determines the background noise level of the local environment from the signals detected by microphone <NUM> and sets the gain of microphone <NUM> to a level selected to compensate for the natural tendency of the user of the mobile station <NUM>.

An optionally incorporated SIM card <NUM> carries, for instance, important information, such as the cellular phone number, the carrier supplying service, subscription details, and security information. The SIM card <NUM> serves primarily to identify the mobile station <NUM> on a radio network. The card <NUM> also contains a memory for storing a personal telephone number registry, text messages, and user specific mobile station settings.

Claim 1:
A computer-implemented method for triangulating a location of a feature (<NUM>) from a sequence of images, the method comprising:
retrieving (<NUM>) the sequence of images and respective camera pose information, wherein the sequence of images is captured by a camera of a vehicle (<NUM>) during a drive;
determining (<NUM>) a vehicle trajectory of the vehicle during the drive;
characterized by
re-ordering the sequence of images by reversing a chronological order of the images based on respective image capture times determined using the vehicle trajectory;
selecting (<NUM>) a first image and a second image, subsequent to the first image, from the re-ordered sequence of images, wherein a first image size of the feature in the first image is larger than a second image size of the feature in the second image;
after detecting the feature in the first image, processing the second image to detect the feature and to associate (<NUM>) the feature as detected in the second image with the feature previously detected in the first image; and
processing the camera pose information and image locations of the detected feature in the first image and the second image to triangulate (<NUM>) the location of the feature.