Systems and methods for optimizing pose estimation

In one embodiment, a system may access first, second, and third probability models that are respectively associated with predetermined first and second body parts and a predetermined segment connecting the first and second body parts. Each model includes probability values associated with regions in an image, with each value representing the probability of the associated region containing the associated body part or segment. The system may select a first and second region based on the first probability model and a third region based on the second probability model. Based on the third probability model, the system may compute a first probability score for regions connecting the first and third regions and a second probability score for regions connecting the second and third regions. Based on the first and second probability scores, the system may select the first region to indicate where the predetermined first body part appears in the image.

TECHNICAL FIELD

This disclosure generally relates to computer vision.

BACKGROUND

Machine learning may be used to enable machines to automatically detect and process objects appearing in images. In general, machine learning typically involves processing a training data set in accordance with a machine-learning model and updating the model based on a training algorithm so that it progressively “learns” the features in the data set that are predictive of the desired outputs. One example of a machine-learning model is a neural network, which is a network of interconnected nodes. Groups of nodes may be arranged in layers. The first layer of the network that takes in input data may be referred to as the input layer, and the last layer that outputs data from the network may be referred to as the output layer. There may be any number of internal hidden layers that map the nodes in the input layer to the nodes in the output layer. In a feed-forward neural network, the outputs of the nodes in each layer—with the exception of the output layer—are configured to feed forward into the nodes in the subsequent layer.

Machine-learning models may be trained to recognize object features that have been captured in images. Such models, however, are typically large and require many operations. While large and complex models may perform adequately on high-end computers with fast processors (e.g., multiple central processing units (“CPUs”) and/or graphics processing units (“GPUs”)) and large memories (e.g., random access memory (“RAM”) and/or cache), such models may not be operable on computing devices that have much less capable hardware resources. The problem is exacerbated further by applications that require near real-time results from the model (e.g., 10, 20, or 30 frames per second), such as augmented reality applications that dynamically adjust computer-generated components based on features detected in live video.

SUMMARY OF PARTICULAR EMBODIMENTS

Embodiments described herein relate to machine-learning models and various optimization techniques that enable computing devices with limited system resources (e.g., mobile devices such as smartphones, tablets, and laptops) to recognize objects and features of objects captured in images or videos. To enable computing devices with limited hardware resources (e.g., in terms of processing power and memory size) to perform such tasks and to do so within acceptable time constraints, embodiments described herein provide a compact machine-learning model with an architecture that is optimized for efficiency performing various image-feature recognition tasks. For example, particular embodiments are directed to real-time or near real-time detection, segmentation, and structure mapping of people captured in images or videos (e.g., satisfying a video's frame rate requirements). These real-time computer vision technologies may be used to enable a variety of mobile applications, such as dynamically replacing a video capture of a person with an avatar, detecting gestures, and performing other dynamic image processing related to particular objects (e.g., persons) appearing in the scene.

In addition, particular embodiments described herein provide an efficient method for up-sampling keypoint detections. For example, the output of a keypoint detection process for a particular joint may be in the form of a probability model (e.g., heat map) with regions (e.g., 56×56 grids resolution) that corresponding to regions in the input image. Each region may have a probability value that represents the likelihood of the joint of interest being within that region. To minimize computation time and resources, it may be desirable to limit the resolution of the probability model (e.g., limiting the number of grids). Having a low-resolution model, however, means that the size of each grid may be large, which in turn means that the estimated location of the joint of interest is less precise. To improve precision, particular embodiments first identify n number (e.g., 2 or 3) of the most likely candidate regions where the joint could be located and apply a refinement algorithm (e.g., quadrilateral interpolation) to the patch surrounding each grid (e.g., 3×3, 5×5, or 7×7 patch). The interpolation result of each patch may yield a maximum probability location that is different from any of the probability values associated with the regions in the patch. The maximum probabilities of each patch may then be compared to find the location that has the largest interpolated probability value. The coordinates of the location corresponding to the maximum interpolated probability value could be on a continuous spectrum (i.e., not discrete) and therefore could represent a much more precise location of the joint of interest.

Further embodiments described herein provide an efficient method for improving the accuracy of keypoint detections. As described above, the output of a keypoint detection process for a particular joint may be in the form of a probability model (e.g., heat map) with probability values that each represents the probability of an associated region in in the image containing the joint of interest. A probability model may identify several regions with sufficiently high probability values, making it difficult to discern which of those regions is where the joint of interest is depicted. To improve the accuracy of keypoint detection for joints, particular embodiments may generate and use probability models for bones. For example, a joint probability model for a person's left knee may include two candidate locations (e.g., locations with similarly high probability values), and a joint probability model for the person's left hip may also have two candidate locations. To choose between the candidate locations, the pose-estimation system may use a bone probability model generated for the person's left femur. In particular, for each possible pairing between the left-knee candidate locations and left-hip candidate locations, the system may use the bone probability model to compute the probability of the left femur being located between that pair of candidate locations. The resulting probability scores of the different pairs of candidate locations may be compared, and the pair with the highest score may be used as the final estimated locations of the person's left knee and left hip. In a similar manner, an overall optimization problem may be used to select the entire set of joints (e.g., all 19 joints or a subset thereof) so that the probability computations from the corresponding bone probability models are maximized.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Embodiments described herein relate to machine-learning models and various optimization techniques that enable computing devices with limited system resources (e.g., mobile devices such as smartphones, tablets, and laptops) to recognize objects and features of objects captured in images or videos. To enable computing devices with limited hardware resources (e.g., in terms of processing power and memory size) to perform such tasks and to do so within acceptable time constraints, embodiments described herein provide a compact machine-learning model with an architecture that is optimized for performing various image-process tasks efficiently. For example, particular embodiments are directed to real-time detection (including classification), segmentation, and structure (e.g., pose) mapping of people captured in images or videos.

FIG. 1Aillustrates an example of an image100with bounding boxes110and segmentation masks120. In particular embodiments, a machine-learning model is trained to process an image, such as image100, and detect particular objects of interest in the image. In the example shown, the machine-learning model is trained to recognize features of people. In particular embodiments, the machine-learning model may output a bounding box110that surrounds a detected instance of an object type, such as a person. A rectangular bounding box may be represented as four two-dimensional coordinates that indicate the four corners of the box. In particular embodiments, the machine-learning model may additionally or alternatively output a segmentation mask120that identifies the particular pixels that belong to the detected instance. For example, the segmentation mask may be represented as a two-dimensional matrix, with each matrix element corresponding to a pixel of the image and the element's value corresponding to whether the associated pixel belongs to the detected person. Although particular data representations for detected persons and segmentation information are described, this disclosure contemplates any suitable data representations of such information.

FIG. 1Billustrates an example of an image150with segmentation masks160and structural keypoint170, which may be used to represent the pose of a detected person. The segmentation mask160, similar to the mask120shown inFIG. 1A, identify the pixels that belong to a detected person. In particular embodiments, a machine-learning model may additionally or alternatively map keypoints170to the detected person's structure. The keypoints may map to the detected person's shoulders, elbows, wrists, hands, hips, knees, ankles, feet, neck, jaw bones, or any other joints or structures of interest. In particular embodiments, the machine-learning model may be trained to map 19 keypoints to a person (e.g., neck, upper spinal joint, lower spinal joint, and left and right jaw bones, cheekbones, shoulders, elbows, wrists, hips, knees, and ankles). In particular embodiments, each keypoint may be represented as a two-dimensional coordinate, and the set of keypoints may be represented as an array or vector of coordinates. For example, 19 keypoints may be represented as a vector with 38 entries, such as [x1, y1, . . . x19, y19], where each pair of (xi, yi) represents the coordinate one keypoint i. The order of each coordinate in the vector may implicitly indicate the keypoint to which the coordinate corresponds. For example, it may be predetermined that (x1, y1) corresponds to the left-shoulder keypoint, (x2, y2) corresponds to the right-shoulder keypoint, and so on. Although particular data representations for keypoints are described, this disclosure contemplates any suitable data representations of such information.

FIG. 2illustrates an example architecture of a machine-learning model200according to particular embodiments. The machine-learning model200is configured to take as input an image201or a preprocessed representation of the image, such as a three-dimensional matrix with dimensions corresponding to the image's height, width, and color channels (e.g., red, green, and blue). The machine-learning model200is configured to extract features of the image201and output an object detection indicator279(e.g., coordinates of a bounding box surrounding a person), keypoints289(e.g., representing the pose of a detected person), and/or segmentation mask299(e.g., identifying pixels that correspond to the detected person). The machine-learning model's200architecture is designed to be compact (thereby reducing storage and memory needs) and with reduced complexities (thereby reducing processing needs) so that it may produce sufficiently accurate and fast results on devices with limited resources to meet the demands of real-time applications (e.g., 10, 15, or 30 frames per second). Compared to conventional architectures, such as those based on ResNet or Feature Pyramid Networks (FPN), the architecture of the machine-learning model200is much smaller in size and could generate predictions much faster (e.g., roughly 100× faster).

In particular embodiments, the machine-learning model200includes several high-level components, including a backbone neural network, also referred to as a trunk210, a region proposal network (RPN)220, detection head230, keypoint head240, and segmentation head250. Each of these components may be configured as a neural network. Conceptually, in the architecture shown, the trunk210is configured to process an input image201and prepare a feature map (e.g., an inception of convolutional outputs) that represents the image201. The RPN220takes the feature map generated by the trunk210and outputs N number of proposed regions of interest (RoIs) that may include objects of interest, such as people, cars, or any other types of objects. The detection head230may then detect which of the N RoIs are likely to contain the object(s) of interest and output corresponding object detection indicators279, which may define a smaller region, such as a bounding box, of the image201that contains the object of interest. In particular embodiments, a bounding box may be the smallest or near smallest rectangle (or any other geometric shape(s)) that is able to fully contain the pixels of the object of interest. For the RoIs deemed to be sufficiently likely to contain the object of interest, which may be referred to as target region definitions, the keypoint head240may determine their respective keypoint mappings289and the segmentation head250may determine their respective segmentation masks299. In particular embodiments, the detection head230, keypoint head240, and segmentation head250may perform their respective operations in parallel. In other embodiments, the detection head230, keypoint head240, and segmentation head250may not perform their operations in parallel but instead adopt a multi-staged processing approach, which has the advantage of reducing computation and speeding up the overall operation. For example, the keypoint head240and segmentation head250may wait for the detection head230to identify the target region definitions corresponding to RoIs that are likely to contain the object of interest and only process those regions. Since the N number of RoIs initially proposed by the RPN220is typically much larger than the number of RoIs deemed sufficiently likely to contain the object of interest (e.g., on the order of 1000-to-1, 100-to-1, etc., depending on the image given), having such an architectural configuration could drastically reduce computations performed by the keypoint head240and segmentation head250, thereby enabling the operation to be performed on devices that lack sufficient hardware resources (e.g., mobile devices).

FIG. 3illustrates an example method for detecting objects of interests (e.g., persons) in an image and generating instance segmentation masks and keypoint masks, in accordance with particular embodiments. The method may begin at step310, where a system performing operations based on a machine-learning model may access an image or a frame of a video (e.g., as captured by a camera of the system, which may be a mobile device).

At step320, the system may generate a feature map for the image using a trunk210. In particular embodiments, the trunk210may be considered as the backbone neural network that learns to represent images holistically and is used by various downstream network branches that may be independently optimized for different applications/tasks (e.g., the RPN220, detection head230, keypoint head240, and segmentation head250). Conceptually, the trunk210is shared with each of the downstream components (e.g., RPN220, detection head230, etc.), which significantly reduces computational cost and resources needed for running the overall model.

The trunk210contains multiple convolutional layers and generates deep feature representations of the input image. In particular embodiments, the trunk210may have a compact architecture that is much smaller compared to ResNet and/or other similar architectures. In particular embodiments, the trunk210may include four (or fewer) convolution layers211,212,213,214, three (or fewer) inception modules215,217,218, and one pooling layer (e.g., max or average pooling)216. In particular embodiments, each of the convolutional layers211,212,213,214may use a kernel size of 3×3 or less. In particular, each input image to the trunk210may undergo, in order, a first convolution layer211(e.g., with 3×3 kernel or patch size, stride size of 2, and padding size of 1), a second convolution layer212(e.g., with 3×3 kernel or patch size, stride size of 2, and padding size of 2), a third convolution layer213(e.g., with 3×3 kernel or patch size and dimensionality reduction), another convolution layer214(e.g., with 3×3 kernel or patch size), a first inception module215, a max or average pooling layer216(e.g., with 3×3 patch size and stride 2), a second inception module217, and a third inception module218.

In particular embodiments, each of the inception modules215,217,218may take the result from its previous layer, perform separate convolution operations on it, and concatenate the resulting convolutions. For example, in one inception module, which may include dimension reduction operations, the result from the previous layer may undergo: (1) a 1×1 convolution, (2) a 1×1 convolution followed by a 3×3 convolution, (3) a 1×1 convolution followed by a 5×5 convolution, and/or (4) a 3×3 max pooling operation followed a 1×1 dimensionality reduction filter. The results of each may then undergo filter concatenation to generate the output of the inception module. In the embodiment described above, the convolutions performed in the inception module use kernel sizes of 5×5 or less; no 7×7 or larger convolution is used in the inception module, which helps reduce the size of the neural net. By limiting the convolution in the inception modules to 5×5 or less, the resulting convolutions and feature maps would be smaller, which in turn means less computation for the subsequent networks (including the networks associated with the downstream components, such as the RPN220, detection head230, etc. Although no 7×7 convolution is used in this particular embodiment, 7×7 convolutions may be used in other embodiments.

Referring again toFIG. 3, at step330, the system in accordance with particular embodiments may identify a plurality of RoIs in the feature map. In particular embodiments, the output of the trunk210may be provided to the RPN220, which may be trained to output proposed candidate object bounding boxes or other types of indication of potential RoIs. In particular embodiments, the candidates may have predefined scales and aspect ratios (e.g., anchor points). The N number of proposed regions of interest (RoIs) output by the RPN220may be large (e.g., in the thousands or hundreds), as the RoIs may not necessarily be limited to those that relate to the type(s) of object of interest. For example, the RoIs may include regions that correspond to trees, dogs, cars, houses, and people, even though the ultimate object of interest is people. In particular embodiments, the N RoIs from the RPN220may be processed by the detection head230to detect RoIs that correspond to the object of interest, such as people.

Referring again toFIG. 3, at step340, the system according to particular embodiments may generate, based on the feature map, a plurality of regional feature maps for the RoIs, respectively. For example, particular embodiments may extract features from the output of the trunk210for each RoI, as represented by block225inFIG. 2, to generate corresponding regional feature maps (i.e., a regional feature map is a feature map that correspond to a particular RoI). Conventionally, a technique called RoIPool may be used. RoIPool may first quantizes a floating-number RoI to the discrete granularity of the feature map. This quantized RoI may be then subdivided into spatial bins which are themselves quantized. The feature values covered by each bin may then be aggregated (usually by max pooling). Quantization may be performed, e.g., on a continuous coordinate x by computing [x/16], where 16 is a feature map stride and [.] is rounding; likewise, quantization is performed when dividing into bins (e.g., 7×7). In effect, quantizing the sampling region in this manner is conceptually similar to “snapping” the region to a uniform grid segmenting the feature map based on the stride size. For example, if an edge of a RoI is between gridlines, the corresponding edge of the actual region that is sampled may be “snapped” to the closest gridline (by rounding). These quantizations introduce misalignments between the RoI and the extracted features. While this may not impact classification, which is robust to small translations, it has a large negative effect on predicting pixel-accurate masks.

To address this, particular embodiments, referred to as RoIAlign, removes the harsh quantization of RoIPool by properly aligning the extracted features with the input. This may be accomplished by avoiding any quantization of the RoI boundaries or bins (i.e., use x/16 instead of [x/16]). Particular embodiments may use bilinear interpolation to compute the exact values of the input features at four regularly sampled locations in each RoI bin, and aggregate the result (using max or average). Through RoIAlign, the system may generate a regional feature map of a predefined dimension for each of the RoIs. Particular embodiments may sample four regular locations, in order to evaluate either max or average pooling. In fact, interpolating only a single value at each bin center (without pooling) is nearly as effective. One could also sample more than four locations per bin, which was found to give diminishing returns.

With RoIAlign, the bilinear interpolation used in the feature pooling225process is more accurate but requires more computation. In particular embodiments, the bilinear interpolation process may be optimized by precomputing the bilinear-interpolation weights at each position in the grid across batches.

Referring again toFIG. 3, at step350, the system may process the plurality of regional feature maps (e.g., generated using RoIAlign) using the detection head to detect ones that correspond to objects of interest depicted in the input image and generate corresponding target region definitions (e.g., a bounding boxes) associated with locations of the detected objects. For example, after pooling features from the output of the trunk210for each RoI, the feature pooling process225(e.g., RoIAlign) may pass the results (i.e., regional feature maps of the RoIs) to the detection head230so that it may detect which RoIs correspond to the object of interest, such as people. The detection head230may be a neural network with a set of convolution, pooling, and fully-connected layers. In particular embodiments, the detection head230may take as input the pooled features of each RoI, or its regional feature map, and perform a single inception operation for each regional feature map. For example, each regional feature map may undergo a single inception module transformation, similar to those described above (e.g., concatenating 1×1 convolution, 3×3 convolution, and 5×5 convolution results), to produce a single inception block. In particular embodiments, the inception module may perform convolutional operations using kernel sizes of 5×5 or fewer, which is different from conventional modules where 7×7 convolutional operations are performed. Compared to other ResNet-based models that use multiple inception blocks, configuring the detection head230to use a single inception block significantly reduces the machine-learning model's size and runtime.

In particular embodiments, the detection head230may be configured to process the inception block associated with a given RoI and output a bounding box and a probability that represents a likelihood of the RoI corresponding to the object of interest (e.g., corresponding to a person). In particular embodiments, the inception block may first be processed by average pooling, and the output of which may be used to generate (1) a bounding-box prediction (e.g., using a fully connected layer) that represents a region definition for the detected object (this bounding box coordinates may more precisely define the region in which the object appears), (2) a classification (e.g., using a fully connected layer), and/or (3) a probability or confidence score (e.g., using Softmax function). Based on the classification and/or probability, the detection head230may determine which of the RoIs likely correspond to the object of interest. In particular embodiments, all N RoI candidates may be sorted based on the detection classification/probability. The top M RoI, or their respective region definitions (e.g., which may be refined bounding boxes with updated coordinates that better surround the objects of interest), may be selected based on their respective score/probability of containing the objects of interest (e.g., people). The selected M region definitions may be referred to as target region definitions. In other embodiments, the RoI selection process may use non-maximal suppression (NMS) to help the selection process terminate early. Using NMS, candidate RoIs may be selected while they are being sorted, and once the desired M number of RoIs (or their corresponding region definitions) have been selected, the selection process terminates. This process, therefore, may further reduce runtime.

In particular embodiments, once the detection head230selects M target region definitions that are likely to correspond to instances of the object of interest (e.g., people), it may pass the corresponding target region definitions (e.g., the refined bounding boxes) to the keypoint head240and segmentation head250for them to generate keypoint maps289and segmentation masks299, respectively. As previously mentioned, since the M number of region definitions that correspond to people is typically a lot fewer than the N number of initially-proposed RoIs (i.e., M<<N), filtering in this manner prior to having them processed by the keypoint head240and segmentation head250significantly reduces computation.

In particular embodiments, before processing the M target region definitions using the keypoint head240and segmentation head250, corresponding regional feature maps may be generated (e.g., using RoIAlign) since the M target region definitions may have refined bounding box definitions that differ from the corresponding RoIs. Referring toFIG. 3, at step360, the system may generate, based on the target region definitions, corresponding target regional feature maps by sampling the feature map for the image. For example, at the feature pooling process235shown inFIG. 2, the system may pool features from the feature map output by the trunk210for each of the M target region definitions selected by the detection head230. The feature pooling block235may perform operations similar to those of block225(e.g., using RoIAlign), generating regional feature maps for the M target region definitions, respectively. In particular embodiments, the bilinear interpolation process may also be optimized by precomputing the bilinear-interpolation weights at each position in the grid across batches.

Referring toFIG. 3, at step370, the system may then generate a keypoint mask associated with each detected person (or other object of interest) by processing the target regional feature map using a third neural network. For example, inFIG. 2, the feature pooling process235may pass the pooled features (the target regional feature maps) to the keypoint head240so that it may, for each of the M target region definitions, detect keypoints289that map to the structure of the detected instance of the object of interest (e.g., 19 points that map to a person's joints, head, etc., which may represent the person's pose). In particular embodiments, the keypoint head240may process each input target region definition using a single inception module transformation similar to those described above (e.g., concatenating 1×1 convolution, 3×3 convolution, and 5×5 convolution results) to produce a single inception block. Compared to other ResNet-based models that use multiple inception blocks, configuring the keypoint head240to use a single inception block significantly reduces the machine-learning model's size and runtime. The inception block may then be further processed through the neural network of the keypoint head240to generate the keypoint masks.

Particular embodiments may model a keypoint's location as a one-hot mask, and the keypoint head240may be tasked with predicting K masks, one for each of K keypoint types (e.g., left shoulder, right elbow, etc.). For each of the K keypoints of an instance, the training target may be a one-hot m×m binary mask in which a single pixel is labeled as a foreground and the rest being labeled as backgrounds (in which case the foreground would correspond to the pixel location of the body part, such as neck joint, corresponding to the keypoint). During training, for each visible ground-truth keypoint, particular embodiments minimize the cross-entropy loss over an m2-way softmax output (which encourages a single point to be detected). In particular embodiments, the K keypoints may still be treated independently. In particular embodiments, the inception block may be input into a deconvolution layer and 2× bilinear upscaling, producing an output resolution of 56×56. In particular embodiments, a relatively high-resolution output (compared to masks) may be required for keypoint-level localization accuracy. In particular embodiments, the keypoint head240may output the coordinates of predicted body parts (e.g., shoulders, knees, ankles, head, etc.) along with a confidence score of the prediction. In particular embodiments, the keypoint head240may output respective keypoint masks and/or heat maps for the predetermined body parts (e.g., one keypoint mask and/or heat map for the left knee joint, another keypoint mask and/or heat map for the right knee, and so forth). Each heat map may include a matrix of values corresponding to pixels, with each value in the heat map representing a probability or confidence score that the associated pixel is where the associated body part is located.

Referring toFIG. 3, at step380, the system may additionally or alternatively generate an instance segmentation mask associated with each detected person (or other object of interest) by processing the target regional feature map using a fourth neural network. For example, the feature pooling process235shown inFIG. 2may additionally or alternatively pass the pooled features (i.e., the target regional feature maps) to the segmentation head250so that it may, for each of the M RoIs, generate a segmentation mask299that identifies which pixels correspond to the detected instance of the object of interest (e.g., a person). In particular embodiments, depending on the needs of an application using the model200, only the keypoint head240or the segmentation head250may be invoked. In particular embodiments, the keypoint head240and the segmentation head250may perform operations concurrently to generate their respective masks. In particular embodiments, the segmentation head may be configured to process each input regional feature map using a single inception module. For example, the pooled features (or regional feature map for RoIAlign) of each of the M region definitions may undergo a single inception module transformation similar to those described above (e.g., concatenating 1×1 convolution, 3×3 convolution, and 5×5 convolution results) to produce a single inception block. Compared to other ResNet-based models that use multiple inception blocks, configuring the keypoint head240to use a single inception block significantly reduces the machine-learning model's size and runtime. The inception block may then be further processed through the neural network of the segmentation head250to generate the segmentation mask.

In particular embodiments, a segmentation mask encodes a detected object's spatial layout. Thus, unlike class labels or box offsets that are inevitably collapsed into short output vectors by fully connected (fc) layers, extracting the spatial structure of masks can be addressed naturally by the pixel-to-pixel correspondence provided by convolutions. Particular embodiments may predict an m×m mask from each RoI using a fully convolutional neural network (FCN). This may allow each layer in the segmentation head250to maintain the explicit m×m object spatial layout without collapsing it into a vector representation that lacks spatial dimensions. Unlike previous methods that resort to fc layers for mask prediction, particular embodiments may require fewer parameters and may be more accurate. This pixel-to-pixel behavior may require RoI features, which themselves are small feature maps, to be well aligned to faithfully preserve the explicit per-pixel spatial correspondence. The aforementioned feature pooling process termed RoIAlign (e.g., used in the feature pooling layers225and235) may address this need.

Particular embodiments may repeat one or more steps of the process ofFIG. 3, where appropriate. Although this disclosure describes and illustrates particular steps of the process ofFIG. 3as occurring in a particular order, this disclosure contemplates any suitable steps of the process ofFIG. 3occurring in any suitable order. Moreover, although this disclosure describes and illustrates an example method for processing an image for objects of interests, including the particular steps of the process shown inFIG. 3, this disclosure contemplates any suitable process for doing so, including any suitable steps, which may include all, some, or none of the steps of the process shown inFIG. 3, where appropriate. Furthermore, although this disclosure describes and illustrates particular components, devices, or systems carrying out particular steps of the process ofFIG. 3, this disclosure contemplates any suitable combination of any suitable components, devices, or systems carrying out any suitable stages of the process ofFIG. 3.

FIG. 4illustrates an example process for training the machine-learning model in accordance with particular embodiments. In particular embodiments, a multi-stage training process may be used to train the machine-learning model, with each stage focusing on training different components of the model. The training process may begin at stage410, where the trunk model (referenced as Trunk1inFIG. 4) is pre-trained to perform a classification task. For example, the trunk may be trained to classify images into any number of categories (e.g., 100, 200 categories). The training dataset may include image samples with labeled/known categories. In particular embodiments, the training process, including the training dataset, may be similar to those used for training ResNet or other similar networks for generating feature map representations of images. This pre-training process helps the trunk model obtain initialization parameters.

At stage420, a temporary trunk (referenced as TrunktempinFIG. 4) and a temporary RPN (referenced as RPNtempinFIG. 4) may be trained together to generate a temporary functional model for generating RoI candidates, in accordance with particular embodiments. Once trained, Trunktempand RPNtempin particular embodiments are used to assist with the subsequent training process and are not themselves included in the machine-learning model200. In particular embodiments, the temporary Trunktempmay be initialized to have the same parameters as those of Trunk1from stage410. Rather than initializing Trunk1in stage410and using the result to initialize Trunktemp, one skilled in the art would recognize that the order may be switched (i.e., Trunktempmay be initialized in stage410and the initialized Trunktempmay be used to initialize Trunk1). The training dataset at stage420may include image samples. Each image sample may have a corresponding ground truth or label, which may include bounding boxes (e.g., represented by anchors) or any other suitable indicators for RoIs that contain foreground/background objects in the image sample. In particular embodiments, the RPN may be trained in the same manner as in Faster R-CNN. For example, the RPN may be trained to generate k anchors (e.g., associated with boxes of predetermined aspect ratios and sizes) for each sampling region and predict a likelihood of each anchor being background or foreground. Once trained, Trunktempand RPNtempwould be configured to process a given image and generate candidate RoIs.

In particular embodiments, at stage430, Trunk1and the various downstream heads (e.g., the detection head, keypoint head, and segmentation head), referred to as Heads1inFIG. 4. The training dataset for this stage may include image samples, each having ground truths or labels that indicate (1) known bounding boxes (or other indicator types) for object instances of interest (e.g., people) in the image for training the detection head, (2) known keypoints (e.g., represented as one-hot masks) for object instances of interest in the image for training the keypoint head, and (3) known segmentation masks for object instances of interest in the image for training the segmentation head.

In particular embodiments, each training image sample, during training, may be processed using the temporary Trunktempand RPNtemptrained in stage420to obtain the aforementioned N candidate RoIs. These N RoIs may then be used for training the Trunk1and the various Heads1. For example, based on the N RoI candidates, the detection head may be trained to select RoI candidates that are likely to contain the object of interest. For each RoI candidate, the machine-learning algorithm may use a bounding-box regressor to process the feature map associated with the RoI and its corresponding ground truth to learn to generate a refined bounding-box that frames the object of interest (e.g., person). The algorithm may also use a classifier (e.g., foreground/background classifier or object-detection classifier for persons or other objects of interest) to process the feature map associated with the RoI and its corresponding ground truth to learn to predict the object's class. In particular embodiments, for the segmentation head, a separate neural network may process the feature map associated with each RoI, generate a segmentation mask (e.g., which may be represented as a matrix or grid with binary values that indicate whether a corresponding pixel belongs to a detected instance of the object or not), compare the generated mask with a ground-truth mask (e.g., indicating the true pixels belonging to the object), and use the computed errors to update the network via backpropagation. In particular embodiments, for the keypoint head, another neural network may process the feature map associated with each RoI, generate a one-hot mask for each keypoint of interest (e.g., for the head, feet, hands, etc.), compare the generated masks with corresponding ground-truth masks (e.g., indicating the true locations of the keypoints of interest), and use the computed errors to update the network via backpropagation. In particular embodiments, the different heads may be trained in parallel.

In particular embodiments, at stage440, after Trunk1and the various Heads1of the machine-learning model have been trained in stage430, the RPN1of the model may be trained with Trunk1being fixed (i.e., the parameters of Trunk1would remain as they were after stage430and unchanged during this training stage). The training dataset at this stage may again include image samples, each having a corresponding ground truth or label, which may include bounding boxes or any other suitable indicators for RoIs appearing in the image sample. Conceptually, this training stage may refine or tailor the RPN1to propose regions that are particularly suitable for human detection.

At stage450, once RPN1has been trained, the various Heads1(e.g., detection head, keypoint head, and segmentation head) may be retrained with both Trunk1and RPN1fixed, in accordance with particular embodiments (i.e., the parameters of Trunk1and RPN1would remain as they were after stage440and unchanged during this training stage). The training dataset may be similar to the one used in stage430(e.g., each training image sample has known ground-truth bounding boxes, keypoints, and segmentation masks). The training process may also be similar to the process described with reference to stage430, but now Trunk1would be fixed and the N candidate RoIs would be generated by the trained (and fixed) Trunk1and RPN1, rather than the temporary Trunktempand RPNtemp.

Referring back toFIG. 2, once the machine-learning model200has been trained, at inference time it may be given an input image201and output corresponding bounding boxes279, keypoints289, and segmentation masks299for instances of objects of interest appearing in the image201. In particular embodiments, the trained model200may be included in applications and distributed to different devices with different system resources, including those with limited resources, such as mobile devices. Due to the compact model architecture and the various optimization techniques described herein, the model200would be capable of performing sufficiently despite the limited system resources to meet the real-time needs of the application, if applicable.

Particular embodiments may repeat one or more stages of the training process ofFIG. 4, where appropriate. Although this disclosure describes and illustrates particular stages of the training process ofFIG. 4as occurring in a particular order, this disclosure contemplates any suitable steps of the training process ofFIG. 4occurring in any suitable order. Moreover, although this disclosure describes and illustrates an example method for training the machine-learning model including the particular stages of the process shown inFIG. 4, this disclosure contemplates any suitable process for training the machine-learning model including any suitable stages, which may include all, some, or none of the stages of the process shown inFIG. 4, where appropriate. Furthermore, although this disclosure describes and illustrates particular components, devices, or systems carrying out particular stages of the process ofFIG. 4, this disclosure contemplates any suitable combination of any suitable components, devices, or systems carrying out any suitable stages of the process ofFIG. 4.

In particular embodiments, at inference time, the trained machine-learning model may be running on a mobile device with limited hardware resources. Compared with mobile CPU, running operations on mobile GPU may provide significant speed-up. Certain mobile platforms may provide third-party GPU processing engines (e.g., Qualcomm® Snapdragon™ Neural Processing Engine (SNPE)) that allow the trained machine-learning model to utilize the various computing capabilities available (e.g., CPU, GPU, DSP). Such third-party processing engines, however, may have certain limitations that would result in suboptimal runtime performance of the machine-learning model.

One issue with third-party processing engines such as SNPE is that it may only support optimized processing for three-dimensional data (hereinafter referred to as 3D tensors). As previously discussed, the RPN is trained to process a given input image and generate N candidate RoIs, and the detection head is trained to select M RoIs. Each of the RoIs may have three-dimensional feature maps (i.e., channel C, height H, and width W). As such, the model needs to process four-dimensional data. Since processing engines such as SNPE only supports three-dimensional convolution processing, one way to process the feature maps is to process the feature maps of the N RoIs (or M, depending on the stage of the inference process) iteratively, such as using a FOR-loop. The FOR-loop for performing sequential convolutions, for instance, may be as follows:for i in range (0, N−1):conv (B[i, C, W, H], K);
where B[i, C, W, H] represents the feature maps of the i-th RoI in the N RoIs and K represents the kernel or patch used in the convolution.FIG. 5Aillustrates this process by showing three RoI feature maps501,502,503undergoing convolution operations with three identical kernel instances511,512,513, respectively. In this case, the FOR-loop and the tensor splitting may be performed using the device's CPU, and the convolution is performed using the device's GPU. So in each iteration, data has to be copied between CPU memory and GPU memory, which creates significant overhead. Further, this iterative process (which also means launching the SNPE environment repeatedly), coupled with the relatively small feature maps of the RoIs, is not an efficient use of SNPE's parallel processing features (SNPE or other third-party processing engines may have optimization features for larger feature maps).

To avoid the aforementioned issues and improve performance, particular embodiments utilize a technique that transforms the 4D tensor (i.e., the feature maps of the N or M RoIs) into a single 3D tensor so that SNPE may be used to perform a single optimized convolution operation on all the feature maps.FIG. 5Billustrates an example where the N=3 three-dimensional feature maps of the RoIs501,502,503are tiled together to form one large 3D tensor550. In particular embodiments, padding data may be inserted between adjacent feature maps to prevent incorrect sampling (e.g., preventing, during convolution, the kernel being applied to two different but neighboring RoI feature maps). As illustrated inFIG. 5B, padding571may be inserted between feature map501and feature map502, and padding572may be inserted between feature map502and feature map503. In particular embodiments, the padding size may depend on the kernel560size. For example, the padding size may be equal to or larger than a dimension of the kernel560(e.g., if the kernel is 3×3, the padding may be 3 or more). In this particular tiling scenario, the resulting 3D tensor550may have the dimension C×H×(W*N+m*(N−1)), where m represents the width of the padding data. Thus, in this case, the C and H dimensions of the tensor550may remain the same relative to those of each of the regional feature maps501-503, and the W dimension of tensor550may be greater than the combined W dimensions of the regional feature maps501-503.

Particular manners of tiling may be more efficient than others, depending on how the combined tensor550is to be processed. For example, if the operation to be performed is convolution (e.g., in the initial inception module of each of the heads230,240, or250), the feature maps may be tiled in a certain dimension to improve subsequent convolution efficiency (e.g., by improving cache-access efficiency and reducing cache misses). The regional feature map of an RoI can usually be thought of as being three-dimensional, with a height size (H), a width size (W), and a channel size (C). Since the RPN220outputs N RoIs, the dimensionality of the N RoIs would be four-dimensional (i.e., H, W, C, and N). The corresponding data representation may be referred to as 4D tensors. In particular embodiments, the 4D tensors may be stored in a data structure that is organized as NCHW (i.e., the data is stored in cache-first order, or in the order of batch, channel, height, and weight). This manner of data storage may provide the detection head with efficient cache access when performing convolution. Similarly, when the segmentation head and/or keypoint head performs convolutions on the regional feature maps of the M region definitions from the detection head, the data may be stored in MCHW order. However, when it comes to the aforementioned feature pooling225/235process (e.g., RoIAlign), cache access is more efficient in NHWC or MHWC order, because it can reduce cache miss and utilize SIMD (single instruction multiple data). Thus, in particular embodiments, the feature pooling225or235process may include a step that organizes or transforms a 4D tensor into NHWC format. This order switching could speed up the feature pooling225process significantly.

FIG. 5Billustrates an example where the feature maps of the RoIs are tiled together in a row to form a single long 3D tensor550. In other words, only a single dimension is being expanded. However, the feature maps may also be tiled in any other configurations, so that two or three dimensions are expanded. To illustrates, in one example scenario, there may be N=12 feature maps. If no padding is inserted, arranging the feature maps in a row may yield a 3D tensor with the dimensions C*1×H*1×W*12. If the feature maps are arranged in a manner that expands two dimensions, the resulting 3D tensor may have the dimensions C*1×H*4×W*3. If the feature maps are arranged in a manner that expands three dimensions, the resulting 3D tensor may have the dimensions C*2×H*3×W*2.

In particular embodiments, it may be more desirable to generate a large 3D tensor with a larger aspect ratio, such as expanding in only one dimension (i.e., in a row), in order to minimize padding (which in turn minimizes the size of the resulting 3D tensor). Since padding is added between adjacent feature maps, minimizing the surface area of feature maps that are adjacent to other feature maps would result in a reduced need for padding. To illustrate, if N=4, tiling the four feature map tiles in a row may need 3*m padding (i.e., one between the first and second tiles, one between the second and third tiles, and one between the third and fourth tiles). However, if the four feature maps tiles are tiled in a 2×2 configuration, the number of paddings needed would be 4*m (i.e., one between the top-left tile and the top-right tile, one between the top-right tile and the bottom-right tile, one between the bottom-right tile and the bottom-left tile, and one between the bottom-left tile and the top-left tile). Thus, in particular embodiments, additional optimization may be gained by arranging the feature maps in a row (i.e., expanding in one dimension only).

FIG. 6illustrates an example method for optimizing convolutional operations on feature maps of RoIs. The method may begin at step610, where a computing system (e.g., a mobile device, laptop, or any other device used at inference time) may access an image of interest. The image, for example, may be a still image posted on a social network or a frame in a live video (e.g., captured in an augmented reality or virtual reality application). In particular embodiments, the system may need to obtain inference results in real-time or near real-time. For example, an augmented reality application or autonomous vehicle may need to determine the instance segmentation masks of people or vehicles captured in an image/video. The optimizations of the machine-learning model described herein enable computing devices, even those with relatively limited hardware resources (e.g., mobile phones), to generate results quickly to meet application requirements.

At step620, the system may generate a feature map that represents the image. In particular embodiments, the system may use the backbone neural network, such as the trunk210described herein, to generate the feature map. While other types of backbones (e.g., ResNet, Feature Pyramid Network, etc.) may alternatively be used, embodiments of the trunk210provide the advantage of, e.g., not requiring significant hardware resources (e.g., CPU, GPU, cache, memory, etc.) to generate feature maps within stringent timing constraints. Embodiments of the trunk enables applications running on mobile platforms, for example, to take advantage of real-time or near real-time instance detection, classification, segmentation, and/or keypoint generation.

At step630, the system may identify a regions of interest (RoIs) in the feature map. In particular embodiments, the RoIs may be identified by a region proposal network (RPN), as described herein.

At step640, the system may generate regional feature maps for the RoIs, respectively. For example, the system may use sampling methods such as RoIPool or RoIAlign to sample an RoI and generate a representative regional feature map. Each of the M regional feature maps generated may have three dimensions (e.g., corresponding to the regional feature map's height, width, and channels). In particular embodiments, the regional feature maps may have equal dimensions (e.g., same height, same width, and same channels).

At step650, the system may generate a combined regional feature map by combining the M regional feature maps into one. As described previously, the regional feature maps (or 3D tensors) may effectively be tiled together to form a larger 3D tensor. In particular embodiments, the combined regional feature map may be formed by tiling the regional feature maps in a single dimension (e.g., in a row). For example, a first dimension and a second dimension of the combined regional feature map may be equal to the first dimension and the second dimension of each of the plurality of regional feature maps, respectively, with the third dimension of the combined regional feature map being equal to or larger than (e.g., due to added paddings) a combination of the respective third dimensions of the regional feature maps (e.g., the regional feature maps may be stacked in the channel direction, resulting in the combined regional feature map retaining the same height and width as those of an individual regional feature map, but with a larger channel depth). In particular embodiments, the combined regional feature map may be formed by tiling the regional feature maps in two dimensions (e.g., 6 regional feature maps may be tiled in a 2×3 configuration). For example, if the regional feature maps are tiled in both the height and width dimensions, the resulting combined regional feature map's height and width may be larger than a single regional feature map, but its channel would remain the same. In particular embodiments, the combined regional feature map may be formed by tiling the regional feature maps in all three dimensions. In this case, the height, width, and channel of the combined regional feature map may be larger than those of a single regional feature map.

In particular embodiments, to prevent cross sampling from feature maps of different RoIs, the system may insert padding data between adjacent pairs of regional feature maps in the combined regional feature map. In particular embodiments, the size of the padding between each adjacent pair of regional feature maps may be at least as wide as a kernel size used by the one or more convolutional layers.

At step660, the system may process the combined regional feature map using one or more convolutional layers to generate another combined regional feature map. For example, the system may use a neural processing engine, such as SNPE, to perform the convolutional operations on the combined regional feature map to generate a second combined regional feature map. By combining M regional feature maps into one, the system is able to process the M maps using existing functionalities of neural processing engines, which may be configured to perform convolutional operations only on three-dimensional tensors, thereby taking full advantage of the optimizations offered by such engines.

At step670, the system may generate, for each of the RoIs, information associated with an object instance based on a portion of the second combined regional feature map (i.e., the result of the convolutional operations performed in step660) associated with that region of interest. In particular embodiments, for each RoI, the system may identify a region in the second combined regional feature map that corresponds to that RoI. That region may then be used to generate the desired output, such as information associated with an object instance in the RoI. For example, the information associated with the object instance may be an instance segmentation mask, a keypoint mask, a bounding box, or a classification.

Particular embodiments may repeat one or more steps of the process ofFIG. 6, where appropriate. Although this disclosure describes and illustrates particular steps of the process ofFIG. 6as occurring in a particular order, this disclosure contemplates any suitable steps of the process ofFIG. 6occurring in any suitable order. Moreover, although this disclosure describes and illustrates an example method for optimizing convolutional operations, including the particular steps of the process shown inFIG. 6, this disclosure contemplates any suitable process for doing so, including any suitable steps, which may include all, some, or none of the steps of the process shown inFIG. 6, where appropriate. Furthermore, although this disclosure describes and illustrates particular components, devices, or systems carrying out particular steps of the process ofFIG. 6, this disclosure contemplates any suitable combination of any suitable components, devices, or systems carrying out any suitable stages of the process ofFIG. 6.

In particular embodiments, training of the neural networks for performing convolutional operations on the combined regional feature map may similarly be based on combinations of regional feature maps that are generated during training. For example, for each training image, a training system may generate a feature map (e.g., using the aforementioned trunk), identify RoIs (e.g., using an RPN), generate regional feature maps for the RoIs (e.g., using RoIAlign), and combine the regional feature maps into a larger combined regional feature map, in a similar manner described above. The neural network that is being trained may then process the combined regional feature map to generate a second combined regional feature map. The system may then compare results based on the second combined regional feature map to the corresponding ground truths, and use the comparison results (e.g., as defined by loss functions) to update the neural network. In particular embodiments, the system may, for each RoI, identify a corresponding region in the second combined regional feature map and use it to generate an output (e.g., segmentation mask, bounding box, keypoints, etc.). Each output may then be compared with its corresponding ground truth. In particular embodiments, the ground truths may similarly be tiled to form a combined ground truth. In particular embodiments, the ground truths may have relative positions in the combined ground truth that mirror the relative positions of the corresponding regional feature maps in the combined regional feature map. For example, if the combined regional feature map includes regional feature maps A, B, and C in a row and in that order, the combined ground truth may also include corresponding ground truths A, B, and C in the same order. The error or loss of the predictions may then be computed based on a comparison between the output of the convolutional layers and the combined ground truth.

In particular embodiments, the trained machine-learning model's runtime may further be improved by selectively allocating particular operations to different types of resources. At inference time, different operations may be assigned to different types of processing resources, such as CPU and GPU. Certain segments of operations within the model's operation tree (e.g., a logical representation of the operations performed by the model) may be assigned to a specified type of processing resource that is better suited for performing that type of operation (e.g., more efficient, support the type of data, etc.). Selection of the optimal allocation may be based on benchmarking. For example, different combinations of operation segments may be allocated for processing by a device's GPU or CPU, and the resulting performance and the time needed to transfer the results to another type of processing unit (as well as any other metrics) may be used to determine how best to segment and allocate the operations. In particular embodiments, the benchmarking process may be automatically performed by automatically segmenting the operation tree in different combinations and/or allocating the segments to different computing resources in different combinations. The end performance results may then be ranked to determine which segmentation and/or allocation combination yields the best result.

As described, the machine-learning model according to particular embodiments is compact and optimized for inference-time speed. Such optimizations may, in certain circumstances, result in the accuracy of the prediction results to be less than optimal. To compensate, particular embodiments may perform post-processing to correct or adjust the model's predictions. In particular, the keypoints predictions generated by the keypoint head may be automatically corrected based on a pose model. At a high level, the pose model may learn the poses that humans are likely to make. Using the post model, the keypoints predictions generated by the keypoint head may be automatically adjusted to reflect the more likely poses that the pose model has learned.

In particular embodiments, a two-dimensional (2D) body pose may be represented by a vector S=[x0, y0, x1, y1, . . . , xN-1, yN-1,]Tthat concatenates x and y coordinates of all the keypoints. In particular embodiments, human poses may be represented by any number of keypoints (e.g., N=5, 10, 19, 30, etc.), as described above. Each (x, y) coordinate in S may be defined in an implicit coordinate system of the image. For example, the top-left corner (or any other point) of the image may be defined as the origin (0, 0) of the coordinate space and all other coordinates may be defined relative to the origin. In particular embodiments, each pose S may be normalized, via a transformation function denoted r(S), to a local coordinate system that is defined to be relative to one or more of the predetermined parts of the body represented by the pose. For example, each transformed coordinate (x′, y′) in r(S), which continues to indicate a joint location, may be defined relative to, e.g., the points corresponding to the body's head, shoulders, and/or hips (e.g., the origin (0, 0) may be defined to be the head, the midpoint between the shoulders, the midpoint between the hips, or the midpoint between the respective midpoints of the shoulders and hips). The r(S) coordinates, therefore, may be considered as a set of normalized coordinates. After a local coordinate system for the pose is defined based on its shoulders and hips, for example, a transformation matrix M between the original implicit coordinate system and the local coordinate system may be defined. In particular embodiments, r(S) may be a function that applies M to each (x, y) coordinate in S.

A morphable 2D pose representation of the pose S may be generated based on Principal Component Analysis (PCA), in accordance with particular embodiments. A PCA transformation model may be trained based a training dataset D containing t training poses S1. . . St, each of which may be a vector of concatenated coordinates of keypoints that correspond to predefined joints or other body parts. The poses in the training dataset D may all be normalized into the same local coordinate system by applying r(S) to each of S1. . . St. An average of all r(S) in the dataset D may be represented as mean pose Sm:

In particular embodiments, a new pose S(B) may be generated using the PCA model based on the following definition:
S(B)=Sm+Vk*B,
where Vkdenotes the first k eigenvectors (e.g., corresponding to the top k principal components with the most variance), Smdenotes mean pose, and B=[β0, β1, . . . , βk-1] denotes the low-dimensional representation of the pose. For a given pose S (or its normalized counterpart r(S)), the pose representation B could be computed as:
B(S)=VkT*(S−Sm)

FIGS. 7A-7Cillustrate examples of how the pose model may morph or deform when changing β0, β1, and β2of the first three components of B. One can see that the first component β0controls the leg length as shown inFIG. 7A, the second component β1controls the left-right pose as shown inFIG. 7B, and the third component β2controls the body width as shown inFIG. 7C.

In particular embodiments, to further constrain the low-dimensional space of pose representation B, a pose-representation probability model for each dimension of B may be learned based on the poses projected to the low-dimensional space. Each dimension may be modeled by a Gaussian distribution giand the pose-representation probability model of B may be defined as:
A(B)=Πgi(Bi)

In particular embodiments, the pose prediction as represented by the keypoints generated by the keypoint head of the machine-learning model may be adjusted as follows. In particular embodiments, the keypoint head may output a plurality of pose probability models H corresponding to a plurality of body parts (e.g., joints), respectively. The plurality of pose probability models may be configured for determining a probability of the associated body part being at a location in the image. For example, each pose probability model may be a heat map that indicates, for each location represented in the heat map, a probability or confidence score that the associated body part is located at that location. Given the pose probability models H, a post-processing objective may be to find a high-likelihood pose S that best fits the following formulation:
S*=arg minS{−log(Π(Hi(Si)))−log(A(VkT*(r(S)−Sm)))+α*∥S(B(r(S)))−r(S)∥2}
where Siis the i-th coordinate (xi, yi) in S that corresponds to a predetermined i-th body part (e.g., a particular joint), Hi(Si) is the confidence or likelihood of the i-th joint or body part in S being at position (xi, yi) in the image, r(S) is the pose S normalized to the local coordinate, S(B(r(S))) represents the reprojected pose of the pose representation B that lies on the underlying low-dimensional space, and α is the weight between two terms. This problem could be solved by gradient-based optimization or any other suitable optimization technique.

In particular embodiments, to speed up the process, the optimization may be approximated using a discrete approach. For each joint heat-map, the first few (e.g., one or two) local maxima may be found and used as candidates using mean shift algorithm based on the type of joints. For each combination of the candidates, the cost of the pose S may be computed as:
E=−log(Π(Hi(Si)))−log(A(VkT*(r(S)−Sm)))+α*∥S(B(r(S)))−r(S)∥2
The pose with the minimal cost may be used as the final pose.

FIG. 8illustrates an example method for generating a pose prediction based on pose probability models, such as those generated by the keypoint head described herein. The method may begin at step810, where a computing system may access a plurality of pose probability models for a plurality of predetermined parts of a body that is depicted in an image, respectively. Each of the plurality of pose probability models is configured for determining a probability of the associated predetermined part of the body being at a location in the image. As previously described, the pose probability models may be probability heat maps generated by the keypoint head.

At step820, the system may determine a candidate pose that is defined by a set of coordinates representing candidate locations of the predetermined parts of the body in the image. The candidate pose may be determined as part of the optimization process (e.g., either via a gradient-based or discrete-based approach). The candidate pose may be the aforementioned S, defined in the implicit coordinate system.

At step830, the system may determine a probability score for the candidate pose based on the plurality of pose probability models and the set of coordinates of the candidate pose. For example, the probability score may be based on Hi(Si), where the probability of each keypoint Siof the pose S is looked up in the corresponding pose probability model (e.g., a heat map) Hito determine the likelihood of that keypoint being correct. The overall probability score may then be computing by, e.g., multiplying the Hi(Si) of every i-th joint in S.

At step840, the system may generate a pose representation for the candidate pose using a transformation model (e.g., based on PCA) and the candidate pose. In particular embodiments, the transformation model may be applied to the candidate pose S (i.e., B(S)), in which the coordinate of each keypoint is defined in an implicit coordinate system. In other embodiments, the transformation model may be applied to a corresponding set of normalized coordinates defined in a local coordinate (i.e., B(r(S))). In particular embodiments, the transformation model may apply PCA eigenvectors to differences between the set of normalized coordinates (e.g., r(S)) and an aggregate representation of a plurality of sets of normalized coordinates that are associated with a plurality of poses (e.g., Sm), respectively. The resulting pose representation B may be defined in a spatial dimension that is of lower dimensionality than S or r(S).

At step850, the system may determine a second probability score for the pose representation B based on a pose-representation probability model, such as the model A described above. For example, the system may use a Gaussian distribution model, generated based on known B values for a set of training images, to determine a probability or likelihood of each individual point in B being correct. The aggregate (e.g., based on a multiplication) of the individual probabilities may then represent the probability score for the pose representation B being correct.

In particular embodiments, either in parallel with or sequential to step850, the system may further compute a reprojection error. For example, at step860, the system may reproject the pose representation B from its spatial dimension into another spatial dimension associated with the coordinate system of the pose that is represented by the pose representation. For example, if the pose representation B(r(S)) represents the normalized coordinates r(S), then the reprojection S(B(r(S))) may be from the spatial dimension of B back into the spatial dimension of r(S). Similarly, if the pose representation B(S) represents the candidate pose S, then the reprojection S(B(S)) may be from the spatial dimension of B back into the spatial dimension of S. At step870, the system may then compute a reprojection error based on the reprojected pose representation and the original coordinates represented by B (e.g., S(B(r(S)))−r(S) or S(B(S))−S).

At step880, the system may determine whether the candidate pose S satisfies one or more criteria, based on one or more of the metrics determined above in steps830,850, and870. As discussed, the criteria may be formulated as an optimization problem, where the objective is to find the S that optimizes the metrics (e.g., maximizes the probability of correctness for the candidate pose, maximizes the probability of correctness for the pose representation, and/or minimizing the reprojection error). In particular embodiments, the previous steps may be repeated iteratively until such a candidate S is determined.

At step890, the system may select the candidate pose to represent a pose of the body depicted in the image based on at least the first probability score for the candidate pose, the second probability score for the pose representation, and/or the reprojection error.

Particular embodiments may repeat one or more steps of the process ofFIG. 8, where appropriate. Although this disclosure describes and illustrates particular steps of the process ofFIG. 8as occurring in a particular order, this disclosure contemplates any suitable steps of the process ofFIG. 8occurring in any suitable order. Moreover, although this disclosure describes and illustrates an example method for selecting a pose, including the particular steps of the process shown inFIG. 8, this disclosure contemplates any suitable process for doing so, including any suitable steps, which may include all, some, or none of the steps of the process shown inFIG. 8, where appropriate. Furthermore, although this disclosure describes and illustrates particular components, devices, or systems carrying out particular steps of the process ofFIG. 8, this disclosure contemplates any suitable combination of any suitable components, devices, or systems carrying out any suitable stages of the process ofFIG. 8.

FIGS. 9A and 9Billustrate an example of how keypoints generated by the machine-learning model may be adjusted using a pose model.FIG. 9Ashows the initial results generated from the keypoint head of the machine-learning model.FIG. 9Bshows the final results after applying the post-processing pose model. The pose model effectively removes incorrect localizations (e.g., leg-crossing).

In particular embodiments, keypoint predictions may be refined using post-processing techniques to improve localization precision. Keypoint predictions, in particular embodiments, may estimate the locations of certain features of interest. In the context of body-pose estimation, for example, the features of interest may be particular joints of interest (e.g., ankles, hip joints, knees, etc.), facial features (e.g., left eye, right ear, head, mouth, etc.), or any other body parts (e.g., head, left hand, right foot, etc.). A keypoint prediction for a particular feature of interest (e.g., left knee or right hip joint) may be represented by a probability model, such as a heat map. The probability model, which may be output by the keypoint head in certain embodiments, may be generated from and correspond to an input image. The probability model may include probability values that are associated with different regions of the input image, with each probability value indicating the probability of the feature of interest being in the associated region. For example, a probability model may be a grid (e.g., 56×56) of probability values that map to a grid of regions in the image. As an example, if the probability value corresponding to the top-left region of the image is 0.67, it may mean that the system predicts a 67% probability or confidence that the body part of interest (e.g., left knee) is located within that region of the image. As such, the larger the size of each region, the less precise the localization is for the feature of interest. For example, if one image is divided into 100×100 regions and another image of the same size is divided into 10×10 regions, each region in the 100×100 regions would be much smaller than each region in the 10×10 regions (the 100×100 division is said to have relatively higher resolution than the 10×10 division). The smaller region can more precisely define the scope of where the feature of interest is located than the larger region.

While the localization precision of a higher-resolution probability model or heat map is higher, the computational resources and time needed to compute all the probability values are also higher. To minimize computation resources and time, especially for computing devices with limited resources (e.g., mobile phones), it may be desirable to limit the resolution of probability models at the expense of precision. Having a low-resolution probability model, however, means that the size of each region would be relatively larger, which in turn means that the estimated location of the joint or feature of interest is less precise.

To improve precision, particular embodiments described herein are directed to systems and methods for up-sampling a given probability model to more precisely pin-point the likely location where the feature of interest is located in the image. In particular embodiments, up-sampling may be applied to the probability values associated with all regions in the image. This may be accomplished by applying bicubic interpolation or convolution/deconvolution to the probability values. Unfortunately, such methods are computationally intensive and may not be suitable for devices with limited processing resources or applications requiring fast outputs (e.g., real-time or near real-time outputs). To address this shortcoming, other embodiments, described in further detail below, provide a much more efficient process for up-sampling a probability model. For example, for a probability model with a 56×56 resolution, the approximate speedup in accordance with such embodiments is roughly 100-times faster than the aforementioned process of applying bicubic interpolation or convolution processes to the entire probability model.

To illustrate,FIGS. 10A-10Fprovide an example of up-sampling a keypoint probability model to determine a more precise location of a keypoint of interest, in accordance with particular embodiments.FIG. 10Aillustrates an image1000depicting an object, which is the body1001of a person in this case. The image1000may be processed by a machine-learning model (e.g., the keypoint head, described above) to generate a probability model for locating a particular feature of interest, which for purposes of this example may be the left elbow. The probability model may include probability values that correspond to regions in the image.FIG. 10Billustrates an example of the image1000being divided in a grid-like manner (i.e., rectangular regions that are aligned horizontally and vertically) into 50×50 regions (e.g., regions1010a,1010b,1010c, and1010d). While this particular example illustrates the image being divided into 50×50 regions, the embodiments described herein contemplates a division of any resolution (e.g., 30×30, 56×56, 100×150, 1000×750, etc.). The region1010a, for example, may have an associated probability value of 0 in the probability model, reflecting the low likelihood of that region1010acontaining the left elbow in this particular example. The region1010bmay be associated with a much higher probability value (e.g., 0.88) since it corresponds to the right elbow. The region1010cmay be associated with an even higher probability value (e.g., 0.95) since it, in fact, contains the left elbow. The region1010dmay have a lower probability value (e.g., 0.75) since it is only close to the left elbow.

In particular embodiments, the up-sampling process may compare the probability values in the probability model to identify n number (e.g., 2, 3, 5, etc.) of candidate probability values to further examine. To ensure computational efficiency, the number n may be limited to be less than a fraction (e.g., 1/100, 1/1000, etc.) of the total number of regions (e.g., for 50×50 regions, fewer than one-hundredth, or 25, candidates may be selected).FIG. 10Cillustrates an example where 3 candidate probability values (shaded in black) are selected for further examination. For illustration purposes, the regions1010b,1010c,1010dcorresponding to the selected probability values are highlighted inFIG. 10C. In particular embodiments, the selected probability values may be selected because they have the n highest values in the probability model. In particular embodiments, the selected probability values may correspond to the n highest local maxima in the grid of probability values.

Each selected candidate probability value may be used to identify surrounding probability values. The regions corresponding to the selected candidate probability value and its surrounding probability values may be referred to as a patch.FIG. 10Dillustrates an example where 3×3 patches are identified (for clarity, the body1001of the person is omitted inFIG. 10D). For example, a first 3×3 patch1030bis defined by the region1010band its surrounding regions1020b(shaded in gray), a second 3×3 patch1030cis defined by the region1010cand its surrounding regions1020c(shaded by downward diagonals), and a third 3×3 patch1030dis defined by the region1010dand its surrounding regions1020d(shaded by upward diagonals). While in this example the patch size is 3×3, the patch size may alternatively be defined to be 5×5, 7×7, or any other suitable size.

Using the identified patches (e.g., patches1030b,1030c, and1030d), the computing system may determine precise locations within the patches that are most likely to be where the feature of interest is located.FIG. 10Eillustrates an example where the locations1040b,1040c, and1040dhave been identified as the most likely locations for the feature of interest to be within their respective patches1030b,1030c, and1030d(for clarity, the body1001of the person is omitted inFIG. 10E). Each location (e.g.,1040b) may be anywhere within its patch (e.g.,1030b), including the center region (e.g.,1010b) and the surrounding regions (e.g.,1020b). Unlike an individual region, a location is a point rather than an area, and as such, it is a much more precise prediction of where the feature of interest is located. In particular embodiments, to identify such a location within a patch, a refinement algorithm may be applied to the associated probability values. For example, quadrilateral interpolation may be applied to the probability values associated with a patch to find the probabilistic maximum within the patch on a continuous spectrum. The interpolation results of each patch may yield a probabilistic maximum that is different from any of the original probability values of the regions in the patch. As an example, the 9 probability values associated with the regions in the 3×3 patch1030b, listed row-by-row starting from the top row and in left-to-right order, may be 0.80, 0.87, 0.84, 0.82, 0.88, 0.86, 0.79, 0.83, and 0.82. Based on the probability values and their relative positions within the patch1030b, quadrilateral interpolation may be used to sample various locations within the patch1030bto find their respective interpolated probability values, which in turn may be compared to identify the maximum within the patch1030b. The illustrated location1040bmay be associated with the identified probabilistic maximum.

In particular embodiments, a final keypoint location for the feature of interest may be selected from the locations associated with the probabilistic maxima of the patches. For example, the maximum probability values computed using quadrilateral interpolation may be compared to find the one that is largest. The final keypoint location for the feature of interest may be set as the location that corresponds to the largest maximum probability value. The coordinates of the location corresponding to the maximum interpolated probability value could be on a continuous spectrum (i.e., not discrete) and therefore could represent a precise location of the feature of interest.FIG. 10Fillustrates an example of the location1040cbeing selected as the final keypoint location for the image1000. In this example, the interpolated probability values associated with locations1040b,1040c, and1040dare compared and the value associated with location1040cmay be deemed to be the largest. As such, the location1040cmay be selected as the most likely location at which the feature of interest (e.g., left elbow) appears in the image1000.

FIG. 11illustrates an example method for up-sampling a keypoint probability model in accordance with particular embodiments. At step1110, a computing system (e.g., a user's mobile device, personal computer, augmented reality device, etc.) may access a probability model associated with an image depicting a body. The probability model may be generated by a machine-learning model, such as the keypoint detection head, and may include probability values associated with regions of the image. Each probability value may represent a probability of the associated region of the image containing a predetermined body part of interest (e.g., joint, facial feature, etc.).

At step1120, the system may select a subset of the probability values based on a comparison of the probability values. For example, from 56×56 probability values, the system may select the 3 highest values or the 3 highest local maxima. As an example,FIG. 10Cillustrates the regions that correspond to the selected probability values.

At step1130, the system may identify, for each selected probability value, surrounding probability values whose associated regions surround the region associated with the selected probability value. As an example, inFIG. 10D, the region1010bis surrounded by regions1020b, and together, the region1010band surrounding regions1020bform the patch1030b.

At step1140, the system may compute, for each selected probability value, a probabilistic maximum based on the selected probability value and the surrounding probability values. For example, based on the probability values in a patch, quadrilateral interpolation may be used to find the probabilistic maximum corresponding to the maximum interpolated probability value in the patch. The probabilistic maximum may be associated with a location (e.g., a point) within the patch (i.e., the regions associated with the selected probability value and the surrounding probability values). An example of a location associated with a probabilistic maximum is shown inFIG. 10E(e.g., location1040bin patch1030b).

At step1150, the system may select, based on the probabilistic maxima, one of the locations associated with the probabilistic maxima to represent a determined location in the image that corresponds to the predetermined body part of the body (e.g., a joint of interest). For example,FIG. 10Fillustrates the location1040cbeing selected due to its associated probabilistic maximum being greater than or equal to that of any of the other locations1040band1040d. In particular embodiments, the selected locations for the different features of interest (e.g., joints) may be used to generate a keypoint mask, as described elsewhere herein.

Particular embodiments may repeat one or more steps of the process ofFIG. 11, where appropriate. Although this disclosure describes and illustrates particular steps of the process ofFIG. 11as occurring in a particular order, this disclosure contemplates any suitable steps of the process ofFIG. 11occurring in any suitable order. Moreover, although this disclosure describes and illustrates an example method for selecting a keypoint for a particular feature of interest using the particular steps of the process shown inFIG. 11, this disclosure contemplates all, some, or none of the steps of the process shown inFIG. 11, where appropriate. Furthermore, although this disclosure describes and illustrates particular components, devices, or systems carrying out particular steps of the process ofFIG. 11, this disclosure contemplates any suitable combination of any suitable components, devices, or systems carrying out any suitable stages of the process ofFIG. 11.

Further embodiments described herein are directed to improving the accuracy of keypoint detections used for estimating the body pose of a person depicted in an image. As described elsewhere herein, a machine-learning model may be trained to process an image and output keypoint detections that estimate the locations of predetermined joints of interest (e.g., ankles, hip joints, knees, structural joints, etc.). For each joint of interest, the output may be in the form of a joint probability model (e.g., a heat map) with probability values that correspond to regions (e.g., 56×56 grids) of the image. Each probability value may represent the probability of the associated region containing the joint of interest. However, in a given probability model, there may be several regions with sufficiently high probability values, making it difficult to discern which of those regions is the actual region that contains the joint of interest. This problem may be particularly prevalent in situations where the user's limbs are crossed (e.g., the depicted person's legs may be crossed, resulting in his left ankle appearing on his right side). For example, a probability model generated for detecting the left knee of a person in an image may include a probability value of 0.91 for the actual location of the left knee and a probability value of 0.92 for the person's right knee. If the final keypoint selection for the left knee is set to be the region with the largest probability value, the right knee would be incorrectly selected in this example since 0.92 is greater than 0.91.

To improve the accuracy of joint detection, particular embodiments may select a keypoint for a joint of interest based on a probability model for a connecting segment (e.g., for joints or features of a human, the connecting segments may be referred to as bone segments). For example, the machine-learning model (e.g., via the keypoint head or a separate head) may be trained to output, in addition to probability models for predetermined joints, probability models for predetermined segments that connect the joints in a pose model.FIG. 12illustrates an example pose model1200that includes a predetermined set of joints of interest (e.g.,1201-1219) and a predetermined set of segments that connect the joints (e.g.,1251-1258). For example, the illustrated predefined joints in the pose model1200includes a person's right cheekbone (or right upper jaw)1201, left cheekbone (or left upper jaw)1202, right lower jaw1203, left lower jaw1204, neck-to-head joint1205, right shoulder1206, left shoulder1207, neck-to-should joint1208, right elbow1209, left elbow1210, right wrist1211, left wrist1212, right hip bone1213, left hip bone1214, center hip bone1215, right knee1216, left knee1217, right ankle1218, and left ankle1219. The predefined joints in the pose model1200may be connected by one or more bone segments. For example, segment1251may connect the right cheekbone1201and the right lower jaw1203; segment1252may connect the right lower jaw1203and the neck-to-head joint1205; segment1253may connect the left lower jaw1204and the neck-to-head joint1205; segment1254may connect the left cheekbone1202and the left lower jaw1204; segment1255may connect the neck-to-head joint1205and the neck-to-shoulder joint1208; segment1256may connect the right shoulder1206and the neck-to-shoulder joint1208; segment1257may connect the left shoulder1207and the neck-to-shoulder joint1208; segment1258may connect the right shoulder1206and the right elbow1209; segment1259may connect the left shoulder1207and the left elbow1210; segment1260may connect the right elbow1209and the right wrist1211; segment1261may connect the left elbow1210and the left wrist1212; segment1262may connect the neck-to-shoulder joint1208and the center hip bone1215; segment1263may connect the right hip1213and the center hip bone1215; segment1264may connect the left hip1214and the center hip bone1215; segment1265may connect the right hip1213and the right knee1216; segment1266may connect the left hip1214and the left knee1217; segment1267may connect the right knee1216and the right ankle1218; and segment1268may connect the left knee1217and the left ankle1219.

A probability model (e.g., heat map) for a connecting segment, like probability models for joints, may include probability values that are each associated with a region in the image. Each of the probability values may represent the likelihood of the associated region overlapping with the connecting segment of interest. For example, a probability model for the left femur (e.g., bone segment1266) may include probability values that indicate the likely location of the left femur in the image. Similarly, another probability model may be generated for the right femur (e.g., bone segment1265), left humerus (e.g., bone segment1259), or any other predetermined segment connecting two of the predetermined joints.

Referring again toFIG. 2, particular embodiments may train the machine-learning model200to generate probability models for predetermined connecting segments (e.g., bone segments, such as the left femur, right humerus, spine, etc.). The keypoint head240, for example, may be tasked with generating the probability models for predetermined segments in addition to joints. Alternatively, a separate neural network may similarly process the pooled features (the target regional feature maps) from the feature pooling block235and generate, for each of the M target region definitions, probability models for different predetermined connecting segments of interest (e.g., one probability model for the left femur, one for the right humerus, and so on). The training target for each generated probability model (or ground truth) may be a binary mask in which a series of regions or pixels are labeled as foreground and the rest being labeled as background, with the foreground labels indicating where the connecting segment of interest (e.g., the right femur) is located. During training, particular embodiments may compare each generated prediction with the corresponding training target and, based on a loss function (e.g., softmax or other suitable functions), update the neural network to improve its predictive abilities. In particular embodiments, the training process may continue until a sufficiently large number (e.g., hundreds, thousands, tens of thousands, etc.) of training samples have been used to train the model or when the loss between the generated probability models and the training targets are sufficiently small (e.g., with an average confidence of more than 0.85, 0.92, 0.95, etc.).

In particular embodiments, the probability models for connecting segments may be used to refine the estimated position of joints. For example, a probability model for a person's left knee may include two candidate regions (e.g., regions with similarly high probability values), and a probability model for the person's left hip may also have two candidate regions. To choose between the candidate regions, the pose-estimation system may use a probability model for the person's left femur. For example, for each possible pairing between the candidate regions for the left knee and the candidate regions for the left hip, the system may use the probability model for the left femur to compute the probability of the left femur being located between each pair of candidate locations. The resulting probability scores of the different pairs of candidate locations may be compared, and the pair with the highest score may be used as the final estimated locations of the person's left knee and left hip. In a similar manner, an overall optimization problem may be solved to select the entire set of joints (e.g., all 19 joints). This may be achieved, in particular embodiments, by maximizing the entire pose's probability scores computed using the associated bone probability models.

FIGS. 13A-13Dillustrate an example of using a probability model for a bone or connecting segment to improve keypoint detection results for joints, in accordance with particular embodiments.FIG. 13Aillustrates an image1300depicting an object, which is the body1301of a person in this case. The image1300may be processed by the aforementioned machine-learning model to generate a probability model for locating a particular feature of interest, which for purposes of this example may be the right hip. The probability model may include probability values that correspond to regions in the image. The image1300is conceptually divided in a grid-like manner (i.e., rectangular regions that are aligned horizontally and vertically) into 50×50 regions (e.g., regions1310a,1310b, and1310c). While this particular example illustrates the image being divided into 50×50 regions, the embodiments described herein contemplates a division of any resolution (e.g., 30×30, 56×56, 100×150, 1000×750, etc.). The region1310a, for example, may have an associated probability value of 0 in the probability model, reflecting the low likelihood of that region1310acontaining the right hip in this particular example. In contrast, the region1310bmay be associated with a much higher probability value (e.g., 0.92) since it, in fact, corresponds to the right hip. The region1310cmay also be associated with a high probability value (e.g., 0.90) since it contains the left hip. Based on the probability values in the probability map, certain regions may be selected as candidates for the right hip (or any other feature of interest). In particular embodiments, the selected probability values may be selected because they have the n highest values in the probability model. In particular embodiments, the selected probability values may correspond to the n highest local maxima in the grid of probability values. The number n values selected may be fixed (e.g., 2, 3, 5, etc.) or based on predetermined rules (e.g., any probability value or local maxima exceeding a predetermined threshold, such as 0.9, may be selected as a candidate). In the example shown inFIG. 13A, the regions1310band1310chave been selected as candidate regions for the right hip.

FIG. 13Billustrates an example of regions of the image1300having corresponding probability values from a probability model for the right knee. Similar toFIG. 13A, the image1300shown inFIG. 13Bis conceptually divided into 50×50 regions, with each region being associated with a probability value from the probability model for the right knee. The probability value associated with each region may indicate the likelihood of that region containing the right knee. The region1320a, for example, may have an associated probability value of 0.02 in the probability model, reflecting the low likelihood of that region1320acontaining the right knee in this particular example. In contrast, the regions corresponding to the person's right knee1320band left knee1320cmay have much higher probability values (e.g., 0.97 and 0.98, respectively). Similar to how the candidate regions1310b,1310cfor the right hip are selected inFIG. 13A, the regions1320band1320cmay be selected as candidates for the right knee based on the probability values in the probability map for the right knee.

FIG. 13Cillustrates an example of regions of the image1300having corresponding probability values from a probability model for the right femur bone segment. Similar toFIGS. 13A and 13B, the image1300shown inFIG. 13Cis conceptually divided into 50×50 regions, with each region being associated with a probability value from the probability model for the right femur. The probability value associated with each region may indicate the likelihood of that region containing a portion of the right femur. The region1330a, for example, may have an associated probability value of 0.01 in the probability model, reflecting the low likelihood of that region1330acontaining the right femur in this particular example. In contrast, the regions corresponding to the person's right femur1330bmay have much higher probability values in the probability model, and other regions that do not contain the right femur may have relatively lower probability values.

FIG. 13Dillustrates a process for assessing the selected candidate regions for the user's right hip and right knee based on the probability model for the right femur. In general, selected candidate regions for joints that are directly connected in a pose model (e.g., right hip and right knee) may be assessed based on corresponding segment probability models (e.g., right femur, right tibia/fibula, etc.). Conceptually, each pair of joint candidates may serve as the candidate end points for a predetermined segment, and the probability model for such segment may be used to assess how likely those candidates are the endpoints for such a segment in the image. As shown inFIG. 13D, the candidate regions for the right hip are regions1310band1310c, determined using the probability model for the right hip, and the candidate regions for the right knee are regions1320band1320c, determined using the probability model for the right knee. In this example, the possible pairings between the right hip and the right knee are therefore: (1) regions1310band1320b, (2) regions1310band1320c, (3) regions1310cand1320b, and (4) regions1310cand1320c.

In particular embodiments, for each pair of candidate joints, a probability score may be computed based on the corresponding segment probability model to determine the likelihood of those pair of candidates being the joints of interest. For example, to compute the probability score for the pairing between regions1310band1320b, the regions1341connecting those two candidate regions1310band1320bmay be identified. Since the joint pairing is between candidates for the right hip and right knee, the probability model for the right femur, which connects the right hip and the right knee in the pose model, may be used to compute the probability score. In particular embodiments, the probability values corresponding to the connecting regions1341may be looked up using the probability model for the right femur. For example, the ten connection regions1341depicted inFIG. 13Dmay have probability values 0.92, 0.93, 0.94, 0.95, 0.95, 0.96, 0.96, 0.96, 0.97, and 0.97. In particular embodiments, the probability score may be computed based on these probability values, such as their average (e.g., 0.95), their product (e.g., 0.60), or any other representation of the aggregate probability. In particular embodiments, the probability values of surrounding regions may also be used (e.g., the regions adjacent to the end candidate regions1310band1320b, regions adjacent to the connecting regions1341, etc.). In a similar manner, a probability score may be computed for the candidate pair1310band1320cbased on the connecting regions1342, another probability score may be computed for the candidate pair1310cand1320bbased on the connecting regions1343, and yet another probability score may be computed for the candidate pair1310cand1320cbased on the connecting regions1344.

In particular embodiments, the computed probability scores may be used to identify the most likely regions for the joints of interest. For example, the probability scores for the connecting regions1341,1342,1343, and1344may be compared, and the candidate pair associated with the highest probability score may be selected to represent the keypoints for the joints of interest (e.g., in this case the right hip and/or the right knee). For example, the probability scores for the connecting regions1341,1342,1343, and1344may be 0.95, 0.66, 0.70, 0.85, respectively. The low probability scores for the connecting regions1342and1343may be attributed to the fact that they include regions between the user's legs with low probability values. Since 0.95 is the highest probability value, the associated regions1310band1320bmay be deemed the most likely regions for the right hip and right knee, respectively.

Although in the example above the keypoints are selected based on probability scores for the particular segment type connecting the joints of interest (e.g., the right femur connecting the right hip and right knee), the keypoint selection process, in particular embodiments, may also take a more holistic view and consider the probability scores of other connecting segments and joints. For example, to determine the location of the person's right knee, the selection process may consider the probability scores associated with the person's right tibia/fibula in addition to the right femur (both the right femur and the right tibia/fibula share the right knee as a common joint), as well as any other connected portions of the pose model (e.g., the left femur, spine, right shoulder, etc.). Considering the probability scores of other connecting segments is helpful because the end goal is to predict a pose structure in certain embodiments, rather than a joint location in isolation. Moreover, there may be disagreement between the conclusions drawn from isolated analyses of different types of connecting segments (e.g., based on the probability scores for the right tibia/fibula, the likely location of the right knee may be at region1320cinstead of the aforementioned region1320b). Thus, in particular embodiments, keypoints for the pose may be determined based on a larger structure that includes multiple different connecting segments and joints. For example, selecting the region for the right knee may be based on not just the probability scores associated with the right femur, but also those of the right tibia/fibula, the segment connecting the right hip and the center hip bone, the spine or segment connecting the center hip bone and the mid-point between the shoulders, etc. For each possible pose (e.g., all 19 keypoints) or portion thereof (e.g., the leg portion includes the right hip joint, right knee, and right ankle) that can be formed using the candidate regions, an aggregated probability score may be computed based on individual probability scores for segments within that pose or portion thereof. For example, in the above example, the probability scores associated with the connecting regions1341,1342,1343, and1344are compared to determine which is the most likely location of the right femur. If the right tibia/fibula is also considered, the probability scores for1341and1343may each be aggregated with the probability score, computed using the probability model for the right tibia/fibula, for the regions under the depicted person's1301right knee (e.g., the regions below1320b, which may be one candidate for the right tibia/fibula). Similarly, the probability scores for1342and1344may each be aggregated with the probability score, computed using the probability model for the right tibia/fibula, for the regions under the depicted person's1301left knee (e.g., the regions below1320c, which may also be a candidate for the right tibia/fibula). The aggregated probability scores may then be compared to determine which pose configuration is more likely.

FIG. 14illustrates an example method for selecting a keypoint region for a particular feature of interest (e.g., a joint, such as the right knee) using a probability model for a connecting segment (e.g., the right femur), in accordance with particular embodiments. In particular embodiments, at step1410, a computing system (e.g., a client device, such as a mobile phone, computer, augmented-reality device, virtual reality device, remote server, distributed system, etc.) may access a first probability model associated with an image depicting a body. The first probability model may include first probability values associated with regions of the image, with each of the first probability values representing a probability of the associated region of the image containing a predetermined first body part (e.g., the right knee joint). In particular embodiments, the first probability model may be generated based on a generated regional definition encompassing the depicted body in the image. The regional definition may be, for example, an object detection indicator (e.g., coordinates of a bounding box surrounding a person) generated by the detection head.

At step1420, the system may access a second probability model associated with the image. The second probability model may include second probability values associated with the regions of the image, with each of the second probability values representing a probability of the associated region of the image containing a predetermined second body part (e.g., the right hip joint). In particular embodiments, the predetermined first body part and the predetermined second body part are directly connected in a body-pose model (e.g., the right knee and the right hip are directly connected in the model shown inFIG. 12without any intervening joints).

At step1430, the system may access a third probability model associated with the image. The third probability model may include third probability values associated with the regions of the image, with each of the third probability values representing a probability of the associated region of the image containing a predetermined segment (e.g., right femur bone) connecting the predetermined first body part (e.g., right knee) and the predetermined second body part (e.g., right hip).

At step1440, the system may select a first region and a second region from the regions of the image based on the first probability model. For example, as illustrated inFIG. 13B, candidate regions1320band1320cfor the right knee are selected based on their probability values in the probability model for the right knee. In particular embodiments, each of the first region and the second region has an associated first probability value that is a local maximum in the first probability model.

At step1450, the system may select a third region from the regions of the image based on the second probability model. For example, as illustrated inFIG. 13A, candidate region1310b(or1310c) may be selected based on its probability value in the probability model for the right hip.

At step1460, the system may compute, based on the third probability model, a first probability score for regions connecting the first region and the third region. For example, as illustrated inFIG. 13D, a probability score may be computed, using the probability model for the right femur, for the connecting regions1341, which connects the regions1320band1310b. In particular embodiments, the first probability score for the regions connecting the first region and the third region is computed based on the third probability values that are associated with those regions. For example, the system may look up the probability values in the probability model for the right femur and use the ones corresponding to the connecting regions to compute the probability score.

At step1470, the system may compute, based on the third probability model, a second probability score for regions connecting the second region and the third region. For example, as illustrated inFIG. 13D, a probability score may be computed, using the probability model for the right femur, for the connecting regions1342, which connects the regions1320cand1310b. As described elsewhere herein, additional probability scores may be computed for other candidate regions (e.g., the connecting region1344between regions1310cand1320c, etc.). In that case, the additional probability scores may also be used in the next step to select the keypoint region for the first body part.

At step1480, the system may select, based at least one the first probability score and the second probability score, the first region to indicate where the predetermined first body part of the body appears in the image. Referring again toFIG. 13D, the system may determine that, because the probability score associated with the connecting regions1341is greater than that of the connecting region1342, the regions1341are more likely to be where the right femur appears in the image. As such, region1320b, which is one of the end points of the connecting region1341, would be the more likely location for the right knee. In particular embodiments, this selection process may further be based on additional probability score(s) computed using additional probability model(s) associated with additional predetermined segment(s) connecting different predetermined body parts. In particular embodiments, the different predetermined body parts connected by the additional predetermined segment may be different from the predetermined first body part and the predetermined second body part. For example, the left hip and the left knee, which are end joints for the left femur, are different from the right hip and the right knee. The system may compute additional probability scores for candidate regions associated with the left femur and/or any other connecting segment, such as the right tibia/fibula, left humerus, etc., and use these probability scores to determine where the right knee is located. Based on the selected region for the right knee (and any other predetermined body part of interest), the system may generate a keypoint mask that represents the predicted pose of the depicted person.

Particular embodiments may repeat one or more steps of the process ofFIG. 14, where appropriate. Although this disclosure describes and illustrates particular steps of the process ofFIG. 14as occurring in a particular order, this disclosure contemplates any suitable steps of the process ofFIG. 14occurring in any suitable order. Moreover, although this disclosure describes and illustrates an example method for selecting a keypoint for a particular feature of interest using the particular steps of the process shown inFIG. 14, this disclosure contemplates all, some, or none of the steps of the process shown inFIG. 14, where appropriate. Furthermore, although this disclosure describes and illustrates particular components, devices, or systems carrying out particular steps of the process ofFIG. 14, this disclosure contemplates any suitable combination of any suitable components, devices, or systems carrying out any suitable stages of the process ofFIG. 14.

FIG. 15illustrates an example network environment1500associated with a social-networking system. Network environment1500includes a client system1530, a social-networking system1560, and a third-party system1570connected to each other by a network1510. AlthoughFIG. 15illustrates a particular arrangement of client system1530, social-networking system1560, third-party system1570, and network1510, this disclosure contemplates any suitable arrangement of client system1530, social-networking system1560, third-party system1570, and network1510. As an example and not by way of limitation, two or more of client system1530, social-networking system1560, and third-party system1570may be connected to each other directly, bypassing network1510. As another example, two or more of client system1530, social-networking system1560, and third-party system1570may be physically or logically co-located with each other in whole or in part. Moreover, althoughFIG. 15illustrates a particular number of client systems1530, social-networking systems1560, third-party systems1570, and networks1510, this disclosure contemplates any suitable number of client systems1530, social-networking systems1560, third-party systems1570, and networks1510. As an example and not by way of limitation, network environment1500may include multiple client system1530, social-networking systems1560, third-party systems1570, and networks1510.

This disclosure contemplates any suitable network1510. As an example and not by way of limitation, one or more portions of network1510may include an ad hoc network, an intranet, an extranet, a virtual private network (VPN), a local area network (LAN), a wireless LAN (WLAN), a wide area network (WAN), a wireless WAN (WWAN), a metropolitan area network (MAN), a portion of the Internet, a portion of the Public Switched Telephone Network (PSTN), a cellular telephone network, or a combination of two or more of these. Network1510may include one or more networks1510.

Links1550may connect client system1530, social-networking system1560, and third-party system1570to communication network1510or to each other. This disclosure contemplates any suitable links1550. In particular embodiments, one or more links1550include one or more wireline (such as for example Digital Subscriber Line (DSL) or Data Over Cable Service Interface Specification (DOCSIS)), wireless (such as for example Wi-Fi or Worldwide Interoperability for Microwave Access (WiMAX)), or optical (such as for example Synchronous Optical Network (SONET) or Synchronous Digital Hierarchy (SDH)) links. In particular embodiments, one or more links1550each include an ad hoc network, an intranet, an extranet, a VPN, a LAN, a WLAN, a WAN, a WWAN, a MAN, a portion of the Internet, a portion of the PSTN, a cellular technology-based network, a satellite communications technology-based network, another link1550, or a combination of two or more such links1550. Links1550need not necessarily be the same throughout network environment1500. One or more first links1550may differ in one or more respects from one or more second links1550.

In particular embodiments, client system1530may be an electronic device including hardware, software, or embedded logic components or a combination of two or more such components and capable of carrying out the appropriate functionalities implemented or supported by client system1530. As an example and not by way of limitation, a client system1530may include a computer system such as a desktop computer, notebook or laptop computer, netbook, a tablet computer, e-book reader, GPS device, camera, personal digital assistant (PDA), handheld electronic device, cellular telephone, smartphone, augmented/virtual reality device, other suitable electronic device, or any suitable combination thereof. This disclosure contemplates any suitable client systems1530. A client system1530may enable a network user at client system1530to access network1510. A client system1530may enable its user to communicate with other users at other client systems1530.

In particular embodiments, social-networking system1560may be a network-addressable computing system that can host an online social network. Social-networking system1560may generate, store, receive, and send social-networking data, such as, for example, user-profile data, concept-profile data, social-graph information, or other suitable data related to the online social network. Social-networking system1560may be accessed by the other components of network environment1500either directly or via network1510. As an example and not by way of limitation, client system1530may access social-networking system1560using a web browser1532, or a native application associated with social-networking system1560(e.g., a mobile social-networking application, a messaging application, another suitable application, or any combination thereof) either directly or via network1510. In particular embodiments, social-networking system1560may include one or more servers1562. Each server1562may be a unitary server or a distributed server spanning multiple computers or multiple datacenters. Servers1562may be of various types, such as, for example and without limitation, web server, news server, mail server, message server, advertising server, file server, application server, exchange server, database server, proxy server, another server suitable for performing functions or processes described herein, or any combination thereof. In particular embodiments, each server1562may include hardware, software, or embedded logic components or a combination of two or more such components for carrying out the appropriate functionalities implemented or supported by server1562. In particular embodiments, social-networking system1560may include one or more data stores1564. Data stores1564may be used to store various types of information. In particular embodiments, the information stored in data stores1564may be organized according to specific data structures. In particular embodiments, each data store1564may be a relational, columnar, correlation, or other suitable database. Although this disclosure describes or illustrates particular types of databases, this disclosure contemplates any suitable types of databases. Particular embodiments may provide interfaces that enable a client system1530, a social-networking system1560, or a third-party system1570to manage, retrieve, modify, add, or delete, the information stored in data store1564.

In particular embodiments, social-networking system1560may provide users with the ability to take actions on various types of items or objects, supported by social-networking system1560. As an example and not by way of limitation, the items and objects may include groups or social networks to which users of social-networking system1560may belong, events or calendar entries in which a user might be interested, computer-based applications that a user may use, transactions that allow users to buy or sell items via the service, interactions with advertisements that a user may perform, or other suitable items or objects. A user may interact with anything that is capable of being represented in social-networking system1560or by an external system of third-party system1570, which is separate from social-networking system1560and coupled to social-networking system1560via a network1510.

In particular embodiments, social-networking system1560may be capable of linking a variety of entities. As an example and not by way of limitation, social-networking system1560may enable users to interact with each other as well as receive content from third-party systems1570or other entities, or to allow users to interact with these entities through an application programming interfaces (API) or other communication channels.

In particular embodiments, a third-party system1570may include one or more types of servers, one or more data stores, one or more interfaces, including but not limited to APIs, one or more web services, one or more content sources, one or more networks, or any other suitable components, e.g., that servers may communicate with. A third-party system1570may be operated by a different entity from an entity operating social-networking system1560. In particular embodiments, however, social-networking system1560and third-party systems1570may operate in conjunction with each other to provide social-networking services to users of social-networking system1560or third-party systems1570. In this sense, social-networking system1560may provide a platform, or backbone, which other systems, such as third-party systems1570, may use to provide social-networking services and functionality to users across the Internet.

In particular embodiments, social-networking system1560also includes user-generated content objects, which may enhance a user's interactions with social-networking system1560. User-generated content may include anything a user can add, upload, send, or “post” to social-networking system1560. As an example and not by way of limitation, a user communicates posts to social-networking system1560from a client system1530. Posts may include data such as status updates or other textual data, location information, photos, videos, links, music or other similar data or media. Content may also be added to social-networking system1560by a third-party through a “communication channel,” such as a newsfeed or stream.

FIG. 16illustrates example social graph1600. In particular embodiments, social-networking system1560may store one or more social graphs1600in one or more data stores. In particular embodiments, social graph1600may include multiple nodes—which may include multiple user nodes1602or multiple concept nodes1604—and multiple edges1606connecting the nodes. Each node may be associated with a unique entity (i.e., user or concept), each of which may have a unique identifier (ID), such as a unique number or username. Example social graph1600illustrated inFIG. 16is shown, for didactic purposes, in a two-dimensional visual map representation. In particular embodiments, a social-networking system1560, client system1530, or third-party system1570may access social graph1600and related social-graph information for suitable applications. The nodes and edges of social graph1600may be stored as data objects, for example, in a data store (such as a social-graph database). Such a data store may include one or more searchable or queryable indexes of nodes or edges of social graph1600.

In particular embodiments, a concept node1604may represent a third-party webpage or resource hosted by a third-party system1570. The third-party webpage or resource may include, among other elements, content, a selectable or other icon, or other inter-actable object (which may be implemented, for example, in JavaScript, AJAX, or PHP codes) representing an action or activity. As an example and not by way of limitation, a third-party webpage may include a selectable icon such as “like,” “check-in,” “eat,” “recommend,” or another suitable action or activity. A user viewing the third-party webpage may perform an action by selecting one of the icons (e.g., “check-in”), causing a client system1530to send to social-networking system1560a message indicating the user's action. In response to the message, social-networking system1560may create an edge (e.g., a check-in-type edge) between a user node1602corresponding to the user and a concept node1604corresponding to the third-party webpage or resource and store edge1606in one or more data stores.

In particular embodiments, a pair of nodes in social graph1600may be connected to each other by one or more edges1606. An edge1606connecting a pair of nodes may represent a relationship between the pair of nodes. In particular embodiments, an edge1606may include or represent one or more data objects or attributes corresponding to the relationship between a pair of nodes. As an example and not by way of limitation, a first user may indicate that a second user is a “friend” of the first user. In response to this indication, social-networking system1560may send a “friend request” to the second user. If the second user confirms the “friend request,” social-networking system1560may create an edge1606connecting the first user's user node1602to the second user's user node1602in social graph1600and store edge1606as social-graph information in one or more of data stores1564. In the example ofFIG. 16, social graph1600includes an edge1606indicating a friend relation between user nodes1602of user “A” and user “B” and an edge indicating a friend relation between user nodes1602of user “C” and user “B.” Although this disclosure describes or illustrates particular edges1606with particular attributes connecting particular user nodes1602, this disclosure contemplates any suitable edges1606with any suitable attributes connecting user nodes1602. As an example and not by way of limitation, an edge1606may represent a friendship, family relationship, business or employment relationship, fan relationship (including, e.g., liking, etc.), follower relationship, visitor relationship (including, e.g., accessing, viewing, checking-in, sharing, etc.), subscriber relationship, superior/subordinate relationship, reciprocal relationship, non-reciprocal relationship, another suitable type of relationship, or two or more such relationships. Moreover, although this disclosure generally describes nodes as being connected, this disclosure also describes users or concepts as being connected. Herein, references to users or concepts being connected may, where appropriate, refer to the nodes corresponding to those users or concepts being connected in social graph1600by one or more edges1606. The degree of separation between two objects represented by two nodes, respectively, is a count of edges in a shortest path connecting the two nodes in the social graph1600. As an example and not by way of limitation, in the social graph1600, the user node1602of user “C” is connected to the user node1602of user “A” via multiple paths including, for example, a first path directly passing through the user node1602of user “B,” a second path passing through the concept node1604of company “Acme” and the user node1602of user “D,” and a third path passing through the user nodes1602and concept nodes1604representing school “Stanford,” user “G,” company “Acme,” and user “D.” User “C” and user “A” have a degree of separation of two because the shortest path connecting their corresponding nodes (i.e., the first path) includes two edges1606.

In particular embodiments, an edge1606between a user node1602and a concept node1604may represent a particular action or activity performed by a user associated with user node1602toward a concept associated with a concept node1604. As an example and not by way of limitation, as illustrated inFIG. 16, a user may “like,” “attended,” “played,” “listened,” “cooked,” “worked at,” or “watched” a concept, each of which may correspond to an edge type or subtype. A concept-profile page corresponding to a concept node1604may include, for example, a selectable “check in” icon (such as, for example, a clickable “check in” icon) or a selectable “add to favorites” icon. Similarly, after a user clicks these icons, social-networking system1560may create a “favorite” edge or a “check in” edge in response to a user's action corresponding to a respective action. As another example and not by way of limitation, a user (user “C”) may listen to a particular song (“Imagine”) using a particular application (SPOTIFY, which is an online music application). In this case, social-networking system1560may create a “listened” edge1606and a “used” edge (as illustrated inFIG. 16) between user nodes1602corresponding to the user and concept nodes1604corresponding to the song and application to indicate that the user listened to the song and used the application. Moreover, social-networking system1560may create a “played” edge1606(as illustrated inFIG. 16) between concept nodes1604corresponding to the song and the application to indicate that the particular song was played by the particular application. In this case, “played” edge1606corresponds to an action performed by an external application (SPOTIFY) on an external audio file (the song “Imagine”). Although this disclosure describes particular edges1606with particular attributes connecting user nodes1602and concept nodes1604, this disclosure contemplates any suitable edges1606with any suitable attributes connecting user nodes1602and concept nodes1604. Moreover, although this disclosure describes edges between a user node1602and a concept node1604representing a single relationship, this disclosure contemplates edges between a user node1602and a concept node1604representing one or more relationships. As an example and not by way of limitation, an edge1606may represent both that a user likes and has used at a particular concept. Alternatively, another edge1606may represent each type of relationship (or multiples of a single relationship) between a user node1602and a concept node1604(as illustrated inFIG. 16between user node1602for user “E” and concept node1604for “SPOTIFY”).

In particular embodiments, social-networking system1560may create an edge1606between a user node1602and a concept node1604in social graph1600. As an example and not by way of limitation, a user viewing a concept-profile page (such as, for example, by using a web browser or a special-purpose application hosted by the user's client system1530) may indicate that he or she likes the concept represented by the concept node1604by clicking or selecting a “Like” icon, which may cause the user's client system1530to send to social-networking system1560a message indicating the user's liking of the concept associated with the concept-profile page. In response to the message, social-networking system1560may create an edge1606between user node1602associated with the user and concept node1604, as illustrated by “like” edge1606between the user and concept node1604. In particular embodiments, social-networking system1560may store an edge1606in one or more data stores. In particular embodiments, an edge1606may be automatically formed by social-networking system1560in response to a particular user action. As an example and not by way of limitation, if a first user uploads a picture, watches a movie, or listens to a song, an edge1606may be formed between user node1602corresponding to the first user and concept nodes1604corresponding to those concepts. Although this disclosure describes forming particular edges1606in particular manners, this disclosure contemplates forming any suitable edges1606in any suitable manner.

FIG. 17illustrates an example computer system1700. In particular embodiments, one or more computer systems1700perform one or more steps of one or more methods described or illustrated herein. In particular embodiments, one or more computer systems1700provide functionality described or illustrated herein. In particular embodiments, software running on one or more computer systems1700performs one or more steps of one or more methods described or illustrated herein or provides functionality described or illustrated herein. Particular embodiments include one or more portions of one or more computer systems1700. Herein, reference to a computer system may encompass a computing device, and vice versa, where appropriate. Moreover, reference to a computer system may encompass one or more computer systems, where appropriate.

In particular embodiments, computer system1700includes a processor1702, memory1704, storage1706, an input/output (I/O) interface1708, a communication interface1710, and a bus1712. Although this disclosure describes and illustrates a particular computer system having a particular number of particular components in a particular arrangement, this disclosure contemplates any suitable computer system having any suitable number of any suitable components in any suitable arrangement.

In particular embodiments, processor1702includes hardware for executing instructions, such as those making up a computer program. As an example and not by way of limitation, to execute instructions, processor1702may retrieve (or fetch) the instructions from an internal register, an internal cache, memory1704, or storage1706; decode and execute them; and then write one or more results to an internal register, an internal cache, memory1704, or storage1706. In particular embodiments, processor1702may include one or more internal caches for data, instructions, or addresses. This disclosure contemplates processor1702including any suitable number of any suitable internal caches, where appropriate. As an example and not by way of limitation, processor1702may include one or more instruction caches, one or more data caches, and one or more translation lookaside buffers (TLBs). Instructions in the instruction caches may be copies of instructions in memory1704or storage1706, and the instruction caches may speed up retrieval of those instructions by processor1702. Data in the data caches may be copies of data in memory1704or storage1706for instructions executing at processor1702to operate on; the results of previous instructions executed at processor1702for access by subsequent instructions executing at processor1702or for writing to memory1704or storage1706; or other suitable data. The data caches may speed up read or write operations by processor1702. The TLBs may speed up virtual-address translation for processor1702. In particular embodiments, processor1702may include one or more internal registers for data, instructions, or addresses. This disclosure contemplates processor1702including any suitable number of any suitable internal registers, where appropriate. Where appropriate, processor1702may include one or more arithmetic logic units (ALUs); be a multi-core processor; or include one or more processors1702. Although this disclosure describes and illustrates a particular processor, this disclosure contemplates any suitable processor.

In particular embodiments, memory1704includes main memory for storing instructions for processor1702to execute or data for processor1702to operate on. As an example and not by way of limitation, computer system1700may load instructions from storage1706or another source (such as, for example, another computer system1700) to memory1704. Processor1702may then load the instructions from memory1704to an internal register or internal cache. To execute the instructions, processor1702may retrieve the instructions from the internal register or internal cache and decode them. During or after execution of the instructions, processor1702may write one or more results (which may be intermediate or final results) to the internal register or internal cache. Processor1702may then write one or more of those results to memory1704. In particular embodiments, processor1702executes only instructions in one or more internal registers or internal caches or in memory1704(as opposed to storage1706or elsewhere) and operates only on data in one or more internal registers or internal caches or in memory1704(as opposed to storage1706or elsewhere). One or more memory buses (which may each include an address bus and a data bus) may couple processor1702to memory1704. Bus1712may include one or more memory buses, as described below. In particular embodiments, one or more memory management units (MMUs) reside between processor1702and memory1704and facilitate accesses to memory1704requested by processor1702. In particular embodiments, memory1704includes random access memory (RAM). This RAM may be volatile memory, where appropriate. Where appropriate, this RAM may be dynamic RAM (DRAM) or static RAM (SRAM). Moreover, where appropriate, this RAM may be single-ported or multi-ported RAM. This disclosure contemplates any suitable RAM. Memory1704may include one or more memories1704, where appropriate. Although this disclosure describes and illustrates particular memory, this disclosure contemplates any suitable memory.

In particular embodiments, storage1706includes mass storage for data or instructions. As an example and not by way of limitation, storage1706may include a hard disk drive (HDD), a floppy disk drive, flash memory, an optical disc, a magneto-optical disc, magnetic tape, or a Universal Serial Bus (USB) drive or a combination of two or more of these. Storage1706may include removable or non-removable (or fixed) media, where appropriate. Storage1706may be internal or external to computer system1700, where appropriate. In particular embodiments, storage1706is non-volatile, solid-state memory. In particular embodiments, storage1706includes read-only memory (ROM). Where appropriate, this ROM may be mask-programmed ROM, programmable ROM (PROM), erasable PROM (EPROM), electrically erasable PROM (EEPROM), electrically alterable ROM (EAROM), or flash memory or a combination of two or more of these. This disclosure contemplates mass storage1706taking any suitable physical form. Storage1706may include one or more storage control units facilitating communication between processor1702and storage1706, where appropriate. Where appropriate, storage1706may include one or more storages1706. Although this disclosure describes and illustrates particular storage, this disclosure contemplates any suitable storage.

In particular embodiments, I/O interface1708includes hardware, software, or both, providing one or more interfaces for communication between computer system1700and one or more I/O devices. Computer system1700may include one or more of these I/O devices, where appropriate. One or more of these I/O devices may enable communication between a person and computer system1700. As an example and not by way of limitation, an I/O device may include a keyboard, keypad, microphone, monitor, mouse, printer, scanner, speaker, still camera, stylus, tablet, touch screen, trackball, video camera, another suitable I/O device or a combination of two or more of these. An I/O device may include one or more sensors. This disclosure contemplates any suitable I/O devices and any suitable I/O interfaces1708for them. Where appropriate, I/O interface1708may include one or more device or software drivers enabling processor1702to drive one or more of these I/O devices. I/O interface1708may include one or more I/O interfaces1708, where appropriate. Although this disclosure describes and illustrates a particular I/O interface, this disclosure contemplates any suitable I/O interface.

In particular embodiments, communication interface1710includes hardware, software, or both providing one or more interfaces for communication (such as, for example, packet-based communication) between computer system1700and one or more other computer systems1700or one or more networks. As an example and not by way of limitation, communication interface1710may include a network interface controller (NIC) or network adapter for communicating with an Ethernet or other wire-based network or a wireless NIC (WNIC) or wireless adapter for communicating with a wireless network, such as a WI-FI network. This disclosure contemplates any suitable network and any suitable communication interface1710for it. As an example and not by way of limitation, computer system1700may communicate with an ad hoc network, a personal area network (PAN), a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), or one or more portions of the Internet or a combination of two or more of these. One or more portions of one or more of these networks may be wired or wireless. As an example, computer system1700may communicate with a wireless PAN (WPAN) (such as, for example, a BLUETOOTH WPAN), a WI-FI network, a WI-MAX network, a cellular telephone network (such as, for example, a Global System for Mobile Communications (GSM) network), or other suitable wireless network or a combination of two or more of these. Computer system1700may include any suitable communication interface1710for any of these networks, where appropriate. Communication interface1710may include one or more communication interfaces1710, where appropriate. Although this disclosure describes and illustrates a particular communication interface, this disclosure contemplates any suitable communication interface.