User:Appuasc11r4

Maximum margin Hough Transform (computer vision ) is a feature extraction technique used to detect objects in image analysis and digital image processing. This technique places Hough transform in a discriminative framework where local parts probabilistically vote for location of the object. It allows for the weights to be learned in a max-margin framework to optimize the classification performance.

Various object detection techniques have been used throughout history viz. sliding window classifier, constellation model and implicit shape model. The Hough transform is also one such method and has been used for various pose estimation problems including shape detection. When the Hough transform is placed in a discriminative framework where each local part casts a weighted vote for the possible locations of the object center, the learning framework takes into account both the appearance of the part and the spatial distribution of its position with respect to the object center and parts. As the appearance of the part and its spatial distribution repeat and occur again at a consistent location then they are assigned with higher weights than the rest. The globally optimal solution can be obtained by using off the shelf optimization packages. This approach is known as Maximum Margin Hough Transform or ${\displaystyle M^{2}HT}$. The parts and the probability distribution of the object locations are treated as blackbox allowing us to learn weights for the popular implicit shape model.

Let ${\displaystyle f_{i}}$ denote the features observed at a location ${\displaystyle l_{i}}$, which could be based on the properties of the local patch around ${\displaystyle l_{i}}$. Let S(O, x) denote the score of object O at a location x. Here x denotes pose related properties such as position, scale, and aspect ratio. Let ${\displaystyle C_{i}}$ denotes the i’th codebook entry of the vector quantized space of features f.

The overall procedure Probabilistic Hough Transform can be seen as a weighted vote for object locations all over the codebook entries ${\displaystyle C_{i}}$. Whereas in Max-Margin Hough Transform the weights ${\displaystyle w_{i}}$ can be learnt in a discriinative manner which optimizes the classification performance. The main idea here is that the score of the S(O, x) is a linear function of ${\displaystyle p(O|C_{i})}$. background. Assuming that the probability ${\displaystyle p(O|C_{i},l)}$ is independent of the location (location invariance).

${\displaystyle \textstyle S(O,x)=\sum _{i,j}p(x|O,C_{i},l_{j})p(C_{i}|f_{j})p(O|C_{i},l_{j})}$

${\displaystyle =\textstyle \sum _{i,j}p(x|O,C_{i},l_{j})p(C_{i}|f_{j})p(O|C_{i})}$

${\displaystyle =\textstyle \sum _{i}p(O|C_{i})\sum _{j}p(x|O,C_{i},l_{j})p(C_{i}|f_{j})}$

${\displaystyle =\textstyle \sum _{i}w_{i}a_{i}(x)=w^{T}A(x)}$

where ${\displaystyle \textstyle A^{T}=[a_{1}a_{2}...a_{K}]}$ is the activation vector and ${\displaystyle a_{i}}$ is given by the following equation:

${\displaystyle a_{i}(x)=\textstyle \sum _{j}p(x|O,C_{i},l_{j})p(C_{i}|f_{j})}$

This algorithm finds weights that maximizes the score S on correct object locations over incorrect ones. Rather than estimating ${\displaystyle w_{i}}$ based only on codebook activations, we can use the conditional distribution of the object centers to learn the weights.^[1]

Let ${\displaystyle {(y_{i},x_{i})}_{i=1}^{N}}$be set of training examples, where ${\displaystyle y_{i}}$ ₢ {+1,−1} is the label and ${\displaystyle x_{i}}$ is the location of the i’th training instance.

The first stage is to compute the activations ${\displaystyle A_{i}=A(x_{i})}$ for each example by carrying forward the voting process and adding up the votes for each feature ${\displaystyle f_{j}}$ found at location ${\displaystyle l_{j}}$ according to the Equation explained in the above section. Thus the score assigned by the model to the instance i is ${\displaystyle w^{T}A_{i}}$. Weights are learned by maximizing this score on correct locations of the object over incorrect ones. In order to be robust to outliers and avoid overfitting, we propose a max-margin formulation leading to the following optimization problem

${\displaystyle min_{w,b,c}1/2w^{T}w+C\sum _{i=1}^{T}c_{i}}$

where w>=0, c>=0 for all i= 1,2,...,N

• Advanced Vision homepage
• Slideshare page

Category:Image processing Category:Artificial intelligence