Bit search

Object detection at a local scale with EEG by Bigdely-Shamlo et al (2008)

2012-02-13T12:57:00.000+01:00

Following our overview on EEG-based classification of images, we have come up with a new article that explores the localization of objects within an image. The article "Brain Activity-Based Image Classification From Rapid Serial Visual Presentation" presents aclassification system based on a Brain Computer Interface (BCI) device that aims at detecting objects of interest in satellite images. The study was performed by Nima Bigdely-Shamlo, Andrey Vankov, Rey R.Ramirez and Scott Makeig of University of California, San Diego.

The paper considers an automatic classificationsystem of images in real time based on a BCI interface that measuresthe EEG waves from 128 channels (High-densityelectroencephalographic acquired date). The final application isthe detection of which satellite images from the city of London contain a plane.Users perform a visual inspection of the image at a local scale guided by RSVP. The systemacquires the user's EEG signals during the viewing of the clip to study whether itis possible to use these signals to detect the images with planes, a task that is considered too challengingfor the computer vision algorithms considered by the authors of the article.Additionally, the experiment also captures the manual classification of images bythe users. This way they can compare the automatic classification based on EEG waveswith the manual detection of the users.

The visual inspection guided by RSVP is made expandinga small region of the image and reducing the contrast of the rest of the image. This preprocessing of the image guarantees thefocus of the user's attention on the highlighted region, so the EEG classifier will not only discern if the whole image contains the plane, but also its location. The generated focus scans the complete image using a path called "Heptunxsearch". The scanning algorithm not only varies the position of the focus but also tests different sizes to consider different scales.

Image preprocessing to highlight a focus region.

Focused images are presented by RSVP in 12Hzand in blocks of 4.1 seconds (Bursts) that alternate relevant and irrelevantimage clips. These burst series are presented to 8 different users. Every user, aftereach block, indicates whether or not the relevant image has been seen. During trainingsessions, feedback is given to users to inform them if their answers has beencorrect or not. This way, the users also tune their attention and improve their manual detection skills.

The authors recommend not showing any relevant image in the first or the last 500ms of each block toprevent the effects that may occur in the EEG waves due to sudden changes inthe limits of image blocks.

Most of the paper describes the processing of the acquired data, which corresponds to 128 channels of EEG waves in the 8ms after displaying each image. As a result,each image is described by a characteristics matrix of 128 columns. Then,these matrices are reduced by different methods (ICA and PCA) to matrices of 50independent columns that characterize each image. Finally we get two matricesof features, one in the time domain and the other in the frequency domain fromwhich the classification is made.

The results presented are based onthe study of the Receiver Operating Characteristic (ROC) curves. These curves determine the amount oftrue positives tp (very relevantimages identified) in terms of false positive fp (irrelevant images identified as relevant) when consideringdifferent decision thresholds by the classifier. To determine the quality of theclassifier, the area under the ROC is calculated (tp and fp normalized at 1), beingthe result better as closer as to the unit.

The authors report results improve when combining theclassifiers in time domain and frequency domain. This fusion is performed by assuming independence between the two classifiers. In this case, the posterior probabilities obtained can be combined with a simple product (Naive Bayes Classifier).

The table shows the values of thearea under the ROC considering the different blocks of images displayed. It isinteresting to note that, although the response of manual annotations could be incorrect (Behaviorally Missed in the table),the values of these areas are still quite high for six of the eight participants. Thismeans that although users are not aware of having seen the object of interest,the brain continues responding to visual stimulus. The table also reflect the cases where users express that the object has appeared when it really was notpresent on the burst. This error is the cause of the the discrepancy between columns 3&4and 5&6. This type of mistake is very rare since in these cases the area underthe ROC is almost equal.

In conclusion,the system described is useful for a first search for anobject in a large portion of an image, a task where state of the art computer vision algorithms areinefficient. However, in our opinion, this paper fails into comparing the obtained results with the ones that could be obtained with a state of the art algorithm. It would be desirable to estimate the gain obtained with this EEG-based classifier, that is limited for the need of a human and a maximum frequency in the RSVP, with a fully automatic classification system based, for example, on the Viola and Jones object detector.

EEG-Augmented Image Search by Healy and Smeaton (2011)

2012-02-02T17:02:00.000+01:00

We have started to develop a new project to explorethe potential of Brain Computer Interfaces (BCI) for the search and tagging of images.The first step in the project development is to make a study of the state ofthe different researches based on the exploration of these interfaces. Thefirst working paper analyzed has been "Optimising the number of channels in EEG-Augmented Search" by Graham Healy and Alan Smeaton from the Dublin City University in Ireland.

The paper describes an experiment based on thedetection of certain target images in a large set of images. For itsrealization, used 4800 images of which 60 contained an object of interest underdifferent views. These images have been extracted from the Amsterdam Library of Object Images (ALOI).

Objects from the ALOI dataset

The relevant images are randomly distributed throughout theset. The sequence of images, known as Rapid Serial Visual Presentation (RSVP), is shown to 8 different people ata frequency of 10Hz. These persons are divided into 4 groups, where the 2people from each group will seek images with a different object of interestfrom the other groups.

The paper discusses the image-search processes based on BCI interfaces combined with a push-button. In the article, they improve theresults obtained when considering only the pulses on the push-button by adding brain waves captured from EEG. They call this concept ‘EEG-AugmentedImage Search’.

For the detection of the target images, they analyzetwo types of signals:

- Signal Button, which is acquired by pressinga button when the user sees a target image.

- EEG signals of the brain activity ofindividuals measured with the device KT88-1016, that consists in 16 sensorsplaced on the scarp. 16 different channels are processed.

P300 wave for a target event

These signals are acquired during one second after thepresentation of each image and sampled at 100Hz. Therefore, each image has anassociated feature vector of 100 samples. The 16 EEGfeature vectors are combined to create a single vector of 1600 samples. This fusionstrategy is called ‘Early Fusion’.

The system analyses the two feature vectors associated to every image (the EEG and the button) to determine if it is relevant to the search. In the case of the button,the pulse is clearly generated when the user presses the button. For EEG, the study isbased on the existence of P300 waves, whichproduce a maximum of around 300ms after the event. The irrelevant images willbe free from pulse (button) or wave (P300).

Because of the variability in the response time ofdifferent users, the proposed design trains a classifier which adapts tosignals generated by each person. A Support Vector Machine (SVM) classifier istrained for each type of feature vector (EEG and button) with relevance labelsassociated to each image presented. This same label is used to train a thirdSVM classifier that combines the outputs of the two classifiers, concatenating theprobability values obtained in each case. This strategy is called ‘Late Fusion’.

The classifier is trained with a subset of trainingimages, 50 target images and 50 non-target images (50/50). The test isperformed with another subset of data with a 10/790 distribution. Theprobability values obtained are sorted from the best to worst, and the precision for the top ten list items is computed (P@10), which correspond with thenumber of relevant images of the test subset. This process is repeated tentimes following a cross-validation scheme with random sampling.

In the table above we can note that thecombination of EEG waves with the signal of the button represents an increase inthe quality of the results for each user. Additionally, we can see the resultsof the second study described in the paper (not discussed in this summary)which optimizes the number of EEG channels used for each user.

In conclusion, the article shows that the EEGsignals can be used to increase the success in the process of image search ifthey are combined with the analysis of behavior responses in the context ofa limited amount of channels.

Intra-video clip retrieval with visual similarity and hierarchical indexing

2012-01-31T11:54:00.000+01:00

Our participation in the Video Browser Showdown at the Multimedia Modeling Conference 2012 required the extend of our visual search interface for still images, GOS, to be able to work with videos. After giving some details about my experience during the competition in the previous entry, now I am going to focus on the user interface.

First of all, the video is processed with a keyframe extractor, which is based on the idea of stripe images. A stripe image is created by taking the centre columns of pixels from every frame and attaching them to each other (see Figure below). This makes it possible to identify the different shots of the video (see SEMEDIA project for more information).

Then, a set of MPEG-7 visual descriptors are computed for each keyframe. Finally, we compute a visual index based on the Hierarchical Cellular Tree (HCT) in order to rapidly find similar images at retrieval time and have the database organized as a hierarchy.

Once the video keyframes are indexed, they can be loaded to GOS by selecting the Open Video option belonging to the File menu. Then, GOS will open a new tab for each computed descriptor. Each of these tabs displays the images belonging to the root node of the HCT. There is also an additional tab which shows all the keyframes extracted by the shot detector sorted by time.

Since the output of the HCT indexing algorithm is a hierarchical clustering of the keyframes in the video, each tab can be understood as a summary of the video according to each visual descriptor. Furthermore, we can take advantage of the tree structure and go down the tree by double-click on an element to visualize which elements represents.

The challenge proposed in the Video Browser Showdown was to localize the target clip within the video. The presented framework provides GOS with two alternatives to fulfill this task, both of them accessible by right-clicking on the thumbnail of one of the shown keyframes:

Find similar images. This option allows to search similar images to the given one. In fact, there are two different options: Find similar images (default) and Find similar images with... The former allows to find similar images according to a visual descriptor set as default (e.g. Color Layout). The latter allows the user to change the descriptor on which the search must be based. In any case, a new tab with the results of the search is opened.

Get temporal segment. This option allows the user to see the temporal context of the keyframe. When it is selected, the previous and next frames are showed in a new tab. These frames have been extracted at 1 frame per second rate. This option is used to see whether the retrieved keyframe belongs to the target clip or not. Since the elements showed in this tab are not the keyframes extracted by the shot detector, they cannot be used to perform new visual searches because these elements have not been indexed.

The strategy to retrieve the clip within the video can be summarized as follows:

See the summary tabs. If you find any keyframe which is likely to be part of the clip, select the Get temporal segment option to visualize it in the timeline.
If no keyframe belonging to the target clip is shown in the tab, you should try to identify a keyframe which is similar to any of the frames in the target video clip and launch a search by visual similarity. If you cannot find any keyframe which can be useful to perform a visual search, you can obtain new elements by descending through the index by double clicking on a thumbnail.
After performing a visual search, try to find any keyframe which can belong to the target video. In such a case, select the Get temporal segment option. Otherwise, you can try performing a new visual search by using an element obtained by the previous search.
If you do not succeed in retrieving the target clip, try with the other summary tabs which has not been already used.
In case you fail to retrieve the clip by using the different summary tabs, you should use the temporal tab, which shows all the keyframes extracted by the shot detector sorted by time.

These steps are illustrated in the following workflow:

In case you may be a bit overwhelmed with all this information, we have also produced a video tutorial that visually describes the presented workflow.

The P300 wave for Brain Computer Interfaces

2012-01-27T19:10:00.001+01:00

The Brain Computer Interfaces (BCI) technologies are based on theacquisition of user’s brainwaves to be processed and interpreted by a computer.Although most applications of this technologies are in the medical field, alsoin the image processing field scientists are developing a lot of studies aboutthe applicability of such devices. It is remarkable that ACM Comunications in May 2011 dedicatedits cover and main article for BCI devices technologies.

BCI devices are based on the measure of EEG signals. These are obtained by measuring the electric potential difference produced by brain activity. The acquisition devices are becoming popular thanks to their relatively low price, availability and security for the users (non invasive technique). Several experiments in the literature have reported their applications in different fields.

One of the most promising analysis that can be performed on EEG is the detection of an Event Related Potential (ERP), which can be produced by two different types of sources: a perception or a thought. The first case would correspond to an image, a temperature change, a sudden pain..., while the second case implies an internal cognitive stimulus, such as a state of attention or meditation. One of the most popular ERPs is the P300 wave, which is measured approximately between 300-600 ms after the stimulus occurs.

Scientists that want to observe the P300 wave prepare experiments on users based on the oddball paradigm. The basic strategy is to present a target stimulus or bull’s eye among other background stimulus.

In our work, we would like to explore the possibilities of measuring the P300 wave using images as stimulus. In this case, the target stimulus would correspond to an image which would be relevant for the user according to a certain task, while the background stimulus would be generated by non-relevant images.

Winners of the Novice Run in the Video Browser Showdown #mmm2012

2012-01-10T10:42:00.001+01:00

My attendance to the Video Browser Showdown at the MultiMedia Modeling 2012 conference has beenone of the greatest and exciting of my life. It took place inKlagenfurt am Wörthersee, which is placed in Austria. I went to this conference as a representative of the UPC team which also consists of Manel Martos, Xavi Giró-i-Nieto, Verónica Vilaplana and Ferran Marqués, to whom I am very grateful. Furthermore, nothing would be possible without the technical support given by Albert Gil and Josep Pujal. Some details about our work can be found here. Moreover, I would like to thank many volunteers from the Image and Video Processing Group which tested the user interface, i.e. the GOS (Graphic Object Searcher), and gave us some advice to improve it. They allowed us to check that the interface was really user-friendly. The development of this user interface started in 2008 thanks to the work done by Silvia Cortés (click here to see her degree's final project). A picture from the testing day is showed below.

The Video BrowserShowdown is a competition in which many teams compete in order toretrieve a short piece of video (around 15-20 seconds), which is onlyseen once in a shared screen, in a longer video, which lasts between1 and 2 hours. There were 30 different videos, which had beenpre-processed.

The competitionstarted at 13:30 on Friday 6th January, but the participants werecalled to be there 30 minutes before to prepare all the equipmentsand check that everything was ok. However, we had already been calledtwo days before to check that there were no problems with thecommunications between our systems and the server. My surprise wasthat we did not only check the systems, but we also did a test runcompetition. The organizers of the event were as enthusiastic as allparticipants. Everything was working perfectly and our first surprisewas that we headed the ranking at the run test competition.

Coming back to theactual competition on Friday and having checked that everything wasright, we were asked by the chairman to give him a brief introductionof our video retrieval systems. We were 11 teams, 3 of which werestudent teams from Klagenfurt University but they were not takingpart of the competition officially.

The competitionconsisted of two rounds: one first round, called expert-run, in whichthe retrieval systems were used by their developers, i.e. theparticipants, and a second round, called novice-run, in which anexternal user had to use the program. Therefore, the chairman asked11 volunteers and they were assigned randomly to each one of theteams. Luckily, we were assigned a very nice and smart girl named Camille. Myintention was explaining how the system worked by using a videotutorial we had prepared for the event but, to my surprise, we wereasked to train our users by using our tools in a run test video.Therefore, I decided to forget about the video tutorial and explainour system by performing an actual search. However, since the runtest video was very easy to find, my goal was not being the fastestteam in retrieving the video but I took advantage of all theavailable time to tell her all the different options and strategieswhich could be used in our video retrieval system. Eventually, wesubmitted the right segment which had been displayed at the sharedscreen. In that screen, in which the target videos were showed, wecould also see which was the accumulated score obtained by each teamat any instant. Moreover, the keyframes submitted by each team werealso displayed and were marked by a red frame if it was a wrongsubmission and by a green frame if it was a right one. The reason whywe were assigned the volunteers at the beginning was that, in thisway, the novice user could also learn about the system and get usedto it through our searches during the expert-run round. Then, theexpert-run round started.

The expert-run roundwas very hard. I remind sometimes that I was still watching the videowhen some teams had already retrieved it! I knew that some videosconsisted of clips which were very similar between them, such as aninterview in a political TV program. Therefore, from my point ofview, it was essential to pay attention while the target video wasbeing displayed to get any important detail, any change in the video,any keyframe easier to be retrieved with our system, since the lastpart of the video could be necessary to distinguish from any othersimilar segments or to retrieve it in a faster way. Anyway, it seemednot to make any point in comparison with some other teams, which werecapable of retrieving the videos in a few seconds, not to sayimmediately. However, I decided not to throw away all the work done.There was a user who was learning how to use our system and we couldretrieve most of the target videos. In fact, Camille, who was getting used to the program impressively fast, evenhelped me in one of the searches. It really was an inflexion point since I thought that wecould have a chance during the novice-run round. The expert-run roundfinished and the winner was Manfred Del Fabro from the Klagenfurt University after 8 video searches (there was no time for 12 scheduledsearches). In fact, I couldn't see which was our position in the ranking since the teams weren't sorted out by their scores. However, I think there were 2 teams which achieved a score lower than ours.

Then, the novice-runround started. Now, the novice users were going to use the systems.After the first search, we directly got the third place. I cheered up Camille for the well-done work. Moreover, I realised that the bestteams in the expert-run round were not doing so well at that moment.Maybe their systems were more powerful but more difficult to use fora novice user. After the third or fourth search we reached the top ofthe ranking. It was our first time at the head of the competition.Unfortunately, we went down to the second position after thefollowing search. We were running out of time, so the chairmandecided that the sixth search would be the last one and we had stillchances to win the competition. Camille found the last targetvideo very quickly so we got an accumulated score of 540 points,which allowed us to reach again the head of the competition. Wecrossed the fingers since we could only wait for the other teams.Then, the other team with chances of winning the novice-run alsoretrieve the video, but they were not fast enough and they got anaccumulated score of 536 points. Therefore, our expectances had beenaccomplished. We did win the novice-run round. It was the bestpresent for that special date (the Three Wise Men).

Finally, the twowinners were called to get our awards for the best video browserexpert-run and novice-run. After receiving the award, many peoplecame to me to know how the system worked and which was based on. Theywere surprised how powerful the option for retrieving similar imageswas by simply selecting the option from a pop menu. Furthermore, Camille highlighted that having different tabs summarizing the content of the video according to different criteria was very useful. In addition to this, the use of tabs for the results of the visual searches and to visualize the timeline was also a good decision.

Then, Oge Marques, which is a very nice professor from Florida and lovesFootball Club Barcelona (he wanted me to play its anthem as I wasbeing asked for the award), took me a picture, which is showed below.Eventually, I could feel relax. The competition had been finished. A summary of the tweets written in #mmm2012 can be seen here, which includes the congratulations from Oge Marques to the winners of the Video Browser Showdown.

The Semantic Shot Annotator at the Muscle Workshop in Pisa

2011-12-23T13:56:00.001+01:00

Most people travel to Pisa (Italy) to visit the world famous Leaning Tower. This local attraction probably sustains most of the economy in the town. The entrance to the tower costs 15 € which is somehow funny, as you can hardly enjoy the inclination from the inside. The locals explain that the origin of the leaning are the grounds, as the town in build on land gained to the Mediterranean Sea. In fact, it seems that the neighboring baptistery is also slightly inclined.

Nevertheless, I did not travel to Pisa for tourism. It has been a constant in the last years for me to travel to Italy to attend to conferences, workshop or courses. I can remember twice to Genoa (ICIP 2005 and SAMT), Sicily (SSMS), Trento (ICMR). This time, it was a workshop organized by MUSCLE, an European Network of Excellence sponsored by the European Commission.

My contribution to this workshop was presenting the results of the bachelor thesis that Elisabet Carcel presented last June, a joint work at the UPC and the Catalan Broadcast Corporation (CCMA). She developed a web-based GUI for the semi-automatic annotation of semantic shot types. The system was aimed to assist the archivers at the CCMA in the annotation of the keyframes which are automatically extracted from the video assets added into the archive. You can find the full details by reading the pre-print of the paper, the full thesis or just browsing through the slides I presented in Pisa. If your comprehension level of Catalan is good enough you can also watch the oral defense for Eli's thesis in this video (first and second parts) that was published last week, too. Maybe the most intuitive first contact though is just watching the two video demos from the soccer and parliament domain.

The participation of the Image Processing Group of the UPC in the workshop was completed with the work of Jaime Gallego Vila, Montse Solano and Montse Pardàs. Jaime presented the latest results of their object tracking algorithm, based on Gaussian Mixture Model of the object and background visual features. Neus and me had worked during Montse Solano's thesis in the development of a GUI for initializing their tracker and collect their results for an interactive segmentation of video objects.

First contact with Active learning with the Transferable Belief Model for Image Annotation”

2011-11-26T23:16:00.005+01:00

This February I will go on Erasmus to Grenoble, to the "Grenoble INP", in the Gipsa Lab (Grenoble Images Parole Signal Automatique) in the Image et Signal department. I have been proposed to work in a project of active learning with M. Rombaut and D. Pellerin. My first task has been reading the paper Multi-labeled image classification by TBM active learning, presented in the Workshop on Theory of Belief Functions (Belief 2010), Brest : France (2010).

When I was collaborating with the TSC department I became familiarized with supervised learning, as it was the system used in experiments such as Formula 1 publicity. This article is not about supervised learning, it is about active learning, a form of supervised learning that requires the interaction of the user. There are situations when we have some many images to annotate that any help can be useful. For example, in the F1 experiment we annotated the images randomly, but a little help to know which ones were the most useful could have provided better results with less annotated images.

This system is a tool to make user’s work easier. Already labeled images in the database are used to structure the unlabeled ones and propose a suitable class for them. This assistance classification system selects images for the user which are interesting to classify according to a specific strategy and propose a label.

The framework is divided in two parts: an automatic part to “model the knowledge” and another part that requires the interaction of the user. Here we have a representation of the system, which is presented as three modules. As we can see, the first two modules are the ones where no interaction of the user is required, and the ones I will explain.

The first step consists in modelling the knowledge of the labeled images to predict the relevant label of the current unlabeled image. The knowledge is modelled using the following techinques.

- Neighbour images (a single one or K nearest neighbours): If image u is close to a classified image (or a set) there is a high believe that it will be labeled the same.

- Knowledge from all classes: Depending on the semantic interpretation of the images one image can be associated to several non-exclusive classes.

- Knowledge from all characteristics: This method allows to detect new classes or a new modality of a known class.

The second step is the active sampling module, where different criteria are presented to select the images that will be labeled by the user:

- Most positive unlabeled images: Sometimes names "most relevant". Here the system chooses the images that are easy to classify because the visual content is very similar to already labeled images.

- Most ambiguous unlabeled images: This strategy consists in choosing the unlabeled image which is on the limits of all the known classes. It can also be interesting to select images that are locally most ambiguous, the ones that are on the borders of a certain class.

- Most rejected unlabeled image: Theselected images are the unlabeled ones that do not correspond to any class. They have been classified as not belonging to any of the already existing classes, so this can be useful to create a new class or correct an already existing classes.

- Most conflicted unlabeled image: The information fusion with all characteristics can lead to a conflict about the inclusion in one or more classes, so they might not correspond to current known classes.

- Most uncertain unlabeled image: The two hypothesis (belonging or not belonging to the class) have similar probabilities, so it is impossible to distinguish one hypothesis from the others.

The third step is the final classification of the selected images.

User navigation through a tree-based visual index

2011-11-17T16:00:00.000+01:00

As a result of the integration of HCT indexing systems, GOS can give now a solution to the visual navigation of large databases.

The indexing engine stores it results as a hierarchy of directories in the file system where every node of the tree-structured index is described by an MPEG-7/XML file. Each of these files define the structure of the node with a list of child nodes and the sub-tree visual representation.

Browsing through visual trees is really easy with GOS. Once the index file has been loaded into memory from its root, user can go down to different nodes. In this figure it is shown the root of a 200.000 images tree-structured index with five children. Double clicking on the choosen sub-tree representation thumbnail, the system will load the XML file and display its child nodes. In the last level of the tree, a black frame indicates to the user that it is a leaf.

Users also have the opportunity to climb the tree using the arrow icon located in the first position of the thumbnail grid. A simple click allows the user to correct their previous navigation action.

Students pick full screen multiplayer as the hottest topic of the semester

2011-10-24T14:12:00.001+02:00

A couple of years ago I started a teaching activity where students would share an online reading extracted from the news or a technical blog. All proposed readings were qualified by the class, providing a ranking of the most appealing articles according to my students. Three years ago the top of the list was for an article about holographic videoconferencing and augmented reality on mobile device. This year the most valued topics in the course Audiovisual Communications were related to reproduction systems and augmented reality.

The favorite reading this semester was the announcement from LG of a new display that exploits the ·D TV technology for a completely new purpose: full screen multiplayer gaming. Instead of providing different images to every eye and generate a depth perception, why not sending completely different images to every viewer ? The proposed application would be those video games where different players are virtually located in different spaces. So far, the classic solution was to split the screen in as many parts as players, but with the dual view technology this is no longer necessary, giving a full 2D image to every player. I guess that with the addition of two set of headphones and DTV receivers, the same philosophy could apply to watching two different TV stations simultaneously. No more discussion at home about soccer or movie night !

Curiously the second and third most voted articles were very similar. Both of them are mobile apps that recognize a flat object (text or an image) and use them to perform some analysis whose result is embedded on the screen using the augmented reality paradigm. A first example is the Word Lens app, which detects text on screen, recognized through an OCR algorithm and translates it. So far, nothing really special, but the innovation comes from the generation of a new graphical layer with a similar font and color that replaces the real text on the screen. The student that proposed the reading tested the app and she admitted being impressed by the accuracy of the application.

The third position was for an article emulating the moving images in Harry Potter's Daily Prophet. The demo app in this case takes a snapshot of a picture on a newspaper and uses it to retrieve from the Internet a video that is embedded just in the location of the image. The proposed application was to provide an additional media linked to the newspapers, or wall ads on the street providing animated versions of them. It looks fun, but I am not sure about how practical is this application. This software is included in the Aurasma library of the British company Autonomy.

Other celebrated readings referred to holografic TV, the Siri assistant for the recent iPhone 4S and a wireless controlled mini-helicopter equipped with cameras.

Management of index servers from GOS

2011-09-27T11:30:00.000+02:00

The first system for database indexing is already built into GOS latest version to execute faster queries.

With the new set of tools for indexing, the user (developer profile) can run faster queries over HCT tools and create indexes as well. There are two running modes selectable in the preferences panel according to whether the index server is handled internally or externally from GOS:

External execution (expert user)

That is a simple implementation for those users who are able to run the indexing tools without using GOS. It will be used only as a search engine (query_request tool). In this case it has to be specified in which host:port your KSC server is executed and the index builder tool (hct_building)

Internal execution (medium user)

In this mode, GOS launches all tools involved in the indexing process. The KSC server is executed on the port selected in the preferences panel. Then it loads the index file that the user has selected from the search space panel. Such indexes must have been previously created, for example, with the index creation interface also developed in GOS.

This mode allows users to create their own indexes by opening a simple dialog. Through the dialog pages the user selects which image descriptors collections wants to add to the index and the visual descriptor index type. If more than one type is selected, GOS creates the same number of different indexes.

Fitting of Region Non-Matches to the Weibull Distribution

2011-09-26T10:33:00.002+02:00

A couple of months ago I explained one strategy I had designed to fuse the similarity scores obtained when comparing two regions in terms of shape, color and texture. At that time, the proposed approach considered an exponential curve whose shape was determined by a parameter beta. That solution though was based on an intuition that missed a firm statistical background.
Last month both Phd advisors agreed that this assumption should sustain on better grounds. In particular, they suggested me to base this normalization curve on a widely agreed probability distribution, such as the one proposed last year by Scheirer, Rocha, Michaels and Boult in their work "Robust Fusion: Extreme Value Theory for Recognition Score Normalization" (ECCV 2010).

Scheme proposed by Scheirer et al (ECCV 2010)

Weibull PDF

Their proposal sustain on the Extreme Value Theory, which basically provides an alternative to the Central Limit Theorem when, instead of focusing on the median values, the interest relies on the extreme values of a distribution. This approach matches the classical visual retrieval problem, where the data distribution refers to the similarity scores associated to the hits that conform a ranked list. The Extreme Value Theory applied to the retrieval case states that these scores will follow a Weibull distribution, a curve that is determined by two parameters k and lambda.

Weibull CDF

The basic idea of Scheirer et al. is to fuse the similarity scores obtained with different features by previously normalizing them through the the Cumulative Distribution Function (CDF) of the Weibull distribution, a transformation that will map any score to a comparable range from 0 to 1. I was glad to see that, for certain combinations of the Weibull parameters, the resulting CDF curve is in fact pretty similar to the exponential I had designed, an observation that supports the assumption that the Weibull distribution can provide good results in this context.

Scheirer et al. provide a valuable insight on how to use Weibull in the visual retrieval scenario. They noticed that, given a query, it is common to obtain a much larger amount of sample that do not match the query (irrelevant) than those that do match the query (relevant). Moreover, the probability distribution functions for match and non-match hits will probably be different. So they propose to focus on the non-match hits, learn their Weibull parameters and use the CDF of these non-match dataset to normalized all scores. And this is exactly the approach I report about in this post.

I am testing the proposed scheme to combine the similarity scores of color, texture and shape when assessing the similarity between two regions in an object retrieval problem. The first step I took was to visualize the histograms of both relevant and non-relevant hits for each type of visual feature and decide whether the data distribution I deal with may match a Weibull one. The obtained results are shown below for one of the train dataset splits defined over the ETHZ dataset.

Score histograms for relevant and non-relevant hits

The first observation is that indeed non-match distributions, on the right, are less noisy than the match ones because many more samples are available. Secondly, every visual feature presents different distribution shapes, so it makes lots of sense to estimate some parameters to fit a generic curve to every specific case. In some cases there are peak values at the highest and lowest bin, which basically indicates the behavior of a distance metric that collapses all distances over/below a certain threshold in the same value. Finally, there is a difference in the EVT case and the data I am displaying. Every obtained score corresponds to the best match between the query region and all the possible regions that are defined in an image, 99 in these experiments. So the results shown are already somehow extreme values. I have my doubts whether I should now only consider the top N non-match hits among this best intra-image matches, or just use all data to try to match the Weibull distribution. Given that the range of score values for relevant matches is similar to the ones for irrelevant, I decided to use the complete irrelevant histograms to be match to the Weibull.

So the next step to solve was how to estimate the parameters of the Weibull distribution to match its Probability Density Function (PDF) to the obtained histograms. I follow a solution based on least squares. Firstly, the Weibull CDF parametrized with k and lambda is operated to obtain a linear expression of the form y=bx+a.

Afterwards, the least squares estimation is applied to obtain the estimations of the k and lambda parameters that define the Weibull distribution.

I implemented the whole estimation in Java and generated some graphs that let me debug the complete process. The next figure compares the actual data histogram with the synthesized PDF.

Actual and Weibull synthesized PDFs

This second figure compares the actual CDF with the one generated with the estimated k and lambda.

Actual and Weibull synthesized CDFs

In general, the obtained curves seem to fit properly to the actual data distribution, so the obtained CDF can be effectively used to normalized the similarity scores for every visual feature. The next step will be to compare the retrieval results when fusing features with these normalization strategy to other option that I have been developing during the last months.

GOS Visual Search on Precomputed Indexes

2011-08-12T14:17:00.008+02:00

In my previous post it was said that GOS is ready to support different architectures to exploit the engine for visual indexing. As mentioned before, the memory execution mode has been published for developers of the image group.

In this mode the user is an expert in the field (HCT) and the indexing service is manually executed from a terminal and accessed by GOS by setting up the KSC server to query an image with query_request.

To keep improving, we wondered how to give users freedom to create and manage their own indexes separating user's images by domain, the image source, ultimately, different datasets the user wants to create. To do so, Carles Ventura has developed a very interesting tool,the database_indexing. It runs an hct tree to be stored on in a text file on the hard disk.

With the help of this binary, GOS is not only capable to perform hct queries(for developers) but also can read indexes previously generated with it and thus achieve greater freedom to search for all kind of users. With the option of reading previously created indexes from disk we significantly reduce the initialization of the indexing service, as it is not necessary no longer to create the free from scratch in every execution, it is enough reading the saved index from a file.

To sum up, the features supported by GOS have increased with the possibility of launching visual searches on indexed datasets. A single click internally handles a query by executing the KSC message manager, the hct_building tool and querying with the query_request tool in a way completely transparent for the user.

Should be noted that the user can perform multiple queries in one GOS session because it keeps the KSC and hct_building threads active listening for new query_request connections.

Evaluation of tags suggested from a video asset

2011-08-02T17:37:00.008+02:00

During this month I implemented a basic tag suggestion. The first task was a system that suggests tags from an image. I explained how it works in this post a few weeks ago. Since we work with assets and the textual metadata are annoted at the level of asset, the second task was to suggest tags from assets.

Tag suggested from assets

Every video asset n the system contains a collection of automatically extracted keyframes that provide a rough overview of its contents. For every keyframe of an asset, a list of tags is suggested in the same way as the first task. To obtain a result at the level of asset, the system combines the suggestions obtained at the level of keyframe. This combination is based on the sum of the scores of the tags.

Dataset

I created a database with a few assets of different topics in order to train the system. In particular I focused in the topics of Football, Table Tennis, Formula 1 and Parliament. Furthermore, I chose another group of assets that had the same topics that were in the dataset for testing the system.

Measures

The results have been evaluated in term of Average Precision at the level of assets. Also, the Mean Average Precision allows us to see if there is any topic easier to suggest than others.

ResultsConclusions

The low precision in Tennis Table is due to the system suggests tags of the topics: Football and Formula 1. This is because the visual similarity between the assets for testing and training are lower than Football and Formula 1 ones.

In order to evaluate properly the topic of Formula 1 we should test with more assets. The results are based on one visual descriptor, MPEG-7 Color Layout. Maybe, we'll obtain better results f we use other visual descriptors or a combination of they. Another solution is improving the system through object detection systems.

The best results are shown in the Parliament and Football topics. These results are due to the keyframes of these topics are very similar. Moreover, in the case of Parliament, a large part of their tags appear in all assets, so is easier to suggest tags.

Adaptation of the ETHZ Shape database to image partitions

2011-08-01T22:42:00.012+02:00

For the last year I have been working with the ETHZ shape classes dataset to run my experiments. As reported one year ago, the objects from the five categories were annotated with bounding boxes, which were mapped into the segmentations I use in my research. The problem of this approach is that, although simple, it introduces many noisy regions from the background that make it difficult to evaluate the next techniques by themselves. For this reason, it was decided to also exploit the pseudo-masks which are also provided in the dataset. And this has not been easy at all.

I write pseudo-masks because in fact they are contours of the annotated objects, but not all of them are not closed. In the region-based approach I follow, the basic work unit is the region which, by definition, is surrounded by a closed contour. So the first task I had to complete was to review all provided masks and manually add the pixels necessary to close them. The main problem was on the legs of the giraffes, but some other contours also had a very thin line hardly noticeable that needed to be closed.

The next problem was the variability in the file naming. Three object categories (applelogos, bottles and giraffes) use a suffix for the contour files, and the two other categories (mugs and swans) use a different extension. This diversity introduced some complexity when writing my scripts and Java software to manage the dataset. Moreover, in the first set every instance of an object was in a separate mask file, while in the two last categories they were all in the same image, so I had to manually split them and name the files consistently with the first scheme.

In order to work with the dataset and evaluate the impact of the rough selections with the bounding boxes, I designed an architecture divided in two stages. In the first stage, the goal was to obtain a binary mask of the object. Given the available software, I decided to segment the closed contours provided in the ETHZ dataset and then apply the same bounding box to regions mechanism I had previously applied on the original images. As a result, I would select a set of regions of the segmented contour image, which would define an object mask.

This stage also created some problems, as I discovered that the provided bounding boxes did not match the positions of the provided contours. Especially again in the giraffes category, many of the rectangles did not include completely the contour, so my mapping algorithm would miss them. The solution was to manually determine again the bounding boxes and modify the provided ground truth.

Once the mask for the object was generated, I mapped the mask on the image segments that had been automatically generated. I used the same mechanism I had developed last Summer for the TRECVID instance search campaign, with a new modification. The measure that determine if a partially overlapped region was to be considered was based now on the Jaccard index instead of the precision. In particular, I forced a minimum Jaccard index of 0.7 to select the region.

At the end the mapping of the ground truth masks on the image segmentations defined a set of regions that could be compared with the ground truth to assess their quality. As I was preparing a dataset to be used in further retrieval and classification tasks, I am not interested in working with a dataset that does not represent the objects that are supposed to be represented. For this reason, I decided to work only with those object instances whose representation on the image partitions is equal or better than a minimum value of the Jaccard Index, which was also taken as 0.7.

Finally, I completed my study by evaluating the impact of using accurate masks or rough bounding boxes to select regions on the considered image segmentations. For this reason I compared the Jaccard Index and the bounding box occupation of the the types of BPT masks (the one generated with the ground truth mask and the one generated with the ground truth bounding box). The results shown below clearly state that those objects with a larger occupation in the bounding box (apples, botlles, mugs) offer a better accuracy than those more complex objects, such as the giraffes and the swans.

Integration of a visual indexing engine for local and remote searches

2011-07-25T14:59:00.010+02:00

One of the problems that appeared when using GOS (Graphic Object Searcher), a user interface developed by the UPSeek group for the retrieval of similar images, was the slow searches. The possibilities on visual search offered by our engine were overshadowed due to the long response time after the user runs the query in a moderate/large database. The reason of this delay is the lack of any indexing structure for the stored data, a scenario that forces the search engine to explore the whole database in every query.

We have seen that GOS can perform image-based queries with a search engine developed for 32-bit Linux systems (deprecated within the research group). Then we saw its possibilities as expanded services including web based queries on UPSeek server. GOS became an UI that could be used in all operating systems and, therefore, opened to many other types of user.

GOS finally included the possibility of an interactive segmentation of images for region selection and region-based queries. Again, the response time of the search engine was an important step to resolve to provide good service that, on the other hand,improves every day.

The time has arrived for a very important step to be developed an efficient indexing system for image descriptors which support the query. This system is based on Hierarchical Cellular Tree (HCT), a process that creates an indexed tree in memory with a database file input.

The system consists of different tools that communicate each other using a simple socket language for exchanging data called KSC. KSCenter acts as an intermediary to receive all requests from the various tools and send them to whoever need them.

These HCT tools have been developed for indexing the Image Group visual descriptors' for Carles Ventura's master thesis:

hct_building: executes the hct tree stored in memory by using a database text file or previous trees stored on hard disk using database_indexing.
database_indexing: run an hct tree to be stored on in a text file on the hard disk.
query_request: run queries to the memory hct tree built by hct_building.

This new system is to be used from GOS in a transparent manner for the user to offer efficient queries both in results and runtime.

Moreover, this is the system that adopts the UPSeek server to provide the service remotely. GOS, in remote mode and selecting the port that is provided by the development team for each user, makes a webservice request to manage the SimilarImages execution of the query_request tool and return the results to the client.

With these new tools we can search on large databases (of order 200K nodes) within a very small time (seconds) but, what if the user prefers to have multiple search indexes? Separate all your images on different topics, situations, places… This freedom will be hosted by GOS and a new tool, the database_indexing, which generates trees and save them to disk for a faster creation and reading of the tree. But this is still a mode of execution to be developed and published in the future.

GOS queries become versatile and powerful over a simple GUI used for all kind of users.

Step by step of a tag suggestion from an image

2011-07-06T21:25:00.013+02:00

In order to get ideas for start to work in the algorithm of tag recommendation, I will summarize the description of the algorithm found in the paper Scalable search-based image annotation by Changu Wang, Feng Jing, Lei Zhang and Hong-Jiang Zhang.

They focus on annotation of large personal image collections. Unlike web images that have rich metadata such filename, URL and surrounding text for indexing and searching, personal images have little textual information. They propose a scalable search-based image annotation (SBIA) algorithm which is analogous to information retrieval.

The algorithm has four steps:

Step 1. Content-based image retrieval
For a target image, a typical CBIR technique is used to retrieve a set of visually similar images denoted by S. For each retrieved image, the distance between image i and the target image is denoted as Dist(i).

Step 2. Text-based keyword search
For each retrieved image i a text-based keyword search process is used to rank all the related keywords. The related keywords are the ones that appear in title or description except the stop words.

For each retrieved image i, the set of related keywords are denoted as Ki and the combination of all Ki for all images in S is denoted as K. For each keyword Kj in K, its relevance score to retrieved image i could be calculated with two strategies:

1. Prominence score: it reflects the prominence of keyword to annotate an image.
where occurrence(i, j) denotes the number of Kj in title or description of retrieved image.

2. IF-IKF: It is based on the TF-IDF weighted scheme that is used in information retrieval. In this paper the images correspond to the textual terms, while the annotation keywords correspond to the documents in information retrieval. Therefore, a keyword could be considered as a document with several related images being terms.

So image frequency (IF) is defined as the number of retrieved images in S that contain Kj. And the keyword frequency (KF) if an image could be defined as the number of related keywords of the image.

As a result, each retrieved image has a textual descriptor. This textual descriptor is represented by a list of keyword-score pairs.

Step 3. Fusion algorithm
The ranked lists of all similar images in S are combined to get the final candidate keyword of the target image. Considering that more similar image should have more impact on the final annotation results, they use the following expression to score and rank the keywords Kj:
where f(*) is a function that transforms distance to similarity.

Once the relevance score of each keyword in K is obtained, they can pick up the final top N candidate annotations.

Step 4. Re-ranking annotations using Random Walk
Finally, the candidate annotations are re-ranked using Random Walk. The basic idea is that highly correlated keywords should be ranked higher. Consider a graph G whose nodes represent a candidate annotation wi and its edges are weighted. This weight is defined based on the "co-occurrence" similarity.

They used a image search engine called EnjoyPhoto to calculate this weight. Each keyword wi will be used as a query to query EnjoyPhoto. The number of search results is denoted as num(i ). For two different word wi and wj, “wiwj” will be used as the query. The number of search results is denoted as num(i, j ). The weight of the edge between wi and wj is

then calculated as:

Once the graph G is constructed, they compute the Random Walk algorithm, as we did in the Reranking algorithm, to suggest the best candidate annotations for the target image.

Normalization of visual distances for fusion in retrieval

2011-07-06T17:49:00.049+02:00

In my previous post I presented why normalizing feature vectors was discarded when working with three types of visual descriptors defined by the MPEG-7 standard. The proposed direction was to focus the normalizing efforts on the similarity metrics (distances) that are proposed for each of these descriptors.

During my first tests with the distances, I noticed that the dynamic range for each of them was completely different. While all of them would be zero-valued when comparing two identical descriptors, the maximum possible figure was variable depending on the type of descriptor. So I decided to compute all mutual distances between the regions of my dataset and determine, for each type of descriptor, the mean value. The mean was chosen in front of the maximum value because in visually empirical tests, pairs of regions completely dissimilar from the descriptor point of view were already measured with distance values below the average. So it was considered that the subjective point of "different" applied to all comparisons with distance equal to the mean and above. So after 317,430,375 comparisons, the three mean distances were learned for every descriptor were: 1.155 for Dominant Colors, 0.302 for Contour Shape and 9.349 for Edge Histogram.

These maximum distances were used to linearly normalize the raw distances so that the maximum distance would be mapped into 1.0. I thought this might have been enough but, when I queried the database with a multicolor-stripped Apple logo, I obtained the results I previously reported for color, texture and shape.

The main problem of these results is in the obtained score values (inverse of the distance). If a user would be shown these figures, the first thing to be noticed is that the values are "very high" as they are supposed to quantize the degree of subjective similarity with respect to the query. In addition, the second criticism these results would obtain is that the values obtained for one descriptor are not comparable with the ones obtained by others. This second problem prevents any early fusion of the distances because values are not comparable from a perceptual point of view. It is necessary then to apply another strategy for normalization.

The chosen approach is based on the figure below, where an alpha value estimated for each visual descriptor is mapped into an beta value whose subjective interpretation in term of similarity is harmonized. In addition, the zero (identical) and mean (different) points are also forced for coherence with the original distance metric. The mean point (mu) of the distance was interpreted as completely different because empirical problems show that the notion of "completely different" was completely satisfied at that point (and probably earlier). So all distance values are mapped to a corrected 1.0.

The determination of the (alpha,beta) pair is they key to solve the whole problem. The adopted solution is based on the assumption that a user expects to find "similar" matches over 0.5 and "not so similar" results under this figure. So the adopted beta was 0.5.

The problem then turns into how to find the threshold between "quite" and "not so" similar. The propose solution assumes that, given a ranked list, this point is located at the top hit that defines the sub-ranked list that maximizes the F-0.5 score. This score is supposed to define the first K elements in a rank list that offer a good trade between precision and recall, priorizing the precision. With this criteria adopted, I ran again retrieval experiments the ETHZ dataset and measured the distance associated to the Kth element in the obtained ranked list.

Not all ranked list were used because in some cases the descriptor was not good for the query, so considering them would introduce noise to the measures. This is shown in the graph below, where in some categories some descriptors perform worse in terms of MAP than even the random case, which is adopted as a baseline. The decision on what ranked lists to use was based on the ranked list's MAP, and only those ranked list whose MAP was higher than the random MAP plus 3 times its standard deviation were considered. This way, it was expected that the considered descriptor was useful in the query that generated the ranked list. Moreover, each threshold was also weighted by the ratio between the ranked list's MAP and the random MAP obtained in the class where the query belongs to.

Once the (alpha,beta) point is defined, multiple options exist for the design of the correction function. One option would be to define to two linear segments joining the the three points in two stages, another one would be to define an exponential curve that would include the requested (alpha,beta) point. If more (alpha,beta) points were defined, multiple segments could also be estimated to obtain a more accurate function.

The exponential function was chosen for simplicity on its implementation, so one of the following expressions was used depending on the relation between alpha and beta.

After experimentation, an alpha value was learned for every visual descriptor. In all cases low values of alpha were estimated (0.7-0.8), proving the previous intuition that the concept of similarity if diluted long before the mean value of all distances is reached.

Finally, the scores obtained in for the Apple logo query are now closer to an harmonized interpretion intra-descriptors thanks to the introduced correction.

MPEG-7 Dominant Colors

MPEG-7 Contour Shape

MPEG-7 Edge Histogram (texture)

Acknowledgments: Thanks to my colleagues Yan Wang and Rongrong Ji for sharing their views and ideas on this topic.

Discarding the normalization of feature vectors from MPEG-7 visual descriptors

2011-07-06T16:20:00.015+02:00

Last week I reported on the evaluation of three visual descriptors for image retrieval through region matching. These features quantize three independent and complementary visual cues: color, shape and texture. The experiments proved that each of them separately is valuable to describe the five object categories that were tested. The next question to be answered now is, as largely reported in the literature, whether their combination increases the overall performance of the retrieval system.

A couple of years ago I explored the possibility of using the Mahalanobis distance, a metric that takes into account the distribution of the two samples to be compared in the feature space. Its computation basically requires the previous estimation covariance of the multidimensional Gaussian distribution of the feature vectors that represent every observation. In those cases where feature dimensions are not correlated (independent), the expression is simplified and only depends on the standard deviation in every dimension. Moreover, on those cases where all dimensions present a same and unitary standard deviation (white distribution), the calculation further reduces to the Euclidean distance.

Assuming the independence of each feature dimension, the simple Euclidean distance can be used by applying a linear transformation A to every input feature vector x and generate a whitened distribution of feature vectors y. Such transformation can be obtained by applying the Singular Vector Decomposition on the covariance matrix.

The final system would require the estimation of the mean and covariance of the feature vectors during a training stage, that would determine the whitening transformation Aw. During retrieval, every input sample x and y would be first whitened before measuring their distance with the Euclidean distance.

The application of these principles to my retrieval problem would allow a fast computation of the same Euclidean distance for every type of considered visual descriptor (shape, color and texture). However, this approach presents an unsolvable problem in my framework. The MPEG-7 visual descriptors I work with are not normally simply a feature vector whose elements have the same interpretation. For example, in the case of the MPEG-7 Contour Shape, the descriptor contains the curvature and eccentricity of the region, as well as the normalized positions and strength of the inflection points. On the MPEG-7 Dominant Color descriptor, the length of the vector may change in every observation, so for every region a variable amount of one to eight dominant colors might be determined. In fact, the standard suggests a difference distance for every visual descriptor, a metric that exploits the different types of information contained in the descriptors.

For this reason, I concluded that the classical normalization techniques on the feature vectors would not apply in my context. My normalization efforts should be applied on a later stage, on the distances themselves.

Tag recommendation from an image

2011-07-04T20:39:00.008+02:00

In my latest contributions to this blog I talked about the use of TF-IDF as textual descriptor and the implementation of a textual similarity graph from the metadata associated with an image. Last week I spoke to Xavi and we defined the tasks that I have to do this month. These include a system that suggests tags from an image.

The idea is: given an image search, find the most visual similar keyframes in the database. As we now have the new text descriptor we can represent each asset with a TF-IDF descriptor (Rembember that the available metadata are in general related to the whole the level of asset, not to specific keyframes). From the textual descriptor associated with the asset of the keyframes retrieval, the system will search the most representative terms and will suggest it to tag the keyframe or make a text query.

This way, we exploit the same principle that guided my bachelor thesis: using automatically extracted visual descriptors from the keyframes and manually generated annotations at the asset scale to generate new annotations at the keyframe scale.

Therefore, the first big problem to solve is how to determined what are the most representative terms among all the textual metadata associated to the assets that contain the most similar keyframes to the query image. Our first idea is to make the sum of the TF-IDF weight for each term of the descriptors. The system will obtain a rankedlist sorted according to the sum of TF-IDF weights. Then it will suggest the firsts tags limited by a threshold or a maximum number o terms.
But we have to consider other alternatives. So in my next posts I will explain the solution chosen.

JSON and Java Representations for web data exchange

2011-07-04T16:57:00.009+02:00

All Java Web Services developed in Java by UPSeek group support XML data exchanges and recently have been adapted to work with JSON (JavaScript Object Notation). Its simplicity has led to widespread use for web data exchange instead of XML representations because JSON is not a document markup language. XML carries a lot of baggage, and it doesn't match the data model of most programming languages. This change has meant a great advance for UPSeek because it is a lightweight and allows us to a more convenient communication with our partners.

With JSON in the system we got more quickly and easily deserialization (process in which a text represententation become a java class or vice versa) than with XML representation. It also expand the possibilities of WebServices to more than one company.

With the new services published it was noted that the amount of data transferred was very high and we needed to use our own complex Java classes to run processes on the server. Because of the many attributes that make up these classes and, therefore, calls to the services were large strings, we decided to start using the Jackson, a java library that simplifies this work task.

Then, there are two types of responses offered by our services: XML representation or String representation (JSON) as the type of user or company that connects to the server.

Comparing MPEG-7 Color, Texture and Shape Descriptors for Region-based Image Retrieval

2011-06-30T22:46:00.012+02:00

Today I am happy to announce the very first results which are to be included in my Phd thesis. These results aim at evaluating the individual performance of three different MPEG-7 visual descriptors computed on regions. There are the Dominant Color, Texture Edge Histogram and Curvature Scale Space (CSS) Shape descriptor. Each of these descriptors is defined by the MPEG-7 standard together with a recommended similarity metric. This metric was taken as a base and was fine-tuned to improve the obtained results.

As an example. One of the experiments would consider a query region of an old Apple logo with very characteristic visual cues: six distinctive colors, a vertical edgy texture and a very recognizable shape for the logo (only the big segment, the leaf was discarded because only one-part queries are supported by the system right now).

As a result, if three visual descriptors are available, there exist three different criteria to assess the similarity between the query region and the regions in the target database. The three obtained results are the following:

MPEG-7 Dominant Colors

MPEG-7 Contour Shape

MPEG-7 Edge Histogram (texture)

The scores shown in these screen shots are normalized by the mean value of all distances when comparing all the elements in the dataset between each other.

This is only the result that might be obtained with one query. In general, when the object of interest appears in the target image, this is correctly spotted among the other dozens of regions that are defined in the image. However, in some cases image that do not represent the query object are ranked better than others, so it is clear that the proposed system is not perfect at all.

In order to obtain more representative results, a broader experiment was conducted on the ETH Zurich Shape dataset, divided in five categories, and use each defined object as a query to a database that contained the rest of the dataset. The query was formulated by matching the query object with the segments defined on a Binary Partition Tree (BPT), and use this mapping as the region of support for the query. The visual descriptors were extracted from the query region and compared with the visual descriptors of the segments defined by the BPT of every image in the dataset. For each of them, the best matching regions was identified and the similarity to the query was used as the score over which building a ranked list. So for every query a ranked list was built, its Average Precision computed and finally obtained a Mean Average Precision for each of the five categories. The obtained results were compared to random ranked list used as baseline and are shown in the following graph:

Results indicate that the given name to the database, ETH Zurich SHAPE dataset is an accurate one, as the shape descriptor is the one that provides best results in almost all categories (in the case of mugs, color outperforms CSS Shape). The table also proves that the engine performs better than a random ranked list in all categories but for Swans, which presents many segmentation problems. However, the visual diversity of the objects in the dataset is an important limitation when searching by only considering the visual features of a single query region. Future experiments will aim at estimating how can the different cues be combined and whether a retrieval based on a previously trained classifier that would consider more visual diversity would improve the performance in terms of MAP.

(reviewed on the 8th July 2011 with updated screen shots)
(reviewed on the 9th Jul 2011 to introduce the graph of results all over the whole dataset)

Average Precision of a Random Ranked List

2011-06-29T23:11:00.010+02:00

I have recently started testing the retrieval algorithms developed for my thesis on the ETHZ shape dataset. These dataset contains a collection of 255 images that contain 289 instances of five different categories: Apple logos, bottles, giraffes, mugs, and swans.

As in any retrieval experiment, the results obtained is a ranked list of results according to the estimated relevance of each item in the test dataset when compared by a certain query. A typical measure for the quality of these ranked lists is the average precision (AP), which basically computes the precision of every relevant result obtained at the position where it appears in the generated ranked list.

When I started obtaining results for the techniques we have been developed, I started wondering but kind of results should I expect. An initial (and wrong) idea was that if the test dataset contained 5 categories, the base figure to beat would be a value of AP=0,2 for every category, as in a classification problem. But the results I obtained were not normally around this value and, in fact, they were category-dependent. These initial steps help me realize that: a) my software was buggy and b) the random results that you would expect from a very buggy implementation were not generating uniform 0,2 AP values for every category.

So, apart from working hard on debugging the software, I also started wondering what would be the AP for a random solution of a retrieval problem. Given that I had a computer to use, the first approach to the problem was to find an empirical answer to that question. So I just simply programmed to generation of random ranked lists and, in one of the trials, I obtained these results:

They prove that the AP between the five classes is related to the amount of instances of every class. The more instances in the dataset, the higher expected AP in a random ranked list.

The next question was then how this expected AP could be related to the amount of instances. A first step was to build a toy example with a test dataset of only three elements belonging to two classes: one instance for class A and two instances for class B. A uniform random distribution of ranked list could be composed as:

1.A, 2.B, 3.B
AP(A) = 1
AP(B)= 1/2 (1/2 + 2/3) = 5/12

1.B, 2.A, 3.B
AP(A) = 1/2
AP(B) = 1/2 (1 + 2/3) = 5/6

1.B, 2.B, 3.A
AP(A) = 1/3
AP(B) = 1/2 (1 + 1 ) = 1

As a result, the expectation for the first class is E{ AP(A) } = 0.61 and for the second class is E{ AP(B) } = 0.75, which does not directly correspond to the proportion of elements of each class in the test set, which would be of 1/3 and 2/3 respectively.

The remaining question is then, how to analytically compute the estimation of AP(x) where x is a class in a randomly generated ranked list ?

(to be continued and solved soon...)

Results and conclusions

2011-06-22T15:41:00.000+02:00

RESULTS

I developed a launcher application that meets the HbbTV standard it's totally configurable by the programmer. I have also helped the Activa Multimedia team to improve their applications.

CONCLUSIONS

I have done some improvements and tests. I also have seen that HbbTV is an standard that needs more development, and broadcasters are not meeting the specification with all requeriments.
In my opinion, this standard is more useful than MHP, so TVC, Telecinco and other broadcasters are developing applications for this new technology.

PERSONAL CONCLUSIONS

This experience has made me grow in two ways: the personal and the professional way.
I saw too that working as a programmer is more interesting for me than I have ever thought.

You can read more about this project in my thesis document.

Segmentation of the breast region with pectoral muscle suppression and automatic breast density classification

2011-06-15T20:24:00.058+02:00

It has been long time since I wrote my last article because I was working in Belgium on my Master Thesis for the degree of Telecommunication Engineering. I would have preferred writing earlier but I was really busy first reading documentation, implementing the source code and performing the experiments. I've chosen to write now because I've just defended my thesis!

I've been working with Benoit Macq and Vincent Nicolas in the ICTEAM of the Université Catholique de Louvain (UCL), medical image processing field. My Masther Thesis was part of a big project called MammoNote, a standard platform for helping the annotation of digital mammography and diagnostic of breast cancer.

I would like to present a little bit what I have done during these months and the obtained results. My final goal was to implement a new method to segment and classify automatically mammograms according to their density. Lets catch up the subject a little bit and explain the need of this method.

Breast cancer is one of the major causes of death among women. Suspicious breast cancers appear as white spots in mammograms, indicating small clusters of micro-calcifications. Nowadays screening mammography is the most adopted technique to perform an early breast cancer detection. However, the accuracy of the computer-aided systems decreases due some factors like density of the breast, presence of labels, artifacts or even pectoral muscle in the mammogram image. So we wanted to obtain a new image only with the presence of the breast without any other element that could decrease the obtained classification rate.

So, my first objective, after reading all the documentation, was implementing a method to segment the breast from the rest of image regions that can be present in a mammography, basically: background, labels, artifacts and pectoral muscles.

Labels removal

For performing the removing labels step it was used a region growing algorithm, from the library of image processing ITK and implemented in C++, called ConnectedThreshold. The base of these algorithms is grow from an initial point, normally inside the desired element to segment, and evaluate if the neighbourhood pixels if they should be considered as the desired object or not.

The Insight Toolkit (ITK) is an open-source platform used for performing registration (aligning and finding correspondence between data) and segmentation (the process of identifying and classifying data extracted from digitally sampled representation acquired from medical images as CT or MRI scanners) among other applications. It's a processing image library very used in medical applications and already used in the medical software implemented in our department.

We can find 4 different type of noise that appear in these mammogram images:

High intensity label.
Low intensity label.
Scanning artifact.
Tape artefict.

In the following figure we can see an example of each one:

So our objective in this step is achieve to remove all of them from our mammogram images. The obtained results were almost a perfect rate of removal except for one scanning artifact. We can see them in the following figure where in the first image appears the breast with all the noises present and in the second one with all of them removed:

Pectoral muscle removal

The following step, remove the pectoral muscle from the mammogram images, was a more complicated task because of different dimensions, shapes and pixel intensities from the muscles in the images. The Hough transform was used, a common used technique to detect geometrical shapes in images. In our case, we wanted to detect the straight line that separates the muscle from the breast and apply a mask to keep the image without it. It was also necessary to apply some pre-processing procedures to the images like smoothing, finding the orientation, extract a region of interest that contains the pectoral muscle and apply an edge detection filter. In the following figures we can see some examples of the technique and the obtained results:

Density classification

Then we decided to continue with the density classification task. The used procedure has its base in a previous work and I have adapted to the actual study case as well as I also added some new features like a cross validation method, using texture features in the feature vector or presenting the results as recognition rates and confusion matrices.

The classification algorithm extracts a large number of random sub-windows, possibly overlapping, at random positions and random size. Then these sub-windows are resized to a 16x16 pixels and it is created a feature vector only using the pixel values. One of the improvements was adding other values to this vector, like texture features as skewness, kurtosis or smoothness.

Then, with the extracted sub-windows of the train images, after a process of 10-fold cross-validation, the algorithm trains a classifier based on an ensemble of decision trees using random thresholds and splitting the nodes until reaching the final class.

For the testing step, the extracted sub-windows from the test images are propagated through the trees and the probability to belong to the class is averaged for all the samples and for each tree finding the final image class.

We have done a lot of experiments, varying several parameters, to find the ones that gave us the best recognition rate. Finally we found that the best results were achieved using the whole original image, sampling the images with as much sub-windows as possible, using a minimum number of elements in a node to initiate an split equal to 4 and adding texture features to the vector.

The results are quite promising because we have achieved the best recognition rate compared with our documentation referred to the current state of the art. In the following images we can see our best results adding or not texture features and a chart showing the different used methods and their corresponding rates.

References

[1] K. Bovis and S. Singh. Classification of mammographic breast density using a combined classifier paradigm.

[2] S. Tzikopoulos, H. Georgiou, M. Mavroforakis, N. Dimitropoulos, and S. Theodoridis. A fully automated complete segmentation scheme for mammograms.

[3] M. Mustra, M. Grgic, and K. Delac. Feature selection for automatic breast density classification.

[4] T. MacGahan, M. R. Pacheco, and A. Wong. A hybrid approach to automatic mammography classification.

Conclusions

To conclude this article I want to give my opinion about the Erasmus exchange. I think it's a very positive experience to go abroad and make the Master final Thesis because besides of learning other language, French in my case, you soak up the culture of the country, travel a lot, meet new people and have fun!

Interactive Image processing demos for the web with Wt

2011-06-12T16:35:00.006+02:00

After four months of hard work, I am proud to present the results of my thesis, which are a framework, some utilities for this framework(called widgets) and a little web demonstration.

To do a little remembering, I was trying to demonstrate the UPC Image and Video processing group algorithms from ImagePlus, a software platform from them , to the web. You can follow the main stream of the project by reading all my articles

Speaking about this framework, it is not very easy to create a web page and even less in C++. The main advantage of the web framework I have built is that you can create a web page like this in less than 3 lines of code.

By doing that, you get an entire web page with its header, its logos,footer and so on.

This approach represents an improvement for programmers in the UPC Image and Video processing groups, who did not even use graphical interfaces for their demonstrations. Now, they are able to create web demonstrations in a fast and easy way, without learning web technology (PHP, HTML, javascript, etc.)

By doing that then, you get a whole void interface.

Furthermore, I developed some utilities to use with the web demonstration. My advisors and I thought that It was too difficult to render a image in the web, using the main technology used in this project, Wt. (If you want to know what is it, please go to my last articles where I spoke about it)

Then I created an intermediate layer, some utilities that automatically call Wt functions and do the usual work, like render a image from ImagePlus to the web. Now, to render an image you just have to create an object of my class, "WebImage" and use the "paint" method. Quite easy, or at least, easier than before...

The other utility I've made is a Bibliographic zone in the interface. The utility just displays a formatted bibliographic text given 4 arguments which are the authors, the name of the article, the publication and the URL.

I also reserved a place for bibliographic texts in my interface, and I made it easier to put bibliographic texts, just writing a line of code for each reference.

And finally I made a web demonstration of an ImagePlus algorithm. It is called BPT and consists on creating a tree by joining the littlest regions to form bigger regions, until there is just one region which is the whole image.

This demonstration contained lots of things, an slider to navigate for that tree, a wheel event which actually does the same of the slider, the original image, the image which is being processed, a file uploader and a combo box to select the image from the server. Also a button to show contours of every region.

Watch it by yourselves.

Main contributions and results

Because of the length of this article I will try to summarize the conclusions of the thesis.
The first conclusion I get from this project is that now people from UPC Image and Video processing group are able to do web demonstrations and show them online, so they now can be seen by all over the world.

At the end, there is a framework which allows you to create a web interface in a few lines of code, two widgets, to render an image and to format a bibliography very easy. Also there is the web demonstration which you can see here.

demonstration online

Mobile devices and future work

Besides, they don't have to learn web technology which make it even easier.
The next thing we can think about is mobile demonstration, because in this architecture that we are using the client (phone or computer) does not work too much, the server is who takes care of everything.¡, or almost everythig, so we can think in mobile demonstrations by adapting all the layout to mobile devices.

And finally, other types of widgets and a lot of different things can be integrated in the demonstrator and in the developer's demonstrations. Really, I expect to see soon some demonstration from someone else.

If you want to see the whole document, you can go to Xavi's professional web page where you can find my thesis as well as my friends Martí and Eli's thesis which have been directed by Xavi this spring.

And at last but not least, the oral presentation was good, I explained everything in my own words. At the beginning I was kind of nervous, but after everything was right. I was and actually I am very happy because I got a "distinction"(10).

Evaluation of object detections and segmentations

2011-05-07T17:27:00.010+02:00

I am currently evaluating the algorithms I have developed for automatic object detection and segmentation. As my techniques are based on hierarchical partitions of the image, I have taken a similar work from Gu, Lim, Arblelaz and Malik (Berkeley) as a reference. In their paper they used the ETHZ shape dataset, which has been proven a good first test because its size is small (256 images belonging to 5 different categories) and provides a segmentation ground truth for evaluation. Two types of experiments can be run on these data: object detection and segmentation.

In the object detection case, the goal is to determine if an object of a certain category is represented by an image and, if so, provide a rough estimation of its location. The location is expressed through the bounding box and a detection is considered correct if the bounding boxes of the detected object and the annotated ground truth overlap on a ratio higher of 0.5 when compared to the union of two boxes. This criterion is known as the Pascal criterion, as it is the one used in the Pascal Visual Object Classes Challenge.

As this is a detection problem, the decision of whether the object is present or not is usually dependent of a certain threshold that sets a compromise between the precision and the recall of the detections. For this reason, providing a detection measure is somehow tricky, as results must take into account this balance. To solve this issue, detection rates (recall) are given together with their associated False Positive detections Per Image (FPPI). By doing so, the detection experiment can be run at different thresholds to will provide different detection rate-FPPI pairs.

Unfortunately it is highly improbable that the output of an experiment will exactly provide the reference FPPI that wants to be measured. So the result of running the detection algorithm at different thresholds will be a set of points that are to be interpolated to find and estimation of the detection rate at the desired FPPI. In my case that was laborious, as I had to try different detection threshold smartly, generating measures as close to the FPPI as possible so that the interpolation of the detection rate was as accurate as possible.

Moreover, as in any classification problem, experiments must be run on different train and test partitions of the annotated dataset. I followed the proposed scheme of estimating the detection rate of every category at 0.3 FPPI for five trials. The partition was generated randomly, as Eli explained last week. As a result, a mean detection rate and its deviation was computed for every category which, finally, are also averaged to provide a single result.

Once the detection performance is evaluated, the second problem can be handle: how to evaluate the quality of the segmentation ? This second part is not that clear on the reference paper, so I made some guesses that might need to modify in the future. To my understanding, the evaluation of the segmentation should be a separate from the detection, so I decided to evaluate the quality of the segmentation only on those detections considered correct by applying the Pascal criterion.

If only considering correct detections in terms of bounding box, the object segmentation can be evaluated at the pixel scale. The object detection segments the image pixels in two classes: positive when representing the object, negative when not assigned to the object. If a pixel-wise truth is available, the amount of true positives as well as true and false negatives can be counted. These measures can be used to compute the precision and recall of the object segmentation, and can also be combined in a single measure as the Jaccard Similarity Index, as Neus presented when evaluating interactive segmentation. However, in the Gu et al work they seem to only consider the precision, so I took the same criteria for comparison purposes.

The measures are ready now but I still need to improve the generation as the ground truth, as I am currently considering the masks generated by mapping the ground truth bounding box onto the image segmentation generated with the Binary Partition Tree technique developed by Jordi Pont-Tuset. Although results are reasonable, I will introduce two modifications: firstly use the accurate contour also included in the ground truth data instead of the bounding box to map it into my image segmentation. Secondly, compare the measures with the actual mask in the ground truth, which will also provide an estimation of the overall performance of the system: Jordi's image segmentation and my object detection+segmentation.

Dataset generation

2011-04-21T16:32:00.008+02:00

In this post I will discuss two different techniques for dataset generation that have been studied and implemented for my project on semantic shot detection: modified K-fold cross-validation and repeated random sub-sampling

For testing a multiclass classifier, the annotated positive and negative instances of all classes have to be split into a trainset and a testset so the trainer and the detector use different sample data for the experiment. Because of the arquitecture of the classifier used in my project, based on binary classifiers, each class annotations are partitioned in order to train and test each semantic shot classifier.

In this case, as there were few labeled instances, 80% of the each class sample data has been used to train its classifier while the 20% left has been used for detection. As there are classes with a few positive instances and much more negative instances (all the positive instances of the other classes), each percentage has been applied separately to positive and negative instances, ensuring at least positive instances to train the system.

All instances belonging to the trainset clutter class have been deleted so the trainer does not include the class when generating the model, but the detector can measure its performance when detecting.

Modified K-fold cross-validation

The K-fold cross-validation algorithm generates K different data subsets, making sure all data is used for both training and detection for each iteration. As a modification of the K-fold cross-validation, where data ara partitioned into K equal parts and the ratio between the sizes of the different subsets is not defined by the user, the parameter K has been calculated automaticaly to build the testset and trainset for the given trainset percentage, allowing more flexibility. This procedure is repeated K times and the predictions of the K dataset are averaged.

The whole procedure can be done several times with aleatory data order for each iteration. The following picutre illustrates one iteration of the process:

Repeated random sub-sampling

Random sub-sampling consists on sorting the data in an aleatory order and then dividing it into the dataset and trainset for the given percentatges. For each iteration a single trainset and dataset is build. As in the K-fold cross-validation the algorithm has been applied separately to each class to train each classifier.

Conclusions

Random-subsampling does not ensure all instances are both used for training and detection, but more iterations can be done with less time, as random sub-sampling represents 1-fold iteration of our modified cross-validation. Predictions using this method give a realistic estimation of the classifier performance with external validation data, while cross-validation usually gives overly optimistic estimations.

Because of the time cost of the K-fold cross-validation, the diversity of the datasets that already offers random sub-sampling and its realistic estimation, the repeated random sub-sampling algorithm has been chosen for the experiment dataset builder.

Reranking at the ACM ICMR in Trento

2011-04-21T11:33:00.007+02:00

Last Monday I had the chance to present my joint work with Monica Alfaro Vendrell and Ferran Marques Acosta in the ACM ICMR 2011 held in Trento. This is a new conference resulting of the fusion of the (now deprecated) CIVR and MIR.

Our contribution proposes some modifications to the classic solution for image ranking based on the random walk, originally proposed by Hsu, Kennedy and Chang in 2007. As Monica reported in this same blog last Fall, we introduced two types of filtering in the Similarity Graph to boost diversity while keeping the relevance estimated during the random walk. You can see the poster we prepared in the next figure.

Two additional proposals were introduced in the paper: a feature fusion based on node probabilities instead of feature similarities, and a new metric to measure the diversity of video assets. This last contribution was introduced to adapt the classic S-recall measure to our scenario, where every keyframe is always associated to one (and only one) asset.

I received several questions and suggestions about our work. The first thing I realized is that many attendees called the random walk algorithm as Pagerank, the famous adaptation of the technique at Google to rank the search results. An interesting proposal came from Benoit Huet (EURECOM), who suggested that in order to prove the impact of the probabilities fusion compared to the similarity ones we could compare the two approaches in our experiments. He also wondered whether the diversity measures we obtained were related to the types of queries we considered and, to be more precise, on the amount of relevant assets.

Finally some other visitors wondered what would come next. On the short term, next July Monica will introduce textual features through the TF-IDF descriptor extraction she implemented last Winter. So for sure the evaluation of the gain by adding textual features will be a must experiment. If trying to go one step beyond, we have long discussed about introducing the mutual reinforcement approach proposed last Summer at CIVR 2010 by Ting Yao, Tao Mei and Chong-Wah Ngo from VIREO at City University of Hong Kong. Their work has continued wiith a new contribution presented also at ACM ICMR by Hung-Khoon Tan and Prof. Ngo. In this paper they explore different fusion strategies in the context of a similarity graph for every different feature.

Apart from the official program, I must highlight that this was the first congress I attended with some real activity in Twitter under the hashtag #icmr2011. This tool made the conference a bit more exciting and helped discussing serious and not-so serious matters related to the multimedia retrieval community. I am pretty sure that online discussion is a practice that it is here to stay, and that also helps as a personal log of the most interesting proposals seen on the slides or posters.

I cannot conclude without highlighting the beautiful landscape that surrounded us in Trento. The town in majestically surrounded by the Alps and a graceful river offered me the change to keep a bit fit during these too much pasta days :)

Web algorithm demonstrator architecture

2011-04-11T21:57:00.004+02:00

Apart from the demonstration, this week I've been preparing the interface of the web page. It wasn't an easy task. We can talk about two kind of interfaces, the first one, the programmer interface, whose name is “GPIapp”, and is a class which allows programmers to do the most common functionality such as change the title of the demonstration, or set a little description about this algorithm in an easy way.

This interface succeeds in that all the files of the web page I've been working with, classes GPIapp, GPIheader, GPIcontent, GPIfooter and GPIdemo are now transparent for the programmer, because they have just to inherit a class from GPIapp and they have already got the whole web page in the demo, and all they put inside, is going to be placed in the correct position.

This is very important because programmers are able to make web pages very fast and without any knowledge of neither HTML, CSS nor other web technology, and also they are avoided to know too much about Wt.

This is the hierarchy of the new classes. As you can see, almost all the classes inherit from WContainerWidget, this is because this one is the "div" element in HTML, and I needed a framework for my web page.

The second interface, as you know is the graphical interface that you can see when you enter at the web page. The design of this interface is a flexible design. It means that it doesn't matter what resolution or display size you have, the web page is going to fit itself to the screen.

Of course the page allows programmers to put a description as long as they want, and the page is resized to fit that text.

Dynamic web demo of image segmentation

2011-04-10T20:18:00.009+02:00

After long time understanding Wt, the C++ library which I have talked about in my last posts, I am glad to release my first web demonstration. This demonstration consists on an image and a slider.

The algorithm I want to demonstrate in this occasion the binary partition tree creation algorithm, an imageplus software that creates a hierarchical partition binary tree with the uniform regions of the image.

Then, the slider at first determines the maxim number of regions the algorithm can segment. This is the 100% of segmentation regions, if the slider is moved down, the number of regions for the segmentation decreases.

In the worst situation, for instance, I had a completely uniform (plain) image, the slider just would have allowed one level, because the minimum is one region, and the maximum is also one region, because is already uniform.

In most images, the diversity of pixel values will allow the definition of several regions. In order to set a maximum value to the slider, the segmentation algorithm is capable of detecting all the plain regions in the image to compute the maximum amount of regions that a the finest possible partition of an image will include.

To know how it works, have a look at this article

Once the leaves of the tree are computed, the demonstration displays their associated regions by uniformly painting them with their average color, they are called “the leaves of the tree”. The slider then, reflects the number of leaves the tree is going to have.

Here there are a few screen-shots of the demonstration.

Speed test

2011-04-06T13:17:00.006+02:00

One of my tasks this week has been to separate the pages of HbbTV application that my team is developing.

It is a very big application, composed by a hook, an initial page, VOD page, EPG page, a searcher, and related videos...

All of these different pages are showed and hidden but they are still in the same application.
I developed the way to separate them and to write only the code who make them work separately.

When you call the url of every page, you make a GET with a variable called standalone, who allows you to chose if you want them united or separated.

Then, I have tested the time of load of every single page called with standalone = true (separately) or standalone = false (united).

I have done it with Mozilla Firefox and with one of the three decoders we have in our company: the one that has incorporated the new HbbTV enabled television.

The times of load we obtained were:

MOZILLA FIREFOX

TELEVISION

HOOK:

standalone = true;
7sec, 8sec, 7sec, 7sec.

standalone = false;
9sec, 9.5sec, 9sec.

INITIAL:

standalone = true;
7.8sec, 10sec, 11sec, 8sec, 11sec, 7.7sec, 8.6 sec.

standalone = false;
10sec, 10sec, 9.8sec, 9.7sec, 9.3sec, 9.8sec.

CONCLUSIONS

- To load JS code is not so critical, the code execution is most costly.

- The hook page is faster than the initial page because contains less JavaScript code.

- The television is very slow executing JS code.

- Images take a long time to load.

- This television suports window.location sentence, and it runs applications not listed in the AIT of the broadcaster TDT steam.

My application as a widget

2011-04-06T12:39:00.002+02:00

A widget is a module that you can insert in other applications or web pages. I have to develop a launcher widget, to insert it where the final user or the broadcaster wants.

I started to program following my team’s structure, being coherent with their code structuring.

So I finished it in two style variables, horizontal and vertical.

It’s not so easy because the navigation is a little complicated to adapt to both of them.

An example of my widget (without look and feel)

It works horizontal or vertical with writing the type in the configuration parameter.

Types of launchers

2011-04-04T10:09:00.011+02:00

As I explained in my last post, a launcher is a kind of application that allows to start another applications being consistent with their life cycle.

Nowadays, most of the digital systems for video or applications and even the computers contain launchers.

I tried to classify these in groups:

- Mobile phones launchers:

The format of these applications is very usable and reduced. Mobiles are often small than other systems and they have lots of apps.

- Computer launchers:

I believe that desktops and other similar widgets can be understood like launcher applications. There are a lot of formats like dock (Mac OS) or the Initial button on other operative systems.

- Television launchers:

With the new technologies of televisions, the launcher is very important. Televisions are capable to do a lot of things so is a good idea to organise them into an application to manage them easily.

- Set-top boxes launchers:

Set-top boxes have already a launcher. This point is very important to develop my project.

- Console launchers:

The video game environments have also applications to start games, networks and other things.

Integrating Wt + Imageplus

2011-04-02T13:25:00.008+02:00

These last weeks I've been getting started with a C++ library whose purpose is to build web applications. This library is called Wt, you can have a look at my last articles to know more about it.

My project consists on demonstrating algorithms from the UPC video and image processing group, so an important step in the development of my application would be to be able to use imageplus algorithms, the library of the group, and create Wt classes in order to show them in a web page.

I have to thanks Albert Gil for helping me with the libraries, because the first step was to change the way of compiling the project, in Wt, actually they are using a program called Cmake, as well as make.

Imageplus, is currently using a program called scons to compile.

We changed this and landed our workspace to the IDE that they are using, Eclipse.

Furthermore, we had to add two libraries from Wt in order to join them, the name of the libraries is libwt and libwthttp.

Once environment was ready, I started to work, and I did some examples that I'm going to explain right now:

The first one was an easy one, we just wanted to test if it was possible to request some data, process it with imageplus and in the end, show the result in the client's browser.

And the algorithm I used was the scalar product between two vectors, which is a data input and data output algorithm, no images, no videos.

Well, you can see in this figure the result, it worked fine.

The second one was a bit more complicated, not so much, but a little bit. It was “plain image generator”. I mean, imageplus was generating images as long as the client requested it. The images were in different colors depending on the position the cursor was poining. Thus, if the cursor was in the top left position, the square generated was different from the bottom right position.

I think that this example makes imageplus overwork, because every time the cursor moves, a request is sent to the server, and then imageplus generates an image. If you want to pass from half a square to the other half, how many requests do you need to do? How many images are you generating?

Well, really this is a nonsense without any relevance because I was just testing how imageplus could generate and image and display it through the web.

Here there are a couple of screenshots.

And now the last one. This example consists on an image in which you go with the cursor over it, and you get the red, green and blue average as well as the total average of the neighbour pixels of the pixel you are pointing.

Although I'm going to explain this now, It applies also for the examples above mentioned.

Imageplus uses a type of structure, or better said, a class to store the image, but Wt uses another type of class to store its image. So I needed to connect them somehow.

The Wt's class which can store a image, getting it in a low level, pixel by pixel is called Wt::WRasterImage, then I have done a function which given a image from imageplus, it returns a pointer to WRasterImage filled with this image. This function will be the main connector to transmit images to the web, very useful.

Although Wt can process the pixels by acceding them and changing their value, it is not the goal we are aiming to. We want all the image and video processing to be done with imageplus.

Currently, I'm trying to merge the webpage I did last week with two of the demos, which seems a bit more complex, but not impossible. I'll explain you in the following articles!

Multiscale object detection tested in Formula 1 sequences

2011-04-02T12:54:00.006+02:00

The detection of objects at a local scale might be a hard processing task if every particular location in the image must be tested. In our research, we focus on the object retrieval and detection on Binary Partition Trees, a hierarchical segmentation of the image that increases (in fact, duplicates) the basic problem of local analysis.

In general, though, the context provided by the pixels of the image that do not represent the object provide valuable information that can simplify the local analysis. In our recent tests, we have considered a double-scale processing of images: at the global and the local scales.

We have demonstrated this approach in the domain of Formula 1 sequences of image. Firstly, we have annotated with GAT a reduced set of around ten diverse examples of every type of object that wants to be detected. Furthermore, we have also annotated as negative examples another set of images that do not contain the object.

The object detector algorithm has used this annotation to train two types of classifiers. Firstly, a classifier based on global scale features (color distribution and edge histogram) capable of discerning between those images that may contain an instance of the modeled object from those that do not.

In a second stage, those image marked as candidates, have been analyzed at a local scale. The detection of the objects has been performed on the local features computed for every region defined by the Binary Partition Tree. In this case the detector extracted the object and showed it with an overlaid mask in green.

So far, no temporal stabilization has been applied yet, so every frame has been treated completely independent. This experiment has allowed a faster processing of the complete sequence, as well a reduction on the amount of false positives when compared with the case of only working at the global scale.

Web interface for shot type detection

2011-03-28T22:34:00.011+02:00

In this post I will explain the evolution of the web interface I have to develop for my bachelor thesis, which persues semi-supervised key-frame shot type identification. This interface will be used to re-train a shot type classifier (already trained with manual labeled examples) for a given domain by validating or correcting its automatic detections and then adding them to the trainer to generate a new model. So for a given domain and an asset (group of keyframes of that domain) the interface will have to show the automatic shot type identification and provide the necessary tools for validating the automatic detections or correcting them if necessary.

After one month of work, two diferent layout proposals were presented to the Documentation Department at the CCMA in order to keep developing the interface with the structure that better suit their needs, these are the following ones:

1st Proposal:

• For each domain we have different tabs for each shot type.

• Each tab contains all the detected keyframes for that shot type.

• The number of keyframes on each tab is fixed, the variable thing is the number of pages for each tab, which depend on the quantity of keyframes detected for that shot-type.

• Keyframes have to be labeled as positive (detection is ok) or negative (detection is wrong)

• Besides labeling as negative a keyframe the information of the right shot-type has also to be provided.

• Only one shot-type can be seen at once.

• To open another asset the already opened one has to be closed, cannot manage working with different assets at the same time.

2nd Proposal:

• For each domain we have different tabs for each asset, so simultaneus working with several assets is supported.

• For each asset tab there are as many keyframe rows as shot types in that domain. So all shot types can be seen at once.

• The columns of each row are fixed for all shot types. As not all shot types have the same keyframes detected and pagination is shared by all shot-types, some of the rows can run out of keyframes.

• This layout makes it suitable for drag and drop functionalities to easily correct a keyframe shot-type detection, so there is no need of labeling any keyframe as negative, just drop it to the right place.

• Once all keyframes are in the right place the page can be entirely validated.

• As when validating there are examples of all shot types within a domain, at training the classifier would have similar number of examples for each one so it will improve in a more homogenic manner (a class will not be undertrained as it can happen with the firs proposal).

Current interface:

Because of its functionality and its visual component, the 2nd proposal was chosen by the CCMA with additional requeriments as showing the title and the detection score for each keyframe. This is its actual appearence before and after validation:

My first Wt C++ web page

2011-03-24T17:39:00.006+01:00

The main goal of my project, is to show algorithms in a web page. If I want to do so, I obviously need to create a web page. But, what is the best way? There are a lot of technology behind web pages and web applications, PHP, ASP.NET, Python, ruby, etc.

In my last post I spoke about Wt, a C++ library for web purposes. In addition, ImagePlus, which is also programmed in C++, is the library used by the Image and Video Processing Group from the Polytechnic University of Catalonia.

What I'm doing is trying to make them easier to show their algorithms in a web page. Doing it in other language different from C++ would implicate someone would have to learn web based languages.

Having said this, what I'm going to explain is that there is an important abstraction process between Wt and web technology. Wt programmers don't care about neither PHP nor any other web issues. So you can program whatever you want just using C++, which is very good for all C/C++ experienced programmers because the need of learning a new language for the web disappears.

And, what about HTML?
I've been programming some time with PHP, and like it, what you are doing is writing the HTML code to be displayed in the client. But in different ways. In Wt you can create a new element such as a WContainerWidget, and it's supposed that you have written a "div" element into a HTML web page. But the difference is that WContainerWidget is a class and you can use its methods in a very easy way.
Conversely, in PHP you have to print all the page code as an string, so it's not so fine.

And CSS, How does Wt manage to put the style on?
First of all, CSS means Cascading Style Sheets and its purpose is to split content from style. Wt allows to programmers to apply the style in two different possibilities. You can apply it in some methods directly from C++, or you can add an external CSS style-sheet with all the rules.
Certainly, CSS is not a programming language, is most a descriptive language about how is the style of the page. Consequently, its syntax is very easy and it's not a problem.

Well, and right now, I'm going to comment a bit my first web page example. I've done five classes which are:

GPIapp
GPIpage
GPIheader
GPIcontent
GPIfooter

All these classes except GPIapp are derived from WContainerWidget. In other words, these are “div” elements. GPIapp is used to launch the web page and set all the external style-sheets and features.

GPIpage is the main container. Inside it, there are the rest of the classes. The GPIpage class is composed then of four private attributes, which are: the page itself, the header, the content and the footer.
In the header we have the logo, a title, and a space in the right.

The content is the perfect holder where the demos are going to be placed. So probably, it will have to become a bit more complex. Another point of abstraction, I think that it will be good stuff if there were a class called GPIdemos, and the content could accept one of those, then the complex code perhaps will be in this last class. Well, this another step, but it has to be thought correctly, so, let me think and I'll explain you it in next posts.

This is my first web page example:

Wt - Web programming with C++

2011-03-17T22:19:00.007+01:00

Some time ago I was thinking in how to do a demonstration of a video algorithm for the UPC image processing group. The first idea was to display the video output in a web interface. I certainly thought a lot around this issue, as well as investigated technologies such gstreamer, ffmpeg, etc.

But really this is not the only way to demonstrate those algorithms. Being aware that not all algorithms output a video, that some of them output coordinates or data in general, it's easy to think that there is another way. What about data streaming.
On the one hand, there is the advantage that we can forget for some time the encoding and multiplexing processes.
On the other hand it's still streaming, so I ought to find out the way to do that, with a smaller amount of data in each sent.

With this last idea, my project became a bit different, the data now are not frames, the data are whatever, coordinates, names, etc. For this reason, I had to research how to send these data.
In a image processing algorithm, is not known when data are going to change, so we certainly need a requirement, data have to be pushed.
I mean, imagine the server in one side, the client in the other side.
Then the server just gives data to the client whenever it wants, and the client just collect this data and integrate it in the web page live demonstration.

Well, I think this is very easy to understand but not possible theoretically, and I'm going to explain why not. We are trying to send the data trough HTTP protocol. This is because HTTP protocol is allowed by firewalls and we can send data without being blocked.

Then we have to think how HTTP works. The way how it works is sending a request to the server, typically a GET or POST request, and the server responds with the data.
So, as you can see, negotiation is needed, we can't just push data. It will be incoherent.

Nevertheless, there are some hacks, you can have a look at reverse AJAX, which has a lot of names, such as comet programming, or a lot more.

I'm not going to comment all of them, but I'm going to mention the most important one, long polling.

This hack consists in doing a request (the client), and when the server has new data, then respond this request. When data arrive, a new request is sent. Thus, we can have a more efficient way that steadily polling.

Actually. there is a library called Wt (uttered as witty), whose use is exclusively to web programming, with the only difference that it is a C++ library. This library is very similar to the famous Qt C++ library which is used to create desktop interfaces.
The library has a very good documentation, very good forums, and in general the impression that it give as, me, Albert and Xavi was a great impression. We couldn't believe that this library was able to do all what says in the documentation. It was really strange, if so, why is not it very known?

Our final answer was that is not very known because it is in C++.
Nowadays, web programming is made by some technologies like PHP, Javascript, AJAX, ASP.NET, and so on.
But Wt offers the possibility to C++ programmers to make a web page without any knowledge about all of this technology. Abstracting thus, these technologies just by using C++.

Well, once said this, I'm going to mention my current trial applications.
The first one has been a simply text input that when you key up, a message such “Hello unknown, how are you?” pops written down in the screen. When the name is known, it shows this name instead unknown.
The background of this simple application is that every time you key up, there is a request. In addition, I've managed to learn how the style works in this library.
Here I leave a screen-shot of my little application:

This has been a good starting point, to realize how Wt could render a web page using C++. But after doing it, I've gotten my hands dirty doing a more complex server push, based on the example server push. Finally I've included another point to my second application. This is the painting.

The second experiment has been to demonstrate the random algorithm from stdlib of C, by sending two random data, in a random time interval, and then the data are rendered by painting a little circle in the coordinates (random1,random2).

I think that it is a good approach because I've already achieved to push data through the net. Now, it's time to connect my little application with ImagePlus, and take over the C random by the ImagePlus random. This will be my first ImagePlus algorithm demonstration.
I expect to show you this in my next post, so, have a look!!

Visual Search with Relevance Feedback based on Weights Updating

2011-03-10T16:23:00.007+01:00

A new Electrical Engineer in the world ! Yesterday Aida successfully defended her Bachelor thesis yesterday at Telecom BCN. She presented her work "Visual Search with Relevance Feedback based on Weights Update" (in Spanish), the first research effort from our work in the field of user interaction for image retrieval. This publication represents a step further after the previous thesis by Carles Ventura.

The thesis compares three different approaches to handle the relevance feedback of a user after a visual search. These three techniques use the information provided by the user when selecting which of the retrieved images is relevant for his/her query. The user interaction allows estimating which of the four available visual similarity criteria match better the user expectations.

The three basic approaches are based on previous work by Rui (updates descriptor weights by increasing/decreasing their relative value), Taycher (updates according to the mean distance among relevant images) and Aksoy (updated according to the relation between the distance standard deviations of relevant and non-relevant images). Aida's work also studied some variation of these three techniques.

Experimentation with the CCD database showed that Taycher approach behaved best when measuring performance with for ANMRR and MAP and that, in general, those techniques that consider the results as a set more than individual items perform better. The results of the study also proved that most gain in interaction is after the first and second iteration, considering in every feedback iteration the labeling of 20 results as relevant and non relevant. In terms of visual descriptors, the MPEG-7 Color Structure was the best relevance estimator, follow by the Texture Edge Histogram, the Color Layout and the Dominant Color, all of them part of MPEG-7. Finally, the comparison between Aida's and Carles worked proved that the fusion of ranked list by distance average is better than the fusion on position.

The future work includes integrating Taycher technique in GOS, our GUI for image retrieval, running further tests on a larger and more generic dataset and defining a more accurate weight update formulation in terms of a linear classifier.

Streaming to an HTML5 web page

2011-03-09T13:33:00.005+01:00

In some articles before this, I've been talking about some separated issues, such as Gstreamer, VLC, the HTTP protocol, streaming techniques and HTML5.

Now, I've achieved in streaming against a web page. And I'm going to explain how the whole test has been.

First of all, I succeeded in sending an HTTP stream with VLC, which has been a very important tool for my last discovery because it has allowed me to investigate how it works.

Another important tool to take account of is wireshark. Wireshark is a network software that allows you to look at and capture what is going through your network interfaces. So you can see all the packets and a lot of information about them, for instance, how the protocol stack is composed.

Besides, I have to reference you again to another article written by myself which explains the main architecture of Gstreamer, one of the most important frameworks for streaming purposes in this moment.

Once said this, let's get our hands dirty, let's to streaming!
Firstly, we have to think about who is going to do streaming, and how. Now we are assuming that we are in the server, and we have to build something like a Gstreamer pipeline.
This pipeline has to cover some requirements.

It has to start with a well-known video file and format. It will be raw.
We have to be aware about what encoding and multiplexing methods HTML5 supports.
What does HTTP streaming means in terms of the HTML5 video tag.
Well, step by step. The first part is what to send. It is an early test so, we can send a gstreamer video pattern already designed for test purposes. It's name is “videotestsrc”. We have got the first piece of the puzzle.

Now, our current worries are the the encoding and multiplexing methods. Well, really, when I tested the VLC HTTP streaming a few time ago, I used Theora as video encoding method,vorbis as audio encoding method, and ogg as well, as multiplexing multimedia container. It worked perfectly, therefore I'm going to use them to do this test. All them except vorbis because there is no audio in here.

Then, I'm going to use theoraenc, the theora encoder, and oggmux, the ogg multiplexer. Of course in the future theora can be replaced by h.264 or VP8 and ogg can be replaced by other containers like webM or mkv.

And finally, the last and for me the most difficult part of this test, to send this coded and multiplexed video that we have got, through the red.
Well, as you know internet is an end-to-end global net. It means that you can't broadcast like if It were a TV broadcasting. Ok, at this point, I did some tests in the way of how could send this data. I spent a lot of days investigating the HTTP protocol and how I could send this data through this protocol, like VLC does.
The strange thing was that when I was capturing the traffic produced by the VLC streaming server, there was no traffic.

Then, in the other machine, opened my HTML 5 file, and then, suddenly a lot of HTTP and TCP traffic were produced.
When you looked at the traffic, you could see the TCP handshake, and then a get request from the client to the server.
It made me think that perhaps the video HTML5 tag manages to encapsulate the data in the HTTP protocol in order to be displayed in the web page, and we just have to send the data via TCP. And effectively, this worked.

To sum up, in my ubuntu, I executed:

gst-launch -v videotestsrc ! theoraenc ! oggmux ! tcpserversink host=192.168.1.35 port=8080

If you have read the blog posts before, you'll know what is gst-launch, the -v is to verbose all the information, the ! sign is used to indicate that this elements are connected, and the las element is a TCP sender, which sends to this IP and to the 8080 port. This is running in the server's machine.

In the client machine I just have to open the HTML5 web page with a browser like Google Chrome 8 or Firefox 3.6 which accept the HTML5 video tag.
If you want to be sure that is being correctly sent, I recommend you to check the traffic in both points of the connection, in the client and server.

Right now, if all has been right, you ought to be doing streaming to a web page using Gstreamer and HTML5

Textual similarity graph

2011-03-04T11:43:00.008+01:00

My goal for these two months was implement to a system that could be generated a textual similarity graph from the metadata associated to images.

We had only worked with the visual modality until now. In our case, four different visual descriptors from the MPEG-7 standard are considered: Color Structure, dominant Color, Color Layout and Texture Edge Histogram. But, we would like to work with multimodal systems to improve the results obtained from diverse algorithms such as the reranking algorithm.

In this post I want to explain you the general scheme of the system. Basically, it consists in two steps. First one corresponds to the extractor of the text descriptor and the second one generates the textual similarity graph.

Extractor

As well as the visual modality, we need a descriptor that could represent the metadata associated to the image. As I told in one of my last post, we calculate the text desciptors based on the TF-IDF weight.

Previously to this step we have to build a dictionary. The dictionary contains the terms that are used to represent all the text descriptors, so all images are represented with the same terms. Moroever, each term have associated an index what indicates the position of this term in the text descriptor.

Textual Similarity graph

Next step is determining the similarity between the different text descriptors to generate the textual SG. We use the cosine similarity to quantify the similarity between text descriptors, as I said in my last post. Finally, we obtain a similarity graph where the nodes are the metadata of the images and the edge are the similarity between their text descriptors.

So now we can work with four visual similarity graph and a textual one.

Introducing Launcher HbbTV Application

2011-03-03T14:48:00.008+01:00

Context

As I explained in the previous post, I'm working on developing applications for HbbTV standard.

What’s a launcher application?

I have to develop a launcher application. The function of this application is to show to the user all the applications available and to start them when user wants.

This is an example of a mobile launcher application.

For now, I have started to try to understand some of JavaScript files and their interaction with HTML and CSS.

I have done some tests:
- I created an interface to show applications
- I tried to start another application

I try my programs with a web browser like Mozilla Firefox, and I have also tested with two different set-top boxes.

The graphic structure of my test application is composed by:

- Background

- Icons

- Focus

When I press the arrows in the set-top box remote control, the focus changes. In this way, I can see the app that is going to be selected. But I can not move the focus, because is very hard to be decoded by the set-top box. There must be 4 focus, and always be hiding and showing the right one.

This is a photograph of my first test.

Going through the HTTP protocol

2011-03-01T17:49:00.007+01:00

When you are looking up a website, a lot of things happen. One of them is related with the HTTP protocol.

Let's talk about HTTP. Fist of all, HTTP is a protocol created by World Wide Web consortium and Internet Engineering task in order to allow all the elements which allow a web architecture to communicate themselves.

And then, how does it work?

Certainly, is not a very difficult protocol, it's based on request-reply scheme. This means that in a communication, first, the client will send a request, then the server will reply this fulfilling as well as possible.

It's important to highlight that it's a stateless protocol, because it doesn't keep any state, this limitation was the main reason for the introduction of cookies in web browsers, to keep a state in the client.

In the request, the client normally asks for some information, and the server gives it back. When you are in the situation above mentioned, looking up for a web page, the server has returned the whole web page in the reply.

But HTTP is not only to transmit web pages. It can be used for transmitting some attributes and values which can launch a CGI script in the server, for example.

Furthermore, and this is the most important part for my project, HTTP is used also to send video, avoiding the firewalls. Therefore, we could send video packets through the web, and take it with a HTML 5 interface.

But well, focusing in the practice, I'm going to show a real example of HTTP communication.

Once a connection has been opened at the server's URI and port, (i.e. URI: http://www.example.com/index.html, port:80) the client sends this message to the server.

GET /index.html HTTP/1.1

Host: www.example.com

User-Agent: name-client

[Blank line]

Then, the server replies with:

HTTP/1.1 200 OK

Fate: Fri, 31 Dec 2003 23:59:59 GMT

Content-Type: text/html

Content-Length: 1221

[...CONTENT...]

As you can see, the server is answering that the server's response has been right, with HTTP version 1.1, with the “OK” message, and the 200 code, which is a status code. Here is the l ist of status codes.

Moreover, the data is in the reply, always in GMT format, and also the content type, which refers to what mime type the data is, and finally, the size of this set of information.
The HTTP packet can have some attributes that can make the protocol work in some different ways. For example, there is an attribute, “content-encoding”, which explain how the data are encoded, or an authentication via HTTP.

Here you can see the whole list of attributes that client and server can request or reply respectively.

As an example, I'm going to show you HTTP headers of a traffic capture that I've done with Wireshark while I was streaming a video with VLC(Videolan) and capturing it with a HTML 5 interface.

Hybrid Broadcast-Broadband TV

2011-03-01T09:33:00.007+01:00

Presentation

I am Martí Alcon, a student who's working in his diploma thesis (Projecte Final de Carrera) with Xavier Giró.

My project is about the development of a launcher application to use it in an interactive television environment suported on the HbbTV standard.

I'm working with Activa Multimèdia like Cristina and Mane l. Cristina worked on adapting Twitter for HbbTV applications. However, my project tries to develop a launcher, to start other apps.

So this post, talks about the environment of my project: Hybrid Broadcast-Broadband TV.

What is HbbTV?

HbbTV is a standard of hybrid television, that's formed by a specification that tries to regulate the emissions of contents via terrestrial and IP.

Usually, we are talking of recieving contents using DTV (Digital TV) or IP, but we can also recieve them using wire or satellite.

HbbTV meets specifications of other standards such OIPFTV, CEA, DVB and W3C.

The programming languages of the HbbTV applications are:

XHTML or php, CSS and JavaScript.

AJAX is a web development technique also used in HbbTV applications.

Broadcasters can use HbbTV application to create catch-up services, video on demand (VOD), menus with related videos, search engines...

Conclusions of my thesis

2011-02-28T16:30:00.007+01:00

I made the oral presentation of my bachelor thesis "Reordenació i agrupament d'imatges resultants d'una cerca de vídeo" (Reranking and clustering images from a video search system) a month ago. You can view it in youtube in Catalan. This project has given me much knowledge both on a personal level and in terms of career. On the one hand, I learned different programming languages such as Java and GWT, as well as provide knowledge about the state of the art of the retrieval systems. On the other hand, the fact of carrying out the bachelor thesis in a company has given me an overview of working world that we will live in.

Furthermore, we presented a paper about the reranking algorithm that I told in this blog, to the congress ACM ICMR 2011 that is going to celebrate in Trento. Finally, our paper has been accepted and is scheduled for a poster session. The final acceptance rate is only 35%.

In conclusion, I'm very glad with the final result of my project!

Measures out of a confusion matrix

2011-02-24T21:33:00.010+01:00

A confusion matrix is used in supervised learning for comparing the outcome classification of an item with the desired classification. Each row of the matrix represents the instances that have been automatically predicted in a class, while each column represents the hand-labeled instances in a class. This matrix is useful for observing which classes have miss-identified items as other classes.

		Hand-labeled
		Class1	Class2	Class3
Automatic	Class1	10	3	0
	Class2	2	8	1
	Class3	0	2	11

Precision and recall:
Precision or specifity is a mesasure of the ability of a system to present only relevant instances. It measures the exactness or fidelity of the system.

Recall or sensitivity is a mesasure of the ability of a system to present all relevant instances, so it is used for evaluating the completeness of results.

It is difficult to compare different systems in terms of precision and recall, as both measures are independent. Moreover, when recall increases precision tends to decrease: as more relevant instances are retrieved, the more nonrelevant instances are retrieved.

F and Fß measure:
F-measure considers both precision and recall providing a single measurement for a system avoiding having two independent measures.

In order to give different weights to precision and recall, the F-measure was derived so that Fß measures the effectiveness of retrieval with respect to a user who attaches ß times as much importance to recall as precision.

Fß measure of a confusion matrix:
For my bachelor thesis I have had to write a function capable to compute the Fß measure for a given confusion matrix. This is the equation that has been derived from the explained measures:

Where "i" represents the class and "N" is the total number of classes.

HTTP Adaptive Streaming Techniques

2011-02-24T13:12:00.003+01:00

There is no a clear and standard way to do streaming, but there are a few techniques to do it. At this point I'm going to summarize them.

Proprietary Techniques:

Adobe's Dynamic HTTP streaming

It uses an own protocol called Real Time Message Protocol (RTMP) to put the fragments into F4F files which are used, in addition to F4M which carries all the features of the files encoded at multiples bit rates to do a smooth streaming.

Apple's HTTP live streaming

A division of the main stream is done in equal length segments and stored (.ts). Also is created an index which contain a play-list of all the media divisions and all the meta-data associated. The extension of this file is .M3U8 This index is served to the client and thus, it can control all the streaming process.
There is a final thesis of Bruna, another student of my career, which explains perfectly all the apple's HTTP live streaming for more information. The document is written in Catalan.

Microsoft's smooth streaming

This method's chunks are contiguous in a mp4 file for random access. There are two different formats:

.ismv: Contains both audio and video.
.isma: Contains olny audio

Server Manifest File (.ism) controls the relation between all media tracks, bit rates and files, while Client Manifest File describes all the available streams of the client, the coders that can be used to be after decoded, video resolutions, etc.
Clients just request the fragments by the URI, using the quality and the offset to the next fragment.

Open Techniques:

Adaptive HTTP streaming (AHS)

It's a project from 3rd Generation Partnership Project (3GPP) which consists in divide the whole stream in chunks.
Usually to codify a frame, video coders use the previous frames, so in this case we should define all the group of pictures(GOP), starting from an I picture and ending before another one, as a chunk.
Of course, there is a meta-data file which indicates how to use this little parts of video, which are each one in one different URI. The name of this file is Media Presentation Description.(MPD)
This version is the 9th release. You can see the whole standard in the official web page chapter 26.234

Dynamic Adaptive Streaming over HTTP (DASH)

The 10th release of 3GPP which is an improvement of AHS which includes new features as well as on-demand streaming video or linear TV including live media broadcast.

Open IPTV forum's HTTP adaptive streaming

Open IPTV forum has adopted the 3GPP AHS and it's base to add some support to MPEG-2 transport files.

Adaptive Streaming over HTTP

2011-02-19T16:16:00.017+01:00

How do we can watch a video on internet? There are a few ways to do that. We can just see it by downloading the whole video file and after, playing it.

That's not comfortable for the user experience's because usually video sizes are not small, and depending of the bandwidth of the connection it can take a lot of time.
There is another way called progressive download, it consists in a service in which you can download the video and play it at the same time. In this method, the video has to be stored in a server, it cannot be streamed by a live web cam.

There is a lot of discussion about what streaming is, and what is not.
The definition of streaming says that just the needed parts of media are transferred in order to play them. I mean, in progressive download, services like youtube, when you pause the video to do other things, this video is still downloading and wasting valuable bandwidth

In addition, returning to the title, it says adaptive. Why adaptive?
Imagine that you are doing streaming with a web cam. Suddenly, the net becomes more and more used, and your video is just being played slower because of the limitation of the net's bandwidth.
Adaptive then, means that the scalability of the video can change depending on the bandwidth available and affecting the spatial (pixels per unit of width), temporal (frames per second), quality (DCT Coefficients and module of Motion Vectors), or combinations of them.
Of this way, in the case you were watching a video and the bandwidth were variable, there would be smoother than before.

The other interesting issue is why to use HTTP. HTTP is the protocol used to web pages, but there are some reasons that make it suitable for sending video through it.

Easy and effortless streaming by avoiding NAT and firewall issues.
There is a clear trend in the web to send video trough HTTP. All Apple's devices, and mobile devices general, you tube and more web streaming services.
It has the ability to give the control of the streaming to the client.

Seeing that, despite there are no standards yet, some companies and entities have defined some ways to do streaming over HTTP. Here in the Bitsearch, you can see another post with some of the most important technologies.

Open source software for video streaming on the web

2011-02-14T15:45:00.015+01:00

In this blog post I would like to explain what is my final thesis about, and three possible actual technologies to succeed in.

It's about how to demonstrate the algorithms of the image processing group in a web interface, with the most recent technologies such as HTML 5.

To stream the video to a web page, we need a streaming engine. This, have to be able to stream the video, so we have to be aware about wheather the most common browsers support all this technologies.

I think that with a little figure is easier to understand:

Where we can see the source as the output of some video processing.

It's clear that all browsers accept HTTP protocol because all pages are served of this way.
And other advantage that HTTP protocol has between other protocols like UDP or RTP, apart from the support for technologies, is that firewalls usually don't accept this type of traffic.

Focusing in the streaming engine, there are three possible technologies to cover this area:

Gstreamer:

Gstreamer is an open source low-level library for multimedia streaming porpouses which is programmed in C. It's a very good designed library with a plug-ins structure which allows you to use a lot of functionalities.There is also an example of software called "Flumotion" from the company “Fluendo” for HTTP streaming. This software could fulfill this requirements.

Fluendo has one of its headquarters here, in Barcelona.

A few days ago I wrote an article explaining the basics of gstreamer.

FFmpeg:

FFmpeg is also a complete solution for the manipulation of audiovisual content. This includes a lot of functionalities such as encoding, decoding, recording, audio and video streaming, etc.
Some of Gstreamer plug-ins are written with ffmpeg functionalities, using them in some of their plug-ins. In terms of my project, FFmpeg is not so much recommended because there are too much changes between different versions of this library. It could be the weakest point of this technology.

VLC media player

VLC media player is an open-source project for playing audiovisual content. It also has a streaming server which could be useful to stream to the web. VLC is programmed in C/C++ and the most interesting library for us is liveMedia, which is a set of C++ libraries and frameworks for multimedia streaming (RTP/RTCP, RTSP, SIP) . It has also some functionalities taken of ffmpeg.

We also have to be conscious about the compatibility of the browsers, the most important ones, at least.

Here there is a comparative of the usage of browsers during January of 2011.

But the use of HTML 5 is not still implemented in all the browsers, in some of them.

Here, there is another figure with the HTML 5 functionalities implemented in the most updated version of each browser. My college Christian wrote an article about HTML 5 explaining what is and what news it includes. We have to look at the green one, which is support for the “video” tag which is able to handle a video stream into a web page. As you can see, In Chrome 4.1, Safari, Opera 10 and Firefox 3.6 this functionality is already implemented.

Threshold Optimization for MPEG-7 Dominant Color Similarity in YCbCr

2011-02-11T13:15:00.008+01:00

These last days I have been adapting a C++ implementation of the MPEG-7 Dominant Color Visual Descriptor to be used in my C libraries. This visual descriptor describes a region as a maximum of eight colors, providing for each of them their mean, variance (optional) and percentage of occupation. The extraction of the descriptor is performed with the software developed in Carles Ventura's thesis, while the similarity assessment is part of my Phd work in C.

The first problem I had was the mismatch between the color space used for the MPEG-7/XML files generated from the C++ library with the color space proposed by the standard to assess similarity. These files express the dominant colors in the RGB color space, while the standard metric is based on the CIE LUV color space. Moreover, my C libraries do not include any RGB to CIE Luv conversion, so I decided to approximate it to YCbCr.

A second problem I was not aware of was the quantized values of the descriptor fields in the XML document. After checking the documentation and with the help of Carles, I figure out how to correctly recover the percentage values, which were the ones that alerted me of the problem as they were not adding up to 1.0.

Once these implementation issues were solved, I started performing some visual tests from GOS, the graphical interface we have developed for visual search. I realized that the results were not very good. Check for exemple this result I obtained when querying the database with the same image which is retrieved as the best result:

Clearly the results could be much better, as only the first six retrieved images include the anchor, while the database contains eleven of these type of keyframes. So I dove into the source code to debug it step by step and realized that the main problem was coming from a parameter heuristically set in the similarity metric. The MPEG-7 standard proposes a value Td=16.0 as a threshold to consider if two dominant colors are similar enough to be considered "similar". This threshold is applied on the euclidean distance between the two colors which are compared. After some debug, I realized that the turquoise color of the anchor's coat from two different images was considered as no similar by the metric due to this threshold. So I tried to increase this threshold to 32.0, with the following result:

The new configuration retrieved much better results. Maybe the fact that I am using the YCbCr color space instead of the recommended CIE Luv space is the reason why the threshold 32.0 is doing much better than the proposed 16.0. In any case, I run some more values for the same experiment and finally estimated that the most appealing visual results are obtained with Td=42.0, as shown in the figure below.

Web architecture of a classification system

2011-02-10T18:49:00.007+01:00

In the context of the i3media project we are close to complete the automatic image annotation system line of work. At this stage of the project we have all the necessary tools to publish the web service and to be used by the users. This paper is intended to lay the foundations of the service architecture and thus to clarify all the possibilities that it provides.

Model training

A model contains the parameters necessary for a classifier to decide whether an image belongs or not to a certain class. These models are built by training a classifier by a set of images which have been previously annotated as belonging or not to the class that is being modeled.

The modeled classes are intended to represent semantic concepts which are to be automatically detected by the system. These semantic classes are defined in an ontology. The implemented system will deal with several ontologies, each of them containing a set of classes that can be found in the same domain. The users of the system must be able to define these domains and the modeled classes.

A user who wants to define a model must make the manual annotation of a set of image representing and not representing the class. This manual annotation will be saved in the server to be able to reuse these annotations in case the model wants to be retrained with new (less) samples. It should be noted that an image can belong to several classes annotations.

The annotations are used by the model builder to train the classifier and build the model. As a result, a model can be generated for every class.

At this point, it is also possible to estimate the performance of the classifier by dividing the train set in two: a smaller train set and a test set. Evaluation measures such us precision, recall or f-measure can be estimated through cross validation and, by doing so, providing the user with a measure of the expected quality of the automatic annotations. This technique was widely developed through Mireia's thesis

Image Classification

Natural user of the service will want to detect and automatically annotate an image. He will select a file system image, the class id of the class he wants to detect (equals to 0 if wants to classifier with all classes in the ontology) and the ontology (model) to be used. Once on the server that info will be passed by the classification engine with the corresponding models.

The client response is a positive annotation with the detection confidence score of the class (the client can set a minimum score to be sent). At this point the user has the possibility of using this annotation to train the classifier or modify it if necessary.

This feedback and self-learning system models allow an improvement of efficiency of the classifier engine with the collaboration of multiple users. However, we must manage somehow this update because if the classifier is working properly will not need to be updated with new redundant annotations.

Supervised, unsupervised and semi-supervised learning

2011-02-08T14:20:00.009+01:00

In this post I will discuss the pros and cons of some machine learning procedures and how would they suit shot type detection at the CCMA (Catalan Broadcasting Corporation). I will focus on three main categories: supervised, unsupervised and semi-supervised learning.

The difference between these types of learning is whether the training data has been hand-labeled or not to generate the classifier’s output. Supervised learning assumes that a set of training data has been provided. On the other hand, unsupervised learning has no labeled data. A combination of both labeled and unlabeled data results in semi-supervised learning.

What does that imply?
In supervised learning, a qualified person would properly label by hand the set of instances to be used for training. This means professionals at the documentation department would be required for this task. The more labeled instances the classifier gets the more precise will be the output, so the amount of hand labeling needed to reach a desired quality is certainly time-consuming The advantage is that the system can be controlled better: shot types can be defined and it can be selected which images are of interest. For example, pictures with no people can be avoided by labeling them as “not relevant shot type” so not relevant shot type pictures will not be shown on a search.

Unsupervised learning, having no labeled data, attempts to find out similar patterns in the data to determine the output. This type of learning needs nobody for the training process but this also means no interactivity: the system has no clue on which shot types are of CCMA’s interest and will define different classes clustering similar data depending on the visual content. This kind of learning wouldn’t suit the CCMA needs as different shot types have to be defined depending on the context: a soccer close-up shot would have a different name than a parliament close-up shot.

Finally, semi-supervised learning is actually a supervised method that avoids labeling a large number of instances. This is done by using some of the labeled data to help the classifier labeling the unlabeled data. Then, this automatic labeled data is also used by the training process. Another supervised method that helps mining labeled data is called active learning. Basically, it decides which data should be labeled to improve the classifier performance with less data. These two options are really interesting, as they have the benefits of both supervised and unsupervised learning: interactivity and taking advantage of unlabeled data. With a few labeled instances and the great amount of unlabeled images at our disposal this system could perform well for shot type detection.

Introduction to the Gstreamer System Architecture

2011-02-01T18:19:00.007+01:00

In my last post I wrote some different things about VLC, which I wanted to use for streaming purposes. I had to investigate what library it used. Actually, there is one library called "LIVE 555 streaming media" which the cone, VLC, is using.
Really, it was very difficult for me to find information for getting started.

For this reason, it was proposed to me, to investigate a bit about another low-level library called Gstreamer and written in C, for streaming and playing multimedia, which is used in several applications.

The first impression was really good. There is a first manual in which you can learn the basic features of Gstreamer, how to initialize it, how to put it in different state, what is a pipeline, what is an element, and finally a OGG player, as a "Hello World" application to apply the concepts already learnt.

As a result of my investigation, I'm going to summarize what I've learnt in this Gstreamer Manual.

The main use of Gstreamer is to manage the video and audio stream to create, for example, a video player, or a streaming server.

An element is the most important class of objects in Gstreamer. Usually, a functionality is achieved by linking elements.

Normally, inside the elements, there are pads, which are inputs and outputs. The input pad is called "sink" and is from where data flows trough the element, for example, from a local file, or from another element. The output pad, is called "source".

Here we can see an example of an elements with two pads. An input pad, and an output pad.

This is an element called filter, with input and output pads.

Besides elements, there is a kind of container called bin, which would be the parent of some elements. And then, there is a type of bin, called pipeline.
This is a hierarchical structure for one important reason. A medium-sized project with gstreamer will contain a lot of elements, imagine that you want to put the "play" state. You should tell to each element. This method allows you to tell the command to the pipeline and it will advise all its elements.

There are also buses and message reporting functionalities which I'm not going to explain in this post because it will be too long.

Finally, as an exemple of the above explained, we have the first "hello world" application, which is an audio player of the Vorbis encoded content in an OGG file.

In the next posts I'm going to explain how it functions by putting snippets of code, and extending a little bit more the bus and message functionalities.

The vector space model for scoring

2011-01-31T15:16:00.021+01:00

In my last post I developed the notion of a document vector that captures the relative importance of the terms in a document. The representation of a set of documents as vectors in a common vector space is known as the vector space model (or term vector model).

Consider the vector derived form a document with one component in the vector for each dictionary term. The set of documents in collection then may be viewed as a set of vectors in a vector space, in which there is one axis for each term. This representation loses the relative ordering of the terms in each document. This type of feature vectors are the basis for the bag of words models.

How to quantify the similarity between two documents in this vector space?

The standard way of quantifying the similarity between two documents is to compute the cosine similarty of their vector representations

where the numerator represents the dot product of the vectors, while the denominator is the product of their Euclidean lengths. Let V(d) denote the document vector for d, with M components. The Euclidean length of d is defined to be:The effect of the denominator of the similarity equation is thus to length-normalize the vectors V(d1) and V(d2) to unit vectors:So I can then rewrite it as:Thus, it can be viewed as the dot product of the normalized versions of the two document vectors. This measure is the cosine of the angle between the two vectors in the following figure.

This similarity measure is used to retrieval similar documents to a particular document in a collection. For example, given a document d, a user wants to finding the documents most similar to d. The search systems will retrieve the documents (di) with highest dot products. They could do this by computing the dot product (v(d)·v(di)) between v(d) and each v(d1), ..., v(dn). Finally the user will obtain a ranked list based on this measure.

Automatic video shot type identification by Wang et al

2011-01-28T00:38:00.019+01:00

My name is Eli Carcel and this will be my first contribution to this blog. As I am now starting my bachelor thesis on keyframe-based shot identification I have been studying the state of the art. I found a related paper called "Automatic Video Shot Size Annotation Scheme by Wang et al (2006)" which I will briefly describe.

The aim of the project is recognizing an image shot type pattern, assuming there are three possible categories: Close-up, Medium shot and Long shot. The project steps include: feature extraction, training, classification and decision.

Process

The first step is feature extraction where two feature vectors are created, one corresponding to low level features such as color, edge and texture and the other one to mid level features involving regions and its features.

Semi-supervised learning is needed in order to obtain valid data to train the system. Co-training can help boosting the training process by offering semi-supervised annotation.

Each vector of features is sent to a different classifier (low level and mid level) to decide which shot size suits best the image among the three existent classes. A combination of both classifiers’ results is used in order to improve its efficency. Cost-sensitive decisions for misclassifications are calculated to provide a better cost minimization based classifier.

Experimental results

Tests are done using 20 hours of video extracted from home video camcorders and then divided into 1000 shots according to timestamps. As in this stage some shots may include images with several shot sizes, each shot is divided into 4000 sub-shots, assuming now identical shot size within a sub-shot.

All results are the average of 10 runs, where a run is an iteration done by using 20% of the samples randomly selected as training data and the other 80% to test the system.

The paper shows how low level descriptors work better in shot type identification, though it can be pursued a better performance using a combined low level and mid level decision.

Awards for Ramon and Cristina's thesis

2011-01-18T13:49:00.015+01:00

Year 2010 was excellent in terms of the quantity and quality of thesis I supervised. Five academic works were defended, four of them qualified with an A with honors. Apart from being very satisfied for the good job of all students, I am especially satisfied for the public recognition that two of them have received.

Last October Ramon Salla Rovira received one of the awards given by companies to the best thesis in the Telecom BCN (ETSETB). His work on the development of a web client for multimodal video retrieval was considered the best thesis in the area of Telematics by Acc entu re. Ramon developed his thesis while working at CCMA, so it was a joint work from the university and industry. In this case the supervision was shared between Xavier Vives and me.

Cristina Ruiz Sancho also received many compliments for her work during her studies and her thesis. In the graduation day at the Engineering School of Terrassa (EET) she was recognized as the best student among all the five undergraduate programs in the school and her thesis was selected to represent the school in the awards organized by the Spanish Association of Technical Telecommunication Engineers. Her work on bringing the Twitter service to social TV received the second prize in this prestigious competition. CCMA can be very proud of their technical divisions because Cristina also developed her thesis there under the joint supervision of Eduard Cucurella.

Ramon and Cristina did an excellent work during their thesis, but their success can only be understood as the tip of a much larger iceberg. Their enthusiasm, talent and ambition was successfully supported by their colleagues at CCMA as well as the teaching and research team at the UPC. For this reason I believe that more excellent thesis are to come soon. Mónica will defend hers next Monday, and Aida and Neus are in the final stages of theirs. I wish the example given my Ramon and Cristina will encourage them during these last weeks of hard work.

Ranking text documents based on TF-IDF

2011-01-14T21:11:00.009+01:00

I introduce the concept of TF-IDF (term frequency-inverse document frequency) in one of my first post but, in this post, I will examine the structure of it for a set of documents.

The TF-IDFf can be seen as a textual descriptor for text documents. And this concept has been extended to the analysis of images, how said Laura in this post.

Term frequency

A weight is assigned to each term in a document according to the number of occurences of the term in the document. This weight is referred to as term frequency. The simplest approach is to assign the weight to be equal to the number of occurrences of term t in document d.But some other common approaches are:

Inverse document frequency

Term frequency suffers from a critical problem: all terms are considered equally important when it comes to assessing relevance on a query. In fact, certain terms have little power in characterizing the document. For instance, the stopwords that are meaningless terms such as articles, pronouns, prepositions, etc.

So document frequency (df) defined as the number of documents in the collection that contain a term t, is introduced for a attenuating the effect of terms that occur to often in the collection to be meaningful for relevance determination. The solution for this problem is attenuating the tf with the inverse document frequency (idf), which is defined as:
where N is the number of documents in a collection. Thus the idf of a rare term is high, whereas the idf of a frequent terms is likely to be low.

TF-IDF weighting

TF-IDF combines the definitions of terms frequency and inverse document frequency to produce a composite weight for each term in each document. The TF-IDF weighting scheme assigns to term t a weight in document d given by:

It will be highest when t occurs many times within a small number of documents.
It will be lower when the term occurs fewer times in a document, or occurs in many documents.
It will be lower when the term occurs in virtually all documents.

At this point, each document can be seen as a vector with one component corresponding to each term in the dictionary. Each value in this vector coorresponds to the computed tf-idf value for the term in the document. For dictionary terms that do not occur in a document, this weight is zero.

Possible applications

A tag cloud is a visual depiction of the term content of a site, typically used to describe the content of web sites. Tags are usually single words and are normally listed alphabetically, and the importance of each tag is shown with a different font size or color. The concept of TF-IDF can be use to determine the weight of each tag.

Temporal stabilization of bounding boxes

2011-01-14T19:26:00.019+01:00

In the recent post, we presented two videos showing the results of a region-based object detection. We tried to detect two different types of objects, a cap and the poker maths in a test sequence produced by our industry partners. We highlighted, using a bounding box, each detected region of interest. Finally, we generated a video, combining all images with their generated bounding boxes.

After analysing these videos, we realized that it was present a upsetting flickering between the bounding boxes of consecutive images. This effect was generated because every single detection was performed individually for every image, without considering the other detections in the sequence. We decided to exploit the temporal dimension to fix this issue.

We used a temporal stabilizer developed by David Varas and Pedro Espinosa. This tool detects outliers and performs a spatial low level filtering of the bounding box vertices.

The next diagram show the design procedure. The input sequence of XML files contains the object detections as a set of regions in the BPT which, at the same time, finally refer to file containing the partition labels of every pixel in the input image. I developed a simple Java application that translated these region IDs to the bounding box coordinates surrounding the images. The sequence of box coordinates was stabilized to finally generate the images with an overlaid rectangle around every detected object.

The resulting videos are shown below:

Notice the multi-view nature of the detections, that have been learnt with no additional interaction from the user side. The object detector has processed all provided region-based annotations to automatically learn the amount of view and build a detector for each of them.

In conclusion, comparing both videos, the one with the flickering problem and the other with the problem fixed, it can be showed a better visualization and more accurate results.