mean average precision - pseudo code There are many blog posts and threads concerning the computation of mAP, both for PASCAL and for COCO. Still, they do not answer some fundamental questions.

I am listing here the flow as I understand it, and will be happy for people's answers and fixes:

Flow:


You run your detection and recognition model through all your testing images, for which you already have ground-truth annotations. You apply no threshold.  Question: Should each detection be duplicated |classes| times and saved for each class with its corresponding confidence? For example, a detection that is 60% dog, 40% cat and 0% for all the rest, should be saved once as dog with 0.6, once as cat with 0.4 and once for each other class with 0? 
For each class, the ground-truth boxes of this class are matched with the detected boxes that intersect with them with $IoU &gt; iou\_threshold$, where $iou\_theshold \in [0,1]$ is a predefined parameter, and which share the same class. The matches will be used in order to compute precision and recall for the class. Question: Is this process performed image-wise or over all the images at once? i.e., are precisions and recalls computed per image and then averaged, or are they computed over the total detections in all the images in one step? 
The detections are sorted according to their confidence. The threshold starts from 0 and is each time raised to exclude the next detection(s) with the next lowest confidence. The remaining detections already have correct/incorrect fields, from the previous step, which are now used to compute precision and recall with the current confidence threshold (the "next threshold" is the confidence of the detection(s) that we just excluded) 
The precision values are computed in certain predefined recall points, as the highest precision in all the points with recall &gt; recall_point. If there are no such points, then we use 0 as precision. The class' average precision (AP) is then computed as simply the mean of all the precisions we found for the set of certain recalls.  
mAP is computed as the mean of the classes' APs 
In COCO, this whole process will be repeated with a certain set of IoU thresholds and will be averaged again.
Firstly for your question 2. The precision and recall is calculated across all images, for a single class. Not on a per-image basis and averaging across images. The "A" in "mAP" means averaging across different recall levels, as you stated in step 4.

For your question 1. Whether to report a same bounding box to both the cat and the dog class is a decision that your detection algorithm should make, not a decision that the evaluation function should make. You can imagine that input to the evaluation script to be a ranked list for each class, for example:

class [dog]                        |  class[cat]                        |  class[foo] ...
image=17, score=0.98, bbox=[...]   |  image=41, score=0.75, bbox=[...]  |  ... 
image=33, score=0.60, bbox=[...]*  |  image=07, score=0.45, bbox=[...]  |  ... 
image=93, score=0.55, bbox=[...]   |  image=33, score=0.40, bbox=[...]* |  ...
...                                |  ...                               |...


The evaluation script will calculate the AP for each class and it won't care whether the same bounding box (*) appears in different classes.

So for your detection algorithm, you can try different strategies and see which one achieves higher mAP.