Slashdot Mirror
Palm/3Com Graffiti A Patent Infringement on Xerox
Olmy's Jart writes "According to this article on money.cnn.com, a judge has ruled that graffiti, the one stroke shorthand used on Palm Pilots, infringes a Xerox patent for "unistrokes". Really light on details and no links to betters sites, unfortunately." MSNBC also has the story.
Bic has just sued Paper Mate over "the pen."
How does this affect handspring? Is Xerox's claim towards the implementation in the OS or the general input method?
-Windchill2001 The One, The Only, The Cold...
for Palm or it's licensees, Handspring, Sony, and HandEra (and perhaps others). Xerox wants damages for infringement, plus they intend to force Palm to cease selling PDA's or to license the patent. If Palm can't afford it... all PalmOS based devices may be in trouble.
Anyone know if BeOS had any non-infringing handwriting recognition? This might force Palm to move ahead with a switch to ARM and a new OS.
Man, Palm is really having a hard time these days. Could this, coupled with their recent downturn help microsoft innovate them out of business a la netscape?
Sure, Palm was the original, and the only one (along with OS licencees) that offers PDAs that aren't overloaded with pricey color screens, 64mb of memory, and desktop applications. (Well they offer those too, but they still have some good straightforward PDAs). But, with the market crowding, and lots of new Wince apps being written, are we seeing the beginning of the end?
I'd hate to have to buy an overloaded PDA because MS becomes the only game in town...
Buy Hex-Rated Stuff, fight the DMCA!
Relevent patent is 5596656
It looks pretty broad and clear
Mmmmmmm
Intellectual Property is being slowly strangled by overrestrective trademarks, copyrights, patents, corrupt companies, and bought politicians.
When are we going to wake up and realize that these artificial constructs originally created to help innovation is actually starting to stifle it? Perhaps people will start to wake up after the recession really starts to hurt. There is going to be a lot of pointing fingers soon.
I wonder when Xerox filed that patent, as Palm (or whatever they were called originally - before 3Com bought them) was selling the software to use graffiti as input on the Apple Newton back in 1994 or so? I think we still have one of the original packages at work.
-"Zow"
The lawsuit will now move on the the penalty phase. The court will decide if Palm has to pay damages and if it is allowed to continue to use the technology. Xerox will urge the court to either require Palm to stop using Graffiti entirely or pay royalties.
Xerox sued U.S. Robotics, which was later bought by 3Com, back in 1997, claiming that Graffiti infringed a patent Xerox received in 1997. Palm was later spun off from 3Com.
Xerox originally filed for its patent in October of 1993. The first handhelds running the Palm OS, the Pilot 1000 and Pilot 5000, were released in April of 1996 by U.S. Robotics. These included Graffiti. A question not yet answered is why Jeff Hawkins didn't file for a patent on Graffiti earlier when he had been developing the idea since the 80s.
In June of last year, a judge dismissed the suit on the grounds that Graffiti wasn't similar enough to Unistrokes. In October, the suit was reinstated and moved to the U.S. District Court for the Western District of New York.
Judge Michael Telesca declared today that Xerox's patent is "valid and enforceable", and that Graffiti does infringe on it.
It is not yet known whether Xerox plans to sue other makers of handheld operating systems, like Microsoft, who also include some form of handwriting recognition.
"Xerox always aggressively defends its patent portfolio -- a valuable corporate asset. Today's ruling vindicates our position that our handwriting-recognition patent was infringed. Either Palm will have to cease production of its hand-held organizer or license the technology from Xerox," said Christina Clayton, Xerox general counsel.
Thanks to montyburns for the tip. -Ed"
Blatanly ripped from Palminfocenter.com
Unistrokes picture - Unistroke.gif
---- "It is never too late to give up our prejudices." --Henry David Thoreau(1817-1862)
When I was in Law School, we were presented with an age-old issue similar to this. Way back when, a printing company accused another of stealing their "shorthand" language that they used in technical manuals. (Basically it was a simple method of printing manuals for machines. If you were a worker who repaired these machines, you would be familiar with the shorthand).
;)
Anyways, the company that originated the shorthand sued another because they began printing manuals with a similar technology. The judge decided (I believe he was right) that it did constitute an infringement and the defendant company was required to pay royalities.
Sure is neat to see how things can change, but the same lawsuits pop up again
- Dave Brennins
http://www.davebrenninslaw.org
dave@davebrenninslaw.org
For anyone interested, here is a paper (in Postscript format, on the parc FTP server) from 1993 by David Goldberg and Cate Richardson of PARC discussing unistrokes. It looks like the foundation for the strokes is there. I wonder how Palm's version measures up to their tests.
In Palm's patent on "Method and apparatus for handwriting input on a pen based palmtop computing device" check out a couple of the references that are cited:
Article: "touch-Typing with a Stylus", by David Goldberg and Cate Richardson, (9) pages total/
Xerox patents relating to handwriting recognition, (5) pages total.
Goldberg is the inventor listed on Xerox's patent. I'm sure someone at Palm (perhaps Hawkins and Haitani) saw this one coming a mile away.
I learned Morse code in 1978 from a fine old geezer in Sweden, who amongst other things taught me to write all characters as a single stroke: backwards 3 for "E", a sort of a triangle for "A", and so on - just like graffiti. It was all just to make copying Morse code easier, but it seemed such an easy way to write that I took to it in everyday life.
Now, I'm not saying that the Xerox or Palm dudes ripped off this idea from Ham Radio geeks. All I mean is that if you're pressed into having to print the standard Latin letters quickly, you are naturally going to end up with something that looks awfully much like the Ham/Morse chicken scratch, or Graffiti, or whatever you want to call it.
I sense a prior art here: ln -s anyone?
Meanwhile, Bill Gates of Microsoft had this to say on the subject. "Ehhx-cellent..."
A feeling of having made the same mistake before: Deja Foobar
Specifying gestures by example, Dean Rubine, ACM SIGGRAPH Computer Graphics , Proceedings of the 18th international conference on Computer graphics July 1991, Volume 25 Issue 4
It is a part of the Andrew Toolkit, historical source is at here.
It is a part of OpenAmulet now.
Perhaps a mouse is NOT a stylus.
How MSNBC has a big story on how one of MS's cheif comeptitors lost a lawsuit whiel everyoen else is running the story that XP lets pirates take over your entoire computer?
Not.
MSNBC == MS PR + NBC's journalistic integrity bought and paid for.
Xerox sued palm and won. Xerox did not sue MS. Why is this legal? At this point MS is most likely infringing on a Xerox Patent but Palm is the only organization being punished for it.
Man out justice system is fucked up. If I ran the world Xerox would have to sue everybody who infringed or nobody. It's unfair to let some people off the hook.
War is necrophilia.
...I'm not going to say that unistrokes weren't innovative either.
Well, I will. The problem is that people confuse the word "new" with the word "innovation". I don't think something should get a patent just because it solves a problem which didn't exist before. PDAs weren't possible for a lot of hardware reasons until recently. The input method, while clever, is something that any intelligent person could develop if asked to solve the problem. Put ten engineers in isolation chambers and give them two weeks to try to find efficient ways to input data into a handheld computer and 7 of them will come up with something similar to xerox's patent. Ask ten engineers to triple battery life and they wont do it in years. If one of them does, they'll deserve the patent they get. That's innovation. This isn't.
When in doubt, have a man come through a door with a gun in his hand.
If people are interested I reccomend reading some of the other Microsoft patents. You'd be surprised what they claim in some of them. Others are so specific ("bit-3 of MS-DOS FAT field XYZ in the root directory of the C drive" sort of thing) they appear solely to exist to get their patent numbers up. (Did someone implement patent quotas at MS in the 90s?) In fact a full review of MS patents could keep /. going for quite
some time. It'd really get the blood pressure up too :)
One alternative is Ken Perlin's QuikWriting, which has been discussed on slashdot and covered by Wired.
"Quikwriting is significantly faster and less stressful to use than Graffiti, and lets you write very quickly without ever picking your stylus up off the surface, although it has the disadvantage that you need to learn a special alphabet. For further info, you can preview a Technote in either PDF or PostScript, which was published at the ACM UIST'98 conference."
Another alternative that builds on Perlin's QuikWriting work, is Francois Guimbretiere's and Terry Winograd's FlowMenus, published at UIST'00.
"We present a new kind of marking menu that was developed for use with a pen device on display surfaces such as large, high resolution, wall-mounted displays. It integrates capabilities of previously separate mechanisms such as marking menus and Quikwriting, and facilitates the entry of multiple commands. While using this menu, the pen never has to leave the active surface so that consecutive menu selections, data entry (text and parameters) and direct manipulation tasks can be integrated fluidly."
I'm currently designing and programming a user interface on the Palm for a remote control application. So I've implemented "Finger Pies", which are simply pie menus that you can use with your finger!
To paraphrase Ben Shneiderman: Finger Pies work well for implementing direct manipulation user interfaces on handheld personal touch screen devices, in which the application provides meaningful, engaging, tightly coupled feedback on the screen, in response to your gesture. By integrating immediate gratification over time, the user enjoys the satisfaction of direct engagement in an immersive experience, and achieves the cognitive resonance of continuous gratification. [My apologies to Ben for the tongue in cheek impression.]
Finger Pies are not meant to replace character input systems like Graffiti, but they are extremely useful and reliable for many applications of handheld input devices, because they're easy enough to use with your finger instead of a pen.
Finger pies are good for reliably selecting between two, four or eight options at a time (which can be nested as pop up submenus), and they're much more robust and resistant to noise than gesture recognition.
One problem with gesture recognition in general, is that it doesn't allow for "reselection" or in-flight refinement and error correction. That is, once you've made a mistake in a gesture, there's no way to change or cancel it, so you will often get characters that you don't mean, and you have to stop what you're doing and erase the mistake.
Pie menus allow you to cancel or change the selection at any time before you commit to the selection, so you can easily browse the menus. So pie menus are most appropriate when there aren't too many items, the items don't change dynamically over time, and when you need to minimize the error rate and selection time.
Most gesture recognition systems are not "self revealing" like pie menus, which can pop up a "map" showing the directions. So pie menus are much easier to learn than gesture recognition, and more appropriate for novice users. Best of all, they naturally train users to "mouse ahead" and select without looking, so they have a smooth, gentle learning curve.
Another advantage of pie menus is that they're not patented or restricted, and there are several freely available open source implementations.
-Don
Penny Lane: "This song was written about the roundabout in liverpool where John and Paul grew up. Half of the song is fact, half is fiction, but most of it is nostalgia. John was starting to write about personal places, and Paul really took this one and ran. "I wrote that the barber had photographs of every head he'd had the pleasure of knowing. Actually, he just had photos of different hair styles. But all the people do stop and say hello." say Paul. Also, "finger pie" is actually an old obscenity in Liverpool. The girls would never thnk of saying the word. It was used in the song as a fun joke for the lads back home. Months after, waitresses in Liverpool had to put up with lads asking for "fish and finger pie." There is also a phallic reference to the "fireman who keeps his fire engine clean." Penny Lane has become a Beatles landmark, and like Blue Jay Way, has it's problems with stolen signs, which are now nicely bolted down. Penny Lane was recorded on December 29, 1966 and released as a single with Strawberry Fields.The song also has a promotional video." -http://members.aol.com/Sumacca/songs.html
Take a look and feel free: http://www.PieMenu.com
> Sure, Palm was the original, and the only one ...
Nope. The TRUE original and only one was the Newton (I had a 120 and a 130 back then). Ok, they were quite bulky, especially compared with a Palm, and somewhat slow (at least the 1xx ones, never got to use a 2xxx), but they were great machines and they were the first and original PDAs. I considered Palms as cheap and ugly rip-offs of the Newton back then. Finally I was forced to switch by Apple abandoning the Newton and am now owning two Palms. It would be a shame to have to move on again because of Palm going down, but honestly Palm and PalmOS hasn't improved much over the last 12-18 months. They are hopelessly behind and if they don't get their act together soon, they will vanish. This would be a sad day.
From: Don Hopkins <hopkins@uk.ac.turing>
Date: Sun, 19 Apr 92 22:33:08 BST
To: Mark Weiser <weiser.PARC@com.xerox>
Cc: hopkins@uk.ac.turing
Subject: cmu
Thanks! I sent email to Myers and phoned him up, and after a while he remembered that I was the guy who sent him the pie menu video tapes [...] I'm quite interested in his work, which involves programming by example and demonstration, visual languages, and constructing GUIs with graphical editors using inferencing and constraints, instead of doing so much boiler plate programming.
I am quite interested in pen based stuff, but I don't want to work for any of the companies currently making pen based products because they are so short sighted and limited by perceived market demands and low end technology. (IBM-PC based technology, MS-DOS, bad languages, etc.) Go is using C with crude object oriented scaffolding, but their ideas are sound, and they're at least using their own OS, however the programming environment sucks, they just can't get away from MS-DOS. Momemta is using smalltalk, which, as one of their engineers told me, allowed them to catch up with Go in a very short time. But they definitly have a set of problems of their own, like running on top of MS-DOS and Windows. It's nice that they use smalltalk, but it's rather slow, and more glitzy than well designed. There was a big battle at Momemta between the programmer who's responsible for how nice it is, and the engineering manager in charge or the project, where the manager refused to use smalltalk because it was a "homosexual programming language". Guess he never heard of Lisp! But the programmer certainly proved his point, and the manager took all the credit for making the decision to go with smalltalk. (That's what the manager claimed at their product announcement, and I shook his hand for using smalltalk, and when I told the programmer about that later, boy was he pissed!) But you still can't program the damn thing in smalltalk, *using the pen*! I guess that's one reason they also have a keyboard. There were some other stupid user interface decisions made as well -- my impression from talking to the programmer was that the manager read some books on user interface design principles, and enforced them to the letter without really understanding them and knowing when they should not apply, and when to just use common sense instead.
So far nobody I've heard of has a programming language you can use with a pen, let alone a pen based user interface *written* in and around such a language. What good is a pen computer with a scripting language if you have to use a keyboard to program it? And if it's not programmable, you might as well be using recipe cards. The pen has so much potential, but everybody's trying to use these computers to simulate a piece of paper running MS-DOS. I think it's all well and fine to take advantage of metaphores people are used to (i.e. writing on paper, or beating their head against MS-DOS) but if you limit yourself to simulating paper then you've severly crippled the system, especially when at the same time you severly break the metaphore you're limiting yourself with by trying to be MS-DOS compatible. No piece of paper ever locked up and asked me if I wanted to Abort, Retry, or Ignore. As an example of how you could make a pen computer easier to use by transcending the paper metaphore: when you write on a piece of paper, the information that it stores is two-dimensional. The time componant is completely collapsed and lost. This is not the case with a pen computer, which can remember ink as a three dimensional entity. Why should I be required to write in a fucking comb, if the computer can tell where one letter ends and the next letter begins by the *temporal* separation between letters instead of the visually obvious and traditional spatial separation? Why hasn't anybody written a handwriting recognizer that lets me keep my hand in one place and just write overlapping letters or words without moving my hand back and forth, looking at the page to see when I reach the right margin, moving my hand back to the left margin and no further and down exactly one line, and then writing another line making sure it's parallel with the first? Why can't I just relax, and keep my hand in one place while writing? (I discovered this handwriting technique when I would fall asleep in class while still taking notes. I would wake up and there would be a big ink blob where I kept writing but stopped moving my hand back and forth.) Of course my hand is used to spacing letters out when writing a word, but I think it would be pretty natural to have an input field in a convenient location that I write a word into, which is recognized, then zaps over to where the text input caret is in my document, in a nice font, and the caret moves on, but the place I'm writing stays in the same place. Just like how a keyboard works. Imagine of you had to move the keyboard to the right a bit every time you typed a character, and then move it down and all the way to to the left whenever the cursor reached the right edge of the screen? Nobody would put up with that. Why put up with such a horrible interface using a pen computer? It's only *paper* that forces you to do that.
Well I doubt it would be possible to develop such a non-conformist interface for a company that was rushing to market as fast as they could. Let alone develop a pen based programming language and then write a user interface around it. Did you read the article in Dr. Dobbs Journal (the December UI issue, the same one with my pie menu article) about the pen extension to X-Windows? What an total abortion! I'm sure the next big market demand made on a company like Go or Momenta will be to implement X-Windows for their machine. During the time that every company with a pen computer is trying to do that very same thing and failing miserably, but thinking it's OK because everybody else is failing just as bad, and the users asked for it anyway, so that's what they get, I would like to be doing something completely different, not wasting my time with the latest fads, stampeeds, and lemming dunks.
-Don
Take a look and feel free: http://www.PieMenu.com
Take a look at this patent. It seems like Palm has been trying to patent any kind of handheld that uses a separate, dedicated input area for handwriting or tapping on a preprinted keyboard. Here is another one that claims methods involving separate input areas for different character types.
If you'd stop the knee-jerk "patents are BAD" reaction and think about the facts before spouting off, you'd realize that this case has been going on since long before the previous ecconomic boom! This isn't about the Tech Slump. Yea, sure -- Xerox is tight for cash, and would love to generate a few $$ off every sale of Palm, Handspring or other devices, but they aren't trying to stiffle competition or put Palm out of business.
Xerox gave us plenty of innovations (e.g., the mouse). This is just one invention they are trying to get credit for.
Your Servant, B. Baggins
Someone should sue Xerox for patenting prior art known as "short-hand."
The biggest trick the devil pulled was letting lawyers become politicians so they can write the laws.
Considering Xerox made a lot of money on machines designed to copy things...
I thought Xerox liked copying...
Recognizing arbitrary handwriting is difficult. So to make the task easier, Graffiti uses a less ambiguous alphabet.
How is that patentable? Computer science's *usual* approach to difficult problems is to make them less general, and this seems like a completely obvious way to do it. Ok, maybe I can understand a patent on a particularly innovative *method* for recognizing Graffiti characters (for instance, some new way of feeding the data into a neural network). But this appears to be a patent on any recognition system that uses a unistroke alphabet even remotely like Xerox's.
Out of morbid curiosity, I developed my own Graffiti-like input system a while back. It used a completely different mathematical trick than any other recognizer I know of (email me if you're interested, I'd be happy to share), and it could be trained to recognize almost any unistroke alphabet. I wonder if it would be covered by this patent, even though it's not limited strictly to the Graffiti alphabet and it uses a completely different algorithm.
As an interesting data point, I showed my system to an AI guy at Georgia Tech, and he was not impressed at my system's capabilities. He said I was sidestepping the problem by requiring unistroke characters.
That said, I am not surprised that Xerox got a patent on this, nor that it was held to be enforceable. I just think it is absurd.
-John