Geometric feature learning

Primitive features

• Corners: Corners are a very simple but significant feature of objects. Especially, Complex objects usually have different corner features with each other. Corners of an object can be extracted through Corner detection. Cho and Dunn [2] used a different way to define a corner by the distance and angle between two straight line segments. This is a new way by defining features as a parameterized composition of several components.
• Edges: Edges are one-dimensional structure features of an image. They represent the boundary of different image regions. The outline of an object can be easily detected by finding the edge using the technique of edge detection.
• Blobs: Blobs represent regions of images, which can be detected using blob detection method.
• Ridges: From a practical viewpoint, a ridge can be thought of as a one-dimensional curve that represents an axis of symmetry. Ridges detection method-see ridge detection
• salient points-see Kadir–Brady saliency detector
• image texture

Compound features[3]

• Geometric composition

Geometric component feature is a combination of several primitive features and it always consists more than 2 primitive features like edges, corners or blobs. Extracting geometric feature vector at location x can be computed according to the reference point, which is shown below:

${\displaystyle \textstyle \ x_{i}=x_{i-1}+\sigma _{i-1}d_{i}{\begin{bmatrix}\cos(\theta _{i-1}+\phi _{i})\\\sin(\theta _{i-1}+\phi _{i})\end{bmatrix}}}$

${\displaystyle \textstyle \ \theta _{i}=\theta _{i-1}+\Delta \theta _{i}}$

${\displaystyle \textstyle \ \sigma _{i}=\sigma _{i-1}\Delta \sigma _{i}}$

x means the location of the location of features, ${\displaystyle \textstyle \theta }$ means the orientation, ${\displaystyle \textstyle \sigma }$ means the intrinsic scale.

• Boolean Composition

Boolean compound feature consists of two sub-features which can be primitive features or compound features. There are two type of boolean features: conjunctive feature whose value is the product of two sub-features and disjunctive features whose value is the maximum of the two sub-features.

Feature space was firstly considered in computer vision area by Segen.[4] He used multilevel graph to represent the geometric relations of local features.

There are many learning algorithms which can be applied to learn to find distinctive features of objects in an image. Learning can be incremental, meaning that the object classes can be added at any time.

• Corner detection
• Curve fitting
• Edge detection
• Global structure extraction
• Feature histograms
• Line detection
• Connected-component labeling
• Image texture
• Motion estimation

The probably approximately correct (PAC) model was applied by D. Roth (2002) to solve computer vision problem by developing a distribution-free learning theory based on this model.[5] This theory heavily relied on the development of feature-efficient learning approach. The goal of this algorithm is to learn an object represented by some geometric features in an image. The input is a feature vector and the output is 1 which means successfully detect the object or 0 otherwise. The main point of this learning approach is collecting representative elements which can represent the object through a function and testing by recognising an object from image to find the representation with high probability. The learning algorithm aims to predict whether the learned target concept ${\displaystyle \textstyle f_{T}(X)}$ belongs to a class, where X is the instance space consists with parameters and then test whether the prediction is correct.

After learning features, there should be some evaluation algorithms to evaluate the learning algorithms. D. Roth applied two learning algorithms:

1.Sparse Network of Winnows(SNoW) system

• SNoW-Train
  • Initial step: initial the set of features ${\displaystyle \textstyle F_{t}=\phi }$ which linked to target t for all ${\displaystyle \textstyle t\in T}$. T is a set of object targets whose elements are ${\displaystyle \textstyle t_{1}}$ to ${\displaystyle \textstyle t_{k}}$
  • If each target object in set T belongs to a list of active features, link feature to target and set initial weight at the same time.
  • Evaluate the targets : compare targets ${\displaystyle \textstyle {\underset {i\in e}{\sum }}w_{i}^{t}}$ with ${\displaystyle \textstyle \theta _{t}}$, where ${\displaystyle \textstyle w_{i}^{t}}$ is the weight on one position connecting the features i to target t. \theta_{t} is the threshold for the target not t.
  • Update weight according to the result of evaluation. There are two cases: predicted positive on negative example (${\displaystyle \textstyle {\underset {i\in e}{\sum }}w_{i}^{t}>\theta _{t}}$ and targets are not in the list of active features) and predicted negative on positive example(${\displaystyle \textstyle {\underset {i\in e}{\sum }}w_{i}^{t}\leq \theta _{t}}$ and targets are in the list of active features).
• SNoW-Evaluation
  • Evaluate the each target using same function as introduced above
  • Prediction: Make a decision to select the dominant active target node.

2. support vector machines

The main purpose of SVM is to find a hyperplane to separate the set of samples ${\displaystyle \textstyle (x_{i},y_{i})}$ where ${\displaystyle \textstyle x_{i}}$ is an input vector which is a selection of features ${\displaystyle \textstyle x\in R^{N}}$ and ${\displaystyle \textstyle y_{i}}$ is the label of ${\displaystyle \textstyle x_{i}}$. The hyperplane has the following form: ${\displaystyle \textstyle f(x)=sgn\left(\sum _{i=1}^{l}y_{i}\alpha _{i}\cdot k(x,x_{i})+b\right)=\left\{{\begin{matrix}1,positive\;inputs\\-1,negative\;inputs\end{matrix}}\right.}$

${\displaystyle \textstyle k(x,x_{i})=\phi (x)\cdot \phi (x_{i})}$ is a kernel function

Both algorithms separate training data by finding a linear function.