Showing posts with label research papers. Show all posts
Showing posts with label research papers. Show all posts

Sunday, December 16, 2007

Image Matching

I had been toying around with the idea on extending Video search to include the audio and video (image) data associated with the video in addition to the user specified tags. This is one of my weekend projects, others being the semantic representation of knowledge and android app development.
This weekend I spent some of my time get out a rough cut of the "Image Indexing using Color Correlograms" [the same with my notes] which could be helpful in my Video Search project. The principle behind an image correlogram [Correloation + histogram] is the spatial correlation between the image colors. A correlogram can be defined as f(c1,c2,k), where f is the number of pixels of color c2 around a pixel of color c1 which are at a distance of k from the c1 colored pixel.
The results looked promising. At present I used only the G channel to generate the correlogram, and I would be refining it over time.
Some results : I chose come images obtained by the query: road via google image search, calculate the correlograms for each and then used the metric described in the paper to find the closeness. The number adjacent to each image describes how close it is to Image 1. Lower the number the closer the image is to Image1

Image 1:





Image 2: 16.32
Image 3: 4.84 Image 4: 9.51

Image 5: 15.06 Image 6: 17.03Image 7: 15.05

The closest images to Image 1 are Image 3 and Image 4, which looks intuitive.
Image 5 and Image 7 have similar correlograms which also seems fine.
But the observation that Images 2,5,6 and 7 are at almost equidistant to Image 1 is not very palpable. Especially as Image 2 is no way related to Image 1. On the other hand, it is not possible to draw inferences on the robustness of this approach with such a small set of test images. I'd be do some more research and come up with enhancements to get better results.

At present I just used the green channel of the image in the creation of the correlogram as histogram of the green channel is closet to the luminosity histogram. [ The reason for this is that the human eye is more sensitive to the color green than any other colors]. The current algorithm calculates f using all the pixels in an image and computing f is quite expensive O(n^2*d) . [The complexity has been mentioned to be O(n^2*d^2) in the paper and I will try to clarify this with the authors]. The space complexity is O(m^2 * d) [where m is the number of possible colors] Further improvements in time and space can be made by calculating the correlogram for select regions of the image (high gradient blocks).

btw, it took me quite some time to set up a development environment in windows.
I used the opencv sdk for reading the images, eclipse IDE with CDT, and mingw (gcc for windows)for the compiler.


Some Informative links that I followed:
opencv
http://www.site.uottawa.ca/~laganier/tutorial/opencv+directshow/cvision.htm
http://www.cs.iit.edu/~agam/cs512/lect-notes/opencv-intro/opencv-intro.html#SECTION00041000000000000000
http://www.xpercept.com/opencv.htm

eclipse cdt:
http://www.cs.umanitoba.ca/~eclipse/7-EclipseCDT.pdf

updates:
Don Dodge on video search

Sunday, June 03, 2007

The germ

The 16th International World Wide Web conference was held at Banff, Alberta Canada from May 8 to 12th this year.
The web has revolutionalized the way information flows, the way people learn, the way people do their everyday things, the way people socialize and a zillion other things. In short, it has revolutionized the way we live.
And each year the www conference sets the stage to accelerate this revolution in the years to come.

Here are a few papers that I'd like to read up in the limited time I have.
I collected these docs by searching for pdf site:http://www2007.org/ with google.
I have skimmed through the abstracts of the interesting papers of the first 90 results
I found around 29 papers interesting.

Track: Semantic Web (2)

1] Analysis of Topological Characteristics of Huge Online *

Social Networking Services

http://www2007.org/papers/paper676.pdf

2] Combating Spam in Tagging Systems [Stanford]

http://www2007.org/workshops/paper_97.pdf


Track: Search, Information organization, retrieval and processing (17)

1] Navigation-Aided Retrieval

http://www2007.org/papers/paper162.pdf

2] Supervised Rank Aggregation *

http://www2007.org/papers/paper286.pdf

3] Functional Faceted Web Query Analysis [NSU, Singapore] *

http://www2007.org/workshops/paper_44.pdf

4] Efficient Search in Large Textual Collections *

with Redundancy

http://www2007.org/papers/paper800.pdf

5] Formalization, User Strategy and Interaction Design:

Users’ Behaviour with Discourse Tagging Semantics

http://www2007.org/workshops/paper_30.pdf

6] Sponsored Search with Contexts [upenn]

http://www2007.org/workshops/paper_83.pdf

7] Towards a Semantic Knowledge Base for Yeast Biologists

http://www2007.org/workshops/paper_130.pdf

8] Detecting Near-Duplicates for Web Crawling [google] *

http://www2007.org/papers/paper215.pdf

9] Robust Methodologies for Modeling Web Click [yahoo]*

Distributions

http://www2007.org/papers/paper056.pdf

10] Random Web Crawls[criteo]

http://www2007.org/papers/paper339.pdf

11] An Adaptive Crawler for Locating Hidden-Web Entry Points [Utah]*

http://www2007.org/papers/paper429.pdf

12] Web Projections: Learning from Contextual Subgraphs of the Web

[Microsoft, cmu]*

http://www2007.org/papers/paper551.pdf

13] The Discoverability of the Web [yahoo]*

http://www2007.org/papers/paper592.pdf

14] Extraction and Search of Chemical Formulae in Text

Documents on the Web [PSU]

http://www2007.org/papers/paper100.pdf

15] Summarizing Email Conversations with Clue Words [ucb, cancada] *

http://www2007.org/papers/paper631.pdf

16] Answering Relationship Queries on the Web [IBM]*

http://www2007.org/papers/paper058.pdf

17] Do Not Crawl in the DUST: Different URLs with Similar Text

http://www2007.org/papers/paper194.pdf

Recommender systems, Collaborative filtering (4)

1] Improving Ontology Recommendation and Reuse in

WebCORE by Collaborative Assessments

http://www2007.org/workshops/paper_8.pdf

2] The Complex Dynamics of Collaborative Tagging [Princeton] *

http://www2007.org/papers/paper635.pdf

3] Scaling Up All Pairs Similarity Search [google] **

http://www2007.org/papers/paper342.pdf

4] Applying Collaborative Tagging to E-Learning

http://www2007.org/workshops/paper_56.pdf

Data Mining: (2)

1] Towards Domain-Independent Information Extraction

from Web Tables

http://www2007.org/papers/paper790.pdf

2] Page-level Template Detection via Isotonic Smoothing [yahoo]* omi

http://www2007.org/papers/paper588.pdf

Miscellaneous but interesting (4)

1] Optimal Audio-Visual Representations

for Illiterate Users of Computers

http://www2007.org/papers/paper764.pdf

2] A Mobile Application Framework for the Geospatial Web

http://www2007.org/papers/paper287.pdf

3] Communication as Information-Seeking: The Case for

Mobile Social Software for Developing Regions [Washington]

http://www2007.org/papers/paper669.pdf

4] Tag-Cloud Drawing: Algorithms for Cloud Visualization

http://www2007.org/workshops/paper_12.pdf