Structural Analysis of Preparation Steps on Supplementary
Documents of Cultural TV Programs
Reiko HAMADA, Ichiro IDE, Shuichi SAKAI, and Hidehiko TANAKA
Graduate School of Electrical Engineering, The University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
TEL: +81-3-5841-7413, FAX: +81-3-5800-6922
fide,reiko,sakai,tanakag@mtl.t.u-tokyo.ac.jp

Abstract
We propose a method to create process ow graphs automatically from documents which explain the process ofassembling something. This is realized by understanding
context by limiting the subject and making use of domain
speci c characteristics. As an example, we restrict the domain to cooking procedures, which is comparatively easy
to retrieve signi cant keywords for the domain. We will
also introduce a future plan to make the dictionary automatically from large corpora.

1 Introduction
Re ecting the increasing importance of handling multimedia data, many studies are made on indexing to TV broadcast video[2]. Multimedia data consist of image, audio,
and text, and various researches on analysis of each individual medium has been made. Especially, image analysis
has been the main theme for handling multimedia. But
recently, it has started to be considered that image analysis alone is insucient for semantic analysis of multimedia
data. In the 1990's, integrated analysis that supplements
the incompleteness of information from each medium has
become a trend[1].
Following this trend, we are trying to integrate TV programs with related documents, taking advantage of the relative easiness of extracting semantic structures from text
media. Among various programs, cultural programs are
considered as appropriate sources since (1)supplementary
documents are available and (2)the video contains a lot of
implicit information that integration could be helpful tothorough understanding of supplementary texts. We are
currently examining and constructing a practical systemusing relatively simple elemental technologies by re ecting
the result of one medium's analysis to the other. We will
focus on cooking programs, so that we can take advantageof domain speci c constraints and knowledge.
In this paper, we will propose the text analysis part ofthis system. Although our aim is to integrate informationfrom various sources, the proposal in this paper should beapplicable to texts without supplementary video.
Analyzing document structure has been an important
subject in the eld of arti cial intelligence for a long time.
Although many researches have been done to understandcontext of documents through structure analysis, it is stilla dicult problem[3, 4].
In this paper, we propose a method to understand context by limiting the subject and making use of domain
speci c characteristics. Our targets are documents which
explain the process of assembling, producing, or cooking
something. There are many documents which explain suchprocesses in the form of supplementary textbook, CD-ROM
or WWW. Information lying in these documents is enormous, but since each document exists independent fromeach other in di erent forms, it is dicult to make fulluse of the information systematically. We try to make aprocess ow graph from these documents through structure analysis. The graph makes the implicitly structured
information visible and understandable. From this graph,
we can normalize the procedures from di erently formatted documents, so that in the future they could be used
to make a database. Furthermore, the ow graph can beused for many applications, such as optimization of theassembly process.
In our method, a domain speci c dictionary is used formaking a practical system for structure analysis. We areplanning to create this dictionary automatically from text
corpora by statistical analysis in the future.

2 Structural Analysis of Preparation StepsIn this section, we propose a structural analysis method of
preparation steps in cooking textbooks.
An example of a document that explains a cooking process is shown in Fig.1. The document consists of an \Ingredients" part and a \Preparation Steps" part. The \Ingredients" part can be used to extract nouns such as ingredients and seasonings. The \Preparation Steps" part gives
explanation on how to cook the \Ingredients". We aim
at analyzing the \Preparation Steps" and create a process
ow graph.
In cooking programs, the order of steps often di er between video and textbook. Nevertheless, there are stillsome restrictions, such as the time ow of processing materials (A material once processed never returns as it was).
Therefore, extracting such restrictions from documents isessential for structuring and association. We propose amethod to create a data ow graph to make such restrictions clear, as shown in Fig.2. By this graph, restricted andun-restricted orders could be distinguished clearly (directly
linked orders can not be changed), and the structure of a
cooking process becomes very clear. Once the graph is created, it is possible to optimize the process or to gather thevideo segments corresponding to each node and restructure
a new video associated with the document.

2.1 Categorization of Cooking Terms
In our method, we only use nouns and verbs as keywords
to make a data ow graph. We categorize nouns and verbs
according to Tables 1 and 2. Words which could not be categorized to any of the categories in the Tables are omitted
from the analysis.
As shown in Table 1, we categorize nouns to Ingredients([Ing]), Seasonings([Sea]), Receptacles, and Tools. In
this experiment, we only use ingredients and seasonings foranalysis. In future, we are planning to use receptacles toknow which ingredients are put together in a receptacle.

Table 2: Categorization of Verb.
Verb
Cook Blend Separate Place
Usage
[Sol]
[Mix]
Example Bake Add Separate P lace

Ingredients
50mL flour
400mL milk
500g asparagus
8 slices ham

Cut

M ix

DivideP ut

Preparation Steps
ñ.Melt butter. Blend in flour andSeasonings, stirring constantly.
Gradually add milk, simmer
until smooth.
2.Boil asparagus until tendercrisp. Wrap the ham around theasparagus.
3. Place noodles, ham rolls inbaking dish; cover with sauce.
Bake 20 min at 180Ä.

verb dictionary, in which words are categorized according
to Tables 1 and 2. In the rest of this Section, we will discuss our method assuming that an ideal dictionary alreadyexists.

2.2 Structural Analysis Experiments

Figure 1: Example of supplementary document for a cooking program.

butter flour salt milk noodles asparagus ham
boil

blend

add

place
:Ingredients

simmercover:Seasoning
:Cook

bake

:Mix

GRATIN

Step1. Extract nouns and verbs that the document
has in common with the dictionary.
Extract nouns and verbs in the document, then make\Noun - Verb" sets. Nouns and verbs are extracted
by matching with words in the dictionary. Words
that do not exist in the dictionary are ignored. We
consider that a verb modi es the nearest noun, satisfying the no-cross condition[5].
Step2. Create intermediate states referring to verbs.
The sets with [Mix] verbs are connected with any
previous set. New numbers are assigned to each of
the new states in this process.

wrap

stir

We will introduce the process of structural analysis for creating a data ow graph. The steps to create the ow graphis as follows::PlaceFigure 2: Example of a data ow graph.
As shown in Table 2, we categorize the verbs into \Cook", \Blend", \Separate" and \Place". But in this experiment, we categorize these types into 2 big titles, [Sol]and [Mix]. [Sol] includes \Cook" verbs and [Mix] includes\Blend", \Separate" and \Place" verbs. [Sol] cooks single
ingredients, such as `Bake' and `Cut'. On the other hand,\Blend" mixes several ingredients, such as `Add', `Mix' and`Sprinkle', \Place" puts ingredients in receptacles, such asa `baking dish'. If several ingredients are put in a dish,these ingredients are mixed in the dish. So we categorized\Place" verbs in the [Mix] category. In the case of a \Separate" verb, it is clear that originally, these ingredients were
one ingredient. So, \Separate" verbs are also categorized
in the [Mix] category.
We are planning to make a domain speci c noun andStep3. Connect intermediate states referring to nouns.
The intermediate states created in the previous step
are connected and data stream is completed in thisstep. First, if there is a \process number" in the process, all the states in that process are connected withthe precess with the \process number". Next, otherstates are connected with the nearest state which has
the same \ingredients". And nally, if there are somestates left, these are connected with the nearest states
which has the same \seasonings". If the categorization of \ingredients" and \seasoning" in the dictionary is correct, we may not need the last rule. But,
there may be mistakes in the dictionary, such as miscategorization of an ingredient as a seasoning or viceversa, since it is dicult to statically categorize somematerials as an ingredient or a seasoning.
An example of the creation process is shown in Fig.3.
We actually applied the method to Japanese documents,
so noun and verb in the example is in reverse order to thatin English.

2.3 Preliminary Experiment

We applied the previous steps to an actual supplementary
document for a cooking program. The text book and its
dictionary is showed in Fig.4. The actual experiment was
performed to a Japanese document, and the English sentences in the following experiment are translations from aJapanese textbook. Note that the domain speci c dictionary used in the experiment was manually created in thiscase.
Table 1: Categorization of Noun.
The data ow graph of the result is shown in Fig.5. The
Noun
Ingredients Seasonings Receptacles Tools
ow of the cooking procedure is visible and easily underUsage
[Ing]
[Sea]
(Currently not used.) standable from the graph. It is shown that the proposed
method works at least for an easy cooking textbook.
ExampleCarrot
Salt
Dish
Oven
ChickenP epper

P lateKnif eOriginal Document
1. Cut chicken, season with salt and peppers. After a while, sprinkle
with flour. Slice mushrooms.
2. Bake chicken in frying pan. Add sauce, mushrooms and fry.
3. Place (2) on the plate and sprinkle with parsley.

1. cutsaltsprinkle

pepper

2. bake
3. placechickenadd(2)

sprinkle

sauce

cut

Create Intermediate States referring
to verbs.

pepper

1-2

flour

slice mushrooms

sprinkle

season3-1

2-1
chicken

sauce

bake

add

mushrooms(2)

parsley

fry

place

sprinkle

Step3.

Connect Intermediate states

1-1
chicken
cut

1-2
salt

pepperslice mushrooms

flour
sprinkle

seasonchicken

sauce

bake

add

mushrooms

2-1

fry

Legends::[Sol]:[Mix]:[Ing]:[Sea]

2-1

bonito:Ingredients:Seasoning
:Cook
:Mix
:Placecauliflower
cut

cook
add
blend

3-1

mushrooms fry
parsley

1-1
salt

put

serve

Step2.

chicken

put

flour

slice mushrooms

Seasoning

boil

cut

1-2

Make noun-verb sets.

seasonchickenput

1-1

1. Cut chicken, season with salt and peppers. After a while, sprinkle
with flour. Slice mushrooms.
2. Bake chicken in frying pan. Add sauce, mushrooms and fry.
3. Place (2) on the plate and sprinkle with parsley.
Step1'.

soup stock

cut

Find nouns and verbs listed
in the Dictionary.

Step1.

chicken(2)

parsleyplacesprinkle

3-1

Figure 3: Structuring Preparation Steps in Cooking Textbook

Figure 5: Data ow graph from Result of a Preliminary
Experiment.

3 Automatic Retrieval of Domain Speci c Dictionary
3.1 Overview
In the previous section, we assumed that an ideal dictionary already exists. But, creating a dictionary in eachdomain manually is burdensome. So, we are attempting toautomatically create a domain speci c dictionary.
The text which explain how to make something uses
characteristic keywords compared to general sentences. For
example, there are few words such as `cook', `boil', `bake'and `chicken' in newspapers. Then, it is relatively easy
to extract such characteristic keywords from these documents statistically. We are now investigating several ideas
introduced in this Section.

3.2 Automatic Retrieval of Cooking Terms
1. Extraction of Nouns from \Ingredients"
Cooking textbooks always have a \Ingredients" part,and other textbooks on assembly and production also
have lists of materials. We are planning to extract
nouns from these lists. The result of nouns extracted
from \Ingredients" of actual cooking documents isshown in Table 3. The list is ordered by frequency.
We gathered the documents from WWW sites.
Table 3: Noun Lists Extracted from \Ingredients"
Noun
Salt
Oil
PepperSoy sauce
Sugar
Sake

GingerButter
GarlicOnion
CarrotStarchFigure 4: The Document and Dictionary for Preliminary
Experiment.

Freq.
864
437
361
345
339
287
212
199
164
164
155
148

Noun
Soup
Leek
Egg
Sweet sake

VinegarSesame oil
White wine
Water
Olive oil
Bouillon
111

TOTAL

Freq.
147
144
144
139
132
105
97
92
88
85
111

11,7002. Extraction of Verbs from \Preparation Steps"
Verbs can be extracted from \Preparation Steps".
Words are not separated in Japanese sentences, so wemust detect the boundaries. We used the morphological analysis system \JUMAN"[6] for this task. \JU-MAN" outputs morpheme and their parts-of-speech.
In the \Preparation Steps", there are many generalwords that can not be used as keywords. So, we use
TF-IDF to separate these general words. Using ageneral corpus S , and a speci c domain's document
C , we can determine the TF-IDF as:
fTF 0IDF =F reqc =Allc
F reqs =Alls(1)

Where Alls and Allc stand for all the verb's number in the corpus and the document, and F reqs andF reqs the target verb's frequency in the corpus andthe document. We are planning to remove the words
which get lower marks in TF-IDF and extract thetrue keywords of each domain. As a general corpora,newspaper articles in RWC text database (RWC-DBTEXT-95-2) [7] were used.
The verbs ordered by frequency in the \Preparation
Steps" are shown in Table 4. Many cooking terms inthe document are so domain speci c, that they neverappear in newspaper articles, thus get in nity score in
fTF 0IDF , so it is more signi cant to show the words
with lower score than higher score as shown in Table
5. The words listed in the Table does not seem to besuitable as cooking keywords. We will remove theseterms from the dictionary.
Table 4: Result of Extraction of Verbs from Documents.
Verb
Freq.
する
(Do)
3,400
加える
(Add)
2,056
入れる
(Put)
1,976
切る
(Cut)
1,342
炒める
(Fry)
858
かける
(Put over)
819
混ぜる
(Mix)
733
とる
(Take)
696
つける(Put on)636
盛る(Serve)584
ふる(Sprinkle)
525
熱する(Heat)
505
むく(Peel)
444
きる(Remove)438
ゆでる(Boil)
413
煮る(Boil)
395
まぶす(Sprinkle)
325
焼く(Roast)320
洗う(Wash)
319
合わせる (Add)
306
111

TOTAL

111

30,161

3. Extraction of Associated Noun-Verb Pairs.
There are some expressions that speci c nouns andverbs associatively function. They can not be analyzed properly individually. Futhermore, from theseassociated pairs, sence of nouns or verbs can be guessedmutually. We extracted these associations by cooccurrence frequency. It could generally be consideredthat a verb modi es the nearest noun and we counted
such noun and verb pairs' cooccurrence frequency.
List of the result is shown in Table 6. As shown in
Table 6, reasonable pairs were extracted.
4. Categorization of Words by cooccurrence Frequency.
We can estimate the sense of verb or noun from associated pairs if the category of the other side of theTable 5: Result of TF-IDF (Lowest Score).
Verb
fTF 0IDF
いる(Be)
0.0031
言う(Say)
0.0049受ける (Receive)0.0058知る(Know)
0.0071
いう(Tell)
0.0099
見る
(See)
0.010
続ける (Continue)
0.011
やる
(Do)
0.013
かかる (Hang)
0.014
決まる (be Decided) 0.018
生きる (Live)
0.021
できる (Can)
0.022
買う
(Buy)
0.023
よる
(Approach)
0.025
求める (Seek)
0.027
待つ(Wait)
0.027
くる(Come)
0.028
当たる (Hit)
0.029
集める (Gather)0.029
感じる (Feel)
0.033
111

111

verb or noun is known. For example, seasonings almost always cooccur with a \Mix" category verb, or
receptacles cooccur with a \Place" category verb.
First, we are planning to build a core dictionary whichcontains few correctly categorized basic terms. Using
the previously introduced statistical methods, the vocabulary of each categories will be extended from thecore dictionary.

4 Conclusion
We proposed a structure analysis method for documents
which explain product process to create a data ow graphautomatically. This is realized by making use of a domain
speci c dictionary. We showed the e ectiveness of the proposed method by a preliminary experiment. Furthermore,
we are planning to create the domain speci c dictionary
automatically in the future.
The data ow graph of documents are useful for integrating with video and other applications such as optimizing the process.
Furthermore, through the usage of a supplementary
document and its analysis, we aim for proposing a novel
advanced multimedia integration method. Using the resultof this method, we will also propose an integrative restructuring method of the multimedia data provided both fromthe video and the supplementary document in the future.

Acknowledgment
RWC text database is a product of Real World Computing Partnership (RWCP), and was used under a licensedagreement.

References[1] D. Ponceleon, S. Sriniivasan, A. Amir, D. Petkovic,
D. Diklic; \Key to E ective Video Retrieval: E ective Cataloging and Browsing", ACM Multimedia'98,
pp.99-107, Aug., 1998.

Table 6: Result of Extracted Association Sets by Cooccurrence Frequency
Noun
Verb
Freq.
器
(dish)
盛る (serve)
480
皮(peel)むく (peel)377
水気(moisture)
きる (remove)315
せん切り (cutting into strips) する (do)298
大さじ (tablespoon)
熱する (heat)278
塩(salt)ふる (sprinkle)
274
塩(salt)する (do)274
薄切り (slice)する (do)265
みじん切り (cut ne)する (do)262
油(oil)
熱する (heat)251
長さ(length)切る (cut)
242
塩(salt)加える (add)
226
鍋
(pot)
入れる (put)221
半分(half)切る (cut)
200
ふた(cover)する (do)179
電子レンジ (microsave oven)
かける (bake in)178
しょうが (ginger)
する (do)170
大さじ (tablespoon)
入れる (put)170
ボール (bowl)
入れる (put)163
こしょう (pepper)する (do)
163
111

TOTAL

111

111

61,350[2] Wactler, H. D., Hauptmann, A. G., Witbrock, M. J.;\Informedia News-on-Demand: Using Speech Recognition to Create a Digital Video Ligrary", CMU Tech.
Rep., CMU-CS-98-109, Mar, 1998.
[3] H. Fukumoto, J. Fukumoto, Y. Suzuki: \An Automatic Extraction of Key Paragraphs Based on the Degree of Context Dpendency(in Japanese)", Journal of
Natural Language Processing, Vol.4, No.2, Apr., 1997.
[4] Y. Ogisawa, N. Inui, Y. Kotani, H.Nisimura: \Analyzing Stories based on Relation between Two Sentences(in Japanese)", IPSJ SIG Notes, 96-NL-112,
Mar., 1996.
[5] S. Kurohashi, M. Nagao: \A Syntactic Analysis
Method of Long Japanese Sentences based on Coordinate Structures' Detection", Journal of Natural Language Processing, Vol.1, No.1, Mar., 1994.
[6] Language Media Lab:, Grad. School of Informaatics,
Kyoto Univ.; \Japanese Morphological Analysis System JUMAN version 3.6", Nov 1998.
[7] Real World Computing Partnership (RWCP); \RWC
Text Database", Mar, 1996.