(12)
`
`United States Patent
`Iwamura
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,188,010 B1
`Feb. 13, 2001
`
`US006188010B1
`
`(54) MUSIC SEARCH BY MELODY INPUT
`
`6,031,174 * 2/2000 Takabayashi ......................... .. 84/609
`
`(75) Inventor: Ryuichi Iwamura, San Diego, CA (US)
`_
`_
`(73) Asslgnees: Sony Corporatlon, Tokyo (JP); Sony
`Electronics, Inc., Park Ridge, NJ (US)
`
`OTHER PUBLICATIONS
`MIDISOFT Desktop Sheet Music 2.0 and MIDISOFT Stu
`dio 6.0 http://WWW.midisoft.com/upgrade.htm Apr. 10,
`1999'
`
`( * ) Notice:
`
`Under 35 U.S.C. 154(b), the term of this
`t
`t h 11 b
`t d d f
`0 d
`.
`pa en S a
`6 6X en 6
`or
`ays
`(21) Appl. NO.Z 09/429,260
`
`* cited by examiner
`
`Primary Examiner—Stanley J. WitkoWski
`74 Attorne , A em, or Firm—Blakel , Sokoloff, Ta lor &
`(Zagman LLPy g
`y
`y
`
`(51) Int. Cl. ............................ .. G09B 15/04, ClOH 1/26
`
`7
`
`.
`
`
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. (58) Field of Search ................... .. 84/609—614, 634—638, R
`
`
`
`Amethod to enable one to Search for a Song title When only
`
`
`
`An user to enter the melody in an easy to understand mannen A
`
`(56)
`
`84/477 R 478; 434/307 A remote music database With melody information is searched
`_
`for the melody entered by the user. using, for example, a
`References Clted
`peak or differential matching algorithm. Upon receiving a
`US PATENT DOCUMENTS
`search request, a database server, i.e., a remote computer,
`_
`WhlCh can be accessed by the user via a client PC, sends a
`5:402:39 * 3/1995 Nakashlma ct a1~ -
`Web page, for example, in HTML or Java containing the
`Z’WOJZO
`9/1997 Gr_eW1: ct al'l """""""""""" " 84/609
`search results to the client PC. The client PC receives and
`s’ggz’gmlg *
`41” 1998 Wms .y et a‘ '
`displays the search results on the monitor and exchanges
`,
`,
`/1999 Contois ............................ .. 84/609 X
`d t
`.th th
`S
`d
`1
`b 1
`d th
`h th
`5,895,876 * 4/1999 Moriyama . . . . .
`. . . . .. 84/609
`a a W1
`6 Server' on“ may a so 6 P aye
`mug 6
`5,925,843 * 7/1999 Miller 6161. ..
`.. 84/609
`Sound Card 10 Connected Speakers
`5,969,283 * 10/1999 Looney et al.
`.. 84/609
`5,986,200 * 11/1999 Curtin .................................. .. 84/609
`
`40 Claims, 8 Drawing Sheets
`
`SEARCH WINDOW
`
`Melody Search
`
`(
`
`PLAY ’
`
`(
`
`CLEAR ’
`
`2
`(SEARCH ’
`
`3
`
`4
`
`5
`
`Search Result
`
`Traiimerei R. Schumann
`
`f6
`
`Google Ex. 1012
`
`

`
`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 1 0f 8
`
`US 6,188,010 B1
`
`FIG- 1 SEARCH WINDOW
`
`Melody Search
`
`1
`
`Search Result
`Tra'Limerei R. Schumann
`
`[6
`
`Google Ex. 1012
`
`

`
`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 2 0f 8
`
`US 6,188,010 B1
`
`Jib
`
`"5.
`
`H1 .
`
`
`
`
`
`5oz .230 .EEEEtm .m
`
`7 v
`
`1 _ l
`
`IDFU.
`
`wv
`
`E
`J L l
`
`Google Ex. 1012
`
`

`
`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 3 0f 8
`
`US 6,188,010 B1
`
`PIANO ROLL wmnow (FUR ELISE)
`
`FIG. 4
`
`PIANO ROLL WINDOW (TRAUMEREI)
`
`FIG. 5
`
`Google Ex. 1012
`
`

`
`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 4 0f 8
`
`US 6,188,010 B1
`
`TRAUMEREI IN PIANO ROLL NOTATION
`
`O PEAK Q DIP
`
`6
`
`USER INPUT (TRAUMEREI)
`
`o PEAK 0 DIP
`
`F|G_ 7
`
`Google Ex. 1012
`
`

`
`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 5 0f 8
`
`US 6,188,010 B1
`
`Fla_ 8
`
`'
`
`|
`
`2
`
`Google Ex. 1012
`
`

`
`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 6 0f 8
`
`US 6,188,010 B1
`
`TRAUMEREI IN PIANO ROLL NOTATION
`
`17(F4)
`16(E4)
`
`FIG. 11
`
`USER INPUT (TRAUMEREI)
`
`FIG. 12
`
`Google Ex. 1012
`
`

`
`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 7 of 8
`
`US 6,188,010 B1
`
`
`
`_H_..%_$:.§_>>GH
`
`
`
`
`
`_sz.:3<s2__ue_a§§\$__.aozmofiflezmexoomGsun.2S_E_EEoca.253Emgm
`
`
`
`
`
`2.83»:.23.._2.=_<..:3...
`
`
`
`
`
`
`
`new>E=8mE_._n_SmoflmzcewmmmEo_._u8_omU.=~>>._on_xomm
`
`
`
`
`
`
`
`__+__________§__§_=,_=__fl__=_§___a
`
`EEEE
`
`I-
`
`
`
`‘xx _H__H=n_
`
`
`
`
`
`:m>o£$m.>4$__m=:EammEzmmm
`
`Google Ex. ‘I012
`
`Google Ex. 1012
`
`

`
`U.S. Patent
`
`Feb. 13, 2001
`
`Sheet 8 0f 8
`
`US 6,188,010 B1
`
`3. .2"
`
`ID
`
`VEME PmF\>
`
`Google Ex. 1012
`
`

`
`US 6,188,010 B1
`
`1
`MUSIC SEARCH BY MELODY INPUT
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invention is directed to a mechanism for
`enabling the searching of songs by their melodies in sound
`?les such as midi ?les.
`2. Description of the Related Art
`In the prior art, if one knoWs a song melody, but not the
`artist or title, about the only Way to determine the title Would
`be to ask a person having knoWledge of the melody and title
`such as a person Who Works in a retail record/compact disc
`store. Existing music search capability available utiliZing the
`Internet usually requires at least a part of its title or com
`poser’s name.
`In US. Pat. No. 5.739.451. a hand held music reference
`device is described With song segments, typically stored as
`compressed MIDI ?les. as Well as titles, lyrics, artists and
`the like. HoWever, searching is generally performed by
`entering at least one of the title. lyrics, artist or the like Which
`is then searched. Reference is made to note structure com
`parator 62 and performing a melody line search utiliZing a
`note structure entered via directional keys. A note structure
`is de?ned as a series of relative note or pitch values. i.e., a
`melody line Which is rising, falling or remaining the same in
`pitch value. Comparator 62 operates to locate songs Which
`have the inputted note structure. Apparently, comparator 62
`is a microprocessor Which has been programmed to perform
`this function, the details of Which are not set forth as
`searching by note structure does not appear to be the
`preferred mechanism for performing a search. Also, the
`entering of a note structure as described in this patent
`provides a limited mechanism for enabling the comparator
`to locate a desired song since basing a search on rising,
`falling or remaining the same pitch values provides only
`limited information.
`In US. Pat. No. 5,402,339, a more sophisticated mecha
`nism is described for performing a search based on a
`melody. HoWever, to perform the search, a user must enter
`a string of note data items Which is a period and scale level
`of a single sound identi?ed by a musical note. To do this, the
`user must possess a high level of music knoWledge and
`sophistication, making the described mechanism unsuitable
`for use by the average person having a limited knoWledge of
`music. Further, period, i.e., note duration is very dif?cult to
`estimate, even for a user having a high level of music
`knoWledge.
`
`SUMMARY OF THE INVENTION
`
`A method and apparatus is disclosed to enable one to
`search for a song title When only its melody is knoWn. The
`invented music search alloWs a user to search a database and
`thereby obtain the title of the Work only With its melody as
`input to a search engine and a minimal knoWledge of music.
`The invention uses a piano roll music notation interface or
`a piano keyboard interface Which alloWs the user to enter the
`melody in an easy to understand manner. This invention
`assumes a user has access to a remote music database
`through, for eXample, the Internet using a personal computer
`(PC) Which functions as a client, With a PC keyboard,
`monitor, preferably a sound card, optionally a microphone
`and Internet or other netWork connection. Upon receiving a
`search request, the database server i.e., a remote computer,
`Which can be accessed by the user via the client PC, sends
`a Web pages for eXample, in HTML or Java containing the
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`2
`search results to the client PC. The client PC receives and
`displays the search results on the monitor and eXchanges
`data With the server. Sound may also be played through the
`sound card to connected speakers.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shoWs a piano roll grid onto Which a melody may
`be entered.
`FIG. 2 is a portion of the Work entitled Fiir Elise in
`standard music notation.
`FIG. 3 is a portion of the Work entitled Traumerei in
`standard music notation.
`FIG. 4 illustrates a piano roll WindoW for the melody (F
`iir Elise) shoWn in FIG. 2.
`FIG. 5 illustrates a piano roll WindoW for the melody (Tr
`aumerei) shoWn in FIG. 3.
`FIG. 6 illustrates Traumerei in piano roll notation.
`FIG. 7 illustrates user input for Traumerei in piano roll
`notation.
`FIG. 8 illustrates a portion of the piano roll WindoW
`shoWing the selection of a particular block representing a
`note.
`FIG. 9 illustrates a portion of the piano roll WindoW
`shoWing the selection of a particular block representing a
`note With a duration tWice as long as the note shoWn in FIG.
`8.
`FIG. 10 illustrates a portion of the piano roll WindoW
`shoWing the selection of a particular block representing a
`note tWice as long as the note shoWn in FIG. 8 With a
`folloWing note With the same pitch.
`FIG. 11 illustrates user input for Traumerei in piano roll
`notation.
`FIG. 12 illustrates user input for Traumerei in piano roll
`notation.
`FIG. 13 illustrates an alternate interface for inputting a
`melody using a representation of a piano keyboard.
`FIG. 14 illustrates a melody having a repeated pattern
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`FIG. 1 shoWs an eXample of a search interface according
`to the present invention. The interface includes piano roll
`grid 1, mouse or other pointing device cursor 2, play button
`3, clear button 4, search button 5, and search result WindoW
`6. Piano roll grid I has vertical scroll button 1a and hori
`Zontal scroll button 1b. Even if a user does not knoW
`traditional musical notation, With this piano roll input, the
`user can easily input a melody to search. This kind of music
`input interface is already used in existing music notation
`softWare. For eXample, a commercially available product
`knoWn as Midisoft Studio 6.0 utiliZes a piano roll input
`interface. See, http://WWW.midisoft.cornmupgrade.htm. In
`this case hoWever, the interface is used to create and edit
`music rather than to perform searches.
`The horiZontal aXis of the grid represents time and the
`vertical aXis of the grid indicates pitch. Each block repre
`sents a note. One block above represents a half note. If the
`current block is C, its upper block is C#.
`The user moves cursor 2 to a block to select it and then
`presses the mouse button. If the selected boX pitch is C4, a
`tone of C4 Will be generated by the soundcard of the PC and
`the user hears the tone. This tone feedback alloWs the user
`to correct the pitch easily. If the pitch is correct, the user
`
`Google Ex. 1012
`
`

`
`US 6,188,010 B1
`
`3
`releases the mouse button and that block is ?xed. If the pitch
`is Wrong, the user moves cursor 2 upward or doWnWard to
`?nd the correct pitch. To correct a ?xed block, the user
`moves the cursor onto the block and drags-and-drops it onto
`another block to correct the pitch. By dragging cursor 2 to
`the right, the user can prolong the duration of a note. For
`example, in FIG. 8, a block is chosen by moving cursor 2
`onto it. In FIG. 9, by continuing to press the mouse button,
`the user drags cursor 2 to the next rightmost block and
`releases the button. These tWo blocks, Which are solid,
`represent one note With duration 2. In FIG. 10, the third
`block is clicked. Because the mouse button has been
`released, this block, Which is hatched, is detected as a
`folloWing note With the same pitch. In this manner, the user
`inputs each note in the melody to search.
`When the user ?nishes the melody input, play button 3 is
`clicked. The Whole melody Which has been entered is
`generated by the soundcard in the PC and is heard through
`connected speakers. If the melody is correct, search button
`5 is selected to start the search. If the user Wants to delete all
`entries made in the piano roll grid, clear button 4 is clicked.
`In this search system, the duration of each note is ignored
`because it is difficult, if not impossible, for a user to input the
`correct duration. No rests (period of silence) are considered,
`either. For this reason, the user does not have to be con
`cerned about the duration of each note. HoWever, since it is
`easier for some users to enable each note to have at least an
`approximate duration to playback their input melody, if the
`user desires to input duration. such capability is provided.
`HoWever, duration information is not used to perform a
`search.
`FIG. 2 is the famous melody in “Fiir Elise” by L. V.
`Beethoven. FIG. 4 shoWs an example of piano roll notation
`for “Fiir Elise”. FIG. 3 is another example melody. “Tr
`aumerei” by R. Schumann. FIG. 5 is the piano roll notation
`for this melody. The user may input the melody in any key.
`The invented search system automatically shifts its key to ?t
`the data in the database as described in detail beloW. The
`user need only be concerned With pitch distance betWeen
`each note.
`For those Who are familiar With music notation, there are
`alternative input methods. A piano keyboard and a music
`sheet are displayed as shoWn in FIG. 13. The user chooses
`a key on keyboard 17 by pointing to the desired key With a
`cursor and clicking a mouse button. A corresponding note
`appears on the sheet 19. This kind of traditional input
`method may alternatively be employed. In this case, if a
`MIDI instrument is available. for example, a MIDI
`keyboard, it may be connected to the PC, and the user may
`enter a melody from the keyboard.
`The invented keyboard (or piano arid) interface is
`designed for on-line access. In order to generate a tone of
`each piano key, the netWork server sends the sound ?les to
`the client computer over the netWork. The client computer
`does not have to store the sound ?les. They Will be sent on
`demand in the preferred embodiment. There are several
`choices for sound ?les. One is a MIDI data ?le. The MIDI
`?le has only a pitch and duration values. So its siZe is very
`compact. It can be accessed over a netWork relatively
`quickly. A disadvantage is that the client computer must
`have a MIDI sound generator. Most UNIX computers have
`no MIDI generator. Thus, although a MIDI ?le is small,
`using MIDI limits the number of clients that can be used.
`Another solution is a Waveform ?le like a .au or .Wav ?le
`Which are Well knoWn sound ?le formats. Each Waveform
`?le is several Kbytes. 60-key data is about 250 kbytes. It is
`
`10
`
`15
`
`25
`
`45
`
`55
`
`65
`
`4
`larger than a MIDI Flle and thus takes more time to send.
`HoWever, no MIDI sound generator is required. Compared
`With a MIDI ?le, more clients can handle the Waveform ?les.
`Also, instead of a keyboard or piano grid input interface,
`a microphone can be used. The microphone receives the
`user’s voice (e.g., by humming) and converts it to an
`electronic signal. The signal is ampli?ed and analog-to
`digital converted. The digitiZed signal is analyZed in a CPU
`by a FFT (Fast Fourier Transform) algorithm according to
`Well knoWn techniques in Which FFT is used to analyZe
`sound by obtaining frequency spectrum information from
`Waveform data. The frequency of the voice is obtained and
`?nally a musical note that has the nearest pitch is selected.
`This kind of interface is already in practical use. For
`example, the folloWing Web pages describe softWare prod
`ucts With such an interface.
`http://WWW.medianavi.co.jp/product/hana/tk9907.html
`http://WWW.medianavi.co.jp/product/hana/step.html
`http://WWW.medianavi.co.jp/product/hana/step2.html
`http://WWW.medianavi.co.jp/product hana/step3.html
`Regardless of the input method employed, in the preferred
`embodiment. a user uses a broWser, such as Netscape
`Navigator available from America on Line installed on the
`client computer and performs the folloWing steps to do a
`search.
`(1) The client requests the search engine Web page (e,g.,.
`Java applet) over a netWork (e.g., the Internet).
`(2) The Web server receives the request and sends back the
`Web page data Which includes the user interface described
`above, Which is for example a Java applei and sound ?les.
`(3) T he client computer displays the Web page. The user
`enters the melody to search using any of the above
`described techniques or anv other suitable mechanism to
`enter the melody. The client computer sends the melody
`data to the Web server.
`(4) The Web server passes the melody data to a CGI
`(Common GateWay Interface) script. The CGI script is,
`for example, a Perl (Practical Extraction Report
`Language) script, an example of Which folloWs:
`
`# Melody Search Program
`if($ENV{QUERYiSTRING}) {
`$entered = $ENV{QUERYiSTRING};
`
`@searchiresult = ‘melodyisearchexe @melody’;
`print “Content-type: text/html\n\n”;
`print “<html>\n”;
`print “<head>\n”;
`print “<title>Melody Search Result</title>\n”;
`print “</head>\n”;
`print “<body>”;
`print “<H2>Melody Search Result </H2>\n”;
`print “<br>”;
`if($ENV{QUERYiSTRING}) {
`print “@searchiresult \n”;
`
`}
`
`(5) The CGI script calls the search program (the invented
`peak search program described beloW) and gives the
`melody data to it.
`(6) The search program searches the database and obtains
`the information about the entered melody.
`(7) The search program returns the search result to the CGI
`script.
`(8) The CGI script passes the result to the Web server.
`
`Google Ex. 1012
`
`

`
`US 6,188,010 B1
`
`5
`(9) The Web server returns the search result to the client. The
`client browser displays it.
`Most of the existing online search engines have a similar
`search process. The search engine as described is novel at
`least as to the following points.
`(a) The Web server provides a Java applet and sound ?les.
`So, the user can enter a melody While listening to play
`back. The user can use any Java-ready computer.
`(b) Fast Peak search. The peaks in all the melodies stored in
`the databases are marked in advance. For melody
`matching, the entered melody is time-shifted, as explained
`beloW, so that its peak matches each peak in the reference
`melody.
`The Music Melody Database
`A composer’s name and a music title are stored With its
`melody data in the database. If necessary, related
`information, for example, performers, history, background,
`can be linked to the database.
`The melody data may be stored as a MIDI ?le. When
`searched, its melody is extracted from the MIDI ?le and
`compared With the input melody. If search speed does not
`matter, this is a good solution because the user listens to the
`searched music by playing the MIDI ?le. The melody stored
`in the database could be not only the beginning of the
`melody, but also one or more famous phrases in the middle
`of the music.
`The folloWing is an example of a database structure for
`storing the foregoing information in C language notation.
`Each melody data is grouped With its composer ID and its
`title ID as folloWs. Here, up to 64 notes are stored for a
`melody. Of course, the siZe of the array used to store the
`melody may be adjusted up or doWn as desired, depending
`on the amount of storage available.
`
`struct melodyidatabase {
`int composeriID:
`int titleiID;
`int m[64]:
`
`Thus, a music database for that has 5000 classical melo
`dies Would be de?ned as folloWs:
`struct melodyidatabase DB[5000];
`Key Shift and Pattern Matching
`Composer-ID list and Title-ID list are shoWn beloW.
`DB[0] is assigned for “Traumerei”.
`3650 is stored in DB[0].composeriID. DB[0].titleiID is
`1720. The search engine ?nds that the entered melody
`matches DB[0] and obtains these tWo Ids. Then they are
`referred to the lists and the composer’s name “Schumann”
`and the title “Traumerei” are obtained.
`
`Composer-ID list
`
`Composer
`
`SCHEIN, Johann Hermann (1586-1630)
`SCHLICK, Arnolt (0. 1460-0. 1517)
`SCHOENBERG, Arnold (1874-1951)
`SCHUBERT, Franz Peter (1797-1828)
`SCHUBERT, Franz (1808-78)
`SCHUMANN, Robert Alexander (1810-56)
`SCHUTZ, Heinrich (1585-1672)
`SCRIABIN, Alexander (1872-1915)
`SERMISY, Claudin de (01490-1562)
`SGAMBATI, Giovanni (1841-1914)
`
`ID
`
`3600
`3610
`3620
`3630
`3640
`3650
`3660
`3670
`3680
`3690
`
`6
`
`-continued
`
`Title-ID list
`
`ID
`
`Title
`
`1710
`1720
`1730
`1740
`1750
`1760
`
`Toccata, Op. 7
`Traumerei (Kinderszenen Op. 15)
`Fantasia in C, Op. 17
`Arabeske, Op. 18
`Novelettes No. 6, Op. 21
`Romance No. 2, Op. 28
`
`Apitch number is assigned to each key as shoWn in Table
`1.
`
`TABLE 1
`
`Key
`
`Value Key
`
`Value Key
`
`Value Key
`
`Value
`
`C1
`C #1
`D1
`D #1
`E1
`F1
`F #1
`G1
`G #1
`A1
`A #1
`B1
`
`36
`37
`38
`39
`40
`41
`42
`43
`44
`45
`46
`47
`
`C2
`C #2
`D2
`D #2
`E2
`F2
`F #2
`G2
`G #2
`A2
`A #2
`B2
`
`48
`49
`50
`51
`52
`53
`54
`55
`56
`57
`58
`59
`
`C3
`C #3
`D3
`D #3
`E3
`F3
`F #3
`G3
`G #3
`A3
`A #3
`B3
`
`60
`61
`62
`63
`64
`65
`66
`67
`68
`69
`70
`71
`
`C4
`C #4
`D4
`D #4
`E4
`F4
`F #4
`G4
`G #4
`A4
`A #4
`B4
`
`72
`73
`74
`75
`76
`77
`78
`79
`80
`81
`82
`83
`
`Peak Search
`Traumerei starts With C3. Which has value 60. The ?rst 21
`notes are represented as A[0][0 .
`.
`. 21]={60, 65, 64, 65, 69,
`72, 77, 77, 76, 74, 72, 77, 67, 69, 70, 74, 65, 67, 69, 72, 67}.
`Note that these absolute pitch values need not be stored in
`the database. A difference betWeen tWo adjacent notes is
`stored to DB[
`(When no index is given to an array m[
`], it indicates the entire data of the array.) If the database has
`absolute pitch data, an entered melody must be key-shifted
`to each melody in the database. This is very time
`consuming. To avoid key-shift, absolute pitch data is con
`verted to relative pitch data and used for matching. Relative
`pitch data is obtained by the next formula.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`Absolute pitch data: a[i]
`
`Where 0 s i < m and m is the length of the melody.
`
`Relative pitch data: r[i] : a[i + l] — a[i] Where 0 s i < m — l.
`
`50
`
`55
`
`60
`
`65
`
`Traumerei’s relative pitch data is stored from DB[0].m[0]
`to DB[0].m[20].
`DB[0].m[0 .
`.
`. 20]={5, —1, 1, 4, 3, 5, 0, —1, —2, —2, 5, —10,
`2, 1, 4, —9, 2, 2, 3, —5}.
`In DB[0].m[21] and later, ?ll data such as 9999, is stored.
`The length of melody in the database is ?exible, Which in the
`example, is up to 64 bytes. It should be long enough to
`uniquely identify the melody.
`Peak notes are also detected and marked When the data
`base is built. Apeak note is de?ned as the note that is higher
`than or equal to each of the adjacent notes. When both of left
`and right note are equal to the note, ie when three con
`secutive notes have the same pitch, the center (second) note
`is not regarded as a peak. In FIGS. 6 and 7, a White dot
`indicates a peak note. In relative pitch notation, if the next
`value is positive or Zero and the next value is negative or
`Zero, the current value is marked as a peak. In case of a series
`
`Google Ex. 1012
`
`

`
`US 6,188,010 B1
`
`7
`of zeroes, only the ?rst Zero is marked. In the next
`representation, a peak is marked With an asterisk.
`DB[0].m[0 .
`.
`. 20]={*5, —1, 1, 4, 3, *5, *0, —1, —2, —2,
`*5, —10, 2, 1, 4, —9, 2, 2, 3, —5}.
`Similarly, the absolute pitch data of Fiir Elise is repre
`sented as
`. 16]={76, 75, 76, 75, 76, 71, 74, 72, 69, 60, 64,
`A[1][0. .
`69, 71, 64, 68, 71, 72}. DB[1].m[0 .
`.
`. 15] Will be DB[1].m
`bx;1[0...15]={—1, *1, —1, *1, —5, *3, —2, —2, —9, 4, 5, *2,
`—7, 4, 3, 1}.
`Assume that the user inputs a part of Traumerei into the
`piano roll grid as shoWn in FIG. 7. The user may enter a
`melody in any key. The ?rst note in FIG. 7 is C3, Which is
`60. (The actual pitch is F3.) Note that the user does not
`alWays enter a melody from the beginning correctly. In this
`case, the user has dropped the ?rst three notes. The pitch data
`of the entered melody is as folloWs.
`Ain[O .
`.
`. 10]={60, 64, 67, 72, 72, 71, 69, 67, 72, 62, 64}.
`The relative pitch data of Ain[ ] Will be
`
`15
`
`Next, Rin[ ] is time-shifted for matching. Rin[ ] Will be
`compared to DB[0].m[ Since the ?rst peak in Rin[ ] is
`Rin[2].,Rin[ ] is time-shifted (i.e, moving the array to the left
`or right, as appropriate) so that Rin[2] locates in the position
`of DB[0].m[0].
`
`25
`
`Each value beloW the line is an absolute difference of the
`tWo associated values. The values in un-overlapped area are
`neglected. The total absolute difference is
`
`When the tWo melodies completely match, the total absolute
`difference Will be Zero. The goal is to ?nd a reference
`melody that gives the least total absolute difference. Again,
`Rin[ ] is time-shifted (in this case, moved to the right) so that
`Rin[2] and DB[0].m[5] match.
`
`This time, the total absolute difference is Zero. The tWo
`melodies completely match. DB[O] is the melody the user is
`looking for. DB[0].composeriID and DB[0].titleiID are
`returned as a search result. The result is indicated in search
`result WindoW 6 in FIG. 1. In this manner, the entered
`melody is shifted to each peak in each reference melody and
`compared. The reference melody that gives the least differ
`ence is returned as a search result.
`To accelerate the search, computation of the total absolute
`difference can be stopped When it exceeds a certain limit.
`Linked Features
`If this database is linked to a music database that has
`complete music score data, searched music may be played
`automatically. For example, DB[0].titleiID may be linked
`to the MIDI ?le of Traumerei . The server sends the MIDI
`?le to the client PC and the client PC play it. Moreover, the
`result can be linked to the list Compact Disc on on-line CD
`shop. For example, all the CDs that includes Traumerei are
`shoWn on the display. By clicking one of them, it is sent to
`the shopping cart of on-line purchaser.
`
`35
`
`45
`
`55
`
`65
`
`8
`
`Variations
`Instead of a peak, a dip can be used. Adip note is indicated
`With a black dot in FIGS. 6 and 7.
`Also both peaks and dips may be used together. The
`number of peaks and dips in each reference melody are
`detected beforehand and a ?ag indicates Which are feWer in
`number. Before matching, this ?ag is detected and it is
`decided Which is to be used, peaks or dips. If dips are feWer
`than peaks, the entered melody is shifted so that the dip in
`the entered melody locates in the position of the dip in the
`reference melody. This method Will save computation time
`because search time greatly depends on the number of
`matching peaks or dips required to be made.
`Moreover, in order to further accelerate the search, the
`order of comparison may be considered for search speed
`improvement. It is most probable that the highest peak in the
`entered melody matches the highest one in the reference
`melody. Therefore, the highest peak is ?rst compared With
`the highest one in the reference melody and next compared
`With the second highest peak. For example, in Traumerei,
`there are four peaks, DB[0].m[0], DB[0].m[5], DB[0].m[6],
`and DB[0].m[10]. Their absolute pitch value are A[0][1],
`A[0][6], A[0][7],A[0][11]. They are respectively, 65, 77, 77,
`and 77. The highest peak in Traumerei is DB[0].m[5],
`DB[0].m[6], and DB[0].m[10]. DB[0].m[0] is the second
`highest. The height order is stored in the database before
`hand. The highest peak in the entered melody Rin[ ] is
`Rin[2], Rin[3], and Rin[7] are the highest and they are 72.
`For matching, the entered melody is shifted so that the
`Rin[2] locates in the same position of the highest peak
`DB[0].m[5], DB[0].m[6] and DB[0].m[10] respectively.
`After this match, the entered melody is shifted to the second
`highest peak DB[0].m[0].
`Instead of using a peak , a differential betWeen notes may
`also be used. The largest step-up in the input melody is
`detected. In relative pitch data DB[
`], the largest value
`indicates the largest step-up. In case of Traumerei,
`DB[0].m[15] is the largest step-up, Which is marked With a
`pound. The second largest step-up is marked With a double
`pound. In this Way, each step-up in the database is numbered
`in large step-up order.
`DB[0].m[0 .
`.
`. 20]={##5, —1, 1, 4, 3, ##5, 0, —1, —2, —2,
`##5, —10, 2, 1, 4, #9, 2, 2, 3, 5}
`Each step-up in the entered melody is also marked in the
`same Way When it is entered.
`Rin[O .
`.
`. 11]={4, 3, #5, 0, —1, —2, —2, #5, —10, 2}.
`The entered melody is shifted so that the largest entered
`step-up locates at the largest step-up in the reference melody.
`The absolute difference betWeen the tWo melodies are com
`puted as described above. If the largest step-up is done, the
`entered melody is shifted to the second largest step-up
`(marked With a double-pound) in the reference melody. In
`this Way, the entered melody is shifted to each step-up and
`compared. FIGS. 11 and 12 illustrate this step-up search.
`These ?gures have the same pattern as FIGS. 6 and 7
`respectively. Solid arroWs indicate the largest step-up in
`FIG. 12. It is ?ve steps. Instead of step-up, step-doWn data
`can be used. In FIGS. 11 and 12, a dotted arroW indicates the
`largest step-doWn.
`Instead of relative pitch data, the original absolute pitch
`data can be stored in the database and used for matching.
`The input melody is key-shifted so that the peaks in the input
`melody have the same pitch as each peak in the reference
`melody. This is done by comparing peaks in the input
`melody and reference melody, and then subtracting the
`difference from each subsequent note until the next peak,
`and then repeating for the second and each subsaequent
`
`Google Ex. 1012
`
`

`
`US 6,188,010 B1
`
`10
`Instead of the using these techniques to perform a string
`search, these search algorithms may be applied to
`perform melody searches.
`Further Search With A Wildcard
`When a regular search does not result in a good match,
`further searches using Wildcards can be performed. In a
`string search, a Wildcard like “?” is used instead of an
`uncertain character. The character “?” matches any charac
`ter. For example, if it desired to ?nd a three-letter Word
`Which starts With “a” and ends With “d”, the search keyWord
`entered Would be “a?d”. As a search result, “add”, “aid”,
`“and”, etc. Would be returned. Such a Wildcard can be
`introduced to music search according to the present inven
`tion. A problem is that the user may not knoW What note of
`the entered melody is Wrong. So, it is desirable that a search
`engine automatically searches With the modi?ed input
`melody. The invented search engine also has such input fault
`tolerance capability.
`First, in the case When string-search algorithm is used,
`assume that the user entered n notes as folloWs.
`
`. a[n])
`.
`(a[1], a[2], a[3] .
`The index of the array starts With 1 for simplicity. (Note
`that actual search uses not a[ ], but a relative difference
`betWeen tWo adjacent notes.)
`(1) Correction of a Wrong Pitch
`The search engine assumes one of the n notes has a Wrong
`pitch. The search engine replaces one of them With a
`Wildcard and tries a search. There are n variations. The
`database is searched n times. The modi?ed input melody is
`represented as follows.
`
`(‘2, a[2], a[3], .
`(a[1], ?, a[3], .
`
`.
`.
`
`. a[n])
`. a[n])
`
`peak. Adisadvantage of absolute pitch data is that a key-shift
`is required for every matching. An advantage is original
`absolute pitch data can be stored Without modi?cation. Also
`a MIDI ?le, Which includes pitch, duration, and other data,
`can be used although it takes time to analyZe MIDI format.
`Advantages of Peak Search
`(1) Search Speed
`Peak notes are approximately 20% of the total number of
`notes in a typical melody. That means search speed using
`peak notes is 20% of a brute force search Which shifts the
`entered melody, note by note. Also because relative pitch
`data is used, no key-shift is required to compare With each
`reference melody.
`(2) No Restriction on Incomplete Input
`The entered melody is shifted based on a peak note in the
`melody. Therefore, the user can start a melody With any note.
`In the above example, an exact result Was obtained even
`though the ?rst three notes of the melody Were dropped . The
`only restriction is that an entered melody must include at
`least one peak.
`(3) Input Fault Tolerance
`The user does not alWays enter the melody Without
`mistakes. Some notes could be dropped or given a Wrong
`pitch. So a search engine should have some input fault
`tolerance. If a peak note is correctly entered, this search
`engine Will ?nd the closest melody from the database. Even
`if a peak has a Wrong pitch, another peak can be used for the
`search. In the above example, assume Rin[2] has the Wrong
`pitch. In this case, no exact result is obtained. So, another
`search Will be done With the second peak Rin[7]. When
`Rin[7] is shifted to DB[0].m[10], the total absolute differ
`ence Will be a minimum and the correct result Will be
`obtained. (As described above, a dip can be used instead of
`a Wrong peak.) For these reasons, a correct search can be
`obtained notWithstanding inaccurate input from the user.
`(4) Flexibility on Search Area
`Some melodies have a repeated pattern as shoWn in FIG.
`14. In this melody, the second measure is identical to the ?rst
`one. TWo peaks are in the melody, but the secon