[vtkusers] Re: Surface registration of two data sets, are there any vtk algorithms?

[Tim Hutton]

George, to save you some time, here are more details of the code I'm using
at the moment. I'm mailing this to the group in the hope that someone will
do the boring work of getting this into a new vtk class, I'm off on holiday
tomorrow, if no-one has done it by the new year I guess I'll have to do it
myself. ;)

- Given 2 vtkPolyData's: 'mesh' and 'target', create a vtkCellLocator for
the target:

vtkCellLocator *locator = vtkCellLocator::New();
locator->SetDataSet(target);
locator->SetNumberOfCellsPerBucket(1);
locator->BuildLocator();

- Create the transform classes (will be reused on each iteration):

vtkLandmarkTransform *matcher = vtkLandmarkTransform::New();
vtkTransformPolyDataFilter *transformer = vtkTransformPolyDataFilter::New();

- Create a replacement set of points for the vertices of the moving mesh:

vtkPoints *points = vtkPoints::New();
points->SetNumberOfPoints(mesh->GetNumberOfPoints());

- Iterate through this loop:

bool converged_yet=false;
do {

	// fill 'points' with the closest points to each vertex in the template mesh
	int cellId,subId;
	float dist2;
	for(int i=0;i<mesh->GetNumberOfPoints();i++)
	{

locator->FindClosestPoint(mesh->GetPoints()->GetPoint(i),points->GetPoint(i)
,cellId,subId,dist2);
	}

	// move mesh to best match the target
	matcher->SetSourceLandmarks(mesh->GetPoints());
	matcher->SetTargetLandmarks(points);
	transformer->SetTransform(matcher);
	transformer->SetInput(mesh);
	transformer->Update();
	mesh->SetPoints(transformer->GetOutput()->GetPoints());
	mesh->Modified();

	// need some check for convergence here
	converged_yet = ...
	// (I'm just running 100 iterations for now)

} while(!converged_yet);

Of course there's lots missing but this is the basic core of the algorithm
as might be implemented in VTK. The actual ICP algorithm has lots of nice
ways of dealing with the bits of the surface that don't match but you might
not need them.

Merry Christmas one and all! - said Tiny Tim.


At 09:31 14/12/00 +0300, you wrote:
>Hi Tim,
>Thanks a lot for your useful information,  I will try to apply the two
classes.
>
>Best regards
>George
>
>>
>>
>> Date: Wed, 13 Dec 2000 11:11:49 +0000
>> To: vtkusers at public.kitware.com
>> From: Tim Hutton <T.Hutton at eastman.ucl.ac.uk>
>> Subject: Re: [vtkusers] Surface registration of two data sets, are
>> there any vtk algorithms?
>>
>> Aha! Was wondering if anyone else needed this.
>>
>> The standard way to match two surfaces would have to be iterative closest
>> point (ICP). The core of the algorithm is to match each vertex in one
>> surface with the closest surface point on the other, then apply the rigid
>> transformation that moves one surface to best match the other. This has to
>> be iterated to get proper convergence of the surfaces.
>>
>> VTK is ideal for this kind of stuff, the two classes vtkCellLocator and
>> vtkLandmarkTransform in particular do all the hard work for you. If there
>> is a desire, I'd be happy to help with a vtkIterativeClosestPointTransform
>> (or whatever) class - trouble is, it's not really visualization, more
>> computational geometry; there's an issue of whether to keep bloating VTK
>> with these things.
>>
>> Tim.
>>
>> At 10:13 13/12/00 +0300, you wrote:
>> >I am wondering whether there could be a program written in vtk which can
>> determine the transformation
>> >between two surface data sets. I have two surface data sets of a bone
>> which I have generated using different
>> >
>> >imaging modalities: one from CT-imaging and the other from laser radar
>> imaging. I would like to obtain the
>> >transformation (rotation and translation) between the two data sets using
>> surface matching techniques.
>> >Anybody out there who knows where I can obtain such surface matching
>> algorithms? Your assistance will be
>> >highly appreciated.
>> >
>> >Best regards
>> >
>> >George kamucha
>> >Department of High Frequency Engineering
>> >University of Kassel
>> >Wilhelmshoeher Allee 73
>> >34121 Kassel
>> >Germany
>> >
>> >
>
>
>_______________________________________________
>This is the private VTK discussion list. 
>Please keep messages on-topic. Check the FAQ at:
<http://public.kitware.com/cgi-bin/vtkfaq>
>Follow this link to subscribe/unsubscribe:
>http://public.kitware.com/mailman/listinfo/vtkusers
>
>
---------------------------------------------------------------------------
Tim Hutton,                        http://www.eastman.ucl.ac.uk/~dmi/MINORI
Research Fellow & PhD student,                   T.Hutton at eastman.ucl.ac.uk
MINORI Project, Biomedical Informatics Unit,     Tel: [+44] (0)20 7915 2344
Eastman Dental Institute, UCL,                   Fax: [+44] (0)20 7915 2303
256 Gray's Inn Road, London WC1X 8LD, UK      Mobile: [+44] (0)7776 070 563  
---------------------------------------------------------------------------
This email represents the views of the sender alone and must not be
construed as representing the views of the Eastman Dental Institute. It may
contain confidential information and may be protected by law as a legally
privileged document and copyright work. Its content should not be disclosed
and it should not be given or copied to anyone other than the person(s)
named or referenced above. If you have received this email in error, please
contact the sender.