We were discussing Signature verification methods. We reviewed the stages involved with Signature verification yesterday. Let us continue to list and compare online and offline verification techniques.

The feature extraction techniques involved include:
1) using an SVM classifier to extract random transform and fractal dimension
2) using neural network to extract curvlet transform, Hough transform
3) using Euclidean distance and least square error classifier for point density and spatial frequency
4) using statistical analysis techniques and chi-square test
5) using feature vector correlation for projection and local point density
6) using svm for Radon transformation
7) using learning techniques
8) using neural network for directional features

Online signature feature extraction also include:
1) signing time
2) signature width and height
3) number of pen-ups and pen-downs
4) total signature length and
5) velocity of pen

Feature extraction depends on pre-processing. Images may need to be loaded, resized, thinned, rotated and cropped.

grayscale is made into binary image with the use of threshold as
(mu1 +mu2) / 2

#codingexercise
We were discussing a coding exercise as shown below:
A person wants to buy L items from her favorite store such that a subset of N items must contain D distinct items.  the items range from 1 to A in price. Determine the maximum amount of money the person can spend.

We discussed a technique for building the combinations in a greedy manner by choosing the highest priced items first. We also discussed an alternate way to enumerate all possible combinations and select only the ones that match the criteria and return the one that has the maximum purchase.
Another way to reduce enumerations of unnecessary combinations would be to use the enumerations only from combinations with repetitions instead of exhaustive combinations.

We were discussing Signature verification methods. Let us review the stages involved with Signature verification. We will also compare online and offline verification techniques afterwards.
The first stage for the image processing is the image acquisition. This is a crucial stage of any recognition system as the quality of image may considerably affect the subsequent stages. Moreover the devices capturing the image may wear over time since this is touch based technique. Therefore, the consistency of image quality over time is also an important factor.
The second stage for the image processing is the pre-processing that removes noise and may even introduce normalization.  Some pre-processing steps may also involve resizing, binary color conversion and cleaning, rotation, thinning and cropping.  Binary image that highlights only the signature may be achieved by determining the extremes of gray values and finding the mid point between them as the threshold. For example, if mu1 and mu2 are the gray values for both groups of pixels, the threshold may be set as ( mu1 + mu2 ) /2
The third stage of the image processing is the feature extraction. This is a critical stage for the signature verification because the type and quality of feature may make the verification accurate, predictable and consistent. While both online and offline verification techniques may vary in feature extraction, both may also involve common techniques. Feature extraction is generally termed global or local depending on the features extracted.
The last stage of the image processing is the signature verification. This may be the Euclidean distance computed in the feature space. If the distance is less than a threshold, the signature may be considered as verified.

#codingexercise
We were discussing a coding exercise as shown below:
A person wants to buy L items from her favorite store such that a subset of N items must contain D distinct items.  the items range from 1 to A in price. Determine the maximum amount of money the person can spend.

Since the price has to be maximized, the algorithm has to be greedy in its strategy to select the next item. when we can no longer purchase the highest priced item because it violates the given restriction, we make the subsequent selection  from the next lower priced item. we determine the threshold from the range 1 to n/d. The rest is recursive combination as shown earlier.
Another way to do this would be to enumerate all possible combinations and select only the ones that match the criteria and return the one that has the maximum purchase.

Signature detection and segmentation is a known field of study and techniques involve shape matching. While some of this processing involve offline techniques, there are online techniques also mentioned in the associated literature.  Moreover, MYCT-Signature corpus, Susig database and GPDS-960 provide well known databases for evaluating algorithms.  For example, one method of non-rigid shape matching involves a spatial histogram aka shape context computed for each point which describes the distributions of the relative positions of all remaining points. The correspondences between points are solved through weighted bipartite graph matching before the signatures are matched. Another method of non-rigid shape matching formulates it as an optimization problem that preserves a local neighborhood structure. This method has an intuitive graph matching interpretation where each point represents a vertex and two vertices are considered connected in the graph if they are neighbors. The problem of finding optimal match between shapes is therefore equivalent to maximizing the number of matched edges between their corresponding graphs under a one-to-one matching constraint. In this optimization approach, an iterative framework is used  to estimate the correspondences and the transformation. In each iteration, graph matching is initialized using shape context distance and subsequently updated through relaxation labeling which is a well-known formal method of expressing low level contextual information, and applying it to complete the extraction of image features. 
Image processing generally involves multiple subsequent stages of processing the images. Signatures have the nice property that they are like the results of sobel edge detection and the edges are expected to be more continuous in their formation.  Moreover, signature pads are  small images, with similar curves and accents and purely black and white, so they are near consistent and this helps with their processing. 
#codingexercise
A person wants to form teams by selecting as many participants from a list as possible. The participants have skills represented by an integer. The skills selected as such must be distinct and contiguous even if they are negative. By making the team as large as possible, more problems can be solved. What is the size of the team he can form ?
one way to do this would be to sort the skills and find the largest distinct unit incremental subsequence.

Another way to do this is with longest increasing sequence.
Int GetLongestIncreasingSubsequence(List<int> A)
{
var best = new int[A.Length+1];

for (int i = 0; i < best.Length; i++)

       best[i] = 1;

for (int i = 1; i < A.Length; i++)

    for (int j=0; j < i; j++)

         if (A[i] == A[j] + 1)

          {

               best[i] = Math.Max(best[i], best[j]+1);

          }
return best.ToList().max();
}

The above assumes distinct elements.

another exercise

A person wants to buy L items from her favorite store such that a subset of N items must contain D distinct items.  the items range from 1 to A in price. Determine the maximum amount of money the person can spend.

Since the price has to be maximized, the algorithm has to be greedy in its strategy to select the next item. when we can no longer purchase the highest priced item because it violates the given restriction, we make the subsequent selection  from the next lower priced item. we determine the threshold from the range 1 to n/d. The rest is recursive combination as shown earlier.

Courtesy: hackerrank

Yesterday we were discussing how to enable user logins with something that they draw such as their signature on a signature pad. Efficient image processing algorithms can then compare signatures. Moreover, what people draw on the signature pads is completely their call and can even handwrite passwords instead of signature. Since the data is private both at rest and transit, this cannot be divulged with anybody else and provides a layer of security on top of the known passwords.  Signature detection and segmentation is a known field of study and techniques involve shape matching. While some of this processing involve offline techniques, there are online techniques also mentioned in the associated literature.  Moreover, MYCT-Signature corpus, Susig database and GPDS-960 provide well known databases for evaluating algorithms.  For example, one method of non-rigid shape matching involves a spatial histogram aka shape context computed for each point which describes the distributions of the relative positions of all remaining points. The correspondences between points are solved through weighted bipartite graph matching before the signatures are matched. Another method of non-rigid shape matching formulates it as an optimization problem that preserves a local neighborhood structure. This method has an intuitive graph matching interpretation where each point represents a vertex and two vertices are considered connected in the graph if they are neighbors. The problem of finding optimal match between shapes is therefore equivalent to maximizing the number of matched edges between their corresponding graphs under a one-to-one matching constraint. In this optimization approach, an iterative framework is used  to estimate the correspondences and the transformation. In each iteration, graph matching is initialized using shape context distance and subsequently updated through relaxation labeling which is a well-known formal method of expressing low level contextual information, and applying it to complete the extraction of image features. 
Image processing generally involves multiple subsequent stages of processing the images. Signatures have the nice property that they are like the results of sobel edge detection and the edges are expected to be more continuous in their formation.  Moreover, signature pads are  small images, with similar curves and accents and purely black and white, so they are near consistent and this helps with their processing. 

We were discussing identity management with Civic.

It introduced three new components: 1) a variety of smart contracts 2) an indigenous utility token and
3) new software applications.
 Blockchain works as the ledger in these cases. The smart contracts are the code executed on the blockchain.  There is a high degree of privacy for the individual whose transactions are maintained in the ledger. The transaction does not divulge any Personally Identifiable Information but an individual can easily prove ownership of the entries.
The ledger itself is decentralized and maintained by a community where no one actor can gain enough influence to submit a fraudulent transaction or alter recorded data.
Civic introduced a proprietary token which will be used as  a form of settlement between participants to an indentity related transaction. It also provides a means to reward the participants While the service provider may follow any standards such as NIST, FIPS or PIV, Civic manages the attestation and its sharing between service providers. For example:
There is a service provider A who sells a service to user. The user sends the PII for verifying identity. A calculates a hash of the PII and records its attestation on the blockchain. User visit service provider B who wants access to all or certain of the PII. The user is willing to share the requested data and A offers a price for its attestation to B which accepts the price. User B can locate and view the blockchain transaction. It would also be able to recreate the hashes for the PII and compare them to that on the blockchain. If B is satisfied, it purchases the attestation and pays the amount into escrow via Civic tokens into escrow. The civic app with the user then transmits the PII to B. To complete the transaction, the CVC from the escrow is shared between the user and A  - the original validator.
While the benefits for recording attestations on a distributed ledger are widely acknowledged to foster a new ecosystem, an identity provider may lean to centralized model for offering innovative technologies.
For example, it may require users to login merely with their signatures. Efficient image processing algorithms can then compare signatures.  The signature pad : http://szimek.github.io/signature_pad/ is one such example which could be considered to replace password entry on many mobile devices. The user may have to flip the screen to landscape orientation but the experience can be very close to the real thing. Moreover, signature pads are  small images and purely black and white, so they are near consistent and this helps with the processing. Moreover, what people draw on the signature pads is completely their call and can even handwrite passwords instead of signature. Since the data is private both at rest and transit, this cannot be divulged with anybody else and provides a layer of security on top of the known passwords.  Signature detection and segmentation is a known field of study and techniques involve shape matching. For example: http://matlab-recognition-code.com/signature-recognition-based-on-neural-networks/

We were discussing identity management with Civic.

It is based on blockchain ledger that enables users to login with their fingerprints.  The availability of a distributed ledger does away with a password database. Civic identity management introduces three new components:
1) a variety of smart contracts
2) an indigenous utility token and
3) new software applications.
 Blockchain works as the ledger in these cases. The smart contracts are the code executed on the blockchain.  The advantages of using a distributed ledger such as blockchain include the following:
There are no middlemen for transfers and therefore there is little fees and low cost. Moreover the protocol has a rewarding mechanism
The ledger is immutable and its integrity checked and agreed on an ongoing basis. 
All transactions on the ledger are visible to anyone and any transaction done anytime is recorded.
The transactions on the ledger cannot be reversed and are immune from chargebacks. These transactions are as sound as cash transactions.
There is a high degree of privacy for the individual whose transactions are maintained in the ledger. The transaction does not divulge any PII but an individual can easily prove ownership of the entries.
The ledger itself is decentralized and maintained by a community where no one actor can gain enough influence to submit a fraudulent transaction or alter recorded data.
Would blockchain be popular without the rewarding incentive ? From a design perspective, we could ignore that.
#codingexercise
Find sum of all possible combinations for N elements

void  Combine(List<int> A, ref List<int> b, int start, int level, ref List<int> sums)   

{   

for (int I = start; I < A.length; I++)   

{    

     b[level] = A[i];   

     sums.Add(GetSum(b)); 

    if (I < A.length)   

           Combine(A, ref b, i+1, level+1, ref sums);   

     b[level] = 0;   

}   

}  

We were discussing identity management with Civic.

It is based on blockchain ledger that enables users to login with their fingerprints.  The availability of a distributed ledger does away with a password database. Civic identity management introduces three new components:
1) a variety of smart contracts
2) an indigenous utility token and
3) new software applications.
 Blockchain works as the ledger in these cases. The smart contracts are the code executed on the blockchain.  The advantages of using a distributed ledger such as blockchain include the following:
There are no middlemen for transfers and therefore there is little fees and low cost. Moreover the protocol has a rewarding mechanism
The ledger is immutable and its integrity checked and agreed on an ongoing basis. 
All transactions on the ledger are visible to anyone and any transaction done anytime is recorded.
The transactions on the ledger cannot be reversed and are immune from chargebacks. These transactions are as sound as cash transactions.
There is a high degree of privacy for the individual whose transactions are maintained in the ledger. The transaction does not divulge any PII but an individual can easily prove ownership of the entries.
The ledger itself is decentralized and maintained by a community where no one actor can gain enough influence to submit a fraudulent transaction or alter recorded data.
#codingexercise
we were discussing compute based methods of finding products of all length combinations from sequence 1 to N 
We could simply do this with Combine
Void  Combine(List<int> A, ref List<int> b, int start, int level, ref List<int> products)  
{  
for (int I = start; I < A.length; I++)  
{   
     b[level] = A[i];  
     products.Add(GetProduct(b));
    if (I < A.length)  
           Combine(A, ref b, i+1, level+1, ref products);  
     b[level] = 1;  
}  
} 

We were discussing identity management with Civic.

It is based on blockchain ledger that enables users to login with their fingerprints.  The availability of a distributed ledger does away with a password database. Civic identity management introduces three new components:
1) a variety of smart contracts
2) an indigenous utility token and
3) new software applications.
 Civic builds a system to enable on-demand, secure and low cost access to identity verification aka IDV. Agencies that perform IDV are called validators, the individual whose identity is verified is called a user and the stamp of approval is called an attestation.  The user's information that is attested is called PII - short for personally identifiable information. This form of improvement enabled Civic to allow users to be recognized merely by their thumbprint while the digital identity was attested.
Attestations can be sold while the PII may not be sold. Civic introduced a token or CVC which is used as a form of settlement between participants for identity related transactions. CVC therefore becomes a currency whose transactions can be specified by the contracts. Civic aims to introduce new services  and improve existing services that can be exchanged for this currency. These services may include personal background checks, blockchain notary services, web monitoring and searches, individual credit reports, peer to peer identity services. The currency facilitates and audits the transactions while the services provide the means for the value paid for. In a way the notion of tokens is used to reward the use of services and are generally accumulated by the user not the service provider or requestor. Blockchain works as the ledger in these cases. The smart contracts are the code executed on the blockchain.  The advantages of using a distributed ledger such as blockchain include the following:
There are no middlemen for transfers and therefore there is little fees and low cost. Moreover the protocol has a rewarding mechanism
The ledger is immutable and its integrity checked and agreed on an ongoing basis. 
All transactions on the ledger are visible to anyone and any transaction done anytime is recorded.
The transactions on the ledger cannot be reversed and are immune from chargebacks. These transactions are as sound as cash transactions.
There is a high degree of privacy for the individual whose transactions are maintained in the ledger. The transaction does not divulge any PII but an individual can easily prove ownership of the entries.
The ledger itself is decentralized and maintained by a community where no one actor can gain enough influence to submit a fraudulent transaction or alter recorded data.
#codingexercise
we were discussing a storage based method of finding sum of products of all combinations.
To make it more compute intensive than storage we could restructure it based on the combine method earlier or as follows(pseudocode):
void CombineIntoProductsBySelectingRfromN(List<int> A, List<int>combinations, int n, int r, int depth, int index) {

  if (index == r) {

    int product = 1;

    for (int i = 0; i < r; i++)

      product = product * combinations[i];

    sum += product;

    return;

  }

   for (int i = depth; i < n; i++) {

    combinations[index] = a[i];

    CombineIntoProductsBySelectingRFromN(a, combinations, n, r, i + 1, index + 1);

    combinations[index] = 0;

  }

}

CombineIntoProductsBySelectingRFromN(a, combinations, n, r, 0, 0);

A = 1,2,3

N = 3

r = 2

We were discussing identity management with Civic.

It is based on blockchain ledger that enables users to login with their fingerprints.  The availability of a distributed ledger does away with a password database. Civic identity management introduces three new components:
1) a variety of smart contracts
2) an indigenous utility token and
3) new software applications.
 Civic builds a system to enable on-demand, secure and low cost access to identity verification aka IDV. Agencies that perform IDV are called validators, the individual whose identity is verified is called a user and the stamp of approval is called an attestation.  The user's information that is attested is called PII - short for personally identifiable information. This form of improvement enabled Civic to allow users to be recognized merely by their thumbprint while the digital identity was attested.
The mechanics of attestation is achieved with the help of a Merkle tree. Each node of the merkle tree represents an element of PII along with the hash and the hash of the hashes of the child nodes.  The root hash then becomes the fingerprint of the data being attested. This root hash is converted to a valid block chain address using the additive property of the Elliptic Curve Cryptography:

  k-priv + h = k-attest

This allows the privacy for both the user and the validator to be protected because it is not easy to determine the user and validator from the above address. 
It is called an Elliptic curve cryptography because the domain parameters are bounded by an elliptical curve

#Find the sum of products of all combinations of N numbers  

Double GetSumOfProductsOfCombinations(List<double>  numbers) 

{ 

List<List<double>> combinations = GetCombinations(numbers); 

var products = combinations.Select( x => GetProduct(x)); 

return products.Sum(); 

} 

In the above method, the numbers are enumerated again and again in each of the combinations leading us to store these numbers rather than the more useful products which number one each for as many combinations as there are to consider. 

For example 1,2,3,4 

Has  

1 

1,2;   2 

1,2,3;    1,3;     2,3;     3 

1,2,3,4;   1,3,4;    2,3,4;    3,4;    1,2,4;    2,4;    4; 

We can organize the above in N-ary tree of products where the elements at each level include only those combinations whose number matches the depth. Since existing products are untouched and the new products are formed by cloning the product stored in each existing node and multiplying with the new element, products from all the combinations are considered. The data structure does not necessarily have to be a tree since we clone the existing products before multiplying with the new number and therefore we can use a list and a recursion upto the inclusion of all given elements in a combination. 

void GetProducts (int depth, list <double> elements,  ref List <double> products)

{
if  (depth == elements.count ()) return;
var newproducts = products.select (x => x * elements [depth]).ToList();
products. addrange (newproducts);
products.add (elements [depth]);
GetProducts(depth + 1, elements, ref products);
}