Search
Code Directory
 ASP
 ASP.NET
 C/C++
 CFML
 CGI/PERL
 Delphi
 Development
 Flash
 HTML
 Java
 JavaScript
 Pascal
 PHP
 Python
 SQL
 Tools
 Visual Basic & VB.NET
 XML
New Code
dotConnect for Dynamics CRM 1.7
Entity Developer 6.3
ODBC Driver for BigCommerce 1.4
dbForge Documenter for Oracle 1.0
dbForge Data Generator for Oracle 2.0
Odoo MobiCraft Theme 1.0
AnyChart JS Charts and Dashboards 8.4.0
IP2Location Geolocation Database October.2018
AnyGantt JS Gantt Charts 8.4.0
dbForge Data Compare for PostgreSQL 3.1
Paste phpSoftPro 1.4.1
Bytescout PDF SDK 1.8.1.243
Odoo Crafito Theme 1.0
Uber Clone- Taxi Booking App 4.1
Excel Add-in for BigCommerce 1.7
Top Code
Travel Booking script 1.0.4
Online Vacation Rental Booking Website Script 4.3.0
PHP Point of sale 10.0
JadaSite e-commerce solution 2.03
Traveling Salesman Problem (TSP) using Simulated Annealing 1.0
Online Food Ordeing System 1.0
TIC TAC TOE AI GAME Script 1.1
image compression using wavelet transform 1.0
Hysteresis Thresholding 1.0
Ping Pong Game Code Script 1.1
Ticket Booking System 1.0
MATLAB Support Package for Arduino (aka ArduinoIO Package) 1.0
Jlguiapplet (mp3&ogg Player) 2.1.2002
Image compression demo usins KL transform 1.0
SuperGeek Free Document OCR 2.5.6
Top Rated
Output Messenger 1.8.0
Aliexpress Clone- Ec21 Script 1
Indiegogo Clone 3.0
Advanced MLM Software 1.2
Online Food Ordeing System 1.0
PHP Image Resize Script 1.0
Best Spotify Clone 1.0
Get Random Record Based on Weight 1.0.0
PHP Point of sale 10.0
Travel Portal Script 9.29
Excel Add-in for Bigcommerce 1.6
Magento Product Designer 1.0
OFOS - Just Eat Clone Script 1.0
PrestaShop Upload Images Module 1.2.1
Trading Software 1.2.4
Kernel decomposition 1.0
File ID: 82222






Kernel decomposition 1.0
Download Kernel decomposition 1.0http://www.mathworks.comReport Error Link
License: Shareware
File Size: 10.0 KB
Downloads: 0
Submit Rating:
Kernel decomposition 1.0 Description
Description: This function does the decomposition of a separable nD kernel into
its 1D components, such that a convolution with each of these
components yields the same result as a convolution with the full nD
kernel, at a drastic reduction in computational cost.

SYNTAX:
=======
[K1,KN,ERR] = DECOMPOSE_KERNEL(H)
computes a set of 1D kernels K1{1}, K1{2}, ... K1{N} such that the
convolution of an image with all of these in turn yields the same
result as a convolution with the N-dimensional input kernel H:
RES1 = CONVN(IMG,H);
RES2 = IMG;
FOR II=1:LENGTH(K1)
RES2 = CONVN(RES2,K1{II});
END

KN is the reconstruction of the original kernel H from the 1D
kernels K1, and ERR is the sum of absolute differences between H
and KN.
The syntax mimics Dirk-Jan Kroon's submission to the FileExchange
(see below).

EXPLANATION:
============

In general, for a 2D kernel H, the convolution with 2D image F:
G = F * H
is identical to the convolution of the image with column vector H1
and convolution of the result with row vector H2:
G = ( F * H1 ) * H2 .
In MATLAB speak, this means that
> CONV2(F,H) == CONV2(CONV2(F,H1),H2)

Because of the properties of the convolution,
( F * H1 ) * H2 = F * ( H1 * H2 ) ,
meaning that the convolution of the two 1D filters with each other
results in the original filter H. And because H1 is a column vector
and H2 a row vector,
H = H1 * H2 = H1 H2 .
Thus, we need to find two vectors whose product yields the matrix H.
In MATLAB speak we need to solve the equation
> H1*H2 == H

The function in the standard MATLAB toolbox, FILTER2, does just
this, and it does it using singular value decomposition:
U S V' = H ,
H1(i) = U(i,1) S(1,1)^0.5 ,
H2(i) = V(i,1)* S(1,1)^0.5 . (the * here is the conjugate!)

Note that, if the kernel H is separable, all values of S are zero
except S(1,1). Also note that this is an under-determined problem,
in the sense that
H = H1 H2 = ( a H1 ) ( 1/a H2 ) ;
that is, it is possible to multiply one 1D kernel with any value
and compensate by dividing the other kernel with the same value.
Our solution will, in effect, just choose one of the infinite number
of (equivalent) solutions.

To extend this concept to nD, what we need to understand is that it
is possible to collapse all dimensions except one, obtaining a 2D
matrix, and solve the above equation. This results in a 1D kernel
and an (n-1)D kernel. Repeat the process until all you have is a
set of 1D kernels and you're done!

This function is inspired by a solution to this problem that
Dirk-Jan Kroon posted on the File Exchange recently:
http://www.mathworks.com/matlabcentral/fil...l-in-1d-kernels
His solution does the whole decomposition in one go, by setting up
one big set of equations. He noted a problem with negative values,
which produce complex 1D kernels. The magnitude of the result is
correct, but the sign is lost. He needs to resort to some heuristic
to determine the sign of each element. What he didn't notice (or
didn't mention) is the problem that his solution has with 0 values.
The SVD solution doesn't have this problem, although it sometimes
does produce a slightly worse solution. For example, in the first
example below, Dirk-Jan Kroon's solution is exact, whereas this one
produces a very small error. Where Dirk-Jan Kroon's solution cannot
find the exact solution, this algorithm generally does better.

EXAMPLES:
=========

Simplest 5D example:

H = ones(5,7,4,1,5);

[K1,~,err] = SeparateKernel(H); % D.Kroon's submission to FileEx.
err

[k1,~,err] = decompose_kernel(H);
err

2D example taken from Dirk-Jan Kroon's submission:

a = permute(rand(4,1),[1 2 3])-0.5;
b = permute(rand(4,1),[2 1 3])-0.5;
H = repmat(a,[1 4]).*repmat(b,[4 1]);

[K1,~,err] = SeparateKernel(H);
err

[k1,~,err] = decompose_kernel(H);
err

2D example for which Dirk-Jan Kroon's solution has problems:

H = [1,2,3,2,1]'*[1,1,3,0,3,1,1];

[K1,~,err] = SeparateKernel(H);
err

[k1,~,err] = decompose_kernel(H);
err

3D example that's not separable:

H = rand(5,5,3);

[K1,~,err] = SeparateKernel(H);
err

[k1,~,err] = decompose_kernel(H);

Example to apply a convolution using the decomposed kernel:

img = randn(50,50,50);
h = ones(7,7,7);
tic;
res1 = convn(img,h);
toc
k1 = decompose_kernel(h);
tic;
res2 = img;
for ii=1:length(k1)
res2 = convn(res2,k1{ii});
end
toc
rms_diff = sqrt(mean((res1(:)-res2(:)).^2))

License: Shareware

Related: correct, Resort, heuristic, magnitude, Complex, Negative, produce, determine

O/S:BSD, Linux, Solaris, Mac OS X

File Size: 10.0 KB

Downloads: 0



More Similar Code

This function SEPARATEKERNEL will separate ( do decomposition of ) any
2D, 3D or nD kernel into 1D kernels. Of course only a sub-set of Kernels
are separable such as a Gaussian Kernel, but it will give approximations for non-separable kernels.

Separating a 3D or 5D image filter into 1D filters will give an large
speed-up in image filtering with for instance the function imfilter.

[K1 KN...



The Empirical Mode Decomposition is a technique to decompose a given signal into a set of elemental signals called Intrinsic Mode Functions. The Empirical Mode Decomposition is the base of the so-called d-deDUHilbert-Huang Transformd-deDt that...



The Gaussian Kernel can be changed to any desired kernel. However such a change will not dramatically improve results. This is a variant of ridge regression using the kernel trick (Mercers Theorem).



This technique takes advantage of the kernel trick that can be used in PCA. This is a tutorial only and is slow for large data sets.
In line 30 the kernel can be changed. Any Kernel should do it.
Ref :...



Transform a inner product matrix or kernel matrix to a square of distance matrix



2 dimenstion Kernel density Estimation with Sheater Jones bandwidth for each variable.
Also the Sheater Jones bandwidth selection
method will work for the univariate.



CMS Kernel is the basic libraries of Content Management System.



PHP Kernel, PHP/AJAX/DHTML framework for rapid applications development.

Automatic environment recognition:
- mobile devices;
- SOAP;
- XML-RPC;
- RSS.



The TatukGIS Developer Kernel (DK) is a comprehensive GIS development toolkit provided as a Delphi/C++Builder VCL. The toolkit incorporates 2,200 public/protected functions and properties in 120 classes. The DK is royalty-free for desktop...



The TatukGIS Developer Kernel (DK) is a comprehensive GIS development toolkit provided as a Delphi/C++Builder VCL (as well as a ActiveX control supporting .NET). The toolkit incorporates 2,300 public/protected functions and properties in 130...

User Review for Kernel decomposition
- required fields
     

Please enter text on the image