1. An apparatus comprising:
an asynchronous constraint satisfaction problem solving module, the asynchronous constraint satisfaction problem solving module executable by one or more processors, the asynchronous constraint problem solving module configured to:
assign a priority level and a rank to each variable of a plurality of variables such that no two variables include both a same priority level and a same rank;
propagate at least one constraint to the plurality of variables in a first thread by reducing a speculative propagation range of a first variable of the plurality of variables when a first value in the speculative propagation range of the first variable is in conflict with the constraint; and
in a second thread, (1) update an explanation for the reduction in the speculative propagation range of the first variable, and (2) backtrack when a choice of a second value for a second variable of the plurality of variables would result in the speculative propagation range of the first variable becoming the empty set, wherein backtracking includes taking back a choice associated with a variable with a lowest priority level and if two choices are associated with respective variables assigned the same priority level then backtracking includes taking back the choice associated with the variable of the respective variables assigned a lower rank.
2. The apparatus of claim 1, wherein the asynchronous constraint satisfaction problem solving module is configured to:
choose the second value for the second variable in a third thread, the value chosen based on a heuristic.
3. The apparatus of claim 1, wherein the asynchronous constraint satisfaction problem solving module is configured to:
receive, during runtime, a new constraint; and
propagate, during runtime, the new constraint in the first thread.
4. The apparatus of claim 3, wherein the asynchronous constraint satisfaction problem solving module is configured to:
receive the plurality of variables and the at least one constraint;
choose the second value for the second variable, the choice made by selecting a value from a search range of the second variable; and
produce output including a solution value for the plurality of variables that satisfies one or more of; the at least one constraints and the new constraint.
5. The apparatus of claim 2, wherein each variable of the plurality of variables includes:
a choice status indicating if the variable is the subject of the choice based on the heuristic;
an initial range including all possible values of the variable;
a search range that is a subset of the initial range of the variable, the search range reduced from the initial range through a backtracking process; and
the speculative propagation range, the speculative propagation range a subset of the search range, the speculative propagation range including an explanation, the explanation including a history of the choices and constraints that reduced the speculative propagation range of the variable.
6. The apparatus of claim 5, wherein;
the search range of the first variable is initialized to the initial range of the first variable;
the speculative propagation range of the first variable is initialized to the initial range of the first variable;
the explanation of the speculative propagation range of the first variable is initialized to the empty set; and
the choice status of the first variable is initialized to indicate that the first variable is not currently the subject of a choice.
7. The apparatus of claim 5, wherein backtracking comprises:
when the explanation indicates that the choice affects only the speculative propagation range of the first variable, reduce the search range of the second variable by removing the second value from the search range and undo all other reductions based on the choice of the second value for the second variable.
8. A computer implemented method comprising:
assigning a priority level and rank to each variable of a plurality of variables such that no two variables include both a same priority level and a same rank;
propagating, using a first processor, at least one constraint to the plurality of variables by reducing a speculative propagation range of a first variable of the plurality of variables when a first value in the speculative propagation range is in conflict with the constraint; and
updating, using a second processor, an explanation for the reduction in the speculative propagation range of the first variable; and
backtracking when a choice of a second value for a second variable of the plurality of variables would result in the speculative propagation range of the first variable becoming the empty set, wherein backtracking includes taking back a choice associated with a variable with a lowest priority level and if two choices are associated with respective variables assigned the same priority level then taking back the choice associated with a variable of the respective variables assigned a lower rank.
9. The method of claim 8, comprising:
choosing, using a third processor, the second value for the second variable based on a heuristic.
10. The method of claim 8, comprising:
receiving, during runtime, a new constraint; and
propagating, during runtime the new constraint in the first thread.
11. The method of claim 10, comprising:
receiving the plurality of variables and the at least one constraint;
choosing a value for the second variable, the choice made by selecting a value from a search range of the second variable; and
producing an output including a solution value for the plurality of variables that satisfies one or more of: the at least one constraint and the new constraint.
12. The method of claim 11, comprising
receiving an initial range for a variable of the plurality of variables, the initial range including all possible values for the variable;
creating a choice status for the variable, the choice status indicating if the variable is the subject of the choice based on the heuristic;
creating a search range for the variable, the search range a subset of the initial range of the variable, the search range reduced from the initial range through the backtracking process; and
creating the speculative propagation range for the variable, the speculative propagation range a subset of the search range of the variable, the speculative propagation range including an explanation, the explanation including a history of the choices and constraints that reduced the initial range of the variable to the speculative propagation range of the variable.
13. The method of claim 12, comprising:
initializing the search range of the first variable to the initial range of the first variable;
initializing the speculative propagation range of the first variable to the initial range of the first variable;
initializing the explanation of the speculative propagation range of the first variable to the empty set; and
initializing the choice status of the first variable to indicate that the first variable is not currently the subject of a choice.
14. The method of claim 13, wherein backtracking when a choice of a second value for a second variable of the plurality of variables would result in the speculative propagation range of the first variable becoming the empty set includes:
when the explanation indicates that the choice affects only the speculative propagation range of the first variable, reducing the search range of the second variable by removing the second value from the search range and undo all other reductions based on the choice of the second value for the second variable.
15. A non-transitory machine readable storage device that stores instructions, the instructions, which when performed by a machine, cause the machine to perform operations for asynchronous constraint satisfaction problem solving, comprising:
assigning a priority level and a rank to each variable of a plurality of variables such that no two variables include both a same priority level and a same rank;
propagating, using a first processor, at least one constraint to the plurality of variables by reducing a speculative propagation range of a first variable of the plurality of variables when a first value in the speculative propagation range is in conflict with the constraint; and
updating, using a second processor, an explanation for the reduction in the speculative propagation range of the first variable; and
backtracking when a choice of a second value for a second variable of the plurality of variables would result in the speculative propagation range of the first variable becoming the empty set, wherein backtracking includes taking back a choice associated with a variable with a lowest priority level and if two choices are associated with respective variables assigned the same priority level then taking back the choice associated with a variable of the respective variables assigned a lower rank.
16. The machine readable storage device of claim 15, wherein the instructions include instructions which when performed by the machine, cause the machine to perform operations comprising:
choosing, using a third processor, the second value for the second variable based on a heuristic.
17. The machine readable storage device of claim 15, wherein the instructions include instructions which when performed by the machine, cause the machine to perform operations comprising:
receiving, during runtime, a new constraint; and
propagating, during runtime, the new constraint in the first thread.
18. The machine readable storage device of claim 15, wherein the instructions include instructions which when performed by the machine, cause the machine to perform operations comprising:
receiving the plurality of variables and the at least one constraint;
choosing a value for the second variable, the choice made by selecting a value from a search range of the second variable; and
producing output including a solution value for the plurality of variables that satisfies one or more of: the at least one constraint and the new constraint.
19. The machine readable storage device of claim 15, wherein the instructions for backtracking when a choice of a second value for a second variable of the plurality of variables would result in the speculative propagation range of the first variable becoming the empty set include instructions which when performed by the machine, cause the machine to perform operations comprising:
when the explanation indicates that the choice affects only the speculative propagation range of the first variable, reducing the search range of the second variable by removing the second value from the search range and undo all other reductions based on the choice of the second value for the second variable.
20. The machine readable storage device of claim 18, wherein the instructions include instructions which when performed by the machine, cause the machine to perform operations comprising:
receiving an initial range for a variable of the plurality of variables, the initial range including all possible values for the variable;
creating a choice status for the variable, the choice status indicating if the variable is the subject of the choice based on the heuristic;
creating a search range for the variable, the search range a subset of the initial range of the variable, the search range reduced from the initial range through the backtracking process; and
creating the speculative propagation range for the variable, the speculative propagation range a subset of the search range of the variable, the speculative propagation range including an explanation, the explanation including a history of the choices and constraints that reduced the initial range of the variable to the speculative propagation range of the variable.
The claims below are in addition to those above.
All refrences to claims which appear below refer to the numbering after this setence.
1. A method comprising:
receiving a detected image of at least one face;
generating a plurality of candidate face images based on the detected image, wherein a candidate face image is generated based on one or more of row or column shifts of pixels of the detected image;
analyzing the candidate face images based on data of at least one model identifying one or more poses related in part to at least one of a position or an orientation of respective candidate face images; and
determining that the image of at least one face corresponds to one of the poses based in part on one or more items of data of the candidate face images passing criteria identified by the model as corresponding to the pose.
2. The method of claim 1
wherein the at least one model comprises a plurality of models, each of the models corresponding to a respective pose, of a plurality of poses;
wherein analyzing the candidate face images further comprises analyzing each of the candidate face images to determine whether the candidate face images passes criterion established for each of the models; and
wherein determining that the image of at least one face corresponds to one of the poses further comprises determining, for each of the models, a total number of the candidate face images that pass the criterion.
3. The method of claim 2,
wherein determining that the image of at least one face corresponds to one of the poses comprises determining a pose of the at least one face of the detected image that corresponds to a respective pose of a corresponding model in which a highest number of the candidate face images passed the criterion.
4. The method of claim 1, wherein the at least one model comprises a plurality of models, each of the models corresponding to a respective pose of a plurality of poses, wherein analyzing the image of the at least one face based on data of at least one model comprises analyzing the detected image based in part on data of each of the models, the method further comprising:
determining, for each of the models, whether the detected image passes at least one condition for a respective pose of the poses; and
calculating one or more confidence scores associated with each of the models in response to determining that the detected image passed the condition for the respective pose.
5. The method of claim 1, wherein the at least one model comprises a plurality of models, each of the models corresponding to a respective pose of a plurality of poses, wherein analyzing the candidate face images based on data of at least one model comprises analyzing each of the candidate face images to determine whether each candidate face images passes criterion established for each of the models, the method further comprising:
determining, for each of the models, a confidence score for each of the candidate face images that passed the criterion.
6. The method of claim 5, further comprising:
adding each of the confidence scores corresponding to the models to obtain a plurality of total confidence scores, each of the total confidence scores corresponding to a respective model of the models; wherein determining that the image of at least one face corresponds to one of the poses further comprises determining that a pose of the image of at least one face corresponds to a respective pose of a corresponding model that is determined to comprise a highest total confidence score of the total confidence scores.
7. The method of claim 1, wherein the at least one model comprises a canonical correlation analysis model corresponding to a plurality of poses, each of the poses assigned a corresponding label, wherein analyzing the candidate face images based on data of at least one model comprises analyzing data of the detected image and data associated with the poses to determine whether the detected image corresponds to one of the poses, the method further comprising:
assigning a label of a corresponding pose to the detected image in response to determining that the detected image is associated with the corresponding pose;
wherein determining that the image of at least one face corresponds to one of the poses is based in part on determining that a pose of the face relates to the corresponding pose based at least in part on a value of the assigned label.
8. The method of claim 1, wherein the at least one model comprises a canonical correlation analysis model corresponding to a plurality of poses, each of the poses assigned a corresponding label of a plurality of labels, the method further comprising:
assigning a respective label of the labels to each of the candidate face images that are determined to be related in part to at least one of the poses.
9. An apparatus comprising:
at least one processor; and
at least one memory including computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following:
receive a detected image of at least one face;
generate a plurality of candidate face images based on the detected image, wherein a candidate face image is generated based on one or more of row or column shifts of pixels of the detected image;
analyze the candidate face images based on data of at one model identifying one or more poses related in part to at least one of a position or an orientation of respective candidate face images; and
determine that the image of at least one face corresponds to one of the poses based in part on one or more items of data of the candidate face images passing criteria identified by the model as corresponding to the pose.
10. The apparatus of claim 9, wherein the at least one model comprises a plurality of models, each of the models corresponding to a respective pose, of a plurality of poses;
wherein causing the apparatus to analyze the candidate face images further comprises causing the apparatus to analyze each of the candidate face images to determine whether the candidate face images passes criterion established for each of the models; and
wherein causing the apparatus to determine that the image of at least one face corresponds to one of the poses further comprises causing the apparatus to determine, for each of the models, a total number of the candidate face images that pass the criterion.
11. The apparatus of claim 10,
wherein causing the apparatus to determine that the image of at least one face corresponds to one of the poses comprises causing the apparatus to determine a pose of the at least one face of the detected image that corresponds to a respective pose of a corresponding model in which a highest number of the candidate face images passed the criterion.
12. The apparatus of claim 10, wherein the plurality of poses comprises at least one of a frontal pose, a tilt pose, a right half profile pose, a left half profile pose, a right full profile pose or a left full profile pose.
13. The apparatus of claim 9, wherein the at least one model comprises a plurality of models, each of the models corresponding to a respective pose of a plurality of poses, and
wherein causing the apparatus to analyze the image of the at least one face based on data of at least one model comprises causing the apparatus to analyze the detected image based in part on data of each of the models, wherein the memory and computer program code are further configured to, with the processor, cause the apparatus to:
determine, for each of the models, whether the detected image passes at least one condition for a respective pose of the poses; and
calculate one or more confidence scores associated with each of the models in response to determining that the detected image passed the condition for the respective pose.
14. The apparatus of claim 13, wherein the memory and computer program code are configured to, with the processor, cause the apparatus to:
determine that a pose of the face corresponds to a respective pose of a corresponding model assigned a highest confidence score of the confidence scores.
15. The apparatus of claim 9,
wherein the at least one model comprises a plurality of models, each of the models corresponding to a respective pose of a plurality of poses, wherein causing the apparatus to analyze the candidate face images based on data of at least one model comprises causing the apparatus to analyze each of the candidate face images to determine whether each candidate face images passes criterion established for each of the models, wherein the apparatus is further caused to:
determine, for each of the models, a confidence score for each of the candidate face images that passed the criterion.
16. The apparatus of claim 15, wherein the memory and computer program code are configured to, with the processor, cause the apparatus to:
add each of the confidence scores corresponding to the models to obtain a plurality of total confidence scores, each of the total confidence scores corresponding to a respective model of the models, wherein causing the apparatus to determine that a pose of the image of at least one face corresponds to a respective pose of a corresponding model that is determined to comprise a highest total confidence score among the total confidence scores.
17. The apparatus of claim 9, wherein the at least one model comprises a canonical correlation analysis model corresponding to a plurality of poses, each of the poses assigned a corresponding label, wherein causing the apparatus to analyze the candidate face images based on data of at least one model comprises causing the apparatus to analyze data of the detected image and data associated with the poses to determine whether the detected image corresponds to one of the poses, wherein the apparatus is further caused to:
assign a label of a corresponding pose to the detected image in response to determining that the detected image is associated with the corresponding pose;
wherein causing the apparatus to determine that the image of at least one face corresponds to one of the poses is based in part on causing the apparatus to determine that a pose of the face relates to the corresponding pose based at least in part on a value of the assigned label.
18. The apparatus of claim 9, wherein the at least one model comprises a canonical correlation analysis model corresponding to a plurality of poses, each of the poses assigned a corresponding label of a plurality of labels, and wherein the memory and computer program code are configured to, with the processor, cause the apparatus to:
assign a respective label of the labels to each of the candidate face images that are determined to be related in part to at least one of the poses.
19. The apparatus of claim 18, wherein a value of the assigned label denotes that the candidate face images correspond to a type of pose and wherein the memory and computer program code are configured to, with the processor, cause the apparatus to:
determine that a pose of the face comprises a pose that is determined to correspond to a highest number of the candidate face images.
20. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:
program code instructions configured to facilitate receipt of a detected image of at least one face;
program code instructions to generate a plurality of candidate face images based on the detected image, wherein a candidate face image is generated based on one or more of row or column shifts of pixels of the detected image;
program code instructions configured to analyze the candidate face images based on data of at least one model identifying one or more poses related in part to at least one of a position or an orientation of respective candidate face images; and
program code instructions configured to determine that the image of at least one face corresponds to one of the poses based in part on one or more items of data of the candidate face images passing criteria identified by the model as corresponding to the pose.