Hough transforms are techniques for object detection, a critical step in many implementations of computer vision, or data mining from images. Specifically, the Randomized Hough transform is a probabilistic variant to the classical Hough transform, and is commonly used to detect curves (straight line, circle, ellipse, etc.) The basic idea of Hough transform (HT) is to implement a voting procedure for all potential curves in the image, and at the termination of the algorithm, curves that do exist in the image will have relatively high voting scores. Randomized Hough transform (RHT) is different from HT in that it tries to avoid conducting the computationally expensive voting process for every nonzero pixel in the image by taking advantage of the geometric properties of analytical curves, and thus improve the time efficiency and reduce the storage requirement of the original algorithm. == Motivation == Although Hough transform (HT) has been widely used in curve detection, it has two major drawbacks: First, for each nonzero pixel in the image, the parameters for the existing curve and redundant ones are both accumulated during the voting procedure. Second, the accumulator array (or Hough space) is predefined in a heuristic way. The more accuracy needed, the higher parameter resolution should be defined. These two needs usually result in a large storage requirement and low speed for real applications. Therefore, RHT was brought up to tackle this problem. == Implementation == In comparison with HT, RHT takes advantage of the fact that some analytical curves can be fully determined by a certain number of points on the curve. For example, a straight line can be determined by two points, and an ellipse (or a circle) can be determined by three points. The case of ellipse detection can be used to illustrate the basic idea of RHT. The whole process generally consists of three steps: Fit ellipses with randomly selected points. Update the accumulator array and corresponding scores. Output the ellipses with scores higher than some predefined threshold. === Ellipse fitting === One general equation for defining ellipses is: a ( x − p ) 2 + 2 b ( x − p ) ( y − q ) + c ( y − q ) 2 = 1 {\displaystyle a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1} with restriction: a c − b 2 > 0 {\displaystyle ac-b^{2}>0} However, an ellipse can be fully determined if one knows three points on it and the tangents in these points. RHT starts by randomly selecting three points on the ellipse. Let them be X 1 {\displaystyle X_{1}} , X 2 {\displaystyle X_{2}} and X 3 {\displaystyle X_{3}} . The first step is to find the tangents of these three points. They can be found by fitting a straight line using least squares technique for a small window of neighboring pixels. The next step is to find the intersection points of the tangent lines. This can be easily done by solving the line equations found in the previous step. Then let the intersection points be T 12 {\displaystyle T_{12}} and T 23 {\displaystyle T_{23}} , the midpoints of line segments X 1 X 2 {\displaystyle X_{1}X_{2}} and X 2 X 3 {\displaystyle X_{2}X_{3}} be M 12 {\displaystyle M_{12}} and M 23 {\displaystyle M_{23}} . Then the center of the ellipse will lie in the intersection of T 12 M 12 {\displaystyle T_{12}M_{12}} and T 23 M 23 {\displaystyle T_{23}M_{23}} . Again, the coordinates of the intersected point can be determined by solving line equations and the detailed process is skipped here for conciseness. Let the coordinates of ellipse center found in previous step be ( x 0 , y 0 ) {\displaystyle (x_{0},y_{0})} . Then the center can be translated to the origin with x ′ = x − x 0 {\displaystyle x'=x-x_{0}} and y ′ = y − y 0 {\displaystyle y'=y-y_{0}} so that the ellipse equation can be simplified to: a x ′ 2 + 2 b x ′ y ′ + c y ′ 2 = 1 {\displaystyle ax'^{2}+2bx'y'+cy'^{2}=1} Now we can solve for the rest of ellipse parameters: a {\displaystyle a} , b {\displaystyle b} and c {\displaystyle c} by substituting the coordinates of X 1 {\displaystyle X_{1}} , X 2 {\displaystyle X_{2}} and X 3 {\displaystyle X_{3}} into the equation above. === Accumulating === With the ellipse parameters determined from previous stage, the accumulator array can be updated correspondingly. Different from classical Hough transform, RHT does not keep "grid of buckets" as the accumulator array. Rather, it first calculates the similarities between the newly detected ellipse and the ones already stored in accumulator array. Different metrics can be used to calculate the similarity. As long as the similarity exceeds some predefined threshold, replace the one in the accumulator with the average of both ellipses and add 1 to its score. Otherwise, initialize this ellipse to an empty position in the accumulator and assign a score of 1. === Termination === Once the score of one candidate ellipse exceeds the threshold, it is determined as existing in the image (in other words, this ellipse is detected), and should be removed from the image and accumulator array so that the algorithm can detect other potential ellipses faster. The algorithm terminates when the number of iterations reaches a maximum limit or all the ellipses have been detected. Pseudo code for RHT: while (we find ellipses AND not reached the maximum epoch) { for (a fixed number of iterations) { Find a potential ellipse. if (the ellipse is similar to an ellipse in the accumulator) then Replace the one in the accumulator with the average of two ellipses and add 1 to the score; else Insert the ellipse into an empty position in the accumulator with a score of 1; } Select the ellipse with the best score and save it in a best ellipse table; Eliminate the pixels of the best ellipse from the image; Empty the accumulator; }
Spanner (database)
Spanner is a distributed SQL database management and storage service developed by Google. It provides features such as global transactions, strongly consistent reads, and automatic multi-site replication and failover. Spanner is used in Google F1, the database for its advertising business Google Ads, as well as Gmail and Google Photos. == Features == Spanner stores large amounts of mutable structured data. Spanner allows users to perform arbitrary queries using SQL with relational data while maintaining strong consistency and high availability for that data with synchronous replication. Key features of Spanner: Transactions can be applied across rows, columns, tables, and databases within a Spanner universe. Clients can control the replication and placement of data using automatic multi-site replication and failover. Replication is synchronous and strongly consistent. Reads are strongly consistent and data is versioned to allow for stale reads: clients can read previous versions of data, subject to garbage collection windows. Supports a native SQL interface for reading and writing data. Support for Graph Query Language == History == Spanner was first described in 2012 for internal Google data centers. Spanner's SQL capability was added in 2017 and documented in a SIGMOD 2017 paper. It became available as part of Google Cloud Platform in 2017, under the name "Cloud Spanner". == Architecture == Spanner uses the Paxos algorithm as part of its operation to shard (partition) data across up to hundreds of servers. It makes heavy use of hardware-assisted clock synchronization using GPS clocks and atomic clocks to ensure global consistency. TrueTime is the brand name for Google's distributed cloud infrastructure, which provides Spanner with the ability to generate monotonically increasing timestamps in data centers around the world. Google's F1 SQL database management system (DBMS) is built on top of Spanner, replacing Google's custom MySQL variant.
Alex Krizhevsky
Alex Krizhevsky is a Canadian computer scientist most noted for his work on artificial neural networks and deep learning. In 2012, Krizhevsky, Ilya Sutskever and their PhD advisor Geoffrey Hinton, at the University of Toronto, developed a powerful visual-recognition network AlexNet using only two GeForce-branded GPU cards. This revolutionized research in neural networks. Previously neural networks were trained on CPUs. The transition to GPUs opened the way to the development of advanced AI models. == AlexNet == Motivated by Sutskever and inspired by Hinton, Krizhevsky developed AlexNet to expand the limits in image recognition and classification. Building on Convolutional Neural Networks and Sutskever’s Deep Neural Network approach of deepening the neural layers far beyond the convention of the time—as well as adding Dropout for training resilience—AlexNet won the ImageNet challenge in 2012. The team presented their paper for AlexNet at NeurIPS (NIPS) 2012. Shortly after AlexNet’s debut, Krizhevsky and Sutskever sold their startup, DNN Research Inc., to Google. Krizhevsky left Google in September 2017 after losing interest in the work, to work at the company Dessa in support of new deep-learning techniques. Many of his numerous papers on machine learning and computer vision are frequently cited by other researchers. He is also the main author of the CIFAR-10 and CIFAR-100 datasets. == Legacy == AlexNet is widely credited with igniting the deep learning revolution. Its success demonstrated the effectiveness of deep neural networks trained on GPUs, leading to rapid progress across multiple domains of artificial intelligence beyond computer vision. The techniques and momentum generated by AlexNet helped shape the development of modern natural language processing models, including large-scale transformer-based models such as BERT and GPT, which power tools like ChatGPT.
ITools Resourceome
iTools is a distributed infrastructure for managing, discovery, comparison and integration of computational biology resources. iTools employs Biositemap technology to retrieve and service meta-data about diverse bioinformatics data services, tools, and web-services. iTools is developed by the National Centers for Biomedical Computing as part of the NIH Road Map Initiative.
Turing test
The Turing test, originally called the imitation game by Alan Turing in 1949, is a test of a machine's ability to exhibit intelligent behaviour equivalent to that of a human. In the test, a human evaluator judges a text transcript of a natural-language conversation between a human and a machine. The evaluator tries to identify the machine, and the machine passes if the evaluator cannot reliably tell them apart. The results would not depend on the machine's ability to answer questions correctly, only on how closely its answers resembled those of a human. Since the Turing test is a test of indistinguishability in performance capacity, the verbal version generalizes naturally to all of human performance capacity, verbal as well as nonverbal (robotic). The test was introduced by Turing in his 1950 paper "Computing Machinery and Intelligence" while working at the University of Manchester. It opens with the words: "I propose to consider the question, 'Can machines think?'." Because "thinking" is difficult to define, Turing chooses to "replace the question by another, which is closely related to it and is expressed in relatively unambiguous words". Turing describes the new form of the problem in terms of a three-person party game called the "imitation game", in which an interrogator asks questions of a man and a woman in another room in order to determine the correct sex of the two players. Turing's new question is: "Are there imaginable digital computers which would do well in the imitation game?" This question, Turing believed, was one that could actually be answered. In the remainder of the paper, he argued against the major objections to the proposition that "machines can think". Since Turing introduced his test, it has been highly influential in the philosophy of artificial intelligence, resulting in substantial discussion and controversy, as well as criticism from philosophers like John Searle, who argue against the test's ability to detect consciousness. == History == === Philosophical background === The question of whether it is possible for machines to think has a long history, which is firmly entrenched in the distinction between dualist and materialist views of the mind. René Descartes prefigures aspects of the Turing test in his 1637 Discourse on the Method when he writes: [H]ow many different automata or moving machines could be made by the industry of man ... For we can easily understand a machine's being constituted so that it can utter words, and even emit some responses to action on it of a corporeal kind, which brings about a change in its organs; for instance, if touched in a particular part it may ask what we wish to say to it; if in another part it may exclaim that it is being hurt, and so on. But it never happens that it arranges its speech in various ways, in order to reply appropriately to everything that may be said in its presence, as even the lowest type of man can do. Here Descartes notes that automata are capable of responding to human interactions but argues that such automata cannot respond appropriately to things said in their presence in the way that any human can. Descartes therefore prefigures the Turing test by defining the insufficiency of appropriate linguistic response as that which separates the human from the automaton. Descartes fails to consider the possibility that future automata might be able to overcome such insufficiency, and so does not propose the Turing test as such, even if he prefigures its conceptual framework and criterion. Denis Diderot formulates in his 1746 book Pensées philosophiques a Turing-test criterion, though with the important implicit limiting assumption maintained, of the participants being natural living beings, rather than considering created artifacts: If they find a parrot who could answer to everything, I would claim it to be an intelligent being without hesitation. This does not mean he agrees with this, but that it was already a common argument of materialists at that time. According to dualism, the mind is non-physical (or, at the very least, has non-physical properties) and, therefore, cannot be explained in purely physical terms. According to materialism, the mind can be explained physically, which leaves open the possibility of minds that are produced artificially. In 1936, philosopher Alfred Ayer considered the standard philosophical question of other minds: how do we know that other people have the same conscious experiences that we do? In his book, Language, Truth and Logic, Ayer suggested a protocol to distinguish between a conscious man and an unconscious machine: "The only ground I can have for asserting that an object which appears to be conscious is not really a conscious being, but only a dummy or a machine, is that it fails to satisfy one of the empirical tests by which the presence or absence of consciousness is determined". (This suggestion is very similar to the Turing test, but it is not certain that Ayer's popular philosophical classic was familiar to Turing.) In other words, a thing is not conscious if it fails the consciousness test. === Cultural background === A rudimentary idea of the Turing test appears in the 1726 novel Gulliver's Travels by Jonathan Swift. When Gulliver is brought before the king of Brobdingnag, the king thinks at first that Gulliver might be a "a piece of clock-work (which is in that country arrived to a very great perfection) contrived by some ingenious artist". Even when he hears Gulliver speaking, the king still doubts whether Gulliver was taught "a set of words" to make him "sell at a better price". Gulliver tells that only after "he put several other questions to me, and still received rational answers" the king became satisfied that Gulliver was not a machine. Tests where a human judges whether a computer or an alien is intelligent were an established convention in science fiction by the 1940s, and it is likely that Turing would have been aware of these. Stanley G. Weinbaum's "A Martian Odyssey" (1934) provides an example of how nuanced such tests could be. Earlier examples of machines or automatons attempting to pass as human include the Ancient Greek myth of Pygmalion who creates a sculpture of a woman that is animated by Aphrodite, Carlo Collodi's novel The Adventures of Pinocchio, about a puppet who wants to become a real boy, and E. T. A. Hoffmann's 1816 story "The Sandman," where the protagonist falls in love with an automaton. In all these examples, people are fooled by artificial beings that—up to a point—pass as human. === Alan Turing and the imitation game === Researchers in the United Kingdom had been exploring "machine intelligence" for up to ten years prior to the founding of the field of artificial intelligence (AI) research in 1956. It was a common topic among the members of the Ratio Club, an informal group of British cybernetics and electronics researchers that included Alan Turing. Turing, in particular, had been running the notion of machine intelligence since at least 1941 and one of the earliest-known mentions of "computer intelligence" was made by him in 1947. In Turing's report, "Intelligent Machinery," he investigated "the question of whether or not it is possible for machinery to show intelligent behaviour" and, as part of that investigation, proposed what may be considered the forerunner to his later tests: It is not difficult to devise a paper machine which will play a not very bad game of chess. Now get three men A, B and C as subjects for the experiment. A and C are to be rather poor chess players, B is the operator who works the paper machine. ... Two rooms are used with some arrangement for communicating moves, and a game is played between C and either A or the paper machine. C may find it quite difficult to tell which he is playing. "Computing Machinery and Intelligence" (1950) was the first published paper by Turing to focus exclusively on machine intelligence. Turing begins the 1950 paper with the claim, "I propose to consider the question 'Can machines think?'" As he highlights, the traditional approach to such a question is to start with definitions, defining both the terms "machine" and "think". Turing chooses not to do so; instead, he replaces the question with a new one, "which is closely related to it and is expressed in relatively unambiguous words". In essence he proposes to change the question from "Can machines think?" to "Can machines do what we (as thinking entities) can do?" The advantage of the new question, Turing argues, is that it draws "a fairly sharp line between the physical and intellectual capacities of a man". To demonstrate this approach Turing proposes a test inspired by a party game, known as the "imitation game", in which a man and a woman go into separate rooms and guests try to tell them apart by writing a series of questions and reading the typewritten answers sent back. In this game, both the man and the woman aim to convince the guests that they ar
Simulation noise
Simulation noise is a function that creates a divergence-free vector field. This signal can be used in artistic simulations for the purpose of increasing the perception of extra detail. The function can be calculated in three dimensions by dividing the space into a regular lattice grid. With each edge is associated a random value, indicating a rotational component of material revolving around the edge. By following rotating material into and out of faces, one can quickly sum the flux passing through each face of the lattice. Flux values at lattice faces are then interpolated to create a field value for all positions. Perlin noise is the earliest form of lattice noise, which has become very popular in computer graphics. Perlin Noise is not suited for simulation because it is not divergence-free. Noises based on lattices, such as simulation noise and Perlin noise, are often calculated at different frequencies and summed together to form band-limited fractal signals. Other approaches developed later that use vector calculus identities to produce divergence free fields, such as "Curl-Noise" as suggested by Rook Bridson, and "Divergence-Free Noise" due to Ivan DeWolf. These often require calculation of lattice noise gradients, which sometimes are not readily available. A naive implementation would call a lattice noise function several times to calculate its gradient, resulting in more computation than is strictly necessary. Unlike these noises, simulation noise has a geometric rationale in addition to its mathematical properties. It simulates vortices scattered in space, to produce its pleasing aesthetic. == Curl noise == The vector field is created as follows, for every point (x,y,z) in the space a vector field G is created, every component x, y and z of the vector field (Gx, Gy, Gz) is defined by a 3D perlin or simplex noise function with x, y and z as parameters. The partial derivative of Gx, Gy, and Gz respect to x, y and z is obtained with the gradient of the perlin or simplex noise by finite differences of implicit calculation inside the simplex noise. The partial derivatives are used to calculate F as the curl of G given by F = ( ∂ G z ∂ y − ∂ G y ∂ z , ∂ G x ∂ z − ∂ G z ∂ x , ∂ G y ∂ x − ∂ G x ∂ y ) {\displaystyle F=({\frac {\partial Gz}{\partial y}}-{\frac {\partial Gy}{\partial z}},{\frac {\partial Gx}{\partial z}}-{\frac {\partial Gz}{\partial x}},{\frac {\partial Gy}{\partial x}}-{\frac {\partial Gx}{\partial y}})} == Bitangent noise == This method is based in the fact that the curl of the gradient of scalar field is zero and the identity that expand the divergence of a cross product of two vectors A and B as the difference of the dot products of each vector with the curl of the other: ∇ × ( ∇ φ ) = 0 . {\displaystyle \nabla \times (\nabla \varphi )=\mathbf {0} .} ∇ ⋅ ( A × B ) = ( ∇ × A ) ⋅ B − A ⋅ ( ∇ × B ) {\displaystyle \nabla \cdot (\mathbf {A} \times \mathbf {B} )=\ (\nabla {\times }\mathbf {A} )\cdot \mathbf {B} \,-\,\mathbf {A} \cdot (\nabla {\times }\mathbf {B} )} which means that if the curl of both vector fields is zero then the divergence of the product of two vectors that are the gradients of scalar fields is zero too. This result in a divergence free vector field by construction only calling two noise functions to create the scalar fields. The vector field es created as follows, two scalar fields are calculated ϕ {\displaystyle \phi } and ψ {\displaystyle \psi } using 3D perlin or simplex noise functions, then the gradients A and B of each of this fields is calculated, the cross product of A and B gives a divergence free vector field. == Signed distance noise == The vector field is created based on a closed and differentiable implicit surface S = F(x,y,z) = 0. For every point in the space, frequently outside or near the surface, we get a vector g that is normal to the surface, this is the gradient of S or the partial derivatives respect to x, y and z, this vector is not unitary, but we can get a unitary normal n by dividing each component of the point by the magnitude of the gradient g. Outside of the surface all these normals point away from the surface. g = ∇ F ( x , y , z ) = ( ∂ F ∂ x , ∂ F ∂ y , ∂ F ∂ z ) {\displaystyle g=\nabla F(x,y,z)=\left({\frac {\partial F}{\partial x}},{\frac {\partial F}{\partial y}},{\frac {\partial F}{\partial z}}\right)} n = g ( x , y , z ) ‖ ∇ F ( x , y , z ) ‖ {\displaystyle \mathbf {n} ={\frac {g(x,y,z)}{\|\nabla F(x,y,z)\|}}} ‖ ∇ F ( x , y , z ) ‖ = ( ∂ F ∂ x ) 2 + ( ∂ F ∂ y ) 2 + ( ∂ F ∂ z ) 2 {\displaystyle \|\nabla F(x,y,z)\|={\sqrt {\left({\frac {\partial F}{\partial x}}\right)^{2}+\left({\frac {\partial F}{\partial y}}\right)^{2}+\left({\frac {\partial F}{\partial z}}\right)^{2}}}} Afterwards we calculate a scalar value p for that point in the space using a 3D perlin or simplex noise function. Now we create a vector field V = pn pointing outside of the surface. The curl of this vector field gives the direction in every point in the space where the particles should move. S D N = ( ∂ V z ∂ y − ∂ V y ∂ z , ∂ V x ∂ z − ∂ V z ∂ x , ∂ V y ∂ x − ∂ V x ∂ y ) {\displaystyle SDN=({\frac {\partial Vz}{\partial y}}-{\frac {\partial Vy}{\partial z}},{\frac {\partial Vx}{\partial z}}-{\frac {\partial Vz}{\partial x}},{\frac {\partial Vy}{\partial x}}-{\frac {\partial Vx}{\partial y}})} By construction this vector SDN will point in a tangent direction to an isosurface at the level of the signed distance to the original surface and can be used to confine the movements of the particles to stay in that surface.
Blockhead (thought experiment)
Blockhead is a theoretical computer system invented as part of a thought experiment by philosopher Ned Block, which appeared in a paper titled "Psychologism and Behaviorism". Block did not personally name the computer in the paper. == Overview == In "Psychologism and Behaviorism", Block argues that the internal mechanism of a system is important in determining whether that system is intelligent and claims to show that a non-intelligent system could pass the Turing test. Block asks the reader to imagine a conversation lasting any given amount of time. He states that given the nature of language, there are a finite number of syntactically and grammatically correct sentences that can be used to start a conversation. Consequently, there is a limit to how many "sensible" responses can be made to the first sentence, then to the second sentence, and so on until the conversation ends. Block then asks the reader to imagine a computer which had been programmed with all the sentences in theory, if not in practice. Block argues that such a machine could continue a conversation with a person on any topic because the computer would be programmed with every sentence that it was possible to use so the computer would be able to pass the Turing test despite the fact that—according to Block—it was not intelligent. Block says that this does not show that there is only one correct internal structure for generating intelligence but simply that some internal structures do not generate intelligence. The argument is related to John Searle's Chinese room.