April 2008


sumber : http://www.nytimes. com/2008/ 04/28/technology /28google. html

April 28, 2008
A Google Prototype for a Precision Image Search
By JOHN MARKOFF

SAN FRANCISCO — Google researchers say they have a software technology
intended to do for digital images on the Web what the company’s
original PageRank software did for searches of Web pages.

On Thursday at the International World Wide Web Conference in Beijing,
two Google scientists presented a paper describing what the
researchers call VisualRank, an algorithm for blending
image-recognition software methods with techniques for weighting and
ranking images that look most similar.

Although image search has become popular on commercial search engines,
results are usually generated today by using cues from the text that
is associated with each image.

Despite decades of effort, image analysis remains a largely unsolved
problem in computer science, the researchers said. For example, while
progress has been made in automatic face detection in images, finding
other objects such as mountains or tea pots, which are instantly
recognizable to humans, has lagged.

“We wanted to incorporate all of the stuff that is happening in
computer vision and put it in a Web framework,” said Shumeet Baluja, a
senior staff researcher at Google, who made the presentation with
Yushi Jing, another Google researcher. The company’s expertise in
creating vast graphs that weigh “nodes,” or Web pages, based on their
“authority” can be applied to images that are the most representative
of a particular query, he said.

The research paper, “PageRank for Product Image Search,” is focused on
a subset of the images that the giant search engine has cataloged
because of the tremendous computing costs required to analyze and
compare digital images. To do this for all of the images indexed by
the search engine would be impractical, the researchers said. Google
does not disclose how many images it has cataloged, but it asserts
that its Google Image Search is the “most comprehensive image search
on the Web.”

The company said that in its research it had concentrated on the 2000
most popular product queries on Google‘s product search, words such as
iPod, Xbox and Zune. It then sorted the top 10 images both from its
ranking system and the standard Google Image Search results. With a
team of 150 Google employees, it created a scoring system for image
“relevance.” The researchers said the retrieval returned 83 percent
less irrelevant images.

Google is not the first into the visual product search category. Riya,
a Silicon Valley start-up, introduced Like.com in 2006. The service,
which refers users to shopping sites, makes it possible for a Web
shopper to select a particular visual attribute, such as a certain
style of brown shoes or a style of buckle, and then be presented with
similar products available from competing Web merchants.

Rather than relying on a text query, the service focuses on the
ability to match shapes or objects that might be hard to describe in
writing, said Munjal Shah, the chief executive of Riya.

“I think what they’re trying to accomplish is largely impossible,” he
said. “Our belief is, there is not large-scale solutions.”

Mr. Shah said there had been a number of technology demonstrations by
Google Labs researchers, such as a project in 2005 that used machine
learning techniques to recognize the gender of a person in an image.
However, the company has been slow to deploy its research, he said.

Artikel ini merupakan bagian dari tulisan pada penelitian disertasi saya. Saya coba sarikan untuk teman-teman yang ingin mempelajari image retrieval. Semoga bermanfaat.

MENGENAL SEMANTIK CITRA – BAGIAN I

Ketika kita mengamati sebuah lukisan yang didalamnya terdapat gunung, air yang mengalir, pepohonan, dan burung yang sedang terbang, kita mengenal lukisan ini adalah lukisan pemandangan. Kemampuan manusia untuk mengenali gambar tidak terlepas dari pengalamannya melihat berbagai jenis gambar sehingga mampu membedakannya satu sama lain. Setelah menghubungkan satu objek dengan objek lainnya, maka kita baru bisa menjelaskan tema gambar atau melakukan penafsiran (interpretation) gambar. Interpretasi tema/konsep citra disebut dengan semantik citra.

Gambar atau citra memiliki karakteristik visual yang terdiri dari warna, bentuk dan tekstur. Pengenalan pada tahap karakteristik visual disebut dengan persepsi. Persepsi adalah tanggapan (penerimaan) langsung terhadap sebuah objek berupa karakteristik visual tanpa melakukan interpretasi.

Jika saja sistem computer memiliki kemampuan seperti manusia dalam menejelaskan semantic citra, maka dapat dipastikan kita dapat mencari gambar digital yang disimpan dalam computer dengan mudah. Namun, kemampuan manusia menjelaskan semantik citra dengan cepat, bukan hal yang sederhana untuk dilakukan oleh komputer. Sudah banyak penelitian dalam bidang image retrieval dikembangkan untuk membuat komputer mampu menjelaskan semantic citra. Dalam banyak penelitian, karakteristik citra seperti warna, bentuk dan tekstur digunakan untuk pencarian citra. Pencarian citra melalui karakteristik citra disebut dengan content-based image retrieval (CBIR).

Pengenalan citra dimulai dengan melakukan ekstraksi ciri (feature extraction), yaitu mengenali citra berdasarkan karakteristik citra. Berdasarkan hasil survey [], perkembangan penelitian CBIR dalam hal ekstraksi ciri dapat dikelompokkan menjadi 3 (tiga) yaitu berbasis global (global-based), berbasis regional (region-based) dan berbasis lokal (local-based).

Global-based

Pengenalan citra berbasis global menggunakan informasi seluruh bagian citra. Salah satu metode berbasis global-based yang banyak paling banyak digunakan adalah histogram warna []. Namun metode ini memiliki kelemahan yaitu hanya menghitung frekuensi piksel citra sehingga sangat sensitive terhadap perubahan cahaya dan geometris. Akibatnya dua buah citra yang memiliki warna dan posisi geometris yang berbeda akan dikenali sebagai dua buah citra yang berbeda, walaupun secara semantic kedua citra tersebut sama. Perhatikan Gambar dibawah ini:

Dengan pendekatan berbasis global, maka kedua citra tersebut akan dikenali sebagai citra yang berbeda.

Region-based

Pada dasarnya manusia mengenali citra berdasarkan objek yang dikandung pada citra tersebut. Oleh karena itu kemudian berkembang pendekatan regional dimana citra disegmentasi menjadi beberapa regional yang merepresentasikan objek.

Namun metode ini juga memiliki kelemahan, yaitu pada saat segmentasi citra. Sampai saat ini belum ada teknik segmentasi citra yang dapat melakukan segmentasi dengan baik. Hasil segmentasi seringkali tidak sesuai dengan objek yang diinginkan. Perhatikan gambar di bawah ini:

Local-based

Oleh karena itu untuk mengatasi masalah segmentasi pada pendekatan regional, kemudian berkembang pendekatan lokal. Pada pendekatan ini citra dibagi menjadi beberapa blok citra yang berukuran sama. Dengan demikian pada pendekatan lokal tidak membutuhkan segmentasi.

Namun pada pendekatan lokal, setiap blok citra tidak memiliki makna. Akibatnya pendekatan lokal tidak mampu menjelaskan hubungan konseptual antar blok citra.

Adanya permasalahan tersebut, maka pendekatan lokal berkembang menjadi pendekatan bagian (part-based). Pada pendekatan bagian akan, akan dideteksi bagian-bagian penting dari citra yang mampu menjelaskan semantik citra. Pendekatan ini disebut juga dengan pendekatan generative. Berikut contoh dari pendekatan bagian.

Untuk mendapatkan bagian penting citra, pendekatan generative menggunakan teori Bayes. Dengan teori bayes, tanpa melakukan segmentasi citra, pendekatan bagian dapat mendeteksi bagian penting citra.

Sumber :

1. Datta, R., Joshi, D., Li, J dan Wang, J. (2007). Image Retrieval: Ideas, Influences, and Trend of the New Age. ACM Transaction on Computing Survey.

2. Bimbo, A. (1999). Visual Information Retrieval. Morgan Kauffman

3. Rui, Y., Huang, T. S., dan Chang, S. F. (1999). Image Retrieval: Current Techniques, Promising Direction, and Open Issues. Journal of Visual Communication and Image Representation, 10(1), 39-62.

4. Smeulders, A. W. M. , et al. (2000). Content-based Image Retrieval at The End of The Early Years. IEEE PAMI, 22(12), 1349-1380

5. Zhang, Y. J. (2003). Content-based Visual Information Retrieval. Beijing, China: Science Publisher.

Oleh : Wisnu Ananta (teman kantor..:)
Ada yang menarik dalam konsep relationship pada basis data, khususnya mengenai one-to-one relationship. Konsep ini mengenai bagaimana mentransformasikan ER model yang mengandung one-to-one relationship ke dalam model. Apakah dua buah entitas yang memiliki one-to-one relationship ini akan ditransformasikan menjadi satu tabel atau dua tabel ? Kalau dua tabel, primary key dari tabel yang mana yang harus ditempatkan pada tabel yang lain, menjadi foreign key ?
 
Saya akan mulai dengan contoh. Andaikan ada dua entitas : mahasiswa dan komputer. Jika asumsinya setiap mahasiswa mendapat fasilitas satu komputer dan setiap mahasiswa selalu menggunakan computer yang sama untuk melakukan praktikum dari semester awal sampai dia lulus, maka relationship antara entitas mahasiswa dan computer ini adalah one-to-one relationship. Jika ternyata masing-masing mahasiswa mendapat satu computer dan tidak ada computer yang tersisa (semua telah dialokasikan kepada mahasiswa), maka kedua entitas ini dinamakan memiliki mandatory one cardinality (total participation) . Untuk kasus yang demikian, maka transformasi model ER ke model relational menjadi satu tabel. Kita satukan kedua entitas dengan atribut-atributnya ke dalam satu tabel.
 
Sebagai contoh: entitas mahasiswa memiliki atribut NRP, dan entitas computer memiliki atribut kode_komp dan tipe. Misal entity instance dari entitas mahasiswa adalah
M={M1, M2, M3} dan entity instance dari entitas computer adalah K={(K1, T1), (K2, T2), (K3, T3)}, maka model relasionalnya menjadi tabel baru (misal M_K) yang mengandung tiga field NRP, Kode_komp, dan Tipe dengan entity instancenya 
M_K = {(M1, K1, T1), (M2,  K2, T2), (M3, K3, T3)}.
 
Dalam konteks hubungan interpersonal (hubungan pribadi antara dua orang manusia), ini adalah hubungan interpersonal yang ideal. Jika analoginya, diri kita adalah representasi dari suatu entitas, dengan atribut berupa keinginan, harapan, dll. Dan orang lain adalah entitas yang lain. Maka jika setiap entity instance kita (keinginan/harapan) kita bertemu tepat dengan entity instance (keinginan/harapan/ atribut lainnya) dari orang lain…. Maka berarti sesungguhnya hati kita dengan hati orang itu telah menjadi satu. Kita mampu merasakan apa yang orang lain rasakan. Ini mungkin seperti yang diisyaratkan Nabi : “tidak beriman seseorang sebelum dia mencintai suadaranya seperti kecintaannya  pada dirinya sendiri.”     
 
Tapi memang sulit mewujudkan relationship yang ideal seperti di atas. Kenyataannya, kita sering berusaha memahami orang lain tetapi merasa bahwa orang lain itu  belum memahami kita penuhnya. Konsep one-to-one relationship berikut mungkin akan memperjelas bagaimana kita harus bersikap.
 
Kembali ke contoh entitas mahasiswa dan computer. Jika asumsinya departemen tersebut memiliki computer yang berlebih. Maka setiap mahasiswa mendapatkan tepat satu computer, yang berarti entity instance dari entitas mahasiswa berpartisipasi penuh pada relationship (mandatory one cardinality) . Sementara itu, karena jumlah computer berlebih, maka ada computer yang menganggur (alias tidak dialokasikan kepada mahasiswa) sehingga  entity instance pada entitas computer hanya berpartisipasi sebagian (optional one cardinality) . Untuk kasus yang demikian, ketika ditransformasikan ke model relational, akan  menghasilkan dua tabel, yaitu : tabel mahasiswa dan tabel computer. Dan yang terpenting adalah primary key dari tabel yang memiliki optional one cardinality (dalam hal ini tabel komputer harus ditempatkan ke  tabel yang mandatory one cardinality (dalam hal ini tabel mahasiswa) sebagai foreign key. Tidak boleh terbalik. Jika terbalik, akan banyak nilai Null pada tabel komputer.
 
Lebih jelasnya dapat dilihat berikut:
jika misalnya M = {(M1, M2, M3} dan K = {(K1, T1), (K2, T2), (K3, T3), (K4, T4), (K5, T5)} maka setelah ditransformasikan ke dalam model relasional menjadi dua tabel M dan K, yaitu:  M = {(M1,K1), (M2,K2), (M3, K3)}, di mana K1, K2, dan K3 sebagai foreign key.
 
dan K = {(K1, T1), ( K2 , T2), (K3, T3), (K4, T4), (K5, T5)}.
 
Jika penempatan primary key terbalik. Maka akan menghasilkan :
 
M = {M1, M2, M3} dan K = {(K1, T1, M1), ( K2 , T2, M2), (K3, T3, M3), (K4, T4, Null), (K5, T5, Null)}, dimana M1, M2, dan M3 menjadi foreign key.
 
Dalam konteks hubungan interpersonal. Jika kita merasa tidak semua keinginan/harapan dipenuhi oleh orang lain tersebut maka analoginya kita seperti entitas computer pada contoh di atas (yaitu memiliki optional one cardinality)  sedangkan orang lain  tersebut mungkin telah merasa cukup puas dengan relationship yang kita bangun analoginya seperti entitas mahasiswa (yang memiliki mandatory one cardinality) . Sesuai dengan contoh di atas, kalau kita menemui kasus yang demikian, maka seharusnyalah kita tetap bersabar/berusaha memahami orang lain tersebut. Kita berusaha dengan ikhlas untuk terus menanamkan identitas kita (primary key) ke dalam lubuk hati orang lain tersebut (menjadi foreign key). Berusaha untuk selalu memulai memahami, memaafkan, menyapa, dll. Karena jika kita berbuat sebaliknya, menuntut orang lain tersebut memulai untuk selalu memahami kita, yang  kita dapatkan adalah kekosongan-kekosong an (nilai NULL) yang mengisi jiwa kita. Tanpa kita sadari sebenarnya ada ruang hampa dalam diri kita. Oleh karena itu,  ini mungkin yang diisyaratkan oleh Nabi Muhammad saw, manusia paling sempurna akhlaknya, agar kita “menyebarkan salam”, “menyebarkan senyum”, “dan selalu menjadi yang lebih dulu memaafkan”.
Moga bermanfaat.

Hari-hari mempersiapkan ujian kualifikasi adalah hari-hari yang menyenangkan sekaligus juga menegangkan…:) Setidaknya selama tiga minggu ke depan saya akan melalui hari-hari seperti itu. Ini merupakan ujian kedua dari lima kali ujian yang harus saya lalui (Proposal, Kualifikasi, Seminar, Ujian Hasil Pembahasan dan Promosi). Fuih… masih panjang nih ceritanya…:p. Oleh sebab itu Tak aneh memang jika ujian ini cukup membuat aku kerja keras untuk mempersiapkannya. Apalagi setelah melihat dosen pengujinya …hmmmmm….

25 April 2008 adalah tanggal yang dijadwalkan untuk ujian kualifikasi (semoga tidak diundur lagi…Amin). Konon kata orang hari jumat adalah hari baik… moga hari baik juga untuk saya..:).

Salah seorang teman yang juga senasib sepenanggungan, menyarankan saya untuk membaca artikel yang ditulis oleh Dr. Andrew Broad Seorang dosen yang membagikan pengalamannya menjalani ujian selama menjadi PhD student…. Artikel itu berjudul “Nasty PhD Question Viva Questions..”. Artikel itu sangat menarik dan membantu saya setidaknya mengurangi ketegangan saya…:).

Semoga bermanfaat juga untuk Anda..:)

 

Download : nasty-phd-viva-questions.pdf