text:
This lesson is in the early stages of development (Alpha version)

# Anatomy of a NIfTI

## Overview

Teaching: 20 min
Exercises: 5 min
Questions
Objectives
• Introduce Python data type

• Load a NIfTI file into Python and understand how data is stored

• View and manipulate image data

In the last lesson, we introduced the NIfTI. NIfTI is one of the most ubiquitous file formats for storing neuroimaging data. We’ll cover a few details to get started working with them. If you’re interested in learning more about NIfTI images, we highly recommend this blog post about the NIfTI format.

NiBabel is a Python package for reading and writing neuroimaging data. To learn more about how NiBabel handles NIfTIs, check out the Working with NIfTI images page of the NiBabel documentation.

First, use the load() function to create a NiBabel image object from a NIfTI file. We’ll load in an example T1w image from the zip file we just downloaded.

Loading in a NIfTI file with nibabel gives us a special type of data object which encodes all the information in the file. Each bit of information is called an attribute in Python’s terminology. To see all of these attributes, type t1_img. and Tab.

There are three main attributes that we’ll discuss today:

t1_hdr is a Python dictionary. Dictionaries are containers that hold pairs of objects - keys and values. Let’s take a look at all of the keys. Similar to t1_img in which attributes can be accessed by typing t1_img. and hitting Tab, you can do the same with t1_hdr. In particular, we’ll be using a method belonging to t1_hdr that will allow you to view the keys associated with it.

Notice that methods require you to include () at the end of them whereas attributes do not. The key difference between a method and an attribute is:

Attributes are stored values kept within an object
Methods are processes that we can run using the object. Usually a method takes attributes, performs an operation on them, then returns it for you to use.

When you type in t1_img. followed by Tab, you’ll see that attributes are highlighted in orange and methods highlighted in blue .

The output above is a list of keys you can use from t1_hdr to access values. We can access the value stored by a given key by typing:

t1_hdr[‘']

EXERCISE: Extract the value of pixdim from t1_hdr

### 2. Data

As you’ve seen above, the header contains useful information that gives us information about the properties (metadata) associated with the MR data we’ve loaded in. Now we’ll move in to loading the actual image data itself. We can achieve this by using the method called t1_img.get_fdata().

What type of data is this exactly? We can determine this by calling the type() function on t1_data.

The data is a multidimensional array representing the image data. In Python, an array is used to store lists of numerical data into something like a table.

EXERCISE: Let’s check out some attributes of the array. How can we see the number of dimensions in the t1_data array? What about the how big each dimension is (shape)? Once again, all of the attributes of the array can be seen by typing t1_data. and Tab.

t1_data contains 3 dimensions. You can think of the data as a 3D version of a picture (more accurately, a volume).

While typical 2D pictures are made out of squares called pixels, a 3D MR image is made up of 3D cubes called voxels.

The 3 numbers given here represent the number of values along a respective dimension (x,y,z). This brain was scanned in 57 slices with a resolution of 67 x 56 voxels per slice. That means there are: $$x * y * z = value$$$$57 * 67 * 56 = 213864$$

voxels in total!

Let’s see the type of data inside of the array.

This tells us that each element in the array (or voxel) is a floating-point number. The data type of an image controls the range of possible intensities. As the number of possible values increases, the amount of space the image takes up in memory also increases.

For our data, the range of intensity values goes from 0 (black) to more positive digits (whiter).

How do we examine what value a particular voxel is? We can inspect the value of a voxel by selecting an index as follows:

data[x,y,z]

So for example we can inspect a voxel at coordinates (10,20,3) by doing the following:

NOTE: Python uses zero-based indexing. The first item in the array is item 0. The second item is item 1, the third is item 2, etc.

This yields a single value representing the intensity of the signal at a particular voxel! Next we’ll see how to not just pull one voxel but a slice or an array of voxels for visualization and analysis!

## Working with Image Data

Slicing does exactly what it seems to imply. Giving our 3D volume, we pull out a 2D slice of our data. Here’s an example of slicing from left to right (sagittal slicing):

This gif is a series of 2D images or slices moving from left to right.

Let’s pull the 10th slice in the x axis.

This is similar to the indexing we did before to pull out a single voxel. However, instead of providing a value for each axis, the : indicates that we want to grab all values from that particular axis.

EXERCISE: Now try selecting the 20th slice from the y axis.

Finally try grabbing the 3rd slice from the z axis.

We’ve been slicing and dicing brain images but we have no idea what they look like! In the next section we’ll show you how you can visualize brain slices!

## Visualizing

We previously inspected the signal intensity of the voxel at coordinates (10,20,3). Let’s see what out data looks like when we slice it at this location. We’ve already indexed the data at each x, y, and z axis. Let’s use matplotlib.

Now, we’re going to step away from discussing our data and talk about the final important attribute of a NIfTI.

### 3. Affine: tells the position of the image array data in a reference space

The final important piece of metadata associated with an image file is the affine matrix. Below is the affine matrix for our data.

To explain this concept, recall that we referred to coordinates in our data as (x,y,z) coordinates such that:

x is the first dimension of t1_data
y is the second dimension of t1_data
z is the third dimension of t1_data

Although this tells us how to access our data in terms of voxels in a 3D volume, it doesn’t tell us much about the actual dimensions in our data (centimetres, right or left, up or down, back or front). The affine matrix allows us to translate between voxel coordinates (x,y,z) and world space coordinates in (left/right,bottom/top,back/front). An important thing to note is that in reality in which order you have:

left/right
bottom/top
back/front

Depends on how you’ve constructed the affine matrix, but for the data we’re dealing with it always refers to:

Right
Anterior
Superior

Applying the affine matrix (t1_affine) is done through using a linear map (matrix multiplication) on voxel coordinates (defined in t1_data).

The concept of an affine matrix may seem confusing at first but an example might help gain an intuition:

Suppose we have two voxels located at the the following coordinates: $$(15,2,90)$$$$(64,100,2)$$

And we wanted to know what the distances between these two voxels are in terms of real world distances (millimetres). This information cannot be derived from using voxel coordinates so we turn to the affine matrix.

Now, the affine matrix we’ll be using happens to be encoded in RAS. That means once we apply the matrix our coordinates are as follows: $$(\text{Right},\text{Anterior},\text{Superior})$$

So increasing a coordinate value in the first dimension corresponds to moving to the right of the person being scanned.

Applying our affine matrix yields the following coordinates: $$(90.23,0.2,2.15)$$$$(10.25,30.5,9.2)$$

This means that:

Voxel 1 is $90.23-10.25= 79.98$ in the R axis. Positive values mean move right
Voxel 1 is $0.2-30.5= -30.3$ in the A axis. Negative values mean move posterior
Voxel 1 is $2.15-9.2= -7.05$ in the S axis. Negatve values mean move inferior

This covers the basics of how NIfTI data and metadata are stored and organized in the context of Python. In the next segment we’ll talk a bit about an increasingly important component of MR data analysis - data organization. This is a key component to reproducible analysis and so we’ll spend a bit of time here.

Teaching: 20 min
Exercises: 5 min
Questions
Objectives


text:
Learn

A finite sequence is exactly what it sounds like - an ordered list of numbers that is finite, meaning it has a stopping value. An extensive, uncountable finite sequence also has a stopping value, but it is generally too cumbersome to be practical.

An infinite sequence is an ordered list of numbers, the count of which has no stopping value. Some infinite sequences converge to a desired value and provide an estimation of that value. The sequence of factorials starts with 0!, 1!, 2!, 3!, 4!,… and evaluates to: 1, 1, 2, 6, 12, … However, if we sum up the inverses of the sequence of factorials we get this:

$\frac{1}{1} + \frac{1}{1} + \frac{1}{2} + \frac{1}{6} + \frac{1}{12} + ... \approx e$

where e is the natural root = 2.71828… of natural logarithms. The three dots “…” mean the number has no end.

### Instructions

1.

Is the decimal portion of the value of pi (3.14159265…) a sequence?

Assign "yes" or "no" to checkpoint_1.

2.

Is 1, 2, 4, 8, 16, 32, … a finite sequence?

Assign "yes" or "no" to checkpoint_2.

format: plain


text:
axiom-developer
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

## [Axiom-developer] [RationalInterpolation]

 From: kratt6 Subject: [Axiom-developer] [RationalInterpolation] Date: Tue, 22 Mar 2005 04:44:32 -0600

Changes
http://page.axiom-developer.org/zope/mathaction/RationalInterpolation/diff
--

??changed:
-The package below implements rational interpolation.
-
-It requires the following previously compiled package:
Introduction

This file contains an implementation of rational interpolation, where the data
points are element of any integral domain.

Questions and Outlook

- Maybe this file should be joined with pinterp.spad, where polynomial
Lagrange interpolation is implemented. This version parallels the structure
of pinterp.spad closely. This also answers comments and questions from
wyscc. He remarked

- Abbreviations for a constructor should be limited to 7 letters (not 8).
The system occasionally adds the 8th character to a package for internal
use.

- Function names begin with a lower case, so RationalInterpolation should
be rationalInterpolation, or better, rationalInterpolate.

- Regarding the types I used for the values, wyscc remarked

- If we are doing a rational interpolation, presumably the values are
rational, so it does not make sense to require the $y$-coordinates of
inputs be integral. On the other hand, as in the above example, if one
uses 'FRAC INT', problems can arise when this package is combined with
other packages that constructs the quotient field of the parameter domain
'F' because Axiom does not like constructing 'FRAC FRAC INT'.

Note however, that the package would rather construct the type 'FRAC SUP
FRAC INT', so this problem should not occur. Moreover, there are situations
- for example in the package [Guess], where we want to interpolate values
from an IntegralDomain. Of course we could first convert them to the
quotient field, however, the current approach seems more natural to me.

- Finally, wyscc asked:
If p(xx) = interpolate(lx, ly, m, k), what is the purpose of
elt(px, qx) = p(qx), the composition of p(xx) and
qx, especially when qx is from FRAC UP(xx,
F) instead of from just F? and why is this function
(the composition) also called interpolate?

I do not really know - apart from a very superficial level: Clearly, the
second function was intended to let the user easily plug in values into the
interpolated function. I don't find this sensible and I would be happy to
change it. Indeed, this would also get rid of the first parameter to
'RINTERP', which is quite a nuisance.

I think we should agree on a general interface for interpolation
algorithms, and mark 'PINTERP' as obsolete. By the way, it seems that
'RINTERP' is faster, too.

- There are probably better ways to implement rational interpolation. Maybe
http://www.cs.ucsb.edu/~omer/personal/abstracts/rational.html
contains something useful, but I don't know.

- For those who speak german,
http://www.num.math.uni-goettingen.de/schaback/teaching/numath.ps
contains quite a bit of information.

- This implementation of rational interpolation neither takes care of
unattainable points, nor does it check whether the values of the
$x$-coordinates are all distinct.

- Comments welcome!

??changed:
-)lib RINTERPA
)abbrev package RINTERPA RationalInterpolationAlgorithms
++ Description:
++ This package exports rational interpolation algorithms
RationalInterpolationAlgorithms(F, P): Cat == Body   where
F: IntegralDomain
P: UnivariatePolynomialCategory(F)
Cat == with
RationalInterpolation: (List F, List F, NonNegativeInteger,
NonNegativeInteger)
-> Fraction P
+++ We assume that the elements of the first list are all distinct.
+++ If they are not, division by zero might occur.

Body == add
RationalInterpolation(xlist, ylist, m, k) ==
#xlist ^= #ylist =>
error "Different number of points and values."
#xlist ^= m+k+1 =>
error "wrong number of points"
tempvec: List F := [1 for i in 1..(m+k+1)]

collist: List List F := cons(tempvec,
[(tempvec := [tempvec.i * xlist.i _
for i in 1..(m+k+1)]) _
for j in 1..max(m, k)])

collist := append([collist.j for j in 1..(m+1)], _
[[- collist.j.i * ylist.i for i in 1..(m+k+1)] _
for j in 1..(k+1)])
resspace: List Vector F := nullSpace((transpose matrix collist) _
::Matrix F)
reslist: List List P := _
[[monomial((resspace.1).(i+1), i) for i in 0..m], _
[monomial((resspace.1).(i+m+2), i) for i in 0..k]]

reduce((_+), reslist.1)/reduce((_+), reslist.2)

??changed:
-Next PolynomialCommonDenominator
-
-Example (added by wyscc):

First we check whether we have the right number of points and values. Clearly
the number of points and the number of values must be identical. Note that we
want to determine the numerator and denominator polynomials only up to a
factor. Thus, we want to determine $m+k+1$ coefficients, where $m$ is the degree
of the polynomial in the numerator and $k$ is the degree of the polynomial in
the denominator.

In fact, we could also leave - for example - $k$ unspecified and determine it
as $k=\#xlist-m-1$: I don't know whether this would be better.

The next step is to set up the matrix. Suppose that our numerator polynomial is
$p(x)=a_0+a_1x+\dots+a_mx^m$ and that our denominator polynomial is
$q(x)=b_0+b_1x+\dots+b_mx^m$. Then we have the following equations, writing $n$
for $m+k+1$:

\begin{eqnarray*}
p(x_1)-y_1q(x_1)&=a_0+a_1x_1+\dots +a_mx_1^m-y_1(b_0+b_1x_1+\dots
+b_kx_1^k)=0\\
p(x_2)-y_2q(x_2)&=a_0+a_1x_2+\dots +a_mx_2^m-y_2(b_0+b_1x_2+\dots
+b_kx_2^k)=0\\
&\;\;\vdots\\
p(x_n)-y_nq(x_n)&=a_0+a_1x_n+\dots +a_mx_n^m-y_n(b_0+b_1x_n+\dots +b_kx_n^k)=0
\end{eqnarray*}

This can be written as
\begin{equation*}
\begin{bmatrix}
1&x_1&\dots&x_1^m&-y_1&-y_1x_1&\dots&-y_1x_1^k\\
1&x_2&\dots&x_2^m&-y_2&-y_2x_2&\dots&-y_2x_2^k\\
\vdots\\
1&x_n&\dots&x_n^m&-y_n&-y_nx_n&\dots&-y_nx_2^k
\end{bmatrix}
\begin{bmatrix}
a_0\\a_1\\\vdots\\a_m\\b_0\\b_1\\\vdots\\b_k
\end{bmatrix}=\mathbf 0
\end{equation*}

We generate this matrix columnwise, then we can solve the system using
'nullSpace'.

Note that it may happen that the system has several solutions. In this case,
some of the data points may not be interpolated correctly. However, the
solution is often still useful, thus we do not signal an error.

Since all the solutions of 'nullSpace' will be equivalent, we can always
simply take the first one. Finally, we return the rational function.

Examples

To conclude we present some examples. To begin with, the following
interpolation
illustrates the concept of unattainable points:

??changed:
-f(x)== (x^3+5*x-3)/(x^2-3)
-f(x)
-xlist:List FRAC INT :=[1/2, 4, 1/6, 8, 1/10, 12]
-ylist :=[f(x) for x in xlist]
interpolate([q,q^2,q^3],[0,x^1,x^2],0,2)$RINTERP(qn, FRAC POLY INT) ++added: \begin{axiom} f(x) == (x^3+5*x-3)/(x^2-3) xlist := [1/2, 4, 1/6, 8, 1/10, 12] ylist := [f(x) for x in xlist] interpolate(xlist, ylist, 3, 2)$RINTERP('x, FRAC INT)
interpolate(1/6::FRAC UP(x,FRAC INT), xlist, ylist, 3, 2)$RINTERP('x,FRAC INT) \end{axiom} ??changed: -dom:=DMP([z],INT); -g:FRAC dom -> FRAC dom dom := DMP([z],INT); g: FRAC dom -> FRAC dom; ??changed: -xxlist:List FRAC dom:=[1/(2*z), 4*z, 1/(6*z), 8*z, 1/(10*z), 12*z] -yylist:=[g(x) for x in xxlist] ---RationalInterpolation(xxlist, yylist, 3::NNI, 2::NNI)$RINTERPA(FRAC dom,
UP(x, FRAC dom))
-\end{axiom}
-
-\begin{axiom}
-interpolate(xlist, ylist, 3, 2)$RINTERP('x, FRAC INT) -interpolate(1/6::FRAC UP(x,FRAC INT), xlist, ylist, 3,2)$RINTERP('x,FRAC INT)
xxlist: List FRAC dom := [1/(2*z), 4*z, 1/(6*z), 8*z, 1/(10*z), 12*z]
yylist := [g(x) for x in xxlist]

--removed:
-
-Question: If p(xx) = interpolate(lx, ly, m, k), what is the
purpose of
-elt(px, qx) = p(qx), the composition of p(xx) and
qx, especially when qx is from FRAC UP(xx,
F) instead of from just F? and why is this function (the
composition) also called interpolate?
-

--
forwarded from http://page.axiom-developer.org/zope/mathaction/address@hidden

reply via email to

 [Prev in Thread] Current Thread [Next in Thread]


text:
# Integrated Boltzman equation for dark matter

1. May 29, 2015

### karlzr

In Dodelson's book, the equation for a scattering process $a + b \Leftrightarrow c + d$ is given as
$a^{-3} \frac{ d (n_a a^3)}{d t}=-n^{\text{eq}}_a n^{\text{eq}}_b<\sigma v>(\frac{n_a n_b}{n^{\text{eq}}_a n^{\text{eq}}_b} - \frac{n_c n_d}{n^{\text{eq}}_c n^{\text{eq}}_d}) = - <\sigma v>(n_a n_b - \frac{n^{\text{eq}}_a n^{\text{eq}}_b}{n^{\text{eq}}_c n^{\text{eq}}_d}n_c n_d)$
with $n_i = g_i e^{\mu_i/T}\int \frac{d^3p}{(2\pi)^3}e^{-E_i/T}$ and the equilibrium number density $n^{\text{eq}}_i = g_i \int \frac{d^3p}{(2\pi)^3}e^{-E_i/T}$.
(1)Why is this $n^{\text{eq}}_i$ the equilibrum number density since we don't necessarily have $\mu=0$ in equilibrium: $n_i=n^{\text{eq}}_i$ ?
(2) In papers about dark matter, it is very often to see $a^{-3} \frac{ d (n_a a^3)}{d t}=-<\sigma v>(n_a n_b - n^{\text{eq}}_a n^{\text{eq}}_b)$. This is true only if both $c$ and $d$ are in equilibrium, right? I have this question because in coannihilation dark matter hep-ph/9704361, the contribution from $\chi_i + X \Leftrightarrow \chi_j + Y$ is said to be $\propto (n_i n_X - n^{\text{eq}}_i n^{\text{eq}}_X)$ when both $\chi_i$ and $\chi_j$ are freezing out. I don't get it because $\chi_j$ isn't in equilibrium.

2. Jun 3, 2015


text:
# Welcome to the Guide for Physics Lists!

Scope of this Manual

This guide is a description of the physics lists class which is one of the mandatory user classes for a Geant4 application. For the most part the “reference” physic lists included in the source distribution are described here as well the modularity and electronic options. Some use cases and areas of application are also described.

## Status of this Document

Guide describing Physics Lists and their possible application in more detail.

• Rev 1.0: First sphinx version implemented for Geant4 Release 10.4, 8th Dec 2017

• Rev 2.0: Updates and fixes in documentatio for Geant4 Release 10.4, 15th May 2018

• Rev 3.0: Geant4 Release 10.5, 11th December 2018

• Rev 3.1: Geant4 Updates and fixes - especially to search functionality, 5th March 2019

• Rev 4.0: Geant4 Release 10.6, 6th December 2019


text:
# How to create an augmented reality application using ARCore

Original author: Ayusch Jain
• Transfer

In this guide you will learn how to add 3D models to the real world. The ARCore library from Google allows you to add full-fledged 3D models to a 2D image (picture or video).

You need to provide the system with a kind of reference image that ARCore will look for in the real world in order to add a 3D model to the image. Augmented reality is already widely used, for example, in books, newspapers, magazines, etc.

Before diving into this tutorial, you should read the previous two articles on this topic, which will introduce you to the main AR-terms:

## What are augmented reality images?

According to developer documentation , ARCore's augmented reality images allow you to create augmented reality applications that can “animate” 2D images, such as posters or product packaging.

You load some reference images into ARCore, and he then tells you about their detection during an AR session, for example, during a video shoot. And this information is used to position the 3D model on a 2D image.

## Limitations on the use of augmented reality images

Here are some limitations you may encounter when using augmented reality images:

• ARCore can only process up to 20 reference images at a time.
• The physical plane in the real world should be flat, and its area should be more than 15 cm x 15 cm.
• ARCore cannot track moving images and objects.

## Choosing the right reference image

Here are some tips for choosing a good reference image for ARCore:

• Augmented reality images support PNG, JPEG and JPG formats.
• It doesn’t matter if there is a color image or black and white, the main thing is that it has high contrast.
• Image resolution should be at least 300 x 300 pixels.
• Using high resolution images does not mean improved performance.
• Images with repeating patterns (such as patterns or peas) should be avoided.
• Use the arcoreimg tool to evaluate how suitable your image is for work. A score of at least 75 points is recommended.

## How to use the arcoreimg tool:

• Unzip the file to any location.
• In the extracted folder, go to the path tools> arcoreimg> windows (even if you have Linux or macOS).
• Open a command prompt in this directory.
• And enter this command:

arcoreimg.exe eval-img --input_image_path=dog.png

Replace dog.png with the full path to your image.

## Getting started with the Augmented Reality application

Now that you have read ARCore and selected a good image with a rating of 75+, it's time to start writing the application code.

### Creating a fragment

We will create a snippet and add it to our Activity. Create a class with the name CustomArFragmentand inherit it from ArFragment. Here is the code for CustomArFragment:

package com.ayusch.augmentedimages;
import android.util.Log;
publicclassCustomArFragmentextendsArFragment{
@Overrideprotected Config getSessionConfiguration(Session session){
getPlaneDiscoveryController().setInstructionView(null);
Config config = new Config(session);
config.setUpdateMode(Config.UpdateMode.LATEST_CAMERA_IMAGE);
session.configure(config);
getArSceneView().setupSession(session);
return config;
}
}

First of all, we disable plane detection. By doing this, we remove the hand icon from the screen, which appears immediately after fragment initialization and tells the user to move his smartphone to search for the plane. We do not need this anymore, since we find not a random plane, but a specific image.

Then we set the update mode for the session LATEST_CAMERA_IMAGE. This ensures that we will find out about image updates every time the camera frame is updated.

### Image Database Setup

Add the selected reference image (which you want to find in the physical world) to the assets folder (create it if it does not already exist). Now we can add images to our database.

We will create this database as soon as the fragment is created. In the logs we display the result of this operation:

if ((((MainActivity) getActivity()).setupAugmentedImagesDb(config, session))) {
Log.d("SetupAugImgDb", "Success");
} else {
Log.e("SetupAugImgDb","Faliure setting up db");
}

Here is what it will look like CustomArFragment:

package com.ayusch.augmentedimages;
import android.util.Log;
publicclassCustomArFragmentextendsArFragment{
@Overrideprotected Config getSessionConfiguration(Session session){
getPlaneDiscoveryController().setInstructionView(null);
Config config = new Config(session);
config.setUpdateMode(Config.UpdateMode.LATEST_CAMERA_IMAGE);
session.configure(config);
getArSceneView().setupSession(session);
if ((((MainActivity) getActivity()).setupAugmentedImagesDb(config, session))) {
Log.d("SetupAugImgDb", "Success");
} else {
Log.e("SetupAugImgDb","Faliure setting up db");
}
return config;
}
}

Soon we will add a method setupAugmentedImagesDbto MainActivity. Now let's add CustomArFragmentto our activity_main.xml:

<?xml version="1.0" encoding="utf-8"?><android.support.constraint.ConstraintLayoutxmlns:android="http://schemas.android.com/apk/res/android"xmlns:app="http://schemas.android.com/apk/res-auto"xmlns:tools="http://schemas.android.com/tools"android:layout_width="match_parent"android:layout_height="match_parent"tools:context=".MainActivity"><fragmentandroid:id="@+id/sceneform_fragment"android:name="com.ayusch.augmentedimages.CustomArFragment"android:layout_width="match_parent"android:layout_height="match_parent" /></android.support.constraint.ConstraintLayout>

Now we will set up our image database, find the reference image in the real world and add a 3D model to the image.

Let's start by setting up our database. Create a public method setupAugmentedImagesDbin the class MainActivity:

publicbooleansetupAugmentedImagesDb(Config config, Session session){
AugmentedImageDatabase augmentedImageDatabase;
if (bitmap == null) {
returnfalse;
}
augmentedImageDatabase = new AugmentedImageDatabase(session);
config.setAugmentedImageDatabase(augmentedImageDatabase);
returntrue;
}
try (InputStream is = getAssets().open("blanket.jpeg")) {
return BitmapFactory.decodeStream(is);
} catch (IOException e) {
}
returnnull;
}

We also created a method loadAugmentedImagethat loads an image from the resource folder and returns a bitmap image.

At setupAugmentedImagesDbfirst we initialize our database for the current session, and then add the image to the database. We called our image tiger . Then we set this database to the config and return true, reporting that the image has been successfully added.

### Detecting reference images in the real world

Now we will begin to detect our reference images in the real world. To do this, we will create a listener that will be called each time the video frame is updated, and this frame will be analyzed for the presence of the reference image there.

Add this line to the method onCreate()in MainActivity:

arFragment.getArSceneView().getScene().addOnUpdateListener(this::onUpdateFrame);

Now add the method onUpdateFrameto MainActivity:

@RequiresApi(api = Build.VERSION_CODES.N)
privatevoidonUpdateFrame(FrameTime frameTime){
Frame frame = arFragment.getArSceneView().getArFrame();
Collection<AugmentedImage> augmentedImages = frame.getUpdatedTrackables(AugmentedImage.class);
for (AugmentedImage augmentedImage : augmentedImages) {
if (augmentedImage.getTrackingState() == TrackingState.TRACKING) {
placeObject(arFragment, augmentedImage.createAnchor(augmentedImage.getCenterPose()), Uri.parse("Mesh_BengalTiger.sfb"));
}
}
}
}

In the first line we get the frame itself. The frame can be represented as a regular screenshot from the video. If you are familiar with how video works, you know that this is just a collection of images that very quickly replace each other, giving the impression of something moving. We just take one of these pictures.

After we have received the frame, we analyze it for the presence of our reference image on it. We take a list of all the items tracked by ARCore using frame.getUpdatedTrackables. Then we loop through it and check if our tiger image is in the frame .

If a match is found, then we simply take and place the 3D model on top of the detected image.

Note. The flag is shouldAddModelused so that we add a 3D model only once.

### Place the 3D model above the reference image.

Now that we have found our reference image in the real world, we can add a 3D model on top of it. Add methods placeObjectand addNodeToScene:

• placeObject: This method is used to build a rendered object for a given Uri. Once rendering is completed, the object is passed to the method addNodeToScenewhere the object is attached to the node, and this node is placed on the stage.
• addNodeToScene: this method creates a node from the resulting anchor, creates another node to which the rendered object is attached, then adds this node to the anchor node and places it on the scene.

This is how it looks like now MainActivity:

package com.ayusch.augmentedimages;
import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
import android.net.Uri;
import android.os.Build;
import android.support.annotation.RequiresApi;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.widget.Toast;
import java.io.IOException;
import java.io.InputStream;
import java.util.Collection;
publicclassMainActivityextendsAppCompatActivity{
ArFragment arFragment;
@OverrideprotectedvoidonCreate(Bundle savedInstanceState){
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
arFragment = (CustomArFragment) getSupportFragmentManager().findFragmentById(R.id.sceneform_fragment);
arFragment.getPlaneDiscoveryController().hide();
}
@RequiresApi(api = Build.VERSION_CODES.N)
privatevoidplaceObject(ArFragment arFragment, Anchor anchor, Uri uri){
ModelRenderable.builder()
.setSource(arFragment.getContext(), uri)
.build()
.exceptionally(throwable -> {
Toast.makeText(arFragment.getContext(), "Error:" + throwable.getMessage(), Toast.LENGTH_LONG).show();
returnnull;
}
);
}
@RequiresApi(api = Build.VERSION_CODES.N)
privatevoidonUpdateFrame(FrameTime frameTime){
Frame frame = arFragment.getArSceneView().getArFrame();
Collection<AugmentedImage> augmentedImages = frame.getUpdatedTrackables(AugmentedImage.class);
for (AugmentedImage augmentedImage : augmentedImages) {
if (augmentedImage.getTrackingState() == TrackingState.TRACKING) {
placeObject(arFragment, augmentedImage.createAnchor(augmentedImage.getCenterPose()), Uri.parse("Mesh_BengalTiger.sfb"));
}
}
}
}
publicbooleansetupAugmentedImagesDb(Config config, Session session){
AugmentedImageDatabase augmentedImageDatabase;
if (bitmap == null) {
returnfalse;
}
augmentedImageDatabase = new AugmentedImageDatabase(session);
config.setAugmentedImageDatabase(augmentedImageDatabase);
returntrue;
}
try (InputStream is = getAssets().open("blanket.jpeg")) {
return BitmapFactory.decodeStream(is);
} catch (IOException e) {
}
returnnull;
}
privatevoidaddNodeToScene(ArFragment arFragment, Anchor anchor, Renderable renderable){
AnchorNode anchorNode = new AnchorNode(anchor);
TransformableNode node = new TransformableNode(arFragment.getTransformationSystem());
node.setRenderable(renderable);
node.setParent(anchorNode);
}


text:
Warning- a whole lot of text and math speak ahead. Continue at your own risk.

Okay, let’s start with the Fourier Transform. The core idea is that a signal (= sequence of numbers over time) can be decomposed into a sum of sinusoids. To maybe sort of get an intuition for why, think about any point in a two-dimensional plane, such as (3,4), or (17,42). Both of these points, and every other point on the plane, can be represented as a sum of multiples of (1,0) and (0,1):

Notice that the reason you only need to know two things is that there are only two degrees of freedom: how far right or left, and how far up or down. In fact, I can uniquely determine any point in the plane given “any” two properties of that point as long as they are sufficiently not redundant (this collection of “properties” is referred to as a basis). For example, the point $(1,1)$ in Cartesian Coordinates, signifying a horizontal offset of positive one and a negative offset of positive one, can also be denoted as $(\sqrt{2},\frac{\pi}{4})$ in Polar Coordinates, signifying a radial offset of $\sqrt{2}$ and an angular offset from the positive x-axis of $\frac{\pi}{4}$ (radians). This reinterpretation of a unique point in some N-space is called a change of basis. One can think of the Fourier Transform as a type of change of basis.

In order to extend this understanding to signals, you must realize that there are infinitely many degrees of freedom: how big the signal is at the start, how big the signal is one infinitesimal moment later, how big the signal is the moment after that, and so on and so forth. Like we said before, since there are infinitely many degrees of freedom, we can uniquely classify any signal with infinitely many “properties”. It may seem like this doesn’t help at all, but defining the basis as the set of all harmonics of a sine wave has a nice real world analogue in the way we humans perceive sounds. And, as you will see, the cyclic nature of sinusoids also allows for a tangential interpretation.

Side note: if instead you defined the basis as the set of all powers of x, you get the Taylor series.

Congrats, you passed Fourier 101. Onto the main course:

The idea is that a parametric curve in 2-dimensions $f(t) = (a(t),b(t))$ can be just as easily written as a complex function of one variable (ie. a signal) $g(t) = a(t)+b(t)i$, after which I can take the Discrete Fourier Transform (DFT) to get a list of coefficients of the complex exponential basis vectors (by the way, in this context, a function is just a vector whose components are the values of the function at every point). The reason I’m using the DFT instead of the at least three other versions of the Fourier Transform is because it takes a discrete periodic signal in the time domain and returns a discrete periodic signal in the frequency domain. I am not really sure why, and most of the resources online either assume it or are really hand-wavey. What I do know is that a discreteness in one domain causes periodicity in the other, and vice versa. Therefore, since I want discreteness in my frequency domain (ie. a finite number of complex exponentials), I impose periodicity onto my time signal (ie. the parametric curve must be a closed loop). And since I can only get discrete time samples, my frequency domain will be periodic (I think this causes/is caused by/is related to aliasing).

Onto some implementation details. Since the DFT is pretty ubiquitous in many digital applications, it wasn’t too difficult to find a working implementation of it online. First of all, the input time-domain signals are obtained and formatted as a list of list of two elements representing the real and imaginary components. Once the input signals are obtained, they are passed into the dft function, which returns a new list. I adapted the code from the above website which was written in C++ to JavaScript. The site has a pretty easy to follow explanation of the implementation, so I won’t bother to go over it here.

function dft(time) {
var ret = []
var n = time.length
for (var i = 0 ; i < n ; ++i) {
var sreal = 0, simag = 0, angle = 0
for (var j = 0 ; j < n ; ++j) {
angle = tpi * i * j / n; // tpi = 2*Math.PI
sreal +=  time[j][0] * Math.cos(angle) + time[j][1] * Math.sin(angle);
simag += -time[j][0] * Math.sin(angle) + time[j][1] * Math.cos(angle);
}
ret.push([sreal/n,simag/n,i])
}
return ret
}

There is one implementation detail to note, however. Notice that my return type is a list of lists of three elements, not two. In addition to the real and imaginary components of the complex coefficient, I also push on the index, or the frequency value, because later on I sort the list in terms of radius, which mixes up the order.

Now comes the fun part. Here’s the formula for the Inverse DFT (IDFT):

(That’s actually not entirely correct; the IDFT is only defined at the sampled points, but here I’m allowing it to be defined continuously on $% $.)

There are a few other things to realize before moving on:

2. complex multiplication = rotation (ie. the product of two complex numbers is a complex number whose angle is the sum of the two angles and whose magnitude is the product of the two magnitudes)
3. complex exponentials can be interpreted as points around a unit circle.
4. From (2) and (3), it follows that multiplying a complex number by a complex exponential $e^{i\theta}$ is equivalent to rotating the prior by $\theta$

First, take a look at a single term of the sum. Since $X[k]$ is a complex number, the whole term can just be interpreted as a point at $X[k]$ rotating at a constant speed in the counter clockwise direction. Extending this to multiple terms, it turns out that the IDFT is actually just the sum of rotating vectors.

Enter the Ptolemaic planetary system. Basically, this was way back when people still believed that the Earth was at center of the universe, and reasoned the crazy complicated paths of the other celestial bodies by saying that their motion can be described by picturing them as the very end of a long chain of satellites. For a clearer explanation, see this Mathematics StackExchange post (in fact, that post describes much, if not all, of what I try to accomplish in this project).

Now to combine the two ideas, the key is to understand that a satellite’s orbit around another celestial body is simply a rotating vector. If the discourse from the above seven-ish paragraphs is now combined, the conclusion is that any closed path can be drawn by an infinite number of planets orbiting the next in an infinitely long dizzying planetary conga line. Or, for practical purposes, any closed path can be approximated by a finite number of planets (perhaps you can see now why the Ptolemaic planetary system was an absurd argument for the geocentric system).

While the argument was absurd for explaining the motions of the planets in our sky, it’s perfect for drawing pictures with circles. After calculating the coefficients of the complex exponentials, the only thing left was to draw each circle with a radius of that circle’s coefficient, and rotate it with a speed of that circle’s frequency.

for (var i = 0 ; i < keyframes.length-options.compression; ++i ) {
c = Complex.Polar(1,animt/360*tpi*keyframes[i][1])['*'](keyframes[i][0])['*'](Complex(w/2/scale))
circle(ctx, 0, 0, c.abs, 'black', false)
ctx.beginPath()
ctx.moveTo(0,0)
ctx.translate(c.real, c.imag)
ctx.lineTo(0,0)
ctx.stroke()
pctx.translate(c.real, c.imag)
}

I use a complex number library here, but it isn’t strictly necessary, just a convenience. animt is the current time step, and c represents the vector of that given circle at time animt. Afterwards, it’s just a matter of drawing the circle, and translating the canvas so that the origin of the canvas is at the end of the vector of the circle that was just drawn.

After drawing some grid lines and adding some basic GUI, the pretty fun to play with Fourier drawing application is done. If you’re still here, I applaud you for your determination, perserverance, and/or insanity.


text:
# Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

### Jucys-Murphy elements, affine braids and Hilb-knot homology

Algebra & Discrete Mathematics

 Speaker: Alexei Oblomkov Location: 2112 Start time: Mon, Mar 6 2017, 4:10PM

Talk is based on the recent joint preprints with Lev Rozansky. In the talk I will explain an interpretation of the HOMFLY knot homology as space of derived sections of quasi-coherent sheaf on the Hilbert scheme of points on the plane. In particular, the new geometric construction of the finite Hecke category will be explained. The construction allow us relate the knot homology of the closure of a braid and of the closure of the same braid but twisted by Jucys-Murphy element of the braid group. As one of the corollary we get an explicit formula for the knot homology of the torus links confirming earlier conjecture by Gorsky, Negut, Oblomkov, Shende and Rasmussen.


text:
# Abstracts

### Monday, January 30th, 2017

9:30 am10:15 am
Randomness is widely used in various areas of computer science, and many of the applications require uniform, uncorrelated bit. However, most  sources of randomness in nature are defective and at best, only contain some amount of entropy. This leads to the area of randomness extraction, where an extractor is a deterministic procedure to produce pure random bits from a weak source. A central open problem (from the 80's) in this area is to extract from 2 independent weak sources (it is known that it is impossible to extract from just 1 weak source). In joint work with David Zuckerman, we resolve this problem. I will discuss the main ideas we use to solve this problem.

As a corollary of our 2-source  extractor, we obtain exponential improvements in explicit constructions of Ramsey graphs, a central object in extremal combinatorics. This is in a line of work spanning the last 70 years in an attempt to meet Erdos' challenge of matching the probabilistic method.
10:25 am11:10 am

Pivotal to recent exciting progress in randomness extractors is a pair of new pseudo-random objects - correlation breakers, and independence-preserving mergers. In this talk, we discuss these objects, their constructions, and applications.

11:40 am12:25 pm

The breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} gives a reduction from the construction of explicit non-malleable extractors to the construction of explicit two-source extractors and bipartite Ramsey graphs. However, even assuming the existence of optimal explicit non-malleable extractors only gives a two-source extractor (or a Ramsey graph) for $\poly(\log n)$ entropy, rather than the optimal $O(\log n)$. In this paper we modify the construction to solve the above barrier. Using the currently best explicit non-malleable extractors we get an explicit bipartite Ramsey graphs for sets of size $2^k$, for $k=O(\log n \log\log n)$. Any further improvement in the construction of non-malleable extractors would immediately yield a corresponding two-source extractor. Intuitively, Chattopadhyay and Zuckerman use an extractor as a sampler, and we observe that one could use a weaker object -- a \emph{somewhere-random condenser} with a small entropy gap and a very short seed. We also show how to explicitly construct this weaker object using the Raz \etal error reduction technique \cite{RRV99}, and the constant degree dispersers of Zuckerman that also work against extremely small tests \cite{Zuc06}.

2:00 pm2:45 pm

This talk will give a high level overview of (deterministic/seedless) extractors for random sources that are defined algebraically. These include sources distributed uniformly over an affine subspace or variety and sources sampled by polynomial maps. I will attempt to survey the various techniques that go into known constructions and the many open problems.

2:55 pm3:40 pm
Speaker:

The breakthrough work of Marcus, Spielman, and Srivastava showed that every bipartite Ramanujan graph has a bipartite Ramanujan double cover. Chris Hall, Doron Puder, and I generalized this to covers of arbitrary degree. I will explain the proof, with emphasis on how group theory and representation theory are useful for this problem.

4:10 pm4:55 pm

This talk will review two different results regarding the existence of Ramanujan graphs. While both methods employ the method of interlacing polynomials, they are thematically quite different. The goal will be to highlight some of the commonalities and differences. This represents joint work with Dan Spielman and Nikhil Srivastava.

### Tuesday, January 31st, 2017

9:30 am10:15 am

No abstract available.

10:25 am11:10 am
I will describe a notion of high dimensional expansion called "agreement expansion", that can be described as a "sheaf cohomology". Agreement expansion captures certain PCP questions and in particular abstracts low degree tests such as plane vs. plane or line vs. line.
I will then describe an agreement question on the finite-field Grassmannian which is a high dimensional version of the Raz-Safra plane vs. plane low degree test. We will discuss a hypothesis regarding agreement expansion on the Grassmannian. This hypothesis, if true, implies NP-hardness of 2:1 games, a variant of the unique games conjecture.

Based on joint works with Tali Kaufman, Subhash Khot, Guy Kindler, Dor Mintzer, and Muli Safra.
11:40 am12:25 pm

We discuss our p-adic version of the best known quantum compiling algorithm on a single qubit that is developed by Ross and Selinger. Two main applications of our algorithm are computing optimally the discrete log of diagonal matrices of $PGL_2(\mathbb{Z}/q\mathbb{Z})$ with respect to Lubotzky, Phillips and Sarnak generators and navigation problem for diagonal vertices of LPS Ramanujan graphs \cite{LPS}. My algorithm and Ross and Selinger's algorithm are conditional on assuming one can factor quickly, and a natural conjecture on the distribution of integers representable as a sum of two squares.

2:00 pm2:45 pm

Some thirty years ago, Lubotzky, Phillips and Sarnak used deep number-theoretic insights to construct the first Ramanujan graphs, as well as optimal pseudo-random generators for the rotation group SO(3). In the last decade their work has seen several developments: On the discrete side, in the study of Ramanujan complexes, which are finite simplicial complexes with the spectral behavior of infinite buildings. On the continuous side, in the study of pseudo random generators for U(n), motivated by the problem of constructing optimal gates for fault-tolerant quantum computation. Results on both the continuous and discrete sides draw on the study of Ramanujan digraphs, which seem to be of independent interest. Based on joint works with Eyal Lubetzky, Alex Lubotzky and Peter Sarnak.

2:55 pm3:40 pm

I will report on the latest results on super-approximation. Roughly super-approximation gives us the right condition in order to get a family of expanders out of the Cayley graphs of the congruence quotients of a group generated by finitely many rational matrices. I will mention a sum-product phenomenon in number fields which is used in the proof of super-approximation. Some of the applications of super-approximation will be mentioned at the end.

4:10 pm4:55 pm

Markoff triples are integer solutions to the equation $x^2+y^2+z^2=3xyz$ which arose in Markoff's spectacular and fundamental work on diophantine approximation and has been henceforth ubiquitous in a tremendous variety of different fields in mathematics and beyond. We will review some of these and will then discuss recent joint work with Bourgain and Sarnak on the connectedness of the set of solutions of the Markoff equation modulo primes under the action of the group generated by Vieta involutions. We show in particular that for almost all primes the induced graph is connected. Similar results for composite moduli enable us to establish certain new arithmetical properties of Markoff numbers, for instance the fact that almost all of them are composite.

### Wednesday, February 1st, 2017

9:30 am10:15 am

Expander graphs have been studied intensively in the last 40 years. In recent years a theory of high dimensional expanders is emerging. We will describe some aspects of this theory such as topological expanders, coboundry expanders and the search for a random model.

10:25 am11:10 am

Expander graphs are widely studied, and various methods are known to obtain bounded degree expander graphs. Recently, there is a growing interest in understanding combinational expansion in higher dimensions (higher dimensional simplicial complexes). However, bounded degree combinatorial expanders (random or explicit) were not known till our work. We present a local to global criterion on a complex that implies combinatorial expansion. We use our criterion to present explicit bounded degree high dimensional expanders. This solves in the affirmative an open question raised by Gromov, who asked whether bounded degree high dimensional expanders could at all exist. Gromov has shown that high dimensional expansion of a $d$-dimensional complex, implies that the complex has a topological overlapping property; Namely, every continuous mapping of such a complex to $R^d$ must have a point in $R^d$ that is covered by a constant fraction of the topological $d$-simplices obtained by the mapping. Gromov has asked whether there exist bounded degree complexes with the topological overlapping property. Our work provides an affirmative answer to this question. Based on joint works with David Kazhdan and Alex Lubotzky, and with Shai Evra.

11:40 am12:25 pm

We will discuss the sharp transition in the time it takes simple random walk on regular Ramanujan graphs to approach the uniform distribution (known as the cutoff phenomenon), and geometric consequences (such as typical distances between vertices) that this implies for such graphs. We will then discuss how these ideas can be extended to regular Ramanujan digraphs, and consequently, to any d-dimensional Ramanujan complexes for d>1 associated with a simple group, with analogous geometric implications for these objects.

Base on joint works with Y. Peres and with A. Lubotzky and O. Parzanchevski.

### Thursday, February 2nd, 2017

9:30 am10:15 am

We will discuss some recent developments in several directions of spectral graph theory, including spectral bounds for graphs with general degree distribution and some variations of Ramanujan graph, satisfying vertex and edge expansion properties.

10:25 am11:10 am

One approach to studying properties of random walks on groups with random generators is to study word-measures on these groups. This approach was proven useful for the study of symmetric groups and random regular graphs. In the current work we focus on the unitary groups U(n). For example, if w is a word in F_2 = <x,y>, sample at random two elements from U(n), A for x and B for y, and evaluate w(A,B). The measure of this random element is called the w measure on U(n). We study the expected trace (and other invariants) of a random unitary matrix sampled from U(n) according to the w-measure, and find surprising algebraic properties of w that determine these quantities. This is joint work with Michael Magee.

11:40 am12:25 pm

Quite a few people are trying to answer the question in the title. Various interesting approaches are being proposed based on algebraic, geometric and topological notions. In this talk I will advocate a combinatorial approach that is based on sparsity and regularity and focuses on notions of low discrepancy. This approach makes it particularly desirable to investigate random high-dimensional combinatorial objects.

2:00 pm2:45 pm

In error-correcting codes, list-decoding (and related properties) are intimately related to pseudorandom objects like expanders and extractors.  As with many pseudorandom notions, list-decodability is not well-understood: It's easy to see that completely random codes have excellent list-decodability properties, and we have some very nice explicit constructions, but we still don't really understand this for many families of codes that we know and love.  One example is random linear codes; this has been well-studied, especially in the past few years, but there are still gaps in our knowledge.  In this talk, I'll discuss some recent work with Atri Rudra about the (average-radius) list decodability (and recovery) of random linear codes; along the way I'll highlight connections to and applications in expanders and extractors.

2:55 pm3:40 pm
Speaker:

Locally testable and locally decodable codes are special families of error-correcting codes that admit highly efficient algorithms that detect and correct errors in transmission in sublinear time, probing only a small number of entries of the corrupted codeword. In recent years, there have been new developments on the construction of locally testable and locally decodable codes using graph-based/combinatorial constructions that exploit the power of expander graphs. These eventually led to the construction of asymptotically good locally testable and locally decodable codes with small (sub-polynomial) query complexity, and with near-optimal error-correction capabilities (approaching the Singleton and Gilbert-Varshamov bounds). In this talk I will survey some of these constructions and highlight the role of expander graphs in their development.

4:10 pm4:55 pm

A celebrated result by Impagliazzo and Wigderson is that under complexity theoretic hardness assumptions, every randomized algorithm can be transformed into one that uses only logarithmically many bits, with polynomial slowdown. Such algorithms can then be completely derandomized, with polynomial slowdown. In the talk I will discuss recent work attempting to extend this approach to: 1. Randomized algorithms that err with probability $1-\epsilon$ for small $\epsilon$. (Here, the goal is to minimize the number of random bits/slowdown as a function of $\epsilon$). 2. Known SAT-solving randomized algorithms. (Here, polynomial slowdown is a deal breaker as it gives trivial algorithms that run in super exponential time). 3. Randomized algorithms that sample from probability distributions. (Here, the goal is to sample a statistically-close distribution using only few random bits). Based on joint work with Artemenko, Impagliazzo and Kabanets.

### Friday, February 3rd, 2017

9:30 am10:15 am

We present an approach to show the existence of large expanders in locally sparse graphs and in sparse (including super-critical) random graphs, as well as its consequences for extremal questions and positional games.

10:25 am11:10 am

Spectral gaps of matrices are related to many basic properties, like mixing times, expansion, isoperimetry and more. We will see a connection between spectral gaps and sign-rank. The sign-rank of a boolean matrix is the minimum dimension of real space in which the matrix can be realized as a point-halfspace incidence matrix. Sign-rank is deeply related to learning theory and communication complexity. We will see that regular matrices with large spectral gaps have high sign-rank; roughly speaking, this means that a matrix with large spectral gap can not be realized in low dimensional real space using halfspaces. This is another aspect in which matrices with a large spectral gap are pseudo-random. Based on work with Noga Alon and Shay Moran.

11:40 am12:25 pm

A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani showed that deterministic randomness extraction from these sources is impossible. Recently, Beigi, Etesami and Gohari (ICALP 2015) studied the generalization of SV sources for non-binary sequences and showed that unlike the binary case, deterministic randomness extraction in the generalized case is sometimes possible. Beigi, Etesami and Gohari presented a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions coincide in ?non-degenerate? cases and completely characterize the randomness extraction problem for non-degenerate cases. In this work, we continue the study of deterministic randomness extraction from non-binary SV sources and obtain following results. 1) We completely characterize the randomness extraction problem for both non-degenerate and degenerate cases by providing a necessary and sufficient condition for the possibility of randomness extraction from SV sources. This condition reduces to the condition of Beigi, Etesami and Gohari when the SV source is non-degenerate and fills the gap in the degenerate case. 2) We further improve both the output length and the error of the extractor of Beigi, Etesami and Gohari from a single bit with inverse polynomial error to linear number of bits with exponential error. As a corollary, in the non-degenerate case, a linear number of bits can be extracted and with exponentially small error when randomness extraction is possible. 3) We show that for any extractable SV source one can always extract a random bit with inverse polynomial error. And we show the error cannot be improved beyond inverse polynomial for a specific degenerate source. Joint work with Salman Beigi, Andrej Bogdanov, Omid Etesami.

2:00 pm2:45 pm

Given a finite group $G$ and a set $A$ of generators, the diameter $\diam(\Gamma(G,A))$ of the Cayley graph $\Gamma(G,A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding $\diam(G):= \max_A\diam(\Gamma(G,A))$. It has long been conjectured that the diameter of the symmetric group of degree $n$ is polynomially bounded in $n$. In 2011, Helfgott and Seress gave a quasipolynomial bound (exp((log n)^(4+epsilon))). We will discuss a recent, much simplified version of the proof.


text:
### Cryptanalysis of stream ciphers with linear masking

Don Coppersmith, Shai Halevi, and Charanjit Jutla

##### Abstract

We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a non-linear process'' (say, akin to a round function in block ciphers), and a linear process'' such as an LFSR (or even fixed tables). The output of the cipher can be the linear sum of both processes. To attack such ciphers, we look for any property of the non-linear process'' that can be distinguished from random. In addition, we look for a linear combination of the linear process that vanishes. We then consider the same linear combination applied to the cipher's output, and try to find traces of the distinguishing property. In this report we analyze two specific distinguishing properties''. One is a linear approximation of the non-linear process, which we demonstrate on the stream cipher SNOW. This attack needs roughly $2^{95}$ words of output, with work-load of about $2^{100}$. The other is a low-diffusion'' attack, that we apply to the cipher Scream-0. The latter attack needs only about $2^{43}$ bytes of output, using roughly $2^{50}$ space and $2^{80}$ time.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. extended abstract appears in Crypto'02
Keywords
Hypothesis testingLinear cryptanalysisLinear maskingLow-Diffusion attacksStream ciphers
Contact author(s)
shaih @ watson ibm com
History
2002-06-05: last of 2 revisions
See all versions
Short URL
https://ia.cr/2002/020

CC BY

BibTeX

@misc{cryptoeprint:2002/020,
author = {Don Coppersmith and Shai Halevi and Charanjit Jutla},
title = {Cryptanalysis of stream ciphers with linear masking},
howpublished = {Cryptology ePrint Archive, Paper 2002/020},
year = {2002},
note = {\url{https://eprint.iacr.org/2002/020}},
url = {https://eprint.iacr.org/2002/020}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.


text:
How to handle Multiple-accounts creation and cheating?

I am developing a game that is running as a web application. The fact is that the game lose sense if one player creates several accounts. Imagine that is a turn-based strategy game, and if you play against yourself (with another account) you can earn tons of points easily.

At first, I thought about logging every single user action, and then comparing the users IP to detect if there is any clue of cheating. But then I noticed that different users could be running under the same IP, for example if they are in the school and all them share the same IP using a proxy. Using this way innocent people could result banned.

Is there any better approach that I'm missing?

• Remember that the really good cheaters will have proxies so that their multiple accounts are actually on different IPs. Don't make "same IP" a required criterion when looking for people cheating in this manner. – Ricket Jul 28 '10 at 17:19
• The way you described it, means that two ore more people can team up to get lots of points easily (like the arena battles in WoW). – Hendrik Brummermann Jul 29 '10 at 21:32
• @Matias, is your product focused on a country or is it meant to be world-wide ? if it is country limited you could try to use people's information like security number or something that can be used with no harm from them, it would not prevent 100% but it would cut down by a lot if you can verify weather the numbers are valid or not... – Prix Aug 2 '10 at 4:37
• @Prix you can run into a Loooooooot of trouble collecting SSNs without adequate protection in the US. – Jesse Dorsey Aug 2 '10 at 13:44
• Re-design your game so that two users can't abuse it, instead of trying to stop them from doing so. – o0'. Oct 24 '10 at 14:13

There are a few different ways to handle this, and many solutions have their own merits. I will give my opinion of the ideal way to handle this.

First, it's important to understand that no matter how complicated your system is, someone who is sufficiently invested in gaming the system (with appropriate knowledge) will figure out a way to game it.

To seriously handle this issue, if it is really an issue for you, you need to handle this in both the design and technical implementation of your game.

On the technical end, you need to basically play a game of comparisons.

In general, I am pro-logging if you are running any type of game with user interaction then verbose logs would allow you to modify and tailor your game based on real quantitative measurements.

Using your logs, you can set up a system to compare data between accounts of any number of similarities.

For example, if two accounts are using the same IP address, or any other information that you deem an appropriate comparison measure, you would want to be able to look at overall interaction between the two (wins/losses, trading) in relation to the amount of interaction with others.

Using this data you can pass appropriate judgement on a case-by-case basis, or automatically. Depending on how widespread the issue has become, I would recommend an automatic option and handling any issues through a live moderator. It's important that you don't delete the account, just suspend it with a message along the lines of "This account has been suspected of violating this game's TOS agreement. If you disagree please go here" with a link to an arbitration panel or something.

It is important that such a thing is in place, because people could be sharing IP addresses at home, or at school. Also, for younger kids, they could be using their parent's email addresses, credit cards, or even names in their sign-up information depending on how protective they are.

The second phase is design side. While some benefit is to be expected, you need to sufficiently disincentivize this form of cheating with your gameplay. There are quite a few ways that you can go about this, there are the wholly annoying ones of very short timeouts (which may be necessary). But I feel the best way is by appropriately adjusting the benefits between two accounts.

For example, some MMOs have altered the benefit that high level players recieve when playing with players outside of a reasonable level range. This discourages players with access to multiple accounts from powerleveling themselves (atleast within a specific range)

You could even specifically target accounts that share data and directly decrease the benefit that they gain when interacting with each other. This would encourage interaction with other players, but it can be circumvented with proxy servers and it would be ill-advised depending on your target audience.

The other way that think would work is having gameplay so engaging that people can't really manage to play two separate accounts and still keep up with everyone else.

Of course with this system, you would need to spend a nice deal of effort tweaking to prevent false positives and what not.

tl;dr?

You want to collect appropriate data that allows you to automatically detect and handle potential threats and deal with false positives on a user-by-user basis. A good deal of babysitting would be necessary to make sure you don't have false-positives.

Also you want to reduce the benefit of cheating with multiple accounts on the gameplay end.

• With a decent amount of logging, an interesting item to check would be how often two accounts are logged in together. There is a chance for false positives here just as any other system check, which is why human interaction will always be needed for final decisions. – ManiacZX Aug 1 '10 at 9:47

The simplest and most effective way to counter 'farming' of scores is to adjust the score received based on the disparity between the players. Bear in mind it's not just one player creating multiple accounts you need to worry about: imagine two friends, one deliberately losing so the others ranking is artificially boosted.

Chess and other games avoid this through forms of the Elo rating system. Basically the reward for beating someone of a higher rating than you is high, but the reward for beating someone of a much lower rating is very low. This very quickly makes deliberately losing to advantage another player ineffective. You can tune the rate at which winning against a poor player quickly results in little net gain. A player playing 'properly', i.e. winning against a wide range of similarly ranked opponents, will advance very quickly.

NB: it's not enough to just penalise players who lose so that winning against them gets you nothing, because then players can create an account, lose with it deliberately, then create another account. This isn't so much of an issue if there is a barrier to entry (e.g. entering credit card details to create a new account), but for free-to-play games that would work.

Also its worth noting that there is a danger if the ratings are used as a measure of actual ability, rather than just as a way to modify any rewards the player receives. If the rating itself is the measure, canny players will use the system to sabotage others. I.e. Player 1 gains a lot of skill/ability through practice, and then creates a new account. Player 2, who is about as good as Player 1, accepts a challenge from the newcomer. Losing to the newcomer will massively hurt their ranking, even though really the new player is of equivalent rank. However if the rating isn't actually used to measure the player, this is actually in Player 2's interest (having their rating pulled down will allow them to advance faster given their actual skill level).

• That is a lot of deep gameplay philosophy, right there, good read. – Kzqai Oct 31 '11 at 5:31

You could award points based on the difference between the opponents' point totals. Very good players would earn few points for defeating newbies, and newbies would earn many points for defeating experienced players. Likewise, losers would lose points proportional to the same scale.

This wouldn't completely solve your problem, but it would eliminate the simple case of someone creating and defeating a bunch of newbie alts, as well as making it harder to level two different accounts of equal power.

Really, though, there's not a foolproof way of stopping this; a sufficiently dedicated cheater will succeed. But if you flag accounts with suspicious activity for review, where "suspicious activity" includes multiple accounts with the same e-mail or IP address, then you'll be able to spot the most egregious offenders.

I've found this is much easier to fix through game design than through enforcement/banning. Even if you permanently ban all of a player's accounts, sufficiently determined players can find a way around your ban (e.g. if you track IP, they can use dynamic IP or IP masking).

For example, if you award points to players for winning PvP contests, you give players incentives to make multiple accounts so they can lose to themselves. If instead you give bigger rewards for playing in groups with the same players over time (i.e. guild participation), you incentivize friendship and community over competition, which changes preferred behaviors. Having additional metagame characteristics tied to the player's account (such as a Reputation score and Friends list) further makes the maintenance of multiple accounts less appealing -- at the least, people would want one "primary" account with a good rep.

If your game is PvP by nature, a big way around the "I'll make several accounts and lose to myself on purpose" problem is to only offer automated matchmaking. So, the player requests to play a game, and the server automatically matches them against someone else who happens to be online at the time. If players can't choose their opponents, there's no way for them to guarantee they'll fight themselves (unless they happen to be the only one online at the time, but then you have bigger problems). See Microsoft Hearts/Spades, or most Facebook games that allow PvP, for examples of this. Note that in this case you'll definitely want some kind of intelligent matchmaking (either using some kind of ranking/rating system as part of the player account, or letting players self-select their preferred level of competitiveness).

If you're worried that players will want to play games with their friends, you can always offer that option as well, but only allow unrated/unranked/practice games when you choose your opponents.

The people over at https://panopticlick.eff.org/ did some testing on how somebody could be uniquely identified by several values that can be gathered from almost any browser. The results are astounding and you could use a similar approach (maybe combined with other measures) to identify and track your users.

• I don't think this is a fine approch to be used, specially if it is a browser game since you can create your own browser making it easy to become a unique person to create a new account. – Prix Aug 2 '10 at 4:34
• @Prix yes, i didn't meant this to be the solution that solves all issues. But I think it could be a good addition to IP logging. And of course you'll need other measures too. – bummzack Aug 2 '10 at 8:26
• Useful, even if it isn't a standalone method. – Kzqai Nov 18 '10 at 18:32

There's a very simple design solution that Blizzard took in Warcraft 3 and Starcraft 2: only let players earn points/score/experience when playing in games using the automatic matchmaking service. Players can still play against their friends, but won't get points from it.

If the player has no way of deciding who they are playing against, there's no reliable way to game it by playing against dummy accounts.

• Effective, but boring. I would much prefer to play a game against opponents that I have come to know (enemies, or friends, or casual acquaintances on chat) than against random unknowns, especially ones that may or may not be active opponents at any point. – Kzqai Nov 18 '10 at 18:06
• Valve seems to go like this too (CS:GO, Dota 2...). I wouldn't call it boring, but more and more frustrating as you play: the effect of this approach is that Player Communities are literally terrible, and not many people can stand it for a longer time. Players meet verbal offending and other abusive behaviour in most of the games of "Public Matchmaking". – madneon Mar 20 '15 at 19:30

i play on a game system called travian, and i really think the technology isnt good enough to catch cheats. Most cheats have 2-4 systems linked via KVM switch, each system runs different OS versions(windows xp, vista, win7, linux mint, Slitaz and so on) , and is run in via proxy servers (though the main account is not using proxy but standard)

This of course creates such an unfair advantage that most of the people that pay to play the game are leaving, with paying members down over 1000 in just a few months, and with the fewer players, its becoming increasing more obvious that accounts are suspicious, but with no evidence of cheating, the players that do cheat escape punishment, and those that pay fairly (whoops, meant to say play fairly) can see the suspicious activity, they get discouraged and quit the game - or they learn to cheat and hence inlies the problems.

Currently for travian, there is no player in the top of the game that can honestly say they dont cheat, or admitt they havnt hired people from countries like the phils and china to help them play the game for them while they sleep or are on holidays.

surely there must be better ways to catch multiple account cheats, or is this the future of games, where just a few actual people make up the entire game base and the winner is based on who can hire the most people in 3rd world countries to play the games for them.

would membership of \$0.01 via credit card (and see who has identical credit card numbers) be a feasible way to detect multiple account cheats at time of registration?

• The issue with credit cards is that you can just buy a gift card and use that to open other accounts. – Jesse Dorsey Jul 31 '10 at 13:12
• @Noctrine You realize that you can edit posts here after you submit them, don't you? Some people prefer to annotate their changes rather than make an invisible edit. – Casey Wagner Sep 4 '10 at 22:00
• @Mike Yeah, but it seemed like it was a, hah! type thing. But re-reading it, it does seem like I didn't read the answer correctly probably the cause of me reading/commenting early in the morning :p Removed that bit. – Jesse Dorsey Sep 5 '10 at 8:55
• This seems like a weird description of the problem to me. What are players who get third parties to play the game getting out of it? Certainly that's gotta cut down a lot of their fun. I can see the fun of multi-accounting by yourself, but having someone else multi-account for you doesn't seem to add to the fun unless you get something back, like money for being at the top. – Kzqai Nov 18 '10 at 18:10

One option if you have multiple servers is to require that any accounts from the same IP must be created on alternate servers. So if you want to create 10 accounts, great, but you'll have to create them on servers that don't interact with each other. This prevents people at the same location from being able to play together, so there is that drawback. On the plus side it also interferes with the effectiveness of proxies in cheating.

You're going to end up with pros and cons to any solution you come up with, and you won't completely eliminate cheating. So decide how far you're willing to go and keep a close eye on how those changes effect the user base.

Most people try to chase after multi accounts with external tools. Which is stupid. If you have proper logs and metrics for user activities you could nail most multi-accounters with a handful of criteria scans inside a game.

And no, I'm not going to hand you the breakdown - truth is - and very few people in the industry are going to spell it out - the more stupid game designers and coders are out there the better job security for the people who know what the hell it is they are doing.

Multi Accounting is only even viable to people if the benefit chain is badly designed and can by manipulated easily by multi-accounts.

If multi-accounting is hard and time consuming in terms of reward (not detection dodging - just gameplay effort and time)

Then the only people really doing it are the hardcore players. And you don't even need to bother raising an eye brow to them as they are community drivers. They spend every effort to know all your loopholes and study efficiency within an environment. By all rights the effort they invest should be the best rewarded. You still get to monetize the majority of lazy ones.

Good designers never really go plugging every loophole - just plug the major ones and make sure you have a way to take out excess out of the economy. Or obviously inject value in if need be.

I have a list on hand of 83 multiaccounters. They think they are fooling us - and get to enjoy the happiness of the idea that they are smarter than us. Most also invest real cash into the game - we don't want to ban them. Our coders didn't really have time for a system - So I set up CM with a secret dummy account to occasionally bash their heads ingame and "legitimately" steal their "riches".

They think they are playing us as company, and are getting increasingly motivated by thinking someone else ingame has an axe to grind. End result is - any critical excess is discarded by a CM - considering he knows what the user is upto, and pull an "ambush" at any time. All of which - can be automated by code but, who has time or budget for that?

Anybody building complex multi-account detection systems for profiling user IDS, to prevent multi accounts in games is pissing against the wind to begin with.

You really need to identify the specific behaviors that you want to prevent.

For example, if the real problem that you want to prevent is not "people making multiple accounts", but "individuals being targeted by multiple accounts controlled by the same person", that's an area where you can use similar traits between potentially clone accounts to allow the players themselves to police multiplaying. In other words, if they detect traits of multiplaying, they can act (via some interface) to check for similarities between the accounts, and if the accounts do have too many similarities, cause a punishment to occur. Player policing. The benefit of this is that multi-accounting matters the most to other, non-multiplaying individuals, so if they feel wronged, they have a recourse they can try to catch the multiplayer on the spot. It also allows things that in a flatly viewed account system would be false positives (like ip) to be much more real evidence of multiaccounting.

Similarly, as others have mentioned, if it's the gaining of rank by defeating their own dummy accounts, a system like the rep system here on stackexchange helps to turn taking ranking points from yourself into a zero-sum gain.

Ensure that making multiple accounts isn't worth it.

Examples of how you'd do this:

• Grant tiny awards in the first few levels compared to later levels.
• Compulsory tutorials - first time players will find it useful and multi-accouters will find them incredibly annoying.
• If there's a reward for referring others, give the award once the referred player reaches a certain level.
• If players battle one another, make winning against low(er) level players get waste of time. E.g. anyone under more than 5 levels than you won't give you rewards for winning against.
• The StackExchange network is an excellent example. Making new accounts has very little benefit.

Allow players to make multiple accounts because you can't stop them from doing it anyway:

• If you add IP blocks, people will use proxies and VPNs
• IP checking also bring about false positives.
• Tracking cookies and local storage data can be deleted.
• If you try to collect (a lot of) personal information, it'll strongly discourage people from registering and it's useless if you don't verify it.
• Each account typically takes up a few bytes of space. You can afford that.

Out of all of these answers, this method is the only one that truly works. If people won't want to make multiple accounts, they won't do it. You can decide on what they want through good, considerate game design.

I think there is another aproach. Because there is another potential harm: Imaging two friends who both create two accounts: one looser and one winner account each. One day friend A uses his looser account to loose all games against friend B's winner account. The next day they change. Checking the IPs won't help here.

You should check the behaviour of the players (a strategy know from intrusion detections systems). If two player play each other often and one looses all the time, this is a clue. If games end very early, it is another clue.

You could score those clues, add the score up to a reputation (don't show the reputation to the users) and ban accounts if they reach a value you define. Maybe there should also be anti-clues that repairs the reputation.

Other clues depend very much on your game. But I think you get the idea.

• I worked on a project that tried to detect cheating like this. There ended up being so many edge cases that the system got it wrong as much as it got it right, both with false positives and false negatives. – tenpn Jul 28 '10 at 16:53
• Having a reputation system would help with the case you describe (e.g. you can only get rep from others, so getting it from yourself just moves it back and forth uselessly). Also, if each friend has two accounts, isn't ip detection actually going to be useful at least some of the time? – Kzqai Nov 18 '10 at 18:13

You can use Flash local data storage, not everyone knows how to delete flash data.

• Not everyone isn't enough, unfortunately. – Lolums Dec 6 '15 at 15:09

Not really a solution, but a deterrent at least: Say that if people are discovered having multiple accounts, all accounts will be banned. This should keep many people from even trying it. Even if you don't actually ban all accounts, or don't have a way to detect it at all, most will be too afraid.

• The only way to make the threat effective is to follow through, which requires continuous monitoring and banning of your playerbase... ...which is just about the least desirable outcome, certainly first you should explore changing the system to minimize cheating potential. – Kzqai Oct 31 '11 at 5:34
• Furthermore, after you get some accounts banned, you still can create new ones to cheat again. That's total nonsense! – o0'. Feb 15 '12 at 8:54