Media Releases

New algorithm finds you, even in untagged photos

December 2, 2013

TORONTO, ON – A new algo­rithm designed at the Uni­ver­si­ty of Toron­to has the pow­er to pro­found­ly change the way we find pho­tos among the bil­lions on social media sites such as Face­book and Flickr.  This month, the Unit­ed States Patent and Trade­mark Office will issue a patent on this tech­nol­o­gy.

Devel­oped by Parham Aara­bi, a pro­fes­sor in The Edward S. Rogers Sr. Depart­ment of Elec­tri­cal & Com­put­er Engi­neer­ing, and his for­mer Master’s stu­dent Ron Appel, the search tool uses tag loca­tions to quan­ti­fy rela­tion­ships between indi­vid­u­als, even those not tagged in any giv­en pho­to.

Imag­ine you and your moth­er are pic­tured togeth­er, build­ing a sand­cas­tle at the beach. You’re both tagged in the pho­to quite close togeth­er. In the next pho­to, you and your father are eat­ing water­mel­on. You’re both tagged. Because of your close ‘tag­ging’ rela­tion­ship with both your moth­er in the first pic­ture and your father in the sec­ond, the algo­rithm can deter­mine that a rela­tion­ship exists between those two and quan­ti­fy how strong it may be.

In a third pho­to, you fly a kite with both par­ents, but only your moth­er is tagged. Giv­en the strength of your ‘tag­ging’ rela­tion­ship with your par­ents, when you search for pho­tos of your father the algo­rithm can return the untagged pho­to because of the very high like­li­hood he’s pic­tured.

“Two things are hap­pen­ing: we under­stand rela­tion­ships, and we can search images bet­ter,” says Pro­fes­sor Aara­bi.

The nim­ble algo­rithm, called rela­tion­al social image search, achieves high reli­a­bil­i­ty with­out using com­pu­ta­tion­al­ly inten­sive object- or facial-recog­ni­tion soft­ware.

“If you want to search a tril­lion pho­tos, nor­mal­ly that takes at least a tril­lion oper­a­tions. It’s based on the num­ber of pho­tos you have,” says Aara­bi. “Face­book has almost half a tril­lion pho­tos, but a bil­lion users—it’s almost a 500 order of mag­ni­tude dif­fer­ence. Our algo­rithm is sim­ply based on the num­ber of tags, not on the num­ber of pho­tos, which makes it more effi­cient to search than stan­dard approach­es.”

Work on this project began in 2005 in Pro­fes­sor Aarabi’s Mobile Appli­ca­tions Lab, Canada’s first lab space for mobile appli­ca­tion devel­op­ment.

Cur­rent­ly the algorithm’s inter­face is pri­mar­i­ly for research, but Aara­bi aims to see it incor­po­rat­ed on the back-end of large image data­bas­es or social net­works. “I envi­sion the inter­face would be exact­ly like you use Face­book search—for users, noth­ing would change. They would just get bet­ter results,” says Aara­bi.

While test­ing the algo­rithm, Aara­bi and Appel dis­cov­ered an unfore­seen appli­ca­tion: a new way to gen­er­ate maps. They tagged a few pho­tographs of build­ings around the Uni­ver­si­ty of Toron­to and ran them through the sys­tem with a bunch of untagged cam­pus pho­tos. “The result we got was of almost a pseu­do-map of the cam­pus from all these pho­tos we had tak­en, which was very inter­est­ing,” says Aara­bi.

This work received sup­port from the Nation­al Sci­ence and Engi­neer­ing Research Coun­cil of Cana­da. It will be pre­sent­ed at the IEEE Inter­na­tion­al Sym­po­sium on Mul­ti­me­dia Dec. 10, 2013.


More infor­ma­tion:

Mar­it Mitchell
Senior Com­mu­ni­ca­tions Offi­cer
The Edward S. Rogers Sr. Depart­ment of Elec­tri­cal & Com­put­er Engi­neer­ing
Uni­ver­si­ty of Toron­to
Phone: 416–978-7997