Image-clustering method and apparatus

[0001] This application is based on and claims priority from Korean Patent Application No. 10-2005-0061346, filed on Jul. 7, 2005, the disclosure of which is incorporated herein by reference.

[0002] 1. Field of the Invention

[0003] The present invention relates to the image clustering, and more particularly to a method and apparatus for clustering images by inferring a unit of event, which is recognized by a user, from a user's image-use pattern.

[0004] 2. Description of Related Art

[0005] Recently, with the development of image-capturing technology and digital image signal processing technology, image-capturing devices, such as digital cameras and camcorders, have become popular, and many people use such devices.

[0006] The image-capturing device, unlike a conventional analog camera, can take several hundreds of pictures. A user can categorize the pictures by events, store them in the form of an album, and output them.

[0007] As the number of pictures becomes very large, it is difficult for the user to categorize such pictures. Accordingly, methods for automatically categorizing the pictures have been proposed.

[0008] For example, pictures can be automatically categorized based on the similarity among pictures, as shown in FIGS. 1A through 1C.

[0009] FIG. 1A is a view illustrating pictures categorized based on color, FIG. 1B is a view illustrating pictures categorized based on texture, and FIG. 1C is a view illustrating pictures categorized based on shape or location of a specified object in the pictures.

[0010] It is difficult to accurately represent the features of the pictures that a user intends to retrieve through the above-described categorization methods. Also, since a human generally has an inclination to arrange events in the order of their creation time, it is not suitable to categorize the pictures merely based on the specified objects.

[0011] In order to address the above problems, an example of clustering pictures based on their creation time is shown in FIGS. 2A through 2C.

[0012] FIG. 2A illustrates a calendar-type browser interface method for grouping pictures by month of creation for one year and displaying representative pictures among the pictures photographed every month. FIG. 2B illustrates a method whereby if the pictures, for example, which correspond to March, are selected among the pictures displayed as shown in FIG. 2A, the pictures photographed in March are displayed by day. FIG. 2C illustrates a method whereby photographing times of the pictures are compared with each other and, if an interval between the shooting times of two successive pictures exceeds a predetermined time, the two pictures are categorized into different events.

[0013] The clustering method based on the creation time cannot reflect the unit of events recognized by respective users. Specifically, only objective information, such as the shooting time, can be reflected, but a user's image-use pattern, such as a user's picture-use history, a user's explicit event categorization, tag information added by the user, and others, cannot be reflected.

[0014] An aspect of the present invention provides an apparatus and method for clustering images by inferring a unit of event recognized by a user through the reflection of a user's image-use pattern.

[0015] According to an aspect of the present invention, there is provided an image-clustering apparatus, including an image-storage module storing a plurality of images, an application module accessing the stored images according to an image-use pattern, a parameter adjustment module adjusting parameters for clustering the stored images, and an image-clustering module clustering the stored images by using values corresponding to the image-use pattern and the adjusted parameters.

[0016] According to another aspect of the present invention, there is provided an image-clustering method, including storing a plurality of images, accessing the stored images according to an image-use pattern, adjusting parameters for clustering the stored images, and clustering the stored images by using values corresponding to the image use pattern and the adjusted parameters.

[0017] According to another aspect of the present invention, there is provided a computer-readable storage medium encoded with processing instructions for causing a processor to execute the aforementioned image-clustering method.

[0018] According to another aspect of the present invention, there is provided an image-clustering apparatus including: an application module accessing stored images according to an image-use pattern; a parameter adjustment module adjusting parameters for clustering the stored images; and an image-clustering module clustering the stored images using values corresponding to the image-use pattern and to adjusted parameters.

[0019] Additional and/or other aspects and advantages of the present invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.

[0020] The above and/or other aspects and advantages of the present invention will become apparent and more readily appreciated from the following detailed description, taken in conjunction with the accompanying drawings of which:

[0021] FIGS. 1A through 1C are views illustrating examples of picture categorization based on a specified object according to the conventional art;

[0022] FIGS. 2A through 2C are views illustrating examples of picture clustering based on a temporal order according to the conventional art;

[0023] FIGS. 3A through 3D are views illustrating examples of a user's image-use pattern according to an embodiment of the present invention;

[0024] FIG. 4 is a block diagram illustrating the construction of an image-clustering apparatus according to an embodiment of the present invention;

[0025] FIG. 5 is a flowchart illustrating an image-clustering process according to an embodiment of the present invention; and

[0026] FIG. 6 is a view illustrating a user interface according to an embodiment of the present invention.

[0027] Reference will now be made in detail to embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The embodiments are described below in order to explain the present invention by referring to the figures.

[0028] Embodiments of the present invention are described hereinafter with reference to flowchart illustrations of user interfaces, methods, and computer program products. It is to be understood that each block of the flowchart illustrations, and combinations of blocks in the flowchart illustrations, can be implemented by computer program instructions. These computer program instructions can be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart block or blocks.

[0029] These computer program instructions may also be stored in a computer usable or computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer usable or computer-readable memory produce an article of manufacture including instruction means that implement the function specified in the flowchart block or blocks.

[0030] The computer program instructions may also be loaded into a computer or other programmable data processing apparatus to cause a series of operations to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions that execute on the computer or other programmable apparatus provide operations for implementing the functions specified in the flowchart block or blocks.

[0031] And each block of the flowchart illustrations may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that in some alternative implementations, the functions noted in the blocks may occur out of order. For example, two blocks shown in succession may in fact be executed substantially concurrently or the blocks may sometimes be executed in reverse order, depending upon the functionality involved.

[0032] In the following description, a scene photographed by an image-capturing device, such as a digital camera or a camcorder, and stored in a specified format is referred to as an “image”. It is assumed that information on the shooting time of an image is collected by an image-capturing device. For example, most commercial digital cameras store the shooting times according to an international standard EXIF (Exchangeable Image File), when the image is stored in a JPEG format.

[0033] Since the following described embodiments of the present invention should infer the unit of an event recognized by the user from the user's image-use pattern, and should put the inference to practical use in an event categorization, it is necessary to define a user's image-use pattern.

[0034] The user's image-use pattern includes i) change of a keyword tag, ii) cluster selection when a slide show, a moving picture, an e-mail, or a photo blog is prepared, and iii) an explicit categorization by the user. FIGS. 3A through 3D show examples of image-use patterns.

[0035] FIG. 3A shows an example of the change of the keyword tag among the user's image-use patterns, and represents that the user tends to give the same keyword tag to the same event. More specifically, picture #1 through picture #3 are indexed by a keyword tag of excursion, picture #4 is indexed by a keyword tag of birthday, picture #5 is indexed by a keyword tag of graduation, and picture #6 through picture #9 are indexed by a keyword tag of business trip. Accordingly, the images having the same keyword tag are regarded as the same events through the user's image-use pattern. This tendency was reported by Kuchinsky et al., “Fotofile: A Consumer Multimedia Organization and Retrieval System”,. Proceedings of CHI, 1999.

[0036] FIGS. 3B and 3C show examples of the cluster selection among the user's image-use patterns. The user may watch the slide show using picture #4 and picture #5, as shown in FIG. 3B, or transfer picture #3 and picture #5 to the other person via the e-mail, as shown in FIG. 3C. In this case, since the user generally selects a wanted image in the unit of similar event or related event, the user can cluster the selected images by using the user's image-use pattern.

[0037] FIG. 3D shows an example of the cluster selection among the user's image-use patterns, in which the user can categorize the events explicitly. More specifically, the user designates picture #1, picture #2, and picture #3 as one event, designates picture #4 and picture #5 as one event, designates picture #6, picture #7, and picture #8 as one event, and designates picture #9 as one event. In this case, the images are clustered in the unit of the event individually designated.

[0038] Specifically, the present embodiment utilizes the three image-use patterns of the user, so that the results are reflected on the image clustering.

[0039] FIG. 4 is a block diagram illustrating the construction of an image-clustering apparatus 400 according to an embodiment of the present invention. The image-clustering apparatus 400 includes an image-clustering module 410, a parameter adjustment module 420, an image-storage module 430, an application module 440, an interface module 450, and a display module 460. The image-clustering module 410, the parameter adjustment module 420, and the application module 440 may be integrated into one module.

[0040] The image-clustering apparatus 400 includes devices for categorizing the stored images based on the specified standard and providing the user with the categorized images, such as, by way of non-limiting examples, a digital camera, a camcorder, a personal computer, a notebook computer, and a PDA, and such devices having the functions of these exemplary devices.

[0041] The term “module”, as used herein, means, but is not limited to, a software or hardware component, such as a Field Programmable Gate Array (FPGA) or Application Specific Integrated Circuit (ASIC), which performs certain tasks. A module may advantageously be configured to reside on the addressable storage medium and configured to execute on one or more processors. Thus, a module may include, by way of example, components, such as software components, object-oriented software components, class components and task components, processes, functions, attributes, procedures, subroutines, segments of program code, drivers, firmware, microcode, circuitry, data, databases, data structures, tables, arrays, and variables. The functionality provided for in the components and modules may be combined into fewer components and modules or further separated into additional components and modules.

[0042] The image-storage module 430 stores a plurality of images therein, and the stored image may have any format which can be recognized by the image-clustering apparatus 400. The images stored in the image-storage module 430 may be images taken by the image-clustering apparatus 400, or received from an external image providing device through an interface module 450.

[0043] Specifically, the interface module 450 may perform serial or parallel communication with other image providing devices to receive an image, or form a cable or wireless network together with other image devices to receive an image. The received image may be transferred to and stored in the image-storage module 430.

[0044] The user may explicitly specify the range of an event with respect to the images stored in the image-storage module 430 through the application module 440 so as to cluster the images. For example, if there are one hundred images in the image-storage module 430, image #1 to image #50 are designated as a first event, image #51 to image #70 are designated as a second event, and image #71 to image 100 are designated as a third event.

[0045] The information on the range of the designated event is transferred to the parameter adjustment module 420 through the image-clustering module 410, and the parameter adjustment module 420 adjusts parameters based on the transferred information. In this case, the parameter can be seen as a weight value for each element which can be reflected when the image clustering is performed, and includes the change of a keyword tag and the image cluster selection. The parameter may be set through learning.

[0046] Also, the user may add the keyword tag to the image stored in the image-storage module 430 through the application module 440, or select a plurality of images so as to prepare a slide show, a moving picture, an e-mail, or a photo blog. That is, the application module 440 may be regarded as an application capable of accessing the images stored in the image-storage module 430.

[0047] The results obtained from the operation of the application module 440 are transferred to the image-clustering module 410.

[0048] The image-clustering module 410 may cluster the images stored in the image-storage module 430 by using the parameters adjusted by the parameter adjustment module 420 and the processing results received from the application module 440. In this case, the image-clustering module 410 may perform its operation in combination with a conventional algorithm for clustering the images.

[0049] The information on the clustering may be stored in various forms. For example, the information may be stored in the image-storage module 430 in the form of a mark-up language such as an extensible markup language (XML), or may be stored in a separate storage area (not shown).

[0050] The images clustered by the image-clustering module 410 may be provided to the user through the display module 460. The display module 460 includes a device (e.g., a monitor or liquid crystal display panel) to visually output the clustered images to the user, and a circuit for driving the device.

[0051] The operation of the image-clustering apparatus shown in FIG. 4 will now be described in detail with concurrent reference to the flowchart of FIG. 5.

[0052] When the image-clustering apparatus 400 receives a clustering command for the images stored in the image-storage module 430 from the user, it determines whether to cluster the successive images.

[0053] For example, if m images are stored in the image-storage module 430, the image-clustering apparatus determines whether to perform a clustering between the first image and the second image, and then determines whether to perform a clustering between the second image and the third images. FIG. 5 shows the process of determining whether to perform the clustering between the (N−1)-th image and the N-th image.

[0054] First, the image-clustering module 410 confirms whether the clustering is explicitly designated by the user with respect to the (N−1)-th image and the N-th image S510.

[0055] In this case, the function indicative of “user's explicit designation” is defined as “EI” (explicit input), and EI for the (N−1)-th image and the N-th image is indicated as “EI_N”.

[0056] The function value of EI_N will be defined as follows.
EI_N=1  (i)

[0057] This refers to a case in which a user has explicitly designated that when the images are arranged in the order of their creation time, the N-th image and the (N−1)-th image are included in the same event.
EI_N=0  (ii)

[0058] This refers to a case in which a user has explicitly designated that when the images are arranged in the order of their creation time, the N-th image and the (N−1)-th image are included in different events.
EI_N=0.5  (iii)

[0059] This refers to a case which corresponds to neither of the above two cases.

[0060] When the clustering has been explicitly designated by the user in operation S510, that is, EI_N is “0” or “1”, the parameter is adjusted S520. Since the user has explicitly designated the clustering, the parameter adjustment is needed. At this time, the parameter is an initial value, and may be preset as an arbitrary value when the image-clustering apparatus 400 is manufactured.

[0061] If the parameter is expressed as “w”, the parameter adjustment may be performed by defining an error function E(w) and performing a gradient-descent method for “w”. In this case, the gradient-descent method corresponds to a known algorithm.

[0062] According to the gradient-descent method, the value w(n) may be expressed by Equation (1). $\begin{array}{cc}w\left(n\right)=w\left(n-1\right)-\alpha \frac{\partial E\left(w\right)}{\partial w}& \left(1\right)\end{array}$
The error function E(w) may be expressed by Equation (2).
$\begin{array}{cc}E\left(w\right)=\sum _{{\mathrm{EI}}_N=0or{\mathrm{EI}}_N=1}{\left({\mathrm{EI}}_N-\frac{1}{1+e^{-x}}\right)}^2& \left(2\right)\end{array}$
In Equation (2), $\frac{1}{1+e^{-x}}$
is a sigmoid function, which will be described in Equation (4). By differentiating E(w) with respect to “w”, the results are obtained as in Equation (3). $\begin{array}{cc}\frac{\partial E\left(w\right)}{\partial w}=\sum _{{\mathrm{EI}}_N=0\mathrm{or}{\mathrm{EI}}_N=1}2\left({\mathrm{EI}}_N-\frac{1}{1+e^{-x}}\right)\left(-\frac{e^{-x}}{{\left(1+e^{-x}\right)}^2}\right)\frac{\partial x}{\partial w}& \left(3\right)\end{array}$

[0063] In this case, the value w(n) means the parameter needed to perform the clustering with respect to the (N−1)-th image and the N-th image, and may be obtained by repeating the process of Equation (1) until the value w(n) becomes equal to the value w(n−1) according to the gradient-descent method. Herein, α is a constant value arbitrarily taken, for example, 0.05.

[0064] There may be a plurality of parameters w according to elements reflected when the image clustering is performed. In order to discern the parameters, the parameters w may be expressed as w₁, w₂, w₃, W_n.

[0065] If the parameter is adjusted in operation S520, the image clustering is performed based on the value of EI_N S530. That is, if EI_N=1, the images are clustered on condition that the N-th image and the (N−1)-th image are included in the same event. If EI_N=0, the images are separated from each other based on a condition that the N-th image and the (N−1)-th image are included in different events.

[0066] Meanwhile, in operation S510, if the clustering is not explicitly designated by the user, it is determined that EI_N=0.5, and the image-clustering module 410 confirms whether the N-th image and the (N−1)-th image are selected as a cluster when the interested images are used at the production of moving images or the preparation of e-mails S540.

[0067] At this time, the function indicative of the cluster selection may be defined as “CS (cross selection)”, CS for the (N−1)-th image and the N-th image is expressed as “CS_N”.

[0068] The function value of CS_N may be defined as follows. However, it is to be understood that the following defined function value is merely exemplary, and that other defined functions are contemplated.
CS_N=1  (i)

[0069] When the images are arranged in the order of their creation time, and there is a history in that the same cluster has been selected before and after the N-th image, that is, when the i-th image satisfying the condition of (i≦N−1) and the j-th image satisfying the condition of (N≦j) are selected as a cluster, the function value of CS_N is set to “1”.
CS_N=0  (i)

[0070] This refers to a case that does not correspond to the above case.

[0071] If the function value of CS_N is set in operation S540, the image-clustering module 410 confirms whether the keyword tag is added to the N-th image and the (N−1)-th image S550.

[0072] In this case, the function indicative of the keyword tag change is defined as “target changed (TC)”, and TC for the (N−1)-th image and the N-th image will be expressed as “TCN”.

[0073] The function value of TC_N may be defined as follows. However, it is to be understood that the following defined function value is merely exemplary, and that other defined functions are contemplated.
TC_N=1  (i)

[0074] This refers to a case in which when the images are arranged in the order of their creation time, the (N−1)-th image and the N-th image have different keyword tags added thereto.
TC_N=0  (ii)

[0075] This refers to a case in which when the images are arranged in the order of their creation time, the (N−1)-th image and the N-th image have the same keyword tags added thereto.
TC_N=0.5  (iii)

[0076] This refers to a case that corresponds to neither of the above two cases. In this case, both the two pictures have no keyword tag.

[0077] The image clustering is performed based on EI_N, CS_N, and TC_N selected in the operations S510, S540, and S550 and the initially or previously set parameters w S560.

[0078] At this time, as an element that is reflected when the image clustering is performed, a conventional algorithm that has been used for image or event clustering may be adopted, in addition to the elements such as EI_N, CS_N, and TC_N.

[0079] In performing the image-clustering method in operation S560, whether to cluster or separate the successive images is determined by comparing a specified function value with a reference value, and advantageously by using a sigmoid function.

[0080] Specifically, if Equation (4) is effected for a specified x, the successive images may be determined not to be clustered, but to be separated from each other. $\begin{array}{cc}\frac{1}{1+e^{-x}}\ge 0.5& \left(4\right)\end{array}$
In this case, x may be expressed in the form that includes the conventional algorithms, in addition to the elements such as EI_N, CS_N, and TC_N.

[0081] For example, according to U.S. Patent Unexamined Publication No. 2003-0009469, on the assumption that a time gap between the i-th image and the (i+1)-th image is gi when the images are arranged in the order of their creation time, the i-th image and the (i+1)-th image may be separated if the time gap satisfies the condition of Equation (5). $\begin{array}{cc}\log \left(g_N\right)\ge K+\frac{1}{2d+1}\sum _{i=-d}^d\log \left(g_{N+i}\right)& \left(5\right)\end{array}$
In this case, K determines the unit of the event, in which as the value K becomes larger, the unit of the event is increased, while as the value K becomes smaller, the unit of the event is decreased.

[0082] Thus, in Equation (4), x may be expressed by Equation (6). $\begin{array}{cc}x=w_1\log \left(g_N\right)+w_2\frac{1}{2d+1}\sum _{i=-d}^d\log \left(g_{N+i}\right)+w_3{\mathrm{CS}}_N+w_4{\mathrm{TS}}_N+w_5& \left(6\right)\end{array}$
In this case, w₁ through w₅ indicate parameter values according to an embodiment of the present invention, and each parameter value is a value set through operation S520, or a previously set value as an initial value when the image-clustering apparatus 400 is manufactured.

[0083] For example, the value w₁ may be expressed by Equation (7) by applying Equation (3) thereto. $\begin{array}{cc}\frac{\partial E\left(w\right)}{\partial w_1}=\alpha \sum _{{\mathrm{EI}}_N=0\mathrm{or}{\mathrm{EI}}_N=1}2\left({\mathrm{EI}}_N-\frac{1}{1+e^{-x}}\right)\left(-\frac{e^{-x}}{{\left(1+e^{-x}\right)}^2}\right)\log \left(g_N\right)& \left(7\right)\end{array}$

[0084] As an alternative, when the image cluster is separated by events, the image cluster is separated into two clusters by clustering time intervals of image photographing, and the cluster corresponding to the wider time interval is processed as a boundary of the event, as disclosed in U.S. Pat. No. 6,606,411.

[0085] Here, on the assumption that P₁ is a probability that the image is contained in an inter-event cluster and P₂ is a probability that the image is contained in an intra-event cluster, the value x may be expressed as Equation (8) by applying Equation (4) thereto.
x=w₁P₁(g_N)+w₂p₂(g_N)+w₃CS_N+w₄TS_N+w₅  (8)

[0086] According to U.S. Patent Publication No. 2003-0009469 and U.S. Pat. No. 6,606,411, the user's picture use history and the event explicitly categorized by the user are not reflected in the image clustering. In the present embodiment of the present invention, the user's image-use pattern can be reflected in the image clustering.

[0087] FIG. 6 is a view illustrating a user interface according to an embodiment of the present invention. The user interface of FIG. 6 is described with concurrent reference to FIG. 4. A user interface 600 can provide images clustered by the image-clustering module 410 to the user through the display module 460.

[0088] The images clustered by the image-clustering module 410 are provided in the form of a virtual folder 620 as one cluster, and the user interface 600 provides several clusters created by the above process to the user. Each cluster can display a certain image among the images contained in its cluster on its cluster surface as a representative image.

[0089] Certain images may be selected among the images contained in each cluster, and be transferred to a selection basket 610. The transferred images may be transmitted by a user via e-mail, or transferred to a blog. Also, a slide show may be performed by using the images contained in the selection basket 610. That is, the user's image-use pattern may be reflected through the images contained in the selection basket 610.

[0090] Also, the images may be moved from one cluster to other cluster by an image moving menu 630. The user can explicitly categorize the range of events to cluster the images.

[0091] Comparing the performance obtained according to an embodiment of the present invention with that of the conventional image clustering algorithm by experiments, it can be shown that the clustering precision is remarkably improved.

[0092] In the experiments, personal pictures were received from three persons (user #1, user #2, and user #3), which includes 716 pictures of user #1 photographed during 1012 days, 1024 pictures of user #2 photographed during 1204 days, and 207 pictures of user #3 photographed during 509 days. Letting the respective users directly designate the ranges of events, recall, precision, and F-measure, results of the algorithm were measured.

[0093] The recall is a ratio of the events found by the algorithm among the categories of the events explicitly designated by the user, the precision is a ratio of the events explicitly designated by the user among the categories of the events computed by the algorithm, and the F-Measure is a geometric mean of the recall and the precision, which is a measure generally used to compare the performances of information retrieval algorithms. If the algorithm computes all pictures as separate events, the recall becomes 1.0, but the precision becomes lowered greatly.

[0094] If the algorithm computes all pictures as one event, the precision becomes 1.0, but the recall becomes lowered greatly. Consequently, when both the recall and the precision are high, a good performance can be obtained. To this end, the F-measure which is the geometric mean between the recall and the precision has been widely used as a performance comparing measure.

[0095] In Tables (1) to (3) below, the conventional art 1 corresponds to the technique disclosed in U.S. Patent Unexamined Publication No. 2003-0009469, and the conventional art 2 corresponds to the technique disclosed in U.S. Pat. No. 6,606,411.

TABLE (1)
User #1
	Recall	Precision	F-Measure
	Conventional Art 1	1.0	0.47	0.64
	Conventional Art 2	1.0	1.0	1.0
	Embodiment of	1.0	1.0	1.0
	Present Invention

[0096]

TABLE (2)
User #2
	Recall	Precision	F-Measure
	Conventional Art 1	0.91	0.43	0.59
	Conventional Art 2	1.0	0.21	0.35
	Embodiment of	0.78	0.80	0.79
	Present Invention

[0097]

TABLE (3)
User #3
	Recall	Precision	F-Measure
	Conventional Art 1	0.86	0.83	0.85
	Conventional Art 2	0.97	0.58	0.73
	Embodiment of	0.93	0.93	0.93
	Present Invention

[0098] According to the above-described embodiments of the present invention, since the user's image-use pattern is reflected, the image clustering that possibly corresponds to the event recognized by the user can be provided.

[0099] Although a few embodiments of the present invention have been shown and described, the present invention is not limited to the described embodiments. Instead, it would be appreciated by those skilled in the art that changes may be made to these embodiments without departing from the principles and spirit of the invention, the scope of which is defined by the claims and their equivalents.