應用生物特徵及視覺密碼學防治車輛失竊和酒醉駕車
車輛遭竊以及酒醉駕車對社會安全造成的危害普遍存在於世界各先進國家。以目前看來，此問題並非嚴刑峻罰就能解決的。若本研究計畫將來普及應用於大眾，必定可以同時減少車輛遭竊之機會和預先防範酒醉者開車駕駛。 生物特徵泛指指紋、虹膜、臉型、聲紋甚至DNA 等等，它的特性即每個人均具有此獨一無二的性徵，加以應用就如同無法被仿造或偷竊的身分證明。若車主能利用自己的生物特徵為車輛上鎖，即可防止車輛遭竊。 視覺密碼學是屬於資訊隱藏技術的一種，藉由兩張以上的影像疊合後呈現其中隱藏之機密資料。雖然視覺密碼學原先純粹是為了加密資料，但我們將之加以修改，設計出複雜且無意義的偽裝影像，使其不易被酒醉後神智不清的人疊合成功而讀出其中的加密資料。 結合生物特徵及視覺密碼學，即可設計出一套可安裝於車上的系統，不僅防止車輛失竊又能防止酒醉駕車事故的發生。 ;The damage which is caused to social security by car stealing and drunk driving universally exist in others developed countries. As things are, these problems can not be solved by severe law. If our project can be applied in the masses extensively, it must be able to prevent both car stealing and drunk driving. Roughly speaking, biological characteristics mean fingerprint, iris, face, pronunciation and DNA. Their uniqueness is a special feature that everyone has. If we can apply it more, the characteristics are identification that can not be imitated or stolen. If the car owner can use his or her biological characteristics to lock the car, the car stealing could be prevented. Visual cryptography belongs to a kind of information hiding. By stacking two or more images, user can recognize the secret information hiding in the stacking. Although visual cryptography is merely created for encryption at first, we modify it and design a complex as well as meaningless stego-image. That makes the unconscious driver who is drunk fail to both stack the images and recognize the secret information hiding inside. We combine biological characteristics with visual cryptography and design a suit of system that is able to install in the car. This system can prevent not only car stealing but also drunk driving.
讓視域更遼闊--在有限的螢幕空間上顯示更多的圖形式資訊
在利用電腦螢幕來瀏覽圖形式資訊的時候，常常受限於螢幕的空間，沒有辦法在顯示\r 資訊整體結構的同時顯現細節部分的資料，目前的使用者介面所採用的方法有放大（zoom\r in）、捲動（scrolling）、開啟多個視窗（multiple view）等方法，這些方法雖然可以呈現出資\r 料的細節部分，但是仍有其個別的缺點存在，放大的方式會有遮蔽的情形；捲動的方式無\r 法同時地呈現整體結構；開啟多個視窗的方法使得使用者的眼睛必須在這些視窗間來回的\r 移動，造成麻煩。\r 魚眼鏡頭是一種短焦距、大視角的相機鏡頭，鏡頭成像的時候，越接近鏡頭中心的物\r 體會越放大而越遠的部分會越縮小，藉著發掘魚眼鏡頭的成像函數，我們發展出了一種新\r 的使用者介面，在瀏覽圖形式資訊的時候，能夠顯示整體的結構，並隨著滑鼠游標的移動，\r 以不開啟新視窗及無遮蔽的方式，即時地將想要觀察的部分局部放大以展現細部的資料，\r 這種使用者介面將具備現有方法的優點而無其缺點。\r Browsing the global structure of a large graph in limited screen space has the drawback that details\r are often too small to be seen. The most common solution provides a scrollable view. This shows full\r details at the region currently visible through the view, but hides the rest of the global structure.\r Alternatively, zooming into a part of the graph does show local details but misses the overall structure of\r the graph. The multiple views approach, one view of the entire graph and the other of a zoomed portion,\r has the advantage of seeing both local details and overall structure, but has the drawback that parts of the\r graph adjacent to the enlarged area are not visible at all in the enlarged views.\r A fisheye camera lens is a very wide angle lens that magnifies nearby objects while shrinking distant\r objects. It seems to be a tool for seeing local detail and global structure simultaneously. By means of\r exploring fisheye camera lens, we develop a user interface for browsing graphs using program analog of\r fisheye lens. Thus, our method seems to have all the advantages of the other approaches without suffering\r from any of the drawbacks.\r \r
灰階影像內容之檢索技術
資訊時代的來臨，促使我們的社會型態大幅改變，無一不朝數位化的方向邁進。網際網路與資訊科技的快速發展，近年來影像資料庫和數位圖書館大量的成立，關於影像資料檢索的研究已漸漸成為一門極為重要的研究議題。在本研究報告中，我們提出一種植基於向量量化編碼法的灰階影像檢索技術。向量量化編碼法是一種極為簡單的影像壓縮技術。我們應用這個編碼法，來萃取出灰階影像內容的特徵值。同時我們也計算出整張影像與影像中間位置的像素平均值，作為日後檢索影像時過濾掉影像資料庫中不需要比對特徵值的依據。\r 我們所提出的方法能有效地萃取影像內容的特徵值並且讓使用者可以快速且正確地查詢到所需要的影像。當影像資料庫中存在與查詢影像完全相同的影像時，我們的檢索技術都能在第一時間第一順位檢索出這張影像。即便影像資料庫中不存在與查詢影像完全相同的影像時，我們的檢索技術平均74.3%也能在第一時間前五個順位檢索出最相似的影像。\r \r With the coming of the information age, our sociological system change extensively, and everything has moves toward digitization. Due to the rapid development of Internet, information technology, the rapid growth of image databases and digital libraries recently, the related researches of image retrieval have become a very important issue. In this memoir, we propose an image retrieval scheme based on the vector quantization to retrieve similar images from the image database according to the pre-collected image features. Vector quantization is a very simple image compression scheme. We have applied vector quantization to extract features from grayscale image. In order to speed up the retrieval process, we also calculated the mean pixel values of whole images and the central part of the image to filter the images, which are significantly dissimilar to the query image.\r The experimental results show that our proposed approaches can effectively extract features from the image and enable users to retrieve images from image database quickly and accurately. When images stored in image database match query image, the proposed scheme can instantly retrieve the stored image at the first rank. Even though images stored in image database query image exactly, the proposed scheme can instantly retrieve the stored image over 74.3% at the first five ranks.
The discovery of America
1.- Purpose of the research This Game is a new education system, where we take as reference a historical event called "The Discovery of America." The objective is to implement a new way of teaching materials using the technology developed in recent decades, where the teacher uses a modern and educational support to keep the mind of the student in ongoing activity; this will allow greater retention which gives result better understanding and more knowledge. The system is designed to model how to teach with the versatility of being a teacher to provide knowledge through a book because it contains the text outlined and summarized the history and examination by the implementation of questions that offer 4 possible answers and answering incorrectly restart the game, it forces the player to pay attention and remember information. 2. Procedures It divided the two-step strategy: 1. Define the game. The player is asked to bring the features of the game. It must recognize three: a) The technical aspects, allowing the appropriation of technological language and sometimes the understanding of the technology used to play is essential for future acquisitions; b) the commercial tab: identify which company developed the game, age or classification suggested, price, where purchased, country of origin, etc.., a review of the business tab allows to point out habits, and c) a description of the game, review of the plot, characters, history, objectives, modality, gender (role, simulation, strategy, battle, etc..) duration, etc.. This category allows the recognition of recreational preferences of the subject. 2. Thinking the game. Before, during or after the game the subject must think what you do to win or how the game unfolds. Contrary to what seems, while playing one thinks and sometimes thinks that performing other tasks and this time it is the player or the viewer understand the way it works and identify the physical or mental is used to play, trying to understand what I do but most of all how I do it, it is metacognition. 3. Data This prototype is structured in RSS: stands for Ruby Scripting System: System with Ruby Scripting for games. Object-Oriented programming "OOP" is a model used by the most programming languages, that lets you use objects and their relationships to program what will be the final application. In order to expand its use were included languages spoken in America and expanded platform for different operating systems. 4. Conclusions With this fun game is a simple way to learn the story in time, the environment and the circumstances where the player is the student of our system that shapes the teacher, book review, making it a modern and practical way to teach with the advantage of keeping the mind active during the use of our game, this allows the continued interest in the student normally lost in conventional classes.
Generalized Quantum Tic-Tac-Toe
Early physicists such as Newton thought that all objects have definite positions. For example, they thought that an apple is either inside a fruit bowl, or outside of it. The advent of quantum physics in the early 20th century proved this viewpoint wrong. There is an uncertainty in the position of any object; we can find a set of possible locations where the object might be. This concept was termed superposition. Quantum tic-tac-toe (QT3) elegantly extends the popular game of tic-tac-toe by adding this quantum physics concept of superposition. Each turn, 1 piece is simultaneously played into 2 distinct squares of a 3-by-3 grid. Eventually, however, every piece will occupy exactly one square, like in tic-tac-toe. Yet, despite this intriguing addition, not much research has been done on the game. Hence in this paper we explore the game in terms of extension, analysis and solution. Firstly, we note that the quantum extension proposed by Alan Goff in QT3 is incomplete. In reality, there can be more than 2 possible locations for any object. Unfortunately, the QT3 game rules do not allow for this extension. Thus we non-trivially generalize the game (GQT3) by proposing a new set of rules. We show that the original QT3 is a subset of GQT3 and prove that our generalized game can always be successfully played from start to finish in a finite number of moves. Then, we begin our analysis of GQT3. Firstly, we investigate the game tree complexity, state space complexity and computational complexity of the game; indicators of how complicated the game is. Notably, we find here that QT3 has a total of about 18 trillion possible games, which is substantially higher than tic-tac-toe’s 400 thousand. Then we examine the Nash Equilibrium of the game; the result if two ‘Gods’ play the game against each other. We find that in this scenario, the first player will win by 0.5 points. To make the game fairer, we suggest minor variations on the scoring, which make the Nash Equilibrium a draw. Note that standard methods to analyze all of these would take at least a year, but we bring down the time to about a minute using symmetry considerations and other optimizations. Finally, we extend our programs into an artificial intelligence that is a perfect solution to the game. We then supplement this with a utility function to make the run-time performance pragmatic for more time-consuming versions of GQT3. Ultimately, GQT3 is a challenging and unique game with myriads of exploration possibilities; we have only scratched the surface here.
A load-balancing strategy for coarse-grained tree searches as applied to fractal image compression
An exact solution to many current computational problems, such as the famous Travelling Salesman Problem (TSP), require a complete tree traversal in order to determine. This is often unfeasible, as the time complexity of the tree traversal grows exponentially with the size of the input, thus leading to an essentially computationally intractable problem. The branch and bound technique is an approach commonly used to speed this process. It entails dynamically pruning off branches of the tree in which the answer is probably not found in, hence reducing the amount of data that is needed to be traversed and the total time and resources required to perform the computation. In this paper, we introduce a new load-balancing strategy for the execution of such a branch and bound algorithm in parallel, using a three-tiered hierarchical approach, to perform fractal image compression, which is essentially a complete tree traversal problem. This novel heuristic is aimed at achieving optimal load-balancing and minimising unnecessary network traffic and bottlenecking, which functions by predicting the optimum search depth and hence controlling the coarseness of the input that is assigned to each worker node. Our scheme additionally enables us to tailor to the specifications of different clusters, as the heuristic is adjusted based on network speed and processor speed, which vary appreciably from cluster to cluster. We further discuss how to apply our method to other large tree search problems, such as the TSP and other NP-complete problems. We have also enhanced an existing load-balancing strategy outlined in Crivelli et. al. (2004, IBM Journal of Research and Development), by prioritising the reallocation of idle worker nodes such that supervisors who are in need of more help receive a larger share of the free workers.
Do SAT Problems Have Boiling Points？
The Boolean Satisfiability problem, called SAT for short, is the problem of determining if a set of constraints involving Boolean (True/False) variables can be simultaneously satisfied. SAT solvers have become an integral part in many computations that involve making choices subject to constraints, such as scheduling software, chip design, decision making for robots (and even Sudoku!). Given their practical applications, one question is when SAT problems become hard to solve. The problem difficulty depends on the constrainedness of the SAT instance, which is defined as the ratio of the number of constraints to the number of variables. Research in the early 90’s showed that SAT problems are easy to solve both when the constrainedness is low and when it is high, abruptly transitioning (“boiling over” ) from easy to hard in a very narrow region in the middle. My project is aimed at verifying this surprising finding. I wrote a basic SAT solver in Python and used it to solve a large number of randomly generated 3SAT problems with given level of constrainedness. My experimental results showed that the percentage of problems with satisfying assignment transitions sharply from 100% to 0% as constrainedness varies between 4 and 5. Right at this point, the time taken to solve the problems peaks sharply. Similar behavior also holds for 2SAT and 4SAT. Thus, SAT problems do seem to exhibit phase transition behavior; my experimental data supported my hypothesis.