Visual Turing Test

Research in computer vision dates back to the 1960s when Seymour Papert first attempted to solve the problem. This unsuccessful attempt was referred to as the Summer Vision Project. The reason why it was not successful was because computer vision is more complicated than what people think. The complexity is in alignment with the human visual system. Roughly 50% of the human brain is devoted in processing vision, which clearly indicates that it is a difficult problem.

Later there were attempts to solve the problems with models inspired by the human brain. Perceptrons by Frank Rosenblatt, which is a form of the neural networks, was one of the first such approaches. These simple neural networks could not live up to their expectations and had certain limitations due to which they were not considered in future research.

Later with the availability of the hardware and some processing power the research shifted to image processing which involves pixel-level operations, like finding edges, de-noising images or applying filters to name a few. There was some great progress in this field but the problem of vision which was to make the machines understand the images was still not being addressed. During this time the neural networks also resurfaced as it was shown that the limitations of the perceptrons can be overcome by Multi-layer perceptrons. Also in the early 1990s convolutional neural networks were born which showed great results on digit recognition but did not scale up well on harder problems.

The late 1990s and early 2000s saw the birth of modern computer vision. One of the reasons this happened was due to the availability of key, feature extraction and representation algorithms. Features along with the already present machine learning algorithms were used to detect, localise and segment objects in Images.

While all these advancements were being made, the community felt the need to have standardised datasets and evaluation metrics so the performances can be compared. This led to the emergence of challenges like the Pascal VOC challenge and the ImageNet challenge. The availability of standard evaluation metrics and the open challenges gave directions to the research. Better algorithms were introduced for specific tasks like object detection and classification.

Visual Turing Test aims to give a new direction to the computer vision research which would lead to the introduction of systems that will be one step closer to understanding images the way humans do.

A large number of datasets have been annotated and generalised to benchmark performances of difference classes of algorithms to assess different vision tasks (e.g., object detection/recognition) on some image domain (e.g., scene images).

One of the most famous datasets in computer vision is ImageNet which is used to assess the problem of object level Image classification. ImageNet is one of the largest annotated datasets available and has over one million images. The other important vision task is object detection and localisation which refers to detecting the object instance in the image and providing the bounding box coordinates around the object instance or segmenting the object. The most popular dataset for this task is the Pascal dataset. Similarly there are other datasets for specific tasks like the H3D[2] dataset for human pose detection, Core dataset to evaluate the quality of detected object attributes such as colour, orientation, and activity.

Having these standard datasets has helped the vision community to come up with extremely well performing algorithms for all these tasks. The next logical step is to create a larger task encompassing of these smaller subtasks. Having such a task would lead to building systems that would understand images, as understanding images would inherently involve detecting objects, localising them and segmenting them.

The Visual Turing Test (VTT) unlike the Turing test has a query engine system which interrogates a computer vision system in the presence of a human co-ordinator.

It is a system that generates a random sequence of binary questions specific to the test image, such that the answer to any question k is unpredictable given the true answers to the previous k − 1 questions (also known as history of questions).

The test happens in the presence of a human operator who serves two main purposes: removing the ambiguous questions and providing the correct answers to the unambiguous questions. Given an Image infinite possible binary questions can be asked and a lot of them are bound to be ambiguous. These questions if generated by the query engine are removed by the human moderator and instead the query engine generates another question such that the answer to it is unpredictable given the history of the questions.

The aim of the Visual Turing Test is to evaluate the Image understanding of a computer system, and an important part of image understanding is the story line of the image. When humans look at an image, they do not think that there is a car at ‘x’ pixels from the left and ‘y’ pixels from the top, but instead they look at it as a story, for e.g. they might think that there is a car parked on the road, a person is exiting the car and heading towards a building. The most important elements of the story line are the objects and so to extract any story line from an image the first and the most important task is to instantiate the objects in it, and that is what the query engine does.

Vocabulary

Vocabulary is a set of words that represent the elements of the images. This vocabulary when used with appropriate grammar leads to a set of questions. The grammar is defined in the next section in a way that it leads to a space of binary questions.

The vocabulary ${\displaystyle {\mathcal {V}}}$ consist of three components:

1. Types of Objects ${\displaystyle {\mathcal {T}}}$
2. Type-dependent attributes of objects ${\displaystyle {\mathcal {A}}(t)}$
3. Type-dependent relationships between two objects ${\displaystyle {\mathcal {R}}(t,t')}$

For Images of urban street scenes the types of objects include people, vehicle and buildings. Attributes refer to the properties of these objects, for e.g. female, child, wearing a hat or carrying something, for people and moving, parked, stopped, one tire visible or two tires visible for vehicles. Relationships between each pair of object classes can be either “ordered” or “unordered”. The unordered relationships may include talking, walking together and the ordered relationships include taller, closer to the camera, occluding, being occluded etc.

Sample regions used as context in a Visual Turing Test. The one on the left shows regions with 1/8 the size of the image and the one on the right show regions with 1/4 size of the image

Additionally all of this vocabulary is used in context of rectangular image regions w \in W which allow for the localisation of objects in the image. An extremely large number of such regions are possible and this complicates the problem, so for this test, regions at specific scales are only used which include 1/16 the size of image, 1/4 the size of image, 1/2 the size of image or larger.

Qexist = 'Is there an instance of an object of type t with attributes A partially visible in region w that was not previously instantiated?'

Quniq = 'Is there a unique instance of an object of type t with attributes A partially visible in region w that was not previously instantiated?'

Qatt(ot) = {'Does object ot have attribute a?' , 'Does object ot have attribute a1 or attribute a2?' , 'Does object ot have attribute a1 and attribute a2?'}

Qrel(ot,ot') = 'Does object ot have relationship r with object ot'?'

To select the next question in the sequence, VTT has to estimate the predictability of every proposed question. This is done using the annotated training set of Images. Each Image is annotated with bounding box around the objects and labelled with the attributes, and pairs of objects are labelled with the relations.
Consider each question type separately:

1. Instantiation questions: The conditional probability estimator for instantiation questions can be represented as:
   ${\displaystyle \quad {\widehat {P}}(X_{q}=1)={\frac {\#\{I\in T,H(I)=1,X_{q}(I)=1\}}{\#\{I\in T,H(I)=1\}}}}$
   The question is only considered if the denominator is at least 80 images. The condition of ${\displaystyle H(I)=1}$ is very strict and may not be true for a large number of Images, as every question in the history eliminates approximately half of the candidates (Images in this case). As a result, the history is pruned and the questions which may not alter the conditional probability are eliminated. Having a shorter history lets us consider a larger number of Images for the probability estimation.
   The history pruning is done in two stages:
   • In the first stage all the attribute and relationship questions are removed, under the assumption that the presence and instantiation of objects only depends on other objects and not their attributes or relations. Also, all the existence questions referring to regions disjoint from the region being referred to in the proposed question, are dropped with the assumption being that the probability of the presence of an object at a location ${\displaystyle w}$ does not change with the presence or absence of objects at locations other than ${\displaystyle w}$. And finally all the uniqueness questions with a negative response referring to regions disjointed from the region being referred to in the proposed question, are dropped with the assumption that the uniqueness questions with a positive response if dropped can alter the response of the future instantiation questions. The history of questions obtained after this first stage of pruning can be referred to as ${\displaystyle H_{q}'}$.
   • In the second stage an image-by-image pruning is performed. Let ${\displaystyle q_{i}}$ be a uniqueness question in ${\displaystyle H}$ that has not been pruned and is preserved in ${\displaystyle H_{q}'}$. If this question is in context of a region which is disjoint from the region being referenced in the proposed question, then the expected answer to this question will be ${\displaystyle 1}$, because of the constraints in the first stage. But if the actual answer to this question for the training image is ${\displaystyle 0}$, then that training image is not considered for the probability estimation, and the question ${\displaystyle q_{i}}$ is also dropped. The final history of questions after this is ${\displaystyle {\tilde {H}}(q,I)}$, and the probability is given by:
     ${\displaystyle \quad {\widehat {P}}(X_{q}=1)={\frac {\#\{I\in T,{\tilde {H}}(q,I)=1,X_{q}(I)=1\}}{\#\{I\in T,{\tilde {H}}(q,I)=1\}}}}$
2. Attribute questions: The probability estimator for attribute questions is dependent on the number of labeled objects rather than the images unlike the instantiation questions.
   Consider an attribute question of the form : ‘Does object o_t have attribute a?’, where ${\displaystyle o_{t}}$ is an object of type ${\displaystyle t}$ and ${\displaystyle a\in A_{t}}$. Let ${\displaystyle A}$ be the set of attributes already known to belong to ${\displaystyle o_{t}}$ because of the history. Let ${\displaystyle {\mathcal {O}}_{\mathbb {T} }}$ be the set of all the annotated objects (ground truth) in the training set, and for each ${\displaystyle o\in {\mathcal {O}}_{\mathbb {T} }}$, let ${\displaystyle {\mathcal {T}}_{\mathbb {T} }(o)}$ be the type of object, and ${\displaystyle {\mathcal {A}}_{\mathbb {T} }(o)}$ be the set of attributes belonging to ${\displaystyle o}$. Then the estimator is given by:
   ${\displaystyle \quad P(X_{q}=1)={\frac {\#\{o\in {\mathcal {O}}_{\mathbb {T} }:{\mathcal {T}}_{\mathbb {T} }(o)=t,A\cup \{a\}\subseteq {\mathcal {A}}_{\mathbb {T} }(o)\}}{\#\{o\in {\mathcal {O}}_{\mathbb {T} }:{\mathcal {T}}_{\mathbb {T} }(o)=t,A\subseteq {\mathcal {A}}_{\mathbb {T} }(o)\}}}}$
   This is basically the ratio of the number of times the object ${\displaystyle o}$ of type ${\displaystyle t}$ with attributes ${\displaystyle A\cup \{a\}}$ occurs in the training data, to the number of times the object ${\displaystyle o}$ of type ${\displaystyle t}$ with attributes ${\displaystyle A}$ occurs in the training data. A high number of attributes in ${\displaystyle A}$ leads to a sparsity problem similar to the instantiation questions. To deal with it we partition the attributes into subsets that are approximately independent conditioned on belonging to the object ${\displaystyle o_{t}}$. For e.g. for ${\displaystyle t={}}$person, attributes like crossing a street and standing still are not independent, but both are fairly independent of the sex of the person, whether the person is child or adult, and whether they are carrying something or not. These conditional independencies reduce the size of the set ${\displaystyle A}$, and thereby overcome the problem of sparsity.
3. Relationship questions: The approach for relationship questions is the same as the attribute questions, where instead of the number of objects, number of pair of objects is considered and for the independence assumption, the relationships that are independent of the attributes of the related objects and the relationships that are independent of each other are included.

Detailed example sequences can be found here.[3]

The Images considered for the Geman et al.[1] work are that of ‘Urban street scenes’ dataset,[1] which has scenes of streets from different cities across the world. This why the types of objects are constrained to people and vehicles for this experiment.

Images of the Urban Street scenes from the training data. The training data is a collection of such images with scenes from different cities across the world

Another dataset introduced by the Max Planck Institute for Informatics is known as DAQUAR[4][5] dataset which has real world images of indoor scenes. But they[4] propose a different version of the visual Turing test which takes on a holistic approach and expects the participating system to exhibit human like common sense.

Example annotations of training image provided by the human workers

This is a very recent work published on March 9, 2015, in the journal Proceedings of the National Academy of Sciences, by researchers from Brown University and Johns Hopkins University. It evaluates how the computer vision systems understand the Images as compared to humans. Currently the test is written and the interrogator is a machine because having an oral evaluation by a human interrogator gives the humans an undue advantage of being subjective, and also expects real time answers.

The Visual Turing Test is expected to give a new direction to the computer vision research. Companies like Google and Facebook are investing millions of dollars into computer vision research, and are trying to build systems that closely resemble the human visual system. Recently Facebook announced its new platform M, which looks at an image and provides a description of it to help the visually impaired.[6] Such systems might be able to perform well on the VTT.