`
`
`as) United States
`
`
`
`
`
`
`
`
`a2) Patent Application Publication 10) Pub. No.: US 2008/0069480 A1
`
`
`
`
`
`
`
`
` Aarabiet al. (43) Pub. Date: Mar. 20, 2008
`
`
`
`
`US 20080069480A1
`
`
`
`
`
`
`
`
`(54) METHOD, SYSTEM AND COMPUTER
`
`
`
`PROGRAM FOR INTERACTIVE SPATIAL
`
`
`
`LINK-BASED IMAGE SEARCHING,
`
`
`
`SORTING AND/OR DISPLAYING
`
`
`
`(76)
`
`
`
`Inventors:
`
`
`
`
`
`
`Parham Aarabi, Toronto (CA);
`
`
`
`
`Ron Appel, Toronto
`(CA
`on Appel, Toronto (CA)
`
`
`
`
`
`Correspondence Address:
`
`
`
`MILLER THOMPSON, LLP
`
`
`
`
`
`
`Scotia Plaza, 40 King Street West, Suite 5800
`
`
`TORONTO, ON M5H 381
`
`
`
`
`
`(21) Appl. No.:
`
`
`
`11/520,680
`
`
`
`(22)
`
`
`
`Filed:
`
`
`
`
`
`Sep. 14, 2006
`
`
`
`
`Publication Classification
`
`
`
`
`
`(51)
`
`
`
`Int. cl
`
`
`(2006.01)
`COOK 9/32
`
`
`
`
`
`
`(2006.01)
`G06K 9/54
`
`
`
`(2006.01)
`G06K 9/60
`
`
`
`
`
`(52) U.S. Che cc ceseseseesseseereeeeeeeees 382/305; 382/300
`
`
`ABSTRACT
`(57)
`A web-based application provides more accurate and clearer
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`methodsof searching,sorting, and displaying a set of images
`
`
`
`
`
`
`stored in a database. A first aspect of the present invention
`
`
`
`
`
`
`
`
`
`is the method by which image data is stored. Typical
`
`
`
`
`
`
`
`content-based systems use colour information, whereas the
`
`
`
`
`
`
`present invention uses an image-location tagging method. A
`
`
`
`
`
`
`
`
`second aspect of the present invention is the method by
`
`
`
`
`
`
`
`
`
`whichthe set of images are sorted in relevancy. Tag data of
`
`
`
`
`
`
`
`
`
`the images allows for a new and fast method of searching
`
`
`
`
`
`
`
`through an entire set. A third aspect of the present invention
`
`
`
`
`
`
`
`
`
`is the method by which the sorted images are displayed to
`
`
`
`
`
`
`
`
`the user. Instead of the common method of just displaying
`
`
`
`
`
`
`
`
`the images in a rectangular array, where each image is the
`
`
`
`
`
`
`
`
`same size, the web-based application positions and sizes
`
`
`
`
`
`
`each image based on how relevantitis.
`
`
`
`
`
`
`ADD TAGS
`
`
`
`
`
`
`
`
`
`TO IMAGES
`AN OBJECT
`
`
`
`
`
`
` VIEW MODE
`
`
`TAG MODE
`
`CLICK ON
`
`
`
`
`
`
`Page 1 of 36
`
`Netskope Exhibit 1017
`
`Page 1 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 1 of 23
`
`
`
`US 2008/0069480 Al
`
`:cy
`
` ADDTAGSTOIMAGES
`
`
`TAGMODE
`
`
`
`VIEWMODE
`
`CLICKONANOBJECT
`
`
`
`
`
`
`
`
`Page 2 of 36
`
`Netskope Exhibit 1017
`
`Page 2 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 2 of 23
`
`
`
`US 2008/0069480 Al
`
`
`
`
`
`Page 3 of 36
`
`Netskope Exhibit 1017
`
`Page 3 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 3 of 23
`
`
`
`US 2008/0069480 Al
`
`
`
`
`
`
`
`
`
`obew] Man
`
`Page 4 of 36
`
`Netskope Exhibit 1017
`
`Page 4 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 4 of 23
`
`
`
`US 2008/0069480 Al
`
`
`
`
`
`Page 5 of 36
`
`Netskope Exhibit 1017
`
`Page 5 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Mar. 20, 2008 Sheet 5 of 23
`
`
`
`US 2008/0069480 Al
`
`
`
` BERReeeeas
`
` enSRA
`
`sabeulxan- pddyuoy
`
`
`
`yeymyoseegfig
`
` a&&
`Sd7zigobeuljasoy-SabeulSnolAald
`
`
`
`[40yoieeg=SUdijd@Be]
`
`
`
`
`
`
`
`
`
`FRERRASthMlbn
`
`
`
`Hobo~SMOG—“SpoWFSZUEBIO-spoGey-Spop|MAIA~BeUTPETIASIUSoBMAIA
`
`
`
`98IGOMON
`
`Peed
`
`APPT
`
`Wcrvitbe|
`
`ATC}|cc
`
`nS
`
`eA
`
`Wweyled
`
`LSelebe
`
`
`
`ABB8¢q»
`
`BerCops]
`WES
`
`Toast
`
`UOe4
`
`
`
`Page 6 of 36
`
`Netskope Exhibit 1017
`
`Page 6 of 36
`
`Netskope Exhibit 1017
`
`
`
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 6 of 23
`
`
`
`US 2008/0069480 Al
`
`
`‘©
`
`* pe
`Ry
`
`
`
`
`
`
`
`Page 7 of 36
`
`Netskope Exhibit 1017
`
`Page 7 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 7 of 23
`
`
`
`US 2008/0069480 Al
`
`
`nN
`
`* pd
`Ry
`
`
`
`Image2
`
`
`
`
`
`Page 8 of 36
`
`Netskope Exhibit 1017
`
`Page 8 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 8 of 23
`
`
`
`US 2008/0069480 Al
`
`
`
`
`
`
`
`
`
`
`
`Page 9 of 36
`
`Netskope Exhibit 1017
`
`Page 9 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 9 of 23
`
`
`
`US 2008/0069480 Al
`
`Pe
`
`oo
`Ry
`
`
`
`
`
`Page 10 of 36
`
`Netskope Exhibit 1017
`
`Page 10 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 10 of 23
`
`
`
`US 2008/0069480 Al
`
`
`
`
`
`Page 11 of 36
`
`Netskope Exhibit 1017
`
`Page 11 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 11 of 23.
`
`
`
`US 2008/0069480 Al
`
`
`
`
`
`
`
`Page 12 of 36
`
`Netskope Exhibit 1017
`
`Page 12 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 12 of 23.
`
`
`
`US 2008/0069480 Al
`
`
`
`
`
`
`
`
`
`Page 13 of 36
`
`Netskope Exhibit 1017
`
`Page 13 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Mar.20, 2008 Sheet 13 of 23
`
`
`
`US 2008/0069480 Al
`
`we.
`
`
`
`
`
`Se
`
`
`
`
`
`
`
`
`ELATGTeRNtoteayeghcatesormtgsnminyymeeneneene8maRaeantayToySeSELTavotegeaseeLabcebaciNeaGEReteENerentaintBoambeeatlantisteropentetutneaANietomdaeASEBT
`MeeeeeeeeeeeeNe
`MeeeeeeeeTTTNeer=—‘
`payybiem|uonoipaid
`
`
`
`ool€0
`
`
`
`
`
`
`
`plowjua9
`
`
`
`_Jeuejd
`
`Page 14 of 36
`
`Netskope Exhibit 1017
`
`Page 14 of 36
`
`Netskope Exhibit 1017
`
`
`
`
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`
`
`
`
`Mar.20, 2008 Sheet 14 of 23
`
`
`
`US 2008/0069480 Al
`
`Page 15 of 36
`
`Netskope Exhibit 1017
`
`Page 15 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Mar.20, 2008 Sheet 15 of 23
`
`
`
`US 2008/0069480 Al
`
`
`[i id (OE EE
`
`
`
`
`
`3iSeee
`
`pamQ.ca
`
`>ros
`
`5/4Be
`
`|
`
`eee
`
`
`
`
`NS
`
`msJ
`
`
`
`Pe)iee)BelFeleeRSPSES6Be
`
`
`‘+omBWWBgt”seAeota.4
`eof.Lae2‘i
`
`EEwa,[enPO
`fifeeye~“Ye
`nsg¢
`
`
`
`NGGESROe
`ISyey
`
`°
`
`
`
`
`
`FS
`
`poe ann“egm1>ST1aaaeB2
`
`
`Page 16 of 36
`
`Netskope Exhibit 1017
`
`Page 16 of 36
`
`Netskope Exhibit 1017
`
`
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 16 of 23
`
`
`
`US 2008/0069480 A1
`
`
`
`]
`
`
`
`
`
`
`
`
`BoBGeaS
`
`Inm
`
`
`wel[ay#8)[be-
`Ei)b-&
`
`
`
`
`
` baztbad
`
`Page 17 of 36
`
`Netskope Exhibit 1017
`
`Page 17 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 17 of 23.
`
`
`
`US 2008/0069480 A1
`
`
`
`
`
`Page 18 of 36
`
`Netskope Exhibit 1017
`
`Page 18 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 18 of 23.
`
`
`
`US 2008/0069480 Al
`
`
`
`
`
`Page 19 of 36
`
`Netskope Exhibit 1017
`
`Page 19 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 19 of 23.
`
`
`
`US 2008/0069480 Al
`
`
`
`
`
`
`
`Page 20 of 36
`
`Netskope Exhibit 1017
`
`Page 20 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 20 of 23
`
`
`
`US 2008/0069480 A1
`
`QO
`
`ww
`
`om
`
`
`
`Fi
`
`KewOLD
`
`
`Page 21 of 36
`
`Netskope Exhibit 1017
`
`Page 21 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`
`
`
`
`Patent Application Publication Mar. 20, 2008 Sheet 21 of 23
`
`
`
`US 2008/0069480 Al
`
`
`
`_15D
`
`Fi
`
`OLD
`
`Page 22 of 36
`
`Netskope Exhibit 1017
`
`Page 22 of 36
`
`Netskope Exhibit 1017
`
`

`

`SHUI[PAUOD|
`
`auion
`
`TESS
`
`
`
`pualyeppy
`
`v}onuadienXary
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(a)raSobeul]KeN-SaziSabew)jasay-Sabeuysnoineig
`
`
`
`
`BUBA|iSHIRIEN|104YessIeyeoig|‘JOpjo4
`
`
`
`
`
`F607-SUOIGO-SSEUTREDIT-evowSe,apOITRAUEES-wom=SUBNNOIA-
`Oy
`
`
`
`Patent Application Publication
`
`
`
`
`
`
`Mar.20, 2008 Sheet 22 of 23
`
`
`
`US 2008/0069480 Al
`
`OTS17
`
`IqnieyWPYIP
`
`jaddeuos
`
`
`
`Page 23 of 36
`
`Netskope Exhibit 1017
`
`Page 23 of 36
`
`Netskope Exhibit 1017
`
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`04Yess.
`
`
`
`
`
`
`
` pane
` do}aaejed
`
` [L_
`
`eyeoy
`
`“1ap|04
`
`
`
`
`
`
`Mar.20, 2008 Sheet 23 of 23
`
`
`
`US 2008/0069480 Al
`
`ZTSif
`
`Page 24 of 36
`
`Netskope Exhibit 1017
`
`
`
`Page 24 of 36
`
`Netskope Exhibit 1017
`
`
`
`
`

`

`
`
`US 2008/0069480 Al
`
`
`
`Mar. 20, 2008
`
`
`
`
`
`
`
`METHOD, SYSTEM AND COMPUTER
`PROGRAM FOR INTERACTIVE SPATIAL
`
`
`
`
`
`
`LINK-BASED IMAGE SEARCHING,
`SORTING AND/OR DISPLAYING
`
`
`
`
`
`
`FIELD OF THE INVENTION
`
`
`
`
`
`
`
`
`
`[0001] The present invention relates to the field of search-
`
`
`
`
`
`ing, sorting and/or displaying images.
`
`
`
`
`
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`[0002] With the adventof the digital camera, and now with
`
`
`
`
`
`
`
`the highly competitive market in which many companies
`
`
`
`
`
`
`such as CANON™, SONY™and NIKON™have a mass of
`
`
`
`
`
`
`
`
`
`
`models for sale to the general public at very affordable
`
`
`
`
`
`
`
`
`prices, a very large number of people that own a computer
`
`
`
`
`
`
`
`
`also own a digital camera. Largely due to this, a blooming
`
`
`
`
`
`
`
`area in web-basedutilities is the online storage of personal
`
`
`photo albums.
`
`
`
`
`
`
`[0003] Existing applications such as YAHOO!™ Photos
`
`
`
`
`
`
`
`
`and FLICKR™allow users to upload their images onto a
`
`
`
`
`
`
`
`remote database, thereby saving space by not having to store
`
`
`
`
`
`
`
`
`
`them locally. However, these online databases must not only
`
`
`
`
`
`
`
`
`
`store the photographs, they must also be able to display
`
`
`
`
`
`
`
`
`them, and provide some methods of searching and sorting
`
`
`through them.
`
`
`
`
`
`
`
`Present methods of image searching include con-
`[0004]
`
`
`
`
`
`
`
`
`tent-based scans such as colour pattern recognition and
`
`
`
`
`
`
`histogram statistics. Although research is currently being
`
`
`
`
`
`
`
`
`
`
`conducted into this field, these types of searches are not very
`
`
`
`
`
`
`
`
`
`accurate, and will not be perfected for many years to come.
`
`
`
`
`
`
`
`Furthermore,
`the image display organization of
`[0005]
`
`
`
`
`
`
`
`many of these existing web applications is confusing, and
`
`
`
`
`
`
`
`
`
`does not clearly denote an order in the images, namely there
`
`
`
`
`
`
`
`
`
`is no clear definition of which image is more relevant than
`the others.
`
`
`
`
`
`
`
`
`
`
`[0006] Numerous methodsfor searching, sorting, and dis-
`
`
`
`
`
`
`
`
`
`playing images have been proposed over the years [1-18].
`
`
`
`
`
`(References to background documents indicated by Arabic
`
`
`
`
`
`
`
`
`numbers in square brackets refer to one or more of the
`
`
`
`
`
`
`
`
`
`references cited in the “List of References” below.) The
`
`
`
`
`
`
`
`methods and systems of searching images can be generally
`
`
`
`
`
`
`
`divided into content-based and tag-based categories. Con-
`
`
`
`
`
`
`
`tent-based image searching/retrieval systems have the ben-
`
`
`
`
`
`
`
`
`
`efit of being mostly automatic (requiring little or no user
`
`
`
`
`
`
`
`
`
`tagging) with the ability to search virtually any image based
`
`
`
`
`
`
`
`
`
`
`on whatit contains [1-9]. Yet, they suffer from the problem
`
`
`
`
`
`
`
`
`of requiring extensive computations for the search, making
`
`
`
`
`
`
`a real-time implementation on a large-scale image database
`
`
`
`
`
`
`expensive. Furthermore, content-based systems often result
`
`
`
`
`
`
`
`in inaccurate search results due to the misrecognition of the
`
`
`
`
`
`
`contents of the image, thereby resulting in frustrated system
`
`
`
`
`
`
`
`users and a perception of unreliability. While a variety of
`
`
`
`
`
`
`
`modifications to classic content-based image search have
`
`
`
`
`
`
`
`
`
`been proposed over the years, such as user feedback and
`
`
`
`
`
`
`
`
`
`sub-image analysis [10], the level of reliability of these
`
`
`
`
`
`
`
`
`systems for general applications have not been increased to
`
`
`
`
`
`the point of wide-spread user acceptance.
`
`
`
`
`
`
`
`
`[0007] An alternative and more successful method, such
`
`
`
`
`
`
`
`as the one implemented on websites such as FLICKR™,is
`
`
`
`
`
`
`
`
`to manually tag or describe the contents of an image, and
`
`
`
`
`
`
`
`
`then to search these images by searching the tags or descrip-
`
`
`
`
`
`
`
`
`
`tions of the images [11,12]. Tag-based methods have the
`
`
`
`
`
`
`
`
`advantage of being reasonablyreliable (as long as the people
`
`
`
`
`
`
`
`
`
`tagging can be trusted) while requiring very simple compu-
`
`
`
`
`
`
`tations (as compared to content-based approaches). How-
`
`
`
`
`
`
`
`
`ever, tagging images requires significant time and effort to
`
`
`
`
`
`
`
`
`
`be spent by the user especially for large image databases.
`
`
`
`
`
`
`
`Furthermore, tag-based approachesare unable to identify the
`
`
`
`
`
`
`
`
`
`specific location of the object being searched within an
`
`
`
`
`
`
`
`
`image;all they can dois to identify whetherthe object exists
`
`
`
`
`in the image or not.
`
`
`
`
`
`
`
`
`[0008] Many methods for searching, sorting, or tagging
`
`
`
`
`
`
`
`
`images have been patented. One example is a patent that
`
`
`
`
`
`
`
`provides a method and apparatus for assigning keywordsto
`
`
`
`
`
`
`
`
`
`objects found within images, as well as video and audiofiles
`
`
`
`
`
`
`
`
`[4]. These keywords can be assignedto file names or URLs
`
`
`
`
`
`
`
`
`
`of images. Images can also be described by the text in the
`
`
`
`
`
`
`
`
`
`link, including headings andtitles, captions, or ALT text
`
`
`
`
`
`
`
`HTMLtags used to annotate images. Images can thus be
`
`
`
`
`
`
`
`searched through these descriptions or “tags”. This method
`
`
`
`
`
`
`
`
`
`
`of searching takes into account the fact that not all captions
`
`
`
`
`
`
`
`
`
`found within the URL are useful or relevant to specific
`
`
`
`
`
`
`
`
`
`
`images, and thus it only tags images using the text found
`
`
`
`
`
`
`
`
`closest to them. It also determines whether any wordsin the
`
`
`
`
`
`
`
`
`
`
`text match the name assigned to the image, thus text that
`
`
`
`
`
`
`
`
`
`matches is given higherpriority as a tag. This method can
`
`
`
`
`
`
`
`
`
`only be successful if the images are carefully named or
`
`
`
`
`
`
`
`described within their URL. However,
`it cannot
`locate
`
`
`
`
`
`
`
`specific objects within images, or images themselves if they
`
`
`
`
`
`
`
`have not been appropriately described by the user.
`
`
`
`
`
`
`
`[0009] A lot of related patents use image processing to
`
`
`
`
`
`
`
`search for images. An “automatic person meta-data labeler”
`
`
`
`
`
`
`
`
`offers a method of labeling objects within images, and does
`
`
`
`
`
`
`
`
`
`so by detecting their distinctive colours [18]. It is useful for
`
`
`
`
`
`
`
`
`
`the prioritization and sorting of images as well as for
`
`
`
`
`
`
`identifying a designated person that appears in a group of
`
`
`
`
`
`
`images. It can be used to automatically label images by
`
`
`
`
`
`
`
`detecting particular patters and colours, such as a piece of
`
`
`
`
`
`
`
`
`jewelry that a person is wearing in all images, or their skin
`
`
`
`
`
`
`
`
`tone. As useful as this is for labeling pictures within certain
`
`
`
`
`
`
`
`
`
`
`albums or groups of images taken of one scene from
`
`
`
`
`
`
`
`different angles, it may not be useful for pictures taken on
`
`
`
`
`
`
`
`different days or of various sceneries. It also may require a
`
`
`
`
`
`
`
`
`
`lot of computational ability, and may take a long time to
`
`
`
`
`
`
`process and label large groups of images.
`
`
`
`
`
`
`
`
`[0010] Another similar patent provides a method for the
`
`
`
`
`
`
`searching of images according to queries containing visual
`
`
`
`
`
`
`
`
`attributes of images, including colour, texture, shape, and
`
`
`
`
`
`
`
`
`
`size [2]. These queries also contain textual tags attached to
`
`
`
`
`
`
`
`images. This is useful in retrieving images, by entering their
`
`
`
`
`
`
`
`
`
`visual or textual attributes, and searching the query. It is
`
`
`
`
`
`
`
`especially effective in searching for images by queries based
`
`
`
`
`
`on pixel information of contained images.
`
`
`
`
`
`
`
`
`[0011] This type of image search is also carried out by a
`
`
`
`
`
`
`
`patent that provides an indexing method for accelerating a
`
`
`
`
`
`
`
`
`content-based image search [3]. It can identify the most
`
`
`
`
`
`
`
`similar images by analyzing their colour, texture, shape, or
`
`
`
`
`
`
`
`content, and generating and storing index values.
`
`
`
`
`
`
`
`[0012] Colour is a common attribute used to define
`
`
`
`
`
`
`
`
`
`
`images, and most methods useit to search for images. One
`
`
`
`
`
`
`
`patent provides this type of method of image searching by
`
`
`
`
`
`
`
`
`using a multilevel image grid data structure of different
`
`
`
`
`
`
`
`
`hierarchical levels with respect to one colour in an image
`
`
`
`
`
`
`
`
`
`[15]. These grid colour levels are compared and matched,
`
`
`
`grouping similar images.
`
`
`
`
`
`
`
`[0013] Another method allows an image search by using a
`
`
`
`
`
`
`
`histogram, comprised of bins [17]. For example, a histogram
`
`Page 25 of 36
`
`Netskope Exhibit 1017
`
`Page 25 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`US 2008/0069480 Al
`
`
`
`Mar. 20, 2008
`
`
`
`
`
`
`
`
`
`
`
`of each image in a database is created using its colour
`
`
`
`
`
`information, in order of importance. If a particular colour
`
`
`
`
`
`
`
`
`
`appears in a lot of images, it is given a low priority, and
`
`
`
`
`
`
`
`
`placed at the end of the chart. Similarly, a less common
`
`
`
`
`
`
`
`
`colour would be given high priority and positioned at the
`
`
`
`
`
`
`
`
`beginning of a chart. Therefore, images that contain less
`
`
`
`
`
`
`
`
`frequent colours will be more distinguishable and would
`thus be effective bins to use.
`
`
`
`
`
`
`
`
`
`
`
`
`[0014] Other methods of searching that have been imple-
`
`
`
`
`
`
`
`
`mented to break images down into segments. One example
`
`
`
`
`
`
`
`
`
`is a patent that involves searching for and localizing an
`
`
`
`
`
`
`
`object within an image, by breaking it down into a number
`
`
`
`
`
`
`
`of geometric sub-models [5]. Geometric descriptions of
`
`
`
`
`
`
`
`
`objects can then be specified in some coordinate system,
`
`
`
`
`
`
`
`
`which enables object
`localization for a broad range of
`
`
`
`
`
`
`
`
`imaging conditions. This is an efficient method both in
`
`
`
`
`memory and computational time.
`
`
`
`
`
`
`
`[0015] Another method segments images into regions to
`
`
`
`
`
`
`
`
`which weights are assigned, and calculates the similarity
`
`
`
`
`
`
`
`between images by comparison of set weights [13]. The
`
`
`
`
`
`
`
`weights are calculated by comparing feature similarities for
`
`
`
`
`
`
`
`
`
`each region in a plurality of images. It is thus a useful
`
`
`
`
`
`
`method for searching for similar images.
`
`
`
`
`
`
`
`
`[0016] Another patented system can be used to search for
`
`
`
`
`
`
`
`images by storing codes in a database [14]. For example, it
`
`
`
`
`
`
`
`
`
`stores facial codes which define facial features in each image
`
`
`
`
`
`
`into a database,
`linking them to corresponding images,
`
`
`
`
`
`
`
`
`instead of storing whole images themselves. This allows for
`
`
`
`
`
`
`
`image searching, while reducing the amount of necessary
`
`
`
`
`
`
`
`storage, making this a fast and efficient method.
`
`
`
`
`
`
`
`
`[0017] These methods can all be extended to further
`
`
`
`
`
`
`
`
`applications, such as video and audio searches. One example
`
`
`
`
`
`
`
`of a previously implemented apparatus is one developed for
`
`
`
`
`
`
`
`the application of a surveillance camera system. This appa-
`
`
`
`
`
`
`
`
`ratus searches for a desired image through a set of images
`
`
`
`
`
`
`
`recorded by the camera, using the difference in luminance
`information between the reference and the other recorded
`
`
`
`
`
`
`
`
`
`
`images [16].
`
`
`
`
`
`
`
`[0018] What is needed therefore is novel methods and
`
`
`
`
`
`
`
`
`systems for searching, sorting, and/or displaying a set of
`
`
`
`
`
`
`
`imagesstored in a database that overcomesthelimitations of
`
`
`
`the priorart.
`
`
`
`
`
`
`
`
`
`
`selection. Those weights can then be usedto find the rank of
`
`
`
`
`
`
`
`
`
`an image (the sum of the weights for that respective image)
`
`
`
`
`
`
`
`
`and the location of the image(the centroid of the weights for
`
`
`
`
`
`
`
`that respective image). Although this centroid-based loca-
`
`
`
`
`
`
`
`tion estimate is the preferred localization technique, an
`
`
`
`
`
`
`alternative non-weighted or weighted planar prediction tech-
`
`
`
`
`
`
`
`
`nique can be used in accordance with the present invention.
`
`
`
`
`
`
`
`[0022]
`In yet another aspect of the present invention, an
`
`
`
`
`
`
`
`image display interface is provided. A set of images are
`
`
`
`
`
`
`sorted based on relevance as determined by ranking meth-
`
`
`
`
`
`
`
`ods. They are displayed according to a numberof tech-
`
`
`
`
`
`
`
`
`
`niques, including: (i) the more relevant the image is, the
`
`
`
`
`
`
`
`
`
`larger it appears relative to other images;
`(1i) the more
`
`
`
`
`
`
`
`
`
`relevant the image is, the closer it is placed to the most
`
`
`
`
`
`
`
`
`
`
`relevant image in the imageset; and (ili) images are dis-
`
`
`
`
`
`
`
`played in as small a size as possible to minimize the user’s
`
`
`
`
`
`
`
`
`eye and pointer movement when browsing images. The
`
`
`
`
`
`
`display of images is determined in accordance with a display
`
`
`packing algorithm.
`
`
`
`
`
`
`[0023] According to one embodiment, a web-based appli-
`
`
`
`
`
`
`
`
`cation provides an image display interface with tagging and
`
`
`
`
`
`
`
`
`linking functionality. The interface provides for the creation
`
`
`
`
`
`
`
`
`
`of new tags and links and provides visual representations of
`
`
`
`
`
`
`
`
`the links formed between images. Image display effects
`
`
`
`
`optimize the ease of use.
`
`
`
`
`
`[0024] According to a particular preferred embodiment, a
`
`
`
`
`
`
`system application having a web-based interface allows
`
`
`
`
`
`
`
`
`users to search, sort and display digital images. Preferably,
`
`
`
`
`
`
`
`
`
`
`a user is required to register and login before they are
`
`
`
`
`
`
`
`
`granted access to the system. The system allows users to
`
`
`
`
`
`
`
`
`upload images and access the images according to a tag
`
`
`
`
`
`
`
`
`mode, a view mode and an organizer mode. The system
`
`
`
`
`
`enables image sharing between friends.
`
`
`
`
`
`
`
`
`It should be understood that the present invention
`[0025]
`
`
`
`
`
`
`
`
`is directed at searching, sorting and/or displaying images but
`
`
`
`
`
`
`
`can be implemented in the same manner to searching,
`
`
`
`
`
`
`
`
`sorting and/or displaying other content, including but not
`
`
`
`
`
`
`
`
`
`
`limited to videos, audio, external links, as well as other
`media where a link between different entities can be drawn.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`
`
`[0026] A detailed description of the preferred embodi-
`
`
`
`
`
`
`
`ments is provided herein below by way of example only and
`SUMMARY OF THE INVENTION
`
`
`
`
`
`
`
`
`
`with reference to the following drawings, in which:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0027]
`FIG. 1 illustrates a flow diagram ofa userinterface
`In one aspect of the present invention, a point of an
`[0019]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in accordance with an aspect of the present invention.
`imageassociated with an object is assignedatag. If the same
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0028]
`FIG. 2 illustrates a simple set of images with
`object appears in two different images,
`it is assigned the
`
`
`
`
`
`
`
`
`
`
`
`
`
`recurring objects (circle, square, etc.).
`same tag and so the two points corresponding to this object
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG.3 illustrates insertion of a new imageinto the
`[0029]
`in the different images are linked through the tag. This link
`
`
`
`
`
`
`
`
`
`existing set.
`structure allowsfor an efficient registration of images within
`
`
`
`
`
`a database.
`
`
`FIG.4 is an illustration of the visual presentation of
`[0030]
`
`
`
`
`
`
`
`
`
`
`
`an image linking system.
`[0020]
`In another aspect of the present invention, a new
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0031]
`FIG. 5 illustrates a suggested linking interface,
`method of image searching andsorting is provided. Accord-
`
`
`
`
`
`
`
`
`
`
`
`
`
`allowing for any image to be linked.
`ing to this aspect, a search is initiated when a userselects a
`
`
`
`
`
`
`
`
`
`
`
`
`FIG.6 is an illustration of geometric interpolation.
`[0032]
`certain location on an image. The method utilizes one or
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0033]
`FIG. 7 is an illustration of relative locality inter-
`more interpolation techniques to search for the object cor-
`
`
`
`
`
`
`
`
`polation.
`respondingto the location selected by the user. These object
`
`
`
`
`
`
`
`
`
`
`
`FIG. 8 is an illustration of large-scale-link interpo-
`[0034]
`localization and searching techniques apply to fully speci-
`
`
`
`
`
`lation.
`
`fied or partially specified tagging/linked images.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIGS. 9A, 9B, 9C and 9D illustrate steps of an
`[0035]
`[0021]
`In another aspect of the present invention, an image
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`image ranking algorithm in accordance with an aspect of the
`ranking and localization algorithm consists of building a
`
`
`
`
`
`
`
`
`
`
`present invention.
`graphical representation of the link structure for the images
`
`
`
`
`
`
`
`
`
`
`
`
`
`and then utilizing graphical methods in order to find the
`FIG. 10 illustrates an example oflocalization esti-
`[0036]
`
`
`
`
`
`
`
`
`
`mates.
`
`respective weights of all
`link points for a given initial
`
`
`
`
`
`
`
`
`Page 26 of 36
`
`Netskope Exhibit 1017
`
`Page 26 of 36
`
`Netskope Exhibit 1017
`
`

`

`
`
`US 2008/0069480 Al
`
`
`
`Mar. 20, 2008
`
`
`
`
`
`
`
`
`
`
`
`FIG. 11 depicts an initial display of an interface for
`[0037]
`
`
`
`an image database.
`
`
`
`
`
`
`[0038]
`FIG. 12 illustrates localization and ranking of an
`
`
`
`
`
`untagged object in the image database.
`
`
`
`
`
`
`
`FIG. 13 depicts a localization and image ranking
`[0039]
`
`
`
`
`
`example for a piano in a ‘home’ database.
`
`
`
`
`
`
`
`FIG. 14 depicts a localization and image ranking
`[0040]
`
`
`
`
`
`
`
`example for a woman holding a dog in a ‘photo album’
`database.
`
`
`
`
`
`
`
`
`
`FIGS. 15A, 15B, 15C and 15D illustrate an
`[0041]
`
`
`
`
`
`
`
`
`
`example of the placement of images on an interface in
`
`
`
`
`
`
`accordance with an aspect of the present invention.
`
`
`
`
`
`
`
`FIG. 16 illustrates a tag mode example shown ona
`[0042]
`web-based interface.
`
`
`
`
`
`
`
`
`
`FIG. 17 illustrates a view mode example shown on
`[0043]
`a web-based interface.
`
`
`
`
`
`
`
`
`
`
`[0044]
`In the drawings, one embodimentof the invention
`
`
`
`
`
`
`
`
`
`is illustrated by way of example.
`is to be expressly
`It
`
`
`
`
`
`
`
`
`
`
`understood that the description and drawingsare only for the
`
`
`
`
`
`
`purpose ofillustration and as an aid to understanding, and
`are not intendedasa definition of the limits of the invention.
`
`
`
`
`
`
`
`
`
`
`
`
`DETAILED DESCRIPTION OF THE
`
`
`INVENTION
`
`
`
`
`
`
`
`[0045] One aspect of the present invention consists of an
`
`
`
`
`
`
`
`interactive spatial link-based method, system and computer
`
`
`
`
`
`
`
`program for searching, sorting and/or displaying digital
`
`
`
`
`
`
`
`
`images. Accordingto this aspect, imagesare partially tagged
`
`
`
`
`
`
`
`
`and the relational and positional information of the tags are
`
`
`
`
`
`
`
`
`utilized in order to search for untagged and unidentified
`
`
`
`
`
`
`
`objects without performing content analysis. By anchoring
`
`
`
`
`
`
`
`each tag at a specific location within an image, a specific
`
`
`
`
`
`
`
`point in several images is associated to a single unique tag.
`
`
`
`
`
`
`
`
`In other words, linking points in several images together
`
`
`
`
`
`indicates the presence of a particular object.
`
`
`
`
`
`
`
`
`
`[0046] By having several such link points in every image,
`
`
`
`
`
`
`
`
`it becomes possible to construct a graphical or circuit
`
`
`
`
`
`
`
`
`representation of the objects by utilizing the distance
`
`
`
`
`
`
`
`
`
`between the link points as a measure of the resistance
`
`
`
`
`
`
`
`
`between those points. Now, if a user wants to search for a
`
`
`
`
`
`
`
`particular linked or unlinked object, all he or she has to do
`
`
`
`
`
`
`
`
`is to click on a specific location within any image. By doing
`
`
`
`
`
`
`
`
`
`so, the click at the location can be modeled as the introduc-
`
`
`
`
`
`
`
`
`tion of a voltage sourceat a particular set of points within the
`
`
`
`
`circuit/graphical representation of the links.
`
`
`
`
`
`
`
`
`[0047] By propagating the voltages across the nodesofthe
`
`
`
`
`
`
`network (using a circuit-like potential propagation algo-
`
`
`
`
`
`
`
`rithm), it becomes possible to rank the relevance of each
`
`
`
`
`
`
`
`
`imageto the object being searched for, as well as to roughly
`
`
`
`
`
`
`
`
`
`localize the object selected within each image. In other
`
`
`
`
`
`
`
`
`
`words, the user clicks on any location within an image and
`
`
`
`
`
`
`
`
`the system automatically finds other views of that object in
`
`
`
`
`
`
`
`
`other images with only minimalinitial user tagging of the
`
`
`
`
`
`
`
`
`
`images. This approach significantly differs from the priorart
`
`
`
`
`
`
`
`in this area by its utilization of location-based tags combined
`
`
`
`
`
`
`
`
`with a novel image ranking and object localization meth-
`
`
`
`
`
`
`odology whosebasis is rooted in graph theory.
`
`
`Image Tags
`
`
`
`Image Tagging
`
`
`
`
`
`
`
`
`[0048] Aside from the conventional image data stored and
`
`
`
`
`
`accessed as pixel colours, applications such as YAHOO!™
`
`
`
`
`
`
`
`Photos and FLICKR™use uni-tags, which contain long
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`descriptions about an image without associating parts of that
`
`
`
`
`
`
`
`description with specific locations in the image. However,
`
`
`
`
`
`
`
`
`the present invention, which uses location-based tagging and
`
`
`
`
`
`
`
`linking, allows for a more descriptive explanation of an
`
`
`
`
`image as compared to these uni-tags.
`
`
`
`
`
`
`
`
`[0049] Often, with images containing multiple objects, the
`
`
`
`
`
`
`
`
`
`
`tags that explain and describe the contents of the image
`
`
`
`
`
`
`
`
`belong to one or more locations within the image. For
`
`
`
`
`
`
`example, in an image that contains a satellite photograph of
`
`
`
`
`
`
`
`
`
`a scene, several buildings may be contained that can be
`
`
`
`
`
`
`
`individually tagged based on their locations. Similarly, for
`
`
`
`
`
`
`
`
`photo albums that may contain multiple individuals, each
`
`
`
`
`
`
`
`person can be individually identified through a separate tag.
`
`
`
`
`
`
`
`
`[0050] The present invention usesa tag structure, in which
`
`
`
`
`
`
`
`
`
`points on a specific image are assigned specific tags. If the
`
`
`
`
`
`
`
`
`same object appears in two different images, it is assigned
`
`
`
`
`
`
`
`
`
`
`the same tag in both images, and so the two points corre-
`
`
`
`
`
`
`
`
`sponding to this object in the different images are hyper-
`
`
`
`
`
`
`
`
`linked through the tag. This hyperlink structureis illustrated
`as a flowchart in FIG. 1.
`
`
`
`
`
`
`
`
`
`
`
`
`[0051]
`It is important to note that these links are image-
`
`
`
`
`
`
`
`location specific, meaning that they link a specific location
`
`
`
`
`
`
`(i.e. approximate x-y position) of an image to a specific
`
`
`
`
`
`
`
`location of another image. Furthermore, while the links here
`
`
`
`
`
`
`can either be bi-directional or uni-directional, the general
`
`
`
`
`
`
`discussion focuses on bi-directional links. (In other words,
`
`
`
`
`
`although in some images there may be a uni-directional
`
`
`
`
`
`
`
`
`
`arrow, this is only for illustrative purposes and the actual
`
`
`
`link is meant to be bi-directional.)
`
`
`
`
`
`
`
`[0052] As shown in FIG. 2, each of the important objects
`
`
`
`
`
`
`
`
`in image 1 are linked to the objects of image 2 or image 3,
`
`
`
`
`
`
`
`
`
`
`or both. For example, since the circle appears in all three
`
`
`
`
`
`
`
`
`
`imagesit is linked across all three images, while the square
`
`
`
`
`
`
`
`
`only appears in images 1 and 3 and therefore there is only
`
`
`
`
`
`
`
`
`
`a single link for it, bypassing image2. In practice, these link
`
`
`
`
`
`
`
`
`structures must be manually obtained for a database of
`
`
`
`
`
`
`images, or they could be automatically obtained by conduct-
`
`
`
`
`
`
`
`ing a sub-image matching operation, which finds similar
`
`
`
`
`
`objects and links them together.
`
`
`Image Re