Sandipan DeyFeb 28, 2018
Graph-Based Image Segmentation in Python
In this article, an implementation of an efficient graph-based image segmentation technique will be described, this algorithm was proposed by Felzenszwalb et. al. from MIT. The slides on this paper can be found from Stanford Vision Lab.. The algorithm is closely related to Kruskal’s algorithm for constructing a minimum spanning tree of a graph, as stated by the author and hence can be
implemented to run in O(m log m) time, where m is the number of edges in the graph.
Problem Definition and the basic idea (from the paper)
- Let G = (V, E) be an undirected graph with vertices vi ∈ V, the set of elements to be segmented, and edges (vi, vj ) ∈ E corresponding to pairs of neighboring vertices. Each edge (vi, vj ) ∈ E has a corresponding weight w((vi, vj)), which is a non-negative measure of the dissimilarity between neighboring elements vi and vj.
-
In the case of image segmentation, the elements in V are pixels and the weight of an edge is some measure of the dissimilarity between the two pixels connected by that edge (e.g., the difference in intensity, color, motion, location or some other local attribute).
-
Particularly for the implementation described here, an edge weight functionbased on the absolute intensity difference (in the yiq space) between the pixels connected by an edge, w((vi, vj )) = |I(pi) − I(pj )|.
-
In the graph-based approach, a segmentation S is a partition of V into components
such that each component (or region) C ∈ S corresponds to a connected component
in a graph G0 = (V, E0), where E0 ⊆ E.
-
In other words, any segmentation is induced by a subset of the edges in E. There are different ways to measure the quality of a segmentation but in general we want the elements in a component to be similar, and elements in different components to be dissimilar.
-
This means that edges between two vertices in the same component should have relatively low weights, and edges between vertices in different components should have higher weights.
-
The next figure shows the steps in the algorithm. The algorithm is very similar to Kruskal’s algorithm for computing the MST for an undirected graph.
-
The threshold function τ controls the degree to which the difference between two
components must be greater than their internal differences in order for there to be
evidence of a boundary between them.
-
For small components, Int(C) is not a good estimate of the local characteristics of the data. In the extreme case, when |C| = 1, Int(C) = 0. Therefore, a threshold function based on the size of the component, τ (C) = k/|C| is needed to be used, where |C| denotes the size of C, and k is some constant parameter.
-
That is, for small components we require stronger evidence for a boundary. In practice k sets a scale of observation, in that a larger k causes a preference for larger components.
-
In general, a Gaussian filter is used to smooth the image slightly before computing the edge weights, in order to compensate for digitization artifacts. We always use a Gaussian with σ = 0.8, which does not produce any visible change to the image but helps remove artifacts.
-
The following python code shows how to create the graph.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
import numpy as np
from scipy import signal
import matplotlib.image as mpimg
def gaussian_kernel(k, s = 0.5):
probs = [exp(-z*z/(2*s*s))/sqrt(2*pi*s*s) for z in range(-k,k+1)]
return np.outer(probs, probs)
def create_graph(imfile, k=1., sigma=0.8, sz=1):
rgb = mpimg.imread(imfile)[:,:,:3]
gauss_kernel = gaussian_kernel(sz, sigma)
for i in range(3):
rgb[:,:,i] = signal.convolve2d(rgb[:,:,i], gauss_kernel, boundary='symm', mode='same')
yuv = rgb2yiq(rgb)
(w, h) = yuv.shape[:2]
edges = {}
for i in range(yuv.shape[0]):
for j in range(yuv.shape[1]):
for i1 in range(i-1, i+2):
for j1 in range(j-1, j+2):
if i1 == i and j1 == j: continue
if i1 >= 0 and i1 = 0 and j1 < h:
wt = np.abs(yuv[i,j,0]-yuv[i1,j1,0])
n1, n2 = ij2id(i,j,w,h), ij2id(i1,j1,w,h)
edges[n1, n2] = edges[n2, n1] = wt
return edges
|
Some Results
- The images are taken from the paper itself or from the internet. The following figures and animations show the result of segmentation as a result of iterative merging of the components (by choosing least weight edges), depending on the internal difference of the components.
- Although in the paper the author described the best value of the parameter k to be around 300, but since in this implementation the pixel RGB values are normalized (to have values in between 0 – 1) and then converted to YIQ values and the YIQ intensities are used for computing the weights (which are typically very small), the value of k that works best in this scenario is 0.001-0.01.
- As we can see from the below results, higher the value of the parameter k, larger the size of the final component and lesser the number of components in the result.
- The minimum spanning tree creation is also shown, the red edges shown in the figures are the edges chosen by the algorithm to merge the components.
Input Image
Output Images for two different values of the parameter k
The forest created after a few iterations
Input Image
Output Images for two different values of the parameter k
The forest created after a few iterations
Input Image
Output Segmented Images
Input Image
Segmented Output Images
Input Image
Output Images for two different values of the parameter k
The forest created after a few iterations
Input Image (UMBC)
Segmented Output Images
Input Image
Segmented Output Image with k=0.001
Input Image
Segmented Output Image with k=0.001
Input Image
Segmented Output Image with k=0.001
Input Image (liver)
Segmented Output Images
Input Image
Segmented Output Images with different values of k
Input Image
Segmented Output Image
Input Image
Segmented Output Images for different k
Graph-Based Image Segmentation in Python
Sandipan DeyFeb 28, 2018
Implementing Lucas-Kanade Optical Flow algorithm in Python
In this article an implementation of the Lucas-Kanade optical flow algorithm is going to be described. This problem appeared as an assignment in a computer vision course from UCSD. The inputs will be sequences of images (subsequent frames from a video) and the algorithm will output an optical flow field (u, v) and trace the motion of the moving objects. The problem description is taken from the assignment itself.
Problem Statement
Single-Scale Optical Flow
- Let’s implement the single-scale Lucas-Kanade optical flow algorithm. This involves finding the motion (u, v) that minimizes the sum-squared error of the brightness constancy equations for each pixel in a window. The algorithm will be implemented as a function with the following inputs:
def optical_flow(I1, I2, window_size, tau) # returns (u, v)
- Here, u and v are the x and y components of the optical flow, I1 and I2 are two images taken at times t = 1 and t = 2 respectively, and window_size is a 1 × 2 vector storing the width and height of the window used during flow computation.
- In addition to these inputs, a theshold τ should be added, such that if τ is larger than the smallest eigenvalue of A’A, then the the optical flow at that position should not be computed. Recall that the optical flow is only valid in regions where
has rank 2, which is what the threshold is checking. A typical value for τ is 0.01.
- We should try experimenting with different window sizes and find out the tradeoffs associated with using a small vs. a large window size.
- The following figure describes the algorithm, which considers a nxn (n>=3) window around each pixel and solves a least-square problem to find the best flow vectors for the pixel.
- The following code-snippet shows how the algorithm is implemented in python for a gray-level image.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
import numpy as np
from scipy import signal
def optical_flow(I1g, I2g, window_size, tau=1e-2):
kernel_x = np.array([[-1., 1.], [-1., 1.]])
kernel_y = np.array([[-1., -1.], [1., 1.]])
kernel_t = np.array([[1., 1.], [1., 1.]])
w = window_size/2
I1g = I1g / 255.
I2g = I2g / 255.
mode = 'same'
fx = signal.convolve2d(I1g, kernel_x, boundary='symm', mode=mode)
fy = signal.convolve2d(I1g, kernel_y, boundary='symm', mode=mode)
ft = signal.convolve2d(I2g, kernel_t, boundary='symm', mode=mode) +
signal.convolve2d(I1g, -kernel_t, boundary='symm', mode=mode)
u = np.zeros(I1g.shape)
v = np.zeros(I1g.shape)
for i in range(w, I1g.shape[0]-w):
for j in range(w, I1g.shape[1]-w):
Ix = fx[i-w:i+w+1, j-w:j+w+1].flatten()
Iy = fy[i-w:i+w+1, j-w:j+w+1].flatten()
It = ft[i-w:i+w+1, j-w:j+w+1].flatten()
nu = ...
u[i,j]=nu[0]
v[i,j]=nu[1]
return (u,v)
|
Some Results
- The following figures and animations show the results of the algorithm on a few image sequences. Some of these input image sequences / videos are from the course and some are collected from the internet.
- As can be seen, the algorithm performs best if the motion of the moving object(s) in between consecutive frames is slow. To the contrary, if the motion is large, the algorithm fails and we should implement / use multiple-scale version Lucas-Kanade with image pyramids.
- Finally, with small window size, the algorithm captures subtle motions but not large motions. With large size it happens the other way.
Input Sequences
Output Optical Flow with different window sizes
window size = 15
window size = 21
Input Sequences
Output Optical Flow
Input Sequences (hamburg taxi)
Output Optical Flow
Input Sequences
Output Optical Flow
Input Sequences
Output Optical Flow
Input Sequences 
Output Optical Flow
Input Sequences
Output Optical Flow
Input Sequences
Output Optical Flow
Input Sequences
Output Optical Flow
Input Sequences
Output Optical Flow
Output Optical Flow
Input Sequences
Output Optical Flow with window size 45
Output Optical Flow with window size 10
Output Optical Flow with window size 25
Output Optical Flow with window size 45
Implementing Lucas-Kanade Optical Flow algorithm in Python
Ray EstevezFeb 27, 2018
A new data trove could teach computers to tell blind people what they need to know
Its creators pose a challenge to machine vision researchers: use the information to make assistive technology better.
A new data trove could teach computers to tell blind people what they need to know
William VorhiesFeb 27, 2018
Advanced Analytics Platforms – Big Changes in the Leaderboard
Summary: The Magic Quadrant for Advanced Analytic and ML Platforms is just out and there are some big changes in the leaderboard. Not only are there some surprising upgrades but some equally notable long falls.
The Gartner Magic Quadrant for Advanced Analytic and ML Platforms came out on February 22nd and there are some big changes in the leaderboard. Not only are there some surprising upgrades (Alteryx, KNIME, H20.ai) but some equally notable long falls for traditional players (IBM, Dataiku, and Teradata).
Blue dots are 2018, gray dots 2017.
For those of you keeping track Gartner split this field in 2017 so that “Advanced Analytic & Machine Learning Platforms” (Machine Learning added just this year) is separate from “Business Intelligence and Analytic Platforms”. There’s significant overlap in the players appearing in both including SAS, IBM, Microsoft, SAP, Alteryx, and a number of others. Additionally you’ll find all the data viz offerings there like Tableau and Qlik.
From a data science perspective though we want to keep our eye on the Advanced Analytics platforms. In prior years the changes had been much more incremental. This year’s big moves seem out of character, so we dived into the detail to see if the scoring had changed or if the nature of the offerings was the key.
Has the Scoring Changed?
We read the 2018 and 2017 reports side-by-side looking for any major changes in scoring that might explain these moves. We didn’t find any. The scoring criteria and eligibility for each year remain essentially unchanged.
Of course raters are always influenced by changes in the market and such impacts can be subtle. In the narrative explanation of markets and capabilities we found only a few hints at how scoring might have been impacted.
New Emphasis on Integrated Machine Learning
We all want our platforms and their components to operate seamlessly. Last year the criteria was perhaps a bit looser with Gartner looking for “reasonably interoperable” components. This year there is much more emphasis on a fully integrated pipeline from accessing and analyzing data through to operationalizing models and managing content.
Machine Learning is a Key Component – AI Gets Noticed but Not Scored
It was important that ML capability be either included in the platform or easily accessed through open source libraries. To their credit, Gartner does not fall into the linguistic trap of conflating Machine Learning with AI. They define the capabilities they are looking for as including “support for modern machine-learning approaches like ensemble techniques (boosting, bagging and random forests) and deep learning”.
They acknowledge the hype around AI but draw a relatively firm boundary between AI and ML, with ML as an enabler of AI. Note for example that deep learning was included above. I’m sure we’re only a year or two away from seeing more specific requirements around AI finding their way into this score.
Automated ML
Gartner is looking for features that facilitate some portion of the process like feature generation or hyperparameter tuning. Many packages contain some limited forms of these.
While some of the majors like SAS and SPSS have introduced more and more automation into their platforms, none of the pure-play AML platforms are yet included. DataRobot gets honorable mention as does Amazon (presumably referring to their new SageMaker offering). I expect within one or two years at least one pure play AML platform will make this list.
Acquisition and Consolidations
Particularly among challengers, adding capability through acquisition continues to be a key strategy though none of these seemed to move the needle much in this year.
Notable acquisitions called out by Gartner for this review include DataRobot’s acquisition of Nutonian, Progress’ acquisition of DataRPM, and TIBCO Software’s acquisition of Statistica (from Quest Software) and Alpine Data.
Several of these consolidations had the impact of taking previously ranked players off the table presumably providing room for new competitors to be ranked.
Big Winners and Losers
So if the difference is not in the scoring it must be in the detail of the offerings. The three that really caught our eye were the rise of Alteryx and H20.ai into the Leaders box and the rapid descent of IBM out.
Alteryx
From its roots in data blending and prep, Alteryx has continuously added to its on-board modeling and machine learning capabilities. In 2017 it acquired Yhat that rounded out its capabilities in model deployment and management. Then, thanks to the capital infusion from its 2017 IPO it upped its game in customer acquisition.
Alteryx’ vision has always been an easy to use platform allowing LOB managers and citizen data scientists to participate. Gartner also reports very high customer satisfaction.
Last year Gartner described this as a ‘land and expand’ strategy moving customers from self-service data acquisition all the way over to predictive analytics. This win has been more like a Super Bowl competitor working their way up field with good offense and defense. Now they’ve made the jump into the ranks of top contenders.
H2O.ai
H2O.ai moved from visionary to leader based on improvements in their offering and execution. This is a coder’s platform and won’t appeal to LOB or CDS audiences. However, thanks to being mostly open source they’ve acquired a reputation as thought leaders and innovators in the ML and deep learning communities.
While a code-centric platform does not immediately bring to mind ease of use, the Deep Water module offers a deep learning front end that abstracts away the back end details of TensorFlow and other DL packages. They also may be on the verge of creating a truly easy to use DL front end which they’ve dubbed ‘Driverless AI’. They also boast a best-in-class Spark integration.
Their open source business model in which practically everything can be downloaded for free has historically crimped their revenue which continues to rely largely on subscription based technical support. However, Gartner reports H2O.ai has 100,000 data scientist users and a strong partner group including Angoss, IBM, Intel, RapidMiner, and TIBCO, which along with its strong technical position makes it revenue prospect stronger.
IBM
Just last year IBM pulled ahead of SAS as the enthroned leader of all the vendors in this segment. This year saw a pretty remarkable downgrade on ability to execute and also on completeness of vision. Even so, with its huge built in customer base it continues to command 9.5% of the market in this segment.
Comparing last year’s analysis with this year’s, it seems that IBM has just gotten ahead of itself in too many new offerings. The core Gartner rating remains based on the solid SPSS product but notes that it seems dated and expensive to some customer. Going back to 2015 IBM had expanded the Watson brand which used to be exclusive to its famous Question Answering Machine to cover, confusingly, a greatly expanded group of analytic products. Then in 2016 IBM doubled down on the confusion by introducing their DSx (Data Science Experience) platform as a separate offering primarily aimed at open source coders.
The customers that Gartner surveyed in 2017 for this year’s rating just couldn’t figure it out. Too many offerings got in the way of support and customer satisfaction, though Gartner looked past the lack of integration to give some extra points for vision.
IBM could easily bounce back if they clear up this multi-headed approach, show us how it’s supposed to be integrated into one offering, and then provide the support to make the transition. Better luck next year.
About the author: Bill Vorhies is Editorial Director for Data Science Central and has practiced as a data scientist and commercial predictive modeler since 2001. He can be reached at:
Bill@DataScienceCentral.com
Advanced Analytics Platforms – Big Changes in the Leaderboard
Vinod SharmaFeb 27, 2018
Blockchain – The Strong Backbone for Businesses
What is Blockchain Technology? How one blockchain can have Infinite possibilities & opportunities in hand in this red ocean market world.
Some background
Blockchain as on date is mystery story for many (Including my self). We have heard lot that it yields strong potential in global supply chain. It is become the backbone tracking architecture for an evolving and fully transparent grid. Investors can also look to diversification into this burgeoning new space via first-movers like oil and gas giant BP, and tech companies like IBM. Now some companies are busy in developing a blockchain based system that will become the data security centre in this era of Big Data.
So are we moving from centralise model to decentralise model for all our business!!
So what is blockchain
It is a protocol like any other and reminds me of SwarmIntelligence. The architecture of blockchain present a more secure way of saving and securing data. On one hand this can reduce fraud on other hand it reduces transaction processing times and fees in financial domain. Blockchain in financial domain is used for below purposes (few examples)
- To send information
- Track information
- Transmit information
- Remittances or cross border money transfer
- Secure information, mainly in financial world
Blockchain is not bitcoin
Bitcoin is digital money. A virtual currency that was the first successful blockchain product. Blockchain is the technology that enables cryptocurrency and provides solid & secured foundation like bitcoin, ethereum, ripple etc. Lets stop here and put one thing in our minds “BlockChain and BitCoin are not synonyms”. Blockchains can be compared to traditional BigData or distributed databases like MongoDB as well.
Smart contracts terms of programmable autonomous contracts are ensured by this exemplary technology. Some examples of for use cases outside financial domain are as below.
- Online voting to address voter fraud.
- Can be used as secure identity
- Data security ; as data is the costliest a-fair of today’s time
- It yields strong potential in global supply chain
- Retail industry system based on blockchain that can become the data backbone
To illustrate it has many examples like above; at the same time it has many other use cases where transparency and security is lacking.
Blockhchain allows businesses to transact more smoothly and efficiently. Transform your business and digitize your transaction work flows.
Backbone for Businesses
Blockchain can work as strong backbone for businesses. This can even called as immune system of any good business of today. It is kind of distributed digital ledger technology as a powerful tool getting attention at rapid pace. Its like featuring a product that contains small blocks of brain in form of dust in contrast.
Smart Contracts – The term was first coined in 1993. SmartContracts become a buzzword in 2013 when Ethereum project about “Decentralized Platforms’” kicked in. Where it was all about an applications that run exactly as programmed without any possibility of downtime, censorship, fraud or third party interference.
Smart Contract became hero thereafter in moderne businesses across the industry. Ethereum-enabled internet-of-things platform, uses this application to allow customer to rent bicycles where they can unlock a smart lock after both parties agreed on the terms of the contract. This is example from one of the company (Slock) project.
Cloud storage – This as another application that businesses can take advantage off. The offering is all about secure cloud storage while decreasing dependency.
Hyperledger – This is an umbrella project of open source blockchains and related tools, started in December 2015 by the Linux Foundation, to support the collaborative development of blockchain-based distributed ledgers. All over the global market there are ledgers that organizations and individuals alike must trust.
Blockchain is probably the most revolutionary innovation of the last decade. We are living in Contracts aka third generation.
An angel for your Blue Ocean Shift Strategy
Blockchain can give you the market which is your own and with competition in front. If you understand your business and where to use Blockchain in it then whole of Blue Ocean is certainly yours. The blue ocean shift strategy allows you to sail freely and therefore to grow your business smoothly without any challenge. Now Lets take all action frameworks one by one.
First action – Eliminate
Which of the factors that the industry takes for granted should be eliminated. For this blockchain suites 100% as there are many of them. We can take security issues; It is considered as most secured technology of today. If you have it right you are set.
Second action – Reduce
Which factors should be reduces well below the industry’s standard. Easy one to guess; cost is your answer. it involves value innovation, which give organizations the ability to combine differentiation and low cost at the same time.
Blockchain allows for simulation.
In this setup transactions are recorded and visible to everyone, therefore it is not purely anonymous. But it does provide pseudonymity. For example, digital wallets are identified via the wallet’s public address or public key. The public key may or may not connected to personal information such as name or address. This allows anyone to transact privately and reputably with data remaining secure.
Conclusion– Blockchain allows you to transform your business and digitize transaction work flows. Finally as a result of this cutting edge technology importance business cant ignore blockchain any more hence its here to stay and grow. This technology has been referred to as the next revolution and although it’s only in the early stages for now.
Blockchain technologies record promises, trades, transactions or simply items we never want to disappear, allowing everyone in an ecosystem to keep a copy of the common system of record. Blockchain allows businesses to transact more smoothly and efficiently. To discover the power of business blockchains and distributed ledger technologies; you might have to wait for next blog post.
Disclaimer – All credits if any remains on the original contributor only.
=========================== About the Author =======================
Read about Author at : About Me
Thank you all, for spending your time reading this post. Please share your feedback / comments / critics / agreements or disagreement / remark for more details about posts, subjects and relevance please read the disclaimer.
Facebook Page Twitter Blog
Blockchain – The Strong Backbone for Businesses
Jayesh Bapu AhireFeb 27, 2018
A complete guide to Raspberry Pi
Raspberry Pi is a small computer that costs between $5 and $35 but can function as a desktop computer or be used for additional functions, such as building smart devices. Originally, the Pi was intended for usage in schools as a method of increasing interest in computers among children and as a tool to teach them basic coding.
The Raspberry Pi Foundation was founded in 2008 by a group of technicians Eben Upton, Rob Mullins, Jack Lang, Alan Mycroft, Pete Lomas, and David Braben. Since the inception, the Pi has grown into one of the most popular technology items in the world, with over eight million units sold as of 2016.
“The idea was that these tiny computers would allow for easy basic programming. Its low power usage and cost were expected to make Pis more easily available in classrooms.” The ‘Pi’ derives from the original idea to make a small computer to run only the Python programming language.
Many have seen the microcomputer’s potential, extending its capabilities by adding a camera or touchscreen module.
What are the different models?
Model A (Pi 1) of the Raspberry Pi was launched commercially on February 19, 2012. It could run Linux-based desktop operating systems, featured 256MB of RAM and a USB port, but no Ethernet port.
Since then, Pi 2 (2015) and Pi 3 (2016) were released, with Pi 3 being the best of the models. You can find detailed information regarding their features and capabilities online. The best model for your needs depends on what it will be used for.
What is it used for?
You may be surprised to know that there are two Raspberry Pi’s currently in space on the International Space Station as a part of the Astro Pi project. This project, run by British astronaut Tim Peake challenges students to write code for experiments he can perform in space.
This is just one of many examples of the extensive capabilities of Raspberry Pi, not to mention its use as a supercomputer and underwater drone.
Why is Pi useful?
With Pi, you can complete a variety of tasks that do not require much processing power and can enhance the small device with modules. It can help you save on space and cut costs while learning new skills and adding capabilities.
How can I use it?
- Learn how to code
- Use it as a desktop PC
- Make a media center
- Use it as a gaming console
- Build a camera attachment
- Make a clock or FM radio
What do others say?
It’s impressive how (relatively) potent the $35 Raspberry Pi 3 can be, but the board won’t work by itself. You’ll need to connect it to a monitor or TV via HDMI; connect it to power via a 5-volt micro-USB cord capable of drawing 2.5 amps from the wall (I used a Kindle Fire charger; my Moto X’s charger wasn’t sufficient); and connect yourself via a USB or Bluetooth keyboard and mouse, though you’ll need to set it up using USB peripherals before you can activate Bluetooth pairing. Grabbing a case or at least a box to house the Pi is a swell idea too, because the board is fully exposed in its default state.
To Summarize
Raspberry Pi is an affordable way of learning basic coding and grasping fundamental computer components. Working hands-on with Pi can help individuals develop their practical skills and provide the potential for a wide range of capabilities with this device. Start experimenting, see what you can learn, and better yet, create!
A complete guide to Raspberry Pi
Recent Comments