Lecture 6,7: Detecting and labellingconstellation-objects in noiseP. PeronaCalifornia Institute of TechnologyEE/CNS148 - Spring 20051 IntroductionConsider an object (object class) composed of F parts. Each part has a number ofcoordinates (position, velocity, size, contrast...) which we indicate with xi. The typicalappearance of the object (object class) is des cribed by a joint ‘object’ probabilitydensity pfg(x1, . . . , xF). Each part is detected by an appropriate feature detector.Apart from the object in the image there is a background which contains texturepatches that may be mistaken for the features that are assoc iated to the object parts.There are three ‘natural’ questions:Detection - Is there an object at all?Counting - How many objects are there?Labelling - Suppose that there is an objec t (or two, or three...), which one of theobserved features correspond to the object parts?We are going to address these ques tions in a probabilistic framework: we are goingto address the detec tion problem by comparing the probability that the object ispresent vs. the probability that the object is absent, given the data that we observe.The counting and labeling problem may be similarly addressed by comparing theprobability of different hypotheses. The aim of this lecture is to develop methods forcalculating such quantities. In order to develop the intuition and the notation we willexamine first the simple case of a 1-part object.2 Toy problem: single-part objectSupp ose that there is either one object or none, and that our object contains onlyone part. We detect in the image N candidate regions/points of coordinates x =(x1, . . . , xN).Notation:1O - The object. O = 0 me ans that no object is present, O = 1 means that there is anobject in the scene, O = 2 means that there are 2 objects in the sce ne, etc.x - The observations, i.e. the detected points. We assume that the ordering of thevector x is random i.e. that we are not listing detections in any special order(this fact is important - it will be used later).h - The hypothesis: a variable telling us which observation is believed to correspond tothe object feature. I.e. h = i means that we believe that xicorresponds to theobject’s feature and all other xjare false alarms. We will indicate with h = 0the hypothesis that all observations are false alarms and that the object’s featurewas not detected.xo- The observed coordinate of the object’s feature.xbg- The coordinates of the background features that have been detecte d. Naturally:xo∪ xbg= x.n - The number of detections associated to background clutter (equal to the length ofthe vector xbg).d - d = 1 indicates the the objec t’s feature was detected, while d = 0 means that thefeature was not detected. Notice that d is a function of h, and d = 0 iff h = 0.2.1 DetectionConsider a situation where there are two possible events: O = 0 and O = 1. Then wemay consider the ratio:R(O|x).=P (O = 1|x)P (O = 0|x)=P (x|O = 1)P (x|O = 0)P (O = 1)P (O = 0).= R(x|O)R(O)(the second equation is obtained using Bayes’ rule). If the ratio R is greater thenone then we may conclude that the object is more likely to be there than not andviceversa. We assume that we know R(O), i.e. the ratio of the a priori probabilitythat the object is present and that the object is absent. If we have no idea whatsoeverof the value of these probabilities then it is common to assume that they are equaland that this ratio is equal to one.In order to compute the ratio R(x|O) we need to compute the conditional probabil-ity density P (x|O). Observe first that there are a number of hypotheses that we mayentertain to explain both O = 0 and O = 1, namely h = 0, 1, . . . , n; let’s call H the setof these hyp. Some of them have zero probability (e.g. h = 3 if O = 0). Notice that hcontains three pieces of information: whether the feature associated to the object wasdetected at all, how many false detections there were and which point xiis the featureassociated to the object. Because of this, it is convenient to write h as three random2variables: d, encoding whether the feature was detected in the first place, n countingthe number of false alarms, and h encoding which feature is associated to the object .Observe that once we know the hypothesis h then n and d are completely determined.Nevertheless considering n and d makes the notation easier as it will be clear later.Observe that all hypotheses h are mutually exclusive and therefore we may writeP (x|O) =Xh∈H,n(h),d(h)P (x, h, n, d|O)Let’s now separate the information contained in the variables:P (x, h, n, d|O) = P (x|h, n, d, O)P (h|n, d, O)P (n|d, O)P (d|O)This is handy b ec ause we know how to estimate/compute each one of the terms in theproduct:P (x|h, n, d, O) – It is the probability density of observing a certain ‘constellation’ ofpoints where we know which point is given by the object and which are falsealarms (h tells us that), and how many such false alarms there are (n tells usthat). The relevant information on d and O is incorporated in h and n, thereforewe may write:P (x|h, n, d, O) = P (x|h, n) = Pfg(xo)Pbg(xbg) if h 6= 0= Pbg(x) if h = 0If we assume that the pdf of the position of the false alarms xbgis uniform ofthe area A of the image, and that the false alarms are independently distributed,then the background pdf is defined asPbg(xbg) = A−nP (h|n, d, O) – It is the probability of a certain hypothesis when we know the numberof false alarms, whether the object’s feature was detected or not, and whetherthe object is there at all. Observe that once we know n and d then O is eitherdetermined or irrelevant and therefore we may write:P (h|n, d, O) = P (h|n, d)= 1 if h = 0 and d = 0=1n + 1if h = i 6= 0 and d = 1= 0 otherwise.In the above we have assumed that all hypotheses are equally likely. This is trueonly if the order of the observations is random (as assume above). It would not betrue if the observations were listed from left to right (i.e. if i < j ⇒ xi<= xj)because in this case our prior knowledge of where we expect the object to bewould be result in some hypotheses being more likely than others.3P (n|d, O) – This is the probability of the number of false alarms. In first order ap-proximation it is independent of wheter the object’s feature was detected or notor whether the object is present or not. If one wants to be very precise onemust say that the presence of the object will occlude part of the background andtherefore limit