Improving Flat Panel Displays by Discrete Optimization
Our objective is to advance the state of the art in modern display technology by means of discrete optimization. Specifi cally, we want lower power consumption in the next generation of fl at-panel displays through a reduction of their addressing time. To this end, we exploit a common feature of today’s displays: the pixels are arranged in a matrix fashion with only one contact per row and per column. For the sake of simplicity, let’s assume that these contacts are switches and that a pixel (i,j) shines if and only if the switches for row i and column j are closed. This implies that an arbitrary pattern cannot be displayed at the same time. Hence, several subframes are necessary to display an image entirely. Traditionally, an image is displayed rowby-row at a suffi ciently high frame rate such that the eye perceives the average. This method is called Single Line Addressing since each subframe consists of a single line. This is a major cause of excessive power consumption because each pixel only shines for a very short time, and thus, it must shine very brightly to achieve a suffi cient average brightness. However, it is possible to drive multiple rows at once, though only by solving a discrete optimization problem in realtime on a driving chip. Constrained by the strong competition on the display market, successful algorithms must be effi cient with respect to arithmetic operations and memory consumption.
We have developed a fully combinatorial approximation algorithm for the practically relevant case in which pixels in consecutive rows are addressed simultaneously. Because the algorithm uses only addition, subtraction, and comparisons, it is well-suited for implementation in hardware. Nevertheless, our algorithm computes decompositions in real-time whose objective values are within one percent of the optimum solution in the majority of cases in practice. This invention was patented and commercialized by Dialog Semiconductor under the brand name SmartXtend and made transparent and fl exible displays possible. In particular, it is used in transparent OLED displays by Futaba (formerly TDK). The Lenovo S800 [ fi gure 1 ] , the Explay Crystal, and the Nexian Glaze M9090 are three mobile phones available on the international market that are driven by our technology.
Figure 1: Lenovo S800, driven by our technology
In a follow-up project funded by the German Research Foundation, we extend this research to further display technologies. Our framework will apply to devices like OLED displays, plasma screens, and e-paper.
Figure 2: Representing the display matrix by a bipartite graph
We develop new sophisticated driving algorithms and thereby contribute to the theory of addressing matrix displays, which still lacks a profound understanding of the underlying computational problems. Due to the relation of binary matrices to bipartite graphs, the addressing problem is captured by the problem of decomposing the edge set of a bipartite graph into a minimum number of complete bipartite subgraphs, also called bicliques. This project will close a research gap in the area of approximation algorithms for biclique decomposition problems, and the foundational research will benefit fl at panel displays and in turn other applications, for example, in graph drawing, computer security, and genetics. In fact, we have already taken a leap forward by recently proving nearly tight lower and upper bounds for approximation factors of polynomial-time algorithms for biclique covering and partition.
DEPT. 1 Algorithms and Complexity
Phone +49 681 9325 1007
Email karrenba mpi-inf.mpg.de