The algorithm that transformed bar code scanning
- Beep. Coffee. Beep. Eggs. Beep. Bread. Silence. Bread. Silence. Bread. Silence. The cashier types in the product’s identification number.
Not long ago, roughly one in ten items at the grocery store checkout needed to be typed in manually because they didn’t scan properly. Today, thanks to an algorithm created by Theo Pavlidis, Distinguished Professor of Computer Science at Stony Brook University, and former graduate student Eugene Joseph, that number has dropped to about one in one hundred.
Hailed as one of the most important inventions of our time, bar code scanning was first used in supermarkets in the 1970s. The technology’s combinations of black lines and white spaces encode information for millions of products, from bubble gum to car tires. This data helps companies to track their inventory, providing them with important information about how, to whom, and for what price their products are sold.
Unfortunately, the frequent failure of bar codes to scan properly made the technology cumbersome. Pavlidis had been receiving funding from the National Science Foundation for many years to investigate the fundamentals of machine vision (enabling computers to “see” the world). One result of this research was that blurred images could be interpreted by computers without having to be de-blurred first. In the early 1990s, he realized that this result could be applied to the reading of bar codes. He enlisted the help of Joseph, and the pair got to work to solve the problem, which was the result of the blurring of the black-and-white bars into a single gray mass during the scanning process.
“This graying effect is a common occurrence in the simple, rugged, and fast cameras used in barcode reading equipment,” said Joseph, now an engineering fellow at Zebra Technologies. “Back in the 1990s, the common belief was that you could only reliably read a barcode if you could see every single bar in the code. My thesis work showed that even when some of the smallest bars disappeared or ‘grayed out’ the barcode could still be read. This opinion is now accepted as fact today.”
Pavlidis and Joseph created an algorithm based on Joseph’s finding that estimated directly from the gray scale image what the black-and-white image would have been. Similar algorithms are currently in use by bar code scanners around the world to solve the problem of blurring.
“It has helped the user to be more efficient,” said Pavlidis. “That is our biggest contribution to bar code scanning”
Joseph noted that since his work was part of his Ph.D. thesis, the technology was placed in the public domain so that no one company could claim exclusive rights to the technology.
With help from another former graduate student, Ynjiun Paul Wang, who is now a chief scientist and the vice president of new healthcare delivery solutions at Welch Allyn, Pavlidis also invented a robust 2-D bar coding method, called PDF4I7, that carries much more information than previously used methods. Today, PDF4I7 is widely used; for example, it is the technology employed by many states, including New York State, in their driver’s licenses and vehicle registration cards.
Pavlidis said he always enjoyed the fast-pace and high-impact of his work with industry. “I like to see things happening in the real world,” he said. “And I always encouraged my students to see the value in that, and to consider working with industry themselves.”
Many of his students did just that. Wang and Joseph both went to work for Symbol Technologies before moving on to other companies. Pavlidis himself retired from Stony Brook in 2001 and joined Symbol Technologies as a chief computer scientist, where he worked for a short time before leaving research altogether.
Perhaps speaking for many of Pavlidis’s students, Joseph said, “I have considered Theo as a cherished mentor in this high-technology industry. I have learned a lot from him, and I am grateful.”
comments powered by Disqus