Computerized Vision Systems

English
Prof. Shimon Ullman
 
Prof. Shimon Ullman designed ways to enable computerized vision systems to recognize objects.
 

Application

 
Research conducted by Ullman and colleagues led to the establishment of a company that eventually evolved into Orbotech. Located in Yavne near Rehovot, Orbotech today is the world’s largest producer of equipment for the automated inspection of printed circuit boards.
 
Prof. Shimon Ullman
Math & Computer Science
English
  • Artificial vision
  • Computer Science and Applied Mathematics
  • Shimon Ullman

Technologies for Computer Networks

English
Prof. Ehud Shapiro
 
Prof. Ehud Shapiro developed technologies and structural laws for computer networks.
 

Application

 
“Virtual Places” software was developed by Ubique Ltd., established to implement programming technologies that grew out of Shapiro’s research. Ubique was a pioneer in the development of virtual “malls” and “meeting places” on the Internet. It was later sold to America Online and today is part of IBM.
 
Prof. Ehud Shapiro
Math & Computer Science
English
  • Computer Science and Applied Mathematics›Computer Science and Applied Mathematics
  • Ehud Shapiro

Are There Limits to Computing?

English
This diagram is part of a proof that a certain class of algorithms cannot compute the determinant of a matrix in polynomial time. From the research of Prof. Ran Raz
 
 

What is the meaning of the Universe? A thousand years from now, our computers still will not be answering such questions. Other types of questions are theoretically answerable, but they may require an impossible amount of resources in practice. Where, then, is the dividing line between the possible and the impossible in computation?


To find out, researchers from around the globe, including scientists in the Weizmann Institute’s Faculty of Mathematics and Computer Science, try to figure out the resources needed to solve particular problems. A problem is considered solvable, for instance, if the amount of processing it requires is linear (or even squared) in relation to the length of the input. But when the computation process grows exponentially in proportion to the data, it soon becomes unsolvable in practical terms.

According to Prof. Ran Raz, one way to begin the search for the dividing line is based on the consideration of “weakened” or “simplified” models for solving various problems. These might give researchers tools to advance, step by step, toward an understanding of more general models for solving problems.

Prof. Irit Dinur tests questions that cannot, as yet, be answered. If any solutions were to be found, however, her research would help us decide whether they are correct. (When we verify a solution – even one that is not ours – we verify that the problem can be solved.) She develops algorithms that represent the solution in such a way that its veracity can be tested through checking a small number of its elements. Thus each piece of the new representation contains information on the correctness of the entire solution.

 
Profs. Irit Dinur and Ran Raz
 

 

 

Prof. Ran Raz is Director of the Moross Research School of Mathematics and Computer Science.

 
 
This diagram is part of a proof that a certain class of algorithms cannot compute the determinant of a matrix in polynomial time. From the research of Prof. Ran Raz
Math & Computer Science
English
  • Algorithm
  • Annual Report 2010
  • Complexity›Complexity
  • Irit Dinur
  • Ran Raz

Designer Nerves

English
 
Dr. Assaf Rotem and Prof. Elisha Moses. Home-grown nerve networks
 

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
In think tanks around the world, analysts try to identify new developments in science and technology that might spur the next big technology wave. These trend spotters will undoubtedly be interested in new research conducted by Prof. Elisha Moses of the Physics of Complex Systems Department and his former research students Drs. Ofer Feinerman and Assaf Rotem. This team has taken the first step in creating circuits and logic gates made of live nerves grown in the lab. The research, which recently appeared in Nature Physics, could have implications for the future creation of biological interfaces between human brains and artificial systems.

Neurons are complex cells, and the networks they form are even more complex: In the brain, large numbers of connections to other neurons are what enable us to think. But when the same cells are grown in lab cultures, they turn out to be quite sluggish, reverting to a very primitive level of functioning. Why does this happen, and how can cells grown in culture be coaxed into becoming more "brainy"?

Moses, Feinerman and Rotem investigated the idea that the design of the nerve network's physical structure might be the key to improving its function. Being physicists – scientists who are used to working with simplified systems – they created a model nerve network in a single dimension, one defined by a straight groove etched on a glass plate. The neurons were "allowed" to develop only along this line. When grown this way, the researchers found the nerve cells could, for the first time ever, be stimulated with a magnetic field. (Beforehand, neurons in culture had been successfully stimulated only with electricity.)

The scientists then investigated the lines further to see if the width of the neuron stripe had any effect on the signals transmitted from cell to cell. Growing the neuronal networks on lines of varying widths, they discovered a threshold thickness – one that allowed for the development of about 100 axons (nerve cell extensions). Below this number, the chances of a neuron passing on a signal it received were iffy. This is because the cells are "programmed" to receive a minimum number of incoming signals before they fire off another one in response. A large number of axonal connections to other nerve cells – say, several hundred – will more or less ensure a reliable response, whereas cells that are connected to just a few others will fire only sporadically. With about 100 neuron connections, signals are sometimes passed on and sometimes not, but adding just a few more raises the odds of a response quite a bit.   

Putting these findings to work, the scientists used two thin stripes of around 100 axons each to create a logic gate similar to one in an electronic computer. Both of these "wires" were connected to a small number of nerve cells. When the cell received a signal along just one of the "wires," the outcome was uncertain; but a signal sent along both "wires" simultaneously was assured of a response. This type of structure is known as an AND gate.

The next structure the team created was yet more complex: Triangles fashioned from the neuron stripes were lined up in a row, point to rib, in a way that forced the axons to develop and send signals in one direction only. Several of these segmented shapes were then linked to one another in a loop to create a closed circuit. The regular relay of nerve signals around the circuit turned it into a sort of biological clock or pacemaker.
 
 
Circuits from nerve cells in the lab
 
Moses: "By creating simple computation tools from neurons with unreliable connections, we learn about the problems the brain must overcome when designing its own complicated 'thought machinery'. Simple animals rely on single nerves to direct their behavior, so these must be very reliable; but our nervous system is built of huge networks of nerve cells that enable a wide range of responses. The extreme sophistication of our neurons carries with it a high risk of error, and a large number of cells is needed to reduce the likelihood of mistakes. Right now we're asking: 'What do nerve cells grown in culture require to be able to carry out complex calculations?' As we find answers, we get closer to understanding the conditions needed for creating a synthetic, many-neuron 'thinking' apparatus."
 
Rotem: "Neuron-based circuits are still much slower than the electronic circuits existing today. But they might offer the promise of performing calculations in parallel, which are impossible on today's computers."
 
Today, this research is contributing to our understanding of the physical principles underlying thought and brain function. In the more distant future, it might serve as the basis for designing new methods of connecting the human brain to various artificial devices and systems.  

 

 
 
 
 
 

 

 

 

(l-r) Dr. Assaf Rotem and Prof. Elisha Moses. Smart nerve network
Math & Computer Science
English
  • Elisha Moses
  • Neural pathway
  • Physics of Complex Systems

Trees of Knowledge

English

 

Profs. Karl Skorecki and Ehud Shapiro. Jewish genetics

 

 
 
Are some contemporary Jewish men descended from the biblical Aaron? Are all cancer metastases derived from the same primary tumor? These are the kinds of questions addressed by Prof. Karl Skorecki, a Rambam Medical Center physician who recently spent his sabbatical leave in the Weizmann Institute's Computer Science and Applied Mathematics Department.
 
Why would a physician choose to spend his sabbatical among computer scientists? Skorecki splits his time between treating patients at Rambam and conducting research in population genetics as Director of the Rappaport Research Institute at the Technion – Israel Institute of Technology. He believes that interaction with computer scientists can help him solve biological problems in "out of the box" ways. Skorecki came to Weizmann because he was fascinated by the work of Institute computer scientist Prof. Ehud Shapiro, who has developed an innovative computational approach to tackling biological questions. Besides, Skorecki had already spent a sabbatical at Weizmann in 1991 before immigrating to Israel from Canada.
 
The approach developed by Shapiro's team takes advantage of certain markers on the DNA molecule to trace the origins, or lineage, of body cells. In particular, DNA regions called microsatellites, which contain numerous repeated genetic "letters," are especially prone to accumulating mistakes – just as a word like "Mississippi" could easily be misspelled as, say, "Missississippi." By assessing such genetic misspellings, scientists can tell how many divisions a cell has undergone and trace the lineage relations among cells.
 
The cells Skorecki studied during his sabbatical at the Weizmann Institute, in collaboration with postdoctoral fellow Dr. Shalev Itzkovitz, included different types of cancer cells. The goal of one collaborative study, for example, was to determine the number of divisions undergone by leukemia cells, which in turn can help assess the aggressiveness of the cancer.
 
These studies, Skorecki says, resemble the population genetics research he has been conducting for many years: "You are looking at the relatedness of cells rather than people, but in both cases you are using DNA analysis to build lineage trees that reveal common origins and different branches." In one study, he analyzed the Y chromosome, which determines male gender and is helpful for tracing ancestry because it is passed on intact from father to son. The analysis revealed that contemporary Jewish men traditionally belonging to the Cohanim tribe might have had a common male ancestor who lived 2,000 to 3,000 years ago – a finding that appears to support the Jewish tradition according to which following the exodus from Egypt, all Jewish priests, the Cohanim, are male descendants of Moses' brother Aaron. In another study, Skorecki and his colleagues found that nearly half of all Ashkenazi Jews can trace their ancestry back to just four women who lived close to 2,000 years ago. Skorecki has also recently revealed that genetic features of the Druze population in northern Israel and its neighboring countries lend credence to the Druze belief about the diverse origins of this ancient minority.
 
Skorecki: "The Weizmann Institute is making an enormous contribution to Israeli medicine by bringing physicians into its labs and teaching them to think like scientists. The more the physicians are trained in critical scientific thinking, the more effective they will be in treating patients. We need to realize the limits of our knowledge and always seek to learn more."
 
Prof. Ehud Shapiro's research is supported by the Clore Center for Biological Physics; the Arie and Ida Crown Memorial Charitable Fund; the Phyllis and Joseph Gurwin Fund for Scientific Advancement; Sally Leafman Appelbaum, Scottsdale, AZ; the Carolito Stiftung, Switzerland; and the Louis Chor Memorial Trust Fund. Prof. Shapiro is the incumbent of the Harry Weinrebe Chair of Computer Science and Biology.
 
(l-r) Profs. Karl Skorecki and Ehud Shapiro.
Math & Computer Science
English
  • Computer Science and Applied Mathematics
  • DNA
  • Ehud Shapiro
  • Gene code

The Inside View

English

Profs. Ronen Basri and Achi Brandt. Computer object recognition

 

Can computers see? Can they be taught to discern a polar bear on white snow? To tell where one spotted Dalmatian ends and another begins? To recognize a woman’s profile after viewing her face-on? Seemingly simple visual tasks that a human being takes for granted pose an enormous challenge to a computer: Every minor variation in lighting or angle interferes with the computer’s ability to perceive and identify objects. Living brains solve these problems thanks to amazing powers; computer scientists are working hard to endow machines with similar abilities.
 
A unique, innovative approach enabling computers to identify and recognize objects was developed by Dr. Eitan Sharon when he was a graduate student under the guidance of Profs. Ronen Basri and Achi Brandt of the Weizmann Institute’s Computer Science and Applied Mathematics Department, in collaboration with departmental colleague Dr. Meirav Galun and Dr. Dahlia Sharon of the Massachusetts General Hospital. The approach involves a multi-stage process that works from the bottom up.
 
The computer starts by comparing the individual pixels in an image and divides them into groups according to the degree of light intensity. The resulting groups go through a series of additional comparisons using such properties as texture, shape and so on. Groups that share common features are combined into increasingly larger segments, and at each stage the parameters for comparison become more numerous and complex. At the end of this process, known as segmentation, the computer can distinguish an object from its background. 
 
After obtaining good results at this stage, the scientists moved on to the next challenge – object recognition. As in a children’s “find the hidden object” game, the computer was instructed to scan through a large database and pick out an image of a pair of glasses identical to a pair it was shown. To perform this task, the computer divided a picture of the glasses into segments and compared these with all the glasses segments in the database, searching for examples whose features matched those of the original pair. At the end of the process, it succeeded in finding the identical glasses, even when these appeared at a different angle or in a slightly different way from the original pair. The method was recently described in the journal Nature.
 
Now that the computer is capable of recognizing objects, can it be put to medical use – recognizing signs of disease? To test this idea, which has been explored by researchers around the world in a variety of ways, the Institute scientists defined a goal: identifying lesions in the brains of patients with multiple sclerosis. In these patients, the protective myelin sheath covering the nerve fibers is damaged, and this damage shows up in magnetic resonance imaging (MRI). The imaging provides the physician with a series of brain sections, which today must all be reviewed by a human being. “In the distant future, we hope that a computer program will be able to recognize the damaged areas independently,” says Basri. “In the more immediate future, the system should be able to help the physician identify these areas and provide information about their location and size, so as to be able to evaluate the patient’s condition or the effectiveness of treatment.”
 
With the help of Prof. Moshe Gomori, a radiologist from Hadassah University Hospital in Jerusalem, the scientists made a number of adjustments to the computer program, enabling it to analyze a three-dimensional image constructed from all the MRI section scans. Data processing then followed the same stages as object recognition: The picture of the brain was divided into segments, and each segment was characterized by a set of features defined by expert radiologists: light intensity, texture, shape and location in the brain. Then followed classification: The computer examined different segments and decided whether an area was healthy or damaged. Decision making involved a learning process: The computer reviewed pictures of brain areas affected by multiple sclerosis and gradually learned to characterize them.
 
The first experiments have produced encouraging results: 60 to 70 percent of areas labeled by the computer as affected matched the physician’s assessment – a percentage similar to the degree of agreement between two physicians. Results of the study, performed by Ayelet Akselrod-Ballin, a graduate student of Basri and Brandt, in collaboration with Italian colleagues, were published in the Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.
 
The Weizmann Institute method has great potential for the diagnosis of any disease or disorder that produces signs visible through MRI or computed tomography scanning. The scientists are already working on additional applications, including the development of a program to identify liver tumors.
 
Now that they’ve taught the computer to see, Institute scientists hope to turn it into a multidisciplinary doctor’s aide that will be found in every clinic, assisting in the diagnosis and follow-up of a variety of ills. Once this vision is realized, they will only need to teach the computer to show a little empathy and tell the patient to say “Ah!”   
 
Prof. Ronen Basri’s research is supported by the A.M.N. Fund for the Promotion of Science, Culture and Arts in Israel.
 
Prof. Achi Brandt’s research is supported by the Philip M. Klutznick Fund for Research. Prof. Brandt is the incumbent of the Elaine and Bram Goldsmith Professorial Chair of Applied Mathematics.
 
Math & Computer Science
English
  • Achi Brandt
  • Artificial vision
  • Computer Science and Applied Mathematics
  • Ronen Basri

The Art of Compromise

English
Prof. Oded Goldreich and Prof. Dana Ron. Close enough for use
 
 

 

Scientists have confirmed what many suspected all along: We live in an imperfect world, filled with less-than-ideal choices. For example, in computing the solution to a problem with a large number of parts, we're forced to choose between efficient computation and an exact solution. If complete accuracy is essential, the computing process is likely to be slow and costly, whereas if we want a "fast and cheap" answer, there is no guarantee it will be exact. According to a recent study by Prof. Oded Goldreich of the Weizmann Institute's Computer Science and Applied Mathematics Department and his spouse, Prof. Dana Ron of the Electrical Engineering-Systems Department at Tel Aviv University, opting for efficiency over accuracy may very often yield results that are close enough to perfect to be useful in many applications.

Efficiency, in the case of computing, means a processing time that is relatively fast in comparison to the amount of data. If the time needed to carry out the computation grows at a steady rate relative to increasing input, it's considered to be fairly efficient. In comparison, processing that expands exponentially in relation to the data is inefficient and typically impractical.

For extremely large data sets, however, even computing at linear rates can be too slow to be feasible. For certain types of problems, Goldreich and Ron found a way to work with super efficiency - by developing a technique that reads just part of the data. What they had to sacrifice was absolute accuracy.

Their method was designed with networks in mind. Networks, such as the Internet, are large entities made up of sites, or nodes, and the links between them. Questions concerning networks may involve enormous amounts of data. They may ask, for instance, how connected is the network (i.e., can one get from any one point to any other point, and through how many different routes)? Or what is the average distance between two nodes? These issues affect research and planning in areas as diverse as computer networks, transportation and biological studies of gene and protein networks.

The standard algorithms (a computer's plans of action) one might use to answer these questions must analyze all of the data found in a network. So efficient are Goldreich and Ron's algorithms, they're dubbed sublinear (the processing needed is smaller than the input size); they randomly choose samples of network nodes and then scan only a portion of the immediate surroundings. Like election-time pollsters, who come close to predicting the actual election results on the basis of a representative sampling of voters, the scientists' method can produce approximate, but very close, answers on the basis of only a fraction of the data.

One of their algorithms, for example, can determine with near accuracy whether a given network is bipartite (separable into two parts). The nodes of a bipartite network can be partitioned such that all of its links are only to nodes in the opposite part. To process the data in a large network with a standard algorithm could range from time-consuming and expensive to futile. In contrast, the scientists' algorithm works by taking a random sample (sample size is determined by the size of the data list and can be as small as its square root) and then taking a small number of steps in random directions.

Thus in cases in which close is good enough, or better than nothing at all, Goldreich and Ron's algorithms may make a lot of sense. For a small loss in accuracy, the scientists gain a great deal of efficiency. And that, in an imperfect world, is close to ideal - a solution based on compromise.
 
Prof. Oded Goldreich is the incumbent of the Meyer W. Weisgal Professorial Chair of Experimental Physics.

 

100 Proof

How can we convince someone of something without giving away any information? Prof. Goldreich, whose work often deals with randomness and interaction, came up with the following story to illustrate the key to so-called zero-knowledge proofs:

On Olympus, the practical-minded Hera declared that all new nectar jugs, formerly of gold, be henceforth fashioned from silver. But perceptive Athena complained, claiming the nectar from the silver jugs did not taste as good as that from the gold ones. Zeus, already irritated with Hera's economizing, let loose his ire: "Let her be served 100 gourds of nectar, each poured at random from an old or a new jug, and let her tell them apart!" To Zeus' surprise, Athena correctly identified the source of each sip of nectar, convincing him there really was a difference.

Athena must have had a way of discerning one taste from the other. (Otherwise, even a goddess would have gotten the answer right only about half the time.) But her proof was based only on the randomness of the repeated servings, not on her means of identifying them, so Zeus learned nothing beyond the fact that she was right. Such zero-knowledge proofs are useful in designing secure computer systems.
 
(l-r) Prof. Oded Goldreich and Prof. Dana Ron. Super efficiency
Math & Computer Science
English
  • Algorithm
  • Computer Science and Applied Mathematics
  • Oded Goldreich

A-mazing Algorithm

English

Dr. Omer Reingold. Into the maze

People have been trying to find their way through mazes since ancient times. Consider the subjects of ancient Athens, forced each year to send seven youths and seven maidens to Minos, the king of Crete, as tribute. These 14 captives were then sent into an exitless maze that housed the youth-and-maiden-eating Minotaur at its center.
 

Theseus, son of Aegeus, king of Athens, with the help of the besotted Ariadne, daughter of Minos, put an end to the Minotaur and the maze’s notoriety. Just as he was about to enter, Ariadne slipped him a ball of thread. One end of the thread was tied to the maze entrance, and Theseus unwound the ball as he roamed the maze in search of the beast at its center. Of course, he managed to kill the Minotaur and, thanks to Ariadne’s thread, found his way out of the maze in safety.
 

The first lesson to be learned from this story is: don’t venture into a maze unprepared. If you’ve forgotten to bring a spool of thread from home, be ready to go to some trouble to get out. From ancient times, the best method for finding one’s way through a maze required leaving threads or signposts. Even for a computer, the only other approach that did not require a very large amount of memory was randomness. If every time you came to an intersecting path, you randomly decided (by flipping a coin, for example) which direction to take, you would eventually get to the point in the maze you were aiming for. Enter Dr. Omer Reingold of the Computer Science and Applied Mathematics Department. Reingold recently came up with a method that’s deterministic (not based on randomness) yet economical when it comes to memory use.

 

Maze for a modern-day Theseus

 

Why should a computer scientist care about mazes? Because a maze can be used as a model for a network – of computers, airline flight routes, roads, etc. In fact, the ability to find a path through a maze or network is a fundamental problem lying at the very heart of much of computer science. Many complex calculations contain deeply hidden mazes. Questions asked by computer scientists in this field are: How much time and how much memory are needed to calculate the steps needed to get from point A to point B in a maze or on a road map? The time question was solved decades ago, the memory question only partially. It’s known that the algorithm (a computer’s plan of action) for finding the way based on random turnings consumes a very small amount of memory. All that’s required is to remember the present position of the “captive” in the maze. In comparison, deterministic algorithms have been memory-hungry when it comes to solving mazelike problems.

 

Recently, Reingold managed to find a solution to this basic quandary, which has engaged many a computer scientist for the last 35 years. Reingold’s algorithm is both deterministic and able to keep memory use down to levels nearly as low as those of the randomness-based algorithms. Armed with the new algorithm, the modern Theseus can enter his maze equipped with an explicit set of navigating instructions -- for example: Turn right at the second intersection, pass three more intersections and turn left, and so on. What’s more, the same series of simple instructions works for every maze and every map.
 

How does the new algorithm work? Reingold’s method of reducing the memory load is as surprising as it is counterintuitive. His first step is to further complicate the maze, adding new paths and intersections. These are laid out in such a way as to convert the original maze into a type known to computer scientists as an “expander graph.” The algorithm for finding a route through an expander graph is known to be a simple one that uses little memory. Reingold’s technique conserves the basic layout of the original while building the enlarged maze. Thus, from the route that has been plotted through the expanded maze, it is possible to reconstruct the correct trail through the smaller one, again using minimal memory.
 

Reingold’s work will likely offer computer scientists a new approach to many problems awaiting solution. In particular, it contains vital clues that randomness may not be the only way to spare computer memory. Though randomness is convenient for planning algorithms, Reingold’s innovative work hints at the possibility that for each algorithm that uses randomness, one can find a deterministic one that will carry out the same tasks using a comparably low outlay of memory.

 

Dr. Omer Reingold’s research is supported by the Center for New Scientists. Dr. Reingold is the incumbent of the Walter and Elise Haas Career Development Chair.
 

 
Dr. Omer Reingold. Memory saver
Math & Computer Science
English
  • Algorithm
  • Computer Science and Applied Mathematics
  • Omer Reingold

Code for Success

English

Prof. Adi Shamir. The S in RSA

 

The A.M. Turing Award, regarded in academic circles as the 'Nobel Prize' of computer science, has been awarded to Prof. Adi Shamir of the Weizmann Institute of Science.
 
Shamir shares the award with Ronald L. Rivest of the Massachusetts Institute of Technology and Leonard M. Adleman of the University of Southern California. The Association for Computing Machinery (ACM) presented the award to them in its annual meeting.
 

Secure transactions

 
While working at M.I.T. in 1977, the three scientists developed an algorithm that was later called RSA (the acronym for their last names). Used worldwide to secure Internet, banking and credit card transactions, the RSA algorithm allows for the delivery and deciphering of encrypted codes between parties that have never previously been in contact. The time needed to crack some versions of the code, which is based on the multiplication of two very large prime numbers and the difficulty in deducing those prime numbers from their product, is estimated at millions of years.
 
Among the numerous applications of this research are smart cards, regularly installed in household television sets to ensure that only subscribers receive TV satellite broadcasts. The smart card also allows the company activating the satellite to charge its customers only for programs viewed by them.
 
Shamir began his acquaintance with the Weizmann Institute of Science as a teenager participating in its youth activities. He later earned his M.Sc. and Ph.D. degrees at the Weizmann Institute and spent three years at M.I.T. He then returned to the Institute, publishing numerous articles and receiving several prestigious awards, including ACM's Kanellakis Award, the Erdos Prize of the Israel Mathematical Society, the IEEE's W.R.G. Baker Prize, the UAP Scientific Prize, The Vatican's PIUS XI Gold Medal and the IEEE Koji Kobayashi Computers and Communications Award.
 

Second winner at Weizmann

 
In 1996, the A.M. Turing Award was conferred on Prof. Amir Pnueli, also a Weizmann Institute computer scientist, for his contributions to program and systems verification. Prof. Michael Rabin of the Hebrew University of Jerusalem and Harvard University received the award in 1976 for his research on nondeterministic machines. The award has been presented annually since 1966 to individuals who have made contributions of 'lasting and major technical importance in the field of computer science.'
 

THE CODE CRACKERS

 
The English mathematician Alan Turing, for whom the prize is named, cracked the German coding system 'Enigma' with his team during World War II, using a system he developed, called 'Bomba.' Many historians believe that this achievement actually decided the Battle of the Atlantic in favor of the Allies.
 

Alan Turing. Enigma

 

 

Prof. Shamir's research is supported by Mr. Mickey Cohen, Director of Technologies, SoftChip Technologies (3000) Ltd.; Mr. Junichi Hattori, Executive Vice President, SII-Seiko Instruments Inc.; Mr. Takeo Hiyama, President/CEO, Abit Corp.; and Ms. Yuko Ishida, President/CEO, Japan Datacom. He is the incumbent of the Paul & Marlene Borman Professorial Chair of Applied Mathematics.
Prof. Adi Shamir. Encryption
Math & Computer Science
English
  • A.M. Turing Award
  • Adi Shamir
  • Algorithm
  • Amir Pnueli
  • Applied Mathematics and Computer Science

Teaching Computers to See

English

Basri, Galun, Brandt and Sharon. Seeing is believing

 

Skeptic: Billions of nerve cells in the human brain are involved in the process of vision. Since scientists find it difficult to understand even one of those cells, it's inconceivable that computers will ever be able to see.

 

Scientist: All the more reason to start working on it.

 
If one could make a computer see, reproducing the natural visual process, one would be adding an important dimension to many aspects of life: Computers could lend an 'extra eye' in the operating room, alerting doctors to problems; surveillance systems would be greatly improved; and quality control in production lines could be significantly enhanced. Along the way, we might attain crucial insights into how the brain constructs images.
 
The problem is the way computers read images. They see them as grids whose tiny squares (pixels) each give the computer only one type of information: color. Color, though, can be an ambiguous guide when it comes to distinguishing between objects. A yellow butterfly on a yellow flower could be mistaken by the computer for part of the flower. A clown, displaying numerous colors, could be interpreted as many different objects. A zebra, having two alternating colors, could be split into the number of its stripes.
 
Recently, a team from the Weizmann Institute devised a method that significantly improves computers' ability to see. The new approach goes from the bottom up -  beginning with one pixel. Each pixel in the image is compared to surrounding pixels in terms of color. As groups of pixels emerge, they are compared to one another using a wide range of more complex parameters: texture (the zebra's alternating black and white stripes emerge as a 'texture' characterizing one object), shape (groups of pixels, in contrast to individual pixels, will form a shape), average fluctuations in color, and more.
 
Groups having common parameters are joined. The bigger the groups, the more the parameters can be made refined and complex. The different objects in the image are separated according to the combination of parameters, which are so diverse that the error range is very small.
 
It doesn't sound as though any of this can be done in the blink of an eye, but in fact this method is much faster than all other existing methods. The reason: In the first stages, when individual or small groups of pixels are compared, only a few 'simple' parameters are employed to compare them. At later stages, many more complex parameters are used to compare large groups of pixels, but by then there are much fewer groups to compare. Thus the complex parameters are also not as time consuming as might be expected.
 
The technique was developed by then Ph.D. student Eitan Sharon under the supervision of Profs. Achi Brandt and Ronen Basri and in collaboration with Dr. Meirav Galun, all in the Applied Mathematics and Computer Science Department. They are currently working to improve the approach.
 
Of course, even if a computer is finally able to distinguish easily between objects, other obstacles will have to be overcome before it is able to 'see' as we do. For one thing, it will have to be taught to interpret what it sees and to correctly categorize objects (for instance, to understand that a poodle and a German shepherd both belong in the 'dog' category despite their different appearances). Thanks to the complexity of our brains, we perform these functions easily. Will scientists find a way to simplify these functions so that they can be incorporated into computers? It may take a while until we find out.

Comparison: Original, Weizmann and other techniques

 

 

Prof. Brandt's research was supported by the Karl E. Gauss Minerva Center for Scientific Computation. He is the incumbent of the Elaine and Bram Goldsmith Professorial Chair of Applied Mathematics.

Prof. Basri conducts his research in the Moross Laboratory for Vision Research and Robotics.

Comparison: Original, Weizmann and other techniques
Math & Computer Science
English
  • Achi Brandt
  • Applied Mathematics and Computer Science
  • Artificial vision
  • Computer learning
  • Ronen Basri

Pages